6

最初的问题：

我们中的一群人（电子工程专业的学生——英国）最近在我们自己的时代开始着手对 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

我觉得这虽然在代码行方面很短，但对于较大的数字可能需要相对较长的时间来执行。我自己做了一些思考，开始沿着一条路线将一个数字向右移动，另一个向左移动，并在此过程中将左移的数字添加到输出中一定次数以到达最终答案。我做得不太对，但后来在 SO 上偶然发现了这个问题，这让我想到了将输入数字之一表示为：

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
4

2 回答 2

5

是的，但你可能会做得更好。有很多经典的“技巧”可以做到这一点。

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

其次，增加的价值只是被乘数的大小。虽然您需要 16（部分和）最终产品，但您不必进行 16 位添加；您可以进行 8 位加法并传播任何进位。这通常在汇编程序中很容易做到。

为了节省时间，您不想在循环中间调用和添加例程。内联代码以节省调用、返回和优化任何寄存器改组所花费的时间。最后，你只循环了 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 重新编码。

于 2012-05-21T01:37:53.657 回答
4

天啊。我已经有 30 年没有用汇编程序编写乘法代码了。这让人回想起在 6502 汇编器中为 Apple II 编写代码的日子。

你是绝对正确的，第二种方法要快得多。8 次加法和 8 次移动比多达 256 次加法快得多。

但是，我认为你有它落后。

您想从 num1 的 MSB 开始，如果该位为 1，则将 num2 添加到结果中。在除 num1 的 LSB 之外的每一位之后，将结果左移 1。

于 2012-05-21T02:27:26.280 回答