master
143
Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
|
|
9b1a8fc0de |
ci: install cmake and g++ before configuring
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 1m25s
The runner image is a bare ubuntu with git and node but no cmake, so the very first step died with 'cmake: command not found' (exit 127). Every job now installs cmake/g++/make first and prints their versions plus the core count, which is also the environment snapshot the logs were missing. |
||
|
|
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.
|
||
|
|
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. |
||
|
|
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. |
||
|
|
692995af59 |
docs: the desk calculator's design and the order to build it in
ci / wide sweep (manual) (11) (push) Skipped
ci / wide sweep (manual) (24) (push) Skipped
ci / wide sweep (manual) (16) (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
ci / cell 8 (push) Canceled after 0s
ci / cell 16 (push) Canceled after 0s
ci / cell 32 (push) Canceled after 0s
Back to the RPN idea, but written down before any code: the command protocol (* + , - . / are exactly 0x2A..0x2F, digits 0x30..0x39, so one bit 4 test splits them and t = C - 0x2A is the command index), the memory map (working cells, a fixed 4 deep stack, library scratch, a pre-seeded constant block), the step budget per token, and the five stages with the driver each one gets verified by. Two decisions recorded there: EOF (0) ends the loop by erasing its counter, and the stack stays a fixed 4 cells -- .tp is an assembly time constant, so a moving stack pointer is the one thing this machine cannot do cheaply. |
||
|
|
c53d2c38f1 |
ci: no cron -- the wide sweep and the cache audit are manual only
ci / wide sweep (manual) (16) (push) Skipped
ci / wide sweep (manual) (11) (push) Skipped
ci / wide sweep (manual) (24) (push) Skipped
ci / wide sweep (manual) (8) (push) Skipped
ci / wide sweep (manual) (32) (push) Skipped
ci / cold cache (manual) (push) Skipped
ci / baseline (11 bit) (push) Canceled after 0s
ci / cell 8 (push) Canceled after 0s
ci / cell 16 (push) Canceled after 0s
ci / cell 32 (push) Canceled after 0s
Nothing changes in this repository every night, so a schedule only spends the runner's time (and the cold cache job re-searches every synthesised block, which is minutes, not seconds). Push and PR keep the 11 bit baseline + the 8/16/32 width matrix; the wide width sweep and the cold cache audit now run only from "Run workflow" (workflow_dispatch). The sweep matrix is trimmed to the widths that are actually verified (8/11/16/24/32); 1..4 bits of the library are not something we have evidence for yet, so they are not offered as a matrix entry. |
||
|
|
c0144a2fcf |
ci: wire CTest and give the runner a pipeline
ci / nightly sweep (1) (push) Skipped
ci / nightly sweep (11) (push) Skipped
ci / nightly sweep (12) (push) Skipped
ci / nightly sweep (16) (push) Skipped
ci / nightly sweep (2) (push) Skipped
ci / nightly sweep (24) (push) Skipped
ci / nightly sweep (32) (push) Skipped
ci / nightly sweep (4) (push) Skipped
ci / nightly sweep (7) (push) Skipped
ci / cold cache (push) Skipped
ci / nightly sweep (8) (push) Skipped
ci / baseline (11 bit) (push) Canceled after 33m54s
ci / cell 8 (push) Canceled after 0s
ci / cell 16 (push) Canceled after 0s
ci / cell 32 (push) Canceled after 0s
`ctest --test-dir build -j` now runs the whole baseline (8 entries, 9 s) instead of six commands typed from memory, and .gitea/workflows/ci.yml drives it: baseline 11 bits, full ctest on every push widths -DR8FORGE_CELL_SIZE=8/16/32, the `widthfree` label only nightly the width sweep for cell 1..32 plus a cold cache run The tests carry labels for that reason: `widthfree` means "true at any width" (bit level slices, the synthesizer, the looping demo, the macro comment format), while flagship / byte_ops / examples pin the 11 bit word (2047 style values, 8 bit era pair counts) and are only meaningful at the default geometry. Cold cache job: throw .r8forge_cache away and let the searcher find the blocks again -- it fails if the fresh results no longer match what the repo ships, which is the cheap version of "the cache is only recomputed when the search changes". Labels in the workflow are `ubuntu-latest`; change them if the self hosted act_runner advertises something else. |
||
|
|
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.
|
||
|
|
0d08fdc838 |
docs: collect every leftover TODO into one file
"Not done yet" was scattered: AGENTS had a five item candidate list, docs/divmod.md had a "no optimisation we skipped" section, README pointed at neither, and the tree carried one genuine code marker nobody had noticed -- src/r8asm.cc:154 still says "TODO: FILL THE BLANK" above the ROT8_NODE macro (inherited from upstream, so it is recorded rather than changed). TODO.md now holds all of it, each item with why it matters and where to start: interaction the desk calculator (input plumbing is already in place) tools --opt peephole + tape diff, --profile, %synth --verify, CI text/picture clb_puts + mini printf, 259 cells as a frame buffer skipped opts clb_divmod's ~D precompute, clb_digits layout, the 495 char copy not TODOs SPEC 12 "we already proved this cannot work" stays out of it AGENTS' candidate section shrinks to a pointer, README gains a row in both of its index tables, and docs/divmod.md 6 is linked from the optimisation entry instead of being rewritten. |
||
|
|
d9689f81ba |
asm: drop the design-story comments, leave the contract (and a pointer)
Seven files still opened with a paragraph about how they came to be -- "the first
version cleared the same bit four times", "the older repeated-subtraction divmod
needed 1.48M steps", "last round rejected shift-and-add because it was longer",
nested with measured step counts. None of that tells a caller how to use the
macro, and it is exactly the material that goes stale (raw_sub's figure had been
retracted, and the numbers are SPEC's job now). The stories already live in
docs/divmod.md and docs/byte-ops.md, so:
digits 119 -> 80 lines mul 125 -> 98
divmod 106 -> 80 inc_ip 81 -> 72
undigits 95 -> 73 raw_sub 52 -> 38
dec_ip 21 -> 18
Each now opens with two lines: what the macro computes and where the contract
lives (SPEC section, plus docs/ when there is a design write-up). Everything
from the `; Macro <name>` block down -- parameter types, preconditions,
what-is-eaten, the non-obvious invariants -- is untouched, which is what
r8forge_macro_docs_test checks and what a caller actually reads.
Baseline unchanged: tape 64513, 21 byte-op items, 15 examples, 48 macros.
|
||
|
|
ae268b9442 |
Interactive I/O: teach the VMs INP, and let examples declare their input
The library can read characters now that the viz defaults to serial ASCII, but
R8Forge's own machines could not: r8forge_derive, r8forge_tape_run and the
examples harness all skipped ',' ("input is not modelled"), so an interactive
program could only be run through ROT-8-viz -- the wrong end of the dev loop,
and nothing in CI could cover it.
Three small pieces:
* INP (',') reads the next scripted character (low 7 bits) and 0 once the
text runs out, in tests/tape_run.cc, src/derive.cc and the examples VM.
r8forge_tape_run and r8forge_derive take -i/--input "<text>", so an
interactive program is run and checked exactly like any other:
r8forge_tape_run t.rot8 -i "12+34="
r8forge_derive calc.r8asm 0 -i "12+34="
* examples_test learns an optional `; in ...` header next to `; out`:
the characters after the marker are fed to INP before the run. The marker
must be the first word after ';' so "include" in a comment is not eaten.
* examples/echo_chars.r8asm: the smallest interactive program -- read four
characters, print them back. in R8F! -> out 82 56 70 33, 8 characters,
8 steps.
Verified the same tape three ways: tape_run -i "R8F!" -> 82 56 70 33,
derive 0 -i "R8F!" -> same, rot8_test --input R8F! -> prints R8F. With no
input at all INP reads 0, which is how every non-interactive example keeps
running unchanged.
Baseline: examples_test is now 15 examples + asm/test.r8asm.
|
||
|
|
ebc7b7c72e |
docs: split the machine-local half of AGENTS.md into an ignored AGENTS.local.md
AGENTS.md was carrying two kinds of things: project facts (semantics traps, the do-not-retry list, baselines, pointers) and this-machine facts (the Visual Studio cmake path, PowerShell's GBK read-modify-write trap, the git identity and the sandbox elevation needed to push, the flaky %synth temp file, "put slow commands in the background"). Only the first kind belongs in a repo: a contributor on another machine gets noise from the second, and half of it goes stale the moment the box changes. So AGENTS.md keeps the project (124 lines) and points at AGENTS.local.md for the rest; AGENTS.local.md is gitignored, so a fresh clone simply re-creates it for its own machine. The commit identity rule stays in AGENTS.md (it is repo policy) and now defers the mechanics to the local file. No content is lost: the moved bullets are byte-identical apart from the framing. |
||
|
|
a82d95658e |
docs: one home per fact -- README as the front door, SPEC as the contract, AGENTS as the manual
The three documents had grown to 2038 lines and quoted each other: 2199 appeared
seven times, 3977 ten times, AGENTS carried a 200-line copy of SPEC's byte-level
tables while README carried another 155-line copy still showing 8-bit-era numbers
(clb_add_nc 688, clb_not_ip 17, ...) that are wrong at 11 bits.
Split by responsibility, keep every fact exactly once:
README.md front door: what it is, 30-second build+run, directory map, where
to read next 547 -> 143 lines
SPEC.md the contract: %synth, geometry, every macro's signature / cells /
tape length / who verifies it, test matrix, boundaries, maintenance
901 -> 807 lines
AGENTS.md the manual: hard rules, build and self-check commands, the traps,
current state, next candidates, do-not-touch list
590 -> 132 lines
Long-form reasoning moves into docs/ instead of being dropped:
docs/divmod.md the shift-restore division story (was SPEC 14, 102 lines;
renumbered 1..6, SPEC keeps a pointer and the references in
SPEC 7.6 and asm/divmod.r8asm now point there)
docs/byte-ops.md the byte-level design history (was README's 155-line section,
rewritten with 11-bit numbers since the old ones were
measured at 8 bits)
Also fixes what the dedupe exposed: SPEC no longer claims only the multiplier has
a step bound, and raw_sub's comment no longer repeats the retracted "1.48M steps"
figure. Every section reference in the tree resolves; the baseline still passes
(asm/test.r8asm 64513 characters, 21 byte-op items, 14 examples, 48 macros).
|
||
|
|
ad45823768 |
AGENTS/SPEC: cross-checks with ROT-8-viz now need -n
ROT-8-viz switched its default I/O to serial ASCII (cells >= 8 bits) with the old decimal numbers behind -n/--numbers, so the handoff notes that tell the next session to compare numeric OUT streams against rot8_test have to say -n. Also records the new commit hash of that repo (a083a34) and that its default is serial now, which is exactly what the ASCII from clb_digits wants. Checked: rot8_test.exe -n on the asm/test.r8asm tape gives the same 93 values as r8forge_tape_run. |
||
|
|
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.
|
||
|
|
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.
|
||
|
|
2e6d9cee86 |
asm/test.r8asm: call every macro, exercise every language feature
The old test.r8asm was a three round hash: `clb_add_nc` + `clb_mul`, nothing
else. It proved "add and multiply are enough for a hash" and it was the file
every session was told to check, but a regression in, say, clb_divmod or raw_sub
could not show up there.
It is now the library's kitchen sink instead: one call per standard macro,
grouped from the smallest to the biggest
A lib set_0 set_1 erase rol step back .anchor copy bit_copy
copy_to_buffer bit_copy_to_buffer clb_bit_mov
B bit slices clb_bit_add_nc clb_bit_inc_nc bit_raw_add/inc/and/or/xor
clb_bit_and/or/xor
C raw_* raw_add raw_inc raw_and raw_or raw_xor raw_sub (operands kept)
D clb_* clb_add_nc clb_inc_nc clb_neg_nc clb_sub_nc clb_not_ip
clb_inc_ip clb_neg_ip clb_dec_ip clb_nonzero clb_add_ip
E big clb_ones + loop/endloop, clb_divmod, clb_digits
F language a user %macro that uses %rep and %for, .var arithmetic,
two inline %synth blocks (map and stat, both cache hits)
G the old hash, now two rounds
Each call is followed by `output`, so the OUT stream is the fingerprint.
examples_test now runs this file too and compares it with the `; out` line in
the header (it already did that for examples/), which makes the file an actual
assertion instead of a length in the docs: an example that stops printing what
its header says fails the test.
Numbers: 58722 characters, 215169 steps, 100 values. r8forge_derive,
r8forge_tape_run and ROT-8-viz's rot8_test produce the identical stream (the
last six values are the hash: 1322 5 82 0 1786 94).
Two layout decisions come from that cross check:
* The tape has to stay under 65536 instructions: that is ROT-8-viz's
INS_SIZE (include/rot8/rot8.h) and read_tape truncates silently past it.
An earlier version of this file was 76047 and the viz stopped after 99 of
its 104 outputs, which is how the limit was found.
* So the hash keeps two rounds and the two rounds share one clb_mul scratch
block (erased in between) instead of carrying three separate ones.
The hash's own rules are unchanged: the multiplier stays 141 because it is the
historical value, not because small operands must sit in MUL any more.
SPEC 10.2, the AGENTS baseline/self-check/table and the README build snippet
are updated to the new numbers and to the 65536 limit.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
66ed7bc263 |
SPEC/AGENTS: why the bit level wrappers must keep their set_0
A question that came up: the %synth stat tables already carry every parameter's
initial value, so shouldn't bit_raw_* stop clearing its output cells first?
No -- and the reason is in the searcher, not in the table.
compress_stat_space() drops the bits whose initial value never changes the
target and canonicalises them to 0 in the start state. The bit slice tables
are periodic in exactly those bits (the old hand written implementation cleared
them before working, and the derived table records that), so the search never
had to handle "the output cell already holds a 1": the block is only proven for
a cleared cell. The wrapper's set_0 is what puts the call site inside the
block's domain.
Measured by removing all nine of them (seven wrappers plus clb_bit_or and
clb_bit_xor):
raw_add / raw_and / raw_or / raw_xor ... still 65536/65536 ok
clb_mul 62064/65536 wrong
clb_divmod 14742/16384 wrong
clb_digits 2048/2048 wrong (one of them HANGs)
The rotation driven macros survive because they write the result at bit 0 and
rotate it away immediately, so the output LSB is 0 anyway; mul and divmod copy
accumulators around and really do feed a 1 back into the slice. Dropping the
set_0 would save three characters per cleared bit, which is exactly why someone
will try it again.
Reverted the experiment and wrote it down: SPEC gains 3.6 (compression
semantics and this trap, with the numbers), 6.1 gets the pointer line, and
AGENTS gets an entry in the "already confirmed dead ends" list.
|
||
|
|
3f4149c9d0 |
examples: one runnable routine per macro group
SPEC is the contract and drv/ is what the tests sweep, but there was no place
that showed a reader how a group is actually used. examples/ now has one stand
alone program per group, each ending in output calls:
base_macros.r8asm S5 set_0 vs erase, rol/ror, copy vs bit_copy vs
clb_bit_mov, step
bit_adder.r8asm S6 4 bit ripple carry adder built from
clb_bit_add_nc, then bit_raw_add for the
preserving variant
byte_raw_ops.r8asm S7.1 raw_add/raw_inc/raw_and/raw_or/raw_xor/raw_sub,
printing the operands afterwards to show the
whole point of the family: they survive
byte_clobber.r8asm S7.2 clb_add/sub/neg/inc_nc (operands eaten) and the
S7.3 clb_and residue (240 & 204 -> B = 12)
byte_in_place.r8asm S8 not/inc/neg/dec/add_ip and clb_nonzero
sum_loop.r8asm S5.1 clb_ones + loop/endloop: 1+2+...+N, count from
data rather than from the assembler
mul_demo.r8asm S9 82*141 and 2047*2047
divmod_demo.r8asm S7.6 2047/10 and 2047/1 (the case that used to hang),
reusing the scratch block on purpose
digits_demo.r8asm S7.7 1234 and 7 -> four ASCII digits
Every header carries a `; out 1 2 3` line: the expected OUT stream, so the
file itself says what it prints. The new r8forge_examples_test target runs all
of examples/*.r8asm and compares that line with the real output (a file without
the marker counts as a failure), printing the tape length and step count on the
way. That makes examples the second place after byte_op_test that checks
behaviour instead of just "it assembles", and keeps the examples from rotting as
the macros change. The six %synth examples get the marker too: their inputs are
all zero, so they print 0 0.
All 15 examples pass. The values in the headers were checked with
r8forge_tape_run (the second interpreter) as well as the test's own machine.
Docs: SPEC S10.3 has the table and the convention, S11 gets the test row, and
README gets a short section plus the layout list. AGENTS records the examples
in the handoff baseline and the "verified" table.
|
||
|
|
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.
|
||
|
|
677878779a |
AGENTS: hand off the divider rewrite at the top of the file
A new session should not have to reconstruct the task from git history. The first thing in AGENTS.md is now the job: replace clb_divmod's repeated subtraction with shift-and-restore division, target 2047/10 going from 1.48M steps to about 35k with the tape staying near 4k. It names the first step (build and single step verify the R cross cell shift plus bit injection before anything else), the order that bit clb_mul got wrong twice, the second step (raw_sub + clb_bit_or/clb_bit_and for the commit logic), the acceptance list, the baseline commands that must stay green, and what not to touch. DEC SPEC 14 holds the derivation, and raw_sub (already in the library) is the piece that makes it possible. |
||
|
|
a2154ee9ac |
SPEC 14: the shift-and-restore divider, worked out before it is built
The divider rewrite is a multi-round build (the cross cell shift cost clb_mul two
reworks), so the design went into SPEC first. The one non obvious part is the
comparison: R needs W+1 bits, but it does not need a W+1 bit subtraction.
With R = (Rhi:Rlo) and D < 2^W, compute S = Rlo - D and Bo = (Rlo >= D) with
raw_sub, and then
commit (R >= D) is Rhi | Bo
the new high bit is Rhi & Bo
All four cases check out (Rhi = 0, Bo = 0 is exactly R < D, no commit). So a
W bit subtract plus one bitwise OR and one AND replaces the W+1 bit machinery.
Also recorded: the state layout, the per round skeleton, why N is rotated with
rol (it hands out the bits most significant first and restores itself after W
rounds), the four pitfalls, and the acceptance checklist (same 76 sample pairs
against the current clb_divmod, step counts before/after, and clb_digits going
from 1.48M steps to tens of thousands).
raw_sub (the previous commit) is what makes this possible at all: the divisor
has to survive every round.
|
||
|
|
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). |
||
|
|
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.
|
||
|
|
b962c345c8 |
clb_digits: derive the digit count from _CELL_SIZE
The round count was spelled out as four 1s in the counter; it is a function of
the cell width (L = floor(W*log10(2)) + 1, integer approximated as
W*30103/100000 + 1, which gives 3/4/5/10 for 8/11/16/32 bits), and r8asm
evaluates that inside %rep, so the counter now builds itself:
%rep _CELL_SIZE * 30103 / 100000
rol
set_1
%endrep
What is still spelled out is the shift chain (three copies with distinct
offsets), because each step names a different cell and r8asm has no %if, no
indexed %rep and no recursion -- it cannot emit L-1 different instruction
groups. So the macro is correct for _CELL_SIZE == 11 only, and the comment now
says so loudly: a 16 bit cell needs one more step and one more cell, otherwise
the result is silently wrong. Making it generic needs an indexed %for in the
assembler (or a ten cell region with a fixed nine step chain, which works at
any width but costs three thousand characters and six cells).
All eleven values still correct at 11 bits, 13743 characters with the driver.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
b89fcb0588 |
SPEC 5.1: do not replace an assembly time counter with clb_ones
Asked for, then stopped mid-flight: the tempting refactor was to build
clb_mul's round counter with clb_ones + loop/endloop instead of
%rep _CELL_SIZE { set_1; ror }. It is the wrong direction and worth writing
down so the next attempt does not get as far:
assembly time %rep _CELL_SIZE { set_1; ror } 55 characters
run time clb_ones (~770) + loop/endloop (~10) + building _CELL_SIZE
as a value, about 850 characters, 4 more cells, tens of
thousands of extra steps
Same for the alignment trap: %rep N { set_1; ror } leaves the run of ones at
the top of the cell, so biz sees bit0 = 0 and the loop never starts -- N < W
needs one rol after the %endrep. clb_mul only escapes it because its N is
_CELL_SIZE, i.e. the whole cell is ones.
|
||
|
|
3cfdad4313 |
loop/endloop: the other half of clb_ones, runtime loop counts
clb_ones turns a count into that many ones, and these two macros spend those ones
one per iteration, so a tape can loop a number of times that only exists at run
time:
clb_ones N C T F
loop C
... body ...
endloop C
\loop c\ is .tp c + biz + set_0 + ror: test the low bit, spend it, rotate the
next one into place. \endloop c\ is .tp c + rnz. No .anchor is used, so the
pair nests, and endloop puts dp back on the counter whatever the body did with
it; the body must not touch c, and c is all zeros once the loop is over.
Checked with verify_loop.r8asm (939 characters): N = 0..11 makes the body run
exactly N times, A = N and C = 0 -- including N = 0, where biz skips the body
entirely. Nesting checked too: an inner loop rebuilt from a copy of its count
gives NO * MI (11 * 11 = 121, and 0 when either count is 0).
One trap found on the way, written into SPEC 5.1: in .r8asm source a loop is
spelled biz/rnz, not [ / ] -- the brackets are the tape encoding, and writing
them makes the assembler say " unknown macro [ \.
|
||
|
|
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).
|
||
|
|
54ddf9b0e7 |
SPEC.md: the %synth grammar and every standard library macro's contract
R8Forge had no spec of its own: the language lives in r8asm_rev/SPEC.md, the assembler
and the search were documented in README.md, and the macro contracts were only in the
comments above each %macro. This adds SPEC.md, pointed at the standard library:
* what this spec covers and what stays upstream (so the two do not drift);
* the five parameter types, the naming prefixes/suffixes, and the measurement
convention for tape lengths (a minimal driver, contiguous cells, no output lines);
* %synth: the full grammar, what map and stat mean, the three metrics, the cache key
and kModelVersion rule, and the four limits (8 params, 8 layers, no byte level
tables, no unconditional flip);
* all 41 macros in asm/ in tables with signature, which cells they eat, cell count,
tape length and implementation (hand written or %synth block + its stat table);
* the warts: clb_and leaves B & ~A behind while clb_or/clb_xor are clean, layout being
silently ignored when its length is not params, and set_0 clearing one bit only;
* a verification matrix saying which test proves what, and the known dead ends.
Every number in the tables was measured for this commit with one uniform driver
(measure_macros.ps1 shape, deleted afterwards), e.g. clb_not_ip 22, clb_add_ip 722,
clb_mul 3964 minimal vs 3977 through drv/mul_byte.r8asm. AGENTS.md and README.md now
point at SPEC.md instead of saying the %synth docs only live in the README.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
6e67eb4678 |
The multiplier: shift and add, one bit at a time, 3977 characters
clb_mul was repeated addition -- add MC into the product, MUL times. That is
the shortest thing to write, but the runtime is proportional to MUL's value:
255 * 255 took 733428 steps, and 2047 * 2047 ran into the 5000000 step ceiling
and hung outright (tape_run: HANG after 5000000 steps). So the multiplier was
a ceiling on what any program could compute.
The new body is the plain binary multiplication from school: hold the
multiplicand, look at the multiplier's low bit, add the multiplicand into the
high half of the product when that bit is 1, then shift the whole product one
place right -- the multiplier lives in the low half of that register, so its
bits fall out one at a time. The loop runs _CELL_SIZE rounds whatever the
operands are, and the tape got shorter as well:
82 * 141 358586 -> 8374 steps
255 * 255 733428 -> 17785 steps
2047 * 2047 HANG -> 26123 steps
tape 5007 -> 3977 characters
(Step counts are the tape's own, with no trailing newline -- tape_run counts
one if the file has one, which is where the first draft of this message got
numbers two out.)
Counter, carry and cross cell shift are the three pieces that needed care:
* the round counter is _CELL_SIZE ones in NR, one eaten per round by
set_0 + ror -- the same trick clb_inc_ip counts rotations with, so "how
many rounds" costs no tape length, only runtime;
* the carry out of the W bit add is not scratch: it is the top bit of the
2W+1 bit shift register, and the next shift moves it into PH's top bit;
* (F:PH:PL) >>= 1 is a cross cell shift. ror all three, bring the bit to
inject down to bit 0 with rol, move it with clb_bit_mov, ror back. The
low pair (PH -> PL) moves first, otherwise PH's bit 0 has already been
overwritten by the carry.
And biz/rnz is a loop pair, not an if/else: a one shot conditional has to eat
the bit it tested (a trailing flb) or rnz jumps straight back. The first
version of this hung exactly there -- no output at all, counter still 0x7ff.
The bit eaten is PL's low bit, which the shift discards anyway.
r8forge_byte_op_test now sweeps 0..255 x 0..255 exhaustively (65536/65536 ok,
6.7s instead of 1.5s) instead of sampling 64 combinations: the cost no longer
grows with the multiplier, so sampling was the only reason not to. asm/
test.r8asm still prints 1322 1786 1600 5 94 127, now as 28729 characters and
57330 steps (was 31901 and about two million), and derive and tape_run agree.
AGENTS.md and README record all of it, plus one correction: the old note said
shift and add had been dismissed because "only tape length is the target". It
is in fact 1000 characters shorter, so the reason given was wrong -- the
tradeoff was not. What changed is the target function: the 5000000 step
ceiling is part of it, and a loop whose length does not depend on its operands
can still have a runtime that does.
|
||
|
|
9b326f3b4b | AGENTS.md: read the docs before touching anything | ||
|
|
2eb26b58d6 | Say which operand the multiplier loops on, and what swapping costs | ||
|
|
24bea4a2b5 | test.r8asm: a rolling hash, (h + c) * 141 mod 2048 over R8F | ||
|
|
330710aed4 | test.r8asm: 32x32 and 64x32, the edge of an 11 bit cell | ||
|
|
3c3e2b4779 | AGENTS.md: commit ROT-8-viz with -c, its local config keeps vanishing | ||
|
|
b80b626c66 | AGENTS.md: an old tape on a new cell width can loop forever | ||
|
|
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.
|
||
|
|
cfe56e164a | AGENTS.md: commit as dsh, not as the repo owner | ||
|
|
6e8e33e455 |
test.r8asm now multiplies as well as adds
The file was the library smoke test: it set up a few cells, called raw_add and
printed five values. It now also calls clb_mul and prints the two product bytes,
so one tape exercises both of the expensive paths and the self check runs a
result rather than only an assembly.
127 + 130 = 257 -> S = 1, Co = 1
200 * 200 = 40000 -> PL = 0x40 = 64, PH = 0x9C = 156
whole tape 5417 characters (was 1666)
Both interpreters agree on `out 127 130 0 1 1 64 156`: r8forge_derive from the
source and r8forge_tape_run from the assembled tape, 427343 steps.
The multiply half lives at cells 16 and up so it cannot disturb the add half, and
the file's existing cell layout is untouched.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
349b6d2748 |
tape_run --trace, and the dp rule that killed the two cell increment
r8forge_tape_run grew a `--trace` flag: it prints pc, instruction, dp and the first four cells before every step. Without it a wrong hand written macro is just "the answer is wrong"; with it the failure is one line, e.g. dp jumping to 1023 because a backwards move was emitted where the runtime was already there. That is what happened to the two cell in place increment I tried after the in place complement. It assembled to 155 characters (against 430 for the slice version) and got 129 of 256 inputs right -- every input whose low bit is 0, i.e. every input that never propagates a carry. The algorithm was fine; the macros were not. The rule it broke: dp is a compile time constant in r8asm while a `[ ... ]` body may be skipped at run time, so **every conditional body has to come back to its own condition cell** (net zero moves). Otherwise the taken and the skipped path leave dp in different places and every later `.tp` is off by one. The library already obeys this: set_0's body never moves, clb_bit_mov ends with `.tp before` and a `flb` that eats the condition on the way out. For a two cell in place add both candidate condition cells hold live data (A's bit is the result, the carry cell's bit is the carry), so each test first has to make its condition consumable, which means moving a bit through the spare bits of the carry cell and rotating it into place -- about eight characters of detour per bit. A correct version should land near 200-220 characters, still about half of the 430 character slice version, but it stays a hand written loop with subtle invariants. Not added to the library yet; the scratch files are gone. AGENTS.md now carries the dp rule under the instruction semantics section, next to the two `set_0` / `%synth` constraints it belongs with. |