summaryrefslogtreecommitdiffstats
path: root/modules/brotli/enc/compress_fragment_two_pass.c
diff options
context:
space:
mode:
Diffstat (limited to 'modules/brotli/enc/compress_fragment_two_pass.c')
-rw-r--r--modules/brotli/enc/compress_fragment_two_pass.c645
1 files changed, 645 insertions, 0 deletions
diff --git a/modules/brotli/enc/compress_fragment_two_pass.c b/modules/brotli/enc/compress_fragment_two_pass.c
new file mode 100644
index 000000000..f8a560638
--- /dev/null
+++ b/modules/brotli/enc/compress_fragment_two_pass.c
@@ -0,0 +1,645 @@
+/* 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 two-pass processing: in the first pass we save
+ the found backward matches and literal bytes into a buffer, and in the
+ second pass we emit them into the bit stream using prefix codes built based
+ on the actual command and literal byte histograms. */
+
+#include "./compress_fragment_two_pass.h"
+
+#include <string.h> /* memcmp, memcpy, memset */
+
+#include "../common/constants.h"
+#include "../common/platform.h"
+#include <brotli/types.h>
+#include "./bit_cost.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, size_t length) {
+ const uint64_t h =
+ (BROTLI_UNALIGNED_LOAD64LE(p) << ((8 - length) * 8)) * kHashMul32;
+ return (uint32_t)(h >> shift);
+}
+
+static BROTLI_INLINE uint32_t HashBytesAtOffset(uint64_t v, size_t offset,
+ size_t shift, size_t length) {
+ BROTLI_DCHECK(offset <= 8 - length);
+ {
+ const uint64_t h = ((v >> (8 * offset)) << ((8 - length) * 8)) * kHashMul32;
+ return (uint32_t)(h >> shift);
+ }
+}
+
+static BROTLI_INLINE BROTLI_BOOL IsMatch(const uint8_t* p1, const uint8_t* p2,
+ size_t length) {
+ if (BrotliUnalignedRead32(p1) == BrotliUnalignedRead32(p2)) {
+ if (length == 4) return BROTLI_TRUE;
+ return TO_BROTLI_BOOL(p1[4] == p2[4] && p1[5] == p2[5]);
+ }
+ return BROTLI_FALSE;
+}
+
+/* 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, 24);
+ memcpy(cmd_depth + 24, depth, 8);
+ memcpy(cmd_depth + 32, depth + 48, 8);
+ memcpy(cmd_depth + 40, depth + 8, 8);
+ memcpy(cmd_depth + 48, depth + 56, 8);
+ memcpy(cmd_depth + 56, depth + 16, 8);
+ BrotliConvertBitDepthsToSymbols(cmd_depth, 64, cmd_bits);
+ memcpy(bits, cmd_bits + 24, 16);
+ memcpy(bits + 8, cmd_bits + 40, 16);
+ memcpy(bits + 16, cmd_bits + 56, 16);
+ memcpy(bits + 24, cmd_bits, 48);
+ memcpy(bits + 48, cmd_bits + 32, 16);
+ memcpy(bits + 56, cmd_bits + 48, 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 + 24, 8);
+ memcpy(cmd_depth + 64, depth + 32, 8);
+ memcpy(cmd_depth + 128, depth + 40, 8);
+ memcpy(cmd_depth + 192, depth + 48, 8);
+ memcpy(cmd_depth + 384, depth + 56, 8);
+ for (i = 0; i < 8; ++i) {
+ cmd_depth[128 + 8 * i] = depth[i];
+ cmd_depth[256 + 8 * i] = depth[8 + i];
+ cmd_depth[448 + 8 * i] = depth[16 + i];
+ }
+ BrotliStoreHuffmanTree(
+ cmd_depth, BROTLI_NUM_COMMAND_SYMBOLS, tree, storage_ix, storage);
+ }
+ BrotliStoreHuffmanTree(&depth[64], 64, tree, storage_ix, storage);
+}
+
+static BROTLI_INLINE void EmitInsertLen(
+ uint32_t insertlen, uint32_t** commands) {
+ if (insertlen < 6) {
+ **commands = insertlen;
+ } else if (insertlen < 130) {
+ const uint32_t tail = insertlen - 2;
+ const uint32_t nbits = Log2FloorNonZero(tail) - 1u;
+ const uint32_t prefix = tail >> nbits;
+ const uint32_t inscode = (nbits << 1) + prefix + 2;
+ const uint32_t extra = tail - (prefix << nbits);
+ **commands = inscode | (extra << 8);
+ } else if (insertlen < 2114) {
+ const uint32_t tail = insertlen - 66;
+ const uint32_t nbits = Log2FloorNonZero(tail);
+ const uint32_t code = nbits + 10;
+ const uint32_t extra = tail - (1u << nbits);
+ **commands = code | (extra << 8);
+ } else if (insertlen < 6210) {
+ const uint32_t extra = insertlen - 2114;
+ **commands = 21 | (extra << 8);
+ } else if (insertlen < 22594) {
+ const uint32_t extra = insertlen - 6210;
+ **commands = 22 | (extra << 8);
+ } else {
+ const uint32_t extra = insertlen - 22594;
+ **commands = 23 | (extra << 8);
+ }
+ ++(*commands);
+}
+
+static BROTLI_INLINE void EmitCopyLen(size_t copylen, uint32_t** commands) {
+ if (copylen < 10) {
+ **commands = (uint32_t)(copylen + 38);
+ } else if (copylen < 134) {
+ const size_t tail = copylen - 6;
+ const size_t nbits = Log2FloorNonZero(tail) - 1;
+ const size_t prefix = tail >> nbits;
+ const size_t code = (nbits << 1) + prefix + 44;
+ const size_t extra = tail - (prefix << nbits);
+ **commands = (uint32_t)(code | (extra << 8));
+ } else if (copylen < 2118) {
+ const size_t tail = copylen - 70;
+ const size_t nbits = Log2FloorNonZero(tail);
+ const size_t code = nbits + 52;
+ const size_t extra = tail - ((size_t)1 << nbits);
+ **commands = (uint32_t)(code | (extra << 8));
+ } else {
+ const size_t extra = copylen - 2118;
+ **commands = (uint32_t)(63 | (extra << 8));
+ }
+ ++(*commands);
+}
+
+static BROTLI_INLINE void EmitCopyLenLastDistance(
+ size_t copylen, uint32_t** commands) {
+ if (copylen < 12) {
+ **commands = (uint32_t)(copylen + 20);
+ ++(*commands);
+ } else if (copylen < 72) {
+ const size_t tail = copylen - 8;
+ const size_t nbits = Log2FloorNonZero(tail) - 1;
+ const size_t prefix = tail >> nbits;
+ const size_t code = (nbits << 1) + prefix + 28;
+ const size_t extra = tail - (prefix << nbits);
+ **commands = (uint32_t)(code | (extra << 8));
+ ++(*commands);
+ } else if (copylen < 136) {
+ const size_t tail = copylen - 8;
+ const size_t code = (tail >> 5) + 54;
+ const size_t extra = tail & 31;
+ **commands = (uint32_t)(code | (extra << 8));
+ ++(*commands);
+ **commands = 64;
+ ++(*commands);
+ } else if (copylen < 2120) {
+ const size_t tail = copylen - 72;
+ const size_t nbits = Log2FloorNonZero(tail);
+ const size_t code = nbits + 52;
+ const size_t extra = tail - ((size_t)1 << nbits);
+ **commands = (uint32_t)(code | (extra << 8));
+ ++(*commands);
+ **commands = 64;
+ ++(*commands);
+ } else {
+ const size_t extra = copylen - 2120;
+ **commands = (uint32_t)(63 | (extra << 8));
+ ++(*commands);
+ **commands = 64;
+ ++(*commands);
+ }
+}
+
+static BROTLI_INLINE void EmitDistance(uint32_t distance, uint32_t** commands) {
+ uint32_t d = distance + 3;
+ uint32_t nbits = Log2FloorNonZero(d) - 1;
+ const uint32_t prefix = (d >> nbits) & 1;
+ const uint32_t offset = (2 + prefix) << nbits;
+ const uint32_t distcode = 2 * (nbits - 1) + prefix + 80;
+ uint32_t extra = d - offset;
+ **commands = distcode | (extra << 8);
+ ++(*commands);
+}
+
+/* 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 BROTLI_INLINE void CreateCommands(const uint8_t* input,
+ size_t block_size, size_t input_size, const uint8_t* base_ip, int* table,
+ size_t table_bits, size_t min_match,
+ uint8_t** literals, uint32_t** commands) {
+ /* "ip" is the input pointer. */
+ const uint8_t* ip = input;
+ const size_t shift = 64u - table_bits;
+ const uint8_t* ip_end = input + block_size;
+ /* "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;
+
+ int last_distance = -1;
+ const size_t kInputMarginBytes = BROTLI_WINDOW_GAP;
+
+ 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 - min_match,
+ input_size - kInputMarginBytes);
+ const uint8_t* ip_limit = input + len_limit;
+
+ uint32_t next_hash;
+ for (next_hash = Hash(++ip, shift, min_match); ; ) {
+ /* Step 1: Scan forward in the input looking for a 6-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 (ie. 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;
+ ip = next_ip;
+ BROTLI_DCHECK(hash == Hash(ip, shift, min_match));
+ next_ip = ip + bytes_between_hash_lookups;
+ if (BROTLI_PREDICT_FALSE(next_ip > ip_limit)) {
+ goto emit_remainder;
+ }
+ next_hash = Hash(next_ip, shift, min_match);
+ candidate = ip - last_distance;
+ if (IsMatch(ip, candidate, min_match)) {
+ 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, min_match)));
+
+ /* 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", 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 6-byte match at ip, and we need to emit bytes in
+ [next_emit, ip). */
+ const uint8_t* base = ip;
+ size_t matched = min_match + FindMatchLengthWithLimit(
+ candidate + min_match, ip + min_match,
+ (size_t)(ip_end - ip) - min_match);
+ int distance = (int)(base - candidate); /* > 0 */
+ int insert = (int)(base - next_emit);
+ ip += matched;
+ BROTLI_DCHECK(0 == memcmp(base, candidate, matched));
+ EmitInsertLen((uint32_t)insert, commands);
+ memcpy(*literals, next_emit, (size_t)insert);
+ *literals += insert;
+ if (distance == last_distance) {
+ **commands = 64;
+ ++(*commands);
+ } else {
+ EmitDistance((uint32_t)distance, commands);
+ last_distance = distance;
+ }
+ EmitCopyLenLastDistance(matched, commands);
+
+ 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;
+ uint32_t cur_hash;
+ uint32_t prev_hash;
+ if (min_match == 4) {
+ input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 3);
+ cur_hash = HashBytesAtOffset(input_bytes, 3, shift, min_match);
+ prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 3);
+ prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 2);
+ prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 1);
+ } else {
+ input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 5);
+ prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 5);
+ prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 4);
+ prev_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 3);
+ input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 2);
+ cur_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match);
+ prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 2);
+ prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 1);
+ }
+
+ candidate = base_ip + table[cur_hash];
+ table[cur_hash] = (int)(ip - base_ip);
+ }
+ }
+
+ while (ip - candidate <= MAX_DISTANCE &&
+ IsMatch(ip, candidate, min_match)) {
+ /* We have a 6-byte match at ip, and no need to emit any
+ literal bytes prior to ip. */
+ const uint8_t* base = ip;
+ size_t matched = min_match + FindMatchLengthWithLimit(
+ candidate + min_match, ip + min_match,
+ (size_t)(ip_end - ip) - min_match);
+ ip += matched;
+ last_distance = (int)(base - candidate); /* > 0 */
+ BROTLI_DCHECK(0 == memcmp(base, candidate, matched));
+ EmitCopyLen(matched, commands);
+ EmitDistance((uint32_t)last_distance, commands);
+
+ 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;
+ uint32_t cur_hash;
+ uint32_t prev_hash;
+ if (min_match == 4) {
+ input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 3);
+ cur_hash = HashBytesAtOffset(input_bytes, 3, shift, min_match);
+ prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 3);
+ prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 2);
+ prev_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 1);
+ } else {
+ input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 5);
+ prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 5);
+ prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 4);
+ prev_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 3);
+ input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 2);
+ cur_hash = HashBytesAtOffset(input_bytes, 2, shift, min_match);
+ prev_hash = HashBytesAtOffset(input_bytes, 0, shift, min_match);
+ table[prev_hash] = (int)(ip - base_ip - 2);
+ prev_hash = HashBytesAtOffset(input_bytes, 1, shift, min_match);
+ 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, min_match);
+ }
+ }
+
+emit_remainder:
+ BROTLI_DCHECK(next_emit <= ip_end);
+ /* Emit the remaining bytes as literals. */
+ if (next_emit < ip_end) {
+ const uint32_t insert = (uint32_t)(ip_end - next_emit);
+ EmitInsertLen(insert, commands);
+ memcpy(*literals, next_emit, insert);
+ *literals += insert;
+ }
+}
+
+static void StoreCommands(MemoryManager* m,
+ const uint8_t* literals, const size_t num_literals,
+ const uint32_t* commands, const size_t num_commands,
+ size_t* storage_ix, uint8_t* storage) {
+ static const uint32_t kNumExtraBits[128] = {
+ 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 12, 14, 24,
+ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4,
+ 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 7, 8, 9, 10, 24,
+ 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
+ 1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, 8, 8,
+ 9, 9, 10, 10, 11, 11, 12, 12, 13, 13, 14, 14, 15, 15, 16, 16,
+ 17, 17, 18, 18, 19, 19, 20, 20, 21, 21, 22, 22, 23, 23, 24, 24,
+ };
+ static const uint32_t kInsertOffset[24] = {
+ 0, 1, 2, 3, 4, 5, 6, 8, 10, 14, 18, 26, 34, 50, 66, 98, 130, 194, 322, 578,
+ 1090, 2114, 6210, 22594,
+ };
+
+ uint8_t lit_depths[256];
+ uint16_t lit_bits[256];
+ uint32_t lit_histo[256] = { 0 };
+ uint8_t cmd_depths[128] = { 0 };
+ uint16_t cmd_bits[128] = { 0 };
+ uint32_t cmd_histo[128] = { 0 };
+ size_t i;
+ for (i = 0; i < num_literals; ++i) {
+ ++lit_histo[literals[i]];
+ }
+ BrotliBuildAndStoreHuffmanTreeFast(m, lit_histo, num_literals,
+ /* max_bits = */ 8,
+ lit_depths, lit_bits,
+ storage_ix, storage);
+ if (BROTLI_IS_OOM(m)) return;
+
+ for (i = 0; i < num_commands; ++i) {
+ const uint32_t code = commands[i] & 0xFF;
+ BROTLI_DCHECK(code < 128);
+ ++cmd_histo[code];
+ }
+ cmd_histo[1] += 1;
+ cmd_histo[2] += 1;
+ cmd_histo[64] += 1;
+ cmd_histo[84] += 1;
+ BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depths, cmd_bits,
+ storage_ix, storage);
+
+ for (i = 0; i < num_commands; ++i) {
+ const uint32_t cmd = commands[i];
+ const uint32_t code = cmd & 0xFF;
+ const uint32_t extra = cmd >> 8;
+ BROTLI_DCHECK(code < 128);
+ BrotliWriteBits(cmd_depths[code], cmd_bits[code], storage_ix, storage);
+ BrotliWriteBits(kNumExtraBits[code], extra, storage_ix, storage);
+ if (code < 24) {
+ const uint32_t insert = kInsertOffset[code] + extra;
+ uint32_t j;
+ for (j = 0; j < insert; ++j) {
+ const uint8_t lit = *literals;
+ BrotliWriteBits(lit_depths[lit], lit_bits[lit], storage_ix, storage);
+ ++literals;
+ }
+ }
+ }
+}
+
+/* Acceptable loss for uncompressible speedup is 2% */
+#define MIN_RATIO 0.98
+#define SAMPLE_RATE 43
+
+static BROTLI_BOOL ShouldCompress(
+ const uint8_t* input, size_t input_size, size_t num_literals) {
+ double corpus_size = (double)input_size;
+ if (num_literals < MIN_RATIO * corpus_size) {
+ return BROTLI_TRUE;
+ } else {
+ uint32_t literal_histo[256] = { 0 };
+ const double max_total_bit_cost = corpus_size * 8 * MIN_RATIO / SAMPLE_RATE;
+ size_t i;
+ for (i = 0; i < input_size; i += SAMPLE_RATE) {
+ ++literal_histo[input[i]];
+ }
+ return TO_BROTLI_BOOL(BitsEntropy(literal_histo, 256) < max_total_bit_cost);
+ }
+}
+
+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 void EmitUncompressedMetaBlock(const uint8_t* input, size_t input_size,
+ size_t* storage_ix, uint8_t* storage) {
+ BrotliStoreMetaBlockHeader(input_size, 1, storage_ix, storage);
+ *storage_ix = (*storage_ix + 7u) & ~7u;
+ memcpy(&storage[*storage_ix >> 3], input, input_size);
+ *storage_ix += input_size << 3;
+ storage[*storage_ix >> 3] = 0;
+}
+
+static BROTLI_INLINE void BrotliCompressFragmentTwoPassImpl(
+ 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_bits, size_t min_match,
+ size_t* storage_ix, uint8_t* storage) {
+ /* Save the start of the first block for position and distance computations.
+ */
+ const uint8_t* base_ip = input;
+ BROTLI_UNUSED(is_last);
+
+ while (input_size > 0) {
+ size_t block_size =
+ BROTLI_MIN(size_t, input_size, kCompressFragmentTwoPassBlockSize);
+ uint32_t* commands = command_buf;
+ uint8_t* literals = literal_buf;
+ size_t num_literals;
+ CreateCommands(input, block_size, input_size, base_ip, table,
+ table_bits, min_match, &literals, &commands);
+ num_literals = (size_t)(literals - literal_buf);
+ if (ShouldCompress(input, block_size, num_literals)) {
+ const size_t num_commands = (size_t)(commands - command_buf);
+ BrotliStoreMetaBlockHeader(block_size, 0, storage_ix, storage);
+ /* No block splits, no contexts. */
+ BrotliWriteBits(13, 0, storage_ix, storage);
+ StoreCommands(m, literal_buf, num_literals, command_buf, num_commands,
+ storage_ix, storage);
+ if (BROTLI_IS_OOM(m)) return;
+ } else {
+ /* Since we did not find many backward references and the entropy of
+ the data is close to 8 bits, we can simply emit an uncompressed block.
+ This makes compression speed of uncompressible data about 3x faster. */
+ EmitUncompressedMetaBlock(input, block_size, storage_ix, storage);
+ }
+ input += block_size;
+ input_size -= block_size;
+ }
+}
+
+#define FOR_TABLE_BITS_(X) \
+ X(8) X(9) X(10) X(11) X(12) X(13) X(14) X(15) X(16) X(17)
+
+#define BAKE_METHOD_PARAM_(B) \
+static BROTLI_NOINLINE void BrotliCompressFragmentTwoPassImpl ## B( \
+ 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* storage_ix, uint8_t* storage) { \
+ size_t min_match = (B <= 15) ? 4 : 6; \
+ BrotliCompressFragmentTwoPassImpl(m, input, input_size, is_last, command_buf,\
+ literal_buf, table, B, min_match, storage_ix, storage); \
+}
+FOR_TABLE_BITS_(BAKE_METHOD_PARAM_)
+#undef BAKE_METHOD_PARAM_
+
+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) {
+ const size_t initial_storage_ix = *storage_ix;
+ const size_t table_bits = Log2FloorNonZero(table_size);
+ switch (table_bits) {
+#define CASE_(B) \
+ case B: \
+ BrotliCompressFragmentTwoPassImpl ## B( \
+ m, input, input_size, is_last, command_buf, \
+ literal_buf, table, 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)) {
+ RewindBitPosition(initial_storage_ix, storage_ix, storage);
+ EmitUncompressedMetaBlock(input, input_size, 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