GCC Code Coverage Report

Directory: ./
Coverage: low: ≥ 0% medium: ≥ 75.0% high: ≥ 90.0%
Coverage Exec / Excl / Total
Lines: 100.0% 67 / 0 / 67
Functions: 100.0% 10 / 0 / 10
Branches: 96.3% 52 / 0 / 54
src/lalg/basis/z2/lib.hpp
Line Branch Exec Source
1 #pragma once
2
3 #include "../../../util/alias/others/lib.hpp"
4 #include "../../../util/bitset_getdata/lib.hpp"
5
6 namespace tifa_libs {
7
8 template <u32 N = 64, bool greedy_insert = false>
9 struct basis_z2 {
10 vec<std::bitset<N>> basis;
11
12 15982170 CEXP basis_z2() NE : basis(N) {}
13
14 198935265 CEXP bool insert(std::bitset<N> x) NE {
15 198935265 bool status = false;
16 if CEXP (greedy_insert) { // greedy
17
1/2
✓ Branch 0 taken 623266369 times.
✗ Branch 1 not taken.
 623266369 for (u32 i = N - 1; ~i; --i)
18
2/2
✓ Branch 3 taken 274332348 times.
✓ Branch 4 taken 348934021 times.
 623266369 if (x[i]) {
19
2/2
✓ Branch 2 taken 38482216 times.
✓ Branch 3 taken 235850132 times.
 274332348 if (basis[i].none()) basis[i] = x;
20
2/2
✓ Branch 3 taken 38482216 times.
✓ Branch 4 taken 235850132 times.
 274332348 if ((x ^= basis[i]).none()) {
21 38482216 status = true;
22 38482216 break;
23 }
24 }
25 } else { // GE
26
3/4
tifa_libs::basis_z2<32u, false>::insert(std::bitset<32ul>):
✓ Branch 0 taken 1151520836 times.
✗ Branch 1 not taken.
tifa_libs::basis_z2<64u, false>::insert(std::bitset<64ul>):
✓ Branch 0 taken 3129601766 times.
✓ Branch 1 taken 12660728 times.
 4293783330 for (u32 i = N - 1; ~i; --i)
27
4/4
tifa_libs::basis_z2<32u, false>::insert(std::bitset<32ul>):
✓ Branch 3 taken 507084112 times.
✓ Branch 4 taken 644436724 times.
tifa_libs::basis_z2<64u, false>::insert(std::bitset<64ul>):
✓ Branch 3 taken 614110074 times.
✓ Branch 4 taken 2515491692 times.
 4281122602 if (x[i]) {
28
4/4
tifa_libs::basis_z2<32u, false>::insert(std::bitset<32ul>):
✓ Branch 4 taken 436245194 times.
✓ Branch 5 taken 70838918 times.
tifa_libs::basis_z2<64u, false>::insert(std::bitset<64ul>):
✓ Branch 4 taken 537156671 times.
✓ Branch 5 taken 76953403 times.
 1121194186 if (basis[i][i]) x ^= basis[i];
29 else {
30
4/4
tifa_libs::basis_z2<32u, false>::insert(std::bitset<32ul>):
✓ Branch 0 taken 1115324540 times.
✓ Branch 1 taken 70838918 times.
tifa_libs::basis_z2<64u, false>::insert(std::bitset<64ul>):
✓ Branch 0 taken 2605702618 times.
✓ Branch 1 taken 76953403 times.
 3868819479 flt_ (u32, j, 0, i)
31
4/4
tifa_libs::basis_z2<32u, false>::insert(std::bitset<32ul>):
✓ Branch 3 taken 557684414 times.
✓ Branch 4 taken 557640126 times.
tifa_libs::basis_z2<64u, false>::insert(std::bitset<64ul>):
✓ Branch 3 taken 999837209 times.
✓ Branch 4 taken 1605865409 times.
 3721027158 if (x[j]) x ^= basis[j];
32
4/4
tifa_libs::basis_z2<32u, false>::insert(std::bitset<32ul>):
✓ Branch 1 taken 1080681918 times.
✓ Branch 2 taken 70838918 times.
tifa_libs::basis_z2<64u, false>::insert(std::bitset<64ul>):
✓ Branch 1 taken 2242361771 times.
✓ Branch 2 taken 76953403 times.
 3470836010 flt_ (u32, j, i + 1, (u32)basis.size())
33
4/4
tifa_libs::basis_z2<32u, false>::insert(std::bitset<32ul>):
✓ Branch 4 taken 436216160 times.
✓ Branch 5 taken 644465758 times.
tifa_libs::basis_z2<64u, false>::insert(std::bitset<64ul>):
✓ Branch 4 taken 566474052 times.
✓ Branch 5 taken 1675887719 times.
 3323043689 if (basis[j][i]) basis[j] ^= x;
34 147792321 basis[i] = x, status = true;
35 147792321 break;
36 }
37 }
38 }
39 198935265 return status;
40 }
41 CEXP bool test(std::bitset<N> x) CNE {
42 for (u32 i = N - 1; ~i; --i) {
43 if (!(x[i])) continue;
44 if (basis[i][i]) x ^= basis[i];
45 else return false;
46 }
47 return true;
48 }
49 ND CEXP u32 rank() CNE {
50 u32 res = 0;
51 flt_ (u32, i, 0, (u32)basis.size()) res += basis[i][i];
52 return res;
53 }
54 CEXP std::bitset<N> max_spn() CNE {
55 std::bitset<N> ret;
56 for (auto&& i : basis) ret ^= i;
57 return ret;
58 }
59 // @return std::nullopt if x is linear independent with current basis, else return the solution
60 CEXP auto coord(std::bitset<N> x) NE {
61 std::optional res{std::bitset<N>{}};
62 for (u32 i = basis.size() - 1; ~i; --i)
63 if (x[i]) {
64 if (!basis[i][i]) {
65 res = std::nullopt;
66 return res;
67 }
68 res->set(i), x ^= basis[i];
69 }
70 return res;
71 }
72 3196434 friend basis_z2 meet(basis_z2 CR l, vec<std::bitset<N>> CR r) NE {
73 if CEXP (greedy_insert) { // Zassenhaus, 2x slower with GE insertion
74 using bslo = bitset_getdata<N>;
75 using bshi = bitset_getdata<N * 2>;
76 using word_t = TPN bslo::word_t;
77 1598217 basis_z2<N * 2> tmp;
78 1598217 CEXP auto Nw = bslo::Nw;
79
2/2
✓ Branch 5 taken 51142944 times.
✓ Branch 6 taken 1598217 times.
 52741161 for (auto CR i : l.basis) {
80 51142944 std::bitset<N * 2> now;
81 if CEXP (bshi::Nw > 1) {
82 memcpy(bshi::getdata(now), bslo::getdata(i), Nw * sizeof(word_t));
83 memcpy(bshi::getdata(now) + Nw, bslo::getdata(i), Nw * sizeof(word_t));
84 51142944 } else bshi::getword(now, 0) = bslo::getword(i, 0) << N | bslo::getword(i, 0);
85 51142944 tmp.insert(now);
86 }
87
2/2
✓ Branch 5 taken 38471187 times.
✓ Branch 6 taken 1598217 times.
 40069404 for (auto CR i : r) {
88 38471187 std::bitset<N * 2> now;
89 if CEXP (bshi::Nw > 1) memcpy(bshi::getdata(now) + Nw, bslo::getdata(i), Nw * sizeof(word_t));
90 38471187 else bshi::getword(now, 0) = bslo::getword(i, 0) << N;
91 38471187 tmp.insert(now);
92 }
93 1598217 basis_z2 ans;
94
2/2
✓ Branch 4 taken 51142944 times.
✓ Branch 5 taken 1598217 times.
 52741161 flt_ (u32, i, 0, N) memcpy(bslo::getdata(ans.basis[i]), bshi::getdata(tmp.basis[i]), Nw * sizeof(word_t));
95 1598217 return ans;
96 1598217 } else { //! will get wrong result with greedy insertion
97 2612308144 auto cvt = [](cT_(std::bitset<N>) x) NE {
98 2612308144 if CEXP (N <= 32) return x.to_ulong();
99 else if CEXP (N <= 64) return x.to_ullong();
100 else return x.to_string();
101 };
102 40069404 auto f = [&](std::bitset<N> x) NE {
103
2/2
✓ Branch 5 taken 1231077984 times.
✓ Branch 6 taken 38471187 times.
 1269549171 for (auto i : l.basis)
104
2/2
✓ Branch 3 taken 502623055 times.
✓ Branch 4 taken 728454929 times.
 1231077984 if (auto y = x ^ i; cvt(y) < cvt(x)) x = y;
105 38471187 return x;
106 };
107 1598217 basis_z2<N> ans;
108
2/2
✓ Branch 5 taken 38471187 times.
✓ Branch 6 taken 1598217 times.
 40069404 for (vecpt<std::bitset<N>> ab; auto x : r) {
109 38471187 auto y = f(x), xy = y ^ x;
110
2/2
✓ Branch 7 taken 75076088 times.
✓ Branch 8 taken 38471187 times.
 113547275 for (auto [a, b] : ab)
111
2/2
✓ Branch 3 taken 37536990 times.
✓ Branch 4 taken 37539098 times.
 75076088 if (auto _ = y ^ b; cvt(_) < cvt(y)) y = _, xy ^= a;
112
2/2
✓ Branch 1 taken 6114485 times.
✓ Branch 2 taken 32356702 times.
 38471187 if (y.any()) ab.emplace_back(xy, y);
113 32356702 else ans.insert(xy);
114 }
115 1598217 return ans;
116 1598217 }
117 }
118 };
119
120 } // namespace tifa_libs
121