1 | // Copyright 2012 Google Inc. All Rights Reserved. |
2 | // |
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. |
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_UTILS_H_ |
15 | #define WEBP_UTILS_HUFFMAN_UTILS_H_ |
16 | |
17 | #include <assert.h> |
18 | #include "src/webp/format_constants.h" |
19 | #include "src/webp/types.h" |
20 | |
21 | #ifdef __cplusplus |
22 | extern "C" { |
23 | #endif |
24 | |
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 |
33 | typedef struct { |
34 | uint8_t bits; // number of bits used for this symbol |
35 | uint16_t value; // symbol value or table offset |
36 | } HuffmanCode; |
37 | |
38 | // long version for holding 32b values |
39 | typedef struct { |
40 | int bits; // number of bits used for this symbol, |
41 | // or an impossible value if not a literal code. |
42 | uint32_t value; // 32b packed ARGB value if literal, |
43 | // or non-literal symbol otherwise |
44 | } HuffmanCode32; |
45 | |
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'. |
56 | typedef struct HTreeGroup HTreeGroup; |
57 | struct HTreeGroup { |
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]; |
68 | }; |
69 | |
70 | // Creates the instance of HTreeGroup with specified number of tree-groups. |
71 | HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); |
72 | |
73 | // Releases the memory allocated for HTreeGroup. |
74 | void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups); |
75 | |
76 | // Builds Huffman lookup table assuming code lengths are in symbol order. |
77 | // The 'code_lengths' is pre-allocated temporary memory buffer used for creating |
78 | // the huffman table. |
79 | // Returns built table size or 0 in case of error (invalid tree or |
80 | // memory error). |
81 | // If root_table is NULL, it returns 0 if a lookup cannot be built, something |
82 | // > 0 otherwise (but not the table size). |
83 | int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits, |
84 | const int code_lengths[], int code_lengths_size); |
85 | |
86 | #ifdef __cplusplus |
87 | } // extern "C" |
88 | #endif |
89 | |
90 | #endif // WEBP_UTILS_HUFFMAN_UTILS_H_ |
91 | |