💾 Archived View for napia.retroforth.org › napia-specification.txt captured on 2023-03-20 at 17:21:38.
⬅️ Previous capture (2023-01-29)
-=-=-=-=-=-=-
# napia specification
napia is a small virtual computer implementing a multicore,
dual stack processor with a simple instruction set, and i/o
devices.
# limitations
Item Size
------------- -------------------------
memory 65,536 cells
data stack 32 numbers
address stack 256 numbers
cell 32-bit signed integer
min value -2147483647
max value 2147483646
cores 10 (8 general, 1 interrupts, 1 solo)
registers 24 per core
# memory model
napia provides a memory space consisting of 32-bit, signed
integer values. The first address is mapped to zero, with
subsequent values following in a strictly linear fashion.
Each addressable 32-bit unit is called a *cell*. There is no
support in the instruction set for accessing values larger or
smaller than a single cell.
# registers
Each processor core maintains an internal `instruction pointer`
register. This document will refer to it as IP. There may also
be internal stack pointers. None of these are directly exposed.
Each processor core also has 24 general purpose registers.
# image file
On startup, napia will load an *image file* ("rom"). This is a
flat, linear sequence of signed integer values. On disk images
are stored in little endian format.
The first value loaded is mapped to address zero, and subsequent
values are loaded to sequential addresses in memory.
An image file does not contain copies of the stacks or any
internal registers.
# endian
The image and block files are stored in little endian format.
# stacks
There are two stacks, one for general data and one for holding
return addresses for calls. The return (or address) stack can
be used to temporarily hold values as well.
Stacks are LIFO (last in, first out).
# instruction set
napia has 40 instructions. In short, these are:
00 00 .. - non-op
01 01 li -n push value in following cell to stack
02 02 du n-nn duplicate top stack item
03 03 dr n- discard top stack item
04 04 sw ab-ba swap top two stack items
05 05 pu n- move top stack item to address stack
06 06 po -n move top address stack item to data stack
07 07 ju a- jump to an address
modifies the instruction pointer
08 08 ca a- call a function
modifies the instruction pointer
09 09 cc af- call a function if the flag is non-zero
modifies the instruction pointer
10 0A cj af- jump to a function if the flag is non-zero
modifies the instruction pointer
11 0B re - return from a call or conditional call
modifies the instruction pointer
12 0C eq ab-f compare two values for equality. a == b
13 0D ne ab-f compare two values for inequality. a != b
14 0E lt ab-f compare two values for less than. a < b
15 0F gt ab-f compare two values for greater than. a > b
16 10 fe a-n fetch a stored value in memory
17 11 st na- store a value into memory
18 12 ad ab-c add two numbers. a + b
19 13 su ab-c subtract two numbers. a - b
20 14 mu ab-c multiply two numbers. a * b
21 15 di ab-cd divide and get remainder. a / b, a % b
22 16 an ab-c bitwise and
23 17 or ab-c bitwise or
24 18 xo ab-c bitwise xor
25 19 sl ab-c shift left. a << b
26 1A sr ab-c shift right. a >> b
27 1B cp sdn-f compare two memory regions
28 1C cy sdn- copy memory
29 1D io n- perform i/o operation
30 1E ic n- initialize a core
31 1F ac an- activate a core, sets core ip to a
32 20 pc n- pause a core
33 21 sc n- resume/start a core
34 22 rr n-n read register n of current core
35 23 wr vn- write value v to regster n of current core
36 24 mx a- run code at address a on solo core
37 25 sv an- set interrupt handler for n to addr. a
38 26 ti n- trigger interrupt n
39 27 si - start handling interrupts
3A 28 hi - halt handling interrupts
A condensed summary table:
Opode Instruction Names Data Stack Effects
===== ================= ====================================
00-05 .. li du dr sw pu - -n n-nn n- nm-mn n-
06-11 po ju ca cc cj re -n a- a- af- af- -
12-17 eq ne lt gt fe st nn-f nn-f nn-f nn-f a-n na-
18-23 ad su mu di an or nn-n nn-n nn-nn nn-n nn-n nn-n
24-29 xo sl sr cp cy io nn-n nn-n nn-n nnn- nnn- n-
30-35 ic ac pc sc rr wr n- an- n- n- n-n vn-
36-40 mx sv ti si hi a- an- n- - -
===== ================= ====================================
And in detail:
--------------------------------------------------------------
00 00 .. - non-op
Does nothing. This is used for padding in instruction bundles.
--------------------------------------------------------------
01 01 li -n push value in following cell to stack
Action is to increment IP, then fetch the value in memory at
IP and place it on the stack. In C:
ip += 1;
stack_push(memory[ip]);
--------------------------------------------------------------
02 02 du n-nn duplicate top stack item
This makes a copy of the top value on the stack, and adds it
to the stack. In C:
sp += 1;
data[sp] = data[sp - 1];
If there is not a value on the stack an underflow occurs. If
there are 32, and overflow occurs.
+--------+-------+
| before | after |
+========+=======+
| | +---+ |
| | | 1 | |
| +---+ | +---+ |
| | 1 | | | 1 | |
| +---+ | +---+ |
| | 2 | | | 2 | |
| +---+ | +---+ |
| | 3 | | | 3 | |
| +---+ | +---+ |
+--------+-------+
--------------------------------------------------------------
03 03 dr n- discard top stack item
In C:
sp -= 1;
If no items are on the stack, an underflow occurs.
+--------+-------+
| before | after |
+========+=======+
| +---+ | |
| | 1 | | |
| +---+ | +---+ |
| | 2 | | | 2 | |
| +---+ | +---+ |
| | 3 | | | 3 | |
| +---+ | +---+ |
+--------+-------+
--------------------------------------------------------------
04 04 sw ab-ba swap top two stack items
a = data[sp];
b = data[sp - 1];
data[sp - 1] = a;
data[sp] = b;
If there are not at least two values on the stack, and
underflow occurs.
+--------+-------+
| before | after |
+========+=======+
| +---+ | +---+ |
| | 1 | | | 2 | |
| +---+ | +---+ |
| | 2 | | | 1 | |
| +---+ | +---+ |
| | 3 | | | 3 | |
| +---+ | +---+ |
+--------+-------+
--------------------------------------------------------------
05 05 pu n- move top stack item to address stack
In C:
rp += 1;
addresses[rp] = data[sp];
sp -= 1;
+--------+-------+
| before | after |
+========+=======+
| +---+ | |
| | 1 | | |
| +---+ | +---+ |
| | 2 | | | 2 | |
| +---+ | +---+ |
| | 3 | | | 3 | |
| +---+ | +---+ |
+--------+-------+
--------------------------------------------------------------
06 06 po -n move top address stack item to data stack
In C:
sp += 1;
data[sp] = addresses[rp];
rp -= 1;
+--------+-------+
| before | after |
+========+=======+
| | +---+ |
| | | 1 | |
| +---+ | +---+ |
| | 2 | | | 2 | |
| +---+ | +---+ |
| | 3 | | | 3 | |
| +---+ | +---+ |
+--------+-------+
--------------------------------------------------------------
07 07 ju a- jump to an address
modifies the instruction pointer
Due to how the execution cycle works (incrementing IP at the
end of the instruction bundle processing), the address needs
to be ajusted to account for this. In C:
ip = data[sp] - 1;
sp -= 1;
--------------------------------------------------------------
08 08 ca a- call a function
modifies the instruction pointer
A call is like the `ju`mp instruction, but adds the original
IP to the address stack. In C:
rp += 1;
address[rp] = ip;
ip = data[sp] - 1;
sp -= 1;
--------------------------------------------------------------
09 09 cc af- call a function if the flag is non-zero
modifies the instruction pointer
Conditional calls are like `ca`lls, but factor in a flag.
In C:
if data[sp] != 0 {
rp += 1;
address[rp] = ip;
ip = data[sp - 1] - 1;
}
sp -= 2;
--------------------------------------------------------------
10 0A cj af- jump to a function if the flag is non-zero
modifies the instruction pointer
Conditional jumps are like `ju`mp, but factor in a flag. In C:
if data[sp] != 0 {
ip = data[sp - 1] - 1;
}
sp -= 2;
--------------------------------------------------------------
11 0B re - return from a call or conditional call
modifies the instruction pointer
In C:
ip = address[rp];
rp -= 1;
--------------------------------------------------------------
12 0C eq ab-f compare two values for equality. a == b
In C:
if (data[sp - 1] == data[sp])
data[sp - 1] = -1;
else
data[sp - 1] = 0;
sp -= 1;
--------------------------------------------------------------
13 0D ne ab-f compare two values for inequality. a != b
In C:
if (data[sp - 1] != data[sp])
data[sp - 1] = -1;
else
data[sp - 1] = 0;
sp -= 1;
--------------------------------------------------------------
14 0E lt ab-f compare two values for less than. a < b
In C:
if (data[sp - 1] < data[sp])
data[sp - 1] = -1;
else
data[sp - 1] = 0;
sp -= 1;
--------------------------------------------------------------
15 0F gt ab-f compare two values for greater than. a > b
In C:
if (data[sp - 1] > data[sp])
data[sp - 1] = -1;
else
data[sp - 1] = 0;
sp -= 1;
--------------------------------------------------------------
16 10 fe a-n fetch a stored value in memory
In C:
data[sp] = memory[data[sp]];
Assuming that memory at 1234 contains 45:
+----------+--------+
| before | after |
+==========+========+
| +------+ | +----+ |
| | 1234 | | | 45 | |
| +------+ | +----+ |
+----------+--------+
--------------------------------------------------------------
17 11 st na- store a value into memory
In C:
memory[data[sp]] = data[sp - 1];
sp -= 2;
+--------+-------+
| before | after |
+========+=======+
| +---+ | |
| | 1 | | |
| +---+ | |
| | 2 | | |
| +---+ | |
+--------+-------+
In this, 1 would be the address, and 2 would be the value to
store there.
--------------------------------------------------------------
18 12 ad ab-c add two numbers. a + b
In C:
data[sp - 1] += data[sp];
sp -= 1;
+--------+-------+
| before | after |
+========+=======+
| +---+ | +---+ |
| | 1 | | | 3 | |
| +---+ | +---+ |
| | 2 | | |
| +---+ | |
+--------+-------+
--------------------------------------------------------------
19 13 su ab-c subtract two numbers. a - b
In C:
data[sp - 1] -= data[sp];
sp -= 1;
+--------+-------+
| before | after |
+========+=======+
| +---+ | +---+ |
| | 4 | | | 5 | |
| +---+ | +---+ |
| | 9 | | |
| +---+ | |
+--------+-------+
--------------------------------------------------------------
20 14 mu ab-c multiply two numbers. a * b
In C:
data[sp - 1] *= data[sp];
sp -= 1;
+--------+-------+
| before | after |
+========+=======+
| +---+ | +---+ |
| | 2 | | | 6 | |
| +---+ | +---+ |
| | 3 | | |
| +---+ | |
+--------+-------+
--------------------------------------------------------------
21 15 di ab-cd divide and get remainder. a / b, a % b
In C:
a = data[sp];
b = data[sp - 1];
data[sp] = b / a;
data[sp - 1] = b % a;
Take two values from the data stack. The top item is the
divisor, and the second item is the dividend. Perform the
division, and push the quotient and remainder to the stack.
After execution the quotient should be on top, with the
remainder below it.
*Division is symmetric, not floored*.
+--------+-------+
| before | after |
+========+=======+
| +---+ | +---+ |
| | 2 | | | 2 | |
| +---+ | +---+ |
| | 5 | | | 1 | |
| +---+ | +---+ |
+--------+-------+
--------------------------------------------------------------
22 16 an ab-c bitwise and
In C:
data[sp - 1] = data[sp - 1] & data[sp];
sp -= 1;
+---------+--------+
| before | after |
+=========+========+
| +----+ | +----+ |
| | -1 | | | -1 | |
| +----+ | +----+ |
| | -1 | | |
| +----+ | |
+---------+--------+
+---------+--------+
| before | after |
+=========+========+
| +----+ | +----+ |
| | 0 | | | 0 | |
| +----+ | +----+ |
| | -1 | | |
| +----+ | |
+---------+--------+
+--------+-------+
| before | after |
+========+=======+
| +---+ | +---+ |
| | 0 | | | 0 | |
| +---+ | +---+ |
| | 0 | | |
| +---+ | |
+--------+-------+
--------------------------------------------------------------
23 17 or ab-c bitwise or
In C:
data[sp - 1] = data[sp - 1] | data[sp];
sp -= 1;
+---------+--------+
| before | after |
+=========+========+
| +----+ | +----+ |
| | -1 | | | -1 | |
| +----+ | +----+ |
| | -1 | | |
| +----+ | |
+---------+--------+
+---------+--------+
| before | after |
+=========+========+
| +----+ | +----+ |
| | 0 | | | -1 | |
| +----+ | +----+ |
| | -1 | | |
| +----+ | |
+---------+--------+
+--------+-------+
| before | after |
+========+=======+
| +---+ | +---+ |
| | 0 | | | 0 | |
| +---+ | +---+ |
| | 0 | | |
| +---+ | |
+--------+-------+
--------------------------------------------------------------
24 18 xo ab-c bitwise xor
In C:
data[sp - 1] = data[sp - 1] ^ data[sp];
sp -= 1;
+---------+-------+
| before | after |
+=========+=======+
| +----+ | +---+ |
| | -1 | | | 0 | |
| +----+ | +---+ |
| | -1 | | |
| +----+ | |
+---------+-------+
+---------+--------+
| before | after |
+=========+========+
| +----+ | +----+ |
| | 0 | | | -1 | |
| +----+ | +----+ |
| | -1 | | |
| +----+ | |
+---------+--------+
+--------+-------+
| before | after |
+========+=======+
| +---+ | +---+ |
| | 0 | | | 0 | |
| +---+ | +---+ |
| | 0 | | |
| +---+ | |
+--------+-------+
--------------------------------------------------------------
25 19 sl ab-c shift left. a << b
In C:
data[sp - 1] = data[sp - 1] << data[sp];
sp -= 1;
The values in these tables are in binary.
+---------------+------------------+
| before | after |
+===============+==================+
| +-----------+ | +--------------+ |
| | 11 | | | 111000111000 | |
| +-----------+ | +--------------+ |
| | 111000111 | | |
| +-----------+ | |
+---------------+------------------+
The results of a negative shift are implementation specific.
--------------------------------------------------------------
26 1A sr ab-c shift right. a >> b
In C:
data[sp - 1] = data[sp - 1] >> data[sp];
sp -= 1;
The values in these tables are in binary.
+------------------+---------------+
| before | after |
+==================+===============+
| +--------------+ | +-----------+ |
| | 11 | | | 111000111 | |
| +--------------+ | +-----------+ |
| | 111000111000 | | |
| +--------------+ | |
+------------------+---------------+
The results of a negative shift are implementation specific.
--------------------------------------------------------------
27 1B cp sdn-f compare two memory regions
In C:
len = data[sp];
dest = data[sp - 1];
src = data[sp - 2];
flag = -1;
while (len) {
if (memory[dest] != memory[src]) flag = 0;
len -= 1;
src += 1;
dest += 1;
};
sp -= 2;
data[sp] = flag;
--------------------------------------------------------------
28 1C cy sdn- copy memory
In C:
len = data[sp];
dest = data[sp - 1];
src = data[sp - 2];
while (len) {
memory[dest] = memory[src];
len -= 1;
src += 1;
dest += 1;
};
sp -= 3;
--------------------------------------------------------------
29 1D io n- perform i/o operation
I/O operations are somewhat dependent on the underlying host.
I/O Device Action
---------- -----------------------------------------
0 Display a character. Consumes a character
from the stack.
1 Read a character from the input device.
Character is pushed to the stack.
2 Read a block into memory.
3 Write memory to a block.
4 Write all memory to an image/rom.
5 Reload the image/rom, and jump to address 0.
Also resets the stack pointers to empty.
6 End execution. On a hosted system, exit napia.
If native, suspend execution.
7 Obtain stack depths. Pushes the data depth then
the address depth.
8 Return current time as a unix timestamp
I/O numbers below 64 are reserved. For custom I/O extensions,
use a number 64 or above.
--------------------------------------------------------------
30 1E ic n- initialize a core
Initialize a processor core. This will zero out all internal
registers and empty the stacks.
--------------------------------------------------------------
31 1F ac an- activate a core, sets core ip to a
Set the IP of a core (n) to address (a). This does not alter
the stacks or registers.
--------------------------------------------------------------
32 20 pc n- pause a core
Pause a core.
--------------------------------------------------------------
33 21 sc n- resume/start a core
Resume a paused core.
--------------------------------------------------------------
34 22 rr n-n read register n of current core
Read register n (0-23) of the current core, and push the value
to the stack.
--------------------------------------------------------------
35 23 wr vn- write value v to regster n of current core
Write value (v) to register n (0-23) on the current core.
--------------------------------------------------------------
36 24 mx a- run code at address a on a solitary core
Force a piece of code to run in a single core, suspending
switching cores until done. (Does not affect interrputs)
--------------------------------------------------------------
37 25 sv an- set interrupt handler for n to addr. a
Set the handler for interrupt n to function at address a.
--------------------------------------------------------------
39 26 ti n- trigger interrupt n
Trigger execution of interrupt handler for interrupt n.
--------------------------------------------------------------
39 27 si - start handling interrupts
Allow processing of interrupts to begin.
--------------------------------------------------------------
3A 28 hi - halt handling interrupts
Suspend processing of interrupts.
--------------------------------------------------------------
# instruction bundling
napia allows up to four instructions to be packed into a single
memory location. These are processed in order. Instructions that
modify the instruction pointer (other than `li`) can not be
followed by anything other than a non-op to avoid unpredictable
behavior.
Instructions are unpacked from right to left. E.g., in C, the
instruction processor can be written like:
void process_opcode_bundle(int opcode) {
process(opcode & 0xFF);
process((opcode >> 8) & 0xFF);
process((opcode >> 16) & 0xFF);
process((opcode >> 24) & 0xFF);
}
Where `process()` takes and executes a single instruction.
# instruction processing
IP is set to zero, and execution begins. For each cycle, the
opcode bundle at IP in memory is executed. At the end of each
cycle, IP is incremented. Execution ends if IP exceeds the
length of memory. In C:
while(ip < 65536) { process_opcode_bundle(memory[ip++]); }
A stack guard is run before each instruction. This ensures that
the data stack contains the correct number of items for the
instruction, and that enough space will remain to hold any
values pushed. The address stack is also checked.
If the data stack over or underflows, the stack pointer is set
to zero (emptying the stack) and an interrupt is triggered. For
the address stack, the address stack pointer is *not* reset.
# block storage
A generic block storage device is provided.
Each block is 1,024 memory cells (4,096 bytes) in length.
Reading a block:
- push the block number
- push an address of the buffer in memory that will hold the
block contents after the read completes
- push the value 2 (read block contents) to the stack
- call I/O operation via the `io` instruction
Writing a block:
- push the block number
- push an address of the buffer in memory that holds the
data to write to the block
- push the value 3 (write block contents) to the stack
- call I/O operation via the `io` instruction
# block file format
An implementation of napia is free to choose the best approach
to implementing the actual block storage. For the reference
model, a flat file is used, with each block being stored
sequentially.
To locate a block, multiply the block number by 4096 and seek
that offset into the file. Then read or write 4096 bytes,
packing or unpacking from memory as needed.
As with the image, the block file in the reference model is
stored in little endian format.
# multicore
The processor has nine cores. One is dedicated to processing
interrupts, the other eight are available to the user.
Execution occurs in a simple round-robin fashion, with each
active core processing one instruction bundle before control
is transferred to the next active core. Suspended cores are
skipped.
# interrupts
During processing of an interrupt, all interrupts are disabled
and only the interrupt core is active. Interrupt handlers are
best kept short and focused.
| 000 | System Cycyle |
| 001 | Data Stack Underflow |
| 002 | Data Stack Overflow |
| 003 | Address Stack Underflow |
| 004 | Address Stack Overflow |
| 005 | Invalid Memory Access |
| 006 | Division by Zero |
| 007 | |
| 008 | |
| 009 | |
| 010 | |
| 011 | |
| 012 | |
| 013 | |
| 014 | |
| 015 | |
| 016 | |