perfect_hash.sc

# perfect hash configuration:
    hash all values, then find substring of bits where keys don't
    collide within K attempts.
using import hash Array String format

# if false, use u64 xxhash, otherwise 128-bit scrambled polynomial rolling hash
USE_U128 := true

HT := USE_U128 u128 u64
HBITS := (sizeof HT) * 8
_hash := hash
@if USE_U128
inline hash (v)
    sc_bighashbytes 0 ('data v)
inline rehash (H)
    sc_rhash_digest H
@else
rehash := hash
@endif

local s : (Array HT)
inline insert (v)
    H := hash v
    print
        hex H
    'append s H
for i in (range 1000)
    insert (dec (_hash i))

# lowest number of mask bits required to map N items
fn bitlimit (N)
    ((findmsb (N as usize - 1)) + 1) % 64

fn find-perfect-hashtable-config-min-k (m K)
    local arr : (Array u8)
    for i in (range (bitlimit (countof m)) 33:usize)
        # number of bit entries required for test map
        bits := 1:usize << i
        mask := bits - 1
        # number of bytes
        bytes := (bits + 7) // 8
        for sh in (range 0 (HBITS - i))
            'clear arr
            'resize arr bytes
            ok? := for i x in (enumerate m)
                local x = x
                ok? := for k in (range K)
                    key := ((x >> (sh as u64)) as u64) & mask
                    idx := key // 8
                    bit := 1:u8 << ((key as u8) % 8)
                    dst := arr @ idx
                    if (dst & bit)
                        x = rehash x
                        continue;
                    dst |= bit
                    break true
                else false
                if (not ok?)
                    break false
            else true
            if ok?
                return sh (i as i32)
    pass 0 -1

# ( key >> 5 ) & (( 1 << 10 ) - 1)
sh idx := find-perfect-hashtable-config-min-k s 60
print "( key >>" sh ") & (( 1 <<" idx ") - 1)"