How to implement CRC-10 algorithm

Question

I'm trying to implement a 10-bit CRC with a polynomial of 0x633. I've scoured through countless pages but not much is written on CRC-10.

I've written some sample code that seems to calculate it just fine. I can run some test data through to get a CRC then run the data + CRC back through to get 0, which is expect. The problem is that we're testing it against this calculator and getting incongruent results: http://www.ghsi.de/pages/subpages/Online%20CRC%20Calculation/indexDetails.php?Polynom=11000110011&Message=1f+ff+30+04+05+34+a7. This includes the poly and test data. The result from this calculator is "0x10e" while mine is "0x3b1".

Here is the code, modified from https://cs.fit.edu/code/svn/cse2410f13team7/wireshark/wsutil/crc10.c:

#include <stdio.h>
#include <stdint.h>

uint16_t GetCRC10(uint16_t crc10, const uint8_t *data_blk_ptr, int data_blk_size);

static const uint16_t byte_crc10_table[256] = {
    0x0000, 0x0233, 0x0255, 0x0066, 0x0299, 0x00aa, 0x00cc, 0x02ff,
    0x0301, 0x0132, 0x0154, 0x0367, 0x0198, 0x03ab, 0x03cd, 0x01fe,
    0x0031, 0x0202, 0x0264, 0x0057, 0x02a8, 0x009b, 0x00fd, 0x02ce,
    0x0330, 0x0103, 0x0165, 0x0356, 0x01a9, 0x039a, 0x03fc, 0x01cf,
    0x0062, 0x0251, 0x0237, 0x0004, 0x02fb, 0x00c8, 0x00ae, 0x029d,
    0x0363, 0x0150, 0x0136, 0x0305, 0x01fa, 0x03c9, 0x03af, 0x019c,
    0x0053, 0x0260, 0x0206, 0x0035, 0x02ca, 0x00f9, 0x009f, 0x02ac,
    0x0352, 0x0161, 0x0107, 0x0334, 0x01cb, 0x03f8, 0x039e, 0x01ad,
    0x00c4, 0x02f7, 0x0291, 0x00a2, 0x025d, 0x006e, 0x0008, 0x023b,
    0x03c5, 0x01f6, 0x0190, 0x03a3, 0x015c, 0x036f, 0x0309, 0x013a,
    0x00f5, 0x02c6, 0x02a0, 0x0093, 0x026c, 0x005f, 0x0039, 0x020a,
    0x03f4, 0x01c7, 0x01a1, 0x0392, 0x016d, 0x035e, 0x0338, 0x010b,
    0x00a6, 0x0295, 0x02f3, 0x00c0, 0x023f, 0x000c, 0x006a, 0x0259,
    0x03a7, 0x0194, 0x01f2, 0x03c1, 0x013e, 0x030d, 0x036b, 0x0158,
    0x0097, 0x02a4, 0x02c2, 0x00f1, 0x020e, 0x003d, 0x005b, 0x0268,
    0x0396, 0x01a5, 0x01c3, 0x03f0, 0x010f, 0x033c, 0x035a, 0x0169,
    0x0188, 0x03bb, 0x03dd, 0x01ee, 0x0311, 0x0122, 0x0144, 0x0377,
    0x0289, 0x00ba, 0x00dc, 0x02ef, 0x0010, 0x0223, 0x0245, 0x0076,
    0x01b9, 0x038a, 0x03ec, 0x01df, 0x0320, 0x0113, 0x0175, 0x0346,
    0x02b8, 0x008b, 0x00ed, 0x02de, 0x0021, 0x0212, 0x0274, 0x0047,
    0x01ea, 0x03d9, 0x03bf, 0x018c, 0x0373, 0x0140, 0x0126, 0x0315,
    0x02eb, 0x00d8, 0x00be, 0x028d, 0x0072, 0x0241, 0x0227, 0x0014,
    0x01db, 0x03e8, 0x038e, 0x01bd, 0x0342, 0x0171, 0x0117, 0x0324,
    0x02da, 0x00e9, 0x008f, 0x02bc, 0x0043, 0x0270, 0x0216, 0x0025,
    0x014c, 0x037f, 0x0319, 0x012a, 0x03d5, 0x01e6, 0x0180, 0x03b3,
    0x024d, 0x007e, 0x0018, 0x022b, 0x00d4, 0x02e7, 0x0281, 0x00b2,
    0x017d, 0x034e, 0x0328, 0x011b, 0x03e4, 0x01d7, 0x01b1, 0x0382,
    0x027c, 0x004f, 0x0029, 0x021a, 0x00e5, 0x02d6, 0x02b0, 0x0083,
    0x012e, 0x031d, 0x037b, 0x0148, 0x03b7, 0x0184, 0x01e2, 0x03d1,
    0x022f, 0x001c, 0x007a, 0x0249, 0x00b6, 0x0285, 0x02e3, 0x00d0,
    0x011f, 0x032c, 0x034a, 0x0179, 0x0386, 0x01b5, 0x01d3, 0x03e0,
    0x021e, 0x002d, 0x004b, 0x0278, 0x0087, 0x02b4, 0x02d2, 0x00e1
};

/* update the data block's CRC-10 remainder one byte at a time */
uint16_t GetCRC10(uint16_t crc10, const uint8_t *data_blk_ptr, int data_blk_size)
{
    register int i;
    uint16_t crc10_accum = 0;

    for (i = 0;  i < data_blk_size; i++) {
        crc10_accum = ((crc10_accum << 8) & 0x3ff)
        ^ byte_crc10_table[( crc10_accum >> 2) & 0xff]
        ^ *data_blk_ptr++;
    }
    crc10_accum = ((crc10_accum << 8) & 0x3ff)
        ^ byte_crc10_table[( crc10_accum >> 2) & 0xff]
        ^ (crc10>>2);
    crc10_accum = ((crc10_accum << 8) & 0x3ff)
        ^ byte_crc10_table[( crc10_accum >> 2) & 0xff]
        ^ ((crc10<<6) & 0xFF);

    return crc10_accum;
}

#define TEST_DATA_SIZE    9

void main()
{
  uint8_t test_input_data[TEST_DATA_SIZE] = {0x1f, 0xff, 0x30, 0x4, 0x5, 0x34, 0xa7, 0x0, 0x0};
  uint16_t crc;
  uint16_t crc_final;

  GenerateCRC10Table();
  crc = GetCRC10(0, test_input_data, TEST_DATA_SIZE-2);
  test_input_data[TEST_DATA_SIZE-2] ^= crc >> 8;
  test_input_data[TEST_DATA_SIZE-1] ^= crc & 0xFF;

  printf("%x\n", crc); // Error here. This crc doesn't match with the calculator.

  crc_final = GetCRC10(0, test_input_data, TEST_DATA_SIZE);

  if (crc_final == 0)
  {
    printf("Success");
  }
}

This is the function used to produce the lookup table:

#define POLYNOMIAL 0x633

static uint16_t byte_crc10_table[256];

void gen_byte_crc10_table(void)
/* generate the table of CRC-10 remainders for all possible bytes */
{
    register int i, j;
    register unsigned short crc10_accum;

    for ( i = 0;  i < 256;  i++ )
    {
        crc10_accum = ((unsigned short) i << 2);
        for ( j = 0;  j < 8;  j++ )
        {
            if ((crc10_accum <<= 1) & 0x400) crc10_accum ^= POLYNOMIAL;
        }
        byte_crc10_table[i] = crc10_accum;
    }
    return;
}

I've tried this with the 0x233 normal polynomial form as well.

Is this even possible? In essence, I'm tying to bitwise operations on a complete array of bytes. I suspect the problem is that the calculator does it bit-by-bit and mine is byte-by-byte. Since the poly is 10 bits wide, it doesn't work cleanly with uint8s. I'd really appreciate some feedback. Thanks.

Does it make sense that the calculator CRC and my CRC are different because of the 10 bit polynomial and 8 bit data difference?

Answer 1

The code in the question is implementing CRC-10/ATM, which includes 6 padded 0 bits after the bytes of data and before the 10 bit CRC. For the example data in the question:

1f ff 30 04 05 34 a7

It should be getting 0x3b1, which is what the code you posted generates.

Alternate implementation, also results in 0x3b1 for the example case you posted, and both the questions code and this alternate implementation match the examples from CRC-10/ATM :

typedef unsigned char   uint8_t;
typedef unsigned short uint16_t;

#define CRC10 (0x233<<6)

static uint16_t crctbl[256];

void gentbl(void)
{
uint16_t crc;
uint16_t c;
uint16_t i;
    for(c = 0; c < 0x100; c++){
        crc = c << 8;
        for(i = 0; i < 8; i++)
            /* assumes twos complement */
            crc = (crc<<1)^((0-(crc>>15))&CRC10);
        crctbl[c] = crc;
    }
}

uint16_t crc10(uint8_t * bfr, int len)
{
uint16_t crc = 0x0000;
    while(len--){
        /* shifting 6 bits instead of 8 will leave crc cycled -2 bits when done */
        crc ^= ((uint16_t)(*bfr++))<<6;     /* xor byte<<6 into crc */
        crc  = (crc<<8)^crctbl[(crc>>8)];   /* cycle crc */
    }
    /* At this point, crc is cycled -2 bits, meaning that */
    /* 2 bit of data have not been cycled yet,  so cycle */
    /* 8 bits to cycle the 2 bits of data and 6 padding bits of 0 */
    crc = (crc<<8)^crctbl[(crc>>8)];        /* cycle crc +8 bits */
    return(crc>>6);                         /* return 10 bit crc */
}

Test code:

#include <stdio.h>

/* test messages including 10 bit CRC */
static uint8_t tst1[] = 
   {0x0A,0x0B,0x0C,0x0D,0x0E,0x0F,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0xf6};

static uint8_t tst2[] =
   {0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x11,0x00,0x00,0x00,0x00,0x00,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x01,0x6B};

static uint8_t tst3[] =
   {0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
    0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
    0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x03,0x0F};

static uint8_t tst4[] =
   {0x12,0x34,0x56,0x78,0x90,0x12,0x34,0x56,0x78,0x90,0x12,0x34,0x56,0x78,0x90,0x12,
    0x34,0x56,0x78,0x90,0x12,0x34,0x56,0x78,0x90,0x12,0x34,0x56,0x78,0x90,0x12,0x34,
    0x56,0x78,0x90,0x12,0x34,0x56,0x78,0x90,0x12,0x34,0x56,0x78,0x90,0x12,0x02,0xED};

static uint8_t tst5[] =
   {0x10,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,
    0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,
    0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x03,0xB9};

static uint8_t tst6[] =
   {0x18,0x01,0x00,0x00,0x00,0x00,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,
    0xFF,0xFF,0xFF,0xFF,0xFF,0xFF,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,0x00,
    0x00,0x00,0x00,0x00,0x00,0x00,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x6A,0x00,0x4A};

static uint8_t* ptst[6] = {tst1, tst2, tst3, tst4, tst5, tst6};

/* length of msgs including crc */
#define LEN (48)

int main(void)
{
uint16_t crc;
int i;
    gentbl();
    for(i = 0; i < (sizeof(ptst)/sizeof(ptst[0])); i++){
        crc = crc10(ptst[i], LEN-2);            /* generate a 10 bit CRC */
        if((crc>>8)   != ptst[i][LEN-2] ||      /* verify it matches test CRC */ 
           (crc&0xff) != ptst[i][LEN-1])
            break;
        crc = crc10(ptst[i], LEN);              /* verify CRC == 0 */
        if(0 != crc)
            break;
    }
    if(i == 6)
        printf("passed\n");
    else
        printf("error\n");
    return 0;
}

Answer 2

A CRC is not defined only by a length and a polynomial. There is also the bit ordering of the incoming bytes, the bit-ordering of the application of the polynomial, the bit as well as byte ordering of the result, the initialization of the CRC, and the final exclusive-or.

That online calculator makes some arbitrary choices in the CRC it calculates, as it itself notes at the top of the page: "Be careful: there are several ways to realize a CRC. They differ (at least) in the way which bit is shifted in first and also in the initialization of the flipflops." It chooses no bit reflections, a zero initialization, and a zero final exclusive-or.

The resulting CRC, with the polynomial you provided, 0x233, actually has a name and an application. It is a CRC-10/ATM (see link). Here is a simple bit-wise implementation:

unsigned crc10atm_bit(unsigned crc, void const *mem, size_t len) {
    unsigned char const *data = mem;
    if (data == NULL)
        return 0;
    while (len--) {
        crc ^= (unsigned)(*data++) << 2;
        for (unsigned k = 0; k < 8; k++)
            crc = crc & 0x200 ? (crc << 1) ^ 0x233 : crc << 1;
    }
    crc &= 0x3ff;
    return crc;
}

The routine uses the convention that the initial value for the CRC is returned when a NULL pointer is passed.

Here is a faster byte-wise implementation using a pre-computed table:

static unsigned short const table_byte[] = {
    0x000, 0x233, 0x255, 0x066, 0x299, 0x0aa, 0x0cc, 0x2ff, 0x301, 0x132, 0x154,
    0x367, 0x198, 0x3ab, 0x3cd, 0x1fe, 0x031, 0x202, 0x264, 0x057, 0x2a8, 0x09b,
    0x0fd, 0x2ce, 0x330, 0x103, 0x165, 0x356, 0x1a9, 0x39a, 0x3fc, 0x1cf, 0x062,
    0x251, 0x237, 0x004, 0x2fb, 0x0c8, 0x0ae, 0x29d, 0x363, 0x150, 0x136, 0x305,
    0x1fa, 0x3c9, 0x3af, 0x19c, 0x053, 0x260, 0x206, 0x035, 0x2ca, 0x0f9, 0x09f,
    0x2ac, 0x352, 0x161, 0x107, 0x334, 0x1cb, 0x3f8, 0x39e, 0x1ad, 0x0c4, 0x2f7,
    0x291, 0x0a2, 0x25d, 0x06e, 0x008, 0x23b, 0x3c5, 0x1f6, 0x190, 0x3a3, 0x15c,
    0x36f, 0x309, 0x13a, 0x0f5, 0x2c6, 0x2a0, 0x093, 0x26c, 0x05f, 0x039, 0x20a,
    0x3f4, 0x1c7, 0x1a1, 0x392, 0x16d, 0x35e, 0x338, 0x10b, 0x0a6, 0x295, 0x2f3,
    0x0c0, 0x23f, 0x00c, 0x06a, 0x259, 0x3a7, 0x194, 0x1f2, 0x3c1, 0x13e, 0x30d,
    0x36b, 0x158, 0x097, 0x2a4, 0x2c2, 0x0f1, 0x20e, 0x03d, 0x05b, 0x268, 0x396,
    0x1a5, 0x1c3, 0x3f0, 0x10f, 0x33c, 0x35a, 0x169, 0x188, 0x3bb, 0x3dd, 0x1ee,
    0x311, 0x122, 0x144, 0x377, 0x289, 0x0ba, 0x0dc, 0x2ef, 0x010, 0x223, 0x245,
    0x076, 0x1b9, 0x38a, 0x3ec, 0x1df, 0x320, 0x113, 0x175, 0x346, 0x2b8, 0x08b,
    0x0ed, 0x2de, 0x021, 0x212, 0x274, 0x047, 0x1ea, 0x3d9, 0x3bf, 0x18c, 0x373,
    0x140, 0x126, 0x315, 0x2eb, 0x0d8, 0x0be, 0x28d, 0x072, 0x241, 0x227, 0x014,
    0x1db, 0x3e8, 0x38e, 0x1bd, 0x342, 0x171, 0x117, 0x324, 0x2da, 0x0e9, 0x08f,
    0x2bc, 0x043, 0x270, 0x216, 0x025, 0x14c, 0x37f, 0x319, 0x12a, 0x3d5, 0x1e6,
    0x180, 0x3b3, 0x24d, 0x07e, 0x018, 0x22b, 0x0d4, 0x2e7, 0x281, 0x0b2, 0x17d,
    0x34e, 0x328, 0x11b, 0x3e4, 0x1d7, 0x1b1, 0x382, 0x27c, 0x04f, 0x029, 0x21a,
    0x0e5, 0x2d6, 0x2b0, 0x083, 0x12e, 0x31d, 0x37b, 0x148, 0x3b7, 0x184, 0x1e2,
    0x3d1, 0x22f, 0x01c, 0x07a, 0x249, 0x0b6, 0x285, 0x2e3, 0x0d0, 0x11f, 0x32c,
    0x34a, 0x179, 0x386, 0x1b5, 0x1d3, 0x3e0, 0x21e, 0x02d, 0x04b, 0x278, 0x087,
    0x2b4, 0x2d2, 0x0e1
};

unsigned crc10atm_byte(unsigned crc, void const *mem, size_t len) {
    unsigned char const *data = mem;
    if (data == NULL)
        return 0;
    while (len--)
        crc = (crc << 8) ^
              table_byte[((crc >> 2) ^ *data++) & 0xff];
    crc &= 0x3ff;
    return crc;
}

You might prefer different choices, e.g. an initial value of 0x3ff and a final exclusive-or of that same value. That would avoid strings of any number of zeros having a CRC of zero. Also some shifts can be avoided if reflections are used.