tor-browser

The Tor Browser
git clone https://git.dasho.dev/tor-browser.git
Log | Files | Refs | README | LICENSE

huffman_utils.h (4537B)

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