哪个是仅使用位移和加法将两个字节相乘的更好方法？

Question

初步问题:

最近,我们一群(电子工程专业学生 - 英国)在PIC16F84A微控制器编程的基础上开始掌握这一点.需要将两个8位数相乘,每个都没有已知的最小值/最大值.一位同学提出了以下想法.

multiply_numbers:
; Takes numbers in Num1 and Num2, and returns product in OutH:OutL
    clrf    OutH            ; clear all non-input variables
    clrf    OutL
mult_loop
    bcf     STATUS,c        ; clear carry bit
    movfw   Num2
    addwf   OutL            ; add Num2 to OutL
    btfsc   STATUS,c        ; check carry bit
    incf    OutH            ; if set, increment OutH
    decfsz  Num1            ; decrement Num1
    goto    mult_loop       ; if Num1 is not zero, repeat loop
    return                  ; else return

我觉得这虽然在代码行方面很短,但执行大数字可能需要相对较长的时间.我自己做了一些思考,开始沿着向右移动一个数字,向左移动另一个数字的路线,并沿着路径向输出添加左移数字一定次数到达输出最终答案.我做得不对,但后来偶然发现了这个问题,这让我想到了一个输入数字:

N = a_0 + a_1*2 + a_2*2 ^ 2 + a_3*2 ^ 3 + ... + a_7*2 ^ 7

从那个起点开始,我想出了这种方法,用于将两个8位数相乘得到一个16位输出(存储在两个8位寄存器中).

multiply_numbers:
; Takes numbers in Num1 and Num2L, and returns product in OutH:OutL
    clrf    Num2H           ; clear all non-input variables
    clrf    OutL
    clrf    OutH
mult_loop
    btfsc   Num1,0          ; test LSB of Num1
    call    add_num16       ; if set, add Num2H:Num2L to OutH:OutL
    call    shift_left      ; shift Num2H:Num2L left (multiply by 2)
    rrf     Num1,f          ; shift Num1 right
    clrw                    ; clear working register (0x00)
    bcf     STATUS,z        ; clear zero bit (3) of the STATUS register
    addwf   Num1,w          ; add 0x00 to Num1
    btfss   STATUS,z        ; if Num1 is zero, then exit loop
    goto    mult_loop       ; else, continue with another iteration
    return
add_num16
    movfw   Num2H
    addwf   OutH,f          ; add Num2H to OutH
    bcf     STATUS,c        ; clear carry bit (0) of the STATUS register
    movfw   Num2L
    addwf   OutL,f          ; add Num2L to OutL
    btfsc   STATUS,c        ; check carry bit
    incf    OutH,f          ; increment OutH if set (OutL overflowed)
    return
shift_left
    bcf     STATUS,c        ; clear carry bit
    rlf     Num2L,f         ; rotate Num2L left (carry -> LSB, MSB -> carry)
    rlf     Num2H,f         ; rotate Num2H left, using carry bit from Num2L
    return

我认为第二个例子在大多数情况下更快,仅仅是因为循环最多只重复8次而不是最多256次.

我假设他们的相对速度/效率是否正确？并且第二个代码块实际上是否按照我的意图运行(它是否存在我错过的任何潜在问题)？最后,使用尚未采用的技术可以进一步优化这种乘法吗？

先感谢您.

PS所有变量/寄存器都已使用自己的地址正确定义.广泛的代码注释是因为我们正在尝试编译一组我们可以在将来引用的例程,并且仍然可以一眼就知道发生了什么以及为什么.

PPS这个问题与个人/爱好对编写这张照片的兴趣有关,与任何当前的课程作业等无关.只是为了消除你可能有的任何怀疑!

---

微控制器:PIC16F84A
开发环境:MPLABX IDE v1.10
编译器:mpasm(v5.43)

---

编辑#1:

• 而不是测试Num1的LSB并将左移Num2H:Num2L添加到OutH:OutL,测试Num1的MSB并将Num2添加到左移OutH:OutL.
• 使'shift_left'内联而不是被调用的子函数.
• 展开'mult_loop'以优化第8次迭代.

方法2改进:

multiply_numbers:
; Takes numbers in Num1 and Num2, and returns product in OutH:OutL
    clrf    OutL            ; clear all non-input variables
    clrf    OutH
; 1st iteration
    btfsc   Num1,7          ; test MSB of Num1
    call    add_num8        ; if set, add Num2 to OutH:OutL
    bcf     STATUS,c        ; clear carry bit
    rlf     OutL,f          ; rotate OutL left (carry -> LSB, MSB -> carry)
    rlf     OutH,f          ; rotate OutH left, using carry bit from OutL
    rlf     Num1,f          ; shift Num1 left
; 2nd iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 3rd iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 4th iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 5th iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 6th iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 7th iteration
    btfsc   Num1,7
    call    add_num8
    bcf     STATUS,c
    rlf     OutL,f
    rlf     OutH,f
    rlf     Num1,f
; 8th iteration
    btfss   Num1,7          ; test MSB of Num1
    return                  ; if not set, then return. else...
add_num8
    bcf     STATUS,c        ; clear carry bit (0) of the STATUS register
    movfw   Num2
    addwf   OutL,f          ; add Num2L to OutL
    btfsc   STATUS,c        ; check carry bit
    incf    OutH,f          ; increment OutH if set (OutL overflowed)
    return

Answer 1

是的,但你可能会做得更好.有一堆经典的"技巧"来做到这一点.

首先,知道乘数可以被解释为2的幂之和,当被乘数位非零时,你巧妙地将被乘数加到乘数上.

其次,增加值只是被乘数的大小.虽然您需要16(部分和)最终产品,但您不必进行16位添加; 你可以做8位添加并传播任何进位.这通常很容易在汇编程序中完成.

为了节省时间,您不希望在循环中调用和ADD例程.内联代码以节省调用,返回和优化任何寄存器混洗所花费的时间.最后,你只循环8次; 它值得展开这样一个循环8次,以避免计数器的开销,并降低由于不得不摆弄计数器造成的"套准压力",给你更多的优化自由.

注意我对PIC控制器一无所知,实际上我不知道它的指令集.但我所说的与任何实现8位乘法的人相关.(16,32和64位乘法有相同的技巧).所以可以抽象地编写以下代码:

 mul16: // computes M1 * M2 --> P where M1 and M2 are 8 bit values, P is 16 bits
        // P is represent by Plow and Phigh 8 bit values.
        // reset the (partial) product
        Plow=0; Phigh=0; // all 16 bits 
       // First iteration:          
       if msb(M1)==1 then { Plow+=M2; if carry then Phigh++; /* propagate carry */ }
       shift M1 left bit;
       shift (Phigh,Plow) left one bit
       // Second iteration
            <same as first>
       <3rd ..7th iteration, same as first>
       // 8th iteration
        if msb(M1)==1 then { Plow+=M2; if carry then Phigh++ }
       // dont bother: shift M1 left bit;
       // dont bother: shift (Phigh,Plow) left one bit   
       <done>

您可能会巧妙地注意到,如果"msb(M1)......"和"将M1向左移一位",通常可以使用汇编语言"向左移位"指令轻松实现,或者在绝望中为自身添加值: - }类似地,"if carry ... add one"通常用"add carry"指令实现.

我留给你为PIC重新编码.