Fondo
Adler-32 es una suma de verificación de 32 bits inventada por Mark Adler en 1995 que forma parte de la biblioteca zlib ampliamente utilizada (también desarrollada por Adler). Adler-32 no es tan confiable como una verificación de redundancia cíclica de 32 bits , pero, al menos en software, es mucho más rápido y fácil de implementar.
Definición
Sea B = [b 1 , ⋯, b n ] una matriz de bytes.
La suma de comprobación Adler-32 de B se define como el resultado de bajo + 65536 × alto , donde:
bajo: = ((1 + b 1 + ⋯ + b n ) mod 65521)
alto: = (((1 + b 1 ) + (1 + b 1 + b 2 ) + ⋯ (1 + b 1 + ⋯ + b n )) mod 65521)
Tarea
Dada una matriz de bytes como entrada, calcule y devuelva su suma de comprobación Adler-32, respetando lo siguiente.
Puede tomar la entrada como una matriz de bytes o enteros, o como una cadena.
En ambos casos, solo los bytes correspondientes a caracteres ASCII imprimibles aparecerán en la entrada.
Puede suponer que la longitud de la entrada satisfará 0 <longitud ≤ 4096 .
Si elige imprimir la salida, puede usar cualquier base positiva hasta 256 inclusive.
Si elige unario, asegúrese de que el intérprete pueda manejar hasta 2 32 - 983056 bytes de salida en una máquina con 16 GiB de RAM.
Las incorporaciones que calculan la suma de comprobación Adler-32 están prohibidas.
Aplican reglas estándar de código de golf .
Casos de prueba
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
fuente
Respuestas:
Jalea,
1917 bytesPruébalo en línea!
fuente
⁹²¤
Mathematica, 46 bytes
Una función anónima que toma una matriz entera y devuelve el Adler-32, con algunas mejoras de miles y Martin (ver comentarios).
millas 'también es de 46 bytes , pero más rápido:
fuente
Julia,
7346 bytesEsta es una función anónima que acepta una matriz y devuelve un entero. Para llamarlo, asígnelo a una variable.
Combinamos
sum(x) + 1
y formamossum(cumsum(x) + 1)
una matriz, dondex
está la matriz de entrada, y tomamos cada módulo 65521. Luego calculamos el producto punto con 1 y 4 8 , lo que nos da(sum(x) + 1) + 4^8 * sum(cumsum(x) + 1)
, que es exactamente la fórmula Adler-32.Pruébalo en línea! (Incluye todos los casos de prueba)
¡Ahorró 27 bytes gracias a Sp3000 y Dennis!
fuente
Función de código de máquina x86-64:
3332 bytes (o3130 bytes con unaint[]
entrada en lugar dechar[]
)Función de código de máquina x86-32: 31 bytes
Como un fragmento de código GNU C en línea-asm: guarda
2B1B (solo elret
insn).Fuente comentada y controlador de prueba en github
La versión de 64 bits se puede llamar directamente desde C con el sistema estándar V x86-64 ABI (usando 2 args ficticios para obtener args en las reglas que quiero). Las convenciones de llamadas personalizadas no son infrecuentes para el código asm, por lo que esta es una característica adicional.
El código de máquina de 32 bits ahorra 1B, porque la fusión de las mitades altas y bajas
push16/push16 => pop32
solo funciona en modo de 32 bits. Una función de 32 bits necesitaría una convención de llamada personalizada. No deberíamos sostener eso en su contra, pero llamar desde C necesita una función de contenedor.Después de procesar 4096
~
(ASCII 126) bytes,high = 0x3f040000, low = 0x7e001
. Entonceshigh
, el bit más significativo aún no está establecido. Mi código se aprovecha de esto, firmando extendiéndoseeax
aedx:eax
lacdq
como una forma de reducir a ceroedx
.0x40 - 0x20
= 32 bytes.Fuente comentada de NASM:
trucos:
xchg eax, r32
es un byte; más barato que mov. 8086 necesitaba datos en el hacha para muchas más cosas que> = 386, por lo que decidieron gastar mucho espacio de código de operación en el ahora raramente utilizadoxchg ax, r16
.La combinación de push64 y push16 para fusionar alto y bajo en un solo registro guarda las instrucciones de movimiento de datos de registro en dos
div
segundos. La versión de 32 bits de este truco funciona aún mejor:push16 / push16 / pop32
es solo 5B en total, no 6.Como presionamos / pop, esto no es seguro para asm en línea en el SysV amd64 ABI (con una zona roja) .
También consideré usar
rcx
como un índice de matriz, en lugar de tener dos contadores de bucle, pero adler32 (s)! = Adler32 (reverse (s)). Entonces no pudimos usarloop
. Contar desde -len hasta cero y usarmovzx r32, [rsi+rcx]
solo usa demasiados bytes.Si queremos considerar incrementar el puntero nosotros mismos, el código de 32 bits es probablemente el camino a seguir. Incluso el x32 ABI (punteros de 32 bits) no es suficiente, porque
inc esi
es 2B en amd64, pero 1B en i386. Parece difícil superarxor eax,eax
/lodsb
/loop
: 4B en total para que cada elemento a su vez se extienda a cero en eax.inc esi
/ /movzx r32, byte [esi]
/loop
es 5B.scas
es otra opción para incrementar un puntero con una instrucción 1B en modo de 64 bits. (rdi
/ enedi
lugar dersi
, entonces tomaríamos el puntero argrdi
). Sinscas
embargo, no podemos usar el resultado del indicador como condición de bucle, porque no queremos mantener eax a cero. Una asignación de registro diferente podría salvar un byte después del ciclo.int[]
entradaLa toma de función completa
uint8_t[]
es la respuesta "principal", porque es un desafío más interesante. Desembalarint[]
es una cosa irracional pedirle a nuestra persona que llama que haga en este idioma, pero ahorra 2B.Si tomamos nuestra entrada como una matriz desempaquetada de enteros de 32 bits, podemos guardar un byte fácilmente (usar
lodsd
y reemplazarxor eax,eax / cdq
con soloxor edx,edx
).Podemos guardar otro byte poniendo a cero edx con
lodsd
/cdq
, y reorganizando el ciclo para que cargue el elemento de terminación 0 antes de salir. (Todavía estamos asumiendo que existe, a pesar de que es una matriz deint
, no una cadena)También hice una versión no probada que usa
scasd
(versión 1B deadd edi,4
) y enadd eax, [rdi]
lugar delodsd
, pero también es de 30 bytes. Los ahorros de tener unhigh
eax al final del ciclo se compensan con un código más grande en otro lugar. Sin0
embargo, tiene la ventaja de no depender de un elemento de terminación en la entrada, lo que quizás no sea razonable para una matriz desempaquetada donde también se nos da la longitud explícitamente.Controlador de prueba C ++ 11
Ver el enlace de github. Esta respuesta se estaba volviendo demasiado grande, y el controlador de prueba obtuvo más funciones con un código más grande.
fuente
int[]
si fuera necesario, o guardar más de 4 bytes de código o algo así. No tengo ningún problema para presentar una solución aladler32(int[])
problema, pero siento que eladler32(char[])
problema es más interesante, ya que es la verdadera función adler32. Es lo que realmente quiero jugar al golf en asm. (Y me encantaría guardar un byte más de alguna manera, ya que en la vida real asm, 33 bytes = 48 bytes si se usa la siguiente funciónALIGN 16
). Supongo que seguiré jugando golf ambos.do{}while(--len)
estilo de bucle en lugar de awhile(len--){}
.MATL , 22 bytes
La entrada puede ser una matriz de números o la cadena ASCII correspondiente.
Pruébalo en línea!
Explicación
fuente
En realidad, 36 bytes
Pruébalo en línea!
Explicación:
fuente
Java, 84 bytes
Si se supone que las soluciones Java siempre son un código compilable completo, avíseme.
Sin golf
Nota
Tendrá que convertir la entrada
String
aint[]
(int[]
es un byte más corto quebyte[]
ochar[]
).Salida
fuente
Piet, 120 codeles
Con codelsize 20:
Notas / ¿Cómo funciona?
Como no es posible usar una matriz o cadena como entrada, este programa funciona tomando una serie de enteros (que representan caracteres ascii) como entradas. Al principio pensé en usar entradas de caracteres, pero tuve problemas para encontrar una buena solución para la terminación, por lo que ahora termina cuando se ingresa cualquier número menor que 1. Originalmente, solo eran valores negativos para la terminación, pero tuve que cambiar la inicialización después de escribir el programa, por lo que ahora no puedo ajustar lo requerido
2
, solo un1
(26/45 en la imagen de seguimiento). Sin embargo, esto no importa porque, según las reglas de desafío, solo se permiten caracteres ascii imprimibles.Luché durante mucho tiempo con la reentrada del bucle, aunque al final encontré una solución bastante elegante. No
pointer
oswitch
operaciones, solo el intérprete choca con las paredes hasta que vuelve a la transición al códec verde para leer la entrada (43-> 44 en las imágenes de seguimiento).La terminación del bucle se logra duplicando primero la entrada, agregando 1 y luego verificando si es mayor que 1. Si es así, se activa el selector de códeles y la ejecución continúa en la ruta inferior. Si no es así, el programa continúa a la izquierda (Codeles amarillos brillantes, 31/50 en las imágenes de rastreo).
El tamaño de entrada admitido depende de la implementación del intérprete, aunque sería posible admitir una entrada arbitrariamente grande con el intérprete correcto (por ejemplo, un intérprete de Java que utiliza
BigInteger
como valores internos)Acabo de ver que la configuración incluye una innecesaria
DUP
yCC
(7-> 8-> 9 en las imágenes de seguimiento). No tengo idea de cómo sucedió eso. Sin embargo, esto es efectivamente un noop, alterna el selector de codeles 16 veces, lo que no produce ningún cambio.Npiet traza imágenes
Configuración y primer bucle:
Terminación de bucle, salida y salida:
Salidas
Perdóname si solo incluyo una salida, solo toma mucho tiempo ingresar: ^)
Npiet traza para [65, -1]
fuente
C89, 70 bytes
Para probar (compilar con
gcc -std=c89 -lm golf.c
):fuente
zlib
ve la fuente? Hm ...for
lugar dewhile
:for(h=0,l=1;*B;)h+=l+=*B++;
Laberinto ,
37363231 bytesPruébalo en línea!
Entrada como una lista de enteros. El programa termina con un error (cuyo mensaje de error va a STDERR).
Explicación
Imprimación de laberinto:
_
.Aunque el código comienza con una "habitación" de 4x2, en realidad son dos bucles separados de dos por dos juntos. La IP simplemente se adhiere a un bucle a la vez debido a los valores de la pila.
Entonces, el código comienza con un bucle 2x2 (en sentido horario) que lee la entrada mientras calcula sumas de prefijos:
Ahora tenemos todas las sumas de prefijos en la pila auxiliar , así como una copia de la suma de todos los valores y
0
de EOF en main . Con eso, ingresamos otro bucle 2x2 (en el sentido de las agujas del reloj) que suma todas las sumas de prefijos para calcularHIGH
.La chimenea principal tiene ahora
LOW - 1
yHIGH
y cero, excepto que no hemos tomado el módulo todavía. El resto del código es completamente lineal:La IP ahora llega a un callejón sin salida y se da vuelta. Los
+
y*
son esencialmente no-ops, debido a los ceros en la parte inferior de la pila. El36
ahora convierte la parte superior de main en63
, pero los dos{{
extraen dos ceros de aux en la parte superior. Luego%
intenta dividir por cero, lo que termina el programa.Tenga en cuenta que Labyrinth usa enteros de precisión arbitraria, por lo que diferir el módulo hasta el final de la suma no causará problemas con el desbordamiento de enteros.
fuente
Python 2,
6058 bytesUn enfoque bastante sencillo. Este es un programa completo que toma una lista de enteros a través de STDIN, por ejemplo
[72, 105, 33]
.(Gracias a @xnor por la increíble sugerencia de alias / inicialización)
fuente
H=h=65521
para inicializarh
mientras alias 65521.J, 30 bytes
Esto probablemente podría condensarse más con un tren diferente.
Uso
Aquí
x $ y
crea una lista conx
copias dey
.Explicación
fuente
Octava,
5250 bytesGuardado 2 bytes gracias a @LuisMendo
Toma una matriz de enteros como entrada.
low se toma del último elemento de high (antes de sumar) en lugar de calcular la suma explícitamente, ahorrando un gran total de ... 1 byte !
Ejecución de muestra en ideone .
fuente
+B
. Supongo que la especificación de entrada dice que puedes tomar enteros, así que tal vez lo haga.CJam,
3029 bytesEntrada como una lista de enteros.
Pruébalo aquí.
Explicación
fuente
Perl 6 , 60 bytes
Explicación:
Prueba:
fuente
Python 3 (79 bytes)
Basado en la solución de R. Kap.
Reemplacé la multiplicación por un turno y eliminé un par de paréntesis.
Como no puedo publicar comentarios, hice una nueva respuesta.
fuente
Esquema, 195 bytes
Si no fuera por todos esos paréntesis ...
fuente
Haskell,
5450 bytesEjemplo de uso:
g [69,97,103,108,101,115,32,97,114,101,32,103,114,101,97,116,33]
->918816254
.scanl
incluye el valor inicial (->1
) en la lista (->[1,1+b1,1+b1+b2,..]
), por lo quesum
está desactivado por1
, que se corrige al anteponer-1
a la lista antes de sumar.Editar: Gracias @xnor por 4 bytes.
fuente
m
:m=(`mod`65521).sum g x=m(-1:scanl(+)1x)*4^8+m(1:x)
. Probablemente haya una mejor manera de arreglar las sumas que anteponer.JavaScript (ES7),
5250 bytesES6 toma 51 bytes (reemplace 4 ** 8 con 65536). Si desea una versión de cadena, para 69 bytes:
Editar: Guardado 2 bytes gracias a @ user81655.
fuente
Función ARM Thumb-2 que acepta
uint8_t[]
: 40 bytes (36B para ABI no estándar yint[]
)Características: módulo no diferido, por lo que las entradas de tamaño arbitrario están bien. En realidad no usa la instrucción de división, por lo que no es lenta. (err, al menos no por esa razón: P)
Ahorro por seguir reglas menos estrictas:
uint32_t[]
matriz.Entonces, el mejor caso es 36B.
0x28 = 40 bytes
Notas:
En lugar de
log%m
al final, lo hacemosif(low>=m) low-=m
dentro del bucle. Si lo hacemos bajo antes que alto, sabemos que ninguno de los dos puede exceder2*m
, por lo que el módulo es solo cuestión de restar o no. Acmp
y predicadosub
es solo 6B en modo Thumb2. El idioma estándar para%
es 8B en modo Thumb2:La longitud implícita
adler(char *)
versión de tiene el mismo tamaño de código que la longitud explícitaadler(uint8_t[], uint32_t len)
. Podemos establecer banderas para la condición de salida de bucle con una sola instrucción 2B de cualquier manera.La versión de longitud implícita tiene la ventaja de funcionar correctamente con la cadena vacía, en lugar de intentar repetir 2 ^ 32 veces.
ensamblar / compilar con:
o
Sin
-static
, el proceso que se ejecuta bajoqemu-arm
no encontró su vinculador dinámico. (Y sí, instalo un ARM configuración cruz-devel sólo por esta respuesta, porque pensé que mi idea predicado-restar estaba ordenada.) En AMD64 Ubuntu, instalargcc-arm-linux-gnueabi
,g++-arm-linux-gnueabi
. encontrégdb-arm-none-eabi
casi no funcionaba la conexiónqemu-arm -g port
.Fuente comentada:
test-adler32.cpp
tiene los mismos casos de prueba ymain()
mi respuesta x86-64, pero comienza de esta manera:fuente
Función de código de máquina x86 de 16 bits: 32 bytes usando una convención de llamada personalizada
Args en registros, y no preservar otros registros que no sean bp (y sp).
En el código de 16 bits, devolvemos un valor de 32 bits en el
dx:ax
par de registros. Esto significa que no tienen que pasar todas las instrucciones fusiónhigh
ylow
eneax
. (Esto también ahorraría bytes en código de 32 y 64 bits, pero solo podemos justificar la descarga de este trabajo a la persona que llama en código de 16 bits).Fuente comentada y controlador de prueba en github (para x86 16, 32 y 64 bits, y ARM).
0x120 - 0x100 = 32 bytes
Probado al ensamblar el mismo código para el modo de 32 bits, por lo que puedo llamarlo (con una función de contenedor) desde C compilado con
-m32
. Para mí, el modo de 16 bits es algo interesante, las llamadas al sistema DOS no lo son. Todas las instrucciones tienen operandos explícitos, exceptoloop
ylodsb
, por lo que el ensamblaje para el modo de 32 bits utiliza prefijos de tamaño de operando. La misma instrucción, codificación diferente. Perolodsb
en modo de 32 bits usará[esi]
, por lo que esta versión para prueba funciona con punteros de 32 bits (porque no hacemos ningún cálculo de dirección o incremento / comparación de puntero).No hay desajustes. Mi arnés de prueba imprime un mensaje si hay una falta de coincidencia.
Con registros de 16 bits, no podemos diferir la reducción del módulo hasta después del ciclo. Hay una diferencia interesante entre 16 bits y otros tamaños de operandos:
m = 65521
(0xFFF1
) es más de la mitad de 65536. Restarm
en acarreo mantiene el valor por debajo de 2 * m, incluso sihigh=0xFFF0 + 0xFFF0
. Después del ciclo, una comparación y resta hará el truco, en lugar de undiv
.Se me ocurrió una nueva técnica para reducir el módulo de un registro después de un anuncio que puede producir un carry . En lugar de poner a cero la mitad superior de la entrada
div
, usesetc dl
para crear un dividendo de 32 bits que contenga el resultado de la suma no truncado (dh
ya está puesto a cero). (div
hace 32b / 16b => división de 16 bits).setcc
(3 bytes) se introdujo con 386. Para ejecutar esto en 286 o anterior, lo mejor que se me ocurre utiliza la instrucción no documentadasalc
(establecer AL desde carry) . Es un código de operación de un bytesbb al,al
, por lo que podríamos usarsalc
/neg al
antes de hacer elxchg ax, dx
(que de todos modos necesitamos). Sinsalc
, hay una secuencia 4B:sbb dx,dx
/neg dx
. No podemos usar 3Bsbb dx,dx
/inc dx
, porque eso emularía ensetnc
lugar de hacerlosetc
.Intenté usar un tamaño de operando de 32 bits en lugar de manejar carry, pero no son solo las
add
instrucciones las que necesitan un prefijo de tamaño de operando. Las instrucciones que configuran las constantes, etc., también necesitan prefijos de tamaño de operando, por lo que no fue el más pequeño.fuente
Pyth,
252423 bytes1 byte gracias a @Jakube .
1 byte más gracias a @Jakube .
Pruébalo en línea!
Traducción de mi respuesta en gelatina .
fuente
Perl 5, 43 bytes
42 bytes, más 1 para
-aE
lugar de-e
La entrada es como enteros decimales, separados por espacios.
Una punta de mi sombrero para Sp3000 , de quien tomé ideas para esta respuesta.
Cómo funciona:
-a
,$.
comienza en 1 y@F
es la matriz de entrada.$h
comienza en 0.$_
es utilizado pormap
como un marcador de posición para cada elemento de una matriz.map$h+=$.+=$_,@F
significa que para cada elemento en@F
que agregamos ese elemento$.
y luego agregamos$.
a$h
.$.%65521+$h%65521*4**8
(es decir,($. % 65521) + ( ($h % 65521) * (4**8) )
ysay
(imprimimos) el resultado.fuente
Factor,
112109103 bytesAhora , esta es una traducción literal del algoritmo en la pregunta ... ahora que realmente lo hice, ya sabes, correcto.
Sin golf:
Espera cualquier secuencia de números o una cadena (no hay mucha diferencia, aunque técnicamente no son lo mismo).
No sé cómo funcionará esto para el límite dado en una versión de Factor compilada con un tamaño de palabra de 32 bits, pero en mi máquina de 6 GB y 64 bits a 2.2 GHz:
fuente
Ruby, 91 bytes
fuente
Clojure, 109 bytes
Basado en la solución de @Mark Adler .
Sin golf
Uso
fuente
Javascript (130 caracteres golfizados)
Sin golf
Golfed
Pegue en la consola de desarrolladores y luego dele una matriz de bytes EG:
Y devolverá la suma de comprobación a la consola
fuente
TMP, 55 bytes
3a1.3b0.1;4+a>T8%a>xFFF14+b>a8%b>xFFF11~5<b>164|b>a2$b$
La implementación en Lua se puede encontrar aquí: http://preview.ccode.gq/projects/TMP.lua
fuente
Python 3.5, 82 bytes:
( -1 byte gracias a Neil ! )
( -1 byte gracias a Mathmandan ! )
( -4 bytes gracias a Dennis ! )
Una
lambda
función anónima . Acepta una matriz de bytes, aplica todo el algoritmo a la matriz y genera el resultado. Ha trabajado con éxito para todos los casos de prueba. Llama a esto asignándole una variable y luego llamando a esa variable como llamaría a una función normal. Si está utilizando el shell, esto debería salir sin una función de impresión. Sin embargo, si no lo está, debe ajustar la llamada a laprint()
función en la función para ver realmente la salida.Pruébalo en línea! (Ideone)
fuente
(E+15)
es en realidad un byte más largo que65536
.4**8
es un byte más corto que65536
.Fisión , 324 bytes
Advertencia justa, la única implementación en la que he probado esto es mi propio puerto del lenguaje a F #. No es golf, principalmente porque me pareció más fácil tener un par de carreras largas mientras mi constante principal se enfriaba en la parte inferior, por lo que puedo volver y ajustarla.
¿Como funciona?
R'~++Y++~'L
bloque fusiona una constante de 256 y lo lanza hacia abajo, configurando el multiplicador de masa del reactor directamente debajo de él.R'~++A++~'A
bloque fusiona otros 256 y lo lanza hacia el reactor de arriba, que fisiona la partícula en dos múltiplos de masa de65536
masa cada uno, lanzándolos hacia la izquierda y hacia la derecha (donde la partícula derecha es destruida inmediatamente por el terminador).65521
(nuestro gran cebado).Z
) al final de la ejecución hace que la partícula duplique el cebado, enviando uno de vuelta a la derecha donde finalmente establece la masa almacenada del reactor de fisión (^
). Así es como aplicaremos el operador de módulo al bloque H.<
) que usaremos para el bloque L.|S
"torre de enfriamiento".\Y/
fusiona el bloque L (que entra por el canal izquierdo) y el bloque H (que entra por el canal derecho), luego los golpea en un terminador que establece el código de salida en la masa fusionada.fuente
*
, que es como estoy devolviendo la salida. Veré si puedo encontrar otro intérprete para verificar la salida mañana.