Skip to content

Instantly share code, notes, and snippets.

@hellman
Created October 11, 2016 18:00
Show Gist options
  • Save hellman/17a6903df726ef017be2afc20ebb911f to your computer and use it in GitHub Desktop.
Save hellman/17a6903df726ef017be2afc20ebb911f to your computer and use it in GitHub Desktop.
HITCON QUALS 2016 - Reverse (Reverse 500)
from binascii import crc32
def lcg_step():
global lcg
lcg = (0x5851F42D4C957F2D * lcg + 0x14057B7EF767814F) % 2**64
return lcg
def extract(val):
res = 32 + val - 95 * ((
((val - (0x58ED2308158ED231 * val >> 64)) >> 1) +
(0x58ED2308158ED231 * val >> 64)) >> 6)
return res & 0xff
buf = bytearray()
lcg = 8323979853562951413
crc = 0
print 31415926
for i in xrange(31415926):
# append a symbol
c = extract( lcg_step() )
buf.append(c)
# reverse interval
x = lcg_step() % len(buf)
y = lcg_step() % len(buf)
l, r = min(x, y), max(x, y)
print l, r
open("buf", "w").write(buf)
#include <bits/stdc++.h>
/*
g++ --std=c++11 -O3 solve.cpp -o solve && ./solve
*/
using namespace std;
typedef long long LL;
#define CONCAT3_NX(x, y, z) x ## y ## z
#define CONCAT3(x, y, z) CONCAT3_NX(x, y, z)
#define VAR(name) CONCAT3(__tmpvar__, name, __LINE__)
#define TYPE(x) __typeof(x)
// pretty for's
#define FOR(i, s, n) for (TYPE(n) i=(s), VAR(end)=(n); i < VAR(end); i++)
#define RFOR(i, s, n) for (TYPE(n) i=(n)-1, VAR(end)=(s); i >= VAR(end); i--)
#define FORN(i, n) FOR(i, 0, n)
#define RFORN(i, n) RFOR(i, 0, n)
#define FOREACH(i, v) for (auto& i: v)
uint32_t POLY = 0xedb88320L;
uint32_t HI = 1u << 31;
uint32_t LO = 1;
uint32_t ONEBYTE = (1u << 31) >> 8;
uint32_t BYTE_CRC[256];
uint32_t SHIFT_BYTES[100 * 1000 * 1000];
inline uint32_t poly_mul(uint32_t a, uint32_t b) {
uint32_t p = 0;
while (b) {
if (b & HI) p ^= a;
b <<= 1;
if (a & LO) a = (a >> 1) ^ POLY;
else a >>= 1;
}
return p;
}
void precompute() {
SHIFT_BYTES[0] = HI; // 1
FOR(i, 1, 100 * 1000 * 1000) {
SHIFT_BYTES[i] = poly_mul(SHIFT_BYTES[i-1], ONEBYTE);
}
FORN(c, 256) {
BYTE_CRC[c] = poly_mul(c, ONEBYTE);
}
}
inline uint32_t lift(uint32_t crc, LL num) {
return poly_mul(crc, SHIFT_BYTES[num]);
}
// Treap
typedef struct item * pitem;
struct item {
int prior, value, cnt;
bool rev;
pitem l, r;
uint32_t crc_forward, crc_backward;
};
inline int cnt (pitem it) {
return it ? it->cnt : 0;
}
inline uint32_t crc1(pitem it) {
if (!it) return 0;
if (it->rev) return it->crc_backward;
return it->crc_forward;
}
inline uint32_t crc2(pitem it) {
if (!it) return 0;
if (it->rev) return it->crc_forward;
return it->crc_backward;
}
inline void update_up (pitem it) {
if (it) {
it->cnt = cnt(it->l) + cnt(it->r) + 1;
int left_size = cnt(it->l);
int right_size = cnt(it->r);
uint32_t cl, cr, cmid;
cmid = BYTE_CRC[it->value];
cl = crc1(it->l);
cr = crc1(it->r);
it->crc_forward = lift(cl, right_size + 1) ^ lift(cmid, right_size) ^ cr;
cl = crc2(it->l);
cr = crc2(it->r);
it->crc_backward = cl ^ lift(cmid, left_size) ^ lift(cr, left_size + 1);
}
}
inline void push (pitem it) {
if (it && it->rev) {
swap(it->crc_forward, it->crc_backward);
it->rev = false;
swap (it->l, it->r);
if (it->l) it->l->rev ^= true;
if (it->r) it->r->rev ^= true;
}
}
void merge (pitem & t, pitem l, pitem r) {
push (l);
push (r);
if (!l || !r)
t = l ? l : r;
else if (l->prior > r->prior)
merge (l->r, l->r, r), t = l;
else
merge (r->l, l, r->l), t = r;
update_up (t);
}
void split (pitem t, pitem & l, pitem & r, int key, int add = 0) {
if (!t)
return void( l = r = 0 );
push (t);
int cur_key = add + cnt(t->l);
if (key <= cur_key)
split (t->l, l, t->l, key, add), r = t;
else
split (t->r, t->r, r, key, add + 1 + cnt(t->l)), l = t;
update_up (t);
}
inline void reverse (pitem t, int l, int r) {
pitem t1, t2, t3;
split (t, t1, t2, l);
split (t2, t2, t3, r-l+1);
t2->rev ^= true;
merge (t, t1, t2);
merge (t, t, t3);
}
inline void insert(pitem &t, pitem new_item, int pos){
if (!t) {
t = new_item;
return;
}
pitem t1, t2;
split(t, t1, t2, pos);
merge(t1, t1, new_item);
merge(t, t1, t2);
}
// prealloc instead of calling new
int top = 0;
item itemspace[33 * 1000 * 1000];
unsigned char buf[33 * 1000 * 1000];
int main() {
precompute();
FILE *fd;
fd = fopen("buf", "r");
int N = (int)fread(buf, 1, sizeof(buf), fd);
fclose(fd);
printf("N = %d\n", N);
pitem root = NULL;
uint32_t curcrc = 0xffffffff;
auto t0 = time(NULL);
fd = fopen("reverses", "r");
fscanf(fd, "%d", &N);
FORN(i, N) {
// append c
itemspace[top] = {rand() ^ (rand() << 24), buf[i]};
pitem t = itemspace + top;
top++;
t->crc_forward = t->crc_backward = BYTE_CRC[buf[i]];
insert(root, t, i);
// reverse [l, r]
int l, r;
fscanf(fd, "%d %d\n", &l, &r);
assert (l <= r && r <= i);
reverse(root, l, r);
if (i % 100000 == 0) {
fprintf(stderr, "i %d curcrc: %08x (%d seconds)\n", i, curcrc ^ 0xffffffff, time(NULL) - t0);
}
// update CRC
curcrc = lift(curcrc, cnt(root));
curcrc ^= crc1(root);
}
fprintf(stderr, "final: %08x\n", curcrc ^ 0xffffffff);
fclose(fd);
return 0;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment