How to Write Code for 32b x 32b => 64b in C

Hi Gurus,

I am looking for C code for multiplying 32bit by 32bit operands and
getting a 64bit product. i.e.

U32 m1, m2;
U64 p = m1 * m2;

Of course I can use

U64 p = (U64) m1 * m2;

But, disassembly listing shows that generated code calls a 64bit x
64bit multiplication routine.

The target I am working on has a 32bit x 32 bit =64bit machine
instruction but doesn't have any 64bit x 64 bit instruction. Before I
wet my hand on assembly programming, I love to see any C code solution
to it.

TIA.

Perry Yuan

re: How to Write Code for 32b x 32b => 64b in C

On May 14, 6:48*pm, "perry.yuan" <perry.y...@gmail.comwrote:A general 32-bit multiply will yield a 64-bit result. If you don't
have any access to this in C then it will be awkward: you may have to
build from 16-bit multiplies.

Of course a 64-bit multiply will in general yield 128-bits which is
why you see that code.

Look more closely at what your compiler is capable of (which one is
it?), it seems unlikely the writers haven't thought this through
fully.


--
Bartc

re: How to Write Code for 32b x 32b => 64b in C

perry.yuan wrote:All you can do in C (or pretty much any non-assembly language)
is express your intent. It's then the implementation's job to
carry out your intent as efficiently as it can, which might not be
quite as efficiently as you would like.

But don't abandon all hope; there are at least two avenues
for further study:

1) Take a closer look at that multiplication subroutine; it
might be better than you fear. For example, the library might
have different versions tuned for different hardware, making a
run-time decision about which to use. It's possible that the
code you actually wind up running is not as bad as you suppose.

2) Study your compiler's documentation to see if there are
command-line flags or other switches that specialize the code
generation. The compiler may be generating code for a "least
common denominator" platform, avoiding instructions that are
available on only some models. If the compiler can be told that
you don't care about the less-endowed machines, it may generate
better code for the machines that interest you. (The code might
then not run at all on the other machines, but ...)

Finally, there may be other compilers you could use.

--
Eric.Sosman@sun.com

re: How to Write Code for 32b x 32b => 64b in C

"perry.yuan" <perry.yuan@gmail.comwrites:There is no direct way in C to specify a 32 x 32 =64 multiplication.
(For that matter, there's no guarantee that a given implementation has
32-bit and 64-bit types, but most do, apparently including yours.)

Assuming U32 and U64 are 32-bit and 64-bit unsigned integer types,
then this:

U64 p = (U64)m1 * m2;

specifies the following operations in the C abstract machine:

Convert the 32-bit value of m1 to 64 bits (because of the cast).
Convert the 32-bit value of m2 to 64 bits (promoted by "*").
Multiply the two 64-bit values, yielding a 64-bit result.
Initialize p, a 64-bit object, with that result.

If the compiler is clever enough to figure out that it can use the
32x32->64 multiplication instruction instead, it's free to perform
that optimization, as long as it can guarantee that it will yield the
same result in all possible cases (which I believe is the case here).

Take a look at your compiler's documentation, and try telling it to
generate optimized code. You might need to use some option to tell it
to generate code for a particular flavor of whatever CPU you're using.

There's no guarantee that this will work (as long as the generated
code gets the right answer, the standard doesn't care how it got it).

If that fails, you might consider writing a small assembly routine and
calling it from your C code, or perhaps using inline assembly. Both
methods are non-standard; if you have any questions, you'll need to
ask in a compiler-specific or platform-specific newsgroup. You'll
also be giving up some portability, which may or may not be a problem
for you.

--
Keith Thompson (The_Other_Keith) kst-u@mib.org <http://www.ghoti.net/~kst>
Nokia
"We must do something. This is something. Therefore, we must do this."
-- Antony Jay and Jonathan Lynn, "Yes Minister"

re: How to Write Code for 32b x 32b => 64b in C

On May 14, 10:48*am, "perry.yuan" <perry.y...@gmail.comwrote:http://www.cs.uaf.edu/~cs301/notes/Chapter5/node5.html

re: How to Write Code for 32b x 32b => 64b in C

On 5ÔÂ15ÈÕ, ÉÏÎç6ʱ40·Ö, user923005 <dcor...@connx.comwrote:..........
http://cashpickup.net

re: How to Write Code for 32b x 32b => 64b in C

On 14 Mai, 19:48, "perry.yuan" <perry.y...@gmail.comwrote:It might not be exactly what you were looking for, but
years ago I wrote a function to multiply two 64 bit
unsigned numbers based on 32 bit unsigned logic (the
type uinttype in the example below is 32 bit).
This function makes sense when absolutely no 64 bit
arithmetic is available:

#define LOWER_16(A) ((A) & 0177777L)
#define UPPER_16(A) (((A) >16) & 0177777L)
#define LOWER_32(A) ((A) & (uinttype) 037777777777L)

static void mult_64 (uinttype a_high, uinttype a_low,
uinttype b_high, uinttype b_low,
uinttype *c_high, uinttype *c_low)

{
uinttype a_low1;
uinttype a_low2;
uinttype b_low1;
uinttype b_low2;
uinttype c1;
uinttype c2;
uinttype c3;
uinttype c4;

/* mult_64 */
a_low1 = LOWER_16(a_low);
a_low2 = UPPER_16(a_low);
b_low1 = LOWER_16(b_low);
b_low2 = UPPER_16(b_low);
c1 = UPPER_16(a_low1 * b_low1);
c2 = a_low1 * b_low2;
c3 = a_low2 * b_low1;
c4 = UPPER_16(c1 + LOWER_16(c2) + LOWER_16(c3)) +
UPPER_16(c2) + UPPER_16(c3) +
a_low2 * b_low2;
*c_low = LOWER_32(a_low * b_low);
*c_high = LOWER_32(a_low * b_high + a_high * b_low + c4);
} /* mult_64 */

How I use this function as part of a random number
generator can be found in the file seed7/src/int_rtl.c
which is part of the Seed7 package.

Greetings Thomas Mertes

Seed7 Homepage: http://seed7.sourceforge.net
Seed7 - The extensible programming language: User defined statements
and operators, abstract data types, templates without special
syntax, OO with interfaces and multiple dispatch, statically typed,
interpreted or compiled, portable, runs under linux/unix/windows.

re: How to Write Code for 32b x 32b => 64b in C

Thanks for all replies and comments. My thinking is: in C language,
operator * for integral types is type-closed (i.e. int32 * int32 =>
int32) but not value-closed (i.e. int32 * int32 =int63). So that
there is no way to do any value-closed integral * operation at C
language level.

re: How to Write Code for 32b x 32b => 64b in C

In article <9303863a-44db-450c-b2d6-9f09497cd303@l17g2000pri.googlegroups.com>,
perry.yuan <perry.yuan@gmail.comwrote:It is value-closed for the unsigned integral types.
unsigned int R = (unsigned int) A * (unsigned int) B;

You may wish to interpret the result in terms of the original signs
of A and B. R would be interpreted as negative if ((A < 0) ^ (B < 0))
(That's exclusive OR that I used.) If R INT_MAX and should be
negative, or if R <= INT_MAX and should be positive, you have
quite straight-forward re-interpretations available, but if
R <= INT_MAX and should be negative or R INT_MAX and should be positive,
it is less clear what the signed equivilent of R should be.
--
'Roberson' is my family name; my given name is 'Walter'.