deps/libchdr/huffman.h

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