1use core::mem::MaybeUninit;
9
10use crate::cost::KernelClass;
11use crate::{CopyPlan, Exec, RawStridedMut, RawStridedRef, Result, StridedError};
12
13type AxisVec<T> = crate::inline::InlineVec<T>;
14
15#[derive(Clone, Debug)]
20pub struct SlicePlan {
21 operand_dims: AxisVec<usize>,
22 operand_strides: AxisVec<isize>,
23 dest_dims: AxisVec<usize>,
24 dest_strides: AxisVec<isize>,
25 source_strides: AxisVec<isize>,
26 source_offset_delta: isize,
27 copy_plan: CopyPlan,
28}
29
30#[derive(Clone, Debug)]
34pub struct ReversePlan {
35 operand_dims: AxisVec<usize>,
36 operand_strides: AxisVec<isize>,
37 dest_strides: AxisVec<isize>,
38 source_strides: AxisVec<isize>,
39 source_offset_delta: isize,
40 copy_plan: CopyPlan,
41}
42
43#[derive(Clone, Debug)]
51pub struct PadPlan {
52 operand_dims: AxisVec<usize>,
53 operand_strides: AxisVec<isize>,
54 dest_dims: AxisVec<usize>,
55 dest_strides: AxisVec<isize>,
56 edge_padding_low: AxisVec<i64>,
57 interior_step: AxisVec<i64>,
58 operand_total: usize,
59 dest_total: usize,
60 contiguous_dest_fill: bool,
61 contiguous_axis0_run: Option<ContiguousPadAxis0Run>,
62 contiguous_axis0_columns: Option<ContiguousPadAxis0Columns>,
63 generic_fill: PadFillCursor,
64 generic_copy: PadCopyCursor,
65}
66
67#[derive(Clone, Debug)]
68struct PadFillCursor {
69 steps: AxisVec<isize>,
70 resets: AxisVec<isize>,
71}
72
73#[derive(Clone, Debug)]
74struct PadCopyCursor {
75 shape: AxisVec<usize>,
76 source_base_delta: isize,
77 dest_base_delta: isize,
78 source_steps: AxisVec<isize>,
79 source_resets: AxisVec<isize>,
80 dest_steps: AxisVec<isize>,
81 dest_resets: AxisVec<isize>,
82 total: usize,
83}
84
85#[derive(Clone, Copy, Debug, Eq, PartialEq)]
86struct ContiguousPadAxis0Run {
87 operand_start: usize,
88 dest_start: usize,
89 len: usize,
90}
91
92#[derive(Clone, Debug)]
102struct ContiguousPadAxis0Columns {
103 column_total: usize,
105 dest_axis0_len: usize,
106 dest_axis0_step: isize,
107 low0: usize,
108 high0: usize,
109 run_len: usize,
110 operand_outer_dims: AxisVec<usize>,
111 operand_outer_strides: AxisVec<isize>,
112 dest_outer_dims: AxisVec<usize>,
113 edge_low_outer: AxisVec<usize>,
114}
115
116#[derive(Clone, Debug)]
127pub struct ConcatenatePlan {
128 input_dims: crate::inline::OperandVec<AxisVec<usize>>,
129 input_strides: crate::inline::OperandVec<AxisVec<isize>>,
130 dest_dims: AxisVec<usize>,
131 dest_strides: AxisVec<isize>,
132 dest_offset_deltas: crate::inline::OperandVec<isize>,
133 segment_starts: crate::inline::OperandVec<usize>,
136 copy_plans: crate::inline::OperandVec<CopyPlan>,
137}
138
139impl SlicePlan {
140 #[allow(clippy::too_many_arguments)]
159 pub fn compile(
160 operand_dims: &[usize],
161 operand_strides: &[isize],
162 dest_dims: &[usize],
163 dest_strides: &[isize],
164 starts: &[usize],
165 limits: &[usize],
166 slice_strides: &[usize],
167 ) -> Result<Self> {
168 let rank = operand_dims.len();
169 if operand_strides.len() != rank || dest_dims.len() != rank || dest_strides.len() != rank {
170 return Err(StridedError::StrideLengthMismatch);
171 }
172 if starts.len() != rank {
173 return Err(StridedError::RankMismatch(starts.len(), rank));
174 }
175 if limits.len() != rank {
176 return Err(StridedError::RankMismatch(limits.len(), rank));
177 }
178 if slice_strides.len() != rank {
179 return Err(StridedError::RankMismatch(slice_strides.len(), rank));
180 }
181 checked_total_len(operand_dims)?;
182 checked_total_len(dest_dims)?;
183
184 let mut expected_dest_dims: AxisVec<usize> = AxisVec::with_capacity(rank);
185 let mut source_strides: AxisVec<isize> = AxisVec::with_capacity(rank);
186 let mut source_offset_delta = 0isize;
187 for axis in 0..rank {
188 let start = starts[axis];
189 let limit = limits[axis];
190 let stride = slice_strides[axis];
191 if start > limit || limit > operand_dims[axis] || stride == 0 {
192 return Err(StridedError::InvalidAxis { axis, rank });
193 }
194 let span = limit - start;
195 expected_dest_dims.push(span.div_ceil(stride));
196 source_strides.push(checked_stride_mul(operand_strides[axis], stride)?);
197 source_offset_delta =
198 checked_offset_add(source_offset_delta, operand_strides[axis], start)?;
199 }
200 if dest_dims != &expected_dest_dims[..] {
201 return Err(StridedError::ShapeMismatch(
202 dest_dims.to_vec(),
203 expected_dest_dims.to_vec(),
204 ));
205 }
206 let copy_plan = CopyPlan::compile(dest_dims, dest_strides, &source_strides)?;
207
208 Ok(Self {
209 operand_dims: operand_dims.into(),
210 operand_strides: operand_strides.into(),
211 dest_dims: dest_dims.into(),
212 dest_strides: dest_strides.into(),
213 source_strides,
214 source_offset_delta,
215 copy_plan,
216 })
217 }
218
219 pub fn execute<T>(
228 &self,
229 dest: &mut RawStridedMut<'_, T>,
230 operand: &RawStridedRef<'_, T>,
231 exec: Exec<'_>,
232 ) -> Result<()>
233 where
234 T: Copy + Send + Sync,
235 {
236 self.check_call(dest, operand)?;
237 let source_offset = operand
238 .offset()
239 .checked_add(self.source_offset_delta)
240 .ok_or(StridedError::OffsetOverflow)?;
241 let source = unsafe {
250 RawStridedRef::new_unchecked(
251 operand.data(),
252 &self.dest_dims,
253 &self.source_strides,
254 source_offset,
255 )
256 };
257 self.copy_plan.execute(dest, &source, exec)
258 }
259
260 pub fn execute_uninit<T>(
269 &self,
270 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
271 operand: &RawStridedRef<'_, T>,
272 exec: Exec<'_>,
273 ) -> Result<()>
274 where
275 T: Copy + Send + Sync,
276 {
277 self.check_call(dest, operand)?;
278 let source_offset = operand
279 .offset()
280 .checked_add(self.source_offset_delta)
281 .ok_or(StridedError::OffsetOverflow)?;
282 let source = unsafe {
291 RawStridedRef::new_unchecked(
292 operand.data(),
293 &self.dest_dims,
294 &self.source_strides,
295 source_offset,
296 )
297 };
298 self.copy_plan.execute_uninit(dest, &source, exec)
299 }
300
301 fn check_call<D, T>(
302 &self,
303 dest: &RawStridedMut<'_, D>,
304 operand: &RawStridedRef<'_, T>,
305 ) -> Result<()> {
306 if operand.dims() != &self.operand_dims[..]
307 || operand.strides() != &self.operand_strides[..]
308 || dest.dims() != &self.dest_dims[..]
309 || dest.strides() != &self.dest_strides[..]
310 {
311 return Err(StridedError::PlanLayoutMismatch);
312 }
313 Ok(())
314 }
315}
316
317impl PadPlan {
318 #[allow(clippy::too_many_arguments)]
337 pub fn compile(
338 operand_dims: &[usize],
339 operand_strides: &[isize],
340 dest_dims: &[usize],
341 dest_strides: &[isize],
342 edge_padding_low: &[i64],
343 edge_padding_high: &[i64],
344 interior_padding: &[i64],
345 ) -> Result<Self> {
346 let rank = operand_dims.len();
347 if operand_strides.len() != rank || dest_dims.len() != rank || dest_strides.len() != rank {
348 return Err(StridedError::StrideLengthMismatch);
349 }
350 if edge_padding_low.len() != rank {
351 return Err(StridedError::RankMismatch(edge_padding_low.len(), rank));
352 }
353 if edge_padding_high.len() != rank {
354 return Err(StridedError::RankMismatch(edge_padding_high.len(), rank));
355 }
356 if interior_padding.len() != rank {
357 return Err(StridedError::RankMismatch(interior_padding.len(), rank));
358 }
359
360 let operand_total = checked_total_len(operand_dims)?;
361 let dest_total = checked_total_len(dest_dims)?;
362 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
363 return Err(StridedError::NonInjectiveOutputLayout);
364 }
365
366 let mut expected_dest_dims: AxisVec<usize> = AxisVec::with_capacity(rank);
367 let mut interior_step: AxisVec<i64> = AxisVec::with_capacity(rank);
368 for axis in 0..rank {
369 if interior_padding[axis] < 0 {
370 return Err(StridedError::InvalidAxis { axis, rank });
371 }
372 let step = interior_padding[axis]
373 .checked_add(1)
374 .ok_or(StridedError::OffsetOverflow)?;
375 interior_step.push(step);
376 expected_dest_dims.push(checked_pad_output_dim(
377 operand_dims[axis],
378 edge_padding_low[axis],
379 edge_padding_high[axis],
380 step,
381 axis,
382 rank,
383 )?);
384 }
385 if dest_dims != &expected_dest_dims[..] {
386 return Err(StridedError::ShapeMismatch(
387 dest_dims.to_vec(),
388 expected_dest_dims.to_vec(),
389 ));
390 }
391 let contiguous_dest_fill = is_dense_col_major(dest_dims, dest_strides);
392 let contiguous_axis0_run = compile_contiguous_pad_axis0_run(
393 operand_dims,
394 operand_strides,
395 dest_dims,
396 dest_strides,
397 edge_padding_low,
398 &interior_step,
399 );
400 let contiguous_axis0_columns = contiguous_axis0_run.and_then(|run| {
401 compile_contiguous_pad_axis0_columns(
402 operand_dims,
403 operand_strides,
404 dest_dims,
405 edge_padding_low,
406 edge_padding_high,
407 &interior_step,
408 contiguous_dest_fill,
409 run,
410 )
411 });
412 let generic_fill = compile_pad_fill_cursor(dest_dims, dest_strides)?;
413 let generic_copy = compile_pad_copy_cursor(
414 operand_dims,
415 operand_strides,
416 dest_dims,
417 dest_strides,
418 edge_padding_low,
419 &interior_step,
420 )?;
421
422 Ok(Self {
423 operand_dims: operand_dims.into(),
424 operand_strides: operand_strides.into(),
425 dest_dims: dest_dims.into(),
426 dest_strides: dest_strides.into(),
427 edge_padding_low: edge_padding_low.into(),
428 interior_step,
429 operand_total,
430 dest_total,
431 contiguous_dest_fill,
432 contiguous_axis0_run,
433 contiguous_axis0_columns,
434 generic_fill,
435 generic_copy,
436 })
437 }
438
439 pub fn execute<T>(
448 &self,
449 dest: &mut RawStridedMut<'_, T>,
450 operand: &RawStridedRef<'_, T>,
451 fill: T,
452 exec: Exec<'_>,
453 ) -> Result<()>
454 where
455 T: Copy + Send + Sync,
456 {
457 let mut exec = exec;
458 self.check_call(dest, operand)?;
459 if self.operand_total == 0 {
460 return self.fill_dest(dest, fill, exec);
461 }
462 if let Some(columns) = &self.contiguous_axis0_columns {
463 return self.execute_axis0_columns(dest, operand, fill, columns, exec);
464 }
465 self.fill_dest(dest, fill, exec.reborrow())?;
466 if let Some(run) = self.contiguous_axis0_run {
467 return self.copy_operand_axis0_runs(dest, operand, run, exec);
468 }
469 self.copy_operand(dest, operand, exec)
470 }
471
472 pub fn execute_uninit<T>(
481 &self,
482 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
483 operand: &RawStridedRef<'_, T>,
484 fill: T,
485 exec: Exec<'_>,
486 ) -> Result<()>
487 where
488 T: Copy + Send + Sync,
489 {
490 let mut exec = exec;
491 self.check_call(dest, operand)?;
492 if self.operand_total == 0 {
493 return self.fill_dest(dest, MaybeUninit::new(fill), exec);
494 }
495 if let Some(columns) = &self.contiguous_axis0_columns {
496 return self.execute_axis0_columns_uninit(dest, operand, fill, columns, exec);
497 }
498 self.fill_dest(dest, MaybeUninit::new(fill), exec.reborrow())?;
499 if let Some(run) = self.contiguous_axis0_run {
500 return self.copy_operand_axis0_runs_uninit(dest, operand, run, exec);
501 }
502 self.copy_operand_uninit(dest, operand, exec)
503 }
504
505 fn fill_dest<T>(&self, dest: &mut RawStridedMut<'_, T>, fill: T, exec: Exec<'_>) -> Result<()>
506 where
507 T: Copy + Send + Sync,
508 {
509 if self.dest_total == 0 {
510 return Ok(());
511 }
512 if self.contiguous_dest_fill {
513 let dest_offset =
514 usize::try_from(dest.offset()).map_err(|_| StridedError::OffsetOverflow)?;
515 let dest_end = dest_offset
516 .checked_add(self.dest_total)
517 .ok_or(StridedError::OffsetOverflow)?;
518 let dest_data = dest.data_mut();
519 let dest_slice = dest_data
520 .get_mut(dest_offset..dest_end)
521 .ok_or(StridedError::OffsetOverflow)?;
522 crate::threading::fill_contiguous(dest_slice, fill, exec);
523 return Ok(());
524 }
525 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.dest_total);
526 if !exec.is_serial() {
527 return self.fill_dest_parallel(dest, fill, exec);
528 }
529 self.fill_dest_serial(dest, fill)
530 }
531
532 fn copy_operand_axis0_runs<T>(
533 &self,
534 dest: &mut RawStridedMut<'_, T>,
535 operand: &RawStridedRef<'_, T>,
536 run: ContiguousPadAxis0Run,
537 exec: Exec<'_>,
538 ) -> Result<()>
539 where
540 T: Copy + Send + Sync,
541 {
542 let dest_offset = dest.offset();
543 let dest_ptr = dest.data_mut().as_mut_ptr();
544 unsafe { self.copy_axis0_runs_raw(dest_ptr, dest_offset, operand, run, exec) }
548 }
549
550 fn copy_operand_axis0_runs_uninit<T>(
551 &self,
552 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
553 operand: &RawStridedRef<'_, T>,
554 run: ContiguousPadAxis0Run,
555 exec: Exec<'_>,
556 ) -> Result<()>
557 where
558 T: Copy + Send + Sync,
559 {
560 let dest_offset = dest.offset();
561 let dest_ptr = dest.data_mut().as_mut_ptr().cast::<T>();
562 unsafe { self.copy_axis0_runs_raw(dest_ptr, dest_offset, operand, run, exec) }
565 }
566
567 fn execute_axis0_columns<T>(
568 &self,
569 dest: &mut RawStridedMut<'_, T>,
570 operand: &RawStridedRef<'_, T>,
571 fill: T,
572 columns: &ContiguousPadAxis0Columns,
573 exec: Exec<'_>,
574 ) -> Result<()>
575 where
576 T: Copy + Send + Sync,
577 {
578 let dest_offset = dest.offset();
579 let dest_ptr = dest.data_mut().as_mut_ptr();
580 let operand_offset = operand.offset();
581 let operand_ptr = operand.data().as_ptr();
582 unsafe {
586 self.write_axis0_columns_raw::<T, false>(
587 dest_ptr,
588 dest_offset,
589 operand_ptr,
590 operand_offset,
591 fill,
592 columns,
593 exec,
594 )
595 }
596 }
597
598 fn execute_axis0_columns_uninit<T>(
599 &self,
600 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
601 operand: &RawStridedRef<'_, T>,
602 fill: T,
603 columns: &ContiguousPadAxis0Columns,
604 exec: Exec<'_>,
605 ) -> Result<()>
606 where
607 T: Copy + Send + Sync,
608 {
609 let dest_offset = dest.offset();
610 let dest_ptr = dest.data_mut().as_mut_ptr().cast::<T>();
611 let operand_offset = operand.offset();
612 let operand_ptr = operand.data().as_ptr();
613 unsafe {
616 self.write_axis0_columns_raw::<T, true>(
617 dest_ptr,
618 dest_offset,
619 operand_ptr,
620 operand_offset,
621 fill,
622 columns,
623 exec,
624 )
625 }
626 }
627
628 #[allow(clippy::too_many_arguments)]
646 unsafe fn write_axis0_columns_raw<T, const UNINIT: bool>(
647 &self,
648 dest_ptr: *mut T,
649 dest_offset: isize,
650 operand_ptr: *const T,
651 operand_offset: isize,
652 fill: T,
653 columns: &ContiguousPadAxis0Columns,
654 exec: Exec<'_>,
655 ) -> Result<()>
656 where
657 T: Copy + Send + Sync,
658 {
659 let column_total = columns.column_total;
660 if column_total == 0 {
661 return Ok(());
662 }
663 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.dest_total);
664 {
665 if exec.budget().get() > 1 && column_total >= exec.budget().get() {
666 let dest_ptr = crate::threading::SendPtr(dest_ptr);
667 let operand_ptr = crate::threading::SendPtr(operand_ptr as *mut T);
668 return crate::threading::parallel_map_reduce(
669 0..column_total,
670 exec,
671 &|range| {
672 let mut outer_idx_storage =
673 CoordScratch::new(columns.dest_outer_dims.len());
674 let outer_idx = outer_idx_storage.as_mut_slice();
675 fill_col_major_index(range.start, &columns.dest_outer_dims, outer_idx);
676 unsafe {
682 self.write_axis0_columns_range::<T, UNINIT>(
683 dest_ptr.as_ptr(),
684 dest_offset,
685 operand_ptr.as_const(),
686 operand_offset,
687 fill,
688 columns,
689 outer_idx,
690 range.start,
691 range.len(),
692 Exec::serial(),
693 )
694 }
695 },
696 &|left, right| left.and(right),
697 );
698 }
699 }
700 let mut outer_idx_storage = CoordScratch::new(columns.dest_outer_dims.len());
701 let outer_idx = outer_idx_storage.as_mut_slice();
702 unsafe {
704 self.write_axis0_columns_range::<T, UNINIT>(
705 dest_ptr,
706 dest_offset,
707 operand_ptr,
708 operand_offset,
709 fill,
710 columns,
711 outer_idx,
712 0,
713 column_total,
714 exec,
715 )
716 }
717 }
718
719 #[allow(clippy::too_many_arguments)]
727 unsafe fn write_axis0_columns_range<T, const UNINIT: bool>(
728 &self,
729 dest_ptr: *mut T,
730 dest_offset: isize,
731 operand_ptr: *const T,
732 operand_offset: isize,
733 fill: T,
734 columns: &ContiguousPadAxis0Columns,
735 outer_idx: &mut [usize],
736 column_start: usize,
737 count: usize,
738 mut exec: Exec<'_>,
739 ) -> Result<()>
740 where
741 T: Copy + Send + Sync,
742 {
743 if count == 0 {
744 return Ok(());
745 }
746 let mut dest_column_offset =
747 checked_offset_add(dest_offset, columns.dest_axis0_step, column_start)?;
748 let mut operand_column_offset = operand_offset;
753 let mut out_of_bounds = 0usize;
754 for (axis, &coord) in outer_idx.iter().enumerate() {
755 match in_bounds_outer_coord(columns, axis, coord) {
756 Some(q) => {
757 operand_column_offset = checked_offset_add(
758 operand_column_offset,
759 columns.operand_outer_strides[axis],
760 q,
761 )?;
762 }
763 None => out_of_bounds += 1,
764 }
765 }
766 for _ in 0..count {
767 if out_of_bounds == 0 {
768 let low_len = columns.low0;
769 let run_len = columns.run_len;
770 let high_len = columns.high0;
771 unsafe {
778 if UNINIT {
779 fill_raw_span_uninit(
780 dest_ptr.offset(dest_column_offset),
781 low_len,
782 fill,
783 exec.reborrow(),
784 );
785 } else {
786 fill_raw_span(
787 dest_ptr.offset(dest_column_offset),
788 low_len,
789 fill,
790 exec.reborrow(),
791 );
792 }
793 crate::threading::copy_contiguous(
794 operand_ptr.offset(operand_column_offset),
795 dest_ptr.offset(dest_column_offset + low_len as isize),
796 run_len,
797 exec.reborrow(),
798 );
799 if UNINIT {
800 fill_raw_span_uninit(
801 dest_ptr
802 .offset(dest_column_offset + low_len as isize + run_len as isize),
803 high_len,
804 fill,
805 exec.reborrow(),
806 );
807 } else {
808 fill_raw_span(
809 dest_ptr
810 .offset(dest_column_offset + low_len as isize + run_len as isize),
811 high_len,
812 fill,
813 exec.reborrow(),
814 );
815 }
816 }
817 } else {
818 unsafe {
821 if UNINIT {
822 fill_raw_span_uninit(
823 dest_ptr.offset(dest_column_offset),
824 columns.dest_axis0_len,
825 fill,
826 exec.reborrow(),
827 );
828 } else {
829 fill_raw_span(
830 dest_ptr.offset(dest_column_offset),
831 columns.dest_axis0_len,
832 fill,
833 exec.reborrow(),
834 );
835 }
836 }
837 }
838 dest_column_offset = dest_column_offset
841 .checked_add(columns.dest_axis0_step)
842 .ok_or(StridedError::OffsetOverflow)?;
843 for (axis, coord) in outer_idx.iter_mut().enumerate() {
844 let was_in_bounds = in_bounds_outer_coord(columns, axis, *coord);
845 if let Some(q) = was_in_bounds {
846 let q = isize::try_from(q).map_err(|_| StridedError::OffsetOverflow)?;
847 let scaled = columns.operand_outer_strides[axis]
848 .checked_mul(q)
849 .ok_or(StridedError::OffsetOverflow)?;
850 operand_column_offset = operand_column_offset
851 .checked_sub(scaled)
852 .ok_or(StridedError::OffsetOverflow)?;
853 }
854 *coord += 1;
855 let wrapped = *coord >= columns.dest_outer_dims[axis];
856 if wrapped {
857 *coord = 0;
858 }
859 let is_in_bounds = in_bounds_outer_coord(columns, axis, *coord);
860 if let Some(q) = is_in_bounds {
861 operand_column_offset = checked_offset_add(
862 operand_column_offset,
863 columns.operand_outer_strides[axis],
864 q,
865 )?;
866 }
867 match (was_in_bounds.is_some(), is_in_bounds.is_some()) {
868 (false, true) => out_of_bounds -= 1,
869 (true, false) => out_of_bounds += 1,
870 _ => {}
871 }
872 if !wrapped {
873 break;
874 }
875 }
876 }
877 Ok(())
878 }
879
880 unsafe fn copy_axis0_runs_raw<T>(
893 &self,
894 dest_ptr: *mut T,
895 dest_offset: isize,
896 operand: &RawStridedRef<'_, T>,
897 run: ContiguousPadAxis0Run,
898 exec: Exec<'_>,
899 ) -> Result<()>
900 where
901 T: Copy + Send + Sync,
902 {
903 if run.len == 0 {
904 return Ok(());
905 }
906 let outer_dims = &self.operand_dims[1..];
907 let outer_total = checked_total_len(outer_dims)?;
908 let copied = outer_total.saturating_mul(run.len);
909 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, copied);
910 {
911 if exec.budget().get() > 1 && outer_total >= exec.budget().get() {
912 let dest_ptr = crate::threading::SendPtr(dest_ptr);
913 return crate::threading::parallel_map_reduce(
914 0..outer_total,
915 exec,
916 &|range| {
917 let mut outer_idx_storage = CoordScratch::new(outer_dims.len());
918 let outer_idx = outer_idx_storage.as_mut_slice();
919 fill_col_major_index(range.start, outer_dims, outer_idx);
920 unsafe {
924 self.copy_axis0_run_range(
925 dest_ptr.as_ptr(),
926 dest_offset,
927 operand,
928 run,
929 outer_idx,
930 range.len(),
931 Exec::serial(),
932 )
933 }
934 },
935 &|left, right| left.and(right),
936 );
937 }
938 }
939 let mut outer_idx_storage = CoordScratch::new(outer_dims.len());
940 let outer_idx = outer_idx_storage.as_mut_slice();
941 unsafe {
943 self.copy_axis0_run_range(
944 dest_ptr,
945 dest_offset,
946 operand,
947 run,
948 outer_idx,
949 outer_total,
950 exec,
951 )
952 }
953 }
954
955 #[allow(clippy::too_many_arguments)]
963 unsafe fn copy_axis0_run_range<T>(
964 &self,
965 dest_ptr: *mut T,
966 dest_offset: isize,
967 operand: &RawStridedRef<'_, T>,
968 run: ContiguousPadAxis0Run,
969 outer_idx: &mut [usize],
970 count: usize,
971 mut exec: Exec<'_>,
972 ) -> Result<()>
973 where
974 T: Copy + Send + Sync,
975 {
976 let outer_dims = &self.operand_dims[1..];
977 let operand_ptr = operand.data().as_ptr();
978 for _ in 0..count {
979 let mut operand_offset =
980 checked_offset_add(operand.offset(), self.operand_strides[0], run.operand_start)?;
981 let mut dest_run_offset =
982 checked_offset_add(dest_offset, self.dest_strides[0], run.dest_start)?;
983 let mut in_bounds = true;
984 for (outer_axis, &coord) in outer_idx.iter().enumerate() {
985 let axis = outer_axis + 1;
986 let out_pos = i128::from(self.edge_padding_low[axis])
987 + coord as i128 * i128::from(self.interior_step[axis]);
988 if out_pos < 0 || out_pos >= self.dest_dims[axis] as i128 {
989 in_bounds = false;
990 break;
991 }
992 operand_offset =
993 checked_offset_add(operand_offset, self.operand_strides[axis], coord)?;
994 dest_run_offset =
995 checked_offset_add(dest_run_offset, self.dest_strides[axis], out_pos as usize)?;
996 }
997 if in_bounds {
998 unsafe {
1004 crate::threading::copy_contiguous(
1005 operand_ptr.offset(operand_offset),
1006 dest_ptr.offset(dest_run_offset),
1007 run.len,
1008 exec.reborrow(),
1009 );
1010 }
1011 }
1012 advance_col_major_index(outer_idx, outer_dims);
1013 }
1014 Ok(())
1015 }
1016
1017 #[cfg(test)]
1018 fn contiguous_axis0_run(&self) -> Option<(usize, usize, usize)> {
1019 self.contiguous_axis0_run
1020 .map(|run| (run.operand_start, run.dest_start, run.len))
1021 }
1022
1023 #[cfg(test)]
1024 fn has_contiguous_dest_fill(&self) -> bool {
1025 self.contiguous_dest_fill
1026 }
1027
1028 #[cfg(test)]
1029 fn has_contiguous_axis0_columns(&self) -> bool {
1030 self.contiguous_axis0_columns.is_some()
1031 }
1032
1033 fn fill_dest_serial<T>(&self, dest: &mut RawStridedMut<'_, T>, fill: T) -> Result<()>
1034 where
1035 T: Copy,
1036 {
1037 let dest_ptr = dest.data_mut().as_mut_ptr();
1038 let mut cursor = PadFillState::new(dest.offset(), &self.dest_dims, &self.generic_fill);
1039 for _ in 0..self.dest_total {
1040 unsafe {
1041 *dest_ptr.offset(cursor.offset) = fill;
1045 }
1046 cursor.advance(&self.dest_dims, &self.generic_fill);
1047 }
1048 Ok(())
1049 }
1050
1051 fn fill_dest_parallel<T>(
1052 &self,
1053 dest: &mut RawStridedMut<'_, T>,
1054 fill: T,
1055 exec: Exec<'_>,
1056 ) -> Result<()>
1057 where
1058 T: Copy + Send + Sync,
1059 {
1060 let dest_offset_base = dest.offset();
1061 let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1062 crate::threading::parallel_map_reduce(
1063 0..self.dest_total,
1064 exec,
1065 &|range| {
1066 let mut cursor = PadFillState::decode(
1067 range.start,
1068 dest_offset_base,
1069 &self.dest_dims,
1070 &self.generic_fill,
1071 )?;
1072 let dest_ptr = dest_ptr.as_ptr();
1073 for _ in range {
1074 unsafe {
1075 *dest_ptr.offset(cursor.offset) = fill;
1080 }
1081 cursor.advance(&self.dest_dims, &self.generic_fill);
1082 }
1083 Ok(())
1084 },
1085 &|left, right| left.and(right),
1086 )
1087 }
1088
1089 fn copy_operand<T>(
1090 &self,
1091 dest: &mut RawStridedMut<'_, T>,
1092 operand: &RawStridedRef<'_, T>,
1093 exec: Exec<'_>,
1094 ) -> Result<()>
1095 where
1096 T: Copy + Send + Sync,
1097 {
1098 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.generic_copy.total);
1099 if !exec.is_serial() {
1100 return self.copy_operand_parallel(dest, operand, exec);
1101 }
1102 self.copy_operand_serial(dest, operand)
1103 }
1104
1105 fn copy_operand_uninit<T>(
1106 &self,
1107 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1108 operand: &RawStridedRef<'_, T>,
1109 exec: Exec<'_>,
1110 ) -> Result<()>
1111 where
1112 T: Copy + Send + Sync,
1113 {
1114 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.generic_copy.total);
1115 if !exec.is_serial() {
1116 return self.copy_operand_uninit_parallel(dest, operand, exec);
1117 }
1118 self.copy_operand_uninit_serial(dest, operand)
1119 }
1120
1121 fn copy_operand_uninit_serial<T>(
1122 &self,
1123 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1124 operand: &RawStridedRef<'_, T>,
1125 ) -> Result<()>
1126 where
1127 T: Copy,
1128 {
1129 if self.generic_copy.total == 0 {
1130 return Ok(());
1131 }
1132 let operand_ptr = operand.data().as_ptr();
1133 let dest_ptr = dest.data_mut().as_mut_ptr();
1134 let source_base = operand
1135 .offset()
1136 .checked_add(self.generic_copy.source_base_delta)
1137 .ok_or(StridedError::OffsetOverflow)?;
1138 let dest_base = dest
1139 .offset()
1140 .checked_add(self.generic_copy.dest_base_delta)
1141 .ok_or(StridedError::OffsetOverflow)?;
1142 let mut cursor = PadCopyState::new(source_base, dest_base, &self.generic_copy);
1143 for _ in 0..self.generic_copy.total {
1144 unsafe {
1154 (*dest_ptr.offset(cursor.dest_offset))
1159 .write(*operand_ptr.offset(cursor.source_offset));
1160 }
1161 cursor.advance(&self.generic_copy);
1162 }
1163 Ok(())
1164 }
1165
1166 fn copy_operand_uninit_parallel<T>(
1167 &self,
1168 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1169 operand: &RawStridedRef<'_, T>,
1170 exec: Exec<'_>,
1171 ) -> Result<()>
1172 where
1173 T: Copy + Send + Sync,
1174 {
1175 let operand_base = operand
1176 .offset()
1177 .checked_add(self.generic_copy.source_base_delta)
1178 .ok_or(StridedError::OffsetOverflow)?;
1179 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1180 let dest_base = dest
1181 .offset()
1182 .checked_add(self.generic_copy.dest_base_delta)
1183 .ok_or(StridedError::OffsetOverflow)?;
1184 let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1185 crate::threading::parallel_map_reduce(
1186 0..self.generic_copy.total,
1187 exec,
1188 &|range| {
1189 let mut cursor =
1190 PadCopyState::decode(range.start, operand_base, dest_base, &self.generic_copy)?;
1191 let operand_ptr = operand_ptr.as_const();
1192 let dest_ptr = dest_ptr.as_ptr();
1193
1194 for _ in range {
1195 unsafe {
1205 (*dest_ptr.offset(cursor.dest_offset))
1210 .write(*operand_ptr.offset(cursor.source_offset));
1211 }
1212 cursor.advance(&self.generic_copy);
1213 }
1214 Ok(())
1215 },
1216 &|left, right| left.and(right),
1217 )
1218 }
1219
1220 fn copy_operand_serial<T>(
1221 &self,
1222 dest: &mut RawStridedMut<'_, T>,
1223 operand: &RawStridedRef<'_, T>,
1224 ) -> Result<()>
1225 where
1226 T: Copy,
1227 {
1228 if self.generic_copy.total == 0 {
1229 return Ok(());
1230 }
1231 let operand_ptr = operand.data().as_ptr();
1232 let dest_ptr = dest.data_mut().as_mut_ptr();
1233 let source_base = operand
1234 .offset()
1235 .checked_add(self.generic_copy.source_base_delta)
1236 .ok_or(StridedError::OffsetOverflow)?;
1237 let dest_base = dest
1238 .offset()
1239 .checked_add(self.generic_copy.dest_base_delta)
1240 .ok_or(StridedError::OffsetOverflow)?;
1241 let mut cursor = PadCopyState::new(source_base, dest_base, &self.generic_copy);
1242 for _ in 0..self.generic_copy.total {
1243 unsafe {
1244 *dest_ptr.offset(cursor.dest_offset) = *operand_ptr.offset(cursor.source_offset);
1249 }
1250 cursor.advance(&self.generic_copy);
1251 }
1252 Ok(())
1253 }
1254
1255 fn copy_operand_parallel<T>(
1256 &self,
1257 dest: &mut RawStridedMut<'_, T>,
1258 operand: &RawStridedRef<'_, T>,
1259 exec: Exec<'_>,
1260 ) -> Result<()>
1261 where
1262 T: Copy + Send + Sync,
1263 {
1264 let operand_base = operand
1265 .offset()
1266 .checked_add(self.generic_copy.source_base_delta)
1267 .ok_or(StridedError::OffsetOverflow)?;
1268 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1269 let dest_base = dest
1270 .offset()
1271 .checked_add(self.generic_copy.dest_base_delta)
1272 .ok_or(StridedError::OffsetOverflow)?;
1273 let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1274 crate::threading::parallel_map_reduce(
1275 0..self.generic_copy.total,
1276 exec,
1277 &|range| {
1278 let mut cursor =
1279 PadCopyState::decode(range.start, operand_base, dest_base, &self.generic_copy)?;
1280 let operand_ptr = operand_ptr.as_const();
1281 let dest_ptr = dest_ptr.as_ptr();
1282
1283 for _ in range {
1284 unsafe {
1285 *dest_ptr.offset(cursor.dest_offset) =
1290 *operand_ptr.offset(cursor.source_offset);
1291 }
1292 cursor.advance(&self.generic_copy);
1293 }
1294 Ok(())
1295 },
1296 &|left, right| left.and(right),
1297 )
1298 }
1299
1300 fn check_call<D, T>(
1301 &self,
1302 dest: &RawStridedMut<'_, D>,
1303 operand: &RawStridedRef<'_, T>,
1304 ) -> Result<()> {
1305 if operand.dims() != &self.operand_dims[..]
1306 || operand.strides() != &self.operand_strides[..]
1307 || dest.dims() != &self.dest_dims[..]
1308 || dest.strides() != &self.dest_strides[..]
1309 {
1310 return Err(StridedError::PlanLayoutMismatch);
1311 }
1312 Ok(())
1313 }
1314}
1315
1316impl ConcatenatePlan {
1317 pub fn compile(
1335 input_dims: &[&[usize]],
1336 input_strides: &[&[isize]],
1337 dest_dims: &[usize],
1338 dest_strides: &[isize],
1339 axis: usize,
1340 ) -> Result<Self> {
1341 if input_dims.is_empty() {
1342 return Err(StridedError::UnsupportedArity {
1343 arity: 0,
1344 max: usize::MAX,
1345 });
1346 }
1347 if input_dims.len() != input_strides.len() {
1348 return Err(StridedError::RankMismatch(
1349 input_strides.len(),
1350 input_dims.len(),
1351 ));
1352 }
1353
1354 let rank = input_dims[0].len();
1355 if dest_dims.len() != rank || dest_strides.len() != rank {
1356 return Err(StridedError::StrideLengthMismatch);
1357 }
1358 if axis >= rank {
1359 return Err(StridedError::InvalidAxis { axis, rank });
1360 }
1361 checked_total_len(dest_dims)?;
1362 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1363 return Err(StridedError::NonInjectiveOutputLayout);
1364 }
1365
1366 let mut expected_dest_dims: AxisVec<usize> = input_dims[0].into();
1367 expected_dest_dims[axis] = 0;
1368 let mut stored_input_dims = crate::inline::OperandVec::with_capacity(input_dims.len());
1369 let mut stored_input_strides = crate::inline::OperandVec::with_capacity(input_dims.len());
1370 let mut dest_offset_deltas = crate::inline::OperandVec::with_capacity(input_dims.len());
1371 let mut copy_plans = crate::inline::OperandVec::with_capacity(input_dims.len());
1372 let mut segment_starts = crate::inline::OperandVec::with_capacity(input_dims.len() + 1);
1373 segment_starts.push(0usize);
1374 let mut axis_base = 0usize;
1375
1376 for (dims, strides) in input_dims.iter().zip(input_strides.iter()) {
1377 if dims.len() != rank {
1378 return Err(StridedError::RankMismatch(dims.len(), rank));
1379 }
1380 if strides.len() != rank {
1381 return Err(StridedError::StrideLengthMismatch);
1382 }
1383 let segment_total = checked_total_len(dims)?;
1384 let segment_end = segment_starts[segment_starts.len() - 1]
1385 .checked_add(segment_total)
1386 .ok_or(StridedError::OffsetOverflow)?;
1387 segment_starts.push(segment_end);
1388 for dim in 0..rank {
1389 if dim == axis {
1390 expected_dest_dims[axis] = expected_dest_dims[axis]
1391 .checked_add(dims[axis])
1392 .ok_or(StridedError::OffsetOverflow)?;
1393 } else if dims[dim] != input_dims[0][dim] {
1394 return Err(StridedError::ShapeMismatch(
1395 dims.to_vec(),
1396 input_dims[0].to_vec(),
1397 ));
1398 }
1399 }
1400 dest_offset_deltas.push(checked_offset_add(0, dest_strides[axis], axis_base)?);
1401 axis_base = axis_base
1402 .checked_add(dims[axis])
1403 .ok_or(StridedError::OffsetOverflow)?;
1404 copy_plans.push(CopyPlan::compile(dims, dest_strides, strides)?);
1405 stored_input_dims.push((*dims).into());
1406 stored_input_strides.push((*strides).into());
1407 }
1408
1409 if dest_dims != &expected_dest_dims[..] {
1410 return Err(StridedError::ShapeMismatch(
1411 dest_dims.to_vec(),
1412 expected_dest_dims.to_vec(),
1413 ));
1414 }
1415
1416 Ok(Self {
1417 input_dims: stored_input_dims,
1418 input_strides: stored_input_strides,
1419 dest_dims: dest_dims.into(),
1420 dest_strides: dest_strides.into(),
1421 dest_offset_deltas,
1422 segment_starts,
1423 copy_plans,
1424 })
1425 }
1426
1427 pub fn execute<T>(
1437 &self,
1438 dest: &mut RawStridedMut<'_, T>,
1439 inputs: &[RawStridedRef<'_, T>],
1440 exec: Exec<'_>,
1441 ) -> Result<()>
1442 where
1443 T: Copy + Send + Sync,
1444 {
1445 let mut exec = exec;
1446 self.check_dest_layout(dest)?;
1447 if inputs.len() != self.input_dims.len() {
1448 return Err(StridedError::RankMismatch(
1449 inputs.len(),
1450 self.input_dims.len(),
1451 ));
1452 }
1453 for (position, input) in inputs.iter().enumerate() {
1454 self.check_input_layout(position, input)?;
1455 self.segment_offset(position, dest.offset())?;
1456 }
1457 if self.try_execute_parallel(
1458 dest,
1459 inputs,
1460 |dst: &mut T, value| *dst = value,
1461 exec.reborrow(),
1462 )? {
1463 return Ok(());
1464 }
1465 for (position, input) in inputs.iter().enumerate() {
1466 self.execute_segment(position, dest, input, exec.reborrow())?;
1467 }
1468 Ok(())
1469 }
1470
1471 pub fn execute_uninit<T>(
1481 &self,
1482 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1483 inputs: &[RawStridedRef<'_, T>],
1484 exec: Exec<'_>,
1485 ) -> Result<()>
1486 where
1487 T: Copy + Send + Sync,
1488 {
1489 let mut exec = exec;
1490 self.check_dest_layout(dest)?;
1491 if inputs.len() != self.input_dims.len() {
1492 return Err(StridedError::RankMismatch(
1493 inputs.len(),
1494 self.input_dims.len(),
1495 ));
1496 }
1497 for (position, input) in inputs.iter().enumerate() {
1498 self.check_input_layout(position, input)?;
1499 self.segment_offset(position, dest.offset())?;
1500 }
1501 if self.try_execute_parallel(
1502 dest,
1503 inputs,
1504 |dst: &mut MaybeUninit<T>, value| {
1505 dst.write(value);
1506 },
1507 exec.reborrow(),
1508 )? {
1509 return Ok(());
1510 }
1511 for (position, input) in inputs.iter().enumerate() {
1512 self.execute_segment_uninit(position, dest, input, exec.reborrow())?;
1513 }
1514 Ok(())
1515 }
1516
1517 fn try_execute_parallel<D, T, Apply>(
1528 &self,
1529 dest: &mut RawStridedMut<'_, D>,
1530 inputs: &[RawStridedRef<'_, T>],
1531 apply: Apply,
1532 exec: Exec<'_>,
1533 ) -> Result<bool>
1534 where
1535 D: Copy + Send + Sync,
1536 T: Copy + Send + Sync,
1537 Apply: Fn(&mut D, T) + Send + Sync,
1538 {
1539 let total = self.segment_starts[self.segment_starts.len() - 1];
1540 let exec = crate::cost::for_len(exec, KernelClass::Copy, total);
1541 if exec.is_serial() {
1542 return Ok(false);
1543 }
1544 let mut dest_offsets: crate::inline::OperandVec<isize> =
1549 crate::inline::OperandVec::with_capacity(inputs.len());
1550 for position in 0..inputs.len() {
1551 if self.copy_plans[position].fused_layout().is_none() {
1552 return Ok(false);
1553 }
1554 dest_offsets.push(self.segment_offset(position, dest.offset())?);
1555 }
1556 let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1557 let starts = &self.segment_starts;
1558 let dest_offsets = &dest_offsets;
1559 crate::threading::parallel_for_each(0..total, exec, &|range| {
1560 let mut position = starts[1..].partition_point(|&end| end <= range.start);
1562 while position < inputs.len() && starts[position] < range.end {
1563 let local_start = range.start.max(starts[position]) - starts[position];
1564 let local_end = range.end.min(starts[position + 1]) - starts[position];
1565 let Some(layout) = self.copy_plans[position].fused_layout() else {
1569 position += 1;
1570 continue;
1571 };
1572 let input = &inputs[position];
1573 unsafe {
1583 crate::raw_ops::apply_fused_range(
1584 dest_ptr.as_ptr(),
1585 dest_offsets[position],
1586 input.data().as_ptr(),
1587 input.offset(),
1588 layout,
1589 local_start,
1590 local_end - local_start,
1591 &apply,
1592 );
1593 }
1594 position += 1;
1595 }
1596 });
1597 Ok(true)
1598 }
1599
1600 pub(crate) fn check_dest_layout<T>(&self, dest: &RawStridedMut<'_, T>) -> Result<()> {
1601 if dest.dims() != &self.dest_dims[..] || dest.strides() != &self.dest_strides[..] {
1602 return Err(StridedError::PlanLayoutMismatch);
1603 }
1604 Ok(())
1605 }
1606
1607 pub(crate) fn check_input_layout<T>(
1608 &self,
1609 position: usize,
1610 input: &RawStridedRef<'_, T>,
1611 ) -> Result<()> {
1612 if position >= self.input_dims.len()
1613 || input.dims() != &self.input_dims[position][..]
1614 || input.strides() != &self.input_strides[position][..]
1615 {
1616 return Err(StridedError::PlanLayoutMismatch);
1617 }
1618 Ok(())
1619 }
1620
1621 pub(crate) fn input_count(&self) -> usize {
1622 self.input_dims.len()
1623 }
1624
1625 pub(crate) fn prefers_whole_plan(&self, exec: &Exec<'_>) -> bool {
1629 let total = self.segment_starts[self.segment_starts.len() - 1];
1630 crate::threading::is_parallel(KernelClass::Copy, total, exec)
1631 }
1632
1633 pub(crate) fn segment_offset(&self, position: usize, dest_offset: isize) -> Result<isize> {
1634 dest_offset
1635 .checked_add(self.dest_offset_deltas[position])
1636 .ok_or(StridedError::OffsetOverflow)
1637 }
1638
1639 pub(crate) fn execute_segment<T>(
1640 &self,
1641 position: usize,
1642 dest: &mut RawStridedMut<'_, T>,
1643 input: &RawStridedRef<'_, T>,
1644 exec: Exec<'_>,
1645 ) -> Result<()>
1646 where
1647 T: Copy + Send + Sync,
1648 {
1649 let segment_offset = self.segment_offset(position, dest.offset())?;
1650 let dest_data = dest.data_mut();
1651 let mut segment = unsafe {
1652 RawStridedMut::new_unchecked(
1653 dest_data,
1654 &self.input_dims[position],
1655 &self.dest_strides,
1656 segment_offset,
1657 )
1658 };
1659 self.copy_plans[position].execute(&mut segment, input, exec)
1660 }
1661
1662 pub(crate) fn execute_segment_uninit<T>(
1663 &self,
1664 position: usize,
1665 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1666 input: &RawStridedRef<'_, T>,
1667 exec: Exec<'_>,
1668 ) -> Result<()>
1669 where
1670 T: Copy + Send + Sync,
1671 {
1672 let segment_offset = self.segment_offset(position, dest.offset())?;
1673 let dest_data = dest.data_mut();
1674 let mut segment = unsafe {
1675 RawStridedMut::new_unchecked(
1676 dest_data,
1677 &self.input_dims[position],
1678 &self.dest_strides,
1679 segment_offset,
1680 )
1681 };
1682 self.copy_plans[position].execute_uninit(&mut segment, input, exec)
1683 }
1684}
1685
1686impl ReversePlan {
1687 pub fn compile(
1700 operand_dims: &[usize],
1701 operand_strides: &[isize],
1702 dest_strides: &[isize],
1703 axes: &[usize],
1704 ) -> Result<Self> {
1705 let rank = operand_dims.len();
1706 if operand_strides.len() != rank || dest_strides.len() != rank {
1707 return Err(StridedError::StrideLengthMismatch);
1708 }
1709 checked_total_len(operand_dims)?;
1710
1711 let mut reverse_axis: AxisVec<bool> = (0..rank).map(|_| false).collect();
1712 for &axis in axes {
1713 if axis >= rank {
1714 return Err(StridedError::InvalidAxis { axis, rank });
1715 }
1716 reverse_axis[axis] = true;
1717 }
1718
1719 let mut source_strides: AxisVec<isize> = AxisVec::with_capacity(rank);
1720 let mut source_offset_delta = 0isize;
1721 for axis in 0..rank {
1722 if reverse_axis[axis] {
1723 source_strides.push(
1724 operand_strides[axis]
1725 .checked_neg()
1726 .ok_or(StridedError::OffsetOverflow)?,
1727 );
1728 if operand_dims[axis] > 0 {
1729 source_offset_delta = checked_offset_add(
1730 source_offset_delta,
1731 operand_strides[axis],
1732 operand_dims[axis] - 1,
1733 )?;
1734 }
1735 } else {
1736 source_strides.push(operand_strides[axis]);
1737 }
1738 }
1739 let copy_plan = CopyPlan::compile(operand_dims, dest_strides, &source_strides)?;
1740
1741 Ok(Self {
1742 operand_dims: operand_dims.into(),
1743 operand_strides: operand_strides.into(),
1744 dest_strides: dest_strides.into(),
1745 source_strides,
1746 source_offset_delta,
1747 copy_plan,
1748 })
1749 }
1750
1751 pub fn execute<T>(
1760 &self,
1761 dest: &mut RawStridedMut<'_, T>,
1762 operand: &RawStridedRef<'_, T>,
1763 exec: Exec<'_>,
1764 ) -> Result<()>
1765 where
1766 T: Copy + Send + Sync,
1767 {
1768 self.check_call(dest, operand)?;
1769 let source_offset = operand
1770 .offset()
1771 .checked_add(self.source_offset_delta)
1772 .ok_or(StridedError::OffsetOverflow)?;
1773 let source = unsafe {
1774 RawStridedRef::new_unchecked(
1775 operand.data(),
1776 &self.operand_dims,
1777 &self.source_strides,
1778 source_offset,
1779 )
1780 };
1781 self.copy_plan.execute(dest, &source, exec)
1782 }
1783
1784 pub fn execute_uninit<T>(
1793 &self,
1794 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1795 operand: &RawStridedRef<'_, T>,
1796 exec: Exec<'_>,
1797 ) -> Result<()>
1798 where
1799 T: Copy + Send + Sync,
1800 {
1801 self.check_call(dest, operand)?;
1802 let source_offset = operand
1803 .offset()
1804 .checked_add(self.source_offset_delta)
1805 .ok_or(StridedError::OffsetOverflow)?;
1806 let source = unsafe {
1807 RawStridedRef::new_unchecked(
1808 operand.data(),
1809 &self.operand_dims,
1810 &self.source_strides,
1811 source_offset,
1812 )
1813 };
1814 self.copy_plan.execute_uninit(dest, &source, exec)
1815 }
1816
1817 fn check_call<D, T>(
1818 &self,
1819 dest: &RawStridedMut<'_, D>,
1820 operand: &RawStridedRef<'_, T>,
1821 ) -> Result<()> {
1822 if operand.dims() != &self.operand_dims[..]
1823 || operand.strides() != &self.operand_strides[..]
1824 || dest.dims() != &self.operand_dims[..]
1825 || dest.strides() != &self.dest_strides[..]
1826 {
1827 return Err(StridedError::PlanLayoutMismatch);
1828 }
1829 Ok(())
1830 }
1831}
1832
1833fn checked_total_len(dims: &[usize]) -> Result<usize> {
1834 if dims.is_empty() {
1835 return Ok(1);
1836 }
1837 dims.iter()
1838 .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
1839 .ok_or(StridedError::OffsetOverflow)
1840}
1841
1842fn checked_stride_mul(stride: isize, factor: usize) -> Result<isize> {
1843 let factor = isize::try_from(factor).map_err(|_| StridedError::OffsetOverflow)?;
1844 stride
1845 .checked_mul(factor)
1846 .ok_or(StridedError::OffsetOverflow)
1847}
1848
1849fn checked_pad_output_dim(
1850 input_extent: usize,
1851 edge_low: i64,
1852 edge_high: i64,
1853 interior_step: i64,
1854 axis: usize,
1855 rank: usize,
1856) -> Result<usize> {
1857 let base = if input_extent == 0 {
1858 0i128
1859 } else {
1860 (input_extent as i128 - 1)
1861 .checked_mul(i128::from(interior_step))
1862 .and_then(|value| value.checked_add(1))
1863 .ok_or(StridedError::OffsetOverflow)?
1864 };
1865 let dim = i128::from(edge_low)
1866 .checked_add(i128::from(edge_high))
1867 .and_then(|value| value.checked_add(base))
1868 .ok_or(StridedError::OffsetOverflow)?;
1869 usize::try_from(dim).map_err(|_| StridedError::InvalidAxis { axis, rank })
1870}
1871
1872fn compile_pad_fill_cursor(dims: &[usize], strides: &[isize]) -> Result<PadFillCursor> {
1873 let mut steps = AxisVec::with_capacity(dims.len());
1874 let mut resets = AxisVec::with_capacity(dims.len());
1875 for (&dim, &stride) in dims.iter().zip(strides) {
1876 steps.push(stride);
1877 resets.push(checked_cursor_reset(stride, dim)?);
1878 }
1879 check_offset_span(dims, &steps)?;
1880 Ok(PadFillCursor { steps, resets })
1881}
1882
1883fn compile_pad_copy_cursor(
1884 operand_dims: &[usize],
1885 operand_strides: &[isize],
1886 dest_dims: &[usize],
1887 dest_strides: &[isize],
1888 edge_padding_low: &[i64],
1889 interior_step: &[i64],
1890) -> Result<PadCopyCursor> {
1891 let mut shape = AxisVec::with_capacity(operand_dims.len());
1892 let mut source_steps = AxisVec::with_capacity(operand_dims.len());
1893 let mut source_resets = AxisVec::with_capacity(operand_dims.len());
1894 let mut dest_steps = AxisVec::with_capacity(operand_dims.len());
1895 let mut dest_resets = AxisVec::with_capacity(operand_dims.len());
1896 let mut source_base_delta = 0isize;
1897 let mut dest_base_delta = 0isize;
1898 let mut copy_empty = false;
1899
1900 for axis in 0..operand_dims.len() {
1901 let (start, end) = checked_pad_valid_interval(
1902 operand_dims[axis],
1903 dest_dims[axis],
1904 edge_padding_low[axis],
1905 interior_step[axis],
1906 )?;
1907 let extent = end - start;
1908 shape.push(extent);
1909 if !copy_empty && extent != 0 {
1910 source_base_delta =
1911 checked_offset_add(source_base_delta, operand_strides[axis], start)?;
1912 let output_start = i128::from(edge_padding_low[axis])
1913 .checked_add(
1914 i128::try_from(start)
1915 .map_err(|_| StridedError::OffsetOverflow)?
1916 .checked_mul(i128::from(interior_step[axis]))
1917 .ok_or(StridedError::OffsetOverflow)?,
1918 )
1919 .ok_or(StridedError::OffsetOverflow)?;
1920 let output_start =
1921 usize::try_from(output_start).map_err(|_| StridedError::OffsetOverflow)?;
1922 dest_base_delta =
1923 checked_offset_add(dest_base_delta, dest_strides[axis], output_start)?;
1924 }
1925 copy_empty |= extent == 0;
1926
1927 let source_step = operand_strides[axis];
1928 let dest_step = checked_stride_mul_i64(dest_strides[axis], interior_step[axis])?;
1929 source_steps.push(source_step);
1930 source_resets.push(checked_cursor_reset(source_step, extent)?);
1931 dest_steps.push(dest_step);
1932 dest_resets.push(checked_cursor_reset(dest_step, extent)?);
1933 }
1934
1935 check_offset_span(&shape, &source_steps)?;
1936 check_offset_span(&shape, &dest_steps)?;
1937 let total = if shape.iter().any(|&extent| extent == 0) {
1938 0
1939 } else {
1940 checked_total_len(&shape)?
1941 };
1942
1943 Ok(PadCopyCursor {
1944 shape,
1945 source_base_delta,
1946 dest_base_delta,
1947 source_steps,
1948 source_resets,
1949 dest_steps,
1950 dest_resets,
1951 total,
1952 })
1953}
1954
1955fn checked_pad_valid_interval(
1956 input_extent: usize,
1957 dest_extent: usize,
1958 edge_low: i64,
1959 step: i64,
1960) -> Result<(usize, usize)> {
1961 if input_extent == 0 || dest_extent == 0 {
1962 return Ok((0, 0));
1963 }
1964 let step = i128::from(step);
1965 let lower = ceil_div_positive(-i128::from(edge_low), step)?;
1966 let dest_last = i128::try_from(dest_extent)
1967 .map_err(|_| StridedError::OffsetOverflow)?
1968 .checked_sub(1)
1969 .ok_or(StridedError::OffsetOverflow)?;
1970 let upper = floor_div_positive(
1971 dest_last
1972 .checked_sub(i128::from(edge_low))
1973 .ok_or(StridedError::OffsetOverflow)?,
1974 step,
1975 )?
1976 .checked_add(1)
1977 .ok_or(StridedError::OffsetOverflow)?;
1978 let input_extent = i128::try_from(input_extent).map_err(|_| StridedError::OffsetOverflow)?;
1979 let lower = lower.clamp(0, input_extent);
1980 let upper = upper.clamp(0, input_extent);
1981 if lower >= upper {
1982 return Ok((0, 0));
1983 }
1984 Ok((
1985 usize::try_from(lower).map_err(|_| StridedError::OffsetOverflow)?,
1986 usize::try_from(upper).map_err(|_| StridedError::OffsetOverflow)?,
1987 ))
1988}
1989
1990fn ceil_div_positive(numerator: i128, denominator: i128) -> Result<i128> {
1991 if denominator <= 0 {
1992 return Err(StridedError::OffsetOverflow);
1993 }
1994 let quotient = numerator.div_euclid(denominator);
1995 let remainder = numerator.rem_euclid(denominator);
1996 quotient
1997 .checked_add(i128::from(remainder != 0))
1998 .ok_or(StridedError::OffsetOverflow)
1999}
2000
2001fn floor_div_positive(numerator: i128, denominator: i128) -> Result<i128> {
2002 if denominator <= 0 {
2003 return Err(StridedError::OffsetOverflow);
2004 }
2005 Ok(numerator.div_euclid(denominator))
2006}
2007
2008fn checked_stride_mul_i64(stride: isize, factor: i64) -> Result<isize> {
2009 let factor = isize::try_from(factor).map_err(|_| StridedError::OffsetOverflow)?;
2010 stride
2011 .checked_mul(factor)
2012 .ok_or(StridedError::OffsetOverflow)
2013}
2014
2015fn checked_cursor_reset(step: isize, extent: usize) -> Result<isize> {
2016 if extent == 0 {
2017 return Ok(0);
2018 }
2019 let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2020 step.checked_mul(last)
2021 .and_then(isize::checked_neg)
2022 .ok_or(StridedError::OffsetOverflow)
2023}
2024
2025fn check_offset_span(shape: &[usize], strides: &[isize]) -> Result<()> {
2026 let mut min = 0isize;
2027 let mut max = 0isize;
2028 for (&extent, &stride) in shape.iter().zip(strides) {
2029 if extent <= 1 {
2030 continue;
2031 }
2032 let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2033 let delta = stride
2034 .checked_mul(last)
2035 .ok_or(StridedError::OffsetOverflow)?;
2036 if delta < 0 {
2037 min = min.checked_add(delta).ok_or(StridedError::OffsetOverflow)?;
2038 } else {
2039 max = max.checked_add(delta).ok_or(StridedError::OffsetOverflow)?;
2040 }
2041 }
2042 let _ = (min, max);
2043 Ok(())
2044}
2045
2046fn is_dense_col_major(dims: &[usize], strides: &[isize]) -> bool {
2047 let mut expected = 1isize;
2048 for (&dim, &stride) in dims.iter().zip(strides.iter()) {
2049 if stride != expected {
2050 return false;
2051 }
2052 let Ok(dim) = isize::try_from(dim) else {
2053 return false;
2054 };
2055 let Some(next) = expected.checked_mul(dim) else {
2056 return false;
2057 };
2058 expected = next;
2059 }
2060 true
2061}
2062
2063fn compile_contiguous_pad_axis0_run(
2064 operand_dims: &[usize],
2065 operand_strides: &[isize],
2066 dest_dims: &[usize],
2067 dest_strides: &[isize],
2068 edge_padding_low: &[i64],
2069 interior_step: &[i64],
2070) -> Option<ContiguousPadAxis0Run> {
2071 if operand_dims.is_empty()
2072 || operand_strides[0] != 1
2073 || dest_strides[0] != 1
2074 || interior_step[0] != 1
2075 {
2076 return None;
2077 }
2078
2079 let operand_extent = operand_dims[0] as i128;
2080 let dest_extent = dest_dims[0] as i128;
2081 let edge_low = i128::from(edge_padding_low[0]);
2082 let operand_start = (-edge_low).clamp(0, operand_extent);
2083 let dest_start = edge_low.clamp(0, dest_extent);
2084 let len = (operand_extent - operand_start).min(dest_extent - dest_start);
2085 Some(ContiguousPadAxis0Run {
2086 operand_start: usize::try_from(operand_start).ok()?,
2087 dest_start: usize::try_from(dest_start).ok()?,
2088 len: usize::try_from(len).ok()?,
2089 })
2090}
2091
2092#[allow(clippy::too_many_arguments)]
2095fn compile_contiguous_pad_axis0_columns(
2096 operand_dims: &[usize],
2097 operand_strides: &[isize],
2098 dest_dims: &[usize],
2099 edge_padding_low: &[i64],
2100 edge_padding_high: &[i64],
2101 interior_step: &[i64],
2102 contiguous_dest_fill: bool,
2103 run: ContiguousPadAxis0Run,
2104) -> Option<ContiguousPadAxis0Columns> {
2105 if run.len == 0 || !contiguous_dest_fill || dest_dims.is_empty() {
2106 return None;
2107 }
2108 if edge_padding_low.iter().any(|&low| low < 0)
2109 || edge_padding_high.iter().any(|&high| high < 0)
2110 || interior_step.iter().any(|&step| step != 1)
2111 {
2112 return None;
2113 }
2114
2115 let rank = operand_dims.len();
2116 let dest_axis0_len = dest_dims[0];
2117 let dest_axis0_step = isize::try_from(dest_axis0_len).ok()?;
2118 let column_total = checked_total_len(&dest_dims[1..]).ok()?;
2119 let mut operand_outer_dims = AxisVec::with_capacity(rank - 1);
2120 let mut operand_outer_strides = AxisVec::with_capacity(rank - 1);
2121 let mut dest_outer_dims = AxisVec::with_capacity(rank - 1);
2122 let mut edge_low_outer = AxisVec::with_capacity(rank - 1);
2123 for axis in 1..rank {
2124 operand_outer_dims.push(operand_dims[axis]);
2125 operand_outer_strides.push(operand_strides[axis]);
2126 dest_outer_dims.push(dest_dims[axis]);
2127 edge_low_outer.push(usize::try_from(edge_padding_low[axis]).ok()?);
2128 }
2129
2130 let low0 = run.dest_start;
2131 let high0 = dest_axis0_len.checked_sub(low0)?.checked_sub(run.len)?;
2132 Some(ContiguousPadAxis0Columns {
2133 column_total,
2134 dest_axis0_len,
2135 dest_axis0_step,
2136 low0,
2137 high0,
2138 run_len: run.len,
2139 operand_outer_dims,
2140 operand_outer_strides,
2141 dest_outer_dims,
2142 edge_low_outer,
2143 })
2144}
2145
2146unsafe fn fill_raw_span<T: Copy + Send + Sync>(ptr: *mut T, len: usize, fill: T, exec: Exec<'_>) {
2153 if len == 0 {
2154 return;
2155 }
2156 let span = unsafe { core::slice::from_raw_parts_mut(ptr, len) };
2159 crate::threading::fill_contiguous(span, fill, exec);
2160}
2161
2162unsafe fn fill_raw_span_uninit<T: Copy + Send + Sync>(
2169 ptr: *mut T,
2170 len: usize,
2171 fill: T,
2172 exec: Exec<'_>,
2173) {
2174 if len == 0 {
2175 return;
2176 }
2177 unsafe { crate::threading::fill_contiguous_uninit(ptr, len, fill, exec) };
2180}
2181
2182fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2183 let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2184 let scaled = stride
2185 .checked_mul(coord)
2186 .ok_or(StridedError::OffsetOverflow)?;
2187 base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2188}
2189
2190fn in_bounds_outer_coord(
2193 columns: &ContiguousPadAxis0Columns,
2194 axis: usize,
2195 coord: usize,
2196) -> Option<usize> {
2197 let q = coord.checked_sub(columns.edge_low_outer[axis])?;
2198 (q < columns.operand_outer_dims[axis]).then_some(q)
2199}
2200
2201fn advance_col_major_index(index: &mut [usize], shape: &[usize]) {
2202 for axis in 0..index.len() {
2203 index[axis] += 1;
2204 if index[axis] < shape[axis] {
2205 return;
2206 }
2207 index[axis] = 0;
2208 }
2209}
2210
2211fn fill_col_major_index(mut linear: usize, shape: &[usize], out: &mut [usize]) {
2212 for (axis, coord) in out.iter_mut().enumerate() {
2213 let dim = shape[axis];
2214 *coord = linear % dim;
2215 linear /= dim;
2216 }
2217}
2218
2219struct PadFillState {
2220 coords: CoordScratch,
2221 offset: isize,
2222}
2223
2224impl PadFillState {
2225 fn new(base: isize, shape: &[usize], _cursor: &PadFillCursor) -> Self {
2226 Self {
2227 coords: CoordScratch::new(shape.len()),
2228 offset: base,
2229 }
2230 }
2231
2232 fn decode(linear: usize, base: isize, shape: &[usize], cursor: &PadFillCursor) -> Result<Self> {
2233 let mut state = Self::new(base, shape, cursor);
2234 fill_col_major_index(linear, shape, state.coords.as_mut_slice());
2235 for (&coord, &step) in state.coords.as_mut_slice().iter().zip(&cursor.steps) {
2236 state.offset = checked_offset_add(state.offset, step, coord)?;
2237 }
2238 Ok(state)
2239 }
2240
2241 #[inline]
2242 fn advance(&mut self, shape: &[usize], cursor: &PadFillCursor) {
2243 for axis in 0..shape.len() {
2247 let next = self.coords.as_mut_slice()[axis] + 1;
2248 if next < shape[axis] {
2249 self.coords.as_mut_slice()[axis] = next;
2250 self.offset += cursor.steps[axis];
2251 return;
2252 }
2253 self.coords.as_mut_slice()[axis] = 0;
2254 self.offset += cursor.resets[axis];
2255 }
2256 }
2257}
2258
2259struct PadCopyState {
2260 coords: CoordScratch,
2261 source_offset: isize,
2262 dest_offset: isize,
2263}
2264
2265impl PadCopyState {
2266 fn new(source_base: isize, dest_base: isize, cursor: &PadCopyCursor) -> Self {
2267 Self {
2268 coords: CoordScratch::new(cursor.shape.len()),
2269 source_offset: source_base,
2270 dest_offset: dest_base,
2271 }
2272 }
2273
2274 fn decode(
2275 linear: usize,
2276 source_base: isize,
2277 dest_base: isize,
2278 cursor: &PadCopyCursor,
2279 ) -> Result<Self> {
2280 let mut state = Self::new(source_base, dest_base, cursor);
2281 fill_col_major_index(linear, &cursor.shape, state.coords.as_mut_slice());
2282 for axis in 0..cursor.shape.len() {
2283 let coord = state.coords.as_mut_slice()[axis];
2284 state.source_offset =
2285 checked_offset_add(state.source_offset, cursor.source_steps[axis], coord)?;
2286 state.dest_offset =
2287 checked_offset_add(state.dest_offset, cursor.dest_steps[axis], coord)?;
2288 }
2289 Ok(state)
2290 }
2291
2292 #[inline]
2293 fn advance(&mut self, cursor: &PadCopyCursor) {
2294 for axis in 0..cursor.shape.len() {
2298 let next = self.coords.as_mut_slice()[axis] + 1;
2299 if next < cursor.shape[axis] {
2300 self.coords.as_mut_slice()[axis] = next;
2301 self.source_offset += cursor.source_steps[axis];
2302 self.dest_offset += cursor.dest_steps[axis];
2303 return;
2304 }
2305 self.coords.as_mut_slice()[axis] = 0;
2306 self.source_offset += cursor.source_resets[axis];
2307 self.dest_offset += cursor.dest_resets[axis];
2308 }
2309 }
2310}
2311
2312struct CoordScratch {
2313 inline: [usize; crate::RAW_FUSED_RANK_LIMIT],
2314 heap: Option<Vec<usize>>,
2315 len: usize,
2316}
2317
2318impl CoordScratch {
2319 fn new(len: usize) -> Self {
2320 if len <= crate::RAW_FUSED_RANK_LIMIT {
2321 Self {
2322 inline: [0; crate::RAW_FUSED_RANK_LIMIT],
2323 heap: None,
2324 len,
2325 }
2326 } else {
2327 Self {
2328 inline: [0; crate::RAW_FUSED_RANK_LIMIT],
2329 heap: Some(vec![0; len]),
2330 len,
2331 }
2332 }
2333 }
2334
2335 fn as_mut_slice(&mut self) -> &mut [usize] {
2336 match &mut self.heap {
2337 Some(heap) => heap,
2338 None => &mut self.inline[..self.len],
2339 }
2340 }
2341}
2342
2343#[cfg(test)]
2344#[path = "static_indexing_plan/tests/tests.rs"]
2345mod tests;
2346
2347#[cfg(test)]
2348#[path = "static_indexing_plan/tests/parallel_tests.rs"]
2349mod parallel_tests;