RC4 (1-я часть)
1. Сразу же бросается в глаза инициализация массива значениями от 0 до 255, которое происходит при каждом новом значении ключа (т.е. фактически при каждом новом пароле). Как же можно сделать ее более эффективной?
Выход есть - инициализировать массив не побайтно (256 команд), а, например, используя 32-битные регистры процессора, по 4 байта за 64 команды - и действительно, выигрыш по времени будет в 4 раза (конечно же, если массив M выровнен минимум по границе DWORD'a). А есть ли еще более "широкие" регистры, чтобы за одну команду "махом" записывать бОльшее кол-во байт? Регистры FPU отпадают, т.к. операции с ними выполняются очень долго, остаются, конечно же, MMX-регистры:
.DATA
qwInit DQ 0706050403020100h
qwAdd DQ 0808080808080808h
...
.CODE
mov edi,offset M+128
movq mm0,qword ptr [qwInit]
movq mm1,qword ptr [qwAdd]
movq [qword ptr edi-128],mm0
paddb mm0,mm1
movq [qword ptr edi-120],mm0
paddb mm0,mm1
movq [qword ptr edi-112],mm0
...
paddb mm0,mm1
movq [qword ptr edi+112],mm0
paddb mm0,mm1
movq [qword ptr edi+120],mm0
Чтобы не писать 31 одинаковый фрагмент кода, гораздо проще использовать зарезервированный макрос Ассемблера IRP, тогда последние строки кода можно заменить на следующую конструкцию:
IRP i,<-15,-14, ... ,14,15>
paddb mm0,mm1
movq [qword ptr edi+(i*8)],mm0
ENDM
Итого получаем - на инициализацию массива из 256 байт затрачиваем 66 команд процессора, которые выполняются за ~35-40 тактов, т.к. команды PADDB и MOVQ выполняются синхронно.
Нетрудно догадаться, ЧТО наворотил бы на месте этого цикла любой компилятор С, если этот код писать не на Асме. ;)
У читателя, наверное, возник вопрос - почему мы инициализируем EDI не на начало массива M, а на его середину?
Просто дело в том, что при таком варианте программы дополнительное смещение к EDI будет приводить к увеличению длины команды MOVQ всего на один байт (знаковый диапазон -128...+127) и команда получает длину в 4 байта. А если, к примеру, прибавить к EDI +256, то смещение будет расширено до DWORD'a и длина команды увеличится до 7 байт. Использование же более коротких команд является предпочтительным, т.к. идет более "плотное" заполнение буфера предвыборки команд и более оптимальное их декодирование процессорами.
И еще - вдумчивый читатель скажет, что есть ведь еще более "широкие" XMM-регистры - те, которые используются в наборах команд SSE (которые, кстати, поддерживают и Athlon'ы) и SSE2 от Intel. Используя их, можно оперировать с памятью блоками по 16 байт за такт!
Действительно, это так. В PWLInside не была включена поддержка SSE только по причине недостаточного распространения таких процессоров в то время, когда создавалась программа. Вполне возможно, что в следующей версии программы поддержка SSE будет присутствовать.
