38 static int IsFull(const HuffmanTree* const tree) {  in IsFull()  argument
39   return (tree->num_nodes_ == tree->max_nodes_);  in IsFull()
42 static void AssignChildren(HuffmanTree* const tree,  in AssignChildren()  argument
44   HuffmanTreeNode* const children = tree->root_ + tree->num_nodes_;  in AssignChildren()
47   tree->num_nodes_ += 2;  in AssignChildren()
58 static int HuffmanTreeAllocate(HuffmanTree* const tree, int num_nodes) {  in HuffmanTreeAllocate()  argument
59   assert(tree != NULL);  in HuffmanTreeAllocate()
60   tree->root_ =  in HuffmanTreeAllocate()
61       (HuffmanTreeNode*)WebPSafeMalloc(num_nodes, sizeof(*tree->root_));  in HuffmanTreeAllocate()
62   return (tree->root_ != NULL);  in HuffmanTreeAllocate()
65 static int TreeInit(HuffmanTree* const tree, int num_leaves) {  in TreeInit()  argument
66   assert(tree != NULL);  in TreeInit()
68   tree->max_nodes_ = HuffmanTreeMaxNodes(num_leaves);  in TreeInit()
69   assert(tree->max_nodes_ < (1 << 16));   // limit for the lut_jump_ table  in TreeInit()
70   if (!HuffmanTreeAllocate(tree, tree->max_nodes_)) return 0;  in TreeInit()
71   TreeNodeInit(tree->root_);  // Initialize root.  in TreeInit()
72   tree->num_nodes_ = 1;  in TreeInit()
73   memset(tree->lut_bits_, 255, sizeof(tree->lut_bits_));  in TreeInit()
74   memset(tree->lut_jump_, 0, sizeof(tree->lut_jump_));  in TreeInit()
78 void VP8LHuffmanTreeFree(HuffmanTree* const tree) {  in VP8LHuffmanTreeFree()  argument
79   if (tree != NULL) {  in VP8LHuffmanTreeFree()
80     WebPSafeFree(tree->root_);  in VP8LHuffmanTreeFree()
81     tree->root_ = NULL;  in VP8LHuffmanTreeFree()
82     tree->max_nodes_ = 0;  in VP8LHuffmanTreeFree()
83     tree->num_nodes_ = 0;  in VP8LHuffmanTreeFree()
188 static int TreeAddSymbol(HuffmanTree* const tree,  in TreeAddSymbol()  argument
192   HuffmanTreeNode* node = tree->root_;  in TreeAddSymbol()
193   const HuffmanTreeNode* const max_node = tree->root_ + tree->max_nodes_;  in TreeAddSymbol()
200       tree->lut_symbol_[idx] = (int16_t)symbol;  in TreeAddSymbol()
201       tree->lut_bits_[idx] = code_length;  in TreeAddSymbol()
212       if (IsFull(tree)) return 0;    // error: too many symbols.  in TreeAddSymbol()
213       AssignChildren(tree, node);  in TreeAddSymbol()
219       tree->lut_jump_[base_code] = (int16_t)(node - tree->root_);  in TreeAddSymbol()
231 int VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree,  in VP8LHuffmanTreeBuildImplicit()  argument
239   assert(tree != NULL);  in VP8LHuffmanTreeBuildImplicit()
252   if (!TreeInit(tree, num_symbols)) return 0;  in VP8LHuffmanTreeBuildImplicit()
258       VP8LHuffmanTreeFree(tree);  in VP8LHuffmanTreeBuildImplicit()
261     return TreeAddSymbol(tree, root_symbol, 0, 0);  in VP8LHuffmanTreeBuildImplicit()
274         if (!TreeAddSymbol(tree, symbol, codes[symbol],  in VP8LHuffmanTreeBuildImplicit()
282     ok = ok && IsFull(tree);  in VP8LHuffmanTreeBuildImplicit()
283     if (!ok) VP8LHuffmanTreeFree(tree);  in VP8LHuffmanTreeBuildImplicit()
288 int VP8LHuffmanTreeBuildExplicit(HuffmanTree* const tree,  in VP8LHuffmanTreeBuildExplicit()  argument
295   assert(tree != NULL);  in VP8LHuffmanTreeBuildExplicit()
301   if (!TreeInit(tree, num_symbols)) return 0;  in VP8LHuffmanTreeBuildExplicit()
309       if (!TreeAddSymbol(tree, symbols[i], codes[i], code_lengths[i])) {  in VP8LHuffmanTreeBuildExplicit()
316   ok = ok && IsFull(tree);  in VP8LHuffmanTreeBuildExplicit()
317   if (!ok) VP8LHuffmanTreeFree(tree);  in VP8LHuffmanTreeBuildExplicit()