/src/libwebp/src/utils/huffman_utils.c
Line | Count | Source (jump to first uncovered line) |
1 | | // Copyright 2012 Google Inc. All Rights Reserved. |
2 | | // |
3 | | // Use of this source code is governed by a BSD-style license |
4 | | // that can be found in the COPYING file in the root of the source |
5 | | // tree. An additional intellectual property rights grant can be found |
6 | | // in the file PATENTS. All contributing project authors may |
7 | | // be found in the AUTHORS file in the root of the source tree. |
8 | | // ----------------------------------------------------------------------------- |
9 | | // |
10 | | // Utilities for building and looking up Huffman trees. |
11 | | // |
12 | | // Author: Urvang Joshi (urvang@google.com) |
13 | | |
14 | | #include <assert.h> |
15 | | #include <stdlib.h> |
16 | | #include <string.h> |
17 | | #include "src/utils/huffman_utils.h" |
18 | | #include "src/utils/utils.h" |
19 | | #include "src/webp/format_constants.h" |
20 | | |
21 | | // Huffman data read via DecodeImageStream is represented in two (red and green) |
22 | | // bytes. |
23 | | #define MAX_HTREE_GROUPS 0x10000 |
24 | | |
25 | 0 | HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) { |
26 | 0 | HTreeGroup* const htree_groups = |
27 | 0 | (HTreeGroup*)WebPSafeMalloc(num_htree_groups, sizeof(*htree_groups)); |
28 | 0 | if (htree_groups == NULL) { |
29 | 0 | return NULL; |
30 | 0 | } |
31 | 0 | assert(num_htree_groups <= MAX_HTREE_GROUPS); |
32 | 0 | return htree_groups; |
33 | 0 | } |
34 | | |
35 | 0 | void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups) { |
36 | 0 | if (htree_groups != NULL) { |
37 | 0 | WebPSafeFree(htree_groups); |
38 | 0 | } |
39 | 0 | } |
40 | | |
41 | | // Returns reverse(reverse(key, len) + 1, len), where reverse(key, len) is the |
42 | | // bit-wise reversal of the len least significant bits of key. |
43 | 0 | static WEBP_INLINE uint32_t GetNextKey(uint32_t key, int len) { |
44 | 0 | uint32_t step = 1 << (len - 1); |
45 | 0 | while (key & step) { |
46 | 0 | step >>= 1; |
47 | 0 | } |
48 | 0 | return step ? (key & (step - 1)) + step : key; |
49 | 0 | } |
50 | | |
51 | | // Stores code in table[0], table[step], table[2*step], ..., table[end]. |
52 | | // Assumes that end is an integer multiple of step. |
53 | | static WEBP_INLINE void ReplicateValue(HuffmanCode* table, |
54 | | int step, int end, |
55 | 0 | HuffmanCode code) { |
56 | 0 | assert(end % step == 0); |
57 | 0 | do { |
58 | 0 | end -= step; |
59 | 0 | table[end] = code; |
60 | 0 | } while (end > 0); |
61 | 0 | } |
62 | | |
63 | | // Returns the table width of the next 2nd level table. count is the histogram |
64 | | // of bit lengths for the remaining symbols, len is the code length of the next |
65 | | // processed symbol |
66 | | static WEBP_INLINE int NextTableBitSize(const int* const count, |
67 | 0 | int len, int root_bits) { |
68 | 0 | int left = 1 << (len - root_bits); |
69 | 0 | while (len < MAX_ALLOWED_CODE_LENGTH) { |
70 | 0 | left -= count[len]; |
71 | 0 | if (left <= 0) break; |
72 | 0 | ++len; |
73 | 0 | left <<= 1; |
74 | 0 | } |
75 | 0 | return len - root_bits; |
76 | 0 | } |
77 | | |
78 | | // sorted[code_lengths_size] is a pre-allocated array for sorting symbols |
79 | | // by code length. |
80 | | static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits, |
81 | | const int code_lengths[], int code_lengths_size, |
82 | 0 | uint16_t sorted[]) { |
83 | 0 | HuffmanCode* table = root_table; // next available space in table |
84 | 0 | int total_size = 1 << root_bits; // total size root table + 2nd level table |
85 | 0 | int len; // current code length |
86 | 0 | int symbol; // symbol index in original or sorted table |
87 | | // number of codes of each length: |
88 | 0 | int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; |
89 | | // offsets in sorted table for each length: |
90 | 0 | int offset[MAX_ALLOWED_CODE_LENGTH + 1]; |
91 | |
|
92 | 0 | assert(code_lengths_size != 0); |
93 | 0 | assert(code_lengths != NULL); |
94 | 0 | assert((root_table != NULL && sorted != NULL) || |
95 | 0 | (root_table == NULL && sorted == NULL)); |
96 | 0 | assert(root_bits > 0); |
97 | | |
98 | | // Build histogram of code lengths. |
99 | 0 | for (symbol = 0; symbol < code_lengths_size; ++symbol) { |
100 | 0 | if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) { |
101 | 0 | return 0; |
102 | 0 | } |
103 | 0 | ++count[code_lengths[symbol]]; |
104 | 0 | } |
105 | | |
106 | | // Error, all code lengths are zeros. |
107 | 0 | if (count[0] == code_lengths_size) { |
108 | 0 | return 0; |
109 | 0 | } |
110 | | |
111 | | // Generate offsets into sorted symbol table by code length. |
112 | 0 | offset[1] = 0; |
113 | 0 | for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) { |
114 | 0 | if (count[len] > (1 << len)) { |
115 | 0 | return 0; |
116 | 0 | } |
117 | 0 | offset[len + 1] = offset[len] + count[len]; |
118 | 0 | } |
119 | | |
120 | | // Sort symbols by length, by symbol order within each length. |
121 | 0 | for (symbol = 0; symbol < code_lengths_size; ++symbol) { |
122 | 0 | const int symbol_code_length = code_lengths[symbol]; |
123 | 0 | if (code_lengths[symbol] > 0) { |
124 | 0 | if (sorted != NULL) { |
125 | 0 | if(offset[symbol_code_length] >= code_lengths_size) { |
126 | 0 | return 0; |
127 | 0 | } |
128 | 0 | sorted[offset[symbol_code_length]++] = symbol; |
129 | 0 | } else { |
130 | 0 | offset[symbol_code_length]++; |
131 | 0 | } |
132 | 0 | } |
133 | 0 | } |
134 | | |
135 | | // Special case code with only one value. |
136 | 0 | if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) { |
137 | 0 | if (sorted != NULL) { |
138 | 0 | HuffmanCode code; |
139 | 0 | code.bits = 0; |
140 | 0 | code.value = (uint16_t)sorted[0]; |
141 | 0 | ReplicateValue(table, 1, total_size, code); |
142 | 0 | } |
143 | 0 | return total_size; |
144 | 0 | } |
145 | | |
146 | 0 | { |
147 | 0 | int step; // step size to replicate values in current table |
148 | 0 | uint32_t low = 0xffffffffu; // low bits for current root entry |
149 | 0 | uint32_t mask = total_size - 1; // mask for low bits |
150 | 0 | uint32_t key = 0; // reversed prefix code |
151 | 0 | int num_nodes = 1; // number of Huffman tree nodes |
152 | 0 | int num_open = 1; // number of open branches in current tree level |
153 | 0 | int table_bits = root_bits; // key length of current table |
154 | 0 | int table_size = 1 << table_bits; // size of current table |
155 | 0 | symbol = 0; |
156 | | // Fill in root table. |
157 | 0 | for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) { |
158 | 0 | num_open <<= 1; |
159 | 0 | num_nodes += num_open; |
160 | 0 | num_open -= count[len]; |
161 | 0 | if (num_open < 0) { |
162 | 0 | return 0; |
163 | 0 | } |
164 | 0 | if (root_table == NULL) continue; |
165 | 0 | for (; count[len] > 0; --count[len]) { |
166 | 0 | HuffmanCode code; |
167 | 0 | code.bits = (uint8_t)len; |
168 | 0 | code.value = (uint16_t)sorted[symbol++]; |
169 | 0 | ReplicateValue(&table[key], step, table_size, code); |
170 | 0 | key = GetNextKey(key, len); |
171 | 0 | } |
172 | 0 | } |
173 | | |
174 | | // Fill in 2nd level tables and add pointers to root table. |
175 | 0 | for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH; |
176 | 0 | ++len, step <<= 1) { |
177 | 0 | num_open <<= 1; |
178 | 0 | num_nodes += num_open; |
179 | 0 | num_open -= count[len]; |
180 | 0 | if (num_open < 0) { |
181 | 0 | return 0; |
182 | 0 | } |
183 | 0 | for (; count[len] > 0; --count[len]) { |
184 | 0 | HuffmanCode code; |
185 | 0 | if ((key & mask) != low) { |
186 | 0 | if (root_table != NULL) table += table_size; |
187 | 0 | table_bits = NextTableBitSize(count, len, root_bits); |
188 | 0 | table_size = 1 << table_bits; |
189 | 0 | total_size += table_size; |
190 | 0 | low = key & mask; |
191 | 0 | if (root_table != NULL) { |
192 | 0 | root_table[low].bits = (uint8_t)(table_bits + root_bits); |
193 | 0 | root_table[low].value = (uint16_t)((table - root_table) - low); |
194 | 0 | } |
195 | 0 | } |
196 | 0 | if (root_table != NULL) { |
197 | 0 | code.bits = (uint8_t)(len - root_bits); |
198 | 0 | code.value = (uint16_t)sorted[symbol++]; |
199 | 0 | ReplicateValue(&table[key >> root_bits], step, table_size, code); |
200 | 0 | } |
201 | 0 | key = GetNextKey(key, len); |
202 | 0 | } |
203 | 0 | } |
204 | | |
205 | | // Check if tree is full. |
206 | 0 | if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) { |
207 | 0 | return 0; |
208 | 0 | } |
209 | 0 | } |
210 | | |
211 | 0 | return total_size; |
212 | 0 | } |
213 | | |
214 | | // Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_bits). |
215 | | // More commonly, the value is around ~280. |
216 | | #define MAX_CODE_LENGTHS_SIZE \ |
217 | | ((1 << MAX_CACHE_BITS) + NUM_LITERAL_CODES + NUM_LENGTH_CODES) |
218 | | // Cut-off value for switching between heap and stack allocation. |
219 | 0 | #define SORTED_SIZE_CUTOFF 512 |
220 | | int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits, |
221 | 0 | const int code_lengths[], int code_lengths_size) { |
222 | 0 | const int total_size = |
223 | 0 | BuildHuffmanTable(NULL, root_bits, code_lengths, code_lengths_size, NULL); |
224 | 0 | assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE); |
225 | 0 | if (total_size == 0 || root_table == NULL) return total_size; |
226 | | |
227 | 0 | if (root_table->curr_segment->curr_table + total_size >= |
228 | 0 | root_table->curr_segment->start + root_table->curr_segment->size) { |
229 | | // If 'root_table' does not have enough memory, allocate a new segment. |
230 | | // The available part of root_table->curr_segment is left unused because we |
231 | | // need a contiguous buffer. |
232 | 0 | const int segment_size = root_table->curr_segment->size; |
233 | 0 | struct HuffmanTablesSegment* next = |
234 | 0 | (HuffmanTablesSegment*)WebPSafeMalloc(1, sizeof(*next)); |
235 | 0 | if (next == NULL) return 0; |
236 | | // Fill the new segment. |
237 | | // We need at least 'total_size' but if that value is small, it is better to |
238 | | // allocate a big chunk to prevent more allocations later. 'segment_size' is |
239 | | // therefore chosen (any other arbitrary value could be chosen). |
240 | 0 | next->size = total_size > segment_size ? total_size : segment_size; |
241 | 0 | next->start = |
242 | 0 | (HuffmanCode*)WebPSafeMalloc(next->size, sizeof(*next->start)); |
243 | 0 | if (next->start == NULL) { |
244 | 0 | WebPSafeFree(next); |
245 | 0 | return 0; |
246 | 0 | } |
247 | 0 | next->curr_table = next->start; |
248 | 0 | next->next = NULL; |
249 | | // Point to the new segment. |
250 | 0 | root_table->curr_segment->next = next; |
251 | 0 | root_table->curr_segment = next; |
252 | 0 | } |
253 | 0 | if (code_lengths_size <= SORTED_SIZE_CUTOFF) { |
254 | | // use local stack-allocated array. |
255 | 0 | uint16_t sorted[SORTED_SIZE_CUTOFF]; |
256 | 0 | BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits, |
257 | 0 | code_lengths, code_lengths_size, sorted); |
258 | 0 | } else { // rare case. Use heap allocation. |
259 | 0 | uint16_t* const sorted = |
260 | 0 | (uint16_t*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted)); |
261 | 0 | if (sorted == NULL) return 0; |
262 | 0 | BuildHuffmanTable(root_table->curr_segment->curr_table, root_bits, |
263 | 0 | code_lengths, code_lengths_size, sorted); |
264 | 0 | WebPSafeFree(sorted); |
265 | 0 | } |
266 | 0 | return total_size; |
267 | 0 | } |
268 | | |
269 | 0 | int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables) { |
270 | | // Have 'segment' point to the first segment for now, 'root'. |
271 | 0 | HuffmanTablesSegment* const root = &huffman_tables->root; |
272 | 0 | huffman_tables->curr_segment = root; |
273 | 0 | root->next = NULL; |
274 | | // Allocate root. |
275 | 0 | root->start = (HuffmanCode*)WebPSafeMalloc(size, sizeof(*root->start)); |
276 | 0 | if (root->start == NULL) return 0; |
277 | 0 | root->curr_table = root->start; |
278 | 0 | root->size = size; |
279 | 0 | return 1; |
280 | 0 | } |
281 | | |
282 | 0 | void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables) { |
283 | 0 | HuffmanTablesSegment *current, *next; |
284 | 0 | if (huffman_tables == NULL) return; |
285 | | // Free the root node. |
286 | 0 | current = &huffman_tables->root; |
287 | 0 | next = current->next; |
288 | 0 | WebPSafeFree(current->start); |
289 | 0 | current->start = NULL; |
290 | 0 | current->next = NULL; |
291 | 0 | current = next; |
292 | | // Free the following nodes. |
293 | 0 | while (current != NULL) { |
294 | 0 | next = current->next; |
295 | 0 | WebPSafeFree(current->start); |
296 | 0 | WebPSafeFree(current); |
297 | 0 | current = next; |
298 | 0 | } |
299 | 0 | } |