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.

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.

file: /Techref/piclist/codegen/constdivmul_help.htm, 9KB, , updated: 2001/3/17 23:29, local time: 2024/6/23 00:20, owner: NG--944, |

©2024 These pages are served without commercial sponsorship. (No popup ads, etc...).Bandwidth abuse increases hosting cost forcing sponsorship or shutdown. This server aggressively defends against automated copying for any reason including offline viewing, duplication, etc... Please respect this requirement and DO NOT RIP THIS SITE. Questions?<A HREF="http://techref.massmind.org/Techref/piclist/codegen/constdivmul_help.htm"> Constant multiplication/division code generator help</A> |

Did you find what you needed? |

## Welcome to massmind.org! |

## Welcome to techref.massmind.org! |

.