Punycode 编码

2023-07-01 ⏳11.2分钟(4.5千字) g

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

背景知识

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

那为什么要强调短小呢?那是因为 DNS 主要全用 UDP 协议通信。早期的互联网受设备限制, IPv4 网络中所有设备都必须支持 576 字节2的报文。再加上 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 还需要满足以下几点要求才能担当为全世界各种文字编码的重任:

好了,铺垫了这么多,接下来我们就看看 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 有诸多好的特性,所以逐渐成为使用最广泛的编码4。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+167*1296 + 32*36 + 16,也就是 g6p,是不是非常短小了。这样我们就把码点的差值转成了对应 ASCII 字符。

坐标位置

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

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

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

数字编界

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

为了解决这个问题,Punycode 使用了所谓的通用变长整数(GVI)5。简单来说它给每一位都设了一个阈值t(i)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…。那么前几位的权重分别是 11, 1*(8−2)=61*(8-2)=6, 6*(8−3)=306*(8-3)=30, 30*(8−5)=9030*(8-5)=90, 90*(8−5)=27090*(8-5)=270,等等。现在我们开始取数字。7 对应的阈值为 2,不比它小,继续。3对应阈值为3,不比它小,继续。 4对应5,小于阈值,所以第一个数字是734,它表示7*1+3*6+4*30=1457*1+3*6+4*30=145。注意,这里的阈值是针对数字的每一位而言的。比如我们接下来继续取数。2对应2,不比它小,继续。5对应3,继续。1对应5,小于阈值,所以第二个数字是251,它表示2*1+5*6+1*30=602*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 实现6,一共才二百行多一点,短小精悍。最后提一句,域名中用点分割的部分叫标签。比中taoshu.in中taoshu和in是两个标签。每个标签都可以使用 Punycode 编码,但需要添加统一的前缀xn--。假设域名叫涛叔.示例,那对应的 Punycode 实际为xn--rort31d.xn--fsq092h。如果客户端支持,就会显示为涛叔.示例,不支持则会显示原始的 Punycode 编码。看起来像是乱码。