please dont rip this site

Constant Multiplication/Division Code Generator Help

  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:

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.


See also:


file: /Techref/piclist/codegen/constdivmul_help.htm, 9KB, , updated: 2001/3/17 23:29, local time: 2017/9/23 09:13, owner: NG--944,
TOP NEW HELP FIND: 
54.159.113.182:LOG IN

 ©2017 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?
Please DO link to this page! Digg it! / MAKE! / 

<A HREF="http://piclist.com/techref/piclist/codegen/constdivmul_help.htm"> Constant multiplication/division code generator help</A>

After you find an appropriate page, you are invited to your to this massmind site! (posts will be visible only to you before review) Just type in the box and press the Post button. (HTML welcomed, but not the <A tag: Instead, use the link box to link to another page. A tutorial is available Members can login to post directly, become page editors, and be credited for their posts.


Link? Put it here: 
if you want a response, please enter your email address: 
Attn spammers: All posts are reviewed before being made visible to anyone other than the poster.
Did you find what you needed?

  PICList 2017 contributors:
o List host: MIT, Site host massmind.org, Top posters @20170923 RussellMc, Van Horn, David, James Cameron, Sean Breheny, alan.b.pearce, IVP, Neil, Bob Blick, David C Brown, Denny Esterline,
* Page Editors: James Newton, David Cary, and YOU!
* Roman Black of Black Robotics donates from sales of Linistep stepper controller kits.
* Ashley Roll of Digital Nemesis donates from sales of RCL-1 RS232 to TTL converters.
* Monthly Subscribers: Gregg Rew. on-going support is MOST appreciated!
* Contributors: Richard Seriani, Sr.
 

Welcome to piclist.com!

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

  .