| | | 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.Runtime.CompilerServices; |
| | | 5 | | using System.Runtime.Intrinsics; |
| | | 6 | | using System.Runtime.Intrinsics.Arm; |
| | | 7 | | using System.Runtime.Intrinsics.Wasm; |
| | | 8 | | using System.Runtime.Intrinsics.X86; |
| | | 9 | | |
| | | 10 | | namespace System.Buffers |
| | | 11 | | { |
| | | 12 | | /// <summary> |
| | | 13 | | /// Contains the implementation of core vectorized Teddy matching operations. |
| | | 14 | | /// They determine which buckets contain potential matches for each input position. |
| | | 15 | | /// </summary> |
| | | 16 | | internal static class TeddyHelper |
| | | 17 | | { |
| | | 18 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 19 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 20 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 21 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 22 | | public static (Vector128<byte> Result, Vector128<byte> Prev0) ProcessInputN2( |
| | | 23 | | Vector128<byte> input, |
| | | 24 | | Vector128<byte> prev0, |
| | | 25 | | Vector128<byte> n0Low, Vector128<byte> n0High, |
| | | 26 | | Vector128<byte> n1Low, Vector128<byte> n1High) |
| | | 27 | | { |
| | | 28 | | // See the full description of ProcessInputN3 below for more details. |
| | | 29 | | // This method follows the same pattern as ProcessInputN3, but compares 2 bytes of each bucket at a time ins |
| | | 30 | | // We are dealing with 4 input nibble bitmaps instead of 6, and only 1 result from the previous iteration in |
| | 0 | 31 | | (Vector128<byte> low, Vector128<byte> high) = GetNibbles(input); |
| | | 32 | | |
| | | 33 | | // Shuffle each nibble with the 2 corresponding bitmaps to determine which positions match any bucket. |
| | 0 | 34 | | Vector128<byte> match0 = Shuffle(n0Low, n0High, low, high); |
| | 0 | 35 | | Vector128<byte> result1 = Shuffle(n1Low, n1High, low, high); |
| | | 36 | | |
| | | 37 | | // RightShift1 shifts the match0 vector to the right by 1 place and shifts in 1 byte from the previous itera |
| | 0 | 38 | | Vector128<byte> result0 = RightShift1(prev0, match0); |
| | | 39 | | |
| | | 40 | | // AND the results together to obtain a list of only buckets that match at all 4 nibble positions. |
| | 0 | 41 | | Vector128<byte> result = result0 & result1; |
| | | 42 | | |
| | | 43 | | // Return the result and the current matches for byte 0. |
| | | 44 | | // The next loop iteration, 'match0' will be passed back to this method as 'prev0'. |
| | 0 | 45 | | return (result, match0); |
| | | 46 | | } |
| | | 47 | | |
| | | 48 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 49 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 50 | | public static (Vector256<byte> Result, Vector256<byte> Prev0) ProcessInputN2( |
| | | 51 | | Vector256<byte> input, |
| | | 52 | | Vector256<byte> prev0, |
| | | 53 | | Vector256<byte> n0Low, Vector256<byte> n0High, |
| | | 54 | | Vector256<byte> n1Low, Vector256<byte> n1High) |
| | | 55 | | { |
| | | 56 | | // See comments in 'ProcessInputN2' for Vector128<byte> above. |
| | | 57 | | // This method is the same, but operates on 32 input characters at a time. |
| | 0 | 58 | | (Vector256<byte> low, Vector256<byte> high) = GetNibbles(input); |
| | | 59 | | |
| | 0 | 60 | | Vector256<byte> match0 = Shuffle(n0Low, n0High, low, high); |
| | 0 | 61 | | Vector256<byte> result1 = Shuffle(n1Low, n1High, low, high); |
| | | 62 | | |
| | 0 | 63 | | Vector256<byte> result0 = RightShift1(prev0, match0); |
| | | 64 | | |
| | 0 | 65 | | Vector256<byte> result = result0 & result1; |
| | | 66 | | |
| | 0 | 67 | | return (result, match0); |
| | | 68 | | } |
| | | 69 | | |
| | | 70 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 71 | | [CompExactlyDependsOn(typeof(Avx512Vbmi))] |
| | | 72 | | public static (Vector512<byte> Result, Vector512<byte> Prev0) ProcessInputN2( |
| | | 73 | | Vector512<byte> input, |
| | | 74 | | Vector512<byte> prev0, |
| | | 75 | | Vector512<byte> n0Low, Vector512<byte> n0High, |
| | | 76 | | Vector512<byte> n1Low, Vector512<byte> n1High) |
| | | 77 | | { |
| | | 78 | | // See comments in 'ProcessInputN2' for Vector128<byte> above. |
| | | 79 | | // This method is the same, but operates on 64 input characters at a time. |
| | 0 | 80 | | (Vector512<byte> low, Vector512<byte> high) = GetNibbles(input); |
| | | 81 | | |
| | 0 | 82 | | Vector512<byte> match0 = Shuffle(n0Low, n0High, low, high); |
| | 0 | 83 | | Vector512<byte> result1 = Shuffle(n1Low, n1High, low, high); |
| | | 84 | | |
| | 0 | 85 | | Vector512<byte> result0 = RightShift1(prev0, match0); |
| | | 86 | | |
| | 0 | 87 | | Vector512<byte> result = result0 & result1; |
| | | 88 | | |
| | 0 | 89 | | return (result, match0); |
| | | 90 | | } |
| | | 91 | | |
| | | 92 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 93 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 94 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 95 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 96 | | public static (Vector128<byte> Result, Vector128<byte> Prev0, Vector128<byte> Prev1) ProcessInputN3( |
| | | 97 | | Vector128<byte> input, |
| | | 98 | | Vector128<byte> prev0, Vector128<byte> prev1, |
| | | 99 | | Vector128<byte> n0Low, Vector128<byte> n0High, |
| | | 100 | | Vector128<byte> n1Low, Vector128<byte> n1High, |
| | | 101 | | Vector128<byte> n2Low, Vector128<byte> n2High) |
| | | 102 | | { |
| | | 103 | | // This is the core operation of the Teddy algorithm that determines which of the buckets contain potential |
| | | 104 | | // Every input bitmap argument (n0Low, n0High, ...) encodes a mapping of each of the possible 16 nibble valu |
| | | 105 | | // We test each nibble in the input against these bitmaps to determine which buckets match a given nibble. |
| | | 106 | | // We then AND together these results to obtain only a list of buckets that match at all 6 nibble positions. |
| | | 107 | | // Each byte of the result represents an 8-bit bitmask of buckets that may match at each position. |
| | 0 | 108 | | (Vector128<byte> low, Vector128<byte> high) = GetNibbles(input); |
| | | 109 | | |
| | | 110 | | // Shuffle each nibble with the 3 corresponding bitmaps to determine which positions match any bucket. |
| | 0 | 111 | | Vector128<byte> match0 = Shuffle(n0Low, n0High, low, high); |
| | 0 | 112 | | Vector128<byte> match1 = Shuffle(n1Low, n1High, low, high); |
| | 0 | 113 | | Vector128<byte> result2 = Shuffle(n2Low, n2High, low, high); |
| | | 114 | | |
| | | 115 | | // match0 contain the information for bucket matches at position 0. |
| | | 116 | | // match1 contain the information for bucket matches at position 1. |
| | | 117 | | // result2 contain the information for bucket matches at position 2. |
| | | 118 | | // If we imagine that we only have 1 bucket with 1 string "ABC", the bitmaps we've just obtained encode the |
| | | 119 | | // match0 tells us at which positions we matched the letter 'A' |
| | | 120 | | // match1 tells us at which positions we matched the letter 'B' |
| | | 121 | | // result2 tells us at which positions we matched the letter 'C' |
| | | 122 | | // If input represents the text "BC text ABC text", they would contain: |
| | | 123 | | // input: [B, C, , t, e, x, t, , A, B, C, , t, e, x, t] |
| | | 124 | | // match0: [0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0] |
| | | 125 | | // match1: [1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] |
| | | 126 | | // result2: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] |
| | | 127 | | // ^ ^ ^ |
| | | 128 | | // Note how the input contains the string ABC, but the matches are not aligned, so we can't just AND them to |
| | | 129 | | // To solve this, we shift 'match0' to the right by 2 places and 'match1' to the right by 1 place. |
| | | 130 | | // result0: [?, ?, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0] |
| | | 131 | | // result1: [?, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0] |
| | | 132 | | // result2: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] |
| | | 133 | | // ^ ^ ^ |
| | | 134 | | // The results are now aligned, but we don't know whether the first two positions matched result0 and result |
| | | 135 | | // To replace the missing bytes, we remember the matches from the previous loop iteration, and look at their |
| | | 136 | | // If the previous loop iteration ended on the character 'A', we might even have an earlier match. |
| | | 137 | | // For example, if the previous input was "Random strings A": |
| | | 138 | | // prev0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1] |
| | | 139 | | // result0: [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] |
| | | 140 | | // ^ ^ |
| | | 141 | | // We will merge the last two bytes of 'prev0' into 'result0' and the last byte of 'prev1' into 'result1' |
| | | 142 | | // result0: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] |
| | | 143 | | // result1: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] |
| | | 144 | | // result2: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] |
| | | 145 | | // |
| | | 146 | | // RightShift1 and RightShift2 perform the above operation of shifting the match vectors |
| | | 147 | | // to the right by 1 and 2 places and shifting in the bytes from the previous iteration. |
| | 0 | 148 | | Vector128<byte> result0 = RightShift2(prev0, match0); |
| | 0 | 149 | | Vector128<byte> result1 = RightShift1(prev1, match1); |
| | | 150 | | |
| | | 151 | | // AND the results together to obtain a list of only buckets that match at all 6 nibble positions. |
| | | 152 | | // result: [0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0] |
| | | 153 | | // ^ ^ |
| | | 154 | | // Note that we found the match at index 1, even though that match started 2 bytes earlier, at the end of th |
| | | 155 | | // The caller must account for that when verifying potential matches, see 'MatchStartOffsetN3 = 2' in 'Ascii |
| | 0 | 156 | | Vector128<byte> result = result0 & result1 & result2; |
| | | 157 | | |
| | | 158 | | // Return the result and the current matches for byte 0 and 1. |
| | | 159 | | // The next loop iteration, 'match0' and 'match1' will be passed back to this method as 'prev0' and 'prev1'. |
| | 0 | 160 | | return (result, match0, match1); |
| | | 161 | | } |
| | | 162 | | |
| | | 163 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 164 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 165 | | public static (Vector256<byte> Result, Vector256<byte> Prev0, Vector256<byte> Prev1) ProcessInputN3( |
| | | 166 | | Vector256<byte> input, |
| | | 167 | | Vector256<byte> prev0, Vector256<byte> prev1, |
| | | 168 | | Vector256<byte> n0Low, Vector256<byte> n0High, |
| | | 169 | | Vector256<byte> n1Low, Vector256<byte> n1High, |
| | | 170 | | Vector256<byte> n2Low, Vector256<byte> n2High) |
| | | 171 | | { |
| | | 172 | | // See comments in 'ProcessInputN3' for Vector128<byte> above. |
| | | 173 | | // This method is the same, but operates on 32 input characters at a time. |
| | 0 | 174 | | (Vector256<byte> low, Vector256<byte> high) = GetNibbles(input); |
| | | 175 | | |
| | 0 | 176 | | Vector256<byte> match0 = Shuffle(n0Low, n0High, low, high); |
| | 0 | 177 | | Vector256<byte> match1 = Shuffle(n1Low, n1High, low, high); |
| | 0 | 178 | | Vector256<byte> result2 = Shuffle(n2Low, n2High, low, high); |
| | | 179 | | |
| | 0 | 180 | | Vector256<byte> result0 = RightShift2(prev0, match0); |
| | 0 | 181 | | Vector256<byte> result1 = RightShift1(prev1, match1); |
| | | 182 | | |
| | 0 | 183 | | Vector256<byte> result = result0 & result1 & result2; |
| | | 184 | | |
| | 0 | 185 | | return (result, match0, match1); |
| | | 186 | | } |
| | | 187 | | |
| | | 188 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 189 | | [CompExactlyDependsOn(typeof(Avx512Vbmi))] |
| | | 190 | | public static (Vector512<byte> Result, Vector512<byte> Prev0, Vector512<byte> Prev1) ProcessInputN3( |
| | | 191 | | Vector512<byte> input, |
| | | 192 | | Vector512<byte> prev0, Vector512<byte> prev1, |
| | | 193 | | Vector512<byte> n0Low, Vector512<byte> n0High, |
| | | 194 | | Vector512<byte> n1Low, Vector512<byte> n1High, |
| | | 195 | | Vector512<byte> n2Low, Vector512<byte> n2High) |
| | | 196 | | { |
| | | 197 | | // See comments in 'ProcessInputN3' for Vector128<byte> above. |
| | | 198 | | // This method is the same, but operates on 64 input characters at a time. |
| | 0 | 199 | | (Vector512<byte> low, Vector512<byte> high) = GetNibbles(input); |
| | | 200 | | |
| | 0 | 201 | | Vector512<byte> match0 = Shuffle(n0Low, n0High, low, high); |
| | 0 | 202 | | Vector512<byte> match1 = Shuffle(n1Low, n1High, low, high); |
| | 0 | 203 | | Vector512<byte> result2 = Shuffle(n2Low, n2High, low, high); |
| | | 204 | | |
| | 0 | 205 | | Vector512<byte> result0 = RightShift2(prev0, match0); |
| | 0 | 206 | | Vector512<byte> result1 = RightShift1(prev1, match1); |
| | | 207 | | |
| | 0 | 208 | | Vector512<byte> result = result0 & result1 & result2; |
| | | 209 | | |
| | 0 | 210 | | return (result, match0, match1); |
| | | 211 | | } |
| | | 212 | | |
| | | 213 | | /// <summary> |
| | | 214 | | /// Read two <see cref="Vector128<UInt16>" /> and concatenate their lower bytes together into a single <se |
| | | 215 | | /// </summary> |
| | | 216 | | /// <remarks> |
| | | 217 | | /// On X86, characters above 32767 are turned into 0, but we account for that by not using Teddy if any of the s |
| | | 218 | | /// </remarks> |
| | | 219 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 220 | | [CompExactlyDependsOn(typeof(Sse2))] |
| | | 221 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 222 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 223 | | public static Vector128<byte> LoadAndPack16AsciiChars(ref char source) |
| | | 224 | | { |
| | | 225 | | Vector128<ushort> source0 = Vector128.LoadUnsafe(ref source); |
| | 0 | 226 | | Vector128<ushort> source1 = Vector128.LoadUnsafe(ref source, (nuint)Vector128<ushort>.Count); |
| | | 227 | | |
| | 0 | 228 | | if (Sse2.IsSupported) |
| | | 229 | | { |
| | 0 | 230 | | return Sse2.PackUnsignedSaturate(source0.AsInt16(), source1.AsInt16()); |
| | | 231 | | } |
| | | 232 | | else if (AdvSimd.Arm64.IsSupported) |
| | | 233 | | { |
| | | 234 | | return AdvSimd.Arm64.UnzipEven(source0.AsByte(), source1.AsByte()); |
| | | 235 | | } |
| | | 236 | | else if (PackedSimd.IsSupported) |
| | | 237 | | { |
| | | 238 | | return PackedSimd.ConvertNarrowingSaturateUnsigned(source0.AsInt16(), source1.AsInt16()); |
| | | 239 | | } |
| | | 240 | | else |
| | | 241 | | { |
| | | 242 | | // We explicitly recheck each IsSupported query to ensure that the trimmer can see which paths are live/ |
| | 0 | 243 | | ThrowHelper.ThrowUnreachableException(); |
| | | 244 | | return default; |
| | | 245 | | } |
| | | 246 | | } |
| | | 247 | | |
| | | 248 | | /// <summary> |
| | | 249 | | /// Read two <see cref="Vector256<UInt16>" /> and concatenate their lower bytes together into a single <se |
| | | 250 | | /// </summary> |
| | | 251 | | /// <remarks> |
| | | 252 | | /// On X86, characters above 32767 are turned into 0, but we account for that by not using Teddy if any of the s |
| | | 253 | | /// </remarks> |
| | | 254 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 255 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 256 | | public static Vector256<byte> LoadAndPack32AsciiChars(ref char source) |
| | | 257 | | { |
| | 0 | 258 | | Vector256<ushort> source0 = Vector256.LoadUnsafe(ref source); |
| | 0 | 259 | | Vector256<ushort> source1 = Vector256.LoadUnsafe(ref source, (nuint)Vector256<ushort>.Count); |
| | | 260 | | |
| | 0 | 261 | | Vector256<byte> packed = Avx2.PackUnsignedSaturate(source0.AsInt16(), source1.AsInt16()); |
| | | 262 | | |
| | 0 | 263 | | return PackedSpanHelpers.FixUpPackedVector256Result(packed); |
| | | 264 | | } |
| | | 265 | | |
| | | 266 | | /// <summary> |
| | | 267 | | /// Read two <see cref="Vector512<UInt16>" /> and concatenate their lower bytes together into a single <se |
| | | 268 | | /// </summary> |
| | | 269 | | /// <remarks> |
| | | 270 | | /// On X86, characters above 32767 are turned into 0, but we account for that by not using Teddy if any of the s |
| | | 271 | | /// </remarks> |
| | | 272 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 273 | | [CompExactlyDependsOn(typeof(Avx512BW))] |
| | | 274 | | public static Vector512<byte> LoadAndPack64AsciiChars(ref char source) |
| | | 275 | | { |
| | 0 | 276 | | Vector512<ushort> source0 = Vector512.LoadUnsafe(ref source); |
| | 0 | 277 | | Vector512<ushort> source1 = Vector512.LoadUnsafe(ref source, (nuint)Vector512<ushort>.Count); |
| | | 278 | | |
| | 0 | 279 | | Vector512<byte> packed = Avx512BW.PackUnsignedSaturate(source0.AsInt16(), source1.AsInt16()); |
| | | 280 | | |
| | 0 | 281 | | return PackedSpanHelpers.FixUpPackedVector512Result(packed); |
| | | 282 | | } |
| | | 283 | | |
| | | 284 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 285 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 286 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 287 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 288 | | private static (Vector128<byte> Low, Vector128<byte> High) GetNibbles(Vector128<byte> input) |
| | | 289 | | { |
| | | 290 | | // 'low' is not strictly correct here, but we take advantage of Ssse3.Shuffle's behavior |
| | | 291 | | // of doing an implicit 'AND 0xF' in order to skip the redundant AND. PackedSimd.Swizzle |
| | | 292 | | // and AdvSimd's table lookup return 0 for indices >= 16 (instead of masking the low 4 |
| | | 293 | | // bits), so they need the explicit AND. |
| | 0 | 294 | | Vector128<byte> low = Ssse3.IsSupported |
| | 0 | 295 | | ? input |
| | 0 | 296 | | : input & Vector128.Create((byte)0xF); |
| | | 297 | | |
| | 0 | 298 | | Vector128<byte> high = input >>> 4; |
| | | 299 | | |
| | 0 | 300 | | return (low, high); |
| | | 301 | | } |
| | | 302 | | |
| | | 303 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 304 | | private static (Vector256<byte> Low, Vector256<byte> High) GetNibbles(Vector256<byte> input) |
| | | 305 | | { |
| | | 306 | | // 'low' is not strictly correct here, but we take advantage of Avx2.Shuffle's behavior |
| | | 307 | | // of doing an implicit 'AND 0xF' in order to skip the redundant AND. |
| | 0 | 308 | | Vector256<byte> low = input; |
| | | 309 | | |
| | 0 | 310 | | Vector256<byte> high = input >>> 4; |
| | | 311 | | |
| | 0 | 312 | | return (low, high); |
| | | 313 | | } |
| | | 314 | | |
| | | 315 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 316 | | private static (Vector512<byte> Low, Vector512<byte> High) GetNibbles(Vector512<byte> input) |
| | | 317 | | { |
| | | 318 | | // 'low' is not strictly correct here, but we take advantage of Avx512BW.Shuffle's behavior |
| | | 319 | | // of doing an implicit 'AND 0xF' in order to skip the redundant AND. |
| | 0 | 320 | | Vector512<byte> low = input; |
| | | 321 | | |
| | 0 | 322 | | Vector512<byte> high = input >>> 4; |
| | | 323 | | |
| | 0 | 324 | | return (low, high); |
| | | 325 | | } |
| | | 326 | | |
| | | 327 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 328 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 329 | | [CompExactlyDependsOn(typeof(AdvSimd.Arm64))] |
| | | 330 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 331 | | private static Vector128<byte> Shuffle(Vector128<byte> maskLow, Vector128<byte> maskHigh, Vector128<byte> low, V |
| | | 332 | | { |
| | 0 | 333 | | return SearchValues.ShuffleNativeModified(maskLow, low) & Vector128.ShuffleNative(maskHigh, high); |
| | | 334 | | } |
| | | 335 | | |
| | | 336 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 337 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 338 | | private static Vector256<byte> Shuffle(Vector256<byte> maskLow, Vector256<byte> maskHigh, Vector256<byte> low, V |
| | | 339 | | { |
| | 0 | 340 | | return Avx2.Shuffle(maskLow, low) & Avx2.Shuffle(maskHigh, high); |
| | | 341 | | } |
| | | 342 | | |
| | | 343 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 344 | | [CompExactlyDependsOn(typeof(Avx512BW))] |
| | | 345 | | private static Vector512<byte> Shuffle(Vector512<byte> maskLow, Vector512<byte> maskHigh, Vector512<byte> low, V |
| | | 346 | | { |
| | 0 | 347 | | return Avx512BW.Shuffle(maskLow, low) & Avx512BW.Shuffle(maskHigh, high); |
| | | 348 | | } |
| | | 349 | | |
| | | 350 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 351 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 352 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 353 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 354 | | private static Vector128<byte> RightShift1(Vector128<byte> left, Vector128<byte> right) |
| | | 355 | | { |
| | | 356 | | // Given input vectors like |
| | | 357 | | // left: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] |
| | | 358 | | // right: [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31] |
| | | 359 | | // We want to shift the last element of left (15) to be the first element of the result |
| | | 360 | | // result: [15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30] |
| | | 361 | | |
| | | 362 | | if (Ssse3.IsSupported) |
| | | 363 | | { |
| | 0 | 364 | | return Ssse3.AlignRight(right, left, 15); |
| | | 365 | | } |
| | | 366 | | else if (AdvSimd.IsSupported) |
| | | 367 | | { |
| | | 368 | | return AdvSimd.ExtractVector128(left, right, 15); |
| | | 369 | | } |
| | | 370 | | else if (PackedSimd.IsSupported) |
| | | 371 | | { |
| | | 372 | | // Call PackedSimd.Swizzle directly (i8x16.swizzle) rather than through |
| | | 373 | | // Vector128.ShuffleNative's dispatcher chain, which the Mono SIMD intrinsic |
| | | 374 | | // recognizer doesn't always lower cleanly. Swizzle clamps out-of-range |
| | | 375 | | // indices (>= 16) to 0 so we can compose the two halves with OR. |
| | | 376 | | Vector128<byte> leftPart = PackedSimd.Swizzle(left, |
| | | 377 | | Vector128.Create((byte)15, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0 |
| | | 378 | | Vector128<byte> rightPart = PackedSimd.Swizzle(right, |
| | | 379 | | Vector128.Create((byte)0xFF, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14)); |
| | | 380 | | return leftPart | rightPart; |
| | | 381 | | } |
| | | 382 | | else |
| | | 383 | | { |
| | | 384 | | // We explicitly recheck each IsSupported query to ensure that the trimmer can see which paths are live/ |
| | 0 | 385 | | ThrowHelper.ThrowUnreachableException(); |
| | | 386 | | return default; |
| | | 387 | | } |
| | | 388 | | } |
| | | 389 | | |
| | | 390 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 391 | | [CompExactlyDependsOn(typeof(Ssse3))] |
| | | 392 | | [CompExactlyDependsOn(typeof(AdvSimd))] |
| | | 393 | | [CompExactlyDependsOn(typeof(PackedSimd))] |
| | | 394 | | private static Vector128<byte> RightShift2(Vector128<byte> left, Vector128<byte> right) |
| | | 395 | | { |
| | | 396 | | // Given input vectors like |
| | | 397 | | // left: [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15] |
| | | 398 | | // right: [16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31] |
| | | 399 | | // We want to shift the last two elements of left (14, 15) to be the first elements of the result |
| | | 400 | | // result: [14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29] |
| | | 401 | | |
| | | 402 | | if (Ssse3.IsSupported) |
| | | 403 | | { |
| | 0 | 404 | | return Ssse3.AlignRight(right, left, 14); |
| | | 405 | | } |
| | | 406 | | else if (AdvSimd.IsSupported) |
| | | 407 | | { |
| | | 408 | | return AdvSimd.ExtractVector128(left, right, 14); |
| | | 409 | | } |
| | | 410 | | else if (PackedSimd.IsSupported) |
| | | 411 | | { |
| | | 412 | | Vector128<byte> leftPart = PackedSimd.Swizzle(left, |
| | | 413 | | Vector128.Create((byte)14, 15, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xFF, 0xF |
| | | 414 | | Vector128<byte> rightPart = PackedSimd.Swizzle(right, |
| | | 415 | | Vector128.Create((byte)0xFF, 0xFF, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13)); |
| | | 416 | | return leftPart | rightPart; |
| | | 417 | | } |
| | | 418 | | else |
| | | 419 | | { |
| | | 420 | | // We explicitly recheck each IsSupported query to ensure that the trimmer can see which paths are live/ |
| | 0 | 421 | | ThrowHelper.ThrowUnreachableException(); |
| | | 422 | | return default; |
| | | 423 | | } |
| | | 424 | | } |
| | | 425 | | |
| | | 426 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 427 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 428 | | private static Vector256<byte> RightShift1(Vector256<byte> left, Vector256<byte> right) |
| | | 429 | | { |
| | | 430 | | // Given input vectors like |
| | | 431 | | // left: 0, 1, 2, 3, 4, 5, ... , 26, 27, 28, 29, 30, [31] |
| | | 432 | | // right: 32, 33, 34, 35, 36, 37, ... , 58, 59, 60, 61, 62, 63 |
| | | 433 | | // We want to shift the last element of left (31) to be the first element of the result |
| | | 434 | | // result: [31], 32, 33, 34, 35, 36, ... , 57, 58, 59, 60, 61, 62 |
| | | 435 | | // |
| | | 436 | | // Avx2.AlignRight acts like two separate Ssse3.AlignRight calls on the lower and upper halves of the source |
| | | 437 | | // Result of Avx2.AlignRight(right, left, 15) is |
| | | 438 | | // lower: [15], 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, |
| | | 439 | | // upper: [31], 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62 |
| | | 440 | | // note how elements at indexes 0 and 16 are off by 16 places. |
| | | 441 | | // We want to read 31 instead of 15 and 47 instead of 31. |
| | | 442 | | // |
| | | 443 | | // To achieve that we create a temporary value where we combine the second half of the first operand and the |
| | | 444 | | // left: 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, [ 16, 17, 18, 19, 20, 21, 22, 2 |
| | | 445 | | // right: [ 32, 33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47 ], 48, 49, 50, 51, 52, 53, 54, 5 |
| | | 446 | | // result: 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, [31], 32, 33, 34, 35, 36, 37, 38, 3 |
| | | 447 | | // This effectively shifts the 0th and 16th element by 16 places (note values 31 and 47). |
| | | 448 | | |
| | 0 | 449 | | Vector256<byte> leftShifted = Avx2.Permute2x128(left, right, (1 << 0) + (2 << 4)); |
| | 0 | 450 | | return Avx2.AlignRight(right, leftShifted, 15); |
| | | 451 | | } |
| | | 452 | | |
| | | 453 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 454 | | [CompExactlyDependsOn(typeof(Avx2))] |
| | | 455 | | private static Vector256<byte> RightShift2(Vector256<byte> left, Vector256<byte> right) |
| | | 456 | | { |
| | | 457 | | // See comments in 'RightShift1(Vector256<byte> left, Vector256<byte> right)' above. |
| | 0 | 458 | | Vector256<byte> leftShifted = Avx2.Permute2x128(left, right, (1 << 0) + (2 << 4)); |
| | 0 | 459 | | return Avx2.AlignRight(right, leftShifted, 14); |
| | | 460 | | } |
| | | 461 | | |
| | | 462 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 463 | | [CompExactlyDependsOn(typeof(Avx512Vbmi))] |
| | | 464 | | private static Vector512<byte> RightShift1(Vector512<byte> left, Vector512<byte> right) |
| | | 465 | | { |
| | | 466 | | // Given input vectors like |
| | | 467 | | // left: 0, 1, 2, 3, 4, 5, ... , 58, 59, 60, 61, 62, [63] |
| | | 468 | | // right: 64, 65, 66, 67, 68, 69, ... , 122, 123, 124, 125, 126, 127 |
| | | 469 | | // We want to shift the last element of left (63) to be the first element of the result |
| | | 470 | | // result: [63], 64, 65, 66, 67, 68, ... , 121, 122, 123, 124, 125, 126 |
| | | 471 | | |
| | 0 | 472 | | return Avx512Vbmi.PermuteVar64x8x2(left, Vector512.CreateSequence<byte>(63, 1), right); |
| | | 473 | | } |
| | | 474 | | |
| | | 475 | | [MethodImpl(MethodImplOptions.AggressiveInlining)] |
| | | 476 | | [CompExactlyDependsOn(typeof(Avx512Vbmi))] |
| | | 477 | | private static Vector512<byte> RightShift2(Vector512<byte> left, Vector512<byte> right) |
| | | 478 | | { |
| | | 479 | | // Given input vectors like |
| | | 480 | | // left: 0, 1, 2, 3, 4, 5, ... , 58, 59, 60, 61, [62], [63] |
| | | 481 | | // right: 64, 65, 66, 67, 68, 69, ... , 122, 123, 124, 125, 126, 127 |
| | | 482 | | // We want to shift the last two elements of left (62, 63) to be the first elements of the result |
| | | 483 | | // result: [62], [63], 64, 65, 66, 67, 68, ... , 121, 122, 123, 124, 125 |
| | | 484 | | |
| | 0 | 485 | | return Avx512Vbmi.PermuteVar64x8x2(left, Vector512.CreateSequence<byte>(62, 1), right); |
| | | 486 | | } |
| | | 487 | | } |
| | | 488 | | } |
| | | 489 | | |