内存那么大，不用就是浪费？

varint 介绍

我们知道 uint32_t 类型占用4个byte，uint64_t 占用8个byte, 但是对于比较小的数字来说，使用uint32_t 或者uint64_t 存储会比较浪费，varint 的思想是根据数字所需大小使用unsigned char* 指针存储数据，节约内存。

leveldb 实现

leveldb 中的varint实现原理简单，每个byte 使用最高bit的 0/1值代表此整数值是否结束，用剩下的7个bit 存储实际的数值。知道最后一个byte 的最高bit 是0 表示整数结束。因此小于128的数据都可以用一个byte 来表示，大于128的，比如说300，使用varint 编码的话需要两个字节10101100 0000 0010

leveldb 32位int变长编码实现

正常情况下，32位int占用4个byte, varint 编码中每个byte 中的最高bit 用来表示该byte 是不是最后一个byte,所以针对大的数varint 编码可能需要5个byte才能表示。leveldb 实现中5个if 分支对应varint占用1到5个byte 的情况。

char* EncodeVarint32(char* dst, uint32_t v) {
  // Operate on characters as unsigneds
  unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
  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);
}

对应的varint 解码的思路是从低byte 到高byte遍历，直到找到最后一个表示编码结束的byte(判断条件是 byte & 128 == 1)，代码如下

// 针对一个byte情况直接处理，大于一个byte 时，
// 使用 GetVarint32PtrFallback 处理
inline const char* GetVarint32Ptr(const char* p,
                                  const char* limit,
                                  uint32_t* value) {
  if (p < limit) {
    uint32_t result = *(reinterpret_cast<const unsigned char*>(p));
    if ((result & 128) == 0) {
      *value = result;
      return p + 1;
    }
  }
  return GetVarint32PtrFallback(p, limit, value);
}

const char* GetVarint32PtrFallback(const char* p,
                                   const char* limit,
                                   uint32_t* value) {
  uint32_t result = 0;
  for (uint32_t shift = 0; shift <= 28 && p < limit; shift += 7) {
    uint32_t byte = *(reinterpret_cast<const unsigned char*>(p));
    p++;
    if (byte & 128) {
      // More bytes are present
      result |= ((byte & 127) << shift);
    } else {
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
  return NULL;
}

64位变长编码的实现

64位整形最多需要**(10 * 8 - 10 > 64)** 10个byte 来保存，类似于32位int的编码，需要写10个if-else 分支，针对64位整形的编码，leveldb 给出了更优雅的解决方案。

char* EncodeVarint64(char* dst, uint64_t v) {
  static const int B = 128;
  unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
  while (v >= B) {
    *(ptr++) = (v & (B-1)) | B;
    v >>= 7;
  }
  *(ptr++) = static_cast<unsigned char>(v);
  return reinterpret_cast<char*>(ptr);
}

针对64位整形的解码，leveldb 实现同样是类似的逻辑。也是从低位byte 开始向高位byte遍历判断编码是否结束。代码实现如下

const char* GetVarint64Ptr(const char* p, const char* limit, uint64_t* value) {
  uint64_t result = 0;
  for (uint32_t shift = 0; shift <= 63 && p < limit; shift += 7) {
    uint64_t byte = *(reinterpret_cast<const unsigned char*>(p));
    p++;
    if (byte & 128) {
      // More bytes are present
      result |= ((byte & 127) << shift);
    } else {
      result |= (byte << shift);
      *value = result;
      return reinterpret_cast<const char*>(p);
    }
  }
  return NULL;
}

总结

varint 的思想是针对32位或者64位整形类型来说存储的大部分数据都是多余的，因此使用每个byte的最高位来标识编码是否结束，使用一个char 型指针存储编码的结果，针对很多情况可以节约存储空间。