Skip to main content

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.

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.

@ uDecToInt.s
@ Converts a decimal text string to an unsigned int.
@ Calling sequence:
@       r0 <- address of string
@       bl uDecToInt
@ returns equivalent int
@ 2017-09-29: Bob Plantz

@ Define my Raspberry Pi
        .cpu    cortex-a53
        .fpu    neon-fp-armv8
        .syntax unified         @ modern syntax

@ Constant for assembler
        .equ    no_ascii,0xf
        .equ    NUL,0

@ The program
        .text
        .align  2
        .global uDecToInt
        .type   uDecToInt, %function
uDecToInt:
        sub     sp, sp, 24      @ space for saving regs
        str     r4, [sp, 0]     @ save r4
        str     r5, [sp, 4]     @      r5
        str     r6, [sp, 8]     @      r6
        str     r7, [sp, 12]    @      r7
        str     fp, [sp, 16]    @      fp
        str     lr, [sp, 20]    @      lr
        add     fp, sp, 20      @ set our frame pointer
        
        mov     r4, r0          @ string pointer
        mov     r5, 0           @ accumulator = 0;
        mov     r7, 10          @ decimal constant
loop:
        ldrb    r6, [r4]        @ get char
        cmp     r6, NUL         @ end of string?
        beq     allDone         @ yes
        mov     r0, r5          @ mul wants 2nd source reg
        mul     r5, r0, r7      @ accumulator X 10
        and     r6, r6, no_ascii  @ strip off acsii
        add     r5, r5, r6      @ add in the new value
        add     r4, r4, 1       @ next char
        b       loop
allDone:        
        mov     r0, r5          @ return accumulator;
        ldr     r4, [sp, 0]     @ restore r4
        ldr     r5, [sp, 4]     @      r5
        ldr     r6, [sp, 8]     @      r6
        ldr     r7, [sp, 12]    @      r7
        ldr     fp, [sp, 16]    @      fp
        ldr     lr, [sp, 20]    @      lr
        add     sp, sp, 24      @      sp
        bx      lr              @ return
Listing 14.5.2. Function to convert an unsigned decimal text string to an integer. (prog asm)

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.