一、前言

當(dāng)我們需要對(duì)一些信息進(jìn)行存儲(chǔ)或者傳輸時(shí)，通常需要用一種數(shù)據(jù)協(xié)議，將信息轉(zhuǎn)換為可存儲(chǔ)或傳輸?shù)男问剑ǘM(jìn)制字節(jié)流、經(jīng)過(guò)編碼的文本等）。
特別地，當(dāng)數(shù)據(jù)源是對(duì)象時(shí)，轉(zhuǎn)化對(duì)象的過(guò)程被稱為序列化，反之，從編碼數(shù)據(jù)轉(zhuǎn)化為對(duì)象的過(guò)程被稱為反序列化。
而協(xié)議本身，有的地方稱之為數(shù)據(jù)交換格式(data interchange format)。
數(shù)據(jù)交換格式

轉(zhuǎn)換為文本的協(xié)議，最常用的是XML和json。
XML協(xié)議擅長(zhǎng)描述，用于構(gòu)建網(wǎng)頁(yè)文檔，Android的頁(yè)面搭建等效果不錯(cuò)，其缺點(diǎn)是解析效率一般
JSON協(xié)議具備較好的可讀性，解析效率也不錯(cuò)，面向閱讀和面向機(jī)器都比較友好，在數(shù)據(jù)協(xié)議的選型時(shí)，通常會(huì)被優(yōu)先選用。

通常而言，一些實(shí)現(xiàn)得比較好的二進(jìn)制協(xié)議的方案，相對(duì)于xml/json協(xié)議的各種實(shí)現(xiàn)，在效率和編碼體積方面有一定優(yōu)勢(shì)。
當(dāng)json協(xié)議性能不能滿足需求時(shí)，大家會(huì)轉(zhuǎn)而考慮二進(jìn)制的數(shù)據(jù)協(xié)議。
而二進(jìn)制的數(shù)據(jù)協(xié)議，多如牛毛，不可勝數(shù)（protobuf, protostuff, thrift, msgpack, avro ...), 挑花了眼，
然后發(fā)現(xiàn)在易用性方面和json差太多...

在性能和易用性方面，其實(shí)有很多空間。
在查了各種資料，耗費(fèi)了許多時(shí)日之后，終于實(shí)現(xiàn)了一種既高效又易用的序列化方案。
目前給方案取名：Packable。

本文分了幾章介紹Packable：

• 第2、3章：協(xié)議設(shè)計(jì)；
• 第4章： 簡(jiǎn)單介紹實(shí)現(xiàn)；
• 第5章：使用方法；
• 第6章：性能測(cè)試；
• 第7章：回顧總結(jié)。

設(shè)計(jì)和實(shí)現(xiàn)部分（2、3、4章）會(huì)比較晦澀，如果之前沒(méi)有了解過(guò)protobuf等協(xié)議的原理/實(shí)現(xiàn)，光看文章的話閱讀體驗(yàn)很差，建議先跳過(guò)；
看了使用方法和性能測(cè)試部分，如果覺(jué)得感興趣，再回頭看；
平時(shí)喜歡閱讀源碼，喜歡各種源碼分析的朋友，可以跑一下代碼，結(jié)合源碼看會(huì)更有閱讀體驗(yàn)。

二、Protobuf協(xié)議

任何成果都不是憑空產(chǎn)生的，在“前輩”的基礎(chǔ)上繼續(xù)探索，才能走得更遠(yuǎn)。
在調(diào)研了各種二進(jìn)制協(xié)議之后，最終選擇參考protobuf協(xié)議。
雖然protobuf有不少缺點(diǎn)，但其中也包含了一些不錯(cuò)的設(shè)計(jì)技巧，值得借鑒。

2.1 構(gòu)型

序列化協(xié)議要想支持向前兼容和向后兼容，基本構(gòu)型都是:

[key value key value ....]

value可能是基礎(chǔ)數(shù)據(jù)類型，也可能是復(fù)合對(duì)象，最終，整個(gè)構(gòu)成一棵“對(duì)象樹(shù)”。
C/C++的結(jié)構(gòu)體，Android的Parcelable等沒(méi)有key的部分，而是直接依次存取value, 但這樣的話就不能版本兼容和跨平臺(tái)了。

2.2 數(shù)據(jù)布局

json協(xié)議是通過(guò)特定符號(hào)來(lái)分隔key/value，解析時(shí)需要找到“符號(hào)對(duì)（引號(hào)，括號(hào)）”來(lái)確定數(shù)據(jù)的邊界；
而protobuf則是通過(guò)type和lenght來(lái)確定數(shù)據(jù)邊界，從而在解析時(shí)只需前序深度遍歷即可。
還有就是，由于不需要分隔符，所以不需要對(duì)特定符號(hào)轉(zhuǎn)義編碼，這也是相對(duì)于xml/json等效率更好的原因之一。

Protobuf的字段布局如下：

<index> <type> [length] <data>

• index是在.proto文件聲明的編號(hào)；
• type并不是具體語(yǔ)言平臺(tái)的“類型”，而是proto自身聲明的“類型”，用于告知程序如何編碼/解碼。
  取值如下：
  
  
  比方說(shuō).proto文件中聲明 fixed32或者float, 編碼時(shí)type皆為5（二進(jìn)制的101，占3bit)。
  真正的語(yǔ)言層面的“類型”，在編譯階段決定， 可以是int類型，也可以是float類型。
  其實(shí)json也是如此，例如{"number":100}, number是int、long、float還是double，得看怎么去讀取。
• lenght：數(shù)據(jù)長(zhǎng)度，當(dāng)value是字符串，數(shù)組或者嵌套對(duì)象時(shí)，才會(huì)有l(wèi)ength; 基礎(chǔ)類型不需要length，因?yàn)榛A(chǔ)類型的length是可知的。
• data： value的數(shù)據(jù)本身。

舉例：

message Result {
    int32 count = 1;
}

message Data { 
    string msg = 1;
    Result result = 2;
}

{
    "msg":"abc",
    "result":{
        "count":1
    }
}

|00001|010|00000011|'a' 'b' 'c'|00010|010|00000010|00001|000|00000100|
+-----+---+--------+-----------+-----+---+--------+-----+---+--------+
 index type length    data      index type length  index type  data
                                                  |<-------count---->|
|<------------ msg ----------->|<------------- result -------------->|

type最大取值為5，用3bit即可表示，所可以聯(lián)合index編碼；
在protobuf協(xié)議中，(index|type)、lenght、以及當(dāng)type=0時(shí)的data，都是用varint編碼的。

2.3 編碼

2.3.1 varint

顧名思義，“可變的整數(shù)”，用可變長(zhǎng)編碼表示整數(shù)。
4字節(jié)的varint的表示方式如下：

   0 ~ 2^07 - 1 0xxxxxxx
2^07 ~ 2^14 - 1 1xxxxxxx 0xxxxxxx
2^14 ~ 2^21 - 1 1xxxxxxx 1xxxxxxx 0xxxxxxx
2^21 ~ 2^28 - 1 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx
2^28 ~ 2^35 - 1 1xxxxxxx 1xxxxxxx 1xxxxxxx 1xxxxxxx 0xxxxxxx

8字節(jié)的varint以此類推。
varint編碼在較小的正整數(shù)通常能節(jié)約空間，比如在[0,127]區(qū)間的整數(shù)可以用一個(gè)字節(jié)表示，但是在表示較大的整數(shù)時(shí)有可能節(jié)約不了空間，在表示負(fù)數(shù)時(shí)甚至比會(huì)占用更多空間(int占5字節(jié)，long占10字節(jié)）。

2.3.2 zigzag

負(fù)數(shù)的最高位是“1”，所以varint編碼負(fù)數(shù)會(huì)占用更大的空間，為了解決這個(gè)問(wèn)題，protobuf引入zigzag編碼。
其運(yùn)算規(guī)則如下：

(n << 1) ^ (n >> 31) // 編碼
(n >>> 1) ^ -(n & 1) // 解碼

zigzag編碼后，數(shù)值變?yōu)椤罢麛?shù)”，按絕對(duì)值排序（原來(lái)是正數(shù)的排在原來(lái)是負(fù)數(shù)的后面）。
如此，對(duì)于一些絕對(duì)值小的負(fù)數(shù)，先經(jīng)過(guò)zigzag編碼，再進(jìn)行varint編碼時(shí)，編碼長(zhǎng)度比較短。
但對(duì)于絕對(duì)值本來(lái)就較大的整數(shù)，zigzag編碼對(duì)空間占用并無(wú)幫助，甚至適得其反。
當(dāng)proto文件中字段聲明為sint32或者sint64時(shí)，該字段會(huì)啟用zigzag編碼。

2.3.3 字符串編碼

protobuf對(duì)字符串統(tǒng)一使用utf-8編碼。

2.3.4 大端小端

當(dāng)type=1或者type=5, 使用固定長(zhǎng)度，小端字節(jié)序。

三、Packable協(xié)議設(shè)計(jì)

3.1 基本編碼規(guī)則

packable參考protobuf, 構(gòu)型也是 ：

[key value key value ....]

但數(shù)據(jù)布局有所區(qū)別：

<flag> <type> <index> [length] [data]

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  flag  | type  |    index    |            value           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  1bit  | 3bit  |   4~12 bit  |                            |

和protobuf的區(qū)別在于：
1、packable的index從0開(kāi)始，而protobuf從1開(kāi)始；
2、不用varint去編碼index和type，而是固定用一到兩個(gè)字節(jié)編碼；
3、value可以不存在（當(dāng)type=0時(shí)）。

當(dāng)index∈[0,15]時(shí)，flag=0, [flag|type|index]用一個(gè)字節(jié)表示；
當(dāng)index∈[16,255]時(shí)，flag=1 [flag|type|0000]為第一個(gè)字節(jié)，index獨(dú)占第二個(gè)字節(jié)。
目前暫不支持大于255的index, 事實(shí)上一個(gè)對(duì)象也沒(méi)多么字段，后面真的用上的話，再拓展第一個(gè)字節(jié)的低4bit即可。
雖然布局不一樣，但是效用是相似的，都是在15以內(nèi)占一個(gè)字節(jié)，大于15占兩個(gè)字節(jié)（Protobuf支持index的范圍更大，但是通常用不到這么多）。
為什么不用varint來(lái)編碼type和index呢？哈哈，既然都重新設(shè)計(jì)了，怎么方便實(shí)現(xiàn)就怎么來(lái)吧。

然后就是，packable的type和protobuf的定義和作用有所不同。
protobuf的type也是占用3bit, 3bit可以表示8個(gè)定義， 但并沒(méi)利用起來(lái)；事實(shí)上protobuf本可用2bit來(lái)表示type(只有varint、32-bit、64-bit、Length-delimited)四種定義。

packable的Type定義和作用如下：

• 1、一個(gè)對(duì)象有時(shí)候有很多未賦值的字段，通常默認(rèn)值是0，空字符串等，可將這類值的type設(shè)為0，而lenght和value字段不需要填充。
  在此情況下，相比于protobuf的varint和Length-delimited能節(jié)省1各子節(jié)，相比于protobuf的32-bit和64-bit分別節(jié)省4和8字節(jié)。
• 2、packable整數(shù)類型不用varint編碼，因?yàn)樵趖ype中定義好了存放了多少個(gè)字節(jié)。
  比如一個(gè)long類型的變量，如果其值在[1,255], 編碼時(shí)將其type設(shè)為1, 解碼時(shí)只讀取1個(gè)字節(jié)。
  type∈[1,4]的處理是類似的，看數(shù)值的有效位決定需要編碼多少字節(jié)。
  packable的整數(shù)在[128,255]區(qū)間仍可以用1個(gè)字節(jié)編碼，而varint編碼則需要兩個(gè)字節(jié)；
  向上可以依此類推，極端地，varint編碼表示long最多需要10字節(jié)，而packable在最壞的情況下也只需8個(gè)字節(jié)。
  并且，直接讀寫int/long比varint編碼效率更高。
• 3、當(dāng)字段為可變對(duì)象（字符串，數(shù)組，對(duì)象）時(shí)，長(zhǎng)度也不用varint編碼，因?yàn)閺膖ype中就知道用多少字節(jié)存儲(chǔ)“l(fā)enght"。

packable充分利用了type的表示空間，從而節(jié)省編碼空間和計(jì)算時(shí)間。

3.2 數(shù)組的編碼

為簡(jiǎn)化描述，我們約定

key = <flag> <type> <index>

3.2.1 基礎(chǔ)類型數(shù)組

基礎(chǔ)類型的數(shù)據(jù)布局:

<key> [length] [v1 v2 ...]

• 數(shù)組元素依此按小端編碼；
• 由于基礎(chǔ)數(shù)據(jù)類型的長(zhǎng)度是固定的，所以解碼時(shí)讀取長(zhǎng)度之后，除以基礎(chǔ)類型的字節(jié)數(shù)即可得出元素個(gè)數(shù)。
  比如，如果是int/float數(shù)組，則size = length / 4。

3.2.2 字符串?dāng)?shù)組

<key> [length] [size] [len1 v1 len2 v2 ...]

• 由于字符串長(zhǎng)度不固定，所以需要編碼size.這里用varint去編碼size，因?yàn)閟ize是正整數(shù)（字符串非空時(shí)），而且通常比較小，用varint編碼能節(jié)約空間。
• 如果數(shù)組元素個(gè)數(shù)為0，則type=0, 此時(shí)不需要編碼value部分。
• 字符串的編碼由“長(zhǎng)度+內(nèi)容”構(gòu)成，其中“內(nèi)容”是可省略的（當(dāng)字符串為空字符串或者null時(shí)）。
• 當(dāng)字符串為null時(shí)，len=-1。
• 數(shù)組的length從key中的type可以得知本身占多少字節(jié)；而字符串的len沒(méi)有額外信息表示自身占多少字節(jié)，為此，len也采用varint編碼（一般字符串不會(huì)太長(zhǎng)，尤其是數(shù)組中的字符串，用varint編碼可節(jié)約空間）。

3.2.3 對(duì)象數(shù)組

<key> [length] [size] [len1 v1 len2 v2 ...]

對(duì)象數(shù)組和字符串?dāng)?shù)組的數(shù)據(jù)布局一樣，
只是len的編碼規(guī)則不同：

• 當(dāng)對(duì)象為null時(shí)，len=0xFFFF；
• len<=0x7FFF時(shí)， len用兩個(gè)字節(jié)編碼；
• 當(dāng)len>0x7FFF時(shí)，len用4個(gè)字節(jié)編碼。

為什么不和字符串一樣用varint編碼呢？
主要是基于實(shí)現(xiàn)的層面考慮: 編碼對(duì)象之前不知道對(duì)象需要占用多少個(gè)字節(jié)，用varint編碼的話，不知道要預(yù)留給多少空間給len，大概率會(huì)預(yù)留不準(zhǔn)；然后當(dāng)寫入value完成之后，了能需要移動(dòng)字節(jié)，以便給len預(yù)留準(zhǔn)確的空間，這樣效率就低了。
所以，直接預(yù)留兩個(gè)字節(jié)，可以確保長(zhǎng)度在32767之內(nèi)的對(duì)象編碼寫入buffer后不需要移動(dòng)，以提高效率；
當(dāng)長(zhǎng)度大于32767, 需要向后移動(dòng)兩個(gè)字節(jié)，而這么長(zhǎng)的對(duì)象，編碼的時(shí)間本身就不少，相比而言移動(dòng)字節(jié)的時(shí)間占比就低了。

3.2.4 字典

存儲(chǔ)key-value對(duì)的數(shù)據(jù)結(jié)構(gòu)，有的編程語(yǔ)言中叫Dictionary，有的叫Map, 是同一個(gè)東西。
編碼時(shí)可以視之為 key-value 的數(shù)組：

<key> [length] [size] [k1 v1 k2 v2 ...]

key或value的有各種類型，為基礎(chǔ)數(shù)據(jù)類型時(shí)，直接固定長(zhǎng)度編碼，為可變長(zhǎng)類型時(shí)，按照可變長(zhǎng)類型數(shù)組的規(guī)則編碼。

3.3 壓縮編碼

對(duì)于某些具備特定的特征的數(shù)值，可以添加某些編碼規(guī)則，達(dá)到節(jié)省空間的目的。
需要聲明的是，接下來(lái)的這些方法，不一定能”壓縮“，僅當(dāng)符合特征時(shí)有效。

3.3.1 zigzag

zigzag編碼前面介紹過(guò)，packable也保留這個(gè)選項(xiàng)。

public PackEncoder putSInt(int index, int value) {
    return putInt(index, (value << 1) ^ (value >> 31));
}

其實(shí)就是在putInt之前加一個(gè)編碼。
建議僅當(dāng)數(shù)值包含絕對(duì)值較小的負(fù)數(shù)才啟用此方法，一般情況下直接使用putInt即可。

3.3.2 double類型

關(guān)于浮點(diǎn)數(shù)的二進(jìn)制的表示方法，如果要講可以抽出一篇來(lái)講，考慮篇幅和主題，本篇就不細(xì)述了。
直接說(shuō)結(jié)論：

• 1、 double類型占8個(gè)字節(jié)
• 2、 對(duì)于一些能夠以較少的2^n組合而成的數(shù)值，后面的字節(jié)都是0。
  n可正可負(fù)，n為負(fù)數(shù)時(shí)，十進(jìn)制形式有“小數(shù)”，例如， 2^-1=0.5, 2^-2=0.25。
• 3、更普適一點(diǎn)的結(jié)論：對(duì)于絕對(duì)值小于等于2^21（2097152）的整數(shù)，后四個(gè)字節(jié)都是0。

下面是舉例一些數(shù)值，方便直觀感受：

a:-2.0      1 1000000-0000 0000-00000000-00000000-00000000-00000000-00000000-00000000
a:-1.0      1 0111111-1111 0000-00000000-00000000-00000000-00000000-00000000-00000000
a:0.0       0 0000000-0000 0000-00000000-00000000-00000000-00000000-00000000-00000000
a:0.5       0 0111111-1110 0000-00000000-00000000-00000000-00000000-00000000-00000000
a:1.0       0 0111111-1111 0000-00000000-00000000-00000000-00000000-00000000-00000000
a:1.5       0 0111111-1111 1000-00000000-00000000-00000000-00000000-00000000-00000000
a:2.0       0 1000000-0000 0000-00000000-00000000-00000000-00000000-00000000-00000000
a:3.98      0 1000000-0000 1111-11010111-00001010-00111101-01110000-10100011-11010111
a:31.0      0 1000000-0011 1111-00000000-00000000-00000000-00000000-00000000-00000000
a:32.0      0 1000000-0100 0000-00000000-00000000-00000000-00000000-00000000-00000000
a:33.0      0 1000000-0100 0000-10000000-00000000-00000000-00000000-00000000-00000000
a:1999.0    0 1000000-1001 1111-00111100-00000000-00000000-00000000-00000000-00000000
a:3999.0    0 1000000-1010 1111-00111110-00000000-00000000-00000000-00000000-00000000
a:2097151.0 0 1000001-0011 1111-11111111-11111111-00000000-00000000-00000000-00000000
a:2097152.0 0 1000001-0100 0000-00000000-00000000-00000000-00000000-00000000-00000000
a:2097153.0 0 1000001-0100 0000-00000000-00000000-10000000-00000000-00000000-00000000

第三點(diǎn)結(jié)論比較有價(jià)值：
如果字段是double類型，但是通常情況下是整數(shù)（比方說(shuō)商品價(jià)格，而商品又是整數(shù)價(jià)格居多），那么是有壓縮空間的。
packable提供了double類型的壓縮選項(xiàng)，啟用時(shí)，編碼過(guò)程為：
1、將double轉(zhuǎn)為long；
2、調(diào)換低位的四個(gè)字節(jié)和高位的四個(gè)字節(jié)；
3、按照l(shuí)ong的編碼方式編碼（long類型編碼時(shí)，如果高位的四個(gè)字節(jié)是0，會(huì)用只編碼低位的4個(gè)字節(jié)）。
如此，對(duì)于符合條件的double類型數(shù)據(jù)，能夠節(jié)約4個(gè)字節(jié)。

3.3.3 bool數(shù)組

對(duì)于bool數(shù)組來(lái)說(shuō)，如果用一個(gè)字節(jié)編碼一個(gè)bool值，那太浪費(fèi)了；其實(shí)很容易想到，一個(gè)字節(jié)可以編碼8個(gè)bool值。
因?yàn)閿?shù)組大小不一定是8的倍數(shù)，所以需要額外信息記錄數(shù)組大小。
一個(gè)方案是像對(duì)象數(shù)組一樣在lenght后記錄size, 但是那并不是最有效的；
其實(shí)可以記錄remain=size%8, 解碼的時(shí)候結(jié)合length和remain可以推算出size。
當(dāng)size比較大的時(shí)候，一個(gè)字節(jié)表示不了；而remian總小于8，用3bit就可以表示。

3.3.4 枚舉數(shù)組

當(dāng)枚舉值只能取兩種值（比如“是/否”，“可用/不可用”）時(shí)，可以用一個(gè)bit編碼一個(gè)值；
當(dāng)枚舉值取值為[0,3]時(shí)，可以用2bit編碼一個(gè)值。
依次類推……
當(dāng)然，如果枚舉值大于255，則直接用int編碼就好了。
當(dāng)枚舉值小于等于255時(shí)，可以用一個(gè)字節(jié)編碼一個(gè)或者多個(gè)值。
數(shù)據(jù)布局bool數(shù)組類似：

<key> [length] [remain] [v1 v2  ...]

3.3.5 int/long/double數(shù)組

int/long/double作為單個(gè)字段，因?yàn)閠ype可以記錄占用幾個(gè)字節(jié)的信息，所以可以壓縮；
而作為數(shù)組的元素，是否可以壓縮呢？
每個(gè)值用額外的2比特記錄占用多少字節(jié)即可。
2比特可以表示4種情況，下面是2比特從0到4，對(duì)應(yīng)各種類型所取的值。

int和long都是從低位開(kāi)始取值，因?yàn)楫?dāng)值比較小時(shí)高位為0；
而double由于符號(hào)為和階碼在高位，所以從從高位取值，比如對(duì)于1, 1.5, 2等值，[16,63]的比特皆為0，所以只需記錄高位的2個(gè)字節(jié)即可。
如果值是0，則只用記錄bits皆可，不需要再編碼value了。

壓縮數(shù)組數(shù)據(jù)布局如下：

<key> [length] [size] [bits] [v1 v2  ...]

size用varint編碼；額外的bits跟隨在size后，每個(gè)值占用2bit; 然后后面的數(shù)組根據(jù)自己是否可以壓縮而決定要占用多少子節(jié)。
這種策略不一定有壓縮效果，也是要視數(shù)組本身而定，通常當(dāng)大部分元素都比較小時(shí)又較好的壓縮效果；
極端情況，數(shù)組所有元素皆為0，則[v1 v2 ...]部分為空，每個(gè)元素只占2bit。

如果需要傳輸一張數(shù)據(jù)表的數(shù)據(jù)，不妨以“列”的方式來(lái)組裝數(shù)據(jù)，這樣編解碼更快；
對(duì)于稀疏的字段（多數(shù)情況下為0），或者字段的值比較小，建議采用壓縮策略。

四、框架實(shí)現(xiàn)

限于篇幅，本篇只大概講一下關(guān)鍵過(guò)程，更多細(xì)節(jié)大家可看源碼了解。

4.1 定義類型

回顧上一章，packable的type占用3個(gè)bit, 字節(jié)的最高的bit用來(lái)表示index寫在剩余的4bit還是下一個(gè)字節(jié)。

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  flag  | type  |    index    |            value           |
+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  1bit  | 3bit  |   4~12 bit  |                            |

為此，定義常量如下：

final class TagFormat {
    private static final byte TYPE_SHIFT = 4;
    static final byte BIG_INDEX_MASK = (byte) (1 << 7);
    static final byte TYPE_MASK = 7 << TYPE_SHIFT;
    static final byte INDEX_MASK = 0xF;
    static final int LITTLE_INDEX_BOUND = 1 << TYPE_SHIFT;

    static final byte TYPE_0 = 0;
    static final byte TYPE_NUM_8 = 1 << TYPE_SHIFT;
    static final byte TYPE_NUM_16 = 2 << TYPE_SHIFT;
    static final byte TYPE_NUM_32 = 3 << TYPE_SHIFT;
    static final byte TYPE_NUM_64 = 4 << TYPE_SHIFT;
    static final byte TYPE_VAR_8 = 5 << TYPE_SHIFT;
    static final byte TYPE_VAR_16 = 6 << TYPE_SHIFT;
    static final byte TYPE_VAR_32 = 7 << TYPE_SHIFT;
}

4.2 實(shí)現(xiàn)Buffer類

public final class EncodeBuffer {
    byte[] hb;
    int position;

    public void writeInt(int v) {
        hb[position++] = (byte) v;
        hb[position++] = (byte) (v >> 8);
        hb[position++] = (byte) (v >> 16);
        hb[position++] = (byte) (v >> 24);
    }
    // ... 
}

Buffer類只需提供基本類型的編碼方法即可，buffer擴(kuò)容由調(diào)用者實(shí)現(xiàn)。
因?yàn)橛袝r(shí)候需要連續(xù)寫入多個(gè)值，調(diào)用處統(tǒng)一判斷擴(kuò)容，比每次調(diào)用Buffer接口都做判斷劃算。

4.3 實(shí)現(xiàn)編碼

public final class PackEncoder {
    private final EncodeBuffer buffer;

    final void putIndex(int index) {
        if (index >= TagFormat.LITTLE_INDEX_BOUND) {
            buffer.writeByte(TagFormat.BIG_INDEX_MASK);
        }
        buffer.writeByte((byte) (index));
    }

    public PackEncoder putInt(int index, int value) {
        checkCapacity(6); // 檢查buffer容量
        if (value == 0) {
            putIndex(index);
        } else {
            int pos = buffer.position;
            putIndex(index);
            if ((value >> 8) == 0) {
                buffer.hb[pos] |= TagFormat.TYPE_NUM_8;
                buffer.writeByte((byte) value);
            } else if ((value >> 16) == 0) {
                buffer.hb[pos] |= TagFormat.TYPE_NUM_16;
                buffer.writeShort((short) value);
            } else {
                buffer.hb[pos] |= TagFormat.TYPE_NUM_32;
                buffer.writeInt(value);
            }
        }
        return this;
    }
}

編碼方法的實(shí)現(xiàn)步驟：

• 1、檢查buffer容量，容量不足則擴(kuò)容
• 2、寫入index
• 3、寫入type
  由于index和type所在比特位不同，所以用"|"操作追加即可；
  當(dāng)value為0時(shí)，type=0,所以不需要特別寫入。
• 4、寫入value
  如上舉例的是寫入int, 根據(jù)value的大小寫入對(duì)應(yīng)的字節(jié)。
  比如，假如value < 256, 在只需寫入一個(gè)字節(jié)。
  編碼其他基礎(chǔ)類型大體步驟如上。

編碼對(duì)象則相對(duì)復(fù)雜一些。
需要序列化的對(duì)象實(shí)現(xiàn)Packable的encode方法，用PackEncoder寫入對(duì)象的字段。
如果對(duì)象的字段中又有對(duì)象，那個(gè)對(duì)象也實(shí)現(xiàn)Packable即可（編碼時(shí)會(huì)遞歸調(diào)用）。

public interface Packable {
    void encode(PackEncoder encoder);
}

具體編碼對(duì)象過(guò)程如下：

    public PackEncoder putPackable(int index, Packable value) {
        if (value == null) {
            return this;
        }
        checkCapacity(6);
        int pTag = buffer.position;
        putIndex(index);
        // 預(yù)留 4 字節(jié)，用來(lái)存放length
        buffer.position += 4;
        int pValue = buffer.position;
        value.encode(this);
        if (pValue == buffer.position) {
            buffer.position -= 4; // value為空對(duì)象，回收預(yù)留空間
        } else {
            putLen(pTag, pValue);
        }
        return this;
    }

    private void putLen(int pTag, int pValue) {
        int len = buffer.position - pValue;
        if (len <= 127) {
            buffer.hb[pTag] |= TagFormat.TYPE_VAR_8;
            buffer.hb[pValue - 4] = (byte) len;
            System.arraycopy(buffer.hb, pValue, buffer.hb, pValue - 3, len);
            buffer.position -= 3;
        } else {
            buffer.hb[pTag] |= TagFormat.TYPE_VAR_32;
            buffer.writeInt(pValue - 4, len);
        }
    }

和編碼基礎(chǔ)類型的步驟類似，只是寫入type要后置，因?yàn)閷懭氩呗允窍染幋avalue，結(jié)束之后寫入value的長(zhǎng)度，以及type。
為了避免過(guò)多的字節(jié)移動(dòng)，僅當(dāng)value長(zhǎng)度小于127時(shí)做compact操作（移動(dòng)字節(jié)，壓縮空間）。
那TYPE_VAR_16豈不是用不上了？
編碼數(shù)組或字符串的時(shí)能用上，因?yàn)閷懭隻uffer前就知道需要占用多少字節(jié)，不需要像寫入對(duì)象一樣先預(yù)留length的空間。

大部分框架在實(shí)現(xiàn)編碼時(shí)需要先填充值到容器中，然后再執(zhí)行編碼時(shí)遍歷容器，編碼各節(jié)點(diǎn)到buffer中。
像protobuf的java實(shí)現(xiàn)，寫入一個(gè)對(duì)象，需要先遍歷每個(gè)字段，計(jì)算需要占用多少空間，然后寫入length, 然后再寫入value。如此，對(duì)象的每一個(gè)字段都要訪問(wèn)兩遍。
而packable的寫入策略則是調(diào)用put方法時(shí)即刻寫入，這樣只需要訪問(wèn)一次各個(gè)字段；
雖然編碼一些小對(duì)象時(shí)需要compact操作，但由于需要移動(dòng)的字節(jié)數(shù)不多，而且考慮到空間局部性，總體效率還是可以的。
最重要的是，這樣的策略編碼實(shí)現(xiàn)簡(jiǎn)單！
計(jì)算每個(gè)字段占用空間，需要多出很多代碼，執(zhí)行效率也大打折扣。

4.4 實(shí)現(xiàn)解碼

public interface PackCreator<T> {
    T decode(PackDecoder decoder);
}

public final class PackDecoder {
    static final long NULL_FLAG = ~0;
    static final long INT_MASK = 0xffffffffL;

    private DecodeBuffer buffer;
    private long[] infoArray;
    private int maxIndex = -1;

    private void parseBuffer() {
        // ... 初始化代碼 ...
        while (buffer.hasRemaining()) {
            byte tag = buffer.readByte();
            int index = (tag & TagFormat.BIG_INDEX_MASK) == 0 ? tag & TagFormat.INDEX_MASK : buffer.readByte() & 0xff;
            if (index > maxIndex)  maxIndex = index;
            byte type = (byte) (tag & TagFormat.TYPE_MASK);
            if (type <= TagFormat.TYPE_NUM_64) {
                if (type == TagFormat.TYPE_0) {
                    infoArray[index] = 0L;
                } else if (type == TagFormat.TYPE_NUM_8) {
                    infoArray[index] = ((long) buffer.readByte()) & 0xffL;
                } else if (type == TagFormat.TYPE_NUM_16) {
                    infoArray[index] = ((long) buffer.readShort()) & 0xffffL;
                } else if (type == TagFormat.TYPE_NUM_32) {
                    infoArray[index] = ((long) buffer.readInt()) & 0xffffffffL;
                } else {
                    // TYPE_NUM_64的處理相對(duì)復(fù)雜一些，此處省略 ...
                }
            } else {
                int size;
                if (type == TagFormat.TYPE_VAR_8) {
                    size = buffer.readByte() & 0xff;
                } else if (type == TagFormat.TYPE_VAR_16) {
                    size = buffer.readShort() & 0xffff;
                } else {
                    size = buffer.readInt();
                }
                infoArray[index] = ((long) buffer.position << 32) | (long) size;
                buffer.position += size;
            }
        }
        // 函數(shù)結(jié)束時(shí)，infoArray記錄了各index對(duì)應(yīng)的值、或者位置、長(zhǎng)度等信息
        // 沒(méi)有賦值的且下標(biāo)小于maxIndex的，infoArray[i] = NULL_FLAG
    }

    long getInfo(int index) {
        if (maxIndex < 0) {
            parseBuffer();
        }
        if (index > maxIndex) {
            return NULL_FLAG;
        }
        return infoArray[index];
    }

    public int getInt(int index, int defValue) {
        long info = getInfo(index);
        return info == NULL_FLAG ? defValue : (int) info;
    }

    public <T> T getPackable(int index, PackCreator<T> creator, T defValue) {
        long info = getInfo(index);
        if (info == NULL_FLAG) {
            return defValue;
        }
        int offset = (int) (info >>> 32);
        int len = (int) (info & INT_MASK);
        PackDecoder decoder = pool.getDecoder(offset, len);
        T object = creator.decode(decoder);
        decoder.recycle();
        return object;
    }
}

解碼是編碼的反操作，基本操作包括：

• 1、讀取(type|index)
• 2、分解 type 和 index
• 3、根據(jù) type 讀取對(duì)應(yīng)的值
  讀取的值會(huì)緩存到infoArray[index]，
  其中，如果是基本類型，可以直接將value填入infoArray中，高位補(bǔ)0；
  如果是可變長(zhǎng)類型，則將offset額length拼湊成long, 再填入infoArray中。
• 4、調(diào)用get方法時(shí)讀取值
  讀取基本類型時(shí)，直接讀取infoArray[index]；
  讀取可變長(zhǎng)類型時(shí)，拆解offset和len, 定位到對(duì)應(yīng)位置，讀取指定長(zhǎng)度的value。

調(diào)用getPackable時(shí)，如果Packable對(duì)象有類型嵌套，會(huì)遞歸調(diào)用decode方法，這和編碼時(shí)的遞歸是類似的。

五、用法

5.1 常規(guī)用法

序列化/反序列化對(duì)象時(shí)，實(shí)現(xiàn)如上接口，然后調(diào)用編碼/解碼方法即可。
用例如下：

static class Data implements Packable {
    String msg;
    Item[] items;

    @Override
    public void encode(PackEncoder encoder) {
        encoder.putString(0, msg)
                .putPackableArray(1, items);
    }

    public static final PackCreator<Data> CREATOR = decoder -> {
        Data data = new Data();
        data.msg = decoder.getString(0);
        data.items = decoder.getPackableArray(1, Item.CREATOR);
        return data;
    };
}

static class Item implements Packable {
    int a;
    long b;

    Item(int a, long b) {
        this.a = a;
        this.b = b;
    }

    @Override
    public void encode(PackEncoder encoder) {
        encoder.putInt(0, a);
        encoder.putLong(1, b);
    }

    static final PackArrayCreator<Item> CREATOR = new PackArrayCreator<Item>() {
        @Override
        public Item[] newArray(int size) {
            return new Item[size];
        }

        @Override
        public Item decode(PackDecoder decoder) {
            return new Item(
                    decoder.getInt(0),
                    decoder.getLong(1)
            );
        }
    };
}

static void test() {
    Data data = new Data();
    // 序列化
    byte[] bytes = PackEncoder.marshal(data);
    // 反序列化
    Data data_2 = PackDecoder.unmarshal(bytes, Data.CREATOR);
}

• 序列化
  1、聲明 implements Packable 接口；
  2、實(shí)現(xiàn)encode()方法，編碼各個(gè)字段（PackEncoder提供了各種類型的API）；
  3、調(diào)用PackEncoder.marshal()方法，傳入對(duì)象， 得到字節(jié)數(shù)組。

• 反序列化
  1、創(chuàng)建一個(gè)靜態(tài)對(duì)象，該對(duì)象為PackCreator的實(shí)例；
  2、實(shí)現(xiàn)decode()方法，解碼各個(gè)字段，賦值給對(duì)象；
  3、調(diào)用PackDecoder.unmarshal(), 傳入字節(jié)數(shù)組以及PackCreator實(shí)例，得到對(duì)象。

如果需要反序列化一個(gè)對(duì)象數(shù)組, 需要?jiǎng)?chuàng)建PackArrayCreator的實(shí)例（Java版本如此，其他版本不需要）。
PackArrayCreator繼承于PackCreator，多了一個(gè)newArray方法，簡(jiǎn)單地創(chuàng)建對(duì)應(yīng)類型對(duì)象數(shù)組返回即可。

5.2 直接編碼

上面的舉例只是范例之一，具體使用過(guò)程中，可以靈活運(yùn)用。
1、PackCreator不一定要在需要反序列化的類中創(chuàng)建，在其他地方也可以，可任意命名。
2、如果只需要序列化（發(fā)送方），則只實(shí)現(xiàn)Packable即可，不需要實(shí)現(xiàn)PackCreator，反之亦然。
3、如果沒(méi)有類定義，或者不方便改寫類，也可以直接編碼/解碼。

static void test2() {
    String msg = "message";
    int a = 100;
    int b = 200;

    PackEncoder encoder = new PackEncoder();
    encoder.putString(0, msg)
                .putInt(1, a)
                .putInt(2, b);
    byte[] bytes = encoder.getBytes();

    PackDecoder decoder = PackDecoder.newInstance(bytes);
    String dMsg = decoder.getString(0);
    int dA = decoder.getInt(1);
    int dB = decoder.getInt(2);
    decoder.recycle();
}

5.3 自定義編碼

比方說(shuō)下面這樣一個(gè)類：

class Info  {
    public long id;
    public String name;
    public Rectangle rect;
}

Rectangle是JDK的一個(gè)類），有四個(gè)字段：

class Rectangle {
  int x, y, width, height;
}

當(dāng)然，有很多方案去實(shí)現(xiàn)（讓Rectangle實(shí)現(xiàn)Packable不在其中，因?yàn)椴荒苄薷腏DK）。
packable提供的一種高效（執(zhí)行效率）的方法：

public static class Info implements Packable {
    public long id;
    public String name;
    public Rectangle rect;

    @Override
    public void encode(PackEncoder encoder) {
        encoder.putLong(0, id)
                .putString(1, name);
        // 返回PackEncoder的buffer
        EncodeBuffer buf = encoder.putCustom(2, 16);     // 4個(gè)int, 占16字節(jié)
        buf.writeInt(rect.x);
        buf.writeInt(rect.y);
        buf.writeInt(rect.width);
        buf.writeInt(rect.height);
    }

    public static final PackCreator<Info> CREATOR = decoder -> {
        Info info = new Info();
        info.id = decoder.getLong(0);
        info.name = decoder.getString(1);
        DecodeBuffer buf = decoder.getCustom(2);
        if (buf != null) {
            info.rect = new Rectangle(
                    buf.readInt(),
                    buf.readInt(),
                    buf.readInt(),
                    buf.readInt());
        }
        return info;
    };
}

通常情況下，大對(duì)象嵌套一些固定字段的小對(duì)象還是挺常見(jiàn)的。
用此方法，可以減少遞歸層次，以及減少index的解析，能提升不少效率，

5.4 類型支持

以上是packable的序列化/反序列化的整體用法。
具體到PackEncoder/PackDecoder，又提供了哪些接口呢（支持什么類型）？
以PackEncoder為例，部分接口如下：

• 基礎(chǔ)類型中的putSInt、putSLong和putCDouble是帶壓縮編碼（參考3.3節(jié)）。
• Map的key-value類型組合太多了，所以只實(shí)現(xiàn)了部分常用類型，然后留了一個(gè)putMap接口提供自定義實(shí)現(xiàn)。

六、性能測(cè)試

除了protobuf之外，還選擇了gson (json協(xié)議的序列化框架之一，java平臺(tái)）來(lái)做下比較。

空間方面，序列化后數(shù)據(jù)大?。?/p>

packable和protobuf大小相近（packable略?。?，約為gson的57%。

耗時(shí)方面，分別在PC和手機(jī)上測(cè)試了兩組數(shù)據(jù)：

1. Macbook Pro

2. 榮耀20S

需要說(shuō)明的是，數(shù)據(jù)特征，測(cè)試平臺(tái)等因素都會(huì)影響結(jié)果，以上測(cè)試結(jié)果僅供參考。
大家可自行用自己的業(yè)務(wù)數(shù)據(jù)對(duì)比一下。

七、總結(jié)

通常而言packable和protobuf性能方面比json的要好，但可讀性方面是硬傷。
一種改善可讀性的方案：將二進(jìn)制內(nèi)容反序列化成Java對(duì)象，再用Gson等框架轉(zhuǎn)化為json。

總體而言，packable有以下優(yōu)點(diǎn)：

• 1、性能優(yōu)異
  編碼解碼速度快；
  編碼后的消息提交小。
• 2、代碼輕量
  一方面是包體積，以Java為例，protobuf的jar包接近2M（lite版會(huì)輕一些，幾百K），而packable的jar包只有37K；
  另一方面是新增消息類型所需要的代碼量，例如前面一節(jié)所定義的數(shù)據(jù)類型，protobuf編譯出來(lái)的java文件有五千多行，而packable所定義的類文件只有百來(lái)行。
• 3、使用方便
  使用protobuf的過(guò)程相對(duì)繁瑣，需要編寫.proto文件、編譯成對(duì)應(yīng)語(yǔ)言平臺(tái)的代碼、拷貝到項(xiàng)目中、項(xiàng)目集成SDK……
  如果需要新增字段，需要修改.proto文件，重新編輯，再次拷貝到項(xiàng)目中。
  相對(duì)而言，packable可以在現(xiàn)有的對(duì)象改造，對(duì)于已經(jīng)定義好的類，實(shí)現(xiàn)相關(guān)接口即可，相關(guān)的實(shí)現(xiàn)和調(diào)用都不需要變更，
  如果需要增刪字段，也只需直接在代碼中增刪字段即可。
• 4、方法靈活
  可以單實(shí)現(xiàn)序列化的接口（或者反序列化接口）；
  除了對(duì)象序列化/反序列化，也支持直接編碼，自定義編碼等。
• 5、支持各種類型，可變對(duì)象支持null類型（protobuf不支持）。
• 6、支持多種壓縮策略

語(yǔ)言支持方面，packable目前實(shí)現(xiàn)了Java、C++、C#、Objective-C、Go等版本，協(xié)議是一致的，可以在不同語(yǔ)言平臺(tái)間相互傳輸。

項(xiàng)目地址：https://github.com/BillyWei01/Packable

備注：
基于降低復(fù)雜度的考慮， Packable 后來(lái)移除的Double的壓縮編碼。
在本篇文章中沒(méi)有做對(duì)應(yīng)的闡述調(diào)整，只同步調(diào)整了其他平臺(tái)的文章：
https://juejin.cn/post/6992380683977130015
（多平臺(tái)更新確實(shí)比較費(fèi)精力，所以沒(méi)有針對(duì)各個(gè)平臺(tái)做同步調(diào)整，抱歉。）