How to reverse a table-based CRC16?

Question

For my project I need to reverse a table-based CRC16 because I have to change some data without changing the CRC.

My problem is to reverse the look up table.

I found some other solutions to reverse the look up table, but not for my CRC table.

#define SIZE_OF_CRC_TABLE 256u
static const uint16_t crc_polynom = 0x1021;

void Compute_CRCTables(uint16_t *CRCTable_forward, uint16_t *CRCTable_reverse) {
    uint16_t result_forward, result_reverse;
    int i, j;

    for (i = 0; i < SIZE_OF_CRC_TABLE; i++) {
        result_forward = (uint16_t) i << 8;
        result_reverse = i;

        for (j = 0; j < 8; j++) {
            /* ---- forward ---- */
            if (result_forward & 0x8000) {
                result_forward = (result_forward <<= 1) ^ crc_polynom;
            }
            else {
                result_forward = result_forward <<= 1;
            }

            /* ---- reverse --- */
            if ((result_reverse & 0x1) != 0) {
                result_reverse = ((result_reverse ^ crc_polynom) >> 1) | 1;
            }
            else {
                result_reverse = result_reverse >>= 1;
            }
        }
        CRCTable_forward[i] = result_forward;
        CRCTable_reverse[i] = result_reverse;
    }
}

CRC table:

0x   0u, 0x1021u, 0x2042u, 0x3063u, 0x4084u, 0x50A5u, 0x60C6u, 0x70E7u,
0x8108u, 0x9129u, 0xA14Au, 0xB16Bu, 0xC18Cu, 0xD1ADu, 0xE1CEu, 0xF1EFu,
0x1231u, 0x 210u, 0x3273u, 0x2252u, 0x52B5u, 0x4294u, 0x72F7u, 0x62D6u,
0x9339u, 0x8318u, 0xB37Bu, 0xA35Au, 0xD3BDu, 0xC39Cu, 0xF3FFu, 0xE3DEu,
0x2462u, 0x3443u, 0x 420u, 0x1401u, 0x64E6u, 0x74C7u, 0x44A4u, 0x5485u,
0xA56Au, 0xB54Bu, 0x8528u, 0x9509u, 0xE5EEu, 0xF5CFu, 0xC5ACu, 0xD58Du,
0x3653u, 0x2672u, 0x1611u, 0x 630u, 0x76D7u, 0x66F6u, 0x5695u, 0x46B4u,
0xB75Bu, 0xA77Au, 0x9719u, 0x8738u, 0xF7DFu, 0xE7FEu, 0xD79Du, 0xC7BCu,
0x48C4u, 0x58E5u, 0x6886u, 0x78A7u, 0x 840u, 0x1861u, 0x2802u, 0x3823u,
0xC9CCu, 0xD9EDu, 0xE98Eu, 0xF9AFu, 0x8948u, 0x9969u, 0xA90Au, 0xB92Bu,
0x5AF5u, 0x4AD4u, 0x7AB7u, 0x6A96u, 0x1A71u, 0x A50u, 0x3A33u, 0x2A12u,
0xDBFDu, 0xCBDCu, 0xFBBFu, 0xEB9Eu, 0x9B79u, 0x8B58u, 0xBB3Bu, 0xAB1Au,
0x6CA6u, 0x7C87u, 0x4CE4u, 0x5CC5u, 0x2C22u, 0x3C03u, 0x C60u, 0x1C41u,
0xEDAEu, 0xFD8Fu, 0xCDECu, 0xDDCDu, 0xAD2Au, 0xBD0Bu, 0x8D68u, 0x9D49u,
0x7E97u, 0x6EB6u, 0x5ED5u, 0x4EF4u, 0x3E13u, 0x2E32u, 0x1E51u, 0x E70u,
0xFF9Fu, 0xEFBEu, 0xDFDDu, 0xCFFCu, 0xBF1Bu, 0xAF3Au, 0x9F59u, 0x8F78u,
0x9188u, 0x81A9u, 0xB1CAu, 0xA1EBu, 0xD10Cu, 0xC12Du, 0xF14Eu, 0xE16Fu,
0x1080u, 0x  A1u, 0x30C2u, 0x20E3u, 0x5004u, 0x4025u, 0x7046u, 0x6067u,
0x83B9u, 0x9398u, 0xA3FBu, 0xB3DAu, 0xC33Du, 0xD31Cu, 0xE37Fu, 0xF35Eu,
0x 2B1u, 0x1290u, 0x22F3u, 0x32D2u, 0x4235u, 0x5214u, 0x6277u, 0x7256u,
0xB5EAu, 0xA5CBu, 0x95A8u, 0x8589u, 0xF56Eu, 0xE54Fu, 0xD52Cu, 0xC50Du,
0x34E2u, 0x24C3u, 0x14A0u, 0x 481u, 0x7466u, 0x6447u, 0x5424u, 0x4405u,
0xA7DBu, 0xB7FAu, 0x8799u, 0x97B8u, 0xE75Fu, 0xF77Eu, 0xC71Du, 0xD73Cu,
0x26D3u, 0x36F2u, 0x 691u, 0x16B0u, 0x6657u, 0x7676u, 0x4615u, 0x5634u,
0xD94Cu, 0xC96Du, 0xF90Eu, 0xE92Fu, 0x99C8u, 0x89E9u, 0xB98Au, 0xA9ABu,
0x5844u, 0x4865u, 0x7806u, 0x6827u, 0x18C0u, 0x 8E1u, 0x3882u, 0x28A3u,
0xCB7Du, 0xDB5Cu, 0xEB3Fu, 0xFB1Eu, 0x8BF9u, 0x9BD8u, 0xABBBu, 0xBB9Au,
0x4A75u, 0x5A54u, 0x6A37u, 0x7A16u, 0x AF1u, 0x1AD0u, 0x2AB3u, 0x3A92u,
0xFD2Eu, 0xED0Fu, 0xDD6Cu, 0xCD4Du, 0xBDAAu, 0xAD8Bu, 0x9DE8u, 0x8DC9u,
0x7C26u, 0x6C07u, 0x5C64u, 0x4C45u, 0x3CA2u, 0x2C83u, 0x1CE0u, 0x CC1u,
0xEF1Fu, 0xFF3Eu, 0xCF5Du, 0xDF7Cu, 0xAF9Bu, 0xBFBAu, 0x8FD9u, 0x9FF8u,
0x6E17u, 0x7E36u, 0x4E55u, 0x5E74u, 0x2E93u, 0x3EB2u, 0x ED1u, 0x1EF0u,

Reverse CRC table (wrong):

0x   0u, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F1Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x E1Du, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F1Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x C19u, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F1Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x E1Du, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F1Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x 811u, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F1Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x E1Du, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F1Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x C19u, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F1Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x E1Du, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F1Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,
0x F9Fu, 0x FEFu, 0x FFFu, 0x FEFu, 0x FDFu, 0x FEFu, 0x FFFu, 0x FEFu,

Answer 1

The poly needs to be reversed as well. This code avoids inner conditionals assuming two's complement math to generate 0x0000 or 0xffff as an and mask.

#define SIZE_OF_CRC_TABLE 256u
#define POLY_FWD 0x1021
#define POLY_RVS 0x8408

void Compute_CRCTables(uint16_t *CRCTable_forward, uint16_t *CRCTable_reverse) {
    uint16_t crc_fwd = 0;
    uint16_t crc_rvs = 0;
    int i, j;

    for (i = 0; i < SIZE_OF_CRC_TABLE; i++) {
        crc_fwd = ((uint16_t)i) << 8;
        crc_rvs = ((uint16_t)i) << 0;
        for (j = 0; j < 8; j++) {
            /* assumes two's complement math */
            crc_fwd = (crc_fwd << 1) ^ ((0 - (crc_fwd >> 15)) & POLY_FWD);
            crc_rvs = (crc_rvs >> 1) ^ ((0 - (crc_rvs &   1)) & POLY_RVS);
        }
        CRCTable_forward[i] = crc_fwd;
        CRCTable_reverse[i] = crc_rvs;
    }
}