Support for compilers without 64-bit support

[GoogleCodeExporter]

It seems that some compilers/environments do not support 64-bit integers and 
those which do may support them badly (slow/bloated code). We need to implement 
a cross-platform backend to do 64-bit calculations where they are required 
(multiplication/division).

Original issue reported on code.google.com by Flatmush@googlemail.com on 24 Feb 2011 at 12:53

[GoogleCodeExporter]

Anyone who has got 32 bit fixed point division/multiplication and Atan2 
functions. Please upload !

Original comment by birdla...@gmail.com on 28 Feb 2011 at 7:57

[GoogleCodeExporter]

Check r22, I've just added the FIXMATH_NO_64BIT macro and implemented 
multiplication in 32-bit, the rest will follow soon.

Original comment by Flatmush@googlemail.com on 28 Feb 2011 at 10:00

[GoogleCodeExporter]

Original comment by Flatmush@googlemail.com on 28 Feb 2011 at 10:00

• Changed state: Started

[GoogleCodeExporter]

Ok, I implemented fix16_div and fix16_sdiv however they are less accurate than 
the 64-bit versions (~0.0035% inaccurate) and slower (~750% the speed of float, 
~375% of 64-bit version).
They do work though, just will need optimizing a bit more if you want to use 
them frequently.
It should now be possible to implement joes algorithm (as it uses fix16_sdiv 
and fix16_mul) but I'm not going to do this right now, if it's what you need 
though it should just be a matter of copying his algorithm and compiling it 
with the macro FIXMATH_NO_64BIT.
Note: FIXMATH_NO_64BIT still uses 64-bit for functions where I haven't 
implemented a 32-bit version.

Original comment by Flatmush@googlemail.com on 28 Feb 2011 at 11:37

[GoogleCodeExporter]

Just updated the division algorithms, they now run faster than a floating point 
divide (pretty impressive) which is roughly a 1250% speed increase (not the 
1600% I overestimated in the commit).
The accuracy is now much higher too at ~0.00065% rather than ~0.0035%.

Original comment by Flatmush@googlemail.com on 28 Feb 2011 at 3:06

[GoogleCodeExporter]

Wow, just tested against the 64-bit version. The 32-bit version is 300% (3 
times) as fast. The 64-bit version is 100% accurate unlike this version, but if 
you don't need scientific accuracy (or can handle the 0.00065% error) then this 
is certainly the version to use.

Original comment by Flatmush@googlemail.com on 28 Feb 2011 at 3:09

[GoogleCodeExporter]

Can anyone please update now 32bit library after all the changes and 
optimizations.

Why the following code gives the wrong answer?

#include <stdio.h>
#include <stdlib.h>

typedef __int32_t fix16_t;

fix16_t fix16_div(fix16_t inArg0, fix16_t inArg1);
volatile int d;

int main(){

    int x = 5063265; //77.2593;
    int y = -6338360;//-96.7157;

    int a;
    d = fix16_div(x, y);
    printf("%d \n",d);  
}

fix16_t fix16_div(fix16_t inArg0, fix16_t inArg1) {

        __int32_t rcp = (0xFFFFFFFF / inArg1);
        #ifndef FIXMATH_FAST_DIV
        if(((0xFFFFFFFF % inArg1) + 1) >= inArg1)
                rcp++;
        #endif
        __int32_t rcp_hi = rcp >> 16;

        __uint32_t rcp_lo = rcp & 0xFFFF;
         __int32_t arg_hi = (inArg0 >> 16);
        __uint32_t arg_lo = (inArg0 & 0xFFFF);

         __int32_t res_hi = rcp_hi * arg_hi;
         __int32_t res_md = (rcp_hi * arg_lo) + (rcp_lo * arg_hi);
        __uint32_t res_lo = rcp_lo * arg_lo;

        __int32_t res = (res_hi << 16) + res_md + (res_lo >> 16);
        #ifndef FIXMATH_NO_ROUNDING
        res += ((res_lo >> 15) & 1);
        #endif
        return res;
}

Original comment by birdla...@gmail.com on 1 Mar 2011 at 9:13

[GoogleCodeExporter]

It seems that my tests were for calculating reciprocals only, when dividing pi 
by random numbers the error is actually closer to 19% which is unacceptable. 
The precision loss is because the reciprocal is inaccurate (32-bits -> 0.00065% 
error) and multiplying it multiplies the error.
A better algorithm will be needed if we want an accuracy that's acceptable, 
when atan is implemented using this divide function it achieves an accuracy of 
5%.

Original comment by Flatmush@googlemail.com on 1 Mar 2011 at 9:37

[GoogleCodeExporter]

The changes aren't tested enough to be released (as you've found out). Release 
packages are only made for stable changes to stable code and the only real 
changes are in the 32-bit code which is currently unstable since only the 
32-bit multiply is tested and correct.

Original comment by Flatmush@googlemail.com on 1 Mar 2011 at 10:32

[GoogleCodeExporter]

looking forward to the correct 32bit codes 

Original comment by birdla...@gmail.com on 1 Mar 2011 at 2:08

[GoogleCodeExporter]

Your long wait is complete :) check the latest commit (>= r32).

32-bit fixed point divide accurate to ~0.00065%, atan/atan2 accurate to 
~0.0055%.

Original comment by Flatmush@googlemail.com on 1 Mar 2011 at 3:27

[GoogleCodeExporter]

Since r39 I would say that this issue has been solved for the most part, so I'm 
going to close it.
Any issues todo with int64.h or 32-bit implemenations of any functions should 
be posted as a new issue.

Original comment by Flatmush@googlemail.com on 3 Mar 2011 at 11:56

• Changed state: Fixed