c++ - 你会如何转置二进制矩阵？

Question

我在 C++ 中有二进制矩阵，我用 8 位值的 vector 表示。

例如下面的矩阵:

1 0 1 0 1 0 1
0 1 1 0 0 1 1
0 0 0 1 1 1 1

表示为:

const uint8_t matrix[] = {
    0b01010101,
    0b00110011,
    0b00001111,
};

我这样做的原因是因为计算这样一个矩阵和一个 8 位 vector 的乘积变得非常简单和高效(每行只需一个按位 AND 和一个奇偶校验计算)，这是比单独计算每个位要好得多。

我现在正在寻找一种转置此类矩阵的有效方法，但我一直无法弄清楚如何在无需手动计算每一位的情况下进行转置。

澄清一下，对于上面的例子，我想从转置中得到以下结果:

const uint8_t transposed[] = {
    0b00000000,
    0b00000100,
    0b00000010,
    0b00000110,
    0b00000001,
    0b00000101,
    0b00000011,
    0b00000111,
};

注意:我更喜欢一种可以使用任意大小的矩阵进行计算的算法，但我也对只能处理特定大小的算法感兴趣。

Answer 1

我花了更多时间寻找解决方案，并且找到了一些不错的解决方案。

SSE2 方式

在现代 x86 CPU 上，可以使用 SSE2 指令非常高效地转置二进制矩阵。使用此类指令可以处理 16×8 矩阵。

此解决方案的灵感来自 this blog post by mischasan并且远远优于我迄今为止对这个问题的所有建议。

这个想法很简单:

• #include <emmintrin.h>
• 16 包 uint8_t变量到 __m128i
• 使用_mm_movemask_epi8获取每个字节的 MSB，生成 uint16_t
• 使用_mm_slli_epi64将 128 位寄存器移动一位
• 重复直到你得到所有 8 uint16_t小号

一个通用的 32 位解决方案

不幸的是，我还需要在 ARM 上进行这项工作。实现 SSE2 版本后，很容易找到 NEON 等效项，但 Cortex-M CPU(与 Cortex-A 相反)没有SIMD 功能，因此 NEON 目前对我来说不是太有用。

注意:因为 Cortex-M 没有原生 64 位算法，所以我无法在任何答案中使用这些想法建议通过将 8x8 block 视为 uint64_t 来做到这一点.大多数具有 Cortex-M CPU 的微 Controller 也没有太多内存，因此我更喜欢在没有查找表的情况下完成所有这些操作。

经过一番思考，可以使用普通的 32 位算法和一些巧妙的编码来实现相同的算法。这样，我一次可以处理 4×8 个 block 。一位同事建议，神奇之处在于 32 位乘法的工作方式:您可以找到一个 32 位数字，您可以将其乘以，然后每个字节的 MSB 在高 32 位中彼此相邻结果。

• 第 4 包 uint8_t s 在一个 32 位变量中
• 屏蔽每个字节的第一位(使用 0x80808080 )
• 将它乘以 0x02040810
• 取乘法的高 32 位的 4 LSB
• 通常，您可以屏蔽每个字节中的第 N 位(将屏蔽右移 N 位)并与魔数(Magic Number)相乘，然后左移 N 位。这里的优点是，如果您的编译器足够聪明以展开循环，则掩码和“魔数(Magic Number)”都会成为编译时常量，因此移动它们不会导致任何性能损失。最后一系列的 4 位有一些问题，因为一个 LSB 丢失了，所以在那种情况下我需要将输入左移 8 位并使用与第一个 4 位系列相同的方法。

如果您使用两个 4×8 block 执行此操作，那么您可以完成一个 8x8 block 并排列生成的位，以便一切都进入正确的位置。