src/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 "./huffman.h"
  17 #include "../utils/utils.h"
  18 #include "../webp/format_constants.h"
  19
  20 #if defined(__cplusplus) || defined(c_plusplus)
  21 extern "C" {
  22 #endif
  23
  24 #define NON_EXISTENT_SYMBOL (-1)
  25
  26 static void TreeNodeInit(HuffmanTreeNode* const node) {
  27   node->children_ = -1;   // means: 'unassigned so far'
  28 }
  29
  30 static int NodeIsEmpty(const HuffmanTreeNode* const node) {
  31   return (node->children_ < 0);
  32 }
  33
  34 static int IsFull(const HuffmanTree* const tree) {
  35   return (tree->num_nodes_ == tree->max_nodes_);
  36 }
  37
  38 static void AssignChildren(HuffmanTree* const tree,
  39                            HuffmanTreeNode* const node) {
  40   HuffmanTreeNode* const children = tree->root_ + tree->num_nodes_;
  41   node->children_ = (int)(children - node);
  42   assert(children - node == (int)(children - node));
  43   tree->num_nodes_ += 2;
  44   TreeNodeInit(children + 0);
  45   TreeNodeInit(children + 1);
  46 }
  47
  48 static int TreeInit(HuffmanTree* const tree, int num_leaves) {
  49   assert(tree != NULL);
  50   if (num_leaves == 0) return 0;
  51   // We allocate maximum possible nodes in the tree at once.
  52   // Note that a Huffman tree is a full binary tree; and in a full binary tree
  53   // with L leaves, the total number of nodes N = 2 * L - 1.
  54   tree->max_nodes_ = 2 * num_leaves - 1;
  55   tree->root_ = (HuffmanTreeNode*)WebPSafeMalloc((uint64_t)tree->max_nodes_,
  56                                                  sizeof(*tree->root_));
  57   if (tree->root_ == NULL) return 0;
  58   TreeNodeInit(tree->root_);  // Initialize root.
  59   tree->num_nodes_ = 1;
  60   return 1;
  61 }
  62
  63 void HuffmanTreeRelease(HuffmanTree* const tree) {
  64   if (tree != NULL) {
  65     free(tree->root_);
  66     tree->root_ = NULL;
  67     tree->max_nodes_ = 0;
  68     tree->num_nodes_ = 0;
  69   }
  70 }
  71
  72 int HuffmanCodeLengthsToCodes(const int* const code_lengths,
  73                               int code_lengths_size, int* const huff_codes) {
  74   int symbol;
  75   int code_len;
  76   int code_length_hist[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
  77   int curr_code;
  78   int next_codes[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 };
  79   int max_code_length = 0;
  80
  81   assert(code_lengths != NULL);
  82   assert(code_lengths_size > 0);
  83   assert(huff_codes != NULL);
  84
  85   // Calculate max code length.
  86   for (symbol = 0; symbol < code_lengths_size; ++symbol) {
  87     if (code_lengths[symbol] > max_code_length) {
  88       max_code_length = code_lengths[symbol];
  89     }
  90   }
  91   if (max_code_length > MAX_ALLOWED_CODE_LENGTH) return 0;
  92
  93   // Calculate code length histogram.
  94   for (symbol = 0; symbol < code_lengths_size; ++symbol) {
  95     ++code_length_hist[code_lengths[symbol]];
  96   }
  97   code_length_hist[0] = 0;
  98
  99   // Calculate the initial values of 'next_codes' for each code length.
 100   // next_codes[code_len] denotes the code to be assigned to the next symbol
 101   // of code length 'code_len'.
 102   curr_code = 0;
 103   next_codes[0] = -1;  // Unused, as code length = 0 implies code doesn't exist.
 104   for (code_len = 1; code_len <= max_code_length; ++code_len) {
 105     curr_code = (curr_code + code_length_hist[code_len - 1]) << 1;
 106     next_codes[code_len] = curr_code;
 107   }
 108
 109   // Get symbols.
 110   for (symbol = 0; symbol < code_lengths_size; ++symbol) {
 111     if (code_lengths[symbol] > 0) {
 112       huff_codes[symbol] = next_codes[code_lengths[symbol]]++;
 113     } else {
 114       huff_codes[symbol] = NON_EXISTENT_SYMBOL;
 115     }
 116   }
 117   return 1;
 118 }
 119
 120 static int TreeAddSymbol(HuffmanTree* const tree,
 121                          int symbol, int code, int code_length) {
 122   HuffmanTreeNode* node = tree->root_;
 123   const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_;
 124   while (code_length-- > 0) {
 125     if (node >= max_node) {
 126       return 0;
 127     }
 128     if (NodeIsEmpty(node)) {
 129       if (IsFull(tree)) return 0;    // error: too many symbols.
 130       AssignChildren(tree, node);
 131     } else if (HuffmanTreeNodeIsLeaf(node)) {
 132       return 0;  // leaf is already occupied.
 133     }
 134     node += node->children_ + ((code >> code_length) & 1);
 135   }
 136   if (NodeIsEmpty(node)) {
 137     node->children_ = 0;      // turn newly created node into a leaf.
 138   } else if (!HuffmanTreeNodeIsLeaf(node)) {
 139     return 0;   // trying to assign a symbol to already used code.
 140   }
 141   node->symbol_ = symbol;  // Add symbol in this node.
 142   return 1;
 143 }
 144
 145 int HuffmanTreeBuildImplicit(HuffmanTree* const tree,
 146                              const int* const code_lengths,
 147                              int code_lengths_size) {
 148   int symbol;
 149   int num_symbols = 0;
 150   int root_symbol = 0;
 151
 152   assert(tree != NULL);
 153   assert(code_lengths != NULL);
 154
 155   // Find out number of symbols and the root symbol.
 156   for (symbol = 0; symbol < code_lengths_size; ++symbol) {
 157     if (code_lengths[symbol] > 0) {
 158       // Note: code length = 0 indicates non-existent symbol.
 159       ++num_symbols;
 160       root_symbol = symbol;
 161     }
 162   }
 163
 164   // Initialize the tree. Will fail for num_symbols = 0
 165   if (!TreeInit(tree, num_symbols)) return 0;
 166
 167   // Build tree.
 168   if (num_symbols == 1) {  // Trivial case.
 169     const int max_symbol = code_lengths_size;
 170     if (root_symbol < 0 || root_symbol >= max_symbol) {
 171       HuffmanTreeRelease(tree);
 172       return 0;
 173     }
 174     return TreeAddSymbol(tree, root_symbol, 0, 0);
 175   } else {  // Normal case.
 176     int ok = 0;
 177
 178     // Get Huffman codes from the code lengths.
 179     int* const codes =
 180         (int*)WebPSafeMalloc((uint64_t)code_lengths_size, sizeof(*codes));
 181     if (codes == NULL) goto End;
 182
 183     if (!HuffmanCodeLengthsToCodes(code_lengths, code_lengths_size, codes)) {
 184       goto End;
 185     }
 186
 187     // Add symbols one-by-one.
 188     for (symbol = 0; symbol < code_lengths_size; ++symbol) {
 189       if (code_lengths[symbol] > 0) {
 190         if (!TreeAddSymbol(tree, symbol, codes[symbol], code_lengths[symbol])) {
 191           goto End;
 192         }
 193       }
 194     }
 195     ok = 1;
 196  End:
 197     free(codes);
 198     ok = ok && IsFull(tree);
 199     if (!ok) HuffmanTreeRelease(tree);
 200     return ok;
 201   }
 202 }
 203
 204 int HuffmanTreeBuildExplicit(HuffmanTree* const tree,
 205                              const int* const code_lengths,
 206                              const int* const codes,
 207                              const int* const symbols, int max_symbol,
 208                              int num_symbols) {
 209   int ok = 0;
 210   int i;
 211
 212   assert(tree != NULL);
 213   assert(code_lengths != NULL);
 214   assert(codes != NULL);
 215   assert(symbols != NULL);
 216
 217   // Initialize the tree. Will fail if num_symbols = 0.
 218   if (!TreeInit(tree, num_symbols)) return 0;
 219
 220   // Add symbols one-by-one.
 221   for (i = 0; i < num_symbols; ++i) {
 222     if (codes[i] != NON_EXISTENT_SYMBOL) {
 223       if (symbols[i] < 0 || symbols[i] >= max_symbol) {
 224         goto End;
 225       }
 226       if (!TreeAddSymbol(tree, symbols[i], codes[i], code_lengths[i])) {
 227         goto End;
 228       }
 229     }
 230   }
 231   ok = 1;
 232  End:
 233   ok = ok && IsFull(tree);
 234   if (!ok) HuffmanTreeRelease(tree);
 235   return ok;
 236 }
 237
 238 #if defined(__cplusplus) || defined(c_plusplus)
 239 }    // extern "C"
 240 #endif