BaseTools/Source/C/BrotliCompress/dec/state.h

   1 /* Copyright 2015 Google Inc. All Rights Reserved.
   2
   3    Distributed under MIT license.
   4    See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
   5 */
   6
   7 /* Brotli state for partial streaming decoding. */
   8
   9 #ifndef BROTLI_DEC_STATE_H_
  10 #define BROTLI_DEC_STATE_H_
  11
  12 #include "../common/constants.h"
  13 #include "../common/dictionary.h"
  14 #include "../common/platform.h"
  15 #include "../common/transform.h"
  16 #include <brotli/types.h>
  17 #include "./bit_reader.h"
  18 #include "./huffman.h"
  19
  20 #if defined(__cplusplus) || defined(c_plusplus)
  21 extern "C" {
  22 #endif
  23
  24 typedef enum {
  25   BROTLI_STATE_UNINITED,
  26   BROTLI_STATE_LARGE_WINDOW_BITS,
  27   BROTLI_STATE_INITIALIZE,
  28   BROTLI_STATE_METABLOCK_BEGIN,
  29   BROTLI_STATE_METABLOCK_HEADER,
  30   BROTLI_STATE_METABLOCK_HEADER_2,
  31   BROTLI_STATE_CONTEXT_MODES,
  32   BROTLI_STATE_COMMAND_BEGIN,
  33   BROTLI_STATE_COMMAND_INNER,
  34   BROTLI_STATE_COMMAND_POST_DECODE_LITERALS,
  35   BROTLI_STATE_COMMAND_POST_WRAP_COPY,
  36   BROTLI_STATE_UNCOMPRESSED,
  37   BROTLI_STATE_METADATA,
  38   BROTLI_STATE_COMMAND_INNER_WRITE,
  39   BROTLI_STATE_METABLOCK_DONE,
  40   BROTLI_STATE_COMMAND_POST_WRITE_1,
  41   BROTLI_STATE_COMMAND_POST_WRITE_2,
  42   BROTLI_STATE_HUFFMAN_CODE_0,
  43   BROTLI_STATE_HUFFMAN_CODE_1,
  44   BROTLI_STATE_HUFFMAN_CODE_2,
  45   BROTLI_STATE_HUFFMAN_CODE_3,
  46   BROTLI_STATE_CONTEXT_MAP_1,
  47   BROTLI_STATE_CONTEXT_MAP_2,
  48   BROTLI_STATE_TREE_GROUP,
  49   BROTLI_STATE_DONE
  50 } BrotliRunningState;
  51
  52 typedef enum {
  53   BROTLI_STATE_METABLOCK_HEADER_NONE,
  54   BROTLI_STATE_METABLOCK_HEADER_EMPTY,
  55   BROTLI_STATE_METABLOCK_HEADER_NIBBLES,
  56   BROTLI_STATE_METABLOCK_HEADER_SIZE,
  57   BROTLI_STATE_METABLOCK_HEADER_UNCOMPRESSED,
  58   BROTLI_STATE_METABLOCK_HEADER_RESERVED,
  59   BROTLI_STATE_METABLOCK_HEADER_BYTES,
  60   BROTLI_STATE_METABLOCK_HEADER_METADATA
  61 } BrotliRunningMetablockHeaderState;
  62
  63 typedef enum {
  64   BROTLI_STATE_UNCOMPRESSED_NONE,
  65   BROTLI_STATE_UNCOMPRESSED_WRITE
  66 } BrotliRunningUncompressedState;
  67
  68 typedef enum {
  69   BROTLI_STATE_TREE_GROUP_NONE,
  70   BROTLI_STATE_TREE_GROUP_LOOP
  71 } BrotliRunningTreeGroupState;
  72
  73 typedef enum {
  74   BROTLI_STATE_CONTEXT_MAP_NONE,
  75   BROTLI_STATE_CONTEXT_MAP_READ_PREFIX,
  76   BROTLI_STATE_CONTEXT_MAP_HUFFMAN,
  77   BROTLI_STATE_CONTEXT_MAP_DECODE,
  78   BROTLI_STATE_CONTEXT_MAP_TRANSFORM
  79 } BrotliRunningContextMapState;
  80
  81 typedef enum {
  82   BROTLI_STATE_HUFFMAN_NONE,
  83   BROTLI_STATE_HUFFMAN_SIMPLE_SIZE,
  84   BROTLI_STATE_HUFFMAN_SIMPLE_READ,
  85   BROTLI_STATE_HUFFMAN_SIMPLE_BUILD,
  86   BROTLI_STATE_HUFFMAN_COMPLEX,
  87   BROTLI_STATE_HUFFMAN_LENGTH_SYMBOLS
  88 } BrotliRunningHuffmanState;
  89
  90 typedef enum {
  91   BROTLI_STATE_DECODE_UINT8_NONE,
  92   BROTLI_STATE_DECODE_UINT8_SHORT,
  93   BROTLI_STATE_DECODE_UINT8_LONG
  94 } BrotliRunningDecodeUint8State;
  95
  96 typedef enum {
  97   BROTLI_STATE_READ_BLOCK_LENGTH_NONE,
  98   BROTLI_STATE_READ_BLOCK_LENGTH_SUFFIX
  99 } BrotliRunningReadBlockLengthState;
 100
 101 struct BrotliDecoderStateStruct {
 102   BrotliRunningState state;
 103
 104   /* This counter is reused for several disjoint loops. */
 105   int loop_counter;
 106
 107   BrotliBitReader br;
 108
 109   brotli_alloc_func alloc_func;
 110   brotli_free_func free_func;
 111   void* memory_manager_opaque;
 112
 113   /* Temporary storage for remaining input. */
 114   union {
 115     uint64_t u64;
 116     uint8_t u8[8];
 117   } buffer;
 118   uint32_t buffer_length;
 119
 120   int pos;
 121   int max_backward_distance;
 122   int max_distance;
 123   int ringbuffer_size;
 124   int ringbuffer_mask;
 125   int dist_rb_idx;
 126   int dist_rb[4];
 127   int error_code;
 128   uint32_t sub_loop_counter;
 129   uint8_t* ringbuffer;
 130   uint8_t* ringbuffer_end;
 131   HuffmanCode* htree_command;
 132   const uint8_t* context_lookup;
 133   uint8_t* context_map_slice;
 134   uint8_t* dist_context_map_slice;
 135
 136   /* This ring buffer holds a few past copy distances that will be used by
 137      some special distance codes. */
 138   HuffmanTreeGroup literal_hgroup;
 139   HuffmanTreeGroup insert_copy_hgroup;
 140   HuffmanTreeGroup distance_hgroup;
 141   HuffmanCode* block_type_trees;
 142   HuffmanCode* block_len_trees;
 143   /* This is true if the literal context map histogram type always matches the
 144      block type. It is then not needed to keep the context (faster decoding). */
 145   int trivial_literal_context;
 146   /* Distance context is actual after command is decoded and before distance is
 147      computed. After distance computation it is used as a temporary variable. */
 148   int distance_context;
 149   int meta_block_remaining_len;
 150   uint32_t block_length_index;
 151   uint32_t block_length[3];
 152   uint32_t num_block_types[3];
 153   uint32_t block_type_rb[6];
 154   uint32_t distance_postfix_bits;
 155   uint32_t num_direct_distance_codes;
 156   int distance_postfix_mask;
 157   uint32_t num_dist_htrees;
 158   uint8_t* dist_context_map;
 159   HuffmanCode* literal_htree;
 160   uint8_t dist_htree_index;
 161   uint32_t repeat_code_len;
 162   uint32_t prev_code_len;
 163
 164   int copy_length;
 165   int distance_code;
 166
 167   /* For partial write operations. */
 168   size_t rb_roundtrips;  /* how many times we went around the ring-buffer */
 169   size_t partial_pos_out;  /* how much output to the user in total */
 170
 171   /* For ReadHuffmanCode. */
 172   uint32_t symbol;
 173   uint32_t repeat;
 174   uint32_t space;
 175
 176   HuffmanCode table[32];
 177   /* List of heads of symbol chains. */
 178   uint16_t* symbol_lists;
 179   /* Storage from symbol_lists. */
 180   uint16_t symbols_lists_array[BROTLI_HUFFMAN_MAX_CODE_LENGTH + 1 +
 181                                BROTLI_NUM_COMMAND_SYMBOLS];
 182   /* Tails of symbol chains. */
 183   int next_symbol[32];
 184   uint8_t code_length_code_lengths[BROTLI_CODE_LENGTH_CODES];
 185   /* Population counts for the code lengths. */
 186   uint16_t code_length_histo[16];
 187
 188   /* For HuffmanTreeGroupDecode. */
 189   int htree_index;
 190   HuffmanCode* next;
 191
 192   /* For DecodeContextMap. */
 193   uint32_t context_index;
 194   uint32_t max_run_length_prefix;
 195   uint32_t code;
 196   HuffmanCode context_map_table[BROTLI_HUFFMAN_MAX_SIZE_272];
 197
 198   /* For InverseMoveToFrontTransform. */
 199   uint32_t mtf_upper_bound;
 200   uint32_t mtf[64 + 1];
 201
 202   /* Less used attributes are at the end of this struct. */
 203
 204   /* States inside function calls. */
 205   BrotliRunningMetablockHeaderState substate_metablock_header;
 206   BrotliRunningTreeGroupState substate_tree_group;
 207   BrotliRunningContextMapState substate_context_map;
 208   BrotliRunningUncompressedState substate_uncompressed;
 209   BrotliRunningHuffmanState substate_huffman;
 210   BrotliRunningDecodeUint8State substate_decode_uint8;
 211   BrotliRunningReadBlockLengthState substate_read_block_length;
 212
 213   unsigned int is_last_metablock : 1;
 214   unsigned int is_uncompressed : 1;
 215   unsigned int is_metadata : 1;
 216   unsigned int should_wrap_ringbuffer : 1;
 217   unsigned int canny_ringbuffer_allocation : 1;
 218   unsigned int large_window : 1;
 219   unsigned int size_nibbles : 8;
 220   uint32_t window_bits;
 221
 222   int new_ringbuffer_size;
 223
 224   uint32_t num_literal_htrees;
 225   uint8_t* context_map;
 226   uint8_t* context_modes;
 227
 228   const BrotliDictionary* dictionary;
 229   const BrotliTransforms* transforms;
 230
 231   uint32_t trivial_literal_contexts[8];  /* 256 bits */
 232 };
 233
 234 typedef struct BrotliDecoderStateStruct BrotliDecoderStateInternal;
 235 #define BrotliDecoderState BrotliDecoderStateInternal
 236
 237 BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderStateInit(BrotliDecoderState* s,
 238     brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque);
 239 BROTLI_INTERNAL void BrotliDecoderStateCleanup(BrotliDecoderState* s);
 240 BROTLI_INTERNAL void BrotliDecoderStateMetablockBegin(BrotliDecoderState* s);
 241 BROTLI_INTERNAL void BrotliDecoderStateCleanupAfterMetablock(
 242     BrotliDecoderState* s);
 243 BROTLI_INTERNAL BROTLI_BOOL BrotliDecoderHuffmanTreeGroupInit(
 244     BrotliDecoderState* s, HuffmanTreeGroup* group, uint32_t alphabet_size,
 245     uint32_t max_symbol, uint32_t ntrees);
 246
 247 #define BROTLI_DECODER_ALLOC(S, L) S->alloc_func(S->memory_manager_opaque, L)
 248
 249 #define BROTLI_DECODER_FREE(S, X) {          \
 250   S->free_func(S->memory_manager_opaque, X); \
 251   X = NULL;                                  \
 252 }
 253
 254 #if defined(__cplusplus) || defined(c_plusplus)
 255 }  /* extern "C" */
 256 #endif
 257
 258 #endif  /* BROTLI_DEC_STATE_H_ */