在相同偏移量下快速搜索两个整数的一些半字节(C,微优化)

Question

我的任务是检查(> trillions检查),两个int是否包含任何预定义的半字节对(第一对0x2 0x7;第二对0xd 0x8).例如:

bit offset:   12345678
first int:  0x3d542783     first pair of  0x2    second:   0xd   
second int: 0x486378d9      nibbles:      0x7      pair:   0x8
               ^  ^

所以,对于这个例子,我用需要的对标记两个偏移(偏移是2和5;但不是7).我的任务中不需要实际偏移量和找到的对数.

因此,对于给定的两个整数,问题是:它们是否包含相同偏移量的这些半字节对中的任何一个.

我检查了我的程序,这部分是最热门的地方(gprof经过验证); 它被称为非常多次(gcov证明).实际上它是嵌套循环的第3或第4个循环(嵌套最多).

我当前的代码很慢(我将其重写为函数,但它是内循环的代码):

static inline int nibble_check (uint32_t A, uint32_t B)
 __attribute__((always_inline))
{
  int i;
  for(i=0;i<8;i++)

    if(  ( ( (A&0xf) ==0xD) && ( (B&0xf) ==0x8) )     // first pair
      || ( ( (A&0xf) ==0x2) && ( (B&0xf) ==0x7) )  )  // second pair
        return 1; // nibbles found
    else {
        A>>=4;
        B>>=4;
    }

  return 0; // nibbles not found
}

另一个任务是不仅在偏移0,4,8位等处找到这对,而且在偏移0,2,4,8,10,......位:

#define douburu_nibble_check(A,B) (nibble_check(A,B) || nibble_check(A>>2, B>>2) )

是否有可能以并行方式重写此函数和宏？

我的编译器是gcc452,cpu是32位模式下的Intel Core2 Solo(x86).

Answer 1

有一些技巧可以测试单词中的零字节(参见http://graphics.stanford.edu/~seander/bithacks.html#ZeroInWord); 一个快速的方法是使用这个表达式:

(x - 0x01010101) & ~x & 0x80808080

如果32位字中的4个字节中的任何一个为0,则评估为某个非零值,否则为0.

此方法可以适用于此处:

static inline int nibble_check(uint32_t A, uint32_t B)
{
  uint32_t tmp1, tmp2;

  tmp1 = (A ^ 0x22222222) | (B ^ 0x77777777);
  tmp2 = (A ^ 0xdddddddd) | (B ^ 0x88888888);

  return !!(((tmp1 - 0x11111111) & ~tmp1 & 0x88888888) |
            ((tmp2 - 0x11111111) & ~tmp2 & 0x88888888));
}