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 (at) 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 241
