Calculate CRC 15 for CAN BUS

Question

I need to calculate a CRC checksum for a CAN BUS.

Scenario:

My input looks always like the following (where x is either 1 or 0, * marks multiple times x, | marks a section and - is a change of input method, lbis Label, tb is TextBox, cb is ComboBox):

• lb: 0
• tb: 11x
• cb: x
• cb: x
• lb: 1
• tb: 4x => Convert.ToString(8-64 / 8, 2).PadLeft(4, '0');
• tb: 8-64x, => 8-64 % 8 == 0
• tb: 15x => CRC of above
• lb: 1
• lb: 11
• lb: 1111111
• lb: 111

Which returns this layout:

0|11*x-x|x-1-4*x|64*x|15*x-1|11|1111111|111

Example:

00101010101000100100101010100101010(missing 15*x CRC sum)1111111111111

This string will be processed by the following string extension, so maximal 5 equal digits follow each other:

public static string Correct4CRC(this string s)
{
    return s.Replace("00000", "000001").Replace("11111", "111110");
}

After that following method returns the divisor:

public static BigInteger CreateDivisor(string s)
{
    var i = BigInteger.Parse(s);
    var d = BigInteger.Pow(i, 15) + BigInteger.Pow(i, 14) + BigInteger.Pow(i, 10) + BigInteger.Pow(i, 8) + BigInteger.Pow(i, 7) + BigInteger.Pow(i, 4) + BigInteger.Pow(i, 3) + 1;
    return d;
}

The only problem I've got is the part with ^:

public static string CRC(this string s)
{
    var dd = s.Correct4CRC();
    var dr = dd.CreateDivisor().ToString();
    int drl = dr.Length;
    var d = dd.Substring(0, drl).CreateDivisor();
    var f = d ^ dr.CreateDivisor();
    var p = true;
    while (p)
    {
        d = dd.Substring(0, drl).CreateDivisor();
        f = d ^ dr.CreateDivisor();
        p = d > dd.CreateDivisor();
    }
    return f.ToString();
}

I know this might be closed as asking for code, but please bear with me as I really don't get it. Another problem is, that there is no real documentation which helped me figuring it out.

Anyway, if you know one good doc, which solves my problem please add it as a comment. I'll check it out and close the answer by myself if I get it.

Answer 1

I think your bitstuffing is wrong (the replacement of 00000 with 000001 and of 11111 with 111110), because it doesn't handle avalanche replacements... 0000011110000 that becomes 0000011111000001.

Here http://blog.qartis.com/can-bus/ there seems to be an example. The page is then linked to http://ghsi.de/CRC/index.php?Polynom=1100010110011001&Message=2AA80 that generates some C code for calculating the CRC-15.

// 0000011110000 becomes 0000011111000001
public static string BitStuff(string bits)
{
    StringBuilder sb = null;

    char last = ' ';
    int count = 0;

    for (int i = 0; i < bits.Length; i++)
    {
        char ch = bits[i];

        if (ch == last)
        {
            count++;

            if (count == 5)
            {
                if (sb == null)
                {
                    // The maximum length is equal to the length of bits
                    // plus 1 for length 5, 2 for length 9, 3 for length 13...
                    // This because the maximum expanion is for
                    // 00000111100001111... or 11111000011110000...
                    sb = new StringBuilder(bits.Length + (bits.Length - 1) / 4);
                    sb.Append(bits, 0, i);
                }

                sb.Append(ch);
                last = ch == '0' ? '1' : '0';
                sb.Append(last);
                count = 1;

                continue;
            }
        }
        else
        {
            last = ch;
            count = 1;
        }

        if (sb != null)
        {
            sb.Append(ch);
        }
    }

    return sb != null ? sb.ToString() : bits;
}

// Taken from http://ghsi.de/CRC/index.php?Polynom=1100010110011001&Message=2AA80
public static string Crc15(string bits)
{
    var res = new char[15]; // CRC Result
    var crc = new bool[15];

    for (int i = 0; i < bits.Length; i++)
    {
        bool doInvert = (bits[i] == '1') ^ crc[14];         // XOR required?

        crc[14] = crc[13] ^ doInvert;
        crc[13] = crc[12];
        crc[12] = crc[11];
        crc[11] = crc[10];
        crc[10] = crc[9] ^ doInvert;
        crc[9] = crc[8];
        crc[8] = crc[7] ^ doInvert;
        crc[7] = crc[6] ^ doInvert;
        crc[6] = crc[5];
        crc[5] = crc[4];
        crc[4] = crc[3] ^ doInvert;
        crc[3] = crc[2] ^ doInvert;
        crc[2] = crc[1];
        crc[1] = crc[0];
        crc[0] = doInvert;
    }

    // Convert binary to ASCII
    for (int i = 0; i < 15; i++)
    {
        res[14 - i] = crc[i] ? '1' : '0';
    }

    return new string(res);
}

and then:

string bits = "0101010101010000000"; // Example data
string crc = Crc15(bits);

bits = bits + crc;
bits = BitStuff(bits);

bits += '1'; // CRC delimiter

bits += 'x'; // ACK slot TODO

bits += '1'; // ACK delimiter
bits += "1111111"; // EOF

Note that you have to put the value for the ACK slot