折腾来折腾去

pikipity的blog

汇编实战之乘除法

上一篇《汇编实战之加减法》中介绍了加减法的考虑方法,接下来将会介绍稍微难一点乘除法的思考与实现方法。

一个16位二进制乘以一个8位二进制

算法

乘法还是很简单的,和加减法没有太大的不同,但要注意得数的范围。同样的,先看8051的汇编指令表,其中已经提供了一个用来做两个8位二进制之间的乘法的指令:

MUL AB

这条指令同时对累加器Acc与累乘器B作用,将Acc与B中的数值相乘以后,高8位到B中,低八位到Acc中。那么还是依照加法算法的思考路线,我们就可以这样了:

$$\begin{array}{rcl} c&=&ab\ &=&\left([a_{15}\cdots a_8]\times256+[a_7\cdots a_0]\right)[b_7\cdots b_0]\ [c{15}\cdots c_8]\times 256+[c_7\cdots c_0]&=&\left([a{15}\cdots a_8][b_7\cdots b_0]\right)\times256+\left([a_7\cdots a_0][b_7\cdots b_0]\right) \end{array}$$

在上面的式子中,我用“$*$”标记需要用MUL指令来做乘法的地方,用"$\times$“来标记需要移位的地方。低八位相乘会产生一个16位的二进制数,高八位相乘再移位后会产生一个24位的二进制数,所以至少我们需要3个地址来存放得数。

那么还需不需要考虑低八位乘积的16位数与高八位乘积的24位数相加的进位呢?由于16位二进制最大换算成十进制是65536,而八进制是255,所以得数最大是16777216,也就是说会刚好超出24位,所以得数还需要一个C来存放进位。这样就可以开始编程了。

汇编子程序

;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;Multiplication of unsigned number
;input: 16 bits: 7CH 7DH
;        8 bits:     7FH
;output 24 bits: C 60H 61H 62H
;REG:A(have been protected), B(have been protected), 63H, C
Multi:
    PUSH Acc   ;protect Acc
    PUSH B     ;protect B
    ;Multiply low 8 bits
    MOV A,7DH
    MOV B,A
    MOV A,7FH
    MUL AB
    MOV 62H,A
    MOV A,B
    MOV 61H,A
    ;Multiply high 8 bits
    MOV A,7CH
    MOV B,A
    MOV A,7FH
    MUL AB
    MOV 63H,A
    MOV A,B
    MOV 60H,A
    ;Summation center 8 bits
    CLR C
    MOV A,63H
    ADD A,61H
    MOV 61H,A
    ;Add C and high 8 bits
    MOV A,60H
    ADDC A,#0
    MOV 60H,A
    ;
    POP B      ;back B
    POP Acc    ;back Acc
    RET

一个16位二进制除以一个8位二进制

算法

通过查汇编指令表,我们可以发现,和乘法一样8051也提供了一个8位二进制的除法指令:

DIV AB

还是对Acc与B作用,商到Acc中,余数到B中。但是除法比较特殊,当我们通过与上面乘法类似的算法考虑的时候,会得到下面的式子:

$$\begin{array}{rcl} c&=&\frac{a}{b}\ &=&\left(a\mbox{的高八位与}b\mbox{的商}\times256+a\mbox{的低八位与}b\mbox{的商}\right)\ &&+\left(\frac{a\mbox{的高八位与}b\mbox{的余数}\times256+a\mbox{的低八位与}b\mbox{的余数}}{b}\right) \end{array}$$

最终得到,商的高八位就是$a$的高八位与$b$的商,商的低八位就是$a$的低八位与$b$的商,余数的高八位就是$a$的高八位与$b$的余数,余数的低八位就是$a$的低八位与$b$的余数。但是经过测试,这是不正确的,为什么呢?再次观察我们最后的结论就会发现问题,式子本身没有问题,问题在于进位。尽管$a$的高八位与$b$的余数和$a$的低八位与$b$的余数分别与$b$做除法的时候无法再出现非0商了,但是两者加起来却有可能大于$b$,在与$b$做除法的时候就会出现非0商,如果单纯按照上面的方法做,我们就会少考虑这个由余数产生出来的商的进位。所以上面的算法行不通。

最终我采用的是移位的方法,原理类似与笔算除法。基本流程如下

除法流程图

汇编子程序

;;;;;;;;;;;;;;;;;;;;;;;;;
;Division for unsigned integer
;input: 16 bits: 64H 65H
;        8 bits: 66H
;output: quotient: 67H 68H
;        remainder: 69H
;Reg: A(has been protected), B(has been protected), C, 6AH
division:
    PUSH Acc   ;protect Acc
    PUSH B     ;protect B
    CLR C      ;clear C
    ;clear result
    MOV 67H,#0
    MOV 68H,#0
    MOV 69H,#0
    MOV 70H,#0
    MOV 6BH,#0
    ;division for high 8 bits
    MOV A,66H
    MOV B,A
    MOV A,64H
    DIV AB
    ;quotient go to high quotient of final result
    MOV 67H,A
    ;remiander go to remainder of final result
    MOV A,B
    MOV 69H,A
    ;begin 8 times of loop
    MOV 6AH,#8
division_loop:
    ;rotate 65H left with C
    MOV A,65H
    RLC A
    MOV 65H,A
    ;rotate 69H left with C
    MOV A,69H
    RLC A
    MOV 69H,A    ;result -> rotate 69H and 65H left together with C
    ;69H - 66H
    CLR C
    MOV A,69H
    SUBB A,66H   ;if negative C=1, otherwise C=0. Result in A
    ;
    JC division_quotient_set_0   ;if C=1, go to division_quotient_set_0
division_quotient_set_1:    ;if C=0, go down
    MOV 69H,A     ;sub result go to 69H
    ;most right bit of 68H set 1
    SETB C
    MOV A,68H
    RLC A
    MOV 68H,A
    ;go to dicision
    JMP division_loop_dicision
division_quotient_set_0:    ;if C=1, go down
    ;most right bit of 68H set 0
    CLR C
    MOV A,68H
    RLC A
    MOV 68H,A
division_loop_dicision:
    DEC 6AH
    MOV A,6AH
    CJNE A,#0,division_loop
    ;
    POP B      ;get back B
    POP Acc    ;get back Acc
    RET


Comments