www.digitalmars.com         C & C++   DMDScript  

D - DSP

reply vadim 7chips.com writes:
Hello,

I believe that people doing DSP would love to use D if it had fixed point data
type.

IMO this is major feuture that is miising in current HLL (c c++ etc)...

Walter i suppos it coule be pretty easyly added to the language?


Vadim
Aug 10 2003
parent reply "Walter" <walter digitalmars.com> writes:
<vadim 7chips.com> wrote in message news:bh6v6o$2rdj$1 digitaldaemon.com...
 Hello,

 I believe that people doing DSP would love to use D if it had fixed point
data
 type.

 IMO this is major feuture that is miising in current HLL (c c++ etc)...

 Walter i suppos it coule be pretty easyly added to the language?
I've done fixed point arithmetic using longs many times. The only time it isn't a long is when you input/output it. Then just put the '.' in the right spot.
Aug 10 2003
next sibling parent Bill Cox <bill viasic.com> writes:
Walter wrote:
 <vadim 7chips.com> wrote in message news:bh6v6o$2rdj$1 digitaldaemon.com...
 
Hello,

I believe that people doing DSP would love to use D if it had fixed point
data
type.

IMO this is major feuture that is miising in current HLL (c c++ etc)...

Walter i suppos it coule be pretty easyly added to the language?
I've done fixed point arithmetic using longs many times. The only time it isn't a long is when you input/output it. Then just put the '.' in the right spot.
I think a lot of guys do the same thing. However, lots of guys out there don't know the rules, like you can do unsigned multiplies with correct results, but not divides. I suspect that D's GC might make the language difficut to use for DSP applications. Bill
Aug 11 2003
prev sibling next sibling parent reply vadim 7chips.com writes:
In article <bh7dbg$8f7$1 digitaldaemon.com>, Walter says...
<vadim 7chips.com> wrote in message news:bh6v6o$2rdj$1 digitaldaemon.com...
 Hello,

 I believe that people doing DSP would love to use D if it had fixed point
data
 type.

 IMO this is major feuture that is miising in current HLL (c c++ etc)...

 Walter i suppos it coule be pretty easyly added to the language?
I've done fixed point arithmetic using longs many times. The only time it isn't a long is when you input/output it. Then just put the '.' in the right spot.
Walter, while it is possible to do foxed point math uisng longs (or shorts) it is pretty tedious and error prone process that makes writing(and reading) DSP algorithms unnecessary defiificult. And the generated code usually sucks... Example (in C) using GCC #define FRACBITS 16 #define FIX(v) (int) (0.5 + (v* (1 << FRACBITS))) #define ASFLOAT(v) (float) (v/(float) (1 << FRACBITS)) int v32 = FIX(3.2); int v44 = FIX(4.4); int wrong; int good; main() { wrong = v32*v44; good = ((long long)v32*v44) >> FRACBITS; printf("wrong = %f good = %f should be: %d/100\n", ASFLOAT(wrong), ASFLOAT(good), 32*44) ; } and the code generated is: movl _v32, %eax imull _v44, %eax movl %eax, _wrong movl _v44, %eax imull _v32 shrdl $16, %edx, %eax sarl $16, %edx movl %eax, _good in case of built in fixed point type the compiler is able to generate much more efficient code and correctly handle exception conditions (saturations, underflows. It would be really helpful to have the type like signed fixed:12.24 or unsigned fixed:8.8 (with conevrsions from./to int and float) Vadim
Aug 11 2003
next sibling parent reply "Walter" <walter digitalmars.com> writes:
Ok, I see your point. When I used fixed point math, it was only in a few
spots, so the extra work to take care of shifting the decimal point didn't
seem important.

<vadim 7chips.com> wrote in message news:bh9ns2$2r34$1 digitaldaemon.com...
 In article <bh7dbg$8f7$1 digitaldaemon.com>, Walter says...
<vadim 7chips.com> wrote in message
news:bh6v6o$2rdj$1 digitaldaemon.com...
 Hello,

 I believe that people doing DSP would love to use D if it had fixed
point
data
 type.

 IMO this is major feuture that is miising in current HLL (c c++ etc)...

 Walter i suppos it coule be pretty easyly added to the language?
I've done fixed point arithmetic using longs many times. The only time it isn't a long is when you input/output it. Then just put the '.' in the
right
spot.
Walter, while it is possible to do foxed point math uisng longs (or shorts) it is pretty tedious and error prone process that makes writing(and reading) DSP algorithms unnecessary defiificult. And the generated code usually
sucks...
 Example (in C) using GCC

 #define FRACBITS 16

 #define FIX(v)  (int) (0.5 + (v* (1 << FRACBITS)))
 #define ASFLOAT(v) (float) (v/(float) (1 << FRACBITS))
 int v32 = FIX(3.2);
 int v44 = FIX(4.4);

 int wrong;
 int good;

 main()
 {
 wrong = v32*v44;
 good = ((long long)v32*v44) >> FRACBITS;

 printf("wrong = %f  good = %f should be: %d/100\n", ASFLOAT(wrong),
 ASFLOAT(good),  32*44) ;
 }

 and the code generated is:
 movl _v32, %eax
 imull _v44, %eax
 movl %eax, _wrong
 movl _v44, %eax
 imull _v32
 shrdl $16, %edx, %eax
 sarl $16, %edx
 movl %eax, _good




 in case of built in fixed point type  the compiler is able to generate
much more
 efficient code and correctly handle exception conditions (saturations,
 underflows.

 It would be really helpful to have the type like

 signed fixed:12.24  or unsigned fixed:8.8  (with conevrsions from./to int
and
 float)


 Vadim
Aug 11 2003
next sibling parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
It's tricky to keep track of when to shift and by how much, in a complex
expression, especially if terms have different numbers of fraction bits.  It
certainly gets ugly in C.  A smart enough compiler could even automatically
optimize shifts out when possible, could keep track of when an overflow was
about to happen inside an expression and only do shifts when necessary, and
for the final result.

It's the declarative model versus the imperative model.  Keeps code in one
place (in this case, in the compiler would be ideal).  You've had firsthand
experience with the imperative model.  But the declarative model is so much
easier to use, or at least it seems like it would be.  I wouldn't know, I've
never had the luxury of a language that natively supported fixed point.

It does seem low-level enough that end-coders shouldn't have to write it.
But making something this close to a native type in a library is a no-go.
Language overhead causes inefficiency.  The optimizer has to reverse
engineer what it is that the library is telling it to do, leading to
inefficient code generation.  You probably are aware of how hard it is for a
compiler to optimize around inline assembly.  Well, the implementation of
library classes like this tend to end up needing to use inline assembly,
(especially for SIMD!) and are inherently not good candidates for
optimization, which is exactly the opposite of the goal which is efficient
code, both in source and executable form.

Sean

"Walter" <walter digitalmars.com> wrote in message
news:bha19r$44b$1 digitaldaemon.com...
 Ok, I see your point. When I used fixed point math, it was only in a few
 spots, so the extra work to take care of shifting the decimal point didn't
 seem important.
Aug 12 2003
prev sibling parent Mark Evans <Mark_member pathlink.com> writes:
Fixed point is a good idea, very much in line with the two leading design
philosophies of D, 'systems language' and 'speed is everything'.  Language
support would ease ports to embedded and DSP chips.  Don't be so heavily focused
on Wintel end-user application development that everything else seems
specialized.

Mark
Aug 12 2003
prev sibling next sibling parent reply "Sean L. Palmer" <palmer.sean verizon.net> writes:
Excellent argument.

I actually like your declaration syntax better than mine.  ;)   But I'd like
to remove the need for wordy signed/unsigned, by making it more like:

fixed:12.24  or ufixed:8.8

This is more consistent with how D handles int types.

What kind of literals would it have?  Int and float literals implicitly
convertible to it?  Or should there be a suffix as there is for most other
numeric types?

How could one specify saturation?

Sean

<vadim 7chips.com> wrote in message news:bh9ns2$2r34$1 digitaldaemon.com...
 In article <bh7dbg$8f7$1 digitaldaemon.com>, Walter says...
I've done fixed point arithmetic using longs many times. The only time it
isn't a long is when you input/output it. Then just put the '.' in the
right
spot.
Walter, while it is possible to do foxed point math uisng longs (or shorts) it is pretty tedious and error prone process that makes writing(and reading) DSP algorithms unnecessary defiificult. And the generated code usually
sucks...
 Example (in C) using GCC

 #define FRACBITS 16

 #define FIX(v)  (int) (0.5 + (v* (1 << FRACBITS)))
 #define ASFLOAT(v) (float) (v/(float) (1 << FRACBITS))
 int v32 = FIX(3.2);
 int v44 = FIX(4.4);

 int wrong;
 int good;

 main()
 {
 wrong = v32*v44;
 good = ((long long)v32*v44) >> FRACBITS;

 printf("wrong = %f  good = %f should be: %d/100\n", ASFLOAT(wrong),
 ASFLOAT(good),  32*44) ;
 }

 and the code generated is:
 movl _v32, %eax
 imull _v44, %eax
 movl %eax, _wrong
 movl _v44, %eax
 imull _v32
 shrdl $16, %edx, %eax
 sarl $16, %edx
 movl %eax, _good




 in case of built in fixed point type  the compiler is able to generate
much more
 efficient code and correctly handle exception conditions (saturations,
 underflows.

 It would be really helpful to have the type like

 signed fixed:12.24  or unsigned fixed:8.8  (with conevrsions from./to int
and
 float)


 Vadim
Aug 12 2003
parent "Vadim Lebedev" <vlebedev aplio.fr> writes:
I suppose the obious way to specify saturation will be something like:

saturated fixed:12.14  v;

Vadim
"Sean L. Palmer" <palmer.sean verizon.net> wrote in message
news:bhaafl$eg2$1 digitaldaemon.com...
 Excellent argument.

 I actually like your declaration syntax better than mine.  ;)   But I'd
like
 to remove the need for wordy signed/unsigned, by making it more like:

 fixed:12.24  or ufixed:8.8

 This is more consistent with how D handles int types.

 What kind of literals would it have?  Int and float literals implicitly
 convertible to it?  Or should there be a suffix as there is for most other
 numeric types?

 How could one specify saturation?

 Sean

 <vadim 7chips.com> wrote in message
news:bh9ns2$2r34$1 digitaldaemon.com...
 In article <bh7dbg$8f7$1 digitaldaemon.com>, Walter says...
I've done fixed point arithmetic using longs many times. The only time
it
isn't a long is when you input/output it. Then just put the '.' in the
right
spot.
Walter, while it is possible to do foxed point math uisng longs (or shorts) it
is
 pretty tedious and error prone process that makes writing(and reading)
DSP
 algorithms unnecessary defiificult.  And the generated code usually
sucks...
 Example (in C) using GCC

 #define FRACBITS 16

 #define FIX(v)  (int) (0.5 + (v* (1 << FRACBITS)))
 #define ASFLOAT(v) (float) (v/(float) (1 << FRACBITS))
 int v32 = FIX(3.2);
 int v44 = FIX(4.4);

 int wrong;
 int good;

 main()
 {
 wrong = v32*v44;
 good = ((long long)v32*v44) >> FRACBITS;

 printf("wrong = %f  good = %f should be: %d/100\n", ASFLOAT(wrong),
 ASFLOAT(good),  32*44) ;
 }

 and the code generated is:
 movl _v32, %eax
 imull _v44, %eax
 movl %eax, _wrong
 movl _v44, %eax
 imull _v32
 shrdl $16, %edx, %eax
 sarl $16, %edx
 movl %eax, _good




 in case of built in fixed point type  the compiler is able to generate
much more
 efficient code and correctly handle exception conditions (saturations,
 underflows.

 It would be really helpful to have the type like

 signed fixed:12.24  or unsigned fixed:8.8  (with conevrsions from./to
int
 and
 float)


 Vadim
Aug 13 2003
prev sibling parent Bill Cox <bill viasic.com> writes:
Hi, Vadim.

After watching this group for a few months, my gut feel is that fixed 
point arithmetic is a bit too specialized for D, and wont be included 
(though I'd support it).  There's no use trying to convince me. 
Walter's the feature guy, and he's very particular about adding features 
that make D more complex.

Obviously, such features would be of real benifit to DSP coders.  There 
are lots of language extensions that can't make it into D that would be 
of great value to various kinds of developers.

The only solution I see to this problem is to make the compiler 
extendable, so that library support of features like fixed point 
arithmetic are implemented just as well as built-ins.

However, this turns out to be somewhat difficult to do well.  The two 
solutions demonstraighted so far are languages that are slow, and 
typically interpreted (Scheme, Forth), and languages that open up 
everything in the compiler from the lexer to the code generator for 
hacking (Pliant).

Walter uses sophisticated custom C++ structures to represent D code, 
which help make the compiler fast, and aids his development.  This seems 
to be incompatible with full language extensibility, since we would have 
to be able to contribute code directly into his source files to make new 
built-in features.

I wish I knew a good solution.

Bill

vadim 7chips.com wrote:
 In article <bh7dbg$8f7$1 digitaldaemon.com>, Walter says...
 
<vadim 7chips.com> wrote in message news:bh6v6o$2rdj$1 digitaldaemon.com...

Hello,

I believe that people doing DSP would love to use D if it had fixed point
data
type.

IMO this is major feuture that is miising in current HLL (c c++ etc)...

Walter i suppos it coule be pretty easyly added to the language?
I've done fixed point arithmetic using longs many times. The only time it isn't a long is when you input/output it. Then just put the '.' in the right spot.
Walter, while it is possible to do foxed point math uisng longs (or shorts) it is pretty tedious and error prone process that makes writing(and reading) DSP algorithms unnecessary defiificult. And the generated code usually sucks... Example (in C) using GCC #define FRACBITS 16 #define FIX(v) (int) (0.5 + (v* (1 << FRACBITS))) #define ASFLOAT(v) (float) (v/(float) (1 << FRACBITS)) int v32 = FIX(3.2); int v44 = FIX(4.4); int wrong; int good; main() { wrong = v32*v44; good = ((long long)v32*v44) >> FRACBITS; printf("wrong = %f good = %f should be: %d/100\n", ASFLOAT(wrong), ASFLOAT(good), 32*44) ; } and the code generated is: movl _v32, %eax imull _v44, %eax movl %eax, _wrong movl _v44, %eax imull _v32 shrdl $16, %edx, %eax sarl $16, %edx movl %eax, _good in case of built in fixed point type the compiler is able to generate much more efficient code and correctly handle exception conditions (saturations, underflows. It would be really helpful to have the type like signed fixed:12.24 or unsigned fixed:8.8 (with conevrsions from./to int and float) Vadim
Aug 12 2003
prev sibling parent "Sean L. Palmer" <palmer.sean verizon.net> writes:
Getting the language to deal with providing a large enough temporary buffer
for the intermediate results before shifting back down would be incredibly
helpful.  Automating the calculation and generation of the shift would be
easy.

A fixed-point multiply is  (short * short ==> long >> 16 ==> short ), which
is difficult to express with C and D also.  But it's an unbelievably
powerful tool, especially where floating point is too costly.

It certainly could benefit from some standardization (something better than
MulDiv, please!) and some serious syntactic sugar.  Making it look alot like
floating point math would be tremendously helpful to us mere humans.  ;)

From the declaration side of things all we need is to specify the base type
(can't be long or you'll not be able to safely multiply without software
emulation!) and how many bits to shift right after a multiply (the number of
bits of fraction.)    Something like    fixed int:4    or    fixed ushort:12

If you want to get really nice you can support a real division instead of a
shift, thus allowing working with fixed point currency, etc.  Things that
divide by other than power of two.  Seconds, for example.  Doesn't matter
much for DSP or pixel work but someone would be happy to have it.

Believe it or not, SIMD operations for this sort of thing exist on many SIMD
platforms.   Think 4 or 8 fixed point multiplies per 2 or 3 cycles.

At very least, a way to specify two short numbers multiply together into a
long buffer *without* extending the shorts first would enable someone to
write a reasonably efficient templated fixed point package (ok, need
division support too), but IMHO this borders too closely on code generation
to properly belong in user or library code.  Need the user to know too much
about the guts of the machine.  Code will not be portable and efficient;  it
would be restricted to either but not both.

Most machines can preserve precision when working with multiplication or
division of word (not long) sized quantities.  Why can't our languages do
that?

Sean

"Walter" <walter digitalmars.com> wrote in message
news:bh7dbg$8f7$1 digitaldaemon.com...
 <vadim 7chips.com> wrote in message
news:bh6v6o$2rdj$1 digitaldaemon.com...
 Hello,

 I believe that people doing DSP would love to use D if it had fixed
point
 data
 type.

 IMO this is major feuture that is miising in current HLL (c c++ etc)...

 Walter i suppos it coule be pretty easyly added to the language?
I've done fixed point arithmetic using longs many times. The only time it isn't a long is when you input/output it. Then just put the '.' in the
right
 spot.
Aug 12 2003