29 Commits
Author SHA1 Message Date
dsh d0fd127048 build: the 32 bit toolchain builds, and 8/16 bit byte tests really pass
Two separate things hid behind "32 bit works":

* tests/byte_op_test.cc could not compile at 32 bits at all (`1 << 32` in a
  constexpr plus an int typed mask), so the whole 32 bit build stopped there --
  only `r8forge` and the core library came out.  kCellMod is now clamped at
  31+ bits and main() prints "skipped" above 16 bits (every sweep there is 2^W
  rows) and exits green.  All ten targets build at 32 bits with MSVC, and the
  same tree builds clean on a Gentoo box with GCC 16 -- the missing <cstring>
  in asm_test.cc that stopped GCC first is in the previous commit.
* the digit drivers hardcoded a 4 cell window, so byte_op_test's digits /
  digits_signed / undigits failed at every other width (16 bits wants 5 digits,
  8 bits 3).  drv/digits.r8asm, drv/digits_signed.r8asm and
  drv/undigits_byte.r8asm now derive D = _CELL_SIZE * 30103 / 100000 + 1 and
  space their cells by it, and the C++ side uses the same kDigits instead of a
  literal 4 (including the T/F cells clb_digits_signed leaves behind).

With that, byte_op_test passes at 8, 11 and 16 bits (the 16 bit run takes about
450 s) and above 16 it skips.  Two more width bugs fell out on the way: the
divmod divisor sweep used 1000 and 2047 unconditionally (they wrap at 8 bits),
and the undigits garbage guard OR'ed in bits above the cell, which at 8 bits
turned '0'+digit into a value over 255.  test_divmod_signed also divided by the
recovered divisor without re-checking it, and at 8 bits the boundary value 1024
wraps to 0 -- that was a hard crash (divide by zero), not a failure.

CMakeLists.txt now refuses -DR8FORGE_CELL_SIZE outside 1..32 at configure time;
the range used to be a comment, so an out of range width was discovered as a
compiler error in whichever file shifted by it first.  geometry.hh and SPEC
section 13 record that 32 is the ceiling because every VM stores a cell in
uint32_t -- going further means widening all five VMs, the assembler's immediate
type and ROT-8-viz's rot8_data.

Also recorded there: the %synth cache is keyed by the truth table, not the
width, so a 32 bit build hits the committed entries (0.4 s for the flagship
tape of 227075 characters).  A full cold rebuild takes ~500 s on a 44 thread
machine, 479 s of which is the single 6 parameter full adder table.
2026-11-19 13:41:59 +08:00
dsh 1f3f453e88 signed: the two two's complement wrappers, with exhaustive sweeps
clb_digits_signed N REG S T F prints '-' (45) and then |N| as the same four
zero padded digits; clb_divmod_signed N D Q R S T1 T2 F is the C style
truncated division (q = trunc(n/d), r = n - q*d, remainder follows the
dividend).  Both are wrappers: clb_digits / clb_divmod still do the work, so
the tape only grows by the sign handling -- 572 characters for the display
(12151 vs 11579 in the same driver layout) and 1191 for the division
(6018 vs 4827).

The sign bit is read with rol + bit_copy + ror, 49 characters.  clb_bit_mov is
deliberately NOT used: it eats the source bit, so N comes back as N - HALF and
1024 -- whose magnitude 1024 only fits the unsigned range -- prints as 0000.
A clb_sub_nc against a HALF constant was the other candidate: 765 characters
for the call plus ~60 for the constant cell.

A flag has to outlive the block that consumes it, because biz/rnz only exit
once the body clears the condition bit.  So sign(N) is moved into T2, sign(D)
into F, and the remainder block flips F into sign(N)^sign(D) on its way out;
a single conditional negation of the quotient then carries the xor.  The
negation scratch is S+6: the only cell in S with a "clean on entry" contract,
and clb_neg_ip leaves it zero again for clb_divmod.

Verified by r8forge_byte_op_test: all 2048 values for the display (worst
117606 steps) and 4202 division pairs -- every |a|,|b| <= 32 plus the
0/+-1/+-1023/+-1024 boundary combinations -- compared against C's / and %.
examples/signed_demo.r8asm is the single point regression that runs as a
program (the flagship cannot carry them: +12.1k / +5.6k on a 62351 tape).
2026-11-18 21:13:52 +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 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 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 f9821f8989 calc: stage 4 verified -- four operations, one shared scratch block
drv/calc_op.r8asm computes one case per operation and displays it with the stage 3
prompt, so the arithmetic path of the calculator is proven:

    +  12 34  ->  46        *  12 34   -> 408
    -  100 30 ->  70        /  2047 3  -> 682

    out 62 32 48 48 52 54 10 | 62 32 48 48 55 48 10
        62 32 48 52 48 56 10 | 62 32 48 54 56 50 10

tape 77356 characters, 599090 steps, tape_run and derive agree on all 28 values.

The useful result is the memory map: the four macros want different scratch, and
one 7 cell block (23..29) serves all of them -- add/sub use its first cell as the
carry, clb_mul uses exactly those 7 as Ci PH MCA S T F NR, clb_divmod uses the same
7 as its S.  They never run at the same time, so one erase before each call does
for all three.  The result cell is the display's N cell directly (add/sub write S
there, mul writes PL, divmod writes Q), which saves a copy per case.

Contract probes confirm SPEC: add leaves the carry output 0, sub reports no-borrow
1, mul keeps MC and eats MUL, divmod keeps N and D and puts the remainder in R.

Over ROT-8-viz's 65536 limit (four expanded clb_digits blocks), so it is verified
through the two r8forge machines only; stage 5 loops the display, so the real
calculator will be smaller than this.
2026-11-11 11:18:41 +08:00
dsh b83f3b1b06 calc_disp: correct the header's tape and step count
The numbers written into the header came from an earlier revision of the file (it
had the display body in there twice as long).  Measured on what is committed:

    tape 29188 characters, 282288 steps for the two prints

which is also what makes it fit under ROT-8-viz's 65536 instruction limit.  The
out line was correct either way, which is why the mistake survived until the tape
was measured against the committed file.
2026-11-11 11:00:53 +08:00
dsh bb1a434586 calc: stage 3 verified -- prompt, four digits, newline
drv/calc_disp.r8asm prints `> ` plus a number in decimal, twice (46 and 2047), so
the display path of the calculator is proven end to end:

    out 62 32 48 48 52 54 10 62 32 50 48 52 55 10
        >  sp  0  0  4  6  LF    >  sp  2  0  4  7  LF

tape 58382 characters, 564578 steps (two clb_digits calls dominate), tape_run and
derive agree.  This one fits under ROT-8-viz's 65536, unlike the two %rep 16/6
drivers.

The probe also pinned down which scratch really is sensitive: with cell 0 or the
four REG cells preset the output does not change (load erases, and the digit
shift chain flushes REG), but cell S+10 (the round counter, only set_1, never
cleared) and S+11 (clb_add_ip scratch) do change the first print -- "0047" and
"0000" respectively.  So "the caller must hand in clean scratch" is real, and the
two prints need the erase between them.
2026-11-11 10:59:12 +08:00
dsh b873d71082 calc: stage 2 verified -- the digit window and clb_undigits
drv/calc_num.r8asm reads 6 characters, shifts digits into a four cell ASCII
window (D3 D2 D1 D0, most significant first) and converts it with clb_undigits
whenever a non digit arrives, then resets the window to "0000".

    in  12 34      out  12 34        tape 88413, 78908 steps
    in  0 7        out  0 7 0 0      (each EOF read is a terminator too)
    in  2047       out  2047 0
    in  9999       out  1807 0       (9999 wraps mod 2048, as the machine does)
    in  1234/0007  out  1234 0 / 7 0  (leading zeros work)

tape_run and derive agree on every case.

One deliberate departure from docs/calc.md: the digit branch copies the character
itself into the window instead of C - 48.  clb_undigits xors each cell with 48 on
the way in, so the window has to hold ASCII -- storing the numeric value paid the
xor twice (first version: "12 34" -> 540 562, e.g. 49^48=1 but 1^48=49 then * 10 +
... lands at 540).  So cell 2 (the 48 constant) and the sub_nc call are unused;
the file says so.

The window shift goes high to low (D3 <- D2 <- D1 <- D0) which is the order that
does not clobber unshifted digits; each copy is preceded by an erase of the
buffer even though this build's copy turns out to clean it itself.
2026-11-11 10:22:58 +08:00
dsh fa12494e43 calc: stage 1 verified -- the character dispatch of the desk calculator
ci / cell 16 (push) Skipped
ci / cell 32 (push) Skipped
ci / cell 8 (push) Skipped
ci / wide sweep (manual) (11) (push) Skipped
ci / wide sweep (manual) (16) (push) Skipped
ci / wide sweep (manual) (24) (push) Skipped
ci / wide sweep (manual) (32) (push) Skipped
ci / wide sweep (manual) (8) (push) Skipped
ci / cold cache (manual) (push) Skipped
ci / baseline (11 bit) (push) Failing after 16s
drv/calc_lex.r8asm reads 16 characters and classifies each one: digits print
1+value, the six commands (* + , - . / = 0x2A..0x2F) print 100+index, anything
else prints 200.  The discriminator is bit 4 of the character (digits 0x30..0x39
have it, the command block does not), so four `ror`s and one `biz` split them,
and `t = C - 0x2A` is the command index.

Measured (tape_run and derive agree; tape 90738 chars, 29990 steps):

    in   0 5 9 + - . , *        (15 chars; the 16th inp is EOF -> 0)
    out  1 200 6 200 10 200 101 200 103 200 104 200 102 200 100 200

i.e. 0->1, space->200, 5->6, 9->10, +->101, -->103, .->104, ,->102, *->100,
EOF->200.  Full-alphabet cross-checks: "0123456789*+,-./" gives
1..10 then 100..105, sixteen letters give sixteen 200s, a one char input gives
its value and fifteen 200s.

Two things recorded in the file's header: 90738 characters is over ROT-8-viz's
65536 INS_SIZE because %rep 16 unrolls the body (this driver is verified through
derive/tape_run only; the final program will use a runtime loop instead), and the
bit 4 filter also sends 0x10..0x1F and 0x3A..0x3F down the digit path, which no
protocol input can reach.

This is also the file that slipped into the CI commit earlier -- now it has a
commit of its own with its measured numbers.
2026-11-10 19:47:23 +08:00
dsh 3c427bb8a5 ci: cancel the previous run of the same ref when a new push arrives
ci / cell 16 (push) Skipped
ci / cell 32 (push) Skipped
ci / cell 8 (push) Skipped
ci / wide sweep (manual) (11) (push) Skipped
ci / wide sweep (manual) (16) (push) Skipped
ci / wide sweep (manual) (24) (push) Skipped
ci / wide sweep (manual) (32) (push) Skipped
ci / wide sweep (manual) (8) (push) Skipped
ci / cold cache (manual) (push) Skipped
ci / baseline (11 bit) (push) Failing after 15s
One runner means a push that lands while an older one is still building waits for
it.  Cancel-in-progress keeps the queue at one entry per branch; a manual sweep is
still only cancelled by another push on the same ref.
2026-11-10 19:44:36 +08:00
dsh a891538c9d ci: push runs only the baseline; matrix on PR/manual; timeouts
ci / cell 16 (push) Skipped
ci / cell 32 (push) Skipped
ci / cell 8 (push) Skipped
ci / wide sweep (manual) (11) (push) Skipped
ci / wide sweep (manual) (16) (push) Skipped
ci / wide sweep (manual) (24) (push) Skipped
ci / wide sweep (manual) (32) (push) Skipped
ci / wide sweep (manual) (8) (push) Skipped
ci / cold cache (manual) (push) Skipped
ci / baseline (11 bit) (push) Canceled after 0s
One runner means one job at a time.  Run #1 took 30 minutes because a push
queued four jobs, each a cold build, and every later push waited behind them.
Now a push runs the 11 bit baseline alone (and not at all for docs only
changes), the width matrix waits for a pull request or the manual button, and
every job has a timeout so a stuck step fails instead of blocking the queue.
2026-11-10 19:42:13 +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 c2cd0e827f clb_divmod: shift-and-restore division instead of repeated subtraction
Repeated subtraction ran N/D rounds and hit the 5M step ceiling for D = 1
(2047/1 hangs outright); it also cost 2.46M steps for 2047/2.  Binary long
division is fixed at _CELL_SIZE rounds whatever the operands are:

    R = 0 ; Q = 0
    repeat _CELL_SIZE:  R = (R << 1) | next bit   (rol N hands the bits out
                                                   MSB first and restores N
                                                   after W rounds)
                        if R >= D:  R -= D ; quotient bit = 1

The one non obvious part is the comparison.  R needs W+1 bits after the shift,
but the high bit (H, the bit rol wraps out of Rlo) only has to decide the
commit: H = 1 means R >= 2^W > D, so commit = H | Bo, where Bo is raw_sub's "no
borrow" (Rlo >= D).  SPEC 14's Shi = H & Bo is always 0 under the invariant "R
< D at the start of every round" (H = 1 and Bo = 1 together would need R >= 2D),
so that clb_bit_and and its copy do not exist in the built version.

Signature is now clb_divmod N D Q R S: N and D survive, Q and R each get their
own cell (the old version ate N into the remainder), and S is a 7 cell scratch
block (Rhi, Sd, Bo, Cm, Ci, buf, NR).  Only S+5 (the copy buffer) has to be
clean on entry; the rest is rewritten or used as a single bit, which is what
lets clb_digits pass the same dirty block back in every round.

The order that cost clb_mul two reworks is the delicate bit: rol Rlo wraps its
top bit into bit 0, so clb_bit_mov has to move that bit into Rhi (which also
clears it) before bit_copy injects N's bit.  bit_copy (not clb_bit_mov) is what
keeps N intact.

Measured on drv/divmod.r8asm (11 bit):

              repeated subtraction     shift-and-restore
    2047/10        495,986                 28,593
    2047/2       2,461,650                 31,997
    999/7          340,086                 28,661
    2047/1         HANG (>5M)              32,383

Small N/D get slower (fixed W rounds) -- the same trade clb_mul made.  Worst
case over the sweep is 32,383 steps; the tape grows 4189 -> 4499 characters.

About the numbers in SPEC 14 / AGENTS: the 1.48M steps claimed there do not
reproduce on this tree.  Measured before the change, 2047/10 was 495,986 and
clb_digits(2047) was 740,695, so the docs now carry the measured values and say
where the old figure came from.

clb_digits keeps its shape (one divmod in a 4 round loop, written digits shift
up by one cell), with S grown to 13 cells: TEN, quotient, remainder, the 7
divmod scratch cells, the loop counter and add_ip's T/F.  2047 goes from
740,695 to 145,138 steps (worst 164,867) and 10829 -> 13717 characters.  It
needs its own %include "asm/add_ip.r8asm" now: that used to arrive through the
old divmod.

Tests: test_divmod sweeps 8 divisors x all 2048 dividends (16384 pairs; the old
76 sample table is a subset) and also asserts N and D come back unchanged;
test_digits sweeps all 2048 values.  Both print the worst step count.

Two traps found on the way:

* r8forge_derive (and byte_op_test/synth_test) checked the assembler error flag
  before export_rot8(), but an unknown macro or a bad .tp target is found while
  the tree is *expanded*: a missing %include left a truncated tape that still
  ran and printed a plausible wrong answer (all four digits came out '0').  All
  three now check after the export.
* raw_sub's comment claimed Bo = 1 means A < B; the code (and clb_sub_nc) mean
  A >= B.  Comment fixed, behaviour untouched.

Also adds drv/div_shift.r8asm, the single step check for the cross cell shift
plus injection, and records the measurements in SPEC 7.6/7.7/14 and AGENTS.
2026-11-07 22:22:03 +08:00
dsh 9a9ca48d9a raw_sub: a subtraction that keeps its operands
clb_sub_nc eats A and B, so the repeated subtraction divider has to copy both
every round (two 495 character copies, about five hundred steps each) -- that
is where clb_divmod's 1.48 million steps for 2047 comes from.  Binary long
division compares against the same divisor every round and cannot afford that,
so it needs a non destructive subtract first.

raw_sub A B S Bo Bc Ci buf is three useful lines: copy ~B, set Ci = 1, then
raw_add (which already preserves its operands).  S = A + ~B + 1 = A - B, and A
and B are untouched.  About 2900 characters, 7 cells, 9 sampled cases correct.

One trap measured: do not flip Bo at the end to turn a carry into a borrow --
clb_not_ip complements the whole cell, so 0 becomes 2047 and 1 becomes 2046.
Bo keeps the library's existing meaning instead: 1 means A >= B (no borrow),
same as clb_sub_nc's carry.

This is step one of replacing clb_divmod's O(N/D) loop with shift-and-restore
division at O(cell_size) rounds (11 instead of 205 for 2047, so roughly forty
times fewer steps for maybe a few hundred extra characters of tape).
2026-11-07 20:24:55 +08:00
dsh a515e823d1 clb_digits: integers become a four digit ASCII string
clb_digits N REG S writes '2' '0' '4' '7' into REG..REG+3 for 2047 -- ASCII
digits, most significant first, fixed width four, zero padded, which is what
was asked for after the ASCII/order/source questions.

divmod appears once, wrapped in a loop that runs four times.  The first
version dispatched each digit to its own cell with four branches and a one-hot
flag handoff, and only the first branch ever fired; the digits themselves were
right (checked by printing N after every division: 204, 20, 2, 0).  Rather than
keep chasing that, the dispatch is gone: each round shifts the digits already
written one cell up (high to low, so nothing gets clobbered) and the new digit
always goes to REG+0.  Four rounds later REG+0..3 are thousands, hundreds, tens,
ones in that order.  Simpler, two nesting levels less, four cells less, and it
works: 0/1/7/10/42/99/100/512/1000/1234/2047 all correct.

Two real traps found on the way, both now in the macro comments and SPEC:

  * copy's buffer cell must be *clean*: a dirty buffer makes the copy produce
    0 (measured: Q = 4, buffer = 0x7f8 -> N = 0).  The library only says the
    buffer is borrowed, never that it has to be zeroed.
  * building a constant cannot be done as 'set a bit, rotate, set another,
    rotate': the second rotation carries the first bit away.  Walk the ring
    once instead -- W rotations, set_1 at each target bit, then back home.

10829 characters with a minimal driver (13743 with the four outputs), 16 cells
in total, and r8forge_byte_op_test's test_digits covers all 11 values.
2026-11-07 17:18:02 +08:00
dsh 4a5bd836a8 clb_divmod: nine parameters down to four
Complaint received and agreed with: nine cells to pass for a division is not an
interface anybody wants to type.  Two things made it possible to shrink:

  * .tp and macro arguments accept address expressions (measured: .tp A+1
    assembles, and set_0 A+1 expands to .tp A+1 inside the callee).  So the
    four scratch cells can be passed as one block: clb_divmod N D Q S uses S,
    S+1, S+2 and S+3.
  * BUF and X were unnecessary: copy already has sources and destinations to
    spare that are dead at the moment they are needed, and clb_inc_ip can take
    a cell that the probe is about to overwrite.

So the signature is now clb_divmod N D Q S -- three data cells and one scratch
base -- and the tape dropped from 5839 to 4189 characters on the way, because
the scratch cells now sit next to each other and every .tp walk got shorter.

Still correct: all 76 sampled pairs (2047/10 = 204 7, 7/10 = 0 7, 10/10 = 1 0,
1234/100 = 12 34, 999/7 = 142 5, 2047/2047 = 1 0), and the O(N/D) limit is
unchanged.
2026-11-07 16:53:27 +08:00
dsh 0b96b76104 clb_divmod: division and modulo, so digits have something to stand on
The library had add, subtract (with a free compare in its carry), negate,
increment, decrement, multiply, and the bit ops -- but nothing that divides.
Asking for a decimal expansion without it means inlining a division per digit,
which is where the 11k character estimate came from.

clb_divmod N D Q W V T Ci X BUF leaves Q = N div D and N itself as the
remainder, eating D.  Plain repeated subtraction:

    Q = 0
    while N >= D:  N -= D ; Q += 1

Two things it took to get right:

  * clb_sub_nc eats both operands, and the subtraction cannot alias (measured:
    clb_sub_nc A B A Ci with A=15 B=10 gives 0), so each round needs copies of
    N and D.  Two of the three copies are pure overhead, but they are in the
    loop body, which appears once.
  * The first round has to be able to do nothing.  Setting T = N and Q = -1
    before the loop makes the first commit a no-op and lets the phantom count
    cancel out, so the probe can live at the *bottom* of the loop and appear
    only once.  Without that the probe is duplicated and the tape grows by
    about 1.3k.

5839 characters with a minimal driver (5845 with the two outputs), 9 cells,
all 76 sampled pairs correct in r8forge_byte_op_test.  Runtime is O(N/D): the
worst case 2047/1 crosses the 5M step budget and hangs, so the test keeps
N/D <= 600 and SPEC says so.  Division by zero is undefined, D >= 1 is the
caller's job.

Next: clb_digits on top of this, which needs a shared loop plus per-cell
conditional writes (computed addressing does not exist here) rather than four
copies of divmod.
2026-11-07 16:51:25 +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 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 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 5f0ce78861 Two's complement: negate and subtract, 3 and 4 cells
clb_neg_nc  A -> -A           3 cells  471 chars   256/256
    clb_sub_nc  A - B             4 cells  730 chars   65536/65536

Both are "invert, then add", which is all two's complement needs:

    -A      = ~A + 1
    A - B   = A + ~B + 1

so the carry cell starts at 1 (that bit is the +1) and each bit flips its input
with one flb right before the slice reads it.  Subtraction's carry out turns out
to be "no borrow": 1 when A >= B, so the same macro answers an unsigned
comparison for free.  Negation's carry is 1 only for A == 0, where -0 is 0 but
does carry out.

The bit level wrappers come along too: clb_bit_neg_nc (flb + clb_bit_inc_nc) and
clb_bit_sub_nc (flb + clb_bit_add_nc).

Tried first, and it does not work: a slice that inverts its own input.  The
table S = ~A ^ Ci, carry = ~A & Ci with 3 params answers

    r8asm: %synth clb_bit_neg_nc_synth: no program up to 8 layers

That is a model limit, not a search budget problem: a synthesised block
"sacrifices one cell, conditionally flips others", so when A is 0 the whole
block is skipped and S can only keep the 0 the wrapper gave it -- while inverting
needs S = 1 exactly then.  Unconditional flip is not expressible, so the flip has
to stay outside the slice.  Both facts are in the file comment and in AGENTS.md.

byte_op_test now covers nine operations, exhaustive, 0.72 s:

    raw_add/and/or/xor  65536 each      raw_inc  512
    clb_add_nc 65536    clb_inc_nc 256
    clb_neg_nc 256      clb_sub_nc 65536

macro_docs_test: 36 macros in 12 files, all in the house format.
2026-11-07 09:06:43 +08:00
dsh 4be8aa15ad Byte level add and increment with 4 and 3 cells: clb_*_nc
The nc slices do drive a rotation, so two more library macros fall out of them:

    clb_add_nc  A + B -> S, carry in/out in one cell   4 cells   693 chars
    clb_inc_nc  A + 1 -> S, carry in/out in one cell   3 cells   433 chars

against raw_add (6 cells, 1647) and raw_inc (5, 1214).  Both are in
r8forge_byte_op_test now, exhaustive: 65536 and 256 combinations, all pass.
clb_inc_nc has to start its carry cell at 1 -- that bit is the "+1"; the add
version starts at 0.  A rotation driver reads the low bit, throws it away and
rotates, so eating the operands is exactly what it wants.

This retracts a sentence that has been in the tree for a while: "rotation needs
A and B preserved".  It does not.  Preserving them is a separate wish (raw_*
grants it, with two more cells).  AGENTS.md said the wrong thing in the do not
retry list; that bullet now says what was really measured, which is only that a
4 cell slice asked to *preserve* A and B has no solution up to 8 layers.

Renamed for the same reason: bit_add_nc -> clb_bit_add_nc, bit_inc_nc ->
clb_bit_inc_nc, verify_add_nc.r8asm -> verify_clb_bit_add_nc.r8asm,
verify_inc_nc.r8asm -> verify_clb_bit_inc_nc.r8asm.  Measured what the prefixes
actually separate here:

    bit_raw_and  A=1 B=1 -> cells 0=1 1=1 2=1   operands preserved, has tmp
    bit_raw_add  A=1 B=1 -> cells 0=1 1=1 4=1   operands preserved, has buf
    clb_bit_and  A=1 B=1 -> cells 2=1           operands eaten, no tmp
    clb_bit_add_nc A=1 B=1 -> cells 2=1 3=1     operands eaten, no tmp

so raw means "the caller passes the scratch cell" and those variants happen to
keep their inputs, while clb means the inputs are gone.  These slices eat A and
B, so they are clb.

One self inflicted mess to own up to: I rewrote AGENTS.md with a PowerShell
Get-Content / Set-Content round trip, which on this machine decodes UTF-8 as GBK
and wrote the file back as mojibake.  Restored it with git checkout -- AGENTS.md
and redid every edit through the editor.  The work rule in AGENTS.md now names
that exact trap instead of only warning about -Encoding ascii.

Green: test.r8asm 1666, full_add 8/8, both verify_*.r8asm, byte_op_test
(65536x4 + 512 + 65536 + 256), macro_docs_test 32 macros in 10 files, fibonacci.
2026-11-07 09:03:08 +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 fc9b5e73e4 Byte level: the dead layer, with two reproducible probes
verify_set_0.r8asm is four characters of tape: set_0 only converges on 0 and 1,
so A=128 hangs.  drv/raw_add_byte.r8asm drives raw_add with operands that carry
no baked in constants -- asm/test.r8asm XORs 127 and 130 into the cells, which
made a first reading of the symptom easy to get wrong.

Measured with both: raw_add survives 0+0 and nothing else (1+0, 0+1, 1+1, 2+2,
5+3, 10+20, 128+0, 128+128, 255+1, 255+255 all hit the step limit).
2026-11-06 23:43:44 +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