Почти постоянное время вращения, что не нарушает стандарты

Question

У меня чертовски много времени, пытаясь придумать постоянное вращение, которое не нарушает стандарты C/C++.

Проблема заключается в крайних / угловых случаях, когда операции вызываются в алгоритмах, и эти алгоритмы не могут быть изменены. Например, следующее из Crypto++ и выполняет тестовый жгут под GCC Ubsan (т.е. g++ fsanitize=undefined):

$ ./cryptest.exe v | grep runtime
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:625:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:643:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'
misc.h:637:22: runtime error: shift exponent 32 is too large for 32-bit type 'unsigned int'

И код в misc.h:637:

template <class T> inline T rotlMod(T x, unsigned int y)
{
    y %= sizeof(T)*8;
    return T((x<<y) | (x>>(sizeof(T)*8-y)));
}

ICC от Intel была особенно безжалостной, и она удалила весь вызов функции без y %= sizeof(T)*8, Мы исправили это несколько лет назад, но оставили другие ошибки на месте из-за отсутствия решения с постоянным временем.

Осталась одна болевая точка. когда y = 0, Я получаю условие, где 32 - y = 32, и это устанавливает неопределенное поведение. Если я добавлю чек для if(y == 0) ..., то код не соответствует требованию постоянного времени.

Я рассмотрел ряд других реализаций, от ядра Linux до других криптографических библиотек. Все они содержат одно и то же неопределенное поведение, поэтому это тупик.

Как я могу выполнить вращение в почти постоянное время с минимальным количеством инструкций?

РЕДАКТИРОВАТЬ: почти постоянное время, я имею в виду избегать ветви, поэтому всегда выполняются одни и те же инструкции. Я не беспокоюсь о таймингах микрокода процессора. Несмотря на то, что предсказание ветвления может быть хорошим на x86/x64, оно может не работать так же хорошо на других платформах, таких как встроенные

---

Ни один из этих трюков не потребовался бы, если бы GCC или Clang предоставили встроенную функцию для выполнения поворота в почти постоянное время. Я бы даже согласился "выполнить вращение", поскольку у них даже этого нет.

Answer 1

Я связался с этим ответом для получения полной информации по нескольким другим "поворотным" вопросам, включая этот вики-вопрос сообщества, который должен постоянно обновляться с учетом передового опыта.

Я нашел сообщение в блоге об этой проблеме, и похоже, что это наконец решенная проблема (с достаточно новыми версиями компилятора).

Джон Регер из Университета Юты рекомендует версию "с" своих попыток сделать функцию поворота. Я заменил его assert на битовое AND и обнаружил, что он все еще компилируется в один вращающийся insn.

typedef uint32_t rotwidth_t;  // parameterize for comparing compiler output with various sizes

rotwidth_t rotl (rotwidth_t x, unsigned int n)
{
  const unsigned int mask = (CHAR_BIT*sizeof(x)-1);  // e.g. 31

  assert ( (n<=mask)  &&"rotate by type width or more");
  n &= mask;  // avoid undef behaviour with NDEBUG.  0 overhead for most types / compilers
  return (x<<n) | (x>>( (-n)&mask ));
}

rotwidth_t rot_const(rotwidth_t x)
{
  return rotl(x, 7);
}

Это может быть связано с типом x, но для реального использования имеет смысл иметь ширину в имени функции (например, rotl32). Обычно, когда вы вращаетесь, вы знаете, какую ширину вы хотите, и это важнее, чем переменная размера, в которой вы в данный момент храните значение.

Также убедитесь, что используете это только с неподписанными типами. Сдвиг вправо подписанных типов делает арифметическое смещение, сдвигая в знаковых битах. (Это технически зависящее от реализации поведение, но теперь все использует дополнение 2).

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

Я проверил мой с gcc.godbolt.org, с определенным NDEBUG, для переменных и счетчиков поворотов во время компиляции:

• gcc: оптимальный код с gcc> = 4.9.0, без ветвления neg+shifts+ или с более ранним.
  (счетчик констант времени компиляции: gcc 4.4.7 в порядке)
• clang: оптимальный код с clang> = 3.5.0, без ветвления neg+shifts+ или с более ранним.
  (во время компиляции const rotate count: clang 3.0 в порядке)
• ICC 13: оптимальный код.
  (счетчик констант времени компиляции с -march=native: генерирует медленнее shld $7, %edi, %edi, Хорошо без -march=native)

Даже более новые версии компилятора могут обрабатывать общедоступный код из википедии (включенный в пример godbolt) без генерации ветки или cmov. Версия Джона Регера позволяет избежать неопределенного поведения, когда число поворотов равно 0.

Есть некоторые предостережения с 8 и 16-битным поворотом, но компиляторы кажутся хорошими с 32 или 64, когда n является uint32_t, Посмотрите комментарии в коде на ссылку Godbolt для некоторых заметок из моего тестирования различной ширины uint*_t, Надеемся, что эта идиома будет лучше узнаваема всеми компиляторами для большего количества комбинаций ширины типов в будущем. Иногда GCC будет бесполезно испускать AND insn на счетчике поворота, хотя x86 ISA определяет вращающиеся insns с этим точным И в качестве первого шага.

"оптимальный" означает такой же эффективный, как:

# gcc 4.9.2 rotl(unsigned int, unsigned int):
    movl    %edi, %eax
    movl    %esi, %ecx
    roll    %cl, %eax
    ret
# rot_const(unsigned int):
    movl    %edi, %eax
    roll    $7, %eax
    ret

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

Со старыми компиляторами вы все равно получите идеальный код, когда счетчик поворотов является константой времени компиляции. Godbolt позволяет вам тестировать с ARM в качестве цели, и он также использовал вращение там. При подсчете переменных в старых компиляторах вы получаете небольшое раздувание кода, но нет ветвлений или серьезных проблем с производительностью, поэтому в целом эта идиома должна быть безопасной для использования.

Кстати, я изменил оригинал Джона Регера, чтобы использовать CHAR_BIT*sizeof(x), а gcc / clang / icc выдает оптимальный код для uint64_t также. Тем не менее, я заметил, что изменение x в uint64_t в то время как тип возврата функции все еще uint32_t заставляет gcc компилировать его в смены / или. Так что будьте осторожны, чтобы привести результат к 32 битам в отдельной точке последовательности, если вы хотите, чтобы младшие 32b из 64b вращались. т.е. присвойте результат 64-битной переменной, затем приведите / верните его. icc по-прежнему генерирует вращающийся insn, но gcc и clang этого не делают, поскольку

// generates slow code: cast separately.
uint32_t r = (uint32_t)( (x<<n) | (x>>( -n&(CHAR_BIT*sizeof(x)-1) )) );

Если кто-то может проверить это с помощью MSVC, было бы полезно узнать, что там происходит.

Answer 2

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

template <class T> inline T rotlMod(T x, unsigned int y)
{
    y %= sizeof(T)*8;
    return T((x<<y) | (x>>((sizeof(T)*8-y) % (sizeof(T)*8))));
}

Answer 3

Написание выражения как T((x<<y) | ((x>>(sizeof(T)*CHAR_BITS-y-1)>>1)) должен дать определенное поведение для всех значений y ниже размера бита, предполагая, что T является беззнаковым типом без отступов. Если компилятор не имеет хорошего оптимизатора, результирующий код может быть не таким хорошим, как тот, который был бы создан вашим исходным выражением. Однако необходимость терпеть неуклюжий трудно читаемый код, который приведет к более медленному выполнению на многих компиляторах, является частью цены прогресса, поскольку гиперсовременный компилятор, который предоставляется

if (y) do_something();
return T((x<<y) | (x>>(sizeof(T)*8-y)));

может улучшить "эффективность" кода, сделав вызов do_something безусловна.

PS: Интересно, существуют ли какие-либо реальные платформы, где изменение определения сдвига вправо так, чтобы x >> y когда y точно равен размеру бита xпотребовалось бы получить либо 0, либо x, но могло бы сделать выбор произвольным (неуказанным) образом, потребовало бы от платформы генерировать дополнительный код или исключило бы действительно полезные оптимизации в не надуманных сценариях?

Answer 4

Альтернативой дополнительному модулю является умножение на 0 или 1 (благодаря !!):

template <class T> T rotlMod(T x, unsigned int y)
{
    y %= sizeof(T) * 8;
    return T((x << y) | (x >> ((!!y) * (sizeof(T) * 8 - y)));
}