Est-il nécessaire de lire chaque octet pour vérifier si un fichier copié est identique à l'original?

J'ai récemment appris l'existence d'un programme appelé Total Commander. C'est un remplacement de l'Explorateur Windows et a ses propres trucs pour copier des fichiers. Pour vérifier si les fichiers sont identiques, au lieu de calculer un CRC, il vérifie littéralement chaque octet, un à la fois, sur l'original et la copie.

Ma question est: est-ce nécessaire? Le CRC ou toute autre technique de ce type peut-il mal tourner? Devriez-vous, en tant que programmeur, essayer d'implémenter ce système parfait mais lent, ou est-ce trop extrême?

Le calcul des CRC (ou, mieux, des sha1sums) sur les deux fichiers nécessite de toute façon de lire chaque octet. Si vous effectuez une comparaison octet par octet, vous pouvez quitter dès que vous voyez une incompatibilité - et vous n'avez pas à vous soucier de deux fichiers différents qui ont la même somme de contrôle (bien que cela soit peu probable pour sha1sum) . Donc, si vous effectuez la comparaison localement, une comparaison octet par octet sera au moins aussi rapide qu'une comparaison de somme de contrôle (sauf si vous avez déjà calculé les sommes de contrôle de toute façon).

D'un autre côté, les comparaisons de sommes de contrôle sont utiles lorsque vous comparez des fichiers qui ne sont pas sur la même machine; les sommes de contrôle peuvent être calculées localement et vous n'avez pas à transférer l'intégralité du contenu sur le réseau.

Des approches hybrides sont également possibles. Par exemple, vous pouvez calculer et comparer des sommes de contrôle pour les deux fichiers un morceau à la fois, ce qui peut éviter de lire l'intégralité des fichiers ( s'ils diffèrent) tout en évitant de transmettre l'intégralité du fichier sur le réseau. Le protocole rsync fait quelque chose comme ça.

Notez que l'utilisation d'un simple CRC vous donne une bonne chance de collision, comme Dave Rager l'a mentionné dans sa réponse. Utilisez au moins sha1sum, ou même quelque chose de plus récent. (N'essayez pas d'inventer votre propre algorithme de hachage; les personnes qui ont développé sha1sum en savent beaucoup plus sur ce genre de choses que nous deux.)

En ce qui concerne la probabilité de collision, si vous utilisez un hachage décent comme sha1sum, vous n'avez pratiquement pas à vous en soucier, à moins que quelqu'un ne construise délibérément et cher des fichiers dont les sha1sums entrent en collision (générer de telles collisions n'était pas faisable lorsque j'ai écrit ceci pour la première fois) , mais des progrès sont en cours ). Citant «Pro ​​Git» de Scott Chacon , section 6.1 :

Voici un exemple pour vous donner une idée de ce qu'il faudrait pour obtenir une collision SHA-1. Si les 6,5 milliards d'humains sur Terre étaient en train de programmer, et chaque seconde, chacun produisait du code qui était l'équivalent de toute l'histoire du noyau Linux (1 million d'objets Git) et le poussait dans un énorme référentiel Git, cela prendrait 5 ans jusqu'à ce référentiel contenait suffisamment d'objets pour avoir une probabilité de 50% de collision d'un seul objet SHA-1. Il est plus probable que tous les membres de votre équipe de programmation soient attaqués et tués par des loups dans des incidents non liés la même nuit.

Sommaire :

La comparaison octet par octet est bonne pour les comparaisons locales. sha1sum est bon pour la comparaison à distance et ne présente aucun risque significatif de faux positifs.

Voici une autre façon d'y penser.

S'il n'y a aucune possibilité que deux fichiers différents aient le même CRC, alors par extension cela signifie que chaque fichier peut être représenté par un CRC unique.Si le CRC était plus petit que le fichier d'origine, cela représenterait une forme de compression sans perte. Sinon, vous feriez tout aussi bien de comparer les fichiers d'origine puisque vous compareriez le même nombre d'octets.

En théorie, vous pouvez utiliser la compression sans perte des deux côtés de la comparaison pour réduire le nombre d'octets nécessaires dans la comparaison, mais c'est une folle course car vous perdriez plus de cycles et vous deviez lire chaque octet des deux fichiers pour effectuer la compression . Autrement dit, pour encoder chaque octet (et son ordre) dans un schéma de compression sans perte, vous devez d'abord le lire et le connecter à l'algorithme, non? Jeu terminé.

Voici une analogie:
si vous vouliez un moyen de déterminer rapidement si deux documents imprimés étaient identiques sans comparer lettre par lettre, vous pouvez comparer le nombre de lettres sur chaque ligne des documents. Si tous les chiffres concordaient, les chances d'améliorer considérablement que les documents sont identiques, mais personne ne dirait que vous pouvez être certain que chaque lettre était la même en utilisant cette approche.

La seule façon parfaite de vérifier des fichiers identiques est l'octet pour la comparaison d'octets. Une autre façon d'être une approximation juste est de calculer un hachage tel que MD5 pour les fichiers et de les comparer. Il est possible qu'il y ait une collision de hachage, mais peu probable.

J'imagine que l'octet pour la comparaison d'octets serait plus rapide que le calcul du hachage sur les deux fichiers au moment où vous effectuez la comparaison. Cependant, si votre application pré-calcule le hachage et stocke des métadonnées sur vos fichiers, la comparaison des hachages sera considérablement plus rapide.

Le CRC n'est probablement pas la voie à suivre car c'est juste un mécanisme de détection d'erreur, pas un hachage. (ou un hachage médiocre avec beaucoup de collisions possibles)

Pour être certain à 100% que deux fichiers sont identiques, il faut vraiment vérifier les octets.

Pourquoi? Collisions de hachage, c'est pourquoi! Selon l'algorithme utilisé pour le hachage, la collision peut être plus ou moins probable, mais elle est néanmoins possible. En suivant ces étapes:

1. Vérifier la taille des fichiers
2. Vérifier les types de mime
3. Vérifier le hachage
4. Vérifiez quelques décalages aléatoires et comparez les bits

Vous donnera une très grande garantie de certitude que les deux fichiers sont les mêmes, mais il y a une très (extrêmement) petite chance que vous ayez une collision aux mains. Le choix de jusqu'où vous voulez aller avec vos comparaisons sera dicté par la situation.

Comme d'autres l'ont dit, il est plus rapide de faire une comparaison octet par octet si les deux fichiers sont sur le même système. Si vous essayez de comparer un tas de fichiers, vous atteindrez le point où le hachage est la meilleure réponse si les fichiers sont en rotation.

Le hachage brille vraiment quand vous n'avez pas toutes les données disponibles. Par exemple, les fichiers se trouvent sur différentes machines. Il vous permet également d'enregistrer les résultats des calculs et de les consulter ultérieurement. (Ce rapport est-il le même que l'ancien? Lorsque vous faites le rapport, enregistrez-en un hachage. Lorsque vous faites le suivant, vous pouvez simplement comparer les hachages. Non seulement vous n'avez pas besoin de lire l'ancien en vous ne le faites pas '' je n'ai même pas besoin d'en avoir une copie.)

Je pense que vous devriez utiliser l'utilitaire de comparaison de fichiers fourni avec votre système d'exploitation ou utiliser un outil de comparaison de fichiers (voir: outils de comparaison de fichiers wiki ) pour comparer le contenu APRÈS avoir vérifié les propriétés du fichier décrites par @Glenn Nelson.

Je ne pense pas que CRC soit précis à 100% et je pense que sa précision diminue avec la longueur du fichier. De plus, je ne vous suggère pas de l'écrire à partir de zéro car cela peut nécessiter beaucoup de tests.

Est-il nécessaire de lire chaque octet pour vérifier si un fichier copié est identique à l'original? OUI pour être sûr à 100%

Est-il nécessaire de lire chaque octet pour vérifier si un fichier copié n'est PAS identique à l'original? NON

Ainsi, pour déterminer rapidement la non-identité, vérifiez d'abord les métadonnées telles que la taille du fichier et tout type de somme de contrôle / CRC ou MIME que le système d'exploitation / système de fichiers / magasin peut déjà maintenir . Puisqu'ils sont pré-calculés par ce système, vous ne payez pas ce coût au moment de la comparaison.

Si ce test réussit, vous devez toujours comparer chaque octet individuellement si vous devez être certain à 100%, MAIS NOTEZ que dans les processeurs pipelinés modernes, et en utilisant plusieurs threads et éventuellement plusieurs processeurs / CPU, faire des comparaisons de blocs de gros fichiers est VRAIMENT rapide et efficace parce que le processus est hautement parallélisable. Bien plus rapide que N'IMPORTE QUEL type de calcul mathématique impliquant chaque octet (bien que certains algorithmes soient également parallélisables, mais peut-être pas aussi facilement ou aussi bien). En effet, les processeurs pipelinés peuvent effectuer des opérations de comparaison de blocs de mémoire dans un microcode ou même du matériel (très rapide) et les sous-systèmes de disque à mémoire sont hautement optimisés pour apporter d'énormes blocs de fichiers vers / depuis la mémoire, le tout en parallèle et avec Matériel. Si votre application fait ce genre de choses régulièrement, et qu'il s'agit d'un goulot d'étranglement connu, il serait sage de l'implémenter dans un code multithread bien écrit qui tire parti des fonctionnalités de parallélisation de votre système d'exploitation et de votre matériel (utilisez peut-être un langage conçu pour cette).

Ce n'est que si vous souhaitez traiter chaque fichier une fois et faire plusieurs comparaisons plus tard (où vous vous souvenez ["mettre en cache"] le résultat d'analyse résumé ou "compressé" [comme le dit JohnFX]), qu'il y aura un avantage significatif à le faire, et même alors, seulement pour prouver la différence (probable); pour prouver l’identité, vous devez toujours effectuer la comparaison octet par octet.