Tony posted
;
***********************************************************************
; DIVIDE_48by24 - Routine to divide a 48 bit number with a 24 bit number
; result upto 48 bits !
;
; Formula: Dividend = Dividend/Divisor
;
; Format: Little endian, Ram = msb, Ram+x = lsb ( where
x=bytesize-1)
; Ram used: Dividend 6 bytes ( 48 bits )
; Divisor 3 bytes ( 24 bits )
; Temp 3 bytes
; BitCount 1 byte for loop counting ( and temp. saving of
carry )
;
; Divisor is preserved
; Dividend holds result
; Returns with zero in W if failed ( division with zero )
; Else returns with one in w
;
; Based on pseudo-code from Nikolai Golovchenko [golovchenko@mail.ru]
;
;
DIVIDE_48by24
; Test for zero division
MOVF Divisor,W
IORWF Divisor+1,W
IORWF Divisor+2,W
BTFSC STATUS,Z
RETLW 0x00 ; divisor = zero, not possible to calculate return with zero in w
; prepare used variables
CLRF Temp
CLRF Temp+1
CLRF Temp+2
MOVLW D'48' ; initialize bit counter
MOVWF BitCount
CLRC ; clear carry at entry
DIVIDE_LOOP_48by24
; a) first time carry cleared
; b) every other bit carry contains the result of
; last subtraction ( division ).
; shift in carry as lowest bit
RLF Dividend+5,F
RLF Dividend+4,F
RLF Dividend+3,F
RLF Dividend+2,F
RLF Dividend+1,F
RLF Dividend,F
; shift in highest bit from dividend through carry in temp
RLF Temp+2,F
RLF Temp+1,F
RLF Temp,F
; save carry status in bitcounter temporarily ( possible overflow from temp msb )
BTFSC STATUS,C
BSF BitCount,7 ; set bit ( carry was set, temp>24bit)
; subtract 24 bit divisor from 24 bit temp
MOVF Divisor+2,W ; get lsb
SUBWF Temp+2,F ; subtract
MOVF Divisor+1,W ; get middle byte
SKPC ; if overflow ( from prev. subtraction )
INCFSZ Divisor+1,W ; incresase source
SUBWF Temp+1,F ; and subtract from dest.
MOVF Divisor,W ; get top byte
SKPC ; if overflow ( from prev. subtraction )
INCFSZ Divisor,W ; increase source
SUBWF Temp,F ; and subtract from dest.
; BTFSC STATUS,C ; save carry status again to use for negative check
; BSF BitCount,7 ; yes carry was set.
; if was carry set ( saved in top bit of bitcount ):
; a) Temp overflowed ( i.e. temp > divisor )
; b) Result was positive from subtraction ( i.e. temp > divisor )
; if carry was cleared:
; a) temp < divisor
; BTFSC BitCount,7
; GOTO DIVIDE_SKIP_48by24 ; carry was set, subtraction ok, continue with next bit
;Scott Dattalo says:
;...[the lines above which are commented out can be] reduced to:
skpc
btfsc BitCount,7
goto DIVIDE_SKIP_48by24
; result of subtraction was negative restore temp
MOVF Divisor+2,W ; get LSB of divisor
ADDWF Temp+2,F ; add it to the lsb of temp
MOVF Divisor+1,W ; middle byte
BTFSC STATUS,C ; check carry for overflow from previous addition
INCFSZ Divisor+1,W ; if carry set we add 1 to the source
ADDWF Temp+1,F ; and add it if not zero in that case Product+Multipland=Product
MOVF Divisor,W ; MSB byte
BTFSC STATUS,C ; check carry for overflow from previous addition
INCFSZ Divisor,W
ADDWF Temp,F ; handle overflow
DIVIDE_SKIP_48by24
; CLRC ; clear carry
; carry should now reflect if divison was possible ( i.e. temp > divisor )
; so if it was set, set carry to be shifted in as lowest bit of Dividend
; BTFSC BitCount,7
; BSF STATUS,C ; restore carry
; BCF BitCount,7 ; clear bit used for saving carry
; DECFSZ BitCount,F ; decrement loop counter
; GOTO DIVIDE_LOOP_48by24 ; another run
;Scott Dattalo says:
;...[the lines above which are commented out can be] reduced to:
rlf BitCount,W ;Restore the carry
bcf BitCount,7 ;clear temporary carry
decfsz BitCount,F
goto DIVIDE_LOOP_48by24
; finally shift in the last carry
RLF Dividend+5,F
RLF Dividend+4,F
RLF Dividend+3,F
RLF Dividend+2,F
RLF Dividend+1,F
RLF Dividend,F
NOP
NOP
RETLW 0x01 ; done
Nik commented:
Some ideas to improve it:
- ) Saving carry in counter can be made like at 24by16
to save carry in counter:
rlf BitCount, fto check carry and BitCount.0 after subtraction:
SKPNC ;if no borrow BSF BitCount, 0 ;set bit 0 of counter (saved carry) BTFSC BitCount, 0 ;if no borrow GOTO DIVIDE_SKIP_48by24 ;jumpto restore carry and counter:
CLRC ;copy bit 0 to carry RRF BitCount, F ;and restore counterTotal: 7 instructions instead of 10 (same savings as in Scott's proposal though) It's hard to beat Scott :)
- ) Clearing carry not necessary before loop.
- ) Using slightly different method can improve speed a lot with small code increase. That can be achieved if you don't restore the remainder in the same iteration. You can do just one subtraction/addition in each iteration. Subtract from remainder if remainder is positive or zero and add to remainder if remainder is negative.
For example let's divide 10101100 (172) by 1001 (9) using this nonrestoring method:
C Temp Dividend = ==== ======== 0 0001 0101100x (x - garbage after initial shift) - 1001 ---------------- 0 1000 0101100x -> borrow, first bit of result is 0 next iteration (2nd), 1 0000 101100x0 + 1001 ----------------- 0 1001 101100x0 -> no carry, next bit of result is 0 next iteration (3rd), 1 0011 01100x00 + 1001 ------------------ 0 1100 01100x00 -> no carry, next bit of result is 0It actually works!
Because the remainder can be negative as well as positive in the non-restoring division method, the sign must be kept somewhere. The easiest case is division of 48 by 23 bits. In that case the remainder (Temp) MSbit is free and can be used for sign bit.
But when divisor is 24 bit, Temp should be extended to hold sign. That consumes one more byte of RAM but saves 9 cycles per loop (original was 42 minus 3 optimized vs 30 in the non-restoring routine). That makes about 48*9=432 cycles total savings!
Probably BitCount can be used as additional space for sign storage, but I don't know how to do that as efficiently for speed.
See both versions below.
Nikolai
;**************************************************** ;max time in loop: 26 cycles DIVIDE_48by23 ; Test for zero division MOVF Divisor,W IORWF Divisor+1,W IORWF Divisor+2,W BTFSC STATUS,Z RETLW 0x00 ; divisor = zero, not possible to calculate return with zero in w ; prepare used variables CLRF Temp CLRF Temp+1 CLRF Temp+2 MOVLW D'48' ; initialize bit counter MOVWF BitCount setc DIVIDE_LOOP_48by23 RLF Dividend+5,F RLF Dividend+4,F RLF Dividend+3,F RLF Dividend+2,F RLF Dividend+1,F RLF Dividend,F ; shift in highest bit from dividend through carry in temp RLF Temp+2,F RLF Temp+1,F RLF Temp,F MOVF Divisor+2,W ; get LSB of divisor btfss Dividend+5, 0 goto Div48by23_add ; subtract 23 bit divisor from 24 bit temp SUBWF Temp+2,F ; subtract MOVF Divisor+1,W ; get middle byte SKPC ; if overflow ( from prev. subtraction ) INCFSZ Divisor+1,W ; incresase source SUBWF Temp+1,F ; and subtract from dest. MOVF Divisor,W ; get top byte SKPC ; if overflow ( from prev. subtraction ) INCFSZ Divisor,W ; increase source SUBWF Temp,F ; and subtract from dest. GOTO DIVIDE_SKIP_48by23 ; carry was set, subtraction ok, continue with next bit Div48by23_add ; result of subtraction was negative restore temp ADDWF Temp+2,F ; add it to the lsb of temp MOVF Divisor+1,W ; middle byte BTFSC STATUS,C ; check carry for overflow from previous addition INCFSZ Divisor+1,W ; if carry set we add 1 to the source ADDWF Temp+1,F ; and add it if not zero in that case Product+Multipland=Product MOVF Divisor,W ; MSB byte BTFSC STATUS,C ; check carry for overflow from previous addition INCFSZ Divisor,W ADDWF Temp,F ; handle overflow DIVIDE_SKIP_48by23 DECFSZ BitCount,F ; decrement loop counter GOTO DIVIDE_LOOP_48by23 ; another run ; finally shift in the last carry RLF Dividend+5,F RLF Dividend+4,F RLF Dividend+3,F RLF Dividend+2,F RLF Dividend+1,F RLF Dividend,F RETLW 0x01 ; done ;**************************************************** ;max time in loop: 30 cycles DIVIDE_48by24 ; Test for zero division MOVF Divisor,W IORWF Divisor+1,W IORWF Divisor+2,W BTFSC STATUS,Z RETLW 0x00 ; divisor = zero, not possible to calculate return with zero in w ; prepare used variables CLRF Temp CLRF Temp+1 CLRF Temp+2 clrf Temp2 MOVLW D'48' ; initialize bit counter MOVWF BitCount DIVIDE_LOOP_48by24 RLF Dividend+5,F RLF Dividend+4,F RLF Dividend+3,F RLF Dividend+2,F RLF Dividend+1,F RLF Dividend,F ; shift in highest bit from dividend through carry in temp RLF Temp+2,F RLF Temp+1,F RLF Temp,F rlf Temp2, f MOVF Divisor+2,W ; get LSB of divisor btfsc Temp2, 7 goto Div48by24_add ; subtract 24 bit divisor from 24 bit temp SUBWF Temp+2,F ; subtract MOVF Divisor+1,W ; get middle byte SKPC ; if overflow ( from prev. subtraction ) INCFSZ Divisor+1,W ; incresase source SUBWF Temp+1,F ; and subtract from dest. MOVF Divisor,W ; get top byte SKPC ; if overflow ( from prev. subtraction ) INCFSZ Divisor,W ; increase source SUBWF Temp,F ; and subtract from dest. movlw 1 skpc subwf Temp2, f GOTO DIVIDE_SKIP_48by24 ; carry was set, subtraction ok, continue with next bit Div48by24_add ; result of subtraction was negative restore temp ADDWF Temp+2,F ; add it to the lsb of temp MOVF Divisor+1,W ; middle byte BTFSC STATUS,C ; check carry for overflow from previous addition INCFSZ Divisor+1,W ; if carry set we add 1 to the source ADDWF Temp+1,F ; and add it if not zero in that case Product+Multipland=Product MOVF Divisor,W ; MSB byte BTFSC STATUS,C ; check carry for overflow from previous addition INCFSZ Divisor,W ADDWF Temp,F ; handle overflow movlw 1 skpnc addwf Temp2, f DIVIDE_SKIP_48by24 DECFSZ BitCount,F ; decrement loop counter GOTO DIVIDE_LOOP_48by24 ; another run ; finally shift in the last carry RLF Dividend+5,F RLF Dividend+4,F RLF Dividend+3,F RLF Dividend+2,F RLF Dividend+1,F RLF Dividend,F RETLW 0x01 ; done ;****************************************************
| file: /Techref/microchip/math/div/48by24ng.htm, 13KB, , updated: 2004/7/12 23:50, local time: 2024/12/27 03:45,
owner: NG--944,
18.217.104.36:LOG IN
|
| ©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions? <A HREF="http://linistepper.com/techref/microchip/math/div/48by24ng.htm"> PIC Microcontoller Math Method - 48 by 24 bit division</A> |
| Did you find what you needed? |