Главная
Блог разработчиков phpBB
 
+ 17 предустановленных модов
+ SEO-оптимизация форума
+ авторизация через соц. сети
+ защита от спама

Звездные войны в начальном коде

Anna | 17.06.2014 | нет комментариев
У меня давным-давно была идея реализовать что-нибудь увлекательное, связанное с квайнами. И наконец-то получилось довести это дело до конца. Когда-то увидел реализацию игры «Жизнь» в начальном коде: Self Printing Game of Life и мне захотелось сделать что-то схожее. Некоторое время поразмыслив, я припомнил, что существует ASCII-графика. Но еще увлекательней и труднее было бы сделать анимацию в ASCII-графике. Пример длинно искать не пришлось, примерно сразу же были обнаружена анимация «Звездных войн», а вернее 4 эпизода «Новая Вера» под наименованием Asciimation. Работа японского программиста Yusuke Endoh«квайновое реле» также подстегнула меня к реализации этой идеи. В процесс реализации такого «фильма» пришлось решить уйма других задач, о чем, однако, сожалеть не пришлось.

Получившийся исходник вот: AsciimationQuine_1_3.7z (доступно и в gist), его дозволено запускать вручную покадрово, а дозволено запустить сразу скрипт для отображения сразу каждого фильма. Исходники же каждого плана для его генерации, интерфейса и других утилит выложены на гитхабе: Freaky-Sources (Туда же включены квайны-палиндромы, о которых я теснее писал). Внятное дело, что сходственная вещь не несет в себе никакой утилитарной пользы, это легко just for fun.

Вступление

Анимацию в квайне дозволено выводить только одним методом: выводить всякий дальнейший кадр в консоль при всякой компиляции. Соответственно скорость «фильма» в таком случае зависит от размера кода (чем огромнее код, тем дольше он будет компилировать и пролистываться в консоли), алгорифма распаковки, скорости компиляции (железа). Причем код, основным образом, занимают сжатые кадры анимации.

Вышеупомянутая «игра Жизнь» в качестве поля использует строки, которые инициализируются и выводятся в начале начального кода программы. Такой подход возможен, если число кода невелико, и в процессе компиляции он неизменно будет виден. Впрочем в моем случае размер кода составляет несколько сотен килобайт, а значит выводить кадры необходимо непременно в конце, Дабы их дозволено было увидеть. Было решено выводить кадры не в виде настоящих строчек, а в виде однострочных комментариев (многострочные тоже дозволено применять), что дозволило выводить их без лишних хвостовых символов (финальной фигурной скобочки) и кавычек.

Так как у меня невысокий IQ я не владею специальными способностями и не могу оперировать огромным числом параметров в голове, я решил по максимому автоматизировать процесс написание квайна. К тому же это дозволило отличнее осознать конструкцию квайна и получить навык в смежных областях (парсинг и обработка начального кода C# с поддержкой NRefactory).

Этапы генерации квайна

Таким образом, я решил разбить процесс написания всякого квайна на следующие этапы:

  • Генерация кода.
  • Генерация данных.
  • Минификация кода.
  • Форматирование кода.
  • Генерация квайна.

Все эти этапы выполняются для особым образом составленного образца. Под «кодом», применительно к звездным войнам, подразумевается код, тот, что тот, что распаковывает сжатые данные. А данными и является запакованный массив кадров анимации. Минификация необходима для того, Дабы сделать код нечитаемым уменьшить текстовый размер кода.

Правда в начале была написана версия с обыкновенным классом .NET GZipStream для распаковки сжатых данных. Но я подумал, что это не спортивно, к тому же такой класс существует только для данной платформы. Таким образом, я написал больше трудную версию с собственным архиватором.

Для того, Дабы было легче ориентироваться в этих этапах, я написал интерфейс на WinForms.

  • Слева вверху текстовое поле, в которое вводится образец квайна со всеми маркерами. Их призвание рассматривается ниже. Первые четыре этапа выполняются именно в этом поле.
  • Слева внизу разные параметры и кнопки для выполнения вышеупомянутых этапов. Также код образца либо результирующего квайна дозволено сразу же проверить на ошибки с поддержкой компиляции.
  • Справа вверху поле, которое заполняется кодом квайна, сгенерированном на последнем этапе.
  • Справа вверху внизу поле, в которые выводятся выводится дальнейшая итерация квайна позже компиляции. Также кнопка «Console Output -> Output» с числом итераций необходима для того, Дабы зациклить процесс компиляции квайна и увидеть покадровую анимацию (ну либо что-то еще).

Для подсветки C# синтаксиса применялся компонент BigObfuscator FastColoredTextBox. К сожалению, он работает достаточно медлительно, так что результирующий «фильм» комфортней глядеть через обыкновенную консоль (правда в ней, к сожалению, тоже не дюже стремительно).

Образец квайна

Образец является начальной точки такого трудного квайна, и он может выглядеть дальнейшим образом:

Образец квайна

using System;
using System.Text;
using System.Collections.Generic;

namespace Asciimation_1_3
{
    class Program
    {
        /*#Asciimation_1_3*/
        /*Asciimation_1_3#*/

        /*#DecodeBase64*/
        /*DecodeBase64#*/

        /*#HuffmanTree*/
        /*HuffmanTree#*/

        /*#HuffmanRleDecode2*/
        /*HuffmanRleDecode2#*/

        /*#Enums*/
        /*Enums#*/

        /*#Utils*/
        /*Utils#*/

        static string Data = /*%Data_1_3*/""/*Data_1_3%*/;
        static int CurrentFrame = /*$CurrentFrame*/0/*CurrentFrame$*/;

        static void Main()
        {
            var output = Decompress_v_1_3(Data, CurrentFrame  );
            if (CurrentFrame == 3591)
                CurrentFrame = 3590;
            /*$@$*/
        }
    }
}
/*$Output_1_3$*/

Как видим, в вышеупомянутом коде куча непонятных комментариев. Но на самом деле они являютсямаркерами, обозначающими куда должен вставляться определенный код либо данные. Превосходством такого подхода является то, что код может вставляться из других полных версий классов, а их, в свою очередь, дозволено тестировать (у меня применяется NUnit). Данные маркеры я систематизировал дальнейшим образом:

  • /*#…*/… /*…#*/ — Код. Участки кода между этими маркерами ищутся по файлам из указанной директории.
  • /*%…*/… /*…%*/ — Данные. Между этими маркерами вставляются сгенерированные с поддержкой определенных способов данные, которые обязаны быть представлены в строковой форме (ну т.е. обыкновенная строка, массив строк, массив байт, целых чисел и т.д.). Вообще говоря, из маркеров данных дозволено извлекать информацию о способе, искать его в скомпилированной сборке и вызывать его с поддержкой рефлексии. Но я решил пока что ограничиться ручным вызовом надобных способов, потому что это больше многофункциональный подход (так легче портировать на другие языки).
  • /*$…*/… /*…$*/ — Параметры. Данные маркеры обозначают код, тот, что меняется при всякой дальнейшей итерации отображения квайна. Они указываются в особой таблице, в которой указывается код для замены. В данном случае параметрами являются номер нынешнего кадра (он инкрементируется всякий раз) и поле итога кадра внизу, реализованное с поддержкой однострочных комментариев. Некоторые параметры являются интронами, т.е. строчками, которые не влияют на код в дальнейшей итерации. В данном случае интроном является поле итога.
  • /*@*/ — Печать. Это особый маркер, в тот, что собственно вставляется код для итога каждого квайна. Он существует только в единичном экземпляре. Замена происходит в самом конце, позже генерации кода и данных на предыдущих этапах. Значимо подметить, что для предотвращения дублирования сегменты данных (Дабы не печатать их в самом квайне и в данной строчке), на данном этапе происходит замена не на сами данные, а на параметры (т.е. взамен «asdf», содержащейся в output, выводится ‘”‘ output ‘”‘).

Таким образом, совмещая информацию об этапах и маркерах, дозволено возвести следующую графическую схему:

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

Подробнее о всех этапах расписано ниже.

Генерация кода

При генерации кода анализируется все файлы начальных кодов из указанной папки. И код между маркерами/*#…*/… /*…#*/ копируется в соответствующие места в начальном образце. Скажем, в дальнейшем примере класс HuffmanRle2 целиком копируется в участок между/*#HuffmanRleDecode2*//*HuffmanRleDecode2#*/. Для того, Дабы игнорировать некоторые фрагменты кода внутри этих маркеров (скажем, способы .ToString() не необходимы в квайне, они необходимы для отладки) и не разбивать данный фрагмент на два, были введены маркеры /*#Ignore*//*Ignore#*/, которые разрешают игнорировать каждый код внутри них.

Пример маркеров в начальном коде

/*#HuffmanRleDecode2*/

public class HuffmanRle2
{
	public static byte[] Decode(HuffmanTree tree, byte[] bytes, ref int curBit, int bytesCount, int bitsCountPerRepLength = 8, int bitsCountPerNotRepLength = 8)
	{
		int minLength = Math.Min(bitsCountPerRepLength, bitsCountPerNotRepLength);
		var maxCount = 1 << (minLength - 1);

		var root = tree.Root;
		var result = new List<byte>(bytes.Length * 2);

		int curBytesCount = 0;
		int i = 0;
		while (curBytesCount < bytesCount)
		{
			var length = Utils.GetInt(bytes, ref curBit, minLength);

			if ((length & maxCount) == 0)
			{
				curBit -= minLength;
				length = Utils.GetInt(bytes, ref curBit, bitsCountPerRepLength);
				var repeatCount = length   2;
				byte value = Utils.GetValue(root, bytes, ref curBit);
				for (int j = 0; j < repeatCount; j  )
				{
					result.Add(value);
					curBytesCount  ;
				}
			}
			else
			{
				curBit -= minLength;
				length = Utils.GetInt(bytes, ref curBit, bitsCountPerNotRepLength);
				var notRepeatCount = (((1 << (bitsCountPerNotRepLength - 1)) - 1) & length)   1;
				for (int j = 0; j < notRepeatCount; j  )
				{
					byte value = Utils.GetValue(root, bytes, ref curBit);
					result.Add(value);
					curBytesCount  ;
				}
			}
			i  ;
		}

		return result.ToArray();
	}
}

/*HuffmanRleDecode2#*/

Невзирая на то, что собранный из различных файлов код, может оказаться не оптимальным с точки зрения критерия минимальной длины, т.к. он писался все же в стандартном жанре, такой подход дозволил написать и прогнать тесты (NUnit) для сжатия и извлечения данных квайна непринужденно перед его генерацией, что упрощает процесс разработки и делает его менее изнурительным. Правда минификация кода, которая описана дальше, разрешает фактически нивелировать недочет такого подхода.

Генерация данных

Для сжатия данных применялись самые примитивные алгорифмы сжатия без потерь, такие как RLE и кодирование Хаффмана. Впрочем данную анимацию, как и всякий фильм, дозволено разбить на основные и промежуточные кадры. Промежуточные кадры содержат информацию, которая изменилась с прошедшего кадра, а основные — всю информацию о кадре. Таким образом, Дабы получить все символы промежуточного кадра, нужно раскодировать все предыдущие кадры до основного, а позже этого рендерить все кадры до нынешнего с учетом полученных изменений. Получилось этакое псевдо-MPEG. Конструкция основного и промежуточного кадров представлена ниже. Помимо обыкновенных и промежуточных кадров, я решил еще включить промежуточные кадры, полученные путем смещения налево, вправо, вверх и вниз, так как они встречаются не так уж и редко.

Frame:
0..3 — type:

  • 000 — base:
    3..13 — chars count
    13… — huffman rle codes
  • 001 — left:
    010 — top:
    011 — right:
    100 — bottom:
    101 — changed:
    3..10 — changes count
    10… — changes

Change:
0..2 — type:

  • 00 — one char:
    2..12 — position
    12… — huffman code
  • 01 — line horizontal:
    2..12 — position
    12..19 — chars count
    19… — huffman codes
  • 10 — line vertical:
    2..12 — position
    12..16 — chars count
    16… — huffman codes

К сожалению, финальное сжатие получилось не таким огромным, как хотелось бы, но абсолютно приемлемым. А хотелось бы на ярусе lzma в 7-zip, т.е. поменьше 100 Кб. Скорее каждого, с поддержкой больше продвинутых способов (интервального кодирования, словарных способов), удалось бы достичь еще большей степени сжатия.

Минификация кода

Минификация необходима для того, Дабы уменьшить размер кода в текстовом формате. Для обработки C# кода применялась библиотека NRefactory. Ее превосходством перед Roslyn является то, что дерево разбора дозволено изменять в процессе, что требуется в задачи минификатора.

Укорочение имен классов, способов, полей, локальных переменных

Самой основной задачей минификатора являлся именно данный этап. Для обхода построенного синтаксического дерева применялся паттерн «Посетитель» (Visitor), реализованный в виде перегрузки необходимых способов обхода узлов при обходе в глубину.

Для того, Дабы с одной стороны применять минимальное число идентификаторов, а с иной — Дабы они не пересекались и не приводили к ошибкам компиляции, алгорифм укорочения был разбит на следующие этапы:

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

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

Стоит подметить, что библиотека поддерживает игнорируемые идентификаторы, т.е. такие, которые по каким-то причинам не обязаны быть укорочены, что применяется в данном плане (параметры квайна).

Для приобретения списка всех ссылок на используемые идентификаторы (Find All References в Visual Studio), применяется механизм ресолвинга NRefactory. Для этого вначале нужно откомпилировать дерево (на всяком этапе: локальные переменные, члены типов, типы):

var unresolvedFile = SyntaxTree.ToTypeSystem();
var projectContent = projectContent.AddOrUpdateFiles(_unresolvedFile);
var compilation = projectContent.CreateCompilation();
var resolver = new CSharpAstResolver(_compilation, SyntaxTree, _unresolvedFile);

Позже чего дозволено искать ссылки дальнейшим образом:

var resolveResult = resolver.Resolve(node);
var findReferences = new FindReferences();
...
findReferences.FindLocalReferences();
...
findReferences.FindReferencesInFile();
Другие минификации

Также были реализованы следующие небольшие минификации:

  • Удаление ключевого слова private
  • Удаление пространств имен
  • Сокращение выражения инициализации переменных:
    • List<byte> a = new List<byte>() => var a = new List<byte>()
    • var a = new b() => b a = new b()

    Примечание: такую замену дозволено исполнить и с поддержкой шаблонного поиска, описанного в статье:
    Using NRefactory for analyzing Csharp code

  • Удаление фигурных скобок, внутри которых только одно выражение: if (a) { b; } => if (a) b;
  • Сокращение записи сопоставления с булевым типом: if (a == true) => if (a); if (a == false) => if (!a)
  • Удаление регионов и комментариев.
Удаление пробельных символов и переносов строк

Позже того, как всевозможные минификации сделаны, из кода остается удалить только лишние пробельные символы и переводы, причем таким образом, Дабы длина строк не превышала определенного значения (для красоты).

Минификатор реализован отдельным планом и его и дозволено скачать тут: CSharp-Minifier. Он в первую очередь разрабатывался с нацелом на сокращения кода в квайнах, следственно нет ничего изумительно в том, что он владеет немножко необычной функциональностью. Однако, я с радостью приму ваши примечания и/или пулл-риквесты.

Форматирование кода

На данном этапе минифицированный код дозволено привести к виду, Дабы он был схож на какую-нибудь картинку. Форматирование идет именно позже минификации, потому что сгенерированный код представляет собой в основном массив единичных символов (их дозволено разрывать), из которых легче строить картинку. Картинка должна иметь только черно-белый формат, Дабы символ представлял белый пиксель, а черный — его неимение. Для лучшего соответствия дозволено применять какие-либо эвристические переборные алгорифмы (генетические).

У меня форматирование реализовано не было.

Генерация квайна

В качестве маркера, куда необходимо распечатать итоговую строку квайна, применялся дальнейший: /*@*/
Поэтапно все выглядит дальнейшим образом. Каждый код может быть абсолютно произвольным, но в примере переносы строк добавлены для лучшей читабельности.

  1. Инициализация образца:
    template =

    class P
    {
    	static void Main()
    	{
    		var a = 6;
    		/*@*/
    		int b = 10;
    	}
    }
    
  2. Генерация образца строки, применяемой для печати квайна. Кавычки, обратные слеши и переносы строк нужно экранировать, так что их представление идет отдельными параметрами при выводи форматированной строки.
    kernel = "var s = {1}{0}{1}; System.Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});"
  3. Замена в образце маркера на строку, используемую для печати из предыдущего этапа. Т.к. в C# при итоге параметров применяются фигурные скобки, то их также нужно экранировать. Это делается путем их дублирования.
    str = template.Replace("{", "{{").Replace("}", "}}").Replace("/*@*/", kernel)
    str =

    class P
    {{
    	static void Main()
    	{{
    		var a = 6;
    		var s = {1}{0}{1}; System.Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});
    		int b = 10;
    	}}
    }}
    
  4. Генерация результирующей строки, применяющейся для печати квайна:
    insertToResult = "var s="" str """
    insertToResult =

    var s="
    class P
    {{
    	static void Main()
    	{{
    		int a=6;
    		var s={1}{0}{1}; Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});
    		int b=10;
    	}}
    }}";
    Console.Write(s,s,'"', '\', "rn");
    
  5. Замена маркера в начальном образце на получившуюся строку:
    result = template.Replace("/*@*/", insertToResult)
    result = 

    using System;
    class c
    {
    	static void Main()
    	{
    		int a=6;
    		var s="using System;class c{{static void Main(){{int a=6;var s={1}{0}{1};Console.Write(s,s,'{1}','{2}{2}',{1}{2}r{2}n{1});int b=10;}}}}";
    		Console.Write(s,s,'"', '\', "rn");
    		int b=10;
    	}
    }
    

Готово: получена программа, которая может печатать сама себя.
Описанный подход дозволено обобщить и до генерации квайнов-палиндромов, но я пока что это не реализовывал.

Запуск

Позже того, как квайн сгенерирован, его дозволено скажем сберечь в файл Asciimation.cs и вывести один кадр дальнейшей командой:
"C:WindowsMicrosoft.NETFramework64v4.0.30319csc.exe" Asciimation.cs && (Asciimation > Asciimation.cs) && Asciimation

А Дабы посмотреть каждый сгенерированный «фильм», необходимо воспользоваться дальнейшим скриптом:

echo off
SET /a i=0
:LOOP
IF %i%==3591 GOTO END
"C:WindowsMicrosoft.NETFramework64v4.0.30319csc.exe" Asciimation.cs && (Asciimation > Asciimation.cs) && Asciimation
SET /a i=%i% 1
GOTO LOOP
:END
pause

Завершение

Описанные в статье тезисы применимы и в случае реализации разных квайнов на других языка программирования. К сожалению, с поддержкой онлайн сервисов (ideone.comcompileonline) протестировать разработанный код невозможно, потому что он все равно превышает максимально возможный размер, невзирая на компрессию.

Сгенерированные файлы и батники дозволено скачать тут: AsciimationQuine_1_3.7z.
В перспективе дозволено испробовать заняться цепными квайнами и, допустимо, повторить подвиг Yusuke Endoh, только теснее не вручную, а с механической генерацией.

Благополучным вам фрик-исходников в классном смысле.

Источник: programmingmaster.ru
Оставить комментарий
Форум phpBB, русская поддержка форума phpBB
Рейтинг@Mail.ru 2008 - 2017 © BB3x.ru - русская поддержка форума phpBB