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

#define BYTE_WIDTH 8
#define POLY_WIDTH 64
#define TWO_UP_EIGHT 256

// Store the computed table values in a data file to be used in the Bytewise CRC calculation program.
#define OUTPUT_FILE "CRC-64.dat"

// "Poly" is the binary representation of the CRC-64 polynomial listed below.
// x64 + x62 + x57 + x55 + x54 + x53 + x52 + x47 + x46 + x45 + x40 + x39 + x38 + x37 + x35 + x33 + x32 + x31 + x29 + x27 + x24 + x23 + x22 + x21 + x19 + x17 + x13 + x12 + x10 + x9 + x7 + x4 + x + 1
const unsigned long int Poly = 4823603603198064275;
const unsigned long int MSB = 9223372036854775808;
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};

// 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);
}

// Feed this function "TableIndex" and it will return the corresponding Lookup-Value for CRC-64.
unsigned long int GenerateLookupTableValue(unsigned long int TableIndex){
	unsigned int X;
	unsigned long int TheRegister = TableIndex<<56;
	// Shift a Byte worth of zeros into the register, and when a "1" is shifted out, perform the required "XOR" operation with "Poly".
	for ( X = BYTE_WIDTH; X; X-- ) {
		if ( TheRegister & MSB ) TheRegister = (TheRegister << 1) ^ Poly;
		else TheRegister <<= 1;
	}
	return TheRegister;
}

int main(){
	unsigned long int X;
	int Y;
	unsigned long int CalculatedValues[TWO_UP_EIGHT];
	FILE* DataOut;
	DataOut = fopen(OUTPUT_FILE, "wb");
	for ( X = 0; X < TWO_UP_EIGHT; X++ ) {
		CalculatedValues[X] = GenerateLookupTableValue(X);
		printf("|%3lu| - Value-|%16lX| - Binary|", X, CalculatedValues[X]);
		PrintUnsignedLongInBinary(CalculatedValues[X]);
		printf("|\n");
	}
	
	// Verify that each value in the lookup table is unique.
	// Each value can be the seen as the remainder when a 9-Byte message is divided by "Poly".
	// The second-to-ninth Bytes are always "W" zeros, so only the first byte changes, making it impossible for two remainders to be the same.
	for ( X = 1; X < TWO_UP_EIGHT; X++ ) {
		for ( Y = (X - 1); Y >= 0; Y-- ) {
			if ( CalculatedValues[X] == CalculatedValues[Y] ) printf("Duplicate values found at |%lu|, and |%d|\n", X, Y);
		}
	}
	printf("The search for duplicate values in the table is complete.\n");
	
	fwrite(CalculatedValues, sizeof(unsigned long int), TWO_UP_EIGHT, DataOut);
	fclose(DataOut);
	return 0;
}