1 // Licensed to the .NET Foundation under one or more agreements.
2 // The .NET Foundation licenses this file to you under the MIT license.
3 // See the LICENSE file in the project root for more information.
7 The xxHash32 implementation is based on the code published by Yann Collet:
8 https://raw.githubusercontent.com/Cyan4973/xxHash/5c174cfa4e45a42f94082dc0d4539b39696afea1/xxhash.c
10 xxHash - Fast Hash algorithm
11 Copyright (C) 2012-2016, Yann Collet
13 BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
15 Redistribution and use in source and binary forms, with or without
16 modification, are permitted provided that the following conditions are
19 * Redistributions of source code must retain the above copyright
20 notice, this list of conditions and the following disclaimer.
21 * Redistributions in binary form must reproduce the above
22 copyright notice, this list of conditions and the following disclaimer
23 in the documentation and/or other materials provided with the
26 THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
27 "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
28 LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
29 A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
30 OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
31 SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
32 LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
33 DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
34 THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
35 (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
36 OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
38 You can contact the author at :
39 - xxHash homepage: http://www.xxhash.com
40 - xxHash source repository : https://github.com/Cyan4973/xxHash
44 using System
.Collections
.Generic
;
45 using System
.ComponentModel
;
46 using System
.Numerics
;
47 using System
.Runtime
.CompilerServices
;
51 // xxHash32 is used for the hash code.
52 // https://github.com/Cyan4973/xxHash
54 public struct HashCode
56 private static readonly uint s_seed
= GenerateGlobalSeed();
58 private const uint Prime1
= 2654435761U;
59 private const uint Prime2
= 2246822519U;
60 private const uint Prime3
= 3266489917U;
61 private const uint Prime4
= 668265263U;
62 private const uint Prime5
= 374761393U;
64 private uint _v1
, _v2
, _v3
, _v4
;
65 private uint _queue1
, _queue2
, _queue3
;
68 private static unsafe uint GenerateGlobalSeed()
71 Interop
.GetRandomBytes((byte*)&result
, sizeof(uint));
75 public static int Combine
<T1
>(T1 value1
)
77 // Provide a way of diffusing bits from something with a limited
78 // input hash space. For example, many enums only have a few
79 // possible hashes, only using the bottom few bits of the code. Some
80 // collections are built on the assumption that hashes are spread
81 // over a larger space, so diffusing the bits may help the
82 // collection work more efficiently.
84 uint hc1
= (uint)(value1
?.GetHashCode() ?? 0);
86 uint hash
= MixEmptyState();
89 hash
= QueueRound(hash
, hc1
);
91 hash
= MixFinal(hash
);
95 public static int Combine
<T1
, T2
>(T1 value1
, T2 value2
)
97 uint hc1
= (uint)(value1
?.GetHashCode() ?? 0);
98 uint hc2
= (uint)(value2
?.GetHashCode() ?? 0);
100 uint hash
= MixEmptyState();
103 hash
= QueueRound(hash
, hc1
);
104 hash
= QueueRound(hash
, hc2
);
106 hash
= MixFinal(hash
);
110 public static int Combine
<T1
, T2
, T3
>(T1 value1
, T2 value2
, T3 value3
)
112 uint hc1
= (uint)(value1
?.GetHashCode() ?? 0);
113 uint hc2
= (uint)(value2
?.GetHashCode() ?? 0);
114 uint hc3
= (uint)(value3
?.GetHashCode() ?? 0);
116 uint hash
= MixEmptyState();
119 hash
= QueueRound(hash
, hc1
);
120 hash
= QueueRound(hash
, hc2
);
121 hash
= QueueRound(hash
, hc3
);
123 hash
= MixFinal(hash
);
127 public static int Combine
<T1
, T2
, T3
, T4
>(T1 value1
, T2 value2
, T3 value3
, T4 value4
)
129 uint hc1
= (uint)(value1
?.GetHashCode() ?? 0);
130 uint hc2
= (uint)(value2
?.GetHashCode() ?? 0);
131 uint hc3
= (uint)(value3
?.GetHashCode() ?? 0);
132 uint hc4
= (uint)(value4
?.GetHashCode() ?? 0);
134 Initialize(out uint v1
, out uint v2
, out uint v3
, out uint v4
);
141 uint hash
= MixState(v1
, v2
, v3
, v4
);
144 hash
= MixFinal(hash
);
148 public static int Combine
<T1
, T2
, T3
, T4
, T5
>(T1 value1
, T2 value2
, T3 value3
, T4 value4
, T5 value5
)
150 uint hc1
= (uint)(value1
?.GetHashCode() ?? 0);
151 uint hc2
= (uint)(value2
?.GetHashCode() ?? 0);
152 uint hc3
= (uint)(value3
?.GetHashCode() ?? 0);
153 uint hc4
= (uint)(value4
?.GetHashCode() ?? 0);
154 uint hc5
= (uint)(value5
?.GetHashCode() ?? 0);
156 Initialize(out uint v1
, out uint v2
, out uint v3
, out uint v4
);
163 uint hash
= MixState(v1
, v2
, v3
, v4
);
166 hash
= QueueRound(hash
, hc5
);
168 hash
= MixFinal(hash
);
172 public static int Combine
<T1
, T2
, T3
, T4
, T5
, T6
>(T1 value1
, T2 value2
, T3 value3
, T4 value4
, T5 value5
, T6 value6
)
174 uint hc1
= (uint)(value1
?.GetHashCode() ?? 0);
175 uint hc2
= (uint)(value2
?.GetHashCode() ?? 0);
176 uint hc3
= (uint)(value3
?.GetHashCode() ?? 0);
177 uint hc4
= (uint)(value4
?.GetHashCode() ?? 0);
178 uint hc5
= (uint)(value5
?.GetHashCode() ?? 0);
179 uint hc6
= (uint)(value6
?.GetHashCode() ?? 0);
181 Initialize(out uint v1
, out uint v2
, out uint v3
, out uint v4
);
188 uint hash
= MixState(v1
, v2
, v3
, v4
);
191 hash
= QueueRound(hash
, hc5
);
192 hash
= QueueRound(hash
, hc6
);
194 hash
= MixFinal(hash
);
198 public static int Combine
<T1
, T2
, T3
, T4
, T5
, T6
, T7
>(T1 value1
, T2 value2
, T3 value3
, T4 value4
, T5 value5
, T6 value6
, T7 value7
)
200 uint hc1
= (uint)(value1
?.GetHashCode() ?? 0);
201 uint hc2
= (uint)(value2
?.GetHashCode() ?? 0);
202 uint hc3
= (uint)(value3
?.GetHashCode() ?? 0);
203 uint hc4
= (uint)(value4
?.GetHashCode() ?? 0);
204 uint hc5
= (uint)(value5
?.GetHashCode() ?? 0);
205 uint hc6
= (uint)(value6
?.GetHashCode() ?? 0);
206 uint hc7
= (uint)(value7
?.GetHashCode() ?? 0);
208 Initialize(out uint v1
, out uint v2
, out uint v3
, out uint v4
);
215 uint hash
= MixState(v1
, v2
, v3
, v4
);
218 hash
= QueueRound(hash
, hc5
);
219 hash
= QueueRound(hash
, hc6
);
220 hash
= QueueRound(hash
, hc7
);
222 hash
= MixFinal(hash
);
226 public static int Combine
<T1
, T2
, T3
, T4
, T5
, T6
, T7
, T8
>(T1 value1
, T2 value2
, T3 value3
, T4 value4
, T5 value5
, T6 value6
, T7 value7
, T8 value8
)
228 uint hc1
= (uint)(value1
?.GetHashCode() ?? 0);
229 uint hc2
= (uint)(value2
?.GetHashCode() ?? 0);
230 uint hc3
= (uint)(value3
?.GetHashCode() ?? 0);
231 uint hc4
= (uint)(value4
?.GetHashCode() ?? 0);
232 uint hc5
= (uint)(value5
?.GetHashCode() ?? 0);
233 uint hc6
= (uint)(value6
?.GetHashCode() ?? 0);
234 uint hc7
= (uint)(value7
?.GetHashCode() ?? 0);
235 uint hc8
= (uint)(value8
?.GetHashCode() ?? 0);
237 Initialize(out uint v1
, out uint v2
, out uint v3
, out uint v4
);
249 uint hash
= MixState(v1
, v2
, v3
, v4
);
252 hash
= MixFinal(hash
);
256 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
257 private static void Initialize(out uint v1
, out uint v2
, out uint v3
, out uint v4
)
259 v1
= s_seed
+ Prime1
+ Prime2
;
260 v2
= s_seed
+ Prime2
;
262 v4
= s_seed
- Prime1
;
265 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
266 private static uint Round(uint hash
, uint input
)
268 return BitOperations
.RotateLeft(hash
+ input
* Prime2
, 13) * Prime1
;
271 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
272 private static uint QueueRound(uint hash
, uint queuedValue
)
274 return BitOperations
.RotateLeft(hash
+ queuedValue
* Prime3
, 17) * Prime4
;
277 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
278 private static uint MixState(uint v1
, uint v2
, uint v3
, uint v4
)
280 return BitOperations
.RotateLeft(v1
, 1) + BitOperations
.RotateLeft(v2
, 7) + BitOperations
.RotateLeft(v3
, 12) + BitOperations
.RotateLeft(v4
, 18);
283 private static uint MixEmptyState()
285 return s_seed
+ Prime5
;
288 [MethodImpl(MethodImplOptions
.AggressiveInlining
)]
289 private static uint MixFinal(uint hash
)
299 public void Add
<T
>(T
value)
301 Add(value?.GetHashCode() ?? 0);
304 public void Add
<T
>(T
value, IEqualityComparer
<T
>? comparer
)
306 Add(comparer
!= null ? comparer
.GetHashCode(value) : (value?.GetHashCode() ?? 0));
309 private void Add(int value)
311 // The original xxHash works as follows:
312 // 0. Initialize immediately. We can't do this in a struct (no
314 // 1. Accumulate blocks of length 16 (4 uints) into 4 accumulators.
315 // 2. Accumulate remaining blocks of length 4 (1 uint) into the
317 // 3. Accumulate remaining blocks of length 1 into the hash.
319 // There is no need for #3 as this type only accepts ints. _queue1,
320 // _queue2 and _queue3 are basically a buffer so that when
321 // ToHashCode is called we can execute #2 correctly.
323 // We need to initialize the xxHash32 state (_v1 to _v4) lazily (see
324 // #0) nd the last place that can be done if you look at the
325 // original code is just before the first block of 16 bytes is mixed
326 // in. The xxHash32 state is never used for streams containing fewer
329 // To see what's really going on here, have a look at the Combine
332 uint val
= (uint)value;
334 // Storing the value of _length locally shaves of quite a few bytes
335 // in the resulting machine code.
336 uint previousLength
= _length
++;
337 uint position
= previousLength
% 4;
339 // Switch can't be inlined.
343 else if (position
== 1)
345 else if (position
== 2)
347 else // position == 3
349 if (previousLength
== 3)
350 Initialize(out _v1
, out _v2
, out _v3
, out _v4
);
352 _v1
= Round(_v1
, _queue1
);
353 _v2
= Round(_v2
, _queue2
);
354 _v3
= Round(_v3
, _queue3
);
355 _v4
= Round(_v4
, val
);
359 public int ToHashCode()
361 // Storing the value of _length locally shaves of quite a few bytes
362 // in the resulting machine code.
363 uint length
= _length
;
365 // position refers to the *next* queue position in this method, so
366 // position == 1 means that _queue1 is populated; _queue2 would have
367 // been populated on the next call to Add.
368 uint position
= length
% 4;
370 // If the length is less than 4, _v1 to _v4 don't contain anything
371 // yet. xxHash32 treats this differently.
373 uint hash
= length
< 4 ? MixEmptyState() : MixState(_v1
, _v2
, _v3
, _v4
);
375 // _length is incremented once per Add(Int32) and is therefore 4
376 // times too small (xxHash length is in bytes, not ints).
380 // Mix what remains in the queue
382 // Switch can't be inlined right now, so use as few branches as
383 // possible by manually excluding impossible scenarios (position > 1
384 // is always false if position is not > 0).
387 hash
= QueueRound(hash
, _queue1
);
390 hash
= QueueRound(hash
, _queue2
);
392 hash
= QueueRound(hash
, _queue3
);
396 hash
= MixFinal(hash
);
400 #pragma warning disable 0809
401 // Obsolete member 'memberA' overrides non-obsolete member 'memberB'.
402 // Disallowing GetHashCode and Equals is by design
404 // * We decided to not override GetHashCode() to produce the hash code
405 // as this would be weird, both naming-wise as well as from a
406 // behavioral standpoint (GetHashCode() should return the object's
407 // hash code, not the one being computed).
409 // * Even though ToHashCode() can be called safely multiple times on
410 // this implementation, it is not part of the contract. If the
411 // implementation has to change in the future we don't want to worry
412 // about people who might have incorrectly used this type.
414 [Obsolete("HashCode is a mutable struct and should not be compared with other HashCodes. Use ToHashCode to retrieve the computed hash code.", error
: true)]
415 [EditorBrowsable(EditorBrowsableState
.Never
)]
416 public override int GetHashCode() => throw new NotSupportedException(SR
.HashCode_HashCodeNotSupported
);
418 [Obsolete("HashCode is a mutable struct and should not be compared with other HashCodes.", error
: true)]
419 [EditorBrowsable(EditorBrowsableState
.Never
)]
420 public override bool Equals(object? obj
) => throw new NotSupportedException(SR
.HashCode_EqualityNotSupported
);
421 #pragma warning restore 0809