// license:BSD-3-Clause // copyright-holders:Aaron Giles /*************************************************************************** huffman.h Static Huffman compression and decompression helpers. ***************************************************************************/ #ifndef MAME_UTIL_HUFFMAN_H #define MAME_UTIL_HUFFMAN_H #pragma once #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_t lookup_value; // a node in the huffman tree struct node_t { node_t * m_parent; // pointer to parent node uint32_t m_count; // number of hits on this node uint32_t m_weight; // assigned weight of this node uint32_t m_bits; // bits used to encode the node uint8_t m_numbits; // number of bits needed for this node }; // construction/destruction huffman_context_base(int numcodes, int maxbits, lookup_value *lookup, uint32_t *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_t totaldata, uint32_t totalweight); huffman_error assign_canonical_codes(); void build_lookup_table(); protected: // internal state uint32_t m_numcodes; // number of total codes being processed uint8_t m_maxbits; // maximum bits per code uint8_t 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_t * m_datahisto; // histogram of data values node_t * m_huffnode; // array of nodes }; // ======================> huffman_encoder // template class for encoding template 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_t data); void encode_one(bitstream_out &bitbuf, uint32_t 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_t m_datahisto_array[_NumCodes]; node_t m_huffnode_array[_NumCodes * 2]; }; // ======================> huffman_decoder // template class for decoding template 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_t 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_t *source, uint32_t slength, uint8_t *dest, uint32_t destlength, uint32_t &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_t *source, uint32_t slength, uint8_t *dest, uint32_t destlength); }; //************************************************************************** // INLINE FUNCTIONS //************************************************************************** //------------------------------------------------- // histo_one - update the histogram //------------------------------------------------- template inline void huffman_encoder<_NumCodes, _MaxBits>::histo_one(uint32_t data) { m_datahisto[data]++; } //------------------------------------------------- // encode_one - encode a single code to the // huffman stream //------------------------------------------------- template inline void huffman_encoder<_NumCodes, _MaxBits>::encode_one(bitstream_out &bitbuf, uint32_t 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 inline uint32_t huffman_decoder<_NumCodes, _MaxBits>::decode_one(bitstream_in &bitbuf) { // peek ahead to get maxbits worth of data uint32_t 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 // MAME_UTIL_HUFFMAN_H 9:29 +0200'>2020-05-191-2/+2 * input_buffer, output_latch, z80dma: Eliminate now-unnecessary bus_r and bus_w... AJR2020-03-181-4/+4 * Correct region widths in miscellaneous drivers and devices (nw) AJR2019-11-161-1/+1 * (nw) Clean up the mess on master Vas Crabb2019-03-261-25/+27 * Revert "conflict resolution (nw)" andreasnaive2019-03-251-27/+25 * mame\drivers: removed most MCFG and MACHINE_CONFIG macros from the rest of th... Ivan Vangelista2019-02-221-5/+6 * output_latch: removed MCFG macros (nw) Ivan Vangelista2019-01-291-11/+12 * imagedev\floppy: removed MCFG macros (nw) Ivan Vangelista2019-01-281-4/+4 * src\devices\machine: more MCFG macros removal (nw) Ivan Vangelista2019-01-171-5/+5 * Include floppy.h explicitly in drivers and bus cards, rather than indirectly ... AJR2018-11-251-0/+1 * rs232: another batch of MCFG removal (nw) Ivan Vangelista2018-10-221-4/+4 * wd_fdc: removed MCFG macros (nw) Ivan Vangelista2018-09-061-3/+3 * -7200fifo, 7400, 7404, 74123, 74145, 74148, 74153, 74157, 74161, 74259: [Ryan... mooglyguy2018-08-111-9/+9 * slicer : fixed regression from last November. Robbbert2018-07-261-1/+8 * private: use (S, T, U, V) (nw) (#3720) David Haywood2018-07-011-2/+4 * as if millions of this pointers suddenly cried out in terror, and were sudden... Vas Crabb2018-06-081-4/+4 * wd_fdc family, msm5832: Eliminate customized MCFG_XXX_ADD macros (nw) AJR2018-05-271-3/+3 * Removed DRIVER_INIT-related macros, made driver init entry in GAME/COMP/CONS ... MooglyGuy2018-05-131-1/+1 * Streamline machine configuration macros - everyone's a device edition. Vas Crabb2018-05-061-25/+25 * Make MCFG_DEVICE_ADD and callable device types more flexible: Vas Crabb2018-05-041-4/+5 * Address maps macros removal, pass 1 [O. Galibert] Olivier Galibert2018-03-141-15/+17 * API change: Memory maps are now methods of the owner class [O. Galibert] Olivier Galibert2018-02-121-2/+4 * xtal.h is dead, long live to xtal.cpp [O. Galibert] Olivier Galibert2018-01-231-3/+3 * API Change: Machine configs are now a method of the owner class, and the prot... Olivier Galibert2018-01-171-1/+2 * slicer: Add 74LS259 (nw) AJR2017-11-221-30/+23