Ь6=(а0 & 2)*64

(а4 & 2)*4

Ь7=(а0 )*128

(а4 & 1) *8

(al & 2)*32

(а5 & 2)*2

(al & 1)*64

(а5 & 1)*4

(а2 & 2)*16

(аб & 2)

(а2 & 1) *32

(аб & 1)*2

(аЗ & 2)*8 I

(а? & 2)/2;

(аЗ & 1)*1б

(а? & 1) ;

На большинстве компьютеров этот код выполняется при помощи 174 команд (62 команды м, 56 команд сдвига и 56 команд или). Команды ит можно заменить командами сложения. На PowerPC транспонирование подматрищл может быть выполнено всего за 63 команды (семь команд пересылки региспров и 56 команд циклического сдвига влево на непосредственно указанное количество битов с последующей вставкой маски). Здесь не учтены ни команды загрузки и сощ>анения байтов, ни код получения адресов загружаемых байтов.

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

На первом шаге битовая матрица 8x8 интерпретируется как 16 битовых матриц размером 2x2 и выполняется транспонирование каждой из них. На втором шаге матрица интерпретируется как четыре подматрицы размером 2x2 (каждый элемент такой подматрицы является матрицей размером 2x2) и выполняется транспонирование всех четырех подматриц 2x2. На последнем шаге матрица интерпретируется как матрица 2x2, элементами которой являются матрищл размером 4x4, и выполняется транспонирование этой матрицы 2x2. Эти преобразования проиллюстрированы ниже.

0123 4567 89аЬ cdef ghij klmn opqr stuv wxyz ABCD EFGH IJKL MNOP QRST UVWX YZ$.

082a 4c6e 193b 5d7f goiq ksmu hpjr Itnv wEyG AICK xFzH BJDL MUOW QYS$ NVPX RZT.

08go 4cks 19hp 5dlt 2aiq 6emu 3bjr 7fnv wEMU AIQY xFNV BJRZ yGOW CKS$ zHPX DLT.

08go wEMU 19hp XFNV 2aiq yGOW 3bjr ZHPX 4cks AIQY 5dlt BJRZ 6emu CKS$ 7fnv DLT.

По сравнению с алгоритмом, в котором на каждом шаге приходится выполнять действия над каждым из восьми битов в восьми регистрах, этот метод оказывается более эффективным. Сначала байты упаковываются по четыре в регистр, затем выполняется перестановка битов в этих регистрах, за которой следует распаковка. Код данной процедуры представлен в листинге 7.2. Параметр А представляет собой адрес первого байта подматрицы 8x8 исходной матрицы (размер которой 8mx8w бит). Аналогично, параметр в является адресом первого байТга 8х8-подматрицы результирующей матрищл (размером 8wx8/n бит). (Таким образом, размер исходной матрицы в байтах - %тхп, результирующей - 8лхт).

Листинг 7.2. Транспонирование матрицы размером 8x8 бит

void transposes(unsigned char A[8], int m, int n, unsigned char В[8])

unsigned x, y, t;

Загружаем массив и упаковываем его в х и у

X = (А[0]«24) у = (А[4*т]«24)

(А [т] «16) (А[5*т]<<16)

(А[2*т] «8) (А[6*т]«8)

А[3*т] ; А[7*т] ;

t = (х * (х >> 7)) & ОхООААООАА; х = х * t * (t << 7); t = (у * (у >> 7)) & ОхООААООАА; у = У * t * (t « 7);

t = (X (х >>14)) & ОхООООСССС; х = х * t * (t <<14); t = (у * (у >>14)) & ОхООООСССС; у = у * t * (t «14);

t = (X & OxFOFOFOFO) ((у » 4) & OxOFOFOFOF); у = ((X « 4) & OxFOFOFOFO) (у & OxOFOFOFOF); X = t;

В[0]=х>>24; В[п]=х>>16; В[2*п]=х»8; В[3*п]=х; B[4*n]=y>>24 В[5*пЗ*у>>16; В[6*п]=у>>8; В[7*п]=у;

Строка

t = (X * (х >> 7)) & ОхООААООАА; х = х * t * (t « 7);

кажется загадкой. В ней выполняется пфестановка битов 1 и 8 (если считать справа), 3 и 10,5 и 12 и т.д. в слове х; в то же время биты О, 2, 4 и т.д. остаются на месте. Все перестановки осуществляются с помощью метода перестановки битов (см. раздел 2.19), в котфом используются команды исключающего или. Слово х до и после первого щнсла имеет вид

0123 4567 89аЬ cdef ghij klmn opqr stuv 082a 4c6e 193b 5d7f goiq ksmu hpjr Itnv

Чтобы реально сравнить эти методы, для непосредственного метода, описанного ранее, составлена завершенная программа, аналогичная процедуре из листинга 7.2. Обе программы откомпилированы компилятором GNU С для целевого компьютера, подобного RISC-компьютеру с базовым набором команд. Полное количество команд с учетом всех команд загрузки, сохранения, кода адресации элементов массивов, пролога и эпилога функций составляет 219 для непосредственного метода и 101 для метода из листинга 7.2. (Пролог и эпилог в данных процедурах были пустыми, если не считать команды возврата из функции.) Вариант кода из листинга 7.2 для 64-битовых RISC-компьютеров с базовым набором команд (когда хну содержатся в одном регистре) содержит около 85 команд.

Алгоритм из листинга 7.2 осуществляет процесс перестановки битов в блоках растущих размеров. Однако транспонирование матрицы можно реализовать и наоборот - от больших блоков к меньшим. В таком алгоритме на первом шаге матрица размером 8x8 интерпретируется как матрица размером 2x2, элементы которой являются матрицами 4x4, и выполняется транспонирование матрицы 2x2. Затем каждая из четырех матриц 4x4 интерпретируется как матрица 2x2, элементы которой являются матрицами размером 2x2 бит, и выполняется транспонирование всех четырех подматриц 2x2 и т.д. Код в этом случае получается такой же, как и в листинге 7.2, но при этом три группы операторов, выполняющих перестановку битов, выполняются в обратном порядке.

Транспонирование битовой матрицы размером 32x32

Естественно, что при транспонировании матриц больших размеров используется тот же рекурсивный метод, что и при транспонировании матриц 8x8. Таким образом, транспонирование матрицы 32x32 вьшолняется в пять этапов.

Детали реализации транспонирования матрицы 32x32 существенно отличаются от процедуры, приведенной в листинге 7.2, так как мы полагаем, что матрицу 32x32 невозможно полностью разместить в регистрах общего назначения и поэтому необходимо разработать компактную процедуру, которая индексирует соответствующие слова бито-

вой матрицы для выполнения перестановки битов. Описанный алгоритм работает лучше при движении от больших блоков к меньшим.

На первом этапе исходная матрица рассматривается как четыре матрицы размером 16x16 и преобразуется следующим образом:

Га с]

в D

Здесь А обозначает левую половину первых 16 слов исходной матрицы, В - правую половину первых 16 слов и т.д. Очевидно, что такое преобразование может быть выполнено посредством следующих обменов:

правая половина слова О с левой половиной слова 16, правая половина слова 1 с левой половиной слова 17,

правая половина слова 15 с левой половиной слова 31.

При реализации этого алгоритма в коде используется индекс к, принимающий значения от О до 15. В цикле по к правая половина слова с номером к меняется местами с левой половиной слова к+16.

На втором этапе матрица рассматривается как 16 матриц размером 8x8 бит и выполняется следующее преобразование:

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

битов OxOOFFOOFF слова О с битами OxFFOOFFOO слова 8, битов OxOOFFOOFF слова 1 с битами OxFFOOFFOO слова 9 и т.д.

Это означает, что биты 0-7 (младшие восемь битов) слова О меняются местами с битами 8-15 слова 8 и т.д. Индексы первого слова в этих перестановках принимают значения к = 0,1, 2, 3,4, 5, 6, 7,16, 17, 18, 19, 20, 21, 22, 23. На каждом шаге очередное значение к можно вычислить по формуле k = {k + 9)&-S . В цикле по к биты слова к меняются местами с битами слова k+S.

Аналогично, на третьем этапе меняются местами

биты OxOFOFOFOF слова О с битами OxFOFOFOFO слова 4, биты OxOFOFOFOF слова 1 с битами OxFOFOFOFO слова 5 и т.д.

Индексы битов в первом слове в этих перестановках равны = О, 1, 2, 3, 8, 9, 10, 11, 16, 17, 18, 19, 24, 25, 26, 27. На каждом шаге очередное значение к вычисляется по формуле it = (it + 5) & -4. В цикле по к биты слова к меняются местами с битами слова + 4.

Все описанные действия в целях компактности представлены в виде отдельной функции на языке С в листинге 7.3 [19]. Внешний цикл выполняет описанные пять этапов; переменная j при этом принимает значения 16, 8, 4, 2 и 1. На каждом этапе формируется маска т, принимающая значения OxOOOOFFFF, OxOOFFOOFF, OxOFOFOFOF, 0x33333333 и 0x55555555. (Код вычисления маски компактен и красив: m = (т<< j). Обратаого ему кода не существует, и в этом основная причина того, что преобразования выполняются от блоков больших размеров к блокам меньших размеров.) Во внутреннем цикле к принимает описанные