dec/huffman.h

   1 /* Copyright 2013 Google Inc. All Rights Reserved.
   2
   3    Distributed under MIT license.
   4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
   5 */
   6
   7 /* Utilities for building Huffman decoding tables. */
   8
   9 #ifndef BROTLI_DEC_HUFFMAN_H_
  10 #define BROTLI_DEC_HUFFMAN_H_
  11
  12 #include "./types.h"
  13
  14 #if defined(__cplusplus) || defined(c_plusplus)
  15 extern "C" {
  16 #endif
  17
  18 #define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15
  19
  20 /* For current format this constant equals to kNumInsertAndCopyCodes */
  21 #define BROTLI_HUFFMAN_MAX_CODE_LENGTHS_SIZE 704
  22
  23 /* Maximum possible Huffman table size for an alphabet size of 704, max code
  24  * length 15 and root table bits 8. */
  25 #define BROTLI_HUFFMAN_MAX_TABLE_SIZE 1080
  26
  27 #define BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH 5
  28
  29 typedef struct {
  30   uint8_t bits;     /* number of bits used for this symbol */
  31   uint16_t value;   /* symbol value or table offset */
  32 } HuffmanCode;
  33
  34
  35 /* Builds Huffman lookup table assuming code lengths are in symbol order. */
  36 void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table,
  37                                         const uint8_t* const code_lengths,
  38                                         uint16_t *count);
  39
  40 /* Builds Huffman lookup table assuming code lengths are in symbol order. */
  41 /* Returns size of resulting table. */
  42 uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
  43                                  int root_bits,
  44                                  const uint16_t* const symbol_lists,
  45                                  uint16_t *count_arg);
  46
  47 /* Builds a simple Huffman table. The num_symbols parameter is to be */
  48 /* interpreted as follows: 0 means 1 symbol, 1 means 2 symbols, 2 means 3 */
  49 /* symbols, 3 means 4 symbols with lengths 2,2,2,2, 4 means 4 symbols with */
  50 /* lengths 1,2,3,3. */
  51 uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
  52                                        int root_bits,
  53                                        uint16_t *symbols,
  54                                        uint32_t num_symbols);
  55
  56 /* Contains a collection of Huffman trees with the same alphabet size. */
  57 typedef struct {
  58   HuffmanCode** htrees;
  59   HuffmanCode* codes;
  60   uint16_t alphabet_size;
  61   uint16_t num_htrees;
  62 } HuffmanTreeGroup;
  63
  64 #if defined(__cplusplus) || defined(c_plusplus)
  65 }    /* extern "C" */
  66 #endif
  67
  68 #endif  /* BROTLI_DEC_HUFFMAN_H_ */