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 "../common/platform.h"
13 #include <brotli/types.h>
14
15 #if defined(__cplusplus) || defined(c_plusplus)
16 extern "C" {
17 #endif
18
19 #define BROTLI_HUFFMAN_MAX_CODE_LENGTH 15
20
21 /* BROTLI_NUM_BLOCK_LEN_SYMBOLS == 26 */
22 #define BROTLI_HUFFMAN_MAX_SIZE_26 396
23 /* BROTLI_MAX_BLOCK_TYPE_SYMBOLS == 258 */
24 #define BROTLI_HUFFMAN_MAX_SIZE_258 632
25 /* BROTLI_MAX_CONTEXT_MAP_SYMBOLS == 272 */
26 #define BROTLI_HUFFMAN_MAX_SIZE_272 646
27
28 #define BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH 5
29
30 #if ((defined(BROTLI_TARGET_ARMV7) || defined(BROTLI_TARGET_ARMV8_32)) && \
31 BROTLI_GNUC_HAS_ATTRIBUTE(aligned, 2, 7, 0))
32 #define BROTLI_HUFFMAN_CODE_FAST_LOAD
33 #endif
34
35 #if !defined(BROTLI_HUFFMAN_CODE_FAST_LOAD)
36 /* Do not create this struct directly - use the ConstructHuffmanCode
37 * constructor below! */
38 typedef struct {
39 uint8_t bits; /* number of bits used for this symbol */
40 uint16_t value; /* symbol value or table offset */
41 } HuffmanCode;
42
ConstructHuffmanCode(const uint8_t bits,const uint16_t value)43 static BROTLI_INLINE HuffmanCode ConstructHuffmanCode(const uint8_t bits,
44 const uint16_t value) {
45 HuffmanCode h;
46 h.bits = bits;
47 h.value = value;
48 return h;
49 }
50
51 /* Please use the following macros to optimize HuffmanCode accesses in hot
52 * paths.
53 *
54 * For example, assuming |table| contains a HuffmanCode pointer:
55 *
56 * BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(table);
57 * BROTLI_HC_ADJUST_TABLE_INDEX(table, index_into_table);
58 * *bits = BROTLI_HC_GET_BITS(table);
59 * *value = BROTLI_HC_GET_VALUE(table);
60 * BROTLI_HC_ADJUST_TABLE_INDEX(table, offset);
61 * *bits2 = BROTLI_HC_GET_BITS(table);
62 * *value2 = BROTLI_HC_GET_VALUE(table);
63 *
64 */
65
66 #define BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(H)
67 #define BROTLI_HC_ADJUST_TABLE_INDEX(H, V) H += (V)
68
69 /* These must be given a HuffmanCode pointer! */
70 #define BROTLI_HC_FAST_LOAD_BITS(H) (H->bits)
71 #define BROTLI_HC_FAST_LOAD_VALUE(H) (H->value)
72
73 #else /* BROTLI_HUFFMAN_CODE_FAST_LOAD */
74
75 typedef BROTLI_ALIGNED(4) uint32_t HuffmanCode;
76
77 static BROTLI_INLINE HuffmanCode ConstructHuffmanCode(const uint8_t bits,
78 const uint16_t value) {
79 return (HuffmanCode) ((value & 0xFFFF) << 16) | (bits & 0xFF);
80 }
81
82 #define BROTLI_HC_MARK_TABLE_FOR_FAST_LOAD(H) uint32_t __fastload_##H = (*H)
83 #define BROTLI_HC_ADJUST_TABLE_INDEX(H, V) H += (V); __fastload_##H = (*H)
84
85 /* These must be given a HuffmanCode pointer! */
86 #define BROTLI_HC_FAST_LOAD_BITS(H) ((__fastload_##H) & 0xFF)
87 #define BROTLI_HC_FAST_LOAD_VALUE(H) ((__fastload_##H) >> 16)
88 #endif /* BROTLI_HUFFMAN_CODE_FAST_LOAD */
89
90 /* Builds Huffman lookup table assuming code lengths are in symbol order. */
91 BROTLI_INTERNAL void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* root_table,
92 const uint8_t* const code_lengths, uint16_t* count);
93
94 /* Builds Huffman lookup table assuming code lengths are in symbol order.
95 Returns size of resulting table. */
96 BROTLI_INTERNAL uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
97 int root_bits, const uint16_t* const symbol_lists, uint16_t* count);
98
99 /* Builds a simple Huffman table. The |num_symbols| parameter is to be
100 interpreted as follows: 0 means 1 symbol, 1 means 2 symbols,
101 2 means 3 symbols, 3 means 4 symbols with lengths [2, 2, 2, 2],
102 4 means 4 symbols with lengths [1, 2, 3, 3]. */
103 BROTLI_INTERNAL uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
104 int root_bits, uint16_t* symbols, uint32_t num_symbols);
105
106 /* Contains a collection of Huffman trees with the same alphabet size. */
107 /* alphabet_size_limit is needed due to simple codes, since
108 log2(alphabet_size_max) could be greater than log2(alphabet_size_limit). */
109 typedef struct {
110 HuffmanCode** htrees;
111 HuffmanCode* codes;
112 uint16_t alphabet_size_max;
113 uint16_t alphabet_size_limit;
114 uint16_t num_htrees;
115 } HuffmanTreeGroup;
116
117 #if defined(__cplusplus) || defined(c_plusplus)
118 } /* extern "C" */
119 #endif
120
121 #endif /* BROTLI_DEC_HUFFMAN_H_ */
122