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