Advanced Arithmetic
Chapter 8
Extended-Precision Addition
As you can see, the idea is to break a larger operation into a sequence of smaller ones. Since the x86 processor family is capable of adding together at most 64 bits at a time (using general-purpose registers), the operation must proceed in blocks of 64 bits or fewer. Here are the steps:
; example in MASM
.data
X oword ?
Y oword ?
.code
mov rax, qword ptr X ; Add together the LO 64 bits
add rax, qword ptr Y ; of the numbers and store the
mov qword ptr Z, rax ; result into the LO qword of Z
mov rax, qword ptr X[8] ; Add together (with carry) the
adc rax, qword ptr Y[8] ; HO 64 bits and store the result
mov qword ptr Z[8], rax ; into the HO qword of ZRemember, X, Y, and Z are oword objects (128 bits), and an instruction of the form mov rax, X would attempt to load a 128-bit value into a 64-bit register. To load a 64-bit value, specifically the LO 64 bits, the qword ptr operator coerces symbols X, Y, and Z to 64 bits. To load the HO qwords, you use address expressions of the form X[8], along with the qword ptr operator, because the x86 memory space addresses bytes, and it takes 8 consecutive bytes to form a quad word.
Extended-Precision Subtraction
Just as it does addition, the x86-64 performs multi-byte subtraction the same way you would manually, except it subtracts whole bytes, words, double words, or quad words at a time rather than decimal digits.
You use the sub instruction on the LO byte, word, double word, or quad word and the sbb (subtract with borrow) instruction on the high-order values.
; Example of extended-precision Subtraction
;
; 256-bit subtraction
.data
BigVal1 qword 4 dup (?)
BigVal2 qword 4 dup (?)
BigVal3 qword 4 dup (?)
.
.
.
; Compute BigVal3 := BigVal1 - BigVal2.
; Note: don't need to coerce types of BigVa1, BigVal2, or BigVal3
; because their base types are already qword.
mov rax, BigVal1[0]
sub rax, BigVal2[0]
mov BigVal3[0], rax
mov rax, BigVal1[8]
sbb rax, BigVal2[8]
mov BigVal3[8], rax
mov rax, BigVal1[16]
sbb rax, BigVal2[16]
mov BigVal3[16], rax
mov rax, BigVal1[24]
sbb rax, BigVal2[24]
mov BigVal3[24], raxExtended-Precision Comparisions
You need to look at both bytes of a pair of values only if the HO bytes are equal. In all other cases, comparing the HO bytes tells you everything you need to know about the values. This is true for any number of bytes, not just two. The following code compares two signed 128-bit integers by comparing their HO quad words first and comparing their LO quad words only if the HO quad words are equal:
; This sequence transfers control to location "IsGreater" if
; QwordValue > QwordValue2. It transfers control to "IsLess" if
; QwordValue < QwordValue2. It falls through to the instruction
; following this sequence if QwordValue = QwordValue2.
; To test for inequality, change the "IsGreater" and "IsLess"
; operands to "NotEqual" in this code.
mov rax, qword ptr QWordValue[8] ; Get HO qword
cmp rax, qword ptr QWordValue2[8]
jg IsGreater
jl IsLess;
mov rax, qword ptr QWordValue[0] ; If HO qwords equal,
cmp rax, qword ptr QWordValue2[0] ; then we must compare
jg IsGreater; ; the LO dwords
jl IsLess;
; Fall through to this point if the two values were equal.To compare unsigned values, use the ja and jb instructions in place of jg and jl.
To generalize the preceding code for objects larger than 128 bits, start the comparison with the objects’ HO quad words and work your way down to their LO quad words, as long as the corresponding double words are equal.
; comparing two 256-bit values
.data
Big1 qword 4 dup (?)
Big2 qword 4 dup (?)
.
.
.
mov rax, Big1[24]
cmp rax, Big2[24]
jb isLE
ja notLE
mov rax, Big1[16]
cmp rax, Big2[16]
jb isLE
ja notLE
mov rax, Big1[8]
cmp rax, Big2[8]
jb isLE
ja notLE
mov rax, Big1[0]
cmp rax, Big2[0]
jnbe notLE
isLE:
Code to execute if Big1 <= Big2
.
.
.
notLE:
Code to execute if Big1 > Big2Extended-Precision Multiplication
The x86-64 does extended-precision multiplication in the same manner except that it works with bytes, words, double words, and quad words rather than digits.
Probably the most important thing to remember when performing an extended-precision multiplication is that you must also perform an extended-precision addition at the same time. Adding up all the partial products requires several additions.
Below code demonstrates how to multiply two 64-bit values (producing a 128-bit result) by using 32-bit instructions. Technically, you can do a 64-bit multiplication with a single instruction, but this example demonstrates a method you can easily extend to 128 bits by using the x86-64 64-bit registers rather than the 32-bit registers.
; 128-bit multiplication
option casemap:none
nl = 10
.const
fmtStr1 byte "%d * %d = %I64d (verify:%I64d)", nl, 0
.data
op1 qword 123456789
op2 qword 234567890
product oword ?
product2 oword ?
.code
externdef printf:proc
; mul64-
;
; Multiplies two 64-bit values passed in rdx and rax by
; doing a 64x64-bit multiplication, producing a 128-bit result.
; Algorithm is easily extended to 128x128 bits by switching the
; 32-bit registers for 64-bit registers.
;
; Stores result to location pointed at by R8.
mul64 proc
mp equ <dword ptr [rbp-8]> ;Multiplier
mc equ <dword ptr [rbp-16]> ;Multiplicand
prd equ <dword ptr [r8]> ;Result
push rbp
mov rbp, rsp
sub rsp, 24
push rbx ;Preserve these register values
push rcx
; Save parameters passed in registers:
mov qword ptr mp, rax
mov qword ptr mc, rdx
; Multiply the LO dword of Multiplier times Multiplicand.
mov eax, mp
mul mc ; Multiply LO dwords.
mov prd, eax ; Save LO dword of product.
mov ecx, edx ; Save HO dword of partial product result.
mov eax, mp
mul mc[4] ; Multiply mp(LO) * mc(HO)
add eax, ecx ; Add to the partial product.
adc edx, 0 ; Don't forget the carry!
mov ebx, eax ; Save partial product for now.
mov ecx, edx
; Multiply the HO word of Multiplier with Multiplicand.
mov eax, mp[4] ; Get HO dword of Multiplier.
mul mc ; Multiply by LO word of Multiplicand.
add eax, ebx ; Add to the partial product.
mov prd[4], eax ; Save the partial product.
adc ecx, edx ; Add in the carry!
mov eax, mp[4] ; Multiply the two HO dwords together.
mul mc[4]
add eax, ecx ; Add in partial product.
adc edx, 0 ; Don't forget the carry!
mov prd[8], eax ;Save HO qword of result
mov prd[12], edx
; EDX:EAX contains 64-bit result at this point
pop rcx ; Restore these registers
pop rbx
leave
ret
mul64 endp
; Here is the "asmMain" function.
public asmMain
asmMain proc
push rbp
mov rbp, rsp
sub rsp, 64 ;Shadow storage
; Test the mul64 function:
mov rax, op1
mov rdx, op2
lea r8, product
call mul64
; Use a 64-bit multiply to test the result
mov rax, op1
mov rdx, op2
imul rax, rdx
mov qword ptr product2, rax
; Print the results:
lea rcx, fmtStr1
mov rdx, op1
mov r8, op2
mov r9, qword ptr product
mov rax, qword ptr product2
mov [rsp+32], rax
call printf
leave
ret ;Returns to caller
asmMain endp
endThe code works only for unsigned operands. To multiply two signed values, you must note the signs of the operands before the multiplication, take the absolute value of the two operands, do an unsigned multiplication, and then adjust the sign of the resulting product based on the signs of the original operands.
Extended-Precision Division
The general algorithm is as follows:
Move the HO quad word of the dividend into RAX and zero-extend it into RDX.
Divide by the divisor.
Store the value in RAX into the corresponding qword position of the quotient result variable (position of the dividend qword loaded into RAX prior to the division).
Load RAX with the next-lower quad word in the dividend, without modifying RDX.
Repeat steps 2 to 4 until you’ve processed all the quad words in the dividend.
; 256-bit by 64-bit division
option casemap:none
nl = 10
.const
fmtStr1 byte "quotient = "
byte "%08x_%08x_%08x_%08x_%08x_%08x_%08x_%08x"
byte nl, 0
fmtStr2 byte "remainder = %I64x", nl, 0
.data
; op1 is a 256-bit value. Initial values were chosen
; to make it easy to verify result.
op1 oword 2222eeeeccccaaaa8888666644440000h
oword 2222eeeeccccaaaa8888666644440000h
op2 qword 2
result oword 2 dup (0) ;Also 256 bits
remain qword 0
.code
externdef printf:proc
; div256-
; Divides a 256-bit number by a 64-bit number.
;
; Dividend - passed by reference in RCX.
; Divisor - passed in RDX.
;
; Quotient - passed by reference in R8.
; Remainder- passed by reference in R9.
div256 proc
divisor equ <qword ptr [rbp-8]>
dividend equ <qword ptr [rcx]>
quotient equ <qword ptr [r8]>
remainder equ <qword ptr [r9]>
push rbp
mov rbp, rsp
sub rsp, 8
mov divisor, rdx
mov rax, dividend[24] ; Begin div with HO qword
xor rdx, rdx ; Zero extend into RDS
div divisor ; Divide HO word
mov quotient[24], rax ; Save HO result
mov rax, dividend[16] ; Get dividend qword #2
div divisor ; Continue with division
mov quotient[16], rax ; Store away qword #2
mov rax, dividend[8] ; Get dividend qword #1
div divisor ; Continue with division
mov quotient[8], rax ; Store away qword #1
mov rax, dividend[0] ; Get LO dividend qword
div divisor ; Continue with division
mov quotient[0], rax ; Store away LO qword
mov remainder, rdx ; Save away remainder
leave
ret
div256 endp
; Here is the "asmMain" function.
public asmMain
asmMain proc
push rbp
mov rbp, rsp
sub rsp, 80 ;Shadow storage
; Test the div256 function:
lea rcx, op1
mov rdx, op2
lea r8, result
lea r9, remain
call div256
; Print the results:
lea rcx, fmtStr1
mov edx, dword ptr result[28]
mov r8d, dword ptr result[24]
mov r9d, dword ptr result[20]
mov eax, dword ptr result[16]
mov [rsp+32], rax
mov eax, dword ptr result[12]
mov [rsp+40], rax
mov eax, dword ptr result[8]
mov [rsp+48], rax
mov eax, dword ptr result[4]
mov [rsp+56], rax
mov eax, dword ptr result[0]
mov [rsp+64], rax
call printf
lea rcx, fmtStr2
mov rdx, remain
call printf
leave
ret ;Returns to caller
asmMain endp
endGeneric N-bit by M-bit Division
To use a divisor larger than 64 bits, you have to implement the division by using a shift-and-subtract strategy, which works but is very slow.
But this method is even easier in binary.
Example of it's implementation in in MASM.
; 128-bit by 128-bit division
option casemap:none
nl = 10
.const
fmtStr1 byte "quotient = "
byte "%08x_%08x_%08x_%08x"
byte nl, 0
fmtStr2 byte "remainder = "
byte "%08x_%08x_%08x_%08x"
byte nl, 0
fmtStr3 byte "quotient (2) = "
byte "%08x_%08x_%08x_%08x"
byte nl, 0
.data
; op1 is a 128-bit value. Initial values were chosen
; to make it easy to verify result.
op1 oword 2222eeeeccccaaaa8888666644440000h
op2 oword 2
op3 oword 11117777666655554444333322220000h
result oword ?
remain oword ?
.code
externdef printf:proc
; div128-
;
; This procedure does a general 128/128 division operation
; using the following algorithm (all variables are assumed
; to be 128-bit objects):
;
; Quotient := Dividend;
; Remainder := 0;
; for i := 1 to NumberBits do
;
; Remainder:Quotient := Remainder:Quotient SHL 1;
; if Remainder >= Divisor then
;
; Remainder := Remainder - Divisor;
; Quotient := Quotient + 1;
;
; endif
; endfor
;
; Data passed:
;
; 128-bit dividend, by reference in RCX
; 128-bit divisor, by reference in RDX
;
; Data returned:
;
; Pointer to 128-bit quotient in R8
; Pointer to 128-bit remainder in R9
div128 proc
remainder equ <[rbp-16]>
dividend equ <[rbp-32]>
quotient equ <[rbp-32]> ;Aliased to dividend
divisor equ <[rbp-48]>
push rbp
mov rbp, rsp
sub rsp, 48
push rax
push rcx
xor rax, rax ;Initialize remainder to 0
mov remainder, rax
mov remainder[8], rax
; Copy the dividend to local storage
mov rax, [rcx]
mov dividend, rax
mov rax, [rcx+8]
mov dividend[8], rax
; Copy the divisor to local storage
mov rax, [rdx]
mov divisor, rax
mov rax, [rdx+8]
mov divisor[8], rax
mov cl, 128 ;Count off bits in cl
; Compute Remainder:Quotient := Remainder:Quotient SHL 1:
repeatLp: shl qword ptr dividend[0], 1 ;256-bit extended
rcl qword ptr dividend[8], 1 ; precision shift
rcl qword ptr remainder[0], 1 ; through remainder
rcl qword ptr remainder[8], 1
; Do a 128-bit comparison to see if the remainder
; is greater than or equal to the divisor.
mov rax, remainder[8]
cmp rax, divisor[8]
ja isGE
jb notGE
mov rax, remainder
cmp rax, divisor
ja isGE
jb notGE
; Remainder := Remainder - Divisor
isGE: mov rax, divisor
sub remainder, rax
mov rax, divisor[8]
sbb remainder[8], rax
; Quotient := Quotient + 1;
add qword ptr quotient, 1
adc qword ptr quotient[8], 0
notGE: dec cl
jnz repeatLp
; Okay, copy the quotient (left in the Dividend variable)
; and the remainder to their return locations.
mov rax, quotient[0]
mov [r8], rax
mov rax, quotient[8]
mov [r8][8], rax
mov rax, remainder[0]
mov [r9], rax
mov rax, remainder[8]
mov [r9][8], rax
pop rcx
pop rax
leave
ret
div128 endp
; Here is the "asmMain" function.
public asmMain
asmMain proc
push rbp
mov rbp, rsp
sub rsp, 64 ;Shadow storage
; Test the div128 function:
lea rcx, op1
lea rdx, op2
lea r8, result
lea r9, remain
call div128
; Print the results:
lea rcx, fmtStr1
mov edx, dword ptr result[12]
mov r8d, dword ptr result[8]
mov r9d, dword ptr result[4]
mov eax, dword ptr result[0]
mov [rsp+32], rax
call printf
lea rcx, fmtStr2
mov edx, dword ptr remain[12]
mov r8d, dword ptr remain[8]
mov r9d, dword ptr remain[4]
mov eax, dword ptr remain[0]
mov [rsp+32], rax
call printf
; Test the div128 function:
lea rcx, op1
lea rdx, op3
lea r8, result
lea r9, remain
call div128
; Print the results:
lea rcx, fmtStr3
mov edx, dword ptr result[12]
mov r8d, dword ptr result[8]
mov r9d, dword ptr result[4]
mov eax, dword ptr result[0]
mov [rsp+32], rax
call printf
lea rcx, fmtStr2
mov edx, dword ptr remain[12]
mov r8d, dword ptr remain[8]
mov r9d, dword ptr remain[4]
mov eax, dword ptr remain[0]
mov [rsp+32], rax
call printf
leave
ret ;Returns to caller
asmMain endp
endTo handle division by 0, check the divisor against 0 prior to running this code and return an appropriate error code if the divisor is 0. Dealing with signed values is the same as the earlier division algorithm: note the signs, take the operands’ absolute values, do the unsigned division, and then fix the sign afterward.
You can use the following technique to boost the performance of this division by a fair amount. Check to see if the divisor variable uses only 32 bits. Often, even though the divisor is a 128-bit variable, the value itself fits into 32 bits (that is, the HO double words of Divisor are 0) and you can use the div instruction, which is much faster. The improved algorithm is a bit more complex because you have to first compare the HO quad words for 0, but on average, it runs much faster while remaining capable of dividing any two pairs of values.
Extended-Precision Negation Operations
The neg instruction doesn’t provide a generic extended-precision form. However, a negation is equivalent to subtracting a value from 0, so we can easily simulate an extended-precision negation by using the sub and sbb instructions.
The following code provides a simple way to negate a (320-bit) value by subtracting that value from 0, using an extended-precision subtraction:
.data
Value qword 5 dup (?) ; 320-bit value
.
.
.
xor rax, rax ; RAX = 0
sub rax, Value
mov Value, rax
mov eax, 0 ; Cannot use XOR here:
sbb rax , Value[8] ; must preserve carry!
mov Value[8], rax
mov eax, 0 ; Zero-extends!
sbb rax, Value[16]
mov Value[16], rax
mov eax, 0
sbb rax, Value[24]
mov Value[24], rax
mov rax, 0
sbb rax, Value[32]
mov Value[32], raxA slightly more efficient way to negate smaller values (128 bits) uses a combination of neg and sbb instructions. This technique uses the fact that neg subtracts its operand from 0. In particular, it sets the flags the same way the sub instruction would if you subtracted the destination value from 0. This code takes the following form (assuming you want to negate the 128-bit value in RDX:RAX):
neg rdx
neg rax
sbb rdx, 0Extended-Precision AND Operations
Performing an n-byte AND operation is easy: simply AND the corresponding bytes between the two operands, saving the result.
; 128-bit AND Operation
mov rax, qword ptr source1
and rax, qword ptr source2
mov qword ptr dest, rax
mov rax, qword ptr source1[8]
and rax, qword ptr source2[8]
mov qword ptr dest[8], raxTo extend this technique to any number of qwords, logically AND the corresponding bytes, words, double words, or quad words together in the operands.
This sequence sets the flags according to the value of the last and operation. If you AND the HO quad words last, this sets all but the zero flag correctly. If you need to test the zero flag after this sequence, logically OR the two resulting double words together (or otherwise compare them both against 0).
You can also use the XMM and YMM registers to perform extended-precision logical operations (up to 256 bits at a time).
Extended-Precision OR Operations
Multi-byte logical OR operations are performed in the same way as multibyte AND operations. You OR the corresponding bytes in the two operands together.
; 192-bit OR Operation
mov rax, qword ptr source1
or rax, qword ptr source2
mov qword ptr dest, rax
mov rax, qword ptr source1[8]
or rax, qword ptr source2[8]
mov qword ptr dest[8], rax
mov rax, qword ptr source1[16]
or rax, qword ptr source2[16]
mov qword ptr dest[16], raxAs in the previous example, this does not set the zero flag properly for the entire operation. If you need to test the zero flag after an extended-precision OR, you must logically OR all the resulting double words together.
Extended-Precision XOR Operations
As with other logical operations, extended-precision XOR operations exclusive-ORs the corresponding bytes in the two operands to obtain the extended-precision result.
; 64-bit XOR Operation
mov rax, qword ptr source1
xor rax, qword ptr source2
mov qword ptr dest, rax
mov rax, qword ptr source1[8]
xor rax, qword ptr source2[8]
mov qword ptr dest[8], raxThe comment about the zero flag in the previous two sections, as well as the comment about the XMM and YMM registers, apply here.
Extended-Precision Shift Operations
Extended-Precision Shift Left
To accomplish this with machine instructions, we must first shift the LO qword to the left (for example, using the shl instruction) and capture the output from bit 63 (conveniently, the carry flag does this for us). We must then shift this bit into the LO bit of the HO qword while simultaneously shifting all the other bits to the left.
For example, to shift the 128-bit quantity in RDX:RAX one position to the left
shl rax, 1
rcl rdx, 1To perform a shift left on an operand larger than 128 bits, use additional rcl instructions. An extended-precision shift-left operation always starts with the least-significant quad word, and each succeeding rcl instruction operates on the next-most-significant double word.
; 192-bit shift left operation
shl qword ptr Operand[0], 1
rcl qword ptr Operand[8], 1
rcl qword ptr Operand[16], 1If you need to shift your data by 2 or more bits, you can place the instructions in a loop to repeat them a certain number of times.
ShiftLoop:
shl qword ptr Operand[0], 1
rcl qword ptr Operand[8], 1
rcl qword ptr Operand[16], 1
dec cl
jnz ShiftLoopExtended-Precision Shift Right and Shift Arithmetic Right
You implement shr (shift right) and sar (shift arithmetic right) in a similar way, except you must start at the HO word of the operand and work your way down to the LO word:
; Extended-precision SAR:
sar qword ptr Operand[16], 1
rcr qword ptr Operand[8], 1
rcr qword ptr Operand[0], 1
; Extended-precision SHR:
shr qword ptr Operand[16], 1
rcr qword ptr Operand[8], 1
rcr qword ptr Operand[0], 1Efficient Multi-bit Extended-Precision Shifts
The shld and shrd instructions let you efficiently implement extended-precision shifts of several bits.
shld Operand1, Operand2, constant
shld Operand1, Operand2, cl
shrd Operand1, Operand2, constant
shrd Operand1, Operand2, cl
.data
ShiftMe qword 012345678h, 90123456h, 78901234h
.
.
.
mov rax, ShiftMe[8]
shld ShiftMe[16], rax, 6
mov rax, ShiftMe[0]
shld ShiftMe[8], rax, 6
shl ShiftMe[0], 6The first shld instruction shifts the bits from ShiftMe[8] into ShiftMe[16] without affecting the value in ShiftMe[8]. The second shld instruction shifts the bits from ShiftMe into ShiftMe[8]. Finally, the shl instruction shifts the LO double word the appropriate amount.
Extended-Precision Rotate Operations
The rcl and rcr operations extend in a manner similar to shl and shr. For example, to perform 192-bit rcl and rcr operations, use the following instructions:
rcl qword ptr Operand[0], 1
rcl qword ptr Operand[8], 1
rcl qword ptr Operand[16], 1
rcr qword ptr Operand[16], 1
rcr qword ptr Operand[8], 1
rcr qword ptr Operand[0], 1Performing an extended-precision rol or ror operation isn’t quite as simple because of the way the incoming bit is processed. You can use the bt, shld, and shrd instructions to implement an extended-precision rol or ror instruction.
; Compute (128-bit) rol RDX:RAX, 4:
mov rbx, rdx
shld rdx, rax, 4
shld rax, rbx, 4
bt rbx, 28 ; Set carry flag, if desiredOperating on Different-Size Operands
Occasionally, you may need to do a computation on a pair of operands that are not the same size. For example, you may need to add a word and a double word together or subtract a byte value from a word value.
To do so, extend the smaller operand to the size of the larger operand and then operate on two same-size operands. For signed operands, you sign-extend the smaller operand to the same size as the larger operand; for unsigned values, you zero-extend the smaller operand. This works for any operation.
Last updated