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 | // Contiguous memory segment of HuffmanCodes. |
47 | typedef struct HuffmanTablesSegment { |
48 | HuffmanCode* start; |
49 | // Pointer to where we are writing into the segment. Starts at 'start' and |
50 | // cannot go beyond 'start' + 'size'. |
51 | HuffmanCode* curr_table; |
52 | // Pointer to the next segment in the chain. |
53 | struct HuffmanTablesSegment* next; |
54 | int size; |
55 | } HuffmanTablesSegment; |
56 | |
57 | // Chained memory segments of HuffmanCodes. |
58 | typedef struct HuffmanTables { |
59 | HuffmanTablesSegment root; |
60 | // Currently processed segment. At first, this is 'root'. |
61 | HuffmanTablesSegment* curr_segment; |
62 | } HuffmanTables; |
63 | |
64 | // Allocates a HuffmanTables with 'size' contiguous HuffmanCodes. Returns 0 on |
65 | // memory allocation error, 1 otherwise. |
66 | int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables); |
67 | void VP8LHuffmanTablesDeallocate(HuffmanTables* const huffman_tables); |
68 | |
69 | #define HUFFMAN_PACKED_BITS 6 |
70 | #define HUFFMAN_PACKED_TABLE_SIZE (1u << HUFFMAN_PACKED_BITS) |
71 | |
72 | // Huffman table group. |
73 | // Includes special handling for the following cases: |
74 | // - is_trivial_literal: one common literal base for RED/BLUE/ALPHA (not GREEN) |
75 | // - is_trivial_code: only 1 code (no bit is read from bitstream) |
76 | // - use_packed_table: few enough literal symbols, so all the bit codes |
77 | // can fit into a small look-up table packed_table[] |
78 | // The common literal base, if applicable, is stored in 'literal_arb'. |
79 | typedef struct HTreeGroup HTreeGroup; |
80 | struct HTreeGroup { |
81 | HuffmanCode* htrees[HUFFMAN_CODES_PER_META_CODE]; |
82 | int is_trivial_literal; // True, if huffman trees for Red, Blue & Alpha |
83 | // Symbols are trivial (have a single code). |
84 | uint32_t literal_arb; // If is_trivial_literal is true, this is the |
85 | // ARGB value of the pixel, with Green channel |
86 | // being set to zero. |
87 | int is_trivial_code; // true if is_trivial_literal with only one code |
88 | int use_packed_table; // use packed table below for short literal code |
89 | // table mapping input bits to a packed values, or escape case to literal code |
90 | HuffmanCode32 packed_table[HUFFMAN_PACKED_TABLE_SIZE]; |
91 | }; |
92 | |
93 | // Creates the instance of HTreeGroup with specified number of tree-groups. |
94 | HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups); |
95 | |
96 | // Releases the memory allocated for HTreeGroup. |
97 | void VP8LHtreeGroupsFree(HTreeGroup* const htree_groups); |
98 | |
99 | // Builds Huffman lookup table assuming code lengths are in symbol order. |
100 | // The 'code_lengths' is pre-allocated temporary memory buffer used for creating |
101 | // the huffman table. |
102 | // Returns built table size or 0 in case of error (invalid tree or |
103 | // memory error). |
104 | int VP8LBuildHuffmanTable(HuffmanTables* const root_table, int root_bits, |
105 | const int code_lengths[], int code_lengths_size); |
106 | |
107 | #ifdef __cplusplus |
108 | } // extern "C" |
109 | #endif |
110 | |
111 | #endif // WEBP_UTILS_HUFFMAN_UTILS_H_ |
112 | |