将两个UInt32相乘以获得不扩展的UInt64

Question

对于我的BigIntegers,在PUREPASCAL实现中(即不允许汇编程序),我必须乘以2 UInt32才能得到UInt64结果.

通常的方法是扩展至少一个操作数,所以你得到一个64位乘法:

Res := UInt64(A) * B;

这里Res是UInt64和A和B的UInt32.

但是,在Win32中,这会产生一个相当笨重的机器代码:

MulTest.dpr.431: Res := UInt64(A) * B;
004DB463 8B45F8           mov eax,[ebp-$08]  // load A 
004DB466 33D2             xor edx,edx        // make it UInt64
004DB468 52               push edx           // push A
004DB469 50               push eax
004DB46A 8B45FC           mov eax,[ebp-$04]  // load B
004DB46D 33D2             xor edx,edx        // make it UInt64 
004DB46F E87C0AF3FF       call @_llmul       // 64 bit multiplication
004DB474 8945E8           mov [ebp-$18],eax  // store 64 bit result
004DB477 8955EC           mov [ebp-$14],edx

现在,如果你这样做:

Res := A * B;

不幸的是,你得到一个32位的中间结果(实际结果的前32位简单地归零):

MulTest.dpr.435: Res := A * B;
004DB4BD 8B45FC           mov eax,[ebp-$04]
004DB4C0 F76DF8           imul dword ptr [ebp-$08]
004DB4C3 33D2             xor edx,edx              // zero out top 32 bits
004DB4C5 8945E8           mov [ebp-$18],eax
004DB4C8 8955EC           mov [ebp-$14],edx

现在,如果线路xor edx,edx不在那里,结果将正是我所需要的.这将是使用UInt64演员表的加宽版本的两倍多(即花费不到一半的时间).

问:有没有人知道是否有伪功能或技巧或演员表没有丢弃64位结果的前32位？我知道如何在汇编程序中执行此操作,但这必须是PUREPASCAL(它也应该在其他平台上工作).

通过访问32位未分配整数数组,我成功地在PUREPASCAL中进行了32位加法,这些整数组成了一个BigInteger作为无符号16位整数数组并添加了这些整数.所以我也尝试使用16位中间结果进行乘法运算:

// Too slow: in a test, 2973 ms for Mul32(A, B) vs 1432 ms for UInt64(A) * B.
function MulU32ToU64(L, R: UInt32): UInt64; inline;
var
  L0R0, L0R1, L1R0, L1R1, Sum: UInt32;
type
  TUInt64 = packed record
    case Byte of
      0: (L0, L1, L2, L3: UInt16);
      1: (I0, I1: UInt32);
  end;
  TUInt32 = packed record
    Lo, Hi: Word;
  end;
begin
  L0R0 := TUInt32(L).Lo * TUInt32(R).Lo;
  L0R1 := TUInt32(L).Lo * TUInt32(R).Hi;
  L1R0 := TUInt32(L).Hi * TUInt32(R).Lo;
  L1R1 := TUInt32(L).Hi * TUInt32(R).Hi;
  TUInt64(Result).L0 := TUInt32(L0R0).Lo;
  Sum := UInt32(TUInt32(L0R0).Hi) + TUInt32(L1R0).Lo + TUInt32(L0R1).Lo;
  TUInt64(Result).L1 := TUInt32(Sum).Lo;
  Sum := UInt32(TUInt32(Sum).Hi) + TUInt32(L1R0).Hi + TUInt32(L0R1).Hi + L1R1;
  TUInt64(Result).I1 := Sum;
end;

它给了我正确的结果,但比两倍更慢的UInt64(A) * B.这并不奇怪,因为它进行了4次UInt32乘法和大量添加,这使得它比使用的代码慢System.__llmul.

更新

正如@J ...指出的那样,Delphi通常使用IMUL,它有一个带符号的乘法.所以,例如$00000002和$FFFFFFFF结果的乘法EAX = $FFFFFFFE和EDX = $FFFFFFFF(换句话说,一个Int64有值-2),而我需要EAX = $FFFFFFFE(相同),但EDX = $00000001(UInt64与值一起$00000001FFFFFFFE).因此,排除前32位是正确的,似乎没有办法强制Delphi使用MUL并保留结果的前32位.

Answer 1

MulTest.dpr.435: Res := A * B;
004DB4BD 8B45FC           mov eax,[ebp-$04]
004DB4C0 F76DF8           imul dword ptr [ebp-$08]
004DB4C3 33D2             xor edx,edx              // zero out top 32 bits
004DB4C5 8945E8           mov [ebp-$18],eax
004DB4C8 8955EC           mov [ebp-$14],edx

现在,如果xor edx,edx不在那里,那么结果将正是我所需要的.

不,这根本不是你想要的.这是一个有符号的乘法,如果你想要一个无符号的结果,结果是无意义的.制作A:=$FFFFFFFF和B:=2- 结果imul是EAX = FFFFFFFE和EDX = FFFFFFFF.即使使用两个无符号操作数,也会发出此操作码.你想要的是mul指令,而不是imul.我不认为delphi编译器会mul从纯粹的pascal中发出.从文件上*(强调我的)

无论x和y的类型如何,x/y的值都是Extended类型.对于其他算术运算符,只要至少一个操作数是实数,结果就是Extended类型; 否则,当至少一个操作数是Int64类型时,结果是Int64类型; 否则,结果是Integer类型.

整数 - 签名.鉴于这对于架构的特性有多依赖,并且考虑到delphi编译器的不足,我认为这里唯一的高性能解决方案将是依赖于目标的汇编.

function UMul3264(x, y : UInt32) : UInt64;
asm
  mul eax, edx
end;