はじめに
2022 年 11 月の初めに、OpenSSL で Severity: High の脆弱性が 2 つ修正されました。
このうち、CVE-2022-3602 の修正が if 条件式の不等号に = を加えるだけという典型的な Off-by-one error であったこともそこそこ話題になりました。プログラミングは難しい。
ファイル名から分かるように、この処理は Punycode デコーダーの一部です。Punycode といえば、非 ASCII 文字を含むホスト名を ASCII 文字に変換するときなどに使われるやつで、日本語ドメインのサイトが xn-- で始まる謎なホスト名になったりするあれです。日本人にはわりと馴染みがある技術ではないでしょうか。
Punycode の仕様は RFC3492 で公開されています。この中で出てくるサンプル文字列の多くが平成の J-pop の曲名だったりするので、日本人にはさらに馴染み易い技術です。
といっても、この RFC を書いた人は日本人ではなく、Adam Costello という当時 UC Berkeley の博士課程にいた方のようです。LinkedIn を見るとベルビュー在住。なんと近所。
名前が Punycode になった理由を 2020 年に本人に問い合わせた人がいました。要は Puny と Unicode をかけただけのようです。まあそりゃそうだろうよ。
さて、ツイッターなどで RFC3492 というキーワードで検索すると、やはり日本語のサンプル文字が日本人の心を打つのか、RFC の日本語訳を作っていたり、エンコーダー/デコーダーを各自実装したりしている日本の方が多く見受けられます。また、Wikipedia の日本語ページもなかなか充実した内容になっています。
こちらが RFC の日本語訳です。興味が出てきた方は是非ご一読ください。
RFC には、疑似言語によるエンコーダー/デコーダーの処理に加え、C によるサンプル実装のソースコードまで載っているので、エンコーダー/デコーダーを自分で実装したり、他言語に移植するのは簡単です。本文を読む必要すらありません。ではなぜ今更こんな記事を書くのかと言えば、この RFC3492、恥ずかしながら全然理解できなかったからです。Punycode という名前の音感に可愛げあって、さらに J-pop のサンプル文字なんか使っているくせに、仕様は可愛くないんですよ。より正確に言えば、数回読めばエンコード、デコードの仕組みは理解できます。しかし細かい部分で、なぜそういう発想になったのか、なぜその計算で成り立つのか、という「作者の意図」のようなものが全然読み取れず、実際にコードを書いてパラメーターを動かしてみたり、手でグラフを書いてちまちま計算するといった作業を経ることでようやくある程度の理解が可能になりました。こんな RFC をさらっと読むだけで理解できる数学的センスが欲しいものです。
というわけで本記事では、なぜこのような仕様になっているか、という点も考察しながらPunycode の完全理解を目指したいと思います。記事の性質上、部分的には RFC3492 を訳しただけの箇所も出てきますが、私が理解しやすいように説明の順番を入れ替えたり、RFC にはない説明も含めるようにしました。
あと、MathJax を使い慣れていないので、読みづらいかもしれません。あらかじめご承知おきください。
Punycode と Bootstring
そもそも Punycode とは何なのか。
RFC3492 は、厳密には一般化された Bootstring というアルゴリズムの仕様を記述したもので、Punycode はそのバリエーションの一つです。Bootstring とは、任意の Code point で構成された数列 (= Extended string) を、Basic code point で構成された数列 (= Basic string) で表現したものです。この性質を利用して、Unicode 文字列を ASCII 文字列の組み合わせで表現したものが Punycode です。
Bootstring において、Extended string を構成する Code point は非負の数であればよいため、文字列に Unicode 範囲外の Code point の文字が含まれていたとしても Punycode 変換は可能です。しかし、Punycode のパラメーターは Exntended string の Code point が Unicode、すなわち 0 から 0x10ffff の範囲であることを想定して最適化されています。
パラメーターの意味については後述しますが、Punycode における Bootstring のパラメーターは以下の通りです。これだけでも仕様の複雑さが伝わってくるのではないでしょうか。パラメーター多くない？
- base = 36
- $t_{min}$ = 1
- $t_{max}$ = 26
- skew = 38
- damp = 700
- initialBias = 72
- initialN = 128
- Basic code point = ASCII characters (0x00~0x7f)
- delimiter = '-' (U+002D)
Bootstring 仕様
適当な Extended string を例に、Bootstring のエンコード過程を見ていきましょう。具体例は 7.1 Sample strings にある日本語がよいですね。7.2 Decoding traces と 7.3 Encoding traces でも使われているサンプル L にしましょう。以下の文字列です。
- Extended string: 3年B組金八先生
- Code points (hex): [0x0033, 0x5E74, 0x0042, 0x7D44, 0x91D1, 0x516B, 0x5148, 0x751F]
- Code points (dec): [51, 24180, 66, 32068, 37329, 20843, 20808, 29983]
- Punycode: 3B-ww4c5e180e575a65lsy2b
Bootstring は、以下 4 つのテクニックを順番に使ってエンコードを行ないます。
- Basic code point segregation
- Insertion unsort coding
- Generalized variable-length integers
- Bias adaptation
Basic code point segregation
最初のステップはとても簡単です。Extended string に含まれる Basic code point を元の順番のまま抜き出して出力データの先頭に加え、さらに delimiter を出力データに加えます。delimiter は Basic code point が存在したときのみ付加します。
“3年B組金八先生” には “3” と “B" という 2 つの Basic code point が含まれているので、このステップによって以下のデータが得られます。
Basic string: 3B-
Insertion unsort coding
前のステップで 2 つの Basic code point を抜き出し、“3B” という文字列が手元にあります。Bootstring の基本的な考え方は、この文字列（もしくは入力文字列に Basic code が含まれていなかった場合は空の文字列）に対し、以下のように残された Basic code 以外の文字を適切な位置に挿入していく操作を繰り返すことで、元の文字列を再現できるようにすることです。
- U+5148 ‘先’ を 2 番目の位置へ $\Longrightarrow$ 3B先
- U+516b ‘八’ を 2 番目の位置へ $\Longrightarrow$ 3B八先
- U+5e74 ‘年’ を 1 番目の位置へ $\Longrightarrow$ 3年B八先
- U+751f ‘生’ を 5 番目の位置へ $\Longrightarrow$ 3年B八先生
- U+7d44 ‘組’ を 3 番目の位置へ $\Longrightarrow$ 3年B組八先生
- U+91d1 ‘金’ を 4 番目の位置へ $\Longrightarrow$ 3年B組金八先生
各ステップは、(Code point, Insertion position) という数値のペアの配列で表現して簡略化できます。
- (20808, 2)
- (20843, 2)
- (24180, 1)
- (29983, 5)
- (32068, 3)
- (37329, 4)
文字をどのような順番で挿入してもデコードはできますが、上の例で分かるように、Bootstring では Code point の昇順に挿入します。この理由については後述します。ここで重要なのは、“3B” という最初の文字列と、挿入文字と位置を示す数値のペアの配列が渡されれば、“3年B組金八先生” という文字にデコードできるということです。
数値のペアの配列、というのはまだ扱いにくいので、できればペアをまとめて単なる数列にしたいですね。そこで出てくるのがステートマシンとランレングス圧縮です。
ある文字列に対して $(n, i)$ という状態を持つステートマシンを想定します。ここで $n$ は挿入する文字、$i$ は挿入位置です。したがって $i$ は $0$ 以上、文字列の長さ以下の数値になります。このステートマシンの状態遷移のルールを以下のように決めます。
- $i + 1$ が文字列の長さ以下のとき: $(n, i) \Rightarrow (n, i + 1)$
- $i$ が文字列の長さに一致するとき: $(n, i) \Rightarrow (n + 1, 0)$
現在の文字列が “3B” で長さは 2 なので、仮に初期状態が (0, 0) であった場合、
(0, 0) $\Rightarrow$ (0, 1) $\Rightarrow$ (0, 2)
$\hspace{5mm}\Rightarrow$ (1, 0) $\Rightarrow$ (1, 1) $\Rightarrow$ (1, 2)
$\hspace{5mm}\Rightarrow$ (2, 0) $\Rightarrow$ (2, 1) $\Rightarrow$ (2, 2)
$\hspace{5mm}\Rightarrow\ldots$
のように状態が遷移します。ただし Bootstring では、ステートマシンの初期状態は (0, 0) ではなく、パラメーター化された (initialN, 0) となっており、前述のように Punycode では initialN = 128 なので、(128, 0) が初期状態となります。
このステートマシンの各状態において、文字を挿入するかどうかを true or false で表現したものを並べると、前述の (Code point, Insertion position) という数値のペアを true or false の配列で表現できます。さらに配列の要素は 2 種類しかなく、要素のほとんどは false であり、かつ配列の最後は必ず true になるので、連続する false の要素の個数だけを並べれば元の配列を再現できます。これがランレングス圧縮です。例えば [false, false, true, false, false, false, false, true, true, false, false, true] という配列なら [2, 4, 0, 2] と表現しても元の配列を再現できます。ランレングス圧縮後の配列の各要素を delta と呼びます。
例えば、最初のペアである (20808, 2) はステートマシンを (128, 0) から延々と動かしていけば
(128, 0): F $\Rightarrow$ (128, 1): F $\Rightarrow$ (128, 2): F
$\hspace{5mm}\Rightarrow$ (129, 0): F $\Rightarrow$ (129, 1): F $\Rightarrow$ (129, 2): F
$\hspace{5mm}\Rightarrow\ldots$
$\hspace{5mm}\Rightarrow$ (20808, 0): F $\Rightarrow$ (20808, 1): F $\Rightarrow$ (20808, 2): T
となり、false が (20808 * 3 + 2) - (128 * 3 + 0) = 62042 回続いた後でようやく最初の true、最初の挿入文字と位置を示す (20808, 2) が現れます。したがって 62042 が最初の delta になります。
2 番目の true は (20843, 2) です。このときの文字列は “3B先” であるため、文字の長さが 2 から 3 に増えていることに注意が必要です。状態遷移は
(20808, 2): T $\Rightarrow$ (20808, 3): F
$\hspace{5mm}\Rightarrow$ (20809, 0): F $\Rightarrow$ (20809, 1): F $\Rightarrow$ (20809, 2): F $\Rightarrow$ (20809, 3): F
$\hspace{5mm}\Rightarrow\ldots$
$\hspace{5mm}\Rightarrow$ (20843, 0): F $\Rightarrow$ (20843, 1): F $\Rightarrow$ (20843, 2): T
となり、(20843 * 4 + 2) - (20808 * 4 + 3) = 139 が次の delta です。
この作業を続けると、前述の (Code point, Insertion position) の配列を次のような delta の配列で表現できます。
\begin{align}
(20808, 2) &\Rightarrow (20808 \times 3 + 2) - (128 \times 3 + 0) = 62042\\
(20843, 2) &\Rightarrow (20843 \times 4 + 2) - (20808 \times 4 + 3) = 139\\
(24180, 1) &\Rightarrow (24180 \times 5 + 1) - (20843 \times 5 + 3) = 16683\\
(29983, 5) &\Rightarrow (29983 \times 6 + 5) - (24180 \times 6 + 2) = 34821\\
(32068, 3) &\Rightarrow (32068 \times 7 + 3) - (29983 \times 7 + 6) = 14592\\
(37329, 4) &\Rightarrow (37329 \times 8 + 4) - (32068 \times 8 + 4) = 42088\\
\end{align}
“3B” という文字列と、[62042, 139, 16683, 34821, 14592, 42088] という数列が与えられれば、ステートマシンを (128, 0) から動かして “3年B組金八先生” という文字列にデコードできます。といっても、実際にデコーダーを実装するときにはステートマシンを素直に何万回も動かす必要はなく、各 delta に対するそのときの文字列の長さを除数として商と剰余を取ることで、挿入する文字の Code point と位置が計算できます。文字の挿入順番を Code point の昇順にしたことで、ステートマシンの状態遷移を、値が単調増加する方向にさせる (RFC の表現を借りれば the state always advances monotonically) ことができ、delta による表現が可能になっています。
Generalized variable-length integers
最初のステップで、“3年B組金八先生” という文字列から “3B-” という文字列を抜き出し、その次のステップで残りの文字列を [62042, 139, 16683, 34821, 14592, 42088] という delta の数列に変換しました。最後のステップとして、delta の数列を Basic string に変換して “3B-” の後に連結します。これが最終的な Bootstring になります。
極端な例ですが、delta を 10 進表記のまま delimiter で区切って並べて “3B-62042-139-16683-145082-14592-42088” にするいい加減な方法でもデコード可能な文字列は得られます。16 進表記にすればもう少し短くできるかもしれません。しかし、この例のように世間で一般的に使われている 10 進表記や 16 進表記を使うと、数と数の間に delimiter が必要になってしまいます。Bootstring が採用したアイディアは、delimiter なしでも一意に区切り位置が決定されるような独自の表記法を定義し、その表記法で delta を並べるというものです。
なぜ一般的な表記法だと delimiter が必要になるかといえば、N 進表記の数の全ての桁がそれぞれ 0 から N-1 の全ての値を取り得るためです。一意に区切り位置が決定されるためには、ここに制限を加える必要があります。そこで、桁ごとに Threshold という値を定義し、最上位の桁は必ずその桁の Threshold より小さい数値になるような表記法を考えます。
さらに、Bootstring では Little-endian の表記法を採用するため、0 桁目が最下位桁 Least Significant Digit、最後の右端に来る桁が最上位桁 Most Significant Digit になります。
桁 $i$ の threshold を $t_i$ とすると、この表記法を使った base=N のときの 3 桁までの数は以下のようになります。
| 値 | 桁 0 | 桁 1 | 桁 2 |
|---|---|---|---|
| $0$ | $0$ | ||
| $1$ | $1$ | ||
| ... | ... | ||
| $t_0-1$ | $t_0-1$ | ||
| $t_0$ | $t_0$ | $0$ | |
| ... | ... | ... | |
| $X$ | $base-1$ | $0$ | |
| $X+1$ | $t_0$ | $1$ | |
| ... | ... | ... | |
| $Y$ | $base-1$ | $base-1$ | $0$ |
| $Y+1$ | $t_0$ | $t_1$ | $1$ |
Little-endian であることを除くと、通常の表記法と異なるのは次の 2 点です。
- 最上位の digit が threshold に達すると、その桁は最上位の桁になれないため、次の桁に 0 を付加する必要がある。
- ある桁の digit が base に達して繰り上がるとき、通常なら 0 にリセットされるが、0 から threshold-1 の数は最上位の桁にしかなれないため、その桁は threshold にリセットされる。
このように定義すると、各桁の重み $w_i$ が自動的に決まります。例えば表中の $X+1$ の行に着目すると、この数は base に等しいため
X+1 = t_0 + w_1 = base
という式が成り立ち、ここから
w_1 = base - t_0
という関係を導き出すことができます。
$Y$ と $Y+1$ については、次の関係式が成り立ちます。
\begin{align}
Y &= (base - 1) + (base - 1) \times w_1\\
Y + 1 &= t_0 + t_1 \times w_1 + w_2
\end{align}
ここから $Y$ を消去して $w_2$ について解くと
\begin{align}
w_2 &= (base - 1) + (base - 1) \times w_1 + 1 - t_0 - t_1 \times w_1\\
&= (base- t_1- 1) \times w_1 + (base - t_0)\\
&= (base- t_1- 1) \times w_1 + w_1 & (base - t_0 = w_1 を代入)\\
&= (base- t_1) \times w_1
\end{align}
という関係式が得られ、RFC に書かれた桁 j の重み $w_j$ が以下のようになる根拠が説明できました。
\begin{align}
w_0 &= 1\\
w_j &= w(j-1) \times (base - t_{j-1}) & (j > 0)
\end{align}
Bootstring において threshold をどうやって用意するかといえば、bias, $t_{min}$, $t_{max}$ と呼ばれるパラメーターを定めて、
t_j = \left\{\begin{array}{ll}
base \times (j + 1) - bias\\
t_{min} & (base \times (j + 1) - bias < t_{min})\\
t_{max} & (base \times (j + 1) - bias > t_{max})
\end{array}
\right.
というように定義します。Punycode におけるこれらのパラメーターを再掲します。
base = 36
$t_{min}$ = 1
$t_{max}$ = 26
initialBias = 72
Bias ではなく initialBias となっているのは、一文字エンコードするたびに bias の値を後述の “Bias adaptation” というアルゴリズムで更新していくためです。一文字目のエンコードのときに bias=72 を使います。
前のステップで得られた delta の数列は [62042, 139, 16683, 34821, 14592, 42088] でした。一文字目の 62042 を bias=72 でエンコードしてみましょう。
bias=72 の場合の threshold と weight は
\begin{align}
t &= 1, 1, 26, 26, 26, \ldots\\
w &= 1, 35, 1225, 12250, 122500, \ldots
\end{align}
となります。62042 は
62042 = 22 + 35 \times (22 + 35 \times (30 + 10 \times 2))
と書けるので、(22 22 30 2) がそれぞれの桁の digit になります。
Punycode は base=36 となっているように 36 進数です。それぞれの桁は 0 から 35 までの digit を取り得るのですが、最後にそれを
- 0 to 25 $\Rightarrow$ ‘a’ to ‘z’
- 26 to 35 $\Rightarrow$ ‘0’ to ‘9’
の文字に置き換えます。したがって (22 22 30 2) は ww4c となります。16 進数表記とは異なり、‘0’ から ‘9’ が素直に 0 から 9 に割り当てられているわけではないことに注意が必要です。‘a’ が 0 で ‘0’ は 26 です。ややこしいな。
試しに Bias を 72 に固定したまま残りの delta も同様に処理すると以下の文字列が得られます。
$62042 = 22 + 35 \times (22 + 35 \times (30 + 10 \times 2)) \Rightarrow$ (22 22 30 2) $\Rightarrow$ ww4c
$139 = 34 + 35 \times 3 \Rightarrow$ (34 3 0) $\Rightarrow$ 8da
$16683 = 23 + 35 \times (21 + 35 \times 13) \Rightarrow$ (23 21 13) $\Rightarrow$ xvn
$34821 = 31 + (35 \times (14 + 35 \times 28)) \Rightarrow$ (31 14 28 0) $\Rightarrow$ 5o2a
$14592 = 32 + (35 \times (31 + 35 \times 11)) \Rightarrow$ (32 31 11) $\Rightarrow$ 65l
$42088 = 18 + (35 \times (12 + 35 \times 34)) \Rightarrow$ (18 12 34 0) $\Rightarrow$ sm8a
結果を比べます。
3B-ww4c5e180e575a65lsy2b (Punycode)
3B-ww4c8daxvn5o2a65lsm8a (Bias=72 で固定)
結果の長さが同じになりました。あれ、Bias adaptation なんて要らないのでは・・・？
Bias adaptation
前述したとおり Bias adaptation とは、Generalized variable-length integers で使う Threshold の元となる Bias という値を、文字をエンコードするたびに更新する作業です。Bias adaptation の目的は、Bootstring をなるべく短くすることだと考えられますが、“3年B組金八先生” という文字列に関しては、Bias を 72 に固定したとしても、Bias adaptation を真面目に行なった場合と同じ長さの Punycode が得られました。Bias adaptation の存在意義が問われています。
そもそも Generalized variable-length integers の長さを短くするなら、桁の重みが常に最大、つまり Threshold を常に $t_{min}$ にすればよいのではないでしょうか。実際にやってみると、Threshold が常に 1 のときの “3年B組金八先生” の delta は
$62042 = 22 + 35 \times (22 + 35 \times (15 + 35 \times 1)) \Rightarrow$ (22 22 15 1 0) $\Rightarrow$ wwpba
$139 = 34 + 35 \times 3 \Rightarrow$ (34 3 0) $\Rightarrow$ 8da
$16683 = 23 + 35 \times (21 + 35 \times 13) \Rightarrow$ (23 21 13 0) $\Rightarrow$ xvna
$34821 = 31 + (35 \times (14 + 35 \times 28)) \Rightarrow$ (31 14 28 0) $\Rightarrow$ 5o2a
$14592 = 32 + (35 \times (31 + 35 \times 11)) \Rightarrow$ (32 31 11 0) $\Rightarrow$ 65la
$42088 = 18 + (35 \times (12 + 35 \times 34)) \Rightarrow$ (18 12 34 0) $\Rightarrow$ sm8a
と変換されます。エンコード結果を比べると
3B-ww4c5e180e575a65lsy2b (Punycode)
3B-wwpba8daxvna5o2a65lasm8a (Threshold=1 で固定)
Punycode より 3 文字長くなりました。
上の結果を見ると、各文字のエンコード結果の末尾が ‘a’ になっています。Threshold が 1 だと ‘a’、すなわち 0 以外のどの文字も最上位桁になれないためです。Threshold が小さいと、その桁が保持できる情報量が減る一方、最上位になれる digit が減るために末尾に 0 を付加する確率が高まり、余分な桁が 1 つ増えてしまうのです。この無駄を最小限に抑えるのが Bias adaptation の存在意義です。
Bias adaptation の手順は以下の通りです。
-
delta のオーバーフローを避けるため、delta を 2 で除算。ただし、これが最初の delta の場合、次以降の delta が大幅に小さくなることが予想されるため、2 の代わりにパラメーター damp で除算。
-
次回以降の delta がより長い文字列に挿入されるという事実を相殺するため、delta を delta div numpoints だけ増加。ここで numpoints は、Basic code point segregation で抜き出した文字を含めてそれまでにエンコードした文字数。
-
表現可能な最小の桁数をを予想するため、delta が ((base - $t_{min}$) * $t_{max}$) div 2 より小さくなるまで delta に対して (base - $t_{min}$) を除数とする除算を繰り返し実行。
-
Bias を次の式で決定
$bias = (base \times Step\ 3. の除算の回数) + (((base - t_{min} + 1) \times delta) \div (delta + skew))$
言葉だと分かりにくいので、RFC の 6.1 Bias adaptation function に書かれた疑似言語による実装を引用します。
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))
実装はシンプルですが、ちょっと意味が分かりませんね。特にステップ 3 と 4。
ここで bias と threshold の関係を再掲します。
t_j = \left\{\begin{array}{ll}
base \times (j + 1) - bias\\
t_{min} & (base \times (j + 1) - bias < t_{min})\\
t_{max} & (base \times (j + 1) - bias > t_{max})
\end{array}
\right.
Threshold は傾きが base の一次関数で、上限と下限がそれぞれ $t_{max}$ と $t_{min}$ に定められています。Punycode の場合 base=36, $t_{max}$=26, $t_{min}$=1 であり、傾きよりも上限と下限の差が狭く設定されています。このことから、$t_i$ はほとんどが 1 か 26 で、その間の値を取る i が 1 つ存在するかしないか、というパターンに限定されます。つまり
t_i = \left\{
\begin{array}{ll}
1 & (i=0, 1, \ldots, a-1)\\
m & (i=a, 1 < m < 26)\\
26 & (i > a)
\end{array}
\right.
を満たす $a$ が存在するか、もしくは
t_i = \left\{
\begin{array}{ll}
1 & (i=0, 1, \ldots, a-1)\\
26 & (i \geq a)
\end{array}
\right.
となります。
以上をふまえると、Bias adaptation のステップ 4 の説明の一部が解読できます。
The motivation for this procedure is that the current delta provides a hint about the likely size of the next delta, and so $t_j$ is set to $t_{max}$ for the more significant digits starting with the one expected to be last, $t_{min}$ for the less significant digits up through the one expected to be third-last, and somewhere between $t_{min}$ and $t_{max}$ for the digit expected to be second-last (balancing the hope of the expected-last digit being unnecessary against the danger of it being insufficient).
Bias adaptation が目指すのは、N 桁の数があったとして、桁 0 から N-3 までは threshold が $t_{max}$、桁 N-2 が $t_{min}$ と $t_{max}$ の間、最上位の桁 N-1 が $t_{max}$ になる bias を決めることだと書かれています。下位の桁が保持する情報量を最大にし、かつ、末尾に余分な ‘a’ を付加することを回避するためであると考えられます。
ここで、上述のステップ 3 に出てくる数は以下のように解釈できます。
$\hspace{5mm}base - t_{min}\Rightarrow$ threshold が t_{min} である桁の weight
$\hspace{5mm}(base - t_{min}) \times t_{max}\Rightarrow$ Threshold が $t_{min}$、桁 0 が 0、桁 1 が $t_{max}$ である 2 桁の数、すなわち $(0\quad t_{max})$
前述のように、下位の桁の threshold は $t_{min}$ に固定してエンコードしたいという目的があります。ステップ 3 のループの中で delta を base - $t_{min}$ で割り続けることで、delta をエンコードする際に何桁まで threshold を $t_{min}$ に固定できるか、を数えることができます。具体的には、ループする回数がその桁数になります。
それだけであれば、ループの終了条件は単純に delta > base - $t_{min}$ でいいはずです。しかし実際の条件は $((base - t_{min}) \times t_{max}) \div 2$ で、これは $(0\quad t_{max})$ という 2 桁の数の半分です。この理由が、おそらく上に引用した RFC にある balancing the hope of the expected-last digit being unnecessary against the danger of it being insufficient の部分です。商が base - $t_{min}$ 以下になるまで除算を続けると、誤差を考慮したときに最後の桁が不要になる可能性が高く、かといってループを早く止めすぎてしまうと、桁数の予想が実際の桁数よりも小さくなってしまう可能性があり、そのバランスを取っているのだと考えられます。
ステップ 3 で、delta の大きさにマッチした桁数が予測できました。この桁数から bias を算出する式がステップ 4 です。ループの回数が $l$ だったとき、$t_0$ から $t_{l-1}$ までが $t_{min}$ になり、$t_l$ が $t_{min}$ と $t_{max}$ の中間の値になるように $t$ の数列が作れる bias が欲しいところです。仮に $t_{min}$ と $t_{max}$ の中間の値を m とおくと
t_l = base \times (l + 1) - bias = m
これを変形して
bias = base \times l + (base - m)
のように bias を決めればよいことになります。
実際に計算してみます。delta = 62042 の場合
((base - t_{min}) \times t_{max}) \div 2 = 455
となるので、
\begin{align}
62042 \div 35 &= 1772 > 455\\
1772 \div 35 &= 50 \leq 455
\end{align}
となって、l=2, delta=50 です。ここで適当に m として $t_{min}$ と $t_{max}$ の中間値である 13 を選ぶと
\begin{align}
bias &= 36 \times 2 + (36 - 13) = 95\\
threshold &= [1, 1, 13, 26, 26, \ldots]
\end{align}
が得られ、狙った通りに $t_l=t_2=m=13$ となっています。これを使って 62042 をエンコードすると
$62042 = 22 + 35 \times (22 + 35 \times (27 + 23 \times 1)) \Rightarrow$ (22 22 27 1)
となり、桁数が正しく予想でき、無駄な桁を作らずに済みました。
この例では、$t_{min}$ と $t_{max}$ の中間値 m として適当に 13 を選び、bias = base * l + (base - m) という式で bias を計算しました。この式における base-m は、上位 2 桁のエンコード方法を規定することが分かります。すなわち、上の例では 62042 を 35 で 2 回除算した後の 50 という数値に対して、base-m=23 という値を weight として使うため、50=27+23*1 と分割し、62042 の上位 2 桁が (27 1) になっています。
m を固定値にしても、ほとんど場合で除算後の delta は 2 桁になってエンコード結果の長さは変わらないはずですが、delta が極端に大きい場合に m を大きく取ってしまうと、delta が 3 桁になります。逆に delta が極端に小さい場合には、m を大きく取れば delta を 1 桁にすることができます。よって、ループ後の delta の大きさに応じて bias を決めることで、より最適なエンコードが可能になりそうです。
実際に Bootstring では、Bias adaptation のステップ 4. は
bias = (base \times x) +(((base - t_{min} + 1) \times delta) \div (delta + skew))
となっており、base - m の代わりに ((base - $t_{min}$ + 1) * delta) div (delta + skew) という delta に依存する式を使っています。delta が大きくなるほど、この値は base - $t_{min}$ + 1 に近づく、つまり base-m の m を小さくすることと同様の効果が得られます。逆に delta が小さい場合には、m を大きくした場合と同様の効果が得られるようになっています。
では最後に、“3年B組金八先生” に bias adaptation を適用してみます。これは RFC の 7.3 Encoding traces でやっていることと同じです。
$bias=72, threshold=[1, 1, 26, 26, \ldots]$
$62042 = 22 + 35 \times (22 + 35 \times (30 + 10 \times 2)) \Rightarrow$ (22 22 30 2) $\Rightarrow$ ww4c
$l=0, bias=27, threshold=[9, 26, 26, \ldots]$
$139 = 31 + 27 \times 4 \Rightarrow$ (31 4) $\Rightarrow$ 5e
$l=0, bias=24, threshold=[12, 26, 26, \ldots]$
$16683 = 27 + 24 \times (34 + 10 \times (26 + 10 \times 4)) \Rightarrow$ (27 34 26 4) $\Rightarrow$ 180e
$l=1, bias=67, threshold=[1, 5, 26, 26, \ldots]$
$34821 = 31 + (35 \times (33 + 31 \times 31)) \Rightarrow$ (31 33 31 0) $\Rightarrow$ 575a
$l=2, bias=82, threshold=[1, 1, 26, 26, \ldots]$
$14592 = 32 + (35 \times (31 + 35 \times 11)) \Rightarrow$ (32 31 11) $\Rightarrow$ 65l
$l=1, bias=67, threshold=[1, 5, 26, 26, \ldots]$
$42088 = 18 + (35 \times (24 + 31 \times (28 + (10 \times 1)))) \Rightarrow$ (18 24 28 1) $\Rightarrow$ sy2b
得られる Punycode は 3B-ww4c5e180e575a65lsy2b になります。3 文字目の delta=16683 では、bias adaptation の除算ループの回数が l=0 で bias が小さめに設定されますが、もう少し bias を大きくすれば 16683 は 3 文字にエンコードできそうです。仮に最適な bias を選択できたとしても、短縮できるのは 1 文字か 2 文字なので、労力と結果が釣り合っていない気がします。
おわりに
本記事では、Punycode の仕様である RFC3492 に記載された各テクニック、Basic code point segregation、Insertion unsort coding、Generalized variable-length integers、Bias adaptation について、計算方法だけでなく、その背後にある作者の意図を推測してみました。どこまで正確に推測できたかは分かりませんが、Punycode が意外、というか不必要に複雑だということが伝われば幸いです。この RFC の Abstract は Punycode is a simple and efficient transfer encoding syntax... という文から始まります。数学的センスがある人にとってこの程度は simple なのでしょうかね。
今更 Punycode の仕様なんて理解しても何もメリットはありませんが、今後 Punycode をどこかで見かけて、そこに “a” が多く含まれていた場合に「あー、これは bias adaptation があまり上手くいっていないねー」的なことを呟けば、かなり玄人な雰囲気を醸し出せると請け合いです。お試しあれ。