☰

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 에뮬레이터자바스크립트의 경우). 그리고 단순 바이트 합계는 2바이트 적습니다.

$ 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 2Unix V5와 Unix V5는 대부분의 텍스트 파일에서 일관성이 있지만 sum에뮬레이터(예: 폴더 내)에서 대부분의 바이너리 파일에 대해 서로 다른 출력을 생성합니다./bin

이것이 실제 동작입니까, 아니면 에뮬레이터의 버그입니까? 사실이라면 알고리즘은 무엇입니까?

추신 : 이것은소스 코드, 누구든지 1974년 어셈블리 코드를 읽을 수 있다면 말이죠.

답변1

처음에는 2^16 모듈로 바이트의 단순한 합이라고 생각했습니다.

합계 모드는 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 v5의 sum부호 확장 문자와 바이너리 파일에만 0x80보다 큰 바이트가 포함되어 있기 때문입니다. 그렇지 않은 경우 알고리즘은 유사해야 하며 매우 큰 파일에서만 다릅니다(문자 합계가 32비트 부호 없는 정수를 오버플로함).

관련 정보