主页 / unix / 问题 / 526611
Accepted
Andriy Makukha
Asked: 2019-06-25 05:05:46 +0800 CST

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

  • 772

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

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

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

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

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

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

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

PS这是源代码，如果有人可以阅读1974年的汇编代码。

historical-unix checksum

1 个回答

  1. Best Answer

    起初，我以为它是字节模数 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 程序（用作./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 位无符号整数）。

    • 4

相关问题