Недавно мой друг показал мне ошибку, которая проявляется в простой функции, вычисляющей полиномиальный хеш от строки с переполнением int'a. Она возвращала отрицательное число, хотя не должна была. Вот сама функция:
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;
}
На некоторых строках, в частности, на строке «bye», и только на сервере (что интересно, на своем компьютере все было в порядке) функция возвращала отрицательное число. Но как же так, ведь в случае, если число отрицательное, к нему прибавится MAX_INT и оно должно стать положительным.
Тут стоит посмотреть на различия сервера и локального компьютера: во-первых на локальном компьютере стояла OS X и использовался компилятор clang, тогда как на сервере стояла Gentoo с компилятором gcc, и во-вторых на сервере компиляция происходила с флагом -O2. Что же, давайте скомпилируем командой
g++ -O2 -S -masm=intel a.cppна стороне сервера и посмотрим ассемблерный код этой функции.
_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Как можно увидеть, никакого сравнения в ассемблерном коде после цикла нет. Получается, компилятор решил, что переменная, хранящая неотрицательное значение и которую только увеличивают, стать меньше нуля не может, и это правильно с точки зрения целочисленной арифметики, которую и реализует int. А это значит, что сравнение с нулём не нужно, и можно выполнить dead code elimination (удаление мертвого кода). Нас предупреждали, что переполнение int'а вызывает undefined behaviour.
А что если вывести, равна ли переменная её собственному значению?
printf("%in", h == -348700627);На выводе мы получим 0, а в ассемблерном коде будет:
xor edx, edx
mov esi, OFFSET FLAT:.LC0
mov edi, 1
xor eax, eax
call __printf_chkгде в регистре edx передается аргумент на вывод. Он равен нулю, никаких проверок не производится. Вообще логично, если число не меньше нуля, зачем сравнивать его с отрицательным. Таким образом, получается, что при переполнении могут не работать функции сравнения целых чисел, а переменная может быть не равной собственному значению! Но на то оно и undefined behaviour.
Давайте попробуем сравнить переменную с положительным числом. Конечно результат будет false, но интересно, будет ли компилятор делать реальную проверку? С помощью двоичного поиска было найдено, что компилятор делает реальную проверку только когда выполняется сравнение с числом 360662 и больше. Это число очень близко к 27752 * 13. Совпадение или нет? Не знаю.
Стоит еще сказать, что на OS X с оптимизацией -O2 таких ошибок не было замечено. Правда теперь использовался clang, а не gcc. В ассемблерном коде выполняется честная, хотя и магическая проверка:
## 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Таким образом, даже простое переполнение int'a может сделать код нерабочим и принести кучу проблем.
P.S. Все-таки полиномиальные хеши стоит писать по основанию большого простого числа. И сравнение будет работать, и гораздо сложнее найти строки, которые сломают Вашу функцию.
Автор: nikitaevg
