## Section14.5Multiplication

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.

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 the N and Z 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. The as 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 the N and Z 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 the N and Z 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.