Як змінна може бути не однаковою її власним значенням

Нещодавно мій друг показав мені помилку, яка проявляється в простій функції для обчислення поліноміальний хеш рядка з переповненням 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("%i\n", 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. Все-таки поліноміальні хеші варто писати основи великого простого числа. І порівняння буде працювати, і набагато складніше знайти рядки, які зламають Вашу функцію.
Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.