一种简单高效的二进制编码方法

18 Mar 2014

JSON 是一种非常常见的编码方法，数据编码之后，可进行持久存储或者网络传输。和 xml 类似，JSON 也是自描述的，编码后的数据具有一定的可读性并且相对 xml 数据更小。

但在 RPC 调用的数据传输时，使用 JSON 编解码速度慢，数据量也太大。

本文介绍一种二进制编码方法，具有编码解码速度快，编码后数据量小的特点，同时类似 JSON，编码后的数据也是自描述的。

支持的常用数据类型

Null。空类型。
Bool。布尔值，true或者false。
Integer。根据长度不同，支持：8 ~ 64 位。
Blob，二进制流。
String。字符串。C 风格字符串不包含最后一个字符。
Float，浮点数。
- Single，单精度浮点数，32位，4字节。
- Double，双精度浮点数，64为，8字节。
List，数组。值可以是支持的任意类型，包括 List 本身。
Dictionary，key-value 键值对。值可以是支持的任意类型，包括 Dictionary 本身

编码方法

Null

编码成一个特殊字节

+-----------+
| 0000 1111 |   0x0f
+-----------+

Bool

true 和 false 分别被编码成一个特殊的字节。

true

+-----------+
| 0000 0100 |   0x04
+-----------+

false

+-----------+
| 0000 0101 |   0x05
+-----------+

Integer

整数会被编码成一个或者多个字节。

整数的类型信息和符号信息被编码到最后一个字节

最后一个字节前三个位用来存储整数区别于其他数据类型的标志以及符号位，第 4，5 个位用来存储整数的长度信息
- 非负整数的前三位
```
+-----------+
| 010x xxxx |  0x40
+-----------+
```
- 负整数的前三位
```
+-----------+
| 011x xxxx |  0x60
+-----------+
```
- 整数的长度信息被编码进第 4，5 位:
```
+-----------+
| xxx0 0xxx |   64bits
+-----------+
+-----------+
| xxx0 1xxx |   8bits
+-----------+
+-----------+
| xxx1 0xxx |   16bits
+-----------+
+-----------+
| xxx1 1xxx |   32bits
+-----------+
```
除去最后一个字节，其他字节（如果编码后的数据是多个字节的话）的首位都是 1，最后一个字节存储整数数据类型信息，该字节首位是 0。这样设计，会给解码带来便利。

最后一个字节的 3 个位，以及其他字节的 7 个位，用来储存整数的数值信息，如图：
```
    7 bits                  3 bits
+-----------+...........+-----------+
| 1xxx xxxx | 1xxx xxxx | .... .xxx |
+-----------+...........+-----------+
```
整数的绝对值数值的二进制补码(Two's Complement)，低位在前，高位在后，7 位一组，填充到这些编码位上。
```
// allocate buf
char *p = buf;
// 小于0x08的数值，编码到最后一个字节的后三位
while (num >= 0x08)
{
    *p++ = 0x80 | num;
    num >>= 7;
}
*p++ = type | num;
```
1 编码后：
```
+-----------+
| 0100 0001 |
+-----------+
```
-16 编码后：
```
+-----------+-----------+
| 1001 0000 | 0110 0000 |  
+-----------+-----------+
```

Blob

二进制流编码后的数据分成两部分，前一部分是原始数据的长度（字节数），后部分是二进制流原始数据。如下：
```
+----------------+
| length + data  |  
+----------------+
```

原始数据的长度的编码和整数相似，但有两个地方不一样：

编码到最后一个字节的 Blob 的数据类型信息是 0x10;

最后一个字节有 4 个位可用来存储编码后的长度信息，对于整数，只有 3 个:

              0x10 + 4bits
+...........+-----------+
| 1xxx xxxx | 0001 xxxx |
+...........+-----------+

编码后：

                                     binary data
+-----------+...........+-----------+============+
| 1xxx xxxx | 1xxx xxxx | 0001 xxxx |    data    |
+-----------+...........+-----------+============+

String

字符串数据的编码方式和 Blob 一样，也是先编码长度，然后编码数据。

字符串数据以及长度不包括 C 风格字符串中的结束字节。

编码到长度数据最后一个字节的 String 的数据类型信息是: 0x20，如下:

              0x20 + 4 bits
+...........+-----------+
| 1xxx xxxx | 0010 xxxx |
+...........+-----------+

+-----------+...........+-----------+============+
| 1xxx xxxx | 1xxx xxxx | 0010 xxxx |    data    |
+-----------+...........+-----------+============+

Float

浮点数类型支持单精度和双精度。编码时，先编码这两种数据类型的类型信息到一个字节。然后再编码浮点数 IEEE-754 标准表示的 32 位或 64 位数据。
编码时高位在前。

编码后，单精度浮点数占 5 个字节；双精度浮点数占 9 个字节，如下所示：

  0x06        8 bytes
+-----------+===========+
| 0000 0110 |    data   |  双精度
+-----------+===========+

  0x07        4 bytes
+-----------+===========+
| 0000 0111 |    data   |  单精度
+-----------+===========+

List

为了编码 List 和 Dictionary 数据类型，定义了一个特殊的字节，用来做闭合标志，如下：
```
+-----------+
| 0000 0001 |   0x01
+-----------+
```

List 的数据类型信息编码成一个字节：

+-----------+
| 0000 0010 |   0x02
+-----------+

在编码时，第一个字节是类型信息，然后是每个子元素，最后是闭合字节：

+-----------+
| 0000 0010 | List 类型信息字节
+-----------+----------------------------
|          元素 1                       
+----------------------------------------
|          元素 2                       
+----------------------------------------
.    .    .
.    .    .
.    .    .
+----------------------------------------
|          元素 N                       
+-----------+----------------------------
| 0000 0001 | 闭合字节
+-----------+

Dictionary

和 List 编码类似，Dictionary 编码时先编码类型信息，Dictionary 类型信息是：
```
+-----------+
| 0000 0011 |   0x03
+-----------+
```

类型信息之后，是 Dictionary 的每个键值对，最后是闭合字节：

+-----------+
| 0000 0011 | 类型信息
+-----------+----------------------------
|            key 1   
+----------------------------------------
|          value 1
+----------------------------------------
|            key 2   
+----------------------------------------
|          value 2
+----------------------------------------
.    .    .
.    .    .
.    .    .
+----------------------------------------
|            key N   
+----------------------------------------
|          value N
+-----------+----------------------------
| 0000 0001 | 闭合字节
+-----------+

一些常量值定义

类型信息：

typedef enum {
    BIN_TYPE_CLOSURE                = 0x01, 
    BIN_TYPE_LIST                   = 0x02,
    BIN_TYPE_DICT                   = 0x03,
    BIN_TYPE_BOOL                   = 0x04,     /* 0000 0100 T */
    BIN_TYPE_BOOL_FALSE             = 0x05,     /* 0000 0101 F */

    BIN_TYPE_FLOAT_DOUBLE           = 0x06,     /* 0010 0110   */
    BIN_TYPE_FLOAT_SINGLE           = 0x07,     /* 0000 0111   */

    BIN_TYPE_NULL                   = 0x0f,

    BIN_TYPE_BLOB                   = 0x10,     /* 0001 xxxx   */
    BIN_TYPE_STRING                 = 0x20,     /* 0010 xxxx   */

    BIN_TYPE_INTEGER                = 0x40,     /* 010x xxxx + */
    BIN_TYPE_INTEGER_NEGATIVE       = 0x60,     /* 011x xxxx - */
} bin_type_t;

整数子类型：

#define BIN_INTEGER_TYPE_64                 0x00 << 3   // default implementation
#define BIN_INTEGER_TYPE_8                  0x01 << 3
#define BIN_INTEGER_TYPE_16                 0x02 << 3
#define BIN_INTEGER_TYPE_32                 0x03 << 3

#define BIN_INTEGER_SUBTYPE_MASK            0x03 << 3

实现

php 实现: https://github.com/binpack/binpack-php
Java 实现: https://github.com/binpack/binpack-java
其他语言，TODO

性能

在 php 实现中，对比 msgpack，编码后两者数据量大小相等，但本编码方法所耗时间是前者是前者 3/4。

https://github.com/binpack/binpack

Follow Me on GitHub