c - cのバイト配列の任意のビットシーケンスを比較する

Question

C コードにいくつかの uint8_t 配列があり、任意のシーケンスビットを別のビットと比較したいと考えています。たとえば、bitarray_1 と bitarray_2 があり、bitarray_1 のビット 13 ～ 47 を bitarray_2 のビット 5 ～ 39 と比較したいとします。これを行う最も効率的な方法は何ですか?

現在、ビットを新しい一時配列の先頭にコピーし、それらに memcmp を使用する単純な実装があるため、これは私のプログラムの大きなボトルネックです。

score 1 · Accepted Answer

のビット 13 ～ 47 はbitarray_1、のビット 5 ～ 39 と同じですbitarray_1 + 1。
最初の 3 ビット (5 ～ 7) をマスクと比較し、他のビット (8 ～ 39) をと比較しmemcmp()ます。

ビットをシフトしてコピーするよりも、別の方法で表現した方が速いかもしれません。測定する必要があります。

/* code skeleton */
static char bitarray_1_bis[BIT_ARRAY_SIZE*8+1];
static char bitarray_2_bis[BIT_ARRAY_SIZE*8+1];
static const char *lookup_table[] = {
    "00000000", "00000001", "00000010" /* ... */
    /* 256 strings */
    /* ... */ "11111111"
};

/* copy every bit of bitarray_1 to an element of bitarray_1_bis */
for (k = 0; k < BIT_ARRAY_SIZE; k++) {
    strcpy(bitarray_1_bis + 8*k, lookup_table[bitarray_1[k]]);
    strcpy(bitarray_2_bis + 8*k, lookup_table[bitarray_2[k]]);
}
memcmp(bitarray_1_bis + 13, bitarray_2_bis + 5, 47 - 13 + 1);

コピーを可能な限り最小限に制限することができます (またそうすべきです)。

速いかどうかはわかりませんが、速かったとしても驚かないでしょう。繰り返しますが、測定する必要があります。

score 1 · Accepted Answer

これを行う最も簡単な方法は、より複雑なケースをより単純なケースに変換してから、より単純なケースを解決することです。

次のコードでdo_compare()は、より単純なケース (シーケンスが 7 ビットを超えてオフセットされることはなく、s1常にと同じかそれ以上オフセットされs2、シーケンスの長さが 0 以外である) を解決します。次に、compare_bit_sequence()関数は難しいケースを簡単なケースに変換し、do_compare()その作業を行うために呼び出します。

これはビットシーケンスを 1 回通過するだけなので、copy-and-memcmp の実装が改善されることを願っています。

#define NOT_EQUAL 0
#define EQUAL 1

/* do_compare()
 *
 * Does the actual comparison, but has some preconditions on parameters to
 * simplify things:
 *
 *     length > 0
 *     8 > s1_off >= s2_off
 */
int do_compare(const uint8_t s1[], const unsigned s1_off, const uint8_t s2[],
    const unsigned s2_off, const unsigned length)
{
    const uint8_t mask_lo_bits[] =
        { 0xff, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
    const uint8_t mask_hi_bits[] =
        { 0x00, 0x80, 0xc0, 0xe0, 0xf0, 0xf8, 0xfc, 0xfe, 0xff };
    const unsigned msb = (length + s1_off - 1) / 8;
    const unsigned s2_shl = s1_off - s2_off;
    const unsigned s2_shr = 8 - s2_shl;
    unsigned n;
    uint8_t s1s2_diff, lo_bits = 0;

    for (n = 0; n <= msb; n++)
    {
        /* Shift s2 so it is aligned with s1, pulling in low bits from
         * the high bits of the previous byte, and store in s1s2_diff */
        s1s2_diff = lo_bits | (s2[n] << s2_shl);

        /* Save the bits needed to fill in the low-order bits of the next
         * byte.  HERE BE DRAGONS - since s2_shr can be 8, this below line
         * only works because uint8_t is promoted to int, and we know that
         * the width of int is guaranteed to be >= 16.  If you change this
         * routine to work with a wider type than uint8_t, you will need
         * to special-case this line so that if s2_shr is the width of the
         * type, you get lo_bits = 0.  Don't say you weren't warned. */  
        lo_bits = s2[n] >> s2_shr;

        /* XOR with s1[n] to determine bits that differ between s1 and s2 */
        s1s2_diff ^= s1[n];

        /* Look only at differences in the high bits in the first byte */
        if (n == 0)
            s1s2_diff &= mask_hi_bits[8 - s1_off];

        /* Look only at differences in the low bits of the last byte */
        if (n == msb)
            s1s2_diff &= mask_lo_bits[(length + s1_off) % 8];

        if (s1s2_diff)
            return NOT_EQUAL;
    }

    return EQUAL;
}

/* compare_bit_sequence()
 *
 * Adjusts the parameters to match the preconditions for do_compare(), then
 *  calls it to do the work.
 */
int compare_bit_sequence(const uint8_t s1[], unsigned s1_off,
    const uint8_t s2[], unsigned s2_off, unsigned length)
{
    /* Handle length zero */
    if (length == 0)
        return EQUAL;

    /* Makes sure the offsets are less than 8 bits */
    s1 += s1_off / 8;
    s1_off %= 8;

    s2 += s2_off / 8;
    s2_off %= 8;

    /* Make sure s2 is the sequence with the shorter offset */
    if (s1_off >= s2_off)
        return do_compare(s1, s1_off, s2, s2_off, length);
    else
        return do_compare(s2, s2_off, s1, s1_off, length);
}

あなたの例で比較を行うには、次のように呼び出します。

compare_bit_sequence(bitarray_1, 13, bitarray_2, 5, 35)

(ビットにゼロから番号を付けており、bitarray がリトルエンディアンで配置されていると仮定しているため、bitarray2[0] の最下位から 6 番目のビットと、最下位から 6 番目のビットから比較が開始されることに注意してください。 bitarray1[1] のビット)。

score 0 · Accepted Answer

最適化されていないビットシーケンス比較関数は次のとおりです。

#include <stdio.h> 
#include <stdint.h> 
                  //  01234567    01234567
uint8_t bitsA[] = { 0b01000000, 0b00010000 };
uint8_t bitsB[] = { 0b10000000, 0b00100000 };

int bit( uint8_t *bits, size_t bitpoz, size_t len ){
  return (bitpoz<len)? !!(bits[bitpoz/8]&(1<<(7-bitpoz%8))): 0;
}

int bitcmp( uint8_t *bitsA, size_t firstA, size_t lenA,
            uint8_t *bitsB, size_t firstB, size_t lenB ){
  int cmp;
  for( size_t i=0; i<lenA || i<lenB; i++ ){
    if( (cmp = bit(bitsA,firstA+i,firstA+lenA) -
               bit(bitsB,firstB+i,firstB+lenB))  ) return cmp;
  }
  return 0;
}

int main(){
  printf( "cmp: %i\n", bitcmp( bitsA,1,11, bitsB,0,11 ) );
}

編集:これが私の(テストされていない)ビット文字列等価テスト関数です:

#include <stdlib.h> 
#include <stdint.h> 

#define load_64bit(bits,first) (*(uint64_t*)bits<<first | *(bits+8)>>(8-first)) 
#define load_32bit(bits,first) (*(uint32_t*)bits<<first | *(bits+4)>>(8-first)) 
#define load_16bit(bits,first) (*(uint16_t*)bits<<first | *(bits+2)>>(8-first)) 
#define load_8bit( bits,first) (           *bits<<first | *(bits+1)>>(8-first)) 

static inline uint8_t last_bits( uint8_t *bits, size_t first, size_t size ){
  return (first+size>8?load_8bit(bits,first):*bits<<first)>>(8-size);
}

int biteq( uint8_t *bitsA, size_t firstA,
           uint8_t *bitsB, size_t firstB, size_t size ){
  if( !size ) return 1;
  bitsA+=firstA/8; firstA%=8;
  bitsB+=firstB/8; firstB%=8;

  for(; size>64;size-=64,bitsA+=8,bitsB+=8)
    if(load_64bit(bitsA,firstA)!=load_64bit(bitsB,firstB)) return 0;

  for(; size>32;size-=32,bitsA+=4,bitsB+=4)
    if(load_32bit(bitsA,firstA)!=load_32bit(bitsB,firstB)) return 0;

  for(; size>16;size-=16,bitsA+=2,bitsB+=2)
    if(load_16bit(bitsA,firstA)!=load_16bit(bitsB,firstB)) return 0;

  for(; size> 8;size-= 8,bitsA++, bitsB++ )
    if(load_8bit( bitsA,firstA)!=load_8bit( bitsB,firstB)) return 0;

  return !size || 
         last_bits(bitsA,firstA,size)==last_bits(bitsB,firstB,size);
}

簡単な測定ツールを作成して、速度を確認しました。

#include <unistd.h> 
#include <stdio.h> 
#include <signal.h> 

#define SIZE 1000000 
uint8_t bitsC[SIZE];

volatile int end_loop;
void sigalrm_hnd( int sig ){ (void)sig; end_loop=1; }

int main(){
  uint64_t loop_count; int cmp;
  signal(SIGALRM,sigalrm_hnd);
  loop_count=0; end_loop=0; alarm(10);
  while( !end_loop ){
    for( int i=1; i<7; i++ ){
      loop_count++;
      cmp = biteq( bitsC,i, bitsC,7-i,(SIZE-1)*8 );
      if( !cmp ){ printf( "cmp: %i (==0)\n", cmp ); return -1; }
    }
  }
  printf( "biteq: %.2f round/sec\n", loop_count/10.0 );
}

結果：

bitcmp:   8.40 round/sec
biteq:  363.60 round/sec

EDIT2: last_bits() が変更されました。

score 0 · Accepted Answer

両方の配列からオフセットを計算し、マスクを適用し、ビットをシフトし、結果を int に格納して比較できるようにする関数を作成するのはどうでしょうか。ビット数 (この例では 34) が int の長さを超えている場合 - 再帰またはループ。

申し訳ありませんが、例はお尻の痛みになります。

c - cのバイト配列の任意のビットシーケンスを比較する

5 に答える 5

Related

Reference