6

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:

  • CRC Name : CRC-16
  • Width : 16 Bits
  • Polynomial Used : 1189 (hex)
  • Seed Value : FFFF (hex)
  • Reflected Input/Output : No
  • Exclusive OR Output : No

  • Test CRC for string "123456789" : 5502 (hex)

    #include <stdio.h>

unsigned int 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
};
unsigned int // Returns Calculated CRC value
CalculateCRC16(
unsigned int crc_seed, // Seed for CRC calculation
void *c_ptr, // Pointer to byte array to perform CRC on
unsigned int len) // Number of bytes to CRC
{
unsigned char *c = c_ptr;
unsigned int crc = crc_seed;
while (len--){
crc = (crc << 8) ^ crctable[((crc >> 8) ^ *c++)];
printf("%d", crc);
}
return (crc);
}

int main(){

    printf("%d", CalculateCRC16(0xFFFF, "123456789", 2));

 return 0;  
}
fvu
  • 32,488
  • 6
  • 61
  • 79
user_name
  • 173
  • 1
  • 2
  • 8
  • Can you show us what errors (or warnings) you are getting? – fvu Mar 16 '14 at 01:56
  • Sure, when I try and call it like I did in the main in this example, it does execute but then breaks straight away. From debugging I found that it breaks as soon as it exits the while loop...but I don't understand why. – user_name Mar 16 '14 at 02:00
  • How can you debug it if there are errors? What do you mean, "breaks". Please be SPECIFIC with your question and provide complete details. – OldProgrammer Mar 16 '14 at 02:05
  • indent, indent, indent... – pat Mar 16 '14 at 02:05
  • your `crc` variable is an `unsigned int`, so when you left shift it, you are keeping more than 16 bits, which will cause grief when you try to index your 256-element lookup table. Change it to a `uint16_t` (`#include `), and you should be good to go. – pat Mar 16 '14 at 02:07
  • Ok sorry, when I tried other ways of calling the function there were errors. In this specific way, it just broke. Do you know what might be causing that? Breaks as in the execution crashes. Thanks pat, I'll try it now! – user_name Mar 16 '14 at 02:08
  • In fact, your lookup table is probably using twice as much memory as it should. Change it to an array of `uint16_t` as well. – pat Mar 16 '14 at 02:11

6 Answers6

6

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;
}
pat
  • 12,587
  • 1
  • 23
  • 52
  • Thank you Pat, this is a massive improvement. However, for the test string, it does not seem to give the result 5502. I'm getting 7A2C. Do you think that the type changes may have affected the algorithm? – user_name Mar 16 '14 at 02:26
  • How did you compute the expected value? Note that you are only taking the CRC of the first 2 bytes of the test string. – pat Mar 16 '14 at 02:27
  • Change the length from 2 to 9, and you get the value you were expecting – pat Mar 16 '14 at 02:28
1

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.

fvu
  • 32,488
  • 6
  • 61
  • 79
  • Ahh that makes sense. Did 16 bits code just use to be commonplace then, and now it's been superseded by modern 32 bits? – user_name Mar 16 '14 at 11:44
  • Yes, for most of the DOS era all DOS code was 16 bits (the first 386 capable PC processor was the 386), just towards the end there were "DOS extenders" that allowed 32 bits code to run under DOS. All pre-Warp OS/2 versions were also 16 bits, as as Windows pre 95 (or maybe 3.11). Before the massive inroads of eg ARM architecture 32 bits embedded processors many higher end embedded processors/controllers were also 16 bits, but they are still relatively common. – fvu Mar 16 '14 at 12:14
  • Also this: @pat's solution is preferable for modern compilers, if you still need to compile the same codebase with an older compiler you'll notice that it may not know about uint16_t. Can be solved with either a typedef, or masking, as in my proposed code. – fvu Mar 16 '14 at 12:21
  • Your assumption is wrong. The value of `crc` is assigned in the function. At no time a value more than 16 bit is assigned. It is before calculation never larger then 0xFFFF. `0xFFFF>>8` = `0x00FF`. `*c` deferences a byte pointer and is 8 bits wide. The XOR Operation doesn't carry any bit to other bit positions. So the maximum value of `(( crc >> 8) ^ *c)` is **0xFF**. – harper Feb 19 '15 at 05:32
  • @harper. The culprit is crc << 8, as 0xffff << 8 - always assuming a 32 bits variable - is 0x00ffff00. However, although the suggested fix does work, it still requires the returned value to be & 0xffff to mask off the upper bits. I'll rework my answer with that note and a better approach. Note that as stated in a previous comment, using the guaranteed 16 bits wide `uint16_t` is still the easiest solution. – fvu Feb 19 '15 at 19:13
1

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

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

Metalartis
  • 115
  • 4
  • since 0 ^ 0 equals 0, the casting is not needed. I think crc should be an "unsigned short int". pat is right, uint16_t is the best choice. – Metalartis Mar 16 '14 at 02:26
  • Update: Since 0 ^ 0 equals 0, if crc was 16bits, the casting will not be needed. For the error, crc seems more than 16bits, so I think you may use "unsigned short int" to define crc. And @pat is right, uint16_t is the best choice. – Metalartis Mar 16 '14 at 02:46
0

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.

Community
  • 1
  • 1
J Ashley
  • 786
  • 1
  • 5
  • 9
0

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];

Ekrem Polat
  • 1
0

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.

kubota880
  • 1
  • 2