| // Copyright 2021 Google LLC |
| // SPDX-License-Identifier: Apache-2.0 |
| // |
| // Licensed under the Apache License, Version 2.0 (the "License"); |
| // you may not use this file except in compliance with the License. |
| // You may obtain a copy of the License at |
| // |
| // http://www.apache.org/licenses/LICENSE-2.0 |
| // |
| // Unless required by applicable law or agreed to in writing, software |
| // distributed under the License is distributed on an "AS IS" BASIS, |
| // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. |
| // See the License for the specific language governing permissions and |
| // limitations under the License. |
| |
| // Per-target |
| #if defined(HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE) == \ |
| defined(HWY_TARGET_TOGGLE) |
| #ifdef HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE |
| #undef HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE |
| #else |
| #define HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE |
| #endif |
| |
| #include "third_party/highway/hwy/contrib/sort/shared-inl.h" // SortConstants |
| #include "third_party/highway/hwy/highway.h" |
| |
| HWY_BEFORE_NAMESPACE(); |
| namespace hwy { |
| namespace HWY_NAMESPACE { |
| namespace detail { |
| |
| #if VQSORT_ENABLED |
| |
| using Constants = hwy::SortConstants; |
| |
| // ------------------------------ SharedTraits |
| |
| // Code shared between all traits. It's unclear whether these can profitably be |
| // specialized for Lane vs Block, or optimized like SortPairsDistance1 using |
| // Compare/DupOdd. |
| template <class Base> |
| struct SharedTraits : public Base { |
| using SharedTraitsForSortingNetwork = |
| SharedTraits<typename Base::TraitsForSortingNetwork>; |
| |
| // Conditionally swaps lane 0 with 2, 1 with 3 etc. |
| template <class D> |
| HWY_INLINE Vec<D> SortPairsDistance2(D d, Vec<D> v) const { |
| const Base* base = static_cast<const Base*>(this); |
| Vec<D> swapped = base->SwapAdjacentPairs(d, v); |
| base->Sort2(d, v, swapped); |
| return base->OddEvenPairs(d, swapped, v); |
| } |
| |
| // Swaps with the vector formed by reversing contiguous groups of 8 keys. |
| template <class D> |
| HWY_INLINE Vec<D> SortPairsReverse8(D d, Vec<D> v) const { |
| const Base* base = static_cast<const Base*>(this); |
| Vec<D> swapped = base->ReverseKeys8(d, v); |
| base->Sort2(d, v, swapped); |
| return base->OddEvenQuads(d, swapped, v); |
| } |
| |
| // Swaps with the vector formed by reversing contiguous groups of 8 keys. |
| template <class D> |
| HWY_INLINE Vec<D> SortPairsReverse16(D d, Vec<D> v) const { |
| const Base* base = static_cast<const Base*>(this); |
| static_assert(Constants::kMaxCols <= 16, "Need actual Reverse16"); |
| Vec<D> swapped = base->ReverseKeys(d, v); |
| base->Sort2(d, v, swapped); |
| return ConcatUpperLower(d, swapped, v); // 8 = half of the vector |
| } |
| }; |
| |
| // ------------------------------ Sorting network |
| |
| // Sorting networks for independent columns in 2, 4 and 8 vectors from |
| // https://bertdobbelaere.github.io/sorting_networks.html. |
| |
| template <class D, class Traits, class V = Vec<D>> |
| HWY_INLINE void Sort2(D d, Traits st, V& v0, V& v1) { |
| st.Sort2(d, v0, v1); |
| } |
| |
| template <class D, class Traits, class V = Vec<D>> |
| HWY_INLINE void Sort4(D d, Traits st, V& v0, V& v1, V& v2, V& v3) { |
| st.Sort2(d, v0, v2); |
| st.Sort2(d, v1, v3); |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v1, v2); |
| } |
| |
| template <class D, class Traits, class V = Vec<D>> |
| HWY_INLINE void Sort8(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, V& v5, |
| V& v6, V& v7) { |
| st.Sort2(d, v0, v2); |
| st.Sort2(d, v1, v3); |
| st.Sort2(d, v4, v6); |
| st.Sort2(d, v5, v7); |
| |
| st.Sort2(d, v0, v4); |
| st.Sort2(d, v1, v5); |
| st.Sort2(d, v2, v6); |
| st.Sort2(d, v3, v7); |
| |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v4, v5); |
| st.Sort2(d, v6, v7); |
| |
| st.Sort2(d, v2, v4); |
| st.Sort2(d, v3, v5); |
| |
| st.Sort2(d, v1, v4); |
| st.Sort2(d, v3, v6); |
| |
| st.Sort2(d, v1, v2); |
| st.Sort2(d, v3, v4); |
| st.Sort2(d, v5, v6); |
| } |
| |
| // (Green's irregular) sorting network for independent columns in 16 vectors. |
| template <class D, class Traits, class V = Vec<D>> |
| HWY_INLINE void Sort16(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, V& v5, |
| V& v6, V& v7, V& v8, V& v9, V& va, V& vb, V& vc, V& vd, |
| V& ve, V& vf) { |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v4, v5); |
| st.Sort2(d, v6, v7); |
| st.Sort2(d, v8, v9); |
| st.Sort2(d, va, vb); |
| st.Sort2(d, vc, vd); |
| st.Sort2(d, ve, vf); |
| st.Sort2(d, v0, v2); |
| st.Sort2(d, v1, v3); |
| st.Sort2(d, v4, v6); |
| st.Sort2(d, v5, v7); |
| st.Sort2(d, v8, va); |
| st.Sort2(d, v9, vb); |
| st.Sort2(d, vc, ve); |
| st.Sort2(d, vd, vf); |
| st.Sort2(d, v0, v4); |
| st.Sort2(d, v1, v5); |
| st.Sort2(d, v2, v6); |
| st.Sort2(d, v3, v7); |
| st.Sort2(d, v8, vc); |
| st.Sort2(d, v9, vd); |
| st.Sort2(d, va, ve); |
| st.Sort2(d, vb, vf); |
| st.Sort2(d, v0, v8); |
| st.Sort2(d, v1, v9); |
| st.Sort2(d, v2, va); |
| st.Sort2(d, v3, vb); |
| st.Sort2(d, v4, vc); |
| st.Sort2(d, v5, vd); |
| st.Sort2(d, v6, ve); |
| st.Sort2(d, v7, vf); |
| st.Sort2(d, v5, va); |
| st.Sort2(d, v6, v9); |
| st.Sort2(d, v3, vc); |
| st.Sort2(d, v7, vb); |
| st.Sort2(d, vd, ve); |
| st.Sort2(d, v4, v8); |
| st.Sort2(d, v1, v2); |
| st.Sort2(d, v1, v4); |
| st.Sort2(d, v7, vd); |
| st.Sort2(d, v2, v8); |
| st.Sort2(d, vb, ve); |
| st.Sort2(d, v2, v4); |
| st.Sort2(d, v5, v6); |
| st.Sort2(d, v9, va); |
| st.Sort2(d, vb, vd); |
| st.Sort2(d, v3, v8); |
| st.Sort2(d, v7, vc); |
| st.Sort2(d, v3, v5); |
| st.Sort2(d, v6, v8); |
| st.Sort2(d, v7, v9); |
| st.Sort2(d, va, vc); |
| st.Sort2(d, v3, v4); |
| st.Sort2(d, v5, v6); |
| st.Sort2(d, v7, v8); |
| st.Sort2(d, v9, va); |
| st.Sort2(d, vb, vc); |
| st.Sort2(d, v6, v7); |
| st.Sort2(d, v8, v9); |
| } |
| |
| // ------------------------------ Merging networks |
| |
| // Blacher's hybrid bitonic/odd-even networks, generated by print_network.cc. |
| // For acceptable performance, these must be inlined, otherwise vectors are |
| // loaded from the stack. The kKeysPerVector allows calling from generic code |
| // but skipping the functions when vectors have too few lanes for |
| // st.SortPairsDistance1 to compile. `if constexpr` in the caller would also |
| // work, but is not available in C++11. We write out the (unused) argument types |
| // rather than `...` because GCC 9 (but not 10) fails to compile with `...`. |
| |
| template <size_t kKeysPerVector, class D, class Traits, class V, |
| HWY_IF_LANES_LE(kKeysPerVector, 1)> |
| HWY_INLINE void Merge8x2(D, Traits, V, V, V, V, V, V, V, V) {} |
| template <size_t kKeysPerVector, class D, class Traits, class V, |
| HWY_IF_LANES_LE(kKeysPerVector, 2)> |
| HWY_INLINE void Merge8x4(D, Traits, V, V, V, V, V, V, V, V) {} |
| |
| template <size_t kKeysPerVector, class D, class Traits, class V, |
| HWY_IF_LANES_LE(kKeysPerVector, 1)> |
| HWY_INLINE void Merge16x2(D, Traits, V, V, V, V, V, V, V, V, V, V, V, V, V, V, |
| V, V) {} |
| template <size_t kKeysPerVector, class D, class Traits, class V, |
| HWY_IF_LANES_LE(kKeysPerVector, 2)> |
| HWY_INLINE void Merge16x4(D, Traits, V, V, V, V, V, V, V, V, V, V, V, V, V, V, |
| V, V) {} |
| template <size_t kKeysPerVector, class D, class Traits, class V, |
| HWY_IF_LANES_LE(kKeysPerVector, 4)> |
| HWY_INLINE void Merge16x8(D, Traits, V, V, V, V, V, V, V, V, V, V, V, V, V, V, |
| V, V) {} |
| template <size_t kKeysPerVector, class D, class Traits, class V, |
| HWY_IF_LANES_LE(kKeysPerVector, 8)> |
| HWY_INLINE void Merge16x16(D, Traits, V, V, V, V, V, V, V, V, V, V, V, V, V, V, |
| V, V) {} |
| |
| template <size_t kKeysPerVector, class D, class Traits, class V = Vec<D>, |
| HWY_IF_LANES_GT(kKeysPerVector, 1)> |
| HWY_INLINE void Merge8x2(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, |
| V& v5, V& v6, V& v7) { |
| v7 = st.ReverseKeys2(d, v7); |
| v6 = st.ReverseKeys2(d, v6); |
| v5 = st.ReverseKeys2(d, v5); |
| v4 = st.ReverseKeys2(d, v4); |
| st.Sort2(d, v0, v7); |
| st.Sort2(d, v1, v6); |
| st.Sort2(d, v2, v5); |
| st.Sort2(d, v3, v4); |
| |
| v3 = st.ReverseKeys2(d, v3); |
| v2 = st.ReverseKeys2(d, v2); |
| v7 = st.ReverseKeys2(d, v7); |
| v6 = st.ReverseKeys2(d, v6); |
| st.Sort2(d, v0, v3); |
| st.Sort2(d, v1, v2); |
| st.Sort2(d, v4, v7); |
| st.Sort2(d, v5, v6); |
| |
| v1 = st.ReverseKeys2(d, v1); |
| v3 = st.ReverseKeys2(d, v3); |
| v5 = st.ReverseKeys2(d, v5); |
| v7 = st.ReverseKeys2(d, v7); |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v4, v5); |
| st.Sort2(d, v6, v7); |
| |
| v0 = st.SortPairsDistance1(d, v0); |
| v1 = st.SortPairsDistance1(d, v1); |
| v2 = st.SortPairsDistance1(d, v2); |
| v3 = st.SortPairsDistance1(d, v3); |
| v4 = st.SortPairsDistance1(d, v4); |
| v5 = st.SortPairsDistance1(d, v5); |
| v6 = st.SortPairsDistance1(d, v6); |
| v7 = st.SortPairsDistance1(d, v7); |
| } |
| |
| template <size_t kKeysPerVector, class D, class Traits, class V = Vec<D>, |
| HWY_IF_LANES_GT(kKeysPerVector, 2)> |
| HWY_INLINE void Merge8x4(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, |
| V& v5, V& v6, V& v7) { |
| v7 = st.ReverseKeys4(d, v7); |
| v6 = st.ReverseKeys4(d, v6); |
| v5 = st.ReverseKeys4(d, v5); |
| v4 = st.ReverseKeys4(d, v4); |
| st.Sort2(d, v0, v7); |
| st.Sort2(d, v1, v6); |
| st.Sort2(d, v2, v5); |
| st.Sort2(d, v3, v4); |
| |
| v3 = st.ReverseKeys4(d, v3); |
| v2 = st.ReverseKeys4(d, v2); |
| v7 = st.ReverseKeys4(d, v7); |
| v6 = st.ReverseKeys4(d, v6); |
| st.Sort2(d, v0, v3); |
| st.Sort2(d, v1, v2); |
| st.Sort2(d, v4, v7); |
| st.Sort2(d, v5, v6); |
| |
| v1 = st.ReverseKeys4(d, v1); |
| v3 = st.ReverseKeys4(d, v3); |
| v5 = st.ReverseKeys4(d, v5); |
| v7 = st.ReverseKeys4(d, v7); |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v4, v5); |
| st.Sort2(d, v6, v7); |
| |
| v0 = st.SortPairsReverse4(d, v0); |
| v1 = st.SortPairsReverse4(d, v1); |
| v2 = st.SortPairsReverse4(d, v2); |
| v3 = st.SortPairsReverse4(d, v3); |
| v4 = st.SortPairsReverse4(d, v4); |
| v5 = st.SortPairsReverse4(d, v5); |
| v6 = st.SortPairsReverse4(d, v6); |
| v7 = st.SortPairsReverse4(d, v7); |
| |
| v0 = st.SortPairsDistance1(d, v0); |
| v1 = st.SortPairsDistance1(d, v1); |
| v2 = st.SortPairsDistance1(d, v2); |
| v3 = st.SortPairsDistance1(d, v3); |
| v4 = st.SortPairsDistance1(d, v4); |
| v5 = st.SortPairsDistance1(d, v5); |
| v6 = st.SortPairsDistance1(d, v6); |
| v7 = st.SortPairsDistance1(d, v7); |
| } |
| |
| // Only used by the now-deprecated SortingNetwork(). |
| template <size_t kKeysPerVector, class D, class Traits, class V = Vec<D>, |
| HWY_IF_LANES_GT(kKeysPerVector, 1)> |
| HWY_INLINE void Merge16x2(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, |
| V& v5, V& v6, V& v7, V& v8, V& v9, V& va, V& vb, |
| V& vc, V& vd, V& ve, V& vf) { |
| vf = st.ReverseKeys2(d, vf); |
| ve = st.ReverseKeys2(d, ve); |
| vd = st.ReverseKeys2(d, vd); |
| vc = st.ReverseKeys2(d, vc); |
| vb = st.ReverseKeys2(d, vb); |
| va = st.ReverseKeys2(d, va); |
| v9 = st.ReverseKeys2(d, v9); |
| v8 = st.ReverseKeys2(d, v8); |
| st.Sort2(d, v0, vf); |
| st.Sort2(d, v1, ve); |
| st.Sort2(d, v2, vd); |
| st.Sort2(d, v3, vc); |
| st.Sort2(d, v4, vb); |
| st.Sort2(d, v5, va); |
| st.Sort2(d, v6, v9); |
| st.Sort2(d, v7, v8); |
| |
| v7 = st.ReverseKeys2(d, v7); |
| v6 = st.ReverseKeys2(d, v6); |
| v5 = st.ReverseKeys2(d, v5); |
| v4 = st.ReverseKeys2(d, v4); |
| vf = st.ReverseKeys2(d, vf); |
| ve = st.ReverseKeys2(d, ve); |
| vd = st.ReverseKeys2(d, vd); |
| vc = st.ReverseKeys2(d, vc); |
| st.Sort2(d, v0, v7); |
| st.Sort2(d, v1, v6); |
| st.Sort2(d, v2, v5); |
| st.Sort2(d, v3, v4); |
| st.Sort2(d, v8, vf); |
| st.Sort2(d, v9, ve); |
| st.Sort2(d, va, vd); |
| st.Sort2(d, vb, vc); |
| |
| v3 = st.ReverseKeys2(d, v3); |
| v2 = st.ReverseKeys2(d, v2); |
| v7 = st.ReverseKeys2(d, v7); |
| v6 = st.ReverseKeys2(d, v6); |
| vb = st.ReverseKeys2(d, vb); |
| va = st.ReverseKeys2(d, va); |
| vf = st.ReverseKeys2(d, vf); |
| ve = st.ReverseKeys2(d, ve); |
| st.Sort2(d, v0, v3); |
| st.Sort2(d, v1, v2); |
| st.Sort2(d, v4, v7); |
| st.Sort2(d, v5, v6); |
| st.Sort2(d, v8, vb); |
| st.Sort2(d, v9, va); |
| st.Sort2(d, vc, vf); |
| st.Sort2(d, vd, ve); |
| |
| v1 = st.ReverseKeys2(d, v1); |
| v3 = st.ReverseKeys2(d, v3); |
| v5 = st.ReverseKeys2(d, v5); |
| v7 = st.ReverseKeys2(d, v7); |
| v9 = st.ReverseKeys2(d, v9); |
| vb = st.ReverseKeys2(d, vb); |
| vd = st.ReverseKeys2(d, vd); |
| vf = st.ReverseKeys2(d, vf); |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v4, v5); |
| st.Sort2(d, v6, v7); |
| st.Sort2(d, v8, v9); |
| st.Sort2(d, va, vb); |
| st.Sort2(d, vc, vd); |
| st.Sort2(d, ve, vf); |
| |
| v0 = st.SortPairsDistance1(d, v0); |
| v1 = st.SortPairsDistance1(d, v1); |
| v2 = st.SortPairsDistance1(d, v2); |
| v3 = st.SortPairsDistance1(d, v3); |
| v4 = st.SortPairsDistance1(d, v4); |
| v5 = st.SortPairsDistance1(d, v5); |
| v6 = st.SortPairsDistance1(d, v6); |
| v7 = st.SortPairsDistance1(d, v7); |
| v8 = st.SortPairsDistance1(d, v8); |
| v9 = st.SortPairsDistance1(d, v9); |
| va = st.SortPairsDistance1(d, va); |
| vb = st.SortPairsDistance1(d, vb); |
| vc = st.SortPairsDistance1(d, vc); |
| vd = st.SortPairsDistance1(d, vd); |
| ve = st.SortPairsDistance1(d, ve); |
| vf = st.SortPairsDistance1(d, vf); |
| } |
| |
| template <size_t kKeysPerVector, class D, class Traits, class V = Vec<D>, |
| HWY_IF_LANES_GT(kKeysPerVector, 2)> |
| HWY_INLINE void Merge16x4(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, |
| V& v5, V& v6, V& v7, V& v8, V& v9, V& va, V& vb, |
| V& vc, V& vd, V& ve, V& vf) { |
| vf = st.ReverseKeys4(d, vf); |
| ve = st.ReverseKeys4(d, ve); |
| vd = st.ReverseKeys4(d, vd); |
| vc = st.ReverseKeys4(d, vc); |
| vb = st.ReverseKeys4(d, vb); |
| va = st.ReverseKeys4(d, va); |
| v9 = st.ReverseKeys4(d, v9); |
| v8 = st.ReverseKeys4(d, v8); |
| st.Sort2(d, v0, vf); |
| st.Sort2(d, v1, ve); |
| st.Sort2(d, v2, vd); |
| st.Sort2(d, v3, vc); |
| st.Sort2(d, v4, vb); |
| st.Sort2(d, v5, va); |
| st.Sort2(d, v6, v9); |
| st.Sort2(d, v7, v8); |
| |
| v7 = st.ReverseKeys4(d, v7); |
| v6 = st.ReverseKeys4(d, v6); |
| v5 = st.ReverseKeys4(d, v5); |
| v4 = st.ReverseKeys4(d, v4); |
| vf = st.ReverseKeys4(d, vf); |
| ve = st.ReverseKeys4(d, ve); |
| vd = st.ReverseKeys4(d, vd); |
| vc = st.ReverseKeys4(d, vc); |
| st.Sort2(d, v0, v7); |
| st.Sort2(d, v1, v6); |
| st.Sort2(d, v2, v5); |
| st.Sort2(d, v3, v4); |
| st.Sort2(d, v8, vf); |
| st.Sort2(d, v9, ve); |
| st.Sort2(d, va, vd); |
| st.Sort2(d, vb, vc); |
| |
| v3 = st.ReverseKeys4(d, v3); |
| v2 = st.ReverseKeys4(d, v2); |
| v7 = st.ReverseKeys4(d, v7); |
| v6 = st.ReverseKeys4(d, v6); |
| vb = st.ReverseKeys4(d, vb); |
| va = st.ReverseKeys4(d, va); |
| vf = st.ReverseKeys4(d, vf); |
| ve = st.ReverseKeys4(d, ve); |
| st.Sort2(d, v0, v3); |
| st.Sort2(d, v1, v2); |
| st.Sort2(d, v4, v7); |
| st.Sort2(d, v5, v6); |
| st.Sort2(d, v8, vb); |
| st.Sort2(d, v9, va); |
| st.Sort2(d, vc, vf); |
| st.Sort2(d, vd, ve); |
| |
| v1 = st.ReverseKeys4(d, v1); |
| v3 = st.ReverseKeys4(d, v3); |
| v5 = st.ReverseKeys4(d, v5); |
| v7 = st.ReverseKeys4(d, v7); |
| v9 = st.ReverseKeys4(d, v9); |
| vb = st.ReverseKeys4(d, vb); |
| vd = st.ReverseKeys4(d, vd); |
| vf = st.ReverseKeys4(d, vf); |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v4, v5); |
| st.Sort2(d, v6, v7); |
| st.Sort2(d, v8, v9); |
| st.Sort2(d, va, vb); |
| st.Sort2(d, vc, vd); |
| st.Sort2(d, ve, vf); |
| |
| v0 = st.SortPairsReverse4(d, v0); |
| v1 = st.SortPairsReverse4(d, v1); |
| v2 = st.SortPairsReverse4(d, v2); |
| v3 = st.SortPairsReverse4(d, v3); |
| v4 = st.SortPairsReverse4(d, v4); |
| v5 = st.SortPairsReverse4(d, v5); |
| v6 = st.SortPairsReverse4(d, v6); |
| v7 = st.SortPairsReverse4(d, v7); |
| v8 = st.SortPairsReverse4(d, v8); |
| v9 = st.SortPairsReverse4(d, v9); |
| va = st.SortPairsReverse4(d, va); |
| vb = st.SortPairsReverse4(d, vb); |
| vc = st.SortPairsReverse4(d, vc); |
| vd = st.SortPairsReverse4(d, vd); |
| ve = st.SortPairsReverse4(d, ve); |
| vf = st.SortPairsReverse4(d, vf); |
| |
| v0 = st.SortPairsDistance1(d, v0); |
| v1 = st.SortPairsDistance1(d, v1); |
| v2 = st.SortPairsDistance1(d, v2); |
| v3 = st.SortPairsDistance1(d, v3); |
| v4 = st.SortPairsDistance1(d, v4); |
| v5 = st.SortPairsDistance1(d, v5); |
| v6 = st.SortPairsDistance1(d, v6); |
| v7 = st.SortPairsDistance1(d, v7); |
| v8 = st.SortPairsDistance1(d, v8); |
| v9 = st.SortPairsDistance1(d, v9); |
| va = st.SortPairsDistance1(d, va); |
| vb = st.SortPairsDistance1(d, vb); |
| vc = st.SortPairsDistance1(d, vc); |
| vd = st.SortPairsDistance1(d, vd); |
| ve = st.SortPairsDistance1(d, ve); |
| vf = st.SortPairsDistance1(d, vf); |
| } |
| |
| template <size_t kKeysPerVector, class D, class Traits, class V = Vec<D>, |
| HWY_IF_LANES_GT(kKeysPerVector, 4)> |
| HWY_INLINE void Merge16x8(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, |
| V& v5, V& v6, V& v7, V& v8, V& v9, V& va, V& vb, |
| V& vc, V& vd, V& ve, V& vf) { |
| vf = st.ReverseKeys8(d, vf); |
| ve = st.ReverseKeys8(d, ve); |
| vd = st.ReverseKeys8(d, vd); |
| vc = st.ReverseKeys8(d, vc); |
| vb = st.ReverseKeys8(d, vb); |
| va = st.ReverseKeys8(d, va); |
| v9 = st.ReverseKeys8(d, v9); |
| v8 = st.ReverseKeys8(d, v8); |
| st.Sort2(d, v0, vf); |
| st.Sort2(d, v1, ve); |
| st.Sort2(d, v2, vd); |
| st.Sort2(d, v3, vc); |
| st.Sort2(d, v4, vb); |
| st.Sort2(d, v5, va); |
| st.Sort2(d, v6, v9); |
| st.Sort2(d, v7, v8); |
| |
| v7 = st.ReverseKeys8(d, v7); |
| v6 = st.ReverseKeys8(d, v6); |
| v5 = st.ReverseKeys8(d, v5); |
| v4 = st.ReverseKeys8(d, v4); |
| vf = st.ReverseKeys8(d, vf); |
| ve = st.ReverseKeys8(d, ve); |
| vd = st.ReverseKeys8(d, vd); |
| vc = st.ReverseKeys8(d, vc); |
| st.Sort2(d, v0, v7); |
| st.Sort2(d, v1, v6); |
| st.Sort2(d, v2, v5); |
| st.Sort2(d, v3, v4); |
| st.Sort2(d, v8, vf); |
| st.Sort2(d, v9, ve); |
| st.Sort2(d, va, vd); |
| st.Sort2(d, vb, vc); |
| |
| v3 = st.ReverseKeys8(d, v3); |
| v2 = st.ReverseKeys8(d, v2); |
| v7 = st.ReverseKeys8(d, v7); |
| v6 = st.ReverseKeys8(d, v6); |
| vb = st.ReverseKeys8(d, vb); |
| va = st.ReverseKeys8(d, va); |
| vf = st.ReverseKeys8(d, vf); |
| ve = st.ReverseKeys8(d, ve); |
| st.Sort2(d, v0, v3); |
| st.Sort2(d, v1, v2); |
| st.Sort2(d, v4, v7); |
| st.Sort2(d, v5, v6); |
| st.Sort2(d, v8, vb); |
| st.Sort2(d, v9, va); |
| st.Sort2(d, vc, vf); |
| st.Sort2(d, vd, ve); |
| |
| v1 = st.ReverseKeys8(d, v1); |
| v3 = st.ReverseKeys8(d, v3); |
| v5 = st.ReverseKeys8(d, v5); |
| v7 = st.ReverseKeys8(d, v7); |
| v9 = st.ReverseKeys8(d, v9); |
| vb = st.ReverseKeys8(d, vb); |
| vd = st.ReverseKeys8(d, vd); |
| vf = st.ReverseKeys8(d, vf); |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v4, v5); |
| st.Sort2(d, v6, v7); |
| st.Sort2(d, v8, v9); |
| st.Sort2(d, va, vb); |
| st.Sort2(d, vc, vd); |
| st.Sort2(d, ve, vf); |
| |
| v0 = st.SortPairsReverse8(d, v0); |
| v1 = st.SortPairsReverse8(d, v1); |
| v2 = st.SortPairsReverse8(d, v2); |
| v3 = st.SortPairsReverse8(d, v3); |
| v4 = st.SortPairsReverse8(d, v4); |
| v5 = st.SortPairsReverse8(d, v5); |
| v6 = st.SortPairsReverse8(d, v6); |
| v7 = st.SortPairsReverse8(d, v7); |
| v8 = st.SortPairsReverse8(d, v8); |
| v9 = st.SortPairsReverse8(d, v9); |
| va = st.SortPairsReverse8(d, va); |
| vb = st.SortPairsReverse8(d, vb); |
| vc = st.SortPairsReverse8(d, vc); |
| vd = st.SortPairsReverse8(d, vd); |
| ve = st.SortPairsReverse8(d, ve); |
| vf = st.SortPairsReverse8(d, vf); |
| |
| v0 = st.SortPairsDistance2(d, v0); |
| v1 = st.SortPairsDistance2(d, v1); |
| v2 = st.SortPairsDistance2(d, v2); |
| v3 = st.SortPairsDistance2(d, v3); |
| v4 = st.SortPairsDistance2(d, v4); |
| v5 = st.SortPairsDistance2(d, v5); |
| v6 = st.SortPairsDistance2(d, v6); |
| v7 = st.SortPairsDistance2(d, v7); |
| v8 = st.SortPairsDistance2(d, v8); |
| v9 = st.SortPairsDistance2(d, v9); |
| va = st.SortPairsDistance2(d, va); |
| vb = st.SortPairsDistance2(d, vb); |
| vc = st.SortPairsDistance2(d, vc); |
| vd = st.SortPairsDistance2(d, vd); |
| ve = st.SortPairsDistance2(d, ve); |
| vf = st.SortPairsDistance2(d, vf); |
| |
| v0 = st.SortPairsDistance1(d, v0); |
| v1 = st.SortPairsDistance1(d, v1); |
| v2 = st.SortPairsDistance1(d, v2); |
| v3 = st.SortPairsDistance1(d, v3); |
| v4 = st.SortPairsDistance1(d, v4); |
| v5 = st.SortPairsDistance1(d, v5); |
| v6 = st.SortPairsDistance1(d, v6); |
| v7 = st.SortPairsDistance1(d, v7); |
| v8 = st.SortPairsDistance1(d, v8); |
| v9 = st.SortPairsDistance1(d, v9); |
| va = st.SortPairsDistance1(d, va); |
| vb = st.SortPairsDistance1(d, vb); |
| vc = st.SortPairsDistance1(d, vc); |
| vd = st.SortPairsDistance1(d, vd); |
| ve = st.SortPairsDistance1(d, ve); |
| vf = st.SortPairsDistance1(d, vf); |
| } |
| |
| // Unused on MSVC, see below |
| #if !HWY_COMPILER_MSVC && !HWY_IS_DEBUG_BUILD |
| |
| template <size_t kKeysPerVector, class D, class Traits, class V = Vec<D>, |
| HWY_IF_LANES_GT(kKeysPerVector, 8)> |
| HWY_INLINE void Merge16x16(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, |
| V& v5, V& v6, V& v7, V& v8, V& v9, V& va, V& vb, |
| V& vc, V& vd, V& ve, V& vf) { |
| vf = st.ReverseKeys16(d, vf); |
| ve = st.ReverseKeys16(d, ve); |
| vd = st.ReverseKeys16(d, vd); |
| vc = st.ReverseKeys16(d, vc); |
| vb = st.ReverseKeys16(d, vb); |
| va = st.ReverseKeys16(d, va); |
| v9 = st.ReverseKeys16(d, v9); |
| v8 = st.ReverseKeys16(d, v8); |
| st.Sort2(d, v0, vf); |
| st.Sort2(d, v1, ve); |
| st.Sort2(d, v2, vd); |
| st.Sort2(d, v3, vc); |
| st.Sort2(d, v4, vb); |
| st.Sort2(d, v5, va); |
| st.Sort2(d, v6, v9); |
| st.Sort2(d, v7, v8); |
| |
| v7 = st.ReverseKeys16(d, v7); |
| v6 = st.ReverseKeys16(d, v6); |
| v5 = st.ReverseKeys16(d, v5); |
| v4 = st.ReverseKeys16(d, v4); |
| vf = st.ReverseKeys16(d, vf); |
| ve = st.ReverseKeys16(d, ve); |
| vd = st.ReverseKeys16(d, vd); |
| vc = st.ReverseKeys16(d, vc); |
| st.Sort2(d, v0, v7); |
| st.Sort2(d, v1, v6); |
| st.Sort2(d, v2, v5); |
| st.Sort2(d, v3, v4); |
| st.Sort2(d, v8, vf); |
| st.Sort2(d, v9, ve); |
| st.Sort2(d, va, vd); |
| st.Sort2(d, vb, vc); |
| |
| v3 = st.ReverseKeys16(d, v3); |
| v2 = st.ReverseKeys16(d, v2); |
| v7 = st.ReverseKeys16(d, v7); |
| v6 = st.ReverseKeys16(d, v6); |
| vb = st.ReverseKeys16(d, vb); |
| va = st.ReverseKeys16(d, va); |
| vf = st.ReverseKeys16(d, vf); |
| ve = st.ReverseKeys16(d, ve); |
| st.Sort2(d, v0, v3); |
| st.Sort2(d, v1, v2); |
| st.Sort2(d, v4, v7); |
| st.Sort2(d, v5, v6); |
| st.Sort2(d, v8, vb); |
| st.Sort2(d, v9, va); |
| st.Sort2(d, vc, vf); |
| st.Sort2(d, vd, ve); |
| |
| v1 = st.ReverseKeys16(d, v1); |
| v3 = st.ReverseKeys16(d, v3); |
| v5 = st.ReverseKeys16(d, v5); |
| v7 = st.ReverseKeys16(d, v7); |
| v9 = st.ReverseKeys16(d, v9); |
| vb = st.ReverseKeys16(d, vb); |
| vd = st.ReverseKeys16(d, vd); |
| vf = st.ReverseKeys16(d, vf); |
| st.Sort2(d, v0, v1); |
| st.Sort2(d, v2, v3); |
| st.Sort2(d, v4, v5); |
| st.Sort2(d, v6, v7); |
| st.Sort2(d, v8, v9); |
| st.Sort2(d, va, vb); |
| st.Sort2(d, vc, vd); |
| st.Sort2(d, ve, vf); |
| |
| v0 = st.SortPairsReverse16(d, v0); |
| v1 = st.SortPairsReverse16(d, v1); |
| v2 = st.SortPairsReverse16(d, v2); |
| v3 = st.SortPairsReverse16(d, v3); |
| v4 = st.SortPairsReverse16(d, v4); |
| v5 = st.SortPairsReverse16(d, v5); |
| v6 = st.SortPairsReverse16(d, v6); |
| v7 = st.SortPairsReverse16(d, v7); |
| v8 = st.SortPairsReverse16(d, v8); |
| v9 = st.SortPairsReverse16(d, v9); |
| va = st.SortPairsReverse16(d, va); |
| vb = st.SortPairsReverse16(d, vb); |
| vc = st.SortPairsReverse16(d, vc); |
| vd = st.SortPairsReverse16(d, vd); |
| ve = st.SortPairsReverse16(d, ve); |
| vf = st.SortPairsReverse16(d, vf); |
| |
| v0 = st.SortPairsDistance4(d, v0); |
| v1 = st.SortPairsDistance4(d, v1); |
| v2 = st.SortPairsDistance4(d, v2); |
| v3 = st.SortPairsDistance4(d, v3); |
| v4 = st.SortPairsDistance4(d, v4); |
| v5 = st.SortPairsDistance4(d, v5); |
| v6 = st.SortPairsDistance4(d, v6); |
| v7 = st.SortPairsDistance4(d, v7); |
| v8 = st.SortPairsDistance4(d, v8); |
| v9 = st.SortPairsDistance4(d, v9); |
| va = st.SortPairsDistance4(d, va); |
| vb = st.SortPairsDistance4(d, vb); |
| vc = st.SortPairsDistance4(d, vc); |
| vd = st.SortPairsDistance4(d, vd); |
| ve = st.SortPairsDistance4(d, ve); |
| vf = st.SortPairsDistance4(d, vf); |
| |
| v0 = st.SortPairsDistance2(d, v0); |
| v1 = st.SortPairsDistance2(d, v1); |
| v2 = st.SortPairsDistance2(d, v2); |
| v3 = st.SortPairsDistance2(d, v3); |
| v4 = st.SortPairsDistance2(d, v4); |
| v5 = st.SortPairsDistance2(d, v5); |
| v6 = st.SortPairsDistance2(d, v6); |
| v7 = st.SortPairsDistance2(d, v7); |
| v8 = st.SortPairsDistance2(d, v8); |
| v9 = st.SortPairsDistance2(d, v9); |
| va = st.SortPairsDistance2(d, va); |
| vb = st.SortPairsDistance2(d, vb); |
| vc = st.SortPairsDistance2(d, vc); |
| vd = st.SortPairsDistance2(d, vd); |
| ve = st.SortPairsDistance2(d, ve); |
| vf = st.SortPairsDistance2(d, vf); |
| |
| v0 = st.SortPairsDistance1(d, v0); |
| v1 = st.SortPairsDistance1(d, v1); |
| v2 = st.SortPairsDistance1(d, v2); |
| v3 = st.SortPairsDistance1(d, v3); |
| v4 = st.SortPairsDistance1(d, v4); |
| v5 = st.SortPairsDistance1(d, v5); |
| v6 = st.SortPairsDistance1(d, v6); |
| v7 = st.SortPairsDistance1(d, v7); |
| v8 = st.SortPairsDistance1(d, v8); |
| v9 = st.SortPairsDistance1(d, v9); |
| va = st.SortPairsDistance1(d, va); |
| vb = st.SortPairsDistance1(d, vb); |
| vc = st.SortPairsDistance1(d, vc); |
| vd = st.SortPairsDistance1(d, vd); |
| ve = st.SortPairsDistance1(d, ve); |
| vf = st.SortPairsDistance1(d, vf); |
| } |
| |
| #endif // !HWY_COMPILER_MSVC && !HWY_IS_DEBUG_BUILD |
| |
| // Reshapes `buf` into a matrix, sorts columns independently, and then merges |
| // into a sorted 1D array without transposing. |
| // |
| // DEPRECATED, use BaseCase() instead. |
| template <class Traits, class V> |
| HWY_INLINE void SortingNetwork(Traits st, size_t cols, V& v0, V& v1, V& v2, |
| V& v3, V& v4, V& v5, V& v6, V& v7, V& v8, V& v9, |
| V& va, V& vb, V& vc, V& vd, V& ve, V& vf) { |
| // traits*-inl assume 'full' vectors (but still capped to kMaxCols). |
| const CappedTag<typename Traits::LaneType, Constants::kMaxCols> d; |
| |
| HWY_DASSERT(cols <= Constants::kMaxCols); |
| |
| // The network width depends on the number of keys, not lanes. |
| constexpr size_t kLanesPerKey = st.LanesPerKey(); |
| const size_t keys = cols / kLanesPerKey; |
| constexpr size_t kMaxKeys = MaxLanes(d) / kLanesPerKey; |
| |
| Sort16(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, vc, vd, ve, vf); |
| |
| // Checking MaxLanes avoids generating HWY_ASSERT code for the unreachable |
| // code paths: if MaxLanes < 2, then keys <= cols < 2. |
| if (HWY_LIKELY(keys >= 2 && kMaxKeys >= 2)) { |
| Merge16x2<kMaxKeys>(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, |
| vc, vd, ve, vf); |
| |
| if (HWY_LIKELY(keys >= 4 && kMaxKeys >= 4)) { |
| Merge16x4<kMaxKeys>(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, |
| vc, vd, ve, vf); |
| |
| if (HWY_LIKELY(keys >= 8 && kMaxKeys >= 8)) { |
| Merge16x8<kMaxKeys>(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, |
| vb, vc, vd, ve, vf); |
| |
| // Avoids build timeout. Must match #if condition in kMaxCols. |
| #if !HWY_COMPILER_MSVC && !HWY_IS_DEBUG_BUILD |
| if (HWY_LIKELY(keys >= 16 && kMaxKeys >= 16)) { |
| Merge16x16<kMaxKeys>(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, |
| va, vb, vc, vd, ve, vf); |
| |
| static_assert(Constants::kMaxCols <= 16, "Add more branches"); |
| } |
| #endif |
| } |
| } |
| } |
| } |
| |
| // As above, but loads from/stores to `buf`. This ensures full vectors are |
| // aligned, and enables loads/stores without bounds checks. |
| // |
| // DEPRECATED, use BaseCase() instead. |
| template <class Traits, typename T> |
| HWY_NOINLINE void SortingNetwork(Traits st, T* HWY_RESTRICT buf, size_t cols) { |
| // traits*-inl assume 'full' vectors (but still capped to kMaxCols). |
| // However, for smaller arrays and sub-maximal `cols` we have overlapping |
| // loads where only the lowest `cols` are valid, and we skip Merge16 etc. |
| const CappedTag<T, Constants::kMaxCols> d; |
| using V = decltype(Zero(d)); |
| |
| HWY_DASSERT(cols <= Constants::kMaxCols); |
| |
| // These are aligned iff cols == Lanes(d). We prefer unaligned/non-constexpr |
| // offsets to duplicating this code for every value of cols. |
| static_assert(Constants::kMaxRows == 16, "Update loads/stores/args"); |
| V v0 = LoadU(d, buf + 0x0 * cols); |
| V v1 = LoadU(d, buf + 0x1 * cols); |
| V v2 = LoadU(d, buf + 0x2 * cols); |
| V v3 = LoadU(d, buf + 0x3 * cols); |
| V v4 = LoadU(d, buf + 0x4 * cols); |
| V v5 = LoadU(d, buf + 0x5 * cols); |
| V v6 = LoadU(d, buf + 0x6 * cols); |
| V v7 = LoadU(d, buf + 0x7 * cols); |
| V v8 = LoadU(d, buf + 0x8 * cols); |
| V v9 = LoadU(d, buf + 0x9 * cols); |
| V va = LoadU(d, buf + 0xa * cols); |
| V vb = LoadU(d, buf + 0xb * cols); |
| V vc = LoadU(d, buf + 0xc * cols); |
| V vd = LoadU(d, buf + 0xd * cols); |
| V ve = LoadU(d, buf + 0xe * cols); |
| V vf = LoadU(d, buf + 0xf * cols); |
| |
| SortingNetwork(st, cols, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, vc, |
| vd, ve, vf); |
| |
| StoreU(v0, d, buf + 0x0 * cols); |
| StoreU(v1, d, buf + 0x1 * cols); |
| StoreU(v2, d, buf + 0x2 * cols); |
| StoreU(v3, d, buf + 0x3 * cols); |
| StoreU(v4, d, buf + 0x4 * cols); |
| StoreU(v5, d, buf + 0x5 * cols); |
| StoreU(v6, d, buf + 0x6 * cols); |
| StoreU(v7, d, buf + 0x7 * cols); |
| StoreU(v8, d, buf + 0x8 * cols); |
| StoreU(v9, d, buf + 0x9 * cols); |
| StoreU(va, d, buf + 0xa * cols); |
| StoreU(vb, d, buf + 0xb * cols); |
| StoreU(vc, d, buf + 0xc * cols); |
| StoreU(vd, d, buf + 0xd * cols); |
| StoreU(ve, d, buf + 0xe * cols); |
| StoreU(vf, d, buf + 0xf * cols); |
| } |
| |
| #else |
| template <class Base> |
| struct SharedTraits : public Base {}; |
| #endif // VQSORT_ENABLED |
| |
| } // namespace detail |
| // NOLINTNEXTLINE(google-readability-namespace-comments) |
| } // namespace HWY_NAMESPACE |
| } // namespace hwy |
| HWY_AFTER_NAMESPACE(); |
| |
| #endif // HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE |
