SHA1: unroll loop in hashBlock.

[ruiu]

Summary

This code is taken from public domain.
https://github.com/jsonn/src/blob/trunk/common/lib/libc/hash/sha1/sha1.c

I wrote a sha1 command and run it on my Xeon E5-2680 v2 2.80GHz machine.
Here is a result. The new hash function is 37% faster than before.

Performance counter stats for './llvm-sha1-old /ssd/build/bin/lld' (10 runs):

    6640.503687 task-clock (msec)         #    1.001 CPUs utilized            ( +-  0.03% )
             54 context-switches          #    0.008 K/sec                    ( +-  5.03% )
              5 cpu-migrations            #    0.001 K/sec                    ( +- 31.73% )
        183,803 page-faults               #    0.028 M/sec                    ( +-  0.00% )
 18,527,954,113 cycles                    #    2.790 GHz                      ( +-  0.03% )
  4,993,237,485 stalled-cycles-frontend   #   26.95% frontend cycles idle     ( +-  0.11% )
<not supported> stalled-cycles-backend
 50,217,149,423 instructions              #    2.71  insns per cycle
                                          #    0.10  stalled cycles per insn  ( +-  0.00% )
  6,094,322,337 branches                  #  917.750 M/sec                    ( +-  0.00% )
     11,778,239 branch-misses             #    0.19% of all branches          ( +-  0.01% )

    6.634017401 seconds time elapsed                                          ( +-  0.03% )

Performance counter stats for './llvm-sha1-new /ssd/build/bin/lld' (10 runs):

    4167.062720 task-clock (msec)         #    1.001 CPUs utilized            ( +-  0.02% )
             52 context-switches          #    0.012 K/sec                    ( +- 16.45% )
              7 cpu-migrations            #    0.002 K/sec                    ( +- 32.20% )
        183,804 page-faults               #    0.044 M/sec                    ( +-  0.00% )
 11,626,611,958 cycles                    #    2.790 GHz                      ( +-  0.02% )
  4,491,897,976 stalled-cycles-frontend   #   38.63% frontend cycles idle     ( +-  0.05% )
<not supported> stalled-cycles-backend
 24,320,180,617 instructions              #    2.09  insns per cycle
                                          #    0.18  stalled cycles per insn  ( +-  0.00% )
  1,574,674,576 branches                  #  377.886 M/sec                    ( +-  0.00% )
     11,769,693 branch-misses             #    0.75% of all branches          ( +-  0.00% )

    4.163251552 seconds time elapsed                                          ( +-  0.02% )

[davide]

lib/Support/SHA1.cpp

12

I'd rather link the original NetBSD repo rather than Joerg's mirror (anoncvs.netbsd.org)

113–192

I don't think this is terrible per-se (not quite readable), but @chandlerc pointed out during the DevSummit (at the libc++ performance BOF IIRC) that we should try to avoid unrolling loops by hand in our algorithms (and make sure the compiler does that on our behalf).
Now, for this case, I'm not sure if LLVM knows how to unroll this loop (and if it doesn't, I'm not sure how profitable it is to teach how to do it), but something to keep in mind in general.

[mehdi_amini]

lib/Support/SHA1.cpp

30

Why did you turn it into a macro?

51

Why a macro for all the RX(..)?

113–192

Yes, I wonder how is the codegen impacted if you turn the above into 4 different loops?

[davide]

lib/Support/SHA1.cpp

30

Agree, not particularly fond of macros in new software unless really needed.

[joerg]

lib/Support/SHA1.cpp

12

Agreed, it was primarily meant as starting point.

http://cvsweb.netbsd.org/bsdweb.cgi/~checkout~/src/common/lib/libc/hash/sha1/sha1.c?rev=1.6

would be a better link.

30

That's actually adopted from the NetBSD implementation. There is no huge advantage for inline function vs macro; the macro just keeps the diff a bit smaller.

51

The macros reflect the building blocks of the main loop, e.g. the different constants and blocks used.
Again, this could be an inline function with references and hoping the compiler optimised all away, but using a macro keeps the diff down.

[ruiu]

• Fix the original source URL
• Convert macros into functions

[ruiu]

If I do not unroll the loop, computing a hash on a file worsened from 4.16 seconds to 5.77, so there's definitely an impact.

[mehdi_amini]

LGTM, Thanks!

In D26890#600802, @ruiu wrote:

If I do not unroll the loop, computing a hash on a file worsened from 4.16 seconds to 5.77, so there's definitely an impact.

Please file a PR on llvm.org with the non-unrolled version of this code, and CC me. The optimization folks should look at this!

lib/Support/SHA1.cpp

82

Please use static free function if there is no need to access the state of the object.

[mehdi_amini]

lib/Support/SHA1.cpp

51

Keeping the diff down is not a metric I value, especially if it is by using macros instead of functions.

[ruiu]

lib/Support/SHA1.cpp

82

blk and blk0 access InternalState, so these functions need to be members.

[mehdi_amini]

lib/Support/SHA1.cpp

82

Sure, but you could have an extra arg to access the buffer, like:

uint32_t SHA1::blk(int I, uint32_t* Buffer) {
  Buffer[I & 15] = rol(
      Buffer[(I + 13) & 15] ^
          Buffer[(I + 8) & 15] ^
          Buffer[(I + 2) & 15] ^ Buffer[I & 15],
      1);
  return Buffer[I & 15];
}

[ruiu]

• Use static free functions instead of class member functions.

[ruiu]

FYI, filed https://llvm.org/bugs/show_bug.cgi?id=31075 to report the unrolling issue.

include/llvm/Support/SHA1.h

 private:
   /// Define some constants.
   /// "static constexpr" would be cleaner but MSVC does not support it yet.
   enum { BLOCK_LENGTH = 64 };
   enum { HASH_LENGTH = 20 };
 
   // Internal State
   struct {
-    uint32_t Buffer[BLOCK_LENGTH / 4];
+    union {
+      uint8_t C[BLOCK_LENGTH];
+      uint32_t L[BLOCK_LENGTH / 4];
+    } Buffer;
     uint32_t State[HASH_LENGTH / 4];
     uint32_t ByteCount;
     uint8_t BufferOffset;
   } InternalState;
 
   // Internal copy of the hash, populated and accessed on calls to result()
   uint32_t HashResult[HASH_LENGTH / 4];
 
   // Helper
   void writebyte(uint8_t data);
   void hashBlock();
   void addUncounted(uint8_t data);
   void pad();
+
+  uint32_t blk0(int I);
+  uint32_t blk(int I);
+  void r0(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+          int I);
+  void r1(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+          int I);
+  void r2(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+          int I);
+  void r3(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+          int I);
+  void r4(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+          int I);
 };
 
 } // end llvm namespace
 
 #endif

lib/Support/SHA1.cpp

 //======- SHA1.h - Private copy of the SHA1 implementation ---*- C++ -* ======//
 //
 //                     The LLVM Compiler Infrastructure
 //
 // This file is distributed under the University of Illinois Open Source
 // License. See LICENSE.TXT for details.
 //
 //===----------------------------------------------------------------------===//
+//
 // This code is taken from public domain
-// (http://oauth.googlecode.com/svn/code/c/liboauth/src/sha1.c)
+// (http://oauth.googlecode.com/svn/code/c/liboauth/src/sha1.c and
+// http://cvsweb.netbsd.org/bsdweb.cgi/src/common/lib/libc/hash/sha1/sha1.c?rev=1.6)
 // and modified by wrapping it in a C++ interface for LLVM,
 // and removing unnecessary code.
 //
 //===----------------------------------------------------------------------===//
 
 #include "llvm/Support/Host.h"
 #include "llvm/Support/SHA1.h"
 #include "llvm/ADT/ArrayRef.h"
 using namespace llvm;
 
 #include <stdint.h>
 #include <string.h>
 
 #if defined(BYTE_ORDER) && defined(BIG_ENDIAN) && BYTE_ORDER == BIG_ENDIAN
 #define SHA_BIG_ENDIAN
 #endif
 
+static uint32_t rol(uint32_t number, int bits) {
+  return (number << bits) | (number >> (32 - bits));
+};
+
+#if SHA_BIG_ENDIAN
+uint32_t SHA1::blk0(int I) {
+  InternalState.Buffer.L[I] =
+      (rol(InternalState.Buffer.L[I], 24) & 0xFF00FF00) |
+      (rol(InternalState.Buffer.L[I], 8) & 0x00FF00FF);
+  return InternalState.Buffer.L[I];
+}
+#else
+uint32_t SHA1::blk0(int I) { return InternalState.Buffer.L[I]; }
+#endif
+
+uint32_t SHA1::blk(int I) {
+  InternalState.Buffer.L[I & 15] = rol(
+      InternalState.Buffer.L[(I + 13) & 15] ^
+          InternalState.Buffer.L[(I + 8) & 15] ^
+          InternalState.Buffer.L[(I + 2) & 15] ^ InternalState.Buffer.L[I & 15],
+      1);
+  return InternalState.Buffer.L[I & 15];
+}
+
+void SHA1::r0(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+              int I) {
+  E += ((B & (C ^ D)) ^ D) + blk0(I) + 0x5A827999 + rol(A, 5);
+  B = rol(B, 30);
+}
+
+void SHA1::r1(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+              int I) {
+  E += ((B & (C ^ D)) ^ D) + blk(I) + 0x5A827999 + rol(A, 5);
+  B = rol(B, 30);
+}
+
+void SHA1::r2(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+              int I) {
+  E += (B ^ C ^ D) + blk(I) + 0x6ED9EBA1 + rol(A, 5);
+  B = rol(B, 30);
+}
+
+void SHA1::r3(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+              int I) {
+  E += (((B | C) & D) | (B & C)) + blk(I) + 0x8F1BBCDC + rol(A, 5);
+  B = rol(B, 30);
+}
+
+void SHA1::r4(uint32_t &A, uint32_t &B, uint32_t &C, uint32_t &D, uint32_t &E,
+              int I) {
+  E += (B ^ C ^ D) + blk(I) + 0xCA62C1D6 + rol(A, 5);
+  B = rol(B, 30);
+}
+
 /* code */
 #define SHA1_K0 0x5a827999
 #define SHA1_K20 0x6ed9eba1
 #define SHA1_K40 0x8f1bbcdc
 #define SHA1_K60 0xca62c1d6
 
 #define SEED_0 0x67452301
 #define SEED_1 0xefcdab89
 #define SEED_2 0x98badcfe
 #define SEED_3 0x10325476
 #define SEED_4 0xc3d2e1f0
 
 void SHA1::init() {
   InternalState.State[0] = SEED_0;
   InternalState.State[1] = SEED_1;
   InternalState.State[2] = SEED_2;
   InternalState.State[3] = SEED_3;
   InternalState.State[4] = SEED_4;
   InternalState.ByteCount = 0;
   InternalState.BufferOffset = 0;
 }
 
-static uint32_t rol32(uint32_t number, uint8_t bits) {
-  return ((number << bits) | (number >> (32 - bits)));
-}
-
 void SHA1::hashBlock() {
-  uint8_t i;
-  uint32_t a, b, c, d, e, t;
-
-  a = InternalState.State[0];
-  b = InternalState.State[1];
-  c = InternalState.State[2];
-  d = InternalState.State[3];
-  e = InternalState.State[4];
-  for (i = 0; i < 80; i++) {
-    if (i >= 16) {
-      t = InternalState.Buffer[(i + 13) & 15] ^
-          InternalState.Buffer[(i + 8) & 15] ^
-          InternalState.Buffer[(i + 2) & 15] ^ InternalState.Buffer[i & 15];
-      InternalState.Buffer[i & 15] = rol32(t, 1);
-    }
-    if (i < 20) {
-      t = (d ^ (b & (c ^ d))) + SHA1_K0;
-    } else if (i < 40) {
-      t = (b ^ c ^ d) + SHA1_K20;
-    } else if (i < 60) {
-      t = ((b & c) | (d & (b | c))) + SHA1_K40;
-    } else {
-      t = (b ^ c ^ d) + SHA1_K60;
-    }
-    t += rol32(a, 5) + e + InternalState.Buffer[i & 15];
-    e = d;
-    d = c;
-    c = rol32(b, 30);
-    b = a;
-    a = t;
-  }
-  InternalState.State[0] += a;
-  InternalState.State[1] += b;
-  InternalState.State[2] += c;
-  InternalState.State[3] += d;
-  InternalState.State[4] += e;
+  uint32_t A = InternalState.State[0];
+  uint32_t B = InternalState.State[1];
+  uint32_t C = InternalState.State[2];
+  uint32_t D = InternalState.State[3];
+  uint32_t e = InternalState.State[4];
+
+  // 4 rounds of 20 operations each. Loop unrolled.
+  r0(A, B, C, D, E, 0);
+  r0(E, A, B, C, D, 1);
+  r0(D, E, A, B, C, 2);
+  r0(C, D, E, A, B, 3);
+  r0(B, C, D, E, A, 4);
+  r0(A, B, C, D, E, 5);
+  r0(E, A, B, C, D, 6);
+  r0(D, E, A, B, C, 7);
+  r0(C, D, E, A, B, 8);
+  r0(B, C, D, E, A, 9);
+  r0(A, B, C, D, E, 10);
+  r0(E, A, B, C, D, 11);
+  r0(D, E, A, B, C, 12);
+  r0(C, D, E, A, B, 13);
+  r0(B, C, D, E, A, 14);
+  r0(A, B, C, D, E, 15);
+  r1(E, A, B, C, D, 16);
+  r1(D, E, A, B, C, 17);
+  r1(C, D, E, A, B, 18);
+  r1(B, C, D, E, A, 19);
+
+  r2(A, B, C, D, E, 20);
+  r2(E, A, B, C, D, 21);
+  r2(D, E, A, B, C, 22);
+  r2(C, D, E, A, B, 23);
+  r2(B, C, D, E, A, 24);
+  r2(A, B, C, D, E, 25);
+  r2(E, A, B, C, D, 26);
+  r2(D, E, A, B, C, 27);
+  r2(C, D, E, A, B, 28);
+  r2(B, C, D, E, A, 29);
+  r2(A, B, C, D, E, 30);
+  r2(E, A, B, C, D, 31);
+  r2(D, E, A, B, C, 32);
+  r2(C, D, E, A, B, 33);
+  r2(B, C, D, E, A, 34);
+  r2(A, B, C, D, E, 35);
+  r2(E, A, B, C, D, 36);
+  r2(D, E, A, B, C, 37);
+  r2(C, D, E, A, B, 38);
+  r2(B, C, D, E, A, 39);
+
+  r3(A, B, C, D, E, 40);
+  r3(E, A, B, C, D, 41);
+  r3(D, E, A, B, C, 42);
+  r3(C, D, E, A, B, 43);
+  r3(B, C, D, E, A, 44);
+  r3(A, B, C, D, E, 45);
+  r3(E, A, B, C, D, 46);
+  r3(D, E, A, B, C, 47);
+  r3(C, D, E, A, B, 48);
+  r3(B, C, D, E, A, 49);
+  r3(A, B, C, D, E, 50);
+  r3(E, A, B, C, D, 51);
+  r3(D, E, A, B, C, 52);
+  r3(C, D, E, A, B, 53);
+  r3(B, C, D, E, A, 54);
+  r3(A, B, C, D, E, 55);
+  r3(E, A, B, C, D, 56);
+  r3(D, E, A, B, C, 57);
+  r3(C, D, E, A, B, 58);
+  r3(B, C, D, E, A, 59);
+
+  r4(A, B, C, D, E, 60);
+  r4(E, A, B, C, D, 61);
+  r4(D, E, A, B, C, 62);
+  r4(C, D, E, A, B, 63);
+  r4(B, C, D, E, A, 64);
+  r4(A, B, C, D, E, 65);
+  r4(E, A, B, C, D, 66);
+  r4(D, E, A, B, C, 67);
+  r4(C, D, E, A, B, 68);
+  r4(B, C, D, E, A, 69);
+  r4(A, B, C, D, E, 70);
+  r4(E, A, B, C, D, 71);
+  r4(D, E, A, B, C, 72);
+  r4(C, D, E, A, B, 73);
+  r4(B, C, D, E, A, 74);
+  r4(A, B, C, D, E, 75);
+  r4(E, A, B, C, D, 76);
+  r4(D, E, A, B, C, 77);
+  r4(C, D, E, A, B, 78);
+  r4(B, C, D, E, A, 79);
+
+  InternalState.State[0] += A;
+  InternalState.State[1] += B;
+  InternalState.State[2] += C;
+  InternalState.State[3] += D;
+  InternalState.State[4] += E;
 }
 
 void SHA1::addUncounted(uint8_t data) {
-  uint8_t *const b = (uint8_t *)InternalState.Buffer;
 #ifdef SHA_BIG_ENDIAN
-  b[InternalState.BufferOffset] = data;
+  InternalState.Buffer.C[InternalState.BufferOffset] = data;
 #else
-  b[InternalState.BufferOffset ^ 3] = data;
+  InternalState.Buffer.C[InternalState.BufferOffset ^ 3] = data;
 #endif
+
   InternalState.BufferOffset++;
   if (InternalState.BufferOffset == BLOCK_LENGTH) {
     hashBlock();
     InternalState.BufferOffset = 0;
   }
 }
 
 void SHA1::writebyte(uint8_t data) {