# 字节级库为什么是现在这样 契约(签名、cell 数、纸带长度、谁验证)在 [`SPEC.md`](../SPEC.md) §7–§9;这里讲 "为什么这么设计"和一路踩出来的结论。原来的位置是 README 的「字节级运算」一节。 前提:一个 cell 是**一个机器字**(默认 11 位,几何在 `include/r8forge/geometry.hh`), "字节级"其实是"机器字级";宏里写 `%rep _CELL_SIZE` 的地方自动跟着位宽走,所以下面 说的位宽相关数字都是 11 位下的。 ## 1. 一个字节怎么用位级切片算 位级切片(`clb_bit_add_nc` 之类)只碰每个 cell 的**最低位**。于是字节级宏就是 "轮转驱动":每轮把当前最低位送进切片,再把整个字 `ror` 一格,W 轮走完。 ```asm %include "asm/raw_add.r8asm" .var A 0 .var B 2 .var Ci 4 .var S 6 .var Co 8 .var tmp 1 raw_add A B Ci S Co tmp ; S = A + B,Co = 进位,A、B 保留 ``` 注意 `Ci` 是**真正的进位输入**:宏不动它的初值,由调用者给(0 就是普通加法,1 就是 "自带 +1",或者接上一字节的进位输出)。这条约定让多字节串接成为可能,也曾经写错过 (加法里顺手 `set_0`、自增里顺手 `set_1`,那就不是输入了)。 ## 2. `raw_*` 与 `clb_*_nc`:省 cell 的代价 `raw_add` 要 6 个 cell,因为它**保留** A、B(外加一个真草稿)。如果调用者不在乎操作数 被吃掉,4 个 cell 就够 —— 这就是 `clb_add_nc` 那一族:`A`、`B` 被吃干净,结果在 `S`, 第 4 格是"进→出"的进位。 | 家族 | 代表 | cell | 操作数 | 纸带(11 位) | |---|---|---|---|---| | `raw_*` | `raw_add` | 6 | 保留 | 2199 | | `clb_*_nc` | `clb_add_nc` | 4 | 吃掉 | 937 | | `clb_*_ip` | `clb_add_ip` | 4 | 原地 | 726 | 三条细节值得记: * **取反放在切片外面**:`clb_sub_nc` = 先 `clb_not_ip B`(整字节取反一次)再走加法, 比"每 bit 取反一次"短二十来个字符,而且 B 本来就会被加法吃掉,取反它没有代价。 * `clb_sub_nc` 的进位输出是**没有借位**(`A >= B` 时为 1),顺带就是无符号比较。 * **别在 Bo 上再取反**:`clb_not_ip` 是整格取反,0 变 2047、1 变 2046,不是 0/1。 ## 3. 原地 `_ip`:两个 cell 的补码,以及一条被推翻的结论 `clb_neg_ip A T` 把 `A` 原地变成 `-A`,只要 **2 个 cell、111 字符**;切片版 `clb_neg_nc` 是 3 个 cell、610 字符。`clb_inc_ip` 是 2 个 cell、89 字符,切片版 586。 **"原地补码不可能"这个结论是错的**,记一下它是怎么错的(别再复现同样的推理): * `%synth` 的四个原地表(`A←~A^Ci`、`A←A^Ci`、`A←A^B^Ci`、`A←A^~B^Ci`)确实全部报 `no program up to 8 layers`。原因是**一个合成块只有一个条件 cell**,区分不了 "A=1 且 Ci=0" 和 "A=1 且 Ci=1"。这一步是实测,没问题。 * 错在把它当成了整条路的结论:手写**不一定要照逐位进位链写**。 真正可行的算法换了个思路,不去逐位测进位: 1. 用 `[ ... ]` 的自然语义把**最低位连续的 1 清掉**(`flb` + `ror`),遇到第一个 0 退出; 2. 那个 0 翻成 1(全 1 输入时跳过,正好是回绕那一格); 3. 剩下的位置只旋转。 "还要转几格"用 **T 的位**计数:T 先做成 0xFF,每转一格 `set_0` + `ror` 消掉一个 1, 一串 1 的长度就是剩余圈数。于是两个 cell 就够,而且没有"无条件翻转"那种表达不出的动作。 顺带纠正另一半:`[ ... ]` 的"跑了就必然消耗被测位"不是死路 —— 只要被测的是**计数器**, 不是数据。这条以前被写成"手写也做不到(2 cell)",错的。 `clb_dec_ip` 不用新算法:`B - 1 = ~(-B)`,所以它是 `clb_neg_ip` + `clb_not_ip`(133 字符)。 ## 4. 原地加法:只有纸带长度是目标,步数不是 `clb_add_ip A B T F` 把 `A += B` 做在 4 个 cell 里、**726 字符**(`raw_add` 是 2199/6 cell)。 没有去写逐位的进位链加法(全加器的进位是 `maj(a,b,c)`,也就是两两的合取,而每个条件 测试都会吃掉被测的那一位,要么先拷贝好几份位、要么嵌套测试,又长又脆),而是利用了 本仓库的一个取舍 —— **只有纸带长度是目标,运行步数不是**: while B != 0: A += 1 ; B -= 1 循环体在纸带里只出现一次,长度与 B 的大小无关;代价是运行 O(B)(B=255 时约 30 万步, 上限 2000 万)。`clb_nonzero B F T` 负责"B != 0"的判断(`biz` 只测最低位,得把 W 位都看 一遍、还不能把 B 吃掉):每位搬进工作位 T、若 T 是 1 就把 F **置一**并还原 B 的那一位。 **注意是 `set_1` 不是 `flb`** —— 这里踩过:`flb` 是翻转,偶数个 1 位会把标志翻回 0 (3、5、255 都测错过)。 这个取舍在别处也能用:凡是"长度优先"的地方都可以想"能不能用循环把代码压掉"。 ## 5. 乘法器:从重复加法换成移位-加法的这一课 现在 `clb_mul` 是**二进制移位-加法**(竖式乘法),一位一位串: 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,最低位(刚看的那位)丢掉 **3977 字符、10 个 cell**,轮数 = 位宽、跟两个操作数的值都无关(11 位下封顶 26123 步)。 旧的重复加法轮数 = `MUL` 的值,代价随乘数线性长大:`255 × 255` 是 73 万步, `2047 × 2047` 直接撞 2000 万步上限(`HANG after 5000000 steps`)。 **设计上的教训**:上一轮把移位-加法否掉了,理由是「重复加法更短」。实测反了 —— 移位-加法不但短 1000 字符(5007 → 3977),步数还少一到两个数量级,只有小乘数(0/1) 比旧版慢一点点。先看目标函数再选算法没错,但目标函数里得把「运行步数有 2000 万上限」 这一条写进去。 拼法上踩过两个坑(细节在 `asm/mul.r8asm` 注释里):跨格移位要按"低位那对先搬", `biz`/`rnz` 是循环对、条件块的身体必须把被测位吃掉。 ## 6. 一个坑:`biz`/`rnz` 看的是最低位 biz: 最低位 == 0 -> 跳到匹配的 ']' 之后 rnz: 最低位 == 1 -> 跳回匹配的 '[' 不是 Brainfuck 那种"整格是否为零"。所以 `set_0` = `[-]` 是**清最低位**:255 → 254、 128 → 128、5 → 4;要清整格得 `%rep _CELL_SIZE { set_0; ror }`(就是 `erase`)。 仓库里曾经有三份解释器把它写成整格零判断,于是所有字节级程序看起来都在死循环 —— 顺着那个错误还得出过"字节级运算只能一位一 cell"的结论,是错的。权威语义见 `ROT-8-viz/src/rot8.c`: ```c void rot8_biz(rot8_iter *iter) { if ((*(iter->mem_now) & 1) == 0) { ... } } void rot8_rnz(rot8_iter *iter) { if ((*(iter->mem_now) & 1) == 1) { ... } } ``` **所以以后凡是"字节级看起来跑不动",第一个怀疑对象是虚拟机,不是库。** ## 7. 一个被删掉的方向 "每个 bit 一个 cell 再拼字节级运算"能跑通(32 cell、1308 字符、65536 组合全对),但既然 一个 cell 就能放一个字节、位也读得出来,就没必要为每个 bit 花一个 cell —— 那份实现已经 删了,要拼字节级运算就用 `raw_*` / `clb_*_nc` / `clb_*_ip`。别再加回来。