CODEWITHSUNDEEP
calgorithmcrc
Silicomancer
Silicomancer

Reputation: 9156

CRC table algorithm in C, width limitation

I found an easy to use implementation of CRC algorithms here. It includes table based and bit-wise algorithms. The code seems to work fine but there is an important limitation of table based algorithms. This is the relevant code:

unsigned long reflect (unsigned long crc, int bitnum) {
    unsigned long i, j=1, crcout=0;

    for (i=(unsigned long)1<<(bitnum-1); i; i>>=1) {
        if (crc & i) crcout|=j;
        j<<= 1;
    }
    return (crcout);
}

void generate_crc_table() {
    // make CRC lookup table used by table algorithms

    int i, j;
    unsigned long bit, crc;

    for (i=0; i<256; i++) {
        crc=(unsigned long)i;
        if (refin) crc=reflect(crc, 8);
        crc<<= order-8;

        for (j=0; j<8; j++) {
            bit = crc & crchighbit;
            crc<<= 1;
            if (bit) crc^= polynom;
        }           

        if (refin) crc = reflect(crc, order);
        crc&= crcmask;
        crctab[i]= crc;
    }
}  

unsigned long crctablefast (unsigned char* p, unsigned long len) {

    // fast lookup table algorithm without augmented zero bytes, e.g. used in pkzip.
    // only usable with polynom orders of 8, 16, 24 or 32.

    unsigned long crc = crcinit_direct;

    if (refin) crc = reflect(crc, order);

    if (!refin) while (len--) crc = (crc << 8) ^ crctab[ ((crc >> (order-8)) & 0xff) ^ *p++];
    else while (len--) crc = (crc >> 8) ^ crctab[ (crc & 0xff) ^ *p++];

    if (refout^refin) crc = reflect(crc, order);
    crc^= crcxor;
    crc&= crcmask;

    return(crc);
}

Please note code comments for table functions say:

only usable with polynom orders of 8, 16, 24 or 32.

Are table based algorithms generally limited to widths that are multiples of eight (especially table algorithms that use 16 and 32 bit tables)?

Is it possible to implement a table based CRC algorithm that accepts any CRC widths (not only multiples of 8)? How?

Upvotes: 0

Views: 1364

Answers (1)

Mark Adler
Mark Adler

Reputation: 112189

Yes, you can implement table-based CRCs for any width polynomial. See the output of crcany for example of table-based implementations for, for example, 5-bit, 13-bit, and 31-bit CRCs.

There is nothing tricky about this.

Upvotes: 1

Related Questions