CppGuide

2024-01-10

关注我，更多的优质内容第一时间阅读

在实际设计协议时，整型数值（如 int32、int64）在协议字段中出现频率非常高，以上面介绍的 TLV 格式为例，L 代表每个字段的长度，假设用一个 int32 类型表示，int32 占 4 个字节，对于无符号的 int32 类型来说，其可表示的范围为 0 ~ 4294967295，实际用途中，我们不会用到太长的字段值，因此可以根据字段实际的 length 值使用 1 ~ n 个字节表示这个 int32 值。

在实际处理中，一个字节（Byte）的共有 8 位（bit），该字节的最高位我们用来作为标志位，用于说明一个整型数值是否到此字节结束，如果某个字节的最高位为 0 表示该整型值的内容到此字节结束，最高位为 1 表示表示下一个字节仍然是该整型值的内容。说的有点抽象，我们来看一个具体的例子。假设在一串字节流中，存在如下二进制数字表示某个整型值：

第1个字节  第2个字节 第3个字节  第4个字节
10111011 11110000 01110000 11110111 ...其他省略...

如上图所示，第一个字节是 10111011 ，其最高位为 1，说明其下一个字节仍然属于表示该整型的序列，下一个字节是第二个字节 11110000，其最高位仍然是 1，再看第三个字节的内容 01110000，第三个字节的最高位是 0，因此表示这个整数的字节序列到此就结束了。假定我们压缩时的顺序是低位内容字节在内存地址较小的位置，高位内容在内存地址较大的位置，则将每个字节的标志位（最高位）去掉后，其值是：

第3个字节  第2个字节 第1个字节 
1110000  1110000  0111011   => 11100 00111000 00111011

11100 00111000 00111011 转换成十进制为 1849403。

使用上述技巧进行压缩的整型，由于一个字节只使用低 7 位（最高位为标志位，一般称为“字节前导位”），一个 int32 的整型共 4 个字节（4 * 8 = 32）位，因此一个 int32 使用上述方法进行压缩其长度可能是 1 ~ 5 个字节。实际协议中，我们基本上很少遇到使用超过 3 个字节以上长度，因此这种压缩还是比较实用的（节省空间）。

有了上面的分析，对于一个无符号 int32 的整型的压缩算法如下，以下代码节选自 POCO C++ 库，代码格式略有调整：

01 //poco-master\Foundation\src\BinaryWriter.cpp
02 //将一个 uint32 压缩成 1 ~ 5 个字节的算法
03 void BinaryWriter::write7BitEncoded(UInt32 value)
04 {
05   do
06  {
07   unsigned char c = (unsigned char) (value & 0x7F);
08   value >>= 7;
09   if (value) 
10    c |= 0x80;
11   
12   _ostr.write((const char*) &c, 1);
13  }
14  while (value);
15 }

上述代码对一个 uint32_t 整型 value 从低到高每次取 7 bit，判断下 value 的值在去掉 7 bit 后是否有剩余（非 0 则说明有剩余，代码第 8 和 9 行），如果则将当前字节最高 bit （标志位）设置为 1，这样得到一个字节的值后，放入字节流容器 _ostr 中，字节流容器的类型只要具有连续的内存存储序列即可，如 std::string。

我们假设现在 value 的值是十进制 125678‬，其二进制是 1 1110 1010 1110 1110，我们来看一下上述函数执行过程：

第一次循环

十六进制 0x7F 的二进制为 0111 1111，执行

unsigned char c = (unsigned char) (value & 0x7F);

后， c = 110（十进制），二进制是 0110 1110，接着将 value 右移 7 bit，看看还有没有剩余（与 0 判断），此时 value 变为 981（十进制），对应二进制 11 1101 0101 ，代码第 9 行 if 条件为真，说明一个字节表示不了这个数值，给算出的字节 c 最高位 bit 设置标志值 1（与 0x80 做或运算，0x80 的二进制是 1000 0000，代码第 **10 ** 行），得到第一个字节值 238（十进制），对应二进制 1110 1110。

第二次循环

c 开始等于 85（十进制），执行代码第 7、8 行后，发现 value 的值仍有剩余，再次在该字节的高位设置标志 1，得到第二个字节值 213（十进制）。

第三次循环

c 开始等于 7，执行代码第 7、8 行后，发现 value 的值已经没有剩余，得到第三个字节值 7，然后退出循环。

程序执行过程如下图所示：

在理解了整型的压缩算法，其对应的解压算法也很容易弄明白了，代码如下，同样节选自 POCO C++ 库，代码格式略有调整：

//poco-master\Foundation\src\BinaryReader.cpp
//将一个字节流中 1 ~ 5 个字节的还原成一个 uint32 整型
void BinaryReader::read7BitEncoded(UInt32& value)
{
 char c;
 value = 0;
 int s = 0;
 do
 {
  c = 0;
  _istr.read(&c, 1);
  UInt32 x = (c & 0x7F);
  x <<= s;
  value += x;
  s += 7;
 }
 while (c & 0x80);
}