implementation of fnv-1(a) with xor folding and both lazy and non-lazy reduction

fnv.py

# http://isthe.com/chongo/tech/comp/fnv/
# https://tools.ietf.org/html/draft-eastlake-fnv-11

    
FNV_PARAMS = {
    # bits -> prime, offset basis
    # see http://isthe.com/chongo/tech/comp/fnv/
    32: (16777619, 2166136261),
    64: (1099511628211, 14695981039346656037),
    128: (309485009821345068724781371, 144066263297769815596495629667062367629),
    256: (374144419156711147060143317175368453031918731002211, 100029257958052580907070968620625704837092796014241193945225284501741471925557),
    512: (35835915874844867368919076489095108449946327955754392558399825615420669938882575126094039892345713852759, 9659303129496669498009435400716310466090418745672637896108374329434462657994582932197716438449813051892206539805784495328239340083876191928701583869517785),
    1024: (5016456510113118655434598811035278955030765345404790744303017523831112055108147451509157692220295382716162651878526895249385292291816524375083746691371804094271873160484737966720260389217684476157468082573, 14197795064947621068722070641403218320880622795441933960878474914617582723252296732303717722150864096521202355549365628174669108571814760471015076148029755969804077320157692458563003215304957150157403644460363550505412711285966361610267868082893823963790439336411086884584107735010676915),
}


def fnv(data: bytes, *, bits: int = None, mod: int = None, lazy: bool = True, version: str = '1a') -> int:
    '''
    Implementation of the Fowler/Noll/Vo hash, supporting:

    - multiple versions: 0, 0a, 1, 1a (defaults to 1a)
    - output size in bits or mod value
    - xor folding for bit lengths not natively supported (see keys of FNV_PARAMS)
    - reduction with lazy or retry methods for mod values that aren't of the form 2**n
    '''

    # setup
    if version not in ('0', '0a', '1', '1a'):
        raise ValueError('invalid version')
    if (bits and mod) or not (bits or mod):
        raise ValueError('one of bits or mod required')
    if bits and bits < 0 or mod and mod < 2:
        raise ValueError('invalid range')
    if mod:
        mod_bits = math.log2(mod)
        bits = math.ceil(mod_bits)
    if bits <= 32:
        param_bits = 32
    else:
        param_bits = int(1 << math.ceil(math.log2(bits)))
    try:
        fnv_prime, offset_basis = FNV_PARAMS[param_bits]
    except KeyError:
        raise ValueError(f'no params for {param_bits} bit hash')
    bit_mask = (1 << param_bits) - 1

    # algo
    if version[0] == '0':
        hash = 0
    else:
        hash = offset_basis
    if version[-1] == 'a':
        for octet_of_data in data:
            hash ^= octet_of_data
            hash *= fnv_prime
            hash &= bit_mask
    else:
        for octet_of_data in data:
            hash *= fnv_prime
            hash ^= octet_of_data
            hash &= bit_mask

    # reduce requested size
    if mod and mod_bits.is_integer() or not mod and bits < param_bits:
        # xor fold
        bit_mask = (1 << bits) - 1
        fold_hash = 0
        while hash:
            fold_hash ^= (hash & bit_mask)
            hash >>= bits
        hash = fold_hash
    elif mod:
        # reduce the size to mod
        if not lazy:
            # reduce w/ retry method (removes bias on higher values)
            retry_level = (((1 << param_bits) - 1) // mod) * mod
            while hash >= retry_level:
                hash *= fnv_prime
                hash += offset_basis
                hash &= bit_mask

        hash %= mod

    return hash