1 /* Copyright 2013 Google Inc. All Rights Reserved.
3 Distributed under MIT license.
4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
7 /* Utilities for building Huffman decoding tables. */
11 //#include <string.h> /* memcpy, memset */
13 #include "../common/constants.h"
14 #include "../common/types.h"
17 #if defined(__cplusplus) || defined(c_plusplus)
21 #define BROTLI_REVERSE_BITS_MAX 8
24 #define BROTLI_REVERSE_BITS_BASE (32 - BROTLI_REVERSE_BITS_MAX)
26 #define BROTLI_REVERSE_BITS_BASE 0
27 static uint8_t kReverseBits
[1 << BROTLI_REVERSE_BITS_MAX
] = {
28 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
29 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
30 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
31 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
32 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,
33 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
34 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,
35 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
36 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,
37 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
38 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA,
39 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
40 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6,
41 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
42 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
43 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
44 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1,
45 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
46 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9,
47 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
48 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,
49 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
50 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED,
51 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
52 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3,
53 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
54 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
55 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
56 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,
57 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
58 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
59 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
61 #endif /* BROTLI_RBIT */
63 #define BROTLI_REVERSE_BITS_LOWEST \
64 (1U << (BROTLI_REVERSE_BITS_MAX - 1 + BROTLI_REVERSE_BITS_BASE))
66 /* Returns reverse(num >> BROTLI_REVERSE_BITS_BASE, BROTLI_REVERSE_BITS_MAX),
67 where reverse(value, len) is the bit-wise reversal of the len least
68 significant bits of value. */
69 static BROTLI_INLINE
uint32_t BrotliReverseBits(uint32_t num
) {
71 return BROTLI_RBIT(num
);
73 return kReverseBits
[num
];
77 /* Stores code in table[0], table[step], table[2*step], ..., table[end] */
78 /* Assumes that end is an integer multiple of step */
79 static BROTLI_INLINE
void ReplicateValue(HuffmanCode
* table
,
88 /* Returns the table width of the next 2nd level table. count is the histogram
89 of bit lengths for the remaining symbols, len is the code length of the next
91 static BROTLI_INLINE
int NextTableBitSize(const uint16_t* const count
,
92 int len
, int root_bits
) {
93 int left
= 1 << (len
- root_bits
);
94 while (len
< BROTLI_HUFFMAN_MAX_CODE_LENGTH
) {
100 return len
- root_bits
;
103 void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode
* table
,
104 const uint8_t* const code_lengths
,
106 HuffmanCode code
; /* current table entry */
107 int symbol
; /* symbol index in original or sorted table */
108 uint32_t key
; /* prefix code */
109 uint32_t key_step
; /* prefix code addend */
110 int step
; /* step size to replicate values in current table */
111 int table_size
; /* size of current table */
112 int sorted
[BROTLI_CODE_LENGTH_CODES
]; /* symbols sorted by code length */
113 /* offsets in sorted table for each length */
114 int offset
[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH
+ 1];
117 BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH
<=
118 BROTLI_REVERSE_BITS_MAX
);
120 /* generate offsets into sorted symbol table by code length */
123 BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH
, {
124 symbol
+= count
[bits
];
125 offset
[bits
] = symbol
;
128 /* Symbols with code length 0 are placed after all other symbols. */
129 offset
[0] = BROTLI_CODE_LENGTH_CODES
- 1;
131 /* sort symbols by length, by symbol order within each length */
132 symbol
= BROTLI_CODE_LENGTH_CODES
;
136 sorted
[offset
[code_lengths
[symbol
]]--] = symbol
;
138 } while (symbol
!= 0);
140 table_size
= 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH
;
142 /* Special case: all symbols but one have 0 code length. */
143 if (offset
[0] == 0) {
145 code
.value
= (uint16_t)sorted
[0];
146 for (key
= 0; key
< (uint32_t)table_size
; ++key
) {
154 key_step
= BROTLI_REVERSE_BITS_LOWEST
;
159 code
.bits
= (uint8_t)bits
;
160 for (bits_count
= count
[bits
]; bits_count
!= 0; --bits_count
) {
161 code
.value
= (uint16_t)sorted
[symbol
++];
162 ReplicateValue(&table
[BrotliReverseBits(key
)], step
, table_size
, code
);
167 } while (++bits
<= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH
);
170 uint32_t BrotliBuildHuffmanTable(HuffmanCode
* root_table
,
172 const uint16_t* const symbol_lists
,
174 HuffmanCode code
; /* current table entry */
175 HuffmanCode
* table
; /* next available space in table */
176 int len
; /* current code length */
177 int symbol
; /* symbol index in original or sorted table */
178 uint32_t key
; /* prefix code */
179 uint32_t key_step
; /* prefix code addend */
180 uint32_t sub_key
; /* 2nd level table prefix code */
181 uint32_t sub_key_step
; /* 2nd level table prefix code addend */
182 int step
; /* step size to replicate values in current table */
183 int table_bits
; /* key length of current table */
184 int table_size
; /* size of current table */
185 int total_size
; /* sum of root table size and 2nd level table sizes */
190 BROTLI_DCHECK(root_bits
<= BROTLI_REVERSE_BITS_MAX
);
191 BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH
- root_bits
<=
192 BROTLI_REVERSE_BITS_MAX
);
194 while (symbol_lists
[max_length
] == 0xFFFF) max_length
--;
195 max_length
+= BROTLI_HUFFMAN_MAX_CODE_LENGTH
+ 1;
198 table_bits
= root_bits
;
199 table_size
= 1 << table_bits
;
200 total_size
= table_size
;
202 /* fill in root table */
203 /* let's reduce the table size to a smaller size if possible, and */
204 /* create the repetitions by memcpy if possible in the coming loop */
205 if (table_bits
> max_length
) {
206 table_bits
= max_length
;
207 table_size
= 1 << table_bits
;
210 key_step
= BROTLI_REVERSE_BITS_LOWEST
;
214 code
.bits
= (uint8_t)bits
;
215 symbol
= bits
- (BROTLI_HUFFMAN_MAX_CODE_LENGTH
+ 1);
216 for (bits_count
= count
[bits
]; bits_count
!= 0; --bits_count
) {
217 symbol
= symbol_lists
[symbol
];
218 code
.value
= (uint16_t)symbol
;
219 ReplicateValue(&table
[BrotliReverseBits(key
)], step
, table_size
, code
);
224 } while (++bits
<= table_bits
);
226 /* if root_bits != table_bits we only created one fraction of the */
227 /* table, and we need to replicate it now. */
228 while (total_size
!= table_size
) {
229 memcpy(&table
[table_size
], &table
[0],
230 (size_t)table_size
* sizeof(table
[0]));
234 /* fill in 2nd level tables and add pointers to root table */
235 key_step
= BROTLI_REVERSE_BITS_LOWEST
>> (root_bits
- 1);
236 sub_key
= (BROTLI_REVERSE_BITS_LOWEST
<< 1);
237 sub_key_step
= BROTLI_REVERSE_BITS_LOWEST
;
238 for (len
= root_bits
+ 1, step
= 2; len
<= max_length
; ++len
) {
239 symbol
= len
- (BROTLI_HUFFMAN_MAX_CODE_LENGTH
+ 1);
240 for (; count
[len
] != 0; --count
[len
]) {
241 if (sub_key
== (BROTLI_REVERSE_BITS_LOWEST
<< 1U)) {
243 table_bits
= NextTableBitSize(count
, len
, root_bits
);
244 table_size
= 1 << table_bits
;
245 total_size
+= table_size
;
246 sub_key
= BrotliReverseBits(key
);
248 root_table
[sub_key
].bits
= (uint8_t)(table_bits
+ root_bits
);
249 root_table
[sub_key
].value
=
250 (uint16_t)(((size_t)(table
- root_table
)) - sub_key
);
253 code
.bits
= (uint8_t)(len
- root_bits
);
254 symbol
= symbol_lists
[symbol
];
255 code
.value
= (uint16_t)symbol
;
257 &table
[BrotliReverseBits(sub_key
)], step
, table_size
, code
);
258 sub_key
+= sub_key_step
;
263 return (uint32_t)total_size
;
266 uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode
* table
,
269 uint32_t num_symbols
) {
270 uint32_t table_size
= 1;
271 const uint32_t goal_size
= 1U << root_bits
;
272 switch (num_symbols
) {
275 table
[0].value
= val
[0];
280 if (val
[1] > val
[0]) {
281 table
[0].value
= val
[0];
282 table
[1].value
= val
[1];
284 table
[0].value
= val
[1];
285 table
[1].value
= val
[0];
291 table
[0].value
= val
[0];
293 table
[2].value
= val
[0];
294 if (val
[2] > val
[1]) {
295 table
[1].value
= val
[1];
296 table
[3].value
= val
[2];
298 table
[1].value
= val
[2];
299 table
[3].value
= val
[1];
307 for (i
= 0; i
< 3; ++i
) {
308 for (k
= i
+ 1; k
< 4; ++k
) {
309 if (val
[k
] < val
[i
]) {
316 for (i
= 0; i
< 4; ++i
) {
319 table
[0].value
= val
[0];
320 table
[2].value
= val
[1];
321 table
[1].value
= val
[2];
322 table
[3].value
= val
[3];
328 if (val
[3] < val
[2]) {
333 for (i
= 0; i
< 7; ++i
) {
334 table
[i
].value
= val
[0];
335 table
[i
].bits
= (uint8_t)(1 + (i
& 1));
337 table
[1].value
= val
[1];
338 table
[3].value
= val
[2];
339 table
[5].value
= val
[1];
340 table
[7].value
= val
[3];
347 while (table_size
!= goal_size
) {
348 memcpy(&table
[table_size
], &table
[0],
349 (size_t)table_size
* sizeof(table
[0]));
355 #if defined(__cplusplus) || defined(c_plusplus)