__modti3做什么?

问题描述 投票:1回答:1

最近,我试着写一个程序来计算(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位变量ab 2.__modti3的正确128位乘积。

我STFW并且知道__modti3的原型是long long __modti3(long long a, long long b)。但汇编代码并没有这样做。当它调用__modti3时,第一个参数%rdi包含ab的低64位乘积,第二个参数%rsi包含ab的高位64位产品,第三个参数%rdx包含m。那么__modti3做了什么才能得到正确答案?

c gcc assembly x86
1个回答
3
投票

不,long long是64位。你可以看到gcc在rdi,rsi,rdx和rcx中传递__modti3 args。 (即x86-64 SysV ABI中的前4个arg传递槽。)

所以这是两个128位操作数,通过regs对的值传递:rsi:rdircx:rdx

它实际上是__int128 __modti3(__int128 quotient, __int128 divisor);这是存在的全部观点和原因:x86-64在硬件中具有long long % long long余数 idiv r64,gcc将用于运行时变量除数/模数。


请注意,您的函数是从mrdx符号扩展到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位乘法。 (这是您展示的代码中发生的情况。)

© www.soinside.com 2019 - 2024. All rights reserved.