src/edh/hamming/lib.hpp
| Line | Branch | Exec | Source |
|---|---|---|---|
| 1 | #pragma once | ||
| 2 | |||
| 3 | #include "../../ds/dbitset/lib.hpp" | ||
| 4 | |||
| 5 | namespace tifa_libs { | ||
| 6 | |||
| 7 | class hamming { | ||
| 8 | 38 | static CEXP u32 get_m(u64 n) NE { | |
| 9 | 38 | u32 m = (u32)std::bit_width(n); | |
| 10 |
2/2✓ Branch 1 taken 11 times.
✓ Branch 2 taken 27 times.
|
38 | if ((1_u64 << m) - m - 1 < n) ++m; |
| 11 | 38 | return m; | |
| 12 | } | ||
| 13 | 75 | static CEXP auto get_nm(u64 len) NE { | |
| 14 | 75 | cu32 m = (u32)std::bit_width(len - 1); | |
| 15 | 75 | return std::make_pair(len - m - 1, m); | |
| 16 | } | ||
| 17 | |||
| 18 | public: | ||
| 19 | 38 | static CEXP auto encode(dbitset CR msg) NE { | |
| 20 | 38 | cu64 n = msg.size(), m = get_m(n), len = n + m + 1; | |
| 21 | 38 | dbitset code(len); | |
| 22 |
2/2✓ Branch 0 taken 9512460 times.
✓ Branch 1 taken 38 times.
|
9512498 | flt_ (u64, i, 1, len, j = 0) |
| 23 |
2/2✓ Branch 1 taken 9512158 times.
✓ Branch 2 taken 302 times.
|
9512460 | if (!std::has_single_bit(i)) code.set(i, msg[j++]); |
| 24 | 38 | u64 _ = 0; | |
| 25 |
2/2✓ Branch 2 taken 4754501 times.
✓ Branch 3 taken 38 times.
|
4754539 | for (u64 j = code.find_next(0); j < len; j = code.find_next(j)) _ ^= j; |
| 26 |
2/2✓ Branch 0 taken 302 times.
✓ Branch 1 taken 38 times.
|
340 | for (u64 i = 1; i < len; i *= 2) |
| 27 |
2/2✓ Branch 0 taken 165 times.
✓ Branch 1 taken 137 times.
|
302 | if (_ & i) code.flip(i); |
| 28 | 38 | code.set(0, code.parity()); | |
| 29 | 38 | return code; | |
| 30 | } | ||
| 31 | template <bool err_correction = false> // == true -> auto correction if possible | ||
| 32 | 75 | static CEXP auto decode(dbitset& code) NE { | |
| 33 | 75 | auto const [n, m] = get_nm(code.size()); | |
| 34 | 75 | std::optional<dbitset> ret; | |
| 35 | if CEXP (err_correction) { | ||
| 36 | 37 | usz err = 0; | |
| 37 |
2/2✓ Branch 3 taken 4754667 times.
✓ Branch 4 taken 37 times.
|
4754704 | for (u64 i = code.find_next(0); i < code.size(); i = code.find_next(i)) err ^= i; |
| 38 |
1/2✓ Branch 0 taken 37 times.
✗ Branch 1 not taken.
|
37 | if (err) { |
| 39 |
1/2✗ Branch 1 not taken.
✓ Branch 2 taken 37 times.
|
37 | retif_((!code.parity()), ret); |
| 40 | 37 | code.flip(err); | |
| 41 | } | ||
| 42 | } | ||
| 43 | 75 | dbitset ans(n); | |
| 44 | 75 | dbitset::word_t _ = 0; | |
| 45 | 75 | u32 wj = 0; | |
| 46 |
4/4auto tifa_libs::hamming::decode<false>(tifa_libs::dbitset&):
✓ Branch 1 taken 9512460 times.
✓ Branch 2 taken 38 times.
auto tifa_libs::hamming::decode<true>(tifa_libs::dbitset&):
✓ Branch 1 taken 9512460 times.
✓ Branch 2 taken 37 times.
|
19024995 | flt_ (u64, i, 1, code.size(), j = 0) { |
| 47 |
4/4auto tifa_libs::hamming::decode<false>(tifa_libs::dbitset&):
✓ Branch 1 taken 302 times.
✓ Branch 2 taken 9512158 times.
auto tifa_libs::hamming::decode<true>(tifa_libs::dbitset&):
✓ Branch 1 taken 302 times.
✓ Branch 2 taken 9512158 times.
|
19024920 | if (std::has_single_bit(i)) continue; |
| 48 |
4/4auto tifa_libs::hamming::decode<false>(tifa_libs::dbitset&):
✓ Branch 1 taken 4754501 times.
✓ Branch 2 taken 4757657 times.
auto tifa_libs::hamming::decode<true>(tifa_libs::dbitset&):
✓ Branch 1 taken 4754501 times.
✓ Branch 2 taken 4757657 times.
|
19024316 | if (code[i]) _ |= ((dbitset::word_t)1 << j); |
| 49 |
4/4auto tifa_libs::hamming::decode<false>(tifa_libs::dbitset&):
✓ Branch 0 taken 148618 times.
✓ Branch 1 taken 9363540 times.
auto tifa_libs::hamming::decode<true>(tifa_libs::dbitset&):
✓ Branch 0 taken 148618 times.
✓ Branch 1 taken 9363540 times.
|
19024316 | if (++j == dbitset::word_width) ans.raw()[wj++] = _, j = _ = 0; |
| 50 | } | ||
| 51 |
4/4auto tifa_libs::hamming::decode<false>(tifa_libs::dbitset&):
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 8 times.
auto tifa_libs::hamming::decode<true>(tifa_libs::dbitset&):
✓ Branch 0 taken 30 times.
✓ Branch 1 taken 7 times.
|
75 | if (_) ans.raw()[wj] = _; |
| 52 | if CEXP (err_correction) { | ||
| 53 | 37 | ret.emplace(ans); | |
| 54 | 37 | return ret; | |
| 55 | 38 | } else return ans; | |
| 56 | 75 | } | |
| 57 | }; | ||
| 58 | } // namespace tifa_libs | ||
| 59 |