¿Es necesario leer cada byte para verificar si un archivo copiado es idéntico al original?

Hace poco me enteré de un programa llamado Total Commander. Es un reemplazo del Explorador de Windows y tiene sus propias cosas para copiar archivos. Para verificar si los archivos son idénticos, en lugar de calcular un CRC, literalmente verifica cada byte, uno a la vez, tanto en el original como en la copia.

Mi pregunta es: ¿es esto necesario? ¿Puede CRC o cualquier otra técnica similar salir mal? ¿Deberías, como programador, probar e implementar este sistema perfecto pero lento, o es demasiado extremo?

El cálculo de CRC (o, mejor aún, sha1sums) en ambos archivos requiere leer cada byte de todos modos. Si hace una comparación byte por byte, puede salir tan pronto como vea una falta de coincidencia, y no tiene que preocuparse por dos archivos diferentes que tengan la misma suma de comprobación (aunque eso es muy poco probable para sha1sum) . Entonces, si está haciendo la comparación localmente, una comparación byte por byte será al menos tan rápida como una comparación de suma de verificación (a menos que ya haya calculado las sumas de verificación de todos modos).

Por otro lado, las comparaciones de suma de comprobación son útiles cuando compara archivos que no están en la misma máquina; las sumas de verificación se pueden calcular localmente y no tiene que transferir todo el contenido a través de la red.

Los enfoques híbridos también son posibles. Por ejemplo, puede calcular y comparar sumas de verificación para los dos archivos un trozo a la vez, lo que puede evitar leer los archivos completos ( si difieren) al tiempo que evita transmitir todo el archivo a través de la red. El protocolo rsync hace algo como esto.

Tenga en cuenta que el uso de un CRC simple le brinda una posibilidad justa de colisión, como Dave Rager mencionó en su respuesta. Use al menos sha1sum, o incluso algo más reciente. (No intente inventar su propio algoritmo de hash; las personas que desarrollaron sha1sum saben mucho más sobre estas cosas que cualquiera de nosotros).

En cuanto a la probabilidad de colisión, si se utiliza un hash decente como sha1sum que prácticamente no tiene que preocuparse por ello, a menos que alguien es deliberada y costoso construir archivos cuyos sha1sums chocan (generación de tales colisiones era no es factible cuando escribí por primera vez este , pero se está progresando ). Citando "Pro Git" de Scott Chacon , sección 6.1 :

Aquí hay un ejemplo para darle una idea de lo que se necesitaría para obtener una colisión SHA-1. Si todos los 6.500 millones de humanos en la Tierra estuvieran programando, y cada segundo, cada uno produjera código que fuera el equivalente de toda la historia del kernel de Linux (1 millón de objetos Git) y lo empujara a un enorme repositorio Git, tomaría 5 años hasta ese repositorio contenía suficientes objetos para tener una probabilidad del 50% de una sola colisión de objetos SHA-1. Existe una mayor probabilidad de que cada miembro de su equipo de programación sea atacado y asesinado por lobos en incidentes no relacionados en la misma noche.

Resumen :

La comparación byte por byte es buena para las comparaciones locales. sha1sum es bueno para la comparación remota, y no presenta una posibilidad significativa de falsos positivos.

Aquí hay otra forma de pensarlo.

Si no existe la posibilidad de que dos archivos diferentes tengan el mismo CRC, entonces, por extensión, significa que cada archivo puede estar representado por un CRC único. Si el CRC fuera más pequeño que el archivo original, representaría una forma de compresión sin pérdidas. De lo contrario, haría lo mismo si comparara los archivos originales, ya que estaría comparando la misma cantidad de bytes.

En teoría, podría usar la compresión sin pérdida de ambos lados de la comparación para reducir la cantidad de bytes necesarios en la comparación, pero es un error tonto porque desperdiciaría más ciclos y tendría que leer cada byte de ambos archivos para hacer la compresión. . Es decir, para codificar cada byte (y su orden) en un esquema de compresión sin pérdidas, primero tendría que leerlo y conectarlo al algoritmo, ¿verdad? Juego terminado.

Aquí hay una analogía:
si desea una forma de determinar rápidamente si dos documentos impresos son idénticos sin comparar letra por letra, puede comparar el recuento de letras en cada línea de los documentos. Si todos los recuentos coinciden, las probabilidades mejoran sustancialmente de que los documentos sean idénticos, sin embargo, nadie argumentaría que podría estar seguro de que cada letra era la misma utilizando este enfoque.

La única forma perfecta de verificar archivos idénticos es byte para comparar byte. Otra forma de ser una aproximación justa es calcular un hash como MD5 para los archivos y compararlos. Es posible que haya una colisión de hash, pero no es muy probable.

Me imagino que la comparación byte por byte sería más rápida que calcular el hash en ambos archivos en el momento en que realiza la comparación. Sin embargo, si su aplicación calcula previamente el hash y almacena metadatos sobre sus archivos, la comparación de los hash será significativamente más rápida.

CRC probablemente no sea el camino a seguir, ya que es solo un mecanismo de detección de errores, no un hash. (o un hash pobre con muchas posibles colisiones)

Para estar 100% seguro de que dos archivos son idénticos, realmente necesita verificar los bytes.

¿Por qué? Colisiones de hash, ¡por eso! Dependiendo del algoritmo utilizado para el hash, la colisión puede ser más o menos probable, pero no obstante es posible. Siguiendo estos pasos:

1. Verificar tamaños de archivo
2. Comprobar tipos de mimo
3. Comprobar hash
4. Verifique algunas compensaciones aleatorias y compare bits

Le dará una garantía muy alta de certeza de que los dos archivos son iguales, sin embargo, existe una posibilidad muy (extremadamente) pequeña de que tenga una colisión en sus manos. La elección determinará qué tan lejos quiere llegar con sus comparaciones.

Como otros han dicho, es más rápido hacer una comparación byte por byte si los dos archivos están en el mismo sistema. Si está tratando de comparar un montón de archivos, llegará al punto en que el hash es la mejor respuesta si los archivos están en almacenamiento giratorio.

El hash realmente brilla cuando no tienes todos los datos disponibles. Por ejemplo, los archivos están en diferentes máquinas. También le permite guardar los resultados de los cálculos y consultarlos más adelante. (¿Es este informe el mismo que el anterior? Cuando realiza el informe, guarde un hash del mismo. Cuando realiza el siguiente, simplemente puede comparar los hash. No solo no necesita leer el antiguo en usted no ' ni siquiera necesita tener una copia disponible).

Creo que debe usar la utilidad de comparación de archivos suministrada con su sistema operativo o usar una herramienta de comparación de archivos (consulte: herramientas de comparación de archivos wiki ) para comparar contenidos DESPUÉS de haber verificado las propiedades del archivo descritas por @Glenn Nelson.

No creo que CRC sea 100% preciso y creo que su precisión disminuye con la longitud del archivo. Además, no le sugiero que lo escriba desde cero, ya que puede requerir muchas pruebas.

¿Es necesario leer cada byte para verificar si un archivo copiado es idéntico al original? SÍ para estar 100% seguro

¿Es necesario leer cada byte para verificar si un archivo copiado NO es idéntico al original? NO

Por lo tanto, para determinar rápidamente la no-identidad, primero verifique los metadatos como el tamaño del archivo y cualquier tipo de suma de comprobación / CRC o MIME que el sistema operativo / sistema de archivos / tienda ya podría estar manteniendo . Dado que están precalculados por ese sistema, no paga este costo al momento de la comparación.

Si esa prueba pasa, aún necesita comparar cada byte individualmente si necesita estar 100% seguro, PERO TENGA EN CUENTA que en las CPU modernas canalizadas, y usando múltiples hilos y posiblemente múltiples procesadores / CPU, hacer comparaciones de bloques de archivos grandes es REALMENTE rápido y eficiente porque el proceso es altamente paralelo. Mucho más rápido que CUALQUIER tipo de cálculo matemático que involucre cada byte (aunque algunos algoritmos posiblemente también sean paralelizables, pero tal vez no tan fácil o tan bien). Esto se debe a que las CPU que están canalizadas pueden realizar operaciones de comparación de bloques de memoria en microcódigo o incluso hardware (realmente rápido) y los subsistemas de disco a memoria están altamente optimizados para llevar enormes bloques de archivos a / desde la memoria, todo en paralelo y con hardware. Si su aplicación hace este tipo de cosas regularmente, y es un cuello de botella de rendimiento conocido, sería prudente implementar esto en un código multiproceso bien escrito que aproveche las funciones de paralelización de su sistema operativo y hardware (tal vez use un lenguaje diseñado para esta).

Solo si desea procesar cada archivo una vez y hacer comparaciones múltiples más tarde (donde recuerde ["caché"] el resultado del análisis resumido o "comprimido" [como dice JohnFX]), habrá un beneficio significativo al hacerlo, e incluso entonces, solo para probar la diferencia (probable); Para demostrar la identidad, aún necesitaría hacer la comparación byte por byte.