crc algo

Hi, wie kann ich mit hilfe dieses algos eine 4 bit crc generieren?
wo setze ich den crc_seed?

// makeTable returns the Table constructed from the specified polynomial.
    func vector<uint32> makeTable(uint32 poly) {
        vector<uint32> Table(256);

    	for (uint32 i = 0; i < 256; i++) {
    		uint32 crc = uint32(i);

    		for (int j = 0; j < 8; j++) {
    			if ((crc&1) == 1) {
    				crc = (crc >> 1) ^ poly;
    			} else {
    				crc >>= 1;
    			}
    		}
    		t[i] = crc;
    	}
    	return t;
    }

kann man den table approach auch für 4 bit crc nehmen?

lagalopex

Der Ansatz mit der Tabelle ist ja dafür da, immer ganze Datenbytes auf einmal verarbeiten zu können. Es ist erstmal unabhängig von der Länge des CRC bzw des gewählten Polynoms.
Für eine 4-bit-CRC musst du also nur ein entsprechendes Polynom vom Grad 4 verwenden. (Wikipedia hat da schon eins...)

Was meinst du mit crc_seed? Einfach den Startwert für die CRC?

ich finde leider den bug nicht...
als polynom have ich: 0x11

#include <iostream>
#include <vector>
#include <sstream>
using namespace std;

typedef unsigned char uint8;
vector<char> Table(256);
uint8 poly = 0x11;
uint8 seed = 0x0A;

// makeTable returns the Table constructed from the specified polynomial.
void makeTable(uint8 poly) {
	for (unsigned int i = 0; i < 256; i++) {
		uint8 crc = uint8(i);
		for (unsigned int j = 0; j < 8; j++) {
			if ((crc&0x80) != 0) {
				crc = crc<<1 ^ poly;
			} else {
				crc <<= 1;
			}
		}
		Table[i] = crc;
	}
}

// Update returns the result of adding the bytes in p to the crc.
uint8 calcCrc(uint8 crc, vector<uint8> p) {
	for (auto v : p) {
		crc = Table[crc^v];
	}
	return crc;
}

int main() {
	// your code goes here

	makeTable(poly);
	vector<uint8> p = {0xA2, 0x20, 0x00, 0x00};

	uint8 crc = calcCrc(seed, p);

	cout << "crc: " << (unsigned int)crc << endl;

	return 0;
}

für: {0xA2, 0x20, 0x00, 0x00}; sollte die crc = 0 sein...

lagalopex

Welches Polynom willst du denn haben? Das jetztige sieht nicht nach 4. Grad aus.

Wieso hast du die Berechnung von der Tabelle geändert?

oenone

Sicher, dass das Polynom 0x11 und nicht 0b11 (also 0x03) sein soll?

das polynom ist: 10001

wenn ich dort folgendes eigebe:
CRC order: 4,
CRC polynom: 11,
init value: 0A,
Final XOR value: FF,
data: sequence: a2200000

bekomme ich:
Invalid CRC polynom

oenone

Algorithmann schrieb:

wenn ich dort folgendes eigebe:
CRC order: 4,
CRC polynom: 11,
init value: 0A,
Final XOR value: FF,
data: sequence: a2200000

bekomme ich:
Invalid CRC polynom

Dein Polynom ist ja auch 5. Ordnung.

@oenone: was hast du denn eingegeben?

@oenone:
hier noch ein paar crc testfälle...mein algo liefert aber andere ergebnisse

data: 2720006144
crc: 0

data: 2720006912
crc: 3

data: 2720006944
crc: 1

data: 2720007008
crc: 5

data: 2720007040
crc: 11

data: 1610612736
crc: 12

alle angaben in dec...

volkard

Table[i] = crc & 15;

Table[i] = crc & 15;

woher kommt die magic number?

volkard

Algorithmann schrieb:

Table[i] = crc & 15;

woher kommt die magic number?

Du wolltest nur 4 Bit.

ich wollte das crc ergebnis auf 4 bit kuerzen...

// Update returns the result of adding the bytes in p to the crc. 
uint8 calcCrc(uint8 crc, vector<uint8> p) { 
    for (auto v : p) { 
        crc = Table[crc^v]; 
    } 
    return crc & 0xF; 
}

Ob jetzt 10001 für ein Polynom 4. oder 5. Ordnung steht, hängt davon ab, ob die führende Potenz mit drin ist. Ich würde hier tippen, dass 10001 für x^4 + 1 steht, was das Polynom 4. Ordnung sein ist und damit zu einer 4-Bit-CRC passt. Die höchste Potenz braucht man nur bei der Berechnung nicht wirklich. Es ist zumindest für CRC32 praktisch, einfach mit einer 32bit-Konstante zu arbeiten (wo dann quasi das x^32 fehlt und implizit benutzt wird).

Wie dem auch sei, sieht die Berechnung der Tabelle falsch aus. Das ist Code für die Berechnung von 8-Bit-CRCs, der so für 4 Bit CRCs nicht funktioniert. Man kann aber den poly-Wert für die 4-Bit CRC einfach 4 Bits nach links shiften und so tun als hätte man ein Polynom 8. Ordnung (x^8 + x^4). Die Prüfsumme wird dann eben in den oberen 4 Bits stecken und die unteren sollten immer Null sein:

makeTable(poly4 << 4);

wobei dann auch deutlich wird, dass die führende eins bei 0x11 rausfällt. Das ist aber nicht schlimm. calcCrc müsste man so ändern:

uint8 calcCrc4(uint8 crc, vector<uint8> const& p) {
    crc <<= 4; // an die richtige Position schieben, 
               // damit das mit der Tabelle klappt
    for (auto v : p) {
        crc = Table[crc^v];
    }
    return (crc >> 4); // wieder zurück schieben,
                       // die unteren Bits sind eh 0,
}

Ich habe zudem ein const& eingefügtm, weil Du sonst unnötig eine eigene, lokale Kopie in der Funktion bekommst. Noch besser ist wahrscheinlich, das über Iteratoren zu machen, damit Du nicht auf Vektoren beschränkt bist. Alternativ eben const uint8* und std::size_t als Parameter. Das würd ich wahrscheinlich so machen (wenn ich nicht gerade einen schöneren Wrappertypen à la array_view<uint8> zur Hand hätte). Für beliebige Container braucht man so eine Prüfsumme eher selten, darf also IMHO ein lineares Speicherlayout voraussetzen.

Ob x^4 + 1 hier 'n vernünftiges Polynom ist, weiß ich nicht. Für CRC4 (CRC-CCITT) würde man x^4 + x + 1 wählen, also makeTable so aufrufen:

makeTable(0x30);

wobei 3 für x + 1 steht, was wieder um 4 geshiftet wurde (0x30 --> 0x130 = x^8 + x^5 + x^4). Die führende Potenz wird wieder weggelassen, weil sie implizit durch das 0x80-dingen in makeTable wieder dazugedichtet wird.

@kkaw: mit oder ohne volkard sein bugix?

@kkaw: dein bugfix funktioniert nicht...wenn ich jedoch volkard seinen bugfix nehme klappt es...

@kkaw: ok lauft nun auch mit deinem fix...findest du den bugfix durch volkard nicht effizienter?