[1] [DFN[[[Bootstring]]]] は、小さな (少ない) [[符号位置]]の[[集合]]によってより大きな[[集合]]の[[文字列]]を表現するための[RUBY[[[算法]]][アルゴリズム]]です [SRC[>>2]]。
[[Bootstring]] の[[引数]]を特定の値に固定した[RUBY[[[実現値]]][インスタンス]] ([[プロファイル]])
として [[Punycode]] があり、 [[IDNA]] で[[国際化ドメイン名]]のために使われています。

* 仕様書

- [2] [CITE@en[RFC 3492 - Punycode: A Bootstring encoding of Unicode for Internationalized Domain Names in Applications (IDNA)]] 
<http://tools.ietf.org/html/rfc3492>

* 性質

[3] [[Bootstring]] は次の性質を持つように設計されています [SRC[>>2 1.1]]。

- [4] [RUBYB[[[完全性]]]@en[completeness]]:
あらゆる[RUBYB[[[拡張文字列]]]@en[extended string]] (任意の[[符号位置]]の列) は、
[RUBYB[[[基本文字列]]]@en[basic string]] ([RUBYB[[[基本符号位置]]]@en[basic code point]]の列)
によって表現できます。
- [5] [RUBYB[[[固有性]]]@en[uniqueness]]: ある[[拡張文字列]]を表現する[[基本文字列]]は、
高々1つしか存在しません。
- [6] [RUBYB[[[可逆性]]]@en[reversibility]]: [[拡張文字列]]を[[基本文字列]]に[[写像]]できたとすると、
その[[基本文字列]]から元の[[拡張文字列]]に再変換することができます。
- [7] [RUBYB[[[効率的符号化]]]@en[efficient encoding]]: [[基本文字列]]の長さと[[拡張文字列]]の長さの[[比]]は小さいです。
- [8] [RUBYB[[[単純性]]]@en[simplicity]]: [[符号化]]と[[復号]]の[[算法]]は十分単純です。
-- [10] [[効率性]]と[[単純性]]は必ずしも両立しませんが、 [[Bootstring]] 
は両者のバランスがとれたものを目指しています。
- [9] [RUBYB[[[可読性]]]@en[readability]]: [[拡張文字列]]中の[[基本符号位置]]は、
[[基本文字列]]中にそのまま出てきます。
-- [11] といってもその主目的は[[効率性]]なのですが。

* 基本符号位置分居

** 符号化

[13] [[拡張文字列]]を [[Bootstring]] で[[符号化]]する時には、
[[基本符号位置]]はすべて元々の順序でそのまま[[基本文字列]]の先頭に含めます。
[SRC[>>2 3.1]]

[14] [[基本符号位置]]を並べた後には[[区切子]]を置きます。
([[基本符号位置]]がまったく無いときは[[区切子]]は含めません。)
[[区切子]]は特定の[[基本符号位置]]とし、[[基本文字列]]のその後の部分には使わないものとします。
[SRC[>>2 3.1]]

[17] これを[DFN[[RUBYB[基本符号位置分居]@en[basic code point segregation]]]]と呼びます。

** 復号

[15] [[復号器]]は、[[基本文字列]]中の最後の[[区切子]]を探すことにより、
どこまでが[[基本符号位置]]を並べたものでどこからが非[[基本符号位置]]を表すものか判断できます。
[SRC[>>2 3.1]]

** 例

[16] [[Punycode]] での例: 「abcあいうえおxyz」は、
[PRE(code)[
abcxyz-k43eqasuw
]PRE]
... となります。[[基本符号位置]]で表せる部分が「abcxyz」で、
その後に[[区切子]]として「[CODE(char)[[[-]]]]」が挟まり、
最後に「あいうえお」を[[符号化]]した文字列が続きます。

* 挿入非整列符号化

[18] [[基本符号位置]]と [CODE(char)[[[-]]]] を取って残った部分は非[[基本符号位置]]を表しています。
これは[[一般化可変長整数]]を使った[[非負整数]]として表された[[差分]]の列となっています。
[SRC[>>2 3.2]]

[19] [[復号器]]の仕事は[[基本符号位置]]の列にこの[[差分]]の列を適用して元の[[拡張文字列]]に戻すことであり、
[[符号化器]]の仕事はそうなるような[[差分]]の列を生成することとなります。

[20] この符号化の方式は[DFN[[RUBYB[[[挿入非整列符号化]]]@en[insertion unsort coding]]]]と呼ばれています。

** 復号

[21] [[復号]]の手順をおおまかに表すと次のようになります [SRC[>>2 3.2]]。
= まず、[[基本文字列]]の最初の[[基本符号位置]]の部分を取り出します。
= 次に、[[区切子]]の後の[[差分]]の列から[[差分]]を1つずつ取出し、それを適用します。[[差分]]1つに対して1つの非[[基本符号位置]]が挿入されることになります。
=- [[差分]]の列は、「先へと進む回数を表す値」と「挿入する[[符号位置]]を表す値」が交互に繰り返される[RUBYB[[[連長符号化]]]@en[run-length encoding]]になっています。
=- [[基本符号位置]]が挿入されるとしたら、それは[[誤り]]です。

* 一般化可変長整数

[22] [[差分]]は[[整数]]の列として表されるのですが、通常の[[整数]]だと、
- 先頭に「0」を付けると同じ[[整数]]を表す別の[[文字列]]が作れてしまう
- 複数の[[整数]]を並べると (1つの[[整数]]の[[桁数]]の情報が別途与えられないと) どこで区切られるかわからない

... といった問題があるため、[[Bootstring]] ではこれらの問題を解消した[DFN[[RUBYB[一般化可変長整数]@en[generalized variable-length integers]]]]を使います。 [SRC[>>2 3.3]]

- [23] [[数字]]としては [CODE(math)[0]] ... [CODE(math)[[VAR@en[base]] - 1]] を使います。 [SRC[>>2 3.3]]
- [24] [[閾値]] [CODE(math)[[VAR[t]] ([VAR[j]])]] を使います。 [SRC[>>2 3.3]]
-- 一番上の桁が [VAR[j]] 番目とすると、その桁だけが [CODE(math)[[VAR[digit[SUB[[VAR[j]]]]]] < [VAR[t]] ([VAR[j]])]] を満たすとします。 [SRC[>>2 3.3]]
--- 続きがもうない桁 [VAR[j]] では [CODE(math)[0]] ... [CODE(math)[[VAR[t]] ([VAR[j]]) - 1]] を使います。
--- 続きがまだある桁 [VAR[j]] では [CODE(math)[[VAR[t]] ([VAR[j]])]] ... [CODE(math)[[VAR@en[base]] - 1]] を使います。
- [25] この[[数字列]]によって表される値は、次の [CODE(math)[[VAR[w]] ([VAR[j]])]] を使って [CODE(math)[Σ[VAR[j]] [VAR[digit[SUB[[VAR[j]]]]]] × [VAR[w]] ([VAR[j]])]] で得られる値です。 [SRC[>>2 3.3]]
-- [CODE(math)[[VAR[w]] (0) = 1]] [SRC[>>2 3.3]]
--- つまり、一番下の[[桁]]については、重みは 1 であり、表される値はその[[数字]]の値と同じです。
-- [CODE(math)[[VAR[w]] ([VAR[j]]) = [VAR[w]] ([VAR[j]] - 1) × ([VAR[base]] - [VAR[t]] ([VAR[j]] - 1))]] [SRC[>>2 3.3]]
--- それより上の[[桁]]については、重みは一つ下の[[桁]]の重みと一つ下の[[桁]]で続きがまだある[[桁]]に使える[[数字]]の個数の[[積]]です。
--- ここで [CODE(math)[[VAR[t]] ([VAR[j]] - 1) = 0]] だったとすると、通常の[[整数]]と同じになります。 (もちろん、その場合 >>24 の「続きがもうない桁」が該当無しになり、続きがあるかどうかは判定できなくなります。

[49] [[Bootstring]] では[[小エンディアン]]を使います [SRC[>>2 3.3]]。つまり、
一番下の[[桁]]が最初に来て、一番上の[[桁]] ([[閾値]]よりも小さな[[桁]])
が最後に来ます。

[48] [CODE(math)[[VAR[t]] ([VAR[j]])]] をどう決めても、
任意の[[非負整数]]の値について[[一般化可変長整数]]がちょうど1つだけ存在します。
[SRC[>>2 3.3]]

[50] 実際には [CODE(math)[[VAR[t]] ([VAR[j]])]] は
- [51] [CODE(math)[[VAR[t]] ([VAR[j]]) = [VAR[base]] × ([VAR[j]] + 1) - [VAR[bias]]]]
- [52] ただし [VAR[t[SUB[min]]]] より小さな値とはしない
- [53] ただし [VAR[t[SUB[max]]]] より大きな値とはしない
- [54] [VAR[base]], [VAR[t[SUB[min]]]], [VAR[t[SUB[max]]]] は[[定数]]
- [55] [VAR[bias]] は[[状態変数]] (>>56)

... と定義します。 [SRC[>>2 3.3]]

** 符号化

[37] [[符号化]]、つまりある値を[[一般化可変長整数]]で表現するには、次のようにします
[SRC[>>2 3.3]]。

= [38] [[符号化]]する値を [VAR[N]] とします。
= [41] [VAR[t]] を [CODE(math)[[VAR[t]] (0)]] とします。
= [39] [VAR[N]] が [VAR[t]] よりも小さければ、 [VAR[N]] を表す[[数字]]を出力し、停止します。ここまでに出力した[[文字列]]が[[符号化]]した結果です。
= [42] そうでなければ、
== [43] [CODE(math)[[VAR[t]] + (([VAR[N]] - [VAR[t]]) mod ([VAR[base]] - [VAR[t]]))]] を表す[[数字]]を出力します。
== [46] [VAR[N]] を [CODE(math)[([VAR[N]] - [VAR[t]]) div ([VAR[base]] - [VAR[t]])]] とします。
== [44] [VAR[t]] を次の桁の[[閾値]]とします。
== [45] >>39 に戻ります。

[47] つまり、最後の桁では表したい値そのものに対応する[[数字]] ([[閾値]]よりも小さな値)
を使って表し、それ以外の桁では[[閾値]]よりも小さな[[数字]]を除いた残った[[数字]]だけで
(通常の[[整数]]のように) 表そうとしたときに使う[[数字]]を使って表す、ということになります。

** 復号

[26] [[復号]]、つまり[[一般化可変長整数]]の表す値の計算の方法は、 >>25 から自然に定まります。

[28] [SRC[>>2 3.3]]
= [27] [VAR[N]] を 0 とします。
= [29] [VAR[w]] を 1 とします。
= [40] [VAR[t]] を [CODE(math)[[VAR[t]] (0)]] とします。
= [30] [VAR[d]] を次の[[数字]]とします。
= [31] [VAR[d]] と [VAR[w]] の[[積]]を [VAR[N]] に足します。
= [32] [VAR[d]] が [VAR[t]] よりも小さければ、[[停止]]します。 [VAR[N]] が[[復号]]結果の値です。
= [33] そうでなければ、
== [34] [VAR[w]] に [VAR[base]] から [VAR[t]] を引いた値を掛けます。
== [35] [VAR[t]] を次の桁の[[閾値]]とします。
== [36] >>30 に戻ります。

* 偏差適応

[56] [VAR[bias]] (>>55) は、[DFN[[RUBYB[偏差適応]@en[bias adaptation]]]]によって、
一つ前の[[差分]]の値に依存して決定します。
具体的には、前の[[差分]]の後、次の[[差分]]の処理の前に、次のように計算します [SRC[>>2 3.4]]。

= [60] [VAR[delta]] を[[差分]]とします。
= [57] >>58 での[[桁溢れ]]を防ぐために [VAR[delta]] を[[整数除算]]します。 [SRC[>>2 3.4]]
=- 最初の[[差分]]であるなら、[[定数]] [VAR[damp]] で割ります。 [SRC[>>2 3.4]]
=- 2つ目以降の[[差分]]であるなら、2 で割ります。 [SRC[>>2 3.4]]
=- 通常1つ目の[[差分]]よりも2つ目の[[差分]]の方が小さいため、こうしています。 [SRC[>>2 3.4]]
= [58] [VAR[delta]] に、そこまでに[[符号化]]または[[復号]]する[[文字列]] [WEAK[(その[[差分]]に対応する[[符号位置]]や[[基本符号位置]]もすべて含みます。)]] の長さによって[[差分]]を[[整数除算]]した結果を足し合わせます。 [SRC[>>2 3.4]]
=- 次の[[差分]]はより長い文字列に挿入されることとなるので、こうしています。 [SRC[>>2 3.4]]
=- つまり、文字列の長さに対する[[差分]]の長さの割合を [VAR[delta]] に足すことになります。
= [59] [VAR[delta]] を[[閾値]]の範囲に収まるまで割り続けます。 [SRC[>>2 3.4]]
=- これは次の[[差分]]を表現するのに必要な[[数字]]の最小の個数を予想するものとなります。 [SRC[>>2 3.4]]
=- 具体的には、 [CODE[while delta > ((base - tmin) * tmax) div 2 do let delta = delta div (base - tmin)]] とします。 [SRC[>>2 3.4]]
=- [VAR[base]] から [VAR[t[SUB[min]]]] を引くと、続きがまだあることを表す[[数字]]が最も多いときの個数となります。
=- [VAR[t[SUB[max]]]] は続きがもうないことを表す[[数字]]が最も多いときの個数となります。
=- ループの条件部の [CODE(math)[([VAR[base]] - [VAR[t[SUB[min]]]]) × [VAR[t[SUB[max]]]])]] では、まだ続く数字の個数ともう続かない数字の個数をかけているので、ちょうど2桁で表せる最大の値を求めていることになります。
=- つまり、このループで [VAR[delta]] を[[整数除算]]した回数が、続きがまだある[[数字]]を最も多く取った時
[WEAK[([VAR[t[SUB[min]]]] を[[閾値]]としたとき)]] の桁数になります。
= [61] [VAR[bias]] は、 >>59 で除算した回数と [VAR[base]] の[[積]]に対して、
[CODE[((base - tmin + 1) * delta) div (delta + skew)]] を足した値とします。 [SRC[>>2 3.4]]
=- 現在の[[差分]]は次の[[差分]]の長さのヒントであり、それによって
[CODE(math)[[VAR[t]] ([VAR[j]])]] は最後になると期待される[[桁]]から上の方の[[桁]]は [VAR[t[SUB[max]]]] に、
最後になると期待される[[桁]]の前の前までの[[桁]]ほ [VAR[t[SUB[min]]]] に、
最後になると期待される[[桁]]の手前の[[桁]]はその中間となるよう、こうしています。
(最後になると期待される[[桁]]が実際には不要であるとの期待と実際にはもっと長くなる危険性とのバランスでそうしています。) [SRC[>>2 3.4]]

** 擬似コード

[195] 次の[[擬似コード]]は、 >>2 6.1 に注釈を入れたものです。

[196] 
[PRE(code)[
 function adapt(delta,numpoints,firsttime):
     if firsttime then let delta = delta div damp
     else let delta = delta div 2
]PRE]

- [199] 初回実行であれば[[引数]]の [VAR[damp]] を、そうでなければ 2 を使って [VAR[delta]] を割ります。
-- [200] これは[[桁溢れ]]を防止するためです。 (>>56)
-- [209] 1つ目の[[符号位置]]は最初の [VAR[n]] ([[Punycode]] では [VAR[0x80]]) からの[[差分]]が [VAR[delta]] に反映されているので、通常は大きな値になります。2つ目以降では [WEAK[(同じ[[書字方式]]の[[文字]]は近い[[符号位置]]を持つ可能性が高いという性質を仮定すると)]] 小さな値となります。

[198] 
[PRE(code)[
     let delta = delta + (delta div numpoints)
]PRE]

- [210] [VAR[numpoints]] は処理済みの[[符号位置]]の数です。 [VAR[delta]] は前の[[符号位置]]から今回の[[符号位置]]までの値の差に処理済みの[[符号位置]]の数を掛けている (>>78) ので、ここで足している値はその値の差を何分の一かにしたもの (>>199) といえます。
-- [211] [[符号位置]]は後から出てくるものほど文字列のより後ろの方へと挿入されて [VAR[delta]] が大きくなる傾向にあるので (>>128 参照)、その補正のために足しています。

[201] 
[PRE(code)[
     let k = 0
     while delta > ((base - tmin) * tmax) div 2 do begin
       let delta = delta div (base - tmin)
       let k = k + base
     end
]PRE]

- [213] [VAR[delta]] をできるだけ割ります。
- [214] [VAR[base]] から [VAR[t[SUB[min]]]] を引いた数は、[[閾値]] [VAR[t]] をもっとも小さくし、できるだけ次の[[桁]]に続くことを意味する[[数字]]を増やした時の次に続く[[数字]]の個数を表しています。
- [215] そのたびに [VAR[k]] に [VAR[base]] を足していっているので、 [VAR[k]] は[[数字]]の述べ個数になります。
-- [216] このあたりは >>157 のループに対応しています。
- [217] ループ条件にある [CODE(math)[([VAR[base]] - [VAR[t[VAR[min]]]]) × [VAR[t[SUB[max]]]]]] は、
-- [218] 前半は >>214 と同じです。
-- [219] [VAR[t[SUB[max]]]] は[[閾値]] [VAR[t]] をもっとも大きくし、できるだけ次の[[桁]]に続かないことを意味する[[数字]]を増やしたときの次に続かない[[数字]]の個数を表しています。
-- [220] それらの[[積]]ですから、この[[桁]]はまだ続き、次の[[桁]]で最後であるとしたときに表せる値の個数になります。

[212] 
[PRE(code)[
     return k + (((base - tmin + 1) * delta) div (delta + skew))
]PRE]

- [221] >>201 で [VAR[delta]] を何度も割っているので、ここでの [VAR[delta]] は最後の2[[桁]]相当の値になっています。

* 引数の制約

[62] [[Bootstring]] の[[引数]]には、次の制約があります [SRC[>>2 4.]]。
- [63] [[基本符号位置]]のうちの1つは[[区切子]]とする必要があります。 [SRC[>>2 4.]]
- [64] [VAR@en[base]] を残った[[基本符号位置]]の数より大きくはできません。 [SRC[>>2 4.]]
- [65] [[区切子]]以外の[[基本符号位置]]に対して 0 ... [CODE(math)[[VAR[base]] - 1]] の[[数字]]の値を割り当てる必要があります。 [SRC[>>2 4.]]
-- [66] [[大文字]]と[[小文字]]のように、複数の[[符号位置]]が同じ値を持っても構いません。 [SRC[>>2 4.]]
-- [72] [[大文字・小文字混合注釈]]を使いたい場合、 0 ... [CODE(math)[[VAR[t[SUB[max]]]] - 1]] のすべての値について[[大文字]]と[[小文字]]が必要です。 [SRC[>>2 4.]]
- [67] [VAR[initial[SUB[[VAR[n]]]]]] は[[拡張文字列]]に現れる最小の非[[基本符号位置]]より大きな値にはできません。 [SRC[>>2 4.]]
-- [149] >>94 での処理がこの初期値からはじまるので、これより小さな非[[基本符号位置]]が存在すると、取りこぼしておかしな結果になってしまいます。
- [68] [CODE(math)[0 ≦ [VAR[t[SUB[min]]]] ≦ [VAR[t[SUB[max]]]] ≦ [VAR[base]] - 1]] [SRC[>>2 4.]]
- [69] [CODE(math)[1 ≦ [VAR[skew]]]] [SRC[>>2 4.]]
- [70] [CODE(math)[1 ≦ [VAR[damp]]]] [SRC[>>2 4.]]
- [71] [CODE(math)[[VAR[initial[SUB[bias]]]] mod [VAR[base]] ≦ [VAR[base]] - [VAR[t[SUB[min]]]]]] [SRC[>>2 4.]]

* 符号化

[73] 次に示すのは、 >>2 6.3 に示された[[擬似コード]]による [[Bootstring]] の[[符号化]]の実装に適宜注釈を入れたものです。

[110] 
[PRE(code)[
   let n = initial_n
]PRE]

- [111] [VAR[n]] は、次に処理するべき非[[基本符号位置]]は [VAR[n]] [[以上]]で最小のものである、というような値を保持する[[変数]]です。
-- [112] [[Punycode]] では [VAR[initial[SUB[[VAR[n]]]]]] は [[0x80]] です。 [[0x00]] ... [[0x7F]] はすべて[[基本符号位置]]であるため、最初に処理するべき非[[基本符号位置]]として最小足り得る [[0x80]] に設定されています。

[109] 
[PRE(code)[
   let delta = 0
]PRE]

- [141] [VAR[delta]] は非[[基本符号位置]]の[[符号化]]に直接関わる値です。
- [142] ここでは初期値を設定しているだけです。 >>78 で[[符号化]]される値が決定します。
- [143] 他に >>128 と >>119 でも値が変化します。

[140] 
[PRE(code)[
   let bias = initial_bias
]PRE]

- [202] [[閾値]]の決定 (>>153) に使う偏差の初期値を設定しています。
- [203] >>104 で前の [VAR[delta]] に基づき次の [VAR[delta]] のための [VAR[bias]] を決定します。

[177] 
[PRE(code)[
   let h = b = the number of basic code points in the input
]PRE]

- [105] [VAR[b]] は[[基本符号位置]]の数を表し、 >>98 と >>104 で参照されています。
- [107] [VAR[h]] は処理し終わった[[符号位置]]の数を表します。
-- [134] >>98 で[[基本符号位置]]の処理が終わるので、 [VAR[h]] は[[基本符号位置]]の個数としておきます。

[98] 
[PRE(code)[
   copy them to the output in order, followed by a delimiter if b > 0
]PRE]

- [103] [[基本符号位置分居]] (>>17) を行います。
-- [99] [VAR@en[input]] から[[基本符号位置]]を取出し、そのままの順序で [VAR[output]] に複写します。
-- [100] その後に[[区切子]]を出力します。
--- [101] ただし、 >>99 が無かったときは出力しません。
--- [102] [[Punycode]] では「[CODE(char)[[[-]]]]」が[[区切子]]です。

[74] 
[PRE(code)[
   {if the input contains a non-basic code point < n then fail}
]PRE]

- [106] >>94 で非[[基本符号位置]]を [VAR[n]] から上へと探していくので、 [VAR[n]] 未満の非[[基本符号位置]]が含まれているとすると、正しく処理できません。
- [76] このチェックは、 [VAR[initial[SUB[[VAR[n]]]]]] より小さな[[符号位置]]がすべて[[基本符号位置]]なら、省略できます。 [SRC[>>2 6.3]]
-- [77] [[Punycode]] ではこれが成立します。 [SRC[>>2 6.3]]

[75] 
[PRE(code)[
   while h < length(input) do begin
]PRE]

- [108] [VAR[h]] は処理し終わった[[符号位置]]の数になっているので、 [VAR[input]] のすべての[[符号位置]]を処理するまでこのループは続きます。

[94] 
[PRE(code)[
     let m = the minimum {non-basic} code point >= n in the input
]PRE]

- [113] [VAR[m]] はこのループで処理する[[符号位置]]を表しています。
-- [114] [VAR[n]] が次に処理するべきかもしれない最小の[[符号位置]]となっており、それ[[以上]]であって [VAR[input]] に含まれている最小の非[[基本符号位置]]が実際に処理されるべき対象となります。
- [79] 「非基本」という条件は、すべての[[基本符号位置]]よりも [VAR[initial[SUB[[VAR[n]]]]]] が大きければ、ここで比較される[[符号位置]]はすべて [VAR[initial[SUB[[VAR[n]]]]]] [[以上]]であるため、常に成立します。 [SRC[>>2 6.3]]
-- [82] [[Punycode]] ではこれが成立します。 [SRC[>>2 6.3]] (>>112)

[78] 
[PRE(code)[
     let delta = delta + (m - n) * (h + 1), fail on overflow
]PRE]

- [144] ここで[[符号化]]されて出力される [VAR[delta]] が決まります。
- [145] [VAR[delta]] は [CODE(math)[[VAR[h]] + 1]] 進数で、一番下の桁が直前の非[[基本符号位置]]からの位置の差 (元の [VAR[delta]])、それより上の桁が直前の非[[基本符号位置]]の次の[[符号位置]]から実際の[[符号位置]]までの値の差 ([CODE(math)[[VAR[m]] - [VAR[n]]]]) を表しています。
- [115] [VAR[delta]] は、この行の直前において、
-- [116] 初回の実行では、 0 です (>>109)。
-- [130] 2回目以降の実行では、直前に処理した非[[基本符号位置]]からの位置の差となります。
--- [129] 内側のループ (>>120) において、 [VAR[c]] が [VAR[n]] より小さい時や [VAR[c]] が[[基本符号位置]]であるときに[[インクリメント]]されます (>>128)。
--- [121] 内側のループ (>>120) において、 [VAR[c]] と [VAR[n]] が等しいとき (>>80) に 0 にリセットされます (>>117)。
---- [127] 必ず一度は実行されます (>>125)。
---- [123] >>120 のループを抜けると、必ず >>122 を通ります。
--- [122] 外側のループ (>>75) の末尾でインクリメントされます (>>119)。
--- [132] まとめると、
---- [131] 非[[基本符号位置]]が連続する場合には、 >>121 で 0 にリセットされ、 >>122 で[[インクリメント]]されるので、 1 になります。
---- [133] 非[[基本符号位置]]の後に[[基本符号位置]]や処理済みの非[[基本符号位置]]がいくつかあるときは、 >>121 で 0 にリセットされ、 >>129 で処理済み数だけ[[インクリメント]]され、 >>122 で一度[[インクリメント]]されるので、結局 >>121 で処理した[[符号位置]]との間にある[[符号位置]]の数より1大きい値 (つまり位置の差) となります。
- [135] [VAR[delta]] が >>115 のような値となるので、 [VAR[delta]] が最大となるのはすべてが非[[基本符号位置]]の時であって、その値は先頭から次に処理する[[符号位置]]までの距離、つまり処理済みの[[符号位置]]の数、すなわち [VAR[h]] となります。
- [139] [CODE(math)[[VAR[m]] - [VAR[n]]]] は、 >>94 より、ここで処理され得る最小の[[符号位置]] ([VAR[n]]) と実際に [VAR[input]] に含まれていた最小の[[符号位置]] ([VAR[m]]) との[[差]]となります。
- [147] この [VAR[delta]] と [CODE(math)[[VAR[m]] - [VAR[n]]]] は、 [VAR[delta]] が [CODE(math)[[VAR[h]] + 1]] よりも必ず小さくなるので、 [CODE(math)[[VAR[m]] - [VAR[n]]]] に [CODE(math)[[VAR[h]] + 1]] を掛けて足せば一つの値にできます。
-- [137] [[復号]]時に取り出すには、 [CODE(math)[[VAR[h]] + 1]] で割った[[商]]と[[余り]]を求めればよいのです。
-- [148] [VAR[h]] はここまでに処理した[[符号位置]]の数なので、[[復号]]時にも自明です。
- [89] [VAR[input]] が長すぎる時 [SRC[>>2 6.3]] (元の [VAR[delta]]) や非常に大きな値を含んでいるとき [SRC[>>2 6.3]] ([VAR[m]] と [VAR[n]] の[[差]]が大きすぎるとき) に[[桁溢れ]]するおそれがあるので、チェックが必要です。
-- [146] [CODE(math)[[VAR[h]] + 1]] が[[桁溢れ]]することは、 >>75 で比較に使われる [VAR[input]] の長さが[[桁溢れ]]しないという前提より、また >>75 の条件がここまで成立していることから、あり得ません。

[88] 
[PRE(code)[
     let n = m
]PRE]

[120] 
[PRE(code)[
     for each code point c in the input (in order) do begin
]PRE]

- [150] ここから内側のループです。

[128] 
[PRE(code)[
       if c < n {or c is basic} then increment delta, fail on overflow
]PRE]

- [151] 処理対象の[[符号位置]] [VAR[c]] が [VAR[n]] よりも小さいか、[[基本符号位置]]であるなら、つまり今回の外側のループによって処理される[[符号位置]]である [VAR[n]] より小さいものなら、 [VAR[delta]] を[[インクリメント]]します。
- [81] [VAR[n]] の初期値である [VAR[initial[SUB[[VAR[n]]]]]] があらゆる[[基本符号位置]]よりも大きいなら、 [VAR[c]] が[[基本符号位置]]である時も常に [CODE(math)[[VAR[c]] < [VAR[n]]]] が成立しますから、チェックを省略できます。 [SRC[>>2 6.3]]
-- [83] [[Punycode]] ではこれが成立します。 [SRC[>>2 6.3]]
- [152] 内側のループ (>>120) 全体で見ると、 [VAR[delta]] は結局のところ、これまでに処理を終えた[[符号位置]]の数が >>78 に足されたものとなります。
-- [87] [VAR[input]] が長すぎる時に [VAR[delta]] が[[桁溢れ]]するおそれがあるので、チェックが必要です。 [SRC[>>2 6.3]]

[80] 
[PRE(code)[
       if c == n then begin
]PRE]

- [125] この [VAR[n]] は >>94 の [VAR[m]] を >>88 で代入したものなので、 [VAR[input]] 中にある[[符号位置]]です。
-- [126] 内側のループ (>>120) は [VAR[input]] の[[符号位置]]を順に処理しているので、最低1回は必ずこの条件が成立します。

[124] 
[PRE(code)[
         let q = delta
]PRE]

- [158] ここからが[[一般化可変長整数]] (>>22) による[[符号化]]です。 
[VAR@en[delta]] の値を[[符号化]]して出力します。

[157] 
[PRE(code)[
         for k = base to infinity in steps of base do begin
]PRE]

- [159] このループでは、[[一般化可変長整数]]の一番下の[[桁]]から順に出力します。最後の[[桁]]まで出力したら抜けます。
- [156] [VAR[k]] は [VAR[base]] の倍数で1倍、2倍、... と増えていきます。
- [155] このループは >>154 で抜けます。

[153] 
[PRE(code)[
           let t = tmin if k <= bias {+ tmin}, or
                   tmax if k >= bias + tmax, or k - bias otherwise
]PRE]

- [160] [VAR[t]] は[[一般化可変長整数]]における、現在の[[桁]]で使う[[閾値]] (>>24) です。
- [86] [VAR[k]] から [VAR[bias]] を引いた値を [VAR[t]] に代入しています。ただし、 [VAR[t]] が [VAR[t[SUB[min]]]] [[以上]] [VAR[t[SUB[max]]]] [[以下]]となるようにします。
- [84] [VAR[t[SUB[min]]]] を足すところを省略すると、 [VAR[k]] が [VAR[bias]] よりも大きく [VAR[bias]] と [VAR[t[SUB[min]]]] の[[和]]よりも小さいときに誤った結果になりますが、 [VAR[bias]] の計算方法および各[[引数]]の条件より、 [VAR[k]] がそのような値になることはありません。 [SRC[>>2 6.3]]
-- [85] これは常に成立します。 [SRC[>>2 6.3]]
- [204] >>157 のループの、
-- [208] はじめのうちは [VAR[k]] が小さいので、 [VAR[t[SUB[min]]]] が使われます。
-- [205] 最後のほうでは [VAR[k]] が大きいので、 [VAR[t[SUB[max]]]] が使われます。
-- [207] 中間では [VAR[k]] よりも [VAR[bias]] の分小さな値が使われます。
- [206] このあたりでおかしなことが起こらないように各[[引数]]には >>71 の条件があります。

[154] 
[PRE(code)[
           if q < t then break
]PRE]

- [162] [VAR[q]] が [VAR[t]] より小さいということは、 [VAR[q]] は最後の1桁だけで表現できるので、ループを抜けます。ループを抜けた >>163 で最後の桁が出力されます。

[161] 
[PRE(code)[
           output the code point for digit t + ((q - t) mod (base - t))
]PRE]

- [164] >>154 の条件が成立しなかったので、これは途中の[[桁]]です。
- [165] この[[桁]]で表されるのは、
-- [166] [[閾値]]よりも下の成分 [VAR[t]] と
-- [167] [[閾値]]よりも上の成分 [CODE(math)[[VAR[q]] - [VAR[t]]]] のうち、
--- [168] この[[桁]]で[[閾値]]よりも上の値を表すために使える[[数字]]は [CODE(math)[[VAR[base]] - [VAR[t]]]] 個なので
--- [169] それで割った余り
-- [170] の[[和]]、 >>166 + >>169 です。

[171] 
[PRE(code)[
           let q = (q - t) div (base - t)
]PRE]

- [173] そして次以降の[[桁]]で表されるのは、 >>167 のうち >>168 で割った[[商]]であり、これを新しい [VAR[q]] とします。

[172] 
[PRE(code)[
         end
]PRE]

- [174] >>157 に戻ります。

[163] 
[PRE(code)[
         output the code point for digit q
]PRE]

- [175] >>154 から来ました。 [VAR[q]] は[[閾値]] [VAR[t]] より小さく、1桁の[[数字]]で表せます。これが [VAR[delta]] の[[一般化可変長整数]]の最後の[[桁]]です。

[104] 
[PRE(code)[
         let bias = adapt(delta, h + 1, test h equals b?)
]PRE]

- [176] [[偏差適応]] (>>56) により、次の [VAR[delta]] のための [VAR[bias]] を計算します。
-- [197] [[関数]] [VAR[adapt]] (>>196) を呼び出します。
-- [178] 第1引数の [VAR[delta]] はループの今周で処理した値であり、これを元に適応させた [VAR[bias]] が返されます。
-- [179] 第2引数の [VAR[h]] はここまでに処理した[[符号位置]]の数です。 [VAR[h]] に1を足しているのは、ループの今周で処理していた [VAR[delta]] の分です。
-- [180] [VAR[b]] は[[基本符号位置]]の数 (>>177) です。これと [VAR[h]] を比較しているので、最初の [VAR[delta]] であったかどうかが第3引数の値となります。

[117] 
[PRE(code)[
         let delta = 0
]PRE]

- [181] 次の非[[基本符号位置]]は今回処理し終えた非[[基本符号位置]]からの差分によって表現しますので、ここで一端 [VAR[delta]] は 0 に戻します。

[118] 
[PRE(code)[
         increment h
]PRE]

- [184] [[符号位置]]1つ分の処理を終えたので、処理済み[[符号位置]]の数である [VAR[h]] を[[インクリメント]]します。
-- [185] これは [VAR[input]] の長さより短く、 [VAR[input]] の長さは表現できるという仮定があるので、[[桁溢れ]]することはありません (>>91 と同じ)。

[182] 
[PRE(code)[
       end
]PRE]

- [192] >>80 からの [VAR[c]] の値の条件分岐がここで終わります。

[183] 
[PRE(code)[
     end
]PRE]

- [186] >>120 からの内側のループはここで終わります。 [VAR[input]] にまだ続きがあれば、更にもう一周します。
-- [188] 現在の [VAR[n]] と同じ値の[[符号位置]]が [VAR[input]] の続きにまだあるかもしれませんし、ないかもしれません。
-- [189] [VAR[input]] にもう続きがないとしたら、値が [VAR[n]] [WEAK[([[以下]])]] の[[符号位置]]はもう残っていないので、 >>119 に進みます。

[119] 
[PRE(code)[
     increment delta and n
]PRE]

- [193] 前の非[[基本符号位置]]からの差が一つ開いたという意味で、 [VAR[delta]] を[[インクリメント]]します (>>122)。
- [194] 次の[[符号位置]]を処理するという意味で (>>189)、 [VAR[n]] を[[インクリメント]]します。
- [91] この[[インクリメント]]の直前において [VAR[delta]] は [VAR[input]] の長さより小さく、 [VAR[input]] の長さは[[桁溢れ]]せずに表せることを前提としているので、 [VAR[delta]] は[[インクリメント]]しても[[桁溢れ]]しません。
- [92] [VAR[n]] は[[桁溢れ]]するおそれがあります。 [SRC[>>2 6.3]]
-- [93] [VAR[n]] は >>88 で [VAR[m]] を代入しています。これは >>94 で代入された[[符号位置]]となります。
[[符号位置]]はすべて[[整数]]として表せると仮定しているので [SRC[>>2 6.]]、
ここまで[[桁溢れ]]せずに処理できています。
-- [97] さて、[[整数]]の最大値の[[符号位置]]が [VAR[n]] に入っていると、
[[インクリメント]]で[[桁溢れ]]します。
-- [95] しかし、 >>94 
で最小の[[符号位置]]から順に処理しているということは、最大値である[[符号位置]]は最後になってはじめて
[VAR[m]]、ひいては [VAR[n]] に代入されます。
-- [96] その場合、 >>75 の条件より 
[WEAK[([VAR[h]]、つまり処理済みの[[符号位置]]の数が [VAR[input]] の長さと一致する、つまり最後の[[符号位置]]まで処理し終えて条件を満たさなくなったため)]]
どのみちループを抜けます。
ループを抜けて終わるだけなので、 [VAR[n]] が桁溢れしても問題ありません [SRC[>>2 6.3]]。

[90] 
[PRE(code)[
   end
]PRE]

- [187] >>75 からの外側のループはここで終わります。 [VAR[h]] がまだ [VAR[input]] の長さに達していなければ、更にもう一周します。
-- [190] [VAR[h]] がまだ [VAR[input]] の長さに達していないということは、 [VAR[n]] より大きな[[符号位置]]がまだあるので、その処理に移ります。
-- [191] [VAR[h]] が [VAR[input]] の長さに等しいなら、これ以上大きな[[符号位置]]は残っていないので、[[符号化]]は完了です。

* 復号

[222] 次に示すのは、 [[RFC 3492]] 6.2 に示された [[Bootstring]] の[[復号]]の[[擬似コード]]に注釈を加えたものです。

[223] 
[PRE(code)[
   let n = initial_n
   let i = 0
   let bias = initial_bias
   let output = an empty string indexed from 0
   consume all code points before the last delimiter (if there is one)
     and copy them to output, fail on any non-basic code point
   if more than zero code points were consumed then consume one more
     (which will be the last delimiter)
   while the input is not exhausted do begin
     let oldi = i
     let w = 1
     for k = base to infinity in steps of base do begin
       consume a code point, or fail if there was none to consume
       let digit = the code point's digit-value, fail if it has none
       let i = i + digit * w, fail on overflow
]PRE]

[228] 
[PRE(code)[
       let t = tmin if k <= bias {+ tmin}, or
               tmax if k >= bias + tmax, or k - bias otherwise
]PRE]

- [230] [VAR[t[SUB[min]]]] を足す部分は、[[符号化]]の時 (>>84) と同様に省略できます。
[SRC[[[RFC 3492]] 6.2]]

[229] 
[PRE(code)[
       if digit < t then break
       let w = w * (base - t), fail on overflow
     end
     let bias = adapt(i - oldi, length(output) + 1, test oldi is 0?)
     let n = n + i div (length(output) + 1), fail on overflow
     let i = i mod (length(output) + 1)
]PRE]

[224] 
[PRE(code)[
     {if n is a basic code point then fail}
]PRE]

- [226] すべての[[基本符号位置]]が [VAR[n[SUB[initial]]]] よりも小さければ、
[VAR[n]] は常に [VAR[n[SUB[initial]]]] [[以上]]となるため、この条件が成立することはなく、
省略できます。 [SRC[[[RFC 3492]] 6.2]]
-- [227] [[Punycode]] はそれに該当します。 [SRC[[[RFC 3492]] 6.2]]

[225] 
[PRE(code)[
     insert n into output at position i
     increment i
   end
]PRE]

- [231] とある[[整数]]の列が与えられた時、それを表現できる[[符号化]]された文字列は、ただ一つだけ存在します。  [SRC[[[RFC 3492]] 6.2]]
-- [232] というのは、この[[復号]]器の状態は[[単調増加]]するだけであり、  [SRC[[[RFC 3492]] 6.2]]
-- [233] かつ[VAR[delta]] の表現方法は一種類だけであるためです。 [SRC[[[RFC 3492]] 6.2]]
- [234] [[誤り条件]]として起こり得るのは、  [SRC[[[RFC 3492]] 6.2]]
-- [235] 不正な[[符号位置]]
-- [236] 予期せぬ [VAR[input]] の終了
-- [237] [[桁溢れ]]
-- [238] [[基本符号位置]]がそのままではなく[[符号化]]されて出現する
-- [239] ... といったものがあります。  [SRC[[[RFC 3492]] 6.2]]
-- [240] [[復号]]器がこれらの誤りで失敗した場合には、他のどんな [VAR[input]] とも同じ出力を生成することはありません。  [SRC[[[RFC 3492]] 6.2]]
--- [241] そのため、出力を再[[符号化]]してもとの [VAR[input]] と照らし合わせなくても、[[符号化]]の[[固有性]]を保証できます。  [SRC[[[RFC 3492]] 6.2]]

* 実装

[12] [CITE[Encode::Bootstring - search.cpan.org]]
<http://search.cpan.org/dist/Encode-Bootstring/lib/Encode/Bootstring.pm>