Apakah perlu membaca setiap byte tunggal untuk memeriksa apakah file yang disalin identik dengan aslinya?

Baru-baru ini saya mengetahui sebuah program bernama Total Commander. Ini adalah pengganti Windows Explorer dan memiliki barang sendiri untuk menyalin file. Untuk memeriksa apakah file-file itu identik, alih-alih menghitung CRC, ia benar-benar memeriksa setiap byte tunggal, satu per satu, baik pada dokumen asli maupun salinannya.

Pertanyaan saya adalah: Apakah ini perlu? Apakah CRC atau teknik lain apa pun bisa salah? Haruskah Anda, sebagai seorang programmer, mencoba dan menerapkan sistem yang sempurna namun lambat ini, atau terlalu ekstrem?

Menghitung CRC (atau, lebih baik, sha1sums) pada kedua file membutuhkan membaca setiap byte. Jika Anda melakukan perbandingan byte-by-byte, Anda dapat berhenti segera setelah Anda melihat ketidakcocokan - dan Anda tidak perlu khawatir tentang dua file berbeda yang kebetulan memiliki checksum yang sama (meskipun itu tidak mungkin untuk sha1sum) . Jadi jika Anda melakukan perbandingan secara lokal, perbandingan byte-by-byte setidaknya akan secepat perbandingan checksum (kecuali jika Anda sudah menghitung checksumnya).

Di sisi lain, perbandingan checksum berguna ketika Anda membandingkan file yang tidak berada di mesin yang sama; checksum dapat dihitung secara lokal, dan Anda tidak perlu mentransfer seluruh konten melalui jaringan.

Pendekatan hybrid juga dimungkinkan. Misalnya, Anda dapat menghitung dan membandingkan checksum untuk dua file sekaligus, yang dapat menghindari membaca seluruh file ( jika berbeda) sementara juga menghindari mentransmisikan seluruh file di seluruh jaringan. The protokol rsync melakukan sesuatu seperti ini.

Perhatikan bahwa menggunakan CRC sederhana memberi Anda peluang tabrakan, seperti yang disebutkan Dave Rager dalam jawabannya. Gunakan setidaknya sha1sum, atau bahkan sesuatu yang lebih baru. (Jangan mencoba untuk membuat algoritma hashing Anda sendiri; orang-orang yang mengembangkan sha1sum tahu lebih banyak tentang hal ini daripada kita berdua.)

Adapun kemungkinan tabrakan, jika Anda menggunakan hash yang layak seperti sha1sum Anda cukup banyak tidak perlu khawatir tentang hal itu, kecuali seseorang secara sengaja dan mahal membangun file yang sha1sums bertabrakan (menghasilkan tabrakan tersebut tidak layak ketika saya pertama kali menulis ini , tetapi kemajuan sedang dibuat ). Mengutip "Pro Git" Scott Chacon , bagian 6.1 :

Berikut ini contoh untuk memberi Anda gambaran tentang apa yang diperlukan untuk mendapatkan tabrakan SHA-1. Jika semua 6,5 ​​miliar manusia di Bumi memprogram, dan setiap detik, masing-masing menghasilkan kode yang setara dengan seluruh sejarah kernel Linux (1 juta objek Git) dan mendorongnya ke dalam satu repositori Git yang sangat besar, akan membutuhkan waktu 5 tahun hingga repositori itu mengandung cukup banyak objek untuk memiliki probabilitas 50% dari satu tabrakan objek SHA-1. Ada kemungkinan yang lebih tinggi bahwa setiap anggota tim pemrograman Anda akan diserang dan dibunuh oleh serigala dalam insiden yang tidak berhubungan pada malam yang sama.

Ringkasan:

Perbandingan byte-by-byte baik untuk perbandingan lokal. sha1sum baik untuk perbandingan jarak jauh, dan tidak memberikan peluang positif palsu yang signifikan.

Berikut cara lain untuk memikirkannya.

Jika tidak ada kemungkinan bahwa dua file berbeda memiliki CRC yang sama, maka dengan ekstensi itu berarti bahwa setiap file dapat diwakili oleh CRC unik. Jika CRC lebih kecil dari file asli maka itu akan mewakili bentuk kompresi lossless. Jika tidak, Anda sebaiknya membandingkan file asli karena Anda akan membandingkan jumlah byte yang sama.

Secara teori Anda bisa menggunakan kompresi lossless dari kedua sisi perbandingan untuk mengurangi jumlah byte yang diperlukan dalam perbandingan, tetapi itu adalah tugas bodoh karena Anda akan membuang lebih banyak siklus dan harus membaca setiap byte dari kedua file untuk melakukan kompresi . Yaitu, untuk menyandikan setiap byte (dan urutannya) dalam skema kompresi lossless Anda harus terlebih dahulu membacanya dan memasukkannya ke dalam algoritma, bukan? Permainan telah berakhir.

Berikut ini analogi:
Jika Anda ingin cara untuk dengan cepat menentukan apakah dua dokumen yang dicetak identik tanpa membandingkan huruf per huruf, Anda dapat membandingkan jumlah huruf pada setiap baris dokumen. Jika jumlah semua cocok, kemungkinan meningkatkan secara substansial bahwa dokumen itu identik, namun tidak ada yang akan berpendapat bahwa Anda dapat memastikan bahwa setiap huruf sama dengan menggunakan pendekatan ini.

Satu-satunya cara sempurna untuk memeriksa file yang identik adalah byte untuk perbandingan byte. Cara lain untuk menjadi perkiraan yang adil adalah dengan menghitung hash seperti MD5 untuk file dan membandingkannya. Mungkin saja ada tabrakan hash tetapi tidak terlalu mungkin.

Saya akan membayangkan perbandingan byte untuk byte akan lebih cepat daripada menghitung hash pada kedua file pada saat Anda melakukan perbandingan. Namun, jika aplikasi Anda pra-menghitung hash dan menyimpan meta-data tentang file Anda, membandingkan hash akan jauh lebih cepat.

CRC mungkin bukan cara yang tepat karena hanya mekanisme pendeteksian kesalahan, bukan hash. (atau hash yang buruk dengan banyak kemungkinan tabrakan)

Agar 100% dua file tertentu identik, Anda benar-benar perlu memeriksa byte.

Mengapa? Tabrakan hash, itu sebabnya! Bergantung pada algoritma yang digunakan untuk hashing, tabrakan mungkin lebih atau kurang mungkin, tetapi mungkin tidak ada yang kurang. Ikuti langkah-langkah ini:

1. Periksa ukuran file
2. Periksa jenis pantomim
3. Periksa hash
4. Periksa beberapa offset acak dan bandingkan bitnya

Akan memberi Anda jaminan kepastian yang sangat tinggi bahwa kedua file itu sama, namun ada kemungkinan sangat kecil bahwa Anda memiliki tabrakan di tangan Anda. Pilihan seberapa jauh Anda ingin melakukan perbandingan akan ditentukan oleh situasi.

Seperti yang orang lain katakan, lebih cepat melakukan perbandingan byte-by-byte jika kedua file tersebut berada pada sistem yang sama. Jika Anda mencoba membandingkan banyak file, Anda akan mencapai titik di mana hashing adalah jawaban yang lebih baik jika file-file itu berada di penyimpanan pemintalan.

Hashing benar-benar bersinar ketika Anda tidak memiliki semua data yang tersedia. Sebagai contoh, file-file tersebut berada pada mesin yang berbeda. Ini juga memungkinkan Anda menyimpan hasil perhitungan dan merujuknya nanti. (Apakah laporan ini sama dengan yang lama? Ketika Anda membuat laporan, simpan satu hash. Ketika Anda membuat yang berikutnya Anda dapat dengan mudah membandingkan hash. Bukan saja Anda tidak perlu membaca yang lama di dalam diri Anda, bukan ' bahkan tidak perlu memiliki salinannya.)

Saya pikir Anda harus menggunakan utilitas perbandingan file yang disediakan dengan sistem operasi Anda atau menggunakan alat perbandingan file (lihat: alat perbandingan file wiki ) untuk membandingkan konten SETELAH Anda telah memeriksa properti file yang digariskan oleh @Glenn Nelson.

Saya tidak berpikir bahwa CRC adalah 100% akurat dan saya pikir akurasinya menurun dengan panjang file. Juga, saya tidak menyarankan Anda menulisnya dari awal karena mungkin memerlukan banyak pengujian.

Apakah perlu membaca setiap byte tunggal untuk memeriksa apakah file yang disalin identik dengan aslinya? YA menjadi 100% yakin

Apakah perlu membaca setiap byte tunggal untuk memeriksa apakah file yang disalin TIDAK identik dengan aslinya? TIDAK

Jadi, untuk menentukan non-identik dengan cepat, periksa dulu metadata seperti ukuran file dan segala jenis checksum / CRC atau MIME yang mungkin sudah dipelihara oleh OS / file-system / system / store . Karena mereka sudah dihitung sebelumnya oleh sistem itu, Anda tidak membayar biaya ini pada saat perbandingan.

Jika tes itu lolos, Anda masih perlu membandingkan setiap byte secara individual jika Anda harus 100% yakin, TETAPI CATATAN bahwa dalam CPU pipelined modern, dan menggunakan beberapa utas dan mungkin beberapa prosesor / CPU, melakukan perbandingan blok file besar BENAR-BENAR cepat dan efisien karena prosesnya sangat paralel. Jauh lebih cepat daripada APAPUN jenis perhitungan matematika yang melibatkan setiap byte (meskipun beberapa algoritma mungkin juga diparalelkan, tetapi mungkin tidak begitu mudah atau sangat baik). Itu karena CPU yang di pipelined dapat melakukan operasi perbandingan blok memori dalam mikrokode atau bahkan perangkat keras (sangat cepat) dan subsistem disk-ke-memori sangat dioptimalkan untuk membawa blok besar file ke / dari memori, semua dilakukan secara paralel dan dengan perangkat keras. Jika aplikasi Anda melakukan hal semacam ini secara teratur, dan ini merupakan hambatan kinerja yang diketahui, Anda sebaiknya menerapkannya dalam kode multithreaded yang ditulis dengan baik yang memanfaatkan fasilitas paralelisasi OS dan perangkat keras Anda (mungkin menggunakan bahasa yang dirancang untuk ini).

Hanya jika Anda ingin memproses setiap file sekali dan melakukan beberapa perbandingan nanti (di mana Anda ingat ["cache"] hasil analisis yang diringkas, atau "dikompresi" [seperti yang dikatakan oleh JohnFX]), akan ada manfaat yang signifikan untuk melakukannya, dan bahkan kemudian, hanya untuk membuktikan perbedaan (kemungkinan); untuk membuktikan identitas, Anda masih perlu melakukan perbandingan byte-by-byte.