问有效的微小布尔矩阵乘法

EN

正如你所说的，

我猜如果我们不用做那个愚蠢的u32演员的话，这将是大约100条指令。但话又说回来，也许编译器会自动将循环拆分成两部分，在这种情况下，对我们来说很不错。

和

我有种直觉，有一些我错过的超级简单的黑客

，我将解释为，您将询问如何将此代码中32位算术的使用降到最小，该代码用于16位处理器。

您确实应该学习如何分解和检查编译的结果，看看编译器是否会像假设的那样自动拆分循环，但假设没有，我看不出为什么您不能手动进行相同的操作：

static u16 P[32];  /* value assigned elsewhere */

u32 FsiPermutationHack(u16 s) {
    u16 *P_hi = P + 16;
    u16 r_lo = 0;
    u16 r_hi = 0;

    for (u16 i = 0; i < 16; i++) {
        r_lo |= (P[i] & s) != 0) << i;
        r_hi |= (P_hi[i] & s) != 0) << i;
    }

    return ((u32) r_hi << 16) + r_lo;
}

它假设u16和u32是无符号16位和32位整数，没有填充位。

还请注意，使用类型u16而不是u32执行算术应该是一种改进，这一思想假定u32类型的整数提升级别高于unsigned int。粗略地说，这可以归结为实现的unsigned int是一个16位类型。对于16位处理器的实现来说，这是完全合理的。然而，在int和unsigned int为32位类型的系统上，所有较窄的整数算术参数无论如何都将被提升到32位。

更新：

关于更好的替代算法的可能性，我观察到，结果的每一位都是从数组P的不同元素计算出来的，每个元素的全部值都被使用，并且元素大小与目标机器的本地字大小相同。因此，似乎没有比数组元素更少的16位按位执行和操作的空间了(但请参阅下面)。

如果我们接受必须单独处理每个数组元素，那么提供的实现在有效地处理它方面做得相当好：

• 它只执行16位的计算，直到最后的结果集合；
• 它在相同的循环中计算结果的上、下半部分，因此只产生16次循环开销，而不是32次循环开销。
• 它在很大程度上删除了通过创建P_hi访问数组上半部分所需要的额外索引算法。

可以手动展开循环以节省更多的周期，但这是一种绝对应该依赖编译器来执行的优化。

至于“位旋转黑客”，我看到的唯一范围是将16位数组元素的相邻对作为32位无符号整数进行处理。这将允许按位执行一个32位，而不是每两个16位数。这将与两个32位比较(与上述代码中的两个16位比较)相结合。可以保留上述方法的16位移位和按位或操作。除了由于违反严格的混叠规则而导致的形式上未定义的行为之外，这还需要32位算法，这大概是16位机器上16位运算速度的一半。性能的衡量要比预期的要好，但我不认为有任何理由期望从这种方法中取得显著的胜利。