;------------------------------------------------------------------
; Tutorial Mult 24 x 24 out 48 (max)
; Fred Maher 3rd Nov 2002
;------------------------------------------------------------------
LIST P=16F628 ; 16F628 Runs at 20 MHz
INCLUDE "p16F628.inc"
__CONFIG _CP_OFF & _WDT_OFF & _HS_OSC & _PWRTE_ON & _LVP_OFF & _BODEN_OFF
ERRORLEVEL -224 ; suppress annoying message because of tris
ERRORLEVEL -302 ; suppress message because of page change
CBLOCK 20H
top1
top2
top3
top4
top5
top6
bot1
bot2
bot3
res1
res2
res3
res4
res5
res6
count
temp
c1
c2
ENDC
; Top and bottom registers are not symetrical. The bottom registers will never need to
; handle more than 24 bits. The top registers can, when the numbers are near the maximum,
; have to handle 48 bits due to left shifting. Now we can reuse registers but it makes
; following these "tutor" multiply routines harder to follow.
;There is no ORG, ISR, as this is a sub routine of a main program. However we
;want it to behave like a program to debug and emulate it running with real number inputs.
;When it is all working we remove ;the header and place the variables with the rest of
;the variables of the existing main ;program code.
;So we can start by putting values into the top and bottom, values that will not cause
;overflow in the result.
;Example numbers :top 00FFFF bot 000024 txb = 23FFDC(inside 24 bit limit)decimal = 2,359,260
Testnums:
movlw 0x0B
movwf top1
movlw 0x00
movwf top2
movlw 0x00
movwf top3
movlw 0x00
movwf top4
movlw 0x00
movwf top5
movlw 0x00
movwf top6
movlw 0xBA
movwf bot1
movlw 0xDC
movwf bot2
movlw 0xFE
movwf bot3
clrf res1
clrf res2
clrf res3
clrf res4
clrf res5
clrf res6
; In example top x bot = B044 F100
; we will use top as multiplicand and bot as the multiplier Note:- the smaller number is as we
; discussed in the multiplier, bottom.
; A word about the code we are going to write. The shifts and the checks produce a lot of trees
;making it easy to lose sight of the main actions. These are.
; THE MULTIPLY SEQUENCE
;----------------------
;Step 1. Use bot bit 0 to decide if we add tops to reses or to skip directly to 4.
;
;Step 2. Add the rotated left 3top to 3res if bot bit not 0, else skip add.
; Please note, the First Time as there is no shifting,
; add directly all the top bits to result. If the first ( rightmost digit of the
;bot.. multiplier ) had been zero and not four then we skip the add and move on
;to the next action. ( bot bit tells us when to skip the add)
;Step 2 actions:. The addition of res and top
; top1 add to res1, carry flag? yes, add 1 to res2 , clear carry flag
; top2 add to res2, carry flag? yes, add 1 to res3 , clear carry flag
; top3 add to res3 , carry flag? yes,
;
;Step 3. Rotate left the three top registers and check overflows in this sequence...
; top1 rotate left, carry flag? yes, add 1 to top2 , clear carry flag
; top2 rotate left, carry flag? yes, add 1 to top3 , clear carry flag
; top3 rotate left, carry flag? yes,
; not this time ---> "add 1 to top4, clear carry flag"<--
;
;Step 4. Bot,bit0( value 1 or 0 )decides if we add or don't add so we need to
; right shift the three bots or read a bit in the corresponding register
; using the loop counter count. This counter would loop from 1 to 24 and
;needs checks ;to move from bot1 reg to bot2 reg then to bot3 reg.
;This first attempt will use the same actions as 3. and 4. So we have after 1st read
;bot1 rotate right, Carry flag? yes , clear carry flag
;bot2 rotate right, Carry flag? yes add b'1000000' = hex80 to bot1 , clear carry flag
;bot3 rotate right, Carry flag? yes add b'1000000' = hex80 to bot2 , clear carry flag
; These are the four steps explained in words....
; The execution time of the multiplication can be quickened considerably if
; we know when the multiplier has finished.
; e.g. look at bot3, bot2, bot1 00 00 24 = 00000000 00000000 0010 0100
; now after five shifts right what remains are zeros.
; So calculation finished at count 6, in 243 cycles; yet we continue
; until we reach count 24, which takes 836 cycles
; What we need to add is a top bottom swap, and detect bot_first_1 for count needed
; routine, to optimize the 24x24 multiply a little more.
;-----------------------------------------------------------------------
; Mult24 is the main mult routine start point
;------------------------------------------------------------------------
Mult24: ;
bcf STATUS,DC
call Regcomp ; Puts smaller number into multiplier and finds count minimum.
nop
incf count,f
clrf res1 ; may have been used for storage in swap
clrf res2
clrf res3
call X24 ; main 24 x 24 mult
Mult24end: ; here back to principal program
goto Mult24end ; dummy loop for testing
; return ; back to main program
;--------------------------------------------------------------------------
; End of multiply 24 x 24 ; out 48, routine
;--------------------------------------------------------------------------
Regcomp: ; compare top and bot regs 3 2 1 to decide if we need to swap.
bcf STATUS,2
bcf STATUS,1
bcf STATUS,0
; These blocks test for:- "0 "... "="... ">" ... using STATUS flags
Test33:
movf bot3,w
subwf top3,w
btfsc STATUS,C ;
goto $+ 3 ; top is equal or bigger
call Swap
goto Leftbit ; find leftmost 1 for count.
; end case top>bot
; Think carefully about this bit. We get here because bot is
; equal or less than top. So we test top for zero, then if zero
; bot is also zero because we have no negative numbers
; (e.g. bot can't be -7)
; if STATUS not zero bot is less than top, then find
; leftmost "1" for count.
clrw ; test top=0 (if top=0 then bot=0 (can't be minus))
xorwf top3,w
btfsc STATUS,Z
goto Test22 ; both zero, continue test with top2,bot2
goto Leftbit
Test22:
movf bot2,w
subwf top2,w
btfsc STATUS,C ;
goto $+ 3 ; top is equal or bigger
call Swap
goto Leftbit ; find leftmost 1 for count.
; end case top>bot
clrw ; test top=0 (if top=0 then bot=0 (can't be minus))
xorwf top2,w
btfsc STATUS,Z
goto Test11 ; both zero, continue test with top2,bot2
goto Leftbit
Test11:
movf bot1,w
subwf top1,w
btfsc STATUS,C ;
goto $+ 3 ; top is equal or bigger
call Swap
goto Leftbit ; find leftmost 1 for count.
; end case top>bot
clrw ; test top=0 (if top=0 then bot=0 (can't be minus))
xorwf top1,w
btfsc STATUS,Z
goto Test11 ; both zero, continue test with top2,bot2
movf bot1,w ;put bot in temp
movwf temp
movlw d'08' ; bot is smaller so set count to 24
movwf count ; do Leftbit
goto Leftbit
Swap:
movf top3,w
movwf res3
movf bot3,w
movwf top3
movf res3,w
movwf bot3
movf top2,w
movwf res2
movf bot2,w
movwf top2
movf res2,w
movwf bot2
movf top1,w
movwf res1
movf bot1,w
movwf top1
movf res1,w
movwf bot1
return
Leftbit:
;Now find in bot3,2,1 that which is not zero, find leftmost ONE
; We leave the routine with count holding the minimum necessary number
;for the multiplier adds and with multiplier as bot, the smaller number
clrw
xorwf bot3,w
btfsc STATUS, Z
goto $+6
movf bot3,w
movwf temp
movlw d'24'
movwf count
goto Oneloop
clrw
xorwf bot2,w
btfsc STATUS, Z
goto $+6
movf bot2,w
movwf temp
movlw d'16'
movwf count
goto Oneloop
clrw
xorwf bot1,w
btfsc STATUS, Z
goto $+4
movf bot1,w
movwf temp
movlw d'08'
movwf count
goto Oneloop
Oneloop: ; We move through the 8 bits of temp from 8 to 1
btfsc temp,7
return
decf count,f
rlf temp,f
goto Oneloop
return ; to main mult
;----------------------------------------------------------------
; End of the compare / count routine
;----------------------------------------------------------------
X24: ; mult loop proper starts here with entered values
Step1: ; To add or not to add? that is the question.
btfss bot1,0
goto Step3 ; 0... don't add top to res
goto Step2 ; 1... add top to res
Step2: ; Adding top to res
movfw top1
addwf res1,f
movfw top2
skpnc
incfsz top2,w
addwf res2,f
movfw top3
skpnc
incfsz top3,w
addwf res3,f
movfw top4
skpnc
incfsz top4,w
addwf res4,f
movfw top5
skpnc
incfsz top5,w
addwf res5,f
movfw top6
skpnc
incfsz top6,w
addwf res6,f
Step3: ; Left shifting top
; This looks the same as an add but it is different, when we shift
; we never sum, but rather drop the carried 1 into a space vacated
; So we start with top6, check C,; top5 check C,.....; top1 check C
bcf STATUS,C
rlf top6,f
btfsc STATUS,C
nop ;incf top4,f
bcf STATUS,C
rlf top5,f
btfsc STATUS,C
incf top6,f
bcf STATUS,C
rlf top4,f
btfsc STATUS,C
incf top5,f
bcf STATUS,C
rlf top3,f
btfsc STATUS,C
incf top4,f
bcf STATUS,C
rlf top2,f
btfsc STATUS,C
incf top3,f
bcf STATUS,C
rlf top1,f
btfsc STATUS,C
incf top2,f
bcf STATUS,C
Stepend:
nop
Step4: ;Right shifting bottom and terminate loop for count = MAX, here 24.
decf count,f ; we start with count =24 OR speeded up count
clrw
xorwf count,w
btfsc STATUS,Z
RETURN ; count finished
; count not finished, continue Step4
rrf bot1,f
bcf STATUS,C
rrf bot2,f
btfss STATUS,C
goto $ + 4 ; there was no carry, jump forward 4
movlw 0x80
addwf bot1,f
bcf STATUS,C
rrf bot3,f
btfss STATUS,C
goto $ + 4 ; there was no carry, jump forward 4
movlw 0x80
addwf bot2,f
bcf STATUS,C
goto Step1
;---------------------------------------------------------------------
; End of reg multiplication
;---------------------------------------------------------------------
end ;not used when this is a subroutine
;------------------------------------------------------------------
; End Mult 24 x 24
;------------------------------------------------------------------