clb_dec_ip A T A = A - 1 2 cells 106 chars 256/256
clb_nonzero B F T F = (B != 0), B intact 3 cells 209 chars 256/256
clb_add_ip A B T F A += B, B is eaten 4 cells 558 chars 2048 sampled
against raw_add (6 cells, 1647) and clb_add_nc plus a copy per round (688 + 364).
Add is the primitive the multiplier needs, so this was the expensive one.
decrement needed no new algorithm: B - 1 = ~(-B), so it is clb_neg_ip then
clb_not_ip, and both are already in place.
The add does not do a per bit carry chain, and it is worth being clear why not:
a full adder's carry is maj(a,b,c), i.e. a pairwise conjunction, and every
conditional test eats the bit it tests, so a hand written ripple needs several
copies of each bit and nested tests -- long and fragile, and it was the reason I
first called this impossible.
What works instead leans on something true of this project: the metric is tape
length, not execution steps. So
while B != 0: A += 1 ; B -= 1
The loop body appears in the tape once, so the length does not depend on B. The
cost is O(B) runtime, about 300k steps at B = 255 against a 5M limit. This is a
general lever: anywhere length is what matters, ask whether a loop can replace
generated code.
The one thing that was genuinely awkward is "B != 0", since biz only looks at the
low bit. clb_nonzero walks the eight bits, moves each into a work cell (which
clears that bit of B), and if it was set, sets F and puts the bit back; B comes
out untouched. Note set_1, not flb: flb flips, so an even number of set bits
flipped the flag back to zero and 3, 5 and 255 all read as "zero" until I fixed
it.
For the multiplier this means one copy per round (364) to keep the multiplicand,
so about 920 per round, roughly 8k for the whole multiplier instead of 13k.
Tests: byte_op_test is sixteen operations now, 1.5 s. test_add_ip is sampled
(8 accumulators x 256 addends) because the loop makes exhaustive runs slow.
82 lines
2.1 KiB
Plaintext
82 lines
2.1 KiB
Plaintext
%include "asm/dec_ip.r8asm"
|
|
|
|
; 原地加法:A <- A + B,结果留在 A 里。
|
|
;
|
|
; 没有去写"逐位的进位链"加法(那需要 maj(a,b,c),也就是两两的合取,而每个条件测试
|
|
; 都会吃掉被测的那一位,所以要么先拷贝好几份位、要么嵌套测试,又长又脆)。
|
|
; 这里利用一件在本仓库里成立的事:**只有纸带长度是目标,运行步数不是**。
|
|
; 于是加法可以写成
|
|
;
|
|
; while B != 0: A += 1 ; B -= 1
|
|
;
|
|
; 循环体在纸带里只出现一次,长度和 B 的大小无关。代价是运行步数 O(B)(B=255 时约 30 万步,
|
|
; 上限 500 万,够用)。
|
|
;
|
|
; 剩下的问题是"B != 0"怎么测 —— 只有 `biz` 测最低位,要测整格是否为零得把八位都看一遍,
|
|
; 而且看的时候不能把 B 吃掉。做法是每看一位:
|
|
; 1. 若该位是 1,把它搬到工作位 T(这一步会清掉 B 的这一位);
|
|
; 2. 若 T 是 1,就把它记进 F(累加,不清),并把 B 的那一位还原;
|
|
; 3. B 转一格,看下一位;八轮之后 B 回到原位、一位不少,F = (B != 0)。
|
|
; 为什么"还原"要放在测试之后:`]` 只能落在最低位为 0 的格子上,所以测试那一步必须先把
|
|
; 被测位清掉;还原放在块外面,靠 T 的值来决定要不要翻回来。
|
|
|
|
; Macro clb_nonzero
|
|
; %1: Cell B
|
|
; %2: Cell F
|
|
; %3: Cell T
|
|
;
|
|
; F = (B != 0),B 保持原样。T 结束时是 0。
|
|
%macro clb_nonzero 3
|
|
.anchor before_clb_nonzero
|
|
|
|
.tp %2
|
|
set_0
|
|
|
|
.tp %1
|
|
%rep _CELL_SIZE
|
|
biz
|
|
.tp %3
|
|
flb
|
|
.tp %1
|
|
flb
|
|
rnz
|
|
.tp %3
|
|
biz
|
|
.tp %2
|
|
set_1
|
|
.tp %1
|
|
flb
|
|
.tp %3
|
|
flb
|
|
.tp %3
|
|
rnz
|
|
.tp %1
|
|
ror
|
|
%endrep
|
|
|
|
.tp before_clb_nonzero
|
|
%endmacro
|
|
|
|
; Macro clb_add_ip
|
|
; %1: Cell A
|
|
; %2: Cell B
|
|
; %3: Cell T
|
|
; %4: Cell F
|
|
;
|
|
; A <- A + B(mod 256),原地;B 被吃干净(结束时为 0),T 和 F 结束都是 0。
|
|
%macro clb_add_ip 4
|
|
.anchor before_clb_add_ip
|
|
|
|
clb_nonzero %2 %4 %3
|
|
|
|
.tp %4
|
|
biz
|
|
clb_inc_ip %1 %3
|
|
clb_dec_ip %2 %3
|
|
clb_nonzero %2 %4 %3
|
|
.tp %4
|
|
rnz
|
|
|
|
.tp before_clb_add_ip
|
|
%endmacro
|