Add dual-tier Base64 block deduplication to the Brotli encoder, improving compression ratio and throughput on payloads containing repeated inline Base64 assets. PiperOrigin-RevId: 964713174
diff --git a/c/enc/backward_references.c b/c/enc/backward_references.c index b5c818d..187b6f6 100644 --- a/c/enc/backward_references.c +++ b/c/enc/backward_references.c
@@ -38,6 +38,11 @@ static const size_t kBase64TriggerLen = 8; +/* Minimum payload length (in bytes) required for Base64 block deduplication. + Blocks shorter than 32 bytes do not yield sufficient entropy reduction to + amortize the backward reference command encoding overhead and are skipped. */ +static const size_t kMinBase64DeduplicationLen = 32; + static BROTLI_INLINE BROTLI_BOOL IsBase64Char(uint8_t c) { return TO_BROTLI_BOOL(kIsBase64[c]); } @@ -108,6 +113,27 @@ return distance + BROTLI_NUM_DISTANCE_SHORT_CODES - 1; } +static BROTLI_INLINE BROTLI_BOOL RingBufferCompare( + const uint8_t* ringbuffer, size_t mask, + size_t pos1, size_t pos2, size_t length) { + size_t rb_size = mask + 1; + while (length > 0) { + size_t idx1 = pos1 & mask; + size_t idx2 = pos2 & mask; + size_t contig1 = rb_size - idx1; + size_t contig2 = rb_size - idx2; + size_t chunk = BROTLI_MIN(size_t, length, contig1); + chunk = BROTLI_MIN(size_t, chunk, contig2); + if (memcmp(&ringbuffer[idx1], &ringbuffer[idx2], chunk) != 0) { + return BROTLI_FALSE; + } + pos1 += chunk; + pos2 += chunk; + length -= chunk; + } + return BROTLI_TRUE; +} + #define EXPAND_CAT(a, b) CAT(a, b) #define CAT(a, b) a ## b #define FN(X) EXPAND_CAT(X, HASHER())
diff --git a/c/enc/backward_references_inc.h b/c/enc/backward_references_inc.h index 02e1f4f..81bc5ca 100644 --- a/c/enc/backward_references_inc.h +++ b/c/enc/backward_references_inc.h
@@ -7,6 +7,24 @@ /* template parameters: EXPORT_FN, FN */ +#ifndef BROTLI_READ_RING_BUFFER_64_DEFINED +#define BROTLI_READ_RING_BUFFER_64_DEFINED +static BROTLI_INLINE uint64_t ReadRingBuffer64(const uint8_t* ringbuffer, size_t mask, size_t pos) { + size_t idx = pos & mask; + if (idx + 8 <= mask + 1) { + return BrotliUnalignedRead64(&ringbuffer[idx]); + } else { + uint64_t val; + uint8_t* val_ptr = (uint8_t*)&val; + size_t i; + for (i = 0; i < 8; ++i) { + val_ptr[i] = ringbuffer[(pos + i) & mask]; + } + return val; + } +} +#endif + static BROTLI_NOINLINE void EXPORT_FN(CreateBackwardReferences)( size_t num_bytes, size_t position, const uint8_t* ringbuffer, size_t ringbuffer_mask, @@ -37,7 +55,8 @@ size_t next_base64_pos = pos_end; if (params->base64_mode && - hasher->common.num_base64_regions < params->max_base64_regions) { + (hasher->common.num_base64_regions < params->max_base64_regions || + hasher->common.num_sub_b64_regions < params->max_base64_regions)) { next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask, position, pos_end); } @@ -72,22 +91,169 @@ 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); + if (length >= kMinBase64DeduplicationLen) { + if (params->base64_mode >= 2) { + BROTLI_BOOL match_found = BROTLI_FALSE; + size_t best_hist_pos = 0; + size_t mlen = scan_pos - position; + BROTLI_BOOL is_macro = (length >= params->min_base64_region_len); + Base64Region* search_regions = is_macro ? hasher->common.base64_regions : hasher->common.sub_b64_regions; + size_t search_num = is_macro ? hasher->common.num_base64_regions : hasher->common.num_sub_b64_regions; + size_t r; + for (r = search_num; r > 0; --r) { + size_t idx = r - 1; + size_t hist_start_literal_pos = + search_regions[idx].start_literal_pos; + size_t hist_length = search_regions[idx].length; + /* Avoid size_t underflow if start_literal_pos is small */ + if (hist_start_literal_pos >= kBase64TriggerLen) { + size_t hist_pos = hist_start_literal_pos - kBase64TriggerLen; + size_t dist = position - hist_pos; + /* Verify distance complies with maximum backward limits, ringbuffer capacity, + and encoder configuration to prevent referencing overwritten history. */ + if (dist >= 1 && + dist <= max_backward_limit && + dist <= ringbuffer_mask && + dist <= params->dist.max_distance) { + /* Count historical trailing '=' padding characters to compute exact payload size */ + size_t hist_num_equals = 0; + while (hist_start_literal_pos + hist_length + hist_num_equals < position && + ringbuffer[(hist_start_literal_pos + hist_length + hist_num_equals) & ringbuffer_mask] == '=') { + hist_num_equals++; + } + /* O(1) length check before comparing payload bytes. This ensures that + non-duplicate blocks (common in production) are rejected immediately in O(1) + without triggering O(N * length) string comparisons. */ + if (hist_length + hist_num_equals == mlen - kBase64TriggerLen) { + size_t compare_len = hist_length + hist_num_equals; + /* Dual-Ended (Prefix + Suffix) 64-Bit Payload Quick Rejection */ + uint64_t hist_prefix = ReadRingBuffer64(ringbuffer, ringbuffer_mask, hist_start_literal_pos); + uint64_t curr_prefix = ReadRingBuffer64(ringbuffer, ringbuffer_mask, position + kBase64TriggerLen); + if (hist_prefix == curr_prefix) { + uint64_t hist_suffix = ReadRingBuffer64(ringbuffer, ringbuffer_mask, hist_start_literal_pos + compare_len - 8); + uint64_t curr_suffix = ReadRingBuffer64(ringbuffer, ringbuffer_mask, position + kBase64TriggerLen + compare_len - 8); + if (hist_suffix == curr_suffix) { + if (RingBufferCompare(ringbuffer, ringbuffer_mask, + hist_start_literal_pos, + position + kBase64TriggerLen, + compare_len)) { + match_found = BROTLI_TRUE; + best_hist_pos = hist_pos; + /* Nearest-Neighbor Anchor Tracking & MRU Cache Promotion */ + search_regions[idx].start_literal_pos = start_pos; + if (idx < search_num - 1) { + Base64Region matched_reg = search_regions[idx]; + size_t k; + for (k = idx; k < search_num - 1; ++k) { + search_regions[k] = search_regions[k + 1]; + } + search_regions[search_num - 1] = matched_reg; + } + break; + } + } + } + } + } + } + } + if (match_found && mlen >= kMinBase64DeduplicationLen) { + size_t dictionary_start = BROTLI_MIN(size_t, + position + position_offset, max_backward_limit); + size_t dist = position - best_hist_pos; + size_t distance_code = ComputeDistanceCode( + dist, dictionary_start + gap, dist_cache); + if ((dist <= (dictionary_start + gap)) && distance_code > 0) { + dist_cache[3] = dist_cache[2]; + dist_cache[2] = dist_cache[1]; + dist_cache[1] = dist_cache[0]; + dist_cache[0] = (int)dist; + FN(PrepareDistanceCache)(privat, dist_cache); + } + InitCommand(commands++, ¶ms->dist, insert_length, + mlen, 0, distance_code); + *num_literals += insert_length; + insert_length = 0; + + /* Bounded Entry/Exit Anchor Hasher Seeding */ + { + size_t entry_start = position + 2; + size_t entry_end = BROTLI_MIN(size_t, position + 6, store_end); + if (entry_start < entry_end) { + FN(StoreRange)(privat, ringbuffer, ringbuffer_mask, entry_start, entry_end); + } + size_t exit_start = (position + mlen >= 4) ? (position + mlen - 4) : 0; + if (exit_start < entry_end) { + exit_start = entry_end; + } + size_t exit_end = BROTLI_MIN(size_t, position + mlen, store_end); + if (exit_start < exit_end) { + FN(StoreRange)(privat, ringbuffer, ringbuffer_mask, exit_start, exit_end); + } + } + + position += mlen; + apply_random_heuristics = position + random_heuristics_window_size; + if (hasher->common.num_base64_regions < params->max_base64_regions || + hasher->common.num_sub_b64_regions < params->max_base64_regions) { + next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask, + position, pos_end); + } else { + next_base64_pos = pos_end; + } + continue; + } + + if (is_macro) { + if (hasher->common.num_base64_regions < params->max_base64_regions) { + 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++; + } + } else { + if (hasher->common.num_sub_b64_regions < params->max_base64_regions) { + hasher->common.sub_b64_regions[hasher->common.num_sub_b64_regions] + .start_literal_pos = start_pos; + hasher->common.sub_b64_regions[hasher->common.num_sub_b64_regions] + .length = length; + hasher->common.num_sub_b64_regions++; + } + } + } else { + /* HEAD Base64 Mode: pure detection & histogram splitting, no deduplication */ + if (hasher->common.num_base64_regions < params->max_base64_regions) { + 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; + apply_random_heuristics = position + random_heuristics_window_size; + FN(StoreRange)(privat, ringbuffer, ringbuffer_mask, position, + BROTLI_MIN(size_t, position + 4, store_end)); + if (hasher->common.num_base64_regions < params->max_base64_regions || + hasher->common.num_sub_b64_regions < params->max_base64_regions) { + next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask, + position, pos_end); + } else { + next_base64_pos = pos_end; + } + continue; } else { - next_base64_pos = pos_end; + if (hasher->common.num_base64_regions < params->max_base64_regions || + hasher->common.num_sub_b64_regions < params->max_base64_regions) { + next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask, + scan_pos, pos_end); + } else { + next_base64_pos = pos_end; + } + continue; } - continue; } size_t max_length = pos_end - position; size_t max_distance = BROTLI_MIN(size_t, position, max_backward_limit);
diff --git a/c/enc/encode.c b/c/enc/encode.c index 0d424c3..feab312 100644 --- a/c/enc/encode.c +++ b/c/enc/encode.c
@@ -106,13 +106,18 @@ return BROTLI_TRUE; case BROTLI_PARAM_BASE64_MODE: - state->params.base64_mode = (int)(value & 1); + if (value > 2) return BROTLI_FALSE; + state->params.base64_mode = (int)value; return BROTLI_TRUE; case BROTLI_PARAM_MAX_BASE64_REGIONS: state->params.max_base64_regions = value; return BROTLI_TRUE; + case BROTLI_PARAM_MIN_BASE64_REGION_LEN: + state->params.min_base64_region_len = value; + return BROTLI_TRUE; + case BROTLI_PARAM_SIMD_HASHER: if (value > 2) return BROTLI_FALSE; state->params.simd_hasher = (BrotliEncoderSimdHasher)value; @@ -707,6 +712,7 @@ BrotliInitSharedEncoderDictionary(¶ms->dictionary); params->base64_mode = (int)BROTLI_DEFAULT_BASE64_MODE; params->max_base64_regions = BROTLI_DEFAULT_MAX_BASE64_REGIONS; + params->min_base64_region_len = BROTLI_DEFAULT_MIN_BASE64_REGION_LEN; params->simd_hasher = BROTLI_DEFAULT_SIMD_HASHER; params->dist.distance_postfix_bits = 0; params->dist.num_direct_distance_codes = 0; @@ -778,6 +784,7 @@ emitting an uncompressed block. */ memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_)); s->hasher_.common.num_base64_regions = 0; + s->hasher_.common.num_sub_b64_regions = 0; } BrotliEncoderState* BrotliEncoderCreateInstance( @@ -1189,14 +1196,42 @@ if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; storage[0] = (uint8_t)s->last_bytes_; 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); + { + Base64Region* merged_regions = NULL; + size_t num_merged_regions = 0; + size_t total_alloc = s->hasher_.common.num_base64_regions + s->hasher_.common.num_sub_b64_regions; + if (total_alloc > 0) { + merged_regions = BROTLI_ALLOC(m, Base64Region, total_alloc); + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(merged_regions)) return BROTLI_FALSE; + /* Merge-sort the two sorted lists of Base64 regions */ + size_t i = 0, j = 0; + while (i < s->hasher_.common.num_base64_regions || j < s->hasher_.common.num_sub_b64_regions) { + if (i < s->hasher_.common.num_base64_regions && j < s->hasher_.common.num_sub_b64_regions) { + if (s->hasher_.common.base64_regions[i].start_literal_pos < s->hasher_.common.sub_b64_regions[j].start_literal_pos) { + merged_regions[num_merged_regions++] = s->hasher_.common.base64_regions[i++]; + } else { + merged_regions[num_merged_regions++] = s->hasher_.common.sub_b64_regions[j++]; + } + } else if (i < s->hasher_.common.num_base64_regions) { + merged_regions[num_merged_regions++] = s->hasher_.common.base64_regions[i++]; + } else { + merged_regions[num_merged_regions++] = s->hasher_.common.sub_b64_regions[j++]; + } + } + } + WriteMetaBlockInternal( + m, data, mask, s->last_flush_pos_, metablock_size, is_last, + merged_regions, num_merged_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 (merged_regions != NULL) { + BROTLI_FREE(m, merged_regions); + } + } if (BROTLI_IS_OOM(m)) return BROTLI_FALSE; s->hasher_.common.num_base64_regions = 0; + s->hasher_.common.num_sub_b64_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 e0b51c4..6f8eb62 100644 --- a/c/enc/hash.h +++ b/c/enc/hash.h
@@ -60,6 +60,8 @@ Base64Region* base64_regions; size_t num_base64_regions; + Base64Region* sub_b64_regions; + size_t num_sub_b64_regions; } HasherCommon; #define score_t size_t @@ -122,6 +124,7 @@ backward_reference_offset MUST be positive. */ static BROTLI_INLINE score_t BackwardReferenceScore( size_t copy_length, size_t backward_reference_offset) { + if (backward_reference_offset == 0) return 0; return BROTLI_SCORE_BASE + BROTLI_LITERAL_BYTE_SCORE * (score_t)copy_length - BROTLI_DISTANCE_BIT_PENALTY * Log2FloorNonZero(backward_reference_offset); } @@ -417,6 +420,7 @@ hasher->common.extra[2] = NULL; hasher->common.extra[3] = NULL; hasher->common.base64_regions = NULL; + hasher->common.sub_b64_regions = NULL; } static BROTLI_INLINE void DestroyHasher(MemoryManager* m, Hasher* hasher) { @@ -427,6 +431,9 @@ if (hasher->common.base64_regions != NULL) { BROTLI_FREE(m, hasher->common.base64_regions); } + if (hasher->common.sub_b64_regions != NULL) { + BROTLI_FREE(m, hasher->common.sub_b64_regions); + } } static BROTLI_INLINE void HasherReset(Hasher* hasher) { @@ -470,6 +477,11 @@ if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(hasher->common.base64_regions)) { return; } + hasher->common.sub_b64_regions = BROTLI_ALLOC( + m, Base64Region, params->max_base64_regions); + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(hasher->common.sub_b64_regions)) { + return; + } } switch (hasher->common.params.type) { #define INITIALIZE_(N) \
diff --git a/c/enc/hash_longest_match64_inc.h b/c/enc/hash_longest_match64_inc.h index 3131451..4d6c3f0 100644 --- a/c/enc/hash_longest_match64_inc.h +++ b/c/enc/hash_longest_match64_inc.h
@@ -235,6 +235,9 @@ i = num[key]; for (; i > down;) { size_t prev_ix = bucket[--i & self->block_mask_]; + if (prev_ix >= cur_ix) { + continue; + } uint32_t current4; const size_t backward = cur_ix - prev_ix; if (BROTLI_PREDICT_FALSE(backward > max_backward)) {
diff --git a/c/enc/hash_longest_match64_simd_inc.h b/c/enc/hash_longest_match64_simd_inc.h index 17dc67d..726680e 100644 --- a/c/enc/hash_longest_match64_simd_inc.h +++ b/c/enc/hash_longest_match64_simd_inc.h
@@ -259,6 +259,9 @@ const size_t rb_index = (head + (size_t)BROTLI_TZCNT64(matches)) & self->block_mask_; size_t prev_ix = bucket[rb_index]; + if (prev_ix >= cur_ix) { + continue; + } uint32_t current4; const size_t backward = cur_ix - prev_ix; if (BROTLI_PREDICT_FALSE(backward > max_backward)) {
diff --git a/c/enc/hash_longest_match_inc.h b/c/enc/hash_longest_match_inc.h index 674dced..ebd83a6 100644 --- a/c/enc/hash_longest_match_inc.h +++ b/c/enc/hash_longest_match_inc.h
@@ -231,6 +231,9 @@ (num[key] > self->block_size_) ? (num[key] - self->block_size_) : 0u; for (i = num[key]; i > down;) { size_t prev_ix = bucket[--i & self->block_mask_]; + if (prev_ix >= cur_ix) { + continue; + } const size_t backward = cur_ix - prev_ix; if (BROTLI_PREDICT_FALSE(backward > max_backward)) { break;
diff --git a/c/enc/hash_longest_match_simd_inc.h b/c/enc/hash_longest_match_simd_inc.h index 075f6da..c7f6b31 100644 --- a/c/enc/hash_longest_match_simd_inc.h +++ b/c/enc/hash_longest_match_simd_inc.h
@@ -232,6 +232,9 @@ const size_t rb_index = (head + (size_t)BROTLI_TZCNT64(matches)) & self->block_mask_; size_t prev_ix = bucket[rb_index]; + if (prev_ix >= cur_ix) { + continue; + } const size_t backward = cur_ix - prev_ix; if (BROTLI_PREDICT_FALSE(backward > max_backward)) { break;
diff --git a/c/enc/params.h b/c/enc/params.h index b34eb4b..6163e04 100644 --- a/c/enc/params.h +++ b/c/enc/params.h
@@ -12,6 +12,8 @@ #include <brotli/encode.h> #include "encoder_dict.h" +#define BROTLI_DEFAULT_MIN_BASE64_REGION_LEN 2048 + typedef struct BrotliHasherParams { int type; int bucket_bits; @@ -43,6 +45,7 @@ SharedEncoderDictionary dictionary; int base64_mode; size_t max_base64_regions; + size_t min_base64_region_len; BrotliEncoderSimdHasher simd_hasher; } BrotliEncoderParams;
diff --git a/c/include/brotli/encode.h b/c/include/brotli/encode.h index 076025e..c31bbed 100644 --- a/c/include/brotli/encode.h +++ b/c/include/brotli/encode.h
@@ -63,7 +63,9 @@ BROTLI_BASE64_MODE_DISABLED = 0, /** Automatic detection of Base64 zones and direct jump (skipping dictionary and LZ77 lookups). */ - BROTLI_BASE64_MODE_DETECTION = 1 + BROTLI_BASE64_MODE_DETECTION = 1, + /** Full dual-tier Base64 deduplication, 64-bit guarding & bounded seeding engine. */ + BROTLI_BASE64_MODE_DEDUPLICATION = 2 } BrotliEncoderBase64Mode; #define BROTLI_DEFAULT_BASE64_MODE BROTLI_BASE64_MODE_DISABLED @@ -256,12 +258,17 @@ */ BROTLI_PARAM_MAX_BASE64_REGIONS = 11, /** + * Minimum Base64 region length for macro block deduplication. + * Default is 2048. + */ + BROTLI_PARAM_MIN_BASE64_REGION_LEN = 12, + /** * SIMD hasher usage mode. * * Controls whether the encoder uses SIMD hashers. * See ::BrotliEncoderSimdHasher for options. */ - BROTLI_PARAM_SIMD_HASHER = 12 + BROTLI_PARAM_SIMD_HASHER = 13 } BrotliEncoderParameter; /**
diff --git a/docs/encode.h.3 b/docs/encode.h.3 index c24fb97..d817e13 100644 --- a/docs/encode.h.3 +++ b/docs/encode.h.3
@@ -223,6 +223,9 @@ .TP \fB\fIBROTLI_BASE64_MODE_DETECTION \fP\fP Automatic detection of Base64 zones and direct jump (skipping dictionary and LZ77 lookups)\&. +.TP +\fB\fIBROTLI_BASE64_MODE_DEDUPLICATION \fP\fP +Full dual-tier Base64 deduplication, 64-bit guarding & bounded seeding engine\&. .SS "enum \fBBrotliEncoderMode\fP" .PP @@ -360,6 +363,9 @@ \fB\fIBROTLI_PARAM_MAX_BASE64_REGIONS \fP\fP Maximum number of Base64 regions to detect\&. Default is 16\&. .TP +\fB\fIBROTLI_PARAM_MIN_BASE64_REGION_LEN \fP\fP +Minimum Base64 region length for macro block deduplication\&. Default is 2048\&. +.TP \fB\fIBROTLI_PARAM_SIMD_HASHER \fP\fP SIMD hasher usage mode\&. Controls whether the encoder uses SIMD hashers\&. See \fBBrotliEncoderSimdHasher\fP for options\&. .SS "enum \fBBrotliEncoderSimdHasher\fP"