Hasher.cs (15120B)
1 using Std; 2 using Std.Clone; 3 using Std.Convert; 4 using Std.Hashing; 5 using Std.Maybe; 6 using Std.Num; 7 using Std.Result; 8 using System; 9 using System.Runtime.CompilerServices; 10 using System.Security.Cryptography; 11 using System.Runtime.InteropServices; 12 #region Namespaces 13 namespace XXHash { 14 #region Types 15 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 16 struct Buffer: IClone<Buffer>, IInto<Buffer> { 17 18 #region Type-level Constructors 19 #endregion 20 21 #region Instance Constructors 22 public Buffer() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 23 [MethodImpl(MethodImplOptions.AggressiveInlining)] 24 Buffer(byte[] data, ulong len) => (_data, _len) = (data, len); 25 #endregion 26 27 #region Type-level Fields 28 #endregion 29 30 #region Instance Fields 31 readonly byte[] _data; 32 internal ulong _len; 33 #endregion 34 35 #region Type-level Properties 36 #endregion 37 38 #region Instance Properties 39 #endregion 40 41 #region Type-level Functions 42 [MethodImpl(MethodImplOptions.AggressiveInlining)] 43 internal static Buffer Default() => new(new byte[Functions.CHUNK_SIZE], ulong.MinValue); 44 #endregion 45 46 #region Instance Functions 47 [MethodImpl(MethodImplOptions.AggressiveInlining)] 48 readonly ulong Available() => Functions.CHUNK_SIZE - _len; 49 public readonly Buffer Clone() { 50 51 var data = new byte[_data.Length]; 52 53 for (var i = 0; i < data.Length; i++) { 54 data[i] = _data[i]; 55 } 56 return new(data, _len); 57 } 58 [MethodImpl(MethodImplOptions.AggressiveInlining)] 59 internal ReadOnlySpan<byte> Consume(ReadOnlySpan<byte> data) { 60 61 var toUse = Math.Min(Available(), (ulong)data.Length); 62 var remaining = data[(int)toUse..]; 63 data = data[..(int)toUse]; 64 var len = (int)_len; 65 66 for (var i = 0; i < (int)toUse; i++) { 67 _data[len + i] = data[i]; 68 } 69 _len += toUse; 70 return remaining; 71 } 72 [MethodImpl(MethodImplOptions.AggressiveInlining)] 73 internal readonly ReadOnlySpan<byte> Data() => _data.AsSpan(0, (int)_len); 74 public override readonly bool Equals(object? _) => false; 75 public override readonly int GetHashCode() => 0; 76 public readonly Buffer Into() => this; 77 [MethodImpl(MethodImplOptions.AggressiveInlining)] 78 internal readonly bool IsEmpty() => _len == ulong.MinValue; 79 [MethodImpl(MethodImplOptions.AggressiveInlining)] 80 internal readonly bool IsFull() => _len == Functions.CHUNK_SIZE; 81 [MethodImpl(MethodImplOptions.AggressiveInlining)] 82 internal Unit SetData(ReadOnlySpan<byte> data) { 83 System.Diagnostics.Debug.Assert(IsEmpty()); 84 System.Diagnostics.Debug.Assert(data.Length < (int)Functions.CHUNK_SIZE); 85 86 for (var i = 0; i < data.Length; i++) { 87 _data[i] = data[i]; 88 } 89 _len = (ulong)data.Length; 90 return new Unit(); 91 } 92 public override readonly string ToString() => string.Empty; 93 readonly Result<Buffer, Bottom> ITryInto<Buffer, Bottom>.TryInto() => new(this); 94 #endregion 95 96 #region Operators 97 #endregion 98 99 #region Types 100 #endregion 101 } 102 [StructLayout(LayoutKind.Explicit, CharSet = CharSet.Unicode, Pack = 8, Size = 8)] 103 public readonly struct RandomXXHashBuilder: IBuildHasher<XXHasher>, IClone<RandomXXHashBuilder>, IInto<RandomXXHashBuilder> { 104 105 #region Type-level Constructors 106 #endregion 107 108 #region Instance Constructors 109 [MethodImpl(MethodImplOptions.AggressiveInlining)] 110 public RandomXXHashBuilder() => _seed = ulong.MinValue; 111 [MethodImpl(MethodImplOptions.AggressiveInlining)] 112 RandomXXHashBuilder(ulong seed) => _seed = seed; 113 #endregion 114 115 #region Type-level Fields 116 #endregion 117 118 #region Instance Fields 119 [FieldOffset(0)]readonly ulong _seed; 120 #endregion 121 122 #region Type-level Properties 123 #endregion 124 125 #region Instance Properties 126 #endregion 127 128 #region Type-level Functions 129 [MethodImpl(MethodImplOptions.AggressiveInlining)] 130 public static RandomXXHashBuilder New() { 131 132 Span<byte> key = stackalloc byte[8]; 133 RandomNumberGenerator.Fill(key); 134 return new(BitConverter.ToUInt64(key)); 135 } 136 #endregion 137 138 #region Instance Functions 139 public readonly XXHasher BuildHasher() => XXHasher.WithSeed(_seed); 140 public readonly RandomXXHashBuilder Clone() => this; 141 public override readonly bool Equals(object? _) => false; 142 public override readonly int GetHashCode() => 0; 143 public readonly RandomXXHashBuilder Into() => this; 144 public override readonly string ToString() => "RandomXXHashBuilder"; 145 readonly Result<RandomXXHashBuilder, Bottom> ITryInto<RandomXXHashBuilder, Bottom>.TryInto() => new(this); 146 #endregion 147 148 #region Operators 149 #endregion 150 151 #region Types 152 #endregion 153 } 154 [StructLayout(LayoutKind.Explicit, CharSet = CharSet.Unicode, Pack = 8, Size = 32)] 155 struct XxCore: IClone<XxCore>, IInto<XxCore> { 156 157 #region Type-level Constructors 158 #endregion 159 160 #region Instance Constructors 161 public XxCore() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 162 [MethodImpl(MethodImplOptions.AggressiveInlining)] 163 XxCore(ulong v1, ulong v2, ulong v3, ulong v4) => (_v1, _v2, _v3, _v4) = (v1, v2, v3, v4); 164 #endregion 165 166 #region Type-level Fields 167 #endregion 168 169 #region Instance Fields 170 [FieldOffset(0)] ulong _v1; 171 [FieldOffset(8)] ulong _v2; 172 [FieldOffset(16)] ulong _v3; 173 [FieldOffset(24)] ulong _v4; 174 #endregion 175 176 #region Type-level Properties 177 #endregion 178 179 #region Instance Properties 180 #endregion 181 182 #region Type-level Functions 183 [MethodImpl(MethodImplOptions.AggressiveInlining)] 184 internal static XxCore WithSeed(ulong seed) => new(seed + Functions.PRIME_1 + Functions.PRIME_2, seed + Functions.PRIME_2, seed, seed - Functions.PRIME_1); 185 #endregion 186 187 #region Instance Functions 188 public readonly XxCore Clone() => this; 189 public override readonly bool Equals(object? _) => false; 190 [MethodImpl(MethodImplOptions.AggressiveInlining)] 191 internal readonly ulong Finish() { 192 193 var hash = _v1.RotateLeft(1u) + _v2.RotateLeft(7u) + _v3.RotateLeft(12u) + _v4.RotateLeft(18u); 194 static ulong MixOne(ulong hash, ulong value) => ((hash ^ ((value * Functions.PRIME_2).RotateLeft(31u) * Functions.PRIME_1)) * Functions.PRIME_1) + Functions.PRIME_4; 195 hash = MixOne(hash, _v1); 196 hash = MixOne(hash, _v2); 197 hash = MixOne(hash, _v3); 198 hash = MixOne(hash, _v4); 199 return hash; 200 } 201 public override readonly int GetHashCode() => 0; 202 [MethodImpl(MethodImplOptions.AggressiveInlining)] 203 internal Unit IngestChunks(ref UnalignedBuffer values) { 204 205 static ulong IngestOneNumber(ulong currentValue, ulong value) => (currentValue + (value * Functions.PRIME_2)).RotateLeft(31u) * Functions.PRIME_1; 206 var (v1, v2, v3, v4) = (_v1, _v2, _v3, _v4); 207 var next = values.Next4UlongReadOnlySpan(out var exists); 208 209 while (exists) { 210 v1 = IngestOneNumber(v1, next[0]); 211 v2 = IngestOneNumber(v2, next[1]); 212 v3 = IngestOneNumber(v3, next[2]); 213 v4 = IngestOneNumber(v4, next[3]); 214 next = values.Next4UlongReadOnlySpan(out exists); 215 } 216 (_v1, _v2, _v3, _v4) = (v1, v2, v3, v4); 217 return new Unit(); 218 } 219 public readonly XxCore Into() => this; 220 public override readonly string ToString() => string.Empty; 221 readonly Result<XxCore, Bottom> ITryInto<XxCore, Bottom>.TryInto() => new(this); 222 #endregion 223 224 #region Operators 225 #endregion 226 227 #region Types 228 #endregion 229 } 230 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 0)] 231 public struct XXHasher: IClone<XXHasher>, IHasher, IInto<XXHasher> { 232 233 #region Type-level Constructors 234 #endregion 235 236 #region Instance Constructors 237 [MethodImpl(MethodImplOptions.AggressiveInlining)] 238 public XXHasher() => (_totalLen, _seed, _core, _buffer) = (ulong.MinValue, ulong.MinValue, XxCore.WithSeed(ulong.MinValue), Buffer.Default()); 239 [MethodImpl(MethodImplOptions.AggressiveInlining)] 240 public XXHasher(ulong seed) => (_totalLen, _seed, _core, _buffer) = (ulong.MinValue, seed, XxCore.WithSeed(seed), Buffer.Default()); 241 [MethodImpl(MethodImplOptions.AggressiveInlining)] 242 XXHasher(ulong totalLen, ulong seed, XxCore core, Buffer buffer) => (_totalLen, _seed, _core, _buffer) = (totalLen, seed, core, buffer); 243 #endregion 244 245 #region Type-level Fields 246 #endregion 247 248 #region Instance Fields 249 XxCore _core; 250 Buffer _buffer; 251 ulong _totalLen; 252 readonly ulong _seed; 253 #endregion 254 255 #region Type-level Properties 256 #endregion 257 258 #region Instance Properties 259 #endregion 260 261 #region Type-level Functions 262 [MethodImpl(MethodImplOptions.AggressiveInlining)] 263 public static XXHasher WithSeed(ulong seed) => new(ulong.MinValue, seed, XxCore.WithSeed(seed), Buffer.Default()); 264 #endregion 265 266 #region Instance Functions 267 public readonly XXHasher Clone() => new(_totalLen, _seed, _core.Clone(), _buffer.Clone()); 268 public override readonly bool Equals(object? _) => false; 269 [MethodImpl(MethodImplOptions.AggressiveInlining)] 270 public readonly ulong Finish() { 271 272 var hash = (_totalLen >= Functions.CHUNK_SIZE ? _core.Finish() : _seed + Functions.PRIME_5) + _totalLen; 273 var bufferedUlongs = UnalignedBuffer.New(_buffer.Data()); 274 Maybe<ulong> bufferedUlong; 275 276 while ((bufferedUlong = bufferedUlongs.NextUlong()).IsSome) { 277 hash = ((hash ^ ((bufferedUlong.Unwrap() * Functions.PRIME_2).RotateLeft(31u) * Functions.PRIME_1)).RotateLeft(27u) * Functions.PRIME_1) + Functions.PRIME_4; 278 } 279 var bufferedUints = UnalignedBuffer.New(bufferedUlongs.Remaining()); 280 Maybe<uint> bufferedUint; 281 282 while ((bufferedUint = bufferedUints.NextUint()).IsSome) { 283 hash = ((hash ^ (bufferedUint.Unwrap() * Functions.PRIME_1)).RotateLeft(23u) * Functions.PRIME_2) + Functions.PRIME_3; 284 } 285 var bufferedBytes = bufferedUints.Remaining(); 286 287 for (var i = 0; i < bufferedBytes.Length; i++) { 288 hash = (hash ^ (bufferedBytes[i] * Functions.PRIME_5)).RotateLeft(11u) * Functions.PRIME_1; 289 } 290 hash = (hash ^ (hash >> 33)) * Functions.PRIME_2; 291 hash = (hash ^ (hash >> 29)) * Functions.PRIME_3; 292 return hash ^ (hash >> 32); 293 } 294 public override readonly int GetHashCode() => 0; 295 public readonly XXHasher Into() => this; 296 [MethodImpl(MethodImplOptions.AggressiveInlining)] 297 ReadOnlySpan<byte> MaybeConsumeBytes(ReadOnlySpan<byte> data) { 298 299 if (_buffer.IsEmpty()) { 300 return data; 301 } else { 302 data = _buffer.Consume(data); 303 304 if (_buffer.IsFull()) { 305 var ulongs = UnalignedBuffer.New(_buffer.Data()); 306 _ = _core.IngestChunks(ref ulongs); 307 System.Diagnostics.Debug.Assert(ulongs.Remaining().IsEmpty); 308 _buffer._len = ulong.MinValue; 309 } 310 return data; 311 } 312 } 313 public override readonly string ToString() => string.Empty; 314 readonly Result<XXHasher, Bottom> ITryInto<XXHasher, Bottom>.TryInto() => new(this); 315 [MethodImpl(MethodImplOptions.AggressiveInlining)] 316 public Unit WriteUnsafe<T>(T val) where T: unmanaged => IHasher.WriteDefaultUnsafe(ref this, val); 317 [MethodImpl(MethodImplOptions.AggressiveInlining)] 318 public Unit Write(ReadOnlySpan<byte> bytes) { 319 320 var remaining = MaybeConsumeBytes(bytes); 321 322 if (!remaining.IsEmpty) { 323 var rem2 = UnalignedBuffer.New(remaining); 324 _ = _core.IngestChunks(ref rem2); 325 _ = _buffer.SetData(rem2.Remaining()); 326 } 327 _totalLen += (ulong)bytes.Length; 328 return new Unit(); 329 } 330 public Unit WriteByte(byte val) => IHasher.WriteByteDefault(ref this, val); 331 public Unit WriteI128(I128 val) => IHasher.WriteI128Default(ref this, val); 332 public Unit WriteInt(int val) => IHasher.WriteIntDefault(ref this, val); 333 public Unit WriteLong(long val) => IHasher.WriteLongDefault(ref this, val); 334 public Unit WriteSbyte(sbyte val) => IHasher.WriteSbyteDefault(ref this, val); 335 public Unit WriteShort(short val) => IHasher.WriteShortDefault(ref this, val); 336 [MethodImpl(MethodImplOptions.AggressiveInlining)] 337 public Unit WriteSliceUnsafe<T>(ReadOnlySpan<T> val) where T: unmanaged => IHasher.WriteSliceDefaultUnsafe(ref this, val); 338 public Unit WriteU128(U128 val) => IHasher.WriteU128Default(ref this, val); 339 public Unit WriteUint(uint val) => IHasher.WriteUintDefault(ref this, val); 340 public Unit WriteUlong(ulong val) => IHasher.WriteUlongDefault(ref this, val); 341 public Unit WriteUshort(ushort val) => IHasher.WriteUshortDefault(ref this, val); 342 #endregion 343 344 #region Operators 345 #endregion 346 347 #region Types 348 #endregion 349 } 350 static class Functions { 351 352 #region Type-level Constructors 353 #endregion 354 355 #region Instance Constructors 356 #endregion 357 358 #region Type-level Fields 359 internal const ulong CHUNK_SIZE = 32ul; 360 internal const ulong PRIME_1 = 11_400_714_785_074_694_791ul; 361 internal const ulong PRIME_2 = 14_029_467_366_897_019_727ul; 362 internal const ulong PRIME_3 = 1_609_587_929_392_839_161ul; 363 internal const ulong PRIME_4 = 9_650_029_242_287_828_579ul; 364 internal const ulong PRIME_5 = 2_870_177_450_012_600_261ul; 365 #endregion 366 367 #region Instance Fields 368 #endregion 369 370 #region Type-level Properties 371 #endregion 372 373 #region Instance Properties 374 #endregion 375 376 #region Type-level Functions 377 #endregion 378 379 #region Instance Functions 380 #endregion 381 382 #region Operators 383 #endregion 384 385 #region Types 386 #endregion 387 } 388 #endregion 389 390 #region Namespaces 391 #endregion 392 } 393 #endregion