143 Commits
Author SHA1 Message Date
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 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 adb3c8d71a bit_raw_add_nc is now bit_add_nc, and here is a 3 cell increment slice
The rename: the four cells of that slice all carry meaning -- A and B are
inputs, the third is a carry that is read on the way in and written on the way
out, the fourth is the sum.  There is no scratch cell, so SPEC.md's `raw`
("the caller passes the scratch cell") does not apply and the name now says so.
Measured before renaming: A=0 B=0 carry-in=1 gives S=1, so the cell is an input,
not a spare.

The cache survived the rename because the key is model version + params + mode +
metric + the resolved table (src/synth.cc), never the block name:
"bit_add_nc_synth: cached, 5 blocks".

verify_raw_add_nc.r8asm is now verify_add_nc.r8asm.

New asm/raw_inc_nc.r8asm, asked as an experiment ("can we even make one"):
bit_inc_nc, a 3 cell increment slice -- A, carry in/out, S -- three parameters
instead of raw_inc's five.  Table 0 4 4 2 0 4 4 2 resolved to a 4 block program
that was already in the cache, emitted tape is 54 characters, and all four input
combinations check out:

    A=0 carry=0 -> S=0 carry=0      A=1 carry=0 -> S=1 carry=0
    A=0 carry=1 -> S=1 carry=0      A=1 carry=1 -> S=0 carry=1

so S = A ^ Ci and the carry becomes A & Ci, with A eaten -- the same shape as
bit_add_nc, and like that one it cannot drive a byte level rotation (the operand
is consumed).  verify_inc_nc.r8asm drives it.

AGENTS.md: the two slices are in the self check list, the verified table and the
naming table; the "every macro" doc check now counts 30 macros in 10 files.
2026-11-07 08:53:25 +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 0fa30baf47 AGENTS.md: how to push from this machine
schannel fails here with SEC_E_NO_CREDENTIALS, so fetch and push both need the openssl backend; that is already set in this repo's local config.  The credential helper additionally needs a one time escalation, because it opens a named pipe and the sandbox refuses it (couldn't create signal pipe, Win32 error 5).  Fetch works without it: the repository is readable anonymously.
2026-11-07 00:12:00 +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 417b428cea AGENTS.md: the naming rules come from SPEC.md, not from habit
The old text said "a macro that exposes cells as parameters must have raw in its
name".  SPEC.md (r8asm_rev-fork/SPEC.md, identical in r8asm_rev) says something
else:

    clb  clobber  destroys its input (usually clears it)
    bit  bit      works on the LSB of a cell
    raw  raw      unwrapped; the caller passes the scratch cell

So raw_add is called raw because you hand it the Co and tmp cells, not because
it takes cells at all, and bit means every CellBit parameter is a low bit -- the
same fact as biz/rnz testing & 1, which is what went wrong last round.

Record the three prefixes, apply them to the existing library, note the two
macros that predate the rule (bit_copy and copy take a buffer without raw in the
name), and point at the two documents that actually define the language: SPEC.md
and the instruction table in ROT-8-viz/README.md.  %synth is not in the spec --
it is this repository's own extension, documented only in README.md.
2026-11-07 00:05:38 +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 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 505ff509eb Rotation and synthesised slices do not mix; naming fixed
Tried the rotating byte level driver with the 4 cell slice.  It cannot work, and
the search says why: rotation needs A and B preserved, because every round reads
their current bit, while a synthesised program consumes its operands.  Rewriting
the table to keep A and B and letting %synth search it gives

    no program up to 8 layers

so 'read without destroying' does not exist in this block model at four cells.
The hand written bit_raw_add can do it (loops), which is exactly why the original
library rotates inside the macro and the synthesised one cannot.

What is committed instead:

  asm/raw_add_nc.r8asm   bit_raw_add_nc, the destroying 4 cell slice, flat cost
                         27 against bit_raw_add's 38, with the naming and the
                         comment format of lib.r8asm:

                            ;   Macro bit_raw_add_nc
                            ;   %1: CellBit A
                            ;   %2: CellBit B
                            ;   %3: CellBit Ci
                            ;   %4: CellBit S

                         The synth body is named bit_raw_add_nc_synth, so the
                         'raw' in the name marks the macro that takes cells.

  verify_raw_add_nc.r8asm  feeds A, B, Ci to one slice and prints sum and carry:
                         8/8 combinations correct, 78 characters.

The rotation limitation is written into the file header so it is not retried
blind, and the library still assembles from cache (1666 characters, 7/7).
2026-11-06 23:24:27 +08:00
dsh c6bfaca349 Drop the bit per cell adders, keep the slice
Splitting every bit into its own cell bought nothing: the 25 cell adder was a
workaround for a workaround, and it made the cell count worse than the hand
written library it was meant to improve on.

Removed: raw_add_nc (5 cell, broken driver), raw_add_nc3 (the 3 cell dead end),
raw_add_bits4, raw_add_bits8, raw_inc_bits8, verify_add8, verify_inc8.

Kept:
  asm/raw_add_nc4.r8asm            the 4 cell slice, flat cost 27 against the
                                   6 cell full adder's 38, with the two
                                   constraints written down (only the low K bits
                                   are modelled, and set_0 only converges on 0/1)
  verify_bit_add_nc4.r8asm         driver that feeds A, B and the carry to one
                                   slice and prints sum and carry, 8/8 correct

The byte level stays with the hand written library, which rotates inside the
macro and keeps whole bytes in a cell; that is 6 cells for an 8 bit add instead
of 25, at the price of not being synthesised.  %synth earns its keep on the small
bit macros (asm/test.r8asm 1714 -> 1666 characters), not on byte level tables
where the 2^16 entry truth table would be hopeless anyway.
2026-11-06 23:17:19 +08:00
dsh d480c001b1 Three cells for the destructive slice: tried, impossible here
Writing the sum back into A's cell would drop the separate S cells and cost no
extra instructions -- the driver would even get simpler.  So it was worth
trying, and it does not work: %synth reports

    no program up to 5 layers

and raising the layer bound to 8 does not help either:

    no program up to 8 layers

So the obstacle is not runtime cost, it is feasibility: three cells cannot do
' two inputs plus a carry in -> a sum plus a new carry' in this instruction
model, the same class of limit that stopped clb_bit_and.  Keeping the four cell
slice (and the 25 cell bit-per-cell adder) is the right call, and the file is
committed with that conclusion written into it so nobody retries it blind.

The layer bound is now 8 rather than 5 (src/synth.cc), since 5 was low enough to
call some feasible tables impossible; a feasible table still costs the same,
only a hopeless search takes 60% longer before giving up.

Cache untouched: restored from git after the experiments, asm/test.r8asm still
assembles from it in a fraction of a second, 7/7 hits, 1666 characters.
2026-11-06 23:09:45 +08:00
dsh 32b16eb077 Base addresses instead of 25 parameters
The eight bit adder took 25 macro arguments because every cell address was
passed in.  That was laziness: .tp accepts expressions, so the macro can take
four base addresses and add the offsets itself.

    raw_add_bits8 0 8 16 24     ; A0..7 at 0, B0..7 at 8, S0..7 at 16, carry at 24
    raw_inc_bits8 0 8 16        ; a0..7 at 0, s0..7 at 8, carry at 16

The bodies are unchanged apart from '%1 + 1' style addresses, so the tapes and
the behaviour must be identical, and they are: add8 still 2550 characters, inc8
still 1514.

Re-verified after the change, on the built in machine:
  add8  7 sums (100+50, 128+127, 200+55, 43+199, 255+0, 1+1, 0+0)  7/7
  inc8  7 values (0, 1, 5, 127, 200, 253, 254)                     7/7

Also committed two verify_*.r8asm drivers so the numbers are reproducible.
2026-11-06 23:07:09 +08:00
dsh 1b8ff08455 Eight bit adders and increments, one bit per cell
raw_add_bits8   A0..A7, B0..B7, S0..S7, carry = 25 cells
raw_inc_bits8   a0..a7, s0..s7, carry       = 17 cells

Both follow the same protocol as the four bit version: no rotation, every cell
holds a single bit, one slice per bit, and the final carry is dropped because
the caller promises the result fits.

The increment slices down to 3 cells -- a, carry (in -> out), s -- and %synth
finds cost 25 in 4 blocks for it: s = a^Ci, carry = a&Ci.  Its table was written
as 8 entries because a 3 parameter stat line wants 2^3 values, and the s bit in
the index does not matter, so the four entry pattern repeats.

One mistake worth recording: set_1 takes no arguments and acts on the current
cell, so 'set_1 %17' silently did nothing and the carry started at 0 instead of
1 -- which made 1+1 give 1 instead of 2 while 42+1 and 200+1 looked fine, since
only the low bit was affected.  The driver now does '.tp %17' then 'set_1'.

Verified on the built in machine:
  raw_add_bits8  9 sums (100+50, 128+127, 200+55, 254+1, ...) 9/9
  raw_inc_bits8  9 values (0, 1, 5, 15, 127, 200, 253, 254, ...) 9/9

Tapes: 2550 and 1514 characters.
2026-11-06 23:02:09 +08:00
dsh 7cf2fabeb7 A bit per cell adder, and it works
The chained version kept every bit in one cell and rotated, which broke the rule
that set_0 needs a cell holding 0 or 1.  This one gives each bit its own cell
instead:

    %1..%4  A0..A3      %5..%8  B0..B3
    %9..%12 S0..S3      %13     carry

    erase carry
    bit_add_nc4 A0 B0 carry S0
    ... one slice per bit, no rotation at all
    last carry dropped (assumes A+B fits)

No rotation means every cell stays a bit, which is the invariant set_0 needs.
Verified against the built in machine over eight sums including 0+0, 1+1,
15+0 and 9+6: 8/8 correct, and the cell dump after a run shows only the S bits
set, so the operands and the carry are consumed as the table says.

Cost: it needs three cells per bit plus the carry (13 for 4 bits, 25 for 8)
instead of 4 rotating cells, and the expansion is longer because each slice now
has a fixed pair of operands.  That is the price of not breaking the invariant,
and it is why the original hand written library rotates inside the macro instead:
it keeps whole 8 bit cells and loops over the bits itself.
2026-11-06 22:06:58 +08:00
dsh cbadc3936a Document what set_0 really is
Checked instead of assuming, and it explains the chained hang:

    '-'  flb  flips bit 0                    cells[dp] ^= 1
    '['  biz  if the cell is zero, jump past the matching ']'
    ']'  rnz  if the cell is not zero, jump back to the matching '['

so set_0 = [ - ] is 'while the cell is not zero, flip its lowest bit', which only
terminates for 0 and 1.  Measured with the cell dump: X=5 goes 5 -> 4 -> 5 -> 4
until the step limit, X=0x80 never changes, and in both cases the tape never
reaches the next instruction.  erase = %rep 8 { set_0; ror } hangs on the same
set_0, so it cannot clear an arbitrary cell either.

That is the whole story of the 8 bit chain: after a slice and a ror the S cell
holds 0x80, the next wrapper calls set_0 on it, and there is no way out.  The
slice itself is fine, as the dump showed (A and B fully cleared, carry a clean
0/1).

Consequence: a cell always holds one bit in this world, so clearing has to
happen while it still is a bit, not after it has been rotated out.
2026-11-06 22:04:46 +08:00
dsh 13b831ec8b A 4 cell adder slice: the carry borrows the scratch cell
Asked why the slice still needs 5 cells.  It does not: the scratch cell was
doing nothing the carry could not do, so the 4 cell version is

    p1..p4 = A, B, carry (in -> out), S

and the table says S = A^B^Ci, carry = AB|AC|BC, A and B consumed.  %synth
finds cost 27 in 5 blocks for it -- the same tape length as the 5 cell version
(cell count is not part of the cost metric, only the instructions are) but one
cell cheaper, 73 characters for a single slice.

All eight input combinations verified through the built in machine.

Diagnosis of the chained hang, from dumping the cells after one slice plus the
ror rotation:

    A=1 B=0  ->  cells: 4=80        (only the rotated sum bit survives)
    A=1 B=1  ->  cells: 1=1         (only the carry)

so a slice leaves A and B fully clear, and the carry is a clean 0/1.  The dirty
one is S: after the rotation its bit 7 is set, and set_0 in the next slice does
not remove it -- the dump after two slices shows 4=81 and, worse, the tape then
runs off the end instead of reaching 'output S'.

So the fix is not in the slice but in the driver: it must not rotate the sum
into a cell that the next slice clears, or must clear the whole cell (set_cell,
not set_0 over the modelled bits).  That is the next step, together with
re-checking whether set_0 is the right primitive here at all.
2026-11-06 21:31:04 +08:00
dsh 18bf78273e A 5 cell adder that ignores carry in and out
The idea: for an adder whose operand sum is known not to overflow, there is no
need for a separate carry in cell or a carry out cell -- the carry can live in
one cell and be overwritten each bit, and the final carry is simply dropped.
That takes the slice from 6 cells (A, B, Ci, S, Co, tmp) down to 5 (A, B,
carry, S, tmp).

The slice was not hand written: the table was derived from S = A^B^Ci and
carry = AB|AC|BC, and %synth searched it with metric flat:

    bit_add_nc_synth: tape cost 27 in 5 blocks   (1891406 states)
    bit_raw_add_synth (the 6 cell full adder):   tape cost 38 in 5 blocks

so 11 units of the metric cheaper, about 29%, plus one cell less per slice.

Verified: all eight input combinations of a single slice are correct through the
built in machine (A, B, Ci -> S), including the all zero one.

Known limitation, found rather than guessed: the synthesised program only
touches the low K bits of each cell, the bits the truth table knows about.  The
caller therefore has to hand it cells whose high bits are zero.  Chaining slices
with ror breaks that: the rotated cell keeps bit 7, and a block that loops until
its cell reaches zero can never get there.  So the 8 bit raw_add_nc hangs; the
slice itself is fine, the driver needs to move each bit into a clean cell first.

Also added: r8forge_derive <file> -1 addr=value ... runs a tape with chosen cells
and prints OUT, which is how the slice was checked.
2026-11-06 21:19:19 +08:00
dsh b1a8ca5617 Unmangle the two flat examples
Full_add_flat.r8asm and full_add_flat_spaced.r8asm had their comments turned
into question marks: they were written through a PowerShell Set-Content with
ASCII encoding, which cannot represent Chinese and substitutes '?'.  Rewritten
as UTF-8, with the comments saying what the files are for.

Both still assemble from cache (95 characters) and still produce the same tape,
which is the point of the layout free metric.

A scan of the whole tree for '???' now comes back empty.
2026-11-06 21:10:17 +08:00
dsh e5d87791e0 Rename per request: CELL_SIZE is the machine width, CELL_ARGC the parameter count
r8asm::ast::CELL_SIZE        machine word width in bits, run time value
                               (import_file's second argument, 8 in the CLI)
  r8veritas<CELL_ARGC>         how many parameter cells a synth block has,
                               compile time, selected by 'params N'

set_cell_bits went back to set_cell_size for the same reason, and the .r8asm
visible names (_CELL_SIZE, _CELL_MAX, _ROL_STEP) are unchanged, so lib.r8asm
keeps working as written.

This time the string literal used by %rep and by the .xor masking is the one
the C++ member is now called too, which removes the trap the previous rename
walked into.

Regressions after the rename:
  asm/test.r8asm                  exit 0, 1666 characters, 7/7 cached
  examples/full_add_layers.r8asm  eight combinations ok
  derive bit_raw_add              same table as the hand written version
  clang-cl build of all five targets, and the clang built binaries produce the
  same 1666 character tape and the same table.
2026-11-06 20:27:49 +08:00
dsh 7d259b1c6c Rename the two different 'CELL_SIZE's so they stop being confused
There were two unrelated things under one name:

  r8asm::ast::CELL_BITS   the machine word width in bits, a run time number
                          (import_file(path, 8)), used by %rep and the .xor
                          argument masking
  r8veritas<PARAMS>       how many parameter cells a synth block has, a
                          compile time template argument selected by 'params N'

The first is now CELL_BITS, the second PARAMS.  What a .r8asm program sees does
not change: _CELL_SIZE / _CELL_MAX / _ROL_STEP keep their names, because
lib.r8asm uses them.

Answering the actual question along the way: the machine word width is a run
time parameter (import_file's second argument, hardcoded to 8 by the CLI), not a
template argument -- the comment in r8asm.hh even apologises for that.  The
synth block's 'params N' is the other one, and only that goes through the
template switch (1..8).

The first attempt at the rename also rewrote the _CELL_SIZE string used by %rep
into _CELL_BITS, so the lookup threw and the assembler died with a fastfail on
any file containing .xor or %rep.  Caught by regressing test.r8asm (exit
0xC0000409, no tape); the string is restored and asm/test.r8asm is back to 1666
characters with all seven blocks cached.
2026-11-06 20:14:49 +08:00
dsh e18827580f Cache key: fix a collision and pin the model version
Asked whether the cache survives a change of CELL_SIZE, and looking at the key
turned up a real problem.

The key used to be params | mode | metric | the stat line's values | layout.
Every block in asm/ uses a stat line, which is why nothing had gone wrong yet,
but a block written with map leaves stat empty -- so two map blocks with the
same params/mode/metric hashed to the same entry, and the second one would have
been served the first one's program.

The key is now the resolved target table itself (every entry, per plane), which
is exactly what the search is given:

  * params / CELL_SIZE is part of it, and the table covers all 2^params entries,
    so blocks of different sizes cannot collide, and changing params in a block
    simply misses and recomputes
  * two blocks that describe the same table (map or stat, either spelling) now
    share one entry

Also added kModelVersion to the key.  Without it, changing the instruction
model later (say adding conjunctions) would keep serving programs that were
optimal for the old model.  Bump it whenever the block set changes.

Cache files now start with a readable header, e.g.

    # params 3 mode 0 metric 1
    0 2 0
    1 4 0

Re-warmed after the change: 7 entries, 885s (bit_raw_add again, 990M states).
asm/test.r8asm still 1666 characters, all seven derived tables still match the
old implementations bit for bit, and a second assembly hits the cache for all
seven and produces an identical tape.
2026-11-06 19:59:12 +08:00
dsh 5f92d288c9 Finish the library warm up: bit_raw_add now optimises instead of falling back
The flat metric goes deeper than the exact one did (415M states for the full
adder), and 700M was not enough for bit_raw_add: it ran out, fell back to the
layer answer and cached that.  The box has 64 GB, not the 32 I assumed, so the
ceiling is now 1.5B states (~22 GB) and the search completes:

    bit_raw_add_synth: tape cost 38 in 5 blocks, 990,636,137 states, 680s

Same tape length as the fallback happened to give, but now it is actually the
minimum of the metric rather than whatever the layer search reached.

All seven cached bodies were re-derived against the old implementations after
the switch and still match bit for bit (bit_raw_add 0 9 10 19 12 21 22 31
repeated, bit_raw_inc 0 5 6 11, clb_bit_or 0 4 4 4, clb_bit_xor 0 4 4 0, ...),
so the shorter tapes are a free win.  asm/test.r8asm: 1674 -> 1666 characters,
and assembling it from the committed cache takes 0.5s.
2026-11-06 19:24:41 +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 505fe8af86 Make it build under clang
Found with scoop's llvm 23.1.5 (clang-cl), which is stricter than MSVC about
non-type template arguments:

    candidate template ignored: substitution failure: deduced non-type
    template argument does not have the same type as the corresponding
    template parameter ('unsigned long long' vs 'int')

block_cost deduced its N from std::array<int, N>, and that deduces size_t;
clang refuses to convert size_t to the int parameter, MSVC allows it.  N is now
size_t.  Every target (r8forge, synth_test, derive, cost_par, cost_search)
builds clean with clang-cl and the clang-built binaries assemble test.r8asm to
the same 1674 characters, pass the eight combination check and derive the same
bit_raw_add table.

Two other portability fixes in the same pass:
  * cost_search used _strtoui64, which is MSVC only -- now std::strtoull
  * the CMake project now finds Threads and links Threads::Threads, which
    clang and MinGW need to pull in the thread runtime
  * if spawning a worker throws (no thread runtime available) the search now
    carries on with the threads it did get instead of failing
2026-11-06 13:54:46 +08:00
dsh 0bc5f1e6b8 Phase-parallel tape search: 22 minutes down to 2.7
The sequential search is memory bound on its hash table, so the split that
works is inside a Dial bucket, not across the graph:

  * the table is read only for the whole bucket, so threads probe it with no
    locking -- 99.7% of the work, since only about one edge in four hundred
    lands on an unseen state
  * misses and dist improvements are buffered per thread and applied by one
    serial pass after the bucket

Cost order is untouched, so the answer is identical.  Measured at limit 60:

    threads   wall      states
    1         12.40s    7,671,626
    8          2.68s    7,671,626
    16         2.20s    7,671,626
    32         2.14s    7,671,626

and at the full limit 82 (the run that used to take 1350s): 162s, 414,631,673
states, cost 75 in 6 blocks -- the same program.

%synth now uses this by default.  examples/full_add.r8asm assembles in 166s
instead of ~23 minutes and still produces the 90 character tape, checked on the
machine for all eight combinations.

The earlier attempt -- one worker per possible first block -- stays in
r8veritas.hh behind opt.threads but off by default; it duplicated the middle of
the graph and cost three to four times the work.
2026-11-06 13:24:09 +08:00
dsh 5b492b4ef5 Parallel cost search: measured, and left off by default
Tried the obvious split -- one worker per possible first block, since a
program's first block is unique and the answers cannot overlap -- and measured
it on the full adder at limit 82:

    workers   wall    total CPU   peak memory
    1         1350s    1350s       11 GB
    8          ~10min  4600s       14 GB
    32         --      4870s       17 GB

So the answers do not overlap but the *search* does: every prefix walks into the
same middle of the graph, and with a table per worker that middle is explored
once per worker instead of once overall.  Three to four times the work and more
memory, for a modest wall clock win.

Kept the code (opt.threads > 1) because it is correct and it is the right shape
for a machine with more memory, but the default is one worker.  The parallel
split that should actually pay off is inside one shared table: expand the
current Dial bucket across threads, insert through a sharded table.  That is
the next attempt, not this one.
2026-11-06 11:40:07 +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
dsh 19cbfb36f6 R8Forge: assembler and searcher in one repo, %synth directive
The searcher stops being a separate program: %synth is an assembly-time
directive.  It describes a truth table, the assembler runs the search while
parsing, and the block list comes back as ready-to-paste r8asm.

Merging is what makes the cost model honest.  The price of a layer is
  cost = 2 (biz + rnz) + sum(move distance + op cost)
and the move distance depends on the call site's cell layout, not on anything
the assembler knows in advance: the same five-layer adder is 87 characters
with the cells adjacent and 136 with them two apart.  Only the side that sees
the layout can price it, which is now the assembler itself.

Working: the assembler (asm/test.r8asm still assembles to the same 1714
characters), the searcher (bit planes + backward one-step lookup, full_add in
5 layers, proven shortest in 7.2s), and %synth parsing plus the search itself.
Not working yet: splicing the synthesised body into the tape -- a synth call
fails loudly with 'unknown macro' instead of emitting anything, so nothing can
silently assemble wrong.  The two ways to finish it are in the README.

Also carries over the CMake fix: no set(CMAKE_CXX_FLAGS ...), which used to
drop /EHsc, push -O3 into Debug and fight /RTC1.
2026-11-05 23:59:15 +08:00