Продолжу рассказы о том, как программисты ходят по краю, даже не подозревая об этом. Поговорим об операциях сдвига <<, >>. Принципы работы операторов сдвига очевидны и многие программисты даже не знают, что их использование согласно стандарту Си/Си++ может приводить к неопределенному или к неуточненному поведению (undefined behaviour/unspecified behavior).
Предыдущие статьи доступны здесь: [1], [2].
Исторический экскурс
В начале немного истории. Необходимость операций сдвига битов очевидна любому программисту. Рано или поздно каждый сталкивается с необходимостью работать с отдельными битами и битовыми масками. Тем не менее, операции сдвига намного более популярны, чем должно были быть. Причина в том, что используя сдвиги можно умножать и делить числа на степень двойки. Например, операция «X << 3» умножит X на 8. Преимущество такого способа умножения и деления заключалось в скорости их работы в прошлом.
Сейчас я достал с пыльной полки книжку с описанием ассемблерных команд для процессоров, начиная с 8086 и кончая 80486. И нашёл таблицу о количестве тактов, необходимых для выполнения различных инструкций.
Умножение 16-битного регистра на ячейку памяти с использованием инструкции MUL на процессоре 8086 требует порядка 124-139 тактов!
Сдвиг 16-битного регистра на N позиций с использованием инструкции SHL на процессоре 8086 требует 8+4*N тактов. То есть в худшем случае получается 72 такта.
Можно было получить существенное ускорение при вычислении арифметических выражений используя различные трюки при работе с битовыми операциями. Это и стало причиной массового использования сдвигов, в начале, на языке ассемблер, потом в языках Си и Си++. Первые компиляторы Си/Си++ были просты. Человек мог получить выигрыш в скорости, явно подсказав компилятору, что здесь следует использовать сдвиг, а не инструкции умножения или деления.
С развитием процессоров польза от использования сдвигов долгое время сохранялась. В 80486 процессоре умножение стало занимать около 26 тактов. Вроде намного лучше. Однако сдвиг стал занимать всего 3 такта и вновь, был более привлекателен, чем умножение.
К счастью эти вынужденные оптимизации в большинстве своём канули в небытие. Во-первых, компиляторы стали умны и используют оптимальный набор инструкций для вычисления арифметических выражений. Во-вторых, процессоры также колоссально изменились. Появились конвейеры, предсказание переходов, переименование регистров и много чего ещё. Поэтому сказать, сколько времени займет выполнение той или иной инструкции обыкновенный программист уже не в состоянии. Но ясно, что если код местами будет не идеален, этого можно даже не заметить. Процессор разобьет инструкции на микроинструкции и начнет выполнять их параллельно. Если честно, то я уже не разбираюсь, как сейчас там всё происходит. Я понял, что разбираться в тонкостях бессмысленно, начиная с процессора Intel Pentium. И сделал вывод, что не стоит думать, что ты лучше знаешь, как нужно писать оптимизирующий код, использовать сдвиги и битовые операции, где только можно. Далеко не факт, что в результате код будет быстрее, чем сделает это оптимизатор в компиляторе. Зато точно можно сказать, что программа станет запутанной и сложной для понимания.
Примечание. Вышесказанное не значит, что использование битовых операций больше не может приносить выгоды. Есть много интересных и полезных трюков [3]. Главное не увлекаться.
Неопределенное поведение
Началось всё с того, что я решил увеличить в анализаторе PVS-Studio количество предупреждений связанных с undefined behaviour [4] и unspecified behavior [5]. Достаточно быстро и просто было реализовано правило, выявляющее некорректное использование операций сдвига. После этого мне пришлось остановиться и задуматься.
Оказалось, что программисты очень любят сдвиги. И используют их всевозможнейшим способом, приводящим часто с точки зрения стандарта к неопределенному поведению. Но одно дело теория, а другое практика. Есть ли смысл ругаться на код, который верой и правдой служил десятилетия и пережил уже не один компилятор? Сложный вопрос. Не смотря на то, что код некорректен, компиляторы следуют некому негласному соглашению и обрабатывают его единообразным способом.
После долгих раздумий, я всё-таки решил оставить данное диагностическое правило в PVS-Studio, не делая из него исключений. Если будет слишком много жалоб от пользователей, то возможно я изменю своё мнение. Впрочем, возможно пользователи удовлетворятся возможностью выключить эту диагностику или используют другие методы подавления предупреждений.
Кстати, именно эти душевные терзания и побудили меня написать статью. Надеюсь информация, которую я покажу, будет интересна и полезна.
Итак, посмотрим, что написано в стандарте C++11 по поводу операторов сдвига:
The shift operators << and >> group left-to-right.
shift-expression << additive-expression
shift-expression >> additive-expression
The operands shall be of integral or unscoped enumeration type and integral promotions are performed.
1. The type of the result is that of the promoted left operand. The behavior is undefined if the right operand is negative, or greater than or equal to the length in bits of the promoted left operand.
2. The value of E1 << E2 is E1 left-shifted E2 bit positions; vacated bits are zero-filled. If E1 has an unsigned type, the value of the result is E1 * 2^E2, reduced modulo one more than the maximum value representable in the result type. Otherwise, if E1 has a signed type and non-negative value, and E1*2^E2 is representable in the result type, then that is the resulting value; otherwise, the behavior is undefined.
3. The value of E1 >> E2 is E1 right-shifted E2 bit positions. If E1 has an unsigned type or if E1 has a signed type and a non-negative value, the value of the result is the integral part of the quotient of E1/2^E2. If E1 has a signed type and a negative value, the resulting value is implementation-defined.
Читать подобные тексты грустно и печально. Но не волнуйтесь. Сейчас мы рассмотрим различные некорректные ситуации на примерах.
Самый простой случай приводящий к неопределенному поведению, это когда правый операнд имеет отрицательное значение. Пример:
int A = 10; int B = A << -5;
Так, слава богу, никто не делает. По крайней мере, проанализировав более 70 open-source проектов, мы не встретили подобных ошибок.
Следующий случай гораздо интереснее. Это сдвиг на N бит, где N, большее, чем количество бит в левом операнде. Простейший пример:
int A = 10; int B = A << 100;
Посмотрим, как такая ошибка может выглядеть на практике. Следующий фрагмент кода был обнаружен нами в библиотеке Lib7z:
SZ_RESULT
SafeReadDirectUInt64(ISzInStream *inStream, UInt64 *value)
{
int i;
*value = 0;
for (i = 0; i < 8; i++)
{
Byte b;
RINOK(SafeReadDirectByte(inStream, &b));
*value |= ((UInt32)b << (8 * i));
}
return SZ_OK;
}
Диагностическое сообщение PVS-Studio: V610 Undefined behavior. Check the shift operator '<<. The right operand ('(8 * i)' = [0..56]) is greater than or equal to the length in bits of the promoted left operand. lib7z 7zin.c 233
Функция пытается побайтно прочитать 64-битное значение. К сожалению, у неё это не получится, если число было больше 0x00000000FFFFFFFF. Обратите внимание на сдвиг "(UInt32)b << (8 * i)". Размер левого операнда составляет 32 бита. При этом сдвиг происходит от 0 до 56 бит. На практике это приведёт к тому, что старшая часть 64-битного значения останется заполнена нулями. Теоретически здесь вообще имеет место неопределенное поведение и результат непредсказуем.
Корректный код должен выглядеть так:
*value |= ((UInt64)b << (8 * i));
У читателя может возникнуть вопрос, а корректен ли код приведенный ниже?
char A = 1; int B = A << 20;
Да, корректен. Слева от оператора << находится переменная A, состоящая только из 8 бит. Но перед началом операции сдвига, левая часть будет расширена до типа int. Соответственно, значение типа 'int' можно сдвинуть на 20 бит.
А теперь самый интересный момент. Это сдвиг отрицательных значений. Простейший пример:
int A = -1 << 5; // undefined behaviour int B = -1 >> 5; // unspecified behavior
В этом коде имеет место неопределённое и неуточненное поведение. С практической точки зрения разницы нет. Вывод один — так писать нельзя.
На этом можно было бы поставить точку и привести пару примеров. К сожалению, есть два нюанса, которые портят идеальную картину мира.
Нюансы, которые портят идеальную картину мира
Нюанс N1. В старом стандарте языка Си++ от 1998 года ситуации с неопределенным поведением обходятся стороной. Сказано, как ведет себя оператор << при сдвиге беззнаковых значений. А про знаковые значения ничего не сказано. В общем, тот самый случай, когда чтение стандарта не прибавляет ясности. Не рассматривается такой случай и всё.
Итак, с точки зрения Си++ от 1998 года, конструкция "-1 << 5" не приводит к неопределенному поведению. Впрочем, как она должна работать, тоже не описывается.
Нюанс N2. Программисты смело во многих программах сдвигают отрицательные значения. И спорить с ними будет сложно, ведь код работает.
Попробуем разобраться, следует ли из-за названных нюансов отказаться от новой диагностики. Мы думаем, что нет.
В старом стандарте Си++ и не сказано про неопределенное поведение. В новом сказано. Получается, что старый стандарт просто был недостаточно точен. Кстати, в новом стандарте языка Си (я смотрел черновик от 25 июня 2010), также сказано, что сдвиги отрицательных значений приводят к неопределенному поведению. Вывод — следует избавиться от некорректного кода.
Теперь по поводу повсеместного использования опасных сдвигов. Их действительно много. Например, в библиотеке JPEG необходимо заполнить массив следующими значениями:
11111111111111111111111111111111b 11111111111111111111111111111101b 11111111111111111111111111111001b 11111111111111111111111111110001b ...
Это записано так:
/* entry n is (-1 << n) + 1 */
static const int extend_offset[16] = { 0,
((-1)<<1) + 1, ((-1)<<2) + 1, ((-1)<<3) + 1,
((-1)<<4) + 1, ((-1)<<5) + 1, ((-1)<<6) + 1,
((-1)<<7) + 1, ((-1)<<8) + 1, ((-1)<<9) + 1,
((-1)<<10) + 1, ((-1)<<11) + 1, ((-1)<<12) + 1,
((-1)<<13) + 1, ((-1)<<14) + 1, ((-1)<<15) + 1
};
Сложно назвать библиотеку JPEG плохой. И этот код проверен временем и разными компиляторами.
С точки зрения стандарта его теперь следует переписать так:
static const int extend_offset[16] =
{ 0,
((~0u)<<1) | 1, ((~0u)<<2) | 1, ((~0u)<<3) | 1,
((~0u)<<4) | 1, ((~0u)<<5) | 1, ((~0u)<<6) | 1,
((~0u)<<7) | 1, ((~0u)<<8) | 1, ((~0u)<<9) | 1,
((~0u)<<10) | 1, ((~0u)<<11) | 1, ((~0u)<<12) | 1,
((~0u)<<13) | 1, ((~0u)<<14) | 1, ((~0u)<<15) | 1
};
Но стоит ли вносить такие правки решать вам. Я могу только дать совет всё-таки это сделать. Неизвестно когда и как, это может себя проявить.
Можно привести другие примеры сдвигов отрицательных значений в разных программах. Но они все однотипны, так что читать про них будет не интересно.
Выводы
- Раньше использование битовых операций и сдвигов было признаком мастерства программиста и позволяло писать быстрый код. Сейчас это почти не актуально. Намного важнее, чтобы код был понятным. Используйте игры с битами только в случае реальной необходимости.
- Выражения вида "-1 << N" теперь объявлены некорректными и производящими к неопределенному поведению.
- Выражения вида "-1 << N" давно и часто используются. Поэтому сложно привести реальные аргументы против использования таких конструкций. Аргументом являются только новые стандарты языков Си и Си++.
- Решайте сами, исправить сдвиг отрицательных значений или нет. Но я рекомендую исправить. Хотя бы на всякий случай.
- Диагностические сообщения, касающиеся опасных сдвигов будут доступны в PVS-Studio начиная с версии 4.60, которая скоро выйдет.
Дополнительные ресурсы
- Не зная брода, не лезь в воду. Часть первая. http://habrahabr.ru/post/137039/
- Не зная брода, не лезь в воду. Часть вторая. http://habrahabr.ru/post/137411/
- Sean Eron Anderson. Bit Twiddling Hacks. http://www.viva64.com/go.php?url=837
- Wikipedia. Неопределённое поведение. http://www.viva64.com/go.php?url=663
- Wikipedia. Неуточняемое поведение. http://www.viva64.com/go.php?url=738
- Алёна C++. Разница между unspecified behavior и undefined behavior. http://www.viva64.com/go.php?url=739
Автор: Andrey2008
