Une alternative plus rapide que le Crc32.

Ollivier · Message par **Ollivier** » lun. 30/mars/2009 7:34

Je suis à la recherche d'une méthode pour "digérer" les chaînes et obtenir une empreinte dans le but des tableaux associatifs ou "hashmap".

Voici une suggestion. Ce code "xore" tout ce qui se situe dans la chaîne d'entrée par paquets de 4 octets. Il est plus rapide que le Crc32 (4 fois plus rapide) ce qui laisse de la marge pour résoudre le problème suivant:

* ne digère pas ou très mal les chaînes répétant le même caractère.

Avant que je ne me prenne la tête sur une méthode lambda, qui, si ça se trouve va déboucher sur quelque chose d'inexact, est-ce que quelqu'un aurait une piste?

Voilà. Merci.

Ollivier

Code : Tout sélectionner

Macro Digest24(Adr,Length,Result)

; EAX, EBX, ESI, EDI and EBP are like 5 variables in PB
; Their format is 32 bits

; AL, BL are others variables
; but their format is 8 bits
; With more precision, 
;     AL = EAX & $FF
; And BL = EBX & $FF

!  XOR     EAX, EAX          ; EAX = 0
!  XOR     EBX, EBX          ; EBX = 0

!  MOV     ESI, [v_#Adr]     ; ESI = Adr
!  MOV     EDI, ESI          ; EDI = ESI (Copy)
!  ADD     ESI, [v_#Length]  ; ESI + Length
!  SUB     ESI, 4            ; ESI - 4
!  STD                       ; Indicates LODS statements
                             ; will DECREASE ESI
                             ; (<>  CLD <=> INCREASE ESI)
!  JMP     l_digestentry
                           
DigestLoop:                  ; Start loop 
!  LODSD                     ; EAX = PeekL(ESI): ESI - 4
!  XOR     EBX, EAX          ; EBX ! EAX
DigestEntry:
!  CMP     ESI, EDI          ; ESI > EDI ?
!  JG      l_digestloop      ; Yes, loop again
                             ; ESI < EDI ?
!  JL      l_digestcorrect   ; Do the correction
                             ; ESI = EDI ?
                             ; Do the last loop
!  LODSD                     ; EAX = PeekL(ESI): ESI - 4
!  XOR     EBX, EAX          ; EBX ! EAX
!  JMP     l_digestdone      ; Quit
                           
DigestCorrect:               ; Correction   
!  LODSB                     ; AL = PeekB(ESI): ESI - 1
!  XOR     BL,  AL           ; BL ! AL
!  MOV     EBP, ESI          ; EBP = ESI (copy)
!  SUB     EBP, EDI          ; EBP - EDI
!  CMP     EBP, -2           ; EBP = -2 ?
!  JZ      l_digestlastcorrect ; Yes, do the last correction
!  ROR     EBX, 8            ; Rotate EBX
!  LODSB                     ; AL = PeekB(ESI): ESI - 1
!  XOR     BL,  AL           ; BL ! AL

DigestLastCorrect:
!  ROR     EBX, 8            ; Rotate EBX
!  LODSB                     ; AL = PeekB(ESI): ESI - 1
!  XOR     BL,  AL           ; BL ! AL

DigestDone:                  ; Reduce from 32 to 24 bits

!  MOV     AL,  BL           ; Pick the first byte

!  ROR     EBX, 8            ; Take the second byte...
!  XOR     BL,  AL           ; And stamp it
!  ROR     EBX, 8            ; Take the third byte...
!  XOR     BL,  AL           ; And stamp it
!  ROR     EBX, 8            ; Take the fourth byte...
!  XOR     BL,  AL           ; And stamp it again
!  ROR     EBX, 16           ; Leave all
!  AND     EBX, 0x00FFFFFF   ; And free the first
!  MOV     [v_#Result], EBX  ; Result = EBX

!  CLD                       ; Clear Direction flag
EndMacro

Define Chn.S

Chn = "Petit test..."
AdChn = @Chn
LnChn = Len(Chn)
MD24.I
Digest24(AdChn,LnChn,MD24)
Debug Hex(MD24)