8#ifndef NUMERICAL_FFT_KERNELS_HPP
9#define NUMERICAL_FFT_KERNELS_HPP
24#if defined(NUMERICAL_NEON_COMPILED)
32 template <
typename Isa,
54 const std::uint64_t
sign {std::uint64_t {1} << 63U};
62 return vdupq_n_u64(std::uint64_t {1} << (real ? 31U : 63U));
81 const double* p)
noexcept
138 const float* p)
noexcept
318#if defined(NUMERICAL_X86_COMPILED) || defined(NUMERICAL_NEON_COMPILED)
322 template <
typename R>
325 const std::complex<R>& v)
noexcept
327 return {std::fma(c, v.real(), s.real()), std::fma(c, v.imag(), s.imag())};
331 template <
typename R>
333 const std::complex<R>& v)
noexcept
335 const R
ii {w.imag() * v.imag()};
336 const R ir {w.imag() * v.real()};
337 return {std::fma(w.real(), v.real(), -
ii), std::fma(w.real(), v.imag(), ir)};
341 template <
typename V>
367 template <
typename Isa,
371 const std::complex<R>*
in,
372 std::complex<R>* out,
373 const std::complex<R>* twiddles)
noexcept
375 using C = std::complex<R>;
378 constexpr std::size_t width {
sizeof(
vec) /
sizeof(C)};
380 const std::size_t run {
quarter - 1};
382 const R*
const from {
reinterpret_cast<const R*
>(
in)};
383 R*
const into {
reinterpret_cast<R*
>(out)};
387 const R*
const factors {
reinterpret_cast<const R*
>(twiddles)};
391 const R*
const at {
from + (2 * p)};
411 const C
w1 {
twiddle ? twiddles[p - 1] : C {1}};
412 const C
w2 {
twiddle ? twiddles[run + p - 1] : C {1}};
413 const C
w3 {
twiddle ? twiddles[(2 * run) + p - 1] : C {1}};
415 R*
const to {into + (2 *
stride * 4 * p)};
424 for (; q + width <=
stride; q += width) {
425 const R*
const at {
in_p + (2 * q)};
474 template <
typename Isa,
478 const std::complex<R>*
in,
479 std::complex<R>* out,
480 const std::complex<R>* twiddles,
481 const std::array<std::complex<R>, 16>& sixteenths)
noexcept
485 constexpr std::size_t width {
sizeof(
vec) /
sizeof(std::complex<R>)};
487 const std::size_t run {
part - 1};
489 const R*
const from {
reinterpret_cast<const R*
>(
in)};
490 R*
const into {
reinterpret_cast<R*
>(out)};
491 for (std::size_t p {0}; p <
part; ++p) {
493 R*
const to {into + (2 *
stride * 16 * p)};
494 for (std::size_t q {0}; q <
stride; q += width) {
495 const R*
const at {
in_p + (2 * q)};
496 std::array<vec, 16> inner {};
498 for (std::size_t
j1 {0};
j1 < 4; ++
j1) {
501 inner[(4 *
j1) + 3]);
504 for (std::size_t
j1 {1};
j1 < 4; ++
j1) {
506 for (std::size_t
k2 {1};
k2 < 4; ++
k2) {
507 vec& value {inner[(4 *
j1) +
k2]};
508 const std::complex<R>& w {sixteenths[
j1 *
k2]};
513 for (std::size_t
k2 {0};
k2 < 4; ++
k2) {
518 for (std::size_t
k1 {0};
k1 < 4; ++
k1) {
519 const std::size_t k {(4 *
k1) +
k2};
521 if (p != 0 && k != 0) {
522 const std::complex<R>& w {twiddles[((k - 1) * run) + p - 1]};
534 template <
typename Isa,
538 const std::complex<R>* twiddles,
541 std::size_t k)
noexcept
545 const std::complex<R> w {twiddles[((k - 1) * run) + p - 1]};
557 template <
typename Isa,
561 const std::complex<R>*
in,
562 std::complex<R>* out,
563 const std::complex<R>* twiddles,
564 R half_root_three)
noexcept
566 using C = std::complex<R>;
569 constexpr std::size_t width {
sizeof(
vec) /
sizeof(std::complex<R>)};
571 const std::size_t run {
part - 1};
575 for (std::size_t p {0}; p <
part; ++p) {
577 C*
const to {out + (
stride * 3 * p)};
580 const C
w1 {p == 0 ? C {1} : twiddles[p - 1]};
581 const C
w2 {p == 0 ? C {1} : twiddles[run + p - 1]};
586 for (; q + width <=
stride; q += width) {
587 const R*
const at {
reinterpret_cast<const R*
>(
in_p + q)};
600 R*
const place {
reinterpret_cast<R*
>(
to + q)};
606 if constexpr (!Isa::whole_strides) {
612 const C v {
x0 - C {R(0.5) * t.real(), R(0.5) * t.imag()}};
614 const C u {half_root_three * d.real(), half_root_three * d.imag()};
615 const C
iu {-u.imag(), u.real()};
628 template <
typename Isa,
632 const std::complex<R>*
in,
633 std::complex<R>* out,
634 const std::complex<R>* twiddles,
640 using C = std::complex<R>;
643 constexpr std::size_t width {
sizeof(
vec) /
sizeof(std::complex<R>)};
645 const std::size_t run {
part - 1};
652 for (std::size_t p {0}; p <
part; ++p) {
654 C*
const to {out + (
stride * 5 * p)};
657 for (; q + width <=
stride; q += width) {
658 const R*
const at {
reinterpret_cast<const R*
>(
in_p + q)};
672 R*
const place {
reinterpret_cast<R*
>(
to + q)};
680 if constexpr (!Isa::whole_strides) {
695 const C
ib1 {-
b1.imag(),
b1.real()};
696 const C
ib2 {-
b2.imag(),
b2.real()};
699 for (std::size_t j {1}; j < 5; ++j) {
712 template <
typename Isa,
716 const std::complex<R>*
in,
717 std::complex<R>* out,
718 const std::complex<R>* twiddles,
719 R half_root_two)
noexcept
723 constexpr std::size_t width {
sizeof(
vec) /
sizeof(std::complex<R>)};
725 const std::size_t run {
part - 1};
728 const R*
const from {
reinterpret_cast<const R*
>(
in)};
729 R*
const into {
reinterpret_cast<R*
>(out)};
730 for (std::size_t p {0}; p <
part; ++p) {
732 R*
const to {into + (2 *
stride * 8 * p)};
733 for (std::size_t q {0}; q + width <=
stride; q += width) {
734 const R*
const at {
in_p + (2 * q)};
759 fft_four_point(
fft_add(
x0,
x4),
fft_add(
x1,
x5),
fft_add(
x2,
x6),
fft_add(
x3,
x7),
e0,
e1,
e2,
e3);
782 template <
typename Isa,
787 const std::complex<R>*
in,
788 std::complex<R>* out,
789 const std::complex<R>* twiddles,
790 const std::complex<R>* roots)
noexcept
792 using C = std::complex<R>;
795 constexpr std::size_t width {
sizeof(
vec) /
sizeof(std::complex<R>)};
797 const std::size_t run {
part - 1};
799 const std::size_t half {
radix / 2};
800 for (std::size_t p {0}; p <
part; ++p) {
805 for (; q + width <=
stride; q += width) {
806 std::array<vec, fft_most_pairs>
sums;
808 const R*
const at {
reinterpret_cast<const R*
>(
in_p + q)};
811 for (std::size_t j {1}; j <= half; ++j) {
818 R*
const place {
reinterpret_cast<R*
>(
to + q)};
820 for (std::size_t k {1}; k <= half; ++k) {
821 std::size_t
power {k};
824 for (std::size_t j {2}; j <= half; ++j) {
836 if constexpr (!Isa::whole_strides) {
838 std::array<C, fft_most_pairs>
sums {};
842 for (std::size_t j {1}; j <= half; ++j) {
850 for (std::size_t k {1}; k <= half; ++k) {
851 std::size_t
power {k};
854 for (std::size_t j {2}; j <= half; ++j) {
873#if defined(NUMERICAL_X86_COMPILED)
875 template <
typename R>
879 std::complex<R>* out,
887 template <
typename R>
891 std::complex<R>* out,
899 template <
typename R>
903 std::complex<R>* out,
904 const std::complex<R>* twiddles,
912 template <
typename R>
916 std::complex<R>* out,
917 const std::complex<R>* twiddles,
930 template <
typename R>
934 std::complex<R> * out,
935 const std::complex<R>* twiddles,
943 template <
typename R>
947 std::complex<R> * out,
948 const std::complex<R>* twiddles,
959 template <
typename R>
963 std::complex<R> * out,
964 const std::complex<R>* twiddles,
972 template <
typename R>
977 std::complex<R> * out,
978 const std::complex<R>* twiddles,
986 template <
typename R>
991 std::complex<R> * out,
992 const std::complex<R>* twiddles,
1001#if defined(NUMERICAL_NEON_COMPILED)
1004 template <
typename R>
1007 const std::complex<R>*
in,
1008 std::complex<R>* out,
1009 const std::complex<R>* twiddles)
noexcept
1015 template <
typename R>
1018 const std::complex<R>*
in,
1019 std::complex<R>* out,
1020 const std::complex<R>* twiddles,
1021 const std::array<std::complex<R>, 16>& sixteenths)
noexcept
1027 template <
typename R>
1030 const std::complex<R>*
in,
1031 std::complex<R> * out,
1032 const std::complex<R>* twiddles,
1033 R half_root_three)
noexcept
1039 template <
typename R>
1042 const std::complex<R>*
in,
1043 std::complex<R> * out,
1044 const std::complex<R>* twiddles,
1054 template <
typename R>
1057 const std::complex<R>*
in,
1058 std::complex<R> * out,
1059 const std::complex<R>* twiddles,
1060 R half_root_two)
noexcept
1066 template <
typename R>
1070 const std::complex<R>*
in,
1071 std::complex<R>* out,
1072 const std::complex<R>* twiddles,
1073 const std::complex<R>* roots)
noexcept
The matrix product kernel behind matrix * matrix and the einsum matmul path.
#define NUMERICAL_UNROLL_BLOCK
T root(const T &x)
The square root of a scalar, as std::sqrt gives it.
The native vector of float and double the kernels hold their lanes in (GNU vector extensions,...
#define NUMERICAL_ALWAYS_INLINE
A dense, row-major, N-dimensional tensor and Einstein summation.
The x86-64 tiles of the double matrix product: AVX-512 and AVX2 with FMA, chosen at run time.