• Home
  • Line#
  • Scopes#
  • Navigate#
  • Raw
  • Download
1 // Copyright 2011 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 // Author: Jyrki Alakuijala (jyrki@google.com)
11 //
12 // Entropy encoding (Huffman) for webp lossless.
13 
14 #include <assert.h>
15 #include <stdlib.h>
16 #include <string.h>
17 #include "src/utils/huffman_encode_utils.h"
18 #include "src/utils/utils.h"
19 #include "src/webp/format_constants.h"
20 
21 // -----------------------------------------------------------------------------
22 // Util function to optimize the symbol map for RLE coding
23 
24 // Heuristics for selecting the stride ranges to collapse.
ValuesShouldBeCollapsedToStrideAverage(int a,int b)25 static int ValuesShouldBeCollapsedToStrideAverage(int a, int b) {
26   return abs(a - b) < 4;
27 }
28 
29 // Change the population counts in a way that the consequent
30 // Huffman tree compression, especially its RLE-part, give smaller output.
OptimizeHuffmanForRle(int length,uint8_t * const good_for_rle,uint32_t * const counts)31 static void OptimizeHuffmanForRle(int length, uint8_t* const good_for_rle,
32                                   uint32_t* const counts) {
33   // 1) Let's make the Huffman code more compatible with rle encoding.
34   int i;
35   for (; length >= 0; --length) {
36     if (length == 0) {
37       return;  // All zeros.
38     }
39     if (counts[length - 1] != 0) {
40       // Now counts[0..length - 1] does not have trailing zeros.
41       break;
42     }
43   }
44   // 2) Let's mark all population counts that already can be encoded
45   // with an rle code.
46   {
47     // Let's not spoil any of the existing good rle codes.
48     // Mark any seq of 0's that is longer as 5 as a good_for_rle.
49     // Mark any seq of non-0's that is longer as 7 as a good_for_rle.
50     uint32_t symbol = counts[0];
51     int stride = 0;
52     for (i = 0; i < length + 1; ++i) {
53       if (i == length || counts[i] != symbol) {
54         if ((symbol == 0 && stride >= 5) ||
55             (symbol != 0 && stride >= 7)) {
56           int k;
57           for (k = 0; k < stride; ++k) {
58             good_for_rle[i - k - 1] = 1;
59           }
60         }
61         stride = 1;
62         if (i != length) {
63           symbol = counts[i];
64         }
65       } else {
66         ++stride;
67       }
68     }
69   }
70   // 3) Let's replace those population counts that lead to more rle codes.
71   {
72     uint32_t stride = 0;
73     uint32_t limit = counts[0];
74     uint32_t sum = 0;
75     for (i = 0; i < length + 1; ++i) {
76       if (i == length || good_for_rle[i] ||
77           (i != 0 && good_for_rle[i - 1]) ||
78           !ValuesShouldBeCollapsedToStrideAverage(counts[i], limit)) {
79         if (stride >= 4 || (stride >= 3 && sum == 0)) {
80           uint32_t k;
81           // The stride must end, collapse what we have, if we have enough (4).
82           uint32_t count = (sum + stride / 2) / stride;
83           if (count < 1) {
84             count = 1;
85           }
86           if (sum == 0) {
87             // Don't make an all zeros stride to be upgraded to ones.
88             count = 0;
89           }
90           for (k = 0; k < stride; ++k) {
91             // We don't want to change value at counts[i],
92             // that is already belonging to the next stride. Thus - 1.
93             counts[i - k - 1] = count;
94           }
95         }
96         stride = 0;
97         sum = 0;
98         if (i < length - 3) {
99           // All interesting strides have a count of at least 4,
100           // at least when non-zeros.
101           limit = (counts[i] + counts[i + 1] +
102                    counts[i + 2] + counts[i + 3] + 2) / 4;
103         } else if (i < length) {
104           limit = counts[i];
105         } else {
106           limit = 0;
107         }
108       }
109       ++stride;
110       if (i != length) {
111         sum += counts[i];
112         if (stride >= 4) {
113           limit = (sum + stride / 2) / stride;
114         }
115       }
116     }
117   }
118 }
119 
120 // A comparer function for two Huffman trees: sorts first by 'total count'
121 // (more comes first), and then by 'value' (more comes first).
CompareHuffmanTrees(const void * ptr1,const void * ptr2)122 static int CompareHuffmanTrees(const void* ptr1, const void* ptr2) {
123   const HuffmanTree* const t1 = (const HuffmanTree*)ptr1;
124   const HuffmanTree* const t2 = (const HuffmanTree*)ptr2;
125   if (t1->total_count_ > t2->total_count_) {
126     return -1;
127   } else if (t1->total_count_ < t2->total_count_) {
128     return 1;
129   } else {
130     assert(t1->value_ != t2->value_);
131     return (t1->value_ < t2->value_) ? -1 : 1;
132   }
133 }
134 
SetBitDepths(const HuffmanTree * const tree,const HuffmanTree * const pool,uint8_t * const bit_depths,int level)135 static void SetBitDepths(const HuffmanTree* const tree,
136                          const HuffmanTree* const pool,
137                          uint8_t* const bit_depths, int level) {
138   if (tree->pool_index_left_ >= 0) {
139     SetBitDepths(&pool[tree->pool_index_left_], pool, bit_depths, level + 1);
140     SetBitDepths(&pool[tree->pool_index_right_], pool, bit_depths, level + 1);
141   } else {
142     bit_depths[tree->value_] = level;
143   }
144 }
145 
146 // Create an optimal Huffman tree.
147 //
148 // (data,length): population counts.
149 // tree_limit: maximum bit depth (inclusive) of the codes.
150 // bit_depths[]: how many bits are used for the symbol.
151 //
152 // Returns 0 when an error has occurred.
153 //
154 // The catch here is that the tree cannot be arbitrarily deep
155 //
156 // count_limit is the value that is to be faked as the minimum value
157 // and this minimum value is raised until the tree matches the
158 // maximum length requirement.
159 //
160 // This algorithm is not of excellent performance for very long data blocks,
161 // especially when population counts are longer than 2**tree_limit, but
162 // we are not planning to use this with extremely long blocks.
163 //
164 // See http://en.wikipedia.org/wiki/Huffman_coding
GenerateOptimalTree(const uint32_t * const histogram,int histogram_size,HuffmanTree * tree,int tree_depth_limit,uint8_t * const bit_depths)165 static void GenerateOptimalTree(const uint32_t* const histogram,
166                                 int histogram_size,
167                                 HuffmanTree* tree, int tree_depth_limit,
168                                 uint8_t* const bit_depths) {
169   uint32_t count_min;
170   HuffmanTree* tree_pool;
171   int tree_size_orig = 0;
172   int i;
173 
174   for (i = 0; i < histogram_size; ++i) {
175     if (histogram[i] != 0) {
176       ++tree_size_orig;
177     }
178   }
179 
180   if (tree_size_orig == 0) {   // pretty optimal already!
181     return;
182   }
183 
184   tree_pool = tree + tree_size_orig;
185 
186   // For block sizes with less than 64k symbols we never need to do a
187   // second iteration of this loop.
188   // If we actually start running inside this loop a lot, we would perhaps
189   // be better off with the Katajainen algorithm.
190   assert(tree_size_orig <= (1 << (tree_depth_limit - 1)));
191   for (count_min = 1; ; count_min *= 2) {
192     int tree_size = tree_size_orig;
193     // We need to pack the Huffman tree in tree_depth_limit bits.
194     // So, we try by faking histogram entries to be at least 'count_min'.
195     int idx = 0;
196     int j;
197     for (j = 0; j < histogram_size; ++j) {
198       if (histogram[j] != 0) {
199         const uint32_t count =
200             (histogram[j] < count_min) ? count_min : histogram[j];
201         tree[idx].total_count_ = count;
202         tree[idx].value_ = j;
203         tree[idx].pool_index_left_ = -1;
204         tree[idx].pool_index_right_ = -1;
205         ++idx;
206       }
207     }
208 
209     // Build the Huffman tree.
210     qsort(tree, tree_size, sizeof(*tree), CompareHuffmanTrees);
211 
212     if (tree_size > 1) {  // Normal case.
213       int tree_pool_size = 0;
214       while (tree_size > 1) {  // Finish when we have only one root.
215         uint32_t count;
216         tree_pool[tree_pool_size++] = tree[tree_size - 1];
217         tree_pool[tree_pool_size++] = tree[tree_size - 2];
218         count = tree_pool[tree_pool_size - 1].total_count_ +
219                 tree_pool[tree_pool_size - 2].total_count_;
220         tree_size -= 2;
221         {
222           // Search for the insertion point.
223           int k;
224           for (k = 0; k < tree_size; ++k) {
225             if (tree[k].total_count_ <= count) {
226               break;
227             }
228           }
229           memmove(tree + (k + 1), tree + k, (tree_size - k) * sizeof(*tree));
230           tree[k].total_count_ = count;
231           tree[k].value_ = -1;
232 
233           tree[k].pool_index_left_ = tree_pool_size - 1;
234           tree[k].pool_index_right_ = tree_pool_size - 2;
235           tree_size = tree_size + 1;
236         }
237       }
238       SetBitDepths(&tree[0], tree_pool, bit_depths, 0);
239     } else if (tree_size == 1) {  // Trivial case: only one element.
240       bit_depths[tree[0].value_] = 1;
241     }
242 
243     {
244       // Test if this Huffman tree satisfies our 'tree_depth_limit' criteria.
245       int max_depth = bit_depths[0];
246       for (j = 1; j < histogram_size; ++j) {
247         if (max_depth < bit_depths[j]) {
248           max_depth = bit_depths[j];
249         }
250       }
251       if (max_depth <= tree_depth_limit) {
252         break;
253       }
254     }
255   }
256 }
257 
258 // -----------------------------------------------------------------------------
259 // Coding of the Huffman tree values
260 
CodeRepeatedValues(int repetitions,HuffmanTreeToken * tokens,int value,int prev_value)261 static HuffmanTreeToken* CodeRepeatedValues(int repetitions,
262                                             HuffmanTreeToken* tokens,
263                                             int value, int prev_value) {
264   assert(value <= MAX_ALLOWED_CODE_LENGTH);
265   if (value != prev_value) {
266     tokens->code = value;
267     tokens->extra_bits = 0;
268     ++tokens;
269     --repetitions;
270   }
271   while (repetitions >= 1) {
272     if (repetitions < 3) {
273       int i;
274       for (i = 0; i < repetitions; ++i) {
275         tokens->code = value;
276         tokens->extra_bits = 0;
277         ++tokens;
278       }
279       break;
280     } else if (repetitions < 7) {
281       tokens->code = 16;
282       tokens->extra_bits = repetitions - 3;
283       ++tokens;
284       break;
285     } else {
286       tokens->code = 16;
287       tokens->extra_bits = 3;
288       ++tokens;
289       repetitions -= 6;
290     }
291   }
292   return tokens;
293 }
294 
CodeRepeatedZeros(int repetitions,HuffmanTreeToken * tokens)295 static HuffmanTreeToken* CodeRepeatedZeros(int repetitions,
296                                            HuffmanTreeToken* tokens) {
297   while (repetitions >= 1) {
298     if (repetitions < 3) {
299       int i;
300       for (i = 0; i < repetitions; ++i) {
301         tokens->code = 0;   // 0-value
302         tokens->extra_bits = 0;
303         ++tokens;
304       }
305       break;
306     } else if (repetitions < 11) {
307       tokens->code = 17;
308       tokens->extra_bits = repetitions - 3;
309       ++tokens;
310       break;
311     } else if (repetitions < 139) {
312       tokens->code = 18;
313       tokens->extra_bits = repetitions - 11;
314       ++tokens;
315       break;
316     } else {
317       tokens->code = 18;
318       tokens->extra_bits = 0x7f;  // 138 repeated 0s
319       ++tokens;
320       repetitions -= 138;
321     }
322   }
323   return tokens;
324 }
325 
VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode * const tree,HuffmanTreeToken * tokens,int max_tokens)326 int VP8LCreateCompressedHuffmanTree(const HuffmanTreeCode* const tree,
327                                     HuffmanTreeToken* tokens, int max_tokens) {
328   HuffmanTreeToken* const starting_token = tokens;
329   HuffmanTreeToken* const ending_token = tokens + max_tokens;
330   const int depth_size = tree->num_symbols;
331   int prev_value = 8;  // 8 is the initial value for rle.
332   int i = 0;
333   assert(tokens != NULL);
334   while (i < depth_size) {
335     const int value = tree->code_lengths[i];
336     int k = i + 1;
337     int runs;
338     while (k < depth_size && tree->code_lengths[k] == value) ++k;
339     runs = k - i;
340     if (value == 0) {
341       tokens = CodeRepeatedZeros(runs, tokens);
342     } else {
343       tokens = CodeRepeatedValues(runs, tokens, value, prev_value);
344       prev_value = value;
345     }
346     i += runs;
347     assert(tokens <= ending_token);
348   }
349   (void)ending_token;    // suppress 'unused variable' warning
350   return (int)(tokens - starting_token);
351 }
352 
353 // -----------------------------------------------------------------------------
354 
355 // Pre-reversed 4-bit values.
356 static const uint8_t kReversedBits[16] = {
357   0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
358   0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf
359 };
360 
ReverseBits(int num_bits,uint32_t bits)361 static uint32_t ReverseBits(int num_bits, uint32_t bits) {
362   uint32_t retval = 0;
363   int i = 0;
364   while (i < num_bits) {
365     i += 4;
366     retval |= kReversedBits[bits & 0xf] << (MAX_ALLOWED_CODE_LENGTH + 1 - i);
367     bits >>= 4;
368   }
369   retval >>= (MAX_ALLOWED_CODE_LENGTH + 1 - num_bits);
370   return retval;
371 }
372 
373 // Get the actual bit values for a tree of bit depths.
ConvertBitDepthsToSymbols(HuffmanTreeCode * const tree)374 static void ConvertBitDepthsToSymbols(HuffmanTreeCode* const tree) {
375   // 0 bit-depth means that the symbol does not exist.
376   int i;
377   int len;
378   uint32_t next_code[MAX_ALLOWED_CODE_LENGTH + 1];
379   int depth_count[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
380 
381   assert(tree != NULL);
382   len = tree->num_symbols;
383   for (i = 0; i < len; ++i) {
384     const int code_length = tree->code_lengths[i];
385     assert(code_length <= MAX_ALLOWED_CODE_LENGTH);
386     ++depth_count[code_length];
387   }
388   depth_count[0] = 0;  // ignore unused symbol
389   next_code[0] = 0;
390   {
391     uint32_t code = 0;
392     for (i = 1; i <= MAX_ALLOWED_CODE_LENGTH; ++i) {
393       code = (code + depth_count[i - 1]) << 1;
394       next_code[i] = code;
395     }
396   }
397   for (i = 0; i < len; ++i) {
398     const int code_length = tree->code_lengths[i];
399     tree->codes[i] = ReverseBits(code_length, next_code[code_length]++);
400   }
401 }
402 
403 // -----------------------------------------------------------------------------
404 // Main entry point
405 
VP8LCreateHuffmanTree(uint32_t * const histogram,int tree_depth_limit,uint8_t * const buf_rle,HuffmanTree * const huff_tree,HuffmanTreeCode * const huff_code)406 void VP8LCreateHuffmanTree(uint32_t* const histogram, int tree_depth_limit,
407                            uint8_t* const buf_rle, HuffmanTree* const huff_tree,
408                            HuffmanTreeCode* const huff_code) {
409   const int num_symbols = huff_code->num_symbols;
410   memset(buf_rle, 0, num_symbols * sizeof(*buf_rle));
411   OptimizeHuffmanForRle(num_symbols, buf_rle, histogram);
412   GenerateOptimalTree(histogram, num_symbols, huff_tree, tree_depth_limit,
413                       huff_code->code_lengths);
414   // Create the actual bit codes for the bit lengths.
415   ConvertBitDepthsToSymbols(huff_code);
416 }
417