Подтвердить что ты не робот

Умножение двух UInt32 на получение UInt64 без расширения

Для моих BigIntegers, в реализации PUREPASCAL (т.е. не на ассемблере не допускается), я должен умножить два 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.

Вопрос: Кто-нибудь знает, существует ли псевдофункция, трюк или приведение, которые не отбрасывают старшие 32 бита 64-битного результата? Я знаю, как это сделать на ассемблере, но это должен быть PUREPASCAL (он должен работать и на других платформах).

Я уже пытался использовать 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 и сохранить MUL 32 бита результата этого.

4b9b3361

ОТВЕТЫ

Ответ 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 из чистого паскаля. Из документация на * (выделение мое)

Значение x/y имеет тип Extended, независимо от типов x и y. Для других арифметических операторов результат имеет тип Extended, когда хотя бы один операнд является реальным; в противном случае результат будет иметь тип Int64, если хотя бы один операнд имеет тип Int64; в противном случае результат имеет тип Integer.

Целое число - подписано. Учитывая, насколько зависимо это от особенностей архитектуры, и учитывая недостатки компиляторов delphi, я думаю, что единственное решение для исполнителей здесь будет целевой сборкой.

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