leveldb的数字编码方法
EncodeFixed32
按照机器的字节存储顺序(大端, 小端), 原样存储到一块32位内存
EncodeFixed64
按照机器的字节存储顺序(大端, 小端), 原样存储到一块64位内存
PutFixed32
将EncodeFixed32处理过的内存块追加到目的地址
PutFixed64
同PutFixed32
EncodeVarint32
将32位的无符号整数以7个有效位, 1个标志位的形式编码.
对于Varint这种整数编码, 是为了减短数值较小的整数所占的存储空间. 实现方法是每8位, 低7位存储有效数值和高1位存储标记位(用来标记是否还有后续的数值), 以127和128这两个数为例:
127 => 0111 1111
第一个字节低7位是有效数值127, 最高位位0, 所以表示没有后续的数值, 于是算出它所代表的数值是127.
128 => 1111 1111 0000 0001
第一个字节低7位是有效数值127, 最高位位1, 所以表示有后续的数值, 相同计算方法算出后续值1, 最高位标志0表示结束, 127 + (1<<7) = 128, 因为每8位实际表示的是7位, 所以要将1左移7位, 若有更多位, 计算方式相同.
leveldb里的32位编码实现:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
| char* EncodeVarint32(char* dst, uint32_t v) {
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);
}
|
用了5个if来判断这个数落在哪个数值区间里, 32位的数值使用变长编码能使用1-5位来表示
leveldb里的64位编码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
|
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);
}
char* EncodeVarint64(char* dst, uint64_t v) {
unsigned char* ptr = reinterpret_cast<unsigned char*>(dst);
static const int B = 128;
int flag = 1;
for (int offset = 0; flag > 0 && offset < 8; offset++) {
*(ptr++) = ((v >> (offset * 7)) & 127) | B;
flag = v >> (offset * 7);
}
return reinterpret_cast<char*>(ptr);
}
|
比较了我和leveldb的实现之后, 发现leveldb更简洁高效, 是因为我的实现维护了一个offset来记录当前的偏移, flag用来记录是否继续计算, 每次都需要维护这个offset和flag, leveldb直接使用v作为变量, 通过每次对它的修改, 来记录是否继续, 同时它只需要用低7位, 省去了记录偏移的麻烦, 简洁有力!