summaryrefslogblamecommitdiffstatshomepage
path: root/src/lib/util/huffman.h
blob: a2bed42bbf939fec8c0ceddcfa3339be91b44e26 (plain) (tree)
1
2
3
4
5
6
7
8
9
10

                                



                                                                            
                                                         
 

                                                                            

            
                     
                     

                    
                      

 


                                                                            
 
                  

                         



                                        

                                       
  


 


                                                                            
 
                                               
 








                                       




                                                                                                  
          
 






















                                                                                                            






                                                                                                                 
  

 
                                          
 






                                                     
                                                                                                                            




                                                                                       
 



                                                            
 

                                             

                                                                



                                          
 






                                                     
                                                                                                          


                                                
 


                                                        
 

                                             

                                                              
  
 
 







                                                     
 



                                                                                                                      
 







                                                     
 
















































                                                                                                  
 


                           
 

      
// license:BSD-3-Clause
// copyright-holders:Aaron Giles
/***************************************************************************

    huffman.h

    Static Huffman compression and decompression helpers.

***************************************************************************/

#pragma once

#ifndef __HUFFMAN_H__
#define __HUFFMAN_H__

#include "osdcore.h"
#include "bitstream.h"


//**************************************************************************
//  CONSTANTS
//**************************************************************************

enum huffman_error
{
	HUFFERR_NONE = 0,
	HUFFERR_TOO_MANY_BITS,
	HUFFERR_INVALID_DATA,
	HUFFERR_INPUT_BUFFER_TOO_SMALL,
	HUFFERR_OUTPUT_BUFFER_TOO_SMALL,
	HUFFERR_INTERNAL_INCONSISTENCY,
	HUFFERR_TOO_MANY_CONTEXTS
};



//**************************************************************************
//  TYPE DEFINITIONS
//**************************************************************************

// ======================> huffman_context_base

// base class for encoding and decoding
class huffman_context_base
{
protected:
	typedef UINT16 lookup_value;

	// a node in the huffman tree
	struct node_t
	{
		node_t *            m_parent;               // pointer to parent node
		UINT32              m_count;                // number of hits on this node
		UINT32              m_weight;               // assigned weight of this node
		UINT32              m_bits;                 // bits used to encode the node
		UINT8               m_numbits;              // number of bits needed for this node
	};

	// construction/destruction
	huffman_context_base(int numcodes, int maxbits, lookup_value *lookup, UINT32 *histo, node_t *nodes);

	// tree creation
	huffman_error compute_tree_from_histo();

	// static tree import; huffman is notably more efficient
	huffman_error import_tree_rle(bitstream_in &bitbuf);
	huffman_error import_tree_huffman(bitstream_in &bitbuf);

	// static tree export
	huffman_error export_tree_rle(bitstream_out &bitbuf);
	huffman_error export_tree_huffman(bitstream_out &bitbuf);

	// internal helpers
	void write_rle_tree_bits(bitstream_out &bitbuf, int value, int repcount, int numbits);
	static int CLIB_DECL tree_node_compare(const void *item1, const void *item2);
	int build_tree(UINT32 totaldata, UINT32 totalweight);
	huffman_error assign_canonical_codes();
	void build_lookup_table();

protected:
	// internal state
	UINT32                  m_numcodes;             // number of total codes being processed
	UINT8                   m_maxbits;              // maximum bits per code
	UINT8                   m_prevdata;             // value of the previous data (for delta-RLE encoding)
	int                     m_rleremaining;         // number of RLE bytes remaining (for delta-RLE encoding)
	lookup_value *          m_lookup;               // pointer to the lookup table
	UINT32 *                m_datahisto;            // histogram of data values
	node_t *                m_huffnode;             // array of nodes
};


// ======================> huffman_encoder

// template class for encoding
template<int _NumCodes = 256, int _MaxBits = 16>
class huffman_encoder : public huffman_context_base
{
public:
	// pass through to the underlying constructor
	huffman_encoder()
		: huffman_context_base(_NumCodes, _MaxBits, nullptr, m_datahisto_array, m_huffnode_array) { histo_reset(); }

	// single item operations
	void histo_reset() { memset(m_datahisto_array, 0, sizeof(m_datahisto_array)); }
	void histo_one(UINT32 data);
	void encode_one(bitstream_out &bitbuf, UINT32 data);

	// expose tree computation and export
	using huffman_context_base::compute_tree_from_histo;
	using huffman_context_base::export_tree_rle;
	using huffman_context_base::export_tree_huffman;

private:
	// array versions of the info we need
	UINT32                  m_datahisto_array[_NumCodes];
	node_t                  m_huffnode_array[_NumCodes * 2];
};


// ======================> huffman_decoder

// template class for decoding
template<int _NumCodes = 256, int _MaxBits = 16>
class huffman_decoder : public huffman_context_base
{
public:
	// pass through to the underlying constructor
	huffman_decoder()
		: huffman_context_base(_NumCodes, _MaxBits, m_lookup_array, nullptr, m_huffnode_array) { }

	// single item operations
	UINT32 decode_one(bitstream_in &bitbuf);

	// expose tree import
	using huffman_context_base::import_tree_rle;
	using huffman_context_base::import_tree_huffman;

private:
	// array versions of the info we need
	node_t                  m_huffnode_array[_NumCodes];
	lookup_value            m_lookup_array[1 << _MaxBits];
};


// ======================> huffman_8bit_encoder

// generic 8-bit encoder/decoder
class huffman_8bit_encoder : public huffman_encoder<>
{
public:
	// construction/destruction
	huffman_8bit_encoder();

	// operations
	huffman_error encode(const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 destlength, UINT32 &complength);
};


// ======================> huffman_8bit_decoder

// generic 8-bit encoder/decoder
class huffman_8bit_decoder : public huffman_decoder<>
{
public:
	// construction/destruction
	huffman_8bit_decoder();

	// operations
	huffman_error decode(const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 destlength);
};



//**************************************************************************
//  INLINE FUNCTIONS
//**************************************************************************

//-------------------------------------------------
//  histo_one - update the histogram
//-------------------------------------------------

template<int _NumCodes, int _MaxBits>
inline void huffman_encoder<_NumCodes, _MaxBits>::histo_one(UINT32 data)
{
	m_datahisto[data]++;
}


//-------------------------------------------------
//  encode_one - encode a single code to the
//  huffman stream
//-------------------------------------------------

template<int _NumCodes, int _MaxBits>
inline void huffman_encoder<_NumCodes, _MaxBits>::encode_one(bitstream_out &bitbuf, UINT32 data)
{
	// write the data
	node_t &node = m_huffnode[data];
	bitbuf.write(node.m_bits, node.m_numbits);
}


//-------------------------------------------------
//  decode_one - decode a single code from the
//  huffman stream
//-------------------------------------------------

template<int _NumCodes, int _MaxBits>
inline UINT32 huffman_decoder<_NumCodes, _MaxBits>::decode_one(bitstream_in &bitbuf)
{
	// peek ahead to get maxbits worth of data
	UINT32 bits = bitbuf.peek(m_maxbits);

	// look it up, then remove the actual number of bits for this code
	lookup_value lookup = m_lookup[bits];
	bitbuf.remove(lookup & 0x1f);

	// return the value
	return lookup >> 5;
}


#endif