可排序的 Base64 编码

Tomas Takac

4.28/5 (8投票s)

2019年11月3日

CPOL

7分钟阅读

11911

140

可排序且文件名友好的 Base64 编码

下载源代码 - 7.4 KB

引言

Base64 编码可以将二进制数据编码为文本，但存在一些缺点。首先，编码后的值可能包含“/”（斜杠），这使得 Base64 编码值在文件名中无法使用，除非你应用另一层编码。其次，当作为string排序时，编码值与作为数字排序的原始值排序方式不同。

背景

在我目前的项目中，我们大量使用 Azure blob 存储。它有一个很方便的功能，即在列出 blobs 时，它总是按名称排序返回。我们依赖此功能来实现版本控制，这样较新的版本就会出现在列表中的最新版本之前。这样，您就可以通过列出给定前缀的“top 1” blobs 来获取实体的最新版本。

有一次，我们需要扩展我们的版本控制方案。我喜欢使用 Base64 对二进制值进行编码的想法，但很快我就了解到了介绍中描述的缺点。最终，我们决定走向另一个方向，但我认为实现这个“更好”的 Base64 仍然很有趣。

Base64

有几种方法可以将二进制数据编码为文本。例如，您可以使用十进制或十六进制数字。顾名思义，Base64 使用 64 个字符：除了 10 个十进制数字外，还有大写字母、小写字母以及两个附加字符“+”和“/”。“=”符号仅用于填充，不编码任何信息。但是不同的编码在输入和输出长度之间有不同的比例。让我们编码 16 个字节，这是 GUID 的长度。

编码	输出长度	示例
十进制数字	39	83010580618813770707986403520966229089
十六进制数字	32	f3cefc61311240f9a9dc6c519c41733e
Base64	24（不带填充为 22）	YfzO8xIx+UCp3GxRnEFzPg==
二进制	16

这些数字是如何得来的？一个 GUID 是 16 个字节，也就是 128 位 - 即 2¹²⁸ 种组合。我们使用对数来获得输出中数字或字符的数量。对数的底是编码中可用字符的数量。因此，对于十进制数字我们使用 log₁₀，对于十六进制数字我们使用 log₁₆，对于 Base64 编码我们使用 log₆₄。正如您所见，编码中可用的字符越多，生成的文本就越短。

您可以在 Wikipedia 上阅读有关二进制到文本编码的更多信息。

字符选择

.NET 实现的 Base64 编码使用以下字符：大写字母“A”到“Z”，然后是小写字母“a”到“z”，然后是十进制数字“0”到“9”，最后是两个附加字符“+”和“/”。

字符	ASCII 码
A .. Z	65 .. 90
a .. z	97 .. 122
0 .. 9	48 .. 57
+ (加号)	42
/ (斜杠)	47

这种字符选择有两个问题。首先，使用“/”显然对文件名有问题。然后，字符的排序不保留排序，因为对于编码中的较高值，它使用了较低的 ASCII 码。为了解决这些问题，我们改变了编码字符的顺序，并选择“/”以外的其他字符。

字符	ASCII 码
+ (加号)	42
0 .. 9	48 .. 57
A .. Z	65 .. 90
_ (下划线)	95
a .. z	97 .. 122

下划线是一个自然的选择，因为它常用于标识符，并且在文件名中受支持。新的排序也与 ASCII 码的排序相匹配。在代码中是这样的

private const string Base64Characters = 
    "+0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ_abcdefghijklmnopqrstuvwxyz";

填充

在 .NET 实现中，输出总是以“=”结尾进行填充，以使输出长度成为 4 的倍数。这当然会破坏排序。为了保留排序，我们需要在 string 的前面添加填充。而且这完全没有必要，我们也不会使用它。

我们仍然需要插入一些填充位来在输出中获得一个完整的字节数。这里有一个简单的规则：

输入长度	输出长度	额外填充位
3n	4n	0 位
3n + 1	4n + 2	4 位
3n + 2	4n + 3	2 位

在上表中，“n”是正整数。我们可以将 3 个字节编码为 4 个 Base64 字符，而无需任何填充。输入大小不是 3 的倍数将导致输出大小的位数不能被 8 整除。在这种情况下，我们将零位插入在输出最高有效字符的前面。

您可以在下表中验证以上内容

输入长度	输出位数
3n	8 * 3n = 24n = 6 * 4n
3n + 1	8 * (3n + 1) = 24n + 8 = 24n + 6 + 2 = 6 * (4n + 1) + 2
3n + 2	8 * (3n + 2) = 24n + 16 = 24n + 12 + 4 = 6 * (4n + 2) + 4

字节序

在我们深入研究实际代码之前，我们需要稍作停留来解释数据布局。.NET 平台是小端序。这意味着对于数组，越重要的值索引越高。因此，最低有效值存储在数组的开头，最高有效值存储在数组的末尾。这很重要，因为当编码为 Base64 时，我们希望将最高有效值放在 string 的开头，将最低有效值放在 string 的末尾。所以顺序是相反的。

要了解更多信息，请阅读 Wikipedia 上的 Endianness。

编码

首先，我们需要确定输出中有多少个字符。我们将遵循上表。我们将每个 3 字节分组使用 4 个 Base64 字符进行编码。如果我们有 1 个额外的字节，我们会添加另外 2 个字符和 4 个填充位。如果我们有 2 个额外的字节，我们会添加另外 3 个字符和 2 个填充位。

var numberOfChars = 4 * Math.DivRem(input.Length, 3, out int extraBytes);

if (extraBytes > 0)
{
    numberOfChars += extraBytes + 1;
}

var output = new char[numberOfChars];

switch (extraBytes)
{
    case 0:
        // no padding
        Encode0(input, output, input.Length - 1, 0);
        break;
    case 1:
        // 4 padding bits
        Encode1(input, output);
        break;
    case 2:
        // 2 padding bits
        Encode2(input, output);
        break;
    default:
        throw new InvalidOperationException("Unreachable code");
}

return new string(output);

无填充编码

这是最简单的编码情况。我们从输入中获取 3 个字节，并在输出中生成 4 个字符。请记住，我们是从末尾读取输入的！

private void Encode0(byte[] input, char[] output, int inputIndex, int outputIndex)
{
    while (inputIndex > 0)
    {
        var i0 = input[inputIndex];
        var i1 = input[inputIndex - 1];
        var i2 = input[inputIndex - 2];

        // 000000 001111 111122 222222
        var o0 = i0 >> 2;
        var o1 = ((i0 & 0x03) << 4) | (i1 >> 4);
        var o2 = ((i1 & 0x0F) << 2) | (i2 >> 6);
        var o3 = i2 & 0x3F;

        output[outputIndex] = Base64Characters[o0];
        output[outputIndex + 1] = Base64Characters[o1];
        output[outputIndex + 2] = Base64Characters[o2];
        output[outputIndex + 3] = Base64Characters[o3];

        inputIndex -= 3;
        outputIndex += 4;
    }
}

带 4 位填充的编码

在这种情况下，我们有一个额外的字节，并将其编码为两个 Base64 字符，带有 4 位填充。处理完这个额外的字节后，我们可以像没有填充一样继续。

private void Encode1(byte[] input, char[] output)
{
    var len = input.Length;
    var i0 = input[len - 1];

    // ....00 000000
    var o0 = i0 >> 6;
    var o1 = i0 & 0x3F;

    output[0] = Base64Characters[o0];
    output[1] = Base64Characters[o1];

    Encode0(input, output, len - 2, 2);
}

带 2 位填充的编码

在这种情况下，我们有两个额外的字节，并将它们编码为 3 个 Base64 字符，带有 2 位填充。同样，在处理完这两个字节后，我们可以像没有填充一样继续。

private void Encode2(byte[] input, char[] output)
{
    var len = input.Length;
    var i0 = input[len - 1];
    var i1 = input[len - 2];

    // ..0000 000011 111111
    var o0 = i0 >> 4;
    var o1 = ((i0 & 0x0F) << 2) | (i1 >> 6);
    var o2 = i1 & 0x3F;

    output[0] = Base64Characters[o0];
    output[1] = Base64Characters[o1];
    output[2] = Base64Characters[o2];

    Encode0(input, output, len - 3, 3);
}

解码

我们使用反向过程来确定输出中有多少个字节。每 4 个字符一组编码 3 个字节。如果我们有 2 个额外的字符，我们添加 1 个字节并使用 4 位填充进行解码。如果我们有 3 个额外的字符，我们添加 2 个字节并使用 2 位填充进行解码。

var numberOfBytes = 3 * Math.DivRem(input.Length, 4, out int extraChars);

if (extraChars > 0)
{
    numberOfBytes += extraChars - 1;
}

var output = new byte[numberOfBytes];

switch (extraChars)
{
    case 0:
        // no padding
        Decode0(input, output, 0, output.Length - 1);
        break;
    case 2:
        // 4 padding bits
        Decode1(input, output);
        break;
    case 3:
        // 2 padding bits
        Decode2(input, output);
        break;
    default:
        throw new InvalidOperationException("Unreachable code");
}

return output;

无填充解码

这是最简单的解码情况。我们从输入中获取 4 个字符，并在输出中生成 3 个字节。请记住，我们需要从末尾将字节放入输出！

private void Decode0(string input, byte[] output, int inputIndex, int outputIndex)
{
    while (inputIndex < input.Length)
    {
        var i0 = Base64Characters.IndexOf(input[inputIndex]);
        var i1 = Base64Characters.IndexOf(input[inputIndex + 1]);
        var i2 = Base64Characters.IndexOf(input[inputIndex + 2]);
        var i3 = Base64Characters.IndexOf(input[inputIndex + 3]);

        // 000000 001111 111122 222222
        var o0 = (byte)((i0 << 2) | (i1 >> 4));
        var o1 = (byte)((i1 << 4) | (i2 >> 2));
        var o2 = (byte)((i2 << 6) | i3);

        output[outputIndex] = o0;
        output[outputIndex - 1] = o1;
        output[outputIndex - 2] = o2;

        inputIndex += 4;
        outputIndex -= 3;
    }
}

带 4 位填充的解码

在这种情况下，我们有 2 个额外的 Base64 字符，并将其解码为 1 个字节，带有 4 位填充。处理完这些额外的字符后，我们可以像没有填充一样继续。

private void Decode1(string input, byte[] output)
{
    var i0 = Base64Characters.IndexOf(input[0]);
    var i1 = Base64Characters.IndexOf(input[1]);

    // ....00 000000
    var o0 = (byte)((i0 << 6) | i1);

    var len = output.Length;
    output[len - 1] = o0;

    Decode0(input, output, 2, len - 2);
}

带 2 位填充的解码

在这种情况下，我们有 3 个额外的 Base64 字符，并将其解码为 2 个字节，带有 2 位填充。处理完这些额外的字符后，我们可以像没有填充一样继续。

private void Decode2(string input, byte[] output)
{
    var i0 = Base64Characters.IndexOf(input[0]);
    var i1 = Base64Characters.IndexOf(input[1]);
    var i2 = Base64Characters.IndexOf(input[2]);

    // ..0000 000011 111111
    var o0 = (byte)((i0 << 4) | (i1 >> 2));
    var o1 = (byte)((i1 << 6) | i2);

    var len = output.Length;
    output[len - 1] = o0;
    output[len - 2] = o1;

    Decode0(input, output, 3, len - 3);
}

关注点

我们新的编码是可排序的，但有一些值得提及的限制。首先，它只适用于长度相同的 string，较短的 string 不总是排在较长的 string 之前。您可以选择将 string 填充到相同的大小，或者实现自己的比较器。

默认排序	带前缀的排序
aa	+aa
aaa	+ab
aab	aaa
ab	aab
aba	aba
abb	abb

另一个问题是，排序在 .NET 中仅适用于序数字符串比较。Azure blob 存储按预期列出 blobs，但您需要在 List.Sort() 中显式指定比较器，例如。当您使用默认比较器对 Base64 字符进行排序时，看起来像这样

_+0123456789aAbBcCdDeEfFgGhHiIjJkKlLmMnNoOpPqQrRsStTuUvVwWxXyYzZ

历史

2019 年 11 月 3 日 - 初始发布