[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)]] * 性質 [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]] * 引数の制約 [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 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] 入力が長すぎる時 [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] [128] [PRE(code)[ if c < n {or c is basic} then increment delta, fail on overflow ]PRE] - [81] 「基本」という条件は、すべての[[基本符号位置]]よりも [VAR[initial[SUB[[VAR[n]]]]]] が大きければ、ここで比較される[[符号位置]]はすべて [VAR[initial[SUB[[VAR[n]]]]]] [[以上]]であるため、決して成立することはありません。 [SRC[>>2 6.3]] -- [83] [[Punycode]] ではこれが成立します。 [SRC[>>2 6.3]] - [87] 入力が長すぎる時に[[桁溢れ]]するおそれがあるので、チェックが必要です。 [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 for k = base to infinity in steps of base do begin let t = tmin if k <= bias {+ tmin}, or tmax if k >= bias + tmax, or k - bias otherwise ]PRE] - [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]] [PRE(code)[ 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 ]PRE] [104] [PRE(code)[ let bias = adapt(delta, h + 1, test h equals b?) ]PRE] [117] [PRE(code)[ let delta = 0 ]PRE] [118] [PRE(code)[ increment h end end ]PRE] [119] [PRE(code)[ increment delta and n ]PRE] - [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] * 実装 [12] [CITE[Encode::Bootstring - search.cpan.org]]