Hashing.cs (21052B)
1 using Std.Clone; 2 using Std.Convert; 3 using Std.Num; 4 using Std.Result; 5 using static Std.Result.Result<Std.Hashing.SipHasher, Std.Bottom>; 6 using System; 7 using System.Runtime.CompilerServices; 8 using System.Runtime.InteropServices; 9 using System.Security.Cryptography; 10 #region Namespaces 11 namespace Std.Hashing { 12 #region Types 13 [StructLayout(LayoutKind.Sequential, CharSet = CharSet.Unicode, Pack = 1, Size = 1)] 14 public readonly struct BuildHasherDefault<THasher>: IProduct, IBuildHasher<THasher>, IClone<BuildHasherDefault<THasher>>, IInto<BuildHasherDefault<THasher>> where THasher: notnull, IHasher, new() { 15 16 #region Type-level Constructors 17 #endregion 18 19 #region Instance Constructors 20 public BuildHasherDefault(){} 21 #endregion 22 23 #region Type-level Fields 24 #endregion 25 26 #region Instance Fields 27 #endregion 28 29 #region Type-level Properties 30 #endregion 31 32 #region Instance Properties 33 #endregion 34 35 #region Type-level Functions 36 #endregion 37 38 #region Instance Functions 39 public readonly THasher BuildHasher() => new(); 40 public readonly BuildHasherDefault<THasher> Clone() => this; 41 public override readonly bool Equals(object? _) => false; 42 public override readonly int GetHashCode() => 0; 43 public readonly BuildHasherDefault<THasher> Into() => this; 44 public readonly Unit IntoUnit() => new Unit(); 45 public readonly void IntoVoid(){} 46 public override readonly string ToString() => string.Empty; 47 readonly Result<BuildHasherDefault<THasher>, Bottom> ITryInto<BuildHasherDefault<THasher>, Bottom>.TryInto() => new(this); 48 #endregion 49 50 #region Operators 51 #endregion 52 53 #region Types 54 #endregion 55 } 56 public interface IBuildHasher<THasher> where THasher: notnull, IHasher { 57 58 #region Type-level Constructors 59 #endregion 60 61 #region Instance Constructors 62 #endregion 63 64 #region Type-level Fields 65 #endregion 66 67 #region Instance Fields 68 #endregion 69 70 #region Type-level Properties 71 #endregion 72 73 #region Instance Properties 74 #endregion 75 76 #region Type-level Functions 77 #endregion 78 79 #region Instance Functions 80 public abstract THasher BuildHasher(); 81 #endregion 82 83 #region Operators 84 #endregion 85 86 #region Types 87 #endregion 88 } 89 public interface IHashable { 90 91 #region Type-level Constructors 92 #endregion 93 94 #region Instance Constructors 95 #endregion 96 97 #region Type-level Fields 98 #endregion 99 100 #region Instance Fields 101 #endregion 102 103 #region Type-level Properties 104 #endregion 105 106 #region Instance Properties 107 #endregion 108 109 #region Type-level Functions 110 #endregion 111 112 #region Instance Functions 113 [MethodImpl(MethodImplOptions.AggressiveInlining)] 114 public abstract Unit Hash<THasher>(ref THasher hasher) where THasher: notnull, IHasher; 115 #endregion 116 117 #region Operators 118 #endregion 119 120 #region Types 121 #endregion 122 } 123 public interface IHasher { 124 125 #region Type-level Constructors 126 #endregion 127 128 #region Instance Constructors 129 #endregion 130 131 #region Type-level Fields 132 #endregion 133 134 #region Instance Fields 135 #endregion 136 137 #region Type-level Properties 138 #endregion 139 140 #region Instance Properties 141 #endregion 142 143 #region Type-level Functions 144 [MethodImpl(MethodImplOptions.AggressiveInlining)] 145 protected static Unit WriteDefaultUnsafe<THasher, T>(THasher self, T val) where THasher: class, IHasher where T: unmanaged { unsafe { return self.WriteSliceUnsafe(new ReadOnlySpan<T>(&val, 1)); } } 146 [MethodImpl(MethodImplOptions.AggressiveInlining)] 147 protected static Unit WriteDefaultUnsafe<THasher, T>(ref THasher self, T val) where THasher: struct, IHasher where T: unmanaged { unsafe { return self.WriteSliceUnsafe(new ReadOnlySpan<T>(&val, 1)); } } 148 [MethodImpl(MethodImplOptions.AggressiveInlining)] 149 protected static Unit WriteByteDefault<THasher>(THasher self, byte val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 1)); } } 150 [MethodImpl(MethodImplOptions.AggressiveInlining)] 151 protected static Unit WriteByteDefault<THasher>(ref THasher self, byte val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 1)); } } 152 [MethodImpl(MethodImplOptions.AggressiveInlining)] 153 protected static Unit WriteI128Default<THasher>(THasher self, I128 val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 16)); } } 154 [MethodImpl(MethodImplOptions.AggressiveInlining)] 155 protected static Unit WriteI128Default<THasher>(ref THasher self, I128 val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 16)); } } 156 [MethodImpl(MethodImplOptions.AggressiveInlining)] 157 protected static Unit WriteIntDefault<THasher>(THasher self, int val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 4)); } } 158 [MethodImpl(MethodImplOptions.AggressiveInlining)] 159 protected static Unit WriteIntDefault<THasher>(ref THasher self, int val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 4)); } } 160 [MethodImpl(MethodImplOptions.AggressiveInlining)] 161 protected static Unit WriteLongDefault<THasher>(THasher self, long val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 8)); } } 162 [MethodImpl(MethodImplOptions.AggressiveInlining)] 163 protected static Unit WriteLongDefault<THasher>(ref THasher self, long val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 8)); } } 164 [MethodImpl(MethodImplOptions.AggressiveInlining)] 165 protected static Unit WriteSbyteDefault<THasher>(THasher self, sbyte val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 1)); } } 166 [MethodImpl(MethodImplOptions.AggressiveInlining)] 167 protected static Unit WriteSbyteDefault<THasher>(ref THasher self, sbyte val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 1)); } } 168 [MethodImpl(MethodImplOptions.AggressiveInlining)] 169 protected static Unit WriteShortDefault<THasher>(THasher self, short val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 2)); } } 170 [MethodImpl(MethodImplOptions.AggressiveInlining)] 171 protected static Unit WriteShortDefault<THasher>(ref THasher self, short val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 2)); } } 172 [MethodImpl(MethodImplOptions.AggressiveInlining)] 173 protected static Unit WriteSliceDefaultUnsafe<THasher, T>(THasher self, ReadOnlySpan<T> vals) where THasher: class, IHasher where T: unmanaged { unsafe { fixed(T* ptr = vals) { return self.Write(new(ptr, vals.Length * sizeof(T))); } } } 174 [MethodImpl(MethodImplOptions.AggressiveInlining)] 175 protected static Unit WriteSliceDefaultUnsafe<THasher, T>(ref THasher self, ReadOnlySpan<T> vals) where THasher: struct, IHasher where T: unmanaged { unsafe { fixed(T* ptr = vals) { return self.Write(new(ptr, vals.Length * sizeof(T))); } } } 176 [MethodImpl(MethodImplOptions.AggressiveInlining)] 177 protected static Unit WriteU128Default<THasher>(THasher self, U128 val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 16)); } } 178 [MethodImpl(MethodImplOptions.AggressiveInlining)] 179 protected static Unit WriteU128Default<THasher>(ref THasher self, U128 val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 16)); } } 180 [MethodImpl(MethodImplOptions.AggressiveInlining)] 181 protected static Unit WriteUintDefault<THasher>(THasher self, uint val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 4)); } } 182 [MethodImpl(MethodImplOptions.AggressiveInlining)] 183 protected static Unit WriteUintDefault<THasher>(ref THasher self, uint val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 4)); } } 184 [MethodImpl(MethodImplOptions.AggressiveInlining)] 185 protected static Unit WriteUlongDefault<THasher>(THasher self, ulong val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 8)); } } 186 [MethodImpl(MethodImplOptions.AggressiveInlining)] 187 protected static Unit WriteUlongDefault<THasher>(ref THasher self, ulong val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 8)); } } 188 [MethodImpl(MethodImplOptions.AggressiveInlining)] 189 protected static Unit WriteUshortDefault<THasher>(THasher self, ushort val) where THasher: class, IHasher { unsafe { return self.Write(new(&val, 2)); } } 190 [MethodImpl(MethodImplOptions.AggressiveInlining)] 191 protected static Unit WriteUshortDefault<THasher>(ref THasher self, ushort val) where THasher: struct, IHasher { unsafe { return self.Write(new(&val, 2)); } } 192 #endregion 193 194 #region Instance Functions 195 [MethodImpl(MethodImplOptions.AggressiveInlining)] 196 public abstract ulong Finish(); 197 [MethodImpl(MethodImplOptions.AggressiveInlining)] 198 public abstract Unit Write(ReadOnlySpan<byte> bytes); 199 [MethodImpl(MethodImplOptions.AggressiveInlining)] 200 public abstract Unit WriteUnsafe<T>(T val) where T: unmanaged; 201 [MethodImpl(MethodImplOptions.AggressiveInlining)] 202 public abstract Unit WriteByte(byte val); 203 [MethodImpl(MethodImplOptions.AggressiveInlining)] 204 public abstract Unit WriteI128(I128 val); 205 [MethodImpl(MethodImplOptions.AggressiveInlining)] 206 public abstract Unit WriteInt(int val); 207 [MethodImpl(MethodImplOptions.AggressiveInlining)] 208 public abstract Unit WriteLong(long val); 209 [MethodImpl(MethodImplOptions.AggressiveInlining)] 210 public abstract Unit WriteSbyte(sbyte val); 211 [MethodImpl(MethodImplOptions.AggressiveInlining)] 212 public abstract Unit WriteShort(short val); 213 [MethodImpl(MethodImplOptions.AggressiveInlining)] 214 public abstract Unit WriteSliceUnsafe<T>(ReadOnlySpan<T> vals) where T: unmanaged; 215 [MethodImpl(MethodImplOptions.AggressiveInlining)] 216 public abstract Unit WriteU128(U128 val); 217 [MethodImpl(MethodImplOptions.AggressiveInlining)] 218 public abstract Unit WriteUint(uint val); 219 [MethodImpl(MethodImplOptions.AggressiveInlining)] 220 public abstract Unit WriteUlong(ulong val); 221 [MethodImpl(MethodImplOptions.AggressiveInlining)] 222 public abstract Unit WriteUshort(ushort val); 223 #endregion 224 225 #region Operators 226 #endregion 227 228 #region Types 229 #endregion 230 } 231 public interface IHasher128: IHasher { 232 233 #region Type-level Constructors 234 #endregion 235 236 #region Instance Constructors 237 #endregion 238 239 #region Type-level Fields 240 #endregion 241 242 #region Instance Fields 243 #endregion 244 245 #region Type-level Properties 246 #endregion 247 248 #region Instance Properties 249 #endregion 250 251 #region Type-level Functions 252 #endregion 253 254 #region Instance Functions 255 [MethodImpl(MethodImplOptions.AggressiveInlining)] 256 public abstract U128 FinishU128(); 257 #endregion 258 259 #region Operators 260 #endregion 261 262 #region Types 263 #endregion 264 } 265 [StructLayout(LayoutKind.Explicit, CharSet = CharSet.Unicode, Pack = 8, Size = 16)] 266 public readonly struct RandomSipHashBuilder: IBuildHasher<SipHasher>, IClone<RandomSipHashBuilder>, IInto<RandomSipHashBuilder> { 267 268 #region Type-level Constructors 269 #endregion 270 271 #region Instance Constructors 272 public RandomSipHashBuilder() => _hasher = SipHasher.New(); 273 #endregion 274 275 #region Type-level Fields 276 #endregion 277 278 #region Instance Fields 279 [FieldOffset(0)] readonly SipHasher _hasher; 280 #endregion 281 282 #region Type-level Properties 283 #endregion 284 285 #region Instance Properties 286 #endregion 287 288 #region Type-level Functions 289 public static RandomSipHashBuilder New() => new(); 290 #endregion 291 292 #region Instance Functions 293 public readonly SipHasher BuildHasher() => _hasher; 294 public readonly RandomSipHashBuilder Clone() => this; 295 public override readonly bool Equals(object? _) => false; 296 public override readonly int GetHashCode() => 0; 297 public readonly RandomSipHashBuilder Into() => this; 298 public override readonly string ToString() => string.Empty; 299 readonly Result<RandomSipHashBuilder, Bottom> ITryInto<RandomSipHashBuilder, Bottom>.TryInto() => new(this); 300 #endregion 301 302 #region Operators 303 #endregion 304 305 #region Types 306 #endregion 307 } 308 [StructLayout(LayoutKind.Explicit, CharSet = CharSet.Unicode, Pack = 8, Size = 72)] 309 public struct SipHasher: IClone<SipHasher>, IHasher128, IInto<SipHasher> { 310 311 #region Type-level Constructors 312 #endregion 313 314 #region Instance Constructors 315 public SipHasher() => throw new InvalidOperationException("Parameterless constructor is not allowed to be called!"); 316 [MethodImpl(MethodImplOptions.AggressiveInlining)] 317 public SipHasher(U128 key) => (_key, _len, _tail, _state, _nTail) = (key, ulong.MinValue, ulong.MinValue, new(key.Low ^ 0x736f6d6570736575ul, key.High ^ 0x646f72616e646f6dul, key.Low ^ 0x6c7967656e657261ul, key.High ^ 0x7465646279746573ul), 0L); 318 #endregion 319 320 #region Type-level Fields 321 #endregion 322 323 #region Instance Fields 324 [FieldOffset(0)] ProdMut<ulong, ulong, ulong, ulong> _state; 325 [FieldOffset(32)] readonly U128 _key; 326 [FieldOffset(48)] ulong _len; 327 [FieldOffset(56)] ulong _tail; 328 [FieldOffset(64)] long _nTail; 329 #endregion 330 331 #region Type-level Properties 332 #endregion 333 334 #region Instance Properties 335 #endregion 336 337 #region Type-level Functions 338 [MethodImpl(MethodImplOptions.AggressiveInlining)] 339 static ulong BytesToUlongLE(ReadOnlySpan<byte> bytes, int start, int len) { 340 341 var i = 0; 342 var val = ulong.MinValue; 343 344 if (i + 3 < len) { 345 val = BitConverter.ToUInt32(bytes.Slice(start + i, 4)); 346 i += 4; 347 } 348 349 if (i + 1 < len) { 350 val |= ((ulong)BitConverter.ToUInt16(bytes.Slice(start + i, 2))) << (i * 8); 351 i += 2; 352 } 353 354 if (i < len) { 355 val |= ((ulong)bytes[start + i]) << (i * 8); 356 } 357 return val; 358 } 359 [MethodImpl(MethodImplOptions.AggressiveInlining)] 360 static Unit Compress(ref ProdMut<ulong, ulong, ulong, ulong> state) { 361 362 state.Item0 += state.Item1; 363 state.Item1 = state.Item1.RotateLeft(13u); 364 state.Item1 ^= state.Item0; 365 state.Item0 = state.Item0.RotateLeft(32u); 366 state.Item2 += state.Item3; 367 state.Item3 = state.Item3.RotateLeft(16u); 368 state.Item3 ^= state.Item2; 369 state.Item0 += state.Item3; 370 state.Item3 = state.Item3.RotateLeft(21u); 371 state.Item3 ^= state.Item0; 372 state.Item2 += state.Item1; 373 state.Item1 = state.Item1.RotateLeft(17u); 374 state.Item1 ^= state.Item2; 375 state.Item2 = state.Item2.RotateLeft(32u); 376 return new Unit(); 377 } 378 [MethodImpl(MethodImplOptions.AggressiveInlining)] 379 public static SipHasher New() { 380 381 unsafe { 382 var key = stackalloc U128[1]; 383 RandomNumberGenerator.Fill(new(key, 16)); 384 return new(*key); 385 } 386 } 387 [MethodImpl(MethodImplOptions.AggressiveInlining)] 388 public static SipHasher NewWithKey(U128 key) => new(key); 389 #endregion 390 391 #region Instance Functions 392 public readonly SipHasher Clone() => this; 393 public override readonly bool Equals(object? _) => false; 394 [MethodImpl(MethodImplOptions.AggressiveInlining)] 395 public readonly ulong Finish() { 396 397 var state = _state; 398 var b = ((_len & 255ul) << 56) | _tail; 399 state.Item3 ^= b; 400 _ = Compress(ref state); 401 state.Item0 ^= b; 402 state.Item2 ^= 255ul; 403 _ = Compress(ref state); 404 _ = Compress(ref state); 405 _ = Compress(ref state); 406 return state.Item0 ^ state.Item1 ^ state.Item2 ^ state.Item3; 407 } 408 [MethodImpl(MethodImplOptions.AggressiveInlining)] 409 public readonly U128 FinishU128() { 410 411 var state = _state; 412 var b = ((_len & 255ul) << 56) | _tail; 413 state.Item3 ^= b; 414 _ = Compress(ref state); 415 state.Item0 ^= b; 416 state.Item2 ^= 238ul; 417 _ = Compress(ref state); 418 _ = Compress(ref state); 419 _ = Compress(ref state); 420 var low = state.Item0 ^ state.Item1 ^ state.Item2 ^ state.Item3; 421 state.Item1 ^= 221ul; 422 _ = Compress(ref state); 423 _ = Compress(ref state); 424 _ = Compress(ref state); 425 return new(low, state.Item0 ^ state.Item1 ^ state.Item2 ^ state.Item3); 426 } 427 public override readonly int GetHashCode() => 0; 428 public readonly SipHasher Into() => this; 429 public override readonly string ToString() => string.Empty; 430 readonly Result<SipHasher, Bottom> ITryInto<SipHasher, Bottom>.TryInto() => OK(this); 431 [MethodImpl(MethodImplOptions.AggressiveInlining)] 432 public Unit WriteUnsafe<T>(T val) where T: unmanaged => IHasher.WriteDefaultUnsafe(ref this, val); 433 [MethodImpl(MethodImplOptions.AggressiveInlining)] 434 public Unit Write(ReadOnlySpan<byte> bytes) { 435 436 var len = bytes.Length; 437 _len += (ulong)len; 438 var needed = 0; 439 var nTail = (int)_nTail; 440 441 if (nTail != 0) { 442 needed = 8 - nTail; 443 _tail |= BytesToUlongLE(bytes, 0, Math.Min(len, needed)) << (nTail * 8); 444 445 if (len < needed) { 446 _nTail += len; 447 return new Unit(); 448 } else { 449 _state.Item3 ^= _tail; 450 _ = Compress(ref _state); 451 _state.Item0 ^= _tail; 452 _nTail = 0L; 453 } 454 } 455 var length = len - needed; 456 var left = length & 7; 457 var i = needed; 458 459 while (i < length - left) { 460 var m = BitConverter.ToUInt64(bytes.Slice(i, 8)); 461 _state.Item3 ^= m; 462 _ = Compress(ref _state); 463 _state.Item0 ^= m; 464 i += 8; 465 } 466 _tail = BytesToUlongLE(bytes, i, left); 467 _nTail = left; 468 return new Unit(); 469 } 470 [MethodImpl(MethodImplOptions.AggressiveInlining)] 471 public Unit WriteByte(byte val) => IHasher.WriteByteDefault(ref this, val); 472 [MethodImpl(MethodImplOptions.AggressiveInlining)] 473 public Unit WriteI128(I128 val) => IHasher.WriteI128Default(ref this, val); 474 [MethodImpl(MethodImplOptions.AggressiveInlining)] 475 public Unit WriteInt(int val) => IHasher.WriteIntDefault(ref this, val); 476 [MethodImpl(MethodImplOptions.AggressiveInlining)] 477 public Unit WriteLong(long val) => IHasher.WriteLongDefault(ref this, val); 478 [MethodImpl(MethodImplOptions.AggressiveInlining)] 479 public Unit WriteSbyte(sbyte val) => IHasher.WriteSbyteDefault(ref this, val); 480 [MethodImpl(MethodImplOptions.AggressiveInlining)] 481 public Unit WriteShort(short val) => IHasher.WriteShortDefault(ref this, val); 482 [MethodImpl(MethodImplOptions.AggressiveInlining)] 483 public Unit WriteSliceUnsafe<T>(ReadOnlySpan<T> val) where T: unmanaged => IHasher.WriteSliceDefaultUnsafe(ref this, val); 484 [MethodImpl(MethodImplOptions.AggressiveInlining)] 485 public Unit WriteU128(U128 val) => IHasher.WriteU128Default(ref this, val); 486 [MethodImpl(MethodImplOptions.AggressiveInlining)] 487 public Unit WriteUint(uint val) => IHasher.WriteUintDefault(ref this, val); 488 [MethodImpl(MethodImplOptions.AggressiveInlining)] 489 public Unit WriteUlong(ulong val) => IHasher.WriteUlongDefault(ref this, val); 490 [MethodImpl(MethodImplOptions.AggressiveInlining)] 491 public Unit WriteUshort(ushort val) => IHasher.WriteUshortDefault(ref this, val); 492 #endregion 493 494 #region Operators 495 #endregion 496 497 #region Types 498 #endregion 499 } 500 #endregion 501 502 #region Namespaces 503 #endregion 504 } 505 #endregion