efm-hash

#!/usr/bin/python3

import sys

# From f3frame.h in ld-process-efm
EFM = [
    0x1220, 0x2100, 0x2420, 0x2220, 0x1100, 0x0110, 0x0420, 0x0900,
    0x1240, 0x2040, 0x2440, 0x2240, 0x1040, 0x0040, 0x0440, 0x0840,
    0x2020, 0x2080, 0x2480, 0x0820, 0x1080, 0x0080, 0x0480, 0x0880,
    0x1210, 0x2010, 0x2410, 0x2210, 0x1010, 0x0210, 0x0410, 0x0810,
    0x0020, 0x2108, 0x0220, 0x0920, 0x1108, 0x0108, 0x1020, 0x0908,
    0x1248, 0x2048, 0x2448, 0x2248, 0x1048, 0x0048, 0x0448, 0x0848,
    0x0100, 0x2088, 0x2488, 0x2110, 0x1088, 0x0088, 0x0488, 0x0888,
    0x1208, 0x2008, 0x2408, 0x2208, 0x1008, 0x0208, 0x0408, 0x0808,
    0x1224, 0x2124, 0x2424, 0x2224, 0x1124, 0x0024, 0x0424, 0x0924,
    0x1244, 0x2044, 0x2444, 0x2244, 0x1044, 0x0044, 0x0444, 0x0844,
    0x2024, 0x2084, 0x2484, 0x0824, 0x1084, 0x0084, 0x0484, 0x0884,
    0x1204, 0x2004, 0x2404, 0x2204, 0x1004, 0x0204, 0x0404, 0x0804,
    0x1222, 0x2122, 0x2422, 0x2222, 0x1122, 0x0022, 0x1024, 0x0922,
    0x1242, 0x2042, 0x2442, 0x2242, 0x1042, 0x0042, 0x0442, 0x0842,
    0x2022, 0x2082, 0x2482, 0x0822, 0x1082, 0x0082, 0x0482, 0x0882,
    0x1202, 0x0248, 0x2402, 0x2202, 0x1002, 0x0202, 0x0402, 0x0802,
    0x1221, 0x2121, 0x2421, 0x2221, 0x1121, 0x0021, 0x0421, 0x0921,
    0x1241, 0x2041, 0x2441, 0x2241, 0x1041, 0x0041, 0x0441, 0x0841,
    0x2021, 0x2081, 0x2481, 0x0821, 0x1081, 0x0081, 0x0481, 0x0881,
    0x1201, 0x2090, 0x2401, 0x2201, 0x1090, 0x0201, 0x0401, 0x0890,
    0x0221, 0x2109, 0x1110, 0x0121, 0x1109, 0x0109, 0x1021, 0x0909,
    0x1249, 0x2049, 0x2449, 0x2249, 0x1049, 0x0049, 0x0449, 0x0849,
    0x0120, 0x2089, 0x2489, 0x0910, 0x1089, 0x0089, 0x0489, 0x0889,
    0x1209, 0x2009, 0x2409, 0x2209, 0x1009, 0x0209, 0x0409, 0x0809,
    0x1120, 0x2111, 0x2490, 0x0224, 0x1111, 0x0111, 0x0490, 0x0911,
    0x0241, 0x2101, 0x0244, 0x0240, 0x1101, 0x0101, 0x0090, 0x0901,
    0x0124, 0x2091, 0x2491, 0x2120, 0x1091, 0x0091, 0x0491, 0x0891,
    0x1211, 0x2011, 0x2411, 0x2211, 0x1011, 0x0211, 0x0411, 0x0811,
    0x1102, 0x0102, 0x2112, 0x0902, 0x1112, 0x0112, 0x1022, 0x0912,
    0x2102, 0x2104, 0x0249, 0x0242, 0x1104, 0x0104, 0x0422, 0x0904,
    0x0122, 0x2092, 0x2492, 0x0222, 0x1092, 0x0092, 0x0492, 0x0892,
    0x1212, 0x2012, 0x2412, 0x2212, 0x1012, 0x0212, 0x0412, 0x0812,
    ]

# i7-9700KF has 64 KiB L1 cache per core.
# Raspberry Pi 4 has 32 KiB L1 cache per core.
# So we're aiming to fit well within that...

def test(show, a, b, c, d, offset=0):
    # 337, 0 0 0 7 = 453
    # 350, 0 0 0 1 = 426
    # 351, 0 1 12 13 = 406
    # 356, 0 0 0 1 = 385
    TABLE_SIZE = 512
    hashtable = [None for i in range(TABLE_SIZE)]

    def efmhash(efm):
        #v = ((efm >> a) ^ (efm >> b) ^ (efm << c) ^ (efm << d))   # max 2
        v = ((efm >> a) ^ (efm >> b) ^ (efm >> c) ^ (efm >> d))   # max 2
        #v = (efm ^ (efm >> 1) ^ (efm >> 3) ^ (efm >> 7))   # 2
        return v % TABLE_SIZE

    buckets = {}
    for value in range(256):
        # There may be an advantage to populating the hashtable starting from a
        # different position (to get the collisions in different places...)
        # (As it turns out: no, there isn't.)
        value = (value + offset) % 256

        efm = EFM[value]
        h = efmhash(efm)
        buckets.setdefault(h, []).append((efm, value))

        # Populate the OA hash table
        pos = h
        while hashtable[pos] is not None:
            pos = (pos + 1) % TABLE_SIZE
        hashtable[pos] = (efm, value)

    # Count the maximum number of hash collisions with this hash
    max_colls = max(len(pairs) for pairs in buckets.values())
    if show:
        for h, pairs in sorted(buckets.items()):
            if len(pairs) > 0:
                print(h, pairs)
    #return max_colls

    #print(a, b, c, d, hashtable)

    # Simulate looking up each value in the hash table
    total_reads = 0
    for efm in EFM:
        pos = efmhash(efm)
        #print("EFM", efm, "hash", pos, end=" ")
        total_reads += 1
        while hashtable[pos][0] != efm:
            total_reads += 1
            pos = (pos + 1) % TABLE_SIZE
            #print(pos, end=" ")
        #print()
    return total_reads

if False:
    result = test(False, 0, 1, 3, 7)
    print("Result:", result, "Per value:", result / 256)
    sys.exit(0)

# Tune the hash function
best_max = 1e100
best_args = None
for a in range(14):
    for b in range(14):
        for c in range(14):
            for d in range(14):
                args = [a, b, c, d]
                result = test(False, *args)
                if result < best_max:
                    best_max = result
                    best_args = args
        print(a, b, "Best:", " ".join("%4d" % i for i in best_args), "Max:", best_max)

# Tune the offset
best_max = 1e100
hash_args = best_args
best_args = None
for offset in range(256):
    args = hash_args + [offset]
    result = test(False, *args)
    print("Offset:", offset, "Result:", result)
    if result < best_max:
        best_max = result
        best_args = args

print("Best args:", best_args)
test(True, *best_args)