Base64 是我无数次使用过的东西之一，但从未完全理解它的用途。对于我的UUID 缩短器，我选择实现 Base32——一种比 Base64 更具可读性和 URL 友好性的替代方案。我不想依赖任何第三方库来进行编码部分。这意味着回到基础知识并了解将数据编码为 Base2ⁿ 格式时实际发生的情况。

这篇文章是我尝试解释和可视化 Base32 编码如何在位级别工作以及它与其他 Base2ⁿ 格式（如 Base64）的关系。

我们将从头开始实现 Base32 编码器。我将使用 Ruby 作为示例代码，但原理应该很容易翻译成任何编程语言。

如果您想直接跳到代码，这就是结果。

什么是 Base2ⁿ 编码？

正如 Base10（十进制）使用 10 位数字来表示数字一样，Base2ⁿ 编码只是表示数字（或字节）的另一种方式，使用 2ⁿ 位数字代替：Base2（二进制）、Base16（十六进制）、Base32、Base64 等。我们拥有的数字越多，表示就越紧凑。

例如，让我们看一下同一 128 位数字 (UUID) 的不同表示形式：

3d89a119-b3f8-4107-8f29-3daf5b964e50   # standard UUID string0x3d89a119b3f841078f293daf5b964e50     # hex81797519916847327862337238645062651472 # decimal1xh6ghkczr843rya9xnxdsckjg             # base32 (Crockford's variant)# and binary:111101100010011010000100011001101100111111100001000001000001111000111100101001001111011010111101011011100101100100111001010000

可用位数决定了单个字符可以表示多少位。例如：使用二进制，我们可以将 1 位数据编码为每个字符（2^1 = 1 位的 2 个字符组合）。类似地，在 Base16（十六进制）中，我们可以将 4 位数据编码为单个字符（2^4 = 4 位的 16 个字符组合）。

推入位：如何将数字转换为 Base8

考虑到这一点，让我们从一个简单的示例开始：将数字249转换为 Base8（八进制）。有多种方法可以实现这一点，但为了说明 Base2ⁿ 编码的一般方法，我们将使用按位运算。

以下是数字 249 的二进制形式（8 位表示形式）：

11111001

Base8 使用 8 位数字 (0-7)，因此我们可以将 3 位数据编码为单个字符（2^3 = 3 位的 8 个字符组合）。

digits = ['0', '1', '2', '3', '4', '5', '6', '7']

数字 249 转换为八进制的 371。以下是二进制表示形式，以 3 位为一组：

011 111 001└─┘ └─┘ └─┘ 3   7   1

该方法非常简单：查看二进制表示形式，我们将值分成每组 3 位的组。每个组代表我们目标系统中的一个字符/数字（digits更具体地说，它在数组中的索引）。

从低位（右侧）开始，我们将使用位掩码一次提取 3 位：

7   # decimal (max. index in the digits array)0x7 # hex111 # binary (3 bits, our chunk size)

让我们提取前 3 位。我们将通过屏蔽除前 3 个较低（右侧）位之外的所有位来实现此目的：

number = 249digit  = number & 0x7 #=> 1 (001)

这为我们提供了结果中的第一个数字：1。

按位AND运算如下所示：

  011 111 001& 000 000 111= 000 000 001

现在我们必须转移到接下来的 3 位。我们将把最右边的位推到右边，将它们从数字中删除：

number = number >> 3 #=> 252 (000 001 111)

按位运算如下所示：

>>    011 111

现在，我们可以提取接下来的 3 位：

  000 011 111& 000 000 111= 000 000 111

这给了我们下一个数字：( 7) 0b111。

我们会一直这样做number > 0，所以在这种情况下，只需再做一次。移至最后 3 位：

>>        011

并提取最后 3 位：

  000 000 011& 000 000 111= 000 000 011

0b011在3我们的目标系统中，所以将它们放在一起，我们得到最终结果：371。

这是代表整个序列的代码：

digits = ['0', '1', '2', '3', '4', '5', '6', '7']result = []number = 249while number > 0  digit = digits[number & 0x7]  result.push(digit)  number = number >> 3endputs result.reverse.join #=> 371

对于任何 Base2ⁿ 编码，该方法实际上都是相同的。对于 Base8，该digits数组并不是严格必需的，但对于较大的基数，例如 Base16 或 Base32，我们需要定义表示附加数字的字符列表。

现在，让我们更改代码，将数字 249 编码为 Base16（每个字符 4 位）。为此，我们将定义 16 个字符并修改位掩码以一次提取 4 位：

digits = ['0', '1', '2', '3', '4', '5', '6', '7', '8', '9', 'a', 'b', 'c', 'd', 'e', 'f']result = []number = 249while number > 0  digit = digits[number & 0xf] # 0xf = 0b1111  result.push(digit)  number = number >> 4endputs result.reverse.join #=> f9

以同样的方式，您可以扩展代码以支持任何 Base2ⁿ 编码：只需向字母表中添加更多字符，根据字母表中的字符数计算位掩码和每次迭代中要移动的位数。我们将在下一节中更详细地探讨这个过程。

Base32 实现（RFC 4648）编码任意数据

在 Base32 中，每个字符可以编码 5 位数据（2^5 = 5 位的 32 个字符组合）。RFC 4648定义了以下字符集：

Value Encoding  Value Encoding  Value Encoding  Value Encoding    0 A             9 J            18 S            27 3    1 B            10 K            19 T            28 4    2 C            11 L            20 U            29 5    3 D            12 M            21 V            30 6    4 E            13 N            22 W            31 7    5 F            14 O            23 X    6 G            15 P            24 Y         (pad) =    7 H            16 Q            25 Z    8 I            17 R            26 2

该编码还有其他变体，例如Crockford 的 Base32，并且可以自定义字母表以满足特定需求1。但是，对于本文，我们将坚持使用 RFC 4648 版本。

将任意数据编码为 Base32 与我之前描述的略有不同。我们需要将输入字符串分成块（每个块 5 个字节），从左侧开始（最重要的在前）。

让我们一步步按照 RFC 算法对示例字符串： 进行编码foobar，该字符串应编码为MZXW6YTBOI======。

这是我们将要做的事情的可视化：

2. Join into a single number0110011001101111011011110110001001100001

首先，我们将字符串转换为字节数组。然后我们将数组分成 5 个字节的组。由于每个字节是 8 位，这意味着每个组将是 40 位（每字节 8 位 * 5 个字节）。

bytes = 'foobar'.bytes #=> [102, 111, 111, 98, 97, 114]chunks = bytes.each_slice(5).to_a# => [[102, 111, 111, 98, 97], [114]]

最后一组仅包含 1 个字节，因此它不能被 5 整除。我们稍后会处理这个问题。现在，让我们关注第一块：

102 111 111 098 097└─┘ └─┘ └─┘ └─┘ └─┘ f   o   o   b   a

以及二进制表示：

01100110 01101111 01101111 01100010 01100001└──────┘ └──────┘ └──────┘ └──────┘ └──────┘  102      111      111      098      097  f        o        o        b        a

首先，我们将这些字节组合成一个 40 位数字：

chunk = [102, 111, 111, 98, 97]buf = 0chunk.each do |byte|  buf = (buf << 8) + byteendbuf #=> 439956234849 (01100 11001 10111 10110 11110 11000 10011 00001)

这是上面循环的二进制版本：

1100110 << 8110011000000000 + 1101111 = 110011001101111110011001101111 << 811001100110111100000000 + 1101111 = 1100110011011111101111111001100110111101101111 << 81100110011011110110111100000000 + 1100010 = 11001100110111101101111011000101100110011011110110111101100010 << 8110011001101111011011110110001000000000 + 1100001 = 110011001101111011011110110001001100001

结果是一个 40 位数字。我们将这个数字分为八个 5 位组，每个 5 位组被编码为一个字符：

01100 11001 10111 10110 11110 11000 10011 00001└───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ 12    25    23    22    30    24    19    1    # index in the ALPHABET array M     Z     X     W     6     Y     T     B    # the character it represents

以下是提取这些 5 位组并将它们编码为 8 个字符的代码：

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567".split("")encoded = Array.new(8)j = encoded.length - 1encoded.length.times do |i|  encoded[j] = ALPHABET[(buf >> 5 * i) & 0x1f]  j -= 1endencoded.join #=> MZXW6YTB

此操作与我们在 Base8 示例中所做的非常相似。我们使用0x1f位掩码一次提取 5 位。每次提取后，我们将数字右移 5 位以访问接下来的 5 位。提取的 5 位作为索引来查找ALPHABET数组中对应的字符。

现在我们已经将第一个块编码为 Base32，但现在是处理棘手部分的时候了。

RFC 规定，如果最后一组包含少于 40 位，则必须用零填充，直到总位数能被 5 整除。每组 5 个字节应产生 8 个编码字符。如果最后一个块产生的字符少于 8 个，我们将用 填充剩余空间=。

在我们的示例中，最后一个块仅包含 1 个字节（8 位），因此我们将用 2 位填充它以达到 10 位，即能被 5 整除的最小数字。

这里需要进行两次计算：

确定最后一个块将产生多少个字符。计算填充该块以使总数可被 5 整除所需的位数。

对于第一部分，我们将使用以下公式：

40 bits = 8 characters8 bits  = x charactersx = 8 * 8 / 40 = 1.6

向上舍入，我们知道这个块应该产生 2 个字符

现在，对于填充计算：

padding = 5 - (chunk.size * 8) % 5

在我们的例子中，最后一个块是一个字节（114, 01110010，代表字母r）。我们将在末尾填充 2 位：

 011100100 << 2

这给了我们 10 位，将被编码为 2 个字符。

01110 01000└───┘ └───┘ 14    8    # index in the ALPHABET array O     I    # the character it represents

转换为代码，这是整个编码序列：

chunk = [114] # the last chunk, the letter "r"bits_in_chunk = chunk.length * 8number_of_characters = (bits_in_chunk / 5.to_f).ceil     # how many encoded characters this chunk will producepadding = bits_in_chunk < 40 ? 5 - bits_in_chunk % 5 : 0 # how many bits we need to pad to make the number of bits divisible by 5buf = 0chunk.each do |byte|  buf = (buf << 8) + byte # combine the bytes into a single numberendbuf <<= padding # add missing bits to the rightencoded = Array.new(8) # an array to hold 8 encoded charactersj = number_of_characters - 1# encode 2 charactersnumber_of_characters.times do |i|  encoded[j] = ALPHABET[(buf >> 5 * i) & 0x1f] # extract 5 bits at a time  j -= 1end# pad the result with 6 '='(8 - number_of_characters).times do |i|  encoded[number_of_characters + i] = "="endencoded.join #=> OI======

现在我们已经完成了编码部分。此时，我们的代码应该涵盖 RFC 描述的所有测试向量：

BASE32("")       = ""BASE32("f")      = "MY======"BASE32("fo")     = "MZXQ===="BASE32("foo")    = "MZXW6==="BASE32("foob")   = "MZXW6YQ="BASE32("fooba")  = "MZXW6YTB"BASE32("foobar") = "MZXW6YTBOI======"

现在，让我们反转这个过程。MZXW6YTBOI======在位级别上，返回的过程foobar将如下所示：

2. Join into a single number0110011001101111011011110101101001100001

逐步解码 Base32 字符串，我们必须执行以下操作：

=从输入字符串中删除填充字符。将字符串拆分为字符数组。将每个字符转换为ALPHABET数组中的索引。将数组划分为 8 个字节的块（40 位 = 8 * 5 编码位）。计算给定块代表的原始字节数（当最后一个块少于 40 位时）。计算编码时应用的位填充。将字节组合成一个数字并去除填充。通过一次提取 1 个字节（8 位）来解码该数字。

因此，从字符串开始MZXW6YTBOI======：

1. MZXW6YTBOI2. ["M", "Z", "X", "W", "6", "Y", "T", "B", "O", "I"]3. [12, 25, 23, 22, 30, 24, 19, 1, 14, 8]4. [[12, 25, 23, 22, 30, 24, 19, 1], [14, 8]]

数组的第一个块正好有 8 个元素。我们将把这些值组合成一个 40 位数字：

01100 11001 10111 10110 11110 10110 10011 00001└───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ └───┘ 12    25    23    22    30    22    19     1

01100 << 5 = 01100000000110000000 + 11001 = 01100110010110011001 << 5011001100100000 + 10111 = 011001100101111011001100101111 << 501100110010111100000 + 10110 = 0110011001011111011001100110010111110110 << 50110011001011111011000000 + 11110 = 01100110010111110110011100110011001011111011001110 << 5011001100101111101100111000000 + 11000 = 011001100101111101100111011000011001100101111101100111011000 << 501100110010111110110011101100000000 + 10011 = 0110011001011111011001110110001001101100110010111110110011101100010011 << 50110011001011111011001110110001001100000 + 00001 = 0110011001011111011001110110001001100001

我们最终应该得到与最初编码完全相同的数字。为了解码它，我们将这些位分组为 8 位段（字节）并一一提取它们：

01100110 01101111 01101111 01100010 01100001└──────┘ └──────┘ └──────┘ └──────┘ └──────┘  102      111      111      098      097   f        o        o        b        a

要一次提取 8 位，我们将使用0xff( 11111111) 位掩码：

  01100110 01101111 01101111 01100010 01100001& 00000000 00000000 00000000 00000000 11111111= 00000000 00000000 00000000 00000000 01100001                                      └──────┘                                         97

对于第二个块（OI，代表 2 个字节），我们必须做一些额外的工作。我们需要计算

该块在原始字符串中表示的字节数foobar。在编码过程中作为填充添加的位数。

整个解码顺序：

str = "MZXW6YTBOI"str = str.delete("=")bytes = str.each_char.map { |char| ALPHABET.index(char) }bytes.each_slice(8).map do |chunk|  number_of_original_bytes = (chunk.length * 5.0 / 8.0).floor  padding = chunk.length < 8 ? 5 - (number_of_original_bytes * 8) % 5 : 0  buf = 0  chunk.each do |byte|    buf = (buf << 5) + byte # each byte in the chunk represents 5 bits  end  buf >>= padding # remove the padding (in this case, the last 2 bits)  decoded = Array.new(number_of_original_bytes)  j = decoded.length - 1  number_of_original_bytes.times do |i|    # extract 8 bits at a time and convert to a character    decoded[i] = ((buf >> 8 * j) & 0xff).chr    j -= 1  end  decodedend.join #=> foobar

此时，我们应该有一个可以工作的 Base32 编码器和解码器。

走向更通用的方法

现在让我们将代码包装到一个类中。我们还将用常量替换硬编码值，以使其更具描述性和通用性：

class Base32  ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZ234567".split("")  PADDING_CHAR = "="  BITS_PER_BYTE  = 8  # 1 byte = 8 bits  BITS_PER_CHAR  = Math.log2(ALPHABET.length).round # 5 = 32 chars = 2^5 - number of bits encoded into a single character in the ALPHABET  BITS_PER_CHUNK = BITS_PER_CHAR.lcm(BITS_PER_BYTE) # 40 (least common mutliple of 5 and 8)  CHARS_PER_CHUNK = BITS_PER_CHUNK / BITS_PER_CHAR  # 8  CHUNK_LENGTH    = BITS_PER_CHUNK / BITS_PER_BYTE  # 5  ENCODING_MASK = ALPHABET.length - 1 # 0x1f  DECODING_MASK = 0xff  def self.encode(str)    # ...  end  def self.decode(str)    # ...  endend

结果可能稍微难以理解，但这一更改的要点在下一节中应该会很清楚2。

完整的实现可以在这里找到。

Base32的陷阱

与 Base64 相比，Base32 提供了更大的灵活性，并且有多种编码变体。字母表是完全可定制的：您可以更改字母表中的顺序，替换某些字符以避免意外的脏话或跳过看起来相似的字符，例如Crockford 的变体。但这是您只能做出一次的选择，并且以后您无法轻易更改字母表。

这种灵活性使得 Base32 与特定的实现紧密相关。缺乏通用标准是它不如 Base64 流行的一个重要原因。

Base64 及以上

现在我们知道了如何实现 Base32，让我们尝试使用相同的方法来实现我们自己的 Base64 编码器3。

Base64 将 6 位数据编码为单个字符（2^6 = 64 个 6 位字符组合）。这意味着我们的块必须是 8 和 6 的最小公倍数，即 24（每个字节 8 位，每个字符 6 位）。

我们现有的代码应该能够开箱即用地处理它。唯一需要的更改是替换ALPHABET数组：

ALPHABET = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz0123456789+/".split

代码的其余部分将是相同的。每个其他值将根据 的长度自动计算ALPHABET：

BITS_PER_CHARACTER = 6BITS_PER_CHUNK     = 24CHARS_PER_CHUNK    = 4CHUNK_LENGTH       = 3ENCODING_MASK      = 0x3f # mask to extract 6 bits at a time

理论上，我描述的方法可用于实现任何 Base2ⁿ 编码。然而，考虑到 ASCII 字符集仅包含 95 个可打印字符，Base64 是您在日常使用中看到的最高的 Base2ⁿ 编码。

话虽如此，实现 Base2ⁿ 编码器是您在现实世界中几乎不需要处理的问题。但我希望本文中的示例可以帮助您了解使用 Base64 或 Base32 时幕后到底发生了什么。

Detail: