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