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);
95 assert(root_bits > 0);
96
97 // Build histogram of code lengths.
98 for (symbol = 0; symbol < code_lengths_size; ++symbol) {
99 if (code_lengths[symbol] > MAX_ALLOWED_CODE_LENGTH) {
100 return 0;
101 }
102 ++count[code_lengths[symbol]];
103 }
104
105 // Error, all code lengths are zeros.
106 if (count[0] == code_lengths_size) {
107 return 0;
108 }
109
110 // Generate offsets into sorted symbol table by code length.
111 offset[1] = 0;
112 for (len = 1; len < MAX_ALLOWED_CODE_LENGTH; ++len) {
113 if (count[len] > (1 << len)) {
114 return 0;
115 }
116 offset[len + 1] = offset[len] + count[len];
117 }
118
119 // Sort symbols by length, by symbol order within each length.
120 for (symbol = 0; symbol < code_lengths_size; ++symbol) {
121 const int symbol_code_length = code_lengths[symbol];
122 if (code_lengths[symbol] > 0) {
123 sorted[offset[symbol_code_length]++] = symbol;
124 }
125 }
126
127 // Special case code with only one value.
128 if (offset[MAX_ALLOWED_CODE_LENGTH] == 1) {
129 HuffmanCode code;
130 code.bits = 0;
131 code.value = (uint16_t)sorted[0];
132 ReplicateValue(table, 1, total_size, code);
133 return total_size;
134 }
135
136 {
137 int step; // step size to replicate values in current table
138 uint32_t low = -1; // low bits for current root entry
139 uint32_t mask = total_size - 1; // mask for low bits
140 uint32_t key = 0; // reversed prefix code
141 int num_nodes = 1; // number of Huffman tree nodes
142 int num_open = 1; // number of open branches in current tree level
143 int table_bits = root_bits; // key length of current table
144 int table_size = 1 << table_bits; // size of current table
145 symbol = 0;
146 // Fill in root table.
147 for (len = 1, step = 2; len <= root_bits; ++len, step <<= 1) {
148 num_open <<= 1;
149 num_nodes += num_open;
150 num_open -= count[len];
151 if (num_open < 0) {
152 return 0;
153 }
154 for (; count[len] > 0; --count[len]) {
155 HuffmanCode code;
156 code.bits = (uint8_t)len;
157 code.value = (uint16_t)sorted[symbol++];
158 ReplicateValue(&table[key], step, table_size, code);
159 key = GetNextKey(key, len);
160 }
161 }
162
163 // Fill in 2nd level tables and add pointers to root table.
164 for (len = root_bits + 1, step = 2; len <= MAX_ALLOWED_CODE_LENGTH;
165 ++len, step <<= 1) {
166 num_open <<= 1;
167 num_nodes += num_open;
168 num_open -= count[len];
169 if (num_open < 0) {
170 return 0;
171 }
172 for (; count[len] > 0; --count[len]) {
173 HuffmanCode code;
174 if ((key & mask) != low) {
175 table += table_size;
176 table_bits = NextTableBitSize(count, len, root_bits);
177 table_size = 1 << table_bits;
178 total_size += table_size;
179 low = key & mask;
180 root_table[low].bits = (uint8_t)(table_bits + root_bits);
181 root_table[low].value = (uint16_t)((table - root_table) - low);
182 }
183 code.bits = (uint8_t)(len - root_bits);
184 code.value = (uint16_t)sorted[symbol++];
185 ReplicateValue(&table[key >> root_bits], step, table_size, code);
186 key = GetNextKey(key, len);
187 }
188 }
189
190 // Check if tree is full.
191 if (num_nodes != 2 * offset[MAX_ALLOWED_CODE_LENGTH] - 1) {
192 return 0;
193 }
194 }
195
196 return total_size;
197 }
198
199 // Maximum code_lengths_size is 2328 (reached for 11-bit color_cache_bits).
200 // More commonly, the value is around ~280.
201 #define MAX_CODE_LENGTHS_SIZE \
202 ((1 << MAX_CACHE_BITS) + NUM_LITERAL_CODES + NUM_LENGTH_CODES)
203 // Cut-off value for switching between heap and stack allocation.
204 #define SORTED_SIZE_CUTOFF 512
VP8LBuildHuffmanTable(HuffmanCode * const root_table,int root_bits,const int code_lengths[],int code_lengths_size)205 int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits,
206 const int code_lengths[], int code_lengths_size) {
207 int total_size;
208 assert(code_lengths_size <= MAX_CODE_LENGTHS_SIZE);
209 if (code_lengths_size <= SORTED_SIZE_CUTOFF) {
210 // use local stack-allocated array.
211 uint16_t sorted[SORTED_SIZE_CUTOFF];
212 total_size = BuildHuffmanTable(root_table, root_bits,
213 code_lengths, code_lengths_size, sorted);
214 } else { // rare case. Use heap allocation.
215 uint16_t* const sorted =
216 (uint16_t*)WebPSafeMalloc(code_lengths_size, sizeof(*sorted));
217 if (sorted == NULL) return 0;
218 total_size = BuildHuffmanTable(root_table, root_bits,
219 code_lengths, code_lengths_size, sorted);
220 WebPSafeFree(sorted);
221 }
222 return total_size;
223 }
224