Pruefsummen-Verfahren gesucht
Peter Simons
Ich habe eine Frage: Ich muss fuer ein paar Datenuebertragungs-
routinen ein eigenes Datenprotokoll entwerfen. Jetzt stellt sich
natuerlich die Frage, welches Pruefsummenverfahren ich verwenden
soll. Das populaerste scheint ja das CRC-Verfahren zu sein. Kann
mir jemand vielleicht eine Beschreibung und eventuell einen
Sourcecode dazu schicken? (Assembler bevorzugt...)
Ausserdem wuerde es mich interessieren, ob es Pruefsummenver-
fahren gibt, bei denen es moeglich ist, die falsch Uebertragenen
Daten zu restaurieren.
Ok, danke im Vorraus....Peter
--
--------------------------------------------------------------------------
Peter Simons FIDO-Net USE-Net
+49 (0)228-746061 Voice 2:241/5305.5 sim...@peti.GUN.de
Lutz Vieweg
> Ich habe eine Frage: Ich muss fuer ein paar Datenuebertragungs-
> routinen ein eigenes Datenprotokoll entwerfen. Jetzt stellt sich
> natuerlich die Frage, welches Pruefsummenverfahren ich verwenden
> soll. Das populaerste scheint ja das CRC-Verfahren zu sein. Kann
> mir jemand vielleicht eine Beschreibung und eventuell einen
> Sourcecode dazu schicken? (Assembler bevorzugt...)
Klar, wenn sich's um meine Lieblingssprache dreht, immer... ;-)
Folgende Routine berechnet die CRC-Pruefsumme, die beim KERMIT
Protokoll gebraucht wird (Type 3). Das Programm ist schon uralt - daher
bitte flames von wegen Style nach nil:
Ich werde es ein bischen nachkommentieren, da ich es (wie immer,
wenn ich Sachen nur fuer mich schreibe) nicht die Bohne kommentiert habe:
crc3 ; a0 = Zeiger auf String (ueber den die Summe gebildet
; werden soll
; d0 = Länge desselben
movem.l d1-d7/a1-a6,-(sp)
moveq #0,d2 ; fuer die spaetere CRC
moveq #0,d3 ; halt eine lokale variablen
subq.w #1,d0 ; laenge = 0 ?
bmi 1$
2$
moveq #0,d1
move.b (a0)+,d1
move.w d1,d3
eor.w d2,d3
and.w #$f,d3
mulu #$1081,d3 ; der wesentliche und langsamste
; Befehl (heul)
lsr.w #4,d2
eor.w d3,d2
lsr.w #4,d1
eor.w d2,d1
and.w #$f,d1
mulu #$1081,d1 ; dito
lsr.w #4,d2
eor.w d1,d2
dbra d0,2$ ; das war's pro byte
1$
; an dieser Stelle steht in d2 der fertige 16-Bit CRC,
; er wird jetzt nur noch in ASCII-Zeichen (eben fuer
; KERMIT) gewandelt
moveq #0,d0
move.w d2,d0
rol.w #4,d0
and.w #$f,d0
add.w #$20,d0
swap d0
move.w d2,d0
lsr.w #6,d0
and.w #$3f,d0
add.w #$20,d0
lsl.w #8,d0
and.w #$3f,d2
add.w #$20,d2
move.b d2,d0
; in d0 sind nun die 3 fertigen ASCII's zu finden...
movem.l (sp)+,d1-d7/a1-a6
rts
Fuer einen 32-bit CRC laeuft die Sache ganz aehnlich, nur habe ich den
bisher noch nicht gebraucht, und daher nicht vorraetig.
Ach ja, die Begruendung, warum dieser CRC als Pruefsumme ganz gut
geeignet ist, ist nicht so kurz und trivial, da verweise ich auf
entsprechende Literatur.
> Ausserdem wuerde es mich interessieren, ob es Pruefsummenver-
> fahren gibt, bei denen es moeglich ist, die falsch Uebertragenen
> Daten zu restaurieren.
Ja, natuerlich. Am einfachsten und bekanntesten duerfte da wohl die
"Cross-Parity" sein, mit deren Hilfe sich vereinzelte Bit-Fehler noch
ohne grossen Aufwand rekonstruieren lassen. Dabei wird ueber einen Block
von Daten eben jeweils eine Paritaet fuer jedes Wort, und eine fuer jede
"Spalte" - d.h. die Bitpositionen gebildet, den Rest kannst Du Dir sicher
denken...
Es gibt dann natuerlich noch wesentlich aufwendigere und maechtigere
Verfahren, die zwar mehr Redundanz verursachen, dafuer aber auch ganze
Scharen von Fehlern korrigieren koennen. Hier muss ich aber auch wieder
auf Literatur verweisen, das ist ein grosses Thema...
cu, Lutz Vieweg
--
..instead of funeral wreaths we'd like you to send your donations
to l...@mania.hotb.sub.org even now. Credit-cards welcome.