Fix edge cases and stability issues in Brotli Base64 entropy coding optimization. PiperOrigin-RevId: 952905771
diff --git a/c/enc/block_encoder_inc.h b/c/enc/block_encoder_inc.h index 9ae6e97..85e2a0d 100644 --- a/c/enc/block_encoder_inc.h +++ b/c/enc/block_encoder_inc.h
@@ -18,7 +18,7 @@ size_t i; for (i = 0; i < histograms_size; ++i) { size_t ix = i * self->histogram_length_; - if (self->histogram_length_ == 256 && is_base64_histogram && + if (self->histogram_length_ == 256 && is_base64_histogram && i < 256 && is_base64_histogram[i]) { size_t k; memset(&self->depths_[ix], 0, 256);
diff --git a/c/enc/brotli_bit_stream.c b/c/enc/brotli_bit_stream.c index 17b6799..10727e0 100644 --- a/c/enc/brotli_bit_stream.c +++ b/c/enc/brotli_bit_stream.c
@@ -1019,11 +1019,25 @@ { 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; + size_t max_type_id = BROTLI_MIN(size_t, mb->literal_split.num_types, 256); + size_t type_id; + for (type_id = 0; type_id < max_type_id; ++type_id) { + if (mb->literal_is_base64[type_id >> 3] & (1u << (type_id & 7))) { + if (mb->literal_context_map) { + size_t j; + for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS); ++j) { + uint32_t b64_histo_id = + mb->literal_context_map[(type_id << BROTLI_LITERAL_CONTEXT_BITS) + j]; + if (b64_histo_id < 256) { + is_base64_histogram[b64_histo_id] = 1; + } + } + } else { + uint32_t b64_histo_id = (uint32_t)type_id; + if (b64_histo_id < 256) { + is_base64_histogram[b64_histo_id] = 1; + } + } } }
diff --git a/c/enc/metablock.c b/c/enc/metablock.c index 3f64497..2204f17 100644 --- a/c/enc/metablock.c +++ b/c/enc/metablock.c
@@ -106,6 +106,74 @@ split->num_types++; } +static void AppendBase64Histogram(MemoryManager* m, MetaBlockSplit* mb) { + size_t base64_type_id = mb->literal_split.num_types - 1; + size_t b64_histo_id = mb->literal_histograms_size; + size_t new_context_map_size = + mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS; + HistogramLiteral* new_histos = + BROTLI_ALLOC(m, HistogramLiteral, mb->literal_histograms_size + 1); + uint32_t* new_context_map = + BROTLI_ALLOC(m, uint32_t, new_context_map_size); + size_t i; + if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_histos) || + BROTLI_IS_NULL(new_context_map)) { + BROTLI_FREE(m, new_histos); + BROTLI_FREE(m, new_context_map); + 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]); + mb->literal_histograms_size++; + + if (mb->literal_context_map != NULL) { + memcpy(new_context_map, mb->literal_context_map, + mb->literal_context_map_size * sizeof(uint32_t)); + BROTLI_FREE(m, mb->literal_context_map); + } else { + /* If context map was NULL (num_contexts == 1), initialize preceding types */ + size_t t; + for (t = 0; t < base64_type_id; ++t) { + for (i = 0; i < 64; ++i) { + new_context_map[(t << 6) + i] = (uint32_t)t; + } + } + } + mb->literal_context_map = new_context_map; + mb->literal_context_map_size = new_context_map_size; + for (i = 0; i < 64; ++i) { + mb->literal_context_map[(base64_type_id << 6) + i] = (uint32_t)b64_histo_id; + } +} + +static void MapBase64RegionsToLiteralPositions( + const Command* commands, size_t num_commands, size_t last_flush_pos, + const Base64Region* in_regions, size_t num_in_regions, + Base64Region* out_regions) { + size_t r; + for (r = 0; r < num_in_regions; ++r) { + size_t target_ring_pos = in_regions[r].start_literal_pos; + size_t curr_ring_pos = last_flush_pos; + size_t curr_lit_pos = 0; + size_t i; + for (i = 0; i < num_commands; ++i) { + const Command cmd = commands[i]; + if (curr_ring_pos + cmd.insert_len_ >= target_ring_pos) { + size_t offset = target_ring_pos > curr_ring_pos ? target_ring_pos - curr_ring_pos : 0; + curr_lit_pos += offset; + break; + } + curr_lit_pos += cmd.insert_len_; + curr_ring_pos += cmd.insert_len_ + CommandCopyLen(&cmd); + } + out_regions[r].start_literal_pos = curr_lit_pos; + out_regions[r].length = in_regions[r].length; + } +} + void BrotliInitDistanceParams(BrotliDistanceParams* dist_params, uint32_t npostfix, uint32_t ndirect, BROTLI_BOOL large_window) { uint32_t alphabet_size_max; @@ -223,7 +291,6 @@ 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; @@ -273,14 +340,6 @@ &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 = @@ -337,26 +396,6 @@ 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;) { @@ -369,6 +408,21 @@ } } + if (num_base64_regions > 0 && mb->literal_split.num_types < 256 && + mb->literal_histograms_size < 256) { + Base64Region local_b64[256]; + size_t safe_num_b64 = BROTLI_MIN(size_t, num_base64_regions, 256); + MapBase64RegionsToLiteralPositions(cmds, num_commands, pos, + base64_regions, safe_num_b64, + local_b64); + ForceBase64LiteralSplits(m, &mb->literal_split, local_b64, + safe_num_b64, 0, mb); + if (!BROTLI_IS_OOM(m)) { + AppendBase64Histogram(m, mb); + } + if (BROTLI_IS_OOM(m)) return; + } + BROTLI_DCHECK(mb->distance_context_map == 0); mb->distance_context_map_size = mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS; @@ -658,6 +712,7 @@ ContextLut literal_context_lut, const size_t num_contexts, const uint32_t* static_context_map, const Command* commands, size_t n_commands, MetaBlockSplit* mb) { + const size_t start_pos = pos; size_t num_literals = 0; size_t i; for (i = 0; i < n_commands; ++i) { @@ -722,9 +777,15 @@ 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 (num_base64_regions > 0 && mb->literal_split.num_types < 256 && + mb->literal_histograms_size + num_contexts <= 256) { + Base64Region local_b64[256]; + size_t safe_num_b64 = BROTLI_MIN(size_t, num_base64_regions, 256); + MapBase64RegionsToLiteralPositions(commands, n_commands, start_pos, + base64_regions, safe_num_b64, + local_b64); + ForceBase64LiteralSplits(m, &mb->literal_split, local_b64, + safe_num_b64, 0, mb); if (BROTLI_IS_OOM(m)) return; { size_t num_b64_histos = num_contexts;