超高速なUTF-8バリデーション、rangeアルゴリズムの紹介

rangeアルゴリズムの紹介

UTF-8を高速にバリデーションするアルゴリズムとして有名なアルゴリズムはLemireさんとKeiserさんの「Validating UTF-8 In Less Than One Instruction Per Byte」が有名だと思いますが、これを凌ぎそうなアルゴリズムを見つけました。

cyb70289(Yibo Cai)さんが発見された、rangeアルゴリズムを見ていこうと思います。（なお、私がみたのはARMのNEONのアルゴリズムです。SSEやAVXなどの実装もありますから、見やすい方を選択していただくとわかりやすいかと思います）

rangeアルゴリズムの概要

基本的なアイデアとなると、以下になります。

• 16バイトSIMDレジスタに読み込む
• SIMDで計算する
• 16バイトのバリデーションを一気に行う

UTF-8のフォーマット

UTF-8のフォーマットを振り返ってみましょう

参考: http://www.unicode.org/versions/Unicode6.0.0/ch03.pdfのp.94 Well-Formed UTF-8 Byte Sequencesより

Rangeアルゴリズムの詳しい説明

rangeテーブルなどのテーブルに関しては、ソースコードを適宜読んでください

1. 上位ニブルの取り出し

ニブル(nibble)とは、バイトの半分を意味しています。「上位ニブル」「下位ニブル」などと呼びます。UTF-8では、1バイト目の上位ニブルから、UTF-8のバイトが何バイトなのかを数える事ができます。

2. 1から、0xC2~0xF4の間を8、それ以外を0とし、rangeテーブルとする

後々に、0xC2から0xF4までの間に処理を挟むため、rangeテーブルには8を登録します。

3. 1番めのバイトを取り出し

例えば、以下のような処理を行います。これによって何バイトのUTF-8シーケンスなのかを判別します。

1. 1で出した上位ニブルからfirst_len_tblテーブルを引き、値をfirst_lenテーブルに格納
2. prev_first_lenを{0, 0, 0, 0, 0, 0, 0, 0}、first_lenは{3, 0, 0, 0, 0, 0, 0, 0}、としよう

4. 2番めのバイトを取り出し

2バイト目のバイトを取り出します。左1バイトをシフトすることで、16バイトごとで処理をしていた部分のうち、途中のUTF-8バイトシーケンスだった場合のケースを拾うことができます。

1. first_lenを左1バイトシフトしrangeテーブルとorする(orをすると、{E0, E0, E0}などで{8, 8, 8}となっていたのが{8, 0A, 0A, 2}などとなって7でエラーになる)
2. {0, 0, 0, 0, 0, 0, 0, 0}, {3, 0, 0, 0, 0, 0, 0, 0} => {0, 0, 0, 0, 0, 0, 3, 0}

5. 3番めのバイトを取り出し

1飽和減算するというところが今までと違うところです。これによって、3は2に、2は1など、バイト数による処理を後々に行うことができます。

1. first_lenを左2バイトシフトする
2. {0, 0, 0, 0, 0, 0, 0, 0}, {3, 0, 0, 0, 0, 0, 0, 0} => {0, 0, 0, 0, 0, 3, 0, 0}
3. 1飽和減算しrangeテーブルとorする(orをすると、{E0, E0, E0}などで{8, 8, 8}となっていたのが{8, 0A, 0A, 2}などとなって7でエラーになる)
1. {0, 0, 0, 0, 0, 2, 3, 0}

6. 4番目のバイトを取り出し

2飽和減算するというところが今までと違うところです。これによって、3は1に、2は0など、バイト数による処理を後々に行うことができます。

1. first_lenを左3バイトシフトする
2. {0, 0, 0, 0, 0, 0, 0, 0}, {3, 0, 0, 0, 0, 0, 0, 0} => {0, 0, 0, 0, 3, 0, 0, 0}
3. 2飽和減算しrangeテーブルとorする(orをすると、{E0, E0, E0}などで{8, 8, 8}となっていたのが{8, 0A, 0A, 2}などとなって7でエラーになる)
1. {0, 0, 0, 0, 1, 2, 3, 0}

7. 0, 1, 2, 3, 8のいずれかならば許容範囲内、それ以外ならエラーになる

先述したとおり、例えば不正なバイト列として{E0, E0, E0}というバイト列が入ってきていた場合、{2, 0A, 0A, 2}などとなっているはずなので、0, 1, 2, 3, 8以外のケースになっていてエラーにすることになります。

8. 8の場合は特殊なケースになる、その対処

例えば、E0の2バイト目はA0から始まるとか、EDの2バイト目は9Fで終わる、F0の2バイト目は90で始まる、F4では2バイト目は8Fで終わるといったエッジケースを処理していきます。

1. まず入力(prev_input, input)を左に1バイトシフトさせる
2. それぞれを0xE0を引き、_range_adjust_tblにマッチさせる
3. _range_adjust_tblの値をrangeに足す(2~4になる)

9. 下限のテーブルを引く

1. 0はASCII、1~3は2,3,4バイトの範囲内、4は2バイト目が0xA0、5は1バイト目がED、6は1バイト目が0xF0、7は1バイト目が0xF4、8は先述のとおり0xC2~0xF4でUTF-8の始まり、それ以外は不正なバイト

10. 上限のテーブルを引く

1. 0はASCII、1~3は2,3,4バイトの範囲内、4は2バイト目が0xA0、5は1バイト目がED、6は1バイト目が0xF0、7は1バイト目が0xF4、8は先述のとおり0xC2~0xF4でUTF-8の始まり、それ以外は不正なバイト

11. 6でいう、{0, 0, 0, 0, 1, 2, 3, 0}の通りになっているかを9で引いた下限テーブルで検証し、エラーが出たら0xFFFF

12. 6でいう、{0, 0, 0, 0, 1, 2, 3, 0}の通りになっているかを10で引いた上限テーブルで検証し、エラーが出たら0xFFFF

13. 11と12をorし、0以外ならばエラー

14. 現在の入力をprev_inputに格納、first_lenテーブルをprev_first_lenに格納

大まかな流れは以上です

これが大まかなrangeアルゴリズムの流れになります。16バイトを下回ると、標準のUTF-8にフォールバックされるというところが抜けていますが、これである程度の長さのUTF-8が高速にバリデーションすることができることがわかっていただけると嬉しいですね。

なお、使用するSIMDによってはrangeアルゴリズムが最速というわけでもなさそうでもありそうです。今回試したのはNEONというARMに搭載されているSIMDなので、rangeアルゴリズムを選択しましたが、x86系統のSSEなどではちょっと様子が違うようです。

学んでみての感想は

そっちょくにいって「すごい」の一言です。SIMDによるUTF-8バリデーションは色々と難しいのですが、それを色々なアイデアを使って乗り越えていくのは純粋にすごいと思いました。これを思いつくのはぼくには難しそうです。勉強になりました。

2023/04/29 1:17