8个6位单元的48位字符串：如何快速获取每个单元的中间4位

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比特。

每个插槽：

将第一位和最后一位结合得到X;
获取中间4位得到Y;
用(X, Y)做点什么；

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

为了实现这个，我在内存中的GET/SET位写了MACRO，这里是相关代码：

#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

没有查找 table:

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 中。

8个6位单元的48位字符串：如何快速获取每个单元的中间4位

48-bit string of eight 6-bit units: how to get middle 4 bits of each unit quickly

c

algorithm

assembly

des