| | | 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 | | |
| | | 4 | | using System.Collections.Generic; |
| | | 5 | | using System.Diagnostics; |
| | | 6 | | using System.Numerics; |
| | | 7 | | using System.Runtime.CompilerServices; |
| | | 8 | | using System.Runtime.Intrinsics; |
| | | 9 | | |
| | | 10 | | namespace System |
| | | 11 | | { |
| | | 12 | | internal static partial class SpanHelpers // .T |
| | | 13 | | { |
| | | 14 | | [Intrinsic] // Unrolled for small sizes |
| | | 15 | | public static unsafe void Fill<T>(ref T refData, nuint numElements, T value) |
| | | 16 | | { |
| | | 17 | | // Early checks to see if it's even possible to vectorize - JIT will turn these checks into consts. |
| | | 18 | | // - T cannot contain references (GC can't track references in vectors) |
| | | 19 | | // - Vectorization must be hardware-accelerated |
| | | 20 | | // - T's size must not exceed the vector's size |
| | | 21 | | // - T's size must be a whole power of 2 |
| | | 22 | | |
| | 1831 | 23 | | if (RuntimeHelpers.IsReferenceOrContainsReferences<T>()) |
| | | 24 | | { |
| | | 25 | | goto CannotVectorize; |
| | | 26 | | } |
| | | 27 | | |
| | 1831 | 28 | | if (!Vector.IsHardwareAccelerated) |
| | | 29 | | { |
| | | 30 | | goto CannotVectorize; |
| | | 31 | | } |
| | | 32 | | |
| | 1831 | 33 | | if (sizeof(T) > Vector<byte>.Count) |
| | | 34 | | { |
| | | 35 | | goto CannotVectorize; |
| | | 36 | | } |
| | | 37 | | |
| | 1831 | 38 | | if (!BitOperations.IsPow2(sizeof(T))) |
| | | 39 | | { |
| | | 40 | | goto CannotVectorize; |
| | | 41 | | } |
| | | 42 | | |
| | 1831 | 43 | | if (numElements >= (uint)(Vector<byte>.Count / sizeof(T))) |
| | | 44 | | { |
| | | 45 | | // We have enough data for at least one vectorized write. |
| | | 46 | | Vector<byte> vector; |
| | | 47 | | |
| | 1048 | 48 | | if (sizeof(T) == 1) |
| | | 49 | | { |
| | 0 | 50 | | vector = new Vector<byte>(Unsafe.BitCast<T, byte>(value)); |
| | | 51 | | } |
| | 1048 | 52 | | else if (sizeof(T) == 2) |
| | | 53 | | { |
| | 1048 | 54 | | vector = (Vector<byte>)new Vector<ushort>(Unsafe.BitCast<T, ushort>(value)); |
| | | 55 | | } |
| | 0 | 56 | | else if (sizeof(T) == 4) |
| | | 57 | | { |
| | | 58 | | // special-case float since it's already passed in a SIMD reg |
| | 0 | 59 | | vector = (typeof(T) == typeof(float)) |
| | 0 | 60 | | ? (Vector<byte>)new Vector<float>(Unsafe.BitCast<T, float>(value)) |
| | 0 | 61 | | : (Vector<byte>)new Vector<uint>(Unsafe.BitCast<T, uint>(value)); |
| | | 62 | | } |
| | 0 | 63 | | else if (sizeof(T) == 8) |
| | | 64 | | { |
| | | 65 | | // special-case double since it's already passed in a SIMD reg |
| | 0 | 66 | | vector = (typeof(T) == typeof(double)) |
| | 0 | 67 | | ? (Vector<byte>)new Vector<double>(Unsafe.BitCast<T, double>(value)) |
| | 0 | 68 | | : (Vector<byte>)new Vector<ulong>(Unsafe.BitCast<T, ulong>(value)); |
| | | 69 | | } |
| | 0 | 70 | | else if (sizeof(T) == Vector<byte>.Count) |
| | | 71 | | { |
| | 0 | 72 | | vector = Unsafe.BitCast<T, Vector<byte>>(value); |
| | | 73 | | } |
| | 0 | 74 | | else if (sizeof(T) == 16) |
| | | 75 | | { |
| | 0 | 76 | | if (Vector<byte>.Count == 32) |
| | | 77 | | { |
| | 0 | 78 | | vector = Vector256.Create(Unsafe.BitCast<T, Vector128<byte>>(value)).AsVector(); |
| | | 79 | | } |
| | 0 | 80 | | else if (Vector<byte>.Count == 64) |
| | | 81 | | { |
| | 0 | 82 | | vector = Vector512.Create(Unsafe.BitCast<T, Vector128<byte>>(value)).AsVector(); |
| | | 83 | | } |
| | | 84 | | else |
| | | 85 | | { |
| | 0 | 86 | | Debug.Fail("Vector<T> is unexpected size."); |
| | | 87 | | goto CannotVectorize; |
| | | 88 | | } |
| | | 89 | | } |
| | 0 | 90 | | else if (sizeof(T) == 32) |
| | | 91 | | { |
| | 0 | 92 | | if (Vector<byte>.Count == 64) |
| | | 93 | | { |
| | 0 | 94 | | vector = Vector512.Create(Unsafe.BitCast<T, Vector256<byte>>(value)).AsVector(); |
| | | 95 | | } |
| | | 96 | | else |
| | | 97 | | { |
| | 0 | 98 | | Debug.Fail("Vector<T> is unexpected size."); |
| | | 99 | | goto CannotVectorize; |
| | | 100 | | } |
| | | 101 | | } |
| | | 102 | | else |
| | | 103 | | { |
| | 0 | 104 | | Debug.Fail("Vector<T> is greater than 512 bits in size?"); |
| | | 105 | | goto CannotVectorize; |
| | | 106 | | } |
| | | 107 | | |
| | 1048 | 108 | | ref byte refDataAsBytes = ref Unsafe.As<T, byte>(ref refData); |
| | 1048 | 109 | | nuint totalByteLength = numElements * (nuint)sizeof(T); // get this calculation ready ahead of time |
| | 1048 | 110 | | nuint stopLoopAtOffset = totalByteLength & (nuint)(nint)(2 * (int)-Vector<byte>.Count); // intentional s |
| | 1048 | 111 | | nuint offset = 0; |
| | | 112 | | |
| | | 113 | | // Loop, writing 2 vectors at a time. |
| | | 114 | | // Compare 'numElements' rather than 'stopLoopAtOffset' because we don't want a dependency |
| | | 115 | | // on the very recently calculated 'stopLoopAtOffset' value. |
| | | 116 | | |
| | 1048 | 117 | | if (numElements >= (uint)(2 * Vector<byte>.Count / sizeof(T))) |
| | | 118 | | { |
| | | 119 | | do |
| | | 120 | | { |
| | 14969 | 121 | | Unsafe.WriteUnaligned(ref Unsafe.AddByteOffset(ref refDataAsBytes, offset), vector); |
| | 14969 | 122 | | Unsafe.WriteUnaligned(ref Unsafe.AddByteOffset(ref refDataAsBytes, offset + (nuint)Vector<byte>. |
| | 14969 | 123 | | offset += (uint)(2 * Vector<byte>.Count); |
| | 14969 | 124 | | } while (offset < stopLoopAtOffset); |
| | | 125 | | } |
| | | 126 | | |
| | | 127 | | // At this point, if any data remains to be written, it's strictly less than |
| | | 128 | | // 2 * sizeof(Vector) bytes. The loop above had us write an even number of vectors. |
| | | 129 | | // If the total byte length instead involves us writing an odd number of vectors, write |
| | | 130 | | // one additional vector now. The bit check below tells us if we're in an "odd vector |
| | | 131 | | // count" situation. |
| | | 132 | | |
| | 1048 | 133 | | if ((totalByteLength & (nuint)Vector<byte>.Count) != 0) |
| | | 134 | | { |
| | 712 | 135 | | Unsafe.WriteUnaligned(ref Unsafe.AddByteOffset(ref refDataAsBytes, offset), vector); |
| | | 136 | | } |
| | | 137 | | |
| | | 138 | | // It's possible that some small buffer remains to be populated - something that won't |
| | | 139 | | // fit an entire vector's worth of data. Instead of falling back to a loop, we'll write |
| | | 140 | | // a vector at the very end of the buffer. This may involve overwriting previously |
| | | 141 | | // populated data, which is fine since we're splatting the same value for all entries. |
| | | 142 | | // There's no need to perform a length check here because we already performed this |
| | | 143 | | // check before entering the vectorized code path. |
| | | 144 | | |
| | 1048 | 145 | | Unsafe.WriteUnaligned(ref Unsafe.AddByteOffset(ref refDataAsBytes, totalByteLength - (nuint)Vector<byte> |
| | | 146 | | |
| | | 147 | | // And we're done! |
| | | 148 | | |
| | 1048 | 149 | | return; |
| | | 150 | | } |
| | | 151 | | |
| | | 152 | | CannotVectorize: |
| | | 153 | | |
| | | 154 | | // If we reached this point, we cannot vectorize this T, or there are too few |
| | | 155 | | // elements for us to vectorize. Fall back to an unrolled loop. |
| | | 156 | | |
| | 783 | 157 | | nuint i = 0; |
| | | 158 | | |
| | | 159 | | // Write 8 elements at a time |
| | | 160 | | |
| | 783 | 161 | | if (numElements >= 8) |
| | | 162 | | { |
| | 340 | 163 | | nuint stopLoopAtOffset = numElements & ~(nuint)7; |
| | | 164 | | do |
| | | 165 | | { |
| | 340 | 166 | | Unsafe.Add(ref refData, (nint)i + 0) = value; |
| | 340 | 167 | | Unsafe.Add(ref refData, (nint)i + 1) = value; |
| | 340 | 168 | | Unsafe.Add(ref refData, (nint)i + 2) = value; |
| | 340 | 169 | | Unsafe.Add(ref refData, (nint)i + 3) = value; |
| | 340 | 170 | | Unsafe.Add(ref refData, (nint)i + 4) = value; |
| | 340 | 171 | | Unsafe.Add(ref refData, (nint)i + 5) = value; |
| | 340 | 172 | | Unsafe.Add(ref refData, (nint)i + 6) = value; |
| | 340 | 173 | | Unsafe.Add(ref refData, (nint)i + 7) = value; |
| | 340 | 174 | | } while ((i += 8) < stopLoopAtOffset); |
| | | 175 | | } |
| | | 176 | | |
| | | 177 | | // Write next 4 elements if needed |
| | | 178 | | |
| | 783 | 179 | | if ((numElements & 4) != 0) |
| | | 180 | | { |
| | 298 | 181 | | Unsafe.Add(ref refData, (nint)i + 0) = value; |
| | 298 | 182 | | Unsafe.Add(ref refData, (nint)i + 1) = value; |
| | 298 | 183 | | Unsafe.Add(ref refData, (nint)i + 2) = value; |
| | 298 | 184 | | Unsafe.Add(ref refData, (nint)i + 3) = value; |
| | 298 | 185 | | i += 4; |
| | | 186 | | } |
| | | 187 | | |
| | | 188 | | // Write next 2 elements if needed |
| | | 189 | | |
| | 783 | 190 | | if ((numElements & 2) != 0) |
| | | 191 | | { |
| | 783 | 192 | | Unsafe.Add(ref refData, (nint)i + 0) = value; |
| | 783 | 193 | | Unsafe.Add(ref refData, (nint)i + 1) = value; |
| | 783 | 194 | | i += 2; |
| | | 195 | | } |
| | | 196 | | |
| | | 197 | | // Write final element if needed |
| | | 198 | | |
| | 783 | 199 | | if ((numElements & 1) != 0) |
| | | 200 | | { |
| | 783 | 201 | | Unsafe.Add(ref refData, (nint)i) = value; |
| | | 202 | | } |
| | 783 | 203 | | } |
| | | 204 | | |
| | | 205 | | public static int IndexOf<T>(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) where T : I |
| | | 206 | | { |
| | 0 | 207 | | Debug.Assert(searchSpaceLength >= 0); |
| | 0 | 208 | | Debug.Assert(valueLength >= 0); |
| | | 209 | | |
| | 0 | 210 | | if (valueLength == 0) |
| | 0 | 211 | | return 0; // A zero-length sequence is always treated as "found" at the start of the search space. |
| | | 212 | | |
| | 0 | 213 | | T valueHead = value; |
| | 0 | 214 | | ref T valueTail = ref Unsafe.Add(ref value, 1); |
| | 0 | 215 | | int valueTailLength = valueLength - 1; |
| | | 216 | | |
| | 0 | 217 | | int index = 0; |
| | 0 | 218 | | while (true) |
| | | 219 | | { |
| | 0 | 220 | | Debug.Assert(0 <= index && index <= searchSpaceLength); // Ensures no deceptive underflows in the comput |
| | 0 | 221 | | int remainingSearchSpaceLength = searchSpaceLength - index - valueTailLength; |
| | 0 | 222 | | if (remainingSearchSpaceLength <= 0) |
| | | 223 | | { |
| | | 224 | | break; // The unsearched portion is now shorter than the sequence we're looking for. So it can't be |
| | | 225 | | } |
| | | 226 | | |
| | | 227 | | // Do a quick search for the first element of "value". |
| | 0 | 228 | | int relativeIndex = IndexOf(ref Unsafe.Add(ref searchSpace, index), valueHead, remainingSearchSpaceLengt |
| | 0 | 229 | | if (relativeIndex < 0) |
| | | 230 | | { |
| | | 231 | | break; |
| | | 232 | | } |
| | 0 | 233 | | index += relativeIndex; |
| | | 234 | | |
| | | 235 | | // Found the first element of "value". See if the tail matches. |
| | 0 | 236 | | if (SequenceEqual(ref Unsafe.Add(ref searchSpace, index + 1), ref valueTail, valueTailLength)) |
| | | 237 | | { |
| | 0 | 238 | | return index; // The tail matched. Return a successful find. |
| | | 239 | | } |
| | | 240 | | |
| | 0 | 241 | | index++; |
| | | 242 | | } |
| | 0 | 243 | | return -1; |
| | | 244 | | } |
| | | 245 | | |
| | | 246 | | // Adapted from IndexOf(...) |
| | | 247 | | public static bool Contains<T>(ref T searchSpace, T value, int length) where T : IEquatable<T>? |
| | | 248 | | { |
| | 0 | 249 | | Debug.Assert(length >= 0); |
| | | 250 | | |
| | 0 | 251 | | nint index = 0; // Use nint for arithmetic to avoid unnecessary 64->32->64 truncations |
| | | 252 | | |
| | 0 | 253 | | if (default(T) != null || (object?)value != null) |
| | | 254 | | { |
| | 0 | 255 | | Debug.Assert(value is not null); |
| | | 256 | | |
| | 0 | 257 | | while (length >= 8) |
| | | 258 | | { |
| | 0 | 259 | | length -= 8; |
| | | 260 | | |
| | 0 | 261 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 0)) || |
| | 0 | 262 | | value.Equals(Unsafe.Add(ref searchSpace, index + 1)) || |
| | 0 | 263 | | value.Equals(Unsafe.Add(ref searchSpace, index + 2)) || |
| | 0 | 264 | | value.Equals(Unsafe.Add(ref searchSpace, index + 3)) || |
| | 0 | 265 | | value.Equals(Unsafe.Add(ref searchSpace, index + 4)) || |
| | 0 | 266 | | value.Equals(Unsafe.Add(ref searchSpace, index + 5)) || |
| | 0 | 267 | | value.Equals(Unsafe.Add(ref searchSpace, index + 6)) || |
| | 0 | 268 | | value.Equals(Unsafe.Add(ref searchSpace, index + 7))) |
| | | 269 | | { |
| | 0 | 270 | | return true; |
| | | 271 | | } |
| | | 272 | | |
| | 0 | 273 | | index += 8; |
| | | 274 | | } |
| | | 275 | | |
| | 0 | 276 | | if (length >= 4) |
| | | 277 | | { |
| | 0 | 278 | | length -= 4; |
| | | 279 | | |
| | 0 | 280 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 0)) || |
| | 0 | 281 | | value.Equals(Unsafe.Add(ref searchSpace, index + 1)) || |
| | 0 | 282 | | value.Equals(Unsafe.Add(ref searchSpace, index + 2)) || |
| | 0 | 283 | | value.Equals(Unsafe.Add(ref searchSpace, index + 3))) |
| | | 284 | | { |
| | 0 | 285 | | return true; |
| | | 286 | | } |
| | | 287 | | |
| | 0 | 288 | | index += 4; |
| | | 289 | | } |
| | | 290 | | |
| | 0 | 291 | | while (length > 0) |
| | | 292 | | { |
| | 0 | 293 | | length--; |
| | | 294 | | |
| | 0 | 295 | | if (value.Equals(Unsafe.Add(ref searchSpace, index))) |
| | | 296 | | { |
| | 0 | 297 | | return true; |
| | | 298 | | } |
| | | 299 | | |
| | 0 | 300 | | index += 1; |
| | | 301 | | } |
| | | 302 | | } |
| | | 303 | | else |
| | | 304 | | { |
| | 0 | 305 | | nint len = length; |
| | 0 | 306 | | for (index = 0; index < len; index++) |
| | | 307 | | { |
| | 0 | 308 | | if ((object?)Unsafe.Add(ref searchSpace, index) is null) |
| | | 309 | | { |
| | 0 | 310 | | return true; |
| | | 311 | | } |
| | | 312 | | } |
| | | 313 | | } |
| | | 314 | | |
| | 0 | 315 | | return false; |
| | | 316 | | } |
| | | 317 | | |
| | | 318 | | public static int IndexOf<T>(ref T searchSpace, T value, int length) where T : IEquatable<T>? |
| | | 319 | | { |
| | 0 | 320 | | Debug.Assert(length >= 0); |
| | | 321 | | |
| | 0 | 322 | | nint index = 0; // Use nint for arithmetic to avoid unnecessary 64->32->64 truncations |
| | 0 | 323 | | if (default(T) != null || (object?)value != null) |
| | | 324 | | { |
| | 0 | 325 | | Debug.Assert(value is not null); |
| | | 326 | | |
| | 0 | 327 | | while (length >= 8) |
| | | 328 | | { |
| | 0 | 329 | | length -= 8; |
| | | 330 | | |
| | 0 | 331 | | if (value.Equals(Unsafe.Add(ref searchSpace, index))) |
| | | 332 | | { |
| | 0 | 333 | | return (int)index; |
| | | 334 | | } |
| | 0 | 335 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 1))) |
| | | 336 | | { |
| | 0 | 337 | | return (int)(index + 1); |
| | | 338 | | } |
| | 0 | 339 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 2))) |
| | | 340 | | { |
| | 0 | 341 | | return (int)(index + 2); |
| | | 342 | | } |
| | 0 | 343 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 3))) |
| | | 344 | | { |
| | 0 | 345 | | return (int)(index + 3); |
| | | 346 | | } |
| | 0 | 347 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 4))) |
| | | 348 | | { |
| | 0 | 349 | | return (int)(index + 4); |
| | | 350 | | } |
| | 0 | 351 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 5))) |
| | | 352 | | { |
| | 0 | 353 | | return (int)(index + 5); |
| | | 354 | | } |
| | 0 | 355 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 6))) |
| | | 356 | | { |
| | 0 | 357 | | return (int)(index + 6); |
| | | 358 | | } |
| | 0 | 359 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 7))) |
| | | 360 | | { |
| | 0 | 361 | | return (int)(index + 7); |
| | | 362 | | } |
| | | 363 | | |
| | 0 | 364 | | index += 8; |
| | | 365 | | } |
| | | 366 | | |
| | 0 | 367 | | if (length >= 4) |
| | | 368 | | { |
| | 0 | 369 | | length -= 4; |
| | | 370 | | |
| | 0 | 371 | | if (value.Equals(Unsafe.Add(ref searchSpace, index))) |
| | | 372 | | { |
| | 0 | 373 | | return (int)index; |
| | | 374 | | } |
| | 0 | 375 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 1))) |
| | | 376 | | { |
| | 0 | 377 | | return (int)(index + 1); |
| | | 378 | | } |
| | 0 | 379 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 2))) |
| | | 380 | | { |
| | 0 | 381 | | return (int)(index + 2); |
| | | 382 | | } |
| | 0 | 383 | | if (value.Equals(Unsafe.Add(ref searchSpace, index + 3))) |
| | | 384 | | { |
| | 0 | 385 | | return (int)(index + 3); |
| | | 386 | | } |
| | | 387 | | |
| | 0 | 388 | | index += 4; |
| | | 389 | | } |
| | | 390 | | |
| | 0 | 391 | | while (length > 0) |
| | | 392 | | { |
| | 0 | 393 | | if (value.Equals(Unsafe.Add(ref searchSpace, index))) |
| | | 394 | | { |
| | 0 | 395 | | return (int)index; |
| | | 396 | | } |
| | | 397 | | |
| | 0 | 398 | | index += 1; |
| | 0 | 399 | | length--; |
| | | 400 | | } |
| | | 401 | | } |
| | | 402 | | else |
| | | 403 | | { |
| | 0 | 404 | | nint len = (nint)length; |
| | 0 | 405 | | for (index = 0; index < len; index++) |
| | | 406 | | { |
| | 0 | 407 | | if ((object?)Unsafe.Add(ref searchSpace, index) is null) |
| | | 408 | | { |
| | 0 | 409 | | return (int)index; |
| | | 410 | | } |
| | | 411 | | } |
| | | 412 | | } |
| | | 413 | | |
| | 0 | 414 | | return -1; |
| | | 415 | | } |
| | | 416 | | |
| | | 417 | | public static int IndexOfAny<T>(ref T searchSpace, T value0, T value1, int length) where T : IEquatable<T>? |
| | | 418 | | { |
| | 0 | 419 | | Debug.Assert(length >= 0); |
| | | 420 | | |
| | | 421 | | T lookUp; |
| | 0 | 422 | | int index = 0; |
| | 0 | 423 | | if (default(T) != null || ((object?)value0 != null && (object?)value1 != null)) |
| | | 424 | | { |
| | 0 | 425 | | Debug.Assert(value0 is not null && value1 is not null); |
| | | 426 | | |
| | 0 | 427 | | while ((length - index) >= 8) |
| | | 428 | | { |
| | 0 | 429 | | lookUp = Unsafe.Add(ref searchSpace, index); |
| | 0 | 430 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 431 | | { |
| | 0 | 432 | | return index; |
| | | 433 | | } |
| | | 434 | | |
| | 0 | 435 | | lookUp = Unsafe.Add(ref searchSpace, index + 1); |
| | 0 | 436 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 437 | | { |
| | 0 | 438 | | return index + 1; |
| | | 439 | | } |
| | | 440 | | |
| | 0 | 441 | | lookUp = Unsafe.Add(ref searchSpace, index + 2); |
| | 0 | 442 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 443 | | { |
| | 0 | 444 | | return index + 2; |
| | | 445 | | } |
| | | 446 | | |
| | 0 | 447 | | lookUp = Unsafe.Add(ref searchSpace, index + 3); |
| | 0 | 448 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 449 | | { |
| | 0 | 450 | | return index + 3; |
| | | 451 | | } |
| | | 452 | | |
| | 0 | 453 | | lookUp = Unsafe.Add(ref searchSpace, index + 4); |
| | 0 | 454 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 455 | | { |
| | 0 | 456 | | return index + 4; |
| | | 457 | | } |
| | | 458 | | |
| | 0 | 459 | | lookUp = Unsafe.Add(ref searchSpace, index + 5); |
| | 0 | 460 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 461 | | { |
| | 0 | 462 | | return index + 5; |
| | | 463 | | } |
| | | 464 | | |
| | 0 | 465 | | lookUp = Unsafe.Add(ref searchSpace, index + 6); |
| | 0 | 466 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 467 | | { |
| | 0 | 468 | | return index + 6; |
| | | 469 | | } |
| | | 470 | | |
| | 0 | 471 | | lookUp = Unsafe.Add(ref searchSpace, index + 7); |
| | 0 | 472 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 473 | | { |
| | 0 | 474 | | return index + 7; |
| | | 475 | | } |
| | | 476 | | |
| | 0 | 477 | | index += 8; |
| | | 478 | | } |
| | | 479 | | |
| | 0 | 480 | | if ((length - index) >= 4) |
| | | 481 | | { |
| | 0 | 482 | | lookUp = Unsafe.Add(ref searchSpace, index); |
| | 0 | 483 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 484 | | { |
| | 0 | 485 | | return index; |
| | | 486 | | } |
| | | 487 | | |
| | 0 | 488 | | lookUp = Unsafe.Add(ref searchSpace, index + 1); |
| | 0 | 489 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 490 | | { |
| | 0 | 491 | | return index + 1; |
| | | 492 | | } |
| | | 493 | | |
| | 0 | 494 | | lookUp = Unsafe.Add(ref searchSpace, index + 2); |
| | 0 | 495 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 496 | | { |
| | 0 | 497 | | return index + 2; |
| | | 498 | | } |
| | | 499 | | |
| | 0 | 500 | | lookUp = Unsafe.Add(ref searchSpace, index + 3); |
| | 0 | 501 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 502 | | { |
| | 0 | 503 | | return index + 3; |
| | | 504 | | } |
| | | 505 | | |
| | 0 | 506 | | index += 4; |
| | | 507 | | } |
| | | 508 | | |
| | 0 | 509 | | while (index < length) |
| | | 510 | | { |
| | 0 | 511 | | lookUp = Unsafe.Add(ref searchSpace, index); |
| | 0 | 512 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 513 | | { |
| | 0 | 514 | | return index; |
| | | 515 | | } |
| | | 516 | | |
| | 0 | 517 | | index++; |
| | | 518 | | } |
| | | 519 | | } |
| | | 520 | | else |
| | | 521 | | { |
| | 0 | 522 | | for (index = 0; index < length; index++) |
| | | 523 | | { |
| | 0 | 524 | | lookUp = Unsafe.Add(ref searchSpace, index); |
| | 0 | 525 | | if ((object?)lookUp is null) |
| | | 526 | | { |
| | 0 | 527 | | if ((object?)value0 is null || (object?)value1 is null) |
| | | 528 | | { |
| | 0 | 529 | | return index; |
| | | 530 | | } |
| | | 531 | | } |
| | 0 | 532 | | else if (lookUp.Equals(value0) || lookUp.Equals(value1)) |
| | | 533 | | { |
| | 0 | 534 | | return index; |
| | | 535 | | } |
| | | 536 | | } |
| | | 537 | | } |
| | | 538 | | |
| | 0 | 539 | | return -1; |
| | | 540 | | } |
| | | 541 | | |
| | | 542 | | public static int IndexOfAny<T>(ref T searchSpace, T value0, T value1, T value2, int length) where T : IEquatabl |
| | | 543 | | { |
| | 0 | 544 | | Debug.Assert(length >= 0); |
| | | 545 | | |
| | | 546 | | T lookUp; |
| | 0 | 547 | | int index = 0; |
| | 0 | 548 | | if (default(T) != null || ((object?)value0 != null && (object?)value1 != null && (object?)value2 != null)) |
| | | 549 | | { |
| | 0 | 550 | | Debug.Assert(value0 is not null && value1 is not null && value2 is not null); |
| | | 551 | | |
| | 0 | 552 | | while ((length - index) >= 8) |
| | | 553 | | { |
| | 0 | 554 | | lookUp = Unsafe.Add(ref searchSpace, index); |
| | 0 | 555 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 556 | | { |
| | 0 | 557 | | return index; |
| | | 558 | | } |
| | | 559 | | |
| | 0 | 560 | | lookUp = Unsafe.Add(ref searchSpace, index + 1); |
| | 0 | 561 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 562 | | { |
| | 0 | 563 | | return index + 1; |
| | | 564 | | } |
| | | 565 | | |
| | 0 | 566 | | lookUp = Unsafe.Add(ref searchSpace, index + 2); |
| | 0 | 567 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 568 | | { |
| | 0 | 569 | | return index + 2; |
| | | 570 | | } |
| | | 571 | | |
| | 0 | 572 | | lookUp = Unsafe.Add(ref searchSpace, index + 3); |
| | 0 | 573 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 574 | | { |
| | 0 | 575 | | return index + 3; |
| | | 576 | | } |
| | | 577 | | |
| | 0 | 578 | | lookUp = Unsafe.Add(ref searchSpace, index + 4); |
| | 0 | 579 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 580 | | { |
| | 0 | 581 | | return index + 4; |
| | | 582 | | } |
| | | 583 | | |
| | 0 | 584 | | lookUp = Unsafe.Add(ref searchSpace, index + 5); |
| | 0 | 585 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 586 | | { |
| | 0 | 587 | | return index + 5; |
| | | 588 | | } |
| | | 589 | | |
| | 0 | 590 | | lookUp = Unsafe.Add(ref searchSpace, index + 6); |
| | 0 | 591 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 592 | | { |
| | 0 | 593 | | return index + 6; |
| | | 594 | | } |
| | | 595 | | |
| | 0 | 596 | | lookUp = Unsafe.Add(ref searchSpace, index + 7); |
| | 0 | 597 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 598 | | { |
| | 0 | 599 | | return index + 7; |
| | | 600 | | } |
| | | 601 | | |
| | 0 | 602 | | index += 8; |
| | | 603 | | } |
| | | 604 | | |
| | 0 | 605 | | if ((length - index) >= 4) |
| | | 606 | | { |
| | 0 | 607 | | lookUp = Unsafe.Add(ref searchSpace, index); |
| | 0 | 608 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 609 | | { |
| | 0 | 610 | | return index; |
| | | 611 | | } |
| | | 612 | | |
| | 0 | 613 | | lookUp = Unsafe.Add(ref searchSpace, index + 1); |
| | 0 | 614 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 615 | | { |
| | 0 | 616 | | return index + 1; |
| | | 617 | | } |
| | | 618 | | |
| | 0 | 619 | | lookUp = Unsafe.Add(ref searchSpace, index + 2); |
| | 0 | 620 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 621 | | { |
| | 0 | 622 | | return index + 2; |
| | | 623 | | } |
| | | 624 | | |
| | 0 | 625 | | lookUp = Unsafe.Add(ref searchSpace, index + 3); |
| | 0 | 626 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 627 | | { |
| | 0 | 628 | | return index + 3; |
| | | 629 | | } |
| | | 630 | | |
| | 0 | 631 | | index += 4; |
| | | 632 | | } |
| | | 633 | | |
| | 0 | 634 | | while (index < length) |
| | | 635 | | { |
| | 0 | 636 | | lookUp = Unsafe.Add(ref searchSpace, index); |
| | 0 | 637 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 638 | | { |
| | 0 | 639 | | return index; |
| | | 640 | | } |
| | | 641 | | |
| | 0 | 642 | | index++; |
| | | 643 | | } |
| | | 644 | | } |
| | | 645 | | else |
| | | 646 | | { |
| | 0 | 647 | | for (index = 0; index < length; index++) |
| | | 648 | | { |
| | 0 | 649 | | lookUp = Unsafe.Add(ref searchSpace, index); |
| | 0 | 650 | | if ((object?)lookUp is null) |
| | | 651 | | { |
| | 0 | 652 | | if ((object?)value0 is null || (object?)value1 is null || (object?)value2 is null) |
| | | 653 | | { |
| | 0 | 654 | | return index; |
| | | 655 | | } |
| | | 656 | | } |
| | 0 | 657 | | else if (lookUp.Equals(value0) || lookUp.Equals(value1) || lookUp.Equals(value2)) |
| | | 658 | | { |
| | 0 | 659 | | return index; |
| | | 660 | | } |
| | | 661 | | } |
| | | 662 | | } |
| | | 663 | | |
| | 0 | 664 | | return -1; |
| | | 665 | | } |
| | | 666 | | |
| | | 667 | | public static int IndexOfAny<T>(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) where T |
| | | 668 | | { |
| | 0 | 669 | | Debug.Assert(searchSpaceLength >= 0); |
| | 0 | 670 | | Debug.Assert(valueLength >= 0); |
| | | 671 | | |
| | 0 | 672 | | if (valueLength == 0) |
| | 0 | 673 | | return -1; // A zero-length set of values is always treated as "not found". |
| | | 674 | | |
| | | 675 | | // For the following paragraph, let: |
| | | 676 | | // n := length of haystack |
| | | 677 | | // i := index of first occurrence of any needle within haystack |
| | | 678 | | // l := length of needle array |
| | | 679 | | // |
| | | 680 | | // We use a naive non-vectorized search because we want to bound the complexity of IndexOfAny |
| | | 681 | | // to O(i * l) rather than O(n * l), or just O(n * l) if no needle is found. The reason for |
| | | 682 | | // this is that it's common for callers to invoke IndexOfAny immediately before slicing, |
| | | 683 | | // and when this is called in a loop, we want the entire loop to be bounded by O(n * l) |
| | | 684 | | // rather than O(n^2 * l). |
| | | 685 | | |
| | 0 | 686 | | if (typeof(T).IsValueType) |
| | | 687 | | { |
| | | 688 | | // Calling ValueType.Equals (devirtualized), which takes 'this' byref. We'll make |
| | | 689 | | // a byval copy of the candidate from the search space in the outer loop, then in |
| | | 690 | | // the inner loop we'll pass a ref (as 'this') to each element in the needle. |
| | 0 | 691 | | for (int i = 0; i < searchSpaceLength; i++) |
| | | 692 | | { |
| | 0 | 693 | | T candidate = Unsafe.Add(ref searchSpace, i); |
| | 0 | 694 | | for (int j = 0; j < valueLength; j++) |
| | | 695 | | { |
| | 0 | 696 | | if (Unsafe.Add(ref value, j)!.Equals(candidate)) |
| | | 697 | | { |
| | 0 | 698 | | return i; |
| | | 699 | | } |
| | | 700 | | } |
| | | 701 | | } |
| | | 702 | | } |
| | | 703 | | else |
| | | 704 | | { |
| | | 705 | | // Calling IEquatable<T>.Equals (virtual dispatch). We'll perform the null check |
| | | 706 | | // in the outer loop instead of in the inner loop to save some branching. |
| | 0 | 707 | | for (int i = 0; i < searchSpaceLength; i++) |
| | | 708 | | { |
| | 0 | 709 | | T candidate = Unsafe.Add(ref searchSpace, i); |
| | 0 | 710 | | if (candidate is not null) |
| | | 711 | | { |
| | 0 | 712 | | for (int j = 0; j < valueLength; j++) |
| | | 713 | | { |
| | 0 | 714 | | if (candidate.Equals(Unsafe.Add(ref value, j))) |
| | | 715 | | { |
| | 0 | 716 | | return i; |
| | | 717 | | } |
| | | 718 | | } |
| | | 719 | | } |
| | | 720 | | else |
| | | 721 | | { |
| | 0 | 722 | | for (int j = 0; j < valueLength; j++) |
| | | 723 | | { |
| | 0 | 724 | | if (Unsafe.Add(ref value, j) is null) |
| | | 725 | | { |
| | 0 | 726 | | return i; |
| | | 727 | | } |
| | | 728 | | } |
| | | 729 | | } |
| | | 730 | | } |
| | | 731 | | } |
| | | 732 | | |
| | 0 | 733 | | return -1; // not found |
| | | 734 | | } |
| | | 735 | | |
| | | 736 | | public static int LastIndexOf<T>(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) where T |
| | | 737 | | { |
| | 0 | 738 | | Debug.Assert(searchSpaceLength >= 0); |
| | 0 | 739 | | Debug.Assert(valueLength >= 0); |
| | | 740 | | |
| | 0 | 741 | | if (valueLength == 0) |
| | 0 | 742 | | return searchSpaceLength; // A zero-length sequence is always treated as "found" at the end of the sear |
| | | 743 | | |
| | 0 | 744 | | int valueTailLength = valueLength - 1; |
| | 0 | 745 | | if (valueTailLength == 0) |
| | | 746 | | { |
| | 0 | 747 | | return LastIndexOf(ref searchSpace, value, searchSpaceLength); |
| | | 748 | | } |
| | | 749 | | |
| | 0 | 750 | | int index = 0; |
| | | 751 | | |
| | 0 | 752 | | T valueHead = value; |
| | 0 | 753 | | ref T valueTail = ref Unsafe.Add(ref value, 1); |
| | | 754 | | |
| | 0 | 755 | | while (true) |
| | | 756 | | { |
| | 0 | 757 | | Debug.Assert(0 <= index && index <= searchSpaceLength); // Ensures no deceptive underflows in the comput |
| | 0 | 758 | | int remainingSearchSpaceLength = searchSpaceLength - index - valueTailLength; |
| | 0 | 759 | | if (remainingSearchSpaceLength <= 0) |
| | | 760 | | { |
| | | 761 | | break; // The unsearched portion is now shorter than the sequence we're looking for. So it can't be |
| | | 762 | | } |
| | | 763 | | |
| | | 764 | | // Do a quick search for the first element of "value". |
| | 0 | 765 | | int relativeIndex = LastIndexOf(ref searchSpace, valueHead, remainingSearchSpaceLength); |
| | 0 | 766 | | if (relativeIndex < 0) |
| | | 767 | | { |
| | | 768 | | break; |
| | | 769 | | } |
| | | 770 | | |
| | | 771 | | // Found the first element of "value". See if the tail matches. |
| | 0 | 772 | | if (SequenceEqual(ref Unsafe.Add(ref searchSpace, relativeIndex + 1), ref valueTail, valueTailLength)) |
| | | 773 | | { |
| | 0 | 774 | | return relativeIndex; // The tail matched. Return a successful find. |
| | | 775 | | } |
| | | 776 | | |
| | 0 | 777 | | index += remainingSearchSpaceLength - relativeIndex; |
| | | 778 | | } |
| | 0 | 779 | | return -1; |
| | | 780 | | } |
| | | 781 | | |
| | | 782 | | public static int LastIndexOf<T>(ref T searchSpace, T value, int length) where T : IEquatable<T>? |
| | | 783 | | { |
| | 0 | 784 | | Debug.Assert(length >= 0); |
| | | 785 | | |
| | 0 | 786 | | if (default(T) != null || (object?)value != null) |
| | | 787 | | { |
| | 0 | 788 | | Debug.Assert(value is not null); |
| | | 789 | | |
| | 0 | 790 | | while (length >= 8) |
| | | 791 | | { |
| | 0 | 792 | | length -= 8; |
| | | 793 | | |
| | 0 | 794 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 7))) |
| | | 795 | | { |
| | 0 | 796 | | return length + 7; |
| | | 797 | | } |
| | 0 | 798 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 6))) |
| | | 799 | | { |
| | 0 | 800 | | return length + 6; |
| | | 801 | | } |
| | 0 | 802 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 5))) |
| | | 803 | | { |
| | 0 | 804 | | return length + 5; |
| | | 805 | | } |
| | 0 | 806 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 4))) |
| | | 807 | | { |
| | 0 | 808 | | return length + 4; |
| | | 809 | | } |
| | 0 | 810 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 3))) |
| | | 811 | | { |
| | 0 | 812 | | return length + 3; |
| | | 813 | | } |
| | 0 | 814 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 2))) |
| | | 815 | | { |
| | 0 | 816 | | return length + 2; |
| | | 817 | | } |
| | 0 | 818 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 1))) |
| | | 819 | | { |
| | 0 | 820 | | return length + 1; |
| | | 821 | | } |
| | 0 | 822 | | if (value.Equals(Unsafe.Add(ref searchSpace, length))) |
| | | 823 | | { |
| | 0 | 824 | | return length; |
| | | 825 | | } |
| | | 826 | | } |
| | | 827 | | |
| | 0 | 828 | | if (length >= 4) |
| | | 829 | | { |
| | 0 | 830 | | length -= 4; |
| | | 831 | | |
| | 0 | 832 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 3))) |
| | | 833 | | { |
| | 0 | 834 | | return length + 3; |
| | | 835 | | } |
| | 0 | 836 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 2))) |
| | | 837 | | { |
| | 0 | 838 | | return length + 2; |
| | | 839 | | } |
| | 0 | 840 | | if (value.Equals(Unsafe.Add(ref searchSpace, length + 1))) |
| | | 841 | | { |
| | 0 | 842 | | return length + 1; |
| | | 843 | | } |
| | 0 | 844 | | if (value.Equals(Unsafe.Add(ref searchSpace, length))) |
| | | 845 | | { |
| | 0 | 846 | | return length; |
| | | 847 | | } |
| | | 848 | | } |
| | | 849 | | |
| | 0 | 850 | | while (length > 0) |
| | | 851 | | { |
| | 0 | 852 | | length--; |
| | | 853 | | |
| | 0 | 854 | | if (value.Equals(Unsafe.Add(ref searchSpace, length))) |
| | | 855 | | { |
| | 0 | 856 | | return length; |
| | | 857 | | } |
| | | 858 | | } |
| | | 859 | | } |
| | | 860 | | else |
| | | 861 | | { |
| | 0 | 862 | | for (length--; length >= 0; length--) |
| | | 863 | | { |
| | 0 | 864 | | if ((object?)Unsafe.Add(ref searchSpace, length) is null) |
| | | 865 | | { |
| | 0 | 866 | | return length; |
| | | 867 | | } |
| | | 868 | | } |
| | | 869 | | } |
| | | 870 | | |
| | 0 | 871 | | return -1; |
| | | 872 | | } |
| | | 873 | | |
| | | 874 | | public static int LastIndexOfAny<T>(ref T searchSpace, T value0, T value1, int length) where T : IEquatable<T>? |
| | | 875 | | { |
| | 0 | 876 | | Debug.Assert(length >= 0); |
| | | 877 | | |
| | | 878 | | T lookUp; |
| | 0 | 879 | | if (default(T) != null || ((object?)value0 != null && (object?)value1 != null)) |
| | | 880 | | { |
| | 0 | 881 | | Debug.Assert(value0 is not null && value1 is not null); |
| | | 882 | | |
| | 0 | 883 | | while (length >= 8) |
| | | 884 | | { |
| | 0 | 885 | | length -= 8; |
| | | 886 | | |
| | 0 | 887 | | lookUp = Unsafe.Add(ref searchSpace, length + 7); |
| | 0 | 888 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 889 | | { |
| | 0 | 890 | | return length + 7; |
| | | 891 | | } |
| | | 892 | | |
| | 0 | 893 | | lookUp = Unsafe.Add(ref searchSpace, length + 6); |
| | 0 | 894 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 895 | | { |
| | 0 | 896 | | return length + 6; |
| | | 897 | | } |
| | | 898 | | |
| | 0 | 899 | | lookUp = Unsafe.Add(ref searchSpace, length + 5); |
| | 0 | 900 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 901 | | { |
| | 0 | 902 | | return length + 5; |
| | | 903 | | } |
| | | 904 | | |
| | 0 | 905 | | lookUp = Unsafe.Add(ref searchSpace, length + 4); |
| | 0 | 906 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 907 | | { |
| | 0 | 908 | | return length + 4; |
| | | 909 | | } |
| | | 910 | | |
| | 0 | 911 | | lookUp = Unsafe.Add(ref searchSpace, length + 3); |
| | 0 | 912 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 913 | | { |
| | 0 | 914 | | return length + 3; |
| | | 915 | | } |
| | | 916 | | |
| | 0 | 917 | | lookUp = Unsafe.Add(ref searchSpace, length + 2); |
| | 0 | 918 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 919 | | { |
| | 0 | 920 | | return length + 2; |
| | | 921 | | } |
| | | 922 | | |
| | 0 | 923 | | lookUp = Unsafe.Add(ref searchSpace, length + 1); |
| | 0 | 924 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 925 | | { |
| | 0 | 926 | | return length + 1; |
| | | 927 | | } |
| | | 928 | | |
| | 0 | 929 | | lookUp = Unsafe.Add(ref searchSpace, length); |
| | 0 | 930 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 931 | | { |
| | 0 | 932 | | return length; |
| | | 933 | | } |
| | | 934 | | } |
| | | 935 | | |
| | 0 | 936 | | if (length >= 4) |
| | | 937 | | { |
| | 0 | 938 | | length -= 4; |
| | | 939 | | |
| | 0 | 940 | | lookUp = Unsafe.Add(ref searchSpace, length + 3); |
| | 0 | 941 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 942 | | { |
| | 0 | 943 | | return length + 3; |
| | | 944 | | } |
| | | 945 | | |
| | 0 | 946 | | lookUp = Unsafe.Add(ref searchSpace, length + 2); |
| | 0 | 947 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 948 | | { |
| | 0 | 949 | | return length + 2; |
| | | 950 | | } |
| | | 951 | | |
| | 0 | 952 | | lookUp = Unsafe.Add(ref searchSpace, length + 1); |
| | 0 | 953 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 954 | | { |
| | 0 | 955 | | return length + 1; |
| | | 956 | | } |
| | | 957 | | |
| | 0 | 958 | | lookUp = Unsafe.Add(ref searchSpace, length); |
| | 0 | 959 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 960 | | { |
| | 0 | 961 | | return length; |
| | | 962 | | } |
| | | 963 | | } |
| | | 964 | | |
| | 0 | 965 | | while (length > 0) |
| | | 966 | | { |
| | 0 | 967 | | length--; |
| | | 968 | | |
| | 0 | 969 | | lookUp = Unsafe.Add(ref searchSpace, length); |
| | 0 | 970 | | if (value0.Equals(lookUp) || value1.Equals(lookUp)) |
| | | 971 | | { |
| | 0 | 972 | | return length; |
| | | 973 | | } |
| | | 974 | | } |
| | | 975 | | } |
| | | 976 | | else |
| | | 977 | | { |
| | 0 | 978 | | for (length--; length >= 0; length--) |
| | | 979 | | { |
| | 0 | 980 | | lookUp = Unsafe.Add(ref searchSpace, length); |
| | 0 | 981 | | if ((object?)lookUp is null) |
| | | 982 | | { |
| | 0 | 983 | | if ((object?)value0 is null || (object?)value1 is null) |
| | | 984 | | { |
| | 0 | 985 | | return length; |
| | | 986 | | } |
| | | 987 | | } |
| | 0 | 988 | | else if (lookUp.Equals(value0) || lookUp.Equals(value1)) |
| | | 989 | | { |
| | 0 | 990 | | return length; |
| | | 991 | | } |
| | | 992 | | } |
| | | 993 | | } |
| | | 994 | | |
| | 0 | 995 | | return -1; |
| | | 996 | | } |
| | | 997 | | |
| | | 998 | | public static int LastIndexOfAny<T>(ref T searchSpace, T value0, T value1, T value2, int length) where T : IEqua |
| | | 999 | | { |
| | 0 | 1000 | | Debug.Assert(length >= 0); |
| | | 1001 | | |
| | | 1002 | | T lookUp; |
| | 0 | 1003 | | if (default(T) != null || ((object?)value0 != null && (object?)value1 != null && (object?)value2 != null)) |
| | | 1004 | | { |
| | 0 | 1005 | | Debug.Assert(value0 is not null && value1 is not null && value2 is not null); |
| | | 1006 | | |
| | 0 | 1007 | | while (length >= 8) |
| | | 1008 | | { |
| | 0 | 1009 | | length -= 8; |
| | | 1010 | | |
| | 0 | 1011 | | lookUp = Unsafe.Add(ref searchSpace, length + 7); |
| | 0 | 1012 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1013 | | { |
| | 0 | 1014 | | return length + 7; |
| | | 1015 | | } |
| | | 1016 | | |
| | 0 | 1017 | | lookUp = Unsafe.Add(ref searchSpace, length + 6); |
| | 0 | 1018 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1019 | | { |
| | 0 | 1020 | | return length + 6; |
| | | 1021 | | } |
| | | 1022 | | |
| | 0 | 1023 | | lookUp = Unsafe.Add(ref searchSpace, length + 5); |
| | 0 | 1024 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1025 | | { |
| | 0 | 1026 | | return length + 5; |
| | | 1027 | | } |
| | | 1028 | | |
| | 0 | 1029 | | lookUp = Unsafe.Add(ref searchSpace, length + 4); |
| | 0 | 1030 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1031 | | { |
| | 0 | 1032 | | return length + 4; |
| | | 1033 | | } |
| | | 1034 | | |
| | 0 | 1035 | | lookUp = Unsafe.Add(ref searchSpace, length + 3); |
| | 0 | 1036 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1037 | | { |
| | 0 | 1038 | | return length + 3; |
| | | 1039 | | } |
| | | 1040 | | |
| | 0 | 1041 | | lookUp = Unsafe.Add(ref searchSpace, length + 2); |
| | 0 | 1042 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1043 | | { |
| | 0 | 1044 | | return length + 2; |
| | | 1045 | | } |
| | | 1046 | | |
| | 0 | 1047 | | lookUp = Unsafe.Add(ref searchSpace, length + 1); |
| | 0 | 1048 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1049 | | { |
| | 0 | 1050 | | return length + 1; |
| | | 1051 | | } |
| | | 1052 | | |
| | 0 | 1053 | | lookUp = Unsafe.Add(ref searchSpace, length); |
| | 0 | 1054 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1055 | | { |
| | 0 | 1056 | | return length; |
| | | 1057 | | } |
| | | 1058 | | } |
| | | 1059 | | |
| | 0 | 1060 | | if (length >= 4) |
| | | 1061 | | { |
| | 0 | 1062 | | length -= 4; |
| | | 1063 | | |
| | 0 | 1064 | | lookUp = Unsafe.Add(ref searchSpace, length + 3); |
| | 0 | 1065 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1066 | | { |
| | 0 | 1067 | | return length + 3; |
| | | 1068 | | } |
| | | 1069 | | |
| | 0 | 1070 | | lookUp = Unsafe.Add(ref searchSpace, length + 2); |
| | 0 | 1071 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1072 | | { |
| | 0 | 1073 | | return length + 2; |
| | | 1074 | | } |
| | | 1075 | | |
| | 0 | 1076 | | lookUp = Unsafe.Add(ref searchSpace, length + 1); |
| | 0 | 1077 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1078 | | { |
| | 0 | 1079 | | return length + 1; |
| | | 1080 | | } |
| | | 1081 | | |
| | 0 | 1082 | | lookUp = Unsafe.Add(ref searchSpace, length); |
| | 0 | 1083 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1084 | | { |
| | 0 | 1085 | | return length; |
| | | 1086 | | } |
| | | 1087 | | } |
| | | 1088 | | |
| | 0 | 1089 | | while (length > 0) |
| | | 1090 | | { |
| | 0 | 1091 | | length--; |
| | | 1092 | | |
| | 0 | 1093 | | lookUp = Unsafe.Add(ref searchSpace, length); |
| | 0 | 1094 | | if (value0.Equals(lookUp) || value1.Equals(lookUp) || value2.Equals(lookUp)) |
| | | 1095 | | { |
| | 0 | 1096 | | return length; |
| | | 1097 | | } |
| | | 1098 | | } |
| | | 1099 | | } |
| | | 1100 | | else |
| | | 1101 | | { |
| | 0 | 1102 | | for (length--; length >= 0; length--) |
| | | 1103 | | { |
| | 0 | 1104 | | lookUp = Unsafe.Add(ref searchSpace, length); |
| | 0 | 1105 | | if ((object?)lookUp is null) |
| | | 1106 | | { |
| | 0 | 1107 | | if ((object?)value0 is null || (object?)value1 is null || (object?)value2 is null) |
| | | 1108 | | { |
| | 0 | 1109 | | return length; |
| | | 1110 | | } |
| | | 1111 | | } |
| | 0 | 1112 | | else if (lookUp.Equals(value0) || lookUp.Equals(value1) || lookUp.Equals(value2)) |
| | | 1113 | | { |
| | 0 | 1114 | | return length; |
| | | 1115 | | } |
| | | 1116 | | } |
| | | 1117 | | } |
| | | 1118 | | |
| | 0 | 1119 | | return -1; |
| | | 1120 | | } |
| | | 1121 | | |
| | | 1122 | | public static int LastIndexOfAny<T>(ref T searchSpace, int searchSpaceLength, ref T value, int valueLength) wher |
| | | 1123 | | { |
| | 0 | 1124 | | Debug.Assert(searchSpaceLength >= 0); |
| | 0 | 1125 | | Debug.Assert(valueLength >= 0); |
| | | 1126 | | |
| | 0 | 1127 | | if (valueLength == 0) |
| | 0 | 1128 | | return -1; // A zero-length set of values is always treated as "not found". |
| | | 1129 | | |
| | | 1130 | | // See comments in IndexOfAny(ref T, int, ref T, int) above regarding algorithmic complexity concerns. |
| | | 1131 | | // This logic is similar, but it runs backward. |
| | 0 | 1132 | | if (typeof(T).IsValueType) |
| | | 1133 | | { |
| | 0 | 1134 | | for (int i = searchSpaceLength - 1; i >= 0; i--) |
| | | 1135 | | { |
| | 0 | 1136 | | T candidate = Unsafe.Add(ref searchSpace, i); |
| | 0 | 1137 | | for (int j = 0; j < valueLength; j++) |
| | | 1138 | | { |
| | 0 | 1139 | | if (Unsafe.Add(ref value, j)!.Equals(candidate)) |
| | | 1140 | | { |
| | 0 | 1141 | | return i; |
| | | 1142 | | } |
| | | 1143 | | } |
| | | 1144 | | } |
| | | 1145 | | } |
| | | 1146 | | else |
| | | 1147 | | { |
| | 0 | 1148 | | for (int i = searchSpaceLength - 1; i >= 0; i--) |
| | | 1149 | | { |
| | 0 | 1150 | | T candidate = Unsafe.Add(ref searchSpace, i); |
| | 0 | 1151 | | if (candidate is not null) |
| | | 1152 | | { |
| | 0 | 1153 | | for (int j = 0; j < valueLength; j++) |
| | | 1154 | | { |
| | 0 | 1155 | | if (candidate.Equals(Unsafe.Add(ref value, j))) |
| | | 1156 | | { |
| | 0 | 1157 | | return i; |
| | | 1158 | | } |
| | | 1159 | | } |
| | | 1160 | | } |
| | | 1161 | | else |
| | | 1162 | | { |
| | 0 | 1163 | | for (int j = 0; j < valueLength; j++) |
| | | 1164 | | { |
| | 0 | 1165 | | if (Unsafe.Add(ref value, j) is null) |
| | | 1166 | | { |
| | 0 | 1167 | | return i; |
| | | 1168 | | } |
| | | 1169 | | } |
| | | 1170 | | } |
| | | 1171 | | } |
| | | 1172 | | } |
| | | 1173 | | |
| | 0 | 1174 | | return -1; // not found |
| | | 1175 | | } |
| | | 1176 | | |
| | | 1177 | | internal static int IndexOfAnyExcept<T>(ref T searchSpace, T value0, int length) |
| | | 1178 | | { |
| | 0 | 1179 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | | 1180 | | |
| | 0 | 1181 | | for (int i = 0; i < length; i++) |
| | | 1182 | | { |
| | 0 | 1183 | | if (!EqualityComparer<T>.Default.Equals(Unsafe.Add(ref searchSpace, i), value0)) |
| | | 1184 | | { |
| | 0 | 1185 | | return i; |
| | | 1186 | | } |
| | | 1187 | | } |
| | | 1188 | | |
| | 0 | 1189 | | return -1; |
| | | 1190 | | } |
| | | 1191 | | |
| | | 1192 | | internal static int LastIndexOfAnyExcept<T>(ref T searchSpace, T value0, int length) |
| | | 1193 | | { |
| | 0 | 1194 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | | 1195 | | |
| | 0 | 1196 | | for (int i = length - 1; i >= 0; i--) |
| | | 1197 | | { |
| | 0 | 1198 | | if (!EqualityComparer<T>.Default.Equals(Unsafe.Add(ref searchSpace, i), value0)) |
| | | 1199 | | { |
| | 0 | 1200 | | return i; |
| | | 1201 | | } |
| | | 1202 | | } |
| | | 1203 | | |
| | 0 | 1204 | | return -1; |
| | | 1205 | | } |
| | | 1206 | | |
| | | 1207 | | internal static int IndexOfAnyExcept<T>(ref T searchSpace, T value0, T value1, int length) |
| | | 1208 | | { |
| | 0 | 1209 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | | 1210 | | |
| | 0 | 1211 | | for (int i = 0; i < length; i++) |
| | | 1212 | | { |
| | 0 | 1213 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 1214 | | if (!EqualityComparer<T>.Default.Equals(current, value0) && !EqualityComparer<T>.Default.Equals(current, |
| | | 1215 | | { |
| | 0 | 1216 | | return i; |
| | | 1217 | | } |
| | | 1218 | | } |
| | | 1219 | | |
| | 0 | 1220 | | return -1; |
| | | 1221 | | } |
| | | 1222 | | |
| | | 1223 | | internal static int LastIndexOfAnyExcept<T>(ref T searchSpace, T value0, T value1, int length) |
| | | 1224 | | { |
| | 0 | 1225 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | | 1226 | | |
| | 0 | 1227 | | for (int i = length - 1; i >= 0; i--) |
| | | 1228 | | { |
| | 0 | 1229 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 1230 | | if (!EqualityComparer<T>.Default.Equals(current, value0) && !EqualityComparer<T>.Default.Equals(current, |
| | | 1231 | | { |
| | 0 | 1232 | | return i; |
| | | 1233 | | } |
| | | 1234 | | } |
| | | 1235 | | |
| | 0 | 1236 | | return -1; |
| | | 1237 | | } |
| | | 1238 | | |
| | | 1239 | | internal static int IndexOfAnyExcept<T>(ref T searchSpace, T value0, T value1, T value2, int length) |
| | | 1240 | | { |
| | 0 | 1241 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | | 1242 | | |
| | 0 | 1243 | | for (int i = 0; i < length; i++) |
| | | 1244 | | { |
| | 0 | 1245 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 1246 | | if (!EqualityComparer<T>.Default.Equals(current, value0) |
| | 0 | 1247 | | && !EqualityComparer<T>.Default.Equals(current, value1) |
| | 0 | 1248 | | && !EqualityComparer<T>.Default.Equals(current, value2)) |
| | | 1249 | | { |
| | 0 | 1250 | | return i; |
| | | 1251 | | } |
| | | 1252 | | } |
| | | 1253 | | |
| | 0 | 1254 | | return -1; |
| | | 1255 | | } |
| | | 1256 | | |
| | | 1257 | | internal static int LastIndexOfAnyExcept<T>(ref T searchSpace, T value0, T value1, T value2, int length) |
| | | 1258 | | { |
| | 0 | 1259 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | | 1260 | | |
| | 0 | 1261 | | for (int i = length - 1; i >= 0; i--) |
| | | 1262 | | { |
| | 0 | 1263 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 1264 | | if (!EqualityComparer<T>.Default.Equals(current, value0) |
| | 0 | 1265 | | && !EqualityComparer<T>.Default.Equals(current, value1) |
| | 0 | 1266 | | && !EqualityComparer<T>.Default.Equals(current, value2)) |
| | | 1267 | | { |
| | 0 | 1268 | | return i; |
| | | 1269 | | } |
| | | 1270 | | } |
| | | 1271 | | |
| | 0 | 1272 | | return -1; |
| | | 1273 | | } |
| | | 1274 | | |
| | | 1275 | | internal static int IndexOfAnyExcept<T>(ref T searchSpace, T value0, T value1, T value2, T value3, int length) |
| | | 1276 | | { |
| | 0 | 1277 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | | 1278 | | |
| | 0 | 1279 | | for (int i = 0; i < length; i++) |
| | | 1280 | | { |
| | 0 | 1281 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 1282 | | if (!EqualityComparer<T>.Default.Equals(current, value0) |
| | 0 | 1283 | | && !EqualityComparer<T>.Default.Equals(current, value1) |
| | 0 | 1284 | | && !EqualityComparer<T>.Default.Equals(current, value2) |
| | 0 | 1285 | | && !EqualityComparer<T>.Default.Equals(current, value3)) |
| | | 1286 | | { |
| | 0 | 1287 | | return i; |
| | | 1288 | | } |
| | | 1289 | | } |
| | | 1290 | | |
| | 0 | 1291 | | return -1; |
| | | 1292 | | } |
| | | 1293 | | |
| | | 1294 | | internal static int LastIndexOfAnyExcept<T>(ref T searchSpace, T value0, T value1, T value2, T value3, int lengt |
| | | 1295 | | { |
| | 0 | 1296 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | | 1297 | | |
| | 0 | 1298 | | for (int i = length - 1; i >= 0; i--) |
| | | 1299 | | { |
| | 0 | 1300 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 1301 | | if (!EqualityComparer<T>.Default.Equals(current, value0) |
| | 0 | 1302 | | && !EqualityComparer<T>.Default.Equals(current, value1) |
| | 0 | 1303 | | && !EqualityComparer<T>.Default.Equals(current, value2) |
| | 0 | 1304 | | && !EqualityComparer<T>.Default.Equals(current, value3)) |
| | | 1305 | | { |
| | 0 | 1306 | | return i; |
| | | 1307 | | } |
| | | 1308 | | } |
| | | 1309 | | |
| | 0 | 1310 | | return -1; |
| | | 1311 | | } |
| | | 1312 | | |
| | | 1313 | | public static bool SequenceEqual<T>(ref T first, ref T second, int length) where T : IEquatable<T>? |
| | | 1314 | | { |
| | 0 | 1315 | | Debug.Assert(length >= 0); |
| | | 1316 | | |
| | 0 | 1317 | | if (Unsafe.AreSame(ref first, ref second)) |
| | | 1318 | | { |
| | 0 | 1319 | | return true; |
| | | 1320 | | } |
| | | 1321 | | |
| | 0 | 1322 | | nint index = 0; // Use nint for arithmetic to avoid unnecessary 64->32->64 truncations |
| | | 1323 | | T lookUp0; |
| | | 1324 | | T lookUp1; |
| | 0 | 1325 | | while (length >= 8) |
| | | 1326 | | { |
| | 0 | 1327 | | length -= 8; |
| | | 1328 | | |
| | 0 | 1329 | | lookUp0 = Unsafe.Add(ref first, index); |
| | 0 | 1330 | | lookUp1 = Unsafe.Add(ref second, index); |
| | 0 | 1331 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1332 | | { |
| | 0 | 1333 | | return false; |
| | | 1334 | | } |
| | | 1335 | | |
| | 0 | 1336 | | lookUp0 = Unsafe.Add(ref first, index + 1); |
| | 0 | 1337 | | lookUp1 = Unsafe.Add(ref second, index + 1); |
| | 0 | 1338 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1339 | | { |
| | 0 | 1340 | | return false; |
| | | 1341 | | } |
| | | 1342 | | |
| | 0 | 1343 | | lookUp0 = Unsafe.Add(ref first, index + 2); |
| | 0 | 1344 | | lookUp1 = Unsafe.Add(ref second, index + 2); |
| | 0 | 1345 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1346 | | { |
| | 0 | 1347 | | return false; |
| | | 1348 | | } |
| | | 1349 | | |
| | 0 | 1350 | | lookUp0 = Unsafe.Add(ref first, index + 3); |
| | 0 | 1351 | | lookUp1 = Unsafe.Add(ref second, index + 3); |
| | 0 | 1352 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1353 | | { |
| | 0 | 1354 | | return false; |
| | | 1355 | | } |
| | | 1356 | | |
| | 0 | 1357 | | lookUp0 = Unsafe.Add(ref first, index + 4); |
| | 0 | 1358 | | lookUp1 = Unsafe.Add(ref second, index + 4); |
| | 0 | 1359 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1360 | | { |
| | 0 | 1361 | | return false; |
| | | 1362 | | } |
| | | 1363 | | |
| | 0 | 1364 | | lookUp0 = Unsafe.Add(ref first, index + 5); |
| | 0 | 1365 | | lookUp1 = Unsafe.Add(ref second, index + 5); |
| | 0 | 1366 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1367 | | { |
| | 0 | 1368 | | return false; |
| | | 1369 | | } |
| | | 1370 | | |
| | 0 | 1371 | | lookUp0 = Unsafe.Add(ref first, index + 6); |
| | 0 | 1372 | | lookUp1 = Unsafe.Add(ref second, index + 6); |
| | 0 | 1373 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1374 | | { |
| | 0 | 1375 | | return false; |
| | | 1376 | | } |
| | | 1377 | | |
| | 0 | 1378 | | lookUp0 = Unsafe.Add(ref first, index + 7); |
| | 0 | 1379 | | lookUp1 = Unsafe.Add(ref second, index + 7); |
| | 0 | 1380 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1381 | | { |
| | 0 | 1382 | | return false; |
| | | 1383 | | } |
| | | 1384 | | |
| | 0 | 1385 | | index += 8; |
| | | 1386 | | } |
| | | 1387 | | |
| | 0 | 1388 | | if (length >= 4) |
| | | 1389 | | { |
| | 0 | 1390 | | length -= 4; |
| | | 1391 | | |
| | 0 | 1392 | | lookUp0 = Unsafe.Add(ref first, index); |
| | 0 | 1393 | | lookUp1 = Unsafe.Add(ref second, index); |
| | 0 | 1394 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1395 | | { |
| | 0 | 1396 | | return false; |
| | | 1397 | | } |
| | | 1398 | | |
| | 0 | 1399 | | lookUp0 = Unsafe.Add(ref first, index + 1); |
| | 0 | 1400 | | lookUp1 = Unsafe.Add(ref second, index + 1); |
| | 0 | 1401 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1402 | | { |
| | 0 | 1403 | | return false; |
| | | 1404 | | } |
| | | 1405 | | |
| | 0 | 1406 | | lookUp0 = Unsafe.Add(ref first, index + 2); |
| | 0 | 1407 | | lookUp1 = Unsafe.Add(ref second, index + 2); |
| | 0 | 1408 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1409 | | { |
| | 0 | 1410 | | return false; |
| | | 1411 | | } |
| | | 1412 | | |
| | 0 | 1413 | | lookUp0 = Unsafe.Add(ref first, index + 3); |
| | 0 | 1414 | | lookUp1 = Unsafe.Add(ref second, index + 3); |
| | 0 | 1415 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1416 | | { |
| | 0 | 1417 | | return false; |
| | | 1418 | | } |
| | | 1419 | | |
| | 0 | 1420 | | index += 4; |
| | | 1421 | | } |
| | | 1422 | | |
| | 0 | 1423 | | while (length > 0) |
| | | 1424 | | { |
| | 0 | 1425 | | lookUp0 = Unsafe.Add(ref first, index); |
| | 0 | 1426 | | lookUp1 = Unsafe.Add(ref second, index); |
| | 0 | 1427 | | if (!(lookUp0?.Equals(lookUp1) ?? (object?)lookUp1 is null)) |
| | | 1428 | | { |
| | 0 | 1429 | | return false; |
| | | 1430 | | } |
| | | 1431 | | |
| | 0 | 1432 | | index += 1; |
| | 0 | 1433 | | length--; |
| | | 1434 | | } |
| | | 1435 | | |
| | 0 | 1436 | | return true; |
| | | 1437 | | } |
| | | 1438 | | |
| | | 1439 | | public static int SequenceCompareTo<T>(ref T first, int firstLength, ref T second, int secondLength) |
| | | 1440 | | where T : IComparable<T>? |
| | | 1441 | | { |
| | 0 | 1442 | | Debug.Assert(firstLength >= 0); |
| | 0 | 1443 | | Debug.Assert(secondLength >= 0); |
| | | 1444 | | |
| | 0 | 1445 | | int minLength = firstLength; |
| | 0 | 1446 | | if (minLength > secondLength) |
| | 0 | 1447 | | minLength = secondLength; |
| | 0 | 1448 | | for (int i = 0; i < minLength; i++) |
| | | 1449 | | { |
| | 0 | 1450 | | T lookUp = Unsafe.Add(ref second, i); |
| | 0 | 1451 | | int result = (Unsafe.Add(ref first, i)?.CompareTo(lookUp) ?? (((object?)lookUp is null) ? 0 : -1)); |
| | 0 | 1452 | | if (result != 0) |
| | | 1453 | | { |
| | 0 | 1454 | | return result; |
| | | 1455 | | } |
| | | 1456 | | } |
| | | 1457 | | |
| | 0 | 1458 | | return firstLength.CompareTo(secondLength); |
| | | 1459 | | } |
| | | 1460 | | |
| | | 1461 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1462 | | internal static bool ContainsValueType<T>(ref T searchSpace, T value, int length) where T : struct, INumber<T> |
| | | 1463 | | { |
| | 21309 | 1464 | | if (PackedSpanHelpers.PackedIndexOfIsSupported && typeof(T) == typeof(short) && PackedSpanHelpers.CanUsePack |
| | | 1465 | | { |
| | 0 | 1466 | | return PackedSpanHelpers.Contains(ref Unsafe.As<T, short>(ref searchSpace), Unsafe.BitCast<T, short>(val |
| | | 1467 | | } |
| | | 1468 | | |
| | 21309 | 1469 | | return NonPackedContainsValueType(ref searchSpace, value, length); |
| | | 1470 | | } |
| | | 1471 | | |
| | | 1472 | | internal static bool NonPackedContainsValueType<T>(ref T searchSpace, T value, int length) where T : struct, INu |
| | | 1473 | | { |
| | 21309 | 1474 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 21309 | 1475 | | Debug.Assert(value is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 1476 | | |
| | 21309 | 1477 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<T>.Count) |
| | | 1478 | | { |
| | 2451 | 1479 | | nuint offset = 0; |
| | | 1480 | | |
| | 2487 | 1481 | | while (length >= 8) |
| | | 1482 | | { |
| | 259 | 1483 | | length -= 8; |
| | | 1484 | | |
| | 259 | 1485 | | if (Unsafe.Add(ref searchSpace, offset) == value |
| | 259 | 1486 | | || Unsafe.Add(ref searchSpace, offset + 1) == value |
| | 259 | 1487 | | || Unsafe.Add(ref searchSpace, offset + 2) == value |
| | 259 | 1488 | | || Unsafe.Add(ref searchSpace, offset + 3) == value |
| | 259 | 1489 | | || Unsafe.Add(ref searchSpace, offset + 4) == value |
| | 259 | 1490 | | || Unsafe.Add(ref searchSpace, offset + 5) == value |
| | 259 | 1491 | | || Unsafe.Add(ref searchSpace, offset + 6) == value |
| | 259 | 1492 | | || Unsafe.Add(ref searchSpace, offset + 7) == value) |
| | | 1493 | | { |
| | 223 | 1494 | | return true; |
| | | 1495 | | } |
| | | 1496 | | |
| | 36 | 1497 | | offset += 8; |
| | | 1498 | | } |
| | | 1499 | | |
| | 2228 | 1500 | | if (length >= 4) |
| | | 1501 | | { |
| | 126 | 1502 | | length -= 4; |
| | | 1503 | | |
| | 126 | 1504 | | if (Unsafe.Add(ref searchSpace, offset) == value |
| | 126 | 1505 | | || Unsafe.Add(ref searchSpace, offset + 1) == value |
| | 126 | 1506 | | || Unsafe.Add(ref searchSpace, offset + 2) == value |
| | 126 | 1507 | | || Unsafe.Add(ref searchSpace, offset + 3) == value) |
| | | 1508 | | { |
| | 99 | 1509 | | return true; |
| | | 1510 | | } |
| | | 1511 | | |
| | 27 | 1512 | | offset += 4; |
| | | 1513 | | } |
| | | 1514 | | |
| | 4825 | 1515 | | while (length > 0) |
| | | 1516 | | { |
| | 2792 | 1517 | | length -= 1; |
| | | 1518 | | |
| | 2792 | 1519 | | if (Unsafe.Add(ref searchSpace, offset) == value) |
| | | 1520 | | { |
| | 96 | 1521 | | return true; |
| | | 1522 | | } |
| | | 1523 | | |
| | 2696 | 1524 | | offset += 1; |
| | | 1525 | | } |
| | | 1526 | | } |
| | 18858 | 1527 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<T>.Count) |
| | | 1528 | | { |
| | 18765 | 1529 | | Vector512<T> current, values = Vector512.Create(value); |
| | 18765 | 1530 | | ref T currentSearchSpace = ref searchSpace; |
| | 18765 | 1531 | | ref T oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector512<T>.Count)); |
| | | 1532 | | |
| | | 1533 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 1534 | | do |
| | | 1535 | | { |
| | 36687 | 1536 | | current = Vector512.LoadUnsafe(ref currentSearchSpace); |
| | | 1537 | | |
| | 36687 | 1538 | | if (Vector512.EqualsAny(values, current)) |
| | | 1539 | | { |
| | 840 | 1540 | | return true; |
| | | 1541 | | } |
| | | 1542 | | |
| | 35847 | 1543 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector512<T>.Count); |
| | | 1544 | | } |
| | 35847 | 1545 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 1546 | | |
| | | 1547 | | // If any elements remain, process the last vector in the search space. |
| | 17925 | 1548 | | if ((uint)length % Vector512<T>.Count != 0) |
| | | 1549 | | { |
| | 17925 | 1550 | | current = Vector512.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | | 1551 | | |
| | 17925 | 1552 | | if (Vector512.EqualsAny(values, current)) |
| | | 1553 | | { |
| | 0 | 1554 | | return true; |
| | | 1555 | | } |
| | | 1556 | | } |
| | | 1557 | | } |
| | 93 | 1558 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<T>.Count) |
| | | 1559 | | { |
| | 32 | 1560 | | Vector256<T> equals, values = Vector256.Create(value); |
| | 32 | 1561 | | ref T currentSearchSpace = ref searchSpace; |
| | 32 | 1562 | | ref T oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector256<T>.Count)); |
| | | 1563 | | |
| | | 1564 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 1565 | | do |
| | | 1566 | | { |
| | 32 | 1567 | | equals = Vector256.Equals(values, Vector256.LoadUnsafe(ref currentSearchSpace)); |
| | 32 | 1568 | | if (equals == Vector256<T>.Zero) |
| | | 1569 | | { |
| | 0 | 1570 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector256<T>.Count); |
| | 0 | 1571 | | continue; |
| | | 1572 | | } |
| | | 1573 | | |
| | 32 | 1574 | | return true; |
| | | 1575 | | } |
| | 0 | 1576 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 1577 | | |
| | | 1578 | | // If any elements remain, process the last vector in the search space. |
| | 0 | 1579 | | if ((uint)length % Vector256<T>.Count != 0) |
| | | 1580 | | { |
| | 0 | 1581 | | equals = Vector256.Equals(values, Vector256.LoadUnsafe(ref oneVectorAwayFromEnd)); |
| | 0 | 1582 | | if (equals != Vector256<T>.Zero) |
| | | 1583 | | { |
| | 0 | 1584 | | return true; |
| | | 1585 | | } |
| | | 1586 | | } |
| | | 1587 | | } |
| | | 1588 | | else |
| | | 1589 | | { |
| | 61 | 1590 | | Vector128<T> equals, values = Vector128.Create(value); |
| | 61 | 1591 | | ref T currentSearchSpace = ref searchSpace; |
| | 61 | 1592 | | ref T oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector128<T>.Count)); |
| | | 1593 | | |
| | | 1594 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 1595 | | do |
| | | 1596 | | { |
| | 61 | 1597 | | equals = Vector128.Equals(values, Vector128.LoadUnsafe(ref currentSearchSpace)); |
| | 61 | 1598 | | if (equals == Vector128<T>.Zero) |
| | | 1599 | | { |
| | 0 | 1600 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector128<T>.Count); |
| | 0 | 1601 | | continue; |
| | | 1602 | | } |
| | | 1603 | | |
| | 61 | 1604 | | return true; |
| | | 1605 | | } |
| | 0 | 1606 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 1607 | | |
| | | 1608 | | // If any elements remain, process the first vector in the search space. |
| | 0 | 1609 | | if ((uint)length % Vector128<T>.Count != 0) |
| | | 1610 | | { |
| | 0 | 1611 | | equals = Vector128.Equals(values, Vector128.LoadUnsafe(ref oneVectorAwayFromEnd)); |
| | 0 | 1612 | | if (equals != Vector128<T>.Zero) |
| | | 1613 | | { |
| | 0 | 1614 | | return true; |
| | | 1615 | | } |
| | | 1616 | | } |
| | | 1617 | | } |
| | | 1618 | | |
| | 19958 | 1619 | | return false; |
| | | 1620 | | } |
| | | 1621 | | |
| | | 1622 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1623 | | internal static int IndexOfChar(ref char searchSpace, char value, int length) |
| | 1351 | 1624 | | => IndexOfValueType(ref Unsafe.As<char, short>(ref searchSpace), (short)value, length); |
| | | 1625 | | |
| | | 1626 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1627 | | internal static int LastIndexOfChar(ref char searchSpace, char value, int length) |
| | 0 | 1628 | | => LastIndexOfValueType(ref Unsafe.As<char, short>(ref searchSpace), (short)value, length); |
| | | 1629 | | |
| | | 1630 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1631 | | internal static int NonPackedIndexOfChar(ref char searchSpace, char value, int length) => |
| | 0 | 1632 | | NonPackedIndexOfValueType<short, DontNegate<short>>(ref Unsafe.As<char, short>(ref searchSpace), (short)valu |
| | | 1633 | | |
| | | 1634 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1635 | | internal static int IndexOfValueType<T>(ref T searchSpace, T value, int length) where T : struct, INumber<T> |
| | 19611 | 1636 | | => IndexOfValueType<T, DontNegate<T>>(ref searchSpace, value, length); |
| | | 1637 | | |
| | | 1638 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1639 | | internal static int IndexOfAnyExceptValueType<T>(ref T searchSpace, T value, int length) where T : struct, INumb |
| | 0 | 1640 | | => IndexOfValueType<T, Negate<T>>(ref searchSpace, value, length); |
| | | 1641 | | |
| | | 1642 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1643 | | private static int IndexOfValueType<TValue, TNegator>(ref TValue searchSpace, TValue value, int length) |
| | | 1644 | | where TValue : struct, INumber<TValue> |
| | | 1645 | | where TNegator : struct, INegator<TValue> |
| | | 1646 | | { |
| | 19611 | 1647 | | if (PackedSpanHelpers.PackedIndexOfIsSupported && typeof(TValue) == typeof(short) && PackedSpanHelpers.CanUs |
| | | 1648 | | { |
| | 10308 | 1649 | | return typeof(TNegator) == typeof(DontNegate<short>) |
| | 10308 | 1650 | | ? PackedSpanHelpers.IndexOf(ref Unsafe.As<TValue, char>(ref searchSpace), Unsafe.BitCast<TValue, cha |
| | 10308 | 1651 | | : PackedSpanHelpers.IndexOfAnyExcept(ref Unsafe.As<TValue, char>(ref searchSpace), Unsafe.BitCast<TV |
| | | 1652 | | } |
| | | 1653 | | |
| | 9303 | 1654 | | return NonPackedIndexOfValueType<TValue, TNegator>(ref searchSpace, value, length); |
| | | 1655 | | } |
| | | 1656 | | |
| | | 1657 | | internal static int NonPackedIndexOfValueType<TValue, TNegator>(ref TValue searchSpace, TValue value, int length |
| | | 1658 | | where TValue : struct, INumber<TValue> |
| | | 1659 | | where TNegator : struct, INegator<TValue> |
| | | 1660 | | { |
| | 17855 | 1661 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 17855 | 1662 | | Debug.Assert(value is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 1663 | | |
| | 17855 | 1664 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 1665 | | { |
| | 7730 | 1666 | | nuint offset = 0; |
| | | 1667 | | |
| | 8140 | 1668 | | while (length >= 8) |
| | | 1669 | | { |
| | 2158 | 1670 | | length -= 8; |
| | | 1671 | | |
| | 2158 | 1672 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset) == value)) |
| | | 1673 | | { |
| | 310 | 1674 | | return (int)(offset); |
| | | 1675 | | } |
| | 1848 | 1676 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 1) == value)) |
| | | 1677 | | { |
| | 182 | 1678 | | return (int)(offset + 1); |
| | | 1679 | | } |
| | 1666 | 1680 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 2) == value)) |
| | | 1681 | | { |
| | 182 | 1682 | | return (int)(offset + 2); |
| | | 1683 | | } |
| | 1484 | 1684 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 3) == value)) |
| | | 1685 | | { |
| | 246 | 1686 | | return (int)(offset + 3); |
| | | 1687 | | } |
| | 1238 | 1688 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 4) == value)) |
| | | 1689 | | { |
| | 316 | 1690 | | return (int)(offset + 4); |
| | | 1691 | | } |
| | 922 | 1692 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 5) == value)) |
| | | 1693 | | { |
| | 349 | 1694 | | return (int)(offset + 5); |
| | | 1695 | | } |
| | 573 | 1696 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 6) == value)) |
| | | 1697 | | { |
| | 101 | 1698 | | return (int)(offset + 6); |
| | | 1699 | | } |
| | 472 | 1700 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 7) == value)) |
| | | 1701 | | { |
| | 62 | 1702 | | return (int)(offset + 7); |
| | | 1703 | | } |
| | | 1704 | | |
| | 410 | 1705 | | offset += 8; |
| | | 1706 | | } |
| | | 1707 | | |
| | 5982 | 1708 | | if (length >= 4) |
| | | 1709 | | { |
| | 1850 | 1710 | | length -= 4; |
| | | 1711 | | |
| | 1850 | 1712 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset) == value)) |
| | | 1713 | | { |
| | 615 | 1714 | | return (int)(offset); |
| | | 1715 | | } |
| | 1235 | 1716 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 1) == value)) |
| | | 1717 | | { |
| | 143 | 1718 | | return (int)(offset + 1); |
| | | 1719 | | } |
| | 1092 | 1720 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 2) == value)) |
| | | 1721 | | { |
| | 140 | 1722 | | return (int)(offset + 2); |
| | | 1723 | | } |
| | 952 | 1724 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset + 3) == value)) |
| | | 1725 | | { |
| | 127 | 1726 | | return (int)(offset + 3); |
| | | 1727 | | } |
| | | 1728 | | |
| | 825 | 1729 | | offset += 4; |
| | | 1730 | | } |
| | | 1731 | | |
| | 8027 | 1732 | | while (length > 0) |
| | | 1733 | | { |
| | 5383 | 1734 | | length -= 1; |
| | | 1735 | | |
| | 5383 | 1736 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset) == value)) |
| | | 1737 | | { |
| | 2313 | 1738 | | return (int)(offset); |
| | | 1739 | | } |
| | | 1740 | | |
| | 3070 | 1741 | | offset += 1; |
| | | 1742 | | } |
| | | 1743 | | |
| | 2644 | 1744 | | return -1; |
| | | 1745 | | } |
| | 10125 | 1746 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 1747 | | { |
| | 6304 | 1748 | | Vector512<TValue> current, values = Vector512.Create(value); |
| | 6304 | 1749 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 6304 | 1750 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector512<TValue>.Count); |
| | | 1751 | | |
| | | 1752 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 1753 | | do |
| | | 1754 | | { |
| | 20989 | 1755 | | current = Vector512.LoadUnsafe(ref currentSearchSpace); |
| | | 1756 | | |
| | 20989 | 1757 | | if (TNegator.HasMatch(values, current)) |
| | | 1758 | | { |
| | 5162 | 1759 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, TNegator.GetMatchMask(values, |
| | | 1760 | | } |
| | | 1761 | | |
| | 15827 | 1762 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector512<TValue>.Count); |
| | | 1763 | | } |
| | 15827 | 1764 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 1765 | | |
| | | 1766 | | // If any elements remain, process the last vector in the search space. |
| | 1142 | 1767 | | if ((uint)length % Vector512<TValue>.Count != 0) |
| | | 1768 | | { |
| | 978 | 1769 | | current = Vector512.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | | 1770 | | |
| | 978 | 1771 | | if (TNegator.HasMatch(values, current)) |
| | | 1772 | | { |
| | 495 | 1773 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, TNegator.GetMatchMask(values |
| | | 1774 | | } |
| | | 1775 | | } |
| | | 1776 | | } |
| | 3821 | 1777 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 1778 | | { |
| | 1824 | 1779 | | Vector256<TValue> equals, values = Vector256.Create(value); |
| | 1824 | 1780 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 1824 | 1781 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector256<TValue>.Count); |
| | | 1782 | | |
| | | 1783 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 1784 | | do |
| | | 1785 | | { |
| | 1824 | 1786 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values, Vector256.LoadUnsafe(ref currentSearchSpac |
| | 1824 | 1787 | | if (equals == Vector256<TValue>.Zero) |
| | | 1788 | | { |
| | 639 | 1789 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector256<TValue>.Count); |
| | 639 | 1790 | | continue; |
| | | 1791 | | } |
| | | 1792 | | |
| | 1185 | 1793 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 1794 | | } |
| | 639 | 1795 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 1796 | | |
| | | 1797 | | // If any elements remain, process the last vector in the search space. |
| | 639 | 1798 | | if ((uint)length % Vector256<TValue>.Count != 0) |
| | | 1799 | | { |
| | 565 | 1800 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values, Vector256.LoadUnsafe(ref oneVectorAwayFrom |
| | 565 | 1801 | | if (equals != Vector256<TValue>.Zero) |
| | | 1802 | | { |
| | 140 | 1803 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 1804 | | } |
| | | 1805 | | } |
| | | 1806 | | } |
| | | 1807 | | else |
| | | 1808 | | { |
| | 1997 | 1809 | | Vector128<TValue> equals, values = Vector128.Create(value); |
| | 1997 | 1810 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 1997 | 1811 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector128<TValue>.Count); |
| | | 1812 | | |
| | | 1813 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 1814 | | do |
| | | 1815 | | { |
| | 1997 | 1816 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values, Vector128.LoadUnsafe(ref currentSearchSpac |
| | 1997 | 1817 | | if (equals == Vector128<TValue>.Zero) |
| | | 1818 | | { |
| | 471 | 1819 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector128<TValue>.Count); |
| | 471 | 1820 | | continue; |
| | | 1821 | | } |
| | | 1822 | | |
| | 1526 | 1823 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 1824 | | } |
| | 471 | 1825 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 1826 | | |
| | | 1827 | | // If any elements remain, process the first vector in the search space. |
| | 471 | 1828 | | if ((uint)length % Vector128<TValue>.Count != 0) |
| | | 1829 | | { |
| | 366 | 1830 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values, Vector128.LoadUnsafe(ref oneVectorAwayFrom |
| | 366 | 1831 | | if (equals != Vector128<TValue>.Zero) |
| | | 1832 | | { |
| | 272 | 1833 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 1834 | | } |
| | | 1835 | | } |
| | | 1836 | | } |
| | | 1837 | | |
| | 1345 | 1838 | | return -1; |
| | | 1839 | | } |
| | | 1840 | | |
| | | 1841 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1842 | | internal static int IndexOfAnyChar(ref char searchSpace, char value0, char value1, int length) |
| | 0 | 1843 | | => IndexOfAnyValueType(ref Unsafe.As<char, short>(ref searchSpace), (short)value0, (short)value1, length); |
| | | 1844 | | |
| | | 1845 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1846 | | internal static int LastIndexOfAnyChar(ref char searchSpace, char value0, char value1, int length) |
| | 0 | 1847 | | => LastIndexOfAnyValueType(ref Unsafe.As<char, short>(ref searchSpace), (short)value0, (short)value1, length |
| | | 1848 | | |
| | | 1849 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1850 | | internal static int IndexOfAnyValueType<T>(ref T searchSpace, T value0, T value1, int length) where T : struct, |
| | 0 | 1851 | | => IndexOfAnyValueType<T, DontNegate<T>>(ref searchSpace, value0, value1, length); |
| | | 1852 | | |
| | | 1853 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1854 | | internal static int IndexOfAnyExceptValueType<T>(ref T searchSpace, T value0, T value1, int length) where T : st |
| | 0 | 1855 | | => IndexOfAnyValueType<T, Negate<T>>(ref searchSpace, value0, value1, length); |
| | | 1856 | | |
| | | 1857 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 1858 | | private static int IndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue value1, i |
| | | 1859 | | where TValue : struct, INumber<TValue> |
| | | 1860 | | where TNegator : struct, INegator<TValue> |
| | | 1861 | | { |
| | 0 | 1862 | | if (PackedSpanHelpers.PackedIndexOfIsSupported && typeof(TValue) == typeof(short) && PackedSpanHelpers.CanUs |
| | | 1863 | | { |
| | 0 | 1864 | | char char0 = Unsafe.BitCast<TValue, char>(value0); |
| | 0 | 1865 | | char char1 = Unsafe.BitCast<TValue, char>(value1); |
| | | 1866 | | |
| | 0 | 1867 | | if (RuntimeHelpers.IsKnownConstant(value0) && RuntimeHelpers.IsKnownConstant(value1)) |
| | | 1868 | | { |
| | | 1869 | | // If the values differ only in the 0x20 bit, we can optimize the search by reducing the number of c |
| | | 1870 | | // This optimization only applies to a small subset of values and the throughput difference is not t |
| | | 1871 | | // We avoid introducing per-call overhead for non-constant values by guarding this optimization behi |
| | 0 | 1872 | | if ((char0 ^ char1) == 0x20) |
| | | 1873 | | { |
| | 0 | 1874 | | char lowerCase = (char)Math.Max(char0, char1); |
| | | 1875 | | |
| | 0 | 1876 | | return typeof(TNegator) == typeof(DontNegate<short>) |
| | 0 | 1877 | | ? PackedSpanHelpers.IndexOfAnyIgnoreCase(ref Unsafe.As<TValue, char>(ref searchSpace), lower |
| | 0 | 1878 | | : PackedSpanHelpers.IndexOfAnyExceptIgnoreCase(ref Unsafe.As<TValue, char>(ref searchSpace), |
| | | 1879 | | } |
| | | 1880 | | } |
| | | 1881 | | |
| | 0 | 1882 | | return typeof(TNegator) == typeof(DontNegate<short>) |
| | 0 | 1883 | | ? PackedSpanHelpers.IndexOfAny(ref Unsafe.As<TValue, char>(ref searchSpace), char0, char1, length) |
| | 0 | 1884 | | : PackedSpanHelpers.IndexOfAnyExcept(ref Unsafe.As<TValue, char>(ref searchSpace), char0, char1, len |
| | | 1885 | | } |
| | | 1886 | | |
| | 0 | 1887 | | return NonPackedIndexOfAnyValueType<TValue, TNegator>(ref searchSpace, value0, value1, length); |
| | | 1888 | | } |
| | | 1889 | | |
| | | 1890 | | // having INumber<T> constraint here allows to use == operator and get better perf compared to .Equals |
| | | 1891 | | internal static int NonPackedIndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue |
| | | 1892 | | where TValue : struct, INumber<TValue> |
| | | 1893 | | where TNegator : struct, INegator<TValue> |
| | | 1894 | | { |
| | 14136 | 1895 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 14136 | 1896 | | Debug.Assert(value0 is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 1897 | | |
| | 14136 | 1898 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 1899 | | { |
| | 8754 | 1900 | | nuint offset = 0; |
| | | 1901 | | TValue lookUp; |
| | | 1902 | | |
| | 8754 | 1903 | | if (typeof(TValue) == typeof(byte)) // this optimization is beneficial only to byte |
| | | 1904 | | { |
| | 1941 | 1905 | | while (length >= 8) |
| | | 1906 | | { |
| | 684 | 1907 | | length -= 8; |
| | | 1908 | | |
| | 684 | 1909 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 684 | 1910 | | lookUp = current; |
| | 684 | 1911 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1912 | | { |
| | 342 | 1913 | | return (int)(offset); |
| | | 1914 | | } |
| | | 1915 | | |
| | 342 | 1916 | | lookUp = Unsafe.Add(ref current, 1); |
| | 342 | 1917 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1918 | | { |
| | 90 | 1919 | | return (int)(offset + 1); |
| | | 1920 | | } |
| | | 1921 | | |
| | 252 | 1922 | | lookUp = Unsafe.Add(ref current, 2); |
| | 252 | 1923 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1924 | | { |
| | 63 | 1925 | | return (int)(offset + 2); |
| | | 1926 | | } |
| | | 1927 | | |
| | 189 | 1928 | | lookUp = Unsafe.Add(ref current, 3); |
| | 189 | 1929 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1930 | | { |
| | 42 | 1931 | | return (int)(offset + 3); |
| | | 1932 | | } |
| | | 1933 | | |
| | 147 | 1934 | | lookUp = Unsafe.Add(ref current, 4); |
| | 147 | 1935 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1936 | | { |
| | 24 | 1937 | | return (int)(offset + 4); |
| | | 1938 | | } |
| | | 1939 | | |
| | 123 | 1940 | | lookUp = Unsafe.Add(ref current, 5); |
| | 123 | 1941 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1942 | | { |
| | 21 | 1943 | | return (int)(offset + 5); |
| | | 1944 | | } |
| | | 1945 | | |
| | 102 | 1946 | | lookUp = Unsafe.Add(ref current, 6); |
| | 102 | 1947 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1948 | | { |
| | 27 | 1949 | | return (int)(offset + 6); |
| | | 1950 | | } |
| | | 1951 | | |
| | 75 | 1952 | | lookUp = Unsafe.Add(ref current, 7); |
| | 75 | 1953 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1954 | | { |
| | 24 | 1955 | | return (int)(offset + 7); |
| | | 1956 | | } |
| | | 1957 | | |
| | 51 | 1958 | | offset += 8; |
| | | 1959 | | } |
| | | 1960 | | } |
| | | 1961 | | |
| | 8610 | 1962 | | while (length >= 4) |
| | | 1963 | | { |
| | 1410 | 1964 | | length -= 4; |
| | | 1965 | | |
| | 1410 | 1966 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 1410 | 1967 | | lookUp = current; |
| | 1410 | 1968 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1969 | | { |
| | 696 | 1970 | | return (int)(offset); |
| | | 1971 | | } |
| | | 1972 | | |
| | 714 | 1973 | | lookUp = Unsafe.Add(ref current, 1); |
| | 714 | 1974 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1975 | | { |
| | 135 | 1976 | | return (int)(offset + 1); |
| | | 1977 | | } |
| | | 1978 | | |
| | 579 | 1979 | | lookUp = Unsafe.Add(ref current, 2); |
| | 579 | 1980 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1981 | | { |
| | 48 | 1982 | | return (int)(offset + 2); |
| | | 1983 | | } |
| | | 1984 | | |
| | 531 | 1985 | | lookUp = Unsafe.Add(ref current, 3); |
| | 531 | 1986 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 1987 | | { |
| | 42 | 1988 | | return (int)(offset + 3); |
| | | 1989 | | } |
| | | 1990 | | |
| | 489 | 1991 | | offset += 4; |
| | | 1992 | | } |
| | | 1993 | | |
| | 13191 | 1994 | | while (length > 0) |
| | | 1995 | | { |
| | 9111 | 1996 | | length -= 1; |
| | | 1997 | | |
| | 9111 | 1998 | | lookUp = Unsafe.Add(ref searchSpace, offset); |
| | 9111 | 1999 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2000 | | { |
| | 3120 | 2001 | | return (int)(offset); |
| | | 2002 | | } |
| | | 2003 | | |
| | 5991 | 2004 | | offset += 1; |
| | | 2005 | | } |
| | | 2006 | | |
| | 4080 | 2007 | | return -1; |
| | | 2008 | | } |
| | 5382 | 2009 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 2010 | | { |
| | 8004 | 2011 | | Vector512<TValue> equals, current, values0 = Vector512.Create(value0), values1 = Vector512.Create(value1 |
| | 4002 | 2012 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 4002 | 2013 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector512<TValue>.Count); |
| | | 2014 | | |
| | | 2015 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2016 | | do |
| | | 2017 | | { |
| | 16926 | 2018 | | current = Vector512.LoadUnsafe(ref currentSearchSpace); |
| | 16926 | 2019 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(values0, current) | Vector512.Equals(values1, curr |
| | 16926 | 2020 | | if (equals == Vector512<TValue>.Zero) |
| | | 2021 | | { |
| | 14289 | 2022 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector512<TValue>.Count); |
| | 14289 | 2023 | | continue; |
| | | 2024 | | } |
| | | 2025 | | |
| | 2637 | 2026 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2027 | | } |
| | 14289 | 2028 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2029 | | |
| | | 2030 | | // If any elements remain, process the last vector in the search space. |
| | 1365 | 2031 | | if ((uint)length % Vector512<TValue>.Count != 0) |
| | | 2032 | | { |
| | 1011 | 2033 | | current = Vector512.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 1011 | 2034 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(values0, current) | Vector512.Equals(values1, curr |
| | 1011 | 2035 | | if (equals != Vector512<TValue>.Zero) |
| | | 2036 | | { |
| | 90 | 2037 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2038 | | } |
| | | 2039 | | } |
| | | 2040 | | } |
| | 1380 | 2041 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 2042 | | { |
| | 1320 | 2043 | | Vector256<TValue> equals, current, values0 = Vector256.Create(value0), values1 = Vector256.Create(value1 |
| | 660 | 2044 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 660 | 2045 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector256<TValue>.Count); |
| | | 2046 | | |
| | | 2047 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2048 | | do |
| | | 2049 | | { |
| | 660 | 2050 | | current = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | 660 | 2051 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values0, current) | Vector256.Equals(values1, curr |
| | 660 | 2052 | | if (equals == Vector256<TValue>.Zero) |
| | | 2053 | | { |
| | 231 | 2054 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector256<TValue>.Count); |
| | 231 | 2055 | | continue; |
| | | 2056 | | } |
| | | 2057 | | |
| | 429 | 2058 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2059 | | } |
| | 231 | 2060 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2061 | | |
| | | 2062 | | // If any elements remain, process the last vector in the search space. |
| | 231 | 2063 | | if ((uint)length % Vector256<TValue>.Count != 0) |
| | | 2064 | | { |
| | 144 | 2065 | | current = Vector256.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 144 | 2066 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values0, current) | Vector256.Equals(values1, curr |
| | 144 | 2067 | | if (equals != Vector256<TValue>.Zero) |
| | | 2068 | | { |
| | 24 | 2069 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2070 | | } |
| | | 2071 | | } |
| | | 2072 | | } |
| | | 2073 | | else |
| | | 2074 | | { |
| | 1440 | 2075 | | Vector128<TValue> equals, current, values0 = Vector128.Create(value0), values1 = Vector128.Create(value1 |
| | 720 | 2076 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 720 | 2077 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector128<TValue>.Count); |
| | | 2078 | | |
| | | 2079 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2080 | | do |
| | | 2081 | | { |
| | 720 | 2082 | | current = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | 720 | 2083 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values0, current) | Vector128.Equals(values1, curr |
| | 720 | 2084 | | if (equals == Vector128<TValue>.Zero) |
| | | 2085 | | { |
| | 285 | 2086 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector128<TValue>.Count); |
| | 285 | 2087 | | continue; |
| | | 2088 | | } |
| | | 2089 | | |
| | 435 | 2090 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2091 | | } |
| | 285 | 2092 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2093 | | |
| | | 2094 | | // If any elements remain, process the first vector in the search space. |
| | 285 | 2095 | | if ((uint)length % Vector128<TValue>.Count != 0) |
| | | 2096 | | { |
| | 147 | 2097 | | current = Vector128.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 147 | 2098 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values0, current) | Vector128.Equals(values1, curr |
| | 147 | 2099 | | if (equals != Vector128<TValue>.Zero) |
| | | 2100 | | { |
| | 39 | 2101 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2102 | | } |
| | | 2103 | | } |
| | | 2104 | | } |
| | | 2105 | | |
| | 1728 | 2106 | | return -1; |
| | | 2107 | | } |
| | | 2108 | | |
| | | 2109 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2110 | | internal static int IndexOfAnyValueType<T>(ref T searchSpace, T value0, T value1, T value2, int length) where T |
| | 0 | 2111 | | => IndexOfAnyValueType<T, DontNegate<T>>(ref searchSpace, value0, value1, value2, length); |
| | | 2112 | | |
| | | 2113 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2114 | | internal static int IndexOfAnyExceptValueType<T>(ref T searchSpace, T value0, T value1, T value2, int length) wh |
| | 0 | 2115 | | => IndexOfAnyValueType<T, Negate<T>>(ref searchSpace, value0, value1, value2, length); |
| | | 2116 | | |
| | | 2117 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2118 | | private static int IndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue value1, T |
| | | 2119 | | where TValue : struct, INumber<TValue> |
| | | 2120 | | where TNegator : struct, INegator<TValue> |
| | | 2121 | | { |
| | 0 | 2122 | | if (PackedSpanHelpers.PackedIndexOfIsSupported && typeof(TValue) == typeof(short) && PackedSpanHelpers.CanUs |
| | | 2123 | | { |
| | 0 | 2124 | | return typeof(TNegator) == typeof(DontNegate<short>) |
| | 0 | 2125 | | ? PackedSpanHelpers.IndexOfAny(ref Unsafe.As<TValue, char>(ref searchSpace), Unsafe.BitCast<TValue, |
| | 0 | 2126 | | : PackedSpanHelpers.IndexOfAnyExcept(ref Unsafe.As<TValue, char>(ref searchSpace), Unsafe.BitCast<TV |
| | | 2127 | | } |
| | | 2128 | | |
| | 0 | 2129 | | return NonPackedIndexOfAnyValueType<TValue, TNegator>(ref searchSpace, value0, value1, value2, length); |
| | | 2130 | | } |
| | | 2131 | | |
| | | 2132 | | internal static int NonPackedIndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue |
| | | 2133 | | where TValue : struct, INumber<TValue> |
| | | 2134 | | where TNegator : struct, INegator<TValue> |
| | | 2135 | | { |
| | 6976 | 2136 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 6976 | 2137 | | Debug.Assert(value0 is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 2138 | | |
| | 6976 | 2139 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 2140 | | { |
| | 4246 | 2141 | | nuint offset = 0; |
| | | 2142 | | TValue lookUp; |
| | | 2143 | | |
| | 4246 | 2144 | | if (typeof(TValue) == typeof(byte)) // this optimization is beneficial only to byte |
| | | 2145 | | { |
| | 2739 | 2146 | | while (length >= 8) |
| | | 2147 | | { |
| | 924 | 2148 | | length -= 8; |
| | | 2149 | | |
| | 924 | 2150 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 924 | 2151 | | lookUp = current; |
| | 924 | 2152 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2153 | | { |
| | 462 | 2154 | | return (int)(offset); |
| | | 2155 | | } |
| | | 2156 | | |
| | 462 | 2157 | | lookUp = Unsafe.Add(ref current, 1); |
| | 462 | 2158 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2159 | | { |
| | 123 | 2160 | | return (int)(offset + 1); |
| | | 2161 | | } |
| | | 2162 | | |
| | 339 | 2163 | | lookUp = Unsafe.Add(ref current, 2); |
| | 339 | 2164 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2165 | | { |
| | 81 | 2166 | | return (int)(offset + 2); |
| | | 2167 | | } |
| | | 2168 | | |
| | 258 | 2169 | | lookUp = Unsafe.Add(ref current, 3); |
| | 258 | 2170 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2171 | | { |
| | 39 | 2172 | | return (int)(offset + 3); |
| | | 2173 | | } |
| | | 2174 | | |
| | 219 | 2175 | | lookUp = Unsafe.Add(ref current, 4); |
| | 219 | 2176 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2177 | | { |
| | 42 | 2178 | | return (int)(offset + 4); |
| | | 2179 | | } |
| | | 2180 | | |
| | 177 | 2181 | | lookUp = Unsafe.Add(ref current, 5); |
| | 177 | 2182 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2183 | | { |
| | 30 | 2184 | | return (int)(offset + 5); |
| | | 2185 | | } |
| | | 2186 | | |
| | 147 | 2187 | | lookUp = Unsafe.Add(ref current, 6); |
| | 147 | 2188 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2189 | | { |
| | 30 | 2190 | | return (int)(offset + 6); |
| | | 2191 | | } |
| | | 2192 | | |
| | 117 | 2193 | | lookUp = Unsafe.Add(ref current, 7); |
| | 117 | 2194 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2195 | | { |
| | 42 | 2196 | | return (int)(offset + 7); |
| | | 2197 | | } |
| | | 2198 | | |
| | 75 | 2199 | | offset += 8; |
| | | 2200 | | } |
| | | 2201 | | } |
| | | 2202 | | |
| | 3535 | 2203 | | while (length >= 4) |
| | | 2204 | | { |
| | 546 | 2205 | | length -= 4; |
| | | 2206 | | |
| | 546 | 2207 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 546 | 2208 | | lookUp = current; |
| | 546 | 2209 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2210 | | { |
| | 267 | 2211 | | return (int)(offset); |
| | | 2212 | | } |
| | | 2213 | | |
| | 279 | 2214 | | lookUp = Unsafe.Add(ref current, 1); |
| | 279 | 2215 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2216 | | { |
| | 90 | 2217 | | return (int)(offset + 1); |
| | | 2218 | | } |
| | | 2219 | | |
| | 189 | 2220 | | lookUp = Unsafe.Add(ref current, 2); |
| | 189 | 2221 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2222 | | { |
| | 27 | 2223 | | return (int)(offset + 2); |
| | | 2224 | | } |
| | | 2225 | | |
| | 162 | 2226 | | lookUp = Unsafe.Add(ref current, 3); |
| | 162 | 2227 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2228 | | { |
| | 24 | 2229 | | return (int)(offset + 3); |
| | | 2230 | | } |
| | | 2231 | | |
| | 138 | 2232 | | offset += 4; |
| | | 2233 | | } |
| | | 2234 | | |
| | 6298 | 2235 | | while (length > 0) |
| | | 2236 | | { |
| | 4571 | 2237 | | length -= 1; |
| | | 2238 | | |
| | 4571 | 2239 | | lookUp = Unsafe.Add(ref searchSpace, offset); |
| | 4571 | 2240 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 2241 | | { |
| | 1262 | 2242 | | return (int)(offset); |
| | | 2243 | | } |
| | | 2244 | | |
| | 3309 | 2245 | | offset += 1; |
| | | 2246 | | } |
| | | 2247 | | |
| | 1727 | 2248 | | return -1; |
| | | 2249 | | } |
| | 2730 | 2250 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 2251 | | { |
| | 5742 | 2252 | | Vector512<TValue> equals, current, values0 = Vector512.Create(value0), values1 = Vector512.Create(value1 |
| | 1914 | 2253 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 1914 | 2254 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector512<TValue>.Count); |
| | | 2255 | | |
| | | 2256 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2257 | | do |
| | | 2258 | | { |
| | 6843 | 2259 | | current = Vector512.LoadUnsafe(ref currentSearchSpace); |
| | 6843 | 2260 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(values0, current) | Vector512.Equals(values1, curr |
| | 6843 | 2261 | | if (equals == Vector512<TValue>.Zero) |
| | | 2262 | | { |
| | 5550 | 2263 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector512<TValue>.Count); |
| | 5550 | 2264 | | continue; |
| | | 2265 | | } |
| | | 2266 | | |
| | 1293 | 2267 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2268 | | } |
| | 5550 | 2269 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2270 | | |
| | | 2271 | | // If any elements remain, process the last vector in the search space. |
| | 621 | 2272 | | if ((uint)length % Vector512<TValue>.Count != 0) |
| | | 2273 | | { |
| | 483 | 2274 | | current = Vector512.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 483 | 2275 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(values0, current) | Vector512.Equals(values1, curr |
| | 483 | 2276 | | if (equals != Vector512<TValue>.Zero) |
| | | 2277 | | { |
| | 84 | 2278 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2279 | | } |
| | | 2280 | | } |
| | | 2281 | | } |
| | 816 | 2282 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 2283 | | { |
| | 1206 | 2284 | | Vector256<TValue> equals, current, values0 = Vector256.Create(value0), values1 = Vector256.Create(value1 |
| | 402 | 2285 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 402 | 2286 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector256<TValue>.Count); |
| | | 2287 | | |
| | | 2288 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2289 | | do |
| | | 2290 | | { |
| | 402 | 2291 | | current = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | 402 | 2292 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values0, current) | Vector256.Equals(values1, curr |
| | 402 | 2293 | | if (equals == Vector256<TValue>.Zero) |
| | | 2294 | | { |
| | 141 | 2295 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector256<TValue>.Count); |
| | 141 | 2296 | | continue; |
| | | 2297 | | } |
| | | 2298 | | |
| | 261 | 2299 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2300 | | } |
| | 141 | 2301 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2302 | | |
| | | 2303 | | // If any elements remain, process the last vector in the search space. |
| | 141 | 2304 | | if ((uint)length % Vector256<TValue>.Count != 0) |
| | | 2305 | | { |
| | 108 | 2306 | | current = Vector256.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 108 | 2307 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values0, current) | Vector256.Equals(values1, curr |
| | 108 | 2308 | | if (equals != Vector256<TValue>.Zero) |
| | | 2309 | | { |
| | 9 | 2310 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2311 | | } |
| | | 2312 | | } |
| | | 2313 | | } |
| | | 2314 | | else |
| | | 2315 | | { |
| | 1242 | 2316 | | Vector128<TValue> equals, current, values0 = Vector128.Create(value0), values1 = Vector128.Create(value1 |
| | 414 | 2317 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 414 | 2318 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector128<TValue>.Count); |
| | | 2319 | | |
| | | 2320 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2321 | | do |
| | | 2322 | | { |
| | 414 | 2323 | | current = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | 414 | 2324 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values0, current) | Vector128.Equals(values1, curr |
| | 414 | 2325 | | if (equals == Vector128<TValue>.Zero) |
| | | 2326 | | { |
| | 147 | 2327 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector128<TValue>.Count); |
| | 147 | 2328 | | continue; |
| | | 2329 | | } |
| | | 2330 | | |
| | 267 | 2331 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2332 | | } |
| | 147 | 2333 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2334 | | |
| | | 2335 | | // If any elements remain, process the first vector in the search space. |
| | 147 | 2336 | | if ((uint)length % Vector128<TValue>.Count != 0) |
| | | 2337 | | { |
| | 66 | 2338 | | current = Vector128.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 66 | 2339 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values0, current) | Vector128.Equals(values1, curr |
| | 66 | 2340 | | if (equals != Vector128<TValue>.Zero) |
| | | 2341 | | { |
| | 18 | 2342 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2343 | | } |
| | | 2344 | | } |
| | | 2345 | | } |
| | | 2346 | | |
| | 798 | 2347 | | return -1; |
| | | 2348 | | } |
| | | 2349 | | |
| | | 2350 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2351 | | internal static int IndexOfAnyValueType<T>(ref T searchSpace, T value0, T value1, T value2, T value3, int length |
| | 3344 | 2352 | | => IndexOfAnyValueType<T, DontNegate<T>>(ref searchSpace, value0, value1, value2, value3, length); |
| | | 2353 | | |
| | | 2354 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2355 | | internal static int IndexOfAnyExceptValueType<T>(ref T searchSpace, T value0, T value1, T value2, T value3, int |
| | 3344 | 2356 | | => IndexOfAnyValueType<T, Negate<T>>(ref searchSpace, value0, value1, value2, value3, length); |
| | | 2357 | | |
| | | 2358 | | private static int IndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue value1, T |
| | | 2359 | | where TValue : struct, INumber<TValue> |
| | | 2360 | | where TNegator : struct, INegator<TValue> |
| | | 2361 | | { |
| | 6688 | 2362 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 6688 | 2363 | | Debug.Assert(value0 is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 2364 | | |
| | 6688 | 2365 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 2366 | | { |
| | 4174 | 2367 | | nuint offset = 0; |
| | | 2368 | | TValue lookUp; |
| | | 2369 | | |
| | 5607 | 2370 | | while (length >= 4) |
| | | 2371 | | { |
| | 3580 | 2372 | | length -= 4; |
| | | 2373 | | |
| | 3580 | 2374 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 3580 | 2375 | | lookUp = current; |
| | 3580 | 2376 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2377 | | { |
| | 1685 | 2378 | | return (int)(offset); |
| | | 2379 | | } |
| | | 2380 | | |
| | 1895 | 2381 | | lookUp = Unsafe.Add(ref current, 1); |
| | 1895 | 2382 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2383 | | { |
| | 198 | 2384 | | return (int)(offset + 1); |
| | | 2385 | | } |
| | | 2386 | | |
| | 1697 | 2387 | | lookUp = Unsafe.Add(ref current, 2); |
| | 1697 | 2388 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2389 | | { |
| | 144 | 2390 | | return (int)(offset + 2); |
| | | 2391 | | } |
| | | 2392 | | |
| | 1553 | 2393 | | lookUp = Unsafe.Add(ref current, 3); |
| | 1553 | 2394 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2395 | | { |
| | 120 | 2396 | | return (int)(offset + 3); |
| | | 2397 | | } |
| | | 2398 | | |
| | 1433 | 2399 | | offset += 4; |
| | | 2400 | | } |
| | | 2401 | | |
| | 2594 | 2402 | | while (length > 0) |
| | | 2403 | | { |
| | 957 | 2404 | | length -= 1; |
| | | 2405 | | |
| | 957 | 2406 | | lookUp = Unsafe.Add(ref searchSpace, offset); |
| | 957 | 2407 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2408 | | { |
| | 390 | 2409 | | return (int)(offset); |
| | | 2410 | | } |
| | | 2411 | | |
| | 567 | 2412 | | offset += 1; |
| | | 2413 | | } |
| | | 2414 | | |
| | 1637 | 2415 | | return -1; |
| | | 2416 | | } |
| | 2514 | 2417 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 2418 | | { |
| | 6936 | 2419 | | Vector512<TValue> equals, current, values0 = Vector512.Create(value0), values1 = Vector512.Create(value1 |
| | 1734 | 2420 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 1734 | 2421 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector512<TValue>.Count); |
| | | 2422 | | |
| | | 2423 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2424 | | do |
| | | 2425 | | { |
| | 6465 | 2426 | | current = Vector512.LoadUnsafe(ref currentSearchSpace); |
| | 6465 | 2427 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(values0, current) | Vector512.Equals(values1, curr |
| | 6465 | 2428 | | | Vector512.Equals(values2, current) | Vector512.Equals(values3, current)); |
| | 6465 | 2429 | | if (equals == Vector512<TValue>.Zero) |
| | | 2430 | | { |
| | 5181 | 2431 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector512<TValue>.Count); |
| | 5181 | 2432 | | continue; |
| | | 2433 | | } |
| | | 2434 | | |
| | 1284 | 2435 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2436 | | } |
| | 5181 | 2437 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2438 | | |
| | | 2439 | | // If any elements remain, process the last vector in the search space. |
| | 450 | 2440 | | if ((uint)length % Vector512<TValue>.Count != 0) |
| | | 2441 | | { |
| | 408 | 2442 | | current = Vector512.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 408 | 2443 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(values0, current) | Vector512.Equals(values1, curr |
| | 408 | 2444 | | | Vector512.Equals(values2, current) | Vector512.Equals(values3, current)); |
| | 408 | 2445 | | if (equals != Vector512<TValue>.Zero) |
| | | 2446 | | { |
| | 51 | 2447 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2448 | | } |
| | | 2449 | | } |
| | | 2450 | | } |
| | 780 | 2451 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 2452 | | { |
| | 1320 | 2453 | | Vector256<TValue> equals, current, values0 = Vector256.Create(value0), values1 = Vector256.Create(value1 |
| | 330 | 2454 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 330 | 2455 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector256<TValue>.Count); |
| | | 2456 | | |
| | | 2457 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2458 | | do |
| | | 2459 | | { |
| | 330 | 2460 | | current = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | 330 | 2461 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values0, current) | Vector256.Equals(values1, curr |
| | 330 | 2462 | | | Vector256.Equals(values2, current) | Vector256.Equals(values3, current)); |
| | 330 | 2463 | | if (equals == Vector256<TValue>.Zero) |
| | | 2464 | | { |
| | 72 | 2465 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector256<TValue>.Count); |
| | 72 | 2466 | | continue; |
| | | 2467 | | } |
| | | 2468 | | |
| | 258 | 2469 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2470 | | } |
| | 72 | 2471 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2472 | | |
| | | 2473 | | // If any elements remain, process the last vector in the search space. |
| | 72 | 2474 | | if ((uint)length % Vector256<TValue>.Count != 0) |
| | | 2475 | | { |
| | 69 | 2476 | | current = Vector256.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 69 | 2477 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values0, current) | Vector256.Equals(values1, curr |
| | 69 | 2478 | | | Vector256.Equals(values2, current) | Vector256.Equals(values3, current)); |
| | 69 | 2479 | | if (equals != Vector256<TValue>.Zero) |
| | | 2480 | | { |
| | 24 | 2481 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2482 | | } |
| | | 2483 | | } |
| | | 2484 | | } |
| | | 2485 | | else |
| | | 2486 | | { |
| | 1800 | 2487 | | Vector128<TValue> equals, current, values0 = Vector128.Create(value0), values1 = Vector128.Create(value1 |
| | 450 | 2488 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 450 | 2489 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, length - Vector128<TValue>.Count); |
| | | 2490 | | |
| | | 2491 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2492 | | do |
| | | 2493 | | { |
| | 450 | 2494 | | current = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | 450 | 2495 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values0, current) | Vector128.Equals(values1, curr |
| | 450 | 2496 | | | Vector128.Equals(values2, current) | Vector128.Equals(values3, current)); |
| | 450 | 2497 | | if (equals == Vector128<TValue>.Zero) |
| | | 2498 | | { |
| | 174 | 2499 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector128<TValue>.Count); |
| | 174 | 2500 | | continue; |
| | | 2501 | | } |
| | | 2502 | | |
| | 276 | 2503 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2504 | | } |
| | 174 | 2505 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2506 | | |
| | | 2507 | | // If any elements remain, process the first vector in the search space. |
| | 174 | 2508 | | if ((uint)length % Vector128<TValue>.Count != 0) |
| | | 2509 | | { |
| | 135 | 2510 | | current = Vector128.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 135 | 2511 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values0, current) | Vector128.Equals(values1, curr |
| | 135 | 2512 | | | Vector128.Equals(values2, current) | Vector128.Equals(values3, current)); |
| | 135 | 2513 | | if (equals != Vector128<TValue>.Zero) |
| | | 2514 | | { |
| | 24 | 2515 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2516 | | } |
| | | 2517 | | } |
| | | 2518 | | } |
| | | 2519 | | |
| | 597 | 2520 | | return -1; |
| | | 2521 | | } |
| | | 2522 | | |
| | | 2523 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2524 | | internal static int IndexOfAnyValueType<T>(ref T searchSpace, T value0, T value1, T value2, T value3, T value4, |
| | 4572 | 2525 | | => IndexOfAnyValueType<T, DontNegate<T>>(ref searchSpace, value0, value1, value2, value3, value4, length); |
| | | 2526 | | |
| | | 2527 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2528 | | internal static int IndexOfAnyExceptValueType<T>(ref T searchSpace, T value0, T value1, T value2, T value3, T va |
| | 4572 | 2529 | | => IndexOfAnyValueType<T, Negate<T>>(ref searchSpace, value0, value1, value2, value3, value4, length); |
| | | 2530 | | |
| | | 2531 | | private static int IndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue value1, T |
| | | 2532 | | where TValue : struct, INumber<TValue> |
| | | 2533 | | where TNegator : struct, INegator<TValue> |
| | | 2534 | | { |
| | 9144 | 2535 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 9144 | 2536 | | Debug.Assert(value0 is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 2537 | | |
| | 9144 | 2538 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 2539 | | { |
| | 5454 | 2540 | | nuint offset = 0; |
| | | 2541 | | TValue lookUp; |
| | | 2542 | | |
| | 7629 | 2543 | | while (length >= 4) |
| | | 2544 | | { |
| | 5202 | 2545 | | length -= 4; |
| | | 2546 | | |
| | 5202 | 2547 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 5202 | 2548 | | lookUp = current; |
| | 5202 | 2549 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2550 | | { |
| | 2337 | 2551 | | return (int)(offset); |
| | | 2552 | | } |
| | | 2553 | | |
| | 2865 | 2554 | | lookUp = Unsafe.Add(ref current, 1); |
| | 2865 | 2555 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2556 | | { |
| | 321 | 2557 | | return (int)(offset + 1); |
| | | 2558 | | } |
| | | 2559 | | |
| | 2544 | 2560 | | lookUp = Unsafe.Add(ref current, 2); |
| | 2544 | 2561 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2562 | | { |
| | 201 | 2563 | | return (int)(offset + 2); |
| | | 2564 | | } |
| | | 2565 | | |
| | 2343 | 2566 | | lookUp = Unsafe.Add(ref current, 3); |
| | 2343 | 2567 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2568 | | { |
| | 168 | 2569 | | return (int)(offset + 3); |
| | | 2570 | | } |
| | | 2571 | | |
| | 2175 | 2572 | | offset += 4; |
| | | 2573 | | } |
| | | 2574 | | |
| | 4245 | 2575 | | while (length > 0) |
| | | 2576 | | { |
| | 2232 | 2577 | | length -= 1; |
| | | 2578 | | |
| | 2232 | 2579 | | lookUp = Unsafe.Add(ref searchSpace, offset); |
| | 2232 | 2580 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 2581 | | { |
| | 414 | 2582 | | return (int)(offset); |
| | | 2583 | | } |
| | | 2584 | | |
| | 1818 | 2585 | | offset += 1; |
| | | 2586 | | } |
| | | 2587 | | |
| | 2013 | 2588 | | return -1; |
| | | 2589 | | } |
| | 3690 | 2590 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 2591 | | { |
| | 5256 | 2592 | | Vector512<TValue> equals, current, values0 = Vector512.Create(value0), values1 = Vector512.Create(value1 |
| | 7884 | 2593 | | values2 = Vector512.Create(value2), values3 = Vector512.Create(value3), values4 = Vector512.Create(v |
| | 2628 | 2594 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 2628 | 2595 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector512<TValue>.Coun |
| | | 2596 | | |
| | | 2597 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2598 | | do |
| | | 2599 | | { |
| | 6714 | 2600 | | current = Vector512.LoadUnsafe(ref currentSearchSpace); |
| | 6714 | 2601 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(values0, current) | Vector512.Equals(values1, curr |
| | 6714 | 2602 | | | Vector512.Equals(values3, current) | Vector512.Equals(values4, current)); |
| | 6714 | 2603 | | if (equals == Vector512<TValue>.Zero) |
| | | 2604 | | { |
| | 4593 | 2605 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector512<TValue>.Count); |
| | 4593 | 2606 | | continue; |
| | | 2607 | | } |
| | | 2608 | | |
| | 2121 | 2609 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2610 | | } |
| | 4593 | 2611 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2612 | | |
| | | 2613 | | // If any elements remain, process the last vector in the search space. |
| | 507 | 2614 | | if ((uint)length % Vector512<TValue>.Count != 0) |
| | | 2615 | | { |
| | 441 | 2616 | | current = Vector512.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 441 | 2617 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(values0, current) | Vector512.Equals(values1, curr |
| | 441 | 2618 | | | Vector512.Equals(values3, current) | Vector512.Equals(values4, current)); |
| | 441 | 2619 | | if (equals != Vector512<TValue>.Zero) |
| | | 2620 | | { |
| | 105 | 2621 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2622 | | } |
| | | 2623 | | } |
| | | 2624 | | } |
| | 1062 | 2625 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 2626 | | { |
| | 1128 | 2627 | | Vector256<TValue> equals, current, values0 = Vector256.Create(value0), values1 = Vector256.Create(value1 |
| | 1692 | 2628 | | values2 = Vector256.Create(value2), values3 = Vector256.Create(value3), values4 = Vector256.Create(v |
| | 564 | 2629 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 564 | 2630 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector256<TValue>.Coun |
| | | 2631 | | |
| | | 2632 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2633 | | do |
| | | 2634 | | { |
| | 564 | 2635 | | current = Vector256.LoadUnsafe(ref currentSearchSpace); |
| | 564 | 2636 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values0, current) | Vector256.Equals(values1, curr |
| | 564 | 2637 | | | Vector256.Equals(values3, current) | Vector256.Equals(values4, current)); |
| | 564 | 2638 | | if (equals == Vector256<TValue>.Zero) |
| | | 2639 | | { |
| | 117 | 2640 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector256<TValue>.Count); |
| | 117 | 2641 | | continue; |
| | | 2642 | | } |
| | | 2643 | | |
| | 447 | 2644 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2645 | | } |
| | 117 | 2646 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2647 | | |
| | | 2648 | | // If any elements remain, process the last vector in the search space. |
| | 117 | 2649 | | if ((uint)length % Vector256<TValue>.Count != 0) |
| | | 2650 | | { |
| | 105 | 2651 | | current = Vector256.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 105 | 2652 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(values0, current) | Vector256.Equals(values1, curr |
| | 105 | 2653 | | | Vector256.Equals(values3, current) | Vector256.Equals(values4, current)); |
| | 105 | 2654 | | if (equals != Vector256<TValue>.Zero) |
| | | 2655 | | { |
| | 54 | 2656 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2657 | | } |
| | | 2658 | | } |
| | | 2659 | | } |
| | | 2660 | | else |
| | | 2661 | | { |
| | 996 | 2662 | | Vector128<TValue> equals, current, values0 = Vector128.Create(value0), values1 = Vector128.Create(value1 |
| | 1494 | 2663 | | values2 = Vector128.Create(value2), values3 = Vector128.Create(value3), values4 = Vector128.Create(v |
| | 498 | 2664 | | ref TValue currentSearchSpace = ref searchSpace; |
| | 498 | 2665 | | ref TValue oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector128<TValue>.Coun |
| | | 2666 | | |
| | | 2667 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 2668 | | do |
| | | 2669 | | { |
| | 498 | 2670 | | current = Vector128.LoadUnsafe(ref currentSearchSpace); |
| | 498 | 2671 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values0, current) | Vector128.Equals(values1, curr |
| | 498 | 2672 | | | Vector128.Equals(values3, current) | Vector128.Equals(values4, current)); |
| | 498 | 2673 | | if (equals == Vector128<TValue>.Zero) |
| | | 2674 | | { |
| | 144 | 2675 | | currentSearchSpace = ref Unsafe.Add(ref currentSearchSpace, Vector128<TValue>.Count); |
| | 144 | 2676 | | continue; |
| | | 2677 | | } |
| | | 2678 | | |
| | 354 | 2679 | | return ComputeFirstIndex(ref searchSpace, ref currentSearchSpace, equals); |
| | | 2680 | | } |
| | 144 | 2681 | | while (Unsafe.IsAddressLessThanOrEqualTo(ref currentSearchSpace, ref oneVectorAwayFromEnd)); |
| | | 2682 | | |
| | | 2683 | | // If any elements remain, process the first vector in the search space. |
| | 144 | 2684 | | if ((uint)length % Vector128<TValue>.Count != 0) |
| | | 2685 | | { |
| | 111 | 2686 | | current = Vector128.LoadUnsafe(ref oneVectorAwayFromEnd); |
| | 111 | 2687 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(values0, current) | Vector128.Equals(values1, curr |
| | 111 | 2688 | | | Vector128.Equals(values3, current) | Vector128.Equals(values4, current)); |
| | 111 | 2689 | | if (equals != Vector128<TValue>.Zero) |
| | | 2690 | | { |
| | 42 | 2691 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, equals); |
| | | 2692 | | } |
| | | 2693 | | } |
| | | 2694 | | } |
| | | 2695 | | |
| | 567 | 2696 | | return -1; |
| | | 2697 | | } |
| | | 2698 | | |
| | | 2699 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2700 | | internal static int LastIndexOfValueType<T>(ref T searchSpace, T value, int length) where T : struct, INumber<T> |
| | 3046 | 2701 | | => LastIndexOfValueType<T, DontNegate<T>>(ref searchSpace, value, length); |
| | | 2702 | | |
| | | 2703 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2704 | | internal static int LastIndexOfAnyExceptValueType<T>(ref T searchSpace, T value, int length) where T : struct, I |
| | 2888 | 2705 | | => LastIndexOfValueType<T, Negate<T>>(ref searchSpace, value, length); |
| | | 2706 | | |
| | | 2707 | | private static int LastIndexOfValueType<TValue, TNegator>(ref TValue searchSpace, TValue value, int length) |
| | | 2708 | | where TValue : struct, INumber<TValue> |
| | | 2709 | | where TNegator : struct, INegator<TValue> |
| | | 2710 | | { |
| | 5934 | 2711 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 5934 | 2712 | | Debug.Assert(value is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 2713 | | |
| | 5934 | 2714 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 2715 | | { |
| | 2978 | 2716 | | nuint offset = (nuint)length - 1; |
| | | 2717 | | |
| | 3004 | 2718 | | while (length >= 8) |
| | | 2719 | | { |
| | 388 | 2720 | | length -= 8; |
| | | 2721 | | |
| | 388 | 2722 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset) == value)) |
| | | 2723 | | { |
| | 194 | 2724 | | return (int)(offset); |
| | | 2725 | | } |
| | 194 | 2726 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 1) == value)) |
| | | 2727 | | { |
| | 50 | 2728 | | return (int)(offset - 1); |
| | | 2729 | | } |
| | 144 | 2730 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 2) == value)) |
| | | 2731 | | { |
| | 22 | 2732 | | return (int)(offset - 2); |
| | | 2733 | | } |
| | 122 | 2734 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 3) == value)) |
| | | 2735 | | { |
| | 18 | 2736 | | return (int)(offset - 3); |
| | | 2737 | | } |
| | 104 | 2738 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 4) == value)) |
| | | 2739 | | { |
| | 26 | 2740 | | return (int)(offset - 4); |
| | | 2741 | | } |
| | 78 | 2742 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 5) == value)) |
| | | 2743 | | { |
| | 22 | 2744 | | return (int)(offset - 5); |
| | | 2745 | | } |
| | 56 | 2746 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 6) == value)) |
| | | 2747 | | { |
| | 12 | 2748 | | return (int)(offset - 6); |
| | | 2749 | | } |
| | 44 | 2750 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 7) == value)) |
| | | 2751 | | { |
| | 18 | 2752 | | return (int)(offset - 7); |
| | | 2753 | | } |
| | | 2754 | | |
| | 26 | 2755 | | offset -= 8; |
| | | 2756 | | } |
| | | 2757 | | |
| | 2616 | 2758 | | if (length >= 4) |
| | | 2759 | | { |
| | 1166 | 2760 | | length -= 4; |
| | | 2761 | | |
| | 1166 | 2762 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset) == value)) |
| | | 2763 | | { |
| | 574 | 2764 | | return (int)(offset); |
| | | 2765 | | } |
| | 592 | 2766 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 1) == value)) |
| | | 2767 | | { |
| | 86 | 2768 | | return (int)(offset - 1); |
| | | 2769 | | } |
| | 506 | 2770 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 2) == value)) |
| | | 2771 | | { |
| | 62 | 2772 | | return (int)(offset - 2); |
| | | 2773 | | } |
| | 444 | 2774 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset - 3) == value)) |
| | | 2775 | | { |
| | 46 | 2776 | | return (int)(offset - 3); |
| | | 2777 | | } |
| | | 2778 | | |
| | 398 | 2779 | | offset -= 4; |
| | | 2780 | | } |
| | | 2781 | | |
| | 3218 | 2782 | | while (length > 0) |
| | | 2783 | | { |
| | 1974 | 2784 | | length -= 1; |
| | | 2785 | | |
| | 1974 | 2786 | | if (TNegator.NegateIfNeeded(Unsafe.Add(ref searchSpace, offset) == value)) |
| | | 2787 | | { |
| | 604 | 2788 | | return (int)(offset); |
| | | 2789 | | } |
| | | 2790 | | |
| | 1370 | 2791 | | offset -= 1; |
| | | 2792 | | } |
| | | 2793 | | |
| | 1244 | 2794 | | return -1; |
| | | 2795 | | } |
| | 2956 | 2796 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 2797 | | { |
| | 1961 | 2798 | | return SimdImpl<Vector512<TValue>>(ref searchSpace, value, length); |
| | | 2799 | | } |
| | 995 | 2800 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 2801 | | { |
| | 503 | 2802 | | return SimdImpl<Vector256<TValue>>(ref searchSpace, value, length); |
| | | 2803 | | } |
| | | 2804 | | else |
| | | 2805 | | { |
| | 492 | 2806 | | return SimdImpl<Vector128<TValue>>(ref searchSpace, value, length); |
| | | 2807 | | } |
| | | 2808 | | |
| | | 2809 | | static int SimdImpl<TVector>(ref TValue searchSpace, TValue value, int length) |
| | | 2810 | | where TVector : struct, ISimdVector<TVector, TValue> |
| | | 2811 | | { |
| | | 2812 | | TVector current; |
| | 2956 | 2813 | | TVector values = TVector.Create(value); |
| | | 2814 | | |
| | 2956 | 2815 | | int offset = length - TVector.ElementCount; |
| | | 2816 | | |
| | | 2817 | | // Loop until either we've finished all elements -or- there's one or less than a vector's-worth remainin |
| | 10309 | 2818 | | while (offset > 0) |
| | | 2819 | | { |
| | 8857 | 2820 | | current = TVector.LoadUnsafe(ref searchSpace, (uint)(offset)); |
| | | 2821 | | |
| | 8857 | 2822 | | if (TNegator.HasMatch(values, current)) |
| | | 2823 | | { |
| | 1504 | 2824 | | return offset + TVector.LastIndexOfWhereAllBitsSet(TNegator.GetMatchMask(values, current)); |
| | | 2825 | | } |
| | | 2826 | | |
| | 7353 | 2827 | | offset -= TVector.ElementCount; |
| | | 2828 | | } |
| | | 2829 | | |
| | | 2830 | | // Process the first vector in the search space. |
| | | 2831 | | |
| | 1452 | 2832 | | current = TVector.LoadUnsafe(ref searchSpace); |
| | | 2833 | | |
| | 1452 | 2834 | | if (TNegator.HasMatch(values, current)) |
| | | 2835 | | { |
| | 361 | 2836 | | return TVector.LastIndexOfWhereAllBitsSet(TNegator.GetMatchMask(values, current)); |
| | | 2837 | | } |
| | | 2838 | | |
| | 1091 | 2839 | | return -1; |
| | | 2840 | | } |
| | | 2841 | | } |
| | | 2842 | | |
| | | 2843 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2844 | | internal static int LastIndexOfAnyValueType<T>(ref T searchSpace, T value0, T value1, int length) where T : stru |
| | 4509 | 2845 | | => LastIndexOfAnyValueType<T, DontNegate<T>>(ref searchSpace, value0, value1, length); |
| | | 2846 | | |
| | | 2847 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 2848 | | internal static int LastIndexOfAnyExceptValueType<T>(ref T searchSpace, T value0, T value1, int length) where T |
| | 4508 | 2849 | | => LastIndexOfAnyValueType<T, Negate<T>>(ref searchSpace, value0, value1, length); |
| | | 2850 | | |
| | | 2851 | | private static int LastIndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue value |
| | | 2852 | | where TValue : struct, INumber<TValue> |
| | | 2853 | | where TNegator : struct, INegator<TValue> |
| | | 2854 | | { |
| | 9017 | 2855 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 9017 | 2856 | | Debug.Assert(value0 is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 2857 | | |
| | 9017 | 2858 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 2859 | | { |
| | 4160 | 2860 | | nuint offset = (nuint)length - 1; |
| | | 2861 | | TValue lookUp; |
| | | 2862 | | |
| | 4160 | 2863 | | if (typeof(TValue) == typeof(byte)) // this optimization is beneficial only to byte |
| | | 2864 | | { |
| | 838 | 2865 | | while (length >= 8) |
| | | 2866 | | { |
| | 456 | 2867 | | length -= 8; |
| | | 2868 | | |
| | 456 | 2869 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 456 | 2870 | | lookUp = current; |
| | 456 | 2871 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2872 | | { |
| | 228 | 2873 | | return (int)(offset); |
| | | 2874 | | } |
| | | 2875 | | |
| | 228 | 2876 | | lookUp = Unsafe.Add(ref current, -1); |
| | 228 | 2877 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2878 | | { |
| | 66 | 2879 | | return (int)(offset - 1); |
| | | 2880 | | } |
| | | 2881 | | |
| | 162 | 2882 | | lookUp = Unsafe.Add(ref current, -2); |
| | 162 | 2883 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2884 | | { |
| | 34 | 2885 | | return (int)(offset - 2); |
| | | 2886 | | } |
| | | 2887 | | |
| | 128 | 2888 | | lookUp = Unsafe.Add(ref current, -3); |
| | 128 | 2889 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2890 | | { |
| | 14 | 2891 | | return (int)(offset - 3); |
| | | 2892 | | } |
| | | 2893 | | |
| | 114 | 2894 | | lookUp = Unsafe.Add(ref current, -4); |
| | 114 | 2895 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2896 | | { |
| | 18 | 2897 | | return (int)(offset - 4); |
| | | 2898 | | } |
| | | 2899 | | |
| | 96 | 2900 | | lookUp = Unsafe.Add(ref current, -5); |
| | 96 | 2901 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2902 | | { |
| | 12 | 2903 | | return (int)(offset - 5); |
| | | 2904 | | } |
| | | 2905 | | |
| | 84 | 2906 | | lookUp = Unsafe.Add(ref current, -6); |
| | 84 | 2907 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2908 | | { |
| | 20 | 2909 | | return (int)(offset - 6); |
| | | 2910 | | } |
| | | 2911 | | |
| | 64 | 2912 | | lookUp = Unsafe.Add(ref current, -7); |
| | 64 | 2913 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2914 | | { |
| | 22 | 2915 | | return (int)(offset - 7); |
| | | 2916 | | } |
| | | 2917 | | |
| | 42 | 2918 | | offset -= 8; |
| | | 2919 | | } |
| | | 2920 | | } |
| | | 2921 | | |
| | 4144 | 2922 | | while (length >= 4) |
| | | 2923 | | { |
| | 1458 | 2924 | | length -= 4; |
| | | 2925 | | |
| | 1458 | 2926 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 1458 | 2927 | | lookUp = current; |
| | 1458 | 2928 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2929 | | { |
| | 724 | 2930 | | return (int)(offset); |
| | | 2931 | | } |
| | | 2932 | | |
| | 734 | 2933 | | lookUp = Unsafe.Add(ref current, -1); |
| | 734 | 2934 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2935 | | { |
| | 134 | 2936 | | return (int)(offset - 1); |
| | | 2937 | | } |
| | | 2938 | | |
| | 600 | 2939 | | lookUp = Unsafe.Add(ref current, -2); |
| | 600 | 2940 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2941 | | { |
| | 120 | 2942 | | return (int)(offset - 2); |
| | | 2943 | | } |
| | | 2944 | | |
| | 480 | 2945 | | lookUp = Unsafe.Add(ref current, -3); |
| | 480 | 2946 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2947 | | { |
| | 82 | 2948 | | return (int)(offset - 3); |
| | | 2949 | | } |
| | | 2950 | | |
| | 398 | 2951 | | offset -= 4; |
| | | 2952 | | } |
| | | 2953 | | |
| | 4528 | 2954 | | while (length > 0) |
| | | 2955 | | { |
| | 2838 | 2956 | | length -= 1; |
| | | 2957 | | |
| | 2838 | 2958 | | lookUp = Unsafe.Add(ref searchSpace, offset); |
| | 2838 | 2959 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1)) |
| | | 2960 | | { |
| | 996 | 2961 | | return (int)(offset); |
| | | 2962 | | } |
| | | 2963 | | |
| | 1842 | 2964 | | offset -= 1; |
| | | 2965 | | } |
| | | 2966 | | |
| | 1690 | 2967 | | return -1; |
| | | 2968 | | } |
| | 4857 | 2969 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 2970 | | { |
| | 7018 | 2971 | | Vector512<TValue> equals, current, values0 = Vector512.Create(value0), values1 = Vector512.Create(value1 |
| | 3509 | 2972 | | nint offset = length - Vector512<TValue>.Count; |
| | | 2973 | | |
| | | 2974 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 14616 | 2975 | | while (offset > 0) |
| | | 2976 | | { |
| | 13288 | 2977 | | current = Vector512.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 13288 | 2978 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(current, values0) | Vector512.Equals(current, valu |
| | | 2979 | | |
| | 13288 | 2980 | | if (equals == Vector512<TValue>.Zero) |
| | | 2981 | | { |
| | 11107 | 2982 | | offset -= Vector512<TValue>.Count; |
| | 11107 | 2983 | | continue; |
| | | 2984 | | } |
| | | 2985 | | |
| | 2181 | 2986 | | return ComputeLastIndex(offset, equals); |
| | | 2987 | | } |
| | | 2988 | | |
| | | 2989 | | // Process the first vector in the search space. |
| | | 2990 | | |
| | 1328 | 2991 | | current = Vector512.LoadUnsafe(ref searchSpace); |
| | 1328 | 2992 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(current, values0) | Vector512.Equals(current, values1) |
| | | 2993 | | |
| | 1328 | 2994 | | if (equals != Vector512<TValue>.Zero) |
| | | 2995 | | { |
| | 232 | 2996 | | return ComputeLastIndex(offset: 0, equals); |
| | | 2997 | | } |
| | | 2998 | | } |
| | 1348 | 2999 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 3000 | | { |
| | 1304 | 3001 | | Vector256<TValue> equals, current, values0 = Vector256.Create(value0), values1 = Vector256.Create(value1 |
| | 652 | 3002 | | nint offset = length - Vector256<TValue>.Count; |
| | | 3003 | | |
| | | 3004 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 786 | 3005 | | while (offset > 0) |
| | | 3006 | | { |
| | 428 | 3007 | | current = Vector256.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 428 | 3008 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(current, values0) | Vector256.Equals(current, valu |
| | | 3009 | | |
| | 428 | 3010 | | if (equals == Vector256<TValue>.Zero) |
| | | 3011 | | { |
| | 134 | 3012 | | offset -= Vector256<TValue>.Count; |
| | 134 | 3013 | | continue; |
| | | 3014 | | } |
| | | 3015 | | |
| | 294 | 3016 | | return ComputeLastIndex(offset, equals); |
| | | 3017 | | } |
| | | 3018 | | |
| | | 3019 | | // Process the first vector in the search space. |
| | | 3020 | | |
| | 358 | 3021 | | current = Vector256.LoadUnsafe(ref searchSpace); |
| | 358 | 3022 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(current, values0) | Vector256.Equals(current, values1) |
| | | 3023 | | |
| | 358 | 3024 | | if (equals != Vector256<TValue>.Zero) |
| | | 3025 | | { |
| | 172 | 3026 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3027 | | } |
| | | 3028 | | } |
| | | 3029 | | else |
| | | 3030 | | { |
| | 1392 | 3031 | | Vector128<TValue> equals, current, values0 = Vector128.Create(value0), values1 = Vector128.Create(value1 |
| | 696 | 3032 | | nint offset = length - Vector128<TValue>.Count; |
| | | 3033 | | |
| | | 3034 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 812 | 3035 | | while (offset > 0) |
| | | 3036 | | { |
| | 364 | 3037 | | current = Vector128.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 364 | 3038 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(current, values0) | Vector128.Equals(current, valu |
| | 364 | 3039 | | if (equals == Vector128<TValue>.Zero) |
| | | 3040 | | { |
| | 116 | 3041 | | offset -= Vector128<TValue>.Count; |
| | 116 | 3042 | | continue; |
| | | 3043 | | } |
| | | 3044 | | |
| | 248 | 3045 | | return ComputeLastIndex(offset, equals); |
| | | 3046 | | } |
| | | 3047 | | |
| | | 3048 | | // Process the first vector in the search space. |
| | 448 | 3049 | | current = Vector128.LoadUnsafe(ref searchSpace); |
| | 448 | 3050 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(current, values0) | Vector128.Equals(current, values1) |
| | 448 | 3051 | | if (equals != Vector128<TValue>.Zero) |
| | | 3052 | | { |
| | 208 | 3053 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3054 | | } |
| | | 3055 | | } |
| | | 3056 | | |
| | 1522 | 3057 | | return -1; |
| | | 3058 | | } |
| | | 3059 | | |
| | | 3060 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3061 | | internal static int LastIndexOfAnyValueType<T>(ref T searchSpace, T value0, T value1, T value2, int length) wher |
| | 2666 | 3062 | | => LastIndexOfAnyValueType<T, DontNegate<T>>(ref searchSpace, value0, value1, value2, length); |
| | | 3063 | | |
| | | 3064 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3065 | | internal static int LastIndexOfAnyExceptValueType<T>(ref T searchSpace, T value0, T value1, T value2, int length |
| | 2666 | 3066 | | => LastIndexOfAnyValueType<T, Negate<T>>(ref searchSpace, value0, value1, value2, length); |
| | | 3067 | | |
| | | 3068 | | private static int LastIndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue value |
| | | 3069 | | where TValue : struct, INumber<TValue> |
| | | 3070 | | where TNegator : struct, INegator<TValue> |
| | | 3071 | | { |
| | 5332 | 3072 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 5332 | 3073 | | Debug.Assert(value0 is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 3074 | | |
| | 5332 | 3075 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 3076 | | { |
| | 2208 | 3077 | | nuint offset = (nuint)length - 1; |
| | | 3078 | | TValue lookUp; |
| | | 3079 | | |
| | 2208 | 3080 | | if (typeof(TValue) == typeof(byte)) // this optimization is beneficial only to byte |
| | | 3081 | | { |
| | 1136 | 3082 | | while (length >= 8) |
| | | 3083 | | { |
| | 616 | 3084 | | length -= 8; |
| | | 3085 | | |
| | 616 | 3086 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 616 | 3087 | | lookUp = current; |
| | 616 | 3088 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3089 | | { |
| | 308 | 3090 | | return (int)(offset); |
| | | 3091 | | } |
| | | 3092 | | |
| | 308 | 3093 | | lookUp = Unsafe.Add(ref current, -1); |
| | 308 | 3094 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3095 | | { |
| | 60 | 3096 | | return (int)(offset - 1); |
| | | 3097 | | } |
| | | 3098 | | |
| | 248 | 3099 | | lookUp = Unsafe.Add(ref current, -2); |
| | 248 | 3100 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3101 | | { |
| | 50 | 3102 | | return (int)(offset - 2); |
| | | 3103 | | } |
| | | 3104 | | |
| | 198 | 3105 | | lookUp = Unsafe.Add(ref current, -3); |
| | 198 | 3106 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3107 | | { |
| | 26 | 3108 | | return (int)(offset - 3); |
| | | 3109 | | } |
| | | 3110 | | |
| | 172 | 3111 | | lookUp = Unsafe.Add(ref current, -4); |
| | 172 | 3112 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3113 | | { |
| | 36 | 3114 | | return (int)(offset - 4); |
| | | 3115 | | } |
| | | 3116 | | |
| | 136 | 3117 | | lookUp = Unsafe.Add(ref current, -5); |
| | 136 | 3118 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3119 | | { |
| | 28 | 3120 | | return (int)(offset - 5); |
| | | 3121 | | } |
| | | 3122 | | |
| | 108 | 3123 | | lookUp = Unsafe.Add(ref current, -6); |
| | 108 | 3124 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3125 | | { |
| | 26 | 3126 | | return (int)(offset - 6); |
| | | 3127 | | } |
| | | 3128 | | |
| | 82 | 3129 | | lookUp = Unsafe.Add(ref current, -7); |
| | 82 | 3130 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3131 | | { |
| | 38 | 3132 | | return (int)(offset - 7); |
| | | 3133 | | } |
| | | 3134 | | |
| | 44 | 3135 | | offset -= 8; |
| | | 3136 | | } |
| | | 3137 | | } |
| | | 3138 | | |
| | 1782 | 3139 | | while (length >= 4) |
| | | 3140 | | { |
| | 754 | 3141 | | length -= 4; |
| | | 3142 | | |
| | 754 | 3143 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 754 | 3144 | | lookUp = current; |
| | 754 | 3145 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3146 | | { |
| | 368 | 3147 | | return (int)(offset); |
| | | 3148 | | } |
| | | 3149 | | |
| | 386 | 3150 | | lookUp = Unsafe.Add(ref current, -1); |
| | 386 | 3151 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3152 | | { |
| | 120 | 3153 | | return (int)(offset - 1); |
| | | 3154 | | } |
| | | 3155 | | |
| | 266 | 3156 | | lookUp = Unsafe.Add(ref current, -2); |
| | 266 | 3157 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3158 | | { |
| | 74 | 3159 | | return (int)(offset - 2); |
| | | 3160 | | } |
| | | 3161 | | |
| | 192 | 3162 | | lookUp = Unsafe.Add(ref current, -3); |
| | 192 | 3163 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3164 | | { |
| | 46 | 3165 | | return (int)(offset - 3); |
| | | 3166 | | } |
| | | 3167 | | |
| | 146 | 3168 | | offset -= 4; |
| | | 3169 | | } |
| | | 3170 | | |
| | 1606 | 3171 | | while (length > 0) |
| | | 3172 | | { |
| | 948 | 3173 | | length -= 1; |
| | | 3174 | | |
| | 948 | 3175 | | lookUp = Unsafe.Add(ref searchSpace, offset); |
| | 948 | 3176 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2)) |
| | | 3177 | | { |
| | 370 | 3178 | | return (int)(offset); |
| | | 3179 | | } |
| | | 3180 | | |
| | 578 | 3181 | | offset -= 1; |
| | | 3182 | | } |
| | | 3183 | | |
| | 658 | 3184 | | return -1; |
| | | 3185 | | } |
| | 3124 | 3186 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 3187 | | { |
| | 6528 | 3188 | | Vector512<TValue> equals, current, values0 = Vector512.Create(value0), values1 = Vector512.Create(value1 |
| | 2176 | 3189 | | nint offset = length - Vector512<TValue>.Count; |
| | | 3190 | | |
| | | 3191 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 7676 | 3192 | | while (offset > 0) |
| | | 3193 | | { |
| | 7006 | 3194 | | current = Vector512.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 7006 | 3195 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(current, values0) | Vector512.Equals(current, valu |
| | | 3196 | | |
| | 7006 | 3197 | | if (equals == Vector512<TValue>.Zero) |
| | | 3198 | | { |
| | 5500 | 3199 | | offset -= Vector512<TValue>.Count; |
| | 5500 | 3200 | | continue; |
| | | 3201 | | } |
| | | 3202 | | |
| | 1506 | 3203 | | return ComputeLastIndex(offset, equals); |
| | | 3204 | | } |
| | | 3205 | | |
| | | 3206 | | // Process the first vector in the search space. |
| | 670 | 3207 | | current = Vector512.LoadUnsafe(ref searchSpace); |
| | 670 | 3208 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(current, values0) | Vector512.Equals(current, values1) |
| | | 3209 | | |
| | 670 | 3210 | | if (equals != Vector512<TValue>.Zero) |
| | | 3211 | | { |
| | 138 | 3212 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3213 | | } |
| | | 3214 | | } |
| | 948 | 3215 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 3216 | | { |
| | 1428 | 3217 | | Vector256<TValue> equals, current, values0 = Vector256.Create(value0), values1 = Vector256.Create(value1 |
| | 476 | 3218 | | nint offset = length - Vector256<TValue>.Count; |
| | | 3219 | | |
| | | 3220 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 582 | 3221 | | while (offset > 0) |
| | | 3222 | | { |
| | 364 | 3223 | | current = Vector256.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 364 | 3224 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(current, values0) | Vector256.Equals(current, valu |
| | | 3225 | | |
| | 364 | 3226 | | if (equals == Vector256<TValue>.Zero) |
| | | 3227 | | { |
| | 106 | 3228 | | offset -= Vector256<TValue>.Count; |
| | 106 | 3229 | | continue; |
| | | 3230 | | } |
| | | 3231 | | |
| | 258 | 3232 | | return ComputeLastIndex(offset, equals); |
| | | 3233 | | } |
| | | 3234 | | |
| | | 3235 | | // Process the first vector in the search space. |
| | 218 | 3236 | | current = Vector256.LoadUnsafe(ref searchSpace); |
| | 218 | 3237 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(current, values0) | Vector256.Equals(current, values1) |
| | | 3238 | | |
| | 218 | 3239 | | if (equals != Vector256<TValue>.Zero) |
| | | 3240 | | { |
| | 98 | 3241 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3242 | | } |
| | | 3243 | | } |
| | | 3244 | | else |
| | | 3245 | | { |
| | 1416 | 3246 | | Vector128<TValue> equals, current, values0 = Vector128.Create(value0), values1 = Vector128.Create(value1 |
| | 472 | 3247 | | nint offset = length - Vector128<TValue>.Count; |
| | | 3248 | | |
| | | 3249 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 526 | 3250 | | while (offset > 0) |
| | | 3251 | | { |
| | 240 | 3252 | | current = Vector128.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 240 | 3253 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(current, values0) | Vector128.Equals(current, valu |
| | | 3254 | | |
| | 240 | 3255 | | if (equals == Vector128<TValue>.Zero) |
| | | 3256 | | { |
| | 54 | 3257 | | offset -= Vector128<TValue>.Count; |
| | 54 | 3258 | | continue; |
| | | 3259 | | } |
| | | 3260 | | |
| | 186 | 3261 | | return ComputeLastIndex(offset, equals); |
| | | 3262 | | } |
| | | 3263 | | |
| | | 3264 | | // Process the first vector in the search space. |
| | 286 | 3265 | | current = Vector128.LoadUnsafe(ref searchSpace); |
| | 286 | 3266 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(current, values0) | Vector128.Equals(current, values1) |
| | | 3267 | | |
| | 286 | 3268 | | if (equals != Vector128<TValue>.Zero) |
| | | 3269 | | { |
| | 164 | 3270 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3271 | | } |
| | | 3272 | | } |
| | | 3273 | | |
| | 774 | 3274 | | return -1; |
| | | 3275 | | } |
| | | 3276 | | |
| | | 3277 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3278 | | internal static int LastIndexOfAnyValueType<T>(ref T searchSpace, T value0, T value1, T value2, T value3, int le |
| | 1672 | 3279 | | => LastIndexOfAnyValueType<T, DontNegate<T>>(ref searchSpace, value0, value1, value2, value3, length); |
| | | 3280 | | |
| | | 3281 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3282 | | internal static int LastIndexOfAnyExceptValueType<T>(ref T searchSpace, T value0, T value1, T value2, T value3, |
| | 1672 | 3283 | | => LastIndexOfAnyValueType<T, Negate<T>>(ref searchSpace, value0, value1, value2, value3, length); |
| | | 3284 | | |
| | | 3285 | | private static int LastIndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue value |
| | | 3286 | | where TValue : struct, INumber<TValue> |
| | | 3287 | | where TNegator : struct, INegator<TValue> |
| | | 3288 | | { |
| | 3344 | 3289 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 3344 | 3290 | | Debug.Assert(value0 is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 3291 | | |
| | 3344 | 3292 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 3293 | | { |
| | 1668 | 3294 | | nuint offset = (nuint)length - 1; |
| | | 3295 | | TValue lookUp; |
| | | 3296 | | |
| | 2044 | 3297 | | while (length >= 4) |
| | | 3298 | | { |
| | 1264 | 3299 | | length -= 4; |
| | | 3300 | | |
| | 1264 | 3301 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 1264 | 3302 | | lookUp = current; |
| | 1264 | 3303 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3304 | | { |
| | 564 | 3305 | | return (int)(offset); |
| | | 3306 | | } |
| | | 3307 | | |
| | 700 | 3308 | | lookUp = Unsafe.Add(ref current, -1); |
| | 700 | 3309 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3310 | | { |
| | 182 | 3311 | | return (int)(offset - 1); |
| | | 3312 | | } |
| | | 3313 | | |
| | 518 | 3314 | | lookUp = Unsafe.Add(ref current, -2); |
| | 518 | 3315 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3316 | | { |
| | 92 | 3317 | | return (int)(offset - 2); |
| | | 3318 | | } |
| | | 3319 | | |
| | 426 | 3320 | | lookUp = Unsafe.Add(ref current, -3); |
| | 426 | 3321 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3322 | | { |
| | 50 | 3323 | | return (int)(offset - 3); |
| | | 3324 | | } |
| | | 3325 | | |
| | 376 | 3326 | | offset -= 4; |
| | | 3327 | | } |
| | | 3328 | | |
| | 1146 | 3329 | | while (length > 0) |
| | | 3330 | | { |
| | 612 | 3331 | | length -= 1; |
| | | 3332 | | |
| | 612 | 3333 | | lookUp = Unsafe.Add(ref searchSpace, offset); |
| | 612 | 3334 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3335 | | { |
| | 246 | 3336 | | return (int)(offset); |
| | | 3337 | | } |
| | | 3338 | | |
| | 366 | 3339 | | offset -= 1; |
| | | 3340 | | } |
| | | 3341 | | |
| | 534 | 3342 | | return -1; |
| | | 3343 | | } |
| | 1676 | 3344 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 3345 | | { |
| | 4624 | 3346 | | Vector512<TValue> equals, current, values0 = Vector512.Create(value0), values1 = Vector512.Create(value1 |
| | 1156 | 3347 | | nint offset = length - Vector512<TValue>.Count; |
| | | 3348 | | |
| | | 3349 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 4532 | 3350 | | while (offset > 0) |
| | | 3351 | | { |
| | 4208 | 3352 | | current = Vector512.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 4208 | 3353 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(current, values0) | Vector512.Equals(current, valu |
| | 4208 | 3354 | | | Vector512.Equals(current, values2) | Vector512.Equals(current, values3)); |
| | 4208 | 3355 | | if (equals == Vector512<TValue>.Zero) |
| | | 3356 | | { |
| | 3376 | 3357 | | offset -= Vector512<TValue>.Count; |
| | 3376 | 3358 | | continue; |
| | | 3359 | | } |
| | | 3360 | | |
| | 832 | 3361 | | return ComputeLastIndex(offset, equals); |
| | | 3362 | | } |
| | | 3363 | | |
| | | 3364 | | // Process the first vector in the search space. |
| | 324 | 3365 | | current = Vector512.LoadUnsafe(ref searchSpace); |
| | 324 | 3366 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(current, values0) | Vector512.Equals(current, values1) |
| | | 3367 | | |
| | 324 | 3368 | | if (equals != Vector512<TValue>.Zero) |
| | | 3369 | | { |
| | 58 | 3370 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3371 | | } |
| | | 3372 | | } |
| | 520 | 3373 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 3374 | | { |
| | 880 | 3375 | | Vector256<TValue> equals, current, values0 = Vector256.Create(value0), values1 = Vector256.Create(value1 |
| | 220 | 3376 | | nint offset = length - Vector256<TValue>.Count; |
| | | 3377 | | |
| | | 3378 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 266 | 3379 | | while (offset > 0) |
| | | 3380 | | { |
| | 168 | 3381 | | current = Vector256.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 168 | 3382 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(current, values0) | Vector256.Equals(current, valu |
| | 168 | 3383 | | | Vector256.Equals(current, values2) | Vector256.Equals(current, values3)); |
| | 168 | 3384 | | if (equals == Vector256<TValue>.Zero) |
| | | 3385 | | { |
| | 46 | 3386 | | offset -= Vector256<TValue>.Count; |
| | 46 | 3387 | | continue; |
| | | 3388 | | } |
| | | 3389 | | |
| | 122 | 3390 | | return ComputeLastIndex(offset, equals); |
| | | 3391 | | } |
| | | 3392 | | |
| | | 3393 | | // Process the first vector in the search space. |
| | 98 | 3394 | | current = Vector256.LoadUnsafe(ref searchSpace); |
| | 98 | 3395 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(current, values0) | Vector256.Equals(current, values1) |
| | 98 | 3396 | | if (equals != Vector256<TValue>.Zero) |
| | | 3397 | | { |
| | 66 | 3398 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3399 | | } |
| | | 3400 | | } |
| | | 3401 | | else |
| | | 3402 | | { |
| | 1200 | 3403 | | Vector128<TValue> equals, current, values0 = Vector128.Create(value0), values1 = Vector128.Create(value1 |
| | 300 | 3404 | | nint offset = length - Vector128<TValue>.Count; |
| | | 3405 | | |
| | | 3406 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 380 | 3407 | | while (offset > 0) |
| | | 3408 | | { |
| | 232 | 3409 | | current = Vector128.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 232 | 3410 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(current, values0) | Vector128.Equals(current, valu |
| | 232 | 3411 | | if (equals == Vector128<TValue>.Zero) |
| | | 3412 | | { |
| | 80 | 3413 | | offset -= Vector128<TValue>.Count; |
| | 80 | 3414 | | continue; |
| | | 3415 | | } |
| | | 3416 | | |
| | 152 | 3417 | | return ComputeLastIndex(offset, equals); |
| | | 3418 | | } |
| | | 3419 | | |
| | | 3420 | | // Process the first vector in the search space. |
| | 148 | 3421 | | current = Vector128.LoadUnsafe(ref searchSpace); |
| | 148 | 3422 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(current, values0) | Vector128.Equals(current, values1) |
| | 148 | 3423 | | if (equals != Vector128<TValue>.Zero) |
| | | 3424 | | { |
| | 48 | 3425 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3426 | | } |
| | | 3427 | | } |
| | | 3428 | | |
| | 398 | 3429 | | return -1; |
| | | 3430 | | } |
| | | 3431 | | |
| | | 3432 | | public static void Replace<T>(ref T src, ref T dst, T oldValue, T newValue, nuint length) where T : IEquatable<T |
| | | 3433 | | { |
| | 0 | 3434 | | if (default(T) is not null || oldValue is not null) |
| | | 3435 | | { |
| | 0 | 3436 | | Debug.Assert(oldValue is not null); |
| | | 3437 | | |
| | 0 | 3438 | | for (nuint idx = 0; idx < length; ++idx) |
| | | 3439 | | { |
| | 0 | 3440 | | T original = Unsafe.Add(ref src, idx); |
| | 0 | 3441 | | Unsafe.Add(ref dst, idx) = oldValue.Equals(original) ? newValue : original; |
| | | 3442 | | } |
| | | 3443 | | } |
| | | 3444 | | else |
| | | 3445 | | { |
| | 0 | 3446 | | for (nuint idx = 0; idx < length; ++idx) |
| | | 3447 | | { |
| | 0 | 3448 | | T original = Unsafe.Add(ref src, idx); |
| | 0 | 3449 | | Unsafe.Add(ref dst, idx) = original is null ? newValue : original; |
| | | 3450 | | } |
| | | 3451 | | } |
| | 0 | 3452 | | } |
| | | 3453 | | |
| | | 3454 | | public static void ReplaceValueType<T>(ref T src, ref T dst, T oldValue, T newValue, nuint length) where T : str |
| | | 3455 | | { |
| | 0 | 3456 | | if (!Vector128.IsHardwareAccelerated || length < (uint)Vector128<T>.Count) |
| | | 3457 | | { |
| | 0 | 3458 | | for (nuint idx = 0; idx < length; ++idx) |
| | | 3459 | | { |
| | 0 | 3460 | | T original = Unsafe.Add(ref src, idx); |
| | 0 | 3461 | | Unsafe.Add(ref dst, idx) = EqualityComparer<T>.Default.Equals(original, oldValue) ? newValue : origi |
| | | 3462 | | } |
| | | 3463 | | } |
| | | 3464 | | else |
| | | 3465 | | { |
| | 0 | 3466 | | Debug.Assert(Vector128.IsHardwareAccelerated && Vector128<T>.IsSupported, "Vector128 is not HW-accelerat |
| | | 3467 | | |
| | 0 | 3468 | | nuint idx = 0; |
| | | 3469 | | |
| | 0 | 3470 | | if (!Vector256.IsHardwareAccelerated || length < (uint)Vector256<T>.Count) |
| | | 3471 | | { |
| | 0 | 3472 | | nuint lastVectorIndex = length - (uint)Vector128<T>.Count; |
| | 0 | 3473 | | Vector128<T> oldValues = Vector128.Create(oldValue); |
| | 0 | 3474 | | Vector128<T> newValues = Vector128.Create(newValue); |
| | | 3475 | | Vector128<T> original, mask, result; |
| | | 3476 | | |
| | | 3477 | | do |
| | | 3478 | | { |
| | 0 | 3479 | | original = Vector128.LoadUnsafe(ref src, idx); |
| | 0 | 3480 | | mask = Vector128.Equals(oldValues, original); |
| | 0 | 3481 | | result = Vector128.ConditionalSelect(mask, newValues, original); |
| | 0 | 3482 | | result.StoreUnsafe(ref dst, idx); |
| | | 3483 | | |
| | 0 | 3484 | | idx += (uint)Vector128<T>.Count; |
| | | 3485 | | } |
| | 0 | 3486 | | while (idx < lastVectorIndex); |
| | | 3487 | | |
| | | 3488 | | // There are (0, Vector128<T>.Count] elements remaining now. |
| | | 3489 | | // As the operation is idempotent, and we know that in total there are at least Vector128<T>.Count |
| | | 3490 | | // elements available, we read a vector from the very end, perform the replace and write to the |
| | | 3491 | | // the resulting vector at the very end. |
| | | 3492 | | // Thus we can eliminate the scalar processing of the remaining elements. |
| | 0 | 3493 | | original = Vector128.LoadUnsafe(ref src, lastVectorIndex); |
| | 0 | 3494 | | mask = Vector128.Equals(oldValues, original); |
| | 0 | 3495 | | result = Vector128.ConditionalSelect(mask, newValues, original); |
| | 0 | 3496 | | result.StoreUnsafe(ref dst, lastVectorIndex); |
| | | 3497 | | } |
| | 0 | 3498 | | else if (!Vector512.IsHardwareAccelerated || length < (uint)Vector512<T>.Count) |
| | | 3499 | | { |
| | 0 | 3500 | | nuint lastVectorIndex = length - (uint)Vector256<T>.Count; |
| | 0 | 3501 | | Vector256<T> oldValues = Vector256.Create(oldValue); |
| | 0 | 3502 | | Vector256<T> newValues = Vector256.Create(newValue); |
| | | 3503 | | Vector256<T> original, mask, result; |
| | | 3504 | | |
| | | 3505 | | do |
| | | 3506 | | { |
| | 0 | 3507 | | original = Vector256.LoadUnsafe(ref src, idx); |
| | 0 | 3508 | | mask = Vector256.Equals(oldValues, original); |
| | 0 | 3509 | | result = Vector256.ConditionalSelect(mask, newValues, original); |
| | 0 | 3510 | | result.StoreUnsafe(ref dst, idx); |
| | | 3511 | | |
| | 0 | 3512 | | idx += (uint)Vector256<T>.Count; |
| | | 3513 | | } |
| | 0 | 3514 | | while (idx < lastVectorIndex); |
| | | 3515 | | |
| | 0 | 3516 | | original = Vector256.LoadUnsafe(ref src, lastVectorIndex); |
| | 0 | 3517 | | mask = Vector256.Equals(oldValues, original); |
| | 0 | 3518 | | result = Vector256.ConditionalSelect(mask, newValues, original); |
| | 0 | 3519 | | result.StoreUnsafe(ref dst, lastVectorIndex); |
| | | 3520 | | } |
| | | 3521 | | else |
| | | 3522 | | { |
| | 0 | 3523 | | Debug.Assert(Vector512.IsHardwareAccelerated && Vector512<T>.IsSupported, "Vector512 is not HW-accel |
| | | 3524 | | |
| | 0 | 3525 | | nuint lastVectorIndex = length - (uint)Vector512<T>.Count; |
| | 0 | 3526 | | Vector512<T> oldValues = Vector512.Create(oldValue); |
| | 0 | 3527 | | Vector512<T> newValues = Vector512.Create(newValue); |
| | | 3528 | | Vector512<T> original, mask, result; |
| | | 3529 | | |
| | | 3530 | | do |
| | | 3531 | | { |
| | 0 | 3532 | | original = Vector512.LoadUnsafe(ref src, idx); |
| | 0 | 3533 | | mask = Vector512.Equals(oldValues, original); |
| | 0 | 3534 | | result = Vector512.ConditionalSelect(mask, newValues, original); |
| | 0 | 3535 | | result.StoreUnsafe(ref dst, idx); |
| | | 3536 | | |
| | 0 | 3537 | | idx += (uint)Vector512<T>.Count; |
| | | 3538 | | } |
| | 0 | 3539 | | while (idx < lastVectorIndex); |
| | | 3540 | | |
| | 0 | 3541 | | original = Vector512.LoadUnsafe(ref src, lastVectorIndex); |
| | 0 | 3542 | | mask = Vector512.Equals(oldValues, original); |
| | 0 | 3543 | | result = Vector512.ConditionalSelect(mask, newValues, original); |
| | 0 | 3544 | | result.StoreUnsafe(ref dst, lastVectorIndex); |
| | | 3545 | | } |
| | | 3546 | | } |
| | 0 | 3547 | | } |
| | | 3548 | | |
| | | 3549 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3550 | | internal static int LastIndexOfAnyValueType<T>(ref T searchSpace, T value0, T value1, T value2, T value3, T valu |
| | 2286 | 3551 | | => LastIndexOfAnyValueType<T, DontNegate<T>>(ref searchSpace, value0, value1, value2, value3, value4, length |
| | | 3552 | | |
| | | 3553 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3554 | | internal static int LastIndexOfAnyExceptValueType<T>(ref T searchSpace, T value0, T value1, T value2, T value3, |
| | 2286 | 3555 | | => LastIndexOfAnyValueType<T, Negate<T>>(ref searchSpace, value0, value1, value2, value3, value4, length); |
| | | 3556 | | |
| | | 3557 | | private static int LastIndexOfAnyValueType<TValue, TNegator>(ref TValue searchSpace, TValue value0, TValue value |
| | | 3558 | | where TValue : struct, INumber<TValue> |
| | | 3559 | | where TNegator : struct, INegator<TValue> |
| | | 3560 | | { |
| | 4572 | 3561 | | Debug.Assert(length >= 0, "Expected non-negative length"); |
| | 4572 | 3562 | | Debug.Assert(value0 is byte or short or int or long, "Expected caller to normalize to one of these types"); |
| | | 3563 | | |
| | 4572 | 3564 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<TValue>.Count) |
| | | 3565 | | { |
| | 2112 | 3566 | | nuint offset = (nuint)length - 1; |
| | | 3567 | | TValue lookUp; |
| | | 3568 | | |
| | 2712 | 3569 | | while (length >= 4) |
| | | 3570 | | { |
| | 1896 | 3571 | | length -= 4; |
| | | 3572 | | |
| | 1896 | 3573 | | ref TValue current = ref Unsafe.Add(ref searchSpace, offset); |
| | 1896 | 3574 | | lookUp = current; |
| | 1896 | 3575 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3576 | | { |
| | 816 | 3577 | | return (int)offset; |
| | | 3578 | | } |
| | | 3579 | | |
| | 1080 | 3580 | | lookUp = Unsafe.Add(ref current, -1); |
| | 1080 | 3581 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3582 | | { |
| | 276 | 3583 | | return (int)offset - 1; |
| | | 3584 | | } |
| | | 3585 | | |
| | 804 | 3586 | | lookUp = Unsafe.Add(ref current, -2); |
| | 804 | 3587 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3588 | | { |
| | 114 | 3589 | | return (int)offset - 2; |
| | | 3590 | | } |
| | | 3591 | | |
| | 690 | 3592 | | lookUp = Unsafe.Add(ref current, -3); |
| | 690 | 3593 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3594 | | { |
| | 90 | 3595 | | return (int)offset - 3; |
| | | 3596 | | } |
| | | 3597 | | |
| | 600 | 3598 | | offset -= 4; |
| | | 3599 | | } |
| | | 3600 | | |
| | 1232 | 3601 | | while (length > 0) |
| | | 3602 | | { |
| | 652 | 3603 | | length -= 1; |
| | | 3604 | | |
| | 652 | 3605 | | lookUp = Unsafe.Add(ref searchSpace, offset); |
| | 652 | 3606 | | if (TNegator.NegateIfNeeded(lookUp == value0 || lookUp == value1 || lookUp == value2 || lookUp == va |
| | | 3607 | | { |
| | 236 | 3608 | | return (int)offset; |
| | | 3609 | | } |
| | | 3610 | | |
| | 416 | 3611 | | offset -= 1; |
| | | 3612 | | } |
| | | 3613 | | } |
| | 2460 | 3614 | | else if (Vector512.IsHardwareAccelerated && length >= Vector512<TValue>.Count) |
| | | 3615 | | { |
| | 3504 | 3616 | | Vector512<TValue> equals, current, values0 = Vector512.Create(value0), values1 = Vector512.Create(value1 |
| | 5256 | 3617 | | values2 = Vector512.Create(value2), values3 = Vector512.Create(value3), values4 = Vector512.Create(v |
| | 1752 | 3618 | | nint offset = length - Vector512<TValue>.Count; |
| | | 3619 | | |
| | | 3620 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 5184 | 3621 | | while (offset > 0) |
| | | 3622 | | { |
| | 4806 | 3623 | | current = Vector512.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 4806 | 3624 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(current, values0) | Vector512.Equals(current, valu |
| | 4806 | 3625 | | | Vector512.Equals(current, values3) | Vector512.Equals(current, values4)); |
| | 4806 | 3626 | | if (equals == Vector512<TValue>.Zero) |
| | | 3627 | | { |
| | 3432 | 3628 | | offset -= Vector512<TValue>.Count; |
| | 3432 | 3629 | | continue; |
| | | 3630 | | } |
| | | 3631 | | |
| | 1374 | 3632 | | return ComputeLastIndex(offset, equals); |
| | | 3633 | | } |
| | | 3634 | | |
| | | 3635 | | // Process the first vector in the search space. |
| | 378 | 3636 | | current = Vector512.LoadUnsafe(ref searchSpace); |
| | 378 | 3637 | | equals = TNegator.NegateIfNeeded(Vector512.Equals(current, values0) | Vector512.Equals(current, values1) |
| | 378 | 3638 | | | Vector512.Equals(current, values3) | Vector512.Equals(current, values4)); |
| | | 3639 | | |
| | 378 | 3640 | | if (equals != Vector512<TValue>.Zero) |
| | | 3641 | | { |
| | 110 | 3642 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3643 | | } |
| | | 3644 | | } |
| | 708 | 3645 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<TValue>.Count) |
| | | 3646 | | { |
| | 752 | 3647 | | Vector256<TValue> equals, current, values0 = Vector256.Create(value0), values1 = Vector256.Create(value1 |
| | 1128 | 3648 | | values2 = Vector256.Create(value2), values3 = Vector256.Create(value3), values4 = Vector256.Create(v |
| | 376 | 3649 | | nint offset = length - Vector256<TValue>.Count; |
| | | 3650 | | |
| | | 3651 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 416 | 3652 | | while (offset > 0) |
| | | 3653 | | { |
| | 312 | 3654 | | current = Vector256.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 312 | 3655 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(current, values0) | Vector256.Equals(current, valu |
| | 312 | 3656 | | | Vector256.Equals(current, values3) | Vector256.Equals(current, values4)); |
| | 312 | 3657 | | if (equals == Vector256<TValue>.Zero) |
| | | 3658 | | { |
| | 40 | 3659 | | offset -= Vector256<TValue>.Count; |
| | 40 | 3660 | | continue; |
| | | 3661 | | } |
| | | 3662 | | |
| | 272 | 3663 | | return ComputeLastIndex(offset, equals); |
| | | 3664 | | } |
| | | 3665 | | |
| | | 3666 | | // Process the first vector in the search space. |
| | 104 | 3667 | | current = Vector256.LoadUnsafe(ref searchSpace); |
| | 104 | 3668 | | equals = TNegator.NegateIfNeeded(Vector256.Equals(current, values0) | Vector256.Equals(current, values1) |
| | 104 | 3669 | | | Vector256.Equals(current, values3) | Vector256.Equals(current, values4)); |
| | | 3670 | | |
| | 104 | 3671 | | if (equals != Vector256<TValue>.Zero) |
| | | 3672 | | { |
| | 62 | 3673 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3674 | | } |
| | | 3675 | | } |
| | | 3676 | | else |
| | | 3677 | | { |
| | 664 | 3678 | | Vector128<TValue> equals, current, values0 = Vector128.Create(value0), values1 = Vector128.Create(value1 |
| | 996 | 3679 | | values2 = Vector128.Create(value2), values3 = Vector128.Create(value3), values4 = Vector128.Create(v |
| | 332 | 3680 | | nint offset = length - Vector128<TValue>.Count; |
| | | 3681 | | |
| | | 3682 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | 400 | 3683 | | while (offset > 0) |
| | | 3684 | | { |
| | 248 | 3685 | | current = Vector128.LoadUnsafe(ref searchSpace, (nuint)(offset)); |
| | 248 | 3686 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(current, values0) | Vector128.Equals(current, valu |
| | 248 | 3687 | | | Vector128.Equals(current, values3) | Vector128.Equals(current, values4)); |
| | | 3688 | | |
| | 248 | 3689 | | if (equals == Vector128<TValue>.Zero) |
| | | 3690 | | { |
| | 68 | 3691 | | offset -= Vector128<TValue>.Count; |
| | 68 | 3692 | | continue; |
| | | 3693 | | } |
| | | 3694 | | |
| | 180 | 3695 | | return ComputeLastIndex(offset, equals); |
| | | 3696 | | } |
| | | 3697 | | |
| | | 3698 | | // Process the first vector in the search space. |
| | | 3699 | | |
| | 152 | 3700 | | current = Vector128.LoadUnsafe(ref searchSpace); |
| | 152 | 3701 | | equals = TNegator.NegateIfNeeded(Vector128.Equals(current, values0) | Vector128.Equals(current, values1) |
| | 152 | 3702 | | | Vector128.Equals(current, values3) | Vector128.Equals(current, values4)); |
| | | 3703 | | |
| | 152 | 3704 | | if (equals != Vector128<TValue>.Zero) |
| | | 3705 | | { |
| | 84 | 3706 | | return ComputeLastIndex(offset: 0, equals); |
| | | 3707 | | } |
| | | 3708 | | } |
| | | 3709 | | |
| | 958 | 3710 | | return -1; |
| | | 3711 | | } |
| | | 3712 | | |
| | | 3713 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3714 | | private static unsafe int ComputeFirstIndex<T>(ref T searchSpace, ref T current, Vector128<T> equals) where T : |
| | | 3715 | | { |
| | 4998 | 3716 | | uint notEqualsElements = equals.ExtractMostSignificantBits(); |
| | 4998 | 3717 | | int index = BitOperations.TrailingZeroCount(notEqualsElements); |
| | 4998 | 3718 | | return index + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current) / (nuint)sizeof(T)); |
| | | 3719 | | } |
| | | 3720 | | |
| | | 3721 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3722 | | private static unsafe int ComputeFirstIndex<T>(ref T searchSpace, ref T current, Vector256<T> equals) where T : |
| | | 3723 | | { |
| | 4155 | 3724 | | uint notEqualsElements = equals.ExtractMostSignificantBits(); |
| | 4155 | 3725 | | int index = BitOperations.TrailingZeroCount(notEqualsElements); |
| | 4155 | 3726 | | return index + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current) / (nuint)sizeof(T)); |
| | | 3727 | | } |
| | | 3728 | | |
| | | 3729 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3730 | | private static unsafe int ComputeFirstIndex<T>(ref T searchSpace, ref T current, Vector512<T> equals) where T : |
| | | 3731 | | { |
| | 17289 | 3732 | | ulong notEqualsElements = equals.ExtractMostSignificantBits(); |
| | 17289 | 3733 | | int index = BitOperations.TrailingZeroCount(notEqualsElements); |
| | 17289 | 3734 | | return index + (int)((nuint)Unsafe.ByteOffset(ref searchSpace, ref current) / (nuint)sizeof(T)); |
| | | 3735 | | } |
| | | 3736 | | |
| | | 3737 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3738 | | private static int ComputeLastIndex<T>(nint offset, Vector128<T> equals) where T : struct |
| | | 3739 | | { |
| | 2202 | 3740 | | uint notEqualsElements = equals.ExtractMostSignificantBits(); |
| | 2202 | 3741 | | int index = 31 - BitOperations.LeadingZeroCount(notEqualsElements); // 31 = 32 (bits in Int32) - 1 (indexing |
| | 2202 | 3742 | | return (int)offset + index; |
| | | 3743 | | } |
| | | 3744 | | |
| | | 3745 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3746 | | private static int ComputeLastIndex<T>(nint offset, Vector256<T> equals) where T : struct |
| | | 3747 | | { |
| | 2278 | 3748 | | uint notEqualsElements = equals.ExtractMostSignificantBits(); |
| | 2278 | 3749 | | int index = 31 - BitOperations.LeadingZeroCount(notEqualsElements); // 31 = 32 (bits in Int32) - 1 (indexing |
| | 2278 | 3750 | | return (int)offset + index; |
| | | 3751 | | } |
| | | 3752 | | |
| | | 3753 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3754 | | private static int ComputeLastIndex<T>(nint offset, Vector512<T> equals) where T : struct |
| | | 3755 | | { |
| | 9517 | 3756 | | ulong notEqualsElements = equals.ExtractMostSignificantBits(); |
| | 9517 | 3757 | | int index = 63 - BitOperations.LeadingZeroCount(notEqualsElements); // 31 = 32 (bits in Int32) - 1 (indexing |
| | 9517 | 3758 | | return (int)offset + index; |
| | | 3759 | | } |
| | | 3760 | | |
| | | 3761 | | internal interface INegator<T> where T : struct |
| | | 3762 | | { |
| | | 3763 | | static abstract bool NegateIfNeeded(bool equals); |
| | | 3764 | | static abstract Vector128<T> NegateIfNeeded(Vector128<T> equals); |
| | | 3765 | | static abstract Vector256<T> NegateIfNeeded(Vector256<T> equals); |
| | | 3766 | | static abstract Vector512<T> NegateIfNeeded(Vector512<T> equals); |
| | | 3767 | | |
| | | 3768 | | // The generic vector APIs assume use for IndexOf where `DontNegate` is |
| | | 3769 | | // for `IndexOfAny` and `Negate` is for `IndexOfAnyExcept` |
| | | 3770 | | |
| | | 3771 | | static abstract bool HasMatch<TVector>(TVector left, TVector right) |
| | | 3772 | | where TVector : struct, ISimdVector<TVector, T>; |
| | | 3773 | | |
| | | 3774 | | static abstract TVector GetMatchMask<TVector>(TVector left, TVector right) |
| | | 3775 | | where TVector : struct, ISimdVector<TVector, T>; |
| | | 3776 | | } |
| | | 3777 | | |
| | | 3778 | | internal readonly struct DontNegate<T> : INegator<T> |
| | | 3779 | | where T : struct |
| | | 3780 | | { |
| | 66790 | 3781 | | public static bool NegateIfNeeded(bool equals) => equals; |
| | 6959 | 3782 | | public static Vector128<T> NegateIfNeeded(Vector128<T> equals) => equals; |
| | 6218 | 3783 | | public static Vector256<T> NegateIfNeeded(Vector256<T> equals) => equals; |
| | 64757 | 3784 | | public static Vector512<T> NegateIfNeeded(Vector512<T> equals) => equals; |
| | | 3785 | | |
| | | 3786 | | // The generic vector APIs assume use for `IndexOfAny` where we |
| | | 3787 | | // want "HasMatch" to mean any of the two elements match. |
| | | 3788 | | |
| | | 3789 | | public static bool HasMatch<TVector>(TVector left, TVector right) |
| | | 3790 | | where TVector : struct, ISimdVector<TVector, T> |
| | | 3791 | | { |
| | 25035 | 3792 | | return TVector.EqualsAny(left, right); |
| | | 3793 | | } |
| | | 3794 | | |
| | | 3795 | | public static TVector GetMatchMask<TVector>(TVector left, TVector right) |
| | | 3796 | | where TVector : struct, ISimdVector<TVector, T> |
| | | 3797 | | { |
| | 5415 | 3798 | | return TVector.Equals(left, right); |
| | | 3799 | | } |
| | | 3800 | | } |
| | | 3801 | | |
| | | 3802 | | internal readonly struct Negate<T> : INegator<T> |
| | | 3803 | | where T : struct |
| | | 3804 | | { |
| | 59142 | 3805 | | public static bool NegateIfNeeded(bool equals) => !equals; |
| | 4518 | 3806 | | public static Vector128<T> NegateIfNeeded(Vector128<T> equals) => ~equals; |
| | 4406 | 3807 | | public static Vector256<T> NegateIfNeeded(Vector256<T> equals) => ~equals; |
| | 34956 | 3808 | | public static Vector512<T> NegateIfNeeded(Vector512<T> equals) => ~equals; |
| | | 3809 | | |
| | | 3810 | | // The generic vector APIs assume use for `IndexOfAnyExcept` where we |
| | | 3811 | | // want "HasMatch" to mean any of the two elements don't match |
| | | 3812 | | |
| | | 3813 | | public static bool HasMatch<TVector>(TVector left, TVector right) |
| | | 3814 | | where TVector : struct, ISimdVector<TVector, T> |
| | | 3815 | | { |
| | 7241 | 3816 | | return !TVector.EqualsAll(left, right); |
| | | 3817 | | } |
| | | 3818 | | |
| | | 3819 | | public static TVector GetMatchMask<TVector>(TVector left, TVector right) |
| | | 3820 | | where TVector : struct, ISimdVector<TVector, T> |
| | | 3821 | | { |
| | 2107 | 3822 | | return ~TVector.Equals(left, right); |
| | | 3823 | | } |
| | | 3824 | | } |
| | | 3825 | | |
| | | 3826 | | internal static int IndexOfAnyInRange<T>(ref T searchSpace, T lowInclusive, T highInclusive, int length) |
| | | 3827 | | where T : IComparable<T> |
| | | 3828 | | { |
| | 0 | 3829 | | for (int i = 0; i < length; i++) |
| | | 3830 | | { |
| | 0 | 3831 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 3832 | | if ((lowInclusive.CompareTo(current) <= 0) && (highInclusive.CompareTo(current) >= 0)) |
| | | 3833 | | { |
| | 0 | 3834 | | return i; |
| | | 3835 | | } |
| | | 3836 | | } |
| | | 3837 | | |
| | 0 | 3838 | | return -1; |
| | | 3839 | | } |
| | | 3840 | | |
| | | 3841 | | internal static int IndexOfAnyExceptInRange<T>(ref T searchSpace, T lowInclusive, T highInclusive, int length) |
| | | 3842 | | where T : IComparable<T> |
| | | 3843 | | { |
| | 0 | 3844 | | for (int i = 0; i < length; i++) |
| | | 3845 | | { |
| | 0 | 3846 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 3847 | | if ((lowInclusive.CompareTo(current) > 0) || (highInclusive.CompareTo(current) < 0)) |
| | | 3848 | | { |
| | 0 | 3849 | | return i; |
| | | 3850 | | } |
| | | 3851 | | } |
| | | 3852 | | |
| | 0 | 3853 | | return -1; |
| | | 3854 | | } |
| | | 3855 | | |
| | | 3856 | | internal static int IndexOfAnyInRangeUnsignedNumber<T>(ref T searchSpace, T lowInclusive, T highInclusive, int l |
| | | 3857 | | where T : struct, IUnsignedNumber<T>, IComparisonOperators<T, T, bool> => |
| | 6097 | 3858 | | IndexOfAnyInRangeUnsignedNumber<T, DontNegate<T>>(ref searchSpace, lowInclusive, highInclusive, length); |
| | | 3859 | | |
| | | 3860 | | internal static int IndexOfAnyExceptInRangeUnsignedNumber<T>(ref T searchSpace, T lowInclusive, T highInclusive, |
| | | 3861 | | where T : struct, IUnsignedNumber<T>, IComparisonOperators<T, T, bool> => |
| | 3996 | 3862 | | IndexOfAnyInRangeUnsignedNumber<T, Negate<T>>(ref searchSpace, lowInclusive, highInclusive, length); |
| | | 3863 | | |
| | | 3864 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 3865 | | private static int IndexOfAnyInRangeUnsignedNumber<T, TNegator>(ref T searchSpace, T lowInclusive, T highInclusi |
| | | 3866 | | where T : struct, IUnsignedNumber<T>, IComparisonOperators<T, T, bool> |
| | | 3867 | | where TNegator : struct, INegator<T> |
| | | 3868 | | { |
| | 10093 | 3869 | | if (PackedSpanHelpers.PackedIndexOfIsSupported && typeof(T) == typeof(ushort) && PackedSpanHelpers.CanUsePac |
| | | 3870 | | { |
| | 1 | 3871 | | ref char charSearchSpace = ref Unsafe.As<T, char>(ref searchSpace); |
| | 1 | 3872 | | char charLowInclusive = Unsafe.BitCast<T, char>(lowInclusive); |
| | 1 | 3873 | | char charRange = (char)(Unsafe.BitCast<T, char>(highInclusive) - charLowInclusive); |
| | | 3874 | | |
| | 1 | 3875 | | return typeof(TNegator) == typeof(DontNegate<ushort>) |
| | 1 | 3876 | | ? PackedSpanHelpers.IndexOfAnyInRange(ref charSearchSpace, charLowInclusive, charRange, length) |
| | 1 | 3877 | | : PackedSpanHelpers.IndexOfAnyExceptInRange(ref charSearchSpace, charLowInclusive, charRange, length |
| | | 3878 | | } |
| | | 3879 | | |
| | 10092 | 3880 | | return NonPackedIndexOfAnyInRangeUnsignedNumber<T, TNegator>(ref searchSpace, lowInclusive, highInclusive, l |
| | | 3881 | | } |
| | | 3882 | | |
| | | 3883 | | internal static int NonPackedIndexOfAnyInRangeUnsignedNumber<T, TNegator>(ref T searchSpace, T lowInclusive, T h |
| | | 3884 | | where T : struct, IUnsignedNumber<T>, IComparisonOperators<T, T, bool> |
| | | 3885 | | where TNegator : struct, INegator<T> |
| | | 3886 | | { |
| | | 3887 | | // T must be a type whose comparison operator semantics match that of Vector128/256. |
| | | 3888 | | |
| | 14860 | 3889 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<T>.Count) |
| | | 3890 | | { |
| | 5650 | 3891 | | T rangeInclusive = highInclusive - lowInclusive; |
| | 32360 | 3892 | | for (int i = 0; i < length; i++) |
| | | 3893 | | { |
| | 13558 | 3894 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 13558 | 3895 | | if (TNegator.NegateIfNeeded((current - lowInclusive) <= rangeInclusive)) |
| | | 3896 | | { |
| | 3028 | 3897 | | return i; |
| | | 3898 | | } |
| | | 3899 | | } |
| | | 3900 | | } |
| | 9210 | 3901 | | else if (!Vector256.IsHardwareAccelerated || length < Vector256<T>.Count) |
| | | 3902 | | { |
| | 2345 | 3903 | | Vector128<T> lowVector = Vector128.Create(lowInclusive); |
| | 2345 | 3904 | | Vector128<T> rangeVector = Vector128.Create(highInclusive - lowInclusive); |
| | | 3905 | | Vector128<T> inRangeVector; |
| | | 3906 | | |
| | 2345 | 3907 | | ref T current = ref searchSpace; |
| | 2345 | 3908 | | ref T oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector128<T>.Count)); |
| | | 3909 | | |
| | | 3910 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 3911 | | do |
| | | 3912 | | { |
| | 2345 | 3913 | | inRangeVector = TNegator.NegateIfNeeded(Vector128.LessThanOrEqual(Vector128.LoadUnsafe(ref current) |
| | 2345 | 3914 | | if (inRangeVector != Vector128<T>.Zero) |
| | | 3915 | | { |
| | 1519 | 3916 | | return ComputeFirstIndex(ref searchSpace, ref current, inRangeVector); |
| | | 3917 | | } |
| | | 3918 | | |
| | 826 | 3919 | | current = ref Unsafe.Add(ref current, Vector128<T>.Count); |
| | | 3920 | | } |
| | 826 | 3921 | | while (Unsafe.IsAddressLessThan(ref current, ref oneVectorAwayFromEnd)); |
| | | 3922 | | |
| | | 3923 | | // Process the last vector in the search space (which might overlap with already processed elements). |
| | 826 | 3924 | | inRangeVector = TNegator.NegateIfNeeded(Vector128.LessThanOrEqual(Vector128.LoadUnsafe(ref oneVectorAway |
| | 826 | 3925 | | if (inRangeVector != Vector128<T>.Zero) |
| | | 3926 | | { |
| | 226 | 3927 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, inRangeVector); |
| | | 3928 | | } |
| | | 3929 | | } |
| | 6865 | 3930 | | else if (!Vector512.IsHardwareAccelerated || length < (uint)Vector512<T>.Count) |
| | | 3931 | | { |
| | 1757 | 3932 | | Vector256<T> lowVector = Vector256.Create(lowInclusive); |
| | 1757 | 3933 | | Vector256<T> rangeVector = Vector256.Create(highInclusive - lowInclusive); |
| | | 3934 | | Vector256<T> inRangeVector; |
| | | 3935 | | |
| | 1757 | 3936 | | ref T current = ref searchSpace; |
| | 1757 | 3937 | | ref T oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector256<T>.Count)); |
| | | 3938 | | |
| | | 3939 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 3940 | | do |
| | | 3941 | | { |
| | 1757 | 3942 | | inRangeVector = TNegator.NegateIfNeeded(Vector256.LessThanOrEqual(Vector256.LoadUnsafe(ref current) |
| | 1757 | 3943 | | if (inRangeVector != Vector256<T>.Zero) |
| | | 3944 | | { |
| | 1147 | 3945 | | return ComputeFirstIndex(ref searchSpace, ref current, inRangeVector); |
| | | 3946 | | } |
| | | 3947 | | |
| | 610 | 3948 | | current = ref Unsafe.Add(ref current, Vector256<T>.Count); |
| | | 3949 | | } |
| | 610 | 3950 | | while (Unsafe.IsAddressLessThan(ref current, ref oneVectorAwayFromEnd)); |
| | | 3951 | | |
| | | 3952 | | // Process the last vector in the search space (which might overlap with already processed elements). |
| | 610 | 3953 | | inRangeVector = TNegator.NegateIfNeeded(Vector256.LessThanOrEqual(Vector256.LoadUnsafe(ref oneVectorAway |
| | 610 | 3954 | | if (inRangeVector != Vector256<T>.Zero) |
| | | 3955 | | { |
| | 177 | 3956 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, inRangeVector); |
| | | 3957 | | } |
| | | 3958 | | } |
| | | 3959 | | else |
| | | 3960 | | { |
| | 5108 | 3961 | | Vector512<T> lowVector = Vector512.Create(lowInclusive); |
| | 5108 | 3962 | | Vector512<T> rangeVector = Vector512.Create(highInclusive - lowInclusive); |
| | | 3963 | | Vector512<T> inRangeVector; |
| | | 3964 | | |
| | 5108 | 3965 | | ref T current = ref searchSpace; |
| | 5108 | 3966 | | ref T oneVectorAwayFromEnd = ref Unsafe.Add(ref searchSpace, (uint)(length - Vector512<T>.Count)); |
| | | 3967 | | |
| | | 3968 | | // Loop until either we've finished all elements or there's less than a vector's-worth remaining. |
| | | 3969 | | do |
| | | 3970 | | { |
| | 13754 | 3971 | | inRangeVector = TNegator.NegateIfNeeded(Vector512.LessThanOrEqual(Vector512.LoadUnsafe(ref current) |
| | 13754 | 3972 | | if (inRangeVector != Vector512<T>.Zero) |
| | | 3973 | | { |
| | 3524 | 3974 | | return ComputeFirstIndex(ref searchSpace, ref current, inRangeVector); |
| | | 3975 | | } |
| | | 3976 | | |
| | 10230 | 3977 | | current = ref Unsafe.Add(ref current, Vector512<T>.Count); |
| | | 3978 | | } |
| | 10230 | 3979 | | while (Unsafe.IsAddressLessThan(ref current, ref oneVectorAwayFromEnd)); |
| | | 3980 | | |
| | | 3981 | | // Process the last vector in the search space (which might overlap with already processed elements). |
| | 1584 | 3982 | | inRangeVector = TNegator.NegateIfNeeded(Vector512.LessThanOrEqual(Vector512.LoadUnsafe(ref oneVectorAway |
| | 1584 | 3983 | | if (inRangeVector != Vector512<T>.Zero) |
| | | 3984 | | { |
| | 443 | 3985 | | return ComputeFirstIndex(ref searchSpace, ref oneVectorAwayFromEnd, inRangeVector); |
| | | 3986 | | } |
| | | 3987 | | } |
| | | 3988 | | |
| | 4796 | 3989 | | return -1; |
| | | 3990 | | } |
| | | 3991 | | |
| | | 3992 | | internal static int LastIndexOfAnyInRange<T>(ref T searchSpace, T lowInclusive, T highInclusive, int length) |
| | | 3993 | | where T : IComparable<T> |
| | | 3994 | | { |
| | 0 | 3995 | | for (int i = length - 1; i >= 0; i--) |
| | | 3996 | | { |
| | 0 | 3997 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 3998 | | if ((lowInclusive.CompareTo(current) <= 0) && (highInclusive.CompareTo(current) >= 0)) |
| | | 3999 | | { |
| | 0 | 4000 | | return i; |
| | | 4001 | | } |
| | | 4002 | | } |
| | | 4003 | | |
| | 0 | 4004 | | return -1; |
| | | 4005 | | } |
| | | 4006 | | |
| | | 4007 | | internal static int LastIndexOfAnyExceptInRange<T>(ref T searchSpace, T lowInclusive, T highInclusive, int lengt |
| | | 4008 | | where T : IComparable<T> |
| | | 4009 | | { |
| | 0 | 4010 | | for (int i = length - 1; i >= 0; i--) |
| | | 4011 | | { |
| | 0 | 4012 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 0 | 4013 | | if ((lowInclusive.CompareTo(current) > 0) || (highInclusive.CompareTo(current) < 0)) |
| | | 4014 | | { |
| | 0 | 4015 | | return i; |
| | | 4016 | | } |
| | | 4017 | | } |
| | | 4018 | | |
| | 0 | 4019 | | return -1; |
| | | 4020 | | } |
| | | 4021 | | |
| | | 4022 | | internal static int LastIndexOfAnyInRangeUnsignedNumber<T>(ref T searchSpace, T lowInclusive, T highInclusive, i |
| | | 4023 | | where T : struct, IUnsignedNumber<T>, IComparisonOperators<T, T, bool> => |
| | 4064 | 4024 | | LastIndexOfAnyInRangeUnsignedNumber<T, DontNegate<T>>(ref searchSpace, lowInclusive, highInclusive, length); |
| | | 4025 | | |
| | | 4026 | | internal static int LastIndexOfAnyExceptInRangeUnsignedNumber<T>(ref T searchSpace, T lowInclusive, T highInclus |
| | | 4027 | | where T : struct, IUnsignedNumber<T>, IComparisonOperators<T, T, bool> => |
| | 4064 | 4028 | | LastIndexOfAnyInRangeUnsignedNumber<T, Negate<T>>(ref searchSpace, lowInclusive, highInclusive, length); |
| | | 4029 | | |
| | | 4030 | | private static int LastIndexOfAnyInRangeUnsignedNumber<T, TNegator>(ref T searchSpace, T lowInclusive, T highInc |
| | | 4031 | | where T : struct, IUnsignedNumber<T>, IComparisonOperators<T, T, bool> |
| | | 4032 | | where TNegator : struct, INegator<T> |
| | | 4033 | | { |
| | | 4034 | | // T must be a type whose comparison operator semantics match that of Vector128/256. |
| | | 4035 | | |
| | 8128 | 4036 | | if (!Vector128.IsHardwareAccelerated || length < Vector128<T>.Count) |
| | | 4037 | | { |
| | 1788 | 4038 | | T rangeInclusive = highInclusive - lowInclusive; |
| | 8408 | 4039 | | for (int i = length - 1; i >= 0; i--) |
| | | 4040 | | { |
| | 3434 | 4041 | | ref T current = ref Unsafe.Add(ref searchSpace, i); |
| | 3434 | 4042 | | if (TNegator.NegateIfNeeded((current - lowInclusive) <= rangeInclusive)) |
| | | 4043 | | { |
| | 1018 | 4044 | | return i; |
| | | 4045 | | } |
| | | 4046 | | } |
| | | 4047 | | } |
| | 6340 | 4048 | | else if (!Vector256.IsHardwareAccelerated || length < Vector256<T>.Count) |
| | | 4049 | | { |
| | 1140 | 4050 | | Vector128<T> lowVector = Vector128.Create(lowInclusive); |
| | 1140 | 4051 | | Vector128<T> rangeVector = Vector128.Create(highInclusive - lowInclusive); |
| | | 4052 | | Vector128<T> inRangeVector; |
| | | 4053 | | |
| | 1140 | 4054 | | nint offset = length - Vector128<T>.Count; |
| | | 4055 | | |
| | | 4056 | | // Loop until either we've finished all elements or there's a vector's-worth or less remaining. |
| | 1284 | 4057 | | while (offset > 0) |
| | | 4058 | | { |
| | 776 | 4059 | | inRangeVector = TNegator.NegateIfNeeded(Vector128.LessThanOrEqual(Vector128.LoadUnsafe(ref searchSpa |
| | 776 | 4060 | | if (inRangeVector != Vector128<T>.Zero) |
| | | 4061 | | { |
| | 632 | 4062 | | return ComputeLastIndex(offset, inRangeVector); |
| | | 4063 | | } |
| | | 4064 | | |
| | 144 | 4065 | | offset -= Vector128<T>.Count; |
| | | 4066 | | } |
| | | 4067 | | |
| | | 4068 | | // Process the first vector in the search space. |
| | 508 | 4069 | | inRangeVector = TNegator.NegateIfNeeded(Vector128.LessThanOrEqual(Vector128.LoadUnsafe(ref searchSpace) |
| | 508 | 4070 | | if (inRangeVector != Vector128<T>.Zero) |
| | | 4071 | | { |
| | 300 | 4072 | | return ComputeLastIndex(offset: 0, inRangeVector); |
| | | 4073 | | } |
| | | 4074 | | } |
| | 5200 | 4075 | | else if (!Vector512.IsHardwareAccelerated || length < Vector512<T>.Count) |
| | | 4076 | | { |
| | 1208 | 4077 | | Vector256<T> lowVector = Vector256.Create(lowInclusive); |
| | 1208 | 4078 | | Vector256<T> rangeVector = Vector256.Create(highInclusive - lowInclusive); |
| | | 4079 | | Vector256<T> inRangeVector; |
| | | 4080 | | |
| | 1208 | 4081 | | nint offset = length - Vector256<T>.Count; |
| | | 4082 | | |
| | | 4083 | | // Loop until either we've finished all elements or there's a vector's-worth or less remaining. |
| | 1436 | 4084 | | while (offset > 0) |
| | | 4085 | | { |
| | 976 | 4086 | | inRangeVector = TNegator.NegateIfNeeded(Vector256.LessThanOrEqual(Vector256.LoadUnsafe(ref searchSpa |
| | 976 | 4087 | | if (inRangeVector != Vector256<T>.Zero) |
| | | 4088 | | { |
| | 748 | 4089 | | return ComputeLastIndex(offset, inRangeVector); |
| | | 4090 | | } |
| | | 4091 | | |
| | 228 | 4092 | | offset -= Vector256<T>.Count; |
| | | 4093 | | } |
| | | 4094 | | |
| | | 4095 | | // Process the first vector in the search space. |
| | 460 | 4096 | | inRangeVector = TNegator.NegateIfNeeded(Vector256.LessThanOrEqual(Vector256.LoadUnsafe(ref searchSpace) |
| | 460 | 4097 | | if (inRangeVector != Vector256<T>.Zero) |
| | | 4098 | | { |
| | 186 | 4099 | | return ComputeLastIndex(offset: 0, inRangeVector); |
| | | 4100 | | } |
| | | 4101 | | } |
| | | 4102 | | else |
| | | 4103 | | { |
| | 3992 | 4104 | | Vector512<T> lowVector = Vector512.Create(lowInclusive); |
| | 3992 | 4105 | | Vector512<T> rangeVector = Vector512.Create(highInclusive - lowInclusive); |
| | | 4106 | | Vector512<T> inRangeVector; |
| | | 4107 | | |
| | 3992 | 4108 | | nint offset = length - Vector512<T>.Count; |
| | | 4109 | | |
| | | 4110 | | // Loop until either we've finished all elements or there's a vector's-worth or less remaining. |
| | 13076 | 4111 | | while (offset > 0) |
| | | 4112 | | { |
| | 11874 | 4113 | | inRangeVector = TNegator.NegateIfNeeded(Vector512.LessThanOrEqual(Vector512.LoadUnsafe(ref searchSpa |
| | 11874 | 4114 | | if (inRangeVector != Vector512<T>.Zero) |
| | | 4115 | | { |
| | 2790 | 4116 | | return ComputeLastIndex(offset, inRangeVector); |
| | | 4117 | | } |
| | | 4118 | | |
| | 9084 | 4119 | | offset -= Vector512<T>.Count; |
| | | 4120 | | } |
| | | 4121 | | |
| | | 4122 | | // Process the first vector in the search space. |
| | 1202 | 4123 | | inRangeVector = TNegator.NegateIfNeeded(Vector512.LessThanOrEqual(Vector512.LoadUnsafe(ref searchSpace) |
| | 1202 | 4124 | | if (inRangeVector != Vector512<T>.Zero) |
| | | 4125 | | { |
| | 296 | 4126 | | return ComputeLastIndex(offset: 0, inRangeVector); |
| | | 4127 | | } |
| | | 4128 | | } |
| | | 4129 | | |
| | 2158 | 4130 | | return -1; |
| | | 4131 | | } |
| | | 4132 | | |
| | | 4133 | | public static int Count<T>(ref T current, T value, int length) where T : IEquatable<T>? |
| | | 4134 | | { |
| | 0 | 4135 | | int count = 0; |
| | | 4136 | | |
| | 0 | 4137 | | ref T end = ref Unsafe.Add(ref current, length); |
| | 0 | 4138 | | if (value is not null) |
| | | 4139 | | { |
| | 0 | 4140 | | while (Unsafe.IsAddressLessThan(ref current, ref end)) |
| | | 4141 | | { |
| | 0 | 4142 | | if (value.Equals(current)) |
| | | 4143 | | { |
| | 0 | 4144 | | count++; |
| | | 4145 | | } |
| | | 4146 | | |
| | 0 | 4147 | | current = ref Unsafe.Add(ref current, 1); |
| | | 4148 | | } |
| | | 4149 | | } |
| | | 4150 | | else |
| | | 4151 | | { |
| | 0 | 4152 | | while (Unsafe.IsAddressLessThan(ref current, ref end)) |
| | | 4153 | | { |
| | 0 | 4154 | | if (current is null) |
| | | 4155 | | { |
| | 0 | 4156 | | count++; |
| | | 4157 | | } |
| | | 4158 | | |
| | 0 | 4159 | | current = ref Unsafe.Add(ref current, 1); |
| | | 4160 | | } |
| | | 4161 | | } |
| | | 4162 | | |
| | 0 | 4163 | | return count; |
| | | 4164 | | } |
| | | 4165 | | |
| | | 4166 | | public static unsafe int CountValueType<T>(ref T current, T value, int length) where T : struct, IEquatable<T> |
| | | 4167 | | { |
| | 0 | 4168 | | int count = 0; |
| | 0 | 4169 | | ref T end = ref Unsafe.Add(ref current, length); |
| | | 4170 | | |
| | 0 | 4171 | | if (Vector128.IsHardwareAccelerated && length >= Vector128<T>.Count) |
| | | 4172 | | { |
| | 0 | 4173 | | if (Vector512.IsHardwareAccelerated && length >= Vector512<T>.Count) |
| | | 4174 | | { |
| | 0 | 4175 | | Vector512<T> targetVector = Vector512.Create(value); |
| | 0 | 4176 | | ref T oneVectorAwayFromEnd = ref Unsafe.Subtract(ref end, Vector512<T>.Count); |
| | 0 | 4177 | | while (Unsafe.IsAddressLessThan(ref current, ref oneVectorAwayFromEnd)) |
| | | 4178 | | { |
| | 0 | 4179 | | count += BitOperations.PopCount(Vector512.Equals(Vector512.LoadUnsafe(ref current), targetVector |
| | 0 | 4180 | | current = ref Unsafe.Add(ref current, Vector512<T>.Count); |
| | | 4181 | | } |
| | | 4182 | | |
| | | 4183 | | // Count the last vector and mask off the elements that were already counted (number of elements bet |
| | 0 | 4184 | | ulong mask = Vector512.Equals(Vector512.LoadUnsafe(ref oneVectorAwayFromEnd), targetVector).ExtractM |
| | 0 | 4185 | | mask >>= (int)((nuint)Unsafe.ByteOffset(ref oneVectorAwayFromEnd, ref current) / (uint)sizeof(T)); |
| | 0 | 4186 | | count += BitOperations.PopCount(mask); |
| | | 4187 | | } |
| | 0 | 4188 | | else if (Vector256.IsHardwareAccelerated && length >= Vector256<T>.Count) |
| | | 4189 | | { |
| | 0 | 4190 | | Vector256<T> targetVector = Vector256.Create(value); |
| | 0 | 4191 | | ref T oneVectorAwayFromEnd = ref Unsafe.Subtract(ref end, Vector256<T>.Count); |
| | 0 | 4192 | | while (Unsafe.IsAddressLessThan(ref current, ref oneVectorAwayFromEnd)) |
| | | 4193 | | { |
| | 0 | 4194 | | count += BitOperations.PopCount(Vector256.Equals(Vector256.LoadUnsafe(ref current), targetVector |
| | 0 | 4195 | | current = ref Unsafe.Add(ref current, Vector256<T>.Count); |
| | | 4196 | | } |
| | | 4197 | | |
| | | 4198 | | // Count the last vector and mask off the elements that were already counted (number of elements bet |
| | 0 | 4199 | | uint mask = Vector256.Equals(Vector256.LoadUnsafe(ref oneVectorAwayFromEnd), targetVector).ExtractMo |
| | 0 | 4200 | | mask >>= (int)((nuint)Unsafe.ByteOffset(ref oneVectorAwayFromEnd, ref current) / (uint)sizeof(T)); |
| | 0 | 4201 | | count += BitOperations.PopCount(mask); |
| | | 4202 | | } |
| | | 4203 | | else |
| | | 4204 | | { |
| | 0 | 4205 | | Vector128<T> targetVector = Vector128.Create(value); |
| | 0 | 4206 | | ref T oneVectorAwayFromEnd = ref Unsafe.Subtract(ref end, Vector128<T>.Count); |
| | 0 | 4207 | | while (Unsafe.IsAddressLessThan(ref current, ref oneVectorAwayFromEnd)) |
| | | 4208 | | { |
| | 0 | 4209 | | count += BitOperations.PopCount(Vector128.Equals(Vector128.LoadUnsafe(ref current), targetVector |
| | 0 | 4210 | | current = ref Unsafe.Add(ref current, Vector128<T>.Count); |
| | | 4211 | | } |
| | | 4212 | | |
| | | 4213 | | // Count the last vector and mask off the elements that were already counted (number of elements bet |
| | 0 | 4214 | | uint mask = Vector128.Equals(Vector128.LoadUnsafe(ref oneVectorAwayFromEnd), targetVector).ExtractMo |
| | 0 | 4215 | | mask >>= (int)((nuint)Unsafe.ByteOffset(ref oneVectorAwayFromEnd, ref current) / (uint)sizeof(T)); |
| | 0 | 4216 | | count += BitOperations.PopCount(mask); |
| | | 4217 | | } |
| | | 4218 | | } |
| | | 4219 | | else |
| | | 4220 | | { |
| | 0 | 4221 | | while (Unsafe.IsAddressLessThan(ref current, ref end)) |
| | | 4222 | | { |
| | 0 | 4223 | | if (current.Equals(value)) |
| | | 4224 | | { |
| | 0 | 4225 | | count++; |
| | | 4226 | | } |
| | | 4227 | | |
| | 0 | 4228 | | current = ref Unsafe.Add(ref current, 1); |
| | | 4229 | | } |
| | | 4230 | | } |
| | | 4231 | | |
| | 0 | 4232 | | return count; |
| | | 4233 | | } |
| | | 4234 | | } |
| | | 4235 | | } |
| | | 4236 | | |