Início / unix / Perguntas / 526611
Accepted
Andriy Makukha
Asked: 2019-06-25 05:05:46 +0800 CST

Qual algoritmo de soma de verificação é usado pela versão 5 do Unix?

  • 772

Não consigo descobrir qual algoritmo foi usado no Unix V5 e V6 para o sumcomando.

A princípio, pensei que fosse uma simples soma de bytes módulo 2^16. No entanto, para uma string "1111111111\n" repetida 320 vezes, ela calcula uma soma de verificação de 28930 (usando o emulador PDP-11 de Julius Schmidt para JavaScript). Considerando que uma simples soma de bytes para ele é dois bytes menor:

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

Mais tarde, nas páginas man do MacOS , descobri que os comandos sume cksumtinham um longo histórico de inconsistências. No entanto, mesmo as versões "históricas" do algoritmo fornecidas no MacOS não concordam com a soma de verificação do Unix V5. A correspondência mais próxima é o comando padrão sumdo UNIX System V (invocado no Mac como cksum -o 2), que retorna a mesma soma de verificação para esta string, mas discorda para outras:

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

Para ser mais específico, o cksum -o 2e o Unix V5 sumproduzem saídas diferentes para a maioria dos arquivos binários no emulador (por exemplo, na pasta /bin), embora concordem na maioria dos arquivos de texto.

Este é um comportamento genuíno ou um bug no emulador? Se for genuíno, qual é o algoritmo?

PS Aqui está o código fonte , se alguém puder ler o código assembly de 1974.

historical-unix checksum

1 respostas

  1. Best Answer

    A princípio, pensei que fosse uma simples soma de bytes módulo 2^16

    É uma soma mod 2^16, só que cada vez que estourar, um 1 será adicionado a ela. Além disso, os bytes serão estendidos antes de serem adicionados à soma. Aqui está um trecho "comentado" da montagem:

    # 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

    o mesmo colocado em um pequeno programa C (use como ./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;
}

    Para ser mais específico, o cksum -o 2 e a soma do Unix V5 produzem saídas diferentes para a maioria dos arquivos binários no emulador (por exemplo, na pasta /bin), embora eles concordem na maioria dos arquivos de texto.

    Isso porque o unix original v5sum assinará estender os caracteres e apenas os binários contêm bytes >= 0x80. Caso contrário, os algoritmos devem ser semelhantes e diferir apenas com arquivos muito grandes (onde a soma dos caracteres transbordará um int não assinado de 32 bits).

    • 4

relate perguntas