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

Question

I have a very difficult question in the “new” primitive assembly in one of my interviews (why the hellish QA requires assembly knowledge when they told me about their Python-based QA tests ...?), And it looks like this:

Suppose your assembler language includes ONLY the following instructions:

• 'inc REG' : increments this register by one.
• 'dec REG' : reduce case by one.
• 'jnz LABEL' : jumps to the given STAGE if the previous command result is not equal to zero.
• 'HELT' : stops working.

Task: Registers A and B contain non-negative values. The program should calculate the value of A * B and find the result in C. In addition, the language registers C, D, ..., Z, which you can assume, are initialized when the program starts to zero.

There are a few points that need more attention, so you need to assume in advance that the values ​​of A and \ or B can be zero .. and a multiple of zero is zero ... it's damn complicated ..

PS Because of this question, I did not reach the implementation of the question "my_atoi ()": - (

Thanks!

Answer 1

I will not give a complete answer, but the key here is that you need to define the mov procedure yourself. Assuming dec X , where X has a value of 0, a negative (or very large) number is obtained, which can be performed 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 the addition as a repeated increment and multiplication, as a repeated addition. In both cases, you will need the inc trick to get jnz to work, and in the multiplication procedure you need to finish the subtraction.

Answer 2

Abort this step by step:

Original:

 C = A * B 

It is equivalent to:

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

It 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 

It 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 ... 

This can be translated into:

  # 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 this unconditional transition into a conditional one. Fortunately, we have many variables that are known to be equal to zero, so we can check whether one of them is equal to zero:

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

So, 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 is a slightly easier way. We can check if A or B are zeros at the beginning, which simplifies it:

  # 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 

Answer 3

The JNZ command can be seen as a do .. while structure, an example with @ user9876 .

 @_loop1: ; do { ; do { INC Z ; z++; INC C ; c++; DEC B ; b--; JNZ _loop1 ; } while (b != 0); ; @_loop2: ; do { INC B ; b++; DEC Z ; z--; JNZ _loop2 ; while (z != 0); ; DEC A ; a--; JNZ _loop1 ; } while (a != 0);