Листинг 7.7. Действия при использовании метода параллельного префикса для онерации сжатия

Алгоритм из листинга 7.6 на 64-битовой машине с базовым RISC-набором выполняется за 169 команд, в то время как алгоритм из листинга 7.5 в худшем случае требует выполнения 516 команд.

Количество команд, выполнения которых требует алгоритм из листинга 7.6, может быть значительно снижено, если m представляет собой константу. Это может быть в двух ситуациях: 1) когда вызов compress (x,m) осушествляется в цикле, в котором значение m не известно заранее, но постоянно в пределах цикла, 2) когда известно значение m и код функции compress генерируется заранее, возможно, компилятором.

Обратите внимание на то, что значение, присвоенное х в цикле в листинге 7.6, используется в этом цикле исключительно в строке, где выполняется присвоение х. Как видно из кода, х зависит только от себя самого и переменной mv. Следовательно, все об-рашения к х можно удалить, а пять вычисляемых значений mv сохранить в переменных mvO, mvl, mv4. Тогда в ситуации 1 вне цикла, в котором имеется обрашение compress (х,т), можно разместить функцию, которая не будет обращаться к х, а будет лишь вычислять значения mvl, а в самом цикле можно разместить следующие строки:

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

В ситуации 2, в которой известно значение т, можно выполнить примерно те же действия, не считая другой возможной оптимизации. Так, может оказаться, что одна из пяти масок равна О, и в этом случае можно опустить одну из приведенных выше строк. Например, если нет битов, которые должны быть перемещены на нечетное число позиций, маска ml равна 0; если нет битов, которые перемещаются более чем на 15 позиций, равной О окажется маска т4.

Так, для

m = 0101 0101 0101 0101 0101 0101 0101 0101 вычисленные маски равны

Поскольку последняя маска равна О, в скомпилированном коде операция сжатия выполняется за 17 команд (не считая команд для загрузки масок). Конечно, имеются еще более специализированные случаи, в часгаости код из раздела 7.2, в котором сжимаются чередующиеся биты, выполняется всего за 13 команд.

Использование команд вставки и извлечения

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

Целевой регистр инициализируется нулевым значением, после чего для каждой непрерывной группы единичных битов в маске m переменная х сдвигается вправо для выравнивания очередного поля и используется команда вставки, которая вставляет биты х в соответствующее место целевого регистра. Таким образом операция сжатия выполняется с помощью 2п +1 команд, где п - количество полей (групп единичных битов) в маске. В наихудшем случае требуется выполнить 33 команды, так как максимальное число полей равно 16 (случай чередования единичных и нулевых битов).

В качестве примера, когда метод с использованием команды вставки дает существенный выигрыш, рассмотрим т=0х001(Ю84А. Сжатие с такой маской требует перемещения битов на 1, 2, 4, 8 и 16 позиций. Следовательно, при использовании метода параллельного префикса требуется выполнение всех 21 команды, в то время как при использовании вставки достаточно 11 команд (в маске имеется пять полей). Еще более удачным примером может служить маска т=0х8О(ХЮО0О. Здесь происходит перемещение одного бита на 31 позицию, что требует выполнения 21 команды в методе параллельного префикса, только трех команд при использовании вставки и только одной команды (сдвиг вправо на 31 бит), если вы не ограничены определенной схемой вычислений.

Можно также воспользоваться командой извлечения (extract) для реализации операции сжатия посредством выполнения Зп -2 команд, где п - количество полей в маске.

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

Сжатие влево

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

наиболее приемлемы, если ваш компьютер имеет команды реверса или подсчета количества единичных битов. Если же таких команд в наборе компьютера нет, можно легко адаптировать алгоритм из листинга 7.6, просто изменив направление всех сдвигов на обратное (за исключением двух сдвигов в выражениях l<<i, всего восемь изменений).

7.5. Обобщенные перестановки

При выполнении обобщенной перестановки битов в слове (или где-либо еще) главной проблемой становится представление перестановок. Очень компактно представить перестановку невозможно. Поскольку в 32-битовом слове можно выполнить 32! перестановки, для указания одной из них требуется, как минимум, ["log2(32!)] = U8 битов, или 3 слова и еще 22 бита.

Один интересный способ представления перестановок тесно связан с операцией сжатия, рассматриваемой в разделе 7.4 [19]. Начнем с непосредственного метода, в котором для каждого бита просто указывается позиция его перемещения. Например, для перестановки, которая выполняется путем циклического сдвига влево на четыре бита, бит в позиции О (младший бит) переместится в позицию 4, в позиции 1 - в позицию 5, в позиции 31 - в позицию 3. Такая перестановка может быть представлена следующим вектором из 32 пятибитовых индексов:

00100 00101

11111 ооооо

00001 00010 00011

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

Каждый бит в р [0] представляет собой младший бит позиции, в которую переносится соответствующий бит исходного слова х, биты в р [1] представляют собой следующий значащий бит и т.д. Это очень похоже на то, как маска m в предыдущем разделе ко-