Сижу я значит спокойно, никого не трогаю, починяю примус, и вдруг как захотелось сгенерировать 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 и написал для него С++ имплементирующий класс, который разместил в заголовочном файле.
Оставшийся часть кода не имеет принципиального значения, и/или интересных необычных приемов заслуживающих отдельного обсуждения, с ним можно ознакомится по адресу:
Комментарии (31)
novoselov
16.11.2024 22:46А если использовать AVX или AVX-512?
KILYAV Автор
16.11.2024 22:46К моему удивлению, практически никакой разницы, увеличение размеров регистров позволит упростить перемещение между ними и разместить все вычисление в SIMD, но алгоритмы Декомпрессии и Компрессии по прежнему будут вычисляться по два и одно значение за раз.
AVX & AVX-512 сделают код короче и быстрей, но не в разы.
KILYAV Автор
16.11.2024 22:46Есть обновление, тесты AndreyDmitriev показали, что лучший на данный момент код на AVX-512 в 10 раз быстрей. Возможно мой код можно ускорить в два и даже три раза, но все равно AVX-512 будет в три пять раз быстрей.
titbit
16.11.2024 22:46Мне кажется, что использование MMX одновременно с XMM слегка снижает производительность, так что рекомендую рассмотреть регистры XMM8-XMM15, тем более код все равно 64-битный.
p.s. ссылка в конце битая и ведет в "https://sha_256/"
KILYAV Автор
16.11.2024 22:46У меня нет оснований для такого утверждения, но я предполагаю что регистры MMX & XMM с аппаратной точки зрения это одни и те же регистры, где в качестве MMX регистра выступает нижняя часть MMX регистра, таким образом мой код просто "отжимает" себе больше регистров из общей "кучи". К примеру в Skylake 128 векторных регистров, разделяемых между 6-8 ядрами.
Согласен что решение через старшие регистры SIMD "безопасней".
AndreyDmitriev
16.11.2024 22:46MMX одновременно с XMM слегка снижает производительность
Тут, видимо, имеются ввиду пенальти, связанные с переходом процессора из одного состояния (AVX) в другое (SSE) и необходимостью сохранить верхние 128 бит каждого YMM регистра. Но это в общем лечится использованием vzeroupper, которая обнуляет эти биты, но всё же учебник не рекомендует смешивать такой код.
Цитата из учебника (на английском)
The last issue that programmers need to be aware of involves the intermixing of x86-AVX and x86-SSE code. Programs are allowed to intermix x86-AVX and x86-SSE instructions, but any intermixing should be kept to a minimum in order avoid internal processor state transition penalties that can affect performance.
These penalties can occur if the processor is required to preserve the upper 128 bits of each YMM register during a transition from executing x86-AVX to executing x86-SSE instructions. State transition penalties can be completely avoided by using the vzeroupper (Zero Upper Bits of YMM Registers) instruction, which zeroes the upper 128 bits of all YMM registers. This instruction should be used prior to any transition from 256-bit x86-AVX code (i.e., any x86-AVX code that uses a YMM register) to x86-SSE code.
One common use of the vzeroupper instruction is by a public function that uses 256-bit x86-AVX instructions. These types of functions should include a vzeroupper instruction prior to the execution of any ret instruction since this prevents processor state transition penalties from occurring in any high-level language code that uses x86-SSE instructions. The vzeroupper instruction should also be employed before calling any library functions that might contain x86-SSE code. Later in this book, you’ll see several source code examples that demonstrate proper use of the vzeroupper instruction. Functions can also use the vzeroall (Zero All YMM Registers) instruction instead of vzeroupper to avoid potential x86-AVX/x86-SSE state transition penalties.
AndreyDmitriev
16.11.2024 22:46Что-то мне подсказывает, что для "r" регистров надо movq использовать вместо movd.
Вот здесь (и ещё в куче мест):
Я просто хотел себе динамическую библиотечку забацать, но налетел на исключение, и вот проходя отладчиком, заметил, что movd местами превратились в movq (там где eax - осталось movd, естественно) :
Ну то есть оно у вас и так работает, просто masm достаточно умный, а если сразу movq написать, то будет аккуратнее, как мне кажется.
KILYAV Автор
16.11.2024 22:46Я компилирую через ml64 у него есть странный баг, он не понимает инструкцию movq в данном контексте, мне даже попадалась инфа в нете, что люди обращались по этому вопросу и им ответили что и так сойдет.
Так и живем.
KILYAV Автор
16.11.2024 22:46Забавно, но вот только что я узнал ответ на этот вопрос.
Изначально инструкция movd появилась вместе с ММХ до х64 и могла пересылать только 32-битные данные из GPR в MMX, а инструкция movq пересылала данные между регистрами MMX, потом регистры расширили, а мнемонику менять не стали, и по прежнему movd пересылает данные между разными регистрами, а movq между регистрами ММХ.
AndreyDmitriev
16.11.2024 22:46Где-там унутре, похоже сидит бага.
Хеш от строки "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ0123" должен быть "8FB605EAB2EFAE3D1FCC881FA5C5DD6219A17CA3663E46642FF566847C24C272", а алгоритм выдаёт "CE9C5B8AEF93B3DBA226776FD28705501FEF649A50C3257D65DFE2DC42997E3A" (если я всё правильно скомпилировал). Однако если я уберу последний символ: "abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ012", то становится правильно: "D74BA075E4259C6C807C4101E66D281096CF9FF14BA01260DEE741B1BDAEF326". Вообще для всех строк короче 55 символов вроде ОК, а вот начиная с 56 байт и длиннее — неверно. Я глубоко не копал, это навскидку так. Константы вроде верные, я проверил.
KILYAV Автор
16.11.2024 22:46Вы совершенно правы, я забыл перезапустить указатель на таблицу констант между блоками, в итоге начиная со второго блока вместо констант происходило чтение мусора.
Что еще раз напоминает об опасности работы с указателями.
Большое Вам спасибо за внимание к моему коду и его проверку.
Надеюсь он Вам пригодится.
AndreyDmitriev
16.11.2024 22:46Спасибо за правку. Да, теперь этот тест проходит, но граница сдвинулась на 64-й байт. Тестовая строка длиной 64 байта - слово test 16 раз — "testtesttesttesttesttesttesttesttesttesttesttesttesttesttesttest". Должно быть "3e2b0a3dc3503d99e14cf834a3be419c4729fe32ee5fd037407f81f4d73aa619", а у Вас (точнее у меня) "4fbce22b8a9bf8137c3d2d0ad0a3cb2ea63d37be47cfdc5ea99f0a958337aca7". Я для проверки вот этим сервисом пользуюсь.
Посмотрите пожалйста, если найдётся время. Практического интереса у меня в общем нет, просто нравятся такие мини-проектики, хочу на мегабайтной строке побенчмаркать и сравнить с OpenSSL и LabVIEW.
KILYAV Автор
16.11.2024 22:46Исправил.
В процедуре загрузки я не учел, что "заглушку" тоже нужно перевернуть.
Попробуйте сейчас.
AndreyDmitriev
16.11.2024 22:46Отлично, на рандомной мегабайтной строке тест проходит!
На досуге время замеряю.
AndreyDmitriev
16.11.2024 22:46По бенчмаркам вот что получается, если взять 16 МБ строку:
На стареньком рабочем лаптопе вот так:
LabVIEW Вы уверенно обогнали, но до OpenSSL не дотянулись, примерно втрое
На Xeon W-2245, тут частота повыше и результаты получше:
А если запустить на камушке, который, насколько я понимаю, нативно поддерживает SHA256, то вот:
Тут уже ровно десятикратная разница.
KILYAV Автор
16.11.2024 22:46Надо попробовать убрать MMX и перенести все в SIMD
На wiki написано, что часть OpenSSL написан на ассемблере, так что возможно тут соревнуются два асм кода и похоже их лучше.
AndreyDmitriev
16.11.2024 22:46А, и вдогонку, одна из самых быстрых реализаций выглядит как-то вот так:
Если процессор поддерживает SHA256RNDS2, SHA256MSG1 и SHA256MSG2
/* sha256-x86.c - Intel SHA extensions using C intrinsics */ /* Written and place in public domain by Jeffrey Walton */ /* Based on code from Intel, and by Sean Gulley for */ /* the miTLS project. */ /* gcc -DTEST_MAIN -msse4.1 -msha sha256-x86.c -o sha256.exe */ /* Include the GCC super header */ #if defined(__GNUC__) # include <stdint.h> # include <x86intrin.h> #endif /* Microsoft supports Intel SHA ACLE extensions as of Visual Studio 2015 */ #if defined(_MSC_VER) # include <immintrin.h> # define WIN32_LEAN_AND_MEAN # include <Windows.h> typedef UINT32 uint32_t; typedef UINT8 uint8_t; #endif /* Process multiple blocks. The caller is responsible for setting the initial */ /* state, and the caller is responsible for padding the final block. */ void sha256_process_x86(uint32_t state[8], const uint8_t data[], uint32_t length) { __m128i STATE0, STATE1; __m128i MSG, TMP; __m128i MSG0, MSG1, MSG2, MSG3; __m128i ABEF_SAVE, CDGH_SAVE; const __m128i MASK = _mm_set_epi64x(0x0c0d0e0f08090a0bULL, 0x0405060700010203ULL); /* Load initial values */ TMP = _mm_loadu_si128((const __m128i*) &state[0]); STATE1 = _mm_loadu_si128((const __m128i*) &state[4]); TMP = _mm_shuffle_epi32(TMP, 0xB1); /* CDAB */ STATE1 = _mm_shuffle_epi32(STATE1, 0x1B); /* EFGH */ STATE0 = _mm_alignr_epi8(TMP, STATE1, 8); /* ABEF */ STATE1 = _mm_blend_epi16(STATE1, TMP, 0xF0); /* CDGH */ while (length >= 64) { /* Save current state */ ABEF_SAVE = STATE0; CDGH_SAVE = STATE1; /* Rounds 0-3 */ MSG = _mm_loadu_si128((const __m128i*) (data+0)); MSG0 = _mm_shuffle_epi8(MSG, MASK); MSG = _mm_add_epi32(MSG0, _mm_set_epi64x(0xE9B5DBA5B5C0FBCFULL, 0x71374491428A2F98ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); /* Rounds 4-7 */ MSG1 = _mm_loadu_si128((const __m128i*) (data+16)); MSG1 = _mm_shuffle_epi8(MSG1, MASK); MSG = _mm_add_epi32(MSG1, _mm_set_epi64x(0xAB1C5ED5923F82A4ULL, 0x59F111F13956C25BULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG0 = _mm_sha256msg1_epu32(MSG0, MSG1); /* Rounds 8-11 */ MSG2 = _mm_loadu_si128((const __m128i*) (data+32)); MSG2 = _mm_shuffle_epi8(MSG2, MASK); MSG = _mm_add_epi32(MSG2, _mm_set_epi64x(0x550C7DC3243185BEULL, 0x12835B01D807AA98ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG1 = _mm_sha256msg1_epu32(MSG1, MSG2); /* Rounds 12-15 */ MSG3 = _mm_loadu_si128((const __m128i*) (data+48)); MSG3 = _mm_shuffle_epi8(MSG3, MASK); MSG = _mm_add_epi32(MSG3, _mm_set_epi64x(0xC19BF1749BDC06A7ULL, 0x80DEB1FE72BE5D74ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG3, MSG2, 4); MSG0 = _mm_add_epi32(MSG0, TMP); MSG0 = _mm_sha256msg2_epu32(MSG0, MSG3); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG2 = _mm_sha256msg1_epu32(MSG2, MSG3); /* Rounds 16-19 */ MSG = _mm_add_epi32(MSG0, _mm_set_epi64x(0x240CA1CC0FC19DC6ULL, 0xEFBE4786E49B69C1ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG0, MSG3, 4); MSG1 = _mm_add_epi32(MSG1, TMP); MSG1 = _mm_sha256msg2_epu32(MSG1, MSG0); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG3 = _mm_sha256msg1_epu32(MSG3, MSG0); /* Rounds 20-23 */ MSG = _mm_add_epi32(MSG1, _mm_set_epi64x(0x76F988DA5CB0A9DCULL, 0x4A7484AA2DE92C6FULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG1, MSG0, 4); MSG2 = _mm_add_epi32(MSG2, TMP); MSG2 = _mm_sha256msg2_epu32(MSG2, MSG1); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG0 = _mm_sha256msg1_epu32(MSG0, MSG1); /* Rounds 24-27 */ MSG = _mm_add_epi32(MSG2, _mm_set_epi64x(0xBF597FC7B00327C8ULL, 0xA831C66D983E5152ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG2, MSG1, 4); MSG3 = _mm_add_epi32(MSG3, TMP); MSG3 = _mm_sha256msg2_epu32(MSG3, MSG2); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG1 = _mm_sha256msg1_epu32(MSG1, MSG2); /* Rounds 28-31 */ MSG = _mm_add_epi32(MSG3, _mm_set_epi64x(0x1429296706CA6351ULL, 0xD5A79147C6E00BF3ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG3, MSG2, 4); MSG0 = _mm_add_epi32(MSG0, TMP); MSG0 = _mm_sha256msg2_epu32(MSG0, MSG3); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG2 = _mm_sha256msg1_epu32(MSG2, MSG3); /* Rounds 32-35 */ MSG = _mm_add_epi32(MSG0, _mm_set_epi64x(0x53380D134D2C6DFCULL, 0x2E1B213827B70A85ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG0, MSG3, 4); MSG1 = _mm_add_epi32(MSG1, TMP); MSG1 = _mm_sha256msg2_epu32(MSG1, MSG0); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG3 = _mm_sha256msg1_epu32(MSG3, MSG0); /* Rounds 36-39 */ MSG = _mm_add_epi32(MSG1, _mm_set_epi64x(0x92722C8581C2C92EULL, 0x766A0ABB650A7354ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG1, MSG0, 4); MSG2 = _mm_add_epi32(MSG2, TMP); MSG2 = _mm_sha256msg2_epu32(MSG2, MSG1); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG0 = _mm_sha256msg1_epu32(MSG0, MSG1); /* Rounds 40-43 */ MSG = _mm_add_epi32(MSG2, _mm_set_epi64x(0xC76C51A3C24B8B70ULL, 0xA81A664BA2BFE8A1ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG2, MSG1, 4); MSG3 = _mm_add_epi32(MSG3, TMP); MSG3 = _mm_sha256msg2_epu32(MSG3, MSG2); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG1 = _mm_sha256msg1_epu32(MSG1, MSG2); /* Rounds 44-47 */ MSG = _mm_add_epi32(MSG3, _mm_set_epi64x(0x106AA070F40E3585ULL, 0xD6990624D192E819ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG3, MSG2, 4); MSG0 = _mm_add_epi32(MSG0, TMP); MSG0 = _mm_sha256msg2_epu32(MSG0, MSG3); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG2 = _mm_sha256msg1_epu32(MSG2, MSG3); /* Rounds 48-51 */ MSG = _mm_add_epi32(MSG0, _mm_set_epi64x(0x34B0BCB52748774CULL, 0x1E376C0819A4C116ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG0, MSG3, 4); MSG1 = _mm_add_epi32(MSG1, TMP); MSG1 = _mm_sha256msg2_epu32(MSG1, MSG0); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); MSG3 = _mm_sha256msg1_epu32(MSG3, MSG0); /* Rounds 52-55 */ MSG = _mm_add_epi32(MSG1, _mm_set_epi64x(0x682E6FF35B9CCA4FULL, 0x4ED8AA4A391C0CB3ULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG1, MSG0, 4); MSG2 = _mm_add_epi32(MSG2, TMP); MSG2 = _mm_sha256msg2_epu32(MSG2, MSG1); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); /* Rounds 56-59 */ MSG = _mm_add_epi32(MSG2, _mm_set_epi64x(0x8CC7020884C87814ULL, 0x78A5636F748F82EEULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); TMP = _mm_alignr_epi8(MSG2, MSG1, 4); MSG3 = _mm_add_epi32(MSG3, TMP); MSG3 = _mm_sha256msg2_epu32(MSG3, MSG2); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); /* Rounds 60-63 */ MSG = _mm_add_epi32(MSG3, _mm_set_epi64x(0xC67178F2BEF9A3F7ULL, 0xA4506CEB90BEFFFAULL)); STATE1 = _mm_sha256rnds2_epu32(STATE1, STATE0, MSG); MSG = _mm_shuffle_epi32(MSG, 0x0E); STATE0 = _mm_sha256rnds2_epu32(STATE0, STATE1, MSG); /* Combine state */ STATE0 = _mm_add_epi32(STATE0, ABEF_SAVE); STATE1 = _mm_add_epi32(STATE1, CDGH_SAVE); data += 64; length -= 64; } TMP = _mm_shuffle_epi32(STATE0, 0x1B); /* FEBA */ STATE1 = _mm_shuffle_epi32(STATE1, 0xB1); /* DCHG */ STATE0 = _mm_blend_epi16(TMP, STATE1, 0xF0); /* DCBA */ STATE1 = _mm_alignr_epi8(STATE1, TMP, 8); /* ABEF */ /* Save state */ _mm_storeu_si128((__m128i*) &state[0], STATE0); _mm_storeu_si128((__m128i*) &state[4], STATE1); } #if defined(TEST_MAIN) #include <stdio.h> #include <string.h> int main(int argc, char* argv[]) { /* empty message with padding */ uint8_t message[64]; memset(message, 0x00, sizeof(message)); message[0] = 0x80; /* initial state */ uint32_t state[8] = { 0x6a09e667, 0xbb67ae85, 0x3c6ef372, 0xa54ff53a, 0x510e527f, 0x9b05688c, 0x1f83d9ab, 0x5be0cd19 }; sha256_process_x86(state, message, sizeof(message)); const uint8_t b1 = (uint8_t)(state[0] >> 24); const uint8_t b2 = (uint8_t)(state[0] >> 16); const uint8_t b3 = (uint8_t)(state[0] >> 8); const uint8_t b4 = (uint8_t)(state[0] >> 0); const uint8_t b5 = (uint8_t)(state[1] >> 24); const uint8_t b6 = (uint8_t)(state[1] >> 16); const uint8_t b7 = (uint8_t)(state[1] >> 8); const uint8_t b8 = (uint8_t)(state[1] >> 0); /* e3b0c44298fc1c14... */ printf("SHA256 hash of empty message: "); printf("%02X%02X%02X%02X%02X%02X%02X%02X...\n", b1, b2, b3, b4, b5, b6, b7, b8); int success = ((b1 == 0xE3) && (b2 == 0xB0) && (b3 == 0xC4) && (b4 == 0x42) && (b5 == 0x98) && (b6 == 0xFC) && (b7 == 0x1C) && (b8 == 0x14)); if (success) printf("Success!\n"); else printf("Failure!\n"); return (success != 0 ? 0 : 1); } #endifВот только тест почему-то не проходит, надо будет разобраться, но время занимает ровно столько же, сколько и OpenSSL.
А собственно OpenSSL, что в тесте выше использовалась, как-то так устроена:
OpenSSL
#include <openssl/evp.h> // OpenSSL SHA256DLL_API int fnSHA256OPENSSL(uint8_t* src, size_t n, uint8_t* dst) { EVP_MD_CTX* mdctx; const EVP_MD* md; unsigned char md_value[EVP_MAX_MD_SIZE]; unsigned int md_len; md = EVP_get_digestbyname("SHA256"); if (!md) return -1; mdctx = EVP_MD_CTX_new(); if (!mdctx) return -2; if (!EVP_DigestInit_ex2(mdctx, md, NULL)) { EVP_MD_CTX_free(mdctx); return -3; } if (!EVP_DigestUpdate(mdctx, src, n)) { EVP_MD_CTX_free(mdctx); return -4; } if (!EVP_DigestFinal_ex(mdctx, md_value, &md_len)) { EVP_MD_CTX_free(mdctx); return -5; } EVP_MD_CTX_free(mdctx); memcpy_s(dst, 32, md_value, md_len); return md_len; }KILYAV Автор
16.11.2024 22:46В примере с Если процессор поддерживает SHA256RNDS2, SHA256MSG1 и SHA256MSG2, есть момент который я хотел попробовать, а именно непосредственную загрузку коэффициентов в регистры не из памяти, а непосредственно командным способом.
Ну и если задуматься то весь этот код по сути ассемблерный, но обернутый в С-подобный синтаксис, что позволяет значительно легче интегрировать его в целевой проект.
Возможно еще один способ который позволяет их коду быть быстрей, это какой то хитрый способ заставить проц грузить данные в кеш заблаговременно.
AndreyDmitriev
16.11.2024 22:46весь этот код по сути ассемблерный, но обернутый в С-подобный синтаксис,
В обиходе это Интринсиками называется. Intel Intrinsics Guide. Штука удобная, потому что во-первых можно комбинировать команды:
й MSG = _mm_add_epi32(MSG1, _mm_set_epi64x(0xAB1..., 0x59F...));А во-вторых, заводить переменные не заботясь о регистрах, которых вечно не хватает, компилятор сам раскидает как надо:
__m128i STATE0, STATE1; __m128i MSG, TMP; __m128i MSG0, MSG1, MSG2, MSG3; __m128i ABEF_SAVE, CDGH_SAVE; const __m128i MASK = _mm_set_epi64x(Из недостатков - постоянно вкорячивает команды обращения к невыровненной памяти, даже если я сто раз ему сказал, что память выровнена (я занимаюсь обработкой изображений и обычно выравниваю аж на границу страницы, суть 4096 байт). Впрочем всегда можно выгнать компилят в ассемблерный листинг и дальше тонко настраивать уже на ассемблере, но это редко бывает нужно, одгако заглянуть в листинг всегда полезно.
хитрый способ заставить проц грузить данные в кеш заблаговременно
Ну да, PREFETCH, PREFETCHNTA, PREFETCHT0 — PREFETCHT2 называется. Но на современных процессорах заметного влияния почти не оказывает, а позапрошлым летом упражнялся, разница гомеопатическая. Говорят надо примерно за сотню-другую тактов до обращения к памяти префетч дёрнуть, но я не увидел разницы, как бы не старался.
Можно ещё профилировщиком Intel VTune пробежать, по крайней мере он "горячие точки" покажет. У Вас бóльшая часть времени вот где-то здесь проходит:
Эх, а раньше можно было увеличить производительность просто перестановкой команд для улучшения ковейеризации, но сейчас всё стало сложнее, кроме того нынче в основном производительность за счёт многоядерности вытягивается.
AndreyDmitriev
16.11.2024 22:46попробовать, а именно непосредственную загрузку коэффициентов в регистры не из памяти, а непосредственно командным способом.
Кстати, для "тонкой" профилировки кода с подсчётом тактов можно воспользоваться комбинацией cpuid/rdtsc.
Я обычно заворачиваю код в DLL и на ассемблере делаю как-то так:
align 16 EXPORT fnRtdsc_empty fnRtdsc_empty PROC mov r10, rcx ; x64 calling convention push rsi push rdi push rbx push rcx push rdx cpuid ; force all previous instructions to complete ; this will reset rax...rdx registerss! rdtsc ; read time stamp counter mov edi, eax ; save start EAX for later mov esi, edx ; save start EDX for later L0: ; CODE to be tested ; вставлять сюда dec r10 jnz L0 cpuid ; wait for FDIV to complete before RDTSC rdtsc ; read time stamp counter sub eax, edi ; subtract the most recent CPU ticks from the original CPU ticks sbb edx, esi ; now, subtract with borrow shl rax, 32 shrd rax, rdx, 32 pop rdx pop rcx pop rbx pop rdi pop rsi RET ;returned through RAX ENDP fnRtdsc_emptyЭта функция вызывается
int diff = fnRtdsc_empty(4096);Параметр - это сколько раз надо внутренний цикл крутить. Дальше я кручу эту функцию этак сотню тысяч раз и выбираю минимальное время.
Теперь если я скажем хочу посмотреть какой код быстрее, вот так:
L1: ; CODE add rax, rax add rax, rax add rax, rax add rax, rax ; тут латентность 4 такта на 4 сложения dec r10 jnz L1Или этак:
L2: ; CODE add rax, rax add rbx, rbx add rcx, rcx add rdx, rdx ; а тут всё параллельно за один такт dec r10 jnz L2То я сразу увижу, что первый заметно медленнее.
Конечно совсем точного значения количества тактов не получить, и от запуска к запуску будет немножко плавать, но если надо измерять на уровне сотен тактов то норм.
KILYAV Автор
16.11.2024 22:46Я использую
rdtscдля измерения в тактах, а вотcpuidя использовал буквально один раз в незаконченном коде как селектор выбора оптимального кода для текущей машины.AndreyDmitriev
16.11.2024 22:46cpuidэто маленький "трюк" для "остановки" конвейеров, так то можно иrdtscобойтись, просто команды могут параллелиться, так что их иногда парой применяют.
sena
а тесты на производительность, интересно же
AndreyDmitriev
Я не поленился и сравнил с LabVIEW 2024Q3 и OpenSSL 3.4.0 - смотрите коммент чуть ниже.