summaryrefslogtreecommitdiffstats
diff options
context:
space:
mode:
authorTimo Teräs <timo.teras@iki.fi>2015-06-11 16:54:13 +0300
committerTimo Teräs <timo.teras@iki.fi>2015-06-11 16:54:13 +0300
commited94d8ffbadf73fab34ca4f50b81885a0d891e56 (patch)
tree88c731cd1198194a6cd70d6f66480a323c51e4da
parent4fab9290b6a51c562cce3df1a9d99a659ed17974 (diff)
downloadapk-tools-ed94d8ffbadf73fab34ca4f50b81885a0d891e56.tar.bz2
apk-tools-ed94d8ffbadf73fab34ca4f50b81885a0d891e56.tar.xz
use murmur3_32 hash
it is more efficient than the previously used djb hash
-rw-r--r--src/blob.c51
1 files changed, 45 insertions, 6 deletions
diff --git a/src/blob.c b/src/blob.c
index 007a0cd..6a2fe92 100644
--- a/src/blob.c
+++ b/src/blob.c
@@ -200,17 +200,56 @@ apk_blob_t apk_blob_pushed(apk_blob_t buffer, apk_blob_t left)
return APK_BLOB_PTR_LEN(buffer.ptr, left.ptr - buffer.ptr);
}
-unsigned long apk_blob_hash_seed(apk_blob_t blob, unsigned long seed)
-{
- unsigned long hash = seed;
+static uint32_t murmur3_32(const char *key, uint32_t len, uint32_t seed)
+{
+ static const uint32_t c1 = 0xcc9e2d51;
+ static const uint32_t c2 = 0x1b873593;
+ static const uint32_t r1 = 15;
+ static const uint32_t r2 = 13;
+ static const uint32_t m = 5;
+ static const uint32_t n = 0xe6546b64;
+ uint32_t hash = seed;
+ const int nblocks = len / 4;
+ const uint32_t *blocks = (const uint32_t *) key;
int i;
+ for (i = 0; i < nblocks; i++) {
+ uint32_t k = blocks[i];
+ k *= c1;
+ k = (k << r1) | (k >> (32 - r1));
+ k *= c2;
+ hash ^= k;
+ hash = ((hash << r2) | (hash >> (32 - r2))) * m + n;
+ }
- for (i = 0; i < blob.len; i++)
- hash = hash * 33 + blob.ptr[i];
-
+ const uint8_t *tail = (const uint8_t *) (key + nblocks * 4);
+ uint32_t k1 = 0;
+
+ switch (len & 3) {
+ case 3:
+ k1 ^= tail[2] << 16;
+ case 2:
+ k1 ^= tail[1] << 8;
+ case 1:
+ k1 ^= tail[0];
+ k1 *= c1;
+ k1 = (k1 << r1) | (k1 >> (32 - r1));
+ k1 *= c2;
+ hash ^= k1;
+ }
+ hash ^= len;
+ hash ^= (hash >> 16);
+ hash *= 0x85ebca6b;
+ hash ^= (hash >> 13);
+ hash *= 0xc2b2ae35;
+ hash ^= (hash >> 16);
return hash;
}
+unsigned long apk_blob_hash_seed(apk_blob_t blob, unsigned long seed)
+{
+ return murmur3_32(blob.ptr, blob.len, seed);
+}
+
unsigned long apk_blob_hash(apk_blob_t blob)
{
return apk_blob_hash_seed(blob, 5381);