algorithm - tinyAVR : How can one multiply by 203, 171，还是 173 真的快？

Question

关注最坏情况下的循环计数，我为 Atmel 的 AVR 编写了整数乘法例程。架构。
在一个特定的实现中，我遇到了 2+1 最坏的情况，对于每一个我都寻求更快的实现。这些与偶数字节相乘的被乘数与乘数的 8 位部分的已知值:
* 11001011 (203₁₀)
* 10101011 (171₁₀)
* 10101101 (173₁₀)
GCC (4.8.1) 将这些计算为 *29*7、*19*9 和 *(43*4+1) - 非常适合三地址机器，而 tinyAVR 不是(相当:大多数都有寄存器对的移动速度是添加速度的两倍)。对于一个两字节的被乘数和乘积，这分别使用 9+2、10+2 和 11+2 加法(和减法)和移动 20、22 和 24 个周期。 Radix-4 Booth 将使用 11+1 加法(在不完全可比较的条件下)和 23 个循环。
由于超出这个问题的原因，我预先计算了 16* 个被乘数(a5:a4，包括移动在内的 7 个周期)；原始和移位的被乘数都可能在以后使用(但对于 MSByte)。并且产品被初始化为以下的被乘数 assembler code片段(我在其中使用了 Booth 风格的重新编码符号:. 用于 NOP、+ 和 -。owing 是一个标签“done 之前的一条指令”，执行单周期修复:

locb:; .-..+.++     ..--.-.- ++..++.-   ++.+.-.-    ..--.-.- 29*7
; WC?!? 11001011                                            s   18
    add p0, p0;15   n   16   a4 15      s   16      n   15  s0  17
    adc p1, p1
    sub p0, a4;13   d   13   z  13      s0  15      s4  12  d   15
    sbc p1, a5
    add p0, p0;11   s4  11   d  12      z   13      z   10  s0  13
    adc p1, p1
    add p0, a0; 9   d   9    aZ 10      a4  12      s0  9   z   11
    adc p1, a1
    add p0, p0; 7   s4  7    d  8       a4  10      d   7   d   10
    adc p1, p1
    add p0, a0; 5   s0  5    d  6       d   8       az  5   aZ  8
    adc p1, a1
    rjmp owing; 3   owi 3    s0 4       d   6       owi 3   d   6
              ;                         aZ  4               aZ  4

(注释从左到右是循环计数(“从到达 done 后退”)，以及使用“标签行”中同一列中的重新编码的进一步代码序列，使用简写 n 表示求反，d 表示双(部分)积，a0/a4/s0/s4用于加减被乘数左移0位或4位，z用于将乘积存入ZL:ZH，aZ/sZ 使用它。)
其他使用宏(以及上述速记)的最坏情况:

loab:; .-.-.-.- +.++.-.-    +.+.+.++    .-.-+.++    +.+.++.-
; WC    10101011
    negP    ;15 set4    ;16 add4    ;15 d   16      a4  16
    sub4    ;12 doubleP ;15 pp2Z    ;13 s4  14      d   14
    pp2Z    ;10 subA    ;13 doubleP ;12 z   12      a0  12
    doubleP ; 9 pp2Z    ;11 doubleP ;10 d   11      d   10
    doubleP ; 7 doubleP ;10 addZ    ; 8 d   9       a4  8
    addZ    ; 5 doubleP ; 8 doubleP ; 6 aZ  7       d   6
    owing   ; 3 addZ    ; 6 addA    ; 4 a0  5       s0  4
            ;   add4    ; 4
loac:; +.+.++.. ++-.++.. .-.-.-..
load: ; .-.-..--    .-.-.-.+    .--.++.+    0.9 1.8 0.8 (avg)
; WC    10101101
    negP    ;15 -1      negP    ;16 a4  a0  a0  17
    sub4    ;12 -16-1   sub4    ;13 d   s4  a0
    pp2Z    ;10 -16-1   doubleP ;11 a0  Z   s4
    sub4    ; 9 -32-1   doubleP ; 9 d   d   d
    doubleP ; 7 -64-2   sub4    ; 7 a4  aZ  d
    addZ    ; 5 -80-3   addA    ; 5 d   d   a0
    owing   ; 3         owing   ; 3 a0  a0  s4

(我不是在任何一次/作为任何一次调用的结果寻找不止一个结果 - 但如果你有办法在不到 23 个周期内获得两个或少于 26 的所有三个，请告诉我。为了证实我对 CSE 的了解，(重新)使用 vlad_tepesch 引入的符号 [rl]sh16 和 add16:

movw        C, x    ; 1
lsh16(C)            ; 3 C=2x
movw        A, C    ; 4
swap        Al      ; 5 
swap        Ah      ; 6
cbr         Ah, 15  ; 7
add         Ah, Al  ; 8
cbr         Al, 15  ; 9
sub         Ah, Al  ;10 A=32x
movw        X, A    ;11
add16(X, C)         ;13 X=34x
movw        B, X    ;14
lsh16(X)            ;16
lsh16(X)            ;18 X=136X
add16(B, X)         ;20 B=170X
add16(B, x)         ;22 B=171X
add16(A, B)         ;24 A=203X
add16(C, B)         ;26 C=173X

‐ 请注意，第一个结果的 22 个周期与原来的 20 个周期相同，外加两个寄存器对移动。除了这些之外的操作顺序是上面标签 loab 之后的第三列/替代项。)
虽然 20 个周期 (15-2(rjmp)+7(*16) 看起来还不错，但这些是最坏的情况。在没有多指令的 AVR CPU 上，
如何将 203、171 和 173 中的每一个乘以 real fast？
(在 done 或 owing 之前移动一个案例，让其他两个更快将缩短关键路径/改善最坏情况循环计数。)

Answer 1

我对 avr-asm 不是很熟悉，但我对 AVR 很了解，所以我试试看

如果您在同一个地方需要这些产品，您可以使用常见的中间结果并尝试添加 2 的倍数。

(a) 203: +128 +64 +8 +2 +1 =  +128 +32 +8 +2 +1   +32
(b) 171:                      +128 +32 +8 +2 +1
(c) 173: +128 +32 +8 +4 +1 =  +128 +32 +8 +2 +1   +2

关键是16位右移和16位加法要有效率。 我不知道我是否监督了什么，但是:

rsh16 (X): 
  LSR Xh
  ROR Xl

和

add16 (Y,X)
  ADD  Yl, Xl
  ADDC Yh, Xh

两个周期。

一对寄存器保存当前的 x*2^n 值 (Xh, Xl)。和其他 3 对(Ah、Ab、Bh、Bl、Ch、Cl)保持结果。

 1. Xh <- x;  Xl <- 0    (X = 256*x)
 2. rsh16(X)             (X = 128*x) 
 3. B = X                (B = 128*x)
 4. rsh16(X); rsh16(X)   (X =  32*x)
 5. add16(B, X)          (B = 128*x + 32*x)
 6. A = X                (A =  32*X)
 7. rsh16(X); rsh16(X)   (X =   8*x)
 8. add16(B, X)          (B = 128*x + 32*x+ 8*x)
 9. rsh16(X); rsh16(X)   (X =   2*x)
10. add16(B, X)          (B = 128*x + 32*x + 8*x + 2*x)
11. C = X                (C =   2*X)
12. CLR  Xh              (clear Xh so we only add the carry below)
    add  Bl, x           
    addc Bh, Xh          (B = 128*x + 32*x + 8*x + 2*x + x) 
13. add16(A, B)          (A = 32*X + B)
14. add16(C, B)          (C =  2*X + B)

如果我是正确的，这将对所有三个乘法加起来达到 32 个周期，并且需要 9 个寄存器(1 个输入，6 个输出，2 个临时寄存器)