GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 98.2% 268 / 0 / 273
Functions: 100.0% 28 / 0 / 28
Branches: 84.0% 142 / 63 / 232
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 wala::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.
 9021 template <int A = 1> struct transformed_t {
27 vector<cnum> v;
28 16257 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 3865 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.
 22100588 static cnum pack(mnum x) {
47 22100588 int64_t v = x.balanced();
48 22100588 int64_t hi = (v + (1 << 14)) >> 15;
49 22100588 return cnum(double(v - (hi << 15)), double(hi));
50 }
51
52 2989 static transformed transform(std::span<const mnum> a, int n) {
53 2989 assert(sz(a) <= 2 * n);
54 2989 transformed r;
55
2/2
✓ Branch 4 → 5 taken 96 times.
✓ Branch 14 → 15 taken 2893 times.
 2989 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 22939 times.
✓ Branch 40 → 41 taken 2893 times.
 22103497 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 231 times.
✓ Branch 17 → 19 taken 22708 times.
 22100508 int j = i < n ? i : i - n;
58 22100508 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 2893 times.
 2989 core::forward(std::span<cnum>(r.v));
61 2989 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 12 template <int A> static transformed_t<A> downsample(const transformed_t<A>& t, int n, bool odd) {
80
1/1
✓ Branch 8 → 9 taken 12 times.
 12 transformed_t<A> r; r.v.resize(n);
81
1/1
✓ Branch 17 → 18 taken 12 times.
 12 core::downsample(std::span<const cnum>(t.v), std::span<cnum>(r.v), odd);
82 12 return r;
83 }
84 294 template <int K> static product_t<K> downsample(const product_t<K>& p, int n, bool odd) {
85
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);
86
1/1
✓ Branch 23 → 24 taken 294 times.
 294 core::downsample(std::span<const cnum>(p.lo), std::span<cnum>(r.lo), odd);
87
1/1
✓ Branch 37 → 38 taken 294 times.
 294 core::downsample(std::span<const cnum>(p.hi), std::span<cnum>(r.hi), odd);
88 294 return r;
89 }
90 6 template <int A> static transformed_t<A> upsample(const transformed_t<A>& t, int n, bool odd) {
91
1/1
✓ Branch 8 → 9 taken 6 times.
 6 transformed_t<A> r; r.v.resize(n);
92
1/1
✓ Branch 17 → 18 taken 6 times.
 6 core::upsample(std::span<const cnum>(t.v), std::span<cnum>(r.v), odd);
93 6 return r;
94 }
95 6 template <int K> static product_t<K> upsample(const product_t<K>& p, int n, bool odd) {
96
2/2
✓ Branch 11 → 12 taken 6 times.
✓ Branch 14 → 15 taken 6 times.
 6 product_t<K> r; r.lo.resize(n); r.hi.resize(n);
97
1/1
✓ Branch 23 → 24 taken 6 times.
 6 core::upsample(std::span<const cnum>(p.lo), std::span<cnum>(r.lo), odd);
98
1/1
✓ Branch 37 → 38 taken 6 times.
 6 core::upsample(std::span<const cnum>(p.hi), std::span<cnum>(r.hi), odd);
99 6 return r;
100 }
101 164 template <int A> static transformed_t<A> negate_arg(const transformed_t<A>& t, int n) {
102 328 assert(n >= 2 && t.size() >= n);
103
1/1
✓ Branch 16 → 29 taken 164 times.
 164 transformed_t<A> r; r.v.resize(n);
104
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];
105 164 return r;
106 }
107 15 template <int A> static transformed_t<A> of_reverse(const transformed_t<A>& t, int n) {
108 30 assert(t.size() >= n);
109
1/1
✓ Branch 15 → 29 taken 15 times.
 15 transformed_t<A> r; r.v.resize(n);
110
2/2
✓ Branch 29 → 16 taken 261 times.
✓ Branch 29 → 30 taken 15 times.
 276 for (int j = 0; j < n; j++) r.v[j] = t.v[core::conj_index(j)];
111 15 return r;
112 }
113 3 template <int A, int B> static transformed_t<A + B> add(transformed_t<A>&& a, const transformed_t<B>& b) {
114 3 transformed_t<A + B> r{std::move(a.v)};
115 3 add_into(r.v, b.v);
116 return r;
117 }
118 // Unpacks b's transform into transforms of its low/high halves via conjugate
119 // symmetry, then multiplies both against a's (still packed) transform. The scale
120 // parameter only affects the bookkeeping, so the body is a shared untyped impl.
121 5430 static void mul_impl(const vector<cnum>& a, const vector<cnum>& b, vector<cnum>& lo, vector<cnum>& hi, int n, bool acc = false) {
122 5430 core::init(n);
123 5430 lo.resize(n); hi.resize(n);
124
4/4
wala::fft::engines::split<wala::modnum<1000000007> >::mul_impl(std::__debug::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > > const&, std::__debug::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > > const&, std::__debug::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > >&, std::__debug::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > >&, int, bool):
✓ Branch 116 → 8 taken 53365 times.
✓ Branch 116 → 117 taken 5382 times.
wala::fft::engines::split<wala::modnum<1000000007> >::mul_impl(std::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > > const&, std::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > > const&, std::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > >&, std::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > >&, int, bool):
✓ Branch 12 → 6 taken 24699142 times.
✓ Branch 12 → 13 taken 48 times.
 24757937 for (int i = 0; i < n; i++) {
125
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24752507 int ci = core::conj_index(i);
126
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24752507 cnum g0 = (b[i] + conj(b[ci])) * cnum(0.5);
127
1/2
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24752507 cnum t = (b[i] - conj(b[ci])) * cnum(0.5);
128 24752507 cnum g1 = cnum(t.y, -t.x);
129
3/4
wala::fft::engines::split<wala::modnum<1000000007> >::mul_impl(std::__debug::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > > const&, std::__debug::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > > const&, std::__debug::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > >&, std::__debug::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > >&, int, bool):
✓ Branch 44 → 45 taken 5228 times.
✓ Branch 44 → 85 taken 48137 times.
wala::fft::engines::split<wala::modnum<1000000007> >::mul_impl(std::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > > const&, std::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > > const&, std::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > >&, std::vector<wala::fft::cplx<double>, std::allocator<wala::fft::cplx<double> > >&, int, bool):
✗ Branch 8 → 9 not taken.
✓ Branch 8 → 10 taken 24699142 times.
 24752507 if (acc) {
130 5228 lo[i] = lo[i] + a[i] * g0;
131 5228 hi[i] = hi[i] + a[i] * g1;
132 } else {
133 24747279 lo[i] = a[i] * g0;
134 24747279 hi[i] = a[i] * g1;
135 }
136 }
137 5430 }
138 1908 template <int A, int B> static product_t<A * B> mul(const transformed_t<A>& a, const transformed_t<B>& b, int n) {
139 5628 assert(a.size() >= n && b.size() >= n);
140 1908 product_t<A * B> p;
141
3/3
wala::fft::engines::split<wala::modnum<1000000007> >::product_t<(1)*(1)> wala::fft::engines::split<wala::modnum<1000000007> >::mul<1, 1>(wala::fft::engines::split<wala::modnum<1000000007> >::transformed_t<1> const&, wala::fft::engines::split<wala::modnum<1000000007> >::transformed_t<1> const&, int):
✓ Branch 5 → 6 taken 48 times.
✓ Branch 32 → 33 taken 1857 times.
wala::fft::engines::split<wala::modnum<1000000007> >::product_t<(2)*(1)> wala::fft::engines::split<wala::modnum<1000000007> >::mul<2, 1>(wala::fft::engines::split<wala::modnum<1000000007> >::transformed_t<2> const&, wala::fft::engines::split<wala::modnum<1000000007> >::transformed_t<1> const&, int):
✓ Branch 32 → 33 taken 3 times.
 1908 mul_impl(a.v, b.v, p.lo, p.hi, n);
142 1908 return p;
143 }
144 23 template <int A> static product_t<A * A> sq(const transformed_t<A>& a, int n) { return mul(a, a, n); }
145 template <int A1, int B1, int A2, int B2>
146 1761 static product_t<A1 * B1 + A2 * B2> mul2(
147 const transformed_t<A1>& a1, const transformed_t<B1>& b1,
148 const transformed_t<A2>& a2, const transformed_t<B2>& b2,
149 int n
150 ) {
151 8805 assert(a1.size() >= n && b1.size() >= n && a2.size() >= n && b2.size() >= n);
152 1761 product_t<A1 * B1 + A2 * B2> p;
153
1/1
✓ Branch 44 → 45 taken 1761 times.
 1761 mul_impl(a1.v, b1.v, p.lo, p.hi, n);
154
1/1
✓ Branch 54 → 55 taken 1761 times.
 1761 mul_impl(a2.v, b2.v, p.lo, p.hi, n, true);
155 1761 return p;
156 }
157 211 static void add_into(vector<cnum>& a, const vector<cnum>& b) {
158 211 assert(sz(a) == sz(b));
159
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];
160 211 }
161 104 template <int K1, int K2> static product_t<K1 + K2> add(product_t<K1>&& a, product_t<K2>&& b) {
162 104 product_t<K1 + K2> r{std::move(a.lo), std::move(a.hi)};
163 104 add_into(r.lo, b.lo);
164 104 add_into(r.hi, b.hi);
165 104 return r;
166 }
167 3577 template <int K = 1, typename Op = assign_op> static void finish(product_t<K>&& p, std::span<mnum> out, Op op = {}) {
168 // The fp error budget is divided by the accumulated scale; K <= 2 is very
169 // conservative (balanced limbs already left ~2x headroom at max lengths).
170 static_assert(K <= 2, "split: accumulated scale too large");
171 3577 int n = p.size();
172 3577 assert(sz(out) <= n);
173
12/14
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 14 → 15 taken 238 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::add_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 14 → 15 taken 558 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 14 → 15 taken 84 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 14 → 15 taken 6 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 8 times.
✓ Branch 14 → 15 taken 12 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✗ Branch 4 → 5 not taken.
✓ Branch 4 → 6 taken 40 times.
✓ Branch 14 → 15 taken 743 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::add_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 14 → 15 taken 1192 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 14 → 15 taken 84 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 14 → 15 taken 5 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 14 → 15 taken 607 times.
 3577 core::inverse(std::span<cnum>(p.lo));
174
12/14
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 21 → 22 taken 238 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::add_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 21 → 22 taken 558 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 21 → 22 taken 84 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 21 → 22 taken 6 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 8 times.
✓ Branch 21 → 22 taken 12 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✗ Branch 7 → 8 not taken.
✓ Branch 7 → 9 taken 40 times.
✓ Branch 21 → 22 taken 743 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::add_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 21 → 22 taken 1192 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 21 → 22 taken 84 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 21 → 22 taken 5 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 21 → 22 taken 607 times.
 3577 core::inverse(std::span<cnum>(p.hi));
175 3577 const int64_t m = mnum::MOD;
176 3577 double d = 1.0 / double(n);
177 // llround + a final wrap so negative half-products (e.g. from negate_arg'd
178 // transforms) reconstruct correctly.
179
24/24
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 60 → 24 taken 938 times.
✓ Branch 60 → 61 taken 238 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::add_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 62 → 24 taken 12989 times.
✓ Branch 62 → 63 taken 558 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 60 → 24 taken 168 times.
✓ Branch 60 → 61 taken 84 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 60 → 24 taken 12 times.
✓ Branch 60 → 61 taken 6 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::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 wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 14 → 11 taken 22077493 times.
✓ Branch 14 → 15 taken 40 times.
✓ Branch 61 → 24 taken 18211 times.
✓ Branch 61 → 62 taken 743 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::add_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 62 → 24 taken 3296 times.
✓ Branch 62 → 63 taken 1192 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 60 → 24 taken 168 times.
✓ Branch 60 → 61 taken 84 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 60 → 24 taken 139 times.
✓ Branch 60 → 61 taken 5 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 61 → 24 taken 4631 times.
✓ Branch 61 → 62 taken 607 times.
 22121753 for (int i = 0; i < sz(out); i++) {
180
4/4
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 11 → 12 taken 10 times.
✓ Branch 11 → 13 taken 10 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 11 → 12 taken 4745039 times.
✓ Branch 11 → 13 taken 17332454 times.
 22118176 int64_t v = (llround(p.lo[i].x * d)
181 22118176 + (llround(p.lo[i].y * d) % m << 15)
182 22118176 + (llround(p.hi[i].x * d) % m << 15)
183 22118176 + (llround(p.hi[i].y * d) % m << 30)) % m;
184
24/24
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 48 → 49 taken 466 times.
✓ Branch 48 → 50 taken 472 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::add_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 48 → 49 taken 5260 times.
✓ Branch 48 → 50 taken 7729 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 48 → 49 taken 82 times.
✓ Branch 48 → 50 taken 86 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 48 → 49 taken 4 times.
✓ Branch 48 → 50 taken 8 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 11 → 12 taken 10 times.
✓ Branch 11 → 13 taken 10 times.
✓ Branch 48 → 49 taken 50 times.
✓ Branch 48 → 50 taken 61 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<1, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 11 → 12 taken 4745039 times.
✓ Branch 11 → 13 taken 17332454 times.
✓ Branch 48 → 49 taken 7599 times.
✓ Branch 48 → 50 taken 10612 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::add_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 48 → 49 taken 1640 times.
✓ Branch 48 → 50 taken 1656 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 48 → 49 taken 87 times.
✓ Branch 48 → 50 taken 81 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 48 → 49 taken 62 times.
✓ Branch 48 → 50 taken 77 times.
void wala::fft::engines::split<wala::modnum<1000000007> >::finish<2, wala::fft::assign_op>(wala::fft::engines::split<wala::modnum<1000000007> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 48 → 49 taken 1940 times.
✓ Branch 48 → 50 taken 2691 times.
 22118176 if (v < 0) v += m;
185 22197966 op(out[i], mnum(v));
186 }
187 3577 }
188 };
189
190 } // namespace wala::fft::engines
191