The program was inspired by James Newton , by numerous and valuable ideas of Scott Dattalo and other PICList members, especially Robert A. LaBudde and Dwayne Reid . Implemented by Nikolai Golovchenko .
The code generator makes possible easy coding of multiplication by a floating point constant in PIC assembly language. The constant may be any positive number. That means that it can be used also for division and right or left shifts.
The form contains the following fields:
First, the decimal floating point constant is converted to fixed point binary form Q32.32 (32 bits of integer and 32 bits of fractional part).
A number in binary form is represented by a sum of powers of two:
31 30 0
N = I * 2 + I * 2 + ... I * 2 +
Q32.32 31 30 0
-1 -2 -32
+ F * 2 + F * 2 + ... F * 2
31 30 0
where
I - value of k-th bit of integer part
k
F - value of k-th bit of fractional part
k
To multiply a variable by a constant the variable should be multiplied by each item of the sum and the results added together. Note that those items, which are equal to zero, can be skipped.
Multiplication by a number, which is a power of two is made simply by shift operation: to multiply a value by two, shift the value left by one bit; to divide a number by two, shift the value right by one bit.
For example, constant 3.578 in binary fractional form:
3.578(dec) = 11.1001 0011 1111 0111 1100 ...(bin)
This is equal to
3.578 = 2 + 1 + 1/2 + 1/16 + 1/128 + 1/256...
v * 3.578 = (v << 1) + v + (v >> 1) + (v >> 4) +
+ (v >> 7) + (v >> 8) + ...
The same expression can be rewritten:
v * 3.578 = = (((((((v >> 1) + v) >> 3) + v) >> 3) + v) >> 1) + v + (v << 1) + ...
Then the fractional part of decomposed constant is truncated. The length of fractional part is determined by the constant error specified in the input form.
Then the code is generated to multiply input value by each item of the decomposed constant and add the results.
Often a constant has a long sequence of set bits. In this case we can optimize multiplication by replacement of long sequences of ones with a difference.
For example, constant multiplier is c= 3.578 and variable is v.
Constant c in binary fractional form:
3.578(dec) = 11.1001 0011 1111 0111 1100 ...(bin)
All long sequences of ones are each replaced with a difference of the bit next to the most significant bit in the sequence and the least significant bit in the sequence. For example, 1111 = 10000 - 1. The difference requires only one substraction instead of four additions.
As a rule of thumb only sequences longer than two bits are economical to replace by a difference.
3.578(dec) = 100.0001 0100 0000 1000 0000..(bin) -
- 000.1000 0000 0001 0000 0100..(bin) =
= 4 - 1/2 + 1/16 + 1/64 - ...(dec).
The algorithm to calculate the product is:
v * 3.578 = v * (4 - 1/2 + 1/16 + 1/64)
As you can see, we can find the product using shifts, addition, and substraction.
Shifts are optimized as well. Shifts by one and two bits use byte rotate instructions. For example,
; ACC = ACC * 4.000000 ; Input: ACC0 (8 bits) ; Output: ACC0 .. ACC1 (10 bits) clrc rlf ACC0, f clrf ACC1 rlf ACC1, f rlf ACC0, f rlf ACC1, f
Shift by 4 and 5 bits use swap instruction. For example,
; ACC = ACC * 32.000000 ; Input: ACC0 (8 bits) ; Output: ACC0 .. ACC1 (13 bits) swapf ACC0, f movf ACC0, w andlw 15 xorwf ACC0, f movwf ACC1 clrc rlf ACC0, f rlf ACC1, f
Shifts by 6 bits use moving bytes by one byte (equivalent to shift by 8 bits) and rotate. For example,
; ACC = ACC * 64.000000 ; Input: ACC0 (8 bits) ; Output: ACC0 .. ACC1 (14 bits) movf ACC0, w movwf ACC1 clrf ACC0 clrc rrf ACC1, f rrf ACC0, f rrf ACC1, f rrf ACC0, f
Shifts by 7 use carry flag for temporary storage and bytes move. For example,
; ACC = ACC * 128.000000 ; Input: ACC0 (8 bits) ; Output: ACC0 .. ACC1 (15 bits) clrc rrf ACC0, w movwf ACC1 clrf ACC0 rrf ACC0, f
As a result the code generator can also be used to quickly and efficiently code shifts by a number of bits in either direction - left or right.
From thread "[PIC]: fixed point binary representation":
Peter Betts says:
The binary number after the decimal point is a always represents a fraction
of 1.
For a 20bit accurate representation of 0.578 just multiply 0.578 * 2^20
(that's 2 raised to the power of 20) = 606076.928 which truncated and
converted to binary gives you 1001 0011 1111 0111 1100.
For a 10bit accurate result 0.578 * 2^10 = 591.872 which truncated in binary
is 1001 0011 11
So hopefully you see that ANY fraction can be represented by a number of
bits (N) in a binary word so long as you (and you code) understand that 2^N
= 1
Fr. Tom McGahee says:
Perhaps the following example will help you understand how
fractions are expressed in binary. I will begin with something
you are hopefully already familiar with, which is straight
binary integer representation. I will then extend the
example to include fractional representation as well.
10000000 = 128
01000000 = 64
00100000 = 32
00010000 = 16
00001000 = 8
00000100 = 4
00000010 = 2
00000001 = 1
.10000000 = 1/2 (128/256) .5
.01000000 = 1/4 (64/256) .25
.00100000 = 1/8 (32/256) .125
.00010000 = 1/16 (16/256) .0625
.00001000 = 1/32 (8/256) .03125
.00000100 = 1/64 (4/256) .015625
.00000010 = 1/128 (2/256) .0078125
.00000001 = 1/256 (1/256) .00390625
Now let's decode 11.10010011
Since 11. = 3 we know the number is 3.something
To determine the "something" fractional part,
consider the fraction to be
(128+16+2+1)/256 = 147/256 = .57421875
maximum error is 1/256 = .00390625
so the truncated 8 bit fraction will have an actual
value somewhere between . 57421875 and .578125
which is an error of .7%
*********
Here is a shortcut way to convert 3.578 to binary:
first write the 3 as 11b
multiply .578*256 and you get 147.968
convert 147 to binary and you get 10010011b
combine the whole number and fraction parts to get
11.10010011b
If you need more digits, convert the .968 remainder
the same way: .988*256=247.808
247 converts to 128+64+32+16+4+2+1 = 11110111
11.10010011 111101111
Need even more digits? Convert the .808 remainder
the same way: .808*256=206.848
206 converts to 128+64+8+4+2 = 11001110
11.10010011 11110111 11001110 etc.
I hope this helps.