IBM-CRC-16 Codierung der CRC

[Andreas K. (all-finder)]

Hallo!

Folgende Frage:

Wie wird die oben genannte CRC berechnet:

P(x) = x^16 + x^15 + x^2 + 1

Das heißt ich habe 6 Bytes einer Nachricht, für diese möchte ich die 
16bit CRC errechnen.

z.B.
Byte 0 = 1
Byte 1 = 9
Byte 2 = 254
...

Wie setze ich diese Werte ein? Addiere ich die jeweiligen Werte auf?

Danke, mfg

PS: ich möchte den logischen Rechenweg... nicht Tabellen zum Shiften / 
XOR'n ;)

[oha (Gast)]

Der CRC ist eine Zustandsmaschine, mit dem CRC als gespeicheter Wert. 
Man beginnt mit Null. Dann rechnet man den CRC des ersten bytes und dann 
alle anderen bytes. Und der CRC Wert der Nachricht is der Wert der 
Maschine am Schluss. Wie man den CRC eines einzelnen Bytes ist klar ?

[Andreas K. (all-finder)]

Das ging ja schnell ;).

"beginnt mit Null" hängt aber nicht mit dem Initwert zusammen, oder? 
Dieser wäre 0xFFFF in meinem Fall. Für die einzelnen Bytes würde ich den 
Wert jeweils einsetzen...

Dann hab ich z.B. P(1) = 4 und weiter?

[oha (Gast)]

Gut man kann auch mit FFFF beginnen. ja. Und dann einfach jeweils des 
CRC ueber das byte rechnen, ohne der Initialwert neu zu setzten. Das ist 
alles.

[Andreas K. (all-finder)]

Dann hab ich für jedes Byte eine CRC, was mach ich dann damit?
CRC(Byte0) = 4
CRC(Byte1) = 2058911320946572 ?
...

[Stefan E. (sternst)]

Andreas K. schrieb:
> Dann hab ich für jedes Byte eine CRC, was mach ich dann damit?

Die CRC ist ein "mitlaufender Wert". Die für Byte 0 errechnete CRC ist 
der neue Startwert für die CRC-Berechnung mit Byte 1, und so weiter.

Das Schema ist wie folgt:

CRC = 0xffff
Schleife(für jedes Byte):
   CRC = Berechnung(CRC,Byte)

[Andreas K. (all-finder)]

is leider noch nicht angekommen.. ich habe das Polynome, welches nur x 
hat. Oder muss ich den aktuellen Wert aus der CRC des vorherigen mit dem 
aktuellen Wert kombinieren (jeweils 8Bit) und dann einsetzen!?

Zusätzlich ignoriere ich den Überlauf(e)? (bilde nur eine Funktin ab)

[Stefan E. (sternst)]

Ach so, es hapert an der grundsätzlichen Berechnung.

http://de.wikipedia.org/wiki/Cyclic_Redundancy_Check

[KelleRassel (Gast)]

Kopier doch einfach die Routinen und gut ist. Schieben und XOR.

[Stefan E. (sternst)]

Zusatz (ich bin nicht begeistert von der neuen Editierregelung):

Dein grundsätzlicher Irrtum liegt darin, das Polynom als 
Berechnungsformel zu betrachten. Wenn dein erstes Byte den Wert 10 hat, 
dann wird nicht diese 10 dort als Wert für x eingesetzt und das Ergebnis 
ist dann der CRC. Es ist schon etwas komplizierter. ;-)

[Andreas K. (all-finder)]

okay, zu leicht gedacht...

Anderer Ansatz: ich überprüfe die CRC einer Berechnung auf dem µC und 
versuche diese abzubilden. Hierzu bräuchte ich das Generatorpolynom. 
Aktuell hab ich nur eine generierte Tabelle gegeben.

Wie bringe ich: P(x) = x^16 + x^15 + x^2 + 1 in den Zusammenhang?

[Thomas P. (tpircher)]

Andreas K. schrieb:
> Wie bringe ich: P(x) = x^16 + x^15 + x^2 + 1 in den Zusammenhang?

2^16 + 2^15 + 2^2 + 1 = 0x18005

Davon laesst du das MSB weg und du erhaelst 0x8005.

Ist die erste Zeile der CRC Tabelle vielleicht

0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280, 0xc241, ...

[Andreas K. (all-finder)]

ja...

[Thomas P. (tpircher)]

Der folgende Code ist von pycrc generiert und sollte dir deinen CRC 
berechnen. Vor ein paar Tagen hat peda hier einen code gepostet, der 
etwas schoener anzuschauen ist, aber letzten Endes aehnlichen 
Maschinencode generieren sollte.

Du rufst die CRC Routinen wie folgt auf:

crc_t crc;

crc = crc_init();
// fuer alle Characters (oder Strings) in deinem datagramm:
    crc = crc_update(crc, (unsigned char *)data, data_len);
crc = crc_finalize(crc);

/**
 * \file stdout
 * Functions and types for CRC checks.
 *
 * Generated on Thu Aug 27 13:40:28 2009,
 * by pycrc v0.7.1, http://www.tty1.net/pycrc/
 * using the configuration:
 *    Width        = 16
 *    Poly         = 0x8005
 *    XorIn        = 0x0000
 *    ReflectIn    = True
 *    XorOut       = 0x0000
 *    ReflectOut   = True
 *    Algorithm    = table-driven
 *    Direct       = True
 *****************************************************************************/
#include "stdout.h"
#include <stdint.h>
#include <stdlib.h>

/**
 * Static table used for the table_driven implementation.
 *****************************************************************************/
static const crc_t crc_table[256] = {
    0x0000, 0xc0c1, 0xc181, 0x0140, 0xc301, 0x03c0, 0x0280, 0xc241,
    0xc601, 0x06c0, 0x0780, 0xc741, 0x0500, 0xc5c1, 0xc481, 0x0440,
    0xcc01, 0x0cc0, 0x0d80, 0xcd41, 0x0f00, 0xcfc1, 0xce81, 0x0e40,
    0x0a00, 0xcac1, 0xcb81, 0x0b40, 0xc901, 0x09c0, 0x0880, 0xc841,
    0xd801, 0x18c0, 0x1980, 0xd941, 0x1b00, 0xdbc1, 0xda81, 0x1a40,
    0x1e00, 0xdec1, 0xdf81, 0x1f40, 0xdd01, 0x1dc0, 0x1c80, 0xdc41,
    0x1400, 0xd4c1, 0xd581, 0x1540, 0xd701, 0x17c0, 0x1680, 0xd641,
    0xd201, 0x12c0, 0x1380, 0xd341, 0x1100, 0xd1c1, 0xd081, 0x1040,
    0xf001, 0x30c0, 0x3180, 0xf141, 0x3300, 0xf3c1, 0xf281, 0x3240,
    0x3600, 0xf6c1, 0xf781, 0x3740, 0xf501, 0x35c0, 0x3480, 0xf441,
    0x3c00, 0xfcc1, 0xfd81, 0x3d40, 0xff01, 0x3fc0, 0x3e80, 0xfe41,
    0xfa01, 0x3ac0, 0x3b80, 0xfb41, 0x3900, 0xf9c1, 0xf881, 0x3840,
    0x2800, 0xe8c1, 0xe981, 0x2940, 0xeb01, 0x2bc0, 0x2a80, 0xea41,
    0xee01, 0x2ec0, 0x2f80, 0xef41, 0x2d00, 0xedc1, 0xec81, 0x2c40,
    0xe401, 0x24c0, 0x2580, 0xe541, 0x2700, 0xe7c1, 0xe681, 0x2640,
    0x2200, 0xe2c1, 0xe381, 0x2340, 0xe101, 0x21c0, 0x2080, 0xe041,
    0xa001, 0x60c0, 0x6180, 0xa141, 0x6300, 0xa3c1, 0xa281, 0x6240,
    0x6600, 0xa6c1, 0xa781, 0x6740, 0xa501, 0x65c0, 0x6480, 0xa441,
    0x6c00, 0xacc1, 0xad81, 0x6d40, 0xaf01, 0x6fc0, 0x6e80, 0xae41,
    0xaa01, 0x6ac0, 0x6b80, 0xab41, 0x6900, 0xa9c1, 0xa881, 0x6840,
    0x7800, 0xb8c1, 0xb981, 0x7940, 0xbb01, 0x7bc0, 0x7a80, 0xba41,
    0xbe01, 0x7ec0, 0x7f80, 0xbf41, 0x7d00, 0xbdc1, 0xbc81, 0x7c40,
    0xb401, 0x74c0, 0x7580, 0xb541, 0x7700, 0xb7c1, 0xb681, 0x7640,
    0x7200, 0xb2c1, 0xb381, 0x7340, 0xb101, 0x71c0, 0x7080, 0xb041,
    0x5000, 0x90c1, 0x9181, 0x5140, 0x9301, 0x53c0, 0x5280, 0x9241,
    0x9601, 0x56c0, 0x5780, 0x9741, 0x5500, 0x95c1, 0x9481, 0x5440,
    0x9c01, 0x5cc0, 0x5d80, 0x9d41, 0x5f00, 0x9fc1, 0x9e81, 0x5e40,
    0x5a00, 0x9ac1, 0x9b81, 0x5b40, 0x9901, 0x59c0, 0x5880, 0x9841,
    0x8801, 0x48c0, 0x4980, 0x8941, 0x4b00, 0x8bc1, 0x8a81, 0x4a40,
    0x4e00, 0x8ec1, 0x8f81, 0x4f40, 0x8d01, 0x4dc0, 0x4c80, 0x8c41,
    0x4400, 0x84c1, 0x8581, 0x4540, 0x8701, 0x47c0, 0x4680, 0x8641,
    0x8201, 0x42c0, 0x4380, 0x8341, 0x4100, 0x81c1, 0x8081, 0x4040
};

/**
 * Reflect all bits of a \a data word of \a data_len bytes.
 *
 * \param data         The data word to be reflected.
 * \param data_len     The width of \a data expressed in number of bits.
 * \return     The reflected data.
 *****************************************************************************/
long crc_reflect(long data, size_t data_len)
{
    unsigned int i;
    long ret;

    ret = data & 0x01;
    for (i = 1; i < data_len; i++)
    {
        data >>= 1;
        ret = (ret << 1) | (data & 0x01);
    }
    return ret;
}


/**
 * Update the crc value with new data.
 *
 * \param crc      The current crc value.
 * \param data     Pointer to a buffer of \a data_len bytes.
 * \param data_len Number of bytes in the \a data buffer.
 * \return         The updated crc value.
 *****************************************************************************/
crc_t crc_update(crc_t crc, const unsigned char *data, size_t data_len)
{
    unsigned int tbl_idx;

    while (data_len--) {
        tbl_idx = (crc ^ *data) & 0xff;
        crc = (crc_table[tbl_idx] ^ (crc >> 8)) & 0xffff;

        data++;
    }
    return crc & 0xffff;
}

[Thomas P. (tpircher)]

Sorry, ich vergass: die dazugehoerige header Datei ist:

/**
 * \file stdout
 * Functions and types for CRC checks.
 *
 * Generated on Thu Aug 27 14:02:29 2009,
 * by pycrc v0.7.1, http://www.tty1.net/pycrc/
 * using the configuration:
 *    Width        = 16
 *    Poly         = 0x8005
 *    XorIn        = 0x0000
 *    ReflectIn    = True
 *    XorOut       = 0x0000
 *    ReflectOut   = True
 *    Algorithm    = table-driven
 *    Direct       = True
 *****************************************************************************/
#ifndef __STDOUT__
#define __STDOUT__

#include <stdint.h>
#include <stdlib.h>

#ifdef __cplusplus
extern "C" {
#endif

/**
 * The definition of the used algorithm.
 *****************************************************************************/
#define CRC_ALGO_TABLE_DRIVEN 1

/**
 * The type of the CRC values.
 *
 * This type must be big enough to contain at least 16 bits.
 *****************************************************************************/
typedef uint16_t crc_t;

/**
 * Reflect all bits of a \a data word of \a data_len bytes.
 *
 * \param data         The data word to be reflected.
 * \param data_len     The width of \a data expressed in number of bits.
 * \return     The reflected data.
 *****************************************************************************/
long crc_reflect(long data, size_t data_len);

/**
 * Calculate the initial crc value.
 *
 * \return     The initial crc value.
 *****************************************************************************/
static inline crc_t crc_init(void)
{
    return 0x0000;
}

/**
 * Update the crc value with new data.
 *
 * \param crc      The current crc value.
 * \param data     Pointer to a buffer of \a data_len bytes.
 * \param data_len Number of bytes in the \a data buffer.
 * \return         The updated crc value.
 *****************************************************************************/
crc_t crc_update(crc_t crc, const unsigned char *data, size_t data_len);

/**
 * Calculate the final crc value.
 *
 * \param crc  The current crc value.
 * \return     The final crc value.
 *****************************************************************************/
static inline crc_t crc_finalize(crc_t crc)
{
    return crc ^ 0x0000;
}


#ifdef __cplusplus
}           /* closing brace for extern "C" */
#endif

#endif      /* __STDOUT__ */