A working RV32I interpreter expressed as a chain of Analytical Engine cards, plus a simulator of the engine to run it on and a Babbage-rate cost model.
You write C, a real RISC-V compiler compiles it, and the resulting program is interpreted by a chain of punched cards fed through a simulated Victorian machine that was never built. The engine then tells you how many seconds of steam it would have taken.
The sieve of Eratosthenes, filling 93% of the Store. The throttle is open past a million to one, so a second of watching costs the engine a fortnight.
engine/ae.py the machine: Store, mill, levers, card set, assembler, costs
engine/rv32.py the RV32I interpreter, written in cards
engine/demo.py RV32 assembler + 19 instruction tests
engine/bench.py per-instruction cost, index ablation, extrapolation
programs/engine.h the whole C runtime: put, emit, decimal formatting
programs/hello.c hello world, printing through the print card
programs/fib.c a fib table plus a recursive cross-check, 60k instructions
programs/sieve.c a sieve filling 93% of the Store, the one to watch
programs/crt0.S startup: set sp, call main, halt the mill
programs/link.ld link flat at address 0 inside the 3440 bytes of Store
build.sh C -> flat RV32I image, checked for unsupported opcodes
runc.py load an image into the Store and run it
gui.py serve the engine to a browser and drive it live
gui/index.html the brass, the gauges and the steam
docs/engine.gif the panel in motion
build/ everything generated (gitignored)
The simulator is pure Python 3 with no dependencies, so the tests and the benchmark work out of the box:
python3 -m engine.demo # 19/19, incl. fib(10)=55 and an array-sum loop
python3 -m engine.bench # per-instruction costs; writes build/cards.txt
Compiling C needs a RISC-V cross-compiler with an rv32i/ilp32 multilib. On
macOS:
brew install riscv64-elf-gcc
Then:
./build.sh # programs/hello.c -> build/hello.bin
python3 runc.py # runs build/hello.bin
./build.sh fib # programs/fib.c -> build/fib.bin
python3 runc.py build/fib.bin
./build.sh sieve && python3 runc.py build/sieve.bin
build.sh takes a bare name (fib), a filename (fib.c) or a path, and
refuses to emit an image the card chain cannot decode. Check the toolchain has
the right multilib with riscv64-elf-gcc -print-multi-lib | grep rv32i.
./build.sh && python3 gui.py
./build.sh sieve && python3 gui.py build/sieve.bin
It prints a link rather than opening anything; paste it into Google Chrome, which is what the panel was built and checked against.
A brass-and-mahogany front panel: the Store as a thousand figure wheels that flare as they are written, the Mill with its flywheel and its two ingress axes, the SGN and RUN levers, the card chain scrolling under the reader, a pressure gauge counting steam consumed, and the printing apparatus. Steam vents off the mill and thickens as the machine is worked harder.
The throttle sits beside the title, so it stays on screen. At its left stop the engine runs at 1x -- Babbage's own rate, one card every tenth of a second, about ten minutes to an emulated instruction; you can watch individual cards go by. At its right stop it is unthrottled and the whole of hello world -- 16,416 cards -- is over before the page can redraw. In between it is logarithmic, spanning some seven orders of magnitude, and the steam thickens with it.
Pacing is by engine-seconds rather than by cards, because a division costs six
hundred times what a card feed does; counting cards would make arithmetic look
free. The engine still runs in Python, through the same step_chain() the
benchmark uses, so there is no second implementation of the machine and
nothing to install -- gui.py is http.server and one HTML file.
build.sh drives riscv64-elf-gcc -march=rv32i -mabi=ilp32 and objcopies the
result to a flat image; runc.py lays that image in the Store from column 140,
sets pc to 0, and feeds the chain. Hello world compiles to 75 bytes, 79
instructions:
Hello, world!
RV32 instructions 79
mill operations 3,514 (add 1,654 sub 1,310 div 550)
on the engine 895 min (53,713 s of steam)
on this machine 2.3 ms
Fifteen hours of steam for fourteen characters. Note that the two times are unrelated: the seconds are what Babbage's machine would have taken, counted from the mill operations and the cards fed. The simulator itself runs at about 30,000 emulated instructions per second.
The ABI is two calls. ecall with a7=1 lays a0 on the output apparatus, one
value per character; a7=93 halts. There is no libc, no stack unwinding, and no
.bss clearing -- the Store comes up as a thousand columns of zero, and a
clearing loop would cost minutes per word for no effect.
Because a TRAP card halts with no diagnostic, build.sh greps the
disassembly for anything the chain cannot decode (M/A/F/D, halfword access,
FENCE, CSR) and refuses to emit an image that would die silently.
fib.c is the larger example: a table of fib(0..24) and a naive recursive
fib(16), about three thousand calls, checked against the iterative answer so
that every jal, jalr, sw and lw in the chain has to be right.
RV32 instructions 60,775
mill operations 3,024,197 (add 1,497,593 sub 973,606 div 552,885)
on the engine 568 days (49,055,359 s of steam)
on this machine 1,976.7 ms
Over half those mill operations are divisions, and they are the whole story of
the cost: RV32I has no divide instruction, so printing a number in decimal
calls into libgcc's __udivsi3, which the engine then services with its own
one-minute division. Linking -lgcc is what makes ordinary C arithmetic work
on a machine that lacks it.
sieve.c is built to use very nearly all of the machine. Its byte array is
sized so that code, data and stack together come to 93% of the 3440 bytes:
text 911 data 0 bss 2320 footprint 3231 of 3440 (93%)
209 bytes left for the stack
sieve of eratosthenes, 2 to 2319
2 3 5 7 11 13 17 19 23 29 31 37
41 43 47 53 59 61 67 71 73 79 83 89
...
344 primes below 2320, the largest 2311.
build.sh reports that footprint rather than the image size, because .bss
costs Store columns without appearing in the flat binary at all. Static data
grows up and the stack grows down, and nothing on this machine will tell you
when they meet -- a smashed stack just runs the chain into nonsense -- so
link.ld asserts that a gap survives and refuses the link otherwise.
It is also the program worth watching in gui.py. The inner loop strides
through the RAM region at the interval of whichever prime is being crossed
off, so the figure wheels light every second column, then every third, then
every fifth, the stride widening as the primes thin out.
The sieve never multiplies. It carries i*i forward by addition instead, since
(i+1)^2 = i^2 + 2i + 1, and RV32I would otherwise call libgcc's __mulsi3 on
every iteration -- the difference between minutes and hours of steam.
Store of 1000 columns x 50 signed decimal digits. Mill with two ingress axes, one egress axis, one secondary egress (remainder), and two levers: SGN (egress negative) and RUN (ran up past 50 digits). Control is a card chain; combinatorial cards advance or reverse it by a punched constant, optionally on a lever.
Cost model uses Babbage's own estimates: ~1 s for a 50-digit addition, ~60 s for a multiplication or division, 0.1 s per card fed.
Indexed variable cards (*V7 in the listing) resolve their column number
through the Store. This is NOT in Babbage's design -- variable cards carry
absolute column numbers punched in cardboard, and there is no dereference.
Run with price_linear=True to charge the unmodified engine's cost instead:
resolving V[V[k]] by scanning the Store, one subtraction and two combinatorial
cards per column.
An RV32 word is a plain decimal integer 0..2^32-1 in one column. The alternative -- one bit per decimal digit -- makes AND/OR cheap but destroys arithmetic. Decimal magnitude wins because RISC-V field extraction becomes five successive mill divisions:
q1, opcode = divmod(ir, 2^7)
q2, rd = divmod(q1, 2^5)
q3, funct3 = divmod(q2, 2^3)
q4, rs1 = divmod(q3, 2^5)
f7, rs2 = divmod(q4, 2^5)
and q4 falls out as the unsigned I-type immediate for free. Left shifts are repeated addition (k seconds for a shift of k, against 60 for a multiply). Only AND/OR/XOR between two arbitrary registers stay dear: 32 iterations of two divisions each.
0..31 x0..x31 (x0 held at zero, doubles as the zero column)
32 pc
33..89 interpreter temporaries
90..139 constants
140..999 emulated RAM, 860 words = 3440 bytes of RV32 address space
Not implemented: FENCE, CSR, M/A/F/D, LH/LHU/SH, misaligned access.