deps/libchdr/huffman.h

   1 /* license:BSD-3-Clause
   2  * copyright-holders:Aaron Giles
   3  ***************************************************************************
   4
   5     huffman.h
   6
   7     Static Huffman compression and decompression helpers.
   8
   9 ***************************************************************************/
  10
  11 #pragma once
  12
  13 #ifndef __HUFFMAN_H__
  14 #define __HUFFMAN_H__
  15
  16 #include "bitstream.h"
  17
  18
  19 /***************************************************************************
  20  *  CONSTANTS
  21  ***************************************************************************
  22  */
  23
  24 enum huffman_error
  25 {
  26         HUFFERR_NONE = 0,
  27         HUFFERR_TOO_MANY_BITS,
  28         HUFFERR_INVALID_DATA,
  29         HUFFERR_INPUT_BUFFER_TOO_SMALL,
  30         HUFFERR_OUTPUT_BUFFER_TOO_SMALL,
  31         HUFFERR_INTERNAL_INCONSISTENCY,
  32         HUFFERR_TOO_MANY_CONTEXTS
  33 };
  34
  35 /***************************************************************************
  36  *  TYPE DEFINITIONS
  37  ***************************************************************************
  38  */
  39
  40 typedef uint16_t lookup_value;
  41
  42 /* a node in the huffman tree */
  43 struct node_t
  44 {
  45         struct node_t*          parent;         /* pointer to parent node */
  46         uint32_t                        count;          /* number of hits on this node */
  47         uint32_t                        weight;         /* assigned weight of this node */
  48         uint32_t                        bits;           /* bits used to encode the node */
  49         uint8_t                         numbits;        /* number of bits needed for this node */
  50 };
  51
  52 /* ======================> huffman_context_base */
  53
  54 /* context class for decoding */
  55 struct huffman_decoder
  56 {
  57         /* internal state */
  58         uint32_t                        numcodes;             /* number of total codes being processed */
  59         uint8_t                         maxbits;           /* maximum bits per code */
  60         uint8_t                         prevdata;             /* value of the previous data (for delta-RLE encoding) */
  61         int                     rleremaining;         /* number of RLE bytes remaining (for delta-RLE encoding) */
  62         lookup_value *          lookup;               /* pointer to the lookup table */
  63         struct node_t *     huffnode;             /* array of nodes */
  64         uint32_t *              datahisto;            /* histogram of data values */
  65
  66         /* array versions of the info we need */
  67 #if 0
  68         node_t*                 huffnode_array; /* [_NumCodes]; */
  69         lookup_value*   lookup_array; /* [1 << _MaxBits]; */
  70 #endif
  71 };
  72
  73 /* ======================> huffman_decoder */
  74
  75 struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits);
  76
  77 /* single item operations */
  78 uint32_t huffman_decode_one(struct huffman_decoder* decoder, struct bitstream* bitbuf);
  79
  80 enum huffman_error huffman_import_tree_rle(struct huffman_decoder* decoder, struct bitstream* bitbuf);
  81 enum huffman_error huffman_import_tree_huffman(struct huffman_decoder* decoder, struct bitstream* bitbuf);
  82
  83 int huffman_build_tree(struct huffman_decoder* decoder, uint32_t totaldata, uint32_t totalweight);
  84 enum huffman_error huffman_assign_canonical_codes(struct huffman_decoder* decoder);
  85 enum huffman_error huffman_compute_tree_from_histo(struct huffman_decoder* decoder);
  86
  87 void huffman_build_lookup_table(struct huffman_decoder* decoder);
  88
  89 #endif