Función de código de máquina x86-64, 30 bytes.
Utiliza la misma lógica de la recursividad como la respuesta C por @Level río St . (Profundidad máxima de recursión = 100)
Utiliza la puts(3)
función de libc, de la cual se ejecutan los ejecutables normales. Es invocable usando el x86-64 System V ABI, es decir, desde C en Linux u OS X, y no registra ningún registro que no debería.
objdump -drwC -Mintel
salida, comentada con explicación
0000000000400340 <g>: ## wrapper function
400340: 6a 64 push 0x64
400342: 5f pop rdi ; mov edi, 100 in 3 bytes instead of 5
; tailcall f by falling into it.
0000000000400343 <f>: ## the recursive function
400343: ff cf dec edi
400345: 97 xchg edi,eax
400346: 6a 0a push 0xa
400348: 5f pop rdi ; mov edi, 10
400349: 0f 8c d1 ff ff ff jl 400320 <putchar> # conditional tailcall
; if we don't tailcall, then eax=--n = arg for next recursion depth, and edi = 10 = '\n'
40034f: 89 f9 mov ecx,edi ; loop count = the ASCII code for newline; saves us one byte
0000000000400351 <f.loop>:
400351: 50 push rax ; save local state
400352: 51 push rcx
400353: 97 xchg edi,eax ; arg goes in rdi
400354: e8 ea ff ff ff call 400343 <f>
400359: 59 pop rcx ; and restore it after recursing
40035a: 58 pop rax
40035b: e2 f4 loop 400351 <f.loop>
40035d: c3 ret
# the function ends here
000000000040035e <_start>:
0x040035e - 0x0400340 = 30 bytes
# not counted: a caller that passes argc-1 to f() instead of calling g
000000000040035e <_start>:
40035e: 8b 3c 24 mov edi,DWORD PTR [rsp]
400361: ff cf dec edi
400363: e8 db ff ff ff call 400343 <f>
400368: e8 c3 ff ff ff call 400330 <exit@plt> # flush I/O buffers, which the _exit system call (eax=60) doesn't do.
Construido con yasm -felf64 -Worphan-labels -gdwarf2 golf-googol.asm &&
gcc -nostartfiles -o golf-googol golf-googol.o
. Puedo publicar la fuente NASM original, pero eso parecía desordenado ya que las instrucciones asm están ahí en el desmontaje.
putchar@plt
está a menos de 128 bytes de distancia jl
, por lo que podría haber usado un salto corto de 2 bytes en lugar de un salto cercano de 6 bytes, pero eso solo es cierto en un pequeño ejecutable, no como parte de un programa más grande. Así que no creo que pueda justificar no contar el tamaño de la implementación de put de libc si también aprovecho una breve codificación jcc para alcanzarla.
Cada nivel de recursión usa 24B de espacio de pila (2 empujes y la dirección de retorno empujada por CALL). Cualquier otra profundidad llamará putchar
con la pila solo alineada por 8, no por 16, por lo que esto viola el ABI. Fallaría una implementación estándar que usara tiendas alineadas para derramar registros xmm a la pila. Pero glibc putchar
no hace eso, escribir en una tubería con almacenamiento en búfer completo o escribir en una terminal con almacenamiento en línea. Probado en Ubuntu 15.10. Esto podría solucionarse con un push / pop ficticio en el .loop
, para compensar la pila por otros 8 antes de la llamada recursiva.
Prueba de que imprime el número correcto de líneas nuevas:
# with a version that uses argc-1 (i.e. the shell's $i) instead of a fixed 100
$ for i in {0..8}; do echo -n "$i: "; ./golf-googol $(seq $i) |wc -c; done
0: 1
1: 10
2: 100
3: 1000
4: 10000
5: 100000
6: 1000000
7: 10000000
8: 100000000
... output = 10^n newlines every time.
Mi primera versión de esto fue 43B, y usé puts()
en un búfer de 9 líneas nuevas (y un byte final de 0), por lo que put agregaría el 10. Ese caso base de recursión estaba aún más cerca de la inspiración C.
Factorizar 10 ^ 100 de una manera diferente podría haber acortado el búfer, tal vez hasta 4 líneas nuevas, ahorrando 5 bytes, pero usar putchar es mucho mejor. Solo necesita un argumento entero, no un puntero, y ningún búfer en absoluto. El estándar C permite implementaciones para las que es una macro putc(val, stdout)
, pero en glibc existe como una función real a la que puede llamar desde asm.
Imprimir solo una nueva línea por llamada en lugar de 10 solo significa que necesitamos aumentar la profundidad máxima de recursión en 1, para obtener otro factor de 10 nuevas líneas. Como 99 y 100 se pueden representar mediante un signo de 8 bits inmediato,push 100
todavía son solo 2 bytes.
Aún mejor, tener 10
un registro funciona como una nueva línea y un contador de bucle, guardando un byte.
Ideas para guardar bytes
Una versión de 32 bits podría guardar un byte para el dec edi
, pero la convención de llamadas stack-args (para funciones de biblioteca como putchar) hace que la llamada de cola funcione con menos facilidad y probablemente requerirá más bytes en más lugares. Podría usar una convención de registro-arg para el privado f()
, solo llamado por g()
, pero luego no pude llamar a putchar (porque f () y putchar () tomarían un número diferente de stack-args).
Sería posible tener f () preservar el estado de la persona que llama, en lugar de guardar / restaurar en la persona que llama. Sin embargo, eso probablemente apesta, porque probablemente necesitaría estar por separado en cada lado de la rama, y no es compatible con las llamadas de cola. Lo intenté pero no encontré ningún ahorro.
Mantener un contador de bucles en la pila (en lugar de presionar / reventar rcx en el bucle) tampoco ayudó. Era 1B peor con la versión que usaba put, y probablemente una pérdida aún mayor con esta versión que configura rcx de manera más económica.