c - 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

假设您的处理器是 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;
}

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