MdeModulePkg: Add Brotli algorithm decompression library
[mirror_edk2.git] / MdeModulePkg / Library / BrotliCustomDecompressLib / dec / huffman.c
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/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 (32 - BROTLI_REVERSE_BITS_MAX)
25 #else
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
60 };
61 #endif /* BROTLI_RBIT */
62
63 #define BROTLI_REVERSE_BITS_LOWEST \
64 (1U << (BROTLI_REVERSE_BITS_MAX - 1 + BROTLI_REVERSE_BITS_BASE))
65
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) {
70 #ifdef BROTLI_RBIT
71 return BROTLI_RBIT(num);
72 #else
73 return kReverseBits[num];
74 #endif
75 }
76
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,
80 int step, int end,
81 HuffmanCode code) {
82 do {
83 end -= step;
84 table[end] = code;
85 } while (end > 0);
86 }
87
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
90 processed symbol */
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) {
95 left -= count[len];
96 if (left <= 0) break;
97 ++len;
98 left <<= 1;
99 }
100 return len - root_bits;
101 }
102
103 void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table,
104 const uint8_t* const code_lengths,
105 uint16_t* count) {
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];
115 int bits;
116 int bits_count;
117 BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <=
118 BROTLI_REVERSE_BITS_MAX);
119
120 /* generate offsets into sorted symbol table by code length */
121 symbol = -1;
122 bits = 1;
123 BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH, {
124 symbol += count[bits];
125 offset[bits] = symbol;
126 bits++;
127 });
128 /* Symbols with code length 0 are placed after all other symbols. */
129 offset[0] = BROTLI_CODE_LENGTH_CODES - 1;
130
131 /* sort symbols by length, by symbol order within each length */
132 symbol = BROTLI_CODE_LENGTH_CODES;
133 do {
134 BROTLI_REPEAT(6, {
135 symbol--;
136 sorted[offset[code_lengths[symbol]]--] = symbol;
137 });
138 } while (symbol != 0);
139
140 table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
141
142 /* Special case: all symbols but one have 0 code length. */
143 if (offset[0] == 0) {
144 code.bits = 0;
145 code.value = (uint16_t)sorted[0];
146 for (key = 0; key < (uint32_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 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);
163 key += key_step;
164 }
165 step <<= 1;
166 key_step >>= 1;
167 } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
168 }
169
170 uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
171 int root_bits,
172 const uint16_t* const symbol_lists,
173 uint16_t* count) {
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 */
186 int max_length = -1;
187 int bits;
188 int bits_count;
189
190 BROTLI_DCHECK(root_bits <= BROTLI_REVERSE_BITS_MAX);
191 BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH - root_bits <=
192 BROTLI_REVERSE_BITS_MAX);
193
194 while (symbol_lists[max_length] == 0xFFFF) max_length--;
195 max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1;
196
197 table = root_table;
198 table_bits = root_bits;
199 table_size = 1 << table_bits;
200 total_size = table_size;
201
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;
208 }
209 key = 0;
210 key_step = BROTLI_REVERSE_BITS_LOWEST;
211 bits = 1;
212 step = 2;
213 do {
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);
220 key += key_step;
221 }
222 step <<= 1;
223 key_step >>= 1;
224 } while (++bits <= table_bits);
225
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]));
231 table_size <<= 1;
232 }
233
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)) {
242 table += table_size;
243 table_bits = NextTableBitSize(count, len, root_bits);
244 table_size = 1 << table_bits;
245 total_size += table_size;
246 sub_key = BrotliReverseBits(key);
247 key += key_step;
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);
251 sub_key = 0;
252 }
253 code.bits = (uint8_t)(len - root_bits);
254 symbol = symbol_lists[symbol];
255 code.value = (uint16_t)symbol;
256 ReplicateValue(
257 &table[BrotliReverseBits(sub_key)], step, table_size, code);
258 sub_key += sub_key_step;
259 }
260 step <<= 1;
261 sub_key_step >>= 1;
262 }
263 return (uint32_t)total_size;
264 }
265
266 uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
267 int root_bits,
268 uint16_t* val,
269 uint32_t num_symbols) {
270 uint32_t table_size = 1;
271 const uint32_t goal_size = 1U << root_bits;
272 switch (num_symbols) {
273 case 0:
274 table[0].bits = 0;
275 table[0].value = val[0];
276 break;
277 case 1:
278 table[0].bits = 1;
279 table[1].bits = 1;
280 if (val[1] > val[0]) {
281 table[0].value = val[0];
282 table[1].value = val[1];
283 } else {
284 table[0].value = val[1];
285 table[1].value = val[0];
286 }
287 table_size = 2;
288 break;
289 case 2:
290 table[0].bits = 1;
291 table[0].value = val[0];
292 table[2].bits = 1;
293 table[2].value = val[0];
294 if (val[2] > val[1]) {
295 table[1].value = val[1];
296 table[3].value = val[2];
297 } else {
298 table[1].value = val[2];
299 table[3].value = val[1];
300 }
301 table[1].bits = 2;
302 table[3].bits = 2;
303 table_size = 4;
304 break;
305 case 3: {
306 int i, k;
307 for (i = 0; i < 3; ++i) {
308 for (k = i + 1; k < 4; ++k) {
309 if (val[k] < val[i]) {
310 uint16_t t = val[k];
311 val[k] = val[i];
312 val[i] = t;
313 }
314 }
315 }
316 for (i = 0; i < 4; ++i) {
317 table[i].bits = 2;
318 }
319 table[0].value = val[0];
320 table[2].value = val[1];
321 table[1].value = val[2];
322 table[3].value = val[3];
323 table_size = 4;
324 break;
325 }
326 case 4: {
327 int i;
328 if (val[3] < val[2]) {
329 uint16_t t = val[3];
330 val[3] = val[2];
331 val[2] = t;
332 }
333 for (i = 0; i < 7; ++i) {
334 table[i].value = val[0];
335 table[i].bits = (uint8_t)(1 + (i & 1));
336 }
337 table[1].value = val[1];
338 table[3].value = val[2];
339 table[5].value = val[1];
340 table[7].value = val[3];
341 table[3].bits = 3;
342 table[7].bits = 3;
343 table_size = 8;
344 break;
345 }
346 }
347 while (table_size != goal_size) {
348 memcpy(&table[table_size], &table[0],
349 (size_t)table_size * sizeof(table[0]));
350 table_size <<= 1;
351 }
352 return goal_size;
353 }
354
355 #if defined(__cplusplus) || defined(c_plusplus)
356 } /* extern "C" */
357 #endif