Сижу я значит спокойно, никого не трогаю, починяю примус, и вдруг как захотелось сгенерировать 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
jle LoadPlugData
mov eax,40h
cmp rdx,10h
jge LoadDataLine
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
jg LoadZeroLine
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
jle ret_LoadZeroLine
align xmmword
LoadZeroLine:
movdqa xmm0,xmm1
movdqa xmm1,xmm2
movdqa xmm2,xmm3
cmp rdx,0
jl @b
cmp rdx,10h
jl ret_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
jg LoadZeroLine
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
jge Block
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 и написал для него С++ имплементирующий класс, который разместил в заголовочном файле.
Оставшийся часть кода не имеет принципиального значения, и/или интересных необычных приемов заслуживающих отдельного обсуждения, с ним можно ознакомится по адресу:
