你能 SHA1 将文件哈希到一定长度吗?

Question

我需要比较两个文件。一个文件可能比另一个文件长，我需要检查较长的文件是否包含较短文件的所有数据。 我可以对两者进行二进制比较，如下所示：

function compareFiles($file_a, $file_b){
if (filesize($file_a) > filesize($file_b)){
$fp_a = fopen($file_b, 'rb');
$fp_b = fopen($file_a, 'rb');
} else { // filesize($file_b) > filesize($file_a)
$fp_a = fopen($file_a, 'rb');
$fp_b = fopen($file_b, 'rb');
}
while (($b = fread($fp_a, 4096)) !== false){
$b_b = fread($fp_b, 4096);
if ($b !== $b_b){
fclose($fp_a);
fclose($fp_b);
return false;
}
}
fclose($fp_a);
fclose($fp_b);
return true;
}

但这会很慢。作为替代方案，我可以将较小文件的 SHA1 哈希与较大文件的 SHA1 哈希进行比较，直到较小文件的大小，如下所示：

function compareFiles($file_a, $file_b){
$tmpfile = '/dev/shm/tmp_file_copy.bin';
if (filesize($file_a) > filesize($file_b)){
$readfromfile = $file_b;
$bytes_to_copy = filesize($file_b);
} else {
$readfromfile = $file_a
$bytes_to_copy = filesize($file_a);
}
$readfile = fopen($readfromfile, 'rb');
$writefile = fopen($tmpfile, 'wb');
while (!feof($readfile) && $bytes_to_copy> 0) {
if ($bytes_to_copy <= 8192) {
$contents = fread($readfile, $bytes_to_copy);
$bytes_to_copy = 0;
} else {
$contents = fread($readfile, 8192);
$bytes_to_copy =- 8192;
}
fwrite($writefile, $contents);
}
fclose($writefile);
fclose($readfile);
$result = sha1_file($readfromfile = $file_a ? $file_b : $file_a) === sha1_file($tmpfile);
unlink($tmpfile);
return $result;
}

但我担心这也会很慢，因为它涉及大量的 I/O(到/dev/shm)。

简而言之，我正在寻找更好的方法...

Answer 1

在这种情况下，散列文件只会更慢。请考虑以下情况。

文件A.txt内容：

AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

文件B.txt内容：

AAAAAAAAAAAAAAAAAAAAABBBBBBBBBB

_{请注意，A.txt总共 40 个字符，比B.txt30 个字符长 10 个字符}

我们必须对每个文件执行多少 I/O 才能确定A.txt是否包含所有B.txt？40 字节？30 字节？不，答案只有 20 个字节，因为这是两个文件共享的共同点。您可以一次流式传输每个文件一个字节(或字节块)，并随时比较它们。这种比较的结果如下所示：

A.txt: AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
B.txt: AAAAAAAAAAAAAAAAAAAAABBBBBBBBBB
Stream ---------------------^
Result ✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓✓X

然后你停下来。为什么要比较其余的？

如果对这两个文件进行哈希处理，则必须将全部内容放在内存中才能计算哈希。即使您在将它们流式传输到内存时将它们分成块进行哈希处理，您认为哪个更快：比较每个文件中的每个字节或对块进行哈希处理？比较的复杂性是O(number of bytes)，而 SHA-1 哈希算法的复杂性由 RFC 3174 指定。

Answer 2

逐字节是最好的方法。它仅比较两个文件的前x个字节，如果它们不同，则停止。哈希函数必须处理文件中的所有字节。不是更慢吗？