Difference between revisions of "PIC: Multiplication"
From ScienceZero
(New page: Low-end microcontrollers from Microchip do not have a multiplication instruction so any multiplication needs to be done using software or external hardware. This is a collection of 8 by 8 ...) |
|||
| (4 intermediate revisions by 2 users not shown) | |||
| Line 1: | Line 1: | ||
Low-end microcontrollers from Microchip do not have a multiplication instruction so any multiplication needs to be done using software or external hardware. This is a collection of 8 by 8 bit multiplication methods that are very efficient. | Low-end microcontrollers from Microchip do not have a multiplication instruction so any multiplication needs to be done using software or external hardware. This is a collection of 8 by 8 bit multiplication methods that are very efficient. | ||
| − | General (13-123 cycles, 18 instructions) | + | |
| + | ==General (13-123 cycles, 18 instructions)== | ||
A simple starting point for experimentation and is easily extendible to any word lenght. It is quite fast if a large portion of the numbers are very small. | A simple starting point for experimentation and is easily extendible to any word lenght. It is quite fast if a large portion of the numbers are very small. | ||
| − | + | ;General - 13-123 cycles, 18 instructions | |
| − | + | ;Remove "clrf tmpH" for 16 by 8 multiplication | |
| + | |||
| + | mul8x8g clrf prodL | ||
| + | clrf prodH | ||
| + | clrf tmpH | ||
| + | clrc | ||
| + | mulgl rrf mulplr | ||
| + | skpc | ||
| + | goto noadd | ||
| + | movfw mulcnd | ||
| + | addwf prodL | ||
| + | skpnc | ||
| + | incf prodH | ||
| + | movfw tmpH | ||
| + | addwf prodH | ||
| + | noadd rlf mulcnd | ||
| + | rlf tmpH | ||
| + | tstf mulplr | ||
| + | skpz | ||
| + | goto mul | ||
| − | |||
| − | |||
| − | + | ==Small (67 cycles constant, 11 instructions)== | |
| − | + | This one is for saving precious code memory and still have good speed. The principle of this method comes from the Microchip application note 526 but has been optimised for minimum size and maximum speed. | |
| − | + | ;Small - 67 cycles constant, 11 instructions | |
| − | + | ;Same principle as application note 526 | |
| + | ;Optimized for minimal size by Bjørn Bæverfjord | ||
| + | |||
| + | mul8x8s clrf prodH | ||
| + | movlw .128 | ||
| + | movwf prodL | ||
| + | movfw mulcnd | ||
| + | mulsl rrf mulplr | ||
| + | skpnc | ||
| + | addwf prodH | ||
| + | rrf prodH | ||
| + | rrf prodL | ||
| + | skpc | ||
| + | goto mulsl | ||
| + | return | ||
| − | |||
| − | + | ==Medium (36 cycles constant, 36 instructions)== | |
| − | + | Directly from Microchip application note 526. | |
| − | + | ;Medium - 36 cycles constant, 36 instructions | |
| − | + | ;From Microchip application note 526 | |
| − | + | ;PIC16C5X / PIC16CXXX Math Utility Routines | |
| − | + | ||
| − | + | mul8x8m clrf prodH | |
| − | + | clrf prodL | |
| − | + | movfw mulcnd | |
| − | + | clrc | |
| − | + | btfsc mulplr,0 | |
| − | + | addwf prodH | |
| − | + | rrf prodH | |
| − | + | rrf prodL | |
| − | + | btfsc mulplr,1 | |
| − | + | addwf prodH | |
| − | + | rrf prodH | |
| − | + | rrf prodL | |
| − | + | btfsc mulplr,2 | |
| − | + | addwf prodH | |
| + | rrf prodH | ||
| + | rrf prodL | ||
| + | btfsc mulplr,3 | ||
| + | addwf prodH | ||
| + | rrf prodH | ||
| + | rrf prodL | ||
| + | btfsc mulplr,4 | ||
| + | addwf prodH | ||
| + | rrf prodH | ||
| + | rrf prodL | ||
| + | btfsc mulplr,5 | ||
| + | addwf prodH | ||
| + | rrf prodH | ||
| + | rrf prodL | ||
| + | btfsc mulplr,6 | ||
| + | addwf prodH | ||
| + | rrf prodH | ||
| + | rrf prodL | ||
| + | btfsc mulplr,7 | ||
| + | addwf prodH | ||
| + | rrf prodH | ||
| + | rrf prodL | ||
| + | return | ||
| − | + | ==Fast (22-36 cycles, 51 instructions)== | |
| − | + | The fastest software solution I could find. Lifted from the PIClist. | |
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | + | ||
| − | mulf0 rrf prodH | + | ;Fast - 22-36 cycles, 51 instructions |
| − | + | ;By Scott Dattalo from the PICList | |
| − | + | ||
| − | + | mul8x8f movfw prodH | |
| − | mulf1 rrf prodH | + | clrc |
| − | + | clrf prodL | |
| − | + | btfsc mulplr,0 | |
| − | + | goto mulf0 | |
| − | mulf2 rrf prodH,f | + | btfsc mulplr,1 |
| − | + | goto mulf1 | |
| − | + | btfsc mulplr,2 | |
| − | + | goto mulf2 | |
| − | mulf3 rrf prodH,f | + | btfsc mulplr,3 |
| − | + | goto mulf3 | |
| − | + | btfsc mulplr,4 | |
| − | + | goto mulf4 | |
| − | mulf4 rrf prodH,f | + | btfsc mulplr,5 |
| − | + | goto mulf5 | |
| − | + | btfsc mulplr,6 | |
| − | + | goto mulf6 | |
| − | mulf5 rrf prodH,f | + | btfsc mulplr,7 |
| − | + | goto mulf7 | |
| − | + | clrf prodH ;Bugfix by Dmitry Kiryashov | |
| − | + | return | |
| − | mulf6 rrf prodH,f | + | |
| − | + | mulf0 rrf prodH | |
| − | + | rrf prodL | |
| − | + | btfsc mulplr,1 | |
| − | mulf7 rrf prodH,f | + | addwf prodH,w |
| − | + | mulf1 rrf prodH | |
| − | + | rrf prodL | |
| + | btfsc mulplr,2 | ||
| + | addwf prodH,w | ||
| + | mulf2 rrf prodH,f | ||
| + | rrf prodL | ||
| + | btfsc mulplr,3 | ||
| + | addwf prodH,w | ||
| + | mulf3 rrf prodH,f | ||
| + | rrf prodL | ||
| + | btfsc mulplr,4 | ||
| + | addwf prodH,w | ||
| + | mulf4 rrf prodH,f | ||
| + | rrf prodL | ||
| + | btfsc mulplr,5 | ||
| + | addwf prodH,w | ||
| + | mulf5 rrf prodH,f | ||
| + | rrf prodL | ||
| + | btfsc mulplr,6 | ||
| + | addwf prodH,w | ||
| + | mulf6 rrf prodH,f | ||
| + | rrf prodL | ||
| + | btfsc mulplr,7 | ||
| + | addwf prodH,w | ||
| + | mulf7 rrf prodH,f | ||
| + | rrf prodL | ||
| + | return | ||
| − | - | + | ==Hardware (2-12 cycles)== |
| + | [[image:Picmul8x8.png|right|thumb|16F84A hardware table lookup]] | ||
| + | How to read a 128kB look up table in EPROM using only 10 I/O pins and still have good performance. A larger PIC with more I/O pins will give higher performance since the data bus can be split into separate address/data busses and made unidirectional. | ||
| − | + | The value of R1 must be selected to give a pulse from the EOR gate that is shorter than the instruction cycle of the PIC and longer than the minimum requirements for the specific latch used. | |
[[Category:Computing]] | [[Category:Computing]] | ||
Latest revision as of 19:09, 5 January 2009
Low-end microcontrollers from Microchip do not have a multiplication instruction so any multiplication needs to be done using software or external hardware. This is a collection of 8 by 8 bit multiplication methods that are very efficient.
Contents
General (13-123 cycles, 18 instructions)
A simple starting point for experimentation and is easily extendible to any word lenght. It is quite fast if a large portion of the numbers are very small.
;General - 13-123 cycles, 18 instructions
;Remove "clrf tmpH" for 16 by 8 multiplication
mul8x8g clrf prodL
clrf prodH
clrf tmpH
clrc
mulgl rrf mulplr
skpc
goto noadd
movfw mulcnd
addwf prodL
skpnc
incf prodH
movfw tmpH
addwf prodH
noadd rlf mulcnd
rlf tmpH
tstf mulplr
skpz
goto mul
Small (67 cycles constant, 11 instructions)
This one is for saving precious code memory and still have good speed. The principle of this method comes from the Microchip application note 526 but has been optimised for minimum size and maximum speed.
;Small - 67 cycles constant, 11 instructions
;Same principle as application note 526
;Optimized for minimal size by Bjørn Bæverfjord
mul8x8s clrf prodH
movlw .128
movwf prodL
movfw mulcnd
mulsl rrf mulplr
skpnc
addwf prodH
rrf prodH
rrf prodL
skpc
goto mulsl
return
Medium (36 cycles constant, 36 instructions)
Directly from Microchip application note 526.
;Medium - 36 cycles constant, 36 instructions
;From Microchip application note 526
;PIC16C5X / PIC16CXXX Math Utility Routines
mul8x8m clrf prodH
clrf prodL
movfw mulcnd
clrc
btfsc mulplr,0
addwf prodH
rrf prodH
rrf prodL
btfsc mulplr,1
addwf prodH
rrf prodH
rrf prodL
btfsc mulplr,2
addwf prodH
rrf prodH
rrf prodL
btfsc mulplr,3
addwf prodH
rrf prodH
rrf prodL
btfsc mulplr,4
addwf prodH
rrf prodH
rrf prodL
btfsc mulplr,5
addwf prodH
rrf prodH
rrf prodL
btfsc mulplr,6
addwf prodH
rrf prodH
rrf prodL
btfsc mulplr,7
addwf prodH
rrf prodH
rrf prodL
return
Fast (22-36 cycles, 51 instructions)
The fastest software solution I could find. Lifted from the PIClist.
;Fast - 22-36 cycles, 51 instructions
;By Scott Dattalo from the PICList
mul8x8f movfw prodH
clrc
clrf prodL
btfsc mulplr,0
goto mulf0
btfsc mulplr,1
goto mulf1
btfsc mulplr,2
goto mulf2
btfsc mulplr,3
goto mulf3
btfsc mulplr,4
goto mulf4
btfsc mulplr,5
goto mulf5
btfsc mulplr,6
goto mulf6
btfsc mulplr,7
goto mulf7
clrf prodH ;Bugfix by Dmitry Kiryashov
return
mulf0 rrf prodH
rrf prodL
btfsc mulplr,1
addwf prodH,w
mulf1 rrf prodH
rrf prodL
btfsc mulplr,2
addwf prodH,w
mulf2 rrf prodH,f
rrf prodL
btfsc mulplr,3
addwf prodH,w
mulf3 rrf prodH,f
rrf prodL
btfsc mulplr,4
addwf prodH,w
mulf4 rrf prodH,f
rrf prodL
btfsc mulplr,5
addwf prodH,w
mulf5 rrf prodH,f
rrf prodL
btfsc mulplr,6
addwf prodH,w
mulf6 rrf prodH,f
rrf prodL
btfsc mulplr,7
addwf prodH,w
mulf7 rrf prodH,f
rrf prodL
return
Hardware (2-12 cycles)
How to read a 128kB look up table in EPROM using only 10 I/O pins and still have good performance. A larger PIC with more I/O pins will give higher performance since the data bus can be split into separate address/data busses and made unidirectional.
The value of R1 must be selected to give a pulse from the EOR gate that is shorter than the instruction cycle of the PIC and longer than the minimum requirements for the specific latch used.
