Трюки от Крыса

Крис Касперски

Хакер, номер #095, стр. 095-136-1

Реализация ROL/ROR

Огромным недостатком языка Си (оторвать бы за него голову его создателям) является отсутствие операторов циклического битового сдвига, которые присутствуют практически на всех процессорах и без которых не обходится ни подсчет CRC32, ни вычисление корректирующих кодов Рида-Соломона, ни куча других подобных алгоритмов.

Некоторые программисты используют ассемблерные вставки, прибегая к непосредственному вызову команд процессора (на x86 это ROL/ROR – циклический битовый сдвиг влево и вправо соответственно). Однако такое решение делает программу непереносимой, причем совершенно неоправданно непереносимой, поскольку циклический сдвиг элементарно реализуется стандартными средствами Си.

Существует множество способов сделать это. Вот только один из них. Не самый быстрый, требующий двух дополнительных переменных (хотя, в принципе, можно обойтись и одной), зато наглядный и универсальный, то есть работающий с переменными любой разрядности:

Реализация циклического сдвига влево на Си (здесь a – переменная, которую нужно сдвигать, n – на сколько разрядов сдвигать)

ROL(int a, int n)

{

int t1, t2;

n = n % (sizeof(a)*8); // нормализуем n

t1 = a << n; // двигаем а вправо на n бит, теряя старшие биты

t2 = a >> (sizeof(a)*8 - n); // перегоняем старшие биты в младшие

return t1 | t2; // объединяем старшие и младшие биты

}

Реализация циклического сдвига влево на Си

ROR(int a, int n)

{

int t1, t2;

n = n % (sizeof(a)*8); // нормализуем n

t1 = a >> n; // двигаем а влево на n бит, теряя младшие биты

t2 = a << (sizeof(a)*8 - n); // перегоняем младшие биты в старшие

return t1 | t2; // объединяем старшие и младшие биты

}

Испытание обоих функций на прочность

#define VAL 0x12345678

printf("%Xh %Xh %Xh\n",VAL,ROL(VAL,8),ROR(VAL,8));

…

$12345678h 34567812h 78123456h

Этот алгоритм автоматически определяет разрядность аргумента а, поэтому функции ROL/ROR можно безболезненно преобразовать в макросы. Также можно реализовать универсальную функцию/макрос ROx, где направление сдвига задается значением аргумента n. Если он положительный — сдвигаем а вправо, вызывая ROL, если n отрицательный — сдвигаем a влево, вызывая ROR и передавая -1*n.

Бумеранг всегда возвращается

Имея в своем распоряжении функцию циклического сдвига, мы можем выполнять эффективный разворот, отображение и другие типы трансформаций геометрических фигур. Главное — выбрать правильную схему отображения байт сдвигаемой переменной на байты двумерного массива с геометрической фигурой внутри.

В самом деле, и разворот, и трансформация по сути своей являются сдвиговыми операциями, что приведенный ниже пример, собственно говоря, и подтверждает:

int x;

// кодируем «пропеллер» в двухмерном массиве,

// развернутом в линейный массив, представленный двойным словом

//

// ** <- фигура типа

.. * <- «бумеранг»

union{int ou; char uo[4];} xxx; xxx.ou = 0x2A2A2A2A20;

for (x=0;x<8;x++)

{

// выбираем схему отображения,

// реализующую разворот

printf("%c%c\n%c%c\n\n",xxx.uo[0],xxx.uo[3],xxx.uo[1],xxx.uo[2]);