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

Daniel M. OP #5873472
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.
Antwort Zitieren Bearbeiten Thread verschieben Thread sperren Anmeldepflicht aktivieren Anpinnen Thread löschen Thread mit anderem zusammenführen Beitrag melden
Stefan Gast #5874280
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
GEKU Gast #5874310
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
}
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Daniel M. OP #5874417
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
Antwort Zitieren Bearbeiten Löschen Beitrag melden
DPA Gast #5874431
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.
Antwort Zitieren Bearbeiten Löschen Beitrag melden
Thread beobachten

Antwort schreiben

Bitte melde dich an, um einen Beitrag zu schreiben.

Bestehender Account

oder

Mit Google-Account einloggen

Noch kein Account?

Die Registrierung ist kostenlos und dauert nur eine Minute.

Jetzt registrieren