実装メモ
リンク
UTF-8デコード
RFC 3629によって与えられているABNFを下記に示す。
冗長なエンコードと代用符号位置のエンコードが除外されている。
UTF8-octets = *( UTF8-char )
UTF8-char = UTF8-1 / UTF8-2 / UTF8-3 / UTF8-4
UTF8-1 = %x00-7F
UTF8-2 = %xC2-DF UTF8-tail
UTF8-3 = %xE0 %xA0-BF UTF8-tail
/ %xE1-EC 2( UTF8-tail )
/ %xED %x80-9F UTF8-tail
/ %xEE-EF 2( UTF8-tail )
UTF8-4 = %xF0 %x90-BF 2( UTF8-tail )
/ %xF1-F3 3( UTF8-tail )
/ %xF4 %x80-8F 2( UTF8-tail )
UTF8-tail = %x80-BF
展開して正規表現で書きくだす。
UTF8-1 = [\x00-\x7F]
UTF8-2 = [\xC2-\xDF] [\x80-\xBF]
UTF8-3a = [\xE0-\xE0] [\xA0-\xBF] [\x80-\xBF]
UTF8-3b = [\xE1-\xEC] [\x80-\xBF] [\x80-\xBF]
UTF8-3c = [\xED-\xED] [\x80-\x9F] [\x80-\xBF]
UTF8-3d = [\xEE-\xEF] [\x80-\xBF] [\x80-\xBF]
UTF8-4a = [\xF0-\xF0] [\x90-\xBF] [\x80-\xBF] [\x80-\xBF]
UTF8-4b = [\xF1-\xF3] [\x80-\xBF] [\x80-\xBF] [\x80-\xBF]
UTF8-4c = [\xF4-\xF4] [\x80-\x8F] [\x80-\xBF] [\x80-\xBF]
第1バイトだけに着目し、妥当でない領域も考慮すると、
| 第1バイト | 長さ |
|---|
| 00..7F | 1 |
| 80..C1 | |
| C2..DF | 2 |
| E0 | 3 |
| E1..EC | 3 |
| ED | 3 |
| EE..EF | 3 |
| F0 | 4 |
| F1..F3 | 4 |
| F4 | 4 |
| F5..FF | |
第2バイト以降の範囲は6種類である。
演算後の値をテーブルとして保持する場合、第2バイト以降の範囲は7種類に分けられる（次表A,B,B2,B3,C,C2,C3）。
| 第1バイト | 第2バイト | 第3バイト | 第4バイト |
|---|
| 00..7F | | | |
| C2..DF | 80..BF (A) | | |
| E0 | A0..BF (B2) | 80..BF (A) | |
| E1..EC | 80..BF (B) | 80..BF (A) | |
| ED | 80..9F (B3) | 80..BF (A) | |
| EE..EF | 80..BF (B) | 80..BF (A) | |
| F0 | 90..BF (C2) | 80..BF (B) | 80..BF (A) |
| F1..F3 | 80..BF (C) | 80..BF (B) | 80..BF (A) |
| F4 | 80..8F (C3) | 80..BF (B) | 80..BF (A) |
UTF-8エンコード
1112064種類の整数を引数としてUTF-8バイト列を返すような関数であり、メモリ量を考えなければ単純な表で実装が可能である。
| 開始符号位置 | 終了符号位置 | 長さ | 数 |
|---|
| 0000 | 007F | 1 | 128 (0x0080) |
| 0080 | 07FF | 2 | 1920 (0x0780) |
| 0800 | D7FF | 3 | 53248 (0xD000) |
| E000 | FFFF | 3 | 8192 (0x2000) |
| 010000 | 10FFFF | 4 | 1048576 (0x010000) |
実験によれば、U+0001..U+07FFまでの区間を表にすると、消費メモリ量と速度のバランスがよいようだった。
U+0800以降については、上位12bitで表を作ることで消費メモリ量と速度のバランスをとる。
| 長さ | 符号位置 | 6bit分割 | 上位12bit |
|---|
| 2 | 0800 | 00 20 00 | 0020 |
| 2 | D800 | 0D 20 00 | 0360 |
| 2 | DFFF | 0D 3F 3F | 037F |
| 2 | FFFF | 0F 3F 3F | 03FF |
| 3 | 010000 | 00 10 00 00 | 0010 |
| 3 | 10FFFF | 04 0F 3F 3F | 010F |
Luaと演算
- Lua 5.3のビット演算は演算子実装なので関数呼び出しよりも速い。
- LuaJITは最適化を考慮する必要がある。
| バージョン | 実装 |
|---|
| Lua 5.1 | |
| LuaJIT | 関数 (bit) |
| Lua 5.2 | 関数 (bit32) |
| Lua 5.3 | 演算子 |
文字数のカウント
任意のバイトは、UTF-8の有効な第1〜4バイトであるか、不正なバイトである。
状態\(s\)と4バイトを引数として、状態を返すような関数\(f(s,a,b,c,d)\)を考え、有限状態機械で表現する。
有限状態機械は最小化しないほうが高速かもしれない。
オフセット
Lua 5.3のutf8.offsetは、\(n\)文字めの位置をバイト単位で返す関数である。
実装は、全バイトにアクセスして末尾バイト（80..BFでないバイト）かどうかを判定している。
仕様が妥当なUTF-8文字列であることを仮定するので、バイト列の先頭からオフセットを探索する場合、先頭バイトだけにアクセスする実装が可能である。
バイト列の末尾からオフセットを探索する場合、先頭バイトだけに着目して実装することはできないので、文字数のカウントと同様のテクニックを用いて実装する。