[C++] CRC Checksum

[P4uluz]

Ik heb een code geschreven die de data van het nvram op een databordje wegschrijft naar het ram. Dit met het doel dat de content van het nvram bewaard blijft wanneer er een diagnose over het nvram gaat.

Nou is het natuurlijk wel verstandig om daarbij ook een checksum te gebruiken om te verifieren dat de data die achteraf terug op het nvram wordt gezet ook hetzelfde is als dat hij voorheen was. Op dit moment doe ik dit door simpelweg alle data bij elkaar op te tellen voor en na de test en deze te vergelijken. Maar aangezien zowel 2 + 4 als 3 + 3 gelijk is aan 6 is dit niet afdoende. (Het gaat nu we om grote hoeveelheden data waarbij de kans klein is dat het op die manier gelijk zal zijn, maar toch...)

Nu wil ik graag een CRC checksum uitvoeren, alleen ik zit een beetje met de handen in het haar hoe dit werkt. Ik heb me al enige tijd ingelezen, maar ik ben er nog niet uit hoe dit werkt. Misschien kan een van jullie opheldering geven waardoor ik er hopelijk wat sneller achter ben. Ik schrijf op het moment per byte aan data van het nvram naar het ram:

code:

nvramPointer = (BYTE *)nvramBase;
for (i = 0;(i < NVRAM_SIZE)&& (memoryBlockPointer < &memoryBlock[NVRAM_SIZE-1]); i++)
{
    *memoryBlockPointer = *nvramPointer;
     memoryBlockPointer++;
     nvramPointer = (BYTE *)(nvramBase + i);
}

Uiteraard zet ik het op een soortgelijke manier terug.

Hoe kan ik nu deze CRC checksum bereiken? Moet ik per verstuurde byte een checksum berekenen en deze opslaan? Of hoef je maar 1 checksum te berekenen over de totale data?
Thnx alvast..

[leuk_he]

P4uluz schreef op maandag 03 maart 2008 @ 14:16:
Hoe kan ik nu deze CRC checksum bereiken?

Code kun je vast wel vinden.

Het idee is dat je over het totaal, of een relevant block een Hash (=crc) berekent. Het verschil met jouw optellen is dat als er een verschuiving optreed( omdraaien van 2 waarden, block op verkeerde positie) de CRC niet klopt omdat je de postie van de bytes meetelt in je berekening.

Sommige code zal op basis van een stream en tussenresultaten werken, omdat als je veel data hebt dit wellicht niet helemaal in je geheugen wilt inlezen maar alleen per byte/block.

[P4uluz]

Even voor de duidelijkheid, stel ik heb in mijn geheugen van adres 1 tm adres 10 wat staan:
-Tel ik adres 1 tm 10 op en bereken daarover een hash.
-Voer ik de test uit op het nvram en zet alle content terug naar adres 1 tm 10
-Tel ik opnieuw adres 1 tm 10 op en bereken de hash
-Vergelijk de 2 hashes

Dit begrijp ik uit jou verhaal?
Dan bereken je volgens mijn als je mijn voorbeeld erbij pakt altijd de hash over 6 en die is bij 2+4 en bij 3+3 dus gelijk, terwijl de data verschilt.

[RobIII]

P4uluz schreef op maandag 03 maart 2008 @ 14:47:
Dan bereken je volgens mijn als je mijn voorbeeld erbij pakt altijd de hash over 6 en die is bij 2+4 en bij 3+3 dus gelijk, terwijl de data verschilt.

1+5, 0+6 en alle andere permutaties ook; maar dat probleem vang je ook niet met een hash; gezien die ook niet uniek is (hoewel met een goed hashing algo de hash stukken beter zal zijn dan het simpel optellen en dus de detectiekans op fouten vele malen groter; echter niet 100%).

[ Voor 6% gewijzigd door RobIII op 03-03-2008 14:56 ]

[P4uluz]

Maar dan ben ik eigenlijk het nut kwijt van het berekenen van een hash. Dan kan je toch ook gewoon de opgetelde data vergelijken. Of nou de hash gelijk is of de initiele waarde waarmee je de hash uitrekent..

Volgens mij zie ik echt iets over het hoofd.

[RobIII]

Ik denk dat je het principe van een hash niet helemaal begrijpt. Je kunt met een hash een fout relatief makkelijk detecteren, met een hoge mate van zekerheid. Maar 100% zul je niet halen; dat is onmogelijk omdat een hash altijd collisions zal hebben bij voldoende data (en ik neem aan dat dat het geval is als je zoveel kb nvram gaat hashen)

Stel het zo: waarom zou ik vele megabytes aan data opslaan als het in een hash van 32 bits zou passen? Dan zou ik die hash makkelijk kunnen 'terugrekenen' naar de vele megabytes. Dat kan dus niet omdat het onmogelijk is voor alle combinaties van bytes in die vele megabytes een unieke hash te berekenen. Er zullen altijd combinaties zijn die dezelfde hash opleveren.

Echter; de kans dat een kleine wijziging (1 bit is voldoende) een verschillende hash oplevert is erg groot mits je een goed hashing algoritme gebruikt; de kans dat dit dezelfde hash oplevert is nihil; vandaar dat je makkelijk kunt controleren of er fouten zijn met hoge mate van zekerheid. Ga je echter voor de 'optelling hash' dan is je kans op een 'collision' gewoon te groot; zeker als de hash-range in de range 0-10 of bijv 0-255 ligt. Kies je voor een grotere (zeg 128 bits) hash dan is de kans op collisions ook al weer drastisch kleiner; enkel niet zo goed als bij een 'echt' hashing algo.

[ Voor 63% gewijzigd door RobIII op 03-03-2008 15:04 ]

[leuk_he]

Je betrekt de positie van de bytes in de berekening.

dus b.v.

hash= (byte op pos 0 *1) + (byte op pos 1 *3) + (byte op pos 3 *5)

Als nu 2 bytes omgewisseld worden dan wordt de hash anders. Bij simpelweg optellen niet.

PS, bovenstaande berekening is versimpeld! bij een goed hash/crc alogirme wordt de kans dat verminkte data dezelfde hash oplevert kleiner.

[Anoniem: 14829]

Zoek 's op MD5 of LHA. Prima hash algorithmes die vaak al in de libraries van je ontwikkelomgeving beschikbaar zijn. En zo niet, dan zijn er ook (en juist) voor C++ wel prima freeware implementaties voor te vinden.

[Rukapul]

MD5 is overkill. MD5 is namelijk bedoeld om moedwillige veranderingen te kunnen detecteren. MD5 kan voor een embedded implementatie behoorlijk zwaar zijn (al valt dat in absolute termen vaak ook al wel weer mee wanneer de data hoeveelheden niet enorm zijn).

Veel lichter is een klassieke CRC welke bedoeld is om veranderingen te detecteren die per ongeluk zijn ontstaan, zoals het flippen van een bit of byte, bepaalde permutaties, etc. Bij elke CRC is terug te vinden welke veranderingen het nog kan detecteren. Een CRC detecteert in elk geval een flink aantal fouten die er bij een eenvoudige som doorheen kunnen glippen.

Een CRC bereken je trouwens gewoon over het hele blok data.

[ Voor 7% gewijzigd door Rukapul op 03-03-2008 21:22 ]