Этот рецепт будет посвящен двум часто применяемым в криптографических и похожих алгоритмах, где требуется манипулировать переменными как потоками битов — циклическому сдвигу влево и вправо.
Данные операции встречаются довольно часто, а вот их реализации найти достаточно сложно и некоторые из существующих решений некорректны. Именно поэтому мы решили здесь разместить обе функции, как обычный рецепт, который легко будет найти впоследствии.
Циклический сдвиг влево (для целочисленных значений и на целочисленный шаг) можно представить следующим образом:
static uint rotateLeft(uint value, int shift) { return (value << shift) | (value >> (32 - shift)); } static T rotateLeft(T)(T value, T shift) { return (value << shift) | (value >> (T.sizeof * 8 - shift)); }
Циклический сдвиг битов вправо выглядит несколько иначе:
static uint rotateRight(uint value, int shift) { return (value >> shift) | (value << (32 - shift)); } static T rotateRight(T)(T value, T shift) { return (value >> shift) | (value << (T.sizeof * 8 - shift)); }
Эти операции, как ни странно, встречаются очень часто и не только в криптографии, автору этого блога однажды удалось найти подобные операции в скоростном алгоритме сортировки, а также в одном из алгоритмов обработки изображений! И, поскольку циклические сдвиги упоминаются во многих алгоритмах, а реализации обычно предлагаются для сдвигов только на 1 бит, настоятельно рекомендуем взять рецепт на вооружение.
И напоследок определения из C, переведенные для D (циклические сдвиги для 32-битных беззнаковых целочисленных значений):
uint rotl32(uint value, uint count) { uint mask = 8 * sizeof(value) - 1; count &= mask; return (value << count) | (value >> (-count & mask)); } uint rotr32(uint value, uint count) { uint mask = 8 * sizeof(value) - 1; count &= mask; return (value >> count) | (value << (-count & mask)); }