Это маскировка перед беззнаковый сдвиг влево на C/С++ тоже параноик?
этот вопрос мотивирован тем, что я реализую криптографические алгоритмы (например, SHA-1) на C / C++, пишу портативный платформенный агностический код и тщательно избегаю неопределенное поведение.
предположим, что стандартизированный криптографический алгоритм просит вас реализовать это:
b = (a << 31) & 0xFFFFFFFF
здесь a и b являются беззнаковыми 32-разрядными целыми числами. Обратите внимание, что в результате мы отбрасываем любые биты выше наименее значимых 32 биты.
в качестве первого наивного приближения мы могли бы предположить, что int имеет ширину 32 бита на большинстве платформ, поэтому мы бы написали:
unsigned int a = (...);
unsigned int b = a << 31;
мы знаем, что этот код не будет работать везде, потому что int имеет ширину 16 бит на некоторых системах, 64 бит на других и, возможно, даже 36 бит. Но с помощью stdint.h, мы можем улучшить этот код uint32_t тип:
uint32_t a = (...);
uint32_t b = a << 31;
Итак, мы закончили, верно? Вот что я думал в течение многих лет. ... Не совсем. Предполагать что на определенной платформе, мы имеем:
// stdint.h
typedef unsigned short uint32_t;
правило для выполнения арифметических операций в C / C++ заключается в том, что если тип (например,short) меньше, чем int, затем он расширяется до int если все значения могут поместиться, или unsigned int в противном случае.
допустим, что компилятор определяет short как 32 бита (со знаком) и int как 48 бит (подпись). Затем эти строки кода:
uint32_t a = (...);
uint32_t b = a << 31;
будет фактически означать:
unsigned short a = (...);
unsigned short b = (unsigned short)((int)a << 31);
Примечание. это a превращается в int потому что все ushort (т. е. uint32) вписывается в int (т. е. int48).
но теперь у нас проблема: сдвиг ненулевых битов влево в знаковый бит целочисленного типа со знаком является неопределенным поведением. Эта проблема возникла потому, что наш uint32 был произведен в int48 - вместо того, чтобы быть повышен до uint48 (где левый сдвиг будет в порядке).
вот мои вопросы:
правильно ли я рассуждаю, и является ли это законной проблемой в теории?
можно ли эту проблему игнорировать, потому что на каждой платформе следующий целочисленный тип удваивает ширину?
хорошая ли идея правильно защититься от этой патологической ситуации, предварительно замаскировав вход таким образом?:
b = (a & 1) << 31;. (Это обязательно будет правильно на каждой платформе. Но это может сделать скорость критической крипто алгоритм медленнее, чем это необходимо.)
разъяснения/изменения:
я принимаю ответы на C или C++ или оба. Я хочу знать ответ хотя бы на один из языков.
логика предварительного маскирования может повредить вращение бита. Например, GCC будет компилировать
b = (a << 31) | (a >> 1);к 32-разрядной инструкции битового вращения на языке ассемблера. Но если предварительно замаскировать сдвиг влево, то вполне возможно, что новой логики нет переводится в бит вращения, что означает теперь 4 операции выполняются вместо 1.
5 ответов:
говоря о с-стороне проблемы,
- правильно ли я рассуждаю, и является ли это законной проблемой в теории?
это проблема, которую я не рассматривал раньше, но я согласен с вашим анализом. C определяет поведение
<<оператор в терминах типа произведен левый операнд, и это возможно, что целочисленные акции приводят к тому, что они (подписаны)intкогда исходный тип этого операнда -uint32_t. Я не ожидаю увидеть это на практике на любой современной машине, но я все для программирования по фактическому стандарту, в отличие от моих личных ожиданий.
- можно ли эту проблему игнорировать, потому что на каждой платформе следующий целочисленный тип удваивает ширину?
C не требует такого отношения между целочисленными типами,хотя на практике это повсеместно. Если вы не однако, решив полагаться только на стандарт, то есть, если вы прилагаете усилия для написания строго соответствующего кода, Вы не можете полагаться на такие отношения.
- является ли хорошей идеей правильно защититься от этой патологической ситуации, предварительно замаскировав вход таким образом?: b = (a & 1)
тип
unsigned longгарантированно имеет не менее 32 бит значения, и он не подлежит продвижению к любому другому типу в рамках целочисленных акций. На многих популярных платформ, он имеет точно такое же представление, какuint32_t, и может быть даже того же типа. Таким образом, я был бы склонен написать выражение следующим образом:uint32_t a = (...); uint32_t b = (unsigned long) a << 31;или, если вам нужно
aтолько в качестве промежуточного значения при вычисленииb, затем объявите его какunsigned longto начинаться.
Q1: Маскировка до сдвиг предотвращает неопределенное поведение, которое имеет отношение к OP.
Q2:"... потому что на каждой платформе следующий целочисленный тип удваивает ширину?" --> нет. "Следующий" целочисленный тип может быть меньше 2x или даже того же размера.
следующее хорошо определено для всех совместимых компиляторов C, которые имеют
uint32_t.uint32_t a; uint32_t b = (a & 1) << 31;Вопрос 3:
uint32_t a; uint32_t b = (a & 1) << 31;не ожидается, что код, который выполняет маску-он не нужен в исполняемый файл-только в исходнике. Если маска действительно возникает, получить лучший компилятор должен быть проблемой.как предложил, лучше подчеркнуть беззнаковость с этими сдвигами.
uint32_t b = (a & 1U) << 31;
@John Bollinger хороший ответ хорошо описывает, как справиться с конкретной проблемой OP.
The общие проблема заключается в том, как сформировать число, которое имеет по крайней мере
nбит, определенный знак-ness и не подвержены удивительным целочисленным акциям-ядро дилеммы OP. Ниже выполняется это путем вызоваunsignedоперация, которая не изменяет значение - эффективный нет-op, кроме проблем типа. Продукт будет по крайней мере ширинаunsignedилиuint32_t. Литье, в общем, может сузить тип. Литье необходимо избегать, если сужение не обязательно произойдет. Компилятор оптимизации не будет создавать ненужные код.uint32_t a; uint32_t b = (a + 0u) << 31; uint32_t b = (a*1u) << 31;
взяв ключ от этот вопрос о возможном UB в
uint32 * uint32арифметика, простой метод должен работать в C и C++:uint32_t a = (...); uint32_t b = (uint32_t)((a + 0u) << 31);целочисленная константа
0uтипаunsigned int. Это способствует добавлениюa + 0uдоuint32_tилиunsigned intв зависимости от того шире. Потому что тип имеет рангintили выше, больше не происходит продвижение, и сдвиг может быть применен с левым операндомuint32_tилиunsigned int.финал бросьте обратно в
uint32_tбудет просто подавлять потенциальные предупреждения о сужении преобразования (скажем, еслиint64 бита).приличный компилятор C должен видеть, что добавление нуля является no-op, что менее обременительно, чем видеть, что предварительная маска не имеет никакого эффекта после сдвига без знака.
чтобы избежать нежелательного продвижения, вы можете использовать больше тип с помощью typedef, как
using my_uint_at_least32 = std::conditional_t<(sizeof(std::uint32_t) < sizeof(unsigned)), unsigned, std::uint32_t>;
для этого сегмента код:
uint32_t a = (...); uint32_t b = a << 31;поощрения
aдля типа без знака вместо типа со знаком используйте:uint32_t b = a << 31u;когда обе стороны
<<оператор является беззнаковым типом, то эта строка в 6.3.1.8 (c стандартный проект n1570) применяется:в противном случае, если оба операнда имеют целочисленные типы со знаком или оба имеют целочисленные типы без знака, операнд с типом меньшего целочисленного ранга преобразования преобразуется в тип операнда с большим рангом.
проблема, которую вы описываете, вызвана тем, что вы используете
31что этоsigned int typeИтак, еще одна строчка в 6.3.1.8в противном случае, если тип операнда со знаком целочисленного типа может представлять все значения типа операнда со знаком целочисленного типа, то операнд со знаком целочисленного типа преобразуется в тип операнда со знаком целочисленного типа.
сил
aдля повышения до знакового типа
обновление:
этот ответ неверен, потому что 6.3.1.1(2) (акцент мой):
...
если int может представить все значения исходного типа (Как ограничено по ширине, для битового поля), значение преобразуется в int; в противном случае он преобразуется в unsigned int. Они называются целое число специальные акции.58) Все остальные типы не изменяются целое акции.
и сноска 58 (Курсив мой):
58) целочисленные акции применяются только: как часть обычных арифметических преобразований, к некоторым выражениям аргументов, к операндам унарных операторов+, -, и ~ и к оба операнда операторов сдвига, как указано в соответствующих подпунктах.
так как происходит только целочисленное продвижение, а не общее арифметическое преобразование, используя
31uне гарантияaдля преобразования вunsigned intкак указано выше.