Листинг 6.5. Поиск первой строки из л единичных битов с помощью команд сдвига и и

int ffstri(unsigned x, int n) {

int s;

while (n > 1) { s = n >> l; x = X & (x << s) ; n = n - S;

return nlz(x);

Поиск строки, содержащей точно п единичных битов, требует на шесть команд больше (на четыре, если есть команда и-нё). После вьшолнения всех действий листинга 6.5 единичные биты в д: находятся в позихщях, где в исходном слове начинается строка из п или более единичных битов. Следовательно, после подстановки вычисленного значения д: выражение

ж»1

&-

ж«1

содержит единичный бит в той позиции, в которой в х находится изолированный единичный бит, т.е. с этой позиции в исходном слове х начинается строка ровно из п единичных битов.

Данный алгоритм можно легко адаптировать и для поиска строк длиной п, которые начинаются в определенных позициях. Например, чтобы найти строку, первый бит которой находится на границе байта, необходимо применить команду и к конечному значению X и числу 0x80808080.

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

ж«-ж(ж«2) X *-х\{х \) x«-0x7F7F7F7Fx

>«-nlz(-J;)»3

Всего при этом требуется выполнение 12 команд из полного набора RISC-команд (т.е. этот алгоритм оказывается менее эффективным, чем алгоритм из листинга 6.2, в котором вьшолняется восемь команд).

ГЛАВА?

ПЕРЕСТАНОВКА БИТОВ И БАЙТОВ

7.1. Реверс битов и байтов

Под операцией реверса битов подразумевается отражение содержимого регистра относительно середины слова, т.е. размещение битов в слове в обратном порядке:

rev (0x01234567) = 0хЕ6А2С480 rev(OOOOOOOlOOlOOOllOlOOOlOlOllOOlll) = 11100110101000101100010010000000

Под операцией реверса байтов подразумевается аналогичное отображение четырех байтов регистра. Операция реверса байтов необходима при преобразовании данных между форматом, когда первым идет младщий байт (little-endian), который используется, например, DEC и Intel, и форматом, когда первым идет старший байт (big-endian), использующийся большинством других производителей.

Ниже показан эффективный метод реверса битов в слове [3]: в первой строке меняются местами соседние биты, во второй - соседние 2-битовые поля и т.д. Все пять операторов присвоения можно выполнять в произвольном порядке.

Для ряда машин можно воспользоваться усовершенствованием, приведенным в листинге 7.1, которое заключается в том, чтобы избежать больших непосредственно задаваемых значений. Этот код требует выполнения 30 базовых RISC-команд и не использует команд ветвления.

Листинг 7.1. Реверс битов

unsigned rev(unsigned х) {

X = (х & 0x55555555) << 1 (х >> 1)

X = (X & 0x33333333) « 2 (х >> 2)

X = (X & OXOFOFOFOF) << 4 (х » 4)

X = (X << 24) I ((X & OxFFOO) << 8) 1

0x55555555 0x33333333 OXOFOFOFOF

((X » return X;

8) & OxFFOO)

(X >> 24);

Последнее присвоение х в этом коде выполняет реверс байта за девять базовых RISC-команд. Если компьютер способен к выполнению циклического сдвига, вычислить х можно за семь команд:

(*&0x00FF00FF)»8

& OxOOFFOOFF

На PowerPC операцию реверса байта можно реализовать всего за три команды [26]: циклический сдвиг влево на 8 бит, за которым следуют две команды rlwimi (rotate left word immediate then mask insert - циклический сдвиг влево непосредственного заданного слова с последующей вставкой маски).

Обобщенный реверс битов

В [19] предложено следующее обобщение реверса битов:

if (к & 1) X = (X & 0x55555555) « 1

if (к & 2) X = (х & 0x33333333) « 2

if (к & 4) X = (х & OxOFOFOFOF) « 4

if (к & 8) X = (X & OxOOFFOOFF) « 8

if (к &16) X = (X & OxOOOOFFFF) << 16

(х & ОхАААААААА) » 1

(х & ОхСССССССС) >> 2

(Х & OxFOFOFOFO) >> 4

(X & OxFFOOFFOO) >> 8

(х & OxFFFFOOOO) >>16

(Последние две команды и можно опустить.) Если к = 31, этот код выполняет реверс всех битов слова. При к = 24 выполняется реверс байтов слова. Если к = 7, выполняется реверс битов в каждом байте, но расположение байтов в слове при этом не изменяется. При к = 16 выполняется перестановка левого и правого полуслов, и т.д. В общем случае эит, находящийся в позиции т, перемещается в позицию m Ф А . На аппаратном уровне )тот процесс реализуется подобно циклическому сдвигу (пять уровней мультиплексиро-5ания, каждым из которых управляет свой бит величины сдвига к).

Повременные методы реверса битов

В [25, item 167] приводятся более сложные выражения для реверса 6-, 7- и 8-битовых це-ых чисел. Несмотря на то что все эти выражения разработаны для 36-битовых машин, выра-:ение для реверса 6-битовых целых чисел работает и на 32-битовых машинах, а выражения ля реверса 7- и 8-битовых чисел - на 64-битовых машинах. Приведем эти выражения.

6 бит: remu((je *0х00082082)& 0x01122408,255)

7 бит: геши {(ж * 0x40100401) & 0x442211008,255)

8 бит: гети((ж *0x202020202) &0x10884422010,1023)

В результате получаются "чистые" целые числа, т.е. числа, выровненные по правой анице, неиспользуемые старшие биты которых равны 0.

Во всех трех случаях вместо функции remu можно использовать функции rem или )d, поскольку аргументы функции remu положительны. Функция остаток от деления 1анных формулах просто суммирует цифры числа в системе счисления по основанию 5 или 1024, подобно тому как в десятичной системе счисления остаток от деления на 9 эсто равен сумме цифр числа (если полученное число больше 9, процесс суммирова-I цифр повторяется). Следовательно, эту функцию можно заменить командами умно-ния и сдвига вправо. Например, реверс 6-битовых чисел.на 32-битовом компьютере «но выполнить так (умножение вьшолняется по модулю 2):

( (ж * 0x00082082) & 0x01122408

(*0х01010101)»24

Применение описанных формул ограничено, так как они включают получение атка (требующее для выполнения 20 тактов и больше) и/или несколько команд