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

// CRC Constants.
#define BYTE_WIDTH 8
#define POLY_WIDTH 64
#define TWO_UP_EIGHT 256
#define LEFT_BYTE_SHIFT 56
#define W_BYTES 8

// The pre-compiled CRC-64 lookup-table is stored in this file.
#define LOOKUP_TABLE_FILE "CRC-64.dat"

// 17x17 4-Colouring Constants.
#define POSITION_COUNT 289
#define CHAR_COUNT 73
#define COLOURS 4
#define POSITIONS_PER_NODE 4

// These values are used to decode unsigned long ints into binary format for output.
const unsigned long int PowersOfTwo[POLY_WIDTH] = {1, 2, 4, 8, 16, 32, 64, 128, 256, 512, 1024, 2048, 4096, 8192, 16384, 32768, 65536, 131072, 262144, 524288, 1048576, 2097152, 4194304,
 8388608, 16777216, 33554432, 67108864, 134217728, 268435456, 536870912, 1073741824, 2147483648, 4294967296, 8589934592, 17179869184, 34359738368, 68719476736, 137438953472, 274877906944,
 549755813888, 1099511627776, 2199023255552, 4398046511104, 8796093022208, 17592186044416, 35184372088832, 70368744177664, 140737488355328, 281474976710656, 562949953421312, 1125899906842624,
 2251799813685248, 4503599627370496, 9007199254740992, 18014398509481984, 36028797018963968, 72057594037927936, 144115188075855872, 288230376151711744, 576460752303423488, 1152921504606846976,
 2305843009213693952, 4611686018427387904, 9223372036854775808};

// This value is integrated into "CrcLookupTable", but it will not be needed explicitly.
const unsigned long int Poly = 4823603603198064275;

// The CRC-64 lookup-table will have global scope.
unsigned long int CrcLookupTable[TWO_UP_EIGHT];

const unsigned int Modulus[POSITIONS_PER_NODE + 1] = { 0, 1, 2, 3, 0 };

const char TheColours[COLOURS] = { '0', '1', '2', '3' };

const unsigned int PositionShift[POSITIONS_PER_NODE] = { 6, 4, 2, 0 };

// This function uses "NumberOfBytes" Bytes starting at "DataMessage" to compute the CRC-Digest, by way of a Byte-wise "CrcLookupTable" based on the CRC-64 "Poly".
unsigned long int LookupTableColouringCrc(const unsigned char *DataMessage, unsigned long int NumberOfBytes){
	int X;
	// Because looking up a "0" in the table returns "0", it is safe to use table-lookups for filling the "WorkingRegister" with its initial "DataMessage" values.
	register unsigned long int WorkingRegister = 0;
	// Query the "CrcLookupTable" exactly "NumberOfBytes" times.  Perform lookups using the leftmost Byte of "WorkingRegister" as the index.
	// After each table query, "XOR" the value returned by "CrcLookupTable" with the value inside "WorkingRegister" as soon as the next "DataMessage" Byte has been drawn in from the right-hand-side.
	// "X" represents the location of the next "DataMessage" Byte to pull into the calculation.
	for ( X = 0; X < NumberOfBytes; X++ ) WorkingRegister = CrcLookupTable[WorkingRegister >> LEFT_BYTE_SHIFT] ^ ((WorkingRegister << BYTE_WIDTH) ^ DataMessage[X]);
	return WorkingRegister;
}

// Read the "POSITION_COUNT" printable characters from "ThisImport" Colouring, and compress them into the "CHAR_COUNT" characters of "ThisColouringString".  Compression has a factor of 4.
void ImportMasterColouringSeedString(unsigned char *ThisColouringString, const char *ThisImport){
	unsigned int X;
	unsigned int CurrentPosition = 3;
	// Zero the destination Bytes.
	memset(ThisColouringString, 0, sizeof(unsigned char)*CHAR_COUNT);
	// Place the colour at position "X" of "ThisImport", into the correct two-bit slot within "ThisColouringString". Position shifting and modulus lookup-tables are used to speed this up.
	for ( X = 0; X < POSITION_COUNT; X++ ) ThisColouringString[X >> 2] += ((ThisImport[X] - TheColours[0]) << PositionShift[CurrentPosition = Modulus[CurrentPosition + 1]]);
}

// Simply print out "ThisLong" using "1"s and "0"s.
void PrintUnsignedLongInBinary(unsigned long int ThisLong){
	unsigned int X;
	char HoldOut[POLY_WIDTH + 1];
	for ( X = 0; X < POLY_WIDTH; X++ ) HoldOut[X] = (ThisLong & PowersOfTwo[POLY_WIDTH - 1 - X])? '1': '0';
	HoldOut[POLY_WIDTH] = '\0';
	printf("%s", HoldOut);
}

// Simply print out "ThisByte" using "1"s and "0"s.
void PrintByteInBinary(unsigned char ThisByte){
	unsigned int X;
	char HoldOut[BYTE_WIDTH + 1];
	for ( X = 0; X < BYTE_WIDTH; X++ ) HoldOut[X] = (ThisByte & PowersOfTwo[BYTE_WIDTH - 1 - X])? '1': '0';
	HoldOut[BYTE_WIDTH] = '\0';
	printf("%s", HoldOut);
}

int main(){
	int X;
	unsigned char *CompactString = (unsigned char*)calloc(CHAR_COUNT + W_BYTES, sizeof(unsigned char));
	unsigned char *TheFinalW = CompactString + CHAR_COUNT;
	unsigned long int TheDigest;
	
	// These 289-character strings are all different, but it is extremely tedious to find the differences, just by looking at them.  Hence we use CRC-64 to help us out.
	char *FirstImport =
	"11302023023013131"
	"20301312322310210"
	"23123320133011020"
	"32211100023332301"
	"00231221230301103"
	"03022131011312230"
	"20232030313120111"
	"31333021100223210"
	"01103201302122333"
	"22013233101030102"
	"33200110302101222"
	"01220012331233001"
	"12001332110123023"
	"30131322001132032"
	"10020303221021312"
	"32112103232200013"
	"13310211020230323\0";
	
	char *SecondImport =
	"11302023023013131"
	"20301312322310210"
	"23123320133011020"
	"32211100023332301"
	"00231221230301103"
	"03022131011312230"
	"20232030313120111"
	"31333001100223210"
	"01103201302122333"
	"22013233101030102"
	"33200110302101222"
	"01220012331233001"
	"12001332110123023"
	"30131322001232032"
	"10020303221021312"
	"32112103232200013"
	"13310211020230323\0";
	
	char *ThirdImport =
	"11302023023013131"
	"20301312322310210"
	"23123320133011020"
	"32211100023332301"
	"00231221230301103"
	"03022131011312230"
	"20232030313120111"
	"31333021100223210"
	"01103201302122333"
	"22013233101030102"
	"33200110302101222"
	"01220012331233001"
	"12001332110123023"
	"10131322001232032"
	"10020303221021312"
	"32112103232200013"
	"13310211020230323\0";
	
	FILE *LookupTableData;
	LookupTableData = fopen(LOOKUP_TABLE_FILE, "rb");
	fread(CrcLookupTable, sizeof(unsigned long int), TWO_UP_EIGHT, LookupTableData);
	fclose(LookupTableData);
	
	// Process the "FirstImport".
	printf("\n---------------------------------------------------------------------------------\n\n");
	
	ImportMasterColouringSeedString(CompactString, FirstImport);
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT);
	printf("TheDigest for FirstImport over CHAR_COUNT Bytes -|%lu|\n", TheDigest);
	
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
	printf("TheDigest for FirstImport plus W zero bits -|%lu|\n", TheDigest);
	
	// Copy the (CRC-Digest with W extra zeros) into the extra positions in "CompactString".
	// It turns out that this is a rather tedious operation, because "unsigned long int"s are stored in "Little Endian Byte Order" in the X86-X64 architecture.
	// The statement below amounts to reversing the Byte order while copying, so that the most significant Bytes get processed first.
	for ( X = 0; X < W_BYTES; X++ ) *(TheFinalW + X) = ((unsigned char *)&TheDigest)[W_BYTES - X - 1];
	
	// Verify the the copied Bytes have arrived in the correct order.
	printf("From TheDigest    |");
	PrintUnsignedLongInBinary(TheDigest);
	printf("|\n");
	
	printf("From CompactString|");
	for( X = 0; X < W_BYTES; X++ ) {
		PrintByteInBinary(CompactString[CHAR_COUNT + X]);
		printf("|");
	}
	printf("\n");
	
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
	printf("TheDigest for FirstImport with previous digest appended -|%lu|\n", TheDigest);
	
	// Process the "SecondImport".
	printf("\n---------------------------------------------------------------------------------\n\n");
	
	ImportMasterColouringSeedString(CompactString, SecondImport);
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT);
	printf("TheDigest for SecondImport over CHAR_COUNT Bytes -|%lu|\n", TheDigest);
	
	memset(CompactString + CHAR_COUNT, 0, W_BYTES);
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
	printf("TheDigest for SecondImport plus W zero bits -|%lu|\n", TheDigest);
	
	// Copy the (CRC-Digest with W extra zeros) into the extra positions in "CompactString".
	// It turns out that this is a rather tedious operation, because "unsigned long int"s are stored in "Little Endian Byte Order" in the X86-X64 architecture.
	// The statement below amounts to reversing the Byte order while copying, so that the most significant Bytes get processed first.
	for ( X = 0; X < W_BYTES; X++ ) *(TheFinalW + X) = ((unsigned char *)&TheDigest)[W_BYTES - X - 1];
	
	// Verify the the copied Bytes have arrived in the correct order.
	printf("From TheDigest    |");
	PrintUnsignedLongInBinary(TheDigest);
	printf("|\n");
	
	printf("From CompactString|");
	for( X = 0; X < W_BYTES; X++ ) {
		PrintByteInBinary(CompactString[CHAR_COUNT + X]);
		printf("|");
	}
	printf("\n");
	
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
	printf("TheDigest for SecondImport with previous digest appended -|%lu|\n", TheDigest);
	
	// Process the "ThirdImport".
	printf("\n---------------------------------------------------------------------------------\n\n");
	
	ImportMasterColouringSeedString(CompactString, ThirdImport);
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT);
	printf("TheDigest for ThirdImport over CHAR_COUNT Bytes -|%lu|\n", TheDigest);
	
	memset(CompactString + CHAR_COUNT, 0, W_BYTES);
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
	printf("TheDigest for ThirdImport plus W zero bits -|%lu|\n", TheDigest);
	
	// Copy the (CRC-Digest with W extra zeros) into the extra positions in "CompactString".
	// It turns out that this is a rather tedious operation, because "unsigned long int"s are stored in "Little Endian Byte Order" in the X86-X64 architecture.
	// The statement below amounts to reversing the Byte order while copying, so that the most significant Bytes get processed first.
	for ( X = 0; X < W_BYTES; X++ ) *(TheFinalW + X) = ((unsigned char *)&TheDigest)[W_BYTES - X - 1];
	
	// Verify the the copied Bytes have arrived in the correct order.
	printf("From TheDigest    |");
	PrintUnsignedLongInBinary(TheDigest);
	printf("|\n");
	
	printf("From CompactString|");
	for( X = 0; X < W_BYTES; X++ ) {
		PrintByteInBinary(CompactString[CHAR_COUNT + X]);
		printf("|");
	}
	printf("\n");
	
	TheDigest = LookupTableColouringCrc(CompactString, CHAR_COUNT + W_BYTES);
	printf("TheDigest for ThirdImport with previous digest appended -|%lu|\n", TheDigest);
	
	printf("\n---------------------------------------------------------------------------------\n\n");
	
	return 0;
}