Punycode 编码

DNS 最早由美国人 Jon Postel 等人设计¹，所以仅支持 ASCII 编码。但很快互联网就扩展到欧洲和世界其他地区。人们希望能够使用自己的本地语言表示 DNS 域名。但同时又必须兼容已经部署和运行的 DNS 软件系统，所以就得设计一种用 ASCII 编码来表示世界上所有不同语言文字的编码规则，这就是 Punycode 编码。我们的中文域名用的也是这种编码。这么重要的编码技术，中文互联网上几乎没有详细的资料介绍。于是只能硬啃它的 RFC 文档，今天把学习成果分享给大家。

在开始之前大家可以先体验一下这个示例。打开之后，如果你的浏览器支持国际化域名，会在地址栏显示涛叔.taoshu.in；否则会显示xn--rort31d.taoshu.in。

背景知识

Punycode 标准 RFC3402 是 2003 年发布的，到今年正好 20 年。但 Punycode 好像没有正式的中文译名。从字面上看 puny 就是短小的意思，表示世界各国文字用 Punycode 表示长度比较短小。如此说来可以把它译成『小码』或者『小短码』，但总感觉不严肃。如果按音译的话，可以考虑译成『帕尼码』。但这个『尼码』发音在中文有特殊涵意，更是不可取。所以就只能先叫 Punycode 吧。

那为什么要强调短小呢？那是因为 DNS 主要全用 UDP 协议通信。早期的互联网受设备限制， IPv4 网络中所有设备都必须支持 576 字节²的报文。再加上 IPv4 报文头可能有 20-60 字节，DNS 报文有 8 字节的头信息，所以 RFC883 要求 DNS 报文不能超过 512 字节。因为这个长度限制，而且一次 DNS 查询中可能会包含多条域名的信息，所以域名就不能取得太长，不然会超出限制。为此 RFC883 还要求域名不能超过 63 个 ASCII 字符。

因为上面的限制，所以使用 ASCII 表示全世界所有的语言文字就很有难度了。我们需要一种短小高效的编码方式，这就是最终取名为 Punycode 的原因。

那有人会说既然是新协议，而且 1983 年到 2003 年已经过了 20 年，就不能直接要求所有的 DNS 系统去掉不能超过 63 个 ASCII 字符的限制吗？甚至能不能直接让 DNS 系统改用 UTF-8 编码呢？很可惜不能。因为过去已经部署了大量的软硬件系统，我们不可能把它们全部升级一遍。如果设计一种不兼容的新编码，那么老系统将无法识别新域名，这会让 DNS 系统分裂成两个系统。没有人会接受这样的方案，只能在现有的系统上打补丁，一条道走到黑。

编码特点

除了短小之外，Punycode 还需要满足以下几点要求才能担当为全世界各种文字编码的重任：

• 完整性：可以使用 ASCII 字符表示全世界所有语言的文字
• 唯一性：同一段文字只能有一种编码表示
• 可逆性：可以根所编码后的 ASCII 字符恢复原始文字
• 有效性：编码后的内容要尽量短小，这个前文已经介绍过
• 简洁性：编解码算法要尽量简洁，实现代码要平衡可读性和运行性能
• 可读性：编码要保留原文中的 ASCII 字符³

好了，铺垫了这么多，接下来我们就看看 Punycode 是作么实现上面的目标的。

首先要选择一种统一的字符集，它要包含世界上所有的文字。显然，这个非 Unicode 莫属。 Unicode 不光包含了当今世界上在用的全部文字，就连历史上曾经出现过现在已经消亡了的文字它也收录。

Unicode

但 Unicode 只是一种字符集，它的作用是给每一个字符定下一个唯一编号，这个编号是一个 32 位的整数，也叫码点(Code Point)。显然不能直接使用四个字节来保存 Unicode，太浪费空间了。如果这样的话，域名最长不能超过 63/4 = 15 个字符。所以我们需要 Punycode 这种高效的表示方式。

除了 Punycode，Unicode 已经有很多种表示方法，也叫编码方法。使用比较多的有 UTF-8、 UTF-16和GBK18030。最早 UTF-16 用两个字节表示所有 Unicode，性能上有优势。UTF-8 和 GBK18030 都变长字节编码，长度为一到四个不等。但后来 Unicode 越来越多，两个字节不够用了，所以 UTF-16 也改成变长字节了，长度分为两个和四个字节。从这个角度来说这几种编码在性能上区别就不大了。但因为 UTF-8 有诸多好的特性，所以逐渐成为使用最广泛的编码⁴。GBK18030 是中国的国家标准，多数字字用两个字节就能表示，比 UTF-8 的三个字节要节省不少空间，所以在中国使用比较多。

但以上无论哪一种编码，其取值都超过了 ASCII 编码的范围，没办法直接用在 DNS 系统中。那能不能想办法转成 ASCII 字符表示呢？也是有的。比如在 urlencode 编码中，它使用 UTF-8 编码，然后把每个字节转换成对应的十六进制表示。比如『涛』的 UTF-8 编码是 0xE60xB60x9B，那么对应的 url 编码就是%E6%B6%9B。这种编码主要用在 URL 路径和 HTTP Header 中。因为 HTTP 协议几乎可以认为没有长度限制，所以用这种方式比较间单。但我们不妨数一数，『涛』的 UTF-8 编码只有三个字节，转成 urlencode 后长度居然达到了九个字节，还不如直接用四字节的 Unicode 码点表示呢。

压缩编码

那怎么才能高效地的编码呢？Punnycode 用了一种类似无损压缩的技术，尽量记录增量变化。假设有四个数字，分别是 100001/100002/100003/100004。每个字都很大，不管用什么编码，只要是完整记录，就会占用很多空间。但我们可以压缩一下，只有第一个 100001 使用完整编码，剩下的四个数字可以记录它们跟第一个数字的差值，也就是 2/3/4 这样需要编码的数据就大会减小。

Unicode 码点取值范围非常大，最大的 U+10FFFF 对应十进制为 1114111，超过了 110 万。但考虑到不同语文的文字都是分配到相临的区域，尤其是全世界绝大多数民族都使用字母，他们的字母表字母不会太多，而且会连续编码，相临的差值最大不会超过一百。所以使用上面说的压缩编码会大大节省空间。

但这个方案对汉字有点不公平，因为汉字实在太多，大约有一万到十万这个量级。常用字之间的差值可能有几百上千。但如果用到了非生辟字，那差值可能会达到上万，远远大于字母文字。但即便如此，也比 Unicode 最大 100 万的取值小两个数量级，也已经很不错了。

为了统一处理，Punycode 设了一个初始码点为 U+128，用来计算第一个码点的差值。这样所有的 Unicode 字符都会转换成差值，这也是为什么在 RFC 文档中称之为 delta 的原因。

36-进制

确定了编码方案，我还得定义如何映射到 ASCII 字符。DNS 规定域名中只能使用字母、数字和连字符。我们因为要同时保存 ASCII 字符和其他语言的字符，所以需要一个分割符来区分，用连字符分割最为合适。那么剩下能用的只能是字母和数字了，加起来一共 36 个。所以我样可以用 36 进制来表示前面说的码点差值。用 a-z 表示 0-25，用 0-9 表示 26-35。比如十进制的 10240 换成 36 进制就是 $7*1296 + 32*36 + 16$，也就是 g6p，是不是非常短小了。这样我们就把码点的差值转成了对应 ASCII 字符。

坐标位置

除了保存码点差值外，我们还需要保存特符字符出现的位置，不然没办法反解。这是 Punycode 比较让人费解的地方，也算是比较精巧的地方。如果要我设计，我会直接用码点增量和出现位置两个数字来表示。位置范围最多也就 63，不会太大。但这样在解码的时候就要依次提取两个数字才能恢复。可能是设计者觉得有点麻烦，于是他们决定用一个数字同时保存码点差值和出现位置。那怎么做呢？假设差值为 delta，当前已经有 n 个字符完成编码。那么接下肯定有 n + 1 字符会被编码，它的位置只能是0-n。为此编码后的数字表示为$delta * (n+1) + i$。这个数字必然落在 $delta*(n+1)$ 到 $delta*(n+1)$ 区间内，前开后闭。反解的时候先到对应的数字 $N$，然后通过 $N$ 获得对应的码点增量$delta$，再跟上一轮的码点相加获得当前的码点，最后通过 $N / (n+1)$ 获得该码点在当前已经解码的字符中的位置，然后插入就好。

现在总结一下。Punycode 编码的对象是一串 Unicode 字符，也就是四字节的码点。Punycode 会根所码点从小到大依次计算当前码点跟上一个码点的差值$delta$，然后根据当前码点在原码点中出现的位置$i$，共同计算一个新的 $delta = delta * (n+1) + i$。最后将该值转换成 36 进制并用 ASCII 字符来表示。

以『涛叔』为例，它的 Unicode 码点依次为 28059(U+6D9B) 和 21460(U+53D4)。Punycode 会先处理『叔』，因为它的码点比较小。先计算码点增量$21460 - 128 = 21332$，此时还没有编码过的字符，所以对应的$n+1=1$，而『叔』在原序列中的位置是一，所以最后的偏移量是 $21332 * 1 + 1 = 21333$ 即 $16 * 1296 + 16 * 36 + 21$ 也就是$qqv$。下一个码点偏移量为 $28059 - 21460 = 6599$，此时 $n+1=2$，『涛』的位置是零，所以最后的偏移量是 $6599*2 +0=13198$即$10*1296+6*36+22$，对应$kgw$。

数字编界

那到现在解决所有的问题了吗？并没有。通过前面的步骤，我们得到了一系列 36 进制的数字，而且长度还比较短，这确实不错。但如果我们直接把这些数字连接起来，就会带来新的问题。以涛叔为例，它对应的编码为$qqvkgw$，那它到底是表示$qqv kgw$还是表示$qq vkgw$呢？分不清楚。有读者可能会立即说给数字之间加分割符不就可以了。确实可以，但会增加编码长度，不可取。

为了解决这个问题，Punycode 使用了所谓的通用变长整数(GVI)⁵。简单来说它给每一位都设了一个阈值$t(i)$，每一位的的权重通过如下递推公式计算：

w(0) = 1
w(j) = w(j-1) * (base - t(j-1)) for j > 0

这里的 base 就是前面说的 32。有了权重，就可以计算最终取值，分别是每一位上的数字乘以对应的权重然后相加。将普通的 32 进制数字转换成 GVI 也很简单，从低位到高位，依将计算

while N > t
  i = t + ((N - t) mod (base - t))
  N = (N - t) div (base - t)

这种 GVI 有一个特点，它的最高位上的数一定小于对应的阈值。这样我们只需要根所这个条件就能找到相邻现个数字的边界，而不需要插入额外的分割符，从而避免浪费宝贵的空间。

现在举个例子。为了方便计算，我们用小端顺序记录数字，也就是先写低位再写高位。比如有一组八进制数字为 734251…，假设每一位对应的阈值是 2, 3, 5, 5, 5, 5…。那么前几位的权重分别是 $1$, $1*(8-2)=6$, $6*(8-3)=30$, $30*(8-5)=90$, $90*(8-5)=270$，等等。现在我们开始取数字。7 对应的阈值为 2，不比它小，继续。3对应阈值为3，不比它小，继续。 4对应5，小于阈值，所以第一个数字是734，它表示$7*1+3*6+4*30=145$。注意，这里的阈值是针对数字的每一位而言的。比如我们接下来继续取数。2对应2，不比它小，继续。5对应3，继续。1对应5，小于阈值，所以第二个数字是251，它表示$2*1+5*6+1*30=60$。

生成阈值

利用 GVI 可以在不插入额外分割符的情况下识别出相临数字的边界。但这需要我们找一组阈值。阈值怎么定才好呢？说实话这部我没完全弄明白，现在也尽量说一下自己的理解。

Punycode 使用如下公式计算阈值：

t(j) = base * (j + 1) - bias

这里j表示第几位数字，bias 通过特殊的算法生成。而且阈值还设置了上限 tmax 和 下限 tmin，只能取两者之间的值。

这个 bias 偏移量的取值就很迷了，没太明白。算法如下：

let delta = delta div 2
let delta = delta + (delta div numpoints)

while delta > ((base - tmin) * tmax) div 2
    do let delta = delta div (base - tmin)

let bias = (base * the number of divisions performed in step 3) +
           (((base - tmin + 1) * delta) div (delta + skew))

研究了很长时间也没完全弄明白。这里面有一个新的常量 skew，然后只有一个变量 delta。从定性的角度来看，Punycode 每编码一个码点，会调整下次用的偏移量。主要思想是根据当前的码点来预测下一个码点，然后估计要用多少位来表示，然后减去对的 base 偏移。

如果不做任何调整，默认的阈值序列是：

1 1 26 26 ...

如果当前码点很大，算法会预测后续的码点也能也很大，所以会返回一个比较大的偏移量，然后会根据t(j) = base * (j+1) - bias计算出比较多的比较小的阈值。也就是说左边为 1的部分会右移。理论上阈值越小，该位的利用率也就越高，最终编码的结果会较小。如果当前码点很小，算法会预测后续码点同样较小，所以右边为26的部分会左移。

因为有这个调整，所以比较小的码点差值（字母或者前后相同的码点）通常用一两位就能表示，比较大的码点差值（比如存在多个汉字的情形）一般用四到五位也就够了。所以 Punycode 编码长度通常是 Unicode 码点长度的两倍左右，已经是非常高效了。

完整算法

算法常量

最后补充一下 Punycode 使用的各常量及其取值：

base         = 36          # 进制基数
tmin         = 1           # 阈值下限
tmax         = 26          # 阈值上限
skew         = 38          # 对殊值，计算 bias 用
damp         = 700         # 初次预测下一个码点的调整因子
initial_bias = 72          # 初始阈值偏移
initial_n    = 128 = 0x80  # 初始码点，用于计算码点差值

算法要求以上常量还得满足以下关系：

0 <= tmin <= tmax <= base-1
skew >= 1
damp >= 2
initial_bias mod base <= base - tmin

只要满足上述关系，调整各常量的取值只会影响编码效率，不会产生错误编码。这些常量也是研究人员通过各种测试获得了经验值。

偏移算法

function adapt(delta,numpoints,firsttime):
     if firsttime then let delta = delta div damp
     else let delta = delta div 2
     let delta = delta + (delta div numpoints)
     let k = 0
     while delta > ((base - tmin) * tmax) div 2 do begin
       let delta = delta div (base - tmin)
       let k = k + base
     end
     return k + (((base - tmin + 1) * delta) div (delta + skew))

编码算法

let n = initial_n
let delta = 0
let bias = initial_bias
let h = b = 原字符串中 ASCII 字符的长度 + 1

将 ASCII 字符复制到 output 中并添加分割符

while h < length(input) do begin
  let m = input 中 >= n 的最小的码点
  # 在 delta 中保存码点差值
  let delta = delta + (m - n) * (h + 1), fail on overflow
  let n = m
  for input 中的的所有码点，从小到大依次处理 do begin
    # 只记录比当前码点小的码点
    if c < n then ++delta, fail on overflow
    # 处理与当前码点相同的码点
    if c == n then begin
      let q = delta
      # 将 delta 转换成 36 进制并输出
      for k = base ;; k += base do begin
        # 确定阈值
        let t = tmin if k <= bias , or
                tmax if k >= bias + tmax, or k - bias otherwise
        # 找到最高位数字边界
        if q < t then break
        # 输出每一位的数字
        output the code point for digit t + ((q - t) mod (base - t))
        # 准备计算下一位数字
        let q = (q - t) div (base - t)
      end
      # 输出最后一位数字（最高位）
      output the code point for digit q
      # 为下一轮调整阈值偏移
      let bias = adapt(delta, h + 1, h == b)
      # 处理下一个相同的码点，需要置零
      let delta = 0
      h++
    end
  end
  increment delta and n
end

解码算法

let n = initial_n
let i = 0
let bias = initial_bias
let output = 空字符串

找到最后一个分割符，把它之前的 ASCII 字符直接复制到 output

while 直到所有 input 都被处理 do begin
  let oldi = i
  let w = 1
  # 找到下一个数字边界并转换成十进制数
  for k = base ;; b += base do begin
    # 读取一位
    let digit = the code point's digit-value, fail if it has none
    # 累加权重
    let i = i + digit * w, fail on overflow
    # 计算阈值
    let t = tmin if k <= bias, or
            tmax if k >= bias + tmax, or k - bias otherwise
    # 找到数字最高位
    if digit < t then break
    # 计算下一位权重
    let w = w * (base - t), fail on overflow
  end
  # 为下一个码点调整阈值偏移量
  let bias = adapt(i - oldi, length(output) + 1, oldi == 0)
  # 计算实际 Unicode 码点
  let n = n + i div (length(output) + 1), fail on overflow
  # 确定码点在位置
  let i = i mod (length(output) + 1)
  # 插入解析的码点
  insert n into output at position i
  i++
end

总结

以上就是 Punycode 编码的核以思想。本文不打算逐行分析代码，而是希望通过分析 Punycode 编码的核心思想来帮助大家快速理解代码实现。我这里推荐阅读 Go 语言 IDNA 包提供的 Punycode 实现⁶，一共才二百行多一点，短小精悍。最后提一句，域名中用点分割的部分叫标签。比中taoshu.in中taoshu和in是两个标签。每个标签都可以使用 Punycode 编码，但需要添加统一的前缀xn--。假设域名叫涛叔.示例，那对应的 Punycode 实际为xn--rort31d.xn--fsq092h。如果客户端支持，就会显示为涛叔.示例，不支持则会显示原始的 Punycode 编码。看起来像是乱码。