Packable-高效易用的序列化框架

作者: 呼啸长风 | 来源:发表于2021-08-04 09:07 被阅读0次

Packable-高效易用的序列化框架
KryoCocoa
KryoCocoa
FlatBuffers学习笔记
Vue简明教程之入门
一、通过ThinkJS创建项目
WCDB CheatSheet
Vue 初识vue、实例化vue对象
1.Vue系列之初识vue
一步一步了解WCDB

一、前言

当我们需要对一些信息进行存储或者传输时，通常需要用一种数据协议，将信息转换为可存储或传输的形式（二进制字节流、经过编码的文本等）。
特别地，当数据源是对象时，转化对象的过程被称为序列化，反之，从编码数据转化为对象的过程被称为反序列化。
而协议本身，有的地方称之为数据交换格式(data interchange format)。
数据交换格式

转换为文本的协议，最常用的是XML和json。
XML协议擅长描述，用于构建网页文档，Android的页面搭建等效果不错，其缺点是解析效率一般
JSON协议具备较好的可读性，解析效率也不错，面向阅读和面向机器都比较友好，在数据协议的选型时，通常会被优先选用。

通常而言，一些实现得比较好的二进制协议的方案，相对于xml/json协议的各种实现，在效率和编码体积方面有一定优势。
当json协议性能不能满足需求时，大家会转而考虑二进制的数据协议。
而二进制的数据协议，多如牛毛，不可胜数（protobuf, protostuff, thrift, msgpack, avro ...), 挑花了眼，
然后发现在易用性方面和json差太多...

在性能和易用性方面，其实有很多空间。
在查了各种资料，耗费了许多时日之后，终于实现了一种既高效又易用的序列化方案。
目前给方案取名：Packable。

本文分了几章介绍Packable：

第2、3章：协议设计；
第4章：简单介绍实现；
第5章：使用方法；
第6章：性能测试；
第7章：回顾总结。

设计和实现部分（2、3、4章）会比较晦涩，如果之前没有了解过protobuf等协议的原理/实现，光看文章的话阅读体验很差，建议先跳过；
看了使用方法和性能测试部分，如果觉得感兴趣，再回头看；
平时喜欢阅读源码，喜欢各种源码分析的朋友，可以跑一下代码，结合源码看会更有阅读体验。

二、Protobuf协议

任何成果都不是凭空产生的，在“前辈”的基础上继续探索，才能走得更远。
在调研了各种二进制协议之后，最终选择参考protobuf协议。
虽然protobuf有不少缺点，但其中也包含了一些不错的设计技巧，值得借鉴。

2.1 构型

序列化协议要想支持向前兼容和向后兼容，基本构型都是:

[key value key value ....]

value可能是基础数据类型，也可能是复合对象，最终，整个构成一棵“对象树”。
C/C++的结构体，Android的Parcelable等没有key的部分，而是直接依次存取value, 但这样的话就不能版本兼容和跨平台了。

2.2 数据布局

json协议是通过特定符号来分隔key/value，解析时需要找到“符号对（引号，括号）”来确定数据的边界；
而protobuf则是通过type和lenght来确定数据边界，从而在解析时只需前序深度遍历即可。
还有就是，由于不需要分隔符，所以不需要对特定符号转义编码，这也是相对于xml/json等效率更好的原因之一。

Protobuf的字段布局如下：

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

index是在.proto文件声明的编号；
type并不是具体语言平台的“类型”，而是proto自身声明的“类型”，用于告知程序如何编码/解码。
取值如下：

比方说.proto文件中声明 fixed32或者float, 编码时type皆为5（二进制的101，占3bit)。
真正的语言层面的“类型”，在编译阶段决定，可以是int类型，也可以是float类型。
其实json也是如此，例如{"number":100}, number是int、long、float还是double，得看怎么去读取。
lenght：数据长度，当value是字符串，数组或者嵌套对象时，才会有length; 基础类型不需要length，因为基础类型的length是可知的。
data： value的数据本身。

举例：

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即可表示，所可以联合index编码；
在protobuf协议中，(index|type)、lenght、以及当type=0时的data，都是用varint编码的。

2.3 编码

2.3.1 varint

顾名思义，“可变的整数”，用可变长编码表示整数。
4字节的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字节的varint以此类推。
varint编码在较小的正整数通常能节约空间，比如在[0,127]区间的整数可以用一个字节表示，但是在表示较大的整数时有可能节约不了空间，在表示负数时甚至比会占用更多空间(int占5字节，long占10字节）。

2.3.2 zigzag

负数的最高位是“1”，所以varint编码负数会占用更大的空间，为了解决这个问题，protobuf引入zigzag编码。
其运算规则如下：

(n << 1) ^ (n >> 31) // 编码
(n >>> 1) ^ -(n & 1) // 解码

zigzag编码后，数值变为“正整数”，按绝对值排序（原来是正数的排在原来是负数的后面）。
如此，对于一些绝对值小的负数，先经过zigzag编码，再进行varint编码时，编码长度比较短。
但对于绝对值本来就较大的整数，zigzag编码对空间占用并无帮助，甚至适得其反。
当proto文件中字段声明为sint32或者sint64时，该字段会启用zigzag编码。

2.3.3 字符串编码

protobuf对字符串统一使用utf-8编码。

2.3.4 大端小端

当type=1或者type=5, 使用固定长度，小端字节序。

三、Packable协议设计

3.1 基本编码规则

packable参考protobuf, 构型也是：

[key value key value ....]

但数据布局有所区别：

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

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

和protobuf的区别在于：
1、packable的index从0开始，而protobuf从1开始；
2、不用varint去编码index和type，而是固定用一到两个字节编码；
3、value可以不存在（当type=0时）。

当index∈[0,15]时，flag=0, [flag|type|index]用一个字节表示；
当index∈[16,255]时，flag=1 [flag|type|0000]为第一个字节，index独占第二个字节。
目前暂不支持大于255的index, 事实上一个对象也没多么字段，后面真的用上的话，再拓展第一个字节的低4bit即可。
虽然布局不一样，但是效用是相似的，都是在15以内占一个字节，大于15占两个字节（Protobuf支持index的范围更大，但是通常用不到这么多）。
为什么不用varint来编码type和index呢？哈哈，既然都重新设计了，怎么方便实现就怎么来吧。

然后就是，packable的type和protobuf的定义和作用有所不同。
protobuf的type也是占用3bit, 3bit可以表示8个定义，但并没利用起来；事实上protobuf本可用2bit来表示type(只有varint、32-bit、64-bit、Length-delimited)四种定义。

packable的Type定义和作用如下：

Type	Meaning	User For
0	TYPE_0	0，空对象
1	TYPE_NUM_8	boolean, byte, short, int, long
2	TYPE_NUM_16	short, int, long
3	TYPE_NUM_32	int, long, float
4	TYPE_NUM_64	long, double
5	TYPE_VAR_8	长度在[1,255]的可变对象
6	TYPE_VAR_16	长度在[256, 65535]的可变对象
7	TYPE_VAR_32	长度大于65535的可变对象

1、一个对象有时候有很多未赋值的字段，通常默认值是0，空字符串等，可将这类值的type设为0，而lenght和value字段不需要填充。
在此情况下，相比于protobuf的varint和Length-delimited能节省1各子节，相比于protobuf的32-bit和64-bit分别节省4和8字节。
2、packable整数类型不用varint编码，因为在type中定义好了存放了多少个字节。
比如一个long类型的变量，如果其值在[1,255], 编码时将其type设为1, 解码时只读取1个字节。
type∈[1,4]的处理是类似的，看数值的有效位决定需要编码多少字节。
packable的整数在[128,255]区间仍可以用1个字节编码，而varint编码则需要两个字节；
向上可以依此类推，极端地，varint编码表示long最多需要10字节，而packable在最坏的情况下也只需8个字节。
并且，直接读写int/long比varint编码效率更高。
3、当字段为可变对象（字符串，数组，对象）时，长度也不用varint编码，因为从type中就知道用多少字节存储“lenght"。

packable充分利用了type的表示空间，从而节省编码空间和计算时间。

3.2 数组的编码

为简化描述，我们约定

key = <flag> <type> <index>

3.2.1 基础类型数组

基础类型的数据布局:

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

数组元素依此按小端编码；
由于基础数据类型的长度是固定的，所以解码时读取长度之后，除以基础类型的字节数即可得出元素个数。
比如，如果是int/float数组，则size = length / 4。

3.2.2 字符串数组

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

由于字符串长度不固定，所以需要编码size.这里用varint去编码size，因为size是正整数（字符串非空时），而且通常比较小，用varint编码能节约空间。
如果数组元素个数为0，则type=0, 此时不需要编码value部分。
字符串的编码由“长度+内容”构成，其中“内容”是可省略的（当字符串为空字符串或者null时）。
当字符串为null时，len=-1。
数组的length从key中的type可以得知本身占多少字节；而字符串的len没有额外信息表示自身占多少字节，为此，len也采用varint编码（一般字符串不会太长，尤其是数组中的字符串，用varint编码可节约空间）。

3.2.3 对象数组

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

对象数组和字符串数组的数据布局一样，
只是len的编码规则不同：

当对象为null时，len=0xFFFF；
len<=0x7FFF时， len用两个字节编码；
当len>0x7FFF时，len用4个字节编码。

为什么不和字符串一样用varint编码呢？
主要是基于实现的层面考虑: 编码对象之前不知道对象需要占用多少个字节，用varint编码的话，不知道要预留给多少空间给len，大概率会预留不准；然后当写入value完成之后，了能需要移动字节，以便给len预留准确的空间，这样效率就低了。
所以，直接预留两个字节，可以确保长度在32767之内的对象编码写入buffer后不需要移动，以提高效率；
当长度大于32767, 需要向后移动两个字节，而这么长的对象，编码的时间本身就不少，相比而言移动字节的时间占比就低了。

3.2.4 字典

存储key-value对的数据结构，有的编程语言中叫Dictionary，有的叫Map, 是同一个东西。
编码时可以视之为 key-value 的数组：

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

key或value的有各种类型，为基础数据类型时，直接固定长度编码，为可变长类型时，按照可变长类型数组的规则编码。

3.3 压缩编码

对于某些具备特定的特征的数值，可以添加某些编码规则，达到节省空间的目的。
需要声明的是，接下来的这些方法，不一定能”压缩“，仅当符合特征时有效。

3.3.1 zigzag

zigzag编码前面介绍过，packable也保留这个选项。

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

其实就是在putInt之前加一个编码。
建议仅当数值包含绝对值较小的负数才启用此方法，一般情况下直接使用putInt即可。

3.3.2 double类型

关于浮点数的二进制的表示方法，如果要讲可以抽出一篇来讲，考虑篇幅和主题，本篇就不细述了。
直接说结论：

1、 double类型占8个字节
2、对于一些能够以较少的2^n组合而成的数值，后面的字节都是0。
n可正可负，n为负数时，十进制形式有“小数”，例如， 2^-1=0.5, 2^-2=0.25。
3、更普适一点的结论：对于绝对值小于等于2^21（2097152）的整数，后四个字节都是0。

下面是举例一些数值，方便直观感受：

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

第三点结论比较有价值：
如果字段是double类型，但是通常情况下是整数（比方说商品价格，而商品又是整数价格居多），那么是有压缩空间的。
packable提供了double类型的压缩选项，启用时，编码过程为：
1、将double转为long；
2、调换低位的四个字节和高位的四个字节；
3、按照long的编码方式编码（long类型编码时，如果高位的四个字节是0，会用只编码低位的4个字节）。
如此，对于符合条件的double类型数据，能够节约4个字节。

3.3.3 bool数组

对于bool数组来说，如果用一个字节编码一个bool值，那太浪费了；其实很容易想到，一个字节可以编码8个bool值。
因为数组大小不一定是8的倍数，所以需要额外信息记录数组大小。
一个方案是像对象数组一样在lenght后记录size, 但是那并不是最有效的；
其实可以记录remain=size%8, 解码的时候结合length和remain可以推算出size。
当size比较大的时候，一个字节表示不了；而remian总小于8，用3bit就可以表示。

3.3.4 枚举数组

当枚举值只能取两种值（比如“是/否”，“可用/不可用”）时，可以用一个bit编码一个值；
当枚举值取值为[0,3]时，可以用2bit编码一个值。
依次类推……
当然，如果枚举值大于255，则直接用int编码就好了。
当枚举值小于等于255时，可以用一个字节编码一个或者多个值。
数据布局bool数组类似：

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

3.3.5 int/long/double数组

int/long/double作为单个字段，因为type可以记录占用几个字节的信息，所以可以压缩；
而作为数组的元素，是否可以压缩呢？
每个值用额外的2比特记录占用多少字节即可。
2比特可以表示4种情况，下面是2比特从0到4，对应各种类型所取的值。

bits	0	1	2	3
int	-	[0,7]	[0,15]	[0,31]
long	-	[0,7]	[0,15]	[0,63]
double	-	[48-63]	[32,63]	[0,63]

int和long都是从低位开始取值，因为当值比较小时高位为0；
而double由于符号为和阶码在高位，所以从从高位取值，比如对于1, 1.5, 2等值，[16,63]的比特皆为0，所以只需记录高位的2个字节即可。
如果值是0，则只用记录bits皆可，不需要再编码value了。

压缩数组数据布局如下：

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

size用varint编码；额外的bits跟随在size后，每个值占用2bit; 然后后面的数组根据自己是否可以压缩而决定要占用多少子节。
这种策略不一定有压缩效果，也是要视数组本身而定，通常当大部分元素都比较小时又较好的压缩效果；
极端情况，数组所有元素皆为0，则[v1 v2 ...]部分为空，每个元素只占2bit。

如果需要传输一张数据表的数据，不妨以“列”的方式来组装数据，这样编解码更快；
对于稀疏的字段（多数情况下为0），或者字段的值比较小，建议采用压缩策略。

四、框架实现

限于篇幅，本篇只大概讲一下关键过程，更多细节大家可看源码了解。

4.1 定义类型

回顾上一章，packable的type占用3个bit, 字节的最高的bit用来表示index写在剩余的4bit还是下一个字节。

+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+
|  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 实现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扩容由调用者实现。
因为有时候需要连续写入多个值，调用处统一判断扩容，比每次调用Buffer接口都做判断划算。

4.3 实现编码

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;
    }
}

编码方法的实现步骤：

1、检查buffer容量，容量不足则扩容
2、写入index
3、写入type
由于index和type所在比特位不同，所以用"|"操作追加即可；
当value为0时，type=0,所以不需要特别写入。
4、写入value
如上举例的是写入int, 根据value的大小写入对应的字节。
比如，假如value < 256, 在只需写入一个字节。
编码其他基础类型大体步骤如上。

编码对象则相对复杂一些。
需要序列化的对象实现Packable的encode方法，用PackEncoder写入对象的字段。
如果对象的字段中又有对象，那个对象也实现Packable即可（编码时会递归调用）。

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

具体编码对象过程如下：

    public PackEncoder putPackable(int index, Packable value) {
        if (value == null) {
            return this;
        }
        checkCapacity(6);
        int pTag = buffer.position;
        putIndex(index);
        // 预留 4 字节，用来存放length
        buffer.position += 4;
        int pValue = buffer.position;
        value.encode(this);
        if (pValue == buffer.position) {
            buffer.position -= 4; // value为空对象，回收预留空间
        } 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);
        }
    }

和编码基础类型的步骤类似，只是写入type要后置，因为写入策略是先编码value，结束之后写入value的长度，以及type。
为了避免过多的字节移动，仅当value长度小于127时做compact操作（移动字节，压缩空间）。
那TYPE_VAR_16岂不是用不上了？
编码数组或字符串的时能用上，因为写入buffer前就知道需要占用多少字节，不需要像写入对象一样先预留length的空间。

大部分框架在实现编码时需要先填充值到容器中，然后再执行编码时遍历容器，编码各节点到buffer中。
像protobuf的java实现，写入一个对象，需要先遍历每个字段，计算需要占用多少空间，然后写入length, 然后再写入value。如此，对象的每一个字段都要访问两遍。
而packable的写入策略则是调用put方法时即刻写入，这样只需要访问一次各个字段；
虽然编码一些小对象时需要compact操作，但由于需要移动的字节数不多，而且考虑到空间局部性，总体效率还是可以的。
最重要的是，这样的策略编码实现简单！
计算每个字段占用空间，需要多出很多代码，执行效率也大打折扣。

4.4 实现解码

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的处理相对复杂一些，此处省略 ...
                }
            } 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;
            }
        }
        // 函数结束时，infoArray记录了各index对应的值、或者位置、长度等信息
        // 没有赋值的且下标小于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、根据 type 读取对应的值
读取的值会缓存到infoArray[index]，
其中，如果是基本类型，可以直接将value填入infoArray中，高位补0；
如果是可变长类型，则将offset额length拼凑成long, 再填入infoArray中。
4、调用get方法时读取值
读取基本类型时，直接读取infoArray[index]；
读取可变长类型时，拆解offset和len, 定位到对应位置，读取指定长度的value。

调用getPackable时，如果Packable对象有类型嵌套，会递归调用decode方法，这和编码时的递归是类似的。

五、用法

5.1 常规用法

序列化/反序列化对象时，实现如上接口，然后调用编码/解码方法即可。
用例如下：

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、实现encode()方法，编码各个字段（PackEncoder提供了各种类型的API）；
3、调用PackEncoder.marshal()方法，传入对象，得到字节数组。
反序列化
1、创建一个静态对象，该对象为PackCreator的实例；
2、实现decode()方法，解码各个字段，赋值给对象；
3、调用PackDecoder.unmarshal(), 传入字节数组以及PackCreator实例，得到对象。

如果需要反序列化一个对象数组, 需要创建PackArrayCreator的实例（Java版本如此，其他版本不需要）。
PackArrayCreator继承于PackCreator，多了一个newArray方法，简单地创建对应类型对象数组返回即可。

5.2 直接编码

上面的举例只是范例之一，具体使用过程中，可以灵活运用。
1、PackCreator不一定要在需要反序列化的类中创建，在其他地方也可以，可任意命名。
2、如果只需要序列化（发送方），则只实现Packable即可，不需要实现PackCreator，反之亦然。
3、如果没有类定义，或者不方便改写类，也可以直接编码/解码。

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 自定义编码

比方说下面这样一个类：

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

Rectangle是JDK的一个类），有四个字段：

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

当然，有很多方案去实现（让Rectangle实现Packable不在其中，因为不能修改JDK）。
packable提供的一种高效（执行效率）的方法：

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个int, 占16字节
        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;
    };
}

通常情况下，大对象嵌套一些固定字段的小对象还是挺常见的。
用此方法，可以减少递归层次，以及减少index的解析，能提升不少效率，

5.4 类型支持

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

基础类型中的putSInt、putSLong和putCDouble是带压缩编码（参考3.3节）。
Map的key-value类型组合太多了，所以只实现了部分常用类型，然后留了一个putMap接口提供自定义实现。

六、性能测试

除了protobuf之外，还选择了gson (json协议的序列化框架之一，java平台）来做下比较。

空间方面，序列化后数据大小：

	数据大小(byte)
packable	2537191 (57%)
protobuf	2614001 (59%)
gson	4407901 (100%)

packable和protobuf大小相近（packable略小），约为gson的57%。

耗时方面，分别在PC和手机上测试了两组数据：

Macbook Pro

	序列化耗时 (ms)	反序列化耗时(ms)
packable	9	8
protobuf	19	11
gson	67	46

荣耀20S

	序列化耗时 (ms)	反序列化耗时(ms)
packable	32	21
protobuf	81	38
gson	190	128

需要说明的是，数据特征，测试平台等因素都会影响结果，以上测试结果仅供参考。
大家可自行用自己的业务数据对比一下。

七、总结

通常而言packable和protobuf性能方面比json的要好，但可读性方面是硬伤。
一种改善可读性的方案：将二进制内容反序列化成Java对象，再用Gson等框架转化为json。

总体而言，packable有以下优点：

1、性能优异
编码解码速度快；
编码后的消息提交小。
2、代码轻量
一方面是包体积，以Java为例，protobuf的jar包接近2M，而packable的jar包只有37K；
另一方面是新增消息类型所需要的代码量，例如前面一节所定义的数据类型，protobuf编译出来的java文件有五千多行，而packable所定义的类文件只有百来行。
3、使用方便
使用protobuf的过程相对繁琐，需要编写.proto文件、编译成对应语言平台的代码、拷贝到项目中、项目集成SDK……
如果需要新增字段，需要修改.proto文件，重新编辑，再次拷贝到项目中。
相对而言，packable可以在现有的对象改造，对于已经定义好的类，实现相关接口即可，相关的实现和调用都不需要变更，
如果需要增删字段，也只需直接在代码中增删字段即可。
4、方法灵活
可以单实现序列化的接口（或者反序列化接口）；
除了对象序列化/反序列化，也支持直接编码，自定义编码等。
5、支持各种类型，可变对象支持null类型（protobuf不支持）。
6、支持多种压缩策略