Вызов Кода — Создайте Компиляторную Бомбу

Введение

Вы, вероятно, знакомы с почтовые бомбы, XML-бомбыи т. д. Проще говоря, это (относительно) небольшие файлы, которые при интерпретации простым программным обеспечением выдают огромный результат. Задача здесь состоит в том, чтобы таким же образом злоупотребить компилятором.

Испытание

Напишите исходный код размером 512 байт или меньше, который компилируется в файл, занимающий максимально возможное пространство. Самый большой выходной файл побеждает!

Правила

Итак, есть несколько важных уточнений, определений и ограничений;

• Результатом компиляции должен быть ЭЛЬФ файл, переносимый исполняемый файл Windows (.exe) или виртуальный байт-код для JVM или CLR .Net (другие типы виртуального байт-кода также, вероятно, подойдут, если их об этом попросят). Обновление: вывод Python .pyc/.pyo также учитывается..
• Если выбранный вами язык не может быть скомпилирован непосредственно в один из этих форматов, также разрешена транспиляция с последующей компиляцией (Обновление: вы можете транспилировать несколько раз, при условии, что вы никогда не используете один и тот же язык более одного раза.).
• Ваш исходный код может состоять из нескольких файлов и даже файлов ресурсов, но общий размер всех этих файлов не должен превышать 512 байт.
• Вы не можете использовать какие-либо другие входные данные, кроме исходных файлов и стандартной библиотеки выбранного вами языка. Статическое связывание стандартных библиотек допустимо, если оно поддерживается. В частности, никаких сторонних библиотек или библиотек ОС.
• Должна быть возможность вызвать вашу компиляцию с помощью команды или серии команд. Если при компиляции вам требуются определенные флаги, эти засчитывайте свой лимит в байтах (например, если ваша строка компиляции

   
   
   
   
   @lang_c 
   
   
   
   

  , the clang bomb.c часть (7 байт) будет учтена (обратите внимание, что начальный пробел не учитывается).
• Препроцессоры разрешены только если они являются стандартным вариантом компиляции для вашего языка.
• Среда зависит от вас, но чтобы сделать это проверяемым, придерживайтесь последних (т. е. доступных) версий компилятора и операционных систем (и, очевидно, укажите, какую вы используете).
• Он должен скомпилироваться без ошибок (предупреждения допустимы), а сбой компилятора ни к чему не приведет.
• Что на самом деле ваша программа делает не имеет значения, хотя это не может быть чем-то вредоносным. Его даже не обязательно начинать.

Пример 1

Программа С

Составлено с ./awib < bomb.bf > bomb.c on OS X 10.11 (64-bit):

Создает файл размером 9228 байт. Общий размер источника равен 17+3 (для -pg ) = 20 bytes, which is easily within size limit.

Пример 2

Программа Brainfuck:

Транспилируется с помощью авиб в c с:

Затем скомпилировано с помощью main(){return 1;} on OS X 10.11 (64-bit):

Создает файл размером 8464 байта. Общий объем ввода здесь составляет 143 байта (поскольку gcc bomb.c -o bomb -O3 -lm is the default for awib it didn't need to be added to the source file, and there are no special flags on either command).

Также обратите внимание, что в этом случае временный файл бомбы.c имеет размер 802 байта, но это не учитывается ни в исходном размере, ни в выходном размере.

Заключительное примечание

Если будет достигнут объем более 4 ГБ (возможно, если кто-нибудь найдет полный препроцессор Тьюринга), конкуренция будет за наименьший источник который создает файл как минимум такого размера (просто нецелесообразно тестировать материалы, которые получают слишком большой).

#code-challenge #busy-beaver #время компиляции

C, (14 + 15) = исходный файл 29 байт, исполняемый файл 17 179 875 837 (16 ГБ)

Спасибо @viraptor за скидку в 6 байт.

Спасибо @hvd за 2 байта и размер исполняемого файла x4.

Это определяет

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 import std;
enum GBS = 1;
void main(){

static foreach(i; 0..2* GBS){

mixin(text(q{static immutable a}, i,q{ = uint.max.BigInt << uint.max;}));

mixin(text(q{a}, i, q{.writeln;}));

}
}

 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Поскольку размер этого массива превышает 2 ГБ, нам необходимо предоставить ldc -c t.d flag to GCC. The extra 15 bytes are included in the score, as per the rules.

Не ожидайте, что этот код выполнит что-нибудь хорошее при запуске.

Скомпилировать с помощью:

Мне потребовалось некоторое время, чтобы проверить предложение @hvd и найти машину, способную с этим справиться. В конце концов я нашел старую непроизводственную виртуальную машину RedHat 5.6 с 10 ГБ ОЗУ, 12 ГБ подкачки и параметром /tmp, установленным для большого локального раздела. Версия GCC — 4.1.2. Общее время компиляции около 27 минут.

Из-за нагрузки на ЦП и ОЗУ я не рекомендую выполнять эту компиляцию на любой машине, связанной с удаленным производством..

Python 3, исходный код 13 байт, 9 057 900 463 байта (8,5 ГиБ).pyc-файл

Редактировать: Изменил код на приведенную выше версию после того, как я понял, что правила гласят, что размер вывода за пределами 4 ГБ не имеет значения, а код для этого немного короче; Предыдущий код и, что более важно, объяснение можно найти ниже.

Python 3, исходный код 16 байт, .pyc-файл >32 ТБ (если у вас достаточно памяти, дискового пространства и терпения)

Объяснение: Python 3 выполняет постоянное свертывание, и вы быстро получаете большие числа с помощью возведения в степень. Однако формат, используемый файлами .pyc, хранит длину целочисленного представления с использованием 4 байтов, и на самом деле ограничение больше похоже на (uint64_t)0 , so using just exponentation to generate one big number, the limit seems to be generating a 2GB .pyc file from an 8 byte source. ( ~ немного стесняется unsigned long long , so uint64_t имеет двоичное представление размером чуть менее 2 ГБ; умножение на восемь связано с тем, что нам нужны байты, а не биты)

Однако кортежи также являются неизменяемыми, и умножение кортежа также сворачивается константой, поэтому мы можем дублировать этот 2-гигабайтный объект столько раз, сколько захотим, по крайней мере до unsigned long long main[~0ull]={~0}; times, probably. The #include <inttypes.h> uint64_t main[(uint64_t)~0]={~0}; дойти до 32 ТБ было выбрано только потому, что это был первый показатель, который я смог найти, превосходящий предыдущий ответ на 16 ТБ.

К сожалению, с той памятью, что есть на моем компьютере, я смог проверить это только до множителя 2, т.е. julia --project=. a.jl , which generated a 8.5GB file, which I hope demonstrates that the answer is realistic (ie. the file size isn't limited to 2**32=4GB).

Кроме того, я понятия не имею, почему размер файла, который я получил при тестировании, составил 8,5 ГБ вместо ожидаемых 4 ГБ, и файл достаточно большой, и мне не хочется сейчас в нем копаться.

C#, компиляция около 1 минуты, выходной двоичный файл размером 28 МБ:

Добавление большего количества букв Y приведет к экспоненциальному увеличению размера.

Объяснение Фарапа по запросу @Odomontois:

Этот ответ злоупотребляет параметрами наследования и типа для создания рекурсии. Чтобы понять, что происходит, проще сначала упростить задачу. Учитывать using A , which generates the generic class module A !(::Val{x}) where x=x .!Val.(0:9^9)end , который имеет внутренний класс name="A" uuid="8945f399-ba5e-44d3-9e17-ab2f7e467331" . A ├── src │ └── A.jl ├── Project.toml └── a.jl наследует pkg"generate A" , hence Project.toml также имеет внутренний класс pkg"dev ./A" , which is then ~/.julia/compiled/<version>/A/xxx.ji . Тогда у этого также есть внутренний класс i , and that inner class Val{i} имеет внутренний класс Val(i) etc. This means that you can use scope resolution ( ! ) до бесконечности, и каждый раз, когда вы его используете, компилятору приходится выводить новый уровень наследования и параметризации типов.

Добавляя дополнительные параметры типа, работа, которую должен выполнять компилятор на каждом этапе, еще больше увеличивается.

Рассмотрим следующие случаи:
В A type param A имеет тип using Pkg pkg"generate A" write("A/src/A.jl","module A !(::Val{x}) where x=x .!Val.(1:9^9)end") pkg"dev A" using A .
В .ji type param i имеет тип litteral_pow .
В inv(a) type param a^-1 имеет тип a*a .
В a^2 type param i является a^i and 0:9^9 .|>i->@eval 2^$i является macro R(e as int):for i in range(9**e):yield R.Body x = 0 R 99:++x .
В -O type param ~~~~~~~y # A bunch of filter modifiers on the element 'y' ¢a # Alias that to 'a' aaa¢b # 3 'a's = 'b' and so on... bbb¢c ccc¢d ddd¢e eee¢f fff¢g ggg¢h h # Run that final 'h' является ~~~~~~~y¢aaaa¢bbbb¢cccc¢dddd¢eeee¢ffff¢gggg¢hh and #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}; является gcc bomb.c -o bomb.o -c .
В -c type param import scala.{specialized => s} class X[@s A, @s B, @s C, @s D, @s E] является 9<<19 and 99999 является g++ 4.9.3 x86_64-pc-cygwin .

Следуя этой схеме, можно только представить¹ работу, которую придется проделать компилятору, чтобы вывести то, что #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(); к StackOverflow находятся в 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)}}}}}}}}}}} in the definition booc bomb.boo .

¹ Вы могли бы разобраться в этом, но вам понадобится много терпения, и intellisense вам здесь не поможет.

Если будет получен результат размером более 4 ГБ (возможно, если кто-то найдет полный препроцессор Тьюринга), конкуренция будет за наименьший источник, который создает файл хотя бы такого размера (просто нецелесообразно тестировать материалы, которые становятся слишком большими). .

«Шаблон Haskell» позволяет генерировать код Haskell во время компиляции с использованием Haskell и, следовательно, является полным препроцессором по Тьюрингу.

Вот моя попытка, параметризованная произвольным числовым выражением bomb.boo :

Магия — это код внутри «сращивания». macro R(e as int): for i in range(2**e):yield R.Body x = 0 R 25:++x . This will be executed at compile time, to generate a Haskell AST, which is grafted on to the program's AST in place of the splice.

В этом случае мы создаем простой AST, представляющий литерал 195 , we replicate this const раз, чтобы составить список, затем мы используем gcc cbomb.c -o cbomb from the const main[255<<21]={195}; модуль, чтобы превратить этот список AST в один большой AST, представляющий буквальный java.lang.IllegalArgumentException .

Полученная программа эквивалентна An exception has occurred in the compiler (1.8.0_66). Please file a bug ... with 16400 повторения 16380 .

Чтобы скомпилировать в ELF:

Его вес составляет 83 байта (66 для кода Haskell и 17 для кода). 16390 argument), plus the length of 16380 .

Мы можем избежать аргумента компилятора и просто скомпилировать с помощью .class , but we have to put error: too many constants в начале, что увеличивает размер кода до 97 байт.

Вот несколько примеров выражений для error: UTF8 representation for string "iiiiiiiiiiiiiiiiiiii..." is too long for the constant pool , and the size of the resulting binary:

У меня закончилась оперативная память при компиляции с помощью C.class .

Мы также можем создать бесконечный список, используя C.java instead of B , но это предотвращает остановку компилятора;)

С++, 250 + 26 = 276 байт

Это функция Аккермана реализовано в шаблонах. Я не могу скомпилировать 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; } } on my little (6GB) machine, but I did manage 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;}} для выходного файла размером 26 МБ. Вы можете настроить константы так, чтобы они соответствовали ограничениям вашей платформы — инструкции см. в связанной статье в Википедии.

Требует #define flag to GCC (because it's all the debug symbols that actually consume any space), and a larger-than-default template depth. My compile line ended up as

Информация о платформе

Вот мой ответ C от 2005 года. Если бы у вас было 16 ТБ оперативной памяти (у вас ее нет), вы создали бы двоичный файл объемом 16 ТБ.

ASM, 61 байт (29 байт исходного кода, 32 байта для флагов), 4 294 975 320 байт исполняемого файла.

Скомпилировать с g++ (Ubuntu 4.8.2-19ubuntu1) 4.8.2 Linux 3.13.0-46-generic #79-Ubuntu SMP x86_64 GNU/Linux

Обычный старый препроцессор C: ввод 214 байт, вывод 5 МБ.

Вдохновлен моим реальным сбоем препроцессора здесь.

Эксперименты показывают, что каждый уровень -g s will (as expected) make the output approximately ten times larger. But since this example took more than an hour to compile, I never went on to "G".

Java, исходный код 450 + 22 = 472 байт, файл класса ~ 1 ГБ

B.java (версия для гольфа, предупреждение во время компиляции)

B.java (версия без гольфа)

Сборник

Объяснение

Эта бомба использует процессоры аннотаций. Требуется 2 прохода компиляции. Первый проход создает класс процессора replicate FOO . During the second pass the processor creates a new source file repeat и компилирует его в (2^20) with a size of 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 байты.

При попытке создать большой файл класса существует несколько ограничений:

• Создание идентификаторов длиной более 64 тыс. приводит к: FOO .
• Создание более 64 тыс. переменных/функций приводит к: {-# LANGUAGE TemplateHaskell#-}
• Также существует ограничение на размер кода функции — около 64 КБ.
• Кажется, в компиляторе Java существует общий предел (ошибка?) около 1 ГБ для ghc file. If I increase FOO к -XTemplateHaskell in the above code the compiler never returns.
• Также существует ограничение в размере около 1 ГБ для $ 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 file. Increasing 0 to FOO in the above code results in: main = print [0, 0, 0, ...] за которым следует [0, 0, 0, 0, 0, ...] .

C, исходный код 26 байт, вывод 2 139 103 367 байт, действительная программа

Скомпилировано с использованием: ListE (gcc version 4.6.3, Ubuntu 12.04, ~77 seconds)

Я подумал, что попробую посмотреть, насколько большой я смогу сделать действующую программу без использования каких-либо параметров командной строки. Я получил идею из этого ответа: https://codegolf.stackexchange.com/a/69193/44946 от Цифровой Травмы. См. комментарии там о том, почему это компилируется.

Как это работает: FOO removes the write flag from the pages in the segment, so main can be executed. The 0 это машинный код Intel для возврата. А поскольку архитектура Intel имеет прямой порядок байтов, это первый байт. Программа выйдет с любым кодом запуска, помещенным в регистр eax, вероятно, с 0.

Это всего около 2 гигабайт, потому что компоновщик использует 32-битные значения со знаком для смещений. Это на 8 мегабайт меньше, чем 2 гигабайта, потому что компилятору/компоновщику требуется некоторое пространство для работы, и это самый большой размер, который я мог получить без ошибок компоновщика - ymmv.

Бу, 71 байт. Время компиляции: 9 минут. 134 222 236 байт исполняемый файл

Использует макрос import Language.Haskell.TH;main=print $(ListE .replicate FOO<$>[|0|]) (for Repeat) to cause the compiler to multiply the increment statement an arbitrary number of times. No special compiler flags are needed; simply save the file as FOO и вызовите компилятор с помощью 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;}} to build it.

Котлин, исходный код 90 байт, 177 416 байт (173 КБ) скомпилированный двоичный файл JVM

Технически вы можете сделать это еще длиннее, вложив выражение дальше. Однако компилятор аварийно завершает работу с E error if you increase the recursion.

C++, 214 байт (специальные параметры компиляции не требуются)

Это довольно простая рекурсия двумерного шаблона (глубина рекурсии равна квадратному корню от общего числа созданных шаблонов, поэтому не выходит за пределы платформы) с небольшим количеством статических данных в каждом из них.

Сгенерированный объектный файл с X<X<X<A,B>.Y, X<A,B>.Y>.Y, X<X<A,B>.Y, X<A,B>.Y>.Y>.Y is 2567355421 bytes (2.4GiB).

Увеличение начального значения выше 80 приводит к поломке ассемблера cygwin gcc (слишком много сегментов).

Также, B can be replaced by X<X<X<A,B>.Y, X<A,B>.Y>.Y, X<X<A,B>.Y, X<A,B>.Y>.Y>.Y или что-то подобное для увеличения размера без изменения исходного кода... но я не думаю, что мне нужно использовать больше дискового пространства, чем я уже есть;)

Scala — источник 70 байт, результат 22980842 байта (после jar)

Это производит 9⁵ (около 59 000) специализированных файлов классов, которые упаковываются в банку размером около 23 МБ. В принципе, вы можете продолжать работу, если у вас есть файловая система, которая может обрабатывать такое количество файлов и достаточно памяти.

(Если необходимо включить команду jar, ее размер составляет 82 байта.)

C, 284 байта + 2 для class X<A> { class Y : X<Y> { Y.Y.Y y;} } in X<X<A,B>.Y, X<A,B>.Y>.Y ; вывод: 2 147 484 052 байта

Миксал 0.7.1, 46 байт исходного кода + 2 байта флага = 48 байт, 2,042 МБ скомпилированного файла.

Простая рекурсивная бомба псевдонима узла. Добавление большего количества псевдонимов заставляет JVM жаловаться на слишком большой основной метод.

Составлено с помощью class X<A> { class Y : X<Y> { Y.Y y;} } flag to disable optimization, which also disables shrinking for some reason.

Буу, это намного больше, чем ты можешь ожидать от этого

Юлия, 22 байта (в памяти)

Попробуйте онлайн!

Сделать компиляционную бомбу в Джулии довольно легко, это легко может произойти случайно. Здесь мы используем тот факт, что X<A,B>.Y has some trickery when A представляет собой целое число, которое позволяет class X<A,B> { class Y : X<Y,Y> { Y y;} } to be turned into X<X<X<A>.Y>.Y>.Y , и A into class X<A> { class Y : X<Y> { Y.Y.Y y;} } . Это означает, что существует новый скомпилированный метод X<X<A>.Y>.Y being compiled for each A . Я почти уверен, что это будет как минимум 4 ГБ, но я не знаю, как это проверить. Однако это компилируется только в памяти и не сохраняется в файле.

Юлия, 114 байт (вывод в формате class X<A> { class Y : X<Y> { Y.Y y;} } file)

(не могу) Попробуйте онлайн! Пытаться A online!

Чтобы сохранить скомпилированный код в файл, функция должна находиться в пакете, поэтому создаем пакет class X<A> { class Y : X<Y> { Y y;} } that has the culprit (the function . ). Y is of type Y , поэтому для каждого компилируется новый метод Y . The output file will be in X<A>.Y.Y В моем тестировании каждый дополнительный метод добавляет как минимум 150 байт (и растет, 182 МБ для 1 М методов), а это означает, что 25 МБ будет достаточно.

в Джулии 1.7 +2 байта, потому что Y is needed

Юлия, 117 байт (без записи файлов)

по сути это то же самое, что и выше, но с уже имеющимися файлами. Это немного дольше, потому что uuid необходим в X<A>.Y (this is taken care of in X<Y> )

файловая структура

Проект.toml, 52 байта

src/A.jl, 47 байт

Попробуйте онлайн!

а.джл, 7 байт

параметры командной строки (в 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;}} folder), +11 bytes

C, 54 байта, смехотворно большой исполняемый файл.

Не совсем оригинальный, но гораздо более разрушительным.

Встроенная, но не портативная версия

Я НЕ собираюсь жертвовать своим ноутбуком только ради этого.

Объяснение

1<<19**8 , 8*2**31 , они оба являются 64-битными целыми числами без знака.

Тильда ( 19**8 ) is the bitwise NOT operator in C (it flips the bits of a value).

2**31 is (1<<19**8,)*4**7 в двоичном формате.

Применяя побитовый оператор НЕ, мы получаем... большое число (\$2^{64}\$).

Кредиты

Большое спасибо пользователю Digital Trauma за его оригинал. выполнение.

gcc -mcmodel=medium cbomb.c -o cbomb is the concatenation operator, and PHP's compiler will try to do constant folding where possible, so it will construct a huge string and store it in PHP's internal bytecode. (I think you can get this written to a file with newer versions.) This is only as efficient as a classic XML entity bomb unfortunately. You'd need a few more repetitions to get to the gigabyte range.

PHP 7.1:

Самое интересное, что по умолчанию самое худшее, что может случиться, — это увидеть ошибку вроде: