c - 二进制矩阵向量乘法

Question

我想将表示为无符号 64 位整数的 8x8二进制矩阵乘以由无符号字符表示的 8 位向量。但是，由于其他一些问题，矩阵必须按列排序，因此没有简单的字节匹配以便于乘法。

知道如何加快这样的计算吗？每个操作都很重要，因为我需要进行数十亿次这样的计算。

乘法是在一个 2 元素字段 (F-2) 上进行的。

Answer 1

使用这种矩阵和向量表示，它有助于以这种方式进行矩阵乘法：

(col ₁ ... col ₈ ) * (v ₁ ... v ₈ ) ^T = col ₁ * v ₁ + ... + col ₈ * v ₈

其中矩阵 A = (col ₁ ... col ₈ )

和列向量 v = (v ₁ ... v ₈ ) ^T

进一步考虑，如果通过重复每个位 8 次然后计算 8 位向量将 8 位向量膨胀为 64 位向量，则可以一次进行所有乘法运算P = A & v_inflated。剩下的唯一事情就是产品的加法（即XOR）。

对产品进行异或的一种简单方法是。

uint64_t P = calculated products from text above;
uint64_t sum = 0;
for( int i = 8; i; --i )
{
   sum ^= P & 0xFF;
   P >> 8;  
}

Answer 2

你只有 256 个向量！使用查找表生成正确的位掩码，然后您的逻辑将类似于

output_bit_n = bool (matrix [n] & lookup [vector])

换句话说，您的查找表可以将 8 位值转换为 64 位世界。

如果编译器不够聪明，无法优化，您可以使用带有旋转进位的指令有效地将其打包到结果中(value<<=1)|=result。