Is it necessary to read every single byte to check if a copied file is identical to the original?

Question

I recently learned of a program called Total Commander. It's a Windows Explorer replacement and has its own stuff to copy files. To check whether the files are identical, instead of calculation a CRC, it literally checks every single byte, one at a time, on both the original and the copy.

My question is: Is this necessary? Can CRC or any other such technique go wrong? Should you, as a programmer, try and implement this perfect but slow system, or is it too extreme?

Answer 1

Calculating CRCs (or, better, sha1sums) on both files requires reading every byte anyway. If you do a byte-by-byte comparison, you can quit as soon as you see a mismatch -- and you don't have to worry about two different files that happen to have the same checksum (though that's vanishingly unlikely for sha1sum). So if you're doing the comparison locally, a byte-by-byte comparison will be at least as fast as a checksum comparison (unless you've already computed the checksums anyway).

On the other hand, checksum comparisons are useful when you're comparing files that aren't on the same machine; the checksums can be computed locally, and you don't have to transfer the entire content over the network.

Note that using a simple CRC gives you a fair chance of a collision, as Dave Rager mentioned in his answer. Use at least sha1sum, or even something more recent. (Don't try to invent your own hashing algorithm; the folks who developed sha1sum know far more about this stuff than either of us.)

As for the likelihood of collision, if you use a decent hash like sha1sum you pretty much don't have to worry about it, unless someone is deliberately and expensively constructing files whose sha1sums collide (generating such collisions is not currently feasible, though it may become so in the foreseeable future). Quoting Scott Chacon's "Pro Git", section 6.1:

Here’s an example to give you an idea of what it would take to get a SHA-1 collision. If all 6.5 billion humans on Earth were programming, and every second, each one was producing code that was the equivalent of the entire Linux kernel history (1 million Git objects) and pushing it into one enormous Git repository, it would take 5 years until that repository contained enough objects to have a 50% probability of a single SHA-1 object collision. A higher probability exists that every member of your programming team will be attacked and killed by wolves in unrelated incidents on the same night.

Summary :

Byte-by-byte comparison is good for local comparisons. sha1sum is good for remote comparison, and presents no significant chance of false positives.

Answer 2

Here's another way to think about it.

If there is no possibility that two different files have the same CRC, then by extension it means that every file can be represented by a unique CRC.If the CRC was smaller than the original file then it would represent a form of lossless compression. If not, you would do just as well to compare the original files since you'd be comparing the same number of bytes.

In theory you could use lossless compression of both sides of the comparison to reduce the number of bytes necessary in the comparison, but it is a fools errand because you'd waste more cycles and have to read every byte of both files to do the compression. That is, to encode every byte (and it's order) in a lossless compression scheme you'd have to first read it in and plug it into the algorithm, right? Game over.

Here's an analogy:
If you wanted a way to quickly determine whether two printed documents were identical without comparing letter by letter, you could compare the count of letters on each line of the documents. If the counts all matched, the odds improve substantially that the documents are identical, however no one would argue that you could be certain that every letter was the same using this approach.

Answer 3

The only perfect way to check for identical files is byte for byte comparison. Another way to be a fair approximation is to calculate a hash such as MD5 for the files and compare those. It's possible there could be a hash collision but not very likely.

I would imagine the byte for byte comparison would be faster than computing the hash on both files at the time you are doing the comparison. However, if your application pre-calculates the hash and stores meta-data about your files, comparing hashes will be significantly faster.

CRC is probably not the way to go as it is just an error detection mechanism, not a hash. (or a poor hash with lots of possible collisions)

Answer 4

To be 100% certain two files are identical, you really do need to check the bytes.

Why? Hash collisions, thats why! Depending on the algorithm used for hashing, collision might be more or less probable, but it is possible none the less. Following these steps:

1. Check file sizes
2. Check mime types
3. Check hash
4. Check a few random offsets and compare bits

Will give you a very high guarantee of certainty that the two files are the same, however there is a very (extremely) small chance that you have a collision on your hands. The choice of how far you want to go with your comparisons will be dictated by the situation.

Answer 5

As others have said it's faster to do a byte-by-byte comparison if the two files are on the same system. If you're trying to compare a bunch of files you'll reach the point where hashing is the better answer if the files are on spinning storage.

Hashing really shines when do you don't have all the data readily available. For example, the files are on different machines. It also lets you save the results of calculations and refer to them later. (Is this report the same as the old one? When you make the report save a hash of it. When you make the next one you can simply compare the hashes. Not only do you not need to read the old one in you don't even need to have a copy of it available.)

Answer 6

I think that you should use the supplied file compare utility with your operating system or use a file compare tool (see: wiki-file compare tools ) to compare contents AFTER you have checked the file properties outlined by @Glenn Nelson.

I don't think that CRC is 100% accurate and I think that its accuracy decreases with file length. Also, I don't suggest you write it from scratch since it may require lots of testing.