Add BROTLI_PARAM_MIN_BASE64_REGION_LEN to gate Base64 literal mode by region size. PiperOrigin-RevId: 981859989
diff --git a/c/enc/backward_references.c b/c/enc/backward_references.c index 018591e..d6dc0b5 100644 --- a/c/enc/backward_references.c +++ b/c/enc/backward_references.c
@@ -52,6 +52,8 @@ return BROTLI_TRUE; } +static const uint64_t kBase64Trigger64 = 0x2c3436657361623bULL; + static size_t FindNextBase64Trigger(const uint8_t* ringbuffer, size_t mask, size_t pos, size_t end) { while (pos + kBase64TriggerLen <= end) { @@ -65,7 +67,11 @@ (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 (offset + kBase64TriggerLen <= scan_len) { + if (BROTLI_UNALIGNED_LOAD64LE(p) == kBase64Trigger64) { + return pos + offset; + } + } else if (pos + offset + kBase64TriggerLen <= end) { if (MatchTrigger(ringbuffer, mask, pos + offset)) { return pos + offset; } @@ -80,6 +86,29 @@ return end; } +static BROTLI_INLINE BROTLI_BOOL CompareRingbuffer( + const uint8_t* ringbuffer, size_t mask, + size_t pos1, size_t pos2, size_t len) { + size_t idx1 = pos1 & mask; + size_t idx2 = pos2 & mask; + if (idx1 + len <= mask + 1 && idx2 + len <= mask + 1) { + return TO_BROTLI_BOOL( + memcmp(&ringbuffer[idx1], &ringbuffer[idx2], len) == 0); + } + while (len > 0) { + size_t chunk1 = mask + 1 - (pos1 & mask); + size_t chunk2 = mask + 1 - (pos2 & mask); + size_t chunk = BROTLI_MIN(size_t, len, BROTLI_MIN(size_t, chunk1, chunk2)); + if (memcmp(&ringbuffer[pos1 & mask], &ringbuffer[pos2 & mask], chunk) != 0) { + return BROTLI_FALSE; + } + pos1 += chunk; + pos2 += chunk; + len -= chunk; + } + return BROTLI_TRUE; +} + #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 02e1f4f..7a91793 100644 --- a/c/enc/backward_references_inc.h +++ b/c/enc/backward_references_inc.h
@@ -43,6 +43,16 @@ } while (position + FN(HashTypeLength)() < pos_end) { if (position >= next_base64_pos) { + if (position > next_base64_pos) { + /* A previous backward match jumped over the trigger position. + Find the next trigger from the current position safely checking + pos_end. */ + next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask, + position, pos_end); + if (position < next_base64_pos) { + goto skip_base64_trigger; + } + } /* Find where it ends */ size_t scan_pos = position + kBase64TriggerLen; size_t first_equal_pos = 0; @@ -64,7 +74,6 @@ } } /* 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 */ @@ -72,23 +81,85 @@ ringbuffer[(start_pos + length - 1) & ringbuffer_mask] == '=') { length--; } - if (length > 0) { + BROTLI_BOOL is_dupe = BROTLI_FALSE; + size_t copy_len = scan_pos - position; + size_t dupe_dist = 0; + size_t matched_region_idx = 0; + if (length > 0 && hasher->common.num_base64_regions > 0) { + size_t r = hasher->common.num_base64_regions; + while (r > 0) { + --r; + size_t prev_start = + hasher->common.base64_regions[r].start_literal_pos; + size_t prev_length = hasher->common.base64_regions[r].length; + if (prev_length != length) { + continue; + } + size_t prev_pos = prev_start - kBase64TriggerLen; + size_t distance = position - prev_pos; + if (distance == 0 || distance > max_backward_limit) { + continue; + } + if (CompareRingbuffer(ringbuffer, ringbuffer_mask, prev_pos, position, + copy_len)) { + is_dupe = BROTLI_TRUE; + dupe_dist = distance; + matched_region_idx = r; + break; + } + } + } + if (is_dupe) { + size_t dictionary_start = + BROTLI_MIN(size_t, position + position_offset, max_backward_limit); + size_t distance_code = + ComputeDistanceCode(dupe_dist, dictionary_start + gap, dist_cache); + if ((dupe_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)dupe_dist; + FN(PrepareDistanceCache)(privat, dist_cache); + } + InitCommand(commands++, ¶ms->dist, insert_length, copy_len, 0, + distance_code); + *num_literals += insert_length; + insert_length = 0; + position = scan_pos; + hasher->common.base64_regions[matched_region_idx].start_literal_pos = + start_pos; + apply_random_heuristics = + position + 2 * copy_len + random_heuristics_window_size; + 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; + } + if (length >= params->min_base64_region_len && 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); + 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; } else { - next_base64_pos = pos_end; + next_base64_pos = FindNextBase64Trigger(ringbuffer, ringbuffer_mask, + position + 1, pos_end); + goto skip_base64_trigger; } - continue; } + skip_base64_trigger:; 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 85e2a0d..5a90658 100644 --- a/c/enc/block_encoder_inc.h +++ b/c/enc/block_encoder_inc.h
@@ -21,16 +21,29 @@ if (self->histogram_length_ == 256 && is_base64_histogram && i < 256 && is_base64_histogram[i]) { size_t k; - memset(&self->depths_[ix], 0, 256); + BROTLI_BOOL all_base64 = BROTLI_TRUE; for (k = 0; k < 256; ++k) { - if (kIsBase64[k]) { - self->depths_[ix + k] = 6; + if (histograms[i].data_[k] > 0 && !kIsBase64[k]) { + all_base64 = BROTLI_FALSE; + break; } } - BrotliConvertBitDepthsToSymbols(&self->depths_[ix], 256, - &self->bits_[ix]); - BrotliStoreHuffmanTree(&self->depths_[ix], 256, tree, storage_ix, - storage); + if (all_base64) { + 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); + } } else { BuildAndStoreHuffmanTree( &histograms[i].data_[0], self->histogram_length_, alphabet_size,
diff --git a/c/enc/encode.c b/c/enc/encode.c index bf13e08..44b447a 100644 --- a/c/enc/encode.c +++ b/c/enc/encode.c
@@ -113,6 +113,10 @@ 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; @@ -713,6 +717,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->hasher_opt = BROTLI_FALSE; params->dist.distance_postfix_bits = 0;
diff --git a/c/enc/params.h b/c/enc/params.h index 45d873c..b1659dc 100644 --- a/c/enc/params.h +++ b/c/enc/params.h
@@ -43,6 +43,7 @@ SharedEncoderDictionary dictionary; int base64_mode; size_t max_base64_regions; + size_t min_base64_region_len; BrotliEncoderSimdHasher simd_hasher; BROTLI_BOOL hasher_opt; } BrotliEncoderParams;
diff --git a/c/include/brotli/encode.h b/c/include/brotli/encode.h index a18a245..22c57ab 100644 --- a/c/include/brotli/encode.h +++ b/c/include/brotli/encode.h
@@ -70,6 +70,8 @@ #define BROTLI_DEFAULT_MAX_BASE64_REGIONS 16 +#define BROTLI_DEFAULT_MIN_BASE64_REGION_LEN 2048 + /** Options for ::BROTLI_PARAM_SIMD_HASHER parameter. */ typedef enum BrotliEncoderSimdHasher { /** Use SIMD hasher when recommended for the quality level. */ @@ -267,7 +269,14 @@ * * When enabled (1), engages H59 instead of H58. */ - BROTLI_PARAM_HASHER_OPT = 13 + BROTLI_PARAM_HASHER_OPT = 13, + /** + * Minimum length of a Base64 region to trigger detection and literal block + * splitting. Below this threshold, Base64 regions are encoded using standard + * LZ77 and Huffman coding. + * Default is 2048. + */ + BROTLI_PARAM_MIN_BASE64_REGION_LEN = 14 } BrotliEncoderParameter; /**
diff --git a/docs/encode.h.3 b/docs/encode.h.3 index dc6003c..8374e88 100644 --- a/docs/encode.h.3 +++ b/docs/encode.h.3
@@ -365,6 +365,9 @@ .TP \fB\fIBROTLI_PARAM_HASHER_OPT \fP\fP Engage optimized hasher\&. When enabled (1), engages H59 instead of H58\&. +.TP +\fB\fIBROTLI_PARAM_MIN_BASE64_REGION_LEN \fP\fP +Minimum length of a Base64 region to trigger detection and literal block splitting\&. Below this threshold, Base64 regions are encoded using standard LZ77 and Huffman coding\&. Default is 2048\&. .SS "enum \fBBrotliEncoderSimdHasher\fP" .PP