From e0db3f0709a737e7258fd40a7cbfe9a461ea0756 Mon Sep 17 00:00:00 2001 From: Norbert Preining Date: Thu, 16 Nov 2023 03:01:15 +0000 Subject: CTAN sync 202311160301 --- dviware/dvisvgm/libs/brotli/enc/encode.c | 875 +++++++++++++++++-------------- 1 file changed, 472 insertions(+), 403 deletions(-) (limited to 'dviware/dvisvgm/libs/brotli/enc/encode.c') diff --git a/dviware/dvisvgm/libs/brotli/enc/encode.c b/dviware/dvisvgm/libs/brotli/enc/encode.c index e77009e39a..95ff2eaf50 100644 --- a/dviware/dvisvgm/libs/brotli/enc/encode.c +++ b/dviware/dvisvgm/libs/brotli/enc/encode.c @@ -7,6 +7,8 @@ /* Implementation of Brotli compressor. */ #include +#include +#include #include /* free, malloc */ #include /* memcpy, memset */ @@ -15,24 +17,26 @@ #include "../common/context.h" #include "../common/platform.h" #include "../common/version.h" -#include "./backward_references.h" -#include "./backward_references_hq.h" -#include "./bit_cost.h" -#include "./brotli_bit_stream.h" -#include "./compress_fragment.h" -#include "./compress_fragment_two_pass.h" -#include "./encoder_dict.h" -#include "./entropy_encode.h" -#include "./fast_log.h" -#include "./hash.h" -#include "./histogram.h" -#include "./memory.h" -#include "./metablock.h" -#include "./prefix.h" -#include "./quality.h" -#include "./ringbuffer.h" -#include "./utf8_util.h" -#include "./write_bits.h" +#include "backward_references.h" +#include "backward_references_hq.h" +#include "bit_cost.h" +#include "brotli_bit_stream.h" +#include "compress_fragment.h" +#include "compress_fragment_two_pass.h" +#include "dictionary_hash.h" +#include "encoder_dict.h" +#include "entropy_encode.h" +#include "fast_log.h" +#include "hash.h" +#include "histogram.h" +#include "memory.h" +#include "metablock.h" +#include "prefix.h" +#include "state.h" +#include "quality.h" +#include "ringbuffer.h" +#include "utf8_util.h" +#include "write_bits.h" #if defined(__cplusplus) || defined(c_plusplus) extern "C" { @@ -40,94 +44,6 @@ extern "C" { #define COPY_ARRAY(dst, src) memcpy(dst, src, sizeof(src)); -typedef enum BrotliEncoderStreamState { - /* Default state. */ - BROTLI_STREAM_PROCESSING = 0, - /* Intermediate state; after next block is emitted, byte-padding should be - performed before getting back to default state. */ - BROTLI_STREAM_FLUSH_REQUESTED = 1, - /* Last metablock was produced; no more input is acceptable. */ - BROTLI_STREAM_FINISHED = 2, - /* Flushing compressed block and writing meta-data block header. */ - BROTLI_STREAM_METADATA_HEAD = 3, - /* Writing metadata block body. */ - 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_; - - uint64_t input_pos_; - RingBuffer ringbuffer_; - size_t cmd_alloc_size_; - Command* commands_; - size_t num_commands_; - size_t num_literals_; - size_t last_insert_len_; - uint64_t last_flush_pos_; - uint64_t last_processed_pos_; - int dist_cache_[BROTLI_NUM_DISTANCE_SHORT_CODES]; - 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 */ - size_t large_table_size_; - /* Command and distance prefix codes (each 64 symbols, stored back-to-back) - used for the next block in FAST_ONE_PASS_COMPRESSION_QUALITY. The command - prefix code is over a smaller alphabet with the following 64 symbols: - 0 - 15: insert length code 0, copy length code 0 - 15, same distance - 16 - 39: insert length code 0, copy length code 0 - 23 - 40 - 63: insert length code 0 - 23, copy length code 0 - Note that symbols 16 and 40 represent the same code in the full alphabet, - but we do not use either of them in FAST_ONE_PASS_COMPRESSION_QUALITY. */ - uint8_t cmd_depths_[128]; - uint16_t cmd_bits_[128]; - /* The compressed form of the command and distance prefix codes for the next - block in FAST_ONE_PASS_COMPRESSION_QUALITY. */ - uint8_t cmd_code_[512]; - size_t cmd_code_numbits_; - /* Command and literal buffers for FAST_TWO_PASS_COMPRESSION_QUALITY. */ - uint32_t* command_buf_; - uint8_t* literal_buf_; - - uint8_t* next_out_; - size_t available_out_; - size_t total_out_; - /* Temporary buffer for padding flush bits or metadata block header / body. */ - union { - uint64_t u64[2]; - uint8_t u8[16]; - } tiny_buf_; - uint32_t remaining_metadata_bytes_; - BrotliEncoderStreamState stream_state_; - - BROTLI_BOOL is_last_block_emitted_; - BROTLI_BOOL is_initialized_; -} BrotliEncoderStateStruct; - static size_t InputBlockSize(BrotliEncoderState* s) { return (size_t)1 << s->params.lgblock; } @@ -147,7 +63,7 @@ BROTLI_BOOL BrotliEncoderSetParameter( BrotliEncoderState* state, BrotliEncoderParameter p, uint32_t value) { /* Changing parameters on the fly is not implemented yet. */ if (state->is_initialized_) return BROTLI_FALSE; - /* TODO: Validate/clamp parameters here. */ + /* TODO(eustas): Validate/clamp parameters here. */ switch (p) { case BROTLI_PARAM_MODE: state->params.mode = (BrotliEncoderMode)value; @@ -283,11 +199,9 @@ static void EncodeWindowBits(int lgwin, BROTLI_BOOL large_window, } } +/* TODO(eustas): move to compress_fragment.c? */ /* Initializes the command and distance prefix codes for the first block. */ -static void InitCommandPrefixCodes(uint8_t cmd_depths[128], - uint16_t cmd_bits[128], - uint8_t cmd_code[512], - size_t* cmd_code_numbits) { +static void InitCommandPrefixCodes(BrotliOnePassArena* s) { static const uint8_t kDefaultCommandDepths[128] = { 0, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 0, 0, 0, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7, @@ -320,13 +234,13 @@ static void InitCommandPrefixCodes(uint8_t cmd_depths[128], 0x46, 0xe1, 0xb0, 0xd0, 0x4e, 0xb2, 0xf7, 0x04, 0x00, }; static const size_t kDefaultCommandCodeNumBits = 448; - COPY_ARRAY(cmd_depths, kDefaultCommandDepths); - COPY_ARRAY(cmd_bits, kDefaultCommandBits); + COPY_ARRAY(s->cmd_depth, kDefaultCommandDepths); + COPY_ARRAY(s->cmd_bits, kDefaultCommandBits); /* Initialize the pre-compressed form of the command and distance prefix codes. */ - COPY_ARRAY(cmd_code, kDefaultCommandCode); - *cmd_code_numbits = kDefaultCommandCodeNumBits; + COPY_ARRAY(s->cmd_code, kDefaultCommandCode); + s->cmd_code_numbits = kDefaultCommandCodeNumBits; } /* Decide about the context map based on the ability of the prediction @@ -401,7 +315,8 @@ static void ChooseContextMap(int quality, first 5 bits of literals. */ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input, size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint, - size_t* num_literal_contexts, const uint32_t** literal_context_map) { + size_t* num_literal_contexts, const uint32_t** literal_context_map, + uint32_t* arena) { static const uint32_t kStaticContextMapComplexUTF8[64] = { 11, 11, 12, 12, /* 0 special */ 0, 0, 0, 0, /* 4 lf */ @@ -426,16 +341,17 @@ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input, return BROTLI_FALSE; } else { const size_t end_pos = start_pos + length; - /* To make entropy calculations faster and to fit on the stack, we collect - histograms over the 5 most significant bits of literals. One histogram + /* To make entropy calculations faster, we collect histograms + over the 5 most significant bits of literals. One histogram without context and 13 additional histograms for each context value. */ - uint32_t combined_histo[32] = { 0 }; - uint32_t context_histo[13][32] = { { 0 } }; + uint32_t* BROTLI_RESTRICT const combined_histo = arena; + uint32_t* BROTLI_RESTRICT const context_histo = arena + 32; uint32_t total = 0; double entropy[3]; size_t dummy; size_t i; ContextLut utf8_lut = BROTLI_CONTEXT_LUT(CONTEXT_UTF8); + memset(arena, 0, sizeof(arena[0]) * 32 * 14); for (; start_pos + 64 <= end_pos; start_pos += 4096) { const size_t stride_end_pos = start_pos + 64; uint8_t prev2 = input[start_pos & mask]; @@ -449,7 +365,7 @@ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input, BROTLI_CONTEXT(prev1, prev2, utf8_lut)]; ++total; ++combined_histo[literal >> 3]; - ++context_histo[context][literal >> 3]; + ++context_histo[(context << 5) + (literal >> 3)]; prev2 = prev1; prev1 = literal; } @@ -457,7 +373,7 @@ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input, entropy[1] = ShannonEntropy(combined_histo, 32, &dummy); entropy[2] = 0; for (i = 0; i < 13; ++i) { - entropy[2] += ShannonEntropy(&context_histo[i][0], 32, &dummy); + entropy[2] += ShannonEntropy(context_histo + (i << 5), 32, &dummy); } entropy[0] = 1.0 / (double)total; entropy[1] *= entropy[0]; @@ -481,19 +397,21 @@ static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t* input, static void DecideOverLiteralContextModeling(const uint8_t* input, size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint, - size_t* num_literal_contexts, const uint32_t** literal_context_map) { + size_t* num_literal_contexts, const uint32_t** literal_context_map, + uint32_t* arena) { if (quality < MIN_QUALITY_FOR_CONTEXT_MODELING || length < 64) { return; } else if (ShouldUseComplexStaticContextMap( input, start_pos, length, mask, quality, size_hint, - num_literal_contexts, literal_context_map)) { + num_literal_contexts, literal_context_map, arena)) { /* Context map was already set, nothing else to do. */ } else { /* Gather bi-gram data of the UTF8 byte prefixes. To make the analysis of UTF8 data faster we only examine 64 byte long strides at every 4kB intervals. */ const size_t end_pos = start_pos + length; - uint32_t bigram_prefix_histo[9] = { 0 }; + uint32_t* BROTLI_RESTRICT const bigram_prefix_histo = arena; + memset(bigram_prefix_histo, 0, sizeof(arena[0]) * 9); for (; start_pos + 64 <= end_pos; start_pos += 4096) { static const int lut[4] = { 0, 0, 1, 2 }; const size_t stride_end_pos = start_pos + 64; @@ -513,7 +431,7 @@ static void DecideOverLiteralContextModeling(const uint8_t* input, static BROTLI_BOOL ShouldCompress( const uint8_t* data, const size_t mask, const uint64_t last_flush_pos, const size_t bytes, const size_t num_literals, const size_t num_commands) { - /* TODO: find more precise minimal block overhead. */ + /* TODO(eustas): find more precise minimal block overhead. */ if (bytes <= 2) return BROTLI_FALSE; if (num_commands < (bytes >> 8) + 2) { if ((double)num_literals > 0.99 * (double)bytes) { @@ -613,10 +531,14 @@ static void WriteMetaBlockInternal(MemoryManager* m, size_t num_literal_contexts = 1; const uint32_t* literal_context_map = NULL; if (!params->disable_literal_context_modeling) { + /* TODO(eustas): pull to higher level and reuse. */ + uint32_t* arena = BROTLI_ALLOC(m, uint32_t, 14 * 32); + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(arena)) return; DecideOverLiteralContextModeling( data, wrapped_last_flush_pos, bytes, mask, params->quality, params->size_hint, &num_literal_contexts, - &literal_context_map); + &literal_context_map, arena); + BROTLI_FREE(m, arena); } BrotliBuildMetaBlockGreedy(m, data, wrapped_last_flush_pos, mask, prev_byte, prev_byte2, literal_context_lut, num_literal_contexts, @@ -681,12 +603,13 @@ static void ChooseDistanceParams(BrotliEncoderParams* params) { } } - BrotliInitDistanceParams( - params, distance_postfix_bits, num_direct_distance_codes); + BrotliInitDistanceParams(¶ms->dist, distance_postfix_bits, + num_direct_distance_codes, params->large_window); } static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s) { - if (BROTLI_IS_OOM(&s->memory_manager_)) return BROTLI_FALSE; + MemoryManager* m = &s->memory_manager_; + if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; if (s->is_initialized_) return BROTLI_TRUE; s->last_bytes_bits_ = 0; @@ -728,8 +651,12 @@ static BROTLI_BOOL EnsureInitialized(BrotliEncoderState* s) { } if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { - InitCommandPrefixCodes(s->cmd_depths_, s->cmd_bits_, - s->cmd_code_, &s->cmd_code_numbits_); + s->one_pass_arena_ = BROTLI_ALLOC(m, BrotliOnePassArena, 1); + if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; + InitCommandPrefixCodes(s->one_pass_arena_); + } else if (s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { + s->two_pass_arena_ = BROTLI_ALLOC(m, BrotliTwoPassArena, 1); + if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; } s->is_initialized_ = BROTLI_TRUE; @@ -745,7 +672,7 @@ static void BrotliEncoderInitParams(BrotliEncoderParams* params) { params->stream_offset = 0; params->size_hint = 0; params->disable_literal_context_modeling = BROTLI_FALSE; - BrotliInitEncoderDictionary(¶ms->dictionary); + BrotliInitSharedEncoderDictionary(¶ms->dictionary); params->dist.distance_postfix_bits = 0; params->dist.num_direct_distance_codes = 0; params->dist.alphabet_size_max = @@ -754,6 +681,11 @@ static void BrotliEncoderInitParams(BrotliEncoderParams* params) { params->dist.max_distance = BROTLI_MAX_DISTANCE; } +static void BrotliEncoderCleanupParams(MemoryManager* m, + BrotliEncoderParams* params) { + BrotliCleanupSharedEncoderDictionary(m, ¶ms->dictionary); +} + static void BrotliEncoderInitState(BrotliEncoderState* s) { BrotliEncoderInitParams(&s->params); s->input_pos_ = 0; @@ -769,9 +701,11 @@ static void BrotliEncoderInitState(BrotliEncoderState* s) { HasherInit(&s->hasher_); s->large_table_ = NULL; s->large_table_size_ = 0; - s->cmd_code_numbits_ = 0; + s->one_pass_arena_ = NULL; + s->two_pass_arena_ = NULL; s->command_buf_ = NULL; s->literal_buf_ = NULL; + s->total_in_ = 0; s->next_out_ = NULL; s->available_out_ = 0; s->total_out_ = 0; @@ -796,13 +730,9 @@ static void BrotliEncoderInitState(BrotliEncoderState* s) { BrotliEncoderState* BrotliEncoderCreateInstance( brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { - BrotliEncoderState* state = 0; - if (!alloc_func && !free_func) { - state = (BrotliEncoderState*)malloc(sizeof(BrotliEncoderState)); - } else if (alloc_func && free_func) { - state = (BrotliEncoderState*)alloc_func(opaque, sizeof(BrotliEncoderState)); - } - if (state == 0) { + BrotliEncoderState* state = (BrotliEncoderState*)BrotliBootstrapAlloc( + sizeof(BrotliEncoderState), alloc_func, free_func, opaque); + if (state == NULL) { /* BROTLI_DUMP(); */ return 0; } @@ -812,19 +742,36 @@ BrotliEncoderState* BrotliEncoderCreateInstance( return state; } +#ifdef BROTLI_REPORTING +/* When BROTLI_REPORTING is defined extra reporting module have to be linked. */ +void BrotliEncoderOnFinish(const BrotliEncoderState* s); +#define BROTLI_ENCODER_ON_FINISH(s) BrotliEncoderOnFinish(s); +#else +#if !defined(BROTLI_ENCODER_ON_FINISH) +#define BROTLI_ENCODER_ON_FINISH(s) (void)(s); +#endif +#endif + static void BrotliEncoderCleanupState(BrotliEncoderState* s) { MemoryManager* m = &s->memory_manager_; + + BROTLI_ENCODER_ON_FINISH(s); + if (BROTLI_IS_OOM(m)) { BrotliWipeOutMemoryManager(m); return; } + BROTLI_FREE(m, s->storage_); BROTLI_FREE(m, s->commands_); RingBufferFree(m, &s->ringbuffer_); DestroyHasher(m, &s->hasher_); BROTLI_FREE(m, s->large_table_); + BROTLI_FREE(m, s->one_pass_arena_); + BROTLI_FREE(m, s->two_pass_arena_); BROTLI_FREE(m, s->command_buf_); BROTLI_FREE(m, s->literal_buf_); + BrotliEncoderCleanupParams(m, &s->params); } /* Deinitializes and frees BrotliEncoderState instance. */ @@ -832,11 +779,8 @@ void BrotliEncoderDestroyInstance(BrotliEncoderState* state) { if (!state) { return; } else { - MemoryManager* m = &state->memory_manager_; - brotli_free_func free_func = m->free_func; - void* opaque = m->opaque; BrotliEncoderCleanupState(state); - free_func(opaque, state); + BrotliBootstrapFree(state, &state->memory_manager_); } } @@ -925,6 +869,8 @@ static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes, uint64_t cmd_dist = (uint64_t)s->dist_cache_[0]; uint32_t distance_code = CommandRestoreDistanceCode(last_command, &s->params.dist); + const CompoundDictionary* dict = &s->params.dictionary.compound; + size_t compound_dictionary_size = dict->total_size; if (distance_code < BROTLI_NUM_DISTANCE_SHORT_CODES || distance_code - (BROTLI_NUM_DISTANCE_SHORT_CODES - 1) == cmd_dist) { if (cmd_dist <= max_distance) { @@ -935,6 +881,38 @@ static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes, (*wrapped_last_processed_pos)++; } } else { + if ((cmd_dist - max_distance - 1) < compound_dictionary_size && + last_copy_len < cmd_dist - max_distance) { + size_t address = + compound_dictionary_size - (size_t)(cmd_dist - max_distance) + + (size_t)last_copy_len; + size_t br_index = 0; + size_t br_offset; + const uint8_t* chunk; + size_t chunk_length; + while (address >= dict->chunk_offsets[br_index + 1]) br_index++; + br_offset = address - dict->chunk_offsets[br_index]; + chunk = dict->chunk_source[br_index]; + chunk_length = + dict->chunk_offsets[br_index + 1] - dict->chunk_offsets[br_index]; + while (*bytes != 0 && data[*wrapped_last_processed_pos & mask] == + chunk[br_offset]) { + last_command->copy_len_++; + (*bytes)--; + (*wrapped_last_processed_pos)++; + if (++br_offset == chunk_length) { + br_index++; + br_offset = 0; + if (br_index != dict->num_chunks) { + chunk = dict->chunk_source[br_index]; + chunk_length = dict->chunk_offsets[br_index + 1] - + dict->chunk_offsets[br_index]; + } else { + break; + } + } + } + } } /* The copy length is at most the metablock size, and thus expressible. */ GetLengthCode(last_command->insert_len_, @@ -952,8 +930,8 @@ static void ExtendLastCommand(BrotliEncoderState* s, uint32_t* bytes, If |*out_size| is positive, |*output| points to the start of the output data. If |is_last| or |force_flush| is BROTLI_TRUE, an output meta-block is always created. However, until |is_last| is BROTLI_TRUE encoder may retain up - to 7 bits of the last byte of output. To force encoder to dump the remaining - bits use WriteMetadata() to append an empty meta-data block. + to 7 bits of the last byte of output. Byte-alignment could be enforced by + emitting an empty meta-data block. Returns BROTLI_FALSE if the size of the input data is larger than input_block_size(). */ @@ -968,10 +946,39 @@ static BROTLI_BOOL EncodeData( MemoryManager* m = &s->memory_manager_; ContextType literal_context_mode; ContextLut literal_context_lut; + BROTLI_BOOL fast_compress = + s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY || + s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY; data = s->ringbuffer_.buffer_; mask = s->ringbuffer_.mask_; + if (delta == 0) { /* No new input; still might want to flush or finish. */ + if (!data) { /* No input has been processed so far. */ + if (is_last) { /* Emit complete finalized stream. */ + BROTLI_DCHECK(s->last_bytes_bits_ <= 14); + s->last_bytes_ |= (uint16_t)(3u << s->last_bytes_bits_); + s->last_bytes_bits_ = (uint8_t)(s->last_bytes_bits_ + 2u); + s->tiny_buf_.u8[0] = (uint8_t)s->last_bytes_; + s->tiny_buf_.u8[1] = (uint8_t)(s->last_bytes_ >> 8); + *output = s->tiny_buf_.u8; + *out_size = (s->last_bytes_bits_ + 7u) >> 3u; + return BROTLI_TRUE; + } else { /* No data, not last -> no-op. */ + *out_size = 0; + return BROTLI_TRUE; + } + } else { + /* Fast compress performs flush every block -> flush is no-op. */ + if (!is_last && (!force_flush || fast_compress)) { /* Another no-op. */ + *out_size = 0; + return BROTLI_TRUE; + } + } + } + BROTLI_DCHECK(data); + + if (s->params.quality > s->params.dictionary.max_quality) return BROTLI_FALSE; /* Adding more blocks after "last" block is forbidden. */ if (s->is_last_block_emitted_) return BROTLI_FALSE; if (is_last) s->is_last_block_emitted_ = BROTLI_TRUE; @@ -991,19 +998,12 @@ static BROTLI_BOOL EncodeData( } } - if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY || - s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { + if (fast_compress) { uint8_t* storage; size_t storage_ix = s->last_bytes_bits_; size_t table_size; int* table; - if (delta == 0 && !is_last) { - /* We have no new input data and we don't have to finish the stream, so - nothing to do. */ - *out_size = 0; - return BROTLI_TRUE; - } storage = GetBrotliStorage(s, 2 * bytes + 503); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; storage[0] = (uint8_t)s->last_bytes_; @@ -1012,16 +1012,14 @@ static BROTLI_BOOL EncodeData( if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { BrotliCompressFragmentFast( - m, &data[wrapped_last_processed_pos & mask], + s->one_pass_arena_, &data[wrapped_last_processed_pos & mask], bytes, is_last, table, table_size, - s->cmd_depths_, s->cmd_bits_, - &s->cmd_code_numbits_, s->cmd_code_, &storage_ix, storage); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; } else { BrotliCompressFragmentTwoPass( - m, &data[wrapped_last_processed_pos & mask], + s->two_pass_arena_, &data[wrapped_last_processed_pos & mask], bytes, is_last, s->command_buf_, s->literal_buf_, table, table_size, @@ -1099,7 +1097,7 @@ static BROTLI_BOOL EncodeData( const size_t max_commands = max_length / 8; const size_t processed_bytes = (size_t)(s->input_pos_ - s->last_flush_pos_); /* If maximal possible additional block doesn't fit metablock, flush now. */ - /* TODO: Postpone decision until next block arrives? */ + /* TODO(eustas): Postpone decision until next block arrives? */ const BROTLI_BOOL next_input_fits_metablock = TO_BROTLI_BOOL( processed_bytes + InputBlockSize(s) <= max_length); /* If block splitting is not used, then flush as soon as there is some @@ -1192,7 +1190,7 @@ static size_t WriteMetadataHeader( if (block_size == 0) { BrotliWriteBits(2, 0, &storage_ix, header); } else { - uint32_t nbits = (block_size == 1) ? 0 : + uint32_t nbits = (block_size == 1) ? 1 : (Log2FloorNonZero((uint32_t)block_size - 1) + 1); uint32_t nbytes = (nbits + 7) / 8; BrotliWriteBits(2, nbytes, &storage_ix, header); @@ -1201,228 +1199,6 @@ static size_t WriteMetadataHeader( return (storage_ix + 7u) >> 3; } -static BROTLI_BOOL BrotliCompressBufferQuality10( - int lgwin, size_t input_size, const uint8_t* input_buffer, - size_t* encoded_size, uint8_t* encoded_buffer) { - MemoryManager memory_manager; - MemoryManager* m = &memory_manager; - - const size_t mask = BROTLI_SIZE_MAX >> 1; - int dist_cache[4] = { 4, 11, 15, 16 }; - int saved_dist_cache[4] = { 4, 11, 15, 16 }; - BROTLI_BOOL ok = BROTLI_TRUE; - const size_t max_out_size = *encoded_size; - size_t total_out_size = 0; - uint16_t last_bytes; - uint8_t last_bytes_bits; - - const size_t hasher_eff_size = BROTLI_MIN(size_t, - input_size, BROTLI_MAX_BACKWARD_LIMIT(lgwin) + BROTLI_WINDOW_GAP); - - BrotliEncoderParams params; - - const int lgmetablock = BROTLI_MIN(int, 24, lgwin + 1); - size_t max_block_size; - const size_t max_metablock_size = (size_t)1 << lgmetablock; - const size_t max_literals_per_metablock = max_metablock_size / 8; - const size_t max_commands_per_metablock = max_metablock_size / 8; - size_t metablock_start = 0; - uint8_t prev_byte = 0; - uint8_t prev_byte2 = 0; - - Hasher hasher; - HasherInit(&hasher); - - BrotliEncoderInitParams(¶ms); - params.quality = 10; - params.lgwin = lgwin; - if (lgwin > BROTLI_MAX_WINDOW_BITS) { - params.large_window = BROTLI_TRUE; - } - SanitizeParams(¶ms); - params.lgblock = ComputeLgBlock(¶ms); - ChooseDistanceParams(¶ms); - max_block_size = (size_t)1 << params.lgblock; - - BrotliInitMemoryManager(m, 0, 0, 0); - - BROTLI_DCHECK(input_size <= mask + 1); - EncodeWindowBits(lgwin, params.large_window, &last_bytes, &last_bytes_bits); - InitOrStitchToPreviousBlock(m, &hasher, input_buffer, mask, ¶ms, - 0, hasher_eff_size, BROTLI_TRUE); - if (BROTLI_IS_OOM(m)) goto oom; - - while (ok && metablock_start < input_size) { - const size_t metablock_end = - BROTLI_MIN(size_t, input_size, metablock_start + max_metablock_size); - const size_t expected_num_commands = - (metablock_end - metablock_start) / 12 + 16; - Command* commands = 0; - size_t num_commands = 0; - size_t last_insert_len = 0; - size_t num_literals = 0; - size_t metablock_size = 0; - size_t cmd_alloc_size = 0; - BROTLI_BOOL is_last; - uint8_t* storage; - size_t storage_ix; - - 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; ) { - size_t block_size = - BROTLI_MIN(size_t, metablock_end - block_start, max_block_size); - ZopfliNode* nodes = BROTLI_ALLOC(m, ZopfliNode, block_size + 1); - size_t path_size; - size_t new_cmd_alloc_size; - if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(nodes)) goto oom; - BrotliInitZopfliNodes(nodes, block_size + 1); - StitchToPreviousBlockH10(&hasher.privat._H10, block_size, block_start, - input_buffer, mask); - path_size = BrotliZopfliComputeShortestPath(m, block_size, block_start, - 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 - will be likely big enough for the whole metablock, so that for most - inputs we will not have to reallocate in later iterations. We do the - allocation here and not before the loop, because if the input is small, - this will be allocated after the Zopfli cost model is freed, so this - will not increase peak memory usage. - TODO: If the first allocation is too small, increase command - buffer size exponentially. */ - new_cmd_alloc_size = BROTLI_MAX(size_t, expected_num_commands, - 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) || BROTLI_IS_NULL(new_commands)) goto oom; - cmd_alloc_size = new_cmd_alloc_size; - if (commands) { - memcpy(new_commands, commands, sizeof(Command) * num_commands); - BROTLI_FREE(m, commands); - } - commands = new_commands; - } - BrotliZopfliCreateCommands(block_size, block_start, &nodes[0], dist_cache, - &last_insert_len, ¶ms, &commands[num_commands], &num_literals); - num_commands += path_size; - block_start += block_size; - metablock_size += block_size; - BROTLI_FREE(m, nodes); - if (num_literals > max_literals_per_metablock || - num_commands > max_commands_per_metablock) { - break; - } - } - - if (last_insert_len > 0) { - InitInsertCommand(&commands[num_commands++], last_insert_len); - num_literals += last_insert_len; - } - - is_last = TO_BROTLI_BOOL(metablock_start + metablock_size == input_size); - storage = NULL; - storage_ix = last_bytes_bits; - - if (metablock_size == 0) { - /* Write the ISLAST and ISEMPTY bits. */ - storage = BROTLI_ALLOC(m, uint8_t, 16); - 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); - storage_ix = (storage_ix + 7u) & ~7u; - } else if (!ShouldCompress(input_buffer, mask, metablock_start, - metablock_size, num_literals, num_commands)) { - /* Restore the distance cache, as its last update by - 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) || BROTLI_IS_NULL(storage)) goto oom; - storage[0] = (uint8_t)last_bytes; - storage[1] = (uint8_t)(last_bytes >> 8); - BrotliStoreUncompressedMetaBlock(is_last, input_buffer, - metablock_start, mask, metablock_size, - &storage_ix, storage); - } else { - MetaBlockSplit mb; - BrotliEncoderParams block_params = params; - InitMetaBlockSplit(&mb); - BrotliBuildMetaBlock(m, input_buffer, metablock_start, mask, - &block_params, - prev_byte, prev_byte2, - commands, num_commands, - literal_context_mode, - &mb); - if (BROTLI_IS_OOM(m)) goto oom; - { - /* The number of distance symbols effectively used for distance - histograms. It might be less than distance alphabet size - for "Large Window Brotli" (32-bit). */ - BrotliOptimizeHistograms(block_params.dist.alphabet_size_limit, &mb); - } - storage = BROTLI_ALLOC(m, uint8_t, 2 * metablock_size + 503); - 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, - mask, prev_byte, prev_byte2, - is_last, - &block_params, - literal_context_mode, - commands, num_commands, - &mb, - &storage_ix, storage); - if (BROTLI_IS_OOM(m)) goto oom; - if (metablock_size + 4 < (storage_ix >> 3)) { - /* Restore the distance cache and last byte. */ - memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); - storage[0] = (uint8_t)last_bytes; - storage[1] = (uint8_t)(last_bytes >> 8); - storage_ix = last_bytes_bits; - BrotliStoreUncompressedMetaBlock(is_last, input_buffer, - metablock_start, mask, - metablock_size, &storage_ix, storage); - } - DestroyMetaBlockSplit(m, &mb); - } - last_bytes = (uint16_t)(storage[storage_ix >> 3]); - last_bytes_bits = storage_ix & 7u; - metablock_start += metablock_size; - if (metablock_start < input_size) { - prev_byte = input_buffer[metablock_start - 1]; - prev_byte2 = input_buffer[metablock_start - 2]; - } - /* Save the state of the distance cache in case we need to restore it for - emitting an uncompressed block. */ - memcpy(saved_dist_cache, dist_cache, 4 * sizeof(dist_cache[0])); - - { - const size_t out_size = storage_ix >> 3; - total_out_size += out_size; - if (total_out_size <= max_out_size) { - memcpy(encoded_buffer, storage, out_size); - encoded_buffer += out_size; - } else { - ok = BROTLI_FALSE; - } - } - BROTLI_FREE(m, storage); - BROTLI_FREE(m, commands); - } - - *encoded_size = total_out_size; - DestroyHasher(m, &hasher); - return ok; - -oom: - BrotliWipeOutMemoryManager(m); - return BROTLI_FALSE; -} - size_t BrotliEncoderMaxCompressedSize(size_t input_size) { /* [window bits / empty metadata] + N * [uncompressed] + [last empty] */ size_t num_large_blocks = input_size >> 14; @@ -1470,7 +1246,8 @@ static size_t MakeUncompressedStream( BROTLI_BOOL BrotliEncoderCompress( int quality, int lgwin, BrotliEncoderMode mode, size_t input_size, - const uint8_t input_buffer[BROTLI_ARRAY_PARAM(input_size)], size_t* encoded_size, + const uint8_t input_buffer[BROTLI_ARRAY_PARAM(input_size)], + size_t* encoded_size, uint8_t encoded_buffer[BROTLI_ARRAY_PARAM(*encoded_size)]) { BrotliEncoderState* s; size_t out_size = *encoded_size; @@ -1487,17 +1264,6 @@ BROTLI_BOOL BrotliEncoderCompress( *encoded_buffer = 6; return BROTLI_TRUE; } - if (quality == 10) { - /* TODO: Implement this direct path for all quality levels. */ - const int lg_win = BROTLI_MIN(int, BROTLI_LARGE_MAX_WINDOW_BITS, - BROTLI_MAX(int, 16, lgwin)); - int ok = BrotliCompressBufferQuality10(lg_win, input_size, input_buffer, - encoded_size, encoded_buffer); - if (!ok || (max_out_size && *encoded_size > max_out_size)) { - goto fallback; - } - return BROTLI_TRUE; - } s = BrotliEncoderCreateInstance(0, 0, 0); if (!s) { @@ -1509,6 +1275,7 @@ BROTLI_BOOL BrotliEncoderCompress( uint8_t* next_out = encoded_buffer; size_t total_out = 0; BROTLI_BOOL result = BROTLI_FALSE; + /* TODO(eustas): check that parameters are sane. */ BrotliEncoderSetParameter(s, BROTLI_PARAM_QUALITY, (uint32_t)quality); BrotliEncoderSetParameter(s, BROTLI_PARAM_LGWIN, (uint32_t)lgwin); BrotliEncoderSetParameter(s, BROTLI_PARAM_MODE, (uint32_t)mode); @@ -1560,6 +1327,18 @@ static void InjectBytePaddingBlock(BrotliEncoderState* s) { s->available_out_ += (seal_bits + 7) >> 3; } +/* Fills the |total_out|, if it is not NULL. */ +static void SetTotalOut(BrotliEncoderState* s, size_t* total_out) { + if (total_out) { + /* Saturating conversion uint64_t -> size_t */ + size_t result = (size_t)-1; + if (s->total_out_ < result) { + result = (size_t)s->total_out_; + } + *total_out = result; + } +} + /* Injects padding bits or pushes compressed data to output. Returns false if nothing is done. */ static BROTLI_BOOL InjectFlushOrPushOutput(BrotliEncoderState* s, @@ -1579,7 +1358,7 @@ static BROTLI_BOOL InjectFlushOrPushOutput(BrotliEncoderState* s, s->next_out_ += copy_output_size; s->available_out_ -= copy_output_size; s->total_out_ += copy_output_size; - if (total_out) *total_out = s->total_out_; + SetTotalOut(s, total_out); return BROTLI_TRUE; } @@ -1676,19 +1455,19 @@ static BROTLI_BOOL BrotliEncoderCompressStreamFast( if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { - BrotliCompressFragmentFast(m, *next_in, block_size, is_last, table, - table_size, s->cmd_depths_, s->cmd_bits_, &s->cmd_code_numbits_, - s->cmd_code_, &storage_ix, storage); + BrotliCompressFragmentFast(s->one_pass_arena_, *next_in, block_size, + is_last, table, table_size, &storage_ix, storage); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; } else { - BrotliCompressFragmentTwoPass(m, *next_in, block_size, is_last, - command_buf, literal_buf, table, table_size, + BrotliCompressFragmentTwoPass(s->two_pass_arena_, *next_in, block_size, + is_last, command_buf, literal_buf, table, table_size, &storage_ix, storage); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; } if (block_size != 0) { *next_in += block_size; *available_in -= block_size; + s->total_in_ += block_size; } if (inplace) { size_t out_bytes = storage_ix >> 3; @@ -1697,7 +1476,7 @@ static BROTLI_BOOL BrotliEncoderCompressStreamFast( *next_out += out_bytes; *available_out -= out_bytes; s->total_out_ += out_bytes; - if (total_out) *total_out = s->total_out_; + SetTotalOut(s, total_out); } else { size_t out_bytes = storage_ix >> 3; s->next_out_ = storage; @@ -1766,6 +1545,7 @@ static BROTLI_BOOL ProcessMetadata( memcpy(*next_out, *next_in, copy); *next_in += copy; *available_in -= copy; + s->total_in_ += copy; /* not actually data input, though */ s->remaining_metadata_bytes_ -= copy; *next_out += copy; *available_out -= copy; @@ -1776,6 +1556,7 @@ static BROTLI_BOOL ProcessMetadata( memcpy(s->next_out_, *next_in, copy); *next_in += copy; *available_in -= copy; + s->total_in_ += copy; /* not actually data input, though */ s->remaining_metadata_bytes_ -= copy; s->available_out_ = copy; } @@ -1803,7 +1584,7 @@ static void UpdateSizeHint(BrotliEncoderState* s, size_t available_in) { BROTLI_BOOL BrotliEncoderCompressStream( BrotliEncoderState* s, BrotliEncoderOperation op, size_t* available_in, - const uint8_t** next_in, size_t* available_out,uint8_t** next_out, + const uint8_t** next_in, size_t* available_out, uint8_t** next_out, size_t* total_out) { if (!EnsureInitialized(s)) return BROTLI_FALSE; @@ -1845,6 +1626,7 @@ BROTLI_BOOL BrotliEncoderCompressStream( CopyInputToRingBuffer(s, copy_input_size, *next_in); *next_in += copy_input_size; *available_in -= copy_input_size; + s->total_in_ += copy_input_size; if (s->flint_ > 0) s->flint_ = (int8_t)(s->flint_ - (int)copy_input_size); continue; } @@ -1922,6 +1704,293 @@ uint32_t BrotliEncoderVersion(void) { return BROTLI_VERSION; } +BrotliEncoderPreparedDictionary* BrotliEncoderPrepareDictionary( + BrotliSharedDictionaryType type, size_t size, + const uint8_t data[BROTLI_ARRAY_PARAM(size)], int quality, + brotli_alloc_func alloc_func, brotli_free_func free_func, void* opaque) { + ManagedDictionary* managed_dictionary = NULL; + BROTLI_BOOL type_is_known = BROTLI_FALSE; + type_is_known |= (type == BROTLI_SHARED_DICTIONARY_RAW); +#if defined(BROTLI_EXPERIMENTAL) + type_is_known |= (type == BROTLI_SHARED_DICTIONARY_SERIALIZED); +#endif /* BROTLI_EXPERIMENTAL */ + if (!type_is_known) { + return NULL; + } + managed_dictionary = + BrotliCreateManagedDictionary(alloc_func, free_func, opaque); + if (managed_dictionary == NULL) { + return NULL; + } + if (type == BROTLI_SHARED_DICTIONARY_RAW) { + managed_dictionary->dictionary = (uint32_t*)CreatePreparedDictionary( + &managed_dictionary->memory_manager_, data, size); + } +#if defined(BROTLI_EXPERIMENTAL) + if (type == BROTLI_SHARED_DICTIONARY_SERIALIZED) { + SharedEncoderDictionary* dict = (SharedEncoderDictionary*)BrotliAllocate( + &managed_dictionary->memory_manager_, sizeof(SharedEncoderDictionary)); + managed_dictionary->dictionary = (uint32_t*)dict; + if (dict != NULL) { + BROTLI_BOOL ok = BrotliInitCustomSharedEncoderDictionary( + &managed_dictionary->memory_manager_, data, size, quality, dict); + if (!ok) { + BrotliFree(&managed_dictionary->memory_manager_, dict); + managed_dictionary->dictionary = NULL; + } + } + } +#else /* BROTLI_EXPERIMENTAL */ + (void)quality; +#endif /* BROTLI_EXPERIMENTAL */ + if (managed_dictionary->dictionary == NULL) { + BrotliDestroyManagedDictionary(managed_dictionary); + return NULL; + } + return (BrotliEncoderPreparedDictionary*)managed_dictionary; +} + +void BrotliEncoderDestroyPreparedDictionary( + BrotliEncoderPreparedDictionary* dictionary) { + ManagedDictionary* dict = (ManagedDictionary*)dictionary; + if (!dictionary) return; + /* First field of dictionary structs. */ + /* Only managed dictionaries are eligible for destruction by this method. */ + if (dict->magic != kManagedDictionaryMagic) { + return; + } + if (dict->dictionary == NULL) { + /* This should never ever happen. */ + } else if (*dict->dictionary == kLeanPreparedDictionaryMagic) { + DestroyPreparedDictionary( + &dict->memory_manager_, (PreparedDictionary*)dict->dictionary); + } else if (*dict->dictionary == kSharedDictionaryMagic) { + BrotliCleanupSharedEncoderDictionary(&dict->memory_manager_, + (SharedEncoderDictionary*)dict->dictionary); + BrotliFree(&dict->memory_manager_, dict->dictionary); + } else { + /* There is also kPreparedDictionaryMagic, but such instances should be + * constructed and destroyed by different means. */ + } + dict->dictionary = NULL; + BrotliDestroyManagedDictionary(dict); +} + +BROTLI_BOOL BrotliEncoderAttachPreparedDictionary(BrotliEncoderState* state, + const BrotliEncoderPreparedDictionary* dictionary) { + /* First field of dictionary structs */ + const BrotliEncoderPreparedDictionary* dict = dictionary; + uint32_t magic = *((const uint32_t*)dict); + SharedEncoderDictionary* current = NULL; + if (magic == kManagedDictionaryMagic) { + /* Unwrap managed dictionary. */ + ManagedDictionary* managed_dictionary = (ManagedDictionary*)dict; + magic = *managed_dictionary->dictionary; + dict = (BrotliEncoderPreparedDictionary*)managed_dictionary->dictionary; + } + current = &state->params.dictionary; + if (magic == kPreparedDictionaryMagic || + magic == kLeanPreparedDictionaryMagic) { + const PreparedDictionary* prepared = (const PreparedDictionary*)dict; + if (!AttachPreparedDictionary(¤t->compound, prepared)) { + return BROTLI_FALSE; + } + } else if (magic == kSharedDictionaryMagic) { + const SharedEncoderDictionary* attached = + (const SharedEncoderDictionary*)dict; + BROTLI_BOOL was_default = !current->contextual.context_based && + current->contextual.num_dictionaries == 1 && + current->contextual.dict[0]->hash_table_words == + kStaticDictionaryHashWords && + current->contextual.dict[0]->hash_table_lengths == + kStaticDictionaryHashLengths; + BROTLI_BOOL new_default = !attached->contextual.context_based && + attached->contextual.num_dictionaries == 1 && + attached->contextual.dict[0]->hash_table_words == + kStaticDictionaryHashWords && + attached->contextual.dict[0]->hash_table_lengths == + kStaticDictionaryHashLengths; + size_t i; + if (state->is_initialized_) return BROTLI_FALSE; + current->max_quality = + BROTLI_MIN(int, current->max_quality, attached->max_quality); + for (i = 0; i < attached->compound.num_chunks; i++) { + if (!AttachPreparedDictionary(¤t->compound, + attached->compound.chunks[i])) { + return BROTLI_FALSE; + } + } + if (!new_default) { + if (!was_default) return BROTLI_FALSE; + /* Copy by value, but then set num_instances_ to 0 because their memory + is managed by attached, not by current */ + current->contextual = attached->contextual; + current->contextual.num_instances_ = 0; + } + } else { + return BROTLI_FALSE; + } + return BROTLI_TRUE; +} + +size_t BrotliEncoderEstimatePeakMemoryUsage(int quality, int lgwin, + size_t input_size) { + BrotliEncoderParams params; + size_t memory_manager_slots = BROTLI_ENCODER_MEMORY_MANAGER_SLOTS; + size_t memory_manager_size = memory_manager_slots * sizeof(void*); + BrotliEncoderInitParams(¶ms); + params.quality = quality; + params.lgwin = lgwin; + params.size_hint = input_size; + params.large_window = lgwin > BROTLI_MAX_WINDOW_BITS; + SanitizeParams(¶ms); + params.lgblock = ComputeLgBlock(¶ms); + ChooseHasher(¶ms, ¶ms.hasher); + if (params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY || + params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) { + size_t state_size = sizeof(BrotliEncoderState); + size_t block_size = BROTLI_MIN(size_t, input_size, (1ul << params.lgwin)); + size_t hash_table_size = + HashTableSize(MaxHashTableSize(params.quality), block_size); + size_t hash_size = + (hash_table_size < (1u << 10)) ? 0 : sizeof(int) * hash_table_size; + size_t cmdbuf_size = params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY ? + 5 * BROTLI_MIN(size_t, block_size, 1ul << 17) : 0; + if (params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) { + state_size += sizeof(BrotliOnePassArena); + } else { + state_size += sizeof(BrotliTwoPassArena); + } + return hash_size + cmdbuf_size + state_size; + } else { + size_t short_ringbuffer_size = (size_t)1 << params.lgblock; + int ringbuffer_bits = ComputeRbBits(¶ms); + size_t ringbuffer_size = input_size < short_ringbuffer_size ? + input_size : (1u << ringbuffer_bits) + short_ringbuffer_size; + size_t hash_size[4] = {0}; + size_t metablock_size = + BROTLI_MIN(size_t, input_size, MaxMetablockSize(¶ms)); + size_t inputblock_size = + BROTLI_MIN(size_t, input_size, (size_t)1 << params.lgblock); + size_t cmdbuf_size = metablock_size * 2 + inputblock_size * 6; + size_t outbuf_size = metablock_size * 2 + 503; + size_t histogram_size = 0; + HasherSize(¶ms, BROTLI_TRUE, input_size, hash_size); + if (params.quality < MIN_QUALITY_FOR_BLOCK_SPLIT) { + cmdbuf_size = BROTLI_MIN(size_t, cmdbuf_size, + MAX_NUM_DELAYED_SYMBOLS * sizeof(Command) + inputblock_size * 12); + } + if (params.quality >= MIN_QUALITY_FOR_HQ_BLOCK_SPLITTING) { + /* Only a very rough estimation, based on enwik8. */ + histogram_size = 200 << 20; + } else if (params.quality >= MIN_QUALITY_FOR_BLOCK_SPLIT) { + size_t literal_histograms = + BROTLI_MIN(size_t, metablock_size / 6144, 256); + size_t command_histograms = + BROTLI_MIN(size_t, metablock_size / 6144, 256); + size_t distance_histograms = + BROTLI_MIN(size_t, metablock_size / 6144, 256); + histogram_size = literal_histograms * sizeof(HistogramLiteral) + + command_histograms * sizeof(HistogramCommand) + + distance_histograms * sizeof(HistogramDistance); + } + return (memory_manager_size + ringbuffer_size + + hash_size[0] + hash_size[1] + hash_size[2] + hash_size[3] + + cmdbuf_size + + outbuf_size + + histogram_size); + } +} +size_t BrotliEncoderGetPreparedDictionarySize( + const BrotliEncoderPreparedDictionary* prepared_dictionary) { + /* First field of dictionary structs */ + const BrotliEncoderPreparedDictionary* prepared = prepared_dictionary; + uint32_t magic = *((const uint32_t*)prepared); + size_t overhead = 0; + if (magic == kManagedDictionaryMagic) { + const ManagedDictionary* managed = (const ManagedDictionary*)prepared; + overhead = sizeof(ManagedDictionary); + magic = *managed->dictionary; + prepared = (const BrotliEncoderPreparedDictionary*)managed->dictionary; + } + + if (magic == kPreparedDictionaryMagic) { + const PreparedDictionary* dictionary = + (const PreparedDictionary*)prepared; + /* Keep in sync with step 3 of CreatePreparedDictionary */ + return sizeof(PreparedDictionary) + dictionary->source_size + + (sizeof(uint32_t) << dictionary->slot_bits) + + (sizeof(uint16_t) << dictionary->bucket_bits) + + (sizeof(uint32_t) * dictionary->num_items) + overhead; + } else if (magic == kLeanPreparedDictionaryMagic) { + const PreparedDictionary* dictionary = + (const PreparedDictionary*)prepared; + /* Keep in sync with step 3 of CreatePreparedDictionary */ + return sizeof(PreparedDictionary) + sizeof(uint8_t*) + + (sizeof(uint32_t) << dictionary->slot_bits) + + (sizeof(uint16_t) << dictionary->bucket_bits) + + (sizeof(uint32_t) * dictionary->num_items) + overhead; + } else if (magic == kSharedDictionaryMagic) { + const SharedEncoderDictionary* dictionary = + (const SharedEncoderDictionary*)prepared; + const CompoundDictionary* compound = &dictionary->compound; + const ContextualEncoderDictionary* contextual = &dictionary->contextual; + size_t result = sizeof(*dictionary); + size_t i; + size_t num_instances; + const BrotliEncoderDictionary* instances; + for (i = 0; i < compound->num_prepared_instances_; i++) { + size_t size = BrotliEncoderGetPreparedDictionarySize( + (const BrotliEncoderPreparedDictionary*) + compound->prepared_instances_[i]); + if (!size) return 0; /* error */ + result += size; + } + if (contextual->context_based) { + num_instances = contextual->num_instances_; + instances = contextual->instances_; + result += sizeof(*instances) * num_instances; + } else { + num_instances = 1; + instances = &contextual->instance_; + } + for (i = 0; i < num_instances; i++) { + const BrotliEncoderDictionary* dict = &instances[i]; + result += dict->trie.pool_capacity * sizeof(BrotliTrieNode); + if (dict->hash_table_data_words_) { + result += sizeof(kStaticDictionaryHashWords); + } + if (dict->hash_table_data_lengths_) { + result += sizeof(kStaticDictionaryHashLengths); + } + if (dict->buckets_data_) { + result += sizeof(*dict->buckets_data_) * dict->buckets_alloc_size_; + } + if (dict->dict_words_data_) { + result += sizeof(*dict->dict_words) * dict->dict_words_alloc_size_; + } + if (dict->words_instance_) { + result += sizeof(*dict->words_instance_); + /* data_size not added here: it is never allocated by the + SharedEncoderDictionary, instead it always points to the file + already loaded in memory. So if the caller wants to include + this memory as well, add the size of the loaded dictionary + file to this. */ + } + } + return result + overhead; + } + return 0; /* error */ +} + +#if defined(BROTLI_TEST) +size_t MakeUncompressedStreamForTest(const uint8_t*, size_t, uint8_t*); +size_t MakeUncompressedStreamForTest( + const uint8_t* input, size_t input_size, uint8_t* output) { + return MakeUncompressedStream(input, input_size, output); +} +#endif + #if defined(__cplusplus) || defined(c_plusplus) } /* extern "C" */ #endif -- cgit v1.2.3