Является ли маскирование перед беззнаковым левым сдвигом в C/С++ слишком параноидальным?

Этот вопрос мотивирован тем, что я внедряю криптографические алгоритмы (например, SHA-1) в C/С++, записывая переносимый платформо-агностический код и полностью избегая поведения undefined.

Предположим, что стандартизованный криптоалгоритм просит вас реализовать это:

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/С++ состоит в том, что если тип (например, 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).

Но теперь у нас есть проблема: смещение ненулевых битов, оставшихся в бите знака целочисленного типа со знаком, - undefined поведение. Эта проблема возникла из-за того, что наш uint32 был повышен до int48 - вместо того, чтобы быть продвинутым до uint48 (где смещение влево было бы в порядке).

Вот мои вопросы:

Является ли мое рассуждение правильным, и является ли это законной проблемой в теории?
Можно ли игнорировать эту проблему, потому что на каждой платформе следующий целочисленный тип имеет двойную ширину?
Хорошая идея правильно защититься от этой патологической ситуации, предварительно маскируя ввод следующим образом: b = (a & 1) << 31;. (Это обязательно будет правильно на каждой платформе, но это может сделать криптографический алгоритм с критической скоростью медленнее, чем необходимо.)

Разъяснения/редактирование:

Я буду принимать ответы для C или С++ или обоих. Я хочу знать ответ хотя бы на одном из языков.
Логика предварительной маскировки может повредить вращение бит. Например, GCC будет компилировать b = (a << 31) | (a >> 1); в 32-разрядную инструкцию бит-вращения на языке ассемблера. Но если мы предварительно замаскируем левый сдвиг, возможно, что новая логика не переведена в бит вращение, а это означает, что теперь выполняется 4 операции вместо 1.

Ответ 1

Взяв ключ из этого вопроса о возможном UB в арифметике uint32 * uint32, следующий простой подход должен работать в 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 должен уметь видеть, что добавление нуля - это не-op, что менее обременительно, чем видеть, что предварительная маска не имеет эффекта после сдвига без знака.

Ответ 2

Говоря на стороне C проблемы,

Я правильно ли рассуждаю, и является ли это законной проблемой в теории?

Это проблема, которую я раньше не рассматривал, но согласен с вашим анализом. C определяет поведение оператора << в терминах типа продвинутого левого операнда, и можно предположить, что целые акции приводят к тому, что они являются (подписаны) int, когда исходный тип этого операнда uint32_t, Я не ожидаю увидеть это на практике на любой современной машине, но я все для программирования в соответствии с фактическим стандартом, а не с моими личными ожиданиями.

Можно ли игнорировать эту проблему, потому что на каждой платформе следующий целочисленный тип имеет двойную ширину?

C не требует такой связи между целыми типами, хотя на практике она вездесуща. Однако если вы настроены полагаться только на стандарт, то есть, если вы пытаетесь написать строго соответствующий код, то вы не можете полагаться на такие отношения.

Это хорошая идея, чтобы правильно защищаться от этой патологической ситуации, предварительно маскируя ввод следующим образом: b = (a и 1) < 31;. (Это обязательно будет правильно на каждой платформе. сделать критически критический алгоритм с критической скоростью медленнее, чем необходимо.)

Тип unsigned long должен иметь как минимум 32 бита значения, и он не подлежит продвижению ни на один другой тип под целыми рекламными акциями. На многих распространенных платформах он имеет то же представление, что и uint32_t, и может даже быть одним и тем же типом. Таким образом, я был бы склонен написать выражение следующим образом:

uint32_t a = (...);
uint32_t b = (unsigned long) a << 31;

Или, если вам нужно a только как промежуточное значение при вычислении b, тогда объявите его как unsigned long для начала.

Ответ 3

Q1: Маскировка перед сдвигом предотвращает поведение undefined, которое вызывает OP.

Q2: "... потому что на каждой платформе следующий целочисленный тип двойной ширины?" → нет. "Следующий" целочисленный тип может быть меньше 2x или даже одного и того же размера.

Для всех совместимых компиляторов C, которые имеют uint32_t, корректно определены следующие.

uint32_t a; 
uint32_t b = (a & 1) << 31;

Q3: uint32_t a; uint32_t b = (a & 1) << 31; не ожидается код, который выполняет маску - в исполняемом файле он не нужен - только в источнике. Если маска действительно возникает, получить лучший компилятор должен быть проблемой.

Как предложил, лучше подчеркнуть неподписанность с этими сдвигами.

uint32_t b = (a & 1U) << 31;

@Джон Боллинджер Хороший ответ. Хорошо, как справиться с конкретной проблемой OP.

Общая проблема заключается в том, как сформировать число, состоящее как минимум из n бит, определенную признак и не подверженное неожиданным целым рекламным акциям - ядро дилеммы OP. Ниже выполняется это, вызывая операцию unsigned, которая не меняет значение - эффективный no-op, отличный от типа. Продукт будет по меньшей мере шириной unsigned или uint32_t. Кастинг, в общем, может сузить тип. Следует избегать литья, если сужение не обязательно произойдет. Компилятор оптимизации не создает ненужный код.

uint32_t a;
uint32_t b = (a + 0u) << 31;
uint32_t b = (a*1u) << 31;

Ответ 4

Чтобы избежать нежелательной рекламы, вы можете использовать больший тип с некоторым typedef, так как

using my_uint_at_least32 = std::conditional_t<(sizeof(std::uint32_t) < sizeof(unsigned)),
                                              unsigned,
                                              std::uint32_t>;

Ответ 5

Для этого сегмента кода:

uint32_t a = (...);
uint32_t b = a << 31;

Чтобы продвигать a к неподписанному типу вместо подписанного типа, используйте:

uint32_t b = a << 31u;

Если обе стороны оператора << являются неподписанным типом, то эта строка в 6.3.1.8 (стандартная черновик стандарта n1570) применяется:

В противном случае, если оба операнда имеют целочисленные типы или оба имеют неподписанные целые типы, операнд с типом ранга меньшего целочисленного преобразования преобразуется в тип операнда с большим рангом.

Проблема, которую вы описываете, вызвана тем, что вы используете 31, которая signed int type, так что другая строка в 6.3.1.8

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

заставляет a продвигаться к подписанному типу

Update:

Этот ответ неверен, потому что 6.3.1.1 (2) (внимание мое):

...

Если int может представлять все значения исходного типа (как ограниченные по ширине, для битового поля), значение преобразуется в int; в противном случае он преобразуется в unsigned int. Они называются целые рекламные акции .58) Все остальные типы не изменяются с помощью целого акции.

и сноска 58 (акцент мой):

58) Целые поощрения применяются только: как часть обычных арифметических преобразований, к некоторым выражениям аргументов, к операндам операторов унарного +, - и ~ и к оба операнда операторов сдвига, как указано в их соответствующих подпунктах.

Так как происходит только цельное продвижение, а не обычное арифметическое преобразование, использование 31u не гарантирует a для преобразования в unsigned int, как указано выше.