XorBinaryFuse silent failure

[vprus]

There is code in XorBinaryFuse8

https://github.com/FastFilter/fastfilter_java/blob/master/fastfilter/src/main/java/org/fastfilter/xor/XorBinaryFuse8.java#L201

that appears to silently fail, and fill the fingerprint array with 0xFF.

Then, the code in mayContain goes like this:

byte f = fingerprint(hash)
f ^= fingerprints[h0] ^ fingerprints[h1] ^ fingerprints[h2];
return (f & 0xff) == 0;

that essentially becomes

f ^= 0xFF ^ 0xFF ^ 0xFF
return (f & 0xff) == 0;

or

f ^= 0xFF;
return (f & 0xFF) == 0;

or

return (f == 0xFF)

In other words, mayContain will now return false most inputs, generating false negatives.

I would suggest that this behaviour is catastrophic in practical code, and a better approach would be to modify the code to through an exception.

[lemire]

@vprus Good point. Would you consider providing a pull request?

[lemire]

@vprus Your blog at https://vladimirprus.com/blog/ seems to be missing an RSS feed.

[vprus]

I have a local patch to add an exception, so yes, can turn that into a PR.

If you're OK with AI-assisted, but human-checked PRs, I can ask Copilot to review other implementations for the same issue as well, let me know.

[vprus]

Nevermind, there seems to be 3 such places, will provide a PR shortly.

[vprus]

Created #50

[lemire]

Just for context, this path should NEVER happen. If it does, it is a bug. So yeah, generating an exception is a good way to handle it.

[vprus]

I don't really understand the underlying math, but I had around 50K strings, so I assumed that String.hashCode.toLong, while imperfect, should still work. Apparently, it did not, and my naive attempt to rehash it into 64-bit did not help either.

[lemire]

@vprus It is almost certainly the case that you have collisions. The Java implementation is a bit naive, but what we do with the other implementations is to prune the duplicates. I'll create a PR on this topic.

That should not happen with 50K strings if you have good hashing. But that's not good: String.hashCode.toLong. I think Google's Guava library must have good hash functions.

So, essentially, it fails because of a bug, and the bug is the use of an excessively weak hashing.

[vprus]

Yes, you are correct. There were two strings with the same hashCode. Using either xxhash or String.hashCode.toLong+distinct worked for me.

Thanks for your help!