RapidFuzz
Loading...
Searching...
No Matches
simd_sse2.hpp
1/* SPDX-License-Identifier: MIT */
2/* Copyright © 2022 Max Bachmann */
3#pragma once
4
5#include <array>
6#include <emmintrin.h>
7#include <ostream>
8#include <rapidfuzz/details/intrinsics.hpp>
9#include <stdint.h>
10
11namespace rapidfuzz {
12namespace detail {
13namespace simd_sse2 {
14
15template <typename T>
16class native_simd;
17
18template <>
19class native_simd<uint64_t> {
20public:
21 static constexpr int alignment = 16;
22 static const int size = 2;
23 __m128i xmm;
24
25 native_simd() noexcept
26 {}
27
28 native_simd(__m128i val) noexcept : xmm(val)
29 {}
30
31 native_simd(uint64_t a) noexcept
32 {
33 xmm = _mm_set1_epi64x(static_cast<int64_t>(a));
34 }
35
36 native_simd(const uint64_t* p) noexcept
37 {
38 load(p);
39 }
40
41 operator __m128i() const noexcept
42 {
43 return xmm;
44 }
45
46 native_simd load(const uint64_t* p) noexcept
47 {
48 xmm = _mm_set_epi64x(static_cast<int64_t>(p[1]), static_cast<int64_t>(p[0]));
49 return *this;
50 }
51
52 void store(uint64_t* p) const noexcept
53 {
54 _mm_store_si128(reinterpret_cast<__m128i*>(p), xmm);
55 }
56
57 native_simd operator+(const native_simd b) const noexcept
58 {
59 return _mm_add_epi64(xmm, b);
60 }
61
62 native_simd& operator+=(const native_simd b) noexcept
63 {
64 xmm = _mm_add_epi64(xmm, b);
65 return *this;
66 }
67
68 native_simd operator-(const native_simd b) const noexcept
69 {
70 return _mm_sub_epi64(xmm, b);
71 }
72
73 native_simd operator-() const noexcept
74 {
75 return _mm_sub_epi64(_mm_setzero_si128(), xmm);
76 }
77
78 native_simd& operator-=(const native_simd b) noexcept
79 {
80 xmm = _mm_sub_epi64(xmm, b);
81 return *this;
82 }
83};
84
85template <>
86class native_simd<uint32_t> {
87public:
88 static constexpr int alignment = 16;
89 static const int size = 4;
90 __m128i xmm;
91
92 native_simd() noexcept
93 {}
94
95 native_simd(__m128i val) noexcept : xmm(val)
96 {}
97
98 native_simd(uint32_t a) noexcept
99 {
100 xmm = _mm_set1_epi32(static_cast<int>(a));
101 }
102
103 native_simd(const uint64_t* p) noexcept
104 {
105 load(p);
106 }
107
108 operator __m128i() const noexcept
109 {
110 return xmm;
111 }
112
113 native_simd load(const uint64_t* p) noexcept
114 {
115 xmm = _mm_set_epi64x(static_cast<int64_t>(p[1]), static_cast<int64_t>(p[0]));
116 return *this;
117 }
118
119 void store(uint32_t* p) const noexcept
120 {
121 _mm_store_si128(reinterpret_cast<__m128i*>(p), xmm);
122 }
123
124 native_simd operator+(const native_simd b) const noexcept
125 {
126 return _mm_add_epi32(xmm, b);
127 }
128
129 native_simd& operator+=(const native_simd b) noexcept
130 {
131 xmm = _mm_add_epi32(xmm, b);
132 return *this;
133 }
134
135 native_simd operator-(const native_simd b) const noexcept
136 {
137 return _mm_sub_epi32(xmm, b);
138 }
139
140 native_simd operator-() const noexcept
141 {
142 return _mm_sub_epi32(_mm_setzero_si128(), xmm);
143 }
144
145 native_simd& operator-=(const native_simd b) noexcept
146 {
147 xmm = _mm_sub_epi32(xmm, b);
148 return *this;
149 }
150};
151
152template <>
153class native_simd<uint16_t> {
154public:
155 static constexpr int alignment = 16;
156 static const int size = 8;
157 __m128i xmm;
158
159 native_simd() noexcept
160 {}
161
162 native_simd(__m128i val) noexcept : xmm(val)
163 {}
164
165 native_simd(uint16_t a) noexcept
166 {
167 xmm = _mm_set1_epi16(static_cast<short>(a));
168 }
169
170 native_simd(const uint64_t* p) noexcept
171 {
172 load(p);
173 }
174
175 operator __m128i() const noexcept
176 {
177 return xmm;
178 }
179
180 native_simd load(const uint64_t* p) noexcept
181 {
182 xmm = _mm_set_epi64x(static_cast<int64_t>(p[1]), static_cast<int64_t>(p[0]));
183 return *this;
184 }
185
186 void store(uint16_t* p) const noexcept
187 {
188 _mm_store_si128(reinterpret_cast<__m128i*>(p), xmm);
189 }
190
191 native_simd operator+(const native_simd b) const noexcept
192 {
193 return _mm_add_epi16(xmm, b);
194 }
195
196 native_simd& operator+=(const native_simd b) noexcept
197 {
198 xmm = _mm_add_epi16(xmm, b);
199 return *this;
200 }
201
202 native_simd operator-(const native_simd b) const noexcept
203 {
204 return _mm_sub_epi16(xmm, b);
205 }
206
207 native_simd operator-() const noexcept
208 {
209 return _mm_sub_epi16(_mm_setzero_si128(), xmm);
210 }
211
212 native_simd& operator-=(const native_simd b) noexcept
213 {
214 xmm = _mm_sub_epi16(xmm, b);
215 return *this;
216 }
217};
218
219template <>
220class native_simd<uint8_t> {
221public:
222 static constexpr int alignment = 16;
223 static const int size = 16;
224 __m128i xmm;
225
226 native_simd() noexcept
227 {}
228
229 native_simd(__m128i val) noexcept : xmm(val)
230 {}
231
232 native_simd(uint8_t a) noexcept
233 {
234 xmm = _mm_set1_epi8(static_cast<char>(a));
235 }
236
237 native_simd(const uint64_t* p) noexcept
238 {
239 load(p);
240 }
241
242 operator __m128i() const noexcept
243 {
244 return xmm;
245 }
246
247 native_simd load(const uint64_t* p) noexcept
248 {
249 xmm = _mm_set_epi64x(static_cast<int64_t>(p[1]), static_cast<int64_t>(p[0]));
250 return *this;
251 }
252
253 void store(uint8_t* p) const noexcept
254 {
255 _mm_store_si128(reinterpret_cast<__m128i*>(p), xmm);
256 }
257
258 native_simd operator+(const native_simd b) const noexcept
259 {
260 return _mm_add_epi8(xmm, b);
261 }
262
263 native_simd& operator+=(const native_simd b) noexcept
264 {
265 xmm = _mm_add_epi8(xmm, b);
266 return *this;
267 }
268
269 native_simd operator-(const native_simd b) const noexcept
270 {
271 return _mm_sub_epi8(xmm, b);
272 }
273
274 native_simd operator-() const noexcept
275 {
276 return _mm_sub_epi8(_mm_setzero_si128(), xmm);
277 }
278
279 native_simd& operator-=(const native_simd b) noexcept
280 {
281 xmm = _mm_sub_epi8(xmm, b);
282 return *this;
283 }
284};
285
286template <typename T>
287std::ostream& operator<<(std::ostream& os, const native_simd<T>& a)
288{
289 alignas(native_simd<T>::alignment) std::array<T, native_simd<T>::size> res;
290 a.store(&res[0]);
291
292 for (size_t i = res.size() - 1; i != 0; i--)
293 os << std::bitset<std::numeric_limits<T>::digits>(res[i]) << "|";
294
295 os << std::bitset<std::numeric_limits<T>::digits>(res[0]);
296 return os;
297}
298
299template <typename T>
300__m128i hadd_impl(__m128i x) noexcept;
301
302template <>
303inline __m128i hadd_impl<uint8_t>(__m128i x) noexcept
304{
305 return x;
306}
307
308template <>
309inline __m128i hadd_impl<uint16_t>(__m128i x) noexcept
310{
311 const __m128i mask = _mm_set1_epi16(0x001f);
312 __m128i y = _mm_srli_si128(x, 1);
313 x = _mm_add_epi16(x, y);
314 return _mm_and_si128(x, mask);
315}
316
317template <>
318inline __m128i hadd_impl<uint32_t>(__m128i x) noexcept
319{
320 const __m128i mask = _mm_set1_epi32(0x0000003f);
321 x = hadd_impl<uint16_t>(x);
322 __m128i y = _mm_srli_si128(x, 2);
323 x = _mm_add_epi32(x, y);
324 return _mm_and_si128(x, mask);
325}
326
327template <>
328inline __m128i hadd_impl<uint64_t>(__m128i x) noexcept
329{
330 return _mm_sad_epu8(x, _mm_setzero_si128());
331}
332
333template <typename T>
334native_simd<T> popcount_impl(const native_simd<T>& v) noexcept
335{
336 const __m128i m1 = _mm_set1_epi8(0x55);
337 const __m128i m2 = _mm_set1_epi8(0x33);
338 const __m128i m3 = _mm_set1_epi8(0x0F);
339
340 /* Note: if we returned x here it would be like _mm_popcnt_epi1(x) */
341 __m128i y;
342 __m128i x = v;
343 /* add even and odd bits*/
344 y = _mm_srli_epi64(x, 1); // put even bits in odd place
345 y = _mm_and_si128(y, m1); // mask out the even bits (0x55)
346 x = _mm_subs_epu8(x, y); // shortcut to mask even bits and add
347 /* if we just returned x here it would be like popcnt_epi2(x) */
348 /* now add the half nibbles */
349 y = _mm_srli_epi64(x, 2); // move half nibbles in place to add
350 y = _mm_and_si128(y, m2); // mask off the extra half nibbles (0x0f)
351 x = _mm_and_si128(x, m2); // ditto
352 x = _mm_adds_epu8(x, y); // totals are a maximum of 5 bits (0x1f)
353 /* if we just returned x here it would be like popcnt_epi4(x) */
354 /* now add the nibbles */
355 y = _mm_srli_epi64(x, 4); // move nibbles in place to add
356 x = _mm_adds_epu8(x, y); // totals are a maximum of 6 bits (0x3f)
357 x = _mm_and_si128(x, m3); // mask off the extra bits
358
359 /* todo use when sse3 available
360 __m128i lookup = _mm_setr_epi8(0, 1, 1, 2, 1, 2, 2, 3, 1, 2, 2, 3, 2, 3, 3, 4);
361 const __m128i low_mask = _mm_set1_epi8(0x0F);
362 __m128i lo = _mm_and_si128(v, low_mask);
363 __m128i hi = _mm_and_si256(_mm_srli_epi32(v, 4), low_mask);
364 __m128i popcnt1 = _mm_shuffle_epi8(lookup, lo);
365 __m128i popcnt2 = _mm_shuffle_epi8(lookup, hi);
366 __m128i total = _mm_add_epi8(popcnt1, popcnt2);*/
367
368 return hadd_impl<T>(x);
369}
370
371template <typename T>
372std::array<T, native_simd<T>::size> popcount(const native_simd<T>& a) noexcept
373{
374 alignas(native_simd<T>::alignment) std::array<T, native_simd<T>::size> res;
375 popcount_impl(a).store(&res[0]);
376 return res;
377}
378
379// function andnot: a & ~ b
380template <typename T>
381native_simd<T> andnot(const native_simd<T>& a, const native_simd<T>& b)
382{
383 return _mm_andnot_si128(b, a);
384}
385
386static inline native_simd<uint8_t> operator==(const native_simd<uint8_t>& a,
387 const native_simd<uint8_t>& b) noexcept
388{
389 return _mm_cmpeq_epi8(a, b);
390}
391
392static inline native_simd<uint16_t> operator==(const native_simd<uint16_t>& a,
393 const native_simd<uint16_t>& b) noexcept
394{
395 return _mm_cmpeq_epi16(a, b);
396}
397
398static inline native_simd<uint32_t> operator==(const native_simd<uint32_t>& a,
399 const native_simd<uint32_t>& b) noexcept
400{
401 return _mm_cmpeq_epi32(a, b);
402}
403
404static inline native_simd<uint64_t> operator==(const native_simd<uint64_t>& a,
405 const native_simd<uint64_t>& b) noexcept
406{
407 // no 64 compare instruction. Do two 32 bit compares
408 __m128i com32 = _mm_cmpeq_epi32(a, b); // 32 bit compares
409 __m128i com32s = _mm_shuffle_epi32(com32, 0xB1); // swap low and high dwords
410 __m128i test = _mm_and_si128(com32, com32s); // low & high
411 __m128i teste = _mm_srai_epi32(test, 31); // extend sign bit to 32 bits
412 __m128i testee = _mm_shuffle_epi32(teste, 0xF5); // extend sign bit to 64 bits
413 return testee;
414}
415
416template <typename T>
417static inline native_simd<T> operator!=(const native_simd<T>& a, const native_simd<T>& b) noexcept
418{
419 return ~(a == b);
420}
421
422static inline native_simd<uint8_t> operator<<(const native_simd<uint8_t>& a, int b) noexcept
423{
424 char mask = static_cast<char>(0xFF >> b);
425 __m128i am = _mm_and_si128(a, _mm_set1_epi8(mask));
426 return _mm_slli_epi16(am, b);
427}
428
429static inline native_simd<uint16_t> operator<<(const native_simd<uint16_t>& a, int b) noexcept
430{
431 return _mm_slli_epi16(a, b);
432}
433
434static inline native_simd<uint32_t> operator<<(const native_simd<uint32_t>& a, int b) noexcept
435{
436 return _mm_slli_epi32(a, b);
437}
438
439static inline native_simd<uint64_t> operator<<(const native_simd<uint64_t>& a, int b) noexcept
440{
441 return _mm_slli_epi64(a, b);
442}
443
444static inline native_simd<uint8_t> operator>>(const native_simd<uint8_t>& a, int b) noexcept
445{
446 char mask = static_cast<char>(0xFF << b);
447 __m128i am = _mm_and_si128(a, _mm_set1_epi8(mask));
448 return _mm_srli_epi16(am, b);
449}
450
451static inline native_simd<uint16_t> operator>>(const native_simd<uint16_t>& a, int b) noexcept
452{
453 return _mm_srli_epi16(a, b);
454}
455
456static inline native_simd<uint32_t> operator>>(const native_simd<uint32_t>& a, int b) noexcept
457{
458 return _mm_srli_epi32(a, b);
459}
460
461static inline native_simd<uint64_t> operator>>(const native_simd<uint64_t>& a, int b) noexcept
462{
463 return _mm_srli_epi64(a, b);
464}
465
466template <typename T>
467native_simd<T> operator&(const native_simd<T>& a, const native_simd<T>& b) noexcept
468{
469 return _mm_and_si128(a, b);
470}
471
472template <typename T>
473native_simd<T> operator&=(native_simd<T>& a, const native_simd<T>& b) noexcept
474{
475 a = a & b;
476 return a;
477}
478
479template <typename T>
480native_simd<T> operator|(const native_simd<T>& a, const native_simd<T>& b) noexcept
481{
482 return _mm_or_si128(a, b);
483}
484
485template <typename T>
486native_simd<T> operator|=(native_simd<T>& a, const native_simd<T>& b) noexcept
487{
488 a = a | b;
489 return a;
490}
491
492template <typename T>
493native_simd<T> operator^(const native_simd<T>& a, const native_simd<T>& b) noexcept
494{
495 return _mm_xor_si128(a, b);
496}
497
498template <typename T>
499native_simd<T> operator^=(native_simd<T>& a, const native_simd<T>& b) noexcept
500{
501 a = a ^ b;
502 return a;
503}
504
505template <typename T>
506native_simd<T> operator~(const native_simd<T>& a) noexcept
507{
508 return _mm_xor_si128(a, _mm_set1_epi32(-1));
509}
510
511// potentially we want a special native_simd<bool> for this
512static inline native_simd<uint8_t> operator>=(const native_simd<uint8_t>& a,
513 const native_simd<uint8_t>& b) noexcept
514{
515 return _mm_cmpeq_epi8(_mm_max_epu8(a, b), a); // a == max(a,b)
516}
517
518static inline native_simd<uint16_t> operator>=(const native_simd<uint16_t>& a,
519 const native_simd<uint16_t>& b) noexcept
520{
521 /* sse4.1 */
522#if 0
523 return _mm_cmpeq_epi16(_mm_max_epu16(a, b), a); // a == max(a,b)
524#endif
525
526 __m128i s = _mm_subs_epu16(b, a); // b-a, saturated
527 return _mm_cmpeq_epi16(s, _mm_setzero_si128()); // s == 0
528}
529
530static inline native_simd<uint64_t> operator>(const native_simd<uint64_t>& a,
531 const native_simd<uint64_t>& b) noexcept;
532static inline native_simd<uint32_t> operator>(const native_simd<uint32_t>& a,
533 const native_simd<uint32_t>& b) noexcept;
534
535static inline native_simd<uint32_t> operator>=(const native_simd<uint32_t>& a,
536 const native_simd<uint32_t>& b) noexcept
537{
538 /* sse4.1 */
539#if 0
540 return (Vec4ib)_mm_cmpeq_epi32(_mm_max_epu32(a, b), a); // a == max(a,b)
541#endif
542
543 return ~(b > a);
544}
545
546static inline native_simd<uint64_t> operator>=(const native_simd<uint64_t>& a,
547 const native_simd<uint64_t>& b) noexcept
548{
549 return ~(b > a);
550}
551
552template <typename T>
553static inline native_simd<T> operator<=(const native_simd<T>& a, const native_simd<T>& b) noexcept
554{
555 return b >= a;
556}
557
558static inline native_simd<uint8_t> operator>(const native_simd<uint8_t>& a,
559 const native_simd<uint8_t>& b) noexcept
560{
561 return ~(b >= a);
562}
563
564static inline native_simd<uint16_t> operator>(const native_simd<uint16_t>& a,
565 const native_simd<uint16_t>& b) noexcept
566{
567 return ~(b >= a);
568}
569
570static inline native_simd<uint32_t> operator>(const native_simd<uint32_t>& a,
571 const native_simd<uint32_t>& b) noexcept
572{
573 __m128i signbit = _mm_set1_epi32(static_cast<int32_t>(0x80000000));
574 __m128i a1 = _mm_xor_si128(a, signbit);
575 __m128i b1 = _mm_xor_si128(b, signbit);
576 return _mm_cmpgt_epi32(a1, b1); // signed compare
577}
578
579static inline native_simd<uint64_t> operator>(const native_simd<uint64_t>& a,
580 const native_simd<uint64_t>& b) noexcept
581{
582 __m128i sign32 = _mm_set1_epi32(static_cast<int32_t>(0x80000000)); // sign bit of each dword
583 __m128i aflip = _mm_xor_si128(a, sign32); // a with sign bits flipped to use signed compare
584 __m128i bflip = _mm_xor_si128(b, sign32); // b with sign bits flipped to use signed compare
585 __m128i equal = _mm_cmpeq_epi32(a, b); // a == b, dwords
586 __m128i bigger = _mm_cmpgt_epi32(aflip, bflip); // a > b, dwords
587 __m128i biggerl = _mm_shuffle_epi32(bigger, 0xA0); // a > b, low dwords copied to high dwords
588 __m128i eqbig = _mm_and_si128(equal, biggerl); // high part equal and low part bigger
589 __m128i hibig = _mm_or_si128(bigger, eqbig); // high part bigger or high part equal and low part bigger
590 __m128i big = _mm_shuffle_epi32(hibig, 0xF5); // result copied to low part
591 return big;
592}
593
594template <typename T>
595static inline native_simd<T> operator<(const native_simd<T>& a, const native_simd<T>& b) noexcept
596{
597 return b > a;
598}
599
600} // namespace simd_sse2
601} // namespace detail
602} // namespace rapidfuzz
Generated by doxygen 1.9.8