Generate crc16 lookup table from existing crc function

Question

I'm working in a project where there is this function that computes a CRC16 checksum.

uint16_t x_crc(uint16_t CrcVal, uint8_t DataIn) {

    CrcVal = (unsigned char) (CrcVal >> 8) | (CrcVal << 8);
    CrcVal ^= DataIn;
    CrcVal ^= (unsigned char) (CrcVal & 0xff) >> 4;
    CrcVal ^= (CrcVal << 8) << 4;
    CrcVal ^= ((CrcVal & 0xff) << 4) << 1;

    return CrcVal &0xFFFF;
}

And it is used like this:

uint8_t x[]={1,2,3,4,5,6,7,8,9,0};
        
uint16_t CrcResult=0;
    
for (size_t i = 0; i<10; i++) {
    CrcResult = x_crc(CrcResult, *(x + i));
}    
    
printf("\n\n\nCRC1 = 0x%04X\n",CrcResult);

Due to performance issues I need to convert to a lookup table. How can I do that, using the above function to generate the entries?

Thanks.

Answer 1

Due to the shifting implementation, it is not clear that this is a left shifting CRC with polynomial 0x11021. Example code including a 256 by 16 bit table driven one. I'm thinking that compiler optimization will inline z_crc, which is the table one. If not, then change the function to take 3 parameters, crcvalue, buffer pointer, # of bytes.

#include <stdio.h>

typedef unsigned short uint16_t;
typedef unsigned char  uint8_t;

uint16_t crctbl[256];

uint16_t x_crc(uint16_t CrcVal, uint8_t DataIn) {
    CrcVal = (unsigned char)(CrcVal>>8)|(CrcVal<<8);  /* rotate left 8 bits */
                                                /* crc ^=      (byte*0x10000)>>16 */
    CrcVal ^= DataIn;                           /* crc ^=       (byte*0x0001)     */
    CrcVal ^= (unsigned char)(CrcVal&0xff)>>4;  /* crc ^= ((crc&0xf0)*0x1000)>>16 */
    CrcVal ^= (CrcVal<<8)<<4;                   /* crc ^= ((crc&0x0f)*0x1000)     */
    CrcVal ^= ((CrcVal&0xff)<<4)<<1;            /* crc ^= ((crc&0xff)*0x0020)     */
    return CrcVal;                              /*                    0x1021      */
}

uint16_t y_crc(uint16_t CrcVal, uint8_t DataIn) {
    CrcVal ^= ((uint16_t)DataIn) << 8;
    for (uint16_t i = 0; i < 8; i++)
        CrcVal = (CrcVal&0x8000)?(CrcVal<<1)^0x1021:(CrcVal << 1);
    return CrcVal;
}

void inittbl()
{
    for (uint16_t j = 0; j < 256; j++)
        crctbl[j] = x_crc(0, (uint8_t)j);
}

uint16_t z_crc(uint16_t CrcVal, uint8_t DataIn) {
    CrcVal = crctbl[(CrcVal>>8)^DataIn]^(CrcVal<<8);
    return CrcVal;
}

int main()
{
uint16_t crcx = 0;
uint16_t crcy = 0;
uint16_t crcz = 0;
uint8_t x[]={1,2,3,4,5,6,7,8,9,0};
    inittbl();
    for(size_t i = 0; i<10; i++)
        crcx = x_crc(crcx, *(x + i));
    for(size_t i = 0; i<10; i++)
        crcy = y_crc(crcy, *(x + i));
    for(size_t i = 0; i<10; i++)
        crcz = z_crc(crcz, *(x + i));
    if (crcx == crcy && crcx == crcz)
        printf("match\n");
    return 0;
}