Skip to main content

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}