1. General description
2. How it works
3. Optimizations

General description

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:

• Input register name. It also serves as an output register. The register may consist of any number of bits, up to 32. Note that input register should be unsigned.
• Bytes order. The bytes of a register are appended numbers 0, 1, 2,... Because input register may be bigger then one 8-bit register, the order is important.  Big endian order assumes that 0 byte is the most significant byte. On the other hand, little endian keeps the least significant byte in byte 0. You may notice that the little endian notation is easier to use, because each byte has a fixed weight. In most cases the little endian version of code is smaller or equal to the big endian.
• Input register size. Enter number of bits in the input register. Use the least size you need as it may reduce the size of generated code.
• Temporary register name. In some cases, the temporary storage may be used during calculations.
• Constant. It should be entered as a number, arithmetic expressions are not supported. Internally constant is represented as 32 bits of integer and 32 bits of fractional part.
• Maximum error in constant approximation, %. Note that some finite decimal constants are infinite in binary representation, e.g. 0.1 decimal is 0.0001100110011001.. binary. Therefore you will need to specify the required precision.

How it works

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.

Optimizations

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.

Comments

Why 3.578(dec) = 11.1001 0011 1111 0111 1100 ...(bin)?

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.