// Source file: MulDiv64.cpp
// Author: Richard van der Wal
// Contact: [email]R.vdWal@xs4all.nl[/email]
//
// Description: Implementation for MulDiv64 and MulShr64
//
// $Log: $
// Multiplies an operant by a multiplier and divides the result by a divider
// Used for scaling 64 bit integer values
// Xscaled = Xstart * Multiplier / Divider
// Uses 128 bit intermediate result
Function MulDiv64(Operant, Multiplier, Divider: Int64): Int64;
StdCall;
Type TVar128 =
Array[0..3]
of LongWord;
Var Remainder, Quotient: TVar128;
CombinedSign: LongWord;
Begin
// Save combined sign
CombinedSign := Int64Rec(Operant).Hi
xor Int64Rec(Multiplier).Hi
xor Int64Rec(Divider).Hi;
// Take absolute values because algorithm is for unsigned only
If Operant < 0
Then Operant := -Operant;
If Multiplier < 0
Then Multiplier := -Multiplier;
If Divider < 0
Then Divider := -Divider;
ASM
// First check Divider for 0
MOV EAX, DWORD PTR [&Divider+4]
OR EAX, DWORD PTR [&Divider+0]
JNZ @DividerOK
DIV EAX
@DividerOK:
LEA EDI, [&Quotient]
// EDI := @Quotient
// Check multiplier for 1 or 0
XOR EAX, EAX
CMP EAX, DWORD PTR [&Multiplier+4]
JNZ @StartMUL
CMP EAX, DWORD PTR [&Multiplier+0]
JNZ @MultiNotNUL
XOR EDX, EDX
JMP @Done
@MultiNotNUL:
// Set result HI part to 0
XOR EAX, EAX
MOV DWORD PTR [EDI+12], EAX
MOV DWORD PTR [EDI+ 8], EAX
MOV EAX, 1
CMP EAX, DWORD PTR [&Multiplier+0]
JNZ @SmallMUL
// Multiplier is 1 so just copy operant to result
MOV EAX, DWORD PTR [&Operant+4]
MOV DWORD PTR [EDI+4], EAX
MOV EAX, DWORD PTR [&Operant+0]
MOV DWORD PTR [EDI+0], EAX
JMP @StartDIV
@SmallMUL:
// Test for 32/32 bit multiplication
XOR EAX, EAX
MOV ECX, DWORD PTR [&Operant+4]
OR ECX, EAX
// test for both hiwords zero.
JNZ @StartMUL
// Do 32/32 bit multiplication
MOV ECX, DWORD PTR [&Multiplier+0]
MOV EAX, DWORD PTR [&Operant+0]
MUL ECX
MOV DWORD PTR [EDI+4], EDX
MOV DWORD PTR [EDI+0], EAX
JMP @StartDIV
@StartMUL:
// Check signs
// Multiply: Quotient = operant * multiplier
MOV EAX, DWORD PTR [&Multiplier+0]
// EAX = LO(multiplier)
MUL DWORD PTR [&Operant+0]
// EDX:EAX = EAX * LO(operant)
MOV DWORD PTR [EDI+0], EAX
// Quotient[0] = EAX
MOV ECX, EDX
// ECX = EDX
MOV EAX, DWORD PTR [&Multiplier+0]
// EAX = LO(multiplier)
MUL DWORD PTR [&Operant+4]
// EDX:EAX = EAX * HI(operant)
ADD EAX, ECX
// EAX = EAX + ECX
ADC EDX, 0
// EDX = EDX + 0 + carry
MOV EBX, EAX
MOV ECX, EDX
MOV EAX, DWORD PTR [&Multiplier+4]
MUL DWORD PTR [&Operant+0]
ADD EAX, EBX
MOV DWORD PTR [EDI+4], EAX
ADC ECX, EDX
pushfd
MOV EAX, DWORD PTR [&Multiplier+4]
MUL DWORD PTR [&Operant+4]
popfd
ADC EAX, ECX
ADC EDX, 0
MOV DWORD PTR [EDI+ 8], EAX
MOV DWORD PTR [EDI+12], EDX
@StartDIV:
// Divide: Quotient = Quotient / Divider
//
// Test Divider = 32bit value
MOV EAX, DWORD PTR [&Divider+4]
CMP EAX, 0
JNZ @FullDIV
MOV ECX, DWORD PTR [&Divider+0]
CMP ECX, 1
JZ @ApplySign
// Start 128/32 bit division
MOV EAX, DWORD PTR [EDI+12]
XOR EDX, EDX
DIV ECX
MOV DWORD PTR [EDI+12], EAX
MOV EAX, DWORD PTR [EDI+8]
DIV ECX
MOV DWORD PTR [EDI+8], EAX
MOV EAX, DWORD PTR [EDI+4]
DIV ECX
MOV DWORD PTR [EDI+4], EAX
MOV EAX, DWORD PTR [EDI+0]
DIV ECX
MOV DWORD PTR [EDI+0], EAX
// Copy the Quotient to the result storage
MOV EAX, DWORD PTR [EDI+12]
MOV DWORD PTR [EDI+12], EAX
MOV EAX, DWORD PTR [EDI+ 8]
MOV DWORD PTR [EDI+ 8], EAX
MOV EAX, DWORD PTR [EDI+ 4]
MOV DWORD PTR [EDI+ 4], EAX
MOV EAX, DWORD PTR [EDI+ 0]
MOV DWORD PTR [EDI+ 0], EAX
// To sign correction and return
JMP @ApplySign
@FullDIV:
// Full 128/64 bit division
XOR EAX, EAX
MOV DWORD PTR [&Remainder+12], EAX
MOV DWORD PTR [&Remainder+ 8], EAX
MOV DWORD PTR [&Remainder+ 4], EAX
MOV DWORD PTR [&Remainder+ 0], EAX
MOV ECX, 128
@Loop1:
// Compute Remainder:Quotient = Remainder:QUOTIENT shl 1
SHL DWORD PTR [EDI+ 0], 1
RCL DWORD PTR [EDI+ 4], 1
RCL DWORD PTR [EDI+ 8], 1
RCL DWORD PTR [EDI+12], 1
RCL DWORD PTR [&Remainder+ 0], 1
RCL DWORD PTR [&Remainder+ 4], 1
RCL DWORD PTR [&Remainder+ 8], 1
RCL DWORD PTR [&Remainder+12], 1
// Test (Remainder >= Divider)
XOR EAX, EAX
CMP DWORD PTR [&Remainder+12], EAX
JA @IfTrue
JB @IfFalse
CMP DWORD PTR [&Remainder+ 8], EAX
JA @IfTrue
JB @IfFalse
MOV EAX, DWORD PTR [&Remainder+ 4]
CMP EAX, DWORD PTR [&Divider+4]
JA @IfTrue
JB @IfFalse
MOV EAX, DWORD PTR [&Remainder+ 0]
CMP EAX, DWORD PTR [&Divider+0]
JB @IfFalse
@IfTrue:
// Remainder = Remainder - Divider
MOV EAX, DWORD PTR [&Divider+0]
SUB DWORD PTR [&Remainder+ 0], EAX
MOV EAX, DWORD PTR [&Divider+4]
SBB DWORD PTR [&Remainder+ 4], EAX
XOR EAX, EAX
SBB DWORD PTR [&Remainder+ 8], EAX
SBB DWORD PTR [&Remainder+12], EAX
// Quotient = Quotient +1
ADD DWORD PTR [EDI+ 0], 1
ADC DWORD PTR [EDI+ 4], 0
ADC DWORD PTR [EDI+ 8], 0
ADC DWORD PTR [EDI+12], 0
@IfFalse:
// Loop size = 101 bytes, is less than 127 so loop is possible
LOOP @Loop1
@ApplySign:
// Correct the sign of the result based on the stored combined sign
JNS @StoreRes
NOT DWORD PTR [EDI+12]
NOT DWORD PTR [EDI+ 8]
NOT DWORD PTR [EDI+ 4]
NOT DWORD PTR [EDI+ 0]
ADD DWORD PTR [EDI+ 0], 1
ADC DWORD PTR [EDI+ 4], 0
ADC DWORD PTR [EDI+ 8], 0
ADC DWORD PTR [EDI+12], 0
@StoreRes:
// Get low order qword from Quotient
MOV EDX, DWORD PTR [EDI+4]
MOV DWORD PTR [&Result+4], EAX
MOV EAX, DWORD PTR [EDI+0]
MOV DWORD PTR [&Result+0], EAX
@Done:
End;
End;