比较c中字节数组中的任意位序列

Question

我的C代码中有几个uint8_t数组，我想将任意一个序列位与另一个序列进行比较。例如，我有bitarray_1和bitarray_2，我想将bitarray_1的13-47位与bitarray_2的5-39位进行比较。最有效的方法是什么？

当前，这是我程序中的一个巨大瓶颈，因为我只有一个幼稚的实现，可以将这些位复制到新的临时数组的开头，然后对它们使用memcmp。

Answer 1

三个词：shift，mask和xor。

移位以获得两个位数组的相同内存对齐方式。如果不是，则在比较它们之前必须先移动其中一个数组。您的示例可能会引起误解，因为位13-47和5-39在8位地址上具有相同的内存对齐方式。如果您将14-48位与5-39位进行比较，那将不是真的。

一旦所有内容对齐并且清除了表边界以外的所有位，则异或就足以一次执行所有位的比较。基本上，您可以通过为每个阵列读取一个内存来做到这一点，这应该非常有效。

如果两个数组的内存对齐方式与示例memcmp中的相同，并且上限和下限的特殊情况可能更快。

同样，通过uint32_t（或在64位体系结构上的uint64_t）访问数组也应该比通过uint8_t访问数组更有效。

原理很简单，但正如Andrejs所说的那样，实现并非一帆风顺。

这是怎么回事（与@caf提案的相似之处并非偶然）：

/* compare_bit_sequence() */
int compare_bit_sequence(uint8_t s1[], unsigned s1_off, uint8_t s2[], unsigned s2_off,
    unsigned length)
{
const uint8_t mask_lo_bits[] =
    { 0x00, 0x01, 0x03, 0x07, 0x0f, 0x1f, 0x3f, 0x7f, 0xff };
const uint8_t clear_lo_bits[] =
    { 0xff, 0xfe, 0xfc, 0xf8, 0xf0, 0xe0, 0xc0, 0x80, 0x00 };
uint8_t v1;
uint8_t * max_s1;
unsigned end;
uint8_t lsl;
uint8_t v1_mask;
int delta;

/* Makes sure the offsets are less than 8 bits */
s1 += s1_off >> 3;
s1_off &= 7;

s2 += s2_off >> 3;
s2_off &= 7;

/* Make sure s2 is the sequence with the shorter offset */
if (s2_off > s1_off){
    uint8_t * tmp_s;
    unsigned tmp_off;
    tmp_s = s2; s2 = s1; s1 = tmp_s;
    tmp_off = s2_off; s2_off = s1_off; s1_off = tmp_off;
}
delta = s1_off;

/* handle the beginning, s2 incomplete */ 
if (s2_off > 0){
    delta = s1_off - s2_off;
    v1 = delta
       ? (s1[0] >> delta | s1[1] << (8 - delta)) & clear_lo_bits[delta]
       : s1[0];
       if (length <= 8 - s2_off){
           if ((v1 ^ *s2)
                & clear_lo_bits[s2_off]
                & mask_lo_bits[s2_off + length]){
                return NOT_EQUAL;
           }
           else {
               return EQUAL;
           }
        }
        else{
            if ((v1 ^ *s2) & clear_lo_bits[s2_off]){
                return NOT_EQUAL;
        }
        length -= 8 - s2_off;
    }
    s1++;
    s2++;
}

/* main loop, we test one group of 8 bits of v2 at each loop */
max_s1 = s1 + (length >> 3);
lsl = 8 - delta;
v1_mask = clear_lo_bits[delta];
while (s1 < max_s1)
{
    if ((*s1 >> delta | (*++s1 << lsl & v1_mask)) ^ *s2++)
    {
        return NOT_EQUAL;
    }
}

/* last group of bits v2 incomplete */
end = length & 7;
if (end && ((*s2 ^ *s1 >> delta) & mask_lo_bits[end]))
{
    return NOT_EQUAL;
}

return EQUAL;

}

尚未使用所有可能的优化。一种有前途的方法是使用更大的数据块（一次使用64位或32位而不是8位），您还可以检测到两个数组的偏移都已同步的情况，在这种情况下，请使用memcmp代替主循环，替换用逻辑运算符＆7对％8取模，用'>> 3'等代替'/ 8'，必须到代码分支，而不是交换s1和s2等，但主要目的是实现的：仅读取和读取一个存储器不是对每个数组项进行内存写入，因此大多数工作都可以在处理器寄存器内进行。