如果只需要低位结果，哪些2补数整数运算可以在不将输入高位清零的情况下使用？

Question

在汇编编程中，经常需要从一个寄存器的低位计算出某些内容，而该寄存器并不保证其他位为零。在高级语言（如C）中，你只需将输入强制转换为小尺寸，让编译器决定是否需要单独清零每个输入的高位，或者是否可以在计算结果后截取结果的高位。

这在x86-64（也称为AMD64）中特别常见，原因有很多¹，其中一些也存在于其他ISA中。

我将使用64位x86作为示例，但意图是讨论二进制补码和无符号二进制算术，因为所有现代CPU都使用它。（请注意，C和C ++不保证二进制补码⁴，且有符号溢出是未定义行为。）

作为一个例子，考虑一个可以编译成LEA指令的简单函数²。（在x86-64 SysV（Linux）ABI³中，前两个函数参数位于rdi和rsi中，返回值在rax中。int是一个32位类型。）

; int intfunc(int a, int b) { return a + b*4 + 3; }
intfunc:
    lea  eax,  [edi + esi*4 + 3]  ; the obvious choice, but gcc can do better
    ret

gcc知道即使是负有符号整数的加法也只会从右到左进位，因此输入的高位不能影响进入eax的内容。因此，它节省了一字节指令并使用了lea eax，[rdi + rsi * 4 + 3]

还有哪些操作具有结果的低位与输入的高位无关的特性？

为什么这样做有效呢？

---

---

脚注

¹ 为什么这在x86-64中经常出现： x86-64具有可变长度指令，其中额外的前缀字节会改变操作数大小（从32位到64位或16位），因此在执行速度相同的指令中通常可以节省一个字节。当写入寄存器的低8位或16位时（AMD/P4/Silvermont）存在假依赖性，或者在以后读取完整寄存器时存在停顿（Intel pre-IvB）：由于历史原因，仅向32位子寄存器写入会将其余64位寄存器清零。几乎所有算术和逻辑都可以用于通用寄存器的低8、16或32位以及完整的64位。整数矢量指令也相当不正交，某些元素大小的一些操作不可用。

此外，与x86-32不同，ABI在寄存器中传递函数参数，并且对于窄类型，不需要将高位设置为零。

² LEA: 与其他指令一样，LEA 的默认操作数大小为32位，但默认地址大小为64位。操作数大小前缀字节（0x66或REX.W）可以使输出操作数大小为16位或64位。地址大小前缀字节（0x67）可以将地址大小减小到32位（在64位模式下）或16位（在32位模式下）。因此，在64位模式下，lea eax，[edx + esi]比lea eax，[rdx + rsi]多占用一个字节。

可以使用lea rax，[edx + esi]，但地址仍然只使用32位计算（进位不会设置rax的第32位）。您可以使用lea eax，[rdx + rsi]获得相同的结果，它比前者短两个字节。因此，在Agner Fog的出色objconv反汇编输出中的注释中警告，地址大小前缀永远没有用处。

³ x86 ABI：调用方不必将用于传递或返回较小类型的64位寄存器的上半部分清零（或符号扩展）。希望将返回值用作数组索引的调用者必须对其进行符号扩展（使用movzx rax，eax或特殊情况下针对eax的指令cdqe。（不要与将eax符号扩展为edx：eax的cdq混淆，例如为了设置idiv而进行的操作。）

这意味着返回 unsigned int 的函数可以在一个64位的临时变量 rax 中计算其返回值，而不需要 mov eax, eax 来清零 rax 的高位。这个设计决策在大多数情况下都很有效：通常调用者不需要任何额外的指令来忽略 rax 上半部分的未定义位。

---

⁴ C和C++

C和C++不需要二进制补码有符号整数（除了C++ std::atomic类型）。 补码反码和原码也是允许的, 所以对于完全可移植的C来说，这些技巧只对unsigned类型有用。显然，对于有符号操作，补码表示中的设置符号位意味着其他位被减去，而不是相加，例如。 我还没有研究过反码的逻辑。

然而，仅适用于二进制补码的位操作技巧非常普遍，因为在实际应用中，没有人关心其他任何东西。许多适用于二进制补码的方法也应该适用于一的补码，因为符号位不会改变其他位的解释：它只有一个值为-(2^N-1)（而不是2^N）。但是，采用符号/大小表示法的每个位的位置值都取决于符号位的正负。

此外请注意，C编译器可以假设有符号溢出永远不会发生，因为这是未定义的行为。例如编译器可能会并且确实假定 (x+1) < x 总是为false。这使得在C中检测有符号溢出变得相当麻烦。请注意无符号环绕（进位）和有符号溢出之间的区别。

- Peter Cordes

Answer 1

可与高位垃圾数据一起使用的宽操作：

• 按位逻辑运算
• 左移（包括 [reg1 + reg2*scale + disp] 中的 *scale）
• 加法/减法（因此也包括 LEA 指令：不需要地址大小前缀。只需使用所需的操作数大小进行截断即可。）

• 乘积的低半部分。例如，16位 x 16位 -> 16位可以通过32位 x 32位 -> 32位来完成。您可以通过使用32位的 imul r32, r/m32, imm32 然后仅读取结果的低16位来避免来自imul r16，r/m16，imm16 的LCP停顿（和部分寄存器问题）。（但是，如果使用 m32 版本，则需要小心更宽的内存引用。）

  正如英特尔指令参考手册所指出的那样，imul 的2和3操作数形式对无符号整数的使用是安全的。输入的符号位不会影响结果的N位在一个 N x N -> N 位乘法中。）

• 2^x （即向左移动 x 位）：至少在x86上有效，其中移位计数被掩码，而不是饱和，直到操作的宽度，因此高位垃圾数据在 ecx 中，甚至在 cl 的高位也不会影响移位计数。也适用于BMI2无标志移位（shlx 等），但不适用于矢量移位（pslld xmm，xmm/m128 等，这些会使计数饱和）。聪明的编译器优化了移位计数的掩码，从而允许C中安全的旋转惯用语（没有未定义的行为）。

显然，标志如进位/溢出/符号/零都会受到宽操作中高位垃圾数据的影响。x86的移位将最后移出的位放入进位标志中，因此这甚至影响移位。

不能与高位垃圾数据一起使用的操作：

• 右移

• 全乘法：例如对于16位x 16位 -> 32位，确保输入的高16位在进行32位x 32位 -> 32位imul之前为零或符号扩展。或使用16位单操作数mul或imul将结果不方便地放入dx：ax中。（有符号与无符号指令的选择将以与在32位imul之前零扩展或符号扩展相同的方式影响高16位。）

• 内存寻址（[rsi + rax]）：根据需要进行符号或零扩展。没有[rsi + eax]寻址模式。

• 除法和余数

• log2（即最高位的位置）
• 尾零计数（除非您知道您想要的部分中有一个设置位，否则只需检查结果是否大于N作为未找到检查。）

---

二进制补码与无符号二进制一样，是一种按位计数系统。无符号二进制的MSB在N位数字中具有2^N-1的位值（例如2³¹）。在二进制补码中，MSB的值为-2^N-1（因此起到符号位的作用）。维基百科文章解释了理解二进制补码和对无符号二进制数取反的许多其他方法。

关键点是设置符号位不会改变其他位的解释方式。加法和减法与无符号二进制完全相同，只有有符号和无符号之间的结果解释不同。（例如，当符号位进位而没有从符号位借出时发生有符号溢出。）

此外，进位从LSB到MSB（从右到左）传播。减法也是一样的：无论高位是否有借位，低位都会借位。如果这导致溢出或进位，则仅会影响高位。例如：

 0x801F
-0x9123
-------
 0xeefc

低 8 位（0xFC）不依赖于它们所借用的值。它们会“环绕”并将借位传递给高 8 位。

因此，加法和减法具有这样的属性：结果的低位不依赖于操作数的任何高位。

由于 LEA 只使用加法（和左移），因此默认地址大小始终是可以的。延迟截断直到操作数大小对结果产生影响时才进行截断也总是没问题的。

（例外情况：16 位代码可以使用地址大小前缀进行 32 位数学运算。在 32 位或 64 位代码中，地址大小前缀会减小宽度而不是增加。）

---

乘法可以看作是重复的加法，或者是移位和加法。低半部分不受任何上位位的影响。在这个 4 位示例中，我写出了所有被累加到低 2 结果位中的位积。只涉及到每个源的低 2 位。很明显，这通常有效：部分积在加法之前进行移位，因此源中的高位从未影响结果中的低位。

请参阅 维基百科 上更详细解释的更大版本。有很多关于 binary signed multiplication 的好的 谷歌结果，包括一些教材。

    *Warning*: This diagram is probably slightly bogus.


       ABCD   A has a place value of -2^3 = -8
     * abcd   a has a place value of -2^3 = -8
     ------
   RRRRrrrr

   AAAAABCD * d  sign-extended partial products
 + AAAABCD  * c
 + AAABCD   * b
 - AABCD    * a  (a * A = +2^6, since the negatives cancel)
  ----------
          D*d
         ^
         C*d+D*c

---

使用带符号的乘法而不是无符号乘法在低半部分（此示例中为低4位）仍会得到相同的结果。 部分积的符号扩展只会发生在结果的上半部分。

这种解释可能不够详细（甚至可能有错误），但有很好的证据表明它在生产代码中使用是正确且安全的。

• gcc使用imul来计算两个unsigned long输入的unsigned long乘积。在Godbolt编译器浏览器上查看gcc利用LEA优化其他函数的示例。

• 英特尔指令参考手册中说：

两个和三个操作数的形式也可以用于无符号操作数，因为乘积的低半部分是相同的，无论操作数是有符号还是无符号。然而，CF和OF标志不能用于确定结果的高半部分是否为非零。

英特尔设计决定仅引入2个和3个操作数形式的imul，而不是mul。

显然，按位二进制逻辑操作（and/or/xor/not）独立地处理每个位：位位置的结果仅取决于该位位置上输入值。位移也很明显。

- Peter Cordes