diff options
Diffstat (limited to 'trunk/src/lib/util/huffman.h')
-rw-r--r-- | trunk/src/lib/util/huffman.h | 252 |
1 files changed, 252 insertions, 0 deletions
diff --git a/trunk/src/lib/util/huffman.h b/trunk/src/lib/util/huffman.h new file mode 100644 index 00000000000..47525d82ed6 --- /dev/null +++ b/trunk/src/lib/util/huffman.h @@ -0,0 +1,252 @@ +/*************************************************************************** + + huffman.h + + Static Huffman compression and decompression helpers. + +**************************************************************************** + + Copyright Aaron Giles + All rights reserved. + + Redistribution and use in source and binary forms, with or without + modification, are permitted provided that the following conditions are + met: + + * Redistributions of source code must retain the above copyright + notice, this list of conditions and the following disclaimer. + * Redistributions in binary form must reproduce the above copyright + notice, this list of conditions and the following disclaimer in + the documentation and/or other materials provided with the + distribution. + * Neither the name 'MAME' nor the names of its contributors may be + used to endorse or promote products derived from this software + without specific prior written permission. + + THIS SOFTWARE IS PROVIDED BY AARON GILES ''AS IS'' AND ANY EXPRESS OR + IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED + WARRANTIES OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE + DISCLAIMED. IN NO EVENT SHALL AARON GILES BE LIABLE FOR ANY DIRECT, + INDIRECT, INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES + (INCLUDING, BUT NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR + SERVICES; LOSS OF USE, DATA, OR PROFITS; OR BUSINESS INTERRUPTION) + HOWEVER CAUSED AND ON ANY THEORY OF LIABILITY, WHETHER IN CONTRACT, + STRICT LIABILITY, OR TORT (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING + IN ANY WAY OUT OF THE USE OF THIS SOFTWARE, EVEN IF ADVISED OF THE + POSSIBILITY OF SUCH DAMAGE. + +***************************************************************************/ + +#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, 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 + +// 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_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 |