How do I implement an efficient 32 bit DivMod in 64 bit code
assembly, delphi, x86-64
Solution
I dug a bit deeper. I think it would be perfectly reasonably to implement this on top of the `UInt64` version. That would look like this:
procedure DivMod(Dividend, Divisor: Cardinal; out Quotient, Remainder: Cardinal);
var
Quotient64, Remainder64: UInt64;
begin
DivMod(Dividend, Divisor, Quotient64, Remainder64);
Quotient := Quotient64;
Remainder := Remainder64;
end;
I don't think the performance would be very significantly affected in comparison to the most optimal asm version.
However, I believe that the x64 asm code in the question is correct. The `MOV` instructions are all fine with 32 bit operands. And the `DIV` is also as described in the comment in the asm code. The Intel documentation for `DIV r/m32` says:
Unsigned divide EDX:EAX by r/m32, with result stored in EAX ← Quotient, EDX ← Remainder.
And let's take a look at what the Delphi compiler does with this code:
var
a, b, c, d: Cardinal;
....
a := 666;
b := 42;
c := a div b;
d := a mod b;
The code that is produced is:
Project39.dpr.14: a := 666;
0000000000423A68 C7450C9A020000 mov [rbp+$0c],$0000029a
Project39.dpr.15: b := 42;
0000000000423A6F C745082A000000 mov [rbp+$08],$0000002a
Project39.dpr.16: c := a div b;
0000000000423A76 8B450C mov eax,[rbp+$0c]
0000000000423A79 33D2 xor edx,edx
0000000000423A7B F77508 div dword ptr [rbp+$08]
0000000000423A7E 894504 mov [rbp+$04],eax
Project39.dpr.17: d := a mod b;
0000000000423A81 8B450C mov eax,[rbp+$0c]
0000000000423A84 33D2 xor edx,edx
0000000000423A86 F77508 div dword ptr [rbp+$08]
0000000000423A89 895500 mov [rbp+$00],edx
I don't have any expectation that the 32 bit divide will be more efficient than a 64 bit divide, but that doesn't really matter. It seems more natural to perform the 32 bit operation with 32 bit operands.
Problem
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; ```