Geekly Articles each Day

ビットを読み取るためのさまざまな方法

画像

私のブログの古い伝統を再開して、私は簡単なタスクを取り、その代替ソリューションの過度に長いリストを考慮し、それらのメリットに感謝します。

単純なタスクは次のとおりです。バイトストリームからデータを読み取り、値を可変ビット数でエンコードします。 個々のバイト、マシンワードなどを読み取ります。 ほとんどのプロセッサと多くのプログラミング言語で直接サポートされていますが、可変ビット長で入出力する場合、通常は自分でソリューションを実装する必要があります。

簡単に聞こえますが、ある意味ではそうです。 問題の最初の原因は、この操作がコーデックを積極的に使用することです-はい、メモリとI / Oではなく計算に制限されます。 したがって、単に機能するだけでなく、効果的な実装も必要です。 そしてその過程で、I / Oバッファリング、バッファーエンド処理、C / C ++で定義されたビットシフトのデッドロック、さまざまなプロセッサアーキテクチャ、およびビットシフトの他の機能とのやり取りが発生します。

この投稿では、主にリーダーを実装するさまざまな方法に焦点を当てます。 実際、ここで説明したすべての手法は記録部分にも同様に適用できますが、アルゴリズムのバリエーションの数を2倍にしたくはありません。 それらは十分にあります。

自由度


「可変ビット数の読み取り」は、タスクの説明が不十分です。 ビットをバイトにパックする多くの受け入れ可能な方法があり、それらのすべてに独自の長所と短所があります。これについては後で説明します。 それまでの間、それらの違いだけを見てみましょう。

まず最初に重要な選択を行う必要があります-フィールドは「先着MSB」または「先着LSB」の形式でパックされます（「最上位ビット」-最上位ビットおよび「最下位ビット」-最下位ビット）。 つまり、実装されたgetbits関数を呼び出して次のコードを実行すると

 a = getbits(4); b = getbits(3);

新しく開かれたビットストリームの場合、同じバイトから両方の値が受信されると予想されますが、このバイトでどのように順序付けられますか？ MSBファーストの形式でパックされている場合、「a」はMSBで始まる4ビットを占有し、「b」は「a」よりも低いため、次のスキームにつながります。


このようにビットに番号を付けます。LSBは0で、MSBに近づくと、値が増加します。 多くのコンテキストでは、この順序が標準です。 LSB-firstは反対の状況です。最初のフィールドはビット0を取り、次のフィールドには増加するビット番号が含まれます。


両方の形式は、一般的なファイル形式で使用されます。 たとえば、JPEGはビットストリームでMSBファースト形式のビットパッキングを使用し、DEFLATE（zip）はLSBファーストを使用します。

解決する必要がある次の質問は、値が数バイトに拡張されたときに何が起こるかです。 5ビットでエンコードする別のc値があるとします。 結果として何が得られますか？ バイトではなく32ビットまたは64ビットのワードで値をパックすることを宣言することにより、問題の解決をわずかに遅らせることができますが、最終的には何かを選択する必要があります。 そして、ここで私たちは突然多くの異なる選択肢に直面しているので、私は主要な申請者のみを検討します。

MSBファーストビットパッキングは、MSBからLSBへの「c」ビットフィールドの反復として認識され、一度に1ビットずつ挿入されます。 1バイトを入力したら、次のバイトに進みます。 ビットフィールドcについてこれらの規則に従うと、ストリームの結果として、ビットは次のスキームになります。


これらのルールに従うと、MSBビットを大きな整数にパックしてビッグエンディアンの順序で保存することで得られるのと同じ2バイトになることに注意してください。 代わりにLSBが最初のバイトにあり、4つの上位ビットが2番目のバイトになるように「c」を分割することにした場合、これは機能しません。 このような一貫したビットパッキングルールを「自然な」ルールと呼びます。

もちろん、LSBファーストビットパッキングには独自の自然な規則があります。 これは、LSBから開始して、ビットごとに新しい値を挿入することで構成され、これを行うと、結果として次のビットストリームが取得されます。


LSBファーストの自然パッキングは、LSBファーストの大きな整数へのパッキングと同じバイトを提供し、リトルエンディアンのバイト順を維持します。 さらに、写真には明らかな不器用さがあります。数バイトの「c」フィールドの論理的に共役したパッキングは、この写真では不連続に見えますが、MSBファーストのパッキング画像は予想どおりです。 しかし、そこには問題があります。MSBファーストの画像では、ビットを右から左に増加する順序（標準）で番号付けし、バイトを左から右に増加する順序で番号付けします（これも標準です）。

左側の各バイトにビット0（LSB）を描画し、右側のビット7（MSB）を描画すると、LSBファーストビットマップで何が起こるかを示します。


このように描画すると、回路は予想どおりになります。 バイトを数値と考えると、右側のMSBの位置は奇妙に見えますが、8ビットの配列と考えると、それほど奇妙ではないことがわかります（実際には、ビット単位のI / Oを行うときにそれを処理します）。

偶然にも、一部のビッグエンディアンアーキテクチャ（IBM POWERなど）では、ビットに次のように番号が付けられています-ビット0はMSB、ビット31（または63）はLSBです。 このようなマシンでビット0 = MSBのMSBファーストビットパッキングスキームを作成し、ビット0がMSBに対応するように独自のビットフィールドに番号を付けると、まったく同じスキームが得られます（ただし、これは少し異なることを意味します） ） この標準は、ビットとバイトの順序を一貫性のあるものにします（これは良いことですが）が、ビットkを 2 kの値に一致させるという便利な標準を壊します（完全に良いとは限りません）。

また、ビット0がMSBになるようにビットの番号を付け直すという考えが脳を爆発させる場合は、ビットの番号付けを変更せずに、反抗者になり、左側に増加するバイトアドレスを描画できます。 または、アドレスを右に増やしますが、わずかに異なる反逆者になり、逆の順序でバイトストリームを記録します。 これらのオプションのいずれかを選択すると、次のスキームが得られます。


これはすでに混乱し始めていることを理解しており、ここで停止しますが、ここで何か重要なことを言わなければなりません：バイトを受信する方法に過度に執着しないでください。 単に見た目が良いからといって、あるオプションが他のオプションよりも優れていると思われるのは簡単ですが、バイトを左から右に、その中のビットを右から左に取得する基準は完全に任意です。変だ。

MSBファーストとLSBファーストの各パッケージング標準にはそれぞれ長所と短所があり、一方を「正しい」、もう一方を「間違った」と指定するよりも、アプリケーションの分野が異なるツールと考える方がはるかに便利です。 バイトオーダーと、値をバイト、ワード、またはより大きなものにパックする必要性については、ビットパッキング標準に最も自然な順序を使用することを強くお勧めします。MSB-firstは当然、ビッグエンディアンのバイト順に対応し、LSB -firstは、リトルエンディアンのバイト順と自然に一致します。 逆の順序でバイトストリームを記述しない限り（信じられないかもしれませんが、そうする論理的な理由があります）。 この場合、リトルエンディアンに対応する逆順でMSBファーストを取得し、ビッグエンディアンに対応する逆順でLSBファーストを取得します。

「自然な」順序を選択する理由は、それらが異なる実装でより大きな自由を与えるためです。 自然な順序のストリームでは、多くの異なるデコーダー（およびエンコーダー）を使用できますが、それぞれに独自のトレードオフ（およびさまざまなケースでの利点）があります。 「不自然な」注文は通常、1つの特定の実装で適用され、他の方法でデコードされると非常に不便です。

最初のgetbits （ビット抽出）


問題を十分な量で説明したので、ソリューションを実装できます。 ビットストリーム全体が連続して（バイトの配列のように）メモリ内にあると仮定すると、特に単純なバージョンが可能になり、現在のところ、配列の最後に到達するなどの不快な問題を完全に無視します。 無限のふりをしましょう！ （どちらも十分に大きいか、エッジの周りにゼロパディングがあります。）

この場合、純粋に機能的な「ビット抽出」関数に基づいて実装を行うことができます。この関数では、発生する問題とあらゆる種類のビット読み取り関数を説明します。 LSBファーストビットをパックすることから始めましょう。

 //  buf[]    integer little-endian,  "width" // ,     "pos" (LSB= 0). uint64_t bit_extract_lsb(const uint8_t *buf, size_t pos, int width) { assert(width >= 0 && width <= 64 - 7); //  64-  little-endian,   , //    "pos" ( "buf"). uint64_t bits = read64LE(&buf[pos / 8]); //     ,  //   . //   LSB     LSB . bits >>= pos % 8; //   "width" ,      . return bits & ((1ull << width) - 1); } //  ,    //  - . const uint8_t *bitstream; //    size_t bit_pos; //      . uint64_t getbits_extract_lsb(int width) { //   uint64_t result = bit_extract_lsb(bitstream, bit_pos, width); //   bit_pos += width; return result; }

LSBファーストビットストリームは、リトルエンディアンの数が多いという事実を利用しました。 最初に、関心のあるビットのいずれかを含む最初のバイトから始まる64の隣接ビットをバイト単位で配置し、必要な最初のビットの下にある残りの余分な0-7ビットを取り除くために右にシフトし、マスクされた結果を返します希望の幅。

posの値に応じて、この右へのシフトにはさらに7ビットかかる可能性があります。 したがって、64ビット全体を読み取りますが、このコードで一度に読み取ることができる最大量は64-7 = 57ビットです。

bitextract 、 bitextractを簡単に実装getbitsます。 ビットストリームの現在の位置（ビット単位）を追跡し、読み取り後にインクリメントを実行します。

MSBファーストの対応するオプションは、コードのデモンストレーション後に説明する1つの厄介な問題を除いて、かなり似た方法で取得されます。

 //  buf[]    integer big-endian,  "width" // ,     "pos" (MSB= 0). uint64_t bit_extract_msb(const uint8_t *buf, size_t pos, int width) { assert(width >= 1 && width <= 64 - 7); //  64-  big-endian,   , //    "pos" ( "buf"). uint64_t bits = read64BE(&buf[pos / 8]); //     ,    . //   MSB      MSB . bits <<= pos % 8; //   "width" . return bits >> (64 - width); } uint64_t getbits_extract_msb(int width) { //   uint64_t result = bit_extract_msb(bitstream, bit_pos, width); //   bit_pos += width; return result; }

このコードは前のコードと同様に機能します：バイトで配列された64の連続ビット（今回はビッグエンディアン）を読み取り、必要なビットフィールドの上部をMSB bitsに揃えるために左シフトを実行しbits （調整するために右シフトを行う前に） LSB bits ）を使用してビットフィールドの下部getbits(3)をgetbits(3)から、右にシフトして下の上位ビットを配置してそれらを返します。これは、 getbits(3)を呼び出すときに通常0から7の値が表示されることを期待しているためです

境界シフトの場合


それで問題は何ですか？ このバージョンのコードでは、 widthゼロにwidthことはできません。 問題は、 width == 0を許可すると、最終シフトが64ビット値を64ビット右にシフトしようとすることであり、C / C ++ではこれは未定義の動作です！ この場合、0〜63バイトのシフトを実行できます。

場合によっては、C / C ++では、マシンとの下位互換性のために詳細が未定義のままになるため、現時点では誰も心配していません。 よく知られた例：符号付き数値の表現に追加のコードを使用するという要件がない。 アーキテクチャは追加のコードなしで存在しますが、今日ではすべてが博物館にのみ保存されています。

残念ながら、これらのケースはありません。 シフト量が範囲外の場合、広く使用されているさまざまなCPUアーキテクチャで何が起こるかを次に示します。


さらに混乱させるために、これらの命令セットのほとんどにはSIMD拡張機能があり、整数SIMD命令には非SIMD命令以外の異なるオフシフト動作があります。 要するに、これは一般的なプラットフォーム間でアーキテクチャの違いがある場合の1つです。 ほとんどの人にとって、POWERとRISC-Vは少し時代遅れに見えるかもしれませんが、たとえば32ビットと64ビットのARMは現在、何億ものデバイスにインストールされています。

したがって、コンパイラがこの右へのシフトで行うことすべてが-ターゲットアーキテクチャに対応する右へのシフト命令を与えたとしても（そして通常は発生します）、アーキテクチャごとに異なる動作が見られます。 ARM A64およびx86-64では、64へのシフトの結果は基本的に何も実行されないため、 getbits(0)は（通常）ゼロ以外の値を返しますが、ゼロが返されることが予想されます。

なぜこれがそんなに重要なのですか？ もちろん、 getbits(0)コードは興味深い使用例ではありません。 ただし、変数xに対してgetbits(x)を実行する必要がある場合があります。xは場合によってはゼロになることがあります。 この場合、コードが正常に機能し、特別なケースのチェックを必要としないのであれば素晴らしいことです。

このケースを機能させたい場合、1つのオプションは明示的にwidth == 0をチェックし、これを特別な方法で処理することです。 別のオプションは、幅がゼロで動作する分岐なしの式を使用することです。たとえば、 Jenne Colletの FSEが使用する次のコードです。

  //   "width" ,     width==0. return (bits >> 1) >> (63 - width);

この特定のケースは、LSBファーストビットストリームの方が扱いやすいです。 そして、それらについて言及したので、マスクを使用する操作について話しましょう。マスクを使用して、 widthビットを分離しました。

  //   "width" ,      . return bits & ((1ull << width) - 1);

同様の形式があります。これは、3オペランドおよび補数（AND-NOT）命令を使用したアーキテクチャでわずかに安価です。 これらには、多くのRISC CPUとBMI1を備えたx86が含まれます。 つまり、すべてのビット単位のマスクを取得し、左シフトを実行して下部widthゼロのwidthを追加してから、すべてを追加できます。

  return bits & ~(~0ull << width);

x86にBMI1だけでなくBMI2のサポートもある場合、コンパイラーにそれを提供する（またはアセンブラーを使用する）方法をBZHIできれば、この場合のために特別に作成されたBZHI命令も使用できます。 場合によっては望ましいもう1つのオプションは、コードを単純化する小さなビットマップルックアップテーブルを単純に準備することです。

  return bits & width_to_mask_table[width];

2つの整数演算の結果を格納するルックアップテーブルを準備するのは、とんでもないアクションのように見えます。特に、ロードするテーブル要素のアドレスの計算には通常、シフトと加算の両方が含まれます。テーブル！ -しかし、この狂気には独自の方法があります：必要なアドレスの計算は、たとえばx86およびARMマシン上の1つのブート命令でメモリアクセスの一部として実行できるため、 このシフトと追加はアドレス生成ユニット（AGU）で計算されますCPUへのロードパイプラインの一部として。整数演算およびシフト命令ではありません。 つまり、2つの整数ALU命令を1つの整数ロード命令に置き換えるという直感に反した決定は、異なるオペレーティングユニット間で負荷のバランスを改善するため、アクティブビットI / Oを使用したコードの大幅な高速化につながります。

もう1つの興味深い特性は、マスクルックアップテーブルを使用するLSBファーストバージョンが、変数によって1つのシフトを実行することです（既に読み取られたビットをシフトするため）。 多くの（多くの場合、些細な！）理由で、多くのマイクロアーキテクチャでは、変数による整数のシフトはコンパイル時間の定数値によるシフトよりも高価であるため、これは重要です。 たとえば、Cell PPU / Xbox 360 Xenonは、12サイクルという非常に長い時間プロセッサコアの速度を低下させる可変距離シフトで悪名が高く、定期的なシフトがパイプラインに組み込まれ、2サイクルで実行されました。 多くのIntel x86マイクロアーキテクチャでは、「従来の」x86変数シフト（ SHR reg, clなど）は、コンパイル時定数によるシフトよりも3倍高価です。

これは、MSBファーストバリアントを拒否するもう1つの理由のようです。上記のオプションは、ビット抽出操作に対して2つまたは3つのシフトを実行します。 しかし、1つのシフト、つまり通常のシフトの代わりに循環シフトを使用して操作に戻ることができるトリックのおかげがあります。

 //  buf[]    integer big-endian,  "width" // ,     "pos" (MSB= 0). uint64_t bit_extract_rot(const uint8_t *buf, size_t pos, int width) { assert(width >= 0 && width <= 64 - 7); //  64-  big-endian,   , //    "pos" ( "buf"). uint64_t bits = read64BE(&buf[pos >> 3]); //   ,        LSB. bits = rotate_left64(bits, (pos & 7) + width); //   "width" . // (   ,       //      - LSB-first.) return bits & width_to_mask_table[width]; }

ここで、左ローテーション（Cコンパイラでの最適な使用方法を理解する必要があります）は、最初に元の左シフトの作業を行い、次に余分な「幅」ビットを回転して、ビットフィールドを値の最上位ビットから最下位ビットに反転させます, , LSB-first.

ああ、はい、私は8で除算を右に3シフト、無符号位置のmod-8をバイナリAND 7で書き始めました。これらは同等の置換であり、このような形式を実際のコードで見ることができるので、ここに追加することにしました。

この回転マスク操作を使用して、RAD Game ToolsでCell PPUとXbox 360のビットを読み取りました。これは、このコアで可変距離シフトがひどいためでした。このバージョンにも問題がないことに注意してくださいwidth == 0。唯一の問題は、ほとんどのアーキテクチャに存在する（そして迅速に実行される）ローテーション命令への依存性ですが、通常、Cコードからそれらにアクセスするのは不便です。

ビットシフトとマスキングを実行するさまざまな方法については既に説明しましたが、将来はそれらを参照します。しかし、ビットI / Oの実用的なロジックはまだ示していません：ビットを抽出する形式は、状態を考えずに概念を説明するのに便利な良い出発点ですが、実際のコードでは、特にそれを使用しないでしょうビットストリーム全体がメモリ内にあり、通常の実行プロセスでバッファの最後まで簡単に読み取れることを前提としています！

そこで、私たちは主なタスクを決定し、マスクのシフトと使用を実行するさまざまな方法を検討し、マスクの固有の問題を明らかにしました。私が選択した「ビット抽出」形式は、状態のないプリミティブに基づいています。これは、ループ不変式を使用しなかったため、最初から便利でした。

次に、遭遇するほとんどのビットリーダーで使用される状態のスタイルに進みます（最も安価であることが判明したため）。また、モノリシックな機能getbitsから、より多くの部分に分割された機能に移行します。しかし、最初から始めましょう。

オプション1：入力を1バイトずつ読み込む


「エクストラクター」リーダーは、ビットストリーム全体が事前にメモリ内にあることを前提としています。これは常に可能または望ましいとは限りません。もう1つの極端なケース、つまりビットリーダーを調べて、必要なときにだけ追加のビットを1つずつ要求します。

一般に、ステートフルオプションは一度に数バイトの入力を受け取り、部分的に処理されたいくつかのバイトを持ちます。このデータを変数に保存する必要があり、これを「ビットバッファー」と呼びます。

 //        //  ,    . uint64_t bitbuf = 0; //     int bitcount = 0; //

入力処理中、このバッファが終了すると常に新しいビットをこのバッファに書き込むか、可能であればこのバッファからビットを読み取ります。

苦労せずgetbitsに、一度に1バイトずつ読み取る最初の実装を作成しましょう。今回はMSBファーストから始めます。

 // :  "bitbuf"  "bitcount" ,   // MSB  ;    "bitbuf" -  0. uint64_t getbits1_msb(int count) { assert(count >= 1 && count <= 57); //    ,       // Big endian;      , //    . while (bitcount < count) { bitbuf |= (uint64_t)getbyte() << (56 - bitcount); bitcount += 8; } //      ;   // "count"   "bitbuf"   . uint64_t result = bitbuf >> (64 - count); //       bitbuf <<= count; bitcount -= count; return result; }

前と同様に、count前の部分で説明したように、結果のビットを取得する方法を変更することにより、≥1 の要件を取り除くことができます。最後にこれについて言及します。アルゴリズムのバージョンを表示するたびに、以前のバリエーションが自動的に適用されることに注意してください。

ここでのアイデアは非常に単純です。まず、要求をすぐに満たすのに十分なビットがバッファにあるかどうかを確認します。そうでない場合は、十分な量になるまで、余分なバイトを1つずつ書き込みます。これはgetbyte()、理想的には、ある種のバッファリングされたI / Oメカニズムを使用することを意味します。これは、クリティカルパス上のポインターの逆参照とインクリメントに単純になります。それを避けることができるならば、それはありません関数呼び出しまたは高価なものである必要があります。一度に8ビットを挿入するため、1回の呼び出しで最大57ビットをカウントできます。これは、何も失う危険を冒さずにバッファを補充できる最大ビット数です。

その後count、バッファから上位ビットを取得し、それらをシフトします。ここに保存される不変式は、カウントされていない最初のビットがMSBバッファーに保存されることです。

また、このプロセスが3つの小さな操作に便利に分割されていることにも注意してください。これらの操作を「補充」、「ピーク」、および「消費」と呼びます。 「補充」フェーズでは、バッファーに最小数のビットが存在することが保証されます。 「スキャン」は、バッファ内の次の数ビットを破棄せずに返し、「消費」はそれらを見ずにビットを削除します。それらはすべて個別に役立ちます。これがすべてどのように構成されているかを示すために、LSBファーストアルゴリズムに相当するものをより小さな部分に分けて示します。

 // :  "bitbuf"  "bitcount" ,   // LSB   ;    "bitbuf" -  0. void refill1_lsb(int count) { assert(count >= 0 && count <= 57); //      . while (bitcount < count) { bitbuf |= (uint64_t)getbyte() << bitcount; bitcount += 8; } } uint64_t peekbits1_lsb(int count) { assert(bit_count >= count); return bitbuf & ((1ull << count) - 1); } void consume1_lsb(int count) { assert(bit_count >= count); bitbuf >>= count; bitcount -= count; } uint64_t getbits1_lsb(int count) { refill1_lsb(count); uint64_t result = peekbits1_lsb(count); consume1_lsb(count); return result; }

getbitsこれら3つの小さなプリミティブを組み合わせて記録することは、常に最適とは限りません。たとえば、MSBファーストビットバッファに回転方法を使用する場合、回転をフェーズpeekbitsとに分割する必要がありconsumeます; 最適な実装では、作業がこれら2つのフェーズに分割されます。ただし、これらの3つのフェーズすべてを個別のステップとしてマスターすると、それらをさまざまな方法で一緒に使用できるため、コードをこれらの個別のステップに分割することは依然として有用です。

楽しみにして


このような最も重要な変換は、いくつかのデコード操作の補充償却です。簡単なおもちゃの例から始めましょう。以前に取得した3ビットのフィールドをカウントしたいとします。

  a = getbits(4); b = getbits(3); c = getbits(5);

場合getbits、上記のように実装され、このコードは3回（補充プロセスをおそらく彼自身）まで完了したことを確認します。しかし、これは愚かです。一度に4 + 3 + 5 = 12ビットを読み取ることが事前にわかっているため、すべて同時に取得できます。

  refill(4+3+5); a = getbits_no_refill(4); b = getbits_no_refill(3); c = getbits_no_refill(5);

ここで、getbits_no_refill-別のオプションgetbits、行うpeekbitsとconsume名前を補充することなく、意味するように、しかし。そして、別々の呼び出し間のリチャージサイクルを取り除くと、getbitsコンパイラーによって最適化された単純な整数コードしかありませんでした。言い換えれば、固定長のケースは低コストです。たとえば、次のように、実際に消費するビット数がわからない場合はさらに興味深いものになります。

  temp = getbits(5); if (temp < 28) result = temp; else result = 28 + (temp - 28)*16 + getbits(4);

これは、0〜27の値が5ビットで送信され、28〜91の値が9ビットで送信される単純な可変長コードです。ポイントは、この場合、将来消費するビット数が事前にわからないことです。ただし、9ビット以上あることがわかっているため、補充が1回だけ発生することを確認できます。

  refill(9); temp = getbits_no_refill(5); if (temp < 28) result = temp; else result = 28 + (temp - 28)*16 + getbits_no_refill(4);

実際、必要に応じて、すべての実行パスでさらに操作を中断して、両方の実行パスが一度だけ（consume）ビットを消費するようにすることができます。たとえば、MSBファーストビットバッファを使用する場合、この小さなデコーダを次のように記述できます。

  refill(9); temp = peekbits(5); if (temp < 28) { result = temp; consume(5); } else { // ""  ""     , //      ! ! result = getbits_no_refill(9) - 28*16 + 28; }

このようなマイクロチューニングは、非常にビジーなサイクルの境界を超えて強く推奨されることはありませんが、前述したように、これらのデコーダサイクルの一部は非常に負荷が高く、この場合、いくつかの命令を異なる場所に保存すると深刻な利得が得られます。可変長コード（たとえば、ハフマンコード）をデコードするための特に重要な手法は、特定のビット数を先読みし、その結果に基づいてテーブルを検索することです。テーブル要素は、デコードされた文字が何であるか、消費する必要のある文字数（つまり、文字に実際に属するスキャンされたビット数）を示します。それがずっとありますハフマンツリーの各ステップをチェックして、一度に1つまたは2ビットのコードを読み取るよりも高速です（残念ながら、この方法は多くの教科書やその他の入門テキストで提供されています）。

しかし、問題があります。先読みして消費するビット数を決定する技術は十分強力ですが、ルールを変更したgetbitsだけです。上記の実装は、絶対に必要な場合にのみ余分なバイトを読み取ろうとします。ただし、可変長のコードリーダーの変更例は常に補充されるため、最終的に5ビットしか消費しない場合でも、バッファーには少なくとも9ビットが含まれます。補充が行われる場所によっては、データストリーム自体の終了後に読み取りが行われる場合もあります。先読みの

方法に慣れました。変更されたコードリーダーは、その必要性が確認される前であっても、追加の入力を受け取り始めます。このアプローチには多くの利点がありますが、トレードオフは、ビットストリームの論理的な終わりの外側を強制的に読み込めることです。これは、このような場合の正しい処理を確実に行う必要があることを意味します。はい、クラッシュの原因になったり、ストリームの外部で読み取ったりすることはありません。しかし、これに加えて、入力バッファリングまたはクロッピングレイヤーの動作原理を意味します。

先読みしたい場合、これを処理する方法が必要です。主なオプションは次のとおりです。


私はあなたを慰めません-これらのオプションはすべて実装が難しく、一部は他のオプションよりも困難です。最後に何かを挿入して問題を取り除くのが最も簡単な方法です。外部フレーミングレイヤーの状況を処理することも良い解決策であり、I / Oバッファリングコントロール全体を作り直して数バイトの読み取りをキャンセルするのは本当にひどいです。しかし、トリミングを制御できない場合、単に良い解決策はありません。過去に、私はこの文脈で役立つ便利なテクニックに関する投稿を書きました。実装によっては、たとえば次のように設定することで問題を回避できます。bitcount子孫から最後のバイトを挿入した直後の巨大な値。しかし、一般的なケースでは、先読みを実装する場合は、ある程度の労力を費やす必要があります。しかし、通常、勝つことはそれだけの価値があるので、これはルーレットゲームではありません。

オプション2：私たちは本当に一度に64ビットをカウントする必要があります


前に説明したすべてのメソッドは、バイト単位での作業を避けるためにさまざまなトリックを使用します。抽出ビットリーダーは、完全な64ビットを読み取ることから始まりますが、現在のバイトのすでに消費された部分を破棄するために7ポジションシフトする必要があります。上記の例getbits1では、ビットバッファーに一度に1バイトを挿入します。バッファにすでに57ビットがあるが、新しいバイト用のスペースがない場合（結果はバッファの幅よりも大きい65ビットであるため）、これはメソッドでサポートされる最大幅getbits1です。 57ビットはかなり有用な量ですが、32ビットプラットフォームで作業する場合、同様のマジックナンバーは25ビット（32-7）になり、これはかなり少ない量であり、多くの場合十分ではありません。

幸いなことに、全幅が必要な場合は、それを実装する方法があります（MSBファーストの回転およびビットバッファーマスクを使用する手法と同様に、RADでこれを学びました）。この段階で、MSBファーストとLSBファーストのメソッドの関係はすでに理解していると思うので、1つのオプションのソリューションのみを示します。 LSBファーストを選択しましょう：

 // : "bitbuf"  "bitcount" ,   // LSB  ; 1 <= bitcount <= 64 uint64_t bitbuf = 0; //     int bitcount = 0; //     uint64_t lookahead = 0; //  64  bool have_lookahead = false; //   ,   ! void initialize() { bitbuf = get_uint64LE(); bitcount = 64; have_lookahead = false; } void ensure_lookahead() { //   lookahead,  //     . if (!have_lookahead) { lookahead = get_uint64LE(); have_lookahead = true; } } uint64_t peekbits2_lsb(int count) { assert(bitcount >= 1); assert(count >= 0 && count <= 64); if (count <= bitcount) { //    buf return bitbuf & width_to_mask_table[count]; } else { ensure_lookahead(); //   bitbuf  lookahead // ( lookahead      buf) uint64_t next_bits = bitbuf; next_bits |= lookahead << bitcount; return next_bits & width_to_mask_table[count]; } } void consume2_lsb(int count) { assert(bitcount >= 1); assert(count >= 0 && count <= 64); if (count < bitcount) { // -   buf //    bitbuf >>= count; bitcount -= count; } else { //    buf  ensure_lookahead(); //      lookahead int lookahead_consumed = count - bitcount; bitbuf = lookahead >> lookahead_consumed; bitcount = 64 - lookahead_consumed; have_lookahead = false; } assert(bitcount >= 1); } uint64_t getbits2_lsb(int count) { uint64_t result = peekbits2_lsb(count); consume2_lsb(count); return result; }

このようなアプローチは、上記で検討したアプローチよりも少し複雑であり、不変式が正しく機能するために明示的な初期化ステップが必要です。また、以前のバージョンとは異なり、いくつかの追加ブランチを使用するため、PCなどの明確なパイプラインを持つマシンにはあまり適していません。さらに、私はそれを再び使用していることに注意してくださいwidth_to_mask_table、これはデモンストレーションのためだけではありません：与えられた幅のマスクを計算するために前回使用した算術式はwidth、一般的な64ビットアーキテクチャで有効な全間隔0-64で機能しませんIBM POWERそして、それはもちろん、許可されない不明確な振る舞いの挑戦を無視する場合にのみ機能します。

基本的な考え方は非常に単純です。1つのバッファーだけではなく、2つの値を追跡します。最後に読み取られた64ビット値から残りのビット数がわかっているためpeekbits、それらが十分でない場合、入力ストリームから次の64ビット値を取得し（外部実装を使用get_uint64LE()）、欠落しているビットを取得します。同様に、ビットconsumeを消費した後、現在の入力バッファにビットが残っているかどうかを確認しwidthます。そうでない場合は、先読み値からビットに切り替えて（消費された値にシフトする）、フラグhave_lookaheadをクリアして、前の先読み値が単にビットバッファの内容になったことを示します。

有効な範囲外のオフセットがないことを保証するために、このコードにはブランチが存在します（未定義の動作を引き起こします）。たとえば、バッファにビットがあるかどうpeekbitsかcount <= bitcountを認識するためにどのようにチェックするかを調べますが、をconsume使用しcount < bitcountます。これは偶然ではありません：の計算next_bitsにpeekbitsはによる右シフトが含まれbitcountます。これはbitcount< count≤64 のパスでのみ発生するため、bitcount < 64安全であることを意味します。consume状況が逆転している：私たちはシフトを行いますlookahead_consumed = count - bitcount。ブロックを囲む条件は、lookahead_consumed≥0を保証します。逆方向では、count64 bitcount以下、1 以上なので、lookahead_consumed≤64-1 =63。つまり、Knuthの言葉を言い換えると、「上記のコードのバグに注意してください。私はそれを正しく証明したが、テストしなかった。」

ビットフィールドの幅が広いことに加えて、この手法にはもう1つの利点があります。常に一度に完全な64ビットuintを読み取ることに注意してください。上記のオプション1は一度にバイトを読み取りますが、再充電サイクルが必要です。以下で説明するさまざまな非分岐オプションは、高速の非整列読み取りをサポートするためにターゲットプロセッサに暗黙的に依存します。これは、1つのサイズと一定のアライメントを読み取ることで際立っている唯一のバージョンです。このため、たとえば多くの古いRISCプロセッサなど、高速の非アライメント読み取りをサポートしないターゲットシステムにとってより魅力的です。

いつものように、私が見せない他のバリエーションがたくさんあります。たとえば、メモリに完全にデコードするデータがある場合、ブールフラグを台無しにする理由はありませんhave_lookahead。現在の先読み語へのポインタを保存し、現在の先読み語が消費されるとそのポインタをインクリメントできます。

オプション3：ビット抽出に戻る


前の部分から抽出した元のビットリーダーは非常に高価でした。ただし、入力ストリーム全体が同時にメモリ内にあるという要件に満足している場合は、それをrefill / peek / consumerパターンでラップして有用なものを取得できます。まだ先読みのある（したがって、対応する困難が生じる）少しの読者がいますが、これは人生です。ここでは、たとえばMSBを再び使用します。

 const uint8_t *bitptr; //     uint64_t bitbuf = 0; //    64  int bitpos = 0; //       void refill3_msb() { assert(bitpos <= 64); //        bitptr += bitpos >> 3; //  (Refill) bitbuf = read64BE(bitptr); //     ,     // (     ;   , //     .) bitpos &= 7; } uint64_t peekbits3_msb(int count) { assert(bitpos + count <= 64); assert(count >= 1 && count <= 64 - 7); //       uint64_t remaining = bitbuf << bitpos; //   "count"  return remaining >> (64 - count); } void consume3_msb(int count) { bitpos += count; }

今回getbitsは、リフィル/ピーク/消費の呼び出しから構築されたものも削除しました。これは、もう1つの理解すべきパターンであるためです。

これは非常に良いオプションです。「リフィル」と「ピーク」/「消費」の別々の部分にビットを抽出するロジックを破ると、これらの個々のピースがどれほど小さく理解しやすいかが明らかになりました。さらに、分岐は完全にありません！このメソッドは、非整列64ビットビッグエンディアン読み取り値が存在し、非常に安価であることを期待しています（これは、一般的なx86およびARMアーキテクチャの問題ではありません）。さらに、現実的な実装のためには、バッファのエンドケース処理を追加する必要があります。「先読み」に関するセクションの説明を参照してください。

オプション4：別の先読みタイプ


次に、分岐せずに別の先読みオプションを実装しましょう。私の知る限り、このオプションはクラーケンで作業中に同僚のチャールズ・ブルームと私がRADの助けを借りて発見しました（更新：ヤンがコメントで指摘したように、主なアイデアはクラーケンのリリースのかなり前にXpackのエリック・ビガーズによって使用されました。私は知りませんでした私も、チャールズと思いますが、それは、このアイデアは確かに頭の中で私たちに来て初めてではない、しかし、私たちのバージョンは興味深い機能を持っていることを意味しています- 。で詳細を参照してください。私の応答）すべてのビットリーダーには分岐がありませんが（リフィルなどでバッファの終わりのチェックを無視すると分岐しません）、このオプションにはいくつかの興味深いプロパティがあります（必要な知識がないため、それらのいくつかについては後で説明します）。この組み合わせでは、私は他のどこにも会ったことがありません。他の誰かが私たちの前にいるなら、コメントで私に知らせてください、そして私は間違いなく著者に言及します！したがって、ここではLSBファーストに戻ります。これは、すべてのホリバーに関係なく、LSBファースト/ MSBファーストがこのレベルで交換可能であることを示すためです。

 const uint8_t *bitptr; //        buf uint64_t bitbuf = 0; //     int bitcount = 0; //     void refill4_lsb() { //          //   . bitbuf |= read64LE(bitptr) << bitcount; //       bitptr += (63 - bitcount) >> 3; //     bitcount |= 56; // now bitcount is in [56,63] } uint64_t peekbits4_lsb(int count) { assert(count >= 0 && count <= 56); assert(count <= bitcount); return bitbuf & ((1ull << count) - 1); } void consume4_lsb(int count) { assert(count <= bitcount); bitbuf >>= count; bitcount -= count; }

ピークとコンシュームの段階はすでに見てきましたが、今回は何らかの理由で最大許容ビット幅が1つ減少し、56ビットになりました。

理由は補充段階であり、その動作は以前に見たものとわずかに異なります。 64ビットのリトルエンディアンを読み取り、それらを現在のビットバッファーの最上部に一致するようにシフトすることは明らかです。ただし、bitptr/を使用した操作にbitcountは説明が必要です。

から始める方が簡単bitcountです。先ほど見たオプションでは、バッファを補充した後、通常57ビットから64ビットになりました。ただし、このバージョンは、56〜63ビットをバッファーに格納することを目的としています（これが、カウンターの制限が1つ減った理由です）。しかし、なぜですか？整数のバイトを挿入すると、補充時bitcountに8の倍数だけ増加します。これは、bitcount & 7（下位3ビット）が変更されないことを意味します。そして、バッファの[56.63]ビットを目指してリフィルを行うと、単一のバイナリOR演算で更新されたビット数を計算できます。

これは次の質問につながります：ポインターをシフトするには何バイト必要ですか？ソースの値を見てみましょうbitcount：


などなど。これは(63 - bitcount) >> 3、に追加するバイトで機能しますbitptr。オーバー

ビットの場合bitbuf、bitcountOR演算を数回実行できます。ただし、これが発生すると、同じ値にORを適用するたびに結果が変更されません。したがって、後で消費機能の右へのシフトのためにそれらがより低く移動するとき、すべてはそれらでうまくいきます。ゴミの可能性について心配する必要はありません。

もちろん、これは面白いですが、このバージョンの特別な点は何ですか？上記のオプション3などの代わりに、いつ使用する必要がありますか？

1つの簡単な理由があります。このオプションでは、ロードするアドレスrefillは現在の値に依存しません。bitcount。実際、次のダウンロードアドレスは、前回の補充が完了した直後に認識されます。このわずかな違いは、並外れた実行を行うプロセッサにとって非常に大きな利点です。整数を含む操作の中で、L1キャッシュでヒットした場合でも、読み込み操作は大きな遅延（通常は約3〜5サイクル、ほとんどの整数操作は1サイクルかかります）によって特徴付けられbitcount、サイクルの反復の終了時の正確な値は遅すぎることがわかっています（上で示した可変長の簡単なコードを参照してください）。

ダウンロードアドレスが独立している場合bitcount、これは、前のリフィルが完了した直後に潜在的にロードコマンドを送信できることを意味します。ロードのバイト順がターゲットISAと一致しない場合（たとえば、リトルエンディアンCPUでMSBファーストビットバッファーを使用する場合）、値の可能なバイト順列でダウンロードを完了する十分な時間があります。前の値に依存する唯一のパラメーターbitcountはシフト、つまり、通常1サイクルかかる通常のALU操作です。

簡単にまとめると、このかなり複雑な詰め替えのバージョンは奇妙に見えますが、命令レベルでの並列性の柔軟な増加を提供します。当時の最新バージョンのKraken-Huffmanデコーダーで2016年にテストしたところ、デスクトップPCでの速度の増加は約10％でした（上記の分岐なしのリフィルに比べて）。

Source: https://habr.com/ru/post/J359122/

More articles:


All Articles