OLD | NEW |
(Empty) | |
| 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@google.com) |
| 11 |
| 12 #ifndef WEBP_UTILS_HUFFMAN_H_ |
| 13 #define WEBP_UTILS_HUFFMAN_H_ |
| 14 |
| 15 #include <assert.h> |
| 16 #include "../webp/types.h" |
| 17 |
| 18 #if defined(__cplusplus) || defined(c_plusplus) |
| 19 extern "C" { |
| 20 #endif |
| 21 |
| 22 // A node of a Huffman tree. |
| 23 typedef struct { |
| 24 int symbol_; |
| 25 int children_; // delta offset to both children (contiguous) or 0 if leaf. |
| 26 } HuffmanTreeNode; |
| 27 |
| 28 // Huffman Tree. |
| 29 typedef struct HuffmanTree HuffmanTree; |
| 30 struct HuffmanTree { |
| 31 HuffmanTreeNode* root_; // all the nodes, starting at root. |
| 32 int max_nodes_; // max number of nodes |
| 33 int num_nodes_; // number of currently occupied nodes |
| 34 }; |
| 35 |
| 36 // Returns true if the given node is a leaf of the Huffman tree. |
| 37 static WEBP_INLINE int HuffmanTreeNodeIsLeaf( |
| 38 const HuffmanTreeNode* const node) { |
| 39 return (node->children_ == 0); |
| 40 } |
| 41 |
| 42 // Go down one level. Most critical function. 'right_child' must be 0 or 1. |
| 43 static WEBP_INLINE const HuffmanTreeNode* HuffmanTreeNextNode( |
| 44 const HuffmanTreeNode* node, int right_child) { |
| 45 return node + node->children_ + right_child; |
| 46 } |
| 47 |
| 48 // Releases the nodes of the Huffman tree. |
| 49 // Note: It does NOT free 'tree' itself. |
| 50 void HuffmanTreeRelease(HuffmanTree* const tree); |
| 51 |
| 52 // Builds Huffman tree assuming code lengths are implicitly in symbol order. |
| 53 // Returns false in case of error (invalid tree or memory error). |
| 54 int HuffmanTreeBuildImplicit(HuffmanTree* const tree, |
| 55 const int* const code_lengths, |
| 56 int code_lengths_size); |
| 57 |
| 58 // Build a Huffman tree with explicitly given lists of code lengths, codes |
| 59 // and symbols. Verifies that all symbols added are smaller than max_symbol. |
| 60 // Returns false in case of an invalid symbol, invalid tree or memory error. |
| 61 int HuffmanTreeBuildExplicit(HuffmanTree* const tree, |
| 62 const int* const code_lengths, |
| 63 const int* const codes, |
| 64 const int* const symbols, int max_symbol, |
| 65 int num_symbols); |
| 66 |
| 67 // Utility: converts Huffman code lengths to corresponding Huffman codes. |
| 68 // 'huff_codes' should be pre-allocated. |
| 69 // Returns false in case of error (memory allocation, invalid codes). |
| 70 int HuffmanCodeLengthsToCodes(const int* const code_lengths, |
| 71 int code_lengths_size, int* const huff_codes); |
| 72 |
| 73 |
| 74 #if defined(__cplusplus) || defined(c_plusplus) |
| 75 } // extern "C" |
| 76 #endif |
| 77 |
| 78 #endif // WEBP_UTILS_HUFFMAN_H_ |
OLD | NEW |