Volume 0 - Basics

Hello World

This is the shortest Digirule ASM program.

You can key it in by entering the numbers 4,1,8,1,0, or you can dgasm and dgsim it first.

1
2
3
4
5
# DigiruleASM "Hello World"

COPYLA 1
ADDLA 1
HALT

The Quick Brown Fox Jumps Over The Lazy Dog

This is a pangram phrase where every letter of English is used exactly once.

The following code snippet is the Digirule ASM equivalent where every operation is used exactly once.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
# The quick brown fox jumps over the lazy dog

.EQU status_reg=252
.EQU zero_bit=0
.EQU carry_bit=1

SBR 7 R0
SHIFTRL R0
SHIFTRR R1
INCR R0
COPYRA R0
XORLA 0xFF
ANDLA 0xF0
SUBLA 0x10
ORLA 0x02
CALL some_proc
ADDRA R1
XORRA R1
SUBRA R1
ORRA R1
INCRJZ R0
BCRSC zero_bit status_reg
DECRJZ R1
CBR zero_bit status_reg
COPYAR R1
COPYRR R1 R0
ADDRPC R0
HALT

some_proc:
COPYLR 0x01 R1
BCRSS zero_bit status_reg
RETLA 0xF
RETURN

R0:
.DB 0
R1:
.DB 0
.DB 0xFF
.DB 0xFF
.DB 0xFF
.DB 0xFF
.DB 0xFF
HALT

Assignments

Most programming languages have assignments. But, just typing a=42 in an editor, is not enough.

Something must realise the intention. Here is what assignments come down to on the Digirule.

Assigning a literal

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
# Literal assignment
# Or what in a higher level language
# could be written as:

# byte R0=0
# ...
# ...
# R0 = 1

COPYLR 1 R0
HALT

R0:
.DB 0

Assigning to expression

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
# Assigning to expression 1
# Or what in a higher level language
# would be written as:

# unsigned char R0=1, R1=42
# ...
# R0 = R1

# Obviously an "expression" is not visible here.
# But, at the ASM level the expression itself 
# has to be explicitly evaluated and this would 
# still be the last step in order to send the 
# result of the expression from some temporary 
# register to the variable

COPYRR R1 R0
HALT

R0:
.DB 1
R1:
.DB 42

Assigning to expression with indirect addressing

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
# Assigning to expression 2
# Or what in a higher level language
# would be written as:

# byte *f_from = NULL, *f_to = NULL;
# byte R0 = 1, R1 = 42;
# ...
# ...
# f_from = &R1
# f_to = &R0
# *f_to = *f_from

COPYLR R1 f_from  # f_from = &R1
COPYLR R0 f_to    # f_to = &R0
CALL f_copy_ind   # *f_from = *f_to
HALT

R0:
.DB 1
R1:
.DB 42

# Memory copy by indirect addressing via self-modification.
# We construct a suitable absolute
# addressing copy instruction (COPYRR) and
# execute it as a sub-routine over f_from, f_to
f_copy_ind:
.DB 7
f_from:
.DB 0
f_to:
.DB 0
RETURN

Swapping the values of two variables

You can just “swap two variables”, or you can use Parallel Assignment

On the Digirule, it is a matter of 3 or 15 clock ticks.

Remember which algorithm uses so many swaps that it gets all…fizzy?

Swap two variables

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
# Plain value swapping between two variables

# Swaps are "traditionally" handled in a 
# Towers-of-Hanoi kind of way, using an 
# intermeidate variable.

# Higher level languages might even offer 
# "parallel assignment" by which a swap
# is expressed as a,b = b,a

# Here, we implement the barebones way of 
# swapping the values of R0,R1, through 
# an intermediate variable R2. In a higher level 
# language this might be written as:

# R2 = R0
# R0 = R1
# R1 = R2

COPYRR R0 R2
COPYRR R1 R0
COPYRR R2 R1
HALT

R0:
.DB 1
R1:
.DB 42
R2:
.DB 0

Swap with indirect copy

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# Indirect value swapping between two variables

# This version achieves the same end-result as swap_simple
# but uses memory copies via indirect addressing.

# In a higher level language this might be written as:
# unsigned char *f_from=NULL, *f_to=NULL;
# unsigned char R0=1, R1=42, R2=0;
# f_from=&R0;f_to=&R2; *f_to = *f_from;
# f_from=&R1;f_to=&R0; *f_to = *f_from;
# f_from=&R2;f_to=&R1; *f_to = *f_from;

COPYLR R0 f_from
COPYLR R2 f_to
CALL f_copy_ind

COPYLR R1 f_from
COPYLR R0 f_to
CALL f_copy_ind

COPYLR R2 f_from
COPYLR R1 f_to
CALL f_copy_ind
HALT

R0:
.DB 1
R1:
.DB 42
R2:
.DB 0

# Memory copy by indirect addressing via self-modification.
# We construct a suitable absolute
# addressing copy instruction (COPYRR) and
# execute it as a sub-routine over f_from, f_to
f_copy_ind:
.DB 7
f_from:
.DB 0
f_to:
.DB 0
RETURN

Array Indexing

Up here, we can write my_array[5] but this implies not one but two operations:

  1. Discover the address

  2. Fetch from address.

Here is how arrays are expressed on the Digirule.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
# Array indexing
# Setup an array and retrieve a number from it

# "Arrays" are consecutive memory addresses,
# with a base address (where they start) and 
# a "stride" that depends on each element's 
# data type.

# Here, we establish an array of 10 values (num_array)
# and retrieve the 5th element from it (using array_idx).
# The value is returned in array_idx_value

# In a higher level language, this could be written 
# as:
# unsigned char num_array[]={1,3,8,12,150,14,38,22,110,20};
# num_array[5]
# ...or even more accurately:
# unsigned char *p_num_array=&num_array
# *(p_num_array+5)

# Notice here that accessing a particular index is not only a
# matter of a memory transfer, but an addition too.

# Calculate the memory offset
COPYLA num_array
ADDRA array_idx
# Fetch the value from that memory offset to array_idx_value
COPYAR f_from
COPYLR array_idx_value f_to
CALL f_copy_ind
HALT


f_copy_ind:
# Memory copy by indirect addressing via self-modification.
# We construct a suitable absolute
# addressing copy instruction (COPYRR) and
# execute it as a sub-routine over f_from, f_to
.DB 7   # COPYRR opcode
f_from:
.DB 0
f_to:
.DB 0
RETURN

array_idx:
.DB 5
array_idx_value:
.DB 0
num_array:
.DB 1,3,8,12,150,14,38,22,110,20

Conditional branching & the if command

When you write if (R0 < R1) {} else {};, how is this evaluated by a CPU?

What does an IF look like when it comes to actually doing it.

Here it is, on a Digirule, the simplest form of flow control.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
# If (expression) run_block_a else run_block_b :: part 1

# A high level "if" captures an ASM pattern where an 
# expression is evaluated and based on that expression's 
# result deciding whether to execute "run_block_a" or 
# "run_block_b" block of commands.

# In a higher level language, this might be written as:
# unsigned char R0, R1, R3

.EQU status_reg=252 # The status register on the Digirule
.EQU carry_bit=1

# IF STARTS HERE
# To test the expression, we
# first have to evaluate the 
# expression.

COPYRA R0
SUBRA R1

# We now check the result of 
# the expression, if the 
# carry bit is set after 
# R0-R1, then R0>R1 else
# R0<=R1.

BCRSC carry_bit status_reg
JUMP lt
JUMP gte


# "THEN" BRANCH STARTS HERE
# then R2 = 0xF0

lt:
COPYLR 0xF0 R2
HALT


# "ELSE" BRANCH STARTS HERE
# else R2 = 0xF0

gte:
COPYLR 0x0F R2
HALT


R0:
.DB 1
R1:
.DB 2
R2:
.DB 0xFF

There is a difference between if (R0 < R1)...; and if (R0<=R1)...; and on the Digirule that difference is 2 clock cycles.

EVERY symbol counts.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
# If (expression) run_block_a else run_block_b :: part 2

# This is almost identical to R0<R1 but since the expression 
# now is R0<=R1, we also add an extra branch to show 
# the equality case. Typically, only two exit points 
# from this block are maintained.


.EQU status_reg=252 # The status register on the Digirule
.EQU carry_bit=1
.EQU zero_bit=0


# Evaluate the expression...
COPYRA R0
SUBRA R1

# Test its result...
BCRSC carry_bit status_reg
JUMP lt
JUMP gte

# "THEN" BRANCH STARTS HERE
lt:
COPYLR 0xF0 R2
HALT

gte:
# At this point, we know that R0<R1 does NOT hold.
# But, the opposite of R0<R1 is not R1>R0 but 
# R1>0 OR R1==R0. Therefore, knowing that 
# R0 IS NOT LESS THAN R1 we proceed here to 
# test if R0==R1. 
BCRSC zero_bit status_reg
JUMP gte_final
JUMP gt_final
HALT

# The two branches are split here just to illustrate 
# the <= distinction. Typically: 

# "ELSE" BRANCH STARTS HERE

gte_final:
COPYLR 0x18 R2
HALT
gt_final:
COPYLR 0x0F R2
HALT


R0:
.DB 2
R1:
.DB 1
R2:
.DB 0xFF

Iteration

We already saw some simple flow control in Digirule ASM.

Diverting execution depending on an expression soon leads to doing things repeatedly until a condition is met.

Here we re-use that to show``FOR`` and WHILE ASM code equivalents on a Digirule.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
# For - loop (a.k.a Bounded Iteration)

# At the ASM level, there is only conditional 
# and unconditional branching and therefore
# just one pattern that leads to iteration.
 
# FOR and WHILE, the two fundamental ways to 
# express iteration, are higher level constructs.

# FOR is used when the iteration bounds (start 
#     and end) are known; and
# WHILE is used when the bounds are not known but 
#     an expression that determines when the loop
#     has to conclude is known.

# There is nothing at the CPU level that actually 
# "does" a FOR, or WHILE.

# In a higher level language, this would be written as:

# unsigned char R0=63;
# for (R0=4;R0++;R0<22) {}
 

.EQU status_reg=252 # The status register on the Digirule2
.EQU zero_bit=0  

# Set the initial value of the iteration variable R0
COPYLR 4 R0 # Equivalent to: for (R0=4;...
loop_start:
NOP         # Equivalent to: {}

INCR R0     # Equivalent to: R0++;...

# End condition satisfied?
COPYRA R0 
SUBLA 22    # Equivalent to: ...R0<22)
BCRSS zero_bit status_reg
JUMP loop_start # Jump to loop_start if it doesn't.
HALT

R0:
.DB 63

Copying a memory block

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
# Copy across memory (arrays).

# An array represents a continuous memory block
# that begins at some address and has a length.

# In some high level languages, such as C, 
# the array must be homogeneous. That is, every 
# one of its elements can be of one and only one 
# type.
# In others, such as Python, each 
# element of the array can be an object of a 
# different type. 

# These incredibly flexible arrays are, again, 
# higher level constructs. In other words, they 
# are conveniences that are still pieced 
# together and delivered via the same low level 
# operations.

# At the level of the CPU, the only thing that 
# trully _exists_ is mathematical and memory 
# operations.

# Here, copying one array to another is a matter 
# of calling a COPY operation ITERATIVELY for every
# one of the array's elements. And right now, on the
# Digirule2, we know how to both do iterations and 
# indirect copies. 

# In a higher level language, this could be expressed 
# as:
# unsigned short R0[] = {0xAB, 0xCD, 0xEF, 0xFE, 0xDC, 0xBA};
# unsigned short R1[] = {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF};
# unsigned short *f_from = NULL, *f_to = NULL;
# unsigned short f_block_len = 6
# f_from = &R0;
# f_to = &R1;
# while (f_block_len){
#   *f_to = *f_from;
#   f_block_len--;
#   f_to++;
#   f_from++;


COPYLR R0 f_from        # f_from = &R0; 
COPYLR R1 f_to          # f_from = &R0;
CALL f_copy_block
HALT


# Generalises f_copy_ind so that it copies the values
# of an array of length f_copy_block.
# To call it, set:
# f_from to the beginning of the source block
# f_to to the beginning of the target block
# f_copy_block to how many elements to copy

f_copy_block:
CALL f_copy_ind         # *f_to = *f_from;
INCR f_from             # *f_from++;
INCR f_to               # *f_to++;
DECRJZ f_block_len      # f_block_len--; AND while (f_block_len){...
JUMP f_copy_block       
RETURN



# Memory copy by indirect addressing via self-modification.
# We construct a suitable absolute
# addressing copy instruction (COPYRR) and
# execute it as a sub-routine over f_from, f_to

f_copy_ind:
.DB 7
f_from:
.DB 0
f_to:
.DB 0
RETURN 

R0:
.DB 0xAB, 0xCD, 0xEF, 0xFE, 0xDC, 0xBA

R1:
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF

f_block_len:
.DB 6

Swapping values between two memory blocks

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
# Swap the values of two arrays around.

# This program extends the idea of swapping 
# the values of two variables (2 1-byte values), 
# to swapping the contents of two arrays.

# This is realised by using a third array that 
# stores the value of one of the variables being 
# swapped.

# In a higher level language, this could be written as:
# void f_copy_block(unigned short *f_from, 
#                   unsigned short *f_to, 
#                   unsigned short f_block_len) {
#     while (f_block_len){
#         *f_to = *f_from;
#          f_to++;
#          f_from++;
#          f_block_len--;
#     }
# }
# unsigned int R0[] = {0xFA, 0xBF, 0xAB, 0xFA, 0xBF, 0xAB};
# unsigned int R1[] = {0xBA, 0xEB, 0xAE, 0xBA, 0xEB, 0xAE}; 
# unsigned int R2[] = {0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF};
# f_copy_block(R0,R2,6)
# f_copy_block(R1,R0,6)
# f_copy_block(R2,R1,6)


COPYLR R0 f_from 
COPYLR R2 f_to
COPYLR 6 f_block_len
CALL f_copy_block

COPYLR R1 f_from 
COPYLR R0 f_to
COPYLR 6 f_block_len
CALL f_copy_block

COPYLR R2 f_from 
COPYLR R1 f_to
COPYLR 6 f_block_len
CALL f_copy_block
HALT


# Generalises f_copy_ind so that it copies the values
# of an array of length f_copy_block.
# To call it, set:
# f_from to the beginning of the source block
# f_to to the beginning of the target block
# f_copy_block to how many elements to copy

f_copy_block:
CALL f_copy_ind
INCR f_from
INCR f_to
DECRJZ f_block_len
JUMP f_copy_block
RETURN

# Memory copy by indirect addressing via self-modification.
# We construct a suitable absolute
# addressing copy instruction (COPYRR) and
# execute it as a sub-routine over f_from, f_to

f_copy_ind:
.DB 7
f_from:
.DB 0
f_to:
.DB 0
RETURN 

R0:
.DB 0xFA, 0xBF, 0xAB, 0xFA, 0xBF, 0xAB

R1:
.DB 0xBA, 0xEB, 0xAE, 0xBA, 0xEB, 0xAE

R2:
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF

f_block_len:
.DB 0