snappy

// Some bit-manipulation functions.
class Bits {
 public:
  // Return floor(log2(n)) for positive integer n.  Returns -1 iff n == 0.
  static int Log2Floor(uint32 n);

  // Return the first set least / most significant bit, 0-indexed.  Returns an
  // undefined value if n == 0.  FindLSBSetNonZero() is similar to ffs() except
  // that it's 0-indexed.
  static int FindLSBSetNonZero(uint32 n);
  static int FindLSBSetNonZero64(uint64 n);

 private:
  DISALLOW_COPY_AND_ASSIGN(Bits);
};

inline int Bits::Log2Floor(uint32 n) {
  return n == 0 ? -1 : 31 ^ __builtin_clz(n); // 只是取低5位即可
}

inline int Bits::FindLSBSetNonZero(uint32 n) {
  return __builtin_ctz(n);
}

inline int Bits::FindLSBSetNonZero64(uint64 n) {
  return __builtin_ctzll(n);
}

// Variable-length integer encoding.
class Varint {
 public:
  // Maximum lengths of varint encoding of uint32.
  static const int kMax32 = 5;

  // Attempts to parse a varint32 from a prefix of the bytes in [ptr,limit-1].
  // Never reads a character at or beyond limit.  If a valid/terminated varint32
  // was found in the range, stores it in *OUTPUT and returns a pointer just
  // past the last byte of the varint32. Else returns NULL.  On success,
  // "result <= limit".
  static const char* Parse32WithLimit(const char* ptr, const char* limit,
                                      uint32* OUTPUT);

  // REQUIRES   "ptr" points to a buffer of length sufficient to hold "v".
  // EFFECTS    Encodes "v" into "ptr" and returns a pointer to the
  //            byte just past the last encoded byte.
  static char* Encode32(char* ptr, uint32 v);

  // EFFECTS    Appends the varint representation of "value" to "*s".
  static void Append32(string* s, uint32 value);
};

inline const char* Varint::Parse32WithLimit(const char* p,
                                            const char* l,
                                            uint32* OUTPUT) {
  const unsigned char* ptr = reinterpret_cast<const unsigned char*>(p);
  const unsigned char* limit = reinterpret_cast<const unsigned char*>(l);
  uint32 b, result;
  if (ptr >= limit) return NULL;
  b = *(ptr++); result = b & 127;          if (b < 128) goto done;
  if (ptr >= limit) return NULL;
  b = *(ptr++); result |= (b & 127) <<  7; if (b < 128) goto done;
  if (ptr >= limit) return NULL;
  b = *(ptr++); result |= (b & 127) << 14; if (b < 128) goto done;
  if (ptr >= limit) return NULL;
  b = *(ptr++); result |= (b & 127) << 21; if (b < 128) goto done;
  if (ptr >= limit) return NULL;
  b = *(ptr++); result |= (b & 127) << 28; if (b < 16) goto done;
  return NULL;       // Value is too long to be a varint32
 done:
  *OUTPUT = result;
  return reinterpret_cast<const char*>(ptr);
}

inline char* Varint::Encode32(char* sptr, uint32 v) {
  // Operate on characters as unsigneds
  unsigned char* ptr = reinterpret_cast<unsigned char*>(sptr);
  static const int B = 128;
  if (v < (1<<7)) {
    *(ptr++) = v;
  } else if (v < (1<<14)) {
    *(ptr++) = v | B;
    *(ptr++) = v>>7;
  } else if (v < (1<<21)) {
    *(ptr++) = v | B;
    *(ptr++) = (v>>7) | B;
    *(ptr++) = v>>14;
  } else if (v < (1<<28)) {
    *(ptr++) = v | B;
    *(ptr++) = (v>>7) | B;
    *(ptr++) = (v>>14) | B;
    *(ptr++) = v>>21;
  } else {
    *(ptr++) = v | B;
    *(ptr++) = (v>>7) | B;
    *(ptr++) = (v>>14) | B;
    *(ptr++) = (v>>21) | B;
    *(ptr++) = v>>28;
  }
  return reinterpret_cast<char*>(ptr);
}

void Varint::Append32(string* s, uint32 value) {
  char buf[Varint::kMax32];
  const char* p = Varint::Encode32(buf, value);
  s->append(buf, p - buf);
}

// For 0 <= offset <= 4, GetUint32AtOffset(UNALIGNED_LOAD64(p), offset) will
// equal UNALIGNED_LOAD32(p + offset).  Motivation: On x86-64 hardware we have
// empirically found that overlapping loads such as
//  UNALIGNED_LOAD32(p) ... UNALIGNED_LOAD32(p+1) ... UNALIGNED_LOAD32(p+2)
// are slower than UNALIGNED_LOAD64(p) followed by shifts and casts to uint32.
static inline uint32 GetUint32AtOffset(uint64 v, int offset) {
  DCHECK(0 <= offset && offset <= 4) << offset;
  return v >> (LittleEndian::IsLittleEndian() ? 8 * offset : 32 - 8 * offset);
}

// 因为Compress是按照1个个chunk来进行压缩的，input_size表示这个chunk大小多少
// 现在来看的话chunk最大32KB。然后table_size表示hashtable桶大小。

uint16* WorkingMemory::GetHashTable(size_t input_size, int* table_size) {
  // Use smaller hash table when input.size() is smaller, since we
  // fill the table, incurring O(hash table size) overhead for
  // compression, and if the input is short, we won't need that
  // many hash table entries anyway.
  assert(kMaxHashTableSize >= 256);
  int htsize = 256; // 首先从桶大小256开始进行调节,*2直到>=input_size或者是kMaxHashTableSize
  while (htsize < kMaxHashTableSize && htsize < input_size) {
    htsize <<= 1;
  }
  CHECK_EQ(0, htsize & (htsize - 1)) << ": must be power of two";
  CHECK_LE(htsize, kMaxHashTableSize) << ": hash table too large";

  uint16* table;
  if (htsize <= ARRAYSIZE(small_table_)) { // 对于WorkingMemory内部有一个small_table_[1<<10],这样可以减少分配代价
    table = small_table_;
  } else {
    if (large_table_ == NULL) {
      large_table_ = new uint16[kMaxHashTableSize]; // 对于大桶的话那么我们需要new出来
    }
    table = large_table_;
  }

  *table_size = htsize;
  memset(table, 0, htsize * sizeof(*table)); // memset(0)是需要的，在Compress部分可以看到为什么需要清0.
  return table;
}

// Return the largest n such that
//
//   s1[0,n-1] == s2[0,n-1]
//   and n <= (s2_limit - s2).
//
// Does not read *s2_limit or beyond.
// Does not read *(s1 + (s2_limit - s2)) or beyond.
// Requires that s2_limit >= s2.

static inline int FindMatchLength(const char* s1,
                                  const char* s2,
                                  const char* s2_limit) {
  DCHECK_GE(s2_limit, s2);
  int matched = 0;

  // Find out how long the match is. We loop over the data 64 bits at a
  // time until we find a 64-bit block that doesn't match; then we find
  // the first non-matching bit and use that to calculate the total
  // length of the match.
  while (PREDICT_TRUE(s2 <= s2_limit - 8)) { // 如果s2还有8个以上字节的话
    if (PREDICT_FALSE(UNALIGNED_LOAD64(s2) == UNALIGNED_LOAD64(s1 + matched))) { // 那么我们首先8个字节进行比较，匹配上的话+8
      s2 += 8;
      matched += 8;
    } else { // 如果不匹配的话，那么我们可以通过xor来判断。如果相同的话为0,然后从LSB判断有多少个0，然后count >> 3就表示匹配字节。非常巧妙。
      // On current (mid-2008) Opteron models there is a 3% more
      // efficient code sequence to find the first non-matching byte.
      // However, what follows is ~10% better on Intel Core 2 and newer,
      // and we expect AMD's bsf instruction to improve.
      uint64 x = UNALIGNED_LOAD64(s2) ^ UNALIGNED_LOAD64(s1 + matched);
      int matching_bits = Bits::FindLSBSetNonZero64(x);
      matched += matching_bits >> 3;
      return matched;
    }
  }
  while (PREDICT_TRUE(s2 < s2_limit)) { // 如果没有8个字节的话那么之后能够1个字节逐个匹配。
    if (PREDICT_TRUE(s1[matched] == *s2)) {
      ++s2;
      ++matched;
    } else {
      return matched;
    }
  }
  return matched;
}

size_t MaxCompressedLength(size_t source_len) {
  // 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_len + source_len/6;
}

// Copy "len" bytes from "src" to "op", one 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
//    len    == 20
// After IncrementalCopy(src, op, len), the result will have
// eleven copies of "ab"
//    ababababababababababab
// Note that this does not match the semantics of either memcpy()
// or memmove();
static inline void IncrementalCopy(const char* src, char* op, int len) {
  DCHECK_GT(len, 0);
  do {
    *op++ = *src++;
  } while (--len > 0);
}

const int kMaxIncrementCopyOverflow = 10;

static inline void IncrementalCopyFastPath(const char* src, char* op, int len) {
  while (op - src < 8) {
    UNALIGNED_STORE64(op, UNALIGNED_LOAD64(src));
    len -= op - src;
    op += op - src;
  }
  while (len > 0) {
    UNALIGNED_STORE64(op, UNALIGNED_LOAD64(src));
    src += 8;
    op += 8;
    len -= 8;
  }
}

// Equivalent to IncrementalCopy except that it can write up to ten extra
// bytes after the end of the copy, and that it is faster.
//
// The main part of this loop is a simple copy of eight bytes at a time until
// we've copied (at least) the requested amount of bytes.  However, if op and
// src are less than eight bytes apart (indicating a repeating pattern of
// length < 8), we first need to expand the pattern in order to get the correct
// results. For instance, if the buffer looks like this, with the eight-byte
// <src> and <op> patterns marked as intervals:
//
//    abxxxxxxxxxxxx
//    [------]           src
//      [------]         op
//
// a single eight-byte copy from <src> to <op> will repeat the pattern once,
// after which we can move <op> two bytes without moving <src>:
//
//    ababxxxxxxxxxx
//    [------]           src
//        [------]       op
//
// and repeat the exercise until the two no longer overlap.
//
// This allows us to do very well in the special case of one single byte
// repeated many times, without taking a big hit for more general cases.
//
// The worst case of extra writing past the end of the match occurs when
// op - src == 1 and len == 1; the last copy will read from byte positions
// [0..7] and write to [4..11], whereas it was only supposed to write to
// position 1. Thus, ten excess bytes.

static inline char* EmitLiteral(char* op,
                                const char* literal,
                                int len,
                                bool allow_fast_path) {
  int n = len - 1;      // Zero-length literals are disallowed
  if (n < 60) {
    // Fits in tag byte
    *op++ = LITERAL | (n << 2);

    // The vast majority of copies are below 16 bytes, for which a
    // call to 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).
    if (allow_fast_path && len <= 16) {
      UNALIGNED_STORE64(op, UNALIGNED_LOAD64(literal));
      UNALIGNED_STORE64(op + 8, UNALIGNED_LOAD64(literal + 8));
      return op + len;
    }
  } else {
    // Encode in upcoming bytes
    char* base = op;
    int count = 0;
    op++;
    while (n > 0) {
      *op++ = n & 0xff;
      n >>= 8;
      count++;
    }
    assert(count >= 1);
    assert(count <= 4);
    *base = LITERAL | ((59+count) << 2);
  }
  memcpy(op, literal, len);
  return op + len;
}

static inline char* EmitCopyLessThan64(char* op, int offset, int len) {
  DCHECK_LE(len, 64);
  DCHECK_GE(len, 4);
  DCHECK_LT(offset, 65536);

  if ((len < 12) && (offset < 2048)) {
    int len_minus_4 = len - 4;
    assert(len_minus_4 < 8);            // Must fit in 3 bits
    *op++ = COPY_1_BYTE_OFFSET | ((len_minus_4) << 2) | ((offset >> 8) << 5);
    *op++ = offset & 0xff;
  } else {
    *op++ = COPY_2_BYTE_OFFSET | ((len-1) << 2);
    LittleEndian::Store16(op, offset);
    op += 2;
  }
  // 这里没有处理offset>=65536的格式，因为就现在实现来说chunk的大小是32K不会造成offset>=64K的情况。
  return op;
}

static inline char* EmitCopy(char* op, int offset, int len) {
  // Emit 64 byte copies but make sure to keep at least four bytes reserved
  while (len >= 68) { // 这里必须判断68，不然如果len<4而offset<208的话那么没有对应的copy编码形式
    op = EmitCopyLessThan64(op, offset, 64);
    len -= 64;
  }

  // Emit an extra 60 byte copy if have too much data to fit in one copy
  if (len > 64) {
    op = EmitCopyLessThan64(op, offset, 60);
    len -= 60;
  }

  // Emit remainder
  op = EmitCopyLessThan64(op, offset, len);
  return op;
}

class SnappyArrayWriter {
 private:
  char* base_; // 起始地址
  char* op_;  // 当前操作地址
  char* op_limit_; // 当前操作阈值

 public:
  inline explicit SnappyArrayWriter(char* dst)
      : base_(dst),
        op_(dst) {
  }

  inline void SetExpectedLength(size_t len) {
    op_limit_ = op_ + len; // 设置阈值
  }

  inline bool CheckLength() const {
    return op_ == op_limit_; // 判断长度是否匹配
  }

  inline bool Append(const char* ip, uint32 len, bool allow_fast_path) {
    char* op = op_;
    const int space_left = op_limit_ - op;
    if (allow_fast_path && len <= 16 && space_left >= 16) {
      // Fast path, used for the majority (about 90%) of dynamic invocations.
      UNALIGNED_STORE64(op, UNALIGNED_LOAD64(ip));
      UNALIGNED_STORE64(op + 8, UNALIGNED_LOAD64(ip + 8));
    } else {
      if (space_left < len) {
        return false;
      }
      memcpy(op, ip, len);
    }
    op_ = op + len;
    return true;
  }

  inline bool AppendFromSelf(uint32 offset, uint32 len) { // 从自身复制，向前走offset然后copy len个字节数据
    char* op = op_;
    const int space_left = op_limit_ - op;

    if (op - base_ <= offset - 1u) {  // -1u catches offset==0
      return false;
    }
    if (len <= 16 && offset >= 8 && space_left >= 16) { // 只有offset>=8才可以直接操作
      // Fast path, used for the majority (70-80%) of dynamic invocations.
      UNALIGNED_STORE64(op, UNALIGNED_LOAD64(op - offset));
      UNALIGNED_STORE64(op + 8, UNALIGNED_LOAD64(op - offset + 8));
    } else {
      if (space_left >= len + kMaxIncrementCopyOverflow) { // 如果允许FastPath的话
        IncrementalCopyFastPath(op - offset, op, len);
      } else {
        if (space_left < len) {
          return false;
        }
        IncrementalCopy(op - offset, op, len);
      }
    }

    op_ = op + len;
    return true;
  }
};

// A Writer that drops everything on the floor and just does validation
class SnappyDecompressionValidator {
 private:
  size_t expected_;
  size_t produced_;

 public:
  inline SnappyDecompressionValidator() : produced_(0) { }
  inline void SetExpectedLength(size_t len) {
    expected_ = len;
  }
  inline bool CheckLength() const {
    return expected_ == produced_;
  }
  inline bool Append(const char* ip, uint32 len, bool allow_fast_path) {
    produced_ += len;
    return produced_ <= expected_;
  }
  inline bool AppendFromSelf(uint32 offset, uint32 len) {
    if (produced_ <= offset - 1u) return false;  // -1u catches offset==0
    produced_ += len;
    return produced_ <= expected_;
  }
};

// Data stored per entry in lookup table:
//      Range   Bits-used       Description
//      ------------------------------------
//      1..64   0..7            Literal/copy length encoded in opcode byte
//      0..7    8..10           Copy offset encoded in opcode byte / 256
//      0..4    11..13          Extra bytes after opcode
//
// We use eight bits for the length even though 7 would have sufficed
// because of efficiency reasons:
//      (1) Extracting a byte is faster than a bit-field
//      (2) It properly aligns copy offset so we do not need a <<8
static const uint16 char_table[256] = {
  0x0001, 0x0804, 0x1001, 0x2001, 0x0002, 0x0805, 0x1002, 0x2002,
  0x0003, 0x0806, 0x1003, 0x2003, 0x0004, 0x0807, 0x1004, 0x2004,
  // ...
};

static const uint32 wordmask[] = {
  0u, 0xffu, 0xffffu, 0xffffffu, 0xffffffffu
};

// Process the next item found in the input.
// Returns true if successful, false on error or end of input.
template <class Writer>
void DecompressAllTags(Writer* writer) {
  const char* ip = ip_;
  for ( ;; ) {
    if (ip_limit_ - ip < 5) { // 如果不够5个字节的话那么就填充，但是填充结果不一定达到5个字节。
      ip_ = ip;
      if (!RefillTag()) return;
      ip = ip_;
    }

    // 读取tag第一个字节到c,得到entry
    const unsigned char c = *(reinterpret_cast<const unsigned char*>(ip++));
    const uint32 entry = char_table[c];
    // 我们将extra bytes按照uint32载入，然后根据wordmask知道，除了留在c里面的长度信息之外，存放在extra bytes里面的长度信息，叫做trailer.
    const uint32 trailer = LittleEndian::Load32(ip) & wordmask[entry >> 11];
    // ip后面extra bytes跳过
    ip += entry >> 11;
    // 得到放在c里面的长度信息
    const uint32 length = entry & 0xff;

    // 如果这个tag是LITERAL的话
    if ((c & 0x3) == LITERAL) {
      uint32 literal_length = length + trailer; // 那么trailer表示literal_length部分
      // 后面操作就是写入LITERAL
      uint32 avail = ip_limit_ - ip;
      while (avail < literal_length) {
        bool allow_fast_path = (avail >= 16);
        if (!writer->Append(ip, avail, allow_fast_path)) return;
        literal_length -= avail;
        reader_->Skip(peeked_);
        size_t n;
        ip = reader_->Peek(&n);
        avail = n;
        peeked_ = avail;
        if (avail == 0) return;  // Premature end of input
        ip_limit_ = ip + avail;
      }
      bool allow_fast_path = (avail >= 16);
      if (!writer->Append(ip, literal_length, allow_fast_path)) {
        return;
      }
      ip += literal_length;
    } else {
      // 如果是COPY的话
      // copy_offset/256 is encoded in bits 8..10.  By just fetching
      // those bits, we get copy_offset (since the bit-field starts at
      // bit 8).
        const uint32 copy_offset = (entry & 0x700) ; // 注意这个地方已经 * 256了，我们不需要进行任何操作
       // 回忆COPY(01)的(offset >> 8) << 5.所以这个地方直接就是这个结果
       // 如果是copy的话，那么trailer信息是offset而不是length
       // 然后将COPY写入.
      if (!writer->AppendFromSelf(copy_offset + trailer, length)) {
        return;
      }
    }
  }
}