1a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Copyright 2012 Google Inc. All Rights Reserved. 2a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 30406ce1417f76f2034833414dcecc9f56253640cVikas Arora// Use of this source code is governed by a BSD-style license 40406ce1417f76f2034833414dcecc9f56253640cVikas Arora// that can be found in the COPYING file in the root of the source 50406ce1417f76f2034833414dcecc9f56253640cVikas Arora// tree. An additional intellectual property rights grant can be found 60406ce1417f76f2034833414dcecc9f56253640cVikas Arora// in the file PATENTS. All contributing project authors may 70406ce1417f76f2034833414dcecc9f56253640cVikas Arora// be found in the AUTHORS file in the root of the source tree. 8a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// ----------------------------------------------------------------------------- 9a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 10a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Utilities for building and looking up Huffman trees. 11a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// 12a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora// Author: Urvang Joshi (urvang@google.com) 13a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 14a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <assert.h> 15a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include <stdlib.h> 168b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#include <string.h> 17a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "./huffman.h" 18a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "../utils/utils.h" 19a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#include "webp/format_constants.h" 20a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 218b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// Uncomment the following to use look-up table for ReverseBits() 228b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// (might be faster on some platform) 238b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora// #define USE_LUT_REVERSE_BITS 24a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 25af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora// Huffman data read via DecodeImageStream is represented in two (red and green) 26af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora// bytes. 27af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora#define MAX_HTREE_GROUPS 0x10000 28a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora#define NON_EXISTENT_SYMBOL (-1) 29a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 30a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void TreeNodeInit(HuffmanTreeNode* const node) { 31a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora node->children_ = -1; // means: 'unassigned so far' 32a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 33a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 34a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int NodeIsEmpty(const HuffmanTreeNode* const node) { 35a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return (node->children_ < 0); 36a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 37a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 38a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int IsFull(const HuffmanTree* const tree) { 39a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return (tree->num_nodes_ == tree->max_nodes_); 40a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 41a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 42a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic void AssignChildren(HuffmanTree* const tree, 43a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeNode* const node) { 44a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeNode* const children = tree->root_ + tree->num_nodes_; 45a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora node->children_ = (int)(children - node); 46a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(children - node == (int)(children - node)); 47a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree->num_nodes_ += 2; 48a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora TreeNodeInit(children + 0); 49a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora TreeNodeInit(children + 1); 50a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 51a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 52af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora// A Huffman tree is a full binary tree; and in a full binary tree with L 53af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora// leaves, the total number of nodes N = 2 * L - 1. 54af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic int HuffmanTreeMaxNodes(int num_leaves) { 55af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return (2 * num_leaves - 1); 56af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora} 57af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 58af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arorastatic int HuffmanTreeAllocate(HuffmanTree* const tree, int num_nodes) { 59af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora assert(tree != NULL); 60af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora tree->root_ = 61af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (HuffmanTreeNode*)WebPSafeMalloc(num_nodes, sizeof(*tree->root_)); 62af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return (tree->root_ != NULL); 63af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora} 64af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 65a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int TreeInit(HuffmanTree* const tree, int num_leaves) { 66a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tree != NULL); 67a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (num_leaves == 0) return 0; 68af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora tree->max_nodes_ = HuffmanTreeMaxNodes(num_leaves); 698b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora assert(tree->max_nodes_ < (1 << 16)); // limit for the lut_jump_ table 70af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!HuffmanTreeAllocate(tree, tree->max_nodes_)) return 0; 71a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora TreeNodeInit(tree->root_); // Initialize root. 72a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree->num_nodes_ = 1; 738b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora memset(tree->lut_bits_, 255, sizeof(tree->lut_bits_)); 748b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora memset(tree->lut_jump_, 0, sizeof(tree->lut_jump_)); 75a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 76a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 77a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 78af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Aroravoid VP8LHuffmanTreeFree(HuffmanTree* const tree) { 79a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (tree != NULL) { 80af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(tree->root_); 81a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree->root_ = NULL; 82a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree->max_nodes_ = 0; 83a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora tree->num_nodes_ = 0; 84a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 85a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 86a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 87af51b94a435132e9014c324e25fb686b3d07a8c8Vikas AroraHTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups) { 88af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HTreeGroup* const htree_groups = 89af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora (HTreeGroup*)WebPSafeCalloc(num_htree_groups, sizeof(*htree_groups)); 90af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora assert(num_htree_groups <= MAX_HTREE_GROUPS); 91af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (htree_groups == NULL) { 92af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return NULL; 93af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 94af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora return htree_groups; 95af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora} 96af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 97af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Aroravoid VP8LHtreeGroupsFree(HTreeGroup* htree_groups, int num_htree_groups) { 98af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (htree_groups != NULL) { 99af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int i, j; 100af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora for (i = 0; i < num_htree_groups; ++i) { 101af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora HuffmanTree* const htrees = htree_groups[i].htrees_; 102af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora for (j = 0; j < HUFFMAN_CODES_PER_META_CODE; ++j) { 103af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHuffmanTreeFree(&htrees[j]); 104af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 105af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 106af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora WebPSafeFree(htree_groups); 107af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora } 108af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora} 109af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora 110af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Aroraint VP8LHuffmanCodeLengthsToCodes( 111af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int* const code_lengths, int code_lengths_size, 112af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int* const huff_codes) { 113a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int symbol; 114a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int code_len; 115a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int code_length_hist[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; 116a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int curr_code; 117a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int next_codes[MAX_ALLOWED_CODE_LENGTH + 1] = { 0 }; 118a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int max_code_length = 0; 119a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 120a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(code_lengths != NULL); 121a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(code_lengths_size > 0); 122a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(huff_codes != NULL); 123a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 124a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Calculate max code length. 125a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (symbol = 0; symbol < code_lengths_size; ++symbol) { 126a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (code_lengths[symbol] > max_code_length) { 127a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora max_code_length = code_lengths[symbol]; 128a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 129a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 130a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (max_code_length > MAX_ALLOWED_CODE_LENGTH) return 0; 131a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 132a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Calculate code length histogram. 133a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (symbol = 0; symbol < code_lengths_size; ++symbol) { 134a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++code_length_hist[code_lengths[symbol]]; 135a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 136a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora code_length_hist[0] = 0; 137a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 138a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Calculate the initial values of 'next_codes' for each code length. 139a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // next_codes[code_len] denotes the code to be assigned to the next symbol 140a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // of code length 'code_len'. 141a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora curr_code = 0; 142a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora next_codes[0] = -1; // Unused, as code length = 0 implies code doesn't exist. 143a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (code_len = 1; code_len <= max_code_length; ++code_len) { 144a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora curr_code = (curr_code + code_length_hist[code_len - 1]) << 1; 145a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora next_codes[code_len] = curr_code; 146a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 147a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 148a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Get symbols. 149a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (symbol = 0; symbol < code_lengths_size; ++symbol) { 150a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (code_lengths[symbol] > 0) { 151a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huff_codes[symbol] = next_codes[code_lengths[symbol]]++; 152a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { 153a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora huff_codes[symbol] = NON_EXISTENT_SYMBOL; 154a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 155a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 156a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 157a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 158a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 1598b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#ifndef USE_LUT_REVERSE_BITS 1608b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 1618b720228d581a84fd173b6dcb2fa295b59db489aVikas Arorastatic int ReverseBitsShort(int bits, int num_bits) { 1628b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int retval = 0; 1638b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int i; 1648b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora assert(num_bits <= 8); // Not a hard requirement, just for coherency. 1658b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora for (i = 0; i < num_bits; ++i) { 1668b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora retval <<= 1; 1678b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora retval |= bits & 1; 1688b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora bits >>= 1; 1698b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora } 1708b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora return retval; 1718b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora} 1728b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 1738b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#else 1748b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 1758b720228d581a84fd173b6dcb2fa295b59db489aVikas Arorastatic const uint8_t kReversedBits[16] = { // Pre-reversed 4-bit values. 1768b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 0x0, 0x8, 0x4, 0xc, 0x2, 0xa, 0x6, 0xe, 1778b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 0x1, 0x9, 0x5, 0xd, 0x3, 0xb, 0x7, 0xf 1788b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora}; 1798b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 1808b720228d581a84fd173b6dcb2fa295b59db489aVikas Arorastatic int ReverseBitsShort(int bits, int num_bits) { 1818b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora const uint8_t v = (kReversedBits[bits & 0xf] << 4) | kReversedBits[bits >> 4]; 1828b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora assert(num_bits <= 8); 1838b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora return v >> (8 - num_bits); 1848b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora} 1858b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 1868b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora#endif 1878b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora 188a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arorastatic int TreeAddSymbol(HuffmanTree* const tree, 189a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int symbol, int code, int code_length) { 1908b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int step = HUFF_LUT_BITS; 1918b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int base_code; 192a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora HuffmanTreeNode* node = tree->root_; 193a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_; 1948b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora assert(symbol == (int16_t)symbol); 1958b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora if (code_length <= HUFF_LUT_BITS) { 1968b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora int i; 1978b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora base_code = ReverseBitsShort(code, code_length); 1988b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora for (i = 0; i < (1 << (HUFF_LUT_BITS - code_length)); ++i) { 1998b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora const int idx = base_code | (i << code_length); 2008b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora tree->lut_symbol_[idx] = (int16_t)symbol; 2018b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora tree->lut_bits_[idx] = code_length; 2028b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora } 2038b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora } else { 2048b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora base_code = ReverseBitsShort((code >> (code_length - HUFF_LUT_BITS)), 2058b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora HUFF_LUT_BITS); 2068b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora } 207a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora while (code_length-- > 0) { 208a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (node >= max_node) { 209a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 210a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 211a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (NodeIsEmpty(node)) { 212a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (IsFull(tree)) return 0; // error: too many symbols. 213a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora AssignChildren(tree, node); 2148b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora } else if (!HuffmanTreeNodeIsNotLeaf(node)) { 215a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; // leaf is already occupied. 216a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 217a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora node += node->children_ + ((code >> code_length) & 1); 2188b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora if (--step == 0) { 2198b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora tree->lut_jump_[base_code] = (int16_t)(node - tree->root_); 2208b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora } 221a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 222a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (NodeIsEmpty(node)) { 223a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora node->children_ = 0; // turn newly created node into a leaf. 2248b720228d581a84fd173b6dcb2fa295b59db489aVikas Arora } else if (HuffmanTreeNodeIsNotLeaf(node)) { 225a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; // trying to assign a symbol to already used code. 226a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 227a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora node->symbol_ = symbol; // Add symbol in this node. 228a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 1; 229a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 230a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 231af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Aroraint VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree, 232af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int* const code_lengths, 233af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int* const codes, 234af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int code_lengths_size) { 235a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int symbol; 236a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int num_symbols = 0; 237a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int root_symbol = 0; 238a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 239a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tree != NULL); 240a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(code_lengths != NULL); 241a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 242a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Find out number of symbols and the root symbol. 243a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (symbol = 0; symbol < code_lengths_size; ++symbol) { 244a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (code_lengths[symbol] > 0) { 245a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Note: code length = 0 indicates non-existent symbol. 246a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ++num_symbols; 247a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora root_symbol = symbol; 248a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 249a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 250a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 251a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Initialize the tree. Will fail for num_symbols = 0 252a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!TreeInit(tree, num_symbols)) return 0; 253a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 254a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Build tree. 255a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (num_symbols == 1) { // Trivial case. 256a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora const int max_symbol = code_lengths_size; 257a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (root_symbol < 0 || root_symbol >= max_symbol) { 258af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora VP8LHuffmanTreeFree(tree); 259a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return 0; 260a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 261a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return TreeAddSymbol(tree, root_symbol, 0, 0); 262a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } else { // Normal case. 263a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int ok = 0; 264af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora memset(codes, 0, code_lengths_size * sizeof(*codes)); 265a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 266af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!VP8LHuffmanCodeLengthsToCodes(code_lengths, code_lengths_size, 267af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora codes)) { 268a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto End; 269a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 270a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 271a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Add symbols one-by-one. 272a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (symbol = 0; symbol < code_lengths_size; ++symbol) { 273a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (code_lengths[symbol] > 0) { 274af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!TreeAddSymbol(tree, symbol, codes[symbol], 275af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora code_lengths[symbol])) { 276a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto End; 277a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 278a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 279a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 280a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ok = 1; 281a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora End: 282a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ok = ok && IsFull(tree); 283af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!ok) VP8LHuffmanTreeFree(tree); 284a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return ok; 285a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 286a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 287a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 288af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Aroraint VP8LHuffmanTreeBuildExplicit(HuffmanTree* const tree, 289af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int* const code_lengths, 290af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int* const codes, 291af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora const int* const symbols, int max_symbol, 292af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora int num_symbols) { 293a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int ok = 0; 294a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora int i; 295a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(tree != NULL); 296a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(code_lengths != NULL); 297a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(codes != NULL); 298a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora assert(symbols != NULL); 299a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 300a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Initialize the tree. Will fail if num_symbols = 0. 301a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!TreeInit(tree, num_symbols)) return 0; 302a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora 303a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora // Add symbols one-by-one. 304a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora for (i = 0; i < num_symbols; ++i) { 305a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (codes[i] != NON_EXISTENT_SYMBOL) { 306a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (symbols[i] < 0 || symbols[i] >= max_symbol) { 307a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto End; 308a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 309a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora if (!TreeAddSymbol(tree, symbols[i], codes[i], code_lengths[i])) { 310a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora goto End; 311a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 312a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 313a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora } 314a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ok = 1; 315a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora End: 316a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora ok = ok && IsFull(tree); 317af51b94a435132e9014c324e25fb686b3d07a8c8Vikas Arora if (!ok) VP8LHuffmanTreeFree(tree); 318a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora return ok; 319a2415724fb3466168b2af5b08bd94ba732c0e753Vikas Arora} 320