haskell - Base64 规范编码

Question

我正在尝试测试 encode 和 decode 函数(在 Data.ByteString.Base64.Lazy 中定义)是相反的:

import qualified Data.ByteString.Lazy as BL

encoded :: Gen BL.ByteString
encoded = do
  body <- concat <$> listOf (group 0)
  end <- group =<< choose (0, 2)
  return . BL.pack $ body <> end
 where
  group :: Int -> Gen [Word8]
  group pad = do
    letters <- vectorOf (4 - pad)
      . elements . map (fromIntegral . ord)
      $ ['A'..'Z'] <> ['a'..'z'] <> ['0'..'9'] <> ['+','/','=']
    return $ letters <> replicate pad 61  -- 61 is ascii for =

prop_encDec = forAll encoded $ \b ->
  [b] == (encode <$> rights [decode b])

但是 QuickCheck 在那里发现了一个问题:

=== prop_encDec ===
*** Failed! Falsifiable (after 1 test):
"1yx="

我已经调查过这个问题一定与非规范编码有关，但我很难理解它是什么以及如何处理它。你能解释一下这个例子为什么解码“1yx=”并重新编码会产生“1yw=”吗？

Answer 1

问题是 x 确实在与编码无关的位置包含了一些。

让我详细说明:base64 字符串 1yx= 将被解码为以下二进制模式

base64: 1      y      x      =
binary: 000001 110010 110001 000000

但是字符串末尾的 = 告诉编码器最后 8 位不相关，所以

000001 110010 110001 000000
^^^^^^ ^^^^^^ ^^^^

只有标记的位会被解码为

binary: 000001 110010 1100

如您所见，x 编码的最后两位 (01) 被忽略

然后如果我们对解码数据进行编码，编码器将用零位填充位流，导致

binary: 000001 110010 110000 000000
                          ^^ ^^^^^^
base64: 1      y      w      =

因此得出结论:编码器不能“正确地”重新编码已解码的 1yx=，因为它包含因解码而丢失的信息。

为了您的测试目的，我建议交换操作顺序。因此，生成一些随机字符串作为输入，对其进行编码，然后对其进行解码，并将其与原始输入进行比较。

您可能还想查看 example维基百科文章的 Base64 编码部分。它包含有关数据填充的商品示例。

---

关于规范和非规范编码:

当且仅当所有填充位都为零时，base64 字符串才是规范的，如果其中一个填充位不为零，则该字符串是非规范的。因此，如果一个 base64 字符串在末尾有一个 =，那么最后 8 位必须为零才能成为规范字符串，如果字符串在末尾有两个 = 那么最后 16 位必须为零。

所以字符串 1yx= 是非规范的，因为正如我们在上面看到的，其中一个填充位是 1。另一方面，字符串 1yw= 是规范的，因为所有 8 个填充位都是零。