delphi - How do I implement an efficient 32 bit DivMod in 64 bit code

Question

I want to use a DivMod function that operates exclusively on 32 bit operands. The implementation in the RTL returns values in 16 bit variables. Its declaration is:

procedure DivMod(Dividend: Cardinal; Divisor: Word; var Result, Remainder: Word);

So, I cannot use that since my inputs may overflow the return values.

The naive Pascal implementation looks like this:

procedure DivMod(Dividend, Divisor: Cardinal; out Quotient, Remainder: Cardinal);
begin
  Quotient := Dividend div Divisor;
  Remainder := Dividend mod Divisor;
end;

This works splendidly but performs the division twice. Since the function is called by part of my code that is in a performance bottleneck, I would like to perform the division once only. To that end I am using Serg's 32 bit DivMod from this question: Is there a DivMod that is *not* Limited to Words (<=65535)?

procedure DivMod(Dividend, Divisor: Cardinal; out Quotient, Remainder: Cardinal);
asm
        PUSH EBX
        MOV  EBX,EDX
        XOR  EDX,EDX
        DIV  EBX
        MOV  [ECX],EAX
        MOV  EBX,Remainder
        MOV  [EBX],EDX
        POP  EBX
end;

This works perfectly.

But now I would like a version of the function for 64 bit code. Note that I still want to operate on 32 bit operands, and return 32 bit values.

Should I re-write the function using 64 bit assembler, or is it sufficient to use the DivMod overload from the RTL that operates on, and returns, 64 bit values?

Specifically I would like to know if there is a performance benefit in writing 64 bit code that does 32 bit operations. Is that even possible? Or would I simply end up re-implementing the DivMod overload with UInt64 parameters? If it is worth implementing a bespoke 64 bit asm version, how would I go about doing it, noting that the operands and operations are 32 bit.

I think that it would look like this, but I am no expert and likely have got something wrong:

procedure DivMod(Dividend, Divisor: Cardinal; out Quotient, Remainder: Cardinal);
asm
        MOV   EAX,ECX   // move Dividend to EAX
        MOV   ECX,EDX   // move Divisor to ECX
        XOR   EDX,EDX   // zeroise EDX
        DIV   ECX       // divide EDX:EAX by ECX
        MOV   [R8],EAX  // save quotient
        MOV   [R9],EDX  // save remainder
end;

Answer 1

For the special case of always dividing by 10 (per comments) you can do something like this :

procedure DivMod10(num : Cardinal; var q, r : Cardinal); inline;
var
  rl : uInt64;
begin
  rl := UInt64(3435973837)*num;
  q := rl shr 35;
  r := num - q*10;
end;

The algorithm varies depending on the denominator, but the source for determining it and the magic numbers can be found in libdivide. This is tested accurate for all unsigned 32-bit integers and is about 3 times faster than using div (and provides the remainder).

Benchmark (optimizations on):

  t0 := GetTickCount;
  for I := 1 to 999999999 do begin
    DivMod10(i, q, r);
  end;
  ShowMessage(IntToStr(GetTickCount - t0));  // result :  1809

  t0 := GetTickCount;
  for I := 1 to 999999999 do begin
    q := i div 10;
  end;
  ShowMessage(IntToStr(GetTickCount - t0));  // result :  5336

Test :

for I := 1 to High(Cardinal) do begin
  DivMod10(i,q,r);
  if q <> (i div 10) then WriteLn(IntToStr(i));
  // no mismatch found
end;