文字は何らかの方法でビットにエンコードする必要があります。 Habréに関するこの投稿を含む、インターネット上のほとんどの文字列は、UTF-8でエンコードされています。 UTF-8形式は、1、2、3、または4バイトの「文字」を表します。これは、文字ごとに1バイトのみを使用するASCII標準の一般化です。つまり、ASCII文字列もUTF-8文字列です。
技術的にはUTF-8がコードポイントを記述しているため、実際にはもう少し複雑です。絵文字のような目に見える文字は、複数のコードポイントで構成することができます...しかし、ほとんどのプログラマーは、それらのわかりやすい言葉遣いを必要としません。
他の基準もあります。 C＃やJavaなどの一部の古いプログラミング言語はUTF-16に依存しています。 1文字あたり2バイトまたは4バイトを使用します。当時は良い考えのようでしたが、今ではコンセンサスがいつでもどこでもUTF-8を使用する方向に向かっています。
ほとんどのエンコーディングには強制可能な制限があります。言い換えれば、すべてのランダムビットシーケンスがUTF-8に入ることができるわけではありません。したがって、文字列を検証する必要があります-それが本当にUTF-8であることを確認してください。
何が問題ですか？すごい。たとえば、MicrosoftのWebサーバーにはこの脆弱性があります。有効で安全と思われるURIを受け入れますが、サーバーによって解釈されると、攻撃者はディスクにリモートアクセスできます。セキュリティ上の懸念はさておき、データベースに無効な行を保存したくないことはほぼ間違いありません。
したがって、プログラミング言語、Webサーバー、ブラウザー、およびデータベースエンジンは、常にUTF-8を検証しています。
文字列のほとんどがASCIIである場合、チェックは非常に高速であり、UTF-8チェックは問題ではありません。ほとんどの文字列がASCIIでエンコードされていた時代は終わりました。私たちは絵文字と多くの国のアルファベットの世界に住んでいます。
2018年に、私は自分自身に問いかけました。UTF-8文字列を検証する速度はどれくらいですか？その時、私はシンボルごとにいくつかのCPUサイクルを持つ検証オプションを見つけました。これで落ち着くことができましたが、この答えは私を満足させませんでした。
作業には何年もかかりましたが、今では理想に近いバージョンになっているようです。新しいアルゴリズムは、他のクイック検索オプションよりも1桁高速です。ホワイトペーパー「1バイトあたり1命令未満でのUTF-8検証」（ソフトウェア：実践と経験で公開予定）を作成し、ベンチマークユーティリティも公開しました。
詳細はすべて科学記事で説明されているため、ここでは詳しく説明しませんが、本質について簡単に説明します。 UTF-8検証の大部分は、連続するバイトのペアを探すことによって行われます。すべてのバイトペアをチェックし、この情報から検出できる可能性のある違反を特定した後、やるべきことは比較的ほとんどありません。
すべてのプロセッサには高速SIMD命令があります。ワイドレジスタ（128ビット、256ビットなど）で動作します。ほとんどのセットには、たとえば16バイトの値（0から16の範囲）を取り、16バイトのテーブルでそれらを検索する「ベクトル化されたルックアップ」命令があります。 IntelおよびAMDプロセッサでは、この説明は命令に対応します
pshufb..。 0〜16の値は、ニブルと呼ばれることもあり、4ビットにまたがります。バイトは2つのニブル（低と高）で構成されます。
私たちの検索アルゴリズムでは、ベクトル化された検索命令は3回呼び出されます。1回は低ニブル、1回は高ニブル、もう1回は次のバイトの高ニブルです。対応する16バイトのルックアップテーブルが3つあります。それらを正しく選択すると、3回の検索のビットごとのANDでエラーが検出されます。
詳細については科学記事を参照してください。ただし、最終的にほぼ完全なUTF-8検証は、分岐のない5行の高速C ++コードで実行されます...これらの5行は、一度に最大32バイトのブロックをチェックします...
simd8 classify(simd8 input, simd8 previous_input) {
auto prev1 = input.prev<1>(previous_input);
auto byte_1_high = prev1.shift_right <4>().lookup_16(table1);
auto byte_1_low = (prev1 & 0x0F).lookup_16(table2);
auto byte_2_high = input.shift_right <4>().lookup_16(table3);
return (byte_1_high & byte_1_low & byte_2_high);
}すぐにはわかりませんが、この検証で十分であり、100％安全です。本当にです。残りの安価な追加の技術ステップはほんのわずかです。
その結果、最近のIntel / AMDプロセッサでは、最もジャンクでランダムな入力でさえもチェックするのに、バイトあたり1命令弱しかかかりません。コードは非常に最適化されているため、1サイクルあたり最大3つの命令、さらにはそれ以上の命令を実行できます。つまり、最新のCPUでは、入力バイトごとにサイクルのごく一部（3分の1未満）を使用します。したがって、処理速度は12 GB / s以上で確実に維持されます。
教訓は、通常のルックアップテーブルは便利ですが、ベクトル化されたテーブルは高速アルゴリズムの基本的な構成要素であるということです。
本番環境で高速UTF-8検証機能を使用する必要がある場合は、simdjsonライブラリ（バージョン0.5以降）をお勧めします。十分にテストされており、ランタイムディスパッチなどの便利な組み込み機能があります。ライブラリはJSONを解析するように設計されていますが、JSONがまったくない場合でも、純粋にUTF-8検証に使用できます。 64ビットARMおよびx64プロセッサをサポートし、他のCPUのフォールバック処理も備えています。 1つのソースファイルと一緒に1つのヘッダーファイルにパックしました。したがって、C ++プロジェクトに配置するだけです。
前作..。検索アルゴリズムの鍵となるベクトル化分類法を普及させる主なメリットは、Mulaにあります。私の知る限り、Keizerは私たちのトリプルサーチ戦略を最初に提案しました。最初の実用的なSIMDベースのUTF-8検証アルゴリズムは、K。Willetsによって作成されました。Z.ウェグナーを含む何人かの人々がそれを改善しました。Travis Downsは、従来のアルゴリズムを高速化する方法について賢明なアイデアを思いつきました。
さらに読む。この作業を楽しんでいる場合は、関連トピックに関する他の記事が好きかもしれません：「ほぼコピーインメモリ速度でのBase64エンコーディングとデコーディング」（ソフトウェア：Practice and Experience、50（2）、2020）および「JSONギガバイト/秒の解析」（ VLDB Journal、28（6）、2019）。