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
VP8LHtreeGroupsNew(int num_htree_groups)25 HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) {
26 HTreeGroup* const htree_groups =
27 (HTreeGroup*)WebPSafeMalloc(num_htree_groups, sizeof(*htree_groups));
28 if (htree_groups == NULL) {
29 return NULL;
30 }
31 assert(num_htree_groups <= MAX_HTREE_GROUPS);
32 return htree_groups;
33 }
34
VP8LHtreeGroupsFree(HTreeGroup * const htree_groups)35 void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups) {
36 if (htree_groups != NULL) {
37 WebPSafeFree(htree_groups);
38 }
39 }
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.
GetNextKey(uint32_t key,int len)43 static WEBP_INLINE uint32_t GetNextKey(uint32_t key, int len) {
44 uint32_t step = 1 << (len - 1);
45 while (key & step) {
46 step >>= 1;
47 }
48 return step ? (key & (step - 1)) + step : key;
49 }
50
51 // Stores code in table[0], table[step], table[2*step], ..., table[end].
52 // Assumes that end is an integer multiple of step.
ReplicateValue(HuffmanCode * table,int step,int end,HuffmanCode code)53 static WEBP_INLINE void ReplicateValue(HuffmanCode* table,
54 int step, int end,
55 HuffmanCode code) {
56 assert(end % step == 0);
57 do {
58 end -= step;
59 table[end] = code;
60 } while (end > 0);
61 }
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
NextTableBitSize(const int * const count,int len,int root_bits)66 static WEBP_INLINE int NextTableBitSize(const int* const count,
67 int len, int root_bits) {
68 int left = 1 << (len - root_bits);
69 while (len < MAX_ALLOWED_CODE_LENGTH) {
70 left -= count[len];
71 if (left <= 0) break;
72 ++len;
73 left <<= 1;
74 }
75 return len - root_bits;
76 }
77
78 // sorted[code_lengths_size] is a pre-allocated array for sorting symbols
79 // by code length.
BuildHuffmanTable(HuffmanCode * const root_table,int root_bits,const int code_lengths[],int code_lengths_size,uint16_t sorted[])80 static int BuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
81 const int code_lengths[], int code_lengths_size,
82 uint16_t sorted[]) {
83 HuffmanCode* table = root_table; // next available space in table
84 int total_size = 1 << root_bits; // total size root table + 2nd level table
85 int len; // current code length
86 int symbol; // symbol index in original or sorted table
87 // number of codes of each length:
88 int count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
89 // offsets in sorted table for each length:
90 int offset[MAX_ALLOWED_CODE_LENGTH + 1];
91
92 assert(code_lengths_size != 0);
93 assert(code_lengths != NULL);
94 assert((root_table != NULL && sorted != NULL) ||
95 (root_table == NULL && sorted == NULL));
96 assert(root_bits > 0);
97
98 // Build histogram of code lengths.
99 for (symbol = 0; symbol < code_lengths_size; ++symbol) {
100 if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) {
101 return 0;
102 }
103 ++count[code_lengths[symbol]];
104 }
105
106 // Error, all code lengths are zeros.
107 if (count[0] == code_lengths_size) {
108 return 0;
109 }
110
111 // Generate offsets into sorted symbol table by code length.
112 offset[1] = 0;
113 for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) {
114 if (count[len] > (1 << len)) {
115 return 0;
116 }
117 offset[len + 1] = offset[len] + count[len];
118 }
119
120 // Sort symbols by length, by symbol order within each length.
121 for (symbol = 0; symbol < code_lengths_size; ++symbol) {
122 const int symbol_code_length = code_lengths[symbol];
123 if (code_lengths[symbol] > 0) {
124 if (sorted != NULL) {
125 sorted[offset[symbol_code_length]++] = symbol;
126 } else {
127 offset[symbol_code_length]++;
128 }
129 }
130 }
131
132 // Special case code with only one value.
133 if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) {
134 if (sorted != NULL) {
135 HuffmanCode code;
136 code.bits = 0;
137 code.value = (uint16_t)sorted[0];
138 ReplicateValue(table, 1, total_size, code);
139 }
140 return total_size;
141 }
142
143 {
144 int step; // step size to replicate values in current table
145 uint32_t low = -1; // low bits for current root entry
146 uint32_t mask = total_size - 1; // mask for low bits
147 uint32_t key = 0; // reversed prefix code
148 int num_nodes = 1; // number of Huffman tree nodes
149 int num_open = 1; // number of open branches in current tree level
150 int table_bits = root_bits; // key length of current table
151 int table_size = 1 << table_bits; // size of current table
152 symbol = 0;
153 // Fill in root table.
154 for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
155 num_open <<= 1;
156 num_nodes += num_open;
157 num_open -= count[len];
158 if (num_open < 0) {
159 return 0;
160 }
161 if (root_table == NULL) continue;
162 for (; count[len] > 0; --count[len]) {
163 HuffmanCode code;
164 code.bits = (uint8_t)len;
165 code.value = (uint16_t)sorted[symbol++];
166 ReplicateValue(&table[key], step, table_size, code);
167 key = GetNextKey(key, len);
168 }
169 }
170
171 // Fill in 2nd level tables and add pointers to root table.
172 for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH;
173 ++len, step <<= 1) {
174 num_open <<= 1;
175 num_nodes += num_open;
176 num_open -= count[len];
177 if (num_open < 0) {
178 return 0;
179 }
180 if (root_table == NULL) continue;
181 for (; count[len] > 0; --count[len]) {
182 HuffmanCode code;
183 if ((key & mask) != low) {
184 table += table_size;
185 table_bits = NextTableBitSize(count, len, root_bits);
186 table_size = 1 << table_bits;
187 total_size += table_size;
188 low = key & mask;
189 root_table[low].bits = (uint8_t)(table_bits + root_bits);
190 root_table[low].value = (uint16_t)((table - root_table) - low);
191 }
192 code.bits = (uint8_t)(len - root_bits);
193 code.value = (uint16_t)sorted[symbol++];
194 ReplicateValue(&table[key >> root_bits], step, table_size, code);
195 key = GetNextKey(key, len);
196 }
197 }
198
199 // Check if tree is full.
200 if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) {
201 return 0;
202 }
203 }
204
205 return total_size;
206 }
207
208 // Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_bits).
209 // More commonly, the value is around ~280.
210 #define MAX_CODE_LENGTHS_SIZE \
211 ((1 << MAX_CACHE_BITS) + NUM_LITERAL_CODES + NUM_LENGTH_CODES)
212 // Cut-off value for switching between heap and stack allocation.
213 #define SORTED_SIZE_CUTOFF 512
VP8LBuildHuffmanTable(HuffmanCode * const root_table,int root_bits,const int code_lengths[],int code_lengths_size)214 int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
215 const int code_lengths[], int code_lengths_size) {
216 int total_size;
217 assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE);
218 if (root_table == NULL) {
219 total_size = BuildHuffmanTable(NULL, root_bits,
220 code_lengths, code_lengths_size, NULL);
221 } else if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
222 // use local stack-allocated array.
223 uint16_t sorted[SORTED_SIZE_CUTOFF];
224 total_size = BuildHuffmanTable(root_table, root_bits,
225 code_lengths, code_lengths_size, sorted);
226 } else { // rare case. Use heap allocation.
227 uint16_t* const sorted =
228 (uint16_t*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted));
229 if (sorted == NULL) return 0;
230 total_size = BuildHuffmanTable(root_table, root_bits,
231 code_lengths, code_lengths_size, sorted);
232 WebPSafeFree(sorted);
233 }
234 return total_size;
235 }
236