summaryrefslogtreecommitdiff
path: root/common
diff options
context:
space:
mode:
Diffstat (limited to 'common')
-rw-r--r--common/attrs.c11
-rw-r--r--common/dict.c11
-rw-r--r--common/hash.c126
-rw-r--r--common/hash.h7
-rw-r--r--common/oid.c17
-rw-r--r--common/oid.h2
-rw-r--r--common/tests/test-hash.c71
7 files changed, 215 insertions, 30 deletions
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);
generated by cgit v1.1 at 2024-12-25 16:52:32 +0000