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

#define BITS			8
#define POLY			0x1d

typedef unsigned int gfa_t;

#define XCHG(x, y)	({ typeof((x)) tmp = (x); (x) = (y); (y) = tmp; })

static inline gfa_t add(gfa_t x, gfa_t y)
{
	return x ^ y;
}

#define sub(x, y)		add((x), (y))

static inline gfa_t mult2(gfa_t x)
{
	return ((x << 1) & ((1 << BITS)-1))^((x & (1 << (BITS-1))) ? POLY : 0);
}

static gfa_t __mult(gfa_t x, gfa_t y)
{
	gfa_t r = 0;

	while(y > 0) {
		if (y & 1)
			r ^= x;
		x = mult2(x);
		y >>= 1;
	}

	return r;
}

static inline gfa_t mult(gfa_t x, gfa_t y)
{
	if (x < y)
		XCHG(x, y);

	return __mult(x, y);
}

static gfa_t expon(gfa_t x, int n)
{
	gfa_t r = 1;

	while(n < 0)
		 n += (1 << BITS)-1;
	n %= (1 << BITS)-1;

	while(n > 0) {
		if (n & 1)
			r = mult(r, x);
		x = __mult(x, x);
		n >>= 1;
	}

	return r;
}

#define div(x, y)		mult((x), expon((y), -1))

/*
 * add(x, y);
 * sub(x, y);
 * mult(x, y);
 * div(x, y);
 * expon(x, k);
 */

static void check_commutativity(void)
{
	gfa_t i, j;

	printf("checking multiplicative commutativity... ");
	for(i = 0; i < (1 << BITS); i++)
		for(j = 0; j < i; j++)
			if (__mult(i, j) != __mult(j, i))
				abort();
	printf("ok\n");
}

static void check_generator(gfa_t g)
{
	unsigned char bm[((1 << BITS)+7) >> 3] = { 0, };
	gfa_t i, x;

	printf("checking for validity of generator %02x... ", g);

	x = 1;
	i = 1;
	do {
		unsigned char mask = 1 << (x & 7);
		int pos = x >> 3;

		if (!(bm[pos] ^= mask))
			break;
		x = __mult(x, g);
		i++;
	} while(x != 1);

	if (i != (1 << BITS))
		abort();

	printf("ok\n");
}

static void check_multiplication(void)
{
	unsigned char bm[((1 << BITS)+7) >> 3];
	gfa_t i, j;

	printf("checking for mutiplication validity... ");

	for(i = 1; i < (1 << BITS); i++) {
		memset(bm, 0, sizeof bm);

		for(j = 0; j < (1 << BITS); j++) {
			gfa_t x = mult(i, j);
			unsigned char mask = 1 << (x & 7);
			int pos = x >> 3;

			if (!(bm[pos] ^= mask))
				break;
		}
	}

	printf("ok\n");
}

static void check_inversion(void)
{
	gfa_t i;

	printf("checking for inversion validity... ");
	for(i = 1; i < (1 << BITS); i++)
		if (mult(i, expon(i, -1)) != 1)
			abort();
	printf("ok\n");
}

int main(int argc, char **argv)
{
	gfa_t i, j, x;

	check_commutativity();
	check_generator(2);
	check_multiplication();
	check_inversion();
	printf("\n");

	/* addition */

	printf("+  |");
	for(j = 0; j < 16; j++)
		printf(" %02x", j);
	printf("\n");

	printf("---+");
	for(j = 0; j < 16; j++)
		printf("---");
	printf("\n");

	for(i = 0; i < 16; i++) {
		printf("%02x |", i);
		for(j = 0; j < 16; j++) {
			printf(" %02x", add(i, j));
		}
		printf("\n");
	}

	printf("\n");

	/* multiplication */

	printf("*  |");
	for(j = 0; j < 16; j++)
		printf(" %02x", j);
	printf("\n");

	printf("---+");
	for(j = 0; j < 16; j++)
		printf("---");
	printf("\n");

	for(i = 0; i < 16; i++) {
		printf("%02x |", i);
		for(j = 0; j < 16; j++) {
			printf(" %02x", mult(i, j));
		}
		printf("\n");
	}

	printf("\n");

	/* exponentiation */

	printf("2^ |");
	for(j = 0; j < 16; j++)
		printf(" _%x", j);
	printf("\n");

	printf("---+");
	for(j = 0; j < 16; j++)
		printf("---");
	printf("\n");

	x = 1;
	for(i = 0; i < 16; i++) {
		printf("%x_ |", i);
		for(j = 0; j < 16; j++) {
			printf(" %02x", x);
			x = mult2(x);
		}
		printf("\n");
	}

	printf("\n");

	/* inverse numbers */

	printf("1/ |");
	for(j = 0; j < 16; j++)
		printf(" _%x", j);
	printf("\n");

	printf("---+");
	for(j = 0; j < 16; j++)
		printf("---");
	printf("\n");

	for(i = 0; i < 16; i++) {
		printf("%x_ |", i);
		for(j = 0; j < 16; j++)
			printf(" %02x", expon(i*16 + j, -1));
		printf("\n");
	}

	printf("\n");

	return 0;
}