master
7
Commits
| Author | SHA1 | Message | Date | |
|---|---|---|---|---|
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|
||
|
|
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.
|