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