Add ICU message format support
[chromium-blink-merge.git] / third_party / brotli / dec / huffman.c
blob9590c761a07f732cad3c223493382be5db406136
1 /* Copyright 2013 Google Inc. All Rights Reserved.
3 Licensed under the Apache License, Version 2.0 (the "License");
4 you may not use this file except in compliance with the License.
5 You may obtain a copy of the License at
7 http://www.apache.org/licenses/LICENSE-2.0
9 Unless required by applicable law or agreed to in writing, software
10 distributed under the License is distributed on an "AS IS" BASIS,
11 WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
12 See the License for the specific language governing permissions and
13 limitations under the License.
16 /* Utilities for building Huffman decoding tables. */
18 #include <assert.h>
19 #include <stdlib.h>
20 #include <stdio.h>
21 #include <string.h>
22 #include "./huffman.h"
23 #include "./safe_malloc.h"
25 #if defined(__cplusplus) || defined(c_plusplus)
26 extern "C" {
27 #endif
29 #define MAX_LENGTH 15
31 /* Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the
32 bit-wise reversal of the len least significant bits of key. */
33 static BROTLI_INLINE int GetNextKey(int key, int len) {
34 int step = 1 << (len - 1);
35 while (key & step) {
36 step >>= 1;
38 return (key & (step - 1)) + step;
41 /* Stores code in table[0], table[step], table[2*step], ..., table[end] */
42 /* Assumes that end is an integer multiple of step */
43 static BROTLI_INLINE void ReplicateValue(HuffmanCode* table,
44 int step, int end,
45 HuffmanCode code) {
46 do {
47 end -= step;
48 table[end] = code;
49 } while (end > 0);
52 /* Returns the table width of the next 2nd level table. count is the histogram
53 of bit lengths for the remaining symbols, len is the code length of the next
54 processed symbol */
55 static BROTLI_INLINE int NextTableBitSize(const int* const count,
56 int len, int root_bits) {
57 int left = 1 << (len - root_bits);
58 while (len < MAX_LENGTH) {
59 left -= count[len];
60 if (left <= 0) break;
61 ++len;
62 left <<= 1;
64 return len - root_bits;
67 int BrotliBuildHuffmanTable(HuffmanCode* root_table,
68 int root_bits,
69 const uint8_t* const code_lengths,
70 int code_lengths_size) {
71 HuffmanCode code; /* current table entry */
72 HuffmanCode* table; /* next available space in table */
73 int len; /* current code length */
74 int symbol; /* symbol index in original or sorted table */
75 int key; /* reversed prefix code */
76 int step; /* step size to replicate values in current table */
77 int low; /* low bits for current root entry */
78 int mask; /* mask for low bits */
79 int table_bits; /* key length of current table */
80 int table_size; /* size of current table */
81 int total_size; /* sum of root table size and 2nd level table sizes */
82 int* sorted; /* symbols sorted by code length */
83 int count[MAX_LENGTH + 1] = { 0 }; /* number of codes of each length */
84 int offset[MAX_LENGTH + 1]; /* offsets in sorted table for each length */
86 sorted = (int*)malloc((size_t)code_lengths_size * sizeof(*sorted));
87 if (sorted == NULL) {
88 return 0;
91 /* build histogram of code lengths */
92 for (symbol = 0; symbol < code_lengths_size; symbol++) {
93 count[code_lengths[symbol]]++;
96 /* generate offsets into sorted symbol table by code length */
97 offset[1] = 0;
98 for (len = 1; len < MAX_LENGTH; len++) {
99 offset[len + 1] = offset[len] + count[len];
102 /* sort symbols by length, by symbol order within each length */
103 for (symbol = 0; symbol < code_lengths_size; symbol++) {
104 if (code_lengths[symbol] != 0) {
105 sorted[offset[code_lengths[symbol]]++] = symbol;
109 table = root_table;
110 table_bits = root_bits;
111 table_size = 1 << table_bits;
112 total_size = table_size;
114 /* special case code with only one value */
115 if (offset[MAX_LENGTH] == 1) {
116 code.bits = 0;
117 code.value = (uint16_t)sorted[0];
118 for (key = 0; key < total_size; ++key) {
119 table[key] = code;
121 free(sorted);
122 return total_size;
125 /* fill in root table */
126 key = 0;
127 symbol = 0;
128 for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
129 for (; count[len] > 0; --count[len]) {
130 code.bits = (uint8_t)(len);
131 code.value = (uint16_t)sorted[symbol++];
132 ReplicateValue(&table[key], step, table_size, code);
133 key = GetNextKey(key, len);
137 /* fill in 2nd level tables and add pointers to root table */
138 mask = total_size - 1;
139 low = -1;
140 for (len = root_bits + 1, step = 2; len <= MAX_LENGTH; ++len, step <<= 1) {
141 for (; count[len] > 0; --count[len]) {
142 if ((key & mask) != low) {
143 table += table_size;
144 table_bits = NextTableBitSize(count, len, root_bits);
145 table_size = 1 << table_bits;
146 total_size += table_size;
147 low = key & mask;
148 root_table[low].bits = (uint8_t)(table_bits + root_bits);
149 root_table[low].value = (uint16_t)((table - root_table) - low);
151 code.bits = (uint8_t)(len - root_bits);
152 code.value = (uint16_t)sorted[symbol++];
153 ReplicateValue(&table[key >> root_bits], step, table_size, code);
154 key = GetNextKey(key, len);
158 free(sorted);
159 return total_size;
162 void BrotliHuffmanTreeGroupInit(HuffmanTreeGroup* group, int alphabet_size,
163 int ntrees) {
164 group->alphabet_size = alphabet_size;
165 group->num_htrees = ntrees;
166 group->codes = (HuffmanCode*)malloc(
167 sizeof(HuffmanCode) * (size_t)(ntrees * BROTLI_HUFFMAN_MAX_TABLE_SIZE));
168 group->htrees = (HuffmanCode**)malloc(sizeof(HuffmanCode*) * (size_t)ntrees);
171 void BrotliHuffmanTreeGroupRelease(HuffmanTreeGroup* group) {
172 if (group->codes) {
173 free(group->codes);
175 if (group->htrees) {
176 free(group->htrees);
180 #if defined(__cplusplus) || defined(c_plusplus)
181 } /* extern "C" */
182 #endif