The two things software cannot check by reading its own source are the 3 bit
packing and the bracket strategy, so both got a tool and a test.
New in the library (r8forge/tape.hh, src/tape.cc): the opcode numbering (taken
from ROT-8-viz enum, so the packed image and the hardware decoder cannot drift),
text <-> opcodes, opcodes <-> 3 bit bytes, the .r8t image with its trailer and
crc32, and a machine model that runs a packed tape the way a board would. The
model takes the bracket strategy as an option: backward scan with loop stack or
not, and jump-back-onto-the-[ (the contract) or past it (what the interpreters
do). All four combinations print the same thing, and the step count differs by
exactly the number of taken ] instructions -- which is what the test asserts.
Found and fixed while writing it: the loop stack discipline depends on the jump
convention. Jumping onto the [ means the [ re-pushes, so ] must pop on the jump;
jumping past it means the entry must stay until the loop exits. Mixing them up
emptied the stack on the second iteration of the calculator main loop -- caught
by the equivalence test on examples/calc.r8asm, not by reading the code.
Tools: r8forge_tape_pack (text tape -> image + --hex for $readmemh + --verify,
727 instructions become 273 bytes for hello, 62%, and the trailer sits past the
halt so address 0 of a ROM is instruction 0), and r8forge_tape_run now reads an
image directly and takes --loop-stack / --retest.
hardware/rot8.v: the 8 bit / 64 cell machine -- 3 bit opcodes from a byte
addressed memory read as a 16 bit window, a 6 bit dp with free wrap, the loop
stack bracket jump, blocking input, halt on ip == length, and a step counter that
counts instructions rather than cycles. hardware/tb_rot8.v loads a --hex image
and prints the OUT stream in tape_run format.
Verified with Icarus Verilog 14 (the RTL against tape_run --loop-stack --retest):
hello 577 instructions 417 steps 10 outs
term 16414 17643 11 (fed "lhi")
calc 51378 166741 19 (fed "12 34 + .": prints the prompt,
046 and the next prompt)
flagship 43676 100142 93
Every OUT stream identical. ctest -R rtl_sim runs that comparison from an 8 bit
build (11 tests in the default build now, where the RTL test self-skips because
the RTL is the 8 bit machine).
Two traps worth remembering: Icarus passes plusargs through as raw bytes, so an
absolute +HEX path containing non-ASCII (this checkout is under a Chinese
directory name) arrives mangled, $readmemh silently leaves the memory empty and
the machine obediently runs LEN steps of opcode 0 printing nothing -- run vvp
from the directory holding the hex with a relative name. And in_ready must not
be qualified with !in_valid or the input handshake deadlocks.
219 lines
8.1 KiB
Verilog
219 lines
8.1 KiB
Verilog
// ROT-8, the machine.
|
|
//
|
|
// Eight instructions, three bit opcodes packed into a byte addressed program
|
|
// memory, a 64 cell by 8 bit data ring, and -- this is the part the software
|
|
// cannot check -- the hardware bracket strategy: a LIFO of loop entry positions
|
|
// instead of a backward scan, jumping back *onto* the '[' so it re-tests.
|
|
//
|
|
// * program memory is read as a 16 bit window (two byte reads), because a three
|
|
// bit instruction can straddle a byte boundary. A real board does this with
|
|
// a 16 bit wide ROM, two ROMs, or a shift register; the interface is written
|
|
// as two reads so all three are countable.
|
|
// * the data ring is 64 cells, so `dp` is a 6 bit counter whose wrap is free.
|
|
// * `,` blocks: `in_ready` goes high and the machine does not advance until
|
|
// `in_valid` is seen. Reading zero has to be an explicit event (`in_valid`
|
|
// with `in_data` zero), otherwise an idle keyboard would feed the program a
|
|
// stream of EOFs.
|
|
// * the step counter counts instructions, not cycles, and a bracket jump costs
|
|
// exactly one step -- the scan and the LIFO bookkeeping are free, which is
|
|
// what keeps the hardware's step counts comparable with the interpreters
|
|
// (see `--loop-stack --retest` in r8forge_tape_run).
|
|
//
|
|
// Opcodes, in the order the assembler packs them (ROT-8-viz's enum):
|
|
// 0 '>' STP 1 '<' BTP 2 '+' ROR 3 '-' FLB
|
|
// 4 '[' BIZ 5 ']' RNZ 6 '.' OUT 7 ',' INP
|
|
//
|
|
// This file is the executable spec of the board. It has not been run yet: there
|
|
// is no Verilog simulator on the development machine, so hardware/README.md says
|
|
// how to run it and what to compare it against once one is available.
|
|
`default_nettype none
|
|
|
|
module rot8 #(
|
|
parameter integer WIDTH = 8, // bits per data cell
|
|
parameter integer RING = 64, // data cells (power of two: free wrap)
|
|
parameter integer IPW = 16, // instruction pointer width
|
|
parameter integer STACKW = 4 // loop stack depth: 2^STACKW entries
|
|
) (
|
|
input wire clk,
|
|
input wire rst_n,
|
|
input wire run, // 1: free run, 0: halted between steps
|
|
input wire step, // one instruction while run is 0
|
|
|
|
// program memory: two byte reads at prog_addr0 / prog_addr1
|
|
output wire [IPW-1:0] prog_addr0,
|
|
output wire [IPW-1:0] prog_addr1,
|
|
input wire [7:0] prog_data0,
|
|
input wire [7:0] prog_data1,
|
|
input wire [IPW-1:0] prog_len, // instruction count: ip == prog_len halts
|
|
|
|
// input: blocks until in_valid, one byte per ','
|
|
input wire in_valid,
|
|
input wire [7:0] in_data,
|
|
output wire in_ready,
|
|
|
|
// output: one cycle pulse per '.'
|
|
output reg out_valid,
|
|
output reg [7:0] out_data,
|
|
|
|
// debug / panel
|
|
output reg [IPW-1:0] ip,
|
|
// $clog2 rather than DPW here: a localparam declared in the body is not in
|
|
// scope in the port list, and the width has to be a constant expression
|
|
output reg [$clog2(RING)-1:0] dp,
|
|
output reg [31:0] steps,
|
|
output reg halted
|
|
);
|
|
|
|
localparam integer DPW = $clog2(RING);
|
|
|
|
localparam [2:0] OP_STP = 3'd0, OP_BTP = 3'd1, OP_ROR = 3'd2, OP_FLB = 3'd3;
|
|
localparam [2:0] OP_BIZ = 3'd4, OP_RNZ = 3'd5, OP_OUT = 3'd6, OP_INP = 3'd7;
|
|
|
|
localparam [1:0] S_FETCH = 2'd0, S_SCAN = 2'd1, S_HALT = 2'd2;
|
|
|
|
reg [1:0] state;
|
|
reg [WIDTH-1:0] cells [0:RING-1];
|
|
reg [IPW-1:0] stack [0:(1<<STACKW)-1];
|
|
reg [STACKW-1:0] sp;
|
|
|
|
// ---- fetch ----------------------------------------------------------------
|
|
// instruction ip starts at bit 3*ip of the byte stream
|
|
wire [IPW+1:0] bit_index = ip * 3;
|
|
wire [IPW-1:0] byte_index = bit_index >> 3;
|
|
wire [2:0] bit_offset = bit_index[2:0];
|
|
wire [15:0] window = {prog_data1, prog_data0};
|
|
wire [2:0] op_now = (window >> bit_offset) & 16'h0007;
|
|
|
|
assign prog_addr0 = byte_index;
|
|
assign prog_addr1 = byte_index + 1'b1;
|
|
// in_ready means "the byte I am waiting for would be taken this cycle". It
|
|
// must NOT be qualified with !in_valid: a producer then never sees the
|
|
// acceptance edge and the handshake deadlocks (the first testbench did exactly
|
|
// that and hello, which reads nothing, was the only tape that could run).
|
|
assign in_ready = (state == S_FETCH) && (op_now == OP_INP);
|
|
|
|
// forward depth counter for the '[' skip
|
|
reg [STACKW:0] scan_depth;
|
|
|
|
integer i;
|
|
always @(posedge clk or negedge rst_n) begin
|
|
if (!rst_n) begin
|
|
state <= S_FETCH;
|
|
ip <= {IPW{1'b0}};
|
|
dp <= {DPW{1'b0}};
|
|
sp <= {STACKW{1'b0}};
|
|
steps <= 32'd0;
|
|
halted <= 1'b0;
|
|
out_valid <= 1'b0;
|
|
out_data <= 8'd0;
|
|
scan_depth <= {(STACKW+1){1'b0}};
|
|
for (i = 0; i < RING; i = i + 1)
|
|
cells[i] <= {WIDTH{1'b0}};
|
|
end else begin
|
|
out_valid <= 1'b0;
|
|
|
|
// ip == prog_len is the halt: the tape ran off its end
|
|
if (ip >= prog_len) begin
|
|
halted <= 1'b1;
|
|
state <= S_HALT;
|
|
end
|
|
|
|
case (state)
|
|
S_FETCH: begin
|
|
if (!halted && (ip < prog_len) && (run || step)) begin
|
|
case (op_now)
|
|
OP_STP: begin
|
|
dp <= (dp == RING - 1) ? {DPW{1'b0}} : dp + 1'b1;
|
|
ip <= ip + 1'b1;
|
|
end
|
|
OP_BTP: begin
|
|
dp <= (dp == 0) ? (RING - 1) : dp - 1'b1;
|
|
ip <= ip + 1'b1;
|
|
end
|
|
OP_ROR: begin
|
|
cells[dp] <= {cells[dp][0], cells[dp][WIDTH-1:1]};
|
|
ip <= ip + 1'b1;
|
|
end
|
|
OP_FLB: begin
|
|
cells[dp][0] <= ~cells[dp][0];
|
|
ip <= ip + 1'b1;
|
|
end
|
|
OP_BIZ: begin
|
|
if (!cells[dp][0]) begin
|
|
// skip forward to the matching ']', then past it
|
|
scan_depth <= {{STACKW{1'b0}}, 1'b1};
|
|
state <= S_SCAN;
|
|
ip <= ip + 1'b1;
|
|
end else begin
|
|
// entering the loop: remember where it starts
|
|
stack[sp] <= ip;
|
|
sp <= sp + 1'b1;
|
|
ip <= ip + 1'b1;
|
|
end
|
|
end
|
|
OP_RNZ: begin
|
|
if (cells[dp][0]) begin
|
|
// jump back ONTO the '[' (it re-tests, and re-pushes), so the
|
|
// entry is popped here
|
|
if (sp != 0) begin
|
|
ip <= stack[sp - 1'b1];
|
|
sp <= sp - 1'b1;
|
|
end else begin
|
|
// ']' with nothing entered: a malformed tape. Halt rather
|
|
// than index below the stack.
|
|
halted <= 1'b1;
|
|
state <= S_HALT;
|
|
end
|
|
end else begin
|
|
if (sp != 0)
|
|
sp <= sp - 1'b1; // the loop finished
|
|
ip <= ip + 1'b1;
|
|
end
|
|
end
|
|
OP_OUT: begin
|
|
out_valid <= 1'b1;
|
|
out_data <= cells[dp];
|
|
ip <= ip + 1'b1;
|
|
end
|
|
OP_INP: begin
|
|
if (in_valid) begin
|
|
cells[dp] <= in_data[WIDTH-1:0];
|
|
ip <= ip + 1'b1;
|
|
end
|
|
// else: hold every register; in_ready is already high
|
|
end
|
|
default: ip <= ip + 1'b1;
|
|
endcase
|
|
// a held ',', a scan or a halt does not count as an instruction
|
|
if (op_now != OP_INP || in_valid)
|
|
steps <= steps + 32'd1;
|
|
end
|
|
end
|
|
|
|
S_SCAN: begin
|
|
// one opcode per cycle: forward only, and free (it is not a step)
|
|
if (run || step) begin
|
|
if (op_now == OP_BIZ)
|
|
scan_depth <= scan_depth + 1'b1;
|
|
else if (op_now == OP_RNZ)
|
|
scan_depth <= scan_depth - 1'b1;
|
|
ip <= ip + 1'b1;
|
|
if (op_now == OP_RNZ && scan_depth == 1) begin
|
|
state <= S_FETCH; // ip now points past the matching ']'
|
|
end
|
|
end
|
|
end
|
|
|
|
S_HALT: begin
|
|
halted <= 1'b1;
|
|
end
|
|
|
|
default: state <= S_FETCH;
|
|
endcase
|
|
end
|
|
end
|
|
|
|
endmodule
|
|
|
|
`default_nettype wire
|