SHA256

[walbus]

[Christian+]

Ich habe mal noch ein paar kleine Änderungen gemacht.
Zumindest bei meinen PC und meinen Testdaten konnte ich so 1/4 der Laufzeit für die Hash Berechnung einsparen.
Noch mehr zu optimieren wird aber glaube ich schwer zumindest fehlt mir gerade eine Idee an welcher Stelle ich noch was ändern könnte.

[ts-soft]

Ich wüßte noch ne Optimierung für Faule

Der Parameter Size.q sollte bei manchen Proceduren Optional sein, z.B.:

Code: Alles auswählen

Procedure.i SHA256(*Memory, Size.q = #PB_Any)
  Protected *Id = ExamineSHA256()
  If Size = #PB_Any : Size = MemorySize(*Memory) : EndIf
  NextSHA256(*Id, *Memory, Size)
  ProcedureReturn FinishSHA256(*Id)
EndProcedure

Procedure.s SHA256Fingerprint(*Memory, Size.q = #PB_Any)
  Protected *Hash, Hash.s
  If Size = #PB_Any : Size = MemorySize(*Memory) : EndIf
  *Hash = SHA256(*Memory, Size)
  Hash = HexSHA256(*Hash)
  FreeMemory(*Hash)
  ProcedureReturn Hash
EndProcedure

Solange es um mit PB allokierten Speicher handelt, kannst Du die größe ja selber ermitteln.

Gruß
Thomas

[Christian+]

Danke für den Hinweis habe ich gleich mal übernommen.

[Helle]

Eine kleine Einsparung:
Anstatt

Code: Alles auswählen

Procedure ProcessChunk(*Id.SHA256DATA)
  Protected *k.LongArray = ?k
  Protected.l a, b, c, d, e, f, g, h, t1, t2, s0, s1, maj, ch
  Protected.i i
  For i = 0 To 16 : *Id\Chunk\l[i] = EndianSwap32(*Id\Chunk\l[i]) : Next
  ....

reicht

Code: Alles auswählen

Procedure ProcessChunk(*Id.SHA256DATA)
  Protected *k.LongArray = ?k
  Protected.l a, b, c, d, e, f, g, h, t1, t2, s0, s1, maj, ch
  Protected.i i
  For i = 0 To 15 : *Id\Chunk\l[i] = EndianSwap32(*Id\Chunk\l[i]) : Next
  ...

W[16] wird ja wieder überschrieben. Bringt aber sicher nicht viel, ist nur eine kleine Ungenauigkeit.
Ich kann mich irgendwie erinnern, das ich damals in der ASM-Variante mal die Datas gleich in Little-Endian umwandeln wollte, um etwas Swappen einzusparen. Faul wie ich bin und eben weil es mit der ASM-Instruction BSWAP so schön einfach und schnell geht, habe ich das nie verwirklicht. Vielleicht bringt es in der reinen PB-Version etwas Nennenswertes.
Ihr könnt es ja mal ausprobieren!
Viel Erfolg und
Helle

[walbus]

[Christian+]

So ich habe in PB zwar noch nie wirklich was mit Assembler gemacht, aber irgendwie hat mich jetzt doch interessiert wie viel schneller noch möglich wäre.
Also habe ich mal mich hingesetzt und an meine recht geringen, eingestaubten Assembler Kenntnisse zurückerinnert um etwas Code zu produzieren der Hoffentlich nicht ganz unbrauchbar ist auch wenn es gewiss noch viel besser geht.
Herausgekommen ist diese Version, die unter x64 eine in Assembler implementierte ProcessChunk Methode verwendet.
Dadurch ist diese Version zumindest auf meinem System nochmal mehr als 5-mal schneller.

Code: Alles auswählen

; ==================================================================================================
; --- Program         : Module SHA256
; --- Author          : Christian+
; --- Source          : http://purebasic.fr/german/viewtopic.php?p=309915#p309915
; --- Date            : August 09, 2013
; --- Compiler        : PureBasic 5.20 beta 8
; --- Target OS       : All
; ==================================================================================================
;
; Komplett in Pure Basic umgesetztes Modul für SHA 256.
;
; ==================================================================================================

DeclareModule SHA256

Structure SHA256DATA
  Size.q
  ChunkSize.i
  *Hash.LongArray
  *Chunk.LongArray
EndStructure

Declare.i ExamineSHA256()
Declare   NextSHA256(*Id.SHA256DATA, *Memory, Size.q)
Declare.i FinishSHA256(*Id.SHA256DATA)

Declare.i SHA256(*Memory, Size.q = #PB_Any)
Declare.i SHA256String(String.s, Format.i = #PB_Ascii)
Declare.i SHA256File(FileName.s)

Declare.s ConvertToHexString(*Hash)

Declare.s FinishSHA256Fingerprint(*Id.SHA256DATA)

Declare.s SHA256Fingerprint(*Memory, Size.q = #PB_Any)
Declare.s SHA256StringFingerprint(String.s, Format.i = #PB_Ascii)
Declare.s SHA256FileFingerprint(FileName.s)

EndDeclareModule

; ==================================================================================================

Module SHA256

EnableExplicit

DisableDebugger

Structure LongArray
  l.l[0]
EndStructure

Macro RightShift(Number, Count)
  ((Number >> Count) & (~($FFFFFFFF << (32 - Count))))
EndMacro

Macro RightRotate(Number, Count)
  (RightShift(Number, Count) | (Number << (32 - Count)))
EndMacro

Procedure.l EndianSwap32(x.l)
  ProcedureReturn x<<24 | ((x<<8) & $00FF0000) | ((x>>8) & $0000FF00) | ((x>>24) & $000000FF)
EndProcedure

Procedure.q EndianSwap64(x.q)
  Protected z.q = x << 56
  z = z | ((x << 40) & $00FF000000000000)
  z = z | ((x << 24) & $0000FF0000000000)
  z = z | ((x <<  8) & $000000FF00000000)
  z = z | ((x >>  8) & $00000000FF000000)
  z = z | ((x >> 24) & $0000000000FF0000)
  z = z | ((x >> 40) & $000000000000FF00)
  z = z | ((x >> 56) & $00000000000000FF)
  ProcedureReturn z
EndProcedure

DataSection
  k:
  Data.l $428a2f98, $71374491, $b5c0fbcf, $e9b5dba5, $3956c25b, $59f111f1, $923f82a4, $ab1c5ed5
  Data.l $d807aa98, $12835b01, $243185be, $550c7dc3, $72be5d74, $80deb1fe, $9bdc06a7, $c19bf174
  Data.l $e49b69c1, $efbe4786, $0fc19dc6, $240ca1cc, $2de92c6f, $4a7484aa, $5cb0a9dc, $76f988da
  Data.l $983e5152, $a831c66d, $b00327c8, $bf597fc7, $c6e00bf3, $d5a79147, $06ca6351, $14292967
  Data.l $27b70a85, $2e1b2138, $4d2c6dfc, $53380d13, $650a7354, $766a0abb, $81c2c92e, $92722c85
  Data.l $a2bfe8a1, $a81a664b, $c24b8b70, $c76c51a3, $d192e819, $d6990624, $f40e3585, $106aa070
  Data.l $19a4c116, $1e376c08, $2748774c, $34b0bcb5, $391c0cb3, $4ed8aa4a, $5b9cca4f, $682e6ff3
  Data.l $748f82ee, $78a5636f, $84c87814, $8cc70208, $90befffa, $a4506ceb, $bef9a3f7, $c67178f2
EndDataSection

Procedure.i ExamineSHA256()
  Protected *Id.SHA256DATA = AllocateMemory(SizeOf(SHA256DATA))
  *Id\Hash = AllocateMemory(32, #PB_Memory_NoClear)
  *Id\Chunk = AllocateMemory(256, #PB_Memory_NoClear)
  *Id\Hash\l[0] = $6A09E667 : *Id\Hash\l[1] = $BB67AE85 : *Id\Hash\l[2] = $3C6EF372 : *Id\Hash\l[3] = $A54FF53A 
  *Id\Hash\l[4] = $510E527F : *Id\Hash\l[5] = $9B05688C : *Id\Hash\l[6] = $1F83D9AB : *Id\Hash\l[7] = $5BE0CD19
  ProcedureReturn *Id
EndProcedure

CompilerIf #PB_Compiler_Processor = #PB_Processor_x64

Procedure ProcessChunk(*Id.SHA256DATA)
  Protected k = ?k
  Protected Chunk = *Id\Chunk
  Protected Hash = *Id\Hash
  ;Swap Endian
  !MOV rax, [p.v_Chunk]
  !MOV rcx, 0
  !SwapEndianLoop:
    !MOV ebx, [rax]
    !BSWAP ebx
    !MOV [rax], ebx
    !ADD rax, 4
  !INC rcx 
  !CMP rcx, 16
  !JNE SwapEndianLoop
  ;*Chunk + 16*4
  !MOV r8, [p.v_Chunk]
  !ADD r8, 64
  ;For i = 16 To 63
  !MOV rcx, 16
  !ExpandLoop:
    ;c15 = *Id\Chunk\l[i-15]
    !MOV eax, [r8 - 15*4]
    ;s0 = RightRotate(c15, 7) ! RightRotate(c15, 18) ! RightShift(c15, 3)
    !MOV ebx, eax
    !SHR ebx, 3
    !ROR eax, 7
    !XOR ebx, eax
    !ROR eax, 11
    !XOR ebx, eax
    ;c2 = *Id\Chunk\l[i-2]
    !MOV eax, [r8 - 2*4]
    ;s1 = RightRotate(c2, 17) ! RightRotate(c2, 19) ! RightShift(c2, 10)
    !MOV edx, eax
    !SHR edx, 10
    !ROR eax, 17
    !XOR edx, eax
    !ROR eax, 2
    !XOR edx, eax
    ;*Id\Chunk\l[i] = *Id\Chunk\l[i-16] + s0 + *Id\Chunk\l[i-7] + s1
    !ADD ebx, edx
    !ADD ebx, [r8 - 16*4]
    !ADD ebx, [r8 - 7*4]
    !MOV [r8], ebx
    ;*Chunk + 4
    !ADD r8, 4
  ;Next
  !INC rcx 
  !CMP rcx, 64
  !JNE ExpandLoop
  ;a = *Id\Hash\l[0] : b = *Id\Hash\l[1] : c = *Id\Hash\l[2] : d = *Id\Hash\l[3]
  ;e = *Id\Hash\l[4] : f = *Id\Hash\l[5] : g = *Id\Hash\l[6] : h = *Id\Hash\l[7]
  !MOV rax, [p.v_Hash]
  !MOV r8d, [rax]
  !MOV r9d, [rax+4]
  !MOV r10d, [rax+8]
  !MOV r11d, [rax+12]
  !MOV r12d, [rax+16]
  !MOV r13d, [rax+20]
  !MOV r14d, [rax+24]
  !MOV r15d, [rax+28]
  ;For i = 0 To 63
  !MOV rcx, 0
  !ProcessLoop:
    ;s1 = RightRotate(e, 6) ! RightRotate(e, 11) ! RightRotate(e, 25)
    !MOV eax, r12d
    !ROR eax, 6
    !MOV ebx, eax
    !ROR eax, 5
    !XOR ebx, eax
    !ROR eax, 14
    !XOR eax, ebx
    ;ch = (e & f) ! ((~ e) & g)
    !MOV ebx, r12d
    !AND ebx, r13d
    !MOV edx, r12d
    !NOT edx
    !AND edx, r14d
    !XOR ebx, edx
    ;t1 = h + S1 + ch + *k\l + *Chunk\l 
    !ADD r15d, eax
    !ADD r15d, ebx
    !MOV rax, [p.v_k]
    !MOV ebx, [rax]
    !ADD rax, 4 ;*k+4
    !MOV [p.v_k], rax
    !ADD r15d, ebx
    !MOV rax, [p.v_Chunk]
    !MOV ebx, [rax]
    !ADD rax, 4 ;*Chunk+4
    !MOV [p.v_Chunk], rax
    !ADD r15d, ebx
    ;maj = (a & b) ! (a & c) ! (b & c)
    !MOV eax, r8d
    !AND eax, r9d
    !MOV ebx, r8d
    !AND ebx, r10d
    !XOR eax, ebx
    !MOV ebx, r9d
    !AND ebx, r10d
    !XOR eax, ebx
    ;s0 = RightRotate(a, 2) ! RightRotate(a, 13) ! RightRotate(a, 22)
    !MOV edx, r8d
    !ROR edx, 2
    !MOV ebx, edx
    !ROR edx, 11
    !XOR ebx, edx
    !ROR edx, 9
    !XOR edx, ebx
    ;t2 = S0 + maj
    !ADD eax, edx
    ;t1
    !MOV ebx, r15d
    ;h = g : g = f : f = e : e = d + t1
    !MOV r15d, r14d
    !MOV r14d, r13d
    !MOV r13d, r12d
    !MOV r12d, r11d
    !ADD r12d, ebx
    ;d = c : c = b : b = a : a = t1 + t2
    !MOV r11d, r10d
    !MOV r10d, r9d
    !MOV r9d, r8d
    !MOV r8d, eax
    !ADD r8d, ebx
  ;Next
  !INC rcx 
  !CMP rcx, 64
  !JNE ProcessLoop
  ;*Id\Hash\l[0] + a : *Id\Hash\l[1] + b : *Id\Hash\l[2] + c : *Id\Hash\l[3] + d
  ;*Id\Hash\l[4] + e : *Id\Hash\l[5] + f : *Id\Hash\l[6] + g : *Id\Hash\l[7] + h
  !MOV rax, [p.v_Hash]
  !ADD r8d, [rax]
  !ADD r9d, [rax+4]
  !ADD r10d, [rax+8]
  !ADD r11d, [rax+12]
  !ADD r12d, [rax+16]
  !ADD r13d, [rax+20]
  !ADD r14d, [rax+24]
  !ADD r15d, [rax+28]
  !MOV [rax], r8d
  !MOV [rax+4], r9d
  !MOV [rax+8], r10d
  !MOV [rax+12], r11d
  !MOV [rax+16], r12d
  !MOV [rax+20], r13d
  !MOV [rax+24], r14d
  !MOV [rax+28], r15d
EndProcedure

CompilerElse

Procedure ProcessChunk(*Id.SHA256DATA)
  Protected *k.Long = ?k
  Protected *Chunk.Long = *Id\Chunk
  Protected.i a, b, c, d, e, f, g, h, t1, t2, s0, s1, maj, ch, c15, c2, i
  For i = 0 To 15 : *Id\Chunk\l[i] = EndianSwap32(*Id\Chunk\l[i]) : Next
  For i = 16 To 63
    c15 = *Id\Chunk\l[i-15]
    c2 = *Id\Chunk\l[i-2]
    s0 = RightRotate(c15, 7) ! RightRotate(c15, 18) ! RightShift(c15, 3)
    s1 = RightRotate(c2, 17) ! RightRotate(c2, 19) ! RightShift(c2, 10)
    *Id\Chunk\l[i] = *Id\Chunk\l[i-16] + s0 + *Id\Chunk\l[i-7] + s1
  Next
  a = *Id\Hash\l[0] : b = *Id\Hash\l[1] : c = *Id\Hash\l[2] : d = *Id\Hash\l[3]
  e = *Id\Hash\l[4] : f = *Id\Hash\l[5] : g = *Id\Hash\l[6] : h = *Id\Hash\l[7]  
  For i = 0 To 63
    s0 = RightRotate(a, 2) ! RightRotate(a, 13) ! RightRotate(a, 22)
    maj = (a & b) ! (a & c) ! (b & c)
    t2 = S0 + maj
    s1 = RightRotate(e, 6) ! RightRotate(e, 11) ! RightRotate(e, 25)
    ch = (e & f) ! ((~ e) & g)
    t1 = h + S1 + ch + *k\l + *Chunk\l 
    h = g : g = f : f = e : e = d + t1
    d = c : c = b : b = a : a = t1 + t2
    *k+4
    *Chunk+4
  Next
  *Id\Hash\l[0] + a : *Id\Hash\l[1] + b : *Id\Hash\l[2] + c : *Id\Hash\l[3] + d
  *Id\Hash\l[4] + e : *Id\Hash\l[5] + f : *Id\Hash\l[6] + g : *Id\Hash\l[7] + h
EndProcedure

CompilerEndIf

Procedure NextSHA256(*Id.SHA256DATA, *Memory, Size.q)
  Protected.i d, NumberOfChunks, i
  *Id\Size + Size
  If *Id\ChunkSize > 0
    d = (64 - *Id\ChunkSize)
    If d > Size : d = Size : EndIf
    CopyMemory(*Memory, *Id\Chunk + *Id\ChunkSize, d)
    *Memory + d : Size - d : *Id\ChunkSize + d
    If *Id\ChunkSize = 64
      ProcessChunk(*Id.SHA256DATA)
      *Id\ChunkSize = 0
    EndIf
  EndIf
  NumberOfChunks = Size / 64
  For i = 0 To NumberOfChunks - 1
    CopyMemory(*Memory+i*64, *Id\Chunk, 64)
    ProcessChunk(*Id)
  Next
  If Size % 64 <> 0
    CopyMemory(*Memory + NumberOfChunks * 64, *Id\Chunk, Size % 64)
    *Id\ChunkSize = Size % 64
  EndIf
EndProcedure

Procedure.i FinishSHA256(*Id.SHA256DATA)
  Protected i.i
  Protected *Hash = *Id\Hash
  Protected BitLength.q = *Id\Size * 8 + 1 + 64
  If BitLength % 512 <> 0
    BitLength = BitLength + (512 - (BitLength % 512))
  EndIf
  FillMemory(*Id\Chunk+*Id\ChunkSize, 64-*Id\ChunkSize, 0)
  PokeA(*Id\Chunk+*Id\ChunkSize, $80)
  If (BitLength/8 - *Id\Size) > 64
    ProcessChunk(*Id)
    FillMemory(*Id\Chunk, 64, 0)
  EndIf
  PokeQ(*Id\Chunk + 64 - 8, EndianSwap64(*Id\Size*8))
  ProcessChunk(*Id)
  For i = 0 To 7 : *Id\Hash\l[i] = EndianSwap32(*Id\Hash\l[i]) : Next
  FreeMemory(*Id\Chunk)
  FreeMemory(*Id)
  ProcedureReturn *Id\Hash
EndProcedure

Procedure.i SHA256(*Memory, Size.q = #PB_Any)
  Protected *Id = ExamineSHA256()
  If Size = #PB_Any : Size = MemorySize(*Memory) : EndIf
  NextSHA256(*Id, *Memory, Size)
  ProcedureReturn FinishSHA256(*Id)
EndProcedure

Procedure.i SHA256String(String.s, Format.i = #PB_Ascii)
  Protected Size.i, *Memory, *Hash
  Size = StringByteLength(String, Format)
  *Memory = AllocateMemory(Size + 1)
  PokeS(*Memory, String, -1, Format)
  *Hash = SHA256(*Memory, Size)
  FreeMemory(*Memory)
  ProcedureReturn *Hash
EndProcedure

Procedure.i SHA256File(FileName.s)
  Protected Size.i, File.i = ReadFile(#PB_Any, FileName)
  If Not File : ProcedureReturn 0 : EndIf
  Protected *Id = ExamineSHA256()
  Protected *Memory = AllocateMemory(640000, #PB_Memory_NoClear)
  While Not Eof(File)
    Size = ReadData(File, *Memory, 640000)
    NextSHA256(*Id, *Memory, Size)
  Wend
  FreeMemory(*Memory)
  CloseFile(File)
  ProcedureReturn FinishSHA256(*Id)
EndProcedure

Macro HexByte(Hash)
  RSet(Hex(PeekA(Hash), #PB_Ascii), 2, "0")
EndMacro

Macro HexLong(Hash)
  HexByte(Hash) + HexByte(Hash+1) + HexByte(Hash+2) + HexByte(Hash+3)
EndMacro

Macro HexSHA256(Hash)
  HexLong(Hash) + HexLong(Hash+4) + HexLong(Hash+8) + HexLong(Hash+12) + HexLong(Hash+16) + HexLong(Hash+20) + HexLong(Hash+24) + HexLong(Hash+28)
EndMacro

Procedure.s ConvertToHexString(*Hash)
  ProcedureReturn HexSHA256(*Hash)
EndProcedure

Procedure.s FinishSHA256Fingerprint(*Id.SHA256DATA)
  Protected *Hash, Hash.s
  *Hash = FinishSHA256(*Id.SHA256DATA)
  Hash = HexSHA256(*Hash)
  FreeMemory(*Hash)
  ProcedureReturn Hash
EndProcedure

Procedure.s SHA256Fingerprint(*Memory, Size.q = #PB_Any)
  Protected *Hash, Hash.s
  If Size = #PB_Any : Size = MemorySize(*Memory) : EndIf
  *Hash = SHA256(*Memory, Size)
  Hash = HexSHA256(*Hash)
  FreeMemory(*Hash)
  ProcedureReturn Hash
EndProcedure

Procedure.s SHA256StringFingerprint(String.s, Format.i = #PB_Ascii)
  Protected *Hash, Hash.s
  *Hash = SHA256String(String, Format)
  Hash = HexSHA256(*Hash)
  FreeMemory(*Hash)
  ProcedureReturn Hash
EndProcedure

Procedure.s SHA256FileFingerprint(FileName.s)
  Protected *Hash, Hash.s
  *Hash = SHA256File(FileName)
  Hash = HexSHA256(*Hash)
  FreeMemory(*Hash)
  ProcedureReturn Hash
EndProcedure

EndModule

;- Beispiele
CompilerIf #PB_Compiler_IsMainFile
  
  EnableExplicit
  
  Define String.s, *Hash
  
  String = ""
  Debug SHA256::SHA256StringFingerprint(String, #PB_Ascii)
  Debug UCase("e3b0c44298fc1c149afbf4c8996fb92427ae41e4649b934ca495991b7852b855")
  
  Debug "---------------------------------------------------------------------"
  
  String = "The quick brown fox jumps over the lazy dog"
  Debug SHA256::SHA256StringFingerprint(String, #PB_Ascii)
  Debug UCase("d7a8fbb307d7809469ca9abcb0082e4f8d5651e46d3cdb762d02d0bf37c9e592")
  
  Debug "---------------------------------------------------------------------"
  
  String = "The quick brown fox jumps over the lazy dog."
  Debug SHA256::SHA256StringFingerprint(String, #PB_Ascii)
  Debug UCase("ef537f25c895bfa782526529a9b63d97aa631564d5d789c2b765448c8635fb6c")
  
  Debug "---------------------------------------------------------------------"
  
  String = "Franz jagt im komplett verwahrlosten Taxi quer durch Bayern"
  Debug SHA256::SHA256StringFingerprint(String, #PB_Ascii)
  Debug UCase("d32b568cd1b96d459e7291ebf4b25d007f275c9f13149beeb782fac0716613f8")
  
  Debug "---------------------------------------------------------------------"
  
  String = "Frank jagt im komplett verwahrlosten Taxi quer durch Bayern"
  Debug SHA256::SHA256StringFingerprint(String, #PB_Ascii)
  Debug UCase("78206a866dbb2bf017d8e34274aed01a8ce405b69d45db30bafa00f5eeed7d5e")
  
CompilerEndIf

; ==================================================================================================

[NicTheQuick]

Wenn du jetzt noch das hier auf entsprechend bestückten Prozessoren nutzt, geht's nochmal mehr ab: AES Befehlssatzerweiterung