#include <stdio.h>
#include <string.h>
#include <stdlib.h>

#include "crc32.c"
#include "md5.c"

#define BFLIB
#include "bfsummult.c"

static unsigned char solution[21];
static unsigned char md5[16];
static unsigned long sum = 0, mult = 0;
static char part4[60];

static inline char hex2c(char c) { c -= '0'; if (c > 9) c = c + '0' - 'A' + 10; return c; }

void solve_check()
{
	unsigned char curmd5[16];
	calc_md5_20(solution, curmd5);
	if (!memcmp(curmd5, md5, 16))
		printf("%s\n", solution);
}

static unsigned char *all_summult_sol;
static unsigned long all_summult_sol_count;
static unsigned long all_summult_sol_sz;

void solve_summult()
{
	unsigned long *cursol = (unsigned long *)all_summult_sol;
	unsigned long cnt = all_summult_sol_count;
	while (cnt--) {
		*(unsigned long *)solution = *cursol++;
		solve_check();
	}
}

static unsigned long *all_crc_sol;

void solve_crc()
{
	unsigned long i;
#ifdef _ONLY_PRINTABLE
	unsigned long ii, ij;
	for (ii=0x20 ; ii<0x7f ; ii++)
	for (ij=0x20 ; ij<0x7f ; ij++) {
		i = (ii << 8) + ij;
#else
	for (i=0 ; i < 0x10000 ; i++) {
#endif
		*(unsigned short *)(solution + 10) = (unsigned short)i;
		*(unsigned long  *)(solution + 12) = all_crc_sol[i];
		
		solve_summult();
	}
}

/*
static unsigned long part4_table[16] = {
	0x1AE,	0x002,	0xA6C,	0xF72,
	0x000,	0x0BA,	0x004,	0x00C,
	0x003,	0x0D9,	0x0FD,	0x005,
	0x008,	0x039,	0xAEF,	0x0FA	
};
*/

void solve_43()
{
	int nibbles[8];
	int nnibles = 0;
	char *ptr = part4 + 3*6 + 10;

	while (*ptr) {
		switch (*ptr) {
		case '1':
			nibbles[nnibles++] = 0;
			ptr += 3;
			break;
		case '2':
			nibbles[nnibles++] = 1;
			ptr += 1;
			break;
		case '3':
			if (ptr[1] == '9') {
				nibbles[nnibles++] = 13;
				ptr += 2;
			} else {
				nibbles[nnibles++] = 8;
				ptr += 1;
			}
			break;
		case '4':
			nibbles[nnibles++] = 6;
			ptr += 1;
			break;
		case '5':
			nibbles[nnibles++] = 11;
			ptr += 1;
			break;
		case '8':
			nibbles[nnibles++] = 12;
			ptr += 1;
			break;
		case 'A':
			nibbles[nnibles++] = (ptr[1] == '6' ? 2 : 14);
			ptr += 3;
			break;
		case 'B':
			nibbles[nnibles++] = 5;
			ptr += 2;
			break;
		case 'C':
			nibbles[nnibles++] = 7;
			ptr += 1;
			break;
		case 'D':
			nibbles[nnibles++] = 9;
			ptr += 2;
			break;
		case 'F':
			if (ptr[1] == '7') {
				nibbles[nnibles++] = 3;
				ptr += 3;
			} else {
				nibbles[nnibles++] = (ptr[1] == 'A' ? 15 : 10);
				ptr += 2;
			}
			break;
		}
	}

	// mask has 8 bits, every 1 is the position of a '4' nibble
	unsigned mask;
	int i;
	int bcount;
	char c;
	for (mask = 0 ; mask < 256 ; mask++) {
		bcount = 0;
		for (i=0 ; i<8 ; i++)
			if (mask & (1 << i))
				bcount++;
		if (bcount + nnibles != 8)
			continue;

		bcount = 0;
		for (i=0 ; i<4 ; i++) {
			if (mask & (1 << (2*i))) {
				bcount++;
				c = 0x40;
			} else
				c = nibbles[2*i - bcount] << 4;
			
			if (mask & (1 << (2*i + 1))) {
				bcount++;
				c |= 0x4;
			} else
				c |= nibbles[2*i + 1 - bcount];

			solution[16+i] = c;
		}

		solve_crc();
	}
}

void solve_41()
{
	unsigned char c;
	int i;
	
	for (i=0 ; i<6 ; i++)
		solution[4+i] = 0;

	for (i=0 ; i<6 ; i++) {
		c = (hex2c(part4[1+3*i]) << 4) | hex2c(part4[2+3*i]);
		solution[9-i] |= (c >> 3);
		solution[i ? 10-i : 4] |= (c << 5);
	}

	solve_43();
}

// create a table with all abcd solving summult
void presolve_summult_cb(unsigned char a, unsigned char b, unsigned char c, unsigned char d)
{
	all_summult_sol_count++;
	
	if (all_summult_sol_count * 4 >= all_summult_sol_sz) {
		all_summult_sol_sz += 1024;
		all_summult_sol = realloc(all_summult_sol, all_summult_sol_sz);
		if (!all_summult_sol) {
			perror("realloc summult");
			printf("all_summult_sol_count: %lu\n", all_summult_sol_count);
			exit(1);
		}
	}
	unsigned long *ultab = (unsigned long*)all_summult_sol;
	ultab[all_summult_sol_count - 1] = (unsigned long)a + ((unsigned long)b<<8) + ((unsigned long)c<<16) + ((unsigned long)d<<24);
}

void presolve_crc()
{
	all_crc_sol = malloc(0x40000);
	if (!all_crc_sol) { perror("malloc crc"); exit(1); }

	unsigned long target = 0;
	unsigned long i;
	for (i=0 ; i<8 ; i++)
		target <<= 4, target += hex2c(part4[6*3+i]);
	

	int c, d, e, f;
	unsigned long crc;
        unsigned long c1, c2, c3, c4;
	
	for (i=0 ; i<0x10000 ; i++) {
		crc = iter_crc(iter_crc(0, i & 255), i >> 8);
		
		c4 = crctable[ crcinvtable[ target >> 24 ] ];
		c3 = crctable[ crcinvtable[ ((target >> 16) ^ (c4 >> 16)) & 255 ] ];
		c2 = crctable[ crcinvtable[ ((target >> 8) ^ (c4 >> 8) ^ (c3 >> 16)) & 255 ] ];
		c1 = crctable[ crcinvtable[ (target ^ c4 ^ (c3 >> 8) ^ (c2 >> 16)) & 255 ] ];
		
		c = crcinvtable[c1 >> 24] ^ (crc & 255);
		crc = (crc >> 8) ^ crctable[(c ^ crc) & 0xff];
		
		d = crcinvtable[c2 >> 24] ^ (crc & 255);
		crc = (crc >> 8) ^ crctable[(d ^ crc) & 0xff];
		
		e = crcinvtable[c3 >> 24] ^ (crc & 255);
		crc = (crc >> 8) ^ crctable[(e ^ crc) & 0xff];
		
		f = crcinvtable[c4 >> 24] ^ (crc & 255);
		crc = (crc >> 8) ^ crctable[(f ^ crc) & 0xff];
		
		all_crc_sol[i] = c + (d << 8) + (e << 16) + (f << 24);
	}
}

void solve()
{
	memset(solution, '.', 20);
	solution[20] = 0;
	
	all_summult_sol_count = 0;
	all_summult_sol_sz = 1024;
	all_summult_sol = malloc(all_summult_sol_sz);
	if (!all_summult_sol) { perror("malloc summult"); exit(1); }
	do_bf(sum, mult, presolve_summult_cb);

	presolve_crc();
	
//	printf("precalc finished\n");
	
	solve_41();
}

void parse_argument(char *str)
{
	unsigned char *uc = md5;
	char *cc = part4;
	
	// try not to send malformed argument :)
	
	// read md5
	while (*str != '-')
		*uc++ = (hex2c(*str) << 4) | hex2c(str[1]), str += 2;

	// read sum
	sum = 0;
	while (*++str != '-')
		sum = sum * 10 + *str - '0';
	
	mult = 0;
	while (*++str != '-')
		mult = mult * 10 + *str - '0';
	
	// read what's left
	while (*str++)
		*cc++ = *str;
}

int main(int argc, char **argv)
{
	
	if (argc < 2) {
		printf("Usage: %s poeut-output\n", argv[0]);
		return 0;
	}

	init_crc();
	init_md5();
	
	parse_argument(argv[1]);

	solve();

	return 0;
}