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