26 Commits
Author SHA1 Message Date
dsh 1e7acc018e hardware: the 74LS machine gets a period bill of materials, and a mechanics plan
Two things: the TTL build is now the main target (Tang Nano looks too modern), and
the packer learned the format that makes the TTL build simple.

Format: r8forge_tape_pack --eprom writes one byte per instruction with the opcode
in the low three bits.  Then ip is the EPROM address and D2..D0 are the opcode --
no shift register, no 16 bit window, no decoder.  It wastes five bits per
instruction, and a 27C512 is exactly 64K, which is the historical instruction
budget: the 8 bit calculator (51378) and the flagship (43676) both fit.  Both
formats live in the same .r8t trailer now (format byte 1 = packed, 2 = one byte
per instruction), decode dispatches on it, and the test runs both and requires
the same output and step count.

Carrier: 74LS DIPs on a green board, 27C512 in a socket with its quartz window,
6116 SRAM, 74LS299 for the rotate, 6850 ACIA for serial, 74LS47 and four seven
segment displays on the panel, 1 MHz can oscillator.  About 31 to 40 chips, 400
to 700 CNY, a few weeks.  The FPGA stays as a bench-only stepping stone.

hardware/mechanics.md: where mechanics actually pays.  The program must stay
electronic (130 metres of paper tape for the calculator), and 512 relays for the
data ring are out, but the pointer is worth it -- > and < are 71 to 73 percent of
all steps, so a 64 position ratchet or uniselector makes the machine physically
walk the ring.  Also listed: an electromagnetic step counter (10 to 20 Hz, so
only in single step mode, with a clutch for free running), a paper tape punch or
plotter for output, a tape/card reader or plain keypad for input, and a hand crank
as the clock.  The rule that keeps this safe: mechanics only ever sit on sensor
and actuator pins and never in the logic path, and the handshake just stops the
sequencer while something moves -- since nothing in the ISA can observe time,
slower is not different.  A relay-only machine is priced honestly too: 60 to 120
relays, 10 to 50 Hz, hello in 10 to 40 seconds, the calculator in four hours, so
that one is an exhibit.

Also fixed: the synthesised macro fallback file name now carries a per-run token.
When the system temp directory is not writable every r8asm falls back to the same
working directory, so parallel ctest runs could write and import the same file --
which showed up as a random one-test failure in 0.39 seconds and nothing else.
2026-11-20 16:35:02 +08:00
dsh 9b31a51fec hardware: M0 -- the packer, the RTL, and a simulator that agrees byte for byte
The two things software cannot check by reading its own source are the 3 bit
packing and the bracket strategy, so both got a tool and a test.

New in the library (r8forge/tape.hh, src/tape.cc): the opcode numbering (taken
from ROT-8-viz enum, so the packed image and the hardware decoder cannot drift),
text <-> opcodes, opcodes <-> 3 bit bytes, the .r8t image with its trailer and
crc32, and a machine model that runs a packed tape the way a board would.  The
model takes the bracket strategy as an option: backward scan with loop stack or
not, and jump-back-onto-the-[ (the contract) or past it (what the interpreters
do).  All four combinations print the same thing, and the step count differs by
exactly the number of taken ] instructions -- which is what the test asserts.

Found and fixed while writing it: the loop stack discipline depends on the jump
convention.  Jumping onto the [ means the [ re-pushes, so ] must pop on the jump;
jumping past it means the entry must stay until the loop exits.  Mixing them up
emptied the stack on the second iteration of the calculator main loop -- caught
by the equivalence test on examples/calc.r8asm, not by reading the code.

Tools: r8forge_tape_pack (text tape -> image + --hex for $readmemh + --verify,
727 instructions become 273 bytes for hello, 62%, and the trailer sits past the
halt so address 0 of a ROM is instruction 0), and r8forge_tape_run now reads an
image directly and takes --loop-stack / --retest.

hardware/rot8.v: the 8 bit / 64 cell machine -- 3 bit opcodes from a byte
addressed memory read as a 16 bit window, a 6 bit dp with free wrap, the loop
stack bracket jump, blocking input, halt on ip == length, and a step counter that
counts instructions rather than cycles.  hardware/tb_rot8.v loads a --hex image
and prints the OUT stream in tape_run format.

Verified with Icarus Verilog 14 (the RTL against tape_run --loop-stack --retest):
  hello        577 instructions  417 steps  10 outs
  term         16414            17643      11 (fed "lhi")
  calc         51378           166741      19 (fed "12 34 + .": prints the prompt,
                                                046 and the next prompt)
  flagship     43676           100142      93
Every OUT stream identical.  ctest -R rtl_sim runs that comparison from an 8 bit
build (11 tests in the default build now, where the RTL test self-skips because
the RTL is the 8 bit machine).

Two traps worth remembering: Icarus passes plusargs through as raw bytes, so an
absolute +HEX path containing non-ASCII (this checkout is under a Chinese
directory name) arrives mangled, $readmemh silently leaves the memory empty and
the machine obediently runs LEN steps of opcode 0 printing nothing -- run vvp
from the directory holding the hex with a relative name.  And in_ready must not
be qualified with !in_valid or the input handshake deadlocks.
2026-11-20 16:25:54 +08:00
dsh 0c75772cbb geometry: the ring size becomes a build option, and the machine takes 64 cells
259 was never part of the machine, just the historical default, so
kDefaultMemoryCells is now R8FORGE_MEMORY_CELLS (1..65536, default 259) with a
range guard in CMake, the same way the cell width already worked.  All five VMs
read it from geometry.hh, so nothing else had to change.

Measured the highest cell each tape in the tree actually touches by walking its
> and < and recording the peak (no tape does a < at cell 0, so none of them
depend on wrapping): calc 51, hello 49, signed_demo 34, term 27, and the
asm/test.r8asm self test 155, because it lays every macro cell block out side by
side.  So a 64 cell ring runs every program we ship; only the self test needs
the default.

Verified: the full ctest suite is 8/8 at both 128 and 64 cells (11 bit); at the
hardware geometry of 8 bit plus 64 cells the widthfree label is 5/5, and the
calculator tape is byte for byte identical to the 259 cell build and its
sessions take the same 166348 steps.  The self test also produces identical
output at 64 cells but 216 more steps, because its high cells fold back onto low
ones -- which is why SPEC section 1.2 states the rule: ring size must be at
least the highest cell a program touches plus one.

Hardware payoff: at 64 cells dp is a 6 bit counter whose wrap is free, so the
TTL build loses its modulo-259 comparator logic (four to five chips), the RAM
needs 64 bytes, and the drum shrinks to 8 tracks by 64 cells (at 3000 rpm that
is 52 s for a calculator session, so it wants to spin faster).  hardware.md is
updated to the 8 bit / 64 cell machine throughout.
2026-11-20 15:34:03 +08:00
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 a56a12f132 r8forge --opt: the peephole pass is part of the assembler now
The pass moved out of tests/tape_opt.cc into src/tape_opt.cc with a header
(rot8_optimize(tape, cell_size)), so both entry points share one implementation:

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

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

Measured: flagship 64513 -> 58060 (-10.0%), calculator 62585 -> 54863 (-12.3%),
and "12 34 + ." still prints the same out stream from the optimised calculator.
ctest 8/8 still green.
2026-11-18 10:34:30 +08:00
dsh a69260522b geometry: kDefaultCellSize now really reads R8FORGE_CELL_SIZE
The build option was plumbed all the way to the compiler (the generated vcxproj
carries R8FORGE_CELL_SIZE=17) but geometry.hh still said = 11, so every width
built an 11 bit toolchain -- which is why the first matrix run printed identical
tapes for all nine widths.  My earlier '16 and 32 verified' claims were therefore
measurements of 11 bit binaries: synth_test and full_add are bit level blocks whose
tape does not depend on the width, so they never noticed.

Now at -DR8FORGE_CELL_SIZE=17: asm/test.r8asm 108789 characters (64513 at 11),
examples/calc.r8asm 112795 (62585), and one session prints '> 000046' -- D is 6 at
17 bits, which is exactly floor(17*log10 2)+1.

tests/widths.ps1 now prints the flagship and calculator tape lengths, because that
is the evidence that a width took effect; an unchanged 64513 means it did not.
2026-11-15 17:32:55 +08:00
dsh 90feedb37b 32 bit cells: widen the VMs to uint32_t, fix the mask at 32, make width a build option
All five R8Forge machines stored a cell in uint16_t, so anything above 16 bits
was silently truncated even though geometry.hh (and the viz) allow 1..32; and
`(1 << cell_size) - 1` for _CELL_MAX was undefined at 32.

  * cells and out/input buffers are uint32_t in derive, tape_run, byte_op_test,
    examples_test and synth_test (r8veritas*.hh keep their uint16_t search
    state -- that is node ids, unrelated)
  * kDefaultCellMask and the injected _CELL_MAX special-case 32 instead of
    shifting by 32
  * width is now a build option: -DR8FORGE_CELL_SIZE=<1..32> (CMake cache var,
    added as a compile definition), so a whole toolchain of another width is one
    configure away; build*/ is ignored so those trees do not leak into git

Verified: 11 bits unchanged (tape 64513, byte_op ok); a 16 bit build passes
synth_test 8/8 and byte_op_test (65536 exhaustive pairs); a 32 bit build passes
synth_test, verify_clb_bit_add_nc and assembles full_add to the same 95 chars.
Exhaustive 32 bit is 2^64 pairs -- that stays sampled, not verified.

SPEC 13 checklist now says five VMs / uint32_t / the 32 bit mask case.
2026-11-10 18:23:26 +08:00
dsh eacf6c01da r8forge: add -q / --quiet for a tape-only stdout
Assembling a library file prints one `%synth ...: cached, N blocks` line per
block (21 of them for asm/test.r8asm), plus search timings and the occasional
temp-directory notice.  That is useful when working on the searcher and noise
when the tape is the output:

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

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

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

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

SPEC 3.7, the README cost-model section and the AGENTS %synth list document it.
2026-11-08 00:24:51 +08:00
dsh b666799950 %synth: make the tape search thread count a run option (-j N)
The tape search always used std::thread::hardware_concurrency() workers with no
way to ask for fewer (or more).  It is now a run option like the cost model:

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

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

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

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

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

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

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

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

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

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

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

New cache entry c16bf083bb0ccbc8.txt is full_add's stat table with mode layers
+ flat, which full_add_stat.r8asm now produces.
2026-11-07 23:44:01 +08:00
dsh 91e3fed537 r8asm %for: repetition with a loop variable
clb_digits needed to name a different cell every round, which %rep cannot do: it
copies identical text N times and has no loop variable, and there is no %if
either, so the three shift steps were spelled out by hand and the macro was
only correct for 11 bit cells.

    %for k 3            ; k is 0, 1, 2 inside the body
        step k
    %endfor

%for <name> <count> binds <name> to 0..count-1 as a compile time constant that
any expression can use: %rep counts, .tp targets, macro arguments.  The loop
scope is a copy of the current scope plus the name, so a %for inside a macro
body still sees that macro's %1, %2, ...  %rep and %for nest in each other
(both closers count as a closer).  %rep itself is untouched.

With it, clb_digits lost its hardcoded chain: the digit count, the shift count
and now the constant builds (tails written as _CELL_SIZE - 5 / _CELL_SIZE - 3)
all follow _CELL_SIZE.  Checked at 16 bits with a five cell region: 4660 gave
'0' '4' '6' '6' '0' and 7 gave '0' '0' '0' '0' '7', so the count really did
become five.  65535 hangs in clb_divmod (6553 rounds, over the 5M step budget)
-- that is the divider's O(N/D), not digits.  Back at 11 bits everything is
unchanged: all eleven values, hash 28729, byte_op and docs green.

SPEC 3.5 documents the directive; it is a local extension like %synth.
2026-11-07 18:05:44 +08:00
dsh ac5810580d kDefaultCellBits -> kDefaultCellSize: the width is cell_size, not cell bits
The cell width is cell_size everywhere else now -- cell_size in the AST, in
ROT-8-viz's rot8_config, and the docs -- but the default in geometry.hh was
still kDefaultCellBits, and the four VMs spelled it that way too.

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

No behaviour change.  All six self checks re-run green: 28729 character hash
tape, synth_test 8/8, both verify_ tapes, byte_op_test (clb_mul 3977 chars,
65536/65536, "byte level library ok") and the macro docs test.  The hash tape
still gives 1322 1786 1600 5 94 127 from r8forge_derive, r8forge_tape_run and
ROT-8-viz's rot8_test -- three implementations, one answer.
2026-11-07 12:33:56 +08:00
dsh 94868be24f Name the two geometry numbers the same way everywhere: cell_size, cell_argc
The cell width was CELL_SIZE on the C++ side, and the searcher's CellBit count
was CELL_ARGC.  Both now match what the code and the docs around them already
called them:

  * include/r8forge/r8asm.hh + src/r8asm.cc: CELL_SIZE -> cell_size
    (set_cell_size assigns this->cell_size, its parameter already had that
    name);
  * include/r8forge/r8veritas.hh: the template parameter CELL_ARGC ->
    cell_argc, 34 uses, so the searcher reads r8veritas<cell_argc>;
  * AGENTS.md says which name means what, and why the name .r8asm programs
    see is still _CELL_SIZE: that one belongs to the macro library, not to
    the C++ side, and changing it would rewrite every macro in asm/;
  * the cross check entry now says which ROT-8-viz is which: the author's fork
    with --cell/--mem, and the upstream starcells/ROT-8 tree in the workspace,
    whose geometry is compile time cell_size/mem_size -- it is 11 / 259 too
    now, and `rot8_test <tape>` against `r8forge_derive ... -1` still gives
    1322 1786 1600 5 94 127 on the hash tape.

All six self checks pass unchanged: 28729 character hash tape, synth_test 8/8,
both verify_ tapes, byte_op_test 65536/65536 for clb_mul and the rest of the
library, macro docs test green.
2026-11-07 12:23:42 +08:00
dsh 62c6f8979f Cell width and tape length: 11 bits, 259 cells, by default
The assembler already took the width as an argument (import_file(path, cell_size))
and exposed _CELL_SIZE / _CELL_MAX / _ROL_STEP to programs, so every macro that
writes %rep _CELL_SIZE follows the width on its own.  What was missing was a
single place saying what the default is, and VMs that agree with it.

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

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

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

Results at 11 x 259:

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

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

AGENTS.md gains a section on how the width flows through the tools, including
the trap that 2048 % 256 == 0 makes several 8 bit expectations still pass by
accident.
2026-11-07 10:56:28 +08:00
dsh 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 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 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 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 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