#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 long ntot, neq;

static word bitrev8[0x100];

/*
 * 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)) & 0xff)

#define r8(x) \
	((const word)(bitrev8[(unsigned int)(x)]))

#define rpcadd(a, b, mask) \
	r8(pcadd((a), (b), (mask)))

static void encrypt(word block[2], unsigned int n)
{
	int key_setup = n >= 1;
	word *p;
	word l = block[0];
	word r = block[1];
	word lw, rw;
#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;
#if 1
			l = pcadd(l, *p, 0x55);
			r = pcadd(r, *(p + 1), 0xaa);
#endif
			for (i = 0; i < Nrounds / 2; i++) {
#if 1
				r ^= pcadd(s[0][l & 0xf], s[1][l >> 4], 0x55);
				l ^= pcadd(s[0][r & 0xf], s[1][r >> 4], 0xaa);
#else
				r ^= rpcadd(s[0][l & 0xf], s[1][r8(l) & 0xf], 0x55);
				l ^= rpcadd(s[1][r & 0xf], s[0][r8(r) & 0xf], 0xaa);
#endif
			}
			if (!key_setup)
				goto out;
#if 1
			lw = pcadd(l, *p, 0x55);
			rw = pcadd(r, *(p + 1), 0xaa);
#elif 0
			lw = *p ^ l;
			rw = *(p + 1) ^ r;
#else
			lw = l;
			rw = r;
#endif
#if 1
			ntot += 2;
			if (*p == lw) neq++;
			if (*(p+1) == rw) neq++;
#endif
			*p++ = lw;
			*p++ = rw;
#if 0
/* For "repeated state" check testing */
			if (p >= &s[0][2])
				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) {
#if 1
			encrypt(block, Niter >= 1 ? 1 : 0); /* not very slow */
#else
			encrypt(block, 1); /* not very slow */
#endif
			i = -1;
		}
	}
	encrypt(block, Niter); /* slow key setup */
}

static void print_state(void)
{
#if 1
/* Expected: approx. 41427 different outputs for 65536 different inputs,
 * approx. 65504 for 500000, or 65536 for 1000000. */
	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
}

static void init_bitrev(void)
{
	unsigned int i, j;

	memset(bitrev8, 0, sizeof(bitrev8));
	for (i = 0; i < 0x100; i++)
		for (j = 0; j < 8; j++)
			bitrev8[i] |= ((i & (1 << j)) >> j) << (7 - j);
	for (i = 0; i < 0x100; i++)
		if (r8(r8(i)) != i)
			fprintf(stderr, "Error: r8(r8(%u)) = %u\n",
			    i, r8(r8(i)));
#if 0
	printf("%02x %02x %02x %02x\n",
		bitrev8[0x55], bitrev8[0xaa], bitrev8[0x0f], bitrev8[0xf0]);
	printf("%02x %02x %02x %02x\n",
		rpcadd(0x0f, 0xf0, 0xff), rpcadd(0xaa, 0x55, 0xff),
		rpcadd(0xff, 0xff, 0x55), rpcadd(1, 3, 2));
#endif
}

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

	init_bitrev();
	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;
}