-
-
Save tomvangoethem/cff59cde9ea0e76037a9 to your computer and use it in GitHub Desktop.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <cstdio> | |
#include <cstring> | |
#include <cassert> | |
#include <cstdint> | |
#include <algorithm> | |
#include <queue> | |
#include <openssl/sha.h> | |
#define LOG(fmt, ...) \ | |
fprintf(stderr, "[%.2f] %s:%d - " fmt, 1.0 * clock() / CLOCKS_PER_SEC, \ | |
__func__, __LINE__, ##__VA_ARGS__); | |
const int N_BLOCK = 33; | |
const int MAX_DATA_LEN = 192; | |
const int MAX_PATH_LEN = 1024; | |
const int MEM_LIMIT = 1 << 30; | |
FILE* my_fopen(const char *path, const char *mode) { | |
FILE *fp = fopen(path, mode); | |
assert(fp != NULL); | |
return fp; | |
} | |
void my_fwrite(const void *data, size_t size, size_t nitems, FILE *fp) { | |
size_t num = fwrite(data, size, nitems, fp); | |
assert(num == nitems); | |
} | |
struct Block { | |
int len; | |
uint8_t data[MAX_DATA_LEN]; | |
void load(const char *path) { | |
FILE *fp = my_fopen(path, "rb"); | |
len = fread(data, 1, MAX_DATA_LEN, fp); | |
fclose(fp); | |
} | |
} block[N_BLOCK][2]; | |
struct Elem { | |
uint64_t idx, val; | |
bool operator <(const Elem &o) const { return val < o.val; } | |
void save(const char *path) { | |
FILE *fp = my_fopen(path, "wb"); | |
for (int i = 0; i < N_BLOCK; i++) { | |
int j = (idx >> i) & 1; | |
my_fwrite(block[i][j].data, block[i][j].len, 1, fp); | |
} | |
my_fwrite("HITCON", 6, 1, fp); | |
fclose(fp); | |
} | |
}; | |
const int N_ELEM = MEM_LIMIT / sizeof(Elem); | |
Elem elem[N_ELEM]; | |
const int N_CHUNK = (1LL << N_BLOCK) / N_ELEM; | |
struct Chunk { | |
FILE *fp; | |
Elem e; | |
void init(int cid) { | |
LOG("init chunk %d\n", cid); | |
char path[MAX_PATH_LEN]; | |
snprintf(path, MAX_PATH_LEN, "chunk_%d", cid); | |
fp = my_fopen(path, "wb"); | |
std::sort(elem, elem + N_ELEM); | |
my_fwrite(elem, sizeof(elem[0]), N_ELEM, fp); | |
fclose(fp); | |
fp = my_fopen(path, "rb"); | |
advance(); | |
} | |
void advance() { fread(&e, sizeof(e), 1, fp); } | |
bool operator <(const Chunk &o) const { return o.e < e; } | |
} chunk[N_CHUNK]; | |
void load_block() { | |
LOG("load %d blocks\n", N_BLOCK); | |
for (int i = 0; i < N_BLOCK; i++) { | |
for (int j = 0; j < 2; j++) { | |
char path[MAX_PATH_LEN]; | |
snprintf(path, MAX_PATH_LEN, "block_%d_%d", i, j); | |
block[i][j].load(path); | |
} | |
} | |
} | |
inline SHA_CTX my_sha1_update(SHA_CTX ctx, const Block &blk) { | |
SHA1_Update(&ctx, blk.data, blk.len); | |
return ctx; | |
} | |
inline uint64_t my_sha1_final(SHA_CTX &ctx) { | |
uint8_t md[20]; | |
SHA1_Final(md, &ctx); | |
return *(uint64_t*)(md + 12); | |
} | |
void dfs_split(int bid, uint64_t idx, SHA_CTX ctx) { | |
static int n_chunk, n_elem; | |
if (bid == N_BLOCK) { | |
SHA1_Update(&ctx, "HITCON", 6); | |
elem[n_elem++] = Elem{idx, my_sha1_final(ctx)}; | |
if (n_elem == N_ELEM) { | |
chunk[n_chunk].init(n_chunk); | |
n_chunk++; | |
n_elem = 0; | |
} | |
return; | |
} | |
dfs_split(bid + 1, idx, my_sha1_update(ctx, block[bid][0])); | |
dfs_split(bid + 1, idx | (1LL << bid), my_sha1_update(ctx, block[bid][1])); | |
} | |
void split_chunk() { | |
LOG("split %d chunks\n", N_CHUNK); | |
SHA_CTX ctx; | |
SHA1_Init(&ctx); | |
dfs_split(0, 0, ctx); | |
} | |
void merge_chunk() { | |
LOG("merge %d chunks\n", N_CHUNK); | |
std::priority_queue<Chunk> pq(chunk, chunk + N_CHUNK); | |
auto get_next = [&]() { | |
auto c = pq.top(); | |
pq.pop(); | |
Elem e = c.e; | |
c.advance(); | |
if (!feof(c.fp)) pq.push(c); | |
return e; | |
}; | |
Elem pre = get_next(); | |
uint64_t tot = 1LL << N_BLOCK; | |
for (uint64_t i = 1; i < tot; i++) { | |
if (i % (tot / 128) == 0) LOG("merged %ld / 128\n", i / (tot / 128)); | |
Elem cur = get_next(); | |
if (pre.val == cur.val) { | |
LOG("Happy Birthday! %016lx\n", pre.val); | |
pre.save("final_msg_0"); | |
cur.save("final_msg_1"); | |
return; | |
} | |
pre = cur; | |
} | |
LOG("unhappy :(\n"); | |
} | |
int main() { | |
load_block(); | |
split_chunk(); | |
merge_chunk(); | |
return 0; | |
} |
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#!/usr/bin/env ruby | |
require 'digest' | |
require 'fileutils' | |
N = 33 | |
def md5(s) | |
Digest::MD5.hexdigest(s) | |
end | |
def run(cmd) | |
puts "run `#{cmd}`" | |
out = `#{cmd}` | |
fail if $? != 0 | |
out | |
end | |
def md5_coll(fin, fout_1, fout_2) | |
20.times do | |
run "./fastcoll #{fin}" | |
FileUtils.mv('md5_data1', fout_1) | |
FileUtils.mv('md5_data2', fout_2) | |
s1 = IO.binread(fout_1) | |
s2 = IO.binread(fout_2) | |
next if s1.include?("\n") || s2.include?("\n") | |
return | |
end | |
fail | |
end | |
run 'make -C clone-fastcoll-master clean' | |
run 'make -C clone-fastcoll-master' | |
FileUtils.rm_rf('run') | |
FileUtils.mkdir_p('run') | |
FileUtils.copy_file('clone-fastcoll-master/fastcoll', 'run/fastcoll') | |
FileUtils.chdir('run') | |
base_bin = "p `xxd fl*`\x00" | |
fail if base_bin.bytes.any?{|x| x % 2 != 0} | |
base_bin = base_bin.bytes.map{|x| (x / 2).chr}.join | |
IO.binwrite('base.bin', base_bin) | |
md5_coll('base.bin', 'md5_0_0', 'md5_0_1') | |
(1...N).each do |i| | |
md5_coll("md5_#{i-1}_0", "md5_#{i}_0", "md5_#{i}_1") | |
end | |
FileUtils.cp('md5_0_0', 'block_0_0') | |
FileUtils.cp('md5_0_1', 'block_0_1') | |
(1...N).each do |i| | |
l = File.size("md5_#{i}_0") - File.size("md5_#{i-1}_0") | |
IO.binwrite("block_#{i}_0", IO.binread("md5_#{i}_0")[-l..-1]) | |
IO.binwrite("block_#{i}_1", IO.binread("md5_#{i}_1")[-l..-1]) | |
end |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment