整型数字压缩
在搜索和存储里面为了更省空间，对整型数字都采取变长压缩，大部分数字其实值都很小，如果使用变长字节来表示，就会有很大压缩空间，levelDB和lucene内部变长整型是如何做的呢？
1. leveldb中Varint32类型
leveldb中变长整型类型使用了一个字节的最高位来表示后面是否还跟了一个字节，对于小于128的数字只需要一个字节就能表示比如14这个数字一个字节就能表示。
00001110 //14
如果值比较大就有可能用到5个字节来表示。levelDB中如何对32整型编码的呢。
-
编码
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);
}
对每个位数进行判断，每7位判断一次，对32进行编码。
-
解码
levelDB中的解码代码，值小于128的时候。
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);
}
当值大于128的时候解码：
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;
}
其中limit最大是5，32位最大长度是5个字节。jeff dean代码果然精简，高效。
2. leveldb中Varint64类型
-
编码操作
64位自己和32一样原理一样，但是jeff dean大神绝对不会这么写10个分支，下面是大神代码：
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);
}
代码真的超级精炼，v & (B-1) | B先与127&后高位设为1，ptr的8位已经完成，这时v值右移7位开始下一个7位进行转换。
-
解码操作
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;
}
解码操作和32位解码操作一样。
##总结
levelDB代码写的真的太好了jeff dean代码精炼到一个地步，包括开发习惯，代码写的很紧凑没有冗余，很好看懂，需要自己慢慢体会。
参考
leveldb: https://github.com/google/leveldb.git