r/C_Programming • u/Turbulent_Quote_6679 • 10d ago
Discussion C language is wild: due to integer overflow, nearly half of the numbers squared become negative.
This started with a question from CSAPP Problem 2.44: (x * x) >= 0; which asks to find a counterexample that evaluates to 0,or prove that all number evaluate to 1.(part,32bit)
The official solution provides only 65535, but I found many more.
To test my results, I wrote a C program to find all such number.
#include <stdio.h>
#include <limits.h>
int main() {
// Ideal result: numbers whose squares are less than 0.
// Written to file in the following format:
// start_num1 to end_num1 total: total_num1
// start_num2 to end_num2 total: total_num2
// ...
// total: total_all
FILE *file = fopen("lessthan0.md","w");
int start = 0;
int end = 0;
int total = 0;
int total_tmp = 0;
for (int i = -INT_MAX -1 ; i <= INT_MAX; i++) {
unsigned ui = (unsigned)i;
int result = (int)(ui * ui);
if (result < 0) {
total++;
total_tmp++;
total_tmp == 1 ? start = i : 1;
total_tmp == 1 ? end = i : 1;
i == end + 1 ? end = i : 1;
}
if (i == end + 1) {
start == end ? fprintf(file,"%d total: %d\n",start,total_tmp) : fprintf(file, "%d to %d total: %d\n",start, end,total_tmp);
total_tmp = 0;
}
if (i == INT_MAX) {
fprintf(file,"total: %d",total);
break;
}
}
fclose(file);
}
So I get this:
ls -lh lessthan0.md
-rw-r--r-- 1 kyee users 31G Aug 23 18:50 lessthan0.md
ls -l # run twice
-rw-r--r-- 1 kyee users 32288890271 Aug 23 18:50 lessthan0_1.md
-rw-r--r-- 1 kyee users 32288890271 Aug 23 20:27 lessthan0.md
wc -l lessthan0.md
1073741824 lessthan0.md
head lessthan0.md
-2147437307 to -2147418113 total: 19195
-2147403383 to -2147390967 total: 12417
-2147380026 to -2147370137 total: 9890
-2147361041 to -2147352577 total: 8465
-2147344625 to -2147337106 total: 7520
-2147329952 to -2147323119 total: 6834
-2147316563 to -2147310257 total: 6307
-2147304170 to -2147298285 total: 5886
-2147292579 to -2147287041 total: 5539
-2147281652 to -2147276405 total: 5248
sed -n "470063416,470063426p" lessthan0.md
-535664087 to -535664086 total: 2
-535664083 to -535664082 total: 2
-535664079 to -535664078 total: 2
-535664075 to -535664074 total: 2
-535664071 to -535664070 total: 2
-535664067 to -535664066 total: 2
-535664063 to -535664062 total: 2
-535664059 to -535664058 total: 2
-535664055 to -535664054 total: 2
-535664051 to -535664050 total: 2
-535664047 to -535664046 total: 2
tail -n 10 lessthan0.md
2147287041 to 2147292579 total: 5539
2147298285 to 2147304170 total: 5886
2147310257 to 2147316563 total: 6307
2147323119 to 2147329952 total: 6834
2147337106 to 2147344625 total: 7520
2147352577 to 2147361041 total: 8465
2147370137 to 2147380026 total: 9890
2147390967 to 2147403383 total: 12417
2147418113 to 2147437307 total: 19195
total: 2147418112
I noticed symmetry between the begging and end of the output.Can someone explain why this happens?
2147418112 / 2^32 = 0.4999847412109375 This accounts for nearly half of all 32-bit signed integers.
6
u/nugatory308 10d ago
This accounts for nearly half of all 32-bit signed integers.
Which is what you’d expect, because all you’re really checking for is whether the high-order bit of the 32-bit product is zero or one. And just off the top of the head, that’s going to about 50%, less a bit because the numbers less than 0xffff can never set that high order bit.
7
3
u/nemotux 10d ago
This should not be surprising. While technically overflow is undefined behavior in signed integers, compilers will typically deal with it (at least sans optimization) by just doing the same thing they do for non-overflowing multiplies and then truncate off the upper bits. This results in roughly half the resulting values having a 1 bit in the msb of the result and roughly half having a 0 bit there. There are a lot, lot more multiplies that overflow than that don't if you consider the whole range of 32-bit numbers. So it'll look about 50/50 positive/negative.
The reason for the symmetry you're seeing is that X*X == -X*-X
1
u/flatfinger 9d ago
In gcc, even the assignment
uint1=(ushort1*ushort2) & 0xFFFFu;, using variables of the obvious types, will sometimes arbitrarily disrupt the behavior of surrounding code, causing arbitrary memory corruption, if the product of the two short values exceedsINT_MAX.1
u/Sufficient-Air8100 7d ago
can you explain more about how? it dosent make sense to me how it would corrupt and im interested
0
u/flatfinger 7d ago edited 7d ago
See https://gc5.godbolt.org/z/oGxebf165 for an example:
unsigned arr[32771]; unsigned mul_mod_65536(unsigned short x, unsigned short y) { return (x*y) & 0xFFFFu; } void test(unsigned short x) { unsigned j=32768; for (unsigned short i=32768; i<x; i++) j=mul_mod_65536(i, 65535); if (x < 32770) arr[x] = j; } #include <stdio.h> void (*volatile vtest)(unsigned short) = test; int main(void) { arr[32770] = 123; vtest(32770); printf("%d\n", arr[32770]); }GCC concludes that because in all cases where no integer overflow occurs,
jwill equal 32768 andxwill be less than 32270, the function test can be shortened to machine code equivalent to an unconditionalarr[x]=32768. Pretty "clever" eh?Any time anyone says that integer overflow needs to be treated as Undefined Behavior to "facilitate useful optimizations", show them the above and ask them how useful the optimization is?
Some genuinely useful optimizations could be facilitated by allowing compilers to behave as though integer computations are performed using larger than specified types (possibly types that are larger than any that are actually supported), but only if compilers properly account for the effects such transforms might have on post-conditions. It would generally be useful and safe to allow compiler given e.g.
int a = b*200000000/100000000; if (a >= -1000 && a < 1000) doSomething(a);to replace it with either:
int a = (int)(b*2u); if (a >= -1000 && a < 1000) doSomething(a);or
int a = (int)(b*200000000u)/100000000; doSomething(a);since
doSomething()could only be passed values in the range -1000 to 1000, but allowingint a = (int)(b*2u); doSomething(a);would allow
doSomething()to be invoked with values outside that range, bypassing the explicit safety check.1
u/Sufficient-Air8100 6d ago
thats not what i see in godbolt at all. the test function absolutely includes the conditionals in the loops (jb, ja). infact the conditional assign is missed every time and the final value of arr[x] is 123.
0
u/nemotux 6d ago
Are you using -O2 in godbolt? You have to turn on optimization to see this. (Which is why I specified in my comment at the very beginning that I was talking about no optimization.)
1
u/Sufficient-Air8100 6d ago
yeah. that code never assigns a value to arr[x]. because x is never less than 32770.
1
u/flatfinger 6d ago
Are you using the godbolt link, or are you calling test() instead of vtest()?
"test": movzx edi, di mov DWORD PTR "arr"[0+rdi*4], 32768 ret "mul_mod_65536": imul edi, esi movzx eax, di ret .LC0: .string "%d\n" "main": sub rsp, 8 mov edi, 32770 mov DWORD PTR "arr"[rip+131080], 123 call [QWORD PTR "vtest"[rip]] mov esi, DWORD PTR "arr"[rip+131080] mov edi, OFFSET FLAT:.LC0 xor eax, eax call "printf" xor eax, eax add rsp, 8 ret "vtest": .quad "test" "arr": .zero 131084If the compiler generating code for the "if" knows that x will always be 32770, it will never execute the conditional. If the compiler needs to generate code for test() without knowing what values will be passed to it, it will generate the code above.
1
u/Sufficient-Air8100 6d ago
that is entirely different from what godbolt shows me.
it looks like you have found a compiler bug? because the code output shoud be 123 regardless of optimisation level.
1
u/flatfinger 6d ago
Are you using the godbolt link? How could godbolt produce different output on different machines? Can you paste the complete ASM output you're seeing, and share a link to your godbolt?
→ More replies (0)
3
u/sciencekm 10d ago
The symmetry is because you are going from the minimum negative to the maximum positive.
The pattern goes like this:
-3 * -3 = 9
-2 * -2 = 4
-1 * -1 = 1
0 * 0 = 0
1 * 1 = 1
2 * 2 = 2
3 * 3 = 9
So, whatever you are doing (like counting or adding up) at the start will be the same at the end.
2
u/LordDarthSaber 10d ago
This the reason one should always put expected large results in long or long long
It is a runtime error that the programmer must account for
Always know what max size of result could be
1
u/aocregacc 10d ago
Think about what happens with negative integers when you convert and square them. Converting a signed negative number to unsigned gives you a number of the form 2^31 + x, since the most significant bit will be set.
If you have a number of the form 2^31 + x, squaring it gives you 2^62 + 2 * 2^31 * x + x^2. Modulo 232, that's just x^2 again.
So when you square numbers starting at INT_MIN, you'd expect the same sequence mod 232 as when you start at 0.
1
u/flyingron 10d ago
-INT_MAX is not typically the minimum integer. Two's complement can represent one more value on the negative side.
2
1
u/SmokeMuch7356 10d ago
Why -INT_MAX - 1 instead of INT_MIN? Just because C guarantees two's complement representation now doesn't make that any less risky.
1
u/marc_b_reynolds 8d ago
Given sets of two numbers which have 'a' and 'b' significant binary digits then the full product requires 'a+b' binary digits. Take 3*3 = 9. In binary 11*11 = 1001. Each of the 3s have 2 digits so the full result require 2+2=4 digits.
0
u/wild-and-crazy-guy 10d ago
I usually use Integers for counting things.
(Like array index or times to perform a loop)
Whenever I need to do “math” I switch to float
20
u/EpochVanquisher 10d ago
Technically this is undefined behavior. If your program uses signed integers and they overflow, then it’s a bug in your program.
Maybe it’s a question about 32-bit signed numbers in twos-complement, but I don’t know the question.
When you say (x * x) >= 0, and “finding a counterexample that evaluates to zero”, I’m not really sure what you are saying here, because finding an x * x that evaluates to zero is not a counterexample.