Einführung
Sie kennen sich wahrscheinlich mit Zip-Bomben , XML-Bomben usw. aus. Einfach ausgedrückt handelt es sich um (relativ) kleine Dateien, die bei der Interpretation durch naive Software eine enorme Leistung erbringen. Die Herausforderung besteht darin, einen Compiler auf die gleiche Weise zu missbrauchen.
Herausforderung
Schreiben Sie einen Quellcode, der 512 Bytes oder weniger belegt und der in eine Datei kompiliert wird, die den größtmöglichen Platz einnimmt. Die größte Ausgabedatei gewinnt!
Regeln
OK, es gibt einige wichtige Klarstellungen, Definitionen und Einschränkungen.
- Die Ausgabe der Kompilierung muss eine ELF- Datei, eine Windows Portable Executable (.exe) oder ein virtueller Bytecode für die JVM oder die CLR von .Net sein (andere Arten von virtuellem Bytecode sind wahrscheinlich ebenfalls in Ordnung, wenn Sie dazu aufgefordert werden). Update: Pythons .pyc / .pyo-Ausgabe zählt ebenfalls .
- Wenn Ihre bevorzugte Sprache nicht direkt in eines dieser Formate kompiliert werden kann, ist auch die Transpilation gefolgt von der Kompilierung zulässig ( Update: Sie können mehrere Transpilierungen durchführen, sofern Sie nie dieselbe Sprache mehr als einmal verwenden ).
- Ihr Quellcode kann aus mehreren Dateien und sogar aus Ressourcendateien bestehen, die Gesamtgröße aller dieser Dateien darf jedoch 512 Byte nicht überschreiten.
- Sie können keine anderen Eingaben als Ihre Quelldatei (en) und die Standardbibliothek der Sprache Ihrer Wahl verwenden. Das statische Verknüpfen von Standardbibliotheken ist OK, wenn dies unterstützt wird. Insbesondere keine Bibliotheken von Drittanbietern oder Betriebssystembibliotheken.
- Es muss möglich sein, Ihre Kompilierung mit einem Befehl oder einer Reihe von Befehlen aufzurufen. Wenn Sie bestimmte Flags erfordern beim Kompilieren, diese auf Ihre Byte - Grenze zählen (zB wenn Ihre Kompilierung Linie ist
gcc bomb.c -o bomb -O3 -lm
, das-O3 -lm
wird ein Teil (7 Byte) gezählt werden (die anfängliche Spitzen Raum zu beachten , wird nicht mitgerechnet). - Präprozessoren sind nur zulässig , wenn sie eine Standard-Kompilierungsoption für Ihre Sprache sind.
- Die Umgebung liegt bei Ihnen, aber um dies überprüfbar zu machen, halten Sie sich bitte an die neuesten (dh verfügbaren) Compilerversionen und Betriebssysteme (und geben Sie an, welche Sie verwenden).
- Es muss fehlerfrei kompiliert werden (Warnungen sind in Ordnung) und ein Absturz des Compilers zählt für nichts.
- Was Ihr Programm tatsächlich tut, ist irrelevant, obwohl es nichts Bösartiges sein kann. Es muss nicht einmal in der Lage sein zu starten.
Beispiel 1
Das C-Programm
main(){return 1;}
Kompiliert mit Apple LLVM version 7.0.2 (clang-700.1.81)
OS X 10.11 (64-Bit):
clang bomb.c -o bomb -pg
Erzeugt eine Datei mit 9228 Bytes. Die Gesamtgröße der Quelle beträgt 17 + 3 (für die -pg
) = 20 Bytes, was leicht innerhalb der Größenbeschränkung liegt.
Beispiel 2
Das Brainfuck-Programm:
++++++[->++++++++++++<]>.----[--<+++>]<-.+++++++..+++.[--->+<]>-----.--
-[-<+++>]<.---[--->++++<]>-.+++.------.--------.-[---<+>]<.[--->+<]>-.
Transpiled mit awib zu c mit:
./awib < bomb.bf > bomb.c
Dann kompiliert mit Apple LLVM version 7.0.2 (clang-700.1.81)
OS X 10.11 (64-Bit):
clang bomb.c
Erzeugt eine Datei mit 8464 Bytes. Die Gesamteingabe beträgt hier 143 Byte (da @lang_c
awib standardmäßig der Quelldatei hinzugefügt werden musste und in keinem der Befehle spezielle Flags vorhanden sind).
Beachten Sie auch, dass in diesem Fall die temporäre Datei bomb.c 802 Byte groß ist, dies jedoch weder für die Quell- noch für die Ausgabegröße gilt.
Schlussbemerkung
Wenn eine Ausgabe von mehr als 4 GB erreicht wird (wenn jemand einen hervorragenden vollständigen Präprozessor findet), wird der Wettbewerb um die kleinste Quelle ausgetragen, die eine Datei mit mindestens dieser Größe erstellt (es ist einfach nicht praktikabel, zu große Einreichungen zu testen ). .
Antworten:
C, (14 + 15) = 29 Byte Quelle, 17.179.875.837 (16 GB) Byte ausführbar
Vielen Dank an @viraptor für 6 Bytes aus.
Dank an @hvd für 2 Bytes und die ausführbare Größe x4.
Dadurch wird die
main
Funktion als großes Array definiert und das erste Element initialisiert. Dadurch speichert GCC das gesamte Array in der resultierenden ausführbaren Datei.Da dieses Array größer als 2 GB ist, müssen wir das
-mcmodel=medium
Flag für GCC bereitstellen . Die zusätzlichen 15 Bytes sind gemäß den Regeln in der Wertung enthalten.Erwarten Sie nicht, dass dieser Code beim Ausführen etwas Nettes bewirkt.
Kompilieren mit:
Ich habe eine Weile gebraucht, um den Vorschlag von @ hvd zu testen - und eine Maschine zu finden, die genug Saft enthält, um damit umzugehen. Schließlich fand ich eine alte Nicht-Produktions-RedHat 5.6-VM mit 10 GB RAM, 12 GB Swap und / tmp, die auf eine große lokale Partition eingestellt war. Die GCC-Version ist 4.1.2. Gesamte Kompilierzeit ca. 27 Minuten.
quelle
a
. Sie können nur verwendenmain[1<<30]={1};
1<<30
dann wollen,7<<28
könnte eine Option sein.C #, ca. 1 min zu kompilieren, 28MB Output Binary:
Das Hinzufügen von mehr Y erhöht die Größe exponentiell.
Eine Erklärung von Pharap gemäß der Anfrage von @Odomontois:
Diese Antwort missbraucht Vererbungs- und Typparameter, um eine Rekursion zu erstellen. Um zu verstehen, was passiert, ist es einfacher, das Problem zuerst zu vereinfachen. Betrachten Sie
class X<A> { class Y : X<Y> { Y y; } }
, was die generische Klasse erzeugtX<A>
, die eine innere Klasse hatY
.X<A>.Y
erbtX<Y>
, hat alsoX<A>.Y
auch eine innere KlasseY
, die dann istX<A>.Y.Y
. Dies hat dann auch eine innere KlasseY
, und diese innere KlasseY
hat eine innere KlasseY
usw. Dies bedeutet, dass Sie scope resolution (.
) ad infinitum verwenden können und jedes Mal, wenn Sie es verwenden, muss der Compiler eine andere Ebene der Vererbung und Typparametrisierung ableiten .Durch Hinzufügen zusätzlicher Typparameter wird die Arbeit des Compilers in jeder Phase weiter erhöht.
Betrachten Sie die folgenden Fälle:
In
class X<A> { class Y : X<Y> { Y y;} }
type hat paramA
einen Typ vonX<A>.Y
.In
class X<A> { class Y : X<Y> { Y.Y y;} }
type hat paramA
einen Typ vonX<X<A>.Y>.Y
.In
class X<A> { class Y : X<Y> { Y.Y.Y y;} }
type hat paramA
einen Typ vonX<X<X<A>.Y>.Y>.Y
.Im
class X<A,B> { class Y : X<Y,Y> { Y y;} }
Typ paramA
istX<A,B>.Y
undB
istX<A,B>.Y
.Im
class X<A> { class Y : X<Y> { Y.Y y;} }
Typ paramA
istX<X<A,B>.Y, X<A,B>.Y>.Y
undB
istX<X<A,B>.Y, X<A,B>.Y>.Y
.Im
class X<A> { class Y : X<Y> { Y.Y.Y y;} }
Typ paramA
istX<X<X<A,B>.Y, X<A,B>.Y>.Y, X<X<A,B>.Y, X<A,B>.Y>.Y>.Y
undB
istX<X<X<A,B>.Y, X<A,B>.Y>.Y, X<X<A,B>.Y, X<A,B>.Y>.Y>.Y
.Nach diesem Muster kann man sich nur vorstellen 1 die Arbeit der Compiler würde tun müssen, um zu folgern , was sind in der Definition .
A
E
Y.Y.Y.Y.Y.Y.Y.Y.Y
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;}}
1 Sie könnten es herausfinden, aber Sie würden viel Geduld benötigen, und Intellisense wird Ihnen hier nicht weiterhelfen.
quelle
Y
Sekunden .Python 3, 13-Byte-Quelle, 9.057.900.463 Byte (8,5 GB) .pyc-Datei
Bearbeiten : Der Code wurde auf die obige Version geändert, nachdem mir klar wurde, dass die Regeln sagen, dass eine Ausgabegröße über 4 GB keine Rolle spielt und der Code für diese Version etwas kürzer ist. Der vorherige Code - und vor allem die Erklärung - finden Sie unten.
Python 3, 16-Byte-Quelle,> 32 TB .pyc-Datei (wenn Sie über genügend Arbeitsspeicher, Speicherplatz und Geduld verfügen)
Erklärung: Python 3 faltet konstant und Sie erhalten mit Exponentation schnell große Zahlen. Das Format, das von .pyc-Dateien verwendet wird, speichert die Länge der Ganzzahldarstellung mit 4 Bytes, und in Wirklichkeit scheint das Limit eher zu sein. Wenn Sie
2**31
also nur Exponentation verwenden, um eine große Zahl zu generieren, scheint das Limit 2 GB zu generieren. pyc datei von einer 8 byte quelle. (19**8
ist ein bisschen schüchtern8*2**31
,1<<19**8
hat also eine binäre Darstellung knapp 2 GB; die Multiplikation mit acht ist, weil wir Bytes wollen, keine Bits)Tupel sind jedoch auch unveränderlich, und das Multiplizieren eines Tupels wird ebenfalls konstant gefaltet, sodass wir diesen 2-GB-Blob so oft duplizieren können, wie wir möchten
2**31
, wahrscheinlich bis zu mindestens einem Mal. Der4**7
zu 32 TB zu bekommen, wurde nur gewählt, weil es der erste Exponent war, den ich finden konnte, der die vorherige 16 TB-Antwort schlug.Leider konnte ich mit dem Speicher, den ich auf meinem eigenen Computer habe, dies nur bis zu einem Multiplikator von 2 testen, dh.
(1<<19**8,)*2
, die eine 8,5 GB-Datei erzeugt hat, was meiner Meinung nach zeigt, dass die Antwort realistisch ist (dh die Dateigröße ist nicht auf 2 ** 32 = 4 GB beschränkt).Außerdem habe ich keine Ahnung, warum die Dateigröße beim Testen 8,5 GB statt der erwarteten 4 GB betrug, und die Datei ist groß genug, sodass ich im Moment keine Lust habe, darin herumzustöbern.
quelle
(1<<19**8,)*2
? 4 GB sind genug.1<<18
auf meinem Computer (1,5 GB) bestätigen, aber ich werde es später unter Linux testen, wo ich erwarte, dass es mit den vollen 8 GB funktioniert (die 32-TB-Version wird nicht ausprobiert!)python -m py_compile asd.py
damit die .pyc-Datei generiert."Template Haskell" ermöglicht die Generierung von Haskell-Code zur Kompilierungszeit mit Haskell und ist daher ein umfassender Vorprozessor.
Hier ist mein Versuch, parametrisiert durch einen beliebigen numerischen Ausdruck
FOO
:Die Magie ist der Code im "Spleiß"
$(...)
. Dies wird zur Kompilierungszeit ausgeführt, um einen Haskell-AST zu generieren, der anstelle des Spleißes auf den AST des Programms gepfropft wird.In diesem Fall erstellen wir einen einfachen AST, der das Literal darstellt
0
. Wir replizieren diesmalFOO
, um eine Liste zu erstellen. Anschließend verwenden wirListE
dasLanguage.Haskell.TH
Modul, um diese AST-Liste in einen großen AST zu verwandeln, der das Literal darstellt[0, 0, 0, 0, 0, ...]
.Das resultierende Programm entspricht
main = print [0, 0, 0, ...]
mitFOO
Wiederholungen von0
.So kompilieren Sie zu ELF:
Dies entspricht 83 Bytes (66 für den Haskell-Code und 17 für das
-XTemplateHaskell
Argument) plus der Länge vonFOO
.Wir können das Compiler-Argument umgehen und kompilieren nur mit
ghc
, aber wir müssen{-# LANGUAGE TemplateHaskell#-}
am Anfang setzen, was den Code auf 97 Bytes erhöht.Hier sind einige Beispielausdrücke für
FOO
und die Größe der resultierenden Binärdatei:Mir ging der Arbeitsspeicher aus, mit dem ich kompiliert habe
(2^20)
.Wir können auch eine unendliche Liste mit
repeat
anstellereplicate FOO
von erstellen, aber das verhindert, dass der Compiler anhält;)quelle
[...].replicate (2^10)<$>[|0|])
). Ich habe keine Erfahrung mit Haskell. Irgendwelche Tipps zum Kompilieren?<$>
Funktion ist in Haskell weit verbreitet, wurde jedoch in GHC 7.10 nur in den "Auftakt" (die standardmäßig verfügbaren Funktionen) verschoben. Für frühere Versionen müssen Sieimport Control.Applicative;
nach der vorhandenenimport
Anweisung hinzufügen . Ich habe es gerade mit GHC 7.8.4 versucht und es funktioniert.C ++, 250 + 26 = 276 Bytes
Dies ist die in Templates implementierte Ackermann-Funktion . Ich kann mit
h=a<4,2>::n;
meinem kleinen Computer (6 GB) nicht kompilieren , habe es aberh=a<3,14>
mit einer 26-MB-Ausgabedatei geschafft. Sie können die Konstanten so einstellen, dass sie an die Grenzen Ihrer Plattform stoßen. Eine Anleitung finden Sie im verknüpften Wikipedia-Artikel.Erfordert ein
-g
Flag für GCC (da alle Debug-Symbole tatsächlich Speicherplatz belegen) und eine Schablonentiefe, die über dem Standard liegt. Meine Kompilierungszeile endete alsPlattforminformationen
quelle
A+B
in jeder Klasse, jetzt denke ich daran ...ASM, 61 Bytes (29 Bytes Quelle, 32 Bytes für Flags), 4.294.975.320 Bytes ausführbar
Kompilieren mit
gcc the_file.s -mcmodel=large -Wl,-fuse-ld=gold
quelle
1<<30
ist gut genug für C. Da dies Assembler ist, ist die Größe in Bytes.as
schafft es zu übergebenld
,ld
scheitert aber damit . Scheint nicht einmal-mcmodel=medium
zu helfen.gold
:gcc -fuse-ld=gold ...
kompiliert / verlinkt ... eek! Fertiggestellt in 1:29 (89 Sekunden) und einer Größe von 1.073.748.000 Bytes.gcc -o g g.s -mcmodel=large -Wl,-fuse-ld=gold
. Schlussbilanz:4,294,975,320 bytes
Mit 32 zusätzlichen Bytes zur Programmlänge für-mcmodel=large -Wl,-fuse-ld=gold
. Bemerkenswert, dass der Header falsch ist; Die Quelle ist 29 Byte (ohne die zusätzlichen Flags hinzugefügt).1<<33
ich eine8,589,942,616
ausführbare Byte-Datei erhalten.Hier ist meine C-Antwort aus dem Jahr 2005. Würde eine 16-TB-Binärdatei erzeugen, wenn Sie 16 TB RAM hätten (Sie haben keine).
quelle
Normaler alter C-Präprozessor: 214 Byte Eingabe, 5 MB Ausgabe
Inspiriert von meinem realen Präprozessor scheitern hier .
Experimente zeigen, dass jede Stufe von
#define
s (wie erwartet) die Ausgabe ungefähr zehnmal größer macht. Da das Kompilieren dieses Beispiels mehr als eine Stunde dauerte, bin ich nie zu "G" übergegangen.quelle
Java, 450 + 22 = 472 Byte Quelle, ~ 1 GB Klassendatei
B.java (Golfversion, Warnung beim Kompilieren)
B.java (ungolfed version)
Zusammenstellung
Erläuterung
Diese Bombe verwendet Anmerkungsprozessoren. Es werden 2 Kompilierungsdurchläufe benötigt. Der erste Durchgang bildet die Prozessorklasse
B
. Während des zweiten Durchlaufs erstellt der Prozessor eine neue QuelldateiC.java
und kompiliert sie in eineC.class
mit einer Größe von1,073,141,162
Bytes.Es gibt verschiedene Einschränkungen beim Versuch, eine große Klassendatei zu erstellen:
error: UTF8 representation for string "iiiiiiiiiiiiiiiiiiii..." is too long for the constant pool
.error: too many constants
.class
Datei zu geben. Wenn ich zu erhöhen ,16380
um16390
in dem obigen Code der Compiler nie zurückgibt..java
Datei. Das Erhöhen16380
auf16400
im obigen Code führt zu:An exception has occurred in the compiler (1.8.0_66). Please file a bug ...
gefolgt von ajava.lang.IllegalArgumentException
.quelle
try..finally
(Code in finally-Block wird für normale und Ausnahmefälle dupliziert) und Initialisierungsblock (Code aus Initialisierungsblock wird an jeden Konstruktor angehängt)ä
durch eine ersetzti
und die Nummern angepasst. Jetzt sollte die Bombe auf jedem System eine 1-GB-Klasse ohne Codierungsprobleme erstellen. Es benötigt jedoch jetzt viel mehr Speicher.C, 26-Byte-Quelle, 2.139.103.367-Byte-Ausgabe, gültiges Programm
Kompiliert mit:
gcc cbomb.c -o cbomb
(gcc version 4.6.3, Ubuntu 12.04, ~ 77 Sekunden)Ich dachte, ich würde versuchen zu sehen, wie groß ich ein gültiges Programm machen könnte, ohne irgendwelche Befehlszeilenoptionen zu verwenden. Die Idee kam mir aus dieser Antwort: https://codegolf.stackexchange.com/a/69193/44946 von Digital Trauma. Lesen Sie die Kommentare dort, warum dies kompiliert wird.
So funktioniert es: Das
const
entfernt das Schreibflag von den Seiten im Segment, damit main ausgeführt werden kann. Dies195
ist der Intel-Maschinencode für eine Rücksendung. Und da die Intel-Architektur Little-Endian ist, ist dies das erste Byte. Das Programm wird mit dem Startcode beendet, der im eax-Register abgelegt ist, wahrscheinlich mit 0.Es sind nur etwa 2 Gig, da der Linker 32-Bit-Werte mit Vorzeichen für Offsets verwendet. Es ist 8 MB kleiner als 2 GB, da der Compiler / Linker etwas Platz zum Arbeiten benötigt und dies das größte ist, das ich ohne Linker-Fehler bekommen könnte - ymmv.
quelle
Boo , 71 Bytes. Kompilierungszeit: 9 Minuten. 134.222.236 Byte ausführbar
Verwendet ein Makro
R
(für Wiederholung), um den Compiler zu veranlassen, die Inkrement-Anweisung beliebig oft zu multiplizieren. Es werden keine speziellen Compiler-Flags benötigt. Speichern Sie die Datei einfach alsbomb.boo
und rufen Sie den Compiler mitbooc bomb.boo
auf, um sie zu erstellen.quelle
2**e
-Was ist das? Versuchen Sie es9**e
!Kotlin , 90-Byte-Quelle, 177416 Byte (173 KB) kompilierte JVM-Binärdatei
Technisch gesehen können Sie dies sogar noch verlängern, indem Sie den Ausdruck weiter verschachteln. Der Compiler stürzt jedoch mit einem
StackOverflow
Fehler ab, wenn Sie die Rekursion erhöhen.quelle
C ++, 214 Bytes (keine speziellen Kompilierungsoptionen erforderlich)
Es handelt sich um eine recht einfache zweidimensionale Vorlagenrekursion (die Rekursionstiefe ergibt sich aus der Quadratwurzel der insgesamt ausgegebenen Vorlagen, sodass die Plattformgrenzen nicht überschritten werden) mit einer kleinen Menge statischer Daten in jeder Vorlage.
Generierte Objektdatei mit
g++ 4.9.3 x86_64-pc-cygwin
2567355421 Bytes (2.4GiB).Wenn Sie den Anfangswert über 80 erhöhen, wird der Cygwin-GCC-Assembler unterbrochen (zu viele Segmente).
Auch
99999
kann ersetzt werden durch9<<19
oder ähnliches für eine erhöhte Größe , ohne den Quellcode zu ändern ... aber ich glaube nicht , ich brauche mehr Speicherplatz zu verwenden , als ich schon bin;)quelle
-c
Kompilierungsflag, um den Linker zu stoppen (2 zusätzliche Bytes), und ich bin nicht sicher, ob ich .o-Ausgaben akzeptieren kann (nicht eine der aufgelisteten). Trotzdem gefällt es mir, also +1.Scala - 70-Byte-Quelle, 22980842-Byte-Ergebnis (nach jar)
Dies erzeugt 9 5 (ungefähr 59.000) spezialisierte Klassendateien, die in ein Glas von ungefähr 23 MB gepackt werden. Sie können im Prinzip weitermachen, wenn Sie über ein Dateisystem verfügen, das mit so vielen Dateien und genügend Speicher umgehen kann.
(Wenn der Befehl jar enthalten sein muss, sind es 82 Byte.)
quelle
error: java.lang.OutOfMemoryError: GC overhead limit exceeded
. Könnten Sie auch den erforderlichen Befehl für die Kompilierung dokumentieren?scalac -J-Xmx12G X.scala
ich das benutzt. Ich habe nicht getestet, wie viel es tatsächlich braucht.error: error while loading AnnotatedElement, class file '/usr/lib/jvm/java-8-openjdk-amd64/jre/lib/rt.jar(java/lang/reflect/AnnotatedElement.class)' is broken (bad constant pool tag 18 at byte 76) one error found
Leider immer noch nicht kompiliert :( Können Sie die Scala- und Java-Version angeben (vielleicht auch die Plattform)? Ich habe scalac 2.9.2 und OpenJDK 1.8.0_66-internal-b17 unter Debian 8 x86-64 verwendet.java version "1.8.0_72-ea" Java(TM) SE Runtime Environment (build 1.8.0_72-ea-b05) Java HotSpot(TM) 64-Bit Server VM (build 25.72-b05, mixed mode)
,$ scala -version Scala code runner version 2.11.7 -- Copyright 2002-2013, LAMP/EPFL
C, 284 Bytes + 2 für den
-c
Einganggcc bomb.c -o bomb.o -c
; Ausgabe: 2 147 484 052 Bytesquelle
Boo, weit mehr als Sie erwarten können
quelle
Python 3:
Tetrationsbombe
quelle