How a variable may not equal its own value.

Recently, my friend showed me an error that manifests itself in a simple function that calculates a polynomial hash from a string with an overflow of int'a. She returned a negative number, although she shouldn’t. Here is the function itself:

unsigned MAX_INT = 2147483647; int hash_code(std::string x) { int h = 13; for (unsigned i = 0; i < 3; i++) { h += h * 27752 + x[i]; } if (h < 0) h += MAX_INT; return h; } 

On some lines, in particular, on the “bye” line, and only on the server (which is interesting, everything was fine on your computer) the function returned a negative number. But how is this, because if the number is negative, MAX_INT will be added to it and it should become positive.

Here it is worth looking at the differences between the server and the local computer: first, OS X was on the local computer and the clang compiler was used, whereas Gentoo was on the server with the gcc compiler, and secondly, the server compiled with the -O2 flag. Well, let's compile with the command

 g++ -O2 -S -masm=intel a.cpp 

on the server side and see the assembler code of this function.
')

 _Z9hash_codeNSt7__cxx1112basic_stringIcSt11char_traitsIcESaIcEEE: .LFB661: .cfi_startproc mov rdx, QWORD PTR [rdi] mov eax, 13 lea rsi, [rdx+3] .L2: # begin of the cycle movsx ecx, BYTE PTR [rdx] add rdx, 1 imul eax, eax, 27753 add eax, ecx cmp rsi, rdx jne .L2 # end of the cycle rep ret # returning the value right away 

As you can see, there is no comparison in the assembler code after the loop. It turns out that the compiler decided that a variable storing a non-negative value and which is only incremented cannot become less than zero, and this is correct from the point of view of integer arithmetic, which int implements. This means that a comparison with zero is not necessary, and you can perform dead code elimination (removal of a dead code). We were warned that int overflow caused undefined behavior.

And what if we derive, is the variable equal to its own value?

 printf("%i\n", h == -348700627); 

In the output we get 0, and in the assembler code will be:

  xor edx, edx mov esi, OFFSET FLAT:.LC0 mov edi, 1 xor eax, eax call __printf_chk 

where in the edx register the argument is passed to the output. It is zero, no checks are performed. It is generally logical, if the number is not less than zero, why compare it with a negative one. Thus, it turns out that when overflowing, the function of comparing integers may not work, and the variable may not be equal to its own value! But then it is undefined behavior.

Let's try to compare a variable with a positive number. Of course, the result will be false, but I wonder if the compiler will do a real check? Using a binary search, it was found that the compiler does a real check only when comparing with the number 360662 and more. This number is very close to 27752 * 13. Coincidence or not? I do not know.

It is also worth saying that on OS X with optimization of -O2 such errors were not noticed. The truth is now used clang, not gcc. The assembly code performs an honest, albeit a magical check:

 ## BB#1: shr eax, 8 movsx eax, al movsx ecx, byte ptr [rdi + 2] inc rdi jmp LBB0_3 LBB0_2: mov rdi, qword ptr [rdi + 16] movsx eax, byte ptr [rdi] movsx ecx, byte ptr [rdi + 1] LBB0_3: imul eax, eax, 27753 lea eax, [rax + rcx + 1423042525] movsx ecx, byte ptr [rdi + 2] imul edx, eax, 27753 add edx, ecx mov eax, edx sar eax, 31 # some magic check and eax, dword ptr [rip + _MAX_INT] # yet another magic add eax, edx pop rbp ret 

Thus, even a simple int'a overflow can make the code inoperative and bring a lot of problems.

PS Still, polynomial hashes should be written on the basis of a large prime number. And the comparison will work, and it is much more difficult to find lines that break your function.