VarInt
VarInt 是一種緊湊的表示數(shù)字的方法。它用一個(gè)或多個(gè)字節(jié)來表示一個(gè)數(shù)字憔儿，值越小的數(shù)字使用越少的字節(jié)數(shù)。這能減少用來表示數(shù)字的字節(jié)數(shù)。
VarInt 中的每個(gè) byte 的最高位 bit 有特殊的含義脑蠕，如果該位為 1，表示后續(xù)的 byte 也是該數(shù)字的一部分跪削，如果該位為 0谴仙，則結(jié)束。其他的 7 個(gè) bit 都用來表示數(shù)字碾盐。
源碼分析
leveldb中的編碼晃跺、解碼函數(shù)分為VarInt和FixedInt兩種。int32和int64操作都是類似的毫玖。FixedInt的實(shí)現(xiàn)極為簡(jiǎn)單掀虎，這里就不說了，主要分析VarInt的解碼和編碼付枫，同樣32位和64位由于原理相似烹玉，也僅僅分析32位的實(shí)現(xiàn)
編碼
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);
}
有效位是7bit的，因此把uint32按7bit分割阐滩，對(duì)unsigned char賦值時(shí)二打，超出0xFF會(huì)自動(dòng)截?cái)啵虼酥苯?code>*(ptr++) = v|B即可掂榔，不需要再把(v|B)與0xFF作&操作.
解碼
VarInt的解碼继效，很簡(jiǎn)單，依次讀取1byte装获，直到最高位為0的byte瑞信，取低7bit，作(<<7)移位操作組合成int
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;
}
其實(shí)我很好奇穴豫，在這為何不直接把兩個(gè)函數(shù)并為一個(gè)函數(shù)凡简，畢竟第二個(gè)能完成第一個(gè)任務(wù)。
編碼長(zhǎng)度
int VarintLength(uint64_t v) {
int len = 1;
while (v >= 128) {
v >>= 7;
len++;
}
return len;
}
非常簡(jiǎn)單的邏輯精肃，不用細(xì)說=潘鲫。=沒看明白的話，在理解下什么是varint
