RC4 (2-я часть)
Теперь рассмотрим "перетасовку" байт в массиве M, используя входной ключ.
Здесь получается такая картина - на обработку одного байта массива M необходимо минимум 7 команд, покажем это на примере одной итерации:
xor eax,eax ;в AL будем хранить индекс A
mov ebp,offset Key
mov edi,offset M
...
add al,byte ptr[ebp+i] ;A += Key[i % 16]
mov dl,byte ptr [edi+i] ;Считываем M[i]
add al,dl ;A += M[i]
movzx esi,al
mov bl,byte ptr [edi+esi] ;Считываем M[A]
mov byte ptr [edi+esi],dl
mov byte ptr [edi+i],bl
...
Причем такая конструкция имеет ряд особенностей:
- Использование команды MOVZX ESI,AL устраняет следующий конфликт на процессорах Intel: обращение к 32-битному регистру сразу после модификации его младшей (16- или 8-битной) части. В этом случае ко времени выполнения команды добавляется несколько тактов штрафа. Кстати, на процессорах от AMD таких штрафов нет. :)
- Конфликты по чтению/записи в одну кэш-линейку процессора.
Известно, что при обращении к ячейке памяти процессор считывает из памяти (или кэша 2-го уровня) не одну эту ячейку, а целую строку (например, 32 байта), которую и размещает в кэше 1-го уровня. При этом ВСЯ эта строка помечается как доступная либо только для чтения, либо для записи. Поэтому, если прочитать байт по адресу X, а потом записать байт по адресу (X + 1), то несмотря на то, что байт по адресу (X + 1) уже в кэше(!), процессор после выполнения первой команды должен сначала "освободить" всю строку, а лишь потом снова ее загрузить, но уже для записи в нее, что, естественно, приводит к штрафам. Но, т.к. алгоритм формирует равномерное распределение байт, то такие конфликты возникают нечасто.
- Возможно, есть еще ряд конфликтов именно по работе с памятью, т.к. такие алгоритмы - это для процессоров не самый "удобный" код :)
В итоге такая конструкция выполняется в среднем за 5 тактов, т.к. все эти команды простые и на процессорах P-II/III от Intel могут декодироваться всеми 3-мя декодерами. Таким образом, декодирование может происходить по 3 команды за такт, что частично компенсирует вышеописанные штрафы.
