умножения, а также команды загрузки больших констант. Последняя формула, например, требует выполнения 10 базовых RISC-команд, две из которых - команды умножения, что составляет примерно ,20 тактов на современных RISC-машинах. С другой стороны, адаптация кода из листинга 7.1 для реверса б-битовых целых чисел потребует около 15 команд и примерно от 9 до 15 тактов, в зависимости от возможностей конкретной машины по распараллеливанию вычислений на уровне команд. Тем не менее подобные формулы дают очень компактный код. Ниже приведено еще несколько аналогичных алгоритмов для 32-битовой машины. При применении этого метода для 8- и 9-битовых целых чисел на 32-битовой машине в алгоритмах дважды применяются идеи из [25].

Вот как выглядит методика реверса 8-битовых целых чисел:

s{x* 0x02020202) & 0x84422010

8) & 0x00000420 remu (s+ (,1023)

Здесь функция remu не может быть заменена командами умножения и сдвига. (Чтобы понять, почему такая замена в данном случае оказывается некорректной, выполните все описанные действия и посмотрите, какие при этом получаются битовые комбинации.)

Вот еще один метод реверса 8-битового целого числа, который интересен тем, что может быть несколько упрощен:

S «- (х * 0x00020202) &Ох01О44О1О ( {х*0x00080808)&0x02088020 remu + (,4095)

Упрощение заключается в том, что второе произведение представляет собой сдвиг влево первого произведения, последняя маска может быть получена из второй маски путем единственной команды сдвига, а команду остаток от деления можно заменить командами умножения и сдвига. После всех упрощений код требует выполнения 14 базовых RISC-команд, две из которых - команды ул<нолсен«я.

и 0x00020202 0x01044010

(<-(и«2)&(и1«1)

(0x01001001 *(s+/))»24

Реверс 9-битового целого числа выполняется следующим образом:

s{x* 0x01001001) & 0x84108010 <<-(** 0x00040040) & 0x00841080

remu(s+(,1023)

Второго умножения можно избежать, так как оно равно первому произведению, сдвинутому вправо на 6 бит. Последняя маска равна второй маске, сдвинутой вправо на 8 бит. После соответствующих замен код будет требовать выполнения 12 базовых RISC-команд, включая одну команду умножения и одну остатка от деления. Команда остаток от деления должна быть беззнаковой, и ее нельзя заменить командами улноженкя и сдвига.

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

кусственный) пример. Пусть имеется 8-битовая величина, из которой требуется извлечь каждый второй бит, и упаковать четыре полученных бита в крайние правые разряды, т.е. выполнить следующее преобразование:

0000 0000 0000 0000 0000 0000 abed efgh => 0000 0000 0000 0000 0000 0000 0000 bdfh

Данное преобразование можно выполнить следующим образом:

t<r-{x* 0x01010101) & 0x40100401 ((*0х08040201)»27

Тем не менее на большинстве компьютеров наиболее практичным оказывается метод, основанный на индексировании таблицы из однобайтовых (или 9-битовых) целых чисел.

Увеличение обращенного целого числа

В алгоритме быстрого преобразования Фурье (БПФ) используется как целая переменная i в цикле, в котором происходит ее увеличение на 1, так и значение rev(i) [50]. Простейший

способ работы состоит, конечно, в вычислении в кавдой итерации увеличенного значения i с последующим вычислением rev(i). Безусловно, для малых значений i быстрее и практичнее

проводить поиск значений rev(i) в таблице, но что делать при больших i, когда поиск в таблице неприменим в силу непрактичности, а для вычисления rev(i) требуется 29 команд?

Если использовать поиск в таблице невозможно, лучше хранить i как в нормальном, так и в реверсном виде, увеличивая оба значения при каждой итерации. При этом возникает вопрос: как наиболее эффективно выполнить приращение целого числа, которое хранится в регистре в реверсном виде? Например, на 4-битовой машине при таком увеличении необходимо последовательно пройти такие значения (в щестнадцатеричной записи):

о, 8, 4, С, 2, А, 6, Е, 1, 9, 5, D, 3, В, 7, F.

В алгоритме быстрого преобразования Фурье как i, так и реверсное значение имеют одинаковую длину, котор почти наверняка меньше 32, и оба значения в регистрах выровнены по правой границе. Однако мы считаем, что i - 32-битовое целое число. После прибавления 1 к реверсному 32-битовому значению выполняется сдвш вправо определенного количества битов, и затем полученное значение используется в алгоритме БПФ для индексации массива в памяти.

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

unsigned х, т;

m = 0x80000000;

X = X * m;

if ((int)x >= 0)

tn = tn > > 1;

X = X * m;

} while (x < m);

Здесь происходит выполнение трех базовых RISC-команд, если х начинается с нулевого бита, плюс четыре дополнительные команды для каждой итерации цикла. Поскольку вероятность того, что х начинается с нулевого бита, равна 1/2, что х начинается с 10

(в бинарной записи) равна 1/4 и т.д., среднее число выполняемых команд равно

3-- + 7- + 11-- + 15-+...= 2 4 8 16

= 4~ + 8~+12~ + 16--+...-1 = 2 4 8 16

/12 3 4 U 4 8 16

-1 =

= 7.

(Во второй строке мы добавили и вычли 1, причем первая единица представлена в виде суммы 1/2 + 1/4+1/8 + .... Полученный ряд похож на ряд, уже рассматривавшийся в разделе 5.4.) Однако в худшем случае выполнять приходится достаточно большое количество команд - 131.

Если в компьютере есть команда вычисления количества ведущих нулевых битов в слове, то увеличить реверсное значение на 1 можно следующим образом:

сначала вычисляется s<-nlz(-ir),

а затем либо xi-x® 0x80000000»s

либо

x<is +0x80000000 :«>s.

В любом случае выполняется пять команд из полного набора RISC-команд, а кроме того, для корректного перехода от OxFFFFFFFF к О требуется, чтобы сдвиги выполнялись по модулю 64. (Из-за этого приведенные формулы не будуг работать на компьютерах с процессором Intel х8б, поскольку сдвиги в нем выполняются по модулю 32.)

7.2. Перемешивание битов

Другим важным видом перестановки битов в слове является операция "идеального перемешивания" (perfect shuffle), которая используется в криптографии. Существует две разновидности идеального перемешивания, которые называются "внешним" и "внутренним". Обе операции чередуют биты из двух половин слова. В целом процесс аналогичен тасованию колоды из 32 карт, разница лишь в том, какая карта должна быть первой. В результате внешнего идеального перемешивания внешние биты остаются во внешних позициях, а после внутреннего идеального перемешивания бит из позиции 15 перемещается в позицию 31. Если 32-битовое слово равно (здесь каждая буква означает один бит)

abed efgh ijkl tnnop ABCD EFGH IJKL MNOP,

to после выполнения внешнего идеального перемешивания расположение битов в слове окажется следующим:

аАЬВ cCdD eEfF gGhH iljJ kKlL mMnN oOpP,