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 código de golfe .
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
fonte
Respostas:
Geléia,
1917 bytesExperimente online!
fonte
⁹²¤
Mathematica, 46 bytes
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:
fonte
Julia,
7346 bytesEsta é 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) + 1
esum(cumsum(x) + 1)
em uma matriz, ondex
está 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!
fonte
função do código da máquina x86-64:
3332 bytes (ou3130 bytes com umaint[]
entrada em vez dechar[]
)função do código da máquina x86-32: 31 bytes
Como um fragmento de código inline-asm do GNU C: salva
2B1B (apenas oret
insn).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 => pop32
funciona 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) byteshigh = 0x3f040000, low = 0x7e001
,. Portantohigh
, o bit mais significativo ainda não está definido. Meu código aproveita isso, inscrever-estendendoeax
paraedx:eax
comcdq
como uma maneira de zeraredx
.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 usadoxchg 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
div
s. 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) .
Eu também considerei usar
rcx
como um índice de matriz, em vez de ter dois contadores de loop, mas adler32 (s)! = Adler32 (reverse (s)). Então não podíamos usarloop
. Contar de -len até zero e usarmovzx 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 baterxor 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
/ emedi
vez dersi
, então colocaríamos o ponteiro argrdi
).scas
Poré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[]
entradaA função completa
uint8_t[]
é a resposta "principal", porque é um desafio mais interessante. Descompactar paraint[]
é 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
lodsd
e substituaxor eax,eax / cdq
por justxor edx,edx
).Podemos salvar outro byte zerando edx com
lodsd
/cdq
e reorganizando o loop para que ele carregue o elemento 0 final antes de sair. (Ainda estamos assumindo que ela existe, mesmo que seja uma matrizint
, não uma sequência).Também fiz uma versão não testada que usa
scasd
(versão 1B deadd edi,4
) e emadd eax, [rdi]
vez delodsd
, mas também tem 30 bytes. As economias de terhigh
no eax no final do loop são compensadas por códigos maiores em outros lugares.0
Poré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.
fonte
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 oadler32(int[])
problema, mas sinto que oadler32(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 usarALIGN 16
). Acho que vou continuar jogando golfe.do{}while(--len)
estilo de loop em vez de awhile(len--){}
.MATL , 22 bytes
A entrada pode ser uma matriz de números ou a sequência ASCII correspondente.
Experimente online!
Explicação
fonte
Na verdade, 36 bytes
Experimente online!
Explicação:
fonte
Java, 84 bytes
Se as soluções Java sempre devem ser um código compilável completo, entre em contato.
Ungolfed
Nota
Você precisará converter a entrada
String
paraint[]
(int[]
é um byte menor quebyte[]
ouchar[]
).Saída
fonte
Piet, 120 Codels
Com 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 um1
(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
pointer
ouswitch
operaçõ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
BigInteger
como valores internos)Só vi que a configuração inclui um desnecessário
DUP
eCC
(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:
Terminação, saída e saída do loop:
Saídas
Perdoe-me se eu incluir apenas uma saída, leva muito tempo para inserir: ^)
Rastreio de Npiet para [65, -1]
fonte
C89, 70 bytes
Para testar (compilar com
gcc -std=c89 -lm golf.c
):fonte
zlib
fonte se parece? Hm ...for
vez dewhile
:for(h=0,l=1;*B;)h+=l+=*B++;
Labirinto ,
37363231 bytesExperimente 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:
_
.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:
Agora, temos todas as somas de prefixo na pilha auxiliar , bem como uma cópia da soma de todos os valores e
0
do EOF no principal . Com isso, inserimos outro loop 2x2 (sentido horário) que soma todos os prefixos a serem computadosHIGH
.A pilha principal agora tem
LOW - 1
eHIGH
e zero, exceto que ainda não tomamos o módulo. O restante do código é completamente linear: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. O36
agora transforma o topo do main em63
, 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.
fonte
Python 2,
6058 bytesUma 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)
fonte
H=h=65521
para inicializarh
enquanto aliasing 65521.J, 30 bytes
Provavelmente isso poderia ser mais condensado com um trem diferente.
Uso
Aqui
x $ y
cria uma lista comx
cópias dey
.Explicação
fonte
Oitava,
5250 bytesGuardado 2 bytes graças a @LuisMendo
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 .
fonte
+B
. Eu acho que a especificação de entrada diz que você pode pegar números inteiros, então talvez eu faça isso.CJam,
3029 bytesInsira como uma lista de números inteiros.
Teste aqui.
Explicação
fonte
Perl 6 , 60 bytes
Explicação:
Teste:
fonte
Python 3 (79 bytes)
Baseado na solução de R. Kap.
Substituí a multiplicação por um turno e tirei um par de colchetes.
Como não posso postar comentários, fiz uma nova resposta.
fonte
Esquema, 195 bytes
Se não fosse por todos esses parênteses ...
fonte
Haskell,
5450 bytesExemplo de uso:
g [69,97,103,108,101,115,32,97,114,101,32,103,114,101,97,116,33]
->918816254
.scanl
inclui o valor inicial (->1
) na lista (->[1,1+b1,1+b1+b2,..]
), de modo quesum
é desativado por1
, que é fixado anexando-1
a lista antes da soma.Edit: Obrigado @xnor por 4 bytes.
fonte
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.JavaScript (ES7),
5250 bytesO ES6 ocupa 51 bytes (substitua 4 ** 8 por 65536). Se você deseja uma versão de string, então, para 69 bytes:
Editar: salvou 2 bytes graças a @ user81655.
fonte
Função ARM Thumb-2 que aceita
uint8_t[]
: 40 bytes (36B para ABI não padrão eint[]
)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:
uint32_t[]
matriz.Então, o melhor caso é 36B.
0x28 = 40 bytes
Notas:
Em vez de
log%m
no final, fazemosif(low>=m) low-=m
dentro do loop. Se fizermos baixo antes do alto, sabemos que nenhum deles pode exceder2*m
; portanto, o módulo é apenas uma questão de subtrair ou não. Acmp
e predicadosub
são apenas 6B no modo Thumb2. O idioma padrão para%
é 8B no modo Thumb2:A
adler(char *)
versão de comprimento implícito é do mesmo tamanho de código que o comprimento explícitoadler(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:
ou
Sem
-static
, o processo em execuçãoqemu-arm
nã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, instalargcc-arm-linux-gnueabi
,g++-arm-linux-gnueabi
. Eu acheigdb-arm-none-eabi
meio que mal trabalhado conectandoqemu-arm -g port
.Fonte comentada:
test-adler32.cpp
tem os mesmos casos de teste emain()
quanto à minha resposta x86-64, mas começa assim:fonte
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:ax
par de registradores. Isso significa que não tem que gastar todas as instruções fusãohigh
elow
emeax
. (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).
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, excetoloop
elodsb
, portanto, a montagem no modo de 32 bits usa prefixos de tamanho de operando. Mesma instrução, codificação diferente. Maslodsb
no 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.
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 om
carry mantém o valor abaixo de 2 * m, mesmo sehigh=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
, usesetc dl
para criar um dividendo de 32 bits com o resultado da adição não truncada (dh
já está zerado). (div
faz 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 documentadasalc
(defina AL de carry) . É um código de operação de um byte parasbb al,al
, portanto, poderíamos usarsalc
/neg al
antes de fazer oxchg ax, dx
(que é necessário de qualquer maneira). Semsalc
, há uma sequência 4B:sbb dx,dx
/neg dx
. Não podemos usar 3Bsbb dx,dx
/inc dx
, porque isso simularia emsetnc
vez desetc
.Tentei usar o tamanho do operando de 32 bits em vez de manipular o carry, mas não são apenas as
add
instruçõ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.fonte
Pitão,
252423 bytes1 byte graças a @Jakube .
Mais 1 byte graças a @Jakube .
Experimente online!
Tradução da minha resposta em geléia .
fonte
Perl 5, 43 bytes
42 bytes, mais 1 para em
-aE
vez de-e
A entrada é como números inteiros decimais, separados por espaço.
Uma dica do meu chapéu para o Sp3000 , de quem tirei idéias para esta resposta.
Como funciona:
-a
,$.
inicia em 1 e@F
é a matriz de entrada.$h
começa em 0.$_
é usadomap
como um espaço reservado para cada elemento de uma matriz.map$h+=$.+=$_,@F
significa que para cada elemento em@F
que adicionamos esse elemento$.
e, em seguida, adicionamos$.
a$h
.$.%65521+$h%65521*4**8
(isto é,($. % 65521) + ( ($h % 65521) * (4**8) )
esay
(imprimimos)) o resultado.fonte
Fator,
112109103 bytesAgora , esta é uma tradução literal do algoritmo na pergunta ... agora que eu realmente fiz isso, você sabe, correto.
Ungolfed:
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:
fonte
Ruby, 91 bytes
fonte
Clojure, 109 bytes
Baseado na solução do @Mark Adler .
Ungolfed
Uso
fonte
Javascript (130 caracteres)
Ungolfed
Golfe
Cole no Developers Console e forneça uma matriz de bytes EG:
E retornará a soma de verificação ao console
fonte
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
fonte
Python 3.5, 82 bytes:
( -1 byte graças a Neil ! )
( -1 byte graças a mathmandan ! )
( -4 bytes graças a Dennis ! )
Uma
lambda
funçã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 naprint()
função para realmente ver a saída.Experimente online! (Ideona)
fonte
(E+15)
é realmente um byte maior que65536
.4**8
é um byte menor que65536
.Fissão , 324 bytes
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?
R'~++Y++~'L
bloco funde uma constante 256 e a lança para baixo, configurando o multiplicador de massa do reator diretamente abaixo dele.R'~++A++~'A
bloco 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).65521
(nosso maior primo).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.<
) que usaremos para o bloco L.|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.fonte
*
, e é assim que estou retornando a saída. Vou ver se consigo encontrar outro intérprete para verificar a saída amanhã.