A2 - Branching

From VO-EM Wiki
Jump to: navigation, search

Our previous program was pretty boring! All our programs would be pretty boring if all we did was execute from top to bottom without ever changing our order of execution. Let's make something slightly more complex.

Overview

If you're familiar with other programming languages, you're probably familiar with if-statements, while loops, and the like. In the end, these statements have to be compiled down into assembly (well, machine code), which differs depending on the features of the CPU they're being compiled for.

Have you read the list of opcodes yet? Did you notice that there's no multiplication instruction? Lots of CPUs lack a multiplication instruction, and our implementation of DLX is one of them.

For this tutorial, we're going to make a program which can multiply positive integers.

Getting started

You're going to need everything you needed in the previous tutorial. Text editor, java runtime, flash player, dasm.jar.

Code

Since we don't have a "multiply", we have to do things the long way. Simply:

5x4 = 5+5+5+5 = 20

Obviously we could write this out as a long string of arithmetic instructions, but we want our program to be able to multiply any integer, so we need to be smarter than that.

Using a C-ish example

a = 5
b = 4
result = 0
while(b>0){
   result = result + a
   b = b-1
} 

If you're not familiar with c syntax, here it is in plain english:

0) Let a = 5 and b = 4. 
1) Let our result = 0. 
2) While b is greater than zero 
3)   Add a to our result
4)   subtract 1 from b

In other words, it will keep adding a to the result and subtracting 1 from b until it runs out of bs.

This is very easy to express in assembly! First, we'll set up our a and b pronumerals.

a     .word     5     ;let a = 5
b     .word     4     ;let b = 4

Does 'word' freak you out? Read about it here!

Next, we set up our registers.

         .start  main     ;start the program from the main label
main     lw      r1,a     ;load four bytes from address a into register 1 (it contains 5) 
         lw      r2,b     ;now load four bytes from b into register 2 (contains 4) 
         clr     r3       ;sets r3 to 0. This is where we'll store our result!

This is our first time using load instructions. They're needed for the CPU to get data from other devices in the computer.

clr r3 is just a short way of writing addi r3,r0,r0, or "add zero to zero and store the result in r3".

Now that that's set up, we make our multiplication loop:

loop     beqz    r2,end   ;go to label 'end' if r2 (b) is equal to zero
         add     r3,r3,r1 ;otherwise, add r1 to r3 and store the result back in r3
         subi    r2,r2,1  ;subtract 1 from r2 and store the result back in r2
         j       loop     ;go back to the loop label to see if we're done
end      halt             ;if we're done, stop executing

There are two new instructions here. j, or "jump", is very simple. It changes the value of PC, meaning the CPU will load a different instruction to what it was originally planning to next cycle. This lets us change the order in which our program executes.

The other new instruction is beqz, or "branch (if) equals zero". This works the same as j, but it only changes the value of PC if the register in its argument is equal to zero. We can use it to make if-statement-like control structures.

The code all in one place

a       .word   5        ;let a = 5
b       .word   4        ;let b = 4
        .start  main     ;start the program from the main label
main    lw      r1,a     ;load four bytes from address a into register 1 (it contains 5) 
        lw      r2,b     ;now load four bytes from b into register 2 (contains 4) 
        clr     r3       ;sets r3 to 0. This is where we'll store our result!
loop    beqz    r2,end   ;go to label 'end' if r2 (b) is equal to zero
        add     r3,r3,r1 ;otherwise, add r1 to r3 and store the result back in r3
        subi    r2,r2,1  ;subtract 1 from r2 and store the result back in r2
        j       loop     ;go back to the loop label to see if we're done
end     halt             ;if we're done, stop executing

Assembling and testing

Just like last time, save your source code as a .dls file. I've called mine multiply.dls.

You can then assemble it with dasm.

java -jar dasm.jar multiply.dls -a

Hint: try using -l to see where a and b are in memory.

Loading up the multiply.dlx executable in the debugger should put an answer in r3. Is it the right answer? If it looks wrong at first glance, be sure to remember that the debugger puts out hexidecimal values, so 14 in hex is actually 20 in decimal.

Stepping through your program with ||> should be considerably more interesting this time - you'll be able to see r2 counting down as r3 counts up.

Try changing the numbers around a bit to get a feel for how the program works, then head on to the next tutorial!

Challenge

This program works fine for positive integers, but how well does it handle negative numbers? You might find something strange if you put a negative number in b. Can you figure out why this happens and how to solve it?