Skip to main content

strided_basic/
raw_ops.rs

1//! Allocation-free copy/axpy over borrowed raw strided layouts.
2//!
3//! The map/zip kernels build a traversal plan per call; for small replay
4//! copies that fixed cost dominates. These entry points take
5//! [`RawStridedRef`]/[`RawStridedMut`], fuse the stride pair into a loop nest
6//! (inline storage for fused ranks at most [`RAW_FUSED_RANK_LIMIT`], one
7//! rank-bounded spill above that), and run plain loops - no view plan, no
8//! cache, and no per-element allocation on any call path. Higher *original*
9//! ranks are normalized and fused before that choice is made, so they no
10//! longer leave the fused replay.
11
12use crate::cost::KernelClass;
13use crate::{ElementOpApply, Exec, RawStridedMut, RawStridedRef, Result};
14use core::mem::MaybeUninit;
15use core::num::NonZeroUsize;
16use core::ops::{Add, Mul};
17
18/// Rank up to which a fused loop nest is stored inline.
19///
20/// The stateless [`copy_scale_raw`] family and [`crate::CopyPlan`] fuse any rank:
21/// layouts whose *fused* rank is at most this limit replay from that inline
22/// storage, and higher fused ranks spill to storage bounded by their rank.
23///
24/// Replay is allocation-free for an original rank at most this limit. A higher
25/// *original* rank needs one transient scratch buffer even when the fused layout
26/// still fits inline, because fusion happens before the representation is
27/// chosen; the replay itself is still allocation-free in that case.
28pub const RAW_FUSED_RANK_LIMIT: usize = 8;
29
30/// One fused axis, used while sorting and merging axes and when a layout has to
31/// spill beyond [`RAW_FUSED_RANK_LIMIT`].
32#[derive(Clone, Copy, Debug)]
33pub(crate) struct FusedAxis {
34    pub(crate) dim: usize,
35    pub(crate) dst: isize,
36    pub(crate) src: isize,
37}
38
39const EMPTY_AXIS: FusedAxis = FusedAxis {
40    dim: 1,
41    dst: 0,
42    src: 0,
43};
44
45/// Stack-allocated fused stride pair (axes ordered by destination stride,
46/// adjacent contiguous axes merged). Built once and replayed by both the
47/// per-call raw kernels and the prepared [`crate::CopyPlan`].
48///
49/// This is the representation every call site replays through, so it keeps the
50/// exact shape, size and `Copy`-ness it had before high-rank fusion existed.
51#[derive(Clone, Copy, Debug)]
52pub(crate) struct FusedPairLayout {
53    pub(crate) rank: usize,
54    pub(crate) dims: [usize; RAW_FUSED_RANK_LIMIT],
55    dst_strides: [isize; RAW_FUSED_RANK_LIMIT],
56    src_strides: [isize; RAW_FUSED_RANK_LIMIT],
57}
58
59impl FusedPairLayout {
60    /// An empty rank-zero layout (one element at the base offset).
61    ///
62    /// Used as the neutral value when an inline `TinyVec<[CopyPlan; N]>` is
63    /// default-initialized; it is never executed as a real plan.
64    fn empty() -> Self {
65        Self {
66            rank: 0,
67            dims: [1; RAW_FUSED_RANK_LIMIT],
68            dst_strides: [0; RAW_FUSED_RANK_LIMIT],
69            src_strides: [0; RAW_FUSED_RANK_LIMIT],
70        }
71    }
72
73    fn from_axes(axes: &[FusedAxis]) -> Self {
74        debug_assert!(axes.len() <= RAW_FUSED_RANK_LIMIT);
75        let mut layout = Self {
76            rank: axes.len(),
77            dims: [1; RAW_FUSED_RANK_LIMIT],
78            dst_strides: [0; RAW_FUSED_RANK_LIMIT],
79            src_strides: [0; RAW_FUSED_RANK_LIMIT],
80        };
81        for (slot, axis) in layout.dims[..axes.len()].iter_mut().zip(axes) {
82            *slot = axis.dim;
83        }
84        for (slot, axis) in layout.dst_strides[..axes.len()].iter_mut().zip(axes) {
85            *slot = axis.dst;
86        }
87        for (slot, axis) in layout.src_strides[..axes.len()].iter_mut().zip(axes) {
88            *slot = axis.src;
89        }
90        layout
91    }
92}
93
94/// A fused pair traversal of any rank.
95///
96/// Fused ranks at most [`RAW_FUSED_RANK_LIMIT`] use the inline layout; longer
97/// layouts keep their axes in one `Vec`. That storage is sized by the original
98/// rank (the fusion scratch is reused, and `truncate` keeps its capacity), never
99/// by the tensor's element count.
100#[derive(Clone, Debug)]
101pub(crate) enum PairTraversal {
102    Inline(FusedPairLayout),
103    Spilled(Vec<FusedAxis>),
104}
105
106impl Default for FusedPairLayout {
107    fn default() -> Self {
108        Self::empty()
109    }
110}
111
112impl Default for PairTraversal {
113    fn default() -> Self {
114        Self::empty()
115    }
116}
117
118impl PairTraversal {
119    /// The empty inline layout, used as a neutral default.
120    #[inline]
121    fn empty() -> Self {
122        Self::Inline(FusedPairLayout::empty())
123    }
124
125    /// The inline layout, or `None` when the traversal spilled.
126    #[inline]
127    pub(crate) fn inline(&self) -> Option<&FusedPairLayout> {
128        match self {
129            Self::Inline(layout) => Some(layout),
130            Self::Spilled(_) => None,
131        }
132    }
133
134    /// Number of fused axes.
135    #[cfg(test)]
136    pub(crate) fn rank(&self) -> usize {
137        match self {
138            Self::Inline(layout) => layout.rank,
139            Self::Spilled(axes) => axes.len(),
140        }
141    }
142}
143
144/// Sort `dims`/`dst_strides`/`src_strides` by destination stride, drop size-1
145/// axes, and merge axes that are contiguous in both layouts.
146///
147/// Returns the fused rank written to `scratch[..rank]`. A zero extent collapses
148/// to a single zero-length axis, which every replay treats as an empty range.
149fn fuse_axes(
150    scratch: &mut [FusedAxis],
151    dims: &[usize],
152    dst_strides: &[isize],
153    src_strides: &[isize],
154) -> usize {
155    debug_assert!(scratch.len() >= dims.len());
156    let mut rank = 0usize;
157    for axis in 0..dims.len() {
158        if dims[axis] == 1 {
159            continue;
160        }
161        if dims[axis] == 0 {
162            scratch[0] = FusedAxis {
163                dim: 0,
164                dst: 0,
165                src: 0,
166            };
167            return 1;
168        }
169        let entry = FusedAxis {
170            dim: dims[axis],
171            dst: dst_strides[axis],
172            src: src_strides[axis],
173        };
174        let mut position = rank;
175        while position > 0 && scratch[position - 1].dst > entry.dst {
176            scratch[position] = scratch[position - 1];
177            position -= 1;
178        }
179        scratch[position] = entry;
180        rank += 1;
181    }
182    if rank == 0 {
183        scratch[0] = EMPTY_AXIS;
184        return 1;
185    }
186    let mut fused = 0usize;
187    for axis in 1..rank {
188        // A merged extent that overflows (possible for a stride-0 broadcast
189        // whose element count exceeds usize) leaves the axes unfused.
190        let merged = isize::try_from(scratch[fused].dim)
191            .ok()
192            .filter(|&extent| {
193                scratch[fused].dst.checked_mul(extent) == Some(scratch[axis].dst)
194                    && scratch[fused].src.checked_mul(extent) == Some(scratch[axis].src)
195            })
196            .and_then(|_| scratch[fused].dim.checked_mul(scratch[axis].dim));
197        if let Some(merged) = merged {
198            scratch[fused].dim = merged;
199        } else {
200            fused += 1;
201            scratch[fused] = scratch[axis];
202        }
203    }
204    fused + 1
205}
206
207/// Fuse a raw stride pair into a traversal of any rank.
208///
209/// Inline when the fused rank is at most [`RAW_FUSED_RANK_LIMIT`], otherwise one
210/// rank-bounded spill. An original rank above the limit uses a transient scratch
211/// buffer even when the fused layout still fits inline, so that fusion happens
212/// before the representation is chosen.
213pub(crate) fn fuse_pair_traversal(
214    dims: &[usize],
215    dst_strides: &[isize],
216    src_strides: &[isize],
217) -> PairTraversal {
218    if dims.len() <= RAW_FUSED_RANK_LIMIT {
219        let mut scratch = [EMPTY_AXIS; RAW_FUSED_RANK_LIMIT];
220        let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
221        debug_assert!(rank <= RAW_FUSED_RANK_LIMIT);
222        return PairTraversal::Inline(FusedPairLayout::from_axes(&scratch[..rank]));
223    }
224    let mut scratch = vec![EMPTY_AXIS; dims.len()];
225    let rank = fuse_axes(&mut scratch, dims, dst_strides, src_strides);
226    scratch.truncate(rank);
227    if rank <= RAW_FUSED_RANK_LIMIT {
228        PairTraversal::Inline(FusedPairLayout::from_axes(&scratch))
229    } else {
230        PairTraversal::Spilled(scratch)
231    }
232}
233
234impl PairTraversal {
235    /// The given axes as a traversal, in their given order: nothing is
236    /// sorted, merged or dropped. Rank zero becomes the one-element
237    /// `EMPTY_AXIS` layout that [`fuse_axes`] also produces.
238    ///
239    /// The three slices must have equal length, and the extents a checked,
240    /// nonzero product (the replay totals multiply them unchecked).
241    pub(crate) fn given(dims: &[usize], dst_strides: &[isize], src_strides: &[isize]) -> Self {
242        debug_assert!(dims.len() == dst_strides.len() && dims.len() == src_strides.len());
243        let rank = dims.len();
244        if rank > RAW_FUSED_RANK_LIMIT {
245            return Self::Spilled(
246                dims.iter()
247                    .zip(dst_strides)
248                    .zip(src_strides)
249                    .map(|((&dim, &dst), &src)| FusedAxis { dim, dst, src })
250                    .collect(),
251            );
252        }
253        let mut layout = FusedPairLayout::empty();
254        layout.rank = rank.max(1);
255        layout.dims[..rank].copy_from_slice(dims);
256        layout.dst_strides[..rank].copy_from_slice(dst_strides);
257        layout.src_strides[..rank].copy_from_slice(src_strides);
258        Self::Inline(layout)
259    }
260}
261
262/// Fuse a raw stride pair into the inline representation.
263///
264/// Returns `None` when the fused rank exceeds [`RAW_FUSED_RANK_LIMIT`]. Used by
265/// the window plans, whose non-fused replay is compiled alongside the plan.
266pub(crate) fn fuse_pair_layout(
267    dims: &[usize],
268    dst_strides: &[isize],
269    src_strides: &[isize],
270) -> Option<FusedPairLayout> {
271    match fuse_pair_traversal(dims, dst_strides, src_strides) {
272        PairTraversal::Inline(layout) => Some(layout),
273        PairTraversal::Spilled(_) => None,
274    }
275}
276
277/// Number of logical elements covered by a fused layout.
278///
279/// Every constructor of a [`FusedPairLayout`] starts from dims whose product
280/// was checked by [`crate::kernel::total_len`], and fusion only merges axes
281/// with a checked product, so the product cannot overflow.
282#[inline]
283pub(crate) fn fused_total(layout: &FusedPairLayout) -> usize {
284    layout.dims[..layout.rank].iter().product()
285}
286
287/// Number of logical elements covered by a spilled axis list.
288#[inline]
289fn spilled_total(axes: &[FusedAxis]) -> usize {
290    axes.iter().map(|axis| axis.dim).product()
291}
292
293/// Serial replay of a fused pair layout over borrowed raw views.
294///
295/// The destination layout need not be injective: runs are replayed in order,
296/// so accumulating callers such as [`axpy_raw`] keep their sequential
297/// semantics. Parallel replay goes through `copy_plan::replay_fused`, which
298/// the plans and the `replay_*_raw` entries call only with a destination
299/// proven injective or a serial token.
300pub(crate) fn apply_fused_pair<D, S, Apply>(
301    dst: &mut RawStridedMut<'_, D>,
302    src: &RawStridedRef<'_, S>,
303    layout: &FusedPairLayout,
304    apply: Apply,
305) where
306    D: Copy,
307    S: Copy,
308    Apply: Fn(&mut D, S),
309{
310    let total = fused_total(layout);
311    if total == 0 {
312        return;
313    }
314    let src_ptr = src.data().as_ptr();
315    let src_base = src.offset();
316    let dst_base = dst.offset();
317    let dst_ptr = dst.data_mut().as_mut_ptr();
318    // SAFETY: `RawStridedRef`/`RawStridedMut` guarantee (by `new`, or by the
319    // caller of `new_unchecked`) that every offset reachable from their offset
320    // through their dims/strides lies inside their data. Callers pass a layout
321    // fused from exactly those dims/strides, so every logical index in
322    // `0..total` maps to in-bounds source and destination slots. The shared
323    // and exclusive borrows cannot overlap, and this is the only writer.
324    unsafe {
325        apply_fused_range(
326            dst_ptr, dst_base, src_ptr, src_base, layout, 0, total, &apply,
327        );
328    }
329}
330
331/// Serial replay of a spilled fused axis list over borrowed raw views.
332///
333/// Kept out of line and separate from [`apply_fused_pair`] so that the inline
334/// entry points keep the code shape they had before high-rank fusion existed:
335/// fused ranks above [`RAW_FUSED_RANK_LIMIT`] are the rare case, and inlining
336/// this second carry loop into them measurably slowed the inline path (extra
337/// register pressure in a loop that runs once per short run).
338#[inline(never)]
339pub(crate) fn apply_spilled_pair<D, S, Apply>(
340    dst: &mut RawStridedMut<'_, D>,
341    src: &RawStridedRef<'_, S>,
342    axes: &[FusedAxis],
343    apply: Apply,
344) where
345    D: Copy,
346    S: Copy,
347    Apply: Fn(&mut D, S),
348{
349    let total = spilled_total(axes);
350    if total == 0 {
351        return;
352    }
353    let src_ptr = src.data().as_ptr();
354    let src_base = src.offset();
355    let dst_base = dst.offset();
356    let dst_ptr = dst.data_mut().as_mut_ptr();
357    // SAFETY: same contract as `apply_fused_pair`, for the axis list fused from
358    // the same dims/strides.
359    unsafe {
360        apply_spilled_range(dst_ptr, dst_base, src_ptr, src_base, axes, 0, total, &apply);
361    }
362}
363
364/// Replay logical indices `start..start + len` of a fused pair layout, in
365/// column-major order of the fused axes (axis 0 fastest).
366///
367/// The start coordinate is decoded once; runs along axis 0 then advance the
368/// outer coordinates incrementally, so no per-element range checks or
369/// coordinate rebuilds remain in the hot loop.
370///
371/// # Safety
372///
373/// - `start + len` must not exceed [`fused_total`] of `layout`.
374/// - For every logical index `i` in the range, `dst_base` plus the fused
375///   destination offset of `i` must be an in-bounds, writable slot of the
376///   allocation behind `dst_ptr`, and likewise `src_base` plus the source
377///   offset must be an in-bounds, readable slot behind `src_ptr`.
378/// - No other thread may access the destination slots of this range while it
379///   runs, and the source slots must not be written concurrently. Destination
380///   and source slots must not overlap.
381#[allow(clippy::too_many_arguments)]
382pub(crate) unsafe fn apply_fused_range<D, S, Apply>(
383    dst_ptr: *mut D,
384    dst_base: isize,
385    src_ptr: *const S,
386    src_base: isize,
387    layout: &FusedPairLayout,
388    start: usize,
389    len: usize,
390    apply: &Apply,
391) where
392    D: Copy,
393    S: Copy,
394    Apply: Fn(&mut D, S),
395{
396    if len == 0 {
397        return;
398    }
399    let rank = layout.rank;
400    let inner_len = layout.dims[0];
401    let inner_dst = layout.dst_strides[0];
402    let inner_src = layout.src_strides[0];
403
404    // Decode the start coordinate once per range. `dst_offset`/`src_offset`
405    // track the offset of the current run start (outer coordinates plus the
406    // inner coordinate `inner_start`); every value is a reachable offset.
407    let mut index = [0usize; RAW_FUSED_RANK_LIMIT];
408    let mut rest = start;
409    let mut dst_outer = dst_base;
410    let mut src_outer = src_base;
411    for axis in 0..rank {
412        let dim = layout.dims[axis];
413        index[axis] = rest % dim;
414        rest /= dim;
415        if axis > 0 {
416            dst_outer += index[axis] as isize * layout.dst_strides[axis];
417            src_outer += index[axis] as isize * layout.src_strides[axis];
418        }
419    }
420    let mut inner_start = index[0];
421    let mut remaining = len;
422    loop {
423        let run = (inner_len - inner_start).min(remaining);
424        let dst_run = dst_outer + inner_start as isize * inner_dst;
425        let src_run = src_outer + inner_start as isize * inner_src;
426        // SAFETY: the run covers logical indices inside the caller's range, so
427        // by this function's contract every slot touched below is in-bounds,
428        // exclusively owned by this call (destination) and unaliased.
429        unsafe {
430            apply_run(
431                dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
432            )
433        };
434        remaining -= run;
435        if remaining == 0 {
436            return;
437        }
438        inner_start = 0;
439        // Advance an axis only when another position along it follows, and
440        // rewind it from its last position, so every intermediate base is a
441        // reachable offset of a validated layout (issue #243 follow-up): a
442        // layout ending within one stride of `isize::MAX` must not overflow.
443        // `remaining > 0` guarantees a following run exists, so the loop
444        // always finds an axis to advance before running out of rank.
445        let mut axis = 1;
446        while axis < rank {
447            if index[axis] + 1 < layout.dims[axis] {
448                index[axis] += 1;
449                dst_outer += layout.dst_strides[axis];
450                src_outer += layout.src_strides[axis];
451                break;
452            }
453            let last = (layout.dims[axis] - 1) as isize;
454            dst_outer -= last * layout.dst_strides[axis];
455            src_outer -= last * layout.src_strides[axis];
456            index[axis] = 0;
457            axis += 1;
458        }
459    }
460}
461
462/// Replay logical indices `start..start + len` of a spilled fused axis list, in
463/// column-major order of the axes (axis 0 fastest).
464///
465/// The carry loop is the one [`apply_fused_range`] uses, over interleaved axes
466/// with its carry state in one rank-bounded `Vec`: no allocation scales with
467/// the tensor size and no per-element coordinate decode happens.
468///
469/// # Safety
470///
471/// The [`apply_fused_range`] contract holds for `axes`.
472///
473/// Kept out of line: inlining this second carry loop into the inline replay
474/// measurably slows that one down.
475#[allow(clippy::too_many_arguments)]
476#[inline(never)]
477pub(crate) unsafe fn apply_spilled_range<D, S, Apply>(
478    dst_ptr: *mut D,
479    dst_base: isize,
480    src_ptr: *const S,
481    src_base: isize,
482    axes: &[FusedAxis],
483    start: usize,
484    len: usize,
485    apply: &Apply,
486) where
487    D: Copy,
488    S: Copy,
489    Apply: Fn(&mut D, S),
490{
491    if len == 0 {
492        return;
493    }
494    let rank = axes.len();
495    let inner_len = axes[0].dim;
496    let inner_dst = axes[0].dst;
497    let inner_src = axes[0].src;
498
499    let mut index = vec![0usize; rank];
500    let mut rest = start;
501    let mut dst_outer = dst_base;
502    let mut src_outer = src_base;
503    for axis in 0..rank {
504        let dim = axes[axis].dim;
505        index[axis] = rest % dim;
506        rest /= dim;
507        if axis > 0 {
508            dst_outer += index[axis] as isize * axes[axis].dst;
509            src_outer += index[axis] as isize * axes[axis].src;
510        }
511    }
512    let mut inner_start = index[0];
513    let mut remaining = len;
514    loop {
515        let run = (inner_len - inner_start).min(remaining);
516        let dst_run = dst_outer + inner_start as isize * inner_dst;
517        let src_run = src_outer + inner_start as isize * inner_src;
518        // SAFETY: the run covers logical indices inside the caller's range, so
519        // by the caller's contract every slot touched below is in-bounds,
520        // exclusively owned by this call (destination) and unaliased.
521        unsafe {
522            apply_run(
523                dst_ptr, dst_run, inner_dst, src_ptr, src_run, inner_src, run, apply,
524            )
525        };
526        remaining -= run;
527        if remaining == 0 {
528            return;
529        }
530        inner_start = 0;
531        // Same incremental carry as the inline replay: offsets only ever hold
532        // reachable positions, and `remaining > 0` guarantees an axis advances.
533        let mut axis = 1;
534        while axis < rank {
535            if index[axis] + 1 < axes[axis].dim {
536                index[axis] += 1;
537                dst_outer += axes[axis].dst;
538                src_outer += axes[axis].src;
539                break;
540            }
541            let last = (axes[axis].dim - 1) as isize;
542            dst_outer -= last * axes[axis].dst;
543            src_outer -= last * axes[axis].src;
544            index[axis] = 0;
545            axis += 1;
546        }
547    }
548}
549
550/// One run along the fused inner axis.
551///
552/// # Safety
553///
554/// Every `dst_offset + k * dst_stride` and `src_offset + k * src_stride` for
555/// `k < len` must be an in-bounds slot as described in [`apply_fused_range`],
556/// with exclusive access to the destination slots.
557#[allow(clippy::too_many_arguments)]
558#[inline(always)]
559unsafe fn apply_run<D, S, Apply>(
560    dst_ptr: *mut D,
561    dst_offset: isize,
562    dst_stride: isize,
563    src_ptr: *const S,
564    src_offset: isize,
565    src_stride: isize,
566    len: usize,
567    apply: &Apply,
568) where
569    D: Copy,
570    S: Copy,
571    Apply: Fn(&mut D, S),
572{
573    if dst_stride == 1 {
574        // SAFETY: a unit destination stride makes the run `len` consecutive
575        // in-bounds slots starting at `dst_offset`, exclusively owned here.
576        let dst_run = unsafe { core::slice::from_raw_parts_mut(dst_ptr.offset(dst_offset), len) };
577        if src_stride == 1 {
578            // A `copy_nonoverlapping` per run is not used for plain copies:
579            // it measured slower than this element loop for short runs
580            // (one `memcpy` call each) and for long cache-resident copies.
581            // SAFETY: `len` consecutive in-bounds source slots, which the
582            // exclusive destination run cannot overlap.
583            let src_run = unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset), len) };
584            for (dst, &value) in dst_run.iter_mut().zip(src_run) {
585                apply(dst, value);
586            }
587            return;
588        }
589        if src_stride == -1 {
590            // INVARIANT: the range walks never pass an empty run, and both
591            // strides are nonzero, so the validated reach `len - 1` fits
592            // `isize`; casting `len` itself would wrap for a run of
593            // `isize::MAX + 1` elements. (A `saturating_sub` here measurably
594            // slowed short unit-stride runs by changing the code layout of
595            // the whole inlined walk.)
596            let last = (len - 1) as isize;
597            // SAFETY: the run reads `src_offset - (len - 1) ..= src_offset`,
598            // all in-bounds; the lowest one is the run's last source slot.
599            let src_run =
600                unsafe { core::slice::from_raw_parts(src_ptr.offset(src_offset - last), len) };
601            for (dst, &value) in dst_run.iter_mut().zip(src_run.iter().rev()) {
602                apply(dst, value);
603            }
604            return;
605        }
606        // SAFETY: the run start is an in-bounds source slot.
607        let src_start = unsafe { src_ptr.offset(src_offset) };
608        for (position, dst) in dst_run.iter_mut().enumerate() {
609            // SAFETY: `position < len`, so this is a run source slot.
610            let value = unsafe { *src_start.offset(position as isize * src_stride) };
611            apply(dst, value);
612        }
613        return;
614    }
615    // SAFETY: the run start is an in-bounds slot of each allocation.
616    let dst_start = unsafe { dst_ptr.offset(dst_offset) };
617    let src_start = unsafe { src_ptr.offset(src_offset) };
618    // The bound stays `usize`: a checked broadcast run may hold more than
619    // `isize::MAX` elements, and `len as isize` would wrap to an empty loop.
620    for position in 0..len {
621        // INVARIANT: a nonzero stride bounds the run by its validated reach,
622        // so `position` fits `isize` exactly; a longer run is possible only
623        // along a zero stride, where the wrapped cast is multiplied by zero.
624        let position = position as isize;
625        // SAFETY: `position < len`, so both are slots of this run.
626        unsafe {
627            let value = *src_start.offset(position * src_stride);
628            apply(&mut *dst_start.offset(position * dst_stride), value);
629        }
630    }
631}
632
633fn ensure_same_dims(dst: &[usize], src: &[usize]) -> Result<()> {
634    if dst != src {
635        return Err(crate::StridedError::ShapeMismatch(
636            dst.to_vec(),
637            src.to_vec(),
638        ));
639    }
640    // Reject an element count beyond usize (a huge stride-0 broadcast)
641    // instead of replaying it.
642    crate::kernel::total_len(dst)?;
643    Ok(())
644}
645
646/// `dest = scale * src` over borrowed raw strided layouts.
647///
648/// # Errors
649///
650/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
651/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
652/// when the element count does not fit `usize`. Nothing is written on error.
653pub fn copy_scale_raw<T>(
654    dest: &mut RawStridedMut<'_, T>,
655    src: &RawStridedRef<'_, T>,
656    scale: T,
657) -> Result<()>
658where
659    T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
660{
661    ensure_same_dims(dest.dims(), src.dims())?;
662    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
663        PairTraversal::Inline(layout) => {
664            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
665                *dst = scale * value
666            })
667        }
668        PairTraversal::Spilled(axes) => {
669            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
670                *dst = scale * value
671            })
672        }
673    }
674    Ok(())
675}
676
677/// `dest = scale * conj(src)` over borrowed raw strided layouts.
678///
679/// # Errors
680///
681/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
682/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
683/// when the element count does not fit `usize`. Nothing is written on error.
684pub fn copy_scale_conj_raw<T>(
685    dest: &mut RawStridedMut<'_, T>,
686    src: &RawStridedRef<'_, T>,
687    scale: T,
688) -> Result<()>
689where
690    T: Copy + Mul<T, Output = T> + ElementOpApply + Send + Sync,
691{
692    ensure_same_dims(dest.dims(), src.dims())?;
693    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
694        PairTraversal::Inline(layout) => {
695            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
696                *dst = scale * value.conj()
697            })
698        }
699        PairTraversal::Spilled(axes) => {
700            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
701                *dst = scale * value.conj()
702            })
703        }
704    }
705    Ok(())
706}
707
708/// `dest = alpha * src + dest` over borrowed raw strided layouts.
709///
710/// # Errors
711///
712/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
713/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
714/// when the element count does not fit `usize`. Nothing is written on error.
715pub fn axpy_raw<T>(
716    dest: &mut RawStridedMut<'_, T>,
717    src: &RawStridedRef<'_, T>,
718    alpha: T,
719) -> Result<()>
720where
721    T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
722{
723    ensure_same_dims(dest.dims(), src.dims())?;
724    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
725        PairTraversal::Inline(layout) => {
726            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
727                *dst = *dst + alpha * value
728            })
729        }
730        PairTraversal::Spilled(axes) => {
731            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
732                *dst = *dst + alpha * value
733            })
734        }
735    }
736    Ok(())
737}
738
739/// `dest = alpha * conj(src) + dest` over borrowed raw strided layouts.
740///
741/// # Errors
742///
743/// Returns [`crate::StridedError::ShapeMismatch`] when `dest` and `src` do
744/// not describe the same extents, or [`crate::StridedError::OffsetOverflow`]
745/// when the element count does not fit `usize`. Nothing is written on error.
746pub fn axpy_conj_raw<T>(
747    dest: &mut RawStridedMut<'_, T>,
748    src: &RawStridedRef<'_, T>,
749    alpha: T,
750) -> Result<()>
751where
752    T: Copy + Add<T, Output = T> + Mul<T, Output = T> + ElementOpApply + Send + Sync,
753{
754    ensure_same_dims(dest.dims(), src.dims())?;
755    match fuse_pair_traversal(dest.dims(), dest.strides(), src.strides()) {
756        PairTraversal::Inline(layout) => {
757            apply_fused_pair(dest, src, &layout, |dst: &mut T, value: T| {
758                *dst = *dst + alpha * value.conj()
759            })
760        }
761        PairTraversal::Spilled(axes) => {
762            apply_spilled_pair(dest, src, &axes, |dst: &mut T, value: T| {
763                *dst = *dst + alpha * value.conj()
764            })
765        }
766    }
767    Ok(())
768}
769
770/// Checked replay of the given axes of two views: the shared body of the
771/// `replay_*_raw` entries.
772///
773/// The element count is checked before anything is built. The unfused
774/// traversal keeps every given extent, and the replay totals (`fused_total`,
775/// `replay_spilled_raw`) take an unchecked product, so the zero-first count
776/// of `kernel::total_len` has to keep an empty layout whose nonzero prefix
777/// overflows, such as `[usize::MAX, 2, 0]`, away from them.
778fn replay_given<D, S, Apply>(
779    dest: &mut RawStridedMut<'_, D>,
780    src: &RawStridedRef<'_, S>,
781    apply: Apply,
782    exec: Exec<'_>,
783) -> Result<()>
784where
785    D: Copy + Send + Sync,
786    S: Copy + Send + Sync,
787    Apply: Fn(&mut D, S) + Sync,
788{
789    ensure_same_dims(dest.dims(), src.dims())?;
790    let total = crate::kernel::total_len(dest.dims())?;
791    if total == 0 {
792        return Ok(());
793    }
794    let traversal = PairTraversal::given(dest.dims(), dest.strides(), src.strides());
795    let mut exec = crate::cost::for_len(exec, KernelClass::Copy, total);
796    if !exec.is_serial()
797        && !crate::layout_check::is_injective_layout_without_alloc(dest.dims(), dest.strides())
798    {
799        // A destination not proven injective replays as one sequential walk,
800        // which is also its defined semantics; the budget-one token cannot be
801        // widened again by the replay's own width rule.
802        exec = exec.limit(NonZeroUsize::MIN);
803    }
804    // SAFETY: `traversal` is built from exactly the views' dims and strides
805    // (`ensure_same_dims` proved the dims agree), so the views' bounds proofs
806    // cover every replayed offset; `total_len` checked the nonzero product;
807    // a non-serial `exec` is left only for a destination proven injective;
808    // the exclusive and shared borrows cannot overlap.
809    unsafe { crate::copy_plan::replay_fused(dest, src, &traversal, apply, exec) };
810    Ok(())
811}
812
813/// `dest = src`, replaying the axes of the two views exactly as given.
814///
815/// The views carry already-fused dims: no axis is reordered, dropped or
816/// merged, and no plan is compiled. Axis 0 is the inner run. Bounds were validated when the views were built
817/// ([`RawStridedRef::new`], [`RawStridedMut::new`]). On a successful call the
818/// replay itself (validation, traversal and dispatch) allocates nothing for a
819/// rank at most [`RAW_FUSED_RANK_LIMIT`]; above it, the axis list and the cursor
820/// of each replayed range are stored in rank-sized buffers. An error may
821/// allocate its payload.
822///
823/// The width comes from the repository rule on `exec`. A parallel replay runs
824/// only on a destination proven injective without allocating; any other
825/// destination is replayed serially in column-major order of the given axes.
826///
827/// # Errors
828///
829/// [`StridedError::ShapeMismatch`](crate::StridedError::ShapeMismatch) when the
830/// two views have different dims, and
831/// [`StridedError::OffsetOverflow`](crate::StridedError::OffsetOverflow) when the
832/// element count overflows `usize`; both before any write.
833///
834/// # Examples
835///
836/// Copy the outer band `1..3` of a stored `2 x 3` block into a transposed
837/// destination:
838///
839/// ```rust
840/// use strided_basic::{replay_copy_raw, Exec, RawStridedMut, RawStridedRef};
841///
842/// let stored = [0.0f64, 1.0, 2.0, 3.0, 4.0, 5.0]; // column-major 2 x 3
843/// let band = [2usize, 2];
844/// let src = RawStridedRef::new(&stored, &band, &[1, 2], 2).unwrap();
845/// let mut out = [0.0f64; 4];
846/// let mut dst = RawStridedMut::new(&mut out, &band, &[2, 1], 0).unwrap();
847/// replay_copy_raw(&mut dst, &src, Exec::serial()).unwrap();
848/// assert_eq!(out, [2.0, 4.0, 3.0, 5.0]);
849/// ```
850pub fn replay_copy_raw<T>(
851    dest: &mut RawStridedMut<'_, T>,
852    src: &RawStridedRef<'_, T>,
853    exec: Exec<'_>,
854) -> Result<()>
855where
856    T: Copy + Send + Sync,
857{
858    replay_given(dest, src, |dst: &mut T, value: T| *dst = value, exec)
859}
860
861/// [`replay_copy_raw`] into a potentially uninitialized destination.
862///
863/// On success every reachable destination element is initialized and no
864/// other slot is written. The destination is never read.
865///
866/// # Errors
867///
868/// As [`replay_copy_raw`].
869///
870/// # Examples
871///
872/// ```rust
873/// use core::mem::MaybeUninit;
874/// use strided_basic::{replay_copy_raw_uninit, Exec, RawStridedMut, RawStridedRef};
875///
876/// let src = [1.0f64, 2.0, 3.0];
877/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
878/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
879/// let source = RawStridedRef::new(&src, &[3], &[-1], 2).unwrap();
880/// replay_copy_raw_uninit(&mut dst, &source, Exec::serial()).unwrap();
881/// drop(dst);
882/// // SAFETY: every reachable destination slot was initialized above.
883/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
884/// assert_eq!(values, [3.0, 2.0, 1.0]);
885/// ```
886pub fn replay_copy_raw_uninit<T>(
887    dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
888    src: &RawStridedRef<'_, T>,
889    exec: Exec<'_>,
890) -> Result<()>
891where
892    T: Copy + Send + Sync,
893{
894    replay_given(
895        dest,
896        src,
897        |dst: &mut MaybeUninit<T>, value: T| {
898            dst.write(value);
899        },
900        exec,
901    )
902}
903
904/// `f(&mut dest[i], src[i])` for every element, replaying the axes of the two
905/// views exactly as given.
906///
907/// Traversal, width and errors are those of [`replay_copy_raw`], and so is the
908/// allocation guarantee, which covers the replay only: allocations made by `f`
909/// are its own. `f` runs once per logical element with exactly its arithmetic,
910/// so an accumulate such as `|d, s| *d += s` is exact. The order in which
911/// elements are visited is unspecified, and on a parallel replay `f` runs
912/// concurrently on disjoint slots: the result is defined only for an `f` whose
913/// effect depends on the supplied slot values alone. On a destination that is
914/// not proven injective, the elements are visited serially in column-major
915/// order of the given axes.
916///
917/// # Errors
918///
919/// As [`replay_copy_raw`].
920///
921/// # Examples
922///
923/// ```rust
924/// use strided_basic::{replay_map_raw, Exec, RawStridedMut, RawStridedRef};
925///
926/// let src = [1.0f64, 2.0, 3.0, 4.0];
927/// let mut acc = [10.0f64, 20.0, 30.0, 40.0];
928/// let source = RawStridedRef::new(&src, &[2, 2], &[2, 1], 0).unwrap();
929/// let mut dst = RawStridedMut::new(&mut acc, &[2, 2], &[1, 2], 0).unwrap();
930/// replay_map_raw(&mut dst, &source, |d, s| *d += s, Exec::serial()).unwrap();
931/// assert_eq!(acc, [11.0, 23.0, 32.0, 44.0]);
932/// ```
933pub fn replay_map_raw<D, S, F>(
934    dest: &mut RawStridedMut<'_, D>,
935    src: &RawStridedRef<'_, S>,
936    f: F,
937    exec: Exec<'_>,
938) -> Result<()>
939where
940    D: Copy + Send + Sync,
941    S: Copy + Send + Sync,
942    F: Fn(&mut D, S) + Send + Sync,
943{
944    replay_given(dest, src, f, exec)
945}
946
947/// `dest[i] = f(src[i])` into a potentially uninitialized destination.
948///
949/// `f` cannot read the destination. On success every reachable destination
950/// element is initialized and no other slot is written. The visit-order,
951/// callback and allocation contract is that of [`replay_map_raw`].
952///
953/// # Errors
954///
955/// As [`replay_copy_raw`].
956///
957/// # Examples
958///
959/// ```rust
960/// use core::mem::MaybeUninit;
961/// use strided_basic::{replay_map_raw_uninit, Exec, RawStridedMut, RawStridedRef};
962///
963/// let src = [1i32, 2, 3];
964/// let mut storage = [MaybeUninit::<f64>::uninit(); 3];
965/// let mut dst = RawStridedMut::new(&mut storage, &[3], &[1], 0).unwrap();
966/// let source = RawStridedRef::new(&src, &[3], &[1], 0).unwrap();
967/// replay_map_raw_uninit(&mut dst, &source, |s| f64::from(s) * 0.5, Exec::serial()).unwrap();
968/// drop(dst);
969/// // SAFETY: every reachable destination slot was initialized above.
970/// let values: Vec<f64> = storage.iter().map(|v| unsafe { v.assume_init() }).collect();
971/// assert_eq!(values, [0.5, 1.0, 1.5]);
972/// ```
973pub fn replay_map_raw_uninit<D, S, F>(
974    dest: &mut RawStridedMut<'_, MaybeUninit<D>>,
975    src: &RawStridedRef<'_, S>,
976    f: F,
977    exec: Exec<'_>,
978) -> Result<()>
979where
980    D: Copy + Send + Sync,
981    S: Copy + Send + Sync,
982    F: Fn(S) -> D + Send + Sync,
983{
984    replay_given(
985        dest,
986        src,
987        move |dst: &mut MaybeUninit<D>, value: S| {
988            dst.write(f(value));
989        },
990        exec,
991    )
992}
993
994#[cfg(test)]
995#[path = "raw_ops/tests/tests.rs"]
996mod tests;
997
998#[cfg(test)]
999#[path = "raw_ops/tests/replay_tests.rs"]
1000mod replay_tests;