user_name
user_name

Reputation: 183

How to use table based CRC-16 code?

I was hoping someone might be able to shed some light on why my CRC-16 implementation does not seem to run correctly on Visual Studio? I got the algorithm from a manual for a specific device, and wrote the int main() myself. There are always 'type' errors when I try to pass the arguments to the function, so I suspect there is something wrong with the format? This is the info that came with the code:

Upvotes: 7

Views: 46490

Answers (6)

kubota880
kubota880

Reputation: 1

that table lists the powers of the polynomial, to avoid errors in the table calculate the powers during the calculation, and make the polynomial an entry as well as the initial value. Use Dartpad to simulate it: https://dartpad.dev/?null_safety=true

void main() {
  final int polynomial = 0x1189;
  final int initialValue = 0xFFFF;
  String crc16(String expression, int polynomial, int initialValue) {
    int checkSum = initialValue;
    for (int i = 0; i < expression.length; i++) {
      checkSum ^= (expression.codeUnitAt(i) << 8);
      for (int j = 0; j < 8; j++) {
        if (((checkSum <<= 1) & 0x10000) == 0x10000) checkSum ^= polynomial;
        checkSum &= 0xFFFF;
      }
    }
    return checkSum.toRadixString(16).toUpperCase();
  }
  print(crc16('123456789', polynomial, initialValue));
}

To be compliant to CRC16 CCITT you should use polynomial=0x1021 and initial value = 0xFFFF.

https://www.gatevidyalay.com/cyclic-redundancy-check-crc-error-detection/ has a good explanation about CRC.

Upvotes: 0

Ekrem Polat
Ekrem Polat

Reputation: 1

I have used the same CRC checks and in your code you need to change only the following line: crc = (crc >> 8) ^ crctable[(crc^(*c++))&0xFF];

Upvotes: 0

J Ashley
J Ashley

Reputation: 826

The table you are using appears to be incorrectly generated. The first sixteen entries are correct, but it diverges after that. I don't think you will have much luck decoding CCITT CRC-16 with it.

See CRC for cross platform applications for an example of the correctly-generated table.

Upvotes: 0

fvu
fvu

Reputation: 32953

On this line

crc = (crc << 8) ^ crctable[((crc >> 8) ^ *c++)];

the result of ((crc >> 8) ^ *c++) can become > 255, and cause an access violation. Just make sure the result is always 0.255 by masking the index into crctable

crc = (crc << 8) ^ crctable[((crc >> 8) ^ *c++) & 0x00FF];
// but you will need to clean up the result as its upper 16 bits
// are not guaranteed to be all 0
return crc & 0xffff;

or better, the resulting crc value as it ensures that crc will never contain a value > 0x0000ffff

crc = ( (crc << 8) ^ crctable[((crc >> 8) ^ *c++)] ) & 0xffff;

and you'll be all set. The base of the issue is that the original code seems to be 16 bits code (where int was 16 bits), and you are using a 32 bits compiler.

Upvotes: 1

pat
pat

Reputation: 12749

All cleaned up and ready to go:

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

static const uint16_t crctable[256] =
{
    0x0000, 0x1189, 0x2312, 0x329B, 0x4624, 0x57AD, 0x6536, 0x74BF,
    0x8C48, 0x9DC1, 0xAF5A, 0xBED3, 0xCA6C, 0xDBE5, 0xE97E, 0xF8F7,
    0x0919, 0x1890, 0x2A0B, 0x3B82, 0x4F3D, 0x5EB4, 0x6C2F, 0x7DA6,
    0x8551, 0x94D8, 0xA643, 0xB7CA, 0xC375, 0xD2FC, 0xE067, 0xF1EE,
    0x1232, 0x03BB, 0x3120, 0x20A9, 0x5416, 0x459F, 0x7704, 0x668D,
    0x9E7A, 0x8FF3, 0xBD68, 0xACE1, 0xD85E, 0xC9D7, 0xFB4C, 0xEAC5,
    0x1B2B, 0x0AA2, 0x3839, 0x29B0, 0x5D0F, 0x4C86, 0x7E1D, 0x6F94,
    0x9763, 0x86EA, 0xB471, 0xA5F8, 0xD147, 0xC0CE, 0xF255, 0xE3DC,
    0x2464, 0x35ED, 0x0776, 0x16FF, 0x6240, 0x73C9, 0x4152, 0x50DB,
    0xA82C, 0xB9A5, 0x8B3E, 0x9AB7, 0xEE08, 0xFF81, 0xCD1A, 0xDC93,
    0x2D7D, 0x3CF4, 0x0E6F, 0x1FE6, 0x6B59, 0x7AD0, 0x484B, 0x59C2,
    0xA135, 0xB0BC, 0x8227, 0x93AE, 0xE711, 0xF698, 0xC403, 0xD58A,
    0x3656, 0x27DF, 0x1544, 0x04CD, 0x7072, 0x61FB, 0x5360, 0x42E9,
    0xBA1E, 0xAB97, 0x990C, 0x8885, 0xFC3A, 0xEDB3, 0xDF28, 0xCEA1,
    0x3F4F, 0x2EC6, 0x1C5D, 0x0DD4, 0x796B, 0x68E2, 0x5A79, 0x4BF0,
    0xB307, 0xA28E, 0x9015, 0x819C, 0xF523, 0xE4AA, 0xD631, 0xC7B8,
    0x48C8, 0x5941, 0x6BDA, 0x7A53, 0x0EEC, 0x1F65, 0x2DFE, 0x3C77,
    0xC480, 0xD509, 0xE792, 0xF61B, 0x82A4, 0x932D, 0xA1B6, 0xB03F,
    0x41D1, 0x5058, 0x62C3, 0x734A, 0x07F5, 0x167C, 0x24E7, 0x356E,
    0xCD99, 0xDC10, 0xEE8B, 0xFF02, 0x8BBD, 0x9A34, 0xA8AF, 0xB926,
    0x5AFA, 0x4B73, 0x79E8, 0x6861, 0x1CDE, 0x0D57, 0x3FCC, 0x2E45,
    0xD6B2, 0xC73B, 0xF5A0, 0xE429, 0x9096, 0x811F, 0xB384, 0xA20D,
    0x53E3, 0x426A, 0x70F1, 0x6178, 0x15C7, 0x044E, 0x36D5, 0x275C,
    0xDFAB, 0xCE22, 0xFCB9, 0xED30, 0x998F, 0x8806, 0xBA9D, 0xAB14,
    0x6CAC, 0x7D25, 0x4FBE, 0x5E37, 0x2A88, 0x3B01, 0x099A, 0x1813,
    0xE0E4, 0xF16D, 0xC3F6, 0xD27F, 0xA6C0, 0xB749, 0x85D2, 0x945B,
    0x65B5, 0x743C, 0x46A7, 0x572E, 0x2391, 0x3218, 0x0083, 0x110A,
    0xE9FD, 0xF874, 0xCAEF, 0xDB66, 0xAFD9, 0xBE50, 0x8CCB, 0x9D42,
    0x7E9E, 0x6F17, 0x5D8C, 0x4C05, 0x38BA, 0x2933, 0x1BA8, 0x0A21,
    0xF2D6, 0xE35F, 0xD1C4, 0xC04D, 0xB4F2, 0xA57B, 0x97E0, 0x8669,
    0x7787, 0x660E, 0x5495, 0x451C, 0x31A3, 0x202A, 0x12B1, 0x0338,
    0xFBCF, 0xEA46, 0xD8DD, 0xC954, 0xBDEB, 0xAC62, 0x9EF9, 0x8F70
};

uint16_t // Returns Calculated CRC value
CalculateCRC16(
    uint16_t crc,      // Seed for CRC calculation
    const void *c_ptr, // Pointer to byte array to perform CRC on
    size_t len)        // Number of bytes to CRC
{
    const uint8_t *c = c_ptr;

    while (len--)
        crc = (crc << 8) ^ crctable[((crc >> 8) ^ *c++)];

    return crc;
}

int main()
{
    printf("%04x\n", CalculateCRC16(0xFFFF, "123456789", 9));

    return 0;
}

Upvotes: 6

Metalartis
Metalartis

Reputation: 115

there is not a computer near me now. Just a try:

crc = (crc << 8) ^ crctable[(unsigned char)(crc >> 8) ^ *c++];

Upvotes: 1

Related Questions