| File: | out/../deps/brotli/c/enc/./command.h |
| Warning: | line 139, column 21 Access to field 'insert_len_' results in a dereference of a null pointer (loaded from variable 'self') |
Press '?' to see keyboard shortcuts
Keyboard shortcuts:
| 1 | /* Copyright 2013 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 | /* Implementation of Brotli compressor. */ | ||||||||
| 8 | |||||||||
| 9 | #include <brotli/encode.h> | ||||||||
| 10 | |||||||||
| 11 | #include <stdlib.h> /* free, malloc */ | ||||||||
| 12 | #include <string.h> /* memcpy, memset */ | ||||||||
| 13 | |||||||||
| 14 | #include "../common/constants.h" | ||||||||
| 15 | #include "../common/context.h" | ||||||||
| 16 | #include "../common/platform.h" | ||||||||
| 17 | #include "../common/version.h" | ||||||||
| 18 | #include "./backward_references.h" | ||||||||
| 19 | #include "./backward_references_hq.h" | ||||||||
| 20 | #include "./bit_cost.h" | ||||||||
| 21 | #include "./brotli_bit_stream.h" | ||||||||
| 22 | #include "./compress_fragment.h" | ||||||||
| 23 | #include "./compress_fragment_two_pass.h" | ||||||||
| 24 | #include "./encoder_dict.h" | ||||||||
| 25 | #include "./entropy_encode.h" | ||||||||
| 26 | #include "./fast_log.h" | ||||||||
| 27 | #include "./hash.h" | ||||||||
| 28 | #include "./histogram.h" | ||||||||
| 29 | #include "./memory.h" | ||||||||
| 30 | #include "./metablock.h" | ||||||||
| 31 | #include "./prefix.h" | ||||||||
| 32 | #include "./quality.h" | ||||||||
| 33 | #include "./ringbuffer.h" | ||||||||
| 34 | #include "./utf8_util.h" | ||||||||
| 35 | #include "./write_bits.h" | ||||||||
| 36 | |||||||||
| 37 | #if defined(__cplusplus) || defined(c_plusplus) | ||||||||
| 38 | extern "C" { | ||||||||
| 39 | #endif | ||||||||
| 40 | |||||||||
| 41 | #define COPY_ARRAY(dst, src)memcpy(dst, src, sizeof(src)); memcpy(dst, src, sizeof(src)); | ||||||||
| 42 | |||||||||
| 43 | typedef enum BrotliEncoderStreamState { | ||||||||
| 44 | /* Default state. */ | ||||||||
| 45 | BROTLI_STREAM_PROCESSING = 0, | ||||||||
| 46 | /* Intermediate state; after next block is emitted, byte-padding should be | ||||||||
| 47 | performed before getting back to default state. */ | ||||||||
| 48 | BROTLI_STREAM_FLUSH_REQUESTED = 1, | ||||||||
| 49 | /* Last metablock was produced; no more input is acceptable. */ | ||||||||
| 50 | BROTLI_STREAM_FINISHED = 2, | ||||||||
| 51 | /* Flushing compressed block and writing meta-data block header. */ | ||||||||
| 52 | BROTLI_STREAM_METADATA_HEAD = 3, | ||||||||
| 53 | /* Writing metadata block body. */ | ||||||||
| 54 | BROTLI_STREAM_METADATA_BODY = 4 | ||||||||
| 55 | } BrotliEncoderStreamState; | ||||||||
| 56 | |||||||||
| 57 | typedef enum BrotliEncoderFlintState { | ||||||||
| 58 | BROTLI_FLINT_NEEDS_2_BYTES = 2, | ||||||||
| 59 | BROTLI_FLINT_NEEDS_1_BYTE = 1, | ||||||||
| 60 | BROTLI_FLINT_WAITING_FOR_PROCESSING = 0, | ||||||||
| 61 | BROTLI_FLINT_WAITING_FOR_FLUSHING = -1, | ||||||||
| 62 | BROTLI_FLINT_DONE = -2 | ||||||||
| 63 | } BrotliEncoderFlintState; | ||||||||
| 64 | |||||||||
| 65 | typedef struct BrotliEncoderStateStruct { | ||||||||
| 66 | BrotliEncoderParams params; | ||||||||
| 67 | |||||||||
| 68 | MemoryManager memory_manager_; | ||||||||
| 69 | |||||||||
| 70 | uint64_t input_pos_; | ||||||||
| 71 | RingBuffer ringbuffer_; | ||||||||
| 72 | size_t cmd_alloc_size_; | ||||||||
| 73 | Command* commands_; | ||||||||
| 74 | size_t num_commands_; | ||||||||
| 75 | size_t num_literals_; | ||||||||
| 76 | size_t last_insert_len_; | ||||||||
| 77 | uint64_t last_flush_pos_; | ||||||||
| 78 | uint64_t last_processed_pos_; | ||||||||
| 79 | int dist_cache_[BROTLI_NUM_DISTANCE_SHORT_CODES16]; | ||||||||
| 80 | int saved_dist_cache_[4]; | ||||||||
| 81 | uint16_t last_bytes_; | ||||||||
| 82 | uint8_t last_bytes_bits_; | ||||||||
| 83 | /* "Flint" is a tiny uncompressed block emitted before the continuation | ||||||||
| 84 | block to unwire literal context from previous data. Despite being int8_t, | ||||||||
| 85 | field is actually BrotliEncoderFlintState enum. */ | ||||||||
| 86 | int8_t flint_; | ||||||||
| 87 | uint8_t prev_byte_; | ||||||||
| 88 | uint8_t prev_byte2_; | ||||||||
| 89 | size_t storage_size_; | ||||||||
| 90 | uint8_t* storage_; | ||||||||
| 91 | |||||||||
| 92 | Hasher hasher_; | ||||||||
| 93 | |||||||||
| 94 | /* Hash table for FAST_ONE_PASS_COMPRESSION_QUALITY mode. */ | ||||||||
| 95 | int small_table_[1 << 10]; /* 4KiB */ | ||||||||
| 96 | int* large_table_; /* Allocated only when needed */ | ||||||||
| 97 | size_t large_table_size_; | ||||||||
| 98 | /* Command and distance prefix codes (each 64 symbols, stored back-to-back) | ||||||||
| 99 | used for the next block in FAST_ONE_PASS_COMPRESSION_QUALITY. The command | ||||||||
| 100 | prefix code is over a smaller alphabet with the following 64 symbols: | ||||||||
| 101 | 0 - 15: insert length code 0, copy length code 0 - 15, same distance | ||||||||
| 102 | 16 - 39: insert length code 0, copy length code 0 - 23 | ||||||||
| 103 | 40 - 63: insert length code 0 - 23, copy length code 0 | ||||||||
| 104 | Note that symbols 16 and 40 represent the same code in the full alphabet, | ||||||||
| 105 | but we do not use either of them in FAST_ONE_PASS_COMPRESSION_QUALITY. */ | ||||||||
| 106 | uint8_t cmd_depths_[128]; | ||||||||
| 107 | uint16_t cmd_bits_[128]; | ||||||||
| 108 | /* The compressed form of the command and distance prefix codes for the next | ||||||||
| 109 | block in FAST_ONE_PASS_COMPRESSION_QUALITY. */ | ||||||||
| 110 | uint8_t cmd_code_[512]; | ||||||||
| 111 | size_t cmd_code_numbits_; | ||||||||
| 112 | /* Command and literal buffers for FAST_TWO_PASS_COMPRESSION_QUALITY. */ | ||||||||
| 113 | uint32_t* command_buf_; | ||||||||
| 114 | uint8_t* literal_buf_; | ||||||||
| 115 | |||||||||
| 116 | uint8_t* next_out_; | ||||||||
| 117 | size_t available_out_; | ||||||||
| 118 | size_t total_out_; | ||||||||
| 119 | /* Temporary buffer for padding flush bits or metadata block header / body. */ | ||||||||
| 120 | union { | ||||||||
| 121 | uint64_t u64[2]; | ||||||||
| 122 | uint8_t u8[16]; | ||||||||
| 123 | } tiny_buf_; | ||||||||
| 124 | uint32_t remaining_metadata_bytes_; | ||||||||
| 125 | BrotliEncoderStreamState stream_state_; | ||||||||
| 126 | |||||||||
| 127 | BROTLI_BOOLint is_last_block_emitted_; | ||||||||
| 128 | BROTLI_BOOLint is_initialized_; | ||||||||
| 129 | } BrotliEncoderStateStruct; | ||||||||
| 130 | |||||||||
| 131 | static size_t InputBlockSize(BrotliEncoderState* s) { | ||||||||
| 132 | return (size_t)1 << s->params.lgblock; | ||||||||
| 133 | } | ||||||||
| 134 | |||||||||
| 135 | static uint64_t UnprocessedInputSize(BrotliEncoderState* s) { | ||||||||
| 136 | return s->input_pos_ - s->last_processed_pos_; | ||||||||
| 137 | } | ||||||||
| 138 | |||||||||
| 139 | static size_t RemainingInputBlockSize(BrotliEncoderState* s) { | ||||||||
| 140 | const uint64_t delta = UnprocessedInputSize(s); | ||||||||
| 141 | size_t block_size = InputBlockSize(s); | ||||||||
| 142 | if (delta >= block_size) return 0; | ||||||||
| 143 | return block_size - (size_t)delta; | ||||||||
| 144 | } | ||||||||
| 145 | |||||||||
| 146 | BROTLI_BOOLint BrotliEncoderSetParameter( | ||||||||
| 147 | BrotliEncoderState* state, BrotliEncoderParameter p, uint32_t value) { | ||||||||
| 148 | /* Changing parameters on the fly is not implemented yet. */ | ||||||||
| 149 | if (state->is_initialized_) return BROTLI_FALSE0; | ||||||||
| 150 | /* TODO: Validate/clamp parameters here. */ | ||||||||
| 151 | switch (p) { | ||||||||
| 152 | case BROTLI_PARAM_MODE: | ||||||||
| 153 | state->params.mode = (BrotliEncoderMode)value; | ||||||||
| 154 | return BROTLI_TRUE1; | ||||||||
| 155 | |||||||||
| 156 | case BROTLI_PARAM_QUALITY: | ||||||||
| 157 | state->params.quality = (int)value; | ||||||||
| 158 | return BROTLI_TRUE1; | ||||||||
| 159 | |||||||||
| 160 | case BROTLI_PARAM_LGWIN: | ||||||||
| 161 | state->params.lgwin = (int)value; | ||||||||
| 162 | return BROTLI_TRUE1; | ||||||||
| 163 | |||||||||
| 164 | case BROTLI_PARAM_LGBLOCK: | ||||||||
| 165 | state->params.lgblock = (int)value; | ||||||||
| 166 | return BROTLI_TRUE1; | ||||||||
| 167 | |||||||||
| 168 | case BROTLI_PARAM_DISABLE_LITERAL_CONTEXT_MODELING: | ||||||||
| 169 | if ((value != 0) && (value != 1)) return BROTLI_FALSE0; | ||||||||
| 170 | state->params.disable_literal_context_modeling = TO_BROTLI_BOOL(!!value)(!!(!!value) ? 1 : 0); | ||||||||
| 171 | return BROTLI_TRUE1; | ||||||||
| 172 | |||||||||
| 173 | case BROTLI_PARAM_SIZE_HINT: | ||||||||
| 174 | state->params.size_hint = value; | ||||||||
| 175 | return BROTLI_TRUE1; | ||||||||
| 176 | |||||||||
| 177 | case BROTLI_PARAM_LARGE_WINDOW: | ||||||||
| 178 | state->params.large_window = TO_BROTLI_BOOL(!!value)(!!(!!value) ? 1 : 0); | ||||||||
| 179 | return BROTLI_TRUE1; | ||||||||
| 180 | |||||||||
| 181 | case BROTLI_PARAM_NPOSTFIX: | ||||||||
| 182 | state->params.dist.distance_postfix_bits = value; | ||||||||
| 183 | return BROTLI_TRUE1; | ||||||||
| 184 | |||||||||
| 185 | case BROTLI_PARAM_NDIRECT: | ||||||||
| 186 | state->params.dist.num_direct_distance_codes = value; | ||||||||
| 187 | return BROTLI_TRUE1; | ||||||||
| 188 | |||||||||
| 189 | case BROTLI_PARAM_STREAM_OFFSET: | ||||||||
| 190 | if (value > (1u << 30)) return BROTLI_FALSE0; | ||||||||
| 191 | state->params.stream_offset = value; | ||||||||
| 192 | return BROTLI_TRUE1; | ||||||||
| 193 | |||||||||
| 194 | default: return BROTLI_FALSE0; | ||||||||
| 195 | } | ||||||||
| 196 | } | ||||||||
| 197 | |||||||||
| 198 | /* Wraps 64-bit input position to 32-bit ring-buffer position preserving | ||||||||
| 199 | "not-a-first-lap" feature. */ | ||||||||
| 200 | static uint32_t WrapPosition(uint64_t position) { | ||||||||
| 201 | uint32_t result = (uint32_t)position; | ||||||||
| 202 | uint64_t gb = position >> 30; | ||||||||
| 203 | if (gb > 2) { | ||||||||
| 204 | /* Wrap every 2GiB; The first 3GB are continuous. */ | ||||||||
| 205 | result = (result & ((1u << 30) - 1)) | ((uint32_t)((gb - 1) & 1) + 1) << 30; | ||||||||
| 206 | } | ||||||||
| 207 | return result; | ||||||||
| 208 | } | ||||||||
| 209 | |||||||||
| 210 | static uint8_t* GetBrotliStorage(BrotliEncoderState* s, size_t size) { | ||||||||
| 211 | MemoryManager* m = &s->memory_manager_; | ||||||||
| 212 | if (s->storage_size_ < size) { | ||||||||
| 213 | BROTLI_FREE(m, s->storage_){ BrotliFree((m), (s->storage_)); s->storage_ = ((void* )0); }; | ||||||||
| 214 | s->storage_ = BROTLI_ALLOC(m, uint8_t, size)((size) > 0 ? ((uint8_t*)BrotliAllocate((m), (size) * sizeof (uint8_t))) : ((void*)0)); | ||||||||
| 215 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(s->storage_)(!!0)) return NULL((void*)0); | ||||||||
| 216 | s->storage_size_ = size; | ||||||||
| 217 | } | ||||||||
| 218 | return s->storage_; | ||||||||
| 219 | } | ||||||||
| 220 | |||||||||
| 221 | static size_t HashTableSize(size_t max_table_size, size_t input_size) { | ||||||||
| 222 | size_t htsize = 256; | ||||||||
| 223 | while (htsize < max_table_size && htsize < input_size) { | ||||||||
| 224 | htsize <<= 1; | ||||||||
| 225 | } | ||||||||
| 226 | return htsize; | ||||||||
| 227 | } | ||||||||
| 228 | |||||||||
| 229 | static int* GetHashTable(BrotliEncoderState* s, int quality, | ||||||||
| 230 | size_t input_size, size_t* table_size) { | ||||||||
| 231 | /* Use smaller hash table when input.size() is smaller, since we | ||||||||
| 232 | fill the table, incurring O(hash table size) overhead for | ||||||||
| 233 | compression, and if the input is short, we won't need that | ||||||||
| 234 | many hash table entries anyway. */ | ||||||||
| 235 | MemoryManager* m = &s->memory_manager_; | ||||||||
| 236 | const size_t max_table_size = MaxHashTableSize(quality); | ||||||||
| 237 | size_t htsize = HashTableSize(max_table_size, input_size); | ||||||||
| 238 | int* table; | ||||||||
| 239 | BROTLI_DCHECK(max_table_size >= 256); | ||||||||
| 240 | if (quality == FAST_ONE_PASS_COMPRESSION_QUALITY0) { | ||||||||
| 241 | /* Only odd shifts are supported by fast-one-pass. */ | ||||||||
| 242 | if ((htsize & 0xAAAAA) == 0) { | ||||||||
| 243 | htsize <<= 1; | ||||||||
| 244 | } | ||||||||
| 245 | } | ||||||||
| 246 | |||||||||
| 247 | if (htsize <= sizeof(s->small_table_) / sizeof(s->small_table_[0])) { | ||||||||
| 248 | table = s->small_table_; | ||||||||
| 249 | } else { | ||||||||
| 250 | if (htsize > s->large_table_size_) { | ||||||||
| 251 | s->large_table_size_ = htsize; | ||||||||
| 252 | BROTLI_FREE(m, s->large_table_){ BrotliFree((m), (s->large_table_)); s->large_table_ = ((void*)0); }; | ||||||||
| 253 | s->large_table_ = BROTLI_ALLOC(m, int, htsize)((htsize) > 0 ? ((int*)BrotliAllocate((m), (htsize) * sizeof (int))) : ((void*)0)); | ||||||||
| 254 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(s->large_table_)(!!0)) return 0; | ||||||||
| 255 | } | ||||||||
| 256 | table = s->large_table_; | ||||||||
| 257 | } | ||||||||
| 258 | |||||||||
| 259 | *table_size = htsize; | ||||||||
| 260 | memset(table, 0, htsize * sizeof(*table)); | ||||||||
| 261 | return table; | ||||||||
| 262 | } | ||||||||
| 263 | |||||||||
| 264 | static void EncodeWindowBits(int lgwin, BROTLI_BOOLint large_window, | ||||||||
| 265 | uint16_t* last_bytes, uint8_t* last_bytes_bits) { | ||||||||
| 266 | if (large_window) { | ||||||||
| 267 | *last_bytes = (uint16_t)(((lgwin & 0x3F) << 8) | 0x11); | ||||||||
| 268 | *last_bytes_bits = 14; | ||||||||
| 269 | } else { | ||||||||
| 270 | if (lgwin == 16) { | ||||||||
| 271 | *last_bytes = 0; | ||||||||
| 272 | *last_bytes_bits = 1; | ||||||||
| 273 | } else if (lgwin == 17) { | ||||||||
| 274 | *last_bytes = 1; | ||||||||
| 275 | *last_bytes_bits = 7; | ||||||||
| 276 | } else if (lgwin > 17) { | ||||||||
| 277 | *last_bytes = (uint16_t)(((lgwin - 17) << 1) | 0x01); | ||||||||
| 278 | *last_bytes_bits = 4; | ||||||||
| 279 | } else { | ||||||||
| 280 | *last_bytes = (uint16_t)(((lgwin - 8) << 4) | 0x01); | ||||||||
| 281 | *last_bytes_bits = 7; | ||||||||
| 282 | } | ||||||||
| 283 | } | ||||||||
| 284 | } | ||||||||
| 285 | |||||||||
| 286 | /* Initializes the command and distance prefix codes for the first block. */ | ||||||||
| 287 | static void InitCommandPrefixCodes(uint8_t cmd_depths[128], | ||||||||
| 288 | uint16_t cmd_bits[128], | ||||||||
| 289 | uint8_t cmd_code[512], | ||||||||
| 290 | size_t* cmd_code_numbits) { | ||||||||
| 291 | static const uint8_t kDefaultCommandDepths[128] = { | ||||||||
| 292 | 0, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, | ||||||||
| 293 | 0, 0, 0, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, | ||||||||
| 294 | 7, 7, 10, 10, 10, 10, 10, 10, 0, 4, 4, 5, 5, 5, 6, 6, | ||||||||
| 295 | 7, 8, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, | ||||||||
| 296 | 5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 297 | 6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4, | ||||||||
| 298 | 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 8, 10, | ||||||||
| 299 | 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, | ||||||||
| 300 | }; | ||||||||
| 301 | static const uint16_t kDefaultCommandBits[128] = { | ||||||||
| 302 | 0, 0, 8, 9, 3, 35, 7, 71, | ||||||||
| 303 | 39, 103, 23, 47, 175, 111, 239, 31, | ||||||||
| 304 | 0, 0, 0, 4, 12, 2, 10, 6, | ||||||||
| 305 | 13, 29, 11, 43, 27, 59, 87, 55, | ||||||||
| 306 | 15, 79, 319, 831, 191, 703, 447, 959, | ||||||||
| 307 | 0, 14, 1, 25, 5, 21, 19, 51, | ||||||||
| 308 | 119, 159, 95, 223, 479, 991, 63, 575, | ||||||||
| 309 | 127, 639, 383, 895, 255, 767, 511, 1023, | ||||||||
| 310 | 14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 311 | 27, 59, 7, 39, 23, 55, 30, 1, 17, 9, 25, 5, 0, 8, 4, 12, | ||||||||
| 312 | 2, 10, 6, 21, 13, 29, 3, 19, 11, 15, 47, 31, 95, 63, 127, 255, | ||||||||
| 313 | 767, 2815, 1791, 3839, 511, 2559, 1535, 3583, 1023, 3071, 2047, 4095, | ||||||||
| 314 | }; | ||||||||
| 315 | static const uint8_t kDefaultCommandCode[] = { | ||||||||
| 316 | 0xff, 0x77, 0xd5, 0xbf, 0xe7, 0xde, 0xea, 0x9e, 0x51, 0x5d, 0xde, 0xc6, | ||||||||
| 317 | 0x70, 0x57, 0xbc, 0x58, 0x58, 0x58, 0xd8, 0xd8, 0x58, 0xd5, 0xcb, 0x8c, | ||||||||
| 318 | 0xea, 0xe0, 0xc3, 0x87, 0x1f, 0x83, 0xc1, 0x60, 0x1c, 0x67, 0xb2, 0xaa, | ||||||||
| 319 | 0x06, 0x83, 0xc1, 0x60, 0x30, 0x18, 0xcc, 0xa1, 0xce, 0x88, 0x54, 0x94, | ||||||||
| 320 | 0x46, 0xe1, 0xb0, 0xd0, 0x4e, 0xb2, 0xf7, 0x04, 0x00, | ||||||||
| 321 | }; | ||||||||
| 322 | static const size_t kDefaultCommandCodeNumBits = 448; | ||||||||
| 323 | COPY_ARRAY(cmd_depths, kDefaultCommandDepths)memcpy(cmd_depths, kDefaultCommandDepths, sizeof(kDefaultCommandDepths ));; | ||||||||
| 324 | COPY_ARRAY(cmd_bits, kDefaultCommandBits)memcpy(cmd_bits, kDefaultCommandBits, sizeof(kDefaultCommandBits ));; | ||||||||
| 325 | |||||||||
| 326 | /* Initialize the pre-compressed form of the command and distance prefix | ||||||||
| 327 | codes. */ | ||||||||
| 328 | COPY_ARRAY(cmd_code, kDefaultCommandCode)memcpy(cmd_code, kDefaultCommandCode, sizeof(kDefaultCommandCode ));; | ||||||||
| 329 | *cmd_code_numbits = kDefaultCommandCodeNumBits; | ||||||||
| 330 | } | ||||||||
| 331 | |||||||||
| 332 | /* Decide about the context map based on the ability of the prediction | ||||||||
| 333 | ability of the previous byte UTF8-prefix on the next byte. The | ||||||||
| 334 | prediction ability is calculated as Shannon entropy. Here we need | ||||||||
| 335 | Shannon entropy instead of 'BitsEntropy' since the prefix will be | ||||||||
| 336 | encoded with the remaining 6 bits of the following byte, and | ||||||||
| 337 | BitsEntropy will assume that symbol to be stored alone using Huffman | ||||||||
| 338 | coding. */ | ||||||||
| 339 | static void ChooseContextMap(int quality, | ||||||||
| 340 | uint32_t* bigram_histo, | ||||||||
| 341 | size_t* num_literal_contexts, | ||||||||
| 342 | const uint32_t** literal_context_map) { | ||||||||
| 343 | static const uint32_t kStaticContextMapContinuation[64] = { | ||||||||
| 344 | 1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 345 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 346 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 347 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 348 | }; | ||||||||
| 349 | static const uint32_t kStaticContextMapSimpleUTF8[64] = { | ||||||||
| 350 | 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 351 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 352 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 353 | 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, | ||||||||
| 354 | }; | ||||||||
| 355 | |||||||||
| 356 | uint32_t monogram_histo[3] = { 0 }; | ||||||||
| 357 | uint32_t two_prefix_histo[6] = { 0 }; | ||||||||
| 358 | size_t total; | ||||||||
| 359 | size_t i; | ||||||||
| 360 | size_t dummy; | ||||||||
| 361 | double entropy[4]; | ||||||||
| 362 | for (i = 0; i < 9; ++i) { | ||||||||
| 363 | monogram_histo[i % 3] += bigram_histo[i]; | ||||||||
| 364 | two_prefix_histo[i % 6] += bigram_histo[i]; | ||||||||
| 365 | } | ||||||||
| 366 | entropy[1] = ShannonEntropy(monogram_histo, 3, &dummy); | ||||||||
| 367 | entropy[2] = (ShannonEntropy(two_prefix_histo, 3, &dummy) + | ||||||||
| 368 | ShannonEntropy(two_prefix_histo + 3, 3, &dummy)); | ||||||||
| 369 | entropy[3] = 0; | ||||||||
| 370 | for (i = 0; i < 3; ++i) { | ||||||||
| 371 | entropy[3] += ShannonEntropy(bigram_histo + 3 * i, 3, &dummy); | ||||||||
| 372 | } | ||||||||
| 373 | |||||||||
| 374 | total = monogram_histo[0] + monogram_histo[1] + monogram_histo[2]; | ||||||||
| 375 | BROTLI_DCHECK(total != 0); | ||||||||
| 376 | entropy[0] = 1.0 / (double)total; | ||||||||
| 377 | entropy[1] *= entropy[0]; | ||||||||
| 378 | entropy[2] *= entropy[0]; | ||||||||
| 379 | entropy[3] *= entropy[0]; | ||||||||
| 380 | |||||||||
| 381 | if (quality < MIN_QUALITY_FOR_HQ_CONTEXT_MODELING7) { | ||||||||
| 382 | /* 3 context models is a bit slower, don't use it at lower qualities. */ | ||||||||
| 383 | entropy[3] = entropy[1] * 10; | ||||||||
| 384 | } | ||||||||
| 385 | /* If expected savings by symbol are less than 0.2 bits, skip the | ||||||||
| 386 | context modeling -- in exchange for faster decoding speed. */ | ||||||||
| 387 | if (entropy[1] - entropy[2] < 0.2 && | ||||||||
| 388 | entropy[1] - entropy[3] < 0.2) { | ||||||||
| 389 | *num_literal_contexts = 1; | ||||||||
| 390 | } else if (entropy[2] - entropy[3] < 0.02) { | ||||||||
| 391 | *num_literal_contexts = 2; | ||||||||
| 392 | *literal_context_map = kStaticContextMapSimpleUTF8; | ||||||||
| 393 | } else { | ||||||||
| 394 | *num_literal_contexts = 3; | ||||||||
| 395 | *literal_context_map = kStaticContextMapContinuation; | ||||||||
| 396 | } | ||||||||
| 397 | } | ||||||||
| 398 | |||||||||
| 399 | /* Decide if we want to use a more complex static context map containing 13 | ||||||||
| 400 | context values, based on the entropy reduction of histograms over the | ||||||||
| 401 | first 5 bits of literals. */ | ||||||||
| 402 | static BROTLI_BOOLint ShouldUseComplexStaticContextMap(const uint8_t* input, | ||||||||
| 403 | size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint, | ||||||||
| 404 | size_t* num_literal_contexts, const uint32_t** literal_context_map) { | ||||||||
| 405 | static const uint32_t kStaticContextMapComplexUTF8[64] = { | ||||||||
| 406 | 11, 11, 12, 12, /* 0 special */ | ||||||||
| 407 | 0, 0, 0, 0, /* 4 lf */ | ||||||||
| 408 | 1, 1, 9, 9, /* 8 space */ | ||||||||
| 409 | 2, 2, 2, 2, /* !, first after space/lf and after something else. */ | ||||||||
| 410 | 1, 1, 1, 1, /* " */ | ||||||||
| 411 | 8, 3, 3, 3, /* % */ | ||||||||
| 412 | 1, 1, 1, 1, /* ({[ */ | ||||||||
| 413 | 2, 2, 2, 2, /* }]) */ | ||||||||
| 414 | 8, 4, 4, 4, /* :; */ | ||||||||
| 415 | 8, 7, 4, 4, /* . */ | ||||||||
| 416 | 8, 0, 0, 0, /* > */ | ||||||||
| 417 | 3, 3, 3, 3, /* [0..9] */ | ||||||||
| 418 | 5, 5, 10, 5, /* [A-Z] */ | ||||||||
| 419 | 5, 5, 10, 5, | ||||||||
| 420 | 6, 6, 6, 6, /* [a-z] */ | ||||||||
| 421 | 6, 6, 6, 6, | ||||||||
| 422 | }; | ||||||||
| 423 | BROTLI_UNUSED(quality)(void)(quality); | ||||||||
| 424 | /* Try the more complex static context map only for long data. */ | ||||||||
| 425 | if (size_hint < (1 << 20)) { | ||||||||
| 426 | return BROTLI_FALSE0; | ||||||||
| 427 | } else { | ||||||||
| 428 | const size_t end_pos = start_pos + length; | ||||||||
| 429 | /* To make entropy calculations faster and to fit on the stack, we collect | ||||||||
| 430 | histograms over the 5 most significant bits of literals. One histogram | ||||||||
| 431 | without context and 13 additional histograms for each context value. */ | ||||||||
| 432 | uint32_t combined_histo[32] = { 0 }; | ||||||||
| 433 | uint32_t context_histo[13][32] = { { 0 } }; | ||||||||
| 434 | uint32_t total = 0; | ||||||||
| 435 | double entropy[3]; | ||||||||
| 436 | size_t dummy; | ||||||||
| 437 | size_t i; | ||||||||
| 438 | ContextLut utf8_lut = BROTLI_CONTEXT_LUT(CONTEXT_UTF8)(&_kBrotliContextLookupTable[(CONTEXT_UTF8) << 9]); | ||||||||
| 439 | for (; start_pos + 64 <= end_pos; start_pos += 4096) { | ||||||||
| 440 | const size_t stride_end_pos = start_pos + 64; | ||||||||
| 441 | uint8_t prev2 = input[start_pos & mask]; | ||||||||
| 442 | uint8_t prev1 = input[(start_pos + 1) & mask]; | ||||||||
| 443 | size_t pos; | ||||||||
| 444 | /* To make the analysis of the data faster we only examine 64 byte long | ||||||||
| 445 | strides at every 4kB intervals. */ | ||||||||
| 446 | for (pos = start_pos + 2; pos < stride_end_pos; ++pos) { | ||||||||
| 447 | const uint8_t literal = input[pos & mask]; | ||||||||
| 448 | const uint8_t context = (uint8_t)kStaticContextMapComplexUTF8[ | ||||||||
| 449 | BROTLI_CONTEXT(prev1, prev2, utf8_lut)((utf8_lut)[prev1] | ((utf8_lut) + 256)[prev2])]; | ||||||||
| 450 | ++total; | ||||||||
| 451 | ++combined_histo[literal >> 3]; | ||||||||
| 452 | ++context_histo[context][literal >> 3]; | ||||||||
| 453 | prev2 = prev1; | ||||||||
| 454 | prev1 = literal; | ||||||||
| 455 | } | ||||||||
| 456 | } | ||||||||
| 457 | entropy[1] = ShannonEntropy(combined_histo, 32, &dummy); | ||||||||
| 458 | entropy[2] = 0; | ||||||||
| 459 | for (i = 0; i < 13; ++i) { | ||||||||
| 460 | entropy[2] += ShannonEntropy(&context_histo[i][0], 32, &dummy); | ||||||||
| 461 | } | ||||||||
| 462 | entropy[0] = 1.0 / (double)total; | ||||||||
| 463 | entropy[1] *= entropy[0]; | ||||||||
| 464 | entropy[2] *= entropy[0]; | ||||||||
| 465 | /* The triggering heuristics below were tuned by compressing the individual | ||||||||
| 466 | files of the silesia corpus. If we skip this kind of context modeling | ||||||||
| 467 | for not very well compressible input (i.e. entropy using context modeling | ||||||||
| 468 | is 60% of maximal entropy) or if expected savings by symbol are less | ||||||||
| 469 | than 0.2 bits, then in every case when it triggers, the final compression | ||||||||
| 470 | ratio is improved. Note however that this heuristics might be too strict | ||||||||
| 471 | for some cases and could be tuned further. */ | ||||||||
| 472 | if (entropy[2] > 3.0 || entropy[1] - entropy[2] < 0.2) { | ||||||||
| 473 | return BROTLI_FALSE0; | ||||||||
| 474 | } else { | ||||||||
| 475 | *num_literal_contexts = 13; | ||||||||
| 476 | *literal_context_map = kStaticContextMapComplexUTF8; | ||||||||
| 477 | return BROTLI_TRUE1; | ||||||||
| 478 | } | ||||||||
| 479 | } | ||||||||
| 480 | } | ||||||||
| 481 | |||||||||
| 482 | static void DecideOverLiteralContextModeling(const uint8_t* input, | ||||||||
| 483 | size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint, | ||||||||
| 484 | size_t* num_literal_contexts, const uint32_t** literal_context_map) { | ||||||||
| 485 | if (quality < MIN_QUALITY_FOR_CONTEXT_MODELING5 || length < 64) { | ||||||||
| 486 | return; | ||||||||
| 487 | } else if (ShouldUseComplexStaticContextMap( | ||||||||
| 488 | input, start_pos, length, mask, quality, size_hint, | ||||||||
| 489 | num_literal_contexts, literal_context_map)) { | ||||||||
| 490 | /* Context map was already set, nothing else to do. */ | ||||||||
| 491 | } else { | ||||||||
| 492 | /* Gather bi-gram data of the UTF8 byte prefixes. To make the analysis of | ||||||||
| 493 | UTF8 data faster we only examine 64 byte long strides at every 4kB | ||||||||
| 494 | intervals. */ | ||||||||
| 495 | const size_t end_pos = start_pos + length; | ||||||||
| 496 | uint32_t bigram_prefix_histo[9] = { 0 }; | ||||||||
| 497 | for (; start_pos + 64 <= end_pos; start_pos += 4096) { | ||||||||
| 498 | static const int lut[4] = { 0, 0, 1, 2 }; | ||||||||
| 499 | const size_t stride_end_pos = start_pos + 64; | ||||||||
| 500 | int prev = lut[input[start_pos & mask] >> 6] * 3; | ||||||||
| 501 | size_t pos; | ||||||||
| 502 | for (pos = start_pos + 1; pos < stride_end_pos; ++pos) { | ||||||||
| 503 | const uint8_t literal = input[pos & mask]; | ||||||||
| 504 | ++bigram_prefix_histo[prev + lut[literal >> 6]]; | ||||||||
| 505 | prev = lut[literal >> 6] * 3; | ||||||||
| 506 | } | ||||||||
| 507 | } | ||||||||
| 508 | ChooseContextMap(quality, &bigram_prefix_histo[0], num_literal_contexts, | ||||||||
| 509 | literal_context_map); | ||||||||
| 510 | } | ||||||||
| 511 | } | ||||||||
| 512 | |||||||||
| 513 | static BROTLI_BOOLint ShouldCompress( | ||||||||
| 514 | const uint8_t* data, const size_t mask, const uint64_t last_flush_pos, | ||||||||
| 515 | const size_t bytes, const size_t num_literals, const size_t num_commands) { | ||||||||
| 516 | /* TODO: find more precise minimal block overhead. */ | ||||||||
| 517 | if (bytes <= 2) return BROTLI_FALSE0; | ||||||||
| 518 | if (num_commands < (bytes >> 8) + 2) { | ||||||||
| 519 | if ((double)num_literals > 0.99 * (double)bytes) { | ||||||||
| 520 | uint32_t literal_histo[256] = { 0 }; | ||||||||
| 521 | static const uint32_t kSampleRate = 13; | ||||||||
| 522 | static const double kMinEntropy = 7.92; | ||||||||
| 523 | const double bit_cost_threshold = | ||||||||
| 524 | (double)bytes * kMinEntropy / kSampleRate; | ||||||||
| 525 | size_t t = (bytes + kSampleRate - 1) / kSampleRate; | ||||||||
| 526 | uint32_t pos = (uint32_t)last_flush_pos; | ||||||||
| 527 | size_t i; | ||||||||
| 528 | for (i = 0; i < t; i++) { | ||||||||
| 529 | ++literal_histo[data[pos & mask]]; | ||||||||
| 530 | pos += kSampleRate; | ||||||||
| 531 | } | ||||||||
| 532 | if (BitsEntropy(literal_histo, 256) > bit_cost_threshold) { | ||||||||
| 533 | return BROTLI_FALSE0; | ||||||||
| 534 | } | ||||||||
| 535 | } | ||||||||
| 536 | } | ||||||||
| 537 | return BROTLI_TRUE1; | ||||||||
| 538 | } | ||||||||
| 539 | |||||||||
| 540 | /* Chooses the literal context mode for a metablock */ | ||||||||
| 541 | static ContextType ChooseContextMode(const BrotliEncoderParams* params, | ||||||||
| 542 | const uint8_t* data, const size_t pos, const size_t mask, | ||||||||
| 543 | const size_t length) { | ||||||||
| 544 | /* We only do the computation for the option of something else than | ||||||||
| 545 | CONTEXT_UTF8 for the highest qualities */ | ||||||||
| 546 | if (params->quality >= MIN_QUALITY_FOR_HQ_BLOCK_SPLITTING10 && | ||||||||
| 547 | !BrotliIsMostlyUTF8(data, pos, mask, length, kMinUTF8Ratio)) { | ||||||||
| 548 | return CONTEXT_SIGNED; | ||||||||
| 549 | } | ||||||||
| 550 | return CONTEXT_UTF8; | ||||||||
| 551 | } | ||||||||
| 552 | |||||||||
| 553 | static void WriteMetaBlockInternal(MemoryManager* m, | ||||||||
| 554 | const uint8_t* data, | ||||||||
| 555 | const size_t mask, | ||||||||
| 556 | const uint64_t last_flush_pos, | ||||||||
| 557 | const size_t bytes, | ||||||||
| 558 | const BROTLI_BOOLint is_last, | ||||||||
| 559 | ContextType literal_context_mode, | ||||||||
| 560 | const BrotliEncoderParams* params, | ||||||||
| 561 | const uint8_t prev_byte, | ||||||||
| 562 | const uint8_t prev_byte2, | ||||||||
| 563 | const size_t num_literals, | ||||||||
| 564 | const size_t num_commands, | ||||||||
| 565 | Command* commands, | ||||||||
| 566 | const int* saved_dist_cache, | ||||||||
| 567 | int* dist_cache, | ||||||||
| 568 | size_t* storage_ix, | ||||||||
| 569 | uint8_t* storage) { | ||||||||
| 570 | const uint32_t wrapped_last_flush_pos = WrapPosition(last_flush_pos); | ||||||||
| 571 | uint16_t last_bytes; | ||||||||
| 572 | uint8_t last_bytes_bits; | ||||||||
| 573 | ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode)(&_kBrotliContextLookupTable[(literal_context_mode) << 9]); | ||||||||
| 574 | BrotliEncoderParams block_params = *params; | ||||||||
| 575 | |||||||||
| 576 | if (bytes == 0) { | ||||||||
| 577 | /* Write the ISLAST and ISEMPTY bits. */ | ||||||||
| 578 | BrotliWriteBits(2, 3, storage_ix, storage); | ||||||||
| 579 | *storage_ix = (*storage_ix + 7u) & ~7u; | ||||||||
| 580 | return; | ||||||||
| 581 | } | ||||||||
| 582 | |||||||||
| 583 | if (!ShouldCompress(data, mask, last_flush_pos, bytes, | ||||||||
| 584 | num_literals, num_commands)) { | ||||||||
| 585 | /* Restore the distance cache, as its last update by | ||||||||
| 586 | CreateBackwardReferences is now unused. */ | ||||||||
| 587 | memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); | ||||||||
| 588 | BrotliStoreUncompressedMetaBlock(is_last, data, | ||||||||
| 589 | wrapped_last_flush_pos, mask, bytes, | ||||||||
| 590 | storage_ix, storage); | ||||||||
| 591 | return; | ||||||||
| 592 | } | ||||||||
| 593 | |||||||||
| 594 | BROTLI_DCHECK(*storage_ix <= 14); | ||||||||
| 595 | last_bytes = (uint16_t)((storage[1] << 8) | storage[0]); | ||||||||
| 596 | last_bytes_bits = (uint8_t)(*storage_ix); | ||||||||
| 597 | if (params->quality <= MAX_QUALITY_FOR_STATIC_ENTROPY_CODES2) { | ||||||||
| 598 | BrotliStoreMetaBlockFast(m, data, wrapped_last_flush_pos, | ||||||||
| 599 | bytes, mask, is_last, params, | ||||||||
| 600 | commands, num_commands, | ||||||||
| 601 | storage_ix, storage); | ||||||||
| 602 | if (BROTLI_IS_OOM(m)(!!0)) return; | ||||||||
| 603 | } else if (params->quality < MIN_QUALITY_FOR_BLOCK_SPLIT4) { | ||||||||
| 604 | BrotliStoreMetaBlockTrivial(m, data, wrapped_last_flush_pos, | ||||||||
| 605 | bytes, mask, is_last, params, | ||||||||
| 606 | commands, num_commands, | ||||||||
| 607 | storage_ix, storage); | ||||||||
| 608 | if (BROTLI_IS_OOM(m)(!!0)) return; | ||||||||
| 609 | } else { | ||||||||
| 610 | MetaBlockSplit mb; | ||||||||
| 611 | InitMetaBlockSplit(&mb); | ||||||||
| 612 | if (params->quality < MIN_QUALITY_FOR_HQ_BLOCK_SPLITTING10) { | ||||||||
| 613 | size_t num_literal_contexts = 1; | ||||||||
| 614 | const uint32_t* literal_context_map = NULL((void*)0); | ||||||||
| 615 | if (!params->disable_literal_context_modeling) { | ||||||||
| 616 | DecideOverLiteralContextModeling( | ||||||||
| 617 | data, wrapped_last_flush_pos, bytes, mask, params->quality, | ||||||||
| 618 | params->size_hint, &num_literal_contexts, | ||||||||
| 619 | &literal_context_map); | ||||||||
| 620 | } | ||||||||
| 621 | BrotliBuildMetaBlockGreedy(m, data, wrapped_last_flush_pos, mask, | ||||||||
| 622 | prev_byte, prev_byte2, literal_context_lut, num_literal_contexts, | ||||||||
| 623 | literal_context_map, commands, num_commands, &mb); | ||||||||
| 624 | if (BROTLI_IS_OOM(m)(!!0)) return; | ||||||||
| 625 | } else { | ||||||||
| 626 | BrotliBuildMetaBlock(m, data, wrapped_last_flush_pos, mask, &block_params, | ||||||||
| 627 | prev_byte, prev_byte2, | ||||||||
| 628 | commands, num_commands, | ||||||||
| 629 | literal_context_mode, | ||||||||
| 630 | &mb); | ||||||||
| 631 | if (BROTLI_IS_OOM(m)(!!0)) return; | ||||||||
| 632 | } | ||||||||
| 633 | if (params->quality >= MIN_QUALITY_FOR_OPTIMIZE_HISTOGRAMS4) { | ||||||||
| 634 | /* The number of distance symbols effectively used for distance | ||||||||
| 635 | histograms. It might be less than distance alphabet size | ||||||||
| 636 | for "Large Window Brotli" (32-bit). */ | ||||||||
| 637 | BrotliOptimizeHistograms(block_params.dist.alphabet_size_limit, &mb); | ||||||||
| 638 | } | ||||||||
| 639 | BrotliStoreMetaBlock(m, data, wrapped_last_flush_pos, bytes, mask, | ||||||||
| 640 | prev_byte, prev_byte2, | ||||||||
| 641 | is_last, | ||||||||
| 642 | &block_params, | ||||||||
| 643 | literal_context_mode, | ||||||||
| 644 | commands, num_commands, | ||||||||
| 645 | &mb, | ||||||||
| 646 | storage_ix, storage); | ||||||||
| 647 | if (BROTLI_IS_OOM(m)(!!0)) return; | ||||||||
| 648 | DestroyMetaBlockSplit(m, &mb); | ||||||||
| 649 | } | ||||||||
| 650 | if (bytes + 4 < (*storage_ix >> 3)) { | ||||||||
| 651 | /* Restore the distance cache and last byte. */ | ||||||||
| 652 | memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); | ||||||||
| 653 | storage[0] = (uint8_t)last_bytes; | ||||||||
| 654 | storage[1] = (uint8_t)(last_bytes >> 8); | ||||||||
| 655 | *storage_ix = last_bytes_bits; | ||||||||
| 656 | BrotliStoreUncompressedMetaBlock(is_last, data, | ||||||||
| 657 | wrapped_last_flush_pos, mask, | ||||||||
| 658 | bytes, storage_ix, storage); | ||||||||
| 659 | } | ||||||||
| 660 | } | ||||||||
| 661 | |||||||||
| 662 | static void ChooseDistanceParams(BrotliEncoderParams* params) { | ||||||||
| 663 | uint32_t distance_postfix_bits = 0; | ||||||||
| 664 | uint32_t num_direct_distance_codes = 0; | ||||||||
| 665 | |||||||||
| 666 | if (params->quality >= MIN_QUALITY_FOR_NONZERO_DISTANCE_PARAMS4) { | ||||||||
| 667 | uint32_t ndirect_msb; | ||||||||
| 668 | if (params->mode == BROTLI_MODE_FONT) { | ||||||||
| 669 | distance_postfix_bits = 1; | ||||||||
| 670 | num_direct_distance_codes = 12; | ||||||||
| 671 | } else { | ||||||||
| 672 | distance_postfix_bits = params->dist.distance_postfix_bits; | ||||||||
| 673 | num_direct_distance_codes = params->dist.num_direct_distance_codes; | ||||||||
| 674 | } | ||||||||
| 675 | ndirect_msb = (num_direct_distance_codes >> distance_postfix_bits) & 0x0F; | ||||||||
| 676 | if (distance_postfix_bits > BROTLI_MAX_NPOSTFIX3 || | ||||||||
| 677 | num_direct_distance_codes > BROTLI_MAX_NDIRECT120 || | ||||||||
| 678 | (ndirect_msb << distance_postfix_bits) != num_direct_distance_codes) { | ||||||||
| 679 | distance_postfix_bits = 0; | ||||||||
| 680 | num_direct_distance_codes = 0; | ||||||||
| 681 | } | ||||||||
| 682 | } | ||||||||
| 683 | |||||||||
| 684 | BrotliInitDistanceParams( | ||||||||
| 685 | params, distance_postfix_bits, num_direct_distance_codes); | ||||||||
| 686 | } | ||||||||
| 687 | |||||||||
| 688 | static BROTLI_BOOLint EnsureInitialized(BrotliEncoderState* s) { | ||||||||
| 689 | if (BROTLI_IS_OOM(&s->memory_manager_)(!!0)) return BROTLI_FALSE0; | ||||||||
| 690 | if (s->is_initialized_) return BROTLI_TRUE1; | ||||||||
| 691 | |||||||||
| 692 | s->last_bytes_bits_ = 0; | ||||||||
| 693 | s->last_bytes_ = 0; | ||||||||
| 694 | s->flint_ = BROTLI_FLINT_DONE; | ||||||||
| 695 | s->remaining_metadata_bytes_ = BROTLI_UINT32_MAX(~((uint32_t)0)); | ||||||||
| 696 | |||||||||
| 697 | SanitizeParams(&s->params); | ||||||||
| 698 | s->params.lgblock = ComputeLgBlock(&s->params); | ||||||||
| 699 | ChooseDistanceParams(&s->params); | ||||||||
| 700 | |||||||||
| 701 | if (s->params.stream_offset != 0) { | ||||||||
| 702 | s->flint_ = BROTLI_FLINT_NEEDS_2_BYTES; | ||||||||
| 703 | /* Poison the distance cache. -16 +- 3 is still less than zero (invalid). */ | ||||||||
| 704 | s->dist_cache_[0] = -16; | ||||||||
| 705 | s->dist_cache_[1] = -16; | ||||||||
| 706 | s->dist_cache_[2] = -16; | ||||||||
| 707 | s->dist_cache_[3] = -16; | ||||||||
| 708 | memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_)); | ||||||||
| 709 | } | ||||||||
| 710 | |||||||||
| 711 | RingBufferSetup(&s->params, &s->ringbuffer_); | ||||||||
| 712 | |||||||||
| 713 | /* Initialize last byte with stream header. */ | ||||||||
| 714 | { | ||||||||
| 715 | int lgwin = s->params.lgwin; | ||||||||
| 716 | if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY0 || | ||||||||
| 717 | s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY1) { | ||||||||
| 718 | lgwin = BROTLI_MAX(int, lgwin, 18)(brotli_max_int((lgwin), (18))); | ||||||||
| 719 | } | ||||||||
| 720 | if (s->params.stream_offset == 0) { | ||||||||
| 721 | EncodeWindowBits(lgwin, s->params.large_window, | ||||||||
| 722 | &s->last_bytes_, &s->last_bytes_bits_); | ||||||||
| 723 | } else { | ||||||||
| 724 | /* Bigger values have the same effect, but could cause overflows. */ | ||||||||
| 725 | s->params.stream_offset = BROTLI_MIN(size_t,(brotli_min_size_t((s->params.stream_offset), ((((size_t)1 << (lgwin)) - 16)))) | ||||||||
| 726 | s->params.stream_offset, BROTLI_MAX_BACKWARD_LIMIT(lgwin))(brotli_min_size_t((s->params.stream_offset), ((((size_t)1 << (lgwin)) - 16)))); | ||||||||
| 727 | } | ||||||||
| 728 | } | ||||||||
| 729 | |||||||||
| 730 | if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY0) { | ||||||||
| 731 | InitCommandPrefixCodes(s->cmd_depths_, s->cmd_bits_, | ||||||||
| 732 | s->cmd_code_, &s->cmd_code_numbits_); | ||||||||
| 733 | } | ||||||||
| 734 | |||||||||
| 735 | s->is_initialized_ = BROTLI_TRUE1; | ||||||||
| 736 | return BROTLI_TRUE1; | ||||||||
| 737 | } | ||||||||
| 738 | |||||||||
| 739 | static void BrotliEncoderInitParams(BrotliEncoderParams* params) { | ||||||||
| 740 | params->mode = BROTLI_DEFAULT_MODEBROTLI_MODE_GENERIC; | ||||||||
| 741 | params->large_window = BROTLI_FALSE0; | ||||||||
| 742 | params->quality = BROTLI_DEFAULT_QUALITY11; | ||||||||
| 743 | params->lgwin = BROTLI_DEFAULT_WINDOW22; | ||||||||
| 744 | params->lgblock = 0; | ||||||||
| 745 | params->stream_offset = 0; | ||||||||
| 746 | params->size_hint = 0; | ||||||||
| 747 | params->disable_literal_context_modeling = BROTLI_FALSE0; | ||||||||
| 748 | BrotliInitEncoderDictionary(¶ms->dictionary); | ||||||||
| 749 | params->dist.distance_postfix_bits = 0; | ||||||||
| 750 | params->dist.num_direct_distance_codes = 0; | ||||||||
| 751 | params->dist.alphabet_size_max = | ||||||||
| 752 | BROTLI_DISTANCE_ALPHABET_SIZE(0, 0, BROTLI_MAX_DISTANCE_BITS)( 16 + (0) + ((24U) << ((0) + 1))); | ||||||||
| 753 | params->dist.alphabet_size_limit = params->dist.alphabet_size_max; | ||||||||
| 754 | params->dist.max_distance = BROTLI_MAX_DISTANCE0x3FFFFFC; | ||||||||
| 755 | } | ||||||||
| 756 | |||||||||
| 757 | static void BrotliEncoderInitState(BrotliEncoderState* s) { | ||||||||
| 758 | BrotliEncoderInitParams(&s->params); | ||||||||
| 759 | s->input_pos_ = 0; | ||||||||
| 760 | s->num_commands_ = 0; | ||||||||
| 761 | s->num_literals_ = 0; | ||||||||
| 762 | s->last_insert_len_ = 0; | ||||||||
| 763 | s->last_flush_pos_ = 0; | ||||||||
| 764 | s->last_processed_pos_ = 0; | ||||||||
| 765 | s->prev_byte_ = 0; | ||||||||
| 766 | s->prev_byte2_ = 0; | ||||||||
| 767 | s->storage_size_ = 0; | ||||||||
| 768 | s->storage_ = 0; | ||||||||
| 769 | HasherInit(&s->hasher_); | ||||||||
| 770 | s->large_table_ = NULL((void*)0); | ||||||||
| 771 | s->large_table_size_ = 0; | ||||||||
| 772 | s->cmd_code_numbits_ = 0; | ||||||||
| 773 | s->command_buf_ = NULL((void*)0); | ||||||||
| 774 | s->literal_buf_ = NULL((void*)0); | ||||||||
| 775 | s->next_out_ = NULL((void*)0); | ||||||||
| 776 | s->available_out_ = 0; | ||||||||
| 777 | s->total_out_ = 0; | ||||||||
| 778 | s->stream_state_ = BROTLI_STREAM_PROCESSING; | ||||||||
| 779 | s->is_last_block_emitted_ = BROTLI_FALSE0; | ||||||||
| 780 | s->is_initialized_ = BROTLI_FALSE0; | ||||||||
| 781 | |||||||||
| 782 | RingBufferInit(&s->ringbuffer_); | ||||||||
| 783 | |||||||||
| 784 | s->commands_ = 0; | ||||||||
| 785 | s->cmd_alloc_size_ = 0; | ||||||||
| 786 | |||||||||
| 787 | /* Initialize distance cache. */ | ||||||||
| 788 | s->dist_cache_[0] = 4; | ||||||||
| 789 | s->dist_cache_[1] = 11; | ||||||||
| 790 | s->dist_cache_[2] = 15; | ||||||||
| 791 | s->dist_cache_[3] = 16; | ||||||||
| 792 | /* Save the state of the distance cache in case we need to restore it for | ||||||||
| 793 | emitting an uncompressed block. */ | ||||||||
| 794 | memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_)); | ||||||||
| 795 | } | ||||||||
| 796 | |||||||||
| 797 | BrotliEncoderState* BrotliEncoderCreateInstance( | ||||||||
| 798 | brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { | ||||||||
| 799 | BrotliEncoderState* state = 0; | ||||||||
| 800 | if (!alloc_func && !free_func) { | ||||||||
| 801 | state = (BrotliEncoderState*)malloc(sizeof(BrotliEncoderState)); | ||||||||
| 802 | } else if (alloc_func && free_func) { | ||||||||
| 803 | state = (BrotliEncoderState*)alloc_func(opaque, sizeof(BrotliEncoderState)); | ||||||||
| 804 | } | ||||||||
| 805 | if (state == 0) { | ||||||||
| 806 | /* BROTLI_DUMP(); */ | ||||||||
| 807 | return 0; | ||||||||
| 808 | } | ||||||||
| 809 | BrotliInitMemoryManager( | ||||||||
| 810 | &state->memory_manager_, alloc_func, free_func, opaque); | ||||||||
| 811 | BrotliEncoderInitState(state); | ||||||||
| 812 | return state; | ||||||||
| 813 | } | ||||||||
| 814 | |||||||||
| 815 | static void BrotliEncoderCleanupState(BrotliEncoderState* s) { | ||||||||
| 816 | MemoryManager* m = &s->memory_manager_; | ||||||||
| 817 | if (BROTLI_IS_OOM(m)(!!0)) { | ||||||||
| 818 | BrotliWipeOutMemoryManager(m); | ||||||||
| 819 | return; | ||||||||
| 820 | } | ||||||||
| 821 | BROTLI_FREE(m, s->storage_){ BrotliFree((m), (s->storage_)); s->storage_ = ((void* )0); }; | ||||||||
| 822 | BROTLI_FREE(m, s->commands_){ BrotliFree((m), (s->commands_)); s->commands_ = ((void *)0); }; | ||||||||
| 823 | RingBufferFree(m, &s->ringbuffer_); | ||||||||
| 824 | DestroyHasher(m, &s->hasher_); | ||||||||
| 825 | BROTLI_FREE(m, s->large_table_){ BrotliFree((m), (s->large_table_)); s->large_table_ = ((void*)0); }; | ||||||||
| 826 | BROTLI_FREE(m, s->command_buf_){ BrotliFree((m), (s->command_buf_)); s->command_buf_ = ((void*)0); }; | ||||||||
| 827 | BROTLI_FREE(m, s->literal_buf_){ BrotliFree((m), (s->literal_buf_)); s->literal_buf_ = ((void*)0); }; | ||||||||
| 828 | } | ||||||||
| 829 | |||||||||
| 830 | /* Deinitializes and frees BrotliEncoderState instance. */ | ||||||||
| 831 | void BrotliEncoderDestroyInstance(BrotliEncoderState* state) { | ||||||||
| 832 | if (!state) { | ||||||||
| 833 | return; | ||||||||
| 834 | } else { | ||||||||
| 835 | MemoryManager* m = &state->memory_manager_; | ||||||||
| 836 | brotli_free_func free_func = m->free_func; | ||||||||
| 837 | void* opaque = m->opaque; | ||||||||
| 838 | BrotliEncoderCleanupState(state); | ||||||||
| 839 | free_func(opaque, state); | ||||||||
| 840 | } | ||||||||
| 841 | } | ||||||||
| 842 | |||||||||
| 843 | /* | ||||||||
| 844 | Copies the given input data to the internal ring buffer of the compressor. | ||||||||
| 845 | No processing of the data occurs at this time and this function can be | ||||||||
| 846 | called multiple times before calling WriteBrotliData() to process the | ||||||||
| 847 | accumulated input. At most input_block_size() bytes of input data can be | ||||||||
| 848 | copied to the ring buffer, otherwise the next WriteBrotliData() will fail. | ||||||||
| 849 | */ | ||||||||
| 850 | static void CopyInputToRingBuffer(BrotliEncoderState* s, | ||||||||
| 851 | const size_t input_size, | ||||||||
| 852 | const uint8_t* input_buffer) { | ||||||||
| 853 | RingBuffer* ringbuffer_ = &s->ringbuffer_; | ||||||||
| 854 | MemoryManager* m = &s->memory_manager_; | ||||||||
| 855 | RingBufferWrite(m, input_buffer, input_size, ringbuffer_); | ||||||||
| 856 | if (BROTLI_IS_OOM(m)(!!0)) return; | ||||||||
| 857 | s->input_pos_ += input_size; | ||||||||
| 858 | |||||||||
| 859 | /* TL;DR: If needed, initialize 7 more bytes in the ring buffer to make the | ||||||||
| 860 | hashing not depend on uninitialized data. This makes compression | ||||||||
| 861 | deterministic and it prevents uninitialized memory warnings in Valgrind. | ||||||||
| 862 | Even without erasing, the output would be valid (but nondeterministic). | ||||||||
| 863 | |||||||||
| 864 | Background information: The compressor stores short (at most 8 bytes) | ||||||||
| 865 | substrings of the input already read in a hash table, and detects | ||||||||
| 866 | repetitions by looking up such substrings in the hash table. If it | ||||||||
| 867 | can find a substring, it checks whether the substring is really there | ||||||||
| 868 | in the ring buffer (or it's just a hash collision). Should the hash | ||||||||
| 869 | table become corrupt, this check makes sure that the output is | ||||||||
| 870 | still valid, albeit the compression ratio would be bad. | ||||||||
| 871 | |||||||||
| 872 | The compressor populates the hash table from the ring buffer as it's | ||||||||
| 873 | reading new bytes from the input. However, at the last few indexes of | ||||||||
| 874 | the ring buffer, there are not enough bytes to build full-length | ||||||||
| 875 | substrings from. Since the hash table always contains full-length | ||||||||
| 876 | substrings, we erase with dummy zeros here to make sure that those | ||||||||
| 877 | substrings will contain zeros at the end instead of uninitialized | ||||||||
| 878 | data. | ||||||||
| 879 | |||||||||
| 880 | Please note that erasing is not necessary (because the | ||||||||
| 881 | memory region is already initialized since he ring buffer | ||||||||
| 882 | has a `tail' that holds a copy of the beginning,) so we | ||||||||
| 883 | skip erasing if we have already gone around at least once in | ||||||||
| 884 | the ring buffer. | ||||||||
| 885 | |||||||||
| 886 | Only clear during the first round of ring-buffer writes. On | ||||||||
| 887 | subsequent rounds data in the ring-buffer would be affected. */ | ||||||||
| 888 | if (ringbuffer_->pos_ <= ringbuffer_->mask_) { | ||||||||
| 889 | /* This is the first time when the ring buffer is being written. | ||||||||
| 890 | We clear 7 bytes just after the bytes that have been copied from | ||||||||
| 891 | the input buffer. | ||||||||
| 892 | |||||||||
| 893 | The ring-buffer has a "tail" that holds a copy of the beginning, | ||||||||
| 894 | but only once the ring buffer has been fully written once, i.e., | ||||||||
| 895 | pos <= mask. For the first time, we need to write values | ||||||||
| 896 | in this tail (where index may be larger than mask), so that | ||||||||
| 897 | we have exactly defined behavior and don't read uninitialized | ||||||||
| 898 | memory. Due to performance reasons, hashing reads data using a | ||||||||
| 899 | LOAD64, which can go 7 bytes beyond the bytes written in the | ||||||||
| 900 | ring-buffer. */ | ||||||||
| 901 | memset(ringbuffer_->buffer_ + ringbuffer_->pos_, 0, 7); | ||||||||
| 902 | } | ||||||||
| 903 | } | ||||||||
| 904 | |||||||||
| 905 | /* Marks all input as processed. | ||||||||
| 906 | Returns true if position wrapping occurs. */ | ||||||||
| 907 | static BROTLI_BOOLint UpdateLastProcessedPos(BrotliEncoderState* s) { | ||||||||
| 908 | uint32_t wrapped_last_processed_pos = WrapPosition(s->last_processed_pos_); | ||||||||
| 909 | uint32_t wrapped_input_pos = WrapPosition(s->input_pos_); | ||||||||
| 910 | s->last_processed_pos_ = s->input_pos_; | ||||||||
| 911 | return TO_BROTLI_BOOL(wrapped_input_pos < wrapped_last_processed_pos)(!!(wrapped_input_pos < wrapped_last_processed_pos) ? 1 : 0 ); | ||||||||
| 912 | } | ||||||||
| 913 | |||||||||
| 914 | static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes, | ||||||||
| 915 | uint32_t* wrapped_last_processed_pos) { | ||||||||
| 916 | Command* last_command = &s->commands_[s->num_commands_ - 1]; | ||||||||
| 917 | const uint8_t* data = s->ringbuffer_.buffer_; | ||||||||
| 918 | const uint32_t mask = s->ringbuffer_.mask_; | ||||||||
| 919 | uint64_t max_backward_distance = | ||||||||
| 920 | (((uint64_t)1) << s->params.lgwin) - BROTLI_WINDOW_GAP16; | ||||||||
| 921 | uint64_t last_copy_len = last_command->copy_len_ & 0x1FFFFFF; | ||||||||
| 922 | uint64_t last_processed_pos = s->last_processed_pos_ - last_copy_len; | ||||||||
| 923 | uint64_t max_distance = last_processed_pos < max_backward_distance ? | ||||||||
| 924 | last_processed_pos : max_backward_distance; | ||||||||
| 925 | uint64_t cmd_dist = (uint64_t)s->dist_cache_[0]; | ||||||||
| 926 | uint32_t distance_code = CommandRestoreDistanceCode(last_command, | ||||||||
| 927 | &s->params.dist); | ||||||||
| 928 | if (distance_code < BROTLI_NUM_DISTANCE_SHORT_CODES16 || | ||||||||
| 929 | distance_code - (BROTLI_NUM_DISTANCE_SHORT_CODES16 - 1) == cmd_dist) { | ||||||||
| 930 | if (cmd_dist <= max_distance) { | ||||||||
| 931 | while (*bytes != 0 && data[*wrapped_last_processed_pos & mask] == | ||||||||
| 932 | data[(*wrapped_last_processed_pos - cmd_dist) & mask]) { | ||||||||
| 933 | last_command->copy_len_++; | ||||||||
| 934 | (*bytes)--; | ||||||||
| 935 | (*wrapped_last_processed_pos)++; | ||||||||
| 936 | } | ||||||||
| 937 | } else { | ||||||||
| 938 | } | ||||||||
| 939 | /* The copy length is at most the metablock size, and thus expressible. */ | ||||||||
| 940 | GetLengthCode(last_command->insert_len_, | ||||||||
| 941 | (size_t)((int)(last_command->copy_len_ & 0x1FFFFFF) + | ||||||||
| 942 | (int)(last_command->copy_len_ >> 25)), | ||||||||
| 943 | TO_BROTLI_BOOL((last_command->dist_prefix_ & 0x3FF) == 0)(!!((last_command->dist_prefix_ & 0x3FF) == 0) ? 1 : 0 ), | ||||||||
| 944 | &last_command->cmd_prefix_); | ||||||||
| 945 | } | ||||||||
| 946 | } | ||||||||
| 947 | |||||||||
| 948 | /* | ||||||||
| 949 | Processes the accumulated input data and sets |*out_size| to the length of | ||||||||
| 950 | the new output meta-block, or to zero if no new output meta-block has been | ||||||||
| 951 | created (in this case the processed input data is buffered internally). | ||||||||
| 952 | If |*out_size| is positive, |*output| points to the start of the output | ||||||||
| 953 | data. If |is_last| or |force_flush| is BROTLI_TRUE, an output meta-block is | ||||||||
| 954 | always created. However, until |is_last| is BROTLI_TRUE encoder may retain up | ||||||||
| 955 | to 7 bits of the last byte of output. To force encoder to dump the remaining | ||||||||
| 956 | bits use WriteMetadata() to append an empty meta-data block. | ||||||||
| 957 | Returns BROTLI_FALSE if the size of the input data is larger than | ||||||||
| 958 | input_block_size(). | ||||||||
| 959 | */ | ||||||||
| 960 | static BROTLI_BOOLint EncodeData( | ||||||||
| 961 | BrotliEncoderState* s, const BROTLI_BOOLint is_last, | ||||||||
| 962 | const BROTLI_BOOLint force_flush, size_t* out_size, uint8_t** output) { | ||||||||
| 963 | const uint64_t delta = UnprocessedInputSize(s); | ||||||||
| 964 | uint32_t bytes = (uint32_t)delta; | ||||||||
| 965 | uint32_t wrapped_last_processed_pos = WrapPosition(s->last_processed_pos_); | ||||||||
| 966 | uint8_t* data; | ||||||||
| 967 | uint32_t mask; | ||||||||
| 968 | MemoryManager* m = &s->memory_manager_; | ||||||||
| 969 | ContextType literal_context_mode; | ||||||||
| 970 | ContextLut literal_context_lut; | ||||||||
| 971 | |||||||||
| 972 | data = s->ringbuffer_.buffer_; | ||||||||
| 973 | mask = s->ringbuffer_.mask_; | ||||||||
| 974 | |||||||||
| 975 | /* Adding more blocks after "last" block is forbidden. */ | ||||||||
| 976 | if (s->is_last_block_emitted_) return BROTLI_FALSE0; | ||||||||
| 977 | if (is_last) s->is_last_block_emitted_ = BROTLI_TRUE1; | ||||||||
| 978 | |||||||||
| 979 | if (delta > InputBlockSize(s)) { | ||||||||
| 980 | return BROTLI_FALSE0; | ||||||||
| 981 | } | ||||||||
| 982 | if (s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY1 && | ||||||||
| 983 | !s->command_buf_) { | ||||||||
| 984 | s->command_buf_ = | ||||||||
| 985 | BROTLI_ALLOC(m, uint32_t, kCompressFragmentTwoPassBlockSize)((kCompressFragmentTwoPassBlockSize) > 0 ? ((uint32_t*)BrotliAllocate ((m), (kCompressFragmentTwoPassBlockSize) * sizeof(uint32_t)) ) : ((void*)0)); | ||||||||
| 986 | s->literal_buf_ = | ||||||||
| 987 | BROTLI_ALLOC(m, uint8_t, kCompressFragmentTwoPassBlockSize)((kCompressFragmentTwoPassBlockSize) > 0 ? ((uint8_t*)BrotliAllocate ((m), (kCompressFragmentTwoPassBlockSize) * sizeof(uint8_t))) : ((void*)0)); | ||||||||
| 988 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(s->command_buf_)(!!0) || | ||||||||
| 989 | BROTLI_IS_NULL(s->literal_buf_)(!!0)) { | ||||||||
| 990 | return BROTLI_FALSE0; | ||||||||
| 991 | } | ||||||||
| 992 | } | ||||||||
| 993 | |||||||||
| 994 | if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY0 || | ||||||||
| 995 | s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY1) { | ||||||||
| 996 | uint8_t* storage; | ||||||||
| 997 | size_t storage_ix = s->last_bytes_bits_; | ||||||||
| 998 | size_t table_size; | ||||||||
| 999 | int* table; | ||||||||
| 1000 | |||||||||
| 1001 | if (delta == 0 && !is_last) { | ||||||||
| 1002 | /* We have no new input data and we don't have to finish the stream, so | ||||||||
| 1003 | nothing to do. */ | ||||||||
| 1004 | *out_size = 0; | ||||||||
| 1005 | return BROTLI_TRUE1; | ||||||||
| 1006 | } | ||||||||
| 1007 | storage = GetBrotliStorage(s, 2 * bytes + 503); | ||||||||
| 1008 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1009 | storage[0] = (uint8_t)s->last_bytes_; | ||||||||
| 1010 | storage[1] = (uint8_t)(s->last_bytes_ >> 8); | ||||||||
| 1011 | table = GetHashTable(s, s->params.quality, bytes, &table_size); | ||||||||
| 1012 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1013 | if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY0) { | ||||||||
| 1014 | BrotliCompressFragmentFast( | ||||||||
| 1015 | m, &data[wrapped_last_processed_pos & mask], | ||||||||
| 1016 | bytes, is_last, | ||||||||
| 1017 | table, table_size, | ||||||||
| 1018 | s->cmd_depths_, s->cmd_bits_, | ||||||||
| 1019 | &s->cmd_code_numbits_, s->cmd_code_, | ||||||||
| 1020 | &storage_ix, storage); | ||||||||
| 1021 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1022 | } else { | ||||||||
| 1023 | BrotliCompressFragmentTwoPass( | ||||||||
| 1024 | m, &data[wrapped_last_processed_pos & mask], | ||||||||
| 1025 | bytes, is_last, | ||||||||
| 1026 | s->command_buf_, s->literal_buf_, | ||||||||
| 1027 | table, table_size, | ||||||||
| 1028 | &storage_ix, storage); | ||||||||
| 1029 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1030 | } | ||||||||
| 1031 | s->last_bytes_ = (uint16_t)(storage[storage_ix >> 3]); | ||||||||
| 1032 | s->last_bytes_bits_ = storage_ix & 7u; | ||||||||
| 1033 | UpdateLastProcessedPos(s); | ||||||||
| 1034 | *output = &storage[0]; | ||||||||
| 1035 | *out_size = storage_ix >> 3; | ||||||||
| 1036 | return BROTLI_TRUE1; | ||||||||
| 1037 | } | ||||||||
| 1038 | |||||||||
| 1039 | { | ||||||||
| 1040 | /* Theoretical max number of commands is 1 per 2 bytes. */ | ||||||||
| 1041 | size_t newsize = s->num_commands_ + bytes / 2 + 1; | ||||||||
| 1042 | if (newsize > s->cmd_alloc_size_) { | ||||||||
| 1043 | Command* new_commands; | ||||||||
| 1044 | /* Reserve a bit more memory to allow merging with a next block | ||||||||
| 1045 | without reallocation: that would impact speed. */ | ||||||||
| 1046 | newsize += (bytes / 4) + 16; | ||||||||
| 1047 | s->cmd_alloc_size_ = newsize; | ||||||||
| 1048 | new_commands = BROTLI_ALLOC(m, Command, newsize)((newsize) > 0 ? ((Command*)BrotliAllocate((m), (newsize) * sizeof(Command))) : ((void*)0)); | ||||||||
| 1049 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(new_commands)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1050 | if (s->commands_) { | ||||||||
| 1051 | memcpy(new_commands, s->commands_, sizeof(Command) * s->num_commands_); | ||||||||
| 1052 | BROTLI_FREE(m, s->commands_){ BrotliFree((m), (s->commands_)); s->commands_ = ((void *)0); }; | ||||||||
| 1053 | } | ||||||||
| 1054 | s->commands_ = new_commands; | ||||||||
| 1055 | } | ||||||||
| 1056 | } | ||||||||
| 1057 | |||||||||
| 1058 | InitOrStitchToPreviousBlock(m, &s->hasher_, data, mask, &s->params, | ||||||||
| 1059 | wrapped_last_processed_pos, bytes, is_last); | ||||||||
| 1060 | |||||||||
| 1061 | literal_context_mode = ChooseContextMode( | ||||||||
| 1062 | &s->params, data, WrapPosition(s->last_flush_pos_), | ||||||||
| 1063 | mask, (size_t)(s->input_pos_ - s->last_flush_pos_)); | ||||||||
| 1064 | literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode)(&_kBrotliContextLookupTable[(literal_context_mode) << 9]); | ||||||||
| 1065 | |||||||||
| 1066 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1067 | |||||||||
| 1068 | if (s->num_commands_ && s->last_insert_len_ == 0) { | ||||||||
| 1069 | ExtendLastCommand(s, &bytes, &wrapped_last_processed_pos); | ||||||||
| 1070 | } | ||||||||
| 1071 | |||||||||
| 1072 | if (s->params.quality == ZOPFLIFICATION_QUALITY10) { | ||||||||
| 1073 | BROTLI_DCHECK(s->params.hasher.type == 10); | ||||||||
| 1074 | BrotliCreateZopfliBackwardReferences(m, bytes, wrapped_last_processed_pos, | ||||||||
| 1075 | data, mask, literal_context_lut, &s->params, | ||||||||
| 1076 | &s->hasher_, s->dist_cache_, | ||||||||
| 1077 | &s->last_insert_len_, &s->commands_[s->num_commands_], | ||||||||
| 1078 | &s->num_commands_, &s->num_literals_); | ||||||||
| 1079 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1080 | } else if (s->params.quality == HQ_ZOPFLIFICATION_QUALITY11) { | ||||||||
| 1081 | BROTLI_DCHECK(s->params.hasher.type == 10); | ||||||||
| 1082 | BrotliCreateHqZopfliBackwardReferences(m, bytes, wrapped_last_processed_pos, | ||||||||
| 1083 | data, mask, literal_context_lut, &s->params, | ||||||||
| 1084 | &s->hasher_, s->dist_cache_, | ||||||||
| 1085 | &s->last_insert_len_, &s->commands_[s->num_commands_], | ||||||||
| 1086 | &s->num_commands_, &s->num_literals_); | ||||||||
| 1087 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1088 | } else { | ||||||||
| 1089 | BrotliCreateBackwardReferences(bytes, wrapped_last_processed_pos, | ||||||||
| 1090 | data, mask, literal_context_lut, &s->params, | ||||||||
| 1091 | &s->hasher_, s->dist_cache_, | ||||||||
| 1092 | &s->last_insert_len_, &s->commands_[s->num_commands_], | ||||||||
| 1093 | &s->num_commands_, &s->num_literals_); | ||||||||
| 1094 | } | ||||||||
| 1095 | |||||||||
| 1096 | { | ||||||||
| 1097 | const size_t max_length = MaxMetablockSize(&s->params); | ||||||||
| 1098 | const size_t max_literals = max_length / 8; | ||||||||
| 1099 | const size_t max_commands = max_length / 8; | ||||||||
| 1100 | const size_t processed_bytes = (size_t)(s->input_pos_ - s->last_flush_pos_); | ||||||||
| 1101 | /* If maximal possible additional block doesn't fit metablock, flush now. */ | ||||||||
| 1102 | /* TODO: Postpone decision until next block arrives? */ | ||||||||
| 1103 | const BROTLI_BOOLint next_input_fits_metablock = TO_BROTLI_BOOL((!!(processed_bytes + InputBlockSize(s) <= max_length) ? 1 : 0) | ||||||||
| 1104 | processed_bytes + InputBlockSize(s) <= max_length)(!!(processed_bytes + InputBlockSize(s) <= max_length) ? 1 : 0); | ||||||||
| 1105 | /* If block splitting is not used, then flush as soon as there is some | ||||||||
| 1106 | amount of commands / literals produced. */ | ||||||||
| 1107 | const BROTLI_BOOLint should_flush = TO_BROTLI_BOOL((!!(s->params.quality < 4 && s->num_literals_ + s->num_commands_ >= 0x2FFF) ? 1 : 0) | ||||||||
| 1108 | s->params.quality < MIN_QUALITY_FOR_BLOCK_SPLIT &&(!!(s->params.quality < 4 && s->num_literals_ + s->num_commands_ >= 0x2FFF) ? 1 : 0) | ||||||||
| 1109 | s->num_literals_ + s->num_commands_ >= MAX_NUM_DELAYED_SYMBOLS)(!!(s->params.quality < 4 && s->num_literals_ + s->num_commands_ >= 0x2FFF) ? 1 : 0); | ||||||||
| 1110 | if (!is_last && !force_flush && !should_flush && | ||||||||
| 1111 | next_input_fits_metablock && | ||||||||
| 1112 | s->num_literals_ < max_literals && | ||||||||
| 1113 | s->num_commands_ < max_commands) { | ||||||||
| 1114 | /* Merge with next input block. Everything will happen later. */ | ||||||||
| 1115 | if (UpdateLastProcessedPos(s)) { | ||||||||
| 1116 | HasherReset(&s->hasher_); | ||||||||
| 1117 | } | ||||||||
| 1118 | *out_size = 0; | ||||||||
| 1119 | return BROTLI_TRUE1; | ||||||||
| 1120 | } | ||||||||
| 1121 | } | ||||||||
| 1122 | |||||||||
| 1123 | /* Create the last insert-only command. */ | ||||||||
| 1124 | if (s->last_insert_len_ > 0) { | ||||||||
| 1125 | InitInsertCommand(&s->commands_[s->num_commands_++], s->last_insert_len_); | ||||||||
| 1126 | s->num_literals_ += s->last_insert_len_; | ||||||||
| 1127 | s->last_insert_len_ = 0; | ||||||||
| 1128 | } | ||||||||
| 1129 | |||||||||
| 1130 | if (!is_last && s->input_pos_ == s->last_flush_pos_) { | ||||||||
| 1131 | /* We have no new input data and we don't have to finish the stream, so | ||||||||
| 1132 | nothing to do. */ | ||||||||
| 1133 | *out_size = 0; | ||||||||
| 1134 | return BROTLI_TRUE1; | ||||||||
| 1135 | } | ||||||||
| 1136 | BROTLI_DCHECK(s->input_pos_ >= s->last_flush_pos_); | ||||||||
| 1137 | BROTLI_DCHECK(s->input_pos_ > s->last_flush_pos_ || is_last); | ||||||||
| 1138 | BROTLI_DCHECK(s->input_pos_ - s->last_flush_pos_ <= 1u << 24); | ||||||||
| 1139 | { | ||||||||
| 1140 | const uint32_t metablock_size = | ||||||||
| 1141 | (uint32_t)(s->input_pos_ - s->last_flush_pos_); | ||||||||
| 1142 | uint8_t* storage = GetBrotliStorage(s, 2 * metablock_size + 503); | ||||||||
| 1143 | size_t storage_ix = s->last_bytes_bits_; | ||||||||
| 1144 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1145 | storage[0] = (uint8_t)s->last_bytes_; | ||||||||
| 1146 | storage[1] = (uint8_t)(s->last_bytes_ >> 8); | ||||||||
| 1147 | WriteMetaBlockInternal( | ||||||||
| 1148 | m, data, mask, s->last_flush_pos_, metablock_size, is_last, | ||||||||
| 1149 | literal_context_mode, &s->params, s->prev_byte_, s->prev_byte2_, | ||||||||
| 1150 | s->num_literals_, s->num_commands_, s->commands_, s->saved_dist_cache_, | ||||||||
| 1151 | s->dist_cache_, &storage_ix, storage); | ||||||||
| 1152 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1153 | s->last_bytes_ = (uint16_t)(storage[storage_ix >> 3]); | ||||||||
| 1154 | s->last_bytes_bits_ = storage_ix & 7u; | ||||||||
| 1155 | s->last_flush_pos_ = s->input_pos_; | ||||||||
| 1156 | if (UpdateLastProcessedPos(s)) { | ||||||||
| 1157 | HasherReset(&s->hasher_); | ||||||||
| 1158 | } | ||||||||
| 1159 | if (s->last_flush_pos_ > 0) { | ||||||||
| 1160 | s->prev_byte_ = data[((uint32_t)s->last_flush_pos_ - 1) & mask]; | ||||||||
| 1161 | } | ||||||||
| 1162 | if (s->last_flush_pos_ > 1) { | ||||||||
| 1163 | s->prev_byte2_ = data[(uint32_t)(s->last_flush_pos_ - 2) & mask]; | ||||||||
| 1164 | } | ||||||||
| 1165 | s->num_commands_ = 0; | ||||||||
| 1166 | s->num_literals_ = 0; | ||||||||
| 1167 | /* Save the state of the distance cache in case we need to restore it for | ||||||||
| 1168 | emitting an uncompressed block. */ | ||||||||
| 1169 | memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_)); | ||||||||
| 1170 | *output = &storage[0]; | ||||||||
| 1171 | *out_size = storage_ix >> 3; | ||||||||
| 1172 | return BROTLI_TRUE1; | ||||||||
| 1173 | } | ||||||||
| 1174 | } | ||||||||
| 1175 | |||||||||
| 1176 | /* Dumps remaining output bits and metadata header to |header|. | ||||||||
| 1177 | Returns number of produced bytes. | ||||||||
| 1178 | REQUIRED: |header| should be 8-byte aligned and at least 16 bytes long. | ||||||||
| 1179 | REQUIRED: |block_size| <= (1 << 24). */ | ||||||||
| 1180 | static size_t WriteMetadataHeader( | ||||||||
| 1181 | BrotliEncoderState* s, const size_t block_size, uint8_t* header) { | ||||||||
| 1182 | size_t storage_ix; | ||||||||
| 1183 | storage_ix = s->last_bytes_bits_; | ||||||||
| 1184 | header[0] = (uint8_t)s->last_bytes_; | ||||||||
| 1185 | header[1] = (uint8_t)(s->last_bytes_ >> 8); | ||||||||
| 1186 | s->last_bytes_ = 0; | ||||||||
| 1187 | s->last_bytes_bits_ = 0; | ||||||||
| 1188 | |||||||||
| 1189 | BrotliWriteBits(1, 0, &storage_ix, header); | ||||||||
| 1190 | BrotliWriteBits(2, 3, &storage_ix, header); | ||||||||
| 1191 | BrotliWriteBits(1, 0, &storage_ix, header); | ||||||||
| 1192 | if (block_size == 0) { | ||||||||
| 1193 | BrotliWriteBits(2, 0, &storage_ix, header); | ||||||||
| 1194 | } else { | ||||||||
| 1195 | uint32_t nbits = (block_size == 1) ? 0 : | ||||||||
| 1196 | (Log2FloorNonZero((uint32_t)block_size - 1) + 1); | ||||||||
| 1197 | uint32_t nbytes = (nbits + 7) / 8; | ||||||||
| 1198 | BrotliWriteBits(2, nbytes, &storage_ix, header); | ||||||||
| 1199 | BrotliWriteBits(8 * nbytes, block_size - 1, &storage_ix, header); | ||||||||
| 1200 | } | ||||||||
| 1201 | return (storage_ix + 7u) >> 3; | ||||||||
| 1202 | } | ||||||||
| 1203 | |||||||||
| 1204 | static BROTLI_BOOLint BrotliCompressBufferQuality10( | ||||||||
| 1205 | int lgwin, size_t input_size, const uint8_t* input_buffer, | ||||||||
| 1206 | size_t* encoded_size, uint8_t* encoded_buffer) { | ||||||||
| 1207 | MemoryManager memory_manager; | ||||||||
| 1208 | MemoryManager* m = &memory_manager; | ||||||||
| 1209 | |||||||||
| 1210 | const size_t mask = BROTLI_SIZE_MAX(~((size_t)0)) >> 1; | ||||||||
| 1211 | int dist_cache[4] = { 4, 11, 15, 16 }; | ||||||||
| 1212 | int saved_dist_cache[4] = { 4, 11, 15, 16 }; | ||||||||
| 1213 | BROTLI_BOOLint ok = BROTLI_TRUE1; | ||||||||
| 1214 | const size_t max_out_size = *encoded_size; | ||||||||
| 1215 | size_t total_out_size = 0; | ||||||||
| 1216 | uint16_t last_bytes; | ||||||||
| 1217 | uint8_t last_bytes_bits; | ||||||||
| 1218 | |||||||||
| 1219 | const size_t hasher_eff_size = BROTLI_MIN(size_t,(brotli_min_size_t((input_size), ((((size_t)1 << (lgwin )) - 16) + 16))) | ||||||||
| 1220 | input_size, BROTLI_MAX_BACKWARD_LIMIT(lgwin) + BROTLI_WINDOW_GAP)(brotli_min_size_t((input_size), ((((size_t)1 << (lgwin )) - 16) + 16))); | ||||||||
| 1221 | |||||||||
| 1222 | BrotliEncoderParams params; | ||||||||
| 1223 | |||||||||
| 1224 | const int lgmetablock = BROTLI_MIN(int, 24, lgwin + 1)(brotli_min_int((24), (lgwin + 1))); | ||||||||
| 1225 | size_t max_block_size; | ||||||||
| 1226 | const size_t max_metablock_size = (size_t)1 << lgmetablock; | ||||||||
| 1227 | const size_t max_literals_per_metablock = max_metablock_size / 8; | ||||||||
| 1228 | const size_t max_commands_per_metablock = max_metablock_size / 8; | ||||||||
| 1229 | size_t metablock_start = 0; | ||||||||
| 1230 | uint8_t prev_byte = 0; | ||||||||
| 1231 | uint8_t prev_byte2 = 0; | ||||||||
| 1232 | |||||||||
| 1233 | Hasher hasher; | ||||||||
| 1234 | HasherInit(&hasher); | ||||||||
| 1235 | |||||||||
| 1236 | BrotliEncoderInitParams(¶ms); | ||||||||
| 1237 | params.quality = 10; | ||||||||
| 1238 | params.lgwin = lgwin; | ||||||||
| 1239 | if (lgwin
| ||||||||
| 1240 | params.large_window = BROTLI_TRUE1; | ||||||||
| 1241 | } | ||||||||
| 1242 | SanitizeParams(¶ms); | ||||||||
| 1243 | params.lgblock = ComputeLgBlock(¶ms); | ||||||||
| 1244 | ChooseDistanceParams(¶ms); | ||||||||
| 1245 | max_block_size = (size_t)1 << params.lgblock; | ||||||||
| 1246 | |||||||||
| 1247 | BrotliInitMemoryManager(m, 0, 0, 0); | ||||||||
| 1248 | |||||||||
| 1249 | BROTLI_DCHECK(input_size <= mask + 1); | ||||||||
| 1250 | EncodeWindowBits(lgwin, params.large_window, &last_bytes, &last_bytes_bits); | ||||||||
| 1251 | InitOrStitchToPreviousBlock(m, &hasher, input_buffer, mask, ¶ms, | ||||||||
| 1252 | 0, hasher_eff_size, BROTLI_TRUE1); | ||||||||
| 1253 | if (BROTLI_IS_OOM(m)(!!0)) goto oom; | ||||||||
| 1254 | |||||||||
| 1255 | while (ok
| ||||||||
| 1256 | const size_t metablock_end = | ||||||||
| 1257 | BROTLI_MIN(size_t, input_size, metablock_start + max_metablock_size)(brotli_min_size_t((input_size), (metablock_start + max_metablock_size ))); | ||||||||
| 1258 | const size_t expected_num_commands = | ||||||||
| 1259 | (metablock_end - metablock_start) / 12 + 16; | ||||||||
| 1260 | Command* commands = 0; | ||||||||
| 1261 | size_t num_commands = 0; | ||||||||
| 1262 | size_t last_insert_len = 0; | ||||||||
| 1263 | size_t num_literals = 0; | ||||||||
| 1264 | size_t metablock_size = 0; | ||||||||
| 1265 | size_t cmd_alloc_size = 0; | ||||||||
| 1266 | BROTLI_BOOLint is_last; | ||||||||
| 1267 | uint8_t* storage; | ||||||||
| 1268 | size_t storage_ix; | ||||||||
| 1269 | |||||||||
| 1270 | ContextType literal_context_mode = ChooseContextMode(¶ms, | ||||||||
| 1271 | input_buffer, metablock_start, mask, metablock_end - metablock_start); | ||||||||
| 1272 | ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode)(&_kBrotliContextLookupTable[(literal_context_mode) << 9]); | ||||||||
| 1273 | |||||||||
| 1274 | size_t block_start; | ||||||||
| 1275 | for (block_start = metablock_start; block_start < metablock_end; ) { | ||||||||
| 1276 | size_t block_size = | ||||||||
| 1277 | BROTLI_MIN(size_t, metablock_end - block_start, max_block_size)(brotli_min_size_t((metablock_end - block_start), (max_block_size ))); | ||||||||
| 1278 | ZopfliNode* nodes = BROTLI_ALLOC(m, ZopfliNode, block_size + 1)((block_size + 1) > 0 ? ((ZopfliNode*)BrotliAllocate((m), ( block_size + 1) * sizeof(ZopfliNode))) : ((void*)0)); | ||||||||
| 1279 | size_t path_size; | ||||||||
| 1280 | size_t new_cmd_alloc_size; | ||||||||
| 1281 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(nodes)(!!0)) goto oom; | ||||||||
| 1282 | BrotliInitZopfliNodes(nodes, block_size + 1); | ||||||||
| 1283 | StitchToPreviousBlockH10(&hasher.privat._H10, block_size, block_start, | ||||||||
| 1284 | input_buffer, mask); | ||||||||
| 1285 | path_size = BrotliZopfliComputeShortestPath(m, block_size, block_start, | ||||||||
| 1286 | input_buffer, mask, literal_context_lut, ¶ms, dist_cache, &hasher, | ||||||||
| 1287 | nodes); | ||||||||
| 1288 | if (BROTLI_IS_OOM(m)(!!0)) goto oom; | ||||||||
| 1289 | /* We allocate a command buffer in the first iteration of this loop that | ||||||||
| 1290 | will be likely big enough for the whole metablock, so that for most | ||||||||
| 1291 | inputs we will not have to reallocate in later iterations. We do the | ||||||||
| 1292 | allocation here and not before the loop, because if the input is small, | ||||||||
| 1293 | this will be allocated after the Zopfli cost model is freed, so this | ||||||||
| 1294 | will not increase peak memory usage. | ||||||||
| 1295 | TODO: If the first allocation is too small, increase command | ||||||||
| 1296 | buffer size exponentially. */ | ||||||||
| 1297 | new_cmd_alloc_size = BROTLI_MAX(size_t, expected_num_commands,(brotli_max_size_t((expected_num_commands), (num_commands + path_size + 1))) | ||||||||
| 1298 | num_commands + path_size + 1)(brotli_max_size_t((expected_num_commands), (num_commands + path_size + 1))); | ||||||||
| 1299 | if (cmd_alloc_size != new_cmd_alloc_size) { | ||||||||
| 1300 | Command* new_commands = BROTLI_ALLOC(m, Command, new_cmd_alloc_size)((new_cmd_alloc_size) > 0 ? ((Command*)BrotliAllocate((m), (new_cmd_alloc_size) * sizeof(Command))) : ((void*)0)); | ||||||||
| 1301 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(new_commands)(!!0)) goto oom; | ||||||||
| 1302 | cmd_alloc_size = new_cmd_alloc_size; | ||||||||
| 1303 | if (commands) { | ||||||||
| 1304 | memcpy(new_commands, commands, sizeof(Command) * num_commands); | ||||||||
| 1305 | BROTLI_FREE(m, commands){ BrotliFree((m), (commands)); commands = ((void*)0); }; | ||||||||
| 1306 | } | ||||||||
| 1307 | commands = new_commands; | ||||||||
| 1308 | } | ||||||||
| 1309 | BrotliZopfliCreateCommands(block_size, block_start, &nodes[0], dist_cache, | ||||||||
| 1310 | &last_insert_len, ¶ms, &commands[num_commands], &num_literals); | ||||||||
| 1311 | num_commands += path_size; | ||||||||
| 1312 | block_start += block_size; | ||||||||
| 1313 | metablock_size += block_size; | ||||||||
| 1314 | BROTLI_FREE(m, nodes){ BrotliFree((m), (nodes)); nodes = ((void*)0); }; | ||||||||
| 1315 | if (num_literals > max_literals_per_metablock || | ||||||||
| 1316 | num_commands > max_commands_per_metablock) { | ||||||||
| 1317 | break; | ||||||||
| 1318 | } | ||||||||
| 1319 | } | ||||||||
| 1320 | |||||||||
| 1321 | if (last_insert_len > 0) { | ||||||||
| 1322 | InitInsertCommand(&commands[num_commands++], last_insert_len); | ||||||||
| 1323 | num_literals += last_insert_len; | ||||||||
| 1324 | } | ||||||||
| 1325 | |||||||||
| 1326 | is_last = TO_BROTLI_BOOL(metablock_start + metablock_size == input_size)(!!(metablock_start + metablock_size == input_size) ? 1 : 0); | ||||||||
| 1327 | storage = NULL((void*)0); | ||||||||
| 1328 | storage_ix = last_bytes_bits; | ||||||||
| 1329 | |||||||||
| 1330 | if (metablock_size == 0) { | ||||||||
| 1331 | /* Write the ISLAST and ISEMPTY bits. */ | ||||||||
| 1332 | storage = BROTLI_ALLOC(m, uint8_t, 16)((16) > 0 ? ((uint8_t*)BrotliAllocate((m), (16) * sizeof(uint8_t ))) : ((void*)0)); | ||||||||
| 1333 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(storage)(!!0)) goto oom; | ||||||||
| 1334 | storage[0] = (uint8_t)last_bytes; | ||||||||
| 1335 | storage[1] = (uint8_t)(last_bytes >> 8); | ||||||||
| 1336 | BrotliWriteBits(2, 3, &storage_ix, storage); | ||||||||
| 1337 | storage_ix = (storage_ix + 7u) & ~7u; | ||||||||
| 1338 | } else if (!ShouldCompress(input_buffer, mask, metablock_start, | ||||||||
| 1339 | metablock_size, num_literals, num_commands)) { | ||||||||
| 1340 | /* Restore the distance cache, as its last update by | ||||||||
| 1341 | CreateBackwardReferences is now unused. */ | ||||||||
| 1342 | memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); | ||||||||
| 1343 | storage = BROTLI_ALLOC(m, uint8_t, metablock_size + 16)((metablock_size + 16) > 0 ? ((uint8_t*)BrotliAllocate((m) , (metablock_size + 16) * sizeof(uint8_t))) : ((void*)0)); | ||||||||
| 1344 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(storage)(!!0)) goto oom; | ||||||||
| 1345 | storage[0] = (uint8_t)last_bytes; | ||||||||
| 1346 | storage[1] = (uint8_t)(last_bytes >> 8); | ||||||||
| 1347 | BrotliStoreUncompressedMetaBlock(is_last, input_buffer, | ||||||||
| 1348 | metablock_start, mask, metablock_size, | ||||||||
| 1349 | &storage_ix, storage); | ||||||||
| 1350 | } else { | ||||||||
| 1351 | MetaBlockSplit mb; | ||||||||
| 1352 | BrotliEncoderParams block_params = params; | ||||||||
| 1353 | InitMetaBlockSplit(&mb); | ||||||||
| 1354 | BrotliBuildMetaBlock(m, input_buffer, metablock_start, mask, | ||||||||
| 1355 | &block_params, | ||||||||
| 1356 | prev_byte, prev_byte2, | ||||||||
| 1357 | commands, num_commands, | ||||||||
| 1358 | literal_context_mode, | ||||||||
| 1359 | &mb); | ||||||||
| 1360 | if (BROTLI_IS_OOM(m)(!!0)) goto oom; | ||||||||
| 1361 | { | ||||||||
| 1362 | /* The number of distance symbols effectively used for distance | ||||||||
| 1363 | histograms. It might be less than distance alphabet size | ||||||||
| 1364 | for "Large Window Brotli" (32-bit). */ | ||||||||
| 1365 | BrotliOptimizeHistograms(block_params.dist.alphabet_size_limit, &mb); | ||||||||
| 1366 | } | ||||||||
| 1367 | storage = BROTLI_ALLOC(m, uint8_t, 2 * metablock_size + 503)((2 * metablock_size + 503) > 0 ? ((uint8_t*)BrotliAllocate ((m), (2 * metablock_size + 503) * sizeof(uint8_t))) : ((void *)0)); | ||||||||
| 1368 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(storage)(!!0)) goto oom; | ||||||||
| 1369 | storage[0] = (uint8_t)last_bytes; | ||||||||
| 1370 | storage[1] = (uint8_t)(last_bytes >> 8); | ||||||||
| 1371 | BrotliStoreMetaBlock(m, input_buffer, metablock_start, metablock_size, | ||||||||
| 1372 | mask, prev_byte, prev_byte2, | ||||||||
| 1373 | is_last, | ||||||||
| 1374 | &block_params, | ||||||||
| 1375 | literal_context_mode, | ||||||||
| 1376 | commands, num_commands, | ||||||||
| 1377 | &mb, | ||||||||
| 1378 | &storage_ix, storage); | ||||||||
| 1379 | if (BROTLI_IS_OOM(m)(!!0)) goto oom; | ||||||||
| 1380 | if (metablock_size + 4 < (storage_ix >> 3)) { | ||||||||
| 1381 | /* Restore the distance cache and last byte. */ | ||||||||
| 1382 | memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); | ||||||||
| 1383 | storage[0] = (uint8_t)last_bytes; | ||||||||
| 1384 | storage[1] = (uint8_t)(last_bytes >> 8); | ||||||||
| 1385 | storage_ix = last_bytes_bits; | ||||||||
| 1386 | BrotliStoreUncompressedMetaBlock(is_last, input_buffer, | ||||||||
| 1387 | metablock_start, mask, | ||||||||
| 1388 | metablock_size, &storage_ix, storage); | ||||||||
| 1389 | } | ||||||||
| 1390 | DestroyMetaBlockSplit(m, &mb); | ||||||||
| 1391 | } | ||||||||
| 1392 | last_bytes = (uint16_t)(storage[storage_ix >> 3]); | ||||||||
| 1393 | last_bytes_bits = storage_ix & 7u; | ||||||||
| 1394 | metablock_start += metablock_size; | ||||||||
| 1395 | if (metablock_start < input_size) { | ||||||||
| 1396 | prev_byte = input_buffer[metablock_start - 1]; | ||||||||
| 1397 | prev_byte2 = input_buffer[metablock_start - 2]; | ||||||||
| 1398 | } | ||||||||
| 1399 | /* Save the state of the distance cache in case we need to restore it for | ||||||||
| 1400 | emitting an uncompressed block. */ | ||||||||
| 1401 | memcpy(saved_dist_cache, dist_cache, 4 * sizeof(dist_cache[0])); | ||||||||
| 1402 | |||||||||
| 1403 | { | ||||||||
| 1404 | const size_t out_size = storage_ix >> 3; | ||||||||
| 1405 | total_out_size += out_size; | ||||||||
| 1406 | if (total_out_size <= max_out_size) { | ||||||||
| 1407 | memcpy(encoded_buffer, storage, out_size); | ||||||||
| 1408 | encoded_buffer += out_size; | ||||||||
| 1409 | } else { | ||||||||
| 1410 | ok = BROTLI_FALSE0; | ||||||||
| 1411 | } | ||||||||
| 1412 | } | ||||||||
| 1413 | BROTLI_FREE(m, storage){ BrotliFree((m), (storage)); storage = ((void*)0); }; | ||||||||
| 1414 | BROTLI_FREE(m, commands){ BrotliFree((m), (commands)); commands = ((void*)0); }; | ||||||||
| 1415 | } | ||||||||
| 1416 | |||||||||
| 1417 | *encoded_size = total_out_size; | ||||||||
| 1418 | DestroyHasher(m, &hasher); | ||||||||
| 1419 | return ok; | ||||||||
| 1420 | |||||||||
| 1421 | oom: | ||||||||
| 1422 | BrotliWipeOutMemoryManager(m); | ||||||||
| 1423 | return BROTLI_FALSE0; | ||||||||
| 1424 | } | ||||||||
| 1425 | |||||||||
| 1426 | size_t BrotliEncoderMaxCompressedSize(size_t input_size) { | ||||||||
| 1427 | /* [window bits / empty metadata] + N * [uncompressed] + [last empty] */ | ||||||||
| 1428 | size_t num_large_blocks = input_size >> 14; | ||||||||
| 1429 | size_t overhead = 2 + (4 * num_large_blocks) + 3 + 1; | ||||||||
| 1430 | size_t result = input_size + overhead; | ||||||||
| 1431 | if (input_size == 0) return 2; | ||||||||
| 1432 | return (result < input_size) ? 0 : result; | ||||||||
| 1433 | } | ||||||||
| 1434 | |||||||||
| 1435 | /* Wraps data to uncompressed brotli stream with minimal window size. | ||||||||
| 1436 | |output| should point at region with at least BrotliEncoderMaxCompressedSize | ||||||||
| 1437 | addressable bytes. | ||||||||
| 1438 | Returns the length of stream. */ | ||||||||
| 1439 | static size_t MakeUncompressedStream( | ||||||||
| 1440 | const uint8_t* input, size_t input_size, uint8_t* output) { | ||||||||
| 1441 | size_t size = input_size; | ||||||||
| 1442 | size_t result = 0; | ||||||||
| 1443 | size_t offset = 0; | ||||||||
| 1444 | if (input_size == 0) { | ||||||||
| 1445 | output[0] = 6; | ||||||||
| 1446 | return 1; | ||||||||
| 1447 | } | ||||||||
| 1448 | output[result++] = 0x21; /* window bits = 10, is_last = false */ | ||||||||
| 1449 | output[result++] = 0x03; /* empty metadata, padding */ | ||||||||
| 1450 | while (size > 0) { | ||||||||
| 1451 | uint32_t nibbles = 0; | ||||||||
| 1452 | uint32_t chunk_size; | ||||||||
| 1453 | uint32_t bits; | ||||||||
| 1454 | chunk_size = (size > (1u << 24)) ? (1u << 24) : (uint32_t)size; | ||||||||
| 1455 | if (chunk_size > (1u << 16)) nibbles = (chunk_size > (1u << 20)) ? 2 : 1; | ||||||||
| 1456 | bits = | ||||||||
| 1457 | (nibbles << 1) | ((chunk_size - 1) << 3) | (1u << (19 + 4 * nibbles)); | ||||||||
| 1458 | output[result++] = (uint8_t)bits; | ||||||||
| 1459 | output[result++] = (uint8_t)(bits >> 8); | ||||||||
| 1460 | output[result++] = (uint8_t)(bits >> 16); | ||||||||
| 1461 | if (nibbles == 2) output[result++] = (uint8_t)(bits >> 24); | ||||||||
| 1462 | memcpy(&output[result], &input[offset], chunk_size); | ||||||||
| 1463 | result += chunk_size; | ||||||||
| 1464 | offset += chunk_size; | ||||||||
| 1465 | size -= chunk_size; | ||||||||
| 1466 | } | ||||||||
| 1467 | output[result++] = 3; | ||||||||
| 1468 | return result; | ||||||||
| 1469 | } | ||||||||
| 1470 | |||||||||
| 1471 | BROTLI_BOOLint BrotliEncoderCompress( | ||||||||
| 1472 | int quality, int lgwin, BrotliEncoderMode mode, size_t input_size, | ||||||||
| 1473 | const uint8_t* input_buffer, size_t* encoded_size, | ||||||||
| 1474 | uint8_t* encoded_buffer) { | ||||||||
| 1475 | BrotliEncoderState* s; | ||||||||
| 1476 | size_t out_size = *encoded_size; | ||||||||
| 1477 | const uint8_t* input_start = input_buffer; | ||||||||
| 1478 | uint8_t* output_start = encoded_buffer; | ||||||||
| 1479 | size_t max_out_size = BrotliEncoderMaxCompressedSize(input_size); | ||||||||
| 1480 | if (out_size == 0) { | ||||||||
| |||||||||
| 1481 | /* Output buffer needs at least one byte. */ | ||||||||
| 1482 | return BROTLI_FALSE0; | ||||||||
| 1483 | } | ||||||||
| 1484 | if (input_size
| ||||||||
| 1485 | /* Handle the special case of empty input. */ | ||||||||
| 1486 | *encoded_size = 1; | ||||||||
| 1487 | *encoded_buffer = 6; | ||||||||
| 1488 | return BROTLI_TRUE1; | ||||||||
| 1489 | } | ||||||||
| 1490 | if (quality == 10) { | ||||||||
| 1491 | /* TODO: Implement this direct path for all quality levels. */ | ||||||||
| 1492 | const int lg_win = BROTLI_MIN(int, BROTLI_LARGE_MAX_WINDOW_BITS,(brotli_min_int((30), ((brotli_max_int((16), (lgwin)))))) | ||||||||
| 1493 | BROTLI_MAX(int, 16, lgwin))(brotli_min_int((30), ((brotli_max_int((16), (lgwin)))))); | ||||||||
| 1494 | int ok = BrotliCompressBufferQuality10(lg_win, input_size, input_buffer, | ||||||||
| 1495 | encoded_size, encoded_buffer); | ||||||||
| 1496 | if (!ok || (max_out_size && *encoded_size > max_out_size)) { | ||||||||
| 1497 | goto fallback; | ||||||||
| 1498 | } | ||||||||
| 1499 | return BROTLI_TRUE1; | ||||||||
| 1500 | } | ||||||||
| 1501 | |||||||||
| 1502 | s = BrotliEncoderCreateInstance(0, 0, 0); | ||||||||
| 1503 | if (!s) { | ||||||||
| 1504 | return BROTLI_FALSE0; | ||||||||
| 1505 | } else { | ||||||||
| 1506 | size_t available_in = input_size; | ||||||||
| 1507 | const uint8_t* next_in = input_buffer; | ||||||||
| 1508 | size_t available_out = *encoded_size; | ||||||||
| 1509 | uint8_t* next_out = encoded_buffer; | ||||||||
| 1510 | size_t total_out = 0; | ||||||||
| 1511 | BROTLI_BOOLint result = BROTLI_FALSE0; | ||||||||
| 1512 | BrotliEncoderSetParameter(s, BROTLI_PARAM_QUALITY, (uint32_t)quality); | ||||||||
| 1513 | BrotliEncoderSetParameter(s, BROTLI_PARAM_LGWIN, (uint32_t)lgwin); | ||||||||
| 1514 | BrotliEncoderSetParameter(s, BROTLI_PARAM_MODE, (uint32_t)mode); | ||||||||
| 1515 | BrotliEncoderSetParameter(s, BROTLI_PARAM_SIZE_HINT, (uint32_t)input_size); | ||||||||
| 1516 | if (lgwin > BROTLI_MAX_WINDOW_BITS24) { | ||||||||
| 1517 | BrotliEncoderSetParameter(s, BROTLI_PARAM_LARGE_WINDOW, BROTLI_TRUE1); | ||||||||
| 1518 | } | ||||||||
| 1519 | result = BrotliEncoderCompressStream(s, BROTLI_OPERATION_FINISH, | ||||||||
| 1520 | &available_in, &next_in, &available_out, &next_out, &total_out); | ||||||||
| 1521 | if (!BrotliEncoderIsFinished(s)) result = 0; | ||||||||
| 1522 | *encoded_size = total_out; | ||||||||
| 1523 | BrotliEncoderDestroyInstance(s); | ||||||||
| 1524 | if (!result || (max_out_size && *encoded_size > max_out_size)) { | ||||||||
| 1525 | goto fallback; | ||||||||
| 1526 | } | ||||||||
| 1527 | return BROTLI_TRUE1; | ||||||||
| 1528 | } | ||||||||
| 1529 | fallback: | ||||||||
| 1530 | *encoded_size = 0; | ||||||||
| 1531 | if (!max_out_size) return BROTLI_FALSE0; | ||||||||
| 1532 | if (out_size >= max_out_size) { | ||||||||
| 1533 | *encoded_size = | ||||||||
| 1534 | MakeUncompressedStream(input_start, input_size, output_start); | ||||||||
| 1535 | return BROTLI_TRUE1; | ||||||||
| 1536 | } | ||||||||
| 1537 | return BROTLI_FALSE0; | ||||||||
| 1538 | } | ||||||||
| 1539 | |||||||||
| 1540 | static void InjectBytePaddingBlock(BrotliEncoderState* s) { | ||||||||
| 1541 | uint32_t seal = s->last_bytes_; | ||||||||
| 1542 | size_t seal_bits = s->last_bytes_bits_; | ||||||||
| 1543 | uint8_t* destination; | ||||||||
| 1544 | s->last_bytes_ = 0; | ||||||||
| 1545 | s->last_bytes_bits_ = 0; | ||||||||
| 1546 | /* is_last = 0, data_nibbles = 11, reserved = 0, meta_nibbles = 00 */ | ||||||||
| 1547 | seal |= 0x6u << seal_bits; | ||||||||
| 1548 | seal_bits += 6; | ||||||||
| 1549 | /* If we have already created storage, then append to it. | ||||||||
| 1550 | Storage is valid until next block is being compressed. */ | ||||||||
| 1551 | if (s->next_out_) { | ||||||||
| 1552 | destination = s->next_out_ + s->available_out_; | ||||||||
| 1553 | } else { | ||||||||
| 1554 | destination = s->tiny_buf_.u8; | ||||||||
| 1555 | s->next_out_ = destination; | ||||||||
| 1556 | } | ||||||||
| 1557 | destination[0] = (uint8_t)seal; | ||||||||
| 1558 | if (seal_bits > 8) destination[1] = (uint8_t)(seal >> 8); | ||||||||
| 1559 | if (seal_bits > 16) destination[2] = (uint8_t)(seal >> 16); | ||||||||
| 1560 | s->available_out_ += (seal_bits + 7) >> 3; | ||||||||
| 1561 | } | ||||||||
| 1562 | |||||||||
| 1563 | /* Injects padding bits or pushes compressed data to output. | ||||||||
| 1564 | Returns false if nothing is done. */ | ||||||||
| 1565 | static BROTLI_BOOLint InjectFlushOrPushOutput(BrotliEncoderState* s, | ||||||||
| 1566 | size_t* available_out, uint8_t** next_out, size_t* total_out) { | ||||||||
| 1567 | if (s->stream_state_ == BROTLI_STREAM_FLUSH_REQUESTED && | ||||||||
| 1568 | s->last_bytes_bits_ != 0) { | ||||||||
| 1569 | InjectBytePaddingBlock(s); | ||||||||
| 1570 | return BROTLI_TRUE1; | ||||||||
| 1571 | } | ||||||||
| 1572 | |||||||||
| 1573 | if (s->available_out_ != 0 && *available_out != 0) { | ||||||||
| 1574 | size_t copy_output_size = | ||||||||
| 1575 | BROTLI_MIN(size_t, s->available_out_, *available_out)(brotli_min_size_t((s->available_out_), (*available_out))); | ||||||||
| 1576 | memcpy(*next_out, s->next_out_, copy_output_size); | ||||||||
| 1577 | *next_out += copy_output_size; | ||||||||
| 1578 | *available_out -= copy_output_size; | ||||||||
| 1579 | s->next_out_ += copy_output_size; | ||||||||
| 1580 | s->available_out_ -= copy_output_size; | ||||||||
| 1581 | s->total_out_ += copy_output_size; | ||||||||
| 1582 | if (total_out) *total_out = s->total_out_; | ||||||||
| 1583 | return BROTLI_TRUE1; | ||||||||
| 1584 | } | ||||||||
| 1585 | |||||||||
| 1586 | return BROTLI_FALSE0; | ||||||||
| 1587 | } | ||||||||
| 1588 | |||||||||
| 1589 | static void CheckFlushComplete(BrotliEncoderState* s) { | ||||||||
| 1590 | if (s->stream_state_ == BROTLI_STREAM_FLUSH_REQUESTED && | ||||||||
| 1591 | s->available_out_ == 0) { | ||||||||
| 1592 | s->stream_state_ = BROTLI_STREAM_PROCESSING; | ||||||||
| 1593 | s->next_out_ = 0; | ||||||||
| 1594 | } | ||||||||
| 1595 | } | ||||||||
| 1596 | |||||||||
| 1597 | static BROTLI_BOOLint BrotliEncoderCompressStreamFast( | ||||||||
| 1598 | BrotliEncoderState* s, BrotliEncoderOperation op, size_t* available_in, | ||||||||
| 1599 | const uint8_t** next_in, size_t* available_out, uint8_t** next_out, | ||||||||
| 1600 | size_t* total_out) { | ||||||||
| 1601 | const size_t block_size_limit = (size_t)1 << s->params.lgwin; | ||||||||
| 1602 | const size_t buf_size = BROTLI_MIN(size_t, kCompressFragmentTwoPassBlockSize,(brotli_min_size_t((kCompressFragmentTwoPassBlockSize), ((brotli_min_size_t ((*available_in), (block_size_limit)))))) | ||||||||
| 1603 | BROTLI_MIN(size_t, *available_in, block_size_limit))(brotli_min_size_t((kCompressFragmentTwoPassBlockSize), ((brotli_min_size_t ((*available_in), (block_size_limit)))))); | ||||||||
| 1604 | uint32_t* tmp_command_buf = NULL((void*)0); | ||||||||
| 1605 | uint32_t* command_buf = NULL((void*)0); | ||||||||
| 1606 | uint8_t* tmp_literal_buf = NULL((void*)0); | ||||||||
| 1607 | uint8_t* literal_buf = NULL((void*)0); | ||||||||
| 1608 | MemoryManager* m = &s->memory_manager_; | ||||||||
| 1609 | if (s->params.quality != FAST_ONE_PASS_COMPRESSION_QUALITY0 && | ||||||||
| 1610 | s->params.quality != FAST_TWO_PASS_COMPRESSION_QUALITY1) { | ||||||||
| 1611 | return BROTLI_FALSE0; | ||||||||
| 1612 | } | ||||||||
| 1613 | if (s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY1) { | ||||||||
| 1614 | if (!s->command_buf_ && buf_size == kCompressFragmentTwoPassBlockSize) { | ||||||||
| 1615 | s->command_buf_ = | ||||||||
| 1616 | BROTLI_ALLOC(m, uint32_t, kCompressFragmentTwoPassBlockSize)((kCompressFragmentTwoPassBlockSize) > 0 ? ((uint32_t*)BrotliAllocate ((m), (kCompressFragmentTwoPassBlockSize) * sizeof(uint32_t)) ) : ((void*)0)); | ||||||||
| 1617 | s->literal_buf_ = | ||||||||
| 1618 | BROTLI_ALLOC(m, uint8_t, kCompressFragmentTwoPassBlockSize)((kCompressFragmentTwoPassBlockSize) > 0 ? ((uint8_t*)BrotliAllocate ((m), (kCompressFragmentTwoPassBlockSize) * sizeof(uint8_t))) : ((void*)0)); | ||||||||
| 1619 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(s->command_buf_)(!!0) || | ||||||||
| 1620 | BROTLI_IS_NULL(s->literal_buf_)(!!0)) { | ||||||||
| 1621 | return BROTLI_FALSE0; | ||||||||
| 1622 | } | ||||||||
| 1623 | } | ||||||||
| 1624 | if (s->command_buf_) { | ||||||||
| 1625 | command_buf = s->command_buf_; | ||||||||
| 1626 | literal_buf = s->literal_buf_; | ||||||||
| 1627 | } else { | ||||||||
| 1628 | tmp_command_buf = BROTLI_ALLOC(m, uint32_t, buf_size)((buf_size) > 0 ? ((uint32_t*)BrotliAllocate((m), (buf_size ) * sizeof(uint32_t))) : ((void*)0)); | ||||||||
| 1629 | tmp_literal_buf = BROTLI_ALLOC(m, uint8_t, buf_size)((buf_size) > 0 ? ((uint8_t*)BrotliAllocate((m), (buf_size ) * sizeof(uint8_t))) : ((void*)0)); | ||||||||
| 1630 | if (BROTLI_IS_OOM(m)(!!0) || BROTLI_IS_NULL(tmp_command_buf)(!!0) || | ||||||||
| 1631 | BROTLI_IS_NULL(tmp_literal_buf)(!!0)) { | ||||||||
| 1632 | return BROTLI_FALSE0; | ||||||||
| 1633 | } | ||||||||
| 1634 | command_buf = tmp_command_buf; | ||||||||
| 1635 | literal_buf = tmp_literal_buf; | ||||||||
| 1636 | } | ||||||||
| 1637 | } | ||||||||
| 1638 | |||||||||
| 1639 | while (BROTLI_TRUE1) { | ||||||||
| 1640 | if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) { | ||||||||
| 1641 | continue; | ||||||||
| 1642 | } | ||||||||
| 1643 | |||||||||
| 1644 | /* Compress block only when internal output buffer is empty, stream is not | ||||||||
| 1645 | finished, there is no pending flush request, and there is either | ||||||||
| 1646 | additional input or pending operation. */ | ||||||||
| 1647 | if (s->available_out_ == 0 && | ||||||||
| 1648 | s->stream_state_ == BROTLI_STREAM_PROCESSING && | ||||||||
| 1649 | (*available_in != 0 || op != BROTLI_OPERATION_PROCESS)) { | ||||||||
| 1650 | size_t block_size = BROTLI_MIN(size_t, block_size_limit, *available_in)(brotli_min_size_t((block_size_limit), (*available_in))); | ||||||||
| 1651 | BROTLI_BOOLint is_last = | ||||||||
| 1652 | (*available_in == block_size) && (op == BROTLI_OPERATION_FINISH); | ||||||||
| 1653 | BROTLI_BOOLint force_flush = | ||||||||
| 1654 | (*available_in == block_size) && (op == BROTLI_OPERATION_FLUSH); | ||||||||
| 1655 | size_t max_out_size = 2 * block_size + 503; | ||||||||
| 1656 | BROTLI_BOOLint inplace = BROTLI_TRUE1; | ||||||||
| 1657 | uint8_t* storage = NULL((void*)0); | ||||||||
| 1658 | size_t storage_ix = s->last_bytes_bits_; | ||||||||
| 1659 | size_t table_size; | ||||||||
| 1660 | int* table; | ||||||||
| 1661 | |||||||||
| 1662 | if (force_flush && block_size == 0) { | ||||||||
| 1663 | s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED; | ||||||||
| 1664 | continue; | ||||||||
| 1665 | } | ||||||||
| 1666 | if (max_out_size <= *available_out) { | ||||||||
| 1667 | storage = *next_out; | ||||||||
| 1668 | } else { | ||||||||
| 1669 | inplace = BROTLI_FALSE0; | ||||||||
| 1670 | storage = GetBrotliStorage(s, max_out_size); | ||||||||
| 1671 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1672 | } | ||||||||
| 1673 | storage[0] = (uint8_t)s->last_bytes_; | ||||||||
| 1674 | storage[1] = (uint8_t)(s->last_bytes_ >> 8); | ||||||||
| 1675 | table = GetHashTable(s, s->params.quality, block_size, &table_size); | ||||||||
| 1676 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1677 | |||||||||
| 1678 | if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY0) { | ||||||||
| 1679 | BrotliCompressFragmentFast(m, *next_in, block_size, is_last, table, | ||||||||
| 1680 | table_size, s->cmd_depths_, s->cmd_bits_, &s->cmd_code_numbits_, | ||||||||
| 1681 | s->cmd_code_, &storage_ix, storage); | ||||||||
| 1682 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1683 | } else { | ||||||||
| 1684 | BrotliCompressFragmentTwoPass(m, *next_in, block_size, is_last, | ||||||||
| 1685 | command_buf, literal_buf, table, table_size, | ||||||||
| 1686 | &storage_ix, storage); | ||||||||
| 1687 | if (BROTLI_IS_OOM(m)(!!0)) return BROTLI_FALSE0; | ||||||||
| 1688 | } | ||||||||
| 1689 | if (block_size != 0) { | ||||||||
| 1690 | *next_in += block_size; | ||||||||
| 1691 | *available_in -= block_size; | ||||||||
| 1692 | } | ||||||||
| 1693 | if (inplace) { | ||||||||
| 1694 | size_t out_bytes = storage_ix >> 3; | ||||||||
| 1695 | BROTLI_DCHECK(out_bytes <= *available_out); | ||||||||
| 1696 | BROTLI_DCHECK((storage_ix & 7) == 0 || out_bytes < *available_out); | ||||||||
| 1697 | *next_out += out_bytes; | ||||||||
| 1698 | *available_out -= out_bytes; | ||||||||
| 1699 | s->total_out_ += out_bytes; | ||||||||
| 1700 | if (total_out) *total_out = s->total_out_; | ||||||||
| 1701 | } else { | ||||||||
| 1702 | size_t out_bytes = storage_ix >> 3; | ||||||||
| 1703 | s->next_out_ = storage; | ||||||||
| 1704 | s->available_out_ = out_bytes; | ||||||||
| 1705 | } | ||||||||
| 1706 | s->last_bytes_ = (uint16_t)(storage[storage_ix >> 3]); | ||||||||
| 1707 | s->last_bytes_bits_ = storage_ix & 7u; | ||||||||
| 1708 | |||||||||
| 1709 | if (force_flush) s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED; | ||||||||
| 1710 | if (is_last) s->stream_state_ = BROTLI_STREAM_FINISHED; | ||||||||
| 1711 | continue; | ||||||||
| 1712 | } | ||||||||
| 1713 | break; | ||||||||
| 1714 | } | ||||||||
| 1715 | BROTLI_FREE(m, tmp_command_buf){ BrotliFree((m), (tmp_command_buf)); tmp_command_buf = ((void *)0); }; | ||||||||
| 1716 | BROTLI_FREE(m, tmp_literal_buf){ BrotliFree((m), (tmp_literal_buf)); tmp_literal_buf = ((void *)0); }; | ||||||||
| 1717 | CheckFlushComplete(s); | ||||||||
| 1718 | return BROTLI_TRUE1; | ||||||||
| 1719 | } | ||||||||
| 1720 | |||||||||
| 1721 | static BROTLI_BOOLint ProcessMetadata( | ||||||||
| 1722 | BrotliEncoderState* s, size_t* available_in, const uint8_t** next_in, | ||||||||
| 1723 | size_t* available_out, uint8_t** next_out, size_t* total_out) { | ||||||||
| 1724 | if (*available_in > (1u << 24)) return BROTLI_FALSE0; | ||||||||
| 1725 | /* Switch to metadata block workflow, if required. */ | ||||||||
| 1726 | if (s->stream_state_ == BROTLI_STREAM_PROCESSING) { | ||||||||
| 1727 | s->remaining_metadata_bytes_ = (uint32_t)*available_in; | ||||||||
| 1728 | s->stream_state_ = BROTLI_STREAM_METADATA_HEAD; | ||||||||
| 1729 | } | ||||||||
| 1730 | if (s->stream_state_ != BROTLI_STREAM_METADATA_HEAD && | ||||||||
| 1731 | s->stream_state_ != BROTLI_STREAM_METADATA_BODY) { | ||||||||
| 1732 | return BROTLI_FALSE0; | ||||||||
| 1733 | } | ||||||||
| 1734 | |||||||||
| 1735 | while (BROTLI_TRUE1) { | ||||||||
| 1736 | if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) { | ||||||||
| 1737 | continue; | ||||||||
| 1738 | } | ||||||||
| 1739 | if (s->available_out_ != 0) break; | ||||||||
| 1740 | |||||||||
| 1741 | if (s->input_pos_ != s->last_flush_pos_) { | ||||||||
| 1742 | BROTLI_BOOLint result = EncodeData(s, BROTLI_FALSE0, BROTLI_TRUE1, | ||||||||
| 1743 | &s->available_out_, &s->next_out_); | ||||||||
| 1744 | if (!result) return BROTLI_FALSE0; | ||||||||
| 1745 | continue; | ||||||||
| 1746 | } | ||||||||
| 1747 | |||||||||
| 1748 | if (s->stream_state_ == BROTLI_STREAM_METADATA_HEAD) { | ||||||||
| 1749 | s->next_out_ = s->tiny_buf_.u8; | ||||||||
| 1750 | s->available_out_ = | ||||||||
| 1751 | WriteMetadataHeader(s, s->remaining_metadata_bytes_, s->next_out_); | ||||||||
| 1752 | s->stream_state_ = BROTLI_STREAM_METADATA_BODY; | ||||||||
| 1753 | continue; | ||||||||
| 1754 | } else { | ||||||||
| 1755 | /* Exit workflow only when there is no more input and no more output. | ||||||||
| 1756 | Otherwise client may continue producing empty metadata blocks. */ | ||||||||
| 1757 | if (s->remaining_metadata_bytes_ == 0) { | ||||||||
| 1758 | s->remaining_metadata_bytes_ = BROTLI_UINT32_MAX(~((uint32_t)0)); | ||||||||
| 1759 | s->stream_state_ = BROTLI_STREAM_PROCESSING; | ||||||||
| 1760 | break; | ||||||||
| 1761 | } | ||||||||
| 1762 | if (*available_out) { | ||||||||
| 1763 | /* Directly copy input to output. */ | ||||||||
| 1764 | uint32_t copy = (uint32_t)BROTLI_MIN((brotli_min_size_t((s->remaining_metadata_bytes_), (*available_out ))) | ||||||||
| 1765 | size_t, s->remaining_metadata_bytes_, *available_out)(brotli_min_size_t((s->remaining_metadata_bytes_), (*available_out ))); | ||||||||
| 1766 | memcpy(*next_out, *next_in, copy); | ||||||||
| 1767 | *next_in += copy; | ||||||||
| 1768 | *available_in -= copy; | ||||||||
| 1769 | s->remaining_metadata_bytes_ -= copy; | ||||||||
| 1770 | *next_out += copy; | ||||||||
| 1771 | *available_out -= copy; | ||||||||
| 1772 | } else { | ||||||||
| 1773 | /* This guarantees progress in "TakeOutput" workflow. */ | ||||||||
| 1774 | uint32_t copy = BROTLI_MIN(uint32_t, s->remaining_metadata_bytes_, 16)(brotli_min_uint32_t((s->remaining_metadata_bytes_), (16)) ); | ||||||||
| 1775 | s->next_out_ = s->tiny_buf_.u8; | ||||||||
| 1776 | memcpy(s->next_out_, *next_in, copy); | ||||||||
| 1777 | *next_in += copy; | ||||||||
| 1778 | *available_in -= copy; | ||||||||
| 1779 | s->remaining_metadata_bytes_ -= copy; | ||||||||
| 1780 | s->available_out_ = copy; | ||||||||
| 1781 | } | ||||||||
| 1782 | continue; | ||||||||
| 1783 | } | ||||||||
| 1784 | } | ||||||||
| 1785 | |||||||||
| 1786 | return BROTLI_TRUE1; | ||||||||
| 1787 | } | ||||||||
| 1788 | |||||||||
| 1789 | static void UpdateSizeHint(BrotliEncoderState* s, size_t available_in) { | ||||||||
| 1790 | if (s->params.size_hint == 0) { | ||||||||
| 1791 | uint64_t delta = UnprocessedInputSize(s); | ||||||||
| 1792 | uint64_t tail = available_in; | ||||||||
| 1793 | uint32_t limit = 1u << 30; | ||||||||
| 1794 | uint32_t total; | ||||||||
| 1795 | if ((delta >= limit) || (tail >= limit) || ((delta + tail) >= limit)) { | ||||||||
| 1796 | total = limit; | ||||||||
| 1797 | } else { | ||||||||
| 1798 | total = (uint32_t)(delta + tail); | ||||||||
| 1799 | } | ||||||||
| 1800 | s->params.size_hint = total; | ||||||||
| 1801 | } | ||||||||
| 1802 | } | ||||||||
| 1803 | |||||||||
| 1804 | BROTLI_BOOLint BrotliEncoderCompressStream( | ||||||||
| 1805 | BrotliEncoderState* s, BrotliEncoderOperation op, size_t* available_in, | ||||||||
| 1806 | const uint8_t** next_in, size_t* available_out,uint8_t** next_out, | ||||||||
| 1807 | size_t* total_out) { | ||||||||
| 1808 | if (!EnsureInitialized(s)) return BROTLI_FALSE0; | ||||||||
| 1809 | |||||||||
| 1810 | /* Unfinished metadata block; check requirements. */ | ||||||||
| 1811 | if (s->remaining_metadata_bytes_ != BROTLI_UINT32_MAX(~((uint32_t)0))) { | ||||||||
| 1812 | if (*available_in != s->remaining_metadata_bytes_) return BROTLI_FALSE0; | ||||||||
| 1813 | if (op != BROTLI_OPERATION_EMIT_METADATA) return BROTLI_FALSE0; | ||||||||
| 1814 | } | ||||||||
| 1815 | |||||||||
| 1816 | if (op == BROTLI_OPERATION_EMIT_METADATA) { | ||||||||
| 1817 | UpdateSizeHint(s, 0); /* First data metablock might be emitted here. */ | ||||||||
| 1818 | return ProcessMetadata( | ||||||||
| 1819 | s, available_in, next_in, available_out, next_out, total_out); | ||||||||
| 1820 | } | ||||||||
| 1821 | |||||||||
| 1822 | if (s->stream_state_ == BROTLI_STREAM_METADATA_HEAD || | ||||||||
| 1823 | s->stream_state_ == BROTLI_STREAM_METADATA_BODY) { | ||||||||
| 1824 | return BROTLI_FALSE0; | ||||||||
| 1825 | } | ||||||||
| 1826 | |||||||||
| 1827 | if (s->stream_state_ != BROTLI_STREAM_PROCESSING && *available_in != 0) { | ||||||||
| 1828 | return BROTLI_FALSE0; | ||||||||
| 1829 | } | ||||||||
| 1830 | if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY0 || | ||||||||
| 1831 | s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY1) { | ||||||||
| 1832 | return BrotliEncoderCompressStreamFast(s, op, available_in, next_in, | ||||||||
| 1833 | available_out, next_out, total_out); | ||||||||
| 1834 | } | ||||||||
| 1835 | while (BROTLI_TRUE1) { | ||||||||
| 1836 | size_t remaining_block_size = RemainingInputBlockSize(s); | ||||||||
| 1837 | /* Shorten input to flint size. */ | ||||||||
| 1838 | if (s->flint_ >= 0 && remaining_block_size > (size_t)s->flint_) { | ||||||||
| 1839 | remaining_block_size = (size_t)s->flint_; | ||||||||
| 1840 | } | ||||||||
| 1841 | |||||||||
| 1842 | if (remaining_block_size != 0 && *available_in != 0) { | ||||||||
| 1843 | size_t copy_input_size = | ||||||||
| 1844 | BROTLI_MIN(size_t, remaining_block_size, *available_in)(brotli_min_size_t((remaining_block_size), (*available_in))); | ||||||||
| 1845 | CopyInputToRingBuffer(s, copy_input_size, *next_in); | ||||||||
| 1846 | *next_in += copy_input_size; | ||||||||
| 1847 | *available_in -= copy_input_size; | ||||||||
| 1848 | if (s->flint_ > 0) s->flint_ = (int8_t)(s->flint_ - (int)copy_input_size); | ||||||||
| 1849 | continue; | ||||||||
| 1850 | } | ||||||||
| 1851 | |||||||||
| 1852 | if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) { | ||||||||
| 1853 | /* Exit the "emit flint" workflow. */ | ||||||||
| 1854 | if (s->flint_ == BROTLI_FLINT_WAITING_FOR_FLUSHING) { | ||||||||
| 1855 | CheckFlushComplete(s); | ||||||||
| 1856 | if (s->stream_state_ == BROTLI_STREAM_PROCESSING) { | ||||||||
| 1857 | s->flint_ = BROTLI_FLINT_DONE; | ||||||||
| 1858 | } | ||||||||
| 1859 | } | ||||||||
| 1860 | continue; | ||||||||
| 1861 | } | ||||||||
| 1862 | |||||||||
| 1863 | /* Compress data only when internal output buffer is empty, stream is not | ||||||||
| 1864 | finished and there is no pending flush request. */ | ||||||||
| 1865 | if (s->available_out_ == 0 && | ||||||||
| 1866 | s->stream_state_ == BROTLI_STREAM_PROCESSING) { | ||||||||
| 1867 | if (remaining_block_size == 0 || op != BROTLI_OPERATION_PROCESS) { | ||||||||
| 1868 | BROTLI_BOOLint is_last = TO_BROTLI_BOOL((!!((*available_in == 0) && op == BROTLI_OPERATION_FINISH ) ? 1 : 0) | ||||||||
| 1869 | (*available_in == 0) && op == BROTLI_OPERATION_FINISH)(!!((*available_in == 0) && op == BROTLI_OPERATION_FINISH ) ? 1 : 0); | ||||||||
| 1870 | BROTLI_BOOLint force_flush = TO_BROTLI_BOOL((!!((*available_in == 0) && op == BROTLI_OPERATION_FLUSH ) ? 1 : 0) | ||||||||
| 1871 | (*available_in == 0) && op == BROTLI_OPERATION_FLUSH)(!!((*available_in == 0) && op == BROTLI_OPERATION_FLUSH ) ? 1 : 0); | ||||||||
| 1872 | BROTLI_BOOLint result; | ||||||||
| 1873 | /* Force emitting (uncompressed) piece containing flint. */ | ||||||||
| 1874 | if (!is_last && s->flint_ == 0) { | ||||||||
| 1875 | s->flint_ = BROTLI_FLINT_WAITING_FOR_FLUSHING; | ||||||||
| 1876 | force_flush = BROTLI_TRUE1; | ||||||||
| 1877 | } | ||||||||
| 1878 | UpdateSizeHint(s, *available_in); | ||||||||
| 1879 | result = EncodeData(s, is_last, force_flush, | ||||||||
| 1880 | &s->available_out_, &s->next_out_); | ||||||||
| 1881 | if (!result) return BROTLI_FALSE0; | ||||||||
| 1882 | if (force_flush) s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED; | ||||||||
| 1883 | if (is_last) s->stream_state_ = BROTLI_STREAM_FINISHED; | ||||||||
| 1884 | continue; | ||||||||
| 1885 | } | ||||||||
| 1886 | } | ||||||||
| 1887 | break; | ||||||||
| 1888 | } | ||||||||
| 1889 | CheckFlushComplete(s); | ||||||||
| 1890 | return BROTLI_TRUE1; | ||||||||
| 1891 | } | ||||||||
| 1892 | |||||||||
| 1893 | BROTLI_BOOLint BrotliEncoderIsFinished(BrotliEncoderState* s) { | ||||||||
| 1894 | return TO_BROTLI_BOOL(s->stream_state_ == BROTLI_STREAM_FINISHED &&(!!(s->stream_state_ == BROTLI_STREAM_FINISHED && ! BrotliEncoderHasMoreOutput(s)) ? 1 : 0) | ||||||||
| 1895 | !BrotliEncoderHasMoreOutput(s))(!!(s->stream_state_ == BROTLI_STREAM_FINISHED && ! BrotliEncoderHasMoreOutput(s)) ? 1 : 0); | ||||||||
| 1896 | } | ||||||||
| 1897 | |||||||||
| 1898 | BROTLI_BOOLint BrotliEncoderHasMoreOutput(BrotliEncoderState* s) { | ||||||||
| 1899 | return TO_BROTLI_BOOL(s->available_out_ != 0)(!!(s->available_out_ != 0) ? 1 : 0); | ||||||||
| 1900 | } | ||||||||
| 1901 | |||||||||
| 1902 | const uint8_t* BrotliEncoderTakeOutput(BrotliEncoderState* s, size_t* size) { | ||||||||
| 1903 | size_t consumed_size = s->available_out_; | ||||||||
| 1904 | uint8_t* result = s->next_out_; | ||||||||
| 1905 | if (*size) { | ||||||||
| 1906 | consumed_size = BROTLI_MIN(size_t, *size, s->available_out_)(brotli_min_size_t((*size), (s->available_out_))); | ||||||||
| 1907 | } | ||||||||
| 1908 | if (consumed_size) { | ||||||||
| 1909 | s->next_out_ += consumed_size; | ||||||||
| 1910 | s->available_out_ -= consumed_size; | ||||||||
| 1911 | s->total_out_ += consumed_size; | ||||||||
| 1912 | CheckFlushComplete(s); | ||||||||
| 1913 | *size = consumed_size; | ||||||||
| 1914 | } else { | ||||||||
| 1915 | *size = 0; | ||||||||
| 1916 | result = 0; | ||||||||
| 1917 | } | ||||||||
| 1918 | return result; | ||||||||
| 1919 | } | ||||||||
| 1920 | |||||||||
| 1921 | uint32_t BrotliEncoderVersion(void) { | ||||||||
| 1922 | return BROTLI_VERSION0x1000009; | ||||||||
| 1923 | } | ||||||||
| 1924 | |||||||||
| 1925 | #if defined(__cplusplus) || defined(c_plusplus) | ||||||||
| 1926 | } /* extern "C" */ | ||||||||
| 1927 | #endif |
| 1 | /* Copyright 2013 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 | /* This class models a sequence of literals and a backward reference copy. */ | |||
| 8 | ||||
| 9 | #ifndef BROTLI_ENC_COMMAND_H_ | |||
| 10 | #define BROTLI_ENC_COMMAND_H_ | |||
| 11 | ||||
| 12 | #include "../common/constants.h" | |||
| 13 | #include "../common/platform.h" | |||
| 14 | #include <brotli/types.h> | |||
| 15 | #include "./fast_log.h" | |||
| 16 | #include "./params.h" | |||
| 17 | #include "./prefix.h" | |||
| 18 | ||||
| 19 | #if defined(__cplusplus) || defined(c_plusplus) | |||
| 20 | extern "C" { | |||
| 21 | #endif | |||
| 22 | ||||
| 23 | BROTLI_INTERNAL__attribute__ ((visibility ("hidden"))) extern const uint32_t | |||
| 24 | kBrotliInsBase[BROTLI_NUM_INS_COPY_CODES24]; | |||
| 25 | BROTLI_INTERNAL__attribute__ ((visibility ("hidden"))) extern const uint32_t | |||
| 26 | kBrotliInsExtra[BROTLI_NUM_INS_COPY_CODES24]; | |||
| 27 | BROTLI_INTERNAL__attribute__ ((visibility ("hidden"))) extern const uint32_t | |||
| 28 | kBrotliCopyBase[BROTLI_NUM_INS_COPY_CODES24]; | |||
| 29 | BROTLI_INTERNAL__attribute__ ((visibility ("hidden"))) extern const uint32_t | |||
| 30 | kBrotliCopyExtra[BROTLI_NUM_INS_COPY_CODES24]; | |||
| 31 | ||||
| 32 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint16_t GetInsertLengthCode(size_t insertlen) { | |||
| 33 | if (insertlen < 6) { | |||
| 34 | return (uint16_t)insertlen; | |||
| 35 | } else if (insertlen < 130) { | |||
| 36 | uint32_t nbits = Log2FloorNonZero(insertlen - 2) - 1u; | |||
| 37 | return (uint16_t)((nbits << 1) + ((insertlen - 2) >> nbits) + 2); | |||
| 38 | } else if (insertlen < 2114) { | |||
| 39 | return (uint16_t)(Log2FloorNonZero(insertlen - 66) + 10); | |||
| 40 | } else if (insertlen < 6210) { | |||
| 41 | return 21u; | |||
| 42 | } else if (insertlen < 22594) { | |||
| 43 | return 22u; | |||
| 44 | } else { | |||
| 45 | return 23u; | |||
| 46 | } | |||
| 47 | } | |||
| 48 | ||||
| 49 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint16_t GetCopyLengthCode(size_t copylen) { | |||
| 50 | if (copylen < 10) { | |||
| 51 | return (uint16_t)(copylen - 2); | |||
| 52 | } else if (copylen < 134) { | |||
| 53 | uint32_t nbits = Log2FloorNonZero(copylen - 6) - 1u; | |||
| 54 | return (uint16_t)((nbits << 1) + ((copylen - 6) >> nbits) + 4); | |||
| 55 | } else if (copylen < 2118) { | |||
| 56 | return (uint16_t)(Log2FloorNonZero(copylen - 70) + 12); | |||
| 57 | } else { | |||
| 58 | return 23u; | |||
| 59 | } | |||
| 60 | } | |||
| 61 | ||||
| 62 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint16_t CombineLengthCodes( | |||
| 63 | uint16_t inscode, uint16_t copycode, BROTLI_BOOLint use_last_distance) { | |||
| 64 | uint16_t bits64 = | |||
| 65 | (uint16_t)((copycode & 0x7u) | ((inscode & 0x7u) << 3u)); | |||
| 66 | if (use_last_distance && inscode < 8u && copycode < 16u) { | |||
| 67 | return (copycode < 8u) ? bits64 : (bits64 | 64u); | |||
| 68 | } else { | |||
| 69 | /* Specification: 5 Encoding of ... (last table) */ | |||
| 70 | /* offset = 2 * index, where index is in range [0..8] */ | |||
| 71 | uint32_t offset = 2u * ((copycode >> 3u) + 3u * (inscode >> 3u)); | |||
| 72 | /* All values in specification are K * 64, | |||
| 73 | where K = [2, 3, 6, 4, 5, 8, 7, 9, 10], | |||
| 74 | i + 1 = [1, 2, 3, 4, 5, 6, 7, 8, 9], | |||
| 75 | K - i - 1 = [1, 1, 3, 0, 0, 2, 0, 1, 2] = D. | |||
| 76 | All values in D require only 2 bits to encode. | |||
| 77 | Magic constant is shifted 6 bits left, to avoid final multiplication. */ | |||
| 78 | offset = (offset << 5u) + 0x40u + ((0x520D40u >> offset) & 0xC0u); | |||
| 79 | return (uint16_t)(offset | bits64); | |||
| 80 | } | |||
| 81 | } | |||
| 82 | ||||
| 83 | static BROTLI_INLINEinline __attribute__((__always_inline__)) void GetLengthCode(size_t insertlen, size_t copylen, | |||
| 84 | BROTLI_BOOLint use_last_distance, | |||
| 85 | uint16_t* code) { | |||
| 86 | uint16_t inscode = GetInsertLengthCode(insertlen); | |||
| 87 | uint16_t copycode = GetCopyLengthCode(copylen); | |||
| 88 | *code = CombineLengthCodes(inscode, copycode, use_last_distance); | |||
| 89 | } | |||
| 90 | ||||
| 91 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t GetInsertBase(uint16_t inscode) { | |||
| 92 | return kBrotliInsBase[inscode]; | |||
| 93 | } | |||
| 94 | ||||
| 95 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t GetInsertExtra(uint16_t inscode) { | |||
| 96 | return kBrotliInsExtra[inscode]; | |||
| 97 | } | |||
| 98 | ||||
| 99 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t GetCopyBase(uint16_t copycode) { | |||
| 100 | return kBrotliCopyBase[copycode]; | |||
| 101 | } | |||
| 102 | ||||
| 103 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t GetCopyExtra(uint16_t copycode) { | |||
| 104 | return kBrotliCopyExtra[copycode]; | |||
| 105 | } | |||
| 106 | ||||
| 107 | typedef struct Command { | |||
| 108 | uint32_t insert_len_; | |||
| 109 | /* Stores copy_len in low 25 bits and copy_code - copy_len in high 7 bit. */ | |||
| 110 | uint32_t copy_len_; | |||
| 111 | /* Stores distance extra bits. */ | |||
| 112 | uint32_t dist_extra_; | |||
| 113 | uint16_t cmd_prefix_; | |||
| 114 | /* Stores distance code in low 10 bits | |||
| 115 | and number of extra bits in high 6 bits. */ | |||
| 116 | uint16_t dist_prefix_; | |||
| 117 | } Command; | |||
| 118 | ||||
| 119 | /* distance_code is e.g. 0 for same-as-last short code, or 16 for offset 1. */ | |||
| 120 | static BROTLI_INLINEinline __attribute__((__always_inline__)) void InitCommand(Command* self, | |||
| 121 | const BrotliDistanceParams* dist, size_t insertlen, | |||
| 122 | size_t copylen, int copylen_code_delta, size_t distance_code) { | |||
| 123 | /* Don't rely on signed int representation, use honest casts. */ | |||
| 124 | uint32_t delta = (uint8_t)((int8_t)copylen_code_delta); | |||
| 125 | self->insert_len_ = (uint32_t)insertlen; | |||
| 126 | self->copy_len_ = (uint32_t)(copylen | (delta << 25)); | |||
| 127 | /* The distance prefix and extra bits are stored in this Command as if | |||
| 128 | npostfix and ndirect were 0, they are only recomputed later after the | |||
| 129 | clustering if needed. */ | |||
| 130 | PrefixEncodeCopyDistance( | |||
| 131 | distance_code, dist->num_direct_distance_codes, | |||
| 132 | dist->distance_postfix_bits, &self->dist_prefix_, &self->dist_extra_); | |||
| 133 | GetLengthCode( | |||
| 134 | insertlen, (size_t)((int)copylen + copylen_code_delta), | |||
| 135 | TO_BROTLI_BOOL((self->dist_prefix_ & 0x3FF) == 0)(!!((self->dist_prefix_ & 0x3FF) == 0) ? 1 : 0), &self->cmd_prefix_); | |||
| 136 | } | |||
| 137 | ||||
| 138 | static BROTLI_INLINEinline __attribute__((__always_inline__)) void InitInsertCommand(Command* self, size_t insertlen) { | |||
| 139 | self->insert_len_ = (uint32_t)insertlen; | |||
| ||||
| 140 | self->copy_len_ = 4 << 25; | |||
| 141 | self->dist_extra_ = 0; | |||
| 142 | self->dist_prefix_ = BROTLI_NUM_DISTANCE_SHORT_CODES16; | |||
| 143 | GetLengthCode(insertlen, 4, BROTLI_FALSE0, &self->cmd_prefix_); | |||
| 144 | } | |||
| 145 | ||||
| 146 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t CommandRestoreDistanceCode( | |||
| 147 | const Command* self, const BrotliDistanceParams* dist) { | |||
| 148 | if ((self->dist_prefix_ & 0x3FFu) < | |||
| 149 | BROTLI_NUM_DISTANCE_SHORT_CODES16 + dist->num_direct_distance_codes) { | |||
| 150 | return self->dist_prefix_ & 0x3FFu; | |||
| 151 | } else { | |||
| 152 | uint32_t dcode = self->dist_prefix_ & 0x3FFu; | |||
| 153 | uint32_t nbits = self->dist_prefix_ >> 10; | |||
| 154 | uint32_t extra = self->dist_extra_; | |||
| 155 | uint32_t postfix_mask = (1U << dist->distance_postfix_bits) - 1U; | |||
| 156 | uint32_t hcode = (dcode - dist->num_direct_distance_codes - | |||
| 157 | BROTLI_NUM_DISTANCE_SHORT_CODES16) >> | |||
| 158 | dist->distance_postfix_bits; | |||
| 159 | uint32_t lcode = (dcode - dist->num_direct_distance_codes - | |||
| 160 | BROTLI_NUM_DISTANCE_SHORT_CODES16) & postfix_mask; | |||
| 161 | uint32_t offset = ((2U + (hcode & 1U)) << nbits) - 4U; | |||
| 162 | return ((offset + extra) << dist->distance_postfix_bits) + lcode + | |||
| 163 | dist->num_direct_distance_codes + BROTLI_NUM_DISTANCE_SHORT_CODES16; | |||
| 164 | } | |||
| 165 | } | |||
| 166 | ||||
| 167 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t CommandDistanceContext(const Command* self) { | |||
| 168 | uint32_t r = self->cmd_prefix_ >> 6; | |||
| 169 | uint32_t c = self->cmd_prefix_ & 7; | |||
| 170 | if ((r == 0 || r == 2 || r == 4 || r == 7) && (c <= 2)) { | |||
| 171 | return c; | |||
| 172 | } | |||
| 173 | return 3; | |||
| 174 | } | |||
| 175 | ||||
| 176 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t CommandCopyLen(const Command* self) { | |||
| 177 | return self->copy_len_ & 0x1FFFFFF; | |||
| 178 | } | |||
| 179 | ||||
| 180 | static BROTLI_INLINEinline __attribute__((__always_inline__)) uint32_t CommandCopyLenCode(const Command* self) { | |||
| 181 | uint32_t modifier = self->copy_len_ >> 25; | |||
| 182 | int32_t delta = (int8_t)((uint8_t)(modifier | ((modifier & 0x40) << 1))); | |||
| 183 | return (uint32_t)((int32_t)(self->copy_len_ & 0x1FFFFFF) + delta); | |||
| 184 | } | |||
| 185 | ||||
| 186 | #if defined(__cplusplus) || defined(c_plusplus) | |||
| 187 | } /* extern "C" */ | |||
| 188 | #endif | |||
| 189 | ||||
| 190 | #endif /* BROTLI_ENC_COMMAND_H_ */ |