# R8Forge SPEC R8Forge = R8ASM 汇编器 + `%synth` 搜索器 + 标准库。这份文件规定 **R8Forge 自己这一层** 的契约,重点在 **`asm/` 里的每个标准库宏**:签名、参数类型、吃什么、留什么、占几个 cell、 纸带多长、由谁验证过。 不在这里的东西: | 内容 | 在哪 | |---|---| | R8ASM 语言本体(词法、运算符优先级、`%macro`/`%rep`/`%include`、`.tp`/`.anchor`/`.var`/`.xor`/`.loop`、作用域、标准宏前缀) | `r8asm_rev/SPEC.md`(`C:\Users\peng0\git\r8asm_rev-fork\SPEC.md`,本仓库**不重复**) | | ROT-8 指令集(8 条指令、LSB 语义) | `ROT-8-viz/README.md` | | 踩过的坑、失败过的方案、交接话 | `AGENTS.md`;设计长文在 `docs/` | 本文的每个数字都是在 **11 位 cell / 259 格**、MSVC Release 构建上**实测**的;口径见 §1.3。 (两者都是构建选项:`-DR8FORGE_CELL_SIZE`、`-DR8FORGE_MEMORY_CELLS`。物理机取 8 位 / 64 格, 见 `docs/hardware.md`;几何变小之后哪些数字会变、哪些不会,§1.2 有实测表。) --- ## 1. 术语与数字口径 ### 1.1 参数类型(宏注释里只准用这五个) | 类型 | 含义 | |---|---| | `Cell` | 一个 cell 地址,装整个机器字(默认 11 位) | | `CellBit` | 一个 cell 地址,但只用它的 **LSB** 当一位用(`biz`/`rnz` 判的就是 `cell & 1`) | | `Unit` | 一个 cell 地址,它的 **下一个 cell** 是它的辅助格(SPEC:地址 n+1 是 n 的 aux) | | `UnitBit` | 同上,但按位用 | | `Count` | 纯数字,不是 cell 地址(比如 `step` 的重复次数、`%rep` 的轮数) | ### 1.2 机器几何 ```cpp // include/r8forge/geometry.hh inline constexpr size_t kDefaultCellSize = 11; // 构建选项 R8FORGE_CELL_SIZE inline constexpr size_t kDefaultMemoryCells = 259; // 构建选项 R8FORGE_MEMORY_CELLS inline constexpr uint32_t kDefaultCellMask = (1u << kDefaultCellSize) - 1u; ``` 位宽可以用构建选项换:`cmake -S . -B build16 -DR8FORGE_CELL_SIZE=16` 会造出一整套 16 位的工具链(汇编器、库、五份 VM 都跟着走)。**上限是 32**(每份 VM 的 cell 都存在 `uint32_t` 里,CMake 里越界直接 `FATAL_ERROR`,见 §13)。实测:11 / 16 位下 `r8forge_synth_test` 8/8 通过;`byte_op_test` 在 8 / 11 / 16 位下全过(16 位那轮约 7.5 分钟,穷举 65536 个值 × 十余项),**17 位以上打印 `skipped` 并返回 0**(每轮 2^W 行,跑不动,但文件得在 1..32 位都编得过);32 位下整套工具链 10 个 target 全部可建、可跑。 **环的大小也是构建选项**(`-DR8FORGE_MEMORY_CELLS=1..65536`,默认 259)。259 只是历史默认值(质数环,走飞了不会落回 2 的幂上),不是语义的一部分:`>`/`<` 都是模环回绕,任何尺寸都成立。实测每条纸带真正碰到的**最高格号**(脚本遍历纸带的 `>`/`<` 记峰值,`'<'@0` 全为 0,说明没有靠回绕的写法): | 纸带 | 峰值 | 64 格装得下? | |---|---|---| | `examples/term.r8asm` | 27 | ✓ | | `examples/signed_demo.r8asm` | 34 | ✓ | | `examples/hello.r8asm` | 49 | ✓ | | `examples/calc.r8asm` | **51** | ✓ | | `asm/test.r8asm`(全家桶自检) | **155** | ✗(它把每个宏的格子块并排铺开,是自检不是程序) | 所以 **64 格能跑所有程序**,128 格留余量;全家桶自检只有 259(或 ≥156)装得下。整轮自检在 `-DR8FORGE_MEMORY_CELLS=128` 和 `=64` 下都是 **8/8 通过**(11 位);物理机那套 **8 位 + 64 格** 组合下 `ctest -L widthfree` 5/5 通过,计算器/hello 的纸带与 259 格的版本**逐字节相同**、 会话步数也完全相同(166 348 步)。64 格在硬件上是白送的简化:`dp` 变成 6 位计数器、 回绕免费,不用做"模 259"的比较器逻辑。**代价**:程序若碰到 ≥ 环大小的格号,地址会被折 回去(全家桶在 64 格下输出不变,但步数从 404 324 变成 404 540)—— 所以选环大小的规则是 "≥ 程序碰到的最高格号 + 1"。 汇编器把三个名字注入 `.r8asm` 程序的作用域,宏库靠它们与位宽解耦: | 名字 | 值(11 位) | 用途 | |---|---|---| | `_CELL_SIZE` | 11 | `%rep _CELL_SIZE { … }` 跟着位宽走 | | `_CELL_MAX` | 2047 | 全 1 的 cell | | `_ROL_STEP` | 10 | `rol` 要转的步数(= 位宽 − 1) | ### 1.3 纸带长度的口径 本文 §5–§9 的"纸带"列一律是**最小驱动**的长度:只 `%include` 该宏所在的库文件, 把形参按顺序摆到地址 `0..N-1`,宏调用**一次**,**不带** `output`。 - `%this` 类宏(`set_0`、`rol`、`copy` …)的驱动先把 `.tp` 指向源 cell(地址 0), 所以**不含**"从别处走到操作数"的行走;宏内部自己的 `.tp` 都算在内。 - 换布局、加 `output`、多摆几个 cell 都会让长度变;`drv/*.r8asm` 里的驱动更长 (比如 `raw_add`:最小驱动 1522,`drv/raw_add_byte.r8asm` 2199)。 - 想复现:`r8forge <那个驱动>.r8asm | 数一下字符数`。 步数(运行代价)是另一回事:乘法器(§9)、`clb_divmod`(§7.6)、`clb_digits`/`clb_undigits`(§7.7、§7.9)给了实测的最坏步数,其余宏只有"O(什么)"的量级说明。 --- ## 2. 机器(汇编器眼里的实现) ``` '-' flb cells[dp] ^= 1 '+' ror cells[dp] = ror(cells[dp], cell_size) '[' biz if (cells[dp] & 1) == 0 -> 跳到匹配的 ']' 之后 ']' rnz if (cells[dp] & 1) == 1 -> 跳回匹配的 '[' '.' out 输出整个 cell 的值 ',' inp 读入并只留低 cell_size 位 '>' stp dp++ '<' btp dp-- ``` 两条**必须记住**的约束(标准库全部遵守,写新宏也得遵守): 1. **`biz`/`rnz` 判的是最低位,不是"整格为零"。** 于是 `set_0` = `[-]` 只清 LSB:`255 → 254`、`128 → 128`、`5 → 4`。 要清整个 cell 得 `%rep _CELL_SIZE { set_0; ror }`,也就是 `erase`。 反过来,字节里的任意一位都能读:`ror` 若干次把目标位转到 LSB,再 `biz`。 2. **每个条件块的身体必须回到它自己的条件 cell(净位移 0)。** `dp` 是**汇编期**常量,而 `[...]` 的 body 运行期可能被跳过;跳过的路径和进入的路径 必须在同一个 `dp` 上会合,否则之后所有 `.tp` 全部错位(症状:`dp` 跑到 1023 这种地方, `r8forge_tape_run --trace` 能看见)。`set_0` 的身体不动、`clb_bit_mov` 的身体最后 `.tp before` 再 `flb`,都是为了这一条。 附带的自然后果:**`biz`/`rnz` 是一对循环**,不是 if/else —— body 必须把被测位吃掉 (最后那个 `flb`),否则 `rnz` 看到还是 1 就跳回去。 --- ## 3. `%synth` 指令 R8Forge 唯一的语言扩展:在汇编期现场搜出一段最短的块序列,拼成一个普通宏。 ### 3.1 语法 ```asm %synth <名字> params ; 1..8 mode tape|layers ; 默认 tape layout ... ; 可选,按 %1..%N 顺序给 cell 地址 map <2^K 项> ; 或者 stat <2^params 项> %endsynth ``` - `stat` = **整张状态表**:每项是该输入组合下所有参数的取值(按 `%1..%N` 的位拼成一个数)。 - `map` = 只写输出位:项数 `2^K`(必须是 2 的幂)就表示 `%1..%K` 是输入,值里 bit j 落到 `%(K+j+1)`,剩下的参数是**必须结束为 0 的草稿位**。 - **代价口径不在源码里选**(早先的 `metric` 行已经删掉):默认按"布局无关"(flat)搜, `r8forge --synth-chars ` 才对这次汇编里的**所有**块按真实 `.tp` 行走搜。见 §3.7。 - `layout` 只在 `--synth-chars` 下有用。**给错个数不会报错**:数量不等于 `params` 时静默 退回 `0..N-1`。 - 定义完就是一个普通宏:`<名字> a1 a2 ... aN`。 ### 3.2 语义 - 目标是一张状态表:`2^N` 个输入组合,每个组合下 N 个 cell 的终值。 - **输入永远是排在最前面的参数**(`%1..%K`),搜索器拿真值表下标直接当输入值; 输入不在最前面就只能用 `stat`。 - 生成的块是 `sacrifice + mask` 模型:选中一个 cell(条件位),清掉它,然后按 mask 对其它 cell 做 `set_1`(OR)或 `flb`(XOR)。所以**合成的块只适用于"每格一位"的世界**, 高位不追踪。 - `mode layers`:只求层数最少(快)。`mode tape`:接着按纸带长度做精确 Dijkstra 搜索, 用层数解的代价做上界。 - 生成的代码走正常宏展开:写成临时文件 `<名字>.synth.r8asm`(系统临时目录,写不进去就退到 当前目录并提示),再 `import_file`,然后删掉。因此生成物不依赖 `lib.r8asm` (`set_1` 展开成 `biz/flb/rnz` + `flb`)。 ### 3.3 缓存 - 目录 `.r8forge_cache/`,**已入库**(克隆下来直接命中,第一次构建不用等搜索)。 - 键 = 模型版本 + params + mode + metric + **解析后的整张目标表**(metric 是 chars 时再加 layout)。所以同一张表、任何写法、任何调用点,共用一份结果。 - 改指令模型必须 bump `kModelVersion`(`src/synth.cc`),否则旧结果会被当成最优。 - 代价参考:`bit_raw_add` 的 flat 搜索 990,636,137 状态 / 680 秒 / 峰值 ~22 GB。 ### 3.4 限制 | 限制 | 原因 / 后果 | |---|---| | `params` 最大 8 | 状态是位平面塞进 64 位字 | | 层数上限 8 | 5 会把一些可行表误判成不可能;再高搜索爆炸 | | 字节级(`2^16` 项)真值表不可行 | 搜索空间 | | 表达不出"无条件翻转" | 模型只会"牺牲一个 cell → 条件翻转别的 cell",输入为 0 时整块被跳过 | | 原地写回的表(`A←~A^Ci` 等四个)无解 | 一个合成块只有一个条件 cell,区分不了 "A=1 且 Ci=0" 和 "A=1 且 Ci=1"(手写可以,见 §8) | ### 3.5 `%for`:带循环变量的重复(本仓库给 r8asm 加的) `%rep` 只会把**同一段文本**抄 N 遍,所以"每轮换一个偏移"写不出来。`%for` 补上这个: %for k 3 ; k = 0, 1, 2 step k %endfor ; -> 第 0 轮没有 stp,第 1 轮两个,第 2 轮四个 * `%for `:`` 在 body 里是**汇编期常量**(0..count-1),可以出现在 任何表达式里 —— `%rep` 的次数、`.tp` 的目标、宏实参都行。 * body 里的 `%2` 之类宏形参照常可见(循环作用域是"复制当前作用域再加一个名字")。 * 和 `%rep` / `%synth` 可以互相嵌套(`%endfor` 和 `%endrep` 都算配对的收口)。 * 和 `%synth` 一样是**本仓库的扩展**,不在上游语言规格里。`%rep` 保持原样。 用处就在这里:`clb_digits` 的挪位链原来是三行手写(`REG+2→REG+3`、`REG+1→REG+2`、 `REG+0→REG+1`),位宽一改就静默算错;现在是 `%for k L-1` 生成,**位数、链长、 常数构建的尾部转数全部跟着 `_CELL_SIZE` 走**。 ### 3.6 "表里那位不影响答案" = "搜索器不保证那位的初值" `compress_stat_space()` 会把**初值不影响终值**的位从搜索的初态里清成 0:只要 `target[j] == target[j ^ (1<` | 真实字符数,含 `.tp` 行走 | 是(`layout`,缺省按相邻) | 只有同一份布局 | 默认 flat 的理由:库里的块会被几十个调用点展开,布局各不相同,只有"步长无关"的结果能一份 缓存复用;对整条纸带来说它通常只长几个百分点(full_add:flat 95 字符、chars 90 字符)。 两个口径的缓存分开存(键里带 metric),所以第一次跑 `--synth-chars` 会真的去搜。 **实测过"地址有关到底能不能省"——省不了**:拿计算器(`examples/calc.r8asm`,整条 73624 字符、 几十个块展开)比,flat **73624**、`--synth-chars`(没有 `layout` 行,按 0..N-1 相邻) **73940**,反而多 316(0.4%)。三条原因: 1. 代价里的 `2*(hi-lo)` **平移不变**:把整组 cell 一起挪远挪近不改变任何价格,能变的只有 排列和散布。相邻布局(0,1,2,…)已经是"最紧"那一种,所以这个口径下没有免费的空间。 2. 库里的块被几十个地址各异的调用点共用,`layout` 行只能猜一份;为它搜出来的序列在真实 调用点上未必更短(4 参数切片的调用点地址在 20~29 之间来回换)。 3. 模型**不算块与块之间那一跳**,所以块数多的解在纸带上吃亏 —— 而精确口径经常选块数多 的解(6 参数全加器:chars 选 6 块 / 模型说 75 字符,flat 选 5 块;实际发射 82 vs 87, 只差 5 字符,其它表就把这 5 字符吃回去还倒贴)。 结论:`chars` 是"**给某个特定布局校一次**"的工具(比如你要为一份布局锁死最优块序列, 再拿结果当常量表),不是省纸带的旋钮。真正能省纸带的是**程序自己的 cell 摆放**: 计算器接终端时把借来的判据格从 52..57 挤到 20..29,纸带 77164 → 73624(−3.5k,−4.6%)。 **`blocks` 删掉了**:块数不是纸带长度的好代理(层数最少 ≠ 纸带最短,块数最少也不是), 而且它只是 `mode layers` 的一个变体。 实现:`r8asm::set_synth_metric(int)`(`include/r8forge/r8asm.hh`),在 `import_file` 之前 调用;CLI 在 `tests/asm_test.cc`(`r8forge`)里解析 `--synth-chars` / `--synth-flat`。 其它入口(`r8forge_derive`、几个测试)不传就一律 flat。 **线程数**也是同一条路子:`-j N`(`--synth-threads N` / `--synth-threads=N`)限制纸带搜索的 worker 数,`0`(默认)是每个硬件线程一个。纸带搜索按"第一个块"切分(见 `r8veritas_phase.hh` 的 `search_tt`),所以多 worker 是安全的;**层数搜索是串行的**,这个 参数对它没用(它本来就只有秒级)。`r8asm::set_synth_threads(unsigned)` 是 C++ 侧的开关。 **`-q` / `--quiet`**:stdout 只剩纸带 —— `%synth` 的 cache 命中、层数/纸带搜索的计时、 临时目录回退的提示都不打。**错误照旧打到 stderr**(缺文件、未知宏、搜不出解、写不了临时 文件),退出码也不变:quiet 是"别啰嗦",不是"藏故障"。C++ 侧是 `r8asm::set_quiet(bool)`。 --- ## 4. 标准库 `asm/` —— 总则 ### 4.1 命名 | 前缀 | 全称 | 含义 | |---|---|---| | `clb` | clobber | 破坏性:会破坏原始输入(多数情况是清零) | | `bit` | bit | 对 cell 的 **LSB** 操作的宏 | | `raw` | raw | 未经封装:**草稿 cell 要调用者自己传** | 后缀(不是前缀): | 后缀 | 含义 | |---|---| | `_nc` | 历史命名(no carry),实际含义是"把操作数吃干净"的切片版 | | `_ip` | in place:结果写回原来的 cell | | `_synth` | `%synth` 生成的块本身,不是给人调用的;包装它的 `%macro` 才用不带后缀的名字 | 例:`raw_add`(保留操作数、要你自己给 `Co`/`tmp`)、`clb_add_nc`(吃 A/B、4 cell)、 `clb_add_ip`(原地、B 被吃)、`bit_raw_add_synth`(合成的块)+ `bit_raw_add`(包装宏)。 ### 4.2 注释契约(机器检查) `asm/` 里每个 `%macro` 必须有注释块,`r8forge_macro_docs_test` 会逐条检查: ```asm ; Macro clb_bit_add_nc ; %1: CellBit A ; %2: CellBit B ``` - `; Macro <名字>` 必须和实际宏名一致; - `%N: <类型> <名字>` 条数必须等于 argc,类型必须是 §1.1 的五种之一; - `%this` 表示"dp 当前所指的 cell"; - 注释块贴在 `%macro` 上方或生成它的 `%synth` 块上方都行。 ### 4.3 布局 标准库**不假设** cell 地址。所有地址都是形参,由调用者自己排;宏内部的 `.tp` 行走算在 这个宏的纸带长度里(所以同样的宏在不同布局下长度不同)。宏返回时 `dp` 回到调用点的 cell。 --- ## 5. 基础宏(`asm/lib.r8asm`) | 宏 | 签名 | 干什么 | cell | 纸带 | |---|---|---|---|---| | `step` | `step N` | `N` 次 `stp stp`(一个 Unit) | 0 | 2 | | `back` | `back N` | `N` 次 `btp btp` | 0 | 2 | | `set_0` | `set_0`(`%this`) | 清 `%this` 的 LSB(= `[-]`) | 1 | 3 | | `set_1` | `set_1`(`%this`) | 置 `%this` 的 LSB(= `set_0` + `flb`) | 1 | 4 | | `erase` | `erase c` | 清 `c` 的**整个** cell(`%rep _CELL_SIZE { set_0; ror }`) | 1 | 44 | | `rol` | `rol`(`%this`) | 左旋一格 = `%rep _CELL_SIZE - 1 { ror }` | 1 | 10 | | `clb_bit_mov` | `clb_bit_mov d`(`%this`) | 把 `%this` 的 LSB **搬**到 `d` 的 LSB,源被吃掉 | 2 | 11 | | `bit_copy` | `bit_copy d b`(`%this`) | 位拷贝,`b` 是借来的缓冲,**源保留** | 3 | 38 | | `copy` | `copy d b`(`%this`) | 整个 cell 拷贝(位拷贝转满 `_CELL_SIZE` 圈) | 3 | 495 | | `bit_copy_to_buffer` | `bit_copy_to_buffer t`(`%this` 是 UnitBit) | 位拷到 Unit 的辅助格,`t` 是缓冲 | 3 | 40 | | `copy_to_buffer` | `copy_to_buffer t`(`%this` 是 Unit) | 整 cell 拷到 Unit 的辅助格 | 3 | 497 | | `output` | `output c` | `.tp` 到 `c` 再 `out`(输出整个 cell 的值) | 1 | 1 | | `loop` | `loop c` | 动态循环开口:按 `c` 里 1 的个数跑,每轮吃掉一个 1 | 1 | 4 + `.tp` | | `endloop` | `endloop c` | 动态循环收口(`rnz` 判 `c` 的最低位) | 1 | 1 + `.tp` | 要点: - **`set_0` 只清一位**,`erase` 才清整格;别把 `set_0` 当"清零 cell"用。 - `copy` 比 `bit_copy` 长十倍多,是因为它对每个 bit 调一次 `bit_copy` 并转圈 (`copy` 495 vs `bit_copy` 38)。只搬一位用 `clb_bit_mov`(11)。 - `clb_bit_mov` 会把源位清掉 —— 它顺手就"吃条件",这正是 `set_0`/`clb_bit_mov` 身体里那个 `flb` 的作用(见 §2 第 2 条)。 ### 5.1 动态循环:`clb_ones` 配 `loop`/`endloop` `%rep` 是**汇编期**的。要按**运行期**算出来的次数循环,用这一对: ``` clb_ones N C T F ; C = N 个 1(N 被吃掉,§7.5) loop C ... body ... ; 想干几次就干几次 endloop C ``` - `loop c` = `.tp c` + `biz` + `set_0` + `ror`:进来时测最低位,进去就**把这一位吃掉再转一格**, 把下一个 1 送到最低位。于是"配额"就是那串 1 的长度,一圈用掉一个。 - `endloop c` = `.tp c` + `rnz`。 - 三条约定:**循环体不许碰 `c`**;不开 `.anchor`,所以**能嵌套**;`endloop` 之后 dp 停在 `c` 上(不管循环体把 dp 指到哪儿,收口都会指回来)。 - 跑完 `c` 是 0。`n = 0` 时 `biz` 直接跳过,一圈不跑 ✓。 实测(`verify_loop.r8asm`,**939 字符**):`n = 0..11` 循环体正好跑 `n` 次,`A = n`、`C = 0`。 嵌套也验过:内层每轮用 `copy` 重新造一份计数器,`NO × MI` 得到 121(11×11)、`MI = 0` 时 0、 `NO = 0` 时 0 —— 就是普通的双层循环。 纸带代价是 `loop` 4 字符 + `endloop` 1 字符 + 两次 `.tp`(跟布局有关),**和次数无关**; 运行是 O(n)。 > 在 `.r8asm` 源码里循环要写 `biz` / `rnz`,**不是** `[` / `]` —— 后者是纸带上的编码。 > 直接手写 `[` 会报 `unknown macro '['`(`lib.r8asm` 里就是这么踩的)。 **别拿它去替代汇编期常数**。`clb_mul` 的轮数计数器是 `_CELL_SIZE` 个 1,汇编期就能做: ``` %rep _CELL_SIZE { set_1; ror } ; 55 字符(4+1 各 11 份) ``` 换成运行期那条路要 `clb_ones`(≈770)+ `loop`/`endloop`(≈10)+ 先把常数 `_CELL_SIZE` 做成运行期的值,**约 850 字符** —— 15 倍,还多 4 个 cell 和几万步运行时间。 所以规则是:**次数在汇编期就知道 → 汇编期造计数器;只有次数来自数据才用 `clb_ones`。** (`loop`/`endloop` 两种都吃:它们只要求"某个 cell 里现在有 n 个 1",不关心这些 1 是谁造的。) 顺带一个坑:`%rep N { set_1; ror }` 造出来的 N 个 1 落在**高位**(bit `W-1` 往下), `biz` 看到的 bit0 是 0,循环一圈都不跑 —— `N < W` 时要在 `%endrep` 后面补一条 `rol` (10 字符),把那串 1 转到含 bit0 的位置。`clb_mul` 没踩这个坑,是因为它的 N 正好等于 `_CELL_SIZE`,整格全 1,bit0 天然是 1。 --- ### 5.2 常量与文本:`load` 和 `clb_puts` `load N V`:把汇编期常数 `V` 装进格 `N` —— `erase` 再 `.xor`,两步都要有(`.xor` 是异或,不清格就是对旧值异或)。 `clb_puts REG LEN`:把 `REG` 起 `LEN` 个连续 cell 的低 7 位当字符依次打出来。`LEN` 必须是 **汇编期常数**:没有间接寻址,`.tp` 只能写死,"遇到 0 就停"的运行期长度做不到。每个字符 约 3~4 字符纸带(两条 `.tp` 加一条 `out`),不占额外 cell,源格保留。 两个都是 `asm/lib.r8asm` 里的基础宏;`examples/hello.r8asm`(727 字符)和 `drv/puts.r8asm` (198 字符)分别演示和单点验证它们。 ### 5.3 `raw_puts_dyn`:运行期长度的打印 `raw_puts_dyn REG MAX LEN CNT F T`:打印 `REG` 起最多 `MAX` 格里的前 `LEN` 格,`LEN` 是**运行期** 的值(把一段缓冲原样打出来)。`LEN` 保持原样;`CNT` 是倒计数(结束时 0,`LEN > MAX` 时剩 `LEN-MAX`);`F` 是每格的条件标志;`T` 兼作 `copy` 缓冲和 nonzero/dec_ip 的草稿、**进来必须 干净**。`MAX` 仍是汇编期常数 —— 打印哪一格要写死 `.tp`,能变的只有"打不打"。 每格约 450 字符纸带、几百步;`drv/puts_dyn.r8asm` 单点验证(`LEN` = 3 / 0 / 8 → `ABC` / 空 / `ABCDEFGH`)。**它不在 `asm/test.r8asm` 里**:MAX=8 的版本要三万多字符,而全家桶离 65536 只剩约一千。 ### 5.4 有符号数(约定 + 实现在 §7.10) 表示法用**二补码**:值 `v` 为负当且仅当第 `_CELL_SIZE-1` 位是 1(11 位时 1024..2047 = −1024..−1,8 位时 128..255 = −128..−1)。 **范围是不对称的**:11 位能表示 −1024..1023。−1024 的绝对值 1024 放不进**有符号** 范围,却放得进**无符号**范围 —— 所以 `1024` 这个位型要能打成 `-1024`(`clb_digits` 本来就是无符号展开)。这条把"取绝对值"的实现路子钉死了:**必须真的取负** (`clb_neg_ip`),不能靠"清掉第 W-1 位"—— 那种写法在 1024 上会打出 0 (`examples/signed_demo.r8asm` 就是这条例子的回归)。 四条约定: * **加、减、乘不需要改**:模 2^W 运算天然按二补码正确。 * **显示**:`-0042`,即字符 45 加现有的定宽补零数字;正数不打印加号。 * **除法**:截断(C 语义)—— `q = trunc(a/b)`、`r = a - q*b`,余数与被除数同号。 * **溢出**:静默回绕,不显示错误(`-1024 / -1` 这种"商出了有符号范围"也一样)。 实现:§7.10 的两个包装宏(`clb_digits_signed`、`clb_divmod_signed`)+ `examples/calc.r8asm` 里的一元负号(判据是 cell `DEPTH`:栈空时 '-' 才是一元, 见那个文件开头)。 ## 6. 位级宏(一个 cell 装一位) ### 6.1 总表 | 宏 | 签名 | 语义 | 吃什么 | cell | 纸带 | 实现 | |---|---|---|---|---|---|---| | `clb_bit_add_nc` | `A B Ci S` | `S = A^B^Ci`,进位进→出 | A、B | 4 | 66 | `%synth` | | `clb_bit_inc_nc` | `A Ci S` | `S = A^Ci`,进位 = `A&Ci` | A | 3 | 50 | `%synth` | | `clb_bit_and` | `a b ans` | `ans = a&b` | a;b 只在"两位都是 1"时清 | 3 | 25 | **手写** | | `clb_bit_or` | `a b ans` | `ans = a\|b` | a、b | 3 | 25 | `%synth` | | `clb_bit_xor` | `a b ans` | `ans = a^b` | a、b | 3 | 20 | `%synth` | | `bit_raw_add` | `A B Ci S Co buf` | 完整全加器:`S=A^B^Ci`,`Co=maj(A,B,Ci)`;**A、B 保留**,`buf` 结束是垃圾 | 无(buf 草稿) | 6 | 106 | `%synth` | | `bit_raw_and` | `arg1 arg2 ans tmp` | `ans = arg1&arg2`,两个操作数保留 | tmp | 4 | 57 | `%synth` | | `bit_raw_or` | `arg1 arg2 ans tmp` | `ans = arg1\|arg2`,保留 | tmp | 4 | 59 | `%synth` | | `bit_raw_xor` | `arg1 arg2 ans tmp` | `ans = arg1^arg2`,保留 | tmp | 4 | 49 | `%synth` | | `bit_raw_inc` | `A Ci S Co tmp` | `S = A^Ci`,`Co = A&Ci`,A 保留 | tmp | 5 | 77 | `%synth` | 所有位级宏都**只碰低 1 位**,喂进来的输入必须是 0/1;`clb_bit_add_nc`/`clb_bit_inc_nc` 的进位 cell 是"进→出"的同一个 cell。 包装宏在调用合成块之前先对**输出位**(`S`、`Co`、`ans`、`tmp`/`buf`)`set_0` —— 那不是 冗余动作:这些表对输出位的初值是周期的,搜索器据此把它们当成"不是输入"、只保证初值为 0 的调用点。删掉会让 `clb_mul`/`clb_divmod`/`clb_digits` 当场挂掉,详见 §3.6。 ### 6.2 为什么 `clb_bit_and` 是手写的 三个参数、没有草稿位,而"与"需要**同时**保住两个输入,只能靠嵌套 `biz`(一层一个条件)。 搜索器在 3 个平面、9 层内穷尽无解 —— 这是模型的表达力边界,不是搜索没跑够。 `or`/`xor` 可以先清一个操作数,所以能合成(`0 4 4 4` / `0 4 4 0`)。 ### 6.3 `%synth` 块与它们的表 | 块 | params | 表(`stat`) | 用它的宏 | |---|---|---|---| | `bit_raw_add_synth` | 6 | `0 9 10 19 12 21 22 31` ×8 | `bit_raw_add` | | `bit_raw_and_synth` | 4 | `0 1 2 7` ×4 | `bit_raw_and` | | `bit_raw_or_synth` | 4 | `0 5 6 7` ×4 | `bit_raw_or` | | `bit_raw_xor_synth` | 4 | `0 5 6 3` ×4 | `bit_raw_xor` | | `bit_raw_inc_synth` | 5 | `0 5 6 11` ×8 | `bit_raw_inc` | | `clb_bit_add_nc_synth` | 4 | `0 8 8 4 8 4 4 12` ×2 | `clb_bit_add_nc` | | `clb_bit_inc_nc_synth` | 3 | `0 4 4 2` ×2 | `clb_bit_inc_nc` | | `clb_bit_or_synth` | 3 | `0 4 4 4` ×2 | `clb_bit_or` | | `clb_bit_xor_synth` | 3 | `0 4 4 0` ×2 | `clb_bit_xor` | 这些表**不是手写的**,是 `r8forge_derive` 从旧的手写实现上穷举出来的 (例:`r8forge_derive drv/bit_raw_add.r8asm 6` → `stat 0 9 10 19 …`)。 所以合成结果与旧实现**逐位一致**,连"某个输入没被清掉"这类怪癖都保住了;要改语义就改表。 --- ## 7. 字节级宏(一个 cell 一个机器字) ### 7.1 `raw_*` 家族:保留操作数 | 宏 | 签名 | 语义 | cell | 纸带 | 验证 | |---|---|---|---|---|---| | `raw_add` | `A B Ci S Co tmp` | `S = A+B+Ci`,`Co` 进位出 | 6 | 1522 | `drv/raw_add_byte.r8asm`,65536/65536 | | `raw_and` | `arg1 arg2 ans tmp` | `ans = arg1 & arg2` | 4 | 697 | 65536/65536 | | `raw_or` | `arg1 arg2 ans tmp` | `ans = arg1 \| arg2` | 4 | 719 | 65536/65536 | | `raw_xor` | `arg1 arg2 ans tmp` | `ans = arg1 ^ arg2` | 4 | 609 | 65536/65536 | | `raw_inc` | `A Ci S Co tmp` | `S = A + Ci`,`Co` 进位出 | 5 | 1179 | 512/512(A 与 Ci) | `raw` 的含义是"草稿 cell 你自己传":`tmp` 结束是垃圾(`bit_raw_add` 的 `%6: buf` 同理)。 **`raw_add` 不吃操作数**:实测 `5+3 → A=5 B=3 S=8`,`255+255 → A=255 B=255 S=254 Co=1`。 (历史注释里"每圈都要重新复印"是过度保守 —— 复印了也没错,但没必要。) ### 7.2 `clb_*_nc` 家族:把操作数吃干净 | 宏 | 签名 | 语义 | 吃什么 | cell | 纸带 | 验证 | |---|---|---|---|---|---|---| | `clb_add_nc` | `A B S Ci` | `S = A+B+Ci` | A、B | 4 | 741 | 65536/65536(`drv/raw_add_nc_byte.r8asm`) | | `clb_inc_nc` | `A S Ci` | `S = A+Ci` | A | 3 | 552 | 256/256 | | `clb_neg_nc` | `A S Ci` | `S = ~A+Ci`(Ci=1 → `-A`) | A | 3 | 574 | 256/256(Ci=1 取负、Ci=0 反码) | | `clb_sub_nc` | `A B S Ci` | `S = A+~B+Ci`(Ci=1 → `A-B`) | A、B | 4 | 765 | 65536/65536 | **进位 cell 是真正的进位输入**:宏自己**不动**它的初值,只把它变成进位输出。 调用者给 0 就是普通运算,给 1 就是"自带 +1",也可以把上一字节的进位输出接过来串多字节。 (这条踩过:早先加法里 `set_0`、自增里 `set_1`,那就不是输入了,还把串接堵死。) 补码那两条的做法是**先原地取反、再走加法/自增**:`-A = ~A + 1`、`A - B = A + ~B + 1`, 那个 `+1` 由调用者的 Ci 给。取反整个字节一次(`clb_not_ip`)比"每 bit 取反一次"短二十来个 字符,而且 B 本来就会被加法吃掉,取反它没有代价。 进位输出的附带语义:`clb_sub_nc` 的进位是**没有借位**(`A >= B` 时为 1)——顺带就是 无符号比较;`clb_neg_nc` 的进位只在 `A` 原本是 0 时为 1(`-0 = 0`,但确实进了位)。 ### 7.3 `clb_and` / `clb_or` / `clb_xor`:半破坏,读清楚再用 | 宏 | 签名 | `ans` | A 之后 | B 之后 | cell | 纸带 | |---|---|---|---|---|---|---| | `clb_and` | `arg1 arg2 ans` | `arg1 & arg2` | **0** | **`B & ~A`(有残留!)** | 3 | 352 | | `clb_or` | `arg1 arg2 ans` | `arg1 \| arg2` | 0 | 0 | 3 | 323 | | `clb_xor` | `arg1 arg2 ans` | `arg1 ^ arg2` | 0 | 0 | 3 | 268 | `clb_and` 是这三个里唯一不清零 B 的:每位只有在"A、B 都是 1"时才清 B, 所以 B 结束在 `B & ~A`(实测 `240 & 204 → ans=192, A=0, B=12`)。 **别拿它当"两个操作数都能回收"的宏**;要干净的与运算,就用 `raw_and`(保留操作数) 或者自己再 `erase` 一次。`clb_or`/`clb_xor` 是干净的。 ### 7.4 三个家族怎么选 | 需求 | 用 | |---|---| | 操作数要还回来 | `raw_*`(6/4 cell,多的那个是草稿) | | 操作数可以扔,要省 cell | `clb_*_nc`(4/3 cell) | | 结果要写回原 cell | `_ip` 家族(§8) | **轮转驱动不吃亏**:`clb_*_nc` 和 `raw_*` 的区别只在"要不要还操作数",两者都是 "读走 LSB → 丢掉 → `ror`" 的轮转驱动,吃掉操作数完全没问题。 ### 7.5 `clb_ones`:把数量展开成一串 1 `clb_ones A B T F`:**`B = 2^A - 1`,也就是从末位起 A 个连续的 1**;A 当计数器被吃干净 (结束为 0),T、F 结束也都是 0。**前提 `A <= _CELL_SIZE`,不做检查**(A 更大时 2^A−1 会绕回)。 | 输入 A | 0 | 1 | 4 | 7 | 11 | |---|---|---|---|---|---| | 输出 B | 0 | 1 | `0x0F` | `0x7F` | `0x7FF`(全 1) | 4 个 cell、纸带 **828 字符**(`drv/ones.r8asm` 是 742,因为它的布局更近), A 的 12 个取值全对(`r8forge_byte_op_test` 的 `test_ones`)。 算法就是"边转边在低位补 1": B = 0 while A != 0: B = 2B + 1 ; A -= 1 `2B+1` 在这台机器上等于 **`rol` + `set_1`**:左旋把 B 的最高位带回末位,紧接着的 `set_1` 正好把它盖成 1,于是等价于"左移补 1"。A 直接当计数器吃掉(省一次 `copy`,那是 495 字符), 循环体只出现一次,所以长度和 A 无关;代价是运行 O(A),而 A ≤ `_CELL_SIZE`。 两个可以拿来写别的东西的恒等式: * `clb_inc_ip` 作用在"n 个 1"上得到 `2^n`(末位起第 n+1 位是 1); * 反过来先摆一个 `2^n` 再 `clb_dec_ip`,也得到 n 个 1(这条比上面的循环短 128 字符的 `clb_dec_ip` 反而更长,因为循环体里要一直 `set_1`,见 `asm/ones.r8asm` 的注释)。 ### 7.6 `clb_divmod`:除法与取模 `clb_divmod N D Q R S`:`Q = N div D`、`R = N mod D`,**N 和 D 都保持原样**。 11 个 cell(N、D、Q、R 四个数据 + `S` 起的 7 个连续草稿),纸带 **4499 字符** (`drv/divmod.r8asm` 是 4511);`r8forge_byte_op_test` 的 `test_divmod` 现在扫 **8 个除数 × 全部 2048 个被除数 = 16384 组**,全对(旧的 76 组抽样表是它的子集)。 草稿格里**只有 `S+5`(`buf`)进来必须是干净的**(它是 `copy`/`bit_copy` 的缓冲, 缓冲带垃圾时拷贝结果是 0);其它格子脏了没关系 —— 要么整格重写(`raw_add` 逐位写 `Sd`/`Bo`),要么只按一位用(`Rhi`/`Cm`/`Bo`),`NR` 每次进来都会重建成 W 个 1。 `clb_digits` 就是这么反复用同一块草稿的。 算法是**二进制长除法(移位-恢复)**,从被除数的最高位往下一位一位串: R = 0 ; Q = 0 repeat _CELL_SIZE 轮: R = (R << 1) | (N 的下一位) ; 每轮 rol N,下一位落在 N 的 LSB if R >= D: R -= D ; 商位 = 1 else: 商位 = 0 轮数 = 位宽,**跟 N、D 的值无关**。旧版是重复减法 O(N/D),`2047/1` 要 2047 轮、 直接撞 2000 万步上限(实测 HANG)。实测(同一条 `drv/divmod.r8asm`,11 位): | 算式 | 重复减法(旧) | 移位-恢复(现在) | |---|---|---| | `2047/10` | 495,986 | **28,593** | | `2047/2` | 2,461,650 | **31,997** | | `999/7` | 340,086 | **28,661** | | `2047/1` | **HANG**(>2000 万) | **32,383** | | `7/10` | 3,014 | 25,315 | | `100/7` | 34,940 | 27,460 | 代价和 `clb_mul` 一样:**N/D 很小时反而慢**(旧版 N/D 轮就结束,新版固定走满 11 轮), 换来"除数和商再大也不会挂"。16384 组里实测最坏 **32,383** 步。 三个设计点: 1. **W+1 位比较拆成"一个 W 位减法 + 一个布尔"**:左移之后 R 最多 W+1 位,最高位 (`Rlo` 左旋绕回来的那一位,记 H)落在 `Rhi` 里。H = 1 时 R >= 2^W > D **必然提交**, 而且 R − D 的低 W 位正好是 `S = Rlo − D (mod 2^W)`;H = 0 时就是普通的 "`Rlo >= D` 才提交"。所以**提交条件 = H | Bo**(一条 `clb_bit_or`),不用真去做 W+1 位减法(`docs/divmod.md` §2)。 2. **"提交后的新高位"恒为 0,不用算**:提交之后 R < D < 2^W,下一轮开头高位就是 0; 而 H = 1、Bo = 1 这个组合在"每轮开头 R < D"的归纳下不可能出现(它会要求 R = 2^W + Rlo >= 2D)。所以 `docs/divmod.md` §2 里写过的 `Shi = H & Bo`、那个 `clb_bit_and` 和一次 copy 都可以省掉 —— `Rhi` 只是个轮内布尔,`clb_bit_or` 顺手就把它吃掉。 3. **D 必须保留**:每轮都要拿同一个除数去比/减,所以走 `raw_sub`(保留操作数、 只吃草稿)。这也是上一轮加 `raw_sub` 的原因(§7.8)。 踩过的三个坑: * **R 的跨格左移顺序**:`rol` 把 `Rlo` 的最高位绕回 bit0,必须先 `clb_bit_mov` 把它 搬进 `Rhi`(搬的同时清掉绕回位),**再** `bit_copy` 从 N 注一位。反了就丢位 —— `clb_mul` 当年在这里返工两轮。 * **`biz`/`rnz` 是循环对**:门控提交的身体最后必须把条件吃掉(`flb`);商位那一步 把"提交时 `set_1`、把条件清掉"合在同一个块里。条件块的身体都回到自己的条件 cell。 * **N 不被消耗**:每轮 `rol` 一次,转满 11 轮自己复原;注入用 `bit_copy`(保留源, 38 字符)。所以余数得单独占一格 R —— 旧版"余数就在 N 里"的约定没有了。 除零没有定义,调用者保证 `D >= 1`(D = 0 时 R >= 0 恒成立,商会变成全 1)。 ### 7.7 `clb_digits`:整数转十进制字符串 `clb_digits N REG S`:把 N 展开成 **`REG..REG+3` 四个连续 cell,每格一个 ASCII 数字 (`'0'..'9'`),高位在前、定长 4 位、左边补 `'0'`**(11 位 cell 最大 2047,正好 4 位)。 N 被吃干净;`REG` 起 4 格、`S` 起 **13 格**必须连续且干净。纸带 **11717 字符** (最小驱动;13 格草稿重排之前是 13717,再往前 10829 —— divmod 的草稿块从 4 格变成 7 格,而且多了一格余数),`r8forge_byte_op_test` 的 `test_digits` 现在**穷举全部 2048 个值**(最坏 **123,755** 步;重排之前 164,867)。 2047 -> REG = '2' '0' '4' '7' 7 -> REG = '0' '0' '0' '7' 做法:**divmod 只出现一次**,外面套一个跑 4 次的运行期循环;而"写哪一格"不做分派 —— 每轮把已经写好的数字**整体往高地址挪一格**,新数字永远写 `REG+0`: 第 1 轮: 挪(空) ; REG+0 = 个位 第 2 轮: 挪(个位 -> REG+1) ; REG+0 = 十位 ... 挪的顺序必须**从高到低**(`REG+2 -> REG+3` 先做),否则会把还没搬的高位盖掉。 4 轮之后 `REG+0..3` 正好是千、百、十、个。 `S` 起的 13 格是这么排的(`clb_divmod` 要一块 7 格的连续草稿,所以它从 `S+2` 开始)。 **这个排法是量出来的,不是拍的**:把 13 格拆成 7 个单元(TEN、商、余数、7 格草稿块、 轮数计数器、add_ip 的 T 和 F),5040 种排列全部汇编一遍、用 `r8forge_tape_run` 跑 `0=2047` 数步数,取最小的那个: S+0 clb_add_ip 的 T S+1 余数(这一位的数字,divmod 的 R) S+2..S+8 clb_divmod 的草稿块(Rhi、Sd、Bo、Cm=Bc、Ci、buf、NR) S+9 TEN(除数) S+10 商(divmod 的 Q) S+11 clb_add_ip 的 F S+12 轮数计数器(loop) 依据是三条距离(这台机器没有随机寻址,访问一格就是走 |Δ地址|): * **余数紧贴草稿块前面、TEN 紧贴草稿块后面**。余数是 `raw_add` 的 A(每次 11 位 一位一位过),TEN 是 `raw_sub` 的被减数(每轮 `copy TEN -> Bc`,缓冲就是块里的 buf)—— 这两个距离直接乘进 divmod 内层 11×11 的位循环。旧排法把 TEN 放在最前面, 离 buf 8 格、离 Bc 6 格;只把它挪到块后面(其它单元的先后不变)就省 **22,226** 步。 * **add_ip 的 T 紧挨着余数**:`clb_inc_ip`/`clb_dec_ip` 的进位链每轮在这两格之间来回, 光把 T 和余数换个位置就差 4,450 步。 * **轮数计数器只被 loop 每轮碰一次**,踢到最远的一头(`S+12`)。 改完 `0=2047` 是 **113,264** 步(145,114 -> 113,264),2048 个值全扫最坏 123,731 (值 1999)、平均 112,552(旧 144,904)。契约一个字没改,改的只是 13 格内部的排法。 挪位链和"商 -> N"的拷贝都借 `S+7`(divmod 的 buf)当缓冲 —— 那个格子在 divmod 结束时 是干净的。余数单独占一格(旧版是"余数就在 N 里"),所以 `REG+0 = '0' + 余数` 读的是 `S+1`;下一轮的 N 还是靠 `copy` 从商搬回去。 第一版是"4 个分支 + one-hot flag 分派",**只写对了第一支**(其余三支没触发),换成 整体挪位后不仅正确,还少了两层嵌套、4 个 cell 和一堆 flag 交接。教训: **在这台只有 `biz`/`rnz` 的机器上,"选一个格写"最好用位置移动表达,别用索引分派。** 三个搭这条宏时踩出来的坑(都写进了宏注释): * **`copy` 的缓冲格必须是干净的**:缓冲里带垃圾时拷贝结果是 **0**(实测 `Q=4`、缓冲 `0x7f8` → `N=0`)。库注释只说了"`b` 是借来的缓冲",没提这条。 * **造常数不能分两次"置位再转"**:第二次旋转会把第一次放好的位一起带走。正确做法是 **绕整圈走一次**(`W` 次 `ror`,转到目标位就 `set_1`,最后转回原位)。 * **换了 divmod 之后要记得补 include**:`clb_add_ip` 原来是从旧的 `divmod.r8asm` 里 间接 include 进来的,新的 `divmod.r8asm` 不再 include 它(它只 include `raw_sub` / `raw_or`),所以 `digits.r8asm` 现在自己 `%include "asm/add_ip.r8asm"`。 漏了的话汇编器会报 `unknown macro '(clb_add_ip'`(**而 `r8forge_derive` 以前会忽略 这个错误、接着跑半截纸带**,见 §11 的说明)。 ### 7.8 `raw_sub`:保留操作数的减法(长除法的地基) `raw_sub A B S Bo Bc Ci buf`:**`S = A - B`,而且 A、B 都原样还回来**, `Bo` 是"没有借位"(1 表示 `A >= B`,和 `clb_sub_nc` 的进位一致)。 7 个 cell,纸带 **2900 字符**左右,9 组抽样全对。 做法就是把 `raw_add`(它本来就保留操作数)套上补码:`S = A + ~B + 1`, 进位输出就是"没借位"。所以整个宏只有三行有用的话:copy 出 `~B`、`Ci = 1`、 `raw_add`。 **踩到的坑**:别在最后 `clb_not_ip Bo` 想"取反得到借位" —— `clb_not_ip` 是 整格取反,0 会变成 2047、1 会变成 2046(实测),不是 0/1。要用"没借位"这个 现成语义,和 `clb_sub_nc` 保持一致。 ### 7.9 `clb_undigits`:十进制字符串转整数(`clb_digits` 的逆) `clb_undigits REG N S`:把 `REG` 起 **4 个连续 cell**(11 位;位数和 `clb_digits` 一样是 `floor(W*log10(2)) + 1`,跟着位宽走)的低 7 位当成 ASCII 数字,拼成整数写进 `N`。 **不做合法性判定**(和 `clb_digits` 一致):每格只取低 7 位,第 7 位以上直接忽略; 超出 `'0'..'9'` 的输入算出一个确定但没意义的数。`REG` 起 4 格被吃干净(每轮把当前位当 加数用掉、其余整体下移一格),`N` 被覆盖;`S` 起 **11 格**草稿,**脏的也行**(每轮都会重建 或整格重写)。纸带 **9642 字符**(最小驱动)/ 9651(带 output), `test_undigits` 穷举**全部 2048 个值 × 2 种输入(干净 / 高位置垃圾)= 4096 组** (最坏 36,481 步)。 49 50 51 52 -> 1234 ("1234") 48 48 48 55 -> 7 ("0007") 2047 -> clb_digits -> "2047" -> clb_undigits -> 2047 做法是 Horner:`N = 0`,然后每位 `N = N*10 + 当前位`,数字区每轮整体**下移一格**,让下一位 进 `REG+0`(和 §7.7 的挪位方向正好相反:那边往高地址挪、新数字写 `REG+0`)。 和 `clb_digits` 一样用一个跑 4 次的运行期循环,所以乘 10 的 `clb_mul` 在纸带里只出现一次 —— 反方向不需要除法,一位一位乘上去就够,整条比 `clb_digits` 小一半。 三个关键点: * **`c ^ 48 = c - 48`**(`c` 在 `'0'..'9'` 内):`'0'+d` 与 48 异或,高两位抵消、低 4 位 不变,所以"减 '0'"就是一条汇编期的 `.xor 48` —— 不用减法、不用常数格。 * **低 7 位掩码**:`ror` 7 格把第 7 位转到最低位,再 `set_0` + `ror` 清掉第 7..W-1 位, 一共转 W 格、结束时格子正好转回原位。第一版写成 `rol; set_0; ror` 循环,**每轮都把同一个 bit 清一遍**,等于什么都没做(实测 `0|5<<7` 原样算进去,`out 688`);错误很隐蔽,因为 它在"高位本来就是 0"的输入上完全正确。 * **计数器要先 `erase`**:`set_1` 只清它转到的那一位,格子里原来的高位会变成额外的 1, 循环就多跑几轮(实测脏草稿时 `1234 -> 1564`)。`clb_mul` 的 NR 没这个问题 —— 它是 `%rep W { set_1; ror }`,每个位都会轮到一次。 `S` 的排法:`S+0` TEN(乘数 10,每轮重建)、`S+1` 轮数计数器、`S+2` copy 缓冲、 `S+3..S+10` 是 `clb_mul` 的 PL/PH/MCA/S/Ci/T/F/NR —— **MC 直接就是 `N`,MUL 就是 `S+0`**, 所以乘法器不用额外的两个 cell。每轮开始把 `Ci` 清 0(上一轮留下的是进位输出)。 存在的理由:`clb_sub_nc` 会吃掉 A 和 B,所以"重复减法"的除法器每轮都得 copy 两个 副本;二进制长除法每轮都要拿同一个除数去比/减,必须有个不破坏操作数的减法。 `clb_divmod` 换成长除法(§7.6)之后,每一轮开的就是它。另外实测过一次"预计算 `~D` 再走 `raw_add`"的写法(同样的纸带、每轮少一次 copy,单轮 2019 → 973 步), 但 `docs/divmod.md` §3 的设计指名用 `raw_sub`、而且它是上一轮专门为长除法加的,所以没有换。 ### 7.10 有符号数包装宏:`clb_digits_signed` / `clb_divmod_signed` 约定在 §5.4(二补码、`-0042` 这种显示、截断除法、静默回绕)。两个宏都只是**包装**, 真正的活还是 `clb_digits` / `clb_divmod` 干的 —— 所以纸带的大头没变,代价是取符号位 和四次条件取负。 | 宏 | 签名 | 语义 | 吃什么 | cell | 纸带 | 验证 | |---|---|---|---|---|---|---| | `clb_digits_signed` | `N REG S T F` | 负数先打 45('-'),再打 **\|N\|** 的四位 | N | 4 + 13 + 2 | 12151 | 2048 个值全扫 | | `clb_divmod_signed` | `N D Q R S T1 T2 F` | `Q = trunc(N/D)`、`R = N - Q*D`(余数随被除数) | N、D 变成 \|N\|、\|D\| | 4 + 7 + 3 | 6030 | 4202 组全扫 | 纸带是 `drv/` 驱动下的实测值;同一个驱动布局下 `clb_digits` 是 11579、`clb_divmod` 是 4481,**包装本身花 572 / 1191 字符**。验证在 `r8forge_byte_op_test` 的 `test_digits_signed`(2048 个值)和 `test_divmod_signed`(\|a\|,\|b\| ≤ 32 全组合 4225 组 + 0/±1/±1023/±1024 的边界组合,最坏 35,202 步)。 clb_digits_signed: 7 -> "0007" 2047 -> "-0001" 1024 -> "-1024" 0 -> "0000" clb_divmod_signed: 7/2 -> 3 r 1 -7/2 -> -3 r -1 7/-2 -> -3 r 1 -7/-2 -> 3 r -1 契约(细节见两个宏的文件注释): * **`clb_digits_signed N REG S T F`**:N 被吃干净;`REG` 起 4 格、`S` 起 13 格、 `T` 进来都必须干净(和 `clb_digits` 一样);`F` 只用最低位、进来最低位要是 0。 结束 `T`、`F` 都是 0。 * **`clb_divmod_signed N D Q R S T1 T2 F`**:S 起的 7 格只要 `S+6`(buf)干净; `T1`、`T2`、`F` 进来必须干净,结束都是 0。**N、D 被吃成绝对值**(要原值自己留副本)。 五个设计点: 1. **符号位怎么读**:`rol`(= W-1 次 `ror`)把 bit `W-1` 转到 bit0,`bit_copy` 抄进标志格, 再 `ror` 把 N 原样还回去 —— 三段一共 49 字符。 **不能用 `clb_bit_mov`**:它顺手吃掉源位,于是 N 少了符号位、转回去就成了 `N - HALF`。负数是拿 N 去取负的,少了这一位 `-1024` 就变成 0(`1024 -> "0000"`), 而 `bit_copy` 走缓冲格、源位原样保留,正是它多出来的 27 个字符买的东西。 **也不用 `clb_sub_nc T HALF` 那种比较**:`clb_sub_nc` 展开一次就是 765 字符,还要 再造一个 HALF 常数格(≈60)。 2. **`clb_digits_signed` 的 '-' 放在 `S+10`**(`clb_divmod` 的商格):第一轮 `clb_divmod` 进来第一件事就是 `erase` 它,所以这个常数格不用调用者事后擦,也不破坏"S 起 13 格 干净"的入口契约。 3. **标志位要活过 `clb_divmod`**:符号在除法**前**(决定取不取负)和除法**后**(决定 Q、R 的符号)都要用,而 `biz`/`rnz` 是循环对 —— 块的身体必须把那个条件位清掉才能 退出。所以"用完还要留"的那一位要搬到另一格存着(`clb_bit_mov`,11 字符): `T2 = sign(N)`、`F = sign(D)`;第 5 步的 `flb` 把 `F` 从 `sign(D)` 翻成 `sign(N)^sign(D)`(那一支进来就说明 `sign(N)=1`),商的符号就齐了。 4. **取负用的草稿格借 `S+6`**:`clb_neg_ip` 要求草稿格干净,而 S 里只有 `S+6`(buf) 有"干净"这个契约;`clb_neg_ip` 用完它就归零,所以 `clb_divmod` 进场时它照样干净。 5. **四次取负**:|N|、|D|、R、Q 各一次,没有一次是多余的(Q 的符号靠第 3 条折成一次)。 单次 `clb_neg_ip` 是 110 字符,所以包装的 1191 里有 440 是这四次。 配 `examples/calc.r8asm` 用时只剩"一元负号"一件:字符 45 在**栈空**(cell `DEPTH` 的值为 0)时置 `NEG`、清 `ISCMD`,下一个压栈的数被 `clb_neg_ip` 取负。判据是栈深而 不是"上一个字符是不是运算符":栈机器里 `1 2 + -` 的 '-' 是二元减法(a 弹空了就是 0, `0 - 栈顶` 和取负同效),按"上一个是运算符"判会把那个负号悄悄吞掉。 --- ## 8. 原地 `_ip` 家族(结果回到原来的 cell) | 宏 | 签名 | 语义 | cell | 纸带 | 验证 | |---|---|---|---|---|---| | `clb_not_ip` | `A` | `A = ~A`(反码) | 1 | 22 | 256/256 | | `clb_inc_ip` | `A T` | `A = A + 1` | 2 | 88 | 256/256 | | `clb_neg_ip` | `A T` | `A = -A`(补码取负) | 2 | 110 | 256/256 | | `clb_dec_ip` | `A T` | `A = A - 1` | 2 | 132 | 256/256 | | `clb_nonzero` | `B F T` | `F = (B != 0)`,**B 不动** | 3 | 280 | 256/256 | | `clb_add_ip` | `A B T F` | `A += B`,**B 被吃** | 4 | 722 | 2048 抽样 | 对比写回 S 的切片版(`clb_inc_nc` 552 / `clb_neg_nc` 574,各 3 cell): **原地版短 5 倍、少一个 cell**。 算法不是逐位测进位(那在两个 cell 里确实不行),而是: 1. 用 `[ ... ]` 的自然语义把**最低位连续的 1 清掉**(`flb` + `ror`),遇到第一个 0 退出; 2. 那个 0 翻成 1(输入全 1 时跳过,正好是回绕那一格); 3. 剩下的位置只旋转,转满 `_CELL_SIZE` 格。 "还要转几格"用 **T 的位**计数:T 先做成 `_CELL_MAX`,每转一格 `set_0` + `ror` 消掉一个 1, 一串 1 的长度就是剩余圈数。于是两个 cell 够用 —— 关键认识是**被测的是计数器,不是数据**, 所以"`[...]` 跑一次就吃掉被测位"不是障碍。 - `clb_neg_ip` = `clb_not_ip` + `clb_inc_ip`; - `clb_dec_ip` = `clb_neg_ip` + `clb_not_ip`(恒等式 `B - 1 = ~(-B)`),不用新算法; - `clb_nonzero` 每轮把 B 的一位**搬进** T(`clb_bit_mov` 顺手清掉 B 那一位),是 1 就把 F **置一**(`set_1`,不是 `flb` —— 翻转会被偶数个 1 翻回 0)并把 B 那一位还原; - `clb_add_ip` 不写逐位进位链,而是 **`while B != 0: A += 1; B -= 1`**: 循环体在纸带里只出现一次,长度与 B 无关,代价是运行 O(B)(B=255 时约 30 万步)。 --- ## 9. 乘法器(`asm/mul.r8asm`) `clb_mul MC MUL PL PH MCA S Ci T F NR`:`(PH:PL) = MC * MUL`,10 个 cell,最小驱动 **3964 字符**(`drv/mul_byte.r8asm` 3977)。MC 保持原样,**MUL 结束为 0**。 算法是**二进制移位-加法**(竖式乘法),一位一位串: ``` A:PH = 0 ; C:F = 0 ; Q:PL = MUL repeat _CELL_SIZE: if Q & 1: (C:PH) += MC ; 一次 W 位加法,进位出到 F (C:PH:PL) >>= 1 ; 跨格右移,最高位补 0,最低位(刚看的那位)丢掉 ``` - 轮数 = 位宽,与两个操作数的**值**无关;11 位下最坏 **26123 步**(`2047*2047`)。 - 纸带长度与 MUL 无关(循环体只出现一次)。 - `MCA`/`S`/`Ci`/`T` 是草稿;`F` 是移位寄存器的最高位(进位),`NR` 是轮数计数器 (`%rep _CELL_SIZE { set_1; ror }` 做成全 1,每轮 `set_0` + `ror` 吃掉一个)。 - 跨格移位:三格先各 `ror`,把要注入的位搬到 bit0(`rol`),`clb_bit_mov` 搬过去,再 `ror` 回来;**低位那对先搬**(PH→PL 先做),否则 PH 的 bit0 已被 F 覆盖。 --- ## 10. 拼起来是什么样 ### 10.1 16 位加法:靠 `clb_add_nc` 的进位输出串 ``` clb_add_nc PL B_lo T Ci ; 低字节相加,进位出到 Ci(A、B 被吃) clb_add_ip PH Ci S F ; 把进位加进高字节(Ci 被吃) ``` ### 10.2 `asm/test.r8asm`:标准库的"全家桶"测试 不是演示,是**回归测试**:`asm/` 里每个宏至少被真的调用一次,r8asm 的语言特性也各走一遍 (`%include` / `%macro` / `%rep` / `%for` / `%synth` 的 `map` 和 `stat` / `.var` / `.anchor` / `.tp` / `.xor` / `step` / `back` / `loop` / `endloop`)。每段调用完就 `output`,所以 整条 OUT 流就是指纹,头部 `; out ...` 写着期望值 —— `r8forge_examples_test` 会跑它并逐项 核对(同一个测试也跑 `examples/`,见 §10.3)。 段落:A 基础设施 → B 位级切片 → C `raw_*`(保留操作数)→ D `clb_*`(破坏性)→ E 大宏(`clb_ones` / `loop` / `clb_digits` + `clb_undigits`)→ F 语言特性(自定义 `%macro` + `%rep` + `%for` + 两份 `%synth`)→ G 两轮 hash(`clb_add_nc` + `clb_mul`)。 11 位下纸带 **62351 字符**、**202159 步**、93 个 `out`。两个约束值得记住: * **必须留在 65536 条指令以下**:ROT-8-viz 的 `INS_SIZE`(`include/rot8/rot8.h`)是 65536 (现在的缓冲是从纸带长度现算的,`INS_SIZE` 只是历史常量,但交叉验证仍按这条走), 超了旧 `read_tape` 会截断。所以 hash 只留两轮、每个宏只调一次。 * **两个有符号包装宏不在全家桶里**(§7.10):它们各自要把 `clb_digits` / `clb_divmod` 再展开一份(+12.1k / +5.6k),而全家桶离 65536 只剩约 3k。它们的单点回归是 `examples/signed_demo.r8asm`,穷举在 `r8forge_byte_op_test`(§11)。 * 三个实现(`r8forge_derive`、`r8forge_tape_run`、ROT-8-viz 的 `rot8_test -n`)对这份 `out` 逐位一致;最后 6 个值 `1322 5 82 0 1786 94` 是老 hash 的指纹 (`1322`/`1786` = 两轮的 h,`5`/`94` = 两轮的 PH,`82` = 被乘数保留、`0` = 乘数被吃)。 ### 10.3 `examples/` 里的例程:每组宏一份 `examples/` 下每个 `.r8asm` 都是**能跑的程序**,头部一行 `; out ...` 写它打印什么: ```sh r8forge examples/<名字>.r8asm > t.rot8 r8forge_tape_run t.rot8 # 打印 out 和步数 ``` | 文件 | 演示哪一组 | 打印 / 说明 | |---|---|---| | `base_macros.r8asm` | §5 基础宏 | `set_0` 只清一位、`erase` 清整格、`rol`/`ror` 转圈、`copy`/`bit_copy` 保留源、`clb_bit_mov` 吃源、`step` | | `bit_adder.r8asm` | §6 位级宏 | 4 位行波加法器(`clb_bit_add_nc` 串进位链),再对比 `bit_raw_add` 保留操作数 | | `byte_raw_ops.r8asm` | §7.1 + §7.8 | `raw_add`/`raw_inc`/`raw_and`/`raw_or`/`raw_xor`/`raw_sub`,每个都把操作数打出来证明没被吃 | | `byte_clobber.r8asm` | §7.2 + §7.3 | `clb_add_nc`/`clb_sub_nc`/`clb_neg_nc`/`clb_inc_nc`(操作数被吃),以及 `clb_and` 的 B 残留 | | `byte_in_place.r8asm` | §8 | `clb_not_ip` / `inc` / `neg` / `dec` / `clb_add_ip` / `clb_nonzero` | | `sum_loop.r8asm` | §5.1 + §7.5 | `clb_ones` + `loop`/`endloop` 算 `1+2+...+N`(次数来自数据,不是汇编期常数) | | `mul_demo.r8asm` | §9 | 82×141、2047×2047 的 `(PH:PL)` | | `divmod_demo.r8asm` | §7.6 | 2047/10、2047/1(旧版第二个会 HANG),顺带证明 N、D 保留、草稿可以反复用 | | `digits_demo.r8asm` | §7.7 | 1234 和 7 的 4 位 ASCII | | `signed_demo.r8asm` | §7.10 | `-7/2` 的商和余数(`-0003`、`-0001`)、以及 `1024 -> "-1024"` 那个绝对值边界 | | `undigits_demo.r8asm` | §7.9 | `"1234"` → 1234、`"0007"` → 7,以及 2047 的 `digits → undigits` 往返 | | `full_add*.r8asm` | §3 `%synth` | 四种写法(`map` / `stat` / `layers` / 手写);输入全 0,所以 `out 0 0` | `r8forge_examples_test` 会把 `examples/` 里所有 `.r8asm` 跑一遍,实跑的 `out` 和头部那行 逐项比(顺带打印纸带长度和步数)。它保证例程既**汇编得出来**、又**还是那样输出**; `r8forge_synth_test` 另外用 8 种输入查 `full_add` 的正确性。 --- ## 11. 验证矩阵 | 测试 | 覆盖 | 断言口径 | |---|---|---| | `r8forge_byte_op_test` | 23 个测试项 = 22 个宏(`clb_neg_nc` 的 Ci=1 / Ci=0 各算一项),见 §7.1、§7.2、§7.5、§7.6、§7.7、§7.9、§7.10、§8、§9 | **按返回值**:穷举 0..255(`clb_add_ip` 2048 抽样、`clb_mul` 65536 全穷举、`clb_ones` 12 个计数全穷举、`clb_divmod` 8 个除数 × 全部 2048 个被除数 = 16384 组全穷举、`clb_digits` 全部 2048 个值全穷举、`clb_digits_signed` 全部 2048 个值全穷举(含 1024 → `-1024`)、`clb_divmod_signed` \|a\|,\|b\| ≤ 32 全组合 + 边界 = 4202 组全穷举(与 C 的 `/` 和 `%` 逐项比)、`clb_undigits` 2048 个值 × 干净/高位垃圾 2 种 = 4096 组全穷举),任一不符即退出码非 0 | | `r8forge_synth_test examples/full_add.r8asm` | `%synth` 端到端:汇编 + 跑 8 种输入 | `all eight combinations ok` | | `r8forge_examples_test` | `examples/` 里全部 19 个程序(11 组宏例程 + 4 个 `%synth` 例子 + 交互例程 + 计算器 + 有符号例程,见 §10.3)**加上 `asm/test.r8asm`**(§10.2) | **按返回值**:每个头部 `; out ...` 与实跑 `out` 逐项相等,缺这一行也算失败;写了 `; in ...` 的先把那串字符喂给 `inp` | | `r8forge verify_clb_bit_add_nc.r8asm` | 4 cell 加法切片(进位进→出) | 单点:`0+0+Ci` | | `r8forge verify_clb_bit_inc_nc.r8asm` | 3 cell 自增切片 | 单点 | | `r8forge_derive verify_loop.r8asm -1 0=N` | 动态循环:`N=0..11` 时循环体跑 `N` 次(`A = N`、`C = 0`) | 逐值 `out` | | `r8forge verify_set_0.r8asm` | `set_0` 只清 LSB | `-1 0=255 → 254`、`0=128 → 128` | | `r8forge_macro_docs_test` | `asm/` 里 55 个宏的注释格式 | 全绿或报错行号 | | `r8forge_tape_run ` | 第二个解释器,直接跑纸带 | 与 `r8forge_derive` 对答案 | | `r8forge_derive -1/-2` | 拿汇编源码跑,打印 `out` / 非零 cell | 人工/脚本比对 | `r8forge_derive` 现在**会检查汇编错误**:`import_file` 只表示"文件打开了",漏一条 `%include`(`unknown macro`)时汇编器的 error 位会被置上、纸带是**截断**的 —— 以前 `derive` 不看这个标志,于是会拿半截纸带跑出一个看起来正常的错答案(实测踩过: `clb_digits` 少 include `add_ip` 时四个数字全是 `'0'`)。现在它和其它入口一样打印 `could not assemble` 并返回 1。**看到 `out` 结果"太整齐"就先看 stderr 有没有这句。** 只有 `r8forge_byte_op_test` 和 `r8forge_examples_test` 是**按返回值**判断的;其它要么只证明 "汇编得出来"、"位级正确",要么是单点探针。改宏之后跑 §11 前几个(外加 docs test)。 --- ## 12. 已知边界(别重试) | 想做的 | 结论 | |---|---| | 3 个 cell 做加法切片 | 层数上限 5 和 8 都报 `no program up to N layers`(自增/取负 3 cell 有解,两个操作数塞不进 3 个 cell) | | 用 `%synth` 写"原地"表(`A←~A^Ci` 等四个) | 全部无解(原因见 §3.4);**手写可以**(§8 的 `_ip` 家族) | | 让切片自己在输入上取反 | 无解(表达不出"无条件翻转");取反放在切片外面(一条 `flb`) | | 4 cell 加法切片要保留 A、B | 无解;要留操作数用 6 cell 的 `bit_raw_add` | | 字节级(`2^16` 项)交给 `%synth` | 搜索空间不可行 | | "每个 bit 一个 cell" 拼字节级运算 | 能跑通但没意义(一个 cell 已经能放一个字节、位也读得出来);这份实现**已删,别再加回来** | --- ## 13. 维护 - **改几何(位宽 / 环大小)**:**用构建选项,别改常量** —— `-DR8FORGE_CELL_SIZE=<1..32>`、`-DR8FORGE_MEMORY_CELLS=<1..65536>`,CMake 里越界直接 `FATAL_ERROR`;五份虚拟机(`tests/synth_test.cc`、`tests/byte_op_test.cc`、 `tests/examples_test.cc`、`src/derive.cc`、`tests/tape_run.cc`)都从 `geometry.hh` 读, 不用动。`asm/` 里的宏靠 `_CELL_SIZE` 自动跟随。换环大小之前先确认目标纸带的**最高格号** (SPEC §1.2 有实测表和理由:程序碰到 ≥ 环大小的地址会被折回去,输出可能不变但步数会变)。 `ROT-8-viz` 侧用 `-m/--mem` 和 `-b/--cell` 对齐同一套几何。 - **位宽上限是 32**:每份 VM 的 cell 都存在 `uint32_t` 里,`geometry.hh` 的 mask 特判了 32, CMake 里加守卫(`-DR8FORGE_CELL_SIZE` 越界直接 `FATAL_ERROR`)。想上 64 位得同时改五份 VM 的 cell、`geometry.hh`、汇编器的立即数类型(`r8asm.hh` 的 `data` 现在还是 `int16_t`)以及 `ROT-8-viz` 的 `rot8_data` / `ROT8_MAX_CELL_SIZE`,否则交叉验证没法做。 `drv/` 里的驱动必须用 `.var D _CELL_SIZE * 30103 / 100000 + 1` 算位数, **不能把窗口写死 4 格** —— 写死过,`byte_op_test` 的 digits / digits_signed / undigits 三项因此在 16 位下一直挂着(16 位要 5 位数字),2026-11 才修。 - **`byte_op_test` 在 17 位以上打印 `skipped`**:它每一轮都是 2^W 行,跑不动;但文件本身要在 1..32 位都编得过(`1 << 32` 是未定义行为,所以 `kCellMod` 在 31/32 位被夹成 0)。 8 / 11 / 16 位下它是真跑的(16 位一轮约 7.5 分钟)。 - **加宏**:先按 §4.1 选前缀/后缀,再写 §4.2 的注释块,跑 `r8forge_macro_docs_test`; 能进 `byte_op_test` 就进(那才有按返回值的验证)。 - **改指令模型**(合成器的块集合、代价):必须 bump `kModelVersion`,否则 `.r8forge_cache/` 里的旧结果会被当成最优。**缓存按真值表存,不含位宽**,所以换位宽不用重算 (实测 32 位命中现成条目只要 0.4 s);只有 bump 版本号、换 `--synth-chars` 口径或删目录才要 重跑,全量一轮约 8 分钟(44 线程机器上 497 s,其中 479 s 是全加器那张 6 参数表)。 - **改本文的数字**:照 §1.3 的口径重新量,别把驱动长度和最小驱动长度混在一列。 --- ## 14. 设计笔记(搬到了 `docs/`) 契约在本文档里;"为什么这么写"和失败记录搬到 `docs/`,免得正文越来越长: * [`docs/divmod.md`](docs/divmod.md) —— `clb_divmod` 的移位-恢复除法:每轮状态、W+1 位比较怎么拆、7 个草稿格、5 个坑、实测步数、没做的优化。 * [`docs/byte-ops.md`](docs/byte-ops.md) —— 字节级库为什么是现在这样:`raw_*` 与 `clb_*_nc` 的取舍、原地 `_ip` 的突破、乘法器从重复加法换成移位-加法的那一课。 * [`docs/calc.md`](docs/calc.md) —— 计算器:命令协议、3 格 RPN 栈、终端外壳(回显/退格/提示符)与它的三个坑、实测步数。 * [`docs/hardware.md`](docs/hardware.md) —— 把这台机器做出来:ISA 翻成硬件需求(含括号扫描的确切边界)、ROM/RAM 预算、FPGA / 分立 TTL / 机电三档载体、打包器与 RTL 对拍路线。 (原来 §14 的内容整段搬进了 `docs/divmod.md`,小节号从 `14.x` 改成 `1..6`。)