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 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 
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.
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.
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
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.
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
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