OLD | NEW |
1 // Copyright 2012 Google Inc. All Rights Reserved. | 1 // Copyright 2012 Google Inc. All Rights Reserved. |
2 // | 2 // |
3 // Use of this source code is governed by a BSD-style license | 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 | 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 | 5 // tree. An additional intellectual property rights grant can be found |
6 // in the file PATENTS. All contributing project authors may | 6 // in the file PATENTS. All contributing project authors may |
7 // be found in the AUTHORS file in the root of the source tree. | 7 // be found in the AUTHORS file in the root of the source tree. |
8 // ----------------------------------------------------------------------------- | 8 // ----------------------------------------------------------------------------- |
9 // | 9 // |
10 // Utilities for building and looking up Huffman trees. | 10 // Utilities for building and looking up Huffman trees. |
11 // | 11 // |
12 // Author: Urvang Joshi (urvang@google.com) | 12 // Author: Urvang Joshi (urvang@google.com) |
13 | 13 |
14 #ifndef WEBP_UTILS_HUFFMAN_H_ | 14 #ifndef WEBP_UTILS_HUFFMAN_H_ |
15 #define WEBP_UTILS_HUFFMAN_H_ | 15 #define WEBP_UTILS_HUFFMAN_H_ |
16 | 16 |
17 #include <assert.h> | 17 #include <assert.h> |
18 #include "../webp/format_constants.h" | 18 #include "../webp/format_constants.h" |
19 #include "../webp/types.h" | 19 #include "../webp/types.h" |
20 | 20 |
21 #ifdef __cplusplus | 21 #ifdef __cplusplus |
22 extern "C" { | 22 extern "C" { |
23 #endif | 23 #endif |
24 | 24 |
25 // A node of a Huffman tree. | 25 #define HUFFMAN_TABLE_BITS 8 |
| 26 #define HUFFMAN_TABLE_MASK ((1 << HUFFMAN_TABLE_BITS) - 1) |
| 27 |
| 28 #define LENGTHS_TABLE_BITS 7 |
| 29 #define LENGTHS_TABLE_MASK ((1 << LENGTHS_TABLE_BITS) - 1) |
| 30 |
| 31 |
| 32 // Huffman lookup table entry |
26 typedef struct { | 33 typedef struct { |
27 int symbol_; | 34 uint8_t bits; // number of bits used for this symbol |
28 int children_; // delta offset to both children (contiguous) or 0 if leaf. | 35 uint16_t value; // symbol value or table offset |
29 } HuffmanTreeNode; | 36 } HuffmanCode; |
30 | 37 |
31 // Huffman Tree. | 38 // long version for holding 32b values |
32 #define HUFF_LUT_BITS 7 | 39 typedef struct { |
33 #define HUFF_LUT (1U << HUFF_LUT_BITS) | 40 int bits; // number of bits used for this symbol, |
34 typedef struct HuffmanTree HuffmanTree; | 41 // or an impossible value if not a literal code. |
35 struct HuffmanTree { | 42 uint32_t value; // 32b packed ARGB value if literal, |
36 // Fast lookup for short bit lengths. | 43 // or non-literal symbol otherwise |
37 uint8_t lut_bits_[HUFF_LUT]; | 44 } HuffmanCode32; |
38 int16_t lut_symbol_[HUFF_LUT]; | |
39 int16_t lut_jump_[HUFF_LUT]; | |
40 // Complete tree for lookups. | |
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 | 45 |
46 // Huffman Tree group. | 46 #define HUFFMAN_PACKED_BITS 6 |
| 47 #define HUFFMAN_PACKED_TABLE_SIZE (1u << HUFFMAN_PACKED_BITS) |
| 48 |
| 49 // Huffman table group. |
| 50 // Includes special handling for the following cases: |
| 51 // - is_trivial_literal: one common literal base for RED/BLUE/ALPHA (not GREEN) |
| 52 // - is_trivial_code: only 1 code (no bit is read from bitstream) |
| 53 // - use_packed_table: few enough literal symbols, so all the bit codes |
| 54 // can fit into a small look-up table packed_table[] |
| 55 // The common literal base, if applicable, is stored in 'literal_arb'. |
47 typedef struct HTreeGroup HTreeGroup; | 56 typedef struct HTreeGroup HTreeGroup; |
48 struct HTreeGroup { | 57 struct HTreeGroup { |
49 HuffmanTree htrees_[HUFFMAN_CODES_PER_META_CODE]; | 58 HuffmanCode* htrees[HUFFMAN_CODES_PER_META_CODE]; |
| 59 int is_trivial_literal; // True, if huffman trees for Red, Blue & Alpha |
| 60 // Symbols are trivial (have a single code). |
| 61 uint32_t literal_arb; // If is_trivial_literal is true, this is the |
| 62 // ARGB value of the pixel, with Green channel |
| 63 // being set to zero. |
| 64 int is_trivial_code; // true if is_trivial_literal with only one code |
| 65 int use_packed_table; // use packed table below for short literal code |
| 66 // table mapping input bits to a packed values, or escape case to literal code |
| 67 HuffmanCode32 packed_table[HUFFMAN_PACKED_TABLE_SIZE]; |
50 }; | 68 }; |
51 | 69 |
52 // Returns true if the given node is not a leaf of the Huffman tree. | |
53 static WEBP_INLINE int HuffmanTreeNodeIsNotLeaf( | |
54 const HuffmanTreeNode* const node) { | |
55 return node->children_; | |
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. | |
66 void VP8LHuffmanTreeFree(HuffmanTree* const tree); | |
67 | |
68 // Creates the instance of HTreeGroup with specified number of tree-groups. | 70 // Creates the instance of HTreeGroup with specified number of tree-groups. |
69 HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); | 71 HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); |
70 | 72 |
71 // Releases the memory allocated for HTreeGroup. | 73 // Releases the memory allocated for HTreeGroup. |
72 void VP8LHtreeGroupsFree(HTreeGroup* htree_groups, int num_htree_groups); | 74 void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups); |
73 | 75 |
74 // Builds Huffman tree assuming code lengths are implicitly in symbol order. | 76 // Builds Huffman lookup table assuming code lengths are in symbol order. |
75 // The 'huff_codes' and 'code_lengths' are pre-allocated temporary memory | 77 // The 'code_lengths' is pre-allocated temporary memory buffer used for creating |
76 // buffers, used for creating the huffman tree. | 78 // the huffman table. |
77 // Returns false in case of error (invalid tree or memory error). | 79 // Returns built table size or 0 in case of error (invalid tree or |
78 int VP8LHuffmanTreeBuildImplicit(HuffmanTree* const tree, | 80 // memory error). |
79 const int* const code_lengths, | 81 int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits, |
80 int* const huff_codes, | 82 const int code_lengths[], int code_lengths_size); |
81 int code_lengths_size); | |
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. | |
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); | |
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). | |
95 int VP8LHuffmanCodeLengthsToCodes(const int* const code_lengths, | |
96 int code_lengths_size, int* const huff_codes); | |
97 | 83 |
98 #ifdef __cplusplus | 84 #ifdef __cplusplus |
99 } // extern "C" | 85 } // extern "C" |
100 #endif | 86 #endif |
101 | 87 |
102 #endif // WEBP_UTILS_HUFFMAN_H_ | 88 #endif // WEBP_UTILS_HUFFMAN_H_ |
OLD | NEW |