deps/libretro-common/include/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  *  CONSTANTS
  20  ***************************************************************************
  21  */
  22
  23 enum huffman_error
  24 {
  25         HUFFERR_NONE = 0,
  26         HUFFERR_TOO_MANY_BITS,
  27         HUFFERR_INVALID_DATA,
  28         HUFFERR_INPUT_BUFFER_TOO_SMALL,
  29         HUFFERR_OUTPUT_BUFFER_TOO_SMALL,
  30         HUFFERR_INTERNAL_INCONSISTENCY,
  31         HUFFERR_TOO_MANY_CONTEXTS
  32 };
  33
  34 /***************************************************************************
  35  *  TYPE DEFINITIONS
  36  ***************************************************************************
  37  */
  38
  39 typedef uint16_t lookup_value;
  40
  41 /* a node in the huffman tree */
  42 struct node_t
  43 {
  44         struct node_t*          parent;         /* pointer to parent node */
  45         uint32_t                        count;          /* number of hits on this node */
  46         uint32_t                        weight;         /* assigned weight of this node */
  47         uint32_t                        bits;           /* bits used to encode the node */
  48         uint8_t                         numbits;        /* number of bits needed for this node */
  49 };
  50
  51 /* ======================> huffman_context_base */
  52
  53 /* context class for decoding */
  54 struct huffman_decoder
  55 {
  56         /* internal state */
  57         uint32_t                        numcodes;             /* number of total codes being processed */
  58         uint8_t                         maxbits;           /* maximum bits per code */
  59         uint8_t                         prevdata;             /* value of the previous data (for delta-RLE encoding) */
  60         int                     rleremaining;         /* number of RLE bytes remaining (for delta-RLE encoding) */
  61         lookup_value *          lookup;               /* pointer to the lookup table */
  62         struct node_t *     huffnode;             /* array of nodes */
  63         uint32_t *              datahisto;            /* histogram of data values */
  64
  65         /* array versions of the info we need */
  66 #if 0
  67         node_t*                 huffnode_array; /* [_NumCodes]; */
  68         lookup_value*   lookup_array; /* [1 << _MaxBits]; */
  69 #endif
  70 };
  71
  72 /* ======================> huffman_decoder */
  73
  74 struct huffman_decoder* create_huffman_decoder(int numcodes, int maxbits);
  75 void delete_huffman_decoder(struct huffman_decoder* decoder);
  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