LevelDB源碼分析之一：coding

LevelDB默認使用的是小端字節(jié)序存儲，低位字節(jié)排放在內(nèi)存的低地址端，高位字節(jié)排放在內(nèi)存的高地址端。?
編碼分為變長的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
}

這兩個函數(shù)非常簡單，功能就是判斷系統(tǒng)是否為小端存儲，如果是，直接將value拷貝到buf，如果不是，則將value轉(zhuǎn)換為小端字節(jié)序存儲到buf中。
解碼函數(shù)DecodeFixed32和DecodeFixed64是編碼的逆過程，也很簡單。
二.EncodeVarint
為什么要把整型（int）編碼成變長整型（varint）呢？是為了盡可能的節(jié)約存儲空間。
varint是一種緊湊的表示數(shù)字的方法，它用一個或多個字節(jié)來表示一個數(shù)字，值越小的數(shù)字使用越少的字節(jié)數(shù)。比如int32類型的數(shù)字，一般需要4個字節(jié)。但是采用Varint，對于很小的int32類型的數(shù)字，則可以用1個字節(jié)來表示。當然凡事都有好的也有不好的一面，采用varint表示法，大的數(shù)字則可能需要5個字節(jié)來表示。從統(tǒng)計的角度來說，一般不會所有消息中的數(shù)字都是大數(shù)，因此大多數(shù)情況下，采用varint后，可以用更小的字節(jié)數(shù)來表示數(shù)字信息。
varint中的每個字節(jié)的最高位（bit）有特殊含義，如果該位為1，表示后續(xù)的字節(jié)也是這個數(shù)字的一部分，如果該位為0，則結(jié)束。其他的7位（bit）都表示數(shù)字。7位能表示的最大數(shù)是127，因此小于128的數(shù)字都可以用一個字節(jié)表示。大于等于128的數(shù)字，比如說300，會用兩個字節(jié)在內(nèi)存中表示為：
低 ? ? ? ? ? ? ? 高
1010 1100 0000 0010
實現(xiàn)過程如下：
300的二進制為100101100，取低7位也就是010 1100放在內(nèi)存低字節(jié)中，由于第二個字節(jié)也是數(shù)字的一部分，因此內(nèi)存低字節(jié)的最高位為1，則完整的內(nèi)存低字節(jié)為1010 1100。300的高2位也就是10放到內(nèi)存的高字節(jié)中，因為數(shù)字到該字節(jié)結(jié)束，因此該字節(jié)包括最高位的其他6位都用0填充，則完整的內(nèi)存高字節(jié)為0000 0010。
正常情況下，int需要32位，varint用一個字節(jié)的最高位作為標識位，所以，一個字節(jié)只能存儲7位，如果整數(shù)特別大，可能需要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，給內(nèi)存高字節(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);
}

下面的函數(shù)是計算整型編碼后的長度，也就是varint的長度。

int?VarintLength(uint64_t?v)?{
??int?len?=?1;
??while?(v?>=?128)?{
????v?>>=?7;
????len++;
??}
??return?len;
}

三.varint解碼

解了編碼的原理，再來看解碼就很輕松了，直接調(diào)用GetVarint32Ptr函數(shù)，該函數(shù)處理value < 128的情況，即varint只占一個字節(jié)的情況，對于varint 大于一個字節(jié)的情況，GetVarint32Ptr調(diào)用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函數(shù)中，參數(shù)p是指向一個包含varint的字符串，limit在調(diào)用的時候都是賦值為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位的類似。