Assembly Implementation
Using lists:
In assembly, there are only 32 registers, most of which are not accessible. Therefore, it is not at all feasible to store list data in registers. That means the list must be stored in memory. The way to do this is assembly is to declare your list like this:
Array: 7, 5, 4, 1, 6, 8, 3, 2, 9, 0
Size: .word 10
You can then get an element of the array by doing:
lw $t0, Array($s4)
Where $s4 is 4 times the index that you want to access (because of the size of ints).
Similarly, we can store words by doing:
sw $t0, Array($s4)
In assembly, there are only 32 registers, most of which are not accessible. Therefore, it is not at all feasible to store list data in registers. That means the list must be stored in memory. The way to do this is assembly is to declare your list like this:
Array: 7, 5, 4, 1, 6, 8, 3, 2, 9, 0
Size: .word 10
You can then get an element of the array by doing:
lw $t0, Array($s4)
Where $s4 is 4 times the index that you want to access (because of the size of ints).
Similarly, we can store words by doing:
sw $t0, Array($s4)
Printing:
In many languages like C, printing out is fairly trivial. Not so in assembly. There is no easy way to print out exactly the thing you want to print. Instead, there is a fairly weird way to set up a system to print out what you want. It includes putting the thing you want to print in $a0 and the size of the thing in $v0, submitting a syscall command, like so:
lw $a0, Array($s2) # print next value from the list
li $v0, 1
syscall
In many languages like C, printing out is fairly trivial. Not so in assembly. There is no easy way to print out exactly the thing you want to print. Instead, there is a fairly weird way to set up a system to print out what you want. It includes putting the thing you want to print in $a0 and the size of the thing in $v0, submitting a syscall command, like so:
lw $a0, Array($s2) # print next value from the list
li $v0, 1
syscall
Writing the Code:
The two algorithms I implemented in assembly were bubble sort and quick sort. They both presented interesting challenges and I learned a lot about writing in assembly. I had the advantage of having written the C code for these first, which allowed me to much better understand the steps involved, without keeping it all in my head as just assembly code. Rather, I would take the C program line by line and translate it, keeping in mind the whole program and possible ramifications. Bubble sort was fairly easy to implement since it was just a double nested for loop. Quick sort was more challenging, but with some debugging, I was able to get it to run perfectly.
The two algorithms I implemented in assembly were bubble sort and quick sort. They both presented interesting challenges and I learned a lot about writing in assembly. I had the advantage of having written the C code for these first, which allowed me to much better understand the steps involved, without keeping it all in my head as just assembly code. Rather, I would take the C program line by line and translate it, keeping in mind the whole program and possible ramifications. Bubble sort was fairly easy to implement since it was just a double nested for loop. Quick sort was more challenging, but with some debugging, I was able to get it to run perfectly.
Code:
bubblesort.asm | |
File Size: | 2 kb |
File Type: | asm |
quicksort.asm | |
File Size: | 2 kb |
File Type: | asm |
Lessons Learned:
While writing these two programs, I learned a great deal of interesting lessons about how to effectively work in assembly and I though I would attempt to pass on some of the biggest lessons that I learned.
While writing these two programs, I learned a great deal of interesting lessons about how to effectively work in assembly and I though I would attempt to pass on some of the biggest lessons that I learned.
- Building in C first can make the experience much more manageable
- Testing the system part way through is always good practice and can prevent hard or even impossible debugging later on
- Just because assembly doesn't have for loops and if statements with curly brackets, doesn't mean indentation can't be a huge help in organizing and understanding your code
- Setting up a correlation between variables in your C program and registers in your assembly program can make the translation process much easier and faster.
Analysis:
One of the nice things about working in assembly is getting to actually see exactly how many base instructions a program takes to run. In mips assembly, I was able to run analysis on the two algorithms to see how many instructions they each took to sort to same exact list. The list is randomly generated set of 100 numbers.
One of the nice things about working in assembly is getting to actually see exactly how many base instructions a program takes to run. In mips assembly, I was able to run analysis on the two algorithms to see how many instructions they each took to sort to same exact list. The list is randomly generated set of 100 numbers.
It is easy to see that quick sort takes much less time to execute than bubble sort. As mentioned in the C page, the level of difference is a function of the size of the list. This differences is for only 100 numbers. The difference would be much greater for larger lists.