Page 203 - ARM 64 Bit Assembly Language

Integer mathematics 191

a ← 0
while y = 0 do
if LSB(y) = 1 then
a ← a + x
end if
x ← x shifted left 1 bit
y ← y shifted right 1 bit
end while

Algorithm 1: Algorithm for binary multiplication.

Example 14. Equivalent multiplication in decimal and binary.

01100101
101 × 01011001
× 89 01100101
909 = 01100101
808 01100101
8989 01100101
0010001100011101

Binary multiplication can be implemented as a sequence of shift and add instructions. Given
two registers, x and y,and an accumulator register a, the product of x and y can be computed
using Algorithm 1. When applying the algorithm, it is important to remember that, in the gen-
eral case, the result of multiplying an n bit number by an m bit number is (at most) an n + m
bit number. For instance 11 2 × 11 2 = 1001 2 . Therefore, when applying Algorithm 1, it is nec-
essary to know the number of bits in x and y.Since x is shifted left on each iteration of the
loop, the registers used to store x and a must both be at least as large as the number of bits in
x plus the number of bits in y.
To multiply two n bit numbers, you must be able to add two 2n bit numbers. Adding 128 bit
numbers requires two add instructions and the carry from the least-significant 64 bits must
be added to the sum of the most-significant 64 bits. AArch64 provides a convenient way to
perform the add with carry. Assume we have two 128 bit numbers, x and y.Wehave x in x0,
x1 and y in x2, x3, where the high order words of each number are in the higher-numbered
registers, and we want to calculate x = x + y. Listing 7.1 shows a two instruction sequence
for an AArch64 processor. The first instruction adds the two least-significant words together
and sets (or clears) the carry bit and other flags in the PSTATE register. The second instruction