Page 1 of 1

GCC 64 bit arithmetic bugs?

Posted: Fri Apr 15, 2005 9:06 am
by Brendan
Hi,
Solar wrote: Should you happen to find that "bug" again, I'd like to hear about it.
Ok I was curious, so I decided to try a little test program. Basic test code is:

Code: Select all

int main(void) {
   int a = 1;
   int b = 5;
   long long int c;
   
   c = a * b;
   
   printf("Results from %d * %d:\n", a, b);
   printf("  As signed 64 bit decimal: %Ld\n", c);
   printf("  As unsigned 64 bit hex: 0x%016LX\n", c);
   printf("  Low dword in hex: 0x%08X\n", c);
   printf("  High dword in hex: 0x%08X\n", c >> 32);
   return 0;
}
And the test environment is:

[tt]bash-2.05b$ gcc --version
gcc (GCC) 3.3.5-20050130 (Gentoo Linux 3.3.5.20050130-r1, ssp-3.3.5.20050130-1, pie-8.7.7.1)

bash-2.05b$ cat /proc/version
Linux version 2.6.9-gentoo-r1 (root@grunt) (gcc version 3.3.4 20040623 (Gentoo Linux 3.3.4-r1, ssp-3.3.2-2, pie-8.7.6)) #7 SMP Wed Jan 12 20:09:39 CST 2005
[/tt]

I'm not sure what the difference is between "long long" and "long long int" but it doesn't seem to make a difference. I changed the values for both a and b to see how they effect the results. The results are as follows...

Test 1 - simple, everything correct

[tt]Results from 1 * 5:
As signed 64 bit decimal: 5
As unsigned 64 bit hex: 0x0000000000000005
Low dword in hex: 0x00000005
High dword in hex: 0x00000000[/tt]


Test 2 - 32 bit result, problem displaying 64 bit decimal only

[tt]Results from 1000000 * 500000:
As signed 64 bit decimal: 1783793664
As unsigned 64 bit hex: 0x000000006A528800
Low dword in hex: 0x6A528800
High dword in hex: 0x00000000[/tt]

Result should be 500000000000 or 0x000000006A528800


Test 3 - 64 bit result, everything wrong

[tt]Results from 1000000 * 2000000:
As signed 64 bit decimal: -1454759936
As unsigned 64 bit hex: 0xFFFFFFFFA94A2000
Low dword in hex: 0xA94A2000
High dword in hex: 0xFFFFFFFF[/tt]

Result should be 2000000000000 or 0x000001D1A94A2000


Test 4 - largest possbile (within range) inputs, everything wrong

[tt]Results from 2147483647 * 2147483647:
As signed 64 bit decimal: 1
As unsigned 64 bit hex: 0x0000000000000001
Low dword in hex: 0x00000001
High dword in hex: 0x00000000[/tt]

Result should be 4611686014132420609 or 0x3FFFFFFF00000001

Then I thought I'd try the following code instead:

Code: Select all

int main(void) {
   long long int c = 0x123456789ABCDEF0;

   printf("  As signed 64 bit decimal: %Ld\n", c);
   printf("  As unsigned 64 bit hex: 0x%016LX\n", c);
   printf("  Low dword in hex: 0x%08X\n", c);
   printf("  High dword in hex: 0x%08X\n", c >> 32);
   return 0;
}
This didn't compile properly ("warning: integer constant is too large for "long" type") so I figured I'd check with a "printf("Size %d\n", sizeof(c));" which reported that c was indeed an 8 byte variable.

I ignored the silly warning and the result was:

[tt] As signed 64 bit decimal: 1311768467463790320
As unsigned 64 bit hex: 0x123456789ABCDEF0
Low dword in hex: 0x9ABCDEF0
High dword in hex: 0x12345678[/tt]

Which is all entirely correct (even though it'd failed to print a 64 bit decimal number before)....

So, am I doing something wrong, or is GCC buggy?


Cheers,

Brendan

Re:GCC 64 bit arithmetic bugs?

Posted: Fri Apr 15, 2005 10:57 am
by Pype.Clicker
check out solar's last post. when operating on integers from different size, the compiler will attempt to give them all the size of the largest operand.

Your multiplication here only involve 32bit ints, so the computation is the same regardless of the size of the target (that cast occurs *after*)

try [tt]c = (long long)a * b;[/tt] instead.

Re:GCC 64 bit arithmetic bugs?

Posted: Fri Apr 15, 2005 11:43 am
by Brendan
Hi,
Pype.Clicker wrote: check out solar's last post. when operating on integers from different size, the compiler will attempt to give them all the size of the largest operand.

Your multiplication here only involve 32bit ints, so the computation is the same regardless of the size of the target (that cast occurs *after*)

try [tt]c = (long long)a * b;[/tt] instead.
Ok, that makes sense in a C sort of way (I'm too used to the "edx:eax = eax * X" Intel MUL and IMUL instructions ::)).

To be honest, I doubt I'll ever be able to consider this behaviour natural...


Thanks,

Brendan

Re:GCC 64 bit arithmetic bugs?

Posted: Fri Apr 15, 2005 12:45 pm
by Solar
Give the poor compiler a break. Given sufficiently complicated terms, it can become quite nontrivial to know the size of the "target" variable beforehand. And last time I looked, programming languages could get quite some flak for trying to be "too intelligent".

And then... you did compile all this with --std=c99, did you? Since before C99, there was no such thing as "long long" in the C standard, and who knows what the GNU people did while not tethered by a standard... :-D

Re:GCC 64 bit arithmetic bugs?

Posted: Fri Apr 15, 2005 1:44 pm
by Brendan
Hi,
Solar wrote:Give the poor compiler a break. Given sufficiently complicated terms, it can become quite nontrivial to know the size of the "target" variable beforehand. And last time I looked, programming languages could get quite some flak for trying to be "too intelligent".
I don't think it'd be much harder to extend the size of all values/variables involved to the size of the largest value/variable involved, rather than only extending the input values/variables to the size of the largest input value/variable.
Solar wrote:And then... you did compile all this with --std=c99, did you?
You've got to be joking, I used "gcc a.c" to compile... :)


Cheers,

Brendan

Re:GCC 64 bit arithmetic bugs?

Posted: Fri Apr 15, 2005 4:24 pm
by proxy
also to get rid of the warnings/errors about integer constants being too large you should append LL or ULL to the end of the constant like this:

Code: Select all

unsigned long long a = 0x100000000ULL;
also, there is no difference between "long long" and "long long int"..long long is effecitvly short hand for long long int.

finally, in c99 (which is the only time you can use long long) there are macros to aid in proper delcaration in <stdint.h>

for example:

Code: Select all

uint64_t a = UINT64_C(0x100000000);

these macros aren't avail in c++ unless you define __ STDC_CONSTANT_MACROS before including <stdint.h>

proxy

Re:GCC 64 bit arithmetic bugs?

Posted: Sun Apr 17, 2005 1:00 am
by Solar
Brendan wrote: I don't think it'd be much harder to extend the size of all values/variables involved to the size of the largest value/variable involved, rather than only extending the input values/variables to the size of the largest input value/variable.
Exactly that is what the compiler is doing - expanding the size of all values involved to the largest size involved. In C++, for example, you can define your own operator+() for a class, which receives two parameters - the one to the left of the '+' and the one to the right. The operator=() that afterwards assigns the result to another variable is not involved, and so cannot influence the result of operator+(). Although you can't overload operators in C, the reasoning is the same.

Re:GCC 64 bit arithmetic bugs?

Posted: Sun Apr 17, 2005 2:56 am
by Brendan
Hi,
Solar wrote: Exactly that is what the compiler is doing - expanding the size of all values involved to the largest size involved. In C++, for example, you can define your own operator+() for a class, which receives two parameters - the one to the left of the '+' and the one to the right. The operator=() that afterwards assigns the result to another variable is not involved, and so cannot influence the result of operator+(). Although you can't overload operators in C, the reasoning is the same.
All operators consist of a resulting value and the input values. If there was no result then there'd be no point doing the operation.

For example, consider "function(A + B)" where both A & B are obvious values and the value passed to the function is the third value.

Promoting all values to the size of the largest value (including the size of the result) would work well, even for complex calculations.

In the case of your C++ operator overloading, the compiler would need to promote values to the correct size before passing any of them to any operators.

An alternative would be strict type checking, where the multiplication I was trying to use would generate an "incompatible variable types in expression" error until I wrote "c = (long long)a * (long long)b;". I know C isn't meant to be this strict, but..

Now to annoy you properly, consider this code:

Code: Select all

int main(void) {
   char a = 100;
   char b = 100;
   int c;
   
   c = a * b;
   
   printf("%d\n", c);
   
   return 0;
}
For consistancy (according to the rules you've stated), this multiplication should be done as a signed 8 bit multiplication and overflow, giving a result that is always between +127 and -128. Unfortunately it behaves exactly how I was expecting "long long = int * int" to work, and gives a 32 bit result (10000).


Cheers,

Brendan

Re:GCC 64 bit arithmetic bugs?

Posted: Sun Apr 17, 2005 11:58 pm
by Solar
I admit you got me, there. I'll have to spend some time double-checking the standard, and the GCC results, but I'll figure this out.

Re:GCC 64 bit arithmetic bugs?

Posted: Mon Apr 18, 2005 9:46 am
by zyp
The reason for this is probably that when using a 32bit cpu, calculation on 32bit numbers is just as fast as 16bit or 8bit, so they are 32bit by standard, and then casted down.
Maybe on a 64bit machine you will get the same behaviour with 64bit numbers.
Unfortunately I don't have a 64bit-system, so I can't test this.

Edit: I managed to get shell access to a 64bit-system so I could test, but I just got the same results as Brendan.

Edit2: Looking at the assembly which gcc generates, imull (32bit multiplication) is used for every multiplication, even if both operands and result is 8bit. Only if one operand is 64bit imulq (64bit multiplication) is used.

Re:GCC 64 bit arithmetic bugs?

Posted: Mon Apr 18, 2005 11:08 am
by Candy
my guess on the standard is that it'll say that it's "undefined" what happens on an overflow of the type used for calculations. All you probably need to guarantee are the last X bits to be correct in the modulus case.