この記事について
この記事は「わいわいswiftc #8」という勉強会で話した内容をまとめ直したものです。
UTF-8
UTF-8という文字エンコーディングがあります。これはUnicodeのコードポイントの列を、バイト列と相互変換する規則の1つです。これを使うことで我々は文字列をデータとして扱っています。Unicodeをバイト列へ変換することをエンコード、バイト列からUnicodeに復元することをデコードと呼びます。
オートマトン
オートマトンという計算のモデルがあります。例えばこのような図で表されます。
https://ja.wikipedia.org/wiki/有限オートマトン
オートマトンには状態と入力があります。入力を受け取ると現在の状態に応じて次の状態に変化します。最終的に入力を受理したり拒否したりします。上図でいえば、緑の丸が状態です。ここでは1から6まで6つの状態があります。矢印の上に書かれているのが入力です。初期状態の1から始めて、「nice」を受け取ると最終的に終了状態の6に到達する事がわかります。
デコードするオートマトン
UTF-8のバイト列をデコードすると、Unicodeのコードポイントが得られるか、不正なバイトシーケンスでエラーとなります。このデコードする手続きを、オートマトンで表現することが出来ます。入力として1バイトずつを受け取り、正しいバイト列であるか、不正であるか結論するオートマトンです。
実装
オートマトンを実装するための方法として、ある状態において、どの文字を受け取ったら、次の状態がどれであるかを表で表現する事ができます。今入力として1バイト受け取ることを考えると、1バイトは0-255の256通りなので、状態を整数で表すとして、以下のように2次元配列で表現できます。
// C言語
int table[][256] = {
{ ... }, // 状態0
{ ... }, // 状態1
{ ... }, // 状態2
...
}
それぞれの配列は、256個の要素を持っています。
実例
最近、正規表現エンジンOnigmoでこれが実際に使われていることを知りました。以下のようになっています。
static const signed char trans[][0x100] = {
{ /* S0 0 1 2 3 4 5 6 7 8 9 a b c d e f */
/* 0 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 1 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 2 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 3 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 4 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 5 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 6 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 7 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 8 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 9 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* a */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* b */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* c */ F, F, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* d */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* e */ 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3,
#ifndef USE_UTF8_31BITS
/* f */ 5, 6, 6, 6, 7, F, F, F, F, F, F, F, F, F, F, F
#else
/* f */ 5, 6, 6, 6, 6, 6, 6, 6, 8, 9, 9, 9,10,11, F, F
#endif
},
AがAcceptで値は-1、FがFailureで値は-2,それ以外は次の状態を表しています。
最後の行がマクロで分岐していますが、以降ではUSE_UTF8_31BITSフラグが無効な方を扱います。
歴史
Onigmoにこのようなコードが実装された経緯を調べました。
2002 正規表現エンジンOnigurumaがリリースされる。
https://en.wikipedia.org/wiki/Oniguruma
2004 RubyがOnigurumaを取り込む。
https://github.com/ruby/ruby/commit/5770336f8be4ac6dbdff43587fda2b508d3786de
2007 Ruby版Onigurumaにオートマトンが実装される。
https://github.com/ruby/ruby/commit/69406aad505414de34dc8b560ac1eadf147b0dbc#diff-3d0809782296d6cdcf6889ddbb19631d
2011 OnigmoがOnigurumaからフォークして生まれる。
https://github.com/k-takata/Onigmo/commit/95e6c10e535f655b87b645ebc3e029a0ec9e242b
2011 OnigmoがRuby版からオートマトンを取り込む。
https://github.com/k-takata/Onigmo/commit/ce13b17b955e0b6dfc6606b1fdbd4755590b360b#diff-67dbe0b8e37d5cc1946b981346e1c0a6
オートマトンの解読
ここからは、オートマトンのコードを詳しく見ていきます。その前に、UTF-8のエンコーディングについて解説します。
UTF-8のエンコーディング
UTF-8のエンコーディングについては、下記のWikipediaの表を見ればわかります。
以下ではこの詳細を説明します。
ASCII互換
UTF-8の最大の魅力はASCII互換なことだと思います。ASCIIコードは0x00から0x7Fまでのコードが使われていますが、これはそのままUnicodeでも同じコードポイントになっており、さらにUTF-8においてもそのまま同じ表現になっています。1バイトは0x00から0xFFまであるので、UTF-8では残りの0x80から0xFFを活用してその他のUnicodeを表します。
この事は表の1段目からも読み取れます。この段はU+0000からU+007Fの表現方法を表しており、ビット列は0xxxxxxxとなっています。これは、最上位ビットは常に0であり、残り7ビットが可変部分である、という事を表しています。よって、このビットパターンが表すバイト値が0x00から0x7Fである事がわかります。
マルチバイト
U+0080以降のコードポイントについては、UTF-8ではマルチバイトで表現します。UTF-8のマルチバイトは、先頭バイトと後続バイトに分類されます。そして、先頭バイトは、2バイト文字の先頭、3バイト文字の先頭、4バイト文字の先頭に分類されています。あるバイト値がどの分類に属しているかは、そのバイト値単体を見て判断できるようにビットが割り当てられています。この仕組のおかげで、あるバイト列の適当な場所から読み始めても、先頭バイトが表れるまでスキップして、そこからデコードすることで正しくデコードする事ができます。
マルチバイト文字の構成を見てみましょう。表の2段目では2バイト文字のパターンが書いてあります。ビット列のところを見ると、110yyyyx, 10xxxxxxとなっています。3バイト文字では1110yyyy, 10yxxxxx, 10xxxxxx、4バイト文字では11110yyy, 10yyxxxx, 10xxxxxx, 10xxxxxxとなっています。面白いことに、先頭バイトについては、2バイト文字では1が2個、3バイト文字では1が3個、4バイト文字では1が4個並んでいます。わかりやすいですね。そして、後続バイトは10から始まっています。このように、バイトの分類は先頭のビットを見ればわかるようになっています。
バイトの先頭部分のビットが分類を表しており、余った部分はデータを表すのに使われます。2バイト文字では、先頭バイトの先頭ビット110以降の5ビット, 後続バイトの先頭ビット10以降の6ビット、合わせて11ビットがデータを表すために使えます。この11ビットというビット幅は、表の有効ビットのところにも書かれています。UTF-8では、このデータ部分にUnicodeのコードポイントをそのまま格納します。11ビットで表せる数は0x0000から0x07FFなので、ビット幅だけで考えれば、UTF-8の2バイト文字が表せるコードポイントはU+0000からU+07FFということになります。
重複排除
実際にはここでもう1手修正し、より短いバイト列での表現との重複排除を行います。2バイトで表せるU+0000からU+07FFは、1バイトで表せる7ビットのコードポイント、U+0000からU+007Fを重複して含んでいます。UTF-8ではこれを禁止しています。すなわち、あるコードポイントをエンコードする際は、可能な限り最小のバイト数で表現する事に決まっており、もし冗長な表現が出現した場合は、それは不正なバイトシーケンスである、ということです。
この重複排除を加味すると、2バイト文字のビットパターンに制約が追加されます。7ビットで表せるコードポイントが禁止されるという事は言い換えると、必ず8〜11ビットの部分を使用しなければならない、ということです。つまり、8〜11ビットの部分の4ビットにおいて、少なくとも1つは1が含まれなければならないということです。もしくは、その4ビットにおいて、全てが0になる事は許されない、と言い換える事もできます。
このような、全てが0になる事が禁止されているビットのグループが、この表においてはyで表現されています。xは特に制限のないビットを表します。試しに3バイト文字を見てみると、1バイト目の5〜8ビットと、2バイト目の3ビット目がyになっています。この5つのビットのどれか1つは1にならなければならない、という事です。
サロゲートペア
もう1つルールがあります。UTF-16という2バイト固定長エンコーディングにおいて、U+010000からU+10FFFFのコードポイントを表すために、0xD800から0xDFFFのバイト値を使用します。このバイト値に対応するコードポイントU+D800からU+DFFFは、Unicodeにおいてもサロゲートペア用のコードポイントとして予約されています。そしてUTF-8では、このサロゲートペア用のコードポイントはエンコードしない事になっています。つまり、デコードした結果U+D800からU+DFFFの範囲のコードポイントが解釈されるビットパターンは、UTF-8において不正なバイトシーケンスであると決まっています。
定義表の解読
まずは初期状態のS0を見てみましょう。(紛らわしいのでマクロ部分は消去しました。)
static const signed char trans[][0x100] = {
{ /* S0 0 1 2 3 4 5 6 7 8 9 a b c d e f */
/* 0 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 1 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 2 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 3 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 4 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 5 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 6 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 7 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 8 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 9 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* a */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* b */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* c */ F, F, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* d */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* e */ 2, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 3, 4, 3, 3,
/* f */ 5, 6, 6, 6, 7, F, F, F, F, F, F, F, F, F, F, F
},
まず、領域のちょうど上半分、0x00〜0x7Fが全てAになっている事がわかります。これは1バイト文字のバイトシーケンスだからです。次に、0x80〜0xBFが全てFになっている事がわかります。これは、後続バイトの10xxxxxxのビットパターンだからです。次に、0xC0〜0xDFが、概ね1になっている事がわかります。例外的に0xC0と0xC1だけはFになっています。この領域は2バイト文字の先頭バイトの110yyyyxのビットパターンに対応しています。0xC0と0xC1がFなのは、これらがyのビット全てが0の1100000xのパターンだからです。このように2バイト文字の先頭バイトが0xC2から0xDFになっている事は、先程の表の2段目のバイト列のところにも書かれています。
ここでいったん状態1を見てみましょう。
{ /* S1 0 1 2 3 4 5 6 7 8 9 a b c d e f */
/* 0 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 1 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 2 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 3 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 4 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 5 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 6 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 7 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 8 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* 9 */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* a */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* b */ A, A, A, A, A, A, A, A, A, A, A, A, A, A, A, A,
/* c */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* d */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* e */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* f */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F
},
これはとてもわかりやすいです。0x80から0xBFまでがA、他がFです。これは後続バイトのビットパターン10xxxxxxに対応しています。状態0で2バイト文字の先頭を読んだあとで遷移する状態なので、1文字読んだら受理という事です。
状態0に戻って、0xE0から0xEFの行を見てみましょう。この行は3バイト文字の先頭バイト1110yyyyに対応しています。概ねが3になっていますが、先頭の0xE0だけは2、終盤の0xEDだけは4になっています。先に状態3を確認しましょう。
{ /* S3 0 1 2 3 4 5 6 7 8 9 a b c d e f */
/* 0 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 1 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 2 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 3 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 4 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 5 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 6 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 7 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 8 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* 9 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* a */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* b */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* c */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* d */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* e */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* f */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F
},
これもわかりやすいですね。0x80から0xBFまでが状態1への遷移、他がFです。これは後続バイトのビットパターン10xxxxxxに対応しています。状態0で3バイト文字の先頭を読んだあとで遷移する状態なので、あと2文字読んだら受理できる状態です。そこで、後続バイトを読んだら状態1に遷移するようになっています。状態1というのは、先程確認したとおり、2バイト文字における後続バイトを受理する状態なので、このようにつなげることで3バイト長をチェックできるという事です。
状態0における0xE0は、3バイト文字の先頭バイト1110yyyyのyが全て0になり、11100000になったパターンです。3バイト文字のyビットは2バイト目の3ビット目にも含まれているので、このパターンではそのyビットが1になっています。2バイト目のyビットが1になると、101xxxxxとなるので、表せる範囲が元々の0x80から0xBFから削られ、0xA0から0xBFに半減します。状態2は、これを表現しています。
{ /* S2 0 1 2 3 4 5 6 7 8 9 a b c d e f */
/* 0 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 1 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 2 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 3 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 4 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 5 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 6 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 7 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 8 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 9 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* a */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* b */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* c */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* d */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* e */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* f */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F
},
状態0における0xEDは、サロゲートペアが関係しています。前述のとおり、UTF-8ではサロゲートペアに使われるコードポイントのデコードを禁止しています。サロゲートペアは、U+D800からU+DFFFであり、これをUTF-8のエンコード規則に当てはめると、U+D800は[0xED, 0xA0, 0x80]、U+DFFFは[0xED, 0xBF, 0xBF]となります。よって、先頭バイトが0xEDであった場合は、1つ目の後続バイトは、サロゲートペア範囲として0xA0〜0xBFが禁止され、元々の0x80〜0xBFから0x80〜0x9Fの範囲に制限されるという事です。状態4はそのようになっています。
{ /* S4 0 1 2 3 4 5 6 7 8 9 a b c d e f */
/* 0 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 1 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 2 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 3 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 4 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 5 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 6 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 7 */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* 8 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* 9 */ 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,
/* a */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* b */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* c */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* d */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* e */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F,
/* f */ F, F, F, F, F, F, F, F, F, F, F, F, F, F, F, F
},
状態1の最後の1行、0xF0から0xFFですが、これまでと同様で、0xF0の状態5への遷移は、yビットによる制限のかかった後続バイトです。6への遷移は通常範囲の後続バイトです。0xF4は、最大コードポイントの制限がかかった後続バイトです。UTF-8のエンコード規則では、4バイト文字は21ビットを扱えるので最大でU+1FFFFFが表現できますが、Unicodeにおいてコードポイントは最大でU+10FFFFとなっているので範囲の制限がかかっているのです。
31ビットへの拡張
Onigmoを使っていたところ、\x{7FFFFFFF}という表記を含む正規表現が読み込めないという問題に遭遇しました。ここまで述べたとおり、UnicodeはU+10FFFFまでしか存在しないので、UTF-8としてはエンコードもデコードもできないからです。しかし、その正規表現は既存のリソースに書かれていて、できればそのまま読み込みたいです。実は、UTF-8のエンコード規則は、そのまま拡張することで5バイト文字, 6バイト文字に対応させ、31bitまでのコードポイントを表せるようにできます。先頭バイトは1の連続する数でそのバイト数を示すので、5バイトであれば111110yy、6バイトであれば1111110yのようにビットパターンを定義するのです。ちなみに、Wikipediaによると、UTF-8の規格策定における初期段階ではそのようになっていたそうです。そこで、このような31ビット拡張をこのオートマトンに対して行って、プルリクエストをだしたところ、マージして貰えました。コンパイル時にUSE_UTF8_31BITSフラグを有効にすると、この拡張が有効になります。