8

bitwise を実装する最良の方法は何memmoveですか? メソッドは追加の宛先とソースのビットオフセットを取り、カウントもビット単位である必要があります。

  • ARM が非標準の を提供している_membitmoveことがわかりました。これはまさに私が必要としているものですが、そのソースが見つかりませんでした。
  • バインドのビットセットにはisc_bitstring_copyが含まれていますが、効率的ではありません
  • C 標準ライブラリがそのようなメソッドを提供していないことは承知していますが、同様のメソッドを提供するサードパーティ コードも見つかりませんでした。
4

2 に答える 2

1

「最良」が「最も簡単」を意味すると仮定すると、ビットを 1 つずつコピーできます。概念的には、ビットのアドレスは、メモリ内のバイトへのポインターとバイト内のビットのインデックスを持つオブジェクト (構造体) です。

struct pointer_to_bit
{
    uint8_t* p;
    int b;
};

void membitmovebl(
    void *dest,
    const void *src,
    int dest_offset,
    int src_offset,
    size_t nbits)
{
    // Create pointers to bits
    struct pointer_to_bit d = {dest, dest_offset};
    struct pointer_to_bit s = {src, src_offset};

    // Bring the bit offsets to range (0...7)
    d.p += d.b / 8; // replace division by right-shift if bit offset can be negative 
    d.b %= 8; // replace "%=8" by "&=7" if bit offset can be negative
    s.p += s.b / 8;
    s.b %= 8;

    // Determine whether it's OK to loop forward
    if (d.p < s.p || d.p == s.p && d.b <= s.b)
    {
        // Copy bits one by one
        for (size_t i = 0; i < nbits; i++)
        {
            // Read 1 bit
            int bit = (*s.p >> s.b) & 1;

            // Write 1 bit
            *d.p &= ~(1 << d.b);
            *d.p |= bit << d.b;

            // Advance pointers
            if (++s.b == 8)
            {
                s.b = 0;
                ++s.p;
            }
            if (++d.b == 8)
            {
                d.b = 0;
                ++d.p;
            }
        }
    }
    else
    {
        // Copy stuff backwards - essentially the same code but ++ replaced by --
    }
}

速度を最適化したバージョンを作成したい場合は、バイト単位で (または、単語単位で) コピーし、ループをアンロールし、多くの特殊なケースを処理するmemmove必要があります (それを行います。はもっと複雑です）。

PSああ、あなたがisc_bitstring_copy非効率的と呼んでいることを見て、おそらく速度の最適化が必要です。次のアイデアを使用できます。

コピー先がバイト単位になるまでビット単位でコピーを開始します ( d.b == 0)。次に、少しいじって、一度に 8 ビットをコピーするのは簡単です。コピーするビットが 8 ビット未満になるまでこれを行います。次に、ビットを 1 つずつコピーし続けます。

// Copy 8 bits from s to d and advance pointers
*d.p = *s.p++ >> s.b;
*d.p++ |= *s.p << (8 - s.b);

PPS ああ、コードを何に使用するかについてのコメントを見て、実際にはすべてのバージョン (バイト/ハーフワード/ワード、ビッグ/リトルエンディアン) を実装する必要はありません。最も簡単なもの、つまり単語を操作するもの ( uint32_t) だけが必要です。

于 2013-09-21T17:37:09.663 に答える