GCC 64 bit arithmetic bugs?

Question about which tools to use, bugs, the best way to implement a function, etc should go here. Don't forget to see if your question is answered in the wiki first! When in doubt post here.
Post Reply
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

GCC 64 bit arithmetic bugs?

Post 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
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
User avatar
Pype.Clicker
Member
Member
Posts: 5964
Joined: Wed Oct 18, 2006 2:31 am
Location: In a galaxy, far, far away
Contact:

Re:GCC 64 bit arithmetic bugs?

Post 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.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re:GCC 64 bit arithmetic bugs?

Post 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
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
User avatar
Solar
Member
Member
Posts: 7635
Joined: Thu Nov 16, 2006 12:01 pm
Location: Germany
Contact:

Re:GCC 64 bit arithmetic bugs?

Post 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
Every good solution is obvious once you've found it.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re:GCC 64 bit arithmetic bugs?

Post 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
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
proxy

Re:GCC 64 bit arithmetic bugs?

Post 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
User avatar
Solar
Member
Member
Posts: 7635
Joined: Thu Nov 16, 2006 12:01 pm
Location: Germany
Contact:

Re:GCC 64 bit arithmetic bugs?

Post 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.
Every good solution is obvious once you've found it.
User avatar
Brendan
Member
Member
Posts: 8561
Joined: Sat Jan 15, 2005 12:00 am
Location: At his keyboard!
Contact:

Re:GCC 64 bit arithmetic bugs?

Post 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
For all things; perfection is, and will always remain, impossible to achieve in practice. However; by striving for perfection we create things that are as perfect as practically possible. Let the pursuit of perfection be our guide.
User avatar
Solar
Member
Member
Posts: 7635
Joined: Thu Nov 16, 2006 12:01 pm
Location: Germany
Contact:

Re:GCC 64 bit arithmetic bugs?

Post 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.
Every good solution is obvious once you've found it.
zyp

Re:GCC 64 bit arithmetic bugs?

Post 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.
User avatar
Candy
Member
Member
Posts: 3883
Joined: Tue Oct 17, 2006 11:33 pm
Location: Eindhoven

Re:GCC 64 bit arithmetic bugs?

Post 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.
Post Reply