Variable CRC-Prüfsummen unter Qt
Verfasst: 22. September 2008 17:14
Heutzutage tauschen viele unterschiedliche Geräte ihre Daten mit einem PC aus. Eine große Anzahl dieser Peripherie nutzt eine serielle Übertragung (RS232, USB, FireWire, SATA, Bluetooth usw.). Die Daten werden in der Regel block weise übertragen. Um Fehler bei der Übertragung zu erkennen benutzt man fast immer CRC-Prüfsummen (cyclic redundancy check = zyklische Redundanz Prüfung).
Qt selbst stellt mit der Funktion
qint16 qChecksum ( const char * data, uint len )
lediglich die CRC-16-CCITT (x^16+x^x^12+x^x^5+x^x^0) zur Verfügung. Andere Prüfsummen müssen selbst implementiert werden.
Ich habe eine Klasse TCrcs geschrieben, die es dem Anwender ermöglicht, verschieden Polynome CRC-4 bis CRC-64 zu errechnen.
z.B.
CRC-16-IBM = x^16 + ^15 + x^10 + x^3
CRC-32-(IEEE) = x^32 + x^26 + x^23 + x^22 + x^16 +x^12+ x^11 + x^10 + x^8 + x^7 + x^5 + x^4 +x^2 + x^1 + x^0
CRC-64-ISO-3309 = x^64 + x^4 + x^3 + x^1 + x^0
Der Anwender hat die Möglichkeit der Klasse das Polynom in vereinfachter Form zu übergeben. Es werden nur die Exponenten durch "+" getrennt übergeben.
z.B.
x^16 + x^15 + x^10 + x^3 =
Der Header TCrcs.h
Der Quellcode TCrcs.cpp
Qt selbst stellt mit der Funktion
qint16 qChecksum ( const char * data, uint len )
lediglich die CRC-16-CCITT (x^16+x^x^12+x^x^5+x^x^0) zur Verfügung. Andere Prüfsummen müssen selbst implementiert werden.
Ich habe eine Klasse TCrcs geschrieben, die es dem Anwender ermöglicht, verschieden Polynome CRC-4 bis CRC-64 zu errechnen.
z.B.
CRC-16-IBM = x^16 + ^15 + x^10 + x^3
CRC-32-(IEEE) = x^32 + x^26 + x^23 + x^22 + x^16 +x^12+ x^11 + x^10 + x^8 + x^7 + x^5 + x^4 +x^2 + x^1 + x^0
CRC-64-ISO-3309 = x^64 + x^4 + x^3 + x^1 + x^0
Der Anwender hat die Möglichkeit der Klasse das Polynom in vereinfachter Form zu übergeben. Es werden nur die Exponenten durch "+" getrennt übergeben.
z.B.
x^16 + x^15 + x^10 + x^3 =
Code: Alles auswählen
16+15+10+3
Code: Alles auswählen
#ifndef TCRCS_H
#define TCRCS_H
#include <QtGlobal>
#include <QtAlgorithms>
#include <QMap>
#include <QString>
#include <QStringList>
#include <QStack>
#include <QFile>
#include <QBitArray>
/**
@author Uwe Kornnagel <uwe@kornnagel.eu>
*/
typedef QMap <QString, QString> TCrcModes;
typedef QList <quint64> TInt64List;
typedef QStack <quint64> TInt64Stack;
class TCrcs {
public:
TCrcs();
~TCrcs();
inline QBitArray CrcBits() {return crc_bits; } // Das Generalpolynom binär
inline quint64 CrcMask() {return crc_mask; } // Die Crc-Maske z.B. 16-Bit = 0xFFFF
inline quint64 CrcTop() {return crc_top; } // Die Crc-TOP Maske für höchstes Bit z.B 16-Bit = 0x8000
inline quint64 CrcPolyWert() {return crc_polywert; } // der Wert des Generalpolynoms
inline quint64 CrcRevPolyWert() {return crc_revpolywert; } // der Wert des reversen Generalpolynoms
inline quint8 CrcLen() {return crc_len; } // die Anzahl der gültigen CRC-Bits z.B. 8, 16, 32 usw.
inline quint64 *CrcTab() { return crc_tab; } // die CRC-Tabelle
inline quint64 CrcValue() {return crc_value; }
inline quint64 CrcStartWert() { return crc_startwert; }
inline TCrcModes CrcModes() { return crc_modes; } // vordefinierte CRC-Polynome
void clear();
void setPolynom(QString wert);
inline void setCrcStartWert(quint64 wert = 0xFFFFFFFF) { crc_startwert = wert; }
QString HexValue(quint64 wert = 0);
quint64 UpdateCrc(quint8 wert);
quint64 UpdateCrc(QByteArray wert);
quint64 UpdateCrc(QFile *file);
quint64 CalcCrc();
quint64 CalcCrc(quint8 wert);
quint64 CalcCrc(QByteArray wert);
quint64 CalcCrc(QFile *file);
protected:
void CalcTables();
private:
QBitArray crc_bits;
quint64 crc_value;
quint64 crc_startwert;
quint64 crc_mask;
quint64 crc_top;
quint64 crc_polywert;
quint64 crc_revpolywert;
quint8 crc_len;
quint64 crc_tab[256];
TCrcModes crc_modes;
};
extern const char *_crcs[];
#endif
Code: Alles auswählen
#include "tcrcs.h"
/**
* Hier einige Standartpolynome
*/
const char *_crcs[] = {
"Benutzerdefiniert\n",
"CRC- 4 (CCITT)\n4+1+0",
"CRC- 5 (Bluetooth)\n5+4+2+0",
"CRC- 5 (USB)\n5+2+0",
"CRC- 8\n8+7+6+4+2+0",
"CRC- 8 (ATM)\n8+2+1+0",
"CRC- 8 (CCITT)\n8+7+3+2+1",
"CRC- 8 (Dallas)\n8+5+4+0",
"CRC- 8 (SAE J1850)\n8+4+3+2+0",
"CRC- 10\n10+9+5+4+1+0",
"CRC- 12 (Telekommunication)\n12+11+3+2+1+0",
"CRC- 15 (CAN)\n15+14+10+8+7+4+3+0",
"CRC- 16 (CCITT)\n16+12+5+0",
"CRC- 16 (IBM)\n16+15+2+0",
"CRC- 16 (XModem)\n16+15+10+3",
"CRC- 24 (IETF RFC2440)\n24+23+18+17+14+11+10+7+6+5+4+3+1+0",
"CRC- 32 (IEEE)\n32+26+23+22+16+12+11+10+8+7+5+4+2+1+0",
"CRC- 32 (Castagnoli)\n32+28+27+26+25+23+22+20+19+18+14+13+11+10+9+8+6+1",
"CRC- 32 (Koopman)\n32+30+29+28+26+20+19+17+16+15+11+10+7+6+4+2+1+0",
"CRC- 64 (ISO 3309)\n64+4+3+1+0",
"CRC- 64 (ECMA-182)\n64+62+57+55+54+53+52+47+46+45+40+39+38+37+35+33+32+31+29+27+24+23+22+21+19+17+13+12+10+9+7+4+1+0",
0
};
/**
* Der Construktor
Anlegen der Tabellen und Initialisierung der Werte
*/
TCrcs::TCrcs() {
clear();
crc_modes.clear();
char *poly, **src = (char **) _crcs;
char line[257];
QString crcName, crcPoly;
while (*src) {
crcName.clear();
crcPoly.clear();
memset(line, 0, 257);
strncpy(line, *src++, 256);
poly = strchr(line, 0x0a);
if (poly) {
*poly++ = 0;
crcPoly.append(poly);
}
crcName.append(line);
crc_modes[crcName.trimmed()] = crcPoly.trimmed();
}
}
/**
* Der Destrultor
Speicherplatz der Tabellen freigeben
*/
TCrcs::~TCrcs() {
}
/**
* Clear
Iniltialsierung aller Werte auf 0x00
*/
void TCrcs::clear() {
crc_bits.clear();
crc_polywert = crc_mask = crc_top = crc_revpolywert = crc_len = crc_value = 0;
setCrcStartWert();
memset(crc_tab, 0, sizeof(crc_tab));
}
/**
* Diese Methode berechnet den Polynomwert und den reveresen Polynomwert.
* Der reverse Polynomwert ist der Polynomwert, bitweise rückwärts gelesen.
* @param wert = das Polynom in vereinfachter Schreibweise, es werden nur die Exponenten durch '+' getrennt geschrieben.
* z.B. CRC-32(IEEE) = x^32+ x^26+ x^23+ x^22+ x^16+ x^12+ x^11+ x^10+ x^8+ x^7+ x^5+ x^4+ x^2+ x^1+ x^0
* ergibt: 32+26+23+22+16+12+11+10+8+7+5+4+2+1+0
*/
void TCrcs::setPolynom(QString wert) {
quint8 vpoly = 0;
bool ok = false;
QStringList sl = wert.split('+', QString::SkipEmptyParts, Qt::CaseInsensitive); // Aufsplittung der Exponenten
clear();
crc_bits.resize(256); // Die Bitarray mit 256 Bits anlegen
crc_bits.fill(false, 256);// Alle Bits auf FALSE setzen
// Das Polynom und dessen Geometrie ermitteln
while (!sl.isEmpty()) {
vpoly = sl.first().trimmed().toUInt(); // den 1. Exponente aus der Liste lesen und als quint8 interpretieren
crc_len = qMax(crc_len, vpoly); // der größte Exponent ist der Anzahl der Bits.
crc_bits.setBit(vpoly); // das entsprechende Bit setzen z.B, 16 für x^16;
sl.pop_front(); // den 1. Wert aus der Liste entfernen => somit wird der 2. Wert zum Ersten.
}
crc_bits.resize(crc_len); // Die Bitmap auf die Anzahl der benötigen bits kürzen
// Die Maske der aktuellen CRC-Länge bestimmen z.B. 16-Bit = 0xFFFF
wert.clear();
wert.fill('1', crc_len);
crc_mask = wert.toULongLong(&ok, 2);
wert.clear();
wert.fill('0', crc_len);
wert[0] = '1';
crc_top = wert.toULongLong(&ok, 2);
// Den Polynomwerte und den reversen Polynomwert berechnen
for (register int i = 0; i < crc_bits.count(); i++) crc_polywert |= (1 << i) * (crc_bits.testBit(i) ? 1 : 0);
for (register int i = crc_bits.count(); i > 0; i--) {
crc_revpolywert <<= 1;
crc_revpolywert |= crc_bits.testBit(crc_len - i) ? 1 : 0;
}
CalcTables();
}
/**
* Berechnung der einzelnen CRC-Tabellen
*/
void TCrcs::CalcTables() {
quint64 crc;
for (register short i = 0; i < 256; i++) {
crc = i;
for (register short j = 0; j < 8; j++) {
crc = (crc & 0x1) ? crc_revpolywert ^(crc >> 1) : (crc >> 1);
}
crc_tab[i] = crc & crc_mask;
}
}
/**
* CRC um ein Byte aktualiseren
* @param wert Das neue Byte
* @return CRC
*/
quint64 TCrcs::UpdateCrc(quint8 wert) {
quint64 _tmp = wert ^ 0xff;
crc_value = ((crc_value >> 8) ^ crc_tab[_tmp & 0xff]) & crc_mask;
return crc_value;
}
/**
* CRC um den Inhalt einer Datei aktualiseren
* @param file offene Datei
* @return CRC
*/
quint64 TCrcs::UpdateCrc(QFile * file) {
if (file) {
if (file->isReadable()) {
qint64 pos = file->pos();
if (file->reset()) {
UpdateCrc(file->readAll());
file->seek(pos);
}
}
}
return crc_value;
}
/**
* CRC um eine Bytearray aktualiseren
* @param wert Die neue Bytearray
* @return CRC
*/
quint64 TCrcs::UpdateCrc(QByteArray wert) {
for (register quint64 i = 0; i < wert.count(); i++) UpdateCrc(wert.at(i));
return crc_value;
}
/**
* Initialisiert eine CRC-Berechung
* @return CRC
*/
quint64 TCrcs::CalcCrc() {
crc_value = CrcStartWert();
return crc_value;
}
/**
* Berchnet die CRC für ein Byte neu
* @param wert Das Byte
* @return CRC
*/
quint64 TCrcs::CalcCrc(quint8 wert) {
crc_value = CrcStartWert();
return UpdateCrc(wert);
}
/**
* Berechnet die CRC für eine Bytearray
* @param wert die ByteArray
* @return CRC
*/
quint64 TCrcs::CalcCrc(QByteArray wert) {
crc_value = CrcStartWert();
return UpdateCrc(wert);
}
/**
* erechnet die CRC einer Datei
* @param file offene Datei
* @return CRC
*/
quint64 TCrcs::CalcCrc(QFile * file) {
crc_value = CrcStartWert();
return UpdateCrc(file);
}
/**
* Ausgabe eines Werte in Hex, die Länge wird an die Anzahl der gültigen Bits angepasse
* @param wert der auszugebende Wert
* @return der angepasste Hexstring
*/
QString TCrcs::HexValue(quint64 wert) {
QString x;
x = QString::number(wert, 16);
x = x.rightJustified(crc_bits.count() >> 2, '0');
return x;
}