CRC - Byte-weise oder Wort-weise?

[Oliver B. (irq)]

Hallo,

ich wundere mich gerade darüber, ob es einen Unterschied macht, ob ich 
eine CRC-32 (Ethernet) Prüfsumme Byte für Byte berechne oder Wort für 
Wort (uint32_t).

Java bietet mit der Klasse CRC32 die Funktion

update(byte[] b)

der ich das Byte-Array übergeben kann, das ich z.B. aus einer Datei 
einlese.

Das Array übertrage ich nun an meinen µC und will sicherstellen, dass es 
auch exakt so angekommen ist. Dazu bietet der STM32 Cortex-M3 eine 
Hardwareeinheit. Die Library von STM hat auch schon eine Funktion 
vorbereitet, die da heißt:

uint32_t CRC_CalcBlockCRC(uint32_t pBuffer[], uint32_t BufferLength)

Im STM32-Manual heißt es: "CRC computation is done on the whole 32-bit 
data word, and not byte per byte"

Besteht da prinzipiell ein Unterschied im Ergebnis, wenn ich das 
übertragene Byte-Array einfach in ein uint32_t-Array caste und dann mit 
der Library-Funktion rechnen lasse? Muss ich evtl. die Byte-Order 
vertauschen? Was passiert, wenn ich die Funktion (bzw das 
CRC-Hardware-Datenregister) einfach nur mit Bytes füttere und den Rest 
mit Nullen auffülle?

Falls keiner spontan eine Antwort weiß, werde ich das einfach mal testen 
(oder mir doch zu Gemüte führen, wie CRC eigentlich funktioniert). Wäre 
aber klasse, wenn jemand spontan die Antwort wüsste.

Viele Grüße, Oliver.

[Oliver B. (irq)]

Ok, ich habe nun weitergesucht und hier ist mein aktueller Stand.

Um eine CRC32 in Software auf dem µC zu berechnen, die äquivalent zur 
Javas CRC32 ist, verwende ich nun folgenden Code:

/*
 * Software CRC32
 *
 * This function calculates the CRC32 over a given byte buffer the same way as
 * Javas CRC32 class does. Use this, if you use the Java CRC32 function.
 *
 * It uses a 256 lookup table, so its reasonable fast, but big in code.
 */
static uint32_t computeCRC32( uint32_t inCrc32, uint8_t byteBuf[], uint32_t bufLen )
{
    uint32_t crcTable[256] = { 0x00000000, 0x77073096, 0xEE0E612C, 0x990951BA,
      0x076DC419, 0x706AF48F, 0xE963A535, 0x9E6495A3, 0x0EDB8832,
      0x79DCB8A4, 0xE0D5E91E, 0x97D2D988, 0x09B64C2B, 0x7EB17CBD,
      0xE7B82D07, 0x90BF1D91, 0x1DB71064, 0x6AB020F2, 0xF3B97148,
      0x84BE41DE, 0x1ADAD47D, 0x6DDDE4EB, 0xF4D4B551, 0x83D385C7,
      0x136C9856, 0x646BA8C0, 0xFD62F97A, 0x8A65C9EC, 0x14015C4F,
      0x63066CD9, 0xFA0F3D63, 0x8D080DF5, 0x3B6E20C8, 0x4C69105E,
      0xD56041E4, 0xA2677172, 0x3C03E4D1, 0x4B04D447, 0xD20D85FD,
      0xA50AB56B, 0x35B5A8FA, 0x42B2986C, 0xDBBBC9D6, 0xACBCF940,
      0x32D86CE3, 0x45DF5C75, 0xDCD60DCF, 0xABD13D59, 0x26D930AC,
      0x51DE003A, 0xC8D75180, 0xBFD06116, 0x21B4F4B5, 0x56B3C423,
      0xCFBA9599, 0xB8BDA50F, 0x2802B89E, 0x5F058808, 0xC60CD9B2,
      0xB10BE924, 0x2F6F7C87, 0x58684C11, 0xC1611DAB, 0xB6662D3D,
      0x76DC4190, 0x01DB7106, 0x98D220BC, 0xEFD5102A, 0x71B18589,
      0x06B6B51F, 0x9FBFE4A5, 0xE8B8D433, 0x7807C9A2, 0x0F00F934,
      0x9609A88E, 0xE10E9818, 0x7F6A0DBB, 0x086D3D2D, 0x91646C97,
      0xE6635C01, 0x6B6B51F4, 0x1C6C6162, 0x856530D8, 0xF262004E,
      0x6C0695ED, 0x1B01A57B, 0x8208F4C1, 0xF50FC457, 0x65B0D9C6,
      0x12B7E950, 0x8BBEB8EA, 0xFCB9887C, 0x62DD1DDF, 0x15DA2D49,
      0x8CD37CF3, 0xFBD44C65, 0x4DB26158, 0x3AB551CE, 0xA3BC0074,
      0xD4BB30E2, 0x4ADFA541, 0x3DD895D7, 0xA4D1C46D, 0xD3D6F4FB,
      0x4369E96A, 0x346ED9FC, 0xAD678846, 0xDA60B8D0, 0x44042D73,
      0x33031DE5, 0xAA0A4C5F, 0xDD0D7CC9, 0x5005713C, 0x270241AA,
      0xBE0B1010, 0xC90C2086, 0x5768B525, 0x206F85B3, 0xB966D409,
      0xCE61E49F, 0x5EDEF90E, 0x29D9C998, 0xB0D09822, 0xC7D7A8B4,
      0x59B33D17, 0x2EB40D81, 0xB7BD5C3B, 0xC0BA6CAD, 0xEDB88320,
      0x9ABFB3B6, 0x03B6E20C, 0x74B1D29A, 0xEAD54739, 0x9DD277AF,
      0x04DB2615, 0x73DC1683, 0xE3630B12, 0x94643B84, 0x0D6D6A3E,
      0x7A6A5AA8, 0xE40ECF0B, 0x9309FF9D, 0x0A00AE27, 0x7D079EB1,
      0xF00F9344, 0x8708A3D2, 0x1E01F268, 0x6906C2FE, 0xF762575D,
      0x806567CB, 0x196C3671, 0x6E6B06E7, 0xFED41B76, 0x89D32BE0,
      0x10DA7A5A, 0x67DD4ACC, 0xF9B9DF6F, 0x8EBEEFF9, 0x17B7BE43,
      0x60B08ED5, 0xD6D6A3E8, 0xA1D1937E, 0x38D8C2C4, 0x4FDFF252,
      0xD1BB67F1, 0xA6BC5767, 0x3FB506DD, 0x48B2364B, 0xD80D2BDA,
      0xAF0A1B4C, 0x36034AF6, 0x41047A60, 0xDF60EFC3, 0xA867DF55,
      0x316E8EEF, 0x4669BE79, 0xCB61B38C, 0xBC66831A, 0x256FD2A0,
      0x5268E236, 0xCC0C7795, 0xBB0B4703, 0x220216B9, 0x5505262F,
      0xC5BA3BBE, 0xB2BD0B28, 0x2BB45A92, 0x5CB36A04, 0xC2D7FFA7,
      0xB5D0CF31, 0x2CD99E8B, 0x5BDEAE1D, 0x9B64C2B0, 0xEC63F226,
      0x756AA39C, 0x026D930A, 0x9C0906A9, 0xEB0E363F, 0x72076785,
      0x05005713, 0x95BF4A82, 0xE2B87A14, 0x7BB12BAE, 0x0CB61B38,
      0x92D28E9B, 0xE5D5BE0D, 0x7CDCEFB7, 0x0BDBDF21, 0x86D3D2D4,
      0xF1D4E242, 0x68DDB3F8, 0x1FDA836E, 0x81BE16CD, 0xF6B9265B,
      0x6FB077E1, 0x18B74777, 0x88085AE6, 0xFF0F6A70, 0x66063BCA,
      0x11010B5C, 0x8F659EFF, 0xF862AE69, 0x616BFFD3, 0x166CCF45,
      0xA00AE278, 0xD70DD2EE, 0x4E048354, 0x3903B3C2, 0xA7672661,
      0xD06016F7, 0x4969474D, 0x3E6E77DB, 0xAED16A4A, 0xD9D65ADC,
      0x40DF0B66, 0x37D83BF0, 0xA9BCAE53, 0xDEBB9EC5, 0x47B2CF7F,
      0x30B5FFE9, 0xBDBDF21C, 0xCABAC28A, 0x53B39330, 0x24B4A3A6,
      0xBAD03605, 0xCDD70693, 0x54DE5729, 0x23D967BF, 0xB3667A2E,
      0xC4614AB8, 0x5D681B02, 0x2A6F2B94, 0xB40BBE37, 0xC30C8EA1,
      0x5A05DF1B, 0x2D02EF8D };

    uint32_t crc32;
    uint32_t i;

    /** accumulate crc32 for buffer **/
    crc32 = inCrc32 ^ 0xFFFFFFFF;
    for (i=0; i < bufLen; i++) {
        crc32 = (crc32 >> 8) ^ crcTable[ (crc32 ^ byteBuf[i]) & 0xFF ];
    }
    return( crc32 ^ 0xFFFFFFFF );
}

Funktioniert prima, hat nur den Nachteil, dass es zusätzlich 1k im Flash 
belegt und auch nicht so schnell ist, wie die HW-CRC.

Zur Checksumme des STM32 habe ich noch gefunden, wie sie berechnet wird. 
Dazu folgender Link:

https://my.st.com/public/STe2ecommunities/mcu/Lists/ARM%20CortexM3%20STM32/Flat.aspx?RootFolder=https%3a%2f%2fmy.st.com%2fpublic%2fSTe2ecommunities%2fmcu%2fLists%2fARM%20CortexM3%20STM32%2fCRC%20calculation%20in%20software&FolderCTID=0x01200200770978C69A1141439FE559EB459D758000626BE2B829C32145B9EB5739142DC17E&currentviews=1761

Der Autor hat herausgefunden, wie die CRC-Berechnung beim STM32 
funktioniert. Das Wesentliche ist:

crc_model.cm_width = 32;            // 32-bit CRC
crc_model.cm_poly  = 0x04C11DB7;    // CRC-32 polynomial
crc_model.cm_init  = 0xFFFFFFFF;    // CRC initialized to 1's
crc_model.cm_refin = FALSE;         // CRC calculated MSB first
crc_model.cm_refot = FALSE;         // Final result is not bit-reversed
crc_model.cm_xorot = 0x00000000;    // Final result XOR'ed with

Man sieht schon die Unterschiede zur Java-CRC. Komischerweise ist das 
auch nirgends dokumentiert (habe zumindest keine Quelle gefunden), weiß 
auch nicht, was sich STM dabei denkt. Wie soll man denn CRCs überprüfen, 
wenn man nicht mal die Berechnungsgrundlage kennt?

Der Autor hat außerdem, mit Hilfe des "PAINLESS GUIDE TO CRC ERROR 
DETECTION ALGORITHMS", eine Implementierung in C geschrieben. Der Code 
ist unter obigem Link zu lesen, aber wer weiß wie lange das noch 
verfügbar ist, wo STM doch momentan ständig seine Websites 
verschlimmbesstert. Daher stelle ich es mal hier rein:

<BR>//////////////////////////////////////////////////////////////////////////
<BR>//
<BR>//  FUNCTION NAME :
<BR>//      CRC_CalcBlockCRC
<BR>//
<BR>//
<BR>//  FUNCTIONAL DESCRIPTION :
<BR>//      Calculate a CRC the same way as the STM32F10x hardware generator.
<BR>//
<BR>//
<BR>//  FORMAL INPUT PARAMETERS :
<BR>//      buffer - pointer to series of 32-bit words (NOT bytes).
<BR>//      words  - count of 32-bit words to do.
<BR>//
<BR>//
<BR>//  FORMAL OUTPUT PARAMETERS :
<BR>//      None
<BR>//
<BR>//
<BR>//  RETURN VALUE :
<BR>//      32-bit CRC value as per the STM32F10x CRC generator.
<BR>//
<BR>//
<BR>//  IMPLICIT INPUTS AND OUTPUTS :
<BR>//      None
<BR>//
<BR>//
<BR>//  IMPORTED FUNCTIONS AND MACROS :
<BR>//      cm_ini(), cm_nxt(), cm_crc()
<BR>//
<BR>//
<BR>//////////////////////////////////////////////////////////////////////////
<BR>
<BR>static      crc32_t                     CRC_CalcBlockCRC(ulword *buffer, ulword words)
<BR>{
<BR>cm_t        crc_model;
<BR>ulword      word_to_do;
<BR>ubyte       byte_to_do;
<BR>int         i;
<BR>
<BR>    // Values for the STM32F generator.
<BR>
<BR>    crc_model.cm_width = 32;            // 32-bit CRC
<BR>    crc_model.cm_poly  = 0x04C11DB7;    // CRC-32 polynomial
<BR>    crc_model.cm_init  = 0xFFFFFFFF;    // CRC initialized to 1's
<BR>    crc_model.cm_refin = FALSE;         // CRC calculated MSB first
<BR>    crc_model.cm_refot = FALSE;         // Final result is not bit-reversed
<BR>    crc_model.cm_xorot = 0x00000000;    // Final result XOR'ed with this
<BR>
<BR>    cm_ini(&crc_model);
<BR>
<BR>    while (words--)
<BR>    {
<BR>        // The STM32F10x hardware does 32-bit words at a time!!!
<BR>
<BR>        word_to_do = *buffer++;
<BR>
<BR>        // Do all bytes in the 32-bit word.
<BR>
<BR>        for (i = 0; i < sizeof(word_to_do); i++)
<BR>        {
<BR>            // We calculate a *byte* at a time. If the CRC is MSB first we
<BR>            // do the next MS byte and vica-versa.
<BR>
<BR>            if (crc_model.cm_refin == FALSE)
<BR>            {
<BR>                // MSB first. Do the next MS byte.
<BR>
<BR>                byte_to_do = (ubyte) ((word_to_do & 0xFF000000) >> 24);
<BR>                word_to_do <<= 8;
<BR>            }
<BR>            else
<BR>            {
<BR>                // LSB first. Do the next LS byte.
<BR>
<BR>                byte_to_do = (ubyte) (word_to_do & 0x000000FF);
<BR>                word_to_do >>= 8;
<BR>            }
<BR>
<BR>            cm_nxt(&crc_model, byte_to_do);
<BR>        }
<BR>    }
<BR>
<BR>    // Return the final result.
<BR>
<BR>    return (cm_crc(&crc_model));
<BR>}
<BR>

Wenn ich mal zu viel Zeit habe, schreibe ich mal eine Java-Methode 
dafür. Da die Performance der Checksummen bei meinem Projekt allerdings 
nicht wirklich wichtig ist, habe ich das mal hinten an gestellt.

Viele Grüße, Oliver.

[Reinhard Kern (Gast)]

Oliver Behr schrieb:
> ich wundere mich gerade darüber, ob es einen Unterschied macht, ob ich
> eine CRC-32 (Ethernet) Prüfsumme Byte für Byte berechne oder Wort für
> Wort (uint32_t).

Hallo Oliver,

das ist wurscht: CRC funktioniert bitweise, es ist ja für serielle Daten 
gedacht. Eine CRC-Hardware schiebt also die Daten Bit für Bit durch den 
CRC-Generator, wie sie auf der Leitung TxD gesendet oder auf RxD 
empfangen werden.

Bei Software im Prinzip das Gleiche: die Grundverknüpfung des nächsten 
Bits mit dem bisherigen Ergebnis muss für ein Byte daher 8x, für ein 
Word 16 x aufgerufen werden usw. Mit den üblichen Tabellen fasst man 
z.B. die 8 Bitoperationen für ein Byte zwar zusammen, aber natürlich 
ändert das nichts am zugrundeliegenden Algorithmus, und das geht eben 
auch für 16 oder 32 Bit nach dem Muster for i := 1 to 32 do 
Schiebe1BitRein.

Gruss Reinhard

[Peter D. (peda)]

Oliver Behr schrieb:
> Wie soll man denn CRCs überprüfen,
> wenn man nicht mal die Berechnungsgrundlage kennt?

Wie eine CRC berechnet wird, ist immer gleich. Unterschiedlich ist nur 
das Polynom und die Länge.
Und das Polynom wird ST bestimmt irgendwo erwähnt haben.

Die Länge richtet sich hauptsächlich nach der Datenmenge.
Bis 256Byte bevorzugt man 8Bit-CRC, bis 64kB 16Bit-CRC und darüber 
32Bit-CRC.

Bekannte Polynome sind:
0x8C (i-Button)
0xa001
0x1021 (X-Modem)
0x8408 (IrDA)


Peter

[Oliver B. (irq)]

Vielen Dank für die Antworten, ich habe nun die Lösung gefunden:

STM32-CRC kompatibel zur Java-Implementierung:

1) Alle Wörter, die in das Datenregister geschrieben werden, müssen 
vorher in ihrer Bitfolge invertiert werden.
2) Das finale Ergebnis muss ebenfalls invertiert und anschließend per 
XOR mit 0xffffffff verknüpft werden.

Beschreibung hier: 
https://my.st.com/public/STe2ecommunities/mcu/Lists/ARM%20CortexM3%20STM32/Flat.aspx?RootFolder=%2Fpublic%2FSTe2ecommunities%2Fmcu%2FLists%2FARM%20CortexM3%20STM32%2FCRC32%20calculation%20mismatch&FolderCTID=0x01200200770978C69A1141439FE559EB459D758000626BE2B829C32145B9EB5739142DC17E&currentviews=555

Richtig, das Polynom ist das Gleiche, aber auf den Rest muss man erst 
mal kommen, darüber schweigt nämlich das Manual. Aber jetzt ist es ja 
raus, hoffe ich kann demjenigen helfen, der vor dem gleichen Problem 
steht.

Beispielimplementierung (getestet):

u32 rbit(u32 d)
{
    __asm__
    (
            " rbit %0, %0"
            : "=r" (d)
            : "0" (d)
            : "cc"
    );

    return d;
}

uint32_t computeCRC32Hardware(uint32_t *data, uint32_t wordCount)
{
  uint32_t i;
  uint32_t crc;

    CRC_ResetDR();
    for(i = 0; i < wordCount; i ++)
    {
      CRC_CalcCRC(rbit(data[i]));
    }
    crc = rbit(CRC_GetCRC()) ^ 0xffffffff;
    return crc;
}

Viele Grüße, Oliver.

[Hans M. (Firma: mayer) (oe1smc)]

hallo Oliver

> Funktioniert prima, hat nur den Nachteil, dass es zusätzlich 1k im Flash
> belegt und auch nicht so schnell ist, wie die HW-CRC.

ich war bei einer 1-wire anwendung auf der suche, wie man den 8-bit crc 
pruefen koennte.  bin dabei auf folgendes code example gestossen
http://www.dattalo.com/technical/software/pic/crc_8bit.c
Scott Dattalo beschreibt darin 3 verschiedene moeglichkeiten ( methoden 
) den crc zu berechnen. einmal mit einer grossen tabelle, dann mit 2 
kleinen und die dritte kommt ohne tabelle aus, nur rechnen.

so etwas muesste es ja auch fuer deinen 32-bit crc geben, denn dem liegt 
ja sicherlich auch ein primzahlenpolynom zugrunde, aber halt 
entsprechend hoeheren grades.

ich habe zwar genug flash, habe aber auch die letzte methode genommen.

schoene gruesse
hans

--

[Hans (Gast)]

>so etwas muesste es ja auch fuer deinen 32-bit crc geben, denn dem liegt
>ja sicherlich auch ein primzahlenpolynom zugrunde, aber halt
>entsprechend hoeheren grades.

Das ist richtig. Normalerweise hat man byteweise das Problem, ob in
die Berechung der CRC das MSB oder das LSB zuerst in die CRC eingeht.
Nun zeigt aber der obige Code, dass man
- wortweise (32Bits) hantieren muss
- dies wortweise (mit dem rbit) gedreht
   (Bit31<->Bit0, Bit30<->Bit1,...) werden muss.

Kurzgefasst: der HW-CRC ist zu nichts kompatibel, was man sonst im
dem Bereich verwendet. (Gerade fuer den Kommunikationsbereich gaebe
es Dutzende von Implementierungen...)

VG, auch
Hans

[Oliver B. (irq)]

Hallo Hans,

ja genau, man muss nicht unbedingt die komplette Tabelle nehmen, es 
reicht auch eine kleinere oder gar keine, geht dann halt zu Lasten der 
Geschwindigkeit.

Ich muss ein bisschen auf die Codegröße schauen, da ich einen Bootloader 
(zum flashen) schreibe und da netto vom Flash für die Applikation dann 
noch genügend übrig bleiben muss. Fix sollte es beim Flashen auch gehen, 
daher rein in Software ohne Tab wäre auch nicht ideal. Außerdem hat der 
STM32 ja eine integrierte CRC-Einheit in Hardware, da hätte es mich 
etwas gewurmt, wenn es nicht mit der gehen würde.

Wie Peter geschrieben hat, würde mir evtl auch eine 16-bit CRC reichen, 
da ich immer eine Page übertrage und darüber die CRC mache. Da ließe 
sich dann entweder Codegröße einsparen oder mehr Geschwindigkeit 
rausholen, wenn man es in Software realisieren würde. Aber jetzt geht es 
ja auch mit der Hardware-Einheit.

Viele Grüße, Oliver.