Files
dsh 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).
2026-11-07 16:29:17 +08:00

56 lines
1.7 KiB
Plaintext

%include "asm/add_ip.r8asm"
; 把"数量"展开成"一串 1":B = 2^A - 1,也就是**从末位起 A 个连续的 1**。
;
; 0 -> 0
; 1 -> 1
; 4 -> 1111 (0x0F)
; 7 -> 1111111 (0x7F)
;
; 前提:A <= _CELL_SIZE,调用者保证,这里不检查(A 更大时 2^A-1 会绕回)。
;
; 算法是"边转边补 1":
;
; B = 0
; while A != 0: B = 2B + 1 ; A -= 1
;
; `2B + 1` 在这台机器上就是 **`rol` + `set_1`**:左旋一格会把 B 的最高位带回到
; 末位,紧随其后的 `set_1` 正好把它盖成 1,于是等价于"左移、低位补 1"。
; A 直接当计数器吃掉(省一次 copy:copy 要 495 字符),循环体在纸带里只出现一次,
; 所以长度和 A 的大小无关;代价是运行 O(A),A <= _CELL_SIZE 所以最多十来轮。
;
; 为什么不用"B = 1,转 A 圈,再减一"那种写法:那样循环体里只剩 `rol`(省 4 字符),
; 但末尾要多一次 `clb_dec_ip`(132 字符),还多一次 `set_1` 打底 —— 反而更长。
;
; 另一个能用的恒等式(写在这里省得下次重推):`clb_inc_ip B` 会把 n 个 1 变成
; 2^n(末位起第 n+1 位是 1),所以"n 个 1 -> 2^n -> 单 1"和它的逆都有现成的路。
; Macro clb_ones
; %1: Cell A
; %2: Cell B
; %3: Cell T
; %4: Cell F
;
; B = 2^A - 1(从末位起 A 个 1);A 被吃干净(结束为 0),T 和 F 结束也都是 0。
; 前提:A <= _CELL_SIZE,不做检查。
%macro clb_ones 4
.anchor before_clb_ones
; B 得先清干净:下面每轮只负责在低位补 1,高位留着原样的垃圾会脏在结果里
erase %2
clb_nonzero %1 %4 %3
.tp %4
biz
.tp %2
rol
set_1
clb_dec_ip %1 %3
clb_nonzero %1 %4 %3
.tp %4
rnz
.tp before_clb_ones
%endmacro