Multiply two 8 bit number that gives 16bit number as result, with 8bit register and only add instruction

Question

I'm new with assembly coding, I'm trying to learn for university purpose. We are using ATmel Studio to simulate ATmega structure, and we will work with ATmega328 instruction set. I have this exercise where I have to multiply two 8bit number (which are 0b00111010 and 0b01010101) with only add instruction (or even adc, no matter which one). I'm struggling a lot because my professor didn't give any paper, just the instruction set manual of the ATmega238, so I'm lost.

Please help me I'm getting crazy.

Following my chat-gpt helped code that doesn't work properly, it does only half of the task, because it correctly calculate only the LSB of the result, the MSB is wrong. I think the problem is in the line "adc r19, r1" but I don't know how to resolve it.

; Input r16 (00111010), r17 (01010101)
; Output r18:r19 (risultato)

    ldi r16, 0b00111010   ; Load first number in r16
    ldi r17, 0b01010101   ; Load second number in r17

    ldi r18, 0            ; Initialize LSB's resoult to 0
    ldi r19, 0            ; Initialize MSB's resoult to 0

    ldi r20, 8            ; 8 bit counter

multiply_loop:
    lsr r17               ; Shift to dx the first number
    brcc no_add           ; Skip if the LSB is 0

    add r18, r16          ; Add first number to the lower part of the resoult
    adc r19, r1           ; Add carry to the higher part of the resoult

no_add:
    lsl r16               ; Left shift of first number

    dec r20               ; Decrease counter
    brne multiply_loop    ; Repeat cycle until counter is 0

    ; Final resoult in r18:r19

Answer 1

First you need to understand what you are doing.

ldi r16, 0b00111010 ; Load first number in r16 ldi r17, 0b01010101 ; Load second number in r17

You can use R17 as a position adder, while R16 will be the value to be add to the pair R18, R19. Lets say R18 is the high order byte.

You do the multiply as you do with pen and paper, every bit "1" of R17 will require an addition of R16 to R19:R18, but R16 will be shifted to represent the position of the bit "1" in the R17. As you can see, the first shift left of R16 you will lose the left bit to carry, so you really need two bytes to hold R16, since it will be shifted left 8 times. Lets use R15 and it will start with zero.

So, R17 will tell you when to add, R15:R16 will be the value to add to R18:R19.

Bit 0 (right) of R17 is "1", it means you need to add the bare R15:R16 to R18:R19. Bit 1 of R17 is "0" you don't add anything, but shift left R15:R16 left 1 bit. Bit 2 of R17 is "1" R15:R16 adds to R18:R19, shift R15:R16 left 1 bit. Bit 3 of R17 is "0" add nothing, shift R15:R16 left 1 bit. Bit 4 of R17 is "1" R16:R16 adds to R18:R19, shift R15:R16 left 1 bit. and so on until Bit 7 of R17 is "0" add nothing, result on R18:R19.

In assembly, using better registers:

   ldi r16, 0b00111010   ; Load first number in r16 (LSB value to add)
   clr r17               ; the MSB of pair R17:R16 (value to add) 

   ldi r18, 0b01010101   ; Load second number in r18 (multiplier)

   clr r1               ; Initialize MSB's result to 0
   clr r0               ; Initialize LSB's result to 0

   ldi r20, 8            ; 8 bit counter

multiply_loop: 

   lsr r18               ; Shift to carry the first number
   brcc no_add           ; Skip if the LSB is 0 (even number)

   add r0, r16          ; Add LSBs first 
   adc r1, r17          ; Add MSBs and carry to result MSB

no_add: 

   lsl r16               ; left shift 16 bits of pair R17:R16
   rol r17               ; carry from lsl above into R17 bit 0

   dec r20               ; Decrease counter
   brne multiply_loop    ; Repeat cycle until counter is 0

; Final result in r1:r0

Answer 2

You need a 16-bit left shift (perhaps add r16,r16 / adc r15,r15) instead of just lsl r16. Then you'll have an upper half of that input to use with adc into the upper half of the product, with adc r19, r15.

Zero R15 first, or whatever register you can spare as a temporary.

In math terms this is zero-extending R16 into R15:R16 to match the width of the product, and so you can left-shift it without losing bits shifted out the top. The partial products you're adding to the result are 16-bit.
This is how you get big 16-bit numbers for the product of two big 8-bit numbers. (e.g. 0xff * 0x80 is a left-shift by 7, giving 0x7f80. 0xff * 0xff is 0xfe01 = 0xff00 - 0xff.)

Related in general for AVR multiplication:

• Faster 16bit multiplication algorithm for 8-bit MCU has some C that describes in higher-level terms what should be going on (using uint16_t in C which takes multiple AVR instructions to operate on.)

• tinyAVR: best known multiplication routines for 8-bit and 16-bit factors? (including table-lookup tricks for 4 bits at a time.)

• http://www.avr-asm-tutorial.net/avr_en/calc/HARDMULT.html - All ATmega chips have a hardware mul instruction that produces a 16-bit result in R1:R0. So this bit-at-a-time loop is only useful as a learning exercise, or for lower-end AVR CPUs than yours.

• http://www.avr-asm-tutorial.net/avr_en/calc/index.html That site also has a tutorial on multiplying in general, including some about the math I think, to help you understand what the code is doing.

BTW, don't waste your time with ChatGPT for assembly language, it's terrible at it, making nonsense code like yours that reads r1 without having loaded any value into it.

Answer 3

The simple approach would be to treat multiplication as successive addition:

    LDI R16, 0b00111010   ; Load first number in r16
    LDI R17, 0b01010101   ; Load second number in r17
    
    CLR R18               ; Initialize LSB's result to 0
    CLR R19               ; Initialize MSB's result to 0
    CLR R20               ; Initialize Auxiliary register 

    RJMP DONE-2

ACCUMULATE:
    ADD R18, R16
    ADC R19, R20
    DEC R17
    BRCC ACCUMULATE
DONE:
    ; Final resoult in r18:r19

Note that this will not work for signed integers, for that it will be necessary to modify the code to account for situations when the result is expected to be negative.