Coverage Report

Created: 2023-09-25 06:02

/src/woff2/brotli/c/dec/huffman.c
Line
Count
Source (jump to first uncovered line)
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
1.70M
#define BROTLI_REVERSE_BITS_MAX 8
22
23
#ifdef BROTLI_RBIT
24
#define BROTLI_REVERSE_BITS_BASE \
25
  ((sizeof(brotli_reg_t) << 3) - BROTLI_REVERSE_BITS_MAX)
26
#else
27
1.70M
#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
1.70M
  ((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. */
70
4.19M
static BROTLI_INLINE brotli_reg_t BrotliReverseBits(brotli_reg_t num) {
71
#ifdef BROTLI_RBIT
72
  return BROTLI_RBIT(num);
73
#else
74
4.19M
  return kReverseBits[num];
75
4.19M
#endif
76
4.19M
}
77
78
/* Stores code in table[0], table[step], table[2*step], ..., table[end] */
79
/* Assumes that end is an integer multiple of step */
80
static BROTLI_INLINE void ReplicateValue(HuffmanCode* table,
81
                                         int step, int end,
82
3.71M
                                         HuffmanCode code) {
83
9.11M
  do {
84
9.11M
    end -= step;
85
9.11M
    table[end] = code;
86
9.11M
  } while (end > 0);
87
3.71M
}
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. */
92
static BROTLI_INLINE int NextTableBitSize(const uint16_t* const count,
93
475k
                                          int len, int root_bits) {
94
475k
  int left = 1 << (len - root_bits);
95
491k
  while (len < BROTLI_HUFFMAN_MAX_CODE_LENGTH) {
96
491k
    left -= count[len];
97
491k
    if (left <= 0) break;
98
16.3k
    ++len;
99
16.3k
    left <<= 1;
100
16.3k
  }
101
475k
  return len - root_bits;
102
475k
}
103
104
void BrotliBuildCodeLengthsHuffmanTable(HuffmanCode* table,
105
                                        const uint8_t* const code_lengths,
106
44.0k
                                        uint16_t* count) {
107
44.0k
  HuffmanCode code;       /* current table entry */
108
44.0k
  int symbol;             /* symbol index in original or sorted table */
109
44.0k
  brotli_reg_t key;       /* prefix code */
110
44.0k
  brotli_reg_t key_step;  /* prefix code addend */
111
44.0k
  int step;               /* step size to replicate values in current table */
112
44.0k
  int table_size;         /* size of current table */
113
44.0k
  int sorted[BROTLI_CODE_LENGTH_CODES];  /* symbols sorted by code length */
114
  /* offsets in sorted table for each length */
115
44.0k
  int offset[BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH + 1];
116
44.0k
  int bits;
117
44.0k
  int bits_count;
118
44.0k
  BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH <=
119
44.0k
                BROTLI_REVERSE_BITS_MAX);
120
121
  /* Generate offsets into sorted symbol table by code length. */
122
44.0k
  symbol = -1;
123
44.0k
  bits = 1;
124
44.0k
  BROTLI_REPEAT(BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH, {
125
44.0k
    symbol += count[bits];
126
44.0k
    offset[bits] = symbol;
127
44.0k
    bits++;
128
44.0k
  });
129
  /* Symbols with code length 0 are placed after all other symbols. */
130
44.0k
  offset[0] = BROTLI_CODE_LENGTH_CODES - 1;
131
132
  /* Sort symbols by length, by symbol order within each length. */
133
44.0k
  symbol = BROTLI_CODE_LENGTH_CODES;
134
132k
  do {
135
132k
    BROTLI_REPEAT(6, {
136
132k
      symbol--;
137
132k
      sorted[offset[code_lengths[symbol]]--] = symbol;
138
132k
    });
139
132k
  } while (symbol != 0);
140
141
44.0k
  table_size = 1 << BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH;
142
143
  /* Special case: all symbols but one have 0 code length. */
144
44.0k
  if (offset[0] == 0) {
145
777
    code.bits = 0;
146
777
    code.value = (uint16_t)sorted[0];
147
25.6k
    for (key = 0; key < (brotli_reg_t)table_size; ++key) {
148
24.8k
      table[key] = code;
149
24.8k
    }
150
777
    return;
151
777
  }
152
153
  /* Fill in table. */
154
43.2k
  key = 0;
155
43.2k
  key_step = BROTLI_REVERSE_BITS_LOWEST;
156
43.2k
  symbol = 0;
157
43.2k
  bits = 1;
158
43.2k
  step = 2;
159
216k
  do {
160
216k
    code.bits = (uint8_t)bits;
161
527k
    for (bits_count = count[bits]; bits_count != 0; --bits_count) {
162
311k
      code.value = (uint16_t)sorted[symbol++];
163
311k
      ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
164
311k
      key += key_step;
165
311k
    }
166
216k
    step <<= 1;
167
216k
    key_step >>= 1;
168
216k
  } while (++bits <= BROTLI_HUFFMAN_MAX_CODE_LENGTH_CODE_LENGTH);
169
43.2k
}
170
171
uint32_t BrotliBuildHuffmanTable(HuffmanCode* root_table,
172
                                 int root_bits,
173
                                 const uint16_t* const symbol_lists,
174
43.3k
                                 uint16_t* count) {
175
43.3k
  HuffmanCode code;       /* current table entry */
176
43.3k
  HuffmanCode* table;     /* next available space in table */
177
43.3k
  int len;                /* current code length */
178
43.3k
  int symbol;             /* symbol index in original or sorted table */
179
43.3k
  brotli_reg_t key;       /* prefix code */
180
43.3k
  brotli_reg_t key_step;  /* prefix code addend */
181
43.3k
  brotli_reg_t sub_key;   /* 2nd level table prefix code */
182
43.3k
  brotli_reg_t sub_key_step;  /* 2nd level table prefix code addend */
183
43.3k
  int step;               /* step size to replicate values in current table */
184
43.3k
  int table_bits;         /* key length of current table */
185
43.3k
  int table_size;         /* size of current table */
186
43.3k
  int total_size;         /* sum of root table size and 2nd level table sizes */
187
43.3k
  int max_length = -1;
188
43.3k
  int bits;
189
43.3k
  int bits_count;
190
191
43.3k
  BROTLI_DCHECK(root_bits <= BROTLI_REVERSE_BITS_MAX);
192
43.3k
  BROTLI_DCHECK(BROTLI_HUFFMAN_MAX_CODE_LENGTH - root_bits <=
193
43.3k
                BROTLI_REVERSE_BITS_MAX);
194
195
370k
  while (symbol_lists[max_length] == 0xFFFF) max_length--;
196
43.3k
  max_length += BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1;
197
198
43.3k
  table = root_table;
199
43.3k
  table_bits = root_bits;
200
43.3k
  table_size = 1 << table_bits;
201
43.3k
  total_size = table_size;
202
203
  /* Fill in the root table. Reduce the table size to if possible,
204
     and create the repetitions by memcpy. */
205
43.3k
  if (table_bits > max_length) {
206
21.1k
    table_bits = max_length;
207
21.1k
    table_size = 1 << table_bits;
208
21.1k
  }
209
43.3k
  key = 0;
210
43.3k
  key_step = BROTLI_REVERSE_BITS_LOWEST;
211
43.3k
  bits = 1;
212
43.3k
  step = 2;
213
280k
  do {
214
280k
    code.bits = (uint8_t)bits;
215
280k
    symbol = bits - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
216
2.19M
    for (bits_count = count[bits]; bits_count != 0; --bits_count) {
217
1.91M
      symbol = symbol_lists[symbol];
218
1.91M
      code.value = (uint16_t)symbol;
219
1.91M
      ReplicateValue(&table[BrotliReverseBits(key)], step, table_size, code);
220
1.91M
      key += key_step;
221
1.91M
    }
222
280k
    step <<= 1;
223
280k
    key_step >>= 1;
224
280k
  } while (++bits <= table_bits);
225
226
  /* If root_bits != table_bits then replicate to fill the remaining slots. */
227
109k
  while (total_size != table_size) {
228
66.5k
    memcpy(&table[table_size], &table[0],
229
66.5k
           (size_t)table_size * sizeof(table[0]));
230
66.5k
    table_size <<= 1;
231
66.5k
  }
232
233
  /* Fill in 2nd level tables and add pointers to root table. */
234
43.3k
  key_step = BROTLI_REVERSE_BITS_LOWEST >> (root_bits - 1);
235
43.3k
  sub_key = (BROTLI_REVERSE_BITS_LOWEST << 1);
236
43.3k
  sub_key_step = BROTLI_REVERSE_BITS_LOWEST;
237
86.6k
  for (len = root_bits + 1, step = 2; len <= max_length; ++len) {
238
43.2k
    symbol = len - (BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1);
239
1.52M
    for (; count[len] != 0; --count[len]) {
240
1.48M
      if (sub_key == (BROTLI_REVERSE_BITS_LOWEST << 1U)) {
241
475k
        table += table_size;
242
475k
        table_bits = NextTableBitSize(count, len, root_bits);
243
475k
        table_size = 1 << table_bits;
244
475k
        total_size += table_size;
245
475k
        sub_key = BrotliReverseBits(key);
246
475k
        key += key_step;
247
475k
        root_table[sub_key].bits = (uint8_t)(table_bits + root_bits);
248
475k
        root_table[sub_key].value =
249
475k
            (uint16_t)(((size_t)(table - root_table)) - sub_key);
250
475k
        sub_key = 0;
251
475k
      }
252
1.48M
      code.bits = (uint8_t)(len - root_bits);
253
1.48M
      symbol = symbol_lists[symbol];
254
1.48M
      code.value = (uint16_t)symbol;
255
1.48M
      ReplicateValue(
256
1.48M
          &table[BrotliReverseBits(sub_key)], step, table_size, code);
257
1.48M
      sub_key += sub_key_step;
258
1.48M
    }
259
43.2k
    step <<= 1;
260
43.2k
    sub_key_step >>= 1;
261
43.2k
  }
262
43.3k
  return (uint32_t)total_size;
263
43.3k
}
264
265
uint32_t BrotliBuildSimpleHuffmanTable(HuffmanCode* table,
266
                                       int root_bits,
267
                                       uint16_t* val,
268
64.1k
                                       uint32_t num_symbols) {
269
64.1k
  uint32_t table_size = 1;
270
64.1k
  const uint32_t goal_size = 1U << root_bits;
271
64.1k
  switch (num_symbols) {
272
37.8k
    case 0:
273
37.8k
      table[0].bits = 0;
274
37.8k
      table[0].value = val[0];
275
37.8k
      break;
276
10.3k
    case 1:
277
10.3k
      table[0].bits = 1;
278
10.3k
      table[1].bits = 1;
279
10.3k
      if (val[1] > val[0]) {
280
7.54k
        table[0].value = val[0];
281
7.54k
        table[1].value = val[1];
282
7.54k
      } else {
283
2.82k
        table[0].value = val[1];
284
2.82k
        table[1].value = val[0];
285
2.82k
      }
286
10.3k
      table_size = 2;
287
10.3k
      break;
288
11.7k
    case 2:
289
11.7k
      table[0].bits = 1;
290
11.7k
      table[0].value = val[0];
291
11.7k
      table[2].bits = 1;
292
11.7k
      table[2].value = val[0];
293
11.7k
      if (val[2] > val[1]) {
294
4.43k
        table[1].value = val[1];
295
4.43k
        table[3].value = val[2];
296
7.31k
      } else {
297
7.31k
        table[1].value = val[2];
298
7.31k
        table[3].value = val[1];
299
7.31k
      }
300
11.7k
      table[1].bits = 2;
301
11.7k
      table[3].bits = 2;
302
11.7k
      table_size = 4;
303
11.7k
      break;
304
2.27k
    case 3: {
305
2.27k
      int i, k;
306
9.11k
      for (i = 0; i < 3; ++i) {
307
20.5k
        for (k = i + 1; k < 4; ++k) {
308
13.6k
          if (val[k] < val[i]) {
309
5.60k
            uint16_t t = val[k];
310
5.60k
            val[k] = val[i];
311
5.60k
            val[i] = t;
312
5.60k
          }
313
13.6k
        }
314
6.83k
      }
315
11.3k
      for (i = 0; i < 4; ++i) {
316
9.11k
        table[i].bits = 2;
317
9.11k
      }
318
2.27k
      table[0].value = val[0];
319
2.27k
      table[2].value = val[1];
320
2.27k
      table[1].value = val[2];
321
2.27k
      table[3].value = val[3];
322
2.27k
      table_size = 4;
323
2.27k
      break;
324
0
    }
325
1.91k
    case 4: {
326
1.91k
      int i;
327
1.91k
      if (val[3] < val[2]) {
328
871
        uint16_t t = val[3];
329
871
        val[3] = val[2];
330
871
        val[2] = t;
331
871
      }
332
15.3k
      for (i = 0; i < 7; ++i) {
333
13.3k
        table[i].value = val[0];
334
13.3k
        table[i].bits = (uint8_t)(1 + (i & 1));
335
13.3k
      }
336
1.91k
      table[1].value = val[1];
337
1.91k
      table[3].value = val[2];
338
1.91k
      table[5].value = val[1];
339
1.91k
      table[7].value = val[3];
340
1.91k
      table[3].bits = 3;
341
1.91k
      table[7].bits = 3;
342
1.91k
      table_size = 8;
343
1.91k
      break;
344
0
    }
345
64.1k
  }
346
533k
  while (table_size != goal_size) {
347
469k
    memcpy(&table[table_size], &table[0],
348
469k
           (size_t)table_size * sizeof(table[0]));
349
469k
    table_size <<= 1;
350
469k
  }
351
64.1k
  return goal_size;
352
64.1k
}
353
354
#if defined(__cplusplus) || defined(c_plusplus)
355
}  /* extern "C" */
356
#endif