1#![cfg_attr(docsrs, feature(doc_cfg))]
117
118use std::any::Any;
119use std::hash::Hasher;
120use std::num::NonZeroUsize;
121use std::sync::Arc;
122
123#[cfg(feature = "autodiff")]
124use tenferro_ad::semantic_extension::{
125 AdValue, ResidualSpec, SemanticAdError, SemanticExtensionRegistryError,
126 SemanticExtensionRuleSet, SemanticLinearTransposeRequest, SemanticLinearTransposeRule,
127 SemanticLinearizeRequest, SemanticLinearizeResult, SemanticLinearizeRule,
128 SemanticPrimalVjpRequest, SemanticPrimalVjpRule,
129};
130use tenferro_cpu::with_cpu_engine;
131use tenferro_extension_macros::define_extension_runtime;
132#[cfg(feature = "cuda")]
133use tenferro_gpu::cuda::raw::with_cuda_engine;
134#[cfg(feature = "cuda")]
135use tenferro_gpu::cuda::CudaEngine;
136use tenferro_ops::SymDim;
137use tenferro_runtime::extension::{
138 apply, ExtensionCacheStore, ExtensionExecutionContext, ExtensionOp,
139};
140#[cfg(feature = "autodiff")]
141use tenferro_runtime::program::{CoreSemanticOp, ProgramValue, SemanticProgramBuilder};
142use tenferro_runtime::{Error, ErrorPhase, Result, TracedTensor};
143use tenferro_tensor::{CacheStats, DType, Engine, ErrorKind, Tensor, TensorRead};
144
145mod api;
146mod backend;
147mod cache;
148mod cpu;
149#[cfg(feature = "cuda")]
150mod cuda;
151#[cfg(feature = "autodiff")]
152mod eager_ext;
153#[cfg(feature = "autodiff")]
154mod eager_in_place;
155pub mod prelude;
156mod spec;
157
158#[cfg(feature = "autodiff")]
159#[cfg_attr(docsrs, doc(cfg(feature = "autodiff")))]
160pub use api::EagerFftOps;
161pub use api::{FftOps, FftOptions, FftRepr, FftScalar, FftnOptions, TracedFftOps};
162pub use backend::{FftBackend, FftExecutionCache};
163pub use cache::{
164 fft_plan_cache_selector, FftPlanCache, DEFAULT_FFT_PLAN_CACHE_CAPACITY, FFT_PLAN_CACHE_NAME,
165};
166#[cfg(feature = "autodiff")]
167#[cfg_attr(docsrs, doc(cfg(feature = "autodiff")))]
168pub use eager_in_place::EagerFftInPlaceError;
169pub use spec::{FftNorm, FftOperation, FftPlanSpec};
170
171pub const FFT_EXTENSION_FAMILY_ID: &str = "tenferro-fft.fft.v1";
182
183#[derive(Default)]
190pub struct FftExecutor {
191 plans: FftPlanCache,
192}
193
194impl FftExecutor {
195 pub fn new(plans: FftPlanCache) -> Self {
197 Self { plans }
198 }
199
200 pub const fn plan_cache(&self) -> &FftPlanCache {
202 &self.plans
203 }
204
205 pub fn plan_cache_mut(&mut self) -> &mut FftPlanCache {
207 &mut self.plans
208 }
209
210 pub fn cache_stats(&self) -> CacheStats {
212 self.plans.stats()
213 }
214
215 pub fn clear_cache(&mut self) {
217 self.plans.clear();
218 }
219
220 fn one_axis_with(
221 &mut self,
222 op: &'static str,
223 operation_of: fn(&'static str, DType) -> tenferro_tensor::Result<FftOperation>,
224 input: &Tensor,
225 opts: &FftOptions,
226 exec: &mut dyn Engine,
227 ) -> tenferro_tensor::Result<Tensor> {
228 self.execute(
229 input,
230 operation_of(op, input.dtype())?,
231 op,
232 opts.n,
233 opts.axis,
234 opts.norm,
235 exec,
236 )
237 }
238
239 fn n_axes_with(
240 &mut self,
241 op: &'static str,
242 operation_of: fn(&'static str, DType) -> tenferro_tensor::Result<FftOperation>,
243 input: &Tensor,
244 opts: &FftnOptions,
245 exec: &mut dyn Engine,
246 ) -> tenferro_tensor::Result<Tensor> {
247 let axes = opts.resolved_axes(input.shape().len());
248 self.execute_nd(
249 op,
250 operation_of(op, input.dtype())?,
251 input,
252 opts.shape.as_deref(),
253 &axes,
254 opts.norm,
255 exec,
256 )
257 }
258
259 pub fn fft_with(
284 &mut self,
285 input: &Tensor,
286 opts: &FftOptions,
287 exec: &mut dyn Engine,
288 ) -> tenferro_tensor::Result<Tensor> {
289 self.one_axis_with(
290 "FftExecutor::fft_with",
291 concrete_fft_operation,
292 input,
293 opts,
294 exec,
295 )
296 }
297
298 pub fn ifft_with(
324 &mut self,
325 input: &Tensor,
326 opts: &FftOptions,
327 exec: &mut dyn Engine,
328 ) -> tenferro_tensor::Result<Tensor> {
329 self.one_axis_with(
330 "FftExecutor::ifft_with",
331 concrete_ifft_operation,
332 input,
333 opts,
334 exec,
335 )
336 }
337
338 pub fn rfft_with(
360 &mut self,
361 input: &Tensor,
362 opts: &FftOptions,
363 exec: &mut dyn Engine,
364 ) -> tenferro_tensor::Result<Tensor> {
365 self.one_axis_with(
366 "FftExecutor::rfft_with",
367 concrete_rfft_operation,
368 input,
369 opts,
370 exec,
371 )
372 }
373
374 pub fn irfft_with(
400 &mut self,
401 input: &Tensor,
402 opts: &FftOptions,
403 exec: &mut dyn Engine,
404 ) -> tenferro_tensor::Result<Tensor> {
405 self.one_axis_with(
406 "FftExecutor::irfft_with",
407 concrete_irfft_operation,
408 input,
409 opts,
410 exec,
411 )
412 }
413
414 pub fn fftn_with(
437 &mut self,
438 input: &Tensor,
439 opts: &FftnOptions,
440 exec: &mut dyn Engine,
441 ) -> tenferro_tensor::Result<Tensor> {
442 self.n_axes_with(
443 "FftExecutor::fftn_with",
444 concrete_fft_operation,
445 input,
446 opts,
447 exec,
448 )
449 }
450
451 pub fn ifftn_with(
474 &mut self,
475 input: &Tensor,
476 opts: &FftnOptions,
477 exec: &mut dyn Engine,
478 ) -> tenferro_tensor::Result<Tensor> {
479 self.n_axes_with(
480 "FftExecutor::ifftn_with",
481 concrete_ifft_operation,
482 input,
483 opts,
484 exec,
485 )
486 }
487
488 pub fn rfftn_with(
510 &mut self,
511 input: &Tensor,
512 opts: &FftnOptions,
513 exec: &mut dyn Engine,
514 ) -> tenferro_tensor::Result<Tensor> {
515 self.n_axes_with(
516 "FftExecutor::rfftn_with",
517 concrete_rfft_operation,
518 input,
519 opts,
520 exec,
521 )
522 }
523
524 pub fn irfftn_with(
549 &mut self,
550 input: &Tensor,
551 opts: &FftnOptions,
552 exec: &mut dyn Engine,
553 ) -> tenferro_tensor::Result<Tensor> {
554 self.n_axes_with(
555 "FftExecutor::irfftn_with",
556 concrete_irfft_operation,
557 input,
558 opts,
559 exec,
560 )
561 }
562
563 #[allow(clippy::too_many_arguments)]
566 fn execute_nd(
567 &mut self,
568 op_name: &'static str,
569 operation: FftOperation,
570 input: &Tensor,
571 shape: Option<&[usize]>,
572 axes: &[isize],
573 norm: FftNorm,
574 session: &mut dyn Engine,
575 ) -> tenferro_tensor::Result<Tensor> {
576 let fft_op = validated_fft_op(
577 op_name,
578 operation,
579 Some(input.dtype()),
580 input.shape().len(),
581 Some(input.shape()),
582 shape,
583 "shape",
584 axes,
585 norm,
586 )?;
587 with_fft_exec_session(session, op_name, |backend| {
588 execute_fft_op(
589 &fft_op,
590 &TensorRead::Tensor(input),
591 backend,
592 FftExecutionCache::caller_owned(&mut self.plans),
593 )
594 })
595 }
596
597 #[allow(clippy::too_many_arguments)]
598 fn execute(
599 &mut self,
600 input: &Tensor,
601 operation: FftOperation,
602 op_name: &'static str,
603 n: Option<usize>,
604 axis: isize,
605 norm: FftNorm,
606 session: &mut dyn Engine,
607 ) -> tenferro_tensor::Result<Tensor> {
608 let spec = concrete_fft_spec(
609 op_name,
610 operation,
611 input.dtype(),
612 input.shape(),
613 n,
614 axis,
615 norm,
616 )?;
617 with_fft_exec_session(session, op_name, |backend| {
621 backend.execute_fft(
622 input,
623 &spec,
624 FftExecutionCache::caller_owned(&mut self.plans),
625 )
626 })
627 }
628}
629
630#[derive(Debug, thiserror::Error)]
631enum FftError {
632 #[error("{op} does not support dtype {dtype:?}; expected {expected}")]
633 UnsupportedDType {
634 op: &'static str,
635 dtype: DType,
636 expected: &'static str,
637 },
638}
639
640#[derive(Clone, Debug, PartialEq)]
641struct FftOp {
642 operation: FftOperation,
643 axes: Vec<usize>,
646 lengths: Option<Vec<usize>>,
648 norm: FftNorm,
649}
650
651impl FftOp {
652 fn new(
653 operation: FftOperation,
654 axes: Vec<usize>,
655 lengths: Option<Vec<usize>>,
656 norm: FftNorm,
657 ) -> Self {
658 Self {
659 operation,
660 axes,
661 lengths,
662 norm,
663 }
664 }
665
666 fn spec(&self, dtype: DType, shape: &[usize]) -> FftPlanSpec {
668 FftPlanSpec::new(
669 self.operation,
670 self.axes.clone(),
671 self.lengths.clone(),
672 self.norm,
673 dtype,
674 shape.to_vec(),
675 )
676 }
677
678 fn step_spec(&self, index: usize, dtype: DType, shape: &[usize]) -> FftPlanSpec {
680 FftPlanSpec::new(
681 self.operation.step_operation(index, self.axes.len()),
682 vec![self.axes[index]],
683 self.lengths.as_ref().map(|lengths| vec![lengths[index]]),
684 self.norm,
685 dtype,
686 shape.to_vec(),
687 )
688 }
689
690 fn execution_order(&self) -> Vec<usize> {
697 let mut order: Vec<usize> = (0..self.axes.len()).collect();
698 if matches!(
699 self.operation,
700 FftOperation::R2cFull | FftOperation::R2cOnesided
701 ) {
702 order.rotate_right(1);
703 }
704 order
705 }
706
707 #[cfg(feature = "autodiff")]
708 fn c2c_adjoint(&self) -> Option<Self> {
709 let operation = match self.operation {
710 FftOperation::C2cForward => FftOperation::C2cInverse,
711 FftOperation::C2cInverse => FftOperation::C2cForward,
712 FftOperation::R2cFull | FftOperation::R2cOnesided | FftOperation::C2r => return None,
713 };
714 Some(Self {
715 operation,
716 axes: self.axes.clone(),
717 lengths: self.lengths.clone(),
718 norm: self.norm.c2c_adjoint(),
719 })
720 }
721}
722
723impl ExtensionOp for FftOp {
724 fn family_id(&self) -> &'static str {
725 FFT_EXTENSION_FAMILY_ID
726 }
727
728 fn payload_hash(&self, hasher: &mut dyn Hasher) {
729 let operation = match self.operation {
730 FftOperation::C2cForward => 0,
731 FftOperation::C2cInverse => 1,
732 FftOperation::R2cOnesided => 2,
733 FftOperation::R2cFull => 3,
734 FftOperation::C2r => 4,
735 };
736 hasher.write_u8(operation);
737 hasher.write_usize(self.axes.len());
738 for axis in &self.axes {
739 hasher.write_usize(*axis);
740 }
741 match &self.lengths {
742 Some(lengths) => {
743 hasher.write_u8(1);
744 for len in lengths {
745 hasher.write_usize(*len);
746 }
747 }
748 None => hasher.write_u8(0),
749 }
750 let norm = match self.norm {
751 FftNorm::Backward => 0,
752 FftNorm::Forward => 1,
753 FftNorm::Ortho => 2,
754 };
755 hasher.write_u8(norm);
756 }
757
758 fn payload_eq(&self, other: &dyn ExtensionOp) -> bool {
759 other
760 .as_any()
761 .downcast_ref::<FftOp>()
762 .is_some_and(|that| self == that)
763 }
764
765 fn clone_arc(&self) -> Arc<dyn ExtensionOp> {
766 Arc::new(self.clone())
767 }
768
769 fn as_any(&self) -> &dyn Any {
770 self
771 }
772
773 fn input_count(&self) -> usize {
774 1
775 }
776
777 fn output_count(&self) -> usize {
778 1
779 }
780
781 fn semantic_effects(&self) -> tenferro_ops::ext_op::ExtensionEffectDeclaration<'_> {
782 tenferro_ops::ext_op::ExtensionEffectDeclaration::Declared(&[])
783 }
784
785 fn semantic_aliases(&self) -> tenferro_ops::ext_op::ExtensionAliasDeclaration<'_> {
786 tenferro_ops::ext_op::ExtensionAliasDeclaration::AllFresh
787 }
788
789 fn infer_output_meta(
790 &self,
791 ctx: &mut tenferro_ops::ExtensionShapeContext<'_>,
792 ) -> tenferro_tensor::Result<Vec<(DType, Vec<SymDim>)>> {
793 let input_dtype = ctx.input_dtype(0)?;
794 let input_shape = ctx.input_shape(0)?;
795 let output_dtype = match self.operation {
796 FftOperation::C2cForward | FftOperation::C2cInverse => {
797 if !matches!(input_dtype, DType::C32 | DType::C64) {
798 return Err(tensor_unsupported_dtype(
799 "tenferro-fft",
800 input_dtype,
801 "C32 or C64",
802 ));
803 }
804 input_dtype
805 }
806 FftOperation::R2cFull | FftOperation::R2cOnesided => match input_dtype {
807 DType::F32 => DType::C32,
808 DType::F64 => DType::C64,
809 _ => {
810 return Err(tensor_unsupported_dtype(
811 "tenferro-fft",
812 input_dtype,
813 "F32 or F64",
814 ));
815 }
816 },
817 FftOperation::C2r => match input_dtype {
818 DType::C32 => DType::F32,
819 DType::C64 => DType::F64,
820 _ => {
821 return Err(tensor_unsupported_dtype(
822 "tenferro-fft",
823 input_dtype,
824 "C32 or C64",
825 ));
826 }
827 },
828 };
829
830 let count = self.axes.len();
831 let mut out_shape = input_shape.to_vec();
832 for (index, &axis) in self.axes.iter().enumerate() {
833 if axis >= input_shape.len() {
834 return Err(tenferro_tensor::Error::axis_out_of_bounds(
835 "tenferro-fft",
836 axis,
837 input_shape.len(),
838 ));
839 }
840 let len = self.lengths.as_ref().map(|lengths| lengths[index]);
841 out_shape[axis] = match self.operation.step_operation(index, count) {
842 FftOperation::C2cForward | FftOperation::C2cInverse => {
843 transform_len_dim(len, &input_shape[axis])?
844 }
845 FftOperation::R2cFull | FftOperation::R2cOnesided => {
846 let len = transform_len_dim(len, &input_shape[axis])?;
847 if self.operation.is_onesided() {
848 len / 2usize + 1usize
849 } else {
850 len
851 }
852 }
853 FftOperation::C2r => output_dim_c2r(&input_shape[axis], len)?,
854 };
855 }
856
857 Ok(vec![(output_dtype, out_shape)])
858 }
859}
860
861fn with_fft_exec_session<X>(
870 session: &mut dyn Engine,
871 op: &'static str,
872 f: impl FnOnce(&mut dyn FftBackend) -> tenferro_tensor::Result<X>,
873) -> tenferro_tensor::Result<X> {
874 if with_cpu_engine(session, |_| ()).is_some() {
879 return with_cpu_engine(session, |exec| f(exec as &mut dyn FftBackend))
880 .expect("marker probe matched a CPU execution session");
881 }
882 #[cfg(feature = "cuda")]
883 if with_cuda_engine(session, |_| ()).is_some() {
884 return with_cuda_engine(session, |exec| f(exec as &mut dyn FftBackend))
885 .expect("marker probe matched a CUDA execution session");
886 }
887 Err(tenferro_tensor::Error::unsupported(
888 op,
889 "selected backend session does not expose an FFT execution capability",
890 ))
891}
892
893fn execute_concrete_fft_op(
894 input: &Tensor,
895 spec: &FftPlanSpec,
896 backend: &mut dyn FftBackend,
897) -> tenferro_tensor::Result<Tensor> {
898 let mut plans = FftPlanCache::with_capacity(NonZeroUsize::MIN);
899 backend.execute_fft(input, spec, FftExecutionCache::caller_owned(&mut plans))
900}
901
902#[allow(clippy::too_many_arguments)]
903fn execute_concrete_fft_read_op(
904 input: &TensorRead<'_>,
905 operation: FftOperation,
906 op_name: &'static str,
907 n: Option<usize>,
908 axis: isize,
909 norm: FftNorm,
910 backend: &mut dyn FftBackend,
911) -> tenferro_tensor::Result<Tensor> {
912 let spec = concrete_fft_spec(
913 op_name,
914 operation,
915 input.dtype(),
916 input.shape(),
917 n,
918 axis,
919 norm,
920 )?;
921 let mut plans = FftPlanCache::with_capacity(NonZeroUsize::MIN);
922 backend.execute_fft_read(
923 input.clone(),
924 &spec,
925 FftExecutionCache::caller_owned(&mut plans),
926 )
927}
928
929#[allow(clippy::too_many_arguments)]
930fn concrete_fft_spec(
931 op: &'static str,
932 operation: FftOperation,
933 input_dtype: DType,
934 input_shape: &[usize],
935 n: Option<usize>,
936 axis: isize,
937 norm: FftNorm,
938) -> tenferro_tensor::Result<FftPlanSpec> {
939 validated_fft_plan_spec(
940 op,
941 operation,
942 input_dtype,
943 input_shape,
944 n.map(|n| [n]).as_ref().map(<[usize; 1]>::as_slice),
945 &[axis],
946 norm,
947 )
948}
949
950#[allow(clippy::too_many_arguments)]
958fn validated_fft_op(
959 op: &'static str,
960 operation: FftOperation,
961 dtype: Option<DType>,
962 input_rank: usize,
963 input_shape: Option<&[usize]>,
964 lengths: Option<&[usize]>,
965 length_argument: &'static str,
966 axes: &[isize],
967 norm: FftNorm,
968) -> tenferro_tensor::Result<FftOp> {
969 if input_rank == 0 {
970 return Err(tenferro_tensor::Error::invalid_argument(
971 op,
972 "rank",
973 "FFT requires rank >= 1",
974 ));
975 }
976 if axes.is_empty() {
977 return Err(tenferro_tensor::Error::invalid_argument(
978 op,
979 "axes",
980 "FFT requires at least one axis",
981 ));
982 }
983 let mut normalized = Vec::with_capacity(axes.len());
984 for &axis in axes {
985 let axis = normalize_axis(op, axis, input_rank)?;
986 if normalized.contains(&axis) {
987 return Err(tenferro_tensor::Error::invalid_argument(
988 op,
989 "axes",
990 format!("axis {axis} is repeated"),
991 ));
992 }
993 normalized.push(axis);
994 }
995 if let Some(lengths) = lengths {
996 if lengths.len() != normalized.len() {
997 return Err(tenferro_tensor::Error::invalid_argument(
998 op,
999 length_argument,
1000 format!(
1001 "expected {} requested lengths for {} axes, got {}",
1002 normalized.len(),
1003 normalized.len(),
1004 lengths.len()
1005 ),
1006 ));
1007 }
1008 if lengths.contains(&0) {
1009 return Err(tenferro_tensor::Error::invalid_argument(
1010 op,
1011 length_argument,
1012 "transform length must be positive",
1013 ));
1014 }
1015 }
1016 if let Some(dtype) = dtype {
1017 validate_operation_dtype(op, operation, dtype)?;
1018 }
1019 let count = normalized.len();
1020 if let Some(shape) = input_shape {
1021 for (index, &axis) in normalized.iter().enumerate() {
1022 let len = lengths.map(|lengths| lengths[index]);
1023 if len.is_none() && shape[axis] == 0 {
1024 return Err(tenferro_tensor::Error::invalid_argument(
1025 op,
1026 length_argument,
1027 "transform length must be positive",
1028 ));
1029 }
1030 match operation.step_operation(index, count) {
1031 FftOperation::C2cForward | FftOperation::C2cInverse => {
1032 transform_len(shape, axis, len)?;
1033 }
1034 FftOperation::R2cFull | FftOperation::R2cOnesided => {
1035 transform_len(shape, axis, len)?;
1036 }
1037 FftOperation::C2r => {
1038 output_shape_c2r(shape, axis, len)?;
1039 }
1040 }
1041 }
1042 }
1043 Ok(FftOp::new(
1044 operation,
1045 normalized,
1046 lengths.map(<[usize]>::to_vec),
1047 norm,
1048 ))
1049}
1050
1051#[allow(clippy::too_many_arguments)]
1052fn validated_fft_plan_spec(
1053 op: &'static str,
1054 operation: FftOperation,
1055 input_dtype: DType,
1056 input_shape: &[usize],
1057 lengths: Option<&[usize]>,
1058 axes: &[isize],
1059 norm: FftNorm,
1060) -> tenferro_tensor::Result<FftPlanSpec> {
1061 let fft_op = validated_fft_op(
1062 op,
1063 operation,
1064 Some(input_dtype),
1065 input_shape.len(),
1066 Some(input_shape),
1067 lengths,
1068 "n",
1069 axes,
1070 norm,
1071 )?;
1072 Ok(fft_op.spec(input_dtype, input_shape))
1073}
1074
1075fn concrete_fft_operation(op: &'static str, dtype: DType) -> tenferro_tensor::Result<FftOperation> {
1076 match dtype {
1077 DType::C32 | DType::C64 => Ok(FftOperation::C2cForward),
1078 DType::F32 | DType::F64 => Ok(FftOperation::R2cFull),
1079 DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1080 Err(tensor_unsupported_dtype(op, dtype, "F32, F64, C32, or C64"))
1081 }
1082 }
1083}
1084
1085fn concrete_ifft_operation(
1086 op: &'static str,
1087 dtype: DType,
1088) -> tenferro_tensor::Result<FftOperation> {
1089 match dtype {
1090 DType::C32 | DType::C64 => Ok(FftOperation::C2cInverse),
1091 DType::F32 | DType::F64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1092 Err(tensor_unsupported_dtype(op, dtype, "C32 or C64"))
1093 }
1094 }
1095}
1096
1097fn concrete_rfft_operation(
1098 op: &'static str,
1099 dtype: DType,
1100) -> tenferro_tensor::Result<FftOperation> {
1101 match dtype {
1102 DType::F32 | DType::F64 => Ok(FftOperation::R2cOnesided),
1103 DType::C32 | DType::C64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1104 Err(tensor_unsupported_dtype(op, dtype, "F32 or F64"))
1105 }
1106 }
1107}
1108
1109fn concrete_irfft_operation(
1110 op: &'static str,
1111 dtype: DType,
1112) -> tenferro_tensor::Result<FftOperation> {
1113 match dtype {
1114 DType::C32 | DType::C64 => Ok(FftOperation::C2r),
1115 DType::F32 | DType::F64 | DType::I32 | DType::I64 | DType::Bool | DType::External(_) => {
1116 Err(tensor_unsupported_dtype(op, dtype, "C32 or C64"))
1117 }
1118 }
1119}
1120
1121fn validate_operation_dtype(
1122 op: &'static str,
1123 operation: FftOperation,
1124 dtype: DType,
1125) -> tenferro_tensor::Result<()> {
1126 let supported = match operation {
1127 FftOperation::C2cForward | FftOperation::C2cInverse | FftOperation::C2r => {
1128 matches!(dtype, DType::C32 | DType::C64)
1129 }
1130 FftOperation::R2cFull | FftOperation::R2cOnesided => {
1131 matches!(dtype, DType::F32 | DType::F64)
1132 }
1133 };
1134 if supported {
1135 Ok(())
1136 } else {
1137 Err(tensor_unsupported_dtype(
1138 op,
1139 dtype,
1140 expected_dtype_description(operation),
1141 ))
1142 }
1143}
1144
1145fn tensor_unsupported_dtype(
1146 op: &'static str,
1147 dtype: DType,
1148 expected: &'static str,
1149) -> tenferro_tensor::Error {
1150 tenferro_tensor::Error::extension(
1151 op,
1152 FFT_EXTENSION_FAMILY_ID,
1153 ErrorKind::Unsupported,
1154 FftError::UnsupportedDType {
1155 op,
1156 dtype,
1157 expected,
1158 },
1159 )
1160}
1161
1162#[cfg(feature = "autodiff")]
1163#[derive(Debug)]
1164struct FftAdRule;
1165
1166#[cfg(feature = "autodiff")]
1167impl SemanticLinearizeRule for FftAdRule {
1168 fn family_id(&self) -> &'static str {
1169 FFT_EXTENSION_FAMILY_ID
1170 }
1171
1172 fn linearize(
1173 &self,
1174 request: SemanticLinearizeRequest<'_>,
1175 builder: &mut SemanticProgramBuilder,
1176 ) -> std::result::Result<SemanticLinearizeResult, SemanticAdError> {
1177 let fft_op = semantic_fft_payload(request.op(), SemanticAdRuleKind::Linearize)?;
1178 if !fft_op.operation.is_c2c() {
1179 return Err(semantic_fft_unsupported(
1180 fft_op.operation,
1181 SemanticAdRuleKind::Linearize,
1182 ));
1183 }
1184 let tangent = match request.tangent_inputs()[0] {
1185 AdValue::Absent => AdValue::Absent,
1186 AdValue::Value(tangent) => {
1187 AdValue::Value(builder.add_extension(Arc::new(fft_op.clone()), &[tangent])?[0])
1188 }
1189 };
1190 Ok(SemanticLinearizeResult::new([tangent], []))
1191 }
1192}
1193
1194#[cfg(feature = "autodiff")]
1195impl SemanticLinearTransposeRule for FftAdRule {
1196 fn family_id(&self) -> &'static str {
1197 FFT_EXTENSION_FAMILY_ID
1198 }
1199
1200 fn residual_mask(&self) -> ResidualSpec {
1201 ResidualSpec::input(0)
1204 }
1205
1206 fn linear_transpose(
1207 &self,
1208 request: SemanticLinearTransposeRequest<'_>,
1209 builder: &mut SemanticProgramBuilder,
1210 ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
1211 Ok([semantic_fft_adjoint(
1212 request.op(),
1213 request.cotangent_outputs()[0],
1214 request.active_inputs()[0],
1215 request.primal_input_value(0)?,
1216 request.residual_mask(),
1217 builder,
1218 )?]
1219 .into())
1220 }
1221}
1222
1223#[cfg(feature = "autodiff")]
1224impl SemanticPrimalVjpRule for FftAdRule {
1225 fn family_id(&self) -> &'static str {
1226 FFT_EXTENSION_FAMILY_ID
1227 }
1228
1229 fn residual_mask(&self) -> ResidualSpec {
1230 ResidualSpec::input(0)
1231 }
1232
1233 fn primal_vjp(
1234 &self,
1235 request: SemanticPrimalVjpRequest<'_>,
1236 builder: &mut SemanticProgramBuilder,
1237 ) -> std::result::Result<Box<[AdValue]>, SemanticAdError> {
1238 Ok([semantic_fft_adjoint(
1239 request.op(),
1240 request.cotangent_outputs()[0],
1241 request.active_inputs()[0],
1242 request.primal_input_value(0)?,
1243 request.residual_mask(),
1244 builder,
1245 )?]
1246 .into())
1247 }
1248}
1249
1250#[cfg(feature = "autodiff")]
1251#[derive(Clone, Copy)]
1252enum SemanticAdRuleKind {
1253 Linearize,
1254 Transpose,
1255}
1256
1257#[cfg(feature = "autodiff")]
1258fn semantic_fft_payload(
1259 op: &dyn ExtensionOp,
1260 role: SemanticAdRuleKind,
1261) -> std::result::Result<&FftOp, SemanticAdError> {
1262 op.as_any().downcast_ref::<FftOp>().ok_or_else(|| {
1263 semantic_fft_unsupported_family(
1264 FFT_EXTENSION_FAMILY_ID,
1265 role,
1266 "FFT semantic AD received an incompatible extension payload",
1267 )
1268 })
1269}
1270
1271#[cfg(feature = "autodiff")]
1272fn semantic_fft_adjoint(
1273 op: &dyn ExtensionOp,
1274 cotangent: AdValue,
1275 active: bool,
1276 primal_input: ProgramValue,
1277 residual_mask: ResidualSpec,
1278 builder: &mut SemanticProgramBuilder,
1279) -> std::result::Result<AdValue, SemanticAdError> {
1280 if !active {
1281 return Ok(AdValue::Absent);
1282 }
1283 let AdValue::Value(cotangent) = cotangent else {
1284 return Ok(AdValue::Absent);
1285 };
1286 let fft_op = semantic_fft_payload(op, SemanticAdRuleKind::Transpose)?;
1287 if !fft_op.operation.is_c2c() {
1288 return Err(semantic_fft_unsupported(
1289 fft_op.operation,
1290 SemanticAdRuleKind::Transpose,
1291 ));
1292 }
1293 let adjoint_op = fft_op
1294 .c2c_adjoint()
1295 .ok_or_else(|| semantic_fft_unsupported(fft_op.operation, SemanticAdRuleKind::Transpose))?;
1296 let adjoint = builder.add_extension(Arc::new(adjoint_op), &[cotangent])?[0];
1297 restore_semantic_c2c_adjoint_input_length(builder, adjoint, primal_input, residual_mask, fft_op)
1298 .map(AdValue::Value)
1299}
1300
1301#[cfg(feature = "autodiff")]
1302fn restore_semantic_c2c_adjoint_input_length(
1303 builder: &mut SemanticProgramBuilder,
1304 adjoint: ProgramValue,
1305 primal_input: ProgramValue,
1306 residual_mask: ResidualSpec,
1307 fft_op: &FftOp,
1308) -> std::result::Result<ProgramValue, SemanticAdError> {
1309 let Some(lengths) = fft_op.lengths.as_ref() else {
1310 return Ok(adjoint);
1311 };
1312 debug_assert!(
1313 residual_mask.declares_input(0),
1314 "fft transpose read primal input 0 as a tensor operand but the residual mask does not \
1315 declare it; declare it in the fft rule's residual mask"
1316 );
1317 let mut adjoint = adjoint;
1318 for (&axis, &transform_len) in fft_op.axes.iter().zip(lengths) {
1319 let input_len = builder
1320 .value_metadata(primal_input)?
1321 .shape()
1322 .get(axis)
1323 .and_then(|extent| extent.as_exact())
1324 .and_then(|dim| match dim {
1325 tenferro_ops::dim_expr::DimExpr::Const(value) => Some(*value),
1326 _ => None,
1327 });
1328 if input_len == Some(transform_len) {
1329 continue;
1330 }
1331
1332 let size = builder.add_op(CoreSemanticOp::ShapeOf { axis }, &[primal_input])?[0];
1333 let truncated =
1334 builder.add_op(CoreSemanticOp::DynamicTruncate { axis }, &[adjoint, size])?[0];
1335 adjoint = builder.add_op(
1336 CoreSemanticOp::PadToMatch { axis },
1337 &[truncated, primal_input],
1338 )?[0];
1339 }
1340 Ok(adjoint)
1341}
1342
1343#[cfg(feature = "autodiff")]
1344fn semantic_fft_unsupported(operation: FftOperation, role: SemanticAdRuleKind) -> SemanticAdError {
1345 semantic_fft_unsupported_family(
1346 fft_ad_family_id(operation),
1347 role,
1348 "FFT operation has no semantic AD rule",
1349 )
1350}
1351
1352#[cfg(feature = "autodiff")]
1353fn semantic_fft_unsupported_family(
1354 family_id: &'static str,
1355 role: SemanticAdRuleKind,
1356 message: impl Into<String>,
1357) -> SemanticAdError {
1358 SemanticAdError::Unsupported {
1359 family_id,
1360 role: match role {
1361 SemanticAdRuleKind::Linearize => {
1362 tenferro_ad::semantic_extension::SemanticAdRuleRole::Linearize
1363 }
1364 SemanticAdRuleKind::Transpose => {
1365 tenferro_ad::semantic_extension::SemanticAdRuleRole::LinearTranspose
1366 }
1367 },
1368 message: message.into(),
1369 }
1370}
1371
1372#[cfg(feature = "autodiff")]
1374pub fn semantic_ad_rules(
1382) -> std::result::Result<SemanticExtensionRuleSet, SemanticExtensionRegistryError> {
1383 SemanticExtensionRuleSet::new()
1384 .with_linearize(Arc::new(FftAdRule))?
1385 .with_linear_transpose(Arc::new(FftAdRule))?
1386 .with_primal_vjp(Arc::new(FftAdRule))
1387}
1388
1389pub(crate) fn execute_fft_extension_reads_session(
1390 op: &FftOp,
1391 inputs: &[TensorRead<'_>],
1392 ctx: &mut ExtensionExecutionContext<'_, dyn Engine + '_>,
1393) -> tenferro_tensor::Result<Vec<Tensor>> {
1394 let (session, caches) = ctx.parts_mut();
1395 execute_fft_extension_reads_on_session(op, inputs, session, caches)
1396}
1397
1398fn execute_fft_extension_reads_for_capability<B: FftBackend + ?Sized>(
1399 op: &FftOp,
1400 inputs: &[TensorRead<'_>],
1401 session: &mut B,
1402 caches: &mut ExtensionCacheStore,
1403) -> tenferro_tensor::Result<Vec<Tensor>> {
1404 if inputs.len() != 1 {
1405 return Err(tenferro_tensor::Error::invalid_argument(
1406 "tenferro-fft",
1407 "inputs",
1408 format!("expected 1 input, got {}", inputs.len()),
1409 ));
1410 }
1411 Ok(vec![execute_fft_op(
1412 op,
1413 &inputs[0],
1414 session,
1415 FftExecutionCache::engine_owned(caches),
1416 )?])
1417}
1418
1419fn execute_fft_op<B: FftBackend + ?Sized>(
1429 op: &FftOp,
1430 input: &TensorRead<'_>,
1431 session: &mut B,
1432 mut cache: FftExecutionCache<'_>,
1433) -> tenferro_tensor::Result<Tensor> {
1434 let mut current: Option<Tensor> = None;
1435 for index in op.execution_order() {
1436 let (dtype, shape) = match ¤t {
1437 Some(tensor) => (tensor.dtype(), tensor.shape().to_vec()),
1438 None => (input.dtype(), input.shape().to_vec()),
1439 };
1440 let spec = op.step_spec(index, dtype, &shape);
1441 let step_name = fft_op_name(spec.operation());
1442 let read = match ¤t {
1443 Some(tensor) => TensorRead::Tensor(tensor),
1444 None => input.clone(),
1445 };
1446 if matches!(&read, TensorRead::View(_)) {
1450 session.validate_fft_read_input(step_name, &read)?;
1451 }
1452 let output = session.execute_fft_read(
1453 read,
1454 &spec,
1455 FftExecutionCache::with_owner(cache.owner(), cache.store_mut()),
1456 )?;
1457 current = Some(output);
1458 }
1459 current.ok_or_else(|| {
1460 tenferro_tensor::Error::invalid_argument(
1461 "tenferro-fft",
1462 "axes",
1463 "FFT requires at least one axis",
1464 )
1465 })
1466}
1467
1468fn execute_fft_extension_reads_on_session(
1469 op: &FftOp,
1470 inputs: &[TensorRead<'_>],
1471 session: &mut dyn Engine,
1472 caches: &mut ExtensionCacheStore,
1473) -> tenferro_tensor::Result<Vec<Tensor>> {
1474 if let Some(result) = with_cpu_engine(session, |session| {
1475 execute_fft_extension_reads_for_capability(op, inputs, session, caches)
1476 }) {
1477 return result;
1478 }
1479 #[cfg(feature = "cuda")]
1480 if let Some(result) = with_cuda_engine(session, |session| {
1481 execute_fft_extension_reads_for_capability(op, inputs, session, caches)
1482 }) {
1483 return result;
1484 }
1485 Err(tenferro_tensor::Error::unsupported(
1486 fft_op_name(op.operation),
1487 "selected backend session does not expose an FFT execution capability",
1488 ))
1489}
1490
1491define_extension_runtime! {
1492 runtime = FftRuntime,
1493 family_id = FFT_EXTENSION_FAMILY_ID,
1494 op_type = FftOp,
1495 execute_in_session = execute_fft_extension_reads_in_session,
1496 session_supported = fft_session_supported,
1497}
1498
1499fn execute_fft_extension_reads_in_session(
1503 op: &FftOp,
1504 session: &mut dyn Engine,
1505 caches: &mut ExtensionCacheStore,
1506 inputs: &[TensorRead<'_>],
1507) -> tenferro_tensor::Result<Vec<Tensor>> {
1508 let mut ctx = ExtensionExecutionContext::new(session, caches);
1509 execute_fft_extension_reads_session(op, inputs, &mut ctx)
1510}
1511
1512fn fft_session_supported<B: Engine + 'static>(_op: &FftOp) -> bool {
1513 let type_id = std::any::TypeId::of::<B>();
1517 type_id == std::any::TypeId::of::<tenferro_cpu::CpuEngine>() || {
1518 #[cfg(feature = "cuda")]
1519 {
1520 type_id == std::any::TypeId::of::<CudaEngine>()
1521 }
1522 #[cfg(not(feature = "cuda"))]
1523 {
1524 false
1525 }
1526 }
1527}
1528
1529fn apply_unary_fftn(
1530 op_name: &'static str,
1531 input: &TracedTensor,
1532 operation: FftOperation,
1533 lengths: Option<&[usize]>,
1534 length_argument: &'static str,
1535 axes: &[isize],
1536 norm: FftNorm,
1537) -> Result<TracedTensor> {
1538 let concrete_shape = input.try_concrete_shape();
1539 let op = Arc::new(
1540 validated_fft_op(
1541 op_name,
1542 operation,
1543 Some(input.dtype()),
1544 input.rank(),
1545 concrete_shape.as_deref(),
1546 lengths,
1547 length_argument,
1548 axes,
1549 norm,
1550 )
1551 .map_err(graph_build_fft_error)?,
1552 );
1553 let mut outputs = apply(op, &[input])?;
1554 outputs
1555 .pop()
1556 .ok_or_else(|| Error::Internal("FFT extension declares exactly one output".into()))
1557}
1558
1559fn graph_build_fft_error(error: tenferro_tensor::Error) -> Error {
1565 match error {
1566 tenferro_tensor::Error::Validation { op, source } => {
1567 Error::validation(op, ErrorPhase::GraphBuild, source)
1568 }
1569 other => Error::from(other),
1570 }
1571}
1572
1573fn single_axis_lengths(n: Option<usize>) -> Option<[usize; 1]> {
1576 n.map(|n| [n])
1577}
1578
1579fn normalize_axis(op: &'static str, axis: isize, rank: usize) -> tenferro_tensor::Result<usize> {
1580 if rank == 0 {
1581 return Err(tenferro_tensor::Error::invalid_argument(
1582 op,
1583 "rank",
1584 "FFT requires rank >= 1",
1585 ));
1586 }
1587 tenferro_tensor::normalize_axis(axis, rank)
1589 .map_err(|source| tenferro_tensor::Error::validation(op, source))
1590}
1591
1592#[cfg(feature = "autodiff")]
1595#[allow(clippy::too_many_arguments)]
1596fn prepare_runtime_fft_op(
1597 op_name: &'static str,
1598 operation: FftOperation,
1599 rank: usize,
1600 concrete_shape: Option<&[usize]>,
1601 n: Option<usize>,
1602 axis: isize,
1603 norm: FftNorm,
1604) -> Result<FftOp> {
1605 let lengths = single_axis_lengths(n);
1606 validated_fft_op(
1607 op_name,
1608 operation,
1609 None,
1610 rank,
1611 concrete_shape,
1612 lengths.as_ref().map(|lengths| lengths.as_slice()),
1613 "n",
1614 &[axis],
1615 norm,
1616 )
1617 .map_err(graph_build_fft_error)
1618}
1619
1620fn runtime_forward_fft_operation(dtype: DType) -> Result<FftOperation> {
1621 match dtype {
1622 DType::C32 | DType::C64 => Ok(FftOperation::C2cForward),
1623 DType::F32 | DType::F64 => Ok(FftOperation::R2cFull),
1624 DType::I32 | DType::I64 | DType::Bool | DType::External(_) => Err(
1625 runtime_unsupported_dtype("fft", dtype, "F32, F64, C32, or C64"),
1626 ),
1627 }
1628}
1629
1630fn require_runtime_dtype(
1631 op: &'static str,
1632 dtype: DType,
1633 supported: &[DType],
1634 expected: &'static str,
1635) -> Result<()> {
1636 if supported.contains(&dtype) {
1637 Ok(())
1638 } else {
1639 Err(runtime_unsupported_dtype(op, dtype, expected))
1640 }
1641}
1642
1643fn runtime_unsupported_dtype(op: &'static str, dtype: DType, expected: &'static str) -> Error {
1644 Error::extension(
1645 op,
1646 ErrorPhase::GraphBuild,
1647 FFT_EXTENSION_FAMILY_ID,
1648 ErrorKind::Unsupported,
1649 FftError::UnsupportedDType {
1650 op,
1651 dtype,
1652 expected,
1653 },
1654 )
1655}
1656
1657fn transform_len_dim(n: Option<usize>, input_dim: &SymDim) -> tenferro_tensor::Result<SymDim> {
1663 let len = n.map(SymDim::from).unwrap_or_else(|| input_dim.clone());
1664 if len.constant_value() == Some(0) {
1665 return Err(tenferro_tensor::Error::invalid_argument(
1666 "fft",
1667 "transform length",
1668 "must be positive",
1669 ));
1670 }
1671 Ok(len)
1672}
1673
1674fn expected_dtype_description(operation: FftOperation) -> &'static str {
1675 match operation {
1676 FftOperation::C2cForward | FftOperation::C2cInverse | FftOperation::C2r => "C32 or C64",
1677 FftOperation::R2cFull | FftOperation::R2cOnesided => "F32 or F64",
1678 }
1679}
1680
1681fn fft_op_name(operation: FftOperation) -> &'static str {
1682 match operation {
1683 FftOperation::C2cForward => "fft",
1684 FftOperation::C2cInverse => "ifft",
1685 FftOperation::R2cFull | FftOperation::R2cOnesided => "rfft",
1686 FftOperation::C2r => "irfft",
1687 }
1688}
1689
1690#[cfg(feature = "autodiff")]
1691fn fft_ad_family_id(operation: FftOperation) -> &'static str {
1692 match operation {
1693 FftOperation::C2cForward | FftOperation::C2cInverse => FFT_EXTENSION_FAMILY_ID,
1694 FftOperation::R2cFull | FftOperation::R2cOnesided => "tenferro-fft.rfft.v1",
1695 FftOperation::C2r => "tenferro-fft.irfft.v1",
1696 }
1697}
1698
1699fn output_shape_c2c(
1700 shape: &[usize],
1701 axis: usize,
1702 n: Option<usize>,
1703) -> tenferro_tensor::Result<Vec<usize>> {
1704 let len = transform_len(shape, axis, n)?;
1705 let mut out_shape = shape.to_vec();
1706 out_shape[axis] = len;
1707 Ok(out_shape)
1708}
1709
1710fn output_shape_r2c(
1711 shape: &[usize],
1712 axis: usize,
1713 n: Option<usize>,
1714 onesided: bool,
1715) -> tenferro_tensor::Result<Vec<usize>> {
1716 let len = transform_len(shape, axis, n)?;
1717 let mut out_shape = shape.to_vec();
1718 out_shape[axis] = if onesided { len / 2 + 1 } else { len };
1719 Ok(out_shape)
1720}
1721
1722fn output_shape_c2r(
1723 shape: &[usize],
1724 axis: usize,
1725 n: Option<usize>,
1726) -> tenferro_tensor::Result<Vec<usize>> {
1727 validate_axis("irfft", shape, axis)?;
1728 let input_len = shape[axis];
1729 let len = match n {
1730 Some(len) => len,
1731 None => default_c2r_output_len(input_len)?,
1732 };
1733 if len == 0 {
1734 return Err(tenferro_tensor::Error::invalid_argument(
1735 "irfft",
1736 "output length",
1737 "must be positive",
1738 ));
1739 }
1740 validate_c2r_spectrum_len(input_len, len)?;
1741 let mut out_shape = shape.to_vec();
1742 out_shape[axis] = len;
1743 Ok(out_shape)
1744}
1745
1746fn output_dim_c2r(input_dim: &SymDim, n: Option<usize>) -> tenferro_tensor::Result<SymDim> {
1747 match (input_dim.constant_value(), n) {
1748 (Some(input_len), Some(output_len)) => {
1749 if output_len == 0 {
1750 return Err(tenferro_tensor::Error::invalid_argument(
1751 "irfft",
1752 "output length",
1753 "must be positive",
1754 ));
1755 }
1756 validate_c2r_spectrum_len(input_len, output_len)?;
1757 Ok(SymDim::from(output_len))
1758 }
1759 (Some(input_len), None) => {
1760 let output_len = default_c2r_output_len(input_len)?;
1761 if output_len == 0 {
1762 return Err(tenferro_tensor::Error::invalid_argument(
1763 "irfft",
1764 "output length",
1765 "must be positive",
1766 ));
1767 }
1768 Ok(SymDim::from(output_len))
1769 }
1770 (None, Some(output_len)) => {
1771 if output_len == 0 {
1772 return Err(tenferro_tensor::Error::invalid_argument(
1773 "irfft",
1774 "output length",
1775 "must be positive",
1776 ));
1777 }
1778 Ok(SymDim::from(output_len))
1779 }
1780 (None, None) => Ok((input_dim.clone() - 1usize) * 2usize),
1781 }
1782}
1783
1784fn default_c2r_output_len(input_len: usize) -> tenferro_tensor::Result<usize> {
1785 if input_len == 0 {
1786 return Err(tenferro_tensor::Error::invalid_argument(
1787 "irfft",
1788 "input spectrum axis length",
1789 "must be positive",
1790 ));
1791 }
1792 input_len
1793 .checked_sub(1)
1794 .and_then(|len| len.checked_mul(2))
1795 .ok_or_else(|| {
1796 tenferro_tensor::Error::invalid_argument(
1797 "irfft",
1798 "default output length",
1799 "overflows usize",
1800 )
1801 })
1802}
1803
1804fn validate_c2r_spectrum_len(
1805 input_len: usize,
1806 output_len: usize,
1807) -> tenferro_tensor::Result<usize> {
1808 let expected = output_len / 2 + 1;
1809 if input_len != expected {
1810 return Err(tenferro_tensor::Error::invalid_argument(
1811 "irfft",
1812 "spectrum",
1813 format!(
1814 "one-sided spectrum axis length mismatch: expected {expected} for output length {output_len}, got {input_len}"
1815 ),
1816 ));
1817 }
1818 Ok(expected)
1819}
1820
1821fn transform_len(shape: &[usize], axis: usize, n: Option<usize>) -> tenferro_tensor::Result<usize> {
1822 validate_axis("fft", shape, axis)?;
1823 let len = n.unwrap_or(shape[axis]);
1824 if len == 0 {
1825 return Err(tenferro_tensor::Error::invalid_argument(
1826 "fft",
1827 "transform length",
1828 "must be positive",
1829 ));
1830 }
1831 Ok(len)
1832}
1833
1834fn validate_axis(op: &'static str, shape: &[usize], axis: usize) -> tenferro_tensor::Result<()> {
1835 if axis >= shape.len() {
1836 return Err(tenferro_tensor::Error::axis_out_of_bounds(
1837 op,
1838 axis,
1839 shape.len(),
1840 ));
1841 }
1842 Ok(())
1843}
1844
1845#[cfg(test)]
1846mod concrete_tests;
1847
1848#[cfg(test)]
1849mod nd_tests;
1850
1851#[cfg(test)]
1852mod lib_tests;