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

Операция сжатия, интересующая нас, должна сжимать влево все биты, помеченные в маске единицами, и вправо - биты, помеченные нулями. Иногда эту операщио называют операцией разделения "агнцев и козлищ" {sheep and goats - SAG) или "обобщенным упорядочением" (general unshuffle). Вычислить эту операцию можно по формуле

SAG(x, m) = compress left(х, m) compress(x, -m).

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

Здесь операция SAG используется для выполнения устойчивой двоичной поразрядной сортировки (устойчивость означает сохранение порядка следования равных элементов при сортировке). Массив р используется как 32 пятибитовых ключа для сортировки битов X. На первом шаге все биты х, для которых р [0] =1, перемещаются в левую половину результирующего слова, а все, для которых р [0] =0, - в правую. Порядок битов при этом не изменяется (т.е. сортировка устойчива). Затем аналогично сортируются все ключи, которые будут использоваться в следующих шагах алгоритма. Очередная, шестая, строка сортирует х на основе вторых младших битов и т.д.

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

р[1] = SAG(p[l] , р[0] ) ;

р[2] = SAG(SAG(p[2] , р[0]), р[1]);

р[3] = SAG(SAG(SAG(p[3] , р [0] ) , р [1] ) , р[2]);

р[4] = SAG(SAG(SAG(SAG(p[4] , р[0]), р [1] ) , р[2]), р[3]);

После этого каждая перестановка осуществляется с помощью следующих действий:

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

Более прямой (хотя, пожалуй, менее интересный) способ осуществления обобщенных перестановок битов в слове состоит в представлении перестановки как последовательности 32 пятибитовых индексов, к-й индекс представляет собой номер бита в исходном слове, который будет помещен в к-ю позицию при перестановке. (Список "откуда", в отличие от списка "куда", применяемого при методе GAS.) Эти индексы могут быть упакованы по 6 в 32-битовое слово; таким образом, для хранения всех 32 индексов требуется шесть слов. Аппаратно команда может быть реализована как

bitgather Rt, Rx, Ri,

где Rt - целевой регистр (а также источник), регистр Rx содержит переставляемые биты, а в регистре Ri содержится шесть пятибитовых индексов (и два неиспользуемых бита). Ниже приведена операщи, выполняемая командой.

Говоря обычным языком, содержимое целевого регистра сдвигается влево на шесть позиций и из слова х выбираются шесть битов и помещаются в шесть освобожденных позиций t. Выбираемые биты определяются шестью пятибитовыми индексами в слове i, берущимися в порядке слева направо. Нумерация битов в индексах может быть как слева направо, так и справа налево.

Для перестановки слова используется последовательность из шести таких команд, все с одинаковыми Rt и Rx, но с разными индексными регистрами. В первом индексном регистре последовательности значащими являются только индексы U и /5, а биты, выбираемые остальными четырьмя ийдексами, просто выдвигаются за пределы Rt.

Реализация этой команды, скорее всего, будет позволять индексным значениям повторяться, так что эта команда может использоваться не только для перестановки битов. Она может применяться для многократного повторения любого выбранного бита в целевом регистре. Операции SAG такая универсальность не свойственна.

Не слишком сложно реализовать эту команду как быструю (т.е. выполняемую за один такт). Модуль выбора бита состоит из шести 32:1 мультиплексоров. Если они построены на базе пяти мультиплексоров 2:1, то данная команда может выполняться быстрее, чем 32-битовая команда сложения [45].

Перестановка битов применяется в криптографии, а для компьютерной графики характерна тесно связанная с перестановкой битов операция перестановки подслое (например, перестановка байтов в пределах слова). Оба эти применения работают чаще с 64-битовыми словами, иногда даже со 128-битовыми, чем с 32-битовыми. Методы SAG и bitgather кето модифицировать для работы, со словами указанной длины.

Для шифрования и дешифрования сообщения с помощью алгоритма стандартного шифрования данных (DES) требуется большое количество отображений, аналогичных перестановкам. Сначала вьшолняется генерация ключа, которая включает 17 перестановочных отображений. Затем каждый блок сообщения, состоящий из 64 битов, подвергается 34 операциям перестановки. Первая и последняя операции представляют собой 64-битовые перестановки, причем одна из них обратна другой. Кроме того, 16 перестановок с повторениями отображают 32-битовые величины на 48-битовые и еще 16 выполняются в пределах 32-битовых слов [И].

Впрочем, в настоящее время DES вышел из употребления, после того как в 1998 году Electronic Frontier Foundation была доказана его низкая криптостойкость при наличии специального аппаратного обеспечения. Национальный институт стандартов и технологий (National Institute of Standards and Technology - NIST) в качестве временной замены предложил использовать Triple DES - метод шифрования, в котором к каждому

64-битовому блоку DES применяется трижды, каждый раз с другим ключом (таким образом, длина ключа равна 192 битам, включая 24 бита четности). Такой метод требует соответственно в три раза больше операций перестановки битов по сравнению с обычным DES.

Однако предлагаемая "постоянная" замена DES н Triple DES, стандарт Advanced Encryption Standard [1], срвсем не использует перестановки на уровне битов. Ближайшая к перестановкам операция, используемая новым стандартом,- простой циклический сдвиг на расстояния, кратные 8. Другие предлагаемые или применяемые методы шифрования используют гораздо меньше перестановок по сравнению с DES.

При сравнении двух рассмотренных методов перестановки следует указать достоинства каждого из них. Метод bitgather обладает следующими преимуществами: простота подготовки индексных слов из данных, описывающих перестановку, более простое аппа-ратаое обеспечение и более универсальное отображение. Метод SAG 1) выполняет перестановку за меньшее число команд, 2) использует в команде только два регистра-источника (что может играть существенную роль в ряде RISC-архитектур), 3) легче масштабируется для выполнения перестановки в двойных словах, 4) более эффективно выполняет перестановку подслов.

Пункт 3 подробно рассматривается в [43]. Команда SAG позволяет осуществить перестановку двойного слова путем выполнения двух команд SAG, нескольких базовых RISC-команд и двух полных перестановок единичных слов. Команда bitgather позволяет сделать то же путем выполнения трех полных перестановок единичных слов и нескольких базовых RISC-команд. Здесь не учитывается предварительная обработка перестановки, состоящая в получении значений, зависящих только от нее; этот подсчет остается читателю в качестве домашнего задания.

Что касается пункта 4, то для перестановки, например, четырех байтов слова при помощи bitgather требуется выполнить шесть команд - столько же, сколько при обобщенной перестановке. Метод SAG позволяет выполнить те же действия за две команды, а не за пять, которые требуются для осуществления обобщенной перестановки с помощью этого метода. Выигрыш в эффективности достигается даже в том случае, когда размер переставляемых подслов не являются степенью 2; для перестановки п подслов требуется [log, и] шагов (в п не входят возможные группы битов, расположенные на концах слова

и не участвующие в перестановке).

Кроме команд SAG и bitgather (которые имеют имена GRP и PPERM соответственно), в [43] рассматриваются и другие возможные команды перестановки, а также перестановки путем поиска в таблицах.

7.6. Перегруппировки и преобразоваЦия индексов

Многие простые перегруппировки битов в компьютерном слове соответствуют еще более простым преобразованиям координат, или индексов битов [19]. Эти соответствия применимы к перегруппировкам элементов в любом одномерном массиве, в котором количество элементов представляет собой целую степень 2. В контексте практического программирования наиболее важен случай, когда элементы массива представляют собой слова (или превосходят их по размеру).

Рассмотрим в качестве примера внешнее идеальное перемешивание элементов массива А размером 8, дающее в результате массив В и состоящее из следующих шагов: