Base32 编码解释
手机扫一扫
吃鸡疯狂打call技能get必备外挂
文彬编程网编码文章Base32 编码解释

Base32 编码解释

编码文章call10242025-03-31 13:32:0619A+A-

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 string
0x3d89a119b3f841078f293daf5b964e50     # hex
81797519916847327862337238645062651472 # decimal
1xh6ghkczr843rya9xnxdsckjg             # 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 # hex
111 # binary (3 bits, our chunk size)

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

number = 249
digit  = 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 = 249

while number > 0
  digit = digits[number & 0x7]
  result.push(digit)
  number = number >> 3
end

puts 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 = 249

while number > 0
  digit = digits[number & 0xf] # 0xf = 0b1111
  result.push(digit)
  number = number >> 4
end

puts 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 number

0110011001101111011011110110001001100001

首先，我们将字符串转换为字节数组。然后我们将数组分成 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 = 0
chunk.each do |byte|
  buf = (buf << 8 byte end buf> 439956234849 (01100 11001 10111 10110 11110 11000 10011 00001)

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

1100110 << 8
110011000000000 + 1101111 = 110011001101111

110011001101111 << 8
11001100110111100000000 + 1101111 = 11001100110111111011111

11001100110111101101111 << 8
1100110011011110110111100000000 + 1100010 = 1100110011011110110111101100010

1100110011011110110111101100010 << 8
110011001101111011011110110001000000000 + 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 - 1

encoded.length.times do |i|
  encoded[j] = ALPHABET[(buf >> 5 * i) & 0x1f]
  j -= 1
end

encoded.join #=> MZXW6YTB

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

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

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

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

这里需要进行两次计算：

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

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

40 bits = 8 characters
8 bits  = x characters

x = 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 * 8
number_of_characters = (bits_in_chunk / 5.to_f).ceil     # how many encoded characters this chunk will produce
padding = 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 5

buf = 0
chunk.each do |byte|
  buf = (buf << 8) + byte # combine the bytes into a single number
end
buf <<= padding add missing bits to the right encoded='Array.new(8)' an array to hold 8 encoded characters j='number_of_characters' - 1 encode 2 characters number_of_characters.times do i encodedj='ALPHABET[(buf'>> 5 * i) & 0x1f] # extract 5 bits at a time
  j -= 1
end

# pad the result with 6 '='
(8 - number_of_characters).times do |i|
  encoded[number_of_characters + i] = "="
end

encoded.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 number

0110011001101111011011110101101001100001

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

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

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

1. MZXW6YTBOI
2. ["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 = 0110000000
0110000000 + 11001 = 0110011001

0110011001 << 5
011001100100000 + 10111 = 011001100101111

011001100101111 << 5
01100110010111100000 + 10110 = 01100110010111110110

01100110010111110110 << 5
0110011001011111011000000 + 11110 = 0110011001011111011001110

0110011001011111011001110 << 5
011001100101111101100111000000 + 11000 = 011001100101111101100111011000

011001100101111101100111011000 << 5
01100110010111110110011101100000000 + 10011 = 01100110010111110110011101100010011

01100110010111110110011101100010011 << 5
0110011001011111011001110110001001100000 + 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 个字节），我们必须做一些额外的工作。我们需要计算

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

整个解码顺序：

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

  decoded
end.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)
    # ...
  end
end

结果可能稍微难以理解，但这一更改的要点在下一节中应该会很清楚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 = 6
BITS_PER_CHUNK     = 24
CHARS_PER_CHUNK    = 4
CHUNK_LENGTH       = 3
ENCODING_MASK      = 0x3f # mask to extract 6 bits at a time

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

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

Detail:https://ptrchm.com/posts/base32-explained/

点击这里复制本文地址 以上内容由文彬编程网整理呈现，请务必在转载分享时注明本文地址！如对内容有疑问，请联系我们，谢谢！
base16

相关文章

qrcode

文彬编程网 © All Rights Reserved.  蜀ICP备2024111239号-4