AskePit 21 ноя в 21:00

constexpr Game of Life

Средний

20 мин

19K

Ненормальное программирование*C++*Python*

Туториал

С чего все началось

В C++ уже больше 10 лет существует constexpr, который позволяет программисту ушло возложить часть вычислений на компилятор. В свое время это взорвало мне мозг, ведь компилятор может посчитать какие-то достаточно сложные вещи еще до запуска программы!

В какой-то момент я подумал: если компилятор сможет сам посчитать все за тебя, то зачем тогда тебе вообще рантайм? Что ты там будешь делать — ответ выводить что ли? Глупости какие-то. Это неспортивно.

На этом моменте и зародился мой челлендж:

"Без рук" или "даже не думай запускать exe-файл"

Ставим себе задачу

Для ясности озвучим основную идею еще раз: хочется написать программу и собрать ее компилятором. Подразумевается, что все вычисления будут сделаны на этапе компиляции. Запускать программу не хочется. Но код должен работать. Взаимоисключающие параграфы? Возможно. Но сделать надо.

Отягчающие: я программист-виндузятник. Срачи на эту тему мы сможем лицезреть в комментариях. Для меня же это означает, что мы будем иметь дело с сущностями специфичными для Windows: компилятор для Visual Studio, cmd, bat, exe и все остальные кошмары линуса. Это в том числе подкинет нам дополнительных трудностей, но я только за.

Программа должна выполнять что-то вразумительное и полезное. Набившие оскомину примеры с вычислением факториала или чисел Фибоначчи мы рассматривать не будем как пошлые, не несущие полезной нагрузки и не бросающие вызов. Заставлять компилятор играть в Doom я тоже, пожалуй, не стану. И дело скорее не в том, что компилятор такое не вывезет — такое скорее не вывезу я.

В итоге я решил остановиться на чем-то среднем — мы-таки заставим компилятор играть, но во что-то существенно более простое. Например, в Game of Life. Ведь даже если Google на своей поисковой странице может себе позволить запустить эту симуляцию, то почему я не могу тоже самое заставить делать C++-компилятор?

Для непрошедших по ссылкам, но незнакомых с этой "игрой" оставлю здесь анимацию:

Освежим в голове правила Game of Life:

Если ячейка жива, и у нее меньше двух соседей, она умирает
Если ячейка жива, и у нее больше трех соседей, она умирает
Если ячейка пустая, но у нее три соседа, в ячейке зарождается жизнь
И так поколение за поколением до бесконечности

"Но падажжи" — скажете вы, — "Game of Life — это игра. У нее должны быть кадры, main loop, бесконечное исполнение, отрисовка, в конце концов, а ты втираешь нам какую-то дичь про compile-only". Отчасти справедливо, но я в своем челлендже оставляю себе большое пространство для маневра, поскольку единственное, чего нельзя делать — это запускать исполняемый файл (ни прямо, ни косвенно). В остальном можно делать все, на что нам хватит фантазии. И тут уж нам надо будет проявить себя по полной.

Нюансы constexpr

Давайте сразу оговоримся про языковые тонкости. C++ дает возможность пометить функцию или метод как constexpr. Но это не дает вам никаких гарантий на исполнение в compile-time. Если в функцию будут переданы не-constepxr параметры, то ваша пометка constexpr будет тихо проигнорирована, и вы даже не узнаете об этом.

Смотрите, вот этот код произведет вычисление на этапе компиляции:

constexpr int twice(int n)
{
    return n * 2;
}

int main()
{
    return twice(17);
}

Программа завершится с кодом 34, при этом 17 * 2 будет посчитан еще на этапе сборки программы, и в бинарник запишется просто результат 34.

Мы сейчас говорим про вещи в вакууме, поэтому опустим тот момент, что компилятор в состоянии самостоятельно свернуть такое тривиальное умножение даже без собственно упоминания constexpr. Для простоты теоретизирования представим, что компилятор без constexpr так делать не станет.

А теперь давайте сделаем так, что программу будет невозможно вычислить в compile-time:

constexpr int twice(int n)
{
    return n * 2;
}

int main()
{
    int n;
    std::cin >> n;
    return twice(n);
}

Теперь код возврата зависит от ввода пользователя, и полномочия компилятора в вычислении результата в compile-time тут — всё. Тем не менее этот код компилируется и запускается. Т.е. функция twice может легально использоваться и в compile-time и в runtime контекстах.

Правда, это не значит, что можно в принципе любую функцию обмазывать constexpr просто на всякий случай. Стоит добавить в функцию что-то несовместимое с compile-time only, как мы получаем ошибку компиляции:

constexpr int twice(int n)
{
    std::cout << n * 2 << std::endl;
    return n * 2;
}

При попытке собраться получаем:

error C3615: constexpr function 'twice' cannot result in a constant expression

Окей, а если я хочу гарантировать, что моя функция всегда-всегда выполняется только в compile-time контексте? Для этого есть, например, проверялка std::is_constant_evaluated из C++20. Это constexpr-функция, которую можно запустить внутри constexpr-функции, чтобы проверить, находимся ли мы сейчас реально в constexpr-контексте или мы даунгрейднулись до рантайма. Ну вы поняли — комитет по стандартизации языка любит сложности.

В нашем случае нам необходимо гарантировать, что мы работаем в compile-time контексте. Любое отклонение от этого курса было бы строго желательно сопровождать ошибкой компиляции. И да, можно было бы как-то обмазаться constexpr и std::is_constant_evaluated, но тот же комитет по стандартизации подарил нам в том же C++20 новый спецификатор consteval, который суть constexpr на максималках. Им можно пометить метод, который предназначен исключительно для выполнения компилятором. А потому любые подозрения, что метод пробуют использовать в рантайме, выльются в праведную ошибку компиляции. И это то, что нам нужно — строгие гарантии, что потеть будет exe-шник компилятора, а не наш exe-шник.

В статье будут использоваться фишки С++20, если понадобится, то и C++23. Да, не только лишь все смогут использовать эти чудеса на продакшене, но что поделать — такова жизнь плюсовика.

Начинаем писать Game of Life

Давайте сначала просто начнем писать код, не заботясь о consteval и прочем. А там разберемся по ходу дела.

Итак, нам нужен канвас определенного размера. Я выбираю 16x16. Позже вы поймете, почему именно такой размер, и оцените смекалочку.

Ненормальное программирование начинается здесь:

#include <array>

constexpr bool _ = false;
constexpr bool X = true;

constexpr size_t N = 16;
using Canvas = std::array<std::array<bool, N>, N>;

constexpr Canvas life {{
	{_,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
	{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,},
}};

int main()
{
    return life[0][1];
}

Сам же сказал, что пока не буду заботиться о compile-time, и сам же все обмазал constexpr. Ну, простите, не удержался. Вычислений пока нет, но я уже постелил соломку.

Что мы тут сделали: ввели двумерную сущность канваса Canvas и объявили стартовый кадр игры life, на который помещена любопытная фигура, Glider. В Game of Life она ведет себя как вращающийся движущийся объект, более-менее сохраняющий свою форму в некотором периоде. Проще показать:

На такой фигуре будет легко проверить правильность написания логики игры — фигура должна каждый кадр идти по диагонали вниз и вправо.

Предвижу вопрос, который у кого-то может встать: зачем я сделал return life[0][1];? Без этой строчки компилятор решит, что все наши переменные были объявлены зазря и просто вырежет вообще все из бинарника.

А еще по адресу [0][1] лежит живая ячейка, поэтому программа по завершению запуска должна вернуть 1. Правда, вот самого запуска никогда не случится, лол — не забываем про основное правило челленджа!

Но вообще нам и запускать-то пока нечего, ведь мы даже еще не скомпилировались.

Запускаем компилятор

Помним — мы на Windows, и наиболее логичный компилятор, который нам доступен — это компилятор, который использует Visual Studio — Microsoft Visual C++ или MSVC. В качестве бинарника известен под именем cl.exe.

Использовать саму Visual Studio в качестве IDE мы не хотим — ведь это для слабых духом. Нас интересует использование cl.exe напрямую. И тут всплывает первый же нюансик. В Linux я могу просто открыть терминал и тут же запустить gcc.exe для своих грязных делишек. Если же вы в свежеоткрытом cmd наберете cl /help, вы получите:

'cl' is not recognized as an internal or external command,
operable program or batch file.

По умолчанию окружение шелла не настроено на работу cl из коробки, а в PATH даже не прописан путь до него. И это так и задумано. Вот развесистая документация про то, как просто запустить чертов cl.

TL;DR: чтобы трогать визуальный компилятор голыми ручками сперва нужно настроить окружение шелла, и сделать это можно почти десятком способов в зависимости от желаемой разрядности и платформы. На каждый вариант окружения есть свой .bat-файл. Первое правило гигиены компиляторопользования в Windows: сперва запускаешь батник с окружением, затем используешь cl.

Вот так работает:

"C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvars64.bat"

cl /help

Здесь мы использовали батник для x64-native tools, он нам подходит.

Знаете все эти терминалы x64/x86 Native Tools Command Prompt for VS2022? Это по сути преднастроенные шеллы, где cl.exe можно запускать сразу из коробки. Такой вариант мы тоже отметаем, потому что хотим запуститься из любого голого терминала.

На данном этапе для компиляции нам подходит такая команда:

cl /std:c++latest main.cpp

Ее исполнение показывает, что наша заготовка успешно компилируется, а потому мы можем продолжить написание кода.

Натягиваем сову на compile-time

Итак, с расчехленным компилятором наготове продолжаем вымучивать Game of Life.

На деле вся вычислительная часть для нашей симуляции до боли примитивна: вы берете старый Canvas, от него по правилам игры высчитываете новый Canvas, как-то его отрисовываете/отображаете и повторяете так до бесконечности — вот и вся программа. Краеугольным камнем в этом алгоритме будет функция с сигнатурой Canvas update(Canvas old), считающая следующее поколение клеток:

consteval Canvas update(Canvas old)
{
    Canvas res;

    for (int r = 0; r < N; ++r) {
        for (int c = 0; c < N; ++c) {

            int neighboursCount = 0;
            for (int nr = r - 1; nr <= r + 1; ++nr) {
                for (int nc = c - 1; nc <= c + 1; ++nc) {
                    if (nr == r && nc == c) continue;
                    
                    int wrappedR = (nr + N) % N;
                    int wrappedC = (nc + N) % N;
                    neighboursCount += static_cast<int>(old[wrappedR][wrappedC]);
                }
            }

            const bool isAlive = old[r][c];
            res[r][c] = neighboursCount == 3 || (isAlive && neighboursCount == 2);
        }
    }

    return res;
}

Фактически вся суть и логика игры умещается в строчке res[r][c] = neighboursCount == 3 || (isAlive && neighboursCount == 2);. Остальной код — сканирование клеток и их соседей.

Заметьте, что я сделал wrapping канвасу. Т.е. если живая клетка "ушла" за экран справа, она оказывается на экране слева. Это сделано, чтобы кипящая на небольшом канвасе жизнь с меньшей вероятностью вырождалась в ничто, а могла самоподдерживаться как можно дольше.

Я под шумок приписал к функции consteval, и компилятор на меня даже не ругнулся. Да, вот так просто — он согласен считать это в compile-time! И циклы, и ветвления, и создание новой переменной — все-все эти роскошества нам доступны. Беззубый constexpr из далекого C++11 не умел ни в циклы, ни в локальные переменные, требовал одного-единственного return, и давал возможность делать ветвление только с помощью тернарного оператора. Памятуя все это я пребываю под впечатлением от текущих возможностей compile-time вычислений в языке.

Теперь создадим переменную, в которой будет лежать второе поколение клеток:

constexpr Canvas newLife = update(life);

Ну и наш трюк с использованием этой переменной, чтобы компилятор не вырезал все к чертям:

int main()
{
    return newLife[0][0];
}

Теоретически у нас на руках теперь есть посчитанный на этапе компиляции второй кадр игры. Остается лишь понять, как его увидеть.

Пытаемся выудить информацию

Как же нам получить результат работы после завершения работы компилятора? Первое, что мне пришло в голову — заставить компилятор помимо бинарника сгенерировать asm-листинг и посмотреть туда. Там определенно должен лежать наш посчитанный второй кадр в виде константы. Ну, еще мы могли бы парсить exe-файл — там тоже эта константа должна быть в каком-то виде, вот только парсить бинарный файл со сложной структурой попахивает безумием.

Ассемблер

Чтобы получить asm-файл компилятору нужно указать флаг /Fa. Чтобы файл не был сильно раздутым мы ко всему прочему попробуем применить максимальный уровень оптимизации, при этом скрестив пальцы, чтобы оптимизатор не сильно почикал наш искомый кадр. Для оптимизации добавим флаг /O2. Итого запускаем команду:

cl /std:c++latest /Fa /O2 main.cpp

Теперь помимо main.exe мы получаем файл main.asm. Посмотрим внутрь, а там до непосредственных ассемблерных опкодов идет секция с объявлением константных данных, где мы видим наш знакомый newLife в виде набора 256 чисел. Листинг привожу кусочно:

CONST	SEGMENT
?newLife@@3V?$array@V?$array@_N$0BA@@std@@$0BA@@std@@B DB 00H ; newLife
	DB	00H
...
	DB	00H
	DB	01H
	DB	00H
	DB	01H
	DB	00H
...
	DB	00H
	DB	01H
	DB	01H
	DB	00H
	DB	00H
...
	DB	00H
	DB	00H
	DB	00H
	DB	00H
	DB	01H
	DB	00H

...

Я скопировал этот массив данных и подшаманил с ним в блокноте, чтобы привести кадр в читабельное состояние:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Ну как — похоже на второй кадр ползущего по диагонали Glider'а? Вроде бы похоже! Я провернул такую же схему для третьего и четвертого кадра:

constexpr Canvas third = update(update(life));
// и
constexpr Canvas fourth = update(update(update(life)));

Получил следующие "изображения":

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 1 1 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Сомнения отпали — это наш Glider, а значит кадры Game of Life просчитывается корректно.

Бинарный файл

Теперь попробуем сунуть руки в бинарный файл и найти там те же данные, что мы имеем в asm-листинге.

Для этого придется хотя бы поверхностно понимать структуру exe-файла. Я этими знаниями не обладал, но по счастью знал, где могу легко и недушно их обрести — я помнил, что у Alek OS на Youtube был видос, где он как раз объяснял формат виндового бинарника. Алекса, между прочим, очень рекомендую всем — его видео закрыли мне не один пробел в общих знаниях, которые пригодятся любому программисту.

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

Массив нашего кадра нужно искать в .rdata-секции бинарника. Здесь лежат все read-only данные.

Хедер, объясняющий, куда идти за .rdata секцией, находится практически в начале файла:

На изображении мы видим начало exe-файла в hex-редакторе. Желтый — 8 байт, выделенных под надпись .rdata. Через 12 байт от желтой области мы выходим на информацию о месте начала .rdata-секции в файле; выделено красным. Это little-endinan, поэтому из 00 F0 00 00 получаем смещение 0xF000.

Идем прямиком туда и смотрим:

Хм, ничего похожего наш массив не видно. В отчаянии прокручиваем чуть ниже:

А вот и оно! Наш Glider из смайликов видно буквально сразу, его трудно перепутать с чем-то еще в этом ворохе бинарного шума. Far3, которым я просматриваю потроха exe показывает бинарный файл строками по 16 байт, и вуаля — наша матрица 16x16 шикарно читается даже в голом бинаре!

Какие именно данные в .rdata-секции лежат до нашего массива, мне понять не удалось. По какому принципу наш массив положили именно в этом месте в .rdata-секции, я тоже не понял. Скорее всего просто потому что положили сюда и все тут.

Зато я обнаружил, что как ни компилируй, массив всегда кладется в 0x320-ый байт от начала .rdata-секции (или 0xF320-ый байт от начала файла). Да, это магическое число зависит от фазы луны и настроения компилятора. Зато, пока мой массив лежит там, я могу распарсить бинарник и достать оттуда ответ вычисления constexpr-программы!

Распаршенный бинарник круче распаршенного asm-текста, поэтому остановимся на выуживании информации из него.

Как будем оживлять игру

А теперь внимательно следите за руками, ненормальное программирование продолжается здесь.

Скопируем тело нашего массива life в файл life.txt:

{_,X,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,X,_,_,_,_,_,_,_,_,_,_,_,_,_},
{X,X,X,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},
{_,_,_,_,_,_,_,_,_,_,_,_,_,_,_,_},

А в плюсовом коде сделаем включение достойное хакеров:

constexpr Canvas life {{
    #include "life.txt"
}};

Отныне считаем, что файл life.txt — это наше "рендер-окно". Ну, и как вы смогли заметить, по совместительству этот файл одновременно является частью C++-кода.

Наш хитрый план заключается в следующем:

Компилируем программу
Парсим exe на предмет нового кадра Game of Life
Записываем новый кадр обратно в life.txt
Повторяем, пока не надоест

Заскриптовать данное решение в бесконечном цикле мы легко сможем тем же питоном.

Блеск и нищета идеи заключается в том, что если при запущенном скрипте смотреть на life.txt в любом текстовом редакторе, который умеет в обновление контента на лету, то мы собственно сможем наблюдать Game of Life в динамике! Еще и в ASCII графике. Я бы даже сказал, в C++-syntax графике, ибо этот контент при этом при всем остается исходным C++-кодом. C++-кодом, который мутирует каждый кадр вместе с игрой. Ну просто эволюционное программирование какое-то.

Пишем main loop

Тут статья делает резкий языковой поворот и превращается из статьи, посвященной C++, в статью про Python.

Ну а еще кто-то может резко возмутиться, ведь я фактически мухлюю у вас на глазах и, показательно избегая рантайма в C++, вместо этого убегаю в рантайм на Python. Не лишено правды, но скомпилированный exe я-таки действительно не запускаю, а потому формально условия челленджа не нарушаются.

Итак, накидаем схему нашего игрового цикла:

def update():
    compile_cpp()
    life = parse()
    render(life)

def main():
    while True:
        update()
        time.sleep(0.25)

if __name__ == "__main__":
    main()

Здесь все несложно — в бесконечном цикле с некоторой задержкой долбим update(), который воплощает описанную нами выше последовательность из компиляции, парсинга и "рендеринга".

Все, что нам остается — реализовать методы compile_cpp, parse, render.

Компилируем C++

Первое, что нам нужно научиться делать — запускать cl.exe в Python-скрипте. Помним, что это не так просто, и предварительно нам нужно настроить окружение. Поэтому мы сперва запускаем батник, потом компилятор:

def compile_cpp():
    ENVIRONMENT_SETUP = r'"C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvars64.bat"'
    
    COMPILE = 'cl /std:c++latest /O2 main.cpp'

    os.system(f'{ENVIRONMENT_SETUP} && {COMPILE}')

Заметьте, что я был вынужден склеить две команды в одну через &&, чтобы пропихнуть их в один вызов os.system. Проблема тут в том, что каждый вызов os.system — это запуск нового шелла, т.е. между вызовами os.system не сохраняется контекст и окружение. Поэтому, раздели я код на две команды, я получил бы жалобу в духе "я не знаю, кто этот ваш cl. а то, что вы настраивали в предыдущем os.system остается в предыдущем os.system".

Парсим бинарник

Теперь, после успешной компиляции, попробуем распарсить exe-файл и удостовериться, что все искомые данные действительно парсятся и изымаются.

N = 16

with open('main.exe', 'rb') as f:
    f.seek(0xF320)
    for r in range(N):
        for c in range(N):
            print(int.from_bytes(f.read(1)), end=' ')
        print()

Получаем:

0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
1 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0
0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0

Все в порядке, бинарник парсится, магическое смещение все еще работает. Значит можно зафиналить:

def parse():
    life = []

    with open('main.exe', 'rb') as f:
        f.seek(0xF320)

        for r in range(N):
            life.append([])
            for c in range(N):
                cell = int.from_bytes(f.read(1))
                life[r].append(cell)
    
    return life

Рендер в life.txt

Тут главное не испортить C++ синтаксис, иначе следующего кадра мы не получим из-за ошибки компиляции плюсового кода на следующей итерации update():

def render(life):
    with open('life.txt', 'w') as f:
        for r in range(N):
            f.write('{')
            for c in range(N):
                cell = 'X' if life[r][c] == 1 else '_'
                f.write(f'{cell},')
            f.write('},\n')

Любуемся результатом

Это ли не чудо:

constexpr-only
мутация исходного кода
исходный код как визуальный контент
не запуская бинарник

Борьба за FPS

Можно сказать, что мы добились, чего хотели — у нас есть симуляция Game of Life, вычисляемая C++-компилятором. Но для полного удовлетворения я хочу устранить еще несколько проблем нашего решения.

Первое, что сразу бросается в глаза — это низкий FPS. По ощущениям что-то около 1 кадра в секунду. С одной стороны, чего я еще хотел — каждый кадр игры с нуля запускается компилятор, которому нужно отработать весь его стандартный цикл парсинга, оптимизаций и генерации кода. Помните, у меня в main-loop был time.sleep(0.25)? Это я явно погорячился, и уже давно успел его выкинуть — анимация выше представлена уже без этой задержки. А цифра FPS-таки все равно крайне мала.

Вспоминаем, что наш скрипт каждый кадр вынужден запускать bat-файл для настройки шелл-окружения. По моим эмпирическим прикидкам этот шаг должен занимать как минимум половину всего рабочего времени, поэтому нам необходимо решить эту проблему и дать возможность скрипту запускать батник один раз на старте и как-то запомнить приобретенный контекст. Хмм, снова хотелки в стиле:

Итак, использование os.system не дает нам запоминать настройки окружения шелла. Я не специалист по Python, но документация, приведенная в docs.python.org утверждает, что если вам не хватает возможностей os.system, то вы можете использовать subprocess.run.

Проявив слабохарактерность и лень, я пошел к ChatGPT, и он подобрал мне решение с использованием subprocess.run, возможно говнокодерское, но тем не менее рабочее.

Ключевая идея: через subprocess.run мы вызовем наш батник + команду set:

"C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvars64.bat" && set

Что делает команда set? Если ее вызвать без аргументов, она просто выведет в stdout список всех текущих переменных окружения шелла. Примерно так:

$ set
HISTFILE='/root/.ash_history'
HOME='/root'
HOSTNAME='localhost'
IFS=' '
LINENO=''
OLDPWD='/'
OPTIND='1'
PAGER='less' PATH='/usr/local/sbin:/usr/local/bin:/usr/sbin:/usr/bin:/sbin:/bin'
PPID='1'
PS1='\h:\w\$ '
PS2='> '
PS4='+ '
PWD='/root'
SHLVL='3'
TERM='linux'
TZ='UTC-01:00' _='--version'
script='/etc/profile.d/*.sh'

Что предлагает ушлый ChatGPT:

Запускаем батник
Запускаем set
Парсим stdout и сохраняем напаршенные переменные в словарик
Вызывать запуск C++-компилятора в цикле мы тоже будем через subprocess.run, у которого как раз имеется опциональный продвинутый аргумент env=, и в него прекрасно вставляется наша мапа, которую мы парсили!

Даже не знаю, насколько тупо это или гениально. Как и все происходящее в статье.

Итого, мы пишем функцию setup(), которую вызовем на старте скрипта:

msvc_env = {}

def setup():
    CMD = r'"C:\Program Files\Microsoft Visual Studio\2022\Community\VC\Auxiliary\Build\vcvars64.bat" && set'
    result = subprocess.run(CMD, stdout=subprocess.PIPE, shell=True)

    for line in result.stdout.decode().splitlines():
        if '=' in line:
            key, value = line.split('=', 1)
            msvc_env[key] = value

А в compile_cpp() заменим os.system на subprocess.run и пропихнем туда наши переменные окружения:

def compile_cpp():
    COMPILE_CMD = 'cl /std:c++latest /O2 main.cpp'

    result = subprocess.run(
        COMPILE_CMD,
        stdout=subprocess.PIPE,
        stderr=subprocess.PIPE,
        shell=True,
        env=msvc_env
    )

Наслаждаемся результатом:

По моим ощущениям это где-то 5 FPS. Против старого результата в 1 FPS. Значит мы не зря старались, а результат ускорился даже не в два раза, а примерно в пять.

Еще можно добавить, что у компилятора есть флаг /MP{n}, который заставляет его работать в несколько потоков, но мои эксперименты показали, что в моем случае выхлоп исчезающе мал.

Compile-time random

Формально у нас есть рабочая версия Game of Life, но она статичная, с одинокой фигурой на канвасе. Хочется же взрывного буйства клеток, которые взаимодействуют друг с другом. Наполнять стартовый кадр вручную — задача муторная, неблагодарная; хотелось бы рандомизировать первый кадр, чтобы каждый запуск имел неожиданный для нас сценарий.

Эти хотелки, в свою очередь, создают нам еще две проблемы, которые придется как-то решать. Во-первых, как сделать рандом в constexpr условиях? Во-вторых, нам как-то нужно объяснить компилятору, что рандомно заполнять канвас нужно только при первой компиляции. Последующие запуски должны отрабатывать симулятивно, как это делается в текущей реализации.

Последнюю проблему мы пока отложим, и займемся вопросом реализации рандома в compile-time.

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

float random (vec2 st) {
    return fract(sin(dot(st.xy,
        vec2(12.9898,78.233)))*u_time*1.0
    );
}

Выглядит сомнительно? Я, пожалуй, не удержусь и допишу шейдер у вас на глазах, для пруфов, что это неплохо работает:

void main() {
    vec2 st = gl_FragCoord.xy/u_resolution.xy;
    
    st *= 10.0;
    st = floor(st);
    
    vec3 back = vec3(0.1, 0.9, 0.5);
    vec3 front = vec3(0.2, 0.2, 0.2);
    
    gl_FragColor = vec4(mix(back, front, random(st)), 1.0);
}

А теперь посмотрите на результат:

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

$R_{n+1}=(R_n*a+b) \bmod m$

Ну или если простым языком, то очередное число в ряду мы:

Перемножим на что-то большое и, желательно, простое
Сложим с чем-то большим и, желательно, простым
Поделим по модулю с чем-то большим и, желательно, простым, а еще лучше — хитро побитово-сдвинутым

Я остановился на:

seq = (110351545 * seq + 12345) % (1 << 31);

Беда лишь в том, что последовательность всегда будет одной и той же, если мы не найдем возможность начинать ее с какого-то рандомного seed'а. Да-да — чтобы реализовать рандом, нам нужен рандом, классика. К слову, в шейдере роль сида играло текущее время.

Я пошел рыскать интернет, и в какой-то момент набрел на GitHub сниппет. Можете не проходить по ссылке, я вам сразу скажу, что главного почерпнул из него — человек использует макрос __TIME__ в качестве сида. Да, тоже время, только в каком-то странном виде.

Вообще этот макрос идет в паре с макросом __DATE__. Оба они работают достаточно любопытно. Вспомним, как работают макросы в принципе: еще до парсинга компилятор сначала запускает препроцессор, который сделает подстановки текста там, где находятся макросы. Только после этого начнется реальная компиляция исходного кода. Вместо __DATE__ и __TIME__ препроцессор подставит в исходный код строковые литералы текущего времени сборки вида "Jan 14 2012" и "22:29:12". Вообще, любопытно осознавать, что с такими макросами в вашем коде до компилятора ваш исходный код доходит каждый раз с немного разным содержимым, поскольку тот же __TIME__ будет раскрываться в разную строковую константу каждую секунду. Правда, мои эксперименты показали, что у макроса __TIME__ подстановка обновляется почему-то каждые 10 секунд, но это может быть спецификой конкретной реализации препроцессора для MSVC. Для наших нужд такая условность не является помехой.

На практике строка прекрасно зашивается даже в asm-файл. Если напишу в C++-коде что-то в духе:

constexpr const char* dd = __DATE__;
constexpr const char* tt = __TIME__;

то в asm-листинге появится вот такой кусок:

;	COMDAT ??_C@_08BCGBJOAF@20?313?330@
CONST	SEGMENT
??_C@_08BCGBJOAF@20?313?330@ DB '20:13:30', 00H		; `string'
CONST	ENDS
;	COMDAT ??_C@_0M@DINKGNNG@Nov?520?52024@
CONST	SEGMENT
??_C@_0M@DINKGNNG@Nov?520?52024@ DB 'Nov 20 2024', 00H	; `string'
CONST	ENDS

Вот я и спалил время написания данной статьи.

Хорошо — как использовать const char* в качестве сида? Захешировать его в число конечно же. Хеш напишем так же самопальный. Вот вам сразу функция, возвращающая consteval seed:

consteval uint32_t seed()
{
    uint32_t hash = 0;

    for (int i : {0, 1, 3, 4, 6}) {
        hash += static_cast<uint32_t>(__TIME__[i]);
    }

    return hash;
}

Почему индексы 0, 1, 3, 4, 6? Если __TIME__ меняется только каждые 10 секунд, то из константы "20:13:30" реально изменяющимися будут только эти индексы. А последний символ под индексом 7 всегда будет неизменным, хотя и не является :.

Итак, комбинируем получившиеся знания и рожаем функцию consteval Canvas random_canvas():

consteval Canvas random_canvas()
{
    Canvas res;

    uint32_t seq = seed();

    for (uint32_t r = 0; r < N; ++r) {
        for (uint32_t c = 0; c < N; ++c) {
            seq = (110351545  * seq + 12345) % (1 << 31);
            res[r][c] = seq % 3 == 0;
        }
    }

    return res;
}

Что такое seq % 3 == 0? Ну, это такой threshold, странная попытка решить, жива клетка или мертва. Не уверен, насколько это нормальное решение, но оно по итогу дало мне хорошие результаты в генерации первого кадра. Например, вот:

{X,X,_,_,X,X,_,_,X,X,_,_,_,_,_,_,},
{_,X,_,_,_,X,X,X,_,_,_,_,_,X,X,_,},
{_,_,_,_,_,_,X,_,X,_,X,_,_,X,X,_,},
{_,X,_,_,_,_,_,_,_,_,_,_,_,_,X,_,},
{_,_,_,X,_,X,_,_,X,_,_,X,X,_,X,X,},
{_,_,_,_,_,_,_,_,_,X,X,_,_,_,_,_,},
{_,_,X,X,_,X,_,X,_,_,_,_,X,X,_,_,},
{_,X,X,_,_,_,_,_,_,_,_,_,X,_,_,_,},
{X,_,X,_,_,X,_,_,X,_,_,X,_,_,_,_,},
{X,_,_,_,X,_,X,_,_,X,X,X,_,X,X,_,},
{_,_,_,_,X,X,_,X,_,X,_,_,_,_,X,X,},
{_,X,_,_,_,X,X,_,X,X,_,X,X,_,_,_,},
{_,_,_,_,X,_,_,X,X,_,_,_,X,_,X,_,},
{_,_,X,_,_,_,_,X,_,_,X,_,_,_,X,_,},
{_,_,_,_,_,_,_,_,X,X,_,_,X,_,_,_,},
{_,X,_,X,_,_,X,_,X,X,X,_,_,X,_,_,},

Я считаю, достойный первый кадр.

Реализовываем условную компиляцию

Последнее препятствие на нашем пути — дать компилятору понять, что ему делать: генерировать первый случайный кадр или симулировать новый кадр на основе предыдущего?

Эта головоломка заняла меня на некоторое время, поскольку уложить в голове, как C++ код сможет понять, что его запустили в первый раз, а не во второй, мне поначалу было непросто. А потом я вспомнил, что это C++, и здесь можно обмазываться макросами до потери пульса, и иногда эти макросы могут творить чудеса, что мы уже смогли увидеть на примере __TIME__.

Все оказалось просто, я бы даже сказал прозаично — в любой компилятор при его запуске можно передать кастомные defineы, чтобы потом на их основе код вел себя по-разному. Для MSVC это можно сделать через флаг /D{define_name}. И эта история стара, как мир, просто сейчас ты забываешь ее в самый нужный момент, потому что нынче модно ругать и шеймить за макросы.

В, общем, классика вступает в дело. Было:

constexpr Canvas newLife = update(life);

Стало:

#ifdef STARTUP
constexpr Canvas newLife = random_canvas();
#else
constexpr Canvas newLife = update(life);
#endif

Изменения на стороне скрипта касаются запуска компилятора:

first_build = True

def compile_cpp():
    global first_build
    
    STARTUP_CMD = '/DSTARTUP' if first_build else ''
    COMPILE_CMD = f'cl /std:c++latest /O2 {STARTUP_CMD} main.cpp'

    result = subprocess.run(
        COMPILE_CMD,
        stdout=subprocess.PIPE,
        stderr=subprocess.PIPE,
        shell=True,
        env=msvc_env
    )
    
    first_build = False

В первую итерацию main loop'а скрипт запустит компилятор вот так:

cl /std:c++latest /O2 /DSTARTUP main.cpp

Остальные запуски будут без /DSTARTUP:

cl /std:c++latest /O2 main.cpp

Финал

Кадры дерганные из-за кривой записи с экрана, но сценарий с огромным космическим кораблем в конце я не мог не оставить.

Бонусом прилагаю, как я смотрю exe-файлу прямо в душу, пока он нещадно меняется компилятором. Смотрю, но не запускаю!

Far3 не выдает такой хороший FPS, но сама возможность видеть такие кишки приносит удовлетворение сама по себе. Расширение Hex Editor для VS Code показывает изменения бинарного файла шустрее, практически в реальном времени, но там нет таких веселых смайликов для байта 01.

Что это было?

Да я и сам задаюсь этим вопросом. Однако же, давайте ретроспективно взглянем, что мы делали и чем мы овладели:

Узнали некоторые тонкости constexpr
Научились запускать MSVC без IDE
Залезли голыми руками в потроха exe и даже нашли там то, что искали
Поюзали макросы, хе-хе
Начали за здравие, закончили за питон
Познали тонкости os.system и subprocess.run
Я зачем-то показал вам шейдер
Сумели в compile-time random
"Игру" написали
Не запускали бинарник, а просто стояли рядом!
Повеселились, в конце концов

Ненормальное программирование делает жизнь веселее. Главное не тащите такое на прод.

Теги:

Хабы:

Если эта публикация вас вдохновила и вы хотите поддержать автора — не стесняйтесь нажать на кнопку