dromozoa-utf8

リンク

RFC
- UTF-8, a transformation format of ISO 10646
- UTF-16, an encoding of ISO 10646
Unicode
- Unicode Technical Reports
  - UAX 11 East Asian Width
  - UAX 14 Unicode Line Breaking Algorithm
  - UAX 15 Unicode Normalization Forms
  - UAX 44 Unicode Character Database
- UCD

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バイト列を返すような関数であり、メモリ量を考えなければ単純な表で実装が可能である。

開始符号位置	終了符号位置	長さ	個数	個数（16進数）
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文字列であることを仮定するので、バイト列の先頭からオフセットを探索する場合、先頭バイトだけにアクセスする実装が可能である。バイト列の末尾からオフセットを探索する場合、先頭バイトだけに着目して実装することはできないので、文字数のカウントと同様のテクニックを用いて実装する。