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 <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 } 320
