процессам [19]. Если перемешивание реализовано на компьютере в видеотдельной команды, этим можно воспользоваться; однако для RISC-компьютеров с базовым набором команд этот способ не годится.

7.4. Сжатие, или обобщенное извлечение

в языке программирования APL имеется операция, которая называется сжатием (compress) и записывается как ВА, где В - булев вектор, а V - вектор с произвольными элементами той же длины, что и В. Результатом данной операции является вектор, состояший из тех элементов V, для которых соответствуюший бит в В равен 1. Длина результирующего вектора равна количеству единичных битов в В.

Рассмотрим аналогичную операцию с битами в слове. Заданы маска т и слово х; требуется выбрать те биты слова х, которые соответствуют единичным битам маски, и переместить их вправо ("сжать"). Например, если сжимаемое слово

abed efgh ijkl mnop qrst uvwx yzAB CDEF, где каждый символ представляет один бит, а маска имеет вид

0000 1111 ООН ООН 1010 1010 0101 0101, то в результате будет получено слово

0000 0000 0000 0000 efgh klop qsuw zBDF.

Эту операцию можно также назвать обобщенным извлечением (generalized extract) по аналогии с командой извлечения, имевшейся в ряде компьютеров.

Нас интересует код, осуществляюЦ1ий данную операцию с минимальным временем работы в наихудшем случае, и в качестве первого приближения, которое будет совершенствоваться, возьмем простой цикл из листинга 7.5. Этот код не содержит команд ветвления в теле цикла и в худшем случае требует выполнения 260 команд, включая пролог и эпилог функции.

Листинг 7.5. Операция сжатия на основе простого цикла

unsigned compress(unsigned х, unsigned m)

unsigned r, s, b; Результат, сдвиг, маскируемый бит

г = 0;

s = 0;

b = m & 1;

r = r I ( (X & b) << s) ; s = s + b; X = X >> 1;

m = m >> 1; } while (m != 0) return Г;

Улучшить этот код можно путем многократного применения метода "параллельного префикса" (см. раздел 5.2) с операцией исключающего или [19] (далее будем обозначать эту операцию как PP-XOR). Основная идея состоит в том, чтобы прежде всего определить биты аргумента х, которые будут перемещены на нечетное количество позиций, и

переместить их (эта задача упрощается, если сначала применить операцию и к слову х и к маске, очистив биты, которые не имеют значения). Биты маски перемещаются точно таким же образом. Затем определяются биты х, перемещаемые на нечетное число, умноженное на 2 (2, 6, 10 и т.д.), после чего вправо перемещаются как эти биты, так и соответствующие биты маски. Далее работаем с битами, перемещаемыми на нечетные числа, умноженные на 4, затем на 8 и 16.

Поскольку этот алгоритм достаточно сложен для понимания, рассмотрим его более детально. Предположим, что входными данными для нашего алгоритма являются следующие:

X = abed efgh ijkl mnop qrst uvwx yzAB CDEF, m = 1000 1000 1110 0000 0000 1111 0101 0101,

1 1 111

9 6 333 4444 3 2 10

Здесь каждая буква в х означает один бит (который может принимать значения О или 1). Числа под каждым единичным битом маски указывают, насколько далеко должен перемещаться вправо соответствующий бит х (это значение равно количеству нулевых битов в m справа от рассматриваемого бита). Как упоминалось ранее, сначала стоит сбросить все не имеющие значения биты х, что даст нам число

X = аООО еООО ijkO 0000 0000 uvwx OzOB ODOF.

Сначала нужно определить, какие биты будут перемещены вправо на нечетное количество позиций, и переместить их на одну позицию вправо. Вспомним, что операция PP-XOR дает нам единичные биты в позициях, для которых количество единичных битов в данной позиции и справа от нее нечетно. Нас же интересуют биты, для которых нечетно количество нулевых битов, расположенных строго справа от данной позиции. Найти их можно путем вычисления тк = ~т<<1 и применением операции PP-XOR к полученному значению. Результат будет следующим:

тк = 1110 1110 ООН 1111 1110 0001 0101 0100, mp = 1010 0101 1110 1010 1010 0000 1100 1100.

Заметим, что тк указывает биты т, которые содержат нулевой бит рядом справа, а mp суммирует их справа по модулю 2. Таким образом, mp определяет биты т, которые имеют нечетное количество нулевых битов справа.

Биты, которые должны быть перемещены на одну позицию, находятся в позициях, имеющих нечетное количество нулевых битов справа (указываемые словом mp), и в этих позициях в m находятся единичные биты, т.е. их можно получить с помощью простой операции mv = mp&m.

mv = 1000 0000 1110 0000 0000 0000 0100 0100

Соответствующие биты m могут быть перемещены путем присвоения m = (т * mv) (mv >> 1) ;

А биты X - с помощью двух присвоений:

t = X & mv,• x = (х t) I (t >> 1) ;

(Перемещение битов m выполняется проще в силу того, что здесь все выбранные биты являются единичными.) Операция исключающего или сбрасывает биты, которые равны 1 в m и X, а операция или устанавливает биты, которые в m и х равны 0. Эти операции могут

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

m = 0100 1000 0111 0000 0000 1111 ООН ООН, X = ОаОО еООО Oijk 0000 0000 uvwx OOzB OODF.

Теперь необходимо подготовить маску для второй итерации, где будуг указаны биты, которые должны быть перемещены вправо на величину, представляющую собой нечетное число, умноженное на 2. Заметим, что величина mk&~mp определяет биты, соседом которых справа в исходной маске m является нулевой бит, и биты, которые в исходной маске имеют справа четное число нулевых битов. Эти свойства применяются совместао, хотя и не каждое в отдельности, к новому значению маски m (т.е. шк указывает все позиции в новой маске т, у которых справа расположен нулевой бит, а всего справа находится четное число нулей). Будучи просуммированной справа при помощи операции PP-XOR, эта величина указывает биты, которые перемещаются вправо на количество позиций, равное удвоенному нечетному числу (2, 6, 10 и т.д.). Таким образом, необходимо присвоить это значение переменной шк и выполнить вторую итерацию описанных выще щагов. Новое значение шк имеет вид

шк = 0100 1010 0001 0101 0100 0001 0001 0000.

Заверщенная функция С, реализующая рассматриваемую операцию, приведена в листинге 7.6. Она требует выполнения 127 базовых RISC-команд, включая пролог и эпилог. В листинге 7.7 показана последовательность значений, принимаемых различными переменными в ключевых точках вычислений (входные данные те же, что использовались при рассмотрении данного алгоритма). Згшетьте, что побочным результатом работы алгоритма является значение маски т, в котором все единичные биты перенесены вправо.

Листинг 7.6. Метод параллельного префикса для операции сжатия

unsigned compress(unsigned х, unsigned m) {

unsigned mk, mp, mv, t; int i;

X = X & m; Сброс незначащих битов

Параллельный префикс

mk = -m << 1; Подсчитаем О справа

for (i = 0; i < 5,- i++)

mp = mk * (mk << 1)

mp = mp * (mp << 2)

mp = mp * (mp << 4)

mp = mp * (mp << 8)

mp = mp * (mp << 16);

mv = mp & m; < Перемещаемые биты

m = m * mv (mv >> (1 << i)); Сжатие m

t = X & mv;

X = X * t I (t >> (1 « i)); Сжатие x

mk = mk & -mp;

return X;