unsigned int multiply, x86-64

unsigned int multiply, x86-64

[Bob Plantz]

I wrote some C code to multiply two unsigned (32-bit) ints and store the
result in a 64-bit unsigned int.

int main(void)
{
   unsigned int x, y;
   unsigned long int z;

   printf("Enter two integers: ");
   scanf("%u %u", &x, &y);

   z = (long int)(x * y);
   
   printf("%u * %u = %lu\n", x , y, z);

   exit(0);
}

For the multiply, gcc produces (with -O0):
	movl	-4(%rbp), %edx
	movl	-8(%rbp), %eax
	imull	%edx, %eax
	mov	%eax, %eax
	movq	%rax, -16(%rbp)

First, it uses signed multiply (imull). Second, it only keeps the
low-order 32 bits of the result.

I would do something like:
        movl     -4(%rbp), %edx
        movl     -8(%rbp), %eax   # zeros high-order 32 bits
        mull     %edx                       # 64-bit result in edx:eax
        shlq     $32, %rdx             # shift to high-order
        addq     %rdx, %rax           # combine into 64-bit result
        movq     %rax, -16(%rbp)

Am I missing something here?

My "application" is that I'm writing a book and want to make sure I have
a clear understanding so I don't say stupid things.

-- Bob

Re: unsigned int multiply, x86-64

[Andrew Haley]

Bob Plantz wrote:
> I wrote some C code to multiply two unsigned (32-bit) ints and store the
> result in a 64-bit unsigned int.
> 
> int main(void)
> {
>    unsigned int x, y;
>    unsigned long int z;
> 
>    printf("Enter two integers: ");
>    scanf("%u %u", &x, &y);
> 
>    z = (long int)(x * y);
>    
>    printf("%u * %u = %lu\n", x , y, z);
> 
>    exit(0);
> }
> 
> For the multiply, gcc produces (with -O0):
> 	movl	-4(%rbp), %edx
> 	movl	-8(%rbp), %eax
> 	imull	%edx, %eax
> 	mov	%eax, %eax
> 	movq	%rax, -16(%rbp)
> 
> First, it uses signed multiply (imull). Second, it only keeps the
> low-order 32 bits of the result.
> 
> I would do something like:
>         movl     -4(%rbp), %edx
>         movl     -8(%rbp), %eax   # zeros high-order 32 bits
>         mull     %edx                       # 64-bit result in edx:eax
>         shlq     $32, %rdx             # shift to high-order
>         addq     %rdx, %rax           # combine into 64-bit result
>         movq     %rax, -16(%rbp)
> 
> Am I missing something here?

Knowledge of C, I think.

try

   z = (long int)x * y;

Andrew.

Re: unsigned int multiply, x86-64

[John Fine]

When x and y are both unsigned int (x*y) is also an unsigned int.
(long int)(x*y) means first compute the unsigned in (x*y) then promote 
it to long int.
To get the answer you want, you need to promote one of the arguments of 
the multiply before multiplying.  I don't know whether the optimizer 
will figure out to do the 32 bit multiply you want and store the 64 bit 
result or whether it would do a 64 bit multiply.
Also, are you sure (long int) is 64 bit?  I thought it was just 32.

Bob Plantz wrote:

>I wrote some C code to multiply two unsigned (32-bit) ints and store the
>result in a 64-bit unsigned int.
>
>int main(void)
>{
>   unsigned int x, y;
>   unsigned long int z;
>
>   printf("Enter two integers: ");
>   scanf("%u %u", &x, &y);
>
>   z = (long int)(x * y);
>   
>  
>

Re: unsigned int multiply, x86-64

[Bob Plantz]

On Tue, 2008-04-15 at 13:16 -0400, John Fine wrote:
> When x and y are both unsigned int (x*y) is also an unsigned int.
> (long int)(x*y) means first compute the unsigned in (x*y) then promote 
> it to long int.
> To get the answer you want, you need to promote one of the arguments of 
> the multiply before multiplying.  I don't know whether the optimizer 
> will figure out to do the 32 bit multiply you want and store the 64 bit 
> result or whether it would do a 64 bit multiply.

Thank you, John, for your remarks.

I knew about multiplying first, then the promotion, but it slipped my
mind. So I tried:
   unsigned int x;
   unsigned long int y;

   printf("Enter two integers: ");
   scanf("%u %lu", &x, &y);

   y = x * y;

In this case 32-bit * 64-bit -> 96-bit result. But the compiler does:
        movl    -4(%rbp), %eax     # load x
        mov     %eax, %edx             # promote to 64-bit (zeroes high
32 bits)
        movq    -16(%rbp), %rax   # load y (64-bit value)
        imulq   %rdx, %rax             # truncate high-order 32 bits of
result
        movq    %rax, -16(%rbp)

I've also tried using 64-bit for all the ints. Basically, if the result
is wider than the widest int in the multiplication, there is overflow.

My thought is that this is a place where assembly language is needed if
the high-order bits need to be preserved. At least one needs to check
the CF and OF. (They get set to one if there is signed multiply
overflow.)

I guess I need to look this up in the C standard. I suspect that it's
okay to ignore multiply overflow.

> Also, are you sure (long int) is 64 bit?  I thought it was just 32.

According to the ABI a long int in 32-bit mode is 32 bits, but in 64-bit
mode it is 64 bits. The code above verifies that a long int is 64 bits
in 64-bit mode.

I'm learning why converting to 64-bit is not as simple as I first
thought. :-)

-- Bob

Re: unsigned int multiply, x86-64

[Bob Plantz]

Andrew nailed it, and several others implied as much.

On Tue, 2008-04-15 at 18:10 +0100, Andrew Haley wrote:
> Bob Plantz wrote:

> > For the multiply, gcc produces (with -O0):
> > 	movl	-4(%rbp), %edx
> > 	movl	-8(%rbp), %eax
> > 	imull	%edx, %eax
> > 	mov	%eax, %eax
> > 	movq	%rax, -16(%rbp)

> > First, it uses signed multiply (imull). Second, it only keeps the
> > low-order 32 bits of the result.

> > Am I missing something here?
> 
> Knowledge of C, I think.

I finally did my homework -- looked it up in ISO/IEC 9899:TC3. Section
6.2.5 Types, #9 states: "A computation involving unsigned operands can
never overflow, because a result that cannot be represented by the
resulting unsigned integer type is reduced modulo the number that is one
greater than the largest value that can be represented by the resulting
type."

In other words, ignoring the possible high-order 32 bits in the 32-bit
multiplication above meets the standard. It is the responsibility of the
programmer to ensure that this never occurs.

I appreciate the comments and apologize for not doing my homework more
thoroughly before posting my question.

-- Bob

Re: unsigned int multiply, x86-64

[Andrew Haley]

Bob Plantz wrote:
> On Tue, 2008-04-15 at 13:16 -0400, John Fine wrote:
>> When x and y are both unsigned int (x*y) is also an unsigned int.
>> (long int)(x*y) means first compute the unsigned in (x*y) then promote 
>> it to long int.
>> To get the answer you want, you need to promote one of the arguments of 
>> the multiply before multiplying.  I don't know whether the optimizer 
>> will figure out to do the 32 bit multiply you want and store the 64 bit 
>> result or whether it would do a 64 bit multiply.
> 
> Thank you, John, for your remarks.
> 
> I knew about multiplying first, then the promotion, but it slipped my
> mind. So I tried:
>    unsigned int x;
>    unsigned long int y;
> 
>    printf("Enter two integers: ");
>    scanf("%u %lu", &x, &y);
> 
>    y = x * y;
> 
> In this case 32-bit * 64-bit -> 96-bit result. But the compiler does:
>         movl    -4(%rbp), %eax     # load x
>         mov     %eax, %edx             # promote to 64-bit (zeroes high
> 32 bits)
>         movq    -16(%rbp), %rax   # load y (64-bit value)
>         imulq   %rdx, %rax             # truncate high-order 32 bits of
> result
>         movq    %rax, -16(%rbp)
> 
> I've also tried using 64-bit for all the ints. Basically, if the result
> is wider than the widest int in the multiplication, there is overflow.
> 
> My thought is that this is a place where assembly language is needed if
> the high-order bits need to be preserved. At least one needs to check
> the CF and OF. (They get set to one if there is signed multiply
> overflow.)

  __uint128_t prod = (__uint128_t) x * y;

in asm:

   asm ("mulq %3" : "=a"(z1), "=d"(z2) : "a"(x), "r"(y));

Andrew.