diff options
author | 2012-02-16 09:47:18 +0000 | |
---|---|---|
committer | 2012-02-16 09:47:18 +0000 | |
commit | f0823886a66100e193d6eeb0402eb872a67fa07d (patch) | |
tree | a68b35942d63e5fcaf2311812dba976ad18cd5b6 /src/lib/util/huffman.h | |
parent | e6dad3759374373e3ce69a76869f16e83ba74df5 (diff) |
Major CHD/chdman update. The CHD version number has been increased
from 4 to 5. This means any diff CHDs will no longer work. If you
absolutely need to keep the data for any existing ones you have,
find both the diff CHD and the original CHD for the game in question
and upgrade using these commands:
rename diff\game.dif diff\game-old.dif
chdman copy -i diff\game-old.dif -ip roms\game.chd -o diff\game.dif -op roms\game.chd -c none
Specifics regarding this change:
Defined a new CHD version 5. New features/behaviors of this version:
- support for up to 4 codecs; each block can use 1 of the 4
- new LZMA codec, which tends to do better than zlib overall
- new FLAC codec, primarily used for CDs (but can be applied anywhere)
- upgraded AVHuff codec now uses FLAC for encoding audio
- new Huffman codec, used to catch more nearly-uncompressable blocks
- compressed CHDs now use a compressed map for significant savings
- CHDs now are aware of a "unit" size; each hunk holds 1 or more units
(in general units map to sectors for hard disks/CDs)
- diff'ing against a parent now diffs at the unit level, greatly
improving compression
Rewrote and modernized chd.c. CHD versions prior to 3 are unsupported,
and version 3/4 CHDs are only supported for reading. Creating a new
CHD now leaves the file open. Added methods to read and write at the
unit and byte level, removing the need to handle this manually. Added
metadata access methods that pass astrings and dynamic_buffers to
simplify the interfaces. A companion class chd_compressor now
implements full multithreaded compression, analyzing and compressing
multiple hunks independently in parallel. Split the codec
implementations out into a separate file chdcodec.*
Updated harddisk.c and cdrom.c to rely on the caching/byte-level read/
write capabilities of the chd_file class. cdrom.c (and chdman) now also
pad CDs to 4-frame boundaries instead of hunk boundaries, ensuring that
the same SHA1 hashes are produced regardless of the hunk size.
Rewrote chdman.exe entirely, switching from positional parameters to
proper options. Use "chdman help" to get a list of commands, and
"chdman help <command>" to get help for any particular command. Many
redundant commands were removed now that additional flexibility is
available. Some basic mappings:
Old: chdman -createblankhd <out.chd> <cyls> <heads> <secs>
New: chdman createhd -o <out.chd> -chs <cyls>,<heads>,<secs>
Old: chdman -createuncomphd <in.raw> <out.chd> ....
New: chdman createhd -i <in.raw> -o <out.chd> -c none ....
Old: chdman -verifyfix <in.chd>
New: chdman verify -i <in.chd> -f
Old: chdman -merge <parent.chd> <diff.chd> <out.chd>
New: chdman copy -i <diff.chd> -ip <parent.chd> -o <out.chd>
Old: chdman -diff <parent.chd> <compare.chd> <diff.chd>
New: chdman copy -i <compare.chd> -o <diff.chd> -op <parent.chd>
Old: chdman -update <in.chd> <out.chd>
New: chdman copy -i <in.chd> -o <out.chd>
Added new core file coretmpl.h to hold core template classes. For now
just one class, dynamic_array<> is defined, which acts like an array
of a given object but which can be appended to and/or resized. Also
defines dynamic_buffer as dynamic_array<UINT8> for holding an
arbitrary buffer of bytes. Expect to see these used a lot.
Added new core helper hashing.c/.h which defines classes for each of
the common hashing methods and creator classes to wrap the
computation of these hashes. A future work item is to reimplement
the core emulator hashing code using these.
Split bit buffer helpers out into C++ classes and into their own
public header in bitstream.h.
Updated huffman.c/.h to C++, and changed the interface to make it
more flexible to use in nonstandard ways. Also added huffman compression
of the static tree for slightly better compression rates.
Created flac.c/.h as simplified C++ wrappers around the FLAC interface.
A future work item is to convert the samples sound device to a modern
device and leverage this for reading FLAC files.
Renamed avcomp.* to avhuff.*, updated to C++, and added support for
FLAC as the audio encoding mechanism. The old huffman audio is still
supported for decode only.
Added a variant of core_fload that loads to a dynamic_buffer.
Tweaked winwork.c a bit to not limit the maximum number of processors
unless the work queue was created with the WORK_QUEUE_FLAG_HIGH_FREQ
option. Further adjustments here are likely going to be necessary.
Fixed bug in aviio.c which caused errors when reading some AVI files.
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 |