CRC32 Selfmade

[cxAlex]

Hier ein kleiner CRC32 Algorythmus, genau wie CRC32Fingerprint() in PB. Vlt. falls jemand einen Progress einbauen will usw.

PS: Sieh hier noch jemand Optimierungspotetial? Bei mir braucht PB um die Checksumme von 1GB Memory zu bilden 3000 ms, mein Code >15000 ms, also 5x so lange. Hatt einer ne Idee was ich noch optimieren könnte?

Code: Alles auswählen

Structure CRC32_Table
  *Entry.l[0]
EndStructure

; Genau wie CRC32Fingerprint()
Procedure CRC32_Mem(*Mem.Byte, MemSize)
  Protected crc32Result.l = $FFFFFFFF
  Protected *Table.CRC32_Table = ?_CRC_Table
  While MemSize
    crc32Result = (((crc32Result & $FFFFFF00)/$100) & $FFFFFF) ! *Table\Entry[(crc32Result & $FF) ! *Mem\b]
    *Mem + 1
    MemSize-1
  Wend
  ProcedureReturn ~crc32Result
EndProcedure

;{ CRC Data
DataSection
  _CRC_Table:
  Data.l 0
  Data.l $0000000077073096, $FFFFFFFFEE0E612C, $FFFFFFFF990951BA, $00000000076DC419, $00000000706AF48F
  Data.l $FFFFFFFFE963A535, $FFFFFFFF9E6495A3, $000000000EDB8832, $0000000079DCB8A4, $FFFFFFFFE0D5E91E
  Data.l $FFFFFFFF97D2D988, $0000000009B64C2B, $000000007EB17CBD, $FFFFFFFFE7B82D07, $FFFFFFFF90BF1D91
  Data.l $000000001DB71064, $000000006AB020F2, $FFFFFFFFF3B97148, $FFFFFFFF84BE41DE, $000000001ADAD47D
  Data.l $000000006DDDE4EB, $FFFFFFFFF4D4B551, $FFFFFFFF83D385C7, $00000000136C9856, $00000000646BA8C0
  Data.l $FFFFFFFFFD62F97A, $FFFFFFFF8A65C9EC, $0000000014015C4F, $0000000063066CD9, $FFFFFFFFFA0F3D63
  Data.l $FFFFFFFF8D080DF5, $000000003B6E20C8, $000000004C69105E, $FFFFFFFFD56041E4, $FFFFFFFFA2677172
  Data.l $000000003C03E4D1, $000000004B04D447, $FFFFFFFFD20D85FD, $FFFFFFFFA50AB56B, $0000000035B5A8FA
  Data.l $0000000042B2986C, $FFFFFFFFDBBBC9D6, $FFFFFFFFACBCF940, $0000000032D86CE3, $0000000045DF5C75
  Data.l $FFFFFFFFDCD60DCF, $FFFFFFFFABD13D59, $0000000026D930AC, $0000000051DE003A, $FFFFFFFFC8D75180
  Data.l $FFFFFFFFBFD06116, $0000000021B4F4B5, $0000000056B3C423, $FFFFFFFFCFBA9599, $FFFFFFFFB8BDA50F
  Data.l $000000002802B89E, $000000005F058808, $FFFFFFFFC60CD9B2, $FFFFFFFFB10BE924, $000000002F6F7C87
  Data.l $0000000058684C11, $FFFFFFFFC1611DAB, $FFFFFFFFB6662D3D, $0000000076DC4190, $0000000001DB7106
  Data.l $FFFFFFFF98D220BC, $FFFFFFFFEFD5102A, $0000000071B18589, $0000000006B6B51F, $FFFFFFFF9FBFE4A5
  Data.l $FFFFFFFFE8B8D433, $000000007807C9A2, $000000000F00F934, $FFFFFFFF9609A88E, $FFFFFFFFE10E9818
  Data.l $000000007F6A0DBB, $00000000086D3D2D, $FFFFFFFF91646C97, $FFFFFFFFE6635C01, $000000006B6B51F4
  Data.l $000000001C6C6162, $FFFFFFFF856530D8, $FFFFFFFFF262004E, $000000006C0695ED, $000000001B01A57B
  Data.l $FFFFFFFF8208F4C1, $FFFFFFFFF50FC457, $0000000065B0D9C6, $0000000012B7E950, $FFFFFFFF8BBEB8EA
  Data.l $FFFFFFFFFCB9887C, $0000000062DD1DDF, $0000000015DA2D49, $FFFFFFFF8CD37CF3, $FFFFFFFFFBD44C65
  Data.l $000000004DB26158, $000000003AB551CE, $FFFFFFFFA3BC0074, $FFFFFFFFD4BB30E2, $000000004ADFA541
  Data.l $000000003DD895D7, $FFFFFFFFA4D1C46D, $FFFFFFFFD3D6F4FB, $000000004369E96A, $00000000346ED9FC
  Data.l $FFFFFFFFAD678846, $FFFFFFFFDA60B8D0, $0000000044042D73, $0000000033031DE5, $FFFFFFFFAA0A4C5F
  Data.l $FFFFFFFFDD0D7CC9, $000000005005713C, $00000000270241AA, $FFFFFFFFBE0B1010, $FFFFFFFFC90C2086
  Data.l $000000005768B525, $00000000206F85B3, $FFFFFFFFB966D409, $FFFFFFFFCE61E49F, $000000005EDEF90E
  Data.l $0000000029D9C998, $FFFFFFFFB0D09822, $FFFFFFFFC7D7A8B4, $0000000059B33D17, $000000002EB40D81
  Data.l $FFFFFFFFB7BD5C3B, $FFFFFFFFC0BA6CAD, $FFFFFFFFEDB88320, $FFFFFFFF9ABFB3B6, $0000000003B6E20C
  Data.l $0000000074B1D29A, $FFFFFFFFEAD54739, $FFFFFFFF9DD277AF, $0000000004DB2615, $0000000073DC1683
  Data.l $FFFFFFFFE3630B12, $FFFFFFFF94643B84, $000000000D6D6A3E, $000000007A6A5AA8, $FFFFFFFFE40ECF0B
  Data.l $FFFFFFFF9309FF9D, $000000000A00AE27, $000000007D079EB1, $FFFFFFFFF00F9344, $FFFFFFFF8708A3D2
  Data.l $000000001E01F268, $000000006906C2FE, $FFFFFFFFF762575D, $FFFFFFFF806567CB, $00000000196C3671
  Data.l $000000006E6B06E7, $FFFFFFFFFED41B76, $FFFFFFFF89D32BE0, $0000000010DA7A5A, $0000000067DD4ACC
  Data.l $FFFFFFFFF9B9DF6F, $FFFFFFFF8EBEEFF9, $0000000017B7BE43, $0000000060B08ED5, $FFFFFFFFD6D6A3E8
  Data.l $FFFFFFFFA1D1937E, $0000000038D8C2C4, $000000004FDFF252, $FFFFFFFFD1BB67F1, $FFFFFFFFA6BC5767
  Data.l $000000003FB506DD, $0000000048B2364B, $FFFFFFFFD80D2BDA, $FFFFFFFFAF0A1B4C, $0000000036034AF6
  Data.l $0000000041047A60, $FFFFFFFFDF60EFC3, $FFFFFFFFA867DF55, $00000000316E8EEF, $000000004669BE79
  Data.l $FFFFFFFFCB61B38C, $FFFFFFFFBC66831A, $00000000256FD2A0, $000000005268E236, $FFFFFFFFCC0C7795
  Data.l $FFFFFFFFBB0B4703, $00000000220216B9, $000000005505262F, $FFFFFFFFC5BA3BBE, $FFFFFFFFB2BD0B28
  Data.l $000000002BB45A92, $000000005CB36A04, $FFFFFFFFC2D7FFA7, $FFFFFFFFB5D0CF31, $000000002CD99E8B
  Data.l $000000005BDEAE1D, $FFFFFFFF9B64C2B0, $FFFFFFFFEC63F226, $00000000756AA39C, $00000000026D930A
  Data.l $FFFFFFFF9C0906A9, $FFFFFFFFEB0E363F, $0000000072076785, $0000000005005713, $FFFFFFFF95BF4A82
  Data.l $FFFFFFFFE2B87A14, $000000007BB12BAE, $000000000CB61B38, $FFFFFFFF92D28E9B, $FFFFFFFFE5D5BE0D
  Data.l $000000007CDCEFB7, $000000000BDBDF21, $FFFFFFFF86D3D2D4, $FFFFFFFFF1D4E242, $0000000068DDB3F8
  Data.l $000000001FDA836E, $FFFFFFFF81BE16CD, $FFFFFFFFF6B9265B, $000000006FB077E1, $0000000018B74777
  Data.l $FFFFFFFF88085AE6, $FFFFFFFFFF0F6A70, $0000000066063BCA, $0000000011010B5C, $FFFFFFFF8F659EFF
  Data.l $FFFFFFFFF862AE69, $00000000616BFFD3, $00000000166CCF45, $FFFFFFFFA00AE278, $FFFFFFFFD70DD2EE
  Data.l $000000004E048354, $000000003903B3C2, $FFFFFFFFA7672661, $FFFFFFFFD06016F7, $000000004969474D
  Data.l $000000003E6E77DB, $FFFFFFFFAED16A4A, $FFFFFFFFD9D65ADC, $0000000040DF0B66, $0000000037D83BF0
  Data.l $FFFFFFFFA9BCAE53, $FFFFFFFFDEBB9EC5, $0000000047B2CF7F, $0000000030B5FFE9, $FFFFFFFFBDBDF21C
  Data.l $FFFFFFFFCABAC28A, $0000000053B39330, $0000000024B4A3A6, $FFFFFFFFBAD03605, $FFFFFFFFCDD70693
  Data.l $0000000054DE5729, $0000000023D967BF, $FFFFFFFFB3667A2E, $FFFFFFFFC4614AB8, $000000005D681B02
  Data.l $000000002A6F2B94, $FFFFFFFFB40BBE37, $FFFFFFFFC30C8EA1, $000000005A05DF1B, $000000002D02EF8D  
EndDataSection
;}

[Helle]

Z.B. Ersetze mal

Code: Alles auswählen

/$100

durch

Code: Alles auswählen

>> 8

Wenn die Daten als Long deklariert sind (oder i), schnipple doch die führenden 4 Bytes ab.

Gruß
Helle

Edit: Das Right-Shift 8 sieht bei mir so komisch aus...

[Little John]

Hatt einer ne Idee was ich noch optimieren könnte?

Sowas ist hier glaub ich schon öfter gepostet worden. Hast Du Dir bei den andern Implementierungen schon alle Tricks abgekuckt?

Gruß, Little John

[cxAlex]

Sowas ist hier glaub ich schon öfter gepostet worden. Hast Du Dir bei den andern Implementierungen schon alle Tricks abgekuckt?

Eigentlich schon. Und außer das ich alle in ASM progge find ich eigentlich jetzt (ausser dem von Helle) keine Optimierungsmöglichkeit mehr.

[alter Mann]

mal 'ne dumme Frage : wie passen die Quads (8Byte Werte) zu Data.l (4Byte)?

[cxAlex]

In der Ursprungsversion (VB) werden die Werte berechnet, ich hab die nur in ne DataSection gepackt um mir die Initialisation zu sparen, wegen der Performance. Im VB Code werden auch zum Speichern der Werte Longs benutzt, und so falsch kann das nicht sein, die CRC Berechnung erfolgt korrekt.

[PMV]

Long ist richtig, weil es 4-Byte Werte sind. Wenn du die Konstanten aus
VB hast, dann denke ich mal, das es dort am Umwandeln oder
Vorzeichenbehandlung liegt, warum hier 8-Byte Werte genommen wurden.
Die 4 hohen Bytes sind lediglich zum unterscheiden von positiven und
negativen Werten, was bei PB überflüssig ist, da dieser ja nur
Vorzeichenbehaftete Variablen kennt. Zumindest sieht es so aus, auf
jeden fall sind diese entweder $00000000 oder $FFFFFFFF und könnten
somit gestrichen werden.

MFG PMV

[alter Mann]

bei mir gibt es mit folgendem Code

Code: Alles auswählen

Structure CRC32_Table
  *Entry.l[0]
EndStructure

; Genau wie CRC32Fingerprint()
Procedure CRC32_Mem(*Mem.Byte, MemSize)
  Protected crc32Result.l = $FFFFFFFF
  Protected *Table.CRC32_Table = ?_CRC_Table
  Protected *Ende=*Mem+Memsize
  While *Mem<*Ende
    crc32Result = ((crc32Result>>8)&$FFFFFF) ! *Table\Entry[(crc32Result & $FF) ! *Mem\b]
    *Mem + 1
  Wend
  ProcedureReturn ~crc32Result
EndProcedure

;{ CRC Data
DataSection
  _CRC_Table:
  Data.l 0
  Data.l $77073096, $EE0E612C, $990951BA, $076DC419, $706AF48F
  Data.l $E963A535, $9E6495A3, $0EDB8832, $79DCB8A4, $E0D5E91E
  Data.l $97D2D988, $09B64C2B, $7EB17CBD, $E7B82D07, $90BF1D91
  Data.l $1DB71064, $6AB020F2, $F3B97148, $84BE41DE, $1ADAD47D
  Data.l $6DDDE4EB, $F4D4B551, $83D385C7, $136C9856, $646BA8C0
  Data.l $FD62F97A, $8A65C9EC, $14015C4F, $63066CD9, $FA0F3D63
  Data.l $8D080DF5, $3B6E20C8, $4C69105E, $D56041E4, $A2677172
  Data.l $3C03E4D1, $4B04D447, $D20D85FD, $A50AB56B, $35B5A8FA
  Data.l $42B2986C, $DBBBC9D6, $ACBCF940, $32D86CE3, $45DF5C75
  Data.l $DCD60DCF, $ABD13D59, $26D930AC, $51DE003A, $C8D75180
  Data.l $BFD06116, $21B4F4B5, $56B3C423, $CFBA9599, $B8BDA50F
  Data.l $2802B89E, $5F058808, $C60CD9B2, $B10BE924, $2F6F7C87
  Data.l $58684C11, $C1611DAB, $B6662D3D, $76DC4190, $01DB7106
  Data.l $98D220BC, $EFD5102A, $71B18589, $06B6B51F, $9FBFE4A5
  Data.l $E8B8D433, $7807C9A2, $0F00F934, $9609A88E, $E10E9818
  Data.l $7F6A0DBB, $086D3D2D, $91646C97, $E6635C01, $6B6B51F4
  Data.l $1C6C6162, $856530D8, $F262004E, $6C0695ED, $1B01A57B
  Data.l $8208F4C1, $F50FC457, $65B0D9C6, $12B7E950, $8BBEB8EA
  Data.l $FCB9887C, $62DD1DDF, $15DA2D49, $8CD37CF3, $FBD44C65
  Data.l $4DB26158, $3AB551CE, $A3BC0074, $D4BB30E2, $4ADFA541
  Data.l $3DD895D7, $A4D1C46D, $D3D6F4FB, $4369E96A, $346ED9FC
  Data.l $AD678846, $DA60B8D0, $44042D73, $33031DE5, $AA0A4C5F
  Data.l $DD0D7CC9, $5005713C, $270241AA, $BE0B1010, $C90C2086
  Data.l $5768B525, $206F85B3, $B966D409, $CE61E49F, $5EDEF90E
  Data.l $29D9C998, $B0D09822, $C7D7A8B4, $59B33D17, $2EB40D81
  Data.l $B7BD5C3B, $C0BA6CAD, $EDB88320, $9ABFB3B6, $03B6E20C
  Data.l $74B1D29A, $EAD54739, $9DD277AF, $04DB2615, $73DC1683
  Data.l $E3630B12, $94643B84, $0D6D6A3E, $7A6A5AA8, $E40ECF0B
  Data.l $9309FF9D, $0A00AE27, $7D079EB1, $F00F9344, $8708A3D2
  Data.l $1E01F268, $6906C2FE, $F762575D, $806567CB, $196C3671
  Data.l $6E6B06E7, $FED41B76, $89D32BE0, $10DA7A5A, $67DD4ACC
  Data.l $F9B9DF6F, $8EBEEFF9, $17B7BE43, $60B08ED5, $D6D6A3E8
  Data.l $A1D1937E, $38D8C2C4, $4FDFF252, $D1BB67F1, $A6BC5767
  Data.l $3FB506DD, $48B2364B, $D80D2BDA, $AF0A1B4C, $36034AF6
  Data.l $41047A60, $DF60EFC3, $A867DF55, $316E8EEF, $4669BE79
  Data.l $CB61B38C, $BC66831A, $256FD2A0, $5268E236, $CC0C7795
  Data.l $BB0B4703, $220216B9, $5505262F, $C5BA3BBE, $B2BD0B28
  Data.l $2BB45A92, $5CB36A04, $C2D7FFA7, $B5D0CF31, $2CD99E8B
  Data.l $5BDEAE1D, $9B64C2B0, $EC63F226, $756AA39C, $026D930A
  Data.l $9C0906A9, $EB0E363F, $72076785, $05005713, $95BF4A82
  Data.l $E2B87A14, $7BB12BAE, $0CB61B38, $92D28E9B, $E5D5BE0D
  Data.l $7CDCEFB7, $0BDBDF21, $86D3D2D4, $F1D4E242, $68DDB3F8
  Data.l $1FDA836E, $81BE16CD, $F6B9265B, $6FB077E1, $18B74777
  Data.l $88085AE6, $FF0F6A70, $66063BCA, $11010B5C, $8F659EFF
  Data.l $F862AE69, $616BFFD3, $166CCF45, $A00AE278, $D70DD2EE
  Data.l $4E048354, $3903B3C2, $A7672661, $D06016F7, $4969474D
  Data.l $3E6E77DB, $AED16A4A, $D9D65ADC, $40DF0B66, $37D83BF0
  Data.l $A9BCAE53, $DEBB9EC5, $47B2CF7F, $30B5FFE9, $BDBDF21C
  Data.l $CABAC28A, $53B39330, $24B4A3A6, $BAD03605, $CDD70693
  Data.l $54DE5729, $23D967BF, $B3667A2E, $C4614AB8, $5D681B02
  Data.l $2A6F2B94, $B40BBE37, $C30C8EA1, $5A05DF1B, $2D02EF8D 
EndDataSection
;}

*test = AllocateMemory(1000000000)


start = ElapsedMilliseconds()
test1 = CRC32Fingerprint(*test,1000000000) 
Zeit1 = ElapsedMilliseconds()-start

start = ElapsedMilliseconds()
test2 = CRC32_Mem(*test,1000000000)
Zeit2 = ElapsedMilliseconds()-start


OpenConsole()
PrintN("Test 1 : "+Str(test1)+"  Zeit : "+Str(Zeit1))
PrintN("Test 2 : "+Str(test2)+"  Zeit : "+Str(Zeit2))

Input()

CloseConsole()

Test 1 : 1676957506 Zeit : 18406
Test 2 : 1676957506 Zeit : 23407

[cxAlex]

Hast du den Debugger aktiviert?

Bei mir gibt der Code:

Test 1 : 1676957506 Zeit : 2781
Test 2 : 1676957506 Zeit : 5297

Immer noch knapp doppelt so lange

[alter Mann]

nein

deswegen auch Ausgabe auf Console

Compileroption: Windows , Alle CPU

getestet mit Dell Laptop Pentium 4 HT 3.2GHz Windows XP