A Type Conversion Question

[Randy Yates]

Consider the following code:

#include "dsptypes.h"

/* definitions */

#define VECTOR_LENGTH 64

/* local variables */

/* local function prototypes */

/* function definitions */

int main(int margc, char **margv)
{
UINT16_T n;
INT16_T x[VECTOR_LENGTH];
INT16_T y[VECTOR_LENGTH];
INT32_T acc;
INT16_T result;

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
x[n] = n;
y[n] = VECTOR_LENGTH - n - 1;
}

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
acc += x[n] * y[n];
}

result = (INT16_T)(acc >> 16);

return result;
}

What does ISO C say about how the conversions in the

acc += x[n] * y[n];

line are to be done? Specifically, is the multiply to be done with 16
bits, then the result promoted to 32 bits, or are x and y first to be
promoted to 32 bits before the multiply? Does the standard specify?

 

[Eric Sosman]

Consider the following code:

#include "dsptypes.h"

Nice of you to hide the crucial details where
nobody can see them ...

/* definitions */

#define VECTOR_LENGTH 64

/* local variables */

/* local function prototypes */

/* function definitions */

int main(int margc, char **margv)
{
UINT16_T n;
INT16_T x[VECTOR_LENGTH];
INT16_T y[VECTOR_LENGTH];
INT32_T acc;
INT16_T result;

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
x[n] = n;
y[n] = VECTOR_LENGTH - n - 1;
}

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
acc += x[n] * y[n];
}

result = (INT16_T)(acc >> 16);

return result;
}

What does ISO C say about how the conversions in the

acc += x[n] * y[n];

line are to be done? Specifically, is the multiply to be done with 16
bits, then the result promoted to 32 bits, or are x and y first to be
promoted to 32 bits before the multiply? Does the standard specify?

Unanswerable with the information provided: you
haven't revealed what INT16_T and INT32_T are.

If INT16_T is `short' and INT32_T is `int', the
two array elements are promoted to `int', multiplied
to produce a 32-bit product, and added to `acc'.

If INT16_T is `int' and INT32_T is `long', the
two array elements are not promoted, the multiplication
produces a 16-bit product, and finally the product is
promoted to `long' and added to `acc'.

If ... ah, pfui. I'm tired of running through all
the possible combinations; look 'em up yourself.

 

[Randy Yates]

Consider the following code:

#include "dsptypes.h"

Nice of you to hide the crucial details where
nobody can see them ...

/* definitions */

#define VECTOR_LENGTH 64

/* local variables */

/* local function prototypes */

/* function definitions */

int main(int margc, char **margv)
{
UINT16_T n;
INT16_T x[VECTOR_LENGTH];
INT16_T y[VECTOR_LENGTH];
INT32_T acc;
INT16_T result;

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
x[n] = n;
y[n] = VECTOR_LENGTH - n - 1;
}

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
acc += x[n] * y[n];
}

result = (INT16_T)(acc >> 16);

return result;
}

What does ISO C say about how the conversions in the

acc += x[n] * y[n];

line are to be done? Specifically, is the multiply to be done with 16
bits, then the result promoted to 32 bits, or are x and y first to be
promoted to 32 bits before the multiply? Does the standard specify?

Unanswerable with the information provided: you
haven't revealed what INT16_T and INT32_T are.

If INT16_T is `short' and INT32_T is `int', the
two array elements are promoted to `int', multiplied
to produce a 32-bit product, and added to `acc'.

If INT16_T is `int' and INT32_T is `long', the
two array elements are not promoted, the multiplication
produces a 16-bit product, and finally the product is
promoted to `long' and added to `acc'.

If ... ah, pfui. I'm tired of running through all
the possible combinations; look 'em up yourself.

Gladly, but I don't have the spec, and I understand it's
not cheap.

Here are the relevent typedefs:

typedef short INT16_T;
typedef long INT32_T;

 

[Eric Sosman]

Gladly, but I don't have the spec, and I understand it's
not cheap.

Eighteen dollars, U.S. A textbook will probably cost
more, but it seems that might be a better investment for
you. No offense meant: Everybody starts from zero.

Here are the relevent typedefs:

typedef short INT16_T;
typedef long INT32_T;

long += short * short
-> long += (int)short * (int)short
-> long += int
-> long += (long)int
-> long += long

 

[Keith Thompson]

Eighteen dollars, U.S. A textbook will probably cost
more, but it seems that might be a better investment for
you. No offense meant: Everybody starts from zero.


long += short * short
-> long += (int)short * (int)short
-> long += int
-> long += (long)int
-> long += long

And the behavior of that depends on whether int is 16 or 32 bits.
(I suppose it could be 24, but that's unlikely.)

 

[Jack Klein]

Consider the following code:

#include "dsptypes.h"

Nice of you to hide the crucial details where
nobody can see them ...

/* definitions */

#define VECTOR_LENGTH 64

/* local variables */

/* local function prototypes */

/* function definitions */

int main(int margc, char **margv)
{
UINT16_T n;
INT16_T x[VECTOR_LENGTH];
INT16_T y[VECTOR_LENGTH];
INT32_T acc;
INT16_T result;

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
x[n] = n;
y[n] = VECTOR_LENGTH - n - 1;
}

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
acc += x[n] * y[n];
}

result = (INT16_T)(acc >> 16);

return result;
}

What does ISO C say about how the conversions in the

acc += x[n] * y[n];

line are to be done? Specifically, is the multiply to be done with 16
bits, then the result promoted to 32 bits, or are x and y first to be
promoted to 32 bits before the multiply? Does the standard specify?

Unanswerable with the information provided: you
haven't revealed what INT16_T and INT32_T are.

If INT16_T is `short' and INT32_T is `int', the
two array elements are promoted to `int', multiplied
to produce a 32-bit product, and added to `acc'.

If INT16_T is `int' and INT32_T is `long', the
two array elements are not promoted, the multiplication
produces a 16-bit product, and finally the product is
promoted to `long' and added to `acc'.

If ... ah, pfui. I'm tired of running through all
the possible combinations; look 'em up yourself.

Gladly, but I don't have the spec, and I understand it's
not cheap.

Here are the relevent typedefs:

typedef short INT16_T;
typedef long INT32_T;

Unfortunately, that does not provide enough information to answer your
question. Either short or long happens to have the same size and
representation as int on your platform, and that is what matters.

On a 32 bit desktop/DSP/micro where int is 32 bits, same as long, then
the two 16-bit shorts will be promoted to 32-bit ints before the
multiplication and it will produce a 32-bit result, as you probably
want.

On an 8-bit or 16-bit micro/DSP where int has 16 bits, those two
16-bit shorts are still "promoted" to ints, but since ints also have
16 bits the promotion is in theory only. The result will be a 16x16
multiply with a 16-bit result.

Some early compilers for the TI 28xx DSP actually got this wrong, if
you compiled with no optimization, and if you stored the result of a
16x16 multiply into a 32-bit object, it actually stored the entire 32
bit contents of the accumulator. That is actually an example of
non-conformance with the C standard, and they fixed it in later
versions.

 

[Randy Yates]

Randy Yates wrote:
Consider the following code:

#include "dsptypes.h"

Nice of you to hide the crucial details where
nobody can see them ...

/* definitions */

#define VECTOR_LENGTH 64

/* local variables */

/* local function prototypes */

/* function definitions */

int main(int margc, char **margv)
{
UINT16_T n;
INT16_T x[VECTOR_LENGTH];
INT16_T y[VECTOR_LENGTH];
INT32_T acc;
INT16_T result;

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
x[n] = n;
y[n] = VECTOR_LENGTH - n - 1;
}

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
acc += x[n] * y[n];
}

result = (INT16_T)(acc >> 16);

return result;
}

What does ISO C say about how the conversions in the

acc += x[n] * y[n];

line are to be done? Specifically, is the multiply to be done with 16
bits, then the result promoted to 32 bits, or are x and y first to be
promoted to 32 bits before the multiply? Does the standard specify?

Unanswerable with the information provided: you
haven't revealed what INT16_T and INT32_T are.

If INT16_T is `short' and INT32_T is `int', the
two array elements are promoted to `int', multiplied
to produce a 32-bit product, and added to `acc'.

If INT16_T is `int' and INT32_T is `long', the
two array elements are not promoted, the multiplication
produces a 16-bit product, and finally the product is
promoted to `long' and added to `acc'.

If ... ah, pfui. I'm tired of running through all
the possible combinations; look 'em up yourself.

Gladly, but I don't have the spec, and I understand it's
not cheap.

Here are the relevent typedefs:

typedef short INT16_T;
typedef long INT32_T;

Unfortunately, that does not provide enough information to answer your
question. Either short or long happens to have the same size and
representation as int on your platform, and that is what matters.

On a 32 bit desktop/DSP/micro where int is 32 bits, same as long, then
the two 16-bit shorts will be promoted to 32-bit ints before the
multiplication and it will produce a 32-bit result, as you probably
want.

On an 8-bit or 16-bit micro/DSP where int has 16 bits, those two
16-bit shorts are still "promoted" to ints, but since ints also have
16 bits the promotion is in theory only. The result will be a 16x16
multiply with a 16-bit result.

Some early compilers for the TI 28xx DSP actually got this wrong, if
you compiled with no optimization, and if you stored the result of a
16x16 multiply into a 32-bit object, it actually stored the entire 32
bit contents of the accumulator. That is actually an example of
non-conformance with the C standard, and they fixed it in later
versions.

Thanks for the response, Jack. In fact it is the TI 54xx compiler I
was using. For the following C code,

#include "dsptypes.h"

/* definitions */

#define VECTOR_LENGTH 64

/* local variables */

/* local function prototypes */

/* function definitions */

int main(int margc, char **margv)
{
UINT16_T n;
INT16_T x[VECTOR_LENGTH];
INT16_T y[VECTOR_LENGTH];
INT32_T acc;
INT16_T result;

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
x[n] = n;
y[n] = VECTOR_LENGTH - n - 1;
}

acc = 0;
for (n = 0; n < VECTOR_LENGTH; n++)
{
acc += x[n] * y[n];
}

result = (INT16_T)(acc >> 16);

return result;
}

that compiler produced the following assembly

0000:0108 main
0000:0108 4A11 PSHM 11h
0000:0109 4A17 PSHM 17h
0000:010A EE80 FRAME -128
0000:010B E781 MVMM SP,AR1
0000:010C 6DE9 MAR *+AR1(64)
0000:010E E787 MVMM SP,AR7
0000:010F E782 MVMM SP,AR2
0000:0110 E800 LD #0h,A
0000:0111 771A STM 3fh,1ah
0000:0113 F072 RPTB 11ah
0000:0115 L1
0000:0115 8092 STL A,*AR2+
0000:0116 E93F LD #3fh,B
0000:0117 F520 SUB A,0,B
0000:0118 8191 STL B,*AR1+
0000:0119 F000 ADD #1h,0,A,A
0000:011B L2
0000:011B E782 MVMM SP,AR2
0000:011C 6DEA MAR *+AR2(64)
0000:011E E783 MVMM SP,AR3
0000:011F E800 LD #0h,A
0000:0120 EC3F RPT #3fh
0000:0121 L3
0000:0121 B089 MAC *AR2+,*AR3+,A,A
0000:0122 L4
0000:0122 F0E0 SFTL A,0,A
0000:0123 F0F0 SFTL A,-16,A
0000:0124 6BF8 ADDM 80h,*(18h)
0000:0127 F495 NOP
0000:0128 F495 NOP
0000:0129 8A17 POPM 17h
0000:012A 8A11 POPM 11h
0000:012B F4E4 FRET

It is obvious here that the two shorts are multiplied using
32-bit accuracy, not 16. The C manual for the 54x states that
an int is 16 bits. So isn't this compiler in violation of
the ANSI standard as well?

 

[Randy Yates]

Eighteen dollars, U.S. A textbook will probably cost
more, but it seems that might be a better investment for
you. No offense meant: Everybody starts from zero.


long += short * short
-> long += (int)short * (int)short
-> long += int
-> long += (long)int
-> long += long

Hi Eric,

This brings up a question in my mind. If you expand out the "+=" syntax, you get this:

long = long + short * short

So, the question is whether the "usual conversions" that are performed when
preparing to operate on operands are done only for binary operands in the
order dictated by the precedence of operators, or for multiple (>2) operands
simultaneously.

That is, is the "short * short" taken first since "*" has precedence over "+",
and then the type conversion done on the operands to this binary operation first
(in which case the short * short will still be performed using a int result),
or are the type conversion rules done on the entire string of operations
at once, in which case the shorts will be promoted to longs before "*" is
applied?

 

[Eric Sosman]

[...]
long += short * short
-> long += (int)short * (int)short
-> long += int
-> long += (long)int
-> long += long

Hi Eric,

This brings up a question in my mind. If you expand out the "+=" syntax, you get this:

long = long + short * short

So, the question is whether the "usual conversions" that are performed when
preparing to operate on operands are done only for binary operands in the
order dictated by the precedence of operators, or for multiple (>2) operands
simultaneously.

That is, is the "short * short" taken first since "*" has precedence over "+",
and then the type conversion done on the operands to this binary operation first
(in which case the short * short will still be performed using a int result),
or are the type conversion rules done on the entire string of operations
at once, in which case the shorts will be promoted to longs before "*" is
applied?

There's no "forecasting:" The promotions (if any) that
occur while evaluating sub-expressions are not affected by
what goes on in the larger, containing expression. The
multiplication of the two shorts occurs the same way in
this expression as it would in any other; the fact that
the product will eventually be converted to a long doesn't
affect the process at all.

If you think about it a bit, you'll see that this is
the sensible way to do things. For example, if the type of
the final result were somehow magically enforced across the
whole expression, things like

int c = 100;
int f = 32 + (int)(1.8 * c + 0.5);

.... would not work right. If `1.8 * c + 0.5' were evaluated
according to the rules of int arithmetic, 1.8 would become
simply 1 and 0.5 would be 0, so you'd have the equivalent of

int c = 100;
int f = 32 + c;

 

[Randy Yates]

It is obvious here that the two shorts are multiplied using
32-bit accuracy, not 16. The C manual for the 54x states that
an int is 16 bits. So isn't this compiler in violation of
the ANSI standard as well?

Jack, others participating in this thread,

Isn't there a difference between "non-conformancy" and "undefined
operation"? That is, when the multiplication overflows, isn't
the result undefined, in which case performing a 32-bit addition
is valid? Or does the C standard define precisely what is supposed
to happen when the result overflows?

 

[Randy Yates]

There's no "forecasting:" The promotions (if any) that
occur while evaluating sub-expressions are not affected by
what goes on in the larger, containing expression.

Thanks for the clarification, Eric.

By the way, I went to the ANSI site and looked for the C specification
but couldn't find it. Can you please provide the specific title, or
give a link to the specific page on the site?

 

[Randy Yates]

That is, when the multiplication overflows, isn't
the result undefined, in which case performing a 32-bit addition
is valid?

Sorry, I meant to write "... in which case performing a
32-bit MULTIPLICATION is valid?"

 

[Kevin Bracey]

In message <[email protected]>

[...]
long += short * short

That is, is the "short * short" taken first since "*" has precedence over
"+", and then the type conversion done on the operands to this binary
operation first (in which case the short * short will still be performed
using a int result), or are the type conversion rules done on the entire
string of operations at once, in which case the shorts will be promoted
to longs before "*" is applied?

There's no "forecasting:" The promotions (if any) that
occur while evaluating sub-expressions are not affected by
what goes on in the larger, containing expression. The
multiplication of the two shorts occurs the same way in
this expression as it would in any other; the fact that
the product will eventually be converted to a long doesn't
affect the process at all.

Indeed. But a good compiler may well be able to spot this and have an option
to warn about it. The compiler I use, given the example above, would issue
the warning "lower precision in wider context: '*'".

This can be useful to point out such potential mistakes. Of course, it can
also be an annoyance - there are cases where you quite reasonably want to
calculate part of a subexpression to lower precision.

 

[Eric Sosman]

Thanks for the clarification, Eric.

By the way, I went to the ANSI site and looked for the C specification
but couldn't find it. Can you please provide the specific title, or
give a link to the specific page on the site?

Search for document 9899-1999. (Use a dash, not a colon,
if you want to avoid sticker shock.)

By the way, are you the same Randy Yates who in a thread
about pointers wrote

This is a flaw in the C standard, in my opinion.

? Pretty gutsy stuff, dishing out bug reports for a Standard
you haven't even seen ...

 

[Kevin Bracey]

In message <[email protected]>

Jack, others participating in this thread,

Isn't there a difference between "non-conformancy" and "undefined
operation"? That is, when the multiplication overflows, isn't the result
undefined, in which case performing a 32-bit addition is valid? Or does the
C standard define precisely what is supposed to happen when the result
overflows?

I think you may have a valid point there. Given that it was signed
arithmetic, then technically speaking you invoke undefined behaviour by
overflow. So the compiler is free to do what it wants.

However, for unsigned arithmetic, the standard does require results to be
reduced modulo (TYPE_MAX+1).

Also, nearly all implementations document signed arithmetic overflow as being
handled in a modulo fashion, effectively "defining" the undefined behaviour.
So your compiler may still be violating its documentation.

For what it's worth, assuming you do want a 16x16->32 multiply, the way I'd
write it in C would be:

acc += (INT32_T) x[n] * y[n];

That promotes x[n] to INT32_T, and hence y[n] as well (because the operands
must match), so you invoke a 32x32->32 multiply. C does not have the concept
of an operation that produces a result wider than its operands.

However, hopefully a compiler will spot when a semantic 32x32->32 multiply is
actually of the form:

(16-bit signed quantity widened to 32 bits)
x (16-bit signed quantity widened to 32 bits) -> 32 bits

and reduce that into a signed 16x16->32 multiply operation, if that's
sensible for the target architecture.

 

[Randy Yates]

In message <[email protected]>

Jack, others participating in this thread,

Isn't there a difference between "non-conformancy" and "undefined
operation"? That is, when the multiplication overflows, isn't the result
undefined, in which case performing a 32-bit addition is valid? Or does the
C standard define precisely what is supposed to happen when the result
overflows?

I think you may have a valid point there. Given that it was signed
arithmetic, then technically speaking you invoke undefined behaviour by
overflow. So the compiler is free to do what it wants.

However, for unsigned arithmetic, the standard does require results to be
reduced modulo (TYPE_MAX+1).

Also, nearly all implementations document signed arithmetic overflow as being
handled in a modulo fashion, effectively "defining" the undefined behaviour.
So your compiler may still be violating its documentation.

For what it's worth, assuming you do want a 16x16->32 multiply, the way I'd
write it in C would be:

acc += (INT32_T) x[n] * y[n];

That promotes x[n] to INT32_T, and hence y[n] as well (because the operands
must match), so you invoke a 32x32->32 multiply. C does not have the concept
of an operation that produces a result wider than its operands.

Kevin, I agree with everything you say up to this point. I should have
clarified in my post that it would be suicide to *depend* on such
behavior.

However, hopefully a compiler will spot when a semantic 32x32->32 multiply is
actually of the form:

(16-bit signed quantity widened to 32 bits)
x (16-bit signed quantity widened to 32 bits) -> 32 bits

and reduce that into a signed 16x16->32 multiply operation, if that's
sensible for the target architecture.

I don't see what's being reduced here.

 

[Randy Yates]

Search for document 9899-1999. (Use a dash, not a colon,
if you want to avoid sticker shock.)

Thanks Eric!

By the way, are you the same Randy Yates who in a thread
about pointers wrote


? Pretty gutsy stuff, dishing out bug reports for a Standard
you haven't even seen ...

Yes, well, was that a bug report or just a comment in a usenet
article? Maybe gutsy (stupid?) nonetheless. That syntax has been
a peeve of mine for years.

 

[Kevin Bracey]

In message <[email protected]>

I don't see what's being reduced here.

Concrete example: 16-bit architecture, 16-bit int, 32-bit long with a
16x16->32 multiply instruction.

Normally,

uint32_t a, b, c;

c = a * b;

would involve doing a fair amount of work to synthesise a 32x32->32 multiply
in the absence of such an instruction in the architecture.

But

uint32_t a, b, c;
uint16_t d, e;

a = d; b = e;

c = a * b;

can be spotted by the compiler - if it can deduce that although a and b are
32-bit, they only contain 16-bit numbers, it can use the 16x16->32 multiply
instruction.

Whether any of this applies to your case, I don't know. I'm sure it has a
32x32->32 multiply instruction, but maybe it's slower than the 16x16->32 one.

The point is that there is no way of directly expressing a 16x16->32 multiply
operation in C. If there is such an instruction in your architecture, and you
want to use it, you have to rely on the compiler optimisations being "clever"
enough to spot places where it can reduce a C 32x32->32 construct into a
16x16->32 machine operation.

 

[Kevin Bracey]

In message <[email protected]>

Yes, well, was that a bug report or just a comment in a usenet
article? Maybe gutsy (stupid?) nonetheless. That syntax has been
a peeve of mine for years.

I think that was uncalled for from Eric. The comment wasn't a criticism
of the standard as such. It could equally have read

"This is a flaw in the C language, in my opinion."

Whether anyone has a copy of the standard or not is nothing to do with a
critique of C's basic pointer declaration syntax.

That said, I'd say not having access to the C standard is pretty
unforgiveable, given the cost, and the level of questions you're asking.

 

[Randy Yates]

In message <[email protected]>


I think that was uncalled for from Eric.

Fortunately my hide is (now) thick enough that these things don't
bother me. (20 years ago that may not have been true)

I appreciate the expertise that folks like yourself and Eric bring
to the group. Thanks for giving me a hand.