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
22extern "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
33typedef 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
39typedef 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.
47typedef 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.
58typedef 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.
66int VP8LHuffmanTablesAllocate(int size, HuffmanTables* huffman_tables);
67void 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'.
79typedef struct HTreeGroup HTreeGroup;
80struct 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.
94HTreeGroup* VP8LHtreeGroupsNew(int num_htree_groups);
95
96// Releases the memory allocated for HTreeGroup.
97void 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).
104int 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