Это маскировка перед беззнаковый сдвиг влево на 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 (где левый сдвиг будет в порядке).


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

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

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

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

разъяснения/изменения:

  • я принимаю ответы на C или C++ или оба. Я хочу знать ответ хотя бы на один из языков.

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

5 68

5 ответов:

говоря о с-стороне проблемы,

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

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

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

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

  1. является ли хорошей идеей правильно защититься от этой патологической ситуации, предварительно замаскировав вход таким образом?: 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 как указано выше.