c - 高效的微型 boolean 矩阵乘法

Question

我有一些无符号的 16 位整数 s我想映射到一个无符号的 32 位整数 r以这样一种方式，即 s 中的每个翻转位最多翻转 r 中的一个(给定)位-- 只是 0..16 之间的映射和 0..32那是。所以我们可以把它看成一个矩阵方程

Ps = r

其中 P 是 32 x 16 boolean 矩阵，s是 16 x 1 boolean vector 和 r是32 x 1 boolean vector 。我有一种直觉，我缺少一些 super 简单的 hack。重要提示:目标机器是 16 位 mcu!

这是我能做的最好的:

static u16 P[32] = someArrayOrWhatever();

u32 FsiPermutationHack(u16 s) {
    u32 r;
    for (u16 i = 0; i < 32; i++)
    {
            r |= ((u32)((P[i] & s) > 0) << i);
    }
    return r;
}

基本原理是这样的:r 的第 i:th 位为 1 当且仅当 (P[i] & s) != 0x0000 .我太笨了，不会拆解东西，但我猜如果我们不必做那个愚蠢的事情的话，这就像 ~100 条指令 u32 throw 。但话又说回来，也许编译器会为我们自动将循环分成两部分，在这种情况下它看起来对我们来说非常好。

对于切线表示歉意，我只是想分享我尝试过的解决方案——你有更好的解决方案吗？

Answer 1

如你所说，

I am guessing this would be like ~100 instructions IF we didn't have to do that stupid u32 cast. But then again, perhaps the compiler auto-splits the loop in two for us in which case it's looking pretty good for us.

和

I have a gut feeling there exists some super simple hack that I'm missing

，我会将您解释为询问如何在用于 16 位处理器的代码中尽量减少 32 位算术的使用。

你真的应该学习如何反汇编和检查编译结果，看看编译器是否像你假设的那样自动拆分循环，但假设它没有，我不明白你为什么不能做同样的事情手动:

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 的不同元素计算的，使用每个元素的全部值，并且元素大小与目标机器的 native 字大小相同。似乎没有范围可以执行比数组元素更少的 16 位按位 AND 运算(但请参见下文)。

如果我们承认每个数组元素都必须单独处理，那么提供的实现可以很好地有效地处理它:

• 在组装最终结果之前，它只执行 16 位计算；
• 它在同一循环中计算结果的上半部分和下半部分，因此仅产生 16 次迭代的循环开销，而不是 32 次
• 它在很大程度上消除了创建 P_hi 时所需的额外索引算法。用于访问数组的上半部分

手动展开循环可能会节省更多的循环，但这是您绝对应该依赖编译器为您执行的优化。

至于“bit twiddling hacks”，我看到的任何这种性质的唯一范围是将相邻的 16 位数组元素对处理为 32 位无符号整数。这将允许执行一个 32 位按位与来代替每两个 16 位与。这将与两个 32 位比较相结合(vs. 上面代码中的两个 16 位比较)。上述方法的16位移位和按位或操作可以保留。除了由于违反严格的别名规则而导致形式上未定义的行为之外，这将涉及 32 位算术，这大概是 16 位机器上 16 位算术速度的一半。性能的衡量比预期的要好，但我认为没有任何理由期望这种方法会取得重大胜利。