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