hash: Add the murmur2 hash and start using it

Add implementation of the murmur2 hash function, and start using
it for our dictionaries. Our implementation is incremental
like our other hash functions.

Also remove p11_oid_hash() which wasn't being used.

In addition fix several tests whose success was based on the
way that the dictionary hashed. This was a hidden testing bug.

14 files changed, 234 insertions, 51 deletions

diff --git a/build/certs/Makefile.am b/build/certs/Makefile.am
index 1d57935..0a46b56 100644
--- a/build/certs/Makefile.am
+++ b/build/certs/Makefile.am
@@ -14,16 +14,16 @@ prepare-certs:
 	openssl x509 -in cacert3.der -inform DER -out $(TOOLS)/files/cacert3.pem
 	cat $(TOOLS)/files/cacert3.pem $(TOOLS)/files/cacert3.pem > $(TOOLS)/files/cacert3-twice.pem
 	openssl x509 -in cacert3.der -inform DER -out $(TRUST)/files/cacert3-trusted.pem \
-		-addtrust clientAuth -addtrust serverAuth -addreject emailProtection \
+		-addtrust serverAuth -addreject emailProtection \
 		-setalias "Custom Label"
-	cp $(TRUST)/files/cacert3-trusted.pem $(TOOLS)/files/cacert3-trusted-client-server-alias.pem
+	cp $(TRUST)/files/cacert3-trusted.pem $(TOOLS)/files/cacert3-trusted-server-alias.pem
 	openssl x509 -in cacert3.der -inform DER -out $(TOOLS)/files/cacert3-trusted-alias.pem \
 		-setalias "Custom Label"
 	openssl x509 -in cacert3.der -inform DER -out $(TOOLS)/files/cacert3-distrust-all.pem \
 		-addreject serverAuth -addreject clientAuth -addreject codeSigning \
 		-addreject emailProtection -addreject ipsecEndSystem -addreject ipsecTunnel \
 		-addreject ipsecUser -addreject timeStamping
-	cat $(TOOLS)/files/cacert3-trusted-client-server-alias.pem \
+	cat $(TOOLS)/files/cacert3-trusted-server-alias.pem \
 		$(TOOLS)/files/cacert3-trusted-alias.pem > $(TOOLS)/files/cacert3-trusted-multiple.pem
 	cp -v cacert-ca.der $(TRUST)/input
 	cp -v cacert-ca.der $(TRUST)/files
diff --git a/common/attrs.c b/common/attrs.c
index 5539789..cce1aaf 100644
--- a/common/attrs.c
+++ b/common/attrs.c
@@ -40,12 +40,14 @@
 #include "compat.h"
 #include "constants.h"
 #include "debug.h"
+#include "hash.h"
 #include "pkcs11.h"
 #include "pkcs11x.h"
 
 #include <assert.h>
 #include <stdarg.h>
 #include <stdio.h>
+#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -481,11 +483,12 @@ unsigned int
 p11_attr_hash (const void *data)
 {
 	const CK_ATTRIBUTE *attr = data;
-	unsigned int hash = (unsigned int)attr->type;
-	const char *p, *end;
+	uint32_t hash;
 
-	for (p = attr->pValue, end = p + attr->ulValueLen ; p != NULL && p != end; p++)
-		hash = (hash << 5) - hash + *p;
+	p11_hash_murmur2 (&hash,
+	                  &attr->type, sizeof (attr->type),
+	                  attr->pValue, (size_t)attr->ulValueLen,
+	                  NULL);
 
 	return hash;
 }
diff --git a/common/dict.c b/common/dict.c
index df8c7ac..409e3a4 100644
--- a/common/dict.c
+++ b/common/dict.c
@@ -35,10 +35,12 @@
 
 #include "debug.h"
 #include "dict.h"
+#include "hash.h"
 
 #include <sys/types.h>
 
 #include <assert.h>
+#include <stdint.h>
 #include <stdlib.h>
 #include <string.h>
 
@@ -326,13 +328,8 @@ p11_dict_size (p11_dict *dict)
 unsigned int
 p11_dict_str_hash (const void *string)
 {
-	const char *p = string;
-	unsigned int hash = *p;
-
-	if (hash)
-		for (p += 1; *p != '\0'; p++)
-			hash = (hash << 5) - hash + *p;
-
+	uint32_t hash;
+	p11_hash_murmur2 (&hash, string, strlen (string), NULL);
 	return hash;
 }
 
diff --git a/common/hash.c b/common/hash.c
index 59548fa..2041f1f 100644
--- a/common/hash.c
+++ b/common/hash.c
@@ -540,3 +540,129 @@ p11_hash_md5 (unsigned char *hash,
 	md5_final (&md5, hash);
 	md5_invalidate (&md5);
 }
+
+/*
+ *  MurmurHash.c
+ *  MYUtilities
+ *
+ *  This file created by Jens Alfke on 3/17/08.
+ *  Algorithm & source code by Austin Appleby, released to public domain.
+ *  <http://murmurhash.googlepages.com/>
+ *  Downloaded 3/16/2008.
+ *  Modified slightly by Jens Alfke (use standard uint32_t and size_t types;
+ *  change 'm' and 'r' to #defines for better C compatibility.)
+ *
+ */
+
+/*-----------------------------------------------------------------------------
+ * MurmurHash2, by Austin Appleby
+ *
+ * Note - This code makes a few assumptions about how your machine behaves -
+ *
+ * 1. We can read a 4-byte value from any address without crashing
+ * 2. sizeof(int) == 4      **Jens: I fixed this by changing 'unsigned int' to 'uint32_t'**
+ *
+ * And it has a few limitations -
+ *
+ * 1. It will not work incrementally.
+ * 2. It will not produce the same results on little-endian and big-endian
+ *    machines.
+ */
+
+void
+p11_hash_murmur2 (void *hash,
+                  const void *input,
+                  size_t len,
+                  ...)
+{
+	/*
+	 * 'm' and 'r' are mixing constants generated offline.
+	 * They're not really 'magic', they just happen to work well.
+	 * seed is arbitrarily chosen
+	 */
+
+	#define m 0x5bd1e995
+	#define r 24
+	#define seed 42
+
+	const unsigned char * data = input;
+	unsigned char overflow[4];
+	va_list va;
+	uint32_t h;
+
+	/* Initialize the hash based on the length */
+	va_start (va, len);
+	h = len;
+	while (va_arg (va, const void *))
+		h += va_arg (va, size_t);
+	h ^= seed;
+	va_end (va);
+
+	/* Mix 4 bytes at a time into the hash */
+	va_start (va, len);
+	for (;;) {
+		uint32_t k;
+
+		if (len >= 4) {
+			k = *(uint32_t *)data;
+			data += 4;
+			len -= 4;
+
+		} else {
+			size_t num = len;
+			memcpy (overflow, data, len);
+
+			while (num < 4) {
+				size_t part;
+
+				data = va_arg (va, const void *);
+				if (!data)
+					break;
+
+				/* Combine uint32 from old and new */
+				len = va_arg (va, size_t);
+				part = 4 - num;
+				if (part > len)
+					part = len;
+				memcpy (overflow + num, data, part);
+				data += part;
+				len -= part;
+				num += part;
+			}
+
+			if (num < 4) {
+				len = num;
+				break;
+			}
+
+			k = *(uint32_t *)overflow;
+		}
+
+		k *= m;
+		k ^= k >> r;
+		k *= m;
+
+		h *= m;
+		h ^= k;
+	}
+	va_end (va);
+
+	/* Handle the last few bytes of the input array */
+	switch(len) {
+	case 3: h ^= overflow[2] << 16;
+	case 2: h ^= overflow[1] << 8;
+	case 1: h ^= overflow[0];
+		h *= m;
+	};
+
+	/*
+	 * Do a few final mixes of the hash to ensure the last few
+	 * bytes are well-incorporated.
+	 */
+	h ^= h >> 13;
+	h *= m;
+	h ^= h >> 15;
+
+	assert (sizeof (h) == P11_HASH_MURMUR2_LEN);
+	memcpy (hash, &h, sizeof (h));
+}
diff --git a/common/hash.h b/common/hash.h
index f4dfce1..b06438d 100644
--- a/common/hash.h
+++ b/common/hash.h
@@ -57,4 +57,11 @@ void     p11_hash_sha1      (unsigned char *hash,
                              size_t length,
                              ...) GNUC_NULL_TERMINATED;
 
+#define P11_HASH_MURMUR2_LEN 4
+
+void     p11_hash_murmur2   (void *hash,
+                             const void *input,
+                             size_t length,
+                             ...) GNUC_NULL_TERMINATED;
+
 #endif /* P11_HASH_H_ */
diff --git a/common/oid.c b/common/oid.c
index 0c876ec..b4b0bf6 100644
--- a/common/oid.c
+++ b/common/oid.c
@@ -60,23 +60,6 @@ p11_oid_simple (const unsigned char *oid,
 	        (size_t)oid[1] == len - 2);  /* matches length */
 }
 
-unsigned int
-p11_oid_hash (const void *oid)
-{
-	const unsigned char *v = oid;
-	unsigned int hash;
-	int len;
-	int i;
-
-	len = p11_oid_length (v);
-	hash = v[0];
-
-	for (i = 1; i < len; i++)
-		hash = (hash << 5) - hash + v[i];
-
-	return hash;
-}
-
 bool
 p11_oid_equal (const void *oid_one,
                const void *oid_two)
diff --git a/common/oid.h b/common/oid.h
index 96b7a27..dee6b10 100644
--- a/common/oid.h
+++ b/common/oid.h
@@ -40,8 +40,6 @@
 bool           p11_oid_simple  (const unsigned char *oid,
                                 int len);
 
-unsigned int   p11_oid_hash    (const void *oid);
-
 bool           p11_oid_equal   (const void *oid_one,
                                 const void *oid_two);
 
diff --git a/common/tests/test-hash.c b/common/tests/test-hash.c
index 5e32c85..f57988e 100644
--- a/common/tests/test-hash.c
+++ b/common/tests/test-hash.c
@@ -35,6 +35,8 @@
 #include "config.h"
 #include "CuTest.h"
 
+#include <assert.h>
+#include <stdint.h>
 #include <stdlib.h>
 #include <stdio.h>
 #include <string.h>
@@ -128,6 +130,73 @@ test_md5 (CuTest *cu)
 	}
 }
 
+static void
+test_murmur2 (CuTest *cu)
+{
+	struct {
+		const char *input;
+		const char *input2;
+		int hash;
+	} fixtures[] = {
+		{ "one", NULL, 1910179066 },
+		{ "two", NULL, 396151652 },
+		{ "four", NULL, -2034170174 },
+		{ "seven", NULL, -588341181 },
+		/* Note that these are identical output */
+		{ "eleven", NULL, -37856894 },
+		{ "ele", "ven", -37856894 },
+		{ NULL },
+	};
+
+	uint32_t first;
+	uint32_t second;
+	int i;
+
+	assert (sizeof (first) == P11_HASH_MURMUR2_LEN);
+	for (i = 0; fixtures[i].input != NULL; i++) {
+		p11_hash_murmur2 ((unsigned char *)&first,
+		                  fixtures[i].input,
+		                  strlen (fixtures[i].input),
+		                  fixtures[i].input2,
+		                  fixtures[i].input2 ? strlen (fixtures[i].input2) : 0,
+		                  NULL);
+
+		p11_hash_murmur2 ((unsigned char *)&second,
+		                  fixtures[i].input,
+		                  strlen (fixtures[i].input),
+		                  fixtures[i].input2,
+		                  fixtures[i].input2 ? strlen (fixtures[i].input2) : 0,
+		                  NULL);
+
+		CuAssertIntEquals (cu, fixtures[i].hash, first);
+		CuAssertIntEquals (cu, fixtures[i].hash, second);
+	}
+}
+
+static void
+test_murmur2_incr (CuTest *cu)
+{
+	uint32_t first, second;
+
+	p11_hash_murmur2 ((unsigned char *)&first,
+	                  "this is the long input!", 23,
+	                  NULL);
+
+	p11_hash_murmur2 ((unsigned char *)&second,
+	                  "this", 4,
+	                  " ", 1,
+	                  "is ", 3,
+	                  "the long ", 9,
+	                  "in", 2,
+	                  "p", 1,
+	                  "u", 1,
+	                  "t", 1,
+	                  "!", 1,
+	                  NULL);
+
+	CuAssertIntEquals (cu, first, second);
+}
+
 int
 main (void)
 {
@@ -138,6 +207,8 @@ main (void)
 	SUITE_ADD_TEST (suite, test_sha1);
 	SUITE_ADD_TEST (suite, test_sha1_long);
 	SUITE_ADD_TEST (suite, test_md5);
+	SUITE_ADD_TEST (suite, test_murmur2);
+	SUITE_ADD_TEST (suite, test_murmur2_incr);
 
 	CuSuiteRun (suite);
 	CuSuiteSummary (suite, output);
diff --git a/tools/tests/files/cacert3-trusted-multiple.pem b/tools/tests/files/cacert3-trusted-multiple.pem
index 5f8071b..e56a58f 100644
--- a/tools/tests/files/cacert3-trusted-multiple.pem
+++ b/tools/tests/files/cacert3-trusted-multiple.pem
@@ -38,8 +38,8 @@ hbNc09+4ufLKxw0BFKxwWMWMjTPUnWajGlCVI/xI4AZDEtnNp4Y5LzZyo4AQ5OHz
 0ctbGsDkgJp8E3MGT9ujayQKurMcvEp4u+XjdTilSKeiHq921F73OIZWWonO1sOn
 ebJSoMbxhbQljPI/lrMQ2Y1sVzufb4Y6GIIiNsiwkTjbKqGTqoQ/9SdlrnPVyNXT
 d+pLncdBu8fA46A/5H2kjXPmEkvfoXNzczqA6NXLji/L6hOn1kGLrPo8idck9U60
-4GGSt/M3mMS+lqO3ijAwMBQGCCsGAQUFBwMCBggrBgEFBQcDAaAKBggrBgEFBQcD
-BAwMQ3VzdG9tIExhYmVs
+4GGSt/M3mMS+lqO3ijAmMAoGCCsGAQUFBwMBoAoGCCsGAQUFBwMEDAxDdXN0b20g
+TGFiZWw=
 -----END TRUSTED CERTIFICATE-----
 -----BEGIN TRUSTED CERTIFICATE-----
 MIIHWTCCBUGgAwIBAgIDCkGKMA0GCSqGSIb3DQEBCwUAMHkxEDAOBgNVBAoTB1Jv
diff --git a/tools/tests/files/cacert3-trusted-client-server-alias.pem b/tools/tests/files/cacert3-trusted-server-alias.pem
index c767eff..55593ec 100644
--- a/tools/tests/files/cacert3-trusted-client-server-alias.pem
+++ b/tools/tests/files/cacert3-trusted-server-alias.pem
@@ -38,6 +38,6 @@ hbNc09+4ufLKxw0BFKxwWMWMjTPUnWajGlCVI/xI4AZDEtnNp4Y5LzZyo4AQ5OHz
 0ctbGsDkgJp8E3MGT9ujayQKurMcvEp4u+XjdTilSKeiHq921F73OIZWWonO1sOn
 ebJSoMbxhbQljPI/lrMQ2Y1sVzufb4Y6GIIiNsiwkTjbKqGTqoQ/9SdlrnPVyNXT
 d+pLncdBu8fA46A/5H2kjXPmEkvfoXNzczqA6NXLji/L6hOn1kGLrPo8idck9U60
-4GGSt/M3mMS+lqO3ijAwMBQGCCsGAQUFBwMCBggrBgEFBQcDAaAKBggrBgEFBQcD
-BAwMQ3VzdG9tIExhYmVs
+4GGSt/M3mMS+lqO3ijAmMAoGCCsGAQUFBwMBoAoGCCsGAQUFBwMEDAxDdXN0b20g
+TGFiZWw=
 -----END TRUSTED CERTIFICATE-----
diff --git a/tools/tests/test-openssl.c b/tools/tests/test-openssl.c
index 4c39b07..dc68c19 100644
--- a/tools/tests/test-openssl.c
+++ b/tools/tests/test-openssl.c
@@ -114,10 +114,10 @@ static CK_ATTRIBUTE cacert3_authority_attrs[] = {
 	{ CKA_INVALID },
 };
 
-static CK_ATTRIBUTE extension_eku_client_server[] = {
+static CK_ATTRIBUTE extension_eku_server[] = {
 	{ CKA_CLASS, &extension_class, sizeof (extension_class) },
 	{ CKA_OBJECT_ID, (void *)P11_OID_EXTENDED_KEY_USAGE, sizeof (P11_OID_EXTENDED_KEY_USAGE) },
-	{ CKA_VALUE, (void *)test_eku_client_and_server, sizeof (test_eku_client_and_server) },
+	{ CKA_VALUE, (void *)test_eku_server, sizeof (test_eku_server) },
 	{ CKA_INVALID },
 };
 
@@ -167,7 +167,7 @@ test_file (CuTest *tc)
 	setup (tc);
 
 	setup_objects (cacert3_authority_attrs,
-	               extension_eku_client_server,
+	               extension_eku_server,
 	               extension_reject_email,
 	               NULL);
 
@@ -182,7 +182,7 @@ test_file (CuTest *tc)
 	CuAssertIntEquals (tc, true, ret);
 
 	test_check_file (tc, test.directory, "extract.pem",
-	                 SRCDIR "/files/cacert3-trusted-client-server-alias.pem");
+	                 SRCDIR "/files/cacert3-trusted-server-alias.pem");
 
 	teardown (tc);
 }
@@ -327,7 +327,7 @@ test_file_multiple (CuTest *tc)
 	setup (tc);
 
 	setup_objects (cacert3_authority_attrs,
-	               extension_eku_client_server,
+	               extension_eku_server,
 	               extension_reject_email,
 	               NULL);
 
@@ -579,7 +579,7 @@ test_directory (CuTest *tc)
 	setup (tc);
 
 	setup_objects (cacert3_authority_attrs,
-	               extension_eku_client_server,
+	               extension_eku_server,
 	               extension_reject_email,
 	               NULL);
 
@@ -604,7 +604,7 @@ test_directory (CuTest *tc)
 #endif
 	                                           NULL));
 	test_check_file (tc, test.directory, "Custom_Label.pem",
-	                 SRCDIR "/files/cacert3-trusted-client-server-alias.pem");
+	                 SRCDIR "/files/cacert3-trusted-server-alias.pem");
 	test_check_file (tc, test.directory, "Custom_Label.1.pem",
 	                 SRCDIR "/files/cacert3-trusted-alias.pem");
 #ifdef OS_UNIX
diff --git a/tools/tests/test.h b/tools/tests/test.h
index 82b8b2c..de2bdc1 100644
--- a/tools/tests/test.h
+++ b/tools/tests/test.h
@@ -193,9 +193,8 @@ static const char test_eku_server_and_client[] = {
 	0x01, 0x05, 0x05, 0x07, 0x03, 0x02,
 };
 
-static const char test_eku_client_and_server[] = {
-	0x30, 0x14, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x03, 0x02, 0x06, 0x08, 0x2b, 0x06,
-	0x01, 0x05, 0x05, 0x07, 0x03, 0x01,
+static const char test_eku_server[] = {
+	0x30, 0x0a, 0x06, 0x08, 0x2b, 0x06, 0x01, 0x05, 0x05, 0x07, 0x03, 0x01,
 };
 
 static const char test_eku_email[] = {
diff --git a/trust/tests/files/cacert3-trusted.pem b/trust/tests/files/cacert3-trusted.pem
index c767eff..55593ec 100644
--- a/trust/tests/files/cacert3-trusted.pem
+++ b/trust/tests/files/cacert3-trusted.pem
@@ -38,6 +38,6 @@ hbNc09+4ufLKxw0BFKxwWMWMjTPUnWajGlCVI/xI4AZDEtnNp4Y5LzZyo4AQ5OHz
 0ctbGsDkgJp8E3MGT9ujayQKurMcvEp4u+XjdTilSKeiHq921F73OIZWWonO1sOn
 ebJSoMbxhbQljPI/lrMQ2Y1sVzufb4Y6GIIiNsiwkTjbKqGTqoQ/9SdlrnPVyNXT
 d+pLncdBu8fA46A/5H2kjXPmEkvfoXNzczqA6NXLji/L6hOn1kGLrPo8idck9U60
-4GGSt/M3mMS+lqO3ijAwMBQGCCsGAQUFBwMCBggrBgEFBQcDAaAKBggrBgEFBQcD
-BAwMQ3VzdG9tIExhYmVs
+4GGSt/M3mMS+lqO3ijAmMAoGCCsGAQUFBwMBoAoGCCsGAQUFBwMEDAxDdXN0b20g
+TGFiZWw=
 -----END TRUSTED CERTIFICATE-----
diff --git a/trust/tests/test-parser.c b/trust/tests/test-parser.c
index 69049f7..7998d97 100644
--- a/trust/tests/test-parser.c
+++ b/trust/tests/test-parser.c
@@ -203,8 +203,7 @@ test_parse_openssl_trusted (CuTest *cu)
 		{ CKA_CLASS, &certificate_extension, sizeof (certificate_extension), },
 		{ CKA_OBJECT_ID, (void *)P11_OID_EXTENDED_KEY_USAGE, sizeof (P11_OID_EXTENDED_KEY_USAGE) },
 		{ CKA_X_CRITICAL, &truev, sizeof (truev) },
-		{ CKA_VALUE, "\x30\x14\x06\x08\x2b\x06\x01\x05\x05\x07\x03\x01\x06\x08\x2b\x06"
-			"\x01\x05\x05\x07\x03\x02", 22 },
+		{ CKA_VALUE, "\x30\x0a\x06\x08\x2b\x06\x01\x05\x05\x07\x03\x01", 12 },
 		{ CKA_INVALID },
 	};