将字节数组转换为任意进制

Question

我有一个字节数组（任意长度），我想使用自己的基础编码器将此数组编码为字符串。在.NET中，有标准的Base64编码器，但如果我想将数组编码为Base62，Base53或Base13呢？

创建这样的通用基础编码器是否可能？

我知道我可以采用简单的方法，即为每个字节保留固定数量的字符（在Base62的情况下，这将是5个字符），并进行直接的字节->字符编码，但我会浪费空间，因为5个Base62字符能够包含多于1个字节但少于2个字节。

我应该如何编写这样的编码器？或者已经有某些类可以实现这一点吗？ 请注意，我还需要通用解码器，否则对我来说这是无用的。

资源

由于解决方案已经知道（使用BigInteger），因此我只想在此处放置一些与BigInteger类相关的资源，因为它在.NET 3.5中不可用：

C#中的大整数
http://intx.codeplex.com/
https://svn.apache.org/repos/asf/incubator/heraldry/libraries/csharp/openid/trunk/Mono/Mono.Math/BigInteger.cs
http://www.codeproject.com/KB/cs/BigInteger_Library.aspx
http://www.codeproject.com/KB/cs/biginteger.aspx

- Paya

---

你能解释一下 Base53 或 Base62 编码在哪些情况下会有用吗？ - Frank Bollack

顺便说一下，如果你想将字节数组转换为字符串，而不需要任何“/”和“+”等类似的符号，只需要使用Base62编码，可以得到只包含小写字母、大写字母和数字0-9的字符串。 - Paya

5个基于62进制的数字可以编码比2个字节更多的数据！ - Nick Johnson

如果您仍然对此感兴趣，并且它不必是普遍数学可移植的，我建议考虑分块。我已经在uint64算术上实现了数字div/mod工作，每次转换8个字节（对于base62产生11个字符，需要10.75个字符，2.3％的开销）。虽然不太节省空间，但速度非常快（没有比较，但没有缓慢的任意长度整数参与）。 - ygoe

Answer 1

晚了一点，但是...

因为你的规范要求使用任意数量的位，所以你必须有一个可以处理任意数量位数的整数类型。如果你无法使用 .NET 4.0，你需要在其他地方获取 BigInteger 实现（例如 .NET 4.0）。

public static class GenericBaseConverter
{
    public static string ConvertToString(byte[] valueAsArray, string digits, int pad)
    {
        if (digits == null)
            throw new ArgumentNullException("digits");
        if (digits.Length < 2)
            throw new ArgumentOutOfRangeException("digits", "Expected string with at least two digits");

        BigInteger value = new BigInteger(valueAsArray);
        bool isNeg = value < 0;
        value = isNeg ? -value : value;

        StringBuilder sb = new StringBuilder(pad + (isNeg ? 1 : 0));

        do
        {
            BigInteger rem;
            value = BigInteger.DivRem(value, digits.Length, out rem);
            sb.Append(digits[(int)rem]);
        } while (value > 0);

        // pad it
        if (sb.Length < pad)
            sb.Append(digits[0], pad - sb.Length);

        // if the number is negative, add the sign.
        if (isNeg)
            sb.Append('-');

        // reverse it
        for (int i = 0, j = sb.Length - 1; i < j; i++, j--)
        {
            char t = sb[i];
            sb[i] = sb[j];
            sb[j] = t;
        }

        return sb.ToString();

    }

    public static BigInteger ConvertFromString(string s, string digits)
    {
        BigInteger result;

        switch (Parse(s, digits, out result))
        {
            case ParseCode.FormatError:
                throw new FormatException("Input string was not in the correct format.");
            case ParseCode.NullString:
                throw new ArgumentNullException("s");
            case ParseCode.NullDigits:
                throw new ArgumentNullException("digits");
            case ParseCode.InsufficientDigits:
                throw new ArgumentOutOfRangeException("digits", "Expected string with at least two digits");
            case ParseCode.Overflow:
                throw new OverflowException();
        }

        return result;
    }

    public static bool TryConvertFromString(string s, string digits, out BigInteger result)
    {
        return Parse(s, digits, out result) == ParseCode.Success;
    }

    private enum ParseCode
    {
        Success,
        NullString,
        NullDigits,
        InsufficientDigits,
        Overflow,
        FormatError,
    }

    private static ParseCode Parse(string s, string digits, out BigInteger result)
    {
        result = 0;

        if (s == null)
            return ParseCode.NullString;
        if (digits == null)
            return ParseCode.NullDigits;
        if (digits.Length < 2)
            return ParseCode.InsufficientDigits;

        // skip leading white space
        int i = 0;
        while (i < s.Length && Char.IsWhiteSpace(s[i]))
            ++i;
        if (i >= s.Length)
            return ParseCode.FormatError;

        // get the sign if it's there.
        BigInteger sign = 1;
        if (s[i] == '+')
            ++i;
        else if (s[i] == '-')
        {
            ++i;
            sign = -1;
        }

        // Make sure there's at least one digit
        if (i >= s.Length)
            return ParseCode.FormatError;


        // Parse the digits.
        while (i < s.Length)
        {
            int n = digits.IndexOf(s[i]);
            if (n < 0)
                return ParseCode.FormatError;
            BigInteger oldResult = result;
            result = unchecked((result * digits.Length) + n);
            if (result < oldResult)
                return ParseCode.Overflow;

            ++i;
        }

        // skip trailing white space
        while (i < s.Length && Char.IsWhiteSpace(s[i]))
            ++i;

        // and make sure there's nothing else.
        if (i < s.Length)
            return ParseCode.FormatError;

        if (sign < 0)
            result = -result;

        return ParseCode.Success;
    }
}

- Tergiver

---

+1 表示代码，但是 apoorv020 首先提出了使用 BigInteger 的解决方案。 - Paya

优秀的代码。可以通过在字节数组末尾添加空字节来避免负的 BigInteger 情况。对于大于 256 的进制，这可能会导致字符串比减号前缀更小。如果 BigInteger 的最后一个字节设置了 0x80 标志，则其为负数。 - tigrou

Answer 2

这是我从博客中复制的内容，希望能帮助您了解如何（以及为什么）将其转换为Base62。

我目前正在开发自己的URL缩短服务：konv.es。 为了创建URL的最短字符哈希值，我使用字符串的GetHashCode()方法，然后将得到的数字转换为Base62（[0-9a-zA-Z]）。 到目前为止，我发现最优雅的解决方案是进行转换（这也是一个非常方便的yield return示例）：

public static IEnumerable<char> ToBase62(int number)
    {
        do
        {
            yield return "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"[number % 62];
            number /= 62;

        } while (number > 0);
    }

额外加分：将其重构为扩展方法

- Steve Konves

---

你有反转这个的方法吗？ - Mat

在哈希值被持久化时，使用GetHashCode()方法是不可靠的。字符串的哈希码在x86和x64运行时以及不同版本的.NET之间可能会有所不同。它只能保证在运行时给出相同的哈希码。 - Drakarah

Answer 3

如果性能不是问题，请在后台使用BigInteger类。您可以使用一个接受字节数组的BigInteger构造函数，然后手动运行除法和模数循环以获得其他非标准基数的表示形式。

还要看看this。

- apoorv020

---

谢谢，我完全忘记了 BigInteger 类，它可以解决这个问题！只要编码 500 字节的数据不超过 5 秒，性能就不是问题。 - Paya

啊，BigInteger 是在 .NET 4.0 中的，但我需要 .NET 3.5 的解决方案。 :-( - Paya

第二个链接中提到的j#库怎么样？ - apoorv020

我实际上并不想在我的项目中添加更多的依赖项，所以如果我使用 BitInteger 解决方案，我可能会使用一些可以编译到我的 .exe 中的代码，例如这个 CodeProject 实现。然而，+1，因为 BigInteger 确实能够解决这个问题。如果没有人提出其他解决方案，我将坚持使用它并接受你的答案。谢谢。 - Paya

Answer 4

BASE64的工作原理很好，因为64是2的幂（2^6），所以每个字符可以保存6位数据，3个字节（3 * 8 = 24位）可以编码成4个字符（4 * 6 = 24）。编码和解码只需通过位移即可完成。

对于不与2的幂对齐的基数（如你的62进制或53进制），则必须将要编码的消息视为一个长数字，并对其执行除法和取模运算。您最好使用Base32编码并浪费一些带宽。

- James Curran

---

那么除了使用 BigInteger 类或类似的东西，没有其他解决方案了吗？ - Paya

Answer 5

受Steve Konves的回答启发

using System.Numerics;

const string base62Chars = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ";
const string base26Chars = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

static void Main() {
    string id = "xAQ0f58JgG";

    BigInteger i = fromBaseX(id, base62Chars);
    Console.WriteLine(i);

    string c = ToBaseX(i, base62Chars);
    Console.WriteLine(c);

    string c2 = ToBaseX(i, base26Chars);
    Console.WriteLine(c2);

    BigInteger i2 = fromBaseX(c2, base26Chars);
    Console.WriteLine(i2);
}

public static string ToBaseX(BigInteger number, string baseX)
{
    int l = baseX.Length;
    string result = "";
    while (number > 0)
    {
        BigInteger remainder = number % l;
        int index = (int)remainder;
        if (index >= l)
        {
            throw new ArgumentException($"Cannot convert {number} ToBaseX {baseX}");
        }
        result += baseX[index];
        number /= l;
    }
    return result;
}

public static BigInteger fromBaseX(string input, string baseX)
{
    int l = baseX.Length;
    BigInteger result;
    int pow = 0;
    foreach (char c in input)
    {
        int index = baseX.IndexOf(c);
        if (index < 0)
        {
            throw new ArgumentException($"Cannot convert {input} fromBaseX {baseX}");
        }
        BigInteger additions = BigInteger.Pow(l, pow) * index;
        result += additions;
        pow++;
    }
    return result;
}

- BillWCJ

Answer 6

您可以从 Michael Giagnocavo 实现的 C# Base32 实现中获取灵感。

- Yakeen

---

我已经仔细查看了那段代码，发现有一个问题：无论是Base64还是Base32都可以直接映射到一些位数，Base64的情况下是6位，而Base32的情况下是3位，但例如Base62并不能映射到整数位数。因此，我不知道如何将Base32实现转换为通用基编码器。 - Paya

@Paya 我认为你是指基于32的5位，因为2⁵=32。 - Kevin Li

Answer 7

我写了一篇文章，描述了一个用Python解决你的问题的方案。我没有使用Python的非常特殊的功能，以便得到一个可以轻松在其他语言中实现的解决方案。你可以看一看，看看它是否符合你的需求。

- Jonny Dee

Answer 8

一篇关于CodeReview的帖子促使我创建了一个RadixEncoding类，它能够处理将字节数组编码/解码为基于N的字符串。

该类可以在这个Q&A线程中找到，其中包括有关BigInteger、字节序支持以及类整体性能的文档和解决方案。

- kornman00

Answer 9

另一个需要注意的例子是Ascii85，它被用于Adobe PostScript和PDF文档中。在Ascii85中，使用5个字符来编码4个字节。你可以通过计算(256^4)/(85^5) = 96.8%来确定这种编码的效率。这是实际使用的位组合的分数。

因此，无论你想要使用什么新的基数来编码你的数据，如果你想最大化编码效率，你需要寻找一个能够使其略高于256的幂次方。对于每个基数，这可能并不容易。检查基数53表明，除非你愿意使用88个字节来编码63个字节，否则你最好的选择可能是使用7个字节来编码5个字节（93.6%的效率）。

- Justin

Answer 10

这是将字节数组转换为base64的示例代码片段。关于这个问题有一篇非常好的文章，我参照了this。

public class Test {

    private static final char[] toBase64URL = {
            'A', 'B', 'C', 'D', 'E', 'F', 'G', 'H', 'I', 'J', 'K', 'L', 'M',
            'N', 'O', 'P', 'Q', 'R', 'S', 'T', 'U', 'V', 'W', 'X', 'Y', 'Z',
            'a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm',
            'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z',
            '0', '1', '2', '3', '4', '5', '6', '7', '8', '9', '-', '_'
    };

    public static void main(String[] args) {

        byte[] mess = "ABC123".getBytes();

        byte[] masks = { -128, 64, 32, 16, 8, 4, 2, 1 };
        StringBuilder builder = new StringBuilder();

        for(int i = 0; i < mess.length; i++) {
            for (byte m : masks) {
                if ((mess[i] & m) == m) {
                    builder.append('1');
                } else {
                    builder.append('0');
                }
            }
        }

        System.out.println(builder.toString());

        int i =0;
        StringBuilder output = new StringBuilder();
        while (i < builder.length()){
            String part = builder.substring(i, i+6);
            int index = Integer.parseInt(part, 2);
            output.append(toBase64URL[index]);
            i += 6;
        }

        System.out.println(output.toString());

    }
}

- Hrishikesh Mishra