Right now I'm writing CRC16 realization with polynomials division and without bit shifts (for educational purposes).
My question is: when I have CRC of previous byte and read new byte where I need to place previous remainder for counting new CRC? (before new byte, after new byte or XOR it with new byte, etc...)
My code works fine for on symbol from text file but it doesn't work with more than one symbol. It seems for me that I put the first remainder to wrong place :)
Full code will placed below.
#include <stdio.h>
#include <stdint.h>
void printBits(uint32_t inbyte, int width)
{
char modres = inbyte % 2;
inbyte = inbyte >> 1;
if (width > 0) {
printBits(inbyte, --width);
}
printf("%d", modres);
}
struct polynom
{
uint8_t x16;uint8_t x15;uint8_t x14;uint8_t x13;uint8_t x12;
uint8_t x11;uint8_t x10;uint8_t x9;uint8_t x8;uint8_t x7;
uint8_t x6;uint8_t x5;uint8_t x4;uint8_t x3;uint8_t x2;
uint8_t x1;uint8_t x0;
};
struct polycrc
{
uint8_t x15; uint8_t x14; uint8_t x13; uint8_t x12;
uint8_t x11; uint8_t x10; uint8_t x9; uint8_t x8; uint8_t x7;
uint8_t x6; uint8_t x5; uint8_t x4; uint8_t x3; uint8_t x2;
uint8_t x1; uint8_t x0;
};
struct byte
{
uint8_t x7; uint8_t x6; uint8_t x5; uint8_t x4;
uint8_t x3; uint8_t x2; uint8_t x1; uint8_t x0;
};
void printPolynom(struct polynom inp)
{
printf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",
inp.x16, inp.x15, inp.x14, inp.x13, inp.x12, inp.x11, inp.x10,
inp.x9, inp.x8, inp.x7, inp.x6, inp.x5, inp.x4, inp.x3, inp.x2,
inp.x1, inp.x0);
}
void printCRC(struct polycrc inp)
{
printf("%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d%d",
inp.x15, inp.x14, inp.x13, inp.x12, inp.x11, inp.x10,
inp.x9, inp.x8, inp.x7, inp.x6, inp.x5, inp.x4, inp.x3, inp.x2,
inp.x1, inp.x0);
}
struct polycrc getCRC(uint8_t inByte, struct polycrc inCRC,
struct polynom inp)
{
struct delim
{
uint8_t xb7, xb6, xb5, xb4, xb3, xb2, xb1, xb0,
xa15, xa14, xa13, xa12, xa11, xa10, xa9, xa8, xa7,
xa6, xa5, xa4, xa3, xa2, xa1, xa0;
};
struct Bytes
{
uint8_t b7; uint8_t b6; uint8_t b5;
uint8_t b4; uint8_t b3; uint8_t b2;
uint8_t b1; uint8_t b0;
};
printBits(inByte, 7);
printf("|");
printCRC(inCRC);
printf("\n");
struct Bytes oneByte;
oneByte.b0 = inByte % 2; inByte = inByte / 2;
oneByte.b1 = inByte % 2; inByte = inByte / 2;
oneByte.b2 = inByte % 2; inByte = inByte / 2;
oneByte.b3 = inByte % 2; inByte = inByte / 2;
oneByte.b4 = inByte % 2; inByte = inByte / 2;
oneByte.b5 = inByte % 2; inByte = inByte / 2;
oneByte.b6 = inByte % 2; inByte = inByte / 2;
oneByte.b7 = inByte % 2; inByte = inByte / 2;
if (oneByte.b7 == 1){
inCRC.x7 ^= inp.x0; inCRC.x8 ^= inp.x1; inCRC.x9 ^= inp.x2;
inCRC.x10 ^= inp.x3; inCRC.x11 ^= inp.x4; inCRC.x12 ^= inp.x5;
inCRC.x13 ^= inp.x6; inCRC.x14 ^= inp.x7; inCRC.x15 ^= inp.x8;
oneByte.b0 ^= inp.x9; oneByte.b1 ^= inp.x10; oneByte.b2 ^= inp.x11;
oneByte.b3 ^= inp.x12; oneByte.b4 ^= inp.x13; oneByte.b5 ^= inp.x14;
oneByte.b6 ^= inp.x15; oneByte.b7 ^= inp.x16;
inByte = oneByte.b6 * 2 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b5 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b6 == 1){
inCRC.x6 ^= inp.x0; inCRC.x7 ^= inp.x1; inCRC.x8 ^= inp.x2;
inCRC.x9 ^= inp.x3; inCRC.x10 ^= inp.x4; inCRC.x11 ^= inp.x5;
inCRC.x12 ^= inp.x6; inCRC.x13 ^= inp.x7; inCRC.x14 ^= inp.x8;
inCRC.x15 ^= inp.x9; oneByte.b0 ^= inp.x10; oneByte.b1 ^= inp.x11;
oneByte.b2 ^= inp.x12; oneByte.b3 ^= inp.x13; oneByte.b4 ^= inp.x14;
oneByte.b5 ^= inp.x15; oneByte.b6 ^= inp.x16;
inByte = oneByte.b5 * 2 * 2 * 2 * 2 * 2;
inByte += oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b5 == 1){
inCRC.x5 ^= inp.x0; inCRC.x6 ^= inp.x1; inCRC.x7 ^= inp.x2;
inCRC.x8 ^= inp.x3; inCRC.x9 ^= inp.x4; inCRC.x10 ^= inp.x5;
inCRC.x11 ^= inp.x6; inCRC.x12 ^= inp.x7; inCRC.x13 ^= inp.x8;
inCRC.x14 ^= inp.x9; inCRC.x15 ^= inp.x10; oneByte.b0 ^= inp.x11;
oneByte.b1 ^= inp.x12; oneByte.b2 ^= inp.x13; oneByte.b3 ^= inp.x14;
oneByte.b4 ^= inp.x15; oneByte.b5 ^= inp.x16;
inByte = oneByte.b4 * 2 * 2 * 2 * 2;
inByte += oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b4 == 1){
inCRC.x4 ^= inp.x0; inCRC.x5 ^= inp.x1; inCRC.x6 ^= inp.x2;
inCRC.x7 ^= inp.x3; inCRC.x8 ^= inp.x4; inCRC.x9 ^= inp.x5;
inCRC.x10 ^= inp.x6; inCRC.x11 ^= inp.x7; inCRC.x12 ^= inp.x8;
inCRC.x13 ^= inp.x9; inCRC.x14 ^= inp.x10; inCRC.x15 ^= inp.x11;
oneByte.b0 ^= inp.x12; oneByte.b1 ^= inp.x13; oneByte.b2 ^= inp.x14;
oneByte.b3 ^= inp.x15; oneByte.b4 ^= inp.x16;
inByte = oneByte.b3 * 2 * 2 * 2;
inByte += oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b3 == 1){
inCRC.x3 ^= inp.x0; inCRC.x4 ^= inp.x1; inCRC.x5 ^= inp.x2;
inCRC.x6 ^= inp.x3; inCRC.x7 ^= inp.x4; inCRC.x8 ^= inp.x5;
inCRC.x9 ^= inp.x6; inCRC.x10 ^= inp.x7; inCRC.x11 ^= inp.x8;
inCRC.x12 ^= inp.x9; inCRC.x13 ^= inp.x10; inCRC.x14 ^= inp.x11;
inCRC.x15 ^= inp.x12; oneByte.b0 ^= inp.x13; oneByte.b1 ^= inp.x14;
oneByte.b2 ^= inp.x15; oneByte.b3 ^= inp.x16;
inByte = oneByte.b2 * 2 * 2;
inByte += oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b2 == 1){
inCRC.x2 ^= inp.x0; inCRC.x3 ^= inp.x1; inCRC.x4 ^= inp.x2;
inCRC.x5 ^= inp.x3; inCRC.x6 ^= inp.x4; inCRC.x7 ^= inp.x5;
inCRC.x8 ^= inp.x6; inCRC.x9 ^= inp.x7; inCRC.x10 ^= inp.x8;
inCRC.x11 ^= inp.x9; inCRC.x12 ^= inp.x10; inCRC.x13 ^= inp.x11;
inCRC.x14 ^= inp.x12; inCRC.x15 ^= inp.x13; oneByte.b0 ^= inp.x14;
oneByte.b1 ^= inp.x15; oneByte.b2 ^= inp.x16;
inByte = oneByte.b1 * 2;
inByte += oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b1 == 1){
inCRC.x1 ^= inp.x0; inCRC.x2 ^= inp.x1; inCRC.x3 ^= inp.x2;
inCRC.x4 ^= inp.x3; inCRC.x5 ^= inp.x4; inCRC.x6 ^= inp.x5;
inCRC.x7 ^= inp.x6; inCRC.x8 ^= inp.x7; inCRC.x9 ^= inp.x8;
inCRC.x10 ^= inp.x9; inCRC.x11 ^= inp.x10; inCRC.x12 ^= inp.x11;
inCRC.x13 ^= inp.x12; inCRC.x14 ^= inp.x13; inCRC.x15 ^= inp.x14;
oneByte.b0 ^= inp.x15; oneByte.b1 ^= inp.x16;
inByte = oneByte.b0;
return getCRC(inByte, inCRC, inp);
}
else if (oneByte.b0 == 1){
inCRC.x0 ^= inp.x0; inCRC.x1 ^= inp.x1; inCRC.x2 ^= inp.x2;
inCRC.x3 ^= inp.x3; inCRC.x4 ^= inp.x4; inCRC.x5 ^= inp.x5;
inCRC.x6 ^= inp.x6; inCRC.x7 ^= inp.x7; inCRC.x8 ^= inp.x8;
inCRC.x9 ^= inp.x9; inCRC.x10 ^= inp.x10; inCRC.x11 ^= inp.x11;
inCRC.x12 ^= inp.x12; inCRC.x13 ^= inp.x13; inCRC.x14 ^= inp.x14;
inCRC.x15 ^= inp.x15; oneByte.b0 ^= inp.x16;
inByte = 0;
return getCRC(inByte, inCRC, inp);
}
else {
return inCRC;
}
}
int main()
{
// Initializing polynomial
struct polynom p;
p.x16 = 1; p.x15 = 1; p.x2 = 1; p.x0 = 1;
p.x14 = 0; p.x13 = 0; p.x12 = 0; p.x11 = 0; p.x10 = 0; p.x9 = 0;
p.x8 = 0; p.x7 = 0; p.x6 = 0; p.x5 = 0; p.x4 = 0;
p.x3 = 0; p.x1 = 0;
// Initializing CRC
struct polycrc crc;
crc.x15 = 0; crc.x14 = 0; crc.x13 = 0; crc.x12 = 0; crc.x11 = 0;
crc.x10 = 0; crc.x9 = 0; crc.x8 = 0; crc.x7 = 0; crc.x6 = 0;
crc.x5 = 0; crc.x4 = 0; crc.x3 = 0; crc.x2 = 0; crc.x1 = 0;
crc.x0 = 0;
// Print p and crc to check
printPolynom(p);
printf("\n");
printCRC(crc);
printf("\n");
char* inFileName = "input1.txt";
FILE* inputFile;
uint8_t c = 0;
fopen_s(&inputFile, inFileName, "r");
if (inputFile == NULL) {
printf("Error opening file %s", inFileName);
return 1;
}
// Read file and count CRC
c = fgetc(inputFile);
while (!feof(inputFile)) {
crc = getCRC(c, crc, p);
printf("Byte %0x CRC: ", c);
printCRC(crc);
printf("\n");
c = fgetc(inputFile);
}
fclose(inputFile);
return 0;
}
To handle the CRC sequence one byte at a time, the sequence is xor an input byte with the upper (if left shift) or lower (if right shift) 8 bits of the CRC, then cycle the 16 bit CRC like a linear feedback shift register 8 times using the CRC polynomial for the feedback. This can be sped up using a 256 entry lookup table. The question is asking for a hardware like solution that maps an uncycled 16 bit input CRC into an 8 cycled 16 bit output CRC using bit field structures.
The mapping is a binary linear mapping (like a binary (and, xor) matrix multiply with a 16 by 16 bit matrix), and the ordering doesn't matter. A set of 16 equations, each xoring a sub set of the uncycled CRC bits, into a cycled CRC bit can be used. The equations can be created by using a conventional method to cycle a CRC 8 times, for a set of 16 input CRC values, each with 1 bit set: {0x0001, 0x0002, 0x0004, ..., 0x2000, 0x4000, 0x8000} and noting which input bits contribute to each output bit.
Example for a left shifting CRC with polynomial 0x11021, for each byte of input:
/* xor the input byte to the upper 8 bits of the CRC */
crcin.b8 ^= dat.b0;
crcin.b9 ^= dat.b1;
crcin.ba ^= dat.b2;
crcin.bb ^= dat.b3;
crcin.bc ^= dat.b4;
crcin.bd ^= dat.b5;
crcin.be ^= dat.b6;
crcin.bf ^= dat.b7;
/* cycle the 16 bit CRC 8 times via mapping */
crcot.b0 = crcin.b8 ^ crcin.bc;
crcot.b1 = crcin.b9 ^ crcin.bd;
crcot.b2 = crcin.ba ^ crcin.be;
crcot.b3 = crcin.bb ^ crcin.bf;
crcot.b4 = crcin.bc;
crcot.b5 = crcin.b8 ^ crcin.bc ^ crcin.bd;
crcot.b6 = crcin.b9 ^ crcin.bd ^ crcin.be;
crcot.b7 = crcin.ba ^ crcin.be ^ crcin.bf;
crcot.b8 = crcin.b0 ^ crcin.bb ^ crcin.bf;
crcot.b9 = crcin.b1 ^ crcin.bc;
crcot.ba = crcin.b2 ^ crcin.bd;
crcot.bb = crcin.b3 ^ crcin.be;
crcot.bc = crcin.b4 ^ crcin.b8 ^ crcin.bc ^ crcin.bf;
crcot.bd = crcin.b5 ^ crcin.b9 ^ crcin.bd;
crcot.be = crcin.b6 ^ crcin.ba ^ crcin.be;
crcot.bf = crcin.b7 ^ crcin.bb ^ crcin.bf;
crcin = crcot;