# 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.

  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 89 90 91 92 93 94 95 96 # 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.

  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 89 90 91 92 93 # 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?

  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 89 90 91 92 93 94 95 96 97 98 99 # 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?

  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 # 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?

  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 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 # 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.

  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 89 90 91 92 93 94 95 96 97 98 99 100 # 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:

  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 # 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:

  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 # 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.