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.