Implementing a CRC algorithm

Question

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

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

@Ajay I haven't just looking now, but not sure what i should initialise it with for an 18 bit CRC and 10 bit data, the documents for that also suggest its for 8 bits/bytes and not arbitrary width integers — James Kent
You need to include some sample data and the expected CRC in your question. — Mark Adler
@rcgldr the data is 10 bit with the checksum embedded across two words, but the 18 bit checksum gets broken into two parts of 9 bits — James Kent
@rcgldr No. The actual YCbCr data in the lines are a full ten bits each. Only a very small number of words, specifically the line numbers and CRCs, make the 10th bit the complement of the 9th bit. The CRCs are calculated on all ten bits of all of the words, including the line numbers. — Mark Adler

Mark Adler Mark Adler · Accepted Answer · 2021-01-28T08:44:14

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.

Implementing a CRC algorithm

1 Answers