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 "./huffman.h"
18#include "../utils/utils.h"
19#include "../webp/format_constants.h"
20
21// Uncomment the following to use look-up table for ReverseBits()
22// (might be faster on some platform)
23// #define USE_LUT_REVERSE_BITS
24
25// Huffman data read via DecodeImageStream is represented in two (red and green)
26// bytes.
27#define MAX_HTREE_GROUPS    0x10000
28#define NON_EXISTENT_SYMBOL (-1)
29
30static void TreeNodeInit(HuffmanTreeNode* const node) {
31  node->children_ = -1;   // means: 'unassigned so far'
32}
33
34static int NodeIsEmpty(const HuffmanTreeNode* const node) {
35  return (node->children_ < 0);
36}
37
38static int IsFull(const HuffmanTree* const tree) {
39  return (tree->num_nodes_ == tree->max_nodes_);
40}
41
42static void AssignChildren(HuffmanTree* const tree,
43                           HuffmanTreeNode* const node) {
44  HuffmanTreeNode* const children = tree->root_ + tree->num_nodes_;
45  node->children_ = (int)(children - node);
46  assert(children - node == (int)(children - node));
47  tree->num_nodes_ += 2;
48  TreeNodeInit(children + 0);
49  TreeNodeInit(children + 1);
50}
51
52// A Huffman tree is a full binary tree; and in a full binary tree with L
53// leaves, the total number of nodes N = 2 * L - 1.
54static int HuffmanTreeMaxNodes(int num_leaves) {
55  return (2 * num_leaves - 1);
56}
57
58static int HuffmanTreeAllocate(HuffmanTree* const tree, int num_nodes) {
59  assert(tree != NULL);
60  tree->root_ =
61      (HuffmanTreeNode*)WebPSafeMalloc(num_nodes, sizeof(*tree->root_));
62  return (tree->root_ != NULL);
63}
64
65static int TreeInit(HuffmanTree* const tree, int num_leaves) {
66  assert(tree != NULL);
67  if (num_leaves == 0) return 0;
68  tree->max_nodes_ = HuffmanTreeMaxNodes(num_leaves);
69  assert(tree->max_nodes_ < (1 << 16));   // limit for the lut_jump_ table
70  if (!HuffmanTreeAllocate(tree, tree->max_nodes_)) return 0;
71  TreeNodeInit(tree->root_);  // Initialize root.
72  tree->num_nodes_ = 1;
73  memset(tree->lut_bits_, 255, sizeof(tree->lut_bits_));
74  memset(tree->lut_jump_, 0, sizeof(tree->lut_jump_));
75  return 1;
76}
77
78void VP8LHuffmanTreeFree(HuffmanTree* const tree) {
79  if (tree != NULL) {
80    WebPSafeFree(tree->root_);
81    tree->root_ = NULL;
82    tree->max_nodes_ = 0;
83    tree->num_nodes_ = 0;
84  }
85}
86
87HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) {
88  HTreeGroup* const htree_groups =
89      (HTreeGroup*)WebPSafeCalloc(num_htree_groups, sizeof(*htree_groups));
90  assert(num_htree_groups <= MAX_HTREE_GROUPS);
91  if (htree_groups == NULL) {
92    return NULL;
93  }
94  return htree_groups;
95}
96
97void VP8LHtreeGroupsFree(HTreeGroup* htree_groups, int num_htree_groups) {
98  if (htree_groups != NULL) {
99    int i, j;
100    for (i = 0; i < num_htree_groups; ++i) {
101      HuffmanTree* const htrees = htree_groups[i].htrees_;
102      for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) {
103        VP8LHuffmanTreeFree(&htrees[j]);
104      }
105    }
106    WebPSafeFree(htree_groups);
107  }
108}
109
110int VP8LHuffmanCodeLengthsToCodes(
111    const int* const code_lengths, int code_lengths_size,
112    int* const huff_codes) {
113  int symbol;
114  int code_len;
115  int code_length_hist[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
116  int curr_code;
117  int next_codes[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
118  int max_code_length = 0;
119
120  assert(code_lengths != NULL);
121  assert(code_lengths_size > 0);
122  assert(huff_codes != NULL);
123
124  // Calculate max code length.
125  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
126    if (code_lengths[symbol] > max_code_length) {
127      max_code_length = code_lengths[symbol];
128    }
129  }
130  if (max_code_length > MAX_ALLOWED_CODE_LENGTH) return 0;
131
132  // Calculate code length histogram.
133  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
134    ++code_length_hist[code_lengths[symbol]];
135  }
136  code_length_hist[0] = 0;
137
138  // Calculate the initial values of 'next_codes' for each code length.
139  // next_codes[code_len] denotes the code to be assigned to the next symbol
140  // of code length 'code_len'.
141  curr_code = 0;
142  next_codes[0] = -1;  // Unused, as code length = 0 implies code doesn't exist.
143  for (code_len = 1; code_len <= max_code_length; ++code_len) {
144    curr_code = (curr_code + code_length_hist[code_len - 1]) << 1;
145    next_codes[code_len] = curr_code;
146  }
147
148  // Get symbols.
149  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
150    if (code_lengths[symbol] > 0) {
151      huff_codes[symbol] = next_codes[code_lengths[symbol]]++;
152    } else {
153      huff_codes[symbol] = NON_EXISTENT_SYMBOL;
154    }
155  }
156  return 1;
157}
158
159#ifndef USE_LUT_REVERSE_BITS
160
161static int ReverseBitsShort(int bits, int num_bits) {
162  int retval = 0;
163  int i;
164  assert(num_bits <= 8);   // Not a hard requirement, just for coherency.
165  for (i = 0; i < num_bits; ++i) {
166    retval <<= 1;
167    retval |= bits & 1;
168    bits >>= 1;
169  }
170  return retval;
171}
172
173#else
174
175static const uint8_t kReversedBits[16] = {  // Pre-reversed 4-bit values.
176  0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe,
177  0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf
178};
179
180static int ReverseBitsShort(int bits, int num_bits) {
181  const uint8_t v = (kReversedBits[bits & 0xf] << 4) | kReversedBits[bits >> 4];
182  assert(num_bits <= 8);
183  return v >> (8 - num_bits);
184}
185
186#endif
187
188static int TreeAddSymbol(HuffmanTree* const tree,
189                         int symbol, int code, int code_length) {
190  int step = HUFF_LUT_BITS;
191  int base_code;
192  HuffmanTreeNode* node = tree->root_;
193  const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_;
194  assert(symbol == (int16_t)symbol);
195  if (code_length <= HUFF_LUT_BITS) {
196    int i;
197    base_code = ReverseBitsShort(code, code_length);
198    for (i = 0; i < (1 << (HUFF_LUT_BITS - code_length)); ++i) {
199      const int idx = base_code | (i << code_length);
200      tree->lut_symbol_[idx] = (int16_t)symbol;
201      tree->lut_bits_[idx] = code_length;
202    }
203  } else {
204    base_code = ReverseBitsShort((code >> (code_length - HUFF_LUT_BITS)),
205                                 HUFF_LUT_BITS);
206  }
207  while (code_length-- > 0) {
208    if (node >= max_node) {
209      return 0;
210    }
211    if (NodeIsEmpty(node)) {
212      if (IsFull(tree)) return 0;    // error: too many symbols.
213      AssignChildren(tree, node);
214    } else if (!HuffmanTreeNodeIsNotLeaf(node)) {
215      return 0;  // leaf is already occupied.
216    }
217    node += node->children_ + ((code >> code_length) & 1);
218    if (--step == 0) {
219      tree->lut_jump_[base_code] = (int16_t)(node - tree->root_);
220    }
221  }
222  if (NodeIsEmpty(node)) {
223    node->children_ = 0;      // turn newly created node into a leaf.
224  } else if (HuffmanTreeNodeIsNotLeaf(node)) {
225    return 0;   // trying to assign a symbol to already used code.
226  }
227  node->symbol_ = symbol;  // Add symbol in this node.
228  return 1;
229}
230
231int VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree,
232                                 const int* const code_lengths,
233                                 int* const codes,
234                                 int code_lengths_size) {
235  int symbol;
236  int num_symbols = 0;
237  int root_symbol = 0;
238
239  assert(tree != NULL);
240  assert(code_lengths != NULL);
241
242  // Find out number of symbols and the root symbol.
243  for (symbol = 0; symbol < code_lengths_size; ++symbol) {
244    if (code_lengths[symbol] > 0) {
245      // Note: code length = 0 indicates non-existent symbol.
246      ++num_symbols;
247      root_symbol = symbol;
248    }
249  }
250
251  // Initialize the tree. Will fail for num_symbols = 0
252  if (!TreeInit(tree, num_symbols)) return 0;
253
254  // Build tree.
255  if (num_symbols == 1) {  // Trivial case.
256    const int max_symbol = code_lengths_size;
257    if (root_symbol < 0 || root_symbol >= max_symbol) {
258      VP8LHuffmanTreeFree(tree);
259      return 0;
260    }
261    return TreeAddSymbol(tree, root_symbol, 0, 0);
262  } else {  // Normal case.
263    int ok = 0;
264    memset(codes, 0, code_lengths_size * sizeof(*codes));
265
266    if (!VP8LHuffmanCodeLengthsToCodes(code_lengths, code_lengths_size,
267                                       codes)) {
268      goto End;
269    }
270
271    // Add symbols one-by-one.
272    for (symbol = 0; symbol < code_lengths_size; ++symbol) {
273      if (code_lengths[symbol] > 0) {
274        if (!TreeAddSymbol(tree, symbol, codes[symbol],
275                           code_lengths[symbol])) {
276          goto End;
277        }
278      }
279    }
280    ok = 1;
281 End:
282    ok = ok && IsFull(tree);
283    if (!ok) VP8LHuffmanTreeFree(tree);
284    return ok;
285  }
286}
287
288int VP8LHuffmanTreeBuildExplicit(HuffmanTree* const tree,
289                                 const int* const code_lengths,
290                                 const int* const codes,
291                                 const int* const symbols, int max_symbol,
292                                 int num_symbols) {
293  int ok = 0;
294  int i;
295  assert(tree != NULL);
296  assert(code_lengths != NULL);
297  assert(codes != NULL);
298  assert(symbols != NULL);
299
300  // Initialize the tree. Will fail if num_symbols = 0.
301  if (!TreeInit(tree, num_symbols)) return 0;
302
303  // Add symbols one-by-one.
304  for (i = 0; i < num_symbols; ++i) {
305    if (codes[i] != NON_EXISTENT_SYMBOL) {
306      if (symbols[i] < 0 || symbols[i] >= max_symbol) {
307        goto End;
308      }
309      if (!TreeAddSymbol(tree, symbols[i], codes[i], code_lengths[i])) {
310        goto End;
311      }
312    }
313  }
314  ok = 1;
315 End:
316  ok = ok && IsFull(tree);
317  if (!ok) VP8LHuffmanTreeFree(tree);
318  return ok;
319}
320