Robotrontechnik-Forum

Registrieren || Einloggen || Hilfe/FAQ || Suche || Mitglieder || Home || Statistik || Kalender || Admins

Willkommen Gast!

Robotrontechnik-Forum » Technische Diskussionen » Suche optimale Prüfsumme/Signatur (Z80) » Themenansicht

Autor

Thread - Seiten: -1-

000
17.05.2026, 14:13 Uhr
Bert

Hallo Forum!

Ich bin auf der Suche nach einer 'optimalen' Prüfsumme für den KC85.
Optimal bedeutet in diesem Fall:
(A) kurze Laufzeit
(B) eindeutige Signatur, auch bei Datenblöcken mit leerem Inhalt (alles FFs oder alles 0)
(C) ein gewisser Fehlerschutz vor fehlerhaften Bytes oder Burstfehlern
Die Codegröße ist nicht ganz so entscheidend.

Was ich mir schon angeschaut habe:

XOR
Vorteil: schnell (A)
Nachteil: keine eindeutige Signatur bei identischem Inhalt (B) und geringer Fehlerschutz (C)

SUM16
Vorteil: schnell (A)
Nachteil: geringer Fehlerschutz (C)

Fletcher-16
(die Variante mit a = 0, b = 0, M = 255)
Vorteil: guter Fehlerschutz (C und B)
Nachteil: nicht so schnell (A)

Fletcher-16
(die Variante mit a = 0, b = 0, M = 256)
Vorteil: ähnlich schnell wie SUM16 (A)
Nachteil: keine eindeutige Signatur (C)

Fletcher-KC
(die Variante mit a = data[0], b = 0, M = 256)
Vorteil: ähnlich schnell wie SUM16 (A)
Nachteil: kein Standard

Adler-16
(Variante von Fletcher mit a = 1, b = 0, M = 251)
Vorteil: eindeutige Signatur (C)
Nachteil: nur mittelschnell (A)

Alle Algorithmen laufen auf dem PC (C++) und dem KC85 (C und Assembler).

Die Assemblervariante ist i.d.R. fünf bis zehnmal schneller als die C-Variante:

Letztendlich bräuchte ich einen Algorithmus der den Rest der Division (=Modulo-Operation) mit 255 oder 251 schnell ausrechnet um von der Geschwindigkeit in die Nähe von SUM16 zu kommen.

Wer sich da mal angucken will, ich hab die Quelltexte (und mehr) hier abgelegt:
https://github.com/boert/KC85-Programme_in_C/tree/main/Pruefsummenvergleich

Vielleicht hat ja noch jemand eine gute Idee!
--
Viele Grüße,
Bert

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

001
17.05.2026, 17:01 Uhr
maleuma

Ich habe in meinem Flash-Programm für CAOS eine modifizierte Fletcher-Routine eingebaut.
Da die Original-Fletcher-Routine für alles 0 und alles FF das gleiche Ergebnis liefert, habe ich statt ADD einfach den Z80-Befehl ADC genommen. Damit ist die Routine genauso schnell, liefert jedoch unterschiedliche Werte bei 00 und FF.
Nachteil: kein Standard und schlechter am PC nachbildbar.

Quellcode:


; Fletcher-Pruefsumme berechnen:
; PE:   HL      Anfangsadresse
;       (PAR1)  Adresse zur Ablage der CRC-Summe
; PA:   DE      CRC
CRCC:   LD      HL,0C000H       ; Anfangsadresse
CRC:    LD      BC,2000H        ; Laenge immer 8 KByte
        LD      DE,'KC'         ; Startwert
; Adjust 16-bit length for 2x8-bit loops
        inc     b               ; BC = 2100H
        dec     bc              ; BC = 20FFH
        inc     c               ; BC = 2000H          Takte:
FLLOOP: ld      a,(hl)          ;                       7
        inc     hl              ;                       6
        add     a,e             ; sum1 += data          4
        ld      e,a             ;                       4
        adc     a,d             ; sum2 += sum1 + cy     4
        ld      d,a             ;                       4
        dec     c               ;                       4
        jp      nz,FLLOOP       ;                       10
        djnz    FLLOOP          ;                       13 (8)

--
Mario.

Dieser Beitrag wurde am 17.05.2026 um 20:33 Uhr von maleuma editiert.

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

002
17.05.2026, 20:19 Uhr
Bert

Das ADC statt ADD bringt an der Stelle leider nicht viel.
Wenn man die Startwerte wieder auf '0' setzt, entspricht das Ergebnis dem SUM16-Algorithmus.
--
Viele Grüße,
Bert

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

003
17.05.2026, 21:12 Uhr
maleuma

Ich habe den SUM16-Algorithmus einmal bei mir eingebaut. Ich bekomme aber andere Ergebnisse als bei meinem Fletcher-ADC. Sowohl mit Startwert "KC" als auch mit Startwert 0.

Bei SUM16 wird bei einem Übertrag der H-Teil nur incrementiert.
Bei Fletcher wird im H-Teil die komplette Summe des Low-Teils aufsummiert.
Oder habe ich das falsch verstanden?
--
Mario.

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

004
17.05.2026, 23:59 Uhr
kaiOr

Alles ein wenig zusammenstampfen geht doch immer.

Quellcode:

;;  (lightly unflexible) Fletcher-16 checksum, mod 255
;;
;; Input:
;;  H = Data address / 100h
;;  B = Data length / 100h
;;
;; Output:
;;  DE = Fletcher-16
;;  HL,BC,AF are modified
fletcher_255:
        ld      a,b
        add     a,h
        ld      b,a
        ld      l,0
        ld      c,l             ; mobile Null
        ld      d,c             ; Start-
        ld      e,c             ; wert
fletcher16_loop:
        ld      a,e
        add     a,(hl)
        adc     a,c
        ld      e,a
        add     a,d
        adc     a,c
        ld      d,a
        inc     l
;; 1x loop unrolling, no problem because L starts even
        ld      a,e
        add     a,(hl)
        adc     a,c
        ld      e,a
        add     a,d
        adc     a,c
        ld      d,a
        inc     l
        jp      nz,fletcher16_loop
        inc     h
        ld      a,h
        cp      b
        jp      nz,fletcher16_loop

        ; d = d mod 255
        dec     l
        ld      a,d
        cp      l
        jr      c,$+3
        inc     d
        ; e = e mod 255
        ld      a,e
        cp      l
        jr      c,$+3
        inc     e

        ret

ca. 186ms

EDIT2: Daten vom Stack holen geht noch einen Hauch schneller:

Quellcode:

;;  (lightly unflexible) Fletcher-16 checksum, mod 255
;;
;; Input:
;;  H = Data address / 100h
;;  B = Data length / 100h
;;
;; Output:
;;  DE = Fletcher-16
;;  HL,BC,AF are modified
spos    equ     0B77Eh          ; freier RAM
cnt     equ     spos-1
fletcher_255:
        xor     a               ; clear CY
        ld      c,a             ; mobile Null
        ld      a,b
        rra
        ld      b,c
        jr      nc,skip         ; gerade?
        ld      b,128
        inc     a
skip    ld      (cnt),a
        ld      l,c
        ld      d,c             ; Start-
        ld      e,c             ; wert
        di
        ld      (spos),sp
        ld      sp,hl
fletcher16_loop:
        pop     hl
        ld      a,e
        add     a,l
        adc     a,c
        ld      e,a
        add     a,d
        adc     a,c
        ld      d,a
        ld      a,e
        add     a,h
        adc     a,c
        ld      e,a
        add     a,d
        adc     a,c
        ld      d,a
        djnz    fletcher16_loop
        ld      hl,cnt
        dec     (hl)
        jp      nz,fletcher16_loop
        ld      sp,(spos)
        ei

        ; d = d mod 255
        dec     b
        ld      a,d
        cp      b
        jr      c,$+3
        inc     d
        ; e = e mod 255
        ld      a,e
        cp      b
        jr      c,$+3
        inc     e

        ret

ca. 183ms

Gruß,
Kai

Dieser Beitrag wurde am 18.05.2026 um 11:58 Uhr von kaiOr editiert.

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

005
19.05.2026, 12:13 Uhr
Bert

Die beiden Fletcher-Varianten (M=255 und M=256) haben den Nachteil für die Länge von 8k keine eindeutige Signatur zu liefern:

Zitat:

00 00 00 ... 00 Länge 8192 Adler-16 A001 fletcher 255 0000 fletcher 256 0000 fletcher ADC 0000 sum16 0000
01 01 01 ... 01 Länge 8192 Adler-16 EFA1 fletcher 255 1220 fletcher 256 0000 fletcher ADC 2000 sum16 2000
02 02 02 ... 02 Länge 8192 Adler-16 4346 fletcher 255 2440 fletcher 256 0000 fletcher ADC 4000 sum16 4000
0F 0F 0F ... 0F Länge 8192 Adler-16 5A8E fletcher 255 0FE1 fletcher 256 0000 fletcher ADC E000 sum16 E000
1F 1F 1F ... 1F Länge 8192 Adler-16 63C0 fletcher 255 30E3 fletcher 256 0000 fletcher ADC E000 sum16 E000
20 20 20 ... 20 Länge 8192 Adler-16 B265 fletcher 255 4204 fletcher 256 0000 fletcher ADC 0000 sum16 0000
55 55 55 ... 55 Länge 8192 Adler-16 622F fletcher 255 00AA fletcher 256 0000 fletcher ADC A000 sum16 A000
7F 7F 7F ... 7F Länge 8192 Adler-16 99F1 fletcher 255 F6EF fletcher 256 0000 fletcher ADC E000 sum16 E000
80 80 80 ... 80 Länge 8192 Adler-16 E896 fletcher 255 0910 fletcher 256 0000 fletcher ADC 0000 sum16 0000
FF FF FF ... FF Länge 8192 Adler-16 E18B fletcher 255 0000 fletcher 256 0000 fletcher ADC E000 sum16 E000

Bei Fletcher-16 mit Modulo 255 gibt es nur bei '00' und 'FF' ein Problem. Bei Fletcher-16 mit Modulo 256 kommt aufgrund der Länge des Datenblocks überall '0000' als Signatur.
Also die unveränderten Fletcher-Checksums sind für meine Anwendung ungeeignet.
Für z.B. kürzere Datenblöcke (<255 Bytes) sollten die aber gut gehen:

Zitat:

00 00 00 ... 00 Länge 254 Adler-16 0301 fletcher 255 0000 fletcher 256 0000
01 01 01 ... 01 Länge 254 Adler-16 0904 fletcher 255 00FE fletcher 256 81FE
02 02 02 ... 02 Länge 254 Adler-16 0F07 fletcher 255 00FD fletcher 256 02FC
0F 0F 0F ... 0F Länge 254 Adler-16 5D2E fletcher 255 00F0 fletcher 256 8FE2
1F 1F 1F ... 1F Länge 254 Adler-16 BD5E fletcher 255 00E0 fletcher 256 9FC2
20 20 20 ... 20 Länge 254 Adler-16 C361 fletcher 255 00DF fletcher 256 20C0
55 55 55 ... 55 Länge 254 Adler-16 0B05 fletcher 255 00AA fletcher 256 D556
7F 7F 7F ... 7F Länge 254 Adler-16 0C83 fletcher 255 0080 fletcher 256 FF02
80 80 80 ... 80 Länge 254 Adler-16 1286 fletcher 255 007F fletcher 256 8000
FF FF FF ... FF Länge 254 Adler-16 1B0D fletcher 255 0000 fletcher 256 7F02

--
Viele Grüße,
Bert

Dieser Beitrag wurde am 19.05.2026 um 12:14 Uhr von Bert editiert.

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

006
19.05.2026, 12:24 Uhr
Bert

@Mario:

Ich habe den Fletcher mit Modulo=256 und ADC statt ADD so am PC nachgebildet:

Quellcode:


uint16_t calc_fsum_adc( const std::vector<uint8_t>& data)
{
    uint16_t  a = 0;
    uint8_t   b = 0;

    for( uint16_t index = 0; index < data.size(); index++)
    {
        a = a + data[ index];
        if( a > 255)
        {
            a = a - 256;
            b = b + a + 1;      // mit carry
        }
        else
        {
            b = b + a;
        }
    }
    return(( (uint16_t) b << 8) | a);
}

Damit erhalte ich die folgenden Ergebnisse:

Zitat:

00 00 00 ... 00 Länge 8192 Adler-16 A001 fletcher ADC 0000 sum16 0000
01 01 01 ... 01 Länge 8192 Adler-16 EFA1 fletcher ADC 2000 sum16 2000
02 02 02 ... 02 Länge 8192 Adler-16 4346 fletcher ADC 4000 sum16 4000
0F 0F 0F ... 0F Länge 8192 Adler-16 5A8E fletcher ADC E000 sum16 E000
1F 1F 1F ... 1F Länge 8192 Adler-16 63C0 fletcher ADC E000 sum16 E000
20 20 20 ... 20 Länge 8192 Adler-16 B265 fletcher ADC 0000 sum16 0000
55 55 55 ... 55 Länge 8192 Adler-16 622F fletcher ADC A000 sum16 A000
7F 7F 7F ... 7F Länge 8192 Adler-16 99F1 fletcher ADC E000 sum16 E000
80 80 80 ... 80 Länge 8192 Adler-16 E896 fletcher ADC 0000 sum16 0000
FF FF FF ... FF Länge 8192 Adler-16 E18B fletcher ADC E000 sum16 E000

Vielleicht rechne ich ja falsch, aber für mich sieht das so aus, wie SUM16.
Das gilt aber nur für den Sonderfall, das alle Eingangswerte identisch sind.

Bei Zufallszahlen als Eingabe passt alles:

Zitat:

F4 EE D4 ... 88 Länge 8192 Adler-16 F423 fletcher ADC 868E sum16 318E
2C 2C 78 ... DB Länge 8192 Adler-16 B3EA fletcher ADC DE6D sum16 FB6D
08 38 F5 ... 94 Länge 8192 Adler-16 2C41 fletcher ADC 1104 sum16 BC04
C6 95 67 ... 46 Länge 8192 Adler-16 08B2 fletcher ADC 1C67 sum16 F167
4D 19 D0 ... 1F Länge 8192 Adler-16 4AEF fletcher ADC D5CC sum16 E9CC
63 C5 EC ... 55 Länge 8192 Adler-16 59E1 fletcher ADC A42C sum16 D42C
EA D9 A6 ... FD Länge 8192 Adler-16 C779 fletcher ADC 83F7 sum16 FBF7
0A 95 BE ... 3E Länge 8192 Adler-16 198B fletcher ADC 9F90 sum16 E190
69 D9 81 ... 06 Länge 8192 Adler-16 236C fletcher ADC C680 sum16 DE80
B5 17 B8 ... E6 Länge 8192 Adler-16 02D5 fletcher ADC 1EE4 sum16 DFE4

--
Viele Grüße,
Bert

Dieser Beitrag wurde am 19.05.2026 um 12:29 Uhr von Bert editiert.

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

007
19.05.2026, 12:34 Uhr
Bert

@kaiOr:
Danke für Deine Anregungen!
Letztendlich wird nicht die Berechnung optimiert, sondern die Schleife. Nachteil der Optimierung ist das Ausrichtung der Daten (Alignment) und die Länge des Datenblocks.
Da muß ich mir noch überlegen, ob ich diese Nachteile in Kauf nehmen kann.
Trotzdem eine gute Idee!
Die Laufzeit kann ich bestätigen.

Die Idee mit dem Stack kann ich leider so nicht umsetzen. Das beißt sich mit meiner Laufzeitmessung über CTC Kanal 2 und Interrupt-Routine.
Aber der Vorteil ist ja auch überschaubar.
--
Viele Grüße,
Bert

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

008
21.05.2026, 21:17 Uhr
Sisyphos

Hallo Forum,

in den historischen Archiver-Programmen ZOO von Rahul Dhesi und LHA von Haruyasu Yoshizaki werden auch Prüfsummen für die zu archivierenden Dateien berechnet. Die Entwickler haben sich vermutlich die gleichen Gedanken über Prüfsummen gemacht wie wir und haben CRC gewählt. Ich habe im Jahr 2002 den Quellcode "gestohlen" und zu einem einfachen CRC Utility verarbeitet. Es gibt CRC als 16-Bit und als 32-Bit Variante. Das Utility einschließlich der Quellen ist hier zum Download:

https://c.gmx.net/%40329524413705750303/M77D8HnhXF4mshNgfu7QJA

Ich habe es 2002 schon für MS-DOS und Windows 32-bit portiert. Wenn Interesse besteht, würde ich versuchen, es für CP/M 2.2 zu portieren. Ich habe hier Aztec-C und HI-TECH-C zur Verfügung. Würde das auf einem KC 85 laufen? Geht es überhaupt um Prüfsummen für Dateien oder um etwas ganz anderes?

LG, Sisyphos.

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

009
21.05.2026, 21:38 Uhr
Sisyphos

Und ich sehe gerade, dass in Robert Jungs ARJ und Phil Katzs PKZIP auch CRC Prüfsummen berechnet wurden. LG, Sisyphos.

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

010
21.05.2026, 21:43 Uhr
maleuma

Es geht hier um Programmcode für CAOS, CP/M 2.2-Programmcode ist unter CAOS nicht ausführbar. Die reine CRC-Berechnung ist ja unabhängig vom Betriebssystem, nur die Anzeigeroutinen müssten umgeschrieben werden. Hier nochmals zum Vergleich mit 000 einige Zeiten, welche mit verschiedenen Routinen ermittelt wurden:

Die Summen in roter Schrift zeigen, dass das Ergebnis bei alles mit 00 identisch ist wie bei FF - also keine zuverlässige Erkennung dieser beiden Zustände.
CRC16 ist vermutlich schon die sicherste Methode und in meinem Screenshot decken sich auch die Zeiten mit um die 860ms für 8KByte.
Mit etwas über 200ms ist die Fletcher-Summe ca. 4x schneller und mit der ADC-Variante nach 001 lässt sich auch 00h und FFh unterscheiden.
--
Mario.

Dieser Beitrag wurde am 21.05.2026 um 21:44 Uhr von maleuma editiert.

Profil || Private Nachricht || Suche

Zitatantwort || Editieren || Löschen

Seiten: -1- [ Technische Diskussionen ]