diff options
Diffstat (limited to 'modules/brotli/enc/encode.c')
| -rw-r--r-- | modules/brotli/enc/encode.c | 143 |
1 files changed, 104 insertions, 39 deletions
diff --git a/modules/brotli/enc/encode.c b/modules/brotli/enc/encode.c index 141e70aa2a..8d90937b43 100644 --- a/modules/brotli/enc/encode.c +++ b/modules/brotli/enc/encode.c @@ -54,12 +54,19 @@ typedef enum BrotliEncoderStreamState { BROTLI_STREAM_METADATA_BODY = 4 } BrotliEncoderStreamState; +typedef enum BrotliEncoderFlintState { + BROTLI_FLINT_NEEDS_2_BYTES = 2, + BROTLI_FLINT_NEEDS_1_BYTE = 1, + BROTLI_FLINT_WAITING_FOR_PROCESSING = 0, + BROTLI_FLINT_WAITING_FOR_FLUSHING = -1, + BROTLI_FLINT_DONE = -2 +} BrotliEncoderFlintState; + typedef struct BrotliEncoderStateStruct { BrotliEncoderParams params; MemoryManager memory_manager_; - HasherHandle hasher_; uint64_t input_pos_; RingBuffer ringbuffer_; size_t cmd_alloc_size_; @@ -73,10 +80,17 @@ typedef struct BrotliEncoderStateStruct { int saved_dist_cache_[4]; uint16_t last_bytes_; uint8_t last_bytes_bits_; + /* "Flint" is a tiny uncompressed block emitted before the continuation + block to unwire literal context from previous data. Despite being int8_t, + field is actually BrotliEncoderFlintState enum. */ + int8_t flint_; uint8_t prev_byte_; uint8_t prev_byte2_; size_t storage_size_; uint8_t* storage_; + + Hasher hasher_; + /* Hash table for FAST_ONE_PASS_COMPRESSION_QUALITY mode. */ int small_table_[1 << 10]; /* 4KiB */ int* large_table_; /* Allocated only when needed */ @@ -114,8 +128,6 @@ typedef struct BrotliEncoderStateStruct { BROTLI_BOOL is_initialized_; } BrotliEncoderStateStruct; -static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s); - static size_t InputBlockSize(BrotliEncoderState* s) { return (size_t)1 << s->params.lgblock; } @@ -174,6 +186,11 @@ BROTLI_BOOL BrotliEncoderSetParameter( state->params.dist.num_direct_distance_codes = value; return BROTLI_TRUE; + case BROTLI_PARAM_STREAM_OFFSET: + if (value > (1u << 30)) return BROTLI_FALSE; + state->params.stream_offset = value; + return BROTLI_TRUE; + default: return BROTLI_FALSE; } } @@ -195,7 +212,7 @@ static uint8_t* GetBrotliStorage(BrotliEncoderState* s, size_t size) { if (s->storage_size_ < size) { BROTLI_FREE(m, s->storage_); s->storage_ = BROTLI_ALLOC(m, uint8_t, size); - if (BROTLI_IS_OOM(m)) return NULL; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(s->storage_)) return NULL; s->storage_size_ = size; } return s->storage_; @@ -234,7 +251,7 @@ static int* GetHashTable(BrotliEncoderState* s, int quality, s->large_table_size_ = htsize; BROTLI_FREE(m, s->large_table_); s->large_table_ = BROTLI_ALLOC(m, int, htsize); - if (BROTLI_IS_OOM(m)) return 0; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(s->large_table_)) return 0; } table = s->large_table_; } @@ -499,7 +516,7 @@ static BROTLI_BOOL ShouldCompress( /* TODO: find more precise minimal block overhead. */ if (bytes <= 2) return BROTLI_FALSE; if (num_commands < (bytes >> 8) + 2) { - if (num_literals > 0.99 * (double)bytes) { + if ((double)num_literals > 0.99 * (double)bytes) { uint32_t literal_histo[256] = { 0 }; static const uint32_t kSampleRate = 13; static const double kMinEntropy = 7.92; @@ -617,11 +634,7 @@ static void WriteMetaBlockInternal(MemoryManager* m, /* The number of distance symbols effectively used for distance histograms. It might be less than distance alphabet size for "Large Window Brotli" (32-bit). */ - uint32_t num_effective_dist_codes = block_params.dist.alphabet_size; - if (num_effective_dist_codes > BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS) { - num_effective_dist_codes = BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS; - } - BrotliOptimizeHistograms(num_effective_dist_codes, &mb); + BrotliOptimizeHistograms(block_params.dist.alphabet_size_limit, &mb); } BrotliStoreMetaBlock(m, data, wrapped_last_flush_pos, bytes, mask, prev_byte, prev_byte2, @@ -678,12 +691,23 @@ static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s) { s->last_bytes_bits_ = 0; s->last_bytes_ = 0; + s->flint_ = BROTLI_FLINT_DONE; s->remaining_metadata_bytes_ = BROTLI_UINT32_MAX; SanitizeParams(&s->params); s->params.lgblock = ComputeLgBlock(&s->params); ChooseDistanceParams(&s->params); + if (s->params.stream_offset != 0) { + s->flint_ = BROTLI_FLINT_NEEDS_2_BYTES; + /* Poison the distance cache. -16 +- 3 is still less than zero (invalid). */ + s->dist_cache_[0] = -16; + s->dist_cache_[1] = -16; + s->dist_cache_[2] = -16; + s->dist_cache_[3] = -16; + memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_)); + } + RingBufferSetup(&s->params, &s->ringbuffer_); /* Initialize last byte with stream header. */ @@ -693,8 +717,14 @@ static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s) { s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { lgwin = BROTLI_MAX(int, lgwin, 18); } - EncodeWindowBits(lgwin, s->params.large_window, - &s->last_bytes_, &s->last_bytes_bits_); + if (s->params.stream_offset == 0) { + EncodeWindowBits(lgwin, s->params.large_window, + &s->last_bytes_, &s->last_bytes_bits_); + } else { + /* Bigger values have the same effect, but could cause overflows. */ + s->params.stream_offset = BROTLI_MIN(size_t, + s->params.stream_offset, BROTLI_MAX_BACKWARD_LIMIT(lgwin)); + } } if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { @@ -712,13 +742,15 @@ static void BrotliEncoderInitParams(BrotliEncoderParams* params) { params->quality = BROTLI_DEFAULT_QUALITY; params->lgwin = BROTLI_DEFAULT_WINDOW; params->lgblock = 0; + params->stream_offset = 0; params->size_hint = 0; params->disable_literal_context_modeling = BROTLI_FALSE; BrotliInitEncoderDictionary(¶ms->dictionary); params->dist.distance_postfix_bits = 0; params->dist.num_direct_distance_codes = 0; - params->dist.alphabet_size = + params->dist.alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE(0, 0, BROTLI_MAX_DISTANCE_BITS); + params->dist.alphabet_size_limit = params->dist.alphabet_size_max; params->dist.max_distance = BROTLI_MAX_DISTANCE; } @@ -734,7 +766,7 @@ static void BrotliEncoderInitState(BrotliEncoderState* s) { s->prev_byte2_ = 0; s->storage_size_ = 0; s->storage_ = 0; - s->hasher_ = NULL; + HasherInit(&s->hasher_); s->large_table_ = NULL; s->large_table_size_ = 0; s->cmd_code_numbits_ = 0; @@ -902,6 +934,7 @@ static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes, (*bytes)--; (*wrapped_last_processed_pos)++; } + } else { } /* The copy length is at most the metablock size, and thus expressible. */ GetLengthCode(last_command->insert_len_, @@ -934,6 +967,7 @@ static BROTLI_BOOL EncodeData( uint32_t mask; MemoryManager* m = &s->memory_manager_; ContextType literal_context_mode; + ContextLut literal_context_lut; data = s->ringbuffer_.buffer_; mask = s->ringbuffer_.mask_; @@ -951,7 +985,10 @@ static BROTLI_BOOL EncodeData( BROTLI_ALLOC(m, uint32_t, kCompressFragmentTwoPassBlockSize); s->literal_buf_ = BROTLI_ALLOC(m, uint8_t, kCompressFragmentTwoPassBlockSize); - if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(s->command_buf_) || + BROTLI_IS_NULL(s->literal_buf_)) { + return BROTLI_FALSE; + } } if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY || @@ -1009,7 +1046,7 @@ static BROTLI_BOOL EncodeData( newsize += (bytes / 4) + 16; s->cmd_alloc_size_ = newsize; new_commands = BROTLI_ALLOC(m, Command, newsize); - if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_commands)) return BROTLI_FALSE; if (s->commands_) { memcpy(new_commands, s->commands_, sizeof(Command) * s->num_commands_); BROTLI_FREE(m, s->commands_); @@ -1024,6 +1061,7 @@ static BROTLI_BOOL EncodeData( literal_context_mode = ChooseContextMode( &s->params, data, WrapPosition(s->last_flush_pos_), mask, (size_t)(s->input_pos_ - s->last_flush_pos_)); + literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; @@ -1034,20 +1072,23 @@ static BROTLI_BOOL EncodeData( if (s->params.quality == ZOPFLIFICATION_QUALITY) { BROTLI_DCHECK(s->params.hasher.type == 10); BrotliCreateZopfliBackwardReferences(m, bytes, wrapped_last_processed_pos, - data, mask, &s->params, s->hasher_, s->dist_cache_, + data, mask, literal_context_lut, &s->params, + &s->hasher_, s->dist_cache_, &s->last_insert_len_, &s->commands_[s->num_commands_], &s->num_commands_, &s->num_literals_); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; } else if (s->params.quality == HQ_ZOPFLIFICATION_QUALITY) { BROTLI_DCHECK(s->params.hasher.type == 10); BrotliCreateHqZopfliBackwardReferences(m, bytes, wrapped_last_processed_pos, - data, mask, &s->params, s->hasher_, s->dist_cache_, + data, mask, literal_context_lut, &s->params, + &s->hasher_, s->dist_cache_, &s->last_insert_len_, &s->commands_[s->num_commands_], &s->num_commands_, &s->num_literals_); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; } else { BrotliCreateBackwardReferences(bytes, wrapped_last_processed_pos, - data, mask, &s->params, s->hasher_, s->dist_cache_, + data, mask, literal_context_lut, &s->params, + &s->hasher_, s->dist_cache_, &s->last_insert_len_, &s->commands_[s->num_commands_], &s->num_commands_, &s->num_literals_); } @@ -1072,7 +1113,7 @@ static BROTLI_BOOL EncodeData( s->num_commands_ < max_commands) { /* Merge with next input block. Everything will happen later. */ if (UpdateLastProcessedPos(s)) { - HasherReset(s->hasher_); + HasherReset(&s->hasher_); } *out_size = 0; return BROTLI_TRUE; @@ -1113,7 +1154,7 @@ static BROTLI_BOOL EncodeData( s->last_bytes_bits_ = storage_ix & 7u; s->last_flush_pos_ = s->input_pos_; if (UpdateLastProcessedPos(s)) { - HasherReset(s->hasher_); + HasherReset(&s->hasher_); } if (s->last_flush_pos_ > 0) { s->prev_byte_ = data[((uint32_t)s->last_flush_pos_ - 1) & mask]; @@ -1174,7 +1215,6 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( size_t total_out_size = 0; uint16_t last_bytes; uint8_t last_bytes_bits; - HasherHandle hasher = NULL; const size_t hasher_eff_size = BROTLI_MIN(size_t, input_size, BROTLI_MAX_BACKWARD_LIMIT(lgwin) + BROTLI_WINDOW_GAP); @@ -1190,6 +1230,9 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( uint8_t prev_byte = 0; uint8_t prev_byte2 = 0; + Hasher hasher; + HasherInit(&hasher); + BrotliEncoderInitParams(¶ms); params.quality = 10; params.lgwin = lgwin; @@ -1226,6 +1269,7 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( ContextType literal_context_mode = ChooseContextMode(¶ms, input_buffer, metablock_start, mask, metablock_end - metablock_start); + ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode); size_t block_start; for (block_start = metablock_start; block_start < metablock_end; ) { @@ -1234,12 +1278,12 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( ZopfliNode* nodes = BROTLI_ALLOC(m, ZopfliNode, block_size + 1); size_t path_size; size_t new_cmd_alloc_size; - if (BROTLI_IS_OOM(m)) goto oom; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(nodes)) goto oom; BrotliInitZopfliNodes(nodes, block_size + 1); - StitchToPreviousBlockH10(hasher, block_size, block_start, + StitchToPreviousBlockH10(&hasher.privat._H10, block_size, block_start, input_buffer, mask); path_size = BrotliZopfliComputeShortestPath(m, block_size, block_start, - input_buffer, mask, ¶ms, dist_cache, hasher, + input_buffer, mask, literal_context_lut, ¶ms, dist_cache, &hasher, nodes); if (BROTLI_IS_OOM(m)) goto oom; /* We allocate a command buffer in the first iteration of this loop that @@ -1254,7 +1298,7 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( num_commands + path_size + 1); if (cmd_alloc_size != new_cmd_alloc_size) { Command* new_commands = BROTLI_ALLOC(m, Command, new_cmd_alloc_size); - if (BROTLI_IS_OOM(m)) goto oom; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_commands)) goto oom; cmd_alloc_size = new_cmd_alloc_size; if (commands) { memcpy(new_commands, commands, sizeof(Command) * num_commands); @@ -1286,7 +1330,7 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( if (metablock_size == 0) { /* Write the ISLAST and ISEMPTY bits. */ storage = BROTLI_ALLOC(m, uint8_t, 16); - if (BROTLI_IS_OOM(m)) goto oom; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom; storage[0] = (uint8_t)last_bytes; storage[1] = (uint8_t)(last_bytes >> 8); BrotliWriteBits(2, 3, &storage_ix, storage); @@ -1297,7 +1341,7 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( CreateBackwardReferences is now unused. */ memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); storage = BROTLI_ALLOC(m, uint8_t, metablock_size + 16); - if (BROTLI_IS_OOM(m)) goto oom; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom; storage[0] = (uint8_t)last_bytes; storage[1] = (uint8_t)(last_bytes >> 8); BrotliStoreUncompressedMetaBlock(is_last, input_buffer, @@ -1318,14 +1362,10 @@ static BROTLI_BOOL BrotliCompressBufferQuality10( /* The number of distance symbols effectively used for distance histograms. It might be less than distance alphabet size for "Large Window Brotli" (32-bit). */ - uint32_t num_effective_dist_codes = block_params.dist.alphabet_size; - if (num_effective_dist_codes > BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS) { - num_effective_dist_codes = BROTLI_NUM_HISTOGRAM_DISTANCE_SYMBOLS; - } - BrotliOptimizeHistograms(num_effective_dist_codes, &mb); + BrotliOptimizeHistograms(block_params.dist.alphabet_size_limit, &mb); } storage = BROTLI_ALLOC(m, uint8_t, 2 * metablock_size + 503); - if (BROTLI_IS_OOM(m)) goto oom; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom; storage[0] = (uint8_t)last_bytes; storage[1] = (uint8_t)(last_bytes >> 8); BrotliStoreMetaBlock(m, input_buffer, metablock_start, metablock_size, @@ -1576,7 +1616,10 @@ static BROTLI_BOOL BrotliEncoderCompressStreamFast( BROTLI_ALLOC(m, uint32_t, kCompressFragmentTwoPassBlockSize); s->literal_buf_ = BROTLI_ALLOC(m, uint8_t, kCompressFragmentTwoPassBlockSize); - if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(s->command_buf_) || + BROTLI_IS_NULL(s->literal_buf_)) { + return BROTLI_FALSE; + } } if (s->command_buf_) { command_buf = s->command_buf_; @@ -1584,7 +1627,10 @@ static BROTLI_BOOL BrotliEncoderCompressStreamFast( } else { tmp_command_buf = BROTLI_ALLOC(m, uint32_t, buf_size); tmp_literal_buf = BROTLI_ALLOC(m, uint8_t, buf_size); - if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(tmp_command_buf) || + BROTLI_IS_NULL(tmp_literal_buf)) { + return BROTLI_FALSE; + } command_buf = tmp_command_buf; literal_buf = tmp_literal_buf; } @@ -1640,8 +1686,10 @@ static BROTLI_BOOL BrotliEncoderCompressStreamFast( &storage_ix, storage); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; } - *next_in += block_size; - *available_in -= block_size; + if (block_size != 0) { + *next_in += block_size; + *available_in -= block_size; + } if (inplace) { size_t out_bytes = storage_ix >> 3; BROTLI_DCHECK(out_bytes <= *available_out); @@ -1786,6 +1834,10 @@ BROTLI_BOOL BrotliEncoderCompressStream( } while (BROTLI_TRUE) { size_t remaining_block_size = RemainingInputBlockSize(s); + /* Shorten input to flint size. */ + if (s->flint_ >= 0 && remaining_block_size > (size_t)s->flint_) { + remaining_block_size = (size_t)s->flint_; + } if (remaining_block_size != 0 && *available_in != 0) { size_t copy_input_size = @@ -1793,10 +1845,18 @@ BROTLI_BOOL BrotliEncoderCompressStream( CopyInputToRingBuffer(s, copy_input_size, *next_in); *next_in += copy_input_size; *available_in -= copy_input_size; + if (s->flint_ > 0) s->flint_ = (int8_t)(s->flint_ - (int)copy_input_size); continue; } if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) { + /* Exit the "emit flint" workflow. */ + if (s->flint_ == BROTLI_FLINT_WAITING_FOR_FLUSHING) { + CheckFlushComplete(s); + if (s->stream_state_ == BROTLI_STREAM_PROCESSING) { + s->flint_ = BROTLI_FLINT_DONE; + } + } continue; } @@ -1810,6 +1870,11 @@ BROTLI_BOOL BrotliEncoderCompressStream( BROTLI_BOOL force_flush = TO_BROTLI_BOOL( (*available_in == 0) && op == BROTLI_OPERATION_FLUSH); BROTLI_BOOL result; + /* Force emitting (uncompressed) piece containing flint. */ + if (!is_last && s->flint_ == 0) { + s->flint_ = BROTLI_FLINT_WAITING_FOR_FLUSHING; + force_flush = BROTLI_TRUE; + } UpdateSizeHint(s, *available_in); result = EncodeData(s, is_last, force_flush, &s->available_out_, &s->next_out_); |