tinystack: a stack-based microcode
Tinystack's distinguishing feature is its short instruction length - 4 bits.
Tinystack's memory is arranged as 32768 words of 2 bytes each. By packing 4
instructions per word, it's possible to spend only one of every four cycles
fetching instructions from memory. The first three instructions of each word
may load values from or store values in memory, but the fourth is reserved
for fetching the next set of instructions.
Tinystack is big-endian - the nibbles 4 5 b f represent the number 0x45bf
0x558 0x559
| --- one byte -- || --- one byte -- |
+----+----+----+----++----+----+----+----+
| Q1 | Q2 || Q3 | Q4 |
+----+----+----+----++----+----+----+----+
| ------------- one word --------------- |
Tinystack contains two stacks, the second of which is called the stash.
The stash can hold general-purpose data but arithmetic can only be performed
on the top two elements of the stack. Data can be moved between the stack and
the stash with the save and rstor instructions.
By convention, the top of the stack and the element below it are sometimes
referred to as x and y respectively.
Stack manipulation instructions:
swap - swap the top two stack elements 1 2 -> 2 1
dup - duplicate the top stack element: 1 2 -> 1 2 2
disc - discard the top stack element 1 2 -> 1
save - remove the top stack element and push it onto the stash
rstor - remove the top stash element and push it onto the stack
lit - push literal nibble
Sequential lits build up a constant at the top of the stack
nibble by nibble, from least significant to most significant.
A command that isn't a lit interrupts this, and when four
nibbles have been pushed, the next call to lit will start the
sequence again.
lit 3 -> 0x0003 lit 5 -> 0x0005
lit 5 -> 0x0053 lit 6 -> 0x0065
dup -> 0x0053 0x0053 lit 4 -> 0x0465
lit 2 -> 0x0053 0x0053 0x0002 lit 2 -> 0x2465
lit 0 -> 0x0053 0x0053 0x0002 lit 7 -> 0x2465 0x0007
Arithmetic instructions:
add - add the top two stack elements and leave the result on the stack
4 5 -> 9 65500 100 -> 64 (mod 2^16)
rol - rotate the bits of y by x places
1 2 -> 4 6 15 -> 3
nand - nand the top two stack elements and leave the result there
4 5 -> 65531 65500 100 -> 65467
sign - smear the high bit across the top of the stack. That is, if the
high bit is 1, the top of the stack will be 0xffff. Otherwise,
it will become 0x0000. This can be used to implement conditional
jumps
Memory instructions:
There are some details about how these handle writing to byte addresses
despite memory arranged in words, but they will be written up later.
Memory operations cannot occur as the last instruction of a word.
ld - acts like "x = *x". Replaces the top value with the value at the
address to which it points.
st - acts like "*x = y; x = y". Stores the second value at the
address pointed to by the top of the stack. Then discards
the top of the stack.
Control flow:
nop - do nothing
call - 1. pop an address from the top of the stack
2. push IP + 1 onto the stack
3. execute the next instruction normally
4. continue execution starting at the address popped earlier
skip - 1. pop an offset from the top of the stack
2. execute the next instruction normally
3. continue execution starting at IP + 1 + offset
The skip instruction has no effect on flow when the top of
the stack is zero.
The behavior of a call or skip in the delay slot following another
call or skip is not defined.
And that's it. This is definitely Turing-complete but organizing useful
programs requires careful attention to the layout of the stack and stash.
A sample program to compute the Fibonacci sequence is included as fib.s, and
its assembled output is included as fib.tsb.
Run this with:
./uasm.py fib.s | ./tinystack_emu.py
A disassembler is also included: udisasm.py