+++ /dev/null
-/* Copyright 2015 Google Inc. All Rights Reserved.\r
-\r
- Distributed under MIT license.\r
- See file LICENSE for detail or copy at https://opensource.org/licenses/MIT\r
-*/\r
-\r
-/* Function for fast encoding of an input fragment, independently from the input\r
- history. This function uses one-pass processing: when we find a backward\r
- match, we immediately emit the corresponding command and literal codes to\r
- the bit stream.\r
-\r
- Adapted from the CompressFragment() function in\r
- https://github.com/google/snappy/blob/master/snappy.cc */\r
-\r
-#include "./compress_fragment.h"\r
-\r
-#include <string.h> /* memcmp, memcpy, memset */\r
-\r
-#include "../common/constants.h"\r
-#include "../common/platform.h"\r
-#include <brotli/types.h>\r
-#include "./brotli_bit_stream.h"\r
-#include "./entropy_encode.h"\r
-#include "./fast_log.h"\r
-#include "./find_match_length.h"\r
-#include "./memory.h"\r
-#include "./write_bits.h"\r
-\r
-#if defined(__cplusplus) || defined(c_plusplus)\r
-extern "C" {\r
-#endif\r
-\r
-#define MAX_DISTANCE (long)BROTLI_MAX_BACKWARD_LIMIT(18)\r
-\r
-/* kHashMul32 multiplier has these properties:\r
- * The multiplier must be odd. Otherwise we may lose the highest bit.\r
- * No long streaks of ones or zeros.\r
- * There is no effort to ensure that it is a prime, the oddity is enough\r
- for this use.\r
- * The number has been tuned heuristically against compression benchmarks. */\r
-static const uint32_t kHashMul32 = 0x1E35A7BD;\r
-\r
-static BROTLI_INLINE uint32_t Hash(const uint8_t* p, size_t shift) {\r
- const uint64_t h = (BROTLI_UNALIGNED_LOAD64LE(p) << 24) * kHashMul32;\r
- return (uint32_t)(h >> shift);\r
-}\r
-\r
-static BROTLI_INLINE uint32_t HashBytesAtOffset(\r
- uint64_t v, int offset, size_t shift) {\r
- BROTLI_DCHECK(offset >= 0);\r
- BROTLI_DCHECK(offset <= 3);\r
- {\r
- const uint64_t h = ((v >> (8 * offset)) << 24) * kHashMul32;\r
- return (uint32_t)(h >> shift);\r
- }\r
-}\r
-\r
-static BROTLI_INLINE BROTLI_BOOL IsMatch(const uint8_t* p1, const uint8_t* p2) {\r
- return TO_BROTLI_BOOL(\r
- BrotliUnalignedRead32(p1) == BrotliUnalignedRead32(p2) &&\r
- p1[4] == p2[4]);\r
-}\r
-\r
-/* Builds a literal prefix code into "depths" and "bits" based on the statistics\r
- of the "input" string and stores it into the bit stream.\r
- Note that the prefix code here is built from the pre-LZ77 input, therefore\r
- we can only approximate the statistics of the actual literal stream.\r
- Moreover, for long inputs we build a histogram from a sample of the input\r
- and thus have to assign a non-zero depth for each literal.\r
- Returns estimated compression ratio millibytes/char for encoding given input\r
- with generated code. */\r
-static size_t BuildAndStoreLiteralPrefixCode(MemoryManager* m,\r
- const uint8_t* input,\r
- const size_t input_size,\r
- uint8_t depths[256],\r
- uint16_t bits[256],\r
- size_t* storage_ix,\r
- uint8_t* storage) {\r
- uint32_t histogram[256] = { 0 };\r
- size_t histogram_total;\r
- size_t i;\r
- if (input_size < (1 << 15)) {\r
- for (i = 0; i < input_size; ++i) {\r
- ++histogram[input[i]];\r
- }\r
- histogram_total = input_size;\r
- for (i = 0; i < 256; ++i) {\r
- /* We weigh the first 11 samples with weight 3 to account for the\r
- balancing effect of the LZ77 phase on the histogram. */\r
- const uint32_t adjust = 2 * BROTLI_MIN(uint32_t, histogram[i], 11u);\r
- histogram[i] += adjust;\r
- histogram_total += adjust;\r
- }\r
- } else {\r
- static const size_t kSampleRate = 29;\r
- for (i = 0; i < input_size; i += kSampleRate) {\r
- ++histogram[input[i]];\r
- }\r
- histogram_total = (input_size + kSampleRate - 1) / kSampleRate;\r
- for (i = 0; i < 256; ++i) {\r
- /* We add 1 to each population count to avoid 0 bit depths (since this is\r
- only a sample and we don't know if the symbol appears or not), and we\r
- weigh the first 11 samples with weight 3 to account for the balancing\r
- effect of the LZ77 phase on the histogram (more frequent symbols are\r
- more likely to be in backward references instead as literals). */\r
- const uint32_t adjust = 1 + 2 * BROTLI_MIN(uint32_t, histogram[i], 11u);\r
- histogram[i] += adjust;\r
- histogram_total += adjust;\r
- }\r
- }\r
- BrotliBuildAndStoreHuffmanTreeFast(m, histogram, histogram_total,\r
- /* max_bits = */ 8,\r
- depths, bits, storage_ix, storage);\r
- if (BROTLI_IS_OOM(m)) return 0;\r
- {\r
- size_t literal_ratio = 0;\r
- for (i = 0; i < 256; ++i) {\r
- if (histogram[i]) literal_ratio += histogram[i] * depths[i];\r
- }\r
- /* Estimated encoding ratio, millibytes per symbol. */\r
- return (literal_ratio * 125) / histogram_total;\r
- }\r
-}\r
-\r
-/* Builds a command and distance prefix code (each 64 symbols) into "depth" and\r
- "bits" based on "histogram" and stores it into the bit stream. */\r
-static void BuildAndStoreCommandPrefixCode(const uint32_t histogram[128],\r
- uint8_t depth[128], uint16_t bits[128], size_t* storage_ix,\r
- uint8_t* storage) {\r
- /* Tree size for building a tree over 64 symbols is 2 * 64 + 1. */\r
- HuffmanTree tree[129];\r
- uint8_t cmd_depth[BROTLI_NUM_COMMAND_SYMBOLS] = { 0 };\r
- uint16_t cmd_bits[64];\r
-\r
- BrotliCreateHuffmanTree(histogram, 64, 15, tree, depth);\r
- BrotliCreateHuffmanTree(&histogram[64], 64, 14, tree, &depth[64]);\r
- /* We have to jump through a few hoops here in order to compute\r
- the command bits because the symbols are in a different order than in\r
- the full alphabet. This looks complicated, but having the symbols\r
- in this order in the command bits saves a few branches in the Emit*\r
- functions. */\r
- memcpy(cmd_depth, depth, 24);\r
- memcpy(cmd_depth + 24, depth + 40, 8);\r
- memcpy(cmd_depth + 32, depth + 24, 8);\r
- memcpy(cmd_depth + 40, depth + 48, 8);\r
- memcpy(cmd_depth + 48, depth + 32, 8);\r
- memcpy(cmd_depth + 56, depth + 56, 8);\r
- BrotliConvertBitDepthsToSymbols(cmd_depth, 64, cmd_bits);\r
- memcpy(bits, cmd_bits, 48);\r
- memcpy(bits + 24, cmd_bits + 32, 16);\r
- memcpy(bits + 32, cmd_bits + 48, 16);\r
- memcpy(bits + 40, cmd_bits + 24, 16);\r
- memcpy(bits + 48, cmd_bits + 40, 16);\r
- memcpy(bits + 56, cmd_bits + 56, 16);\r
- BrotliConvertBitDepthsToSymbols(&depth[64], 64, &bits[64]);\r
- {\r
- /* Create the bit length array for the full command alphabet. */\r
- size_t i;\r
- memset(cmd_depth, 0, 64); /* only 64 first values were used */\r
- memcpy(cmd_depth, depth, 8);\r
- memcpy(cmd_depth + 64, depth + 8, 8);\r
- memcpy(cmd_depth + 128, depth + 16, 8);\r
- memcpy(cmd_depth + 192, depth + 24, 8);\r
- memcpy(cmd_depth + 384, depth + 32, 8);\r
- for (i = 0; i < 8; ++i) {\r
- cmd_depth[128 + 8 * i] = depth[40 + i];\r
- cmd_depth[256 + 8 * i] = depth[48 + i];\r
- cmd_depth[448 + 8 * i] = depth[56 + i];\r
- }\r
- BrotliStoreHuffmanTree(\r
- cmd_depth, BROTLI_NUM_COMMAND_SYMBOLS, tree, storage_ix, storage);\r
- }\r
- BrotliStoreHuffmanTree(&depth[64], 64, tree, storage_ix, storage);\r
-}\r
-\r
-/* REQUIRES: insertlen < 6210 */\r
-static BROTLI_INLINE void EmitInsertLen(size_t insertlen,\r
- const uint8_t depth[128],\r
- const uint16_t bits[128],\r
- uint32_t histo[128],\r
- size_t* storage_ix,\r
- uint8_t* storage) {\r
- if (insertlen < 6) {\r
- const size_t code = insertlen + 40;\r
- BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r
- ++histo[code];\r
- } else if (insertlen < 130) {\r
- const size_t tail = insertlen - 2;\r
- const uint32_t nbits = Log2FloorNonZero(tail) - 1u;\r
- const size_t prefix = tail >> nbits;\r
- const size_t inscode = (nbits << 1) + prefix + 42;\r
- BrotliWriteBits(depth[inscode], bits[inscode], storage_ix, storage);\r
- BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);\r
- ++histo[inscode];\r
- } else if (insertlen < 2114) {\r
- const size_t tail = insertlen - 66;\r
- const uint32_t nbits = Log2FloorNonZero(tail);\r
- const size_t code = nbits + 50;\r
- BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r
- BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);\r
- ++histo[code];\r
- } else {\r
- BrotliWriteBits(depth[61], bits[61], storage_ix, storage);\r
- BrotliWriteBits(12, insertlen - 2114, storage_ix, storage);\r
- ++histo[61];\r
- }\r
-}\r
-\r
-static BROTLI_INLINE void EmitLongInsertLen(size_t insertlen,\r
- const uint8_t depth[128],\r
- const uint16_t bits[128],\r
- uint32_t histo[128],\r
- size_t* storage_ix,\r
- uint8_t* storage) {\r
- if (insertlen < 22594) {\r
- BrotliWriteBits(depth[62], bits[62], storage_ix, storage);\r
- BrotliWriteBits(14, insertlen - 6210, storage_ix, storage);\r
- ++histo[62];\r
- } else {\r
- BrotliWriteBits(depth[63], bits[63], storage_ix, storage);\r
- BrotliWriteBits(24, insertlen - 22594, storage_ix, storage);\r
- ++histo[63];\r
- }\r
-}\r
-\r
-static BROTLI_INLINE void EmitCopyLen(size_t copylen,\r
- const uint8_t depth[128],\r
- const uint16_t bits[128],\r
- uint32_t histo[128],\r
- size_t* storage_ix,\r
- uint8_t* storage) {\r
- if (copylen < 10) {\r
- BrotliWriteBits(\r
- depth[copylen + 14], bits[copylen + 14], storage_ix, storage);\r
- ++histo[copylen + 14];\r
- } else if (copylen < 134) {\r
- const size_t tail = copylen - 6;\r
- const uint32_t nbits = Log2FloorNonZero(tail) - 1u;\r
- const size_t prefix = tail >> nbits;\r
- const size_t code = (nbits << 1) + prefix + 20;\r
- BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r
- BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);\r
- ++histo[code];\r
- } else if (copylen < 2118) {\r
- const size_t tail = copylen - 70;\r
- const uint32_t nbits = Log2FloorNonZero(tail);\r
- const size_t code = nbits + 28;\r
- BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r
- BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);\r
- ++histo[code];\r
- } else {\r
- BrotliWriteBits(depth[39], bits[39], storage_ix, storage);\r
- BrotliWriteBits(24, copylen - 2118, storage_ix, storage);\r
- ++histo[39];\r
- }\r
-}\r
-\r
-static BROTLI_INLINE void EmitCopyLenLastDistance(size_t copylen,\r
- const uint8_t depth[128],\r
- const uint16_t bits[128],\r
- uint32_t histo[128],\r
- size_t* storage_ix,\r
- uint8_t* storage) {\r
- if (copylen < 12) {\r
- BrotliWriteBits(depth[copylen - 4], bits[copylen - 4], storage_ix, storage);\r
- ++histo[copylen - 4];\r
- } else if (copylen < 72) {\r
- const size_t tail = copylen - 8;\r
- const uint32_t nbits = Log2FloorNonZero(tail) - 1;\r
- const size_t prefix = tail >> nbits;\r
- const size_t code = (nbits << 1) + prefix + 4;\r
- BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r
- BrotliWriteBits(nbits, tail - (prefix << nbits), storage_ix, storage);\r
- ++histo[code];\r
- } else if (copylen < 136) {\r
- const size_t tail = copylen - 8;\r
- const size_t code = (tail >> 5) + 30;\r
- BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r
- BrotliWriteBits(5, tail & 31, storage_ix, storage);\r
- BrotliWriteBits(depth[64], bits[64], storage_ix, storage);\r
- ++histo[code];\r
- ++histo[64];\r
- } else if (copylen < 2120) {\r
- const size_t tail = copylen - 72;\r
- const uint32_t nbits = Log2FloorNonZero(tail);\r
- const size_t code = nbits + 28;\r
- BrotliWriteBits(depth[code], bits[code], storage_ix, storage);\r
- BrotliWriteBits(nbits, tail - ((size_t)1 << nbits), storage_ix, storage);\r
- BrotliWriteBits(depth[64], bits[64], storage_ix, storage);\r
- ++histo[code];\r
- ++histo[64];\r
- } else {\r
- BrotliWriteBits(depth[39], bits[39], storage_ix, storage);\r
- BrotliWriteBits(24, copylen - 2120, storage_ix, storage);\r
- BrotliWriteBits(depth[64], bits[64], storage_ix, storage);\r
- ++histo[39];\r
- ++histo[64];\r
- }\r
-}\r
-\r
-static BROTLI_INLINE void EmitDistance(size_t distance,\r
- const uint8_t depth[128],\r
- const uint16_t bits[128],\r
- uint32_t histo[128],\r
- size_t* storage_ix, uint8_t* storage) {\r
- const size_t d = distance + 3;\r
- const uint32_t nbits = Log2FloorNonZero(d) - 1u;\r
- const size_t prefix = (d >> nbits) & 1;\r
- const size_t offset = (2 + prefix) << nbits;\r
- const size_t distcode = 2 * (nbits - 1) + prefix + 80;\r
- BrotliWriteBits(depth[distcode], bits[distcode], storage_ix, storage);\r
- BrotliWriteBits(nbits, d - offset, storage_ix, storage);\r
- ++histo[distcode];\r
-}\r
-\r
-static BROTLI_INLINE void EmitLiterals(const uint8_t* input, const size_t len,\r
- const uint8_t depth[256],\r
- const uint16_t bits[256],\r
- size_t* storage_ix, uint8_t* storage) {\r
- size_t j;\r
- for (j = 0; j < len; j++) {\r
- const uint8_t lit = input[j];\r
- BrotliWriteBits(depth[lit], bits[lit], storage_ix, storage);\r
- }\r
-}\r
-\r
-/* REQUIRES: len <= 1 << 24. */\r
-static void BrotliStoreMetaBlockHeader(\r
- size_t len, BROTLI_BOOL is_uncompressed, size_t* storage_ix,\r
- uint8_t* storage) {\r
- size_t nibbles = 6;\r
- /* ISLAST */\r
- BrotliWriteBits(1, 0, storage_ix, storage);\r
- if (len <= (1U << 16)) {\r
- nibbles = 4;\r
- } else if (len <= (1U << 20)) {\r
- nibbles = 5;\r
- }\r
- BrotliWriteBits(2, nibbles - 4, storage_ix, storage);\r
- BrotliWriteBits(nibbles * 4, len - 1, storage_ix, storage);\r
- /* ISUNCOMPRESSED */\r
- BrotliWriteBits(1, (uint64_t)is_uncompressed, storage_ix, storage);\r
-}\r
-\r
-static void UpdateBits(size_t n_bits, uint32_t bits, size_t pos,\r
- uint8_t* array) {\r
- while (n_bits > 0) {\r
- size_t byte_pos = pos >> 3;\r
- size_t n_unchanged_bits = pos & 7;\r
- size_t n_changed_bits = BROTLI_MIN(size_t, n_bits, 8 - n_unchanged_bits);\r
- size_t total_bits = n_unchanged_bits + n_changed_bits;\r
- uint32_t mask =\r
- (~((1u << total_bits) - 1u)) | ((1u << n_unchanged_bits) - 1u);\r
- uint32_t unchanged_bits = array[byte_pos] & mask;\r
- uint32_t changed_bits = bits & ((1u << n_changed_bits) - 1u);\r
- array[byte_pos] =\r
- (uint8_t)((changed_bits << n_unchanged_bits) | unchanged_bits);\r
- n_bits -= n_changed_bits;\r
- bits >>= n_changed_bits;\r
- pos += n_changed_bits;\r
- }\r
-}\r
-\r
-static void RewindBitPosition(const size_t new_storage_ix,\r
- size_t* storage_ix, uint8_t* storage) {\r
- const size_t bitpos = new_storage_ix & 7;\r
- const size_t mask = (1u << bitpos) - 1;\r
- storage[new_storage_ix >> 3] &= (uint8_t)mask;\r
- *storage_ix = new_storage_ix;\r
-}\r
-\r
-static BROTLI_BOOL ShouldMergeBlock(\r
- const uint8_t* data, size_t len, const uint8_t* depths) {\r
- size_t histo[256] = { 0 };\r
- static const size_t kSampleRate = 43;\r
- size_t i;\r
- for (i = 0; i < len; i += kSampleRate) {\r
- ++histo[data[i]];\r
- }\r
- {\r
- const size_t total = (len + kSampleRate - 1) / kSampleRate;\r
- double r = (FastLog2(total) + 0.5) * (double)total + 200;\r
- for (i = 0; i < 256; ++i) {\r
- r -= (double)histo[i] * (depths[i] + FastLog2(histo[i]));\r
- }\r
- return TO_BROTLI_BOOL(r >= 0.0);\r
- }\r
-}\r
-\r
-/* Acceptable loss for uncompressible speedup is 2% */\r
-#define MIN_RATIO 980\r
-\r
-static BROTLI_INLINE BROTLI_BOOL ShouldUseUncompressedMode(\r
- const uint8_t* metablock_start, const uint8_t* next_emit,\r
- const size_t insertlen, const size_t literal_ratio) {\r
- const size_t compressed = (size_t)(next_emit - metablock_start);\r
- if (compressed * 50 > insertlen) {\r
- return BROTLI_FALSE;\r
- } else {\r
- return TO_BROTLI_BOOL(literal_ratio > MIN_RATIO);\r
- }\r
-}\r
-\r
-static void EmitUncompressedMetaBlock(const uint8_t* begin, const uint8_t* end,\r
- const size_t storage_ix_start,\r
- size_t* storage_ix, uint8_t* storage) {\r
- const size_t len = (size_t)(end - begin);\r
- RewindBitPosition(storage_ix_start, storage_ix, storage);\r
- BrotliStoreMetaBlockHeader(len, 1, storage_ix, storage);\r
- *storage_ix = (*storage_ix + 7u) & ~7u;\r
- memcpy(&storage[*storage_ix >> 3], begin, len);\r
- *storage_ix += len << 3;\r
- storage[*storage_ix >> 3] = 0;\r
-}\r
-\r
-static uint32_t kCmdHistoSeed[128] = {\r
- 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1,\r
- 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1,\r
- 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0,\r
- 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\r
- 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,\r
- 1, 1, 1, 1, 0, 0, 0, 0,\r
-};\r
-\r
-static BROTLI_INLINE void BrotliCompressFragmentFastImpl(\r
- MemoryManager* m, const uint8_t* input, size_t input_size,\r
- BROTLI_BOOL is_last, int* table, size_t table_bits, uint8_t cmd_depth[128],\r
- uint16_t cmd_bits[128], size_t* cmd_code_numbits, uint8_t* cmd_code,\r
- size_t* storage_ix, uint8_t* storage) {\r
- uint32_t cmd_histo[128];\r
- const uint8_t* ip_end;\r
-\r
- /* "next_emit" is a pointer to the first byte that is not covered by a\r
- previous copy. Bytes between "next_emit" and the start of the next copy or\r
- the end of the input will be emitted as literal bytes. */\r
- const uint8_t* next_emit = input;\r
- /* Save the start of the first block for position and distance computations.\r
- */\r
- const uint8_t* base_ip = input;\r
-\r
- static const size_t kFirstBlockSize = 3 << 15;\r
- static const size_t kMergeBlockSize = 1 << 16;\r
-\r
- const size_t kInputMarginBytes = BROTLI_WINDOW_GAP;\r
- const size_t kMinMatchLen = 5;\r
-\r
- const uint8_t* metablock_start = input;\r
- size_t block_size = BROTLI_MIN(size_t, input_size, kFirstBlockSize);\r
- size_t total_block_size = block_size;\r
- /* Save the bit position of the MLEN field of the meta-block header, so that\r
- we can update it later if we decide to extend this meta-block. */\r
- size_t mlen_storage_ix = *storage_ix + 3;\r
-\r
- uint8_t lit_depth[256];\r
- uint16_t lit_bits[256];\r
-\r
- size_t literal_ratio;\r
-\r
- const uint8_t* ip;\r
- int last_distance;\r
-\r
- const size_t shift = 64u - table_bits;\r
-\r
- BrotliStoreMetaBlockHeader(block_size, 0, storage_ix, storage);\r
- /* No block splits, no contexts. */\r
- BrotliWriteBits(13, 0, storage_ix, storage);\r
-\r
- literal_ratio = BuildAndStoreLiteralPrefixCode(\r
- m, input, block_size, lit_depth, lit_bits, storage_ix, storage);\r
- if (BROTLI_IS_OOM(m)) return;\r
-\r
- {\r
- /* Store the pre-compressed command and distance prefix codes. */\r
- size_t i;\r
- for (i = 0; i + 7 < *cmd_code_numbits; i += 8) {\r
- BrotliWriteBits(8, cmd_code[i >> 3], storage_ix, storage);\r
- }\r
- }\r
- BrotliWriteBits(*cmd_code_numbits & 7, cmd_code[*cmd_code_numbits >> 3],\r
- storage_ix, storage);\r
-\r
- emit_commands:\r
- /* Initialize the command and distance histograms. We will gather\r
- statistics of command and distance codes during the processing\r
- of this block and use it to update the command and distance\r
- prefix codes for the next block. */\r
- memcpy(cmd_histo, kCmdHistoSeed, sizeof(kCmdHistoSeed));\r
-\r
- /* "ip" is the input pointer. */\r
- ip = input;\r
- last_distance = -1;\r
- ip_end = input + block_size;\r
-\r
- if (BROTLI_PREDICT_TRUE(block_size >= kInputMarginBytes)) {\r
- /* For the last block, we need to keep a 16 bytes margin so that we can be\r
- sure that all distances are at most window size - 16.\r
- For all other blocks, we only need to keep a margin of 5 bytes so that\r
- we don't go over the block size with a copy. */\r
- const size_t len_limit = BROTLI_MIN(size_t, block_size - kMinMatchLen,\r
- input_size - kInputMarginBytes);\r
- const uint8_t* ip_limit = input + len_limit;\r
-\r
- uint32_t next_hash;\r
- for (next_hash = Hash(++ip, shift); ; ) {\r
- /* Step 1: Scan forward in the input looking for a 5-byte-long match.\r
- If we get close to exhausting the input then goto emit_remainder.\r
-\r
- Heuristic match skipping: If 32 bytes are scanned with no matches\r
- found, start looking only at every other byte. If 32 more bytes are\r
- scanned, look at every third byte, etc.. When a match is found,\r
- immediately go back to looking at every byte. This is a small loss\r
- (~5% performance, ~0.1% density) for compressible data due to more\r
- bookkeeping, but for non-compressible data (such as JPEG) it's a huge\r
- win since the compressor quickly "realizes" the data is incompressible\r
- and doesn't bother looking for matches everywhere.\r
-\r
- The "skip" variable keeps track of how many bytes there are since the\r
- last match; dividing it by 32 (i.e. right-shifting by five) gives the\r
- number of bytes to move ahead for each iteration. */\r
- uint32_t skip = 32;\r
-\r
- const uint8_t* next_ip = ip;\r
- const uint8_t* candidate;\r
- BROTLI_DCHECK(next_emit < ip);\r
-trawl:\r
- do {\r
- uint32_t hash = next_hash;\r
- uint32_t bytes_between_hash_lookups = skip++ >> 5;\r
- BROTLI_DCHECK(hash == Hash(next_ip, shift));\r
- ip = next_ip;\r
- next_ip = ip + bytes_between_hash_lookups;\r
- if (BROTLI_PREDICT_FALSE(next_ip > ip_limit)) {\r
- goto emit_remainder;\r
- }\r
- next_hash = Hash(next_ip, shift);\r
- candidate = ip - last_distance;\r
- if (IsMatch(ip, candidate)) {\r
- if (BROTLI_PREDICT_TRUE(candidate < ip)) {\r
- table[hash] = (int)(ip - base_ip);\r
- break;\r
- }\r
- }\r
- candidate = base_ip + table[hash];\r
- BROTLI_DCHECK(candidate >= base_ip);\r
- BROTLI_DCHECK(candidate < ip);\r
-\r
- table[hash] = (int)(ip - base_ip);\r
- } while (BROTLI_PREDICT_TRUE(!IsMatch(ip, candidate)));\r
-\r
- /* Check copy distance. If candidate is not feasible, continue search.\r
- Checking is done outside of hot loop to reduce overhead. */\r
- if (ip - candidate > MAX_DISTANCE) goto trawl;\r
-\r
- /* Step 2: Emit the found match together with the literal bytes from\r
- "next_emit" to the bit stream, and then see if we can find a next match\r
- immediately afterwards. Repeat until we find no match for the input\r
- without emitting some literal bytes. */\r
-\r
- {\r
- /* We have a 5-byte match at ip, and we need to emit bytes in\r
- [next_emit, ip). */\r
- const uint8_t* base = ip;\r
- size_t matched = 5 + FindMatchLengthWithLimit(\r
- candidate + 5, ip + 5, (size_t)(ip_end - ip) - 5);\r
- int distance = (int)(base - candidate); /* > 0 */\r
- size_t insert = (size_t)(base - next_emit);\r
- ip += matched;\r
- BROTLI_DCHECK(0 == memcmp(base, candidate, matched));\r
- if (BROTLI_PREDICT_TRUE(insert < 6210)) {\r
- EmitInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,\r
- storage_ix, storage);\r
- } else if (ShouldUseUncompressedMode(metablock_start, next_emit, insert,\r
- literal_ratio)) {\r
- EmitUncompressedMetaBlock(metablock_start, base, mlen_storage_ix - 3,\r
- storage_ix, storage);\r
- input_size -= (size_t)(base - input);\r
- input = base;\r
- next_emit = input;\r
- goto next_block;\r
- } else {\r
- EmitLongInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,\r
- storage_ix, storage);\r
- }\r
- EmitLiterals(next_emit, insert, lit_depth, lit_bits,\r
- storage_ix, storage);\r
- if (distance == last_distance) {\r
- BrotliWriteBits(cmd_depth[64], cmd_bits[64], storage_ix, storage);\r
- ++cmd_histo[64];\r
- } else {\r
- EmitDistance((size_t)distance, cmd_depth, cmd_bits,\r
- cmd_histo, storage_ix, storage);\r
- last_distance = distance;\r
- }\r
- EmitCopyLenLastDistance(matched, cmd_depth, cmd_bits, cmd_histo,\r
- storage_ix, storage);\r
-\r
- next_emit = ip;\r
- if (BROTLI_PREDICT_FALSE(ip >= ip_limit)) {\r
- goto emit_remainder;\r
- }\r
- /* We could immediately start working at ip now, but to improve\r
- compression we first update "table" with the hashes of some positions\r
- within the last copy. */\r
- {\r
- uint64_t input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 3);\r
- uint32_t prev_hash = HashBytesAtOffset(input_bytes, 0, shift);\r
- uint32_t cur_hash = HashBytesAtOffset(input_bytes, 3, shift);\r
- table[prev_hash] = (int)(ip - base_ip - 3);\r
- prev_hash = HashBytesAtOffset(input_bytes, 1, shift);\r
- table[prev_hash] = (int)(ip - base_ip - 2);\r
- prev_hash = HashBytesAtOffset(input_bytes, 2, shift);\r
- table[prev_hash] = (int)(ip - base_ip - 1);\r
-\r
- candidate = base_ip + table[cur_hash];\r
- table[cur_hash] = (int)(ip - base_ip);\r
- }\r
- }\r
-\r
- while (IsMatch(ip, candidate)) {\r
- /* We have a 5-byte match at ip, and no need to emit any literal bytes\r
- prior to ip. */\r
- const uint8_t* base = ip;\r
- size_t matched = 5 + FindMatchLengthWithLimit(\r
- candidate + 5, ip + 5, (size_t)(ip_end - ip) - 5);\r
- if (ip - candidate > MAX_DISTANCE) break;\r
- ip += matched;\r
- last_distance = (int)(base - candidate); /* > 0 */\r
- BROTLI_DCHECK(0 == memcmp(base, candidate, matched));\r
- EmitCopyLen(matched, cmd_depth, cmd_bits, cmd_histo,\r
- storage_ix, storage);\r
- EmitDistance((size_t)last_distance, cmd_depth, cmd_bits,\r
- cmd_histo, storage_ix, storage);\r
-\r
- next_emit = ip;\r
- if (BROTLI_PREDICT_FALSE(ip >= ip_limit)) {\r
- goto emit_remainder;\r
- }\r
- /* We could immediately start working at ip now, but to improve\r
- compression we first update "table" with the hashes of some positions\r
- within the last copy. */\r
- {\r
- uint64_t input_bytes = BROTLI_UNALIGNED_LOAD64LE(ip - 3);\r
- uint32_t prev_hash = HashBytesAtOffset(input_bytes, 0, shift);\r
- uint32_t cur_hash = HashBytesAtOffset(input_bytes, 3, shift);\r
- table[prev_hash] = (int)(ip - base_ip - 3);\r
- prev_hash = HashBytesAtOffset(input_bytes, 1, shift);\r
- table[prev_hash] = (int)(ip - base_ip - 2);\r
- prev_hash = HashBytesAtOffset(input_bytes, 2, shift);\r
- table[prev_hash] = (int)(ip - base_ip - 1);\r
-\r
- candidate = base_ip + table[cur_hash];\r
- table[cur_hash] = (int)(ip - base_ip);\r
- }\r
- }\r
-\r
- next_hash = Hash(++ip, shift);\r
- }\r
- }\r
-\r
- emit_remainder:\r
- BROTLI_DCHECK(next_emit <= ip_end);\r
- input += block_size;\r
- input_size -= block_size;\r
- block_size = BROTLI_MIN(size_t, input_size, kMergeBlockSize);\r
-\r
- /* Decide if we want to continue this meta-block instead of emitting the\r
- last insert-only command. */\r
- if (input_size > 0 &&\r
- total_block_size + block_size <= (1 << 20) &&\r
- ShouldMergeBlock(input, block_size, lit_depth)) {\r
- BROTLI_DCHECK(total_block_size > (1 << 16));\r
- /* Update the size of the current meta-block and continue emitting commands.\r
- We can do this because the current size and the new size both have 5\r
- nibbles. */\r
- total_block_size += block_size;\r
- UpdateBits(20, (uint32_t)(total_block_size - 1), mlen_storage_ix, storage);\r
- goto emit_commands;\r
- }\r
-\r
- /* Emit the remaining bytes as literals. */\r
- if (next_emit < ip_end) {\r
- const size_t insert = (size_t)(ip_end - next_emit);\r
- if (BROTLI_PREDICT_TRUE(insert < 6210)) {\r
- EmitInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,\r
- storage_ix, storage);\r
- EmitLiterals(next_emit, insert, lit_depth, lit_bits, storage_ix, storage);\r
- } else if (ShouldUseUncompressedMode(metablock_start, next_emit, insert,\r
- literal_ratio)) {\r
- EmitUncompressedMetaBlock(metablock_start, ip_end, mlen_storage_ix - 3,\r
- storage_ix, storage);\r
- } else {\r
- EmitLongInsertLen(insert, cmd_depth, cmd_bits, cmd_histo,\r
- storage_ix, storage);\r
- EmitLiterals(next_emit, insert, lit_depth, lit_bits,\r
- storage_ix, storage);\r
- }\r
- }\r
- next_emit = ip_end;\r
-\r
-next_block:\r
- /* If we have more data, write a new meta-block header and prefix codes and\r
- then continue emitting commands. */\r
- if (input_size > 0) {\r
- metablock_start = input;\r
- block_size = BROTLI_MIN(size_t, input_size, kFirstBlockSize);\r
- total_block_size = block_size;\r
- /* Save the bit position of the MLEN field of the meta-block header, so that\r
- we can update it later if we decide to extend this meta-block. */\r
- mlen_storage_ix = *storage_ix + 3;\r
- BrotliStoreMetaBlockHeader(block_size, 0, storage_ix, storage);\r
- /* No block splits, no contexts. */\r
- BrotliWriteBits(13, 0, storage_ix, storage);\r
- literal_ratio = BuildAndStoreLiteralPrefixCode(\r
- m, input, block_size, lit_depth, lit_bits, storage_ix, storage);\r
- if (BROTLI_IS_OOM(m)) return;\r
- BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depth, cmd_bits,\r
- storage_ix, storage);\r
- goto emit_commands;\r
- }\r
-\r
- if (!is_last) {\r
- /* If this is not the last block, update the command and distance prefix\r
- codes for the next block and store the compressed forms. */\r
- cmd_code[0] = 0;\r
- *cmd_code_numbits = 0;\r
- BuildAndStoreCommandPrefixCode(cmd_histo, cmd_depth, cmd_bits,\r
- cmd_code_numbits, cmd_code);\r
- }\r
-}\r
-\r
-#define FOR_TABLE_BITS_(X) X(9) X(11) X(13) X(15)\r
-\r
-#define BAKE_METHOD_PARAM_(B) \\r
-static BROTLI_NOINLINE void BrotliCompressFragmentFastImpl ## B( \\r
- MemoryManager* m, const uint8_t* input, size_t input_size, \\r
- BROTLI_BOOL is_last, int* table, uint8_t cmd_depth[128], \\r
- uint16_t cmd_bits[128], size_t* cmd_code_numbits, uint8_t* cmd_code, \\r
- size_t* storage_ix, uint8_t* storage) { \\r
- BrotliCompressFragmentFastImpl(m, input, input_size, is_last, table, B, \\r
- cmd_depth, cmd_bits, cmd_code_numbits, cmd_code, storage_ix, storage); \\r
-}\r
-FOR_TABLE_BITS_(BAKE_METHOD_PARAM_)\r
-#undef BAKE_METHOD_PARAM_\r
-\r
-void BrotliCompressFragmentFast(\r
- MemoryManager* m, const uint8_t* input, size_t input_size,\r
- BROTLI_BOOL is_last, int* table, size_t table_size, uint8_t cmd_depth[128],\r
- uint16_t cmd_bits[128], size_t* cmd_code_numbits, uint8_t* cmd_code,\r
- size_t* storage_ix, uint8_t* storage) {\r
- const size_t initial_storage_ix = *storage_ix;\r
- const size_t table_bits = Log2FloorNonZero(table_size);\r
-\r
- if (input_size == 0) {\r
- BROTLI_DCHECK(is_last);\r
- BrotliWriteBits(1, 1, storage_ix, storage); /* islast */\r
- BrotliWriteBits(1, 1, storage_ix, storage); /* isempty */\r
- *storage_ix = (*storage_ix + 7u) & ~7u;\r
- return;\r
- }\r
-\r
- switch (table_bits) {\r
-#define CASE_(B) \\r
- case B: \\r
- BrotliCompressFragmentFastImpl ## B( \\r
- m, input, input_size, is_last, table, cmd_depth, cmd_bits, \\r
- cmd_code_numbits, cmd_code, storage_ix, storage); \\r
- break;\r
- FOR_TABLE_BITS_(CASE_)\r
-#undef CASE_\r
- default: BROTLI_DCHECK(0); break;\r
- }\r
-\r
- /* If output is larger than single uncompressed block, rewrite it. */\r
- if (*storage_ix - initial_storage_ix > 31 + (input_size << 3)) {\r
- EmitUncompressedMetaBlock(input, input + input_size, initial_storage_ix,\r
- storage_ix, storage);\r
- }\r
-\r
- if (is_last) {\r
- BrotliWriteBits(1, 1, storage_ix, storage); /* islast */\r
- BrotliWriteBits(1, 1, storage_ix, storage); /* isempty */\r
- *storage_ix = (*storage_ix + 7u) & ~7u;\r
- }\r
-}\r
-\r
-#undef FOR_TABLE_BITS_\r
-\r
-#if defined(__cplusplus) || defined(c_plusplus)\r
-} /* extern "C" */\r
-#endif\r
projects / mirror_edk2.git / blobdiff