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

//求數的二進制最高位的冪指數，即MSB
static int getMinPolynomialBits(uint64_t n) {
	int r = 0;
	while (n >>= 1) r++;
	return r;
}

//append>0表示計算crc校驗碼，賦值到crcRemainder
//append=0，表示校驗輸入bit流是否正確；0表示正確，-1表示錯誤
//此處的多項式默認為0x96(高位補1后的結果)，默認crc位數為7，可根據代碼自行修改
static int crcCheck(const char* msg, int append, char* crcRemainder)
{
	if (msg == NULL || crcRemainder == NULL || strlen(msg) == 0) {
		printf("input parameter is unvalid!\n");
		return -1;
	}
	 //hex: 0x96 = b'10010110' = DEC:150 
	uint64_t poly = 0x96; 
	int polyLen = getMinPolynomialBits(poly + 1); //=7

	int msgLen = strlen(msg);
	//printf("%d\n", msgLen);

	//計算crc校驗碼
	if (append) {
		unsigned char* pBufCrc = (unsigned char*)calloc(msgLen + polyLen, sizeof(unsigned char)); 
		memset(pBufCrc, 0, msgLen + polyLen);

		for (int j = 0; j < msgLen; j++) {
			pBufCrc[j] = msg[j] - '0';
		}

		uint8_t* p = NULL;
		for (int i = 0; i < msgLen; i++) {
			if (pBufCrc[i]) {
				p = pBufCrc + i + polyLen;
				uint64_t t = poly;
				do {
					*(p--) ^= t & 1;
				} while (t >>= 1);
			}
		}
		p = NULL;

		size_t k;
		for (k = 0; k < polyLen; k++) {
			crcRemainder[k] = pBufCrc[k + msgLen] + 48;
		}
		if (pBufCrc) {
			free(pBufCrc);
			pBufCrc = NULL;
		}
	}
	else {
		// 校驗接受端的比特流
		unsigned char* pBuffer = (unsigned char*)calloc(msgLen, sizeof(unsigned char)); 
		memset(pBuffer, 0, msgLen);

		int inforLen = msgLen - polyLen;//提取出信息流部分，然后計算當前信息對應crc校驗碼

		for (int j = 0; j < inforLen; j++) {
			pBuffer[j] = msg[j] - '0';
		}

		uint8_t* p = NULL;
		for (int i = 0; i < inforLen; i++) {
			if (pBuffer[i]) {
				p = pBuffer + i + polyLen;
				uint64_t t = poly;
				do {
					*(p--) ^= t & 1;
				} while (t >>= 1);
			}
		}
		p = NULL;

		//計算得到的crc碼和輸入的crc碼進行對比驗證，若每一位都相同，則校驗成功
		for (size_t k = inforLen; k < msgLen; k++) {
			if (msg[k] != pBuffer[k] + 48) {
				if (pBuffer) {
					free(pBuffer);
					pBuffer = NULL;
				}
				return -1;
			}
		}
		if (pBuffer) {
			free(pBuffer);
			pBuffer = NULL;
		}
	}
	return 0;
}