mikrocontroller.net

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.
Autor: Daniel M. (daniel_m781)
Datum:

Bewertung
0 lesenswert
nicht 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:
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.

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

Bewertung
0 lesenswert
nicht 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

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: Stefan (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: GEKU (Gast)
Datum:

Bewertung
1 lesenswert
nicht lesenswert
// 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;
}


Autor: Megatroll (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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.

Autor: Stef (Gast)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: GEKU (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
Megatroll schrieb:
> nicht in einem loop verwenden

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

Autor: Daniel M. (daniel_m781)
Datum:

Bewertung
0 lesenswert
nicht 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

Autor: DPA (Gast)
Datum:

Bewertung
0 lesenswert
nicht lesenswert
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.

Autor: Georg G. (df2au)
Datum:

Bewertung
-1 lesenswert
nicht 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.

Autor: Carl D. (jcw2)
Datum:

Bewertung
0 lesenswert
nicht 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
Autor: Veit D. (devil-elec)
Datum:

Bewertung
0 lesenswert
nicht 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]
  • [avrasm]AVR-Assembler-Code[/avrasm]
  • [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.

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