Section 14.5 Multiplication
The hexToInt
function discussed in Section 14.3 shows how to convert a string of hexadecimal characters into the integer they represent. That function uses the fact that each hexadecimal character represents four bits. So as the characters are read from left to right, the bits in the accumulator are shifted four places to the left in order to make space for the next four-bit value. The character is converted to the four bits it represents and added to the accumulator.
Although the four-bit left shift seems natural for hexadecimal, it is equivalent to multiplying the value in the accumulator by sixteen. This follows from the positional notation used to write numbers. Add another hexadecimal digit to the right of an existing number effectively multiplies that existing number by sixteen. A little thought shows that this algorithm, shown in Algorithm 14.5.1, works in any number base.
Algorithm 14.5.1. Character to Integer Conversion.
\(\displaystyle accumulator = 0\)
-
While more characters
\(\displaystyle accumulator = base \times accumulator\)
\(temp = \)integer equivalent of character
\(\displaystyle accumulator = accumulator + temp\)
Of course, you probably want to write programs that allow users to work with decimal numbers. So we need to know how to convert a string of decimal characters to the integer they represent. The characters that represent decimal numbers are in the range \(\hex{30}_{16}\)–\(\hex{39}_{16}\text{,}\) so the conversion of a single decimal numeral to the integer it represents is simply:
temp = character & 0xf
Multiplication by ten can be performed by shifting and adding, but using a multiply instruction is more straightforward. Multiplication is somewhat more complicated than addition. The main problem is that the product can, in general, occupy the number of digits in the multiplier plus the number of digits in the multiplicand. This is easily seen by computing \(99 \times 99 = 9801\) (in decimal). Thus in general,
There are three simple multiply instructions, mul
, smull
, and umull
. The one you use depends on the size of the numbers, and for large numbers, their sign.
MUL
-
Multiplies two 32-bit values and produces a 32-bit result.
MUL{S}{<c>} <Rd>, <Rn>{, <Rm>}
If ‘
S
’ is present theN
andZ
condition flags are updated according to the result, but the other condition flags are not changed. If absent, the condition flags are not changed.<c>
is the condition code, Table 9.2.1.<Rd>
specifies the destination register, and<Rm>
and<Rn>
are the source registers.
The values in the two source operand registers are multiplied and the low-order 32 bits of the result are stored in
<Rd>
. If<Rm>
is not present,<Rd>
is used as the second source operand. Theas
assembler prefers that<Rm>
be used. The 32-bit result does not depend on whether the source operands are considered signed or not. SMULL
-
Multiplies two signed 32-bit values and produces a 64-bit result.
SMULL{S}{<c>} <RdLo>, <RdHi>, <Rn>, <Rm>
If ‘
S
’ is present theN
andZ
condition flags are updated according to the result, but the other condition flags are not changed. If absent, the condition flags are not changed.<c>
is the condition code, Table 9.2.1.<RdHi>
specifies the high-order 32-bit destination register,<RdLo>
the low-order 32-bit destination register, and<Rm>
and<Rn>
are the source registers.
The values in the two source operand registers are multiplied, the high-order 32 bits of the result are stored in
<RdHi>
, and the low-order 32 bits of the result are stored in<RdLo>
.<Rm>
and<Rn>
are treated as holding signed values. UMULL
-
Multiplies two unsigned 32-bit values and produces a 64-bit result.
UMULL{S}{<c>} <RdLo>, <RdHi>, <Rn>, <Rm>
If ‘
S
’ is present theN
andZ
condition flags are updated according to the result, but the other condition flags are not changed. If absent, the condition flags are not changed.<c>
is the condition code, Table 9.2.1.<RdHi>
specifies the high-order 32-bit destination register,<RdLo>
the low-order 32-bit destination register, and<Rm>
and<Rn>
are the source registers.
The values in the two source operand registers are multiplied, the high-order 32 bits of the result are stored in
<RdHi>
, and the low-order 32 bits of the result are stored in<RdLo>
.<Rm>
and<Rn>
are treated as holding unsigned values.
If you are certain that the result of your multiplication will be within the range \(-2,147,483,648 \leq x \leq +2,147,483,647\) for signed integers or \(x \leq 4,294,967,295\) for unsigned, then you can use the mull
instruction. Otherwise, you must use the smull
or umull
instruction, respectively. Notice that the carry and overflow condition flags are not affected by the multiplication instructions.
The algorithm to convert a text string that represents an unsigned decimal integer to an unsigned int
is very similar to the hexadecimal conversion in Exercise 14.4.3. The only difference is to use mul
to multiply by \(10\) instead of shifting left four bit positions to multiply by \(16\text{.}\) The function in Listing 14.5.2 shows how to do this.
Notice that I copied the value in the accumulator register to a temporary register before performing the multiplication:
mov r0, r5 @ mul wants 2nd source reg mul r5, r0, r7 @ accumulator X 10
Although using only r5
worked for me, the as
assembler gave a message saying that it is better to use two source registers. I suspect this has to do with the instruction execution pipeline used in the CPU, but that discussion is beyond the scope of this book. See books like Computer Organization and Design, Third Edition[13], Computer Organization & Architecture: Designing for Performance[14], and Structured Computer Organization, Fifth Edition[16] for a discussion of pipelines.
Before learning how to convert an int
to its corresponding decimal text string, we need to learn how to divide. Division is described in Section 14.6.