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 "./huffman_encode.h"
18#include "../utils/utils.h"
19#include "../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.
25static 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.
31static 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).
122static 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
135static 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
165static 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
261static 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
295static 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
326int 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.
356static 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
361static 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.
374static 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
406void VP8LCreateHuffmanTree(uint32_t* const histogram, int tree_depth_limit,
407                           uint8_t* const buf_rle,
408                           HuffmanTree* const huff_tree,
409                           HuffmanTreeCode* const huff_code) {
410  const int num_symbols = huff_code->num_symbols;
411  memset(buf_rle, 0, num_symbols * sizeof(*buf_rle));
412  OptimizeHuffmanForRle(num_symbols, buf_rle, histogram);
413  GenerateOptimalTree(histogram, num_symbols, huff_tree, tree_depth_limit,
414                      huff_code->code_lengths);
415  // Create the actual bit codes for the bit lengths.
416  ConvertBitDepthsToSymbols(huff_code);
417}
418