GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 96.6% 254 / 0 / 263
Functions: 100.0% 25 / 0 / 25
Branches: 83.1% 133 / 61 / 221
fft/engines/split.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <algorithm>
4 #include <cassert>
5 #include <cmath>
6 #include <cstdint>
7 #include <span>
8 #include <utility>
9 #include <vector>
10
11 #include "fft/core.hpp"
12 #include "fft/engine.hpp"
13
14 namespace ecnerwala::fft::engines {
15
16 // Multiplies mod `mnum` by splitting values into balanced 15-bit halves (each limb in
17 // [-2^14, 2^14], from the balanced representative |v| <= MOD/2) packed into one complex
18 // transform per operand.
19 template <typename mnum> struct split {
20 static_assert(sizeof(decltype(mnum::MOD)) <= 4, "limbs must fit 15 bits");
21 using value_type = mnum;
22 static constexpr bool commutative = true;
23 static constexpr int unit_scale = 1;
24 using cnum = cplx<double>;
25 using core = fft_core<cnum>;
26
2/6
✓ Branch 8 → 9 taken 48 times.
✗ Branch 8 → 13 not taken.
✗ Branch 90 → 91 not taken.
✓ Branch 97 → 98 taken 20 times.
✗ Branch 118 → 119 not taken.
✗ Branch 125 → 126 not taken.
 8853 template <int A = 1> struct transformed_t {
27 vector<cnum> v;
28 16146 int size() const { return sz(v); }
29 102 transformed_t() = default;
30 3 explicit transformed_t(vector<cnum>&& v_) : v(std::move(v_)) {}
31 ✗ template <int A2> requires (A2 != A) explicit(A2 > A) transformed_t(transformed_t<A2>&& o)
32 ✗ : v(std::move(o.v)) {}
33 };
34 using transformed = transformed_t<1>;
35 48 template <int K> struct product_t {
36 // After finish's inverse transforms: lo = (lo*lo, hi*lo), hi = (lo*hi, hi*hi).
37 vector<cnum> lo, hi;
38 3811 int size() const { return sz(lo); }
39 ✗ product_t() = default;
40 104 product_t(vector<cnum>&& lo_, vector<cnum>&& hi_) : lo(std::move(lo_)), hi(std::move(hi_)) {}
41 20 template <int K2> requires (K2 != K) explicit(K2 > K) product_t(product_t<K2>&& o)
42 20 : lo(std::move(o.lo)), hi(std::move(o.hi)) {}
43 };
44 using product = product_t<1>;
45
46
2/2
✓ Branch 2 → 3 taken 11556440 times.
✓ Branch 2 → 4 taken 10521129 times.
 22098826 static cnum pack(mnum x) {
47 22098826 int64_t v = x.balanced();
48 22098826 int64_t hi = (v + (1 << 14)) >> 15;
49 22098826 return cnum(double(v - (hi << 15)), double(hi));
50 }
51
52 2923 static transformed transform(std::span<const mnum> a, int n) {
53 2923 assert(sz(a) <= 2 * n);
54 2923 transformed r;
55
2/2
✓ Branch 4 → 5 taken 96 times.
✓ Branch 14 → 15 taken 2827 times.
 2923 r.v.assign(n, cnum(0));
56
4/4
✓ Branch 9 → 6 taken 22077569 times.
✓ Branch 9 → 10 taken 96 times.
✓ Branch 40 → 17 taken 21177 times.
✓ Branch 40 → 41 taken 2827 times.
 22101669 for (int i = 0; i < sz(a); i++) {
57
4/4
✓ Branch 6 → 7 taken 4 times.
✓ Branch 6 → 8 taken 22077565 times.
✓ Branch 17 → 18 taken 139 times.
✓ Branch 17 → 19 taken 21038 times.
 22098746 int j = i < n ? i : i - n;
58 22098746 r.v[j] = r.v[j] + pack(a[i]);
59 }
60
3/4
✗ Branch 10 → 11 not taken.
✓ Branch 10 → 12 taken 96 times.
✓ Branch 12 → 13 taken 96 times.
✓ Branch 44 → 45 taken 2827 times.
 2923 core::forward(std::span<cnum>(r.v));
61 2923 return r;
62 }
63 3035 static void extend_to(transformed& t, int m, std::span<const mnum> coeffs) {
64 3035 assert(!(m & (m-1)) && sz(coeffs) <= 2 * m);
65
3/4
✓ Branch 5 → 6 taken 96 times.
✗ Branch 5 → 24 not taken.
✓ Branch 11 → 12 taken 1939 times.
✓ Branch 11 → 112 taken 1000 times.
 8002 if (t.size() >= m) return;
66
4/5
✓ Branch 6 → 7 taken 96 times.
✗ Branch 6 → 11 not taken.
✓ Branch 17 → 18 taken 1932 times.
✓ Branch 17 → 46 taken 7 times.
✓ Branch 19 → 20 taken 1932 times.
 7934 if (t.size() == 0) { t = transform(coeffs, m); return; }
67
1/1
✓ Branch 48 → 65 taken 7 times.
 7 auto buf = buffer_pool<cnum>::get(sz(coeffs));
68
2/4
✗ Branch 13 → 12 not taken.
✗ Branch 13 → 21 not taken.
✓ Branch 66 → 49 taken 80 times.
✓ Branch 66 → 104 taken 7 times.
 87 for (int i = 0; i < sz(coeffs); i++) buf[i] = pack(coeffs[i]);
69
2/4
✗ Branch 21 → 14 not taken.
✗ Branch 21 → 22 not taken.
✓ Branch 109 → 67 taken 10 times.
✓ Branch 109 → 110 taken 7 times.
 34 while (t.size() < m) {
70 10 int s = t.size();
71
1/2
✗ Branch 14 → 15 not taken.
✓ Branch 74 → 75 taken 10 times.
 10 t.v.resize(2 * s);
72 // coeffs past 2s are zero: they didn't fit in the transform we're a prefix of
73
1/3
✗ Branch 17 → 18 not taken.
✗ Branch 17 → 19 not taken.
✓ Branch 98 → 99 taken 10 times.
 20 core::extend(
74
0/3
✗ Branch 17 → 18 not taken.
✗ Branch 17 → 19 not taken.
✗ Branch 19 → 20 not taken.
 10 std::span<cnum>(t.v),
75
0/2
✗ Branch 17 → 18 not taken.
✗ Branch 17 → 19 not taken.
 30 std::span<const cnum>(buf.span()).first(size_t(min(sz(coeffs), 2 * s)))
76 );
77 }
78 7 }
79 588 static void downsample_core(std::span<const cnum> in, std::span<cnum> out, bool odd) {
80
2/2
✓ Branch 2 → 3 taken 198 times.
✓ Branch 2 → 4 taken 390 times.
 588 if (odd) core::odd_half(in, out);
81 390 else core::even_half(in, out);
82 588 }
83 ✗ template <int A> static transformed_t<A> downsample(const transformed_t<A>& t, int n, bool odd) {
84 ✗ transformed_t<A> r; r.v.resize(n);
85 ✗ downsample_core(std::span<const cnum>(t.v), std::span<cnum>(r.v), odd);
86 ✗ return r;
87 }
88 294 template <int K> static product_t<K> downsample(const product_t<K>& p, int n, bool odd) {
89
2/2
✓ Branch 11 → 12 taken 294 times.
✓ Branch 14 → 15 taken 294 times.
 294 product_t<K> r; r.lo.resize(n); r.hi.resize(n);
90
1/1
✓ Branch 23 → 24 taken 294 times.
 294 downsample_core(std::span<const cnum>(p.lo), std::span<cnum>(r.lo), odd);
91
1/1
✓ Branch 37 → 38 taken 294 times.
 294 downsample_core(std::span<const cnum>(p.hi), std::span<cnum>(r.hi), odd);
92 294 return r;
93 }
94 164 template <int A> static transformed_t<A> negate_arg(const transformed_t<A>& t, int n) {
95 328 assert(n >= 2 && t.size() >= n);
96
1/1
✓ Branch 16 → 29 taken 164 times.
 164 transformed_t<A> r; r.v.resize(n);
97
2/2
✓ Branch 29 → 17 taken 3526 times.
✓ Branch 29 → 30 taken 164 times.
 3690 for (int j = 0; j < n; j++) r.v[j] = t.v[j ^ 1];
98 164 return r;
99 }
100 3 template <int A, int B> static transformed_t<A + B> add(transformed_t<A>&& a, const transformed_t<B>& b) {
101 3 transformed_t<A + B> r{std::move(a.v)};
102 3 add_into(r.v, b.v);
103 return r;
104 }
105 // Unpacks b's transform into transforms of its low/high halves via conjugate
106 // symmetry, then multiplies both against a's (still packed) transform. The scale
107 // parameter only affects the bookkeeping, so the body is a shared untyped impl.
108 5382 static void mul_impl(const vector<cnum>& a, const vector<cnum>& b, vector<cnum>& lo, vector<cnum>& hi, int n, bool acc = false) {
109 5382 core::init(n);
110 5382 lo.resize(n); hi.resize(n);
111
4/4
ecnerwala::fft::engines::split<modnum<1000000007> >::mul_impl(std::__debug::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&, std::__debug::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&, std::__debug::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&, std::__debug::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&, int, bool):
✓ Branch 116 → 8 taken 51874 times.
✓ Branch 116 → 117 taken 5334 times.
ecnerwala::fft::engines::split<modnum<1000000007> >::mul_impl(std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&, std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&, std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&, std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&, int, bool):
✓ Branch 12 → 6 taken 24699142 times.
✓ Branch 12 → 13 taken 48 times.
 24756398 for (int i = 0; i < n; i++) {
112
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24751016 int ci = core::conj_index(i);
113
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24751016 cnum g0 = (b[i] + conj(b[ci])) * cnum(0.5);
114
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24751016 cnum t = (b[i] - conj(b[ci])) * cnum(0.5);
115 24751016 cnum g1 = cnum(t.y, -t.x);
116
3/4
ecnerwala::fft::engines::split<modnum<1000000007> >::mul_impl(std::__debug::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&, std::__debug::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&, std::__debug::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&, std::__debug::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&, int, bool):
✓ Branch 44 → 45 taken 5228 times.
✓ Branch 44 → 85 taken 46646 times.
ecnerwala::fft::engines::split<modnum<1000000007> >::mul_impl(std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&, std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > > const&, std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&, std::vector<ecnerwala::fft::cplx<double>, std::allocator<ecnerwala::fft::cplx<double> > >&, int, bool):
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24751016 if (acc) {
117 5228 lo[i] = lo[i] + a[i] * g0;
118 5228 hi[i] = hi[i] + a[i] * g1;
119 } else {
120 24745788 lo[i] = a[i] * g0;
121 24745788 hi[i] = a[i] * g1;
122 }
123 }
124 5382 }
125 1860 template <int A, int B> static product_t<A * B> mul(const transformed_t<A>& a, const transformed_t<B>& b, int n) {
126 5484 assert(a.size() >= n && b.size() >= n);
127 1860 product_t<A * B> p;
128
3/3
ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<(1)*(1)> ecnerwala::fft::engines::split<modnum<1000000007> >::mul<1, 1>(ecnerwala::fft::engines::split<modnum<1000000007> >::transformed_t<1> const&, ecnerwala::fft::engines::split<modnum<1000000007> >::transformed_t<1> const&, int):
✓ Branch 5 → 6 taken 48 times.
✓ Branch 32 → 33 taken 1809 times.
ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<(2)*(1)> ecnerwala::fft::engines::split<modnum<1000000007> >::mul<2, 1>(ecnerwala::fft::engines::split<modnum<1000000007> >::transformed_t<2> const&, ecnerwala::fft::engines::split<modnum<1000000007> >::transformed_t<1> const&, int):
✓ Branch 32 → 33 taken 3 times.
 1860 mul_impl(a.v, b.v, p.lo, p.hi, n);
129 1860 return p;
130 }
131 23 template <int A> static product_t<A * A> sq(const transformed_t<A>& a, int n) { return mul(a, a, n); }
132 template <int A1, int B1, int A2, int B2>
133 1761 static product_t<A1 * B1 + A2 * B2> mul2(
134 const transformed_t<A1>& a1, const transformed_t<B1>& b1,
135 const transformed_t<A2>& a2, const transformed_t<B2>& b2,
136 int n
137 ) {
138 8805 assert(a1.size() >= n && b1.size() >= n && a2.size() >= n && b2.size() >= n);
139 1761 product_t<A1 * B1 + A2 * B2> p;
140
1/1
✓ Branch 44 → 45 taken 1761 times.
 1761 mul_impl(a1.v, b1.v, p.lo, p.hi, n);
141
1/1
✓ Branch 54 → 55 taken 1761 times.
 1761 mul_impl(a2.v, b2.v, p.lo, p.hi, n, true);
142 1761 return p;
143 }
144 211 static void add_into(vector<cnum>& a, const vector<cnum>& b) {
145 211 assert(sz(a) == sz(b));
146
2/2
✓ Branch 27 → 6 taken 5504 times.
✓ Branch 27 → 28 taken 211 times.
 5715 for (int i = 0; i < sz(a); i++) a[i] = a[i] + b[i];
147 211 }
148 104 template <int K1, int K2> static product_t<K1 + K2> add(product_t<K1>&& a, product_t<K2>&& b) {
149 104 product_t<K1 + K2> r{std::move(a.lo), std::move(a.hi)};
150 104 add_into(r.lo, b.lo);
151 104 add_into(r.hi, b.hi);
152 104 return r;
153 }
154 3523 template <int K = 1, typename Op = assign_op> static void finish(product_t<K>&& p, std::span<mnum> out, Op op = {}) {
155 // The fp error budget is divided by the accumulated scale; K <= 2 is very
156 // conservative (balanced limbs already left ~2x headroom at max lengths).
157 static_assert(K <= 2, "split: accumulated scale too large");
158 3523 int n = p.size();
159 3523 assert(sz(out) <= n);
160
12/14
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 14 → 15 taken 238 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 14 → 15 taken 558 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 14 → 15 taken 84 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 14 → 15 taken 6 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 8 times.
✓ Branch 14 → 15 taken 12 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 40 times.
✓ Branch 14 → 15 taken 689 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 14 → 15 taken 1192 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 14 → 15 taken 84 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 14 → 15 taken 5 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 14 → 15 taken 607 times.
 3523 core::inverse(std::span<cnum>(p.lo));
161
12/14
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 21 → 22 taken 238 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 21 → 22 taken 558 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 21 → 22 taken 84 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 21 → 22 taken 6 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 8 times.
✓ Branch 21 → 22 taken 12 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 40 times.
✓ Branch 21 → 22 taken 689 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 21 → 22 taken 1192 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 21 → 22 taken 84 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 21 → 22 taken 5 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 21 → 22 taken 607 times.
 3523 core::inverse(std::span<cnum>(p.hi));
162 3523 const int64_t m = mnum::MOD;
163 3523 double d = 1.0 / double(n);
164 // llround + a final wrap so negative half-products (e.g. from negate_arg'd
165 // transforms) reconstruct correctly.
166
24/24
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 60 → 24 taken 938 times.
✓ Branch 60 → 61 taken 238 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 62 → 24 taken 12989 times.
✓ Branch 62 → 63 taken 558 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 60 → 24 taken 168 times.
✓ Branch 60 → 61 taken 84 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 60 → 24 taken 12 times.
✓ Branch 60 → 61 taken 6 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 16 → 11 taken 20 times.
✓ Branch 16 → 17 taken 8 times.
✓ Branch 60 → 24 taken 111 times.
✓ Branch 60 → 61 taken 12 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 14 → 11 taken 22077493 times.
✓ Branch 14 → 15 taken 40 times.
✓ Branch 61 → 24 taken 16392 times.
✓ Branch 61 → 62 taken 689 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 62 → 24 taken 3296 times.
✓ Branch 62 → 63 taken 1192 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 60 → 24 taken 168 times.
✓ Branch 60 → 61 taken 84 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 60 → 24 taken 139 times.
✓ Branch 60 → 61 taken 5 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 61 → 24 taken 4631 times.
✓ Branch 61 → 62 taken 607 times.
 22119880 for (int i = 0; i < sz(out); i++) {
167
4/4
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 11 → 12 taken 10 times.
✓ Branch 11 → 13 taken 10 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 11 → 12 taken 4745039 times.
✓ Branch 11 → 13 taken 17332454 times.
 22116357 int64_t v = (llround(p.lo[i].x * d)
168 22116357 + (llround(p.lo[i].y * d) % m << 15)
169 22116357 + (llround(p.hi[i].x * d) % m << 15)
170 22116357 + (llround(p.hi[i].y * d) % m << 30)) % m;
171
24/24
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 48 → 49 taken 489 times.
✓ Branch 48 → 50 taken 449 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 48 → 49 taken 5280 times.
✓ Branch 48 → 50 taken 7709 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 48 → 49 taken 89 times.
✓ Branch 48 → 50 taken 79 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 48 → 49 taken 3 times.
✓ Branch 48 → 50 taken 9 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 11 → 12 taken 10 times.
✓ Branch 11 → 13 taken 10 times.
✓ Branch 48 → 49 taken 52 times.
✓ Branch 48 → 50 taken 59 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 11 → 12 taken 4745039 times.
✓ Branch 11 → 13 taken 17332454 times.
✓ Branch 48 → 49 taken 6938 times.
✓ Branch 48 → 50 taken 9454 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 48 → 49 taken 1617 times.
✓ Branch 48 → 50 taken 1679 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 48 → 49 taken 89 times.
✓ Branch 48 → 50 taken 79 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 48 → 49 taken 69 times.
✓ Branch 48 → 50 taken 70 times.
void ecnerwala::fft::engines::split<modnum<1000000007> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::split<modnum<1000000007> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 48 → 49 taken 1991 times.
✓ Branch 48 → 50 taken 2640 times.
 22116357 if (v < 0) v += m;
172 22192509 op(out[i], mnum(v));
173 }
174 3523 }
175 };
176
177 /* namespace ecnerwala::fft::engines */ }
178