GCC Code Coverage Report

Directory: src/
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 98.1% 265 / 0 / 270
Functions: 100.0% 21 / 0 / 21
Branches: 93.1% 175 / 26 / 214
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 "modnum.hpp"
11
12 namespace ecnerwala::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 1062 transformed_t(typename E1::transformed&& t1_, typename E2::transformed&& t2_)
31 2124 : 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 3811 int size() const { return sz(p1); }
40 ✗ product_t() = default;
41 4019 product_t(typename E1::product&& p1_, typename E2::product&& p2_)
42 7990 : 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 895 static transformed transform(std::span<const mnum> a, int n) {
49 895 assert(sz(a) <= 2 * n);
50
1/1
✓ Branch 7 → 8 taken 895 times.
 895 auto b1 = buffer_pool<num1>::get(sz(a));
51
1/1
✓ Branch 10 → 42 taken 895 times.
 895 auto b2 = buffer_pool<num2>::get(sz(a));
52
2/2
✓ Branch 43 → 11 taken 13618 times.
✓ Branch 43 → 44 taken 895 times.
 55367 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 895 times.
 2685 E1::transform(std::span<const num1>(b1.span()), n),
55
1/1
✓ Branch 66 → 67 taken 895 times.
 2685 E2::transform(std::span<const num2>(b2.span()), n),
56 1790 };
57 895 }
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 ✗ template <int A> static transformed_t<A> downsample(const transformed_t<A>& t, int n, bool odd) {
67 ✗ 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 164 template <int A> static transformed_t<A> negate_arg(const transformed_t<A>& t, int n) {
73
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)};
74 }
75 // Exact per prime; the scale tracks the true (integer) coefficient growth.
76 3 template <int A, int B> static transformed_t<A + B> add(transformed_t<A>&& a, const transformed_t<B>& b) {
77 12 return transformed_t<A + B>{E1::add(std::move(a.t1), b.t1), E2::add(std::move(a.t2), b.t2)};
78 }
79 1860 template <int A, int B> static product_t<A * B> mul(const transformed_t<A>& a, const transformed_t<B>& b, int n) {
80
5/5
ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<(1)*(1)> ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::mul<1, 1>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::transformed_t<1> const&, ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::transformed_t<1> const&, int):
✓ Branch 3 → 4 taken 48 times.
✓ Branch 9 → 10 taken 1809 times.
✓ Branch 22 → 23 taken 1809 times.
ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<(2)*(1)> ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::mul<2, 1>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::transformed_t<2> const&, ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::transformed_t<1> const&, int):
✓ Branch 9 → 10 taken 3 times.
✓ Branch 22 → 23 taken 3 times.
 7296 return product_t<A * B>{E1::mul(a.t1, b.t1, n), E2::mul(a.t2, b.t2, n)};
81 }
82 23 template <int A> static product_t<A * A> sq(const transformed_t<A>& a, int n) { return mul(a, a, n); }
83 template <int A1, int B1, int A2, int B2>
84 1761 static product_t<A1 * B1 + A2 * B2> mul2(
85 const transformed_t<A1>& a1, const transformed_t<B1>& b1,
86 const transformed_t<A2>& a2, const transformed_t<B2>& b2,
87 int n
88 ) {
89 return product_t<A1 * B1 + A2 * B2>{
90
1/1
✓ Branch 15 → 16 taken 1761 times.
 3522 E1::mul2(a1.t1, b1.t1, a2.t1, b2.t1, n),
91
1/1
✓ Branch 38 → 39 taken 1761 times.
 3522 E2::mul2(a1.t2, b1.t2, a2.t2, b2.t2, n),
92 3522 };
93 }
94 104 template <int K1, int K2> static product_t<K1 + K2> add(product_t<K1>&& a, product_t<K2>&& b) {
95 416 return product_t<K1 + K2>{E1::add(std::move(a.p1), b.p1), E2::add(std::move(a.p2), b.p2)};
96 }
97 3523 template <int K = 1, typename Op = assign_op> static void finish(product_t<K>&& p, std::span<mnum> out, Op op = {}) {
98 // The reconstruction needs |c| < whole/2; balanced inputs bound each addend's
99 // true coefficients by n (MOD/2)^2, so the safe length is divided by the
100 // accumulated scale. K <= 2 is very conservative (~2^35 even for MOD ~ 2^30).
101 static_assert(K <= 2, "crt: accumulated scale too large");
102 3523 int n = p.size();
103 3523 assert(sz(out) <= n);
104
10/10
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 12 → 13 taken 238 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 12 → 13 taken 558 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 12 → 13 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 12 → 13 taken 6 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 12 → 13 taken 12 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 12 → 13 taken 689 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 12 → 13 taken 1192 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 12 → 13 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 12 → 13 taken 5 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 12 → 13 taken 607 times.
 3523 auto o1 = buffer_pool<num1>::get(sz(out));
105
14/16
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 15 → 16 taken 238 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 15 → 16 taken 558 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 15 → 16 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 15 → 16 taken 6 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::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 ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 5 → 6 taken 40 times.
✗ Branch 6 → 7 not taken.
✓ Branch 6 → 8 taken 40 times.
✓ Branch 15 → 16 taken 689 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 15 → 16 taken 1192 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 15 → 16 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 15 → 16 taken 5 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 15 → 16 taken 607 times.
 3523 auto o2 = buffer_pool<num2>::get(sz(out));
106
12/12
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 23 → 24 taken 238 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 23 → 24 taken 558 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 23 → 24 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 23 → 24 taken 6 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 8 → 9 taken 8 times.
✓ Branch 23 → 24 taken 12 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 8 → 9 taken 40 times.
✓ Branch 23 → 24 taken 689 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 23 → 24 taken 1192 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 23 → 24 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 23 → 24 taken 5 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 23 → 24 taken 607 times.
 3523 E1::finish(std::move(p.p1), o1.span());
107
12/12
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 32 → 33 taken 238 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 32 → 33 taken 558 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 32 → 33 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 32 → 33 taken 6 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 11 → 12 taken 8 times.
✓ Branch 32 → 33 taken 12 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 11 → 12 taken 40 times.
✓ Branch 32 → 33 taken 689 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 32 → 33 taken 1192 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 32 → 33 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 32 → 33 taken 5 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 32 → 33 taken 607 times.
 3523 E2::finish(std::move(p.p2), o2.span());
108
109 // TODO: Could hardcode these
110 10473 num1 inv_n2 = inv(num1(num2::MOD));
111 10473 num2 inv_n1 = inv(num2(num1::MOD));
112 3523 __int128_t whole = __int128_t(num1::MOD) * __int128_t(num2::MOD);
113
114 3523 mnum m1_mod = mnum(num1::MOD);
115 3523 mnum m2_mod = mnum(num2::MOD);
116 3523 mnum whole_mod = m1_mod * m2_mod;
117
24/24
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 118 → 66 taken 938 times.
✓ Branch 118 → 119 taken 238 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 120 → 66 taken 12989 times.
✓ Branch 120 → 121 taken 558 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 118 → 66 taken 168 times.
✓ Branch 118 → 119 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 118 → 66 taken 12 times.
✓ Branch 118 → 119 taken 6 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::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 ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 30 → 15 taken 22077493 times.
✓ Branch 30 → 31 taken 40 times.
✓ Branch 119 → 66 taken 16392 times.
✓ Branch 119 → 120 taken 689 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 120 → 66 taken 3296 times.
✓ Branch 120 → 121 taken 1192 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 118 → 66 taken 168 times.
✓ Branch 118 → 119 taken 84 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 118 → 66 taken 139 times.
✓ Branch 118 → 119 taken 5 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 119 → 66 taken 4631 times.
✓ Branch 119 → 120 taken 607 times.
 22119880 for (int i = 0; i < sz(out); i++) {
118
2/4
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 20 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 22077493 times.
 22155201 num1 v1 = o1[i] * inv_n2;
119
2/4
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 20 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✗ Branch 15 → 16 not taken.
✓ Branch 15 → 17 taken 22077493 times.
 22155201 num2 v2 = o2[i] * inv_n1;
120
6/8
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::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 ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::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.
 44271558 mnum o_mod = mnum(uint64_t(v1)) * m2_mod + mnum(int(v2)) * m1_mod;
121 22116357 __int128_t o_exact = __int128_t(uint64_t(v1)) * __int128_t(num2::MOD) + __int128_t(int(v2)) * __int128_t(num1::MOD);
122
27/28
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 106 → 107 taken 483 times.
✓ Branch 106 → 108 taken 455 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 106 → 107 taken 5319 times.
✓ Branch 106 → 108 taken 7670 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 106 → 107 taken 81 times.
✓ Branch 106 → 108 taken 87 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 106 → 107 taken 11 times.
✓ Branch 106 → 108 taken 1 time.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::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 55 times.
✓ Branch 106 → 108 taken 56 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::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 7124 times.
✓ Branch 106 → 108 taken 9268 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 106 → 107 taken 1653 times.
✓ Branch 106 → 108 taken 1643 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 106 → 107 taken 86 times.
✓ Branch 106 → 108 taken 82 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 106 → 107 taken 101 times.
✓ Branch 106 → 108 taken 38 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 106 → 107 taken 2003 times.
✓ Branch 106 → 108 taken 2628 times.
 22116357 if (o_exact >= whole) { o_exact -= whole; o_mod -= whole_mod; }
123 // Balanced representatives: |o| <= whole/2
124
24/24
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_twice_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_twice_op):
✓ Branch 108 → 109 taken 455 times.
✓ Branch 108 → 110 taken 483 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 108 → 109 taken 5234 times.
✓ Branch 108 → 110 taken 7755 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_twice_op>):
✓ Branch 108 → 109 taken 87 times.
✓ Branch 108 → 110 taken 81 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 108 → 109 taken 1 time.
✓ Branch 108 → 110 taken 11 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 25 → 26 taken 10 times.
✓ Branch 25 → 29 taken 10 times.
✓ Branch 108 → 109 taken 56 times.
✓ Branch 108 → 110 taken 55 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<1, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<1>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 25 → 26 taken 4744924 times.
✓ Branch 25 → 29 taken 17332569 times.
✓ Branch 108 → 109 taken 6936 times.
✓ Branch 108 → 110 taken 9456 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::add_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::add_op):
✓ Branch 108 → 109 taken 1643 times.
✓ Branch 108 → 110 taken 1653 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::add_op>):
✓ Branch 108 → 109 taken 82 times.
✓ Branch 108 → 110 taken 86 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op> >(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::detail::cut_op<modnum<1000000007>, ecnerwala::fft::assign_op>):
✓ Branch 108 → 109 taken 38 times.
✓ Branch 108 → 110 taken 101 times.
void ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::finish<2, ecnerwala::fft::assign_op>(ecnerwala::fft::engines::crt<modnum<1000000007>, mod_goldilocks, modnum<2013265921> >::product_t<2>&&, std::span<modnum<1000000007>, 18446744073709551615ul>, ecnerwala::fft::assign_op):
✓ Branch 108 → 109 taken 1932 times.
✓ Branch 108 → 110 taken 2699 times.
 22116357 if (o_exact > whole / 2) o_mod -= whole_mod;
125 22153665 op(out[i], o_mod);
126 }
127 6998 }
128 };
129
130 /* namespace ecnerwala::fft::engines */ }
131