这么复杂的函数用来测试变量是否为零，有什么好处呢？

Question

我正在撰写计算机科学硕士论文，研究的是针对后量子安全签名编写的代码。整个内容可以在这里找到，但这不是重点。为了论文，我尝试解释一个“简单”的函数，但实际上并不简单。

该函数测试变量在伽罗华域GF(16)中是否为非零值。（这里的GF(16)可以理解为4位无符号整数）。该函数如下：

static inline uint8_t gf16_is_nonzero(uint8_t a) {
    unsigned a4 = a & 0xf; // mask lowest 4 bits of a
    unsigned r = 0u - a4;  // set 4 high bits if a is nonzero
    r >>= 4;               // right-shift high bits into low bits
    return r & 1;          // return lowest bit
}

我理解它的工作原理，但我不明白为什么这个函数需要如此复杂。可能有很好的理由，比如性能或安全方面的好处（例如防止时间攻击）。因为如果没有这些好处，把函数写成简单易懂的方式岂不更聪明：

static inline uint8_t gf16_is_nonzero(uint8_t a) {
    return (a & 15) != 0;
}

修改

这段代码不是我写的，而是由加密研究人员编写的，他们正在尝试让他们的PQ算法被NIST标准化。

TonyDelroy在评论中提出了第二个代码片段的更简单的方法。

- linderd

---

好奇。为什么要使用 & 0xf 和后面使用 & 15 的区别？ - chux - Reinstate Monica

F在十六进制中是十进制的15。我后来只使用了15，因为它更明显。 - linderd

最明显的是 0b1111；然后是 0xF。对于位掩码，15 是最不明显的。 - Vlad Feinstein

我认为这取决于情况，如果你正在使用GF16，那么很明显。但整个问题不在于此。 - linderd

Answer 1

这段代码之所以这样写，是因为它是无分支的。

测试条件通常是一项昂贵的操作，而加法、减法和位运算则不然。

但这是过早地进行优化。使用-O3编译第一个函数会得到以下结果：

andl    $15, %edi
negl    %edi
shrl    $31, %edi
movl    %edi, %eax
ret

第二个函数编译成以下内容：

andl    $15, %edi
setne   %al
ret

故事的寓意是：编写清晰表达您意图的代码，然后让编译器来处理其余部分。

- dbush

---

额外说明：编译器本来可能会生成无分支代码，而这段代码可能会更慢/更长。 - Dietrich Epp

因为这是加密代码，可能甚至不允许有可能的分支。在加密领域，“仅依赖编译器”这种说法很滑稽。 - harold

是的，我认为@harold说得有道理。问题不在于分支会很昂贵，而在于它意味着执行时间可能取决于数据，这就为侧信道攻击打开了大门。 - Nate Eldredge

比较操作并不昂贵 - 请参阅https://www.agner.org/optimize/instruction_tables.pdf - 它们会设置标志位作为副作用，可以使用类似于setne的指令而不需要跳转，但这完全取决于CPU指令集。 尽管如此，没有任何理由不采用x＆15 == 0，我无法想象问题中编写复杂代码以避免分支。 对我来说，这种奇怪的代码似乎是出于FUD（恐惧、不确定和怀疑）的驱动。 或许是由某个过度思考的硬件工程师编写的。 - Tony Delroy

说比较不是分支，这都是虚假信息，这种说法很容易。但是，比较可能会导致分支，也可能不会，这通常发生在优化后。无论哪种情况都没有保证。 - harold