OldComp.cz • Zobrazit téma - XOR (cyklický redundantní součet)

Vyhledat témata bez odpovědí | Zobrazit aktivní témata

Obsah fóra » ZX Spectrum, Sinclair a kompatibilní » ZX Spectrum - programování a vývoj software

Všechny časy jsou v UTC + 1 hodina [ Letní čas ]

XOR (cyklický redundantní součet)

Moderátoři: Jiiira, SCjoe

Stránka 3 z 4

[ Příspěvků: 56 ]

Přejít na stránku Předchozí 1, 2, 3, 4 Další

Verze pro tisk

Předchozí téma | Následující téma

Autor

Zpráva

dex

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 28.05.2020, 21:11

Pan Štábní

Registrován: 12.05.2013, 22:24
Příspěvky: 1316
Bydliště: u Prahy
Has thanked: 39 times
Been thanked: 326 times

Když bude XXX mimo xorovaná data, nebude kontrolovat svou vlastní správnost.

Nahoru

EC1045.01

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 10:27

Profík

Registrován: 15.01.2014, 20:08
Příspěvky: 652
Bydliště: Šlapanice
Has thanked: 96 times
Been thanked: 77 times

Omlouvám se, že tu budu trochu čeřit hladinu.

Toto téma mi přijde dost zajímavé tak jsem zkusil ten postup, co uvedl Panda38 na výpočet (polynomu) CRC co je vhodný i pro 8 bity převést na instrukce 8080A. Jen u toho posledního řádku si nejsem jist, jestli jsem ho pochopil správně.

Kód:

   TYTLE POLINOM CRC

;PSANO V ASM 8080A A SE SINTAXI PRO MACROASEBLER POD CP/M
;PROGRAMEK VA VYPOCET CRC

;POCATECNI KONSTANTY PRO KONKRETNI PROTOKOLY
XMODEM   EQU   0
CCITT   EQU   -1
CCITTB   EQU   1D0FH

;V <HL> ADRESA DAT
;V <DE> JE CRC
;JEN VLASTNI PROGRAM PRO PRIDANI JEDNOHO BYTE

;crc = (crc >> 8) | (crc << 8);   .... prohodí vyšší a nižší bajt CRC
   MOV   A,E
   MOV   E,D
   MOV   D,A

;crc ^= data;               .... provede XOR nižšího bajtu CRC s datovým bajtem
   MOV   A,M
   XRA   E

;crc ^= (crc & 0xff) >> 4;         ... provede XOR nižšího bajtu CRC se sebou samým rotovaným 4x vpravo
   RRC
   RRC
   RRC
   RRC
   XRA   E
   MOV   E,A

;crc ^= crc << 12;            ... provede XOR vyššího bajtu CRC se sebou samým rotovaným 4x vlevo
   MOV   A,D
   RLC
   RLC
   RLC
   RLC
   XRA   D
   MOV   D,A

;crc ^= (crc & 0xff) << 5;         ... provede XOR CRC (dvojregistr) s nižším bajtem rotovaným 5x vlevo
;TADY SI NEJSEM JIST ZDA JSEM TO POCHOPIL SPRAVNE
   MOV   A,E
   RLC
   RLC
   RLC
   RLC
   RLC
   MOV   B,A
   XRA   E
   MOV   E,A
   MOV   A,D
   XRA   B
   MOV   D,A

   END

Pokut jde o opravy dat u dat kdy je zajištění provedeno pomoci XOR např. u pole 16x16 dat 17x17 včetně XOR. Nejprve se spočítají znovu kontrolní XOR pro řádky a sloupce a z toho se zjistí kde je konkrétně chyba. Pokut bude v daném řádku nebo sloupci jen jedna chyba tak půjde opravit, aneb se špatný byte „zahodí“ a z těch ostatních se počítá vadný byte, tj. pokut jsem pochopil správně tak pro zjednodušení algoritmu by mělo stačit nahradit vadný byte sousedním byte. Spočítat XOR pro celí řádek/sloupec (včetně kontrolního XOR) a to co zbude je onen správný byte který se pak dosadí na místo toho vadného. Při správné konstataci půjde zrekonstruovat až 34 chyb. Tedy v poli 16x16 dat 17x17 včetně XOR.

Něco podobného určitě půjde i pro ten CRC ale ta „matematika“ okolo rekonstrukce bude řadově složitější, ale taky by si to mělo poradit s daleko větším poškozením dat.

_________________
Ne všichni jsme měli z češtiny za jedna, aneb jsem dyslektik a dysgrafik.

http://www.sapi.cz/

Nahoru

Panda38

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 14:35

Pan Štábní

Registrován: 24.05.2018, 22:32
Příspěvky: 1661
Bydliště: Most, Praha
Has thanked: 627 times
Been thanked: 546 times

Omlouvám se za nesprávně použité slovo, psal jsem "rotace", ale je tím myšlen bitový posun (C značky >> a <<). Tj. do vstupního bitu jde "0". Z toho pohledu je tento kód bohužel špatně. :-(

Když tak můžu zkusit navrhnout opravy, ale už nejsem v 8080 kódu moc zběhlý.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement

Nahoru

EC1045.01

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 15:03

Profík

Registrován: 15.01.2014, 20:08
Příspěvky: 652
Bydliště: Šlapanice
Has thanked: 96 times
Been thanked: 77 times

U posuv vpravo jsem nechal jako rotaci ale jen se umazli nejvyšší 4 bity. U posuvu vlevo je použito sčítaní, což samo se sebou je vlastně násobení a tím dochází k posuvu. Takže teď by to mělo být správně ? Samozřejmě ten kód půjde zoptimalizovat, ale pro začátek se chci držet těch kroku.

Kód:

   TYTLE POLINOM CRC

;PSANO V ASM 8080A A SE SINTAXI PRO MACROASEBLER POD CP/M
;PROGRAMEK VA VYPOCET CRC

;POCATECNI KONSTANTY PRO KONKRETNI PROTOKOLY
XMODEM   EQU   0
CCITT   EQU   -1
CCITTB   EQU   1D0FH

;V <HL> ADRESA DAT
;V <DE> JE CRC
;JEN VLASTNI PROGRAM PRO PRIDANI JEDNOHO BYTE

;crc = (crc >> 8) | (crc << 8);   .... prohodí vyšší a nižší bajt CRC
   MOV   A,E
   MOV   E,D
   MOV   D,A

;crc ^= data;               .... provede XOR nižšího bajtu CRC s datovým bajtem
   MOV   A,M
   XRA   E

;crc ^= (crc & 0xff) >> 4;         ... provede XOR nižšího bajtu CRC se sebou samým rotovaným 4x vpravo
   RRC
   RRC
   RRC
   RRC
   ANI   0FH   ;JEN SPODNI 4 BYTI
   XRA   E
   MOV   E,A

;crc ^= crc << 12;            ... provede XOR vyššího bajtu CRC se sebou samým rotovaným 4x vlevo
   MOV   A,D
   ADD   A
   ADD   A
   ADD   A
   ADD   A   ;POSUV O 4 BYTY VLEVO
   XRA   D
   MOV   D,A

;crc ^= (crc & 0xff) << 5;         ... provede XOR CRC (dvojregistr) s nižším bajtem rotovaným 5x vlevo
;TADY SI NEJSEM JIST ZDA JSEM TO POCHOPIL SPRAVNE
   MOV   A,E
   ADD   A
   ADD   A
   ADD   A
   ADD   A
   ADD   A   ;POSUV O 5 BYTU VLEVO
   MOV   B,A
   XRA   E
   MOV   E,A
   MOV   A,D
   XRA   B
   MOV   D,A

   END

_________________
Ne všichni jsme měli z češtiny za jedna, aneb jsem dyslektik a dysgrafik.

http://www.sapi.cz/

Nahoru

Panda38

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 16:08

Pan Štábní

Registrován: 24.05.2018, 22:32
Příspěvky: 1661
Bydliště: Most, Praha
Has thanked: 627 times
Been thanked: 546 times

Ještě nějaké chyby, zkusil jsem opravit. Ale nezaručeno, nemám jak vyzkoušet. Je potřeba ještě vyzkoušet na kontrolních vzorkách.

Kód:

   TITLE POLYNOM CRC

;PSANO V ASM 8080A A SE SYNTAXI PRO MACROASSEMBLER POD CP/M
;PROGRAMEK NA VYPOCET CRC

;POCATECNI KONSTANTY PRO KONKRETNI PROTOKOLY
XMODEM   EQU   0
CCITT   EQU   -1
CCITTB   EQU   1D0FH

;V <HL> ADRESA DAT
;V <DE> JE CRC
;JEN VLASTNI PROGRAM PRO PRIDANI JEDNOHO BYTE

;crc = (crc >> 8) | (crc << 8);   .... prohodi vyssi a nizsi bajt CRC
   MOV   A,E
   MOV   E,D
   MOV   D,A

;crc ^= data;               .... provede XOR nizsiho bajtu CRC s datovym bajtem
   MOV   A,M
   XRA   E
   MOV   E,A

;crc ^= (crc & 0xff) >> 4;         ... provede XOR nizsiho bajtu CRC se sebou samym posunutym 4x vpravo
   RRC
   RRC
   RRC
   RRC   ;POSUV O 4 BITY VPRAVO
   ANI   0FH   ;JEN SPODNI 4 BITY
   XRA   E
   MOV   E,A

;crc ^= crc << 12;            ... provede XOR vyssiho bajtu CRC s nizsim bajtem posunutym 4x vlevo
   MOV   A,E
   ADD   A
   ADD   A
   ADD   A
   ADD   A   ;POSUV O 4 BITY VLEVO
   XRA   D
   MOV   D,A

;crc ^= (crc & 0xff) << 5;         ... provede XOR CRC (dvojregistr) s nizsim bajtem posunutym 5x vlevo
   MOV   A,E
   RRC
   RRC
   RRC   ;POSUV O 3 BITY VPRAVO
   ANI   1FH   ;JEN SPODNICH 5 BITU
   XRA   D
   MOV   D,A

   MOV   A,E
   ADD   A
   ADD   A
   ADD   A
   ADD   A
   ADD   A   ;POSUV O 5 BITU VLEVO
   XRA   E
   MOV   E,A

   END

Kontrolní vzorky:
- pro XModem: ASCII text "123456789" -> 0x31C3, hex 0xFC 0x05 0x4A -> 0x8048
- pro CCITT: ASCII text "123456789" -> 0x29B1, hex 0xFC 0x05 0x4A -> 0x4CD4
- pro CCITT-B: ASCII text "123456789" -> 0xE5CC, hex 0xFC 0x05 0x4A -> 0x9144

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement

Nahoru

Busy

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 17:17

Pan Generální

Registrován: 22.05.2013, 21:14
Příspěvky: 3386
Bydliště: Bratislava
Has thanked: 351 times
Been thanked: 707 times

Panda38 píše:

Když tak můžu zkusit navrhnout opravy, ale už nejsem v 8080 kódu moc zběhlý.

Preto ja vsetky asemblerove programy pisem zasadne v Z80 mnemotechnike. Pre tych, ktori by sa bali ze sa im "presmykne" nejaka Z80 instrukcia ktoru 8080 nema, tak napr. sjasmplus umoznuje pouzit prepinas -i8080 pri ktorom oznaci taketo instrukcie za chybne.

Nahoru

EC1045.01

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 18:26

Profík

Registrován: 15.01.2014, 20:08
Příspěvky: 652
Bydliště: Šlapanice
Has thanked: 96 times
Been thanked: 77 times

Tak jsem to upravil, aby se to dalo spustit pod CP/M a vyšli následující výsledky:

XMODEM = 31C3H
CCITT = 29B1H
CCITT-B = E5CCH

Takže to vypadá, že by to mělo fungovat.

Mně jaksi mnemonika Z80 nesedí, aneb furt je tam LD jo vím, že víc jak půlka instrukcí je o stehování něčeho někam … mnemonika 8080 je proste pestřejší.

Přílohy:

Poznámka: Zdrojový kód

CRC.rar [4.27 KiB]
391 krát

_________________
Ne všichni jsme měli z češtiny za jedna, aneb jsem dyslektik a dysgrafik.

http://www.sapi.cz/

Nahoru

Panda38

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 18:45

Pan Štábní

Registrován: 24.05.2018, 22:32
Příspěvky: 1661
Bydliště: Most, Praha
Has thanked: 627 times
Been thanked: 546 times

Na případné kontroly se dá použít online CRC kalkulátor. Tady je přednastavený testovací vzorek "123456789" a na záložce CRC-16 jsou výsledky pro CRC-16/XMODEM (init=0x0000), CRC-16/CCITT-FALSE (init=0xFFFF) a CRC-16/AUG-CCITT (init=0x1D0F). https://crccalc.com/

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement

Nahoru

EC1045.01

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 18:48

Profík

Registrován: 15.01.2014, 20:08
Příspěvky: 652
Bydliště: Šlapanice
Has thanked: 96 times
Been thanked: 77 times

Ještě dodatek
Pro tu druhou sadu to vyšlo taky správně

XMODEM = 8048H
CCITT = 4CD4H
CCITT-B = 9144H

Jak by vypadal algoritmus, co by se pokoušel opravit chybu či detekce kde došlo k chybě?

Přílohy:

Poznámka: Zdrojový kód

CRC.rar [4.75 KiB]
374 krát

_________________
Ne všichni jsme měli z češtiny za jedna, aneb jsem dyslektik a dysgrafik.

http://www.sapi.cz/

Nahoru

lukz

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 19:00

Kecálek

Registrován: 28.10.2016, 21:03
Příspěvky: 120
Has thanked: 13 times
Been thanked: 50 times

Chtěl jsem si taky vyzkoušet implementaci tohohle CRC algoritmu. Ale z toho popisu tady mi nebylo moc jasné, jak to funguje, tak jsem hledal nějaké zdroje, a pro mě srozumitelnější popis programu jsem nakonec našel na
https://www.ccsinfo.com/forum/viewtopic.php?t=24977 .

A když jsem to pochopil, tak jsem se vrátil k tomu, co proběhlo tady, a po porovnání myslím, že je to úplně to samé. Zkusil jsem si to tedy také převést na i8080 assembler, třeba se to bude hodit jako alternativní verze. Napadlo mě vícekrát využít některé společné podvýrazy, což by mělo pomoci ke kratšímu kódu.

https://gist.githubusercontent.com/lukq ... ci8080.asm

Nahoru

Panda38

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 19:21

Pan Štábní

Registrován: 24.05.2018, 22:32
Příspěvky: 1661
Bydliště: Most, Praha
Has thanked: 627 times
Been thanked: 546 times

Samooprava: nejjednodušší metoda je rozdělit data na několik bloků, např. 10, k nim se přidá 11. blok který bude XORem předešlých 10 bloků (tedy redundance bude 10%). Každý blok je zajištěný CRC. Když se některý z bloků detekuje jako vadný, vypočte se XORováním ze zbylých 10 bloků (včetně paritního). Tímto způsobem se dá rekonstruovat 1 z 10 bloků.

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement

Nahoru

PotPalo

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 20:11

Pan Štábní

Registrován: 01.12.2017, 21:01
Příspěvky: 1770
Bydliště: BA-Petržalka :(
Has thanked: 17 times
Been thanked: 279 times

A keď sa poškodia dva naraz, je to v háji.

Nahoru

EC1045.01

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 21:14

Profík

Registrován: 15.01.2014, 20:08
Příspěvky: 652
Bydliště: Šlapanice
Has thanked: 96 times
Been thanked: 77 times

Tak jsem spočítal, kolik strojových cyklů zabere jeden průchod pro výpočet CRC a pro 8080 je to 160 pro 8085 a Z80 to je 149. Při 2MHz to bude 80us a 74.5us. Skok do programu a návrat z něj zabere 4 byty a 27 (8080A/Z80) nebo 28 (8085) strojových cyklů tj. 13.5us nebo 14us

Přenos jednoho byte pomocí UART při 9600 baud 8bit a 1 stop a start bitu trvá cca 1.04mS pro 19200 baud to je cca 521us a pro 38400 baud to je cca 260us takže ta rutina pro vypočet CRC je vhodné napsat spíše tak aby byla co nejrychlejší než aby byla co nejkratší.

Aby byl přenos více zabezpečen tak to by spíš chtělo to křížové XOR např. pro 16x16 dat a ten CRC pro každý klok tj. 17x pak by se dalo opravit daleko více chyb, jenže redundance by byla dost vysoká.

Pout si to pamatuji dobře tak u CD je na 1024 byte dat 288 bytu na opravy a tam se dá opravit hodně jenže to by 8bit stroj počítal neúměrně dlouho. To co tu řešíme je spíše pro odchytnutí chyb při přenosu dat aneb jen ta základní technika pro rekonstrukci dat.

Ale zajímavá debata.

_________________
Ne všichni jsme měli z češtiny za jedna, aneb jsem dyslektik a dysgrafik.

http://www.sapi.cz/

Nahoru

Panda38

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 22:59

Pan Štábní

Registrován: 24.05.2018, 22:32
Příspěvky: 1661
Bydliště: Most, Praha
Has thanked: 627 times
Been thanked: 546 times

Chyby v komunikaci by se měly řešit spíš komunikačním protokolem - hlídat pakety pomocí CRC a v případě chyby si vyžádat opakování paketu. Tam by error correction byl nepraktický - buď by to jelo spolehlivě a nadbytečnost by to zbytečně zpomalovala, nebo by bylo tak chybné že to samoopravy neopraví. Číslovat pakety a když se posloupnost přeruší nebo je chyba CRC, tak zažádat protistranu o opakování od toho čísla, příp. po více chybách resetovat spojení a navázat komunikaci od začátku. V jednodušším případě vysílač jen čeká na potvrzení každého paketu ACK nebo NAK (nebo time-out a opakování).

_________________
i++ (INC) increment
i-- (DEC) decrement
i@@ (EXC) excrement

Nahoru

_dworkin

Předmět příspěvku: Re: XOR (cyklický redundantní součet)

Napsal: 14.06.2020, 23:42

Profík

Registrován: 23.06.2013, 23:49
Příspěvky: 893
Has thanked: 74 times
Been thanked: 136 times

EC1045.01 píše:

Neovereno, ale pro Z80 me vychazi rychlost 116 taktu (nebo 117).

Kód:

    ld   A,(HL)     ; 1:7
    xor  D          ; 1:4
    ld   C, A       ; 1:4   x = ((old_crc>>8) ^ data) & 0xff;
    rrca            ; 1:4
    rrca            ; 1:4
    rrca            ; 1:4
    rrca            ; 1:4
    and  0x0F       ; 2:7
    xor  C          ; 1:4
    ld   C, A       ; 1:4   x ^= x>>4
                    ;11:46

Spodni cast jsem provedl dvema zpusoby, tak je snad aspon jeden spravne.

Kód:

    rrca            ; 1:4
    rrca            ; 1:4
    rrca            ; 1:4
    ld   C, A       ; 1:4
    rrca            ; 1:4
    and  0xF0       ; 2:7   1111 0000
    xor  D          ; 1:4
    ld   B, A       ; 1:4   crc_hi = (old_crc << 8) ^ (x << 12)

    xor  D          ; 1:4
    add  A, A       ; 1:4   1110 0000
    xor  E          ; 1:4
    ld   E, A       ; 1:4   crc_lo = (x << 5) ^ x
    
    ld   A, C       ; 1:4
    and  0x1F       ; 2:7   0001 1111
    xor  B          ; 1:4
    ld   D, A       ; 1:4   crc_hi = (old_crc << 8) ^ (x << 12) ^ (x << 5)
                    ;18:70

Kód:

    add  A, A       ; 1:4
    add  A, A       ; 1:4
    add  A, A       ; 1:4
    add  A, A       ; 1:4   1111 0000
    xor  D          ; 1:4
    ld   B, A       ; 1:4   crc_hi = (old_crc << 8) ^ (x << 12)

    xor  D          ; 1:4
    add  A, A       ; 1:4   1110 0000
    xor  E          ; 1:4
    ld   E, A       ; 1:4   crc_lo = (x << 5) ^ x

    ld   A, C       ; 1:4
    rrca            ; 1:4
    rrca            ; 1:4
    rrca            ; 1:4
    and  0x1F       ; 2:7   0001 1111
    xor  B          ; 1:4
    ld   D, A       ; 1:4   crc_hi = (old_crc << 8) ^ (x << 12) ^ (x << 5)
                    ;18:71

Nahoru

Stránka 3 z 4

[ Příspěvků: 56 ]

Přejít na stránku Předchozí 1, 2, 3, 4 Další

Obsah fóra » ZX Spectrum, Sinclair a kompatibilní » ZX Spectrum - programování a vývoj software

Všechny časy jsou v UTC + 1 hodina [ Letní čas ]

Kdo je online

Uživatelé procházející toto fórum: Žádní registrovaní uživatelé a 1 návštěvník

Nemůžete zakládat nová témata v tomto fóru
Nemůžete odpovídat v tomto fóru
Nemůžete upravovat své příspěvky v tomto fóru
Nemůžete mazat své příspěvky v tomto fóru
Nemůžete přikládat soubory v tomto fóru

Přejít na: