// Copyright 2005 Google Inc. All Rights Reserved.

//

// Redistribution and use in source and binary forms, with or without

// modification, are permitted provided that the following conditions are

// met:

//

//     * Redistributions of source code must retain the above copyright

// notice, this list of conditions and the following disclaimer.

//     * Redistributions in binary form must reproduce the above

// copyright notice, this list of conditions and the following disclaimer

// in the documentation and/or other materials provided with the

// distribution.

//     * Neither the name of Google Inc. nor the names of its

// contributors may be used to endorse or promote products derived from

// this software without specific prior written permission.

//

// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

#include "snappy-internal.h"

#include "snappy-sinksource.h"

#include "snappy.h"

#if !defined(SNAPPY_HAVE_SSSE3)

// __SSSE3__ is defined by GCC and Clang. Visual Studio doesn't target SIMD

// support between SSE2 and AVX (so SSSE3 instructions require AVX support), and

// defines __AVX__ when AVX support is available.

#if defined(__SSSE3__) || defined(__AVX__)

#define SNAPPY_HAVE_SSSE3 1

#else

#define SNAPPY_HAVE_SSSE3 0

#endif

#endif  // !defined(SNAPPY_HAVE_SSSE3)

#if !defined(SNAPPY_HAVE_BMI2)

// __BMI2__ is defined by GCC and Clang. Visual Studio doesn't target BMI2

// specifically, but it does define __AVX2__ when AVX2 support is available.

// Fortunately, AVX2 was introduced in Haswell, just like BMI2.

//

// BMI2 is not defined as a subset of AVX2 (unlike SSSE3 and AVX above). So,

// GCC and Clang can build code with AVX2 enabled but BMI2 disabled, in which

// case issuing BMI2 instructions results in a compiler error.

#if defined(__BMI2__) || (defined(_MSC_VER) && defined(__AVX2__))

#define SNAPPY_HAVE_BMI2 1

#else

#define SNAPPY_HAVE_BMI2 0

#endif

#endif  // !defined(SNAPPY_HAVE_BMI2)

#if SNAPPY_HAVE_SSSE3

// Please do not replace with <x86intrin.h>. or with headers that assume more

// advanced SSE versions without checking with all the OWNERS.

#include <tmmintrin.h>

#endif

#if SNAPPY_HAVE_BMI2

// Please do not replace with <x86intrin.h>. or with headers that assume more

// advanced SSE versions without checking with all the OWNERS.

#include <immintrin.h>

#endif

#include <algorithm>

#include <array>

#include <cstddef>

#include <cstdint>

#include <cstdio>

#include <cstring>

#include <string>

#include <utility>

#include <vector>

namespace snappy {

namespace {

// The amount of slop bytes writers are using for unconditional copies.

constexpr int kSlopBytes = 64;

using internal::char_table;

using internal::COPY_1_BYTE_OFFSET;

using internal::COPY_2_BYTE_OFFSET;

using internal::COPY_4_BYTE_OFFSET;

using internal::kMaximumTagLength;

using internal::LITERAL;

// We translate the information encoded in a tag through a lookup table to a

// format that requires fewer instructions to decode. Effectively we store

// the length minus the tag part of the offset. The lowest significant byte

// thus stores the length. While total length - offset is given by

// entry - ExtractOffset(type). The nice thing is that the subtraction

// immediately sets the flags for the necessary check that offset >= length.

// This folds the cmp with sub. We engineer the long literals and copy-4 to

// always fail this check, so their presence doesn't affect the fast path.

// To prevent literals from triggering the guard against offset < length (offset

// does not apply to literals) the table is giving them a spurious offset of

// 256.

inline constexpr int16_t MakeEntry(int16_t len, int16_t offset) {

  return len - (offset << 8);

}

inline constexpr int16_t LengthMinusOffset(int data, int type) {

  return type == 3   ? 0xFF                    // copy-4 (or type == 3)

         : type == 2 ? MakeEntry(data + 1, 0)  // copy-2

         : type == 1 ? MakeEntry((data & 7) + 4, data >> 3)  // copy-1

         : data < 60 ? MakeEntry(data + 1, 1)  // note spurious offset.

                     : 0xFF;                   // long literal

}

inline constexpr int16_t LengthMinusOffset(uint8_t tag) {

  return LengthMinusOffset(tag >> 2, tag & 3);

}

template <size_t... Ints>

struct index_sequence {};

template <std::size_t N, size_t... Is>

struct make_index_sequence : make_index_sequence<N - 1, N - 1, Is...> {};

template <size_t... Is>

struct make_index_sequence<0, Is...> : index_sequence<Is...> {};

template <size_t... seq>

constexpr std::array<int16_t, 256> MakeTable(index_sequence<seq...>) {

  return std::array<int16_t, 256>{LengthMinusOffset(seq)...};

}

// We maximally co-locate the two tables so that only one register needs to be

// reserved for the table address.

struct {

  alignas(64) const std::array<int16_t, 256> length_minus_offset;

  uint32_t extract_masks[4];  // Used for extracting offset based on tag type.

} table = {MakeTable(make_index_sequence<256>{}), {0, 0xFF, 0xFFFF, 0}};

// Any hash function will produce a valid compressed bitstream, but a good

// hash function reduces the number of collisions and thus yields better

// compression for compressible input, and more speed for incompressible

// input. Of course, it doesn't hurt if the hash function is reasonably fast

// either, as it gets called a lot.

inline uint32_t HashBytes(uint32_t bytes, uint32_t mask) {

  constexpr uint32_t kMagic = 0x1e35a7bd;

  return ((kMagic * bytes) >> (32 - kMaxHashTableBits)) & mask;

}

}  // namespace

size_t MaxCompressedLength(size_t source_bytes) {

  // Compressed data can be defined as:

  //    compressed := item* literal*

  //    item       := literal* copy

  //

  // The trailing literal sequence has a space blowup of at most 62/60

  // since a literal of length 60 needs one tag byte + one extra byte

  // for length information.

  //

  // Item blowup is trickier to measure.  Suppose the "copy" op copies

  // 4 bytes of data.  Because of a special check in the encoding code,

  // we produce a 4-byte copy only if the offset is < 65536.  Therefore

  // the copy op takes 3 bytes to encode, and this type of item leads

  // to at most the 62/60 blowup for representing literals.

  //

  // Suppose the "copy" op copies 5 bytes of data.  If the offset is big

  // enough, it will take 5 bytes to encode the copy op.  Therefore the

  // worst case here is a one-byte literal followed by a five-byte copy.

  // I.e., 6 bytes of input turn into 7 bytes of "compressed" data.

  //

  // This last factor dominates the blowup, so the final estimate is:

  return 32 + source_bytes + source_bytes / 6;

}

namespace {

void UnalignedCopy64(const void* src, void* dst) {

  char tmp[8];

  std::memcpy(tmp, src, 8);

  std::memcpy(dst, tmp, 8);

}

void UnalignedCopy128(const void* src, void* dst) {

  // std::memcpy() gets vectorized when the appropriate compiler options are

  // used. For example, x86 compilers targeting SSE2+ will optimize to an SSE2

  // load and store.

  char tmp[16];

  std::memcpy(tmp, src, 16);

  std::memcpy(dst, tmp, 16);

}

template <bool use_16bytes_chunk>

inline void ConditionalUnalignedCopy128(const char* src, char* dst) {

  if (use_16bytes_chunk) {

    UnalignedCopy128(src, dst);

  } else {

    UnalignedCopy64(src, dst);

    UnalignedCopy64(src + 8, dst + 8);

  }

}

// Copy [src, src+(op_limit-op)) to [op, (op_limit-op)) a byte at a time. Used

// for handling COPY operations where the input and output regions may overlap.

// For example, suppose:

//    src       == "ab"

//    op        == src + 2

//    op_limit  == op + 20

// After IncrementalCopySlow(src, op, op_limit), the result will have eleven

// copies of "ab"

//    ababababababababababab

// Note that this does not match the semantics of either std::memcpy() or

// std::memmove().

inline char* IncrementalCopySlow(const char* src, char* op,

                                 char* const op_limit) {

  // TODO: Remove pragma when LLVM is aware this

  // function is only called in cold regions and when cold regions don't get

  // vectorized or unrolled.

#ifdef __clang__

#pragma clang loop unroll(disable)

#endif

  while (op < op_limit) {

    *op++ = *src++;

  }

  return op_limit;

}

#if SNAPPY_HAVE_SSSE3

// Computes the bytes for shuffle control mask (please read comments on

// 'pattern_generation_masks' as well) for the given index_offset and

// pattern_size. For example, when the 'offset' is 6, it will generate a

// repeating pattern of size 6. So, the first 16 byte indexes will correspond to

// the pattern-bytes {0, 1, 2, 3, 4, 5, 0, 1, 2, 3, 4, 5, 0, 1, 2, 3} and the

// next 16 byte indexes will correspond to the pattern-bytes {4, 5, 0, 1, 2, 3,

// 4, 5, 0, 1, 2, 3, 4, 5, 0, 1}. These byte index sequences are generated by

// calling MakePatternMaskBytes(0, 6, index_sequence<16>()) and

// MakePatternMaskBytes(16, 6, index_sequence<16>()) respectively.

template <size_t... indexes>

inline constexpr std::array<char, sizeof...(indexes)> MakePatternMaskBytes(

    int index_offset, int pattern_size, index_sequence<indexes...>) {

  return {static_cast<char>((index_offset + indexes) % pattern_size)...};

}

// Computes the shuffle control mask bytes array for given pattern-sizes and

// returns an array.

template <size_t... pattern_sizes_minus_one>

inline constexpr std::array<std::array<char, sizeof(__m128i)>,

                            sizeof...(pattern_sizes_minus_one)>

MakePatternMaskBytesTable(int index_offset,

                          index_sequence<pattern_sizes_minus_one...>) {

  return {MakePatternMaskBytes(

      index_offset, pattern_sizes_minus_one + 1,

      make_index_sequence</*indexes=*/sizeof(__m128i)>())...};

}

// This is an array of shuffle control masks that can be used as the source

// operand for PSHUFB to permute the contents of the destination XMM register

// into a repeating byte pattern.

alignas(16) constexpr std::array<std::array<char, sizeof(__m128i)>,

                                 16> pattern_generation_masks =

    MakePatternMaskBytesTable(

        /*index_offset=*/0,

        /*pattern_sizes_minus_one=*/make_index_sequence<16>());

// Similar to 'pattern_generation_masks', this table is used to "rotate" the

// pattern so that we can copy the *next 16 bytes* consistent with the pattern.

// Basically, pattern_reshuffle_masks is a continuation of

// pattern_generation_masks. It follows that, pattern_reshuffle_masks is same as

// pattern_generation_masks for offsets 1, 2, 4, 8 and 16.

alignas(16) constexpr std::array<std::array<char, sizeof(__m128i)>,

                                 16> pattern_reshuffle_masks =

    MakePatternMaskBytesTable(

        /*index_offset=*/16,

        /*pattern_sizes_minus_one=*/make_index_sequence<16>());

SNAPPY_ATTRIBUTE_ALWAYS_INLINE

static inline __m128i LoadPattern(const char* src, const size_t pattern_size) {

  __m128i generation_mask = _mm_load_si128(reinterpret_cast<const __m128i*>(

      pattern_generation_masks[pattern_size - 1].data()));

  // Uninitialized bytes are masked out by the shuffle mask.

  // TODO: remove annotation and macro defs once MSan is fixed.

  SNAPPY_ANNOTATE_MEMORY_IS_INITIALIZED(src + pattern_size, 16 - pattern_size);

  return _mm_shuffle_epi8(

      _mm_loadu_si128(reinterpret_cast<const __m128i*>(src)), generation_mask);

}

SNAPPY_ATTRIBUTE_ALWAYS_INLINE

static inline std::pair<__m128i /* pattern */, __m128i /* reshuffle_mask */>

LoadPatternAndReshuffleMask(const char* src, const size_t pattern_size) {

  __m128i pattern = LoadPattern(src, pattern_size);

  // This mask will generate the next 16 bytes in-place. Doing so enables us to

  // write data by at most 4 _mm_storeu_si128.

  //

  // For example, suppose pattern is:        abcdefabcdefabcd

  // Shuffling with this mask will generate: efabcdefabcdefab

  // Shuffling again will generate:          cdefabcdefabcdef

  __m128i reshuffle_mask = _mm_load_si128(reinterpret_cast<const __m128i*>(

      pattern_reshuffle_masks[pattern_size - 1].data()));

  return {pattern, reshuffle_mask};

}

#endif  // SNAPPY_HAVE_SSSE3

// Fallback for when we need to copy while extending the pattern, for example

// copying 10 bytes from 3 positions back abc -> abcabcabcabca.

//

// REQUIRES: [dst - offset, dst + 64) is a valid address range.

SNAPPY_ATTRIBUTE_ALWAYS_INLINE

static inline bool Copy64BytesWithPatternExtension(char* dst, size_t offset) {

#if SNAPPY_HAVE_SSSE3

  if (SNAPPY_PREDICT_TRUE(offset <= 16)) {

    switch (offset) {

      case 0:

        return false;

      case 1: {

        std::memset(dst, dst[-1], 64);

        return true;

      }

      case 2:

      case 4:

      case 8:

      case 16: {

        __m128i pattern = LoadPattern(dst - offset, offset);

        for (int i = 0; i < 4; i++) {

          _mm_storeu_si128(reinterpret_cast<__m128i*>(dst + 16 * i), pattern);

        }

        return true;

      }

      default: {

        auto pattern_and_reshuffle_mask =

            LoadPatternAndReshuffleMask(dst - offset, offset);

        __m128i pattern = pattern_and_reshuffle_mask.first;

        __m128i reshuffle_mask = pattern_and_reshuffle_mask.second;

        for (int i = 0; i < 4; i++) {

          _mm_storeu_si128(reinterpret_cast<__m128i*>(dst + 16 * i), pattern);

          pattern = _mm_shuffle_epi8(pattern, reshuffle_mask);

        }

        return true;

      }

    }

  }

#else

  if (SNAPPY_PREDICT_TRUE(offset < 16)) {

    if (SNAPPY_PREDICT_FALSE(offset == 0)) return false;

    // Extend the pattern to the first 16 bytes.

    for (int i = 0; i < 16; i++) dst[i] = dst[i - offset];

    // Find a multiple of pattern >= 16.

    static std::array<uint8_t, 16> pattern_sizes = []() {

      std::array<uint8_t, 16> res;

      for (int i = 1; i < 16; i++) res[i] = (16 / i + 1) * i;

      return res;

    }();

    offset = pattern_sizes[offset];

    for (int i = 1; i < 4; i++) {

      std::memcpy(dst + i * 16, dst + i * 16 - offset, 16);

    }

    return true;

  }

#endif  // SNAPPY_HAVE_SSSE3

  // Very rare.

  for (int i = 0; i < 4; i++) {

    std::memcpy(dst + i * 16, dst + i * 16 - offset, 16);

  }

  return true;

}

// Copy [src, src+(op_limit-op)) to [op, op_limit) but faster than

// IncrementalCopySlow. buf_limit is the address past the end of the writable

// region of the buffer.

inline char* IncrementalCopy(const char* src, char* op, char* const op_limit,

                             char* const buf_limit) {

#if SNAPPY_HAVE_SSSE3

  constexpr int big_pattern_size_lower_bound = 16;

#else

  constexpr int big_pattern_size_lower_bound = 8;

#endif

  // Terminology:

  //

  // slop = buf_limit - op

  // pat  = op - src

  // len  = op_limit - op

  assert(src < op);

  assert(op < op_limit);

  assert(op_limit <= buf_limit);

  // NOTE: The copy tags use 3 or 6 bits to store the copy length, so len <= 64.

  assert(op_limit - op <= 64);

  // NOTE: In practice the compressor always emits len >= 4, so it is ok to

  // assume that to optimize this function, but this is not guaranteed by the

  // compression format, so we have to also handle len < 4 in case the input

  // does not satisfy these conditions.

  size_t pattern_size = op - src;

  // The cases are split into different branches to allow the branch predictor,

  // FDO, and static prediction hints to work better. For each input we list the

  // ratio of invocations that match each condition.

  //

  // input        slop < 16   pat < 8  len > 16

  // ------------------------------------------

  // html|html4|cp   0%         1.01%    27.73%

  // urls            0%         0.88%    14.79%

  // jpg             0%        64.29%     7.14%

  // pdf             0%         2.56%    58.06%

  // txt[1-4]        0%         0.23%     0.97%

  // pb              0%         0.96%    13.88%

  // bin             0.01%     22.27%    41.17%

  //

  // It is very rare that we don't have enough slop for doing block copies. It

  // is also rare that we need to expand a pattern. Small patterns are common

  // for incompressible formats and for those we are plenty fast already.

  // Lengths are normally not greater than 16 but they vary depending on the

  // input. In general if we always predict len <= 16 it would be an ok

  // prediction.

  //

  // In order to be fast we want a pattern >= 16 bytes (or 8 bytes in non-SSE)

  // and an unrolled loop copying 1x 16 bytes (or 2x 8 bytes in non-SSE) at a

  // time.

  // Handle the uncommon case where pattern is less than 16 (or 8 in non-SSE)

  // bytes.

  if (pattern_size < big_pattern_size_lower_bound) {

#if SNAPPY_HAVE_SSSE3

    // Load the first eight bytes into an 128-bit XMM register, then use PSHUFB

    // to permute the register's contents in-place into a repeating sequence of

    // the first "pattern_size" bytes.

    // For example, suppose:

    //    src       == "abc"

    //    op        == op + 3

    // After _mm_shuffle_epi8(), "pattern" will have five copies of "abc"

    // followed by one byte of slop: abcabcabcabcabca.

    //

    // The non-SSE fallback implementation suffers from store-forwarding stalls

    // because its loads and stores partly overlap. By expanding the pattern

    // in-place, we avoid the penalty.

    // Typically, the op_limit is the gating factor so try to simplify the loop

    // based on that.

    if (SNAPPY_PREDICT_TRUE(op_limit <= buf_limit - 15)) {

      auto pattern_and_reshuffle_mask =

          LoadPatternAndReshuffleMask(src, pattern_size);

      __m128i pattern = pattern_and_reshuffle_mask.first;

      __m128i reshuffle_mask = pattern_and_reshuffle_mask.second;

      // There is at least one, and at most four 16-byte blocks. Writing four

      // conditionals instead of a loop allows FDO to layout the code with

      // respect to the actual probabilities of each length.

      // TODO: Replace with loop with trip count hint.

      _mm_storeu_si128(reinterpret_cast<__m128i*>(op), pattern);

      if (op + 16 < op_limit) {

        pattern = _mm_shuffle_epi8(pattern, reshuffle_mask);

        _mm_storeu_si128(reinterpret_cast<__m128i*>(op + 16), pattern);

      }

      if (op + 32 < op_limit) {

        pattern = _mm_shuffle_epi8(pattern, reshuffle_mask);

        _mm_storeu_si128(reinterpret_cast<__m128i*>(op + 32), pattern);

      }

      if (op + 48 < op_limit) {

        pattern = _mm_shuffle_epi8(pattern, reshuffle_mask);

        _mm_storeu_si128(reinterpret_cast<__m128i*>(op + 48), pattern);

      }

      return op_limit;

    }

    char* const op_end = buf_limit - 15;

    if (SNAPPY_PREDICT_TRUE(op < op_end)) {

      auto pattern_and_reshuffle_mask =

          LoadPatternAndReshuffleMask(src, pattern_size);

      __m128i pattern = pattern_and_reshuffle_mask.first;

      __m128i reshuffle_mask = pattern_and_reshuffle_mask.second;

      // This code path is relatively cold however so we save code size

      // by avoiding unrolling and vectorizing.

      //

      // TODO: Remove pragma when when cold regions don't get

      // vectorized or unrolled.

#ifdef __clang__

#pragma clang loop unroll(disable)

#endif

      do {

        _mm_storeu_si128(reinterpret_cast<__m128i*>(op), pattern);

        pattern = _mm_shuffle_epi8(pattern, reshuffle_mask);

        op += 16;

      } while (SNAPPY_PREDICT_TRUE(op < op_end));

    }

    return IncrementalCopySlow(op - pattern_size, op, op_limit);

#else   // !SNAPPY_HAVE_SSSE3

    // If plenty of buffer space remains, expand the pattern to at least 8

    // bytes. The way the following loop is written, we need 8 bytes of buffer

    // space if pattern_size >= 4, 11 bytes if pattern_size is 1 or 3, and 10

    // bytes if pattern_size is 2.  Precisely encoding that is probably not

    // worthwhile; instead, invoke the slow path if we cannot write 11 bytes

    // (because 11 are required in the worst case).

    if (SNAPPY_PREDICT_TRUE(op <= buf_limit - 11)) {

      while (pattern_size < 8) {

        UnalignedCopy64(src, op);

        op += pattern_size;

        pattern_size *= 2;

      }

      if (SNAPPY_PREDICT_TRUE(op >= op_limit)) return op_limit;

    } else {

      return IncrementalCopySlow(src, op, op_limit);

    }

#endif  // SNAPPY_HAVE_SSSE3

  }

  assert(pattern_size >= big_pattern_size_lower_bound);

  constexpr bool use_16bytes_chunk = big_pattern_size_lower_bound == 16;

  // Copy 1x 16 bytes (or 2x 8 bytes in non-SSE) at a time. Because op - src can

  // be < 16 in non-SSE, a single UnalignedCopy128 might overwrite data in op.

  // UnalignedCopy64 is safe because expanding the pattern to at least 8 bytes

  // guarantees that op - src >= 8.

  //

  // Typically, the op_limit is the gating factor so try to simplify the loop

  // based on that.

  if (SNAPPY_PREDICT_TRUE(op_limit <= buf_limit - 15)) {

    // There is at least one, and at most four 16-byte blocks. Writing four

    // conditionals instead of a loop allows FDO to layout the code with respect

    // to the actual probabilities of each length.

    // TODO: Replace with loop with trip count hint.

    ConditionalUnalignedCopy128<use_16bytes_chunk>(src, op);

    if (op + 16 < op_limit) {

      ConditionalUnalignedCopy128<use_16bytes_chunk>(src + 16, op + 16);

    }

    if (op + 32 < op_limit) {

      ConditionalUnalignedCopy128<use_16bytes_chunk>(src + 32, op + 32);

    }

    if (op + 48 < op_limit) {

      ConditionalUnalignedCopy128<use_16bytes_chunk>(src + 48, op + 48);

    }

    return op_limit;

  }

  // Fall back to doing as much as we can with the available slop in the

  // buffer. This code path is relatively cold however so we save code size by

  // avoiding unrolling and vectorizing.

  //

  // TODO: Remove pragma when when cold regions don't get vectorized

  // or unrolled.

#ifdef __clang__

#pragma clang loop unroll(disable)

#endif

  for (char* op_end = buf_limit - 16; op < op_end; op += 16, src += 16) {

    ConditionalUnalignedCopy128<use_16bytes_chunk>(src, op);

  }

  if (op >= op_limit) return op_limit;

  // We only take this branch if we didn't have enough slop and we can do a

  // single 8 byte copy.

  if (SNAPPY_PREDICT_FALSE(op <= buf_limit - 8)) {

    UnalignedCopy64(src, op);

    src += 8;

    op += 8;

  }

  return IncrementalCopySlow(src, op, op_limit);

}

}  // namespace

template <bool allow_fast_path>

static inline char* EmitLiteral(char* op, const char* literal, int len) {

  // The vast majority of copies are below 16 bytes, for which a

  // call to std::memcpy() is overkill. This fast path can sometimes

  // copy up to 15 bytes too much, but that is okay in the

  // main loop, since we have a bit to go on for both sides:

  //

  //   - The input will always have kInputMarginBytes = 15 extra

  //     available bytes, as long as we're in the main loop, and

  //     if not, allow_fast_path = false.

  //   - The output will always have 32 spare bytes (see

  //     MaxCompressedLength).

  assert(len > 0);  // Zero-length literals are disallowed

  int n = len - 1;

  if (allow_fast_path && len <= 16) {

    // Fits in tag byte

    *op++ = LITERAL | (n << 2);

    UnalignedCopy128(literal, op);

    return op + len;

  }

  if (n < 60) {

    // Fits in tag byte

    *op++ = LITERAL | (n << 2);

  } else {

    int count = (Bits::Log2Floor(n) >> 3) + 1;

    assert(count >= 1);

    assert(count <= 4);

    *op++ = LITERAL | ((59 + count) << 2);

    // Encode in upcoming bytes.

    // Write 4 bytes, though we may care about only 1 of them. The output buffer

    // is guaranteed to have at least 3 more spaces left as 'len >= 61' holds

    // here and there is a std::memcpy() of size 'len' below.

    LittleEndian::Store32(op, n);

    op += count;

  }

  std::memcpy(op, literal, len);

  return op + len;

}

Unexecuted instantiation: snappy.cc:char* snappy::EmitLiteral<true>(char*, char const*, int)

Unexecuted instantiation: snappy.cc:char* snappy::EmitLiteral<false>(char*, char const*, int)

template <bool len_less_than_12>

static inline char* EmitCopyAtMost64(char* op, size_t offset, size_t len) {

  assert(len <= 64);

  assert(len >= 4);

  assert(offset < 65536);

  assert(len_less_than_12 == (len < 12));

  if (len_less_than_12) {

    uint32_t u = (len << 2) + (offset << 8);

    uint32_t copy1 = COPY_1_BYTE_OFFSET - (4 << 2) + ((offset >> 3) & 0xe0);

    uint32_t copy2 = COPY_2_BYTE_OFFSET - (1 << 2);

    // It turns out that offset < 2048 is a difficult to predict branch.

    // `perf record` shows this is the highest percentage of branch misses in

    // benchmarks. This code produces branch free code, the data dependency

    // chain that bottlenecks the throughput is so long that a few extra

    // instructions are completely free (IPC << 6 because of data deps).

    u += offset < 2048 ? copy1 : copy2;

    LittleEndian::Store32(op, u);

    op += offset < 2048 ? 2 : 3;

  } else {

    // Write 4 bytes, though we only care about 3 of them.  The output buffer

    // is required to have some slack, so the extra byte won't overrun it.

    uint32_t u = COPY_2_BYTE_OFFSET + ((len - 1) << 2) + (offset << 8);

    LittleEndian::Store32(op, u);

    op += 3;

  }

  return op;

}

Unexecuted instantiation: snappy.cc:char* snappy::EmitCopyAtMost64<true>(char*, unsigned long, unsigned long)

Unexecuted instantiation: snappy.cc:char* snappy::EmitCopyAtMost64<false>(char*, unsigned long, unsigned long)

template <bool len_less_than_12>

static inline char* EmitCopy(char* op, size_t offset, size_t len) {

  assert(len_less_than_12 == (len < 12));

  if (len_less_than_12) {

    return EmitCopyAtMost64</*len_less_than_12=*/true>(op, offset, len);

  } else {

    // A special case for len <= 64 might help, but so far measurements suggest

    // it's in the noise.

    // Emit 64 byte copies but make sure to keep at least four bytes reserved.

    while (SNAPPY_PREDICT_FALSE(len >= 68)) {

      op = EmitCopyAtMost64</*len_less_than_12=*/false>(op, offset, 64);

      len -= 64;

    }

    // One or two copies will now finish the job.

    if (len > 64) {

      op = EmitCopyAtMost64</*len_less_than_12=*/false>(op, offset, 60);

      len -= 60;

    }

    // Emit remainder.

    if (len < 12) {

      op = EmitCopyAtMost64</*len_less_than_12=*/true>(op, offset, len);

    } else {

      op = EmitCopyAtMost64</*len_less_than_12=*/false>(op, offset, len);

    }

    return op;

  }

}

Unexecuted instantiation: snappy.cc:char* snappy::EmitCopy<true>(char*, unsigned long, unsigned long)

Unexecuted instantiation: snappy.cc:char* snappy::EmitCopy<false>(char*, unsigned long, unsigned long)

bool GetUncompressedLength(const char* start, size_t n, size_t* result) {

  uint32_t v = 0;

  const char* limit = start + n;

  if (Varint::Parse32WithLimit(start, limit, &v) != NULL) {

    *result = v;

    return true;

  } else {

    return false;

  }

}

namespace {

uint32_t CalculateTableSize(uint32_t input_size) {

  static_assert(

      kMaxHashTableSize >= kMinHashTableSize,

      "kMaxHashTableSize should be greater or equal to kMinHashTableSize.");

  if (input_size > kMaxHashTableSize) {

    return kMaxHashTableSize;

  }

  if (input_size < kMinHashTableSize) {

    return kMinHashTableSize;

  }

  // This is equivalent to Log2Ceiling(input_size), assuming input_size > 1.

  // 2 << Log2Floor(x - 1) is equivalent to 1 << (1 + Log2Floor(x - 1)).

  return 2u << Bits::Log2Floor(input_size - 1);

}

}  // namespace

namespace internal {

WorkingMemory::WorkingMemory(size_t input_size) {

  const size_t max_fragment_size = std::min(input_size, kBlockSize);

  const size_t table_size = CalculateTableSize(max_fragment_size);

  size_ = table_size * sizeof(*table_) + max_fragment_size +

          MaxCompressedLength(max_fragment_size);

  mem_ = std::allocator<char>().allocate(size_);

  table_ = reinterpret_cast<uint16_t*>(mem_);

  input_ = mem_ + table_size * sizeof(*table_);

  output_ = input_ + max_fragment_size;

}

WorkingMemory::~WorkingMemory() {

  std::allocator<char>().deallocate(mem_, size_);

}

uint16_t* WorkingMemory::GetHashTable(size_t fragment_size,

                                      int* table_size) const {

  const size_t htsize = CalculateTableSize(fragment_size);

  memset(table_, 0, htsize * sizeof(*table_));

  *table_size = htsize;

  return table_;

}

}  // end namespace internal

// Flat array compression that does not emit the "uncompressed length"

// prefix. Compresses "input" string to the "*op" buffer.

//

// REQUIRES: "input" is at most "kBlockSize" bytes long.

// REQUIRES: "op" points to an array of memory that is at least

// "MaxCompressedLength(input.size())" in size.

// REQUIRES: All elements in "table[0..table_size-1]" are initialized to zero.

// REQUIRES: "table_size" is a power of two

//

// Returns an "end" pointer into "op" buffer.

// "end - op" is the compressed size of "input".

namespace internal {

char* CompressFragment(const char* input, size_t input_size, char* op,

                       uint16_t* table, const int table_size) {

  // "ip" is the input pointer, and "op" is the output pointer.

  const char* ip = input;

  assert(input_size <= kBlockSize);

  assert((table_size & (table_size - 1)) == 0);  // table must be power of two

  const uint32_t mask = table_size - 1;

  const char* ip_end = input + input_size;

  const char* base_ip = ip;

  const size_t kInputMarginBytes = 15;

  if (SNAPPY_PREDICT_TRUE(input_size >= kInputMarginBytes)) {

    const char* ip_limit = input + input_size - kInputMarginBytes;

    for (uint32_t preload = LittleEndian::Load32(ip + 1);;) {

      // Bytes in [next_emit, ip) will be emitted as literal bytes.  Or

      // [next_emit, ip_end) after the main loop.

      const char* next_emit = ip++;

      uint64_t data = LittleEndian::Load64(ip);

      // The body of this loop calls EmitLiteral once and then EmitCopy one or

      // more times.  (The exception is that when we're close to exhausting

      // the input we goto emit_remainder.)

      //

      // In the first iteration of this loop we're just starting, so

      // there's nothing to copy, so calling EmitLiteral once is

      // necessary.  And we only start a new iteration when the

      // current iteration has determined that a call to EmitLiteral will

      // precede the next call to EmitCopy (if any).

      //

      // Step 1: Scan forward in the input looking for a 4-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 (or skipped), 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 char* candidate;

      if (ip_limit - ip >= 16) {

        auto delta = ip - base_ip;

        for (int j = 0; j < 4; ++j) {

          for (int k = 0; k < 4; ++k) {

            int i = 4 * j + k;

            // These for-loops are meant to be unrolled. So we can freely

            // special case the first iteration to use the value already

            // loaded in preload.

            uint32_t dword = i == 0 ? preload : static_cast<uint32_t>(data);

            assert(dword == LittleEndian::Load32(ip + i));

            uint32_t hash = HashBytes(dword, mask);

            candidate = base_ip + table[hash];

            assert(candidate >= base_ip);

            assert(candidate < ip + i);

            table[hash] = delta + i;

            if (SNAPPY_PREDICT_FALSE(LittleEndian::Load32(candidate) == dword)) {

              *op = LITERAL | (i << 2);

              UnalignedCopy128(next_emit, op + 1);

              ip += i;

              op = op + i + 2;

              goto emit_match;

            }

            data >>= 8;

          }

          data = LittleEndian::Load64(ip + 4 * j + 4);

        }

        ip += 16;

        skip += 16;

      }

      while (true) {

        assert(static_cast<uint32_t>(data) == LittleEndian::Load32(ip));

        uint32_t hash = HashBytes(data, mask);

        uint32_t bytes_between_hash_lookups = skip >> 5;

        skip += bytes_between_hash_lookups;

        const char* next_ip = ip + bytes_between_hash_lookups;

        if (SNAPPY_PREDICT_FALSE(next_ip > ip_limit)) {

          ip = next_emit;

          goto emit_remainder;

        }

        candidate = base_ip + table[hash];

        assert(candidate >= base_ip);

        assert(candidate < ip);

        table[hash] = ip - base_ip;

        if (SNAPPY_PREDICT_FALSE(static_cast<uint32_t>(data) ==

                                LittleEndian::Load32(candidate))) {

          break;

        }

        data = LittleEndian::Load32(next_ip);

        ip = next_ip;

      }

      // Step 2: A 4-byte match has been found.  We'll later see if more

      // than 4 bytes match.  But, prior to the match, input

      // bytes [next_emit, ip) are unmatched.  Emit them as "literal bytes."

      assert(next_emit + 16 <= ip_end);

      op = EmitLiteral</*allow_fast_path=*/true>(op, next_emit, ip - next_emit);

      // Step 3: Call EmitCopy, and then see if another EmitCopy could

      // be our next move.  Repeat until we find no match for the

      // input immediately after what was consumed by the last EmitCopy call.

      //

      // If we exit this loop normally then we need to call EmitLiteral next,

      // though we don't yet know how big the literal will be.  We handle that

      // by proceeding to the next iteration of the main loop.  We also can exit

      // this loop via goto if we get close to exhausting the input.

    emit_match:

      do {

        // We have a 4-byte match at ip, and no need to emit any

        // "literal bytes" prior to ip.

        const char* base = ip;

        std::pair<size_t, bool> p =

            FindMatchLength(candidate + 4, ip + 4, ip_end, &data);

        size_t matched = 4 + p.first;

        ip += matched;

        size_t offset = base - candidate;

        assert(0 == memcmp(base, candidate, matched));

        if (p.second) {

          op = EmitCopy</*len_less_than_12=*/true>(op, offset, matched);

        } else {

          op = EmitCopy</*len_less_than_12=*/false>(op, offset, matched);

        }

        if (SNAPPY_PREDICT_FALSE(ip >= ip_limit)) {

          goto emit_remainder;

        }

        // Expect 5 bytes to match

        assert((data & 0xFFFFFFFFFF) ==

               (LittleEndian::Load64(ip) & 0xFFFFFFFFFF));

        // We are now looking for a 4-byte match again.  We read

        // table[Hash(ip, shift)] for that.  To improve compression,

        // we also update table[Hash(ip - 1, mask)] and table[Hash(ip, mask)].

        table[HashBytes(LittleEndian::Load32(ip - 1), mask)] = ip - base_ip - 1;

        uint32_t hash = HashBytes(data, mask);

        candidate = base_ip + table[hash];

        table[hash] = ip - base_ip;

        // Measurements on the benchmarks have shown the following probabilities

        // for the loop to exit (ie. avg. number of iterations is reciprocal).

        // BM_Flat/6  txt1    p = 0.3-0.4

        // BM_Flat/7  txt2    p = 0.35

        // BM_Flat/8  txt3    p = 0.3-0.4

        // BM_Flat/9  txt3    p = 0.34-0.4

        // BM_Flat/10 pb      p = 0.4

        // BM_Flat/11 gaviota p = 0.1

        // BM_Flat/12 cp      p = 0.5

        // BM_Flat/13 c       p = 0.3

      } while (static_cast<uint32_t>(data) == LittleEndian::Load32(candidate));

      // Because the least significant 5 bytes matched, we can utilize data

      // for the next iteration.

      preload = data >> 8;

    }

  }

emit_remainder:

  // Emit the remaining bytes as a literal

  if (ip < ip_end) {

    op = EmitLiteral</*allow_fast_path=*/false>(op, ip, ip_end - ip);

  }

  return op;

}

}  // end namespace internal

// Called back at avery compression call to trace parameters and sizes.

static inline void Report(const char *algorithm, size_t compressed_size,

                          size_t uncompressed_size) {

  // TODO: Switch to [[maybe_unused]] when we can assume C++17.

  (void)algorithm;

  (void)compressed_size;

  (void)uncompressed_size;

}

// Signature of output types needed by decompression code.

// The decompression code is templatized on a type that obeys this

// signature so that we do not pay virtual function call overhead in

// the middle of a tight decompression loop.

//

// class DecompressionWriter {

//  public:

//   // Called before decompression

//   void SetExpectedLength(size_t length);

//

//   // For performance a writer may choose to donate the cursor variable to the

//   // decompression function. The decompression will inject it in all its

//   // function calls to the writer. Keeping the important output cursor as a

//   // function local stack variable allows the compiler to keep it in

//   // register, which greatly aids performance by avoiding loads and stores of

//   // this variable in the fast path loop iterations.

//   T GetOutputPtr() const;

//

//   // At end of decompression the loop donates the ownership of the cursor

//   // variable back to the writer by calling this function.

//   void SetOutputPtr(T op);

//

//   // Called after decompression

//   bool CheckLength() const;

//

//   // Called repeatedly during decompression

//   // Each function get a pointer to the op (output pointer), that the writer

//   // can use and update. Note it's important that these functions get fully

//   // inlined so that no actual address of the local variable needs to be

//   // taken.

//   bool Append(const char* ip, size_t length, T* op);

//   bool AppendFromSelf(uint32_t offset, size_t length, T* op);

//

//   // The rules for how TryFastAppend differs from Append are somewhat

//   // convoluted:

//   //

//   //  - TryFastAppend is allowed to decline (return false) at any

//   //    time, for any reason -- just "return false" would be

//   //    a perfectly legal implementation of TryFastAppend.

//   //    The intention is for TryFastAppend to allow a fast path

//   //    in the common case of a small append.

//   //  - TryFastAppend is allowed to read up to <available> bytes

//   //    from the input buffer, whereas Append is allowed to read

//   //    <length>. However, if it returns true, it must leave

//   //    at least five (kMaximumTagLength) bytes in the input buffer

//   //    afterwards, so that there is always enough space to read the

//   //    next tag without checking for a refill.

//   //  - TryFastAppend must always return decline (return false)

//   //    if <length> is 61 or more, as in this case the literal length is not

//   //    decoded fully. In practice, this should not be a big problem,

//   //    as it is unlikely that one would implement a fast path accepting

//   //    this much data.

//   //

//   bool TryFastAppend(const char* ip, size_t available, size_t length, T* op);

// };

static inline uint32_t ExtractLowBytes(uint32_t v, int n) {

  assert(n >= 0);

  assert(n <= 4);

#if SNAPPY_HAVE_BMI2

  return _bzhi_u32(v, 8 * n);

#else

  // This needs to be wider than uint32_t otherwise `mask << 32` will be

  // undefined.

  uint64_t mask = 0xffffffff;

  return v & ~(mask << (8 * n));

#endif

}

static inline bool LeftShiftOverflows(uint8_t value, uint32_t shift) {

  assert(shift < 32);

  static const uint8_t masks[] = {

      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  //

      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  //

      0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00, 0x00,  //

      0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe};

  return (value & masks[shift]) != 0;

}

inline bool Copy64BytesWithPatternExtension(ptrdiff_t dst, size_t offset) {

  // TODO: Switch to [[maybe_unused]] when we can assume C++17.

  (void)dst;

  return offset != 0;

}

void MemCopy(char* dst, const uint8_t* src, size_t size) {

  std::memcpy(dst, src, size);