summaryrefslogtreecommitdiffstatshomepage
path: root/trunk/src/lib/util/huffman.h
diff options
context:
space:
mode:
Diffstat (limited to 'trunk/src/lib/util/huffman.h')
-rw-r--r--trunk/src/lib/util/huffman.h252
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