Divide 24 bit int by 16 bit int to 24 bit int
from by Nikolai Golovchenko
from by Nikolai Golovchenko
| CODE |
| 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 Nikolai Golovchenko says: 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 |
Here is a slightly optimized version - 1 instruction shorter, 24 cycles faster!
| CODE |
| ;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 |
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.
| CODE |
| 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 |
| QUOTE |
| 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 . |