#include "transfer.h"
#include <cassert>
#include <cstdio>
std::vector<int> get_attachment(std::vector<int> source) {
int r = 0, n = (int) source.size();
while ((1 << r) < n + r + 1) ++r;
std::vector<int> message(n + r);
int ptr = 0;
for (int i = 0; i < (int) message.size(); ++i)
if (__builtin_popcount(i + 1) != 1)
message[i] = source[ptr++];
else
message[i] = 0;
assert(ptr == n);
for (int i = 0; i < (int) message.size(); ++i) {
if (__builtin_popcount(i + 1) == 1) continue;
for (int j = 0; j <= r; ++j)
if ((i + 1) & (1 << j))
message[(1 << j) - 1] ^= message[i];
}
std::vector<int> attach;
for (int i = 0; i < (int) message.size(); ++i)
if (__builtin_popcount(i + 1) == 1)
attach.push_back(message[i]);
return attach;
}
std::vector<int> retrieve(std::vector<int> _data) {
int r = 0, n = (int) _data.size();
while ((1 << r) < n + r + 1) { ++r; --n; }
assert(n + r == (int) _data.size());
std::vector<int> data(n + r);
int ptr = 0;
for (int i = 0; i < (int) _data.size(); ++i)
if (__builtin_popcount(i + 1) != 1) data[i] = _data[ptr++];
for (int i = 0; i < (int) _data.size(); ++i)
if (__builtin_popcount(i + 1) == 1) data[i] = _data[ptr++];
int fix = 0;
for (int i = 0; i < (int) data.size(); ++i) {
if (__builtin_popcount(i + 1) == 1) continue;
for (int j = 0; (1 << j) <= i + 1; ++j) {
if ((i + 1) & (1 << j))
data[(1 << j) - 1] ^= data[i];
}
}
for (int i = 0; i < (int) data.size(); ++i)
if (__builtin_popcount(i + 1) == 1 && data[i] == 1)
fix += i + 1;
if (fix != 0)
data[fix - 1] ^= 1;
std::vector<int> message;
for (int i = 0; i < (int) data.size(); ++i)
if (__builtin_popcount(i + 1) != 1)
message.push_back(data[i]);
return message;
}
