implementation of c=a*b using ONLY inc dec and jnz commands

Question

I've got a very complicated question in a 'new' primitive assembly in one of my interviews (why the hell QA requires an assembly knowledge when they told me their QA's tests based on Python... ?), and it's goes like this:

Assume your assembly language includes ONLY the following instructions:

• 'inc REG': increments a given register by one.
• 'dec REG': decrement a given register by one.
• 'jnz LABEL': jumps to a given LABEL if the previous instruction's result was not zero.
• 'HELT': stops running.

Task: A and B registers hold non-negative values. The program should calculate the value of A*B and locate the result in C. In addition, the language holds registers C,D,...,Z, which you can assume are initialized at program start to zero.

There are few points here that required more attention, like that you have to take in advance that A and\or B values may be zero.. and multiple by zero is... zero.. this is damn tough..

P.S. Because of that question I didn't make it to reach the implementation of the 'my_atoi()' 's question.. :-(

Thanks !

Answer 1

I'm not going to give the full answer, but the key here is that you have to define a mov routine yourself. Assuming dec X where X holds 0 produces a negative (or very large) number, that can be done as:

MOV_AD:     ; copy value in A to D, using E as scratch space
    inc A   ; must be non-zero for jnz to work below
COPYLOOP:
    inc D
    inc E
    dec A
    jnz COPYLOOP
    dec D   ; undo the first inc A in D

            ; E now contains the initial value of A + 1
MOVBACK:    ; move value in E back to A
    inc A
    dec E
    jnz MOVBACK
    dec A   ; undo the first inc A

WIPE_E:     ; wipe the scratch space
    dec E
    jnz WIPE_E

Once you have the appropriate mov routines, you can implement addition as repeated increment and multiplication as repeated addition. In both, you'll need the inc trick to get jnz to work, and in the multiplication routine, you'll need to end with a subtraction.

Answer 2

Breaking this down step by step:

Original:

C = A * B

Is equivalent to:

C = 0
while A != 0:
   dec A
   C += B

Is equivalent to:

C = 0
while A != 0:
   dec A
   # Note: Following block of code changes B but sets it back to
   #       original value when done
   Z = 0
   while B != 0:
       dec B
       inc Z
       inc C
   B = Z

Is equivalent to:

C = 0
Z = 0
while A != 0:
   dec A
   # Note: Following block of code changes B but sets it back to
   #       original value when done
   while B != 0:
       dec B
       inc Z
       inc C
   while Z != 0:
       dec Z
       inc B

Now we just need to figure out how to translate this construct:

while LOOP_VAR != 0:
    dec LOOP_VAR
    ... some code here which does not use LOOP_VAR ...

That can be translated to:

    # Next 4 lines do "if LOOP_VAR == 0: goto loop_end"
    inc LOOP_VAR
    dec LOOP_VAR  # To set flags
    jnz loop_again
    goto loop_end
loop_again:
    ... some code here which does not use LOOP_VAR ...
    dec LOOP_VAR
    jnz loop_again
loop_end:

And of course, we need to translate that unconditional goto into a conditional one. Fortunately we have lots of variables that are known to be zero, so we can test if one of them is zero:

    # Unconditional jump to "loop_end".  Note that Q is always zero.
    inc Q
    dec Q
    jnz loop_end

So, putting that all together:

    # Next 3 lines do "if A != 0: goto outer_loop_again"
    inc A
    dec A  # To set flags
    jnz outer_loop_again

    # Unconditional jump to "outer_loop_end".  Note that Q is always zero.
    inc Q
    dec Q
    jnz outer_loop_end

outer_loop_again:

    # Next 3 lines do "if B != 0: goto addition_loop_again"
    inc B
    dec B  # To set flags
    jnz addition_loop_again

    # Unconditional jump to "addition_loop_end".  Note that Q is always zero.
    inc Q
    dec Q
    jnz addition_loop_end

addition_loop_again:
    inc Z
    inc C
    dec B
    jnz addition_loop_again
addition_loop_end:

    # Next 3 lines do "if Z != 0: goto move_loop_again"
    inc Z
    dec Z  # To set flags
    jnz move_loop_again

    # Unconditional jump to "move_loop_end".  Note that Q is always zero.
    inc Q
    dec Q
    jnz move_loop_end

move_loop_again:
    inc B
    dec Z
    jnz move_loop_again
move_loop_end:

    dec A
    jnz outer_loop_again
outer_loop_end:

    # Finished!
    helt

Edited to add: Actually, there's a slightly simpler way. We can check if A or B are zero at the start, which simplifies it to:

    # Check if A is zero, and halt if so
    # (So that multiplying by zero gives zero)
    inc A
    dec A  # To set flags
    jnz a_non_zero
    helt  # Multiplying by zero gives zero
a_non_zero:

    # Check if B is zero, and halt if so
    # (So that multiplying by zero gives zero)
    inc B
    dec B  # To set flags
    jnz b_non_zero
    helt  # Multiplying by zero gives zero
b_non_zero:

outer_loop_again:

addition_loop_again:
    inc Z
    inc C
    dec B
    jnz addition_loop_again

move_loop_again:
    inc B
    dec Z
    jnz move_loop_again

    dec A
    jnz outer_loop_again

    # Finished!
    helt