C unsigned long long和imulq
作为一个刚接触组装的人,我使用gcc进行逆向工程。 但是现在我遇到了一个有趣的问题:我尝试将两个64位整数乘以x86-64。 C代码如下:
unsigned long long val(unsigned long long a, unsigned long long b){ return a*b; }
并使用gcc编译:
val: movq %rdi, %rax imulq %rsi, %rax ret
将有符号乘法用于无符号整数可能违反直觉,但它适用于C.
但是,我想检查溢出的乘法。 现在,如果结果大于2^63-1
则设置溢出标志(我猜是因为它毕竟是带符号的乘法)。 但是对于无符号64位,只要结果不大于2^64-1
这仍然可以。
在这种情况下,进行乘法(在assembly中)的正确方法是什么?
当乘以两个值时,无论是无符号乘法还是有符号乘法,结果的最低有效位都完全相同。 因此,如果将两个32位值相乘,则得到64位结果,其中低32位是相同的,无论乘法是有符号还是无符号。 对于64位乘法也是如此,它产生128位结果,其中低64位在两种情况下都是相同的。
因此,编译器经常使用IMUL
指令(其助记符建议有符号乘法)用于两种类型的乘法,因为它比MUL
更灵活,并且通常更快。 MUL
只有一种forms(允许任意通用寄存器或存储器位置乘以隐含的目标寄存器AL / AX / EAX / RAX),而IMUL
有多种forms,包括单操作数forms(与MUL
相同) ),一个双操作数forms(寄存器或存储器×寄存器或存储器或立即数),以及三操作数forms(寄存器或存储器×立即数,将结果存储在第三个目标寄存器中)。 更多详细信息可在英特尔的文档中找到(请参阅x86标签wiki以获取链接),或快速参考MUL和IMUL 。
编译器可以一直使用IMUL
的原因是因为你丢弃了结果的高位。 当您执行32位×32位乘法并将结果存储在32位变量中时,将丢弃整个64位结果的高32位。 同样,对于64位×64位乘法也是如此,它丢弃了128位结果的高64位,只留下低64位,无论是有符号还是无符号乘法都是相同的。
引自英特尔手册:
[IMUL]的两个和三个操作数forms也可以与无符号操作数一起使用,因为无论操作数是有符号还是无符号,产品的下半部分都是相同的。 但是,CF和OF标志不能用于确定结果的上半部分是否为非零。
彼得·科德斯(Peter Cordes)在他关于二进制补码算术运算的一个非常普遍的问题的较大答案的一部分中也对此进行了很好的解释。
无论如何,在自己编写汇编代码时,您必须决定是否要执行编译器所做的相同操作并丢弃产品的高位,或者是否要保留它们。 如果您不关心高位并假设操作不会溢出,请编写与编译器相同的代码。
如果你关心高位,只需使用MUL
指令,如果乘法的乘积大于其操作数的类型,则设置CF和OF标志。
mov rax, QWORD PTR [a] ; put 64-bit operand 'a' into RAX mov rbx, QWORD PTR [b] ; put 64-bit operand 'b' into RBX mul rbx ; multiply 'a' * 'b' ; 128-bit result is returned in RDX:RAX (upper-bits:lower-bits) jo ProductOverflowed
在这里使用MUL
几乎肯定比尝试找到一种方法来使用IMUL
并在之后测试高64位以查看它们是否为非零(这表示溢出)更有效。 简单地拥有一个不可预测的分支会让你在性能方面落后,相比之下,使用IMUL
可以节省1或2μs。
看起来你不能在没有一堆额外代码的情况下使用imul
,因为CF和OF都设置相同。 正如本手册的“操作”部分所述,如果完整的128b结果与sign_extend(low_half_result)
不匹配,则设置它们。 所以你是对的,即使是imul
的多操作数forms仍然有一些签名的行为。 如果它们像add
/ sub
和set OF和CF一样独立会很好,所以你可以查看CF表示无符号数据或OF表示签名数据。
找到一个好的asm序列的最好方法之一是询问编译器。 C没有方便的整数溢出检测, 但Rust确实如此 。
我编译了这个函数来返回值和unsigned-wraparound检测bool。 显然,Rust的ABI将它们作为一个隐藏的第一个arg传递给它们,而不是像rdx:rax那样,我认为C ABI会用于这样一个小结构。 🙁
pub fn overflowing_mul(a: u64, b: u64) -> (u64, bool) { a.overflowing_mul(b) }
# frame-pointer boilerplate elided mov rax, rsi mul rdx mov qword ptr [rdi], rax seto byte ptr [rdi + 8] mov rax, rdi # return the pointer to the return-value ret
Asm输出来自Godbolt编译器资源管理器(Rust 1.7.0) 。 这或多或少地证实了mov
指令和单操作数完全乘法的额外imul
比在双操作数imul
之后用额外检查做的任何事情都更有效。
mul
的文档说
“如果结果的上半部分为0,则OF和CF标志设置为0;否则,它们设置为1。”
总而言之, 使用mul
并检查OF
或CF
以查看高半部分是否为非零。
mul
vs. imul
trivia:
只有全乘(N x N => 2N)结果的上半部分在imul
和mul
之间不同。 我认为英特尔选择imul
作为具有多个显式操作数的那个
imul r32, r32, sign-extended-imm8
会更有意义,因为符号扩展可能比零扩展更有用。
我只是意识到imul
的标志结果只是签名的。 有趣的一点。
为什么gcc不使用
mul
进行无符号乘法?
因为单操作数mul
/ imul
较慢(根据Agner Fog的insn表 ,在Intel CPU上为2 imul
而不是1。另请参阅x86标签wiki)。 它们还使用了更多的寄存器:它们需要在rax
使用其中一个输入,并在rdx:rax
生成它们的输出,因此通常需要额外的mov
指令来将数据移入/移出这些寄存器。
因此,如果你不关心标志结果, imul r64, r64
是比mul r64
更好的选择。
在Intel CPUs imul r64,r64
实际上比mul r32
更快。 在其他一些CPU上并非如此,包括AMD Bulldozer系列,其中64位乘法有些慢。 但是,由于mul r32
将其结果放入edx:eax
而不是仅仅一个目标寄存器,因此在大多数情况下它们不是直接替换它们。