recent work on fixed-point in avr-gcc

Go To Last Post
32 posts / 0 new
Author
Message
#1
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I found out that gcc has had support for fixed-point since 2007, however for most targets it is implemented completely in c library calls. I decided I would try to get gcc to emit reasonable assembly for avr.

When configuring gcc I used the following line:

./configure --target=avr --enable-languages=c --disable-libssp --enable-fixed-point

This will break without my patch. You only need the dwarf and gdb patches if you want to debug.

Currently there are a bunch of types with the following formats:

short _Fract       s.7   unsigned short _Fract       .8
_Fract             s.15  unsigned _Fract             .16
long _Fract        s.31  unsigned long _Fract        .32
long long _Fract   s.64  unsigned long long _Fract   .64
short _Accum      s7.8   unsigned short _Accum      8.8
_Accum           s15.16  unsigned _Accum           16.16
long _Accum      s31.32  unsigned long _Accum      32.32
long long _Accum s63.64  unsigned long long _Accum 64.64

Initially everything basically worked, but emitted a lot of large slow c routines to do the work.

Now I have support builtin to gcc for the following:
1. Conversions between all fixed-point types and integers.
2. Addition and Subtraction for types not "long" or "long long"
3. Multiplication for short _Fract

In assembly libraries I have support for:
1. Conversion to and from fixed-point and floating point for types not "long" or "long long"
2. Multiplication for all types that are not "long" or "long long" except a few cases (see below)

Things missing: (hopefully some people are interested in helping)
1. Multiplication - Currently for micros without a mul instruction, I don't have assembly routines for s7.8 8.8 s15.16 or 16.16 types. (update: completed)
2. Division - I do not have any routines for division, so I would greatly appreciate this support. (update: completed)
3. Optimization - gcc often emits instructions to load into one register, then move to another before performing an operation resulting in an extra move. There are also a lot of other opportunities for other optimizations. (I noticed it does stupid stuff even with integers)
4. Fixed point math library - I would like to pick a few types, probably signed only, (s7.8 and s15.16) and provide library routines similar to the floating point library (sqrt, sin, cos, tan, asin, acos, atan, log, pow, etc...)
5. String conversion - I'm not sure it would be correct to build this into printf, but various routines like atof (except atok or ator etc see: http://gcc.gnu.org/wiki/FixedPoi... for suffixes) and also converting to strings. In some situations it would be best to convert to float then string, but that would use more memory if you didn't use floats otherwise.
6. Saturating types - The fixed point stardard adds types with saturation (_Sat attribute) which effectively doubles the number of new types from above. The only difference is these types saturate to the maximum or minimum value, so they are slower to use, but have certain applications. I have basically ignored these types, so all support is via the c library.

Let me know if you have any interest in this and what you have tried with it.

Last Edited: Sun. Feb 1, 2009 - 05:16 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

apparently there is a 3 file limit for attachments, here is the gdb patch.. it works for testing but isn't ready to be part of gdb yet.

Attachment(s): 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

This sounds like really great work!

Are you in contact with the avr-libc people? I think that would be a good place to ask for help for your missing functions.

Regarding fixed point division: I this what you are after? http://www.embedded.com/columns/...

Note the article contains some typing and syntax errors. E.g. the pseudo-code for the div macro should be

 DIVX_Y(A,B) (FULLSIZEINT+1) (((A.full<<Y+1)/     B.full)+1)/2

Edit: Regarding conversion to string, there is an ongoing thread here http://www.avrfreaks.net/index.p... where people are looking for the "best" conversion function. There isn't much difference between unpacked BCD and ASCII output, so that thread might be interesting for string conversion.

Stealing Proteus doesn't make you an engineer.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

geckosenator!

I've been sort of strifing this subject, but hasn't gotten at all as far as you have. This is truly great!

I've had some out-of-forum discussions with Eric Weddington on the avr-libc/WinAVR documantation and it involved, among others, stdfix.h .

Please contact EW (or the avr-libc mailing list) and report on your progress. They are the people who will be able to give the best help with moving this towards completion. Avoid double-work and all that..

There has been student work done for the AVR architecture that we might be able to capitalize on. I got a few pointers to this from EW.

I could mail an abridged version of my correspondence with EW to you but I'm a wee bit paranoid when it comes to exchanging addreses in public. Look for a PM with an email address to me!

I'm dreaming of the day when we can advice all people being flabbergasted by the code size increase for floats to move over to _Accum or _Fract!

Again, this is great work!

"He used to carry his guitar in a gunny sack, or sit beneath the tree by the railroad track. Oh the engineers would see him sitting in the shade, Strumming with the rhythm that the drivers made. People passing by, they would stop and say, "Oh, my, what that little country boy could play!" [Chuck Berry]

 

"Some questions have no answers."[C Baird] "There comes a point where the spoon-feeding has to stop and the independent thinking has to start." [C Lawson] "There are always ways to disagree, without being disagreeable."[E Weddington] "Words represent concepts. Use the wrong words, communicate the wrong concept." [J Morin] "Persistence only goes so far if you set yourself up for failure." [Kartman]

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Update:

I have completed the division routines for the smaller types (not "long" or "long long" types)

My next step is trig functions, so I'm looking for help with string functions since I don't want to do that.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

geckosenator wrote:
My next step is trig functions,[...]
CORDIC perhaps?

Don Kinzer
ZBasic Microcontrollers
http://www.zbasic.net

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

geckosenator wrote:
My next step is trig functions, so I'm looking for help with string functions since I don't want to do that.
The strtofx... functions? If you want them in C we can talk.

Stealing Proteus doesn't make you an engineer.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

ArnoldB wrote:
The strtofx... functions? If you want them in C we can talk.

C is better than nothing.. if someone else comes along with faster versions in assembly I would replace it, but for string operations I think speed is less critical.

Both string to and string from would be needed, so as a minimum:

atok (string to fract)
ator (string to accum)
ktoa (fract to string)
rtoa (accum to string)

Then you could include short versions (like atohr)

Eventually maybe printf (vsprintf) support.. take a look at how there is printf_flt, maybe we would add printf_fix, and printf_fixflt if you wanted both to avoid code bloat to people not using fixed point.

What do you think?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If C functions are just intended as an intermediate solution I wouldn't like to invest time in writing them. So I'd pass.

Stealing Proteus doesn't make you an engineer.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have tried your patches using gcc 4.3.2 (since one of them failed on 4.2.2) using Bingos modified script for Femtoos on a Fedora10 machine since I hoped to make things easy for me. The build enviroment compiles and links without your patches.

After patching the first fail was about a missing .func directive in libgcc_fixed.S. After fixing that a strange fault occur in a compiler generated assembly file.

What gcc version are you using?

Which other patches do you apply to binutils, gcc avr-libc and friends?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Thanks for trying the patches.

I am using gcc from svn.

There are no patches to binutils, or avr-libc (yet) But you do need the patches for gcc. There was a smaller patch you must apply or it might be the cause of the compiler error you saw.

I completed division and multiplication which were not done when I first posted. I have attached an updated patch which contains all of my changes. Try applying only this patch to gcc from svn and see if you can compile.

I'm working on the math library currently, so eventually I will have an avr-libc patch, I have a bunch done, but still a few routines to go, and even then they can use a lot of improvement. I have sin and cos for 32bit fixed point running about 8x faster than floating point (and it's written in c) but it's only accurate to .001
I will post a patch for avr-libc.

I have not done any work on string parsing.

Let me know if there are any other difficulties.

Last Edited: Fri. Mar 6, 2009 - 03:02 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I now have a working math library based on the CORDIC algorithm for the s15.16 fixed point type. I could implement it easily enough for other sizes, but I figured this was the most useful size to start with.. so 32bit fixed point is what I'm focusing on.

It is about half the size of the floating point library for the same functions. For example, if you just use sinr, cosr, and atan2r, it uses 722 bytes. The floating point library would use 1488 bytes.

For reference fixed point multiplication is 3x faster than floating point, and division is about the same speed.. Addition is about 25x faster for fixed point. Functions that do rounding are also about 25x faster.

sinr and cosr are more than 2x faster than floating point on avrs without multipliers.. only slightly faster if you have a hardware multiplier.

For atan2 it is about 3.5x faster since CORDIC is really good at this operation.

I know of a way to make sin and cosine much faster, but I haven't gotten around to it (hybrid approach of parabolic estimation with final CORDIC iterations)

I have implemented all of the functions in the regular math library. I added atanhr (arc tangent hyperbolic) which is normally in math libraries but currently missing from the avr floating point math library. Didn't bother with asinhr or acoshr yet.

For asinr, the performance is terrible because it uses the identity:

asinr(x) = atanr(x/sqrtr(1-x*x))

This gives accuracy to .005 degrees (about 13 bits after the decimal.. considering all the rounding errors it's not too bad)

I implemented asin directly using CORDIC but for some reason the accuracy is only .05 degrees which is considerably worse but the computation is much faster.

I still need to do a little work to make all of the valid ranges work for certain functions.. so it's not 100% complete, but it's basically working. There is a lot of optimizing that could be done.. anyone interested?

See patch for avrlibc.. it autodetects if avr-gcc has fixed point support using configure, and only builds libfixm.a if it should.

Last Edited: Fri. Mar 6, 2009 - 03:01 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have been looking for something like this for a while! I just got it to compile on OSX with the gcc trunk. I got weird complaints about missing opcodes at first but using the latest version of binutils fixed this.

I'm looking forward to trying this out, thanks again!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Great,

I have only compiled this on a linux system, so it's good to know it compiled for you on OSX.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:

I now have a working math library based on the CORDIC algorithm for the s15.16 fixed point type. I could implement it easily enough for other sizes, but I figured this was the most useful size to start with.. so 32bit fixed point is what I'm focusing on.


It sounds like a great job.

In "general" FP work, e.g., conversion between internal units and real-world units, there is all arithmetic--add, mul, an occasional divide. Maybe some exponential work if applying a curve equation.

For concentrating on the trig area, the S15.16 sounds pretty good. For "general" work, though, the 32k might be a limitation I would think. For my AVR microcontroller apps, I'd be probably mostly working with a calculated temperature or voltage. Perhaps a S23.8 lets you get to a million with two decimal places.

I don't know what would be "right". Regardless of the format care would need to be taken to avoid overflow, just as with regular integers. In floating-point one worries about accumulated error with values of vastly different magnitudes but the top range is virtually immaterial.

Lee

You can put lipstick on a pig, but it is still a pig.

I've never met a pig I didn't like, as long as you have some salt and pepper.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Quote:
Regardless of the format care would need to be taken to avoid overflow.

I believe this what the saturated types are for. The draft embedded C standard is actually kinda interesting. I also has a proposal of how multiple address spaces should be handled.

Olof

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yes, there are saturating types for all of the fixed point types. They are fully supported via the c library, so you can try them out already.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

I'm having trouble compiling avr-libc with your patch.

I got the head from CVS, run to bootstrap to build configure script, and it will build OK. When I apply your patch, make returns:

make[3]: Entering directory `/Users/friis/Desktop/avr-libc/include'
make[3]: *** No rule to make target `fixmath.h', needed by `all-am'.  Stop.

Should fixmath.h be provided by that patch? I don't see it in there.

builtins in avr-gcc seems to be working well though!

Thanks again,

Evan

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

My mistake. It looks like I missed that file with my patch. I have it included in the new patch.

When you run configure, make sure that it says:

checking whether fixed-point is supported... yes

If it says no, then it won't compile any of the fixed point math library. Let me know of any other problems.

Last Edited: Fri. Mar 6, 2009 - 03:01 AM
  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hi Boulder
and tanks to your great work.
but i'm total new to fixed point math i need some advice and where to get started and how to use your lib.
by the way thanks for your work and sharing it!

I love Digital
and you who involved in it!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

This patch is basically still experimental, but if you like, you can apply it to the latest gcc and compile. I would start with just building avr-gcc from source without fixed point support, then try applying the patch and compiling.

If you have any difficulties, feel free to post here, or send me a private message, and I'll do my best to decode the errors for you.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Hi,

This might be a dumb question, but how do I get the bits out of a _Fract? (to send over serial, for example) It seems if I cast to int/char it just truncates it to zero, which I guess is what I should expect. I looked a bit at the gcc embedded-C spec (linked from here http://gcc.gnu.org/wiki/FixedPointArithmetic) and it seems the functions I should use are

 int bitsr(_Fract pippo) 

etc. Are these implemented yet? I wouldn't mind trying to help with these, if not. It might take me a bit as I don't know much about the gcc internals.

Other than this though, I can say that I've seen a huge improvement over my templated C++ (lets not go there) fixed point class!

Thanks again.

Cheers,

Evan

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

First thanks for doing/sharing this.
I have not tested this but I will.
For a long time I have be thinking making a fast
float that's 16bit 2 complement mantissa and the normal
8 bit exp. (and perhaps for speed only use 15 bit so MSB allways is 1 when normalised). This way a mapping to and from int should be easy (read fast).
So now when you have done this work perhaps you can tell how hard it would be to write the clib's.
I have never done libs for GNU but 10 years ago I worked with a backend for the LCC compiler for our own CPU. And I assume that the structure is kind of the same.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

If you do 16 or 24 bit floats.. you would first need routines to handle all the basic operations.

Then the tricky part is adding a new type to GCC. The fixed point types were already supported for the mips backend, so I saved a lot of work that would be required.

I thought about 24bit integers.. but I decided it was too much trouble, maybe someone else knows a better way?

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have run the fixed point a bunch on actual hardware. Before I was just using the simulator.

I had to write a function to print strings over the uart. It is slow and written in c.

approximate benchmarks for attiny processor, no mul. I calculated this from actual hardware.

sink, cosk -- 2000 cycles
tank -- 3000 cycles
asink, acosk -- 4000 cycles
atank, atan2k -- 2000 cycles
logk -- 3000 cycles
expk -- 4000 cycles
powk -- 8000 cycles
sinhk, coshk -- 5000 cycles
tanhk, atanhk -- 3000 cycles
hypotk -- 2000 cycles
sqrtk -- 2000 cycles

The sqrtk can improve significantly, currently it uses CORDIC which is not the best way to implement sqrt.

The library is also much smaller (approx 4x less code than the floating point)

This is for 32bit fixed point (s15.16)

For example, 16bit fixed point (s7.8) would run twice as fast for adding, subtracting and shifting, 4x as fast for multiplication, division, and most trig operations, and for some operations more than 4x faster..

It would also require roughly half the code space.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

I have more recent patches which fix some problems.

Attachment(s): 

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

hi,

i am very sorry to disturb you with a newbie question. i was searching the web for a function loga2linear() or if you prefer antilog(). for example if i use a logarithmic potentiometer, i would like to apply a function to correct the logarithmic curve to linear. is it possible with your patch? or any other solution? i am using an atmega16.

pat

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

gcc-4.4.2 at least compiles with your patches; didn't try them yet. Did you have any progress in submitting your patches up-stream? Stumbled also over your thread on gcc-patches. Well. Now it's January 2010, and your previous post dates March 2009 and the current svn version of gcc does not seem to have fixed point support for avr, so I guess the answer is "no".

Looks like it was a work of many hours. Looks nice. Thx.

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Is there any progress on this? I only found the posts of January last year. It would be awesome to get this merged to gcc!

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Is there a one stop shopping outlet for the fixed point library and docs? Did anyone add string conversions? I just need a signed int with one single decimal point. Just adding and subtracting. I could write it myself but am lazy...

I use:
AS6 (under duress)
WinAvr 20100110
Windows 10
STK 600
AVR ONE!(broken and Atmel won't fix)
JTAGICE3 (only works with AS6)
AVRISP II
So far - '88 '2560
Sometimes my own RTOS

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

For things like the fixed point you need to wait until it's been integrated into a "WinAVR" or a "Toolchain" - I *think* the most recent Toolchain in AS5 *may* have gecksenator's fixed point work.

Quote:

I could write it myself but am lazy.

For something like that I would - just use int's multiplied up by a factor of 10 all the way through then at the last minute, before display just split the display string so that there's a d.p. before the last digit. Something like:

#include 
#include 
#include 

char buffer[10];
int value = 12345;
uint8_t len;

int main(void){
	itoa(value, buffer, 10);
	len = strlen(buffer) - 1;
	buffer[len+2] = 0;
	buffer[len+1] = buffer[len];
	buffer[len] = '.';
	while(1);
} 

At the end of that buffer[] = "1234.5"

  • 1
  • 2
  • 3
  • 4
  • 5
Total votes: 0

Yeah, I was going to do the x10 method but figured that if there was a good set of fixed point math stuff out there I wanted it. Glad to see itoa is present. In a prior life I would have had to write that too.

I use:
AS6 (under duress)
WinAvr 20100110
Windows 10
STK 600
AVR ONE!(broken and Atmel won't fix)
JTAGICE3 (only works with AS6)
AVRISP II
So far - '88 '2560
Sometimes my own RTOS