CRC calculation with arbitrary values and lengths

Question

I am trying to modify that piece of code to make it work with arbitrary values and lengths.

My modification so far:

public static int ModRTU_CRC(final byte[] buf, int crc)
{
    final int len = buf.length;

    for (int pos = 0; pos < len; pos++)
    {
        crc ^= buf[pos]; // XOR byte into least sig. byte of crc

        for (int i = 8; i != 0; i--)
        { // Loop over each bit
            if ((crc & 0x0001) != 0)
            { // If the LSB is set
                crc >>= 1; // Shift right and XOR 0xA001
                crc ^= 0xA001;
            }
            else
            {
                // Else LSB is not set
                crc >>= 1; // Just shift right
            }
        }
    }
    // Note, this number has low and high bytes swapped, so use it
    // accordingly (or swap bytes)
    return crc;
}

I'm testing my code in the following way:

final String a = "1101011011";
final String crc = "10011";
final int parsedA = Integer.parseInt(a, 2);
final ByteBuffer parsedBytes = ByteBuffer.allocate(4).putInt(parsedA);
final byte[] array = parsedBytes.array();
final int parsedCRC = Integer.parseInt(crc, 2);

System.out.println(Integer.toBinaryString(ModRTU_CRC(array, parsedCRC)));

I get 1000111101000101 but the correct answer is 11010110111110. Even if i swap bytes i don't get to the goal. Can you help me please to figure out where i made a mistake?

In the linked code, `crc` starts at 0xFFFF, but here it starts at some other value that we can't see in your code (depending on the value of `b`). Is this correct? — user253751, Mar 30 '14 at 09:52
Correct, crc is depending on the value of b. In this case `crc` would be `0x13`. — Danny Lo, Mar 30 '14 at 09:58
The code in the question does not show the value of `b`, so you might want to add that. Also, how did you calculate that `11010110111110` is the correct answer? Also, apart from the starting value of `crc`, are there any differences between this code and the linked code? — user253751, Mar 30 '14 at 10:02
Oops, `crc` is meant to be `b`. Fixed that: `final int parsedCRC = Integer.parseInt(crc, 2);` I calculated `11010110111110` on a piece of paper: `1110` is a remainder of division `1101011011` by `10011`. There are 2 differences: i get length of the buffer from buffer itself. Plus crc is not fixed, I pass it to the method. — Danny Lo, Mar 30 '14 at 10:09
A CRC isn't the remainder of division. Also you didn't print `a`, only the calculated CRC, so even if it did return `1110` it would only print `1110` and not `11010110111110`. — user253751, Mar 30 '14 at 10:21

Mark Adler · Accepted Answer · 2014-03-31T00:13:57.950

You are seriously confused. Your attempted example is directly from Ross William's CRC tutorial. You need to read that tutorial again in its entirety and more slowly, working out everything as you go along.

The CRC and the CRC polynomial are two different things. Your 10011 is the CRC polynomial from the tutorial, x⁴+x+1. Your 1101011011 is the message. From the tutorial, the remainder of dividing the message with 0000 appended by the CRC polynomial is 1110. That is the CRC. It is a four-bit CRC, since it uses a fourth-degree polynomial.

Then what you think you should get is the message with the CRC appended, i.e. 11010110111110. That is not the CRC. That is the message with the CRC appended. That message and CRC appended has the property that if you divide it by the CRC polynomial, you will get a remainder of zero. That is what is normally transmitted once the CRC has been computed.

For some reason you are attempting to perform this operation with a CRC routine that uses a different polynomial for a 16-bit CRC (the 0xA001 is for the polynomial x¹⁶+x¹⁵+x²+1, reversed), feeding the CRC polynomial from the example in the tutorial to where the initial CRC should go in the routine (recall that the CRC and the CRC polynomial are two different things), and providing a 10-bit message as 32 bits. Furthermore you are presenting the message in big-endian order (assuming that you didn't change order of that byte buffer), which feeds a bunch of zeros in first, and you are using a routine that processes eight bits at a time, which makes it impossible to process just ten bits.

You should step away from the CRC routine, and start over with the tutorial.

Thanks for that lengthy explanation. I see now that the algorithm I modified and hoped to apply for various crc polynomial and messages isn't really appropriate or to be precise it has to be modificated more than I expected. I'll make a step back and try to solve my task from the scratch. — Danny Lo, Apr 01 '14 at 14:24

CRC calculation with arbitrary values and lengths

1 Answers1