ISO/IEC13239 CRC16 Implementation

4
votes

I need a CRC16 implementation for NFC Tags. As the standard tolds me this is ISO/IEC13239 and a sample C code is provided. I translated this code into Java but it gives me wrong results:

private static final char POLYNOMIAL = 0x8404;
private static final char PRESET_VALUE = 0xFFFF;

public static int crc16(byte[] data) {
char current_crc_value = PRESET_VALUE;
for (int i = 0; i < data.length; i++) {
    current_crc_value = (char) (current_crc_value ^ ((char) data[i]));
    for (int j = 0; j < 8; j++) {
    if ((current_crc_value & 0x0001) == 0x0001) {
        current_crc_value = (char) ((current_crc_value >>> 1) ^ POLYNOMIAL);
    } else {
        current_crc_value = (char) (current_crc_value >>> 1);
    }
    }
}
current_crc_value = (char) ~current_crc_value;

return current_crc_value;
}

As the standard tells me a byte sequence of 1,2,3,4 should create a CRC Value of 0x3991 A C Version is here on Page 42: http://www.waazaa.org/download/fcd-15693-3.pdf

Also other CRC Implementations does not work: crc16 implementation java The first gives me 0x9e33, the second 0x0FA1 (my implementation by the way says 0xE1E5)

Does someone find an error in my sample or is there another CRC16 Implementation thats really works?

3
javacrc16
The CRC needs to manipulated with variables 16 bits wide and unsigned. Your variable crc_current_value is a char. You also have a lot of casting to char throught the routine... – guga
You need to be aware that there is a much faster algorithm than this, using precomputed tables. – user207421
@EJP: you mean that one in the link? That gives me complete different result... – reox
You have to tweak the polynomial and the initial value to suit your case. It does work, I've been using it for 25 years, 17 in Java. – user207421

3 Answers

5
votes

Your answer is pretty close, but I think there may be some problems with masking and polynomials. Here are some tweaks that seem to work for me:

private static final int POLYNOMIAL   = 0x8408;
private static final int PRESET_VALUE = 0xFFFF;

public static int crc16(byte[] data)
{
  int current_crc_value = PRESET_VALUE;
  for (int i = 0; i < data.length; i++ )
  {
    current_crc_value ^= data[i] & 0xFF;
    for (int j = 0; j < 8; j++)
    {
      if ((current_crc_value & 1) != 0)
      {
        current_crc_value = (current_crc_value >>> 1) ^ POLYNOMIAL;
      }
      else
      {
        current_crc_value = current_crc_value >>> 1;
      }
    }
  }
  current_crc_value = ~current_crc_value;

  return current_crc_value & 0xFFFF;
}
2
votes

For a start - the PDF has:

#define POLYNOMIAL 0x8408 // x^16 + x^12 + x^5 + 1

while you have

private static final char POLYNOMIAL = 0x8404;

This would certainly cause issues - please fix that and let us know if that was the problem.

I am a little concerned that they state that 0x8408 is equivalent to x^16 + x^12 + x^5 + 1 because it is not, that polynomial would be represented by 0x8811. 0x8408 would represent x^16 + x^11 + x^4 which is unlikely to be correct as it is neither prime n'or primitive. For that matter neither is 0x8404.

0
votes

Here is a faster implementation (source).

Use ccittPoly with initial value 0xFFFF and complement the result. This gives 0x3991 for new byte[]{1, 2, 3, 4}.

public class Crc16 {

// Generator polynom codes:
public static final int stdPoly    = 0xA001; // standard CRC-16 x16+x15+x2+1 (CRC-16-IBM)
public static final int stdRPoly   = 0xC002; // standard reverse x16+x14+x+1 (CRC-16-IBM)
public static final int ccittPoly  = 0x8408; // CCITT/SDLC/HDLC X16+X12+X5+1 (CRC-16-CCITT)
   // The initial CRC value is usually 0xFFFF and the result is complemented.
public static final int ccittRPoly = 0x8810; // CCITT reverse X16+X11+X4+1   (CRC-16-CCITT)
public static final int lrcPoly    = 0x8000; // LRCC-16 X16+1

private short[] crcTable;

public Crc16 (int polynom) {
   crcTable = genCrc16Table(polynom); }

public int calculate (byte[] data, int initialCrcValue) {
   int crc = initialCrcValue;
   for (int p = 0; p < data.length; p++) {
      crc = (crc >> 8) ^ (crcTable[(crc & 0xFF) ^ (data[p] & 0xFF)] & 0xFFFF); }
   return crc; }

private static short[] genCrc16Table (int polynom) {
   short[] table = new short[256];
   for (int x = 0; x < 256; x++) {
      int w = x;
      for (int i = 0; i < 8; i++) {
         if ((w & 1) != 0) {
            w = (w >> 1) ^ polynom; }
          else {
            w = w >> 1; }}
      table[x] = (short)w; }
   return table; }

}