Volume 1 - Complex programs

The programs in this sections are re-using concepts and techniques that are introduced in the ref:section about the basics <vol_0>.

Implement A Stack

What use is a stack within a CPU? And what if a CPU doesn’t have one?

Out of the box, the Digirule2 does not have an internal stack. It is however possible, to implement one and this implementation relies heavily on the indirect copy snippet that was presented earlier.

# Simple stack & operations

# A stack is a data structure in which 
# all operations (Read & Write) take 
# place through its "head" pointer.

# In ASM, it looks like an array (e.g stack[n])
# but unlike an array, "n" IS NOT specified freely 
# but through two simple rules:

# 1 - Increase n AFTER Write
# 2 - Decrease n BEFORE Read

# Thus "n" always points to the next available 
# value, at the TOP of the stack. 
# Because of this, the Read and Write ops are more 
# descriptively known as PUSH and POP.

# Stacks are also known as First-In-First-Out 
# or FIFO lists.

# In this demo, we demonstrate this "FIFO" logic, by 
# swapping the contents of two variables by:
# PUSH R0
# PUSH R1  
# POP R0  
# POP R1   

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

# Initialise the stack head
COPYLR stack stack_ptr

# To push, point f_from to the variable to push to the 
# head of the stack and call f_push
# PUSH R0
COPYLR R0 f_from
CALL f_push

# PUSH R1
COPYLR R1 f_from
CALL f_push

# To pop, point f_to to the variable to pop the head of
# stack to and call f_pop.
# POP R0 
# Which now receives the value of R1. >>FIFO<<
COPYLR R0 f_to
CALL f_pop

# POP R1 
# Which now receives the value of R0.
COPYLR R1 f_to
CALL f_pop
HALT

# Pushes the value of whatever f_from points to, to 
# the top of the stack.
f_push:
COPYRR stack_ptr f_to
CALL f_copy_ind
INCR stack_ptr
RETURN

# Pops the value of the top of the stack to whatever f_to 
# points to.
f_pop:
COPYRA stack_ptr
SUBLA stack
BCRSS zero_bit status_reg # NOTE THIS CHECK. It prevents >>UNDERFLOW<<
DECR stack_ptr
COPYRR stack_ptr f_from
CALL f_copy_ind
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 0xF0
R1:
.DB 0x0F
stack:
.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
stack_ptr:
.DB 0

Function calling conventions

The Digirule’s instruction set includes a CALL operation. It stores the value of the Program Counter (PC) to the internal stack and transfer execution to a different point in memory. Execution returns to the calling point once a RETURN or RETLA is encountered.

But, calling functions with an arbitrary number of arguments is slightly different and relies heavily on the CPUs stack.

This little demo shows a cdecl(ish) call convention to swap two numbers.

# Function calling and call conventions

# Stacks allow us to define functions with 
# many different arguments.

# This brings about the question of how to load 
# and clear the stack before and after a function 
# call.

# There are different ways to do this which are 
# collectively known as "Calling Conventions".

# Here, we are demonstrating a cdecl inspired 
# scheme, adapted to the Digirule ASM.

# In a higher level language, this demo would be
# written as:
# unsigned short f_add_two_numbers(unsigned short R0, unsigned short R1){
#    return R0 + R1
# }
# ...
# ...
# R0 = f_add_two_numbers(2,2)

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

# Initialise the stack head
COPYLR stack stack_ptr

COPYLR 2 R0
COPYLR R0 f_from
# Push 2 twice, so the function will do 2+2
CALL f_push
CALL f_push 
CALL f_add_two_numbers  # Equivalent to: f_add_two_numbers(2,2) 
COPYAR R0
HALT


# Self-explanatory
f_add_two_numbers:
COPYLR R0 f_to
CALL f_pop
COPYRA R0
CALL f_pop
ADDRA R0
RETURN

# Pushes the value of whatever f_from points to, to 
# the top of the stack.
f_push:
COPYRR stack_ptr f_to
CALL f_copy_ind
INCR stack_ptr
RETURN

# Pops the value of the top of the stack to whatever f_to 
# points to.
# NOTE HERE: We re-use the value of the Accumulator which 
# we may be already using in another part of the program.
# This too is specified in the cdecl convention.
f_pop:
COPYAR T0 # Save the Accumulator
COPYRA stack_ptr
SUBLA stack
BCRSS zero_bit status_reg # NOTE THIS CHECK. It prevents >>UNDERFLOW<<
DECR stack_ptr
COPYRA T0 # Restore the Accumulator
COPYRR stack_ptr f_from
CALL f_copy_ind
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 0xF0
T0:
.DB 0xFF
stack:
.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
stack_ptr:
.DB 0

Recursion

Being able to call functions, leads naturally to the question “Can a function call itself?”.

This is called recursion and is a very important concept in computer science (and mathematics), since it allows us to express complex iterative processes that are composed of “setup” and repetitive steps.

Having defined a stack on the #Digirule it is relatively easy to express recursion.

This is demonstrated here via the recursive evaluation of a Fibonacci series evaluation.

What is the largest Fibonacci term that the Digirule can compute out of the box?

How many steps does it take to do that?

# Recursive Fibonacci

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

# Initialise the stack head
COPYLR stack stack_ptr

COPYLR 7 R0
COPYLR R0 f_from
CALL f_push
CALL f_fibonacci
COPYAR R0
HALT


# Self-explanatory
f_fibonacci:
COPYLR R0 f_to
CALL f_pop
COPYLA 2
SUBRA R0
BCRSS carry_bit status_reg
JUMP f_fibonacci_ret_num
DECR R0
COPYLR R0 f_from
CALL f_push
CALL f_push
CALL f_fibonacci
COPYAR T1
COPYLR R0 f_to
CALL f_pop
DECR R0
COPYLR T1 f_from
CALL f_push
COPYLR R0 f_from
CALL f_push
CALL f_fibonacci
COPYLR T1 f_to
CALL f_pop
ADDRA T1
RETURN


f_fibonacci_ret_num:
COPYRA R0
RETURN

COPYRA R0
CALL f_pop
ADDRA R0
RETURN

# Pushes the value of whatever f_from points to, to 
# the top of the stack.
f_push:
COPYRR stack_ptr f_to
CALL f_copy_ind
INCR stack_ptr
RETURN

# Pops the value of the top of the stack to whatever f_to 
# points to.
# NOTE HERE: We re-use the value of the Accumulator which 
# we may be already using in another part of the program.
f_pop:
COPYAR T0 # Save the Accumulator
COPYRA stack_ptr
SUBLA stack
BCRSS zero_bit status_reg # NOTE THIS CHECK. It prevents >>UNDERFLOW<<
DECR stack_ptr
COPYRA T0 # Restore the Accumulator
COPYRR stack_ptr f_from
CALL f_copy_ind
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 0xF0
T0:
.DB 0xFF
T1:
.DB 0xFF
stack_ptr:
.DB 0
stack:
.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

Find the minimum value of an array of integers

One of the more detailed Digirule demos presented here, is that of a very simple random number generator, using a Linear Feedback Shift Register (LFSR). This random number generator, can be used to fill an array with random numbers.

But, what can we do with a set of random numbers?

We can find its minimum (or maximum)

What modifications would this code snippet require, so that it returns the maximum value of the array?

# Find the minimum value of an array of integers

# Plain simple minimum number finder:
# Suppose that the first number is the minimum
# then compare it against all others. If you 
# find a number that is smaller than the initial 
# assumption, make THAT number your current "assumed" 
# min.

.EQU status_reg=252  # The status register on the Digirule
.EQU carry_bit=1     # Carry bit field of the status reg
.EQU zero_bit=0      # Zero bit field of the status reg

# R0 Is the iteration bounded var
# R1 Is the current min value of the array
# R2 Is the index of the current min value

COPYLR 0 R0                     # Locate the zero element of the array...
COPYLA num_array
ADDRA R0
COPYAR f_from
COPYLR R1 f_to                  # ...and make it the "current min value".
CALL f_copy_ind
COPYRR R0 R2
loop_start:
COPYLA num_array
ADDRA R0                        # Fetch the next number from the array...
COPYAR f_from
COPYLR R3 f_to
CALL f_copy_ind

COPYRA R3
SUBRA R1
BCRSC carry_bit status_reg      # Is it smaller than the "current min value"?
CALL mark_new_min               # If it is, make THAT number the "current min value".
INCR R0                         # Otherwise, move to the next number to compare...
COPYRA R0
SUBLA 20
BCRSS zero_bit status_reg
JUMP loop_start                 # UNLESS, you have checked all N numbers (N=20 here) in
HALT                            # which case, stop.

mark_new_min:
COPYRR R0 R2
COPYRR R3 R1
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:
# memory prior to being called from the main program.
.DB 7   # COPYRR opcode
f_from:
.DB 0
f_to:
.DB 0
RETURN

R0:
.DB 0
R1:
.DB 0 
R2:
.DB 0
R3:
.DB 0

num_array:
.DB 1,3,8,12,150,14,38,22,110,20,191,88,175,61,59,42,139,222,215,0

Sorting an array of integers

Bubble Sort, Shaker Sort, Quicksort, Merge Sort, Heap sort, Insertion sort….Delay sort!

So many different ways to enforce order to a list of items.

This is a demonstration of the simplest, most primitive and slowest algorithm that is based on finding the minimum (or maximum) element in an array: “Selection Sort”.

The algorithm is composed of two steps:

1. Find the minimum of an array of \(N-n\) numbers starting at position \(n\),

2. Move that minimum value to position \(n\)

3. Repeat from step 1 while \(n<N\)

As is, the agorithm sorts a list of integers in ascending order. What modifications would make the algorithm to sort in descending order?

# Sort a list of integers using "Select Sort".

# Sorting algorithms are often used to 
# demonstrate the concept of computational complexity 
# (i.e. How many steps does it take for an algorithm 
# to complete a task).

# Here is a demonstration of one of the simplest, 
# most primitive and slowest algorithms to sort a 
# list of integers. It is called "Select Sort" and it 
# is basically the repetitive application of 
# finding an extreme element (min or max) and then 
# bringing it to the beginning of the list: 

# Find the min of ([5,12,6,1]) --> 1
# Move it to the beginning ([1,12,6,5])
# Find the min of (1,[12,6,5]) --> 5
# Move it to the beginning (1,[5,12,6])
# Find the min of (1,5,[12,6]) --> 6
# Move it to the beginning (1,5,6,12) DONE.

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

COPYLR 0 R4
COPYLR 0 R5
index_loop:
CALL f_find_min     # Find the minimum...

COPYLA num_array    # Move it to the beginning of the current block    
ADDRA R5
COPYAR f_from
COPYLR R6 f_to
CALL f_copy_ind
COPYAR f_to
COPYLA num_array
ADDRA R2
COPYAR f_from
CALL f_copy_ind
COPYAR f_to
COPYLR R6 f_from
CALL f_copy_ind

INCR R5  
INCR R4
COPYRA R4
SUBLA 7                     # Have all elements been covered?
BCRSS zero_bit status_reg
JUMP index_loop             # If not, repeat this sequence of steps
HALT                        # Else, terminate.


# R0 Is the iteration bounded var
# R1 Is the current min value of the array
# R2 Is the index of the current value
# R3 Is the current value at the current 
#    array index
# R4 is the index of the number that is 
#    currently under test.

f_find_min:
COPYRR R4 R0
COPYLA num_array
ADDRA R0
COPYAR f_from
COPYLR R1 f_to
CALL f_copy_ind
COPYRR R0 R2
loop_start:
COPYLA num_array
ADDRA R0
COPYAR f_from
COPYLR R3 f_to
CALL f_copy_ind

# Now R3 has the next number at offset R0 from label num_array
# Compare it with the currently assumed minimum

COPYRA R3
SUBRA R1
BCRSC carry_bit status_reg
CALL mark_new_min
INCR R0
COPYRA R0
SUBLA 8
BCRSS zero_bit status_reg
JUMP loop_start
RETURN

mark_new_min:
COPYRR R0 R2
COPYRR R3 R1
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   # COPYRR opcode
f_from:
.DB 0
f_to:
.DB 0
RETURN

R0:
.DB 0
R1:
.DB 0 
R2:
.DB 0
R3:
.DB 0
R4:
.DB 0
R5:
.DB 0
R6:
.DB 0

num_array:
.DB 10,132,8,12,150,9,1,4,192,200,0,0,0,0,0,0,0,0,0,0,0,0,0,0

Longest Ripple Counter Ever

A ripple counter and a relatively accurate clock signal source are the basic building blocks of digital timers.

All that a ripple counter does is count clock pulses. Now, suppose we have some i and we start counting in binary by repeatedly calling i=i+1 (or i++ for short).

The values of i will be:

   MSb    LSb  Decimal
bit 76543210
   -------------------
    00000000     0
    00000001     1
    00000010     2
    00000011     3
    00000100     4
    00000101     5
    00000110     6
    00000111     7
    ........    ...
    11111111    255

Bit 0, the Least Significant bit (LSb), counts \(0,1\) and then resets and “signals” bit 1, its neighbour to the left to count \(1\). Once bit 1 has counted its maximum (\(0,1\)) it will reset and “signal” bit 2, its neighbour to the left to count \(1\)….And so on, all the way to the Most Significant bit (MSb)).

From this point of view a ripple counter is just a chain of tiny little elementary counters, each one counting to its maximum and then advancing the next counter.

This continues until i now assumes the value 255 (or 11111111 in binary). Now, something special happens: If we try to i++ once more, i wraps around and hits zero again.

This is a fancy way of saying i resets and we could “catch” that event and use it to increase another variable (j) to start counting. This, would now look like:

• Increase variable i

  • Once i wraps around increase j

    • Once j wraps around increase k

      • Once k wraps around increase l

        • Once l wraps around increase m

And so on until we run out of memory.

In the following Digirule2 program, we use this concept to construct a ripple counter that is 224 BYTES long.

(Notice here the distinction between bit and Byte.)

A 1 byte long counter can count from \(0\) to \(2^{1 \times 8} - 1\), or \(255\).

A 224 byte long counter can count from \(0\) to \(2^{224 \times 8} - 1\) or …

279095111627852376407822673918065072905887935345660252615989519488029661278604994789701101367875859521849524793382568057369148405837577299984720398976429790087982805274893437406788716103454867635208144157749912668657006085226160261808841484862703257771979713923863820038729637520989894984676774385364934677289947762340313157123529922421738738162392233756507666339799675257002539356619747080176786496732679854783185583233878234270370065954615221443190595445898747930123678952192875629172092437548194134594886873249778512829119416327938768895

This number is big.

How Long Is Long?

Suppose that it takes the Digirule aproximately \(60e-6\) seconds 1 to increase the counter by 1. That is 60 microseconds.

• This means that this number, describes \(1.67457066976711425845e535\) seconds.

  • Divided by 3600 seconds in an hour, it describes \(4.6515851937975396068e531\) hours.

    • Divided by 24 hours in a day, it describes \(1.93816049741564150283e530\) days.

      • Divided by 30 days in a month, it describes \(6.46053499138547167611e528\) months.

        • Divided by 12 months in a year, it describes \(5.38377915948789306342e527\) years.

          • Divided by 100 years in a century, it describes \(5.38377915948789306342e525\) centuries.

            • Divided by 100 centuries in a millenium, it describes \(5.38377915948789306342e523\) millenia.

That is \(\approx 5.4 \times 10^{523}\) millenia.

There is no single battery that will keep this counter going until it counts to its maximum.

There is no single lifetime (devoted to maintaining a running Digirule) within which to see its value wrap around.

And while this counter scans through each and every value between \(0\) and \(2^{1792}\) as it gallops through the millenia, it also goes through ALL the possible Digirule 2 programs that can be constructed in 224 bytes and, all the possible phrases in English 2 that can be described in 224 bytes.

# One huge ripple counter

# The main idea behind this program was to write the 
# smallest program possible, using the most memory 
# possible.

# The program is making use of some self-modifying code 
# to produce an INCR indirect: An INCR instruction that 
# increases the value of a specific memory location.

# The counter is initialised at a very special occasion:
# It is about to reset itself from its maximum count back 
# down to 0. This creates a rippling effect as the reset 
# ripple travels from the Least Significant Byte (LSB) to 
# the Most Significant Byte (MSB).
 
# This counter is 224 BYTES long and the highest number it 
# can represent is:

# 27909511162785237640782267391806507290588793534566025261
# 59895194880296612786049947897011013678758595218495247933
# 82568057369148405837577299984720398976429790087982805274
# 89343740678871610345486763520814415774991266865700608522
# 61602618088414848627032577719797139238638200387296375209
# 89894984676774385364934677289947762340313157123529922421
# 73873816239223375650766633979967525700253935661974708017
# 67864967326798547831855832338782342703700659546152214431
# 90595445898747930123678952192875629172092437548194134594
# 886873249778512829119416327938768895

.EQU status_register=252        # Status register
.EQU zero_bit=0                 # Zero bit of the status reg

count_again:
COPYLR counter incr_addr        # Sets the target of INCR to incr (the LSB)
CALL incr_ind                   # Increases the LSB

count_higher:
BCRSS zero_bit status_register
JUMP count_again                # As soon as the LSB resets, increase 
INCR incr_addr                  # its most immediate MSB...
COPYRA incr_addr
SUBLA 253                       # Check if the counter has reached its maximum
BCRSC zero_bit status_register  # addressable byte and wrap around if it has.
JUMP count_again
CALL incr_ind                   # ...and keep rippling up the orders
JUMP count_higher               # of magnitude

# Indirect INCR
# Set incr_addr then call incr_ind
incr_ind:
.DB 19
incr_addr:
.DB 0
RETURN

# Start of the counter state
counter:
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF 
.DB 0xFF, 0xFF, 0xFF, 0xFF

Hacking the Status Register

Out of the 8 bits available in Digirule2’s status register, the CPU makes use of just 3:

• 0 Zero bit (Set when the previous operation resulted in 0)

• 1 Carry bit (Set when the previous operation results in a carry bit)

• 2 Display bit (Determines what the ADDR LEDs display)

This leaves another 5 bits “hidden” in the status register that go unused.

Are these bits accessible via Digirule2 code? And if they are, can we use them to save and recall the status register bits themselves?

Answering these questions ends up being a fantastic brainteaser, primarily because the instructions we use to manipulate the status register, also modify the status register.

Are the “hidden” bits accessible?

The idea here is to set the higher bits (>3) and then try to read them back. If their state has been preserved, then they can be considered “accessible”.

Here is the code:

# Hacking the status register. Can it be done?

# The Digirule2 has an 8bit status register but only uses 3 of those bits
# Is it possible to use the remaining 5 bits?

# It turns out that is. The following program confirms that when
# executed on the actual hardware.  

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

CBR 4 status_reg        # Clear bit 4 (this is the first of the "hidden" bits)
BCRSS 4 status_reg      # Test bit 4
JUMP disp_left          # If bit 4 is zero, display 0xF0    
JUMP disp_right         # If bit 4 is one, display 0x0F
HALT

disp_right:
COPYLR 0x0F R0
JUMP display

disp_left:
COPYLR 0xF0 R0
JUMP display

display:
COPYRR R0 led_reg
JUMP display

R0:
.DB 0

Keying this in to the Digirule2 confirms the result. It is indeed possible to write and read to those “hidden” bits.

Using the “hidden” bits to save and restore the status register

This all comes down to saving bits 0,1 to higher bits (say for example 4 and 5).

The straightforward way to do this would be to store the status register, shift it left by 3,ORit with the saved value and then store that result back to the status register. To restore it we can simply shift right by 3 positions and have the status register set to the stored values.

The following code is indeed along those lines but with minor differences since:

1. Logic operations such as OR go through the Accumulator but SHIFT** operations can be applied to numeric registers directly. Shifting and ORing to save the status register bits to higher bits would require an extra memory location. Which would then beg the question: Why not just save the status register to memory and move on? (But that is not what we are trying to do here).

1. The SHIFT** instructions are through the carry bit. Therefore, to just do SHIFT on the Digirule2, it has to be preceded by an instruction that clears the carry bit.

2. The COPYRR instruction modifies the zero bit.

For these reasons, saving and loading the values of the status register is carried out by plain simple bit operations. The code is almost identical which means that it can possibly be reduced and optimised even further (e.g. use the same function for saving and loading).

Here is the code:

# Hacking the status register. Save and Restore.

# Since we confirmed that it is possible to use the "hidden" 
# bits of the status register, is it possible to use it so that
# we save and restore the status register WITHOUT using additional 
# memory?

# It turns out that this is more difficult than it sounds at first, 
# because of the way the instruction set interacts with the carry 
# bit.

# The specific problem is that COPYRR modifies the zero flag. Therefore
# any computation that ends with a COPYRR in order to set the status 
# register to some new value ends up MODIFYING it as well.

# The answer? Do EVERYTHING with bit operations.

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

SBR carry_bit status_reg    # Set both bits of th status register
SBR zero_bit status_reg
CALL save_status_reg        # Save that value of the status register
COPYRR status_reg R0        # Check the content of R0
CBR carry_bit status_reg
CBR zero_bit status_reg     # Modify both flags and check the content again
COPYRR status_reg R0
CALL load_status_reg
COPYRR status_reg R0        # Recall the status register and examine it via R0.
HALT

save_status_reg:
CBR 3 status_reg                # Clear both higher bits
CBR 4 status_reg
BCRSC zero_bit status_reg       # Test bit 0 if it is 1 set the 4th bit
JUMP save_status_reg_zero_bit
save_status_reg_test_carry_bit:
BCRSC carry_bit status_reg      # Test bit 1 if it is 1 set the 5th bit
JUMP save_status_reg_carry_bit
save_status_reg_return:
RETURN

save_status_reg_zero_bit:
SBR 3 status_reg
JUMP save_status_reg_test_carry_bit
save_status_reg_carry_bit:
SBR 4 status_reg
JUMP save_status_reg_return

load_status_reg:                
CBR zero_bit status_reg                # Clear both higher bits
CBR carry_bit status_reg
BCRSC 3 status_reg       # Test bit 3 if it is 1 set the zero bit
JUMP load_status_reg_zero_bit
load_status_reg_test_carry_bit:
BCRSC 4 status_reg      # Test bit 4 if it is 1 set the carry bit
JUMP load_status_reg_carry_bit
load_status_reg_return:
RETURN

load_status_reg_zero_bit:
SBR zero_bit status_reg
JUMP load_status_reg_test_carry_bit
load_status_reg_carry_bit:
SBR carry_bit status_reg
JUMP load_status_reg_return

R0:
.DB 0

1

Brent Hauser responded with all the details about the Digirule2’s timings on the Discord server. The 60 micro second estimate is a conservative estimate of the Digirule’s timing to execute the counter program. If the hardware counts a bit slower than that, then the millenia will keep piling up. Even if the Digirule was made to run 1 order of mangitude faster, that would only knock off one order of magnitude from that \(...e51\). It would still be, a big number.

2

“…phrases in English” is the quicker thing to describe here, since the ASCII table contains direct correspondences of numbers to English characters. If the memory was interpreted as Unicode, all languages would be possible but in that case, the maximum number of letters described by 224 bytes would varry.