Skip to content

Instantly share code, notes, and snippets.

@omigo

omigo/inthash.c

Forked from lh3/inthash.c
Created January 5, 2018 02:26
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save omigo/cda16bd3a508d2c6a9bc1de5a6dd2fea to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save omigo/cda16bd3a508d2c6a9bc1de5a6dd2fea to your computer and use it in GitHub Desktop.
Download ZIP

Revisions

  1. @lh3 lh3 revised this gist Nov 21, 2014. 1 changed file with 6 additions and 0 deletions.
    6 changes: 6 additions & 0 deletions inthash.c
    View file
    Original file line number Diff line number Diff line change
    @@ -1,3 +1,9 @@
    /*
    For any 1<k<=64, let mask=(1<<k)-1. hash_64() is a bijection on [0,1<<k), which means
    hash_64(x, mask)==hash_64(y, mask) if and only if x==y. hash_64i() is the inversion of
    hash_64(): hash_64i(hash_64(x, mask), mask) == hash_64(hash_64i(x, mask), mask) == x.
    */

    // Thomas Wang's integer hash functions. See <https://gist.github.com/lh3/59882d6b96166dfc3d8d> for a snapshot.
    uint64_t hash_64(uint64_t key, uint64_t mask)
    {
  2. @lh3 lh3 created this gist Nov 21, 2014.
    50 changes: 50 additions & 0 deletions inthash.c
    View file
    Original file line number Diff line number Diff line change
    @@ -0,0 +1,50 @@
    // Thomas Wang's integer hash functions. See <https://gist.github.com/lh3/59882d6b96166dfc3d8d> for a snapshot.
    uint64_t hash_64(uint64_t key, uint64_t mask)
    {
    key = (~key + (key << 21)) & mask; // key = (key << 21) - key - 1;
    key = key ^ key >> 24;
    key = ((key + (key << 3)) + (key << 8)) & mask; // key * 265
    key = key ^ key >> 14;
    key = ((key + (key << 2)) + (key << 4)) & mask; // key * 21
    key = key ^ key >> 28;
    key = (key + (key << 31)) & mask;
    return key;
    }

    // The inversion of hash_64(). Modified from <https://naml.us/blog/tag/invertible>
    uint64_t hash_64i(uint64_t key, uint64_t mask)
    {
    uint64_t tmp;

    // Invert key = key + (key << 31)
    tmp = (key - (key << 31));
    key = (key - (tmp << 31)) & mask;

    // Invert key = key ^ (key >> 28)
    tmp = key ^ key >> 28;
    key = key ^ tmp >> 28;

    // Invert key *= 21
    key = (key * 14933078535860113213ull) & mask;

    // Invert key = key ^ (key >> 14)
    tmp = key ^ key >> 14;
    tmp = key ^ tmp >> 14;
    tmp = key ^ tmp >> 14;
    key = key ^ tmp >> 14;

    // Invert key *= 265
    key = (key * 15244667743933553977ull) & mask;

    // Invert key = key ^ (key >> 24)
    tmp = key ^ key >> 24;
    key = key ^ tmp >> 24;

    // Invert key = (~key) + (key << 21)
    tmp = ~key;
    tmp = ~(key - (tmp << 21));
    tmp = ~(key - (tmp << 21));
    key = ~(key - (tmp << 21)) & mask;

    return key;
    }