Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 1 | // Copyright 2012 Google Inc. All Rights Reserved. |
| 2 | // |
Vikas Arora | 0406ce1 | 2013-08-09 15:57:12 -0700 | [diff] [blame] | 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. |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 8 | // ----------------------------------------------------------------------------- |
| 9 | // |
| 10 | // Utilities for building and looking up Huffman trees. |
| 11 | // |
| 12 | // Author: Urvang Joshi (urvang@google.com) |
| 13 | |
| 14 | #ifndef WEBP_UTILS_HUFFMAN_H_ |
| 15 | #define WEBP_UTILS_HUFFMAN_H_ |
| 16 | |
| 17 | #include <assert.h> |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 18 | #include "webp/format_constants.h" |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 19 | #include "webp/types.h" |
| 20 | |
Vikas Arora | 8b72022 | 2014-01-02 16:48:02 -0800 | [diff] [blame] | 21 | #ifdef __cplusplus |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 22 | extern "C" { |
| 23 | #endif |
| 24 | |
| 25 | // A node of a Huffman tree. |
| 26 | typedef struct { |
| 27 | int symbol_; |
| 28 | int children_; // delta offset to both children (contiguous) or 0 if leaf. |
| 29 | } HuffmanTreeNode; |
| 30 | |
| 31 | // Huffman Tree. |
Vikas Arora | 8b72022 | 2014-01-02 16:48:02 -0800 | [diff] [blame] | 32 | #define HUFF_LUT_BITS 7 |
| 33 | #define HUFF_LUT (1U << HUFF_LUT_BITS) |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 34 | typedef struct HuffmanTree HuffmanTree; |
| 35 | struct HuffmanTree { |
Vikas Arora | 8b72022 | 2014-01-02 16:48:02 -0800 | [diff] [blame] | 36 | // Fast lookup for short bit lengths. |
| 37 | uint8_t lut_bits_[HUFF_LUT]; |
| 38 | int16_t lut_symbol_[HUFF_LUT]; |
| 39 | int16_t lut_jump_[HUFF_LUT]; |
| 40 | // Complete tree for lookups. |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 41 | HuffmanTreeNode* root_; // all the nodes, starting at root. |
| 42 | int max_nodes_; // max number of nodes |
| 43 | int num_nodes_; // number of currently occupied nodes |
| 44 | }; |
| 45 | |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 46 | // Huffman Tree group. |
| 47 | typedef struct HTreeGroup HTreeGroup; |
| 48 | struct HTreeGroup { |
| 49 | HuffmanTree htrees_[HUFFMAN_CODES_PER_META_CODE]; |
| 50 | }; |
| 51 | |
Vikas Arora | 8b72022 | 2014-01-02 16:48:02 -0800 | [diff] [blame] | 52 | // Returns true if the given node is not a leaf of the Huffman tree. |
| 53 | static WEBP_INLINE int HuffmanTreeNodeIsNotLeaf( |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 54 | const HuffmanTreeNode* const node) { |
Vikas Arora | 8b72022 | 2014-01-02 16:48:02 -0800 | [diff] [blame] | 55 | return node->children_; |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 56 | } |
| 57 | |
| 58 | // Go down one level. Most critical function. 'right_child' must be 0 or 1. |
| 59 | static WEBP_INLINE const HuffmanTreeNode* HuffmanTreeNextNode( |
| 60 | const HuffmanTreeNode* node, int right_child) { |
| 61 | return node + node->children_ + right_child; |
| 62 | } |
| 63 | |
| 64 | // Releases the nodes of the Huffman tree. |
| 65 | // Note: It does NOT free 'tree' itself. |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 66 | void VP8LHuffmanTreeFree(HuffmanTree* const tree); |
| 67 | |
| 68 | // Creates the instance of HTreeGroup with specified number of tree-groups. |
| 69 | HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); |
| 70 | |
| 71 | // Releases the memory allocated for HTreeGroup. |
| 72 | void VP8LHtreeGroupsFree(HTreeGroup* htree_groups, int num_htree_groups); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 73 | |
| 74 | // Builds Huffman tree assuming code lengths are implicitly in symbol order. |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 75 | // The 'huff_codes' and 'code_lengths' are pre-allocated temporary memory |
| 76 | // buffers, used for creating the huffman tree. |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 77 | // Returns false in case of error (invalid tree or memory error). |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 78 | int VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree, |
| 79 | const int* const code_lengths, |
| 80 | int* const huff_codes, |
| 81 | int code_lengths_size); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 82 | |
| 83 | // Build a Huffman tree with explicitly given lists of code lengths, codes |
| 84 | // and symbols. Verifies that all symbols added are smaller than max_symbol. |
| 85 | // Returns false in case of an invalid symbol, invalid tree or memory error. |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 86 | int VP8LHuffmanTreeBuildExplicit(HuffmanTree* const tree, |
| 87 | const int* const code_lengths, |
| 88 | const int* const codes, |
| 89 | const int* const symbols, int max_symbol, |
| 90 | int num_symbols); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 91 | |
| 92 | // Utility: converts Huffman code lengths to corresponding Huffman codes. |
| 93 | // 'huff_codes' should be pre-allocated. |
| 94 | // Returns false in case of error (memory allocation, invalid codes). |
Vikas Arora | af51b94 | 2014-08-28 10:51:12 -0700 | [diff] [blame] | 95 | int VP8LHuffmanCodeLengthsToCodes(const int* const code_lengths, |
| 96 | int code_lengths_size, int* const huff_codes); |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 97 | |
Vikas Arora | 8b72022 | 2014-01-02 16:48:02 -0800 | [diff] [blame] | 98 | #ifdef __cplusplus |
Vikas Arora | a241572 | 2012-08-09 16:18:58 -0700 | [diff] [blame] | 99 | } // extern "C" |
| 100 | #endif |
| 101 | |
| 102 | #endif // WEBP_UTILS_HUFFMAN_H_ |