Unterschiede
Hier werden die Unterschiede zwischen zwei Versionen angezeigt.
Nächste Überarbeitung | Vorhergehende Überarbeitung | ||
cpm:crc [2011/08/30 08:15] – angelegt volkerp | cpm:crc [2014/03/11 09:18] (aktuell) – volkerp | ||
---|---|---|---|
Zeile 1: | Zeile 1: | ||
====== CRC-Berechnung ====== | ====== CRC-Berechnung ====== | ||
- | In diversen U880-Programmen, | + | In diversen U880-Programmen, |
- | CRC-CCITT (CRC-16) | + | CRC-CCITT (CRC-16) |
- | s. Wikipedia. | + | s. [[http://de.wikipedia.org/ |
Als Startwert wird eigentlich immer 0FFFFh genommen. | Als Startwert wird eigentlich immer 0FFFFh genommen. | ||
- | In Assembler sieht die CRC-Routine wie folgt aus. | + | :!: In der DDR-Literatur liest man auch oft " |
- | < | + | 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. |
+ | |||
+ | < | ||
+ | $buf = ....; | ||
+ | $len = 2048; | ||
+ | |||
+ | #CRC-CCITT (CRC-16) x16 + x12 + x5 + 1 | ||
+ | $POLY = 0b_0001_0000_0010_0001; | ||
+ | # da nur mit 16 Bit gearbeitet wird | ||
+ | |||
+ | # | ||
+ | $crc16 = 0xFFFF; | ||
+ | |||
+ | for ($i=0; | ||
+ | my $byte = ord(substr($buf, | ||
+ | |||
+ | $byte = $byte * 0x100; | ||
+ | for (0..7) # 8 Bits pro Byte | ||
+ | { | ||
+ | if (($byte & 0x8000) ^ ($crc16 & 0x8000)) { | ||
+ | # wenn die Hi-Bits unterschiedlich sind, dann | ||
+ | $crc16 <<= 1; # shift left | ||
+ | $crc16 ^= $POLY; # XOR-Verknüpfung mit CRC-Poly | ||
+ | $crc16 &= 0xFFFF; # beschränken auf 16 Bit | ||
+ | } else { | ||
+ | # ansonsten nächstes Bit ohne Verküpfung | ||
+ | $crc16 <<= 1; # shift left | ||
+ | $crc16 &= 0xFFFF; # beschränken auf 16 Bit | ||
+ | } | ||
+ | $byte <<= 1; # shift left, nächstes Bit | ||
+ | $byte &= 0xFFFF; | ||
+ | } | ||
+ | } | ||
+ | |||
+ | # Ausgabe | ||
+ | printf "CRC = %.4X\n", | ||
+ | </ | ||
+ | |||
+ | Normalerweise werden CRC-Polynome mit reverser Bit-Reihenfolge berechnet; auch die einzelnen Bytes werden in umgekehrter Reihenfolge abgearbeitet. Und richtig optimal wird es erst mit vorbrechneten Tabellen... | ||
+ | |||
+ | In Assembler sieht die CRC-Routine wie folgt aus. Die Berechnung ist optimiert und erfolgt tetradenweise. (Der Code stammt aus der Z9001-EPROM-Software) | ||
+ | |||
+ | in: DE = Startadr., BC = Länge\\ | ||
+ | out: HL = CRC | ||
+ | |||
+ | <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: | crc: | ||
crc1: | crc1: | ||
Zeile 48: | Zeile 99: | ||
ret | ret | ||
</ | </ | ||
+ | |||
+ | 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, | ||
+ | ld l,e | ||
+ | dec bc | ||
+ | add hl,bc | ||
+ | ex hl,de | ||
+ | ld (arg2), | ||
+ | |||
+ | ; ab HL, bis (arg2), ret HL=CRC | ||
+ | crc_fa ld de, | ||
+ | bytecrc ld b, | ||
+ | crclp1 sla e ; | ||
+ | rl d | ||
+ | sbc a, | ||
+ | xor (hl) ; | ||
+ | and b | ||
+ | jr z,crc0 | ||
+ | ; | ||
+ | ld a,e | ||
+ | xor 21h ; | ||
+ | ld e,a | ||
+ | ld a,d | ||
+ | xor 10h ; | ||
+ | ld d,a | ||
+ | crc0 srl b | ||
+ | jr nc, | ||
+ | ; | ||
+ | ld bc, | ||
+ | xor a ; Cy -> 0 | ||
+ | sbc hl,bc | ||
+ | add hl,bc | ||
+ | inc hl | ||
+ | jr nz, | ||
+ | ex de, | ||
+ | ret | ||
+ | |||
+ | arg2 ds 2 | ||
+ | |||
+ | end | ||
+ | </ | ||
+ | |||
+ | s.a. | ||
+ | |||
+ | * http:// | ||
+ | * http:// | ||
+ | * http:// | ||
+ | |||
+ | ===== 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, | ||
+ | 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 | ||
+ | 0 sein. | ||
+ | |||
+ | {{: | ||
+ | |||