# 19.12 x 1.14

• posted

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))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))
• posted

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

• posted

on 2 + 14 =3D 16 and this is used to align the

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

• posted

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

• posted

[...]

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

• posted

I think if b is more than 14 bits, and a is 32 bits, you end up overflowing some MSB's and it fails. I could be wrong though. I'd have to stare at it longer and I think I've stared at it long enough. :-)

Steve

• posted

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
• posted

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

• posted

That does assume ints are 32bits. That assumption does not appear in the original question are far as I can see. And, ints are not required to be 32 bits by any of the C standards AFAIK.

Robert

• posted

The macro contains the expression

((((a)>>16)*(b))to be 32 bits by any of the C standards AFAIK.

Certainly true. We're forced to either guess at the context here, or probe the OP for more info. I chose to guess. ;-)

Steve

• posted

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

• posted

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

• posted

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 the other hand, just happens to _explicitly_ cast the values to 16 bit values _prior_ to the binary multiplication operator. Since that is 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 _not_ choose a 32x32-->32 multiplication, but 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

• posted
[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

• posted

Yes the result is 19.12, and that is important.

Direct multiplying of 19.12 and 1.14 gives a 20.26 product. To get the 19.12 (or 20.12) product you right shift 14 bits. The first takes the more significant bits of a, after the shift it is 19.-4, multiply by 1.14 for a 20.10 result. Shift left 2 for 20.12.

I would use bitwise and to remove excess bits,

#define mul19dot12by1dot14(a,b) \ (((((a)>>16)*(b))14))

The second one takes the low 16 bits of a, 4.12 multiplies by 1.14 generating a 5.26 product. Shifts right 14 for 5.14, then add.

The PL/I precision and scale form uses the total digits (not including sign bit) and digits after the radix point. That makes it a little easier to read when the scale factor (digits after the radix point) is negative.

-- glen

• posted

Hi Alex,

In a nutshell, it's taking in A(19,12) and A(1,14) and returning an A(19,12).

As you've correctly noted, this would normally require 32+16 = 48 bits, and would have a scaling of A(21,26).

The macro gets us back to 32 bits (and A(19,12)) by throwing away 2 bits of the high result (the > 14).

```--
%  Randy Yates                  % "With time with what you've learned,
%% Fuquay-Varina, NC            %  they'll kiss the ground you walk ```
• posted

Agreed; I had assumed it does not overflow. Assuming 32-bit ints, only (((a)>>16)*(b))

• posted

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.

• posted

Hans-Bernhard Bröker wrote: (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

• posted

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.

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.