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

Question

我的任务是检查(>万亿次检查)，两个 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)。我的任务不需要实际偏移量和找到的对数。

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

我检查了我的程序，这部分是 HitTest 的地方(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 是 Intel Core2 Solo，32 位模式 (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));
}