Comparer des fichiers binaires - faire un patch

[Octavius]

Alors voici le problème, j'ai un programme A version 1 et le même programme A version 2.

Je voudrais programmer un programme B qui puisse comparer la v2 à la v1 et créer un patch exécutable. Le hic c'est que je ne sais pas comment m'y prendre.

Evidemment je sais que des petits programmes comme ça existent déjà sur internet, mais mon but c'est surtout d'apprendre, je n'en ai pas vraiment l'utilité actuellement.

Pour commencer c'est surtout la première étape qui m'intéresse : comparer les bits un à un de v1 et v2, repérer les blocs de bits ajoutés, supprimés, déplacés, inversés, etc. et stocker ces informations pour pouvoir les réutiliser pour le patch.

Je n'arrive pas à trouver ce qu'il me faut sur le forum ou sur le net pour apprendre (méthodes générales, bouts de codes, etc.), merci de votre aide.

[Fred]

Pourquoi ne pas remplacer totalement l'executable ?

[Octavius]

Parce que je veux apprendre !

Certes, les exécutables sont très souvents de petite taille, mais la technique serait applicable à des fichiers binaires qui pourraient être bien plus gros, images, sons, vidéos, archives, etc.

Comme je l'ai dis, ce qui m'intéresse c'est d'apprendre une ou des méthodes qui me permet de comparer des blocs de données brutes.

[cha0s]

Je sait pas comment fonctionne le compilateur de purebasic mais pour par exemple gcc le code peut être optimisé a la compilation, donc une modification même mineure peut avoir un gros impacte sur la structure de l'exécutable donc je ne sait pas si c'est très intéressant pour cette exemple.

Sinon ba faut faire des comparaison, le mieux est de prendre des gros type comme des entiers pour comparer, sa sera moins précis que octet par octet mais plus rapide. Après tu stocke que les modifications et ne garde que les données significative (des blocs > 1Mo par exemple).

Il faut aussi penser a vérifier que les données non pas été altérée donc le mieux serait d'avoir un hachage du fichier final.

[Backup]

tu veux faire un patcher en fait

genre
original_protegé
copy_sans protection

patch=difference

c'est assez simple

tu lis octet par octet, l'original , et en meme temps la copy
et lorsqu'il y a une différence tu note la position du pointeur de lecture (c'est a dire la position de l'octet lu (offset))
et tu ecris dans un fichier 'patch.txt' la position,et l'octet de "copy_sans_protection"

ensuite il te faut une partie "Patcher" (un bouton)
qui va relire le fichier "Patch.txt"
et va pouvoir appliquer a un "original_protege" , les modifications a faire
qui sont ecrite dans le fichier 'patch.txt'

si c'est ecrit dans patch.txt qu'a l'octet 20 , il faut mettre E4
ben tu le fait au 20 eme octet de "original_protege" , tu ecris E4
rien de plus simple a faire !

toute ressemblance avec une histoire deja vecu serai purement fortuite....

ne me cherchez plus , je suis parti loin ....

[Cls]

Ça a l'air très simple, c'est en réalité assez compliqué ! En effet tu ne peux pas faire une comparaison bit à bit classique, il te faut utiliser un algorithme de comparaison du genre diff. Le code source de diff est dispo ici : http://perl.plover.com/diff/Diff.pm

Un lien qui peut t'aider : http://perso.telecom-paristech.fr/~tale ... book1.html

Bon courage en tout cas !

Edit : grillé par Dobro ! Les problèmes commencent lorsque les tailles des fichiers comparés différent.

[Backup]

Edit : grillé par Dobro ! Les problèmes commencent lorsque les tailles des fichiers comparés différent.

pas vraiment !

puisqu'il suffit de prendre la copy comme etant la reference de longueur

apres tout c'est le résultat qui compte !!
on part du principe que l'original on s'en fou , puisqu'il a ete modifié dans ce sens

c'est donc la copy qui sera la reference de taille a lire (offset)
tout ce qui dans "l'original a modifier" dépasse la longueur de copy , on vire (tronquage):D

partant du principe que tout les executables on besoin de leur entete , en principe la partie qui peux sauter se trouve a la fin ...

ou au milieu mais ça reviens a raccourcir le fichiers

mais dans l'absolu , si tu modifie un original par certains octets bien placé
tu ne change guere la taille
ou au pire , meme si tu cree une copy avec des octets modifié + les octets en rabe
de l'original , on s'en fou ça va quand meme marcher

le prg cheminera dans les nouvelles instructions
meme si des trace des anciennes existent toujours dans le fichier
on s'en fou

[Octavius]

Merci en tout cas, je sens que ça va m'aider ! Si j'arrive à faire un bout de code en PB je le posterai.

[Cls]

Oui tu as raison.

En fait dans ce topic il y a 2 choses : d'un coté la comparaison de fichiers et de l'autre le mécanisme de patch. Faire un patch s'avère simple, comparer 2 fichiers beaucoup moins.

[Backup]

comparer 2 fichiers beaucoup moins.

oui c'est vrais

[Octavius]

Ton lien, Cls, m'a orienté vers un programme dont la méthode serait de comparer deux séquences de bits et de trouver la plus longue sous-séquence commune.

[Octavius]

Voici un petit programme que j'ai pondu en tant que préliminaire, ça permet de trouver la plus longue séquence commune entre deux chaînes de caractères situées dans 2 fichiers texte.

Code : Tout sélectionner

EnableExplicit

Define Event.i

Procedure.s FindLCS(File_0.s,File_1.s)

Protected *Address_0,*Address_1

If OpenFile(0,File_0)=0 : ProcedureReturn "" : EndIf
If OpenFile(1,File_1)=0 : CloseFile(0) : ProcedureReturn "" : EndIf

*Address_0=AllocateMemory(Lof(0))
*Address_1=AllocateMemory(Lof(1))

ReadData(0,*Address_0,Lof(0))
ReadData(1,*Address_1,Lof(1))

CloseFile(0)
CloseFile(1)

Protected Dim Matrix.s(MemorySize(*Address_0)+1,MemorySize(*Address_1)+1)
Protected i.i,j.i

For j=1 To MemorySize(*Address_1)
  For i=1 To MemorySize(*Address_0)
    If PeekB(*Address_0+i-1)=PeekB(*Address_1+j-1)
      Matrix(i,j)=Matrix(i-1,j-1)+PeekS(*Address_0+i-1,1)
    Else
      If Len(Matrix(i,j-1))>Len(Matrix(i-1,j))
        Matrix(i,j)=Matrix(i,j-1)
      Else
        Matrix(i,j)=Matrix(i-1,j)
      EndIf
    EndIf
  Next i
Next j

ProcedureReturn Matrix(MemorySize(*Address_0),MemorySize(*Address_1))

EndProcedure

OpenWindow(0,0,0,400,110,"LCS Finder, par Octavius",#PB_Window_ScreenCentered|#PB_Window_SystemMenu|#PB_Window_MinimizeGadget)
StringGadget(0,10,10,340,20,"")
StringGadget(1,10,40,340,20,"")
ButtonGadget(2,360,10,30,20,"...")
ButtonGadget(3,360,40,30,20,"...")
ButtonGadget(4,170,70,60,30,"OK")

Repeat
  
  Event=WaitWindowEvent()
  Select Event
    Case #PB_Event_Gadget
      Event=EventGadget()
      Select Event
        Case 2,3
          SetGadgetText(Event-2,OpenFileRequester("Choisir un fichier",GetCurrentDirectory(),"Tous|*.*",0))
        Case 4
          MessageRequester("LCS",FindLCS(GetGadgetText(0),GetGadgetText(1)))
      EndSelect
    Case #PB_Event_CloseWindow : End
  EndSelect
  
ForEver

J'ai essayé avec a.txt contenant : "Ceci est une chaîne de caractères !" ;
et b.txt contenant : "Cela est une autre chaîne de caractères..." ;
et le résultat qui s'affiche dans le requester est "Ce est une chaîne de caractères", ce qui est effectivement la plus longue séquence commune.

Après ça, ça devrait être relativement simple de trouver les opérations de suppression et d'insertion pour passer d'une séquence à une autre. Pour ce qui est de cet algorithme en lui-même, la technique utilisée est très proche du calcul de la distance de Levenshtein.

Pour l'instant ça ne marche qu'avec les chaînes de caractères, et seulement les petites (la taille de la matrice utilisée peut augmenter rapidement), il faut que je généralise encore ce code et que je l'optimise pour pouvoir faire ça avec n'importe quelle séquence binaire.

EDIT: pour deux séquences A et B, il peut exister plusieurs plus longue séquence commune, mon programme n'en trouve qu'une car une seule solution me suffit, je ne cherche pas à donner l'ensemble des solutions mathématiques mais pour cela il suffirait de distinguer le cas Len(Matrix(i,j-1))=Len(Matrix(i-1,j) et de stocker les 2 solutions possibles indépendamment à chaque fois que ce cas se présente.

[Cls]

Très intéressant ce code J'attends la suite impatiemment

[Ar-S]

+1, ce travail est très intéressant.