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