51 Commits
Author SHA1 Message Date
dsh 12a2254078 docs: a design note for building the machine out of silicon
docs/hardware.md turns the ISA into hardware requirements and works out what a
physical ROT-8 needs.  The load-bearing observation is that nothing in the
instruction set can observe time -- no counters, no interrupts, and the I/O
behaviours are "block until a character" and "latch the cell" -- so any
implementation that reproduces the same sequence of (ip, dp, cells, output) is
the same machine, at any clock rate and any number of cycles per instruction.
That is what makes the build tractable: a microcoded sequencer, slow memory or
even a drum are all legal.

The note pins the parts that are easy to get wrong: the exact scan boundaries
for [ and ] (the ] case jumps back onto the [ itself so it re-tests, which the
reference rot8.c gets right and a naive implementation gets wrong), the halt
condition, cells starting at zero, and the input convention -- , blocks until a
character arrives and an explicit EOF reads as 0, otherwise every interactive
read would return zero and the program would exit at once.

Budget: 3 bits per instruction, so the flagship tape is 23.4 KB of ROM and the
calculator at 11 bits is 27.6 KB; the data ring is 259 cells by W bits at most
518 bytes.  Two consequences: the instruction pointer needs at least 17 bits
because the calculator now assembles to 73624, past the historical INS_SIZE of
65536, and the 32 bit calculator (126 KB) does not fit the block RAM of the
small boards.

Three carriers are compared: FPGA first (Tang Nano 9K, about 58 KB of BSRAM, a
weekend of work), discrete TTL as the real machine (25-35 chips, 0.25-0.5 M
instructions per second, a few weeks) and electromechanical as the showpiece
(a drum with 11 tracks and 259 cells per track, read and write heads one cell
apart so a read-modify-write costs one cell time: 22 s for a whole calculator
session at 3000 rpm).  The verification plan leans on what already exists: a
packer into the 3 bit format, the RTL testbench compared against tape_run step
by step, then the panel single-stepped against an exported trace.

Nothing is implemented; the note ends with the decisions that come first --
which carrier, which width (8, 11 or 16), program storage, and whether the
physical tape form matters.  The first concrete step would be M0: the packer
plus a rot8.v testbench, which needs no hardware purchase and gives all three
carriers the same golden model.
2026-11-20 15:14:42 +08:00
dsh 5c414292d2 calc: a terminal front end -- echo, backspace editing and a prompt
The calculator now behaves like the terminal tape from the previous commit:
every character is echoed, backspace edits the digit window, Enter commits the
line and prints the next prompt, and '.' puts its result on its own line:

    > 12 34 + .
    0046
    > 12<BS>3 .
    0013
    > ^D

It is not the terminal's line buffer moved over: the calculator consumes one
character at a time, and replaying a buffered line would mean unrolling the
engine once per buffer cell, which does not fit.  Line editing here is the
digit window: backspace shifts it right by one, pads a '0' in front, echoes
"space, backspace" and keeps accumulating.

Three things had to be learned the hard way, all recorded in docs/calc.md ?8:

* a borrowed constant cell gets eaten.  KBS (the 8 that backspace subtracts)
  lived in SC+5, and the operator step erases SC..SC+6 wholesale, so the first
  byte after an operator was treated as a backspace -- every character of
  "12 34 + ." came out as an erase.  It is now loaded right before each use.
  It also must not borrow R: the EOF test writes R every round.
* set_1 only forces the low bit; cells lent to the classifier have to be
  re-initialised each round rather than assumed clean.
* the prompt after Enter has to be printed before the command dispatch and the
  operators run, because EH (the "this was Enter" flag) borrows SC+3, which
  mul uses as scratch -- the first version printed a prompt after every
  multiplication.

The tape went 64983 -> 73624 characters (+8.6k: three copies for the window
shift alone are ~4.4k, the two subtracts ~3k).  That is past the old
ROT-8-viz INS_SIZE of 65536; the current VM sizes its buffer from the tape and
runs 112802 characters at 16 bits and 336304 at 32 bits, so only the
historical budget is gone, not the ability to run it.  Ducking under 65536
again would mean dropping line editing: echo plus the Enter prompt alone is
about +2.5k, still over.

Verified: ctest 8/8 (examples_test checks the new header stream), the width
matrix at 11, 16 and 32 bits (calc stream, terminal tape and the viz's serial
output all agree; 73624 / 112802 / 336304 characters), and docs/calc.md records
step counts for the whole session list -- "12 34 + ." is 287589 steps, about
17% more than before the front end.
2026-11-19 14:27:30 +08:00
dsh c417304140 term: a line-editing terminal -- buffer, backspace and command dispatch
examples/term.r8asm was a per-character echo (prompt, echo, backspace erase,
newline, EOF).  It is now a small shell: a 4 character line buffer, a backspace
that really removes a character, and Enter -- or EOF, for a half typed line --
commits the line and dispatches on its first character.  'l' prints the length,
'r' prints the buffer backwards, 'q' quits, anything else is ignored.

The header session "lhi" exercises the whole chain: EOF commits the pending
line, so examples_test sees the '3'.  Three more sessions are documented in the
header: "rab" gives NUL+'b'+'a'+'r', "lab<BS>" gives '2' (the backspace really
dropped the 'b'), and "lhi<NL>rxy<NL>" prints '3' then the reversed second
line.

Three things ate most of the debugging time; all three are written up in the
file:

* "else" needs a flag cell.  biz enters when the low bit is set, so "if not A
  then B" cannot be inferred from "the last test missed": set FLAG=1 before the
  test, clear it in the matched branch, look at FLAG afterwards.  And biz tests
  the CURRENT dp cell, so the order has to be "set FLAG, then .tp to the
  condition cell, then biz" -- the wrong order made every character look like
  a commit key.
* clb_sub_nc eats its operands, so the echo and the append both work from the
  copy CE.  The first version appended C (already zeroed by the comparison),
  which left the line buffer empty: 'l' printed 0 and 'r' printed four NULs.
* the cell layout dominates the tape.  copy / clb_sub_nc / clb_nonzero all emit
  .tp internally, some of them inside %rep _CELL_SIZE, so a 20 cell gap costs
  a couple of thousand characters: putting the constants at 22..28 gave 33067
  characters, packing the hot cells into 0..27 gives 21721.

The buffer is left aligned with a length counter -- appending needs a dispatch
on LEN, but backspace is just LEN-- -- and 'r' prints all four cells instead of
dispatching on the length, which costs a NUL for the unused cells and is
documented.

tests/widths.ps1 now also checks term.r8asm at every width (its expected
stream is width independent, which is what makes it a good second program for
the matrix), and TODO/AGENTS/README record the item as done.
2026-11-18 21:58:29 +08:00
dsh 4eec72953a docs: README -- the calculator is done, the terminal tape is next
The TODO summary line still advertised the interactive calculator; it has been
finished (and is now an RPN stack).  Point at docs/calc.md and list what is
really left: the terminal tape, the mini printf, the tape optimiser,
--profile, the cache check and CI.
2026-11-18 21:46:36 +08:00
dsh 10f164b480 docs: the signed wrappers in SPEC, AGENTS, README and TODO
SPEC gains 7.10 with both contracts, the five design points and the measured
tape lengths; 5.4 stops saying "implementation pending" and spells out why the
range is asymmetric -- |N| can be outside the signed range while still fitting
unsigned, so 1024 has to print -1024 and the absolute value cannot be done by
clearing the sign bit.

Numbers re-measured on this machine, because some had drifted: the flagship is
62351 characters / 202159 steps (documented as 62513 / 206491), --opt takes it
to 56338, the calculator is 62624, the byte level test is 23 items over 22
macros, and asm/ has 55 macros in 23 files.

tests/widths.ps1 no longer compares the viz's serial output below 8 bit cells:
the viz prints one number per OUT there, so the 7 bit "viz FAILED" was the
script's expectation, not the tape -- the calculator itself passes at 7 bits
through r8forge_derive, and the same failure reproduces with the previous
calculator (checked against HEAD in a temp worktree).  The TODO gains the open
question of whether the flagship should keep the 65536 limit at all, plus the
evidence that a 16 bit tape of 96052 characters runs fine in the viz.
2026-11-18 21:14:07 +08:00
dsh 3543003a78 digits: reorder the scratch block -- 22% fewer steps, 15% less tape
The profile said 77% of clb_digits' steps are pointer moves, so the layout of its
13 cell scratch block (S..S+12) is the cost.  The block is one rigid 7 cell unit
(clb_divmod owns its internal order: Rhi,Sd,Bo,Cm=Bc,Ci,buf,NR) plus six free
units, so the legal space is 5040 permutations.  All 5040 were assembled and run
(minimal driver, value 2047):

  old: TEN Q R [block] counter T F
  new: T1 R [block] TEN Q F counter

   tape 13,717 -> 11,717 chars (-14.6%)
   steps 145,114 -> 113,264 (-21.9%)
   pointer moves 111,958 -> 80,108 (-28.4%)   non-move steps identical (33,156)

Full 2048 value sweep: worst 164,843 -> 123,731 (-24.9%), mean 144,904 -> 112,552
(-22.3%), better on all 2048 values.  The old layout ranked 3459/5040.

Two things worth remembering.  First, ordering the units by the wrapper's first
visit order is *worse* than the old layout (150,748 steps): first visit ignores
revisit frequency -- the counter is touched once per round, TEN is copied into Bc
every round, T1 is hammered by clb_add_ip's carry chain.  Second, the n-1 lower
bound is not reachable here: 74% of the steps still execute inside clb_divmod's
block, whose order is not clb_digits' to choose, so this lever is now exhausted
(that is what the exhaustive search proves).

Min tape is not min steps either: block-first BQTRT1F1C gives the shortest tape
(10,713) but 123,890 steps.  Tape counts a .tp once, steps count its execution.

Ripple: asm/test.r8asm 64,513 -> 62,513 chars, 236,439 -> 206,491 steps, INS_SIZE
headroom ~1k -> ~3k; --opt 58,060 -> 56,350; calc --opt 52,857; calc_op 77,356 ->
69,324 chars / 599,090 -> 476,170 steps.

Verified: ctest 8/8, byte_op_test 21 items (digits 2048/2048), examples_test 18,
--opt assembles, SPEC 7.7/10.2 + AGENTS + README + docs/calc.md + docs/divmod.md
numbers updated.  New driver drv/digits_layout.r8asm keeps the measurement honest
(one clb_digits call, no output, value fed as 0=2047).
2026-11-18 17:27:05 +08:00
dsh a56a12f132 r8forge --opt: the peephole pass is part of the assembler now
The pass moved out of tests/tape_opt.cc into src/tape_opt.cc with a header
(rot8_optimize(tape, cell_size)), so both entry points share one implementation:

  r8forge --opt file.r8asm > t.rot8     assemble, then optimise in memory
  r8forge_tape_opt t.rot8 t2.rot8       optimise a tape assembled earlier

--opt is peeled off argv before the rest of the parsing, so it can appear
anywhere and the existing flags are untouched; without it the output is byte for
byte what it was (flagship 64513).

Measured: flagship 64513 -> 58060 (-10.0%), calculator 62585 -> 54863 (-12.3%),
and "12 34 + ." still prints the same out stream from the optimised calculator.
ctest 8/8 still green.
2026-11-18 10:34:30 +08:00
dsh 55ab5dfebd examples: the terminal tape -- prompt, echo, newline, backspace, EOF
examples/term.r8asm is the "type at it and it answers" program: it prints "> ", then
echoes every character the machine reads, prints a fresh prompt after each newline,
and answers a backspace with space + backspace so the cursor erases the glyph.
EOF (the 0 that inp returns when the input is gone) erases the loop quota, so the
loop ends and the tape runs off its end after one final newline.

  tape 3467 characters, 4743 steps for a two line session (the calculator is 62585)

Measured (derive and tape_run, then the reference machine's serial output):

    in  hi            out 62 32 104 105 10                       "> hi\n"
    in  hi<LF>ok      out 62 32 104 105 10 62 32 111 107 10      two prompts
    in  h<BS>i        out 62 32 104 8 32 8 105 10                the 8 32 8 pair

All three character streams agree with ROT-8-viz byte for byte (bar CRLF).
r8forge_examples_test passes all 18 examples.

One thing worth recording: my brief for this said "a body entered on LSB==0 needs no
clear" -- that is backwards, `[` *jumps* on LSB==0, so bodies are entered on LSB==1.
Following it inverted the dispatch (EOF fired with C=0x68) and it took a
`tape_run --trace` to see it; the file now documents the real rule next to the loop.
2026-11-17 20:31:36 +08:00
dsh a1f88e3d25 asm: raw_puts_dyn -- print a buffer whose length is only known at run time
A terminal has to echo the line the user just typed, and that length is a cell, not
a constant; clb_puts cannot do it because .tp takes a literal address.  So this one
walks MAX compile time slots and decides per slot whether to print: CNT starts as a
copy of LEN, clb_nonzero turns "CNT != 0" into the flag F, and the print happens
inside `biz F` with the countdown *inside* the guarded body as well.

That last detail is the whole bug this round: with clb_dec_ip outside the guard, a
CNT of 0 wrapped to 2047 on the first skipped cell and the rest of the buffer came
out (LEN=0 printed E F G H).  The fix is also why the driver covers LEN = 3, 0 and
8 -- the zero case is what caught it.

  drv/puts_dyn.r8asm   13376 chars, out 65 66 67 65 66 67 68 69 70 71 72 (ABC, nothing, ABCDEFGH)
  reference machine    "ABCABCDEFGH"     6306 steps

Also learnt: `copy` takes two arguments (%this is the source), and it wants a clean
buffer -- the first version passed three and then reused a dirty T, which showed up
as a countdown that started from the wrong value.

Not in asm/test.r8asm: an 8 slot version costs thousands of characters and the
flagship is about a thousand under the 65536 limit.  SPEC 5.3 records the contract
and that exception; the macro count is 53.
2026-11-17 20:11:01 +08:00
dsh 37d1dca0c7 docs: the macro count is 52 (48 + load + clb_puts + test.r8asm's local load twice over) 2026-11-17 19:55:47 +08:00
dsh f7ac81b06f asm: clb_puts and load -- printing a sentence, and the constant helper
clb_puts REG LEN prints LEN consecutive cells as characters (the low 7 bits, which
is what serial OUT sends).  LEN has to be an assembly time constant: .tp takes a
literal address here, so "print until the cell is zero" is not expressible -- the
walk would leave the data pointer somewhere else.  Each character costs two .tp
plus one out (three or four tape characters), uses no extra cell and leaves the
source cells alone.

load N V is the helper every driver was writing by hand (erase then .xor): .xor is
an exclusive or, so a second load without the erase would mix with the old value.

  drv/puts.r8asm      198 chars, in-family check: out 72 73 33 72 (HI! plus the
                      untouched source cell)
  examples/hello.r8asm 727 chars, out 72 69 76 76 79 44 32 82 56 33, and the
                      reference machine prints "HELLO, R8!"

Both are documented in SPEC 5.2; the macro count goes 48 -> 50 and the examples 16
-> 17.  The flagship tape is untouched (64513) because asm/test.r8asm still has its
own local load -- same body, and lib's definition comes first, so nothing changed.
2026-11-17 19:55:32 +08:00
dsh b497bf0637 examples: the desk calculator -- 12 34 + . -> > 0046
The five stage drivers are now one program.  examples/calc.r8asm is a two
register desk calculator: digits build a number, + - * / set the pending
operator, . prints the accumulator (`> 0046` + newline) and , clears it.  EOF (the
0 that inp returns when the input runs out) erases the loop counter, so the loop
ends and the tape simply runs off its end.

    in 12 34 + .   out 62 32 48 48 52 54 10       (> 0046)   314777 steps
    in 2047 3 / .  out 62 32 48 54 56 50 10       (> 0682)   362281
    in 7 6 * .     out 62 32 48 48 52 50 10       (> 0042)   299352
    in 9 4 - .     out 62 32 48 48 48 53 10       (> 0005)   292030
    both of the first two in one session          659759 steps

62585 characters, under ROT-8-viz's 65536 for the first time in this series, so
the whole calculator can be cross-checked against the reference machine later.
tape_run and derive agree, r8forge_examples_test passes all 16 examples, ctest 8/8.

Four deliberate departures from docs/calc.md, each forced by a measurement:

  * settle before loading the new operand, and `.` settles too -- the literal
    order printed 0034 for 12 34 + . because the space arrives before the + and
    overwrites A;  * the operator is one-hot (1 2 4 8) so settlement is four flat
    mutually exclusive biz blocks;  * the loop quota is refilled each round
    (clb_ones can only make _CELL_SIZE ones, 11 here) instead of a fixed 128;
  * three cell moves worth ~24k of tape: clb_undigits scratch 35..45 -> 5..15
    (next to the window it decodes), result/display target 0 -> 20 (adjacent
    scratch makes the %synth blocks shorter), 35..45 reused as one shot flags.

Also found a trap worth remembering: a biz body that ended with `.tp B1; set_0`
(condition cell is FLAG) has net displacement +2, and only on the skipped path
does it desynchronise every later .tp -- the symptom was `-` and `,` sending the
tape into the weeds.  Net displacement 0 on both paths, always.
2026-11-15 16:03:45 +08:00
dsh cc75ed7ea4 drop the CI pipeline, keep the local ctest
The act_runner image has no cmake and installing it per run did not get through
this network (even from a domestic mirror), so the pipeline was cost without a
green run.  Remove .gitea/workflows/ci.yml and the image recipe, keep what was
useful on its own:

  * ctest --test-dir build -j 4   runs the 8 checks in about 9 s
  * README / AGENTS now point at that instead of six commands typed by hand

TODO keeps a note: CI is paused, and ROT-8-viz is still the untested half.
2026-11-11 10:07:44 +08:00
dsh 0d08fdc838 docs: collect every leftover TODO into one file
"Not done yet" was scattered: AGENTS had a five item candidate list, docs/divmod.md
had a "no optimisation we skipped" section, README pointed at neither, and the
tree carried one genuine code marker nobody had noticed -- src/r8asm.cc:154
still says "TODO: FILL THE BLANK" above the ROT8_NODE macro (inherited from
upstream, so it is recorded rather than changed).

TODO.md now holds all of it, each item with why it matters and where to start:

  interaction   the desk calculator (input plumbing is already in place)
  tools         --opt peephole + tape diff, --profile, %synth --verify, CI
  text/picture  clb_puts + mini printf, 259 cells as a frame buffer
  skipped opts  clb_divmod's ~D precompute, clb_digits layout, the 495 char copy
  not TODOs     SPEC 12 "we already proved this cannot work" stays out of it

AGENTS' candidate section shrinks to a pointer, README gains a row in both of its
index tables, and docs/divmod.md 6 is linked from the optimisation entry instead
of being rewritten.
2026-11-09 17:22:25 +08:00
dsh ae268b9442 Interactive I/O: teach the VMs INP, and let examples declare their input
The library can read characters now that the viz defaults to serial ASCII, but
R8Forge's own machines could not: r8forge_derive, r8forge_tape_run and the
examples harness all skipped ',' ("input is not modelled"), so an interactive
program could only be run through ROT-8-viz -- the wrong end of the dev loop,
and nothing in CI could cover it.

Three small pieces:

  * INP (',') reads the next scripted character (low 7 bits) and 0 once the
    text runs out, in tests/tape_run.cc, src/derive.cc and the examples VM.
    r8forge_tape_run and r8forge_derive take -i/--input "<text>", so an
    interactive program is run and checked exactly like any other:
        r8forge_tape_run t.rot8 -i "12+34="
        r8forge_derive calc.r8asm 0 -i "12+34="
  * examples_test learns an optional `;   in ...` header next to `;   out`:
    the characters after the marker are fed to INP before the run.  The marker
    must be the first word after ';' so "include" in a comment is not eaten.
  * examples/echo_chars.r8asm: the smallest interactive program -- read four
    characters, print them back.  in R8F! -> out 82 56 70 33, 8 characters,
    8 steps.

Verified the same tape three ways: tape_run -i "R8F!" -> 82 56 70 33,
derive 0 -i "R8F!" -> same, rot8_test --input R8F! -> prints R8F.  With no
input at all INP reads 0, which is how every non-interactive example keeps
running unchanged.

Baseline: examples_test is now 15 examples + asm/test.r8asm.
2026-11-09 17:14:12 +08:00
dsh a82d95658e docs: one home per fact -- README as the front door, SPEC as the contract, AGENTS as the manual
The three documents had grown to 2038 lines and quoted each other: 2199 appeared
seven times, 3977 ten times, AGENTS carried a 200-line copy of SPEC's byte-level
tables while README carried another 155-line copy still showing 8-bit-era numbers
(clb_add_nc 688, clb_not_ip 17, ...) that are wrong at 11 bits.

Split by responsibility, keep every fact exactly once:

  README.md   front door: what it is, 30-second build+run, directory map, where
              to read next                                     547 -> 143 lines
  SPEC.md     the contract: %synth, geometry, every macro's signature / cells /
              tape length / who verifies it, test matrix, boundaries, maintenance
                                                               901 -> 807 lines
  AGENTS.md   the manual: hard rules, build and self-check commands, the traps,
              current state, next candidates, do-not-touch list
                                                               590 -> 132 lines

Long-form reasoning moves into docs/ instead of being dropped:

  docs/divmod.md    the shift-restore division story (was SPEC 14, 102 lines;
                    renumbered 1..6, SPEC keeps a pointer and the references in
                    SPEC 7.6 and asm/divmod.r8asm now point there)
  docs/byte-ops.md  the byte-level design history (was README's 155-line section,
                    rewritten with 11-bit numbers since the old ones were
                    measured at 8 bits)

Also fixes what the dedupe exposed: SPEC no longer claims only the multiplier has
a step bound, and raw_sub's comment no longer repeats the retracted "1.48M steps"
figure. Every section reference in the tree resolves; the baseline still passes
(asm/test.r8asm 64513 characters, 21 byte-op items, 14 examples, 48 macros).
2026-11-09 16:34:15 +08:00
dsh c4048132cc asm/undigits: the inverse of clb_digits (ASCII decimal -> integer)
clb_digits could turn a number into four ASCII digits but nothing could turn
them back, so a program that stored or received a decimal string had no way
home.  clb_undigits REG N S is that way back:

    clb_digits   N REG S      ; 1234 -> 49 50 51 52
    clb_undigits REG N S      ; 49 50 51 52 -> 1234

Same number of digit cells as clb_digits writes (floor(W*log10 2) + 1, four at
11 bits), each read as its low 7 bits, so leading zeros are fine and garbage in
bits 7 and above is ignored.  No validity checking, exactly like clb_digits: a
cell that is not '0'..'9' yields a deterministic but meaningless number, and the
documentation says so.

Horner in a runtime loop, one clb_mul in the whole tape:

    N = 0 ; repeat 4: N = N*10 + digit ; shift the digit cells down one

9642 characters (minimum driver) -- smaller than clb_digits, because the reverse
direction needs no division.

Three things worth remembering, all found by testing rather than reasoning:

  * c ^ 48 == c - 48 for '0'..'9' (the top two bits cancel, the low four are
    identical), so subtracting '0' is one assembly time `.xor 48`: no
    subtraction, no constant cell.
  * The low-7-bit mask is `ror` 7, then set_0+ror per bit for the rest: the total
    rotation is W, so the cell ends up facing the same way.  The first version
    wrote `rol; set_0; ror` in a %rep and cleared the same bit four times -- it
    looks right and is undetectable on inputs whose high bits are already 0
    (measured: 0|5<<7 came through as 688).
  * The round counter must be erased before it is built: set_1 only clears the
    bit it rotates to, so high ones left in the cell turn into extra rounds
    (measured: dirty scratch gave 1234 -> 1564).

Tests and docs:

  * r8forge_byte_op_test gains test_undigits: all 2048 values x {clean, garbage
    in bits 7+} = 4096 cases, worst 36,481 steps.
  * examples/undigits_demo.r8asm: "1234" -> 1234, "0007" -> 7, and a
    digits -> undigits round trip on 2047; examples_test runs it like the rest.
  * asm/test.r8asm calls it too (round trip inside the digits section).  That
    pushed the file over ROT-8-viz's 65536 instruction limit, so the redundant
    second raw_add case, the reversed raw_sub case and the standalone divmod
    section are gone -- every macro is still called at least once, and the file
    is 64513 characters / 236439 steps / 93 outputs now.
  * SPEC 7.9 (contract + the three traps), 10.2, 10.3 and 11, the AGENTS byte
    table / verified list / naming table / baselines, and the README example
    table all updated.
2026-11-09 16:17:39 +08:00
dsh eacf6c01da r8forge: add -q / --quiet for a tape-only stdout
Assembling a library file prints one `%synth ...: cached, N blocks` line per
block (21 of them for asm/test.r8asm), plus search timings and the occasional
temp-directory notice.  That is useful when working on the searcher and noise
when the tape is the output:

    r8forge -q examples/full_add.r8asm > full_add.rot8

-q keeps stdout to the tape alone: cache hits, the layer/tape search lines and
the "temp dir is not writable, using ..." fallback are silenced.  Errors are
not: a missing file, an unknown macro, no program up to N layers, a tape search
that fell back to the layer answer and "cannot write the synthesised macro
anywhere" all still go to stderr with the same exit code.  Quiet means "don't
natter", not "hide the failure".

Implementation follows the existing per-run switches: ast::quiet, the
r8asm::set_quiet(bool) setter, one more parameter on r8asm_synth_program (the
prints live in synth.cc) and the temp-directory notice in r8asm.cc.  The CLI
parses -q and --quiet anywhere among the arguments.

Verified: -q examples/full_add.r8asm and -q asm/test.r8asm produce byte
identical tapes to the normal run (95 / 58722 characters), stderr drops from 1
line / 21 lines to 0 bytes, and -q on a missing file or an unknown macro still
prints the error and returns 1.

SPEC 3.7, the README cost-model section and the AGENTS %synth list document it.
2026-11-08 00:24:51 +08:00
dsh 2e6d9cee86 asm/test.r8asm: call every macro, exercise every language feature
The old test.r8asm was a three round hash: `clb_add_nc` + `clb_mul`, nothing
else.  It proved "add and multiply are enough for a hash" and it was the file
every session was told to check, but a regression in, say, clb_divmod or raw_sub
could not show up there.

It is now the library's kitchen sink instead: one call per standard macro,
grouped from the smallest to the biggest

    A  lib        set_0 set_1 erase rol step back .anchor copy bit_copy
                  copy_to_buffer bit_copy_to_buffer clb_bit_mov
    B  bit slices clb_bit_add_nc clb_bit_inc_nc bit_raw_add/inc/and/or/xor
                  clb_bit_and/or/xor
    C  raw_*      raw_add raw_inc raw_and raw_or raw_xor raw_sub (operands kept)
    D  clb_*      clb_add_nc clb_inc_nc clb_neg_nc clb_sub_nc clb_not_ip
                  clb_inc_ip clb_neg_ip clb_dec_ip clb_nonzero clb_add_ip
    E  big        clb_ones + loop/endloop, clb_divmod, clb_digits
    F  language   a user %macro that uses %rep and %for, .var arithmetic,
                  two inline %synth blocks (map and stat, both cache hits)
    G  the old hash, now two rounds

Each call is followed by `output`, so the OUT stream is the fingerprint.
examples_test now runs this file too and compares it with the `;   out` line in
the header (it already did that for examples/), which makes the file an actual
assertion instead of a length in the docs: an example that stops printing what
its header says fails the test.

Numbers: 58722 characters, 215169 steps, 100 values.  r8forge_derive,
r8forge_tape_run and ROT-8-viz's rot8_test produce the identical stream (the
last six values are the hash: 1322 5 82 0 1786 94).

Two layout decisions come from that cross check:

  * The tape has to stay under 65536 instructions: that is ROT-8-viz's
    INS_SIZE (include/rot8/rot8.h) and read_tape truncates silently past it.
    An earlier version of this file was 76047 and the viz stopped after 99 of
    its 104 outputs, which is how the limit was found.
  * So the hash keeps two rounds and the two rounds share one clb_mul scratch
    block (erased in between) instead of carrying three separate ones.

The hash's own rules are unchanged: the multiplier stays 141 because it is the
historical value, not because small operands must sit in MUL any more.

SPEC 10.2, the AGENTS baseline/self-check/table and the README build snippet
are updated to the new numbers and to the 65536 limit.
2026-11-08 00:15:39 +08:00
dsh b666799950 %synth: make the tape search thread count a run option (-j N)
The tape search always used std::thread::hardware_concurrency() workers with no
way to ask for fewer (or more).  It is now a run option like the cost model:

    r8forge -j N <file.r8asm>                N workers
    r8forge --synth-threads=N <file.r8asm>   same thing

0 (the default) means one worker per hardware thread, as before.
r8asm::set_synth_threads(unsigned) is the C++ side; the CLI parses -j,
--synth-threads and --synth-threads=.  The layer search stays serial (it only
takes seconds and has no split), so the knob only affects the expensive tape
search, which splits by first block (see r8veritas_phase.hh).

The search line on stderr now ends with ", N threads", which makes the setting
verifiable without timing: with a freshly written table (params 4, or4) and the
cache entry removed between runs,

    -j 1                 -> 230 states, 0.0009s, 1 threads
    -j 4                 -> ..., 4 threads
    --synth-threads=2    -> ..., 2 threads
    (nothing) / -j 0     -> ..., 32 threads (hardware_concurrency here)

Documented in SPEC 3.7, README's cost model section and the AGENTS %synth
section.  asm/test.r8asm is unchanged at 28729 characters; byte_op_test,
examples_test (all 13), macro_docs, synth_test (95 chars, 8/8) and
r8forge_derive all still green.
2026-11-07 23:56:37 +08:00
dsh b4ea79ba91 %synth: the cost model is a run option, not a per block metric line
`metric chars|flat|blocks` inside %synth meant the same truth table could be
searched twice for two call sites, and every library block had to spell out
`metric flat` to avoid the default.  The cost model belongs to the whole
assembly, so it is one now:

    r8forge <file.r8asm>                  flat (layout free), the default
    r8forge --synth-chars <file.r8asm>    charge the real .tp walk

flat stays the default because a library block is expanded at dozens of call
sites with different layouts: only a layout free result can share one cache
entry, and it is usually within a few percent (full_add: 95 vs 90 characters).
The chars search is far more expensive (full_add: 415M states, ~21 minutes,
~10 GB), which is exactly why it should be asked for on the command line.

`metric blocks` goes with it: block count is a poor proxy for tape length (and
it was only another way to ask for mode layers).

Implementation: the metric lives in the assembler (ast::synth_metric, default
1) and is set through r8asm::set_synth_metric() before import_file; the CLI in
tests/asm_test.cc parses --synth-chars / --synth-flat.  The cache key already
carried metric, so the committed entries still hit: assembling the library and
asm/test.r8asm gives byte identical tapes (28729 characters, byte_op_test all
green, all 13 examples green, synth_test still 8/8).

A `metric` line now fails with a message that names the flag instead of being
silently ignored.  examples/full_add_flat.r8asm and full_add_flat_spaced.r8asm
are removed: they only existed to demonstrate the per block metric (the flat
default makes them copies of full_add.r8asm).

Also repairs the mojibake in README's metric section: an earlier tool wrote
\x0c / \x08 / \x0d where \f, \b and \r belonged, which ate characters out of
"flat", "blocks", "biz/flb/rnz" and "rnz".  The section is rewritten for the
flag, and the %synth numbers in README/SPEC/AGENTS now match what the tree
prints.

New cache entry c16bf083bb0ccbc8.txt is full_add's stat table with mode layers
+ flat, which full_add_stat.r8asm now produces.
2026-11-07 23:44:01 +08:00
dsh 3f4149c9d0 examples: one runnable routine per macro group
SPEC is the contract and drv/ is what the tests sweep, but there was no place
that showed a reader how a group is actually used.  examples/ now has one stand
alone program per group, each ending in output calls:

    base_macros.r8asm    S5   set_0 vs erase, rol/ror, copy vs bit_copy vs
                              clb_bit_mov, step
    bit_adder.r8asm      S6   4 bit ripple carry adder built from
                              clb_bit_add_nc, then bit_raw_add for the
                              preserving variant
    byte_raw_ops.r8asm   S7.1 raw_add/raw_inc/raw_and/raw_or/raw_xor/raw_sub,
                              printing the operands afterwards to show the
                              whole point of the family: they survive
    byte_clobber.r8asm   S7.2 clb_add/sub/neg/inc_nc (operands eaten) and the
                              S7.3 clb_and residue (240 & 204 -> B = 12)
    byte_in_place.r8asm  S8   not/inc/neg/dec/add_ip and clb_nonzero
    sum_loop.r8asm       S5.1 clb_ones + loop/endloop: 1+2+...+N, count from
                              data rather than from the assembler
    mul_demo.r8asm       S9   82*141 and 2047*2047
    divmod_demo.r8asm    S7.6 2047/10 and 2047/1 (the case that used to hang),
                              reusing the scratch block on purpose
    digits_demo.r8asm    S7.7 1234 and 7 -> four ASCII digits

Every header carries a `;   out 1 2 3` line: the expected OUT stream, so the
file itself says what it prints.  The new r8forge_examples_test target runs all
of examples/*.r8asm and compares that line with the real output (a file without
the marker counts as a failure), printing the tape length and step count on the
way.  That makes examples the second place after byte_op_test that checks
behaviour instead of just "it assembles", and keeps the examples from rotting as
the macros change.  The six %synth examples get the marker too: their inputs are
all zero, so they print 0 0.

All 15 examples pass.  The values in the headers were checked with
r8forge_tape_run (the second interpreter) as well as the test's own machine.

Docs: SPEC S10.3 has the table and the convention, S11 gets the test row, and
README gets a short section plus the layout list.  AGENTS records the examples
in the handoff baseline and the "verified" table.
2026-11-07 22:34:15 +08:00
dsh bfad4b5d34 clb_ones: unary expansion, a count becomes that many ones
New macro in asm/ones.r8asm: clb_ones A B T F leaves B = 2^A - 1, i.e. A
consecutive ones starting at the low bit, and eats A (it is spent as the
counter).  The contract only holds for A <= _CELL_SIZE and is not checked, as
asked: 0 -> 0, 1 -> 1, 4 -> 0x0F, 7 -> 0x7F, 11 -> 0x7FF (all ones).

The loop is "shift and stuff a one in":

    B = 0
    while A != 0:  B = 2B + 1 ; A -= 1

In this machine `2B + 1` is exactly `rol` + `set_1`: the left rotation brings
B's top bit round to the low bit and set_1 overwrites it.  A is spent as the
counter instead of being copied (a copy is 495 characters), the loop body
appears once so the length does not depend on A, and the run time is O(A) with
A <= cell size.

The other sizing option was measured and rejected: start from 1, rotate A
times, then clb_dec_ip once.  That drops set_1 from the body but pays 132
characters for the decrement and 44 for the erase, so it comes out 128 longer.

  * tests/byte_op_test.cc: test_ones walks every A the contract covers
    (0..kCellSize), which is the whole domain once the range is the caller's
    job; 742 characters with the driver, 828 with a minimal one.
  * drv/ones.r8asm: the driver the test uses.
  * SPEC.md 7.5: the contract, the algorithm, and the two identities worth
    remembering -- clb_inc_ip turns n ones into 2^n, and building it the other
    way round costs more than it saves.  Macro counts bumped to 42.
  * AGENTS.md: the tables, plus the naming row (destructive computation whose
    result lives in another cell, so no _ip suffix).
2026-11-07 16:29:17 +08:00
dsh 54ddf9b0e7 SPEC.md: the %synth grammar and every standard library macro's contract
R8Forge had no spec of its own: the language lives in r8asm_rev/SPEC.md, the assembler
and the search were documented in README.md, and the macro contracts were only in the
comments above each %macro.  This adds SPEC.md, pointed at the standard library:

  * what this spec covers and what stays upstream (so the two do not drift);
  * the five parameter types, the naming prefixes/suffixes, and the measurement
    convention for tape lengths (a minimal driver, contiguous cells, no output lines);
  * %synth: the full grammar, what map and stat mean, the three metrics, the cache key
    and kModelVersion rule, and the four limits (8 params, 8 layers, no byte level
    tables, no unconditional flip);
  * all 41 macros in asm/ in tables with signature, which cells they eat, cell count,
    tape length and implementation (hand written or %synth block + its stat table);
  * the warts: clb_and leaves B & ~A behind while clb_or/clb_xor are clean, layout being
    silently ignored when its length is not params, and set_0 clearing one bit only;
  * a verification matrix saying which test proves what, and the known dead ends.

Every number in the tables was measured for this commit with one uniform driver
(measure_macros.ps1 shape, deleted afterwards), e.g. clb_not_ip 22, clb_add_ip 722,
clb_mul 3964 minimal vs 3977 through drv/mul_byte.r8asm.  AGENTS.md and README.md now
point at SPEC.md instead of saying the %synth docs only live in the README.
2026-11-07 12:44:47 +08:00
dsh ac5810580d kDefaultCellBits -> kDefaultCellSize: the width is cell_size, not cell bits
The cell width is cell_size everywhere else now -- cell_size in the AST, in
ROT-8-viz's rot8_config, and the docs -- but the default in geometry.hh was
still kDefaultCellBits, and the four VMs spelled it that way too.

  * include/r8forge/geometry.hh: kDefaultCellBits -> kDefaultCellSize.
    kDefaultCellMask keeps its name: it is a mask, not a size.
  * src/derive.cc, tests/asm_test.cc, tests/synth_test.cc, tests/tape_run.cc,
    tests/byte_op_test.cc: same rename, and the local shorthand kBits in
    byte_op_test.cc is now kCellSize so the test file does not put the old
    word back.
  * AGENTS.md and README.md follow.  The cross check bullet now describes the
    workspace ROT-8-viz as it actually is (fork dsh/ROT-8-viz, branch main,
    runtime --cell / --mem over cell_size / mem_size), instead of the feature
    branch it used to point at, which no longer exists.

No behaviour change.  All six self checks re-run green: 28729 character hash
tape, synth_test 8/8, both verify_ tapes, byte_op_test (clb_mul 3977 chars,
65536/65536, "byte level library ok") and the macro docs test.  The hash tape
still gives 1322 1786 1600 5 94 127 from r8forge_derive, r8forge_tape_run and
ROT-8-viz's rot8_test -- three implementations, one answer.
2026-11-07 12:33:56 +08:00
dsh 6e67eb4678 The multiplier: shift and add, one bit at a time, 3977 characters
clb_mul was repeated addition -- add MC into the product, MUL times.  That is
the shortest thing to write, but the runtime is proportional to MUL's value:
255 * 255 took 733428 steps, and 2047 * 2047 ran into the 5000000 step ceiling
and hung outright (tape_run: HANG after 5000000 steps).  So the multiplier was
a ceiling on what any program could compute.

The new body is the plain binary multiplication from school: hold the
multiplicand, look at the multiplier's low bit, add the multiplicand into the
high half of the product when that bit is 1, then shift the whole product one
place right -- the multiplier lives in the low half of that register, so its
bits fall out one at a time.  The loop runs _CELL_SIZE rounds whatever the
operands are, and the tape got shorter as well:

    82 * 141     358586 -> 8374 steps
    255 * 255    733428 -> 17785 steps
    2047 * 2047      HANG -> 26123 steps
    tape           5007 -> 3977 characters

(Step counts are the tape's own, with no trailing newline -- tape_run counts
one if the file has one, which is where the first draft of this message got
numbers two out.)

Counter, carry and cross cell shift are the three pieces that needed care:

  * the round counter is _CELL_SIZE ones in NR, one eaten per round by
    set_0 + ror -- the same trick clb_inc_ip counts rotations with, so "how
    many rounds" costs no tape length, only runtime;
  * the carry out of the W bit add is not scratch: it is the top bit of the
    2W+1 bit shift register, and the next shift moves it into PH's top bit;
  * (F:PH:PL) >>= 1 is a cross cell shift.  ror all three, bring the bit to
    inject down to bit 0 with rol, move it with clb_bit_mov, ror back.  The
    low pair (PH -> PL) moves first, otherwise PH's bit 0 has already been
    overwritten by the carry.

And biz/rnz is a loop pair, not an if/else: a one shot conditional has to eat
the bit it tested (a trailing flb) or rnz jumps straight back.  The first
version of this hung exactly there -- no output at all, counter still 0x7ff.
The bit eaten is PL's low bit, which the shift discards anyway.

r8forge_byte_op_test now sweeps 0..255 x 0..255 exhaustively (65536/65536 ok,
6.7s instead of 1.5s) instead of sampling 64 combinations: the cost no longer
grows with the multiplier, so sampling was the only reason not to.  asm/
test.r8asm still prints 1322 1786 1600 5 94 127, now as 28729 characters and
57330 steps (was 31901 and about two million), and derive and tape_run agree.

AGENTS.md and README record all of it, plus one correction: the old note said
shift and add had been dismissed because "only tape length is the target".  It
is in fact 1000 characters shorter, so the reason given was wrong -- the
tradeoff was not.  What changed is the target function: the 5000000 step
ceiling is part of it, and a loop whose length does not depend on its operands
can still have a runtime that does.
2026-11-07 12:09:45 +08:00
dsh 62c6f8979f Cell width and tape length: 11 bits, 259 cells, by default
The assembler already took the width as an argument (import_file(path, cell_size))
and exposed _CELL_SIZE / _CELL_MAX / _ROL_STEP to programs, so every macro that
writes %rep _CELL_SIZE follows the width on its own.  What was missing was a
single place saying what the default is, and VMs that agree with it.

include/r8forge/geometry.hh now holds kDefaultCellBits = 11,
kDefaultMemoryCells = 259 and kDefaultCellMask, and the four VMs use it:

* cells are uint16_t, the tape is kDefaultMemoryCells long
* ROR is (v >> 1) | ((v & 1) << (kDefaultCellBits - 1)), not the 8 bit version
* input and output mask with kDefaultCellMask

The tests now state their expectations in terms of the width instead of a byte
(kCellMask, kBits, kCellMod).  Two things were genuinely wrong for 11 bits and
are fixed: clb_neg_* and clb_inc_* were compared against 256 - a and 0xff, and
asm/test.r8asm set B with .xor (~126)+1 -- .xor takes its constant modulo the
cell width, so that is 1922 in an 11 bit cell, not 130.

Results at 11 x 259:

    asm/test.r8asm        7262 characters, out 127 130 0 257 0 1088 19
                          (127+130 = 257, and 200*200 = 19*2048 + 1088)
    r8forge_byte_op_test  all 17 operations pass
    r8forge_synth_test    all eight combinations ok (bit level is width free)
    r8forge_macro_docs_test  41 macros in 17 files
    asm/fibonacci.r8asm   11959 characters, 13 terms now (no wrap at 256)

ROT-8-viz moved its defaults to 11 x 259 in the same change, so the tapes cross
check: both implementations print 127 130 0 257 0 1088 19 for asm/test.r8asm.
Tapes grow when the width does (raw_add 1647 -> 2199 characters), because the
%rep _CELL_SIZE loops are longer.

AGENTS.md gains a section on how the width flows through the tools, including
the trap that 2048 % 256 == 0 makes several 8 bit expectations still pass by
accident.
2026-11-07 10:56:28 +08:00
dsh 6e8e33e455 test.r8asm now multiplies as well as adds
The file was the library smoke test: it set up a few cells, called raw_add and
printed five values.  It now also calls clb_mul and prints the two product bytes,
so one tape exercises both of the expensive paths and the self check runs a
result rather than only an assembly.

    127 + 130 = 257        -> S = 1, Co = 1
    200 * 200 = 40000      -> PL = 0x40 = 64, PH = 0x9C = 156
    whole tape             5417 characters (was 1666)

Both interpreters agree on `out 127 130 0 1 1 64 156`: r8forge_derive from the
source and r8forge_tape_run from the assembled tape, 427343 steps.

The multiply half lives at cells 16 and up so it cannot disturb the add half, and
the file's existing cell layout is untouched.
2026-11-07 10:15:58 +08:00
dsh 185b4bf24a The multiplier, 3729 characters, by repeated addition
clb_mul  MC MUL PL PH MCA S Ci T F NR    (PH:PL) = MC * MUL
    10 cells, 3729 characters, 64 sampled cases, 255*255 = 0xFE01 included

For scale: fibonacci is 8761 characters and does not multiply.  The tape length
does not depend on MUL at all, because the loop body appears once.

The algorithm is repeated addition, not shift-and-add:

    (PH:PL) = 0
    while MUL != 0:  (PH:PL) += MC ; MUL -= 1

which is the same lever as clb_add_ip: length is the metric, steps are not.  Worst
case is about a million steps against the five million limit and that is fine.

The 16 bit accumulate uses clb_add_nc for the low byte because it is the one that
reports a carry out; clb_add_ip does not, so it cannot do that step.  clb_add_nc
eats its operands, so each round copies the multiplicand first.  The carry then
goes into the high byte with clb_add_ip, which costs nothing extra since it is
0 or 1.

Worth recording what this did to my own plan: I had said the multiplier needed
"cross byte shifts" and "conditional accumulate" first, and sketched a
shift-and-add design around them.  Repeated addition needs neither -- the shift
disappears entirely.  The primitive that actually mattered was the one I called
missing two messages earlier: an add that keeps the addend alive, which is what
pushed out clb_add_ip and clb_nonzero.  Look at the objective function before
copying the shape of a hardware multiplier.

byte_op_test is seventeen operations, still 1.4 s, with test_mul sampled over
8 multipliers x 8 multiplicands.
2026-11-07 09:56:03 +08:00
dsh a6560b72cf In place add, by looping instead of writing a carry chain
clb_dec_ip  A T        A = A - 1                2 cells  106 chars  256/256
    clb_nonzero B F T      F = (B != 0), B intact   3 cells  209 chars  256/256
    clb_add_ip  A B T F    A += B, B is eaten       4 cells  558 chars  2048 sampled

against raw_add (6 cells, 1647) and clb_add_nc plus a copy per round (688 + 364).
Add is the primitive the multiplier needs, so this was the expensive one.

decrement needed no new algorithm: B - 1 = ~(-B), so it is clb_neg_ip then
clb_not_ip, and both are already in place.

The add does not do a per bit carry chain, and it is worth being clear why not:
a full adder's carry is maj(a,b,c), i.e. a pairwise conjunction, and every
conditional test eats the bit it tests, so a hand written ripple needs several
copies of each bit and nested tests -- long and fragile, and it was the reason I
first called this impossible.

What works instead leans on something true of this project: the metric is tape
length, not execution steps.  So

    while B != 0:  A += 1 ; B -= 1

The loop body appears in the tape once, so the length does not depend on B.  The
cost is O(B) runtime, about 300k steps at B = 255 against a 5M limit.  This is a
general lever: anywhere length is what matters, ask whether a loop can replace
generated code.

The one thing that was genuinely awkward is "B != 0", since biz only looks at the
low bit.  clb_nonzero walks the eight bits, moves each into a work cell (which
clears that bit of B), and if it was set, sets F and puts the bit back; B comes
out untouched.  Note set_1, not flb: flb flips, so an even number of set bits
flipped the flag back to zero and 3, 5 and 255 all read as "zero" until I fixed
it.

For the multiplier this means one copy per round (364) to keep the multiplicand,
so about 920 per round, roughly 8k for the whole multiplier instead of 13k.

Tests: byte_op_test is sixteen operations now, 1.5 s.  test_add_ip is sampled
(8 accumulators x 256 addends) because the loop makes exhaustive runs slow.
2026-11-07 09:49:51 +08:00
dsh 2f79898e3d In place increment in two cells, 74 characters, by counting rotations in the
scratch cell's bits

I said a two cell in place increment was impossible.  It is not.  The version in
asm/inc_ip.r8asm does A = A + 1 with A and one scratch cell, 74 characters,
256/256 exhaustive, and there is a two cell in place negate on top of it:

    clb_not_ip A       A = ~A      1 cell    17 chars   256/256
    clb_inc_ip A T     A = A + 1   2 cells   74 chars   256/256
    clb_neg_ip A T     A = -A      2 cells   90 chars   256/256

against clb_inc_nc (3 cells, 430) and clb_neg_nc (3 cells, 448).  Five times
shorter, one cell less.

Both of my earlier impossibility arguments were about a *specific* algorithm, the
per bit carry ripple, and I stated them as if they covered the problem.  The one
worth remembering is the synthesis one, which is still true: a synthesised block
has exactly one condition cell, so it cannot tell (A=1, Ci=0) from (A=1, Ci=1),
and all four in place tables answer "no program up to 8 layers".  The hand
written argument was simply wrong.

The algorithm that works does not test the carry per bit at all:

1. `[ ... ]` already means "while the low bit is set", so clearing the run of
   low ones is a loop that falls out on the first zero (flb + ror);
2. flip that zero to one -- skip it when the input is all ones, which is exactly
   the wrap-around case;
3. rotate the rest of the way.

What is left is "how many rotations remain", with only two cells.  The counter
goes into the scratch cell's bits: T starts as 0xFF, and every rotation does
set_0 then ror, which eats one 1 -- the length of the run of ones is the number
of rotations left.  Three characters per step, and a full turn counts to eight.

The wrap case falls out for free: when the input was 0xFF the counter is spent
exactly then, so step 2 is skipped and the answer is 0.

Two smaller notes.  The dp rule from the last commit is what these macros had to
respect -- every conditional body returns to its own condition cell -- and
`[ ... ]` consuming its condition is only a problem when the condition is data;
here it is the counter.  And I mangled asm/inc_ip.r8asm once with a PowerShell
Get-Content / Set-Content round trip (the trap AGENTS.md warns about) and had to
rewrite it with the editor; no other file was touched.

byte_op_test is twelve operations now, still exhaustive, still under a second.
2026-11-07 09:40:05 +08:00
dsh eedd9a33a6 Negate and subtract invert the whole byte first instead of bit by bit
Asked why an in place complement does not exist, given that in place inversion
does.  The inversion half is now hoisted out of the per bit loop, which is both
simpler and shorter:

    clb_neg_nc A S Ci = clb_not_ip A ; clb_inc_nc A S Ci     468 -> 448
    clb_sub_nc A B S Ci = clb_not_ip B ; clb_add_nc A B S Ci   725 -> 707

and the unsigned complement through the same macro (carry in at 0) drops 467 ->
447.  B is eaten by the add anyway, so inverting it in place costs nothing.  The
per bit `flb` wrappers (clb_bit_neg_nc, clb_bit_sub_nc) are gone with them, so
macro_docs_test now counts 35 macros.

What does not work is the other half: there is no in place increment, so the sum
still has to land in S.  Two independent reasons, both written down:

* A synthesised block has exactly one condition cell, so it cannot tell
  (A=1, Ci=0) from (A=1, Ci=1) -- and that distinction is the whole carry rule.
  All four in place tables answer "no program up to 8 layers".
* Hand writing cannot do it with two cells either: `[ ... ]` is the only one shot
  conditional this ISA has, and it eats the bit it tests, while in place
  increment needs both cells' bits alive at the same time.

So one cell buys the ones' complement only; a two's complement negate costs three
(A, S, carry).  tests unchanged and green: ten byte level operations, 1666
character test tape, 8/8 full adder, fibonacci.

Also: the docs quoted clb_neg_nc at 468 and clb_sub_nc at 725, now 448 and 707.
2026-11-07 09:20:44 +08:00
dsh 557e2a1c38 In place: the ones' complement takes one cell and 17 characters
Asked whether two's complement can be done in place.  The negate cannot, but the
inversion half can and is absurdly cheap, so it is a macro now:

    clb_not_ip A        A = ~A, one cell, 17 characters, 256/256

`%rep 8 { flb; ror }` -- flip the low bit, rotate the next one down, eight times
puts the byte back where it started.  The same result through clb_neg_nc with its
carry at 0 costs 467 characters, because that path runs a synthesised slice once
per bit.

The in place two's complement itself: tried four tables and none of them exist.

    A <- ~A ^ Ci        A <- A ^ Ci        A <- A ^ B ^ Ci     A <- A ^ ~B ^ Ci
    no program up to 8 layers (all four)

Two separate reasons, both worth keeping:

* Synthesis cannot: a block has exactly one condition cell.  In place increment
  has to tell (A=1, Ci=0) -> (1,0) from (A=1, Ci=1) -> (0,1); A is the same in
  both and only Ci differs, and one condition cannot look at two cells.
* Hand writing cannot either (2 cells): `[ ... ]` is a while loop and the only
  one shot conditional this ISA has, and it eats the bit it tests.  In place
  negate wants "flip the low bit every round, then decide the carry from it",
  so both cells hold live bits and the test destroys one.

So a negate still has to land in a separate S (clb_neg_nc, 3 cells); one cell
buys the ones' complement only.  byte_op_test is ten operations now, AGENTS.md
and README.md carry the distinction and the two reasons.
2026-11-07 09:16:44 +08:00
dsh 026ad82455 The nc macros take a real carry in, they do not seed it themselves
They used to write the carry cell themselves -- set_0 inside clb_add_nc, set_1
inside clb_inc_nc / clb_neg_nc / clb_sub_nc -- which made the parameter a lie: a
cell the caller passes and the callee overwrites is not a carry input, it is a
scratch cell wearing a carry's name.  It also ruled out the thing a carry is for:
multi byte arithmetic.  The carry out of the low byte could not be handed to the
high byte, because the high byte's call would zero (or one) it first.

Now the macros only read it, and the caller decides:

    clb_add_nc A B S Ci     S = A + B + Ci      Ci = 0 plain add, or chained
    clb_inc_nc A S Ci       S = A + Ci          Ci = 1 gives A + 1
    clb_neg_nc A S Ci       S = ~A + Ci         Ci = 1 gives -A, Ci = 0 gives ~A
    clb_sub_nc A B S Ci     S = A + ~B + Ci     Ci = 1 gives A - B, Ci = 0 A-B-1

which also turns the negate into two operations for free: two's complement
negation at Ci=1 and the ones' complement (~A) at Ci=0.  The second one has its
own driver and test now (drv/raw_not_nc_byte.r8asm).

The drivers set the bit explicitly before the call, which is where that
instruction belongs -- the tapes end up the same length as before (688/430/468/725
instead of 693/433/471/730: one setup instruction moved out of the macro).

All nine byte level operations still pass, and the docs (AGENTS.md, README.md and
the four file headers) now state the carry in contract instead of describing a
constant.
2026-11-07 09:12:47 +08:00
dsh 87ab064121 Delete the duplicate slice file, and say what the carry cell really is
asm/raw_add_nc4.r8asm carried the same 4 cell table as asm/raw_add_nc.r8asm --
same stat line, same metric, only the wrapper was named bit_add_nc4 -- and
nothing included it.  Gone; raw_add_nc.r8asm stays, it is the one
verify_raw_add_nc.r8asm and the docs point at.

While looking at it: is the third parameter a scratch cell, and does the slice
have a carry input at all?  Measured with verify_raw_add_nc.r8asm:

    A=0 B=0 carry-in=0 -> S=0 carry-out=0
    A=0 B=0 carry-in=1 -> S=1 carry-out=0
    A=1 B=1 carry-in=1 -> S=1 carry-out=1

so the cell is read on the way in and written on the way out -- a carry input
and a carry output sharing one cell, not a scratch.  All four parameters carry
meaning, which is why the `raw` in bit_raw_add_nc is history rather than
something SPEC.md asks for (raw = the caller passes the scratch cell).  AGENTS.md
now spells that out instead of repeating "and the scratch cell is passed by the
caller", which was wrong for this one.

The macro count in the docs drops to "every macro" rather than a number, so
adding or removing one does not leave a stale count behind.

Everything still green: test.r8asm 1666, full_add 8/8, verify_raw_add_nc,
byte_op_test 65536x4 + 512, macro_docs_test 29 macros in 9 files, fibonacci.
2026-11-07 00:26:03 +08:00
dsh 56ea288cd6 Tidy the standard library's macro docs, and check them by machine
Audited all 30 %macro in asm/.  The format was already followed almost
everywhere -- the doc block sits above the %macro, or above the %synth block
that generates its body -- but four things were wrong:

  raw_and.r8asm  the two doc blocks still carried the old names (bit_and, and)
  raw_xor.r8asm  raw_xor's first two parameters were typed Unit, not Cell
  lib.r8asm      step / back / output had no type at all ("%1: step_count")

and two files still repeated the retracted claim that set_0 only converges on 0
and 1 (raw_add_nc.r8asm, raw_add_nc4.r8asm).  Those now say what set_0 really
does -- it clears the low bit -- and stay on the point that matters for a bit
level slice: A, B and the carry must be single bits because the searched
program only tracks the low K bits.

Parameter types are now a closed set: Cell, CellBit, Unit, UnitBit, Count
(Count is for step/back's repeat count).  It is written down in AGENTS.md
together with the format, so the next macro has something to copy.

New r8forge_macro_docs_test checks the format instead of trusting review: a doc
block must exist, its ";   Macro <name>" line must match the macro, the number
of documented parameters must equal argc, and every type must be one of the
five.  Negative tested by deleting a parameter line and by renaming a block --
it reports both and exits 1.

Also fixes a real annoyance found while running the checks: %synth writes its
generated macro to the system temp directory and imports it.  That write fails
intermittently on this machine (same directory, cmd can write, r8forge cannot;
cause unknown), which turned every assembly into "cannot open ...synth.r8asm".
The body is now built in memory and written to the temp directory or, if that
open fails, to the working directory, with one stderr line saying so.

Full suite green: test.r8asm 1666 characters, full_add 8/8, verify_raw_add_nc,
byte_op_test 65536x4 + 512, macro_docs_test 30/30, fibonacci prints its ten
numbers.
2026-11-07 00:23:28 +08:00
dsh e30725247e Delete the one bit per cell layer
It was written from a wrong diagnosis.  Because the interpreters in this repo
read biz/rnz as a whole cell zero test, every packed byte program looked hung,
and the conclusion was "byte level arithmetic has to be one bit per cell".
With the interpreters fixed (86a54aa) that reason is gone: raw_add does the same
job with 6 cells instead of 32, and this repository had already deleted the same
approach once before for the same reason.

Removed: asm/byte_add.r8asm, asm/pack_byte.r8asm, examples/add8.r8asm,
examples/add8_inc.r8asm, tests/byte_add_test.cc and its CMake target.
AGENTS.md and README.md stop listing them and each keeps one paragraph saying
the direction was tried and dropped, so the next person does not add it back.

Still green after the deletion:

    asm/test.r8asm        1666 characters, 7/7 cache hits
    full_add              8/8 combinations
    verify_raw_add_nc     assembles
    byte_op_test          raw_add/and/or/xor 65536 each, raw_inc 512
    fibonacci             1 1 2 3 5 8 13 21 34 55
2026-11-07 00:07:34 +08:00
dsh afd56e7a8c Fix the ROT-8 interpreters: biz / rnz test the low bit
Four interpreters here (tests/synth_test.cc, src/derive.cc and the two I added
earlier: tests/tape_run.cc, tests/byte_add_test.cc) implemented '[' and ']' as
a Brainfuck style "is this whole cell zero" test.  The reference implementation
does not:

    ROT-8-viz src/rot8.c
    rot8_biz: if ((*mem & 1) == 0) skip to just past the matching ']'
    rot8_rnz: if ((*mem & 1) == 1) jump back to the matching '['

That one difference is why every byte level program in the library looked like
an endless loop.  It is invisible in the bit level world -- for a cell holding 0
or 1 the low bit test and the zero test agree -- which is why the synth tables,
asm/test.r8asm and full_add never noticed anything.

Cross checked against the reference before touching anything: the tape our
assembler produces for "A = 128, set_0, B = 3, raw_add" prints 128 3 0 131 0 on
ROT-8-viz/build/rot8_test.exe and hung in our derive.

With the fix, measured:

    raw_add   65536/65536 pairs ok  1647 chars
    raw_and   65536/65536            639
    raw_or    65536/65536            575
    raw_xor   65536/65536            463
    raw_inc   512/512               1214
    asm/fibonacci.r8asm prints 1 1 2 3 5 8 13 21 34 55, exactly what its
    comment claims

So the byte level layer was never broken.  Two commits ago it was declared dead
-- set_0 "only converges on 0 and 1", the bits of a packed byte "unreadable",
raw_add "only survives 0+0" -- entirely on the strength of the broken
interpreters.  AGENTS.md and README.md now say the opposite and keep the wrong
diagnosis as a worked example: when byte level code looks hung, check the
interpreter first.

New:
  tests/byte_op_test.cc + drv/raw_{add,and,or,xor,inc}_byte.r8asm
      exhaustive runtime proof for the byte level library, 0.5 s
  tests/tape_run.cc + r8forge_tape_run
      a second interpreter that runs a .rot8 file directly -- cross checking
      derive is now one command

verify_set_0.r8asm now demonstrates what set_0 really does instead of claiming
it hangs: 255 -> 254, 5 -> 4, 128 -> 128 (it clears the low bit, not the cell).

The one bit per cell layer (byte_add / pack_byte) stays as a documented
alternative: it is correct under the real semantics too, just redundant.
2026-11-07 00:01:25 +08:00
dsh 43390efe8a Byte level add, one bit per cell: 65536 combinations ok
The rotation based byte layer never ran.  Measured with r8forge_derive -2:

    raw_add   A=0,B=0 / 1+1 / 3+5 / 1+0   out empty (step limit hit)
    raw_add   A=127,B=130                 out 0 0 0 0 0, everything destroyed
    raw_and   0xF0 and 0xCC, 1 and 1, 0 and 5   out empty
    copy      A=5                         out empty (A=0 returns fine)

Not "only operand preservation is missing": set_0 (= [-]) cannot clear a cell
that holds more than one bit, and biz only answers "is this whole cell zero",
because ror does not change zero-ness.  So the bits of a packed byte are
unreadable, and the whole ror + set_0 layer has no future.  The docs now say
that instead of blaming operand preservation.

What replaces it is one bit per cell:

  asm/byte_add.r8asm   8 bit adder.  Bit i owns four adjacent cells at base+4i:
                       A, B, carry (in -> out), scratch.  The synthesised four
                       cell slice bit_raw_add_nc does the bit, clb_bit_mov moves
                       the carry into the next quartet.  A doubles as the
                       accumulator, so calling byte_add again continues the sum.
  asm/pack_byte.r8asm  eight flags -> one byte, the only direction that works.
                       bit_raw_flip_if consumes a flag into flipping bit 0 of an
                       accumulator that may already hold bits (no set_0 there).
  examples/add8.r8asm  a+b, 1308 characters.  A shared carry cell layout needs
                       only 25 cells but was measured at 2517: paying .tp travel
                       eight times beats saving seven carry cells.
  examples/add8_inc.r8asm   add 1 three times, proving the block composes.
  tests/byte_add_test.cc    r8forge_byte_add_test: runs the tapes on the ROT-8
                       machine over every input pair, 0.3 s.

Also: AGENTS.md gains the measurement table, the third instruction set
constraint (packed bytes are unreadable), the new files, and the note that
build/ has to be rebuilt with the VS bundled cmake -- scoop's 4.4 reconfigures
it and dies with "No preprocessor test for PellesC".
2026-11-06 23:40:14 +08:00
dsh 9041034b6e Write the handoff notes down
AGENTS.md, pointed at from the README, so a new session does not have to
rediscover any of this:

  * working habits: put anything over ~30s in the background, keep large stderr
    out of the transcript (the transport failures), write Chinese only through
    the editor, put conclusions in commits rather than in the chat
  * build and self check commands for both MSVC and clang-cl
  * r8forge_derive's three modes, including the detail that -1/-2 take assembly
    source, not a .rot8 tape
  * the instruction semantics and the two consequences: set_0 only converges on
    0/1, and synthesised programs only touch the low K bits of each cell
  * %synth syntax, metric flat, the cache key and kModelVersion, the 990M state
    reference point and the layer bound of 8
  * what is verified working, and the list of dead ends not to retry: three cell
    slices, rotation with synthesised slices, bit per cell adders, byte level
    tables through the search
  * the naming and comment conventions of lib.r8asm
2026-11-06 23:26:58 +08:00
dsh 14af0ca6ff Standard library: flat metric, cache pre-warmed and committed
Every synth block in asm/ now says 'metric flat', so the seven block bodies are
optimised without the .tp walk and therefore do not depend on where the caller
puts its cells.  The resulting bodies are cached in .r8forge_cache/ and the
cache is committed, so a fresh clone assembles the library without waiting for
a single search.

asm/test.r8asm: 1674 -> 1666 characters.

The seven tables were re-derived after the switch and all match the hand written
implementations bit for bit (bit_raw_add still 0 9 10 19 12 21 22 31 repeated,
bit_raw_inc 0 5 6 11, and so on), so this is a pure length win.

One caveat: bit_raw_add's flat search still runs out of state budget (700M, the
table stops fitting in a laptop) and falls back to the layer answer, which is
what got cached for it.  The other six converge in milliseconds; the whole warm
up took 396 seconds, almost all of it that one block.
2026-11-06 18:55:18 +08:00
dsh da16c111cf Add a layout independent metric so a result can be cached and reused
%synth could optimise the real tape characters, but that price depends on where
the cells sit, so the answer was only good for one layout and the cache could
only be shared between call sites with the same addresses.

  metric chars   tape characters including the .tp walk   layout dependent
  metric flat    characters without the walk             layout independent
  metric blocks  block count                             layout independent

'flat' is the step-free mode: it counts biz/flb/rnz and the ops, ignores how
far apart the cells are, so one search result and one cache entry serve every
layout.  The price is a slightly longer tape when the layout happens to suit a
different program: 90 characters for chars, 95 for flat on the full adder.

Checked: examples/full_add_flat.r8asm hits the cache on the second run, and the
same block with 'layout 0 2 4 6 8 10' added hits the *same* entry and emits a
byte-identical tape (the key drops the layout for the layout-free metrics).
Both pass the eight combination check.
2026-11-06 18:39:49 +08:00
dsh 30089af06d Rewrite the bit macros as %synth blocks
The eight bit-level macros in asm/ are now synthesised instead of hand written.
Their tables were not typed in by hand: r8forge_derive (new, src/derive.cc)
runs the OLD implementation over every input combination and reads the cells
back, so the replacement is bit-for-bit identical, quirks included.  big two
findings:

  * a synth block assumes the parameters that do not take part in the
    computation start at 0 (that is what compress_stat_space means).  These
    macros are called repeatedly inside a loop, so S/Co/tmp arrive dirty; each
    one now has a thin %macro wrapper that clears them and then calls the
    synthesised body.  With that, bit_raw_add derives to exactly the old table
    (0 9 10 19 12 21 22 31 repeated) and bit_raw_and to 0 1 2 7 repeated.
  * clb_bit_and stays hand written.  Three parameters leave no scratch bit and
    "and" needs both inputs alive at once, so it needs nested biz; the searcher
    exhausts nine layers over three planes without finding anything.  That is
    the model's expressive limit, not a shallow search.

asm/test.r8asm assembles to 1674 characters, down from 1714, with identical
block semantics.

%synth results are cached in .r8forge_cache/ keyed by the table, so the
twenty minute tape search happens once per table rather than once per build.

Note on verification: r8forge_derive validates one block at a time, which is
what the tables above are.  The little VM inside it is not solid enough to
vouch for whole programs (fibonacci prints two numbers instead of ten), so
"the whole library still computes the right answer end to end" is NOT verified
here -- that needs the real ROT-8 virtual machine.
2026-11-06 11:04:29 +08:00
dsh 9a760f2a41 Drop the inputs/outputs declarations: the table already says it
A synth block used to spell out which parameter is an input and which is an
output.  That was redundant: with map, 2^K entries already mean %1..%K are the
inputs and the value's bits land on the parameters after them; with a raw
table, nothing needs saying at all.  So 'inputs' and 'outputs' now fail with a
message pointing at map/stat, and the map form derives both.

Added 'stat' as the fully explicit form: 2^params values, one per input
combination, which is exactly the state table the search consumes.
examples/full_add_stat.r8asm is the same adder written that way and produces a
byte-identical tape to the map version (95 characters), both pass the eight
combination check.
2026-11-06 10:33:34 +08:00
dsh 6f2ecf0e22 Add a mode switch and a getting-started section
%synth used to always run both searches, so every assembly of the full adder
sat there for twenty minutes.  A block can now say 'mode layers' to stop after
the layer search (7.7 seconds) or 'mode tape' (the default) to pay for the
shortest tape.  examples/full_add_layers.r8asm is the fast one, 95 characters
and still checked on the machine.

The lexer also no longer chokes on a UTF-8 BOM.  Every Windows editor writes
one, and the first token came out as a garbage prefix, which crashed the
assembler with an access violation rather than saying anything useful.

README grew a getting-started walkthrough: build, a complete adder.r8asm, what
the two stderr lines mean, how to drop a synth block into a library, and the
three things that bite (inputs first, don't call them in/out, map length).
2026-11-06 10:14:58 +08:00
dsh 346cbdc6e4 %synth: emit the tape-optimal program, not the fewest-layer one
The layer search still runs first (7.7 seconds) but only to get a bound; the
cost search then takes over and its answer is what goes on the tape.  A caller
that wants its own layout can say 'layout 0 2 4 6 8 10' inside the block.

examples/full_add.r8asm now assembles to 90 characters of tape instead of 95:
cost 75 in 6 blocks after 415M states and about 21 minutes, against the 82 the
five layer program needs.  Assembly getting slower is the whole point -- it is
the price of the shortest tape.

For scale: one bit_raw_add slice is 179 characters with the cells adjacent, and
the synthesised slice is 82.  A whole raw_add call is 1650 characters today, so
eight synthesised slices would land near 700.
2026-11-06 09:48:39 +08:00
dsh 548c239a85 Tape-length search beats the layer search on the full adder
Five layers cost 95 characters; six layers cost 90.  Both are in examples/ and
both pass the eight-combination check on the ROT-8 machine in
tests/synth_test.cc (which now takes a file argument).

    sacrifice B,  FLIP {S,T}
    sacrifice A,  FLIP {B}
    sacrifice B,  FLIP {A,Ci,S}
    sacrifice Ci, FLIP {B,Co,T}
    sacrifice S,  SET1 {Ci,Co}
    sacrifice T,  FLIP {B,Ci,S,Co}

Cost 75 in the model, 90 on the tape once the inter-block hops and the two
output lines are counted.  The goal was popped at 75 only after everything
below 75 had been expanded, so 75 is the minimum of this cost model.

Trading a layer for a shorter tape is not a contradiction: the layer search
cannot see that a small, cheap block can be worth more than one wide, expensive
one.
2026-11-06 09:12:15 +08:00
dsh 230cf92159 Fix the Dial queue: two ways it silently dropped states
First version scanned ahead for the next nonempty bucket but stopped one max
edge weight out, so a sparse frontier ended the search early and claimed
"nothing under the limit" while the queue still had work.  Scanning further is
also wrong: the ring reuses a slot every ring.size steps, so a far bucket sits
where a near one would be.  Plain Dial now: step one cost unit at a time.

The growth table in the README was measured with the broken version and was
wildly optimistic.  Real numbers from the fixed build, full adder with
adjacent cells: cost 58 -> 80M states, 66 -> 220M, 70 -> 280M, about 27 bytes
per state and 650k states/s, so cost 75 / 450M states / 12GB is roughly the
ceiling on this machine.

Validated solve_cost on the small problems where the answer is known by hand:
copy comes out at cost 17 (sacrifice 0 into {2}, then sacrifice 2 into {0,1}),
which is the two block program, and it replays ok.
2026-11-06 09:10:00 +08:00
dsh 98593b568c Add a tape-length search: Dijkstra with the real block cost
Layers are not characters.  solve_cost runs Dijkstra over the same state graph
with an edge weight of what the block actually assembles to:

    w = 3 (biz + flb + rnz) + 2 * span(cell addresses) + sum(op)
        op = 1 for flb, 4 for set_1

Dial buckets, pop in cost order, the first pop of the goal is the shortest
tape.  Give it max_cost and it becomes branch and bound: anything past the
bound never enters the queue.

Exhausted regions on the full adder with adjacent cells:

    max_cost 20    1,086 states      0.0s
    max_cost 40  128,528 states      0.1s
    max_cost 50  999,448 states      0.7s
    max_cost 60  7,671,626 states   12.8s
    max_cost 65 20,153,459 states   47.6s

About 2.6x states per 5 cost, about 32 bytes per state, so max_cost 80 is
~350M states / 11GB and 82 would be ~600M / 19GB.  The block weight leaves out
the hop from the previous sacrifice (that would make the cost depend on
history and Dijkstra would stop working); the emitter adds it when it reports
the real length -- the five layer program is 82 in the model, 87 on the tape.

The first version of the bucket ring only looked one max-edge-weight ahead for
work, so it declared 'nothing under the limit' while the queue still had
states further out.  That made the small limits look sound when they were not;
advancing to the next nonempty bucket fixed it.
2026-11-06 08:49:11 +08:00
dsh 79bc0a4068 Splice %synth into the tape, and check it on a ROT-8 machine
The synthesised body is written out as a macro file and imported, so the
generated code goes through the ordinary expansion path instead of being
spliced by hand.  set_1 is spelled out as set_0 plus flb, so the generated file
needs nothing from lib.r8asm.

examples/full_add.r8asm now assembles: 7.7 seconds of search at assembly time,
then a 95 character tape.  tests/synth_test.cc runs that tape on a small ROT-8
machine for all eight input combinations and checks S and Co -- all eight pass.

Two things that cost me time and are worth writing down:

  * the opcode map is "><+-[].,", i.e. '-' is flb and '+' is ror.  Guess it the
    other way round and a perfectly good tape looks like an infinite loop.
  * synth names must not collide with mnemonics: 'out' is lexed as rot8_out
    before it can be a block keyword.
2026-11-06 00:08:29 +08:00