Q1.15 calculation

On 06/08/2010 06:58 PM, Randy Yates wrote:
> Tim Wescott<tim@seemywebsite.now>  writes:
>> [...]
>> Is this C?  Do you have to stick to C?  C really doesn't like
>> Q1.anything -- it's only native fixed-point data type is integer, and
>> it sticks to it like glue.
>
> Er, all fixed-point processing uses plain integer
> operations. Fixed-point is all in how you interpret things.
>
> There is nothing inherently "non-fixed-point" in C. C is just fine for
> fixed-point processing.

In most processor instruction sets, multiplying two N-bit registers 
coughs up an 2*N bit answer.  In most of the rest there's a "multiply 
and return high" and a "multiply and return low".  In most of the slim 
remainder (getting fatter with all the fixed point DSP's out there) 
there is some fast way of getting one or the other part -- including 
many DSP chips that have a straight "multiply fractional and accumulate" 
or "multiply with shift and accumulate".

C discards the high half, and returns the low.  For fractional 
arithmetic, you want the high half, shifted up one.

C is just fine for _integer_ processing, but wastes a lot of steps for 
fixed point _fractional_ processing.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

Randy Yates <yates@ieee.org> wrote:
(snip)
 
> Er, all fixed-point processing uses plain integer
> operations. Fixed-point is all in how you interpret things.

Yes, but you need different product bits for multiply, and
different dividend bits for divide.  That isn't so easy in
high-level language integer operations.  Many processors
generate a 2N bit product and accept a 2N bit dividend,
but it is not so easy in high-level languages.
 
> There is nothing inherently "non-fixed-point" in C. 
> C is just fine for fixed-point processing.

-- glen

On Jun 8, 11:48&#4294967295;pm, Tim Wescott <t...@seemywebsite.now> wrote:
> On 06/08/2010 06:58 PM, Randy Yates wrote:
>
> > Tim Wescott<t...@seemywebsite.now> &#4294967295;writes:
> >> [...]
> >> Is this C? &#4294967295;Do you have to stick to C? &#4294967295;C really doesn't like
> >> Q1.anything -- it's only native fixed-point data type is integer, and
> >> it sticks to it like glue.
>
> > Er, all fixed-point processing uses plain integer
> > operations. Fixed-point is all in how you interpret things.
>
> > There is nothing inherently "non-fixed-point" in C. C is just fine for
> > fixed-point processing.
>
> In most processor instruction sets, multiplying two N-bit registers
> coughs up an 2*N bit answer. &#4294967295;In most of the rest there's a "multiply
> and return high" and a "multiply and return low". &#4294967295;In most of the slim
> remainder (getting fatter with all the fixed point DSP's out there)
> there is some fast way of getting one or the other part -- including
> many DSP chips that have a straight "multiply fractional and accumulate"
> or "multiply with shift and accumulate".
>
> C discards the high half, and returns the low. &#4294967295;For fractional
> arithmetic, you want the high half, shifted up one.
>
> C is just fine for _integer_ processing, but wastes a lot of steps for
> fixed point _fractional_ processing.

i dunno where you'll get 16-bit words nowadaze in C.  maybe the type
"short", is that usually 16 bit or is even short 32 bits?

anyway, assuming "short" is 16 bits and "long" is 32 bits, i've always
felt that C errs when the intermediate result of short x short is
still a short.  without promoting a short to a long first (which might
cost the processor an instruction cycle), a short times short should
be inherently a long.  and maybe a long times a long should be a "long
long" until it's implicitly or explicitly cast back to a long.  or
maybe that would waste an instruction cycle or two, i dunno.  but,
definitely, if C were doing what it should, a short times short should
be a long without having to cast one or the other operand first.
that's what i think, anyway.  but i know C doesn't do that.

r b-j

robert bristow-johnson <rbj@audioimagination.com> wrote:
(snip)
 
> anyway, assuming "short" is 16 bits and "long" is 32 bits, i've always
> felt that C errs when the intermediate result of short x short is
> still a short.  without promoting a short to a long first (which might
> cost the processor an instruction cycle), a short times short should
> be inherently a long.  

In general, C promotes any integer type smaller than int to
int before doing most operations on it.  On a system with 32 bit
int (most these days) multiply will generate a 32 bit result.
There is a fair chance that the compiler will figure that out
and use a 16x16-->32 multiply.

> and maybe a long times a long should be a "long
> long" until it's implicitly or explicitly cast back to a long.  or
> maybe that would waste an instruction cycle or two, i dunno.  but,
> definitely, if C were doing what it should, a short times short should
> be a long without having to cast one or the other operand first.
> that's what i think, anyway.  but i know C doesn't do that.

At least gcc will figure out that if you cast one (or both) operands
of multiply from int (or long) to long long to use a 32x32-->64
multiply instruction.  It won't generate other parts of the product
which will always be zero.   I haven't tried it on other compilers,
but they likely do it, too.  (It might be that it needs more than -O0,
I haven't checked lately.)

-- glen

On 06/08/2010 09:15 PM, robert bristow-johnson wrote:
> On Jun 8, 11:48 pm, Tim Wescott<t...@seemywebsite.now>  wrote:
>> On 06/08/2010 06:58 PM, Randy Yates wrote:
>>
>>> Tim Wescott<t...@seemywebsite.now>    writes:
>>>> [...]
>>>> Is this C?  Do you have to stick to C?  C really doesn't like
>>>> Q1.anything -- it's only native fixed-point data type is integer, and
>>>> it sticks to it like glue.
>>
>>> Er, all fixed-point processing uses plain integer
>>> operations. Fixed-point is all in how you interpret things.
>>
>>> There is nothing inherently "non-fixed-point" in C. C is just fine for
>>> fixed-point processing.
>>
>> In most processor instruction sets, multiplying two N-bit registers
>> coughs up an 2*N bit answer.  In most of the rest there's a "multiply
>> and return high" and a "multiply and return low".  In most of the slim
>> remainder (getting fatter with all the fixed point DSP's out there)
>> there is some fast way of getting one or the other part -- including
>> many DSP chips that have a straight "multiply fractional and accumulate"
>> or "multiply with shift and accumulate".
>>
>> C discards the high half, and returns the low.  For fractional
>> arithmetic, you want the high half, shifted up one.
>>
>> C is just fine for _integer_ processing, but wastes a lot of steps for
>> fixed point _fractional_ processing.
>
> i dunno where you'll get 16-bit words nowadaze in C.  maybe the type
> "short", is that usually 16 bit or is even short 32 bits?

On just about any processor whose native word length is 8- or 16 bits an 
'int' is 16 bits.  The ANSI spec says that a short is guaranteed to be 
at least 16 bits with no upper bound, an int is guaranteed to be the 
same size or bigger than a short, and a long is guaranteed to be at 
least 32 bits, again with no upper bound.  I can't remember if a long 
long is guaranteed to be 64 bits, or even if it's guaranteed to be there 
by the standard (it's not guaranteed to be there by the marketplace).

So generally on an 8- or 16-bit machine the tools will set short and int 
to 16 bits, and long to 32.  On a 64-bit machine, everything will be 64 
bits.

Assuming that something is so on an AVR or a fixed-point DSP chip just 
because it is so on your desktop is a deadly way to do embedded programming.

> anyway, assuming "short" is 16 bits and "long" is 32 bits, i've always
> felt that C errs when the intermediate result of short x short is
> still a short.  without promoting a short to a long first (which might
> cost the processor an instruction cycle), a short times short should
> be inherently a long.  and maybe a long times a long should be a "long
> long" until it's implicitly or explicitly cast back to a long.  or
> maybe that would waste an instruction cycle or two, i dunno.  but,
> definitely, if C were doing what it should, a short times short should
> be a long without having to cast one or the other operand first.
> that's what i think, anyway.  but i know C doesn't do that.

C was not designed to do DSP -- it was designed to do system 
programming.  Generally this deficiency doesn't show up too badly, but 
it does when you want to do fixed-point arithmetic that's anything other 
than integer.

-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

Tim Wescott wrote:
> On 06/08/2010 09:15 PM, robert bristow-johnson wrote:

>> i dunno where you'll get 16-bit words nowadaze in C.  maybe the type
>> "short", is that usually 16 bit or is even short 32 bits?

typedef int16_t s16;


> C was not designed to do DSP -- it was designed to do system 
> programming.

#include <libetsi.h>



Vladimir Vassilevsky
DSP and Mixed Signal Design Consultant
http://www.abvolt.com

On 06/09/2010 07:49 AM, Vladimir Vassilevsky wrote:
>
>
> Tim Wescott wrote:
>> On 06/08/2010 09:15 PM, robert bristow-johnson wrote:
>
>>> i dunno where you'll get 16-bit words nowadaze in C. maybe the type
>>> "short", is that usually 16 bit or is even short 32 bits?
>
> typedef int16_t s16;

Which works great until you do that for a 24-bit processor, or one 
that's 32-bit only.  There's a typedef that means "at least 16 bits" 
under that system (C99?) -- but that's just an int or a short, so why 
not use the original paradigm?

>> C was not designed to do DSP -- it was designed to do system programming.
>
> #include <libetsi.h>
>
>
>
> Vladimir Vassilevsky
> DSP and Mixed Signal Design Consultant
> http://www.abvolt.com


-- 
Tim Wescott
Control system and signal processing consulting
www.wescottdesign.com

Tim Wescott <tim@seemywebsite.now> wrote:
(snip)
 
> On just about any processor whose native word length is 8- or 16 bits an 
> 'int' is 16 bits.  The ANSI spec says that a short is guaranteed to be 
> at least 16 bits with no upper bound, an int is guaranteed to be the 
> same size or bigger than a short, and a long is guaranteed to be at 
> least 32 bits, again with no upper bound.  I can't remember if a long 
> long is guaranteed to be 64 bits, or even if it's guaranteed to be there 
> by the standard (it's not guaranteed to be there by the marketplace).

When the DEC Alpha first came out the C compilers for it used 64 bits
for long.  Much of the usual TCP/IP code uses long for 32 bits
(because int could be 16), and broke on the Alpha compilers.
As I understand it, long long was added to solve that problem,
though not standard until C99.  (and I don't know specifically
what the standard says about it.)
 
> So generally on an 8- or 16-bit machine the tools will set short and int 
> to 16 bits, and long to 32.  On a 64-bit machine, everything will be 64 
> bits.

I believe that there are 64 bit word addressed machines where
char, short, int, and long are all 64 bits.  Rare, though.
 
(snip)

> C was not designed to do DSP -- it was designed to do system 
> programming.  Generally this deficiency doesn't show up too badly, but 
> it does when you want to do fixed-point arithmetic that's anything other 
> than integer.

-- glen 

As several have pointed out generic fixed point math written in C
runs into several implementation specific issues. The most obvious
one is multiply.

I have done several fixed point implementations either as a C library
or as an extended data type in C compiler. At some point processor
specific issues become a factor in the implementation. The main ones
natural word length and accessibility to most significant part of the
product.

There are others that play a role. 24 bit processors are used in some
embedded applications because it provides the amount of resolution
needed to support the problem and the remaining 8 bits of the memory
implementation can be used for error corrections in bad environments.

The core embedded routines are not very hard to implement and porting
code after the core is done can be quite easy.

ISO/IEC 18037 has been implemented in some compilers to address
fixed point and DSP needs in C.

Regards,


w..
--
Walter Banks
Byte Craft Limited
http://www.bytecraft.com

On 6/9/10 10:33 AM, Tim Wescott wrote:
> 
> So generally on an 8- or 16-bit machine the tools will set short and int
> to 16 bits, and long to 32.  On a 64-bit machine, everything will be 64
> bits.

Did you really mean a 64-bit machine uses 64 bits for short and int and
long?  That's not true for every 64-bit machine.  Don't most C compilers
for 64-bit machines have 16-bit shorts, 32-bit ints, and 64-bit longs?

> 
> Assuming that something is so on an AVR or a fixed-point DSP chip just
> because it is so on your desktop is a deadly way to do embedded
> programming.

Definitely agree with that!

Ray