Chromium Code Reviews
chromiumcodereview-hr@appspot.gserviceaccount.com (chromiumcodereview-hr) | Please choose your nickname with Settings | Help | Chromium Project | Gerrit Changes | Sign out
(1210)

Side by Side Diff: third_party/libwebp/utils/huffman.h

Issue 1546003002: libwebp: update to 0.5.0 (Closed) Base URL: https://chromium.googlesource.com/chromium/src.git@master
Patch Set: 'defines' exists Created 4 years, 12 months ago
Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.
Jump to:
View unified diff | Download patch
OLDNEW
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_
OLDNEW

Powered by Google App Engine
This is Rietveld 408576698