Это маскировка перед беззнаковый сдвиг влево на 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 long
to начинаться.
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
будет просто подавлять потенциальные предупреждения о сужении преобразования (скажем, еслиint
64 бита).приличный компилятор 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
как указано выше.