19.12 x 1.14

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

Translate This Thread From English to

Threaded View
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

Re: 19.12 x 1.14

Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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?

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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
Quoted text here. Click to load it
[...]
Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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

Re: 19.12 x 1.14
On Mon, 16 Feb 2009 20:33:19 +0000 (UTC), snipped-for-privacy@speedymail.org

Quoted text here. Click to load it

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

Quoted text here. Click to load it


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
Quoted text here. Click to load it

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

Re: 19.12 x 1.14



Quoted text here. Click to load it



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.

Quoted text here. Click to load it

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

Quoted text here. Click to load it

I haven't used K&R c for a long time.  Pretty much everything is
'89-ish, now.

Quoted text here. Click to load it

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.)

Quoted text here. Click to load it

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:

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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

Quoted text here. Click to load it



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.

Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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.)

Quoted text here. Click to load it

I was pretty much considering things from a run-time point of view
when I first wrote, setting aside arguments about the preprocessor.

Quoted text here. Click to load it

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.)

Quoted text here. Click to load it

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

Re: 19.12 x 1.14

[interesting discussion of preprocessor snipped]

Quoted text here. Click to load it



[code example snipped]

Quoted text here. Click to load it


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.

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

Re: 19.12 x 1.14
On Tue, 17 Feb 2009 21:36:10 +0100, Hans-Bernhard Bröker

Quoted text here. Click to load it

Thanks.  But I have looked at 16-bit c compiler cases and examined the
output.  So while what you say is true for 32-bit platforms, it isn't
everywhere true for c compilers.

Jon

Re: 19.12 x 1.14

Quoted text here. Click to load it



The compiler could do a 16x16-->32 unsigned multiply, though.

Personally, I would use &0xffff instead of the cast.

-- glen


Re: 19.12 x 1.14
Quoted text here. Click to load it

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.

Quoted text here. Click to load it

But that only applies _after_ both have been made at least as big as an int.

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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.

Quoted text here. Click to load it

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

Quoted text here. Click to load it

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

Quoted text here. Click to load it

No, he isn't.

Re: 19.12 x 1.14
(snip)

Quoted text here. Click to load it



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.

Quoted text here. Click to load it


Yes.  The interesting things happen when one operand is larger
than an int.

-- glen


Re: 19.12 x 1.14

Quoted text here. Click to load it

IIRC "long long" is part of C99.  Perhaps that standard says
something specifically about the above expression, but what you
describe does not seem consistent with the spirit of earlier C
standards.  I would think you would have to promote the operands.

Steve

Site Timeline