c - 効率的な C BitStream の実装

Question

私は現在、純粋な C で効率的な BitStream を実装するためのさまざまな可能な戦略を研究しています。これは、さまざまなビットベースの圧縮アルゴリズムを実装するために必要です。ただし、このトピックに関する文献はあまり見つけられず、見つけることができる良い例はあまりないようです。

これが私が探しているものです：

関数呼び出しを避けるためのマクロベースの実装
BitStream との間で「n」個のビットを読み書きする関数。
一般的なものよりも最適化された、5ビットなどの特定のビット数を読み書きする関数。

私は次のことについて疑問に思っています：

BitStream で保持する必要がある変数。BYTE ポインター、バイト位置、現在のバイトのビットインデックス、現在のバイトに残っているビット数などがあります。
維持する変数の数を減らす方法。変数が多ければ多いほど、更新する必要のある変数も多くなります。
単一の読み取り/書き込み操作のコンテキストで、中間/一時変数を最小限に抑える方法。
操作を BYTE レベルで行うか、UINT16 レベルまたは UINT32 レベルで行う必要があるか。おそらく、ビットを UINT32 に蓄積し、それがいっぱいになったときにバイトを書き込む (またはフラッシュ操作で書き込みが完了したときに) バイトごとにすべてを行うよりもはるかに高速です。
できるだけループを避けるにはどうすればよいでしょうか。理想的には、BitStream に書き込むビット数をループすることは絶対に避けるべきです。

これはやり過ぎに見えるかもしれませんが、圧縮に関連する残りのコードが非常に最適化されている場合、BitStream の部分がすべてを台無しにしているように見えます。たとえば、画像圧縮コードで SIMD CPU 命令を使用してエンコードプロセスの一部を最適化するアセンブリルーチンを目にすることは珍しくありませんが、最後のステップは BitStream への書き込みです。

アイデア、参照、誰か? ありがとうございました！

score 3 · Accepted Answer

記録のために、これが私が最終的に得た BitStream 実装です。ほとんどがマクロベースで、32 ビットアキュムレータを使用します。ビットは最上位ビットから最下位ビットまでアキュムレータに格納されます。たとえば、次のビットが設定されているかどうかをテストするには、(accumulator & 0x80000000) を実行します。これにより、BitStream をあまり操作しなくても、複数のテストを実行することが非常に実用的になります。書き込みでは、アキュムレータにビットを蓄積し、いっぱいになると出力バッファに自動的にフラッシュします。フラッシングは、すべてのビットが書き込まれたときに手動でトリガーすることもできます。あなたの走行距離は異なるかもしれませんが、私はそれに非常に満足しています. ハフマンコーディングを使用する Microsoft Point to Point Compression (MPPC) の実装に使用しましたが、パフォーマンスは優れています。

struct _wBitStream
{
    BYTE* buffer;
    BYTE* pointer;
    DWORD position;
    DWORD length;
    DWORD capacity;
    UINT32 mask;
    UINT32 offset;
    UINT32 prefetch;
    UINT32 accumulator;
};
typedef struct _wBitStream wBitStream;

#define BitStream_Prefetch(_bs) do { \
    (_bs->prefetch) = 0; \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 4)) \
        (_bs->prefetch) |= (*(_bs->pointer + 4) << 24); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 5)) \
        (_bs->prefetch) |= (*(_bs->pointer + 5) << 16); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 6)) \
        (_bs->prefetch) |= (*(_bs->pointer + 6) << 8); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 7)) \
        (_bs->prefetch) |= (*(_bs->pointer + 7) << 0); \
} while(0)

#define BitStream_Fetch(_bs) do { \
    (_bs->accumulator) = 0; \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 0)) \
        (_bs->accumulator) |= (*(_bs->pointer + 0) << 24); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 1)) \
        (_bs->accumulator) |= (*(_bs->pointer + 1) << 16); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 2)) \
        (_bs->accumulator) |= (*(_bs->pointer + 2) << 8); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) <(_bs->capacity + 3)) \
        (_bs->accumulator) |= (*(_bs->pointer + 3) << 0); \
    BitStream_Prefetch(_bs); \
} while(0)

#define BitStream_Flush(_bs) do { \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 0)) \
        *(_bs->pointer + 0) = (_bs->accumulator >> 24); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 1)) \
        *(_bs->pointer + 1) = (_bs->accumulator >> 16); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 2)) \
        *(_bs->pointer + 2) = (_bs->accumulator >> 8); \
    if (((UINT32) (_bs->pointer - _bs->buffer)) < (_bs->capacity + 3)) \
        *(_bs->pointer + 3) = (_bs->accumulator >> 0); \
} while(0)

#define BitStream_Shift(_bs, _nbits) do { \
    _bs->accumulator <<= _nbits; \
    _bs->position += _nbits; \
    _bs->offset += _nbits; \
    if (_bs->offset < 32) { \
        _bs->mask = ((1 << _nbits) - 1); \
        _bs->accumulator |= ((_bs->prefetch >> (32 - _nbits)) & _bs->mask); \
        _bs->prefetch <<= _nbits; \
    } else { \
        _bs->mask = ((1 << _nbits) - 1); \
        _bs->accumulator |= ((_bs->prefetch >> (32 - _nbits)) & _bs->mask); \
        _bs->prefetch <<= _nbits; \
        _bs->offset -= 32; \
        _bs->pointer += 4; \
        BitStream_Prefetch(_bs); \
        if (_bs->offset) { \
            _bs->mask = ((1 << _bs->offset) - 1); \
            _bs->accumulator |= ((_bs->prefetch >> (32 - _bs->offset)) & _bs->mask); \
            _bs->prefetch <<= _bs->offset; \
        } \
    } \
} while(0)

#define BitStream_Write_Bits(_bs, _bits, _nbits) do { \
    _bs->position += _nbits; \
    _bs->offset += _nbits; \
    if (_bs->offset < 32) { \
        _bs->accumulator |= (_bits << (32 - _bs->offset)); \
    } else { \
        _bs->offset -= 32; \
        _bs->mask = ((1 << (_nbits - _bs->offset)) - 1); \
        _bs->accumulator |= ((_bits >> _bs->offset) & _bs->mask); \
        BitStream_Flush(bs); \
        _bs->accumulator = 0; \
        _bs->pointer += 4; \
        if (_bs->offset) { \
            _bs->mask = ((1 << _bs->offset) - 1); \
            _bs->accumulator |= ((_bits & _bs->mask) << (32 - _bs->offset)); \
        } \
    } \
} while(0)

void BitStream_Attach(wBitStream* bs, BYTE* buffer, UINT32 capacity)
{
    bs->position = 0;
    bs->buffer = buffer;
    bs->offset = 0;
    bs->accumulator = 0;
    bs->pointer = bs->buffer;
    bs->capacity = capacity;
    bs->length = bs->capacity * 8;
}

wBitStream* BitStream_New()
{
    wBitStream* bs = NULL;

    bs = (wBitStream*) calloc(1, sizeof(wBitStream));

    return bs;
}

void BitStream_Free(wBitStream* bs)
{
    free(bs);
}

score 1 · Accepted Answer

うーん。残念ながら、私が指摘しようとしているのは必ずしも効率的な実装ではありません.誰かがより良い答えを投稿することを願っています. しかし、これを回答として投稿する価値があると思うほど、あなたの理解には十分な穴があります。

まず第一に、優れたパフォーマンスのためにマクロは必要ありません! これは、非常に古いコンパイラまたは未熟なコンパイラでコーディングしていない限り、非常に時代遅れのアプローチです。インライン関数は、マクロと同じくらい効率的です (ただし、より効率的になる場合もあります)。静的関数を適切に使用することで、コンパイラは何をインライン化し、何をインライン化しないかを決定できます。gcc は優れたコンパイラーではないかもしれませんが、値がいつ定数であるか、ポインターであるかを判断する点では優れています! これにより、定数をマクロに入れる必要もなくなります。つまり、これは次のとおりです。

#define UINT_BIT_SIZE (sizeof(uint) * 8)

とまったく同じくらい効率的です

static const size_t UINT_BIT_SIZE = sizeof(uint) * 8;

ただし、後者には型があります。constgcc の最近のバージョン (過去 4 年ほど) では、静的 (またはローカル) とマークされ、値が変更されていない限り、コンパイル時の定数として扱う必要さえありません。コンパイル単位内の任意のコードによって、コンパイル時の定数として扱われます。

CPU キャッシュの出現により、コードの一部が高速または (比較的) 低速になる要因が根本的に変化しました。コードのホットな部分が上位キャッシュ (L1 / L2) に収まらない場合、特にメインメモリにアクセスする必要がある場合は、インライン展開やマクロによって速度が低下します。同様に、一度に複数の場所でデータに触れると、大量のキャッシュミスが発生します。

そうは言っても、私は「ビットクリーク」を書きました。これは、Linux デバイスドライバーの非パフォーマンスクリティカルな部分のマイナーな実装です (「クリーク」は「ストリームではない」という意味です)。はstruct bit_creek、ビットのストリームとして扱うメモリのセグメントを表し、関数は、バッファをオーバーランした場合に返されるストリームとして読み取りまたは書き込みをcreek_get_bits行います。creek_put_bits-EOVERFLOW

構造体にskip_bitsを格納し、さらにあなたが示唆したように、完全なバイトになるまでバイトをメインメモリに書き込むことさえしないと、おそらくパフォーマンスをさらに絞り出すことができますが、パフォーマンスはまったく重要ではありませんでした。

幸運を！

c - 効率的な C BitStream の実装

2 に答える 2

Related

Reference