master
50
Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
|
|
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. |
||
|
|
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.
|
||
|
|
5c414292d2 |
calc: a terminal front end -- echo, backspace editing and a prompt
The calculator now behaves like the terminal tape from the previous commit:
every character is echoed, backspace edits the digit window, Enter commits the
line and prints the next prompt, and '.' puts its result on its own line:
> 12 34 + .
0046
> 12<BS>3 .
0013
> ^D
It is not the terminal's line buffer moved over: the calculator consumes one
character at a time, and replaying a buffered line would mean unrolling the
engine once per buffer cell, which does not fit. Line editing here is the
digit window: backspace shifts it right by one, pads a '0' in front, echoes
"space, backspace" and keeps accumulating.
Three things had to be learned the hard way, all recorded in docs/calc.md ?8:
* a borrowed constant cell gets eaten. KBS (the 8 that backspace subtracts)
lived in SC+5, and the operator step erases SC..SC+6 wholesale, so the first
byte after an operator was treated as a backspace -- every character of
"12 34 + ." came out as an erase. It is now loaded right before each use.
It also must not borrow R: the EOF test writes R every round.
* set_1 only forces the low bit; cells lent to the classifier have to be
re-initialised each round rather than assumed clean.
* the prompt after Enter has to be printed before the command dispatch and the
operators run, because EH (the "this was Enter" flag) borrows SC+3, which
mul uses as scratch -- the first version printed a prompt after every
multiplication.
The tape went 64983 -> 73624 characters (+8.6k: three copies for the window
shift alone are ~4.4k, the two subtracts ~3k). That is past the old
ROT-8-viz INS_SIZE of 65536; the current VM sizes its buffer from the tape and
runs 112802 characters at 16 bits and 336304 at 32 bits, so only the
historical budget is gone, not the ability to run it. Ducking under 65536
again would mean dropping line editing: echo plus the Enter prompt alone is
about +2.5k, still over.
Verified: ctest 8/8 (examples_test checks the new header stream), the width
matrix at 11, 16 and 32 bits (calc stream, terminal tape and the viz's serial
output all agree; 73624 / 112802 / 336304 characters), and docs/calc.md records
step counts for the whole session list -- "12 34 + ." is 287589 steps, about
17% more than before the front end.
|
||
|
|
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. |
||
|
|
d2da61a255 |
build: include <cstring> in asm_test.cc
std::strcmp needs it; MSVC pulls it in transitively so the Windows build never noticed, but GCC 16 rejects the file. Found while trying to build a 32 bit toolchain on a Linux box to time the %synth cache. |
||
|
|
c417304140 |
term: a line-editing terminal -- buffer, backspace and command dispatch
examples/term.r8asm was a per-character echo (prompt, echo, backspace erase, newline, EOF). It is now a small shell: a 4 character line buffer, a backspace that really removes a character, and Enter -- or EOF, for a half typed line -- commits the line and dispatches on its first character. 'l' prints the length, 'r' prints the buffer backwards, 'q' quits, anything else is ignored. The header session "lhi" exercises the whole chain: EOF commits the pending line, so examples_test sees the '3'. Three more sessions are documented in the header: "rab" gives NUL+'b'+'a'+'r', "lab<BS>" gives '2' (the backspace really dropped the 'b'), and "lhi<NL>rxy<NL>" prints '3' then the reversed second line. Three things ate most of the debugging time; all three are written up in the file: * "else" needs a flag cell. biz enters when the low bit is set, so "if not A then B" cannot be inferred from "the last test missed": set FLAG=1 before the test, clear it in the matched branch, look at FLAG afterwards. And biz tests the CURRENT dp cell, so the order has to be "set FLAG, then .tp to the condition cell, then biz" -- the wrong order made every character look like a commit key. * clb_sub_nc eats its operands, so the echo and the append both work from the copy CE. The first version appended C (already zeroed by the comparison), which left the line buffer empty: 'l' printed 0 and 'r' printed four NULs. * the cell layout dominates the tape. copy / clb_sub_nc / clb_nonzero all emit .tp internally, some of them inside %rep _CELL_SIZE, so a 20 cell gap costs a couple of thousand characters: putting the constants at 22..28 gave 33067 characters, packing the hot cells into 0..27 gives 21721. The buffer is left aligned with a length counter -- appending needs a dispatch on LEN, but backspace is just LEN-- -- and 'r' prints all four cells instead of dispatching on the length, which costs a NUL for the unused cells and is documented. tests/widths.ps1 now also checks term.r8asm at every width (its expected stream is width independent, which is what makes it a good second program for the matrix), and TODO/AGENTS/README record the item as done. |
||
|
|
10f164b480 |
docs: the signed wrappers in SPEC, AGENTS, README and TODO
SPEC gains 7.10 with both contracts, the five design points and the measured tape lengths; 5.4 stops saying "implementation pending" and spells out why the range is asymmetric -- |N| can be outside the signed range while still fitting unsigned, so 1024 has to print -1024 and the absolute value cannot be done by clearing the sign bit. Numbers re-measured on this machine, because some had drifted: the flagship is 62351 characters / 202159 steps (documented as 62513 / 206491), --opt takes it to 56338, the calculator is 62624, the byte level test is 23 items over 22 macros, and asm/ has 55 macros in 23 files. tests/widths.ps1 no longer compares the viz's serial output below 8 bit cells: the viz prints one number per OUT there, so the 7 bit "viz FAILED" was the script's expectation, not the tape -- the calculator itself passes at 7 bits through r8forge_derive, and the same failure reproduces with the previous calculator (checked against HEAD in a temp worktree). The TODO gains the open question of whether the flagship should keep the 65536 limit at all, plus the evidence that a 16 bit tape of 96052 characters runs fine in the viz. |
||
|
|
1f3f453e88 |
signed: the two two's complement wrappers, with exhaustive sweeps
clb_digits_signed N REG S T F prints '-' (45) and then |N| as the same four zero padded digits; clb_divmod_signed N D Q R S T1 T2 F is the C style truncated division (q = trunc(n/d), r = n - q*d, remainder follows the dividend). Both are wrappers: clb_digits / clb_divmod still do the work, so the tape only grows by the sign handling -- 572 characters for the display (12151 vs 11579 in the same driver layout) and 1191 for the division (6018 vs 4827). The sign bit is read with rol + bit_copy + ror, 49 characters. clb_bit_mov is deliberately NOT used: it eats the source bit, so N comes back as N - HALF and 1024 -- whose magnitude 1024 only fits the unsigned range -- prints as 0000. A clb_sub_nc against a HALF constant was the other candidate: 765 characters for the call plus ~60 for the constant cell. A flag has to outlive the block that consumes it, because biz/rnz only exit once the body clears the condition bit. So sign(N) is moved into T2, sign(D) into F, and the remainder block flips F into sign(N)^sign(D) on its way out; a single conditional negation of the quotient then carries the xor. The negation scratch is S+6: the only cell in S with a "clean on entry" contract, and clb_neg_ip leaves it zero again for clb_divmod. Verified by r8forge_byte_op_test: all 2048 values for the display (worst 117606 steps) and 4202 division pairs -- every |a|,|b| <= 32 plus the 0/+-1/+-1023/+-1024 boundary combinations -- compared against C's / and %. examples/signed_demo.r8asm is the single point regression that runs as a program (the flagship cannot carry them: +12.1k / +5.6k on a 62351 tape). |
||
|
|
01aa13d0f0 |
tape_run --profile: the walking share is measured, not estimated
A tape run now reports, on stderr (stdout keeps the out line):
profile: 314779 steps, 250112 of them pointer moves (79.5%)
> 125073 39.7% < 125039 39.7% + 22178 7.0% - 12395 3.9%
[ 25121 8.0% ] 4954 1.6% . 7 , 10
hottest cells (steps spent there): 11:30471 10:26446 9:25733 12:24879 ...
The flagship tape: 236441 steps, 180665 pointer moves (76.4%), hottest cells
91, 90, 92, 89, 87, 93, 88, 86, 85 -- which is exactly clb_digits' scratch block.
So the "walking is about seventy percent" line in AGENTS turns out to be right, and
now it is measured: this machine has no random access, every access costs
|delta address|, so layout is the performance knob -- which is also why the
peephole pass (that only cancels round trips) buys 17% of the steps.
TODO drops the --profile item; AGENTS gets the number and the conclusion, with the
two commands next to the other baseline entries.
|
||
|
|
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. |
||
|
|
ca72e19b0b |
tape_opt: the peephole pass -- 10% off the flagship tape with identical output
r8forge_tape_opt rewrites a tape with three run-local rules: > < a maximal run of pointer moves becomes its net displacement + a run becomes (length % _CELL_SIZE), a whole turn is a no-op - a run becomes (length % 2), two flips cancel The nice part is what it does NOT do: it never looks at brackets. '[' and ']' are not in any of the three character classes, so they always end a run, and within a run only the net matters (the pointer moves are pure additions and nothing in between is observable). Keeping every run's net keeps the pointer identical at every surviving character, brackets included, so the pairing that the machine finds by scanning cannot change; and since bracket characters are never added or removed, a run can never be merged across one. No stack, no offset table, one linear pass. Measured, with tape_run's out stream compared before and after (and the reference machine on the flagship's -n stream, same 93 values): asm/test.r8asm 64513 -> 58060 (-6453, 10.0%) examples/calc.r8asm 62585 -> 54863 (-7722, 12.3%) "12 34 + ." identical examples/term.r8asm 3467 -> 3402 ( -65, 1.9%) "hi" identical Step counts unchanged (the removed instructions did nothing). Not yet wired into `r8forge` itself: the pipeline is `r8forge f.r8asm > t.rot8 && r8forge_tape_opt t.rot8 t2.rot8`, and a --opt flag can wrap that later. |
||
|
|
ba5a8a465d |
tests/widths.ps1: assert the calculator at every width, not just print it
The script used to build the toolchain per width, run the widthfree label and
print whatever the calculator produced. It now checks:
* widthfree ctest label passes;
* examples/calc.r8asm assembles, and `12 34 + .` prints exactly D digits where
D = floor(W * 30103 / 100000) + 1 -- the width's digit count, computed the same
way the library computes it. A build that silently ignored the width would
print four digits and fail here instead of looking green;
* if ROT-8-viz is built next door, it runs the same tape and prints the same
thing, which makes the three way check part of the matrix.
Also fixes the invocation: `-Widths` is a comma separated string now, because
`powershell -File ... -Widths 11,16` binds as one string and 11,16 became 1116.
Measured at cell 11 (the default): widthfree ok, tape 62585, calc ok
`out 62 32 48 48 52 54 10`, viz ok `> 0046`. Default list is 7,8,11,16,17,31,32;
each width is a full toolchain build, so the whole run is about twenty minutes.
|
||
|
|
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. |
||
|
|
e137b09958 |
tests/widths.ps1: do not pipe native stderr into the output stream
The first run died at cell 1: with ErrorActionPreference=Stop a native command whose stderr is captured through the pipeline becomes a terminating ErrorRecord, so r8asm's harmless 'cached, 5 blocks' line killed the script. Native calls now report through LASTEXITCODE and their stderr goes to \; the configure no longer passes CMAKE_BUILD_TYPE, which the Visual Studio generator ignores anyway (it printed a warning per width). |
||
|
|
b7de3cad23 |
calc: the digit window follows _CELL_SIZE
The desk calculator hardcoded a four cell window, which is only right at 11 bits: clb_digits and clb_undigits use D = _CELL_SIZE * 30103 / 100000 + 1 digits (3 at 8 bits, 5 at 16, 10 at 32). D is now a .var, the window is REG..REG+D-1, every cell after it moves by D-4 (zero at 11 bits, so the numeric map is unchanged), and the startup fill, the shift chain, the flush reset and the D outputs are all %for generated. Two more width hardcodes turned up outside the window and are fixed: the C restore after the four-ror bit 4 test was `%rep 7` (only 4+7=11 at the default), it is `%rep _CELL_SIZE - 4` now -- which emits the same seven rors at 11 bits, so the tape is byte for byte identical (62585 characters, every step count unchanged). The literal descending shift was tried first and assembles fine but is wrong: writing REG+D-2 before reading it clobbers the digit that is about to move, giving "> 0350" for 12 34 + . instead of "> 0046". The chain goes ascending, which is the exact generalisation of the old four copy chain. tests/widths.ps1 builds the toolchain at 1 2 7 8 11 16 17 31 32 bits, runs the widthfree label at each and, where the ASCII constants fit (>= 6), runs one calculator session. 1 and 2 cannot: '0' is 48 and a two bit cell holds 3. Verified at 11 bits: tape unchanged, all five sessions identical, derive agrees, r8forge_examples_test 16/16. |
||
|
|
b2ba20b885 |
vms: raise the step cap from 5M to 20M
5 million steps was picked when the worst macro (clb_add_ip with B=2047) sat just under a million, so it caught hangs quickly. The interactive programs changed the arithmetic: one printed line of the desk calculator costs about 225k steps (40k for clb_undigits, up to 32k for the operation, ~141k for clb_digits), which is only about twenty lines before the cap, and examples_test applies the same cap to every example. At roughly 2.3e8 steps per second a 20M cap costs 0.09 s when a program really does run away, and byte_op_test (the only place that runs 465k programs) is unchanged -- so the safety net stays cheap while a session gets four times the room. docs/calc.md, docs/divmod.md, docs/byte-ops.md and SPEC's "500 ?" mentions now say 2000 ?. |
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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).
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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. |
||
|
|
557e2a1c38 |
In place: the ones' complement takes one cell and 17 characters
Asked whether two's complement can be done in place. The negate cannot, but the
inversion half can and is absurdly cheap, so it is a macro now:
clb_not_ip A A = ~A, one cell, 17 characters, 256/256
`%rep 8 { flb; ror }` -- flip the low bit, rotate the next one down, eight times
puts the byte back where it started. The same result through clb_neg_nc with its
carry at 0 costs 467 characters, because that path runs a synthesised slice once
per bit.
The in place two's complement itself: tried four tables and none of them exist.
A <- ~A ^ Ci A <- A ^ Ci A <- A ^ B ^ Ci A <- A ^ ~B ^ Ci
no program up to 8 layers (all four)
Two separate reasons, both worth keeping:
* Synthesis cannot: a block has exactly one condition cell. In place increment
has to tell (A=1, Ci=0) -> (1,0) from (A=1, Ci=1) -> (0,1); A is the same in
both and only Ci differs, and one condition cannot look at two cells.
* Hand writing cannot either (2 cells): `[ ... ]` is a while loop and the only
one shot conditional this ISA has, and it eats the bit it tests. In place
negate wants "flip the low bit every round, then decide the carry from it",
so both cells hold live bits and the test destroys one.
So a negate still has to land in a separate S (clb_neg_nc, 3 cells); one cell
buys the ones' complement only. byte_op_test is ten operations now, AGENTS.md
and README.md carry the distinction and the two reasons.
|
||
|
|
026ad82455 |
The nc macros take a real carry in, they do not seed it themselves
They used to write the carry cell themselves -- set_0 inside clb_add_nc, set_1
inside clb_inc_nc / clb_neg_nc / clb_sub_nc -- which made the parameter a lie: a
cell the caller passes and the callee overwrites is not a carry input, it is a
scratch cell wearing a carry's name. It also ruled out the thing a carry is for:
multi byte arithmetic. The carry out of the low byte could not be handed to the
high byte, because the high byte's call would zero (or one) it first.
Now the macros only read it, and the caller decides:
clb_add_nc A B S Ci S = A + B + Ci Ci = 0 plain add, or chained
clb_inc_nc A S Ci S = A + Ci Ci = 1 gives A + 1
clb_neg_nc A S Ci S = ~A + Ci Ci = 1 gives -A, Ci = 0 gives ~A
clb_sub_nc A B S Ci S = A + ~B + Ci Ci = 1 gives A - B, Ci = 0 A-B-1
which also turns the negate into two operations for free: two's complement
negation at Ci=1 and the ones' complement (~A) at Ci=0. The second one has its
own driver and test now (drv/raw_not_nc_byte.r8asm).
The drivers set the bit explicitly before the call, which is where that
instruction belongs -- the tapes end up the same length as before (688/430/468/725
instead of 693/433/471/730: one setup instruction moved out of the macro).
All nine byte level operations still pass, and the docs (AGENTS.md, README.md and
the four file headers) now state the carry in contract instead of describing a
constant.
|
||
|
|
5f0ce78861 |
Two's complement: negate and subtract, 3 and 4 cells
clb_neg_nc A -> -A 3 cells 471 chars 256/256
clb_sub_nc A - B 4 cells 730 chars 65536/65536
Both are "invert, then add", which is all two's complement needs:
-A = ~A + 1
A - B = A + ~B + 1
so the carry cell starts at 1 (that bit is the +1) and each bit flips its input
with one flb right before the slice reads it. Subtraction's carry out turns out
to be "no borrow": 1 when A >= B, so the same macro answers an unsigned
comparison for free. Negation's carry is 1 only for A == 0, where -0 is 0 but
does carry out.
The bit level wrappers come along too: clb_bit_neg_nc (flb + clb_bit_inc_nc) and
clb_bit_sub_nc (flb + clb_bit_add_nc).
Tried first, and it does not work: a slice that inverts its own input. The
table S = ~A ^ Ci, carry = ~A & Ci with 3 params answers
r8asm: %synth clb_bit_neg_nc_synth: no program up to 8 layers
That is a model limit, not a search budget problem: a synthesised block
"sacrifices one cell, conditionally flips others", so when A is 0 the whole
block is skipped and S can only keep the 0 the wrapper gave it -- while inverting
needs S = 1 exactly then. Unconditional flip is not expressible, so the flip has
to stay outside the slice. Both facts are in the file comment and in AGENTS.md.
byte_op_test now covers nine operations, exhaustive, 0.72 s:
raw_add/and/or/xor 65536 each raw_inc 512
clb_add_nc 65536 clb_inc_nc 256
clb_neg_nc 256 clb_sub_nc 65536
macro_docs_test: 36 macros in 12 files, all in the house format.
|
||
|
|
4be8aa15ad |
Byte level add and increment with 4 and 3 cells: clb_*_nc
The nc slices do drive a rotation, so two more library macros fall out of them:
clb_add_nc A + B -> S, carry in/out in one cell 4 cells 693 chars
clb_inc_nc A + 1 -> S, carry in/out in one cell 3 cells 433 chars
against raw_add (6 cells, 1647) and raw_inc (5, 1214). Both are in
r8forge_byte_op_test now, exhaustive: 65536 and 256 combinations, all pass.
clb_inc_nc has to start its carry cell at 1 -- that bit is the "+1"; the add
version starts at 0. A rotation driver reads the low bit, throws it away and
rotates, so eating the operands is exactly what it wants.
This retracts a sentence that has been in the tree for a while: "rotation needs
A and B preserved". It does not. Preserving them is a separate wish (raw_*
grants it, with two more cells). AGENTS.md said the wrong thing in the do not
retry list; that bullet now says what was really measured, which is only that a
4 cell slice asked to *preserve* A and B has no solution up to 8 layers.
Renamed for the same reason: bit_add_nc -> clb_bit_add_nc, bit_inc_nc ->
clb_bit_inc_nc, verify_add_nc.r8asm -> verify_clb_bit_add_nc.r8asm,
verify_inc_nc.r8asm -> verify_clb_bit_inc_nc.r8asm. Measured what the prefixes
actually separate here:
bit_raw_and A=1 B=1 -> cells 0=1 1=1 2=1 operands preserved, has tmp
bit_raw_add A=1 B=1 -> cells 0=1 1=1 4=1 operands preserved, has buf
clb_bit_and A=1 B=1 -> cells 2=1 operands eaten, no tmp
clb_bit_add_nc A=1 B=1 -> cells 2=1 3=1 operands eaten, no tmp
so raw means "the caller passes the scratch cell" and those variants happen to
keep their inputs, while clb means the inputs are gone. These slices eat A and
B, so they are clb.
One self inflicted mess to own up to: I rewrote AGENTS.md with a PowerShell
Get-Content / Set-Content round trip, which on this machine decodes UTF-8 as GBK
and wrote the file back as mojibake. Restored it with git checkout -- AGENTS.md
and redid every edit through the editor. The work rule in AGENTS.md now names
that exact trap instead of only warning about -Encoding ascii.
Green: test.r8asm 1666, full_add 8/8, both verify_*.r8asm, byte_op_test
(65536x4 + 512 + 65536 + 256), macro_docs_test 32 macros in 10 files, fibonacci.
|
||
|
|
56ea288cd6 |
Tidy the standard library's macro docs, and check them by machine
Audited all 30 %macro in asm/. The format was already followed almost
everywhere -- the doc block sits above the %macro, or above the %synth block
that generates its body -- but four things were wrong:
raw_and.r8asm the two doc blocks still carried the old names (bit_and, and)
raw_xor.r8asm raw_xor's first two parameters were typed Unit, not Cell
lib.r8asm step / back / output had no type at all ("%1: step_count")
and two files still repeated the retracted claim that set_0 only converges on 0
and 1 (raw_add_nc.r8asm, raw_add_nc4.r8asm). Those now say what set_0 really
does -- it clears the low bit -- and stay on the point that matters for a bit
level slice: A, B and the carry must be single bits because the searched
program only tracks the low K bits.
Parameter types are now a closed set: Cell, CellBit, Unit, UnitBit, Count
(Count is for step/back's repeat count). It is written down in AGENTS.md
together with the format, so the next macro has something to copy.
New r8forge_macro_docs_test checks the format instead of trusting review: a doc
block must exist, its "; Macro <name>" line must match the macro, the number
of documented parameters must equal argc, and every type must be one of the
five. Negative tested by deleting a parameter line and by renaming a block --
it reports both and exits 1.
Also fixes a real annoyance found while running the checks: %synth writes its
generated macro to the system temp directory and imports it. That write fails
intermittently on this machine (same directory, cmd can write, r8forge cannot;
cause unknown), which turned every assembly into "cannot open ...synth.r8asm".
The body is now built in memory and written to the temp directory or, if that
open fails, to the working directory, with one stderr line saying so.
Full suite green: test.r8asm 1666 characters, full_add 8/8, verify_raw_add_nc,
byte_op_test 65536x4 + 512, macro_docs_test 30/30, fibonacci prints its ten
numbers.
|
||
|
|
e30725247e |
Delete the one bit per cell layer
It was written from a wrong diagnosis. Because the interpreters in this repo
read biz/rnz as a whole cell zero test, every packed byte program looked hung,
and the conclusion was "byte level arithmetic has to be one bit per cell".
With the interpreters fixed (
|
||
|
|
afd56e7a8c |
Fix the ROT-8 interpreters: biz / rnz test the low bit
Four interpreters here (tests/synth_test.cc, src/derive.cc and the two I added
earlier: tests/tape_run.cc, tests/byte_add_test.cc) implemented '[' and ']' as
a Brainfuck style "is this whole cell zero" test. The reference implementation
does not:
ROT-8-viz src/rot8.c
rot8_biz: if ((*mem & 1) == 0) skip to just past the matching ']'
rot8_rnz: if ((*mem & 1) == 1) jump back to the matching '['
That one difference is why every byte level program in the library looked like
an endless loop. It is invisible in the bit level world -- for a cell holding 0
or 1 the low bit test and the zero test agree -- which is why the synth tables,
asm/test.r8asm and full_add never noticed anything.
Cross checked against the reference before touching anything: the tape our
assembler produces for "A = 128, set_0, B = 3, raw_add" prints 128 3 0 131 0 on
ROT-8-viz/build/rot8_test.exe and hung in our derive.
With the fix, measured:
raw_add 65536/65536 pairs ok 1647 chars
raw_and 65536/65536 639
raw_or 65536/65536 575
raw_xor 65536/65536 463
raw_inc 512/512 1214
asm/fibonacci.r8asm prints 1 1 2 3 5 8 13 21 34 55, exactly what its
comment claims
So the byte level layer was never broken. Two commits ago it was declared dead
-- set_0 "only converges on 0 and 1", the bits of a packed byte "unreadable",
raw_add "only survives 0+0" -- entirely on the strength of the broken
interpreters. AGENTS.md and README.md now say the opposite and keep the wrong
diagnosis as a worked example: when byte level code looks hung, check the
interpreter first.
New:
tests/byte_op_test.cc + drv/raw_{add,and,or,xor,inc}_byte.r8asm
exhaustive runtime proof for the byte level library, 0.5 s
tests/tape_run.cc + r8forge_tape_run
a second interpreter that runs a .rot8 file directly -- cross checking
derive is now one command
verify_set_0.r8asm now demonstrates what set_0 really does instead of claiming
it hangs: 255 -> 254, 5 -> 4, 128 -> 128 (it clears the low bit, not the cell).
The one bit per cell layer (byte_add / pack_byte) stays as a documented
alternative: it is correct under the real semantics too, just redundant.
|
||
|
|
43390efe8a |
Byte level add, one bit per cell: 65536 combinations ok
The rotation based byte layer never ran. Measured with r8forge_derive -2:
raw_add A=0,B=0 / 1+1 / 3+5 / 1+0 out empty (step limit hit)
raw_add A=127,B=130 out 0 0 0 0 0, everything destroyed
raw_and 0xF0 and 0xCC, 1 and 1, 0 and 5 out empty
copy A=5 out empty (A=0 returns fine)
Not "only operand preservation is missing": set_0 (= [-]) cannot clear a cell
that holds more than one bit, and biz only answers "is this whole cell zero",
because ror does not change zero-ness. So the bits of a packed byte are
unreadable, and the whole ror + set_0 layer has no future. The docs now say
that instead of blaming operand preservation.
What replaces it is one bit per cell:
asm/byte_add.r8asm 8 bit adder. Bit i owns four adjacent cells at base+4i:
A, B, carry (in -> out), scratch. The synthesised four
cell slice bit_raw_add_nc does the bit, clb_bit_mov moves
the carry into the next quartet. A doubles as the
accumulator, so calling byte_add again continues the sum.
asm/pack_byte.r8asm eight flags -> one byte, the only direction that works.
bit_raw_flip_if consumes a flag into flipping bit 0 of an
accumulator that may already hold bits (no set_0 there).
examples/add8.r8asm a+b, 1308 characters. A shared carry cell layout needs
only 25 cells but was measured at 2517: paying .tp travel
eight times beats saving seven carry cells.
examples/add8_inc.r8asm add 1 three times, proving the block composes.
tests/byte_add_test.cc r8forge_byte_add_test: runs the tapes on the ROT-8
machine over every input pair, 0.3 s.
Also: AGENTS.md gains the measurement table, the third instruction set
constraint (packed bytes are unreadable), the new files, and the note that
build/ has to be rebuilt with the VS bundled cmake -- scoop's 4.4 reconfigures
it and dies with "No preprocessor test for PellesC".
|
||
|
|
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
|
||
|
|
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.
|
||
|
|
548c239a85 |
Tape-length search beats the layer search on the full adder
Five layers cost 95 characters; six layers cost 90. Both are in examples/ and
both pass the eight-combination check on the ROT-8 machine in
tests/synth_test.cc (which now takes a file argument).
sacrifice B, FLIP {S,T}
sacrifice A, FLIP {B}
sacrifice B, FLIP {A,Ci,S}
sacrifice Ci, FLIP {B,Co,T}
sacrifice S, SET1 {Ci,Co}
sacrifice T, FLIP {B,Ci,S,Co}
Cost 75 in the model, 90 on the tape once the inter-block hops and the two
output lines are counted. The goal was popped at 75 only after everything
below 75 had been expanded, so 75 is the minimum of this cost model.
Trading a layer for a shorter tape is not a contradiction: the layer search
cannot see that a small, cheap block can be worth more than one wide, expensive
one.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
79bc0a4068 |
Splice %synth into the tape, and check it on a ROT-8 machine
The synthesised body is written out as a macro file and imported, so the
generated code goes through the ordinary expansion path instead of being
spliced by hand. set_1 is spelled out as set_0 plus flb, so the generated file
needs nothing from lib.r8asm.
examples/full_add.r8asm now assembles: 7.7 seconds of search at assembly time,
then a 95 character tape. tests/synth_test.cc runs that tape on a small ROT-8
machine for all eight input combinations and checks S and Co -- all eight pass.
Two things that cost me time and are worth writing down:
* the opcode map is "><+-[].,", i.e. '-' is flb and '+' is ror. Guess it the
other way round and a perfectly good tape looks like an infinite loop.
* synth names must not collide with mnemonics: 'out' is lexed as rot8_out
before it can be a block keyword.
|
||
|
|
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. |