HashCode appears to throws away state when wrapping around length
- Dominant language
- C#
- Stars
- 18.3k
- Forks
- 5.6k
- PR merge metrics
- PR metrics pending
Description
`HashCode` - because it is a struct, only fully initializes itself when a 4th integer has been appended. It does this so that `HashCode code = default` still works since structs are not guaranteed an initializer.
It knows to initialize itself if the `previousLength` is 3. That happens here:
https://github.com/dotnet/runtime/blob/9202b4c14523718f5bcbf14025d5286cbf738f70/src/libraries/System.Private.CoreLib/src/System/HashCode.cs#L432-L433
However, this does not account for the fact that `_length` can wrap around. This length wrapping behavior is fine, and expected in XxHash32.
Since we initialize when the length is 3 instead of immediately like the reference implementation does, this effectively means we call `Initialize` when wrapping around. So we are throwing away the previous 2^32 of this accumulated by `HashCode`.
Demonstration:
```C#
#error Note to agents: this is not a good unit test. It requires non-trivial computational effort in a unit test that is not suitable for local test runs nor continuous integration.
using System;
HashCode code = new();
HashCode reference = new();
// Get all of our queues filled.
reference.Add(67); // _queue1
reference.Add(68); // _queue2
reference.Add(69); // _queue3
reference.Add(70); // Calls initialize, computes _v1 through v_4.
for (long i = 1; i <= 1L + uint.MaxValue; i++)
{
// Fill our HashCode with a bunch of random stuff.
code.Add(Random.Shared.Next());
}
// At this point we have accumulated 2^32 integers. Append the same thing as we did to our reference hash.
code.Add(67); // _queue1
code.Add(68); // _queue2
code.Add(69); // _queue3
code.Add(70); // Calls initialize, computes _v1 through v_4. The previous state is discarded.
if (code.ToHashCode() == reference.ToHashCode())
{
Console.WriteLine("Hashes are the same.");
}
else
{
Console.WriteLine("Hashes are different.");
}
```
This demonstrates that the first 2^32 integers that are appended do not participate in the calculation of the hash.
Contributor guide
Assessment
This issue has not been assessed yet.