Wprowadzenie

Jesteś prawdopodobnie zna bomby zip , bomb XML itp Mówiąc prościej, są (względnie) to małe pliki, które produkują ogromne wyjście kiedy interpretowane przez naiwnego oprogramowania. Wyzwaniem jest nadużycie kompilatora w ten sam sposób.

Wyzwanie

Napisz kod źródłowy, który zajmuje 512 bajtów lub mniej i który kompiluje się w plik, który zajmuje najwięcej możliwej przestrzeni. Największy plik wyjściowy wygrywa!

Zasady

OK, więc jest kilka ważnych wyjaśnień, definicji i ograniczeń;

• Dane wyjściowe kompilacji muszą być plikiem ELF , przenośnym plikiem wykonywalnym systemu Windows (.exe) lub wirtualnym kodem bajtowym dla JVM lub CLR .Net (inne typy wirtualnego kodu bajtowego również prawdopodobnie będą OK, jeśli zostaną o to poproszone). Aktualizacja: Dane wyjściowe .pyc / .pyo Pythona również się liczą .
• Jeśli wybranego języka nie można skompilować bezpośrednio w jednym z tych formatów, dozwolona jest również transpilacja, a następnie kompilacja ( Aktualizacja: możesz transpilować wiele razy, o ile nigdy nie używasz tego samego języka więcej niż jeden raz ).
• Kod źródłowy może składać się z wielu plików, a nawet plików zasobów, ale suma wszystkich tych plików nie może przekraczać 512 bajtów.
• Nie można używać innych danych wejściowych niż pliki źródłowe i standardowa biblioteka wybranego języka. Łączenie statyczne bibliotek standardowych jest OK, jeśli jest obsługiwane. W szczególności nie ma bibliotek stron trzecich ani bibliotek systemu operacyjnego.
• Musi istnieć możliwość wywołania kompilacji za pomocą polecenia lub szeregu poleceń. Jeśli potrzebujesz specyficznych flag podczas kompilacji, liczą się one do limitu bajtów (np. Jeśli twoja linia kompilacji jest gcc bomb.c -o bomb -O3 -lm, -O3 -lmczęść (7 bajtów) zostanie policzona (zwróć uwagę, że początkowa spacja nie jest liczona).
• Preprocesory są dozwolone tylko wtedy, gdy są standardową opcją kompilacji dla twojego języka.
• Środowisko zależy od ciebie, ale aby uczynić to weryfikowalnym, trzymaj się najnowszych (tj. Dostępnych) wersji kompilatora i systemów operacyjnych (i oczywiście określ, którego używasz).
• Musi się kompilować bez błędów (ostrzeżenia są OK), a awaria kompilatora nie ma znaczenia.
• To, co faktycznie robi twój program , jest nieistotne, chociaż nie może być niczym złośliwym. Nie musi nawet być w stanie się uruchomić.

Przykład 1

Program C.

main(){return 1;}

Kompilowany z Apple LLVM version 7.0.2 (clang-700.1.81)OS X 10.11 (64-bit):

clang bomb.c -o bomb -pg

Tworzy plik 9228 bajtów. Całkowity rozmiar źródła to 17 + 3 (dla -pg) = 20 bajtów, co łatwo mieści się w limicie rozmiaru.

Przykład 2

Program Brainfuck:

++++++[->++++++++++++<]>.----[--<+++>]<-.+++++++..+++.[--->+<]>-----.--
-[-<+++>]<.---[--->++++<]>-.+++.------.--------.-[---<+>]<.[--->+<]>-.

Przeniesione z awib do c z:

./awib < bomb.bf > bomb.c

Następnie skompilowany z Apple LLVM version 7.0.2 (clang-700.1.81)OS X 10.11 (64-bit):

clang bomb.c

Tworzy plik 8464 bajtów. Łączna ilość danych wejściowych wynosi 143 bajty (ponieważ @lang_cjest domyślną opcją awib, nie trzeba jej dodawać do pliku źródłowego, a żadne polecenie nie ma specjalnych flag).

Należy również pamiętać, że w tym przypadku plik tymczasowy bomb.c ma 802 bajtów, ale nie ma to wpływu na rozmiar źródła ani rozmiar wyjściowy.

Ostatnia uwaga

Jeśli zostanie uzyskana moc wyjściowa większa niż 4 GB (być może jeśli ktoś znajdzie kompletny preprocesor Turinga), konkurencja będzie dotyczyć najmniejszego źródła, które tworzy plik o co najmniej takiej wielkości (po prostu nie jest praktyczne testowanie zgłoszeń, które stają się zbyt duże) .

C, (14 + 15) = źródło 29 bajtów, plik wykonywalny 17 179 875 837 (16 GB)

Dzięki @viraptor za 6 bajtów off.

Dzięki @hvd za 2 bajty wyłączone i rozmiar pliku wykonywalnego x4.

Definiuje to mainfunkcję jako dużą tablicę i inicjuje jej pierwszy element. To powoduje, że GCC przechowuje całą tablicę w wynikowym pliku wykonywalnym.

Ponieważ ta tablica jest większa niż 2 GB, musimy dostarczyć -mcmodel=mediumflagę do GCC. Dodatkowe 15 bajtów jest uwzględnionych w wyniku, zgodnie z zasadami.

main[-1u]={1};

Nie oczekuj, że ten kod zrobi coś miłego po uruchomieniu.

Połącz z:

gcc -mcmodel=medium cbomb.c -o cbomb

Zajęło mi trochę czasu, aby przejść do testowania sugestii @ hvd - i znaleźć maszynę z wystarczającą ilością soku, aby sobie z tym poradzić. W końcu znalazłem starą nieprodukcyjną maszynę RedHat 5.6 z 10 GB pamięci RAM, 12 GB wymiany i / tmp ustawioną na dużą partycję lokalną. Wersja GCC to 4.1.2. Całkowity czas kompilacji około 27 minut.

Ze względu na obciążenie procesora i pamięci RAM odradzam wykonywanie tej kompilacji na dowolnym komputerze związanym z produkcją .

C #, około 1 min do skompilowania, wyjście binarne 28 MB:

class X<A,B,C,D,E>{class Y:X<Y,Y,Y,Y,Y>{Y.Y.Y.Y.Y.Y.Y.Y.Y y;}}

Dodanie większej liczby Y spowoduje wykładniczy wzrost rozmiaru.

Wyjaśnienie Pharap zgodnie z prośbą @Odomontois:

Ta odpowiedź nadużywa parametrów dziedziczenia i typu do tworzenia rekurencji. Aby zrozumieć, co się dzieje, łatwiej jest najpierw uprościć problem. Zastanów się class X<A> { class Y : X<Y> { Y y; } }, który generuje klasę ogólną X<A>, która ma klasę wewnętrzną Y. X<A>.Ydziedziczy X<Y>, stąd X<A>.Yteż ma klasę wewnętrzną Y, która jest wtedy X<A>.Y.Y. Ma to również klasę wewnętrzną Y, a ta klasa wewnętrzna Yma klasę wewnętrzną Yitp. Oznacza to, że możesz używać scope resolution ( .) ad infinitum i za każdym razem, gdy go używasz, kompilator musi wydedukować inny poziom dziedziczenia i parametryzację typu .

Dodając dodatkowe parametry typu, praca kompilatora na każdym etapie jest zwiększana.

Rozważ następujące przypadki:
W class X<A> { class Y : X<Y> { Y y;} }typie parametr Ama typ X<A>.Y.
W class X<A> { class Y : X<Y> { Y.Y y;} }typ param Ama typ X<X<A>.Y>.Y.
W class X<A> { class Y : X<Y> { Y.Y.Y y;} }typ param Ama typ X<X<X<A>.Y>.Y>.Y.
W class X<A,B> { class Y : X<Y,Y> { Y y;} }typie param Ajest X<A,B>.Yi Bjest X<A,B>.Y.
W class X<A> { class Y : X<Y> { Y.Y y;} }typie param Ajest X<X<A,B>.Y, X<A,B>.Y>.Yi Bjest X<X<A,B>.Y, X<A,B>.Y>.Y.
W class X<A> { class Y : X<Y> { Y.Y.Y y;} }typie param Ajest X<X<X<A,B>.Y, X<A,B>.Y>.Y, X<X<A,B>.Y, X<A,B>.Y>.Y>.Yi Bjest X<X<X<A,B>.Y, X<A,B>.Y>.Y, X<X<A,B>.Y, X<A,B>.Y>.Y>.Y.

W następstwie tego wzorca, można sobie wyobrazić tylko ¹ pracy kompilator musiałby zrobić, by wydedukować, co Asię Esą Y.Y.Y.Y.Y.Y.Y.Y.Yw definicji class X<A,B,C,D,E>{class Y:X<Y,Y,Y,Y,Y>{Y.Y.Y.Y.Y.Y.Y.Y.Y y;}}.

¹ Możesz to rozgryźć, ale potrzebujesz dużo cierpliwości, a inteligencja ci tutaj nie pomoże.

Python 3, 13-bajtowe źródło, 9 057,900,463 bajtów (8,5GiB) .pyc-file

(1<<19**8,)*2

Edycja : Zmieniłem kod na powyższą wersję po tym, jak zdałem sobie sprawę, że reguły mówią, że wielkość wyjściowa powyżej 4GiB nie ma znaczenia, a kod dla tego jest jeszcze trochę krótszy; Poprzedni kod - i co ważniejsze wyjaśnienie - można znaleźć poniżej.

Python 3, 16 bajtowe źródło, plik .pyc> 32 TB (jeśli masz wystarczającą ilość pamięci, miejsca na dysku i cierpliwości)

(1<<19**8,)*4**7

Objaśnienie: Python 3 ciągle się składa, a duże wykładziny szybko się potęgują. Format używany w plikach .pyc przechowuje długość reprezentacji liczb całkowitych przy użyciu 4 bajtów, a w rzeczywistości limit wydaje się bardziej podobny 2**31, więc używając tylko potęgowania do wygenerowania jednej dużej liczby, limit generuje 2 GB. plik pyc ze źródła 8-bajtowego. ( 19**8jest nieco nieśmiały 8*2**31, więc 1<<19**8ma reprezentację binarną nieco poniżej 2 GB; mnożenie przez osiem to dlatego, że chcemy bajtów, a nie bitów)

Jednak krotki są również niezmienne, a mnożenie krotki jest również stale składane, więc możemy powielić ten blob 2 GB tyle razy, ile chcemy, przynajmniej 2**31prawdopodobnie. 4**7Dostać się do 32TB został wybrany tylko dlatego, że był to pierwszy wykładnik udało mi się znaleźć, że piłka poprzednią 16TB odpowiedź.

Niestety, mając pamięć na swoim komputerze, mogłem to przetestować tylko do mnożnika 2, tj. (1<<19**8,)*2, który wygenerował plik 8,5 GB, co mam nadzieję pokazuje, że odpowiedź jest realistyczna (tzn. rozmiar pliku nie jest ograniczony do 2 ** 32 = 4 GB).

Poza tym nie mam pojęcia, dlaczego rozmiar pliku, który uzyskałem podczas testowania, wynosił 8,5 GB zamiast 4 GB, czego się spodziewałem, a plik jest na tyle duży, że w tej chwili nie mam ochoty się w niego grzebać.

Jeśli zostanie uzyskana moc wyjściowa większa niż 4 GB (być może jeśli ktoś znajdzie kompletny preprocesor Turinga), konkurencja będzie dotyczyć najmniejszego źródła, które tworzy plik o co najmniej takiej wielkości (po prostu nie jest praktyczne testowanie zgłoszeń, które stają się zbyt duże) .

„Szablon Haskell” pozwala na generowanie kodu Haskell w czasie kompilacji przy użyciu Haskell, a zatem jest kompletnym wstępnym procesorem.

Oto moja próba, sparametryzowana dowolnym wyrażeniem liczbowym FOO:

import Language.Haskell.TH;main=print $(ListE .replicate FOO<$>[|0|])

Magia to kod wewnątrz „splice” $(...). Zostanie to wykonane w czasie kompilacji, aby wygenerować Haskell AST, który zostanie wszczepiony w AST programu zamiast połączenia.

W tym przypadku tworzymy prosty AST reprezentujący literał 0, replikujemy te FOOczasy, aby utworzyć listę, a następnie używamy ListEz Language.Haskell.THmodułu, aby przekształcić tę listę AST w jeden duży AST reprezentujący literał [0, 0, 0, 0, 0, ...].

Powstały program jest równoważny main = print [0, 0, 0, ...]z FOOpowtórzeniami 0.

Aby skompilować do ELF:

$ ghc -XTemplateHaskell big.hs
[1 of 1] Compiling Main             ( big.hs, big.o )
Linking big ...
$ file big
big: ELF 32-bit LSB executable, Intel 80386, version 1 (SYSV), dynamically linked, interpreter /nix/store/mibabdfiaznqaxqiy4bqhj3m9gaj45km-glibc-2.21/lib/ld-linux.so.2, for GNU/Linux 2.6.32, not stripped

Waży to 83 bajty (66 dla kodu Haskell i 17 dla -XTemplateHaskellargumentu) plus długość FOO.

Możemy uniknąć argumentu kompilatora i po prostu skompilować ghc, ale musimy umieścić {-# LANGUAGE TemplateHaskell#-}na początku, co powoduje wzrost kodu do 97 bajtów.

Oto kilka przykładowych wyrażeń FOOi wielkość wynikowego pliku binarnego:

FOO         FOO size    Total size    Binary size
-------------------------------------------------
(2^10)      6B          89B           1.1MB
(2^15)      6B          89B           3.6MB
(2^17)      6B          89B           12MB
(2^18)      6B          89B           23MB
(2^19)      6B          89B           44MB

Skończyło mi się kompilowanie pamięci RAM (2^20).

Możemy również stworzyć nieskończoną listę, używając repeatzamiast replicate FOO, ale to zapobiega kompilatorowi;)

C ++, 250 + 26 = 276 bajtów

template<int A,int B>struct a{static const int n;};
template<int A,int B>const int a<A,B>::n=a<A-1,a<A,B-1>::n>::n;
template<int A>struct a<A,0>{static const int n=a<A-1,1>::n;};
template<int B>struct a<0,B>{static const int n=B+1;};
int h=a<4,2>::n;

Jest to funkcja Ackermann zaimplementowana w szablonach. Nie mogę się skompilować h=a<4,2>::n;na moim małym (6 GB) komputerze, ale udało mi się h=a<3,14>uzyskać plik wyjściowy o wielkości 26 MB. Możesz dostroić stałe, aby przekroczyć granice platformy - wskazówki znajdziesz w linkowanym artykule z Wikipedii.

Wymaga -gflagi dla GCC (ponieważ wszystkie symbole debugowania faktycznie zajmują dowolne miejsce) i głębia szablonu większa niż domyślna. Moja linia kompilacji zakończyła się jako

g++ -ftemplate-depth=999999 -g -c -o 69189.o 69189.cpp

Informacje o platformie

g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2
Linux 3.13.0-46-generic #79-Ubuntu SMP x86_64 GNU/Linux

ASM, 61 bajtów (źródło 29 bajtów, 32 bajty na flagi), plik wykonywalny 4,294,975,320 bajtów

.globl main
main:
.zero 1<<32

Połącz z gcc the_file.s -mcmodel=large -Wl,-fuse-ld=gold

Oto moja odpowiedź C z 2005 roku. Wytworzyłby plik binarny 16 TB, gdybyś miał 16 TB pamięci RAM (nie masz).

struct indblock{
   uint32_t blocks[4096];
};

struct dindblock {
    struct indblock blocks[4096];
};

struct tindblock {
    struct dindblock blocks[4096];
};

struct inode {
    char data[52]; /* not bothering to retype the details */
    struct indblock ind;
    struct dindblock dint;
    struct tindblock tind;
};

struct inode bbtinode;

int main(){}

Zwykły stary preprocesor C: wejście 214 bajtów, wyjście 5 MB

Zainspirowany moim prawdziwym preprocesorem zawiodłem tutaj .

#define A B+B+B+B+B+B+B+B+B+B
#define B C+C+C+C+C+C+C+C+C+C
#define C D+D+D+D+D+D+D+D+D+D
#define D E+E+E+E+E+E+E+E+E+E
#define E F+F+F+F+F+F+F+F+F+F
#define F x+x+x+x+x+x+x+x+x+x

int main(void) { int x, y = A; }

Eksperymenty pokazują, że każdy poziom #defines spowoduje (zgodnie z oczekiwaniami) wydajność około dziesięciokrotnie większą. Ale ponieważ ten przykład skompilował się dłużej niż godzinę, nigdy nie przeszedłem do „G”.

Java, źródło 450 + 22 = 472 bajtów, plik klasy ~ 1GB

B.java (wersja golfowa, ostrzeżenie podczas kompilacji)

import javax.annotation.processing.*;@SupportedAnnotationTypes("java.lang.Override")public class B extends AbstractProcessor{@Override public boolean process(java.util.Set a,RoundEnvironment r){if(a.size()>0){try(java.io.Writer w=processingEnv.getFiler().createSourceFile("C").openWriter()){w.write("class C{int ");for(int i=0;i<16380;++i){for(int j=0;j<65500;++j){w.write("i");}w.write(i+";int ");}w.write("i;}");}catch(Exception e){}}return true;}}

B.java (wersja bez golfa)

import java.io.Writer;
import java.util.Set;

import javax.annotation.processing.AbstractProcessor;
import javax.annotation.processing.RoundEnvironment;
import javax.annotation.processing.SupportedAnnotationTypes;
import javax.annotation.processing.SupportedSourceVersion;
import javax.lang.model.SourceVersion;
import javax.lang.model.element.TypeElement;

@SupportedAnnotationTypes("java.lang.Override")
@SupportedSourceVersion(SourceVersion.RELEASE_8)
public class B extends AbstractProcessor {
    @Override
    public boolean process(Set<? extends TypeElement> annotations, RoundEnvironment roundEnv) {
        if (annotations.size() > 0) {
            try (Writer writer = processingEnv.getFiler().createSourceFile("C").openWriter()) {
                writer.write("class C{int ");
                for (int i = 0; i < 16380; ++i) {
                    for (int j = 0; j < 65500; ++j) {
                        writer.write("i");
                    }
                    writer.write(i + ";int ");
                }
                writer.write("i;}");
            } catch (Exception e) {
            }
        }
        return true;
    }
}

Kompilacja

javac B.java
javac -J-Xmx16G -processor B B.java

Wyjaśnienie

Ta bomba używa procesorów adnotacji. Wymaga 2 przejść kompilacyjnych. Pierwszy przebieg buduje klasę procesora B. Podczas drugiego przejścia procesor tworzy nowy plik źródłowy C.javai kompiluje go do plikuC.class rozmiaru1,073,141,162 bajtów.

Istnieje kilka ograniczeń podczas próby utworzenia dużego pliku klasy:

• Utworzenie identyfikatorów dłuższych niż około 64 tys. Powoduje: error: UTF8 representation for string "iiiiiiiiiiiiiiiiiiii..." is too long for the constant pool .
• Utworzenie ponad około 64 000 zmiennych / funkcji powoduje: error: too many constants
• Istnieje również limit około 64k dla rozmiaru kodu funkcji.
• Wydaje się, że istnieje ogólny limit (błąd?) W kompilatorze Java wynoszący około 1 GB dla .classpliku. Jeśli zwiększę 16380do16390 powyższego kodu, kompilator nigdy nie zwraca.
• .javaPlik ma również limit około 1 GB . Zwiększenie 16380do 16400powyższego kodu powoduje: An exception has occurred in the compiler (1.8.0_66). Please file a bug ...po którym następuje java.lang.IllegalArgumentException.

C, źródło 26 bajtów, wyjście 2139103367 bajtów, poprawny program

const main[255<<21]={195};

Opracowano przy użyciu: gcc cbomb.c -o cbomb (gcc wersja 4.6.3, Ubuntu 12.04, ~ 77 sekund)

Pomyślałem, że spróbuję zobaczyć, jak duży mogę zrobić prawidłowy program bez użycia opcji wiersza poleceń. Pomysł mam z tej odpowiedzi: https://codegolf.stackexchange.com/a/69193/44946 przez Digital Trauma. Zobacz komentarze tam, dlaczego to się kompiluje.

Jak to działa: constUsuwa flagę zapisu ze stron w segmencie, dzięki czemu main można wykonać. Jest 195to kod maszynowy Intel do zwrotu. A ponieważ architektura Intela ma charakter endian, jest to pierwszy bajt. Program zakończy działanie bez względu na kod startowy umieszczony w rejestrze eax, prawdopodobnie 0.

To tylko około 2 gig, ponieważ linker używa 32-bitowych podpisanych wartości dla przesunięć. Jest o 8 megapikseli mniejszy niż 2 gig, ponieważ kompilator / linker potrzebuje trochę miejsca do pracy i jest to największy, jaki udało mi się uzyskać bez błędów linkera - ymmv.

Boo , 71 bajtów. Czas kompilacji: 9 minut. 134.222.236 bajtów wykonywalny

macro R(e as int):
 for i in range(2**e):yield R.Body
x = 0
R 25:++x

Używa makra R(dla Powtarzania), aby kompilator pomnożył instrukcję przyrostu dowolną liczbę razy. Nie są wymagane żadne specjalne flagi kompilatora; po prostu zapisz plik jako bomb.booi uruchom kompilator, booc bomb.booaby go skompilować.

Kotlin , źródło 90 bajtów, 177416 bajtów (173 KB) skompilowany plik binarny JVM

inline fun a(x:(Int)->Any){x(0);x(1)}
fun b()=a{a{a{a{a{a{a{a{a{a{a{println(it)}}}}}}}}}}}

Technicznie możesz to wydłużyć jeszcze bardziej, zagnieżdżając wyrażenie. Jednak kompilator ulega awarii z StackOverflowbłędem, jeśli zwiększysz rekurencję.

C ++, 214 bajtów (nie są wymagane specjalne opcje kompilacji)

#define Z struct X
#define T template<int N
T,int M=N>Z;struct Y{static int f(){return 0;}};T>Z<N,0>:Y{};T>Z<0,N>:Y{};T,int M>Z{static int f(){static int x[99999]={X<N-1,M>::f()+X<N,M-1>::f()};}};int x=X<80>::f();

Jest to dość prosta dwuwymiarowa rekurencja szablonu (głębokość rekurencji jest równa pierwiastkowi kwadratowemu całkowitej liczby wysłanych szablonów, więc nie przekroczy limitów platformy), z małą ilością statycznych danych w każdym z nich.

Wygenerowany plik obiektowy g++ 4.9.3 x86_64-pc-cygwinma 2567355421 bajtów (2.4GiB).

Zwiększenie wartości początkowej powyżej 80 przerywa asembler gcc cygwin (zbyt wiele segmentów).

Ponadto 99999można go zastąpić 9<<19lub w podobny sposób, aby zwiększyć rozmiar bez zmiany kodu źródłowego ... ale nie sądzę, że potrzebuję więcej miejsca na dysku niż już jestem;)

Scala - źródło 70 bajtów, wynik 22980842 bajtów (po słoiku)

import scala.{specialized => s}
class X[@s A, @s B, @s C, @s D, @s E]

Daje to 9 ⁵ (około 59 000) wyspecjalizowanych plików klas, które są pakowane w słoik o wielkości około 23 MB. Zasadniczo możesz kontynuować, jeśli masz system plików, który może obsłużyć tyle plików i wystarczającą ilość pamięci.

(Jeśli polecenie jar musi być dołączone, ma 82 bajty).

C 284 + 2 bajty dla -cIN gcc bomb.c -o bomb.o -c; wyjście: 2 147 484 052 bajtów

#define a 1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1
#define b a,a,a,a,a,a,a,a,a,a,a,a,a,a,a,a
#define c b,b,b,b,b,b,b,b,b,b,b,b,b,b,b,b
#define d c,c,c,c,c,c,c,c,c,c,c,c,c,c,c,c
#define e d,d,d,d,d,d,d,d,d,d,d,d,d,d,d,d
#define f e,e,e,e,e,e,e,e,e,e,e,e,e,e,e,e
__int128 x[]={f,f,f,f,f,f,f,f};

Buczenie, o wiele więcej, niż można się po tym spodziewać

macro R(e as int):for i in range(9**e):yield R.Body
x = 0
R 99:++x

Python 3:

9**9**9**9**9

Bomba tetracyjna