noloader
commented
6 years ago @pcordes,
Thanks for the analysis. If you want to workup a patch to test your proposed changes then I am happy to test it.
I had some time to look at SHA512_Round and untangle what is going on (I think). Here is what is happening at a high level in pseudo code. Recall SHA-512 uses 80 rounds. Rounds 0-15 mix the message and state. Rounds 16-79 mix state. The end state is the hash (or additional messages can be processed).
void SHA512_HashBlock_SSE2(state, message)
{
DO_PROLOGUE
round=0
jmp PREPARE_RNDS_00_15
SHA152_Round
... // process state
return
PREPARE_RNDS_00_15
... // arrange state+msg
if (++round != 16)
call SHA152_Round
PREPARE_RNDS_16_79
... // arrange state alone
if (++round != 80)
call SHA152_Round
DO_EPILOGUE
}So it looks like Wei is using the call to perform the branch. The push of eip and return ensures the branch back to the body (either PREPARE_RNDS_00_15 or PREPARE_RNDS_16_79) has the right address.
Without the call and return the library would need to manage the return address and branch to the return address from SHA152_Round. The return address would land in either PREPARE_RNDS_00_15 or PREPARE_RNDS_16_79.
I'm guessing Wei chose this pattern for two or three reasons. First is simplicity. The call and return is pretty easy. Second is register pressures. Especially on i386 where registers are scarce. Third is performance on a critical path. SHA512_Round is the heart of the algorithm.
Looking at the routine I can't tell if register pressure applies in this case. I think it is suffering register pressure for i386. It looks like EAX-EDX, ESI and EDI are used in the routine.
If a freestanding SHA512_Round was added then it would be on the critical path. The function would be called 80 times, the epilogue takes 7 instructions, and the prologue takes 3 instructions. If my calculations are correct then the freestanding version of the function would execute an additional 800 instructions on a critical path.
Now, onto remediations. We can't add a freestanding SHA512_Round due to the performance hit. That means we need to manage the return branch from SHA512_Round. My question is, what do you recommend to manage the return address? That is, how do we manage GO_BACK efficiently?
void SHA512_HashBlock_SSE2(state, message)
{
DO_PROLOGUE
round=0
jmp PREPARE_RNDS_00_15
SHA152_Round
... // process state
branch GO_BACK
PREPARE_RNDS_00_15
... // arrange state+msg
if (++round != 16)
branch SHA152_Round
PREPARE_RNDS_16_79
... // arrange state alone
if (++round != 80)
branch SHA152_Round
DO_EPILOGUE
}One of the things that concerns me is the code uses EBX so we may not be able to count on the PIC register being valid until the asm is complete. I think that means a temporary could encounter troubles:
void SHA512_HashBlock_SSE2(state, message)
{
void* addr;
__asm__
(
SHA152_Round
... // process state
jmp addr
PREPARE_RNDS_00_15
... // arrange state+msg
if (++round != 16)
addr = PREPARE_RNDS_16_79
jmp SHA152_Round
PREPARE_RNDS_16_79
... // arrange state alone
if (++round != 80)
addr = PREPARE_RNDS_16_79
jmp SHA152_Round
);
}
pcordes
https://github.com/weidai11/cryptopp/blob/28e20d6e5f920e48688c71456f9392a4a5f78135/sha.cpp#L963
looks like it's mostly for 32-bit mode, but it's also used for x86-64 x32.
push rbxis not safe in 64-bit mode: you clobber the red-zone without telling the compiler, potentially breaking things if this inlines into a function with any locals, or even without optimization if this functions spills its args. (https://stackoverflow.com/questions/34520013/using-base-pointer-register-in-c-inline-asm)Better to simply declare a clobber on ebx and ask for the input you want in
"b"instead of"a", and avoid a uselessmov. (gcc4.9 and earlier don't support EBX as an operand with-m32 -fPIC, but gcc5 has no problem: https://godbolt.org/g/Ddzp1o).AS2( lea ebx, SHA512_K)This line only runs for MSVC 32-bit mode, so it can't use RIP-relative addressing. LEA is pointless, usemov ebx, OFFSET SHA512_Kto save a byte.Inside
#if CRYPTOPP_BOOL_X32, you should use RSP instead of ESP. RSP is always correctly zero-extended, so you can save the address-size prefix. You could probably hack around that with a#definefor ESP, and maybe another like EDI_PTR or something that expands to EDI for 32-bit mode, or RDI for 64-bit mode. x32 is unpopular enough that you can kind of justify emitting worse machine code for it just to gain some source convenience, though, when it's just 1 extra byte in a few places with no performance penalty other than code-size.More importantly, MMX looks pointless here. x32 has 64-bit integer registers, and plenty of them. It also has 16 XMM registers.
MMX
paddqwill hurt a lot on Bulldozer-family vs. integeradd(because each pair of cores shares one SIMD unit), and maybe hurt slightly on most Intel whereaddruns on more ports. The extramovq2dqinstructions don't help either.This is weird; is it optimized to avoid 16-byte unaligned stores or something? On modern HW,
movupswill be better. On Nehalem and newer,movhps [esi+8], xmm0is a single uop (but a singlemovupsis probably still better even on a cache-line split, on CPUs where its single-uop).movhps-stores are 2 uops (including a shuffle) on Core2, Bulldozer-family, and Ryzen, though. So probably justmovupsunless you really care about Core2 / K8 where that's slower even if the address is aligned.As I commented on the recent commit, don't define a function inside another function. Define it separately, e.g. with an
asm()statement at global scope.