OldComp.cz

Komunitní diskuzní fórum pro fanoušky historických počítačů


Právě je 28.03.2024, 18:39

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




Odeslat nové téma Odpovědět na téma  [ Příspěvků: 56 ]  Přejít na stránku 1, 2, 3, 4  Další
Autor Zpráva
 Předmět příspěvku: XOR (cyklický redundantní součet)
PříspěvekNapsal: 27.05.2020, 08:43 
Offline
Kecálek

Registrován: 06.04.2020, 16:24
Příspěvky: 222
Bydliště: Opava
Has thanked: 31 times
Been thanked: 70 times
Chtěl bych si zde podělit o dvě (pro mne jako samouka zajímavé) věci, na které jsem v souvislosti s XORem v poslední době narazil. Chytřejší než já mi to snad objasní, abych to pochopil :)

1. v úvodu bude 0 (příp. cokoliv jiného ale předem známého a dohodnutého), následně budu xorovat jeden byte za druhým postupně jak jdou v paměti. Nakonci dostanu nějakou hodnotu řekněme X. Stejné X však dostanu když budu bajty XORovat nikoliv postupně ale (libovolně) na přeskáčku (samožřejmě je musím vyxorovat úplně všechny).

2. Chtěl jsem do MDOSu 2.1 dát kontrolní XOR hodnotu a tu si zkontrolovat při každém resetu. Chtěl jsem už v DROM mít něco tohoto typu
ld a,XXX ;počáteční XOR hodnota
...
smyčka na XOR (hl) o 14336 bytes (D)ROM
...
cp YYY

tj. natvrdo zapsané hodnty, a vlastně by to tak xorovoalo i samo sebe (jelikož podprogram by byl někde v 0 - 14336. Naspal jsem si program, který se mi snaží ty hodnoty XXX a YYY zjistit. Byla to opravdu náročná úloha pro náš malinký CPU tak jsem v RealSpectrum dal CPU na max a už to bylo snesitelnější - cca hodina. Jenže ačkoliv jsem prošel všechny možnosti, tak mi to pokaždé dopadlo neúspěchem - takové dvě hodnoty zkrátka nelezeny nebyly! Je možné, že jsem v prográmku na hledání udělal chybu (snad jsem ho nesmazal, zkusím ho v případě zájmu pohledat...). Nevím, zkrátka vzal jsem si z toho ponaučení, že výsledek XORu musí být uložen mimo XORovanou oblast.

3. Ano, v úvodu jsem psal pouze o dvou, ale mám i třetí. Ta mi je však jasná. Pro nezasvěcené ji ale popíšu. Utilita u@speccyFTP přenáší soubory mezi dvěmi 8255 (tj. paralelní přenos = celý byte najednou). Spolehlivost paketů řeším XORem. Vysílací strana udělá CRC XOR a připlácne ho nakonec paketu. Přijímací strana dělá XOR po každém přijatém byte a nakonec jej porovná s tím posledním byte z doručeného paketu. Jsou-li shodné je to OK, nejsou-li pak muselo dojít k chybě. Při poškozeném jednom (či klidně více) drátu na datové bráně je však tato XOR ochrana neúčinná. Příjem hrdě hlásí, že XOR sedí. :) Je to proto, že i ten XOR přijde špatně (je osekán o bity, kde chybí dráty) a čili naprosto sedí s XORem, který si průběžně dělala přijímací strana (něboť také všechny bytes před tím došly osekané o ty bity kde chybí dráty).


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 09:42 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 08.07.2013, 00:28
Příspěvky: 1554
Has thanked: 485 times
Been thanked: 634 times
(1) Xor je komutativní, stejně jako sčítání nebo násobení - nezáleží na pořadí.


(2) Čili ses snažil vpodstatě o takový mining kryptoměn XXX a YYY? :-D
Formálně chceš tedy následující:

Byte1 xor Byte2 xor XXX xor Byte3 xor YYY xor Byte4 = YYY

Kdyby tam nebylo Xor, ale třeba Plus (se stejnými? vlastnostmi), aby to bylo uchopitelnější

Byte1 + Byte2 + XXX + Byte3 + YYY + Byte4 = YYY
je totéž jako
Byte1 + Byte2 + XXX + Byte3 + Byte4 = 0
je totéž jako
XXX = -( Byte1 + Byte2 + Byte3 + Byte4 )

Pokud to zkusím zpětně převést na Xor a bitové operace

XXX = ~( Byte1 xor Byte2 xor Byte3 xor Byte4 )

XXX si tedy musíš předpočítat tímto způsobem. V tomhle okamžiku podle mě na YYY nezáleží a může to být jakákoliv hodnota. Protože ale chceš dělat checksum Xorem YYY musíš mít v kódu, zbývá tedy podle mě YYY neXORovat (aby nebylo jak na levé, tak na pravé straně):

Byte1 + Byte2 + XXX + Byte3 + Byte4 = YYY

Snad to k něčemu bude... :shrug:

_________________
より良い競争相手からソフトウェアを購入する (。◕‿‿◕。)
Ďábel se skrývá v detailu (staré technické rčení)


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 09:44 
Offline
Kecálek

Registrován: 07.05.2014, 12:10
Příspěvky: 197
Bydliště: Jbc
Has thanked: 0 time
Been thanked: 39 times
Pokud se pouzije takovyto jednoduchy algoritmus, tak vetsinou staci menit tam jeden byte, treba inicializacni, a vysledek vzdy testovat na nulu. Pak podle algoritmu a vysledne testovane hodnoty se jen provede korekce pocatecni hodnoty, aby byl vysledek nulovy.
V ruznych projektech, kde jsem neco podobneho delal, jsem mel na konci pridanou hodnotu, kterou jsem pred uvolnenim projektu nastavil, aby byl kontrolni soucet (vcetne teto hodnoty) nulovy.


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 09:50 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 864 times
Been thanked: 697 times
U CRC s XORem se dělává, že se střadač po každé operaci rotuje o 1 bit. Tím se sníží šance, že se navzájem vykompenzují chyby na stejné bitové pozici (vadný drát). Jiná alternativa (méně přesná) je používat součet ADD, kde se chyby na nižších bitech projeví na vyšších bitech součtu, částečně to ošetřuje opakované chyby na nižších pozicích.

Výsledek 0 se dá také zajistit u obou případů - u XOR doplnit na konec výsledek beze změny, u ADD doplnit negaci výsledku.

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


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 09:59 
Offline
Radil

Registrován: 18.10.2014, 23:10
Příspěvky: 377
Has thanked: 28 times
Been thanked: 120 times
(2) Jednoducho pred výpočtom kontrolného bajtu dosaď za YYY nulu a po výpočte ho tam doplníš.

(3) Môžeš zmeniť kontrolu z XOR na ADD, ale keď bude všetkých 8 drátov zlých, tak to nebude tiež fungovať. To pomôže zistiť len test každej linky pred prenosom.


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 10:11 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 14.05.2013, 19:10
Příspěvky: 1486
Bydliště: Kurim
Has thanked: 828 times
Been thanked: 577 times
Ono záleží na tom, k čemu to potřebuješ a jak náročný algoritmus si můžeš dovolit. Pro kotrolní součet dat v EPROM asi asi stačí obyčejný XOR, hrozí tam časem výpadek semtam nějakého bitu. Při přenosu dat je určitě lepší využít něco jak píše Panda38 nebo CRC funkci s vhodným polynomem, která Ti zajistí detekci jakékoli chyby v příslušné dlouhém úseku dat https://cs.wikipedia.org/wiki/Cyklick%C ... ou%C4%8Det

_________________
http://www.8bity.cz


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 11:03 
Offline
Kecálek

Registrován: 06.04.2020, 16:24
Příspěvky: 222
Bydliště: Opava
Has thanked: 31 times
Been thanked: 70 times
Antony/DTA píše:
(2) Jednoducho pred výpočtom kontrolného bajtu dosaď za YYY nulu a po výpočte ho tam doplníš.

Toto mě nenapadlo, to si určitě vyzkouším.


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 11:15 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 864 times
Been thanked: 697 times
CRC polynomem má podstatně vyšší úspěšnost v detekci chyb, ale má pro malé systémy nevýhodu - buď vyžaduje časově náročný výpočet, nebo rozměrnou tabulku. Existuje ale metoda použitelná dobře i pro 8-bity, spolehlivá a rychlá: fast-CCITT (polynom x^16 + x^12 + x^5 + 1), používá se např. u XModemu a Bluetooth a má dost vysokou úroveň zabezpečení chyb:

Akumulátor CRC je 16-bitový (2 registry). Přidání 1 datového bajtu k akumulátoru:
Kód:
crc = (crc >> 8) | (crc << 8);   .... prohodí vyšší a nižší bajt CRC
crc ^= data;               .... provede XOR nižšího bajtu CRC s datovým bajtem
crc ^= (crc & 0xff) >> 4;         ... provede XOR nižšího bajtu CRC se sebou samým rotovaným 4x vpravo
crc ^= crc << 12;            ... provede XOR vyššího bajtu CRC se sebou samým rotovaným 4x vlevo
crc ^= (crc & 0xff) << 5;         ... provede XOR CRC (dvojregistr) s nižším bajtem rotovaným 5x vlevo

Výchozí hodnoty CRC:
- 0000 pro XModem
- FFFF pro CCITT
- 1D0F pro CCITT-B

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

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


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 13:21 
Offline
Profík
Uživatelský avatar

Registrován: 20.02.2017, 01:17
Příspěvky: 800
Has thanked: 19 times
Been thanked: 48 times
Nejsem odborník na tuto IT aritmetiku, ale jedno vím: vadí mi, když někdo používá tzv. XOR sprajty co prosvítají přes další objekty, aby si ušetřil práci a rychlost. Hlavně jsou tím "slavné" staré hry pro Spectrum. Ale když někdo něco takového udělá v roce 2020, je to trapné...


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 13:52 
Offline
Óm Nejvyšší
Uživatelský avatar

Registrován: 07.07.2019, 22:14
Příspěvky: 3766
Has thanked: 269 times
Been thanked: 452 times
Není nic snadnějšího než ty hry in persona přepsat do vhodnějšího grafického kabátku a potunit rychlost běhu aby to stíhalo běžet i bez průhledných spritů ;).


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 16:49 
Offline
Óm Nejvyšší

Registrován: 22.05.2013, 21:14
Příspěvky: 3642
Bydliště: Bratislava
Has thanked: 371 times
Been thanked: 788 times
MTs píše:
2. Chtěl jsem do MDOSu 2.1 dát kontrolní XOR hodnotu a tu si zkontrolovat při každém resetu. Chtěl jsem už v DROM mít něco tohoto typu
ld a,XXX ;počáteční XOR hodnota
...
smyčka na XOR (hl) o 14336 bytes (D)ROM
...
cp YYY

tj. natvrdo zapsané hodnty, a vlastně by to tak xorovoalo i samo sebe (jelikož podprogram by byl někde v 0 - 14336. Naspal jsem si program, který se mi snaží ty hodnoty XXX a YYY zjistit. Byla to opravdu náročná úloha pro náš malinký CPU tak jsem v RealSpectrum dal CPU na max a už to bylo snesitelnější - cca hodina. Jenže ačkoliv jsem prošel všechny možnosti, tak mi to pokaždé dopadlo neúspěchem - takové dvě hodnoty zkrátka nelezeny nebyly!
A ani nemohli !

Totiz, ty si urobil nieco taketo:
Kód:
XXX xor #3E xor XXX xor ... xor ... xor #FE xor YYY xor ... = YYY
Prve XXX je inicializacna hodnota, #3E je ld a,..., nasleduje zase XXX, potom dalsie bajty, neskor cp = #FE, bajt YYY, nakoniec ostatne bajty a toto vsetko sa musi rovnat YYY.
Po uprave (preusporiadanie clenov rovnice):
Kód:
(XXX xor XXX) xor (YYY xor YYY) xor #3E xor #FE xor vsetky_ostatne_bajty = 0
Obsah zatvoriek je pochopitelne nulovy, takze zostava toto:
Kód:
xor #3E xor #FE xor vsetky_ostatne_bajty = 0
Nuz a mozes sa snazit dosadzat XXX a YYY ake len chces, ked ostatne bajty raz nedaju nulovy xor, tak proste nedaju :bang:

Riesenie je ze minimalne jedno z XXX a YYY nutne musi byt mimo xorovanej oblasti, aby bolo v rovnici iba raz a tym padom malo vplyv na vysledok.

Dodatok: Ale aj keby si toto vsetko urobil a problemy s xorom vyriesil, tak aj tak to moze zlyhat. Predpokladam ze ak zistis, ze XOR nesedi, budes tam mat nejake JR NZ,CHYBA. Ale co ak nastane nejaka zmena prave v tretom bite operacneho kodu instrukcie JR NZ,... ? Vysledny xor samozrejme sediet nebude, ale instrukcia sa zmeni na JR Z,... a kedze xor nesedi a bude NZ, procesor neskoci. A vsetko sa bude tvarit tak, ako keby bol obsah romky v najlepsom poriadku :)


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 18:16 
Offline
Pan Štábní

Registrován: 23.06.2013, 23:49
Příspěvky: 1100
Has thanked: 100 times
Been thanked: 157 times
Neni pro kontrolni soucet lepsi neco z ceho jde take odvodit i ktere data jsou vadna a dokonce je i opravit? Ano, bude to pridavat k prenesenym datum o dost vic nez jeden nebo dva bajty s kontrolnim xorem, ale ne zas tolik oproti puvodnim datum. Chyby take budeme ocekavat nahodne a sem tam.

+12.5% pokud budes resit bloky o 256 bajtech.
+6.25% pokud budes resit bloky o 1024 bajtech.
+3.125% pokud budes resit bloky o 4096 bajtech.

Plus asi neco malo na kontrolu kontroly... :D Jen netusim jak moc by to cpu stihal.

Idea je takova ze kontrolni soucty budou vzdy o "rozmer nize". Data budou treba plocha a kontrola obvod. Kdyz budes mit tabulku 16*16 bajtu tak kontrolni data budou ulozeny v jednom 16 polozkovem sloupci a radku navic. A v kazdem bajtu radku bude ten xor celeho sloupce. Takze pokud ti nebude sedet bit tak budes vedet ze ten bitovy sloupec je spatne a muzes pracne pocitat kontrolni sloupec navic a hledat vadny radek. I kdyz to by asi taky slo pres nejakou mensi 256 bajtovou tabulku, kterou si predtim vygenerujes. Prusecik by mela byt chyba. Dokud netrefis 2 chyby na stejnem radku nebo sloupci tak to bude fungovat.

_________________
Z80 Forth compiler (ZX Spectrum 48kb): https://codeberg.org/DW0RKiN/M4_FORTH


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 18:33 
Offline
Pan Štábní
Uživatelský avatar

Registrován: 24.05.2018, 22:32
Příspěvky: 1972
Bydliště: Most, Praha
Has thanked: 864 times
Been thanked: 697 times
Proti klasickému XOR CRC se u samopravy doba prodlouží jen na 2x a něco - namísto 1x průchodu se projde navíc i v příčném směru. Pro data 16x16 je to matice 17x17 bajtů, kontrolní řádek/sloupec je také zabezpečený XORem (který je v rohu jako 17. prvek). Kontroluje se 17 řádků a 17 sloupců. Když se najde vadný, lze kterýkoliv z těch 17 vygenerovat XORováním ze zbylých 16.

Měl jsem takto zabezpečnou sadu disket paritní disketou, která byla XORem ostatních disket v sadě - nejednou mi to zachránilo data na vadné disketě, kterákoliv disketa ze sady se dala rekonstruovat. (obvykle chyby nebyly ve stejných sektorech, tak se dalo opravit i více vadných disket)

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


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 19:04 
Offline
Pan Generální
Uživatelský avatar

Registrován: 23.03.2014, 20:13
Příspěvky: 2773
Has thanked: 224 times
Been thanked: 601 times
XOR ruleeez! ;)

_________________
Plesnivý sýr z Tesca, zatuchlé kuřecí řízky z Albertu, oslizlé hovězí a myší trus z Lidlu.
Nákup potravinářské inspekce v ČR, říjen 2023.


Nahoru
 Profil  
 
PříspěvekNapsal: 27.05.2020, 19:28 
Offline
Kecálek

Registrován: 06.04.2020, 16:24
Příspěvky: 222
Bydliště: Opava
Has thanked: 31 times
Been thanked: 70 times
Busy píše:
Dodatok: Ale aj keby si toto vsetko urobil a problemy s xorom vyriesil, tak aj tak to moze zlyhat. Predpokladam ze ak zistis, ze XOR nesedi, budes tam mat nejake JR NZ,CHYBA. Ale co ak nastane nejaka zmena prave v tretom bite operacneho kodu instrukcie JR NZ,... ? Vysledny xor samozrejme sediet nebude, ale instrukcia sa zmeni na JR Z,... a kedze xor nesedi a bude NZ, procesor neskoci. A vsetko sa bude tvarit tak, ako keby bol obsah romky v najlepsom poriadku :)


Však ale tato jediná případná chyba (změna z "jr nz" na "jr z") je jako jedna jediná v pohodě a vlastně je i v pořádku, že se ROMka vyhodnotí jako že je OK. Dalo by se říci, že jde o chybu, která samu sebe opravila. :lol: Ale je to opravdu dobrá připomínka!! :like: Test tedy musí ještě obsahovat, že na tom místě je opravdu kód instrukce "jr nz" A i ten test testu může selhat ze stejného důvodu. Zkrátka dobré psycho :suicide: Ale ta pravděpodobnost, že se to fakt stane je opravdu hodně malinkatá a myslím, že je lepší mít nějaký "selfhealthtestík" než vůbec žádný.


Nahoru
 Profil  
 
Zobrazit příspěvky za předchozí:  Seřadit podle  
Odeslat nové téma Odpovědět na téma  [ Příspěvků: 56 ]  Přejít na stránku 1, 2, 3, 4  Další

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 4 návštevní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

Hledat:
Přejít na:  
Založeno na phpBB® Forum Software © phpBB Group
Český překlad – phpBB.cz