CRC-16-Berechnung mit Lookup-Tabelle: zwei Varianten, beide gültig?

[Daniel M. (daniel_m781)]

Hallo,

in existierendem Code finde ich zwei Varianten zur Prüfsummenberechnung 
nach CCITT und frage mich, ob beide tatsächlich einen gültigen CRC-Wert 
berechnen.

Startwert ist 0x0, verwendetes Polynom ist 0x1021:
Variante A:

void crcAlgA(char* buf, unsigned short* crc) {
    unsigned short i;
    
    for(i = 0; i < strlen(buf); i++) {
        *crc = ((*crc) << 8) ^ crctab[((*crc) >> 8) ^ buf[i]];
    }
}

Variante B:

void crcAlgB(char* buf, unsigned short* crc) {
    unsigned short i;
    
    for(i = 0; i < strlen(buf); i++) {
        *crc = ((*crc) << 8) ^ crctab[((*crc) >> 8)] ^ buf[i];
    }
}

Beide Variante verwenden die gleiche Lookup-Tabelle:

const unsigned short crctab[256] = {
    0x0000, 0x1021, 0x2042, 0x3063, 0x4084, 0x50A5, 0x60C6, 0x70E7,
    0x8108, 0x9129, 0xA14A, 0xB16B, 0xC18C, 0xD1AD, 0xE1CE, 0xF1EF,
    0x1231, 0x0210, 0x3273, 0x2252, 0x52B5, 0x4294, 0x72F7, 0x62D6,
    0x9339, 0x8318, 0xB37B, 0xA35A, 0xD3BD, 0xC39C, 0xF3FF, 0xE3DE,
    0x2462, 0x3443, 0x0420, 0x1401, 0x64E6, 0x74C7, 0x44A4, 0x5485,
    0xA56A, 0xB54B, 0x8528, 0x9509, 0xE5EE, 0xF5CF, 0xC5AC, 0xD58D,
    0x3653, 0x2672, 0x1611, 0x0630, 0x76D7, 0x66F6, 0x5695, 0x46B4,
    0xB75B, 0xA77A, 0x9719, 0x8738, 0xF7DF, 0xE7FE, 0xD79D, 0xC7BC,
    0x48C4, 0x58E5, 0x6886, 0x78A7, 0x0840, 0x1861, 0x2802, 0x3823,
    0xC9CC, 0xD9ED, 0xE98E, 0xF9AF, 0x8948, 0x9969, 0xA90A, 0xB92B,
    0x5AF5, 0x4AD4, 0x7AB7, 0x6A96, 0x1A71, 0x0A50, 0x3A33, 0x2A12,
    0xDBFD, 0xCBDC, 0xFBBF, 0xEB9E, 0x9B79, 0x8B58, 0xBB3B, 0xAB1A,
    0x6CA6, 0x7C87, 0x4CE4, 0x5CC5, 0x2C22, 0x3C03, 0x0C60, 0x1C41,
    0xEDAE, 0xFD8F, 0xCDEC, 0xDDCD, 0xAD2A, 0xBD0B, 0x8D68, 0x9D49,
    0x7E97, 0x6EB6, 0x5ED5, 0x4EF4, 0x3E13, 0x2E32, 0x1E51, 0x0E70,
    0xFF9F, 0xEFBE, 0xDFDD, 0xCFFC, 0xBF1B, 0xAF3A, 0x9F59, 0x8F78,
    0x9188, 0x81A9, 0xB1CA, 0xA1EB, 0xD10C, 0xC12D, 0xF14E, 0xE16F,
    0x1080, 0x00A1, 0x30C2, 0x20E3, 0x5004, 0x4025, 0x7046, 0x6067,
    0x83B9, 0x9398, 0xA3FB, 0xB3DA, 0xC33D, 0xD31C, 0xE37F, 0xF35E,
    0x02B1, 0x1290, 0x22F3, 0x32D2, 0x4235, 0x5214, 0x6277, 0x7256,
    0xB5EA, 0xA5CB, 0x95A8, 0x8589, 0xF56E, 0xE54F, 0xD52C, 0xC50D,
    0x34E2, 0x24C3, 0x14A0, 0x0481, 0x7466, 0x6447, 0x5424, 0x4405,
    0xA7DB, 0xB7FA, 0x8799, 0x97B8, 0xE75F, 0xF77E, 0xC71D, 0xD73C,
    0x26D3, 0x36F2, 0x0691, 0x16B0, 0x6657, 0x7676, 0x4615, 0x5634,
    0xD94C, 0xC96D, 0xF90E, 0xE92F, 0x99C8, 0x89E9, 0xB98A, 0xA9AB,
    0x5844, 0x4865, 0x7806, 0x6827, 0x18C0, 0x08E1, 0x3882, 0x28A3,
    0xCB7D, 0xDB5C, 0xEB3F, 0xFB1E, 0x8BF9, 0x9BD8, 0xABBB, 0xBB9A,
    0x4A75, 0x5A54, 0x6A37, 0x7A16, 0x0AF1, 0x1AD0, 0x2AB3, 0x3A92,
    0xFD2E, 0xED0F, 0xDD6C, 0xCD4D, 0xBDAA, 0xAD8B, 0x9DE8, 0x8DC9,
    0x7C26, 0x6C07, 0x5C64, 0x4C45, 0x3CA2, 0x2C83, 0x1CE0, 0x0CC1,
    0xEF1F, 0xFF3E, 0xCF5D, 0xDF7C, 0xAF9B, 0xBFBA, 0x8FD9, 0x9FF8,
    0x6E17, 0x7E36, 0x4E55, 0x5E74, 0x2E93, 0x3EB2, 0x0ED1, 0x1EF0
};

Algorithmus A erzeugt einen Wert gemäß CRC-16/XMODEM, soweit OK. Was 
aber Algorithmus B erzeugt, kann ich einfach nicht sinnvoll beurteilen. 
Hängt man jedoch zwei Nullbytes an die Nachricht an, entspricht das 
Ergebnis von B dem von A.

Ist Variante B überhaupt ein CRC-Algorithmus? Falls ja: welcher 
Algorithmus ist das? Ich muss die Prüfsummenberechnung für extern 
spezifizieren und kann dabei nicht auf Quelltext ausweichen, sondern 
muss allgemein formulieren.

Beim Versuch der Identifikation, um welchen Algorithmus es sich handeln 
könnte, habe ich diese Seiten sehr hilfreich gefunden:
https://crccalc.com/?crc=AB01&method=crc16&datatype=ascii
http://www.sunshine2k.de/coding/javascript/crc/crc_js.html

Vielen Dank schon mal und viele Grüße,
D.

[Frank L. (Firma: Flk Consulting UG) (flk)]

Hallo,
Ich würde sagen, B ist fehlerhaft. Das XOR mit buf[i] wirkt auf das 
Ergebnis des Zugriffes auf die Tabelle. Während in A der Platz im Array 
über das XOR buf[1] ermittelt wird.

Gruß
Frank

[Stefan (Gast)]

Hallo,

richtig ist Version A,

aber die Version ist ebenfals grenzwertig
da in deinem Array buf wegen dem strlen(buf)
kein Zeichen 0x00 vorkommen darf!

Gruss

[Stefan (Gast)]

Hallo,

vielleicht noch eine Anmerkung zu

Daniel M. schrieb:
> Ist Variante B überhaupt ein CRC-Algorithmus? Falls ja: welcher
> Algorithmus ist das?

eine Prüfsumme (sprich CRC) kann jeder berechnen wie er lustig ist. Sie 
muss nur eindeutig reproduzierbar sein.

Nur der internationalen Gepflogenheit der fortgesetzten Polynomdivision 
mit genormten Polynom entspricht Version B nicht!

Gruss

[GEKU (Gast)]

// Most significant bit first (big-endian)
// x^16+x^12+x^5+1 = (1) 0001 0000 0010 0001 = 0x1021

unsigned short crc_be(unsigned short rem,char *strInput, int len)
{
    int n=16;
    int i;
    int j;

    for (i=0;i<len;i++)
    {
        rem=rem^(strInput[i]<<(n-8));   // n = 16 in this example

        for (j=1;j<=8;j++) // Assuming 8 bits per byte
        {
            if (rem&0x8000) // if leftmost (most significant) bit is set
            {
                rem=(rem<<1)^0x1021;
            }
            else
            {
                rem=rem<<1;
            }
            rem=rem&0xffff;      // Trim remainder to 16 bits
        }
    }
    // A popular variant complements rem here
    return rem;
}

// Least significant bit first (little-endian)
// x^16+x^12+x^5+1 = 1000 0100 0000 1000 (1) = 0x8408

unsigned short crc_le(unsigned short rem,char *strInput,int len)
{
    int n=16;
    int i;
    int j;

    for (i=0;i<len;i++)
    {
        rem=rem^strInput[i];

        for (j=1;j<=8;j++) // Assuming 8 bits per byte
        {
            if (rem&0x0001)   // if rightmost (least significant) bit is set
            {
                rem=(rem>>1)^0x8408;
            }
            else
            {
                rem=rem>>1;
            }
        }
    }
    // A popular variant complements rem here
    return rem;
}

[Megatroll (Gast)]

Es ist aber schon klar, dass man strlen() nicht in einem loop verwenden 
sollte ? Falls der Compiler doof genung ist rechnet er das jedes mal 
neu, heisst er zaehlt die character.

[Stef (Gast)]

Hallo,

Megatroll schrieb:
> Falls der Compiler doof genung ist rechnet er das jedes mal
> neu, heisst er zaehlt die character.

strlen() ermittelt immer die Länge eines Strings bzw. zählt die Anzahl 
seiner Zeichen bis zu 0x00

[GEKU (Gast)]

Megatroll schrieb:
> nicht in einem loop verwenden

außer man verändert die Länge der Zeichenkette der Programmschleife.

[Daniel M. (daniel_m781)]

@Megatroll: ich nehme an, das bezieht sich auf meine zwei vorgestellten 
Varianten? Mir persönlich war das tatsächlich nicht klar, da ich C-Code 
gerade so gut verstehe, um ihn halbwegs lesen zu können -- ich komme 
eher aus der Python-Ecke ;) In jedem Fall Danke für den Hinweis!

Letztlich geht es mir bei der Frage aber gar nicht um Effizienz, sondern 
darum ob Variante B überhaupt eine gültige Implementierung darstellt.

Variante A kann ich einfach spezifizieren: Startwert 0x0, Poly 0x1021, 
kein Bit-Reversal für Input/Result, Result XOR 0x0. Variante B ist hier 
deutlich unorthodoxer. Ich finde keine solche Entsprechung auf 
einschlägigen Seiten:

http://www.sunshine2k.de/coding/javascript/crc/crc_js.html
http://www.zorc.breitbandkatze.de/crc.html

[DPA (Gast)]

Ich würd das so anpassen:

void crcAlgC(char* buf, unsigned short* crc) {
  unsigned short tmp = *crc;
  for(unsigned char* it=(unsigned char*)buf, c=*it; c; c=*++it)
    tmp = (tmp << 8) ^ crctab[(tmp >> 8) ^ c];
  *crc = tmp;
}

Weniger dereferenzierungen, kein ständiges strlen, und das "unsigned 
char" damit c nicht plöztlich mal negativ ist.

[Georg G. (df2au)]

DPA schrieb:
> Ich würd das so anpassen:

und sobald im Datensatz eine Null ist, knallt es.
Die Länge sollte explizit übergeben werden.

[Carl D. (jcw2)]

Georg G. schrieb:
> DPA schrieb:
>> Ich würd das so anpassen:
>
> und sobald im Datensatz eine Null ist, knallt es.
> Die Länge sollte explizit übergeben werden.

char* (in der Schnittstelle) und c!=0 (implizit in der Loop) spricht 
dafür, daß C-Strings behandelt werden sollen. Was soll da knallen?

[Veit D. (devil-elec)]

Hallo,

für CRC16 gibts eine Standardlib
http://www.nongnu.org/avr-libc/user-manual/group__util__crc.html

Es gibt auch Online Rechner mit denen du deine Ergebnisse vergleichen 
kannst.