crc algo

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?

volkard

Algorithmann schrieb:

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

Aber meiner ist eher geraten. Ich würde ihn nicht einsetzen, ohne ihn mit ein paar Millionen Tests gegen kkaws Version laufen zu lassen.

Das, was ich geschrieben habe, bezog sich auf die zuletzt hier gezeigte Tabellengenerierung, wo -- und das ist mir jetzt aufgefallen -- die Richtung des Shifts nicht mit dem übereinstimmt, was Du hier zu erst gezeigt hattest.

Algorithmann schrieb:

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

Ist das ein Bugfix? Das sieht für mich nämlich in erster Linie nach einer CRC mit Polynom x⁸+x⁴+x+1 aus, wobei die oberen 4 Bits aschließend weggeschmissen werden. Ich denke nicht, dass das äquivalent ist.

Bzgl Effizienz: Das sollte keinen Unterschied machen, es sei denn vielleicht, Du rufst calcCrc für jedes Byte einzeln auf.