bitproto 最近的开发笔记

最近对 bitproto 做了两项改进：

支持任意比特位数的有符号整数的编解码 ¶
提升 C 语言常规模式的编解码性能 ¶

本文是对这两项的开发笔记，以便日后回忆。

任意 int{n} 的支持 ¶

原本 bitproto 只支持整数个字节大小的有符号类型，也就是只支持 int8, int16, int32 和 int64, 我和嵌软同学们的开发经历中，也很少会用到负数。最近一位外国朋友发邮件过来，说 WNK8010 传感器返回的压力和温度数值都是 24bit 大小的。希望 bitproto 可以支持任意比特大小的有符号整数, 就是说，需要支持形如以下的 bitproto 定义:

message X {
    int24 data = 1;
}

我们知道，有符号整数的最高位是符号位，对于一个整数，要想在编码后成功在解码端读出正确数值，那么必须在拷贝比特时带上符号位，简而言之，必须在编解码时照顾到符号位。

此前，int8/16/32/64 之所以可以 work，在于 bitproto 恰好把符号位照顾到了。

比如下面这个 bitproto 定义：

message X {
    int32 data = 1;
}

假如 data 的数值是 -11，其二进制表示为（高位在左侧，8 位一组）：

11111111 11111111 11111111 11110101
^
符号位

在编码时，bitproto 会把 data 的 32 个比特全部拷贝到目标 buffer 中。在解码时, bitproto 也恰好把 32 个比特拷贝到了目标变量的内存 buffer 上，所以符号位最终回到了最高位, 以 int32_t 类型去读这块内存，解析结果就是正确的。

// 编码时，符号位被拷贝到 s 了
struct X x = {.data = -11};
unsigned char s[BYTES_LENGTH_X] = {0};
EncodeX(&x, s);

// 解码时，符号位正好被拷贝到字段 `x1.data`
struct X x1 = {0};
DecodeX(&x1, s);
// x1.data 表示为 int32 就恰好是 -11
x1.data  // => -11

也就是说，bitproto 只忠实地拷贝比特，并没有特殊的照顾符号位。int32 可以 work 是因为恰好把符号位也拷贝了。

而对于 24bit 大小的 -11，bitproto 在编解码时却没有照顾到最高位的符号：

编码时，只拷贝了低 24 位：

11111111 11111111 11111111 11110101
^        +------------------------+
符号            低 24 位

解码时，同样是拷贝 24 位，高 8 位则自然留 0, 因此得到 16777205, 而非 -11。

00000000 11111111 11111111 11110101
^        +------------------------+
符号             拷贝的 24 bit

也即，对 int24 这种 “不规整” 的有符号整数，符号位在拷贝时被忽视了，自然解码就会出错。

正如 int8 类型的整数的表达范围是 -128~127 那样，按照默契， int24 类型的整数的表达范围，应该是 -2^23 ~ 2^23-1，也就是 -8388608 ~ 8388607。

那么，应该把第 24 位视作符号位。确切说，高 9 位都是符号标志：　

11111111 11111111 11111111 11110101
         ^
        符号

bitproto 在编码时，本来就会把第 24 位带上拷贝走，那么我们只需要关注解码端逻辑就行。就是说，要关注如何在解码时，把高 9 位全部还原到符号标志。

具体说，拿到错误的 16777205 后，如何修正其高 8 位符号，变为正确的 -11 ?

一个直接的思路是, 借助算术右移的符号位传播 (sign-propagation) 的特点，先左移 8 位，再右移 8 位：

16777205 << 8 >> 8

详细的说明是：

// 最开始的数字 16777205
00000000 11111111 11111111 11110101
         ^

// 左移 8 位后, 符号来到最高位, 数字变为 -2816
11111111 11111111 11110101 00000000
^

// 再右移 8 位，左侧补 1, 数字变为 -11
11111111 11111111 11111111 11110101
         ^

与算术右移相对的是逻辑右移，不同点在于，算术右移时会按最高位符号位补充高位，而逻辑右移会用 0 来填充。这两种右移方式，对于非负数没什么区别，但对于负数，结果则是不同的。

从字面上理解，之所以叫做 “算术” 右移，是因为中间结果 -2816 除以 2^8，也就是除以 8 次 2，就得到 -11 的结果，算术位移会遵循算术含义，右移一位就是除以 2，所以符号也不会变。

这个思路看起来挺简洁的，不过，算术右移 or 逻辑右移是编译器实现决定的，C 标准并没有做要求。所以，不可完全地假设算术右移存在，这个思路的可移植性没有那么强，虽然大部分 C 编译器是算术右移的。

于是，对于 C 语言，我选了另一个 “稍笨” 但是可移植的思路。

值得一提，Go 语言是算术右移的，所以 16777205 << 8 >> 8 的思路在 Go 语言的 bitproto 编解码中得到了应用。

稍微 “安全” 点的思路是非常朴素的，假设 V = 16777205：

查看第 24 位符号标志。
具体来说，安全地右移 23 位, 标志位来到最右端。
此时如果最后一位是 1 就表示是负数，如果是 0 就是非负数。
```
(V >> (24-1)) & 1
```

如果是负数，才需要处理符号问题。

取 ~((1 << 24) - 1) 作为 mask：

// mask 的高 8 位全是 1，低 24 位全是 0
11111111 00000000 00000000 00000000

结果即 V | mask :

// 最开始的数字 16777205
00000000 11111111 11111111 11110101

// 或 上这个 mask
11111111 00000000 00000000 00000000

// 最终得到下面的 -11
11111111 11111111 11111111 11110101

这个思路避免了对负数的右移操作，因此对 C 语言说，是安全的、确保可移植的。

C 语言编解码性能优化 ¶

bitproto 一直有个 “鱼和熊掌，不可兼得” 的无奈现状, 有两种模式存在：

优化模式：不走 lib 形式, 不支持协议扩展，但是性能极高, 编译后体积可能会大
常规模式：走 lib 形式, 支持协议扩展, 但编解码性能不如优化模式, 编译后体积有限

优化模式充分利用了 bitproto 协议固定大小 (Fixed-size) 的特点，在协议编译期预先做了所有编解码的计算，平铺式地生成了编解码的最终代码，所以它很快。不过，正是因为完全假定了所有协议消息是固定大小的，优化模式也不能支持协议的可扩展性。

而我的目的就是希望可扩展性和高性能并存。

两种模式的性能差距还不小。在我的 STM32 板子上，对于 100 字节大小的 bitproto 消息，两种模式的编解码耗时分别在大约 15μs 和 170μs 左右，差距达十倍有余。

虽然常规模式在 Unix 系统中表现的已足够快了，在我的电脑和 Github Action 上的 runner 中， C 语言编解码达到了 <2μs 的耗时, Go 语言编解码达到了 <10μs 的耗时，对于服务器端、PC 端都是足够快了。

但在 STM32 上和优化模式的性能差距还是太大了，因此我花了两天来进一步探索优化的可能。

我其实并不懂嵌入式，只是和他们合作过。之前一位嵌软同学（也是 bitproto 的 “粉丝”）教过我如何搭起来 STM32 的开发环境，我凭着回忆和命令历史，摸索着重新搭了起来。

提到性能优化，我认为，算法思路的优化效果最佳，语言层面的、 trick 优化则次之。

这次的性能优化主要有 2 类：

比特拷贝的性能优化，主要是细节技术优化
基本类型数组的批量比特拷贝（新思路）

下面展开说一下具体优化点：

对 uint16/uint32 批量赋值。大概是这个意思:

// 优化前
uint32_t v32 = (*((uint32_t *)(src))) >> shift;
unsigned char *ptr = (unsigned char *)(&v32);
dst[0] = ptr[0];
dst[1] = ptr[1];
dst[2] = ptr[2];
dst[3] = ptr[3];

// 优化后
((uint32_t *)dst)[0] = ((uint32_t *)(src))[0] >> shift;

避免在每一次循环都计算乘法，转为每次累加，大概是这个意思：

// 优化前
unsigned char *data;

for (int k = 0; k < cap; k++) {
    // 这里每次都要做一次乘法计算
    void *element_ptr = (void *)(data + k * element_size);
    //...
}

// 优化后
element_ptr = data;

for (int k = 0; k < cap; k++) {
    // ...
    element_ptr += element_size;
}

改进核心比特拷贝的思路 7b1559 ：

原来单个字节内拷贝比特的思路是:

// 假设 要拷贝的字节 src 中的 5 个比特到字节 dst 中
// 拷贝的起始位置 si 是 1, 目标位置 di 是 2.

       +---+ 要拷贝的５个比特
src: 10101011
           ^ 起始位置
dst: 00000010
          ^ 目标位置

先构造一个 “奇怪” 的 mask :

 +---+  第2到7位全部赋 1
01111100
     ^ 目标位置　

这个 mask 的意思是，两头儿写 0 的比特位不要，只要 src 字节中间的 5 个比特。

将 src 字节视情况左移 or 右移，本例中是左移１位和目标字节 dst 对齐。

// 左移 src 一位, 和 dst 齐
src: 01010110
          ^ 起始位置
dst: 00000010
          ^ 目标位置

再拿着这个 mask 和位移后的 src 取与操作，即拷贝出了需要的第 2~7 位的比特:

src: 01010110
&  : 01111100
// 结果
dst: 01010100
      +---+ 拷贝出的比特，第 2~7 位

以上是之前的老的思路，其 C 语言描述大概是：

// 优化前
unsigned char BpSmartShift(unsigned char n, int k) {
    return (k > 0) ? (n >> k) : ((k == 0) ? n : (n << (0 - k)));
}

int shift = si - di;
unsigned char mask = (1 << (di + c)) - (1 << di);
dst |= BpSmartShift(src, shift) & mask;

优化后的思路则更简洁直接，同时省去了一些加减法计算，也更快。

大的思路是不变的，先对齐，再拿 mask 拷贝。

对齐不再做所谓的 BpSmartShift，而是对 src 字节先右移再左移。

src: 10101011
           ^ 起始位置
// 右移 1 位，消灭 si 右侧比特
src: 01010101
            ^
// 再左移 2 位，对齐目标字节的位置 di
src: 01010100
          ^
dst: 00000010
          ^ 目标位置

mask 的构造也更简单，取 0xff 左移两次，再取反：

// 0xff
11111111
// 左移 2 + 5 位, 右侧补零
10000000
// 取反
01111111

这个 mask 和之前的 mask 稍有不同，意思是，要清除掉高位不需要的比特，本例中是最高位那个。虽然 src 字节的低 2 位比特我们也不需要，但是它们已经确定是 0 了，不会污染后续的或运算。

最后，拿 mask 和位移后的 src 取与操作，即完成拷贝：

src: 01010100
&  : 01111100
dst: 01010100

这个思路用 C 语言描述起来特别简单：

// 优化后
dst |= ((src >> si << di) & ~(0xff << di << c));

本次中最激动人心的一个优化点：规整的基本类型数组的编解码优化 (367db7)。
所谓 “规整的基本类型的数组”，是指例如 uint8/16/32/64[n], int8/16/32/64[n], byte 这种基本的、且整数个字节大小的类型。
之前 bitproto 编解码的思路是，不断拆解到基本类型的处理，再进入单个字节内的比特拷贝。
对于一个数组而言，编解码过程（其实就是比特拷贝过程）会被拆解到小颗粒度的基本类型一次一次的进行。这个过程是非常碎片化的。
以一个 uint16[5] 类型的数组 V 为例，考虑其编码到 buffer S 的过程：
之前的做法是 “小碎步” 过程，就是按 uint16 的颗粒度不断调用基本编解码方法 BpEndecode，所以要调用 5 次。
而且如果未对齐的话，每一次调用 BpEndecode 方法都会处理对齐问题，产生的小碎片拷贝过程。虽然 BpEndecode 方法内部已经做了批量拷贝比特的优化，但是其局限在 uint16 大小的 buffer 内不得不先解决对齐问题，批量化处理能力也十分有限。
可以看到，如果 V 和 S 没有对齐的话，也就是说目标 buffer S 并不是从最低位开始拷贝比特的话，拷贝过程就会拆成 10 步来完成。
但是，在 C 语言中基本类型的数组的内存是连续的！
我们可以直接大批量地按字节、uint16, uint32 来拷贝！
具体的过程是：
先把目标 buffer S 的不规整的头部处理一下，拷贝一些碎片比特。
接下来，尝试按 uint32, uint16 等四字节、双字节的方式，批量赋值拷贝:
具体来说，就是先用 uint32_t 去读相关的 4 个字节，然后做位移对齐，再进行赋值!
```
((uint32_t *)dst)[0] = ((uint32_t *)(src))[0] >> si;
c = 32 - si; // 追踪本次拷贝的比特数
```
同理，按 uint16 双字节批量拷贝是一样的道理：
最后，处理掉尾部的碎片部分：
可以看到，对于这个例子而言，只需要 4 次拷贝。
这个思路，对规整的基本类型的数组有效，例如 uint32[n]，因为其内存是连续且无缝隙的。对于结构体、布尔值则不行，因为虽然仍然是分布在连续内存上，但是其字段、元素之间有无效数据的缝隙。

上面四次优化下来，STM32 开发板上的编解码性能降低为 140μs 左右，开启 -O3 模式时可以达到 123μs。

我仍然不满意，因为空间还是很大。

（完）