funkcja kodu maszynowego x86-64, 30 bajtów.
Wykorzystuje tę samą logikę rekurencji jako C Odpowiedź @Level rzeki św . (Maksymalna głębokość rekurencji = 100)
Korzysta z puts(3)funkcji libc, z którą normalne pliki wykonywalne są powiązane. Można go wywoływać za pomocą ABI x86-64 System V, tj. Z C w systemie Linux lub OS X, i nie blokuje żadnych rejestrów, których nie powinien.
objdump -drwC -Mintel wyjście, skomentowane z wyjaśnieniem
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.
Zbudowany z yasm -felf64 -Worphan-labels -gdwarf2 golf-googol.asm &&
gcc -nostartfiles -o golf-googol golf-googol.o . Mogę opublikować oryginalne źródło NASM, ale wydawało się, że to bałagan, ponieważ instrukcje asm są tam w trakcie demontażu.
putchar@pltznajduje się w odległości mniejszej niż 128 bajtów jl, więc mógłbym użyć 2-bajtowego krótkiego skoku zamiast 6-bajtowego skoku w pobliżu, ale jest to prawdą tylko w małym pliku wykonywalnym, a nie jako część większego programu. Więc nie sądzę, żebym mógł usprawiedliwić nie liczenie wielkości implementacji put libc, jeśli skorzystam z krótkiego kodowania jcc, aby to osiągnąć.
Każdy poziom rekurencji wykorzystuje 24B przestrzeni stosu (2 wypychania i adres zwrotny wypychany przez CALL). Każda inna głębokość będzie putcharsprawdzać ze stosem wyrównanym tylko o 8, a nie o 16, więc to narusza ABI. Implementacja stdio, która używa wyrównanych sklepów do rozlewania rejestrów xmm na stos, byłaby błędna. Ale glibc's putchartego nie robi, pisząc do potoku z pełnym buforowaniem lub pisząc do terminala z buforowaniem linii. Testowane na Ubuntu 15.10. Można to naprawić za pomocą manekina push / pop w .loopcelu wyrównania stosu o kolejne 8 przed wywołaniem rekurencyjnym.
Dowód, że drukuje odpowiednią liczbę nowych linii:
# 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.
Moja pierwsza wersja to 43B i była używana puts() w buforze 9 nowych linii (i kończącym 0 bajtów), więc put wstawiałby 10. Ten podstawowy przypadek rekurencji był jeszcze bliższy inspiracji C.
Faktoring 10 ^ 100 w inny sposób mógł skrócić bufor, może nawet do 4 nowych linii, oszczędzając 5 bajtów, ale zdecydowanie lepiej jest użyć putchar. Potrzebuje tylko liczby całkowitej, a nie wskaźnika i bufora. Standard C pozwala na implementacje, dla których jest to makro putc(val, stdout), ale w glibc istnieje jako prawdziwa funkcja, którą można wywołać z asm.
Drukowanie tylko jednej nowej linii na połączenie zamiast 10 oznacza po prostu, że musimy zwiększyć maksymalną głębokość rekurencji o 1, aby uzyskać kolejny współczynnik 10 nowych linii. Ponieważ zarówno 99, jak i 100 mogą być reprezentowane przez 8-bitowy znak bezpośredni z rozszerzonym znakiem,push 100 nadal jest to tylko 2 bajty.
Co więcej, posiadanie 10w rejestrze działa zarówno jako licznik nowej linii, jak i licznik pętli, oszczędzając bajt.
Pomysły na oszczędzanie bajtów
Wersja 32-bitowa może zaoszczędzić bajt dla dec edi, ale konwencja wywoływania argumentów stosu (dla funkcji bibliotecznych takich jak putchar) sprawia, że wywołanie ogonowe jest trudniejsze i prawdopodobnie wymagałoby więcej bajtów w większej liczbie miejsc. Mógłbym użyć konwencji register-arg dla prywatnego f(), wywoływanego tylko przez g(), ale wtedy nie mogłem wywołać putchar tail-call (ponieważ f () i putchar () przyjmowałyby inną liczbę argumentów stosu).
Byłoby możliwe, aby f () zachowywał stan dzwoniącego, zamiast zapisywania / przywracania w dzwoniącym. Prawdopodobnie jest to do bani, ponieważ prawdopodobnie musiałoby się dostać osobno z każdej strony gałęzi i nie jest kompatybilne z ogłaszaniem. Próbowałem, ale nie znalazłem żadnych oszczędności.
Utrzymywanie licznika pętli na stosie (zamiast push / pop rcx w pętli) również nie pomogło. Było gorzej o 1B z wersją, która używa putów, i prawdopodobnie jeszcze większą stratę z tą wersją, która taniej konfiguruje rcx.
