metablock.c (26696B)
1 /* Copyright 2015 Google Inc. All Rights Reserved. 2 3 Distributed under MIT license. 4 See file LICENSE for detail or copy at https://opensource.org/licenses/MIT 5 */ 6 7 /* Algorithms for distributing the literals and commands of a metablock between 8 block types and contexts. */ 9 10 #include "metablock.h" 11 12 #include "../common/constants.h" 13 #include "../common/context.h" 14 #include "../common/platform.h" 15 #include "bit_cost.h" 16 #include "block_splitter.h" 17 #include "cluster.h" 18 #include "command.h" 19 #include "entropy_encode.h" 20 #include "histogram.h" 21 #include "memory.h" 22 #include "params.h" 23 #include "prefix.h" 24 25 #if defined(__cplusplus) || defined(c_plusplus) 26 extern "C" { 27 #endif 28 29 void BrotliInitDistanceParams(BrotliDistanceParams* dist_params, 30 uint32_t npostfix, uint32_t ndirect, BROTLI_BOOL large_window) { 31 uint32_t alphabet_size_max; 32 uint32_t alphabet_size_limit; 33 uint32_t max_distance; 34 35 dist_params->distance_postfix_bits = npostfix; 36 dist_params->num_direct_distance_codes = ndirect; 37 38 alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE( 39 npostfix, ndirect, BROTLI_MAX_DISTANCE_BITS); 40 alphabet_size_limit = alphabet_size_max; 41 max_distance = ndirect + (1U << (BROTLI_MAX_DISTANCE_BITS + npostfix + 2)) - 42 (1U << (npostfix + 2)); 43 44 if (large_window) { 45 BrotliDistanceCodeLimit limit = BrotliCalculateDistanceCodeLimit( 46 BROTLI_MAX_ALLOWED_DISTANCE, npostfix, ndirect); 47 alphabet_size_max = BROTLI_DISTANCE_ALPHABET_SIZE( 48 npostfix, ndirect, BROTLI_LARGE_MAX_DISTANCE_BITS); 49 alphabet_size_limit = limit.max_alphabet_size; 50 max_distance = limit.max_distance; 51 } 52 53 dist_params->alphabet_size_max = alphabet_size_max; 54 dist_params->alphabet_size_limit = alphabet_size_limit; 55 dist_params->max_distance = max_distance; 56 } 57 58 static void RecomputeDistancePrefixes(Command* cmds, 59 size_t num_commands, 60 const BrotliDistanceParams* orig_params, 61 const BrotliDistanceParams* new_params) { 62 size_t i; 63 64 if (orig_params->distance_postfix_bits == new_params->distance_postfix_bits && 65 orig_params->num_direct_distance_codes == 66 new_params->num_direct_distance_codes) { 67 return; 68 } 69 70 for (i = 0; i < num_commands; ++i) { 71 Command* cmd = &cmds[i]; 72 if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) { 73 PrefixEncodeCopyDistance(CommandRestoreDistanceCode(cmd, orig_params), 74 new_params->num_direct_distance_codes, 75 new_params->distance_postfix_bits, 76 &cmd->dist_prefix_, 77 &cmd->dist_extra_); 78 } 79 } 80 } 81 82 static BROTLI_BOOL ComputeDistanceCost(const Command* cmds, 83 size_t num_commands, 84 const BrotliDistanceParams* orig_params, 85 const BrotliDistanceParams* new_params, 86 double* cost, 87 HistogramDistance* tmp) { 88 size_t i; 89 BROTLI_BOOL equal_params = BROTLI_FALSE; 90 uint16_t dist_prefix; 91 uint32_t dist_extra; 92 double extra_bits = 0.0; 93 HistogramClearDistance(tmp); 94 95 if (orig_params->distance_postfix_bits == new_params->distance_postfix_bits && 96 orig_params->num_direct_distance_codes == 97 new_params->num_direct_distance_codes) { 98 equal_params = BROTLI_TRUE; 99 } 100 101 for (i = 0; i < num_commands; i++) { 102 const Command* cmd = &cmds[i]; 103 if (CommandCopyLen(cmd) && cmd->cmd_prefix_ >= 128) { 104 if (equal_params) { 105 dist_prefix = cmd->dist_prefix_; 106 } else { 107 uint32_t distance = CommandRestoreDistanceCode(cmd, orig_params); 108 if (distance > new_params->max_distance) { 109 return BROTLI_FALSE; 110 } 111 PrefixEncodeCopyDistance(distance, 112 new_params->num_direct_distance_codes, 113 new_params->distance_postfix_bits, 114 &dist_prefix, 115 &dist_extra); 116 } 117 HistogramAddDistance(tmp, dist_prefix & 0x3FF); 118 extra_bits += dist_prefix >> 10; 119 } 120 } 121 122 *cost = BrotliPopulationCostDistance(tmp) + extra_bits; 123 return BROTLI_TRUE; 124 } 125 126 void BrotliBuildMetaBlock(MemoryManager* m, 127 const uint8_t* ringbuffer, 128 const size_t pos, 129 const size_t mask, 130 BrotliEncoderParams* params, 131 uint8_t prev_byte, 132 uint8_t prev_byte2, 133 Command* cmds, 134 size_t num_commands, 135 ContextType literal_context_mode, 136 MetaBlockSplit* mb) { 137 /* Histogram ids need to fit in one byte. */ 138 static const size_t kMaxNumberOfHistograms = 256; 139 HistogramDistance* distance_histograms; 140 HistogramLiteral* literal_histograms; 141 ContextType* literal_context_modes = NULL; 142 size_t literal_histograms_size; 143 size_t distance_histograms_size; 144 size_t i; 145 size_t literal_context_multiplier = 1; 146 uint32_t npostfix; 147 uint32_t ndirect_msb = 0; 148 BROTLI_BOOL check_orig = BROTLI_TRUE; 149 double best_dist_cost = 1e99; 150 BrotliDistanceParams orig_params = params->dist; 151 BrotliDistanceParams new_params = params->dist; 152 HistogramDistance* tmp = BROTLI_ALLOC(m, HistogramDistance, 1); 153 154 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(tmp)) return; 155 156 for (npostfix = 0; npostfix <= BROTLI_MAX_NPOSTFIX; npostfix++) { 157 for (; ndirect_msb < 16; ndirect_msb++) { 158 uint32_t ndirect = ndirect_msb << npostfix; 159 BROTLI_BOOL skip; 160 double dist_cost; 161 BrotliInitDistanceParams(&new_params, npostfix, ndirect, 162 params->large_window); 163 if (npostfix == orig_params.distance_postfix_bits && 164 ndirect == orig_params.num_direct_distance_codes) { 165 check_orig = BROTLI_FALSE; 166 } 167 skip = !ComputeDistanceCost( 168 cmds, num_commands, &orig_params, &new_params, &dist_cost, tmp); 169 if (skip || (dist_cost > best_dist_cost)) { 170 break; 171 } 172 best_dist_cost = dist_cost; 173 params->dist = new_params; 174 } 175 if (ndirect_msb > 0) ndirect_msb--; 176 ndirect_msb /= 2; 177 } 178 if (check_orig) { 179 double dist_cost; 180 ComputeDistanceCost(cmds, num_commands, &orig_params, &orig_params, 181 &dist_cost, tmp); 182 if (dist_cost < best_dist_cost) { 183 /* NB: currently unused; uncomment when more param tuning is added. */ 184 /* best_dist_cost = dist_cost; */ 185 params->dist = orig_params; 186 } 187 } 188 BROTLI_FREE(m, tmp); 189 RecomputeDistancePrefixes(cmds, num_commands, &orig_params, ¶ms->dist); 190 191 BrotliSplitBlock(m, cmds, num_commands, 192 ringbuffer, pos, mask, params, 193 &mb->literal_split, 194 &mb->command_split, 195 &mb->distance_split); 196 if (BROTLI_IS_OOM(m)) return; 197 198 if (!params->disable_literal_context_modeling) { 199 literal_context_multiplier = 1 << BROTLI_LITERAL_CONTEXT_BITS; 200 literal_context_modes = 201 BROTLI_ALLOC(m, ContextType, mb->literal_split.num_types); 202 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(literal_context_modes)) return; 203 for (i = 0; i < mb->literal_split.num_types; ++i) { 204 literal_context_modes[i] = literal_context_mode; 205 } 206 } 207 208 literal_histograms_size = 209 mb->literal_split.num_types * literal_context_multiplier; 210 literal_histograms = 211 BROTLI_ALLOC(m, HistogramLiteral, literal_histograms_size); 212 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(literal_histograms)) return; 213 ClearHistogramsLiteral(literal_histograms, literal_histograms_size); 214 215 distance_histograms_size = 216 mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS; 217 distance_histograms = 218 BROTLI_ALLOC(m, HistogramDistance, distance_histograms_size); 219 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(distance_histograms)) return; 220 ClearHistogramsDistance(distance_histograms, distance_histograms_size); 221 222 BROTLI_DCHECK(mb->command_histograms == 0); 223 mb->command_histograms_size = mb->command_split.num_types; 224 mb->command_histograms = 225 BROTLI_ALLOC(m, HistogramCommand, mb->command_histograms_size); 226 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->command_histograms)) return; 227 ClearHistogramsCommand(mb->command_histograms, mb->command_histograms_size); 228 229 BrotliBuildHistogramsWithContext(cmds, num_commands, 230 &mb->literal_split, &mb->command_split, &mb->distance_split, 231 ringbuffer, pos, mask, prev_byte, prev_byte2, literal_context_modes, 232 literal_histograms, mb->command_histograms, distance_histograms); 233 BROTLI_FREE(m, literal_context_modes); 234 235 BROTLI_DCHECK(mb->literal_context_map == 0); 236 mb->literal_context_map_size = 237 mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS; 238 mb->literal_context_map = 239 BROTLI_ALLOC(m, uint32_t, mb->literal_context_map_size); 240 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->literal_context_map)) return; 241 242 BROTLI_DCHECK(mb->literal_histograms == 0); 243 mb->literal_histograms_size = mb->literal_context_map_size; 244 mb->literal_histograms = 245 BROTLI_ALLOC(m, HistogramLiteral, mb->literal_histograms_size); 246 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->literal_histograms)) return; 247 248 BrotliClusterHistogramsLiteral(m, literal_histograms, literal_histograms_size, 249 kMaxNumberOfHistograms, mb->literal_histograms, 250 &mb->literal_histograms_size, mb->literal_context_map); 251 if (BROTLI_IS_OOM(m)) return; 252 BROTLI_FREE(m, literal_histograms); 253 254 if (params->disable_literal_context_modeling) { 255 /* Distribute assignment to all contexts. */ 256 for (i = mb->literal_split.num_types; i != 0;) { 257 size_t j = 0; 258 i--; 259 for (; j < (1 << BROTLI_LITERAL_CONTEXT_BITS); j++) { 260 mb->literal_context_map[(i << BROTLI_LITERAL_CONTEXT_BITS) + j] = 261 mb->literal_context_map[i]; 262 } 263 } 264 } 265 266 BROTLI_DCHECK(mb->distance_context_map == 0); 267 mb->distance_context_map_size = 268 mb->distance_split.num_types << BROTLI_DISTANCE_CONTEXT_BITS; 269 mb->distance_context_map = 270 BROTLI_ALLOC(m, uint32_t, mb->distance_context_map_size); 271 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->distance_context_map)) return; 272 273 BROTLI_DCHECK(mb->distance_histograms == 0); 274 mb->distance_histograms_size = mb->distance_context_map_size; 275 mb->distance_histograms = 276 BROTLI_ALLOC(m, HistogramDistance, mb->distance_histograms_size); 277 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->distance_histograms)) return; 278 279 BrotliClusterHistogramsDistance(m, distance_histograms, 280 mb->distance_context_map_size, 281 kMaxNumberOfHistograms, 282 mb->distance_histograms, 283 &mb->distance_histograms_size, 284 mb->distance_context_map); 285 if (BROTLI_IS_OOM(m)) return; 286 BROTLI_FREE(m, distance_histograms); 287 } 288 289 #define FN(X) X ## Literal 290 #include "metablock_inc.h" /* NOLINT(build/include) */ 291 #undef FN 292 293 #define FN(X) X ## Command 294 #include "metablock_inc.h" /* NOLINT(build/include) */ 295 #undef FN 296 297 #define FN(X) X ## Distance 298 #include "metablock_inc.h" /* NOLINT(build/include) */ 299 #undef FN 300 301 /* Greedy block splitter for one block category (literal, command or distance). 302 Gathers histograms for all context buckets. */ 303 typedef struct ContextBlockSplitter { 304 /* Alphabet size of particular block category. */ 305 size_t alphabet_size_; 306 size_t num_contexts_; 307 size_t max_block_types_; 308 /* We collect at least this many symbols for each block. */ 309 size_t min_block_size_; 310 /* We merge histograms A and B if 311 entropy(A+B) < entropy(A) + entropy(B) + split_threshold_, 312 where A is the current histogram and B is the histogram of the last or the 313 second last block type. */ 314 double split_threshold_; 315 316 size_t num_blocks_; 317 BlockSplit* split_; /* not owned */ 318 HistogramLiteral* histograms_; /* not owned */ 319 size_t* histograms_size_; /* not owned */ 320 321 /* The number of symbols that we want to collect before deciding on whether 322 or not to merge the block with a previous one or emit a new block. */ 323 size_t target_block_size_; 324 /* The number of symbols in the current histogram. */ 325 size_t block_size_; 326 /* Offset of the current histogram. */ 327 size_t curr_histogram_ix_; 328 /* Offset of the histograms of the previous two block types. */ 329 size_t last_histogram_ix_[2]; 330 /* Entropy of the previous two block types. */ 331 double last_entropy_[2 * BROTLI_MAX_STATIC_CONTEXTS]; 332 /* The number of times we merged the current block with the last one. */ 333 size_t merge_last_count_; 334 } ContextBlockSplitter; 335 336 static void InitContextBlockSplitter( 337 MemoryManager* m, ContextBlockSplitter* self, size_t alphabet_size, 338 size_t num_contexts, size_t min_block_size, double split_threshold, 339 size_t num_symbols, BlockSplit* split, HistogramLiteral** histograms, 340 size_t* histograms_size) { 341 size_t max_num_blocks = num_symbols / min_block_size + 1; 342 size_t max_num_types; 343 BROTLI_DCHECK(num_contexts <= BROTLI_MAX_STATIC_CONTEXTS); 344 345 self->alphabet_size_ = alphabet_size; 346 self->num_contexts_ = num_contexts; 347 self->max_block_types_ = BROTLI_MAX_NUMBER_OF_BLOCK_TYPES / num_contexts; 348 self->min_block_size_ = min_block_size; 349 self->split_threshold_ = split_threshold; 350 self->num_blocks_ = 0; 351 self->split_ = split; 352 self->histograms_size_ = histograms_size; 353 self->target_block_size_ = min_block_size; 354 self->block_size_ = 0; 355 self->curr_histogram_ix_ = 0; 356 self->merge_last_count_ = 0; 357 358 /* We have to allocate one more histogram than the maximum number of block 359 types for the current histogram when the meta-block is too big. */ 360 max_num_types = 361 BROTLI_MIN(size_t, max_num_blocks, self->max_block_types_ + 1); 362 BROTLI_ENSURE_CAPACITY(m, uint8_t, 363 split->types, split->types_alloc_size, max_num_blocks); 364 BROTLI_ENSURE_CAPACITY(m, uint32_t, 365 split->lengths, split->lengths_alloc_size, max_num_blocks); 366 if (BROTLI_IS_OOM(m)) return; 367 split->num_blocks = max_num_blocks; 368 if (BROTLI_IS_OOM(m)) return; 369 BROTLI_DCHECK(*histograms == 0); 370 *histograms_size = max_num_types * num_contexts; 371 *histograms = BROTLI_ALLOC(m, HistogramLiteral, *histograms_size); 372 self->histograms_ = *histograms; 373 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(*histograms)) return; 374 /* Clear only current histogram. */ 375 ClearHistogramsLiteral(&self->histograms_[0], num_contexts); 376 self->last_histogram_ix_[0] = self->last_histogram_ix_[1] = 0; 377 } 378 379 /* Does either of three things: 380 (1) emits the current block with a new block type; 381 (2) emits the current block with the type of the second last block; 382 (3) merges the current block with the last block. */ 383 static void ContextBlockSplitterFinishBlock( 384 ContextBlockSplitter* self, MemoryManager* m, BROTLI_BOOL is_final) { 385 BlockSplit* split = self->split_; 386 const size_t num_contexts = self->num_contexts_; 387 double* last_entropy = self->last_entropy_; 388 HistogramLiteral* histograms = self->histograms_; 389 390 if (self->block_size_ < self->min_block_size_) { 391 self->block_size_ = self->min_block_size_; 392 } 393 if (self->num_blocks_ == 0) { 394 size_t i; 395 /* Create first block. */ 396 split->lengths[0] = (uint32_t)self->block_size_; 397 split->types[0] = 0; 398 399 for (i = 0; i < num_contexts; ++i) { 400 last_entropy[i] = 401 BrotliBitsEntropy(histograms[i].data_, self->alphabet_size_); 402 last_entropy[num_contexts + i] = last_entropy[i]; 403 } 404 ++self->num_blocks_; 405 ++split->num_types; 406 self->curr_histogram_ix_ += num_contexts; 407 if (self->curr_histogram_ix_ < *self->histograms_size_) { 408 ClearHistogramsLiteral( 409 &self->histograms_[self->curr_histogram_ix_], self->num_contexts_); 410 } 411 self->block_size_ = 0; 412 } else if (self->block_size_ > 0) { 413 /* Try merging the set of histograms for the current block type with the 414 respective set of histograms for the last and second last block types. 415 Decide over the split based on the total reduction of entropy across 416 all contexts. */ 417 double entropy[BROTLI_MAX_STATIC_CONTEXTS]; 418 HistogramLiteral* combined_histo = 419 BROTLI_ALLOC(m, HistogramLiteral, 2 * num_contexts); 420 double combined_entropy[2 * BROTLI_MAX_STATIC_CONTEXTS]; 421 double diff[2] = { 0.0 }; 422 size_t i; 423 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(combined_histo)) return; 424 for (i = 0; i < num_contexts; ++i) { 425 size_t curr_histo_ix = self->curr_histogram_ix_ + i; 426 size_t j; 427 entropy[i] = BrotliBitsEntropy(histograms[curr_histo_ix].data_, 428 self->alphabet_size_); 429 for (j = 0; j < 2; ++j) { 430 size_t jx = j * num_contexts + i; 431 size_t last_histogram_ix = self->last_histogram_ix_[j] + i; 432 combined_histo[jx] = histograms[curr_histo_ix]; 433 HistogramAddHistogramLiteral(&combined_histo[jx], 434 &histograms[last_histogram_ix]); 435 combined_entropy[jx] = BrotliBitsEntropy( 436 &combined_histo[jx].data_[0], self->alphabet_size_); 437 diff[j] += combined_entropy[jx] - entropy[i] - last_entropy[jx]; 438 } 439 } 440 441 if (split->num_types < self->max_block_types_ && 442 diff[0] > self->split_threshold_ && 443 diff[1] > self->split_threshold_) { 444 /* Create new block. */ 445 split->lengths[self->num_blocks_] = (uint32_t)self->block_size_; 446 split->types[self->num_blocks_] = (uint8_t)split->num_types; 447 self->last_histogram_ix_[1] = self->last_histogram_ix_[0]; 448 self->last_histogram_ix_[0] = split->num_types * num_contexts; 449 for (i = 0; i < num_contexts; ++i) { 450 last_entropy[num_contexts + i] = last_entropy[i]; 451 last_entropy[i] = entropy[i]; 452 } 453 ++self->num_blocks_; 454 ++split->num_types; 455 self->curr_histogram_ix_ += num_contexts; 456 if (self->curr_histogram_ix_ < *self->histograms_size_) { 457 ClearHistogramsLiteral( 458 &self->histograms_[self->curr_histogram_ix_], self->num_contexts_); 459 } 460 self->block_size_ = 0; 461 self->merge_last_count_ = 0; 462 self->target_block_size_ = self->min_block_size_; 463 } else if (diff[1] < diff[0] - 20.0) { 464 /* Combine this block with second last block. */ 465 split->lengths[self->num_blocks_] = (uint32_t)self->block_size_; 466 split->types[self->num_blocks_] = split->types[self->num_blocks_ - 2]; 467 BROTLI_SWAP(size_t, self->last_histogram_ix_, 0, 1); 468 for (i = 0; i < num_contexts; ++i) { 469 histograms[self->last_histogram_ix_[0] + i] = 470 combined_histo[num_contexts + i]; 471 last_entropy[num_contexts + i] = last_entropy[i]; 472 last_entropy[i] = combined_entropy[num_contexts + i]; 473 HistogramClearLiteral(&histograms[self->curr_histogram_ix_ + i]); 474 } 475 ++self->num_blocks_; 476 self->block_size_ = 0; 477 self->merge_last_count_ = 0; 478 self->target_block_size_ = self->min_block_size_; 479 } else { 480 /* Combine this block with last block. */ 481 split->lengths[self->num_blocks_ - 1] += (uint32_t)self->block_size_; 482 for (i = 0; i < num_contexts; ++i) { 483 histograms[self->last_histogram_ix_[0] + i] = combined_histo[i]; 484 last_entropy[i] = combined_entropy[i]; 485 if (split->num_types == 1) { 486 last_entropy[num_contexts + i] = last_entropy[i]; 487 } 488 HistogramClearLiteral(&histograms[self->curr_histogram_ix_ + i]); 489 } 490 self->block_size_ = 0; 491 if (++self->merge_last_count_ > 1) { 492 self->target_block_size_ += self->min_block_size_; 493 } 494 } 495 BROTLI_FREE(m, combined_histo); 496 } 497 if (is_final) { 498 *self->histograms_size_ = split->num_types * num_contexts; 499 split->num_blocks = self->num_blocks_; 500 } 501 } 502 503 /* Adds the next symbol to the current block type and context. When the 504 current block reaches the target size, decides on merging the block. */ 505 static void ContextBlockSplitterAddSymbol( 506 ContextBlockSplitter* self, MemoryManager* m, 507 size_t symbol, size_t context) { 508 HistogramAddLiteral(&self->histograms_[self->curr_histogram_ix_ + context], 509 symbol); 510 ++self->block_size_; 511 if (self->block_size_ == self->target_block_size_) { 512 ContextBlockSplitterFinishBlock(self, m, /* is_final = */ BROTLI_FALSE); 513 if (BROTLI_IS_OOM(m)) return; 514 } 515 } 516 517 static void MapStaticContexts(MemoryManager* m, 518 size_t num_contexts, 519 const uint32_t* static_context_map, 520 MetaBlockSplit* mb) { 521 size_t i; 522 BROTLI_DCHECK(mb->literal_context_map == 0); 523 mb->literal_context_map_size = 524 mb->literal_split.num_types << BROTLI_LITERAL_CONTEXT_BITS; 525 mb->literal_context_map = 526 BROTLI_ALLOC(m, uint32_t, mb->literal_context_map_size); 527 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(mb->literal_context_map)) return; 528 529 for (i = 0; i < mb->literal_split.num_types; ++i) { 530 uint32_t offset = (uint32_t)(i * num_contexts); 531 size_t j; 532 for (j = 0; j < (1u << BROTLI_LITERAL_CONTEXT_BITS); ++j) { 533 mb->literal_context_map[(i << BROTLI_LITERAL_CONTEXT_BITS) + j] = 534 offset + static_context_map[j]; 535 } 536 } 537 } 538 539 typedef struct GreedyMetablockArena { 540 union { 541 BlockSplitterLiteral plain; 542 ContextBlockSplitter ctx; 543 } lit_blocks; 544 BlockSplitterCommand cmd_blocks; 545 BlockSplitterDistance dist_blocks; 546 } GreedyMetablockArena; 547 548 static BROTLI_INLINE void BrotliBuildMetaBlockGreedyInternal( 549 MemoryManager* m, GreedyMetablockArena* arena, const uint8_t* ringbuffer, 550 size_t pos, size_t mask, uint8_t prev_byte, uint8_t prev_byte2, 551 ContextLut literal_context_lut, const size_t num_contexts, 552 const uint32_t* static_context_map, const Command* commands, 553 size_t n_commands, MetaBlockSplit* mb) { 554 size_t num_literals = 0; 555 size_t i; 556 for (i = 0; i < n_commands; ++i) { 557 num_literals += commands[i].insert_len_; 558 } 559 560 if (num_contexts == 1) { 561 InitBlockSplitterLiteral(m, &arena->lit_blocks.plain, 256, 512, 400.0, 562 num_literals, &mb->literal_split, &mb->literal_histograms, 563 &mb->literal_histograms_size); 564 } else { 565 InitContextBlockSplitter(m, &arena->lit_blocks.ctx, 256, num_contexts, 512, 566 400.0, num_literals, &mb->literal_split, &mb->literal_histograms, 567 &mb->literal_histograms_size); 568 } 569 if (BROTLI_IS_OOM(m)) return; 570 InitBlockSplitterCommand(m, &arena->cmd_blocks, BROTLI_NUM_COMMAND_SYMBOLS, 571 1024, 500.0, n_commands, &mb->command_split, &mb->command_histograms, 572 &mb->command_histograms_size); 573 if (BROTLI_IS_OOM(m)) return; 574 InitBlockSplitterDistance(m, &arena->dist_blocks, 64, 512, 100.0, n_commands, 575 &mb->distance_split, &mb->distance_histograms, 576 &mb->distance_histograms_size); 577 if (BROTLI_IS_OOM(m)) return; 578 579 for (i = 0; i < n_commands; ++i) { 580 const Command cmd = commands[i]; 581 size_t j; 582 BlockSplitterAddSymbolCommand(&arena->cmd_blocks, cmd.cmd_prefix_); 583 for (j = cmd.insert_len_; j != 0; --j) { 584 uint8_t literal = ringbuffer[pos & mask]; 585 if (num_contexts == 1) { 586 BlockSplitterAddSymbolLiteral(&arena->lit_blocks.plain, literal); 587 } else { 588 size_t context = 589 BROTLI_CONTEXT(prev_byte, prev_byte2, literal_context_lut); 590 ContextBlockSplitterAddSymbol(&arena->lit_blocks.ctx, m, literal, 591 static_context_map[context]); 592 if (BROTLI_IS_OOM(m)) return; 593 } 594 prev_byte2 = prev_byte; 595 prev_byte = literal; 596 ++pos; 597 } 598 pos += CommandCopyLen(&cmd); 599 if (CommandCopyLen(&cmd)) { 600 prev_byte2 = ringbuffer[(pos - 2) & mask]; 601 prev_byte = ringbuffer[(pos - 1) & mask]; 602 if (cmd.cmd_prefix_ >= 128) { 603 BlockSplitterAddSymbolDistance( 604 &arena->dist_blocks, cmd.dist_prefix_ & 0x3FF); 605 } 606 } 607 } 608 609 if (num_contexts == 1) { 610 BlockSplitterFinishBlockLiteral( 611 &arena->lit_blocks.plain, /* is_final = */ BROTLI_TRUE); 612 } else { 613 ContextBlockSplitterFinishBlock( 614 &arena->lit_blocks.ctx, m, /* is_final = */ BROTLI_TRUE); 615 if (BROTLI_IS_OOM(m)) return; 616 } 617 BlockSplitterFinishBlockCommand( 618 &arena->cmd_blocks, /* is_final = */ BROTLI_TRUE); 619 BlockSplitterFinishBlockDistance( 620 &arena->dist_blocks, /* is_final = */ BROTLI_TRUE); 621 622 if (num_contexts > 1) { 623 MapStaticContexts(m, num_contexts, static_context_map, mb); 624 } 625 } 626 627 void BrotliBuildMetaBlockGreedy(MemoryManager* m, 628 const uint8_t* ringbuffer, 629 size_t pos, 630 size_t mask, 631 uint8_t prev_byte, 632 uint8_t prev_byte2, 633 ContextLut literal_context_lut, 634 size_t num_contexts, 635 const uint32_t* static_context_map, 636 const Command* commands, 637 size_t n_commands, 638 MetaBlockSplit* mb) { 639 GreedyMetablockArena* arena = BROTLI_ALLOC(m, GreedyMetablockArena, 1); 640 if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(arena)) return; 641 if (num_contexts == 1) { 642 BrotliBuildMetaBlockGreedyInternal(m, arena, ringbuffer, pos, mask, 643 prev_byte, prev_byte2, literal_context_lut, 1, NULL, commands, 644 n_commands, mb); 645 } else { 646 BrotliBuildMetaBlockGreedyInternal(m, arena, ringbuffer, pos, mask, 647 prev_byte, prev_byte2, literal_context_lut, num_contexts, 648 static_context_map, commands, n_commands, mb); 649 } 650 BROTLI_FREE(m, arena); 651 } 652 653 void BrotliOptimizeHistograms(uint32_t num_distance_codes, 654 MetaBlockSplit* mb) { 655 uint8_t good_for_rle[BROTLI_NUM_COMMAND_SYMBOLS]; 656 size_t i; 657 for (i = 0; i < mb->literal_histograms_size; ++i) { 658 BrotliOptimizeHuffmanCountsForRle(256, mb->literal_histograms[i].data_, 659 good_for_rle); 660 } 661 for (i = 0; i < mb->command_histograms_size; ++i) { 662 BrotliOptimizeHuffmanCountsForRle(BROTLI_NUM_COMMAND_SYMBOLS, 663 mb->command_histograms[i].data_, 664 good_for_rle); 665 } 666 for (i = 0; i < mb->distance_histograms_size; ++i) { 667 BrotliOptimizeHuffmanCountsForRle(num_distance_codes, 668 mb->distance_histograms[i].data_, 669 good_for_rle); 670 } 671 } 672 673 #if defined(__cplusplus) || defined(c_plusplus) 674 } /* extern "C" */ 675 #endif