from by Nikolai
Golovchenko
FXD2416U:
CLRF REMB0
CLRF REMB1
MOVLW 24
MOVWF LOOPCOUNT
LOOPU2416
RLF ACCB0, W ;left shift of accb0's msb to reminder
RLF REMB1, F
RLF REMB0, F
MOVF BARGB1, W ;REMB -= BARGB
SUBWF REMB1, F
MOVF BARGB0, W
BTFSS _C
INCFSZ BARGB0,W
SUBWF REMB0, F
BTFSC _C
GOTO UOK46LL ;if no borrow
MOVF BARGB1, W ;REMB += BARGB
ADDWF REMB1, F
MOVF BARGB0, W
BTFSC _C
INCFSZ BARGB0,W
ADDWF REMB0, F
BCF _C
UOK46LL
RLF AARGB2, F
RLF AARGB1, F
RLF AARGB0, F
DECFSZ LOOPCOUNT, F
GOTO LOOPU2416
RETURN
The routine above is actually 24 by 15 bits division.
Below is a 24 by 16 bits division routine:
;Inputs:
; Dividend - AARGB0:AARGB1:AARGB2 (0 - most significant!)
; Divisor - BARGB0:BARGB1
;Temporary:
; Counter - LOOPCOUNT
; Remainder- REMB0:REMB1
;Output:
; Quotient - AARGB0:AARGB1:AARGB2
;
; Size: 28
; Max timing: 4+24*(6+6+4+3+6)-1+3+2=608 cycles (with return)
; Min timing: 4+24*(6+6+5+6)-1+3+2=560 cycles (with return)
;
FXD2416U:
CLRF REMB0
CLRF REMB1
MOVLW 24
MOVWF LOOPCOUNT
LOOPU2416
RLF AARGB2, F ;shift left divider to pass next bit to remainder
RLF AARGB1, F ;and shift in next bit of result
RLF AARGB0, F
RLF REMB1, F ;shift carry into remainder
RLF REMB0, F
RLF LOOPCOUNT, F ;save carry in counter
MOVF BARGB1, W ;substract divisor from remainder
SUBWF REMB1, F
MOVF BARGB0, W
BTFSS _C
INCFSZ BARGB0, W
SUBWF REMB0, W ;keep that byte in W untill we make sure about borrow
SKPNC ;if no borrow
BSF LOOPCOUNT, 0 ;set bit 0 of counter (saved carry)
BTFSC LOOPCOUNT, 0 ;if no borrow
GOTO UOK46LL ;jump
MOVF BARGB1, W ;restore remainder if borrow
ADDWF REMB1, F
MOVF REMB0, W ;read high byte of remainder to W
;to not change it by next instruction
UOK46LL
MOVWF REMB0 ;store high byte of remainder
CLRC ;copy bit 0 to carry
RRF LOOPCOUNT, F ;and restore counter
DECFSZ LOOPCOUNT, f ;decrement counter
GOTO LOOPU2416 ;and repeat loop if not zero
RLF AARGB2, F ;shift in last bit of result
RLF AARGB1, F
RLF AARGB0, F
RETURN
Nikolai Golovchenko shares this code:
Here is a slightly optimized version - 1 instruction shorter, 24 cycles faster!
;Inputs:
; Dividend - AARGB0:AARGB1:AARGB2 (0 - most significant!)
; Divisor - BARGB0:BARGB1
;Temporary:
; Counter - LOOPCOUNT
; Remainder- REMB0:REMB1
;Output:
; Quotient - AARGB0:AARGB1:AARGB2
;
; Size: 27
; Max timing: 4+24*(6+6+4+3+5)-1+3+2=584 cycles (with return)
; Min timing: 4+24*(6+6+5+5)-1+3+2=536 cycles (with return)
;
;25-Sep-2000 Original version
;20-Oct-2001 Made the loop one instruction shorter, comments
; review.
FXD2416U:
CLRF REMB0
CLRF REMB1
MOVLW 24
MOVWF LOOPCOUNT
LOOPU2416
RLF AARGB2, F ;shift dividend left to move next bit to remainder
RLF AARGB1, F ;and shift in next bit of result
RLF AARGB0, F ;
RLF REMB1, F ;shift carry (next dividend bit) into remainder
RLF REMB0, F
RLF LOOPCOUNT, F ;save carry in counter, since remainder
;can be 17 bit long in some cases (e.g.
;0x800000/0xFFFF)
MOVF BARGB1, W ;substract divisor from 16-bit remainder
SUBWF REMB1, F ;
MOVF BARGB0, W ;
BTFSS STATUS, C ;
INCFSZ BARGB0, W ;
SUBWF REMB0, F ;
;here we also need to take into account the 17th bit of remainder, which
;is in LOOPCOUNT.0. If we don't have a borrow after subtracting from lower
;16 bits of remainder, then there is no borrow regardless of 17th bit
;value. But, if we have the borrow, then that will depend on 17th bit
;value. If it is 1, then no final borrow will occur. If it is 0, borrow
;will occur.
SKPNC ;if no borrow after 16 bit subtraction
BSF LOOPCOUNT, 0 ;then no no borrow in result. Overwrite
;LOOPCOUNT.0 with 1 to indicate no
;borrow.
;if borrow did occur, LOOPCOUNT.0 will
;hold the eventual borrow value (0-borrow,
;1-no borrow)
BTFSC LOOPCOUNT, 0 ;if no borrow after 17-bit subtraction
GOTO UOK46LL ;skip remainder restoration.
ADDWF REMB0, F ;restore higher byte of remainder. (w
;contains the value subtracted from it
;previously)
MOVF BARGB1, W ;restore lower byte of remainder
ADDWF REMB1, F ;
UOK46LL
CLRC ;copy bit LOOPCOUNT.0 to carry
RRF LOOPCOUNT, F ;and restore counter
DECFSZ LOOPCOUNT, f ;decrement counter
GOTO LOOPU2416 ;and repeat loop if not zero. carry
;contains next quotient bit (if borrow,
;it is 0, if not, it is 1).
RLF AARGB2, F ;shift in last bit of quotient
RLF AARGB1, F
RLF AARGB0, F
RETURN
Nikolai Golovchenko shares this code:
Well, the routine can be made even simpler! This version is 5 instructions
shorter and 48 cycles faster. Thanks to
Zlatko Petkov for an idea of
removing the extra shifts after the loop. Nikolai Golovchenko. 5-Dec-2004.
FXD2416U:
CLRF REMB0
CLRF REMB1
MOVLW .24
MOVWF LOOPCOUNT
LOOPU2416
RLF AARGB2, W ;shift dividend left to move next bit to remainder
RLF AARGB1, F ;
RLF AARGB0, F ;
RLF REMB1, F ;shift carry (next dividend bit) into remainder
RLF REMB0, F
RLF AARGB2, F ;finish shifting the dividend and save carry in AARGB2.0,
;since remainder can be 17 bit long in some cases
;(e.g. 0x800000/0xFFFF). This bit will also serve
;as the next result bit.
MOVF BARGB1, W ;substract divisor from 16-bit remainder
SUBWF REMB1, F ;
MOVF BARGB0, W ;
BTFSS STATUS, C ;
INCFSZ BARGB0, W ;
SUBWF REMB0, F ;
;here we also need to take into account the 17th bit of remainder, which
;is in AARGB2.0. If we don't have a borrow after subtracting from lower
;16 bits of remainder, then there is no borrow regardless of 17th bit
;value. But, if we have the borrow, then that will depend on 17th bit
;value. If it is 1, then no final borrow will occur. If it is 0, borrow
;will occur. These values match the borrow flag polarity.
SKPNC ;if no borrow after 16 bit subtraction
BSF AARGB2, 0 ;then there is no borrow in result. Overwrite
;AARGB2.0 with 1 to indicate no
;borrow.
;if borrow did occur, AARGB2.0 already
;holds the final borrow value (0-borrow,
;1-no borrow)
BTFSC AARGB2, 0 ;if no borrow after 17-bit subtraction
GOTO UOK46LL ;skip remainder restoration.
ADDWF REMB0, F ;restore higher byte of remainder. (w
;contains the value subtracted from it
;previously)
MOVF BARGB1, W ;restore lower byte of remainder
ADDWF REMB1, F ;
UOK46LL
DECFSZ LOOPCOUNT, f ;decrement counter
GOTO LOOPU2416 ;and repeat the loop if not zero.
RETURN
Fathy Lotfy Samaha of Freelancer Says:
Thanks so much, this is a much simple routine,
but it did not work with me until I changed
the first line to :movlw .24 ,I am using MPASM and MPLAB, it recogonize
the decimal numbers precedded with a dot .
Questions:
Dear Piclist People:
Thanks to all for sharing your knowledge. I was wondering if some of you have had a problem like the one I describe below. Any help will be welcomed!
I⬙m dealing with integer unsigned binary division using a PIC. I implemented 24/24 bit division and everything went ok. But when performing 24/16 bit division, something goes wrong.
The dividend (numerator) is a 24 bit constant, but the divisor (denominator) is a variable number. When this denominator takes a low value (but still 16 bit value), say 10700 i.e., the error in the result is quite a lot, and it becomes bigger as the difference between both operands does too. Is there a solution to this?
Thanks again for your help. Greetings!
Comments:
reference the LAST code segment.
Using a PIC18F4520, please note the code changes.
THANKS YOU all for saving me a lot of work.LOOPU2416 bcf CARRY ; addition of code line rlcf BSR1_Larger24Lo,W ; shift dividend left to move next bit to remainder rlcf BSR1_Larger24Mi,F rlcf BSR1_Larger24Hi,F rlcf BSR1_Remain16Lo,F ; shift carry (next dividend bit) into remainder rlcf BSR1_Remain16Hi,F rlcf BSR1_Larger24Lo,F ; finish shifting the dividend and save carry in ; BSR1_Larger24Lo.0, ; since remainder can be 17 bit long in some cases ; (e.g. 0x800000/0xFFFF). This bit will also serve ; as the next result bit.I apologise for spiling the convention in MY labels, but you can work backwards from the origonal code.
Rick
Sorry, I forgot...
Also, for PIC184520...
replace SKPNC with btfsc CARRY; SKPNC ;if no borrow after 16 bit subtraction btfsc CARRY ; if no borrow after 16 bit subtraction