Base62 与 Base91 两种编码范式的完整实现与推演

在我的项目里，Base62 和 Base91 是仅有的两个「标准库没有、必须手写」的编码器。本文把它们从数学原理到逐行代码到手动演算完整拆开。

Base 编码到底是什么

所有 Base 编码做的都是同一件事：把一串字节（byte）按某种分块规则映射成一串可打印字符。 区别只在「每个字符能装多少 bit」以及「bit 不整除时怎么凑齐」。

最耳熟能详的是 Base64：字符表 64 个字符，因为 64 = 2⁶，每个字符正好装 6 bit。但 8 和 6 不整除，它没法逐字节处理，只能攒满 3 个字节（24 bit）拼成 4 个字符，末尾不够 24 bit 就用 = 补齐。这套「凑整数倍 + 补位」的玩法是大多数 base 的通用套路。

本文要讲的是 Base64 的两个「不守规矩」的变体：

• Base62：字符表只有 62 个，不是 2 的整数次幂，每字符只能装 ≈ 5.95 bit。既然装不整，它干脆不走位分块，而是把整串字节当成一个大整数，反复「除以 62 取余」——大数 divmod 路线。
• Base91：字符表 91 个，每字符装 ≈ 6.5 bit，是常见 Base 里密度最高的。它想逼近这个上限，就直接对比特流动手，按 13/14 bit 切块——比特流切块路线。

术语澄清：base 是编码不是加密——无密钥、无保密性，只是「字节 ↔ 文本」的可逆映射。说「base 加密」是通俗叫法。

一个先决知识：字节 ≠ 字符。"999" 是 3 个 ASCII 字符，UTF-8 编码后是 3 个字节 {0x39,0x39,0x39}；而整数 999 是 2 个字节 {0x03,0xE7}。所有 base 编码器只认字节，不认识「屏幕上的数字」——这决定了后面的一切。

Base62：大数 divmod 范式

数学思想

把整串字节看成一个 256 进制的大整数，再转换成 62 进制。

• 字节串 {b0,b1,b2} 的数值 = b0·256² + b1·256 + b2（大端）。
• 不断「除以 62 取余」：余数是一位 base62 数码，商继续下一轮，直到商为 0。
• 收集到的余数是低位在前，要反转成高位在前。
• 因为 big.Int.SetBytes 会丢弃前导零字节，编码前先数出前导零个数，用 alphabet[0]（'0'）补回——保证二进制可无损还原。

字符表 0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz，下标即数码值。

编码实现

func base62Encode(input []byte) string {
    // SetBytes 丢弃前导零字节 → 先统计前导 0x00 个数，末尾用 '0'(alphabet[0]) 补回
    lead := 0
    for lead < len(input) && input[lead] == 0 {
        lead++
    }

    x := new(big.Int).SetBytes(input[lead:]) // 前导零去掉后的字节串 → 大整数
    base := big.NewInt(62)
    mod := new(big.Int)
    // 容量估算：base62 每字符 ≈ log2(62)≈5.95bit，每字节8bit → 输出≈输入×8/5.95≈1.3436倍
    result := make([]byte, 0, len(input)*138/100+1)

    for x.Sign() > 0 {
        x.DivMod(x, base, mod)           // x = x÷62，余数写进 mod
        result = append(result, base62Alphabet[mod.Int64()]) // 余数 → 当前位字符
    }
    // result 现在是低位在前，需反转
    for i, j := 0, len(result)-1; i < j; i, j = i+1, j-1 {
        result[i], result[j] = result[j], result[i]
    }

    // 补回前导零：'0' 就是 alphabet[0]，对应数值 0
    prefix := make([]byte, lead)
    for i := range prefix {
        prefix[i] = base62Alphabet[0]
    }
    return string(append(prefix, result...))
}

短除法手动演算（数值 999，字节 {0x03,0xE7} = 3×256+231）：

999 ÷ 62 = 16 余 7     → alphabet[7]  = '7'    （最低位）
 16 ÷ 62 = 0  余 16    → alphabet[16] = 'G'    （次低位）
余数序列（低位在前）: [7, 16] → "7G" → 反转 → [16, 7] → "G7"

解码实现（霍纳法还原）

func base62Decode(s string) (string, error) {
    // 统计前导 '0'，解码主体后补回 0x00
    lead := 0
    for lead < len(s) && s[lead] == '0' {
        lead++
    }

    x := new(big.Int)
    base := big.NewInt(62)
    // 霍纳法：从左到右 x = x*62 + 当前位数值，还原大整数
    for _, r := range s[lead:] {
        if r > 255 {   // 查表前防 rune 越界（中文/emoji 等输入）
            return "", fmt.Errorf("invalid base62 char %q", r)
        }
        v := base62DecTable[r]  // 字符 → 数码值
        if v < 0 {
            return "", fmt.Errorf("invalid base62 char %q", r)
        }
        x.Mul(x, base)
        x.Add(x, big.NewInt(int64(v)))
    }
    // 补回前导零字节，再 Bytes() 得原始字节
    prefix := make([]byte, lead)
    return string(append(prefix, x.Bytes()...)), nil
}

解码手动演算（"G7"）：

'G' → 16:  x = 0*62+16 = 16
'7' →  7:  x = 16*62+7 = 999
→ x.Bytes() = {0x03,0xE7}

base62DecTable [256]int 在 init() 里预计算：初始全 -1，然后按字符表把每个字符的下标写进去。查表 O(1) 且天然能识别非法字符，配合 r > 255 越界检查防 panic。

Base91：13/14-bit 比特流切块范式

数学思想

直接对「比特流」做 13/14-bit 分块，目标是逼近每字符 ≈ log₂91 ≈ 6.5 bit 的密度上限。

• 把输入字节按位拼进一个累加器 b，攒够 13 或 14 bit 就切成一个「两位数码组」。
• 两位数码组 v 拆成 v/91（高位码）和 v%91（低位码），各自查 91 字符表。
• 为什么必须两位一组：单字符最大数码值 = 90，而一个 13-bit 块最大 = 8191，一个字符装不下一个块，被迫用两个 91 进制数位（最大能表示 8280）才能装下。
• 选 13 还是 14：由 v & 8191 > 88 决定，88 = 8280 − 8192（来历见 3.3）。

字符表 91 个：A-Z a-z 0-9 加 30 个符号，特意避开易混淆的撇号、双引号、反斜杠等。

编码实现

func base91Encode(input []byte) string {
    var out []byte
    var b uint32   // 比特累加器
    var n int      // 累加器里已有多少有效位

    for _, byteVal := range input {
        b |= uint32(byteVal) << uint(n) // 新字节塞到累加器已有位之上（低位在前拼接）
        n += 8
        if n > 13 {
            var v uint32
            v = b & 8191              // 先取低 13 bit
            if v > 88 {
                b >>= 13              // 低13位>88 → 切 13 bit
                n -= 13
            } else {
                v = b & 16383         // 否则改用 14 bit（16383 = 2¹⁴−1）
                b >>= 14
                n -= 14
            }
            out = append(out, base91Alphabet[v%91], base91Alphabet[v/91]) // 一组 → 两个字符
        }
    }
    // 收尾：剩余 < 14 bit 也要输出，最多补两个字符
    if n > 0 {
        out = append(out, base91Alphabet[b%91])
        if n > 7 || b > 90 {
            out = append(out, base91Alphabet[b/91])
        }
    }
    return string(out)
}

88 的来历：为什么低 13 位 > 88 就退回切 13 bit

这个 88 是 Base91 里最精妙也最易错的地方，用三层推导讲清楚：

第一层：两位数码组最大能装多大？

两位 91 进制数位，高码 c1、低码 c0 都 ∈ [0, 90]，合成的组值 v = c1×91 + c0。当 c1 = c0 = 90 时取最大值：

v_max = 90×91 + 90 = 8190 + 90 = 8280

第二层：一个组必须装得下 13 bit，且最好能装 14 bit

• 13-bit 块的范围是 [0, 2¹³−1] = [0, 8191]，必须 ≤ 8280，所以装 13 bit 一定安全。
• 14-bit 块范围 [0, 2¹⁴−1] = [0, 16383]，远超过 8280，所以不可能用两位码装满 14 bit。
• 妥协方案：只有当「低 13 位的值 + 可能的第 14 位」不会超过 8280 时，才敢用 14 bit。

第三层：88 = 8280 − 8192 就是那条「额度线」

• 假设低 13 位的值是 v13，如果第 14 位（bit 13）为 1，它贡献 2¹³ = 8192。
• 两者合起来是 v13 + 8192，要求 ≤ 8280 → 推出 v13 ≤ 8280 − 8192 = 88。
• 所以：低 13 位 ≤ 88 → 即使第 14 位是 1，总价值 ≤ 8280，能塞进两位码 → 切 14 bit；低 13 位 > 88 → 第 14 位一进来就超界 → 退回切 13 bit。

把编码/解码两边写成对称的判据就是 v & 8191 > 88（编码端在切块前判断，解码端从 v 剥掉第 14 位再判断）。

解码实现（对称还原）

func base91Decode(s string) (string, error) {
    var out []byte
    var b uint32
    var n int
    v := -1   // 组内缓冲：-1 表示「等下一个字符组成两位组」

    for _, r := range s {
        if r > 255 {
            return "", fmt.Errorf("invalid base91 char %q", r)
        }
        c := base91DecTable[r]
        if c < 0 {
            return "", fmt.Errorf("invalid base91 char %q", r)
        }
        if v < 0 {
            v = c                 // 组内第一个码：先存着
        } else {
            v += c * 91           // 组内第二个码：v = 高码×91 + 低码，还原 13/14-bit 值
            b |= uint32(v) << uint(n)  // 塞回比特累加器
            if v&8191 > 88 {      // 与编码端对称：据此判断当时切的是 13 还是 14 bit
                n += 13
            } else {
                n += 14
            }
            for n > 7 {           // 攒够 8 bit 就吐出一个字节
                out = append(out, byte(b&255))
                b >>= 8
                n -= 8
            }
            v = -1                // 重置组缓冲
        }
    }
    if v > -1 {   // 收尾：可能剩一个单码，输出最后 1 字节
        out = append(out, byte((b|uint32(v)<<uint(n))&255))
    }
    return string(out), nil
}

编码先动位置、解码先处理的根本原因：编码端喂进来的是定宽 8 bit / 字节，可以确定地把 n += 8 写在前面；解码端吐出去的是不定宽 13 或 14 bit 组，必须先拼出 v、用 v&8191 > 88 判断这组到底占几 bit，才知道 n 该加多少。一个定宽、一个不定宽，顺序自然相反。

Base62 vs Base91：两种范式为何长得不一样

看了实现之后，Base 的处理都是进制位处理，本质上来说原理是一致，那么 Base62 与 Base91 的实现逻辑也是互通的，把 62 的字符表和 divmod 逻辑换成 91 进制，或把 91 的分块逻辑套到 62 上，都能做到字节无损 roundtrip——因为两者本质都是「字节 ↔ 数字 ↔ 文本」的可逆映射，范式不同只是实现策略不同。

但「能用」不等于「一样好」：Base62 用大数 divmod 天然避开「位边界」问题，但每字符密度低、输出更长；Base91 用位分块逼近密度上限、输出更短，却要求编码/解码端共享同一个 88 判据，稍不对称就解不回。实际选型看场景：想纯可读（URL、短链、文件名）用 Base 62；想尽量压缩文本长度可以用 Base 91。

边界实例：88 与 89 的鸿沟

用两个只有 1 字节差别的输入，直观展示 88 这条分界线。两个输入都是 2 字节、拼进累加器后都是 16 bit，正好在 n > 13 的切块点触发一次分块。

实例 A：输入 {0x58, 0x20} → 低 13 位 = 88 → 切 14 bit

字节低位在前拼接：b = 0x58 | (0x20 << 8) = 88 + 8192 = 8280，n = 16
v = b & 8191 = 88        → 88 > 88 不成立 → 走 14-bit 分支
v = b & 16383 = 8280     → 8280 = 90×91 + 90 → 输出 alphabet[90], alphabet[90]

实际编码结果 ""A：alphabet[90] 是双引号、alphabet[90] 又是双引号，再加收尾 1 字符 A。

实例 B：输入 {0x59, 0x20} → 低 13 位 = 89 → 切 13 bit

字节低位在前拼接：b = 0x59 | (0x20 << 8) = 89 + 8192 = 8281，n = 16
v = b & 8191 = 89        → 89 > 88 成立 → 走 13-bit 分支
v = 89                   → 89 = 0×91 + 89 → 输出 alphabet[89], alphabet[0]

实际编码结果 ~AB：alphabet[89] 是 ~、alphabet[0] 是 A，再加收尾 1 字符 B。

仅第 1 字节差 1（0x58 → 0x59），低 13 位就从 88 变 89，切块从 14 bit 退回 13 bit，输出字符完全不同——这就是 88 判据的价值：一条精确的「装不装得下」的线。

测试向量收尾

总结

Base62 和 Base91 本质是同一类东西：把任意字节串无损映射成可打印文本的编码。差别在取舍上：

• Base62 字符集只用字母数字，干净通用，适合 URL、短链接、文件名这类「要能安全贴在任何地方」的场景，代价是每字符承载的 bit 少、输出偏长；
• Base91 把字符表扩到 91 个字符，每字符承载 bit 更多、输出更短，适合尽量压缩文本长度的场景，代价是字符集不纯。

Base 编码本质遵守按场景需求进行选择，没有客观上的优劣之分。