Bug 781627 - Copy security/nss/lib/freebl/sha_fast.c to mfbt. r=jlebar.
authorRafael Ávila de Espíndola <respindola@mozilla.com>
Mon, 20 Aug 2012 15:01:55 -0400
changeset 105955 74cef2e06a354bd6744d7dca8b22f734e7e58aab
parent 105954 9819f1e610ef00ac0f6d53aab37d73902637db14
child 105956 27f8a4f625063035919fe3d4c5dceb7edb00c5ce
push idunknown
push userunknown
push dateunknown
reviewersjlebar
bugs781627
milestone17.0a1
Bug 781627 - Copy security/nss/lib/freebl/sha_fast.c to mfbt. r=jlebar.
mfbt/SHA1.cpp
mfbt/SHA1.h
mfbt/exported_headers.mk
mfbt/sources.mk
mfbt/tests/Makefile.in
mfbt/tests/TestSHA1.cpp
new file mode 100644
--- /dev/null
+++ b/mfbt/SHA1.cpp
@@ -0,0 +1,342 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include <string.h>
+#include "mozilla/SHA1.h"
+#include "mozilla/Assertions.h"
+
+// FIXME: We should probably create a more complete mfbt/Endian.h. This assumes
+// that any compiler that doesn't define these macros is little endian.
+#if defined(__BYTE_ORDER__) && defined(__ORDER_LITTLE_ENDIAN__)
+#if __BYTE_ORDER__ == __ORDER_LITTLE_ENDIAN__
+#define MOZ_IS_LITTLE_ENDIAN
+#endif
+#else
+#define MOZ_IS_LITTLE_ENDIAN
+#endif
+
+using namespace mozilla;
+
+static inline uint32_t SHA_ROTL(uint32_t t, uint32_t n)
+{
+    return ((t << n) | (t >> (32 - n)));
+}
+
+#ifdef MOZ_IS_LITTLE_ENDIAN
+static inline unsigned SHA_HTONL(unsigned x) {
+  const unsigned int mask = 0x00FF00FF;
+  x = (x << 16) | (x >> 16);
+  return ((x & mask) << 8) | ((x >> 8) & mask);
+}
+#else
+static inline unsigned SHA_HTONL(unsigned x) {
+  return x;
+}
+#endif
+
+static void shaCompress(volatile unsigned *X, const uint32_t * datain);
+
+#define SHA_F1(X,Y,Z) ((((Y)^(Z))&(X))^(Z))
+#define SHA_F2(X,Y,Z) ((X)^(Y)^(Z))
+#define SHA_F3(X,Y,Z) (((X)&(Y))|((Z)&((X)|(Y))))
+#define SHA_F4(X,Y,Z) ((X)^(Y)^(Z))
+
+#define SHA_MIX(n,a,b,c)    XW(n) = SHA_ROTL(XW(a)^XW(b)^XW(c)^XW(n), 1)
+
+SHA1Sum::SHA1Sum() : size(0), mDone(false)
+{
+  // Initialize H with constants from FIPS180-1.
+  H[0] = 0x67452301L;
+  H[1] = 0xefcdab89L;
+  H[2] = 0x98badcfeL;
+  H[3] = 0x10325476L;
+  H[4] = 0xc3d2e1f0L;
+}
+
+/* Explanation of H array and index values:
+ * The context's H array is actually the concatenation of two arrays
+ * defined by SHA1, the H array of state variables (5 elements),
+ * and the W array of intermediate values, of which there are 16 elements.
+ * The W array starts at H[5], that is W[0] is H[5].
+ * Although these values are defined as 32-bit values, we use 64-bit
+ * variables to hold them because the AMD64 stores 64 bit values in
+ * memory MUCH faster than it stores any smaller values.
+ *
+ * Rather than passing the context structure to shaCompress, we pass
+ * this combined array of H and W values.  We do not pass the address
+ * of the first element of this array, but rather pass the address of an
+ * element in the middle of the array, element X.  Presently X[0] is H[11].
+ * So we pass the address of H[11] as the address of array X to shaCompress.
+ * Then shaCompress accesses the members of the array using positive AND
+ * negative indexes.
+ *
+ * Pictorially: (each element is 8 bytes)
+ * H | H0 H1 H2 H3 H4 W0 W1 W2 W3 W4 W5 W6 W7 W8 W9 Wa Wb Wc Wd We Wf |
+ * X |-11-10 -9 -8 -7 -6 -5 -4 -3 -2 -1 X0 X1 X2 X3 X4 X5 X6 X7 X8 X9 |
+ *
+ * The byte offset from X[0] to any member of H and W is always
+ * representable in a signed 8-bit value, which will be encoded
+ * as a single byte offset in the X86-64 instruction set.
+ * If we didn't pass the address of H[11], and instead passed the
+ * address of H[0], the offsets to elements H[16] and above would be
+ * greater than 127, not representable in a signed 8-bit value, and the
+ * x86-64 instruction set would encode every such offset as a 32-bit
+ * signed number in each instruction that accessed element H[16] or
+ * higher.  This results in much bigger and slower code.
+ */
+#define H2X 11 /* X[0] is H[11], and H[0] is X[-11] */
+#define W2X  6 /* X[0] is W[6],  and W[0] is X[-6]  */
+
+/*
+ *  SHA: Add data to context.
+ */
+void SHA1Sum::update(const uint8_t *dataIn, uint32_t len)
+{
+  MOZ_ASSERT(!mDone);
+  register unsigned int lenB;
+  register unsigned int togo;
+
+  if (!len)
+    return;
+
+  /* accumulate the byte count. */
+  lenB = (unsigned int)(size) & 63U;
+
+  size += len;
+
+  /*
+   *  Read the data into W and process blocks as they get full
+   */
+  if (lenB > 0) {
+    togo = 64U - lenB;
+    if (len < togo)
+      togo = len;
+    memcpy(u.b + lenB, dataIn, togo);
+    len    -= togo;
+    dataIn += togo;
+    lenB    = (lenB + togo) & 63U;
+    if (!lenB) {
+      shaCompress(&H[H2X], u.w);
+    }
+  }
+  while (len >= 64U) {
+    len    -= 64U;
+    shaCompress(&H[H2X], (uint32_t *)dataIn);
+    dataIn += 64U;
+  }
+  if (len) {
+    memcpy(u.b, dataIn, len);
+  }
+}
+
+
+/*
+ *  SHA: Generate hash value
+ */
+void SHA1Sum::finish(uint8_t hashout[20])
+{
+  MOZ_ASSERT(!mDone);
+  register uint64_t size2 = size;
+  register uint32_t lenB = (uint32_t)size2 & 63;
+
+  static const uint8_t bulk_pad[64] = { 0x80,0,0,0,0,0,0,0,0,0,
+          0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
+          0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0  };
+
+  /*
+   *  Pad with a binary 1 (e.g. 0x80), then zeroes, then length in bits
+   */
+
+  update(bulk_pad, (((55+64) - lenB) & 63) + 1);
+  MOZ_ASSERT(((uint32_t)size & 63) == 56);
+  /* Convert size from bytes to bits. */
+  size2 <<= 3;
+  u.w[14] = SHA_HTONL((uint32_t)(size2 >> 32));
+  u.w[15] = SHA_HTONL((uint32_t)size2);
+  shaCompress(&H[H2X], u.w);
+
+  /*
+   *  Output hash
+   */
+  u.w[0] = SHA_HTONL(H[0]);
+  u.w[1] = SHA_HTONL(H[1]);
+  u.w[2] = SHA_HTONL(H[2]);
+  u.w[3] = SHA_HTONL(H[3]);
+  u.w[4] = SHA_HTONL(H[4]);
+  memcpy(hashout, u.w, 20);
+  mDone = true;
+}
+
+/*
+ *  SHA: Compression function, unrolled.
+ *
+ * Some operations in shaCompress are done as 5 groups of 16 operations.
+ * Others are done as 4 groups of 20 operations.
+ * The code below shows that structure.
+ *
+ * The functions that compute the new values of the 5 state variables
+ * A-E are done in 4 groups of 20 operations (or you may also think
+ * of them as being done in 16 groups of 5 operations).  They are
+ * done by the SHA_RNDx macros below, in the right column.
+ *
+ * The functions that set the 16 values of the W array are done in
+ * 5 groups of 16 operations.  The first group is done by the
+ * LOAD macros below, the latter 4 groups are done by SHA_MIX below,
+ * in the left column.
+ *
+ * gcc's optimizer observes that each member of the W array is assigned
+ * a value 5 times in this code.  It reduces the number of store
+ * operations done to the W array in the context (that is, in the X array)
+ * by creating a W array on the stack, and storing the W values there for
+ * the first 4 groups of operations on W, and storing the values in the
+ * context's W array only in the fifth group.  This is undesirable.
+ * It is MUCH bigger code than simply using the context's W array, because
+ * all the offsets to the W array in the stack are 32-bit signed offsets,
+ * and it is no faster than storing the values in the context's W array.
+ *
+ * The original code for sha_fast.c prevented this creation of a separate
+ * W array in the stack by creating a W array of 80 members, each of
+ * whose elements is assigned only once. It also separated the computations
+ * of the W array values and the computations of the values for the 5
+ * state variables into two separate passes, W's, then A-E's so that the 
+ * second pass could be done all in registers (except for accessing the W
+ * array) on machines with fewer registers.  The method is suboptimal
+ * for machines with enough registers to do it all in one pass, and it
+ * necessitates using many instructions with 32-bit offsets.
+ *
+ * This code eliminates the separate W array on the stack by a completely
+ * different means: by declaring the X array volatile.  This prevents
+ * the optimizer from trying to reduce the use of the X array by the
+ * creation of a MORE expensive W array on the stack. The result is
+ * that all instructions use signed 8-bit offsets and not 32-bit offsets.
+ *
+ * The combination of this code and the -O3 optimizer flag on GCC 3.4.3
+ * results in code that is 3 times faster than the previous NSS sha_fast
+ * code on AMD64.
+ */
+static void
+shaCompress(volatile unsigned *X, const uint32_t *inbuf)
+{
+  register unsigned A, B, C, D, E;
+
+
+#define XH(n) X[n-H2X]
+#define XW(n) X[n-W2X]
+
+#define K0 0x5a827999L
+#define K1 0x6ed9eba1L
+#define K2 0x8f1bbcdcL
+#define K3 0xca62c1d6L
+
+#define SHA_RND1(a,b,c,d,e,n) \
+  a = SHA_ROTL(b,5)+SHA_F1(c,d,e)+a+XW(n)+K0; c=SHA_ROTL(c,30) 
+#define SHA_RND2(a,b,c,d,e,n) \
+  a = SHA_ROTL(b,5)+SHA_F2(c,d,e)+a+XW(n)+K1; c=SHA_ROTL(c,30) 
+#define SHA_RND3(a,b,c,d,e,n) \
+  a = SHA_ROTL(b,5)+SHA_F3(c,d,e)+a+XW(n)+K2; c=SHA_ROTL(c,30) 
+#define SHA_RND4(a,b,c,d,e,n) \
+  a = SHA_ROTL(b,5)+SHA_F4(c,d,e)+a+XW(n)+K3; c=SHA_ROTL(c,30) 
+
+#define LOAD(n) XW(n) = SHA_HTONL(inbuf[n])
+
+  A = XH(0);
+  B = XH(1);
+  C = XH(2);
+  D = XH(3);
+  E = XH(4);
+
+  LOAD(0);		   SHA_RND1(E,A,B,C,D, 0);
+  LOAD(1);		   SHA_RND1(D,E,A,B,C, 1);
+  LOAD(2);		   SHA_RND1(C,D,E,A,B, 2);
+  LOAD(3);		   SHA_RND1(B,C,D,E,A, 3);
+  LOAD(4);		   SHA_RND1(A,B,C,D,E, 4);
+  LOAD(5);		   SHA_RND1(E,A,B,C,D, 5);
+  LOAD(6);		   SHA_RND1(D,E,A,B,C, 6);
+  LOAD(7);		   SHA_RND1(C,D,E,A,B, 7);
+  LOAD(8);		   SHA_RND1(B,C,D,E,A, 8);
+  LOAD(9);		   SHA_RND1(A,B,C,D,E, 9);
+  LOAD(10);		   SHA_RND1(E,A,B,C,D,10);
+  LOAD(11);		   SHA_RND1(D,E,A,B,C,11);
+  LOAD(12);		   SHA_RND1(C,D,E,A,B,12);
+  LOAD(13);		   SHA_RND1(B,C,D,E,A,13);
+  LOAD(14);		   SHA_RND1(A,B,C,D,E,14);
+  LOAD(15);		   SHA_RND1(E,A,B,C,D,15);
+
+  SHA_MIX( 0, 13,  8,  2); SHA_RND1(D,E,A,B,C, 0);
+  SHA_MIX( 1, 14,  9,  3); SHA_RND1(C,D,E,A,B, 1);
+  SHA_MIX( 2, 15, 10,  4); SHA_RND1(B,C,D,E,A, 2);
+  SHA_MIX( 3,  0, 11,  5); SHA_RND1(A,B,C,D,E, 3);
+
+  SHA_MIX( 4,  1, 12,  6); SHA_RND2(E,A,B,C,D, 4);
+  SHA_MIX( 5,  2, 13,  7); SHA_RND2(D,E,A,B,C, 5);
+  SHA_MIX( 6,  3, 14,  8); SHA_RND2(C,D,E,A,B, 6);
+  SHA_MIX( 7,  4, 15,  9); SHA_RND2(B,C,D,E,A, 7);
+  SHA_MIX( 8,  5,  0, 10); SHA_RND2(A,B,C,D,E, 8);
+  SHA_MIX( 9,  6,  1, 11); SHA_RND2(E,A,B,C,D, 9);
+  SHA_MIX(10,  7,  2, 12); SHA_RND2(D,E,A,B,C,10);
+  SHA_MIX(11,  8,  3, 13); SHA_RND2(C,D,E,A,B,11);
+  SHA_MIX(12,  9,  4, 14); SHA_RND2(B,C,D,E,A,12);
+  SHA_MIX(13, 10,  5, 15); SHA_RND2(A,B,C,D,E,13);
+  SHA_MIX(14, 11,  6,  0); SHA_RND2(E,A,B,C,D,14);
+  SHA_MIX(15, 12,  7,  1); SHA_RND2(D,E,A,B,C,15);
+
+  SHA_MIX( 0, 13,  8,  2); SHA_RND2(C,D,E,A,B, 0);
+  SHA_MIX( 1, 14,  9,  3); SHA_RND2(B,C,D,E,A, 1);
+  SHA_MIX( 2, 15, 10,  4); SHA_RND2(A,B,C,D,E, 2);
+  SHA_MIX( 3,  0, 11,  5); SHA_RND2(E,A,B,C,D, 3);
+  SHA_MIX( 4,  1, 12,  6); SHA_RND2(D,E,A,B,C, 4);
+  SHA_MIX( 5,  2, 13,  7); SHA_RND2(C,D,E,A,B, 5);
+  SHA_MIX( 6,  3, 14,  8); SHA_RND2(B,C,D,E,A, 6);
+  SHA_MIX( 7,  4, 15,  9); SHA_RND2(A,B,C,D,E, 7);
+
+  SHA_MIX( 8,  5,  0, 10); SHA_RND3(E,A,B,C,D, 8);
+  SHA_MIX( 9,  6,  1, 11); SHA_RND3(D,E,A,B,C, 9);
+  SHA_MIX(10,  7,  2, 12); SHA_RND3(C,D,E,A,B,10);
+  SHA_MIX(11,  8,  3, 13); SHA_RND3(B,C,D,E,A,11);
+  SHA_MIX(12,  9,  4, 14); SHA_RND3(A,B,C,D,E,12);
+  SHA_MIX(13, 10,  5, 15); SHA_RND3(E,A,B,C,D,13);
+  SHA_MIX(14, 11,  6,  0); SHA_RND3(D,E,A,B,C,14);
+  SHA_MIX(15, 12,  7,  1); SHA_RND3(C,D,E,A,B,15);
+
+  SHA_MIX( 0, 13,  8,  2); SHA_RND3(B,C,D,E,A, 0);
+  SHA_MIX( 1, 14,  9,  3); SHA_RND3(A,B,C,D,E, 1);
+  SHA_MIX( 2, 15, 10,  4); SHA_RND3(E,A,B,C,D, 2);
+  SHA_MIX( 3,  0, 11,  5); SHA_RND3(D,E,A,B,C, 3);
+  SHA_MIX( 4,  1, 12,  6); SHA_RND3(C,D,E,A,B, 4);
+  SHA_MIX( 5,  2, 13,  7); SHA_RND3(B,C,D,E,A, 5);
+  SHA_MIX( 6,  3, 14,  8); SHA_RND3(A,B,C,D,E, 6);
+  SHA_MIX( 7,  4, 15,  9); SHA_RND3(E,A,B,C,D, 7);
+  SHA_MIX( 8,  5,  0, 10); SHA_RND3(D,E,A,B,C, 8);
+  SHA_MIX( 9,  6,  1, 11); SHA_RND3(C,D,E,A,B, 9);
+  SHA_MIX(10,  7,  2, 12); SHA_RND3(B,C,D,E,A,10);
+  SHA_MIX(11,  8,  3, 13); SHA_RND3(A,B,C,D,E,11);
+
+  SHA_MIX(12,  9,  4, 14); SHA_RND4(E,A,B,C,D,12);
+  SHA_MIX(13, 10,  5, 15); SHA_RND4(D,E,A,B,C,13);
+  SHA_MIX(14, 11,  6,  0); SHA_RND4(C,D,E,A,B,14);
+  SHA_MIX(15, 12,  7,  1); SHA_RND4(B,C,D,E,A,15);
+
+  SHA_MIX( 0, 13,  8,  2); SHA_RND4(A,B,C,D,E, 0);
+  SHA_MIX( 1, 14,  9,  3); SHA_RND4(E,A,B,C,D, 1);
+  SHA_MIX( 2, 15, 10,  4); SHA_RND4(D,E,A,B,C, 2);
+  SHA_MIX( 3,  0, 11,  5); SHA_RND4(C,D,E,A,B, 3);
+  SHA_MIX( 4,  1, 12,  6); SHA_RND4(B,C,D,E,A, 4);
+  SHA_MIX( 5,  2, 13,  7); SHA_RND4(A,B,C,D,E, 5);
+  SHA_MIX( 6,  3, 14,  8); SHA_RND4(E,A,B,C,D, 6);
+  SHA_MIX( 7,  4, 15,  9); SHA_RND4(D,E,A,B,C, 7);
+  SHA_MIX( 8,  5,  0, 10); SHA_RND4(C,D,E,A,B, 8);
+  SHA_MIX( 9,  6,  1, 11); SHA_RND4(B,C,D,E,A, 9);
+  SHA_MIX(10,  7,  2, 12); SHA_RND4(A,B,C,D,E,10);
+  SHA_MIX(11,  8,  3, 13); SHA_RND4(E,A,B,C,D,11);
+  SHA_MIX(12,  9,  4, 14); SHA_RND4(D,E,A,B,C,12);
+  SHA_MIX(13, 10,  5, 15); SHA_RND4(C,D,E,A,B,13);
+  SHA_MIX(14, 11,  6,  0); SHA_RND4(B,C,D,E,A,14);
+  SHA_MIX(15, 12,  7,  1); SHA_RND4(A,B,C,D,E,15);
+
+  XH(0) += A;
+  XH(1) += B;
+  XH(2) += C;
+  XH(3) += D;
+  XH(4) += E;
+}
new file mode 100644
--- /dev/null
+++ b/mfbt/SHA1.h
@@ -0,0 +1,46 @@
+/* -*- Mode: C++; tab-width: 2; indent-tabs-mode: nil; c-basic-offset: 2 -*- */
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+/* Simple class for computing SHA1. */
+
+/*
+ * To compute the SHA1 of a buffer using this class you should write something
+ * like:
+ * void SHA1(const uint8_t* buf, unsigned size, uint8_t hash[20])
+ * {
+ *   SHA1Sum S;
+ *   S.update(buf, size);
+ *   S.finish(hash);
+ * }
+ * If there are multiple buffers or chunks, the update method can be called
+ * multiple times and the SHA1 is computed on the concatenation of all the
+ * buffers passed to it.
+ * The finish method may only be called once and cannot be followed by calls
+ * to update.
+ */
+
+#ifndef mozilla_SHA1_h_
+#define mozilla_SHA1_h_
+
+#include <stdint.h>
+namespace mozilla {
+class SHA1Sum {
+  union {
+    uint32_t w[16];         /* input buffer */
+    uint8_t  b[64];
+  } u;
+  uint64_t size;            /* count of hashed bytes. */
+  unsigned H[22];           /* 5 state variables, 16 tmp values, 1 extra */
+  bool mDone;
+
+public:
+  static const unsigned int HashSize = 20;
+  SHA1Sum();
+  void update(const uint8_t *dataIn, uint32_t len);
+  void finish(uint8_t hashout[20]);
+};
+}
+
+#endif /* mozilla_SHA1_h_ */
--- a/mfbt/exported_headers.mk
+++ b/mfbt/exported_headers.mk
@@ -19,13 +19,14 @@ EXPORTS_mozilla += \
   HashFunctions.h \
   Likely.h \
   LinkedList.h \
   MSStdInt.h \
   RangedPtr.h \
   RefPtr.h \
   Scoped.h \
   StandardInteger.h \
+  SHA1.h \
   ThreadLocal.h \
   TypeTraits.h \
   Types.h \
   Util.h \
   $(NULL)
--- a/mfbt/sources.mk
+++ b/mfbt/sources.mk
@@ -4,16 +4,17 @@
 
 ifndef MFBT_ROOT
 $(error Before including this file, you must define MFBT_ROOT to point to \
 the MFBT source directory)
 endif
 
 CPPSRCS += \
   HashFunctions.cpp \
+  SHA1.cpp \
   $(NULL)
 
 # Imported double-conversion sources.
 VPATH += $(MFBT_ROOT)/double-conversion \
   $(NULL)
 
 CPPSRCS += \
   bignum-dtoa.cc \
--- a/mfbt/tests/Makefile.in
+++ b/mfbt/tests/Makefile.in
@@ -9,22 +9,23 @@ VPATH = @srcdir@
 
 include $(DEPTH)/config/autoconf.mk
 
 STL_FLAGS =
 
 CPP_UNIT_TESTS = \
   TestCheckedInt.cpp \
   TestTypeTraits.cpp \
+  TestSHA1.cpp \
   $(NULL)
 
 # in order to prevent rules.mk from trying to link to libraries that are
 # not available to MFBT, we have to reset these MOZ_GLUE*_LDFLAGS before including it
 # and LIBS_ after including it. For WRAP_LDFLAGS, it shouldn't matter.
 # See later comments in bug 732875.
 
 MOZ_GLUE_PROGRAM_LDFLAGS=
 MOZ_GLUE_LDFLAGS =
 WRAP_LDFLAGS=
 
 include $(topsrcdir)/config/rules.mk
 
-LIBS=
+LIBS= $(call EXPAND_LIBNAME_PATH,mfbt,$(DEPTH)/mfbt)
new file mode 100644
--- /dev/null
+++ b/mfbt/tests/TestSHA1.cpp
@@ -0,0 +1,199 @@
+/* This Source Code Form is subject to the terms of the Mozilla Public
+ * License, v. 2.0. If a copy of the MPL was not distributed with this
+ * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
+
+#include "mozilla/SHA1.h"
+
+using namespace mozilla;
+
+static unsigned int TestV[1024] = {
+  0x048edc1a, 0x4345588c, 0x0ef03cbf, 0x1d6438f5, 0x094e0a1e, 0x68535f60,
+  0x14e8c927, 0x60190043, 0x5d640ab7, 0x73dc7c62, 0x364223f9, 0x47320292,
+  0x3924cae0, 0x5f6b26d3, 0x5efa04ef, 0x7aab361e, 0x2773b1aa, 0x1631b07d,
+  0x385b5dd1, 0x26c809b0, 0x28ad3a9f, 0x0315292a, 0x1a544e67, 0x1e79dcb9,
+  0x787683e8, 0x3a591c75, 0x1dd338c7, 0x01c539e5, 0x1c15b23e, 0x0697c25c,
+  0x4df5fd45, 0x672aa324, 0x39f74e6e, 0x269cdd5f, 0x087b6fce, 0x293509db,
+  0x0aef54a9, 0x210c4cc5, 0x29d6dc4a, 0x16320825, 0x3ab7b181, 0x56d6fd25,
+  0x6837fda2, 0x3e7994c2, 0x37f77529, 0x48c85472, 0x424fd84d, 0x00aba7fa,
+  0x6d8475de, 0x354634a7, 0x0c73bb49, 0x0a335de6, 0x0a9ea542, 0x5ffb31f1,
+  0x00a6a3f2, 0x76b14a03, 0x1e436a37, 0x173b766a, 0x33cf3ca0, 0x34eb0f1a,
+  0x4ca073ee, 0x27591fe6, 0x5eaf3356, 0x10c24493, 0x1bad88b6, 0x676f2309,
+  0x7f5e2d91, 0x74bd4c83, 0x66549b43, 0x52ffdf24, 0x2dfa0a83, 0x7c3e1cbf,
+  0x1edf87fc, 0x1f6fa930, 0x7c29bc74, 0x374bcd2f, 0x5b43de94, 0x0d09a3a6,
+  0x7437ecb0, 0x635117f8, 0x2aa78f65, 0x2c788958, 0x098cb9f3, 0x13ed5b3f,
+  0x41b7c7ba, 0x696b2d88, 0x42e20d63, 0x69585b1d, 0x4a9b027c, 0x0c761cba,
+  0x563bdbc4, 0x3bde2f5b, 0x0bab9730, 0x7740104c, 0x11641702, 0x26f03c32,
+  0x011a87c6, 0x2c5e4e6c, 0x46c34200, 0x6a167e84, 0x34205728, 0x0e8a6152,
+  0x0014604b, 0x6793bacd, 0x442bca9c, 0x6f2018ce, 0x4313e07e, 0x77f2c69c,
+  0x62621441, 0x47bf6358, 0x59c45e04, 0x16ba3426, 0x6ac0c19d, 0x20218c6b,
+  0x510b4ddc, 0x585f6c9d, 0x1ed02b0c, 0x366bf0a9, 0x131c7f59, 0x0ebcd320,
+  0x00ca858a, 0x5efbcb77, 0x2a7a1859, 0x64bb5afd, 0x76258886, 0x6505c895,
+  0x602cfa32, 0x17040942, 0x783df744, 0x3838e0ae, 0x6a021e39, 0x4c8c9c5a,
+  0x4a5e96b6, 0x10f4477d, 0x247fda4f, 0x4c390400, 0x0cbe048c, 0x7b547d26,
+  0x1e2e6897, 0x4ba7e01b, 0x5cfea1bb, 0x39a2d199, 0x45aee64a, 0x12615500,
+  0x0151615f, 0x1a9f5d33, 0x4542ed44, 0x101357eb, 0x35a16b1f, 0x3420b3e1,
+  0x6442bac7, 0x1c0f2a8c, 0x68d642f1, 0x45744fc4, 0x048e60cb, 0x5f217f44,
+  0x6cc7d151, 0x27f41984, 0x2d01eb09, 0x2bb15aea, 0x6dda49f8, 0x590dd6bc,
+  0x280cc20b, 0x7e2592b5, 0x043642f0, 0x292b5d29, 0x2e0a9b69, 0x41162471,
+  0x1e55db6b, 0x648b96fe, 0x05f8f9d1, 0x4a9d4cbb, 0x38517039, 0x2b0f8917,
+  0x4d1e67bb, 0x713e0974, 0x64fdf214, 0x11223963, 0x2bd09d24, 0x19924092,
+  0x4b4a70f0, 0x1ece6b03, 0x1780c9c1, 0x09b4c3ac, 0x58ac7e73, 0x5c9a4747,
+  0x321f943b, 0x41167667, 0x3a19cf8c, 0x53f4144d, 0x03a498de, 0x6fb4b742,
+  0x54d793cb, 0x7ee164e2, 0x501af74c, 0x43201e7f, 0x0ad581be, 0x497f046a,
+  0x3b1d2a9f, 0x53b88eb0, 0x2c3a26c5, 0x5ae970ba, 0x7d7ee4ff, 0x471366c5,
+  0x46119703, 0x3bfc2e58, 0x456d6c4f, 0x4b6bb181, 0x45d7c872, 0x0d023221,
+  0x021176d1, 0x4195ad44, 0x4621ec90, 0x3ae68279, 0x57952f71, 0x1796080c,
+  0x228077bb, 0x5e2b7fee, 0x3d71dd88, 0x4a651849, 0x7f1c8081, 0x04c333fc,
+  0x1f99bff6, 0x11b7754c, 0x740be324, 0x069bf2e2, 0x0802f3e0, 0x371cf30e,
+  0x1d44dda5, 0x6033b9e5, 0x5639a9b0, 0x6526bfff, 0x14d7d9b7, 0x4182b6a7,
+  0x01a5fa76, 0x7aa5e581, 0x762465e6, 0x386b3a2e, 0x495a3ab0, 0x04421b2e,
+  0x46e04591, 0x472af458, 0x6a007dd3, 0x2e8be484, 0x18660abe, 0x7969af82,
+  0x5a242a83, 0x581b5f72, 0x5f0eff6d, 0x38aea98c, 0x2acb5853, 0x6d650b35,
+  0x10b750d7, 0x18fdcd14, 0x09b4816c, 0x3ceef016, 0x6957153c, 0x27cf39fb,
+  0x60e3495d, 0x381e1da6, 0x4b5be02d, 0x14b6f309, 0x6380c589, 0x1a31f436,
+  0x4b5e50c1, 0x493ac048, 0x314baad1, 0x71e24ab7, 0x718af49c, 0x022f4658,
+  0x1a419d5b, 0x1854610d, 0x2ec4e99a, 0x7096ce50, 0x5467ba00, 0x404aab4c,
+  0x1a5ab015, 0x217580f7, 0x2d50071e, 0x71a9f437, 0x27f758b5, 0x11cd8b3f,
+  0x63b089c9, 0x53c860c1, 0x2fa6b7d7, 0x61e54771, 0x5c0ba6b9, 0x3138f796,
+  0x5c7359cd, 0x4c2c5654, 0x549d581c, 0x3129ebf7, 0x4958a248, 0x1a460541,
+  0x68e64964, 0x597c0609, 0x57afcbab, 0x2f1c6479, 0x57a0ad5c, 0x5936938f,
+  0x536a5cbe, 0x29aacf0b, 0x43eca70d, 0x6e7a3e4e, 0x563c1e3b, 0x32f23909,
+  0x12faa42d, 0x28b0bbde, 0x797e2842, 0x1b827bdf, 0x0df96a6e, 0x542ef7f4,
+  0x6226d368, 0x01cb4258, 0x77bcba08, 0x7e6dc041, 0x0571eda3, 0x0fdf5065,
+  0x5c9b9f7a, 0x2b496dd6, 0x02d3b40b, 0x3a5752db, 0x4843a293, 0x6fdc9c3f,
+  0x42963996, 0x39c9e4eb, 0x01db58ad, 0x7e79381c, 0x5bb207bb, 0x2df5de51,
+  0x1549ec82, 0x64f01e70, 0x536eb0d0, 0x10fa6e03, 0x5b7f9a20, 0x2d8b625d,
+  0x397410c7, 0x7778284e, 0x1ab75170, 0x254f304e, 0x395ba877, 0x0c2e2815,
+  0x5c723dec, 0x63b91327, 0x7c5954b5, 0x67dd69a3, 0x21d220c7, 0x5a287fcd,
+  0x0d0b9c59, 0x22444c9f, 0x6305cb43, 0x12f717cc, 0x77c11945, 0x0e79bda8,
+  0x6e014391, 0x441d0179, 0x5e17dd2f, 0x53e57a5c, 0x692f4b9a, 0x76c1e94b,
+  0x5a872d81, 0x044f7e7e, 0x0970844f, 0x25e34e73, 0x57865d3c, 0x640771d2,
+  0x12d410ed, 0x1424e079, 0x3e1c7fd7, 0x0e89295a, 0x48dcf262, 0x55a29550,
+  0x0fd4d360, 0x7494d449, 0x41e6f260, 0x2230d4e7, 0x5ad1cd49, 0x7f8dd428,
+  0x7722b48a, 0x7a14848d, 0x2a83335a, 0x548c0d9b, 0x24f5d43b, 0x33a417cb,
+  0x3061e078, 0x1a1bc935, 0x5aedb5df, 0x6755f3e4, 0x795e4cdb, 0x64dfcd1c,
+  0x6d5164fc, 0x34a3df0e, 0x2cc92142, 0x2569127d, 0x130f3d86, 0x43617cc2,
+  0x25eaf1fa, 0x044ae792, 0x4b47ee17, 0x6879ea87, 0x7eb455fa, 0x54481e19,
+  0x13bba2f0, 0x6da3fe79, 0x19c306ff, 0x42591e38, 0x2b0e205d, 0x60bd48bc,
+  0x550aa0ce, 0x2296a6ef, 0x551eb052, 0x76df1b8e, 0x242a2d22, 0x0ada0b06,
+  0x58b661ec, 0x490bec94, 0x20bd7c59, 0x760de8c3, 0x7a048ee8, 0x44ba6dcd,
+  0x3816abd9, 0x47e8527e, 0x2194a188, 0x6967a480, 0x7f7e2083, 0x0ec455f3,
+  0x78198eab, 0x3d710773, 0x05969198, 0x76ffcffe, 0x54be4797, 0x11105781,
+  0x3a851719, 0x516284b8, 0x4295de1c, 0x3905be43, 0x6d4e7d6a, 0x0877796d,
+  0x0b9e986a, 0x5e2b853f, 0x7e6c79cd, 0x4a44a54c, 0x1e28b9a2, 0x5b1e408e,
+  0x6a1c8eac, 0x62a87929, 0x4f075dac, 0x5c030e8c, 0x3df73ce9, 0x321c3c69,
+  0x2325cc45, 0x4eaf0759, 0x486a31fb, 0x12d04b94, 0x714e15d5, 0x420d1910,
+  0x092dc45b, 0x0119beac, 0x68b2bfdb, 0x74863a17, 0x3c7ab8e5, 0x035bc2df,
+  0x4e7a7965, 0x017f58d6, 0x6414074e, 0x3a1e64ae, 0x2d6725d8, 0x0f22f82a,
+  0x0a0affa0, 0x4159f31e, 0x4002cb9d, 0x234e393f, 0x6028169f, 0x3b804078,
+  0x0c16e2e1, 0x0e198020, 0x24b13c40, 0x1ceb2143, 0x38dd4246, 0x6f483590,
+  0x69b20a6e, 0x105580b1, 0x5d60f184, 0x065d18eb, 0x09a28739, 0x70345728,
+  0x595a5934, 0x14a78a43, 0x449f05c7, 0x6556fcfc, 0x260bc0b2, 0x3afb600e,
+  0x1f47bb91, 0x145c14b6, 0x541832fe, 0x54f10f23, 0x3013650e, 0x6c0d32ba,
+  0x4f202c8d, 0x66bcc661, 0x6131dc7f, 0x04828b25, 0x1737565d, 0x520e967f,
+  0x16cf0438, 0x6f2bc19e, 0x553c3dda, 0x356906b0, 0x333916d5, 0x2887c195,
+  0x11e7440b, 0x6354f182, 0x06b2f977, 0x6d2c9a5c, 0x2d02bfb7, 0x74fafcf6,
+  0x2b955161, 0x74035c38, 0x6e9bc991, 0x09a3a5b9, 0x460f416a, 0x11afabfc,
+  0x66e32d10, 0x4a56ac6e, 0x6448afa8, 0x680b0044, 0x05d0e296, 0x49569eac,
+  0x0adb563b, 0x4a9da168, 0x4f857004, 0x0f234600, 0x6db386ec, 0x280b94bf,
+  0x7cd258a5, 0x6165fd88, 0x3bf2aac9, 0x2cb47c44, 0x2381c2a4, 0x4fe42552,
+  0x21d4c81e, 0x24baa9af, 0x365231cb, 0x11b7fc81, 0x419748fb, 0x38ff637e,
+  0x065f3365, 0x21f1aba8, 0x2df41ace, 0x5cec1d95, 0x22c078a8, 0x7bb894fc,
+  0x2d66fc53, 0x7ed82ccc, 0x4485c9d7, 0x1af210fc, 0x5d2faa09, 0x3b33412e,
+  0x79d12ea8, 0x7bb8103b, 0x5cea1a7b, 0x2779db45, 0x1250ed5b, 0x0c4d8964,
+  0x6c18e9f5, 0x501ddc60, 0x3de43ae4, 0x6c0e8577, 0x0adfb426, 0x7ec718f5,
+  0x1991f387, 0x101ccb9c, 0x632360b4, 0x7d52ce4d, 0x0b58c91c, 0x1fa59d53,
+  0x0b0b48b0, 0x297315d0, 0x7f3132ff, 0x323b85d1, 0x2f852141, 0x23e84bdc,
+  0x3732cb25, 0x1274eb57, 0x21a882c3, 0x095288a9, 0x2120e253, 0x617799ce,
+  0x5e4926b3, 0x52575363, 0x696722e0, 0x509c9117, 0x3b60f14f, 0x423310fa,
+  0x4e694e80, 0x000a647e, 0x453e283a, 0x3f1d21ef, 0x527c91f0, 0x7ac2e88a,
+  0x1ba3b840, 0x1c3f253a, 0x04c40280, 0x437dc361, 0x7247859c, 0x61e5b34c,
+  0x20746a53, 0x58cfc2df, 0x79edf48e, 0x5b48e723, 0x7b08baac, 0x1d1035ea,
+  0x023fc918, 0x2de0427c, 0x71540904, 0x4030e8f5, 0x2b0961f6, 0x4ec98ef0,
+  0x781076ee, 0x0dac959b, 0x16f66214, 0x273411e5, 0x02334297, 0x3b568cd1,
+  0x7cf4e8c0, 0x0f4c2c91, 0x2d8dd28e, 0x4a7b3fb0, 0x237969ae, 0x363d6cb6,
+  0x75fee60a, 0x5825f4df, 0x29f79f9d, 0x22de4f33, 0x2309590e, 0x1977c2bd,
+  0x67f7bebe, 0x452b8330, 0x5dc70832, 0x5cddbea4, 0x59091e0b, 0x4d287830,
+  0x2bbc2ce6, 0x420ee023, 0x02d6e086, 0x228a7a14, 0x48207207, 0x1d5ccc5a,
+  0x37d32cdc, 0x50dc6508, 0x0b795304, 0x5b9fd543, 0x2a3f2925, 0x72e71606,
+  0x0dc8ba42, 0x3279a910, 0x6bd2c2e2, 0x775065d8, 0x547c59a6, 0x4b5374cf,
+  0x0c45cd18, 0x532096d6, 0x351c9bd1, 0x107fdce0, 0x3ae69075, 0x5dddd5de,
+  0x3bb0ba8b, 0x0b1a0019, 0x6c226525, 0x109e9002, 0x312191be, 0x16fa3de8,
+  0x4a5197aa, 0x0931b2d2, 0x79ee6e1b, 0x657a142b, 0x6ab74d38, 0x77440cff,
+  0x11e37956, 0x5c335799, 0x269d3be3, 0x18923cfd, 0x4dd71b00, 0x77c58014,
+  0x07145324, 0x1678546a, 0x5dfd4f6a, 0x207f4e13, 0x6b0a98c0, 0x015bc2cf,
+  0x1636d8fe, 0x7bc5f038, 0x183a0661, 0x573ec5f3, 0x54cf2255, 0x2fcc905c,
+  0x71bb70b9, 0x2b122a89, 0x59f86e5b, 0x5528273d, 0x464cf857, 0x27efdeec,
+  0x1d0bcfcc, 0x64d7837f, 0x1e7a659a, 0x02aa611c, 0x53969ad5, 0x0e83f59f,
+  0x50a6d11b, 0x79513c59, 0x0e5c3c98, 0x2ed7bbcf, 0x117de9d9, 0x375ec696,
+  0x19c830aa, 0x66950511, 0x2b6dbbaa, 0x5ca18c9b, 0x0a487514, 0x6f44a887,
+  0x6921bc6e, 0x3ef8130b, 0x26f6cde3, 0x686d7605, 0x6583553a, 0x29bcf7cc,
+  0x55d42201, 0x1c93497c, 0x64c53231, 0x32088f6e, 0x381c5770, 0x617574d8,
+  0x09757952, 0x1a616eb0, 0x1140e8aa, 0x0ff66ffb, 0x32039001, 0x5a455e7c,
+  0x0027b906, 0x21cf154c, 0x67d3527f, 0x56fd7602, 0x150f8b25, 0x2ae8e4c8,
+  0x0bf10aec, 0x3d26a40f, 0x5c4c8ffc, 0x3c291322, 0x737fd02c, 0x4b506209,
+  0x484ddaa4, 0x00b44669, 0x5974bdd1, 0x7d39d617, 0x12995404, 0x48f00bbe,
+  0x44f7c59a, 0x23cb9292, 0x6476f20b, 0x034fbd59, 0x2893161c, 0x1dbae8c0,
+  0x50348c2e, 0x797f0957, 0x685ddeaf, 0x36fb8a2e, 0x0fceb6f4, 0x10347ab4,
+  0x72720bfc, 0x292a4304, 0x0cbf8a27, 0x3cea6db7, 0x4b0c6b15, 0x57e8e716,
+  0x4e9c54cc, 0x4fc7f7ca, 0x49a6d3e2, 0x10fc2df3, 0x73db387e, 0x72cb89c3,
+  0x71dba437, 0x4b14048c, 0x6e1af265, 0x1084b213, 0x3842107d, 0x6ecdc171,
+  0x647919b2, 0x41a80841, 0x7b387c76, 0x46bc094b, 0x331b312a, 0x2f140cc4,
+  0x355d0a11, 0x19390200, 0x69b05263, 0x582963fa, 0x44897e31, 0x66a473f0,
+  0x0374f08d, 0x35879e45, 0x5e1dd7ef, 0x34d6a311, 0x6e4e18eb, 0x7b44734b,
+  0x0e421333, 0x3da026d8, 0x5becbf4b, 0x56db4a1f, 0x1f2089bc, 0x28c733f2,
+  0x04b0975d, 0x6156f224, 0x12d1f40f, 0x7f4d30f4, 0x2c0b9861, 0x769a083b,
+  0x739544fb, 0x1dbd1067, 0x0e8cd717, 0x4c246fb2, 0x115eff39, 0x19e22f2a,
+  0x4563ba61, 0x5d33a617, 0x54af83cf, 0x030bde73, 0x54b4736d, 0x0f01dfec,
+  0x08869c01, 0x4e9e4d7b, 0x4739855a, 0x62d964a3, 0x26948fde, 0x30adf212,
+  0x1f57b400, 0x3766c914, 0x1e7f9d1c, 0x33258b59, 0x522ab2c2, 0x3dc99798,
+  0x15f53fe2, 0x05636669, 0x354b59c3, 0x1c37ebd4, 0x0bb7ebf9, 0x0e4e87f9,
+  0x680d3124, 0x2770d549, 0x0c5e112e, 0x74aaa7ed, 0x06c0b550, 0x342b5922,
+  0x4532ab5b, 0x4257dbee, 0x087f32a9, 0x45ada3e3, 0x7a854272, 0x061625f2,
+  0x47c85a91, 0x25ad375d, 0x2809bd9d, 0x168b9348, 0x4381b0a3, 0x6f2dc6ca,
+  0x122e54f6, 0x6c3228a6, 0x653c1652, 0x60b60584, 0x1d304b77, 0x4cc74c58,
+  0x087e3dd5, 0x79bd540e, 0x79ab7a70, 0x26fcd1c9, 0x342abaaf, 0x644716b0,
+  0x01f076cb, 0x73628937, 0x20b01ff8, 0x5832b80b, 0x2f77fc92, 0x4468d962,
+  0x2bac2679, 0x7f850778, 0x47d2997c, 0x02690cb7, 0x7de54951, 0x54d80b14,
+  0x5e0c6854, 0x313cc749, 0x622b86ba, 0x38dbf6d3, 0x045d3e52, 0x574f87fd,
+  0x09f1b078, 0x31784f71, 0x4f01dd2f, 0x1874c9f9, 0x5837c7af, 0x2372f768,
+  0x531bd1e8, 0x61816c0b, 0x4592995f, 0x156463c0, 0x250c5afe, 0x40c83178,
+  0x4396f6b7, 0x29bdbec0, 0x43ea8ca5, 0x5c474696, 0x2c869192, 0x2ff2f51a,
+  0x7c963fe5, 0x294319c1, 0x019fbe26, 0x72fa8e68, 0x245ca463, 0x4ca88208,
+  0x72ac845a, 0x25307181, 0x2cdf88f7, 0x0adbfebd, 0x2eea465b, 0x52e4eee0,
+  0x084daacd, 0x717ce67e, 0x594087c2, 0x2b8ee5c7, 0x4558f811, 0x76b65ba4,
+  0x5de05e09, 0x3db76e27, 0x3c75110d, 0x04ca67e7, 0x51cd6d09, 0x7b4e9c3e,
+  0x7cdda4d2, 0x674fb021, 0x7d372d2d, 0x13f7978b, 0x5fb106b1, 0x034377d1,
+  0x2e5336f3, 0x099bb17d, 0x04e6755e, 0x34f73c1e, 0x004e0a0d, 0x7f2c32e2,
+  0x1fc8f910, 0x67d0859d, 0x76462b25, 0x59fa9a17, 0x028e53ef, 0x3d6d5fdd,
+  0x79a4671e, 0x5cbec506, 0x2c23ee6d, 0x628a2c1e, 0x4dae87bd, 0x07a189ea,
+  0x3a414a96, 0x5915f622, 0x6bea011e, 0x412674cf, 0x07ecc314, 0x6a7dbce8,
+  0x7e176f10, 0x68e60d47, 0x079ea970, 0x79f3b55c, 0x65a46098, 0x56155533,
+  0x7e5d0272, 0x795bfad5, 0x094da770, 0x05ba427c, 0x152e430e, 0x187d8470,
+  0x08e607bc, 0x45ce5ef9, 0x654231ae, 0x38d8cb48, 0x605632f8, 0x25cf8ee9,
+  0x11497170, 0x171a3b00, 0x0f103d49, 0x24826483, 0x2848e187, 0x7498919b,
+  0x1bb788cb, 0x791ad5c7, 0x5129330e, 0x016c4436, 0x430f05bf, 0x1f06b5cd,
+  0x62df1378, 0x0423b9b4, 0x0341acaf, 0x3189543c, 0x7b96b2ea, 0x6c4865c3,
+  0x4cc7adc3, 0x78a2bff6, 0x642db7c7, 0x70d02300, 0x7cd43ac0, 0x4f5fe414,
+  0x333b52c2, 0x500d3c74, 0x65782c01, 0x3f72a2c5, 0x278f59d8, 0x493bf7f8,
+  0x16bf51a0, 0x6cc70ced, 0x6ed15979, 0x1a77abae, 0x08cadbb7, 0x2f2e0bc0,
+  0x236f5e8d, 0x1a4b4495, 0x360bd008, 0x32227d40
+};
+
+int main()
+{
+  SHA1Sum S;
+  unsigned char hash[20];
+  S.update((const unsigned char*) TestV, sizeof(TestV));
+  S.finish(hash);
+  const unsigned char expected[20] = {
+    0xc8, 0xf2, 0x09, 0x59, 0x4e, 0x64, 0x40, 0xaa, 0x7b, 0xf7, 0xb8, 0xe0,
+    0xfa, 0x44, 0xb2, 0x31, 0x95, 0xad, 0x94, 0x81};
+
+  for (unsigned int i = 0; i < 20; ++i) {
+    if (hash[i] != expected[i]) {
+      return 1;
+    }
+  }
+  return 0;
+}