Re: x86 asm SHA1 (draft)

From: linux@horizon.com <linux@horizon.com>
Date: Jun 24, 2006, 09:20 UTC
Message-ID: <20060624092026.31029.qmail@science.horizon.com>
In-Reply-To: <7vfyhv11ej.fsf@assigned-by-dhcp.cox.net>

> OK.  I somehow got an impression that your two versions had
> quite different performance characteristics on G4 and G5 and
> there was a real choice.  If they are between a few per-cent,
> then I agree it is not worth doing at all.

My apologies for being unclear.

The place where a noticeable (if not disastrous) difference can appear is x86, which has a lot more models with "interesting" performance characteristics. In particular, Intel is fond of building CPUs with a very small "sweet spot".

The openssl SHA1 code had to be reworked to not suck on a P4, with the resultant performance change:

# compared with original compared with Intel cc # assembler impl. generated code # Pentium -16% +48% # PIII/AMD +8% +16% # P4 +85%(!) +45%

The original code had the most popular round (what I call ROUND_MIX(F2,...))) implemented as follows, with single-uop instructions (no load+op) scheduled for the Pentium pipeline: (A..E are working variables, S and T are temps)

	movl    16(%esp),S	U  \
        movl    24(%esp),T	 V  \
        xorl    S,T		U    \
        movl    48(%esp),S	 V    > "MIX", pentium-optimized
        xorl    S,T		U    /
        movl    4(%esp),S	 V  /
        xorl    S,T		U  /
        movl	B,S		 V
	roll	$1,T		U	Rotate of mix (SHA0 -> SHA1 fix)
	xor	C,S		 V
	mov	T,16(%esp)	U	Store back W[i]
	xor	D,S		 V	Finish computing F(B,C,D) = B^C^D
	lea	K(T,E),E	U	Add K and W[i] to E
	mov	A,T		 V
	roll	$5,T		UV
	rorl	$1,B		U
	add	S,E		 V
	rorl	$1,B		U
	add	T,E		 V

While the P4-optimized version goes:
	movl	B,S
	movl	16(%esp),T
	rorl	$2,B
	xorl	24(%esp),T
	xorl	C,S
	xorl	48(%esp),T
	xorl	D,S		This is F(B,C,D) = B^C^D
	xorl	4(%esp),T
	roll	$1,T		Rotate of mix (SHA0 -> SHA1 fix)
	addl	S,E
	movl	T,16(%esp)
	movl	A,S
	roll	$5,S
	lea	K(E,T),E
	add	S,E

(The original code actually rotates the working variables around 6 registers, not 5, but I've rearranged the last couple of instructions to rotate around 5.)