CRC berechnung - amiga-news.de Forum

amiga-news.de Forum > Programmierung > CRC berechnung

[ - Suche - Neue Beiträge - Registrieren - Login - ]

-1-

[ - Beitrag schreiben - ]

23.11.2006, 09:48 Uhr

MaikG
Posts: 5172
Nutzer

Gibt es mehrere arten von CRC?

Ich habe hier eine Datei, für die habe ich auch den Korrekten
CRC. Aber das Programm unten gibt mir ganz andere sachen zurück.
Ich habe schon vorne und hinten bei der Datei was abgeschnitten.
Vorne steht ja der CRC mit drin und hinten ist evtl. ein EOF oder
so. Ja, trotzdem kam nicht der korrekte wert.
Der Code ist von http://vb-tec.de/crc.htm, nur halt auf das
wichtigste beschränkt und in Normal Basic übersetzt:

code:

REM $Include exec.bh

DEFINT a-z

COMMON SHARED pInititialized%
DIM SHARED pTable&(255)

SUB CRCInit&

Poly&=&HEDB88320&
  FOR i% = 0 TO 255
    CRC& = i%
    FOR j% = 0 TO 7
      IF CRC& AND &H1 THEN
        CRC& = ((CRC& AND &HFFFFFFFE)  &H2 AND &H7FFFFFFF) XOR Poly&
      ELSE
        CRC& = CRC&  &H2 AND &H7FFFFFFF
      END IF
    NEXT j%
    pTable&(i%) = CRC&
  NEXT i%
  pInititialized% = True&
END SUB

'CRC32File - Prüfsumme über eine Datei


FUNCTION CRC32File&(Path$)
IF NOT pInititialized% THEN CALL CRCInit&
 OPEN Path$ FOR INPUT AS #1
   Length& = LOF(1)
   CRC& = &HFFFFFFFF&
    FOR i& = 1 TO Length&
     CRC& = ((CRC& AND &HFFFFFF00)  &H100) AND &HFFFFFF XOR pTable&(ASC(INPUT$(1,#1)) XOR CRC& AND &HFF&)
    NEXT i&
   CRC32File& = NOT CRC&
   PRINT HEX$(NOT CRC&)
CLOSE #1
NEXT j%
END FUNCTION

[ - Antworten - Zitieren - Direktlink - ]

23.11.2006, 11:39 Uhr

melior
Posts: 160
Nutzer

@MaikG:

Oh ja, es gibt verschiedene CRCs. Schau doch mal hier:

CRC (Wikipedia)

Tschüß André

[ - Antworten - Zitieren - Direktlink - ]

23.11.2006, 15:59 Uhr

MaikG
Posts: 5172
Nutzer

>Oh ja, es gibt verschiedene CRCs. Schau doch mal hier:

Oh nein. Wie finde ich raus welche Sorte benutzt wurde?

CRC ist 00157F2F, aber daraus kann man das nicht schliessen oder?

[ - Antworten - Zitieren - Direktlink - ]

23.11.2006, 18:38 Uhr

melior
Posts: 160
Nutzer

@MaikG:

An Deiner Stelle würde ich ein bekanntes CRC32-Tool nehmen und schauen, welches Ergebnis es liefert. Im Aminet gibt es einige davon. Wenn Du dann eins gefunden hast, das die richtige Zahl liefert, hast Du vielleicht auch den Sourcecode dazu oder kannst zumindest nach einem CRC32-Sourcecode suchen.

Tschüß André

[ - Antworten - Zitieren - Direktlink - ]

23.11.2006, 22:44 Uhr

MaikG
Posts: 5172
Nutzer

Also wenns nur die auf der Seite gibt kann ich:
CRC-16,CCITT, XMODEM, 12Bit-CRC, 10 Bit CRC und 8Bit CRC
ausschliessen. Das Ergebniss ist keine 32 Bit zahl(8Stellig Hex)

Ja, die 2 CRC32er hab ich probiert, stimmt nicht.
Theoretisch kann man jedoch sowohl beliebige Poly werte
(von 10000000-FFFFFFFF) und beliebiege Anfangswerte von 0-FFFFFFFF
nehmen. Soviel Tools mit soviel sorten wird es nicht geben, ausserdem
würde das dauern... Ich bräuchte eines das die Datei Analysiert.

Mein Migi hat zwar schon tausende berechnungen gemacht, der richtige
wert war aber noch nicht dabei...

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 07:00 Uhr

bubblebobble
Posts: 707
Nutzer

Wofü brauchst du das denn?

Die Implementierung für PNG Bilder sieht so aus,
evtl. hilft dir das weiter.
Das kannst du auch Problemlos auf eine File Buffer für Buffer anwenden.
In Amiblitz ist das alles schon implementiert:

code:

;/* Table of CRCs of all 8-bit messages. */
Dim CRC_table.l(256)
CRC_c.l=0
CRC_n.l=0
CRC_k.l=0
For CRC_n = 0 To 255
  CRC_c = CRC_n
  For CRC_k = 0 To 7
    If (CRC_c & 1)
      CRC_c = Xor($edb88320 , (CRC_c LSR 1))
    Else
      CRC_c = CRC_c LSR 1
    End If
    CRC_table(CRC_n) = CRC_c
  Next
Next


Function.l CRC32_update{CRC.l, sourceaddr.l, blength.l}
SHARED CRC_table()
c.l = CRC
For n.l = 0 To blength-1
  byte.l = Peek.b(sourceaddr+n)
  c = Xor(CRC_table(Xor(c , byte) & $ff) , (c LSR 8))
Next
Function Return c
End Function


Function.l CRC32_finalize{CRC.l}
Function Return Xor(CRC , $ffffffff)
End Function


Function.l CRC32{sourceaddr.l, blength.l}
Function Return Xor(CRC32_update{$ffffffff, sourceaddr, blength} , $ffffffff)
End Function


Function.l CRC32_fromstring{a.s}
Function Return Xor(CRC32_update{$ffffffff, &a.s, FLen(a.s)} , $ffffffff)
End Function


; Demo:

NPrint "Message and CRC code calculated in different ways:"
message.s ="The quick brown fox jumps wherever."
NPrint "Message: ",message.s
NPrint "CRC32 (from string)         : $",Hex$(CRC32_fromstring{message.s})

NPrint "CRC32 (direct memory)       : $",Hex$(CRC32{&message.s,Len(message.s)})

partA.l = Len(message.s)/2
partB.l = Len(message.s)-partA
CRC.l = CRC32_update{ -1, &message +     0, partA}
CRC.l = CRC32_update{CRC, &message + partA, partB}
CRC.l = CRC32_finalize{CRC}

NPrint "CRC32 (via several buffers) : $",Hex$(CRC)

Delay_ 200
End

--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 08:48 Uhr

melior
Posts: 160
Nutzer

Zitat:
Das Ergebniss ist keine 32 Bit zahl(8Stellig Hex)

Jede Ziffer einer 8-stelligen Hexzahl kann die Werte 0-15 (dezimal) einnehmen. Das läßt sich mit 4 Bits darstellen. Na und 8 * 4 ist 32.

Wenn Deine beiden CRC32-Programme einen anderen Wert geliefert haben, hat vielleicht auch nur die Invertierung am Schluß gefehlt ...

Tschüß André

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 10:05 Uhr

MaikG
Posts: 5172
Nutzer

>Wofü brauchst du das denn?

Ich hab eine Datei, die möchte ich verändern. Die hat aber eine
CRC Prüfsumme. Würde ich jetzt was verändern ohne die Prüfsumme
neu zu berechnen würde die Datei nicht angenommen werden.

>Die Implementierung für PNG Bilder sieht so aus,

Irgendwie sieht das Komplitzierter aus... Das Problem ist
ja das ich den Poly wert und den Anfangswert nicht kenne.

>Jede Ziffer einer 8-stelligen Hexzahl kann die Werte 0-15 (dezimal)
>einnehmen. Das läßt sich mit 4 Bits darstellen. Na und 8 * 4 ist 32.

Das Ergebniss muss 00157F2F sein, wenns nur FA56 ist, ist das
falsch.

>Wenn Deine beiden CRC32-Programme einen anderen Wert geliefert
>haben, hat vielleicht auch nur die Invertierung am Schluß gefehlt ...

Ich hab die Ausgabe einmal normal und einmal mit NOT davor.

code:

PRINT HEX$(NOT CRC&), print hex$(CRC&)

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 11:19 Uhr

melior
Posts: 160
Nutzer

Zitat:
Das Ergebniss muss 00157F2F sein, wenns nur FA56 ist, ist das
falsch.

... oder es werden nur die führenden Nullen weggelassen.

Wie wäre es denn, wenn Du die Datei irgendwo zum Download bereitstellst? Dann müßten wir nicht länger spekulieren.

Tschüß André

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 17:01 Uhr

MaikG
Posts: 5172
Nutzer

>... oder es werden nur die führenden Nullen weggelassen.

Ich hab mehrere Dateien da gibts auch Prüfsummen ohne 0en.

>Wie wäre es denn, wenn Du die Datei irgendwo zum Download
>bereitstellst? Dann müßten wir nicht länger spekulieren.

Hab kein Webspace, aber wie willst du das rausbekommen?
Ein Tool(mehr hab ich nicht gefunden) habe ich aus dem
Aminet, liefert eine andere Prüfsumme. In dem PC-Programm
stehen die beiden Poly's von CRC32 nicht. Bin mal mit dem
Hexeditor drüber, also kann ich die 2 Standard teile dann auch
streichen...

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 17:45 Uhr

melior
Posts: 160
Nutzer

Zitat:
Hab kein Webspace, aber wie willst du das rausbekommen?

Ich hätte mir angeschaut, welche CRC32 das Linux-Tool "crc32" liefert.

Tschüß André

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 18:03 Uhr

bubblebobble
Posts: 707
Nutzer

Also CRC32 ergibt eine 32bit Prüfsumme, also ein
Langwort, daher der Name. Es gibt auch CRC16 und CRC64.
Eigentlich ist CRC32 standardisiert, das ist der Sinn.

CRC32 geht so wie in obigem Amiblitz Beispiel Source.
Kompliziert ist das nicht.

Vielleicht solltest du dir überlegen, doch mal auf
AB2 umzusteigen ? ;-)
Dort gibt jede Menge Befehle inkl. Source, der sich mit moderneren
Dingen beschäftigt, z.B. gibts auch MD5
(was ziemliche Kopfschmerzen bereitet hatte zu implementieren)

Wenn es bei dir nicht klappt, der CRC Algo aber deiner Meinung nach
korrekt implementiert ist, machst du vermutlich einen der
folgenden Fehler:

1. Anfangspolynom ist falsch
2. Du berechnest die Checksumme über einen falschen Bereich, z.B.
Chunk header ist meistens nicht mit drin und die Prüfsumme selbst etc.
3. Du hast das invertieren am Ende vergessen

--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 18:42 Uhr

MaikG
Posts: 5172
Nutzer

>Ich hätte mir angeschaut, welche CRC32 das Linux-Tool "crc32"
>liefert.

Ich könnte es dir ja Mailen.

>Vielleicht solltest du dir überlegen, doch mal auf
>AB2 umzusteigen ? ;-)

Mag ich nicht, mein Source macht doch auch CRC32.

>1. Anfangspolynom ist falsch

Das würde ich nicht als Fehler bezeichnen, weil das ja nicht
gegeben ist.

>2. Du berechnest die Checksumme über einen falschen Bereich, z.B.
>Chunk header ist meistens nicht mit drin und die Prüfsumme selbst etc.

Also der Header müssten die ersten 30 Bytes sein. Die größe des
bereichs ist gegeben, daher müssen 30 Bytes abgeschnitten werden.
Ich hab auch probiert vorne 28 Byte abzuschneiden hinten 2.
Und viele andere Variationen.

>3. Du hast das invertieren am Ende vergessen

Inventrieren ist NOT, wenn ich das richtig verstehe.
Das Programm gibt mir wie gesagt einmal das Normale und einmal
das NOT ergebniss.

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 19:08 Uhr

Flinx
Posts: 1073
Nutzer

@MaikG:

Bevor Du mit einem unbekannten Dateiformat experimentierst: Hast Du denn Deinen Algorithmus schon mal mit einer Datei getestet, bei der klar ist, was für ein CRC-Rest herauskommen muß?

[ - Antworten - Zitieren - Direktlink - ]

24.11.2006, 22:26 Uhr

MaikG
Posts: 5172
Nutzer

>Bevor Du mit einem unbekannten Dateiformat experimentierst: Hast Du
>denn Deinen Algorithmus schon mal mit einer Datei getestet, bei der
>klar ist, was für ein CRC-Rest herauskommen muß?

Nein, hab keine solche Datei. Der Code war Virtual Basic, die
Conventrierung war nicht schwer. Ich hoffe eingentlich das
dieser fehlerfrei ist.

Edit:
Ja, der Code Funktioniert. Hab ebend eine Datei durch das
Aminet-Tool gejagt danach durch mein Programm - selbes ergebniss.

[ Dieser Beitrag wurde von MaikG am 24.11.2006 um 23:15 Uhr geändert. ]

[ - Antworten - Zitieren - Direktlink - ]

01.12.2006, 18:14 Uhr

MaikG
Posts: 5172
Nutzer

Hab jetzt ein CRC-Bruteforce Programm geschrieben, bin in den letzten
tagen bis 1.100.000 gekommen. Das könnte noch sehr sehr lange dauern.
Hab auch versucht das in Qbasic zu Compilieren, das ist aber
langsamer als das Programm unter WinUAE. Würde sich vielleicht jemand
bereit erklären, der zufällig einen 3,8 GHZ PC mit UAE hat das mal
durchlaufen zu lassen? Gegenüber eines 500MHZ AMD müsste das
auf so einem sehr schnell gehen.

[ - Antworten - Zitieren - Direktlink - ]

01.12.2006, 23:17 Uhr

bubblebobble
Posts: 707
Nutzer

@Maik
Was ist nun eignetlich das Problem ?

Soll ich dir die CRC32 Summe deiner Datei mit Amiblitz berechnen ?

Was meinst du im letzten Post mit Brute Force ?

--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de

[ - Antworten - Zitieren - Direktlink - ]

02.12.2006, 10:36 Uhr

MaikG
Posts: 5172
Nutzer

>Was ist nun eignetlich das Problem ?

Ich hab eine Datei, deren Poly wert zur berechnung der CRC32 summe
kein Standard ist.

>Soll ich dir die CRC32 Summe deiner Datei mit Amiblitz berechnen ?

Eine Normale rechnung wird da nicht funktionieren.

>Was meinst du im letzten Post mit Brute Force ?

Ich habe ein Programm geschrieben das forwährend alle Poly's
von 0 bis einer vorzeichenbehafteten Long durchgeht.
Wenn es das korrekt Ergebniss erhält meldet es sich.
Problem ist es dauert sehr lange, die Datei ist 185k groß.
Ich bin jetzt bei etwa 1Mio. Es würde etwa 70 Tage dauern
bis ich bei 16,7 Mio(vermutlich ist der Poly im bereich 1-16,7Mio) bin.
Ich hab nur einen 500MHZ PC, ist etwas schneller dabei als mein
Amiga. Mit einem 3,8 GHZ PC dürfte das nicht lange dauern.

[ - Antworten - Zitieren - Direktlink - ]

02.12.2006, 18:05 Uhr

bubblebobble
Posts: 707
Nutzer

@Maik
Was macht dich glauben, dass es in den unteren 24bit ist ?
(16,7 Mio).

Wenn es eine 32bit Checksumme ist, musst du u.U. nochmal 256 mal so viel durchsuchen.
Ausserdem verlangst du hier, dass jemand für dich seinen Rechner zwei Wochen auf 100% CPU Last nudeln lässt.

Wenn CRC32 gut designt ist, wirst du durch Verändern des Anfangspolynoms auf jeden Fall eine Config finden, für die du die "richtige" Checksumme erhältst. Das muss aber noch lange nicht die Lösung sein, es sei denn es liegt wirklich nur am Polynom.

Gibts denn dazu keine Docu ? Was für eine Anwendung ist das denn?
Ich vermute immer noch, dass du über den flaschen Bereich rechnest oder einen Fehler machst.

--
Thilo Köhler, Author von:
HD-Rec, Samplemanager, ArTKanoid, Monkeyscript, Toadies, AsteroidsTR, TuiTED, PosTED, TKPlayer, TKUnpacker
Homepage: http://www.hd-rec.de

[ - Antworten - Zitieren - Direktlink - ]

02.12.2006, 23:19 Uhr

MaikG
Posts: 5172
Nutzer

>Was macht dich glauben, dass es in den unteren 24bit ist ?
>(16,7 Mio).

Das Ergebniss muss 157F2F sein, nach einigen Poly Experimenten
denke ich das es so sein muss. Bei einem größeren Poly kann bei
dieser datei vermutlich keine 6 Stellige Zahl rauskommen.

>Wenn es eine 32bit Checksumme ist, musst du u.U. nochmal 256 mal so
>viel durchsuchen.
>Ausserdem verlangst du hier, dass jemand für dich seinen Rechner
>zwei Wochen auf 100% CPU Last nudeln lässt.

70:7,6=9,2 Tage bei 10 h pro Tag. Aber das währe eine reine MHZ
rechnung, die so nicht stimmt. Es gibt wie bei 68000, 68020...
vermutlich auch beim PC verschnellerungen ausserhalb des MHZ bereichs.
Dann hat der Rechner SD-Ram und einen 124MHZ Bus. Heute gibts einen
800MHZ Bus, 800 MHZ Ram und größeren Cache.
Ich Rechne daher nur mit Stunden.

>Wenn CRC32 gut designt ist, wirst du durch Verändern des
>Anfangspolynoms auf jeden Fall eine Config finden, für die du die
>"richtige" Checksumme erhältst. Das muss aber noch lange nicht die
>Lösung sein, es sei denn es liegt wirklich nur am Polynom.

Ich bin kein Mathematiker, es gibt die möglichkeit durch verändern
irgendwelcher Bits das Polynom rückwärts rauszufinden. Aber das
ist zu hoch für mich.

>Gibts denn dazu keine Docu ? Was für eine Anwendung ist das denn?

Wenns eine Doku gäbe, stände dort der Poly drin. Wie jetzt Anwendung?
Ich hab eine Datei die muss, wenn ich diese ändern will einen neuen
CRC bekommen.

>Ich vermute immer noch, dass du über den flaschen Bereich rechnest
>oder einen Fehler machst.

Glaub ich nicht, ich hab die größe über die der CRC berechnet wird.
Dafür ziehe ich 30 Bytes von der Datei vorne ab wo auch der CRC
drin steht. Ich finds logisch die ersten 30 Bytes zu Cutten, ohne
gehts nicht. Hab jedoch auch
Anfang Ende
28 2
26 4
24 6
22 8
20 10

mit den Normalen Poly's probiert.

Das Programm hat keinen Fehler, ich hab es gegengecheckt mit dem
aus dem Aminet. Beide liefern bei der gleichen Datei den gleichen
Wert.

[ - Antworten - Zitieren - Direktlink - ]

-1-

[ - Beitrag schreiben - ]

amiga-news.de Forum > Programmierung > CRC berechnung

[ - Suche - Neue Beiträge - Registrieren - Login - ]