How to Calculate CRC-CCITT from ISO FDX-B microchip data

I’m having trouble calculating the correct CRC value for the 64 bit data stored in a ISO FDX-B complaint microchip. I know the correct CRC should be 0x73f9. Any help would be appreciated. The code is Java not C++.

The raw data is:

    Forward LSB - MSB
    00010011 10000010 00011100 00101000 01011010 01101111 00000000 00000001
       19      130       28       40       90       111      0        1
    
    Reverse MSB - LSB
    10000000 00000000 11110110 01011010 00010100 00111000 01000001 11001000 
      128      0        246       90      20        56       65       200

I feed this into a routine crc16 respectfully;

    	byte[] y = { (byte)19,      (byte)130,       (byte)28,       (byte)40,       (byte)90,       (byte)111,      (byte)0,        (byte)1 };
    
    	crc = crc16(y);
        // crc = oxa7f0;
    
    byte[] x = { (byte)128,      (byte)0,        (byte)246,       (byte)90,      (byte)20,        (byte)56,       (byte)65 ,      (byte)200};	
    	
    int crc = crc16(x);
    // crc = 0x1438

Here's the crc routine:

    // Calculates the 16 bit CRC value of the byte buffer
    public static int crc16(byte[] bytes)
    {
    	int crc = 0xFFFF; // initial value
    	int polynomial = 0x8408; // 0001 0000 0010 0001 (0, 5, 12)
    
    	for (byte b : bytes)
    	{
    		for (int i = 0; i < 8; i++)
    		{
    			boolean bit = ((b >> (7 - i) & 1) == 1);
    			boolean c15 = ((crc >> 15 & 1) == 1);
    			crc <<= 1;
    			if (c15 ^ bit)
    				crc ^= polynomial;
    		}
    	}
    
    	crc &= 0xffff;
    
    	return crc;
    }

You are probably doing something wrong.

This is an Arduino/C++ forum and not the place to ask.

Where did you get the test data from and how do you know it is the correct CRC? Where did you get the CRC code from? It would be nice if you tell us if you happen to get a solution from your post in Stackoverflow.

Pete

@jremington it wouldn't be the first time...

@el_supremo thanks for the serious response. I will certainly cross post the solution when I find it. So, the data is from a reader I built running on an Arduino UNO. I put this code up in my Java environment as it has a good debugger. I calculated the source data manually multiple times as well as validated it in my program. Additionally, I have a commercial reader that gives the same results for all fields so I'm confident the data and expected checksum are accurate. The algorithm must be wrong and I found it on StackOverflow decoding similar FDX-B data. I've tried numerous others to no avail.

Change the initial value to zero int crc = 0; // initial value and try both x and y again. I think you'll find that either x gets the correct result directly or its result is correct but bit-reversed - i.e. it will produce 0x9FCE instead of 0x73F9.

Pete

Hi Pete, you are correct! An initial value of 0 returns X: 69ab (MSB – LSB source) and Y: 9fce (the LSB - MSB source). So taking the calculated checksum 9FCE and reversing the bits I get the correct checksum. I'm curious as to why the reversal is needed as I would never thought of performing that on the calculated value.

1001 1111 1100 1110 9 F C E

7 3 F 9 0111 0011 1111 1001

I appreciate the help Pete. Now I can roll this into my reader sketch and know I have a good read.

Just as an FYI I found a catalog of all the CRC protocols here:

http://reveng.sourceforge.net/crc-catalogue/16.htm

And these links are on-line CRC calculators, neither of which could give me the correct checksum:

https://www.lammertbies.nl/comm/info/crc-calculation.html

http://www.zorc.breitbandkatze.de/crc.html

The data are transmitted low order bit and low order byte first. The CRC result also appears to be transmitted low order bit first, so you have to invert the output of your CRC result to match what the tag sends or rewrite your CRC calculator to change the order of the computation - which might be a good idea since you could then verify the CRC in an RFID message without having to reverse the bits in the 64-bit message and the CRC.

This datasheet has a good description of the protocol - or at least, it was very useful to me. On page 34, figure 7-1 and Table 7-1 show the ordering in which the bits are sent and has an example of a 64-bit message plus its corresponding CRC.

Pete

That’s what I tried to do by summing LSB-MSB and vs vs. In the end what I care about is a match of the 2 check sums and not their real values so in the interest of saving compute cycles I used both LSB-MSB versions eliminating the reversals. So here’s a C++ sketch that does this.

You have been a supremo help Peter…thanks again…ed

// Calculates the 16 bit CRC value of the byte buffer
// Note: Some algorithms require a bit wise reversal of the returned CRC to match
unsigned int crc16(unsigned char *bytes, int len)
{
    unsigned int crc = 0x0; //  initial value
    int polynomial = 0x1021;

    for (int idx=0; idx<len; idx++)
    {
        char b = bytes[idx];
        
        for (int i = 0; i < 8; i++)
        {
            boolean bit = ((b >> (7 - i) & 1) == 1);
            boolean c15 = ((crc >> 15 & 1) == 1);
            crc <<= 1;
            if (c15 ^ bit)
                crc ^= polynomial;
        }
    }

    crc &= 0xffff;

    return crc;
}

void setup()
{
     Serial.begin(9600);

   
    unsigned char datay[8] = { 19,     130,       28,       40,       90,       111,      0,        1 };
 
    // Should return 0x9FCE
    unsigned int y = crc16(datay, 8);
   
    Serial.print("Y: ");
    Serial.println(y, HEX);
}

void loop()
{
    delay(250);
}

When you read the RFID data, you can use a property of CRC polynomials to make the check slightly easier. Instead of doing a CRC on the 8 bytes of data and testing whether they are equal to the CRC, you do a CRC of the 10 bytes (data+CRC) and then all you need to test for is whether the CRC function returned zero or not. It will be zero if the data+CRC are correct. Otherwise it will be non-zero.
Here’s an addition to your code to illustrate it:

// Calculates the 16 bit CRC value of the byte buffer
// Note: Some algorithms require a bit wise reversal of the returned CRC to match
unsigned int crc16(unsigned char *bytes, int len)
{
    unsigned int crc = 0x0; //  initial value
    int polynomial = 0x1021;

    for (int idx=0; idx<len; idx++)
    {
        char b = bytes[idx];
       
        for (int i = 0; i < 8; i++)
        {
            boolean bit = ((b >> (7 - i) & 1) == 1);
            boolean c15 = ((crc >> 15 & 1) == 1);
            crc <<= 1;
            if (c15 ^ bit)
                crc ^= polynomial;
        }
    }

    crc &= 0xffff;

    return crc;
}

void setup()
{
     Serial.begin(9600);
  while(!Serial);
   
    unsigned char datay[8] = { 19,     130,       28,       40,       90,       111,      0,        1 };

    // datay with CRC on the end
    unsigned char datay_crc[10] = {
      19, 130, 28, 40, 90, 111, 0, 1, 0x9F, 0xCE
    };
    
    // Should return 0x9FCE
    unsigned int y = crc16(datay, 8);
   
    Serial.print("Y: ");
    Serial.println(y, HEX);

    // do a CRC over 8 data bytes and 2 CRC bytes
    unsigned int x  = crc16(datay_crc, 10);
   
    Serial.print("X: ");
    Serial.println(x, HEX);

    // So in the actual code, the "real" way to code it would be:
    if(crc16(datay_crc, 10)) {
      // A CRC over data+CRC must return zero for success.
      // This has returned non-zero and has failed.
      Serial.println("CRC FAILED!");
      // Code to handle CRC failure
      // Usually you would try reading the tag again
      // or return an error
    } else {
      Serial.println("CRC MATCHED");
      // Handle CRC success - decode the data
    }
}

void loop()
{
    delay(250);
}

Pete

P.S. This method avoids the need to extract the CRC bytes from the message and assemble them into a 16-bit integer. The CRC on the end just becomes part of the message over which the CRC is calculated.

Pete

sweet mod.

worked perfectly!

Excellent.

Pete

Oh, do you mean with "live" input from a microchip reader?

Pete

sure do

Splendid :)

Pete

So I ran into a bit of a challenge. With a bad read I sometimes see a boat load of zeros. Its not a problem if I reject the read but taking a CRC over zeros with a zero CRC passes! I’m temped to look at the raw CRC bytes to check for zero and reject on that before taking the real CRC. I added 2 test cases to the sample code.

// Calculates the 16 bit CRC value of the byte buffer
// Note: Some algorithms require a bit wise reversal of the returned CRC to match
unsigned int crc16(unsigned char *bytes, int len)
{
    unsigned int crc = 0x0; //  initial value
    int polynomial = 0x1021;

    for (int idx=0; idx<len; idx++)
    {
        char b = bytes[idx];
      
        for (int i = 0; i < 8; i++)
        {
            boolean bit = ((b >> (7 - i) & 1) == 1);
            boolean c15 = ((crc >> 15 & 1) == 1);
            crc <<= 1;
            if (c15 ^ bit)
                crc ^= polynomial;
        }
    }

    crc &= 0xffff;

    return crc;
}

void setup()
{
    Serial.begin(9600);

    // Test all zeros
    unsigned char data_zero[10] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
    unsigned int z  = crc16(data_zero, 10);
    Serial.print("Z: ");
    Serial.println(z, HEX);

    unsigned char data_zero1[8] = { 0, 0, 0, 0, 0, 0, 0, 0, };
    unsigned z1  = crc16(data_zero1, 8);
    Serial.print("Z1: ");
    Serial.println(z1, HEX);
  
 
  
    unsigned char datay[8] = { 19,     130,       28,       40,       90,       111,      0,        1 };

    // datay with CRC on the end
    unsigned char datay_crc[10] = { 19, 130, 28, 40, 90, 111, 0, 1, 0x9F, 0xCE };
    
    // Should return 0x9FCE
    unsigned int y = crc16(datay, 8);
  
    Serial.print("Y: ");
    Serial.println(y, HEX);

    // do a CRC over 8 data bytes and 2 CRC bytes
    unsigned int x  = crc16(datay_crc, 10);
  
    Serial.print("X: ");
    Serial.println(x, HEX);

    // So in the actual code, the "real" way to code it would be:
    if(crc16(datay_crc, 10)) 
    {
      // A CRC over data+CRC must return zero for success.
      // This has returned non-zero and has failed.
      Serial.println("CRC FAILED!");
      
      // Code to handle CRC failure
      // Usually you would try reading the tag again
      // or return an error
    }
    else
    {
      Serial.println("CRC MATCHED");
      // Handle CRC success - decode the data
    }
}

void loop()
{
    delay(250);
}

You may have to do that. The problem is that the CRC basically divides the data by an odd number and the CRC result is the remainder of that division. If the data are zero then the result is zero. This is why some implementations of CRC require a non-zero start value. All you can do is if the CRC passes (returns zero) then test all 8 data bytes for zero.

taking a CRC over zeros with a zero CRC passes

It's not a zero CRC, it's a zero start value. The CRC itself is still the same polynomial.

Pete

That will work Pete. Just another sanity check. Is starting with an initial value of 0 part of the FDX-B protocol or a quirk of how I implemented it?

I haven't found a document which explicitly states what the start value should be. I played with several variations of the CRC implementation until I got a CRC which matched your example and an example I found online. Those needed an initial value of zero to match the example CRCs. They certainly won't match when 0xFFFF is used instead of zero.

Pete