www.digitalmars.com         C & C++   DMDScript  

digitalmars.D - reature request: fixed point

reply kov_serg <kov_serg freemail.ru> writes:
Is it possible to add to "Basic Data Types" one more type?

fixed point type is intermediate type between fload and integer. Build in
support of fixed point type will great help in realtime signal and image
processing. 32 bit fixed point with 16bit for integer part and 16 bit of
fraction is very easy implemented on any 32bit CPU and have good performance.
Especially if CPU has no FPU.

fixed x; // 32bit min=-0x8000.0000 max=0x7FFF.FFFF
...
fixed a=3.14, b=2.3, c=-5.3;
fixed d=a*b/c;

What you think about including "fixed" type in D 2.0?
Mar 01 2008
next sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
kov_serg wrote:

 Is it possible to add to "Basic Data Types" one more type?
 
 fixed point type is intermediate type between fload and integer. Build in
support of fixed point type will great help in realtime signal and image
processing. 32 bit fixed point with 16bit for integer part and 16 bit of
fraction is very easy implemented on any 32bit CPU and have good performance.
Especially if CPU has no FPU.
 
 fixed x; // 32bit min=-0x8000.0000 max=0x7FFF.FFFF
 ...
 fixed a=3.14, b=2.3, c=-5.3;
 fixed d=a*b/c;
 
 What you think about including "fixed" type in D 2.0?


What about 24.8 format? Cairo just switched to this for instance.  Or 
those based off short or long.

There are too many potential flavors.

More constructive would probably be to list things that a "struct fixed 
{...}" currently can't do that are necessary to make it seem like a 
built-in.  All the things you showed in your example are possible now.


struct fixed
{
    static fixed opCall(double x) {
         fixed R; with(R) {
          /* repr = convert x to fixed */
         } return R;
    }
    fixed opMul(fixed x) { /* return repr * x */ }
    fixed opDiv(fixed x) { /* return repr / x */ }

    int repr;
}

--bb
Mar 01 2008
parent kov_serg <kov_serg freemail.ru> writes:
Bill Baxter Wrote:

...

 What about 24.8 format? Cairo just switched to this for instance.  Or 
 those based off short or long.
 
 There are too many potential flavors.
 
 More constructive would probably be to list things that a "struct fixed 
 {...}" currently can't do that are necessary to make it seem like a 
 built-in.  All the things you showed in your example are possible now.
 
 
 struct fixed
 {
     static fixed opCall(double x) {
          fixed R; with(R) {
           /* repr = convert x to fixed */
          } return R;
     }
     fixed opMul(fixed x) { /* return repr * x */ }
     fixed opDiv(fixed x) { /* return repr / x */ }
 
     int repr;
 }
 
 --bb


I have no idea how to implement fixed type effective in D. But it very simple
in assembler code. So why not to include this type to buildin type. It simple,
it fast, it usefull.
For example for fixed 16.16 and 24.8 operation mul_div will look the same

fixed mul_div(fixed a,fixed b,fixed c) { asm {
  // assume: eax=a, edx=b, ecx=c
  imul edx
  idiv ecx
  // result in eax
}}

Simple thing must be simple
fixed d=a*b/c;
d+=a;
// and so on

I'll be happy to see fixed type in any form buildin or as a library. But I
think this type should be.

ps: I fixed 16.16 and 24.8 is the most usefull
Mar 01 2008
prev sibling next sibling parent reply "Janice Caron" <caron800 googlemail.com> writes:
On 01/03/2008, kov_serg <kov_serg freemail.ru> wrote:

  What you think about including "fixed" type in D 2.0?


Sounds like a job for a library to me.
Mar 01 2008
parent bearophile <bearophileHUGS lycos.com> writes:
Janice Caron:

 Sounds like a job for a library to me.


I agree. I think a good language has to be flexible enough to allow someone to
write some kind of "library" that gives something like a native type.

Bye,
bearophile
Mar 01 2008
prev sibling next sibling parent reply Walter Bright <newshound1 digitalmars.com> writes:
kov_serg wrote:

 Is it possible to add to "Basic Data Types" one more type?
 
 fixed point type is intermediate type between fload and integer. Build in
support of fixed point type will great help in realtime signal and image
processing. 32 bit fixed point with 16bit for integer part and 16 bit of
fraction is very easy implemented on any 32bit CPU and have good performance.
Especially if CPU has no FPU.
 
 fixed x; // 32bit min=-0x8000.0000 max=0x7FFF.FFFF
 ...
 fixed a=3.14, b=2.3, c=-5.3;
 fixed d=a*b/c;
 
 What you think about including "fixed" type in D 2.0?


It isn't too hard to do fixed point arithmetic:

typedef int Fixed;
Fixed fixed(int m, int n) { return cast(Fixed)(m * 0x10000 + n); }

Fixed a = fixed(3,14);
Fixed b = fixed(2,3);
Fixed c = -fixed(5,3);
Fixed d = a * b / c;
Mar 01 2008
next sibling parent reply "Jb" <jb nowhere.com> writes:
"Walter Bright" <newshound1 digitalmars.com> wrote in message 
news:fqd3c0$12pt$1 digitalmars.com...

 kov_serg wrote:

 Is it possible to add to "Basic Data Types" one more type?

 fixed point type is intermediate type between fload and integer. Build in 
 support of fixed point type will great help in realtime signal and image 
 processing. 32 bit fixed point with 16bit for integer part and 16 bit of 
 fraction is very easy implemented on any 32bit CPU and have good 
 performance. Especially if CPU has no FPU.

 fixed x; // 32bit min=-0x8000.0000 max=0x7FFF.FFFF
 ...
 fixed a=3.14, b=2.3, c=-5.3;
 fixed d=a*b/c;

 What you think about including "fixed" type in D 2.0?


 It isn't too hard to do fixed point arithmetic:

 typedef int Fixed;
 Fixed fixed(int m, int n) { return cast(Fixed)(m * 0x10000 + n); }

 Fixed a = fixed(3,14);
 Fixed b = fixed(2,3);
 Fixed c = -fixed(5,3);
 Fixed d = a * b / c;


The results of multiplies need to be shifted right, and divisions need to be 
shifted left. Actualy for division it's best to shift the numerator left 
before the division. But i dont see how your example would do that. Your 
example should be...

(((a*b) >> 16) << 16) / c

In that case the shifts cancel out. But this..

(((a*b)+c) / d

Would have to be..

((((a*b) >> 16)+c) << 16) / d

And one problem is whether the compiler will return an int64 for a 32 bit 
multiply, and then will it do the correct shift. I mean to multiply two 
16.16 numbers you need at least a 48 bit result.

In assembler it should be somthing like...

MOV     EAX,A
IMUL     B
SHRD    EAX,EDX,16

Is the compiler smart enough to generate that kind of code from...

d = (a*b) shr 16;

??
Mar 01 2008
next sibling parent Bill Baxter <dnewsgroup billbaxter.com> writes:
Jb wrote:

 "Walter Bright" <newshound1 digitalmars.com> wrote in message 
 news:fqd3c0$12pt$1 digitalmars.com...

 kov_serg wrote:

 Is it possible to add to "Basic Data Types" one more type?

 fixed point type is intermediate type between fload and integer. Build in 
 support of fixed point type will great help in realtime signal and image 
 processing. 32 bit fixed point with 16bit for integer part and 16 bit of 
 fraction is very easy implemented on any 32bit CPU and have good 
 performance. Especially if CPU has no FPU.

 fixed x; // 32bit min=-0x8000.0000 max=0x7FFF.FFFF
 ...
 fixed a=3.14, b=2.3, c=-5.3;
 fixed d=a*b/c;

 What you think about including "fixed" type in D 2.0?


 It isn't too hard to do fixed point arithmetic:

 typedef int Fixed;
 Fixed fixed(int m, int n) { return cast(Fixed)(m * 0x10000 + n); }

 Fixed a = fixed(3,14);
 Fixed b = fixed(2,3);
 Fixed c = -fixed(5,3);
 Fixed d = a * b / c;


 
 The results of multiplies need to be shifted right, and divisions need to be 
 shifted left. Actualy for division it's best to shift the numerator left 
 before the division. But i dont see how your example would do that. Your 
 example should be...
 
 (((a*b) >> 16) << 16) / c
 
 In that case the shifts cancel out. But this..
 
 (((a*b)+c) / d
 
 Would have to be..
 
 ((((a*b) >> 16)+c) << 16) / d
 
 And one problem is whether the compiler will return an int64 for a 32 bit 
 multiply, and then will it do the correct shift. I mean to multiply two 
 16.16 numbers you need at least a 48 bit result.
 
 In assembler it should be somthing like...
 
 MOV     EAX,A
 IMUL     B
 SHRD    EAX,EDX,16
 
 Is the compiler smart enough to generate that kind of code from...
 
 d = (a*b) shr 16;
 
 ?? 
 
 


Well, you can do inline assembly in your code, if that's what you really 
want.

--bb
Mar 01 2008
prev sibling parent Walter Bright <newshound1 digitalmars.com> writes:
Jb wrote:

 The results of multiplies need to be shifted right, and divisions need to be 
 shifted left.


Ah, you're right. I forgot.
Mar 02 2008
prev sibling next sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 02/03/2008, Walter Bright <newshound1 digitalmars.com> wrote:

 It isn't too hard to do fixed point arithmetic:

  typedef int Fixed;
  Fixed fixed(int m, int n) { return cast(Fixed)(m * 0x10000 + n); }

  Fixed a = fixed(3,14);
  Fixed b = fixed(2,3);
  Fixed c = -fixed(5,3);
  Fixed d = a * b / c;


That wouldn't work for

    Fixed e  = a * b;

But this would:

    struct Fixed(uint shift)
    {
        uint n;
        Fixed opMul(Fixed rhs)
        {
            return cast(uint)((cast(ulong)n * cast(ulong)rhs.n) >> shift);
        }
    }

    alias Fixed!(uint,16) Fixed32;

Of course, if you want also to do saturation (which digital signal
processing often requires) then there's that to take into account too.
So I still think a library solution would be best.
Mar 01 2008
prev sibling parent "Janice Caron" <caron800 googlemail.com> writes:
On 02/03/2008, Janice Caron <caron800 googlemail.com> wrote:

     alias Fixed!(uint,16) Fixed32;


Forget that part. That should have read

    alias Fixed!(16) Fixed16;

My bad. But the struct itself still looks good.
Mar 01 2008
prev sibling parent reply Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
How about 
http://team0xf.com:8080/omg?f=1b291ae58034;file=core/Fixed.d;style=gitweb ?

-- 
Tomasz Stachowiak
http://h3.team0xf.com/
h3/h3r3tic on #D freenode
Mar 02 2008
next sibling parent reply kov_serg <kov_serg freemail.ru> writes:
Tom S Wrote:


 How about ...


http://svn.icculus.org/duke3d/trunk/extras/fixed.h?view=markup&pathrev=2

Here some ideas for you ;) this old source in Watcom C++

In my practice I have to use more specialized operations for example
safe_mul_div(a,b,c) for some opration with antialiased bitmap transformation.
safe_mul_div does not throw divide by zero. simply return 0 instead. In general
case there are a lot of underwater stones.
But anyway this type is very interesting and usefull. And it should be and
should look same on different 32bit cpu and platforms. Thans you very much,
that you are interesting in this.
Mar 02 2008
parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
kov_serg wrote:

 http://svn.icculus.org/duke3d/trunk/extras/fixed.h?view=markup&pathrev=2
 
 Here some ideas for you ;) this old source in Watcom C++
 
 In my practice I have to use more specialized operations for example
safe_mul_div(a,b,c) for some opration with antialiased bitmap transformation.
safe_mul_div does not throw divide by zero. simply return 0 instead. In general
case there are a lot of underwater stones.


Thanks! I'll add it to my TODO list :>


-- 
Tomasz Stachowiak
http://h3.team0xf.com/
h3/h3r3tic on #D freenode
Mar 02 2008
prev sibling parent reply Bill Baxter <dnewsgroup billbaxter.com> writes:
Tom S wrote:

 How about 
 http://team0xf.com:8080/omg?f=1b291ae58034;file=core/Fixed.d;style=gitweb ?


Open Math for Games, huh?  Looks like a very nifty lib in the works there!

Just lay off the crazy swizzling templates in the vector class ok?  :-)

--bb
Mar 02 2008
parent Tom S <h3r3tic remove.mat.uni.torun.pl> writes:
Bill Baxter wrote:

 Open Math for Games, huh?  Looks like a very nifty lib in the works there!


Tnx. Yay for hype! :D
OMG needs support *hint hint* There's a lot of stuff to be implemented: 
http://team0xf.com:8080/omg?f=f1a719df47ba;file=TODO.txt;style=gitweb



 Just lay off the crazy swizzling templates in the vector class ok?  :-)


Hahah, they are long gone :P That was one of the priorities. The new 
vector struct has a very simple 'swizzle' function template instead.


-- 
Tomasz Stachowiak
http://h3.team0xf.com/
h3/h3r3tic on #D freenode
Mar 02 2008