Understanding results of CRC8 SAE J1850 (normal) vs. "Zero"

Question

I need a verification of CRC8-SAE-J1850 messages and therefore wrote a script, that reads logs and needs to calculate CRC8 (non ZERO) from there to match them with the CRC8 values in the log and then check which step in the tool chain caused the hassle.

Anyway, I spent some time looking into documentation, SO posts and other peoples sourcecode, but I want to stick with python for easier textprocessing and interfaces to my other tools.

I found some code on sourceforge evansneath's Python CRC Implementation which is nicely straight forward and wanted to give it a go, but I figured it does not work as expected (maybe I understood something completely wrong, but I am stuck here):

def crc(msg, div, code='11111111'):
    """Cyclic Redundancy Check
        Generates an error detecting code based on an inputted message and divisor in the form of a polynomial representation.
        Arguments:
        msg: The input message of which to generate the output code.
        div: The divisor in polynomial form. For example, if the polynomial of x^3 + x + 1 is given, this should be represented as '1011' in the div argument.
        code: This is an option argument where a previously generated code may be passed in. This can be used to check validity. If the inputted code produces an outputted code of all zeros, then the message has        no errors.
    Returns:
        An error-detecting code generated by the message and the given divisor.
    """

    msg = msg + code
    msg = list (msg)
    div = list (div)

    for i in range (len (msg) - len (code)):
        if msg[i] == '1':
            for j in range (len (div)):
               msg[i+j] = str ((int (msg[i+j])+int (div[j]))%2)

    return ''.join (msg[-len (code):])

#Testing:
# Use a divisor that simulates: CRC8 SAE J1850 x^8+x^4+x^3+x^2+x^0
div = '100011101'#0x1D with leading 1 as given by polynomial
msg = '10101001' # 0xA9, just for a Test

print('Input message:', hex(int(msg,2)))
print('Polynomial:', hex(int(div,2)))

o = '11111111'
z = '00000000'

code = crc(msg, div, o)

print('CRC8 code:', hex(int(code,2)))

# Test for output code of '00000000' respectively '11111111' proving that the function worked correctly
print('Success:', crc(msg, div, code) == o)

I checked the results using this generator: CRC Generator which seems to be the only one featuring CRC8 SAE J1850 ZERO and non-ZERO.

Now the fun part: for ZERO the above code works perfectly fine.

Unfortunately the CRC codes I get from the software I want to check are initialized and checked against 0xFF ('11111111') where both tools deliver completely different results. So far I wasn't even able to find some off-by-one issue (which I would have rated the most likely case) or a mathematical link between the solution calculated by the script above and the one by the website. The website complies with the result from the software however the python part above doesn't.

Can anyone point me to a documentation I might have missed or is it another issue? I already checked for MSB/LSB issues when entering messages on the website and tried initializing with 0xFE as some other code suggested. But no success... Most examples however are zero based and there I have no issues.

Edit:

I checked the calculation and went through an example by hand as well as printing every single step and achieved the same. So mathematically it seems correct, but what is the SAE doing other than appending a line of '11111111' and then XOR-ing bitwise, then shifting until there is a leading one again, XOR-ing etc... and spitting out the remainder? It must be an issue of understanding on my side.

Test 1 ---------------------------
Input message: 0xa9
Polynome: 0x11d
['1', '0', '1', '0', '1', '0', '0', '1', '1', '1', '1', '1', '1', '1', '1', 1']
 /
['1', '0', '0', '0', '1', '1', '1', '0', '1']
 =
current message: ['1', '0', '1', '0', '1', '0', '0', '1', '1', '1', '1', '1', '1 ', '1', '1', '1']
shift 0 Bits
1 XOR 1 = 0
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 0 = 0
1 XOR 1 = 0
0 XOR 1 = 1
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
current message: ['0', '0', '1', '0', '0', '1', '1', '1', '0', '1', '1', '1', '1 ', '1', '1', '1']
shift 2 Bits
1 XOR 1 = 0
0 XOR 0 = 0
0 XOR 0 = 0
1 XOR 0 = 1
1 XOR 1 = 0
1 XOR 1 = 0
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
current message: ['0', '0', '0', '0', '0', '1', '0', '0', '1', '1', '0', '1', '1 ', '1', '1', '1']
shift 5 Bits
1 XOR 1 = 0
0 XOR 0 = 0
0 XOR 0 = 0
1 XOR 0 = 1
1 XOR 1 = 0
0 XOR 1 = 1
1 XOR 1 = 0
1 XOR 0 = 1
1 XOR 1 = 0
CRC8 code: 0xab

Reverse Calculation: Check
['1', '0', '1', '0', '1', '0', '0', '1', '1', '0', '1', '0', '1', '0', '1', '1']
 /
['1', '0', '0', '0', '1', '1', '1', '0', '1']
 =
current message: ['1', '0', '1', '0', '1', '0', '0', '1', '1', '0', '1', '0', '1', '0', '1', '1']
shift 0 Bits
1 XOR 1 = 0
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 0 = 0
1 XOR 1 = 0
0 XOR 1 = 1
0 XOR 1 = 1
1 XOR 0 = 1
1 XOR 1 = 0
current message: ['0', '0', '1', '0', '0', '1', '1', '1', '0', '0', '1', '0', '1', '0', '1', '1']
shift 2 Bits
1 XOR 1 = 0
0 XOR 0 = 0
0 XOR 0 = 0
1 XOR 0 = 1
1 XOR 1 = 0
1 XOR 1 = 0
0 XOR 1 = 1
0 XOR 0 = 0
1 XOR 1 = 0
current message: ['0', '0', '0', '0', '0', '1', '0', '0', '1', '0', '0', '0', '1', '0', '1', '1']
shift 5 Bits
1 XOR 1 = 0
0 XOR 0 = 0
0 XOR 0 = 0
1 XOR 0 = 1
0 XOR 1 = 1
0 XOR 1 = 1
0 XOR 1 = 1
1 XOR 0 = 1
0 XOR 1 = 1
CRC correct: True

Solution 1

I solved it.

It is never mentioned that for the SAE J1850 the input is XORed with 0xFF. Even though the C-code Mark Adler provided states precisely that in crc ^= 0xff; however it didn't help me understand what my problem was.

It was not a bug, my code worked correctly but it was the premises I assumed.

This is why the C-Code did not help me solve the issue, because I never understood THIS was the problem in the first place.

The corrected code for SAE J1850 Calculation (with XORin 0xFF, XORout 0xFF, non reflected, non reversed, polynomial 0x1D) Bit-by-Bit is as follows.

Credits for the code remain with evensneath on github, I merely changed the input.

def crc(msg, div, code='11111111'):
"""Cyclic Redundancy Check
Generates an error detecting code based on an inputted message
and divisor in the form of a polynomial representation.
Arguments:
    msg: The input message of which to generate the output code.
    div: The divisor in polynomial form. For example, if the polynomial
        of x^3 + x + 1 is given, this should be represented as '1011' in
        the div argument.
    code: This is an option argument where a previously generated code may
        be passed in. This can be used to check validity. If the inputted
        code produces an outputted code of all zeros, then the message has
        no errors.
Returns:
    An error-detecting code generated by the message and the given divisor.
"""
# Append the code to the message. If no code is given, default to '1111111'
# Uncomment every occurence of msg_XORIN if not CRC-8 SAE J1850 
msg_XORIN = [] # XOR the input before appending the code
msg_XORIN = [str((int(msg[i])+1) %2) for i in range(len(list(msg)))]
msg = msg_XORIN

div = list(div)
msg = list(msg) + list(code) # Convert msg and div into list form for easier handling

# Loop over every message bit (minus the appended code)
for i in range(len(msg)-len(code)):
    # If that messsage bit is not one, shift until it is.
    if msg[i] == '1':
        for j in range(len(div)):
            # Perform modulo 2 ( == XOR) on each index of the divisor
            msg[i+j] = str((int(msg[i+j])+int(div[j]))%2)

# Output the last error-checking code portion of the message generated

return ''.join(msg[-len(code):])

The testcases from the question can be carried over. call once to generate CRC, call again with msg + generated crc to verify.

Good source: http://reveng.sourceforge.net/crc-catalogue/1-15.htm#crc.cat-bits.8

Solution 2

That CRC is normally defined with these parameters:

width=8 poly=0x1d init=0xff refin=false refout=false xorout=0xff check=0x4b name="CRC-8/SAE-J1850"

crcgen will take that and produce C code to compute the CRC. You can easily translate that to Python if you like. Here is the bit-wise routine in C from crcgen:

#include <stdint.h>

unsigned crc8sae_j1850_bit(unsigned crc, unsigned char const *data, size_t len) {
    if (data == NULL)
        return 0;
    crc ^= 0xff;
    while (len--) {
        crc ^= *data++;
        for (unsigned k = 0; k < 8; k++)
            crc = crc & 0x80 ? (crc << 1) ^ 0x1d : crc << 1;
    }
    crc &= 0xff;
    crc ^= 0xff;
    return crc;
}

The "ZERO" version as listed on the linked CRC calculator page has these parameters, simply changing the initial and xorout values to zero:

width=8 poly=0x1d init=0x00 refin=false refout=false xorout=0x00 check=0x37 name="CRC-8/SAE-J1850-ZERO"

Here is the bit-wise routine in C from crcgen for that one:

#include <stdint.h>

unsigned crc8sae_j1850_zero_bit(unsigned crc, unsigned char const *data, size_t len) {
    if (data == NULL)
        return 0;
    while (len--) {
        crc ^= *data++;
        for (unsigned k = 0; k < 8; k++)
            crc = crc & 0x80 ? (crc << 1) ^ 0x1d : crc << 1;
    }
    crc &= 0xff;
    return crc;
}