diff options
-rw-r--r-- | enc/encode.c | 95 | ||||
-rw-r--r-- | enc/metablock.c | 23 |
2 files changed, 107 insertions, 11 deletions
diff --git a/enc/encode.c b/enc/encode.c index dc0ddc1..372af65 100644 --- a/enc/encode.c +++ b/enc/encode.c @@ -381,12 +381,100 @@ static void ChooseContextMap(int quality, } } +/* Decide if we want to use a more complex static context map containing 13 + context values, based on the entropy reduction of histograms over the + 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, ContextType* literal_context_mode, + size_t* num_literal_contexts, const uint32_t** literal_context_map) { + static const uint32_t kStaticContextMapComplexUTF8[64] = { + 11, 11, 12, 12, /* 0 special */ + 0, 0, 0, 0, /* 4 lf */ + 1, 1, 9, 9, /* 8 space */ + 2, 2, 2, 2, /* !, first after space/lf and after something else. */ + 1, 1, 1, 1, /* " */ + 8, 3, 3, 3, /* % */ + 1, 1, 1, 1, /* ({[ */ + 2, 2, 2, 2, /* }]) */ + 8, 4, 4, 4, /* :; */ + 8, 7, 4, 4, /* . */ + 8, 0, 0, 0, /* > */ + 3, 3, 3, 3, /* [0..9] */ + 5, 5, 10, 5, /* [A-Z] */ + 5, 5, 10, 5, + 6, 6, 6, 6, /* [a-z] */ + 6, 6, 6, 6, + }; + BROTLI_UNUSED(quality); + /* Try the more complex static context map only for long data. */ + if (size_hint < (1 << 20)) { + 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 + 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 total = 0; + double entropy[3]; + size_t dummy; + size_t i; + 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]; + uint8_t prev1 = input[(start_pos + 1) & mask]; + size_t pos; + /* To make the analysis of the data faster we only examine 64 byte long + strides at every 4kB intervals. */ + for (pos = start_pos + 2; pos < stride_end_pos; ++pos) { + const uint8_t literal = input[pos & mask]; + const uint8_t context = (uint8_t)kStaticContextMapComplexUTF8[ + Context(prev1, prev2, CONTEXT_UTF8)]; + ++total; + ++combined_histo[literal >> 3]; + ++context_histo[context][literal >> 3]; + prev2 = prev1; + prev1 = literal; + } + } + 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[0] = 1.0 / (double)total; + entropy[1] *= entropy[0]; + entropy[2] *= entropy[0]; + /* The triggering heuristics below were tuned by compressing the individual + files of the silesia corpus. If we skip this kind of context modeling + for not very well compressible input (i.e. entropy using context modeling + is 60% of maximal entropy) or if expected savings by symbol are less + than 0.2 bits, then in every case when it triggers, the final compression + ratio is improved. Note however that this heuristics might be too strict + for some cases and could be tuned further. */ + if (entropy[2] > 3.0 || entropy[1] - entropy[2] < 0.2) { + return BROTLI_FALSE; + } else { + *literal_context_mode = CONTEXT_UTF8; + *num_literal_contexts = 13; + *literal_context_map = kStaticContextMapComplexUTF8; + return BROTLI_TRUE; + } + } +} + static void DecideOverLiteralContextModeling(const uint8_t* input, size_t start_pos, size_t length, size_t mask, int quality, - ContextType* literal_context_mode, size_t* num_literal_contexts, - const uint32_t** literal_context_map) { + size_t size_hint, ContextType* literal_context_mode, + size_t* num_literal_contexts, const uint32_t** literal_context_map) { if (quality < MIN_QUALITY_FOR_CONTEXT_MODELING || length < 64) { return; + } else if (ShouldUseComplexStaticContextMap( + input, start_pos, length, mask, quality, size_hint, literal_context_mode, + num_literal_contexts, literal_context_map)) { + /* 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 @@ -508,7 +596,8 @@ static void WriteMetaBlockInternal(MemoryManager* m, if (!params->disable_literal_context_modeling) { DecideOverLiteralContextModeling( data, wrapped_last_flush_pos, bytes, mask, params->quality, - &literal_context_mode, &num_literal_contexts, &literal_context_map); + params->size_hint, &literal_context_mode, &num_literal_contexts, + &literal_context_map); } BrotliBuildMetaBlockGreedy(m, data, wrapped_last_flush_pos, mask, prev_byte, prev_byte2, literal_context_mode, num_literal_contexts, diff --git a/enc/metablock.c b/enc/metablock.c index 86118c2..1db76da 100644 --- a/enc/metablock.c +++ b/enc/metablock.c @@ -156,7 +156,7 @@ void BrotliBuildMetaBlock(MemoryManager* m, #include "./metablock_inc.h" /* NOLINT(build/include) */ #undef FN -#define BROTLI_MAX_STATIC_CONTEXTS 3 +#define BROTLI_MAX_STATIC_CONTEXTS 13 /* Greedy block splitter for one block category (literal, command or distance). Gathers histograms for all context buckets. */ @@ -241,7 +241,7 @@ static void InitContextBlockSplitter( (2) emits the current block with the type of the second last block; (3) merges the current block with the last block. */ static void ContextBlockSplitterFinishBlock( - ContextBlockSplitter* self, BROTLI_BOOL is_final) { + ContextBlockSplitter* self, MemoryManager* m, BROTLI_BOOL is_final) { BlockSplit* split = self->split_; const size_t num_contexts = self->num_contexts_; double* last_entropy = self->last_entropy_; @@ -275,10 +275,12 @@ static void ContextBlockSplitterFinishBlock( Decide over the split based on the total reduction of entropy across all contexts. */ double entropy[BROTLI_MAX_STATIC_CONTEXTS]; - HistogramLiteral combined_histo[2 * BROTLI_MAX_STATIC_CONTEXTS]; /* 6KiB */ + HistogramLiteral* combined_histo = + BROTLI_ALLOC(m, HistogramLiteral, 2 * num_contexts); double combined_entropy[2 * BROTLI_MAX_STATIC_CONTEXTS]; double diff[2] = { 0.0 }; size_t i; + if (BROTLI_IS_OOM(m)) return; for (i = 0; i < num_contexts; ++i) { size_t curr_histo_ix = self->curr_histogram_ix_ + i; size_t j; @@ -350,6 +352,7 @@ static void ContextBlockSplitterFinishBlock( self->target_block_size_ += self->min_block_size_; } } + BROTLI_FREE(m, combined_histo); } if (is_final) { *self->histograms_size_ = split->num_types * num_contexts; @@ -360,12 +363,14 @@ static void ContextBlockSplitterFinishBlock( /* Adds the next symbol to the current block type and context. When the current block reaches the target size, decides on merging the block. */ static void ContextBlockSplitterAddSymbol( - ContextBlockSplitter* self, size_t symbol, size_t context) { + ContextBlockSplitter* self, MemoryManager* m, + size_t symbol, size_t context) { HistogramAddLiteral(&self->histograms_[self->curr_histogram_ix_ + context], symbol); ++self->block_size_; if (self->block_size_ == self->target_block_size_) { - ContextBlockSplitterFinishBlock(self, /* is_final = */ BROTLI_FALSE); + ContextBlockSplitterFinishBlock(self, m, /* is_final = */ BROTLI_FALSE); + if (BROTLI_IS_OOM(m)) return; } } @@ -437,8 +442,9 @@ static BROTLI_INLINE void BrotliBuildMetaBlockGreedyInternal( BlockSplitterAddSymbolLiteral(&lit_blocks.plain, literal); } else { size_t context = Context(prev_byte, prev_byte2, literal_context_mode); - ContextBlockSplitterAddSymbol(&lit_blocks.ctx, literal, - static_context_map[context]); + ContextBlockSplitterAddSymbol(&lit_blocks.ctx, m, literal, + static_context_map[context]); + if (BROTLI_IS_OOM(m)) return; } prev_byte2 = prev_byte; prev_byte = literal; @@ -459,7 +465,8 @@ static BROTLI_INLINE void BrotliBuildMetaBlockGreedyInternal( &lit_blocks.plain, /* is_final = */ BROTLI_TRUE); } else { ContextBlockSplitterFinishBlock( - &lit_blocks.ctx, /* is_final = */ BROTLI_TRUE); + &lit_blocks.ctx, m, /* is_final = */ BROTLI_TRUE); + if (BROTLI_IS_OOM(m)) return; } BlockSplitterFinishBlockCommand(&cmd_blocks, /* is_final = */ BROTLI_TRUE); BlockSplitterFinishBlockDistance(&dist_blocks, /* is_final = */ BROTLI_TRUE); |