Advanced Digirule 2 Programming¶
dgtools
provides an assembler that can interpret labels as memory addresses and this makes it possible to start
creating more involved programs.
However, one thing that the Digirule2 hardware itself does not specify is a stack which is an important part of more complex programs that include function calling.
This section first establishes a stack and associated operations (push, pop), later a set of registers and finally based on these pre-requisites it demonstrates function calling with parameters passed on the stack.
Defining a Stack¶
The Digirule 2 is capable of referencing approximately 256 bytes of main memory. Therefore, it should be possible to
implement a stack as a statically allocated array of N
values where the push and pop operations are carried out
at the “head” of the stack.
The only problem here is that the Digirule 2 instruction set does not support indirect memory access. The command COPYRR copies memory content from one address to another address but (out of the box) it cannot copy memory from the value of a memory address (i.e. where a memory location is pointing to), to the value of another address.
Implementing indirect memory access¶
To achieve this, we are going to use the label capabilities of dgasm
to “build” a COPYRR
that can copy memory
indirectly.
This is achieved by writing a “template” function:
1f_copy_by_ref:
2.DB 7
3f_from:
4.DB 0
5f_to:
6.DB 0
7RETURN
This is part of dg_asm_examples/advanced/stack.dsf
The first byte (7
) is the opcode of COPYRR
, the second byte is labeled f_from
and the third byte is
labeld f_to
.
The CPU is “tricked” into thinking that it executes a COPYRR
but this is now a parametrisable COPYRR
that copies
between two addresses that can be the result of any computation performed by the code.
To copy between two references, calculate the references (if required), move the references to addresses f_from
and f_to
and then execute a CALL f_copy_byref
. The CPU will fetch the 7
, decide it is a COPYRR
, read in
the next two bytes, perform the copy, hit the RETURN and go back to where it was called from.
Getting the “head” of the stack¶
Defining the stack through dgasm
is as trivial as defining a label and immediately populating it with values. For
example:
1stack:
2.DB 0xF0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0x0F
There is no particular reason for these default values other than making this memory range stand out in a memory dump.
The stack also needs a way of pointing to its head address.
Note
A stack is a data structure that can store and retrieve data through the operations of push and pop respectively. Both storage and retrieval are performed from a single end-point that always points at the top of the stack. Most commonly, this is called the “head” of the stack.
This can be achieved by using another “labeled” location:
1stack_ptr:
2.DB 0
Having defined the stack, we now need to define its two fundamental operations: push, pop
. This is relatively easy,
all we have to do is find out where the head is pointing to and send (or retrieve) a number to (or from) that location.
This is achieved with:
1f_push:
2CALL f_get_stack_head
3COPYAR f_to
4COPYLR r0 f_from
5CALL f_copy_by_ref
6INCR stack_ptr
7RETURN
8
9f_pop:
10DECR stack_ptr
11CALL f_get_stack_head
12COPYAR f_from
13COPYLR r0 f_to
14CALL f_copy_by_ref
15RETURN
16
17f_get_stack_head:
18COPYLA stack
19ADDRA stack_ptr
20RETURN
This is part of dg_asm_examples/advanced/stack.dsf
Note
This is a bit of an overkill for getting the head of a stack, because it assumes that the head has to
be re-calculated prior to every push or pop. Such a mode of access would be necessary in the case of an array
where elements can be stored to or read from randomly across any element of the array. Since the head of the
stack can only be increased or decreased and is being assigned to its own memory space, a much faster way of
working with it here would be to establish f_get_stack_head
as f_init_stack
and then use stack_ptr
directly at subsequent calls.
But for these examples, we will take the scenic route, as it makes the program traces more interesting too.
All that f_push, f_pop
do is to calculate where the head of the stack is and then pass that address as either the
f_from
or f_to
“parameter” of a made-up COPYRR
that now copies by reference.
But, how are these “low level” functions going to communicate with the rest of the code? The Digirule 2 does not specify a standardised register set.
By now, it should be clear that this is not a problem at all because we can use the labeled .DB capabilities of the assembler, to specify the equivalent of a “register” or even a complete set of registers.
For the purposes of this example, register r0
is used as the intermediate register for the f_push, f_pop
functions.
The complete example below pushes values 0,1,2,3,2,1,0,1,2 to the stack and terminates:
1start:
2COPYLR 0 r0
3CALL f_push
4COPYLR 1 r0
5CALL f_push
6COPYLR 2 r0
7CALL f_push
8COPYLR 3 r0
9CALL f_push
10COPYLR 2 r0
11CALL f_push
12COPYLR 1 r0
13CALL f_push
14COPYLR 0 r0
15CALL f_push
16COPYLR 1 r0
17CALL f_push
18COPYLR 2 r0
19CALL f_push
20HALT
21
22f_push:
23CALL f_get_stack_head
24COPYAR f_to
25COPYLR r0 f_from
26CALL f_copy_by_ref
27INCR stack_ptr
28RETURN
29
30f_pop:
31DECR stack_ptr
32CALL f_get_stack_head
33COPYAR f_from
34COPYLR r0 f_to
35CALL f_copy_by_ref
36RETURN
37
38f_get_stack_head:
39COPYLA stack
40ADDRA stack_ptr
41RETURN
42
43f_copy_by_ref:
44.DB 7
45f_from:
46.DB 0
47f_to:
48.DB 0
49RETURN
50
51
52r0:
53.DB 0
54
55stack_ptr:
56.DB 0
57stack:
58.DB 0xF0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0x0F
This listing is available in dg_asm_examples/advanced/stack.dsf
Function calls using a stack¶
Now that the Digirule 2 has a stack, it can call any function with any number of argument by adopting a “calling convention” and defining a standardised set of registers.
In this section, the addition of two numbers is performed within the following two argument function:
1q_add_ab:
2CALL f_pop
3COPYRR r0 t0
4CALL f_pop
5COPYRR r0 t1
6COPYRA t0
7ADDRA t1
8COPYAR r0
9CALL f_push
10RETURN
This is part of dg_asm_examples/advanced/funcall.dsf
Here, q_add_ab
first pops the numbers from the stack to “temporary registers”, performs the addition, pushes the
result back on to the stack and returns. All that the caller has to do now is to pop the stack on the “other side of
the call” to retrieve the result.
The complete listing is now:
1.EQU a=1
2.EQU b=2
3
4start:
5COPYLR a r0
6CALL f_push
7COPYLR b r0
8CALL f_push
9CALL q_add_ab
10CALL f_pop
11COPYRR r0 255
12HALT
13
14q_add_ab:
15CALL f_pop
16COPYRR r0 t0
17CALL f_pop
18COPYRR r0 t1
19COPYRA t0
20ADDRA t1
21COPYAR r0
22CALL f_push
23RETURN
24
25f_push:
26CALL f_get_stack_head
27COPYAR f_to
28COPYLR r0 f_from
29CALL f_copy_by_ref
30INCR stack_ptr
31RETURN
32
33f_pop:
34DECR stack_ptr
35CALL f_get_stack_head
36COPYAR f_from
37COPYLR r0 f_to
38CALL f_copy_by_ref
39RETURN
40
41f_get_stack_head:
42COPYLA stack
43ADDRA stack_ptr
44RETURN
45
46f_copy_by_ref:
47.DB 7
48f_from:
49.DB 0
50f_to:
51.DB 0
52RETURN
53
54
55r0:
56.DB 0
57r1:
58.DB 0
59r2:
60.DB 0
61r3:
62.DB 0
63r4:
64.DB 0
65r5:
66.DB 0
67r6:
68.DB 0
69r7:
70.DB 0
71
72t0:
73.DB 0
74t1:
75.DB 0
76t2:
77.DB 0
78t3:
79.DB 0
80t4:
81.DB 0
82t5:
83.DB 0
84t6:
85.DB 0
86t7:
87.DB 0
88
89stack_ptr:
90.DB 0
91stack:
92.DB 0xF0,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0,1,0x0F
This is listing dg_asm_examples/advanced/stack.dsf
.
It is basically a continuation of listing dg_asm_examples/intro/simpleadd_5.dsf
and it could be called externally as per this example from the introductory section.
Conclusion¶
Now that Digirule 2 has a stack and a set of standardised registers, it is possible to start thinking about implementing a higher level language that compiles down to its assembly.
It should then be possible to write arbitrarily complex programs to carry out functionality possibly not envisaged for the Digirule 2.
But, aside from being 8bit and having a very limited amount of memory, there is nothing that can be expressed with a “stack machine” that Digirule cannot do.
It might be slow and somewhat difficult to define, but Digirule will eventally compute it.