third_party/libwebp/utils/huffman.c

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