LESSON #1 : Fibonacci routine in ASM Motorola 68000.
Overview
For the first lesson, i will show you how to code the famous Fibonacci routine in ASM.
This algorithm is often used as an example / snippet to learn a new programming language syntax.
http://www.scriptol.com/programming/fibonacci.php
So, why not do it also for the Motorola 68000 processor ?
The Fibonacci formula calculates a sequence of integer numbers, well-known in mathematics and computer science.
The sequence is always the same :
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, [...]
fibonacci(0) ==> 0
fibonacci(1) ==> 1
fibonacci(2) ==> 1
fibonacci(3) ==> 2
fibonacci(4) ==> 3
fibonacci(5) ==> 5
fibonacci(6) ==> 8
fibonacci(7) ==> 13
fibonacci(8) ==> 21
[...]
More informations about the Fibonacci number can be found here :
https://en.wikipedia.org/wiki/Fibonacci_number
Begin the lesson with a Javascript implementation of the Fibonacci formula
Why Javascript ? Well, because it is simple and available for all of us. Just open your modern favorite web-browser in your main home computer, type the F12 key, and you have a ready-to-use tool that can execute code.
A typical Javascript Fibonacci program could be written like this :
function fibonacci(n) {
return (n <= 2) ? 1 : fibonacci(n - 1) + fibonacci(n - 2);
}
But this is a recursive function - a function that calls itself - and i do not want this as a first ASM lesson.
So, better use such procedural approach :
function fibonacci(n) {
var result = 1, a = 0, b = 1;
while (n > 1) {
result = a + b;
a = b;
b = result;
n--;
}
return result;
}
Translating this function in ASM
In the 68000 CPU, the developer can use Data Registers to store any 32bits integer values. There is 8 Data Registers (D0 to D7). The CPU also have 8 Address Registers (A0 to A7) that can store any 32bits integer values just like the Data Registers does - but this time they should store a 32bits Address (pointer to a memory area) rather than a random value. In other words a Address Register should contains a Valid Address whereas a Data Register can contains any value. For our example, we only need to use Data Registers ; which is better for this first ASM lesson.
function fibonacci(d0) {
var d1 = 1, d2 = 0, d3 = 1;
while (d0 > 1) {
d1 = d2 + d3;
d2 = d3;
d3 = d1;
d0--;
}
return d1;
}
Once this is done, we will again make some changes to the Javascript code to avoid such mathematical expressions : d1 = d2 + d3;
We can't do such complex operations in ASM. We need to simplify it a little.
d1 = d2 + d3;
This is equal to :
d1 = d2;
d1 += d3;
According to this simple rule, we now rewrite the our function like this :
function fibonacci(d0) {
var d1 = 1;
var d2 = 0;
var d3 = 1;
while (d0 > 1) {
d1 = d2;
d1 += d3;
d2 = d3;
d3 = d1;
d0 -= 1;
}
return d1;
}
Create our own ASM Sub-Routine
That is good enough now. We have a simple Fibonacci function, easy to convert in ASM. Only thing remaining is the While loop. In assembly language, you have no choice, all loops are done using the good old LABELS / GOTO, just like it is/was with old BASIC language.
Let's see how this looks like :
01 Fibonacci: ; function fibonacci(d0) {
02 move.l #1,d1 ; d1 = 1
03 move.l #0,d2 ; d2 = 0
04 move.l #1,d3 ; d3 = 1
05 .loop ;
06 cmp.l #1,d0 ; while (d0 > 1)
07 ble .exit ; {
08 move.l d2,d1 ; d1 = d2
09 add.l d3,d1 ; d1 += d3
10 move.l d3,d2 ; d2 = d3
11 move.l d1,d3 ; d3 = d1
12 sub.l #1,d0 ; d0 -= 1
13 bra .loop ; }
14 .exit ;
15 rts ; }
Ok, it is done ! This 68K ASM Fibonacci routine works :) It is not optimized but it works as expected.
As you can see in this ASM code there is some stuff that needs to be explained. Let's try to do so line after line.
Line 1 : We declare the name of the function. It is a simple Label. In assembly language we call such Labels a "Sub-Routine" label.
Line 2 to 4 : We initialize our 3 variables, just like in the Javascript function.
Line 5 : We declare a sub-label. This label is in the scope of our Sub-Routine label. This means this label is not usable "outside" of the sub-routine. This label is used to "emulate" our "While" Javascript keyword.
Line 6 : Here we process the boolean expression of our "While". We wants to compare the Data Register "d0" and the numerical value "1". Such numerical values are called "Immediates values" in assembly language.
Line 7 : Once we asked the CPU to compare "d0" and "1", we wants now to compute our ">" operator (Greater Than). CMP must have the numerical value as Left Operator. So we need to reverse our comparison. This becomes "Lower or Equal" which is "BLE". BLE means Branch to the given Label (.exit) if Right Operand (d0) is Lower or Equal to the Left Operand (1).
Line 8 to 12 : Easy to understand. Look at the comments and keep in mind that the Right operator is the destination whereas the Left operator is the source.
Line 13 : We branch to the .loop Label. This is same as the closing bracket of the Javascript While.
Line 14 : This is our Exit label, used by our comparison at line 6.
Line 15 : This RTS keyword tells the CPU to Return Sub-Routine. This means the program will come back to the main program. This is equivalent to the closing bracket of our Javascript function.
Call our Sub-Routine in a ASM program
Ok ok, we have a sub-routine that computes Fibonacci values. But how to make a full program with this ?
Well, this is not complicated. Just a matter of some lines in a so called "Main" program.
Here it is :
Main: ; Main program
move.l #8,d0 ; d0 = 8
bsr Fibonacci ; Fibonacci(8)
rts ; Stop the main program
Fibonacci: ; Sub-routine
move.l #1,d1 ; d1 = 1
move.l #0,d2 ; d2 = 0
move.l #1,d3 ; d3 = 1
.loop ;
cmp.l #1,d0 ; while (d0 > 1)
ble .exit ; {
stop #-1 ;
move.l d2,d1 ; d1 = d2
add.l d3,d1 ; d1 += d3
move.l d3,d2 ; d2 = d3
move.l d1,d3 ; d3 = d1
sub.l #1,d0 ; d0 -= 1
bra .loop ; }
.exit ;
rts ; Exit the Sub-Routine
What to learn here ?
We have a "Main" label which is the Main program, just as a main() in a C source code.
Difference is you can call it as you want. Main: or Program: or MyProgram: or anything you prefers.
The "BSR". The BSR means "Branch to Sub-Routine" and will move the program to the given label - to our Fibonacci sub-routine.
The "RTS". The RTS in the main program will exit the program and return to the Operating System whereas a RTS in a sub-routine only exit from the sub-routine.
Ok, seems we understand little more how works a ASM program now. But there is something that is bad in our program (actually there is more than one but it is enough for the first lesson).
Protect the registers used in our Sub-Routine
As you can see our sub-routine use some Data Registers. We use D0, D1, D2 and D3. This 4 registers are used and overwritten by such instructions : MOVE Something into Dx.
Well, and ? Is it a problem ? Yes it could be. Our Data-Registers needs to be "protected" in the Sub-Routine so that the main program will not be impacted by the sub-routine execution. Just like a Javascript (or any language) function has his own scope inside the brackets { }. Remark : This is not mandatory, you could deliberately not wants to protect your routine to saves some execution cycles but then you need to perfectely know what you do - but this is another story. Let's focus on our 'protection'.
The protection is quite easy to add to our sub-routine. This is done like this :
Main: ; Main program
move.l #8,d0 ; d0 = 8
bsr Fibonacci ; Fibonacci(8)
; d0 = $15 = 21
rts ; Stop the main program
Fibonacci: ; Sub-Routine
movem.l d1-d3,-(sp) ; Store used registers
move.l #1,d1 ; d1 = 1
move.l #0,d2 ; d2 = 0
move.l #1,d3 ; d3 = 1
.loop ;
cmp.l #1,d0 ; while (d0 > 1)
ble .exit ; {
stop #-1 ;
move.l d2,d1 ; d1 = d2
add.l d3,d1 ; d1 += d3
move.l d3,d2 ; d2 = d3
move.l d1,d3 ; d3 = d1
sub.l #1,d0 ; d0 -= 1
bra .loop ; }
.exit ;
move.l d1,d0 ; Put the result in d0
movem.l (sp)+,d1-d3 ; Restore used registers
rts ; Exit from the Sub-Routine
The MOVEM instruction is like the MOVE instruction but it can move the contents of one or more registers into the STACK of the program, in one ASM instruction. The stack is a memory area that is pre-allocated by the Operating System when it executes a new task. Typically, the stack is 4096 bytes, but it can be much more. We are speaking of the same stack as the one we use in the AmigaOS CLI / SHELL when we do >SetStack 10000 for example. This memory area is very useful to store temporary our CPU Registers contents or any other datas. By convention, a sub-routine store and restore the registers in this dedicated memory area.
The SP is a special register. It is a ALIAS of the A7 Address Register that represents the stack of our program. This can be replace by A7 but it is more readable to use SP (Stack Pointer). We will studied it later, so i will not develop more this right now.
End-notes
Don't forget to refers to official Motorola documentation and to some useful existing websites :
http://68k.hax.com/
https://www.nxp.com/files/archives/doc/ref_manual/M68000PRM.pdf
See you for the next lesson.
Aucun commentaire:
Enregistrer un commentaire
Remarque : Seul un membre de ce blog est autorisé à enregistrer un commentaire.