map: Use simpler fnv-1a hash function

17 files changed, 10 insertions, 190 deletions

diff --git a/Makefile b/Makefile
index d52da1b..7a82c80 100644
--- a/Makefile
+++ b/Makefile
@@ -33,7 +33,6 @@ SRC=\
 	pp.c\
 	scan.c\
 	scope.c\
-	siphash.c\
 	stmt.c\
 	targ.c\
 	token.c\
@@ -59,7 +58,6 @@ $(objdir)/pp.o      : pp.c      util.h cc.h       $(stagedeps) ; $(CC) $(CFLAGS)
 $(objdir)/qbe.o     : qbe.c     util.h cc.h ops.h $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ qbe.c
 $(objdir)/scan.o    : scan.c    util.h cc.h       $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ scan.c
 $(objdir)/scope.o   : scope.c   util.h cc.h       $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ scope.c
-$(objdir)/siphash.o : siphash.c                   $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ siphash.c
 $(objdir)/stmt.o    : stmt.c    util.h cc.h       $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ stmt.c
 $(objdir)/targ.o    : targ.c    util.h cc.h       $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ targ.c
 $(objdir)/token.o   : token.c   util.h cc.h       $(stagedeps) ; $(CC) $(CFLAGS) -c -o $@ token.c
diff --git a/attr.c b/attr.c
index 31d16f7..8a4bbd2 100644
--- a/attr.c
+++ b/attr.c
@@ -1,6 +1,5 @@
 #include <limits.h>
 #include <stdbool.h>
-#include <stdint.h>
 #include <string.h>
 #include "util.h"
 #include "cc.h"
diff --git a/decl.c b/decl.c
index 56c4cbe..05700f7 100644
--- a/decl.c
+++ b/decl.c
@@ -2,7 +2,6 @@
 #include <limits.h>
 #include <stdbool.h>
 #include <stddef.h>
-#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
diff --git a/eval.c b/eval.c
index e1be25e..8de1316 100644
--- a/eval.c
+++ b/eval.c
@@ -1,7 +1,6 @@
 #include <limits.h>
 #include <stdbool.h>
 #include <stddef.h>
-#include <stdint.h>
 #include "util.h"
 #include "cc.h"
 
diff --git a/init.c b/init.c
index 6056f5b..a713933 100644
--- a/init.c
+++ b/init.c
@@ -1,6 +1,5 @@
 #include <assert.h>
 #include <stdbool.h>
-#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 #include "util.h"
diff --git a/main.c b/main.c
index 96fea3e..bf3cedb 100644
--- a/main.c
+++ b/main.c
@@ -1,5 +1,4 @@
 #include <stdbool.h>
-#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include "util.h"
diff --git a/map.c b/map.c
index 2f34ae3..a0cbd68 100644
--- a/map.c
+++ b/map.c
@@ -1,20 +1,20 @@
 #include <assert.h>
 #include <stdbool.h>
-#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 #include "util.h"
 
-static uint64_t
+static unsigned long
 hash(const void *ptr, size_t len)
 {
-	extern int siphash(const uint8_t *, const size_t, const uint8_t *, uint8_t *, const size_t);
-	static const uint8_t k[16] = {0};  /* XXX: we don't have a way to get entropy in standard C */
-	uint64_t r;
-
-	siphash(ptr, len, k, (uint8_t *)&r, sizeof(r));
-
-	return r;
+	unsigned long h;
+	const unsigned char *pos, *end;
+
+	/* FNV-1a */
+	h = 0x811c9dc5;
+	for (pos = ptr, end = pos + len; pos != end; ++pos)
+		h = (h ^ *pos) * 0x1000193;
+	return h;
 }
 
 void
diff --git a/pp.c b/pp.c
index 09d1a06..99e56e8 100644
--- a/pp.c
+++ b/pp.c
@@ -1,7 +1,6 @@
 #include <assert.h>
 #include <stdarg.h>
 #include <stdbool.h>
-#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
diff --git a/scan.c b/scan.c
index 0e6e7b1..8a38e22 100644
--- a/scan.c
+++ b/scan.c
@@ -1,7 +1,6 @@
 #include <ctype.h>
 #include <stdarg.h>
 #include <stdbool.h>
-#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
diff --git a/scope.c b/scope.c
index d48658b..c8de958 100644
--- a/scope.c
+++ b/scope.c
@@ -1,6 +1,5 @@
 #include <stdbool.h>
 #include <stdlib.h>
-#include <stdint.h>
 #include <string.h>
 #include "util.h"
 #include "cc.h"
diff --git a/siphash.c b/siphash.c
deleted file mode 100644
index 871330b..0000000
--- a/siphash.c
+++ /dev/null
@@ -1,165 +0,0 @@
-/*
-   SipHash reference C implementation
-
-   Copyright (c) 2012-2016 Jean-Philippe Aumasson
-   <jeanphilippe.aumasson@gmail.com>
-   Copyright (c) 2012-2014 Daniel J. Bernstein <djb@cr.yp.to>
-
-   To the extent possible under law, the author(s) have dedicated all copyright
-   and related and neighboring rights to this software to the public domain
-   worldwide. This software is distributed without any warranty.
-
-   You should have received a copy of the CC0 Public Domain Dedication along
-   with
-   this software. If not, see
-   <http://creativecommons.org/publicdomain/zero/1.0/>.
- */
-#include <assert.h>
-#include <stdint.h>
-#include <stdio.h>
-#include <string.h>
-
-/* default: SipHash-2-4 */
-#define cROUNDS 2
-#define dROUNDS 4
-
-#define ROTL(x, b) (uint64_t)(((x) << (b)) | ((x) >> (64 - (b))))
-
-#define U32TO8_LE(p, v)                                                        \
-    (p)[0] = (uint8_t)((v));                                                   \
-    (p)[1] = (uint8_t)((v) >> 8);                                              \
-    (p)[2] = (uint8_t)((v) >> 16);                                             \
-    (p)[3] = (uint8_t)((v) >> 24);
-
-#define U64TO8_LE(p, v)                                                        \
-    U32TO8_LE((p), (uint32_t)((v)));                                           \
-    U32TO8_LE((p) + 4, (uint32_t)((v) >> 32));
-
-#define U8TO64_LE(p)                                                           \
-    (((uint64_t)((p)[0])) | ((uint64_t)((p)[1]) << 8) |                        \
-     ((uint64_t)((p)[2]) << 16) | ((uint64_t)((p)[3]) << 24) |                 \
-     ((uint64_t)((p)[4]) << 32) | ((uint64_t)((p)[5]) << 40) |                 \
-     ((uint64_t)((p)[6]) << 48) | ((uint64_t)((p)[7]) << 56))
-
-#define SIPROUND                                                               \
-    do {                                                                       \
-        v0 += v1;                                                              \
-        v1 = ROTL(v1, 13);                                                     \
-        v1 ^= v0;                                                              \
-        v0 = ROTL(v0, 32);                                                     \
-        v2 += v3;                                                              \
-        v3 = ROTL(v3, 16);                                                     \
-        v3 ^= v2;                                                              \
-        v0 += v3;                                                              \
-        v3 = ROTL(v3, 21);                                                     \
-        v3 ^= v0;                                                              \
-        v2 += v1;                                                              \
-        v1 = ROTL(v1, 17);                                                     \
-        v1 ^= v2;                                                              \
-        v2 = ROTL(v2, 32);                                                     \
-    } while (0)
-
-#ifdef DEBUG
-#define TRACE                                                                  \
-    do {                                                                       \
-        printf("(%3d) v0 %08x %08x\n", (int)inlen, (uint32_t)(v0 >> 32),       \
-               (uint32_t)v0);                                                  \
-        printf("(%3d) v1 %08x %08x\n", (int)inlen, (uint32_t)(v1 >> 32),       \
-               (uint32_t)v1);                                                  \
-        printf("(%3d) v2 %08x %08x\n", (int)inlen, (uint32_t)(v2 >> 32),       \
-               (uint32_t)v2);                                                  \
-        printf("(%3d) v3 %08x %08x\n", (int)inlen, (uint32_t)(v3 >> 32),       \
-               (uint32_t)v3);                                                  \
-    } while (0)
-#else
-#define TRACE
-#endif
-
-int siphash(const uint8_t *in, const size_t inlen, const uint8_t *k,
-            uint8_t *out, const size_t outlen) {
-
-    assert((outlen == 8) || (outlen == 16));
-    uint64_t v0 = 0x736f6d6570736575ULL;
-    uint64_t v1 = 0x646f72616e646f6dULL;
-    uint64_t v2 = 0x6c7967656e657261ULL;
-    uint64_t v3 = 0x7465646279746573ULL;
-    uint64_t k0 = U8TO64_LE(k);
-    uint64_t k1 = U8TO64_LE(k + 8);
-    uint64_t m;
-    int i;
-    const uint8_t *end = in + inlen - (inlen % sizeof(uint64_t));
-    const int left = inlen & 7;
-    uint64_t b = ((uint64_t)inlen) << 56;
-    v3 ^= k1;
-    v2 ^= k0;
-    v1 ^= k1;
-    v0 ^= k0;
-
-    if (outlen == 16)
-        v1 ^= 0xee;
-
-    for (; in != end; in += 8) {
-        m = U8TO64_LE(in);
-        v3 ^= m;
-
-        TRACE;
-        for (i = 0; i < cROUNDS; ++i)
-            SIPROUND;
-
-        v0 ^= m;
-    }
-
-    switch (left) {
-    case 7:
-        b |= ((uint64_t)in[6]) << 48; /* fallthrough */
-    case 6:
-        b |= ((uint64_t)in[5]) << 40; /* fallthrough */
-    case 5:
-        b |= ((uint64_t)in[4]) << 32; /* fallthrough */
-    case 4:
-        b |= ((uint64_t)in[3]) << 24; /* fallthrough */
-    case 3:
-        b |= ((uint64_t)in[2]) << 16; /* fallthrough */
-    case 2:
-        b |= ((uint64_t)in[1]) << 8; /* fallthrough */
-    case 1:
-        b |= ((uint64_t)in[0]);
-        break;
-    case 0:
-        break;
-    }
-
-    v3 ^= b;
-
-    TRACE;
-    for (i = 0; i < cROUNDS; ++i)
-        SIPROUND;
-
-    v0 ^= b;
-
-    if (outlen == 16)
-        v2 ^= 0xee;
-    else
-        v2 ^= 0xff;
-
-    TRACE;
-    for (i = 0; i < dROUNDS; ++i)
-        SIPROUND;
-
-    b = v0 ^ v1 ^ v2 ^ v3;
-    U64TO8_LE(out, b);
-
-    if (outlen == 8)
-        return 0;
-
-    v1 ^= 0xdd;
-
-    TRACE;
-    for (i = 0; i < dROUNDS; ++i)
-        SIPROUND;
-
-    b = v0 ^ v1 ^ v2 ^ v3;
-    U64TO8_LE(out + 8, b);
-
-    return 0;
-}
diff --git a/stmt.c b/stmt.c
index e81b47b..ff163bf 100644
--- a/stmt.c
+++ b/stmt.c
@@ -1,6 +1,5 @@
 #include <assert.h>
 #include <stdbool.h>
-#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include <string.h>
diff --git a/targ.c b/targ.c
index 8402b97..81b22a8 100644
--- a/targ.c
+++ b/targ.c
@@ -1,4 +1,3 @@
-#include <stdint.h>
 #include <string.h>
 #include "util.h"
 #include "cc.h"
diff --git a/token.c b/token.c
index 1bc1249..b67baa6 100644
--- a/token.c
+++ b/token.c
@@ -2,7 +2,6 @@
 #include <ctype.h>
 #include <stdarg.h>
 #include <stdbool.h>
-#include <stdint.h>
 #include <stdio.h>
 #include <stdlib.h>
 #include "util.h"
diff --git a/tree.c b/tree.c
index 9beb976..8876da4 100644
--- a/tree.c
+++ b/tree.c
@@ -1,7 +1,6 @@
 #include <assert.h>
 #include <stdbool.h>
 #include <stddef.h>
-#include <stdint.h>
 #include "util.h"
 
 #define MAXH (sizeof(void *) * 8 * 3 / 2)
diff --git a/type.c b/type.c
index 5f6e417..8a9c440 100644
--- a/type.c
+++ b/type.c
@@ -1,7 +1,6 @@
 #include <assert.h>
 #include <stdbool.h>
 #include <stddef.h>
-#include <stdint.h>
 #include <string.h>
 #include "util.h"
 #include "cc.h"
diff --git a/util.h b/util.h
index 4108075..1e7a99c 100644
--- a/util.h
+++ b/util.h
@@ -48,7 +48,7 @@ struct map {
 };
 
 struct mapkey {
-	uint64_t hash;
+	unsigned long hash;
 	const void *str;
 	size_t len;
 };