ネットワークワーキンググループ A. Costello
Request for Comments: 3492 Univ. of California, Berkeley
分類: 標準化過程(Standards Track) 2003年3月
Punycode: アプリケーションにおいてドメイン名国際化(IDNA)を
行うためのUnicodeのBootstringエンコーディング
本文書の位置づけ
本文書はインターネットコミュニティーのためにインターネット標準化過程に
あるプロトコルを規定し、その向上のために議論と提案を求めるものである。
このプロトコルの標準化の状況については"Internet Official Protocol
Standards"(STD 1)の最新版を参照のこと。本文書の配布は制限されない。
著作権表示
Copyright (C) The Internet Society (2003). All Rights Reserved.
要旨
Punycodeは、単純で効率的な転送用エンコーディング(transfer
encoding)記法であり、IDNA(Internationalized Domain Names in Applications)と
共に使用されるように設計されている。PunycodeはUnicode文字列を、一意かつ
可逆的にASCII文字列に変換する。ASCII文字は、そのまま文字として表現され、
非ASCII文字はホスト名ラベルで使用可能なASCII文字(文字、数字、ハイフン)で
表現される。本文書は、Bootstringと呼ぶ一般的アルゴリズムを定義する。
本アルゴリズムは、より大きな文字集合に属するコードポイントの並びを、
基本コードポイントの並びによって一意に表現することを可能にする。
Punycodeは、IDNA向けに本文書で規定したパラメーター値を使用する、
Bootstringの適用事例(instance)である。
目次
1. はじめに...................................................2
1.1 機能的特徴............................................2
1.2 プロトコルとの関係....................................3
2. 用語.......................................................3
3. Bootstringの説明...........................................4
3.1 基本コードポイントの分離..............................4
3.2 挿入による整列復元コーディング........................4
3.3 一般化可変長整数......................................5
3.4 bias補正..............................................7
4. Bootstringのパラメーター...................................8
5. Punycode用のパラメーター値.................................8
6. Bootstringアルゴリズム.....................................9
Costello Standards Track [Page 1]
RFC 3492 IDNA Punycode March 2003
6.1 bias補正関数.........................................10
6.2 デコーディング処理...................................11
6.3 エンコーディング処理.................................12
6.4 オーバーフローの処理.................................13
7. Punycode例................................................14
7.1 文字列の例...........................................14
7.2 デコーディング処理の検証.............................17
7.3 エンコーディング処理の検証...........................19
8. セキュリティーに関する考察................................20
9. 参考文献..................................................21
9.1 必須の参考文献.......................................21
9.2 有用な参考文献.......................................21
A. 文字種注釈(Mixed-case annotation).........................22
B. 免責条項と使用許諾........................................22
C. Punycodeの実装例..........................................23
著者の連絡先.................................................34
完全な著作権表示.............................................35
1. はじめに
[IDNA]は国際化ドメイン名をサポートするためのアーキテクチャーを記述して
いる。これは非ASCII文字を含むラベルを、特別なACEプレフィックスで始まる
ASCII文字だけで構成されたACEラベルによって表現可能にするものである。
プレフィックスの後に続けられたラベルの残りは、ある制約条件を満たすように
PunycodeでエンコードされたUnicode文字列である。プレフィックスと
制約条件の詳細については、[IDNA]と[NAMEPREP]を参照のこと。
Punycodeは、Bootstringと呼ばれる、より一般的なアルゴリズムの適用事例
(instance)である。このアルゴリズムは、より大きな文字集合に属する
コードポイントの並びを、小さな"基本(basic)"コードポイントの集合に
含まれるコードポイントの並びによって一意に表現可能にするものである。
Punycodeは、Bootstringの特定のパラメーター値をIDNA向けに適切に設定した
ものである。
1.1 機能的特徴
Bootstringは、以下の機能的特徴を持つように設計された。
* 完全性: 拡張文字列(任意のコードポイントの並び)は、基本文字列(基本
コードポイントの並び)によって表現できる。許容される文字列、文字列の
長さ等の制約は、上位層で導入可能である。
* 一意性: 与えられた拡張文字列を表現する基本文字列は一つしか存在
しない。
* 可逆性: 任意の拡張文字列を基本文字列に変換した場合、その基本文字列から
変換前の拡張文字列を再生可能である。
Costello Standards Track [Page 2]
RFC 3492 IDNA Punycode March 2003
* 効率的エンコーディング: 拡張文字列の長さと、それを表現する基本文字列の
長さの比率は小さい。処理対象がドメイン名であることを考慮すると、これは
重要な意味を持つ。なぜなら、RFC1034[RFC1034]はドメインラベルを63文字に
制限しているからである。
* 単純性: エンコーディングとデコーディングのアルゴリズムは、実装には
充分に単純なものである。効率性と単純性のゴールは二律背反するものだが、
Bootstringはその間で優れたバランスを取ることを目標としている。
* 読みやすさ: 拡張文字列に含まれる基本コードポイントは、変換後の
基本文字列においてもそのまま表現される。(主たる意図は効率を改善する
ことであり、読みやすさを改善することではないにしても)。
Punycodeは[IDNA]のToASCII処理とToUnicode処理で使用されない付加的機能も
サポート可能である。エンコーディング前に拡張文字列の大文字、小文字の
文字種が統一されている(case-folded)場合、文字種が統一された文字列を
どのように文字種混在の文字列に変換したかを示すために、基本文字列は
大文字と小文字が混在した文字列を使用することができる。付録A "文字種注釈
(Mixed-case annotation)"を参照のこと。
1.2 プロトコルとの関係
PunycodeはドメインラベルをASCIIに変換するために、IDNAプロトコル[IDNA]で
使用されるものであり、他の目的のためには設計されていない。任意の文章を
処理するために設計されたものではないことをここに明記する。
2. 用語
本文書におけるキーワード"しなければならない(MUST)"、"してはならない
(MUST NOT)"、"要求される(REQUIRED)"、"するものとする(SHALL)"、
"しないものとする(SHALL NOT)"、"すべきである(SHOULD)"、"すべきでない
(SHOULD NOT)"、"推奨される(RECOMMENDED)"、"してもよい(MAY)"、
"任意である(OPTIONAL)"は、BCP14、RFC2119[RFC2119]に記述されている
とおりに解釈される。
コードポイントは符号化文字集合(coded character set)において、
文字に関連付けられる整数値(integral value)である。
Unicode標準[UNICODE]に記述されているとおり、Unicodeコードポイントは、
"U+"に4桁の16進数を続けることによって表現される。また、コードポイントの
範囲は、プレフィックス無しで2つの16進数を".."で分割した表現形式を使用
する。
演算子divとmodは整数の割り算を実行する。(x div y)はxをyで割った商で、
余りは捨てられる。また、(x mod y)はxをyで割った余りである。したがって、
(x div y) * y + (x mod y) == x となる。Bootstringはこれらの演算子を
負でない演算数に対してだけ使用する。したがって、商と余りは常に
負でない値を持つ。
break構文は、(C言語のように)一番深い(内側の)ループから脱出するもの
である。
Costello Standards Track [Page 3]
RFC 3492 IDNA Punycode March 2003
オーバーフローは、整数を保存する変数の最大値を超える値を計算しようと
する試みである。
3. Bootstringの説明
Bootstringは、任意のコードポイントの並び("拡張文字列")を、基本
コードポイントの並び("基本文字列")として表現する。本セクションは、
この表現形式について記述する。セクション6"Bootstringアルゴリズム"
では、このアルゴリズムを擬似的なコードとして提示する。セクション7.1
"デコーディング処理の検証"と7.2"エンコーディング処理の検証"では、
入力例に対するアルゴリズムの処理を検証する。
以下のセクションでは、Bootstringが使用する4つの手法を記述する。
"基本コードポイントの分離(segregation)"は、拡張文字列に含まれる基本
コードポイントを対象とする、非常に単純で効果的なエンコーディング
である。これらは、単純に全てが直ちにコピーされる。
"挿入による整列復元コーディング(insertion unsort coding)"は、
非基本コード(non-basic code point)をdelta(*1)としてエンコードする。
その際に、コードポイントの処理は、入力されるコードポイントの並びの
順番ではなく、コードポイントの値が数値的に小さいものから順に処理される。
この結果、一般的にdeltaはより小さくなる。deltaは、"一般化可変長整数
(generalized variable-length integer)"として表現される。これは負でない
整数を表現するために、基本コードポイントを使用する。
この整数表現のパラメーターは、続くdeltaが同様な大きさ(magnitude)を持つ
場合には、効率を改善するために、"bias補正(bias adaptation)"を使用して
動的に調整される。
《脚注》
*1: delta
原文に含まれる幾つかの語、delta, bias, tmin, tmax, damp は、
後に擬似コード内でそのまま扱われるため、原文のままとした。
|
3.1 基本コードポイントの分離
拡張文字列に含まれる基本コードポイントは、全てそのままの文字として
原文どおりの順序で基本文字列の先頭にコピーされる。基本コードポイントの
数がゼロでない場合(に限っては)、区切り文字(delimiter)が続けられる。
区切り文字は、残りの基本文字列には決して現れない特定の基本コード
ポイントである。したがって、デコーダーは、区切り文字が存在する場合、
最後の区切り文字を探すことにより、そのまま文字として表現されている
部分の終端部を見つけることができる。
3.2 挿入による整列復元コーディング
基本文字列の残り部分(区切り文字がある場合には、最後の区切り文字よりも
後ろの部分)は、セクション3.3に記述されるとおり、一般化可変長整数として
表現された、負でない整数のdeltaの並びである。deltaの意味は、
デコーダーの観点から考えるのが最も理解しやすい。
デコーダーは拡張文字列を徐々に構築する。初めは、拡張文字列は基本文字列
のうち、そのまま文字として使用されている部分をコピーしたものである
(ただし、最後の区切り文字は除かれる)。デコーダーは非基本コードポイントを
各delta毎に拡張文字列に挿入していき、最終的にはデコードされた文字列に
到達する。
Costello Standards Track [Page 4]
RFC 3492 IDNA Punycode March 2003
この処理の主要な部分は、2つの状態変数インデックスiとカウンターnを持つ
状態マシン(state machine)である。インデックスiは拡張文字列における位置を
示し、0(最初の位置)から拡張文字列の現在の長さ(現在の終端を越えた位置に
存在する仮想的な位置)の範囲を採る。現在の状態が<n,i>である場合、iが
拡張文字列長よりも短かければ次の状態は<n,i+1>となり、iが拡張文字列長と
等しければ、次の状態は<n+1,0>となる。言い換えると、各状態の変化はiを
増加(increment)させ、必要に応じてゼロに周回する。nは周回した回数を
カウントするものである。
状態は常に単調に進むことに注意してもらいたい(デコーダーには現在よりも
前の状態に戻す方法は存在しない)。各状態において、挿入処理は行われるか
行われないかのどちらかである。任意の状態において行われる挿入処理は、
多くとも1回である。挿入処理は、拡張文字列のiの位置に、値nを挿入する。
deltaはこの一連のイベントの連続長(run-length)エンコーディングである。
つまり、deltaは挿入処理後の状態に先立つ挿入処理前の状態の連続の長さである。
したがって、各delta毎に、デコーダーはdelta状態の変更を実行し、挿入処理を
行った後に、もう1度状態の変更を行う。(実装は各状態の変更を個別に実行する
必要はなく、代わりに割り算を使用し、余りの計算を行い、次の挿入状態を
直接演算することができる)。挿入されたコードポイントが基本コードポイントの
場合、エラーとなる。(セクション3.1に記述されるとおり、基本コードポイントは
分離されているはずだからである)。
エンコーダーの主な仕事は、期待する文字列をデコーダーに構築させる
deltaの並びを導出することである。この目標は、拡張文字列を走査して
デコーダーが挿入しなければならない次のコードポイントを順次探していき、
デコーダーが実行しなければならない状態変更の回数をカウントすることに
よって達成される。デコーダーから出力される拡張文字列は、挿入処理が
されたコードポイントだけしか含まないという事実を心に留めておいて
もらいたい。セクション6.3 "エンコーディング処理"で詳細なアルゴリズムを
示す。
3.3 一般化可変長整数
従来の整数表現では、base(基数)は数字を識別するために使用できる記号の数
であり、記号に対応する値は0からbase-1までである。ここで、digit_0が最も
低い桁の値を示し、digit_1が次に低い桁の値、以下同様であるとする。
すると、表現される値は、digit_j * w(j) の和となる。ただし、
w(j) = base^jは、jの桁の位置に対する重み(倍率)である。例えば、基数8の
整数437の場合、桁の値はそれぞれ7, 3, 4であり、重みはそれぞれ1, 8, 64
である。したがって、表現される値は7 + 3*8 + 4*64 = 287 となる。
この表現方法には2つの欠点がある。1つめの欠点は、各値に対して複数の
エンコーディングが存在することである。(なぜなら、最上位の桁に余分なゼロを
追加できるからである)。これは一意なエンコーディングが必要とされる場合には
不便である。2つめの欠点は、整数はそれ自身で区切り文字を持たないこと
である。このため、複数の整数を続けて記述すると、2つの整数の境界は
わからなくなる。
Costello Standards Track [Page 5]
RFC 3492 IDNA Punycode March 2003
一般化可変長表現は、この2つの問題を解決する。桁の値は依然として0から
base-1の範囲だが、この整数はしきい値t(j)によって境界が設定される。
各桁それぞれについて、しきい値t(j)は0からbase-1の範囲で設定される。
そして、最上位の一桁だけがdigit_j < t(j)を必ず満たす。したがって、
幾つかの整数が続けて記述されている場合でも、それらを分離することは
容易である。リトルエンディアン(最下位桁が先頭にくる)の場合は1桁目から、
ビッグエンディアン(最上位桁が先頭に来る)の場合は最後の桁から分離処理を
開始すればよい。 既に述べたとおり、値はdigit_j * w(j) の和であるが、
以下に示すとおり重みが異なる。
w(0) = 1
w(j) = w(j-1) * (base - t(j-1)) j > 0の場合
例として、リトルエンディアンのbase 8の数の並び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よりも小さいことから、4が最後の数字
であることがわかる。734が表現する値は、7*1 + 3*6 + 4*30 = 145である。
次の整数は251で、その値は2*1 + 5*6 + 1*30 = 62である。この表現の
デコーディングは、従来の整数のデコーディングと極めて似ている。
現在の値N = 0、重み w = 1から開始する。次の桁の数dを取り込み、Nを
d * w だけ増加させる。dが現在のしきい値(t)よりも小さければ処理を終え、
そうでない場合はwを(base - t)の係数で増加させ、次の桁の処理に向けて
tを更新する。以後、それを繰り返す。
この表現のエンコーディングは従来の整数のエンコーディングと同様である。
N < tの場合、Nに対する1桁の数を出力し、処理を終える。そうでない場合、
t + ((N - t) mod (base - t))に対する桁の数を出力し、Nを
(N - t) div (base - t)に置き換え、次の桁の計算に向けてtを更新すると
いった処理を繰り返す。
t(j)の値が採る範囲がどのようなものであるとしても、負でない整数値
それぞれに対して、一般化可変長表現が1つだけ存在する。
Bootstringは、deltaを先頭から分割できるように、リトルエンディアンの
順序づけを使用する。t(j)の値は、定数base, tmin, tmaxと、biasと呼ばれる
状態変数を使用して、以下のように定義される。
t(j) = base * (j + 1) - bias
値はtminからtmaxの範囲に制限される。
Costello Standards Track [Page 6]
RFC 3492 IDNA Punycode March 2003
値を制限するとは、与式がtminより小さい値またはtmaxよりも大きい値を
導出した場合、それぞれt(j) = tminまたはtmaxとなることを意味する。
(セクション6 "Bootstringアルゴリズム"で提示する擬似コードでは、
パフォーマンス向上のために数式 base * (j + 1)をkと記述している)。
このようなt(j)の値は、整数の表現をbiasによって決定される特定の範囲内に
納める際に有効に作用する。
3.4 bias補正
各deltaがエンコードまたはデコードされた後に、次のdeltaに対する
biasを以下のように設定する。
1. 次の処理段階におけるオーバーフローを回避するために、deltaを
縮小させる。
let delta = delta div 2
deltaが最初のdeltaである場合には、除数は2ではなく、代わりに
dampと呼ばれる定数を使用する。これにより、2番目に生成されるdeltaは、
通常最初のdeltaよりも極めて小さくなるという事実を補正する。
2. 次のdeltaは、より長い文字列に挿入されるという事実にあわせて、deltaを
増加させる。
let delta = delta + (delta div numpoints)
numpointsとは、ここまでの段階でエンコード/デコードされた
コードポイントの数である。(このdeltaに対応するものと、基本コード
ポイントを含む)。
3. deltaは、次のdeltaを表現するために必要な最小桁数を予測するために、
しきい値内に収まるまで繰り返し除算される。
while delta > ((base - tmin) * tmax) div 2
do let delta = delta div (base - tmin)
4. biasの設定
let bias =
(base * 処理段階3で実行された割り算の回数) +
(((base - tmin + 1) * delta) div (delta + skew))
この処理の目指すものは、現在のdeltaが次のdeltaの大まかなサイズの
ヒントを提供するため、最上位桁である可能性がより高い桁の数値に対する
t(j)をtmaxに設定し、最下位桁から上位3桁目である可能性が高い桁までは
t(j)をtminに設定する。最後に最上位桁から2番目であると期待される桁に
対してはt(j)をtminとtmaxの間の値に設定することである。(これは最上位桁
であると予想される桁が不要になるという希望と、その桁が最上位桁ではない
という危険をバランスさせるということである)。
Costello Standards Track [Page 7]
RFC 3492 IDNA Punycode March 2003
4. Bootstringのパラメーター
任意の基本コードポイントの集合に対して、区切り文字が1つ指定されなければ
ならない。baseは残りの識別可能な基本コードポイント数よりも大きくては
いけない。0からbase-1の範囲で桁に表示される値は、それぞれ個別に、
区切り文字ではない基本コードポイントに関連付けられなければならない。
幾つかの場合においては、複数のコードポイントが同じ桁表示値を持つ
必要がある。例えば、基本文字列が大文字小文字を区別しない
(case-insensitive)場合、同じ文字の大文字と小文字は等しいものとして
扱われる必要がある。
nの初期値は、拡張文字列内に現れ得る非基本コードポイントの最小値よりも
大きくてはいけない。
残りの5つのパラメーター(tmin, tmax, skew, damp, biasの初期値)は
以下の制約を満たさなければならない。
0 <= tmin <= tmax <= base-1
skew >= 1
damp >= 2
initial_bias mod base <= base - tmin
提示された制約が満たされていれば、これら5つのパラメーターは効率に
影響を与えるが、正確さには影響を与えない。これらは経験的に最適な値が
定められる。
文字種注釈のサポートが求められる場合(付録A参照)、0からtmax-1までに
対応するコードポイントが全て大文字と小文字の形式を持っていることを
確認すること。
5. Punycode用のパラメーター値
Punycodeは以下のBootstringパラメーター値を使用する。
base = 36
tmin = 1
tmax = 26
skew = 38
damp = 700
initial_bias = 72
initial_n = 128 = 0x80
Punycodeに入力する整数は負でないものでなければならないという制約が
付加されてはいるが、これらのパラメーターは0..10FFFFの範囲の整数を採る
Unicode[UNICODE]コードポイントに対して特にうまく動作するように設計
されている。(しかし、UnicodeのUTF-16エンコーディングが使用するために
予約されているD800..DFFFは対象ではない)。
Costello Standards Track [Page 8]
RFC 3492 IDNA Punycode March 2003
基本コードポイントはASCII[ASCII]コードポイント(0..7F)であり、そのうち
U+002D(-)は区切り文字である。また、他のコードポイントの幾つかは
以下に示すように桁表示値を持つ。
コードポイント 桁表示値
------------ ---------------------------
41..5A (A-Z) = それぞれ0から25に対応
61..7A (a-z) = それぞれ0から25に対応
30..39 (0-9) = それぞれ26から35に対応
ハイフン(マイナス)を区切り文字として使用するということは、Unicode文字列が
全て基本コードポイントで構成されている場合にはエンコードされた文字列は
ハイフン(マイナス)で終わっても良いことを意味する。しかし、IDNAはそのような
文字列にエンコードされることを禁止している。エンコードされた文字列は
ハイフン(マイナス)で始まってもよいが、IDNAは先頭にプレフィックスを
追加する。以上の結果、Punycodeを使用するIDNAは、ホスト名ラベルが
ハイフン(マイナス)で開始、終了しないというRFC952のルール[RFC952]に
準拠する。
デコーダーは、ある文字について大文字と小文字の形態を(大文字と小文字が
混在している状態も含めて)認識できなければならない(MUST)。
エンコーダーは、文字種注釈(付録A参照)を使用していない限り、
出力を大文字または小文字だけの形態にすべきである(SHOULD)。
おそらくは、ほとんどのユーザーはエンコードされた文字列を直接書いたり
タイプしたりはしないだろう(むしろカット＆ペーストをするだろうから)。
しかし、直接書いたりタイプしたりするユーザーに対しては、以下に
示すように視覚的にどちらとも取れる可能性がある文字の集合があることを
警告する必要がある。
G 6
I l 1
O 0
S 5
U V
Z 2
このような不明瞭さは通常文脈から判断して解決される。しかし、Punycodeで
エンコードされた文字列の場合、そのような文脈は人間に対して何も示されない。
6. Bootstringアルゴリズム
擬似コードの幾つかの部分は、パラメーターが(Punycodeに適した)ある条件を
満たす場合には省略できる。省略可能な部分は{括弧}でくくられており、
省略可能な条件の説明が、擬似コードのすぐ後ろに記載される。
Costello Standards Track [Page 9]
RFC 3492 IDNA Punycode March 2003
形式上、コードポイントは整数であるため、擬似コードはコードポイントに
対して直接算術的処理が実行可能であると想定している。幾つかのプログラミング
言語では、コードポイントと整数を明示的に変換する必要があるかもしれない。
6.1 bias補正関数
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))
adapt()内部におけるdeltaとkの値変更が、エンコーディング/デコーディング
処理の内部で使用されている同名の変数に影響を与えるかについては
気にしなくてよい。adapt()を呼び出した後に、呼び出した処理(caller)は
それらの変数の値を読み出すことなく、上書きするからである。
Costello Standards Track [Page 10]
RFC 3492 IDNA Punycode March 2003
6.2 デコーディング処理
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
let t = tmin if k <= bias {+ tmin}, 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, test oldi is 0?)
let n = n + i div (length(output) + 1), fail on overflow
let i = i mod (length(output) + 1)
{if n is a basic code point then fail}
insert n into output at position i
increment i
end
(nが基本コードポイントであるか検査している){}括弧に囲まれた記述は、
initial_nが全ての基本コードポイントよりも大きい場合(Punycodeではこれは
正しい)省略可能である。なぜなら、nは決してinitial_nより小さくは
ならないからである。
tの値がtminからtmaxの範囲に制限される条件下では、tの割り当ての際に
{+tmin}部分は常に省略可能である。tの値を制限することにより、
bias < k < bias + tmin の場合に制約計算が正しくなくなるが、bias計算方法と
パラメーターの制約により、そのような事態は発生しない。
デコーダーの状態は単調にしか進展しないため、任意のdeltaに対して1つだけ
しか表現が存在しない。したがって、与えられた整数の並びを表現可能な
エンコードされた文字列は1つしか存在しない。エラー条件は、コードポイントが
無効な場合、予期しない入力終了の発生、オーバーフロー発生、基本コード
ポイントをそのまま文字として扱わずにdeltaを使用してエンコードした場合等
である。これらのエラーによってデコーダーの処理が失敗するため、異なる
2つの入力から同じ出力を生成することはできない。
Costello Standards Track [Page 11]
RFC 3492 IDNA Punycode March 2003
この性質が無ければ、エンコーディングの一意性を保証するために、出力を
再度エンコードし、入力と一致するかを検証する必要があっただろう。
6.3 エンコーディング処理
let n = initial_n
let delta = 0
let bias = initial_bias
let h = b = the number of basic code points in the input
copy them to the output in order, followed by a delimiter if b > 0
{if the input contains a non-basic code point < n then fail}
while h < length(input) do begin
let m = the minimum {non-basic} code point >= n in the input
let delta = delta + (m - n) * (h + 1), fail on overflow
let n = m
for each code point c in the input (in order) do begin
if c < n {or c is basic} then increment delta, fail on overflow
if c == n then begin
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
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, test h equals b?)
let delta = 0
increment h
end
end
increment delta and n
end
(入力がnより小さい非基本コードポイントを含むか検査している){}括弧に
囲まれた記述は、nより小さい全てのコードポイントが基本コードポイントである
場合(Punycodeでは、コードポイントが割り当てられていなければこれは正しい)
には省略可能である。
{}括弧に囲まれている条件 "non-basic" と "or c is basic" 部分は、
intial_nが全ての基本コードポイントより大きい場合(Punycodeではこれは
正しい)省略可能である。なぜなら、検査されるコードポイントは、決して
initial_nよりも小さくはならないからである。
tの値がtminからtmaxの範囲に制限される条件下では、tの割り当ての際に
{+tmin}部分は常に省略可能である。tの値を制限することにより、
bias < k < bias + tmin の場合に制約計算が正しくなくなるが、bias計算方法と
パラメーターの制約により、そのような事態は発生しない。
Costello Standards Track [Page 12]
RFC 3492 IDNA Punycode March 2003
入力に非常に大きな値が含まれている場合または入力が非常に長い場合に、
無効な出力の生成を回避するために、オーバーフローの検査が必要である。
外側のループの最後にあるdeltaの増加(increment)処理はオーバーフロー
しない。なぜなら、deltaを増加させるまでは delta < length(input) であり、
length(input)は常に表現可能(representable)であると想定されるからである。
nの増加処理はオーバーフローする可能性があるが、それは h == length(input)
の場合だけである。nがオーバーフローした場合、処理は終了となる。
6.4 オーバーフローの処理
IDNAにおいて、有効なIDNAラベル全てをオーバーフロー無しで処理するには
26ビットの符号無し(unsigned)整数があれば充分である。27ビットのdeltaを
必要とする文字列は、コードポイントの限界(0..10FFFF)を越えるか、
ラベル長の限界(63文字)を越えるかのどちらかとなるからである。
しかし、入力は必ずしも有効なIDNAラベルではないため、オーバー
フローの処理は必要である。
プログラミング言語がオーバーフロー検知を提供しない場合、以下に述べる
手法を使用することができる。A、B、Cは表現可能な負でない整数で、Cは
ゼロでないとする。その場合、B > maxint - Aの場合にだけA+Bはオーバー
フローする。また、B > (maxint - A) div Cの場合にだけA + (B * C)は
オーバーフローする。ここで、maxintはmaxint + 1が表現不可能な整数の
最大値である。この手法をC言語で実証したものについては付録C "Punycodeの
実装例"を参照のこと。
セクション6.2と6.3で示したデコーディングアルゴリズム、エンコーディング
アルゴリズムは、オーバーフローが発生した時点でそれを検知し、オーバーフロー
処理を行う。別の方法として、オーバーフロー発生を抑制するために、入力に
制限を課すことが挙げられる。例えば、エンコーダーが入力されたコードポイントが
Mを越えていないこと、および入力長がLを越えていないことを確認済みであれば、
deltaは(M - initial_n) * (L + 1)を越えることはないため、整数を保存する
変数がこの大きな値を表現可能であれば、オーバーフローは発生しない。
このオーバーフロー抑制という方法は、オーバーフロー検知を使用する方法に
比べて、より多くの制限を入力に課すことになるが、幾つかのプログラミング
言語ではより簡便であると見なされるかもしれない。
理論的には、デコーダーの場合にも、可変長整数における数字の数を制限する
ことにより(これは、最も内側のループで繰り返しの回数を制限することである)、
類似した方法を採ることができる。しかし、与えられたdeltaを表現するために
充分な桁数で、(補正処理のために)はるかに大きなdeltaを表現できることが
時折ある。したがって、この方法はおそらく、32ビットよりも大きな整数を
必要とするだろう。
Costello Standards Track [Page 13]
RFC 3492 IDNA Punycode March 2003
デコーダーが使用できるもう一つの方法として、オーバーフロー発生を許容
しておき、最終的に出力される文字を再度エンコーディングし、それを
デコーダーの入力と比較することによってオーバーフロー発生を検査する
というものが挙げられる。(大文字小文字を区別しないASCII比較を使用して)
両者が一致しない場合は、オーバーフローが発生している。この後処理型
オーバーフロー検知方式(delayed-detection)は、即時型オーバーフロー検知
方式(immediate-detection)に比べて入力に課す制約はないため、幾つかの
プログラミング言語ではより簡便であると見なされるかもしれない。
実際、デコーダーがINDAのToUnicode処理[IDNA]内部だけでしか使用されない
のであれば、オーバーフローを検査する必要は全くない。ToUnicode処理は
より上位レベルで再度エンコーディングと比較を実行し、そこで一致しなければ
Punycodeのデコーダーが失敗したのと同じ結果となるからである。
7. Punycode例
7.1 文字列の例
以下に示すPunycodeエンコーディングでは、ACEプレフィックスは表示されない。
1行で表示するには長すぎる文字列については、改行が挿入される場所に
バックスラッシュが示される。
初めに示す幾つかの例は全て"Why can't they just speak in <language>?"
という文章を変換したものである。(Michael Kaplanの"地方"ページ[PROVINCIAL]
から無償提供された)。単語の分割点(word break)と句読点については、
ドメイン名でしばしばそのように処理されることにあわせて除去した。
(A) アラビア語 (エジプト語): ليهمابتكلموشعابي؟
u+0644 u+064A u+0647 u+0645 u+0627 u+0628 u+062A u+0643 u+0644
u+0645 u+0648 u+0634 u+0639 u+0631 u+0628 u+064A u+061F
Punycode: egbpdaj6bu4bxfgehfvwxn
(B) 中国語 (簡体字): 他们为什么不说中文
u+4ED6 u+4EEC u+4E3A u+4EC0 u+4E48 u+4E0D u+8BF4 u+4E2D u+6587
Punycode: ihqwcrb4cv8a8dqg056pqjye
(C) 中国語 (繁体字): 他們爲什麽不說中文
u+4ED6 u+5011 u+7232 u+4EC0 u+9EBD u+4E0D u+8AAA u+4E2D u+6587
Punycode: ihqwctvzc91f659drss3x8bo0yb
(D) チェコ語: Pročprostěnemluvíčesky
U+0050 u+0072 u+006F u+010D u+0070 u+0072 u+006F u+0073 u+0074
u+011B u+006E u+0065 u+006D u+006C u+0075 u+0076 u+00ED u+010D
u+0065 u+0073 u+006B u+0079
Punycode: Proprostnemluvesky-uyb24dma41a
Costello Standards Track [Page 14]
RFC 3492 IDNA Punycode March 2003
(E) ヘブライ語: למההםפשוטלאמדבריםעברית
u+05DC u+05DE u+05D4 u+05D4 u+05DD u+05E4 u+05E9 u+05D5 u+05D8
u+05DC u+05D0 u+05DE u+05D3 u+05D1 u+05E8 u+05D9 u+05DD u+05E2
u+05D1 u+05E8 u+05D9 u+05EA
Punycode: 4dbcagdahymbxekheh6e0a7fei0b
(F) ヒンズー語 (デバナーガリ文字): यहलोगहिन्दऺक्योंनहऺंबोलसकतेहैं
u+092F u+0939 u+0932 u+094B u+0917 u+0939 u+093F u+0928 u+094D
u+0926 u+0940 u+0915 u+094D u+092F u+094B u+0902 u+0928 u+0939
u+0940 u+0902 u+092C u+094B u+0932 u+0938 u+0915 u+0924 u+0947
u+0939 u+0948 u+0902
Punycode: i1baa7eci9glrd9b2ae1bj0hfcgg6iyaf8o0a1dig0cd
(G) 日本語 (漢字と平仮名): なぜみんな日本語を話してくれないのか
u+306A u+305C u+307F u+3093 u+306A u+65E5 u+672C u+8A9E u+3092
u+8A71 u+3057 u+3066 u+304F u+308C u+306A u+3044 u+306E u+304B
Punycode: n8jok5ay5dzabd5bym9f0cm5685rrjetr6pdxa
(H) 韓国語 (ハングル音節): 세계의모든사람들이한국어를이해한다면얼마나좋을까
u+C138 u+ACC4 u+C758 u+BAA8 u+B4E0 u+C0AC u+B78C u+B4E4 u+C774
u+D55C u+AD6D u+C5B4 u+B97C u+C774 u+D574 u+D55C u+B2E4 u+BA74
u+C5BC u+B9C8 u+B098 u+C88B u+C744 u+AE4C
Punycode: 989aomsvi5e83db1d2a355cv1e0vak1dwrv93d5xbh15a0dt30a5j\
psd879ccm6fea98c
(I) ロシア語 (キリル文字): почемужеонинеговорятпорусски
U+043F u+043E u+0447 u+0435 u+043C u+0443 u+0436 u+0435 u+043E
u+043D u+0438 u+043D u+0435 u+0433 u+043E u+0432 u+043E u+0440
u+044F u+0442 u+043F u+043E u+0440 u+0443 u+0441 u+0441 u+043A
u+0438
Punycode: b1abfaaepdrnnbgefbaDotcwatmq2g4l
(J) スペイン語: PorquénopuedensimplementehablarenEspañol
U+0050 u+006F u+0072 u+0071 u+0075 u+00E9 u+006E u+006F u+0070
u+0075 u+0065 u+0064 u+0065 u+006E u+0073 u+0069 u+006D u+0070
u+006C u+0065 u+006D u+0065 u+006E u+0074 u+0065 u+0068 u+0061
u+0062 u+006C u+0061 u+0072 u+0065 u+006E U+0045 u+0073 u+0070
u+0061 u+00F1 u+006F u+006C
Punycode: PorqunopuedensimplementehablarenEspaol-fmd56a
(K) ベトナム語: TạisaohọkhôngthểchỉnóitiếngViệt
U+0054 u+1EA1 u+0069 u+0073 u+0061 u+006F u+0068 u+1ECD u+006B
u+0068 u+00F4 u+006E u+0067 u+0074 u+0068 u+1EC3 u+0063 u+0068
u+1EC9 u+006E u+00F3 u+0069 u+0074 u+0069 u+1EBF u+006E u+0067
U+0056 u+0069 u+1EC7 u+0074
Punycode: TisaohkhngthchnitingVit-kjcr8268qyxafd2f1b9g
Costello Standards Track [Page 15]
RFC 3492 IDNA Punycode March 2003
次に示す幾つかの例は、全て日本の音楽アーティスト名、歌の名前、テレビ
番組名である。これらを例として挙げた理由は、単に著者がたまたま手近に
これらの情報を持っていたからである。(しかし、日本語は英数字、仮名、
漢字、それらが多様に混在した文字列の例を提供するのに便利である)。
(L) 3年B組金八先生
u+0033 u+5E74 U+0042 u+7D44 u+91D1 u+516B u+5148 u+751F
Punycode: 3B-ww4c5e180e575a65lsy2b
(M) 安室奈美恵-with-SUPER-MONKEYS
u+5B89 u+5BA4 u+5948 u+7F8E u+6075 u+002D u+0077 u+0069 u+0074
u+0068 u+002D U+0053 U+0055 U+0050 U+0045 U+0052 u+002D U+004D
U+004F U+004E U+004B U+0045 U+0059 U+0053
Punycode: -with-SUPER-MONKEYS-pc58ag80a8qai00g7n9n
(N) Hello-Another-Way-それぞれの場所
U+0048 u+0065 u+006C u+006C u+006F u+002D U+0041 u+006E u+006F
u+0074 u+0068 u+0065 u+0072 u+002D U+0057 u+0061 u+0079 u+002D
u+305D u+308C u+305E u+308C u+306E u+5834 u+6240
Punycode: Hello-Another-Way--fc4qua05auwb3674vfr0b
(O) ひとつ屋根の下2
u+3072 u+3068 u+3064 u+5C4B u+6839 u+306E u+4E0B u+0032
Punycode: 2-u9tlzr9756bt3uc0v
(P) MajiでKoiする5秒前
U+004D u+0061 u+006A u+0069 u+3067 U+004B u+006F u+0069 u+3059
u+308B u+0035 u+79D2 u+524D
Punycode: MajiKoi5-783gue6qz075azm5e
(Q) パフィーdeルンバ
u+30D1 u+30D5 u+30A3 u+30FC u+0064 u+0065 u+30EB u+30F3 u+30D0
Punycode: de-jg4avhby1noc0d
(R) そのスピードで
u+305D u+306E u+30B9 u+30D4 u+30FC u+30C9 u+3067
Punycode: d9juau41awczczp
最後に示す例は、ホスト名ラベルに関する既存のルールに反するASCII文字列
である。(これはIDNA用の例としては妥当なものではない。なぜなら、IDNAは
決して何も制約が無い(pure)ASCIIラベルをエンコードしないからである)。
(S) -> $1.00 <-
u+002D u+003E u+0020 u+0024 u+0031 u+002E u+0030 u+0030 u+0020
u+003C u+002D
Punycode: -> $1.00 <--
Costello Standards Track [Page 16]
RFC 3492 IDNA Punycode March 2003
7.2 デコーディング処理の検証
以下の検証において、処理を進めるデコーダーの状態は、拡張文字列に
含まれるコードポイントを表現する16進数の値の並びで示される。
アスタリスクは、一番最後に挿入されたコードポイントの直後に現れ、
n(アスタリスク直前の値)とi(アスタリスク直後の値)の両方を示す。他の
数値は10進数で表現される。
セクション7.1の例(B)をデコーディング処理する場合の検証は以下のとおり
である。
nは128、iは0、biasは72である。
入力は"ihqwcrb4cv8a8dqg056pqjye"である。
区切り文字は存在しないので、拡張文字列は空(empty)で処理が開始される。
delta "ihq"は19853にデコードされる。
biasは21になる。
4E0D *
delta "wc"は64にデコードされる。
biasは20になる。
4E0D 4E2D *
delta "rb"は37にデコードされる。
biasは13になる。
4E3A * 4E0D 4E2D
delta "4c"は56にデコードされる。
biasは17になる。
4E3A 4E48 * 4E0D 4E2D
delta "v8a"は599にデコードされる。
biasは32になる。
4E3A 4EC0 * 4E48 4E0D 4E2D
delta "8d"は130にデコードされる。
biasは23になる。
4ED6 * 4E3A 4EC0 4E48 4E0D 4E2D
delta "qg"は154にデコードされる。
biasは25になる。
4ED6 4EEC * 4E3A 4EC0 4E48 4E0D 4E2D
delta "056p"は46301にデコードされる。
biasは84になる。
4ED6 4EEC 4E3A 4EC0 4E48 4E0D 4E2D 6587 *
delta "qjye"は88531にデコードされる。
biasは90になる。
4ED6 4EEC 4E3A 4EC0 4E48 4E0D 8BF4 * 4E2D 6587
Costello Standards Track [Page 17]
RFC 3492 IDNA Punycode March 2003
セクション7.1の例(L)をデコーディング処理する場合の検証は以下のとおり
である。
nは128、iは0、biasは72である。
入力は"3B-ww4c5e180e575a65lsy2b"である。
そのまま文字として表現されている部分は"3B-"であるから、以下の拡張文字列
から処理が開始される。
0033 0042
delta "ww4c"は62042にデコードされる。
biasは27になる。
0033 0042 5148 *
delta "5e"は139にデコードされる。
biasは24になる。
0033 0042 516B * 5148
delta "180e"は16683にデコードされる。
biasは67になる。
0033 5E74 * 0042 516B 5148
delta "575a"は34821にデコードされる。
biasは82になる。
0033 5E74 0042 516B 5148 751F *
delta "65l"は14592にデコードされる。
biasは67になる。
0033 5E74 0042 7D44 * 516B 5148 751F
delta "sy2b"は42088にデコードされる。
biasは84になる。
0033 5E74 0042 7D44 91D1 * 516B 5148 751F
Costello Standards Track [Page 18]
RFC 3492 IDNA Punycode March 2003
7.3 エンコーディング処理の検証
以下の検証において、コードポイント値は16進数で表記され、他の数値は
10進数で表記される。
セクション7.1の例(B)をエンコーディング処理する場合の検証は以下のとおり
である。
biasは72である。
入力は以下のとおりであり、基本コードポイントは存在しないので、そのまま
文字として表現されている部分は存在しない。
4ED6 4EEC 4E3A 4EC0 4E48 4E0D 8BF4 4E2D 6587
挿入されるべき次のコードポイントは4E0Dである。
deltaは19853になる必要があるので、"ihq"とエンコードされる。
biasは21になる。
挿入されるべき次のコードポイントは4E2Dである。
deltaは64になる必要があるので、"wc"とエンコードされる。
biasは20になる。
挿入されるべき次のコードポイントは4E3Aである。
deltaは64になる必要があるので、"rb"とエンコードされる。
biasは13になる。
挿入されるべき次のコードポイントは4E48である。
deltaは64になる必要があるので、"4c"とエンコードされる。
biasは17になる。
挿入されるべき次のコードポイントは4EC0である。
deltaは599になる必要があるので、"v8a"とエンコードされる。
biasは32になる。
挿入されるべき次のコードポイントは4ED6である。
deltaは599になる必要があるので、"8d"とエンコードされる。
biasは23になる。
挿入されるべき次のコードポイントは4EECである。
deltaは154になる必要があるので、"qg"とエンコードされる。
biasは25になる。
挿入されるべき次のコードポイントは6587である。
deltaは154になる必要があるので、"056p"とエンコードされる。
biasは84になる。
挿入されるべき次のコードポイントは8BF4である。
deltaは154になる必要があるので、"qjye"とエンコードされる。
biasは90になる。
出力は"ihqwcrb4cv8a8dqg056pqjye"になる。
Costello Standards Track [Page 19]
RFC 3492 IDNA Punycode March 2003
セクション7.1の例(L)をエンコーディング処理する場合の検証は以下のとおり
である。
biasは72である。
入力は以下のとおりである。
0033 5E74 0042 7D44 91D1 516B 5148 751F
基本コードポイント(0033, 0042)はそのまま文字としてコピーされるので、
"3B-"となる。
挿入されるべき次のコードポイントは5148である。
deltaは62042になる必要があるので、"ww4c"とエンコードされる。
biasは27になる。
挿入されるべき次のコードポイントは516Bである。
deltaは139になる必要があるので、"5e"とエンコードされる(*2)。
biasは24になる。
《脚注》
*2: "5e"とエンコードされる。
原文では"encodes as 516B"と書かれているが、ここは文脈から原文の
記述が誤っていることが明らかであるため、訳文では修正している。
|
挿入されるべき次のコードポイントは5E74である。
deltaは16683になる必要があるので、"180e"とエンコードされる。
biasは67になる。
挿入されるべき次のコードポイントは751Fである。
deltaは34821になる必要があるので、"575a"とエンコードされる。
biasは82になる。
挿入されるべき次のコードポイントは7D44である。
deltaは14592になる必要があるので、"65l"とエンコードされる。
biasは67になる。
挿入されるべき次のコードポイントは91D1である。
deltaは42088になる必要があるので、"sy2b"とエンコードされる。
biasは84になる。
出力は "3B-ww4c5e180e575a65lsy2b"となる。
8. セキュリティーに関する考察
ユーザーは、DNSにおいて各ドメイン名がそれぞれ単一の権威(authority)に
よって制御されることを期待する。ドメインラベルとして使用されるUnicode
文字列が複数のACEラベルに変換される可能性がある場合、1つの国際化
ドメイン名が複数のASCIIドメイン名に変換される可能性がある。複数の
ASCIIドメイン名はそれぞれ異なる権威によって制御されるかもしれないため、
その中の幾つかは、本来他に送られるべきサービスリクエストをハイジャック
するような偽装をする可能性がある。これらの可能性を排除するため、
PunycodeはUnicode文字列それぞれが単一のエンコーディングを持つように
設計されている。
しかし、依然として"同じ"文章に対して複数のUnicode表現が存在する可能性が
残される。これは"同じ"という様々な定義に由来するものである。この問題は
正規化という話題の下で、Unicode標準に対する幾つかの拡張を行う方向で
努力がなされている。この作業をドメイン名に対して適用したものが
Nameprep[NAMEPREP]である。
Costello Standards Track [Page 20]
RFC 3492 IDNA Punycode March 2003
9. 参考文献
9.1 必須の参考文献
[RFC2119] Bradner, S., "Key words for use in RFCs to Indicate
Requirement Levels", BCP 14, RFC 2119, March 1997.
9.2 有用な参考文献
[RFC952] Harrenstien, K., Stahl, M. and E. Feinler, "DOD Internet
Host Table Specification", RFC 952, October 1985.
[RFC1034] Mockapetris, P., "Domain Names - Concepts and
Facilities", STD 13, RFC 1034, November 1987.
[IDNA] Faltstrom, P., Hoffman, P. and A. Costello,
"Internationalizing Domain Names in Applications
(IDNA)", RFC 3490, March 2003.
[NAMEPREP] Hoffman, P. and M. Blanchet, "Nameprep: A Stringprep
Profile for Internationalized Domain Names (IDN)", RFC
3491, March 2003.
[ASCII] Cerf, V., "ASCII format for Network Interchange", RFC
20, October 1969.
[PROVINCIAL] Kaplan, M., "The 'anyone can be provincial!' page",
http://www.trigeminal.com/samples/provincial.html.
[UNICODE] The Unicode Consortium, "The Unicode Standard",
http://www.unicode.org/unicode/standard/standard.html.
Costello Standards Track [Page 21]
RFC 3492 IDNA Punycode March 2003
A. 文字種注釈
大文字小文字を区別しない文字列に対してPunycodeを使用するために、
上位層では、Punycodeエンコーディングに先立ち、文字列の文字種統一を
行う必要がある。エンコードされた文字列では、大文字と小文字を混在して
使用可能であり、エンコードされた文字列を表示する際に、文字種が統一
された文字列をどのように文字種混在の文字列に変換したかを示す注釈として
使用される。しかし、文字種注釈は[IDNA]で規定されるToASCII処理と
ToUnicode処理では使用されないので、IDNAの実装者はこの付録を無視できる
ことに注意してもらいたい。
基本コードポイントは、混在した文字種を直接使用することができる。
デコーダーはこれらのコードポイントを文字通りコピーするので、小文字の
コードポイントは小文字のまま残され、大文字のコードポイントは大文字の
まま残される。非基本コードポイントは、それぞれdeltaで表現される。
deltaは基本コードポイントの並びで表現され、その最後で注釈を提供する。
大文字であった場合には、(可能であれば)非基本コードポイントを大文字に
変換し、小文字であった場合には、(可能であれば)非基本コードポイントを
小文字に変換することを示す。
これらの注釈は、デコーダーから返されるコードポイントを変更しない。
注釈は独立して返され、その処理を呼び出したもの(caller)はその値を
使用するか無視するかを選択する。エンコーダーはコードポイントに加えて、
注釈を受理できる。しかし注釈はASCII文字の大文字/小文字の形態に影響を
与える以外には、出力を変更しない。
Punycodeエンコーダーとデコーダーはこれらの注釈をサポートする必要はなく、
また上位層もこれらを使用する必要はない。
B. 免責条項と使用許諾
本文書全体またはその一部(擬似コードとCコードも含む)について、著者は
一切の保証を行わないし、その使用の結果生じたあらゆる損害について責任を
負わない。著者はこれらを任意の方法で使用、修正、配布を確定的に許可する
(irrevocable permission)。ただし、他者が自由にこれらを使用、修正、配布
する権限を損なわないこと、またこれらから派生したものを再配布する際には、
著者やバージョン情報に関して誤解を招く情報を含めないことが条件である。
また、派生物の使用許諾条件がこれらのものと同様である必要はない。
Costello Standards Track [Page 22]
RFC 3492 IDNA Punycode March 2003
C. Punycodeの実装例
/*
punycode.c from RFC 3492
http://www.nicemice.net/idn/
Adam M. Costello
http://www.nicemice.net/amc/
This is ANSI C code (C89) implementing Punycode (RFC 3492).
*/
/************************************************************/
/* Public interface (would normally go in its own .h file): */
enum punycode_status {
punycode_success,
punycode_bad_input, /* Input is invalid. */
punycode_big_output, /* Output would exceed the space provided. */
punycode_overflow /* Input needs wider integers to process. */
};
typedef unsigned int punycode_uint;
typedef unsigned long punycode_uint;
enum punycode_status punycode_encode(
punycode_uint input_length,
const punycode_uint input[],
const unsigned char case_flags[],
punycode_uint *output_length,
char output[] );
/* punycode_encode() converts Unicode to Punycode. The input */
/* is represented as an array of Unicode code points (not code */
/* units; surrogate pairs are not allowed), and the output */
/* will be represented as an array of ASCII code points. The */
/* output string is *not* null-terminated; it will contain */
/* zeros if and only if the input contains zeros. (Of course */
/* the caller can leave room for a terminator and add one if */
/* needed.) The input_length is the number of code points in */
/* the input. The output_length is an in/out argument: the */
/* caller passes in the maximum number of code points that it */
Costello Standards Track [Page 23]
RFC 3492 IDNA Punycode March 2003
/* can receive, and on successful return it will contain the */
/* number of code points actually output. The case_flags array */
/* holds input_length boolean values, where nonzero suggests that */
/* the corresponding Unicode character be forced to uppercase */
/* after being decoded (if possible), and zero suggests that */
/* it be forced to lowercase (if possible). ASCII code points */
/* are encoded literally, except that ASCII letters are forced */
/* to uppercase or lowercase according to the corresponding */
/* uppercase flags. If case_flags is a null pointer then ASCII */
/* letters are left as they are, and other code points are */
/* treated as if their uppercase flags were zero. The return */
/* value can be any of the punycode_status values defined above */
/* except punycode_bad_input; if not punycode_success, then */
/* output_size and output might contain garbage. */
enum punycode_status punycode_decode(
punycode_uint input_length,
const char input[],
punycode_uint *output_length,
punycode_uint output[],
unsigned char case_flags[] );
/* punycode_decode() converts Punycode to Unicode. The input is */
/* represented as an array of ASCII code points, and the output */
/* will be represented as an array of Unicode code points. The */
/* input_length is the number of code points in the input. The */
/* output_length is an in/out argument: the caller passes in */
/* the maximum number of code points that it can receive, and */
/* on successful return it will contain the actual number of */
/* code points output. The case_flags array needs room for at */
/* least output_length values, or it can be a null pointer if the */
/* case information is not needed. A nonzero flag suggests that */
/* the corresponding Unicode character be forced to uppercase */
/* by the caller (if possible), while zero suggests that it be */
/* forced to lowercase (if possible). ASCII code points are */
/* output already in the proper case, but their flags will be set */
/* appropriately so that applying the flags would be harmless. */
/* The return value can be any of the punycode_status values */
/* defined above; if not punycode_success, then output_length, */
/* output, and case_flags might contain garbage. On success, the */
/* decoder will never need to write an output_length greater than */
/* input_length, because of how the encoding is defined. */
/**********************************************************/
/* Implementation (would normally go in its own .c file): */
Costello Standards Track [Page 24]
RFC 3492 IDNA Punycode March 2003
/*** Bootstring parameters for Punycode ***/
enum { base = 36, tmin = 1, tmax = 26, skew = 38, damp = 700,
initial_bias = 72, initial_n = 0x80, delimiter = 0x2D };
/* basic(cp) tests whether cp is a basic code point: */
/* delim(cp) tests whether cp is a delimiter: */
/* decode_digit(cp) returns the numeric value of a basic code */
/* point (for use in representing integers) in the range 0 to */
/* base-1, or base if cp is does not represent a value. */
static punycode_uint decode_digit(punycode_uint cp)
{
return cp - 48 < 10 ? cp - 22 : cp - 65 < 26 ? cp - 65 :
cp - 97 < 26 ? cp - 97 : base;
}
/* encode_digit(d,flag) returns the basic code point whose value */
/* (when used for representing integers) is d, which needs to be in */
/* the range 0 to base-1. The lowercase form is used unless flag is */
/* nonzero, in which case the uppercase form is used. The behavior */
/* is undefined if flag is nonzero and digit d has no uppercase form. */
static char encode_digit(punycode_uint d, int flag)
{
return d + 22 + 75 * (d < 26) - ((flag != 0) << 5);
/* 0..25 map to ASCII a..z or A..Z */
/* 26..35 map to ASCII 0..9 */
}
/* flagged(bcp) tests whether a basic code point is flagged */
/* (uppercase). The behavior is undefined if bcp is not a */
/* basic code point. */
/* encode_basic(bcp,flag) forces a basic code point to lowercase */
/* if flag is zero, uppercase if flag is nonzero, and returns */
/* the resulting code point. The code point is unchanged if it */
/* is caseless. The behavior is undefined if bcp is not a basic */
/* code point. */
static char encode_basic(punycode_uint bcp, int flag)
{
Costello Standards Track [Page 25]
RFC 3492 IDNA Punycode March 2003
bcp -= (bcp - 97 < 26) << 5;
return bcp + ((!flag && (bcp - 65 < 26)) << 5);
}
/*** Platform-specific constants ***/
/* maxint is the maximum value of a punycode_uint variable: */
static const punycode_uint maxint = -1;
/* Because maxint is unsigned, -1 becomes the maximum value. */
/*** Bias adaptation function ***/
static punycode_uint adapt(
punycode_uint delta, punycode_uint numpoints, int firsttime )
{
punycode_uint k;
delta = firsttime ? delta / damp : delta >> 1;
/* delta >> 1 is a faster way of doing delta / 2 */
delta += delta / numpoints;
for (k = 0; delta > ((base - tmin) * tmax) / 2; k += base) {
delta /= base - tmin;
}
return k + (base - tmin + 1) * delta / (delta + skew);
}
/*** Main encode function ***/
enum punycode_status punycode_encode(
punycode_uint input_length,
const punycode_uint input[],
const unsigned char case_flags[],
punycode_uint *output_length,
char output[] )
{
punycode_uint n, delta, h, b, out, max_out, bias, j, m, q, k, t;
/* Initialize the state: */
n = initial_n;
delta = out = 0;
max_out = *output_length;
bias = initial_bias;
/* Handle the basic code points: */
Costello Standards Track [Page 26]
RFC 3492 IDNA Punycode March 2003
for (j = 0; j < input_length; ++j) {
if (basic(input[j])) {
if (max_out - out < 2) return punycode_big_output;
output[out++] =
case_flags ? encode_basic(input[j], case_flags[j]) : input[j];
}
/* else if (input[j] < n) return punycode_bad_input; */
/* (not needed for Punycode with unsigned code points) */
}
h = b = out;
/* h is the number of code points that have been handled, b is the */
/* number of basic code points, and out is the number of characters */
/* that have been output. */
if (b > 0) output[out++] = delimiter;
/* Main encoding loop: */
while (h < input_length) {
/* All non-basic code points < n have been */
/* handled already. Find the next larger one: */
for (m = maxint, j = 0; j < input_length; ++j) {
/* if (basic(input[j])) continue; */
/* (not needed for Punycode) */
if (input[j] >= n && input[j] < m) m = input[j];
}
/* Increase delta enough to advance the decoder's */
/* <n,i> state to <m,0>, but guard against overflow: */
if (m - n > (maxint - delta) / (h + 1)) return punycode_overflow;
delta += (m - n) * (h + 1);
n = m;
for (j = 0; j < input_length; ++j) {
/* Punycode does not need to check whether input[j] is basic: */
if (input[j] < n /* || basic(input[j]) */ ) {
if (++delta == 0) return punycode_overflow;
}
if (input[j] == n) {
/* Represent delta as a generalized variable-length integer: */
for (q = delta, k = base; ; k += base) {
if (out >= max_out) return punycode_big_output;
Costello Standards Track [Page 27]
RFC 3492 IDNA Punycode March 2003
t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */
k >= bias + tmax ? tmax : k - bias;
if (q < t) break;
output[out++] = encode_digit(t + (q - t) % (base - t), 0);
q = (q - t) / (base - t);
}
output[out++] = encode_digit(q, case_flags && case_flags[j]);
bias = adapt(delta, h + 1, h == b);
delta = 0;
++h;
}
}
++delta, ++n;
}
*output_length = out;
return punycode_success;
}
/*** Main decode function ***/
enum punycode_status punycode_decode(
punycode_uint input_length,
const char input[],
punycode_uint *output_length,
punycode_uint output[],
unsigned char case_flags[] )
{
punycode_uint n, out, i, max_out, bias,
b, j, in, oldi, w, k, digit, t;
/* Initialize the state: */
n = initial_n;
out = i = 0;
max_out = *output_length;
bias = initial_bias;
/* Handle the basic code points: Let b be the number of input code */
/* points before the last delimiter, or 0 if there is none, then */
/* copy the first b code points to the output. */
for (b = j = 0; j < input_length; ++j) if (delim(input[j])) b = j;
if (b > max_out) return punycode_big_output;
for (j = 0; j < b; ++j) {
Costello Standards Track [Page 28]
RFC 3492 IDNA Punycode March 2003
if (case_flags) case_flags[out] = flagged(input[j]);
if (!basic(input[j])) return punycode_bad_input;
output[out++] = input[j];
}
/* Main decoding loop: Start just after the last delimiter if any */
/* basic code points were copied; start at the beginning otherwise. */
for (in = b > 0 ? b + 1 : 0; in < input_length; ++out) {
/* in is the index of the next character to be consumed, and */
/* out is the number of code points in the output array. */
/* Decode a generalized variable-length integer into delta, */
/* which gets added to i. The overflow checking is easier */
/* if we increase i as we go, then subtract off its starting */
/* value at the end to obtain delta. */
for (oldi = i, w = 1, k = base; ; k += base) {
if (in >= input_length) return punycode_bad_input;
digit = decode_digit(input[in++]);
if (digit >= base) return punycode_bad_input;
if (digit > (maxint - i) / w) return punycode_overflow;
i += digit * w;
t = k <= bias /* + tmin */ ? tmin : /* +tmin not needed */
k >= bias + tmax ? tmax : k - bias;
if (digit < t) break;
if (w > maxint / (base - t)) return punycode_overflow;
w *= (base - t);
}
bias = adapt(i - oldi, out + 1, oldi == 0);
/* i was supposed to wrap around from out+1 to 0, */
/* incrementing n each time, so we'll fix that now: */
if (i / (out + 1) > maxint - n) return punycode_overflow;
n += i / (out + 1);
i %= (out + 1);
/* Insert n at position i of the output: */
/* not needed for Punycode: */
/* if (decode_digit(n) <= base) return punycode_invalid_input; */
if (out >= max_out) return punycode_big_output;
if (case_flags) {
memmove(case_flags + i + 1, case_flags + i, out - i);
Costello Standards Track [Page 29]
RFC 3492 IDNA Punycode March 2003
/* Case of last character determines uppercase flag: */
case_flags[i] = flagged(input[in - 1]);
}
memmove(output + i + 1, output + i, (out - i) * sizeof *output);
output[i++] = n;
}
*output_length = out;
return punycode_success;
}
/******************************************************************/
/* Wrapper for testing (would normally go in a separate .c file): */
/* For testing, we'll just set some compile-time limits rather than */
/* use malloc(), and set a compile-time option rather than using a */
/* command-line option. */
enum {
unicode_max_length = 256,
ace_max_length = 256
};
static void usage(char **argv)
{
fprintf(stderr,
"\n"
"%s -e reads code points and writes a Punycode string.\n"
"%s -d reads a Punycode string and writes code points.\n"
"\n"
"Input and output are plain text in the native character set.\n"
"Code points are in the form u+hex separated by whitespace.\n"
"Although the specification allows Punycode strings to contain\n"
"any characters from the ASCII repertoire, this test code\n"
"supports only the printable characters, and needs the Punycode\n"
"string to be followed by a newline.\n"
"The case of the u in u+hex is the force-to-uppercase flag.\n"
, argv[0], argv[0]);
exit(EXIT_FAILURE);
}
static void fail(const char *msg)
Costello Standards Track [Page 30]
RFC 3492 IDNA Punycode March 2003
{
fputs(msg,stderr);
exit(EXIT_FAILURE);
}
static const char too_big[] =
"input or output is too large, recompile with larger limits\n";
static const char invalid_input[] = "invalid input\n";
static const char overflow[] = "arithmetic overflow\n";
static const char io_error[] = "I/O error\n";
/* The following string is used to convert printable */
/* characters between ASCII and the native charset: */
static const char print_ascii[] =
"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n"
"\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n\n"
" !\"#$%&'()*+,-./"
"0123456789:;<=>?"
"@ABCDEFGHIJKLMNO"
"PQRSTUVWXYZ[\\]^_"
"`abcdefghijklmno"
"pqrstuvwxyz{|}~\n";
int main(int argc, char **argv)
{
enum punycode_status status;
int r;
unsigned int input_length, output_length, j;
unsigned char case_flags[unicode_max_length];
if (argc != 2) usage(argv);
if (argv[1][0] != '-') usage(argv);
if (argv[1][2] != 0) usage(argv);
if (argv[1][1] == 'e') {
punycode_uint input[unicode_max_length];
unsigned long codept;
char output[ace_max_length+1], uplus[3];
int c;
/* Read the input code points: */
input_length = 0;
for (;;) {
r = scanf("%2s%lx", uplus, &codept);
if (ferror(stdin)) fail(io_error);
Costello Standards Track [Page 31]
RFC 3492 IDNA Punycode March 2003
if (r == EOF || r == 0) break;
if (r != 2 || uplus[1] != '+' || codept > (punycode_uint)-1) {
fail(invalid_input);
}
if (input_length == unicode_max_length) fail(too_big);
if (uplus[0] == 'u') case_flags[input_length] = 0;
else if (uplus[0] == 'U') case_flags[input_length] = 1;
else fail(invalid_input);
input[input_length++] = codept;
}
/* Encode: */
output_length = ace_max_length;
status = punycode_encode(input_length, input, case_flags,
&output_length, output);
if (status == punycode_bad_input) fail(invalid_input);
if (status == punycode_big_output) fail(too_big);
if (status == punycode_overflow) fail(overflow);
assert(status == punycode_success);
/* Convert to native charset and output: */
for (j = 0; j < output_length; ++j) {
c = output[j];
assert(c >= 0 && c <= 127);
if (print_ascii[c] == 0) fail(invalid_input);
output[j] = print_ascii[c];
}
output[j] = 0;
r = puts(output);
if (r == EOF) fail(io_error);
return EXIT_SUCCESS;
}
if (argv[1][1] == 'd') {
char input[ace_max_length+2], *p, *pp;
punycode_uint output[unicode_max_length];
/* Read the Punycode input string and convert to ASCII: */
fgets(input, ace_max_length+2, stdin);
if (ferror(stdin)) fail(io_error);
Costello Standards Track [Page 32]
RFC 3492 IDNA Punycode March 2003
if (feof(stdin)) fail(invalid_input);
input_length = strlen(input) - 1;
if (input[input_length] != '\n') fail(too_big);
input[input_length] = 0;
for (p = input; *p != 0; ++p) {
pp = strchr(print_ascii, *p);
if (pp == 0) fail(invalid_input);
*p = pp - print_ascii;
}
/* Decode: */
output_length = unicode_max_length;
status = punycode_decode(input_length, input, &output_length,
output, case_flags);
if (status == punycode_bad_input) fail(invalid_input);
if (status == punycode_big_output) fail(too_big);
if (status == punycode_overflow) fail(overflow);
assert(status == punycode_success);
/* Output the result: */
for (j = 0; j < output_length; ++j) {
r = printf("%s+%04lX\n",
case_flags[j] ? "U" : "u",
(unsigned long) output[j] );
if (r < 0) fail(io_error);
}
return EXIT_SUCCESS;
}
usage(argv);
return EXIT_SUCCESS; /* not reached, but quiets compiler warning */
}
Costello Standards Track [Page 33]
RFC 3492 IDNA Punycode March 2003
著者の連絡先
Adam M. Costello
University of California, Berkeley
http://www.nicemice.net/amc/
Costello Standards Track [Page 34]
RFC 3492 IDNA Punycode March 2003
完全な著作権表示
Copyright (C) The Internet Society (2003). All Rights Reserved.
This document and translations of it may be copied and furnished to
others, and derivative works that comment on or otherwise explain it
or assist in its implementation may be prepared, copied, published
and distributed, in whole or in part, without restriction of any
kind, provided that the above copyright notice and this paragraph are
included on all such copies and derivative works. However, this
document itself may not be modified in any way, such as by removing
the copyright notice or references to the Internet Society or other
Internet organizations, except as needed for the purpose of
developing Internet standards in which case the procedures for
copyrights defined in the Internet Standards process must be
followed, or as required to translate it into languages other than
English.
The limited permissions granted above are perpetual and will not be
revoked by the Internet Society or its successors or assigns.
This document and the information contained herein is provided on an
"AS IS" basis and THE INTERNET SOCIETY AND THE INTERNET ENGINEERING
TASK FORCE DISCLAIMS ALL WARRANTIES, EXPRESS OR IMPLIED, INCLUDING
BUT NOT LIMITED TO ANY WARRANTY THAT THE USE OF THE INFORMATION
HEREIN WILL NOT INFRINGE ANY RIGHTS OR ANY IMPLIED WARRANTIES OF
MERCHANTABILITY OR FITNESS FOR A PARTICULAR PURPOSE.
謝辞
RFCエディターの活動に対する資金は現在Internet Societyによって
提供されている。
Costello Standards Track [Page 35]