blob: 7d24dd31ea8bee050739c3f0b05a55ef24fe8a8d (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
|
#include <iostream>
#include <string_view>
using namespace std;
namespace {
size_t
smallest_dragon_length(string_view start_bits, size_t disc_size)
{
auto length = start_bits.size();
while ( length < disc_size ) {
length = 2 * length + 1;
}
return length;
}
char
bit_at(size_t pos, size_t total_length, string_view start_bits)
{
size_t inversions = 0;
auto invert_if_needed = [&](char chr) {
if ( (inversions % 2) == 1 ) {
return (chr == '0') ? '1' : '0';
}
else {
return chr;
}
};
while ( total_length > start_bits.size() ) {
auto prev_length = (total_length - 1) / 2;
if ( pos == prev_length ) {
return invert_if_needed('0');
}
else if ( pos > prev_length ) {
pos = prev_length - 1 - (pos - prev_length - 1);
inversions++;
total_length = prev_length;
}
else {
total_length = prev_length;
}
}
auto bit = start_bits[pos];
return invert_if_needed(bit);
}
void
checksum(string_view start_bits, size_t disc_size)
{
auto data_length = smallest_dragon_length(start_bits, disc_size);
string bits;
for ( size_t i = 0; i != disc_size; ++i ) {
bits += bit_at(i, data_length, start_bits);
}
while ( bits.size() % 2 == 0 ) {
string new_bits;
for ( size_t i = 0; i != bits.size(); i += 2 ) {
new_bits += (bits[i] == bits[i + 1]) ? '1' : '0';
}
bits = std::move(new_bits);
}
cout << bits << '\n';
}
} // namespace
int
main()
{
// checksum("10000", 20);
checksum("00111101111101000", 272);
checksum("00111101111101000", 35651584);
}
|
