Seite 1 von 1

Variable CRC-Prüfsummen unter Qt

Verfasst: 22. September 2008 17:14
von uwe_kornnagel
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 =

Code: Alles auswählen

16+15+10+3 
Der Header TCrcs.h

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
Der Quellcode TCrcs.cpp

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;
}