CODEWITHSUNDEEP
c#mathcryptographycrccrc8
Rocket254
Rocket254

Reputation: 134

Confirmation of Reverse Reciprocal CRC-8 Value?

I've spent quite a bit of time trying to confirm the type of CRC-8 algorithm used in ASCII data communications between two devices. I have confirmed that the CRC is calculated on the 0x02 Start of text byte + the next byte of data. An Interface Design Document that I have describing one device specifies the use of a 0xEA polynomial with an initial value of 0xFF. An example of one captured message is below:

Input Bytes: 0x02 0x41

CRC Result: b10011011 or 0x9B

Going into the problem, I had little to no knowledge of the inner working of a typical CRC algorithm. Initially, I tried hand calculation against the input bytes to confirm my understanding of the algo before attempting a code solution. This involved XORing the 1st input byte with my 0xFF initial value and then skipping to the second input byte to continue the XOR operations.

Having tried multiple times to confirm the CRC through typical XOR operations while shifting the MSB left out of the register during each step, I could never get the results I wanted. Today, I realized that the 0xEA polynomial is also considered to be a reversed reciprocal of the 0xD5 poly with an implied 1+x^8 that is commonly used in CRC-8 algos. How does this fact change how I would go about manually calculating the CRC? I've read that in some instances a reverse leads to the algo right shifting bits instead of left shifting?

Upvotes: 0

Views: 911

Answers (1)

rcgldr
rcgldr

Reputation: 28921

The polynomial is x^8+x^7+x^5+x^3+x^2+x+1 => 01AF bit reversed to x^8+x^7+x^6+x^5+x^3+x+1 => 0x1EB. Example code where the conditional XOR is done after the shift, so the XOR value is 0x1EB>>1 = 0xF5. A 256 byte table lookup could be used to replace the inner loop.

using System;
namespace crc8r
{
    class Program
    {
        private static byte crc8r(byte[] bfr, int bfrlen)
        {
            byte crc = 0xff;
            for (int j = 0; j < bfrlen; j++)
            {
                crc ^= bfr[j];
                for (int i = 0; i < 8; i++)
                    // assumes twos complement math
                    crc = (byte)((crc>>1)^((0-(crc&1))&0xf5));
            }
            return crc;
        }

        static void Main(string[] args)
        {
            byte[] data = new byte[3] {0x02, 0x41, 0x00};
            byte crc;
            crc = crc8r(data, 2);           // crc == 0x9b
            Console.WriteLine("{0:X2}", crc);
            data[2] = crc;
            crc = crc8r(data, 3);           // crc == 0x00
            Console.WriteLine("{0:X2}", crc);
            return;
        }
    }
}

Regarding "EA", if the polynomial is XOR'ed before the shift, 0x1EB (or 0x1EA since bit 0 will be shifted off and doesn't matter) is used. XOR'ing before the shift requires 9 bits, or a post shift OR or XOR of 0x80, while XOR'ing after the shift only requires 8 bits.

Example line of code using 0x1eb before the shift:

                    crc = (byte)((crc^((0-(crc&1))&0x1eb))>>1);

Upvotes: 1

Related Questions