#### Do you have a question? Post it now! No Registration Necessary

**posted on**

- vectorizor

February 16, 2009, 6:38 pm

Ok guys, I'm looking at some computation done in fixed-point, and

there is one that I dont quite understand. Here it is:

#define mul19dot12by1dot14(a,b) (((((a)>>16)*(b))<<2) + (TINT32)

(((TUINT32)(((TUINT16)(a))*(TUINT16)(b)))>>14))

What is being done here is multiplying a 32 bits number by a 16 bits

one, so theoretically the result is up to 48 bits. Therefore, to do it

in ANSI C, we'd have to use 64 bits arithmetic. But this is slow,

especially, on embedded processors. Hence, the computation is divided

into 2 16 bits multiplications, and 1 addition, so 32 bits arithmetic

can be used. Btw, I believe the result is also in 19.12.

I more or less understand the intent, which is to divide the 19.12

number into 2 16 bits numbers, multiplying them by the 1.14 number,

which gives us 2 32 bits numbers, which we add to get the result. But

I dont quite understand all the subtleties of the computation. here

are some specific questions:

1) the first part of the macro: (((a)>>16)*(b))<<2) . Shifting a by

16 to get its MSB, and multypling them, ok, but why the <<2 ?!?!

2) Same thing with the second part. Whyhe >> 14? How does the

recombination of the 2 intermediate results work?

Thanks in advance,

Alex

there is one that I dont quite understand. Here it is:

#define mul19dot12by1dot14(a,b) (((((a)>>16)*(b))<<2) + (TINT32)

(((TUINT32)(((TUINT16)(a))*(TUINT16)(b)))>>14))

What is being done here is multiplying a 32 bits number by a 16 bits

one, so theoretically the result is up to 48 bits. Therefore, to do it

in ANSI C, we'd have to use 64 bits arithmetic. But this is slow,

especially, on embedded processors. Hence, the computation is divided

into 2 16 bits multiplications, and 1 addition, so 32 bits arithmetic

can be used. Btw, I believe the result is also in 19.12.

I more or less understand the intent, which is to divide the 19.12

number into 2 16 bits numbers, multiplying them by the 1.14 number,

which gives us 2 32 bits numbers, which we add to get the result. But

I dont quite understand all the subtleties of the computation. here

are some specific questions:

1) the first part of the macro: (((a)>>16)*(b))<<2) . Shifting a by

16 to get its MSB, and multypling them, ok, but why the <<2 ?!?!

2) Same thing with the second part. Whyhe >> 14? How does the

recombination of the 2 intermediate results work?

Thanks in advance,

Alex

Re: 19.12 x 1.14

It seems pretty clear that the values of 2, 14, and 16 satisfy

the relation 2 + 14 = 16 and this is used to align the

two partial products.

I would not use code like this in an implementation. I might

conceivably use it to try to bit-match some hardware implementation.

In general I would rebel against anything like this, and use

something like System C fixed-point types, if I could.

Steve

Re: 19.12 x 1.14

Many thanks to the prompt answer.

All right, but I cant work out the whys and hows of this alignment.

FOr instance, for the 1st part of the multiplication, taking the 16

MSB of the 19.12 number creates an integer that needs to be multiplied

by 8 to get its real value in the original 19.12 number. Hence I'd

shift it by 3, not 2?! Does that make sense?

Thanks for the suggestion, I am not aware of System C , and I shall

take a look.

Thanks again

Alex

All right, but I cant work out the whys and hows of this alignment.

FOr instance, for the 1st part of the multiplication, taking the 16

MSB of the 19.12 number creates an integer that needs to be multiplied

by 8 to get its real value in the original 19.12 number. Hence I'd

shift it by 3, not 2?! Does that make sense?

Thanks for the suggestion, I am not aware of System C , and I shall

take a look.

Thanks again

Alex

Re: 19.12 x 1.14

The calculation looks okay to me. a can be 32 bits and b can

be 14 bits. The first term takes the 16 MSB's of a, multiplies

them by b, and places the 30 bit result in bits 31 through 2.

The second term takes the 16 LSB's of a, multiplies them

by b, and places the 16 MSB's of the 30 bit result in bits

15 through 0.

This is the correct justification because for the first

term, the MSB of the result ends up in bit 31, and for

the second term, the MSB of the result ends up in bit 15.

Which is correct given that for the first term, you

had shifted the input a by 16.

Hope this helps.

Steve

Re: 19.12 x 1.14

[...]

Simple rules: '>>' decreases fractional digit count, '<<' increases, '*'

adds. If a is 19.12 and b is 1.14, this yields

12 (from a)

- 16 (right shift)

+ 14 (from multiplication by b)

+ 2 (left shift)

= 12

fractional digits.

Same thing. 12 + 14 - 12 = 12 fractional bits.

They are compatible because both have 12 fractional bits. So you now

only have to check that you've used all input bits. If b has 16 bits

total, it is always used completely, and the 32 bits of a are split

evenly, so that works, too.

Stefan

Re: 19.12 x 1.14

One of the things that bothers me about the macro is implicit

conversions.

For example, I take it that the first parameter is assumed to be a

variable or value that the c compiler will evaluate as a 32-bit

unsigned word and that the second parameter is assumed to be a

variable or value that the c compiler will evaluate as a 16-bit

unsigned word.

Taking a working part of the macro as an example, shifting (a) by 16

bits downward, (a) >> 16, would yield a result that the compiler would

maintain as a 32-bit unsigned word. Multiplying it by (b) would cause

'b' to be promoted first to a 32-bit signed value, then to a 32-bit

unsigned value (I think it goes in order, like that) before the

multiplication is coded. So the compiler would choose a 32x32

multiplication algorithm that tosses away the upper 32 bits of the 64

bit result (without special back-end processing, anyway.) No problem

there, really, as the product fits.

But the other part of the macro casts (a) and (b) to 16-bit unsigned

values, I gather. In doing so, the compiler may choose a 16x16

multiplication that tosses away the upper 16 bits of the result, since

the c compiler expects the result doesn't necessarily have to be any

larger than the two values being multipled. Since all 16 bits of (a)

would be valid [4.12 format with the upper bits tossed away] and since

(b) has 15 valid bits [1.14 format], the resulting product (without

more analysis) could have 31 bits of useful information. Shifting

that downwards by 14 places, as the macro does, might leave 1 valid

bit in the upper 16-bit part of the result. And since the c compiler

is permitted to toss it, it might get lost and not included in the

sum. So I think this is worth a little more thought to be sure it

will always work out.

To understand the macro though, assuming away the above issues for a

moment, we have the following:

((a) >> 16) is this:

0000 0000 0000 0000|0xxx xxxx xxxx xxxx|0000^

where I placed a caret (^) at the location of the implied radix point

and where a vertical bar (|) is placed at 16-bit word boundaries. It's

only the first two words. I just tacked on the last 0's to allow

placement of the implied radix point. (b) is this:

0y^yy yyyy yyyy yyyy

assuming that there is no sign present and that the 1.14 designation

is accurate.

The macro generates two products. Let's look at the details. I'll

put hidden parts (those parts the compiler doesn't "see" but which

help us keep track of the radix) in parentheses.

0000 0000 0000 0000 | 0xxx xxxx xxxx xxxx (|0000^0000)

x 0000 0000 0000 0000 | 0y^yy yyyy yyyy yyyy

------------------------------------------- multiplication

00zz zzzz zzzz zzzz | zzzz zz^zz zzzz zzzz <--- yields

=========================================== shifted up by 2

zzzz zzzz zzzz zzzz | zzzz^ zzzz zzzz zz00 <--- yields

Note that this retains all of the integer bits of precision and

retains only 10 bits of precision below the radix point. The least

signicant two bits are lost. Which may, or may not, be okay. The

upshot is that the result of this is, so far, in [20.12] format.

For now, against my earlier argument about word sizes that I think the

compiler might use, let's assume that the other product is also done

as a 32x32 multiplication. It then looks like this:

0000 0000 0000 0000 | xxxx^ xxxx xxxx xxxx

x 0000 0000 0000 0000 | 0y^yy yyyy yyyy yyyy

-------------------------------------------- multiplication

0zzz zz^zz zzzz zzzz | zzzz zzzz zzzz zzzz <--- yields

============================================ shifted down by 14

0000 0000 0000 000z | zzzz^ zzzz zzzz zzzz <--- yields

Now, note two things. One is that the implied radix point is located

exactly in the same place. This is good. The addition is properly

aligned, then, and the result will be sensible. The other thing to

note is that there is a valid bit in the upper word.

Which brings me back to my earlier point. When the c compiler gets

done with the 16x16 multiplication and takes only the lower 16 bits of

the result, it is then faced with the addition step. That requires an

implicit conversion to take place if the explicit one didn't already

force the issue, promoting the 16 bit result of the second product to

a 32-bit value before addition. But in doing so, I am thinking that

the upper bit shown above may get lost.

Jon

Re: 19.12 x 1.14

Not in K&R C. Is this one of the things they changed

in ANSI C? In K&R, C Reference Manual, section 6.6 on

evaluating expressions, it states "First any operands of

type char or short are converted to int..." The upcasting

occurs before the multiply.

In my previous replies to this thread I assumed the

result of any C multiply operator is 32 bits as

would be, or once was, standard.

Of course, an C compiler for an embedded target

may choose to do things differently, regardless

of any standard.

Steve

Re: 19.12 x 1.14

The macro contains the expression

((((a)>>16)*(b))<<2)

If ints are not larger than 16 bits, such an expression

will never work. Granted, they could be 24 bits or something.

Probably though they are 32.

Being a macro, with no surrounding code, compiler version,

or target stated, we don't really know, but I'm pretty certain

the above expression is not going to work as expected with

16 bit ints.

Certainly true. We're forced to either guess at the context

here, or probe the OP for more info. I chose to guess. ;-)

Steve

Re: 19.12 x 1.14

On Mon, 16 Feb 2009 23:59:10 +0000 (UTC), snipped-for-privacy@speedymail.org

I haven't used K&R c for a long time. Pretty much everything is

'89-ish, now.

Yes. Implicit promotions. I tend to rely upon Harbison & Steele

these days, though. Not the K&R book(s). (I still have two copies of

my original 1978 purchases made in... well, 1978! Original owner when

I was doing Unix v6 stuff.)

Hmm. Can you find that in the standard? It's been my vague

understanding that this falls under "usual conversions, integer

promotions" in discussing binary operators, like multiplication. I

think the standard says something like, "If both operands have the

same type, then no further conversion is needed." This doesn't

address itself to the result of the operation, though. In the case of

preprocessing and where the values are known at that time (constants),

I think different rules apply than what apply if the values are

computed at run-time. In the run-time case, I'm open to hearing that

the result of an integer multiplication of two rvalues of the same

integer rank must be of a higher rank... but my bad memory suggests

that this is not always the case. It may be implementation defined,

but I seem to recall compilers I've used not so many years back

yielding multiplications that don't seem to fit what you are saying.

To test this idea, I decided to try out the older 16-bit c compiler

from Microsoft. Their v1.52c, which is the last one they made before

going completely over to the 'dark side' of 32-bit only compilers.

Here is the result:

I think this makes the point I had in mind. At least, in this case.

Well, I'm not the guardian of c standards and I learn along with many

as I go. Been at it some 30 years now in c (since 1978), so I've

learned to be a little cautious on these points. I took the time to

completely expose my thinking, though, so I'm wide open for being

shown my errors. Which is as it should be.

Jon

I haven't used K&R c for a long time. Pretty much everything is

'89-ish, now.

Yes. Implicit promotions. I tend to rely upon Harbison & Steele

these days, though. Not the K&R book(s). (I still have two copies of

my original 1978 purchases made in... well, 1978! Original owner when

I was doing Unix v6 stuff.)

Hmm. Can you find that in the standard? It's been my vague

understanding that this falls under "usual conversions, integer

promotions" in discussing binary operators, like multiplication. I

think the standard says something like, "If both operands have the

same type, then no further conversion is needed." This doesn't

address itself to the result of the operation, though. In the case of

preprocessing and where the values are known at that time (constants),

I think different rules apply than what apply if the values are

computed at run-time. In the run-time case, I'm open to hearing that

the result of an integer multiplication of two rvalues of the same

integer rank must be of a higher rank... but my bad memory suggests

that this is not always the case. It may be implementation defined,

but I seem to recall compilers I've used not so many years back

yielding multiplications that don't seem to fit what you are saying.

To test this idea, I decided to try out the older 16-bit c compiler

from Microsoft. Their v1.52c, which is the last one they made before

going completely over to the 'dark side' of 32-bit only compilers.

Here is the result:

I think this makes the point I had in mind. At least, in this case.

Well, I'm not the guardian of c standards and I learn along with many

as I go. Been at it some 30 years now in c (since 1978), so I've

learned to be a little cautious on these points. I took the time to

completely expose my thinking, though, so I'm wide open for being

shown my errors. Which is as it should be.

Jon

Re: 19.12 x 1.14

I'm saying what I assumed.

The value 32 bits is in no standard. However, if you

are not using longs, then the size of the result of any multiply

is the size of an int. That I'm pretty sure must be the case.

This is an interesting area. I think you're right that it's

possible for constant expressions to be evaluated at compile

time in a way that yields a different result from those

evaluated at run time.

However, since we're just given the OP's macro, we can't say

that it is evaluated at compile time. In the general

case, the parameters in the OP's macro are replaced with variables,

and it then becomes an expression to be evaluated only at run-time.

Thanks for the example. (The OP's case did not use any longs

(at least, that we can see from here...)) I think your

result is consistent with promoting both operands to longs

before multiplying.

Steve

Re: 19.12 x 1.14

On Tue, 17 Feb 2009 02:30:01 +0000 (UTC), snipped-for-privacy@speedymail.org

I'm pretty sure I'm correct here. There is a clear standard on the

preprocessor and it is, to my knowledge, not entirely the same as the

way the c language compiler handles the situation (as interpreted by

the use of human language to describe the behavior.)

I was pretty much considering things from a run-time point of view

when I first wrote, setting aside arguments about the preprocessor.

The OP wrote, "What is being done here is multiplying a 32 bits number

by a 16 bits one..." It's clear from that usage. 'a' is a 32 bit

value that is semantically a 19.12 bit value (with the high order bit

set to zero, I can only assume, or else signed.) 'b' is a 16 bit

value that is semantically a 1.14 bit value (again with the high order

bit set to zero, assuming along the same lines from above.) In other

words, 'a' is either a TUINT32 or else a TINT32 (if signed) and 'b' is

either a TUINT16 or else a TINT16 (if signed.)

Not if I understand what you are saying. The subexpression prior to

the + operator would be, if the values are as the OP stated and I have

interpreted from there, a 32-bit integer and a 16-bit integer. The c

compiler would, of course, promote the 16-bit integer to the one of

higher rank, which is the 32-bit integer value. At that point, the

multiplication operation would be chosen on the basis after the

implicit promotion. The subexpression

other hand, just happens to

values

done before the c compiler gets a chance to look more closely at the

binary operation, it would "see" two equally ranked, 16 bit values on

both sides and would

instead choose a 16x16-->16 operation. (I've looked a lot at the

emulation libraries of various embedded c compilers to see enough of

the subroutines often used for these purposes.) So the second half of

the expression wouldn't necessarily be performed promoting its

operands to 32 bits. In fact, I assert that it decidedly would not do

that.

But again, I'm flawed and may not have the fuller view. That's just

how I see it. By the way, I've tested the macro a few times on some c

compilers with values I know will probably not work... and indeed it

doesn't work right in those cases.

Jon

I'm pretty sure I'm correct here. There is a clear standard on the

preprocessor and it is, to my knowledge, not entirely the same as the

way the c language compiler handles the situation (as interpreted by

the use of human language to describe the behavior.)

I was pretty much considering things from a run-time point of view

when I first wrote, setting aside arguments about the preprocessor.

The OP wrote, "What is being done here is multiplying a 32 bits number

by a 16 bits one..." It's clear from that usage. 'a' is a 32 bit

value that is semantically a 19.12 bit value (with the high order bit

set to zero, I can only assume, or else signed.) 'b' is a 16 bit

value that is semantically a 1.14 bit value (again with the high order

bit set to zero, assuming along the same lines from above.) In other

words, 'a' is either a TUINT32 or else a TINT32 (if signed) and 'b' is

either a TUINT16 or else a TINT16 (if signed.)

Not if I understand what you are saying. The subexpression prior to

the + operator would be, if the values are as the OP stated and I have

interpreted from there, a 32-bit integer and a 16-bit integer. The c

compiler would, of course, promote the 16-bit integer to the one of

higher rank, which is the 32-bit integer value. At that point, the

multiplication operation would be chosen on the basis after the

implicit promotion. The subexpression

___after___the + operator, on theother hand, just happens to

___explicitly___cast the values to 16 bitvalues

___prior___to the binary multiplication operator. Since that isdone before the c compiler gets a chance to look more closely at the

binary operation, it would "see" two equally ranked, 16 bit values on

both sides and would

___not___choose a 32x32-->32 multiplication, butinstead choose a 16x16-->16 operation. (I've looked a lot at the

emulation libraries of various embedded c compilers to see enough of

the subroutines often used for these purposes.) So the second half of

the expression wouldn't necessarily be performed promoting its

operands to 32 bits. In fact, I assert that it decidedly would not do

that.

But again, I'm flawed and may not have the fuller view. That's just

how I see it. By the way, I've tested the macro a few times on some c

compilers with values I know will probably not work... and indeed it

doesn't work right in those cases.

Jon

Re: 19.12 x 1.14

[interesting discussion of preprocessor snipped]

[code example snipped]

Okay. What I wrote above, promoting the operands first, does give the

result your program gave, and also is how K&R C would define the

behavior. I don't know about C89 but I'll take your word for it

that it has changed there. (I don't have a copy of the standard

on hand.)

Distinct from all this, a compliant compiler might emit code that

doesn't step-by-step follow the specified behavior in the standard;

so long as the result is always the same.

Thanks. I like these language design questions, and it's always

interesting to me how a seemingly straightforward language like

C can produce these subtleties. I am now highly curious to see the

C89 spec to find the relevant language, and I will do this at the

next convenient point in time.

Steve

Re: 19.12 x 1.14

The compiler is not at liberty to make that decision. If int is more

than 16 bits wide on the target platform (otherwise the casts would be

pointless), those explicit casts don't have the effect you think. Every

16-bit value, whether created by casting or because the number is so

narrow begin with, would get cast up to a 32-bit value on such a

platform.

___Before___the arithmetic operation is evaluated, that is.

On a 32-bit platform, it has to behave at least outwardly as if it did

exactly that.

Re: 19.12 x 1.14

It is. Not not just multipliy, either, but all arithmetic operations.

Stated more compactly the rule is:

C won't perform arithmetic on anything smaller than an int.

The catch is that each implementation gets to pick its own size for int,

and that will change the actual results of that rule.

But that only applies

___after___both have been made at least as big as an int.

Actually, it does. The type of the result is the same as the (now equal)

type of the converted operands.

No. Preprocessing does indeed have its own rules (IIRC everything gets

cast up to long int), but calculations on constants outside preprocessor

instructions follow the same rules as those on variables.

If you hear that, you're being lied to. :-)

It's actually never the case in a correct implementation.

No, he isn't.

Re: 19.12 x 1.14

(snip)

That is true for int and smaller. Some C implementations have long

larger than int, others have (long long) longer than int. Since most

machines have multiply instructions that generate a product twice as

long as the operands, it is sometimes nice to be able to do that from C.

Some compilers given:

int a,b;

long long c;

c=(long long)a*b;

recognize that even though a has been cast to (long long) that

it only contains an (int), and generate a single multiply instruction.

Yes. The interesting things happen when one operand is larger

than an int.

-- glen

That is true for int and smaller. Some C implementations have long

larger than int, others have (long long) longer than int. Since most

machines have multiply instructions that generate a product twice as

long as the operands, it is sometimes nice to be able to do that from C.

Some compilers given:

int a,b;

long long c;

c=(long long)a*b;

recognize that even though a has been cast to (long long) that

it only contains an (int), and generate a single multiply instruction.

Yes. The interesting things happen when one operand is larger

than an int.

-- glen

#### Site Timeline

- » Driving LED with PWM, Beginner's Question
- — Next thread in » Embedded Programming

- » uC with easy USB
- — Previous thread in » Embedded Programming

- » FFT Speeds
- — Newest thread in » Embedded Programming

- » FFT Speeds
- — The site's Newest Thread. Posted in » Embedded Programming