FNV (or Fowler–Noll–Vo) is a non-cryptographic hash function.
Python implementation
Below are self-contained implementations of FNV in Python. Feel free to grab one and drop it into your projects.
FNV-1
In [2]:
def fnv1_64(buf): h = 14695981039346656037 for c in buf: h *= 1099511628211 h &= 0xFFFFFFFFFFFFFFFF # u64 h ^= c return h
In [3]:
fnv1_64(b"Hello world") fnv1_64(b"Hello wordl")
Out [3]:
13583674344491166159
Out [3]:
13583665548398140543
FNV-1a
In [4]:
def fnv1a_64(buf): h = 14695981039346656037 for c in buf: h ^= c h *= 1099511628211 h &= 0xFFFFFFFFFFFFFFFF # u64 return h
In [5]:
fnv1a_64(b"Hello world") fnv1a_64(b"Hello wordl")
Out [5]:
2815866345377719495
Out [5]:
2823738848634196455
Usage as PRNG
This is extremely cursed.
In [6]:
class FNV1A_Random: def __init__(self): self.keybuf = bytearray(4) def seed(self, buf): self.keybuf = bytearray(len(buf) + 4) for i, c in enumerate(buf): self.keybuf[i] = c self.n = 0 def next_bit(self): h = 14695981039346656037 for rnd in range(8): for c in self.keybuf: h ^= c h *= 1099511628211 h &= 0xFFFFFFFFFFFFFFFF # u64 # Increment counter n = int.from_bytes(self.keybuf[-4:], 'big') n += 1 n = n.to_bytes(4, 'big') self.keybuf[-4] = n[0] self.keybuf[-3] = n[1] self.keybuf[-2] = n[2] self.keybuf[-1] = n[3] return (h >> 62) & 1 def next_nbit_int(self, n): i = 0 for _ in range(n): i <<= 1 i |= self.next_bit() return i
In [7]:
rng = FNV1A_Random() rng.seed(b"very epic seed") total = 0 for _ in range(500_000): n = rng.next_nbit_int(8) total += n # Should be around 127.5 total / 500_000
Out [7]:
127.483458
References and useful links
- FNV hash on Wikipedia