Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Path: utzoo!mnetor!uunet!seismo!sundc!sun!gorodish!guy
From: guy%gorodish@Sun.COM (Guy Harris)
Newsgroups: comp.lang.c
Subject: Re: 16x16 = 32
Message-ID: <31167@sun.uucp>
Date: Sun, 18-Oct-87 03:16:29 EDT
Article-I.D.: sun.31167
Posted: Sun Oct 18 03:16:29 1987
Date-Received: Sun, 18-Oct-87 23:03:58 EDT
References: <143@kesmai.COM>
Sender: news@sun.uucp
Lines: 106

> ...There is no question that the fully unoptimized expression (where ints
> are 16 bits and longs are 32 bits).
> 
>    ((long) (x * y)) where x and y are ints says:
> 
>    get int x
>    get int y
>    multiply using operation appropriate for 16 bit ints
>    convert result to long (32 bits).
> ...
>
> ...I was addressing one of the other ways to skin a cat.

Given the semantics of C, the correct way to do this on a 68K C implementation,
with 16-bit "int"s, would be to do a MULS and then to sign-extend the low-order
16 bits of the result into a 32-bit quantity.  If, however, the result were
immediately converted to an "int" (e.g., if you had

	int x, y, z;

	z = (long) (x * y);

) it would be permissible merely to throw the low-order 16 bits into "z" and
throw away the high-order 16 bits.

(This means that a "typical" 68000 16-bit-"int" implementation of C will, for
the code fragment:

	int x = 30000;
	int y = 30000;

	printf("%ld\n", (long) (x * y));

print "-5888".  30,000 times 30,000 is 900,000,000; the hex value of this is
0x35a4e900.  Truncated to 16 bits, this is 0xe900, so the result of (x * y)
would, in this implementation, be 0xe900, which is -5888 in two's complement.
A C implementation with 16-bit "int"s could, of course give a different result,
or trap on overflow, because 900,000,000 won't fit into an "int", but "int" is
the type of the result of "(x * y)"; as K&R say, "the handling of overflow and
divide check in expression evaluation is machine-dependent".)

Now, if MWC says that they must sign-extend the result of the multiplication
*even if the result is immediately converted to "int"*, but they define the
result of a multiplication of an "int" by an "int" as the result you get by
multiplying the integer values of the two "int"s (i.e., doing real live
arithmetic, not machine arithmetic) and then taking the result modulo 2^16
(i.e., chopping off all but the low 16 bits), then they're full of prunes.
Given that the sign-extension will only tack 16 bits of 0 or 1 to the
front of the low-order 16 bits, and that the conversion of this back to "int"
will only chop those bits off again (K&R, "6.1 Characters and Integers": "When
a longer integer is converted to a shorter or to a 'char', it is truncated on
the left; excess bits are simply discarded."), doing the sign extension is
indeed needless *if* the "long" value is not to be used except to convert it
back to "int".

However, you are presumably not doing that (why convert it to "long" only to
immediately convert it back to "int"?); you say you want a 16x16->32 multiply,
which is not what "int * int" is in a C implementation with 16-bit "int"s.

> I think it highly unlikely that ((long) x) * y would give me a better
> result as then the compiler has to realise that an expression now cast
> as long was previously short so that a 16x16 multiply is
> perfectly viable.  I would speculate that this is easily as complicated
> if not more than realising that the result of a MULS operation doesn't
> require an extend to long.  Granted, it expresses the result wanted
> better but in reality I think it highly doubtful you could find a compiler
> for the Amiga, ST, or Mac that would generate anything but 32x32 operations
> from the expression.

Naah.  Our 68K C compiler, when asked to do:

	short x, y;
	long z;

	z = (long)x * (long)y;

will quite cheerfully do a MULS instruction to multiply "s1" and "s2", and
stuff the 32-bit result into "z".  It will do this even if you *don't* specify
optimization!  Since our compiler has 32-bit "int"s, the example above most
closely matches what a 16-bit compiler would do with "x" and "y" being "int"s.

It may be complicated (I seem to remember hearing that getting this right was a
bit tricky), but it's certainly not impossible.  If you can't find an Amiga,
ST, or Mac compiler that would turn:

	int x, y;
	long z;

	z = (long)x * (long)y;

into a MULS followed by a MOVE.L of the 32-bit result of the MULS into "z", it
means the state of the art for Amiga, ST, and Mac compilers isn't very advanced
at all.

> Finally.  Again, I'm not debating that the code MW generates is correct. I'm
> debating their assertion that code that doesn't throw away the high
> bits in the result of a 16x16 multiply when extending to 32 bits
> is incorrect and would fail acceptance testing.

Well, you're wrong.  In a C implementation with 16-bit "int"s, any
multiplication of two "int"s must, if it yields a result at all (which it may
not, if overflows are checked for), MUST yield a 16-bit result.  Sorry, but
that's the way it is.
	Guy Harris
	{ihnp4, decvax, seismo, decwrl, ...}!sun!guy
	guy@sun.com