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)]
650 unsafe fn write_axis0_columns_raw<T, const UNINIT: bool>(
651 &self,
652 dest_ptr: *mut T,
653 dest_offset: isize,
654 operand_ptr: *const T,
655 operand_offset: isize,
656 fill: T,
657 columns: &ContiguousPadAxis0Columns,
658 exec: Exec<'_>,
659 ) -> Result<()>
660 where
661 T: Copy + Send + Sync,
662 {
663 let column_total = columns.column_total;
664 if column_total == 0 {
665 return Ok(());
666 }
667 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.dest_total);
668 {
669 if exec.budget().get() > 1 && column_total >= exec.budget().get() {
670 let dest_ptr = crate::threading::SendPtr(dest_ptr);
671 let operand_ptr = crate::threading::SendPtr(operand_ptr as *mut T);
672 return crate::threading::parallel_map_reduce(
673 0..column_total,
674 exec,
675 &|range| {
676 let mut outer_idx_storage =
677 CoordScratch::new(columns.dest_outer_dims.len());
678 let outer_idx = outer_idx_storage.as_mut_slice();
679 fill_col_major_index(range.start, &columns.dest_outer_dims, outer_idx);
680 unsafe {
686 self.write_axis0_columns_range::<T, UNINIT>(
687 dest_ptr.as_ptr(),
688 dest_offset,
689 operand_ptr.as_const(),
690 operand_offset,
691 fill,
692 columns,
693 outer_idx,
694 range.start,
695 range.len(),
696 Exec::serial(),
697 )
698 }
699 },
700 &|left, right| left.and(right),
701 );
702 }
703 }
704 let mut outer_idx_storage = CoordScratch::new(columns.dest_outer_dims.len());
705 let outer_idx = outer_idx_storage.as_mut_slice();
706 unsafe {
708 self.write_axis0_columns_range::<T, UNINIT>(
709 dest_ptr,
710 dest_offset,
711 operand_ptr,
712 operand_offset,
713 fill,
714 columns,
715 outer_idx,
716 0,
717 column_total,
718 exec,
719 )
720 }
721 }
722
723 #[allow(clippy::too_many_arguments)]
732 unsafe fn write_axis0_columns_range<T, const UNINIT: bool>(
733 &self,
734 dest_ptr: *mut T,
735 dest_offset: isize,
736 operand_ptr: *const T,
737 operand_offset: isize,
738 fill: T,
739 columns: &ContiguousPadAxis0Columns,
740 outer_idx: &mut [usize],
741 column_start: usize,
742 count: usize,
743 mut exec: Exec<'_>,
744 ) -> Result<()>
745 where
746 T: Copy + Send + Sync,
747 {
748 if count == 0 {
749 return Ok(());
750 }
751 let mut dest_column_offset =
752 checked_offset_add(dest_offset, columns.dest_axis0_step, column_start)?;
753 let mut operand_column_offset = operand_offset;
758 let mut out_of_bounds = 0usize;
759 for (axis, &coord) in outer_idx.iter().enumerate() {
760 match in_bounds_outer_coord(columns, axis, coord) {
761 Some(q) => {
762 operand_column_offset = checked_offset_add(
763 operand_column_offset,
764 columns.operand_outer_strides[axis],
765 q,
766 )?;
767 }
768 None => out_of_bounds += 1,
769 }
770 }
771 for _ in 0..count {
772 if out_of_bounds == 0 {
773 let low_len = columns.low0;
774 let run_len = columns.run_len;
775 let high_len = columns.high0;
776 unsafe {
783 if UNINIT {
784 fill_raw_span_uninit(
785 dest_ptr.offset(dest_column_offset),
786 low_len,
787 fill,
788 exec.reborrow(),
789 );
790 } else {
791 fill_raw_span(
792 dest_ptr.offset(dest_column_offset),
793 low_len,
794 fill,
795 exec.reborrow(),
796 );
797 }
798 crate::threading::copy_contiguous(
799 operand_ptr.offset(operand_column_offset),
800 dest_ptr.offset(dest_column_offset + low_len as isize),
801 run_len,
802 exec.reborrow(),
803 );
804 if UNINIT {
805 fill_raw_span_uninit(
806 dest_ptr
807 .offset(dest_column_offset + low_len as isize + run_len as isize),
808 high_len,
809 fill,
810 exec.reborrow(),
811 );
812 } else {
813 fill_raw_span(
814 dest_ptr
815 .offset(dest_column_offset + low_len as isize + run_len as isize),
816 high_len,
817 fill,
818 exec.reborrow(),
819 );
820 }
821 }
822 } else {
823 unsafe {
826 if UNINIT {
827 fill_raw_span_uninit(
828 dest_ptr.offset(dest_column_offset),
829 columns.dest_axis0_len,
830 fill,
831 exec.reborrow(),
832 );
833 } else {
834 fill_raw_span(
835 dest_ptr.offset(dest_column_offset),
836 columns.dest_axis0_len,
837 fill,
838 exec.reborrow(),
839 );
840 }
841 }
842 }
843 dest_column_offset = dest_column_offset
846 .checked_add(columns.dest_axis0_step)
847 .ok_or(StridedError::OffsetOverflow)?;
848 for (axis, coord) in outer_idx.iter_mut().enumerate() {
849 let was_in_bounds = in_bounds_outer_coord(columns, axis, *coord);
850 if let Some(q) = was_in_bounds {
851 let q = isize::try_from(q).map_err(|_| StridedError::OffsetOverflow)?;
852 let scaled = columns.operand_outer_strides[axis]
853 .checked_mul(q)
854 .ok_or(StridedError::OffsetOverflow)?;
855 operand_column_offset = operand_column_offset
856 .checked_sub(scaled)
857 .ok_or(StridedError::OffsetOverflow)?;
858 }
859 *coord += 1;
860 let wrapped = *coord >= columns.dest_outer_dims[axis];
861 if wrapped {
862 *coord = 0;
863 }
864 let is_in_bounds = in_bounds_outer_coord(columns, axis, *coord);
865 if let Some(q) = is_in_bounds {
866 operand_column_offset = checked_offset_add(
867 operand_column_offset,
868 columns.operand_outer_strides[axis],
869 q,
870 )?;
871 }
872 match (was_in_bounds.is_some(), is_in_bounds.is_some()) {
873 (false, true) => out_of_bounds -= 1,
874 (true, false) => out_of_bounds += 1,
875 _ => {}
876 }
877 if !wrapped {
878 break;
879 }
880 }
881 }
882 Ok(())
883 }
884
885 unsafe fn copy_axis0_runs_raw<T>(
898 &self,
899 dest_ptr: *mut T,
900 dest_offset: isize,
901 operand: &RawStridedRef<'_, T>,
902 run: ContiguousPadAxis0Run,
903 exec: Exec<'_>,
904 ) -> Result<()>
905 where
906 T: Copy + Send + Sync,
907 {
908 if run.len == 0 {
909 return Ok(());
910 }
911 let outer_dims = &self.operand_dims[1..];
912 let outer_total = checked_total_len(outer_dims)?;
913 let copied = outer_total.saturating_mul(run.len);
914 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, copied);
915 {
916 if exec.budget().get() > 1 && outer_total >= exec.budget().get() {
917 let dest_ptr = crate::threading::SendPtr(dest_ptr);
918 return crate::threading::parallel_map_reduce(
919 0..outer_total,
920 exec,
921 &|range| {
922 let mut outer_idx_storage = CoordScratch::new(outer_dims.len());
923 let outer_idx = outer_idx_storage.as_mut_slice();
924 fill_col_major_index(range.start, outer_dims, outer_idx);
925 unsafe {
929 self.copy_axis0_run_range(
930 dest_ptr.as_ptr(),
931 dest_offset,
932 operand,
933 run,
934 outer_idx,
935 range.len(),
936 Exec::serial(),
937 )
938 }
939 },
940 &|left, right| left.and(right),
941 );
942 }
943 }
944 let mut outer_idx_storage = CoordScratch::new(outer_dims.len());
945 let outer_idx = outer_idx_storage.as_mut_slice();
946 unsafe {
948 self.copy_axis0_run_range(
949 dest_ptr,
950 dest_offset,
951 operand,
952 run,
953 outer_idx,
954 outer_total,
955 exec,
956 )
957 }
958 }
959
960 #[allow(clippy::too_many_arguments)]
970 unsafe fn copy_axis0_run_range<T>(
971 &self,
972 dest_ptr: *mut T,
973 dest_offset: isize,
974 operand: &RawStridedRef<'_, T>,
975 run: ContiguousPadAxis0Run,
976 outer_idx: &mut [usize],
977 count: usize,
978 mut exec: Exec<'_>,
979 ) -> Result<()>
980 where
981 T: Copy + Send + Sync,
982 {
983 let outer_dims = &self.operand_dims[1..];
984 let operand_ptr = operand.data().as_ptr();
985 for _ in 0..count {
986 let mut operand_offset =
987 checked_offset_add(operand.offset(), self.operand_strides[0], run.operand_start)?;
988 let mut dest_run_offset =
989 checked_offset_add(dest_offset, self.dest_strides[0], run.dest_start)?;
990 let mut in_bounds = true;
991 for (outer_axis, &coord) in outer_idx.iter().enumerate() {
992 let axis = outer_axis + 1;
993 let out_pos = i128::from(self.edge_padding_low[axis])
994 + coord as i128 * i128::from(self.interior_step[axis]);
995 if out_pos < 0 || out_pos >= self.dest_dims[axis] as i128 {
996 in_bounds = false;
997 break;
998 }
999 operand_offset =
1000 checked_offset_add(operand_offset, self.operand_strides[axis], coord)?;
1001 dest_run_offset =
1002 checked_offset_add(dest_run_offset, self.dest_strides[axis], out_pos as usize)?;
1003 }
1004 if in_bounds {
1005 unsafe {
1011 crate::threading::copy_contiguous(
1012 operand_ptr.offset(operand_offset),
1013 dest_ptr.offset(dest_run_offset),
1014 run.len,
1015 exec.reborrow(),
1016 );
1017 }
1018 }
1019 advance_col_major_index(outer_idx, outer_dims);
1020 }
1021 Ok(())
1022 }
1023
1024 #[cfg(test)]
1025 fn contiguous_axis0_run(&self) -> Option<(usize, usize, usize)> {
1026 self.contiguous_axis0_run
1027 .map(|run| (run.operand_start, run.dest_start, run.len))
1028 }
1029
1030 #[cfg(test)]
1031 fn has_contiguous_dest_fill(&self) -> bool {
1032 self.contiguous_dest_fill
1033 }
1034
1035 #[cfg(test)]
1036 fn has_contiguous_axis0_columns(&self) -> bool {
1037 self.contiguous_axis0_columns.is_some()
1038 }
1039
1040 fn fill_dest_serial<T>(&self, dest: &mut RawStridedMut<'_, T>, fill: T) -> Result<()>
1041 where
1042 T: Copy,
1043 {
1044 let dest_ptr = dest.data_mut().as_mut_ptr();
1045 let mut cursor = PadFillState::new(dest.offset(), &self.dest_dims, &self.generic_fill);
1046 for _ in 0..self.dest_total {
1047 unsafe {
1048 *dest_ptr.offset(cursor.offset) = fill;
1052 }
1053 cursor.advance(&self.dest_dims, &self.generic_fill);
1054 }
1055 Ok(())
1056 }
1057
1058 fn fill_dest_parallel<T>(
1059 &self,
1060 dest: &mut RawStridedMut<'_, T>,
1061 fill: T,
1062 exec: Exec<'_>,
1063 ) -> Result<()>
1064 where
1065 T: Copy + Send + Sync,
1066 {
1067 let dest_offset_base = dest.offset();
1068 let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1069 crate::threading::parallel_map_reduce(
1070 0..self.dest_total,
1071 exec,
1072 &|range| {
1073 let mut cursor = PadFillState::decode(
1074 range.start,
1075 dest_offset_base,
1076 &self.dest_dims,
1077 &self.generic_fill,
1078 )?;
1079 let dest_ptr = dest_ptr.as_ptr();
1080 for _ in range {
1081 unsafe {
1082 *dest_ptr.offset(cursor.offset) = fill;
1087 }
1088 cursor.advance(&self.dest_dims, &self.generic_fill);
1089 }
1090 Ok(())
1091 },
1092 &|left, right| left.and(right),
1093 )
1094 }
1095
1096 fn copy_operand<T>(
1097 &self,
1098 dest: &mut RawStridedMut<'_, T>,
1099 operand: &RawStridedRef<'_, T>,
1100 exec: Exec<'_>,
1101 ) -> Result<()>
1102 where
1103 T: Copy + Send + Sync,
1104 {
1105 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.generic_copy.total);
1106 if !exec.is_serial() {
1107 return self.copy_operand_parallel(dest, operand, exec);
1108 }
1109 self.copy_operand_serial(dest, operand)
1110 }
1111
1112 fn copy_operand_uninit<T>(
1113 &self,
1114 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1115 operand: &RawStridedRef<'_, T>,
1116 exec: Exec<'_>,
1117 ) -> Result<()>
1118 where
1119 T: Copy + Send + Sync,
1120 {
1121 let exec = crate::cost::for_len_tree(exec, KernelClass::Copy, self.generic_copy.total);
1122 if !exec.is_serial() {
1123 return self.copy_operand_uninit_parallel(dest, operand, exec);
1124 }
1125 self.copy_operand_uninit_serial(dest, operand)
1126 }
1127
1128 fn copy_operand_uninit_serial<T>(
1129 &self,
1130 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1131 operand: &RawStridedRef<'_, T>,
1132 ) -> Result<()>
1133 where
1134 T: Copy,
1135 {
1136 if self.generic_copy.total == 0 {
1137 return Ok(());
1138 }
1139 let operand_ptr = operand.data().as_ptr();
1140 let dest_ptr = dest.data_mut().as_mut_ptr();
1141 let source_base = operand
1142 .offset()
1143 .checked_add(self.generic_copy.source_base_delta)
1144 .ok_or(StridedError::OffsetOverflow)?;
1145 let dest_base = dest
1146 .offset()
1147 .checked_add(self.generic_copy.dest_base_delta)
1148 .ok_or(StridedError::OffsetOverflow)?;
1149 let mut cursor = PadCopyState::new(source_base, dest_base, &self.generic_copy);
1150 for _ in 0..self.generic_copy.total {
1151 unsafe {
1161 (*dest_ptr.offset(cursor.dest_offset))
1166 .write(*operand_ptr.offset(cursor.source_offset));
1167 }
1168 cursor.advance(&self.generic_copy);
1169 }
1170 Ok(())
1171 }
1172
1173 fn copy_operand_uninit_parallel<T>(
1174 &self,
1175 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1176 operand: &RawStridedRef<'_, T>,
1177 exec: Exec<'_>,
1178 ) -> Result<()>
1179 where
1180 T: Copy + Send + Sync,
1181 {
1182 let operand_base = operand
1183 .offset()
1184 .checked_add(self.generic_copy.source_base_delta)
1185 .ok_or(StridedError::OffsetOverflow)?;
1186 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1187 let dest_base = dest
1188 .offset()
1189 .checked_add(self.generic_copy.dest_base_delta)
1190 .ok_or(StridedError::OffsetOverflow)?;
1191 let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1192 crate::threading::parallel_map_reduce(
1193 0..self.generic_copy.total,
1194 exec,
1195 &|range| {
1196 let mut cursor =
1197 PadCopyState::decode(range.start, operand_base, dest_base, &self.generic_copy)?;
1198 let operand_ptr = operand_ptr.as_const();
1199 let dest_ptr = dest_ptr.as_ptr();
1200
1201 for _ in range {
1202 unsafe {
1212 (*dest_ptr.offset(cursor.dest_offset))
1217 .write(*operand_ptr.offset(cursor.source_offset));
1218 }
1219 cursor.advance(&self.generic_copy);
1220 }
1221 Ok(())
1222 },
1223 &|left, right| left.and(right),
1224 )
1225 }
1226
1227 fn copy_operand_serial<T>(
1228 &self,
1229 dest: &mut RawStridedMut<'_, T>,
1230 operand: &RawStridedRef<'_, T>,
1231 ) -> Result<()>
1232 where
1233 T: Copy,
1234 {
1235 if self.generic_copy.total == 0 {
1236 return Ok(());
1237 }
1238 let operand_ptr = operand.data().as_ptr();
1239 let dest_ptr = dest.data_mut().as_mut_ptr();
1240 let source_base = operand
1241 .offset()
1242 .checked_add(self.generic_copy.source_base_delta)
1243 .ok_or(StridedError::OffsetOverflow)?;
1244 let dest_base = dest
1245 .offset()
1246 .checked_add(self.generic_copy.dest_base_delta)
1247 .ok_or(StridedError::OffsetOverflow)?;
1248 let mut cursor = PadCopyState::new(source_base, dest_base, &self.generic_copy);
1249 for _ in 0..self.generic_copy.total {
1250 unsafe {
1251 *dest_ptr.offset(cursor.dest_offset) = *operand_ptr.offset(cursor.source_offset);
1256 }
1257 cursor.advance(&self.generic_copy);
1258 }
1259 Ok(())
1260 }
1261
1262 fn copy_operand_parallel<T>(
1263 &self,
1264 dest: &mut RawStridedMut<'_, T>,
1265 operand: &RawStridedRef<'_, T>,
1266 exec: Exec<'_>,
1267 ) -> Result<()>
1268 where
1269 T: Copy + Send + Sync,
1270 {
1271 let operand_base = operand
1272 .offset()
1273 .checked_add(self.generic_copy.source_base_delta)
1274 .ok_or(StridedError::OffsetOverflow)?;
1275 let operand_ptr = crate::threading::SendPtr(operand.data().as_ptr() as *mut T);
1276 let dest_base = dest
1277 .offset()
1278 .checked_add(self.generic_copy.dest_base_delta)
1279 .ok_or(StridedError::OffsetOverflow)?;
1280 let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1281 crate::threading::parallel_map_reduce(
1282 0..self.generic_copy.total,
1283 exec,
1284 &|range| {
1285 let mut cursor =
1286 PadCopyState::decode(range.start, operand_base, dest_base, &self.generic_copy)?;
1287 let operand_ptr = operand_ptr.as_const();
1288 let dest_ptr = dest_ptr.as_ptr();
1289
1290 for _ in range {
1291 unsafe {
1292 *dest_ptr.offset(cursor.dest_offset) =
1297 *operand_ptr.offset(cursor.source_offset);
1298 }
1299 cursor.advance(&self.generic_copy);
1300 }
1301 Ok(())
1302 },
1303 &|left, right| left.and(right),
1304 )
1305 }
1306
1307 fn check_call<D, T>(
1308 &self,
1309 dest: &RawStridedMut<'_, D>,
1310 operand: &RawStridedRef<'_, T>,
1311 ) -> Result<()> {
1312 if operand.dims() != &self.operand_dims[..]
1313 || operand.strides() != &self.operand_strides[..]
1314 || dest.dims() != &self.dest_dims[..]
1315 || dest.strides() != &self.dest_strides[..]
1316 {
1317 return Err(StridedError::PlanLayoutMismatch);
1318 }
1319 Ok(())
1320 }
1321}
1322
1323impl ConcatenatePlan {
1324 pub fn compile(
1342 input_dims: &[&[usize]],
1343 input_strides: &[&[isize]],
1344 dest_dims: &[usize],
1345 dest_strides: &[isize],
1346 axis: usize,
1347 ) -> Result<Self> {
1348 if input_dims.is_empty() {
1349 return Err(StridedError::UnsupportedArity {
1350 arity: 0,
1351 max: usize::MAX,
1352 });
1353 }
1354 if input_dims.len() != input_strides.len() {
1355 return Err(StridedError::RankMismatch(
1356 input_strides.len(),
1357 input_dims.len(),
1358 ));
1359 }
1360
1361 let rank = input_dims[0].len();
1362 if dest_dims.len() != rank || dest_strides.len() != rank {
1363 return Err(StridedError::StrideLengthMismatch);
1364 }
1365 if axis >= rank {
1366 return Err(StridedError::InvalidAxis { axis, rank });
1367 }
1368 checked_total_len(dest_dims)?;
1369 if !crate::layout_check::is_injective_layout(dest_dims, dest_strides) {
1370 return Err(StridedError::NonInjectiveOutputLayout);
1371 }
1372
1373 let mut expected_dest_dims: AxisVec<usize> = input_dims[0].into();
1374 expected_dest_dims[axis] = 0;
1375 let mut stored_input_dims = crate::inline::OperandVec::with_capacity(input_dims.len());
1376 let mut stored_input_strides = crate::inline::OperandVec::with_capacity(input_dims.len());
1377 let mut dest_offset_deltas = crate::inline::OperandVec::with_capacity(input_dims.len());
1378 let mut copy_plans = crate::inline::OperandVec::with_capacity(input_dims.len());
1379 let mut segment_starts = crate::inline::OperandVec::with_capacity(input_dims.len() + 1);
1380 segment_starts.push(0usize);
1381 let mut axis_base = 0usize;
1382
1383 for (dims, strides) in input_dims.iter().zip(input_strides.iter()) {
1384 if dims.len() != rank {
1385 return Err(StridedError::RankMismatch(dims.len(), rank));
1386 }
1387 if strides.len() != rank {
1388 return Err(StridedError::StrideLengthMismatch);
1389 }
1390 let segment_total = checked_total_len(dims)?;
1391 let segment_end = segment_starts[segment_starts.len() - 1]
1392 .checked_add(segment_total)
1393 .ok_or(StridedError::OffsetOverflow)?;
1394 segment_starts.push(segment_end);
1395 for dim in 0..rank {
1396 if dim == axis {
1397 expected_dest_dims[axis] = expected_dest_dims[axis]
1398 .checked_add(dims[axis])
1399 .ok_or(StridedError::OffsetOverflow)?;
1400 } else if dims[dim] != input_dims[0][dim] {
1401 return Err(StridedError::ShapeMismatch(
1402 dims.to_vec(),
1403 input_dims[0].to_vec(),
1404 ));
1405 }
1406 }
1407 dest_offset_deltas.push(checked_offset_add(0, dest_strides[axis], axis_base)?);
1408 axis_base = axis_base
1409 .checked_add(dims[axis])
1410 .ok_or(StridedError::OffsetOverflow)?;
1411 copy_plans.push(CopyPlan::compile(dims, dest_strides, strides)?);
1412 stored_input_dims.push((*dims).into());
1413 stored_input_strides.push((*strides).into());
1414 }
1415
1416 if dest_dims != &expected_dest_dims[..] {
1417 return Err(StridedError::ShapeMismatch(
1418 dest_dims.to_vec(),
1419 expected_dest_dims.to_vec(),
1420 ));
1421 }
1422
1423 Ok(Self {
1424 input_dims: stored_input_dims,
1425 input_strides: stored_input_strides,
1426 dest_dims: dest_dims.into(),
1427 dest_strides: dest_strides.into(),
1428 dest_offset_deltas,
1429 segment_starts,
1430 copy_plans,
1431 })
1432 }
1433
1434 pub fn execute<T>(
1444 &self,
1445 dest: &mut RawStridedMut<'_, T>,
1446 inputs: &[RawStridedRef<'_, T>],
1447 exec: Exec<'_>,
1448 ) -> Result<()>
1449 where
1450 T: Copy + Send + Sync,
1451 {
1452 let mut exec = exec;
1453 self.check_dest_layout(dest)?;
1454 if inputs.len() != self.input_dims.len() {
1455 return Err(StridedError::RankMismatch(
1456 inputs.len(),
1457 self.input_dims.len(),
1458 ));
1459 }
1460 for (position, input) in inputs.iter().enumerate() {
1461 self.check_input_layout(position, input)?;
1462 self.segment_offset(position, dest.offset())?;
1463 }
1464 if self.try_execute_parallel(
1465 dest,
1466 inputs,
1467 |dst: &mut T, value| *dst = value,
1468 exec.reborrow(),
1469 )? {
1470 return Ok(());
1471 }
1472 for (position, input) in inputs.iter().enumerate() {
1473 self.execute_segment(position, dest, input, exec.reborrow())?;
1474 }
1475 Ok(())
1476 }
1477
1478 pub fn execute_uninit<T>(
1488 &self,
1489 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1490 inputs: &[RawStridedRef<'_, T>],
1491 exec: Exec<'_>,
1492 ) -> Result<()>
1493 where
1494 T: Copy + Send + Sync,
1495 {
1496 let mut exec = exec;
1497 self.check_dest_layout(dest)?;
1498 if inputs.len() != self.input_dims.len() {
1499 return Err(StridedError::RankMismatch(
1500 inputs.len(),
1501 self.input_dims.len(),
1502 ));
1503 }
1504 for (position, input) in inputs.iter().enumerate() {
1505 self.check_input_layout(position, input)?;
1506 self.segment_offset(position, dest.offset())?;
1507 }
1508 if self.try_execute_parallel(
1509 dest,
1510 inputs,
1511 |dst: &mut MaybeUninit<T>, value| {
1512 dst.write(value);
1513 },
1514 exec.reborrow(),
1515 )? {
1516 return Ok(());
1517 }
1518 for (position, input) in inputs.iter().enumerate() {
1519 self.execute_segment_uninit(position, dest, input, exec.reborrow())?;
1520 }
1521 Ok(())
1522 }
1523
1524 fn try_execute_parallel<D, T, Apply>(
1535 &self,
1536 dest: &mut RawStridedMut<'_, D>,
1537 inputs: &[RawStridedRef<'_, T>],
1538 apply: Apply,
1539 exec: Exec<'_>,
1540 ) -> Result<bool>
1541 where
1542 D: Copy + Send + Sync,
1543 T: Copy + Send + Sync,
1544 Apply: Fn(&mut D, T) + Send + Sync,
1545 {
1546 let total = self.segment_starts[self.segment_starts.len() - 1];
1547 let exec = crate::cost::for_len(exec, KernelClass::Copy, total);
1548 if exec.is_serial() {
1549 return Ok(false);
1550 }
1551 let mut dest_offsets: crate::inline::OperandVec<isize> =
1556 crate::inline::OperandVec::with_capacity(inputs.len());
1557 for position in 0..inputs.len() {
1558 if self.copy_plans[position].fused_layout().is_none() {
1559 return Ok(false);
1560 }
1561 dest_offsets.push(self.segment_offset(position, dest.offset())?);
1562 }
1563 let dest_ptr = crate::threading::SendPtr(dest.data_mut().as_mut_ptr());
1564 let starts = &self.segment_starts;
1565 let dest_offsets = &dest_offsets;
1566 crate::threading::parallel_for_each(0..total, exec, &|range| {
1567 let mut position = starts[1..].partition_point(|&end| end <= range.start);
1569 while position < inputs.len() && starts[position] < range.end {
1570 let local_start = range.start.max(starts[position]) - starts[position];
1571 let local_end = range.end.min(starts[position + 1]) - starts[position];
1572 let Some(layout) = self.copy_plans[position].fused_layout() else {
1576 position += 1;
1577 continue;
1578 };
1579 let input = &inputs[position];
1580 unsafe {
1590 crate::raw_ops::apply_fused_range(
1591 dest_ptr.as_ptr(),
1592 dest_offsets[position],
1593 input.data().as_ptr(),
1594 input.offset(),
1595 layout,
1596 local_start,
1597 local_end - local_start,
1598 &apply,
1599 );
1600 }
1601 position += 1;
1602 }
1603 });
1604 Ok(true)
1605 }
1606
1607 pub(crate) fn check_dest_layout<T>(&self, dest: &RawStridedMut<'_, T>) -> Result<()> {
1608 if dest.dims() != &self.dest_dims[..] || dest.strides() != &self.dest_strides[..] {
1609 return Err(StridedError::PlanLayoutMismatch);
1610 }
1611 Ok(())
1612 }
1613
1614 pub(crate) fn check_input_layout<T>(
1615 &self,
1616 position: usize,
1617 input: &RawStridedRef<'_, T>,
1618 ) -> Result<()> {
1619 if position >= self.input_dims.len()
1620 || input.dims() != &self.input_dims[position][..]
1621 || input.strides() != &self.input_strides[position][..]
1622 {
1623 return Err(StridedError::PlanLayoutMismatch);
1624 }
1625 Ok(())
1626 }
1627
1628 pub(crate) fn input_count(&self) -> usize {
1629 self.input_dims.len()
1630 }
1631
1632 pub(crate) fn prefers_whole_plan(&self, exec: &Exec<'_>) -> bool {
1636 let total = self.segment_starts[self.segment_starts.len() - 1];
1637 crate::threading::is_parallel(KernelClass::Copy, total, exec)
1638 }
1639
1640 pub(crate) fn segment_offset(&self, position: usize, dest_offset: isize) -> Result<isize> {
1641 dest_offset
1642 .checked_add(self.dest_offset_deltas[position])
1643 .ok_or(StridedError::OffsetOverflow)
1644 }
1645
1646 pub(crate) fn execute_segment<T>(
1647 &self,
1648 position: usize,
1649 dest: &mut RawStridedMut<'_, T>,
1650 input: &RawStridedRef<'_, T>,
1651 exec: Exec<'_>,
1652 ) -> Result<()>
1653 where
1654 T: Copy + Send + Sync,
1655 {
1656 let segment_offset = self.segment_offset(position, dest.offset())?;
1657 let dest_data = dest.data_mut();
1658 let mut segment = unsafe {
1659 RawStridedMut::new_unchecked(
1660 dest_data,
1661 &self.input_dims[position],
1662 &self.dest_strides,
1663 segment_offset,
1664 )
1665 };
1666 self.copy_plans[position].execute(&mut segment, input, exec)
1667 }
1668
1669 pub(crate) fn execute_segment_uninit<T>(
1670 &self,
1671 position: usize,
1672 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1673 input: &RawStridedRef<'_, T>,
1674 exec: Exec<'_>,
1675 ) -> Result<()>
1676 where
1677 T: Copy + Send + Sync,
1678 {
1679 let segment_offset = self.segment_offset(position, dest.offset())?;
1680 let dest_data = dest.data_mut();
1681 let mut segment = unsafe {
1682 RawStridedMut::new_unchecked(
1683 dest_data,
1684 &self.input_dims[position],
1685 &self.dest_strides,
1686 segment_offset,
1687 )
1688 };
1689 self.copy_plans[position].execute_uninit(&mut segment, input, exec)
1690 }
1691}
1692
1693impl ReversePlan {
1694 pub fn compile(
1707 operand_dims: &[usize],
1708 operand_strides: &[isize],
1709 dest_strides: &[isize],
1710 axes: &[usize],
1711 ) -> Result<Self> {
1712 let rank = operand_dims.len();
1713 if operand_strides.len() != rank || dest_strides.len() != rank {
1714 return Err(StridedError::StrideLengthMismatch);
1715 }
1716 checked_total_len(operand_dims)?;
1717
1718 let mut reverse_axis: AxisVec<bool> = (0..rank).map(|_| false).collect();
1719 for &axis in axes {
1720 if axis >= rank {
1721 return Err(StridedError::InvalidAxis { axis, rank });
1722 }
1723 reverse_axis[axis] = true;
1724 }
1725
1726 let mut source_strides: AxisVec<isize> = AxisVec::with_capacity(rank);
1727 let mut source_offset_delta = 0isize;
1728 for axis in 0..rank {
1729 if reverse_axis[axis] {
1730 source_strides.push(
1731 operand_strides[axis]
1732 .checked_neg()
1733 .ok_or(StridedError::OffsetOverflow)?,
1734 );
1735 if operand_dims[axis] > 0 {
1736 source_offset_delta = checked_offset_add(
1737 source_offset_delta,
1738 operand_strides[axis],
1739 operand_dims[axis] - 1,
1740 )?;
1741 }
1742 } else {
1743 source_strides.push(operand_strides[axis]);
1744 }
1745 }
1746 let copy_plan = CopyPlan::compile(operand_dims, dest_strides, &source_strides)?;
1747
1748 Ok(Self {
1749 operand_dims: operand_dims.into(),
1750 operand_strides: operand_strides.into(),
1751 dest_strides: dest_strides.into(),
1752 source_strides,
1753 source_offset_delta,
1754 copy_plan,
1755 })
1756 }
1757
1758 pub fn execute<T>(
1767 &self,
1768 dest: &mut RawStridedMut<'_, T>,
1769 operand: &RawStridedRef<'_, T>,
1770 exec: Exec<'_>,
1771 ) -> Result<()>
1772 where
1773 T: Copy + Send + Sync,
1774 {
1775 self.check_call(dest, operand)?;
1776 let source_offset = operand
1777 .offset()
1778 .checked_add(self.source_offset_delta)
1779 .ok_or(StridedError::OffsetOverflow)?;
1780 let source = unsafe {
1781 RawStridedRef::new_unchecked(
1782 operand.data(),
1783 &self.operand_dims,
1784 &self.source_strides,
1785 source_offset,
1786 )
1787 };
1788 self.copy_plan.execute(dest, &source, exec)
1789 }
1790
1791 pub fn execute_uninit<T>(
1800 &self,
1801 dest: &mut RawStridedMut<'_, MaybeUninit<T>>,
1802 operand: &RawStridedRef<'_, T>,
1803 exec: Exec<'_>,
1804 ) -> Result<()>
1805 where
1806 T: Copy + Send + Sync,
1807 {
1808 self.check_call(dest, operand)?;
1809 let source_offset = operand
1810 .offset()
1811 .checked_add(self.source_offset_delta)
1812 .ok_or(StridedError::OffsetOverflow)?;
1813 let source = unsafe {
1814 RawStridedRef::new_unchecked(
1815 operand.data(),
1816 &self.operand_dims,
1817 &self.source_strides,
1818 source_offset,
1819 )
1820 };
1821 self.copy_plan.execute_uninit(dest, &source, exec)
1822 }
1823
1824 fn check_call<D, T>(
1825 &self,
1826 dest: &RawStridedMut<'_, D>,
1827 operand: &RawStridedRef<'_, T>,
1828 ) -> Result<()> {
1829 if operand.dims() != &self.operand_dims[..]
1830 || operand.strides() != &self.operand_strides[..]
1831 || dest.dims() != &self.operand_dims[..]
1832 || dest.strides() != &self.dest_strides[..]
1833 {
1834 return Err(StridedError::PlanLayoutMismatch);
1835 }
1836 Ok(())
1837 }
1838}
1839
1840fn checked_total_len(dims: &[usize]) -> Result<usize> {
1841 if dims.is_empty() {
1842 return Ok(1);
1843 }
1844 dims.iter()
1845 .try_fold(1usize, |acc, &dim| acc.checked_mul(dim))
1846 .ok_or(StridedError::OffsetOverflow)
1847}
1848
1849fn checked_stride_mul(stride: isize, factor: usize) -> Result<isize> {
1850 let factor = isize::try_from(factor).map_err(|_| StridedError::OffsetOverflow)?;
1851 stride
1852 .checked_mul(factor)
1853 .ok_or(StridedError::OffsetOverflow)
1854}
1855
1856fn checked_pad_output_dim(
1857 input_extent: usize,
1858 edge_low: i64,
1859 edge_high: i64,
1860 interior_step: i64,
1861 axis: usize,
1862 rank: usize,
1863) -> Result<usize> {
1864 let base = if input_extent == 0 {
1865 0i128
1866 } else {
1867 (input_extent as i128 - 1)
1868 .checked_mul(i128::from(interior_step))
1869 .and_then(|value| value.checked_add(1))
1870 .ok_or(StridedError::OffsetOverflow)?
1871 };
1872 let dim = i128::from(edge_low)
1873 .checked_add(i128::from(edge_high))
1874 .and_then(|value| value.checked_add(base))
1875 .ok_or(StridedError::OffsetOverflow)?;
1876 usize::try_from(dim).map_err(|_| StridedError::InvalidAxis { axis, rank })
1877}
1878
1879fn compile_pad_fill_cursor(dims: &[usize], strides: &[isize]) -> Result<PadFillCursor> {
1880 let mut steps = AxisVec::with_capacity(dims.len());
1881 let mut resets = AxisVec::with_capacity(dims.len());
1882 for (&dim, &stride) in dims.iter().zip(strides) {
1883 steps.push(stride);
1884 resets.push(checked_cursor_reset(stride, dim)?);
1885 }
1886 check_offset_span(dims, &steps)?;
1887 Ok(PadFillCursor { steps, resets })
1888}
1889
1890fn compile_pad_copy_cursor(
1891 operand_dims: &[usize],
1892 operand_strides: &[isize],
1893 dest_dims: &[usize],
1894 dest_strides: &[isize],
1895 edge_padding_low: &[i64],
1896 interior_step: &[i64],
1897) -> Result<PadCopyCursor> {
1898 let mut shape = AxisVec::with_capacity(operand_dims.len());
1899 let mut source_steps = AxisVec::with_capacity(operand_dims.len());
1900 let mut source_resets = AxisVec::with_capacity(operand_dims.len());
1901 let mut dest_steps = AxisVec::with_capacity(operand_dims.len());
1902 let mut dest_resets = AxisVec::with_capacity(operand_dims.len());
1903 let mut source_base_delta = 0isize;
1904 let mut dest_base_delta = 0isize;
1905 let mut copy_empty = false;
1906
1907 for axis in 0..operand_dims.len() {
1908 let (start, end) = checked_pad_valid_interval(
1909 operand_dims[axis],
1910 dest_dims[axis],
1911 edge_padding_low[axis],
1912 interior_step[axis],
1913 )?;
1914 let extent = end - start;
1915 shape.push(extent);
1916 if !copy_empty && extent != 0 {
1917 source_base_delta =
1918 checked_offset_add(source_base_delta, operand_strides[axis], start)?;
1919 let output_start = i128::from(edge_padding_low[axis])
1920 .checked_add(
1921 i128::try_from(start)
1922 .map_err(|_| StridedError::OffsetOverflow)?
1923 .checked_mul(i128::from(interior_step[axis]))
1924 .ok_or(StridedError::OffsetOverflow)?,
1925 )
1926 .ok_or(StridedError::OffsetOverflow)?;
1927 let output_start =
1928 usize::try_from(output_start).map_err(|_| StridedError::OffsetOverflow)?;
1929 dest_base_delta =
1930 checked_offset_add(dest_base_delta, dest_strides[axis], output_start)?;
1931 }
1932 copy_empty |= extent == 0;
1933
1934 let source_step = operand_strides[axis];
1935 let dest_step = checked_stride_mul_i64(dest_strides[axis], interior_step[axis])?;
1936 source_steps.push(source_step);
1937 source_resets.push(checked_cursor_reset(source_step, extent)?);
1938 dest_steps.push(dest_step);
1939 dest_resets.push(checked_cursor_reset(dest_step, extent)?);
1940 }
1941
1942 check_offset_span(&shape, &source_steps)?;
1943 check_offset_span(&shape, &dest_steps)?;
1944 let total = if shape.contains(&0) {
1945 0
1946 } else {
1947 checked_total_len(&shape)?
1948 };
1949
1950 Ok(PadCopyCursor {
1951 shape,
1952 source_base_delta,
1953 dest_base_delta,
1954 source_steps,
1955 source_resets,
1956 dest_steps,
1957 dest_resets,
1958 total,
1959 })
1960}
1961
1962fn checked_pad_valid_interval(
1963 input_extent: usize,
1964 dest_extent: usize,
1965 edge_low: i64,
1966 step: i64,
1967) -> Result<(usize, usize)> {
1968 if input_extent == 0 || dest_extent == 0 {
1969 return Ok((0, 0));
1970 }
1971 let step = i128::from(step);
1972 let lower = ceil_div_positive(-i128::from(edge_low), step)?;
1973 let dest_last = i128::try_from(dest_extent)
1974 .map_err(|_| StridedError::OffsetOverflow)?
1975 .checked_sub(1)
1976 .ok_or(StridedError::OffsetOverflow)?;
1977 let upper = floor_div_positive(
1978 dest_last
1979 .checked_sub(i128::from(edge_low))
1980 .ok_or(StridedError::OffsetOverflow)?,
1981 step,
1982 )?
1983 .checked_add(1)
1984 .ok_or(StridedError::OffsetOverflow)?;
1985 let input_extent = i128::try_from(input_extent).map_err(|_| StridedError::OffsetOverflow)?;
1986 let lower = lower.clamp(0, input_extent);
1987 let upper = upper.clamp(0, input_extent);
1988 if lower >= upper {
1989 return Ok((0, 0));
1990 }
1991 Ok((
1992 usize::try_from(lower).map_err(|_| StridedError::OffsetOverflow)?,
1993 usize::try_from(upper).map_err(|_| StridedError::OffsetOverflow)?,
1994 ))
1995}
1996
1997fn ceil_div_positive(numerator: i128, denominator: i128) -> Result<i128> {
1998 if denominator <= 0 {
1999 return Err(StridedError::OffsetOverflow);
2000 }
2001 let quotient = numerator.div_euclid(denominator);
2002 let remainder = numerator.rem_euclid(denominator);
2003 quotient
2004 .checked_add(i128::from(remainder != 0))
2005 .ok_or(StridedError::OffsetOverflow)
2006}
2007
2008fn floor_div_positive(numerator: i128, denominator: i128) -> Result<i128> {
2009 if denominator <= 0 {
2010 return Err(StridedError::OffsetOverflow);
2011 }
2012 Ok(numerator.div_euclid(denominator))
2013}
2014
2015fn checked_stride_mul_i64(stride: isize, factor: i64) -> Result<isize> {
2016 let factor = isize::try_from(factor).map_err(|_| StridedError::OffsetOverflow)?;
2017 stride
2018 .checked_mul(factor)
2019 .ok_or(StridedError::OffsetOverflow)
2020}
2021
2022fn checked_cursor_reset(step: isize, extent: usize) -> Result<isize> {
2023 if extent == 0 {
2024 return Ok(0);
2025 }
2026 let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2027 step.checked_mul(last)
2028 .and_then(isize::checked_neg)
2029 .ok_or(StridedError::OffsetOverflow)
2030}
2031
2032fn check_offset_span(shape: &[usize], strides: &[isize]) -> Result<()> {
2033 let mut min = 0isize;
2034 let mut max = 0isize;
2035 for (&extent, &stride) in shape.iter().zip(strides) {
2036 if extent <= 1 {
2037 continue;
2038 }
2039 let last = isize::try_from(extent - 1).map_err(|_| StridedError::OffsetOverflow)?;
2040 let delta = stride
2041 .checked_mul(last)
2042 .ok_or(StridedError::OffsetOverflow)?;
2043 if delta < 0 {
2044 min = min.checked_add(delta).ok_or(StridedError::OffsetOverflow)?;
2045 } else {
2046 max = max.checked_add(delta).ok_or(StridedError::OffsetOverflow)?;
2047 }
2048 }
2049 let _ = (min, max);
2050 Ok(())
2051}
2052
2053fn is_dense_col_major(dims: &[usize], strides: &[isize]) -> bool {
2054 let mut expected = 1isize;
2055 for (&dim, &stride) in dims.iter().zip(strides.iter()) {
2056 if stride != expected {
2057 return false;
2058 }
2059 let Ok(dim) = isize::try_from(dim) else {
2060 return false;
2061 };
2062 let Some(next) = expected.checked_mul(dim) else {
2063 return false;
2064 };
2065 expected = next;
2066 }
2067 true
2068}
2069
2070fn compile_contiguous_pad_axis0_run(
2071 operand_dims: &[usize],
2072 operand_strides: &[isize],
2073 dest_dims: &[usize],
2074 dest_strides: &[isize],
2075 edge_padding_low: &[i64],
2076 interior_step: &[i64],
2077) -> Option<ContiguousPadAxis0Run> {
2078 if operand_dims.is_empty()
2079 || operand_strides[0] != 1
2080 || dest_strides[0] != 1
2081 || interior_step[0] != 1
2082 {
2083 return None;
2084 }
2085
2086 let operand_extent = operand_dims[0] as i128;
2087 let dest_extent = dest_dims[0] as i128;
2088 let edge_low = i128::from(edge_padding_low[0]);
2089 let operand_start = (-edge_low).clamp(0, operand_extent);
2090 let dest_start = edge_low.clamp(0, dest_extent);
2091 let len = (operand_extent - operand_start).min(dest_extent - dest_start);
2092 Some(ContiguousPadAxis0Run {
2093 operand_start: usize::try_from(operand_start).ok()?,
2094 dest_start: usize::try_from(dest_start).ok()?,
2095 len: usize::try_from(len).ok()?,
2096 })
2097}
2098
2099#[allow(clippy::too_many_arguments)]
2104fn compile_contiguous_pad_axis0_columns(
2105 operand_dims: &[usize],
2106 operand_strides: &[isize],
2107 dest_dims: &[usize],
2108 edge_padding_low: &[i64],
2109 edge_padding_high: &[i64],
2110 interior_step: &[i64],
2111 contiguous_dest_fill: bool,
2112 run: ContiguousPadAxis0Run,
2113) -> Option<ContiguousPadAxis0Columns> {
2114 if run.len == 0 || !contiguous_dest_fill || dest_dims.is_empty() {
2115 return None;
2116 }
2117 if edge_padding_low.iter().any(|&low| low < 0)
2118 || edge_padding_high.iter().any(|&high| high < 0)
2119 || interior_step.iter().any(|&step| step != 1)
2120 {
2121 return None;
2122 }
2123
2124 let rank = operand_dims.len();
2125 let dest_axis0_len = dest_dims[0];
2126 let dest_axis0_step = isize::try_from(dest_axis0_len).ok()?;
2127 let column_total = checked_total_len(&dest_dims[1..]).ok()?;
2128 let mut operand_outer_dims = AxisVec::with_capacity(rank - 1);
2129 let mut operand_outer_strides = AxisVec::with_capacity(rank - 1);
2130 let mut dest_outer_dims = AxisVec::with_capacity(rank - 1);
2131 let mut edge_low_outer = AxisVec::with_capacity(rank - 1);
2132 for axis in 1..rank {
2133 operand_outer_dims.push(operand_dims[axis]);
2134 operand_outer_strides.push(operand_strides[axis]);
2135 dest_outer_dims.push(dest_dims[axis]);
2136 edge_low_outer.push(usize::try_from(edge_padding_low[axis]).ok()?);
2137 }
2138
2139 let low0 = run.dest_start;
2140 let high0 = dest_axis0_len.checked_sub(low0)?.checked_sub(run.len)?;
2141 Some(ContiguousPadAxis0Columns {
2142 column_total,
2143 dest_axis0_len,
2144 dest_axis0_step,
2145 low0,
2146 high0,
2147 run_len: run.len,
2148 operand_outer_dims,
2149 operand_outer_strides,
2150 dest_outer_dims,
2151 edge_low_outer,
2152 })
2153}
2154
2155unsafe fn fill_raw_span<T: Copy + Send + Sync>(ptr: *mut T, len: usize, fill: T, exec: Exec<'_>) {
2162 if len == 0 {
2163 return;
2164 }
2165 let span = unsafe { core::slice::from_raw_parts_mut(ptr, len) };
2168 crate::threading::fill_contiguous(span, fill, exec);
2169}
2170
2171unsafe fn fill_raw_span_uninit<T: Copy + Send + Sync>(
2178 ptr: *mut T,
2179 len: usize,
2180 fill: T,
2181 exec: Exec<'_>,
2182) {
2183 if len == 0 {
2184 return;
2185 }
2186 unsafe { crate::threading::fill_contiguous_uninit(ptr, len, fill, exec) };
2189}
2190
2191fn checked_offset_add(base: isize, stride: isize, coord: usize) -> Result<isize> {
2192 let coord = isize::try_from(coord).map_err(|_| StridedError::OffsetOverflow)?;
2193 let scaled = stride
2194 .checked_mul(coord)
2195 .ok_or(StridedError::OffsetOverflow)?;
2196 base.checked_add(scaled).ok_or(StridedError::OffsetOverflow)
2197}
2198
2199fn in_bounds_outer_coord(
2202 columns: &ContiguousPadAxis0Columns,
2203 axis: usize,
2204 coord: usize,
2205) -> Option<usize> {
2206 let q = coord.checked_sub(columns.edge_low_outer[axis])?;
2207 (q < columns.operand_outer_dims[axis]).then_some(q)
2208}
2209
2210fn advance_col_major_index(index: &mut [usize], shape: &[usize]) {
2211 for axis in 0..index.len() {
2212 index[axis] += 1;
2213 if index[axis] < shape[axis] {
2214 return;
2215 }
2216 index[axis] = 0;
2217 }
2218}
2219
2220fn fill_col_major_index(mut linear: usize, shape: &[usize], out: &mut [usize]) {
2221 for (axis, coord) in out.iter_mut().enumerate() {
2222 let dim = shape[axis];
2223 *coord = linear % dim;
2224 linear /= dim;
2225 }
2226}
2227
2228struct PadFillState {
2229 coords: CoordScratch,
2230 offset: isize,
2231}
2232
2233impl PadFillState {
2234 fn new(base: isize, shape: &[usize], _cursor: &PadFillCursor) -> Self {
2235 Self {
2236 coords: CoordScratch::new(shape.len()),
2237 offset: base,
2238 }
2239 }
2240
2241 fn decode(linear: usize, base: isize, shape: &[usize], cursor: &PadFillCursor) -> Result<Self> {
2242 let mut state = Self::new(base, shape, cursor);
2243 fill_col_major_index(linear, shape, state.coords.as_mut_slice());
2244 for (&coord, &step) in state.coords.as_mut_slice().iter().zip(&cursor.steps) {
2245 state.offset = checked_offset_add(state.offset, step, coord)?;
2246 }
2247 Ok(state)
2248 }
2249
2250 #[inline]
2251 fn advance(&mut self, shape: &[usize], cursor: &PadFillCursor) {
2252 #[allow(clippy::needless_range_loop)]
2257 for axis in 0..shape.len() {
2258 let next = self.coords.as_mut_slice()[axis] + 1;
2259 if next < shape[axis] {
2260 self.coords.as_mut_slice()[axis] = next;
2261 self.offset += cursor.steps[axis];
2262 return;
2263 }
2264 self.coords.as_mut_slice()[axis] = 0;
2265 self.offset += cursor.resets[axis];
2266 }
2267 }
2268}
2269
2270struct PadCopyState {
2271 coords: CoordScratch,
2272 source_offset: isize,
2273 dest_offset: isize,
2274}
2275
2276impl PadCopyState {
2277 fn new(source_base: isize, dest_base: isize, cursor: &PadCopyCursor) -> Self {
2278 Self {
2279 coords: CoordScratch::new(cursor.shape.len()),
2280 source_offset: source_base,
2281 dest_offset: dest_base,
2282 }
2283 }
2284
2285 fn decode(
2286 linear: usize,
2287 source_base: isize,
2288 dest_base: isize,
2289 cursor: &PadCopyCursor,
2290 ) -> Result<Self> {
2291 let mut state = Self::new(source_base, dest_base, cursor);
2292 fill_col_major_index(linear, &cursor.shape, state.coords.as_mut_slice());
2293 for axis in 0..cursor.shape.len() {
2294 let coord = state.coords.as_mut_slice()[axis];
2295 state.source_offset =
2296 checked_offset_add(state.source_offset, cursor.source_steps[axis], coord)?;
2297 state.dest_offset =
2298 checked_offset_add(state.dest_offset, cursor.dest_steps[axis], coord)?;
2299 }
2300 Ok(state)
2301 }
2302
2303 #[inline]
2304 fn advance(&mut self, cursor: &PadCopyCursor) {
2305 for axis in 0..cursor.shape.len() {
2309 let next = self.coords.as_mut_slice()[axis] + 1;
2310 if next < cursor.shape[axis] {
2311 self.coords.as_mut_slice()[axis] = next;
2312 self.source_offset += cursor.source_steps[axis];
2313 self.dest_offset += cursor.dest_steps[axis];
2314 return;
2315 }
2316 self.coords.as_mut_slice()[axis] = 0;
2317 self.source_offset += cursor.source_resets[axis];
2318 self.dest_offset += cursor.dest_resets[axis];
2319 }
2320 }
2321}
2322
2323struct CoordScratch {
2324 inline: [usize; crate::RAW_FUSED_RANK_LIMIT],
2325 heap: Option<Vec<usize>>,
2326 len: usize,
2327}
2328
2329impl CoordScratch {
2330 fn new(len: usize) -> Self {
2331 if len <= crate::RAW_FUSED_RANK_LIMIT {
2332 Self {
2333 inline: [0; crate::RAW_FUSED_RANK_LIMIT],
2334 heap: None,
2335 len,
2336 }
2337 } else {
2338 Self {
2339 inline: [0; crate::RAW_FUSED_RANK_LIMIT],
2340 heap: Some(vec![0; len]),
2341 len,
2342 }
2343 }
2344 }
2345
2346 fn as_mut_slice(&mut self) -> &mut [usize] {
2347 match &mut self.heap {
2348 Some(heap) => heap,
2349 None => &mut self.inline[..self.len],
2350 }
2351 }
2352}
2353
2354#[cfg(test)]
2355#[path = "static_indexing_plan/tests/tests.rs"]
2356mod tests;
2357
2358#[cfg(test)]
2359#[path = "static_indexing_plan/tests/parallel_tests.rs"]
2360mod parallel_tests;