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