CRC4 INTERLAKEN and ITU lookup table generation

Question

I try to geneate CRC4 lookup tables in C++ for the known CRC algorithms CRC-4/INTERLAKEN and CRC-4/ITU. The CRC definitions are as follows:

width=4 poly=0x3 init=0xf refin=false refout=false xorout=0xf check=0xb residue=0x2 name="CRC-4/INTERLAKEN"
width=4 poly=0x3 init=0x0 refin=true refout=true xorout=0x0 check=0x7 residue=0x0 name="CRC-4/G-704"

I've started adapting the code found from the answer here to generate lookup table to compare with tables found in the answer found here. If the bit order does not matter for this code, besides polynomial which is the same what else I need to consider? How different would the codes for INTERLAKEN and ITU algorithms be?

The code:

#include <iomanip>
#include <iostream>

void make_crc_table(unsigned long crcTable[])
{
    unsigned long POLYNOMIAL = 0x3;
    unsigned long remainder;
    unsigned char b = 0;
    do
    {
        remainder = b;
        for (unsigned long bit = 8; bit > 0; --bit)
        {
            if (remainder & 1)
                remainder = (remainder >> 1) ^ POLYNOMIAL;
            else
                remainder = (remainder >> 1);
        }
        crcTable[(size_t)b] = remainder;
    } while (0 != ++b);
}

int main()
{
    unsigned long crcTable[256];
    make_crc_table(crcTable);
    // Print the CRC table
    for (size_t i = 0; i < 256; i++)
    {
        std::cout << "0x";
        std::cout << std::setfill('0') << std::setw(2) << std::hex << crcTable[i];
        if (i % 16 == 15)
            std::cout << "," << std::endl;
        else
            std::cout << ", ";
    }

    return 0;
}

The output:

0x00, 0x02, 0x03, 0x01, 0x01, 0x03, 0x02, 0x00, 0x02, 0x00, 0x01, 0x03, 0x03, 0x01, 0x00, 0x02,
0x03, 0x01, 0x00, 0x02, 0x02, 0x00, 0x01, 0x03, 0x01, 0x03, 0x02, 0x00, 0x00, 0x02, 0x03, 0x01,
0x01, 0x03, 0x02, 0x00, 0x00, 0x02, 0x03, 0x01, 0x03, 0x01, 0x00, 0x02, 0x02, 0x00, 0x01, 0x03,
0x02, 0x00, 0x01, 0x03, 0x03, 0x01, 0x00, 0x02, 0x00, 0x02, 0x03, 0x01, 0x01, 0x03, 0x02, 0x00,
0x02, 0x00, 0x01, 0x03, 0x03, 0x01, 0x00, 0x02, 0x00, 0x02, 0x03, 0x01, 0x01, 0x03, 0x02, 0x00,
0x01, 0x03, 0x02, 0x00, 0x00, 0x02, 0x03, 0x01, 0x03, 0x01, 0x00, 0x02, 0x02, 0x00, 0x01, 0x03,
0x03, 0x01, 0x00, 0x02, 0x02, 0x00, 0x01, 0x03, 0x01, 0x03, 0x02, 0x00, 0x00, 0x02, 0x03, 0x01,
0x00, 0x02, 0x03, 0x01, 0x01, 0x03, 0x02, 0x00, 0x02, 0x00, 0x01, 0x03, 0x03, 0x01, 0x00, 0x02,
0x03, 0x01, 0x00, 0x02, 0x02, 0x00, 0x01, 0x03, 0x01, 0x03, 0x02, 0x00, 0x00, 0x02, 0x03, 0x01,
0x00, 0x02, 0x03, 0x01, 0x01, 0x03, 0x02, 0x00, 0x02, 0x00, 0x01, 0x03, 0x03, 0x01, 0x00, 0x02,
0x02, 0x00, 0x01, 0x03, 0x03, 0x01, 0x00, 0x02, 0x00, 0x02, 0x03, 0x01, 0x01, 0x03, 0x02, 0x00,
0x01, 0x03, 0x02, 0x00, 0x00, 0x02, 0x03, 0x01, 0x03, 0x01, 0x00, 0x02, 0x02, 0x00, 0x01, 0x03,
0x01, 0x03, 0x02, 0x00, 0x00, 0x02, 0x03, 0x01, 0x03, 0x01, 0x00, 0x02, 0x02, 0x00, 0x01, 0x03,
0x02, 0x00, 0x01, 0x03, 0x03, 0x01, 0x00, 0x02, 0x00, 0x02, 0x03, 0x01, 0x01, 0x03, 0x02, 0x00,
0x00, 0x02, 0x03, 0x01, 0x01, 0x03, 0x02, 0x00, 0x02, 0x00, 0x01, 0x03, 0x03, 0x01, 0x00, 0x02,
0x03, 0x01, 0x00, 0x02, 0x02, 0x00, 0x01, 0x03, 0x01, 0x03, 0x02, 0x00, 0x00, 0x02, 0x03, 0x01,

Original question ends here.

Update after rcgldr's answer:

#include <iostream>
#include <bitset>
#include <iomanip>

void make_crc_table(unsigned int crcTable[])
{
    unsigned char POLYNOMIAL = 0xc;
    unsigned char remainder;
    unsigned char b = 0;
    do
    {
        remainder = b;
        for (int bit = 8; bit > 0; --bit)
        {
            if (remainder & 0x80)
                remainder = (remainder << 1) ^ POLYNOMIAL;
            else
                remainder = (remainder << 1);
        }
        crcTable[(size_t)b] = remainder;
    } while (0 != ++b);
}

int main()
{
    unsigned int crcTable[256];
    make_crc_table(crcTable);

    for (size_t i = 0; i < 256; i++)
    {
        std::cout << "0x";
        std::cout << std::setfill('0') << std::setw(2) << std::hex << (crcTable[i]);
        if (i % 16 == 15)
            std::cout << "," << std::endl;
        else
            std::cout << ", ";
    }

    return 0;
}

Output of the code:

0x00, 0x0c, 0x18, 0x14, 0x30, 0x3c, 0x28, 0x24, 0x60, 0x6c, 0x78, 0x74, 0x50, 0x5c, 0x48, 0x44,
0xc0, 0xcc, 0xd8, 0xd4, 0xf0, 0xfc, 0xe8, 0xe4, 0xa0, 0xac, 0xb8, 0xb4, 0x90, 0x9c, 0x88, 0x84,
0x8c, 0x80, 0x94, 0x98, 0xbc, 0xb0, 0xa4, 0xa8, 0xec, 0xe0, 0xf4, 0xf8, 0xdc, 0xd0, 0xc4, 0xc8,
0x4c, 0x40, 0x54, 0x58, 0x7c, 0x70, 0x64, 0x68, 0x2c, 0x20, 0x34, 0x38, 0x1c, 0x10, 0x04, 0x08,
0x14, 0x18, 0x0c, 0x00, 0x24, 0x28, 0x3c, 0x30, 0x74, 0x78, 0x6c, 0x60, 0x44, 0x48, 0x5c, 0x50,
0xd4, 0xd8, 0xcc, 0xc0, 0xe4, 0xe8, 0xfc, 0xf0, 0xb4, 0xb8, 0xac, 0xa0, 0x84, 0x88, 0x9c, 0x90,
0x98, 0x94, 0x80, 0x8c, 0xa8, 0xa4, 0xb0, 0xbc, 0xf8, 0xf4, 0xe0, 0xec, 0xc8, 0xc4, 0xd0, 0xdc,
0x58, 0x54, 0x40, 0x4c, 0x68, 0x64, 0x70, 0x7c, 0x38, 0x34, 0x20, 0x2c, 0x08, 0x04, 0x10, 0x1c,
0x28, 0x24, 0x30, 0x3c, 0x18, 0x14, 0x00, 0x0c, 0x48, 0x44, 0x50, 0x5c, 0x78, 0x74, 0x60, 0x6c,
0xe8, 0xe4, 0xf0, 0xfc, 0xd8, 0xd4, 0xc0, 0xcc, 0x88, 0x84, 0x90, 0x9c, 0xb8, 0xb4, 0xa0, 0xac,
0xa4, 0xa8, 0xbc, 0xb0, 0x94, 0x98, 0x8c, 0x80, 0xc4, 0xc8, 0xdc, 0xd0, 0xf4, 0xf8, 0xec, 0xe0,
0x64, 0x68, 0x7c, 0x70, 0x54, 0x58, 0x4c, 0x40, 0x04, 0x08, 0x1c, 0x10, 0x34, 0x38, 0x2c, 0x20,
0x3c, 0x30, 0x24, 0x28, 0x0c, 0x00, 0x14, 0x18, 0x5c, 0x50, 0x44, 0x48, 0x6c, 0x60, 0x74, 0x78,
0xfc, 0xf0, 0xe4, 0xe8, 0xcc, 0xc0, 0xd4, 0xd8, 0x9c, 0x90, 0x84, 0x88, 0xac, 0xa0, 0xb4, 0xb8,
0xb0, 0xbc, 0xa8, 0xa4, 0x80, 0x8c, 0x98, 0x94, 0xd0, 0xdc, 0xc8, 0xc4, 0xe0, 0xec, 0xf8, 0xf4,
0x70, 0x7c, 0x68, 0x64, 0x40, 0x4c, 0x58, 0x54, 0x10, 0x1c, 0x08, 0x04, 0x20, 0x2c, 0x38, 0x34,

rcgldr · Accepted Answer · 2020-06-07T14:48:58.827

2

The bit order matters. The question's code is using reflected input and output. That means the polynomial should be bit reversed from 0x03 to 0x0c. To confirm this, table entry [0x80] should be 0x0c.

For the Interlaken table, the code should look like:

void make_crc_table(unsigned char crcTable[])
{
    unsigned char POLYNOMIAL = 0x30;
    unsigned char remainder;
    unsigned char b = 0;
    do
    {
        remainder = b;
        for (int bit = 8; bit > 0; --bit)
        {
            if (remainder & 0x80)
                remainder = (remainder << 1) ^ POLYNOMIAL;
            else
                remainder = (remainder << 1);
        }
        crcTable[(size_t)b] = remainder;
    } while (0 != ++b);
}

Note that the CRC will be in the upper 4 bits of a byte. When done, the code will need to return (crc>>4)^0x0f.

edited Jun 07 '20 at 14:48

answered Jun 04 '20 at 21:04

rcgldr

27,407
3
36
61

Thanks for an the answer @rcgldr. Unfortunately with my hobbyist programming skills I could not figure out how Mark Adler generated the CRC4 tables. Still studying though. – stardust Jun 06 '20 at 14:30
I have tried with `0x3` for Interlaken and `0xc` for ITU, so far the results does not match with the table from Mark Adler's answer. – stardust Jun 06 '20 at 22:20
1

@stardust - Mark Adler's interlaken table indexing assumes that a prior xorout = 0xf has been done to crc, and the table values for crc include an xorout = 0xf. For the initial call to his interlaken crc, use input parameter crc = 0x0 (not 0xf). – rcgldr Jun 07 '20 at 00:22
I have updated my question, added the code I am trying. – stardust Jun 07 '20 at 11:11
1

@stardust - In my answer, the example code is for Interlaken, but I had called it ITU. My asnwer is fixed now. For the question's first code, change `POLYNOMIAL = 0x3;` to `POLYNOMIAL = 0xC;`. For the question's second code, change `POLYNOMIAL = 0xc;` to `POLYNOMIAL = 0x30;` . – rcgldr Jun 07 '20 at 14:51

CRC4 INTERLAKEN and ITU lookup table generation

1 Answers1