Calcular a soma de verificação Adler-32

32

fundo

O Adler-32 é uma soma de verificação de 32 bits inventada por Mark Adler em 1995, que faz parte da biblioteca zlib amplamente usada (também desenvolvida pela Adler). O Adler-32 não é tão confiável quanto uma verificação de redundância cíclica de 32 bits , mas - pelo menos em software - é muito mais rápido e fácil de implementar.

Definição

Seja B = [b 1 , ⋯, b n ] uma matriz de bytes.

A soma de verificação Adler-32 de B é definida como o resultado de baixo + 65536 × alto , onde:

  • baixo: = ((1 + b 1 + ⋯ + b n ) mod 65521)

  • high: = (((1 + b 1 ) + (1 + b 1 + b 2 ) + ⋯ (1 + b 1 + ⋯ + b n )) mod 65521)

Tarefa

Dada uma matriz de bytes como entrada, calcule e retorne sua soma de verificação Adler-32, respeitando o seguinte.

  • Você pode receber a entrada como uma matriz de bytes ou números inteiros ou como uma sequência.

    Nos dois casos, apenas bytes correspondentes a caracteres ASCII imprimíveis ocorrerão na entrada.

    Você pode assumir que o comprimento da entrada satisfará 0 <comprimento ≤ 4096 .

  • Se você optar por imprimir a saída, poderá usar qualquer base positiva até 256 inclusive.

    Se você escolher unário, verifique se o intérprete pode lidar com até 2 32 - 983056 bytes de saída em uma máquina com 16 GiB de RAM.

  • Os internos que calculam a soma de verificação Adler-32 são proibidos.

  • Aplicam-se as regras padrão de .

Casos de teste

String:     "Eagles are great!"
Byte array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254

String:     "Programming Puzzles & Code Golf"
Byte array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937

String:     <1040 question marks>
Byte array: <1040 copies of 63>
Checksum:   2181038080
Dennis
fonte
7
Observarei que muitas das respostas aqui falharão com seqüências de entrada grandes ou muito grandes quando elas excederem as somas inteiras de 32 ou 64 bits, devido ao adiamento da operação do módulo até depois que as somas forem calculadas. Uma implementação verdadeiramente compatível precisaria executar a operação do módulo pelo menos periodicamente para impedir que as somas transbordassem. Um número inteiro assinado de 32 bits seria excedido após apenas 4096 0xff's. Um número inteiro assinado de 64 bits seria excedido após 256 MiB de 0xff.
Mark Adler
@MarkAdler Hm, ponto justo. Como não especifiquei que as soluções teriam que funcionar para seqüências arbitrariamente longas e não desejo invalidar as respostas existentes, definirei um limite para o comprimento da entrada.
Dennis
@ MarkAdler Eu não acho que isso importe. Estou bastante certo de que o estouro (números inteiros de 32 bits) pode ocorrer apenas com 4104 ou mais bytes de entrada, pois o valor máximo de high antes do módulo é n * (n + 1) / 2 * 255 + n . Além disso, o desafio restringe a entrada a bytes correspondentes a caracteres ASCII imprimíveis.
Dennis
Também podemos permitir que os idiomas excedam seus tipos numéricos e exigimos apenas que o resultado retornado seja equivalente, contabilizando o excedente, ao resultado correto.
miles
1
@PeterCordes Sim, matrizes de 32 bits são perfeitamente perfeitas. Pelo menos na minha opinião, as submissões devem se concentrar no golfe do algoritmo e prestar o mínimo de atenção possível à E / S.
Dennis

Respostas:

3

Geléia, 19 17 bytes

+\,S‘S€%65521ḅ⁹²¤

Experimente online!

+\,S‘S€%65521ḅ⁹²¤    Main monadic chain. Takes array as only argument.

                     The array is shown here as [b1 b2 ... bn].
+\                   Reduce by addition (+) while returning immediate results.
                         yields [b1 b1+b2 ... b1+b2+...+bn].

  ,                  Concatenate with...
   S                 the sum of the argument.
                         yields [[b1 b1+b2 ... b1+b2+...+bn] b1+b2+...+bn].

    ‘                Increment [each].
                         yields [[1+b1 1+b1+b2 ... 1+b1+b2+...+bn] 1+b1+b2+...+bn].

     S€              Sum each list.
                         yields [[1+b1+1+b1+b2+...+1+b1+b2+...+bn] 1+b1+b2+...+bn].

       %65521        Modulo [each] by 65521.

             ḅ⁹²¤    Convert from base    65536    to integer.
              ⁹                        256
               ²                           squared
Freira Furada
fonte
Melhor ainda:⁹²¤
Dennis
1
@ Dennis Eu superei seus 18 bytes então.
Freira vazada
1
Bem, você já outgolfed ..
Leaky Nun
64

Mathematica, 46 bytes

{1,4^8}.Fold[##+{0,#&@@#}&,{1,0},#]~Mod~65521&

Uma função anônima que pega uma matriz inteira e retorna o Adler-32, com algumas melhorias de milhas e Martin (veja comentários).

miles 'também tem 46 bytes , mas é mais rápido:

{1,4^8}.{Tr@#+1,Tr[Accumulate@#+1]}~Mod~65521&
Mark Adler
fonte
37
... Você acabou de jogar seu próprio algoritmo famoso?
Mego
25
Perdoe-me se estou um pouco impressionado. Não é todo dia que você vê um nome tão grande na engenharia de software em nosso humilde e pequeno site. Bem vindo a bordo!
Mego
6
Não é tão grande assim.
Mark Adler
3
Se você está falando sério, é a primeira vez que penso em implementar o Adler-32 no Mathematica.
Mark Adler
9
Ou talvez você tenha esta solução pronta desde que ingressou na Code Golf, apenas esperando que ela seja solicitada. "Finalmente!" ;-)
Antti Haapala
13

Julia, 73 46 bytes

x->[sum(x)+1;sum(cumsum(x)+1)]%65521⋅[1;4^8]

Esta é uma função anônima que aceita uma matriz e retorna um número inteiro. Para chamá-lo, atribua-o a uma variável.

Combinamos sum(x) + 1e sum(cumsum(x) + 1)em uma matriz, onde xestá a matriz de entrada, e usamos cada módulo 65521. Em seguida, calculamos o produto escalar com 1 e 4 8 , o que nos dá (sum(x) + 1) + 4^8 * sum(cumsum(x) + 1), que é exatamente a fórmula de Adler-32.

Experimente online! (Inclui todos os casos de teste)

Economizou 27 bytes graças ao Sp3000 e ao Dennis!

Alex A.
fonte
Uau, isso é realmente inteligente.
gato
@cat Tenho Sp3000 e Dennis para agradecer a maior parte da esperteza. :)
Alex A.
11

função do código da máquina x86-64: 33 32 bytes (ou 31 30 bytes com uma int[]entrada em vez de char[])

função do código da máquina x86-32: 31 bytes

Como um fragmento de código inline-asm do GNU C: salva 2B 1B (apenas o retinsn).

Fonte comentada e driver de teste no github

A versão de 64 bits pode ser chamada diretamente de C com o System V x86-64 ABI padrão (usando 2 args fictícios para obter args nos registros desejados). Convenções de chamada personalizadas não são incomuns para código ASM, portanto, esse é um recurso de bônus.

O código da máquina de 32 bits economiza 1B, pois a fusão das metades alta e baixa push16/push16 => pop32funciona apenas no modo 32 bits. Uma função de 32 bits precisaria de uma convenção de chamada personalizada. Não devemos manter isso contra isso, mas chamar de C precisa de uma função de wrapper.

Após o processamento de 4096 ~(ASCII 126) bytes high = 0x3f040000, low = 0x7e001,. Portanto high, o bit mais significativo ainda não está definido. Meu código aproveita isso, inscrever-estendendo eaxpara edx:eaxcom cdqcomo uma maneira de zerar edx.

# See the NASM source below
0000000000401120 <golfed_adler32_amd64>:
  401120:       31 c0                   xor    eax,eax
  401122:       99                      cdq    
  401123:       8d 7a 01                lea    edi,[rdx+0x1]
0000000000401126 <golfed_adler32_amd64.byteloop>:
  401126:       ac                      lods   al,BYTE PTR ds:[rsi]
  401127:       01 c7                   add    edi,eax
  401129:       01 fa                   add    edx,edi
  40112b:       e2 f9                   loop   401126 <golfed_adler32_amd64.byteloop>
000000000040112d <golfed_adler32_amd64.end>:
  40112d:       66 b9 f1 ff             mov    cx,0xfff1
  401131:       92                      xchg   edx,eax
  401132:       99                      cdq    
  401133:       f7 f1                   div    ecx
  401135:       52                      push   rdx
  401136:       97                      xchg   edi,eax
  401137:       99                      cdq    
  401138:       f7 f1                   div    ecx
  40113a:       66 52                   push   dx      # this is the diff from last version: evil push/pop instead of shift/add
  40113c:       58                      pop    rax
  40113d:       66 5a                   pop    dx
  40113f:       c3                      ret    
0000000000401140 <golfed_adler32_amd64_end>:

0x40 - 0x20 = 32 bytes.


Fonte NASM comentada:

truques:

  • xchg eax, r32é um byte; mais barato que o mov. O 8086 precisava de dados no machado para muito mais coisas do que> = 386, então eles decidiram gastar muito espaço no código de operação no agora raramente usado xchg ax, r16.

  • A mistura de push64 e push16 para mesclar alto e baixo em um único registro salva as instruções de movimentação de dados reg-reg em torno de dois divs. A versão de 32 bits desse truque funciona ainda melhor: push16 / push16 / pop32é apenas 5B no total, não 6.

Como pressionamos / pop, isso não é seguro para asm inline no SysV amd64 ABI (com uma zona vermelha) .

golfed_adler32_amd64_v3:   ; (int dummy, const char *buf, int dummy, uint64_t len)

    ;; args: len in rcx,  const char *buf in rsi
    ;; Without dummy args, (unsigned len, const char *buf),  mov ecx, edi is the obvious solution, costing 2 bytes

    xor     eax,eax         ; scratch reg for loading bytes
    cdq                     ; edx: high=0
    lea     edi, [rdx+1]    ; edi: low=1
    ;jrcxz  .end            ; We don't handle len=0.  unlike rep, loop only checks rcx after decrementing
.byteloop:
    lodsb                   ; upper 24b of eax stays zeroed (no partial-register stall on Intel P6/SnB-family CPUs, thanks to the xor-zeroing)
    add     edi, eax        ; low += zero_extend(buf[i])
    add     edx, edi        ; high += low
    loop   .byteloop
.end:
    ;; exit when ecx = 0, eax = last byte of buf
    ;; lodsb at this point would load the terminating 0 byte, conveniently leaving eax=0

    mov     cx, 65521       ; ecx = m = adler32 magic constant.  (upper 16b of ecx is zero from the loop exit condition.  This saves 1B over mov r32,imm32)
    ;sub    cx, (65536 - 65521) ; the immediate is small enough to use the imm8 encoding.  No saving over mov, though, since this needs a mod/rm byte

    xchg    eax, edx        ; eax = high,  edx = buf[last_byte]
    cdq                     ; could be removed if we could arrange things so the loop ended with a load of the 0 byte

    div     ecx             ; div instead of idiv to fault instead of returning wrong answers if high has overflowed to negative.  (-1234 % m is negative)
    push    rdx             ; push high%m and 6B of zero padding

    xchg    eax, edi        ; eax=low
    cdq
    div     ecx             ; edx = low%m

    ;; concatenate the two 16bit halves of the result by putting them in contiguous memory
    push    dx              ; push low%m with no padding
    pop     rax             ; pop  high%m << 16 | low%m   (x86 is little-endian)

    pop     dx              ; add rsp, 2 to restore the stack pointer

    ;; outside of 16bit code, we can't justify returning the result in the dx:ax register pair
    ret
golfed_adler32_amd64_end_v3:

Eu também considerei usar rcxcomo um índice de matriz, em vez de ter dois contadores de loop, mas adler32 (s)! = Adler32 (reverse (s)). Então não podíamos usar loop. Contar de -len até zero e usar movzx r32, [rsi+rcx]apenas usa muitos bytes.

Se queremos considerar incrementar o ponteiro, o código de 32 bits provavelmente é o caminho a percorrer. Até o x32 ABI (ponteiros de 32 bits) não é suficiente, porque inc esié 2B no amd64, mas 1B no i386. Parece difícil de bater xor eax,eax/ lodsb/ loop: 4B total de obter cada elemento na viragem zero-estendido em eax. inc esi/ movzx r32, byte [esi]/ loopé 5B.

scasé outra opção para incrementar um ponteiro com uma instrução 1B no modo de 64 bits. ( rdi/ em edivez de rsi, então colocaríamos o ponteiro arg rdi). scasPorém, não podemos usar o resultado do sinalizador como uma condição de loop, porque não queremos manter o eax zerado. Alocação de registro diferente pode salvar um byte após o loop.


int[] entrada

A função completa uint8_t[]é a resposta "principal", porque é um desafio mais interessante. Descompactar para int[]é uma coisa irracional pedir ao nosso interlocutor nesse idioma, mas economiza 2B.

Se considerarmos nossa entrada como uma matriz descompactada de números inteiros de 32 bits, podemos salvar um byte facilmente (use lodsde substitua xor eax,eax / cdqpor just xor edx,edx).

Podemos salvar outro byte zerando edx com lodsd/ cdqe reorganizando o loop para que ele carregue o elemento 0 final antes de sair. (Ainda estamos assumindo que ela existe, mesmo que seja uma matriz int, não uma sequência).

; untested: I didn't modify the test driver to unpack strings for this
golfed_adler32_int_array:
    ; xor   edx,edx
    lodsd                   ; first element. only the low byte non-zero
    cdq                     ; edx: high=0
    lea     edi, [rdx+1]    ; edi: low=1
    ;jrcxz  .end            ; handle len=0?  unlike rep, loop only checks rcx after decrementing
.intloop:
    add     edi, eax        ; low += buf[i]
    add     edx, edi        ; high += low
    lodsd                   ; load buf[i+1] for next iteration
    loop   .intloop
.end:
    ;; exit when ecx = 0, eax = terminating 0

    xchg    eax, edx
    ;cdq               ; edx=0 already, ready for div
    ; same as the char version

Também fiz uma versão não testada que usa scasd(versão 1B de add edi,4) e em add eax, [rdi]vez de lodsd, mas também tem 30 bytes. As economias de ter highno eax no final do loop são compensadas por códigos maiores em outros lugares. 0Porém, ele tem a vantagem de não depender de um elemento de terminação na entrada, o que talvez não seja razoável para uma matriz descompactada, na qual também recebemos explicitamente o comprimento.


Driver de teste C ++ 11

Veja o link do github. Essa resposta estava ficando muito grande e o driver de teste obteve mais recursos com código maior.

Peter Cordes
fonte
2
Eu permiti números inteiros em vez de bytes, principalmente porque muitos idiomas nem sequer têm um tipo de byte. Números inteiros de 32 bits podem ser uma opção não natural para montagem, mas o código de golfe consiste em extrair o último byte enquanto permanece dentro das regras. Se uma opção "não natural" levar a uma contagem de bytes mais baixa, eu diria que faça isso.
Dennis
@ Dennis: Eu entendo a necessidade da regra para alguns idiomas. Eu gostaria que houvesse uma maneira de a regra permitir que você usasse apenas int[]se necessário, ou salvasse mais de 4 bytes de código ou algo assim. Não tenho nenhum problema em apresentar uma solução para o adler32(int[])problema, mas sinto que o adler32(char[])problema é mais interessante, pois é a verdadeira função adler32. É o que eu realmente quero jogar golfe em asm. (E eu adoraria salvar mais um byte de alguma forma, já que na vida real asm, 33 bytes = 48 bytes se a próxima função usar ALIGN 16). Acho que vou continuar jogando golfe.
Peter Cordes
@ Dennis: também, precisamos lidar com o caso len = 0? Eu salvo 2B usando um do{}while(--len)estilo de loop em vez de a while(len--){}.
Peter Cordes
4
Quando se trata de explicações, quanto mais detalhado, melhor.
Dennis
3
@cat: Não, eu não acho asm doloroso. Eu não gastaria meu tempo escrevendo respostas do Stackoverflow para perguntas de desempenho / asm e atualizando o wiki da tag x86 se o fiz: P Se você quiser saber por que o código é lento ou rápido, é necessário examinar e entender o asm. Depois de fazer isso por um tempo, você começa a ver quando o compilador poderia ter feito um código mais rápido ... e, eventualmente, começa a pensar em como o compilador pode compilar o código enquanto você o escreve. Otimizar o tamanho do código em vez do desempenho é uma mudança interessante às vezes.
Peter Cordes
8

MATL , 22 bytes

tsQwYsQsh16W15-\l8Mh*s

A entrada pode ser uma matriz de números ou a sequência ASCII correspondente.

Experimente online!

Explicação

t       % Take array or string as input. Duplicate
sQ      % Sum all its values, and add 1
wYsQs   % Swap. Cumulative sum, add 1, sum
h       % Concatenate horizontally
16W     % 2^16: gives 65536
15-     % Subtract 15: gives 65521
\       % Element-wise modulo operation
l       % Push 1
8M      % Push 65536 again
h       % Concatenate horizontally: gives array [1, 65535]
*s      % Element-wise multiplication and sum. Display
Luis Mendo
fonte
7

Na verdade, 36 bytes

;Σu@;╗lR`╜HΣu`MΣk`:65521@%`M1#84ⁿ@q*

Experimente online!

Explicação:

;Σu@;╗lR`╜HΣu`MΣk`:65521@%`M1#84ⁿ@q*
;Σu                                   sum(input)+1
   @;╗lR                              push a copy of input to reg0, push range(1, len(input)+1)
        `╜HΣu`M                       map over range: sum(head(reg0,n))+1
               Σk                     sum, combine lower and upper into a list
                 `:65521@%`M          modulo each by 65521
                            1#84ⁿ@q*  dot product with [1,4**8]
Mego
fonte
7

Java, 84 bytes

long a(int[]i){long a=1,b=0;for(int p:i)b=(b+(a=(a+p)%(p=65521)))%p;return b<<16|a;}

Se as soluções Java sempre devem ser um código compilável completo, entre em contato.

Ungolfed

long a(int[] i) {
    long a = 1, b = 0;
    for (int p : i) b = (b + (a = (a + p) % (p = 65521))) % p;
    return b << 16 | a;
}

Nota

Você precisará converter a entrada Stringpara int[]( int[]é um byte menor que byte[]ou char[]).

Saída

String:     "Eagles are great!"
Byte Array: [69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]
Checksum:   918816254
Expected:   918816254

String:     "Programming Puzzles & Code Golf"
Byte Array: [80, 114, 111, 103, 114, 97, 109, 109, 105, 110, 103, 32, 80, 117, 122, 122, 108, 101, 115, 32, 38, 32, 67, 111, 100, 101, 32, 71, 111, 108, 102]
Checksum:   3133147946
Expected:   3133147946

String:     "~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"
Byte Array: [126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126, 126]
Checksum:   68095937
Expected:   68095937

String:     "?????????...?"
Byte Array: [63, 63, 63, 63, 63, 63, 63, 63, 63, ...,63]
Checksum:   2181038080
Expected:   2181038080
Marv
fonte
1
Boa resposta e bem-vindo ao site! Além disso, soluções que não são completas e compiláveis ​​são boas, a menos que o desafio indique explicitamente que deve ser um programa completo. Esta é uma função completa, por isso conta.
DJMcMayhem
6

Piet, 120 Codels codelsize 1

Com codelsize 20:

codelsize 20

Notas / Como funciona?

  • Como não é possível usar uma matriz ou string como entrada, esse programa funciona usando uma série de números inteiros (representando caracteres ascii) como entradas. Pensei em usar as entradas de caracteres no início, mas lutei para encontrar uma boa solução para a terminação, então agora termina quando qualquer número menor que 1 é inserido. Originalmente, eram apenas valores negativos para finalização, mas tive que alterar a inicialização após escrever o programa, agora não posso ajustar o necessário 2, apenas um 1(26/45 na imagem de rastreamento). Isso não importa, porque de acordo com as regras do desafio, apenas caracteres ascii imprimíveis são permitidos.

  • Durante muito tempo, lutei para reinserir o loop, apesar de eu ter encontrado a solução bastante elegante no final. Sem pointerou switchoperações, apenas o intérprete correr em paredes até que ele transições de volta para a CODEL verde para ler a entrada (43-> 44 nas imagens traço).

  • A terminação do loop é obtida duplicando primeiro a entrada, adicionando 1 e depois verificando se é maior que 1. Se for, o seletor de codel é acionado e a execução continua no caminho inferior. Caso contrário, o programa continua à esquerda (codelos amarelos brilhantes, 31/50 nas imagens de rastreamento).

  • O tamanho da entrada suportada depende da implementação do intérprete, embora seja possível suportar uma entrada arbitrariamente grande com o intérprete correto (por exemplo, um intérprete Java que use BigIntegercomo valores internos)

  • Só vi que a configuração inclui um desnecessário DUPe CC(7-> 8-> 9 nas imagens de rastreamento). Não faço ideia de como isso aconteceu. Este é efetivamente um noop, porém, alterna o seletor de codel 16 vezes, o que resulta em nenhuma alteração.

Imagens de rastreamento Npiet

Configuração e primeiro loop:

starttrace

Terminação, saída e saída do loop:

traço final

Saídas

Perdoe-me se eu incluir apenas uma saída, leva muito tempo para inserir: ^)

String: "Eagles are great!"

PS B:\Marvin\Desktop\Piet> .\npiet.exe adler32.png
? 69
? 97
? 103
? 108
? 101
? 115
? 32
? 97
? 114
? 101
? 32
? 103
? 114
? 101
? 97
? 116
? 33
? -1
918816254

Rastreio de Npiet para [65, -1]

trace: step 0  (0,0/r,l nR -> 1,0/r,l dR):
action: push, value 4
trace: stack (1 values): 4

trace: step 1  (1,0/r,l dR -> 2,0/r,l dB):
action: duplicate
trace: stack (2 values): 4 4

trace: step 2  (2,0/r,l dB -> 3,0/r,l nM):
action: multiply
trace: stack (1 values): 16

trace: step 3  (3,0/r,l nM -> 4,0/r,l nC):
action: duplicate
trace: stack (2 values): 16 16

trace: step 4  (4,0/r,l nC -> 5,0/r,l nY):
action: duplicate
trace: stack (3 values): 16 16 16

trace: step 5  (5,0/r,l nY -> 6,0/r,l nM):
action: duplicate
trace: stack (4 values): 16 16 16 16

trace: step 6  (6,0/r,l nM -> 7,0/r,l nC):
action: duplicate
trace: stack (5 values): 16 16 16 16 16

trace: step 7  (7,0/r,l nC -> 8,0/r,l nY):
action: duplicate
trace: stack (6 values): 16 16 16 16 16 16

trace: step 8  (8,0/r,l nY -> 9,0/r,l lB):
action: switch
trace: stack (5 values): 16 16 16 16 16
trace: stack (5 values): 16 16 16 16 16

trace: step 9  (9,0/r,l lB -> 10,0/r,l dM):
action: multiply
trace: stack (4 values): 256 16 16 16

trace: step 10  (10,0/r,l dM -> 11,0/r,l nR):
action: multiply
trace: stack (3 values): 4096 16 16

trace: step 11  (11,0/r,l nR -> 12,0/r,l lY):
action: multiply
trace: stack (2 values): 65536 16

trace: step 12  (12,0/r,l lY -> 13,0/r,l lM):
action: duplicate
trace: stack (3 values): 65536 65536 16

trace: step 13  (13,0/r,l lM -> 14,0/r,l nM):
action: push, value 3
trace: stack (4 values): 3 65536 65536 16

trace: step 14  (14,0/r,l nM -> 15,0/r,l dM):
action: push, value 2
trace: stack (5 values): 2 3 65536 65536 16

trace: step 15  (15,0/r,l dM -> 16,0/r,l lC):
action: roll
trace: stack (3 values): 16 65536 65536

trace: step 16  (16,0/r,l lC -> 17,0/r,l nB):
action: sub
trace: stack (2 values): 65520 65536

trace: step 17  (17,0/r,l nB -> 18,0/r,l dB):
action: push, value 1
trace: stack (3 values): 1 65520 65536

trace: step 18  (18,0/r,l dB -> 19,0/r,l dM):
action: add
trace: stack (2 values): 65521 65536

trace: step 19  (19,0/r,l dM -> 19,1/d,r dC):
action: duplicate
trace: stack (3 values): 65521 65521 65536

trace: step 20  (19,1/d,r dC -> 18,1/l,l lC):
action: push, value 1
trace: stack (4 values): 1 65521 65521 65536

trace: step 21  (18,1/l,l lC -> 17,1/l,l nC):
action: push, value 1
trace: stack (5 values): 1 1 65521 65521 65536

trace: step 22  (17,1/l,l nC -> 16,1/l,l dB):
action: sub
trace: stack (4 values): 0 65521 65521 65536

trace: step 23  (16,1/l,l dB -> 15,1/l,l lB):
action: push, value 1
trace: stack (5 values): 1 0 65521 65521 65536

trace: step 24  (15,1/l,l lB -> 13,2/l,l dG):
action: in(number)
? 65
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 25  (13,2/l,l dG -> 12,2/l,l dR):
action: duplicate
trace: stack (7 values): 65 65 1 0 65521 65521 65536

trace: step 26  (12,2/l,l dR -> 11,2/l,l lR):
action: push, value 1
trace: stack (8 values): 1 65 65 1 0 65521 65521 65536

trace: step 27  (11,2/l,l lR -> 10,2/l,l lY):
action: add
trace: stack (7 values): 66 65 1 0 65521 65521 65536

trace: step 28  (10,2/l,l lY -> 9,2/l,l nY):
action: push, value 1
trace: stack (8 values): 1 66 65 1 0 65521 65521 65536

trace: step 29  (9,2/l,l nY -> 8,1/l,r nB):
action: greater
trace: stack (7 values): 1 65 1 0 65521 65521 65536

trace: step 30  (8,1/l,r nB -> 7,1/l,r lY):
action: switch
trace: stack (6 values): 65 1 0 65521 65521 65536
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 31  (7,1/l,l lY -> 6,2/l,l nY):
action: push, value 2
trace: stack (7 values): 2 65 1 0 65521 65521 65536

trace: step 32  (6,2/l,l nY -> 5,3/l,l dB):
action: pointer
trace: stack (6 values): 65 1 0 65521 65521 65536

trace: step 33  (5,3/r,l dB -> 7,4/r,l dM):
action: add
trace: stack (5 values): 66 0 65521 65521 65536

trace: step 34  (7,4/r,l dM -> 8,4/r,l dC):
action: duplicate
trace: stack (6 values): 66 66 0 65521 65521 65536

trace: step 35  (8,4/r,l dC -> 9,3/r,l lC):
action: push, value 3
trace: stack (7 values): 3 66 66 0 65521 65521 65536

trace: step 36  (9,3/r,l lC -> 10,3/r,l nC):
action: push, value 2
trace: stack (8 values): 2 3 66 66 0 65521 65521 65536

trace: step 37  (10,3/r,l nC -> 11,3/r,l dY):
action: roll
trace: stack (6 values): 0 66 66 65521 65521 65536

trace: step 38  (11,3/r,l dY -> 12,3/r,l dG):
action: add
trace: stack (5 values): 66 66 65521 65521 65536

trace: step 39  (12,3/r,l dG -> 13,3/r,l lG):
action: push, value 2
trace: stack (6 values): 2 66 66 65521 65521 65536

trace: step 40  (13,3/r,l lG -> 14,3/r,l nG):
action: push, value 1
trace: stack (7 values): 1 2 66 66 65521 65521 65536

trace: step 41  (14,3/r,l nG -> 15,3/r,l dR):
action: roll
trace: stack (5 values): 66 66 65521 65521 65536
trace: white cell(s) crossed - continuing with no command at 17,3...

trace: step 42  (15,3/r,l dR -> 17,3/r,l lB):

trace: step 43  (17,3/r,l lB -> 13,2/l,l dG):
action: in(number)
? -1
trace: stack (6 values): -1 66 66 65521 65521 65536

trace: step 44  (13,2/l,l dG -> 12,2/l,l dR):
action: duplicate
trace: stack (7 values): -1 -1 66 66 65521 65521 65536

trace: step 45  (12,2/l,l dR -> 11,2/l,l lR):
action: push, value 1
trace: stack (8 values): 1 -1 -1 66 66 65521 65521 65536

trace: step 46  (11,2/l,l lR -> 10,2/l,l lY):
action: add
trace: stack (7 values): 0 -1 66 66 65521 65521 65536

trace: step 47  (10,2/l,l lY -> 9,2/l,l nY):
action: push, value 1
trace: stack (8 values): 1 0 -1 66 66 65521 65521 65536

trace: step 48  (9,2/l,l nY -> 8,1/l,r nB):
action: greater
trace: stack (7 values): 0 -1 66 66 65521 65521 65536

trace: step 49  (8,1/l,r nB -> 7,1/l,r lY):
action: switch
trace: stack (6 values): -1 66 66 65521 65521 65536
trace: stack (6 values): -1 66 66 65521 65521 65536

trace: step 50  (7,1/l,r lY -> 6,1/l,r dY):
action: pop
trace: stack (5 values): 66 66 65521 65521 65536

trace: step 51  (6,1/l,r dY -> 4,1/l,r lY):
action: push, value 3
trace: stack (6 values): 3 66 66 65521 65521 65536

trace: step 52  (4,1/l,r lY -> 3,1/l,r nY):
action: push, value 2
trace: stack (7 values): 2 3 66 66 65521 65521 65536

trace: step 53  (3,1/l,r nY -> 2,1/l,r nM):
action: duplicate
trace: stack (8 values): 2 2 3 66 66 65521 65521 65536

trace: step 54  (2,1/l,r nM -> 1,1/l,r dG):
action: pointer
trace: stack (7 values): 2 3 66 66 65521 65521 65536

trace: step 55  (1,1/r,r dG -> 2,2/r,r lR):
action: roll
trace: stack (5 values): 65521 66 66 65521 65536

trace: step 56  (2,2/r,r lR -> 2,3/d,l nR):
action: push, value 1
trace: stack (6 values): 1 65521 66 66 65521 65536

trace: step 57  (2,3/d,l nR -> 2,4/d,l lC):
action: switch
trace: stack (5 values): 65521 66 66 65521 65536
trace: stack (5 values): 65521 66 66 65521 65536

trace: step 58  (2,4/d,r lC -> 2,5/d,r nM):
action: mod
trace: stack (4 values): 66 66 65521 65536

trace: step 59  (2,5/d,r nM -> 4,5/r,r dM):
action: push, value 3
trace: stack (5 values): 3 66 66 65521 65536

trace: step 60  (4,5/r,r dM -> 6,5/r,r lM):
action: push, value 2
trace: stack (6 values): 2 3 66 66 65521 65536

trace: step 61  (6,5/r,r lM -> 7,5/r,r nC):
action: roll
trace: stack (4 values): 65521 66 66 65536

trace: step 62  (7,5/r,r nC -> 8,5/r,r dM):
action: mod
trace: stack (3 values): 66 66 65536

trace: step 63  (8,5/r,r dM -> 11,5/r,r lM):
action: push, value 3
trace: stack (4 values): 3 66 66 65536

trace: step 64  (11,5/r,r lM -> 12,5/r,r nM):
action: push, value 1
trace: stack (5 values): 1 3 66 66 65536

trace: step 65  (12,5/r,r nM -> 13,5/r,r dC):
action: roll
trace: stack (3 values): 66 65536 66

trace: step 66  (13,5/r,r dC -> 14,5/r,r nB):
action: multiply
trace: stack (2 values): 4325376 66

trace: step 67  (14,5/r,r nB -> 15,5/r,r nM):
action: add
trace: stack (1 values): 4325442

trace: step 68  (15,5/r,r nM -> 16,5/r,r dB):
action: out(number)
4325442
trace: stack is empty
trace: white cell(s) crossed - continuing with no command at 19,5...

trace: step 69  (16,5/r,r dB -> 19,5/r,r nM):
Marv
fonte
5

C89, 70 bytes

h,l,m=65521;A(char*B){h=0;l=1;while(*B)h+=l+=*B++;return h%m<<16|l%m;}

Para testar (compilar com gcc -std=c89 -lm golf.c):

#include <stdio.h>
int main(int argc, char** argv) {
    printf("%u\n", A("Eagles are great!"));
    printf("%u\n", A("Programming Puzzles & Code Golf"));
    printf("%u\n", A("~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~"));
    return 0;
}
orlp
fonte
É assim que a zlibfonte se parece? Hm ...
cat
1
Essa implementação foi um bom ponto de partida para minha versão do x86 asm.
Peter Cordes
Pode salvar 1 byte usando em forvez de while:for(h=0,l=1;*B;)h+=l+=*B++;
ninjalj 1/11/16
5

Labirinto , 37 36 32 31 bytes

}?"{655:}21:}%=}){%{{36*+!
:++)

Experimente online!

Insira como uma lista de números inteiros. O programa termina com um erro (cuja mensagem de erro vai para STDERR).

Explicação

Primário labirinto:

  • O labirinto possui duas pilhas de números inteiros de precisão arbitrária, principal e auxiliar (iliária), que são inicialmente preenchidos com uma quantidade infinita (implícita) de zeros.
  • O código fonte se assemelha a um labirinto, onde o ponteiro de instrução (IP) segue os corredores quando pode (mesmo nos cantos). O código começa no primeiro caractere válido em ordem de leitura, ou seja, no canto superior esquerdo neste caso. Quando o IP chega a qualquer forma de junção (ou seja, várias células adjacentes além daquela de onde veio), ele selecionará uma direção com base no topo da pilha principal. As regras básicas são: vire à esquerda quando negativo, continue em frente quando zero, vire à direita quando positivo. E quando uma dessas opções não for possível porque existe uma parede, o IP seguirá na direção oposta. O IP também muda ao atingir becos sem saída.
  • Os dígitos são processados ​​multiplicando a parte superior da pilha principal por 10 e adicionando o dígito. Para iniciar um novo número, você pode pressionar um zero com _.

Embora o código comece com uma "sala" de 4x2, na verdade são dois loops separados por dois e dois. Por acaso, o IP mantém um loop por vez devido aos valores da pilha.

Portanto, o código começa com um loop 2x2 (sentido horário) que lê a entrada enquanto calcula o prefixo:

}   Move last prefix sum over to aux.
?   Read an integer from STDIN or push 0 on EOF, which exits the loop.
+   Add current value to prefix sum.
:   Duplicate this prefix sum.

Agora, temos todas as somas de prefixo na pilha auxiliar , bem como uma cópia da soma de todos os valores e 0do EOF no principal . Com isso, inserimos outro loop 2x2 (sentido horário) que soma todos os prefixos a serem computados HIGH.

"   No-op. Does nothing.
{   Pull one prefix sum over from aux. When we're done, this fetches a 0,
    which exits the loop.
)   Increment prefix sum.
+   Add it to HIGH.

A pilha principal agora tem LOW - 1e HIGHe zero, exceto que ainda não tomamos o módulo. O restante do código é completamente linear:

655      Turn the zero into 655.
:}       Make a copy and shift it over to aux.
21       Turn the copy on main into 65521.
:}       Make a copy and shift it over to aux.
%        Take HIGH mod 65521.
=        Swap HIGH with the other copy of 65521 on aux.
}){      Move 65521 back to aux, increment LOW-1 to LOW, 
         move 65521 back to main.
%        Take LOW mod 65521.
{        Move HIGH back to main.
{        Move the other copy of 655 back to main.
36       Turn it into 65536.
*        Multiply HIGH by that.
+        Add it to LOW.
!        Print it.

O IP agora atinge um beco sem saída e se vira. O +e *são essencialmente não-ops, devido aos zeros na parte inferior da pilha. O 36agora transforma o topo do main em 63, mas os dois {{puxam dois zeros de aux em cima dele. Em seguida, %tenta dividir por zero, que finaliza o programa.

Observe que o Labyrinth usa números inteiros de precisão arbitrária, portanto, adiar o módulo até o final da soma não causará problemas com o excesso de números inteiros.

Martin Ender
fonte
5

Python 2, 60 58 bytes

H=h=65521
l=1
for n in input():l+=n;h+=l
print h%H<<16|l%H

Uma abordagem bastante direta. Este é um programa completo que pega uma lista de números inteiros via STDIN, por exemplo [72, 105, 33].

(Obrigado a @xnor pela incrível dica de aliasing / inicialização)

Sp3000
fonte
2
Você pode fazer H=h=65521para inicializar henquanto aliasing 65521.
xnor
4

J, 30 bytes

+/(+65536&*)&(65521|+/)&:>:+/\

Provavelmente isso poderia ser mais condensado com um trem diferente.

Uso

Aqui x $ ycria uma lista com xcópias de y.

   f =: +/(+65536&*)&(65521|+/)&:>:+/\
   f 69 97 103 108 101 115 32 97 114 101 32 103 114 101 97 116 33
918816254
   f 80 114 111 103 114 97 109 109 105 110 103 32 80 117 122 122 108 101 115 32 38 32 67 111 100 101 32 71 111 108 102
3133147946
   f (32 $ 126)
68095937
   f (1040 $ 63)
2181038080
   f (4096 $ 255)
2170679522

Explicação

+/(+65536&*)&(65521|+/)&:>:+/\
f (           g           ) h     Monad train (f g h) y = (f y) g (h y)
+/                                Sum the input list
                           +/\    Sum each prefix of the input, forms a list
x     f   &   g   &:   h    y     Composed verbs, makes (g (h x)) f (g (h y))
                         >:       Increment the sum and increment each prefix sum
               (m f g) y          Hook, makes m f (g y)
                    +/            Sum the prefix sums
              65521|              Take the sum and prefix total mod 65521
    (f g) y                       Hook again
    65536&*                       Multiply the prefix total by 65536
                                  This is a bonded verb, it will only multiply
                                  using a fixed value now
   +                              Add the sum and scaled prefix total
milhas
fonte
4

Oitava, 52 50 bytes

Guardado 2 bytes graças a @LuisMendo

@(B)mod([sum(S=cumsum(B)+1),S(end)],65521)*[4^8;1]

Toma uma matriz de números inteiros como entrada.

low é obtido do último elemento de high (antes da soma) em vez de calcular explicitamente a soma, economizando um total geral de ... 1 byte !

Amostra executada em ideone .

taça
fonte
@LuisMendo Ooh, eu esqueci +B. Eu acho que a especificação de entrada diz que você pode pegar números inteiros, então talvez eu faça isso.
copo
3

CJam, 30 29 bytes

q~{1$+}*]:)_W>]1fb65521f%2G#b

Insira como uma lista de números inteiros.

Teste aqui.

Explicação

q~       e# Read and evaluate input.
{        e# Fold this block over the list, computing prefix sums.
  1$+    e#   Copy the last prefix and add the current element.
}*
]        e# Wrap the prefix sums in an array.
:)       e# Increment each. This will sum to HIGH.
_W>      e# Copy the list and truncate to only the last element, i.e.
         e# the sum of the entire input plus 1. This is LOW.
]        e# Wrap both of those lists in an array.
1fb      e# Sum each, by treating it as base 1 digits.
65521f%  e# Take each modulo 65521.
2G#b     e# Treat the list as base 65536 digits, computing 65536*HIGH + LOW.
Martin Ender
fonte
3

Perl 6 , 60 bytes

{(.sum+1)%65521+65536*((sum(1,*+.shift...->{!$_})-1)%65521)}

Explicação:

{
  # $_ is the implicit parameter for this lambda because this block doesn't have
  # an explicit parameter, and @_ isn't seen inside of it.
  # ( @_ takes precedence over $_ when it is seen by the compiler )

  # .sum is short for $_.sum
  ( .sum + 1 ) % 65521 + 65536
  *
  (
    (
      sum(

        # generate a sequence:

        1,         # starting with 1
        * + .shift # lambda that adds previous result (*) with $_.shift
        ...        # generate until:
        -> { !$_ } # $_ is empty

        # ^ I used a pointy block with zero parameters
        # so that the block doesn't have an implicit parameter
        # like the surrounding block

        # this is so that $_ refers to the outer $_

      ) - 1        # remove starting value
    ) % 65521
  )
}

Teste:

#! /usr/bin/env perl6
use v6.c;
use Test;

# give the lambda a name
my &Adler32 = {(.sum+1)%65521+65536*((sum(1,*+.shift...->{!$_})-1)%65521)}

my @tests = (
  (  918816254,  'Eagles are great!'),
  ( 3133147946,  'Programming Puzzles & Code Golf'),
  (   68095937,  '~' x 32,     "'~' x 32"),
  ( 2181038080,  63 xx 1040,   "'?' x 1040"),
);

plan +@tests;

for @tests -> ($checksum, $input, $gist? ) {
  my @array := do given $input {
    when Str { .encode.Array }
    default { .Array }
  }

  is Adler32(@array), $checksum, $gist // $input.perl
}
1..4
ok 1 - "Eagles are great!"
ok 2 - "Programming Puzzles \& Code Golf"
ok 3 - '~' x 32
ok 4 - '?' x 1040
Brad Gilbert b2gills
fonte
3

Python 3 (79 bytes)

Baseado na solução de R. Kap.

lambda w,E=65521:(1+sum(w))%E+(sum(1+sum(w[:i+1])for i in range(len(w)))%E<<16)

Substituí a multiplicação por um turno e tirei um par de colchetes.

Como não posso postar comentários, fiz uma nova resposta.

R2D2
fonte
3

Esquema, 195 bytes

(define(a b)(+(let L((b b)(s 1))(if(=(length b)0)s(L(cdr b)(modulo(+ s(car b))65521))))(* 65536(let H((b b)(s 1)(t 0))(if(=(length b)0)t(let((S(+ s(car b))))(H(cdr b)S(modulo(+ t S)65521))))))))

Se não fosse por todos esses parênteses ...

Numeri diz Restabelecer Monica
fonte
3

Haskell, 54 50 bytes

m=(`mod`65521).sum
g x=m(-1:scanl(+)1x)*4^8+m(1:x)

Exemplo de uso: g [69,97,103,108,101,115,32,97,114,101,32,103,114,101,97,116,33]-> 918816254.

scanlinclui o valor inicial (-> 1) na lista (-> [1,1+b1,1+b1+b2,..]), de modo que sumé desativado por 1, que é fixado anexando -1a lista antes da soma.

Edit: Obrigado @xnor por 4 bytes.

nimi
fonte
Parece que você pode extrair a soma em m: m=(`mod`65521).sum g x=m(-1:scanl(+)1x)*4^8+m(1:x). Provavelmente, há uma maneira melhor de corrigir as somas do que o anexo.
Xnor
3

JavaScript (ES7), 52 50 bytes

a=>a.map(b=>h+=l+=b,h=0,l=1)&&l%65521+h%65521*4**8

O ES6 ocupa 51 bytes (substitua 4 ** 8 por 65536). Se você deseja uma versão de string, então, para 69 bytes:

s=>[...s].map(c=>h+=l+=c.charCodeAt(),h=0,l=1)&&l%65521+h%65521*65536

Editar: salvou 2 bytes graças a @ user81655.

Neil
fonte
3

Função ARM Thumb-2 que aceita uint8_t[]: 40 bytes (36B para ABI não padrão e int[])

Características: módulo não diferido, portanto entradas de tamanho arbitrário são boas. Na verdade, não usa a instrução de divisão, por isso não é lento. (err, pelo menos não por esse motivo: P)

Economias de seguir regras menos estritas:

  • -2B se não precisarmos salvar registros antes de usá-los.
  • -2B por exigir que o chamador descompacte bytes em uma uint32_t[]matriz.

Então, o melhor caso é 36B.

// uint8_t *buf in r0,  uint32_t len in r1
00000000 <adler32arm_golf2>:
   0:   b570            push    {r4, r5, r6, lr} //
   2:   2201            movs    r2, #1          // low
   4:   2300            movs    r3, #0          // high
   6:   f64f 75f1       movw    r5, #65521      ; 0xfff1 = m
0000000a <adler32arm_golf2.byteloop>:
   a:   f810 4b01       ldrb.w  r4, [r0], #1    // post-increment byte-load
   e:   4422            add     r2, r4          // low += *B
  10:   4413            add     r3, r2          // high += low
  12:   42aa            cmp     r2, r5          // subtract if needed instead of deferred modulo
  14:   bf28            it      cs
  16:   1b52            subcs   r2, r2, r5
  18:   42ab            cmp     r3, r5
  1a:   bf28            it      cs              // Predication in thumb mode is still possible, but takes a separate instruction
  1c:   1b5b            subcs   r3, r3, r5
  1e:   3901            subs    r1, #1          // while(--len)
  20:   d1f3            bne.n   a <.byteloop2>
  22:   eac2 4003       pkhbt   r0, r2, r3, lsl #16   // other options are the same size: ORR or ADD.
  26:   bd70            pop     {r4, r5, r6, pc}  // ARM can return by popping the return address (from lr) into the pc; nifty
00000028 <adler32arm_end_golf2>:

0x28 = 40 bytes


Notas:

Em vez de log%mno final, fazemos if(low>=m) low-=mdentro do loop. Se fizermos baixo antes do alto, sabemos que nenhum deles pode exceder 2*m; portanto, o módulo é apenas uma questão de subtrair ou não. A cmpe predicado subsão apenas 6B no modo Thumb2. O idioma padrão para% é 8B no modo Thumb2:

UDIV R2, R0, R1         // R2 <- R0 / R1
MLS  R0, R1, R2, R0     // R0 <- R0 - (R1 * R2 )

A adler(char *)versão de comprimento implícito é do mesmo tamanho de código que o comprimento explícito adler(uint8_t[], uint32_t len). Podemos definir sinalizadores para a condição de saída de loop com uma única instrução 2B de qualquer maneira.

A versão de comprimento implícito tem a vantagem de trabalhar corretamente com a sequência vazia, em vez de tentar repetir 2 ^ 32 vezes.


montar / compilar com:

arm-linux-gnueabi-as --gen-debug -mimplicit-it=always -mfloat-abi=soft -mthumb adler32-arm.S

ou

arm-linux-gnueabi-g++ -Wa,-mimplicit-it=always -g -static -std=gnu++14 -Wall -Wextra -Os -march=armv6t2 -mthumb -mfloat-abi=soft test-adler32.cpp -fverbose-asm adler32-arm.S -o test-adler32
qemu-arm ./test-adler32

Sem -static, o processo em execução qemu-armnão encontrou o vinculador dinâmico. (E sim, eu instalar um ARM configuração cross-devel apenas para esta resposta, porque eu pensei que a minha ideia baseia-subtrair foi arrumado.) No amd64 Ubuntu, instalar gcc-arm-linux-gnueabi, g++-arm-linux-gnueabi. Eu achei gdb-arm-none-eabimeio que mal trabalhado conectando qemu-arm -g port.

Fonte comentada:

// There's no directive to enable implicit-it=always

// gcc uses compiler uses these in its output
.syntax unified
.arch armv8-a
.fpu softvfp

.thumb      @ aka .code 16

.p2align 4
.globl adler32arm_golf    @ put this label on the one we want to test

.thumb_func
adler32arm_golf:
adler32arm_golf2:   @ (uint8_t buf[], uint32_t len)
        @ r0 = buf
        @ r1 = len
        push    {r4, r5, r6, lr}   @ even number of regs keeps the stack aligned.  Good style? since there's no code-size saving

        movs    r2, #1          @ r2: low
        movs    r3, #0          @ r3: high
                                @ r4 = tmp for loading bytes
        movw    r5, #65521      @ r5: modulo constant

adler32arm_golf2.byteloop2:
        ldrb    r4, [r0], #1    @ *(buf++) post-increment addressing.  4B encoding
        @ldrb    r4, [r0, r1]   @ 2B encoding, but unless we make the caller pass us buf+len and -len, it needs extra code somewhere else
        @ldmia   r0!, {r4}      @ int[] version:  r4 = [r0]; r0+=4;  post-increment addressing.  2B encoding.

        add     r2, r2, r4      @ low += tmp
        add     r3, r3, r2      @ high += low;   // I think it's safe to do this before the modulo range-reduction for low, but it would certainly work to put it after.

        cmp     r2, r5
        subhs   r2, r5          @ if(low>=m) low-=m;   @ 6B total for %.  predicated insns require an IT instruction in thumb2

        cmp     r3, r5
        subhs   r3, r5          @ if(high>=m) high-=m;  // equivalent to high %= m.

        @sub    r1, #1          @ 4B encoding: sub.w to not set flags with immediate
        subs    r1, #1          @ len-- and set flags.  2B encoding
        @cmp    r4, #0          @ null-termination check. 2B encoding
        bne     adler32arm_golf2.byteloop2

@        udiv    r0, r2, r5            @ normal way to do one of the modulos
@        mls     r2, r5, r0, r2         @ r2 = low % m.  8B total for %

        PKHBT   r0, r2, r3, lsl #16     @ 4B   r0 = [ high%m <<16  |   low%m  ]
        @orr     r0, r0, r4, lsl #16    @ 4B
        @orr     r0, r0, r4             @ 4B
        @add     r0, r2, r3, lsl #16    @ 4B
        @add     r0, r0, r4             @ 2B
        pop     {r4, r5, r6, pc}        @ ARM can return by popping the return address (saved from lr) into pc.  Nifty
adler32arm_end_golf2:

test-adler32.cpptem os mesmos casos de teste e main()quanto à minha resposta x86-64, mas começa assim:

#include <stdint.h>
uint32_t adler32_simple(const uint8_t *B) {
  const uint32_t m=65521;

  uint32_t h=0, l=1;
  do {
    l += *B++;        // Borrowed from orlp's answer, as a simple reference implementation
    h += l;
    l %= m; h %= m;   // with non-deferred modulo if this is uncommented
  } while(*B);

  return h%m<<16|l%m;
}


#include <stdio.h>
//#include <zlib.h>
#include <string.h>
#include <assert.h>
#include <string>   // useful for the memset-style constructors that repeat a character n times


extern "C" {
    unsigned golfed_adler32_amd64(int /*dummy1*/, const char *buf, int /*dummy2*/, unsigned len);
    unsigned adler32arm_golf(const char *buf, unsigned len);
}
#ifdef __amd64__
#define golfed_adler32(buf, len)   golfed_adler32_amd64(1234, buf, 1234, len)
#elif  __arm__
#define golfed_adler32(buf, len)   adler32arm_golf(buf, len)
#else
#error "no architecture"
#endif

static void test_adler(const char *str)
{
    unsigned len = strlen(str);
//    unsigned zlib = zlib_adler(len, str);
    unsigned reference = adler32_simple((const uint8_t*)str);
    unsigned golfed = golfed_adler32(str, len);

    printf("%s: c:%u asm:%u\n", str, reference, golfed);
    assert(reference == golfed);
}

// main() to call test_adler() unchanged from my amd64 answer, except that the comments about length limits don't apply
Peter Cordes
fonte
3

Função de código de máquina x86 de 16 bits: 32 bytes usando uma convenção de chamada personalizada

Args nos registros e não preservando os registros que não sejam bp (e sp).

No código de 16 bits, retornamos um valor de 32 bits no dx:axpar de registradores. Isso significa que não tem que gastar todas as instruções fusão highe lowemeax . (Isso economizaria bytes no código de 32 e 64 bits também, mas só podemos justificar a transferência desse trabalho para o chamador no código de 16 bits.)

Fonte comentada e driver de teste no github (para x86 16, 32 e 64 bits e ARM).

### const char *buf in SI,  uint16_t len in CX
## returns in dx:ax
## also clobbers bx and di.
00000100 <adler32_x16_v6>:
 100:   31 c0                   xor    ax,ax         # set up for lods
 102:   99                      cwd                  # dx= high=0
 103:   bf 01 00                mov    di,0x1        # di= low=0
 106:   bb f1 ff                mov    bx,0xfff1     # bx= m
00000109 <adler32_x16_v6.byteloop>:
 109:   ac                      lods
 10a:   01 c7                   add    di,ax         # low+=buf[i]. modulo-reduce on carry, or on low>=m
 10c:   72 04                   jc     112 <adler32_x16_v6.carry_low>
 10e:   39 df                   cmp    di,bx
 110:   72 02                   jb     114 <adler32_x16_v6.low_mod_m_done>
00000112 <adler32_x16_v6.carry_low>:
 112:   29 df                   sub    di,bx
00000114 <adler32_x16_v6.low_mod_m_done>:
 114:   01 fa                   add    dx,di         # high+=low
 116:   0f 92 d0                setb   al            # store the carry to set up a 32bit dividend.
 119:   92                      xchg   dx,ax
 11a:   f7 f3                   div    bx            # high (including carry) %= m, in dx.  ax=0 or 1 (so we're set for lods next iteration)                                                         
 11c:   e2 eb                   loop   109 <adler32_x16_v6.byteloop>
 11e:   97                      xchg   di,ax         # 
 11f:   c3                      ret    
00000120 <adler32_x16_v6_end>:

0x120 - 0x100 = 32 bytes

Testado montando o mesmo código para o modo de 32 bits, para que eu possa chamá-lo (com uma função de wrapper) de C compilado com -m32. Para mim, o modo 16 bits é um pouco interessante, as chamadas do sistema DOS não são. Todas as instruções têm operandos explícitos, exceto loope lodsb, portanto, a montagem no modo de 32 bits usa prefixos de tamanho de operando. Mesma instrução, codificação diferente. Mas lodsbno modo 32 bits usará[esi] , portanto, esta versão para teste funciona com ponteiros de 32 bits (porque não fazemos nenhum cálculo de endereço ou incremento / comparação de ponteiros).

Sem incompatibilidades. Meu equipamento de teste imprime uma mensagem se houver uma incompatibilidade.

$ yasm -felf32 -Worphan-labels -gdwarf2 adler32-x86-16.asm -o adler32-x86-16+32.o &&
   g++ -DTEST_16BIT -m32 -std=gnu++11 -O1 -g -Wall -Wextra -o test-adler32-x16  adler32-x86-16+32.o  test-adler32.cpp -lz &&
   ./test-adler32-x16
Eagles are great! (len=17): zlib:0x36c405fe  c:0x36c405fe golfed:0x36c405fe
Programming Puzzles & Code Golf (len=31): zlib:0xbac00b2a  c:0xbac00b2a golfed:0xbac00b2a
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=32): zlib:0x040f0fc1  c:0x040f0fc1 golfed:0x040f0fc1
?????????????????????????????????????????????????? (len=1040): zlib:0x82000000  c:0x82000000 golfed:0x82000000
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=4096): zlib:0xb169e06a  c:0xb169e06a golfed:0xb169e06a
(0xFF repeating) (len=4096): zlib:0x8161f0e2  c:0x8161f0e2 golfed:0x8161f0e2
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5837): zlib:0x5d2a398c  c:0x5d2a398c golfed:0x5d2a398c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=5838): zlib:0x97343a0a  c:0x97343a0a golfed:0x97343a0a
(0xFF repeating) (len=9999): zlib:0xcae9ea2c  c:0xcae9ea2c golfed:0xcae9ea2c
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~ (len=65535): zlib:0x33bc06e5  c:0x33bc06e5 golfed:0x33bc06e5

Com registros de 16 bits, não podemos adiar a redução do módulo até depois do loop. Há uma diferença interessante entre 16 bits e outros tamanhos de operando: m = 65521( 0xFFF1) é mais da metade 65536. Subtrair o mcarry mantém o valor abaixo de 2 * m, mesmo se high=0xFFF0 + 0xFFF0. Após o loop, uma comparação e subtração fará o truque, em vez de umdiv .

Eu inventei uma nova técnica para reduzir o módulo de um registro depois de um complemento que pode produzir uma carga . Em vez de zerar a metade superior da entrada div, use setc dlpara criar um dividendo de 32 bits com o resultado da adição não truncada ( dhjá está zerado). ( divfaz 32b / 16b => divisão de 16 bits.)

setcc(3 bytes) foi introduzido com 386. Para executar isso em 286 ou anterior, o melhor que eu criei usa a instrução não documentada salc(defina AL de carry) . É um código de operação de um byte para sbb al,al, portanto, poderíamos usar salc/ neg alantes de fazer o xchg ax, dx(que é necessário de qualquer maneira). Sem salc, há uma sequência 4B: sbb dx,dx/ neg dx. Não podemos usar 3B sbb dx,dx/ inc dx, porque isso simularia em setncvez de setc.


Tentei usar o tamanho do operando de 32 bits em vez de manipular o carry, mas não são apenas as addinstruções que precisam de um prefixo do tamanho do operando. As instruções para configurar as constantes e assim por diante também precisam de prefixos de tamanho de operando, por isso acabaram não sendo os menores.

Peter Cordes
fonte
2

Perl 5, 43 bytes

42 bytes, mais 1 para em -aEvez de-e

A entrada é como números inteiros decimais, separados por espaço.

map$h+=$.+=$_,@F;say$.%65521+$h%65521*4**8

Uma dica do meu chapéu para o Sp3000 , de quem tirei idéias para esta resposta.

Como funciona:

  1. Por causa disso -a, $. inicia em 1 e @Fé a matriz de entrada. $hcomeça em 0. $_é usado mapcomo um espaço reservado para cada elemento de uma matriz.
  2. map$h+=$.+=$_,@Fsignifica que para cada elemento em @Fque adicionamos esse elemento $.e, em seguida, adicionamos $.a $h.
  3. Em seguida, fazemos a aritmética modular $.%65521+$h%65521*4**8(isto é, ($. % 65521) + ( ($h % 65521) * (4**8) )e say(imprimimos)) o resultado.
msh210
fonte
1

Fator, 112 109 103 bytes

Agora , esta é uma tradução literal do algoritmo na pergunta ... agora que eu realmente fiz isso, você sabe, correto.

[ [ sum 1 + ] [ [ dup length [1,b] reverse v. ] [ length ] bi + ] bi [ 65521 mod ] bi@ 16 shift bitor ]

Ungolfed:

: adler-32 ( seq -- n )
  [ sum 1 + ] 
  [ 
    [ dup length [1,b] reverse v. ] 
    [ length ] bi + 
  ] bi 
  [ 65521 mod ] bi@ 
  16 shift bitor 
  ;

Espera qualquer sequência de números ou uma sequência (não há muita diferença, embora eles não sejam tecnicamente iguais).

Não sei como isso funcionará para o limite especificado em uma versão do Factor compilada com tamanho de palavra de 32 bits, mas na minha máquina de 6 GB e 64 bits e 2,2 GHz:

IN: scratchpad 1040 63 <array>

--- Data stack:
{ 63 63 63 63 63 63 63 63 63 63 63 63 63 63 ~1026 more~ }
IN: scratchpad [ adler-32 ] time
Running time: 7.326900000000001e-05 seconds

--- Data stack:
2181038080
IN: scratchpad 10,000 63 <array> 

--- Data stack:
2181038080
{ 63 63 63 63 63 63 63 63 63 63 63 63 63 63 ~9986 more~ }
IN: scratchpad [ adler-32 ] time
Running time: 0.000531669 seconds
gato
fonte
1

Ruby, 91 bytes

->s{b=s.bytes;z=i=b.size
b.inject(1,:+)%65521+b.map{|e|e*(1+i-=1)}.inject(z,:+)%65521*4**8}
Value Ink
fonte
1

Clojure, 109 bytes

Baseado na solução do @Mark Adler .

(fn f[s](->> s(reduce #(mapv + %(repeat %2)[0(first %)])[1 0])(map #(rem % 65521))(map *[1 65536])(apply +)))

Ungolfed

(fn f [s]
  (->> s
       (reduce #(mapv + % (repeat %2) [0 (first %)]) [1 0])
       (map #(rem % 65521))
       (map * [1 65536])
       (apply +)))

Uso

=> (def f (fn f[s](->> s(reduce #(mapv + %(repeat %2)[0(first %)])[1 0])(map #(rem % 65521))(map *[1 65536])(apply +))))
=> (f [69 97 103 108 101 115 32 97 114 101 32 103 114 101 97 116 33])
918816254
=> (f [80 114 111 103 114 97 109 109 105 110 103 32 80 117 122 122 108 101 115 32 38 32 67 111 100 101 32 71 111 108 102])
3133147946
=> (f (repeat 32 126))
68095937
=> (f (repeat 1040 63))
2181038080
=> (f (repeat 4096 255))
2170679522
milhas
fonte
1

Javascript (130 caracteres)

Ungolfed

function a(b)
{
    c=1
    for(i=0;i<b.length;i++)
    {
        c+=b[i]
    }
    d=c%65521
    f=""
    e=0
    k=""
    for(j=0;j<b.length;j++)
    {
        k+= "+"+b[j]
        f+= "(1"+k+")"
        e= ((eval(f)))
        if(j!=b.length-1){f+="+"}
    }
    g=e%65521
    h=d+65536*g
    console.log(h)
}

Golfe

a=b=>{for(c=1,k=f="",y=b.length,i=0;i<y;i++)c+=x=b[i],f+="(1"+(k+="+"+x)+")",i<y-1&&(f+="+");return z=65521,c%z+65536*(eval(f)%z)}

Cole no Developers Console e forneça uma matriz de bytes EG:

[69, 97, 103, 108, 101, 115, 32, 97, 114, 101, 32, 103, 114, 101, 97, 116, 33]

E retornará a soma de verificação ao console

Shubshub
fonte
1

TMP, 55 bytes

3a1.3b0.1;4+a>T8%a>xFFF14+b>a8%b>xFFF11~5<b>164|b>a2$b$

A implementação em Lua pode ser encontrada aqui: http://preview.ccode.gq/projects/TMP.lua

brianush1
fonte
1
Bem-vindo à Programação de Puzzles e Code Golf! Essa linguagem satisfaz nossa definição de linguagens de programação ?
cat
@cat Eu acredito que sim, mas não tenho certeza se ele realmente suporta "tuplas?"
Brianush1
O BrainFuck também não, então você provavelmente está bem. Se estiver completo, puder encontrar números primos e fazer as coisas básicas que qualquer outra linguagem pode fazer (e pode), funcionará :) CSS não é uma linguagem de programação por si só e nem é HTML, mas CSS3 + HTML está completo e pode encontrar números primos.
gato
Então, está tudo bem em usar no CodeGolf?
Brianush1
Eu acho que sim - eu não conheço nem TMP nem Lua; portanto, uma explicação desse código seria uma grande ajuda (e tornaria essa uma ótima resposta). : D
cat
1

Python 3.5, 82 bytes:

( -1 byte graças a Neil ! )

( -1 byte graças a mathmandan ! )

( -4 bytes graças a Dennis ! )

lambda w:((1+sum(w))%65521)+4**8*(sum(1+sum(w[:i+1])for i in range(len(w)))%65521)

Uma lambdafunção anônima . Aceita uma matriz de bytes, aplica todo o algoritmo à matriz e gera o resultado. Trabalhou com sucesso para todos os casos de teste. Você chama isso atribuindo uma variável a ela e, em seguida, chamando essa variável da mesma maneira que chamaria uma função normal. Se você estiver usando o shell, isso deve sair sem uma função de impressão. No entanto, se não estiver, você deve agrupar a chamada de função na print()função para realmente ver a saída.

Experimente online! (Ideona)

R. Kap
fonte
(E+15)é realmente um byte maior que 65536.
Neil
@ Neil Obrigado pela dica. Está consertado agora.
R. Kap
@ Sp3000 Então? Seria importante se eles adicionassem alguns bytes, mas o fato de eles não adicionarem bytes fica bem comigo.
R. Kap
4**8é um byte menor que 65536.
mathmandan
Você pode economizar 4 bytes, soltando os colchetes ao redor do gerador e iterando de 0 a len (w) . Outros 6 bytes podem ser salvos explorando a precedência do operador.
Dennis
1

Fissão , 324 bytes

          /   M
       R_MZ  |S
      D ]    |S
 /?V?\} {}/  |S /    \
R{/A  Z$[/   |S/     {\
  } J{\      |S      ;_
 \^  /       |S   R'~++Y++~'L
 /    /      |S       }Y;
 \  \        ;^/
 /  /         +\+ R'~++A++~'L
 \  <Z________________/
    ;\X       //
              \Y/
               *

Aviso justo, a única implementação em que eu testei isso é a minha própria porta da linguagem para o F #. Não é jogado golfe, principalmente porque achei mais fácil fazer algumas corridas longas enquanto minha constante principal esfriava no fundo, para que eu possa voltar e ajustá-lo.

Como funciona?

  • o R'~++Y++~'L bloco funde uma constante 256 e a lança para baixo, configurando o multiplicador de massa do reator diretamente abaixo dele.
  • O R'~++A++~'Abloco funde outros 256 e o ​​lança em direção ao reator acima, que divide a partícula em dois múltiplos de massa de65536 massa cada, lançando-os para a esquerda e para a direita (onde a partícula direita é imediatamente destruída pelo terminador).
  • A partícula esquerda atinge outro reator e sofre fissão, dividindo-se em duas partículas de massa igual subindo e descendo.
  • A potência de duas partículas que viaja para cima passa por uma manipulação de massa líquida de zero, reflete à esquerda e depois define o multiplicador de massa do reator de fusão. Este reator será como multiplicamos o bloco H.
  • A partícula descendente se reflete à esquerda e lança massa a longo prazo, atingindo finalmente uma massa de 65521 (nosso maior primo).
  • O espelho rotacional ( Z) no final da corrida faz com que a partícula duplique o prime, enviando um de volta para a direita, onde finalmente define a massa armazenada do reator de fissão (^ ). É assim que aplicaremos o operador de módulo ao bloco H.
  • A segunda cópia é refletida de volta, onde ela executa uma função análoga para o reator de fissão ( <) que usaremos para o bloco L.
  • Agora que nossas constantes estão no lugar, nos envolvemos em travessuras no canto superior esquerdo para ler nossa opinião e gerar nossas duas listas. Para ser sincero, esqueço como isso funciona, mas para a corda vazia eu tive que desacelerar a partição de soma do bloco H, o que explica a |S"torre de resfriamento".
  • \Y/ funde o bloco L (que entra pelo canal esquerdo) e o bloco H (que entra pelo canal direito) e os bate em um terminador que define o código de saída para a massa fundida.
Andrew Coonce
fonte
A menos que eu esteja cometendo um erro em algum lugar, isso não parece funcionar com o intérprete oficial ( link ). Onde eu poderia obter sua porta para F #?
Dennis
@ Dennis Estou tentando descobrir se o erro está do meu lado ou não, mas também não consigo fazer o intérprete funcionar. Vou ver se consigo fazê-lo funcionar e, se necessário, atualizo minha resposta.
Andrew Coonce
@ Dennis Parece que o intérprete online não lida com as interrupções do código de erro *, e é assim que estou retornando a saída. Vou ver se consigo encontrar outro intérprete para verificar a saída amanhã.
Andrew Coonce