1use core::mem::MaybeUninit;
4use std::ops::Mul;
5
6use crate::view::{StridedView, StridedViewMut};
7use crate::{broadcast_mul_into, broadcast_mul_into_uninit, Exec};
8use crate::{ElementOp, Result, StridedError};
9
10type AxisVec<T> = crate::inline::InlineVec<T>;
11
12pub fn batched_outer_product_into<D, A, B, OpA, OpB>(
28 dest: &mut StridedViewMut<D>,
29 lhs: &StridedView<A, OpA>,
30 rhs: &StridedView<B, OpB>,
31 lhs_free_ndim: usize,
32 rhs_free_ndim: usize,
33 exec: Exec<'_>,
34) -> Result<()>
35where
36 D: Copy + Send + Sync + 'static,
37 A: Copy + Send + Sync + Mul<B, Output = D> + 'static,
38 B: Copy + Send + Sync + 'static,
39 OpA: ElementOp<A>,
40 OpB: ElementOp<B>,
41{
42 validate_batched_outer_shape(dest, lhs, rhs, lhs_free_ndim, rhs_free_ndim)?;
43
44 let batch_ndim = lhs.ndim() - lhs_free_ndim;
45 let mut lhs_axes = AxisVec::<usize>::with_capacity(lhs.ndim());
46 let mut rhs_axes = AxisVec::<usize>::with_capacity(rhs.ndim());
47
48 lhs_axes.extend(0..lhs_free_ndim);
49 rhs_axes.extend(lhs_free_ndim..lhs_free_ndim + rhs_free_ndim);
50
51 let batch_axis_start = lhs_free_ndim + rhs_free_ndim;
52 lhs_axes.extend(batch_axis_start..batch_axis_start + batch_ndim);
53 rhs_axes.extend(batch_axis_start..batch_axis_start + batch_ndim);
54
55 broadcast_mul_into(dest, lhs, &lhs_axes, rhs, &rhs_axes, exec)
56}
57
58pub fn batched_outer_product_into_uninit<D, A, B, OpA, OpB>(
79 dest: &mut StridedViewMut<MaybeUninit<D>>,
80 lhs: &StridedView<A, OpA>,
81 rhs: &StridedView<B, OpB>,
82 lhs_free_ndim: usize,
83 rhs_free_ndim: usize,
84 exec: Exec<'_>,
85) -> Result<()>
86where
87 D: Copy + Send + Sync + 'static,
88 A: Copy + Send + Sync + Mul<B, Output = D> + 'static,
89 B: Copy + Send + Sync + 'static,
90 OpA: ElementOp<A>,
91 OpB: ElementOp<B>,
92{
93 validate_batched_outer_shape(dest, lhs, rhs, lhs_free_ndim, rhs_free_ndim)?;
94 let batch_ndim = lhs.ndim() - lhs_free_ndim;
95 let mut lhs_axes = AxisVec::<usize>::with_capacity(lhs.ndim());
96 let mut rhs_axes = AxisVec::<usize>::with_capacity(rhs.ndim());
97 lhs_axes.extend(0..lhs_free_ndim);
98 rhs_axes.extend(lhs_free_ndim..lhs_free_ndim + rhs_free_ndim);
99 let batch_axis_start = lhs_free_ndim + rhs_free_ndim;
100 lhs_axes.extend(batch_axis_start..batch_axis_start + batch_ndim);
101 rhs_axes.extend(batch_axis_start..batch_axis_start + batch_ndim);
102 broadcast_mul_into_uninit(dest, lhs, &lhs_axes, rhs, &rhs_axes, exec)
103}
104
105fn validate_batched_outer_shape<D, A, OpA, B, OpB>(
106 dest: &StridedViewMut<D>,
107 lhs: &StridedView<A, OpA>,
108 rhs: &StridedView<B, OpB>,
109 lhs_free_ndim: usize,
110 rhs_free_ndim: usize,
111) -> Result<()> {
112 if lhs_free_ndim > lhs.ndim() {
113 return Err(StridedError::RankMismatch(lhs_free_ndim, lhs.ndim()));
114 }
115 if rhs_free_ndim > rhs.ndim() {
116 return Err(StridedError::RankMismatch(rhs_free_ndim, rhs.ndim()));
117 }
118
119 let lhs_batch_ndim = lhs.ndim() - lhs_free_ndim;
120 let rhs_batch_ndim = rhs.ndim() - rhs_free_ndim;
121 if lhs_batch_ndim != rhs_batch_ndim {
122 return Err(StridedError::RankMismatch(lhs_batch_ndim, rhs_batch_ndim));
123 }
124
125 let expected_dest_rank = lhs_free_ndim + rhs_free_ndim + lhs_batch_ndim;
126 if dest.ndim() != expected_dest_rank {
127 return Err(StridedError::RankMismatch(dest.ndim(), expected_dest_rank));
128 }
129
130 ensure_dims(&dest.dims()[..lhs_free_ndim], &lhs.dims()[..lhs_free_ndim])?;
131 ensure_dims(
132 &dest.dims()[lhs_free_ndim..lhs_free_ndim + rhs_free_ndim],
133 &rhs.dims()[..rhs_free_ndim],
134 )?;
135 ensure_dims(
136 &dest.dims()[lhs_free_ndim + rhs_free_ndim..],
137 &lhs.dims()[lhs_free_ndim..],
138 )?;
139 ensure_dims(
140 &dest.dims()[lhs_free_ndim + rhs_free_ndim..],
141 &rhs.dims()[rhs_free_ndim..],
142 )?;
143
144 Ok(())
145}
146
147fn ensure_dims(actual: &[usize], expected: &[usize]) -> Result<()> {
148 if actual == expected {
149 Ok(())
150 } else {
151 Err(StridedError::ShapeMismatch(
152 actual.to_vec(),
153 expected.to_vec(),
154 ))
155 }
156}
157
158#[derive(Clone, Debug, PartialEq, Eq)]
167pub struct LazyOuterProductLayout {
168 pub base_dims: Vec<usize>,
170 pub output_strides: Vec<isize>,
172}
173
174pub fn plan_lazy_outer_product(
212 output_dims: &[usize],
213 lhs_dims: &[usize],
214 lhs_strides: &[isize],
215 lhs_axes: &[usize],
216 rhs_dims: &[usize],
217 rhs_strides: &[isize],
218 rhs_axes: &[usize],
219) -> Result<Option<LazyOuterProductLayout>> {
220 for (dims, strides, axes) in [
221 (lhs_dims, lhs_strides, lhs_axes),
222 (rhs_dims, rhs_strides, rhs_axes),
223 ] {
224 if dims.len() != strides.len() {
225 return Err(StridedError::RankMismatch(dims.len(), strides.len()));
226 }
227 if dims.len() != axes.len() {
228 return Err(StridedError::RankMismatch(dims.len(), axes.len()));
229 }
230 }
231 if !extents_match_output(output_dims, lhs_dims, lhs_axes)
232 || !extents_match_output(output_dims, rhs_dims, rhs_axes)
233 || lhs_strides
234 .iter()
235 .chain(rhs_strides)
236 .any(|&stride| stride < 0)
237 {
238 return Ok(None);
239 }
240 let Some(partition) = classify_outer_axes(output_dims.len(), lhs_axes, rhs_axes) else {
241 return Ok(None);
242 };
243 if checked_axes_product(lhs_dims, &partition.lhs_free)? <= 1
244 || checked_axes_product(rhs_dims, &partition.rhs_free)? <= 1
245 {
246 return Ok(None);
247 }
248
249 let output_rank = output_dims.len();
250 let lhs_prefix = partition
251 .lhs_free_out
252 .iter()
253 .chain(&partition.rhs_free_out)
254 .chain(&partition.batch_out)
255 .copied()
256 .eq(0..output_rank);
257 let rhs_prefix = !lhs_prefix
258 && partition
259 .rhs_free_out
260 .iter()
261 .chain(&partition.lhs_free_out)
262 .chain(&partition.batch_out)
263 .copied()
264 .eq(0..output_rank);
265 if !lhs_prefix && !rhs_prefix {
266 return Ok(None);
267 }
268
269 let lhs_physical = axes_by_physical_stride(lhs_strides, &partition.lhs_free);
270 let rhs_physical = axes_by_physical_stride(rhs_strides, &partition.rhs_free);
271 if lhs_physical == partition.lhs_free && rhs_physical == partition.rhs_free {
272 return Ok(None);
273 }
274
275 let mut base_out_axes = Vec::with_capacity(output_rank);
277 let (leading, leading_axes, trailing, trailing_axes) = if lhs_prefix {
278 (&lhs_physical, lhs_axes, &rhs_physical, rhs_axes)
279 } else {
280 (&rhs_physical, rhs_axes, &lhs_physical, lhs_axes)
281 };
282 base_out_axes.extend(leading.iter().map(|&axis| leading_axes[axis]));
283 base_out_axes.extend(trailing.iter().map(|&axis| trailing_axes[axis]));
284 base_out_axes.extend(partition.batch_out.iter().copied());
285
286 let base_dims: Vec<usize> = base_out_axes
287 .iter()
288 .map(|&axis| output_dims[axis])
289 .collect();
290 let mut output_strides = vec![0isize; output_rank];
291 let mut stride = 1isize;
292 for (&out_axis, &extent) in base_out_axes.iter().zip(&base_dims) {
293 output_strides[out_axis] = stride;
296 let extent = isize::try_from(extent).map_err(|_| StridedError::OffsetOverflow)?;
297 stride = stride
298 .checked_mul(extent)
299 .ok_or(StridedError::OffsetOverflow)?;
300 }
301 Ok(Some(LazyOuterProductLayout {
302 base_dims,
303 output_strides,
304 }))
305}
306
307struct OuterAxisPartition {
308 lhs_free_out: Vec<usize>,
309 rhs_free_out: Vec<usize>,
310 batch_out: Vec<usize>,
311 lhs_free: Vec<usize>,
312 rhs_free: Vec<usize>,
313}
314
315fn extents_match_output(output_dims: &[usize], dims: &[usize], axes: &[usize]) -> bool {
316 dims.iter()
317 .zip(axes)
318 .all(|(&dim, &axis)| output_dims.get(axis) == Some(&dim))
319}
320
321fn operand_axes_by_output(axes: &[usize], output_rank: usize) -> Option<Vec<Option<usize>>> {
322 let mut by_output = vec![None; output_rank];
323 for (operand_axis, &output_axis) in axes.iter().enumerate() {
324 if by_output
325 .get_mut(output_axis)?
326 .replace(operand_axis)
327 .is_some()
328 {
329 return None;
330 }
331 }
332 Some(by_output)
333}
334
335fn classify_outer_axes(
336 output_rank: usize,
337 lhs_axes: &[usize],
338 rhs_axes: &[usize],
339) -> Option<OuterAxisPartition> {
340 let lhs_by_output = operand_axes_by_output(lhs_axes, output_rank)?;
341 let rhs_by_output = operand_axes_by_output(rhs_axes, output_rank)?;
342 let mut partition = OuterAxisPartition {
343 lhs_free_out: Vec::new(),
344 rhs_free_out: Vec::new(),
345 batch_out: Vec::new(),
346 lhs_free: Vec::new(),
347 rhs_free: Vec::new(),
348 };
349 for output_axis in 0..output_rank {
350 match (lhs_by_output[output_axis], rhs_by_output[output_axis]) {
351 (Some(_), Some(_)) => partition.batch_out.push(output_axis),
352 (Some(lhs_axis), None) => {
353 partition.lhs_free_out.push(output_axis);
354 partition.lhs_free.push(lhs_axis);
355 }
356 (None, Some(rhs_axis)) => {
357 partition.rhs_free_out.push(output_axis);
358 partition.rhs_free.push(rhs_axis);
359 }
360 (None, None) => return None,
361 }
362 }
363 Some(partition)
364}
365
366fn checked_axes_product(dims: &[usize], axes: &[usize]) -> Result<usize> {
367 if axes.iter().any(|&axis| dims[axis] == 0) {
370 return Ok(0);
371 }
372 axes.iter().try_fold(1usize, |acc, &axis| {
373 acc.checked_mul(dims[axis])
374 .ok_or(StridedError::OffsetOverflow)
375 })
376}
377
378fn axes_by_physical_stride(strides: &[isize], axes: &[usize]) -> Vec<usize> {
379 let mut sorted = axes.to_vec();
380 sorted.sort_by(|&lhs, &rhs| strides[lhs].cmp(&strides[rhs]).then(lhs.cmp(&rhs)));
381 sorted
382}