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