Как переменная может быть не равной её собственному значению

Недавно мой друг показал мне ошибку, которая проявляется в простой функции, вычисляющей полиномиальный хеш от строки с переполнением 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. Все-таки полиномиальные хеши стоит писать по основанию большого простого числа. И сравнение будет работать, и гораздо сложнее найти строки, которые сломают Вашу функцию.
AdBlock has stolen the banner, but banners are not teeth — they will be back

More
Ads

Comments 102

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

      Вот только "раньше работало же". Трюк-то популярный был...

      • UFO just landed and posted this here
        • UFO just landed and posted this here
          • UFO just landed and posted this here
            • UFO just landed and posted this here
              • UFO just landed and posted this here
                • UFO just landed and posted this here
                    +4
                    Откройте секрет — это какой социальный эксперимент или банальный бытовой хабраслив?
                    • UFO just landed and posted this here
        +3
        Автор просто описывает поведение компилятора при UB, причём несколько раз упоминая что там UB.
          +2
          Это совершенно бессмысленное занятие.

          Даже здесь в комментариях можно отследить, что такая подача информации формирует мнение о компиляторе что он «чудит». А компилятор работает в согласии со Стандартом, никаких чудес нет.

          Любая эксплуатация UB кроме его ликвидации — это хорошая такая мегатонна, заложенная под проект.
            –3

            Ну если компилятор это компилирует, да еще и делует это в согласии со Стандартом, то получается, что чудут стандарт.


            Если честно, у меня в голове не укладывается, как мог родиться, а тем более стать настолько популярным, язык с UB. Ведь само существование UB — это хорошая такая мегатонна, заложенная под все проекты на этом языке.

              +2

              А что, были какие‐либо другие альтернативы без UB, производительные и пригодные для написания кода для разных экзотических платформ с различными ограничениями? Тут всё просто: либо вы рисуете UB в стандарте, либо вы рисуете там «implementation‐defined», что не намного лучше: в случае с UB программист не знает, что там сделает компилятор, в случае с «implementation‐defined» программист не знает, что сделает компилятор на другой платформе, только, в отличие от оптимизаций на UB, это незнание вылезет только на той самой другой платформе. Либо вы рисуете в стандарте твёрдые гарантии определённого поведения и проседаете в производительности, иногда очень сильно.

                0
                Вот, например, статья, объясняющая:
                https://habrahabr.ru/post/230777/
                0
                Мне было интересно почитать статью, так что занятие смысл имеет. Люди могут программировать для развлечения, не отнимайте у них право обнаруживать и исследовать такие забавности.
              –4
              Я вот упорно не понимаю фанатов UB. Если у вас случился UB, то значит можно всё? Файлы с диска поудалять, процессы поубивать, ssh на внешний адрес отрыть? А что, неопределённое поведение — как хочу, так и насру?

              Гораздо логичнее в этом случае просто не компилироваться. Видишь UB — отказываешься компилироваться. И никаких подстав.
                –2
                Переполнение UB только для стандарта с/с++, для проца (асма) оно вовсе не UB, поэтому на использовании переполнения построены кучи алгоритмов, в т.ч. расчета хэшей, и данный пример не исключение, он тоже использует переполнение. h += h * 27752 + x[i]; дает переполнение неоднократно.
                  –3
                  Ну мы то имеем дело с c++, а не с процом(асмом). И если он не может справиться — то пусть честно отказывается компилироваться. Мозгов соптимизировать и выкинуть проверку у него хватает, а мозгов признаться в собственной ограниченности — нет.
                  +5
                  1. Компилятор залезть в голову к программисту не может. Некоторые UB случаются в зависимости от входных данных.

                  2. Не все случаи наличия UB можно логически доказать, имея только код программы.

                  3. Для выдачи предупреждений о возможном UB есть статические анализаторы, которые работают эвристически (делают вид, что они — ваш опытный коллега, который бедокод детектирует на уровне интуиции, потому как за свою карьеру видел километры мозговых извержений разной степени тяжести).

                  4. Принцип единой ответственности: задача компилятора — собрать программу, опираясь на стандарт языка; Искать потенциальные проблемы — не задача компилятора.

                  Поиск плохого кода — на статический анализатор. Поиск утечек памяти и прочего, что на статике не увидеть — на динамический анализатор.
                    +1
                    «Видишь UB — отказываешься компилироваться.»

                    С такой хотелкой, вам имеет смысл обратить более пристальное внимание на java. Там подход именно такой, что все должно быть 100% детерминированно, никаких UB не допускается.
                  +4
                  Рекомендую автору почитать http://stackoverflow.com/questions/16188263/is-signed-integer-overflow-still-undefined-behavior-in-c, посчитать 27752 в 3 степени и понять, почему хэш от 2 букв считается нормально, а от 3х уже с какими-то странными результатами.
                    +5
                    Я попридираюсь к терминам, можно?: )
                    В C++ переменная в принципе не может быть равна её значению, потому что в C++ вообще нельзя сравнивать переменные с чем бы то ни было, можно сравнивать только значения переменных. Но даже если взять язык, в котором можно (например, Common Lisp), то заголовок всё равно был бы не слишком осмысленным, т.к. переменная может быть равна своему значению только если значение этой переменной — сама эта переменная. Т.е., если выражаться терминами C++, если она — ссылка на саму себя, что в C++ сделать не позволит система типов.
                      +2
                      Указатель сам на себя считается?
                        0
                        Ответ naryl: Зависит от того считаете ли вы переменную и адрес памяти где лежит её значение одним и тем же. Если да — то считается. Проблема в том, что в *рантайме* C++ вообще нет понятия «переменная», а сравнение имеет смысл только в рантайме.
                      0

                      На самом деле, все беды лечатся грамотным code review, который приведенный выше код не должен проходить.

                        0

                        А ещё все люди должны быть добрыми и помогать друг другу.

                          –1
                          Code Review — не доброта и взаимопомощь?
                            +2

                            Где как, но мой комментарий не об этом. А о том, что в идеальном мире много что должно быть, в реальности бывает по-разному.

                          –1
                          На самом деле, было бы неплохо, если бы _вместо_ оптимизации, компилятор выдавал бы предупреждение, о том что у вас unused code.
                            +1

                            Будет куча false positive в кросс-платформенных библиотеках, где константные условия используются для выбора нужной реализации.

                              0
                              Константные условия это проверки с const или препроцессор? Компилятор сначала разворачивает препроцессор, сохраняя code map. И логично использовать для таких вещей препроцессор, чтобы в сборку точно попадал только код под нужную платформу. Неиспользуемый код есть неиспользуемый код.
                                +2

                                Не логично. Во‐первых, код с препроцессором может плохо выглядеть, в отличие от if (HAS_FEATURE) {}. Во‐вторых, иногда есть выбор между «использовать нельзя» (#define HAS_FEATURE 0), «использовать нужно, если включена настройка» (выбор поведения в runtime, #define HAS_FEATURE use_feature) и «использовать нужно всегда». Без использования «dead code elimination» (DCE) при постоянном условии такой тройной выбор будет выглядеть ужасно. В‐третьих, компилятор проводит некоторые проверки до оптимизаций, но исключённый препроцессором код не будет в них участвовать. А это удобно — узнавать, что вы написали «helpres» вместо «helpers» до того, как код дойдёт до CI.


                                В‐четвёртых, попробуйте засунуть #ifdef в функцию, которая сама определяется #define’ом. Если у вас есть «библиотека макросов», генерирующая вам функции, то исключать оттуда код можно только полагаясь на DCE. И нет, никаких шаблонов: я пишу на C. А оптимизации для C и C++ во многом пересекаются.

                          –6
                          > Как можно увидеть, никакого сравнения в ассемблерном коде после цикла нет. Получается, компилятор решил, что переменная, хранящая неотрицательное значение и которую только увеличивают, стать меньше нуля не может…

                          Я понимаю, что в стандарте UB, но кто оказался таким тупым, что не предусмотрел переполнения, и решил, что переменная только растет? То есть, половину дела он продумал, а половину нет?
                            0

                            На самом деле тут было вычисление по модулю 232. До того, как компиляторы "научились" использовать UB для оптимизации — для вычислений в кольце вычетов по такому модулю надо было всего лишь игнорировать переполнения.

                              0
                              Не во всех архитектурах целые числа образуют кольцо вычетов.

                              Это идёт с больших и суперкомпьютеров, где одно время была мода в ряде семейств вообще не реализовывать отдельное целочисленное АЛУ, а использовать в качестве целых чисел ненормализованные вещественные, с мантиссой в прямом коде.
                                0

                                Ну да, платформо-зависимый код, и что? Это, кстати, совершенно нормально для такой области как хеш-функции.

                                  0
                                  Так его и надо тогда оформлять, как платформо-зависимый, благо, в стандартах С и С++ предусмотрены для этого специальные типы.
                                    0

                                    Эти "специальные типы" нужны как раз для обеспечения платформо-независимости. Здесь же такая задача попросту не стояла, вот и все.

                                      0
                                      Ну так что тогда удивляться, что программа работает только на определённой платформе в определённом режиме компиляции?

                                      Если мне не изменяет память (а проверять лень), вопрос, растрогавший автора поста, исчерпывающе разобран в книге Меткалфа “Оптимизация в Фортране”, написанной ещё до рождения многих современных программистов.
                            • UFO just landed and posted this here
                                0

                                Есть. В Haskell по стандарту так же как в C: беззнаковые числа считаются по модулю, знаковые — UB. Но GHC гарантирует, что и в знаковом лучае будет вычисляться по модулю. Про другие компиляторы не знаю.

                              +13
                              Это лишь частный случай более общей оптимизации. На самом деле, оптимизатор подобным образом работает не только с переполнением, но и с любым другим UB. При принятии решений об оптимизации он исходит из того, что UB нигде нет. Если, например, в программе будет разыменование указателя, а где-нибудь ниже по коду этот же указатель будет проверяться на NULL, то оптимизатор уберёт проверку (и весь код, который должен быть выполнен в том случае, когда NULL), поскольку к этому моменту уже точно известно, что указатель не равен NULL. Ведь если бы был NULL, то выше по коду случилось бы UB… а такого не может быть, потому что программист не должен такого допускать.
                              +4
                              Даже в том случае, если проверка на отрицательность не выбрасывается компилятором, и даже если при этом при переполнении int код не вызывет UB, а ведет себя как простой битовый счетчик, есть шанс напороться на отрицательное число.

                              Дело в том, что в традиционной схеме представления отрицательных чисел:
                              MAX_VALUE = (2^n) -1
                              MIN_VALUE = -(2^n)

                              Если их сложить, получим -1.

                              Так же, рекомендую заглянуть в мою заметку (post/278329/) и в каменты к ней. Там подняты некоторые близкие вопросы багов, связанных с переполнением.
                                0
                                Я не специалист по с++, так что поправьте меня, пожалуйста, но разве в стандарте специфицирован размер int? Как в коде вообще могла оказаться захардкоженая константа максимального значения для int?
                                  –2

                                  Легко на x86, x86-64, arm5/7 размер int в gcc 4 байта.

                                    +2

                                    От того, что MAX_INT заменят на INT_MAX из limits.h (или что там у вас в C++ вместо этого, вроде какая‐то std:: шняга специальная есть вида std::numeric_limits<int>::max()) смысл статьи не изменится. Но на месте автора я бы всё же заменил.

                                      0
                                      Есть заголовочный файл climits, в нём есть константа INT_MAX. Судя по всему про этот файл автор тоже не знает.
                                      +19
                                      А можно было просто сделать int unsigned'om, выпилить проверку, и получить код, который абсолютно легален с точки зрения стандарта.
                                        0
                                        +1. Я тоже как-то пропустил момент, когда для исключительно положительных чисел взял обычный int.
                                          0
                                          взяли*
                                        +9
                                        >> Как переменная может быть не равной её собственному значению

                                        Отвечая на вопрос безотносительно статьи: запросто. NaN не равно самому себе.
                                          0
                                          А warning/hint компилятор на это дело выдает? Типа бесполезная проверка (h < 0), я её выкину вместе с кодом: h += MAX_INT;
                                            +2
                                            То, что видит оптимизатор, мало напоминает исходный код. Это может быть результат раскрытия макросов, специализации шаблонов, кучи inline подстановок, других проходов оптимизации. Возможно, в процессе оптимизации были применены знания о конкретной платформе, и тогда удаление кода условия — «компилятор молодец», а не «программист накосячил». А что если оптимизатор удаляет (после соответствующих подстановок) код проверки на необходимость роста вектора в подобном случае?

                                            std::vector<int> vec;
                                            vec.reserve(1024);
                                            for ( int i = 0; i < 600; i++ ){
                                                vec.push_back(i * i);
                                            }
                                            


                                            Для каких-то частных случаев сообщение может и выдается, но в общем случае оно будет бесполезным с кучей false positives.

                                            Информировать о таких вещах — задача все же для статического анализатора, там и работа идет с представлением гораздо ближе к исходному коду, и есть более внятный контроль за ложноположительными срабатываниями.
                                              –1
                                              Я вас понял, но ситуация все равно гнусная. Где-то в дебрях кода может проскочить «неудачный» тайпкаст к знаковому типу, а в итоге компилятор наворотит делов.
                                              Просто конкретно в этом моменте косяк хорошо видно, но зная злостный оптимизатор С++ считаю, что выдавать warning/hint в таких случаях жизненно необходимо.
                                            –4
                                            Компилятор с непривычки начудил, но я бы тоже удивился, увидев такую странную магию чисел в функции.
                                              +3
                                              Я что-то пропустил, и язык теперь гарантирует использование дополнительного кода для представления отрицательных чисел? Знаковый тип для контрольной суммы — это просто грубая ошибка.
                                                0

                                                Язык — нет, но платформа — да. На С++ иногда платформо-зависимый код пишут, и это нормально.

                                                  0
                                                  Для платформо-зависимого кода надо бы использовать платформо-зависимые типы.
                                                    +1

                                                    А int — он что — платформо‐независимый?

                                                      +1
                                                      Сам тип int — независимый (в отличие, скажем, от int32_t, гарантирующего реализацию именно только на платформах в дополнительном коде). Зависит от платформы только реализация int, на которую хорошая программа не должна завязываться.

                                                      А в данном случае надо использовать что-нибудь из серии uint32_t.
                                                        +1
                                                        У вас с оппонентом разное понимание термина платформо-независимый. У вас — реализующийся на всех платформах(т.е. базовый, обзательный к реализации для всех платформ и компиляторов языка). У аппонента — имеющий одинаковые параметры на всех платформах. Лично я больше привык ко второй трактовке.
                                                          0

                                                          И как это поможет? В момент приведения его к int (или int32_t) для борьбы с переполнением оптимизатор опять посчитает, что можно выкинуть мертвый код.

                                                            +2

                                                            @vadimr предложил uint32_t, а не int/int32_t. Никакого UB при переполнении здесь не будет. Даже если потом приводить результат к int (зачем?) и сравнивать с нулём, по стандарту это implementation‐defined, а не undefined behaviour и сравнение с нулём при приведении 32‐битного беззнакового целого к 32‐битному знаковому не выкинут (вот в случае uint16_t→int32_t выкинули бы, только не думаю, что кто‐то здесь будет считать, что это недопустимо).

                                                              0

                                                              Что здесь со ссылками на пользователей, на vadimr она то формируется, то нет?

                                                            0
                                                            1. int32_t по сравнению с int по стандарту гарантирует только размер контейнера.

                                                            Все целочисленные знаковые типы хранятся одинаково «в дополнительном коде». Платформно зависимо только наличие знака у нулевого значения, значения для неопределенности, и переполнений.
                                                            Открываем стандарт ISO C, смотрим, мотаем на ус…
                                                            H.2.2 Integer types
                                                            1 The signed C integer types int, long int, long long int, and the corresponding
                                                            unsigned types are compatible with LIA−1. If an implementation adds support for the
                                                            LIA−1 exceptional values ‘‘integer_overflow’’ and ‘‘undefined’’, then those types are
                                                            LIA−1 conformant types. C’s unsigned integer types are ‘‘modulo’’ in the LIA−1 sense
                                                            in that overflows or out-of-bounds results silently wrap. An implementation that defines
                                                            signed integer types as also being modulo need

                                                            6.2.6.2 Integer types
                                                            1 For unsigned integer types other than unsigned char, the bits of the object
                                                            representation shall be divided into two groups: value bits and padding bits (there need
                                                            not be any of the latter). If there are N value bits, each bit shall represent a different
                                                            power of 2 between 1 and 2N−1, so that objects of that type shall be capable of
                                                            representing values from 0 to 2N − 1 using a pure binary representation; this shall be
                                                            known as the value representation. The values of any padding bits are unspecified.53)
                                                            2 For signed integer types, the bits of the object representation shall be divided into three
                                                            groups: value bits, padding bits, and the sign bit. There need not be any padding bits;
                                                            signed char shall not have any padding bits. There shall be exactly one sign bit.
                                                            Each bit that is a value bit shall have the same value as the same bit in the object
                                                            representation of the corresponding unsigned type (if there are M value bits in the signed
                                                            type and N in the unsigned type, then M ≤ N). If the sign bit is zero, it shall not affect the resulting value. If the sign bit is one, the value shall be modified in one of the
                                                            following ways:
                                                            — the corresponding value with sign bit 0 is negated (sign and magnitude);
                                                            — the sign bit has the value −(2M) (two’s complement);
                                                            — the sign bit has the value −(2M − 1) (ones’ complement).
                                                            Which of these applies is implementation-defined, as is whether the value with sign bit 1
                                                            and all value bits zero (for the first two), or with sign bit and all value bits 1 (for ones’
                                                            complement), is a trap representation or a normal value. In the case of sign and
                                                            magnitude and ones’ complement, if this representation is a normal value it is called a
                                                            negative zero.
                                                              +2
                                                              Вообще-то в вашей цитате ясным английским языком написано, что отрицательные числа могут представляться в прямом, обратном или дополнительном коде, в зависимости от реализации.
                                                                0
                                                                Все целочисленные знаковые типы хранятся одинаково «в дополнительном коде». Платформно зависимо только наличие знака у нулевого значения

                                                                В дополнительном коде не бывает знака у нулевого значения

                                                                  0
                                                                  Я поэтому и взял в кавычки, т.к. в дополнительном коде и паддинга не бывает, а видимо на некоторых архитектурах он есть…
                                                                  Тут речь шла о том, что нету разницы между int32_t etc и int кроме размера контейнера.
                                                                    0
                                                                    Разница есть. В соответствии с IEEE Std 1003.1, тип int32_t не должен быть определён, если представление отрицательных целых чисел отлично от дополнительного кода. В отличие от типа int, определённого на всех платформах.
                                                                      0
                                                                      IEEE Std 1003.1 Это POSIX стандарт, а не стандарт на C.
                                                                        0
                                                                        Тут дополнительно нужно уточнять, какого года IEEE Std 1003.1 вы имеете в виду?

                                                                        Поскольку первые ревизии стандартов IEEE Std 1003.1 включали частично стандарты ANSI C, которые давно устарели.

                                                                        В данный момент все IEEE Std 1003.xx устарели и нужно использовать ISO/IEC/IEEE 9945:2009/Cor 1:2013
                                                                          0
                                                                          IEEE Std 1003.1-2008/Cor 1-2013;
                                                                            0
                                                                            IEEE Std 1003.1-2008/Cor 1-2013:

                                                                            The typedef name int N _t designates a signed integer type with width N, no padding bits, and a two's-complement representation.

                                                                            Разумеется, это вопрос POSIX, а не стандарта языка, как и вообще все вопросы внутренней реализации libc.
                                                                              0

                                                                              POSIX — лишь одно из семейств платформ

                                                                                0
                                                                                Конечно.
                                                                          0
                                                                          Не совсем так. Для POSIX наличие целочисленных типов intXX_t и uintXX_t с заданными размерами контейнеров 8,16,32 bit обязательно (знаковые обязаны быть в дополнительном коде) «required». 64 bit требуется, если правильно реализован. Все это описано как расширение ISO C.
                                                          –6

                                                          -fno-strict-overflow для GCC выключает эту херню в оптимизаторе

                                                            +6
                                                            Это в коде херня, и это её надо убирать куда-нибудь подальше, а не выключать оптимизации в компиляторе.
                                                              +1

                                                              Тем не менее, идея отключить UB при целочисленном знаковом переполнении в одном из модулей (не во всех!), где собраны функции, производящие вычисления в кольце вычетов по модулю 2^32 или 2:64 — довольно здравая.

                                                                +2
                                                                Зачем? Используете unsigned int — и всё будет работать, как и должно работать.
                                                                  0

                                                                  Иногда знаковый тип требуется на выходе… и не всегда отрицательное значение является ошибкой. Приведение же к типу int с переполнением также даст UB, ЕМНИП.

                                                                    0
                                                                    Приведение же к типу int с переполнением также даст UB.

                                                                    В C++ можно использовать reinterpret_cast чтобы получить implementation-defined behavior вместо UB. В C, по-идее, можно добиться того же через указатели или union.

                                                                    0
                                                                    Это не так, работать будет, но не как Должно.
                                                                    1. Начнем с того что x[i] это char, а он уже знаковый тип.
                                                                    2. Далее для в исходном коде константа 27752 а не 27753 как в дизассемблированом. Оба числа не простые, а ближайшее простое 27751.
                                                                    3. Первый цикл несет абсолютно бессмысленную с точки зрения хэширования операцию 13*27752+x[i] видимо ее добавили для компенсации переполнения на второй итерации.
                                                                    4. Размер константы 27752 или 27753 на 7 бит больше чем нужно для хэширования, что ведет к большому числу лишних коллизий.
                                                                    Чтобы работало, как «Должно» нужно привести x[i] к целочисленному типу, далее умножать на максимальное простое число для представления которого достаточно unsigned char или на бит больше (253 или 257 в зависимости от окраски входных данных), для h нужно применить целочисленный тип, которого гарантировано достаточно для хранения результата без переполнения, h нужно инициализировать 0. Потом можно взять результат по модулю 2N где N необходимый порядок выходных слотов или по модулю ближайшего простого числа соответствующему числу выходных слотов хэш функции. Иначе будут лишние неравномерные коллизии.
                                                                    Еще лучше, конечно, применить стандартные HASH функции выведенные лучшими собаководами.
                                                                      0

                                                                      Если брать результат по модулю 2N — то переполнение при вычислении h допустимо.

                                                                        +3

                                                                        По стандарту char не знаковый, а implementation‐defined. Символы из “basic execution character set” гарантированно неотрицательны (C99, в стандарте C++11 я такого заявления не нашёл). Однозначно знаковым является signed char, однозначно беззнаковым unsigned char, а сам char вообще не принадлежит ни одному из классов целочисленных типов, описанных в документации.

                                                                    0

                                                                    Скажите это разработчикам glibc или gnump, всяких кодеков, например. Да на самом деле дофига реально существующих библиотек использует хоть где-то в коде подобные уловки.

                                                                    +1
                                                                    Проблема приведенного исходного кода от этого никуда не девается.
                                                                    Нужно использовать без знаковый тип это раз.
                                                                    Кроме того затычка с проверкой знака, будучи не выкинутой компилятором, увеличивает число коллизий данного хэша в два раза для определенного множества входных строк (или окрашивает спектр для любого множества случайных входных значений, кому так понятнее).
                                                                      0

                                                                      Можно не цепляться за этот конкретный код, так как он всего лишь демонстрирует общую проблему с default установками оптимизации в последних версиях GCC. Эта оптимизация вступает в противоречие с приемами, которые по сути являются общей практикой для многих библиотек, где много работы с числами (например, вычисления с числами высокой разрядности, криптография, кодеки). Эта оптимизация помогает в редких случаях, но может испортить работу древнего хардкорного кода, который создавали, отлаживали и оптимизировали годами. Не понимаю, нафига они врубили ее именно по умолчанию.

                                                                        0
                                                                        Есть стандарт имплементации языка, если его за годы не прочитали, то это странно.
                                                                        Посыл про то, что эта оптимизация не нужна тоже мягко говоря странный.
                                                                        Если программист собирает свои программы с опциями оптимизации, то он должен понимать, что делает и стоит посмотреть, что они подразумевают.
                                                                        Если он использует новую версию компилятора, то заглянуть в changelog тоже стоит.
                                                                        Мне вот например не понятно почему для gcc не включена по умолчанию -Wconversion -Wbad-function-cast -Wcast-qual
                                                                    0
                                                                    Стоит еще сказать, что на OS X с оптимизацией -O2 таких ошибок не было замечено.

                                                                    Просто повесьте рядом с компьютером с OS X зеркало и посмотрите в него — тогда вы может быть всё-таки заметите ошибку (причём независимо от уровня оптимизации).

                                                                      0
                                                                      Я благодарен автору статьи хотя бы за то, что из комментария выше узнал про отношение оптимизаций и UB при компиляции кода.

                                                                      P.S.: Исходя из названия, кстати, ожидал увидеть что-нибудь про адреса объектов при множественном наследовании (вроде этого).
                                                                        0

                                                                        del

                                                                          0
                                                                          Чтобы наверняка работало надо заменить
                                                                          if (h < 0) h += MAX_INT;
                                                                          на
                                                                          if (h < 0) h ^= 0x80000000;
                                                                          т.е. смена старшего разряда (там знак) с 1 на 0. Так число гарантированно станет положительным. Можно использовать маску 0xFFFFFFFF, это будет равносильно h = -h-1
                                                                            0

                                                                            Это все мертвому припарки до тех пор пока оптимизатор считает условие (h < 0) всегда ложным.

                                                                              0
                                                                              Тогда вообще без if()
                                                                              h &= 0x7FFFFFFF;
                                                                            +5
                                                                            Стоит еще добавить, что std::string — состоит из char, а char может быть как знаковым, так и беззнаковым на разных платформах.
                                                                            И раз уж вы используете C++, то используйте std::numeric_limits.
                                                                            Иначе ваши возмущения по поводу того, что в разных местах у вас работает по-разному выдает в вас новичка.
                                                                              +6
                                                                              В ассемблерном коде выполняется честная, хотя и магическая проверка

                                                                              sar eax, 31 # some magic check
                                                                              and eax, dword ptr [rip + _MAX_INT] # yet another magic
                                                                              add eax, edx


                                                                              Эх молодежь…
                                                                              Вобщем-то простейшая оптимизация.
                                                                              Как это работает:
                                                                              команда «sar» это арифметический сдвиг вправо (Shift ArithmeticRight).
                                                                              При сдвиге регистра вправо нужно придумать что положить в самый старший бит (влево тоже, но сейчас не об этом).
                                                                              Есть несколько стандартных вариантов (класть 0, размножать старший бит, класть то что было в младшем и т.п.). В данном случае делается размножение старшего бита, напирмер (сократим до 8 бит для наглядности):
                                                                              10001100 -> sar r,1 -> 11000110
                                                                              00001100 -> sar r,1 -> 00000110
                                                                              такой сдвиг сохраняет знак числа и примерно соответствует операции деления целого числа на 2 (поэтому он и называется арифметическим).
                                                                              Особо интересными случаями являются применение этой операции к единице и минус единице:
                                                                              1 (00000001) -> sar r,1 -> 0 (00000000)
                                                                              -1 (11111111) -> sar r,1 -> -1 (11111111)

                                                                              т.е. если применить эту опреацию много-много раз к положительному числу, мы получим 0, а если к отрицательному то -1 (11111111).
                                                                              Собственно это здесь и делается: в результате арифметического сдвига вправо на 32 бита в eax будет 0, если исодное значение было положительным, или 0xffffff если отрицательным.
                                                                              Соответственно вторая строчка — операция and с константой MAX_INT. т.к. в eax у нас возможны только 0 и 0xffffffff, результатом этого and будет либо 0, либо MAX_INT (в зависимости от знака исходного значения).
                                                                              Ну и последней строчкой добавляем это значение к результату функции.
                                                                              В терминах C это можно переписать так:
                                                                              h += h>=0 ? MAX_INT : 0;
                                                                              


                                                                              Зачем это надо:
                                                                              Современные процессоры очень не любят команды условных переходов. Такая оптимизация позволяет сделать эквивалентный код без переходов.
                                                                                0
                                                                                Спасибо за такое подробное разъяснение.
                                                                                  +1
                                                                                  Собственно это здесь и делается: в результате арифметического сдвига вправо на 32 бита в eax будет 0, если исодное значение было положительным, или 0xffffff если отрицательным.

                                                                                  Поправка: сдвиг на 31 бит, а не на 32. Сдвиг на 32 бита не изменит число, потому что используются только младшие 5 бит операнда.

                                                                                    0
                                                                                    да, согласен, 31. есть еще несколько ошибок в тексте… (условие в C-ном выражении противоположное написал), но когда заметил редактировать уже не давало. Но так можт и лучше — видно что кто-то прочитал. :)

                                                                                Only users with full accounts can post comments. Log in, please.