Сижу я значит спокойно, никого не трогаю, починяю примус, и вдруг как захотелось сгенерировать SHA-256 целиком внутри процессора на MASM64, без обращения к памяти, что прям места себе не нахожу.
По сути алгоритм SHA-256 состоит из двух частей, часто называемых Декомпрессией, когда из данных входящего сообщения генерируются дополнительные данные и Компрессии, когда эти данные сжимаются до сообщения фиксированной длины Hesh. Оба алгоритма, до определенной степени, могут работать параллельно, когда данные вычисленные на этапе Декомпрессии тут же подвергаются Компрессии, а результатам такой параллельной работы является поэтапное обновление Hesh.
Алгоритм Декомпрессии позволяет вычислять два новых значения за раз и требует для своей работы 16 dword, что автоматически приводит к тому что единственное подходящие для него место размещения SIMD регистры.
В регистрах XMM0-XMM3 размещаются непосредственно сами значения, а в регистрах XMM4-XMM5 производятся вычисления. По соглашению о вызовах эти регистры не сохраняют значения между вызовами функций и потому их значения не требуется сохранять, перед началом процедуры и восстанавливать по ее окончанию.
Скрытый текст
.code align xmmword Head: ; s0 pshufd xmm4,xmm0,10100101b movdqa xmm5,xmm4 psrld xmm5,3 psrlq xmm4,7 pxor xmm5,xmm4 psrlq xmm4,11 pxor xmm5,xmm4 ; s0 + w[0] pshufd xmm5,xmm5,10001000b paddd xmm5,xmm0 ; s0 + w[0] + w[9] pshufd xmm4,xmm2,10011001b paddd xmm5,xmm4 ; w[i] + k[i] + h movdq2q mm7,xmm0 paddd mm7,qword ptr[r9] paddd mm7,mm3 shufps xmm0,xmm1,01001110b shufps xmm1,xmm2,01001110b shufps xmm2,xmm3,01001110b shufps xmm3,xmm5,01001110b ; s1 pshufd xmm4,xmm3,01010000b movdqa xmm5,xmm4 psrld xmm5,10 psrlq xmm4,17 pxor xmm5,xmm4 psrlq xmm4,2 pxor xmm5,xmm4 pshufd xmm5,xmm5,10001000b ; s1 + s0 + w[0] + w[9] pslldq xmm5,8 paddd xmm3,xmm5К интересной особенности этого алгоритма можно отнести способ реализации вращения данных в SIMD регистрах. Стоит заметить, что прямая инструкция вращения данных отсутствует, и чтобы реализовать вращение сперва производится копирование dword в верхнюю и нижнюю часть qword, а потом производится сдвиг на право/лево. Таким образом биты из одного dword перемещаются в другой dword,что полностью идентично прямому вращению dword.
Алгоритм Компрессии позволяет вычислять только одно новое значение за раз и требует для своей работы 8 dword, учитывая что SIMD регистры уже заняты, а регистры общего назначения GPR не позволяют эффективно реализовать алгоритм Компрессии размещаем его в MMX регистрах (привет из 90-х).
В регистрах MM0-XMM3 размещаются непосредственно сами значения, а в регистрах MM4-XMM6 производятся вычисления, регистр MM7 используем для перемещения данных между SIMD и MMX. Соглашение о вызовах вообще не оговаривает состояние MMX регистров, что делает их все временными.
Скрытый текст
.code align xmmword Tail: clc ; s1 @@:pshufw mm4,mm2,01000100b psrlq mm4,6 pshufw mm5,mm4,11100100b psrlq mm4,5 pxor mm5,mm4 psrlq mm4,14 pxor mm4,mm5 ; ch punpckhdq mm3,mm2 pshufw mm5,mm2,11101110b pand mm5,mm2 pshufw mm6,mm2,01000100b pandn mm6,mm3 pxor mm5,mm6 ; t1 paddd mm5,mm7 psrlq mm7,20h paddd mm4,mm5 ; d + t1 psllq mm4,20h punpckldq mm2,mm1 paddd mm2,mm4 pshufw mm2,mm2,01001110b ; s0 pshufw mm5,mm0,01000100b psrlq mm5,2 pshufw mm6,mm5,11100100b psrlq mm5,11 pxor mm6,mm5 psrlq mm5,9 pxor mm5,mm6 ; t1 + s0 punpckhdq mm1,mm0 punpckldq mm0,mm5 paddd mm0,mm4 ; maj pshufw mm4,mm0,01000100b pand mm4,mm1 pshufw mm5,mm4,11101110b pxor mm4,mm5 pshufw mm5,mm1,01001110b pand mm5,mm1 pxor mm4,mm5 ; maj ; t1 + t2 psllq mm4,20h paddd mm0,mm4 pshufw mm0,mm0,01001110b cmc jc@b add r9,08h ret К интересным особенностям этого алгоритма можно отнести то, что dword Hesh размещены в регистрах «змейкой», то есть меняют направление своего расположения от четного регистра к нечетному. Это позволяет эффективней получать к ним доступ и проще их перемещать.
Процедуру загрузки данных в регистры SIMD, производит разворот от big-endian к little-endian , добавление байта заглушки 80h и длины сообщения в битах в последний блок.
Скрытый текст
.code align xmmword Load: cmp rdx,0 jleLoadPlugData mov eax,40h cmp rdx,10h jgeLoadDataLine ret_LoadDataLine: movd xmm5,eax mov rax,[r11] bt edx,3 cmovc rax,[r11 + 8] mov r8,80h ror rax,cl shld r8,rax,cl xor rax,rax bt edx,3 cmovc rax,r8 cmovc r8,[r11] bswap rax bswap r8 movd xmm3,r8 movd xmm4,rax shufps xmm3,xmm4,00010001b movd eax,xmm5 sub rdx,10h sub eax,10h cmp eax,0 jgLoadZeroLine ret_LoadZeroLine: pshufd xmm4,xmm3,10111011b movd rax,xmm4 cmp rdx,-9 cmovle rax,rcx movd xmm4,rax shufps xmm3,xmm4,00010100b ret align xmmword @@:pxor xmm3,xmm3 sub rdx,10h sub eax,10h jleret_LoadZeroLine align xmmword LoadZeroLine: movdqa xmm0,xmm1 movdqa xmm1,xmm2 movdqa xmm2,xmm3 cmp rdx,0 jl@b cmp rdx,10h jlret_LoadDataLine align xmmword LoadDataLine: movdqu xmm3,xmmword ptr[r11] movdqa xmm4,xmm3 psllw xmm3,8 psrlw xmm4,8 por xmm3,xmm4 pshufhw xmm3,xmm3,10110001b pshuflw xmm3,xmm3,10110001b add r11,10h sub rdx,10h sub eax,10h cmp eax,0 jgLoadZeroLine ret align xmmword LoadPlugData: setz al movzx eax,al shl eax,31 ; AndreyDmitriev movd xmm0,eax pxor xmm1,xmm1 pxor xmm2,xmm2 movd xmm3,rcx pshufd xmm3,xmm3,00011110b sub rdx,40h retОсновная процедура метода, принимает данные и запускает цикл обработки. Из интересных особенностей про него можно отметить только, что загрузка первоначального Hesh производится не из памяти а непосредственно в регистр MMX через регистры RAX.
Скрытый текст
.code align xmmword ?ImplBin@SHA256@KILYAV@@CA?AV?$array@E$0CA@@std@@PEBDI@Z proc ?ImplBin@SHA256@KILYAV@@CA?AV?$array@E$0CA@@std@@PEBDI@Z endp Bin: lea r9,[const] mov r10,rcx mov r11,rdx lea rcx,[r8 * 8] mov rdx,r8 mov rax,0bb67ae856a09e667h movd mm0,rax mov rax,03c6ef372a54ff53ah ; 0a54ff53a3c6ef372h movd mm1,rax mov rax,09b05688c510e527fh movd mm2,rax mov rax,01f83d9ab5be0cd19h ; 05be0cd191f83d9abh movd mm3,rax align xmmword Block: movd qword ptr[r10 + 00h],mm0 movd qword ptr[r10 + 08h],mm1 movd qword ptr[r10 + 10h],mm2 movd qword ptr[r10 + 18h],mm3 call Load mov eax,18h align xmmword @@:call Head dec eax jnz@b mov eax,08h align xmmword @@: movdq2q mm7,xmm0 paddd mm7,qword ptr[r9] paddd mm7,mm3 shufps xmm0,xmm1,01001110b shufps xmm1,xmm2,01001110b shufps xmm2,xmm3,01001110b psrldq xmm3,8 call Tail dec eax jnz@b paddd mm0,qword ptr[r10 + 00h] paddd mm1,qword ptr[r10 + 08h] paddd mm2,qword ptr[r10 + 10h] paddd mm3,qword ptr[r10 + 18h] sub r9,100h ; AndreyDmitriev cmp rdx,-8 jgeBlock movq2dq xmm1,mm0 movq2dq xmm2,mm1 call Store movdqa xmm0,xmm1 movq2dq xmm1,mm2 movq2dq xmm2,mm3 call Store movdqu [r10 + 00h],xmm0 movdqu [r10 + 10h],xmm1 mov rax,r10 ret Store: pshuflw xmm1,xmm1,10110001b pshuflw xmm2,xmm2,00011011b punpcklqdq xmm1,xmm2 movdqa xmm2,xmm1 psllw xmm1,8 psrlw xmm2,8 por xmm1,xmm2 retДополнительно представлена процедура Hex которая преобразует данные полученные из Bin в строку символов char.
Скрытый текст
.code align xmmword ?ImplHex@SHA256@KILYAV@@CA?AV?$array@D$0EA@@std@@PEBDI@Z proc ?ImplHex@SHA256@KILYAV@@CA?AV?$array@D$0EA@@std@@PEBDI@Z endp Hex: call Bin mov rdx,303007070909h movd xmm5,rdx punpcklbw xmm5,xmm5 call HexDuoLine movdqu [rax + 30h],xmm2 movdqa xmm2,xmm1 call HexLine movdqu [rax + 20h],xmm2 movdqa xmm1,xmm0 call HexDuoLine movdqu [rax + 10h],xmm2 movdqa xmm2,xmm1 call HexLine movdqu [rax + 00h],xmm2 ret align xmmword HexDuoLine: movdqa xmm2,xmm1 pxor xmm3,xmm3 punpckhbw xmm2,xmm3 punpcklbw xmm1,xmm3 align xmmword HexLine: movdqa xmm3,xmm2 psrlw xmm2,4 psllw xmm3,12 psrlw xmm3,4 por xmm2,xmm3 movdqa xmm3,xmm2 pshufd xmm4,xmm5,0 pcmpgtb xmm3,xmm4 pshufd xmm4,xmm5,01010101b pand xmm3,xmm4 paddb xmm2,xmm3 pshufd xmm4,xmm5,10101010b paddb xmm2,xmm4 retВ итоге к памяти все таки пришлось обращаться за самим сообщением, константами и сохранять начальное значение hesh блока.
Чтобы код имел хоть какай-то практический смысл, и для удобство тестирования, я скомпилировал его в статическую библиотеку под Visual Studio и написал для него С++ имплементирующий класс, который разместил в заголовочном файле.
Оставшийся часть кода не имеет принципиального значения, и/или интересных необычных приемов заслуживающих отдельного обсуждения, с ним можно ознакомится по адресу:
ссылка на оригинал статьи https://habr.com/ru/articles/859092/
Добавить комментарий