Add an experimental feature to automatically detect Base64 encoded content in the input stream and optimize compression by skipping dictionary and history lookups for these regions. This is controlled by a new parameter BROTLI_PARAM_BASE64_MODE. PiperOrigin-RevId: 948030912
diff --git a/c/enc/backward_references.c b/c/enc/backward_references.c index b48dd85..b5c818d 100644 --- a/c/enc/backward_references.c +++ b/c/enc/backward_references.c
@@ -18,6 +18,68 @@ #include "params.h" #include "quality.h" /* IWYU pragma: keep for inc */ +BROTLI_INTERNAL const BROTLI_MODEL("small") + uint8_t kIsBase64[256] = { + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, + 0, 0, 0, 1, /* 43 '+', 47 '/' (45 '-' is 0) */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, /* 48-57 '0'-'9' (61 '=' + is 0) */ + 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 65-79 'A'-'O' */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, /* 80-90 'P'-'Z' */ + 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, /* 97-111 'a'-'o' */ + 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, /* 112-122 'p'-'z' */ + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, + 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0}; + +static const size_t kBase64TriggerLen = 8; + +static BROTLI_INLINE BROTLI_BOOL IsBase64Char(uint8_t c) { + return TO_BROTLI_BOOL(kIsBase64[c]); +} + +static BROTLI_INLINE BROTLI_BOOL MatchTrigger(const uint8_t* ringbuffer, + size_t mask, size_t pos) { + const char* trigger = ";base64,"; + size_t i; + for (i = 0; i < kBase64TriggerLen; ++i) { + if (ringbuffer[(pos + i) & mask] != trigger[i]) return BROTLI_FALSE; + } + return BROTLI_TRUE; +} + +static size_t FindNextBase64Trigger(const uint8_t* ringbuffer, size_t mask, + size_t pos, size_t end) { + while (pos + kBase64TriggerLen <= end) { + size_t ringbuffer_size = mask + 1; + size_t pos_index = pos & mask; + size_t contiguous_len = ringbuffer_size - pos_index; + size_t max_scan_len = end - pos; + size_t scan_len = BROTLI_MIN(size_t, contiguous_len, max_scan_len); + + const uint8_t* p = + (const uint8_t*)memchr(&ringbuffer[pos_index], ';', scan_len); + if (p != NULL) { + size_t offset = (size_t)(p - &ringbuffer[pos_index]); + if (pos + offset + kBase64TriggerLen <= end) { + if (MatchTrigger(ringbuffer, mask, pos + offset)) { + return pos + offset; + } + } else { + return end; + } + pos += offset + 1; + } else { + pos += scan_len; + } + } + return end; +} + #if defined(__cplusplus) || defined(c_plusplus) extern "C" { #endif
diff --git a/c/enc/backward_references_inc.h b/c/enc/backward_references_inc.h index 752c12e..02e1f4f 100644 --- a/c/enc/backward_references_inc.h +++ b/c/enc/backward_references_inc.h
@@ -35,7 +35,60 @@ FN(PrepareDistanceCache)(privat, dist_cache); + size_t next_base64_pos = pos_end; + if (params->base64_mode && + hasher->common.num_base64_regions < params->max_base64_regions) { + next_base64_pos = + FindNextBase64Trigger(ringbuffer, ringbuffer_mask, position, pos_end); + } while (position + FN(HashTypeLength)() < pos_end) { + if (position >= next_base64_pos) { + /* Find where it ends */ + size_t scan_pos = position + kBase64TriggerLen; + size_t first_equal_pos = 0; + while (scan_pos < pos_end) { + uint8_t c = ringbuffer[scan_pos & ringbuffer_mask]; + if (IsBase64Char(c)) { + if (first_equal_pos != 0) { + scan_pos = first_equal_pos; + break; + } + scan_pos++; + } else if (c == '=') { + if (first_equal_pos == 0) { + first_equal_pos = scan_pos; + } + scan_pos++; + } else { + break; + } + } + /* Jump directly to the end of base64 block */ + /* Skip the ';base64,' trigger */ + size_t start_pos = position + kBase64TriggerLen; + size_t length = scan_pos - start_pos; + /* Exclude '=' characters from the flat 6-bit entropy block */ + while (length > 0 && + ringbuffer[(start_pos + length - 1) & ringbuffer_mask] == '=') { + length--; + } + if (length > 0) { + hasher->common.base64_regions[hasher->common.num_base64_regions] + .start_literal_pos = start_pos; + hasher->common.base64_regions[hasher->common.num_base64_regions] + .length = length; + hasher->common.num_base64_regions++; + } + insert_length += (scan_pos - position); + position = scan_pos; + if (hasher->common.num_base64_regions < params->max_base64_regions) { + next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask, + position, pos_end); + } else { + next_base64_pos = pos_end; + } + continue; + } size_t max_length = pos_end - position; size_t max_distance = BROTLI_MIN(size_t, position, max_backward_limit); size_t dictionary_start = BROTLI_MIN(size_t,
diff --git a/c/enc/block_encoder_inc.h b/c/enc/block_encoder_inc.h index 8cbd5ea..9ae6e97 100644 --- a/c/enc/block_encoder_inc.h +++ b/c/enc/block_encoder_inc.h
@@ -1,20 +1,14 @@ -/* NOLINT(build/header_guard) */ -/* Copyright 2014 Google Inc. All Rights Reserved. - - Distributed under MIT license. - See file LICENSE for detail or copy at https://opensource.org/licenses/MIT -*/ - -/* template parameters: FN */ +#if !defined(BROTLI_BASE64_LUT_) +#define BROTLI_BASE64_LUT_ +BROTLI_INTERNAL extern const BROTLI_MODEL("small") uint8_t kIsBase64[256]; +#endif #define HistogramType FN(Histogram) -/* Creates entropy codes for all block types and stores them to the bit - stream. */ -static void FN(BuildAndStoreEntropyCodes)(MemoryManager* m, BlockEncoder* self, - const HistogramType* histograms, const size_t histograms_size, - const size_t alphabet_size, HuffmanTree* tree, - size_t* storage_ix, uint8_t* storage) { +static void FN(BuildAndStoreEntropyCodes)( + MemoryManager* m, BlockEncoder* self, const HistogramType* histograms, + const size_t histograms_size, const size_t alphabet_size, HuffmanTree* tree, + const uint8_t* is_base64_histogram, size_t* storage_ix, uint8_t* storage) { const size_t table_size = histograms_size * self->histogram_length_; self->depths_ = BROTLI_ALLOC(m, uint8_t, table_size); self->bits_ = BROTLI_ALLOC(m, uint16_t, table_size); @@ -24,9 +18,24 @@ size_t i; for (i = 0; i < histograms_size; ++i) { size_t ix = i * self->histogram_length_; - BuildAndStoreHuffmanTree(&histograms[i].data_[0], self->histogram_length_, - alphabet_size, tree, &self->depths_[ix], &self->bits_[ix], - storage_ix, storage); + if (self->histogram_length_ == 256 && is_base64_histogram && + is_base64_histogram[i]) { + size_t k; + memset(&self->depths_[ix], 0, 256); + for (k = 0; k < 256; ++k) { + if (kIsBase64[k]) { + self->depths_[ix + k] = 6; + } + } + BrotliConvertBitDepthsToSymbols(&self->depths_[ix], 256, + &self->bits_[ix]); + BrotliStoreHuffmanTree(&self->depths_[ix], 256, tree, storage_ix, + storage); + } else { + BuildAndStoreHuffmanTree( + &histograms[i].data_[0], self->histogram_length_, alphabet_size, + tree, &self->depths_[ix], &self->bits_[ix], storage_ix, storage); + } } } }
diff --git a/c/enc/brotli_bit_stream.c b/c/enc/brotli_bit_stream.c index 1e9e946..17b6799 100644 --- a/c/enc/brotli_bit_stream.c +++ b/c/enc/brotli_bit_stream.c
@@ -1017,16 +1017,30 @@ if (BROTLI_IS_OOM(m)) return; } - BuildAndStoreEntropyCodesLiteral(m, literal_enc, mb->literal_histograms, - mb->literal_histograms_size, BROTLI_NUM_LITERAL_SYMBOLS, tree, - storage_ix, storage); + { + uint8_t is_base64_histogram[256] = {0}; + if (mb->literal_split.num_types > 0) { + size_t b64_type_id = mb->literal_split.num_types - 1; + if (b64_type_id < 256 && (mb->literal_is_base64[b64_type_id >> 3] & (1u << (b64_type_id & 7)))) { + uint32_t b64_histo_id = mb->literal_context_map ? mb->literal_context_map[b64_type_id << 6] : (uint32_t)b64_type_id; + is_base64_histogram[b64_histo_id] = 1; + } + } + + BuildAndStoreEntropyCodesLiteral(m, literal_enc, mb->literal_histograms, + mb->literal_histograms_size, BROTLI_NUM_LITERAL_SYMBOLS, tree, + is_base64_histogram, + storage_ix, storage); + } if (BROTLI_IS_OOM(m)) return; BuildAndStoreEntropyCodesCommand(m, command_enc, mb->command_histograms, mb->command_histograms_size, BROTLI_NUM_COMMAND_SYMBOLS, tree, + NULL, storage_ix, storage); if (BROTLI_IS_OOM(m)) return; BuildAndStoreEntropyCodesDistance(m, distance_enc, mb->distance_histograms, mb->distance_histograms_size, num_distance_symbols, tree, + NULL, storage_ix, storage); if (BROTLI_IS_OOM(m)) return; BROTLI_FREE(m, tree);
diff --git a/c/enc/encode.c b/c/enc/encode.c index b2583e4..305c231 100644 --- a/c/enc/encode.c +++ b/c/enc/encode.c
@@ -105,6 +105,14 @@ state->params.stream_offset = value; return BROTLI_TRUE; + case BROTLI_PARAM_BASE64_MODE: + state->params.base64_mode = (int)(value & 1); + return BROTLI_TRUE; + + case BROTLI_PARAM_MAX_BASE64_REGIONS: + state->params.max_base64_regions = value; + return BROTLI_TRUE; + default: return BROTLI_FALSE; } } @@ -488,6 +496,8 @@ const uint64_t last_flush_pos, const size_t bytes, const BROTLI_BOOL is_last, + const Base64Region* base64_regions, + size_t num_base64_regions, ContextType literal_context_mode, const BrotliEncoderParams* params, const uint8_t prev_byte, @@ -499,7 +509,6 @@ int* dist_cache, size_t* storage_ix, uint8_t* storage) { - const uint32_t wrapped_last_flush_pos = WrapPosition(last_flush_pos); uint16_t last_bytes; uint8_t last_bytes_bits; ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode); @@ -518,7 +527,7 @@ CreateBackwardReferences is now unused. */ memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0])); BrotliStoreUncompressedMetaBlock(is_last, data, - wrapped_last_flush_pos, mask, bytes, + (size_t)last_flush_pos, mask, bytes, storage_ix, storage); return; } @@ -527,13 +536,13 @@ last_bytes = (uint16_t)((storage[1] << 8) | storage[0]); last_bytes_bits = (uint8_t)(*storage_ix); if (params->quality <= MAX_QUALITY_FOR_STATIC_ENTROPY_CODES) { - BrotliStoreMetaBlockFast(m, data, wrapped_last_flush_pos, + BrotliStoreMetaBlockFast(m, data, (size_t)last_flush_pos, bytes, mask, is_last, params, commands, num_commands, storage_ix, storage); if (BROTLI_IS_OOM(m)) return; } else if (params->quality < MIN_QUALITY_FOR_BLOCK_SPLIT) { - BrotliStoreMetaBlockTrivial(m, data, wrapped_last_flush_pos, + BrotliStoreMetaBlockTrivial(m, data, (size_t)last_flush_pos, bytes, mask, is_last, params, commands, num_commands, storage_ix, storage); @@ -550,17 +559,20 @@ BROTLI_ALLOC(m, uint32_t, 32 * (BROTLI_MAX_STATIC_CONTEXTS + 1)); if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(arena)) return; DecideOverLiteralContextModeling( - data, wrapped_last_flush_pos, bytes, mask, params->quality, + data, (size_t)last_flush_pos, bytes, mask, params->quality, params->size_hint, &num_literal_contexts, &literal_context_map, arena); BROTLI_FREE(m, arena); } - BrotliBuildMetaBlockGreedy(m, data, wrapped_last_flush_pos, mask, + BrotliBuildMetaBlockGreedy(m, data, (size_t)last_flush_pos, mask, + base64_regions, num_base64_regions, prev_byte, prev_byte2, literal_context_lut, num_literal_contexts, literal_context_map, commands, num_commands, &mb); if (BROTLI_IS_OOM(m)) return; } else { - BrotliBuildMetaBlock(m, data, wrapped_last_flush_pos, mask, &block_params, + BrotliBuildMetaBlock(m, data, (size_t)last_flush_pos, mask, + base64_regions, num_base64_regions, + &block_params, prev_byte, prev_byte2, commands, num_commands, literal_context_mode, @@ -573,7 +585,7 @@ for "Large Window Brotli" (32-bit). */ BrotliOptimizeHistograms(block_params.dist.alphabet_size_limit, &mb); } - BrotliStoreMetaBlock(m, data, wrapped_last_flush_pos, bytes, mask, + BrotliStoreMetaBlock(m, data, (size_t)last_flush_pos, bytes, mask, prev_byte, prev_byte2, is_last, &block_params, @@ -591,7 +603,7 @@ storage[1] = (uint8_t)(last_bytes >> 8); *storage_ix = last_bytes_bits; BrotliStoreUncompressedMetaBlock(is_last, data, - wrapped_last_flush_pos, mask, + (size_t)last_flush_pos, mask, bytes, storage_ix, storage); } } @@ -688,6 +700,8 @@ params->size_hint = 0; params->disable_literal_context_modeling = BROTLI_FALSE; BrotliInitSharedEncoderDictionary(¶ms->dictionary); + params->base64_mode = (int)BROTLI_DEFAULT_BASE64_MODE; + params->max_base64_regions = BROTLI_DEFAULT_MAX_BASE64_REGIONS; params->dist.distance_postfix_bits = 0; params->dist.num_direct_distance_codes = 0; params->dist.alphabet_size_max = @@ -757,6 +771,7 @@ /* Save the state of the distance cache in case we need to restore it for emitting an uncompressed block. */ memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_)); + s->hasher_.common.num_base64_regions = 0; } BrotliEncoderState* BrotliEncoderCreateInstance( @@ -1170,10 +1185,12 @@ storage[1] = (uint8_t)(s->last_bytes_ >> 8); WriteMetaBlockInternal( m, data, mask, s->last_flush_pos_, metablock_size, is_last, + s->hasher_.common.base64_regions, s->hasher_.common.num_base64_regions, literal_context_mode, &s->params, s->prev_byte_, s->prev_byte2_, s->num_literals_, s->num_commands_, s->commands_, s->saved_dist_cache_, s->dist_cache_, &storage_ix, storage); if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; + s->hasher_.common.num_base64_regions = 0; s->last_bytes_ = (uint16_t)(storage[storage_ix >> 3]); s->last_bytes_bits_ = storage_ix & 7u; s->last_flush_pos_ = s->input_pos_;
diff --git a/c/enc/hash.h b/c/enc/hash.h index eb9e455..e0b51c4 100644 --- a/c/enc/hash.h +++ b/c/enc/hash.h
@@ -29,6 +29,11 @@ #endif typedef struct { + size_t start_literal_pos; + size_t length; +} Base64Region; + +typedef struct { /** * Dynamically allocated areas; regular hasher uses one or two allocations; * "composite" hasher uses up to 4 allocations. @@ -52,6 +57,9 @@ * data initialization (using input ringbuffer). */ BROTLI_BOOL is_prepared_; + + Base64Region* base64_regions; + size_t num_base64_regions; } HasherCommon; #define score_t size_t @@ -408,6 +416,7 @@ hasher->common.extra[1] = NULL; hasher->common.extra[2] = NULL; hasher->common.extra[3] = NULL; + hasher->common.base64_regions = NULL; } static BROTLI_INLINE void DestroyHasher(MemoryManager* m, Hasher* hasher) { @@ -415,6 +424,9 @@ if (hasher->common.extra[1] != NULL) BROTLI_FREE(m, hasher->common.extra[1]); if (hasher->common.extra[2] != NULL) BROTLI_FREE(m, hasher->common.extra[2]); if (hasher->common.extra[3] != NULL) BROTLI_FREE(m, hasher->common.extra[3]); + if (hasher->common.base64_regions != NULL) { + BROTLI_FREE(m, hasher->common.base64_regions); + } } static BROTLI_INLINE void HasherReset(Hasher* hasher) { @@ -452,6 +464,13 @@ hasher->common.extra[i] = BROTLI_ALLOC(m, uint8_t, alloc_size[i]); if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(hasher->common.extra[i])) return; } + if (params->base64_mode && params->max_base64_regions > 0) { + hasher->common.base64_regions = BROTLI_ALLOC( + m, Base64Region, params->max_base64_regions); + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(hasher->common.base64_regions)) { + return; + } + } switch (hasher->common.params.type) { #define INITIALIZE_(N) \ case N: \
diff --git a/c/enc/metablock.c b/c/enc/metablock.c index dfe8120..3f64497 100644 --- a/c/enc/metablock.c +++ b/c/enc/metablock.c
@@ -9,23 +9,103 @@ #include "metablock.h" -#include "../common/constants.h" -#include "../common/context.h" -#include "../common/platform.h" #include "bit_cost.h" #include "block_splitter.h" #include "cluster.h" #include "command.h" #include "entropy_encode.h" +#include "hash.h" #include "histogram.h" #include "memory.h" #include "params.h" #include "prefix.h" +#include "../common/constants.h" +#include "../common/context.h" +#include "../common/platform.h" #if defined(__cplusplus) || defined(c_plusplus) extern "C" { #endif +static void ForceBase64LiteralSplits(MemoryManager* m, BlockSplit* split, + const Base64Region* base64_regions, + size_t num_base64_regions, + size_t last_flush_pos, + MetaBlockSplit* mb) { + size_t r; + /* Each base64 region can split an existing block into at most 3 blocks + (adding 2 new blocks). In the worst case, every base64 region splits + a different block, increasing the number of blocks by 2 * + num_base64_regions. We add 1 extra block as a safety margin. */ + size_t new_alloc_size = split->num_blocks + num_base64_regions * 2 + 1; + uint8_t* new_types = BROTLI_ALLOC(m, uint8_t, new_alloc_size); + uint32_t* new_lengths = BROTLI_ALLOC(m, uint32_t, new_alloc_size); + size_t new_num_blocks = 0; + size_t curr_offset = 0; + size_t block_idx = 0; + + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_types) || + BROTLI_IS_NULL(new_lengths)) { + return; + } + + memset(mb->literal_is_base64, 0, sizeof(mb->literal_is_base64)); + uint8_t base64_type_id = (uint8_t)split->num_types; + mb->literal_is_base64[base64_type_id >> 3] |= + (uint8_t)(1u << (base64_type_id & 7)); + + for (block_idx = 0; block_idx < split->num_blocks; ++block_idx) { + uint32_t block_len = split->lengths[block_idx]; + uint8_t block_type = split->types[block_idx]; + size_t block_start = curr_offset; + size_t block_end = curr_offset + block_len; + + BROTLI_BOOL intersected = BROTLI_FALSE; + for (r = 0; r < num_base64_regions; ++r) { + size_t b64_start = base64_regions[r].start_literal_pos - last_flush_pos; + size_t b64_end = b64_start + base64_regions[r].length; + + if (b64_start < block_end && b64_end > block_start) { + if (b64_start > block_start) { + new_types[new_num_blocks] = block_type; + new_lengths[new_num_blocks] = (uint32_t)(b64_start - block_start); + new_num_blocks++; + } + size_t intersect_start = BROTLI_MAX(size_t, block_start, b64_start); + size_t intersect_end = BROTLI_MIN(size_t, block_end, b64_end); + new_types[new_num_blocks] = base64_type_id; + new_lengths[new_num_blocks] = + (uint32_t)(intersect_end - intersect_start); + new_num_blocks++; + + if (b64_end < block_end) { + block_start = b64_end; + block_len = (uint32_t)(block_end - b64_end); + continue; + } else { + block_len = 0; + intersected = BROTLI_TRUE; + break; + } + } + } + + if (!intersected && block_len > 0) { + new_types[new_num_blocks] = block_type; + new_lengths[new_num_blocks] = block_len; + new_num_blocks++; + } + curr_offset = block_end; + } + + BROTLI_FREE(m, split->types); + BROTLI_FREE(m, split->lengths); + split->types = new_types; + split->lengths = new_lengths; + split->num_blocks = new_num_blocks; + split->num_types++; +} + void BrotliInitDistanceParams(BrotliDistanceParams* dist_params, uint32_t npostfix, uint32_t ndirect, BROTLI_BOOL large_window) { uint32_t alphabet_size_max; @@ -123,16 +203,13 @@ return BROTLI_TRUE; } -void BrotliBuildMetaBlock(MemoryManager* m, - const uint8_t* ringbuffer, - const size_t pos, - const size_t mask, - BrotliEncoderParams* params, - uint8_t prev_byte, - uint8_t prev_byte2, - Command* cmds, - size_t num_commands, - ContextType literal_context_mode, +void BrotliBuildMetaBlock(MemoryManager* m, const uint8_t* ringbuffer, + const size_t pos, const size_t mask, + const Base64Region* base64_regions, + size_t num_base64_regions, + BrotliEncoderParams* params, uint8_t prev_byte, + uint8_t prev_byte2, Command* cmds, + size_t num_commands, ContextType literal_context_mode, MetaBlockSplit* mb) { /* Histogram ids need to fit in one byte. */ static const size_t kMaxNumberOfHistograms = 256; @@ -146,6 +223,7 @@ uint32_t npostfix; uint32_t ndirect_msb = 0; BROTLI_BOOL check_orig = BROTLI_TRUE; + BROTLI_BOOL base64_applied = BROTLI_FALSE; double best_dist_cost = 1e99; BrotliDistanceParams orig_params = params->dist; BrotliDistanceParams new_params = params->dist; @@ -195,6 +273,14 @@ &mb->distance_split); if (BROTLI_IS_OOM(m)) return; + if (num_base64_regions > 0 && mb->literal_split.num_types < 256) { + ForceBase64LiteralSplits(m, &mb->literal_split, base64_regions, + num_base64_regions, pos, mb); + if (!BROTLI_IS_OOM(m)) { + base64_applied = BROTLI_TRUE; + } + } + if (!params->disable_literal_context_modeling) { literal_context_multiplier = 1 << BROTLI_LITERAL_CONTEXT_BITS; literal_context_modes = @@ -251,6 +337,26 @@ if (BROTLI_IS_OOM(m)) return; BROTLI_FREE(m, literal_histograms); + if (base64_applied) { + size_t base64_type_id = mb->literal_split.num_types - 1; + size_t b64_histo_id = mb->literal_histograms_size; + HistogramLiteral* new_histos = + BROTLI_ALLOC(m, HistogramLiteral, mb->literal_histograms_size + 1); + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_histos)) { + return; + } + memcpy(new_histos, mb->literal_histograms, + mb->literal_histograms_size * sizeof(HistogramLiteral)); + BROTLI_FREE(m, mb->literal_histograms); + mb->literal_histograms = new_histos; + HistogramClearLiteral(&mb->literal_histograms[b64_histo_id]); + for (i = 0; i < 64; ++i) { + mb->literal_context_map[(base64_type_id << 6) + i] = + (uint32_t)b64_histo_id; + } + mb->literal_histograms_size++; + } + if (params->disable_literal_context_modeling) { /* Distribute assignment to all contexts. */ for (i = mb->literal_split.num_types; i != 0;) { @@ -547,7 +653,8 @@ static BROTLI_INLINE void BrotliBuildMetaBlockGreedyInternal( MemoryManager* m, GreedyMetablockArena* arena, const uint8_t* ringbuffer, - size_t pos, size_t mask, uint8_t prev_byte, uint8_t prev_byte2, + size_t pos, size_t mask, const Base64Region* base64_regions, + size_t num_base64_regions, uint8_t prev_byte, uint8_t prev_byte2, ContextLut literal_context_lut, const size_t num_contexts, const uint32_t* static_context_map, const Command* commands, size_t n_commands, MetaBlockSplit* mb) { @@ -614,6 +721,30 @@ &arena->lit_blocks.ctx, m, /* is_final = */ BROTLI_TRUE); if (BROTLI_IS_OOM(m)) return; } + + if (num_base64_regions > 0 && mb->literal_split.num_types < 256) { + ForceBase64LiteralSplits(m, &mb->literal_split, base64_regions, + num_base64_regions, pos, mb); + if (BROTLI_IS_OOM(m)) return; + { + size_t num_b64_histos = num_contexts; + size_t b64_histo_id = mb->literal_histograms_size; + HistogramLiteral* new_histos = BROTLI_ALLOC( + m, HistogramLiteral, mb->literal_histograms_size + num_b64_histos); + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_histos)) { + return; + } + memcpy(new_histos, mb->literal_histograms, + mb->literal_histograms_size * sizeof(HistogramLiteral)); + BROTLI_FREE(m, mb->literal_histograms); + mb->literal_histograms = new_histos; + for (i = 0; i < num_b64_histos; ++i) { + HistogramClearLiteral(&mb->literal_histograms[b64_histo_id + i]); + } + mb->literal_histograms_size += num_b64_histos; + } + } + BlockSplitterFinishBlockCommand( &arena->cmd_blocks, /* is_final = */ BROTLI_TRUE); BlockSplitterFinishBlockDistance( @@ -624,26 +755,22 @@ } } -void BrotliBuildMetaBlockGreedy(MemoryManager* m, - const uint8_t* ringbuffer, - size_t pos, - size_t mask, - uint8_t prev_byte, - uint8_t prev_byte2, - ContextLut literal_context_lut, - size_t num_contexts, - const uint32_t* static_context_map, - const Command* commands, - size_t n_commands, - MetaBlockSplit* mb) { +void BrotliBuildMetaBlockGreedy( + MemoryManager* m, const uint8_t* ringbuffer, size_t pos, size_t mask, + const Base64Region* base64_regions, size_t num_base64_regions, + uint8_t prev_byte, uint8_t prev_byte2, ContextLut literal_context_lut, + size_t num_contexts, const uint32_t* static_context_map, + const Command* commands, size_t n_commands, MetaBlockSplit* mb) { GreedyMetablockArena* arena = BROTLI_ALLOC(m, GreedyMetablockArena, 1); if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(arena)) return; if (num_contexts == 1) { - BrotliBuildMetaBlockGreedyInternal(m, arena, ringbuffer, pos, mask, + BrotliBuildMetaBlockGreedyInternal( + m, arena, ringbuffer, pos, mask, base64_regions, num_base64_regions, prev_byte, prev_byte2, literal_context_lut, 1, NULL, commands, n_commands, mb); } else { - BrotliBuildMetaBlockGreedyInternal(m, arena, ringbuffer, pos, mask, + BrotliBuildMetaBlockGreedyInternal( + m, arena, ringbuffer, pos, mask, base64_regions, num_base64_regions, prev_byte, prev_byte2, literal_context_lut, num_contexts, static_context_map, commands, n_commands, mb); }
diff --git a/c/enc/metablock.h b/c/enc/metablock.h index e7d1052..5e2b456 100644 --- a/c/enc/metablock.h +++ b/c/enc/metablock.h
@@ -10,13 +10,14 @@ #ifndef BROTLI_ENC_METABLOCK_H_ #define BROTLI_ENC_METABLOCK_H_ -#include "../common/context.h" -#include "../common/platform.h" #include "block_splitter.h" #include "command.h" +#include "hash.h" #include "histogram.h" #include "memory.h" #include "params.h" +#include "../common/context.h" +#include "../common/platform.h" #if defined(__cplusplus) || defined(c_plusplus) extern "C" { @@ -38,6 +39,7 @@ size_t command_histograms_size; HistogramDistance* distance_histograms; size_t distance_histograms_size; + uint8_t literal_is_base64[32]; } MetaBlockSplit; static BROTLI_INLINE void InitMetaBlockSplit(MetaBlockSplit* mb) { @@ -54,6 +56,7 @@ mb->command_histograms_size = 0; mb->distance_histograms = 0; mb->distance_histograms_size = 0; + memset(mb->literal_is_base64, 0, sizeof(mb->literal_is_base64)); } static BROTLI_INLINE void DestroyMetaBlockSplit( @@ -72,23 +75,19 @@ The distance parameters are dynamically selected based on the commands which get recomputed under the new distance parameters. The new distance parameters are stored into *params. */ -BROTLI_INTERNAL void BrotliBuildMetaBlock(MemoryManager* m, - const uint8_t* ringbuffer, - const size_t pos, - const size_t mask, - BrotliEncoderParams* params, - uint8_t prev_byte, - uint8_t prev_byte2, - Command* cmds, - size_t num_commands, - ContextType literal_context_mode, - MetaBlockSplit* mb); +BROTLI_INTERNAL void BrotliBuildMetaBlock( + MemoryManager* m, const uint8_t* ringbuffer, const size_t pos, + const size_t mask, const Base64Region* base64_regions, + size_t num_base64_regions, BrotliEncoderParams* params, uint8_t prev_byte, + uint8_t prev_byte2, Command* cmds, size_t num_commands, + ContextType literal_context_mode, MetaBlockSplit* mb); /* Uses a fast greedy block splitter that tries to merge current block with the last or the second last block and uses a static context clustering which is the same for all block types. */ BROTLI_INTERNAL void BrotliBuildMetaBlockGreedy( MemoryManager* m, const uint8_t* ringbuffer, size_t pos, size_t mask, + const Base64Region* base64_regions, size_t num_base64_regions, uint8_t prev_byte, uint8_t prev_byte2, ContextLut literal_context_lut, size_t num_contexts, const uint32_t* static_context_map, const Command* commands, size_t n_commands, MetaBlockSplit* mb);
diff --git a/c/enc/params.h b/c/enc/params.h index fd1de00..01b1a41 100644 --- a/c/enc/params.h +++ b/c/enc/params.h
@@ -41,6 +41,8 @@ BrotliDistanceParams dist; /* TODO(eustas): rename to BrotliShared... */ SharedEncoderDictionary dictionary; + int base64_mode; + size_t max_base64_regions; } BrotliEncoderParams; #endif /* BROTLI_ENC_PARAMS_H_ */
diff --git a/c/include/brotli/encode.h b/c/include/brotli/encode.h index ac26ea8..6c568a0 100644 --- a/c/include/brotli/encode.h +++ b/c/include/brotli/encode.h
@@ -57,6 +57,19 @@ BROTLI_MODE_FONT = 2 } BrotliEncoderMode; +/** Options for ::BROTLI_PARAM_BASE64_MODE parameter. */ +typedef enum BrotliEncoderBase64Mode { + /** Base64 optimization is disabled. */ + BROTLI_BASE64_MODE_DISABLED = 0, + /** Automatic detection of Base64 zones and direct jump (skipping dictionary + and LZ77 lookups). */ + BROTLI_BASE64_MODE_DETECTION = 1 +} BrotliEncoderBase64Mode; + +#define BROTLI_DEFAULT_BASE64_MODE BROTLI_BASE64_MODE_DISABLED + +#define BROTLI_DEFAULT_MAX_BASE64_REGIONS 16 + /** Default value for ::BROTLI_PARAM_QUALITY parameter. */ #define BROTLI_DEFAULT_QUALITY 11 /** Default value for ::BROTLI_PARAM_LGWIN parameter. */ @@ -218,7 +231,18 @@ * maximal window size have the same effect. Values greater than 2**30 are not * allowed. */ - BROTLI_PARAM_STREAM_OFFSET = 9 + BROTLI_PARAM_STREAM_OFFSET = 9, + /** + * Base64 encoding mode. Controls how the encoder handles Base64 content. + * Currently supports 0 (disabled) and 1 (automatic detection and skip + * dictionary lookups). + */ + BROTLI_PARAM_BASE64_MODE = 10, + /** + * Maximum number of Base64 regions to detect. + * Default is 16. + */ + BROTLI_PARAM_MAX_BASE64_REGIONS = 11 } BrotliEncoderParameter; /**
diff --git a/docs/encode.h.3 b/docs/encode.h.3 index 49173aa..2151051 100644 --- a/docs/encode.h.3 +++ b/docs/encode.h.3
@@ -55,6 +55,10 @@ .in +1c .ti -1c +.RI "typedef enum \fBBrotliEncoderBase64Mode\fP \fBBrotliEncoderBase64Mode\fP" +.br +.RI "\fIOptions for \fBBROTLI_PARAM_BASE64_MODE\fP parameter\&. \fP" +.ti -1c .RI "typedef enum \fBBrotliEncoderMode\fP \fBBrotliEncoderMode\fP" .br .RI "\fIOptions for \fBBROTLI_PARAM_MODE\fP parameter\&. \fP" @@ -176,6 +180,10 @@ Minimal value for \fBBROTLI_PARAM_LGWIN\fP parameter\&. .SH "Typedef Documentation" .PP +.SS "typedef enum \fBBrotliEncoderBase64Mode\fP \fBBrotliEncoderBase64Mode\fP" + +.PP +Options for \fBBROTLI_PARAM_BASE64_MODE\fP parameter\&. .SS "typedef enum \fBBrotliEncoderMode\fP \fBBrotliEncoderMode\fP" .PP @@ -194,6 +202,19 @@ Opaque structure that holds encoder state\&. Allocated and initialized with \fBBrotliEncoderCreateInstance\fP\&. Cleaned up and deallocated with \fBBrotliEncoderDestroyInstance\fP\&. .SH "Enumeration Type Documentation" .PP +.SS "enum \fBBrotliEncoderBase64Mode\fP" + +.PP +Options for \fBBROTLI_PARAM_BASE64_MODE\fP parameter\&. +.PP +\fBEnumerator\fP +.in +1c +.TP +\fB\fIBROTLI_BASE64_MODE_DISABLED \fP\fP +Base64 optimization is disabled\&. +.TP +\fB\fIBROTLI_BASE64_MODE_DETECTION \fP\fP +Automatic detection of Base64 zones and direct jump (skipping dictionary and LZ77 lookups)\&. .SS "enum \fBBrotliEncoderMode\fP" .PP @@ -324,6 +345,12 @@ If offset is not 0, then stream header is omitted\&. In any case output start is byte aligned, so for proper streams stitching 'predecessor' stream must be flushed\&. .PP Range is not artificially limited, but all the values greater or equal to maximal window size have the same effect\&. Values greater than 2**30 are not allowed\&. +.TP +\fB\fIBROTLI_PARAM_BASE64_MODE \fP\fP +Base64 encoding mode\&. Controls how the encoder handles Base64 content\&. Currently supports 0 (disabled) and 1 (automatic detection and skip dictionary lookups)\&. +.TP +\fB\fIBROTLI_PARAM_MAX_BASE64_REGIONS \fP\fP +Maximum number of Base64 regions to detect\&. Default is 16\&. .SH "Function Documentation" .PP .SS "\fBBROTLI_BOOL\fP BrotliEncoderAttachPreparedDictionary (\fBBrotliEncoderState\fP * state, const BrotliEncoderPreparedDictionary * dictionary)"