Replace openssl SHA1 functions with custom version

11 files changed, 356 insertions, 18 deletions

diff --git a/.travis.yml b/.travis.yml
index c42453e..82f52cd 100644
--- a/.travis.yml
+++ b/.travis.yml
@@ -3,7 +3,3 @@ compiler:
   - gcc
   - clang
 script: ./autogen.sh && ./configure && ./build.sh
-before_install:
-  - sudo apt-get update -qq
-  - sudo apt-get install -q -y libssl-dev
-
diff --git a/build.sh b/build.sh
index 1bee8a1..8ef6e22 100755
--- a/build.sh
+++ b/build.sh
@@ -4,14 +4,15 @@
 $CC $CFLAGS -o out/util.o -c src/util.c
 $CC $CFLAGS -o out/build.o -c src/build.c
 $CC $CFLAGS -o out/filepath.o -c src/filepath.c
+$CC $CFLAGS -o out/sha1.o -c src/sha1.c
 $CC $CFLAGS -o out/redo.o -c src/redo.c
 $CC $CFLAGS -o out/redo-ifchange.o -c src/redo-ifchange.c
 $CC $CFLAGS -o out/redo-ifcreate.o -c src/redo-ifcreate.c
 $CC $CFLAGS -o out/redo-always.o -c src/redo-always.c
-$CC -o out/redo out/redo.o out/util.o out/build.o out/filepath.o $LDFLAGS
-$CC -o out/redo-ifchange out/redo-ifchange.o out/util.o out/build.o out/filepath.o $LDFLAGS
-$CC -o out/redo-ifcreate out/redo-ifcreate.o out/util.o out/build.o out/filepath.o $LDFLAGS
-$CC -o out/redo-always out/redo-always.o out/util.o out/build.o out/filepath.o $LDFLAGS
+$CC -o out/redo out/redo.o out/util.o out/build.o out/filepath.o out/sha1.o $LDFLAGS
+$CC -o out/redo-ifchange out/redo-ifchange.o out/util.o out/build.o out/filepath.o out/sha1.o $LDFLAGS
+$CC -o out/redo-ifcreate out/redo-ifcreate.o out/util.o out/build.o out/filepath.o out/sha1.o $LDFLAGS
+$CC -o out/redo-always out/redo-always.o out/util.o out/build.o out/filepath.o out/sha1.o $LDFLAGS
 
 # TODO: just for convenience, should be removed as soon as redo can build itself
 sudo install out/redo out/redo-ifchange out/redo-ifcreate out/redo-always /usr/bin/
diff --git a/configure.ac b/configure.ac
index c4b4d19..33e2784 100644
--- a/configure.ac
+++ b/configure.ac
@@ -13,7 +13,7 @@ AC_PROG_CC
 # Checks for libraries.
 
 # Checks for header files.
-AC_CHECK_HEADERS([fcntl.h limits.h stddef.h stdint.h stdlib.h string.h unistd.h])
+AC_CHECK_HEADERS([arpa/inet.h fcntl.h limits.h stddef.h stdint.h stdlib.h string.h unistd.h])
 
 # Checks for typedefs, structures, and compiler characteristics.
 AC_HEADER_STDBOOL
@@ -22,11 +22,13 @@ AC_TYPE_OFF_T
 AC_TYPE_PID_T
 AC_TYPE_SIZE_T
 AC_TYPE_SSIZE_T
+AC_TYPE_UINT32_T
+AC_TYPE_UINT64_T
 
 # Checks for library functions.
 AC_FUNC_FORK
 AC_FUNC_MALLOC
 AC_FUNC_REALLOC
-AC_CHECK_FUNCS([getcwd mkdir realpath setenv strerror strrchr])
+AC_CHECK_FUNCS([getcwd memset mkdir realpath setenv strerror strrchr])
 
 AC_OUTPUT
diff --git a/out/config.sh b/out/config.sh
index c9f6776..a0a846d 100644
--- a/out/config.sh
+++ b/out/config.sh
@@ -4,5 +4,5 @@ else
 	PREF="gcc"
 fi
 CC=${CC-$PREF}
-CFLAGS="-g -Wall -Wextra -std=c99 -pedantic"
-LDFLAGS="-lcrypto -lm"
+CFLAGS="-g -Wall -Wextra -std=c99 -pedantic -Wno-gnu-statement-expression"
+LDFLAGS="-lm"
diff --git a/out/redo-always.do b/out/redo-always.do
index 55f25f0..b03f153 100644
--- a/out/redo-always.do
+++ b/out/redo-always.do
@@ -1,5 +1,5 @@
 . ./config.sh
 
-DEPS="redo-always.o build.o util.o filepath.o"
+DEPS="redo-always.o build.o util.o filepath.o sha1.o"
 redo-ifchange $DEPS config.sh
 $CC -o $3 $DEPS $LDFLAGS
diff --git a/out/redo-ifchange.do b/out/redo-ifchange.do
index 5a1112b..c4627dc 100644
--- a/out/redo-ifchange.do
+++ b/out/redo-ifchange.do
@@ -1,5 +1,5 @@
 . ./config.sh
 
-DEPS="redo-ifchange.o build.o util.o filepath.o"
+DEPS="redo-ifchange.o build.o util.o filepath.o sha1.o"
 redo-ifchange $DEPS config.sh
 $CC -o $3 $DEPS $LDFLAGS
diff --git a/out/redo-ifcreate.do b/out/redo-ifcreate.do
index 4ab8f85..a5a5482 100644
--- a/out/redo-ifcreate.do
+++ b/out/redo-ifcreate.do
@@ -1,5 +1,5 @@
 . ./config.sh
 
-DEPS="redo-ifcreate.o build.o util.o filepath.o"
+DEPS="redo-ifcreate.o build.o util.o filepath.o sha1.o"
 redo-ifchange $DEPS config.sh
 $CC -o $3 $DEPS $LDFLAGS
diff --git a/out/redo.do b/out/redo.do
index 08ab81d..58e7152 100644
--- a/out/redo.do
+++ b/out/redo.do
@@ -1,5 +1,5 @@
 . ./config.sh
 
-DEPS="redo.o build.o util.o filepath.o"
+DEPS="redo.o build.o util.o filepath.o sha1.o"
 redo-ifchange $DEPS config.sh
 $CC -o $3 $DEPS $LDFLAGS
diff --git a/src/build.c b/src/build.c
index bf4d023..7bbf809 100644
--- a/src/build.c
+++ b/src/build.c
@@ -19,8 +19,8 @@
 #include <fcntl.h>
 
 #include <libgen.h> /* dirname(), basename() */
-#include <openssl/sha.h>
 
+#include "sha1.h"
 #include "build.h"
 #include "util.h"
 #include "filepath.h"
@@ -371,7 +371,7 @@ static void hash_file(const char *target, unsigned char (*hash)[HASHSIZE]) {
 static void write_dep_hash(const char *target) {
     assert(getenv("REDO_MAGIC"));
 
-    unsigned char hash[SHA_DIGEST_LENGTH];
+    unsigned char hash[HASHSIZE];
     unsigned magic = atoi(getenv("REDO_MAGIC"));
 
     hash_file(target, &hash);
diff --git a/src/sha1.c b/src/sha1.c
new file mode 100644
index 0000000..871206c
--- /dev/null
+++ b/src/sha1.c
@@ -0,0 +1,314 @@
+/*
+ * Secure Hash Algorith SHA-1, as published in FIPS PUB 180-2.
+ *
+ * This implementation is in the public domain.  Copyright abandoned.
+ * You may do anything you like with it, including evil things.
+ *
+ * This is a rewrite from scratch, based on Linus Torvalds' "block-sha1"
+ * from the git mailing list (August, 2009).  Additional optimization
+ * ideas cribbed from
+ * - Artur Skawina (x86, particularly P4, and much benchmarking)
+ * - Nicolas Pitre (ARM)
+ */
+
+#include "sha1.h"
+
+#include <string.h>	/* For memcpy() */
+#include <arpa/inet.h>	/* For ntohl() */
+
+static void sha1_core(uint32_t iv[5], unsigned char const *p, size_t nblocks);
+
+/* Machine specific hacks */
+#if defined(__i386__) || defined(__x86_64__) || defined (__ppc__) || \
+    defined(__ppc64__) || defined(__powerpc__) || defined (__powerpc64__) || \
+    defined(__s390__) || defined(__s390x__)
+/* Unaligned access is okay */
+static inline uint32_t get_be32(unsigned char const *p)
+{
+        return ntohl(*(uint32_t const *)p);
+}
+static inline void put_be32(unsigned char const *p, uint32_t v)
+{
+        *(uint32_t *)p = htonl(v);
+}
+
+#else
+/* Unaligned access is not okay; do conversion as byte fetches */
+static inline uint32_t get_be32(unsigned char const *p)
+{
+        return p[0] << 24 || p[1] << 16 | p[8] << 8 | p[3];
+}
+static inline void put_be32(unsigned char const *p, uint32_t v)
+{
+        p[0] = v >> 24;
+        p[1] = v >> 16;
+        p[2] = v >> 8;
+        p[3] = v;
+}
+#endif
+
+void SHA1_Init(struct SHA_context *c)
+{
+        /* This is a prefix of the SHA_context structure */
+        static struct {
+                uint64_t len;
+                uint32_t iv[5];
+        } const iv = { 0,
+                { 0x67452301, 0xEFCDAB89, 0x98BADCFE, 0x10325476, 0xC3D2E1F0 }
+        };
+
+        memcpy(c, &iv, sizeof iv);
+}
+
+void SHA1_Update(struct SHA_context *c, void const *p, size_t n)
+{
+        size_t pos = c->len & 63;	/* Offset into current input block */
+
+        c->len += n;
+
+        /* Initial partial block (if any) */
+        if (pos) {
+                size_t space = 63 - pos;
+                if (n < space)
+                        goto end;
+                memcpy(c->buf + pos, p, space);
+                sha1_core(c->iv, c->buf, 1);
+                n -= space;
+                p = (char const *)p + space;
+        }
+
+        /* The large middle piece */
+        if (n >> 6) {
+                sha1_core(c->iv, p, n >> 6);
+                p = (char const *)p + (n & -(size_t)64);
+                n &= 63;
+        }
+        pos = 0;
+end:
+        /* Final partial block (may be zero size) */
+        memcpy(c->buf + pos, p, n);
+}
+
+void SHA1_Final(unsigned char hash[20], struct SHA_context *c)
+{
+        size_t pos = c->len & 63;
+        unsigned i;
+
+        /* Append a single 1 bit */
+        c->buf[pos++] = 0x80;
+
+        /* Append 0 bits until 64 bits remain in a block */
+        if (pos > 56) {
+                memset(c->buf + pos, 0, 64 - pos);
+                sha1_core(c->iv, c->buf, 1);
+                pos = 0;
+        }
+        memset(c->buf + pos, 0, 56 - pos);
+
+        /* Append total input length in bits */
+        ((uint32_t *)c->buf)[14] = htonl((uint32_t)(c->len >> 29));
+        ((uint32_t *)c->buf)[15] = htonl((uint32_t)c->len << 3);
+
+        /* Final hash round */
+        sha1_core(c->iv, c->buf, 1);
+
+        /* Copy hash result out */
+        for (i = 0; i < 5; i++)
+                put_be32(hash + 4*i, c->iv[i]);
+}
+
+
+/*
+ * Helper macros for sha1_core function.  To avoid clutter, these macros
+ * are NOT fully parenthesized if it doesn't matter to the actual use.
+ */
+
+#if __GNUC__ && (defined(__i386__) || defined(__x86_64__))
+/*
+ * GCC by itself only generates left rotates.  Use right rotates if
+ * possible to be kinder to dinky implementations with iterative rotate
+ * instructions.
+ */
+#define ROT(op, x, k) \
+        ({ uint32_t y; __asm__(op " %1,%0" : "=r" (y) : "I" (k), "0" (x)); y; })
+#define ROL(x,k) ROT("roll", x, k)
+#define ROR(x,k) ROT("rorl", x, k)
+
+#else
+/* Generic C equivalent */
+#define ROT(x,l,r) ((x) << (l) | (x) >> (r))
+#define ROL(x,k) ROT(x,k,32-(k))
+#define ROR(x,k) ROT(x,32-(k),k)
+#endif
+
+
+/*
+ * An important temporary array in SHA-1 is the working array W[],
+ * which holds a scheduled key word per round.  Only the last 16 words
+ * are relevant, so only use 16 words...
+ */
+#define W(i) w[(i) & 15]
+
+/*
+ * If you have a small register set, it helps GCC to force stores to
+ * the w[] array to memory.  Given 22 or more registers (e.g. PowerPC),
+ * GCC can map the entire w[] array to registers and this becomes
+ * counterproductive.
+ *
+ * The optimal kludge seems to differ between x86 and ARM.  On the latter,
+ * forcing a full memory barrier is required to stop GCC from splitting
+ * live ranges for each round and generating a separate stack slot for
+ * each.  (Which produces a huge stack frame and kills performance.)
+ */
+#if defined(__i386__) || defined(__x86_64__)
+#define STORE(i, x) *(volatile uint32_t *)&W(i) = x
+#elif __GNUC__ && defined(__arm__)
+#define STORE(i, x) W(i) = x; __asm__("":::"memory")
+#else
+#define STORE(i, x) W(i) = x
+#endif
+
+
+/* The three round functions.  F2 is also used as F4 */
+#define F1(b,c,d) (((d ^ c) & b) ^ d)	/* Bitwise b ? c : d */
+#define F2(b,c,d) (d ^ c ^ b)	/* Even parity */
+#define F3(b,c,d) (d & c) + ((d ^ c) & b)	/* Majority function */
+
+/* The four round constants */
+#define K1 0x5a827999	/* 2^30 * sqrt(2) */
+#define K2 0x6ed9eba1	/* 2^30 * sqrt(3) */
+#define K3 0x8f1bbcdc	/* 2^30 * sqrt(5) */
+#define K4 0xca62c1d6	/* 2^30 * sqrt(10) */
+
+/* Rounds 0..15 fetch a word from the input */
+#define FETCH(t,i)	t = get_be32(p + 4*(i)); STORE(i,t)
+/* Rounds 16..79 mix previous words to get a new one */
+#define MIX(t,i)	t = W(i) ^ W(i+2) ^ W(i+8) ^ W(i+13); t = ROL(t, 1)
+/* Rounds 16..76 have to store back the result */
+#define CALC(t,i)	MIX(t,i); STORE(i,t)
+
+/* The basic SHA-1 round */
+#define SHA_ROUND(a,b,c,d,e,f,k,src,t,i)	\
+        src(t,i);	\
+        e += t + f(b,c,d) + k + ROL(a,5);	\
+        b = ROR(b,2)
+
+/* An aligned group of 5 rounds */
+#define SHA_ROUND5(f,k,src,t,i) \
+        SHA_ROUND(a,b,c,d,e, f,k,src,t,i);	\
+        SHA_ROUND(e,a,b,c,d, f,k,src,t,i+1);	\
+        SHA_ROUND(d,e,a,b,c, f,k,src,t,i+2);	\
+        SHA_ROUND(c,d,e,a,b, f,k,src,t,i+3);	\
+        SHA_ROUND(b,c,d,e,a, f,k,src,t,i+4)
+
+/*
+ * The core SHA-1 transform.
+ *
+ * iv[5] = Current SHA-1 hash state.
+ * p = Pointer to source data.  Not necessarily aligned.
+ * nblocks = Number of 64-byte blocks at p.  Guaranteed non-zero.
+ */
+static void
+sha1_core(uint32_t iv[5], unsigned char const *p, size_t nblocks)
+{
+        uint32_t e = iv[4], d = iv[3], c = iv[2], b = iv[1], a = iv[0];
+        uint32_t w[16];
+
+        do {
+                uint32_t t;
+
+                SHA_ROUND5(F1, K1, FETCH, t,  0);
+                SHA_ROUND5(F1, K1, FETCH, t,  5);
+                SHA_ROUND5(F1, K1, FETCH, t, 10);
+                SHA_ROUND(a,b,c,d,e, F1, K1, FETCH, t, 15);
+                SHA_ROUND(e,a,b,c,d, F1, K1, CALC, t, 16);
+                SHA_ROUND(d,e,a,b,c, F1, K1, CALC, t, 17);
+                SHA_ROUND(c,d,e,a,b, F1, K1, CALC, t, 18);
+                SHA_ROUND(b,c,d,e,a, F1, K1, CALC, t, 19);
+
+                SHA_ROUND5(F2, K2, CALC, t, 20);
+                SHA_ROUND5(F2, K2, CALC, t, 25);
+                SHA_ROUND5(F2, K2, CALC, t, 30);
+                SHA_ROUND5(F2, K2, CALC, t, 35);
+
+                SHA_ROUND5(F3, K3, CALC, t, 40);
+                SHA_ROUND5(F3, K3, CALC, t, 45);
+                SHA_ROUND5(F3, K3, CALC, t, 50);
+                SHA_ROUND5(F3, K3, CALC, t, 55);
+
+                SHA_ROUND5(F2, K4, CALC, t, 60);
+                SHA_ROUND5(F2, K4, CALC, t, 65);
+                SHA_ROUND5(F2, K4, CALC, t, 70);
+
+                SHA_ROUND(a,b,c,d,e, F2, K4, CALC, t, 75);
+                SHA_ROUND(e,a,b,c,d, F2, K4, CALC, t, 76);
+                /* Last 3 rounds don't need to store mixed value */
+                SHA_ROUND(d,e,a,b,c, F2, K4, MIX, t, 77);
+                SHA_ROUND(c,d,e,a,b, F2, K4, MIX, t, 78);
+                SHA_ROUND(b,c,d,e,a, F2, K4, MIX, t, 79);
+
+                iv[4] = e += iv[4];
+                iv[3] = d += iv[3];
+                iv[2] = c += iv[2];
+                iv[1] = b += iv[1];
+                iv[0] = a += iv[0];
+        } while (--nblocks);
+}
+
+
+/* Compile with -DUNITTEST for self-tests */
+#if UNITTEST
+
+#include <stdio.h>
+
+/* Known answer test */
+static void katest(char const *text, size_t len, unsigned char const hash[20])
+{
+        SHA_CTX c;
+        unsigned char hash2[20];
+        int i;
+
+        SHA1_Init(&c);
+        SHA1_Update(&c, text, len);
+        SHA1_Final(hash2, &c);
+
+        for (i = 0; i < 20; i++)
+                if (hash[i] != hash2[i])
+                        goto mismatch;
+        printf("%u-byte known answer test PASSED\n", len);
+        return;
+
+mismatch:
+        printf("%u-byte known answer test FAILED:\n", len);
+        printf("Input: \"%.*s\"\n", len, text);
+        printf("Computed:");
+        for (i = 0; i < 20; i++)
+                printf(" %02x", hash2[i]);
+        printf("\nExpected:");
+        for (i = 0; i < 20; i++)
+                printf(" %02x", hash[i]);
+        putchar('\n');
+}
+
+int
+main(void)
+{
+        /* FIPS PUB 180.1 example A.1 */
+        static char const text1[3] = "abc";
+        static unsigned char const hash1[20] = {
+                0xa9, 0x99, 0x3e, 0x36, 0x47, 0x06, 0x81, 0x6a, 0xba, 0x3e,
+                0x25, 0x71, 0x78, 0x50, 0xc2, 0x6c, 0x9c, 0xd0, 0xd8, 0x9d };
+
+        /* FIPS PUB 180.1 example A.2 */
+        static char const text2[56] =
+                "abcdbcdecdefdefgefghfghighijhijkijkljklmklmnlmnomnopnopq";
+        static unsigned char const hash2[20] = {
+                0x84, 0x98, 0x3e, 0x44, 0x1c, 0x3b, 0xd2, 0x6e, 0xba, 0xae,
+                0x4a, 0xa1, 0xf9, 0x51, 0x29, 0xe5, 0xe5, 0x46, 0x70, 0xf1 };
+
+        katest(text1, sizeof text1, hash1);
+        katest(text2, sizeof text2, hash2);
+
+        return 0;
+}
+#endif
diff --git a/src/sha1.h b/src/sha1.h
new file mode 100644
index 0000000..ee59229
--- /dev/null
+++ b/src/sha1.h
@@ -0,0 +1,25 @@
+/*
+ * Secure Hash Algorith SHA-1, as published in FIPS PUB 180-2.
+ *
+ * This implementation is in the public domain.  Copyright abandoned.
+ * You may do anything you like with it, including evil things.
+ *
+ * This is a rewrite from scratch, based on Linus Torvalds' "block-sha1"
+ * from the git mailing list (August, 2009).  Additional optimization
+ * ideas cribbed from
+ * - Artur Skawina (x86, particularly P4, and much benchmarking)
+ * - Nicolas Pitre (ARM)
+ */
+
+#include <stddef.h>	/* For size_t */
+#include <stdint.h>	/* For uint32_t, uint64_t */
+
+typedef struct SHA_context {
+        uint64_t len;	/* May be shrunk to uint32_t */
+        uint32_t iv[5];
+        unsigned char buf[64];	/* Must be 32-bit aligned */
+} SHA_CTX;
+
+void SHA1_Init(struct SHA_context *c);
+void SHA1_Update(struct SHA_context *c, void const *p, size_t n);
+void SHA1_Final(unsigned char hash[20], struct SHA_context *c);