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 // 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
  30 static void TreeNodeInit(HuffmanTreeNode* const node) {
  31   node->children_ = -1;   // means: 'unassigned so far'
  32 }
  33
  34 static int NodeIsEmpty(const HuffmanTreeNode* const node) {
  35   return (node->children_ < 0);
  36 }
  37
  38 static int IsFull(const HuffmanTree* const tree) {
  39   return (tree->num_nodes_ == tree->max_nodes_);
  40 }
  41
  42 static 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.
  54 static int HuffmanTreeMaxNodes(int num_leaves) {
  55   return (2 * num_leaves - 1);
  56 }
  57
  58 static 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
  65 static 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
  78 void 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
  87 HTreeGroup* 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
  97 void 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
 110 int 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
 161 static 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
 175 static 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
 180 static 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
 188 static 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
 231 int 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
 288 int 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 }