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 #include "./huffman.h"
10
11 #include <string.h> /* memcpy, memset */
12
13 #include "../common/constants.h"
14 #include <brotli/types.h>
15 #include "./port.h"
16
17 #if defined(__cplusplus) || defined(c_plusplus)
18 extern "C" {
19 #endif
20
21 #define BROTLI_REVERSE_BITS_MAX 8
22
23 #ifdef BROTLI_RBIT
24 #define BROTLI_REVERSE_BITS_BASE \
25 ((sizeof(reg_t) << 3) - BROTLI_REVERSE_BITS_MAX)
26 #else
27 #define BROTLI_REVERSE_BITS_BASE 0
28 static uint8_t kReverseBits[1 << BROTLI_REVERSE_BITS_MAX] = {
29 0x00, 0x80, 0x40, 0xC0, 0x20, 0xA0, 0x60, 0xE0,
30 0x10, 0x90, 0x50, 0xD0, 0x30, 0xB0, 0x70, 0xF0,
31 0x08, 0x88, 0x48, 0xC8, 0x28, 0xA8, 0x68, 0xE8,
32 0x18, 0x98, 0x58, 0xD8, 0x38, 0xB8, 0x78, 0xF8,
33 0x04, 0x84, 0x44, 0xC4, 0x24, 0xA4, 0x64, 0xE4,
34 0x14, 0x94, 0x54, 0xD4, 0x34, 0xB4, 0x74, 0xF4,
35 0x0C, 0x8C, 0x4C, 0xCC, 0x2C, 0xAC, 0x6C, 0xEC,
36 0x1C, 0x9C, 0x5C, 0xDC, 0x3C, 0xBC, 0x7C, 0xFC,
37 0x02, 0x82, 0x42, 0xC2, 0x22, 0xA2, 0x62, 0xE2,
38 0x12, 0x92, 0x52, 0xD2, 0x32, 0xB2, 0x72, 0xF2,
39 0x0A, 0x8A, 0x4A, 0xCA, 0x2A, 0xAA, 0x6A, 0xEA,
40 0x1A, 0x9A, 0x5A, 0xDA, 0x3A, 0xBA, 0x7A, 0xFA,
41 0x06, 0x86, 0x46, 0xC6, 0x26, 0xA6, 0x66, 0xE6,
42 0x16, 0x96, 0x56, 0xD6, 0x36, 0xB6, 0x76, 0xF6,
43 0x0E, 0x8E, 0x4E, 0xCE, 0x2E, 0xAE, 0x6E, 0xEE,
44 0x1E, 0x9E, 0x5E, 0xDE, 0x3E, 0xBE, 0x7E, 0xFE,
45 0x01, 0x81, 0x41, 0xC1, 0x21, 0xA1, 0x61, 0xE1,
46 0x11, 0x91, 0x51, 0xD1, 0x31, 0xB1, 0x71, 0xF1,
47 0x09, 0x89, 0x49, 0xC9, 0x29, 0xA9, 0x69, 0xE9,
48 0x19, 0x99, 0x59, 0xD9, 0x39, 0xB9, 0x79, 0xF9,
49 0x05, 0x85, 0x45, 0xC5, 0x25, 0xA5, 0x65, 0xE5,
50 0x15, 0x95, 0x55, 0xD5, 0x35, 0xB5, 0x75, 0xF5,
51 0x0D, 0x8D, 0x4D, 0xCD, 0x2D, 0xAD, 0x6D, 0xED,
52 0x1D, 0x9D, 0x5D, 0xDD, 0x3D, 0xBD, 0x7D, 0xFD,
53 0x03, 0x83, 0x43, 0xC3, 0x23, 0xA3, 0x63, 0xE3,
54 0x13, 0x93, 0x53, 0xD3, 0x33, 0xB3, 0x73, 0xF3,
55 0x0B, 0x8B, 0x4B, 0xCB, 0x2B, 0xAB, 0x6B, 0xEB,
56 0x1B, 0x9B, 0x5B, 0xDB, 0x3B, 0xBB, 0x7B, 0xFB,
57 0x07, 0x87, 0x47, 0xC7, 0x27, 0xA7, 0x67, 0xE7,
58 0x17, 0x97, 0x57, 0xD7, 0x37, 0xB7, 0x77, 0xF7,
59 0x0F, 0x8F, 0x4F, 0xCF, 0x2F, 0xAF, 0x6F, 0xEF,
60 0x1F, 0x9F, 0x5F, 0xDF, 0x3F, 0xBF, 0x7F, 0xFF
61 };
62 #endif /* BROTLI_RBIT */
63
64 #define BROTLI_REVERSE_BITS_LOWEST \
65 ((reg_t)1 << (BROTLI_REVERSE_BITS_MAX - 1 + BROTLI_REVERSE_BITS_BASE))
66
67 /* Returns reverse(num >> BROTLI_REVERSE_BITS_BASE, BROTLI_REVERSE_BITS_MAX),
68 where reverse(value, len) is the bit-wise reversal of the len least
69 significant bits of value. */
BrotliReverseBits(reg_t num)70 static BROTLI_INLINE reg_t BrotliReverseBits(reg_t num) {
71 #ifdef BROTLI_RBIT
72 return BROTLI_RBIT(num);
73 #else
74 return kReverseBits[num];
75 #endif
76 }
77
78 /* Stores code in table[0], table[step], table[2*step], ..., table[end] */
79 /* Assumes that end is an integer multiple of step */
ReplicateValue(HuffmanCode * table,int step,int end,HuffmanCode code)80 static BROTLI_INLINE void ReplicateValue(HuffmanCode* table,
81 int step, int end,
82 HuffmanCode code) {
83 do {
84 end -= step;
85 table[end] = code;
86 } while (end > 0);
87 }
88
89 /* Returns the table width of the next 2nd level table. count is the histogram
90 of bit lengths for the remaining symbols, len is the code length of the next
91 processed symbol */
NextTableBitSize(const uint16_t * const count,int len,int root_bits)92 static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count,
93 int len, int root_bits) {
94 int left = 1 << (len - root_bits);
95 while (len < BROTLI_HUFFMAN_MAX_CODE_LENGTH) {
96 left -= count[len];
97 if (left <= 0) break;
98 ++len;
99 left <<= 1;
100 }
101 return len - root_bits;
102 }
103
BrotliBuildCodeLengthsHuffmanTable(HuffmanCode * table,const uint8_t * const code_lengths,uint16_t * count)104 void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table,
105 const uint8_t* const code_lengths,
106 uint16_t* count) {
107 HuffmanCode code; /* current table entry */
108 int symbol; /* symbol index in original or sorted table */
109 reg_t key; /* prefix code */
110 reg_t key_step; /* prefix code addend */
111 int step; /* step size to replicate values in current table */
112 int table_size; /* size of current table */
113 int sorted[BROTLI_CODE_LENGTH_CODES]; /* symbols sorted by code length */
114 /* offsets in sorted table for each length */
115 int offset[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1];
116 int bits;
117 int bits_count;
118 BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <=
119 BROTLI_REVERSE_BITS_MAX);
120
121 /* generate offsets into sorted symbol table by code length */
122 symbol = -1;
123 bits = 1;
124 BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH, {
125 symbol += count[bits];
126 offset[bits] = symbol;
127 bits++;
128 });
129 /* Symbols with code length 0 are placed after all other symbols. */
130 offset[0] = BROTLI_CODE_LENGTH_CODES - 1;
131
132 /* sort symbols by length, by symbol order within each length */
133 symbol = BROTLI_CODE_LENGTH_CODES;
134 do {
135 BROTLI_REPEAT(6, {
136 symbol--;
137 sorted[offset[code_lengths[symbol]]--] = symbol;
138 });
139 } while (symbol != 0);
140
141 table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
142
143 /* Special case: all symbols but one have 0 code length. */
144 if (offset[0] == 0) {
145 code.bits = 0;
146 code.value = (uint16_t)sorted[0];
147 for (key = 0; key < (reg_t)table_size; ++key) {
148 table[key] = code;
149 }
150 return;
151 }
152
153 /* fill in table */
154 key = 0;
155 key_step = BROTLI_REVERSE_BITS_LOWEST;
156 symbol = 0;
157 bits = 1;
158 step = 2;
159 do {
160 code.bits = (uint8_t)bits;
161 for (bits_count = count[bits]; bits_count != 0; --bits_count) {
162 code.value = (uint16_t)sorted[symbol++];
163 ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
164 key += key_step;
165 }
166 step <<= 1;
167 key_step >>= 1;
168 } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
169 }
170
BrotliBuildHuffmanTable(HuffmanCode * root_table,int root_bits,const uint16_t * const symbol_lists,uint16_t * count)171 uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
172 int root_bits,
173 const uint16_t* const symbol_lists,
174 uint16_t* count) {
175 HuffmanCode code; /* current table entry */
176 HuffmanCode* table; /* next available space in table */
177 int len; /* current code length */
178 int symbol; /* symbol index in original or sorted table */
179 reg_t key; /* prefix code */
180 reg_t key_step; /* prefix code addend */
181 reg_t sub_key; /* 2nd level table prefix code */
182 reg_t sub_key_step; /* 2nd level table prefix code addend */
183 int step; /* step size to replicate values in current table */
184 int table_bits; /* key length of current table */
185 int table_size; /* size of current table */
186 int total_size; /* sum of root table size and 2nd level table sizes */
187 int max_length = -1;
188 int bits;
189 int bits_count;
190
191 BROTLI_DCHECK(root_bits <= BROTLI_REVERSE_BITS_MAX);
192 BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH - root_bits <=
193 BROTLI_REVERSE_BITS_MAX);
194
195 while (symbol_lists[max_length] == 0xFFFF) max_length--;
196 max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1;
197
198 table = root_table;
199 table_bits = root_bits;
200 table_size = 1 << table_bits;
201 total_size = table_size;
202
203 /* fill in root table */
204 /* let's reduce the table size to a smaller size if possible, and */
205 /* create the repetitions by memcpy if possible in the coming loop */
206 if (table_bits > max_length) {
207 table_bits = max_length;
208 table_size = 1 << table_bits;
209 }
210 key = 0;
211 key_step = BROTLI_REVERSE_BITS_LOWEST;
212 bits = 1;
213 step = 2;
214 do {
215 code.bits = (uint8_t)bits;
216 symbol = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
217 for (bits_count = count[bits]; bits_count != 0; --bits_count) {
218 symbol = symbol_lists[symbol];
219 code.value = (uint16_t)symbol;
220 ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
221 key += key_step;
222 }
223 step <<= 1;
224 key_step >>= 1;
225 } while (++bits <= table_bits);
226
227 /* if root_bits != table_bits we only created one fraction of the */
228 /* table, and we need to replicate it now. */
229 while (total_size != table_size) {
230 memcpy(&table[table_size], &table[0],
231 (size_t)table_size * sizeof(table[0]));
232 table_size <<= 1;
233 }
234
235 /* fill in 2nd level tables and add pointers to root table */
236 key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1);
237 sub_key = (BROTLI_REVERSE_BITS_LOWEST << 1);
238 sub_key_step = BROTLI_REVERSE_BITS_LOWEST;
239 for (len = root_bits + 1, step = 2; len <= max_length; ++len) {
240 symbol = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
241 for (; count[len] != 0; --count[len]) {
242 if (sub_key == (BROTLI_REVERSE_BITS_LOWEST << 1U)) {
243 table += table_size;
244 table_bits = NextTableBitSize(count, len, root_bits);
245 table_size = 1 << table_bits;
246 total_size += table_size;
247 sub_key = BrotliReverseBits(key);
248 key += key_step;
249 root_table[sub_key].bits = (uint8_t)(table_bits + root_bits);
250 root_table[sub_key].value =
251 (uint16_t)(((size_t)(table - root_table)) - sub_key);
252 sub_key = 0;
253 }
254 code.bits = (uint8_t)(len - root_bits);
255 symbol = symbol_lists[symbol];
256 code.value = (uint16_t)symbol;
257 ReplicateValue(
258 &table[BrotliReverseBits(sub_key)], step, table_size, code);
259 sub_key += sub_key_step;
260 }
261 step <<= 1;
262 sub_key_step >>= 1;
263 }
264 return (uint32_t)total_size;
265 }
266
BrotliBuildSimpleHuffmanTable(HuffmanCode * table,int root_bits,uint16_t * val,uint32_t num_symbols)267 uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
268 int root_bits,
269 uint16_t* val,
270 uint32_t num_symbols) {
271 uint32_t table_size = 1;
272 const uint32_t goal_size = 1U << root_bits;
273 switch (num_symbols) {
274 case 0:
275 table[0].bits = 0;
276 table[0].value = val[0];
277 break;
278 case 1:
279 table[0].bits = 1;
280 table[1].bits = 1;
281 if (val[1] > val[0]) {
282 table[0].value = val[0];
283 table[1].value = val[1];
284 } else {
285 table[0].value = val[1];
286 table[1].value = val[0];
287 }
288 table_size = 2;
289 break;
290 case 2:
291 table[0].bits = 1;
292 table[0].value = val[0];
293 table[2].bits = 1;
294 table[2].value = val[0];
295 if (val[2] > val[1]) {
296 table[1].value = val[1];
297 table[3].value = val[2];
298 } else {
299 table[1].value = val[2];
300 table[3].value = val[1];
301 }
302 table[1].bits = 2;
303 table[3].bits = 2;
304 table_size = 4;
305 break;
306 case 3: {
307 int i, k;
308 for (i = 0; i < 3; ++i) {
309 for (k = i + 1; k < 4; ++k) {
310 if (val[k] < val[i]) {
311 uint16_t t = val[k];
312 val[k] = val[i];
313 val[i] = t;
314 }
315 }
316 }
317 for (i = 0; i < 4; ++i) {
318 table[i].bits = 2;
319 }
320 table[0].value = val[0];
321 table[2].value = val[1];
322 table[1].value = val[2];
323 table[3].value = val[3];
324 table_size = 4;
325 break;
326 }
327 case 4: {
328 int i;
329 if (val[3] < val[2]) {
330 uint16_t t = val[3];
331 val[3] = val[2];
332 val[2] = t;
333 }
334 for (i = 0; i < 7; ++i) {
335 table[i].value = val[0];
336 table[i].bits = (uint8_t)(1 + (i & 1));
337 }
338 table[1].value = val[1];
339 table[3].value = val[2];
340 table[5].value = val[1];
341 table[7].value = val[3];
342 table[3].bits = 3;
343 table[7].bits = 3;
344 table_size = 8;
345 break;
346 }
347 }
348 while (table_size != goal_size) {
349 memcpy(&table[table_size], &table[0],
350 (size_t)table_size * sizeof(table[0]));
351 table_size <<= 1;
352 }
353 return goal_size;
354 }
355
356 #if defined(__cplusplus) || defined(c_plusplus)
357 } /* extern "C" */
358 #endif
359