These chips are based on the RISC-technology, which of course requires a lot of programming knowledge if higher functions should be implemented. Sometimes you need to operate multiplying or division. There exist many ways to do these operations. The question only is about speed and memory allocation.
The algorithm is based on a particularity of binary notation.
Imagine the multiplying of the numbers x10 = 7 and y10 = 5
x2 = 111
y2 = 101, which signifies y10 = 1*22 + 0*21 + 1*20 = 1*1002 + 0*102 + 1*12
the distributive rule gives us:
111 * 101 = 111 * (1*100 + 0*10 + 1*1) = 111*(1*100) + 111*(0*10) + 111*(1*1)
the associative and commutative rules give us:
= (111*100)*1 + (111*10)*0 + (111*1)*1
In binary notation, multiplying by factors of 2 is equivalent to shifting the number:
= 11100*1 + 1110*0 + 111*1
= 11100 + 111 = 100011 = 3510
Thus a simple algorithm may be written for multiplication:
| ' operate the muliplication z = x * y | ||||||||||
| z := 0 | ||||||||||
| while y <> 0 do | ||||||||||
|
Let's now analyze the function MULV8 which may be accessed from within a program by preparing the temporary variables TEMPX and TEMPY, calling the function and finally retrieving the product from the variable RESULT.
For example,
we want our program to compute:
z := x * y
In PIC-assembler this will be:
|
MOVF x,W MOVWF TEMPX MOVF y,W MOVWF TEMPY CALL MULV8 MOVF RESULT,W MOVWF z |
Suppose we have z := 27 * 7 (= 189)
expressed in binary notation: z := b'00011011' * b'00000111'
here is what the computer will do:
to those not too familiar with PIC-assembler, we translate the code :
clrf means 'clear file' (in PIC-language a file is an 8-bit register)
movlw 'fill accumulator with litteral value'
movwf 'transfer value from accumulator to file'
movf 'transfer value from file to itself (F) or the accumulator (W)'
btfsc means 'skip next instruction if the designed bit is clear')
bcf 'bit clear at file' Status,C = CLEAR THE CARRY-FLAG
rrf 'rotate right file and store it to itself or the accumulator'
rlf 'rotate left file and store...'
btfss 'skip next instruction if designed bit is set' Status,Z = ZERO-FLAG SET?
| LINE | TEMPX | TEMPY | RESULT | W | ZERO-BIT | CARRY-BIT |
| CLRF RESULT | 00011011 | 00000111 | 0 | ? | ? | ? |
| MOVF TEMPX,W | 00011011 | 00000111 | 0 | 00011011 | 0 | ? |
| BTFSC TEMPY,0 | 00011011 | 00000111 | 0 | 00011011 | 0 | ? |
| ADDWF RESULT | 00011011 | 00000111 | 00011011 | 00011011 | 0 | 1 |
| BCF STATUS,C | 00011011 | 00000111 | 00011011 | 00011011 | 0 | 0 |
| RRF TEMPY,F | 00011011 | 00000011 | 00011011 | 00011011 | 0 | 1 |
| BCF STATUS,C | 00011011 | 00000011 | 00011011 | 00011011 | 0 | 0 |
| RLF TEMPX,F | 00110110 | 00000011 | 00011011 | 00011011 | 0 | 0 |
| MOVF TEMPY,F | 00110110 | 00000011 | 00011011 | 00011011 | 0 | 0 |
| BTFSS STATUS,Z | 00110110 | 00000011 | 00011011 | 00011011 | 0 | 0 |
| next loop | ||||||
| MOVF TEMPX,W | 00110110 | 00000111 | 00011011 | 00110110 | 0 | 0 |
| BTFSC TEMPY,0 | 00110110 | 00000011 | 00011011 | 00110110 | 0 | 0 |
| ADDWF RESULT | 00110110 | 00000111 | 01010001 | 00110110 | 0 | 1 |
| BCF STATUS,C | 00110110 | 00000111 | 01010001 | 00110110 | 0 | 0 |
| RRF TEMPY,F | 00110110 | 00000001 | 01010001 | 00110110 | 0 | 1 |
| BCF STATUS,C | 00110110 | 00000001 | 01010001 | 00110110 | 0 | 0 |
| RLF TEMPX,F | 01101100 | 00000001 | 01010001 | 00110110 | 0 | 0 |
| MOVF TEMPY,F | 01101100 | 00000001 | 01010001 | 00110110 | 0 | 0 |
| BTFSS STATUS,Z | 01101100 | 00000001 | 01010001 | 00110110 | 0 | 0 |
| next loop | ||||||
| MOVF TEMPX,W | 01101100 | 00000001 | 01010001 | 01101100 | 0 | 0 |
| BTFSC TEMPY,0 | 01101100 | 00000001 | 01010001 | 01101100 | 0 | 0 |
| ADDWF RESULT | 01101100 | 00000001 | 10111101 | 01101100 | 0 | 1 |
| BCF STATUS,C | 01101100 | 00000001 | 10111101 | 01101100 | 0 | 0 |
| RRF TEMPY,F | 01101100 | 00000000 | 10111101 | 01101100 | 0 | 1 |
| BCF STATUS,C | 01101100 | 00000000 | 10111101 | 01101100 | 0 | 0 |
| RLF TEMPX,F | 11011000 | 00000000 | 10111101 | 01101100 | 0 | 0 |
| MOVF TEMPY,F | 11011000 | 00000000 | 10111101 | 01101100 | 1 | 0 |
| RETURN | =189 |
Here the functions for 8 and 16-bits: (Author: Claude Baumann 2002)
| MULV8 CLRF RESULT MULU8LOOP MOVF TEMPX,W BTFSC TEMPY,0 ADDWF RESULT BCF STATUS,C RRF TEMPY,F BCF STATUS,C RLF TEMPX,F MOVF TEMPY,F BTFSS STATUS,Z GOTO MULU8LOOP RETURN |
ADD16 MOVF TEMPX16,W ADDWF RESULT16 BTFSC STATUS,C INCF RESULT16_H MOVF TEMPX16_H,W ADDWF RESULT16_H RETURN MULV16 CLRF RESULT16 CLRF RESULT16_H MULU16LOOP BTFSC TEMPY16,0 CALL ADD16 BCF STATUS,C RRF TEMPY16_H,F RRF TEMPY16,F BCF STATUS,C RLF TEMPX16,F RLF TEMPX16_H,F MOVF TEMPY16,F BTFSS STATUS,Z GOTO MULU16LOOP MOVF TEMPY16_H,F BTFSS STATUS,Z GOTO MULU16LOOP RETURN |
Note that these programs work for signed and unsigned variables.