Origin & motivation: see
compression_intelligence.md(the Hutter-Prize thesis this build log descends from). Research directions: seeresearch_roadmap.md. Reasoned evolution: seedesign_evolution.md.
Implemented the call stack (software stack of return addresses, returned via
j @reg) and a C-borrowed function language (int f(int a, int b) { … }),
compiled by cc.py to copyjump with synthesized arithmetic (adder/subtractor/
comparators from gates — no ALU). See callstack_language.md.
Verified: sum(3,5)→8; countdown(5)→[5,4,3,2,1] (recursion); sum(255,1)
→0 (8-bit overflow). Limitation (v1): non-tail recursion needs callee-saved
registers. See design_evolution.md §10.
Built the first data structure on the substrate: a stack — a 13-bit stack
pointer + poke (push) / peek (pop), with ripple increment/decrement for the
pointer. stack_demo_gen.py → program_stack_demo.prg.txt (push 0,1,1, pop
→ [1, 1, 0]), verified. See design_evolution.md §9.
Shared the remaining fixed-address bodies (register rotation A=D,D=C,C=B,B=BNEW
×64 → one body; left-rotate → 16 bodies by shift amount). program_md5.prg.txt:
36,865 → 28,272 instructions (~9× smaller than the original 260,996).
Also recorded a negative result: the “collapse the 64 rounds into a loop”
step is a non-optimization here — in a no-ALU machine, immediate constants beat
data tables (a loop needs table init + peek + address arithmetic, which costs
more than the immediates it replaces). See design_evolution.md §8.
Extended CopyJumpMachine.py with indirect addressing: an operand prefixed
with @ is dereferenced (the 13-bit value at that address is the actual
address) — m dst @src (peek), m @dst src (poke), j @reg (computed goto).
Added as an addressing mode, not a new opcode, so the machine stays OISC /
URISC. Verified by program_indirect_demo.prg.txt (peek + poke) and a
computed-goto check; MD5 and the outliner demos still pass (no regression).
This makes pointers expressible — the primitive that unlocks arrays, heap, stacks, call-stacks (recursion), and linked structures, all built in software.
Continuing the reuse-aware codegen: the F/G/H/I round functions (fixed
addresses B, C, D → F) are now shared as 4 subroutines, called 16× each —
like add32. program_md5.prg.txt: 65,637 → 36,865 instructions
(47,326 lines), still verified against hashlib (all RFC 1321 vectors).
Cumulative: 260,996 → 65,637 (add32) → 36,865 (add32 + round function), ~7× smaller than the original inlined program, entirely from source-level reuse.
The MD5 generator now emits shared add32 subroutines instead of inlining
the ~769-instruction body 260 times. Each distinct (dst, a, b) signature is
written once (fixed addresses) and called via a return register + dispatch tree
— source-level reuse, no post-hoc detection.
program_md5.prg.txt: 260,996 → 65,637 instructions (~4× smaller),
375,758 → 89,893 lines.hashlib (all RFC 1321 vectors).This is the “generator should be aware of the optimizations from the start”
idea — the generator knows its patterns by name, so it never emits the
duplicated code in the first place (vs. outliner.js, which rediscovers
duplication post-hoc in code it didn’t generate).
A Node rewriter (vm_programs/outliner.js) that turns inlined copy+jump code
into shared subgraphs — the inverse of inlining, implementing strategy 2 from
docs/reuse_graphs_paths.md (return register + dispatch tree, no call stack).
.prg.txt → instructions + labels.j conditions are distinguished from jump targets).⌈log₂N⌉ bits) + jumps in; a dispatch tree at the body exit routes back.vm_programs/verify_outliner.py runs original vs rewritten under
CopyJumpMachine.py and asserts identical output bits.
program_integer_sum.prg.txt: 29-instruction full adder inlined 7× →
233 → 94 instructions (−139), bit-identical on 5 inputs (incl. carry).program_inline_demo.prg.txt (synthetic): 8-instruction body × 4 →
44 → 36 instructions (−8), bit-identical.vm_programs/outliner.js — the rewriter (Node).vm_programs/verify_outliner.py — semantic-equivalence checker.vm_programs/program_inline_demo.prg.txt (+ .outlined.prg.txt) — demo.vm_programs/program_integer_sum.outlined.prg.txt — outlined full adder.cin 0 vs 4) are v2.RET_BASE (default 8000) must not collide with the program’s own data.reuse_graphs_paths.md for the full measured-results table and the cost
model (when reuse actually shrinks a program).Full MD5 computed entirely from copy+jump primitives, executed by the
“pythonic runner” vm_programs/CopyJumpMachine.py.
| File | Role |
|---|---|
vm_programs/md5_gen.py |
generator: emits program_md5.prg.txt |
vm_programs/program_md5.prg.txt |
generated MD5 program (65,637 instructions) |
vm_programs/md5_reference.py |
expected digests via hashlib |
vm_programs/md5_check.py |
runs the program in the VM and diffs vs hashlib |
vm_programs/md5.md |
design notes (memory layout, primitives, round structure) |
Every MD5 operation is lowered to bit-level copy+jump code:
j <bit> <label>).sum = a⊕b⊕cin, carry = (a&b) | ((a⊕b)&cin)), 5 adds per round.mod 16 arithmetic at runtime).The standard MD5 structure is followed: per round compute F/G/H/I(B,C,D),
then F += A + K[i] + M[g], B += leftrotate(F, s[i]), rotate registers
A=D, D=C, C=B, and finally add the initial constants back
(a0 += A, b0 += B, c0 += C, d0 += D). Bits are LSB-first throughout.
python3 vm_programs/md5_check.py → PASS against hashlib:
b"" → d41d8cd98f00b204e9800998ecf8427eb"abc" → 900150983cd24fb0d6963f7d28e17f72b"hello" → 5d41402abc4b2a76b9719d911017c592b"The quick brown fox jumps over the lazy dog" → 9e107d9d372bb6826bd81d3542a419d6Also verified through the CLI entry point
(python3 vm_programs/CopyJumpMachine.py vm_programs/program_md5.prg.txt),
which emits the 16 digest bytes LSB-first.
python3 vm_programs/md5_reference.py # expected digests
python3 vm_programs/md5_gen.py # (re)generate the program
python3 vm_programs/md5_check.py # run in VM + diff vs hashlib
python3 vm_programs/CopyJumpMachine.py vm_programs/program_md5.prg.txt
Change the embedded message by editing MESSAGE at the top of
md5_gen.py, then re-running the generator.
len(message) < 56 bytes). Multi-block MD5
would need a block loop and running-state chaining across blocks.1024+31 for INIT_D, plus scratch bits at 8000..8003)..cj numeric export is intentionally not generated (the Python runner
executes the textual format directly).resm_bbjj.md.All five stages are complete and verified.
CopyJumpMachine.py — no export)| Stage | File | Result |
|---|---|---|
| 1. XOR gate | vm_programs/program_xor_gate.prg.txt |
✅ 4/4 truth-table cases pass |
| 2. Reference xorshift32 | vm_programs/xorshift32_reference.py |
✅ outputs match expected |
| 3. Countdown loop-count | vm_programs/program_countdown.prg.txt |
✅ counts 10 → 1, terminates |
| 4. One number from seed | vm_programs/program_xorshift32_step.prg.txt |
✅ 0x87985AA5 |
| 5. N numbers in loop | vm_programs/program_xorshift32_loop.prg.txt |
✅ all 10 match reference |
Plus the generator: vm_programs/xorshift32_gen.py (emits stages 4 & 5).
00→byte:0, 01→byte:1, 10→byte:1, 11→byte:0.byte: 10, 9, 8, …, 1.0x87985AA5 (matches reference step 1).xorshift32_reference.py → all 10 values OK (0x87985AA5 … 0x3AB14B11).# XOR gate (type/pass two bits)
printf '1\n0\n' | python3 vm_programs/CopyJumpMachine.py vm_programs/program_xor_gate.prg.txt
# Reference PRNG (play with seed/n)
python3 vm_programs/xorshift32_reference.py 0x12345678 10
python3 vm_programs/xorshift32_reference.py 1 5
# Countdown
python3 vm_programs/CopyJumpMachine.py vm_programs/program_countdown.prg.txt
# One number / N numbers
python3 vm_programs/CopyJumpMachine.py vm_programs/program_xorshift32_step.prg.txt
python3 vm_programs/CopyJumpMachine.py vm_programs/program_xorshift32_loop.prg.txt
xorshift32_gen.py): edit SEED and N at the top, then re-run python3 vm_programs/xorshift32_gen.py to regenerate stages 4 & 5. The emitted .prg.txt headers echo the chosen values (e.g. # SEED = 0x12345678, # N = 10).program_countdown.prg.txt): # === EMBEDDED CONSTANT: N = 10 === with a commented bit-map for editing.# x[0] = seed bit 0 = 0).<<13, >>17, <<5 as index arithmetic over the bit arrays (out-of-range source = constant 0), so no actual shift instructions.a=0 → dst=b; a=1,b=0 → 1; a=1,b=1 → 0), reused 61× per xorshift step (the other 35 bits are plain copies where the shift moved a bit out).Everything is non-interactive (no in reads) so it’s deterministic and directly diffable against the Python reference.
vm_programs/program_xor_gate.prg.txtvm_programs/xorshift32_reference.pyvm_programs/program_countdown.prg.txtvm_programs/program_xorshift32_step.prg.txtvm_programs/program_xorshift32_loop.prg.txtvm_programs/xorshift32_gen.py.cj numeric export (via exporter.py) later.