Originally posted in my portfolio.
Before you start making any false assumptions, no this post won't make you a machine language ninja ! It's purpose is to show you an implementation of a basic and simple algorithm in machine language, hopefully to give you an understanding of how things work on a deep level.
At first the algorithm I wanted to show you how to implement is the insertion sort algorithm. But while writing this post, I figured out that it's implementation was hard to understand for the beginner this post is for. So I decided to be doing a simpler one, a program that calculate the sum of 16 integers ( 32 bits long integers ).
Well, in this example, I will be using the Motorola MC68000 also known as MC68K, a 32 bits processor with a huge frequency of 2 MHz ( yeah, you heard right *M*Hz ). Yes it's an old one, but widely used in the 80's, and simple to start with.
First we have the microprocessor ( Wow ! #captain_obvious ). What interest us in it besides it's logical and arithmetic unit, is it's registers. What a register you might ask. Well, a register is a temporary memory located inside the microprocessor. There are two types, data registers, which can hold data ( thanks again captain obvious ), and address registers, which holds memory addresses. In our case, the MC68K has 8 address registers and 8 data registers, both of them can hold up to 32 bits of data. We are also going to be using a main memory of 16 M Bytes ( yes who needs more).
i ← 0
sum ← 0
while i < length(A)
sum ← sum + A[i]
Or if you prefer in a more friendly language like C :
void sum(int arr, int n)
int i, sum = 0;
for (i = 1; i < n; i++)
sum += arr[i];
In order for us not to drown in '1's and '0's, we should start by writing our code in assembly language. Assembly language is the layer just about machine language. And because assembly is just a more friendly way to write binary, it's also called machine language.
Finally ! To simplify things a little bit we'll assume we have in memory the array we'll use.
note : for simplicity I will skip some steps
START MOVE #15,D0 We initialize the counter, we will be decrementing
CLR D1 We clear some registers nothing fancy, this one for the cumulative sum
CLR D2 this one for the current value to add to the sum
LEA ARRAY(PC),A0 We store the array adress in an adress register
LEA SUM,A1 We store the memory address where we are going to write the result
LOOP MOVE.W (A0)+,D2 Now copy each each element of the array
ADD.L D2,D1 we add it to the cumulative sum
DBRA D0,BCL We loop till the counter is equal to -1, yep that's how loops without condition are done in assembly
TRAP #0 We exit ( It's more complicated than that, but hey we're simplifiying )
SUM DS.L 1 We're asking for an empty spot in the memory
Hold on a sec, yes We'll write in binary but not in '1's and '0's, but in hexadecimal representation. In order to have the binary code, either we run an assembling program that will read each instruction ( an instruction is a line ), and write it in binary, and then we read the memory where it putted it to read the binary, but that will spoil the fun. Or we translate it manually. To do that we will need the processor documentation again to know how to translate each instruction and its arguments into binary. After doing it, we'll obtain the following code :
303C 000F 4241 4242 41FA 0014 43F9 0000 103E 3418 D282 51C8 FFFA 2281 4E40
or if you insist, here it is in binary :
note : the code will vary slightly depending on the address of the array and the address where the program will put the result
I hope that this post was fun to read, maybe you'll never need in your life to use assembly, but it's always fun and very interesting to see how the program we write in the high level language we cherish are seen by the microprocessor in reality.