17#if defined(HIGHWAY_HWY_CONTRIB_SORT_TRAITS_TOGGLE) == \
18 defined(HWY_TARGET_TOGGLE)
19#ifdef HIGHWAY_HWY_CONTRIB_SORT_TRAITS_TOGGLE
20#undef HIGHWAY_HWY_CONTRIB_SORT_TRAITS_TOGGLE
22#define HIGHWAY_HWY_CONTRIB_SORT_TRAITS_TOGGLE
38template <
typename LaneTypeArg,
typename KeyTypeArg>
40 static constexpr bool Is128() {
return false; }
49 return IsSame<KeyTypeArg, float16_t>() ?
"f16"
50 : IsSame<KeyTypeArg, float>() ?
"f32"
51 : IsSame<KeyTypeArg, double>() ?
"f64"
52 : IsSame<KeyTypeArg, int16_t>() ?
"i16"
53 : IsSame<KeyTypeArg, int32_t>() ?
"i32"
54 : IsSame<KeyTypeArg, int64_t>() ?
"i64"
55 : IsSame<KeyTypeArg, uint16_t>() ?
"u32"
56 : IsSame<KeyTypeArg, uint32_t>() ?
"u32"
57 : IsSame<KeyTypeArg, uint64_t>() ?
"u64"
58 : IsSame<KeyTypeArg, hwy::K32V32>() ?
"k+v=64"
68template <
class D, HWY_IF_FLOAT_OR_SPECIAL_D(D)>
72template <
class D, HWY_IF_NOT_FLOAT_NOR_SPECIAL_D(D)>
77template <
class D, HWY_IF_FLOAT_OR_SPECIAL_D(D)>
81template <
class D, HWY_IF_NOT_FLOAT_NOR_SPECIAL_D(D)>
87template <
class D, HWY_IF_FLOAT_OR_SPECIAL_D(D)>
92 using VU =
Vec<
decltype(du)>;
93 using TU =
TFromD<
decltype(du)>;
114template <
class D, HWY_IF_FLOAT_OR_SPECIAL_D(D)>
119 using VU =
Vec<
decltype(du)>;
120 using TU =
TFromD<
decltype(du)>;
140template <
class D, HWY_IF_NOT_FLOAT_NOR_SPECIAL_D(D)>
145template <
class D, HWY_IF_NOT_FLOAT_NOR_SPECIAL_D(D)>
147 return Sub(v,
Set(
d, TFromD<D>{1}));
150#if VQSORT_ENABLED || HWY_IDE
155template <
typename LaneType,
typename KeyType>
156struct KeyLane :
public KeyLaneBase<LaneType, KeyType> {
158 HWY_INLINE void Swap(LaneType* a, LaneType* b)
const {
164 template <
class V,
class M>
165 HWY_INLINE V CompressKeys(V keys, M mask)
const {
171 HWY_INLINE Vec<D> SetKey(D d,
const LaneType* key)
const {
176 HWY_INLINE Mask<D> EqualKeys(D , Vec<D> a, Vec<D> b)
const {
181 HWY_INLINE Mask<D> NotEqualKeys(D , Vec<D> a, Vec<D> b)
const {
187 HWY_INLINE bool NoKeyDifference(D , Vec<D> diff)
const {
189 const RebindToUnsigned<D> du;
193 HWY_INLINE bool Equal1(
const LaneType* a,
const LaneType* b)
const {
198 HWY_INLINE Vec<D> ReverseKeys(D d, Vec<D> v)
const {
203 HWY_INLINE Vec<D> ReverseKeys2(D d, Vec<D> v)
const {
208 HWY_INLINE Vec<D> ReverseKeys4(D d, Vec<D> v)
const {
213 HWY_INLINE Vec<D> ReverseKeys8(D d, Vec<D> v)
const {
218 HWY_INLINE Vec<D> ReverseKeys16(D d, Vec<D> v)
const {
219 static_assert(SortConstants::kMaxCols <= 16,
"Assumes u32x16 = 512 bit");
220 return ReverseKeys(d, v);
224 HWY_INLINE V OddEvenKeys(
const V odd,
const V even)
const {
228 template <
class D, HWY_IF_T_SIZE_D(D, 2)>
229 HWY_INLINE Vec<D> SwapAdjacentPairs(D d,
const Vec<D> v)
const {
230 const Repartition<uint32_t, D> du32;
233 template <
class D, HWY_IF_T_SIZE_D(D, 4)>
234 HWY_INLINE Vec<D> SwapAdjacentPairs(D ,
const Vec<D> v)
const {
237 template <
class D, HWY_IF_T_SIZE_D(D, 8)>
238 HWY_INLINE Vec<D> SwapAdjacentPairs(D ,
const Vec<D> v)
const {
242 template <
class D, HWY_IF_NOT_T_SIZE_D(D, 8)>
243 HWY_INLINE Vec<D> SwapAdjacentQuads(D d,
const Vec<D> v)
const {
245 const RepartitionToWide<D> dw;
247 const RepartitionToWide<RebindToUnsigned<D>> dw;
251 template <
class D, HWY_IF_T_SIZE_D(D, 8)>
252 HWY_INLINE Vec<D> SwapAdjacentQuads(D d,
const Vec<D> v)
const {
257 template <
class D, HWY_IF_NOT_T_SIZE_D(D, 8)>
258 HWY_INLINE Vec<D> OddEvenPairs(D d,
const Vec<D> odd,
259 const Vec<D> even)
const {
261 const RepartitionToWide<D> dw;
263 const RepartitionToWide<RebindToUnsigned<D>> dw;
267 template <
class D, HWY_IF_T_SIZE_D(D, 8)>
268 HWY_INLINE Vec<D> OddEvenPairs(D , Vec<D> odd, Vec<D> even)
const {
272 template <
class D, HWY_IF_NOT_T_SIZE_D(D, 8)>
273 HWY_INLINE Vec<D> OddEvenQuads(D d, Vec<D> odd, Vec<D> even)
const {
275 const RepartitionToWide<D> dw;
277 const RepartitionToWide<RebindToUnsigned<D>> dw;
281 template <
class D, HWY_IF_T_SIZE_D(D, 8)>
282 HWY_INLINE Vec<D> OddEvenQuads(D d, Vec<D> odd, Vec<D> even)
const {
295struct OrderAscending :
public KeyLane<T, T> {
298 static constexpr bool IsKV() {
return false; }
300 using Order = SortAscending;
301 using OrderForSortingNetwork = OrderAscending<T>;
312 HWY_INLINE Vec<D> First(D ,
const Vec<D> a,
const Vec<D> b)
const {
317 HWY_INLINE Vec<D> Last(D ,
const Vec<D> a,
const Vec<D> b)
const {
350struct OrderDescending :
public KeyLane<T, T> {
353 static constexpr bool IsKV() {
return false; }
355 using Order = SortDescending;
356 using OrderForSortingNetwork = OrderDescending<T>;
366 HWY_INLINE Vec<D> First(D ,
const Vec<D> a,
const Vec<D> b)
const {
371 HWY_INLINE Vec<D> Last(D ,
const Vec<D> a,
const Vec<D> b)
const {
403struct KeyValue64 :
public KeyLane<uint64_t, hwy::K32V32> {
406 static constexpr bool IsKV() {
return true; }
409 HWY_INLINE Mask<D> EqualKeys(D , Vec<D> a, Vec<D> b)
const {
410 return Eq(ShiftRight<32>(a), ShiftRight<32>(b));
414 HWY_INLINE Mask<D> NotEqualKeys(D , Vec<D> a, Vec<D> b)
const {
415 return Ne(ShiftRight<32>(a), ShiftRight<32>(b));
418 HWY_INLINE bool Equal1(
const uint64_t* a,
const uint64_t* b)
const {
419 return (*a >> 32) == (*b >> 32);
424 HWY_INLINE bool NoKeyDifference(D , Vec<D> diff)
const {
426 const RebindToUnsigned<D> du;
427 const Vec<
decltype(du)> zero =
Zero(du);
428 const Vec<
decltype(du)> keys = ShiftRight<32>(diff);
433struct OrderAscendingKV64 :
public KeyValue64 {
434 using Order = SortAscending;
435 using OrderForSortingNetwork = OrderAscending<LaneType>;
437 HWY_INLINE bool Compare1(
const LaneType* a,
const LaneType* b)
const {
438 return (*a >> 32) < (*b >> 32);
442 HWY_INLINE Mask<D> Compare(D , Vec<D> a, Vec<D> b)
const {
443 return Lt(ShiftRight<32>(a), ShiftRight<32>(b));
449 HWY_INLINE Vec<D> First(D ,
const Vec<D> a,
const Vec<D> b)
const {
454 HWY_INLINE Vec<D> Last(D ,
const Vec<D> a,
const Vec<D> b)
const {
482 HWY_INLINE Vec<D> PrevValue(D d, Vec<D> v)
const {
483 return Sub(v,
Set(d, uint64_t{1} << 32));
487struct OrderDescendingKV64 :
public KeyValue64 {
488 using Order = SortDescending;
489 using OrderForSortingNetwork = OrderDescending<LaneType>;
491 HWY_INLINE bool Compare1(
const LaneType* a,
const LaneType* b)
const {
492 return (*b >> 32) < (*a >> 32);
496 HWY_INLINE Mask<D> Compare(D , Vec<D> a, Vec<D> b)
const {
497 return Lt(ShiftRight<32>(b), ShiftRight<32>(a));
503 HWY_INLINE Vec<D> First(D ,
const Vec<D> a,
const Vec<D> b)
const {
508 HWY_INLINE Vec<D> Last(D ,
const Vec<D> a,
const Vec<D> b)
const {
535 HWY_INLINE Vec<D> PrevValue(D d, Vec<D> v)
const {
536 return Add(v,
Set(d, uint64_t{1} << 32));
542struct TraitsLane :
public Base {
543 using TraitsForSortingNetwork =
544 TraitsLane<typename Base::OrderForSortingNetwork>;
551 HWY_INLINE void Sort2(D
d, Vec<D>& a, Vec<D>& b)
const {
552 const Base* base =
static_cast<const Base*
>(
this);
554 const Vec<D> a_copy = a;
557#if HWY_AVX3 < HWY_TARGET && HWY_TARGET <= HWY_SSSE3
558 if (
sizeof(TFromD<D>) == 8) {
559 const Mask<D> cmp = base->Compare(
d, a, b);
565 a = base->First(
d, a, b);
566 b = base->Last(
d, a_copy, b);
570 template <
class D, HWY_IF_T_SIZE_D(D, 8)>
571 HWY_INLINE Vec<D> SortPairsDistance1(D
d, Vec<D> v)
const {
572 const Base* base =
static_cast<const Base*
>(
this);
573 Vec<D> swapped = base->ReverseKeys2(
d, v);
576#if HWY_AVX3 < HWY_TARGET && HWY_TARGET <= HWY_SSSE3
577 const Vec<D> cmp =
VecFromMask(
d, base->Compare(
d, v, swapped));
580 Sort2(
d, v, swapped);
581 return base->OddEvenKeys(swapped, v);
586 template <
class D, HWY_IF_NOT_T_SIZE_D(D, 8)>
587 HWY_INLINE Vec<D> SortPairsDistance1(D
d, Vec<D> v)
const {
588 const Base* base =
static_cast<const Base*
>(
this);
589 Vec<D> swapped = base->ReverseKeys2(
d, v);
590 Sort2(
d, v, swapped);
591 return base->OddEvenKeys(swapped, v);
596 HWY_INLINE Vec<D> SortPairsReverse4(D
d, Vec<D> v)
const {
597 const Base* base =
static_cast<const Base*
>(
this);
598 Vec<D> swapped = base->ReverseKeys4(
d, v);
599 Sort2(
d, v, swapped);
600 return base->OddEvenPairs(
d, swapped, v);
605 HWY_INLINE Vec<D> SortPairsDistance4(D
d, Vec<D> v)
const {
606 const Base* base =
static_cast<const Base*
>(
this);
607 Vec<D> swapped = base->SwapAdjacentQuads(
d, v);
610 Sort2(
d, v, swapped);
611 return base->OddEvenQuads(
d, swapped, v);
651template <
class Order>
654 template <
typename T>
#define HWY_RESTRICT
Definition base.h:95
#define HWY_INLINE
Definition base.h:101
#define HWY_DASSERT(condition)
Definition base.h:290
HWY_API Vec128< T, N > Neg(hwy::NonFloatTag, Vec128< T, N > v)
Definition emu128-inl.h:744
HWY_INLINE Vec128< T, N > Max(hwy::NonFloatTag, Vec128< T, N > a, Vec128< T, N > b)
Definition emu128-inl.h:689
HWY_INLINE Vec128< T, N > Add(hwy::NonFloatTag, Vec128< T, N > a, Vec128< T, N > b)
Definition emu128-inl.h:560
Vec< D > SmallerSortValue(D d, Vec< D > v)
Definition traits-inl.h:115
HWY_INLINE Vec128< T, N > Min(hwy::NonFloatTag, Vec128< T, N > a, Vec128< T, N > b)
Definition emu128-inl.h:681
HWY_INLINE bool AllFalse(hwy::SizeTag< 1 >, const Mask256< T > mask)
Definition x86_256-inl.h:7076
HWY_INLINE Vec128< T, N > Sub(hwy::NonFloatTag, Vec128< T, N > a, Vec128< T, N > b)
Definition emu128-inl.h:570
Vec< D > LargestSortValue(D d)
Definition traits-inl.h:69
Vec< D > LargerSortValue(D d, Vec< D > v)
Definition traits-inl.h:88
HWY_INLINE Vec128< T, N > IfThenElse(hwy::SizeTag< 1 >, Mask128< T, N > mask, Vec128< T, N > yes, Vec128< T, N > no)
Definition x86_128-inl.h:1269
HWY_INLINE Vec128< T, N > CompressNot(Vec128< T, N > v, uint64_t mask_bits)
Definition arm_neon-inl.h:8860
Vec< D > SmallestSortValue(D d)
Definition traits-inl.h:78
HWY_API Vec128< T, N > OddEvenBlocks(Vec128< T, N >, Vec128< T, N > even)
Definition arm_neon-inl.h:7156
HWY_API VFromD< D > VecFromMask(D d, const MFromD< D > m)
Definition arm_neon-inl.h:2960
HWY_API Vec128< T, N > DupOdd(Vec128< T, N > v)
Definition arm_neon-inl.h:7091
HWY_API auto Lt(V a, V b) -> decltype(a==b)
Definition generic_ops-inl.h:7339
HWY_API auto Eq(V a, V b) -> decltype(a==b)
Definition generic_ops-inl.h:7331
HWY_API Mask128< T, N > IsNaN(const Vec128< T, N > v)
Definition arm_neon-inl.h:5093
D d
Definition arm_sve-inl.h:1915
HWY_API VFromD< D > BitCast(D d, Vec128< FromT, Repartition< FromT, D >().MaxLanes()> v)
Definition arm_neon-inl.h:1581
HWY_API VFromD< D > MaxOfLanes(D d, VFromD< D > v)
Definition arm_sve-inl.h:3228
HWY_API VFromD< D > ConcatLowerUpper(D d, VFromD< D > hi, VFromD< D > lo)
Definition arm_neon-inl.h:6965
HWY_API Vec128< uint64_t, N > Max(Vec128< uint64_t, N > a, Vec128< uint64_t, N > b)
Definition arm_neon-inl.h:3377
HWY_API Vec128< T > Shuffle1032(Vec128< T > v)
Definition arm_neon-inl.h:6008
HWY_API VFromD< D > Zero(D d)
Definition arm_neon-inl.h:947
HWY_API Vec128< T, 1 > Reverse(D, Vec128< T, 1 > v)
Definition arm_neon-inl.h:5959
HWY_API Vec128< uint64_t, N > Min(Vec128< uint64_t, N > a, Vec128< uint64_t, N > b)
Definition arm_neon-inl.h:3311
HWY_API Vec128< int64_t > Abs(const Vec128< int64_t > v)
Definition arm_neon-inl.h:3271
typename D::T TFromD
Definition ops/shared-inl.h:426
HWY_API Vec128< T, N > IfVecThenElse(Vec128< T, N > mask, Vec128< T, N > yes, Vec128< T, N > no)
Definition arm_neon-inl.h:2785
HWY_API VFromD< D > MinOfLanes(D d, VFromD< D > v)
Definition arm_sve-inl.h:3224
HWY_API Vec128< T, N > SwapAdjacentBlocks(Vec128< T, N > v)
Definition arm_neon-inl.h:7162
HWY_API VFromD< D > ConcatUpperLower(D d, VFromD< D > hi, VFromD< D > lo)
Definition arm_neon-inl.h:6989
HWY_API Vec64< uint32_t > Shuffle2301(const Vec64< uint32_t > v)
Definition arm_neon-inl.h:3084
HWY_API Vec< D > SignBit(D d)
Definition generic_ops-inl.h:75
Rebind< MakeUnsigned< TFromD< D > >, D > RebindToUnsigned
Definition ops/shared-inl.h:465
HWY_API Vec< D > Inf(D d)
Definition generic_ops-inl.h:91
HWY_API bool AllTrue(D d, Mask128< T > m)
Definition arm_neon-inl.h:8416
HWY_API svbool_t Gt(const V a, const V b)
Definition arm_sve-inl.h:1578
decltype(MaskFromVec(Zero(D()))) Mask
Definition generic_ops-inl.h:52
HWY_API MFromD< DTo > RebindMask(DTo, Mask128< TFrom, NFrom > m)
Definition arm_neon-inl.h:2969
HWY_INLINE Vec128< TFromD< D > > Set(D, T t)
Definition arm_neon-inl.h:931
HWY_API VFromD< D > Reverse8(D d, VFromD< D > v)
Definition arm_neon-inl.h:5935
HWY_API auto Le(V a, V b) -> decltype(a==b)
Definition generic_ops-inl.h:7353
HWY_API VFromD< D > Reverse4(D d, VFromD< D > v)
Definition arm_neon-inl.h:5900
HWY_API Vec128< T, N > OddEven(const Vec128< T, N > a, const Vec128< T, N > b)
Definition arm_neon-inl.h:7107
decltype(Zero(D())) Vec
Definition generic_ops-inl.h:46
HWY_API auto Ne(V a, V b) -> decltype(a==b)
Definition generic_ops-inl.h:7335
decltype(GetLane(V())) LaneType
Definition generic_ops-inl.h:39
HWY_API svbool_t IsFinite(const V v)
Definition arm_sve-inl.h:1725
HWY_API VFromD< D > Reverse2(D d, VFromD< D > v)
Definition arm_neon-inl.h:5860
HWY_API HWY_BITCASTSCALAR_CONSTEXPR T LowestValue()
Definition base.h:2191
HWY_API HWY_BITCASTSCALAR_CONSTEXPR T HighestValue()
Definition base.h:2212
#define HWY_NAMESPACE
Definition set_macros-inl.h:166
Definition traits-inl.h:39
KeyTypeArg KeyType
Definition traits-inl.h:46
static constexpr bool Is128()
Definition traits-inl.h:40
constexpr size_t LanesPerKey() const
Definition traits-inl.h:41
LaneTypeArg LaneType
Definition traits-inl.h:44
const char * KeyString() const
Definition traits-inl.h:48
Definition traits-inl.h:618
HWY_INLINE Vec< D > LastValue(D d) const
Definition traits-inl.h:629
HWY_INLINE bool Compare1(const T *a, const T *b) const
Definition traits-inl.h:621
HWY_INLINE Mask< D > Compare(D, Vec< D > a, Vec< D > b)
Definition traits-inl.h:624
Definition traits-inl.h:635
HWY_INLINE bool Compare1(const T *a, const T *b) const
Definition traits-inl.h:638
HWY_INLINE Mask< D > Compare(D, Vec< D > a, Vec< D > b)
Definition traits-inl.h:641
HWY_INLINE Vec< D > LastValue(D d) const
Definition traits-inl.h:646
Definition traits-inl.h:652
HWY_INLINE void Swap(T *a, T *b) const
Definition traits-inl.h:655
HWY_INLINE Vec< D > SetKey(D d, const TFromD< D > *key) const
Definition traits-inl.h:662