FNV is invertible

[jbosboom]

FNV is an invertible function. Its inverse is

uint32_t ifnv(uint32_t h, string_view s) {
    for (char c : s)
        h = (h ^ c) * 0x359c449b;
    return h;
}

Then ifnv(fnv("abcd"), "dcba") == fnv(""). You can use this to speed up fnv.exe and words.py -c 2:

• Most obviously, for fnv.exe -s foo, you can inverse-hash the target(s) with the reversed suffix.
• Less obviously, fnv.exe can search longer strings using a bidirectional search: search forwards for n characters and save their hashes, then search backwards from the target(s) for m characters looking for matching hashes. This is a time-memory tradeoff, but it seems worthwhile because 37**n + 37**m is much smaller than 37**(n+m).
• A similar time-memory tradeoff is possible with words.py -c 2.

[bnnm]

Very interesting, thanks a lot for pointing this out. I've updated fnv.exe for fast suffixes and will try to optimize other stuff later.

Seems most useful for words.py to allow bigger word lists combinations, since fnv.exe is still kind of limited by the big number of false positives it makes.