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 int VP8LBuildHuffmanTable(HuffmanCode* const root_table, int root_bits, 82 const int code_lengths[], int code_lengths_size); 83 84 #ifdef __cplusplus 85 } // extern "C" 86 #endif 87 88 #endif // WEBP_UTILS_HUFFMAN_UTILS_H_ 89