二进制打包很有趣

# 二进制打包其实很有趣 原文来源：https://hereticpleb.vercel.app/blog/packing-binary-is-fun-actually ## 为什么有人要做这个？ 我在推特上看到有人争论说，用 JSON 存数据显然不是“真正的”开发者该做的。显然，我也必须成为一名“真正的”开发者。结果发现，答案是用二进制。自然，我有了一个绝妙的主意： > “自己制作二进制格式能有多难？” 肯定就只是写个小 `wb` 嘛。( ˶ˆᗜˆ˵ ) 可惜，事实并非只是写个 `wb`。我最终构建了一整个二进制模式语言，可以将 JSON 数据包体积缩小 80%。 jBin (https://github.com/PranavDesai-Git/jbin) ## 什么是二进制打包？ 假设我们有一些数据： ``` "hello world" ``` 它在 ASCII 编码下会转化为： ``` 104 101 108 108 111 32 119 111 114 108 100 h e l l o [空格] w o r l d ``` 所以 `h` 在 ASCII 中是 104。由于这些 ASCII 值都适合 8 位，每个字符占 1 个字节。 ``` h e l o [空格] w o r l d 01101000 01100101 01101100 01101111 00100000 01110111 01101111 01110010 01101100 01100100 ``` 所以我们可以用一小段 C 代码把它写出来： ```c FILE *f = fopen("file.bin", "wb"); unsigned char data[] = "hello world"; fwrite(data, 1, sizeof(data) - 1, f); fclose(f); ``` 很简单。现在来试试写 104。显然，我们也可以直接把 104 当作 ASCII 字符来写： ``` '1' '0' '4' → 49 48 52 ``` 但一个只需要 1 字节的数字却花了 3 字节。所以如果我们想节省这 2 字节，就需要一种方式告诉解码器：“嘿，这是一个整数，不是字符串。”你可以添加一个头部，这样就只多了一个字节（好吧，这取决于你有多少种类型...希望你不要有超过 128 种类型...如果真有，那你有更大的问题了）。很好！我们就用第一个字节表示类型，第二个字节表示数据。 ``` [类型][数据] ``` 假设 0 是整数，1 是字符串，那么 104 就是： ``` 00000000 01101000 ``` 而字符串会是... ``` 00000001 01101000 ``` 哦，等等...这只会得到 `h`，我们需要一种方式来表示不同长度的数据。好吧，那就再加一个字节。这个字节表示字符串的长度。所以现在我们的二进制格式变成： ``` [类型][长度][数据] ``` 太好了！现在我们可以这样表示字符串了： ``` [类型] [长度] [数据] (字符串) (1) (11) 00... h e l 01101000 01100101 01101100 l o [空格] 01101100 01101111 00100000 w o r 01110111 01101111 01110010 l d 01101100 01100100 ``` 太棒了！现在我们可以把字符串和整数打包在一起了！比如我们要表示 `"userid": 123`，现在你可以这样打包： ``` [类型:字符串][长度:6][单词:userid][类型:整数][长度:-][数据:123] ``` 很好！我们可以用 2 字节的头部将 123 表示为 1 字节的数字。但注意，我们真的没为整数使用长度字段？那为什么还需要它呢？浪费字节不是吗？嗯...如果我们去掉它，二进制读取器怎么知道头部结束了？它需要某种方式表示“好的，头部结束了，现在开始读取实际数据。”那么，用什么来表示一个字节结束了呢？也许用一个表示头部长度的字节？这有点多余。我们去掉长度字段只是为了添加另一个长度字段。但是，我们可以用头部本身的一个比特位。我们可以用一个比特位表示： > 我不是头部的最后一个字节。后面还有更多。 你可能会想：为什么不用最低有效位（LSB）？那样我们就只能表示偶数了。这...不太理想。所以我们会用最高有效位（MSB）。所以现在我们的标签看起来像这样： ``` [继续位][7位数据] ``` 如果继续位是 1，表示后面还有一个头部字节。如果是 0，表示头部结束。使用这种方式，我们可以将 123 表示为： ``` [类型=0][数据=123] ``` 如果是字符串，则是： ``` [类型=1][长度=11][数据=104]... ``` 类型是 1，长度是 11。但等等...如果长度大于 127 怎么办？只有 7 位最多只能表示到 127！ > 我们用同样的方式处理整数！如果最高位是 1，表示整数继续。128 可以写成： ``` 10000001 00000000 ^ MSB / 继续位 ``` （大端序） 二进制读取器会这样处理： - 读取第一个字节。 - MSB 是 1，所以后面还有字节。 - 剩余的 7 位是 1。 - 读取第二个字节。 - 它的 MSB 是 0，所以这是最后一个字节。 - 它剩余的 7 位是 0。 - 将两个 7 位的值组合起来得到 128。 这是一种变长整数（varint）。我们这里使用的编码是小端序：最不重要的 7 位在前。 ``` 10000000 00000001 ``` 嘿，这不是很棒吗？你可以在同一个二进制中表示不同类型的数据，而你的二进制解析器都能正确读取它们。 但注意，我们是为每个字段存储这些数据。 ``` [类型][数据] [类型][数据] [类型][数据] ``` 而且大多数数据并不是一堆随机的值。它通常是有结构的。以一个 C 结构体为例： ```c struct { int i; char *s; int a[10]; } ``` 假设在 32 位系统上，这将是： ``` [32位整数] [32位指针] [10 × 32位整数] ``` 我们不需要每次都添加头部，因为我们从结构体本身就知道数据的类型。 嗯，我在想我们能否为我们的二进制数据也这样做...答案是肯定的。这就是模式（schema）的作用！所以对于我们的结构体，模式可以写成： ``` i: 整数 s: 字符串 a: 列表(整数) ``` 模式让我们无需在每个值旁边存储类型。现在我们的二进制格式不需要担心类型！它只需要担心数据的大小！ > 这就是 protobuf 的做法。 那么让我们想想我们可以有的所有不同大小的数据。我们有整数、浮点数、布尔值、字符串。我们可以将整数和布尔值视为变长整数（varint），而浮点数是固定宽度：f32 或 f64。字符串不同。我们不能直接将它们的字节编码为 varint，因为字节本身是我们需要保留的实际数据。所以相反，我们需要在开始读取之前知道字符串有多少个字节。所以现在我们的编码类型有： - varint - f32 - f64 - 定界符（delimited） 但是！我们如何访问字段？比如我们不能只说“给我字符串”，我们需要指定是哪一个。没问题，我们就用数字表示每个字段。我们可以索引它们，或者让用户自己分配数字来寻址。这就是我们需要字段编号的原因。 还要注意另一件事：我们只有四种可能的类型。四个值恰好可以放入 2 位。 ``` 00 - varint 01 - f32 10 - f64 11 - 定界符 ``` 嘿，这不是很整洁吗？现在我们可以把它编码...*在我们的字段编号里！* > 等等，怎么做到？ 一些二进制技巧...不完全是。你只需把它们挤在一起。将字段编号左移 2 位为我们的 2 位类型腾出空间，然后将类型按位或（OR）到这些空位上。假设你的字段编号是 10，并且是定界符类型。 ``` 00001010 (10) 左移 2 位 00101000 与我们的类型进行或运算！ 00101011 ``` 看啊！我们这 1 个字节的数字告诉了我们它的类型和字段编号！ 但如果我们进一步呢？我们已经把类型打包进了字段编号。为什么到此为止？如果我们还能把长度也打包进去呢？我们可以。现在我们的头部可以包含： ``` [字段编号][长度][类型] ``` 全部都在一个 varint 里！！！(ᴖᗜᴖ) 很酷。除了一件事，就是太繁琐了。要打包一个字符串，我必须告诉它“这是定界符”，给出长度，然后给出字节。每一次。每一次都这样。只有农民才这么干。平民。我们不干。所以显然，解决方案是编写一整个模式语言。我们在模式文件中声明数据，让程序处理所有那些繁琐的格式化和编码工作。 --- ## 构建模式语法 好吧，那么...我们需要决定一种不会吸干你灵魂的语法（说你呢，protobuf）。字段编号...那是什么？就是索引对吧。你在购物清单上如何索引东西？你写数字. 物品。为什么不直接用这个！所以就像这样： ``` 1. name ``` 我们需要模式表示类型。我们就借鉴其他语言的做法，像这样： ``` 1. name: 类型 ``` 很整洁，对吧？但等等。我们如何表示消息（结构体）的结束呢？好吧，我们可以用 `{}`，但这样不太好。为什么要过度复杂化事情呢？它是一个列表。列表有结尾。我们就给它一个结尾。 ``` 消息 名称: 1. 名称:类型 2. 名称:类型 3. 名称:类型 结束 ``` 不，缩进不应该重要。使用缩进重要的语言太烦人了。只是痛苦。我们就别那样了。那么，如果没有分号，你如何识别行尾呢？换行符？我的意思是，我们可以这样做，但如果他们想在一行内输入呢，这很丑，但假设他们想这么做。我们不要限制这个。但分号很丑。我们可以用数字！如果我们看到一个数字和一个点，我们就认为它是一个新条目！很整洁，对吧？( ᴖᗜᴖ ) 问题...如果编译器读取时找不到某个字段呢？我们可能会崩溃...对于所有字段我们都会崩溃，但我们确实想要可选字段对吧？我们就走明显的路，像这样： ``` 数字. 名称: 类型 = 默认值 ``` 这表示可选。非常直观。 既然我们在这里，让我们想想人们可能表示的所有不同数据类型...我们显然有类型的条目。哦，我们需要列表。我们需要某种方式在多个东西中选择，所以我们需要一个枚举。很好，让我们想想那些...哦，我们可以让它们像函数一样，非常直观。 ``` 数字. 名称: 结构(类型) ``` 像： ``` 1. friends: 列表(People) ``` 哦，等等，People 是什么？哦，它也应该是一个消息。像这样： ``` 消息 People: 1. name: string 2. location: string 结束 ``` 嗯...我们还需要自定义类型...所以在语言中，我们是否希望一切都按顺序排列？那挺尴尬的。以后我们可以做一遍处理，把所有的表组合在一起，并让它引用那个结构体。嘿，多亏了这个，我们还可以有自引用。因为当我们打包时，它就只是一个指向该结构体的指针！所以我们可以这样做： ``` 消息 People: 1. name: 字符串 2. location: 字符串 3. friends: 列表(People) 结束 ``` 现在来说枚举。因为我们有两遍处理，我们可以把枚举放在消息外面！它在哪里声明也不重要！我们可以这样声明枚举： ``` 枚举 名称: 数字. 名称 数字. 名称 数字. 名称 结束 ``` 还有 protobuf 做了一件事，强制枚举从 0 开始，像那样。我们真的需要吗？编译器这么笨，它无法识别吗？我们就让编译器默认处理吧。哦，等等...人们可能需要一种方式来表示枚举，但所有类型都不一样。是的，那是联合体（union）。我们就加上这个，没问题。 ``` 数字. 名称: 联合(类型, 类型, 类型...) ``` 哦，等等...我们的默认值。这对联合体怎么起作用？如果我们有这样一个联合： ``` 数字. 名称: 联合(i32, i64) = 10 ``` 无法确定 10 是 i32 还是 i64。所以当字段未找到时，我们该怎么办？我们可以通过让默认值紧邻类型来解决这个问题。 ``` 数字. 名称: 联合(i32 = 10, i64) ``` 现在如果字段未找到，它将是值为 10 的 i32。好吧，人们还想映射东西...所以我们添加： ``` 数字. 名称: 映射(键类型, 值类型) ``` 让我们添加声明包和导入的语法： ``` 包 "包名" ``` ``` 导入 "包" ``` 嘿，你瞧，我们有了一些非常整洁的语法。让我们把它们组合起来： ``` 包 "com.game.core" 导入 "math.jbin" 枚举 活动: 1. active 2. inactive 结束 消息 玩家: 1. name: 字符串 2. health: i32 = 100 3. weapons: 列表(字符串) 4. connections: 列表(玩家) 5. activeStatus: 活动 6. inventory: 映射(字符串, i32) 7. balance: 联合(字符串="empty", i32) 结束 ``` 哦，等等...我们现在有一门完整的语言了...不管怎样。这是它在 .proto 中的等效写法： ```protobuf syntax = "proto2"; package com.game.core; import "math.proto"; enum Activity { ACTIVE = 1; INACTIVE = 2; } message Player { optional string name = 1; optional int32 health = 2 [default = 100]; repeated string weapons = 3; repeated Player connections = 4; optional Activity active_status = 5; map inventory = 6; oneof balance { string empty = 7; int32 amount = 8; } } ``` 看那个。呃。 --- ## 现在来实际实现它 要实现这个，我自然选择了 C++。“自然”是说，我想找一个可以写在简历上，并且不想跟 Rust 借用检查器较劲的语言。我已经够老了。好啦。设计得够多了。是时候让这东西真正运行起来了。首先，我们需要编码我们的二进制。 ### 编码和解码数据 要编码一个变长整数（varint），基本上就是这样： ```cpp void encodeVariant(std::vector<uint8_t> &buffer, uint64_t value) { while (value >= 128) { uint8_t lower = value & 127; // 127 = 01111111 lower |= 128; buffer.push_back(lower); value >>= 7; } uint8_t lower = value & 127; buffer.push_back(lower); } ``` 这构建了我们的 varint。如果值 >= 128，我们取最低的 7 位，将 MSB 设为 1 表示“还有更多”，并将其附加到缓冲区。然后我们将值右移 7 位并重复。对于最后一个字节，我们将 MSB 保持为 0。非常简单。我们可以用以下代码解码它： ```cpp uint64_t decodeVariant(const std::vector<uint8_t> &buffer, size_t &offset) { uint64_t result = 0; int shift = 0; while ((buffer[offset] & 128) != 0 && offset < buffer.size()) { uint8_t byte = buffer[offset++]; byte &= 127; const uint64_t cast = static_cast<uint64_t>(byte) << shift; result |= cast; shift += 7; } uint8_t byte = buffer[offset++] & 127; const uint64_t cast = static_cast<uint64_t>(byte) << shift; result |= cast; return result; } ``` 现在我们能够使用 LEB128 编码和解码 varint 了，让我们来编码和解码一些标签（我们讨论过的头部元数据）： ```cpp void encodeTag(std::vector<uint8_t> &buffer, uint32_t fieldNumber, wiretype wiretype) { uint64_t val = (static_cast<uint64_t>(fieldNumber) << 2); val |= static_cast<uint64_t>(wiretype); encodeVariant(buffer, val); } void decodeTag(const std::vector<uint8_t> &buffer, size_t &offset, uint32_t &outFieldNumber, wiretype &outType) { uint64_t val = decodeVariant(buffer, offset); outType = static_cast<wiretype>(val & 3); outFieldNumber = val >> 2; } ``` 我们还可以为字符串添加一些辅助函数： ```cpp void encodeString(std::vector<uint8_t> &buffer, uint32_t fieldNumber, const std::string &text) { encodeTag(buffer, fieldNumber, wiretype::Delimited); encodeVariant(buffer, text.size()); buffer.insert(buffer.end(), text.begin(), text.end()); } std::string decodeString(const std::vector<uint8_t> &buffer, size_t &offset) { uint64_t size = decodeVariant(buffer, offset); std::string result = std::string(buffer.begin() + offset, buffer.begin() + offset + size); offset += size; return result; } ``` 编码一个字符串现在就只是三件事：写它的标签，写它的长度，然后写它的字节。信不信由你，这基本上就是我们的核心引擎完成了！剩下的只是编译器和 JSON 转换部分了！٩(^ᗜ^ )و ́- 好极了！现在我们已经写好了二进制编码...让我们来写个编译器吧。应该很简单...对吧？ ### 构建编译器 是的，它是一个编译器。别说了，我不想叫它转换器（transpiler），它就是编译器。定义是： > 编译器是将一种编程语言（源语言）编写的源代码转换为另一种编程语言（目标语言）的计算机程序，同时保留原始代码的确切含义和行为。 我们的程序做到了。走开，编译器警察们。我的程序接受我的模式，并将其转换为二进制或代码。 #### 问题 我们的语言很可爱。很精巧。不幸的是，计算机完全不知道它是什么意思。它只是字节。所以让我们给这些符号赋予意义吧！让我们看看我们的语法： ``` 1. name:string ``` 所以它的结构是： ``` 数字 → 点 → 标识符 → 冒号 → 类型 ``` 然后我们可以用它来构建这些条目的表示。这就是词法分析器（Lexer）所做的。