c - 8 个 6 位单元的 48 位字符串 : how to get middle 4 bits of each unit quickly

Question

我用C语言实现DES算法差不多了，想优化一下我的代码。所以我使用了gprof。 这是报告的一部分:

Each sample counts as 0.01 seconds.
  %   cumulative   self              self     total           
 time   seconds   seconds    calls  us/call  us/call  name    
 51.78      9.32     9.32  8000000     1.17     1.17  sboxes
 34.71     15.57     6.25  8000000     0.78     0.78  extendRight
  9.90     17.35     1.78   500000     3.56    35.96  operation
  2.39     17.78     0.43  8000000     0.05     0.05  xorRightAndKey

gprof 显示 sboxes 函数占用了 51.78% 的时间。

在 sboxes(uchar aucData[6], ...) 中，我得到了 48 位，将它们分成 8 个槽，每个槽 6 位。

对于每个插槽:

1. 将第一位和最后一位相结合得到X;

2. 获取中间4位得到Y;

3. 用(X, Y)做一些事情；

例如，011110 是一个插槽，所以 X = 00 和 Y = 1111。

为了实现这一点，我将 MACRO 写入内存中的 GET/SET 位，相关代码如下:

#define LOCATE(ptr, index) (((char *)(ptr))[(index) >> 3])

#define GET_BIT(ptr, index) (LOCATE((ptr), (index)) & (((uchar)0x80) >> ((index) % 8)))

这里是获取(X, Y)

的代码

uchar basePos = 0x00;
for (int i = 0; i < 8; ++i) {
    x = 0;
    y = 0;
    basePos = i * 6; // to locate the slot
    // combine first bit with last bit 
    if (0 != GET_BIT(aucData, basePos)) {
        x |= 0x02;
    }   
    if (0 != GET_BIT(aucData, basePos + 5)) {
        x |= 0x01;
    }   
    // get continuous 4 bits
    for (int j = 1; j <= 4; ++j) {
        if (0 != GET_BIT(aucData, basePos + j)) {
            y |= (0x01 << (4 - j));
        }   
    }   
    // do something with (x, y)
}

所以我的问题是，给了我48位，如何尽快得到中间的4位？

Answer 1

没有查找表:

typedef unsigned long long u64;

void sboxes(uchar aucData[6])
{
    u64 v = aucData[0] + (((u64)aucData[1]) << 8)
    + (((u64)aucData[2]) << 16)
    + (((u64)aucData[3]) << 24)
    + (((u64)aucData[4]) << 32)
    + (((u64)aucData[5]) << 40);

    for(int i = 0; i < 8; i++) 
    {
        uchar x = ((v & 1) << 1) | ((v >> 5) & 1);
        uchar y = ((v >> 1) & 0xF);
        // do something with x, y
        printf("x: %hhu, y: %hhu\n", x, y);

        v >>= 6;
    }
}

完全免责声明:我没有进行基准测试。但它应该很快。如果它仍然太慢，您可以更快地打包到 u64 中。