netcore/System.Private.CoreLib/shared/System/HashCode.cs

   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.
   4
   5 /*
   6
   7 The xxHash32 implementation is based on the code published by Yann Collet:
   8 https://raw.githubusercontent.com/Cyan4973/xxHash/5c174cfa4e45a42f94082dc0d4539b39696afea1/xxhash.c
   9
  10   xxHash - Fast Hash algorithm
  11   Copyright (C) 2012-2016, Yann Collet
  12
  13   BSD 2-Clause License (http://www.opensource.org/licenses/bsd-license.php)
  14
  15   Redistribution and use in source and binary forms, with or without
  16   modification, are permitted provided that the following conditions are
  17   met:
  18
  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
  24   distribution.
  25
  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.
  37
  38   You can contact the author at :
  39   - xxHash homepage: http://www.xxhash.com
  40   - xxHash source repository : https://github.com/Cyan4973/xxHash
  41
  42 */
  43
  44 using System.Collections.Generic;
  45 using System.ComponentModel;
  46 using System.Numerics;
  47 using System.Runtime.CompilerServices;
  48
  49 namespace System
  50 {
  51     // xxHash32 is used for the hash code.
  52     // https://github.com/Cyan4973/xxHash
  53
  54     public struct HashCode
  55     {
  56         private static readonly uint s_seed = GenerateGlobalSeed();
  57
  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;
  63
  64         private uint _v1, _v2, _v3, _v4;
  65         private uint _queue1, _queue2, _queue3;
  66         private uint _length;
  67
  68         private static unsafe uint GenerateGlobalSeed()
  69         {
  70             uint result;
  71             Interop.GetRandomBytes((byte*)&result, sizeof(uint));
  72             return result;
  73         }
  74
  75         public static int Combine<T1>(T1 value1)
  76         {
  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.
  83
  84             uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
  85
  86             uint hash = MixEmptyState();
  87             hash += 4;
  88
  89             hash = QueueRound(hash, hc1);
  90
  91             hash = MixFinal(hash);
  92             return (int)hash;
  93         }
  94
  95         public static int Combine<T1, T2>(T1 value1, T2 value2)
  96         {
  97             uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
  98             uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
  99
 100             uint hash = MixEmptyState();
 101             hash += 8;
 102
 103             hash = QueueRound(hash, hc1);
 104             hash = QueueRound(hash, hc2);
 105
 106             hash = MixFinal(hash);
 107             return (int)hash;
 108         }
 109
 110         public static int Combine<T1, T2, T3>(T1 value1, T2 value2, T3 value3)
 111         {
 112             uint hc1 = (uint)(value1?.GetHashCode() ?? 0);
 113             uint hc2 = (uint)(value2?.GetHashCode() ?? 0);
 114             uint hc3 = (uint)(value3?.GetHashCode() ?? 0);
 115
 116             uint hash = MixEmptyState();
 117             hash += 12;
 118
 119             hash = QueueRound(hash, hc1);
 120             hash = QueueRound(hash, hc2);
 121             hash = QueueRound(hash, hc3);
 122
 123             hash = MixFinal(hash);
 124             return (int)hash;
 125         }
 126
 127         public static int Combine<T1, T2, T3, T4>(T1 value1, T2 value2, T3 value3, T4 value4)
 128         {
 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);
 133
 134             Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
 135
 136             v1 = Round(v1, hc1);
 137             v2 = Round(v2, hc2);
 138             v3 = Round(v3, hc3);
 139             v4 = Round(v4, hc4);
 140
 141             uint hash = MixState(v1, v2, v3, v4);
 142             hash += 16;
 143
 144             hash = MixFinal(hash);
 145             return (int)hash;
 146         }
 147
 148         public static int Combine<T1, T2, T3, T4, T5>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5)
 149         {
 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);
 155
 156             Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
 157
 158             v1 = Round(v1, hc1);
 159             v2 = Round(v2, hc2);
 160             v3 = Round(v3, hc3);
 161             v4 = Round(v4, hc4);
 162
 163             uint hash = MixState(v1, v2, v3, v4);
 164             hash += 20;
 165
 166             hash = QueueRound(hash, hc5);
 167
 168             hash = MixFinal(hash);
 169             return (int)hash;
 170         }
 171
 172         public static int Combine<T1, T2, T3, T4, T5, T6>(T1 value1, T2 value2, T3 value3, T4 value4, T5 value5, T6 value6)
 173         {
 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);
 180
 181             Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
 182
 183             v1 = Round(v1, hc1);
 184             v2 = Round(v2, hc2);
 185             v3 = Round(v3, hc3);
 186             v4 = Round(v4, hc4);
 187
 188             uint hash = MixState(v1, v2, v3, v4);
 189             hash += 24;
 190
 191             hash = QueueRound(hash, hc5);
 192             hash = QueueRound(hash, hc6);
 193
 194             hash = MixFinal(hash);
 195             return (int)hash;
 196         }
 197
 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)
 199         {
 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);
 207
 208             Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
 209
 210             v1 = Round(v1, hc1);
 211             v2 = Round(v2, hc2);
 212             v3 = Round(v3, hc3);
 213             v4 = Round(v4, hc4);
 214
 215             uint hash = MixState(v1, v2, v3, v4);
 216             hash += 28;
 217
 218             hash = QueueRound(hash, hc5);
 219             hash = QueueRound(hash, hc6);
 220             hash = QueueRound(hash, hc7);
 221
 222             hash = MixFinal(hash);
 223             return (int)hash;
 224         }
 225
 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)
 227         {
 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);
 236
 237             Initialize(out uint v1, out uint v2, out uint v3, out uint v4);
 238
 239             v1 = Round(v1, hc1);
 240             v2 = Round(v2, hc2);
 241             v3 = Round(v3, hc3);
 242             v4 = Round(v4, hc4);
 243
 244             v1 = Round(v1, hc5);
 245             v2 = Round(v2, hc6);
 246             v3 = Round(v3, hc7);
 247             v4 = Round(v4, hc8);
 248
 249             uint hash = MixState(v1, v2, v3, v4);
 250             hash += 32;
 251
 252             hash = MixFinal(hash);
 253             return (int)hash;
 254         }
 255
 256         [MethodImpl(MethodImplOptions.AggressiveInlining)]
 257         private static void Initialize(out uint v1, out uint v2, out uint v3, out uint v4)
 258         {
 259             v1 = s_seed + Prime1 + Prime2;
 260             v2 = s_seed + Prime2;
 261             v3 = s_seed;
 262             v4 = s_seed - Prime1;
 263         }
 264
 265         [MethodImpl(MethodImplOptions.AggressiveInlining)]
 266         private static uint Round(uint hash, uint input)
 267         {
 268             return BitOperations.RotateLeft(hash + input * Prime2, 13) * Prime1;
 269         }
 270
 271         [MethodImpl(MethodImplOptions.AggressiveInlining)]
 272         private static uint QueueRound(uint hash, uint queuedValue)
 273         {
 274             return BitOperations.RotateLeft(hash + queuedValue * Prime3, 17) * Prime4;
 275         }
 276
 277         [MethodImpl(MethodImplOptions.AggressiveInlining)]
 278         private static uint MixState(uint v1, uint v2, uint v3, uint v4)
 279         {
 280             return BitOperations.RotateLeft(v1, 1) + BitOperations.RotateLeft(v2, 7) + BitOperations.RotateLeft(v3, 12) + BitOperations.RotateLeft(v4, 18);
 281         }
 282
 283         private static uint MixEmptyState()
 284         {
 285             return s_seed + Prime5;
 286         }
 287
 288         [MethodImpl(MethodImplOptions.AggressiveInlining)]
 289         private static uint MixFinal(uint hash)
 290         {
 291             hash ^= hash >> 15;
 292             hash *= Prime2;
 293             hash ^= hash >> 13;
 294             hash *= Prime3;
 295             hash ^= hash >> 16;
 296             return hash;
 297         }
 298
 299         public void Add<T>(T value)
 300         {
 301             Add(value?.GetHashCode() ?? 0);
 302         }
 303
 304         public void Add<T>(T value, IEqualityComparer<T>? comparer)
 305         {
 306             Add(comparer != null ? comparer.GetHashCode(value) : (value?.GetHashCode() ?? 0));
 307         }
 308
 309         private void Add(int value)
 310         {
 311             // The original xxHash works as follows:
 312             // 0. Initialize immediately. We can't do this in a struct (no
 313             //    default ctor).
 314             // 1. Accumulate blocks of length 16 (4 uints) into 4 accumulators.
 315             // 2. Accumulate remaining blocks of length 4 (1 uint) into the
 316             //    hash.
 317             // 3. Accumulate remaining blocks of length 1 into the hash.
 318
 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.
 322
 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
 327             // than 16 bytes.
 328
 329             // To see what's really going on here, have a look at the Combine
 330             // methods.
 331
 332             uint val = (uint)value;
 333
 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;
 338
 339             // Switch can't be inlined.
 340
 341             if (position == 0)
 342                 _queue1 = val;
 343             else if (position == 1)
 344                 _queue2 = val;
 345             else if (position == 2)
 346                 _queue3 = val;
 347             else // position == 3
 348             {
 349                 if (previousLength == 3)
 350                     Initialize(out _v1, out _v2, out _v3, out _v4);
 351
 352                 _v1 = Round(_v1, _queue1);
 353                 _v2 = Round(_v2, _queue2);
 354                 _v3 = Round(_v3, _queue3);
 355                 _v4 = Round(_v4, val);
 356             }
 357         }
 358
 359         public int ToHashCode()
 360         {
 361             // Storing the value of _length locally shaves of quite a few bytes
 362             // in the resulting machine code.
 363             uint length = _length;
 364
 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;
 369
 370             // If the length is less than 4, _v1 to _v4 don't contain anything
 371             // yet. xxHash32 treats this differently.
 372
 373             uint hash = length < 4 ? MixEmptyState() : MixState(_v1, _v2, _v3, _v4);
 374
 375             // _length is incremented once per Add(Int32) and is therefore 4
 376             // times too small (xxHash length is in bytes, not ints).
 377
 378             hash += length * 4;
 379
 380             // Mix what remains in the queue
 381
 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).
 385             if (position > 0)
 386             {
 387                 hash = QueueRound(hash, _queue1);
 388                 if (position > 1)
 389                 {
 390                     hash = QueueRound(hash, _queue2);
 391                     if (position > 2)
 392                         hash = QueueRound(hash, _queue3);
 393                 }
 394             }
 395
 396             hash = MixFinal(hash);
 397             return (int)hash;
 398         }
 399
 400 #pragma warning disable 0809
 401         // Obsolete member 'memberA' overrides non-obsolete member 'memberB'.
 402         // Disallowing GetHashCode and Equals is by design
 403
 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).
 408
 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.
 413
 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);
 417
 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
 422     }
 423 }