python - Implementing a CRC algorithm

Question

I'm trying to implement a CRC algorithm as defined in some video interface standards:

• SMPTE296M-2001
• BT.1120-9:2017

The raw data is 10 bit words that are squashed into 8 bit bytes which I have no issues extracting and working with in numpy.

the CRC has polynomial:

CRC(X) = X^18 + X^5 + X^4 + 1

I believe this gives me the constant:

POLY = 0x40031

I've tried a few different implementations and nothing I generate matches my sample data. this implementation was inspired by this

MASK = 0x3FFFF
class MYCRC:
    crc_table = []
    def __init__(self):
        if not self.crc_table:
            for i in range(1024):
                k = i
                for j in range(10):
                    if k & 1:
                        k ^= POLY
                    k >>= 1
                self.crc_table.append(k)

    def calc(self, crc, data):
        crc ^= MASK
        for d in data:
            crc = (crc >> 10) ^ self.crc_table[(crc & 0x3FF) ^ d]
        return crc ^ MASK

then there is this implementation I pulled from somewhere (not sure where)

def crc_calc(crc, p):
    crc = MASK & ~crc
    for i in range(len(p)):
        crc = (crc ^ p[i]) # & BIG_MASK
        for j in range(10):
            crc = ((crc >> 1) ^ (POLY & -(crc & 1))) # & BIG_MASK
    return MASK & ~crc

I also looked at using this library which has support for using custom polynomials, but it appears to be built to work with 8 bit data, not the 10 bit data I have.

I'm not sure how best to share test data as I only have whole frames which if exported as a numpy file is ~5MB. I'm also unclear as the the range of data I'm supposed to feed to the CRC calculation. I think from reading it, it should be from the first active sample on one line, up to the line count of the line after, then the checksum calculated over that range. This makes the most sense from a hardware perspective, but the standard doesn't read that clearly to me.

edit: pastebin of 10 lines worth of test data, this includes the embedded checksum. within a line of data, samples 0-7 are the EAV marker, 8-11 are the line number,12-16 are the two checksums. the data is two interleaved streams of video data (luma channel and CbCr channel). the standards state the checksums are run from the first active sample to the end of the line data, which I interpret to mean that it runs from sample 740 of one line to sample 11 of the next line.

As per section 5 of SMPTE292M the data is 10 bit data which cannot go below 0x3 or above 0x3FC. as per table 4 the result of the CRC should be 18 bits which get split and embedded into the stream as two words (with one bit filled in with the not of another bit) Note that there is one checksum for each channel of data, these two checksums are at 12-16 on each line

edit 2 some longer test data that straddles the jump from blanking data to active frame data

question from:https://stackoverflow.com/questions/65922806/implementing-a-crc-algorithm

Answer 1

The CRC calculation must be done reflected. (Clue in note on Table 9: "NOTE – CRC0 is the MSB of error detection codes.")

This C routine checks the CRCs in your example correctly:

// Update the CRC-18 crc with the low ten bits of word.
// Polynomial = 1000000000000110001
// Reflected (dropping x^18) = 10 0011 0000 0000 0000 = 0x23000
unsigned crc18(unsigned crc, unsigned word) {
    crc ^= word & 0x3ff;
    for (int k = 0; k < 10; k++)
        crc = crc & 1 ? (crc >> 1) ^ 0x23000 : crc >> 1;
    return crc;
}

Indeed the span of the check is from the start of the active line through the line numbers, up to just before the two CRCs in the stream. That calculation matches those two CRCs. Each CRC is calculated on alternating words from the stream. The CRCs are initialized to zero.