LevelDB源碼分析之一：coding
LevelDB默認使用的是小端字節(jié)序存儲，低位字節(jié)排放在內存的低地址端，高位字節(jié)排放在內存的高地址端。?
編碼分為變長的EncodeVarint和固定大小的EncodeFixed兩種，每種又分32位和64位。
一.EncodeFixed
void?EncodeFixed32(char*?buf,?uint32_t?value)?{
#if?__BYTE_ORDER?==?__LITTLE_ENDIAN
??memcpy(buf,?&value,?sizeof(value));
#else
??buf[0]?=?value?&?0xff;
??buf[1]?=?(value?>>?8)?&?0xff;
??buf[2]?=?(value?>>?16)?&?0xff;
??buf[3]?=?(value?>>?24)?&?0xff;
#endif
}void?EncodeFixed64(char*?buf,?uint64_t?value)?{
#if?__BYTE_ORDER?==?__LITTLE_ENDIAN
??memcpy(buf,?&value,?sizeof(value));
#else
??buf[0]?=?value?&?0xff;
??buf[1]?=?(value?>>?8)?&?0xff;
??buf[2]?=?(value?>>?16)?&?0xff;
??buf[3]?=?(value?>>?24)?&?0xff;
??buf[4]?=?(value?>>?32)?&?0xff;
??buf[5]?=?(value?>>?40)?&?0xff;
??buf[6]?=?(value?>>?48)?&?0xff;
??buf[7]?=?(value?>>?56)?&?0xff;
#endif
}這兩個函數非常簡單，功能就是判斷系統(tǒng)是否為小端存儲，如果是，直接將value拷貝到buf，如果不是，則將value轉換為小端字節(jié)序存儲到buf中。
解碼函數DecodeFixed32和DecodeFixed64是編碼的逆過程，也很簡單。
二.EncodeVarint
為什么要把整型（int）編碼成變長整型（varint）呢？是為了盡可能的節(jié)約存儲空間。
varint是一種緊湊的表示數字的方法，它用一個或多個字節(jié)來表示一個數字，值越小的數字使用越少的字節(jié)數。比如int32類型的數字，一般需要4個字節(jié)。但是采用Varint，對于很小的int32類型的數字，則可以用1個字節(jié)來表示。當然凡事都有好的也有不好的一面，采用varint表示法，大的數字則可能需要5個字節(jié)來表示。從統(tǒng)計的角度來說，一般不會所有消息中的數字都是大數，因此大多數情況下，采用varint后，可以用更小的字節(jié)數來表示數字信息。
varint中的每個字節(jié)的最高位（bit）有特殊含義，如果該位為1，表示后續(xù)的字節(jié)也是這個數字的一部分，如果該位為0，則結束。其他的7位（bit）都表示數字。7位能表示的最大數是127，因此小于128的數字都可以用一個字節(jié)表示。大于等于128的數字，比如說300，會用兩個字節(jié)在內存中表示為：
低 ? ? ? ? ? ? ? 高
1010 1100 0000 0010
實現過程如下：
300的二進制為100101100，取低7位也就是010 1100放在內存低字節(jié)中，由于第二個字節(jié)也是數字的一部分，因此內存低字節(jié)的最高位為1，則完整的內存低字節(jié)為1010 1100。300的高2位也就是10放到內存的高字節(jié)中，因為數字到該字節(jié)結束，因此該字節(jié)包括最高位的其他6位都用0填充，則完整的內存高字節(jié)為0000 0010。
正常情況下，int需要32位，varint用一個字節(jié)的最高位作為標識位，所以，一個字節(jié)只能存儲7位，如果整數特別大，可能需要5個字節(jié)才能存放（5*8-5（標志位）>32），下面if語句的第五個分支就是處理這種情況。
char*?EncodeVarint32(char*?dst,?uint32_t?v)?{
??//?Operate?on?characters?as?unsigneds
??unsigned?char*?ptr?=?reinterpret_cast(dst);
??static?const?int?B?=?128;
??if?(v?<?(1<<7))?{???????????????//如果v小于128
????*(ptr++)?=?v;
??}?else?if?(v?<?(1<>7;??????????????//把300（0000?0001?0010?1100）右移7位得到000?0000?0000?0001?0，給內存高字節(jié)。
??}?else?if?(v?<?(1<>7)?|?B;
????*(ptr++)?=?v>>14;
??}?else?if?(v?<?(1<>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(ptr);
}對于64位整型，我們最多需要10個字節(jié)（10*8-10（標志位）>64），如果像EncodeVarint32一樣寫代碼，需要有10個if分支，大?？隙]這么勤快。其實EncodeVarint32也可以像EncodeVarint64這么寫。
char*?EncodeVarint64(char*?dst,?uint64_t?v)?{
??static?const?int?B?=?128;
??unsigned?char*?ptr?=?reinterpret_cast(dst);
??while?(v?>=?B)?{
????*(ptr++)?=?(v?&?(B-1))?|?B;
????v?>>=?7;
??}
??*(ptr++)?=?static_cast(v);
??return?reinterpret_cast(ptr);
}下面的函數是計算整型編碼后的長度，也就是varint的長度。
int?VarintLength(uint64_t?v)?{
??int?len?=?1;
??while?(v?>=?128)?{
????v?>>=?7;
????len++;
??}
??return?len;
}三.varint解碼
解了編碼的原理，再來看解碼就很輕松了，直接調用GetVarint32Ptr函數，該函數處理value < 128的情況，即varint只占一個字節(jié)的情況，對于varint 大于一個字節(jié)的情況，GetVarint32Ptr調用GetVarint32PtrFallback來處理。
inline?const?char*?GetVarint32Ptr(const?char*?p,
??????????????????????????????????const?char*?limit,
??????????????????????????????????uint32_t*?value)?{
??if?(p?<?limit)?{
????uint32_t?result?=?*(reinterpret_cast(p));
????if?((result?&?128)?==?0)?{
??????*value?=?result;
??????return?p?+?1;
????}
??}
??return?GetVarint32PtrFallback(p,?limit,?value);
}在GetVarint32Ptr和GetVarint32PtrFallback函數中，參數p是指向一個包含varint的字符串，limit在調用的時候都是賦值為limit= p + 5, 這是因為varint最多占用5個字節(jié)。value用于存儲返回的int值。
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(p));
????p++;
????if?(byte?&?128)?{
??????//?More?bytes?are?present
??????result?|=?((byte?&?127)?<<?shift);
????}?else?{
??????result?|=?(byte?<<?shift);
??????*value?=?result;
??????return?reinterpret_cast(p);
????}
??}
??return?NULL;
}64位的解碼與32位的類似。
下載文檔
