6

私は過去に何度もこれをしなければならなかった、そして私は結果に決して満足しなかった。

ソースと宛先の両方が便利なプロセッサ境界で整列（右シフト）されない可能性があるソースから宛先に連続したビット配列をコピーする高速な方法を誰かが提案できますか？

ソースと宛先の両方が整列されていない場合、問題はすぐにどちらか一方だけが整列されていない問題に変更される可能性があります（最初のコピーが言った後）。

出発点として、私のコードは必然的に次のようになります（テストされていない、副作用を無視するこれは単なるカフの例ではありません）：

const char mask[8] = { 1, 3, 7, 15, 31, 63, 127, 255 };
/* Assume:
 * - destination is already zeroed,
 * - offsets are right shifts
 * - bits to copy is big (> 32 say)
 */
int bitarray_copy(char * src, int src_bit_offset, int src_bit_len,
                  char * dst, int dst_bit_offset) {
    if (src_bit_offset == dst_bit_offset) { /* Not very interesting */ 
    } else {
        int bit_diff_offset = src_bit_offset - dst_bit_offset; /* assume positive */
        int loop_count;
        char c;
        char mask_val = mask[bit_diff_offset];

        /* Get started, line up the destination. */
        c  = (*src++ << bit_diff_offset) | ((*src >> (8 - bit_diff_offset)) & mask_val);
        c &= mask[8-dst_bit_offset];

        *dst++ |= c;

        src_bit_len -= 8 - dst_bit_offset;
        loop_count = src_bit_len >> 3;

        while (--loop_count >= 0) 
            * dst ++ = (*src++ << bit_diff_offset) | ((*src >> (8 - bit_diff_offset)) & mask_val);

        /* Trailing tail copy etc ... */
        if (src_bit_len % 8) /* ... */
    }
}

（実際、これは私が以前に行ったよりも優れています。それほど悪くはありません）

4

4 に答える 4

7

これが私がやったことです。（編集は2014年8月21日にシングルビットコピーのバグのために変更されました。）

#include <limits.h>
#include <string.h>
#include <stddef.h>

#define PREPARE_FIRST_COPY()                                      \
    do {                                                          \
    if (src_len >= (CHAR_BIT - dst_offset_modulo)) {              \
        *dst     &= reverse_mask[dst_offset_modulo];              \
        src_len -= CHAR_BIT - dst_offset_modulo;                  \
    } else {                                                      \
        *dst     &= reverse_mask[dst_offset_modulo]               \
              | reverse_mask_xor[dst_offset_modulo + src_len];    \
         c       &= reverse_mask[dst_offset_modulo + src_len];    \
        src_len = 0;                                              \
    } } while (0)


static void
bitarray_copy(const unsigned char *src_org, int src_offset, int src_len,
                    unsigned char *dst_org, int dst_offset)
{
    static const unsigned char mask[] =
        { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
    static const unsigned char reverse_mask[] =
        { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
    static const unsigned char reverse_mask_xor[] =
        { 0xff, 0x7f, 0x3f, 0x1f, 0x0f, 0x07, 0x03, 0x01, 0x00 };

    if (src_len) {
        const unsigned char *src;
              unsigned char *dst;
        int                  src_offset_modulo,
                             dst_offset_modulo;

        src = src_org + (src_offset / CHAR_BIT);
        dst = dst_org + (dst_offset / CHAR_BIT);

        src_offset_modulo = src_offset % CHAR_BIT;
        dst_offset_modulo = dst_offset % CHAR_BIT;

        if (src_offset_modulo == dst_offset_modulo) {
            int              byte_len;
            int              src_len_modulo;
            if (src_offset_modulo) {
                unsigned char   c;

                c = reverse_mask_xor[dst_offset_modulo]     & *src++;

                PREPARE_FIRST_COPY();
                *dst++ |= c;
            }

            byte_len = src_len / CHAR_BIT;
            src_len_modulo = src_len % CHAR_BIT;

            if (byte_len) {
                memcpy(dst, src, byte_len);
                src += byte_len;
                dst += byte_len;
            }
            if (src_len_modulo) {
                *dst     &= reverse_mask_xor[src_len_modulo];
                *dst |= reverse_mask[src_len_modulo]     & *src;
            }
        } else {
            int             bit_diff_ls,
                            bit_diff_rs;
            int             byte_len;
            int             src_len_modulo;
            unsigned char   c;
            /*
             * Begin: Line things up on destination. 
             */
            if (src_offset_modulo > dst_offset_modulo) {
                bit_diff_ls = src_offset_modulo - dst_offset_modulo;
                bit_diff_rs = CHAR_BIT - bit_diff_ls;

                c = *src++ << bit_diff_ls;
                c |= *src >> bit_diff_rs;
                c     &= reverse_mask_xor[dst_offset_modulo];
            } else {
                bit_diff_rs = dst_offset_modulo - src_offset_modulo;
                bit_diff_ls = CHAR_BIT - bit_diff_rs;

                c = *src >> bit_diff_rs     &
                    reverse_mask_xor[dst_offset_modulo];
            }
            PREPARE_FIRST_COPY();
            *dst++ |= c;

            /*
             * Middle: copy with only shifting the source. 
             */
            byte_len = src_len / CHAR_BIT;

            while (--byte_len >= 0) {
                c = *src++ << bit_diff_ls;
                c |= *src >> bit_diff_rs;
                *dst++ = c;
            }

            /*
             * End: copy the remaing bits; 
             */
            src_len_modulo = src_len % CHAR_BIT;
            if (src_len_modulo) {
                c = *src++ << bit_diff_ls;
                c |= *src >> bit_diff_rs;
                c     &= reverse_mask[src_len_modulo];

                *dst     &= reverse_mask_xor[src_len_modulo];
                *dst |= c;
            }
        }
    }
}
于 2010-08-20T22:39:38.243 に答える
1

内部ループは2バイトの断片を取り、それらを宛先バイトに移動します。それはほぼ最適です。以下に、順不同でいくつかのヒントを示します。

  • 一度に1バイトに制限する必要はありません。プラットフォームで回避できる最大の整数サイズを使用してください。もちろん、これは開始ロジックと終了ロジックを複雑にします。
  • 符号なし文字または整数を使用する場合は、右にシフトした後、ソースの2番目の部分をマスクする必要がない場合があります。これはコンパイラによって異なります。
  • マスクが必要な場合は、コンパイラがテーブルルックアップをループの外に移動していることを確認してください。そうでない場合は、一時変数にコピーして使用します。
于 2010-08-20T20:25:12.163 に答える
1

最適なものは、ターゲットプラットフォームによって異なります。バレルシフタのない一部のプラットフォームでは、ベクトル全体を1ビット右または左に1ビットシフトし、n <3の場合、最速のアプローチになります（PIC18プラットフォームでは、左に1ビットシフトするための8倍展開バイトループのコストは11です。 8バイトあたりの命令サイクル）。そうでなければ、私はパターンが好きです（バッファの終わりで何をしたいかに応じてsrc2を初期化する必要があることに注意してください）

  src1 = * src ++;
  src2 =（src1 shl shiftamount1）| （src2 shr shiftamount2）;
  * dest ++ = src2;
  src2 = * src ++;
  src1 =（src2 shl shiftamount1）| （src1 shr shiftamount2）;
  * dest ++ = src1;

これは、ARMでの非常に効率的な実装に役立ちます（レジスタがsrc、dest、src1、src2、shiftamount1、およびshiftamount2で使用可能な場合、2ワードごとに8つの命令。より多くのレジスタを使用すると、マルチワードのロード/ストアによる操作が高速化されます。 4ワードの処理は、次のようになります（最初の4行が一緒になって、最後の4行と同様に1つの命令になることを除いて、1行に1つのマシン命令）：

  src0 = * src ++;
  src1 = * src ++;
  src2 = * src ++;
  src3 = * src ++;
  tmp = src0;
  src0 = src0 shr shiftamount1
  src0 = src0 | src1 shl shiftamount2
  src1 = src1 shr shiftamount1
  src1 = src1 | src2 shl shiftamount2
  src2 = src2 shr shiftamount1
  src2 = src2 | src3 shl shiftamount2
  src3 = src3 shr shiftamount1
  src3 = src3 | tmp shl shiftamount2
  * dest ++ = src0;
  * dest ++ = src1;
  * dest ++ = src2;
  * dest ++ = src3;

16バイトごとに11個の命令がローテーションされます。

于 2010-08-20T20:59:55.757 に答える
0

あなたの解決策は、私が見たほとんどのものと似ています。基本的に、最初と最後に整列されていない作業を行い、中央のメインループは整列されたアクセスを使用します。本当に効率が必要で、非常に長いビットストリームでこれを行う場合は、メインループでSSE2などのアーキテクチャ固有のものを使用することをお勧めします。

于 2010-08-20T20:58:20.420 に答える