2022-05-17に更新

[RFC3492日本語訳] Punycode: アプリケーションにおいてドメイン名国際化(IDNA)を行うためのUnicodeのBootstringエンコーディング

読了目安:63分

はじめに

この記事は、RFC3492の日本語訳を転載したものです。Punycodeの仕様を参照する上で、JDNA翻訳版と思われる日本語訳ドキュメントが大いに参考になっていたのですが、2020年末からhttp://jdna.jp/へのアクセスができないようで、本ドキュメントも参照できない状態となっていますので、その中身をこちらに転載しています。転載にあたって、一部内容を改変・省略しています。

RFC3492原文:https://datatracker.ietf.org/doc/html/rfc3492
日本語訳(転載元Webアーカイブ):https://web.archive.org/web/20201019220316/http://jdna.jp/survey/rfc/rfc3492j.html

Punycode: アプリケーションにおいてドメイン名国際化(IDNA)を行うためのUnicodeのBootstringエンコーディング

ネットワークワーキンググループ A. Costello
Request for Comments: 3492 Univ. of California, Berkeley
分類: 標準化過程(Standards Track) 2003年3月

本文書の位置づけ

本文書はインターネットコミュニティーのためにインターネット標準化過程にあるプロトコルを規定し、その向上のために議論と提案を求めるものである。このプロトコルの標準化の状況については"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. はじめに

IDNAは国際化ドメイン名をサポートするためのアーキテクチャーを記述している。これは非ASCII文字を含むラベルを、特別なACEプレフィックスで始まるASCII文字だけで構成されたACEラベルによって表現可能にするものである。プレフィックスの後に続けられたラベルの残りは、ある制約条件を満たすようにPunycodeでエンコードされたUnicode文字列である。プレフィックスと制約条件の詳細については、IDNAとNAMEPREPを参照のこと。

Punycodeは、Bootstringと呼ばれる、より一般的なアルゴリズムの適用事例(instance)である。このアルゴリズムは、より大きな文字集合に属するコードポイントの並びを、小さな"基本(basic)"コードポイントの集合に含まれるコードポイントの並びによって一意に表現可能にするものである。Punycodeは、Bootstringの特定のパラメーター値をIDNA向けに適切に設定したものである。

1.1 機能的特徴

Bootstringは、以下の機能的特徴を持つように設計された。

  • 完全性: 拡張文字列(任意のコードポイントの並び)は、基本文字列(基本コードポイントの並び)によって表現できる。許容される文字列、文字列の長さ等の制約は、上位層で導入可能である。

  • 一意性: 与えられた拡張文字列を表現する基本文字列は一つしか存在しない。

  • 可逆性: 任意の拡張文字列を基本文字列に変換した場合、その基本文字列から変換前の拡張文字列を再生可能である。

  • 効率的エンコーディング: 拡張文字列の長さと、それを表現する基本文字列の長さの比率は小さい。処理対象がドメイン名であることを考慮すると、これは重要な意味を持つ。なぜなら、RFC1034はドメインラベルを63文字に制限しているからである。

  • 単純性: エンコーディングとデコーディングのアルゴリズムは、実装には充分に単純なものである。効率性と単純性のゴールは二律背反するものだが、Bootstringはその間で優れたバランスを取ることを目標としている。

  • 読みやすさ: 拡張文字列に含まれる基本コードポイントは、変換後の基本文字列においてもそのまま表現される。(主たる意図は効率を改善することであり、読みやすさを改善することではないにしても)。

PunycodeはIDNAのToASCII処理とToUnicode処理で使用されない付加的機能もサポート可能である。エンコーディング前に拡張文字列の大文字、小文字の文字種が統一されている(case-folded)場合、文字種が統一された文字列をどのように文字種混在の文字列に変換したかを示すために、基本文字列は大文字と小文字が混在した文字列を使用することができる。付録A "文字種注釈(Mixed-case annotation)"を参照のこと。

1.2 プロトコルとの関係

PunycodeはドメインラベルをASCIIに変換するために、IDNAプロトコルで使用されるものであり、他の目的のためには設計されていない。任意の文章を処理するために設計されたものではないことをここに明記する。

2. 用語

本文書におけるキーワード"しなければならない(MUST)"、"してはならない(MUST NOT)"、"要求される(REQUIRED)"、"するものとする(SHALL)"、"しないものとする(SHALL NOT)"、"すべきである(SHOULD)"、"すべきでない(SHOULD NOT)"、"推奨される(RECOMMENDED)"、"してもよい(MAY)"、"任意である(OPTIONAL)"は、BCP14、RFC2119に記述されているとおりに解釈される。

コードポイントは符号化文字集合(coded character set)において、文字に関連付けられる整数値(integral value)である。

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言語のように)一番深い(内側の)ループから脱出するものである。

オーバーフローは、整数を保存する変数の最大値を超える値を計算しようとする試みである。

3. Bootstringの説明

Bootstringは、任意のコードポイントの並び("拡張文字列")を、基本コードポイントの並び("基本文字列")として表現する。本セクションは、この表現形式について記述する。セクション6"Bootstringアルゴリズム"では、このアルゴリズムを擬似的なコードとして提示する。セクション7.2"デコーディング処理の検証"7.3"エンコーディング処理の検証"では、入力例に対するアルゴリズムの処理を検証する。

以下のセクションでは、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毎に拡張文字列に挿入していき、最終的にはデコードされた文字列に到達する。

この処理の主要な部分は、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つの整数の境界はわからなくなる。

一般化可変長表現は、この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の範囲に制限される。

値を制限するとは、与式が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の間の値に設定することである。(これは最上位桁であると予想される桁が不要になるという希望と、その桁が最上位桁ではないという危険をバランスさせるということである)。

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のUTF-16エンコーディングが使用するために予約されているD800..DFFFは対象ではない)。

基本コードポイントは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のルールに準拠する。

デコーダーは、ある文字について大文字と小文字の形態を(大文字と小文字が混在している状態も含めて)認識できなければならない(MUST)。エンコーダーは、文字種注釈(付録A参照)を使用していない限り、出力を大文字または小文字だけの形態にすべきである(SHOULD)

おそらくは、ほとんどのユーザーはエンコードされた文字列を直接書いたりタイプしたりはしないだろう(むしろカット&ペーストをするだろうから)。しかし、直接書いたりタイプしたりするユーザーに対しては、以下に示すように視覚的にどちらとも取れる可能性がある文字の集合があることを警告する必要がある。

G 6
I l 1
O 0
S 5
U V
Z 2

このような不明瞭さは通常文脈から判断して解決される。しかし、Punycodeでエンコードされた文字列の場合、そのような文脈は人間に対して何も示されない。

6. Bootstringアルゴリズム

擬似コードの幾つかの部分は、パラメーターが(Punycodeに適した)ある条件を満たす場合には省略できる。省略可能な部分は{括弧}でくくられており、省略可能な条件の説明が、擬似コードのすぐ後ろに記載される。

形式上、コードポイントは整数であるため、擬似コードはコードポイントに対して直接算術的処理が実行可能であると想定している。幾つかのプログラミング言語では、コードポイントと整数を明示的に変換する必要があるかもしれない。

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)はそれらの変数の値を読み出すことなく、上書きするからである。

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つの入力から同じ出力を生成することはできない。

この性質が無ければ、エンコーディングの一意性を保証するために、出力を再度エンコードし、入力と一致するかを検証する必要があっただろう。

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計算方法とパラメーターの制約により、そのような事態は発生しない。

入力に非常に大きな値が含まれている場合または入力が非常に長い場合に、無効な出力の生成を回避するために、オーバーフローの検査が必要である。

外側のループの最後にある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.26.3で示したデコーディングアルゴリズム、エンコーディングアルゴリズムは、オーバーフローが発生した時点でそれを検知し、オーバーフロー処理を行う。別の方法として、オーバーフロー発生を抑制するために、入力に制限を課すことが挙げられる。例えば、エンコーダーが入力されたコードポイントがMを越えていないこと、および入力長がLを越えていないことを確認済みであれば、deltaは(M - initial_n) * (L + 1)を越えることはないため、整数を保存する変数がこの大きな値を表現可能であれば、オーバーフローは発生しない。このオーバーフロー抑制という方法は、オーバーフロー検知を使用する方法に比べて、より多くの制限を入力に課すことになるが、幾つかのプログラミング言語ではより簡便であると見なされるかもしれない。

理論的には、デコーダーの場合にも、可変長整数における数字の数を制限することにより(これは、最も内側のループで繰り返しの回数を制限することである)、類似した方法を採ることができる。しかし、与えられたdeltaを表現するために充分な桁数で、(補正処理のために)はるかに大きなdeltaを表現できることが時折ある。したがって、この方法はおそらく、32ビットよりも大きな整数を必要とするだろう。

デコーダーが使用できるもう一つの方法として、オーバーフロー発生を許容しておき、最終的に出力される文字を再度エンコーディングし、それをデコーダーの入力と比較することによってオーバーフロー発生を検査するというものが挙げられる。(大文字小文字を区別しないASCII比較を使用して)両者が一致しない場合は、オーバーフローが発生している。この後処理型オーバーフロー検知方式(delayed-detection)は、即時型オーバーフロー検知方式(immediate-detection)に比べて入力に課す制約はないため、幾つかのプログラミング言語ではより簡便であると見なされるかもしれない。

実際、デコーダーがINDAのToUnicode処理内部だけでしか使用されないのであれば、オーバーフローを検査する必要は全くない。ToUnicode処理はより上位レベルで再度エンコーディングと比較を実行し、そこで一致しなければPunycodeのデコーダーが失敗したのと同じ結果となるからである。

7. Punycode例

7.1 文字列の例

以下に示すPunycodeエンコーディングでは、ACEプレフィックスは表示されない。1行で表示するには長すぎる文字列については、改行が挿入される場所にバックスラッシュが示される。

初めに示す幾つかの例は全て"Why can't they just speak in (language)?"という文章を変換したものである。(Michael Kaplanの"地方"ページから無償提供された)。単語の分割点(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

(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

次に示す幾つかの例は、全て日本の音楽アーティスト名、歌の名前、テレビ番組名である。これらを例として挙げた理由は、単に著者がたまたま手近にこれらの情報を持っていたからである。(しかし、日本語は英数字、仮名、漢字、それらが多様に混在した文字列の例を提供するのに便利である)。

(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 <--

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

セクション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

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"になる。

セクション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である。

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.

A. 文字種注釈

大文字小文字を区別しない文字列に対してPunycodeを使用するために、上位層では、Punycodeエンコーディングに先立ち、文字列の文字種統一を行う必要がある。エンコードされた文字列では、大文字と小文字を混在して使用可能であり、エンコードされた文字列を表示する際に、文字種が統一された文字列をどのように文字種混在の文字列に変換したかを示す注釈として使用される。しかし、文字種注釈はIDNAで規定されるToASCII処理とToUnicode処理では使用されないので、IDNAの実装者はこの付録を無視できることに注意してもらいたい。

基本コードポイントは、混在した文字種を直接使用することができる。デコーダーはこれらのコードポイントを文字通りコピーするので、小文字のコードポイントは小文字のまま残され、大文字のコードポイントは大文字のまま残される。非基本コードポイントは、それぞれdeltaで表現される。deltaは基本コードポイントの並びで表現され、その最後で注釈を提供する。大文字であった場合には、(可能であれば)非基本コードポイントを大文字に変換し、小文字であった場合には、(可能であれば)非基本コードポイントを小文字に変換することを示す。

これらの注釈は、デコーダーから返されるコードポイントを変更しない。注釈は独立して返され、その処理を呼び出したもの(caller)はその値を使用するか無視するかを選択する。エンコーダーはコードポイントに加えて、注釈を受理できる。しかし注釈はASCII文字の大文字/小文字の形態に影響を与える以外には、出力を変更しない。

Punycodeエンコーダーとデコーダーはこれらの注釈をサポートする必要はなく、また上位層もこれらを使用する必要はない。

B. 免責条項と使用許諾

本文書全体またはその一部(擬似コードとCコードも含む)について、著者は一切の保証を行わないし、その使用の結果生じたあらゆる損害について責任を負わない。著者はこれらを任意の方法で使用、修正、配布を確定的に許可する(irrevocable permission)。ただし、他者が自由にこれらを使用、修正、配布する権限を損なわないこと、またこれらから派生したものを再配布する際には、著者やバージョン情報に関して誤解を招く情報を含めないことが条件である。また、派生物の使用許諾条件がこれらのものと同様である必要はない。

C. Punycodeの実装例

/*
punycode.c from RFC 3492
[http://www.nicemice.net/idn/](http://www.nicemice.net/idn/)
Adam M. Costello
[http://www.nicemice.net/amc/](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     */
    /* 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): */

/*** 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)
{
  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: */

  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;
          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) {
    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);
      /* 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)
{
  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);

      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);
    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 */
}

著者の連絡先

Adam M. Costello
University of California, Berkeley
http://www.nicemice.net/amc/

完全な著作権表示

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によって提供されている。

ツイッターでシェア
みんなに共有、忘れないようにメモ

ウラル

Crieitは誰でも投稿できるサービスです。 是非記事の投稿をお願いします。どんな軽い内容でも投稿できます。

また、「こんな記事が読みたいけど見つからない!」という方は是非記事投稿リクエストボードへ!

有料記事を販売できるようになりました!

こじんまりと作業ログやメモ、進捗を書き残しておきたい方はボード機能をご利用ください。
ボードとは?

コメント