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