Forum: Mikrocontroller und Digitale Elektronik CRC-16-Berechnung mit Lookup-Tabelle: zwei Varianten, beide gültig?


Announcement: there is an English version of this forum on EmbDev.net. Posts you create there will be displayed on Mikrocontroller.net and EmbDev.net.
von Daniel M. (daniel_m781)


Lesenswert?

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:
1
void crcAlgA(char* buf, unsigned short* crc) {
2
    unsigned short i;
3
    
4
    for(i = 0; i < strlen(buf); i++) {
5
        *crc = ((*crc) << 8) ^ crctab[((*crc) >> 8) ^ buf[i]];
6
    }
7
}

Variante B:
1
void crcAlgB(char* buf, unsigned short* crc) {
2
    unsigned short i;
3
    
4
    for(i = 0; i < strlen(buf); i++) {
5
        *crc = ((*crc) << 8) ^ crctab[((*crc) >> 8)] ^ buf[i];
6
    }
7
}

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

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.

: Verschoben durch Moderator
von Frank L. (Firma: Flk Consulting UG) (flk)


Lesenswert?

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

von Stefan (Gast)


Lesenswert?

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

von Stefan (Gast)


Lesenswert?

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

von GEKU (Gast)


Lesenswert?

1
// Most significant bit first (big-endian)
2
// x^16+x^12+x^5+1 = (1) 0001 0000 0010 0001 = 0x1021
3
4
unsigned short crc_be(unsigned short rem,char *strInput, int len)
5
{
6
    int n=16;
7
    int i;
8
    int j;
9
10
    for (i=0;i<len;i++)
11
    {
12
        rem=rem^(strInput[i]<<(n-8));   // n = 16 in this example
13
14
        for (j=1;j<=8;j++) // Assuming 8 bits per byte
15
        {
16
            if (rem&0x8000) // if leftmost (most significant) bit is set
17
            {
18
                rem=(rem<<1)^0x1021;
19
            }
20
            else
21
            {
22
                rem=rem<<1;
23
            }
24
            rem=rem&0xffff;      // Trim remainder to 16 bits
25
        }
26
    }
27
    // A popular variant complements rem here
28
    return rem;
29
}
30
31
// Least significant bit first (little-endian)
32
// x^16+x^12+x^5+1 = 1000 0100 0000 1000 (1) = 0x8408
33
34
unsigned short crc_le(unsigned short rem,char *strInput,int len)
35
{
36
    int n=16;
37
    int i;
38
    int j;
39
40
    for (i=0;i<len;i++)
41
    {
42
        rem=rem^strInput[i];
43
44
        for (j=1;j<=8;j++) // Assuming 8 bits per byte
45
        {
46
            if (rem&0x0001)   // if rightmost (least significant) bit is set
47
            {
48
                rem=(rem>>1)^0x8408;
49
            }
50
            else
51
            {
52
                rem=rem>>1;
53
            }
54
        }
55
    }
56
    // A popular variant complements rem here
57
    return rem;
58
}

von Megatroll (Gast)


Lesenswert?

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.

von Stef (Gast)


Lesenswert?

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

von GEKU (Gast)


Lesenswert?

Megatroll schrieb:
> nicht in einem loop verwenden

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

von Daniel M. (daniel_m781)


Lesenswert?

@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

von DPA (Gast)


Lesenswert?

Ich würd das so anpassen:
1
void crcAlgC(char* buf, unsigned short* crc) {
2
  unsigned short tmp = *crc;
3
  for(unsigned char* it=(unsigned char*)buf, c=*it; c; c=*++it)
4
    tmp = (tmp << 8) ^ crctab[(tmp >> 8) ^ c];
5
  *crc = tmp;
6
}

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

von Georg G. (df2au)


Lesenswert?

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

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

von Carl D. (jcw2)


Lesenswert?

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?

: Bearbeitet durch User
von Veit D. (devil-elec)


Lesenswert?

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.

Antwort schreiben

Die Angabe einer E-Mail-Adresse ist freiwillig. Wenn Sie automatisch per E-Mail über Antworten auf Ihren Beitrag informiert werden möchten, melden Sie sich bitte an.

Wichtige Regeln - erst lesen, dann posten!

  • Groß- und Kleinschreibung verwenden
  • Längeren Sourcecode nicht im Text einfügen, sondern als Dateianhang

Formatierung (mehr Informationen...)

  • [c]C-Code[/c]
  • [code]Code in anderen Sprachen, ASCII-Zeichnungen[/code]
  • [math]Formel in LaTeX-Syntax[/math]
  • [[Titel]] - Link zu Artikel
  • Verweis auf anderen Beitrag einfügen: Rechtsklick auf Beitragstitel,
    "Adresse kopieren", und in den Text einfügen




Bild automatisch verkleinern, falls nötig
Bitte das JPG-Format nur für Fotos und Scans verwenden!
Zeichnungen und Screenshots im PNG- oder
GIF-Format hochladen. Siehe Bildformate.
Hinweis: der ursprüngliche Beitrag ist mehr als 6 Monate alt.
Bitte hier nur auf die ursprüngliche Frage antworten,
für neue Fragen einen neuen Beitrag erstellen.

Mit dem Abschicken bestätigst du, die Nutzungsbedingungen anzuerkennen.