C 从 8 个不同字节中提取 8 位的最快方法是什么？

Question

所以我有一个8字节的数组，我无法控制，也不能直接改变格式。此代码是与硬件通信的瓶颈，因此优化它很重要。

我的任务是提取 1 个字节的有用数据，使用 8 个源字节中每个字节的 1 位。我需要从字节中提取的每一位总是处于相同的偏移量。我从最高有效位到最低有效位构建结果字节。

我现在的解决方案如下

const uint8_t MASK = 0x04;

void extract(uint8_t* data, uint8_t* result) {
  // I assume result starts equal to 0

  uint8_t j = 0x80; // Most significant bit first

  for (uint8_t i = 0; i < 8; ++i) {
    // Check if the bit I am interested in is high
    if (data[i] & MASK) {
      // Set the bit in result high
      *result |= j;
    }

    // Move on to the next bit
    j >>= 1;
  }
}

我觉得这接近最佳，但我不擅长位魔术，所以我很好奇是否有人知道更快的方法。

代码是运行存在于 AM335X 上的 TI-PRU

Answer 1

提供的代码足够高效，但如果您对替代方案感兴趣，首先您可以通过手动展开它来摆脱循环。其次，您可以用一些位运算替换 if 逻辑：

j = (!!(data[0] & MASK)) << 7;
j |= (!!(data[1] & MASK)) << 6;
...
j |= (!!(data[6] & MASK)) << 1;
j |= (!!(data[7] & MASK));

同样，我认为生成的代码不会比启用优化的原始代码好多少。

Answer 2

假设您的处理器是 32 位处理器。

void extract_shift(uint8_t* data, uint8_t* result) {
    uint32_t x1 = (data[0] << 24) | (data[1] << 16) | (data[2] << 8) | data[3];
    uint32_t x2 = (data[4] << 24) | (data[5] << 16) | (data[6] << 8) | data[7];
    x1 &= (MASK << 24) | (MASK << 16) | (MASK << 8) | (MASK);
    x2 &= (MASK << 24) | (MASK << 16) | (MASK << 8) | (MASK);
    x1 = (x1 >> 19) | (x1 >> 12) | (x1 >>  5) | (x1 <<  2);
    x2 = (x2 >> 23) | (x2 >> 16) | (x2 >>  9) | (x2 >>  2);
    *result = (x1 | x2);
}

这尝试使用 32 位加载来加载数据（假设您的处理器允许未对齐加载并且具有正确的字节顺序，或者编译器能够以更好的方式进行字节交换；x86 上的 gcc does that correctly).

然后一次使用 32 位字进行屏蔽。

然后将低位半字节中的位汇集起来，将两个半字节组合起来完成。这是交错完成的，以尝试限制依赖项的数量。

假设你的机器有硬件倍频器，我们可以试试看。如何？乘法是左移的组合。但是在这里我们有左移和右移。因此，让我们在最高有效字节中构建结果，然后将其移回原位：

void extract_premul(uint8_t* data, uint8_t* result) {
    uint32_t x1 = (data[0] << 24) | (data[1] << 16) | (data[2] << 8) | data[3];
    uint32_t x2 = (data[4] << 24) | (data[5] << 16) | (data[6] << 8) | data[7];
    x1 &= (MASK << 24) | (MASK << 16) | (MASK << 8) | (MASK);
    x2 &= (MASK << 24) | (MASK << 16) | (MASK << 8) | (MASK);
    x1 = (x1 <<  5) | (x1 << 12) | (x1 << 19) | (x1 << 26);
    x2 = (x2 <<  1) | (x2 <<  8) | (x2 << 15) | (x2 << 22);
    *result = (x1 | x2) >> 24;
}

现在我们可以使用乘法，用二进制表示有助于理解与上述版本的关系。

void extract_mul(uint8_t* data, uint8_t* result) {
    uint32_t x1 = (data[0] << 24) | (data[1] << 16) | (data[2] << 8) | data[3];
    uint32_t x2 = (data[4] << 24) | (data[5] << 16) | (data[6] << 8) | data[7];
    x1 &= (MASK << 24) | (MASK << 16) | (MASK << 8) | (MASK);
    x2 &= (MASK << 24) | (MASK << 16) | (MASK << 8) | (MASK);
    //  3         2         1
    // 10987654321098765432109876543210
    x1 *= 0b100000010000001000000100000;
    x2 *=     0b10000001000000100000010;
    *result = (x1 | x2) >> 24;
}

与一组移位相比，两个（可流水线化的）乘法的相对性能取决于您的硬件。

Answer 3

假设 MASK 是常量 0x04:

然后读入两个屏蔽的32位值，如@AProgrammer:

uint32_t* dwptr = (uint32_t*)data;
uint32_t x1 = dwptr[0] & 0x04040404;
uint32_t x2 = dwptr[1] & 0x04040404;

相关位设置在 2 个变量的每个字节的位 2 上。

将位移动到方便的位置（对于前 4 个字节，我们需要结果的高 4 位作为标志，因此对于 x1，将其从第 2 位移动到第 4 位 - x2 已经在低 4 位中，我们将补偿 x2 在以下块之后的块中的第 2 位而不是第 0 位）：

x1 <<= 2;

通过左移和 ORing 将这些位翻四倍：

x1 |= x1 << 1;
x1 |= x1 << 2;
x2 |= x2 << 1;
x2 |= x2 >> 2; // we started on bit 2 and not bit 0 for x2 - saved us the shift of x2 in the block above

现在删除不需要的：

x1 &= 0x10204080;
x2 &= 0x01020408;

构建结果（合并所有 8 个字节）：

x1_8* = (uint8_t*)x1;
x1_16* = (uint16_t*)x1;

x1 |= x2;
x1_16[0] |= x1_16[1];
result = x1_8[0] | x1_8[1];

为了便于理解，我用很多行编写了这段代码，但它应该运行相当快 - 对于所有 8 位，我们总共只有 5 次移位和 9 次逻辑运算。

你也可以试试汇编例程，比如

结果例如R0.b0（寄存器 0，字节 0）
MASKBIT 为 2，因为 MASK 为常量 0x04
byte0/byte1/byte2 正在加载到寄存器中，例如R1.b0、R1.b1、R1.b2、R1.b3、R2.b0、R2.b1、R2.b2、R2.b3，如果加载到寄存器 R1 和 R2

        ldi result, 0
        qbbc flag0zero, byte0, MASKBIT
        set result, result, 7
    flag0zero:
        qbbc flag1zero, byte1, MASKBIT
        set result, result, 6
    flag1zero:
        qbbc flag2zero, byte2, MASKBIT
        set result, result, 5
    flag2zero:

等等。

PRU 可以在 1 个周期内完成所有这些内部操作，甚至是组合 bittests/jumps。我们有 8 个位测试和 8 个位集。由于在 RISC 架构上的赋值是 'hidden'，因此在汇编器中执行之前的算法可能会更快一些，因为您可以将目标寄存器与源寄存器分开指定。

可能访问内存或提到的硬件外围设备比标志的计算慢。我们正在谈论 ~20 次操作 @200 MHz，即 100ns 用于完整的标志计算。

您可以启用循环计数器 (https://nerdhut.de/2016/06/18/beaglebone-clock-cycle-counter/) 来衡量什么需要很长时间以及什么解决方案最快。

C 从 8 个不同字节中提取 8 位的最快方法是什么？

What is the fastest way in C to extract 8 bits from 8 different bytes?

c

embedded

optimization

bit-manipulation

bit-shift