GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 55 / 0 / 55
Functions: 100.0% 2 / 0 / 2
Branches: 84.8% 56 / 0 / 66
src/conv/add/u64/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../trans/fft_r3/lib.hpp"
4 #include "../naive/lib.hpp"
5
6 namespace tifa_libs {
7
8 template <class T>
9 44 vecuu conv_u64(vec<T> CR a, vec<T> CR b, u32 ans_size = 0) NE {
10 44 cu32 n = (u32)a.size(), m = (u32)b.size();
11
1/2
✓ Branch 0 taken 44 times.
✗ Branch 1 not taken.
 44 if (!ans_size) ans_size = n + m - 1;
12
2/6
✗ Branch 1 not taken.
✓ Branch 2 taken 44 times.
✗ Branch 4 not taken.
✗ Branch 5 not taken.
✗ Branch 6 not taken.
✓ Branch 7 taken 44 times.
 44 retif_((a.empty() && b.empty()) [[unlikely]], {});
13
2/2
✓ Branch 1 taken 18 times.
✓ Branch 2 taken 26 times.
 44 if (min(n, m) < CONV_NAIVE_THRESHOLD) return conv_naive<T, u64>(a, b, ans_size);
14
2/4
✓ Branch 0 taken 26 times.
✗ Branch 1 not taken.
✓ Branch 3 taken 26 times.
✗ Branch 4 not taken.
 26 static fft_r3<T> fft;
15 using EI = fft_r3<T>::data_t;
16 CEXP static EI inv_3{-T(1) / 3 * 2 + 1, 0};
17 26 fft.bzr(n + m - 1);
18 26 u32 s = fft.size();
19 78 vec<EI> pa(s), pb(s);
20
2/2
✓ Branch 4 taken 7492161 times.
✓ Branch 5 taken 26 times.
 7492187 for (u32 i = 0; i < min(s, n); ++i) pa[i].real(a[i]);
21
1/2
✗ Branch 4 not taken.
✓ Branch 5 taken 26 times.
 26 for (u32 i = s; i < min(2 * s, n); ++i) pa[i - s].imag(a[i]);
22
2/2
✓ Branch 4 taken 7797725 times.
✓ Branch 5 taken 26 times.
 7797751 for (u32 i = 0; i < min(s, m); ++i) pb[i].real(b[i]);
23
2/2
✓ Branch 4 taken 3392 times.
✓ Branch 5 taken 26 times.
 3418 for (u32 i = s; i < min(2 * s, m); ++i) pb[i - s].imag(b[i]);
24 26 vec<EI> pc(4 * s);
25 1693250 auto mul = [](auto&& mul, EI* p, EI* q, EI* to, u32 n) {
26
2/2
✓ Branch 0 taken 1662120 times.
✓ Branch 1 taken 31130 times.
 1693250 if (n <= 27) {
27 1662120 fill_n(to, n, 0);
28
2/2
✓ Branch 0 taken 44719776 times.
✓ Branch 1 taken 1662120 times.
 46381896 flt_ (u32, i, 0, n) {
29
2/2
✓ Branch 2 taken 625368276 times.
✓ Branch 3 taken 44719776 times.
 670088052 flt_ (u32, j, 0, n - i) to[i + j] += p[i] * q[j];
30
2/2
✓ Branch 3 taken 580648500 times.
✓ Branch 4 taken 44719776 times.
 625368276 flt_ (u32, j, n - i, n) to[i + j - n] += p[i] * q[j] * EI::w;
31 }
32 1662120 return;
33 }
34 31130 u32 m = 1;
35
2/2
✓ Branch 0 taken 92976 times.
✓ Branch 1 taken 31130 times.
 124106 for (; m * m < n; m *= 3);
36 31130 u32 r = n / m;
37 31130 EI inv{1};
38
2/2
✓ Branch 1 taken 92973 times.
✓ Branch 2 taken 31130 times.
 124103 for (u32 i = 1; i < r; i *= 3) inv *= inv_3;
39
2/2
✓ Branch 0 taken 846612 times.
✓ Branch 1 taken 31130 times.
 877742 flt_ (u32, i, 0, r) {
40 846612 fft.twiddle(p + m * i, m, m / r * i, to + m * i);
41 846612 fft.twiddle(q + m * i, m, m / r * i, to + n + m * i);
42 }
43 31130 fft.dif(to, m, r), fft.dif(to + n, m, r);
44
3/4
✓ Branch 1 taken 846612 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 846612 times.
✓ Branch 4 taken 31130 times.
 877742 flt_ (u32, i, 0, r) mul(mul, to + m * i, to + n + m * i, to + 2 * n + m * i, m);
45 31130 fft.dit(to + 2 * n, m, r);
46
2/2
✓ Branch 1 taken 33539832 times.
✓ Branch 2 taken 31130 times.
 33570962 flt_ (u32, i, 0, n) to[2 * n + i] *= inv;
47
2/2
✓ Branch 1 taken 846612 times.
✓ Branch 2 taken 31130 times.
 877742 flt_ (u32, i, 0, r) fft.twiddle(to + 2 * n + m * i, m, 3 * m - m / r * i, to + n + m * i);
48
2/2
✓ Branch 0 taken 846612 times.
✓ Branch 1 taken 31130 times.
 877742 flt_ (u32, i, 0, r) {
49
2/2
✓ Branch 2 taken 33539832 times.
✓ Branch 3 taken 846612 times.
 34386444 flt_ (u32, j, 0, m) p[m * i + j] = conj(p[m * i + j]), q[m * i + j] = conj(q[m * i + j]);
50 846612 fft.twiddle(p + m * i, m, 2 * m / r * i, to + m * i);
51 846612 fft.twiddle(q + m * i, m, 2 * m / r * i, p + m * i);
52 }
53 31130 fft.dif(to, m, r), fft.dif(p, m, r);
54
3/4
✓ Branch 1 taken 846612 times.
✗ Branch 2 not taken.
✓ Branch 3 taken 846612 times.
✓ Branch 4 taken 31130 times.
 877742 flt_ (u32, i, 0, r) mul(mul, to + m * i, p + m * i, to + 2 * n + m * i, m);
55 31130 fft.dit(to + 2 * n, m, r);
56
2/2
✓ Branch 1 taken 33539832 times.
✓ Branch 2 taken 31130 times.
 33570962 flt_ (u32, i, 0, n) to[2 * n + i] *= inv;
57
2/2
✓ Branch 1 taken 846612 times.
✓ Branch 2 taken 31130 times.
 877742 flt_ (u32, i, 0, r) fft.twiddle(to + 2 * n + m * i, m, 3 * m - 2 * m / r * i, q + m * i);
58 31130 fill_n(to, n, 0);
59
2/2
✓ Branch 0 taken 33539832 times.
✓ Branch 1 taken 31130 times.
 33570962 flt_ (u32, i, 0, n) {
60 33539832 to[i] += (1 - EI::w) * to[n + i] + (1 - EI::w2) * conj(q[i]);
61
2/2
✓ Branch 0 taken 32691762 times.
✓ Branch 1 taken 848070 times.
 33539832 if (i + m < n) to[i + m] += (EI::w2 - EI::w) * (to[n + i] - conj(q[i]));
62 848070 else to[i + m - n] += (1 - EI::w2) * (to[n + i] - conj(q[i]));
63 }
64
2/2
✓ Branch 1 taken 33539832 times.
✓ Branch 2 taken 31130 times.
 33570962 flt_ (u32, i, 0, n) to[i] *= inv_3;
65 };
66 26 mul(mul, pa.data(), pb.data(), pc.data(), s);
67 26 vec<T> ans(ans_size);
68
2/2
✓ Branch 4 taken 10866317 times.
✓ Branch 5 taken 26 times.
 10866343 flt_ (u32, i, 0, min(s, ans_size)) ans[i] = pc[i].real();
69
2/2
✓ Branch 4 taken 4426935 times.
✓ Branch 5 taken 26 times.
 4426961 flt_ (u32, i, s, min(2 * s, ans_size)) ans[i] = pc[i - s].imag();
70 26 return ans;
71 26 }
72
73 } // namespace tifa_libs
74