19

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?

8
  • 3
    Have a look at how "rsync" handles this.
    – user1249
    Dec 3, 2011 at 22:30
  • 24
    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). 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. Dec 3, 2011 at 23:07
  • 3
    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. I don't have a source for this, but I've heard (in the context of git) that the probability of two different files having the same sha1sum is about the same as the probability of every member of your development team being eaten by wolves. On the same day. In completely unrelated incidents. Dec 3, 2011 at 23:10
  • 5
    @KeithThompson: I think your first comment should be an answer :-) Dec 3, 2011 at 23:26
  • 6
    Short answer - No, it's best just to have your computer do it for you.
    – psr
    Jan 19, 2012 at 23:30

7 Answers 7

44

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 in the absence of deliberate collisions, which became feasible after I originally wrote this answer). 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.

Hybrid approaches are also possible. For example, you might compute and compare checksums for the two files a chunk at a time, which can avoid reading the whole files (if they differ) while also avoiding transmitting the whole file across the network. The rsync protocol does something like this.

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 was not feasible when I first wrote this, but progress is being made). 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 accidental false positives.

And there are newer checksum checksum algorithms that are (so far) less vulnerable to deliberate collisions than SHA1 is. I won't be too specific to avoid having this answer become obsolete yet again in a few years.

6
  • It should be noted that the common definition of a "good" hash function includes the property that it is very hard to create different inputs with the same hash ("collision-resistance"). SHA-1 has some (so far theoretical) weaknesses in this respect, but you cannot just "construct two files which collide", even if you try fairly hard.
    – sleske
    Jan 20, 2012 at 8:40
  • @sleske: Updated Jan 20, 2012 at 20:17
  • 1
    @KeithThompson I'm upvoting the answer, but I think it's about time for an update on SHA1 - The SHAppening
    – K.Steff
    Oct 16, 2016 at 19:07
  • I suspect they would get cranky if you tried to host this theoretical repo on GitHub.
    – hBy2Py
    Oct 18, 2016 at 17:28
  • 2
    I more meant that they would be unhappy at having however many exabytes per second of data thrust at them. :-)
    – hBy2Py
    Oct 18, 2016 at 18:21
11

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.

4

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)

1
  • +1 Agree. It soooo much more likely that your hard drive gets broken compared to incidental collision of good hashing function (CRC32 is weak - also agree). Jan 19, 2012 at 23:15
2

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.

4
  • I think if you pick a good hashing algorithm, the 2. and 4. will not give you any real increase "equal" quality. Probably 1. is needed only for weak hash as well. Jan 19, 2012 at 23:13
  • 1
    -1 This does not make sense. If you pick a good hashing algorithm, all other steps are superfluous. 1. and 4. are actually already covered by what a hash does, and 2. is nonsense (Most file systems do not even have a notion of "MIME type", and even if they had, it adds very little information).
    – sleske
    Jan 20, 2012 at 8:43
  • @sleske I'm saying instead of flat out hashing the file, which is an intensive operations, you can perform some preliminary operations that are not so heavy.
    – user7007
    Jan 20, 2012 at 19:43
  • I recon just 1 and 3 make a lot of sense. (1) will flag up most cases of different files saving the need to calculate the hash. Hash clash on the same length file is so unlikely it's not worth worrying about. Oct 18, 2016 at 19:59
1

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.)

0

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.

0

Is it necessary to read every single byte to check if a copied file is identical to the original? YES to be 100% sure

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

Thus, to determine non-identicality quickly, first check metadata like file size and any checksum/CRC or MIME type that the OS/file-system/store might already be maintaining. Since they are pre-calculated by that system, you don't pay this cost at the time of the comparison.

If that test passes, you still need to compare every byte individually if you need to be 100% certain, BUT NOTE that in modern pipelined CPUs, and using multiple threads and possibly multiple processors/CPUs, doing block comparisons of large files is REALLY fast and efficient because the process is highly parallelizable. Way faster than ANY kind of mathematical computation involving each byte (though some algorithms are possibly also parallelizable, but perhaps not so easily or so well). That's because CPUs that are pipelined can do block-comparison operations of memory in microcode or even hardware (really fast) and disk-to-memory subsystems are highly optimized to bringing huge blocks of files to/from memory, all done in parallel and with hardware. If your application does this sort of thing regularly, and it's a known performance bottleneck, you'd be wise to implement this in well-written multithreaded code that takes advantage of your OS's and hardware's parallelization facilities (perhaps use a language that is designed for this).

Only if you want to process each file once and do multiple comparisons later (where you remember ["cache"] the summarized, or "compressed" [as JohnFX puts it] analysis result), will there be a significant benefit to doing so, and even then, only to prove difference (likely); to prove identicality, you'd still need to do the byte-by-byte comparison.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.