• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
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 "../common/platform.h"
15 #include <brotli/types.h>
16 
17 #if defined(__cplusplus) || defined(c_plusplus)
18 extern "C" {
19 #endif
20 
21 #define BROTLI_REVERSE_BITS_MAX 8
22 
23 #if defined(BROTLI_RBIT)
24 #define BROTLI_REVERSE_BITS_BASE \
25   ((sizeof(brotli_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   ((brotli_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(brotli_reg_t num)70 static BROTLI_INLINE brotli_reg_t BrotliReverseBits(brotli_reg_t num) {
71 #if defined(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
91    next 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   brotli_reg_t key;       /* prefix code */
110   brotli_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 = ConstructHuffmanCode(0, (uint16_t)sorted[0]);
146     for (key = 0; key < (brotli_reg_t)table_size; ++key) {
147       table[key] = code;
148     }
149     return;
150   }
151 
152   /* Fill in table. */
153   key = 0;
154   key_step = BROTLI_REVERSE_BITS_LOWEST;
155   symbol = 0;
156   bits = 1;
157   step = 2;
158   do {
159     for (bits_count = count[bits]; bits_count != 0; --bits_count) {
160       code = ConstructHuffmanCode((uint8_t)bits, (uint16_t)sorted[symbol++]);
161       ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
162       key += key_step;
163     }
164     step <<= 1;
165     key_step >>= 1;
166   } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
167 }
168 
BrotliBuildHuffmanTable(HuffmanCode * root_table,int root_bits,const uint16_t * const symbol_lists,uint16_t * count)169 uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
170                                  int root_bits,
171                                  const uint16_t* const symbol_lists,
172                                  uint16_t* count) {
173   HuffmanCode code;       /* current table entry */
174   HuffmanCode* table;     /* next available space in table */
175   int len;                /* current code length */
176   int symbol;             /* symbol index in original or sorted table */
177   brotli_reg_t key;       /* prefix code */
178   brotli_reg_t key_step;  /* prefix code addend */
179   brotli_reg_t sub_key;   /* 2nd level table prefix code */
180   brotli_reg_t sub_key_step;  /* 2nd level table prefix code addend */
181   int step;               /* step size to replicate values in current table */
182   int table_bits;         /* key length of current table */
183   int table_size;         /* size of current table */
184   int total_size;         /* sum of root table size and 2nd level table sizes */
185   int max_length = -1;
186   int bits;
187   int bits_count;
188 
189   BROTLI_DCHECK(root_bits <= BROTLI_REVERSE_BITS_MAX);
190   BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH - root_bits <=
191                 BROTLI_REVERSE_BITS_MAX);
192 
193   while (symbol_lists[max_length] == 0xFFFF) max_length--;
194   max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1;
195 
196   table = root_table;
197   table_bits = root_bits;
198   table_size = 1 << table_bits;
199   total_size = table_size;
200 
201   /* Fill in the root table. Reduce the table size to if possible,
202      and create the repetitions by memcpy. */
203   if (table_bits > max_length) {
204     table_bits = max_length;
205     table_size = 1 << table_bits;
206   }
207   key = 0;
208   key_step = BROTLI_REVERSE_BITS_LOWEST;
209   bits = 1;
210   step = 2;
211   do {
212     symbol = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
213     for (bits_count = count[bits]; bits_count != 0; --bits_count) {
214       symbol = symbol_lists[symbol];
215       code = ConstructHuffmanCode((uint8_t)bits, (uint16_t)symbol);
216       ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
217       key += key_step;
218     }
219     step <<= 1;
220     key_step >>= 1;
221   } while (++bits <= table_bits);
222 
223   /* If root_bits != table_bits then replicate to fill the remaining slots. */
224   while (total_size != table_size) {
225     memcpy(&table[table_size], &table[0],
226            (size_t)table_size * sizeof(table[0]));
227     table_size <<= 1;
228   }
229 
230   /* Fill in 2nd level tables and add pointers to root table. */
231   key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1);
232   sub_key = (BROTLI_REVERSE_BITS_LOWEST << 1);
233   sub_key_step = BROTLI_REVERSE_BITS_LOWEST;
234   for (len = root_bits + 1, step = 2; len <= max_length; ++len) {
235     symbol = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
236     for (; count[len] != 0; --count[len]) {
237       if (sub_key == (BROTLI_REVERSE_BITS_LOWEST << 1U)) {
238         table += table_size;
239         table_bits = NextTableBitSize(count, len, root_bits);
240         table_size = 1 << table_bits;
241         total_size += table_size;
242         sub_key = BrotliReverseBits(key);
243         key += key_step;
244         root_table[sub_key] = ConstructHuffmanCode(
245             (uint8_t)(table_bits + root_bits),
246             (uint16_t)(((size_t)(table - root_table)) - sub_key));
247         sub_key = 0;
248       }
249       symbol = symbol_lists[symbol];
250       code = ConstructHuffmanCode((uint8_t)(len - root_bits), (uint16_t)symbol);
251       ReplicateValue(
252           &table[BrotliReverseBits(sub_key)], step, table_size, code);
253       sub_key += sub_key_step;
254     }
255     step <<= 1;
256     sub_key_step >>= 1;
257   }
258   return (uint32_t)total_size;
259 }
260 
BrotliBuildSimpleHuffmanTable(HuffmanCode * table,int root_bits,uint16_t * val,uint32_t num_symbols)261 uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
262                                        int root_bits,
263                                        uint16_t* val,
264                                        uint32_t num_symbols) {
265   uint32_t table_size = 1;
266   const uint32_t goal_size = 1U << root_bits;
267   switch (num_symbols) {
268     case 0:
269       table[0] = ConstructHuffmanCode(0, val[0]);
270       break;
271     case 1:
272       if (val[1] > val[0]) {
273         table[0] = ConstructHuffmanCode(1, val[0]);
274         table[1] = ConstructHuffmanCode(1, val[1]);
275       } else {
276         table[0] = ConstructHuffmanCode(1, val[1]);
277         table[1] = ConstructHuffmanCode(1, val[0]);
278       }
279       table_size = 2;
280       break;
281     case 2:
282       table[0] = ConstructHuffmanCode(1, val[0]);
283       table[2] = ConstructHuffmanCode(1, val[0]);
284       if (val[2] > val[1]) {
285         table[1] = ConstructHuffmanCode(2, val[1]);
286         table[3] = ConstructHuffmanCode(2, val[2]);
287       } else {
288         table[1] = ConstructHuffmanCode(2, val[2]);
289         table[3] = ConstructHuffmanCode(2, val[1]);
290       }
291       table_size = 4;
292       break;
293     case 3: {
294       int i, k;
295       for (i = 0; i < 3; ++i) {
296         for (k = i + 1; k < 4; ++k) {
297           if (val[k] < val[i]) {
298             uint16_t t = val[k];
299             val[k] = val[i];
300             val[i] = t;
301           }
302         }
303       }
304       table[0] = ConstructHuffmanCode(2, val[0]);
305       table[2] = ConstructHuffmanCode(2, val[1]);
306       table[1] = ConstructHuffmanCode(2, val[2]);
307       table[3] = ConstructHuffmanCode(2, val[3]);
308       table_size = 4;
309       break;
310     }
311     case 4: {
312       if (val[3] < val[2]) {
313         uint16_t t = val[3];
314         val[3] = val[2];
315         val[2] = t;
316       }
317       table[0] = ConstructHuffmanCode(1, val[0]);
318       table[1] = ConstructHuffmanCode(2, val[1]);
319       table[2] = ConstructHuffmanCode(1, val[0]);
320       table[3] = ConstructHuffmanCode(3, val[2]);
321       table[4] = ConstructHuffmanCode(1, val[0]);
322       table[5] = ConstructHuffmanCode(2, val[1]);
323       table[6] = ConstructHuffmanCode(1, val[0]);
324       table[7] = ConstructHuffmanCode(3, val[3]);
325       table_size = 8;
326       break;
327     }
328   }
329   while (table_size != goal_size) {
330     memcpy(&table[table_size], &table[0],
331            (size_t)table_size * sizeof(table[0]));
332     table_size <<= 1;
333   }
334   return goal_size;
335 }
336 
337 #if defined(__cplusplus) || defined(c_plusplus)
338 }  /* extern "C" */
339 #endif
340