Skip to content

Instantly share code, notes, and snippets.

@nothings
Created June 26, 2020 22:03
Show Gist options
  • Save nothings/09d289124cb3371c2debeb747bdfe581 to your computer and use it in GitHub Desktop.
Save nothings/09d289124cb3371c2debeb747bdfe581 to your computer and use it in GitHub Desktop.
// based on xxhash32
unsigned int hash(char *data, size_t len)
{
unsigned int hash;
if (len < 4) {
// load 3 bytes, overlapping if len < 3
static unsigned char offset1[4] = { 0,0,1,1 };
static unsigned char offset2[4] = { 0,0,0,2 };
unsigned int h = data[0] + (data[offset1[len]]<<8) + (data[offset2[len]]<<16);
h = xxprime1 + h*xxprime2;
hash = rotl(h,13) * xxprime1;
} else if (len <= 8) {
// load two 32-bit ints, overlapping if len < 8
unsigned int h0 = xxprime1 + load_unaligned_32(data+ 0 )*xxprime2;
unsigned int h1 = xxprime2 + load_unaligned_32(data+len-4)*xxprime2;
h0 = rotl(h0,13) * xxprime1;
h1 = rotl(h1,13) * xxprime1;
hash = rotl(h0,1) + rotl(h1,7);
} else {
unsigned int h0 = xxprime1 ^ xxprime2;
unsigned int h1 = xxprime2;
unsigned int h2 = 0;
unsigned int h3 = xxprime1;
if (len < 16) {
// load four 32-bit ints, partially overlapping
h0 = h0 + load_unaligned_32(data+ 0) * xxprime2;
h1 = h1 + load_unaligned_32(data+ 4) * xxprime2;
h2 = h2 + load_unaligned_32(data+len-8) * xxprime2;
h3 = h3 + load_unaligned_32(data+len-4) * xxprime2;
h0 = rotl(h0,13)*xxprime1;
h1 = rotl(h1,13)*xxprime1;
h2 = rotl(h2,13)*xxprime1;
h3 = rotl(h3,13)*xxprime1;
} else {
while (len > 16) {
h0 = h0 + load_unaligned_32(data+ 0) * xxprime2;
h1 = h1 + load_unaligned_32(data+ 4) * xxprime2;
h2 = h2 + load_unaligned_32(data+ 8) * xxprime2;
h3 = h3 + load_unaligned_32(data+12) * xxprime2;
h0 = rotl(h0,13)*xxprime1;
h1 = rotl(h1,13)*xxprime1;
h2 = rotl(h2,13)*xxprime1;
h3 = rotl(h3,13)*xxprime1;
data += 16;
len -= 16;
}
data = data + len - 16;
h0 = h0 + load_unaligned_32(data+ 0) * xxprime2;
h1 = h1 + load_unaligned_32(data+ 4) * xxprime2;
h2 = h2 + load_unaligned_32(data+ 8) * xxprime2;
h3 = h3 + load_unaligned_32(data+12) * xxprime2;
h0 = rotl(h0,13)*xxprime1;
h1 = rotl(h1,13)*xxprime1;
h2 = rotl(h2,13)*xxprime1;
h3 = rotl(h3,13)*xxprime1;
}
hash = rotl(h0,1)+rotl(h1,7)+rotl(h2,12)+rotl(h3,18);
}
hash += len;
// XXH hash avalanche
hash ^= hash >> 15;
hash *= xxprime2;
hash ^= hash >> 13;
hash *= xxprime3;
hash ^= hash >> 16;
return hash;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment