BaseXX 编码

概述

参考：

• RFC 4648, The Base16, Base32, and Base64 Data Encodings
• Wiki, Base64

Base64 是一种 二进制 到 文本 的编码方案，它是基于 64 个可打印的字符来表示二进制的数据的一种方法。Base64 编码实现了让二进制数据可以在只支持文本的通信信道上传输。

Base64 在万维网上特别流行，它的用途包括将图像文件或其他二进制资产嵌入文本资产（例如HTML和CSS文件）中的功能。

Base16

Base32

Base64

痛点：二进制数据无法在纯文本协议（如早期 Email、早期的 HTML、etc.）中安全传输，需要一种只用可打印字符来表示任意二进制数据的编码方式。

最简单的解决方案：使用 Hex（i.e. Base16）。从 字符的编码与解码 中，我们可知：任意二进制数据的 1 Byte 是 8 bit。Base16 使用两个十六进制字符表示每个 Byte。e.g. 10101110 用十六进制表示就是 AE，我们只需要传输文本 AE，就可以直到这个 Byte 记录的是什么。

[!tip] BaseXX 之所以叫编码方案，其实跟 UTF-8 编码、等编码设计的思路是一样的，只不过最终目标不一样

• UTF-8 是将二进制编码为人类可读的有语义文字
• BaseXX 虽然也是将二进制编码为人类认识的文字，但是并无语义。主要是用于方便传输信息

但是，现在有一个新的问题，1 Byte（8 bit） 信息以十六进制表示，就要变为 2 个字符，传输的时候，需要传输 2 Bytes（16 bit）的信息！！直接翻倍！

[!quote] 从 字符的编码与解码 中可知，一个字符占 1 Byte，i.e. 8 bit

但是 Base16 非常简单、高效、直接！所以 二进制编辑器、WireShark 中的 Packet Bytes 窗口、etc. 都是直接默认使用十六进制表示二进制的方式（虽然也可以使用 十进制 或 八进制）

由于 Base16 最大的问题在于膨胀率，那么有没有什么办法，可以使用更少的 bit 来表示字符呢？那就需要一张字符与 bit 的对应表。由于 Base16 本质使用的是 ASCII 编码，这是痛点的来源，那我们是不是可以自己设计一个字符编码规则？

在 ASCII 表 中，可打印的字符有大约 94 个，再去掉在各种协议里有特殊含义的（空格、引号、尖括号、等），还剩大约 64 个左右。这 64 个字符想要完全用二进制表示，刚好最多需要 6 个 1。64 刚好是 $2^6$ ，最大值是 111111！

所以，Base64 设计了自己的字符映射表

[!note] 还有一个 = 作为 Padding(填充) 字符

此时剩下的问题就是，如何让原始 bit 与这个 Base64 的字符映射表对应上。原始信息使用 ASCII，每 8 bit 表示一个符号，要想让 6 bit 与 8 bit 对应上，那就要扩展一些思路，让多个 8 bit 与 多个 6 bit 在某一时刻具有相同的 bit 即可。这就要使用到数学中的 最小公倍数 思想了，i.e. 找到 X 个 8 和 Y 个 6 分别至少需要多少组才能实现 1 对 1 的效果？

答案是: 24 bit

这意味着，只需要每 3 Bytes（i.e. 24 bit）进行一次编码，就可以让这 3 Bytes 的信息在编码后完整保存到 4 个字符中（i.e. 4 Bytes）。并不需要像 Base16 似的，对每个 Bytes 都要编码

还可以这么理解：3 个 ASCII 里的符号，编码后，得到 4 个 Base64 映射表里的字符！

后面使用具体带图的示例，来更加直观得来分析找个问题

我们对 Desist 这 6 Bytes 字符串进行 Base64 编码

一、首先将 Desist 转为二进制数据 01000100 01100101 01110011 01101001 01110011 01110100，一共可以分为 2 组。

二、每组 3 Bytes 分别进行编码，得到的编码结果为: RGVzaXN0。共 8 Bytes

三、RGVzaXN0 在传输和存储时，这 4 个 Base64 映射表里的字符，需要转换为 ASCII 里的二进制表示，i.e. 变为了 $4 * 8 = 32$ bit。

这就是说：24 bit 的原始信息在编码后，膨胀到了 32 bit。膨胀率为: $\frac{32-24}{24} = \frac{1}{3} \approx 33.3\dot{3}%$（Base64 的膨胀率相比 Base16 有了显著的降低）

总结、若有 n Bytes 需要编码，则编码后的总 Bytes 为:

$$\left\lceil \frac{n}{3} \right\rceil \times 4$$

计算逻辑为： n 除以 3（向上取整） 得到 n Bytes 可以分成几组，再乘以 4 之后，得到这些组里一共有多少个 Bytes。

无法刚好整除的问题

现在我们知道了 Base64 编码的基本设计。但是这里面还有一个问题，如果 $\frac{n}{3}$ 除不开怎么办？比如有 2 Bytes(16 bit) 需要编码，前 12 bit 编码后，还剩 4 bit 咋办？这其实就是说：若待编码的数据无法按照 6bit 刚好拆完呢？

我们对 De 这 2 Bytes 字符串进行 Base64 编码，ASCII 是 01000100 01100101，编码后是 010001 000110 0101，最后一部分不足 6bit 的，怎么办？

Base64 规定：

这段话的意思是：待编码数据按照 3Bytes/组 进行分组后，如果 final quantum(最终量) 的 bit 数不足 24，那么在最后一个 encoding quantum(编码量) 右侧添加数个值为 0 的 bit，直到 final quantum 的 bit 数达到 6 bit 整数倍数。转为 Bytes 时，使用 = 符号作为 Padding(填充)，补充到 4 Bytes。

[!Tip]

• encoding quantum(编码量) # 每个 8 bit 组成的一组数据（就是图中每个橙色的框）
• final quantum(最终量) # 是按照 3 Bytes 分组后，最后一组数据。个人感觉是个简写，其实就是 final encoding quantum

所以，最后得到的编码结果为：RGU=。共 4 Bytes

这里面的思想，要使用另一个计算方式：

$$6 - ((n \times 8) \mod 6)$$

n 个 Bytes，有 $n * 8$ 个 bit，除 6 后得到 余数，再用 6 减去 余数，即可得到需要补充的 bit 数。

[!Note] 这里的余数本质是按照 6bit/组 进行分组后，最后一组的 bit 数

约分后本质就是 4 / 3，那么任何数除 3 的余数一共有三种结果（0, 1, 2），具体需要补充的时候，要 * 2 获取约分前的结果（i.e. 0, 2, 4）：

• 余数为 0，不需要填充
• 余数为 2（除 3 余数为 1），距离 6 bit 还差 4 bit，填充 0000，两个 =
• 余数为 4（除 3 余数为 2），距离 6 bit 还差 2 bit，填充 00，一个 =

e.g 1 Bytes 待编码信息，(1 * 8) % 6 余数为 2，用 6 - 2 = 4，最后需要补 4 个 0

[!Attention] n * 8 / 6 与 n / 3 * 4 这两个公式的虽然结果一样，但是所表达的现实含义完全不同。不可相互对比。

这两个公式是对不同分组方式的实现。只不过约分后，这两个公式刚好一样而已。这是巧合

• n * 8 / 6 按照每个 Byte 应该包含多少 bit 进行分组。计算的是 原始数据 编码后需补充多少 bit，需要取余数。本质是 算余量。把所有 bit 打散，按每 6 个 bit 进行分组。
  • 人话：原来的字符映射表是 8bit/字符，现在改为 6bit/字符 后，这组数据有多少 bit 无法组成一个字符？
• n / 3 * 4 按照每次编码使用多少 Bytes 进行分组。计算的是 原始数据 编码后会扩大多少 Byte，需要向上取整。本质是 分组。把所有 Byte 打散，按每 3 个 Byte 进行分组后，还要计算每组的容量变为 4 之后，总 Byte 变成了多少。
  • 人话：一组数据，原本是 3字符/组，变为 4字符/组 后，一共有多少数据？

只不过刚巧 1 Byte = 8 bit。。就造成了这种错觉~ 所以，一个是先乘后除，另一个是先除后乘

如果楞要比较的话，那 n * 8 / 6 应该改为 n * 8 / 24 * 4，这时现实意义就一样，都是用来计算分组的了，只不过计算单位不一样了。

我再来一个简单点的示例

我们对 D 这 1 Btye 字符进行 Base64 编码，ASCII 是 01000100，编码后是 010001 00，需要填充 4 个 0，需要 2 个 =

所以，最后得到的编码结果为：RA==。共 4 Bytes

个人疑惑：

验证一下不使用填充的情况，找到 5 个 0 的字符反推一下，e.g. g

假如，编码后结果是 ag，Base64 字符映射表对应 011010 100000。解码时，如果没有填充，取 8 bit 是 01101010，解码结果为 j，最后还是最多剩下 4 bit 嘛~ 那不写填充的 = 不是一样可以解码吗？为啥非要加个填充呢。。。。。

最终

若有 n Bytes 需要编码，则编码后需要传输的总 Bytes 为: $\frac{n}{3} \times 4$，除不开最终结果向上取整

哪怕多出来 1 bit，实际也会占 6 bit，只有 6 bit 的数据才是有意义的，能够参考 Base64 编码表找到对应字符的

假如有 1 Bytes，$1 / 3 = 0.3\dot{3}$，向上取整为 1，$1 * 4 = 4$，所以 1 Bytes 编码后是 4 Bytes

示例：

1 Bytes -> 4 Bytes; 2 Bytes -> 4 Bytes; 3 Bytes -> 4 Bytes;

4 Bytes -> 8 Bytes; 5 Bytes -> 8 Bytes; 6 Bytes -> 8 Bytes;

7 Bytes -> 12 Bytes; …… 略