一．問(wèn)題的提出
這里的編碼，具體是指如何高效地將基本類型序列化，以便在網(wǎng)絡(luò)上傳輸，不是指將整個(gè)數(shù)據(jù)包用utf8或base64等編碼，更不是應(yīng)用層和業(yè)務(wù)相關(guān)的編碼。
假若有定義如下：
#pragma
pack(1)
typedef
struct tagS_HDR
{
uint8 nProtocol;//協(xié)議類型
uint16
nLength;//消息長(zhǎng)度，不包括本消息頭
uint16
nType;//消息類型
uint8 nExt;//協(xié)議擴(kuò)展標(biāo)記，比如消息子類型
}S_HDR;
#pragma
pack()
typedef
struct tagS_FileTxHDR_Req
{
S_HDR hdr_;//消息頭
uint32 nUID_;//接收方用戶唯一ID
string sFileName_;//要傳送的文件名
uint32 nFileSize_;//文件大小
uint8 nFileID_;//臨時(shí)分配的文件ID,最多支持同時(shí)傳256個(gè)文件
}S_FileTxHDR_Req;
如果你是做服務(wù)器開(kāi)發(fā)，對(duì)類似這樣的結(jié)構(gòu)體應(yīng)該非常熟悉,為了簡(jiǎn)化問(wèn)題，在繼續(xù)討論之前，我們做幾個(gè)假設(shè)：
(1)消息頭的長(zhǎng)度是固定的，且設(shè)計(jì)足夠高效，不在編碼優(yōu)化之列。
(2)整形里面只關(guān)注uint8,uint16.uint32.
(3)字符串關(guān)注兩類：以\0結(jié)尾的string和二進(jìn)制流的bytes。
(4)其它類型暫不關(guān)注，不影響問(wèn)題的討論，后續(xù)會(huì)慢慢完善。
（5）libprotobuf已經(jīng)很強(qiáng)大，但也有限制，比如必須鏈接一個(gè)庫(kù)，如果是手機(jī)客戶端和服務(wù)器通訊，顯然是不能用的。
場(chǎng)景如下：A(ID為123)要給B（ID為456）發(fā)送file.txt文件，文件內(nèi)容為”Hello World!”,傳統(tǒng)的序列化方式為nUID占用4個(gè)字節(jié)，nFileSize也占用4個(gè)字節(jié)，而事實(shí)上456用2個(gè)字節(jié)表示足以，” Hello World!”的長(zhǎng)度用一個(gè)字節(jié)表示足以。明顯是浪費(fèi)嘛！有沒(méi)有什么辦法解決這個(gè)問(wèn)題呢？當(dāng)然有，答案是：站在巨人的肩上。
二。Base 128 Varints
Google Protobuf里面提出了“Base 128 Varints”編碼，這是一種變字節(jié)長(zhǎng)度的編碼，官方描述為：varints是用一個(gè)或多個(gè)字節(jié)序列化整形的一種方法。我理解要點(diǎn)有三個(gè)(1)操作是序列化(2)操作對(duì)象是整形(3)變長(zhǎng)編碼。重點(diǎn)是最后一點(diǎn)，他是如何編碼的呢？
（1）除了最后一個(gè)字節(jié)，varint中的每個(gè)字節(jié)的最高位設(shè)為1，表示后面還有字節(jié)出現(xiàn)
（2）每個(gè)字節(jié)的低7位看成是一個(gè)組（group），這個(gè)組和他相鄰的下一個(gè)7位組共同存儲(chǔ)某個(gè)整形的“組合表示”，最低有效組在前面。
上面的定義可能比較生硬，我沒(méi)看具體例子之前，也沒(méi)搞明白，我們來(lái)看http://code.google.com/intl/zh-CN/apis/protocolbuffers/docs/encoding.html#varints中的例子：
(1)一個(gè)字節(jié)。下面只有一個(gè)字節(jié)，所以最高位是0，表示十進(jìn)制1
0000 0001
(2)兩個(gè)字節(jié)。
1010 1100 0000 0010
由于第一個(gè)字節(jié)后面還有一個(gè)字節(jié)，所以第一個(gè)字節(jié)的最高位設(shè)置為1，表示后面還有后繼字節(jié)，第二個(gè)字節(jié)的最高位為0。去掉每個(gè)字節(jié)的最高位，我們對(duì)兩個(gè)字節(jié)進(jìn)行分組。第一個(gè)7位組：0101100，第二個(gè)7位組：0000010，組合起來(lái)就是：0101100 0000010，由于最低有效組在前面，所以兩個(gè)7位組進(jìn)行調(diào)換，結(jié)果為：0000010 0101100，中間的空格是為了大家區(qū)分，去掉前面的0，也就是：100101100，十進(jìn)制為1*2^8 + 1*2^5 + 1*2^3 + 1*2^2 =
256 + 32 + 8 + 4 = 300。
（3）三個(gè)字節(jié)。我們換種方式，給定某個(gè)整形，要求寫出他的varint表示，這里當(dāng)然是落在需要3個(gè)字節(jié)表示的整形。16380可以嗎？不可以！因?yàn)?6380 < 2^14，所以2個(gè)字節(jié)足以，我們就以27491為例，27491的二進(jìn)制表示為：
0110 1011 0110 0011
注意這里是高字節(jié)之前，低字節(jié)在后，和varint的編碼規(guī)則相反，首先按照7位一組劃分為：0000001 1010110 1100011，然后反轉(zhuǎn)為：1100011 1010110 0000001，最后將末尾的7位組前面補(bǔ)0組成一個(gè)字節(jié)，兩個(gè)7位組都補(bǔ)1分別組成一個(gè)字節(jié)：
11100011 11010110 00000001
(4)更多字節(jié)。聰明的你可能發(fā)現(xiàn)，varint編碼中4個(gè)字節(jié)最大表示的數(shù)為2^28,非常正確，同時(shí)說(shuō)明了天下沒(méi)有免費(fèi)的午餐，有得有失。Protobuf引入了fixed32解決這個(gè)問(wèn)題的，如果某個(gè)字段經(jīng)常大于2^28,應(yīng)當(dāng)優(yōu)選fixed32，他是固定長(zhǎng)度為32位的。
三．String和bytes
string和bytes的表示形式一致，都是“長(zhǎng)度+值”，其中長(zhǎng)度采用varint編碼，值為字符序列或者二進(jìn)制碼流
如有錯(cuò)誤，請(qǐng)指正，下次會(huì)寫到結(jié)構(gòu)體類型的編碼，對(duì)應(yīng)于libprotobuf的Message概念。