NumericAL
A header-only C++20 lexer built on REAL
Loading...
Searching...
No Matches
fft_kernels.hpp
Go to the documentation of this file.
1
8#ifndef NUMERICAL_FFT_KERNELS_HPP
9#define NUMERICAL_FFT_KERNELS_HPP
10
11#include <array>
12#include <cmath>
13#include <complex>
14#include <cstddef>
15#include <cstdint>
16
17#include "gemm.hpp"
18#include "simd.hpp"
19#include "tensor.hpp"
20#include "x86.hpp"
21
22namespace numerical::detail {
23
24#if defined(NUMERICAL_NEON_COMPILED)
26 struct fft_neon
27 {
28 static constexpr bool whole_strides {false};
29 };
30
32 template <typename Isa,
33 typename R>
34 struct fft_reg;
35
37 template <>
38 struct fft_reg<fft_neon, double>
39 {
40 float64x2_t v;
41 };
42
44 template <>
45 struct fft_reg<fft_neon, float>
46 {
47 float32x4_t v;
48 };
49
52 bool real) noexcept
53 {
54 const std::uint64_t sign {std::uint64_t {1} << 63U};
56 }
57
60 bool real) noexcept
61 {
62 return vdupq_n_u64(std::uint64_t {1} << (real ? 31U : 63U));
63 }
64
67 uint64x2_t signs) noexcept
68 {
70 }
71
74 uint64x2_t signs) noexcept
75 {
77 }
78
81 const double* p) noexcept
82 {
83 return {vld1q_f64(p)};
84 }
85
88 double c) noexcept
89 {
90 return {vdupq_n_f64(c)};
91 }
92
94 NUMERICAL_ALWAYS_INLINE void fft_store(double * p,
96 {
97 vst1q_f64(p, v.v);
98 }
99
102 fft_reg<fft_neon, double> b) noexcept
103 {
104 return {vaddq_f64(a.v, b.v)};
105 }
106
109 fft_reg<fft_neon, double> b) noexcept
110 {
111 return {vsubq_f64(a.v, b.v)};
112 }
113
116 {
117 return {neon_flipped(neon_exchanged(v.v), neon_part_signs(v, true))};
118 }
119
122 {
123 return {neon_flipped(neon_exchanged(v.v), neon_part_signs(v, false))};
124 }
125
130 fft_reg<fft_neon, double> v) noexcept
131 {
133 return {vfmaq_f64(crossed, re.v, v.v)};
134 }
135
138 const float* p) noexcept
139 {
140 return {vld1q_f32(p)};
141 }
142
145 float c) noexcept
146 {
147 return {vdupq_n_f32(c)};
148 }
149
151 NUMERICAL_ALWAYS_INLINE void fft_store(float * p,
152 fft_reg<fft_neon, float> v) noexcept
153 {
154 vst1q_f32(p, v.v);
155 }
156
159 fft_reg<fft_neon, float> b) noexcept
160 {
161 return {vaddq_f32(a.v, b.v)};
162 }
163
166 fft_reg<fft_neon, float> b) noexcept
167 {
168 return {vsubq_f32(a.v, b.v)};
169 }
170
173 {
174 return {neon_flipped(neon_exchanged(v.v), neon_part_signs(v, true))};
175 }
176
179 {
180 return {neon_flipped(neon_exchanged(v.v), neon_part_signs(v, false))};
181 }
182
187 fft_reg<fft_neon, float> v) noexcept
188 {
190 return {vfmaq_f32(crossed, re.v, v.v)};
191 }
192
195 {
196 return {vdupq_laneq_f64(v.v, 0)};
197 }
198
201 {
202 return {vtrn1q_f32(v.v, v.v)};
203 }
204
207 {
208 return {vdupq_laneq_f64(v.v, 1)};
209 }
210
213 {
214 return {vtrn2q_f32(v.v, v.v)};
215 }
216
224 {
225 vst1q_f64(to, y0.v);
226 vst1q_f64(to + 2, y1.v);
227 vst1q_f64(to + 4, y2.v);
228 vst1q_f64(to + 6, y3.v);
229 }
230
237 {
242 vst1q_f32(to, vreinterpretq_f32_f64(vzip1q_f64(a, b))); // butterfly 0: y0 y1
243 vst1q_f32(to + 4, vreinterpretq_f32_f64(vzip1q_f64(c, d))); // y2 y3
244 vst1q_f32(to + 8, vreinterpretq_f32_f64(vzip2q_f64(a, b))); // butterfly 1
246 }
247
250 fft_reg<fft_neon, double> b) noexcept
251 {
252 return {vmulq_f64(a.v, b.v)};
253 }
254
258 fft_reg<fft_neon, double> c) noexcept
259 {
260 return {vfmaq_f64(c.v, a.v, b.v)};
261 }
262
266 {
267 return {vcopyq_laneq_f64(even.v, 1, odd.v, 1)};
268 }
269
272 {
273 return {neon_flipped(v.v, neon_part_signs(v, false))};
274 }
275
278 {
279 return {neon_exchanged(v.v)};
280 }
281
284 fft_reg<fft_neon, float> b) noexcept
285 {
286 return {vmulq_f32(a.v, b.v)};
287 }
288
292 fft_reg<fft_neon, float> c) noexcept
293 {
294 return {vfmaq_f32(c.v, a.v, b.v)};
295 }
296
300 {
301 return {vbslq_f32(vreinterpretq_u32_u64(vdupq_n_u64(std::uint64_t {0xFFFFFFFF} << 32U)), odd.v, even.v)};
302 }
303
306 {
307 return {neon_flipped(v.v, neon_part_signs(v, false))};
308 }
309
312 {
313 return {neon_exchanged(v.v)};
314 }
315
316#endif
317
318#if defined(NUMERICAL_X86_COMPILED) || defined(NUMERICAL_NEON_COMPILED)
319
322 template <typename R>
323 NUMERICAL_ALWAYS_INLINE std::complex<R> fft_scaled_add(const std::complex<R>& s,
324 R c,
325 const std::complex<R>& v) noexcept
326 {
327 return {std::fma(c, v.real(), s.real()), std::fma(c, v.imag(), s.imag())};
328 }
329
331 template <typename R>
332 NUMERICAL_ALWAYS_INLINE std::complex<R> fft_fused_product(const std::complex<R>& w,
333 const std::complex<R>& v) noexcept
334 {
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)};
338 }
339
341 template <typename V>
343 const V& v1,
344 const V& v2,
345 const V& v3,
346 V& y0,
347 V& y1,
348 V& y2,
349 V& y3) noexcept
350 {
351 const V a_plus_c {fft_add(v0, v2)};
352 const V a_minus_c {fft_sub(v0, v2)};
353 const V b_plus_d {fft_add(v1, v3)};
354 const V i_b_d {fft_times_i(fft_sub(v1, v3))};
359 }
360
367 template <typename Isa,
368 typename R>
370 std::size_t stride,
371 const std::complex<R>* in,
372 std::complex<R>* out,
373 const std::complex<R>* twiddles) noexcept
374 {
375 using C = std::complex<R>;
376 using vec = fft_reg<Isa, R>;
377 constexpr Isa isa {};
378 constexpr std::size_t width {sizeof(vec) / sizeof(C)}; // complex numbers in a register
379 const std::size_t quarter {current / 4};
380 const std::size_t run {quarter - 1};
381 const std::size_t apart {2 * stride * quarter}; // parts between a butterfly's inputs
382 const R* const from {reinterpret_cast<const R*>(in)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
383 R* const into {reinterpret_cast<R*>(out)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the same
384 std::size_t vector_begin {quarter}; // the butterflies the first pass takes by registers: [vector_begin, vector_end)
385 std::size_t vector_end {quarter};
386 if (stride == 1 && quarter >= 2 * width) { // the first pass: a register of butterflies along p, past the first
387 const R* const factors {reinterpret_cast<const R*>(twiddles)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
388 vector_begin = width; // its first register's butterflies one at a time: p = 0 multiplies by nothing
389 vector_end = quarter - (quarter % width); // whole registers only
390 for (std::size_t p {vector_begin}; p < vector_end; p += width) {
391 const R* const at {from + (2 * p)};
392 const vec a {fft_load(isa, at)};
393 const vec b {fft_load(isa, at + apart)};
394 const vec c {fft_load(isa, at + (2 * apart))};
395 const vec d {fft_load(isa, at + (3 * apart))};
396 const vec a_plus_c {fft_add(a, c)};
397 const vec a_minus_c {fft_sub(a, c)};
398 const vec b_plus_d {fft_add(b, d)};
399 const vec i_b_d {fft_times_i(fft_sub(b, d))};
400 const vec w1 {fft_load(isa, factors + (2 * (p - 1)))};
401 const vec w2 {fft_load(isa, factors + (2 * (run + p - 1)))};
402 const vec w3 {fft_load(isa, factors + (2 * ((2 * run) + p - 1)))};
407 }
408 }
409 for (std::size_t p {0}; p < quarter; p = (p + 1 == vector_begin) ? vector_end : p + 1) { // those the registers did not take
410 const bool twiddle {p != 0};
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}};
414 const R* const in_p {from + (2 * stride * p)};
415 R* const to {into + (2 * stride * 4 * p)};
416 std::size_t q {0};
417 if (stride >= width) {
418 const vec w1_re {fft_splat(isa, w1.real())};
419 const vec w1_im {fft_splat(isa, w1.imag())};
420 const vec w2_re {fft_splat(isa, w2.real())};
421 const vec w2_im {fft_splat(isa, w2.imag())};
422 const vec w3_re {fft_splat(isa, w3.real())};
423 const vec w3_im {fft_splat(isa, w3.imag())};
424 for (; q + width <= stride; q += width) {
425 const R* const at {in_p + (2 * q)};
426 const vec a {fft_load(isa, at)};
427 const vec b {fft_load(isa, at + apart)};
428 const vec c {fft_load(isa, at + (2 * apart))};
429 const vec d {fft_load(isa, at + (3 * apart))};
430 const vec a_plus_c {fft_add(a, c)};
431 const vec a_minus_c {fft_sub(a, c)};
432 const vec b_plus_d {fft_add(b, d)};
433 const vec i_b_d {fft_times_i(fft_sub(b, d))};
434 vec first {fft_sub(a_minus_c, i_b_d)};
435 vec second {fft_sub(a_plus_c, b_plus_d)};
437 if (twiddle) {
438 first = fft_twiddled(w1_re, w1_im, first);
439 second = fft_twiddled(w2_re, w2_im, second);
441 }
442 R* const place {to + (2 * q)};
444 fft_store(place + (2 * stride), first);
445 fft_store(place + (4 * stride), second);
446 fft_store(place + (6 * stride), third);
447 }
448 }
449 for (; q < stride; ++q) { // a stride narrower than a register: one butterfly at a time, the same arithmetic
450 const C a {in[(stride * p) + q]};
451 const C b {in[(stride * (p + quarter)) + q]};
452 const C c {in[(stride * (p + (2 * quarter))) + q]};
453 const C d {in[(stride * (p + (3 * quarter))) + q]};
454 const C a_plus_c {a + c};
455 const C a_minus_c {a - c};
456 const C b_plus_d {b + d};
457 const C b_minus_d {b - d};
458 const C i_b_d {-b_minus_d.imag(), b_minus_d.real()};
459 C* const place {out + (stride * 4 * p) + q};
460 place[0] = a_plus_c + b_plus_d;
464 }
465 }
466 }
467
474 template <typename Isa,
475 typename R>
477 std::size_t stride,
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
482 {
483 using vec = fft_reg<Isa, R>;
484 constexpr Isa isa {};
485 constexpr std::size_t width {sizeof(vec) / sizeof(std::complex<R>)}; // complex numbers in a register
486 const std::size_t part {current / 16};
487 const std::size_t run {part - 1};
488 const std::size_t apart {2 * stride * part}; // parts between a butterfly's inputs
489 const R* const from {reinterpret_cast<const R*>(in)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
490 R* const into {reinterpret_cast<R*>(out)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the same
491 for (std::size_t p {0}; p < part; ++p) {
492 const R* const in_p {from + (2 * stride * 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) {
499 fft_four_point(fft_load(isa, at + (j1 * apart)), fft_load(isa, at + ((j1 + 4) * apart)), fft_load(isa, at + ((j1 + 8) * apart)),
500 fft_load(isa, at + ((j1 + 12) * apart)), inner[4 * j1], inner[(4 * j1) + 1], inner[(4 * j1) + 2],
501 inner[(4 * j1) + 3]);
502 }
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]};
509 value = (j1 * k2) == 4 ? fft_times_minus_i(value) : fft_twiddled(fft_splat(isa, w.real()), fft_splat(isa, w.imag()), value);
510 }
511 }
513 for (std::size_t k2 {0}; k2 < 4; ++k2) {
514 std::array<vec, 4> outputs {};
515 fft_four_point(inner[k2], inner[4 + k2], inner[8 + k2], inner[12 + k2], outputs[0], outputs[1], outputs[2],
516 outputs[3]);
518 for (std::size_t k1 {0}; k1 < 4; ++k1) {
519 const std::size_t k {(4 * k1) + k2};
520 vec y {outputs[k1]};
521 if (p != 0 && k != 0) {
522 const std::complex<R>& w {twiddles[((k - 1) * run) + p - 1]};
523 y = fft_twiddled(fft_splat(isa, w.real()), fft_splat(isa, w.imag()), y);
524 }
525 fft_store(to + (2 * q) + (2 * stride * k), y);
526 }
527 }
528 }
529 }
530 }
531
534 template <typename Isa,
535 typename R>
537 const fft_reg<Isa, R>& value,
538 const std::complex<R>* twiddles,
539 std::size_t run,
540 std::size_t p,
541 std::size_t k) noexcept
542 {
543 constexpr Isa isa {};
544 if (p != 0) {
545 const std::complex<R> w {twiddles[((k - 1) * run) + p - 1]};
546 fft_store(place, fft_twiddled(fft_splat(isa, w.real()), fft_splat(isa, w.imag()), value));
547 return;
548 }
549 fft_store(place, value);
550 }
551
557 template <typename Isa,
558 typename R>
560 std::size_t stride,
561 const std::complex<R>* in,
562 std::complex<R>* out,
563 const std::complex<R>* twiddles,
564 R half_root_three) noexcept
565 {
566 using C = std::complex<R>;
567 using vec = fft_reg<Isa, R>;
568 constexpr Isa isa {};
569 constexpr std::size_t width {sizeof(vec) / sizeof(std::complex<R>)};
570 const std::size_t part {current / 3};
571 const std::size_t run {part - 1};
572 const std::size_t apart {stride * part};
573 const vec half {fft_splat(isa, R(0.5))};
574 const vec root {fft_splat(isa, half_root_three)};
575 for (std::size_t p {0}; p < part; ++p) {
576 const C* const in_p {in + (stride * p)};
577 C* const to {out + (stride * 3 * p)};
578 std::size_t q {0};
579 if (stride >= width) {
580 const C w1 {p == 0 ? C {1} : twiddles[p - 1]};
581 const C w2 {p == 0 ? C {1} : twiddles[run + p - 1]};
582 const vec w1_re {fft_splat(isa, w1.real())};
583 const vec w1_im {fft_splat(isa, w1.imag())};
584 const vec w2_re {fft_splat(isa, w2.real())};
585 const vec w2_im {fft_splat(isa, w2.imag())};
586 for (; q + width <= stride; q += width) {
587 const R* const at {reinterpret_cast<const R*>(in_p + q)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
588 const vec x0 {fft_load(isa, at)};
589 const vec x1 {fft_load(isa, at + (2 * apart))};
590 const vec x2 {fft_load(isa, at + (4 * apart))};
591 const vec t {fft_add(x1, x2)};
592 const vec v {fft_sub(x0, fft_mul(half, t))};
593 const vec iu {fft_times_i(fft_mul(root, fft_sub(x1, x2)))};
594 vec y1 {fft_sub(v, iu)};
595 vec y2 {fft_add(v, iu)};
596 if (p != 0) {
599 }
600 R* const place {reinterpret_cast<R*>(to + q)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the same
602 fft_store(place + (2 * stride), y1);
603 fft_store(place + (4 * stride), y2);
604 }
605 }
606 if constexpr (!Isa::whole_strides) {
607 for (; q < stride; ++q) { // a stride narrower than a register
608 const C x0 {in_p[q]};
609 const C x1 {in_p[q + apart]};
610 const C x2 {in_p[q + (2 * apart)]};
611 const C t {x1 + x2};
612 const C v {x0 - C {R(0.5) * t.real(), R(0.5) * t.imag()}};
613 const C d {x1 - x2};
614 const C u {half_root_three * d.real(), half_root_three * d.imag()};
615 const C iu {-u.imag(), u.real()};
616 to[q] = x0 + t;
617 to[q + stride] = p == 0 ? v - iu : fft_fused_product(twiddles[p - 1], v - iu);
618 to[q + 2 * stride] = p == 0 ? v + iu : fft_fused_product(twiddles[run + p - 1], v + iu);
619 }
620 }
621 }
622 }
623
628 template <typename Isa,
629 typename R>
631 std::size_t stride,
632 const std::complex<R>* in,
633 std::complex<R>* out,
634 const std::complex<R>* twiddles,
635 R c1,
636 R c2,
637 R s1,
638 R s2) noexcept
639 {
640 using C = std::complex<R>;
641 using vec = fft_reg<Isa, R>;
642 constexpr Isa isa {};
643 constexpr std::size_t width {sizeof(vec) / sizeof(std::complex<R>)};
644 const std::size_t part {current / 5};
645 const std::size_t run {part - 1};
646 const std::size_t apart {stride * part};
647 const vec vc1 {fft_splat(isa, c1)};
648 const vec vc2 {fft_splat(isa, c2)};
649 const vec vs1 {fft_splat(isa, s1)};
650 const vec vs2 {fft_splat(isa, s2)};
651 const vec vms1 {fft_splat(isa, -s1)};
652 for (std::size_t p {0}; p < part; ++p) {
653 const C* const in_p {in + (stride * p)};
654 C* const to {out + (stride * 5 * p)};
655 std::size_t q {0};
656 if (stride >= width) {
657 for (; q + width <= stride; q += width) {
658 const R* const at {reinterpret_cast<const R*>(in_p + q)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
659 const vec x0 {fft_load(isa, at)};
660 const vec x1 {fft_load(isa, at + (2 * apart))};
661 const vec x2 {fft_load(isa, at + (4 * apart))};
662 const vec x3 {fft_load(isa, at + (6 * apart))};
663 const vec x4 {fft_load(isa, at + (8 * apart))};
664 const vec t1 {fft_add(x1, x4)};
665 const vec t2 {fft_add(x2, x3)};
666 const vec t3 {fft_sub(x1, x4)};
667 const vec t4 {fft_sub(x2, x3)};
668 const vec a1 {fft_fused(vc2, t2, fft_fused(vc1, t1, x0))};
669 const vec a2 {fft_fused(vc1, t2, fft_fused(vc2, t1, x0))};
672 R* const place {reinterpret_cast<R*>(to + q)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the same
674 fft_store_twiddled<Isa>(place + (2 * stride), fft_sub(a1, ib1), twiddles, run, p, 1);
675 fft_store_twiddled<Isa>(place + (4 * stride), fft_sub(a2, ib2), twiddles, run, p, 2);
676 fft_store_twiddled<Isa>(place + (6 * stride), fft_add(a2, ib2), twiddles, run, p, 3);
677 fft_store_twiddled<Isa>(place + (8 * stride), fft_add(a1, ib1), twiddles, run, p, 4);
678 }
679 }
680 if constexpr (!Isa::whole_strides) {
681 for (; q < stride; ++q) { // a stride narrower than a register
682 const C x0 {in_p[q]};
683 const C x1 {in_p[q + apart]};
684 const C x2 {in_p[q + (2 * apart)]};
685 const C x3 {in_p[q + (3 * apart)]};
686 const C x4 {in_p[q + (4 * apart)]};
687 const C t1 {x1 + x4};
688 const C t2 {x2 + x3};
689 const C t3 {x1 - x4};
690 const C t4 {x2 - x3};
691 const C a1 {fft_scaled_add(fft_scaled_add(x0, c1, t1), c2, t2)};
692 const C a2 {fft_scaled_add(fft_scaled_add(x0, c2, t1), c1, t2)};
693 const C b1 {fft_scaled_add(C {s1 * t3.real(), s1 * t3.imag()}, s2, t4)};
694 const C b2 {fft_scaled_add(C {s2 * t3.real(), s2 * t3.imag()}, -s1, t4)};
695 const C ib1 {-b1.imag(), b1.real()};
696 const C ib2 {-b2.imag(), b2.real()};
697 const std::array<C, 4> y {a1 - ib1, a2 - ib2, a2 + ib2, a1 + ib1};
698 to[q] = (x0 + t1) + t2;
699 for (std::size_t j {1}; j < 5; ++j) {
700 to[q + (j * stride)] = p == 0 ? y[j - 1] : fft_fused_product(twiddles[((j - 1) * run) + p - 1], y[j - 1]);
701 }
702 }
703 }
704 }
705 }
706
712 template <typename Isa,
713 typename R>
715 std::size_t stride,
716 const std::complex<R>* in,
717 std::complex<R>* out,
718 const std::complex<R>* twiddles,
719 R half_root_two) noexcept
720 {
721 using vec = fft_reg<Isa, R>;
722 constexpr Isa isa {};
723 constexpr std::size_t width {sizeof(vec) / sizeof(std::complex<R>)};
724 const std::size_t part {current / 8};
725 const std::size_t run {part - 1};
726 const std::size_t apart {2 * stride * part}; // parts between a butterfly's inputs
727 const vec root {fft_splat(isa, half_root_two)};
728 const R* const from {reinterpret_cast<const R*>(in)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
729 R* const into {reinterpret_cast<R*>(out)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the same
730 for (std::size_t p {0}; p < part; ++p) {
731 const R* const in_p {from + (2 * stride * 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)};
735 const vec x0 {fft_load(isa, at)};
736 const vec x1 {fft_load(isa, at + apart)};
737 const vec x2 {fft_load(isa, at + (2 * apart))};
738 const vec x3 {fft_load(isa, at + (3 * apart))};
739 const vec x4 {fft_load(isa, at + (4 * apart))};
740 const vec x5 {fft_load(isa, at + (5 * apart))};
741 const vec x6 {fft_load(isa, at + (6 * apart))};
742 const vec x7 {fft_load(isa, at + (7 * apart))};
743 const vec b1 {fft_sub(x1, x5)};
744 const vec b3 {fft_sub(x3, x7)};
745 const vec s1 {fft_add(b1, fft_exchanged(b1))}; // re + im in both lanes
746 const vec d1 {fft_sub(b1, fft_exchanged(b1))}; // re − im, im − re
747 const vec s3 {fft_add(b3, fft_exchanged(b3))};
748 const vec d3 {fft_sub(fft_exchanged(b3), b3)}; // im − re, re − im
749 const vec w1 {fft_mul(root, fft_parts_of(s1, d1))};
751 vec e0 {};
752 vec e1 {};
753 vec e2 {};
754 vec e3 {};
755 vec o0 {};
756 vec o1 {};
757 vec o2 {};
758 vec o3 {};
761 R* const place {to + (2 * q)};
763 fft_store_twiddled<Isa>(place + (2 * stride), o0, twiddles, run, p, 1);
764 fft_store_twiddled<Isa>(place + (4 * stride), e1, twiddles, run, p, 2);
765 fft_store_twiddled<Isa>(place + (6 * stride), o1, twiddles, run, p, 3);
766 fft_store_twiddled<Isa>(place + (8 * stride), e2, twiddles, run, p, 4);
767 fft_store_twiddled<Isa>(place + (10 * stride), o2, twiddles, run, p, 5);
768 fft_store_twiddled<Isa>(place + (12 * stride), e3, twiddles, run, p, 6);
769 fft_store_twiddled<Isa>(place + (14 * stride), o3, twiddles, run, p, 7);
770 }
771 }
772 }
773
775 inline constexpr std::size_t fft_most_pairs {30};
776
782 template <typename Isa,
783 typename R>
785 std::size_t current,
786 std::size_t stride,
787 const std::complex<R>* in,
788 std::complex<R>* out,
789 const std::complex<R>* twiddles,
790 const std::complex<R>* roots) noexcept
791 {
792 using C = std::complex<R>;
793 using vec = fft_reg<Isa, R>;
794 constexpr Isa isa {};
795 constexpr std::size_t width {sizeof(vec) / sizeof(std::complex<R>)};
796 const std::size_t part {current / radix};
797 const std::size_t run {part - 1};
798 const std::size_t apart {stride * part};
799 const std::size_t half {radix / 2};
800 for (std::size_t p {0}; p < part; ++p) {
801 const C* const in_p {in + (stride * p)};
802 C* const to {out + (stride * radix * p)};
803 std::size_t q {0};
804 if (stride >= width) {
805 for (; q + width <= stride; q += width) {
806 std::array<vec, fft_most_pairs> sums; // NOLINT(cppcoreguidelines-pro-type-member-init): the first half written before read
807 std::array<vec, fft_most_pairs> differences; // NOLINT(cppcoreguidelines-pro-type-member-init): the same
808 const R* const at {reinterpret_cast<const R*>(in_p + q)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): a complex number is its two parts ([complex.numbers])
809 const vec x0 {fft_load(isa, at)};
810 vec total {x0};
811 for (std::size_t j {1}; j <= half; ++j) {
812 const vec x {fft_load(isa, at + (2 * j * apart))};
813 const vec y {fft_load(isa, at + (2 * (radix - j) * apart))};
814 sums[j - 1] = fft_add(x, y);
815 differences[j - 1] = fft_sub(x, y);
816 total = fft_add(total, sums[j - 1]);
817 }
818 R* const place {reinterpret_cast<R*>(to + q)}; // NOLINT(cppcoreguidelines-pro-type-reinterpret-cast): the same
820 for (std::size_t k {1}; k <= half; ++k) {
821 std::size_t power {k}; // j·k mod r, kept by additions
822 vec cosines {fft_fused(fft_splat(isa, roots[power].real()), sums[0], x0)};
823 vec sines {fft_mul(fft_splat(isa, -roots[power].imag()), differences[0])};
824 for (std::size_t j {2}; j <= half; ++j) {
825 power += k;
826 power -= power >= radix ? radix : 0;
827 cosines = fft_fused(fft_splat(isa, roots[power].real()), sums[j - 1], cosines);
828 sines = fft_fused(fft_splat(isa, -roots[power].imag()), differences[j - 1], sines);
829 }
830 const vec i_sines {fft_times_i(sines)};
831 fft_store_twiddled<Isa>(place + (2 * stride * k), fft_sub(cosines, i_sines), twiddles, run, p, k);
832 fft_store_twiddled<Isa>(place + (2 * stride * (radix - k)), fft_add(cosines, i_sines), twiddles, run, p, radix - k);
833 }
834 }
835 }
836 if constexpr (!Isa::whole_strides) {
837 for (; q < stride; ++q) { // a stride narrower than a register
838 std::array<C, fft_most_pairs> sums {};
839 std::array<C, fft_most_pairs> differences {};
840 const C x0 {in_p[q]};
841 C total {x0};
842 for (std::size_t j {1}; j <= half; ++j) {
843 const C x {in_p[q + (j * apart)]};
844 const C y {in_p[q + ((radix - j) * apart)]};
845 sums[j - 1] = x + y;
846 differences[j - 1] = x - y;
847 total = total + sums[j - 1];
848 }
849 to[q] = total;
850 for (std::size_t k {1}; k <= half; ++k) {
851 std::size_t power {k};
852 C cosines {fft_scaled_add(x0, roots[power].real(), sums[0])};
853 C sines {-roots[power].imag() * differences[0].real(), -roots[power].imag() * differences[0].imag()};
854 for (std::size_t j {2}; j <= half; ++j) {
855 power += k;
856 power -= power >= radix ? radix : 0;
857 cosines = fft_scaled_add(cosines, roots[power].real(), sums[j - 1]);
858 sines = fft_scaled_add(sines, -roots[power].imag(), differences[j - 1]);
859 }
860 const C i_sines {-sines.imag(), sines.real()};
861 const C low {cosines - i_sines};
862 const C high {cosines + i_sines};
863 to[q + (stride * k)] = p == 0 ? low : fft_fused_product(twiddles[((k - 1) * run) + p - 1], low);
864 to[q + (stride * (radix - k))] = p == 0 ? high : fft_fused_product(twiddles[((radix - k - 1) * run) + p - 1], high);
865 }
866 }
867 }
868 }
869 }
870
871#endif
872
873#if defined(NUMERICAL_X86_COMPILED)
875 template <typename R>
876 NUMERICAL_TARGET("avx2,fma") inline void avx2_radix_four_pass(std::size_t current,
877 std::size_t stride,
878 const std::complex<R>* in,
879 std::complex<R>* out,
880 const std::complex<R>* twiddles) noexcept
881 {
883 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
884 }
885
887 template <typename R>
888 NUMERICAL_TARGET("avx512f,avx2,fma") inline void avx512_radix_four_pass(std::size_t current,
889 std::size_t stride,
890 const std::complex<R>* in,
891 std::complex<R>* out,
892 const std::complex<R>* twiddles) noexcept
893 {
895 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
896 }
897
899 template <typename R>
900 NUMERICAL_TARGET("avx2,fma") inline void avx2_radix_sixteen_pass(std::size_t current,
901 std::size_t stride,
902 const std::complex<R>* in,
903 std::complex<R>* out,
904 const std::complex<R>* twiddles,
905 const std::array<std::complex<R>, 16>& sixteenths) noexcept
906 {
907 fft_radix_sixteen_pass<fft_avx2>(current, stride, in, out, twiddles, sixteenths);
908 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
909 }
910
912 template <typename R>
913 NUMERICAL_TARGET("avx512f,avx2,fma") inline void avx512_radix_sixteen_pass(std::size_t current,
914 std::size_t stride,
915 const std::complex<R>* in,
916 std::complex<R>* out,
917 const std::complex<R>* twiddles,
918 const std::array<std::complex<R>, 16>& sixteenths) noexcept
919 {
920 if (stride % (sizeof(fft_reg<fft_avx512, R>) / sizeof(std::complex<R>)) == 0) {
921 fft_radix_sixteen_pass<fft_avx512>(current, stride, in, out, twiddles, sixteenths);
922 }
923 else {
924 fft_radix_sixteen_pass<fft_avx2>(current, stride, in, out, twiddles, sixteenths);
925 }
926 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
927 }
928
930 template <typename R>
931 NUMERICAL_TARGET("avx512f,avx2,fma") inline void avx512_radix_three_pass(std::size_t current,
932 std::size_t stride,
933 const std::complex<R>* in,
934 std::complex<R> * out,
935 const std::complex<R>* twiddles,
936 R half_root_three) noexcept
937 {
938 fft_radix_three_pass<fft_avx512>(current, stride, in, out, twiddles, half_root_three);
939 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
940 }
941
943 template <typename R>
944 NUMERICAL_TARGET("avx512f,avx2,fma") inline void avx512_radix_five_pass(std::size_t current,
945 std::size_t stride,
946 const std::complex<R>* in,
947 std::complex<R> * out,
948 const std::complex<R>* twiddles,
949 R c1,
950 R c2,
951 R s1,
952 R s2) noexcept
953 {
954 fft_radix_five_pass<fft_avx512>(current, stride, in, out, twiddles, c1, c2, s1, s2);
955 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
956 }
957
959 template <typename R>
960 NUMERICAL_TARGET("avx512f,avx2,fma") inline void avx512_radix_eight_pass(std::size_t current,
961 std::size_t stride,
962 const std::complex<R>* in,
963 std::complex<R> * out,
964 const std::complex<R>* twiddles,
965 R half_root_two) noexcept
966 {
967 fft_radix_eight_pass<fft_avx512>(current, stride, in, out, twiddles, half_root_two);
968 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
969 }
970
972 template <typename R>
973 NUMERICAL_TARGET("avx512f,avx2,fma") inline void avx512_radix_any_pass(std::size_t radix,
974 std::size_t current,
975 std::size_t stride,
976 const std::complex<R>* in,
977 std::complex<R> * out,
978 const std::complex<R>* twiddles,
979 const std::complex<R>* roots) noexcept
980 {
981 fft_radix_any_pass<fft_avx512>(radix, current, stride, in, out, twiddles, roots);
982 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
983 }
984
986 template <typename R>
987 NUMERICAL_TARGET("avx2,fma") inline void avx2_radix_any_pass(std::size_t radix,
988 std::size_t current,
989 std::size_t stride,
990 const std::complex<R>* in,
991 std::complex<R> * out,
992 const std::complex<R>* twiddles,
993 const std::complex<R>* roots) noexcept
994 {
995 fft_radix_any_pass<fft_avx2>(radix, current, stride, in, out, twiddles, roots);
996 _mm256_zeroupper(); // the upper halves cleared: code past the kernel may be SSE alone
997 }
998
999#endif
1000
1001#if defined(NUMERICAL_NEON_COMPILED)
1002
1004 template <typename R>
1005 void neon_radix_four_pass(std::size_t current,
1006 std::size_t stride,
1007 const std::complex<R>* in,
1008 std::complex<R>* out,
1009 const std::complex<R>* twiddles) noexcept
1010 {
1012 }
1013
1015 template <typename R>
1016 void neon_radix_sixteen_pass(std::size_t current,
1017 std::size_t stride,
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
1022 {
1023 fft_radix_sixteen_pass<fft_neon>(current, stride, in, out, twiddles, sixteenths);
1024 }
1025
1027 template <typename R>
1028 void neon_radix_three_pass(std::size_t current,
1029 std::size_t stride,
1030 const std::complex<R>* in,
1031 std::complex<R> * out,
1032 const std::complex<R>* twiddles,
1033 R half_root_three) noexcept
1034 {
1035 fft_radix_three_pass<fft_neon>(current, stride, in, out, twiddles, half_root_three);
1036 }
1037
1039 template <typename R>
1040 void neon_radix_five_pass(std::size_t current,
1041 std::size_t stride,
1042 const std::complex<R>* in,
1043 std::complex<R> * out,
1044 const std::complex<R>* twiddles,
1045 R c1,
1046 R c2,
1047 R s1,
1048 R s2) noexcept
1049 {
1050 fft_radix_five_pass<fft_neon>(current, stride, in, out, twiddles, c1, c2, s1, s2);
1051 }
1052
1054 template <typename R>
1055 void neon_radix_eight_pass(std::size_t current,
1056 std::size_t stride,
1057 const std::complex<R>* in,
1058 std::complex<R> * out,
1059 const std::complex<R>* twiddles,
1060 R half_root_two) noexcept
1061 {
1062 fft_radix_eight_pass<fft_neon>(current, stride, in, out, twiddles, half_root_two);
1063 }
1064
1066 template <typename R>
1067 void neon_radix_any_pass(std::size_t radix,
1068 std::size_t current,
1069 std::size_t stride,
1070 const std::complex<R>* in,
1071 std::complex<R>* out,
1072 const std::complex<R>* twiddles,
1073 const std::complex<R>* roots) noexcept
1074 {
1075 fft_radix_any_pass<fft_neon>(radix, current, stride, in, out, twiddles, roots);
1076 }
1077
1078#endif
1079} // namespace numerical::detail
1080
1081#endif // NUMERICAL_FFT_KERNELS_HPP
The matrix product kernel behind matrix * matrix and the einsum matmul path.
#define NUMERICAL_UNROLL_BLOCK
Definition gemm.hpp:72
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
Definition simd.hpp:25
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.