Boost performance of SHA-512 and SHA-256.
authorWerner Koch <wk@gnupg.org>
Fri, 11 Dec 2009 16:32:04 +0000 (16:32 +0000)
committerWerner Koch <wk@gnupg.org>
Fri, 11 Dec 2009 16:32:04 +0000 (16:32 +0000)
NEWS
cipher/ChangeLog
cipher/sha256.c
cipher/sha512.c
tests/benchmark.c

diff --git a/NEWS b/NEWS
index f97f0e2..a4593a8 100644 (file)
--- a/NEWS
+++ b/NEWS
@@ -11,6 +11,9 @@ Noteworthy changes in version 1.5.x (unreleased)
 
  * Fix a hang on some W2000 machines.
 
+ * Boost SHA-512 performance by 30% on ia32 boxes and gcc 4.3; SHA-256
+   goes up by 25%.
+
  * Interface changes relative to the 1.4.2 release:
  ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
  GCRY_CIPHER_MODE_AESWRAP   NEW.
index cd29838..b6ba4d4 100644 (file)
@@ -1,3 +1,14 @@
+2009-12-11  Werner Koch  <wk@g10code.com>
+
+       * sha256.c (Cho, Maj, Sum0, Sum1): Turn macros into inline
+       functions.
+       (transform): Partly unroll to interweave the chain variables
+
+       * sha512.c (ROTR, Ch, Maj, Sum0, Sum1): Turn macros into inline
+       functions.
+       (transform): Partly Unroll to interweave the chain variables.
+       Suggested by Christian Grothoff.
+
 2009-12-10  Werner Koch  <wk@g10code.com>
 
        * Makefile.am (o_flag_munging): New.
index e0148da..afb0805 100644 (file)
@@ -94,10 +94,6 @@ sha224_init (void *context)
 /*
   Transform the message X which consists of 16 32-bit-words. See FIPS
   180-2 for details.  */
-#define Cho(x,y,z) (z ^ (x & (y ^ z)))      /* (4.2) same as SHA-1's F1 */
-#define Maj(x,y,z) ((x & y) | (z & (x|y)))  /* (4.3) same as SHA-1's F3 */
-#define Sum0(x) (ror ((x), 2) ^ ror ((x), 13) ^ ror ((x), 22))  /* (4.4) */
-#define Sum1(x) (ror ((x), 6) ^ ror ((x), 11) ^ ror ((x), 25))  /* (4.5) */
 #define S0(x) (ror ((x), 7) ^ ror ((x), 18) ^ ((x) >> 3))       /* (4.6) */
 #define S1(x) (ror ((x), 17) ^ ror ((x), 19) ^ ((x) >> 10))     /* (4.7) */
 #define R(a,b,c,d,e,f,g,h,k,w) do                                 \
@@ -113,6 +109,35 @@ sha224_init (void *context)
             b = a;                                                \
             a = t1 + t2;                                          \
           } while (0)
+
+/* (4.2) same as SHA-1's F1.  */
+static inline u32
+Cho (u32 x, u32 y, u32 z)
+{
+  return (z ^ (x & (y ^ z)));
+}
+
+/* (4.3) same as SHA-1's F3 */
+static inline u32
+Maj (u32 x, u32 y, u32 z)
+{
+  return ((x & y) | (z & (x|y)));
+}
+  
+/* (4.4) */
+static inline u32
+Sum0 (u32 x)
+{
+  return (ror (x, 2) ^ ror (x, 13) ^ ror (x, 22));
+}
+
+/* (4.5) */
+static inline u32
+Sum1 (u32 x)
+{
+  return (ror (x, 6) ^ ror (x, 11) ^ ror (x, 25));
+}
+
  
 static void
 transform (SHA256_CONTEXT *hd, const unsigned char *data)
@@ -171,8 +196,55 @@ transform (SHA256_CONTEXT *hd, const unsigned char *data)
   for (; i < 64; i++)
     w[i] = S1(w[i-2]) + w[i-7] + S0(w[i-15]) + w[i-16];
 
-  for (i=0; i < 64; i++)
-    R(a,b,c,d,e,f,g,h,K[i],w[i]);
+  for (i=0; i < 64;)
+    {
+#if 0
+      R(a,b,c,d,e,f,g,h,K[i],w[i]);
+      i++;
+#else
+      t1 = h + Sum1 (e) + Cho (e, f, g) + K[i] + w[i];   
+      t2 = Sum0 (a) + Maj (a, b, c);
+      d += t1;
+      h  = t1 + t2;
+
+      t1 = g + Sum1 (d) + Cho (d, e, f) + K[i+1] + w[i+1];
+      t2 = Sum0 (h) + Maj (h, a, b);
+      c += t1;
+      g  = t1 + t2;
+
+      t1 = f + Sum1 (c) + Cho (c, d, e) + K[i+2] + w[i+2];
+      t2 = Sum0 (g) + Maj (g, h, a);
+      b += t1;
+      f  = t1 + t2;
+
+      t1 = e + Sum1 (b) + Cho (b, c, d) + K[i+3] + w[i+3];
+      t2 = Sum0 (f) + Maj (f, g, h);
+      a += t1;
+      e  = t1 + t2;
+
+      t1 = d + Sum1 (a) + Cho (a, b, c) + K[i+4] + w[i+4];
+      t2 = Sum0 (e) + Maj (e, f, g);
+      h += t1;
+      d  = t1 + t2;
+
+      t1 = c + Sum1 (h) + Cho (h, a, b) + K[i+5] + w[i+5];
+      t2 = Sum0 (d) + Maj (d, e, f);
+      g += t1;
+      c  = t1 + t2;
+
+      t1 = b + Sum1 (g) + Cho (g, h, a) + K[i+6] + w[i+6];
+      t2 = Sum0 (c) + Maj (c, d, e);
+      f += t1;
+      b  = t1 + t2;
+
+      t1 = a + Sum1 (f) + Cho (f, g, h) + K[i+7] + w[i+7];
+      t2 = Sum0 (b) + Maj (b, c, d);
+      e += t1;
+      a  = t1 + t2;
+
+      i += 8;
+#endif
+    }
 
   hd->h0 += a;
   hd->h1 += b;
@@ -183,10 +255,6 @@ transform (SHA256_CONTEXT *hd, const unsigned char *data)
   hd->h6 += g;
   hd->h7 += h;
 }
-#undef Cho
-#undef Maj
-#undef Sum0
-#undef Sum1
 #undef S0
 #undef S1
 #undef R
index bbbd4c5..1951c32 100644 (file)
@@ -98,6 +98,36 @@ sha384_init (void *context)
 }
 
 
+static inline u64
+ROTR (u64 x, u64 n)
+{
+  return ((x >> n) | (x << (64 - n)));
+}
+
+static inline u64
+Ch (u64 x, u64 y, u64 z)
+{
+  return ((x & y) ^ ( ~x & z));
+}
+
+static inline u64
+Maj (u64 x, u64 y, u64 z)
+{
+  return ((x & y) ^ (x & z) ^ (y & z));
+}
+
+static inline u64
+Sum0 (u64 x)
+{
+  return (ROTR (x, 28) ^ ROTR (x, 34) ^ ROTR (x, 39));
+}
+
+static inline u64
+Sum1 (u64 x)
+{
+  return (ROTR (x, 14) ^ ROTR (x, 18) ^ ROTR (x, 41));
+}
+
 /****************
  * Transform the message W which consists of 16 64-bit-words
  */
@@ -182,21 +212,26 @@ transform (SHA512_CONTEXT *hd, const unsigned char *data)
   }
 #endif
 
-#define ROTR(x,n) (((x)>>(n)) | ((x)<<(64-(n))))
-#define Ch(x,y,z) (((x) & (y)) ^ ((~(x)) & (z)))
-#define Maj(x,y,z) (((x) & (y)) ^ ((x) & (z)) ^ ((y) & (z)))
-#define Sum0(x) (ROTR((x),28) ^ ROTR((x),34) ^ ROTR((x),39))
-#define Sum1(x) (ROTR((x),14) ^ ROTR((x),18) ^ ROTR((x),41))
 #define S0(x) (ROTR((x),1) ^ ROTR((x),8) ^ ((x)>>7))
 #define S1(x) (ROTR((x),19) ^ ROTR((x),61) ^ ((x)>>6))
 
   for (t = 16; t < 80; t++)
     w[t] = S1 (w[t - 2]) + w[t - 7] + S0 (w[t - 15]) + w[t - 16];
 
-  for (t = 0; t < 80; t++)
+
+  for (t = 0; t < 80; )
     {
       u64 t1, t2;
 
+      /* Performance on a AMD Athlon(tm) Dual Core Processor 4050e
+         with gcc 4.3.3 using gcry_md_hash_buffer of each 10000 bytes
+         initialized to 0,1,2,3...255,0,... and 1000 iterations:
+
+         Not unrolled with macros:  440ms
+         Unrolled with macros:      350ms
+         Unrolled with inline:      330ms
+      */
+#if 0 /* Not unrolled.  */
       t1 = h + Sum1 (e) + Ch (e, f, g) + k[t] + w[t];
       t2 = Sum0 (a) + Maj (a, b, c);
       h = g;
@@ -207,12 +242,53 @@ transform (SHA512_CONTEXT *hd, const unsigned char *data)
       c = b;
       b = a;
       a = t1 + t2;
-
-      /* printf("t=%d a=%016llX b=%016llX c=%016llX d=%016llX "
-          "e=%016llX f=%016llX g=%016llX h=%016llX\n",t,a,b,c,d,e,f,g,h); */
+      t++;
+#else /* Unrolled to interweave the chain variables.  */
+      t1 = h + Sum1 (e) + Ch (e, f, g) + k[t] + w[t];
+      t2 = Sum0 (a) + Maj (a, b, c);
+      d += t1;
+      h  = t1 + t2;
+
+      t1 = g + Sum1 (d) + Ch (d, e, f) + k[t+1] + w[t+1];
+      t2 = Sum0 (h) + Maj (h, a, b);
+      c += t1;
+      g  = t1 + t2;
+
+      t1 = f + Sum1 (c) + Ch (c, d, e) + k[t+2] + w[t+2];
+      t2 = Sum0 (g) + Maj (g, h, a);
+      b += t1;
+      f  = t1 + t2;
+
+      t1 = e + Sum1 (b) + Ch (b, c, d) + k[t+3] + w[t+3];
+      t2 = Sum0 (f) + Maj (f, g, h);
+      a += t1;
+      e  = t1 + t2;
+
+      t1 = d + Sum1 (a) + Ch (a, b, c) + k[t+4] + w[t+4];
+      t2 = Sum0 (e) + Maj (e, f, g);
+      h += t1;
+      d  = t1 + t2;
+
+      t1 = c + Sum1 (h) + Ch (h, a, b) + k[t+5] + w[t+5];
+      t2 = Sum0 (d) + Maj (d, e, f);
+      g += t1;
+      c  = t1 + t2;
+
+      t1 = b + Sum1 (g) + Ch (g, h, a) + k[t+6] + w[t+6];
+      t2 = Sum0 (c) + Maj (c, d, e);
+      f += t1;
+      b  = t1 + t2;
+
+      t1 = a + Sum1 (f) + Ch (f, g, h) + k[t+7] + w[t+7];
+      t2 = Sum0 (b) + Maj (b, c, d);
+      e += t1;
+      a  = t1 + t2;
+      
+      t += 8;
+#endif
     }
 
-  /* update chaining vars */
+  /* Update chaining vars.  */
   hd->h0 += a;
   hd->h1 += b;
   hd->h2 += c;
index 214858d..f3a110b 100644 (file)
@@ -47,6 +47,9 @@ static int large_buffers;
 /* Number of cipher repetitions.  */
 static int cipher_repetitions;
 
+/* Number of hash repetitions.  */
+static int hash_repetitions;
+
 /* Whether fips mode was active at startup.  */
 static int in_fips_mode;
 
@@ -387,8 +390,10 @@ md_bench ( const char *algoname )
 {
   int algo;
   gcry_md_hd_t hd;
-  int i;
+  int i, repcount;
   char buf[1000];
+  char *largebuf;
+  char digest[512/8];
   gcry_error_t err = GPG_ERR_NO_ERROR;
 
   if (!algoname)
@@ -421,30 +426,57 @@ md_bench ( const char *algoname )
   printf ("%-12s", gcry_md_algo_name (algo));
 
   start_timer ();
-  for (i=0; i < 1000; i++)
-    gcry_md_write (hd, buf, sizeof buf);
+  for (repcount=0; repcount < hash_repetitions; repcount++)
+    for (i=0; i < 1000; i++)
+      gcry_md_write (hd, buf, sizeof buf);
   gcry_md_final (hd);
   stop_timer ();
   printf (" %s", elapsed_time ());
+  fflush (stdout);
 
   gcry_md_reset (hd);
   start_timer ();
-  for (i=0; i < 10000; i++)
-    gcry_md_write (hd, buf, sizeof buf/10);
+  for (repcount=0; repcount < hash_repetitions; repcount++)
+    for (i=0; i < 10000; i++)
+      gcry_md_write (hd, buf, sizeof buf/10);
   gcry_md_final (hd);
   stop_timer ();
   printf (" %s", elapsed_time ());
+  fflush (stdout);
 
   gcry_md_reset (hd);
   start_timer ();
-  for (i=0; i < 1000000; i++)
-    gcry_md_write (hd, "", 1);
+  for (repcount=0; repcount < hash_repetitions; repcount++)
+    for (i=0; i < 1000000; i++)
+      gcry_md_write (hd, "", 1);
   gcry_md_final (hd);
   stop_timer ();
   printf (" %s", elapsed_time ());
+  fflush (stdout);
 
   gcry_md_close (hd);
+
+  /* Now 100 hash operations on 10000 bytes using the fast function.
+     We initialize the buffer so that all memory pages are committed
+     and we have repeatable values.  */
+  if (gcry_md_get_algo_dlen (algo) > sizeof digest)
+    die ("digest buffer too short\n");
+
+  largebuf = malloc (10000);
+  if (!largebuf)
+    die ("out of core\n");
+  for (i=0; i < 10000; i++)
+    largebuf[i] = i;
+  start_timer ();
+  for (repcount=0; repcount < hash_repetitions; repcount++)
+    for (i=0; i < 100; i++)
+      gcry_md_hash_buffer (algo, digest, largebuf, 10000);
+  stop_timer ();
+  printf (" %s", elapsed_time ());
+  free (largebuf);
+
   putchar ('\n');
+  fflush (stdout);
 }
 
 static void
@@ -1053,7 +1085,7 @@ main( int argc, char **argv )
           large_buffers = 1;
           argc--; argv++;
         }
-      else if (!strcmp (*argv, "--cipher-repetition"))
+      else if (!strcmp (*argv, "--cipher-repetitions"))
         {
           argc--; argv++;
           if (argc)
@@ -1062,6 +1094,15 @@ main( int argc, char **argv )
               argc--; argv++;
             }
         }
+      else if (!strcmp (*argv, "--hash-repetitions"))
+        {
+          argc--; argv++;
+          if (argc)
+            {
+              hash_repetitions = atoi(*argv);
+              argc--; argv++;
+            }
+        }
       else if (!strcmp (*argv, "--fips"))
         {
           argc--; argv++;
@@ -1096,10 +1137,10 @@ main( int argc, char **argv )
 
   gcry_control (GCRYCTL_INITIALIZATION_FINISHED, 0);
 
-
-
   if (cipher_repetitions < 1)
     cipher_repetitions = 1;
+  if (hash_repetitions < 1)
+    hash_repetitions = 1;
   
   if ( !argc )
     {