Auf der Suche nach einem schnellen CRC8 Algorithmus hab ich mir den in
der avr libc mal angeschaut und mich gewundert. Warum wird bei manchen
CRC Berechnungen nicht immer gleich ein komplettes Byte verarbeitet
sonder mit Schleife die einzelnen Bits durchgeschoben.
Wenn man sich den Algorithmus als eine Black-Box vorstellt und eben nur
aus den Bits im Eingangsbyte ein neuer CRC Wert berechnet kann man eine
Matrix aufstellen, welche dann eben mit asm-Befehlen optimiert werden
kann.
So sieht die Matrix zum beispiel für den CRC8 (x^8 + x^5 + x^4 + 1) für
Maxim/Dallas 1-Wire Geräte aus:
76543210
0 xx x
1 xx x x
2 xx x xx
3 x x xx
4 x xx
5 x xx
6 x xx x
7 x xx x
Somit setzt sich das AusgabeBit 0 aus dem XOR von Eingangsbit 5, 4 und 2
zusammen, usw.
Daraus hab ich also folgenden Assembler-Code generiert:
1
; zuerst das XOR von dem vorherigen CRC mit dem Datenbyte
2
eor 24, 22
3
; dann brauchen wir 2 Kopien
4
mov 22, 24
5
mov 23, 24
6
7
bst 22, 0
8
lsr 22
9
eor 24, 22
10
swap 24
11
andi 23, 0xF0
12
bld 23, 1
13
eor 24, 23
14
15
andi 22, 0x07
16
bld 22, 7
17
lsr 22
18
brcc skip
19
sbr 22, 0x80
20
skip:
21
sbrc 24, 4
22
sbr 22, 0x0C
23
eor 24, 22
24
ret
Damit ist man mit 18 Instruktionen schon wesentlich schneller als die
Schleife die in der avr-libc drin ist, welche 50 Zyklen für einen
Durchlauf braucht (dafür aber auch 10 Befehle weniger Platz braucht).
Vielleicht hab ich noch was übersehen was man noch eleganter, kürzer
schreiben könnte?
Je nach Generatorpolynom gelingt das umsetzen auf byteweise Verarbeitung
unterschiedlich gut, so ist der CRC-8 (ITU-T) mit x^8 + x^2 + x + 1 um
einiges kürzer.
01234567
0 012
1 123
2 234
3 345
4 0 456
5 1 567
6 1 67
7 01 7
1
; zuerst das XOR von dem vorherigen CRC mit dem Datenbyte
2
eor 24, 22
3
; dann brauchen wir eine Kopie
4
mov 22, 24
5
clr 23
6
7
lsr 22
8
eor 24, 22
9
brcc no_bit_0
10
sbr 23, 0x10
11
no_bit_0:
12
ror 22
13
eor 24, 22
14
brcc no_bit_1
15
sbr 23, 0xE0
16
no_bit_1:
17
eor 24, 23
18
ret
Manche werden jetzt einwenden das ein richtig schneller CRC nur mit
einer Look-Up Tabelle geht, jedoch benötigt auch das Pointer berechnen
und nachschauen in der (meist im PGM liegenden) Tabelle nicht
unerheblich viel Zeit (auch immerhin 8 Zyklen):
1
; zuerst das XOR von dem vorherigen CRC mit dem Datenbyte
Wenn man das nicht als Subroutine, sondern mittels eines #define
inlined, sind das ebenfalls 18 Cycles.
Im original-File avreth1\util\crc8.c von Simon Schulz ist ein dicker
Bug:
crc8_calc_byte(crc,data[len]);
// pgm_read_byte(&crc8_lookuptable[crc ^ data[len]]);
richtig ist:
crc8_calc_byte(crc,data[ i ]);
// pgm_read_byte(&crc8_lookuptable[crc ^ data[ i ]]);
Den selben Bug habe ich auch in einer crc16-Version gesehen:
unsigned short OneWireCRC::crc16(unsigned short* data, unsigned short
len)
{
unsigned short i;
unsigned short crc = 0;
for ( i = 0; i < len; i++){
// unsigned short cdata = data[len]; //Bug: len --> i
unsigned short cdata = data[ i ];
// cdata = (cdata ^ (crc & 0xff)) & 0xff; //sollte auch einfacher
gehen:
cdata = (cdata ^ crc ) & 0xff;
crc >>= 8;
if (oddparity[cdata & 0xf] ^ oddparity[cdata >> 4]) crc ^= 0xc001;
cdata <<= 6; //alles sehr umständlich
crc ^= cdata;
cdata <<= 1;
crc ^= cdata;
}
return crc;
}
Armin Otterstätter schrieb:> So sieht die Matrix zum beispiel für den CRC8 (x^8 + x^5 + x^4 + 1) für> Maxim/Dallas 1-Wire Geräte aus:>> 76543210> 0 xx x> 1 xx x x> 2 xx x xx> 3 x x xx> 4 x xx> 5 x xx> 6 x xx x> 7 x xx x>> Somit setzt sich das AusgabeBit 0 aus dem XOR von Eingangsbit 5, 4 und 2> zusammen, usw.
Ich sitze da jetzt schon eine ganze Weile drüber und krieg einfach nicht
raus, wie Du auf die Tabelle kommst. Könntest Du ein Beispiel posten?
Gruß, Maria
Hmm also im als einfachsten Fall durch stupides ausprobieren.
Letzendlich bildet der CRC einen Eingangwert auf einen Ausgangswert ab.
Dabei ist der Eingangswert und der Ausgangswert immer gleich breit
(Bit-Breitemäßig gesehen) und zwar so breit wie der CRC der am Ende
rauskommen soll.
Betrachte ich also den CRC als eine Black-Box, dann kann diese doch für
z.B. 8-Bit CRC maximal 256 verschiedene Eingangswerte sehen. Für jeden
dieser Eingangswerte bekomme ich nun einen Ausgangswert. Da die
CRC-Berechnung auf XOR beruht kann man sich also überlegen welche Bits
des Eingangswerts XOR-Verknüpft werden müssen damit sich der vorgegebene
Ausgangswert ergibt.
Ich hab dazu mal ein Gnumeric-Sheet (OpenSource-Excel) gemacht, wenn
dich das interessiert kann ich es dir gerne schicken (allerdings im
Moment noch alles undokumentiert). Damit lässt sich die Matrix durch
"ausprobieren" relativ leicht erstellen, da es falls Fehler vorhanden
sind, diese anzeigt.
Grüße,
armino
Armin Otterstätter schrieb:> Ich hab dazu mal ein Gnumeric-Sheet (OpenSource-Excel) gemacht, wenn> dich das interessiert kann ich es dir gerne schicken (allerdings im> Moment noch alles undokumentiert). Damit lässt sich die Matrix durch> "ausprobieren" relativ leicht erstellen, da es falls Fehler vorhanden> sind, diese anzeigt.>> Grüße,> armino
Das wäre nett!
Aber ich denke, da ist noch ein Mißverständnis. Ich habe mal für einen
Beispiel-Input 10101010 den CRC berechnet, ungespiegeltes und
gespiegeltes Polynom. Aber Deine Tabelle reproduziert weder den einen,
noch den anderen Wert:
1
76543210
2
1010101000000000 : 100110001
3
100110001
4
---------
5
110010100
6
100110001
7
---------
8
101001010
9
100110001
10
---------
11
111101100
12
100110001
13
---------
14
110111010
15
100110001
16
---------
17
100010110
18
100110001
19
---------
20
100111
21
22
76543210
23
1010101000000000 : 100011001
24
100011001
25
---------
26
100110100
27
100011001
28
---------
29
101101000
30
100011001
31
---------
32
111000100
33
100011001
34
---------
35
11011101
Ist der Startwert <> 0? Oder was ist der Fehler?
Gruß, Maria
Korrekt, da hab ich meinen asm-Code oben nicht so genau beschrieben.
Es steht zwar in der ersten Zeile das wir ein XOR des Datenbytes mit dem
vorherigen CRC machen, dieser Schritt wird sonst aber nirgends
erläutert.
Daher hier nochmal genauer dokumentiert:
1
; zuerst das XOR von dem vorherigen CRC mit dem Datenbyte
2
eor 24, 22
3
4
; dann brauchen wir 2 Kopien
5
mov 22, 24
6
mov 23, 24
7
8
; aller Code ab hier wurde mithilfe der Tabelle generiert
9
bst 22, 0
10
lsr 22
11
eor 24, 22
12
swap 24
13
andi 23, 0xF0
14
bld 23, 1
15
eor 24, 23
16
17
andi 22, 0x07
18
bld 22, 7
19
lsr 22
20
brcc skip
21
sbr 22, 0x80
22
skip:
23
sbrc 24, 4
24
sbr 22, 0x0C
25
eor 24, 22
26
ret
In deinem Fall hätte die Blackbox ja zwei Eingangswerte einmal das
Datenbyte und den CRC.
Das gnumeric-file hab ich mal angehängt.
Grüße,
armino
Armin Otterstätter schrieb:> Warum wird bei manchen> CRC Berechnungen nicht immer gleich ein komplettes Byte verarbeitet> sonder mit Schleife die einzelnen Bits durchgeschoben.
Vielleicht weil bei der häufigsten Anwendung von CRC8 - nämlich den
Dallas-Sensoren - sich kaum jemand darüber Gedanken macht, wie man pro
Sekunde wenige Mikrosekunden einsparen kann.
Armin Otterstätter schrieb:> Korrekt, da hab ich meinen asm-Code oben nicht so genau beschrieben.>> Es steht zwar in der ersten Zeile das wir ein XOR des Datenbytes mit dem> vorherigen CRC machen, dieser Schritt wird sonst aber nirgends> erläutert.>> Daher hier nochmal genauer dokumentiert:>>
1
> ; zuerst das XOR von dem vorherigen CRC mit dem Datenbyte
2
> eor 24, 22
3
>
Hier wird aber auch nicht geklärt, mit welchem Wert crc initialisiert
wird!
0x00 oder 0xff oder was?
> Das gnumeric-file hab ich mal angehängt.
Danke schön! Das werde ich mal studieren.
Gruß, Maria
A. K. schrieb:> Vielleicht weil bei der häufigsten Anwendung von CRC8 - nämlich den> Dallas-Sensoren - sich kaum jemand darüber Gedanken macht, wie man pro> Sekunde wenige Mikrosekunden einsparen kann.
Das kommt wie du ja schon schreibt ganz auf die Anwendung an. In meinem
Fall soll der CRC8 ein Bus-Protokoll absichern. Da der Bus-Master dabei
pro Sekunde für bis zu 250 Devices mehrere CRC berechnen muss macht es
schon Sinn auf die Geschwindigkeit zu achten. Eine Tabellenlösung wollte
ich vermeiden um nicht soviel Flashspeicher zu verschenken.
Ich hab mich gefreut eine Lösung zwischen Tabelle und stupider Schleife
gefunden zu haben und wollte es für andere zur Verfügung stellen. Wer's
nicht brauch muss es ja nicht verwenden.
maria czerny schrieb:> Hier wird aber auch nicht geklärt, mit welchem Wert crc initialisiert> wird!> 0x00 oder 0xff oder was?
Die von mir vorgeschlagene Black-Box Ansicht auf die CRC Implementierung
hat nichts mit der Initialisierung des CRC zu tun. Das kann als je nach
Gusto (bzw. Vorgabe des CRC) gewählt werden.
Hallo Armin,
Du hast auf Deinem ersten Tabellenblatt (CRC-8 Dallas/Maxim) in der
ersten Spalte die Input-Bytes und in der zweiten die zugehörigen CRCs,
stimmts?
In meinem Beispiel oben entspricht bei LSB-first dem Input-Byte der Wert
0x55 (85) und bei MSB-first der Wert 0xAA (170). Dies entspricht bei
normalem Polynom der CRC 0x27 und bei reflektiertem Polynom der CRC
0xDD.
In Deiner Tabelle ist aber weder an der Position 85 noch an der Position
170 einer der beiden CRCs zu finden.
Was also ist der Fehler?
Gruß, Maria
maria czerny schrieb:> Du hast auf Deinem ersten Tabellenblatt (CRC-8 Dallas/Maxim) in der> ersten Spalte die Input-Bytes und in der zweiten die zugehörigen CRCs,> stimmts?
Stimmt soweit.
maria czerny schrieb:> Was also ist der Fehler?
Keine Ahnung ich denk mal mit deinem Beispiel stimmt was nicht. Ich hab
die Werte mit der crc-Funktion die mit der Avr-Libc mitgeliefert wird
generiert. Und wenn ich diesen Online-Calculator
(http://www.datastat.com/sysadminjournal/maximcrc.cgi) nehme und z.B. 55
eingebe dann stimmt das ja auch...
Thread beobachten
Seitenaufteilung abschalten