w32tex
About: TeX Live provides a comprehensive TeX system including all the major TeX-related programs, macro packages, and fonts that are free software. Windows sources.
  Fossies Dox: w32tex-src.tar.xz  ("unofficial" and yet experimental doxygen-generated source code documentation)  

encode.c
Go to the documentation of this file.
1 /* Copyright 2013 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 /* Implementation of Brotli compressor. */
8 
9 #include <brotli/encode.h>
10 
11 #include <stdlib.h> /* free, malloc */
12 #include <string.h> /* memcpy, memset */
13 
14 #include "../common/constants.h"
15 #include "../common/context.h"
16 #include "../common/platform.h"
17 #include "../common/version.h"
18 #include "./backward_references.h"
20 #include "./bit_cost.h"
21 #include "./brotli_bit_stream.h"
22 #include "./compress_fragment.h"
24 #include "./encoder_dict.h"
25 #include "./entropy_encode.h"
26 #include "./fast_log.h"
27 #include "./hash.h"
28 #include "./histogram.h"
29 #include "./memory.h"
30 #include "./metablock.h"
31 #include "./prefix.h"
32 #include "./quality.h"
33 #include "./ringbuffer.h"
34 #include "./utf8_util.h"
35 #include "./write_bits.h"
36 
37 #if defined(__cplusplus) || defined(c_plusplus)
38 extern "C" {
39 #endif
40 
41 #define COPY_ARRAY(dst, src) memcpy(dst, src, sizeof(src));
42 
44  /* Default state. */
46  /* Intermediate state; after next block is emitted, byte-padding should be
47  performed before getting back to default state. */
49  /* Last metablock was produced; no more input is acceptable. */
51  /* Flushing compressed block and writing meta-data block header. */
53  /* Writing metadata block body. */
56 
64 
65 typedef struct BrotliEncoderStateStruct {
67 
69 
74  size_t num_commands_;
75  size_t num_literals_;
83  /* "Flint" is a tiny uncompressed block emitted before the continuation
84  block to unwire literal context from previous data. Despite being int8_t,
85  field is actually BrotliEncoderFlintState enum. */
89  size_t storage_size_;
91 
93 
94  /* Hash table for FAST_ONE_PASS_COMPRESSION_QUALITY mode. */
95  int small_table_[1 << 10]; /* 4KiB */
96  int* large_table_; /* Allocated only when needed */
98  /* Command and distance prefix codes (each 64 symbols, stored back-to-back)
99  used for the next block in FAST_ONE_PASS_COMPRESSION_QUALITY. The command
100  prefix code is over a smaller alphabet with the following 64 symbols:
101  0 - 15: insert length code 0, copy length code 0 - 15, same distance
102  16 - 39: insert length code 0, copy length code 0 - 23
103  40 - 63: insert length code 0 - 23, copy length code 0
104  Note that symbols 16 and 40 represent the same code in the full alphabet,
105  but we do not use either of them in FAST_ONE_PASS_COMPRESSION_QUALITY. */
108  /* The compressed form of the command and distance prefix codes for the next
109  block in FAST_ONE_PASS_COMPRESSION_QUALITY. */
112  /* Command and literal buffers for FAST_TWO_PASS_COMPRESSION_QUALITY. */
115 
118  size_t total_out_;
119  /* Temporary buffer for padding flush bits or metadata block header / body. */
120  union {
122  uint8_t u8[16];
126 
130 
132  return (size_t)1 << s->params.lgblock;
133 }
134 
136  return s->input_pos_ - s->last_processed_pos_;
137 }
138 
141  size_t block_size = InputBlockSize(s);
142  if (delta >= block_size) return 0;
143  return block_size - (size_t)delta;
144 }
145 
148  /* Changing parameters on the fly is not implemented yet. */
149  if (state->is_initialized_) return BROTLI_FALSE;
150  /* TODO: Validate/clamp parameters here. */
151  switch (p) {
152  case BROTLI_PARAM_MODE:
153  state->params.mode = (BrotliEncoderMode)value;
154  return BROTLI_TRUE;
155 
157  state->params.quality = (int)value;
158  return BROTLI_TRUE;
159 
160  case BROTLI_PARAM_LGWIN:
161  state->params.lgwin = (int)value;
162  return BROTLI_TRUE;
163 
165  state->params.lgblock = (int)value;
166  return BROTLI_TRUE;
167 
169  if ((value != 0) && (value != 1)) return BROTLI_FALSE;
170  state->params.disable_literal_context_modeling = TO_BROTLI_BOOL(!!value);
171  return BROTLI_TRUE;
172 
174  state->params.size_hint = value;
175  return BROTLI_TRUE;
176 
178  state->params.large_window = TO_BROTLI_BOOL(!!value);
179  return BROTLI_TRUE;
180 
182  state->params.dist.distance_postfix_bits = value;
183  return BROTLI_TRUE;
184 
186  state->params.dist.num_direct_distance_codes = value;
187  return BROTLI_TRUE;
188 
190  if (value > (1u << 30)) return BROTLI_FALSE;
191  state->params.stream_offset = value;
192  return BROTLI_TRUE;
193 
194  default: return BROTLI_FALSE;
195  }
196 }
197 
198 /* Wraps 64-bit input position to 32-bit ring-buffer position preserving
199  "not-a-first-lap" feature. */
202  uint64_t gb = position >> 30;
203  if (gb > 2) {
204  /* Wrap every 2GiB; The first 3GB are continuous. */
205  result = (result & ((1u << 30) - 1)) | ((uint32_t)((gb - 1) & 1) + 1) << 30;
206  }
207  return result;
208 }
209 
211  MemoryManager* m = &s->memory_manager_;
212  if (s->storage_size_ < size) {
213  BROTLI_FREE(m, s->storage_);
214  s->storage_ = BROTLI_ALLOC(m, uint8_t, size);
215  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(s->storage_)) return NULL;
216  s->storage_size_ = size;
217  }
218  return s->storage_;
219 }
220 
221 static size_t HashTableSize(size_t max_table_size, size_t input_size) {
222  size_t htsize = 256;
223  while (htsize < max_table_size && htsize < input_size) {
224  htsize <<= 1;
225  }
226  return htsize;
227 }
228 
230  size_t input_size, size_t* table_size) {
231  /* Use smaller hash table when input.size() is smaller, since we
232  fill the table, incurring O(hash table size) overhead for
233  compression, and if the input is short, we won't need that
234  many hash table entries anyway. */
235  MemoryManager* m = &s->memory_manager_;
236  const size_t max_table_size = MaxHashTableSize(quality);
237  size_t htsize = HashTableSize(max_table_size, input_size);
238  int* table;
239  BROTLI_DCHECK(max_table_size >= 256);
241  /* Only odd shifts are supported by fast-one-pass. */
242  if ((htsize & 0xAAAAA) == 0) {
243  htsize <<= 1;
244  }
245  }
246 
247  if (htsize <= sizeof(s->small_table_) / sizeof(s->small_table_[0])) {
248  table = s->small_table_;
249  } else {
250  if (htsize > s->large_table_size_) {
251  s->large_table_size_ = htsize;
252  BROTLI_FREE(m, s->large_table_);
253  s->large_table_ = BROTLI_ALLOC(m, int, htsize);
254  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(s->large_table_)) return 0;
255  }
256  table = s->large_table_;
257  }
258 
259  *table_size = htsize;
260  memset(table, 0, htsize * sizeof(*table));
261  return table;
262 }
263 
264 static void EncodeWindowBits(int lgwin, BROTLI_BOOL large_window,
265  uint16_t* last_bytes, uint8_t* last_bytes_bits) {
266  if (large_window) {
267  *last_bytes = (uint16_t)(((lgwin & 0x3F) << 8) | 0x11);
268  *last_bytes_bits = 14;
269  } else {
270  if (lgwin == 16) {
271  *last_bytes = 0;
272  *last_bytes_bits = 1;
273  } else if (lgwin == 17) {
274  *last_bytes = 1;
275  *last_bytes_bits = 7;
276  } else if (lgwin > 17) {
277  *last_bytes = (uint16_t)(((lgwin - 17) << 1) | 0x01);
278  *last_bytes_bits = 4;
279  } else {
280  *last_bytes = (uint16_t)(((lgwin - 8) << 4) | 0x01);
281  *last_bytes_bits = 7;
282  }
283  }
284 }
285 
286 /* Initializes the command and distance prefix codes for the first block. */
287 static void InitCommandPrefixCodes(uint8_t cmd_depths[128],
288  uint16_t cmd_bits[128],
289  uint8_t cmd_code[512],
290  size_t* cmd_code_numbits) {
291  static const uint8_t kDefaultCommandDepths[128] = {
292  0, 4, 4, 5, 6, 6, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8,
293  0, 0, 0, 4, 4, 4, 4, 4, 5, 5, 6, 6, 6, 6, 7, 7,
294  7, 7, 10, 10, 10, 10, 10, 10, 0, 4, 4, 5, 5, 5, 6, 6,
295  7, 8, 8, 9, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10,
296  5, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
297  6, 6, 6, 6, 6, 6, 5, 5, 5, 5, 5, 5, 4, 4, 4, 4,
298  4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 6, 7, 7, 7, 8, 10,
299  12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12, 12,
300  };
301  static const uint16_t kDefaultCommandBits[128] = {
302  0, 0, 8, 9, 3, 35, 7, 71,
303  39, 103, 23, 47, 175, 111, 239, 31,
304  0, 0, 0, 4, 12, 2, 10, 6,
305  13, 29, 11, 43, 27, 59, 87, 55,
306  15, 79, 319, 831, 191, 703, 447, 959,
307  0, 14, 1, 25, 5, 21, 19, 51,
308  119, 159, 95, 223, 479, 991, 63, 575,
309  127, 639, 383, 895, 255, 767, 511, 1023,
310  14, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
311  27, 59, 7, 39, 23, 55, 30, 1, 17, 9, 25, 5, 0, 8, 4, 12,
312  2, 10, 6, 21, 13, 29, 3, 19, 11, 15, 47, 31, 95, 63, 127, 255,
313  767, 2815, 1791, 3839, 511, 2559, 1535, 3583, 1023, 3071, 2047, 4095,
314  };
315  static const uint8_t kDefaultCommandCode[] = {
316  0xff, 0x77, 0xd5, 0xbf, 0xe7, 0xde, 0xea, 0x9e, 0x51, 0x5d, 0xde, 0xc6,
317  0x70, 0x57, 0xbc, 0x58, 0x58, 0x58, 0xd8, 0xd8, 0x58, 0xd5, 0xcb, 0x8c,
318  0xea, 0xe0, 0xc3, 0x87, 0x1f, 0x83, 0xc1, 0x60, 0x1c, 0x67, 0xb2, 0xaa,
319  0x06, 0x83, 0xc1, 0x60, 0x30, 0x18, 0xcc, 0xa1, 0xce, 0x88, 0x54, 0x94,
320  0x46, 0xe1, 0xb0, 0xd0, 0x4e, 0xb2, 0xf7, 0x04, 0x00,
321  };
322  static const size_t kDefaultCommandCodeNumBits = 448;
323  COPY_ARRAY(cmd_depths, kDefaultCommandDepths);
324  COPY_ARRAY(cmd_bits, kDefaultCommandBits);
325 
326  /* Initialize the pre-compressed form of the command and distance prefix
327  codes. */
328  COPY_ARRAY(cmd_code, kDefaultCommandCode);
329  *cmd_code_numbits = kDefaultCommandCodeNumBits;
330 }
331 
332 /* Decide about the context map based on the ability of the prediction
333  ability of the previous byte UTF8-prefix on the next byte. The
334  prediction ability is calculated as Shannon entropy. Here we need
335  Shannon entropy instead of 'BitsEntropy' since the prefix will be
336  encoded with the remaining 6 bits of the following byte, and
337  BitsEntropy will assume that symbol to be stored alone using Huffman
338  coding. */
339 static void ChooseContextMap(int quality,
340  uint32_t* bigram_histo,
341  size_t* num_literal_contexts,
342  const uint32_t** literal_context_map) {
343  static const uint32_t kStaticContextMapContinuation[64] = {
344  1, 1, 2, 2, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
345  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
346  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
347  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
348  };
349  static const uint32_t kStaticContextMapSimpleUTF8[64] = {
350  0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
351  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
352  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
353  0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
354  };
355 
356  uint32_t monogram_histo[3] = { 0 };
357  uint32_t two_prefix_histo[6] = { 0 };
358  size_t total;
359  size_t i;
360  size_t dummy;
361  double entropy[4];
362  for (i = 0; i < 9; ++i) {
363  monogram_histo[i % 3] += bigram_histo[i];
364  two_prefix_histo[i % 6] += bigram_histo[i];
365  }
366  entropy[1] = ShannonEntropy(monogram_histo, 3, &dummy);
367  entropy[2] = (ShannonEntropy(two_prefix_histo, 3, &dummy) +
368  ShannonEntropy(two_prefix_histo + 3, 3, &dummy));
369  entropy[3] = 0;
370  for (i = 0; i < 3; ++i) {
371  entropy[3] += ShannonEntropy(bigram_histo + 3 * i, 3, &dummy);
372  }
373 
374  total = monogram_histo[0] + monogram_histo[1] + monogram_histo[2];
375  BROTLI_DCHECK(total != 0);
376  entropy[0] = 1.0 / (double)total;
377  entropy[1] *= entropy[0];
378  entropy[2] *= entropy[0];
379  entropy[3] *= entropy[0];
380 
382  /* 3 context models is a bit slower, don't use it at lower qualities. */
383  entropy[3] = entropy[1] * 10;
384  }
385  /* If expected savings by symbol are less than 0.2 bits, skip the
386  context modeling -- in exchange for faster decoding speed. */
387  if (entropy[1] - entropy[2] < 0.2 &&
388  entropy[1] - entropy[3] < 0.2) {
389  *num_literal_contexts = 1;
390  } else if (entropy[2] - entropy[3] < 0.02) {
391  *num_literal_contexts = 2;
392  *literal_context_map = kStaticContextMapSimpleUTF8;
393  } else {
394  *num_literal_contexts = 3;
395  *literal_context_map = kStaticContextMapContinuation;
396  }
397 }
398 
399 /* Decide if we want to use a more complex static context map containing 13
400  context values, based on the entropy reduction of histograms over the
401  first 5 bits of literals. */
403  size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint,
404  size_t* num_literal_contexts, const uint32_t** literal_context_map) {
405  static const uint32_t kStaticContextMapComplexUTF8[64] = {
406  11, 11, 12, 12, /* 0 special */
407  0, 0, 0, 0, /* 4 lf */
408  1, 1, 9, 9, /* 8 space */
409  2, 2, 2, 2, /* !, first after space/lf and after something else. */
410  1, 1, 1, 1, /* " */
411  8, 3, 3, 3, /* % */
412  1, 1, 1, 1, /* ({[ */
413  2, 2, 2, 2, /* }]) */
414  8, 4, 4, 4, /* :; */
415  8, 7, 4, 4, /* . */
416  8, 0, 0, 0, /* > */
417  3, 3, 3, 3, /* [0..9] */
418  5, 5, 10, 5, /* [A-Z] */
419  5, 5, 10, 5,
420  6, 6, 6, 6, /* [a-z] */
421  6, 6, 6, 6,
422  };
424  /* Try the more complex static context map only for long data. */
425  if (size_hint < (1 << 20)) {
426  return BROTLI_FALSE;
427  } else {
428  const size_t end_pos = start_pos + length;
429  /* To make entropy calculations faster and to fit on the stack, we collect
430  histograms over the 5 most significant bits of literals. One histogram
431  without context and 13 additional histograms for each context value. */
432  uint32_t combined_histo[32] = { 0 };
433  uint32_t context_histo[13][32] = { { 0 } };
434  uint32_t total = 0;
435  double entropy[3];
436  size_t dummy;
437  size_t i;
439  for (; start_pos + 64 <= end_pos; start_pos += 4096) {
440  const size_t stride_end_pos = start_pos + 64;
441  uint8_t prev2 = input[start_pos & mask];
442  uint8_t prev1 = input[(start_pos + 1) & mask];
443  size_t pos;
444  /* To make the analysis of the data faster we only examine 64 byte long
445  strides at every 4kB intervals. */
446  for (pos = start_pos + 2; pos < stride_end_pos; ++pos) {
447  const uint8_t literal = input[pos & mask];
448  const uint8_t context = (uint8_t)kStaticContextMapComplexUTF8[
449  BROTLI_CONTEXT(prev1, prev2, utf8_lut)];
450  ++total;
451  ++combined_histo[literal >> 3];
452  ++context_histo[context][literal >> 3];
453  prev2 = prev1;
454  prev1 = literal;
455  }
456  }
457  entropy[1] = ShannonEntropy(combined_histo, 32, &dummy);
458  entropy[2] = 0;
459  for (i = 0; i < 13; ++i) {
460  entropy[2] += ShannonEntropy(&context_histo[i][0], 32, &dummy);
461  }
462  entropy[0] = 1.0 / (double)total;
463  entropy[1] *= entropy[0];
464  entropy[2] *= entropy[0];
465  /* The triggering heuristics below were tuned by compressing the individual
466  files of the silesia corpus. If we skip this kind of context modeling
467  for not very well compressible input (i.e. entropy using context modeling
468  is 60% of maximal entropy) or if expected savings by symbol are less
469  than 0.2 bits, then in every case when it triggers, the final compression
470  ratio is improved. Note however that this heuristics might be too strict
471  for some cases and could be tuned further. */
472  if (entropy[2] > 3.0 || entropy[1] - entropy[2] < 0.2) {
473  return BROTLI_FALSE;
474  } else {
475  *num_literal_contexts = 13;
476  *literal_context_map = kStaticContextMapComplexUTF8;
477  return BROTLI_TRUE;
478  }
479  }
480 }
481 
483  size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint,
484  size_t* num_literal_contexts, const uint32_t** literal_context_map) {
486  return;
488  input, start_pos, length, mask, quality, size_hint,
489  num_literal_contexts, literal_context_map)) {
490  /* Context map was already set, nothing else to do. */
491  } else {
492  /* Gather bi-gram data of the UTF8 byte prefixes. To make the analysis of
493  UTF8 data faster we only examine 64 byte long strides at every 4kB
494  intervals. */
495  const size_t end_pos = start_pos + length;
496  uint32_t bigram_prefix_histo[9] = { 0 };
497  for (; start_pos + 64 <= end_pos; start_pos += 4096) {
498  static const int lut[4] = { 0, 0, 1, 2 };
499  const size_t stride_end_pos = start_pos + 64;
500  int prev = lut[input[start_pos & mask] >> 6] * 3;
501  size_t pos;
502  for (pos = start_pos + 1; pos < stride_end_pos; ++pos) {
503  const uint8_t literal = input[pos & mask];
504  ++bigram_prefix_histo[prev + lut[literal >> 6]];
505  prev = lut[literal >> 6] * 3;
506  }
507  }
508  ChooseContextMap(quality, &bigram_prefix_histo[0], num_literal_contexts,
509  literal_context_map);
510  }
511 }
512 
514  const uint8_t* data, const size_t mask, const uint64_t last_flush_pos,
515  const size_t bytes, const size_t num_literals, const size_t num_commands) {
516  /* TODO: find more precise minimal block overhead. */
517  if (bytes <= 2) return BROTLI_FALSE;
518  if (num_commands < (bytes >> 8) + 2) {
519  if ((double)num_literals > 0.99 * (double)bytes) {
520  uint32_t literal_histo[256] = { 0 };
521  static const uint32_t kSampleRate = 13;
522  static const double kMinEntropy = 7.92;
523  const double bit_cost_threshold =
524  (double)bytes * kMinEntropy / kSampleRate;
525  size_t t = (bytes + kSampleRate - 1) / kSampleRate;
526  uint32_t pos = (uint32_t)last_flush_pos;
527  size_t i;
528  for (i = 0; i < t; i++) {
529  ++literal_histo[data[pos & mask]];
530  pos += kSampleRate;
531  }
532  if (BitsEntropy(literal_histo, 256) > bit_cost_threshold) {
533  return BROTLI_FALSE;
534  }
535  }
536  }
537  return BROTLI_TRUE;
538 }
539 
540 /* Chooses the literal context mode for a metablock */
542  const uint8_t* data, const size_t pos, const size_t mask,
543  const size_t length) {
544  /* We only do the computation for the option of something else than
545  CONTEXT_UTF8 for the highest qualities */
546  if (params->quality >= MIN_QUALITY_FOR_HQ_BLOCK_SPLITTING &&
548  return CONTEXT_SIGNED;
549  }
550  return CONTEXT_UTF8;
551 }
552 
554  const uint8_t* data,
555  const size_t mask,
556  const uint64_t last_flush_pos,
557  const size_t bytes,
558  const BROTLI_BOOL is_last,
559  ContextType literal_context_mode,
561  const uint8_t prev_byte,
562  const uint8_t prev_byte2,
563  const size_t num_literals,
564  const size_t num_commands,
565  Command* commands,
566  const int* saved_dist_cache,
567  int* dist_cache,
568  size_t* storage_ix,
569  uint8_t* storage) {
570  const uint32_t wrapped_last_flush_pos = WrapPosition(last_flush_pos);
571  uint16_t last_bytes;
572  uint8_t last_bytes_bits;
573  ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode);
574  BrotliEncoderParams block_params = *params;
575 
576  if (bytes == 0) {
577  /* Write the ISLAST and ISEMPTY bits. */
578  BrotliWriteBits(2, 3, storage_ix, storage);
579  *storage_ix = (*storage_ix + 7u) & ~7u;
580  return;
581  }
582 
583  if (!ShouldCompress(data, mask, last_flush_pos, bytes,
584  num_literals, num_commands)) {
585  /* Restore the distance cache, as its last update by
586  CreateBackwardReferences is now unused. */
587  memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0]));
589  wrapped_last_flush_pos, mask, bytes,
590  storage_ix, storage);
591  return;
592  }
593 
594  BROTLI_DCHECK(*storage_ix <= 14);
595  last_bytes = (uint16_t)((storage[1] << 8) | storage[0]);
596  last_bytes_bits = (uint8_t)(*storage_ix);
598  BrotliStoreMetaBlockFast(m, data, wrapped_last_flush_pos,
599  bytes, mask, is_last, params,
600  commands, num_commands,
601  storage_ix, storage);
602  if (BROTLI_IS_OOM(m)) return;
603  } else if (params->quality < MIN_QUALITY_FOR_BLOCK_SPLIT) {
604  BrotliStoreMetaBlockTrivial(m, data, wrapped_last_flush_pos,
605  bytes, mask, is_last, params,
606  commands, num_commands,
607  storage_ix, storage);
608  if (BROTLI_IS_OOM(m)) return;
609  } else {
610  MetaBlockSplit mb;
611  InitMetaBlockSplit(&mb);
613  size_t num_literal_contexts = 1;
614  const uint32_t* literal_context_map = NULL;
615  if (!params->disable_literal_context_modeling) {
617  data, wrapped_last_flush_pos, bytes, mask, params->quality,
618  params->size_hint, &num_literal_contexts,
619  &literal_context_map);
620  }
621  BrotliBuildMetaBlockGreedy(m, data, wrapped_last_flush_pos, mask,
622  prev_byte, prev_byte2, literal_context_lut, num_literal_contexts,
623  literal_context_map, commands, num_commands, &mb);
624  if (BROTLI_IS_OOM(m)) return;
625  } else {
626  BrotliBuildMetaBlock(m, data, wrapped_last_flush_pos, mask, &block_params,
627  prev_byte, prev_byte2,
628  commands, num_commands,
629  literal_context_mode,
630  &mb);
631  if (BROTLI_IS_OOM(m)) return;
632  }
634  /* The number of distance symbols effectively used for distance
635  histograms. It might be less than distance alphabet size
636  for "Large Window Brotli" (32-bit). */
638  }
639  BrotliStoreMetaBlock(m, data, wrapped_last_flush_pos, bytes, mask,
640  prev_byte, prev_byte2,
641  is_last,
642  &block_params,
643  literal_context_mode,
644  commands, num_commands,
645  &mb,
646  storage_ix, storage);
647  if (BROTLI_IS_OOM(m)) return;
648  DestroyMetaBlockSplit(m, &mb);
649  }
650  if (bytes + 4 < (*storage_ix >> 3)) {
651  /* Restore the distance cache and last byte. */
652  memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0]));
653  storage[0] = (uint8_t)last_bytes;
654  storage[1] = (uint8_t)(last_bytes >> 8);
655  *storage_ix = last_bytes_bits;
657  wrapped_last_flush_pos, mask,
658  bytes, storage_ix, storage);
659  }
660 }
661 
663  uint32_t distance_postfix_bits = 0;
664  uint32_t num_direct_distance_codes = 0;
665 
667  uint32_t ndirect_msb;
668  if (params->mode == BROTLI_MODE_FONT) {
669  distance_postfix_bits = 1;
670  num_direct_distance_codes = 12;
671  } else {
672  distance_postfix_bits = params->dist.distance_postfix_bits;
673  num_direct_distance_codes = params->dist.num_direct_distance_codes;
674  }
675  ndirect_msb = (num_direct_distance_codes >> distance_postfix_bits) & 0x0F;
676  if (distance_postfix_bits > BROTLI_MAX_NPOSTFIX ||
677  num_direct_distance_codes > BROTLI_MAX_NDIRECT ||
678  (ndirect_msb << distance_postfix_bits) != num_direct_distance_codes) {
679  distance_postfix_bits = 0;
680  num_direct_distance_codes = 0;
681  }
682  }
683 
685  params, distance_postfix_bits, num_direct_distance_codes);
686 }
687 
689  if (BROTLI_IS_OOM(&s->memory_manager_)) return BROTLI_FALSE;
690  if (s->is_initialized_) return BROTLI_TRUE;
691 
692  s->last_bytes_bits_ = 0;
693  s->last_bytes_ = 0;
694  s->flint_ = BROTLI_FLINT_DONE;
695  s->remaining_metadata_bytes_ = BROTLI_UINT32_MAX;
696 
697  SanitizeParams(&s->params);
698  s->params.lgblock = ComputeLgBlock(&s->params);
699  ChooseDistanceParams(&s->params);
700 
701  if (s->params.stream_offset != 0) {
702  s->flint_ = BROTLI_FLINT_NEEDS_2_BYTES;
703  /* Poison the distance cache. -16 +- 3 is still less than zero (invalid). */
704  s->dist_cache_[0] = -16;
705  s->dist_cache_[1] = -16;
706  s->dist_cache_[2] = -16;
707  s->dist_cache_[3] = -16;
708  memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_));
709  }
710 
711  RingBufferSetup(&s->params, &s->ringbuffer_);
712 
713  /* Initialize last byte with stream header. */
714  {
715  int lgwin = s->params.lgwin;
716  if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY ||
717  s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) {
718  lgwin = BROTLI_MAX(int, lgwin, 18);
719  }
720  if (s->params.stream_offset == 0) {
721  EncodeWindowBits(lgwin, s->params.large_window,
722  &s->last_bytes_, &s->last_bytes_bits_);
723  } else {
724  /* Bigger values have the same effect, but could cause overflows. */
725  s->params.stream_offset = BROTLI_MIN(size_t,
726  s->params.stream_offset, BROTLI_MAX_BACKWARD_LIMIT(lgwin));
727  }
728  }
729 
730  if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) {
731  InitCommandPrefixCodes(s->cmd_depths_, s->cmd_bits_,
732  s->cmd_code_, &s->cmd_code_numbits_);
733  }
734 
735  s->is_initialized_ = BROTLI_TRUE;
736  return BROTLI_TRUE;
737 }
738 
740  params->mode = BROTLI_DEFAULT_MODE;
741  params->large_window = BROTLI_FALSE;
742  params->quality = BROTLI_DEFAULT_QUALITY;
743  params->lgwin = BROTLI_DEFAULT_WINDOW;
744  params->lgblock = 0;
745  params->stream_offset = 0;
746  params->size_hint = 0;
747  params->disable_literal_context_modeling = BROTLI_FALSE;
748  BrotliInitEncoderDictionary(&params->dictionary);
749  params->dist.distance_postfix_bits = 0;
750  params->dist.num_direct_distance_codes = 0;
751  params->dist.alphabet_size_max =
753  params->dist.alphabet_size_limit = params->dist.alphabet_size_max;
754  params->dist.max_distance = BROTLI_MAX_DISTANCE;
755 }
756 
758  BrotliEncoderInitParams(&s->params);
759  s->input_pos_ = 0;
760  s->num_commands_ = 0;
761  s->num_literals_ = 0;
762  s->last_insert_len_ = 0;
763  s->last_flush_pos_ = 0;
764  s->last_processed_pos_ = 0;
765  s->prev_byte_ = 0;
766  s->prev_byte2_ = 0;
767  s->storage_size_ = 0;
768  s->storage_ = 0;
769  HasherInit(&s->hasher_);
770  s->large_table_ = NULL;
771  s->large_table_size_ = 0;
772  s->cmd_code_numbits_ = 0;
773  s->command_buf_ = NULL;
774  s->literal_buf_ = NULL;
775  s->next_out_ = NULL;
776  s->available_out_ = 0;
777  s->total_out_ = 0;
778  s->stream_state_ = BROTLI_STREAM_PROCESSING;
779  s->is_last_block_emitted_ = BROTLI_FALSE;
780  s->is_initialized_ = BROTLI_FALSE;
781 
782  RingBufferInit(&s->ringbuffer_);
783 
784  s->commands_ = 0;
785  s->cmd_alloc_size_ = 0;
786 
787  /* Initialize distance cache. */
788  s->dist_cache_[0] = 4;
789  s->dist_cache_[1] = 11;
790  s->dist_cache_[2] = 15;
791  s->dist_cache_[3] = 16;
792  /* Save the state of the distance cache in case we need to restore it for
793  emitting an uncompressed block. */
794  memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_));
795 }
796 
800  if (!alloc_func && !free_func) {
802  } else if (alloc_func && free_func) {
804  }
805  if (state == 0) {
806  /* BROTLI_DUMP(); */
807  return 0;
808  }
810  &state->memory_manager_, alloc_func, free_func, opaque);
812  return state;
813 }
814 
816  MemoryManager* m = &s->memory_manager_;
817  if (BROTLI_IS_OOM(m)) {
819  return;
820  }
821  BROTLI_FREE(m, s->storage_);
822  BROTLI_FREE(m, s->commands_);
823  RingBufferFree(m, &s->ringbuffer_);
824  DestroyHasher(m, &s->hasher_);
825  BROTLI_FREE(m, s->large_table_);
826  BROTLI_FREE(m, s->command_buf_);
827  BROTLI_FREE(m, s->literal_buf_);
828 }
829 
830 /* Deinitializes and frees BrotliEncoderState instance. */
832  if (!state) {
833  return;
834  } else {
835  MemoryManager* m = &state->memory_manager_;
836  brotli_free_func free_func = m->free_func;
837  void* opaque = m->opaque;
839  free_func(opaque, state);
840  }
841 }
842 
843 /*
844  Copies the given input data to the internal ring buffer of the compressor.
845  No processing of the data occurs at this time and this function can be
846  called multiple times before calling WriteBrotliData() to process the
847  accumulated input. At most input_block_size() bytes of input data can be
848  copied to the ring buffer, otherwise the next WriteBrotliData() will fail.
849  */
851  const size_t input_size,
852  const uint8_t* input_buffer) {
853  RingBuffer* ringbuffer_ = &s->ringbuffer_;
854  MemoryManager* m = &s->memory_manager_;
855  RingBufferWrite(m, input_buffer, input_size, ringbuffer_);
856  if (BROTLI_IS_OOM(m)) return;
857  s->input_pos_ += input_size;
858 
859  /* TL;DR: If needed, initialize 7 more bytes in the ring buffer to make the
860  hashing not depend on uninitialized data. This makes compression
861  deterministic and it prevents uninitialized memory warnings in Valgrind.
862  Even without erasing, the output would be valid (but nondeterministic).
863 
864  Background information: The compressor stores short (at most 8 bytes)
865  substrings of the input already read in a hash table, and detects
866  repetitions by looking up such substrings in the hash table. If it
867  can find a substring, it checks whether the substring is really there
868  in the ring buffer (or it's just a hash collision). Should the hash
869  table become corrupt, this check makes sure that the output is
870  still valid, albeit the compression ratio would be bad.
871 
872  The compressor populates the hash table from the ring buffer as it's
873  reading new bytes from the input. However, at the last few indexes of
874  the ring buffer, there are not enough bytes to build full-length
875  substrings from. Since the hash table always contains full-length
876  substrings, we erase with dummy zeros here to make sure that those
877  substrings will contain zeros at the end instead of uninitialized
878  data.
879 
880  Please note that erasing is not necessary (because the
881  memory region is already initialized since he ring buffer
882  has a `tail' that holds a copy of the beginning,) so we
883  skip erasing if we have already gone around at least once in
884  the ring buffer.
885 
886  Only clear during the first round of ring-buffer writes. On
887  subsequent rounds data in the ring-buffer would be affected. */
888  if (ringbuffer_->pos_ <= ringbuffer_->mask_) {
889  /* This is the first time when the ring buffer is being written.
890  We clear 7 bytes just after the bytes that have been copied from
891  the input buffer.
892 
893  The ring-buffer has a "tail" that holds a copy of the beginning,
894  but only once the ring buffer has been fully written once, i.e.,
895  pos <= mask. For the first time, we need to write values
896  in this tail (where index may be larger than mask), so that
897  we have exactly defined behavior and don't read uninitialized
898  memory. Due to performance reasons, hashing reads data using a
899  LOAD64, which can go 7 bytes beyond the bytes written in the
900  ring-buffer. */
901  memset(ringbuffer_->buffer_ + ringbuffer_->pos_, 0, 7);
902  }
903 }
904 
905 /* Marks all input as processed.
906  Returns true if position wrapping occurs. */
908  uint32_t wrapped_last_processed_pos = WrapPosition(s->last_processed_pos_);
909  uint32_t wrapped_input_pos = WrapPosition(s->input_pos_);
910  s->last_processed_pos_ = s->input_pos_;
911  return TO_BROTLI_BOOL(wrapped_input_pos < wrapped_last_processed_pos);
912 }
913 
915  uint32_t* wrapped_last_processed_pos) {
916  Command* last_command = &s->commands_[s->num_commands_ - 1];
917  const uint8_t* data = s->ringbuffer_.buffer_;
918  const uint32_t mask = s->ringbuffer_.mask_;
919  uint64_t max_backward_distance =
920  (((uint64_t)1) << s->params.lgwin) - BROTLI_WINDOW_GAP;
921  uint64_t last_copy_len = last_command->copy_len_ & 0x1FFFFFF;
922  uint64_t last_processed_pos = s->last_processed_pos_ - last_copy_len;
923  uint64_t max_distance = last_processed_pos < max_backward_distance ?
924  last_processed_pos : max_backward_distance;
925  uint64_t cmd_dist = (uint64_t)s->dist_cache_[0];
926  uint32_t distance_code = CommandRestoreDistanceCode(last_command,
927  &s->params.dist);
928  if (distance_code < BROTLI_NUM_DISTANCE_SHORT_CODES ||
929  distance_code - (BROTLI_NUM_DISTANCE_SHORT_CODES - 1) == cmd_dist) {
930  if (cmd_dist <= max_distance) {
931  while (*bytes != 0 && data[*wrapped_last_processed_pos & mask] ==
932  data[(*wrapped_last_processed_pos - cmd_dist) & mask]) {
933  last_command->copy_len_++;
934  (*bytes)--;
935  (*wrapped_last_processed_pos)++;
936  }
937  } else {
938  }
939  /* The copy length is at most the metablock size, and thus expressible. */
940  GetLengthCode(last_command->insert_len_,
941  (size_t)((int)(last_command->copy_len_ & 0x1FFFFFF) +
942  (int)(last_command->copy_len_ >> 25)),
943  TO_BROTLI_BOOL((last_command->dist_prefix_ & 0x3FF) == 0),
944  &last_command->cmd_prefix_);
945  }
946 }
947 
948 /*
949  Processes the accumulated input data and sets |*out_size| to the length of
950  the new output meta-block, or to zero if no new output meta-block has been
951  created (in this case the processed input data is buffered internally).
952  If |*out_size| is positive, |*output| points to the start of the output
953  data. If |is_last| or |force_flush| is BROTLI_TRUE, an output meta-block is
954  always created. However, until |is_last| is BROTLI_TRUE encoder may retain up
955  to 7 bits of the last byte of output. To force encoder to dump the remaining
956  bits use WriteMetadata() to append an empty meta-data block.
957  Returns BROTLI_FALSE if the size of the input data is larger than
958  input_block_size().
959  */
961  BrotliEncoderState* s, const BROTLI_BOOL is_last,
962  const BROTLI_BOOL force_flush, size_t* out_size, uint8_t** output) {
965  uint32_t wrapped_last_processed_pos = WrapPosition(s->last_processed_pos_);
966  uint8_t* data;
967  uint32_t mask;
968  MemoryManager* m = &s->memory_manager_;
969  ContextType literal_context_mode;
970  ContextLut literal_context_lut;
971 
972  data = s->ringbuffer_.buffer_;
973  mask = s->ringbuffer_.mask_;
974 
975  /* Adding more blocks after "last" block is forbidden. */
976  if (s->is_last_block_emitted_) return BROTLI_FALSE;
977  if (is_last) s->is_last_block_emitted_ = BROTLI_TRUE;
978 
979  if (delta > InputBlockSize(s)) {
980  return BROTLI_FALSE;
981  }
982  if (s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY &&
983  !s->command_buf_) {
984  s->command_buf_ =
986  s->literal_buf_ =
988  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(s->command_buf_) ||
989  BROTLI_IS_NULL(s->literal_buf_)) {
990  return BROTLI_FALSE;
991  }
992  }
993 
994  if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY ||
995  s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) {
996  uint8_t* storage;
997  size_t storage_ix = s->last_bytes_bits_;
998  size_t table_size;
999  int* table;
1000 
1001  if (delta == 0 && !is_last) {
1002  /* We have no new input data and we don't have to finish the stream, so
1003  nothing to do. */
1004  *out_size = 0;
1005  return BROTLI_TRUE;
1006  }
1007  storage = GetBrotliStorage(s, 2 * bytes + 503);
1008  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1009  storage[0] = (uint8_t)s->last_bytes_;
1010  storage[1] = (uint8_t)(s->last_bytes_ >> 8);
1011  table = GetHashTable(s, s->params.quality, bytes, &table_size);
1012  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1013  if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) {
1015  m, &data[wrapped_last_processed_pos & mask],
1016  bytes, is_last,
1017  table, table_size,
1018  s->cmd_depths_, s->cmd_bits_,
1019  &s->cmd_code_numbits_, s->cmd_code_,
1020  &storage_ix, storage);
1021  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1022  } else {
1024  m, &data[wrapped_last_processed_pos & mask],
1025  bytes, is_last,
1026  s->command_buf_, s->literal_buf_,
1027  table, table_size,
1028  &storage_ix, storage);
1029  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1030  }
1031  s->last_bytes_ = (uint16_t)(storage[storage_ix >> 3]);
1032  s->last_bytes_bits_ = storage_ix & 7u;
1034  *output = &storage[0];
1035  *out_size = storage_ix >> 3;
1036  return BROTLI_TRUE;
1037  }
1038 
1039  {
1040  /* Theoretical max number of commands is 1 per 2 bytes. */
1041  size_t newsize = s->num_commands_ + bytes / 2 + 1;
1042  if (newsize > s->cmd_alloc_size_) {
1043  Command* new_commands;
1044  /* Reserve a bit more memory to allow merging with a next block
1045  without reallocation: that would impact speed. */
1046  newsize += (bytes / 4) + 16;
1047  s->cmd_alloc_size_ = newsize;
1048  new_commands = BROTLI_ALLOC(m, Command, newsize);
1049  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_commands)) return BROTLI_FALSE;
1050  if (s->commands_) {
1051  memcpy(new_commands, s->commands_, sizeof(Command) * s->num_commands_);
1052  BROTLI_FREE(m, s->commands_);
1053  }
1054  s->commands_ = new_commands;
1055  }
1056  }
1057 
1058  InitOrStitchToPreviousBlock(m, &s->hasher_, data, mask, &s->params,
1059  wrapped_last_processed_pos, bytes, is_last);
1060 
1061  literal_context_mode = ChooseContextMode(
1062  &s->params, data, WrapPosition(s->last_flush_pos_),
1063  mask, (size_t)(s->input_pos_ - s->last_flush_pos_));
1064  literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode);
1065 
1066  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1067 
1068  if (s->num_commands_ && s->last_insert_len_ == 0) {
1069  ExtendLastCommand(s, &bytes, &wrapped_last_processed_pos);
1070  }
1071 
1072  if (s->params.quality == ZOPFLIFICATION_QUALITY) {
1073  BROTLI_DCHECK(s->params.hasher.type == 10);
1074  BrotliCreateZopfliBackwardReferences(m, bytes, wrapped_last_processed_pos,
1075  data, mask, literal_context_lut, &s->params,
1076  &s->hasher_, s->dist_cache_,
1077  &s->last_insert_len_, &s->commands_[s->num_commands_],
1078  &s->num_commands_, &s->num_literals_);
1079  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1080  } else if (s->params.quality == HQ_ZOPFLIFICATION_QUALITY) {
1081  BROTLI_DCHECK(s->params.hasher.type == 10);
1082  BrotliCreateHqZopfliBackwardReferences(m, bytes, wrapped_last_processed_pos,
1083  data, mask, literal_context_lut, &s->params,
1084  &s->hasher_, s->dist_cache_,
1085  &s->last_insert_len_, &s->commands_[s->num_commands_],
1086  &s->num_commands_, &s->num_literals_);
1087  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1088  } else {
1089  BrotliCreateBackwardReferences(bytes, wrapped_last_processed_pos,
1090  data, mask, literal_context_lut, &s->params,
1091  &s->hasher_, s->dist_cache_,
1092  &s->last_insert_len_, &s->commands_[s->num_commands_],
1093  &s->num_commands_, &s->num_literals_);
1094  }
1095 
1096  {
1097  const size_t max_length = MaxMetablockSize(&s->params);
1098  const size_t max_literals = max_length / 8;
1099  const size_t max_commands = max_length / 8;
1100  const size_t processed_bytes = (size_t)(s->input_pos_ - s->last_flush_pos_);
1101  /* If maximal possible additional block doesn't fit metablock, flush now. */
1102  /* TODO: Postpone decision until next block arrives? */
1103  const BROTLI_BOOL next_input_fits_metablock = TO_BROTLI_BOOL(
1104  processed_bytes + InputBlockSize(s) <= max_length);
1105  /* If block splitting is not used, then flush as soon as there is some
1106  amount of commands / literals produced. */
1107  const BROTLI_BOOL should_flush = TO_BROTLI_BOOL(
1108  s->params.quality < MIN_QUALITY_FOR_BLOCK_SPLIT &&
1109  s->num_literals_ + s->num_commands_ >= MAX_NUM_DELAYED_SYMBOLS);
1110  if (!is_last && !force_flush && !should_flush &&
1111  next_input_fits_metablock &&
1112  s->num_literals_ < max_literals &&
1113  s->num_commands_ < max_commands) {
1114  /* Merge with next input block. Everything will happen later. */
1115  if (UpdateLastProcessedPos(s)) {
1116  HasherReset(&s->hasher_);
1117  }
1118  *out_size = 0;
1119  return BROTLI_TRUE;
1120  }
1121  }
1122 
1123  /* Create the last insert-only command. */
1124  if (s->last_insert_len_ > 0) {
1125  InitInsertCommand(&s->commands_[s->num_commands_++], s->last_insert_len_);
1126  s->num_literals_ += s->last_insert_len_;
1127  s->last_insert_len_ = 0;
1128  }
1129 
1130  if (!is_last && s->input_pos_ == s->last_flush_pos_) {
1131  /* We have no new input data and we don't have to finish the stream, so
1132  nothing to do. */
1133  *out_size = 0;
1134  return BROTLI_TRUE;
1135  }
1136  BROTLI_DCHECK(s->input_pos_ >= s->last_flush_pos_);
1137  BROTLI_DCHECK(s->input_pos_ > s->last_flush_pos_ || is_last);
1138  BROTLI_DCHECK(s->input_pos_ - s->last_flush_pos_ <= 1u << 24);
1139  {
1140  const uint32_t metablock_size =
1141  (uint32_t)(s->input_pos_ - s->last_flush_pos_);
1142  uint8_t* storage = GetBrotliStorage(s, 2 * metablock_size + 503);
1143  size_t storage_ix = s->last_bytes_bits_;
1144  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1145  storage[0] = (uint8_t)s->last_bytes_;
1146  storage[1] = (uint8_t)(s->last_bytes_ >> 8);
1148  m, data, mask, s->last_flush_pos_, metablock_size, is_last,
1149  literal_context_mode, &s->params, s->prev_byte_, s->prev_byte2_,
1150  s->num_literals_, s->num_commands_, s->commands_, s->saved_dist_cache_,
1151  s->dist_cache_, &storage_ix, storage);
1152  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1153  s->last_bytes_ = (uint16_t)(storage[storage_ix >> 3]);
1154  s->last_bytes_bits_ = storage_ix & 7u;
1155  s->last_flush_pos_ = s->input_pos_;
1156  if (UpdateLastProcessedPos(s)) {
1157  HasherReset(&s->hasher_);
1158  }
1159  if (s->last_flush_pos_ > 0) {
1160  s->prev_byte_ = data[((uint32_t)s->last_flush_pos_ - 1) & mask];
1161  }
1162  if (s->last_flush_pos_ > 1) {
1163  s->prev_byte2_ = data[(uint32_t)(s->last_flush_pos_ - 2) & mask];
1164  }
1165  s->num_commands_ = 0;
1166  s->num_literals_ = 0;
1167  /* Save the state of the distance cache in case we need to restore it for
1168  emitting an uncompressed block. */
1169  memcpy(s->saved_dist_cache_, s->dist_cache_, sizeof(s->saved_dist_cache_));
1170  *output = &storage[0];
1171  *out_size = storage_ix >> 3;
1172  return BROTLI_TRUE;
1173  }
1174 }
1175 
1176 /* Dumps remaining output bits and metadata header to |header|.
1177  Returns number of produced bytes.
1178  REQUIRED: |header| should be 8-byte aligned and at least 16 bytes long.
1179  REQUIRED: |block_size| <= (1 << 24). */
1180 static size_t WriteMetadataHeader(
1181  BrotliEncoderState* s, const size_t block_size, uint8_t* header) {
1182  size_t storage_ix;
1183  storage_ix = s->last_bytes_bits_;
1184  header[0] = (uint8_t)s->last_bytes_;
1185  header[1] = (uint8_t)(s->last_bytes_ >> 8);
1186  s->last_bytes_ = 0;
1187  s->last_bytes_bits_ = 0;
1188 
1189  BrotliWriteBits(1, 0, &storage_ix, header);
1190  BrotliWriteBits(2, 3, &storage_ix, header);
1191  BrotliWriteBits(1, 0, &storage_ix, header);
1192  if (block_size == 0) {
1193  BrotliWriteBits(2, 0, &storage_ix, header);
1194  } else {
1195  uint32_t nbits = (block_size == 1) ? 0 :
1196  (Log2FloorNonZero((uint32_t)block_size - 1) + 1);
1197  uint32_t nbytes = (nbits + 7) / 8;
1198  BrotliWriteBits(2, nbytes, &storage_ix, header);
1199  BrotliWriteBits(8 * nbytes, block_size - 1, &storage_ix, header);
1200  }
1201  return (storage_ix + 7u) >> 3;
1202 }
1203 
1205  int lgwin, size_t input_size, const uint8_t* input_buffer,
1206  size_t* encoded_size, uint8_t* encoded_buffer) {
1207  MemoryManager memory_manager;
1208  MemoryManager* m = &memory_manager;
1209 
1210  const size_t mask = BROTLI_SIZE_MAX >> 1;
1211  int dist_cache[4] = { 4, 11, 15, 16 };
1212  int saved_dist_cache[4] = { 4, 11, 15, 16 };
1213  BROTLI_BOOL ok = BROTLI_TRUE;
1214  const size_t max_out_size = *encoded_size;
1215  size_t total_out_size = 0;
1216  uint16_t last_bytes;
1217  uint8_t last_bytes_bits;
1218 
1219  const size_t hasher_eff_size = BROTLI_MIN(size_t,
1220  input_size, BROTLI_MAX_BACKWARD_LIMIT(lgwin) + BROTLI_WINDOW_GAP);
1221 
1223 
1224  const int lgmetablock = BROTLI_MIN(int, 24, lgwin + 1);
1225  size_t max_block_size;
1226  const size_t max_metablock_size = (size_t)1 << lgmetablock;
1227  const size_t max_literals_per_metablock = max_metablock_size / 8;
1228  const size_t max_commands_per_metablock = max_metablock_size / 8;
1229  size_t metablock_start = 0;
1230  uint8_t prev_byte = 0;
1231  uint8_t prev_byte2 = 0;
1232 
1233  Hasher hasher;
1234  HasherInit(&hasher);
1235 
1237  params.quality = 10;
1238  params.lgwin = lgwin;
1239  if (lgwin > BROTLI_MAX_WINDOW_BITS) {
1240  params.large_window = BROTLI_TRUE;
1241  }
1243  params.lgblock = ComputeLgBlock(&params);
1245  max_block_size = (size_t)1 << params.lgblock;
1246 
1247  BrotliInitMemoryManager(m, 0, 0, 0);
1248 
1249  BROTLI_DCHECK(input_size <= mask + 1);
1250  EncodeWindowBits(lgwin, params.large_window, &last_bytes, &last_bytes_bits);
1251  InitOrStitchToPreviousBlock(m, &hasher, input_buffer, mask, &params,
1252  0, hasher_eff_size, BROTLI_TRUE);
1253  if (BROTLI_IS_OOM(m)) goto oom;
1254 
1255  while (ok && metablock_start < input_size) {
1256  const size_t metablock_end =
1257  BROTLI_MIN(size_t, input_size, metablock_start + max_metablock_size);
1258  const size_t expected_num_commands =
1259  (metablock_end - metablock_start) / 12 + 16;
1260  Command* commands = 0;
1261  size_t num_commands = 0;
1262  size_t last_insert_len = 0;
1263  size_t num_literals = 0;
1264  size_t metablock_size = 0;
1265  size_t cmd_alloc_size = 0;
1266  BROTLI_BOOL is_last;
1267  uint8_t* storage;
1268  size_t storage_ix;
1269 
1270  ContextType literal_context_mode = ChooseContextMode(&params,
1271  input_buffer, metablock_start, mask, metablock_end - metablock_start);
1272  ContextLut literal_context_lut = BROTLI_CONTEXT_LUT(literal_context_mode);
1273 
1274  size_t block_start;
1275  for (block_start = metablock_start; block_start < metablock_end; ) {
1276  size_t block_size =
1277  BROTLI_MIN(size_t, metablock_end - block_start, max_block_size);
1278  ZopfliNode* nodes = BROTLI_ALLOC(m, ZopfliNode, block_size + 1);
1279  size_t path_size;
1280  size_t new_cmd_alloc_size;
1281  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(nodes)) goto oom;
1282  BrotliInitZopfliNodes(nodes, block_size + 1);
1283  StitchToPreviousBlockH10(&hasher.privat._H10, block_size, block_start,
1284  input_buffer, mask);
1286  input_buffer, mask, literal_context_lut, &params, dist_cache, &hasher,
1287  nodes);
1288  if (BROTLI_IS_OOM(m)) goto oom;
1289  /* We allocate a command buffer in the first iteration of this loop that
1290  will be likely big enough for the whole metablock, so that for most
1291  inputs we will not have to reallocate in later iterations. We do the
1292  allocation here and not before the loop, because if the input is small,
1293  this will be allocated after the Zopfli cost model is freed, so this
1294  will not increase peak memory usage.
1295  TODO: If the first allocation is too small, increase command
1296  buffer size exponentially. */
1297  new_cmd_alloc_size = BROTLI_MAX(size_t, expected_num_commands,
1298  num_commands + path_size + 1);
1299  if (cmd_alloc_size != new_cmd_alloc_size) {
1300  Command* new_commands = BROTLI_ALLOC(m, Command, new_cmd_alloc_size);
1301  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(new_commands)) goto oom;
1302  cmd_alloc_size = new_cmd_alloc_size;
1303  if (commands) {
1304  memcpy(new_commands, commands, sizeof(Command) * num_commands);
1306  }
1307  commands = new_commands;
1308  }
1309  BrotliZopfliCreateCommands(block_size, block_start, &nodes[0], dist_cache,
1310  &last_insert_len, &params, &commands[num_commands], &num_literals);
1311  num_commands += path_size;
1313  metablock_size += block_size;
1314  BROTLI_FREE(m, nodes);
1315  if (num_literals > max_literals_per_metablock ||
1316  num_commands > max_commands_per_metablock) {
1317  break;
1318  }
1319  }
1320 
1321  if (last_insert_len > 0) {
1322  InitInsertCommand(&commands[num_commands++], last_insert_len);
1323  num_literals += last_insert_len;
1324  }
1325 
1326  is_last = TO_BROTLI_BOOL(metablock_start + metablock_size == input_size);
1327  storage = NULL;
1328  storage_ix = last_bytes_bits;
1329 
1330  if (metablock_size == 0) {
1331  /* Write the ISLAST and ISEMPTY bits. */
1332  storage = BROTLI_ALLOC(m, uint8_t, 16);
1333  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom;
1334  storage[0] = (uint8_t)last_bytes;
1335  storage[1] = (uint8_t)(last_bytes >> 8);
1336  BrotliWriteBits(2, 3, &storage_ix, storage);
1337  storage_ix = (storage_ix + 7u) & ~7u;
1338  } else if (!ShouldCompress(input_buffer, mask, metablock_start,
1339  metablock_size, num_literals, num_commands)) {
1340  /* Restore the distance cache, as its last update by
1341  CreateBackwardReferences is now unused. */
1342  memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0]));
1343  storage = BROTLI_ALLOC(m, uint8_t, metablock_size + 16);
1344  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom;
1345  storage[0] = (uint8_t)last_bytes;
1346  storage[1] = (uint8_t)(last_bytes >> 8);
1347  BrotliStoreUncompressedMetaBlock(is_last, input_buffer,
1348  metablock_start, mask, metablock_size,
1349  &storage_ix, storage);
1350  } else {
1351  MetaBlockSplit mb;
1352  BrotliEncoderParams block_params = params;
1353  InitMetaBlockSplit(&mb);
1354  BrotliBuildMetaBlock(m, input_buffer, metablock_start, mask,
1355  &block_params,
1356  prev_byte, prev_byte2,
1357  commands, num_commands,
1358  literal_context_mode,
1359  &mb);
1360  if (BROTLI_IS_OOM(m)) goto oom;
1361  {
1362  /* The number of distance symbols effectively used for distance
1363  histograms. It might be less than distance alphabet size
1364  for "Large Window Brotli" (32-bit). */
1366  }
1367  storage = BROTLI_ALLOC(m, uint8_t, 2 * metablock_size + 503);
1368  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(storage)) goto oom;
1369  storage[0] = (uint8_t)last_bytes;
1370  storage[1] = (uint8_t)(last_bytes >> 8);
1371  BrotliStoreMetaBlock(m, input_buffer, metablock_start, metablock_size,
1372  mask, prev_byte, prev_byte2,
1373  is_last,
1374  &block_params,
1375  literal_context_mode,
1376  commands, num_commands,
1377  &mb,
1378  &storage_ix, storage);
1379  if (BROTLI_IS_OOM(m)) goto oom;
1380  if (metablock_size + 4 < (storage_ix >> 3)) {
1381  /* Restore the distance cache and last byte. */
1382  memcpy(dist_cache, saved_dist_cache, 4 * sizeof(dist_cache[0]));
1383  storage[0] = (uint8_t)last_bytes;
1384  storage[1] = (uint8_t)(last_bytes >> 8);
1385  storage_ix = last_bytes_bits;
1386  BrotliStoreUncompressedMetaBlock(is_last, input_buffer,
1387  metablock_start, mask,
1388  metablock_size, &storage_ix, storage);
1389  }
1390  DestroyMetaBlockSplit(m, &mb);
1391  }
1392  last_bytes = (uint16_t)(storage[storage_ix >> 3]);
1393  last_bytes_bits = storage_ix & 7u;
1394  metablock_start += metablock_size;
1395  if (metablock_start < input_size) {
1396  prev_byte = input_buffer[metablock_start - 1];
1397  prev_byte2 = input_buffer[metablock_start - 2];
1398  }
1399  /* Save the state of the distance cache in case we need to restore it for
1400  emitting an uncompressed block. */
1401  memcpy(saved_dist_cache, dist_cache, 4 * sizeof(dist_cache[0]));
1402 
1403  {
1404  const size_t out_size = storage_ix >> 3;
1405  total_out_size += out_size;
1406  if (total_out_size <= max_out_size) {
1407  memcpy(encoded_buffer, storage, out_size);
1408  encoded_buffer += out_size;
1409  } else {
1410  ok = BROTLI_FALSE;
1411  }
1412  }
1413  BROTLI_FREE(m, storage);
1415  }
1416 
1417  *encoded_size = total_out_size;
1418  DestroyHasher(m, &hasher);
1419  return ok;
1420 
1421 oom:
1423  return BROTLI_FALSE;
1424 }
1425 
1426 size_t BrotliEncoderMaxCompressedSize(size_t input_size) {
1427  /* [window bits / empty metadata] + N * [uncompressed] + [last empty] */
1428  size_t num_large_blocks = input_size >> 14;
1429  size_t overhead = 2 + (4 * num_large_blocks) + 3 + 1;
1430  size_t result = input_size + overhead;
1431  if (input_size == 0) return 2;
1432  return (result < input_size) ? 0 : result;
1433 }
1434 
1435 /* Wraps data to uncompressed brotli stream with minimal window size.
1436  |output| should point at region with at least BrotliEncoderMaxCompressedSize
1437  addressable bytes.
1438  Returns the length of stream. */
1440  const uint8_t* input, size_t input_size, uint8_t* output) {
1441  size_t size = input_size;
1442  size_t result = 0;
1443  size_t offset = 0;
1444  if (input_size == 0) {
1445  output[0] = 6;
1446  return 1;
1447  }
1448  output[result++] = 0x21; /* window bits = 10, is_last = false */
1449  output[result++] = 0x03; /* empty metadata, padding */
1450  while (size > 0) {
1451  uint32_t nibbles = 0;
1453  uint32_t bits;
1454  chunk_size = (size > (1u << 24)) ? (1u << 24) : (uint32_t)size;
1455  if (chunk_size > (1u << 16)) nibbles = (chunk_size > (1u << 20)) ? 2 : 1;
1456  bits =
1457  (nibbles << 1) | ((chunk_size - 1) << 3) | (1u << (19 + 4 * nibbles));
1458  output[result++] = (uint8_t)bits;
1459  output[result++] = (uint8_t)(bits >> 8);
1460  output[result++] = (uint8_t)(bits >> 16);
1461  if (nibbles == 2) output[result++] = (uint8_t)(bits >> 24);
1463  result += chunk_size;
1464  offset += chunk_size;
1465  size -= chunk_size;
1466  }
1467  output[result++] = 3;
1468  return result;
1469 }
1470 
1472  int quality, int lgwin, BrotliEncoderMode mode, size_t input_size,
1473  const uint8_t* input_buffer, size_t* encoded_size,
1474  uint8_t* encoded_buffer) {
1476  size_t out_size = *encoded_size;
1477  const uint8_t* input_start = input_buffer;
1478  uint8_t* output_start = encoded_buffer;
1479  size_t max_out_size = BrotliEncoderMaxCompressedSize(input_size);
1480  if (out_size == 0) {
1481  /* Output buffer needs at least one byte. */
1482  return BROTLI_FALSE;
1483  }
1484  if (input_size == 0) {
1485  /* Handle the special case of empty input. */
1486  *encoded_size = 1;
1487  *encoded_buffer = 6;
1488  return BROTLI_TRUE;
1489  }
1490  if (quality == 10) {
1491  /* TODO: Implement this direct path for all quality levels. */
1492  const int lg_win = BROTLI_MIN(int, BROTLI_LARGE_MAX_WINDOW_BITS,
1493  BROTLI_MAX(int, 16, lgwin));
1494  int ok = BrotliCompressBufferQuality10(lg_win, input_size, input_buffer,
1495  encoded_size, encoded_buffer);
1496  if (!ok || (max_out_size && *encoded_size > max_out_size)) {
1497  goto fallback;
1498  }
1499  return BROTLI_TRUE;
1500  }
1501 
1502  s = BrotliEncoderCreateInstance(0, 0, 0);
1503  if (!s) {
1504  return BROTLI_FALSE;
1505  } else {
1506  size_t available_in = input_size;
1507  const uint8_t* next_in = input_buffer;
1508  size_t available_out = *encoded_size;
1509  uint8_t* next_out = encoded_buffer;
1510  size_t total_out = 0;
1516  if (lgwin > BROTLI_MAX_WINDOW_BITS) {
1518  }
1520  &available_in, &next_in, &available_out, &next_out, &total_out);
1521  if (!BrotliEncoderIsFinished(s)) result = 0;
1522  *encoded_size = total_out;
1524  if (!result || (max_out_size && *encoded_size > max_out_size)) {
1525  goto fallback;
1526  }
1527  return BROTLI_TRUE;
1528  }
1529 fallback:
1530  *encoded_size = 0;
1531  if (!max_out_size) return BROTLI_FALSE;
1532  if (out_size >= max_out_size) {
1533  *encoded_size =
1534  MakeUncompressedStream(input_start, input_size, output_start);
1535  return BROTLI_TRUE;
1536  }
1537  return BROTLI_FALSE;
1538 }
1539 
1541  uint32_t seal = s->last_bytes_;
1542  size_t seal_bits = s->last_bytes_bits_;
1543  uint8_t* destination;
1544  s->last_bytes_ = 0;
1545  s->last_bytes_bits_ = 0;
1546  /* is_last = 0, data_nibbles = 11, reserved = 0, meta_nibbles = 00 */
1547  seal |= 0x6u << seal_bits;
1548  seal_bits += 6;
1549  /* If we have already created storage, then append to it.
1550  Storage is valid until next block is being compressed. */
1551  if (s->next_out_) {
1552  destination = s->next_out_ + s->available_out_;
1553  } else {
1554  destination = s->tiny_buf_.u8;
1555  s->next_out_ = destination;
1556  }
1557  destination[0] = (uint8_t)seal;
1558  if (seal_bits > 8) destination[1] = (uint8_t)(seal >> 8);
1559  if (seal_bits > 16) destination[2] = (uint8_t)(seal >> 16);
1560  s->available_out_ += (seal_bits + 7) >> 3;
1561 }
1562 
1563 /* Injects padding bits or pushes compressed data to output.
1564  Returns false if nothing is done. */
1566  size_t* available_out, uint8_t** next_out, size_t* total_out) {
1567  if (s->stream_state_ == BROTLI_STREAM_FLUSH_REQUESTED &&
1568  s->last_bytes_bits_ != 0) {
1570  return BROTLI_TRUE;
1571  }
1572 
1573  if (s->available_out_ != 0 && *available_out != 0) {
1574  size_t copy_output_size =
1575  BROTLI_MIN(size_t, s->available_out_, *available_out);
1576  memcpy(*next_out, s->next_out_, copy_output_size);
1577  *next_out += copy_output_size;
1578  *available_out -= copy_output_size;
1579  s->next_out_ += copy_output_size;
1580  s->available_out_ -= copy_output_size;
1581  s->total_out_ += copy_output_size;
1582  if (total_out) *total_out = s->total_out_;
1583  return BROTLI_TRUE;
1584  }
1585 
1586  return BROTLI_FALSE;
1587 }
1588 
1590  if (s->stream_state_ == BROTLI_STREAM_FLUSH_REQUESTED &&
1591  s->available_out_ == 0) {
1592  s->stream_state_ = BROTLI_STREAM_PROCESSING;
1593  s->next_out_ = 0;
1594  }
1595 }
1596 
1598  BrotliEncoderState* s, BrotliEncoderOperation op, size_t* available_in,
1599  const uint8_t** next_in, size_t* available_out, uint8_t** next_out,
1600  size_t* total_out) {
1601  const size_t block_size_limit = (size_t)1 << s->params.lgwin;
1602  const size_t buf_size = BROTLI_MIN(size_t, kCompressFragmentTwoPassBlockSize,
1603  BROTLI_MIN(size_t, *available_in, block_size_limit));
1604  uint32_t* tmp_command_buf = NULL;
1605  uint32_t* command_buf = NULL;
1606  uint8_t* tmp_literal_buf = NULL;
1607  uint8_t* literal_buf = NULL;
1608  MemoryManager* m = &s->memory_manager_;
1609  if (s->params.quality != FAST_ONE_PASS_COMPRESSION_QUALITY &&
1610  s->params.quality != FAST_TWO_PASS_COMPRESSION_QUALITY) {
1611  return BROTLI_FALSE;
1612  }
1613  if (s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) {
1614  if (!s->command_buf_ && buf_size == kCompressFragmentTwoPassBlockSize) {
1615  s->command_buf_ =
1617  s->literal_buf_ =
1619  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(s->command_buf_) ||
1620  BROTLI_IS_NULL(s->literal_buf_)) {
1621  return BROTLI_FALSE;
1622  }
1623  }
1624  if (s->command_buf_) {
1625  command_buf = s->command_buf_;
1626  literal_buf = s->literal_buf_;
1627  } else {
1628  tmp_command_buf = BROTLI_ALLOC(m, uint32_t, buf_size);
1629  tmp_literal_buf = BROTLI_ALLOC(m, uint8_t, buf_size);
1630  if (BROTLI_IS_OOM(m) || BROTLI_IS_NULL(tmp_command_buf) ||
1631  BROTLI_IS_NULL(tmp_literal_buf)) {
1632  return BROTLI_FALSE;
1633  }
1634  command_buf = tmp_command_buf;
1635  literal_buf = tmp_literal_buf;
1636  }
1637  }
1638 
1639  while (BROTLI_TRUE) {
1640  if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) {
1641  continue;
1642  }
1643 
1644  /* Compress block only when internal output buffer is empty, stream is not
1645  finished, there is no pending flush request, and there is either
1646  additional input or pending operation. */
1647  if (s->available_out_ == 0 &&
1648  s->stream_state_ == BROTLI_STREAM_PROCESSING &&
1649  (*available_in != 0 || op != BROTLI_OPERATION_PROCESS)) {
1650  size_t block_size = BROTLI_MIN(size_t, block_size_limit, *available_in);
1651  BROTLI_BOOL is_last =
1652  (*available_in == block_size) && (op == BROTLI_OPERATION_FINISH);
1653  BROTLI_BOOL force_flush =
1654  (*available_in == block_size) && (op == BROTLI_OPERATION_FLUSH);
1655  size_t max_out_size = 2 * block_size + 503;
1656  BROTLI_BOOL inplace = BROTLI_TRUE;
1657  uint8_t* storage = NULL;
1658  size_t storage_ix = s->last_bytes_bits_;
1659  size_t table_size;
1660  int* table;
1661 
1662  if (force_flush && block_size == 0) {
1663  s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED;
1664  continue;
1665  }
1666  if (max_out_size <= *available_out) {
1667  storage = *next_out;
1668  } else {
1669  inplace = BROTLI_FALSE;
1670  storage = GetBrotliStorage(s, max_out_size);
1671  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1672  }
1673  storage[0] = (uint8_t)s->last_bytes_;
1674  storage[1] = (uint8_t)(s->last_bytes_ >> 8);
1675  table = GetHashTable(s, s->params.quality, block_size, &table_size);
1676  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1677 
1678  if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY) {
1679  BrotliCompressFragmentFast(m, *next_in, block_size, is_last, table,
1680  table_size, s->cmd_depths_, s->cmd_bits_, &s->cmd_code_numbits_,
1681  s->cmd_code_, &storage_ix, storage);
1682  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1683  } else {
1684  BrotliCompressFragmentTwoPass(m, *next_in, block_size, is_last,
1685  command_buf, literal_buf, table, table_size,
1686  &storage_ix, storage);
1687  if (BROTLI_IS_OOM(m)) return BROTLI_FALSE;
1688  }
1689  if (block_size != 0) {
1690  *next_in += block_size;
1691  *available_in -= block_size;
1692  }
1693  if (inplace) {
1694  size_t out_bytes = storage_ix >> 3;
1695  BROTLI_DCHECK(out_bytes <= *available_out);
1696  BROTLI_DCHECK((storage_ix & 7) == 0 || out_bytes < *available_out);
1697  *next_out += out_bytes;
1698  *available_out -= out_bytes;
1699  s->total_out_ += out_bytes;
1700  if (total_out) *total_out = s->total_out_;
1701  } else {
1702  size_t out_bytes = storage_ix >> 3;
1703  s->next_out_ = storage;
1704  s->available_out_ = out_bytes;
1705  }
1706  s->last_bytes_ = (uint16_t)(storage[storage_ix >> 3]);
1707  s->last_bytes_bits_ = storage_ix & 7u;
1708 
1709  if (force_flush) s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED;
1710  if (is_last) s->stream_state_ = BROTLI_STREAM_FINISHED;
1711  continue;
1712  }
1713  break;
1714  }
1715  BROTLI_FREE(m, tmp_command_buf);
1716  BROTLI_FREE(m, tmp_literal_buf);
1718  return BROTLI_TRUE;
1719 }
1720 
1722  BrotliEncoderState* s, size_t* available_in, const uint8_t** next_in,
1723  size_t* available_out, uint8_t** next_out, size_t* total_out) {
1724  if (*available_in > (1u << 24)) return BROTLI_FALSE;
1725  /* Switch to metadata block workflow, if required. */
1726  if (s->stream_state_ == BROTLI_STREAM_PROCESSING) {
1727  s->remaining_metadata_bytes_ = (uint32_t)*available_in;
1728  s->stream_state_ = BROTLI_STREAM_METADATA_HEAD;
1729  }
1730  if (s->stream_state_ != BROTLI_STREAM_METADATA_HEAD &&
1731  s->stream_state_ != BROTLI_STREAM_METADATA_BODY) {
1732  return BROTLI_FALSE;
1733  }
1734 
1735  while (BROTLI_TRUE) {
1736  if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) {
1737  continue;
1738  }
1739  if (s->available_out_ != 0) break;
1740 
1741  if (s->input_pos_ != s->last_flush_pos_) {
1743  &s->available_out_, &s->next_out_);
1744  if (!result) return BROTLI_FALSE;
1745  continue;
1746  }
1747 
1748  if (s->stream_state_ == BROTLI_STREAM_METADATA_HEAD) {
1749  s->next_out_ = s->tiny_buf_.u8;
1750  s->available_out_ =
1751  WriteMetadataHeader(s, s->remaining_metadata_bytes_, s->next_out_);
1752  s->stream_state_ = BROTLI_STREAM_METADATA_BODY;
1753  continue;
1754  } else {
1755  /* Exit workflow only when there is no more input and no more output.
1756  Otherwise client may continue producing empty metadata blocks. */
1757  if (s->remaining_metadata_bytes_ == 0) {
1758  s->remaining_metadata_bytes_ = BROTLI_UINT32_MAX;
1759  s->stream_state_ = BROTLI_STREAM_PROCESSING;
1760  break;
1761  }
1762  if (*available_out) {
1763  /* Directly copy input to output. */
1765  size_t, s->remaining_metadata_bytes_, *available_out);
1766  memcpy(*next_out, *next_in, copy);
1767  *next_in += copy;
1768  *available_in -= copy;
1769  s->remaining_metadata_bytes_ -= copy;
1770  *next_out += copy;
1771  *available_out -= copy;
1772  } else {
1773  /* This guarantees progress in "TakeOutput" workflow. */
1774  uint32_t copy = BROTLI_MIN(uint32_t, s->remaining_metadata_bytes_, 16);
1775  s->next_out_ = s->tiny_buf_.u8;
1776  memcpy(s->next_out_, *next_in, copy);
1777  *next_in += copy;
1778  *available_in -= copy;
1779  s->remaining_metadata_bytes_ -= copy;
1780  s->available_out_ = copy;
1781  }
1782  continue;
1783  }
1784  }
1785 
1786  return BROTLI_TRUE;
1787 }
1788 
1789 static void UpdateSizeHint(BrotliEncoderState* s, size_t available_in) {
1790  if (s->params.size_hint == 0) {
1792  uint64_t tail = available_in;
1793  uint32_t limit = 1u << 30;
1794  uint32_t total;
1795  if ((delta >= limit) || (tail >= limit) || ((delta + tail) >= limit)) {
1796  total = limit;
1797  } else {
1798  total = (uint32_t)(delta + tail);
1799  }
1800  s->params.size_hint = total;
1801  }
1802 }
1803 
1805  BrotliEncoderState* s, BrotliEncoderOperation op, size_t* available_in,
1806  const uint8_t** next_in, size_t* available_out,uint8_t** next_out,
1807  size_t* total_out) {
1808  if (!EnsureInitialized(s)) return BROTLI_FALSE;
1809 
1810  /* Unfinished metadata block; check requirements. */
1811  if (s->remaining_metadata_bytes_ != BROTLI_UINT32_MAX) {
1812  if (*available_in != s->remaining_metadata_bytes_) return BROTLI_FALSE;
1814  }
1815 
1817  UpdateSizeHint(s, 0); /* First data metablock might be emitted here. */
1818  return ProcessMetadata(
1819  s, available_in, next_in, available_out, next_out, total_out);
1820  }
1821 
1822  if (s->stream_state_ == BROTLI_STREAM_METADATA_HEAD ||
1823  s->stream_state_ == BROTLI_STREAM_METADATA_BODY) {
1824  return BROTLI_FALSE;
1825  }
1826 
1827  if (s->stream_state_ != BROTLI_STREAM_PROCESSING && *available_in != 0) {
1828  return BROTLI_FALSE;
1829  }
1830  if (s->params.quality == FAST_ONE_PASS_COMPRESSION_QUALITY ||
1831  s->params.quality == FAST_TWO_PASS_COMPRESSION_QUALITY) {
1832  return BrotliEncoderCompressStreamFast(s, op, available_in, next_in,
1833  available_out, next_out, total_out);
1834  }
1835  while (BROTLI_TRUE) {
1836  size_t remaining_block_size = RemainingInputBlockSize(s);
1837  /* Shorten input to flint size. */
1838  if (s->flint_ >= 0 && remaining_block_size > (size_t)s->flint_) {
1839  remaining_block_size = (size_t)s->flint_;
1840  }
1841 
1842  if (remaining_block_size != 0 && *available_in != 0) {
1843  size_t copy_input_size =
1844  BROTLI_MIN(size_t, remaining_block_size, *available_in);
1845  CopyInputToRingBuffer(s, copy_input_size, *next_in);
1846  *next_in += copy_input_size;
1847  *available_in -= copy_input_size;
1848  if (s->flint_ > 0) s->flint_ = (int8_t)(s->flint_ - (int)copy_input_size);
1849  continue;
1850  }
1851 
1852  if (InjectFlushOrPushOutput(s, available_out, next_out, total_out)) {
1853  /* Exit the "emit flint" workflow. */
1854  if (s->flint_ == BROTLI_FLINT_WAITING_FOR_FLUSHING) {
1856  if (s->stream_state_ == BROTLI_STREAM_PROCESSING) {
1857  s->flint_ = BROTLI_FLINT_DONE;
1858  }
1859  }
1860  continue;
1861  }
1862 
1863  /* Compress data only when internal output buffer is empty, stream is not
1864  finished and there is no pending flush request. */
1865  if (s->available_out_ == 0 &&
1866  s->stream_state_ == BROTLI_STREAM_PROCESSING) {
1867  if (remaining_block_size == 0 || op != BROTLI_OPERATION_PROCESS) {
1868  BROTLI_BOOL is_last = TO_BROTLI_BOOL(
1869  (*available_in == 0) && op == BROTLI_OPERATION_FINISH);
1870  BROTLI_BOOL force_flush = TO_BROTLI_BOOL(
1871  (*available_in == 0) && op == BROTLI_OPERATION_FLUSH);
1873  /* Force emitting (uncompressed) piece containing flint. */
1874  if (!is_last && s->flint_ == 0) {
1876  force_flush = BROTLI_TRUE;
1877  }
1878  UpdateSizeHint(s, *available_in);
1879  result = EncodeData(s, is_last, force_flush,
1880  &s->available_out_, &s->next_out_);
1881  if (!result) return BROTLI_FALSE;
1882  if (force_flush) s->stream_state_ = BROTLI_STREAM_FLUSH_REQUESTED;
1883  if (is_last) s->stream_state_ = BROTLI_STREAM_FINISHED;
1884  continue;
1885  }
1886  }
1887  break;
1888  }
1890  return BROTLI_TRUE;
1891 }
1892 
1894  return TO_BROTLI_BOOL(s->stream_state_ == BROTLI_STREAM_FINISHED &&
1896 }
1897 
1899  return TO_BROTLI_BOOL(s->available_out_ != 0);
1900 }
1901 
1903  size_t consumed_size = s->available_out_;
1904  uint8_t* result = s->next_out_;
1905  if (*size) {
1906  consumed_size = BROTLI_MIN(size_t, *size, s->available_out_);
1907  }
1908  if (consumed_size) {
1909  s->next_out_ += consumed_size;
1910  s->available_out_ -= consumed_size;
1911  s->total_out_ += consumed_size;
1913  *size = consumed_size;
1914  } else {
1915  *size = 0;
1916  result = 0;
1917  }
1918  return result;
1919 }
1920 
1922  return BROTLI_VERSION;
1923 }
1924 
1925 #if defined(__cplusplus) || defined(c_plusplus)
1926 } /* extern "C" */
1927 #endif
struct @88 table[500]
#define state
Definition: aptex-macros.h:996
#define tail
Definition: aptex-macros.h:514
#define mode
Definition: aptex-macros.h:510
@ block_size
Definition: aptex.h:160
void BrotliCreateBackwardReferences(size_t num_bytes, size_t position, const uint8_t *ringbuffer, size_t ringbuffer_mask, ContextLut literal_context_lut, const BrotliEncoderParams *params, Hasher *hasher, int *dist_cache, size_t *last_insert_len, Command *commands, size_t *num_commands, size_t *num_literals)
void BrotliCreateZopfliBackwardReferences(MemoryManager *m, size_t num_bytes, size_t position, const uint8_t *ringbuffer, size_t ringbuffer_mask, ContextLut literal_context_lut, const BrotliEncoderParams *params, Hasher *hasher, int *dist_cache, size_t *last_insert_len, Command *commands, size_t *num_commands, size_t *num_literals)
size_t BrotliZopfliComputeShortestPath(MemoryManager *m, size_t num_bytes, size_t position, const uint8_t *ringbuffer, size_t ringbuffer_mask, ContextLut literal_context_lut, const BrotliEncoderParams *params, const int *dist_cache, Hasher *hasher, ZopfliNode *nodes)
void BrotliCreateHqZopfliBackwardReferences(MemoryManager *m, size_t num_bytes, size_t position, const uint8_t *ringbuffer, size_t ringbuffer_mask, ContextLut literal_context_lut, const BrotliEncoderParams *params, Hasher *hasher, int *dist_cache, size_t *last_insert_len, Command *commands, size_t *num_commands, size_t *num_literals)
void BrotliZopfliCreateCommands(const size_t num_bytes, const size_t block_start, const ZopfliNode *nodes, int *dist_cache, size_t *last_insert_len, const BrotliEncoderParams *params, Command *commands, size_t *num_literals)
void BrotliInitZopfliNodes(ZopfliNode *array, size_t length)
static BROTLI_INLINE double BitsEntropy(const uint32_t *population, size_t size)
Definition: bit_cost.h:44
static BROTLI_INLINE double ShannonEntropy(const uint32_t *population, size_t size, size_t *total)
Definition: bit_cost.h:21
void BrotliStoreMetaBlockTrivial(MemoryManager *m, const uint8_t *input, size_t start_pos, size_t length, size_t mask, BROTLI_BOOL is_last, const BrotliEncoderParams *params, const Command *commands, size_t n_commands, size_t *storage_ix, uint8_t *storage)
void BrotliStoreMetaBlockFast(MemoryManager *m, const uint8_t *input, size_t start_pos, size_t length, size_t mask, BROTLI_BOOL is_last, const BrotliEncoderParams *params, const Command *commands, size_t n_commands, size_t *storage_ix, uint8_t *storage)
void BrotliStoreMetaBlock(MemoryManager *m, const uint8_t *input, size_t start_pos, size_t length, size_t mask, uint8_t prev_byte, uint8_t prev_byte2, BROTLI_BOOL is_last, const BrotliEncoderParams *params, ContextType literal_context_mode, const Command *commands, size_t n_commands, const MetaBlockSplit *mb, size_t *storage_ix, uint8_t *storage)
void BrotliStoreUncompressedMetaBlock(BROTLI_BOOL is_final_block, const uint8_t *BROTLI_RESTRICT input, size_t position, size_t mask, size_t len, size_t *BROTLI_RESTRICT storage_ix, uint8_t *BROTLI_RESTRICT storage)
static BROTLI_INLINE uint32_t CommandRestoreDistanceCode(const Command *self, const BrotliDistanceParams *dist)
Definition: command.h:146
static BROTLI_INLINE void GetLengthCode(size_t insertlen, size_t copylen, BROTLI_BOOL use_last_distance, uint16_t *code)
Definition: command.h:83
static BROTLI_INLINE void InitInsertCommand(Command *self, size_t insertlen)
Definition: command.h:138
void BrotliCompressFragmentFast(MemoryManager *m, const uint8_t *input, size_t input_size, BROTLI_BOOL is_last, int *table, size_t table_size, uint8_t cmd_depth[128], uint16_t cmd_bits[128], size_t *cmd_code_numbits, uint8_t *cmd_code, size_t *storage_ix, uint8_t *storage)
void BrotliCompressFragmentTwoPass(MemoryManager *m, const uint8_t *input, size_t input_size, BROTLI_BOOL is_last, uint32_t *command_buf, uint8_t *literal_buf, int *table, size_t table_size, size_t *storage_ix, uint8_t *storage)
static const size_t kCompressFragmentTwoPassBlockSize
#define BROTLI_MAX_DISTANCE
Definition: constants.h:80
#define BROTLI_DISTANCE_ALPHABET_SIZE(NPOSTFIX, NDIRECT, MAXNBITS)
Definition: constants.h:69
#define BROTLI_MAX_NDIRECT
Definition: constants.h:67
#define BROTLI_WINDOW_GAP
Definition: constants.h:102
#define BROTLI_NUM_DISTANCE_SHORT_CODES
Definition: constants.h:60
#define BROTLI_MAX_NPOSTFIX
Definition: constants.h:66
#define BROTLI_MAX_DISTANCE_BITS
Definition: constants.h:68
#define BROTLI_MAX_BACKWARD_LIMIT(W)
Definition: constants.h:103
const uint8_t * ContextLut
Definition: context.h:105
#define BROTLI_CONTEXT_LUT(MODE)
Definition: context.h:108
ContextType
Definition: context.h:94
@ CONTEXT_UTF8
Definition: context.h:97
@ CONTEXT_SIGNED
Definition: context.h:98
#define BROTLI_CONTEXT(P1, P2, LUT)
Definition: context.h:111
int params
Definition: definitions.c:42
#define dummy
Definition: devnag.c:313
int dummy
Definition: dummy.c:29
struct rect data
Definition: dvipdfm.c:64
void BrotliInitEncoderDictionary(BrotliEncoderDictionary *dict)
Definition: encoder_dict.c:18
static BROTLI_INLINE uint32_t Log2FloorNonZero(size_t n)
Definition: fast_log.h:21
static void copy(GlyphCachePtr *root)
Definition: gcache.c:378
#define s
Definition: afcover.h:80
#define t
Definition: afcover.h:96
static FIELD_PTR prev
Definition: genind.c:36
#define memcpy(d, s, n)
Definition: gsftopk.c:64
unsigned nbytes
Definition: in_pcx.cpp:355
register bit_buf_type register int int nbits
Definition: jdhuff.h:156
#define NULL
Definition: ftobjs.h:61
small capitals from c petite p
Definition: afcover.h:72
small capitals from c petite p scientific i
Definition: afcover.h:80
#define bits
Definition: infblock.c:15
void(* free_func)()
Definition: zlib.h:64
voidpf(* alloc_func)()
Definition: zlib.h:63
unsigned short uint16_t
Definition: stdint.h:79
unsigned int uint32_t
Definition: stdint.h:80
unsigned char uint8_t
Definition: stdint.h:78
unsigned __int64 uint64_t
Definition: stdint.h:90
signed char int8_t
Definition: stdint.h:75
#define buf_size
Definition: ctangleboot.c:104
#define length(c)
Definition: ctangleboot.c:65
#define malloc
Definition: alloca.c:91
const int * pos
Definition: combiners.h:905
#define size_t
Definition: glob.c:257
#define BROTLI_ALLOC(M, T, N)
Definition: memory.h:44
#define BROTLI_FREE(M, P)
Definition: memory.h:48
#define BROTLI_IS_OOM(M)
Definition: memory.h:54
#define BROTLI_IS_NULL(A)
Definition: memory.h:68
void BrotliOptimizeHistograms(uint32_t num_distance_codes, MetaBlockSplit *mb)
Definition: metablock.c:641
void BrotliBuildMetaBlockGreedy(MemoryManager *m, const uint8_t *ringbuffer, size_t pos, size_t mask, uint8_t prev_byte, uint8_t prev_byte2, ContextLut literal_context_lut, size_t num_contexts, const uint32_t *static_context_map, const Command *commands, size_t n_commands, MetaBlockSplit *mb)
Definition: metablock.c:619
void BrotliBuildMetaBlock(MemoryManager *m, const uint8_t *ringbuffer, const size_t pos, const size_t mask, BrotliEncoderParams *params, uint8_t prev_byte, uint8_t prev_byte2, Command *cmds, size_t num_commands, ContextType literal_context_mode, MetaBlockSplit *mb)
Definition: metablock.c:126
void BrotliInitDistanceParams(BrotliEncoderParams *params, uint32_t npostfix, uint32_t ndirect)
Definition: metablock.c:28
static BROTLI_INLINE void DestroyMetaBlockSplit(MemoryManager *m, MetaBlockSplit *mb)
Definition: metablock.h:58
static BROTLI_INLINE void InitMetaBlockSplit(MetaBlockSplit *mb)
Definition: metablock.h:42
union value value
Definition: obx.h:44
unsigned start_pos
Definition: parse_ofm.c:60
static int delta
Definition: pbmtolj.c:36
set set set set set set set macro pixldst1 abits if abits op else op endif endm macro pixldst2 abits if abits op else op endif endm macro pixldst4 abits if abits op else op endif endm macro pixldst0 abits op endm macro pixldst3 mem_operand op endm macro pixldst30 mem_operand op endm macro pixldst abits if abits elseif abits elseif abits elseif abits elseif abits pixldst0 abits else pixldst0 abits pixldst0 abits pixldst0 abits pixldst0 abits endif elseif abits else pixldst0 abits pixldst0 abits endif elseif abits else error unsupported bpp *numpix else pixst endif endm macro pixld1_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl mov asr adds SRC_WIDTH_FIXED bpl add asl else error unsupported endif endm macro pixld2_s mem_operand if mov asr add asl add asl mov asr sub UNIT_X add asl mov asr add asl add asl mov asr add UNIT_X add asl else pixld1_s mem_operand pixld1_s mem_operand endif endm macro pixld0_s mem_operand if asr adds SRC_WIDTH_FIXED bpl add asl elseif asr adds SRC_WIDTH_FIXED bpl add asl endif endm macro pixld_s_internal mem_operand if mem_operand pixld2_s mem_operand pixdeinterleave basereg elseif mem_operand elseif mem_operand elseif mem_operand elseif mem_operand pixld0_s mem_operand else pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else pixld0_s mem_operand pixld0_s mem_operand endif elseif mem_operand else error unsupported mem_operand if bpp mem_operand endif endm macro vuzp8 reg2 vuzp d d &reg2 endm macro vzip8 reg2 vzip d d &reg2 endm macro pixdeinterleave basereg basereg basereg basereg basereg endif endm macro pixinterleave basereg basereg basereg basereg basereg endif endm macro PF boost_increment endif if endif PF tst PF addne PF subne PF cmp ORIG_W if endif if endif if endif PF subge ORIG_W PF subges if endif if endif if endif endif endm macro cache_preload_simple endif if dst_r_bpp pld[DST_R, #(PREFETCH_DISTANCE_SIMPLE *dst_r_bpp/8)] endif if mask_bpp pld chunk_size[MASK, #(PREFETCH_DISTANCE_SIMPLE *mask_bpp/8)] endif endif endm macro fetch_mask_pixblock pixld mask_basereg pixblock_size MASK endm macro ensure_destination_ptr_alignment process_pixblock_tail_head if beq irp skip1 beq endif SRC MASK if dst_r_bpp DST_R else add endif PF add sub src_basereg pixdeinterleave mask_basereg pixdeinterleave dst_r_basereg process_pixblock_head pixblock_size cache_preload_simple process_pixblock_tail pixinterleave dst_w_basereg irp beq endif process_pixblock_tail_head tst beq irp
static char storage
Definition: pnmtosgi.c:48
static int size
Definition: ppmlabel.c:24
static int offset
Definition: ppmtogif.c:642
static int quality
Definition: ppmtopjxl.c:45
bstring c int memset(void *s, int c, int length)
static long bytes
Definition: psutil.c:35
#define BROTLI_VERSION
Definition: version.h:17
static void InjectBytePaddingBlock(BrotliEncoderState *s)
Definition: encode.c:1540
static uint8_t * GetBrotliStorage(BrotliEncoderState *s, size_t size)
Definition: encode.c:210
static void ChooseDistanceParams(BrotliEncoderParams *params)
Definition: encode.c:662
static void BrotliEncoderInitState(BrotliEncoderState *s)
Definition: encode.c:757
static size_t HashTableSize(size_t max_table_size, size_t input_size)
Definition: encode.c:221
static BROTLI_BOOL ProcessMetadata(BrotliEncoderState *s, size_t *available_in, const uint8_t **next_in, size_t *available_out, uint8_t **next_out, size_t *total_out)
Definition: encode.c:1721
static BROTLI_BOOL BrotliCompressBufferQuality10(int lgwin, size_t input_size, const uint8_t *input_buffer, size_t *encoded_size, uint8_t *encoded_buffer)
Definition: encode.c:1204
static int * GetHashTable(BrotliEncoderState *s, int quality, size_t input_size, size_t *table_size)
Definition: encode.c:229
static void BrotliEncoderCleanupState(BrotliEncoderState *s)
Definition: encode.c:815
static void InitCommandPrefixCodes(uint8_t cmd_depths[128], uint16_t cmd_bits[128], uint8_t cmd_code[512], size_t *cmd_code_numbits)
Definition: encode.c:287
static void WriteMetaBlockInternal(MemoryManager *m, const uint8_t *data, const size_t mask, const uint64_t last_flush_pos, const size_t bytes, const BROTLI_BOOL is_last, ContextType literal_context_mode, const BrotliEncoderParams *params, const uint8_t prev_byte, const uint8_t prev_byte2, const size_t num_literals, const size_t num_commands, Command *commands, const int *saved_dist_cache, int *dist_cache, size_t *storage_ix, uint8_t *storage)
Definition: encode.c:553
const uint8_t * BrotliEncoderTakeOutput(BrotliEncoderState *s, size_t *size)
Definition: encode.c:1902
BROTLI_BOOL BrotliEncoderIsFinished(BrotliEncoderState *s)
Definition: encode.c:1893
BrotliEncoderFlintState
Definition: encode.c:57
@ BROTLI_FLINT_WAITING_FOR_FLUSHING
Definition: encode.c:61
@ BROTLI_FLINT_WAITING_FOR_PROCESSING
Definition: encode.c:60
@ BROTLI_FLINT_NEEDS_2_BYTES
Definition: encode.c:58
@ BROTLI_FLINT_NEEDS_1_BYTE
Definition: encode.c:59
@ BROTLI_FLINT_DONE
Definition: encode.c:62
static BROTLI_BOOL EncodeData(BrotliEncoderState *s, const BROTLI_BOOL is_last, const BROTLI_BOOL force_flush, size_t *out_size, uint8_t **output)
Definition: encode.c:960
static uint32_t WrapPosition(uint64_t position)
Definition: encode.c:200
static BROTLI_BOOL EnsureInitialized(BrotliEncoderState *s)
Definition: encode.c:688
uint32_t BrotliEncoderVersion(void)
Definition: encode.c:1921
static void CheckFlushComplete(BrotliEncoderState *s)
Definition: encode.c:1589
static void UpdateSizeHint(BrotliEncoderState *s, size_t available_in)
Definition: encode.c:1789
static void ExtendLastCommand(BrotliEncoderState *s, uint32_t *bytes, uint32_t *wrapped_last_processed_pos)
Definition: encode.c:914
static void EncodeWindowBits(int lgwin, BROTLI_BOOL large_window, uint16_t *last_bytes, uint8_t *last_bytes_bits)
Definition: encode.c:264
BROTLI_BOOL BrotliEncoderCompress(int quality, int lgwin, BrotliEncoderMode mode, size_t input_size, const uint8_t *input_buffer, size_t *encoded_size, uint8_t *encoded_buffer)
Definition: encode.c:1471
BROTLI_BOOL BrotliEncoderHasMoreOutput(BrotliEncoderState *s)
Definition: encode.c:1898
BrotliEncoderState * BrotliEncoderCreateInstance(brotli_alloc_func alloc_func, brotli_free_func free_func, void *opaque)
Definition: encode.c:797
static void BrotliEncoderInitParams(BrotliEncoderParams *params)
Definition: encode.c:739
size_t BrotliEncoderMaxCompressedSize(size_t input_size)
Definition: encode.c:1426
void BrotliEncoderDestroyInstance(BrotliEncoderState *state)
Definition: encode.c:831
static ContextType ChooseContextMode(const BrotliEncoderParams *params, const uint8_t *data, const size_t pos, const size_t mask, const size_t length)
Definition: encode.c:541
BrotliEncoderStreamState
Definition: encode.c:43
@ BROTLI_STREAM_FLUSH_REQUESTED
Definition: encode.c:48
@ BROTLI_STREAM_PROCESSING
Definition: encode.c:45
@ BROTLI_STREAM_FINISHED
Definition: encode.c:50
@ BROTLI_STREAM_METADATA_BODY
Definition: encode.c:54
@ BROTLI_STREAM_METADATA_HEAD
Definition: encode.c:52
#define COPY_ARRAY(dst, src)
Definition: encode.c:41
static BROTLI_BOOL UpdateLastProcessedPos(BrotliEncoderState *s)
Definition: encode.c:907
static void DecideOverLiteralContextModeling(const uint8_t *input, size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint, size_t *num_literal_contexts, const uint32_t **literal_context_map)
Definition: encode.c:482
BROTLI_BOOL BrotliEncoderCompressStream(BrotliEncoderState *s, BrotliEncoderOperation op, size_t *available_in, const uint8_t **next_in, size_t *available_out, uint8_t **next_out, size_t *total_out)
Definition: encode.c:1804
static size_t MakeUncompressedStream(const uint8_t *input, size_t input_size, uint8_t *output)
Definition: encode.c:1439
static size_t InputBlockSize(BrotliEncoderState *s)
Definition: encode.c:131
static void ChooseContextMap(int quality, uint32_t *bigram_histo, size_t *num_literal_contexts, const uint32_t **literal_context_map)
Definition: encode.c:339
static BROTLI_BOOL InjectFlushOrPushOutput(BrotliEncoderState *s, size_t *available_out, uint8_t **next_out, size_t *total_out)
Definition: encode.c:1565
static size_t WriteMetadataHeader(BrotliEncoderState *s, const size_t block_size, uint8_t *header)
Definition: encode.c:1180
BROTLI_BOOL BrotliEncoderSetParameter(BrotliEncoderState *state, BrotliEncoderParameter p, uint32_t value)
Definition: encode.c:146
struct BrotliEncoderStateStruct BrotliEncoderStateStruct
static size_t RemainingInputBlockSize(BrotliEncoderState *s)
Definition: encode.c:139
static BROTLI_BOOL BrotliEncoderCompressStreamFast(BrotliEncoderState *s, BrotliEncoderOperation op, size_t *available_in, const uint8_t **next_in, size_t *available_out, uint8_t **next_out, size_t *total_out)
Definition: encode.c:1597
static BROTLI_BOOL ShouldCompress(const uint8_t *data, const size_t mask, const uint64_t last_flush_pos, const size_t bytes, const size_t num_literals, const size_t num_commands)
Definition: encode.c:513
static uint64_t UnprocessedInputSize(BrotliEncoderState *s)
Definition: encode.c:135
static void CopyInputToRingBuffer(BrotliEncoderState *s, const size_t input_size, const uint8_t *input_buffer)
Definition: encode.c:850
static BROTLI_BOOL ShouldUseComplexStaticContextMap(const uint8_t *input, size_t start_pos, size_t length, size_t mask, int quality, size_t size_hint, size_t *num_literal_contexts, const uint32_t **literal_context_map)
Definition: encode.c:402
static BROTLI_INLINE void HasherInit(Hasher *hasher)
Definition: hash.h:392
static BROTLI_INLINE void DestroyHasher(MemoryManager *m, Hasher *hasher)
Definition: hash.h:396
static BROTLI_INLINE void InitOrStitchToPreviousBlock(MemoryManager *m, Hasher *hasher, const uint8_t *data, size_t mask, BrotliEncoderParams *params, size_t position, size_t input_size, BROTLI_BOOL is_last)
Definition: hash.h:462
static BROTLI_INLINE void HasherReset(Hasher *hasher)
Definition: hash.h:401
void BrotliInitMemoryManager(MemoryManager *m, brotli_alloc_func alloc_func, brotli_free_func free_func, void *opaque)
Definition: memory.c:30
void BrotliWipeOutMemoryManager(MemoryManager *m)
Definition: memory.c:62
#define BROTLI_DEFAULT_WINDOW
Definition: encode.h:62
#define BROTLI_MAX_WINDOW_BITS
Definition: encode.h:29
#define BROTLI_DEFAULT_QUALITY
Definition: encode.h:60
BrotliEncoderParameter
Definition: encode.h:134
@ BROTLI_PARAM_QUALITY
Definition: encode.h:147
@ BROTLI_PARAM_NDIRECT
Definition: encode.h:204
@ BROTLI_PARAM_DISABLE_LITERAL_CONTEXT_MODELING
Definition: encode.h:178
@ BROTLI_PARAM_STREAM_OFFSET
Definition: encode.h:220
@ BROTLI_PARAM_LARGE_WINDOW
Definition: encode.h:188
@ BROTLI_PARAM_NPOSTFIX
Definition: encode.h:196
@ BROTLI_PARAM_LGBLOCK
Definition: encode.h:172
@ BROTLI_PARAM_SIZE_HINT
Definition: encode.h:184
@ BROTLI_PARAM_LGWIN
Definition: encode.h:158
@ BROTLI_PARAM_MODE
Definition: encode.h:140
#define BROTLI_DEFAULT_MODE
Definition: encode.h:64
BrotliEncoderMode
Definition: encode.h:45
@ BROTLI_MODE_FONT
Definition: encode.h:56
BrotliEncoderOperation
Definition: encode.h:67
@ BROTLI_OPERATION_FLUSH
Definition: encode.h:90
@ BROTLI_OPERATION_EMIT_METADATA
Definition: encode.h:130
@ BROTLI_OPERATION_FINISH
Definition: encode.h:109
@ BROTLI_OPERATION_PROCESS
Definition: encode.h:73
#define BROTLI_LARGE_MAX_WINDOW_BITS
Definition: encode.h:34
#define BROTLI_UINT32_MAX
Definition: types.h:59
#define BROTLI_TRUE
Definition: types.h:51
void *(* brotli_alloc_func)(void *opaque, size_t size)
Definition: types.h:71
void(* brotli_free_func)(void *opaque, void *address)
Definition: types.h:81
#define BROTLI_FALSE
Definition: types.h:53
#define BROTLI_SIZE_MAX
Definition: types.h:60
#define TO_BROTLI_BOOL(X)
Definition: types.h:55
#define BROTLI_BOOL
Definition: types.h:49
#define mask(n)
Definition: lbitlib.c:93
#define MAX_NUM_DELAYED_SYMBOLS
Definition: quality.h:33
#define MAX_QUALITY_FOR_STATIC_ENTROPY_CODES
Definition: quality.h:22
static BROTLI_INLINE void SanitizeParams(BrotliEncoderParams *params)
Definition: quality.h:59
#define MIN_QUALITY_FOR_OPTIMIZE_HISTOGRAMS
Definition: quality.h:25
#define HQ_ZOPFLIFICATION_QUALITY
Definition: quality.h:20
#define ZOPFLIFICATION_QUALITY
Definition: quality.h:19
#define FAST_ONE_PASS_COMPRESSION_QUALITY
Definition: quality.h:17
#define MIN_QUALITY_FOR_NONZERO_DISTANCE_PARAMS
Definition: quality.h:24
static BROTLI_INLINE int ComputeLgBlock(const BrotliEncoderParams *params)
Definition: quality.h:75
#define MIN_QUALITY_FOR_HQ_CONTEXT_MODELING
Definition: quality.h:28
#define MIN_QUALITY_FOR_HQ_BLOCK_SPLITTING
Definition: quality.h:29
static BROTLI_INLINE size_t MaxMetablockSize(const BrotliEncoderParams *params)
Definition: quality.h:103
#define FAST_TWO_PASS_COMPRESSION_QUALITY
Definition: quality.h:18
#define MIN_QUALITY_FOR_CONTEXT_MODELING
Definition: quality.h:27
#define MIN_QUALITY_FOR_BLOCK_SPLIT
Definition: quality.h:23
static BROTLI_INLINE size_t MaxHashTableSize(int quality)
Definition: quality.h:36
static BROTLI_INLINE void RingBufferInit(RingBuffer *rb)
Definition: ringbuffer.h:49
static BROTLI_INLINE void RingBufferSetup(const BrotliEncoderParams *params, RingBuffer *rb)
Definition: ringbuffer.h:56
static BROTLI_INLINE void RingBufferFree(MemoryManager *m, RingBuffer *rb)
Definition: ringbuffer.h:66
static BROTLI_INLINE void RingBufferWrite(MemoryManager *m, const uint8_t *bytes, size_t n, RingBuffer *rb)
Definition: ringbuffer.h:105
#define uint32_t
Definition: stdint.in.h:168
#define uint64_t
Definition: stdint.in.h:215
#define uint16_t
Definition: stdint.in.h:161
#define int8_t
Definition: stdint.in.h:153
#define uint8_t
Definition: stdint.in.h:154
uint32_t alphabet_size_limit
Definition: params.h:27
BrotliDistanceParams dist
Definition: params.h:42
RingBuffer ringbuffer_
Definition: encode.c:71
BROTLI_BOOL is_initialized_
Definition: encode.c:128
uint16_t last_bytes_
Definition: encode.c:81
uint16_t cmd_bits_[128]
Definition: encode.c:107
size_t large_table_size_
Definition: encode.c:97
uint32_t * command_buf_
Definition: encode.c:113
uint64_t last_flush_pos_
Definition: encode.c:77
int small_table_[1<< 10]
Definition: encode.c:95
uint32_t remaining_metadata_bytes_
Definition: encode.c:124
uint8_t cmd_code_[512]
Definition: encode.c:110
BrotliEncoderStreamState stream_state_
Definition: encode.c:125
MemoryManager memory_manager_
Definition: encode.c:68
uint8_t cmd_depths_[128]
Definition: encode.c:106
Command * commands_
Definition: encode.c:73
union BrotliEncoderStateStruct::@1428 tiny_buf_
int saved_dist_cache_[4]
Definition: encode.c:80
BROTLI_BOOL is_last_block_emitted_
Definition: encode.c:127
uint64_t last_processed_pos_
Definition: encode.c:78
int dist_cache_[BROTLI_NUM_DISTANCE_SHORT_CODES]
Definition: encode.c:79
uint8_t * storage_
Definition: encode.c:90
uint8_t last_bytes_bits_
Definition: encode.c:82
uint8_t * literal_buf_
Definition: encode.c:114
BrotliEncoderParams params
Definition: encode.c:66
uint32_t insert_len_
Definition: command.h:108
uint16_t cmd_prefix_
Definition: command.h:113
uint16_t dist_prefix_
Definition: command.h:116
uint32_t copy_len_
Definition: command.h:110
Definition: hash.h:381
union Hasher::@1429 privat
H10 _H10
Definition: hash.h:387
const uint32_t mask_
Definition: ringbuffer.h:35
uint32_t pos_
Definition: ringbuffer.h:41
uint8_t * buffer_
Definition: ringbuffer.h:46
Definition: namelist.c:170
Definition: execute.c:108
Definition: sh.h:1226
Definition: output.h:18
Definition: dvips.h:235
Definition: table.h:30
static int block_start
Definition: tex4ht.c:946
m
Definition: tex4ht.c:3990
return() int(((double) *(font_tbl[cur_fnt].wtbl+(int)(*(font_tbl[cur_fnt].char_wi+(int)(ch - font_tbl[cur_fnt].char_f)% 256)))/(double)(1L<< 20)) *(double) font_tbl[cur_fnt].scale)
#define BROTLI_MAX(T, A, B)
Definition: platform.h:520
#define BROTLI_UNUSED(X)
Definition: platform.h:511
#define BROTLI_MIN(T, A, B)
Definition: platform.h:519
#define BROTLI_DCHECK(x)
Definition: platform.h:484
void output_start(void)
Definition: output.c:508
static UBool fallback(char *loc)
Definition: ucurr.cpp:604
Definition: obx.h:51
BROTLI_BOOL BrotliIsMostlyUTF8(const uint8_t *data, const size_t pos, const size_t mask, const size_t length, const double min_fraction)
Definition: utf8_util.c:68
static const double kMinUTF8Ratio
Definition: utf8_util.h:19
static BROTLI_INLINE void BrotliWriteBits(size_t n_bits, uint64_t bits, size_t *BROTLI_RESTRICT pos, uint8_t *BROTLI_RESTRICT array)
Definition: write_bits.h:34
#define limit(x)
Definition: yuvsplittoppm.c:26