GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 98.9% 273 / 0 / 276
Functions: 100.0% 25 / 0 / 25
Branches: 93.4% 183 / 26 / 222
fft/engines/crt.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include <cassert>
4 #include <cstdint>
5 #include <span>
6 #include <utility>
7
8 #include "fft/engine.hpp"
9 #include "fft/engines/ntt.hpp"
10 #include "num/modnum.hpp"
11
12 namespace wala::fft::engines {
13
14 // Multiplies mod `mnum` by running NTTs modulo two FFT-friendly primes and CRT'ing.
15 // Inputs use balanced representatives (|v| <= MOD/2), so the true integer coefficients
16 // are bounded by n (MOD/2)^2.
17 template <typename mnum, typename num1 = mod_goldilocks, typename num2 = modnum<(15 << 27) + 1>>
18 struct crt {
19 static_assert(sizeof(decltype(mnum::MOD)) <= 4, "n (MOD/2)^2 must fit the CRT modulus product");
20 using value_type = mnum;
21 static constexpr bool commutative = true;
22 static constexpr int unit_scale = 1;
23 using E1 = ntt<num1>;
24 using E2 = ntt<num2>;
25
1/2
✓ Branch 9 → 10 taken 48 times.
✗ Branch 9 → 14 not taken.
 96 template <int A = 1> struct transformed_t {
26 typename E1::transformed t1;
27 typename E2::transformed t2;
28
2/2
✓ Branch 18 → 19 taken 159 times.
✓ Branch 18 → 20 taken 58 times.
 3469 int size() const { return t1.size(); }
29 156 transformed_t() = default;
30 1161 transformed_t(typename E1::transformed&& t1_, typename E2::transformed&& t2_)
31 2322 : t1(std::move(t1_)), t2(std::move(t2_)) {}
32 ✗ template <int A2> requires (A2 != A) explicit(A2 > A) transformed_t(transformed_t<A2>&& o)
33 ✗ : t1(std::move(o.t1)), t2(std::move(o.t2)) {}
34 };
35 using transformed = transformed_t<1>;
36 48 template <int K> struct product_t {
37 typename E1::product p1;
38 typename E2::product p2;
39 3865 int size() const { return sz(p1); }
40 ✗ product_t() = default;
41 4073 product_t(typename E1::product&& p1_, typename E2::product&& p2_)
42 8098 : p1(std::move(p1_)), p2(std::move(p2_)) {}
43 20 template <int K2> requires (K2 != K) explicit(K2 > K) product_t(product_t<K2>&& o)
44 40 : p1(std::move(o.p1)), p2(std::move(o.p2)) {}
45 };
46 using product = product_t<1>;
47
48 961 static transformed transform(std::span<const mnum> a, int n) {
49 961 assert(sz(a) <= 2 * n);
50
1/1
✓ Branch 7 → 8 taken 961 times.
 961 auto b1 = buffer_pool<num1>::get(sz(a));
51
1/1
✓ Branch 10 → 42 taken 961 times.
 961 auto b2 = buffer_pool<num2>::get(sz(a));
52
2/2
✓ Branch 43 → 11 taken 15380 times.
✓ Branch 43 → 44 taken 961 times.
 62481 for (int i = 0; i < sz(a); i++) { int64_t v = a[i].balanced(); b1[i] = num1(v); b2[i] = num2(v); }
53 return transformed{
54
1/1
✓ Branch 54 → 55 taken 961 times.
 2883 E1::transform(std::span<const num1>(b1.span()), n),
55
1/1
✓ Branch 66 → 67 taken 961 times.
 2883 E2::transform(std::span<const num2>(b2.span()), n),
56 1922 };
57 961 }
58
1/2
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 96 times.
 3035 static void extend_to(transformed& t, int m, std::span<const mnum> coeffs) {
59
3/4
✗ Branch 2 → 3 not taken.
✓ Branch 2 → 4 taken 96 times.
✓ Branch 10 → 11 taken 1000 times.
✓ Branch 10 → 13 taken 1939 times.
 5974 if (t.size() >= m) return;
60
1/1
✓ Branch 15 → 16 taken 1939 times.
 2035 auto b1 = buffer_pool<num1>::get(sz(coeffs));
61
2/2
✓ Branch 5 → 15 taken 96 times.
✓ Branch 18 → 50 taken 1939 times.
 2035 auto b2 = buffer_pool<num2>::get(sz(coeffs));
62
10/10
✓ Branch 6 → 7 taken 11556440 times.
✓ Branch 6 → 8 taken 10521129 times.
✓ Branch 8 → 9 taken 11556440 times.
✓ Branch 8 → 10 taken 10521129 times.
✓ Branch 11 → 12 taken 11556440 times.
✓ Branch 11 → 13 taken 10521129 times.
✓ Branch 15 → 6 taken 22077569 times.
✓ Branch 15 → 16 taken 96 times.
✓ Branch 51 → 19 taken 7639 times.
✓ Branch 51 → 52 taken 1939 times.
 55744169 for (int i = 0; i < sz(coeffs); i++) { int64_t v = coeffs[i].balanced(); b1[i] = num1(v); b2[i] = num2(v); }
63
3/4
✓ Branch 18 → 19 taken 96 times.
✗ Branch 19 → 20 not taken.
✓ Branch 19 → 21 taken 96 times.
✓ Branch 63 → 64 taken 1939 times.
 3974 E1::extend_to(t.t1, m, std::span<const num1>(b1.span()));
64
2/2
✓ Branch 21 → 22 taken 96 times.
✓ Branch 78 → 79 taken 1939 times.
 3974 E2::extend_to(t.t2, m, std::span<const num2>(b2.span()));
65 2035 }
66 12 template <int A> static transformed_t<A> downsample(const transformed_t<A>& t, int n, bool odd) {
67
2/2
✓ Branch 6 → 7 taken 12 times.
✓ Branch 14 → 15 taken 12 times.
 48 return transformed_t<A>{E1::downsample(t.t1, n, odd), E2::downsample(t.t2, n, odd)};
68 }
69 294 template <int K> static product_t<K> downsample(const product_t<K>& p, int n, bool odd) {
70
2/2
✓ Branch 6 → 7 taken 294 times.
✓ Branch 14 → 15 taken 294 times.
 1176 return product_t<K>{E1::downsample(p.p1, n, odd), E2::downsample(p.p2, n, odd)};
71 }
72 6 template <int A> static transformed_t<A> upsample(const transformed_t<A>& t, int n, bool odd) {
73
2/2
✓ Branch 6 → 7 taken 6 times.
✓ Branch 14 → 15 taken 6 times.
 24 return transformed_t<A>{E1::upsample(t.t1, n, odd), E2::upsample(t.t2, n, odd)};
74 }
75 6 template <int K> static product_t<K> upsample(const product_t<K>& p, int n, bool odd) {
76
2/2
✓ Branch 6 → 7 taken 6 times.
✓ Branch 14 → 15 taken 6 times.
 24 return product_t<K>{E1::upsample(p.p1, n, odd), E2::upsample(p.p2, n, odd)};
77 }
78 164 template <int A> static transformed_t<A> negate_arg(const transformed_t<A>& t, int n) {
79
2/2
✓ Branch 6 → 7 taken 164 times.
✓ Branch 14 → 15 taken 164 times.
 656 return transformed_t<A>{E1::negate_arg(t.t1, n), E2::negate_arg(t.t2, n)};
80 }
81 15 template <int A> static transformed_t<A> of_reverse(const transformed_t<A>& t, int n) {
82
2/2
✓ Branch 6 → 7 taken 15 times.
✓ Branch 14 → 15 taken 15 times.
 60 return transformed_t<A>{E1::of_reverse(t.t1, n), E2::of_reverse(t.t2, n)};
83 }
84 // Exact per prime; the scale tracks the true (integer) coefficient growth.
85 3 template <int A, int B> static transformed_t<A + B> add(transformed_t<A>&& a, const transformed_t<B>& b) {
86 12 return transformed_t<A + B>{E1::add(std::move(a.t1), b.t1), E2::add(std::move(a.t2), b.t2)};
87 }
88 1908 template <int A, int B> static product_t<A * B> mul(const transformed_t<A>& a, const transformed_t<B>& b, int n) {
89
5/5
wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<(1)*(1)> wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::mul<1, 1>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::transformed_t<1> const&, wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::transformed_t<1> const&, int):
✓ Branch 3 → 4 taken 48 times.
✓ Branch 9 → 10 taken 1857 times.
✓ Branch 22 → 23 taken 1857 times.
wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<(2)*(1)> wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::mul<2, 1>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::transformed_t<2> const&, wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::transformed_t<1> const&, int):
✓ Branch 9 → 10 taken 3 times.
✓ Branch 22 → 23 taken 3 times.
 7488 return product_t<A * B>{E1::mul(a.t1, b.t1, n), E2::mul(a.t2, b.t2, n)};
90 }
91 23 template <int A> static product_t<A * A> sq(const transformed_t<A>& a, int n) { return mul(a, a, n); }
92 template <int A1, int B1, int A2, int B2>
93 1761 static product_t<A1 * B1 + A2 * B2> mul2(
94 const transformed_t<A1>& a1, const transformed_t<B1>& b1,
95 const transformed_t<A2>& a2, const transformed_t<B2>& b2,
96 int n
97 ) {
98 return product_t<A1 * B1 + A2 * B2>{
99
1/1
✓ Branch 15 → 16 taken 1761 times.
 3522 E1::mul2(a1.t1, b1.t1, a2.t1, b2.t1, n),
100
1/1
✓ Branch 38 → 39 taken 1761 times.
 3522 E2::mul2(a1.t2, b1.t2, a2.t2, b2.t2, n),
101 3522 };
102 }
103 104 template <int K1, int K2> static product_t<K1 + K2> add(product_t<K1>&& a, product_t<K2>&& b) {
104 416 return product_t<K1 + K2>{E1::add(std::move(a.p1), b.p1), E2::add(std::move(a.p2), b.p2)};
105 }
106 3577 template <int K = 1, typename Op = assign_op> static void finish(product_t<K>&& p, std::span<mnum> out, Op op = {}) {
107 // The reconstruction needs |c| < whole/2; balanced inputs bound each addend's
108 // true coefficients by n (MOD/2)^2, so the safe length is divided by the
109 // accumulated scale. K <= 2 is very conservative (~2^35 even for MOD ~ 2^30).
110 static_assert(K <= 2, "crt: accumulated scale too large");
111 3577 int n = p.size();
112 3577 assert(sz(out) <= n);
113
10/10
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 12 → 13 taken 238 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 12 → 13 taken 558 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 12 → 13 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 12 → 13 taken 6 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 12 → 13 taken 12 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 12 → 13 taken 743 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 12 → 13 taken 1192 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 12 → 13 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 12 → 13 taken 5 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 12 → 13 taken 607 times.
 3577 auto o1 = buffer_pool<num1>::get(sz(out));
114
14/16
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 15 → 16 taken 238 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 15 → 16 taken 558 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 15 → 16 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 15 → 16 taken 6 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 5 → 6 taken 8 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 8 times.
✓ Branch 15 → 16 taken 12 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 5 → 6 taken 40 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 40 times.
✓ Branch 15 → 16 taken 743 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 15 → 16 taken 1192 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 15 → 16 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 15 → 16 taken 5 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 15 → 16 taken 607 times.
 3577 auto o2 = buffer_pool<num2>::get(sz(out));
115
12/12
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 23 → 24 taken 238 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 23 → 24 taken 558 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 23 → 24 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 23 → 24 taken 6 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 8 → 9 taken 8 times.
✓ Branch 23 → 24 taken 12 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 8 → 9 taken 40 times.
✓ Branch 23 → 24 taken 743 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 23 → 24 taken 1192 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 23 → 24 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 23 → 24 taken 5 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 23 → 24 taken 607 times.
 3577 E1::finish(std::move(p.p1), o1.span());
116
12/12
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 32 → 33 taken 238 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 32 → 33 taken 558 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 32 → 33 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 32 → 33 taken 6 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::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 8 times.
✓ Branch 32 → 33 taken 12 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 11 → 12 taken 40 times.
✓ Branch 32 → 33 taken 743 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 32 → 33 taken 1192 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 32 → 33 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 32 → 33 taken 5 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 32 → 33 taken 607 times.
 3577 E2::finish(std::move(p.p2), o2.span());
117
118 // TODO: Could hardcode these
119 10635 num1 inv_n2 = inv(num1(num2::MOD));
120 10635 num2 inv_n1 = inv(num2(num1::MOD));
121 3577 __int128_t whole = __int128_t(num1::MOD) * __int128_t(num2::MOD);
122
123 3577 mnum m1_mod = mnum(num1::MOD);
124 3577 mnum m2_mod = mnum(num2::MOD);
125 3577 mnum whole_mod = m1_mod * m2_mod;
126
24/24
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 118 → 66 taken 938 times.
✓ Branch 118 → 119 taken 238 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 120 → 66 taken 12989 times.
✓ Branch 120 → 121 taken 558 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 118 → 66 taken 168 times.
✓ Branch 118 → 119 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 118 → 66 taken 12 times.
✓ Branch 118 → 119 taken 6 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 31 → 15 taken 20 times.
✓ Branch 31 → 32 taken 8 times.
✓ Branch 118 → 66 taken 111 times.
✓ Branch 118 → 119 taken 12 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 30 → 15 taken 22077493 times.
✓ Branch 30 → 31 taken 40 times.
✓ Branch 119 → 66 taken 18211 times.
✓ Branch 119 → 120 taken 743 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 120 → 66 taken 3296 times.
✓ Branch 120 → 121 taken 1192 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 118 → 66 taken 168 times.
✓ Branch 118 → 119 taken 84 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 118 → 66 taken 139 times.
✓ Branch 118 → 119 taken 5 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 119 → 66 taken 4631 times.
✓ Branch 119 → 120 taken 607 times.
 22121753 for (int i = 0; i < sz(out); i++) {
127
2/4
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 20 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 22077493 times.
 22158839 num1 v1 = o1[i] * inv_n2;
128
2/4
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 20 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 22077493 times.
 22158839 num2 v2 = o2[i] * inv_n1;
129
6/8
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 20 times.
✓ Branch 18 → 19 taken 7 times.
✓ Branch 18 → 20 taken 13 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 22077493 times.
✓ Branch 18 → 19 taken 10618902 times.
✓ Branch 18 → 20 taken 11458591 times.
 44277015 mnum o_mod = mnum(uint64_t(v1)) * m2_mod + mnum(int(v2)) * m1_mod;
130 22118176 __int128_t o_exact = __int128_t(uint64_t(v1)) * __int128_t(num2::MOD) + __int128_t(int(v2)) * __int128_t(num1::MOD);
131
27/28
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 106 → 107 taken 460 times.
✓ Branch 106 → 108 taken 478 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 106 → 107 taken 5356 times.
✓ Branch 106 → 108 taken 7633 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 106 → 107 taken 75 times.
✓ Branch 106 → 108 taken 93 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 106 → 107 taken 10 times.
✓ Branch 106 → 108 taken 2 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 21 → 22 taken 10 times.
✓ Branch 21 → 25 taken 10 times.
✗ Branch 22 → 23 not taken.
✓ Branch 22 → 24 taken 10 times.
✓ Branch 106 → 107 taken 49 times.
✓ Branch 106 → 108 taken 62 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 21 → 22 taken 17321289 times.
✓ Branch 21 → 25 taken 4756204 times.
✓ Branch 22 → 23 taken 1520120 times.
✓ Branch 22 → 24 taken 15801169 times.
✓ Branch 106 → 107 taken 7807 times.
✓ Branch 106 → 108 taken 10404 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 106 → 107 taken 1708 times.
✓ Branch 106 → 108 taken 1588 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 106 → 107 taken 78 times.
✓ Branch 106 → 108 taken 90 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 106 → 107 taken 73 times.
✓ Branch 106 → 108 taken 66 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 106 → 107 taken 1979 times.
✓ Branch 106 → 108 taken 2652 times.
 22118176 if (o_exact >= whole) { o_exact -= whole; o_mod -= whole_mod; }
132 // Balanced representatives: |o| <= whole/2
133
24/24
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_twice_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_twice_op):
✓ Branch 108 → 109 taken 478 times.
✓ Branch 108 → 110 taken 460 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 108 → 109 taken 5197 times.
✓ Branch 108 → 110 taken 7792 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_twice_op>):
✓ Branch 108 → 109 taken 93 times.
✓ Branch 108 → 110 taken 75 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 108 → 109 taken 2 times.
✓ Branch 108 → 110 taken 10 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 25 → 26 taken 10 times.
✓ Branch 25 → 29 taken 10 times.
✓ Branch 108 → 109 taken 62 times.
✓ Branch 108 → 110 taken 49 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<1, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<1>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 25 → 26 taken 4744924 times.
✓ Branch 25 → 29 taken 17332569 times.
✓ Branch 108 → 109 taken 7744 times.
✓ Branch 108 → 110 taken 10467 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::add_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::add_op):
✓ Branch 108 → 109 taken 1588 times.
✓ Branch 108 → 110 taken 1708 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::add_op>):
✓ Branch 108 → 109 taken 90 times.
✓ Branch 108 → 110 taken 78 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op> >(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::detail::cut_op<wala::modnum<1000000007>, wala::fft::assign_op>):
✓ Branch 108 → 109 taken 66 times.
✓ Branch 108 → 110 taken 73 times.
void wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::finish<2, wala::fft::assign_op>(wala::fft::engines::crt<wala::modnum<1000000007>, wala::mod_goldilocks, wala::modnum<2013265921> >::product_t<2>&&, std::span<wala::modnum<1000000007>, 18446744073709551615ul>, wala::fft::assign_op):
✓ Branch 108 → 109 taken 1956 times.
✓ Branch 108 → 110 taken 2675 times.
 22118176 if (o_exact > whole / 2) o_mod -= whole_mod;
134 22157303 op(out[i], o_mod);
135 }
136 7106 }
137 };
138
139 } // namespace wala::fft::engines
140