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

#if 1
#define Niter 512
#define Nrounds 2
#else
#define Niter 2
#define Nrounds 512
#endif

typedef unsigned char word;

static word s[2][16];

static unsigned long ntot, neq;

/*
 * These are filled with digits of Pi from Blowfish S-boxes.
 * We actually use only the least significant 8 bits of each 32-bit value.
 */
static unsigned int init_s[2][16] = {
	{
		0xd1310ba6, 0x98dfb5ac, 0x2ffd72db, 0xd01adfb7,
		0xb8e1afed, 0x6a267e96, 0xba7c9045, 0xf12c7f99,
		0x24a19947, 0xb3916cf7, 0x0801f2e2, 0x858efc16,
		0x636920d8, 0x71574e69, 0xa458fea3, 0xf4933d7e
	}, {
		0x4b7a70e9, 0xb5b32944, 0xdb75092e, 0xc4192623,
		0xad6ea6b0, 0x49a7df7d, 0x9cee60b8, 0x8fedb266,
		0xecaa8c71, 0x699a17ff, 0x5664526c, 0xc2b19ee1,
		0x193602a5, 0x75094c29, 0xa0591340, 0xe4183a3e
	}
};

static void init(void)
{
	int i, j;

	for (i = 0; i < 2; i++)
		for (j = 0; j < 16; j++)
			s[i][j] = init_s[i][j] & 0xff;
}

#define pcadd(a, b, mask) \
	(((a) ^ (b)) + (((a) & (b) & (mask)) << 1))

static void encrypt(word block[2], unsigned int n)
{
	int key_setup = n >= 1;
	word *p;
	word l = block[0];
	word r = block[1];
#if 1
	char save_s[sizeof(s)];
	int next_save = -1;
#endif

	do {
#if 0
		if (key_setup)
			l = r = 0; /* Reduce state to just s[], for testing */
#endif
		p = &s[0][0];
		do {
			int i;
			for (i = 0; i < Nrounds / 2; i++) {
				r ^= pcadd(s[0][l & 0xf], s[1][l >> 4], 0x55);
				l ^= pcadd(s[0][r & 0xf], s[1][r >> 4], 0xaa);
			}
			if (!key_setup)
				goto out;
			*p++ ^= l;
			*p++ ^= r;
#if 1
			ntot += 2;
			if (!*(p-2)) neq++;
			if (!*(p-1)) neq++;
#endif
#if 0
/* For "repeated state" check testing */
			if (p >= &s[0][4])
				break;
#endif
		} while (p < &s[1][15]);
#if 1
		if (next_save >= 0 && !memcmp(save_s, s, sizeof(s)))
			fprintf(stderr, "Error: repeated state\n");
		if (next_save < 0 || n == next_save) {
			memcpy(save_s, s, sizeof(s));
			next_save = n >> 1;
		}
#endif
	} while (--n);

out:
	block[0] = l;
	block[1] = r;
}

/*
 * Make sure that encrypt() does a 1-to-1 transformation when the encryption
 * key is fixed and "n" is 0.
 */
void test(void)
{
	unsigned int data, encrypted;
	word block[2];
	char save_s[sizeof(s)];
	unsigned char seen[0x10000];

	init();
	block[0] = block[1] = 0;
	encrypt(block, Niter); /* slow key setup */
	memcpy(save_s, s, sizeof(s));

	memset(seen, 0, sizeof(seen));

	for (data = 0; data <= 0xffff; data++) {
		memcpy(s, save_s, sizeof(s));
		block[0] = data & 0xff;
		block[1] = data >> 8;
		encrypt(block, 0);
		encrypted = block[0] + (block[1] << 8);
		if (encrypted > 0xffff || seen[encrypted]) {
			fprintf(stderr, "Error: %04x -> %04x\n",
			    data, encrypted);
		} else
			seen[encrypted] = 1;
	}
}

static void set_key(char *key)
{
	word block[2];
	int i;
	char *p = key;

	init();
	block[0] = block[1] = 0;
	for (i = 0; i < 16; i++) {
		if (!*p)
			break;
		s[0][i] ^= *p++; /* Assume at least 8-bit S-box output width */
		if (i == 15) {
			encrypt(block, 0); /* XXX: might not use entire s[0] */
			i = -1;
		}
	}
	encrypt(block, Niter); /* slow key setup */
}

static void print_state(void)
{
#if 0
/* Expected: approx. 41427 different outputs for 65536 different inputs */
	word block[2];

	block[0] = block[1] = 0;
	encrypt(block, 0);
	printf("%02x%02x\n", block[0], block[1]);
#else
/* Expected: no collisions */
	int i, j;

	for (i = 0; i < 2; i++)
		for (j = 0; j < 16; j++)
			printf("%02x", s[i][j]);
	putchar('\n');
#endif
}

int main(void)
{
	char key[0x1000], *p;

	test();

	while ((p = fgets(key, sizeof(key), stdin))) {
		p = strchr(p, '\n');
		if (*p)
			p = 0;
		set_key(key);
		print_state();
	}

/* Expected: a value close to 256.00 */
	fprintf(stderr, "ntot/neq = %.2f\n", (double)ntot / neq);

	return 0;
}