Subject: Re: Linus' sha1 is much faster!

From: Giuseppe Scrivano <[email-masked]>
Date: Sun, 16 Aug 2009 21:25:11 +0200

Hi Pádraig,

I tried to reproduce your results but I wasn't able to do it.  The
biggest difference on a 300MB file I noticed was approximately 15% using
on both implementations -O2, and 5% using -O3.
My GCC version is "gcc (Debian 4.3.3-14) 4.3.3" and the CPU is: Intel(R)
Pentium(R) D CPU 3.20GHz.

I also spent some time trying to improve the gnulib SHA1 implementation
and it seems a lookup table can improve things a bit.

Can you please try the patch that I have attached and tell me which
performance difference (if any) you get?

Thanks,
Giuseppe

>>From b975a5e0849eaa46e5cf410c5bf6e2308f044d61 Mon Sep 17 00:00:00 2001
From: Giuseppe Scrivano <[email-masked]>
Date: Sun, 16 Aug 2009 20:53:54 +0200
Subject: [PATCH] SHA1: use a lookup table for faster hashing

* lib/sha1.c (struct sha1_pre): New member.
* lib/sha1.c (sha1_process_block): Use the lookup table to quickly find
indices to use in the current round.
---
 lib/sha1.c |  160 ++++++++++++++++++++++++++++++++++-------------------------
 1 files changed, 92 insertions(+), 68 deletions(-)

diff --git a/lib/sha1.c b/lib/sha1.c
index 9c6c7ae..ec18ba7 100644
--- a/lib/sha1.c
+++ b/lib/sha1.c
@@ -283,6 +283,32 @@ sha1_process_bytes (const void *buffer, size_t len, struct sha1_ctx *ctx)
 #define F3(B,C,D) ( ( B & C ) | ( D & ( B | C ) ) )
 #define F4(B,C,D) (B ^ C ^ D)
 
+struct lookup_t
+{
+  unsigned char l1 : 4;
+  unsigned char l2 : 4;
+  unsigned char l3 : 4;
+  unsigned char l4 : 4;
+};
+
+const static struct lookup_t
+sha1_pre[16] = {{(0 - 3) & 0x0f, (0 - 8) & 0x0f, (0 - 14) & 0x0f},
+                {(1 - 3) & 0x0f, (1 - 8) & 0x0f, (1 - 14) & 0x0f},
+                {(2 - 3) & 0x0f, (2 - 8) & 0x0f, (2 - 14) & 0x0f},
+                {(3 - 3) & 0x0f, (3 - 8) & 0x0f, (3 - 14) & 0x0f},
+                {(4 - 3) & 0x0f, (4 - 8) & 0x0f, (4 - 14) & 0x0f},
+                {(5 - 3) & 0x0f, (5 - 8) & 0x0f, (5 - 14) & 0x0f},
+                {(6 - 3) & 0x0f, (6 - 8) & 0x0f, (6 - 14) & 0x0f},
+                {(7 - 3) & 0x0f, (7 - 8) & 0x0f, (7 - 14) & 0x0f},
+                {(8 - 3) & 0x0f, (8 - 8) & 0x0f, (8 - 14) & 0x0f},
+                {(9 - 3) & 0x0f, (9 - 8) & 0x0f, (9 - 14) & 0x0f},
+                {(10 - 3) & 0x0f, (10 - 8) & 0x0f, (10 - 14) & 0x0f},
+                {(11 - 3) & 0x0f, (11 - 8) & 0x0f, (11 - 14) & 0x0f},
+                {(12 - 3) & 0x0f, (12 - 8) & 0x0f, (12 - 14) & 0x0f},
+                {(13 - 3) & 0x0f, (13 - 8) & 0x0f, (13 - 14) & 0x0f},
+                {(14 - 3) & 0x0f, (14 - 8) & 0x0f, (14 - 14) & 0x0f},
+                {(15 - 3) & 0x0f, (15 - 8) & 0x0f, (15 - 14) & 0x0f}};
+
 /* Process LEN bytes of BUFFER, accumulating context into CTX.
    It is assumed that LEN % 64 == 0.
    Most of this code comes from GnuPG's cipher/sha1.c.  */
@@ -309,9 +335,8 @@ sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
 
 #define rol(x, n) (((x) << (n)) | ((uint32_t) (x) >> (32 - (n))))
 
-#define M(I) ( tm =   x[I&0x0f] ^ x[(I-14)&0x0f] \
-		    ^ x[(I-8)&0x0f] ^ x[(I-3)&0x0f] \
-	       , (x[I&0x0f] = rol(tm, 1)) )
+#define M(I) (x[I] = rol (x[sha1_pre[I].l1] ^ x[sha1_pre[I].l2] \
+                          ^ x[sha1_pre[I].l3] ^ x[I], 1))
 
 #define R(A,B,C,D,E,F,K,M)  do { E += rol( A, 5 )     \
 				      + F( B, C, D )  \
@@ -322,7 +347,6 @@ sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
 
   while (words < endp)
     {
-      uint32_t tm;
       int t;
       for (t = 0; t < 16; t++)
 	{
@@ -346,70 +370,70 @@ sha1_process_block (const void *buffer, size_t len, struct sha1_ctx *ctx)
       R( c, d, e, a, b, F1, K1, x[13] );
       R( b, c, d, e, a, F1, K1, x[14] );
       R( a, b, c, d, e, F1, K1, x[15] );
-      R( e, a, b, c, d, F1, K1, M(16) );
-      R( d, e, a, b, c, F1, K1, M(17) );
-      R( c, d, e, a, b, F1, K1, M(18) );
-      R( b, c, d, e, a, F1, K1, M(19) );
-      R( a, b, c, d, e, F2, K2, M(20) );
-      R( e, a, b, c, d, F2, K2, M(21) );
-      R( d, e, a, b, c, F2, K2, M(22) );
-      R( c, d, e, a, b, F2, K2, M(23) );
-      R( b, c, d, e, a, F2, K2, M(24) );
-      R( a, b, c, d, e, F2, K2, M(25) );
-      R( e, a, b, c, d, F2, K2, M(26) );
-      R( d, e, a, b, c, F2, K2, M(27) );
-      R( c, d, e, a, b, F2, K2, M(28) );
-      R( b, c, d, e, a, F2, K2, M(29) );
-      R( a, b, c, d, e, F2, K2, M(30) );
-      R( e, a, b, c, d, F2, K2, M(31) );
-      R( d, e, a, b, c, F2, K2, M(32) );
-      R( c, d, e, a, b, F2, K2, M(33) );
-      R( b, c, d, e, a, F2, K2, M(34) );
-      R( a, b, c, d, e, F2, K2, M(35) );
-      R( e, a, b, c, d, F2, K2, M(36) );
-      R( d, e, a, b, c, F2, K2, M(37) );
-      R( c, d, e, a, b, F2, K2, M(38) );
-      R( b, c, d, e, a, F2, K2, M(39) );
-      R( a, b, c, d, e, F3, K3, M(40) );
-      R( e, a, b, c, d, F3, K3, M(41) );
-      R( d, e, a, b, c, F3, K3, M(42) );
-      R( c, d, e, a, b, F3, K3, M(43) );
-      R( b, c, d, e, a, F3, K3, M(44) );
-      R( a, b, c, d, e, F3, K3, M(45) );
-      R( e, a, b, c, d, F3, K3, M(46) );
-      R( d, e, a, b, c, F3, K3, M(47) );
-      R( c, d, e, a, b, F3, K3, M(48) );
-      R( b, c, d, e, a, F3, K3, M(49) );
-      R( a, b, c, d, e, F3, K3, M(50) );
-      R( e, a, b, c, d, F3, K3, M(51) );
-      R( d, e, a, b, c, F3, K3, M(52) );
-      R( c, d, e, a, b, F3, K3, M(53) );
-      R( b, c, d, e, a, F3, K3, M(54) );
-      R( a, b, c, d, e, F3, K3, M(55) );
-      R( e, a, b, c, d, F3, K3, M(56) );
-      R( d, e, a, b, c, F3, K3, M(57) );
-      R( c, d, e, a, b, F3, K3, M(58) );
-      R( b, c, d, e, a, F3, K3, M(59) );
-      R( a, b, c, d, e, F4, K4, M(60) );
-      R( e, a, b, c, d, F4, K4, M(61) );
-      R( d, e, a, b, c, F4, K4, M(62) );
-      R( c, d, e, a, b, F4, K4, M(63) );
-      R( b, c, d, e, a, F4, K4, M(64) );
-      R( a, b, c, d, e, F4, K4, M(65) );
-      R( e, a, b, c, d, F4, K4, M(66) );
-      R( d, e, a, b, c, F4, K4, M(67) );
-      R( c, d, e, a, b, F4, K4, M(68) );
-      R( b, c, d, e, a, F4, K4, M(69) );
-      R( a, b, c, d, e, F4, K4, M(70) );
-      R( e, a, b, c, d, F4, K4, M(71) );
-      R( d, e, a, b, c, F4, K4, M(72) );
-      R( c, d, e, a, b, F4, K4, M(73) );
-      R( b, c, d, e, a, F4, K4, M(74) );
-      R( a, b, c, d, e, F4, K4, M(75) );
-      R( e, a, b, c, d, F4, K4, M(76) );
-      R( d, e, a, b, c, F4, K4, M(77) );
-      R( c, d, e, a, b, F4, K4, M(78) );
-      R( b, c, d, e, a, F4, K4, M(79) );
+      R( e, a, b, c, d, F1, K1, M( 0) );
+      R( d, e, a, b, c, F1, K1, M( 1) );
+      R( c, d, e, a, b, F1, K1, M( 2) );
+      R( b, c, d, e, a, F1, K1, M( 3) );
+      R( a, b, c, d, e, F2, K2, M( 4) );
+      R( e, a, b, c, d, F2, K2, M( 5) );
+      R( d, e, a, b, c, F2, K2, M( 6) );
+      R( c, d, e, a, b, F2, K2, M( 7) );
+      R( b, c, d, e, a, F2, K2, M( 8) );
+      R( a, b, c, d, e, F2, K2, M( 9) );
+      R( e, a, b, c, d, F2, K2, M(10) );
+      R( d, e, a, b, c, F2, K2, M(11) );
+      R( c, d, e, a, b, F2, K2, M(12) );
+      R( b, c, d, e, a, F2, K2, M(13) );
+      R( a, b, c, d, e, F2, K2, M(14) );
+      R( e, a, b, c, d, F2, K2, M(15) );
+      R( d, e, a, b, c, F2, K2, M( 0) );
+      R( c, d, e, a, b, F2, K2, M( 1) );
+      R( b, c, d, e, a, F2, K2, M( 2) );
+      R( a, b, c, d, e, F2, K2, M( 3) );
+      R( e, a, b, c, d, F2, K2, M( 4) );
+      R( d, e, a, b, c, F2, K2, M( 5) );
+      R( c, d, e, a, b, F2, K2, M( 6) );
+      R( b, c, d, e, a, F2, K2, M( 7) );
+      R( a, b, c, d, e, F3, K3, M( 8) );
+      R( e, a, b, c, d, F3, K3, M( 9) );
+      R( d, e, a, b, c, F3, K3, M(10) );
+      R( c, d, e, a, b, F3, K3, M(11) );
+      R( b, c, d, e, a, F3, K3, M(12) );
+      R( a, b, c, d, e, F3, K3, M(13) );
+      R( e, a, b, c, d, F3, K3, M(14) );
+      R( d, e, a, b, c, F3, K3, M(15) );
+      R( c, d, e, a, b, F3, K3, M( 0) );
+      R( b, c, d, e, a, F3, K3, M( 1) );
+      R( a, b, c, d, e, F3, K3, M( 2) );
+      R( e, a, b, c, d, F3, K3, M( 3) );
+      R( d, e, a, b, c, F3, K3, M( 4) );
+      R( c, d, e, a, b, F3, K3, M( 5) );
+      R( b, c, d, e, a, F3, K3, M( 6) );
+      R( a, b, c, d, e, F3, K3, M( 7) );
+      R( e, a, b, c, d, F3, K3, M( 8) );
+      R( d, e, a, b, c, F3, K3, M( 9) );
+      R( c, d, e, a, b, F3, K3, M(10) );
+      R( b, c, d, e, a, F3, K3, M(11) );
+      R( a, b, c, d, e, F4, K4, M(12) );
+      R( e, a, b, c, d, F4, K4, M(13) );
+      R( d, e, a, b, c, F4, K4, M(14) );
+      R( c, d, e, a, b, F4, K4, M(15) );
+      R( b, c, d, e, a, F4, K4, M( 0) );
+      R( a, b, c, d, e, F4, K4, M( 1) );
+      R( e, a, b, c, d, F4, K4, M( 2) );
+      R( d, e, a, b, c, F4, K4, M( 3) );
+      R( c, d, e, a, b, F4, K4, M( 4) );
+      R( b, c, d, e, a, F4, K4, M( 5) );
+      R( a, b, c, d, e, F4, K4, M( 6) );
+      R( e, a, b, c, d, F4, K4, M( 7) );
+      R( d, e, a, b, c, F4, K4, M( 8) );
+      R( c, d, e, a, b, F4, K4, M( 9) );
+      R( b, c, d, e, a, F4, K4, M(10) );
+      R( a, b, c, d, e, F4, K4, M(11) );
+      R( e, a, b, c, d, F4, K4, M(12) );
+      R( d, e, a, b, c, F4, K4, M(13) );
+      R( c, d, e, a, b, F4, K4, M(14) );
+      R( b, c, d, e, a, F4, K4, M(15) );
 
       a = ctx->A += a;
       b = ctx->B += b;
-- 
1.6.3.3