ref: 8c6bf5fb064673d45f16bd9b97ccb45a54983827
parent: 77d59f66059e6632fa5dec987b05fa52315325d1
author: Ori Bernstein <ori@eigenstate.org>
date: Sun Apr 9 11:07:11 EDT 2023
hash: replace siphash with much faster metrohash
--- a/blk.c
+++ b/blk.c
@@ -366,7 +366,7 @@
return -1;
bh = UNPACK64(b->data);
/* the hash covers the log and offset */
- if(bh != siphash(b->data+Loghashsz, Logspc-Loghashsz)){+ if(bh != bufhash(b->data+Loghashsz, Logspc-Loghashsz)){ werrstr("corrupt log");return -1;
}
@@ -800,7 +800,7 @@
packbp(b->buf+4, Ptrsz, &b->deadp);
break;
case Tlog:
- h = siphash(b->data + Loghashsz, Logspc-Loghashsz);
+ h = bufhash(b->data + Loghashsz, Logspc-Loghashsz);
PACK64(b->data, h);
break;
case Tdat:
--- a/fns.h
+++ b/fns.h
@@ -56,6 +56,7 @@
int blkdealloc(vlong);
ushort blkfill(Blk*);
uvlong blkhash(Blk*);
+uvlong bufhash(void*, usize);
u32int ihash(uvlong);
void finalize(Blk*);
@@ -65,7 +66,6 @@
Tree* opensnap(char*);
void closesnap(Tree*);
-uvlong siphash(void*, usize);
void reamfs(char*);
void growfs(char*);
int loadarena(Arena*, Fshdr *fi, vlong);
--- a/hash.c
+++ b/hash.c
@@ -1,32 +1,28 @@
-/*
- Copyright (c) 2013 Marek Majkowski <marek@popcount.org>
+// metrohash64.cpp
+//
+// The MIT License (MIT)
+//
+// Copyright (c) 2015 J. Andrew Rogers
+//
+// Permission is hereby granted, free of charge, to any person obtaining a copy
+// of this software and associated documentation files (the "Software"), to deal
+// in the Software without restriction, including without limitation the rights
+// to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
+// copies of the Software, and to permit persons to whom the Software is
+// furnished to do so, subject to the following conditions:
+//
+// The above copyright notice and this permission notice shall be included in all
+// copies or substantial portions of the Software.
+//
+// THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
+// IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
+// FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
+// AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
+// LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
+// OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
+// SOFTWARE.
+//
- Permission is hereby granted, free of charge, to any person obtaining a copy
- of this software and associated documentation files (the "Software"), to deal
- in the Software without restriction, including without limitation the rights
- to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
- copies of the Software, and to permit persons to whom the Software is
- furnished to do so, subject to the following conditions:
-
- The above copyright notice and this permission notice shall be included in
- all copies or substantial portions of the Software.
-
- THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
- IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
- FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
- AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
- LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
- OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
- THE SOFTWARE.
-
- Original location:
- https://github.com/majek/csiphash/
-
- Solution inspired by code from:
- Samuel Neves (supercop/crypto_auth/siphash24/little)
- djb (supercop/crypto_auth/siphash24/little2)
- Jean-Philippe Aumasson (https://131002.net/siphash/siphash24.c)
-*/
#include <u.h>
#include <libc.h>
#include <fcall.h>
@@ -53,59 +49,98 @@
HALF_ROUND(v0,v1,v2,v3,13,16); \
HALF_ROUND(v2,v1,v0,v3,17,21);
+#define rotate_right(v, k)\
+ ((v >> k) | (v << (64 - k)))
+#define read_u64(ptr) \
+ (*(u64int*)ptr)
+#define read_u32(ptr) \
+ (*(u32int*)ptr)
+#define read_u16(ptr) \
+ (*(u16int*)ptr)
+#define read_u8(ptr) \
+ (*(u8int*)ptr)
-static u64int
-siphash24(const void *src, unsigned long src_sz, const char key[16]) {- const u64int *_key = (u64int *)key;
- u64int k0 = _le64toh(_key[0]);
- u64int k1 = _le64toh(_key[1]);
- u64int b = (u64int)src_sz << 56;
- const u64int *in = (u64int*)src;
+uvlong
+metrohash64_1(void * key, u64int len, u32int seed)
+{+ static const u64int k0 = 0xC83A91E1;
+ static const u64int k1 = 0x8648DBDB;
+ static const u64int k2 = 0x7BDEC03B;
+ static const u64int k3 = 0x2F5870A5;
- u64int v0 = k0 ^ 0x736f6d6570736575ULL;
- u64int v1 = k1 ^ 0x646f72616e646f6dULL;
- u64int v2 = k0 ^ 0x6c7967656e657261ULL;
- u64int v3 = k1 ^ 0x7465646279746573ULL;
+ const uchar * ptr = key;
+ const uchar * const end = ptr + len;
+
+ u64int hash = ((((u64int) seed) + k2) * k0) + len;
+
+ if(len >= 32){+ u64int v[4];
+ v[0] = hash;
+ v[1] = hash;
+ v[2] = hash;
+ v[3] = hash;
+
+ do{+ v[0] += read_u64(ptr) * k0; ptr += 8; v[0] = rotate_right(v[0],29) + v[2];
+ v[1] += read_u64(ptr) * k1; ptr += 8; v[1] = rotate_right(v[1],29) + v[3];
+ v[2] += read_u64(ptr) * k2; ptr += 8; v[2] = rotate_right(v[2],29) + v[0];
+ v[3] += read_u64(ptr) * k3; ptr += 8; v[3] = rotate_right(v[3],29) + v[1];
+ }
+ while(ptr <= (end - 32));
- while (src_sz >= 8) {- u64int mi = _le64toh(*in);
- in += 1; src_sz -= 8;
- v3 ^= mi;
- DOUBLE_ROUND(v0,v1,v2,v3);
- v0 ^= mi;
+ v[2] ^= rotate_right(((v[0] + v[3]) * k0) + v[1], 33) * k1;
+ v[3] ^= rotate_right(((v[1] + v[2]) * k1) + v[0], 33) * k0;
+ v[0] ^= rotate_right(((v[0] + v[2]) * k0) + v[3], 33) * k1;
+ v[1] ^= rotate_right(((v[1] + v[3]) * k1) + v[2], 33) * k0;
+ hash += v[0] ^ v[1];
}
-
- u64int t = 0; u8int *pt = (u8int *)&t; u8int *m = (u8int *)in;
- switch (src_sz) {- case 7: pt[6] = m[6];
- case 6: pt[5] = m[5];
- case 5: pt[4] = m[4];
- case 4: *((u32int*)&pt[0]) = *((u32int*)&m[0]); break;
- case 3: pt[2] = m[2];
- case 2: pt[1] = m[1];
- case 1: pt[0] = m[0];
+
+ if((end - ptr) >= 16){+ u64int v0 = hash + (read_u64(ptr) * k0); ptr += 8; v0 = rotate_right(v0,33) * k1;
+ u64int v1 = hash + (read_u64(ptr) * k1); ptr += 8; v1 = rotate_right(v1,33) * k2;
+ v0 ^= rotate_right(v0 * k0, 35) + v1;
+ v1 ^= rotate_right(v1 * k3, 35) + v0;
+ hash += v1;
}
- b |= _le64toh(t);
+
+ if((end - ptr) >= 8){+ hash += read_u64(ptr) * k3; ptr += 8;
+ hash ^= rotate_right(hash, 33) * k1;
+
+ }
+
+ if((end - ptr) >= 4){+ hash += read_u32(ptr) * k3; ptr += 4;
+ hash ^= rotate_right(hash, 15) * k1;
+ }
+
+ if((end - ptr) >= 2){+ hash += read_u16(ptr) * k3; ptr += 2;
+ hash ^= rotate_right(hash, 13) * k1;
+ }
+
+ if((end - ptr) >= 1){+ hash += read_u8 (ptr) * k3;
+ hash ^= rotate_right(hash, 25) * k1;
+ }
+
+ hash ^= rotate_right(hash, 33);
+ hash *= k0;
+ hash ^= rotate_right(hash, 33);
- v3 ^= b;
- DOUBLE_ROUND(v0,v1,v2,v3);
- v0 ^= b; v2 ^= 0xff;
- DOUBLE_ROUND(v0,v1,v2,v3);
- DOUBLE_ROUND(v0,v1,v2,v3);
- return (v0 ^ v1) ^ (v2 ^ v3);
+ return hash;
}
uvlong
-siphash(void *src, usize len)
+bufhash(void *src, usize len)
{- static char key[16] = "gefsgefsgefsgefs";
- return siphash24(src, len, key);
+ return metrohash64_1(src, len, 0x6765);
}
uvlong
blkhash(Blk *b)
{- return siphash(b->buf, Blksz);
+ return metrohash64_1(b->buf, Blksz, 0x6765);
}
u32int
--- a/pack.c
+++ b/pack.c
@@ -522,7 +522,7 @@
packarena(char *p, int sz, Arena *a, Fshdr *fi)
{assert(sz == Blksz);
- memcpy(p, "gefs0002", 8); p += 8;
+ memcpy(p, "gefs0003", 8); p += 8;
PACK32(p, Blksz); p += 4;
PACK32(p, Bufspc); p += 4;
PACK32(p, fi->snap.ht); p += 4;
@@ -545,7 +545,7 @@
assert(sz == Blksz);
memset(a, 0, sizeof(*a));
memset(fi, 0, sizeof(*fi));
- if(memcmp(p, "gefs0002", 8) != 0){+ if(memcmp(p, "gefs0003", 8) != 0){ werrstr("wrong block header %.8s\n", p);return nil;
}