dotnet / dotnet/runtime

HashCode appears to throws away state when wrapping around length

Open
#123,356 4 comments 0 reactions 0 assignees View on GitHub
area-System.Runtime
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

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.