Skip to content

Instantly share code, notes, and snippets.

@nothings

nothings/a string hash.c

Created June 26, 2020 22:03
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save nothings/09d289124cb3371c2debeb747bdfe581 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save nothings/09d289124cb3371c2debeb747bdfe581 to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. nothings created this gist Jun 26, 2020.
    67 changes: 67 additions & 0 deletions a string hash.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,67 @@
    // 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;
    }