/tinystack

A 4 bit instruction set for a stack architecture

Primary LanguagePython

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