Grok  9.7.5
sorting_networks-inl.h
Go to the documentation of this file.
1 // Copyright 2021 Google LLC
2 // SPDX-License-Identifier: Apache-2.0
3 //
4 // Licensed under the Apache License, Version 2.0 (the "License");
5 // you may not use this file except in compliance with the License.
6 // You may obtain a copy of the License at
7 //
8 // http://www.apache.org/licenses/LICENSE-2.0
9 //
10 // Unless required by applicable law or agreed to in writing, software
11 // distributed under the License is distributed on an "AS IS" BASIS,
12 // WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 // See the License for the specific language governing permissions and
14 // limitations under the License.
15 
16 // Per-target
17 #if defined(HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE) == \
18  defined(HWY_TARGET_TOGGLE)
19 #ifdef HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE
20 #undef HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE
21 #else
22 #define HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE
23 #endif
24 
26 #include "hwy/contrib/sort/shared-inl.h" // SortConstants
27 #include "hwy/highway.h"
28 
30 namespace hwy {
31 namespace HWY_NAMESPACE {
32 namespace detail {
33 
35 
36 // ------------------------------ SharedTraits
37 
38 // Code shared between all traits. It's unclear whether these can profitably be
39 // specialized for Lane vs Block, or optimized like SortPairsDistance1 using
40 // Compare/DupOdd.
41 template <class Base>
42 struct SharedTraits : public Base {
43  // Conditionally swaps lane 0 with 2, 1 with 3 etc.
44  template <class D>
46  const Base* base = static_cast<const Base*>(this);
47  Vec<D> swapped = base->SwapAdjacentPairs(d, v);
48  base->Sort2(d, v, swapped);
49  return base->OddEvenPairs(d, swapped, v);
50  }
51 
52  // Swaps with the vector formed by reversing contiguous groups of 8 keys.
53  template <class D>
55  const Base* base = static_cast<const Base*>(this);
56  Vec<D> swapped = base->ReverseKeys8(d, v);
57  base->Sort2(d, v, swapped);
58  return base->OddEvenQuads(d, swapped, v);
59  }
60 
61  // Swaps with the vector formed by reversing contiguous groups of 8 keys.
62  template <class D>
64  const Base* base = static_cast<const Base*>(this);
65  static_assert(Constants::kMaxCols <= 16, "Need actual Reverse16");
66  Vec<D> swapped = base->ReverseKeys(d, v);
67  base->Sort2(d, v, swapped);
68  return ConcatUpperLower(d, swapped, v); // 8 = half of the vector
69  }
70 };
71 
72 // ------------------------------ Sorting network
73 
74 // (Green's irregular) sorting network for independent columns in 16 vectors.
75 template <class D, class Traits, class V = Vec<D>>
76 HWY_INLINE void Sort16(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, V& v5,
77  V& v6, V& v7, V& v8, V& v9, V& va, V& vb, V& vc, V& vd,
78  V& ve, V& vf) {
79  st.Sort2(d, v0, v1);
80  st.Sort2(d, v2, v3);
81  st.Sort2(d, v4, v5);
82  st.Sort2(d, v6, v7);
83  st.Sort2(d, v8, v9);
84  st.Sort2(d, va, vb);
85  st.Sort2(d, vc, vd);
86  st.Sort2(d, ve, vf);
87  st.Sort2(d, v0, v2);
88  st.Sort2(d, v1, v3);
89  st.Sort2(d, v4, v6);
90  st.Sort2(d, v5, v7);
91  st.Sort2(d, v8, va);
92  st.Sort2(d, v9, vb);
93  st.Sort2(d, vc, ve);
94  st.Sort2(d, vd, vf);
95  st.Sort2(d, v0, v4);
96  st.Sort2(d, v1, v5);
97  st.Sort2(d, v2, v6);
98  st.Sort2(d, v3, v7);
99  st.Sort2(d, v8, vc);
100  st.Sort2(d, v9, vd);
101  st.Sort2(d, va, ve);
102  st.Sort2(d, vb, vf);
103  st.Sort2(d, v0, v8);
104  st.Sort2(d, v1, v9);
105  st.Sort2(d, v2, va);
106  st.Sort2(d, v3, vb);
107  st.Sort2(d, v4, vc);
108  st.Sort2(d, v5, vd);
109  st.Sort2(d, v6, ve);
110  st.Sort2(d, v7, vf);
111  st.Sort2(d, v5, va);
112  st.Sort2(d, v6, v9);
113  st.Sort2(d, v3, vc);
114  st.Sort2(d, v7, vb);
115  st.Sort2(d, vd, ve);
116  st.Sort2(d, v4, v8);
117  st.Sort2(d, v1, v2);
118  st.Sort2(d, v1, v4);
119  st.Sort2(d, v7, vd);
120  st.Sort2(d, v2, v8);
121  st.Sort2(d, vb, ve);
122  st.Sort2(d, v2, v4);
123  st.Sort2(d, v5, v6);
124  st.Sort2(d, v9, va);
125  st.Sort2(d, vb, vd);
126  st.Sort2(d, v3, v8);
127  st.Sort2(d, v7, vc);
128  st.Sort2(d, v3, v5);
129  st.Sort2(d, v6, v8);
130  st.Sort2(d, v7, v9);
131  st.Sort2(d, va, vc);
132  st.Sort2(d, v3, v4);
133  st.Sort2(d, v5, v6);
134  st.Sort2(d, v7, v8);
135  st.Sort2(d, v9, va);
136  st.Sort2(d, vb, vc);
137  st.Sort2(d, v6, v7);
138  st.Sort2(d, v8, v9);
139 }
140 
141 // ------------------------------ Merging networks
142 
143 // Blacher's hybrid bitonic/odd-even networks, generated by print_network.cc.
144 
145 template <class D, class Traits, class V = Vec<D>>
146 HWY_INLINE void Merge2(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, V& v5,
147  V& v6, V& v7, V& v8, V& v9, V& va, V& vb, V& vc, V& vd,
148  V& ve, V& vf) {
149  v8 = st.ReverseKeys2(d, v8);
150  v9 = st.ReverseKeys2(d, v9);
151  va = st.ReverseKeys2(d, va);
152  vb = st.ReverseKeys2(d, vb);
153  vc = st.ReverseKeys2(d, vc);
154  vd = st.ReverseKeys2(d, vd);
155  ve = st.ReverseKeys2(d, ve);
156  vf = st.ReverseKeys2(d, vf);
157  st.Sort2(d, v0, vf);
158  st.Sort2(d, v1, ve);
159  st.Sort2(d, v2, vd);
160  st.Sort2(d, v3, vc);
161  st.Sort2(d, v4, vb);
162  st.Sort2(d, v5, va);
163  st.Sort2(d, v6, v9);
164  st.Sort2(d, v7, v8);
165  v4 = st.ReverseKeys2(d, v4);
166  vc = st.ReverseKeys2(d, vc);
167  v5 = st.ReverseKeys2(d, v5);
168  vd = st.ReverseKeys2(d, vd);
169  v6 = st.ReverseKeys2(d, v6);
170  ve = st.ReverseKeys2(d, ve);
171  v7 = st.ReverseKeys2(d, v7);
172  vf = st.ReverseKeys2(d, vf);
173  st.Sort2(d, v0, v7);
174  st.Sort2(d, v8, vf);
175  st.Sort2(d, v1, v6);
176  st.Sort2(d, v9, ve);
177  st.Sort2(d, v2, v5);
178  st.Sort2(d, va, vd);
179  st.Sort2(d, v3, v4);
180  st.Sort2(d, vb, vc);
181  v2 = st.ReverseKeys2(d, v2);
182  v3 = st.ReverseKeys2(d, v3);
183  v6 = st.ReverseKeys2(d, v6);
184  v7 = st.ReverseKeys2(d, v7);
185  va = st.ReverseKeys2(d, va);
186  vb = st.ReverseKeys2(d, vb);
187  ve = st.ReverseKeys2(d, ve);
188  vf = st.ReverseKeys2(d, vf);
189  st.Sort2(d, v0, v3);
190  st.Sort2(d, v1, v2);
191  st.Sort2(d, v4, v7);
192  st.Sort2(d, v5, v6);
193  st.Sort2(d, v8, vb);
194  st.Sort2(d, v9, va);
195  st.Sort2(d, vc, vf);
196  st.Sort2(d, vd, ve);
197  v1 = st.ReverseKeys2(d, v1);
198  v3 = st.ReverseKeys2(d, v3);
199  v5 = st.ReverseKeys2(d, v5);
200  v7 = st.ReverseKeys2(d, v7);
201  v9 = st.ReverseKeys2(d, v9);
202  vb = st.ReverseKeys2(d, vb);
203  vd = st.ReverseKeys2(d, vd);
204  vf = st.ReverseKeys2(d, vf);
205  st.Sort2(d, v0, v1);
206  st.Sort2(d, v2, v3);
207  st.Sort2(d, v4, v5);
208  st.Sort2(d, v6, v7);
209  st.Sort2(d, v8, v9);
210  st.Sort2(d, va, vb);
211  st.Sort2(d, vc, vd);
212  st.Sort2(d, ve, vf);
213  v0 = st.SortPairsDistance1(d, v0);
214  v1 = st.SortPairsDistance1(d, v1);
215  v2 = st.SortPairsDistance1(d, v2);
216  v3 = st.SortPairsDistance1(d, v3);
217  v4 = st.SortPairsDistance1(d, v4);
218  v5 = st.SortPairsDistance1(d, v5);
219  v6 = st.SortPairsDistance1(d, v6);
220  v7 = st.SortPairsDistance1(d, v7);
221  v8 = st.SortPairsDistance1(d, v8);
222  v9 = st.SortPairsDistance1(d, v9);
223  va = st.SortPairsDistance1(d, va);
224  vb = st.SortPairsDistance1(d, vb);
225  vc = st.SortPairsDistance1(d, vc);
226  vd = st.SortPairsDistance1(d, vd);
227  ve = st.SortPairsDistance1(d, ve);
228  vf = st.SortPairsDistance1(d, vf);
229 }
230 
231 template <class D, class Traits, class V = Vec<D>>
232 HWY_INLINE void Merge4(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, V& v5,
233  V& v6, V& v7, V& v8, V& v9, V& va, V& vb, V& vc, V& vd,
234  V& ve, V& vf) {
235  v8 = st.ReverseKeys4(d, v8);
236  v9 = st.ReverseKeys4(d, v9);
237  va = st.ReverseKeys4(d, va);
238  vb = st.ReverseKeys4(d, vb);
239  vc = st.ReverseKeys4(d, vc);
240  vd = st.ReverseKeys4(d, vd);
241  ve = st.ReverseKeys4(d, ve);
242  vf = st.ReverseKeys4(d, vf);
243  st.Sort2(d, v0, vf);
244  st.Sort2(d, v1, ve);
245  st.Sort2(d, v2, vd);
246  st.Sort2(d, v3, vc);
247  st.Sort2(d, v4, vb);
248  st.Sort2(d, v5, va);
249  st.Sort2(d, v6, v9);
250  st.Sort2(d, v7, v8);
251  v4 = st.ReverseKeys4(d, v4);
252  vc = st.ReverseKeys4(d, vc);
253  v5 = st.ReverseKeys4(d, v5);
254  vd = st.ReverseKeys4(d, vd);
255  v6 = st.ReverseKeys4(d, v6);
256  ve = st.ReverseKeys4(d, ve);
257  v7 = st.ReverseKeys4(d, v7);
258  vf = st.ReverseKeys4(d, vf);
259  st.Sort2(d, v0, v7);
260  st.Sort2(d, v8, vf);
261  st.Sort2(d, v1, v6);
262  st.Sort2(d, v9, ve);
263  st.Sort2(d, v2, v5);
264  st.Sort2(d, va, vd);
265  st.Sort2(d, v3, v4);
266  st.Sort2(d, vb, vc);
267  v2 = st.ReverseKeys4(d, v2);
268  v3 = st.ReverseKeys4(d, v3);
269  v6 = st.ReverseKeys4(d, v6);
270  v7 = st.ReverseKeys4(d, v7);
271  va = st.ReverseKeys4(d, va);
272  vb = st.ReverseKeys4(d, vb);
273  ve = st.ReverseKeys4(d, ve);
274  vf = st.ReverseKeys4(d, vf);
275  st.Sort2(d, v0, v3);
276  st.Sort2(d, v1, v2);
277  st.Sort2(d, v4, v7);
278  st.Sort2(d, v5, v6);
279  st.Sort2(d, v8, vb);
280  st.Sort2(d, v9, va);
281  st.Sort2(d, vc, vf);
282  st.Sort2(d, vd, ve);
283  v1 = st.ReverseKeys4(d, v1);
284  v3 = st.ReverseKeys4(d, v3);
285  v5 = st.ReverseKeys4(d, v5);
286  v7 = st.ReverseKeys4(d, v7);
287  v9 = st.ReverseKeys4(d, v9);
288  vb = st.ReverseKeys4(d, vb);
289  vd = st.ReverseKeys4(d, vd);
290  vf = st.ReverseKeys4(d, vf);
291  st.Sort2(d, v0, v1);
292  st.Sort2(d, v2, v3);
293  st.Sort2(d, v4, v5);
294  st.Sort2(d, v6, v7);
295  st.Sort2(d, v8, v9);
296  st.Sort2(d, va, vb);
297  st.Sort2(d, vc, vd);
298  st.Sort2(d, ve, vf);
299  v0 = st.SortPairsReverse4(d, v0);
300  v1 = st.SortPairsReverse4(d, v1);
301  v2 = st.SortPairsReverse4(d, v2);
302  v3 = st.SortPairsReverse4(d, v3);
303  v4 = st.SortPairsReverse4(d, v4);
304  v5 = st.SortPairsReverse4(d, v5);
305  v6 = st.SortPairsReverse4(d, v6);
306  v7 = st.SortPairsReverse4(d, v7);
307  v8 = st.SortPairsReverse4(d, v8);
308  v9 = st.SortPairsReverse4(d, v9);
309  va = st.SortPairsReverse4(d, va);
310  vb = st.SortPairsReverse4(d, vb);
311  vc = st.SortPairsReverse4(d, vc);
312  vd = st.SortPairsReverse4(d, vd);
313  ve = st.SortPairsReverse4(d, ve);
314  vf = st.SortPairsReverse4(d, vf);
315  v0 = st.SortPairsDistance1(d, v0);
316  v1 = st.SortPairsDistance1(d, v1);
317  v2 = st.SortPairsDistance1(d, v2);
318  v3 = st.SortPairsDistance1(d, v3);
319  v4 = st.SortPairsDistance1(d, v4);
320  v5 = st.SortPairsDistance1(d, v5);
321  v6 = st.SortPairsDistance1(d, v6);
322  v7 = st.SortPairsDistance1(d, v7);
323  v8 = st.SortPairsDistance1(d, v8);
324  v9 = st.SortPairsDistance1(d, v9);
325  va = st.SortPairsDistance1(d, va);
326  vb = st.SortPairsDistance1(d, vb);
327  vc = st.SortPairsDistance1(d, vc);
328  vd = st.SortPairsDistance1(d, vd);
329  ve = st.SortPairsDistance1(d, ve);
330  vf = st.SortPairsDistance1(d, vf);
331 }
332 
333 template <class D, class Traits, class V = Vec<D>>
334 HWY_INLINE void Merge8(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4, V& v5,
335  V& v6, V& v7, V& v8, V& v9, V& va, V& vb, V& vc, V& vd,
336  V& ve, V& vf) {
337  v8 = st.ReverseKeys8(d, v8);
338  v9 = st.ReverseKeys8(d, v9);
339  va = st.ReverseKeys8(d, va);
340  vb = st.ReverseKeys8(d, vb);
341  vc = st.ReverseKeys8(d, vc);
342  vd = st.ReverseKeys8(d, vd);
343  ve = st.ReverseKeys8(d, ve);
344  vf = st.ReverseKeys8(d, vf);
345  st.Sort2(d, v0, vf);
346  st.Sort2(d, v1, ve);
347  st.Sort2(d, v2, vd);
348  st.Sort2(d, v3, vc);
349  st.Sort2(d, v4, vb);
350  st.Sort2(d, v5, va);
351  st.Sort2(d, v6, v9);
352  st.Sort2(d, v7, v8);
353  v4 = st.ReverseKeys8(d, v4);
354  vc = st.ReverseKeys8(d, vc);
355  v5 = st.ReverseKeys8(d, v5);
356  vd = st.ReverseKeys8(d, vd);
357  v6 = st.ReverseKeys8(d, v6);
358  ve = st.ReverseKeys8(d, ve);
359  v7 = st.ReverseKeys8(d, v7);
360  vf = st.ReverseKeys8(d, vf);
361  st.Sort2(d, v0, v7);
362  st.Sort2(d, v8, vf);
363  st.Sort2(d, v1, v6);
364  st.Sort2(d, v9, ve);
365  st.Sort2(d, v2, v5);
366  st.Sort2(d, va, vd);
367  st.Sort2(d, v3, v4);
368  st.Sort2(d, vb, vc);
369  v2 = st.ReverseKeys8(d, v2);
370  v3 = st.ReverseKeys8(d, v3);
371  v6 = st.ReverseKeys8(d, v6);
372  v7 = st.ReverseKeys8(d, v7);
373  va = st.ReverseKeys8(d, va);
374  vb = st.ReverseKeys8(d, vb);
375  ve = st.ReverseKeys8(d, ve);
376  vf = st.ReverseKeys8(d, vf);
377  st.Sort2(d, v0, v3);
378  st.Sort2(d, v1, v2);
379  st.Sort2(d, v4, v7);
380  st.Sort2(d, v5, v6);
381  st.Sort2(d, v8, vb);
382  st.Sort2(d, v9, va);
383  st.Sort2(d, vc, vf);
384  st.Sort2(d, vd, ve);
385  v1 = st.ReverseKeys8(d, v1);
386  v3 = st.ReverseKeys8(d, v3);
387  v5 = st.ReverseKeys8(d, v5);
388  v7 = st.ReverseKeys8(d, v7);
389  v9 = st.ReverseKeys8(d, v9);
390  vb = st.ReverseKeys8(d, vb);
391  vd = st.ReverseKeys8(d, vd);
392  vf = st.ReverseKeys8(d, vf);
393  st.Sort2(d, v0, v1);
394  st.Sort2(d, v2, v3);
395  st.Sort2(d, v4, v5);
396  st.Sort2(d, v6, v7);
397  st.Sort2(d, v8, v9);
398  st.Sort2(d, va, vb);
399  st.Sort2(d, vc, vd);
400  st.Sort2(d, ve, vf);
401  v0 = st.SortPairsReverse8(d, v0);
402  v1 = st.SortPairsReverse8(d, v1);
403  v2 = st.SortPairsReverse8(d, v2);
404  v3 = st.SortPairsReverse8(d, v3);
405  v4 = st.SortPairsReverse8(d, v4);
406  v5 = st.SortPairsReverse8(d, v5);
407  v6 = st.SortPairsReverse8(d, v6);
408  v7 = st.SortPairsReverse8(d, v7);
409  v8 = st.SortPairsReverse8(d, v8);
410  v9 = st.SortPairsReverse8(d, v9);
411  va = st.SortPairsReverse8(d, va);
412  vb = st.SortPairsReverse8(d, vb);
413  vc = st.SortPairsReverse8(d, vc);
414  vd = st.SortPairsReverse8(d, vd);
415  ve = st.SortPairsReverse8(d, ve);
416  vf = st.SortPairsReverse8(d, vf);
417  v0 = st.SortPairsDistance2(d, v0);
418  v1 = st.SortPairsDistance2(d, v1);
419  v2 = st.SortPairsDistance2(d, v2);
420  v3 = st.SortPairsDistance2(d, v3);
421  v4 = st.SortPairsDistance2(d, v4);
422  v5 = st.SortPairsDistance2(d, v5);
423  v6 = st.SortPairsDistance2(d, v6);
424  v7 = st.SortPairsDistance2(d, v7);
425  v8 = st.SortPairsDistance2(d, v8);
426  v9 = st.SortPairsDistance2(d, v9);
427  va = st.SortPairsDistance2(d, va);
428  vb = st.SortPairsDistance2(d, vb);
429  vc = st.SortPairsDistance2(d, vc);
430  vd = st.SortPairsDistance2(d, vd);
431  ve = st.SortPairsDistance2(d, ve);
432  vf = st.SortPairsDistance2(d, vf);
433  v0 = st.SortPairsDistance1(d, v0);
434  v1 = st.SortPairsDistance1(d, v1);
435  v2 = st.SortPairsDistance1(d, v2);
436  v3 = st.SortPairsDistance1(d, v3);
437  v4 = st.SortPairsDistance1(d, v4);
438  v5 = st.SortPairsDistance1(d, v5);
439  v6 = st.SortPairsDistance1(d, v6);
440  v7 = st.SortPairsDistance1(d, v7);
441  v8 = st.SortPairsDistance1(d, v8);
442  v9 = st.SortPairsDistance1(d, v9);
443  va = st.SortPairsDistance1(d, va);
444  vb = st.SortPairsDistance1(d, vb);
445  vc = st.SortPairsDistance1(d, vc);
446  vd = st.SortPairsDistance1(d, vd);
447  ve = st.SortPairsDistance1(d, ve);
448  vf = st.SortPairsDistance1(d, vf);
449 }
450 
451 // Unused on MSVC, see below
452 #if !HWY_COMPILER_MSVC
453 
454 template <class D, class Traits, class V = Vec<D>>
455 HWY_INLINE void Merge16(D d, Traits st, V& v0, V& v1, V& v2, V& v3, V& v4,
456  V& v5, V& v6, V& v7, V& v8, V& v9, V& va, V& vb, V& vc,
457  V& vd, V& ve, V& vf) {
458  v8 = st.ReverseKeys16(d, v8);
459  v9 = st.ReverseKeys16(d, v9);
460  va = st.ReverseKeys16(d, va);
461  vb = st.ReverseKeys16(d, vb);
462  vc = st.ReverseKeys16(d, vc);
463  vd = st.ReverseKeys16(d, vd);
464  ve = st.ReverseKeys16(d, ve);
465  vf = st.ReverseKeys16(d, vf);
466  st.Sort2(d, v0, vf);
467  st.Sort2(d, v1, ve);
468  st.Sort2(d, v2, vd);
469  st.Sort2(d, v3, vc);
470  st.Sort2(d, v4, vb);
471  st.Sort2(d, v5, va);
472  st.Sort2(d, v6, v9);
473  st.Sort2(d, v7, v8);
474  v4 = st.ReverseKeys16(d, v4);
475  vc = st.ReverseKeys16(d, vc);
476  v5 = st.ReverseKeys16(d, v5);
477  vd = st.ReverseKeys16(d, vd);
478  v6 = st.ReverseKeys16(d, v6);
479  ve = st.ReverseKeys16(d, ve);
480  v7 = st.ReverseKeys16(d, v7);
481  vf = st.ReverseKeys16(d, vf);
482  st.Sort2(d, v0, v7);
483  st.Sort2(d, v8, vf);
484  st.Sort2(d, v1, v6);
485  st.Sort2(d, v9, ve);
486  st.Sort2(d, v2, v5);
487  st.Sort2(d, va, vd);
488  st.Sort2(d, v3, v4);
489  st.Sort2(d, vb, vc);
490  v2 = st.ReverseKeys16(d, v2);
491  v3 = st.ReverseKeys16(d, v3);
492  v6 = st.ReverseKeys16(d, v6);
493  v7 = st.ReverseKeys16(d, v7);
494  va = st.ReverseKeys16(d, va);
495  vb = st.ReverseKeys16(d, vb);
496  ve = st.ReverseKeys16(d, ve);
497  vf = st.ReverseKeys16(d, vf);
498  st.Sort2(d, v0, v3);
499  st.Sort2(d, v1, v2);
500  st.Sort2(d, v4, v7);
501  st.Sort2(d, v5, v6);
502  st.Sort2(d, v8, vb);
503  st.Sort2(d, v9, va);
504  st.Sort2(d, vc, vf);
505  st.Sort2(d, vd, ve);
506  v1 = st.ReverseKeys16(d, v1);
507  v3 = st.ReverseKeys16(d, v3);
508  v5 = st.ReverseKeys16(d, v5);
509  v7 = st.ReverseKeys16(d, v7);
510  v9 = st.ReverseKeys16(d, v9);
511  vb = st.ReverseKeys16(d, vb);
512  vd = st.ReverseKeys16(d, vd);
513  vf = st.ReverseKeys16(d, vf);
514  st.Sort2(d, v0, v1);
515  st.Sort2(d, v2, v3);
516  st.Sort2(d, v4, v5);
517  st.Sort2(d, v6, v7);
518  st.Sort2(d, v8, v9);
519  st.Sort2(d, va, vb);
520  st.Sort2(d, vc, vd);
521  st.Sort2(d, ve, vf);
522  v0 = st.SortPairsReverse16(d, v0);
523  v1 = st.SortPairsReverse16(d, v1);
524  v2 = st.SortPairsReverse16(d, v2);
525  v3 = st.SortPairsReverse16(d, v3);
526  v4 = st.SortPairsReverse16(d, v4);
527  v5 = st.SortPairsReverse16(d, v5);
528  v6 = st.SortPairsReverse16(d, v6);
529  v7 = st.SortPairsReverse16(d, v7);
530  v8 = st.SortPairsReverse16(d, v8);
531  v9 = st.SortPairsReverse16(d, v9);
532  va = st.SortPairsReverse16(d, va);
533  vb = st.SortPairsReverse16(d, vb);
534  vc = st.SortPairsReverse16(d, vc);
535  vd = st.SortPairsReverse16(d, vd);
536  ve = st.SortPairsReverse16(d, ve);
537  vf = st.SortPairsReverse16(d, vf);
538  v0 = st.SortPairsDistance4(d, v0);
539  v1 = st.SortPairsDistance4(d, v1);
540  v2 = st.SortPairsDistance4(d, v2);
541  v3 = st.SortPairsDistance4(d, v3);
542  v4 = st.SortPairsDistance4(d, v4);
543  v5 = st.SortPairsDistance4(d, v5);
544  v6 = st.SortPairsDistance4(d, v6);
545  v7 = st.SortPairsDistance4(d, v7);
546  v8 = st.SortPairsDistance4(d, v8);
547  v9 = st.SortPairsDistance4(d, v9);
548  va = st.SortPairsDistance4(d, va);
549  vb = st.SortPairsDistance4(d, vb);
550  vc = st.SortPairsDistance4(d, vc);
551  vd = st.SortPairsDistance4(d, vd);
552  ve = st.SortPairsDistance4(d, ve);
553  vf = st.SortPairsDistance4(d, vf);
554  v0 = st.SortPairsDistance2(d, v0);
555  v1 = st.SortPairsDistance2(d, v1);
556  v2 = st.SortPairsDistance2(d, v2);
557  v3 = st.SortPairsDistance2(d, v3);
558  v4 = st.SortPairsDistance2(d, v4);
559  v5 = st.SortPairsDistance2(d, v5);
560  v6 = st.SortPairsDistance2(d, v6);
561  v7 = st.SortPairsDistance2(d, v7);
562  v8 = st.SortPairsDistance2(d, v8);
563  v9 = st.SortPairsDistance2(d, v9);
564  va = st.SortPairsDistance2(d, va);
565  vb = st.SortPairsDistance2(d, vb);
566  vc = st.SortPairsDistance2(d, vc);
567  vd = st.SortPairsDistance2(d, vd);
568  ve = st.SortPairsDistance2(d, ve);
569  vf = st.SortPairsDistance2(d, vf);
570  v0 = st.SortPairsDistance1(d, v0);
571  v1 = st.SortPairsDistance1(d, v1);
572  v2 = st.SortPairsDistance1(d, v2);
573  v3 = st.SortPairsDistance1(d, v3);
574  v4 = st.SortPairsDistance1(d, v4);
575  v5 = st.SortPairsDistance1(d, v5);
576  v6 = st.SortPairsDistance1(d, v6);
577  v7 = st.SortPairsDistance1(d, v7);
578  v8 = st.SortPairsDistance1(d, v8);
579  v9 = st.SortPairsDistance1(d, v9);
580  va = st.SortPairsDistance1(d, va);
581  vb = st.SortPairsDistance1(d, vb);
582  vc = st.SortPairsDistance1(d, vc);
583  vd = st.SortPairsDistance1(d, vd);
584  ve = st.SortPairsDistance1(d, ve);
585  vf = st.SortPairsDistance1(d, vf);
586 }
587 
588 #endif // !HWY_COMPILER_MSVC
589 
590 // Reshapes `buf` into a matrix, sorts columns independently, and then merges
591 // into a sorted 1D array without transposing.
592 //
593 // `st` is SharedTraits<Traits*<Order*>>. This abstraction layer bridges
594 // differences in sort order and single-lane vs 128-bit keys.
595 // `buf` ensures full vectors are aligned, and enables loads/stores without
596 // bounds checks.
597 //
598 // References:
599 // https://drops.dagstuhl.de/opus/volltexte/2021/13775/pdf/LIPIcs-SEA-2021-3.pdf
600 // https://github.com/simd-sorting/fast-and-robust/blob/master/avx2_sort_demo/avx2sort.h
601 // "Entwurf und Implementierung vektorisierter Sortieralgorithmen" (M. Blacher)
602 template <class Traits, typename T>
603 HWY_INLINE void SortingNetwork(Traits st, T* HWY_RESTRICT buf, size_t cols) {
605  using V = decltype(Zero(d));
606 
608 
609  // The network width depends on the number of keys, not lanes.
610  constexpr size_t kLanesPerKey = st.LanesPerKey();
611  const size_t keys = cols / kLanesPerKey;
612  constexpr size_t kMaxKeys = MaxLanes(d) / kLanesPerKey;
613 
614  // These are aligned iff cols == Lanes(d). We prefer unaligned/non-constexpr
615  // offsets to duplicating this code for every value of cols.
616  static_assert(Constants::kMaxRows == 16, "Update loads/stores/args");
617  V v0 = LoadU(d, buf + 0x0 * cols);
618  V v1 = LoadU(d, buf + 0x1 * cols);
619  V v2 = LoadU(d, buf + 0x2 * cols);
620  V v3 = LoadU(d, buf + 0x3 * cols);
621  V v4 = LoadU(d, buf + 0x4 * cols);
622  V v5 = LoadU(d, buf + 0x5 * cols);
623  V v6 = LoadU(d, buf + 0x6 * cols);
624  V v7 = LoadU(d, buf + 0x7 * cols);
625  V v8 = LoadU(d, buf + 0x8 * cols);
626  V v9 = LoadU(d, buf + 0x9 * cols);
627  V va = LoadU(d, buf + 0xa * cols);
628  V vb = LoadU(d, buf + 0xb * cols);
629  V vc = LoadU(d, buf + 0xc * cols);
630  V vd = LoadU(d, buf + 0xd * cols);
631  V ve = LoadU(d, buf + 0xe * cols);
632  V vf = LoadU(d, buf + 0xf * cols);
633 
634  Sort16(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, vc, vd, ve, vf);
635 
636  // Checking MaxLanes avoids generating HWY_ASSERT code for the unreachable
637  // code paths: if MaxLanes < 2, then keys <= cols < 2.
638  if (HWY_LIKELY(keys >= 2 && kMaxKeys >= 2)) {
639  Merge2(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, vc, vd, ve,
640  vf);
641 
642  if (HWY_LIKELY(keys >= 4 && kMaxKeys >= 4)) {
643  Merge4(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, vc, vd, ve,
644  vf);
645 
646  if (HWY_LIKELY(keys >= 8 && kMaxKeys >= 8)) {
647  Merge8(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, vc, vd,
648  ve, vf);
649 
650  // Avoids build timeout
651 #if !HWY_COMPILER_MSVC
652  if (HWY_LIKELY(keys >= 16 && kMaxKeys >= 16)) {
653  Merge16(d, st, v0, v1, v2, v3, v4, v5, v6, v7, v8, v9, va, vb, vc, vd,
654  ve, vf);
655 
656  static_assert(Constants::kMaxCols <= 16, "Add more branches");
657  }
658 #endif
659  }
660  }
661  }
662 
663  StoreU(v0, d, buf + 0x0 * cols);
664  StoreU(v1, d, buf + 0x1 * cols);
665  StoreU(v2, d, buf + 0x2 * cols);
666  StoreU(v3, d, buf + 0x3 * cols);
667  StoreU(v4, d, buf + 0x4 * cols);
668  StoreU(v5, d, buf + 0x5 * cols);
669  StoreU(v6, d, buf + 0x6 * cols);
670  StoreU(v7, d, buf + 0x7 * cols);
671  StoreU(v8, d, buf + 0x8 * cols);
672  StoreU(v9, d, buf + 0x9 * cols);
673  StoreU(va, d, buf + 0xa * cols);
674  StoreU(vb, d, buf + 0xb * cols);
675  StoreU(vc, d, buf + 0xc * cols);
676  StoreU(vd, d, buf + 0xd * cols);
677  StoreU(ve, d, buf + 0xe * cols);
678  StoreU(vf, d, buf + 0xf * cols);
679 }
680 
681 } // namespace detail
682 // NOLINTNEXTLINE(google-readability-namespace-comments)
683 } // namespace HWY_NAMESPACE
684 } // namespace hwy
686 
687 #endif // HIGHWAY_HWY_CONTRIB_SORT_SORTING_NETWORKS_TOGGLE
#define HWY_RESTRICT
Definition: base.h:63
#define HWY_INLINE
Definition: base.h:64
#define HWY_DASSERT(condition)
Definition: base.h:193
#define HWY_LIKELY(expr)
Definition: base.h:68
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)
Definition: sorting_networks-inl.h:76
HWY_INLINE void Merge16(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)
Definition: sorting_networks-inl.h:455
HWY_INLINE void Merge4(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)
Definition: sorting_networks-inl.h:232
HWY_INLINE void SortingNetwork(Traits st, T *HWY_RESTRICT buf, size_t cols)
Definition: sorting_networks-inl.h:603
HWY_INLINE void Merge8(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)
Definition: sorting_networks-inl.h:334
HWY_INLINE void Merge2(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)
Definition: sorting_networks-inl.h:146
d
Definition: rvv-inl.h:1656
typename detail::CappedTagChecker< T, kLimit >::type CappedTag
Definition: ops/shared-inl.h:173
HWY_API Vec128< T, N > Zero(Simd< T, N, 0 > d)
Definition: arm_neon-inl.h:733
HWY_API void StoreU(const Vec128< uint8_t > v, Full128< uint8_t >, uint8_t *HWY_RESTRICT unaligned)
Definition: arm_neon-inl.h:2224
HWY_API Vec128< uint8_t > LoadU(Full128< uint8_t >, const uint8_t *HWY_RESTRICT unaligned)
Definition: arm_neon-inl.h:2031
HWY_API Vec128< T, N > ConcatUpperLower(Simd< T, N, 0 > d, Vec128< T, N > hi, Vec128< T, N > lo)
Definition: arm_neon-inl.h:3895
HWY_INLINE constexpr HWY_MAYBE_UNUSED size_t MaxLanes(D)
Definition: ops/shared-inl.h:271
const vfloat64m1_t v
Definition: rvv-inl.h:1656
decltype(Zero(D())) Vec
Definition: generic_ops-inl.h:32
Definition: aligned_allocator.h:27
#define HWY_NAMESPACE
Definition: set_macros-inl.h:80
HWY_AFTER_NAMESPACE()
HWY_BEFORE_NAMESPACE()
Definition: sorting_networks-inl.h:42
HWY_INLINE Vec< D > SortPairsDistance2(D d, Vec< D > v) const
Definition: sorting_networks-inl.h:45
HWY_INLINE Vec< D > SortPairsReverse8(D d, Vec< D > v) const
Definition: sorting_networks-inl.h:54
HWY_INLINE Vec< D > SortPairsReverse16(D d, Vec< D > v) const
Definition: sorting_networks-inl.h:63
Definition: contrib/sort/shared-inl.h:28
static constexpr size_t kMaxCols
Definition: contrib/sort/shared-inl.h:34
static constexpr size_t kMaxRows
Definition: contrib/sort/shared-inl.h:43