最近,我试着写一个程序来计算(a * b)%m,其中(0 <= a,b,m <= 2 ^ 63-1)。而且,幸运的是,我知道GCC支持__int128_t
。所以我最终得到了以下程序。
#include <stdint.h>
int64_t multimod(int64_t a, int64_t b, int64_t m)
{
__int128_t ab = (__int128_t)a * b;
ab %= m;
return ab;
}
但我想在没有__int128_t
的情况下做到这一点,以便既挑战自己又使这个功能更有效率。我决定首先模拟这个函数的汇编程序的过程。所以我使用了objdump
并获得了multimod
的以下部分。
int64_t multimod(int64_t a, int64_t b, int64_t m)
{
720: 55 push %rbp
721: 49 89 d1 mov %rdx,%r9
724: 49 89 f8 mov %rdi,%r8
727: 49 c1 f8 3f sar $0x3f,%r8
72b: 48 89 f0 mov %rsi,%rax
72e: 48 c1 f8 3f sar $0x3f,%rax
732: 4c 89 c2 mov %r8,%rdx
735: 48 0f af d6 imul %rsi,%rdx
739: 48 0f af c7 imul %rdi,%rax
73d: 49 89 c0 mov %rax,%r8
740: 49 01 d0 add %rdx,%r8
743: 48 89 f8 mov %rdi,%rax
746: 48 f7 e6 mul %rsi
749: 48 89 c7 mov %rax,%rdi
74c: 49 8d 34 10 lea (%r8,%rdx,1),%rsi
750: 4c 89 c9 mov %r9,%rcx
753: 48 c1 f9 3f sar $0x3f,%rcx
757: 4c 89 ca mov %r9,%rdx
75a: e8 61 00 00 00 callq 7c0 <__modti3>
75f: 5d pop %rbp
760: c3 retq
我分析了整个部分并相信它可以分为两部分--- 1.获得64位变量a
和b
2.__modti3
的正确128位乘积。
我STFW并且知道__modti3
的原型是long long __modti3(long long a, long long b)
。但汇编代码并没有这样做。当它调用__modti3
时,第一个参数%rdi
包含a
和b
的低64位乘积,第二个参数%rsi
包含a
和b
的高位64位产品,第三个参数%rdx
包含m
。那么__modti3
做了什么才能得到正确答案?
不,long long
是64位。你可以看到gcc在rdi,rsi,rdx和rcx中传递__modti3 args。 (即x86-64 SysV ABI中的前4个arg传递槽。)
所以这是两个128位操作数,通过regs对的值传递:rsi:rdi
和rcx:rdx
。
它实际上是__int128 __modti3(__int128 quotient, __int128 divisor);
这是存在的全部观点和原因:x86-64在硬件中具有long long % long long
余数
idiv r64
,gcc将用于运行时变量除数/模数。
请注意,您的函数是从m
将rdx
符号扩展到rcx:rdx
中
mov %r9, %rcx # originally from RDX on entry; you didn't enable full optimization
sar $63, %rcx # copy sign bit to all bit positions.
这与cqo
(AT&T cqto
)将RAX签名扩展为RDX:RAX的方式完全相同。
顺便说一句,如果使用-O3
启用完全优化,代码更容易阅读。然后,您只能获得1个乘法指令,使用64位输入并产生128位输出。 https://gcc.godbolt.org/z/0gKc5d
如果你想让asm看起来更像源代码,那么使用-O1
或-Og
进行编译有时会更有帮助,但由于C没有扩展乘法运算符,所以实际上并不需要它。您希望编译器在乘以加宽乘法之前优化加宽输入,而不是将输入符号扩展为寄存器对并执行128x128 => 128位乘法。 (这是您展示的代码中发生的情况。)