summaryrefslogtreecommitdiffstats
path: root/modules/brotli/enc/compress_fragment.c
blob: 9e50b2098a0b7e42ea2026995e385494f117bbd5 (plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
/* Copyright 2015 Google Inc. All Rights Reserved.

   Distributed under MIT license.
   See file LICENSE for detail or copy at https://opensource.org/licenses/MIT
*/

/* Function for fast encoding of an input fragment, independently from the input
   history. This function uses one-pass processing: when we find a backward
   match, we immediately emit the corresponding command and literal codes to
   the bit stream.

   Adapted from the CompressFragment() function in
   https://github.com/google/snappy/blob/master/snappy.cc */

#include "./compress_fragment.h"

#include <string.h>  /* memcmp, memcpy, memset */

#include "../common/constants.h"
#include "../common/platform.h"
#include <brotli/types.h>
#include "./brotli_bit_stream.h"
#include "./entropy_encode.h"
#include "./fast_log.h"
#include "./find_match_length.h"
#include "./memory.h"
#include "./write_bits.h"

#if defined(__cplusplus) || defined(c_plusplus)
extern "C" {
#endif

#define MAX_DISTANCE (long)BROTLI_MAX_BACKWARD_LIMIT(18)

/* kHashMul32 multiplier has these properties:
   * The multiplier must be odd. Otherwise we may lose the highest bit.
   * No long streaks of ones or zeros.
   * There is no effort to ensure that it is a prime, the oddity is enough
     for this use.
   * The number has been tuned heuristically against compression benchmarks. */
static const uint32_t kHashMul32 = 0x1E35A7BD;

static BROTLI_INLINE uint32_t Hash(const uint8_t* p, size_t shift) {
  const uint64_t h = (BROTLI_UNALIGNED_LOAD64LE(p) << 24) * kHashMul32;
  return (uint32_t)(h >> shift);
}

static BROTLI_INLINE uint32_t HashBytesAtOffset(
    uint64_t v, int offset, size_t shift) {
  BROTLI_DCHECK(offset >= 0);
  BROTLI_DCHECK(offset <= 3);
  {
    const uint64_t h = ((v >> (8 * offset)) << 24) * kHashMul32;
    return (uint32_t)(h >> shift);
  }
}

static BROTLI_INLINE BROTLI_BOOL IsMatch(const uint8_t* p1, const uint8_t* p2) {
  return TO_BROTLI_BOOL(
      BrotliUnalignedRead32(p1) == BrotliUnalignedRead32(p2) &&
      p1[4] == p2[4]);
}

/* Builds a literal prefix code into "depths" and "bits" based on the statistics
   of the "input" string and stores it into the bit stream.
   Note that the prefix code here is built from the pre-LZ77 input, therefore
   we can only approximate the statistics of the actual literal stream.
   Moreover, for long inputs we build a histogram from a sample of the input
   and thus have to assign a non-zero depth for each literal.
   Returns estimated compression ratio millibytes/char for encoding given input
   with generated code. */
static size_t BuildAndStoreLiteralPrefixCode(MemoryManager* m,
                                             const uint8_t* input,
                                             const size_t input_size,
                                             uint8_t depths[256],
                                             uint16_t bits[256],
                                             size_t* storage_ix,
                                             uint8_t* storage) {
  uint32_t histogram[256] = { 0 };
  size_t histogram_total;
  size_t i;
  if (input_size < (1 << 15)) {
    for (i = 0; i < input_size; ++i) {
      ++histogram[input[i]];
    }
    histogram_total = input_size;
    for (i = 0; i < 256; ++i) {
      /* We weigh the first 11 samples with weight 3 to account for the
         balancing effect of the LZ77 phase on the histogram. */
      const uint32_t adjust = 2 * BROTLI_MIN(uint32_t, histogram[i], 11u);
      histogram[i] += adjust;
      histogram_total += adjust;
    }
  } else {
    static const size_t kSampleRate = 29;
    for (i = 0; i < input_size; i += kSampleRate) {
      ++histogram[input[i]];
    }
    histogram_total = (input_size + kSampleRate - 1) / kSampleRate;
    for (i = 0; i < 256; ++i) {
      /* We add 1 to each population count to avoid 0 bit depths (since this is
         only a sample and we don't know if the symbol appears or not), and we
         weigh the first 11 samples with weight 3 to account for the balancing
         effect of the LZ77 phase on the histogram (more frequent symbols are
         more likely to be in backward references instead as literals). */
      const uint32_t adjust = 1 + 2 * BROTLI_MIN(uint32_t, histogram[i], 11u);
      histogram[i] += adjust;
      histogram_total += adjust;
    }
  }
  BrotliBuildAndStoreHuffmanTreeFast(m, histogram, histogram_total,
                                     /* max_bits = */ 8,
                                     depths, bits, storage_ix, storage);
  if (BROTLI_IS_OOM(m)) return 0;
  {
    size_t literal_ratio = 0;
    for (i = 0; i < 256; ++i) {
      if (histogram[i]) literal_ratio += histogram[i] * depths[i];
    }
    /* Estimated encoding ratio, millibytes per symbol. */
    return (literal_ratio * 125) / histogram_total;
  }
}

/* Builds a command and distance prefix code (each 64 symbols) into "depth" and
   "bits" based on "histogram" and stores it into the bit stream. */
static void BuildAndStoreCommandPrefixCode(const uint32_t histogram[128],
    uint8_t depth[128], uint16_t bits[128], size_t* storage_ix,
    uint8_t* storage) {
  /* Tree size for building a tree over 64 symbols is 2 * 64 + 1. */
  HuffmanTree tree[129];
  uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS] = { 0 };
  uint16_t cmd_bits[64];

  BrotliCreateHuffmanTree(histogram, 64, 15, tree, depth);
  BrotliCreateHuffmanTree(&histogram[64], 64, 14, tree, &depth[64]);
  /* We have to jump through a few hoops here in order to compute
     the command bits because the symbols are in a different order than in
     the full alphabet. This looks complicated, but having the symbols
     in this order in the command bits saves a few branches in the Emit*
     functions. */
  memcpy(cmd_depth, depth, 24);
  memcpy(cmd_depth + 24, depth + 40, 8);
  memcpy(cmd_depth + 32, depth + 24, 8);
  memcpy(cmd_depth + 40, depth + 48, 8);
  memcpy(cmd_depth + 48, depth + 32, 8);
  memcpy(cmd_depth + 56, depth + 56, 8);
  BrotliConvertBitDepthsToSymbols(cmd_depth, 64, cmd_bits);
  memcpy(bits, cmd_bits, 48);
  memcpy(bits + 24, cmd_bits + 32, 16);
  memcpy(bits + 32, cmd_bits + 48, 16);
  memcpy(bits + 40, cmd_bits + 24, 16);
  memcpy(bits + 48, cmd_bits + 40, 16);
  memcpy(bits + 56, cmd_bits + 56, 16);
  BrotliConvertBitDepthsToSymbols(&depth[64], 64, &bits[64]);
  {
    /* Create the bit length array for the full command alphabet. */
    size_t i;
    memset(cmd_depth, 0, 64);  /* only 64 first values were used */
    memcpy(cmd_depth, depth, 8);
    memcpy(cmd_depth + 64, depth + 8, 8);
    memcpy(cmd_depth + 128, depth + 16, 8);
    memcpy(cmd_depth + 192, depth + 24, 8);
    memcpy(cmd_depth + 384, depth + 32, 8);
    for (i = 0; i < 8; ++i) {
      cmd_depth[128 + 8 * i] = depth[40 + i];
      cmd_depth[256 + 8 * i] = depth[48 + i];
      cmd_depth[448 + 8 * i] = depth[56 + i];
    }
    BrotliStoreHuffmanTree(
        cmd_depth, BROTLI_NUM_COMMAND_SYMBOLS, tree, storage_ix, storage);
  }
  BrotliStoreHuffmanTree(&depth[64], 64, tree, storage_ix, storage);
}

/* REQUIRES: insertlen < 6210 */
static BROTLI_INLINE void EmitInsertLen(size_t insertlen,
                                        const uint8_t depth[128],
                                        const uint16_t bits[128],
                                        uint32_t histo[128],
                                        size_t* storage_ix,
                                        uint8_t* storage) {
  if (insertlen < 6) {
    const size_t code = insertlen + 40;
    BrotliWriteBits(depth[code], bits[code], storage_ix, storage);
    ++histo[code];
  } else if (insertlen < 130) {
    const size_t tail = insertlen - 2;
    const uint32_t nbits = Log2FloorNonZero(tail) - 1u;
    const size_t prefix = tail >> nbits;
    const size_t inscode = (nbits << 1) + prefix + 42;
    BrotliWriteBits(depth[inscode], bits[inscode], storage_ix, storage);
    BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);
    ++histo[inscode];
  } else if (insertlen < 2114) {
    const size_t tail = insertlen - 66;
    const uint32_t nbits = Log2FloorNonZero(tail);
    const size_t code = nbits + 50;
    BrotliWriteBits(depth[code], bits[code], storage_ix, storage);
    BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);
    ++histo[code];
  } else {
    BrotliWriteBits(depth[61], bits[61], storage_ix, storage);
    BrotliWriteBits(12, insertlen - 2114, storage_ix, storage);
    ++histo[61];
  }
}

static BROTLI_INLINE void EmitLongInsertLen(size_t insertlen,
                                            const uint8_t depth[128],
                                            const uint16_t bits[128],
                                            uint32_t histo[128],
                                            size_t* storage_ix,
                                            uint8_t* storage) {
  if (insertlen < 22594) {
    BrotliWriteBits(depth[62], bits[62], storage_ix, storage);
    BrotliWriteBits(14, insertlen - 6210, storage_ix, storage);
    ++histo[62];
  } else {
    BrotliWriteBits(depth[63], bits[63], storage_ix, storage);
    BrotliWriteBits(24, insertlen - 22594, storage_ix, storage);
    ++histo[63];
  }
}

static BROTLI_INLINE void EmitCopyLen(size_t copylen,
                                      const uint8_t depth[128],
                                      const uint16_t bits[128],
                                      uint32_t histo[128],
                                      size_t* storage_ix,
                                      uint8_t* storage) {
  if (copylen < 10) {
    BrotliWriteBits(
        depth[copylen + 14], bits[copylen + 14], storage_ix, storage);
    ++histo[copylen + 14];
  } else if (copylen < 134) {
    const size_t tail = copylen - 6;
    const uint32_t nbits = Log2FloorNonZero(tail) - 1u;
    const size_t prefix = tail >> nbits;
    const size_t code = (nbits << 1) + prefix + 20;
    BrotliWriteBits(depth[code], bits[code], storage_ix, storage);
    BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);
    ++histo[code];
  } else if (copylen < 2118) {
    const size_t tail = copylen - 70;
    const uint32_t nbits = Log2FloorNonZero(tail);
    const size_t code = nbits + 28;
    BrotliWriteBits(depth[code], bits[code], storage_ix, storage);
    BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);
    ++histo[code];
  } else {
    BrotliWriteBits(depth[39], bits[39], storage_ix, storage);
    BrotliWriteBits(24, copylen - 2118, storage_ix, storage);
    ++histo[39];
  }
}

static BROTLI_INLINE void EmitCopyLenLastDistance(size_t copylen,
                                                  const uint8_t depth[128],
                                                  const uint16_t bits[128],
                                                  uint32_t histo[128],
                                                  size_t* storage_ix,
                                                  uint8_t* storage) {
  if (copylen < 12) {
    BrotliWriteBits(depth[copylen - 4], bits[copylen - 4], storage_ix, storage);
    ++histo[copylen - 4];
  } else if (copylen < 72) {
    const size_t tail = copylen - 8;
    const uint32_t nbits = Log2FloorNonZero(tail) - 1;
    const size_t prefix = tail >> nbits;
    const size_t code = (nbits << 1) + prefix + 4;
    BrotliWriteBits(depth[code], bits[code], storage_ix, storage);
    BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);
    ++histo[code];
  } else if (copylen < 136) {
    const size_t tail = copylen - 8;
    const size_t code = (tail >> 5) + 30;
    BrotliWriteBits(depth[code], bits[code], storage_ix, storage);
    BrotliWriteBits(5, tail & 31, storage_ix, storage);
    BrotliWriteBits(depth[64], bits[64], storage_ix, storage);
    ++histo[code];
    ++histo[64];
  } else if (copylen < 2120) {
    const size_t tail = copylen - 72;
    const uint32_t nbits = Log2FloorNonZero(tail);
    const size_t code = nbits + 28;
    BrotliWriteBits(depth[code], bits[code], storage_ix, storage);
    BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);
    BrotliWriteBits(depth[64], bits[64], storage_ix, storage);
    ++histo[code];
    ++histo[64];
  } else {
    BrotliWriteBits(depth[39], bits[39], storage_ix, storage);
    BrotliWriteBits(24, copylen - 2120, storage_ix, storage);
    BrotliWriteBits(depth[64], bits[64], storage_ix, storage);
    ++histo[39];
    ++histo[64];
  }
}

static BROTLI_INLINE void EmitDistance(size_t distance,
                                       const uint8_t depth[128],
                                       const uint16_t bits[128],
                                       uint32_t histo[128],
                                       size_t* storage_ix, uint8_t* storage) {
  const size_t d = distance + 3;
  const uint32_t nbits = Log2FloorNonZero(d) - 1u;
  const size_t prefix = (d >> nbits) & 1;
  const size_t offset = (2 + prefix) << nbits;
  const size_t distcode = 2 * (nbits - 1) + prefix + 80;
  BrotliWriteBits(depth[distcode], bits[distcode], storage_ix, storage);
  BrotliWriteBits(nbits, d - offset, storage_ix, storage);
  ++histo[distcode];
}

static BROTLI_INLINE void EmitLiterals(const uint8_t* input, const size_t len,
                                       const uint8_t depth[256],
                                       const uint16_t bits[256],
                                       size_t* storage_ix, uint8_t* storage) {
  size_t j;
  for (j = 0; j < len; j++) {
    const uint8_t lit = input[j];
    BrotliWriteBits(depth[lit], bits[lit], storage_ix, storage);
  }
}

/* REQUIRES: len <= 1 << 24. */
static void BrotliStoreMetaBlockHeader(
    size_t len, BROTLI_BOOL is_uncompressed, size_t* storage_ix,
    uint8_t* storage) {
  size_t nibbles = 6;
  /* ISLAST */
  BrotliWriteBits(1, 0, storage_ix, storage);
  if (len <= (1U << 16)) {
    nibbles = 4;
  } else if (len <= (1U << 20)) {
    nibbles = 5;
  }
  BrotliWriteBits(2, nibbles - 4, storage_ix, storage);
  BrotliWriteBits(nibbles * 4, len - 1, storage_ix, storage);
  /* ISUNCOMPRESSED */
  BrotliWriteBits(1, (uint64_t)is_uncompressed, storage_ix, storage);
}

static void UpdateBits(size_t n_bits, uint32_t bits, size_t pos,
    uint8_t* array) {
  while (n_bits > 0) {
    size_t byte_pos = pos >> 3;
    size_t n_unchanged_bits = pos & 7;
    size_t n_changed_bits = BROTLI_MIN(size_t, n_bits, 8 - n_unchanged_bits);
    size_t total_bits = n_unchanged_bits + n_changed_bits;
    uint32_t mask =
        (~((1u << total_bits) - 1u)) | ((1u << n_unchanged_bits) - 1u);
    uint32_t unchanged_bits = array[byte_pos] & mask;
    uint32_t changed_bits = bits & ((1u << n_changed_bits) - 1u);
    array[byte_pos] =
        (uint8_t)((changed_bits << n_unchanged_bits) | unchanged_bits);
    n_bits -= n_changed_bits;
    bits >>= n_changed_bits;
    pos += n_changed_bits;
  }
}

static void RewindBitPosition(const size_t new_storage_ix,
                              size_t* storage_ix, uint8_t* storage) {
  const size_t bitpos = new_storage_ix & 7;
  const size_t mask = (1u << bitpos) - 1;
  storage[new_storage_ix >> 3] &= (uint8_t)mask;
  *storage_ix = new_storage_ix;
}

static BROTLI_BOOL ShouldMergeBlock(
    const uint8_t* data, size_t len, const uint8_t* depths) {
  size_t histo[256] = { 0 };
  static const size_t kSampleRate = 43;
  size_t i;
  for (i = 0; i < len; i += kSampleRate) {
    ++histo[data[i]];
  }
  {
    const size_t total = (len + kSampleRate - 1) / kSampleRate;
    double r = (FastLog2(total) + 0.5) * (double)total + 200;
    for (i = 0; i < 256; ++i) {
      r -= (double)histo[i] * (depths[i] + FastLog2(histo[i]));
    }
    return TO_BROTLI_BOOL(r >= 0.0);
  }
}

/* Acceptable loss for uncompressible speedup is 2% */
#define MIN_RATIO 980

static BROTLI_INLINE BROTLI_BOOL ShouldUseUncompressedMode(
    const uint8_t* metablock_start, const uint8_t* next_emit,
    const size_t insertlen, const size_t literal_ratio) {
  const size_t compressed = (size_t)(next_emit - metablock_start);
  if (compressed * 50 > insertlen) {
    return BROTLI_FALSE;
  } else {
    return TO_BROTLI_BOOL(literal_ratio > MIN_RATIO);
  }
}

static void EmitUncompressedMetaBlock(const uint8_t* begin, const uint8_t* end,
                                      const size_t storage_ix_start,
                                      size_t* storage_ix, uint8_t* storage) {
  const size_t len = (size_t)(end - begin);
  RewindBitPosition(storage_ix_start, storage_ix, storage);
  BrotliStoreMetaBlockHeader(len, 1, storage_ix, storage);
  *storage_ix = (*storage_ix + 7u) & ~7u;
  memcpy(&storage[*storage_ix >> 3], begin, len);
  *storage_ix += len << 3;
  storage[*storage_ix >> 3] = 0;
}

static uint32_t kCmdHistoSeed[128] = {
  0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,
  0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
  1, 1, 1, 1, 0, 0, 0, 0,
};

static BROTLI_INLINE void BrotliCompressFragmentFastImpl(
    MemoryManager* m, const uint8_t* input, size_t input_size,
    BROTLI_BOOL is_last, int* table, size_t table_bits, 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) {
  uint32_t cmd_histo[128];
  const uint8_t* ip_end;

  /* "next_emit" is a pointer to the first byte that is not covered by a
     previous copy. Bytes between "next_emit" and the start of the next copy or
     the end of the input will be emitted as literal bytes. */
  const uint8_t* next_emit = input;
  /* Save the start of the first block for position and distance computations.
  */
  const uint8_t* base_ip = input;

  static const size_t kFirstBlockSize = 3 << 15;
  static const size_t kMergeBlockSize = 1 << 16;

  const size_t kInputMarginBytes = BROTLI_WINDOW_GAP;
  const size_t kMinMatchLen = 5;

  const uint8_t* metablock_start = input;
  size_t block_size = BROTLI_MIN(size_t, input_size, kFirstBlockSize);
  size_t total_block_size = block_size;
  /* Save the bit position of the MLEN field of the meta-block header, so that
     we can update it later if we decide to extend this meta-block. */
  size_t mlen_storage_ix = *storage_ix + 3;

  uint8_t lit_depth[256];
  uint16_t lit_bits[256];

  size_t literal_ratio;

  const uint8_t* ip;
  int last_distance;

  const size_t shift = 64u - table_bits;

  BrotliStoreMetaBlockHeader(block_size, 0, storage_ix, storage);
  /* No block splits, no contexts. */
  BrotliWriteBits(13, 0, storage_ix, storage);

  literal_ratio = BuildAndStoreLiteralPrefixCode(
      m, input, block_size, lit_depth, lit_bits, storage_ix, storage);
  if (BROTLI_IS_OOM(m)) return;

  {
    /* Store the pre-compressed command and distance prefix codes. */
    size_t i;
    for (i = 0; i + 7 < *cmd_code_numbits; i += 8) {
      BrotliWriteBits(8, cmd_code[i >> 3], storage_ix, storage);
    }
  }
  BrotliWriteBits(*cmd_code_numbits & 7, cmd_code[*cmd_code_numbits >> 3],
                  storage_ix, storage);

 emit_commands:
  /* Initialize the command and distance histograms. We will gather
     statistics of command and distance codes during the processing
     of this block and use it to update the command and distance
     prefix codes for the next block. */
  memcpy(cmd_histo, kCmdHistoSeed, sizeof(kCmdHistoSeed));

  /* "ip" is the input pointer. */
  ip = input;
  last_distance = -1;
  ip_end = input + block_size;

  if (BROTLI_PREDICT_TRUE(block_size >= kInputMarginBytes)) {
    /* For the last block, we need to keep a 16 bytes margin so that we can be
       sure that all distances are at most window size - 16.
       For all other blocks, we only need to keep a margin of 5 bytes so that
       we don't go over the block size with a copy. */
    const size_t len_limit = BROTLI_MIN(size_t, block_size - kMinMatchLen,
                                        input_size - kInputMarginBytes);
    const uint8_t* ip_limit = input + len_limit;

    uint32_t next_hash;
    for (next_hash = Hash(++ip, shift); ; ) {
      /* Step 1: Scan forward in the input looking for a 5-byte-long match.
         If we get close to exhausting the input then goto emit_remainder.

         Heuristic match skipping: If 32 bytes are scanned with no matches
         found, start looking only at every other byte. If 32 more bytes are
         scanned, look at every third byte, etc.. When a match is found,
         immediately go back to looking at every byte. This is a small loss
         (~5% performance, ~0.1% density) for compressible data due to more
         bookkeeping, but for non-compressible data (such as JPEG) it's a huge
         win since the compressor quickly "realizes" the data is incompressible
         and doesn't bother looking for matches everywhere.

         The "skip" variable keeps track of how many bytes there are since the
         last match; dividing it by 32 (i.e. right-shifting by five) gives the
         number of bytes to move ahead for each iteration. */
      uint32_t skip = 32;

      const uint8_t* next_ip = ip;
      const uint8_t* candidate;
      BROTLI_DCHECK(next_emit < ip);
trawl:
      do {
        uint32_t hash = next_hash;
        uint32_t bytes_between_hash_lookups = skip++ >> 5;
        BROTLI_DCHECK(hash == Hash(next_ip, shift));
        ip = next_ip;
        next_ip = ip + bytes_between_hash_lookups;
        if (BROTLI_PREDICT_FALSE(next_ip > ip_limit)) {
          goto emit_remainder;
        }
        next_hash = Hash(next_ip, shift);
        candidate = ip - last_distance;
        if (IsMatch(ip, candidate)) {
          if (BROTLI_PREDICT_TRUE(candidate < ip)) {
            table[hash] = (int)(ip - base_ip);
            break;
          }
        }
        candidate = base_ip + table[hash];
        BROTLI_DCHECK(candidate >= base_ip);
        BROTLI_DCHECK(candidate < ip);

        table[hash] = (int)(ip - base_ip);
      } while (BROTLI_PREDICT_TRUE(!IsMatch(ip, candidate)));

      /* Check copy distance. If candidate is not feasible, continue search.
         Checking is done outside of hot loop to reduce overhead. */
      if (ip - candidate > MAX_DISTANCE) goto trawl;

      /* Step 2: Emit the found match together with the literal bytes from
         "next_emit" to the bit stream, and then see if we can find a next match
         immediately afterwards. Repeat until we find no match for the input
         without emitting some literal bytes. */

      {
        /* We have a 5-byte match at ip, and we need to emit bytes in
           [next_emit, ip). */
        const uint8_t* base = ip;
        size_t matched = 5 + FindMatchLengthWithLimit(
            candidate + 5, ip + 5, (size_t)(ip_end - ip) - 5);
        int distance = (int)(base - candidate);  /* > 0 */
        size_t insert = (size_t)(base - next_emit);
        ip += matched;
        BROTLI_DCHECK(0 == memcmp(base, candidate, matched));
        if (BROTLI_PREDICT_TRUE(insert < 6210)) {
          EmitInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,
                        storage_ix, storage);
        } else if (ShouldUseUncompressedMode(metablock_start, next_emit, insert,
                                             literal_ratio)) {
          EmitUncompressedMetaBlock(metablock_start, base, mlen_storage_ix - 3,
                                    storage_ix, storage);
          input_size -= (size_t)(base - input);
          input = base;
          next_emit = input;
          goto next_block;
        } else {
          EmitLongInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,
                            storage_ix, storage);
        }
        EmitLiterals(next_emit, insert, lit_depth, lit_bits,
                     storage_ix, storage);
        if (distance == last_distance) {
          BrotliWriteBits(cmd_depth[64], cmd_bits[64], storage_ix, storage);
          ++cmd_histo[64];
        } else {
          EmitDistance((size_t)distance, cmd_depth, cmd_bits,
                       cmd_histo, storage_ix, storage);
          last_distance = distance;
        }
        EmitCopyLenLastDistance(matched, cmd_depth, cmd_bits, cmd_histo,
                                storage_ix, storage);

        next_emit = ip;
        if (BROTLI_PREDICT_FALSE(ip >= ip_limit)) {
          goto emit_remainder;
        }
        /* We could immediately start working at ip now, but to improve
           compression we first update "table" with the hashes of some positions
           within the last copy. */
        {
          uint64_t input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 3);
          uint32_t prev_hash = HashBytesAtOffset(input_bytes, 0, shift);
          uint32_t cur_hash = HashBytesAtOffset(input_bytes, 3, shift);
          table[prev_hash] = (int)(ip - base_ip - 3);
          prev_hash = HashBytesAtOffset(input_bytes, 1, shift);
          table[prev_hash] = (int)(ip - base_ip - 2);
          prev_hash = HashBytesAtOffset(input_bytes, 2, shift);
          table[prev_hash] = (int)(ip - base_ip - 1);

          candidate = base_ip + table[cur_hash];
          table[cur_hash] = (int)(ip - base_ip);
        }
      }

      while (IsMatch(ip, candidate)) {
        /* We have a 5-byte match at ip, and no need to emit any literal bytes
           prior to ip. */
        const uint8_t* base = ip;
        size_t matched = 5 + FindMatchLengthWithLimit(
            candidate + 5, ip + 5, (size_t)(ip_end - ip) - 5);
        if (ip - candidate > MAX_DISTANCE) break;
        ip += matched;
        last_distance = (int)(base - candidate);  /* > 0 */
        BROTLI_DCHECK(0 == memcmp(base, candidate, matched));
        EmitCopyLen(matched, cmd_depth, cmd_bits, cmd_histo,
                    storage_ix, storage);
        EmitDistance((size_t)last_distance, cmd_depth, cmd_bits,
                     cmd_histo, storage_ix, storage);

        next_emit = ip;
        if (BROTLI_PREDICT_FALSE(ip >= ip_limit)) {
          goto emit_remainder;
        }
        /* We could immediately start working at ip now, but to improve
           compression we first update "table" with the hashes of some positions
           within the last copy. */
        {
          uint64_t input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 3);
          uint32_t prev_hash = HashBytesAtOffset(input_bytes, 0, shift);
          uint32_t cur_hash = HashBytesAtOffset(input_bytes, 3, shift);
          table[prev_hash] = (int)(ip - base_ip - 3);
          prev_hash = HashBytesAtOffset(input_bytes, 1, shift);
          table[prev_hash] = (int)(ip - base_ip - 2);
          prev_hash = HashBytesAtOffset(input_bytes, 2, shift);
          table[prev_hash] = (int)(ip - base_ip - 1);

          candidate = base_ip + table[cur_hash];
          table[cur_hash] = (int)(ip - base_ip);
        }
      }

      next_hash = Hash(++ip, shift);
    }
  }

 emit_remainder:
  BROTLI_DCHECK(next_emit <= ip_end);
  input += block_size;
  input_size -= block_size;
  block_size = BROTLI_MIN(size_t, input_size, kMergeBlockSize);

  /* Decide if we want to continue this meta-block instead of emitting the
     last insert-only command. */
  if (input_size > 0 &&
      total_block_size + block_size <= (1 << 20) &&
      ShouldMergeBlock(input, block_size, lit_depth)) {
    BROTLI_DCHECK(total_block_size > (1 << 16));
    /* Update the size of the current meta-block and continue emitting commands.
       We can do this because the current size and the new size both have 5
       nibbles. */
    total_block_size += block_size;
    UpdateBits(20, (uint32_t)(total_block_size - 1), mlen_storage_ix, storage);
    goto emit_commands;
  }

  /* Emit the remaining bytes as literals. */
  if (next_emit < ip_end) {
    const size_t insert = (size_t)(ip_end - next_emit);
    if (BROTLI_PREDICT_TRUE(insert < 6210)) {
      EmitInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,
                    storage_ix, storage);
      EmitLiterals(next_emit, insert, lit_depth, lit_bits, storage_ix, storage);
    } else if (ShouldUseUncompressedMode(metablock_start, next_emit, insert,
                                         literal_ratio)) {
      EmitUncompressedMetaBlock(metablock_start, ip_end, mlen_storage_ix - 3,
                                storage_ix, storage);
    } else {
      EmitLongInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,
                        storage_ix, storage);
      EmitLiterals(next_emit, insert, lit_depth, lit_bits,
                   storage_ix, storage);
    }
  }
  next_emit = ip_end;

next_block:
  /* If we have more data, write a new meta-block header and prefix codes and
     then continue emitting commands. */
  if (input_size > 0) {
    metablock_start = input;
    block_size = BROTLI_MIN(size_t, input_size, kFirstBlockSize);
    total_block_size = block_size;
    /* Save the bit position of the MLEN field of the meta-block header, so that
       we can update it later if we decide to extend this meta-block. */
    mlen_storage_ix = *storage_ix + 3;
    BrotliStoreMetaBlockHeader(block_size, 0, storage_ix, storage);
    /* No block splits, no contexts. */
    BrotliWriteBits(13, 0, storage_ix, storage);
    literal_ratio = BuildAndStoreLiteralPrefixCode(
        m, input, block_size, lit_depth, lit_bits, storage_ix, storage);
    if (BROTLI_IS_OOM(m)) return;
    BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depth, cmd_bits,
                                   storage_ix, storage);
    goto emit_commands;
  }

  if (!is_last) {
    /* If this is not the last block, update the command and distance prefix
       codes for the next block and store the compressed forms. */
    cmd_code[0] = 0;
    *cmd_code_numbits = 0;
    BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depth, cmd_bits,
                                   cmd_code_numbits, cmd_code);
  }
}

#define FOR_TABLE_BITS_(X) X(9) X(11) X(13) X(15)

#define BAKE_METHOD_PARAM_(B) \
static BROTLI_NOINLINE void BrotliCompressFragmentFastImpl ## B(             \
    MemoryManager* m, const uint8_t* input, size_t input_size,               \
    BROTLI_BOOL is_last, int* table, 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) {                                  \
  BrotliCompressFragmentFastImpl(m, input, input_size, is_last, table, B,    \
      cmd_depth, cmd_bits, cmd_code_numbits, cmd_code, storage_ix, storage); \
}
FOR_TABLE_BITS_(BAKE_METHOD_PARAM_)
#undef BAKE_METHOD_PARAM_

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) {
  const size_t initial_storage_ix = *storage_ix;
  const size_t table_bits = Log2FloorNonZero(table_size);

  if (input_size == 0) {
    BROTLI_DCHECK(is_last);
    BrotliWriteBits(1, 1, storage_ix, storage);  /* islast */
    BrotliWriteBits(1, 1, storage_ix, storage);  /* isempty */
    *storage_ix = (*storage_ix + 7u) & ~7u;
    return;
  }

  switch (table_bits) {
#define CASE_(B)                                                     \
    case B:                                                          \
      BrotliCompressFragmentFastImpl ## B(                           \
          m, input, input_size, is_last, table, cmd_depth, cmd_bits, \
          cmd_code_numbits, cmd_code, storage_ix, storage);          \
      break;
    FOR_TABLE_BITS_(CASE_)
#undef CASE_
    default: BROTLI_DCHECK(0); break;
  }

  /* If output is larger than single uncompressed block, rewrite it. */
  if (*storage_ix - initial_storage_ix > 31 + (input_size << 3)) {
    EmitUncompressedMetaBlock(input, input + input_size, initial_storage_ix,
                              storage_ix, storage);
  }

  if (is_last) {
    BrotliWriteBits(1, 1, storage_ix, storage);  /* islast */
    BrotliWriteBits(1, 1, storage_ix, storage);  /* isempty */
    *storage_ix = (*storage_ix + 7u) & ~7u;
  }
}

#undef FOR_TABLE_BITS_

#if defined(__cplusplus) || defined(c_plusplus)
}  /* extern "C" */
#endif