strided_basic/erased/arg_reduce.rs
1//! Dtype-erased `argmax` / `argmin` along one axis.
2
3use super::line::{for_each_unit, LineLayout, UnitKernel, UnitPtr, PANEL};
4use super::{
5 check_reduce_layout_offset_arithmetic, checked_total_len, reduce_uninit_writer, reduce_writer,
6 ReduceWriter,
7};
8use crate::erased_common::{check_dtype, validate_uninit_no_overlap};
9use crate::*;
10use num_complex::{Complex32, Complex64};
11
12/// Runtime operation of an [`ErasedArgReducePlan`].
13///
14/// # Examples
15///
16/// ```
17/// use strided_basic::ArgReduceOp;
18/// assert_ne!(ArgReduceOp::Max, ArgReduceOp::MaxAbs);
19/// ```
20#[non_exhaustive]
21#[derive(Clone, Copy, Debug, Eq, PartialEq)]
22pub enum ArgReduceOp {
23 /// Index of the largest value. Real dtypes only.
24 Max,
25 /// Index of the smallest value. Real dtypes only.
26 Min,
27 /// Index of the largest magnitude (`|x|`, the modulus for complex input).
28 MaxAbs,
29 /// Index of the smallest magnitude (`|x|`, the modulus for complex input).
30 MinAbs,
31}
32
33impl ArgReduceOp {
34 #[inline]
35 fn label(self) -> &'static str {
36 match self {
37 Self::Max => "argmax",
38 Self::Min => "argmin",
39 Self::MaxAbs => "argmax_abs",
40 Self::MinAbs => "argmin_abs",
41 }
42 }
43}
44
45/// Dtype-erased `argmax` / `argmin` along one axis.
46///
47/// The destination holds one index per line: its dimensions are the source
48/// dimensions with `axis` removed (batch axes are preserved in order), and its
49/// dtype is the index dtype, `i32` or `i64`. Indices count from the start of
50/// the logical axis, whatever the sign of its stride.
51///
52/// Supported source dtypes are `f32`, `f64`, `i32` and `i64` for every
53/// [`ArgReduceOp`], and `c32` / `c64` for the magnitude variants
54/// ([`ArgReduceOp::MaxAbs`], [`ArgReduceOp::MinAbs`]) only.
55///
56/// # Ties, NaN and magnitudes
57///
58/// * Ties resolve to the **lowest index**. `-0.0` and `+0.0` compare equal,
59/// so they tie.
60/// * NaN propagates like [`ReduceOp::Max`]: if a line contains a NaN, the
61/// result is the index of its **first** NaN, for both the max and the min
62/// variants. A complex element is NaN when either component is NaN. This
63/// matches NumPy, PyTorch and JAX.
64/// * Infinities order normally; `+inf` beats every finite value for `Max`.
65/// * The complex magnitude is the overflow-safe modulus (`hypot` of the
66/// components), so values near the top of the exponent range still order
67/// correctly. A component of `±inf` makes the magnitude `+inf` unless the
68/// other component is NaN.
69/// * The integer magnitude is the unsigned absolute value, so `i32::MIN` is
70/// larger than `i32::MAX`.
71///
72/// The result does not depend on the layout, execution context or thread
73/// count.
74///
75/// # Examples
76///
77/// ```
78/// use strided_basic::{
79/// Exec, ArgReduceOp, ErasedArgReducePlan, ErasedRawStridedMut, ErasedRawStridedRef,
80/// KernelDType,
81/// };
82///
83/// // Column-major 3 x 2 matrix; argmax down each column.
84/// let src = [1.0_f64, 5.0, 5.0, -2.0, -7.0, 3.0];
85/// let mut out = [0_i64; 2];
86/// let plan = ErasedArgReducePlan::compile(
87/// KernelDType::F64,
88/// KernelDType::I64,
89/// ArgReduceOp::Max,
90/// &[3, 2],
91/// &[1, 3],
92/// &[2],
93/// &[1],
94/// 0,
95/// )
96/// .unwrap();
97/// let src_ref = ErasedRawStridedRef::from_slice(&src, &[3, 2], &[1, 3], 0).unwrap();
98/// let mut dest = ErasedRawStridedMut::from_slice_mut(&mut out, &[2], &[1], 0).unwrap();
99/// plan.execute(&mut dest, &src_ref, Exec::serial()).unwrap();
100/// assert_eq!(out, [1, 2]); // lowest index wins the 5.0 tie
101/// ```
102#[derive(Clone, Debug)]
103pub struct ErasedArgReducePlan {
104 dtype: KernelDType,
105 index_dtype: KernelDType,
106 op: ArgReduceOp,
107 src_dims: crate::inline::InlineVec<usize>,
108 src_strides: crate::inline::InlineVec<isize>,
109 dest_dims: crate::inline::InlineVec<usize>,
110 dest_strides: crate::inline::InlineVec<isize>,
111 layout: LineLayout,
112}
113
114impl ErasedArgReducePlan {
115 /// Validate and store an arg-reduction plan for fixed layouts.
116 ///
117 /// `dest_dims` must equal `src_dims` with `axis` removed.
118 ///
119 /// # Examples
120 ///
121 /// ```
122 /// use strided_basic::{ArgReduceOp, ErasedArgReducePlan, KernelDType};
123 /// let plan = ErasedArgReducePlan::compile(
124 /// KernelDType::C64, KernelDType::I32, ArgReduceOp::MaxAbs, &[4, 3], &[3, 1], &[3], &[1], 0,
125 /// )
126 /// .unwrap();
127 /// assert_eq!(plan.index_dtype(), KernelDType::I32);
128 /// // Complex input has no order without the magnitude.
129 /// assert!(ErasedArgReducePlan::compile(
130 /// KernelDType::C64, KernelDType::I64, ArgReduceOp::Max, &[4], &[1], &[], &[], 0,
131 /// )
132 /// .is_err());
133 /// // An empty axis has no index to return.
134 /// assert!(ErasedArgReducePlan::compile(
135 /// KernelDType::F64, KernelDType::I64, ArgReduceOp::Max, &[0, 2], &[1, 1], &[2], &[1], 0,
136 /// )
137 /// .is_err());
138 /// ```
139 ///
140 /// # Errors
141 ///
142 /// * `UnsupportedDType` for a `bool` source or an index dtype other than
143 /// `i32` / `i64`;
144 /// * `UnsupportedOp` for `Max` / `Min` on complex input, and for a
145 /// zero-length `axis`, which has no index to return;
146 /// * `InvalidAxis`, `StrideLengthMismatch`, `ShapeMismatch` and
147 /// `NonInjectiveOutputLayout` for inconsistent layouts;
148 /// * `OffsetOverflow` when a layout's offsets are not representable, or
149 /// when the axis is too long for an `i32` index.
150 // Dtype pair, op, both layouts and the axis are the compile key; wrapping adds nothing.
151 #[allow(clippy::too_many_arguments)]
152 pub fn compile(
153 dtype: KernelDType,
154 index_dtype: KernelDType,
155 op: ArgReduceOp,
156 src_dims: &[usize],
157 src_strides: &[isize],
158 dest_dims: &[usize],
159 dest_strides: &[isize],
160 axis: usize,
161 ) -> Result<Self> {
162 check_arg_dtype(dtype, op)?;
163 if !matches!(index_dtype, KernelDType::I32 | KernelDType::I64) {
164 return Err(StridedError::UnsupportedDType {
165 dtype: index_dtype.label(),
166 });
167 }
168 if src_dims.len() != src_strides.len() || dest_dims.len() != dest_strides.len() {
169 return Err(StridedError::StrideLengthMismatch);
170 }
171 let rank = src_dims.len();
172 if axis >= rank {
173 return Err(StridedError::InvalidAxis { axis, rank });
174 }
175 let expected: crate::inline::InlineVec<usize> = (0..rank)
176 .filter(|&a| a != axis)
177 .map(|a| src_dims[a])
178 .collect();
179 if dest_dims != expected.as_slice() {
180 return Err(StridedError::ShapeMismatch(
181 dest_dims.to_vec(),
182 expected.to_vec(),
183 ));
184 }
185 if src_dims[axis] == 0 {
186 return Err(StridedError::UnsupportedOp {
187 op: "argmax/argmin over a zero-length axis",
188 dtype: dtype.label(),
189 });
190 }
191 if index_dtype == KernelDType::I32 && i32::try_from(src_dims[axis] - 1).is_err() {
192 return Err(StridedError::OffsetOverflow);
193 }
194 checked_total_len(src_dims)?;
195 check_reduce_layout_offset_arithmetic(src_dims, src_strides)?;
196 check_reduce_layout_offset_arithmetic(dest_dims, dest_strides)?;
197 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
198 return Err(StridedError::NonInjectiveOutputLayout);
199 }
200 let layout = LineLayout::compile(src_dims, src_strides, dest_strides, 0, axis, false)?;
201 Ok(Self {
202 dtype,
203 index_dtype,
204 op,
205 src_dims: src_dims.into(),
206 src_strides: src_strides.into(),
207 dest_dims: dest_dims.into(),
208 dest_strides: dest_strides.into(),
209 layout,
210 })
211 }
212
213 /// Source element dtype.
214 ///
215 /// # Examples
216 ///
217 /// ```
218 /// use strided_basic::{ArgReduceOp, ErasedArgReducePlan, KernelDType};
219 /// let plan = ErasedArgReducePlan::compile(
220 /// KernelDType::F32, KernelDType::I64, ArgReduceOp::Min, &[2], &[1], &[], &[], 0,
221 /// )
222 /// .unwrap();
223 /// assert_eq!(plan.dtype(), KernelDType::F32);
224 /// ```
225 #[inline]
226 pub fn dtype(&self) -> KernelDType {
227 self.dtype
228 }
229
230 /// Destination index dtype (`i32` or `i64`).
231 ///
232 /// # Examples
233 ///
234 /// ```
235 /// use strided_basic::{ArgReduceOp, ErasedArgReducePlan, KernelDType};
236 /// let plan = ErasedArgReducePlan::compile(
237 /// KernelDType::F32, KernelDType::I64, ArgReduceOp::Min, &[2], &[1], &[], &[], 0,
238 /// )
239 /// .unwrap();
240 /// assert_eq!(plan.index_dtype(), KernelDType::I64);
241 /// ```
242 #[inline]
243 pub fn index_dtype(&self) -> KernelDType {
244 self.index_dtype
245 }
246
247 /// Arg-reduction operation.
248 ///
249 /// # Examples
250 ///
251 /// ```
252 /// use strided_basic::{ArgReduceOp, ErasedArgReducePlan, KernelDType};
253 /// let plan = ErasedArgReducePlan::compile(
254 /// KernelDType::F32, KernelDType::I64, ArgReduceOp::Min, &[2], &[1], &[], &[], 0,
255 /// )
256 /// .unwrap();
257 /// assert_eq!(plan.op(), ArgReduceOp::Min);
258 /// ```
259 #[inline]
260 pub fn op(&self) -> ArgReduceOp {
261 self.op
262 }
263
264 fn check_layouts(
265 &self,
266 dest_dims: &[usize],
267 dest_strides: &[isize],
268 src: &ErasedRawStridedRef<'_>,
269 ) -> Result<()> {
270 if src.dims() != self.src_dims.as_slice()
271 || src.strides() != self.src_strides.as_slice()
272 || dest_dims != self.dest_dims.as_slice()
273 || dest_strides != self.dest_strides.as_slice()
274 {
275 return Err(StridedError::PlanLayoutMismatch);
276 }
277 Ok(())
278 }
279
280 /// Execute into an initialized index destination.
281 ///
282 /// # Examples
283 ///
284 /// ```
285 /// use strided_basic::{
286 /// Exec, ArgReduceOp, ErasedArgReducePlan, ErasedRawStridedMut, ErasedRawStridedRef,
287 /// KernelDType,
288 /// };
289 /// let src = [3_i32, -9, 9, 1];
290 /// let mut out = [0_i32; 1];
291 /// let plan = ErasedArgReducePlan::compile(
292 /// KernelDType::I32, KernelDType::I32, ArgReduceOp::MaxAbs, &[4], &[1], &[], &[], 0,
293 /// )
294 /// .unwrap();
295 /// let src_ref = ErasedRawStridedRef::from_slice(&src, &[4], &[1], 0).unwrap();
296 /// let mut dest = ErasedRawStridedMut::from_slice_mut(&mut out, &[], &[], 0).unwrap();
297 /// plan.execute(&mut dest, &src_ref, Exec::serial()).unwrap();
298 /// assert_eq!(out, [1]);
299 /// ```
300 ///
301 /// # Errors
302 ///
303 /// Returns `DTypeMismatch` or `PlanLayoutMismatch` when a descriptor does
304 /// not match the plan, before any destination write.
305 pub fn execute(
306 &self,
307 dest: &mut ErasedRawStridedMut<'_>,
308 src: &ErasedRawStridedRef<'_>,
309 exec: Exec<'_>,
310 ) -> Result<()> {
311 check_dtype(self.index_dtype, dest.dtype())?;
312 check_dtype(self.dtype, src.dtype())?;
313 self.check_layouts(dest.dims(), dest.strides(), src)?;
314 match self.index_dtype {
315 KernelDType::I32 => {
316 let mut writer = reduce_writer::<i32>(dest)?;
317 self.dispatch_dtype(&mut writer, src, exec)
318 }
319 _ => {
320 let mut writer = reduce_writer::<i64>(dest)?;
321 self.dispatch_dtype(&mut writer, src, exec)
322 }
323 }
324 }
325
326 /// Execute into an uninitialized index destination.
327 ///
328 /// On success every reachable destination element is written; validation
329 /// errors are returned before any write.
330 ///
331 /// # Examples
332 ///
333 /// ```
334 /// use core::mem::MaybeUninit;
335 /// use num_complex::Complex64;
336 /// use strided_basic::{
337 /// Exec, ArgReduceOp, ErasedArgReducePlan, ErasedRawStridedPtr, ErasedRawStridedRef,
338 /// ErasedRawStridedUninitMut, KernelDType,
339 /// };
340 /// let src = [Complex64::new(3.0, 4.0), Complex64::new(0.0, 6.0)];
341 /// let mut out = [MaybeUninit::<i64>::uninit()];
342 /// let plan = ErasedArgReducePlan::compile(
343 /// KernelDType::C64, KernelDType::I64, ArgReduceOp::MinAbs, &[2], &[1], &[], &[], 0,
344 /// )
345 /// .unwrap();
346 /// let src_ref = ErasedRawStridedRef::from_slice(&src, &[2], &[1], 0).unwrap();
347 /// let src_ptr = ErasedRawStridedPtr::from_ref(&src_ref);
348 /// let mut dest = ErasedRawStridedUninitMut::from_uninit_slice(&mut out, &[], &[], 0).unwrap();
349 /// plan.execute_uninit(&mut dest, &src_ptr, Exec::serial()).unwrap();
350 /// assert_eq!(unsafe { out[0].assume_init() }, 0);
351 /// ```
352 ///
353 /// # Errors
354 ///
355 /// As [`Self::execute`], plus `OverlappingInputOutput` when the source
356 /// overlaps the destination allocation.
357 pub fn execute_uninit(
358 &self,
359 dest: &mut ErasedRawStridedUninitMut<'_>,
360 src: &ErasedRawStridedPtr<'_>,
361 exec: Exec<'_>,
362 ) -> Result<()> {
363 check_dtype(self.index_dtype, dest.dtype())?;
364 check_dtype(self.dtype, src.dtype())?;
365 validate_uninit_no_overlap(dest, src, 0)?;
366 // SAFETY: the owning erased entry rejected all input/output overlap before conversion.
367 let src = unsafe { src.try_as_ref_after_no_overlap() }?;
368 self.check_layouts(dest.dims(), dest.strides(), &src)?;
369 match self.index_dtype {
370 KernelDType::I32 => {
371 let mut writer = reduce_uninit_writer::<i32>(dest)?;
372 self.dispatch_dtype(&mut writer, &src, exec)
373 }
374 _ => {
375 let mut writer = reduce_uninit_writer::<i64>(dest)?;
376 self.dispatch_dtype(&mut writer, &src, exec)
377 }
378 }
379 }
380
381 fn dispatch_dtype<I, W>(
382 &self,
383 dest: &mut W,
384 src: &ErasedRawStridedRef<'_>,
385 exec: Exec<'_>,
386 ) -> Result<()>
387 where
388 I: ArgIndex,
389 W: ReduceWriter<I>,
390 {
391 // The dtype and op are matched once per execution; each loop is
392 // monomorphized for one (dtype, key, direction, index) combination.
393 macro_rules! real {
394 ($ty:ty) => {
395 match self.op {
396 ArgReduceOp::Max => self.run::<$ty, I, W, Plain, Greater>(dest, src, exec),
397 ArgReduceOp::Min => self.run::<$ty, I, W, Plain, Less>(dest, src, exec),
398 ArgReduceOp::MaxAbs => {
399 self.run::<$ty, I, W, Magnitude, Greater>(dest, src, exec)
400 }
401 ArgReduceOp::MinAbs => self.run::<$ty, I, W, Magnitude, Less>(dest, src, exec),
402 }
403 };
404 }
405 macro_rules! complex {
406 ($ty:ty) => {
407 match self.op {
408 ArgReduceOp::MaxAbs => {
409 self.run::<$ty, I, W, Magnitude, Greater>(dest, src, exec)
410 }
411 ArgReduceOp::MinAbs => self.run::<$ty, I, W, Magnitude, Less>(dest, src, exec),
412 // INVARIANT: check_arg_dtype rejects ordered complex ops at compile.
413 ArgReduceOp::Max | ArgReduceOp::Min => Err(StridedError::UnsupportedOp {
414 op: self.op.label(),
415 dtype: self.dtype.label(),
416 }),
417 }
418 };
419 }
420 match self.dtype {
421 KernelDType::F32 => real!(f32),
422 KernelDType::F64 => real!(f64),
423 KernelDType::I32 => real!(i32),
424 KernelDType::I64 => real!(i64),
425 KernelDType::C32 => complex!(Complex32),
426 KernelDType::C64 => complex!(Complex64),
427 _ => Err(StridedError::UnsupportedDType {
428 dtype: self.dtype.label(),
429 }),
430 }
431 }
432
433 fn run<T, I, W, F, D>(
434 &self,
435 dest: &mut W,
436 src: &ErasedRawStridedRef<'_>,
437 exec: Exec<'_>,
438 ) -> Result<()>
439 where
440 T: KernelStorageElement + Send + Sync,
441 I: ArgIndex,
442 W: ReduceWriter<I>,
443 F: KeyFn<T>,
444 D: Direction,
445 {
446 let layout = &self.layout;
447 let source = UnitPtr(src.data_as::<T>()?.as_ptr() as *mut T);
448 // SAFETY: the validated writer owns the destination allocation.
449 let target = UnitPtr(unsafe { dest.ptr() });
450 let n = layout.axis_len;
451 let ss = layout.src_axis_stride;
452 let lane = layout.dest_lane_stride;
453 let kernel = ArgUnit::<T, I, F, D> {
454 source,
455 target,
456 n,
457 ss,
458 lane,
459 _ops: core::marker::PhantomData,
460 };
461 // INVARIANT: (1) compile checked the signed source/destination spans
462 // and every cursor step/reset, and rejected an empty axis; (2) the raw
463 // descriptors validated every reachable offset; (3) execute checked
464 // exact plan-layout equality. Units own disjoint outputs.
465 // SAFETY: the three-link invariant above.
466 unsafe { for_each_unit(layout, src.offset(), dest.offset(), kernel, exec) }
467 }
468}
469
470/// Per-unit arg-reduction kernel of one execution.
471struct ArgUnit<T, I, F, D> {
472 source: UnitPtr<T>,
473 target: UnitPtr<I>,
474 n: usize,
475 ss: isize,
476 lane: isize,
477 _ops: core::marker::PhantomData<fn() -> (F, D)>,
478}
479
480impl<T, I, F, D> Clone for ArgUnit<T, I, F, D> {
481 fn clone(&self) -> Self {
482 *self
483 }
484}
485impl<T, I, F, D> Copy for ArgUnit<T, I, F, D> {}
486
487impl<T, I, F, D> UnitKernel for ArgUnit<T, I, F, D>
488where
489 T: KernelStorageElement + Send + Sync,
490 I: ArgIndex,
491 F: KeyFn<T>,
492 D: Direction,
493{
494 #[inline(always)]
495 unsafe fn unit(self, so: isize, d_o: isize, width: usize) {
496 let Self {
497 source,
498 target,
499 n,
500 ss,
501 lane,
502 ..
503 } = self;
504 // SAFETY: the caller passes offsets of the validated layout.
505 unsafe {
506 if width == 1 {
507 let index = arg_line::<T, F, D>(source.get(), so, ss, n);
508 target.get().offset(d_o).write(I::from_index(index));
509 } else {
510 arg_panel::<T, I, F, D>(source.get(), so, ss, n, target.get(), d_o, lane, width);
511 }
512 }
513 }
514}
515
516fn check_arg_dtype(dtype: KernelDType, op: ArgReduceOp) -> Result<()> {
517 match dtype {
518 KernelDType::F32 | KernelDType::F64 | KernelDType::I32 | KernelDType::I64 => Ok(()),
519 KernelDType::C32 | KernelDType::C64 => match op {
520 ArgReduceOp::MaxAbs | ArgReduceOp::MinAbs => Ok(()),
521 ArgReduceOp::Max | ArgReduceOp::Min => Err(StridedError::UnsupportedOp {
522 op: op.label(),
523 dtype: dtype.label(),
524 }),
525 },
526 _ => Err(StridedError::UnsupportedDType {
527 dtype: dtype.label(),
528 }),
529 }
530}
531
532/// Index element written to the destination.
533pub(super) trait ArgIndex: KernelStorageElement + Send + Sync {
534 fn from_index(index: usize) -> Self;
535}
536
537impl ArgIndex for i32 {
538 #[inline(always)]
539 fn from_index(index: usize) -> Self {
540 // INVARIANT: compile rejected axes whose last index exceeds i32::MAX.
541 index as i32
542 }
543}
544
545impl ArgIndex for i64 {
546 #[inline(always)]
547 fn from_index(index: usize) -> Self {
548 // INVARIANT: an addressable axis length fits in i64.
549 index as i64
550 }
551}
552
553/// Comparable key of an element.
554pub(super) trait OrderKey: Copy + PartialEq {
555 /// Whether the key is NaN (never for integer keys).
556 fn key_is_nan(self) -> bool;
557 /// Whether `candidate` replaces `best` for a maximum: strictly greater,
558 /// or the first NaN.
559 fn beats_max(candidate: Self, best: Self) -> bool;
560 /// Whether `candidate` replaces `best` for a minimum: strictly less, or
561 /// the first NaN.
562 fn beats_min(candidate: Self, best: Self) -> bool;
563}
564
565macro_rules! impl_float_key {
566 ($($ty:ty),*) => {$(
567 impl OrderKey for $ty {
568 #[inline(always)]
569 fn key_is_nan(self) -> bool {
570 self.is_nan()
571 }
572 #[inline(always)]
573 fn beats_max(candidate: Self, best: Self) -> bool {
574 // Select form without a data dependent branch; a NaN `best`
575 // is never replaced, so the first NaN wins.
576 (candidate > best) | (candidate.is_nan() & !best.is_nan())
577 }
578 #[inline(always)]
579 fn beats_min(candidate: Self, best: Self) -> bool {
580 (candidate < best) | (candidate.is_nan() & !best.is_nan())
581 }
582 }
583 )*};
584}
585impl_float_key!(f32, f64);
586
587macro_rules! impl_int_key {
588 ($($ty:ty),*) => {$(
589 impl OrderKey for $ty {
590 #[inline(always)]
591 fn key_is_nan(self) -> bool {
592 false
593 }
594 #[inline(always)]
595 fn beats_max(candidate: Self, best: Self) -> bool {
596 candidate > best
597 }
598 #[inline(always)]
599 fn beats_min(candidate: Self, best: Self) -> bool {
600 candidate < best
601 }
602 }
603 )*};
604}
605impl_int_key!(i32, i64, u32, u64);
606
607/// Maps an element to its comparison key.
608pub(super) trait KeyFn<T> {
609 type Key: OrderKey;
610 fn key(value: T) -> Self::Key;
611}
612
613/// The value itself (real dtypes).
614pub(super) struct Plain;
615/// The magnitude `|x|`.
616pub(super) struct Magnitude;
617
618macro_rules! impl_plain_key {
619 ($($ty:ty),*) => {$(
620 impl KeyFn<$ty> for Plain {
621 type Key = $ty;
622 #[inline(always)]
623 fn key(value: $ty) -> $ty {
624 value
625 }
626 }
627 )*};
628}
629impl_plain_key!(f32, f64, i32, i64);
630
631impl KeyFn<f32> for Magnitude {
632 type Key = f32;
633 #[inline(always)]
634 fn key(value: f32) -> f32 {
635 value.abs()
636 }
637}
638impl KeyFn<f64> for Magnitude {
639 type Key = f64;
640 #[inline(always)]
641 fn key(value: f64) -> f64 {
642 value.abs()
643 }
644}
645impl KeyFn<i32> for Magnitude {
646 type Key = u32;
647 #[inline(always)]
648 fn key(value: i32) -> u32 {
649 value.unsigned_abs()
650 }
651}
652impl KeyFn<i64> for Magnitude {
653 type Key = u64;
654 #[inline(always)]
655 fn key(value: i64) -> u64 {
656 value.unsigned_abs()
657 }
658}
659impl KeyFn<Complex32> for Magnitude {
660 type Key = f32;
661 #[inline(always)]
662 fn key(value: Complex32) -> f32 {
663 // `hypot` returns +inf for an infinite component even when the other
664 // is NaN; the NaN test keeps any NaN component a NaN key.
665 if value.re.is_nan() || value.im.is_nan() {
666 f32::NAN
667 } else {
668 value.re.hypot(value.im)
669 }
670 }
671}
672impl KeyFn<Complex64> for Magnitude {
673 type Key = f64;
674 #[inline(always)]
675 fn key(value: Complex64) -> f64 {
676 if value.re.is_nan() || value.im.is_nan() {
677 f64::NAN
678 } else {
679 value.re.hypot(value.im)
680 }
681 }
682}
683
684/// Maximum or minimum, fixed at compile time.
685pub(super) trait Direction {
686 fn beats<K: OrderKey>(candidate: K, best: K) -> bool;
687}
688pub(super) struct Greater;
689pub(super) struct Less;
690impl Direction for Greater {
691 #[inline(always)]
692 fn beats<K: OrderKey>(candidate: K, best: K) -> bool {
693 K::beats_max(candidate, best)
694 }
695}
696impl Direction for Less {
697 #[inline(always)]
698 fn beats<K: OrderKey>(candidate: K, best: K) -> bool {
699 K::beats_min(candidate, best)
700 }
701}
702
703/// Independent lanes of the contiguous winner search.
704const ARG_LANES: usize = 8;
705
706/// Index of the winning element of one line.
707///
708/// A unit-stride line runs two passes: a lane-parallel search for the winning
709/// key (NaN if the line has one), then a scan for the first element whose key
710/// equals it (or is NaN). Equal keys tie, so the second pass returns the
711/// lowest index of the winner, exactly as the sequential scan used for
712/// strided lines.
713///
714/// # Safety
715///
716/// Every `src.offset(so + k * ss)` for `k < n` must be readable, and `n > 0`.
717#[inline(always)]
718unsafe fn arg_line<T, F, D>(src: *const T, so: isize, ss: isize, n: usize) -> usize
719where
720 T: Copy,
721 F: KeyFn<T>,
722 D: Direction,
723{
724 // SAFETY: the caller guarantees every visited offset and `n > 0`; a unit
725 // stride line is `n` contiguous elements.
726 unsafe {
727 if ss == 1 {
728 let values = core::slice::from_raw_parts(src.offset(so), n);
729 let mut lanes = [F::key(values[0]); ARG_LANES];
730 let (chunks, remainder) = values.as_chunks::<ARG_LANES>();
731 for chunk in chunks {
732 for (lane, &value) in lanes.iter_mut().zip(chunk) {
733 let key = F::key(value);
734 *lane = if D::beats(key, *lane) { key } else { *lane };
735 }
736 }
737 // Which NaN or which signed zero wins here does not matter: the
738 // second pass matches by NaN-ness or by equality.
739 let mut winner = lanes[0];
740 let tail = remainder.iter().map(|&value| F::key(value));
741 for key in lanes[1..].iter().copied().chain(tail) {
742 if D::beats(key, winner) {
743 winner = key;
744 }
745 }
746 let found = if winner.key_is_nan() {
747 values.iter().position(|&value| F::key(value).key_is_nan())
748 } else {
749 values.iter().position(|&value| F::key(value) == winner)
750 };
751 // INVARIANT: the winner is the key of some element of the line.
752 return found.unwrap_or(0);
753 }
754 let mut best = F::key(src.offset(so).read());
755 let mut best_index = 0;
756 let mut offset = so;
757 for index in 1..n {
758 offset += ss;
759 let key = F::key(src.offset(offset).read());
760 if D::beats(key, best) {
761 best = key;
762 best_index = index;
763 }
764 }
765 best_index
766 }
767}
768
769/// Arg-reduces `width` adjacent lines whose source elements are contiguous
770/// across the lines; output `j` is written at `d_o + j * lane`.
771///
772/// # Safety
773///
774/// As [`arg_line`] for each line `j < width` with source base `so + j`, every
775/// destination offset must be writable, and `width <= PANEL`.
776// Panel leaf: both base/offset/stride triples, the length and the panel width, once
777// per panel.
778#[allow(clippy::too_many_arguments)]
779#[inline(always)]
780unsafe fn arg_panel<T, I, F, D>(
781 src: *const T,
782 so: isize,
783 ss: isize,
784 n: usize,
785 dst: *mut I,
786 d_o: isize,
787 lane: isize,
788 width: usize,
789) where
790 T: Copy,
791 I: ArgIndex,
792 F: KeyFn<T>,
793 D: Direction,
794{
795 debug_assert!(width <= PANEL);
796 // SAFETY: the caller guarantees `width` contiguous source elements at
797 // every axis position and the destination offsets.
798 unsafe {
799 let first = core::slice::from_raw_parts(src.offset(so), width);
800 let mut best = [F::key(first[0]); PANEL];
801 let mut best_index = [0usize; PANEL];
802 for (best, &value) in best.iter_mut().zip(first) {
803 *best = F::key(value);
804 }
805 let best = &mut best[..width];
806 let best_index = &mut best_index[..width];
807 let mut offset = so;
808 for index in 1..n {
809 offset += ss;
810 let row = core::slice::from_raw_parts(src.offset(offset), width);
811 for ((best, best_index), &value) in best.iter_mut().zip(best_index.iter_mut()).zip(row)
812 {
813 let key = F::key(value);
814 let take = D::beats(key, *best);
815 *best = if take { key } else { *best };
816 *best_index = if take { index } else { *best_index };
817 }
818 }
819 for (lane_index, &index) in best_index.iter().enumerate() {
820 dst.offset(d_o + lane_index as isize * lane)
821 .write(I::from_index(index));
822 }
823 }
824}