Files
dsh 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 ?.
2026-11-11 11:04:14 +08:00

140 lines
7.3 KiB
Markdown
Raw Permalink Blame History

This file contains ambiguous Unicode characters
This file contains Unicode characters that might be confused with other characters. If you think that this is intentional, you can safely ignore this warning. Use the Escape button to reveal them.
# 字节级库为什么是现在这样
契约(签名、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`。别再加回来。