]>
Commit | Line | Data |
---|---|---|
f9995f31 MG |
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_ */ |