src/SDL2/external/libwebp-0.3.0/src/utils/huffman.c

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