diff options
Diffstat (limited to 'src/lib/util/huffman.h')
-rw-r--r-- | src/lib/util/huffman.h | 217 |
1 files changed, 184 insertions, 33 deletions
diff --git a/src/lib/util/huffman.h b/src/lib/util/huffman.h index f512975c77f..10dc301e7df 100644 --- a/src/lib/util/huffman.h +++ b/src/lib/util/huffman.h @@ -2,7 +2,7 @@ huffman.h - Huffman compression routines. + Static Huffman compression and decompression helpers. **************************************************************************** @@ -37,19 +37,22 @@ ***************************************************************************/ +#pragma once + #ifndef __HUFFMAN_H__ +#define __HUFFMAN_H__ #include "osdcore.h" +#include "bitstream.h" -/*************************************************************************** - CONSTANTS -***************************************************************************/ +//************************************************************************** +// CONSTANTS +//************************************************************************** -enum _huffman_error +enum huffman_error { HUFFERR_NONE = 0, - HUFFERR_OUT_OF_MEMORY, HUFFERR_TOO_MANY_BITS, HUFFERR_INVALID_DATA, HUFFERR_INPUT_BUFFER_TOO_SMALL, @@ -57,45 +60,193 @@ enum _huffman_error HUFFERR_INTERNAL_INCONSISTENCY, HUFFERR_TOO_MANY_CONTEXTS }; -typedef enum _huffman_error huffman_error; -/*************************************************************************** - TYPE DEFINITIONS -***************************************************************************/ +//************************************************************************** +// TYPE DEFINITIONS +//************************************************************************** -typedef UINT16 huffman_lookup_value; +// ======================> huffman_context_base -typedef struct _huffman_context huffman_context; +// 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 -/*************************************************************************** - FUNCTION PROTOTYPES -***************************************************************************/ +// 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, NULL, 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 -huffman_error huffman_create_context(huffman_context **context, int maxbits); -void huffman_free_context(huffman_context *context); +// 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, NULL, 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_error huffman_import_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 *actlength); -huffman_error huffman_export_tree(huffman_context *context, UINT8 *dest, UINT32 dlength, UINT32 *actlength); -huffman_error huffman_deltarle_import_tree(huffman_context *context, const UINT8 *source, UINT32 slength, UINT32 *actlength); -huffman_error huffman_deltarle_export_tree(huffman_context *context, UINT8 *dest, UINT32 dlength, UINT32 *actlength); -huffman_error huffman_compute_tree(huffman_context *context, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor); -huffman_error huffman_compute_tree_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor); -huffman_error huffman_deltarle_compute_tree(huffman_context *context, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor); -huffman_error huffman_deltarle_compute_tree_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor); +// ======================> 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); -huffman_error huffman_encode_data(huffman_context *context, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor, UINT8 *dest, UINT32 dlength, UINT32 *actlength); -huffman_error huffman_encode_data_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor, UINT8 *dest, UINT32 dlength, UINT32 *actlength); -huffman_error huffman_deltarle_encode_data(huffman_context *context, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor, UINT8 *dest, UINT32 dlength, UINT32 *actlength); -huffman_error huffman_deltarle_encode_data_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 swidth, UINT32 sheight, UINT32 sstride, UINT32 sxor, UINT8 *dest, UINT32 dlength, UINT32 *actlength); + // return the value + return lookup >> 5; +} -huffman_error huffman_decode_data(huffman_context *context, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength); -huffman_error huffman_decode_data_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength); -huffman_error huffman_deltarle_decode_data(huffman_context *context, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength); -huffman_error huffman_deltarle_decode_data_interleaved(int numcontexts, huffman_context **contexts, const UINT8 *source, UINT32 slength, UINT8 *dest, UINT32 dwidth, UINT32 dheight, UINT32 dstride, UINT32 dxor, UINT32 *actlength); #endif |