☰

Unix 版本 5 使用什么校验和算法？

tag-icon • tag-icon checksum historical-unix
Unix 版本 5 使用什么校验和算法？

我不知道 Unix V5 和 V6 中的sum命令使用了什么算法。

一开始我以为就是简单的字节模2^16之和。然而，对于重复 320 次的字符串“1111111111\n”，它计算的校验和为28930（使用Julius Schmidt 的 PDP-11 模拟器对于 JavaScript）。而它的简单字节总和要小两个字节：

$ python -c 'print(sum(bytearray(b"1111111111\n"*320)) & 0xFFFF)'
28928

后来，从MacOS 手册页，我发现sum和cksum命令长期以来一直存在不一致的情况。然而，即使是 MacOS 上提供的“历史”算法版本也与 Unix V5 的校验和不一致。最接近的匹配是sumUNIX System V 的默认命令（在 Mac 上调用，如cksum -o 2），它为此字符串返回相同的校验和，但不同意其他命令：

$ python -c 'print("1111111111\n"*320, end="")' | cksum -o 2
28930 7

更具体地说，cksum -o 2和 Unix V5sum为模拟器中的大多数二进制文件（例如，在文件夹中/bin）生成不同的输出，尽管它们在大多数文本文件上是一致的。

这是真实的行为还是模拟器中的错误？如果是真的，是什么算法？

PS 这是源代码，如果有人能读懂 1974 年的汇编代码的话。

答案1

一开始我以为是简单的字节模2^16之和

它是一个sum mod 2^16，只是每次溢出时都会加1。此外，在添加到总和之前，字节将被符号扩展。这是程序集中的“注释”片段：

# r2 is the pointer into the data
# r0 is the length of the data
# r5 is the sum
2:
        movb    (r2)+,r4    # r4 = sign_extend(*r2++)
        add     r4,r5       # r5 += r4
        adc     r5          # if(r5 overflowed) r5++
        sob     r0,2b       # if(--r0) goto 2 above

将同样的内容放入一个小型 C 程序中（使用 as ./v5sum < file）：

#include <stdio.h>
int main(void){
        int c, s = 0;
        while((c = getchar()) != EOF){
                s += c & 0x80 ? c | 0xff00 : c; // alternative: s += (unsigned short)(signed char)c
                if(s & 0x10000){ s++; s &= 0xffff; };
        }
        printf("%d\n", s);
        return 0;
}

更具体地说， cksum -o 2 和 Unix V5 的 sum 为模拟器中的大多数二进制文件（例如，在文件夹 /bin 中）产生不同的输出，尽管它们在大多数文本文件上是一致的。

这是因为原始的 unix v5sum会对字符进行符号扩展，并且只有二进制文件包含 >= 0x80 的字节。否则，算法应该是相似的，仅在非常大的文件上有所不同（其中字符的总和将溢出 32 位无符号整数）。

相关内容