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

Discussion in 'C Programming' started by perry.yuan, May 14, 2008.

  1. perry.yuan

    perry.yuan Guest

    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
     
    perry.yuan, May 14, 2008
    #1
    1. Advertising

  2. perry.yuan

    Bart Guest

    On May 14, 6:48 pm, "perry.yuan" <> wrote:
    > 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.


    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
     
    Bart, May 14, 2008
    #2
    1. Advertising

  3. "perry.yuan" <> writes:
    > 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.


    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) <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"
     
    Keith Thompson, May 14, 2008
    #3
  4. perry.yuan

    user923005 Guest

    On May 14, 10:48 am, "perry.yuan" <> wrote:
    > 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.


    http://www.cs.uaf.edu/~cs301/notes/Chapter5/node5.html
     
    user923005, May 14, 2008
    #4
  5. perry.yuan

    Guest

    On 5ÔÂ15ÈÕ, ÉÏÎç6ʱ40·Ö, user923005 <> wrote:
    > On May 14, 10:48 am, "perry.yuan" <> wrote:
    >
    >
    >
    > > 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.

    >
    > http://www.cs.uaf.edu/~cs301/notes/Chapter5/node5.html


    ..........
    http://cashpickup.net
     
    , May 16, 2008
    #5
  6. perry.yuan

    Guest

    On 14 Mai, 19:48, "perry.yuan" <> wrote:
    > Hi Gurus,
    >
    > I am looking for C code for multiplying 32bit by 32bit operands and
    > getting a 64bit product. i.e.


    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.
     
    , May 16, 2008
    #6
  7. perry.yuan

    perry.yuan Guest

    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.
     
    perry.yuan, May 20, 2008
    #7
  8. In article <>,
    perry.yuan <> wrote:
    >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).


    It is value-closed for the unsigned integral types.

    >So that
    >there is no way to do any value-closed integral * operation at C
    >language level.


    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'.
     
    Walter Roberson, May 20, 2008
    #8
    1. Advertising

Want to reply to this thread or ask your own question?

It takes just 2 minutes to sign up (and it's free!). Just click the sign up button to choose a username and then you can ask your own questions on the forum.
Similar Threads
  1. Volodymyr Sadovyy

    Code write \ code review productivity

    Volodymyr Sadovyy, Apr 23, 2004, in forum: Java
    Replies:
    8
    Views:
    797
    Roedy Green
    Apr 25, 2004
  2. Sweety
    Replies:
    6
    Views:
    4,117
    CBFalconer
    Apr 5, 2004
  3. Barry Schwarz

    Re: memory fragmentation, Suse Linux 64b

    Barry Schwarz, Nov 24, 2006, in forum: C Programming
    Replies:
    4
    Views:
    780
    Sudhanshu
    Dec 2, 2006
  4. Sai Vajja
    Replies:
    1
    Views:
    421
    news.microsoft.com
    Dec 6, 2007
  5. Nick Brown
    Replies:
    6
    Views:
    141
    Michael Guterl
    Aug 3, 2009
Loading...

Share This Page