Unterschiede

Hier werden die Unterschiede zwischen zwei Versionen angezeigt.

--- cpm:crc [2011/10/31 07:44] – volkerp
+++ cpm:crc [2025/08/21 10:31] (aktuell) – volkerp
@@ Zeile 1: / Zeile 1: @@
 ====== CRC-Berechnung ======
-In diversen U880-Programmen, z.B. EPROM-Software, wird oftmals eine Prüfsumme ausgegeben. Dabei handelt es sich fast immer um CRC-16 oder auch CCITT genanntes Polynom
+In diversen U880-Programmen, z.B. EPROM-Software, wird oftmals eine Prüfsumme ausgegeben. Dabei handelt es sich fast immer um eine 16 BIT-CRC-Prüfsumme, d.h. ein 17-Bit-Polynom, nach Standard CCITT:
 CRC-CCITT (CRC-16) x^16 + x^12 + x^5 + 1
@@ Zeile 8: / Zeile 8: @@
 Als Startwert wird eigentlich immer 0FFFFh genommen.
+Pseudocode
+<code>
+for each byte:
+    crc ^= byte << 8
+    for 8 bits:
+        if (crc & 0x8000):
+            crc = (crc << 1) ^ 0x1021
+        else:
+            crc <<= 1
+</code>
+:!: In der DDR-Literatur liest man auch oft "SDLC-Polynom". SLDC (Synchronous Data Link Control) wurde Mitte der 70er von IBM für die Kommunikation zwischen ihren Rechnern über die System Network Architecture (SNA) entwickelt. Als Standard-CRC kommt hier das obige CRC16-CCITT-Polynom zum Einsatz.
 In Perl kann man die CRC so berechnen (nicht optimiert, reine Umsetzung des Polynoms!). Die Und-Verknüpfung mit 0x8000 erfolgt zur Maskierung des Hi-Bits 15; Die Und-Verknüpfung mit 0xFFFF ist nötig, um das Ergebnis als 16Bit-Zahl zu belassen.
-<code>
+<code perl>
 $buf = ....;	#Arrays von 2KiByte FFh
 $len = 2048;	#Anzahl der Bytes
@@ Zeile 54: / Zeile 68: @@
 out: HL = CRC
-<code>
+<code z80>
+;------------------------------------------------------------------------------
+; CRC berechnen
+; Routine aus EPROMA2
+; in DE = Startadr., BC = Länge, out HL=CRC
+; CRC-CCITT (CRC-16) x16 + x12 + x5 + 1
+;------------------------------------------------------------------------------
 crc:		ld	hl, 0FFFFh
 crc1:		ld	a, (de)
@@ Zeile 90: / Zeile 110: @@
 		jr	nz, crc1
 		ret
+</code>
+und hier eine direkte Implementierung ohne Optimierung (und dadurch langsamer, aber leichter zu verstehen)
+<code z80>
+;------------------------------------------------------------------------------
+; CRC berechnen
+; Routine aus FA 11/86
+; ab HL, bis DE, ret HL=CRC (SDLC x16+x12+x5+x1)
+;------------------------------------------------------------------------------
+		; ab DE, BC Bytes, ret HL=CRC
+crc_fa0		ld	h,d
+		ld	l,e
+		dec	bc
+		add	hl,bc
+		ex	hl,de
+		ld	(arg2),de
+		; ab HL, bis (arg2), ret HL=CRC
+crc_fa		ld	de, 0FFFFh	; rücksetzen CRC
+bytecrc		ld	b,80h		; beginne mit Bit 7
+crclp1		sla	e		; CRC schieben
+		rl	d
+		sbc	a,a		; Cy=1 -> A=FF
+		xor	(hl)		; Cy=0 -> A=00
+		and	b
+		jr	z,crc0
+		;Rückkopplung CRC-Generator
+		ld	a,e
+		xor	21h		; 0010_0001 bei SDLC
+		ld	e,a
+		ld	a,d
+		xor	10h		; 0001_0000 bei SDLC
+		ld	d,a
+crc0		srl	b
+		jr	nc,crclp1	; Byte fertig?
+		;
+		ld	bc,(arg2)
+		xor	a		; Cy -> 0
+		sbc	hl,bc
+		add	hl,bc
+		inc	hl
+		jr	nz,bytecrc	; fertig?
+		ex	de,hl		; CRC nach HL
+		ret
+arg2		ds	2
+		end
 </code>
@@ Zeile 95: / Zeile 165: @@
   * http://www.robotrontechnik.de/html/forum/thwb/showtopic.php?threadid=3846
-  * http://www.ac1-info.de/literatur/fa_86_11.htm
+  * http://www.ac1-info.de/literatur/fa_86_11.htm (Berechnung nach SDLC, mit Bit-Schieberegister)
+  * http://werner.dichler.at/sites/default/files/attachment/prj21_CRC%20Einfuehrung.pdf von Werner Dichler
+===== Hardware =====
+aus mc 1984/07
+CRC ist die Abkürzung für Cyclic Redundancy
+Check und so etwas ähnliches
+wie eine Prüfsumme, darf aber damit
+nicht verwechselt werden, da die Erzeugung
+des CRC aufwendiger ist. Dabei
+werden nicht einfach die einzelnen Bytes
+aufaddiert, sondern verschiedene
+Bits gemäß einem sogenannten Generator-
+Polynom. Es gibt dabei sehr unterschiedliche
+Vorschriften, jedoch verwendet
+man bei den gängigen Controllern
+das vom CCITT definierte Polynom.
+Es lautet G(x) = 1 + x^5 + x^12 + x^16.
+Daraus kann man eine Schaltung konstruieren,
+die etwa wie in Bild 16 aussieht.
+Ein Reset-Eingang sorgt dafür, daß
+das Schieberegister auf einen definierten
+Wert gesetzt werden kann. Dann werden
+der Eingang FREI auf 1 gelegt und zusammen
+mit einem Takt die Daten an E
+angelegt. Nach dem Ende des Datenstroms
+wird FREI auf 0 gelegt, und die
+CRC-Bytes können aus dem Register geschoben
+werden. Um nun einen Datenstrom
+zu testen, wird genauso wie vorher
+verfahren, nur daß nun auch die
+CRC-Bytes mitverrechnet werden. Das
+Ergebnis im Schieberegister muß anschließend
+sein.
+{{:cpm:crc-hardware.jpg|}}