[Из песочницы] Как переменная может быть не равной её собственному значению14.08.2016 15:33

Недавно мой друг показал мне ошибку, которая проявляется в простой функции, вычисляющей полиномиальный хеш от строки с переполнением 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. Все-таки полиномиальные хеши стоит писать по основанию большого простого числа. И сравнение будет работать, и гораздо сложнее найти строки, которые сломают Вашу функцию.

Комментарии (3)

  • 14 августа 2016 в 15:04

    +4

    ↑

    ↓

    Стоп-стоп-стоп. Переполнение int — это UB в C++. Собственно, все прочие рассуждения смысла не несут — достаточно знать Стандарт.

  • 14 августа 2016 в 15:16

    +1

    ↑

    ↓

    Рекомендую автору почитать http://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c, посчитать 27752 в 3 степени и понять, почему хэш от 2 букв считается нормально, а от 3х уже с какими-то странными результатами.

  • 14 августа 2016 в 15:29

    0

    ↑

    ↓

    Я попридираюсь к терминам, можно?:)
    В C++ переменная в принципе не может быть равна её значению, потому что в C++ вообще нельзя сравнивать переменные с чем бы то ни было, можно сравнивать только значения переменных. Но даже если взять язык, в котором можно (например, Common Lisp), то заголовок всё равно был бы не слишком осмысленным, т.к. переменная может быть равна своему значению только если значение этой переменной — сама эта переменная. Т.е., если выражаться терминами C++, если она — ссылка на саму себя, что в C++ сделать не позволит система типов.

© Habrahabr.ru