#madskillz

Как правильно выполнить любой код до и после main() 🏃

Функция int main() не является настоящей "точкой входа" в программе. До того, как зайти туда (и после него), программа выполняет много другого кода, в том числе юзерского.

Почти всегда этот код - инициализация статических объектов, которая выполняется до main(). Программа:

    std::vector<int> MakeVector() {
        std::cout << "do MakeVector" << std::endl;
        return {1, 2, 3};
    }
    std::vector<int> VECTOR = MakeVector();
    int main() {
        std::cout << "do main" << std::endl;
    }

Выведет такое:

    do MakeVector
    do main

Пример на godbolt

В этом коде можно делать что угодно (читать файлы, записывать в поток и т.д.), окружение там полностью готово. Я часто использую лямбды:
Пример на godbolt 1, godbolt 2.

😀 Есть крутой лонгрид (со схемами) про то, что происходит до и после main(): Linux x86 Program Start Up.
Но все описание там "примерное", потому что поведение зависит от компилятора и его версии 🖥
В моем случае некоторые действия находятся в другом положении схемы (увидел по gdb), и еще есть дополнительная вложенность - есть функции для отдельных .cpp-файлов, а там внутри уже вызовы для инициализации переменных.

⌨️ Для того, чтобы "вызвать функцию до main()", можно пометить ее специальным атрибутом.
А именно __attribute__((constructor)) или менее вырвиглазно [[gnu::constructor]].

Здесь слова "constructor" и "destructor" не относятся к классам в C++, это исторические названия еще до C++.

Пример на godbolt с ctor-ами и dtor-ами

Однако здесь есть типичный прикол с std::cout 😁
👍 Пример по ссылке выше, скомпилированный на x86-64 clang trunk по состоянию на 13.06.2023 работает нормально.
❌ Более старый релиз x86-64 clang 16.0.0 дает сегфолт в кторах и будет работать только если поменять там на printf - ссылка на godbolt.
😠 Это связано с тем, что std::cout и подобные объекты инициализируются в конструкторе статического объекта std::ios_base::Init (объявление этого объекта находится в хедере <iostream>).
А компилятор данной версии так скомпилировал, что кторы выполняются ДО НЕГО и пытаются обратиться к неинициализированному объекту.
Функция printf таких спецэффектов не имеет, там просто перенаправление в нужный системный вызов (syscall) без регистрации и СМС.
Мораль думайте сами 👍

❔ Для чего может быть полезна такая штука? Лучше описать как "вопрос-ответ"

1️⃣
Вопрос: В чем принципиальное отличие этого кода:

    [[gnu::constructor]] void foo() {
        // приколы
    }

от этого:

    struct Dummy {
        Dummy() { /* приколы */ }
    };
    Dummy dummy;

или более укуренного этого:

    const auto dummy = []{
        // приколы
        return nullptr;
    }();

Ответ: Никакого, кроме более удобной записи.

2️⃣
Вопрос: Зачем это все надо, почему нельзя этот кусок кода поместить в int main()???
Ответ: Иногда нужно выполнить кусок кода, только если мы линкуем какую-то библиотеку или подключаем хедер. Например, если в библиотеке хэширования есть расчет хитрых данных для хэшей на старте программы в [[gnu::constructor]], то не надо париться с тем, как и что вызвать в main(), можно просто линковать библиотеку и заработает.

Да точно это же и происходит для std::cout, как мы только что увидели выше!

3️⃣
Вопрос: Какие жесткие проблемы решает эта запись?
Ответ: В кторах и дторах можно указывать приоритет 😐 Чем он выше, тем позже выполнится ктор (и соответственно раньше дтор).
Пример на godbolt.
Это решает артиллерийский выстрел в ногу под названием Static Initialization Order Fiasco. Очередность выполнения инициализаций обычно зависит от порядка линковки, а с приоритетом стало можно это нормально разруливать! 😎

В остальном проблемы линковки все еще остаются легендарными - можно почитать пример особо опасной проблемы, о которой писал раньше: https://news.1rj.ru/str/cxx95/76

#theory

Замороженные корутины 🧊

Am Ende bleib ich doch alleine
Но в конце я остаюсь один
Die Zeit steht still und mir ist kalt
Время остановилось, и мне холодно

Этот пост больше теоретический, чем практический - просто эта тема сложная, чтобы даже иметь какой-то minimal viable product 😱

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

1️⃣ Разработка "тасок" по триггеру

"Таска" это такая микро-программа на Python, которая должна запускаться по какому-то триггеру и делать что-то обычно небольшое: отправка email, создание тикетов, http-запрос в сервис, и прочее 👦 Сервис выполняет эти программы на каком-нибудь свободном сервере.

Иногда таска может быть посложнее - например, создать и запустить другие таски и ждать их выполнения. В таких случаях исходная таска "замораживается" (переходит в состояние "Wait") и прекращает свою работу, а после финиширования дочерней таски возобновляет работу, снова на каком-нибудь свободном сервере 🖥

Есть проблема - система не может как бы "продолжить" код таски с той точки, где было ожидание таски. Был придуман нереальный костыль, который выглядит примерно так:

    def on_execute(self):
        if not self.Context.config_stage:
            self.Context.config_stage = True
            param1 = ...
            param2 = ...
            task = sdk.CreateTask(param1, param2, ...)  # создаем дочернюю таску №1
            raise sdk.WaitTask(task)
        if not self.Context.run_stage:
            self.Context.run_stage = True
            param = ...
            task = sdk.CreateTask(param, ...)  # создаем дочернюю таску №2
            raise sdk.WaitTask(task)

Сервис сохраняет "контекст" между разными запусками таски, а метод on_execute каждый раз запускается сначала ♻️
В "контексте" можно ставить флажки, чтобы имитировать разные стадии таски, еще туда можно сохранять списки/строки/числа ✍️
Наконец, оповещение сервису о том, что текущей таске надо дождаться другую таску, делается через бросание исключения (raise), чтобы это "прорвалось" за пределы def on_execute (удобнее, чем просто return, если вызываются всякие вложенные методы) 🤔

При таком подходе надо очень аккуратно писать код и много думать, если таске нужно делать что-то немного нетривиальное: например запуск дочерних тасок в цикле, пока одна из них не завершится успешно 🙁 Попробуйте сами наколхозить такое, будет треш.

2️⃣ Микросервисы в Apphost

По ссылке открыто описано что такое Apphost - фреймворк для микросервисов (на Python или C++).
Он решает многие старые проблемы, но появляется новая проблема - теперь программа не может просто так сделать HTTP-запрос.
Нужно разбивать всю программу на микроскопические куски кода, которые принимают некие "входящие" объекты и формируют "исходящие", но не более того. Все походы во внешние сервисы делает Apphost. Эти куски кода выполняются на разных серверах.
Та часть, которая раньше делалась мгновенно, сейчас делается в 10 раз медленнее из-за настройки конфигов, жесткого обдумывания "графа" выполнения, и так далее.

❓ Использование корутин

Неприятности в сервисах, указанных выше, теоретически можно решить через корутины. Я когда-то писал о них в канале. Это функции, которые могут приостанавливать свое выполнение, а затем продолжать с той же точки.

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

Потом здесь можно почитать, как корутины реализованы в C++ (начиная с C++20) - это очень сложные статьи, их можно читать несколько недель, зато появляется максимальное понимание, как компилятор преобразовывает код.

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

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ

#cringe

Про SJW в C++ комьюнити 🤡

Настало время обратить внимание на такую суперважную для Барнаула (Алтайский край) проблему, как борьбу за социальную справедливость в комьюнити по C++.

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

Я написал ему на почту - что произошло и кто может отревьюить патч. Оказалось, что сообщество его "отменило" aka "закэнселило" 🤡

В 2011 году он, видимо, последовал совету Трампа ("grab them by the pussy"), после чего получил две уголовки и попал в почетный список Форбс "U.S.'s sex offender registry".

Зачем об этом знать и какое отношение это имеет к C++?
Оказывается (как он мне написал), в 2021 году группировка с includecpp.org об этом факте узнала и начала попытки "отменить" еб*ря-террориста со всего интернета, и оффлайн тоже. 🔫

По этой причине он, например, не выступал на CppCon 2021 - для этого борцуны в твиттере угрожали Гербу Саттеру, а также выгнать Microsoft из комитета по C++.

И соответственно из LLVM его также выгнали - якобы по причине нарушение "Code of Conduct".

Далее произошел небольшой прикол (это было начало 2022 года) 😁
- Я в ответ написал ему, что понимаю его - меня также "отменяют", ограничивая в правах пожрать в макдаке и оплатить онлифанс, хотя я даже не трогал маленьких девочек.
- На что он бомбанул и ответил в общих чертах, что тут как раз все правильно, SJW ни при чем, наши страны находятся в состоянии войны, тебя разъ*бут как Ирак, зато ты после этого получишь аналог Плана Маршалла 😱

От такой щедрости я почувствовал мем с пингвином. Особо не ответил ему, но надеюсь что он больше не показывает своего Маршалла местным Лолитам 😁

Однако вернемся к нашим маленьким фанатам экстремизма. Сайт includecpp.org выглядит максимально клоунским.
Достаточно посмотреть на "code of conduct" и пооткрывать твиттеры в ссылках под "the moderation and administration team includes", чтобы начать подозревать, что в западных странах есть проблемы с доступностью психотерапии для населения.

На мой взгляд, корнем проблемы является то, что комьюнити по C++ не объединено никаким бизнес-интересом - развитие языка и компиляторов не идет слишком быстро.

Из-за этого, когда толпе нечего делать, они находят всякие причины поссориться с кем-либо, и особенно крикливые объединяются в организованные группировки. В целом это оставляет плохое впечатление и желание дистанцироваться от любого рода "тусовок".
Похожие драмы происходят в Rust и прочих языках, и мне все-таки кажется что нормальный человек не будет таким заниматься.

Я пофантазировал и представил себе "Моральный кодекс C++-программиста в 2030 году", через несколько лет посмотрим насколько я попал 🚬
1️⃣ Запрет паттерна проектирования "фабрика" и слов в коде как work, job и прочее, так как это угнетает права безработных
2️⃣ Одобрямс легализации насвая в стране, истинная вера в то что это "менее вредно чем алкоголь", прослушивание учёных которые доказывают это "научными фактами"
3️⃣ Подписывание бумажки "я признаю Rust Foundation террористической организацией за вторжение в Linux Kernel и оккупацию 20% Stackoverflow"
4️⃣ Переменные наподобии номера гендера хранить в int16, потому что int8 не будет хватать
5️⃣ Не менее 28.2% C++-программистов должны составлять иностранные специалисты из беднейших регионов мира, с такой же зарплатой как у всех
6️⃣ Мультиязычность - одна часть проекта должна быть на C++, другая на Python, третья на Delphi, четвертая на JavaScript и т.д. Реклама, что такой подход делает проект более технологично богатым. Всякие утверждения, что некоторые языки не совместимы друг с другом и что моноязычный C++-проект проще разрабатывать - языковой шовинизм.
7️⃣ Из-за того, что комитет по C++ когда-то попытался поглотить комитет по C, каждый C++-программист теперь должен платить репарации C-программистам. За утверждения, что C и C++ родственные языки, имеющие общую историю и происхождение, которые совместимы в одном проекте, следует немедленный кэнселинг.

#books

Обзор книги "Practical Binary Analysis" (2019 г.) 📚

(можно скачать PDF тут)

На фотографии внештатный корреспондент паблика "C++95" Билли, прочитавший данную книгу.
Его отзыв: "Oh yeah, это точно стоит three hundred bucks! ASM WE CAN!" 📞

Я давно ничего не писал из-за занятости, но сейчас смог 🫡

Эта книга посвящена разнообразному анализу бинарников, то есть исполняемых программ без соответствующего исходного кода. В ней очень много информации, больше чем в любой другой книге из #books - ее реально читать неделями.
Там есть знания, которые могут пригодиться разве что reverse engineers и vulnerable researchers, но и другим тоже может быть интересно 🤔

В 1️⃣ главе дается анатомия бинарника и как он вообще появляется на свет - как в книге про компиляцию.

Во 2️⃣ и в 3️⃣ главах описываются форматы исполняемых файлов ELF (на Linux) и PE (на Windows)

В 4️⃣ главе строится своя тулза для загрузки бинарника с помощью libbfd. В книге вообще есть упор на создание собственных анализаторов бинарников.

В крутой 5️⃣ главе решается задача из CTF по поиску "флага" в бинарнике, на примере которой применяются десятки подходов и тулз, чтобы шарить еще лучше.

В 6️⃣ главе, которая на мой взгляд является центральной, показывается фундамент анализа и дизассемблирования 🖥

Там народу являют жестокую правду - в общем случае нет какого-то единого алгоритма дизассемблирования.

Более тупые дизассемблеры (как objdump) имеют линейный алгоритм - тупо расшифровывают ассемблерные команды от начала до конца.
Так как компиляторы могут встраивать вспомогательные данные прямо в код (особенно Visual Studio), то можно например напороться на jump table. По факту это список адресов, но дизассемблер об этом не знает и нарасшифрует в этом месте ассемблерные команды 👍
Ничего не упадет, потому что в x86 "плотный" набор команд и практически любая последовательность байтов представляет собой валидный ассемблер 👍

Более умные дизассемблеры (как IDA Pro) имеют рекурсивный алгоритм - они расшифровывают как бы настоящий код и только те места, куда управление доказанно может перейти, например через jmp. Там свои сложности с неявным control flow, когда в коде есть jump table или vtable, которые неявно указывают куда передавать управление, но это решаемо.

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

Чтобы определить, где находится условная "функция", дизасм ищет "сигнатуры", то есть паттерны ассемблерных инструкций, которые часто используются в начале/конце функции.
Пример сигнатуры в неоптимизированном x86 это "пролог" push ebp; mov ebp,esp и "эпилог" leave; ret
Есть и более сложные кейсы, когда делается "tail call", а оптимизированные функции могут не иметь пролога и/или эпилога, поэтому ошибок может быть от 20% и больше.

Очень сложно восстанавливать структуры данных (C/C++), дизасмы часто не пытаются этого делать ☔️

Для более простого анализа часто используется промежуточное представление (IR, Intermediate Representation) ассемблера - например, вместо исходника где могут быть сотни разновидностей инструкций x86/ARM, можно получить IR где единицы разновидностей. IR бывает несколько, например REIL.

Дизасм восстанавливает код, который делает примерно то же, что ассемблер. Обычно выглядит он все равно довольно ужасно, но дизасмы стараются 🥺 Например, по эвристикам (то есть через три костыля) определяются простые циклы (for/while), математические формулы, и прочее.

ПРОДОЛЖЕНИЕ В КОММЕНТАРИИ

#cringe #books

На данном скриншоте - последствие того, как автор поста на два дня положил систему для практикума форк-бомбой.

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

Обзор книги "Введение в язык Си++" (2012/2020 г.) 📚 🤪

Jeder lacht, jeder lacht — ja
Все смеются, все смеются, да
Jeder lacht über dich
Все смеются над тобой

В #books есть обзоры на хорошие книги, но не хватает обзоров на примеры, каких книг не стоит писать. Я решил, что надо обзирать какой-нибудь университетский учебник, потому что его эффект более разлагающий.

Под руку попалось творчество уже знакомого нам Столярика. Уважаемый телезритель может засомневаться - нет ли у меня предвзятого отношения к нему? Нет - просто других методичек почти нет, и они слишком плохи, чтобы быть интересными.

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

Книжка намеренно небольшая, потому что рассчитана на 6-8 лекций. За 4 года бакалавриата на C++ больше времени не находится, ведь так в учебный план не поместятся философия, урматы и основы экономики.
А ведь плюсы это такая глыба, что полный справочник позволяет Столярову обороняться от своих многочисленных врагов... 🔫👀🔫

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

Предполагается, что читатель уже знает язык C и с него переучивается на C++, там описывается разница между языками

    Для изучения базовых средств языка Си++ вам потребуется уверенное владение языком Си

Звучит аналогично тому, чтобы изучить французский язык, надо сначала выучить латынь (откуда le français произошел), а потом выучить дифф между латынью и французским 😈
Языки упорно называются "Си" и "Си++", одобряем патриотический перевод 👍
В главе Язык Си++ и его совместимость с Си нет ни слова про действительную совместимость языков через extern "C".

    В языке Си++ введен механизм **защиты**, который позволяет запретить доступ к некоторым частям структуры

Интересно, как "инкапсуляцию" перевели как "защиту"... Еще можно переводить "полиморфизм" как "превентивный удар", а "наследование" как "хлопо́к". Там много такого надмозгового перевода.

    Мы могли бы написать и так:
        double mod = str_complex(2.7, 3.8).modulo();
    В последнем случае мы создали временную **анонимную переменную** типа `str_complex`

Фразу "unnamed object" из Стандарта лучше перевести как "безымянный объект". Но лучше бы были рассмотрены категории выражений (lvalue/rvalue и их подвиды) и их поведение, вместо этого всё объясняется "на пальцах" и размыто, а про move-семантику нет ни слова.

На примере показывается полезность инкапсуляции в C++. К сожалению, не описана типичная Сишная идиома для инкапсуляции opaque data type, что было бы к месту для тех, кто переучивается с С на C++.

В главе про const ничего не сказано про ключевые слова constexpr и (!) mutable, что плохо, потому что не складывается понимание что это слово про логическую константность, а не физическую.

Там же рекомендуется передача переменной через константную ссылку:

    Так, если в описанном ранее классе `Complex` вместо
         Complex operator+(Complex op2) { ... }
    написать
        Complex operator+(const Complex &op2) { ... }
    семантика кода не изменится, но физически вместо копирования двух полей `double` будет происходить передача адреса ...

По крайней мере для 16-байтовых типов это неверно - их на x86-64 выгоднее передавать через копию. В проектах можно использовать чекер clang-tidy: пример проверки на godbolt.

ПРОДОЛЖЕНИЕ В КОММЕНТАРИИ

#opensource

Обзор на TeX 📖

Ist doch so gut gewürzt und so schön flambiert
Так хорошо приправлено и красиво обжарено
Und so liebevoll auf Porzellan serviert
И с любовью подано на фарфоре
Dazu ein guter Wein und zarter Kerzenschein
Под хорошее вино и нежный свет свечей
Ja, da lass ich mir Zeit, etwas Kultur muss sein
Да, я не тороплюсь, капля культуры должна быть!

В опенсорсе самым 𝓪𝓮𝓼𝓽𝓱𝓮𝓽𝓲𝓬𝓪𝓵 проектом является скорее всего TeX от Дональда Кнута. Это система для создания красивых документов, особенно для научных работ и технических книг 📖 Многие хотя бы раз его использовали, например для описания математических формул.

Про него есть много информации, но почти вся поверхностная. Стало интересно, что там внутри.

Можно смотреть "снизу вверх":
1️⃣ Шрифты - набор изображений символов (обычно векторных), сейчас популярен формат TrueType.
Векторные изображения переводятся в пиксельные на мониторе с приколами наподобии хинтинга и ClearType.

Многие стандартные шрифты имеют разное начертание для разных размеров, чтобы выглядело красивее. То есть буквы в 10м кегле (10pt) это не то же самое, что увеличенные в два раза буквы из 5pt 🤵

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

Это обширная тема, в линуксе даже есть мемчик "шрифты говно" 💩

2️⃣ Формат файлов DVI - выходной файл TeX. Чтобы "прочитать" этот файл, надо хранить состояние из нескольких переменных и выполнять "команды" из файла побайтово. Например, команда set_char_a как бы "печатает" в текущем месте один символ a и сдвигает курсор вправо на ширину символа a.

Этот файл не содержит в себе шрифтов, а только "ссылается" на них, и знает из шрифта высоту/длину/глубину символов. На картинки он тоже только ссылается, и дефолтные DVI-просмотрщики не показывают их.

Смысл этого формата - получать один и тот же документ на любом компьютере 🖥

3️⃣ TeX - сам набор программ и язык разметки.

Самая подробная информация есть в книге от автора The TeXbook в 400+ страниц, можно пропускать слишком подробные куски 🔍
В других книгах как обычно выкинут 80% информации и еще неправильно переведут (например, "инкапсуляцию" как "защиту").

У ванильного TeX примерно 900 команд, но только ~300 команд являются базовыми. Например, команда \TeX для вывода лого TeX является макросом для такой последовательности:

    T\kern -.1667em\lower .5ex\hbox {E}\kern -.125emX

То есть печатается символ T, потом печатается E со сдвигом от изначального места немного вниз и влево, потом печатается X со сдвигом влево 📄

В The TeXbook описано, как текст из .tex-файла переводится в токены, какие есть категории токенов (глава 8)

В отличие от WYSIWYG-редакторов, TeX работает на уровне абзаца, а не строки, и распределяет слова по отдельным строкам так, чтобы минимизировать метрику badness.

В TeX есть понятие "клей" (glue) - это объект-отступ между разными сущностями TeX 🔺 "Клей" после запятой растягивается в 1.25 раз больше, чем "клей" между соседними словами, а "клей" после точки/знака !/знака ? соответственно в 3 раза больше.

"Клей" может быть бесконечно растяжимым/сжимаемым, например команда \centerline это макрос

    \line {\hss #1\hss }

Команда hss ставит бесконечный "клей", и TeX располагает параметр макроса (то есть #1) ровно в центр строки.

Есть огромная куча костылей, чтобы менять любое правило.
Например, чтобы написать в документе Mr. Evil с отступом как между соседними словами (а не с х3 отступом как для нового предложения) надо писать Mr.\ Evil.
Чтобы было нельзя перенести Evil на следующую строку без Mr., надо писать Mr.~Evil (~ это тот же пробел).

Можно поставить одинаковый glue stretching (после слов, запятых и точек) командой \frenchspacing.

Можно сформировать длины строк в форме полукруга (в The TeXbook есть примеры) командой \parshape, и так далее...

ПРОДОЛЖЕНИЕ В КОММЕНТАРИИ

#story

Как проходит отбор к межнару по информатике 🚬

Я подумал, о чем бы написать в канал, чтобы он не пустовал, и решил, что эта тема сойдет 😁 Про C++ тоже будет.

🅰️🅰️🅰️🅰️🅰️🫥1️⃣
Калибровка Dota MMR рейтинга Codeforces
Однажды я как обычно отсиживал время в своей школе, и кто-то сказал что бывают некие "олимпиады", с помощью которых можно поступить в любой вуз без экзаменов, но это не точно 👦

Я был не уверен, что мне особо нужен "топовый" (будто бы) вуз, что я вывезу если там сложно учиться и так далее 🚬 Но идти в рандомный ПТУ из-за слитых экзаменов тоже не хотелось.
Отнесся скептически, слово "олимпиады" ассоциировались со скучным занятием для ботанов 🤓 Стало просто интересно, за что дают ход в любой вуз.

Узнал, что в этом олимпиаде есть несколько этапов (школа/город/область/финал). Открыл Codeforces, который в интернете советовали для подготовки. Порешал там что-то (🔍 первый день).

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

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

Прикол в том, что Codeforces превращает решение обычных алгоритмических задач в рейтинговую игру 🎮

В стандартном раунде дается 5 задач на 2 часа.
В самом начале задачи стоят 500-1000-1500-2000-2500 баллов, они отсортированы по сложности: первую решают почти все, последнюю единицы (из многих тысяч участников) ⌨️ Чем позже решишь задачу, тем меньше баллов она будет стоить, за неудачную попытку от задачи отнимается 50 баллов.

Во время раунда отосланное решение задачи проверяется на "претестах", то есть каком-то наборе из ~10-15 тестов, и только после раунда на всех ~100-150 тестах. Это значит, что статус "претесты пройдены" не означает полного решения и задача может упасть во время полного тестирования 🚬 Если кажется, что решение было неправильным, то можно в течение раунда перепослать решение, тогда от задачи также отнимается 50 баллов.

Если 100% кажется, что твое решение правильное, можно "заблокировать" задачу - тогда больше нельзя перепосылать решение, зато можно смотреть решения этой же задачи у других участников в твоей "комнате" (рандомные ~50 участников раунда) и попытаться "взломать" их решения ⌨️ То есть подбирать такой тестовый кейс, на котором чужое решение работает неправильно. Успешный взлом +100 баллов, неуспешный -50 баллов.

Это всё и еще ряд правил делают каждый раунд непохожим друг на друга. Есть несколько стратегий по разгрому раунда, самые необычные/сложные такие:
1️⃣ "Стальные Яйца" - первым делом решать 3-ю или 4-ю задачу. Так как более "весомые" задачи теряют больше баллов со временем, то выгоднее решать их быстрее всего (в разумных пределах) и потом уже 1-ю и 2-ю.
Это самый рискованный путь, и если задачу решить не удастся, то урон рейтингу будет мощным.
2️⃣ "Крутой Какер" - после решения первых задач (сколько можешь - 2 или 3) не пытаться решать оставшиеся, а "заблокировать" решения и бросить все силы на "взлом" чужих решений. Для этого усиленно ищутся крайние случаи и прокачивается навык скорочтения говнокода.
Можно пойти на такую хитрость - так как многие другие участники изредка мониторят "комнату" и сразу же блокируют свои решения после первых взломов (далеко не все задачи "взломабельные") и тоже пытаются ломать кого-то, лучше не ломать никого сразу, а накопить список лохов и потом грохнуть сразу пятерых и получить +500 баллов 👊
(Самые жесткие вариации стратегии дополнительно предполагают засылку хренового решения по сложной задаче, лишь бы пройти претесты, а потом прочитать чье-то нормальное решение в комнате и также ломать)

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

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ

#opensource #compiler

Обзор на Zig ⚡️

(Вступление)
Эти фото из прошлой жизни, сняты где-то ~7 лет назад. Они напоминают мне старый демотиватор. Мягкая лошадь давно живет у мамы, а фандом умер 🪦

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

Символом эскапизма в европейской истории можно назвать замок Нойшванштайн - его построил король Баварии Людвиг II, по хардкору фанатевший по операм Рихарда Вагнера (известного представителя немецкого романтизма), потратив кучу бюджетных денег. Интерьер весь отделан с изображениями его разных опер. Людям понравилось - сейчас это бешено популярное туристическое место. Каждый может строить свой личный "нойшванштайн".

Главная концепция немецкого романтизма обозначается моим любимым словом (непереводимым!):
📜 Sehnsucht - ein hoher grad eines heftigen und oft schmerzlichen verlangens nach etwas, besonders wenn man keine hoffnung hat das verlangte zu erlangen, oder wenn die erlangung ungewisz, noch entfernt ist. (Das Wörterbuch der Gebrüder Grimm)
📜 Sehnsucht (читается "зензухт" с длинным "е") - высокая степень сильного и зачастую болезненного желания чего-то, особенно когда нет надежды это получить либо цель желания смутна и еще далека. (Словарь братьев Гримм)
Это смутные мечты по недостижимой идеальной действительности и гармонии. Тема обыгрывается в творчестве Гёте, Шиллера, Вагнера, из современных Rammstein, и так далее.

Мой небольшой sehnsuchtlein состоит в поиске "идеального C++". В двух словах, фундаментально мне не нравится, что ООП в языке реализуется так, что каждый "объект" является "рабом" и реагирует на вызовы методов, чтобы работать - вместо того, чтобы быть полноценным компонентом. По сути настоящими "объектами" являются отдельные потоки. Эту тему сейчас я не буду развивать, она пока не получила внятного оформления. Для поиска ответов я исследую другие языки программирования.
Недавно проверял язык Zig на предмет интересных идей.

Обзор на Zig ⚡️ (теперь точно)

У языка почти 27k звезд на гитхабе. Похоже, что автор назвал язык в честь операции на splay-дереве 🌴 Но с его символом-молнией возможно что автор языка просто маленький любитель экстремизма - уважает песни "Коловрат", фильм "Romper Stomper", и прочие методички по акциям прямого действия против ценнейших иностранных специалистов (осуждаем) 🤷‍♂️🤷‍♂️🤷‍♂️

Создание своего языка программирования может казаться задачей для надмозгов, но это проще, чем кажется:
1️⃣ Парсер языка - ANTLR/yacc/flex, или можно написать свой парсер; он нужен для перевода кода в LLVM IR
2️⃣ "Бэкенд" языка это почти всегда LLVM, у Zig тоже:

Zig supports generating code for all targets that LLVM supports

3️⃣ Если хочется добавить интероп с С/C++, это делается через использование libclang в парсере
4️⃣ По желанию можно реализовать "рантайм" языка: сборщик мусора, система исключений, RTTI, виртуальную машину, еще можно сделать compile-time вычисления...
Свой микро-язык можно написать за несколько вечеров.
Разных языков сделана огромная куча (один из списков), у этого дела есть большая фан-база: @CompilerDev, @LanguageDev

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ

#retro #story

Обзор Sega Mega Drive 🏃

16-битная приставка Sega Mega Drive появилась у меня в середине 00-х. Я переиграл во многие игры, потому что на городском рынке можно было брать напрокат картриджи на неделю за 15 рублей 🏃‍♂️
Хотя тогда было уже поздно для таких приставок, в провинции время идет с отставанием (обыграно в "Жмурках", снятом в то время), я помню даже оранжевые картриджи для совсем отсталой 8-битной Dendy на том же рынке 🎮

Mega Drive породил новый культурный пласт и сподвиг людей на такие увлечения:
1️⃣ Sonic 😈 - вырос из игры 1991 года, которая выжала максимум из тогдашнего железа (обзор только физики значителен).
После успеха оригинальной игры вышло овер 9000 других игр про Соника, мультфильмов, комиксов и прочего хлама для школьников.
Известный деятель sndk также вырос на нем - даже пробовал сделать свою игру, и в параллельной вселенной он стал бы обычным программистом, но куда лучше у него получалась треш-озвучка, что стало его карьерой.
Даже профессиональные издатели игр выпускали закосы под Соника 🦔
2️⃣ PixelArt 😊 - старые игры были вынуждены иметь пиксельную графику, но с эволюцией железа это почти сразу стало андеграундом. До сих пор живы ценители такого стиля.
В этой сфере популярно рисовать со всякими ограничениями, например "не больше 8 цветов на картинку".
3️⃣ RetroGaming 🎮 - любовь к старому железу и играм, анализ их архитектур и так далее. Играть можно на эмуляторах, хотя есть ценители которые приобретают старые оригинальные девайсы.
У некоторых приставок (у той же Mega Drive) есть новодельные реплики, можно их купить на алиэкспресс 😁
Еще, например, есть дистрибутив Raspberry Pi специально под ретро, и у всех версий RaspPi есть композитный видеовыход, способный работать со старыми телевизорами, что нужно для аутентичности.
4️⃣ Reversing ⚙️ - реверс и изменение старых игр.
Изменение старых игр называется "ромхакинг", про это тоже есть куча ресурсов.
Есть деятели, которые проводят лютые стримы по ромхакингу.
Есть даже ежегодный конкурс на лучший ромхак Соника.
5️⃣ Sega - отдельные ценители следят именно за компанией Sega, например выкладывают на форумах всякие найденные сомнительной ценности материалы, наподобии "финансовый отчет Sega за 1986 год" 😁 Это показывает, насколько приставка повлияла на культуру, что даже такие увлечения есть.

Архитектура Mega Drive выглядит так 🔍, то есть состоит из нескольких главных кусков:

1️⃣ Motorola 68000 - главный процессор, о нем писал тут. Игры программировались на его ассемблере.
Любое обращение к памяти в ассемблере выполнялось шиной (на картинке 68000 bus), которая преобразовывала адреса в разные места: ROM картриджа (объем 4Mb), RAM процессора (объем 64Kb), контрольные порты и так далее, подробнее описано тут.
В общем, больше сказать нечего 😁 Это обычный процессор для игровой логики, достаточно дешевый и популярный на момент создания Mega Drive.

2️⃣ VDP (Video Display Processor) - асик разработки самой Sega, чип видеоконтроллера. Полностью про его работу описано на этом крутейшем сайте (это лучшее, что я читал технического за год), ниже будет пересказ 😉
Этот процессор работает так - у него 24 регистра, которые отвечают за всякую хреновню, а также 64Kb собственного RAM (называется VRAM - Video RAM), куда нужно совать информацию о графике.
Данные во VRAM засовывает процессор 68000 (он же может менять регистры), и VDP просто отрисовывает на телевизор картинку согласно присланным данным и всё, больше ничего не делает.

В VDP достаточно навороченная система со цветами.
В любой момент времени активно 4 палитры, в каждой палитре находится 16 цветов, каждый цвет занимает 9 бит (то есть по 3 бита на R/G/B, суммарно доступно 512 уникальных цветов).
Первый цвет палитры всегда прозрачный, то есть по факту в палитре доступно 15 цветов плюс "прозрачность".

ПРОДОЛЖЕНИЕ В КОММЕНТАРИЯХ

#compiler

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

На кнопочном телефоне у меня было не так много Java-игр, плюс товарищи могли что-то передать по ИК-порту. Но однажды мне купили ШНУР по которому можно было с компа перекинуть все, и я стал "устанавливать все игры" 🖥

Ломая глаза об экран 240x320, я прошел все популярные игры, а для Gravity Defied я прошел все моды и даже пытался менять в .jar-файле что-то сам, получилось поставить картинку на фон и поменять окраску мотыка ⌨️

Обзор байткода Java 👩‍💻

Язык 👩‍💻Java появился в 1995 году и прошел большую эволюцию. Сначала он использовался для апплетов, выполняющихся в браузере. Потом для приложений Nokia и прочих кнопочников (подмножество J2ME).

Эти направления давно умерли, но язык живет - он популярен для разработки в Android, в финтехе и бэкенде (лучший в мире фреймворк для бэкенда 👩‍💻 Spring), есть много проектов (Kafka, ZooKeeper, etc.), появились интероперабельные языки - 👩‍💻Kotlin, 👩‍💻Scala, Closure.
Есть несколько реализаций компилятора Java и виртуальных машин.

Язык довольно простой, потому что на него наложена куча ограничений:
Весь код должен находиться внутри классов.
Тело функции надо писать сразу (нельзя как в C++ только "объявить" функцию).
Принцип "1 класс = 1файл" - в файле Foo.java должно находиться определение ровно одного класса с именем Foo.
Все типы, кроме примитивных (int, double, и пр.), неявно наследуются от класса java.lang.Object. Все методы виртуальные (кроме статических методов).

Генерики в языке - просто развод, их по факту нет. Они добавлены аж в 2004 году как синтаксический сахар 🍫
Все ссылки на объекты указывают на java.lang.Object, а в коде делается неявное приведение к типу.
То есть запись ArrayList<Foo> это самообман - в действительности хранятся ссылки не на Foo, а на java.lang.Object, просто есть неявное приведение к Foo и компилятор чекнет что в твоем коде нигде нет некорректных приведений 🔍

Чтобы примитивные типы можно было использовать в контейнерах, для них сделаны типы-"обертки", наследующиеся от java.lang.Object. Для int это Integer, для double это Double, и так далее.
Нельзя сделать ArrayList<int>, можно сделать ArrayList<Integer>.
Можно оценить оверхед - если std::vector<int> из 128 элементов это 4*128 последовательных байт в памяти, то ArrayList<Integer> из тех же элементов это 128 объектов (которые находятся хрен знает где в куче), каждый является оберткой над int-ом 🍔
Хотя в Java это нормально - он не задумывался как супер вычислительный язык.

После компиляции каждый Foo.java преобразуется в Foo.class, потом они все попадают в "исполняемый" .jar-файл, который является просто zip-архивом 📦
В начале .class-файла находится "constant pool", это константы (строки, длинные числа, и прочее).
Потом в файле находятся функции класса, скомпилированные в байткод.

В супер понятной официальной спеке можно увидеть примерный вывод компилятора в разных случаях, формат .class-файла, что должна делать виртуальная машина, и прочее.
Байткод очень простой - каждая команда состоит из 1 байта, называется "опкод", после него может быть 1-2 байта дополнительной инфы, если надо.
Команды разбиты на ~20 групп из почти одинаковых опкодов, список тут. Многие высокоуровневые, например опкод arraylength который положит на стек размер массива.

Компилятор (который переводит язык в .class-файлы) не делает никаких предположений о memory layout объекта, поэтому вызов метода выглядит так:

    invokevirtual #4 // каждый метод (кроме статических) является виртуальным

Где #4 это 4-й объект в "constant pool", являет собой "символическую ссылку", то есть тупо строку 😁
Если это метод int addtwo(int a, int b) в классе Example, то ссылка такая: Example.addtwo(II)I
Виртуальная машина должна сама все отрезольвить и подставить адрес метода.

ПРОДОЛЖЕНИЕ В КОММЕНТАРИИ

#story

Психоакустика и Bluetooth 🎧

(Вступление)

Heute treff ich einen Herrn,
Сегодня встречаюсь с одним господином,
Der hat mich zum Fressen gern.
Который охотно меня съест.
Weiche Teile und auch Harte,
Нежное филе, да и твердые куски
Stehen auf der Speisekarte.
Входят в меню!

На фото господин, чей голос я почти каждый день слушаю уже давно.
Особенно круто было в 12-13 лет. Представьте - на улице среди панелек мрак и холод, в дворовой школе безвкусно одетые учителя талдонят про деепричастия, на перемене порамсил с иностранным специалистом (и его 100500 братьев хотят с тобой поговорить), на обед вчерашние макароны.
Но вот ты за компьютером, включаешь эту музыку, и все проблемы тают как майский снег, ты становишься "Богом, входящим в Вальгаллу". Всегда есть что посмотреть - например клип из 1995 (вдохновленный романом "Парфюмер"), клип из 1998 (нарезанный из фильма "Олимпия" 1938 года), запись концерта 1998 года Live Aus Berlin (море огня) 🔥

Самый базовый формат цифрового звука это PCM, он представляет собой просто значения амплитуд (это громкость звука).
Например, формат WAV это заголовок из 44 байт, после которого идут байты PCM.
Несжатый звук длительностью в 1 секунду, с частотой 48kHz, стерео (то есть два канала), с двумя байтами на каждое значение амплитуды занимает примерно 1.5 Мбит.

Звук передается мне через Bluetooth 🤙 Но в таком случае его приходится сжимать.
Рекламируется, что пропускная способность Bluetooth составляет 3 Мбит/с, но по факту доступно в разы меньше и вышеуказанный звук нельзя передать несжатым.
Например, под "3 Мбит/с" подразумевается, что идут две одновременные передачи битов от девайса A к девайсу Б, и наоборот от девайса Б к девайсу А, обе 1.5 Мбит/c (направление меняется каждые 625 микросекунд). Кроме этого, много места занимают служебные заголовки, и бывает снижение битрейта из-за расстояния и интерференции 😔

Звук можно сжимать без потерь (lossless кодеки), там применяется много приколов и есть много кодеков (например FLAC), но толку мало - сжатие получается примерно в два раза. Этого недостаточно, чтобы нормально передавать звук по Bluetooth. Еще такие алгоритмы обычно вычислительно сложные 👎

Звук можно сжимать с потерями (lossy кодеки). Всего кодеков в Bluetooth с десяток, но единственный, который должен поддерживаться каждым девайсом это SBC (sub-band coding) 🤷‍♂️
Этот кодек сжимает по отдельности небольшие куски стрима. Например, для 16-битного стерео это 512 байт, то есть 128 значений амплитуд, что при частоте 44.1kHz соответствует 2.9мс. В кодеке можно поставить разные настройки (о них "договариваются" девайсы при коннекте через специальные пакеты), при High Quality на такой кусок выходит пакет в 119 байт, что соответствует битрейту 328 Кбит/с.

Чтобы так сильно сжать звук, используются познания психоакустики 👁 Эта наука изучает обработку звука мозгом. Если есть какой-то громкий звук в определенной частоте, то остальные звуки в других частотах мозг как бы "не слышит".
В SBC используется примитивная психоакустическая модель. Частоты разделяется на несколько равных диапазонов (называются "band", в SBC их максимум 8 штук, а в MP3 аж 32), и чем "громче" диапазон, тем больше битов выделяется на его кодировку, а информацию о "тихих" диапазонах можно и вовсе выбросить.
Информация упаковывается в фрейм, получателю остается вычислительно куда менее трудоемкая задача - распаковать фрейм, восстановить подпорченный сжатием звук и воспроизвести его 🎧

За мощность сжатия в SBC отвечает параметр bitpool. Чем он больше, тем меньше сжимается аудио. К сожалению, абсолютное большинство производителей девайсов и софта (даже Windows и Linux) ограничили его сверху значением 53, что дает этот самый битрейт 328 кбит/с.

ПРОДОЛЖЕНИЕ В КОММЕНТАРИИ

#jostik

Обзор жостиков C++ 😱 (номер NULL)

У Вани в канале посты часто состоят из нескольких тем. Я тоже решил не сорить маленькими постами, а собирать мелкие приколы в кучу.
Это будет разоблачение "жостиков", это термин для каких-то малоизвестных (или не очень) жёстких фактов C++ 😡

1️⃣ Ленивый компилятор не затирает память

Авторитеты из PVS-Studio дропнули тест по C++, где надо было найти что не так в коде. Я ответил почти на всё 😁 Вы тоже пройдите, там интересно. Самый интересный прикол был тут:

void UContentPackage::createPackage(dsaFile *m, const void *v, int size) {
  unsigned char        secretDsaKey[3096], L;
  const unsigned char *p = v;
  int                  i, j, t;
  ....
  UContent::generateDsaKey(secretDsaKey, sizeof(salt));
  ....
  // тут был какой-то код для шифрования и подписи файла
  ....
  memset (secretDsaKey, 0, sizeof(secretDsaKey));
}

Это утекшие исходники движка Unity.

Компилятор выбросил memset, и ключ остался на стеке 🤷‍♂️ Компилятор вправе делать такую оптимизацию. В PVS-Studio нашли много таких примеров в опенсорсе.
Чтобы данные гарантированно заполнились нулями, нужно использовать какую-нибудь PRO-версию memset с volatile внутри (он не даст соптимизировать).

Интересен не сам факт игнора memset, а то что такая ошибка помогла банде хакеров сломать систему - кусок из разбора ⌨️

Наличие части утёкших исходников Unity и этого бага в движке помогло SKIDROW в 2017 взломать квест Syberia 3 (Сибирь 3) и еще несколько больших игр на этом движке

Идея в том, что генерируется рандомный закрытый ключ, неким файлам присваивается цифровая подпись, потом игра загружает данные файлы, верифицирует подпись и все норм. Если "угнать" ключ, то можно подписать свой файл и игра его примет.

Я перечитывал несколько раз разбор, гуглил, и возникло много вопросов, на которые не нашел ответа 🤔
1️⃣ Непонятен смысл схемы с "подписью" - зачем на стороне игрока что-то шифровать и потом расшифровывать? Так работает движок Unity?
2️⃣ Ключ остается на стеке после выполнения функции, но если бы memset работал как задумывалось, то что помешало бы украсть ключ во время шифровки файла (т.е. работы метода createPackage)?
3️⃣ Какие гарантии, что кусок стека, где лежит ключ, не будет "испорчен" далее во время работы программы? Для этого достаточно вызвать несколько вложенных функций.
4️⃣ Нигде в интернете не смог нагуглить, как именно взломщики воспользовались ключом, чтобы взломать защиту игры. Всё ведет на этот квиз по C++. Возможно, автор сам входит в эту банду хакеров и просто спалился 😁

2️⃣ Не отдавай ссылку на this из конструкторе

Следующий жостик - не надо никому отдавать ссылку на this или на какой-то свой объект (что равносильно, т.к. адрес объекта будет "this + N байт") на хранение из конструктора. Пример:

class State {
public:
    State(Data data)
        : data_{std::move(data)}
    {
        // `data_` передается по ссылке,
        // неявно используется адрес `this`
        workers_.push_back(std::make_shared<Worker>(data_));
    }

private:
    Data data_;
    std::list<std::shared_ptr<Worker>> workers_;
};

Обычно объект State создается один раз из-за RVO, например тут:

State makeState(Data data) {
    return State{std::move(data)};
}

Но в моем случае был подобный код:

std::pair<State, int> makeState(Data data) {
    return {State{std::move(data)}, 228};
}

Где неявно происходило перемещение объекта State, адрес this становился другим, а воркеры оставались со ссылкой на хз что 💻
Ссылка на godbolt
Я запомнил этот баг, потому что когда-то я его допустил на собеседовании и потом мы 10 минут с собеседующим искали ошибку под gdb и санитайзерами 🎮 Тогда я починил его, заменив в этой паре State на std::shared_ptr<State>.
Самый простой способ этого не допускать - сделать объект некопируемым и неперемещаемым

    State(const State&) = delete;
    State(State&&) = delete;

Тогда перемещения просто не скомпилируются. Если вы делаете свой язык программирования, то сделайте там иммутабельность по умолчанию ⌨️

СМ. ПРОДОЛЖЕНИЕ