#creepy

char, который не char 👎

В файлах разных форматах встречаются file signature - это какая-то последовательность байт, которая помогает подтвердить точный формат файла. Часто это значит, что в начале файла расположены "магические байты" специально для этого формата.

На википедии есть список сигнатур для многих форматов. Часто байты в начале файла человекочитаемы, то есть байты кодируют буквы латиницы - например Rar!, LZIP, OggS.

Посмотрим на пример класса, который принимает четыре байта, а потом проверяет, является ли это сигнатурой RAR-файла:

class BinarySignature {
public:
    BinarySignature(int32_t value)
        : Value_{value}
    {}

    int32_t AsInt() {
        return Value_;
    }

    bool IsRar() {
        return Value_ == 'Rar!';
    }

private:
    int32_t Value_;
};

Заметили ли вы что-то страшное? Это сравнение int с многосимвольным char!

Value_ == 'Rar!'

Запись литерала 'X' из одного символа везде поддерживается одинаково и имеет тип char.

Запись литерала 'XXXXX' из нескольких символов имеет тип int, но компилятор вправе не поддерживать такую запись. Также у этой записи implementation-defined числовое значение, то есть также отдано на откуп компилятору.

Большинство компиляторов C++ поддерживают мульти-символьный литерал и переводят его в int как если бы это были последовательные байты.

Ссылка на godbolt.

Вот такой бывает удобный юзкейс, когда надо взаимодействовать с человекочитаемыми сигнатурами в бинарных файлах 😐

#offtop

Обновление izaron.github.io 🔺

На этом скриншоте - старая версия сайта сайта izaron.github.io, которая велась 5-6 лет назад (сделал скриншот перед обновлением).

Я решил перевести все посты на английский и обновить сайт. Обнаружил, что за прошедшие 6 лет доступные шаблоны для личного блога стали приближенными к магии ✨

В постах с разметкой markdown есть такие фичи:
- можно писать LaTeX-формулы
- встраивать видео с YouTube
- с полпинка прикрутить систему комментариев и реакций
- есть адаптивная верстка, красивая подсветка кода, темная и светлая тема
- сайт обновляется сразу, как только запушить новый коммит на GitHub
- большие возможности по кастомизации всяких кнопок и внешнего вида

Шаблон Chirpy крутой, мне нравится 😁 Можно скопипастить мой репозиторий блога.

#creepy

std::move_only_function - самая позорная фича C++ 🤡

В С++23 добавили std::move_only_function. Это тот же std::function, но в нем основное различие - нет copy-конструкторов, то есть с объектом можно сделать только move.

(Недавно был пост про самую простую реализацию std::function).

В чем кринж этой фичи? Это НЕ добавление "нового класса", с разницей как между std::string и std::string_view.

Это просто "улучшение" старого std::function. Если бы std::function можно было нормально менять, то он бы выглядел, как сегодняшний std::move_only_function. Но менять его нельзя, по причинам описанным в посте про ABI.

Почему я думаю, что это улучшение старого класса, а не новый класс:
1️⃣ Copy-конструкторы в std::function и так не нужны совсем. Как минимум это бесполезно, как максимум это создает разные проблемы при ненамеренном копировании функторов.
2️⃣ В новом классе есть фичи наподобии "small string optimization" - Callable-объект могут не пихать в динамическую память, если у них маленький размер. Это очень нужно, большинство Callable имеют малый размер.
3️⃣ Об этом написали сами авторы класса в своем пропозале - что они фиксят разные мелкие баги std::function.

То есть Комитет по C++, не имея возможности и воли решить вопрос со сломом ABI, решает дублировать классы со стремными названиями и делает вид что так и должно быть. Это не нормально и вызывает у всех много вопросов. Еще на юзеров перекладывается обязанность переписать используемый тип, вместо того чтобы просто обновить версию libstdc++.

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

Можно везде использовать std::move_only_function вместо std::function, но лучше бы std::function был переделан в нормальный вид без нового класса.

#opensource

Обзор на GNOME 🦶

Я сделал хештег #opensource, в котором будут обзоры на opensource проекты с уклоном в C/C++. Иногда интересно поисследовать исходники и даже сделать туда патчи, чтобы узнать много нового.

—

GNOME это окружение рабочего стола, одно из двух самых популярных наравне с KDE.

Денисы Поповы наделали кучу его форков: BolgenOS, MATE, Cinnamon, Pantheon, Consort, etc.

GNOME или его форк используются по умолчанию в куче дистрибутивов: Ubuntu, Debian, Fedora, Arch, Linux Mate, openSUSE, etc.

Мое знакомство с GNOME началось с того, что его UI мне очень нравился, а UI у KDE - категорически нет. Поэтому я решил помочь GNOME патчами.

6 лет назад патчи отсылались по голубиной электронной почте. За это время, видимо, у последнего мейнтейнера умер его Pentium, который тянул только почтовый клиент, поэтому сейчас завели GitLab.

Так выглядят патчи в типичный проект Gnome - nautilus (файловый менеджер), на примере моих коммитов туда:
1️⃣ Фикс группового переименования директорий
2️⃣ Вроде бы фикс popup-а для двух мониторов
3️⃣ Подтверждение смены имени файла при конфликтах через Enter

Бездна баттхёрта начинается с того, что почти все проекты Gnome написаны на Си. Так выглядит обычная структура типа очереди:
struct NautilusFileQueue
{
GList *head;
GList *tail;
GHashTable *item_to_link_map;
};

GList выглядит так же стремно со всеми вытекающими:
typedef struct _GList GList;
struct _GList
{
gpointer data;
GList *next;
GList *prev;
};
Это вызывает флешбеки к задачам с leetcode, там тоже надо было вручную переворачивать списки.

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

Активно используется уникальная идиома Си - opaque data type, например для hash table.
В этой идиоме пользователь видит просто объявление структуры struct foo; и функции которые первым аргументом берут struct foo*, и на этом всё.

Программировать на Си мне не понравилось, так как все равно нужно сначала думать в терминах ООП (как в C++), а потом переводить мысли в Си как через перевод Гоблина.

Самая страшная вещь это то, что Gnome - радикальные велосипедисты. У них есть такие велосипеды, куда вложено куча усилий, как:
1️⃣ GObject - жуткая имитация ООП "как в C++", лишь бы не писать на C++.

2️⃣ Vala - новый язык программирования для десктопных приложений Gnome. Вяло разрабатывается с 2006. Код на нем транслируется в Си. Зачем он сделан - решительно непонятно. У Gnome (точнее у GTK) есть куча обвязок в другие языки, разрабатывать приложения можно на Python, C++, JavaScript, ...

3️⃣ Builder - новая IDE, также непонятно зачем нужная. Косят под Xcode? Разрабатывать приложения можно из любой IDE, где фичей будет заведомо больше.

Для Gnome я бы отметил, что там по ощущениям вроде как всё плохо с тестами. По истории коммитов в nautilus видно, что там половина коммитов - переводы (в основном на такие важные языки как Friulian, Occitan, Catalan, Faroese...), другая половина - изменение поведения принципиально без автотестов.

#story

Встраивание файлов в исходники 📦

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

⭕️ Финтех: много коэффициентов и числовых констант для performance-critical алгоритмов
⭕️ Геймдев: иконки, текстуры, код шейдеров и скриптов
⭕️ Embedded: часто это единственный вариант, если микросхема не имеет ОС и соответственно файловой системы
⭕️ Бэкенд: файлы настроек (известных в build-time), SSL/TLS-сертификаты

Чаще всего для такой цели используется программа xxd.
Посмотрим на пример: файл template.cpp - это шаблон для генерации кода.

Запустим команду

xxd -i template.cpp template.cpp.data

Получим такой файл template.cpp.data:

unsigned char template_cpp[] = {
    /* байты */
}
unsigned int template_cpp_len = /* кол-во байтов */;

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

#include "template.cpp.data"
const std::string TEMPLATE{(char*)template_cpp, template_cpp_len};

В системе сборки можно автоматизировать, чтобы команда xxd запускалась автоматически каждый раз при изменении шаблона, и сгенерированный файл не попадал в исходники (то есть лежал в build-директории): ссылка на функцию CMake.

Подобную функциональность несколько лет пытаются внести в C/C++ в виде директивы препроцессора #embed. Пока удалось это сделать для C23 - крутой блог с примерами:

  static const char sound_signature[] = {
#embed <sdk/jump.wav>
  };

  // verify PCM WAV resource signature
  assert(sound_signature[0] == 'R');
  assert(sound_signature[1] == 'I');
  assert(sound_signature[2] == 'F');
  assert(sound_signature[3] == 'F');

#opensource

Обзор на Lua 👩‍💻

Lua это классический скриптовый язык, широко известный в некоторых кругах. На нем пишутся аддоны к World of Warcraft, Nmap, Nginx, Adobe Lightroom, Neovim, и еще к сотне других проектов. Я решил сделать обзор и собрал всякую редкую информацию.

Этот язык простой как пробка. Основу можно узнать в Learn Lua in 15 minutes.

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

foo.bar = 1337
function Lib.sum (x, y) return x + y end
list = {"apple", "orange", "banana"}

... аналогичны этим:

foo["bar"] = 1337
Lib["sum"] = function (x, y) return x + y end
list = {[1] = "apple", [2] = "banana", [3] = "orange"}

... то есть "массив" это тоже хэш-таблица с ключами от 1 до n (нумерация массивов в Lua с единицы)

Через эти хэш-таблицы имитируется абсолютно всё с использованием разного рода костылей.

Даже можно реализовать, с позволения сказать, ООП.
Объекту foo (хэш-таблице) можно придать ссылку __index на базовый класс (другую хэш-таблицу).
Если какого-то поля foo.bar (ключа bar в таблице foo) нет, то интерпретатор Lua посмотрит в таблицу foo.__index, а если и там нет, то в foo.__index.__index, и так далее.

В языке есть корутины, closure (как лямбда-функции в C++), рефлексия, и прочие нужные приколы.

В интернете есть многие сотни статей про Lua, даже я написал статью 10 лет назад, но лучше читать книгу от автора Programming in Lua. В книгах обычно самое полное изложение, в то время как статьи в интернете заведомо неполные и обычно пишутся чтобы "показать чето крутое".
В книге есть такая информация, которой больше нигде нет, например:
1️⃣ Разные флаги, например флаг LUA_32BITS скомпилирует интерпретатор "Small Lua" с 32-битными числами
2️⃣ Описание условий tail call optimization у функций
3️⃣ Метки и goto
4️⃣ Особенность сборки мусора

Изначально Lua состоял только из интерпретатора и годился для интеракции с проектами на C/C++ (хотя Lua можно использовать и сам по себе как самостоятельный язык).

За долгое время накопилась куча библиотек и проектов. Есть даже несколько новых интерпретаторов/компиляторов, то есть от авторского Lua там только синтаксис языка. Есть полуживой менеджер пакетов LuaRocks (я туда делал пару коммитов).
Конечно, с Python объем всего добра не сравнится, но по сравнению с другими скриптовыми языками Lua выглядит хорошо.

Интересно, что в языке есть навороченный сборщик мусора. Это реализация обычного mark-and-sweep, с крутыми особенностями:
1️⃣ Раньше сборщик мусора делал stop-the-world (когда посреди исполнения программа останавливается и сборщик собирает весь мусор), а сейчас сборщик инкрементальный.
Каждый раз, когда нужно аллоцировать память в N байт, сборщик мусора заодно делает небольшой объем работы, прямо пропорциональный этому N.
В итоге не происходит никаких "фризов", просто аллокация памяти выглядит чуть замедленной.
2️⃣ На объект (= хэш-таблицу) можно повесить функцию, которая вызовется перед "удалением" этого объекта сборщиком мусора. Прикол в том, что внутри этой функции можно сохранить объект в какую-нибудь переменную, и удаления в итоге не произойдет. Это называется воскрешением объекта ✝️. Такого нет во многих языках.
В книге есть разные примеры использования этой техники.
3️⃣ В таблице можно пометить все ключи и/или значения как "weak". Тогда сборщик мусора не будет считать такие ссылки за настоящие ("strong") и в при удалении объекта удалит протухшую пару ключ-значение из таблицы.

Кстати, у Вани в канале есть сборник постов о GC, можно подписаться и почитать 😐

Интерпретатор Lua работает так - читает исходник, транслирует его в "байткод" и интерпретирует этот байткод (как в Java), это быстрее и удобнее.
Поисследовать этот процесс можно, скомпилировав исходники Lua в debug-режиме и запуская его из-под gdb.

Лексер (перевод кусков кода в "токены") и парсер (перевод "токенов" в байткод) работают одновременно, трансляция происходит в один проход, достаточно смотреть на следующий токен (это LL(1)-парсер).
Это самый простой транслятор, и наверное каждый смог бы реализовать перевод Lua в байткод.

#compiler

Теория девиртуализации 😶

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

Однако в некоторых случаях компилятор может "доказать", что он точно "знает" метод, который надо вызвать, несмотря на то, что метод виртуальный 😐

Два простых примера: класс без final (нет оптимизации), класс с final (есть оптимизация - девиртуализация). Девиртуализованный вариант меньше дергает память.
void CallDo(TDerived& obj) {
obj.Do(); // будет ли девиртуализация?
}

Компилятор считает, что можно девиртуализовать вызов в таких случаях:
1️⃣ Метод класса помечен как final.
Смысл в том, что даже в случае работы с объектами TDerived*/TDerived& (которые могут указывать на наследника TDerived) нужный метод будет одним и тем же, как его определил класс TDerived.
struct TDerived : IBase {
void Do() final override; // слово `final` тут
};

2️⃣ Класс является финальным. Смысл в том, что указатель на этот класс не будет указывать на какого-то наследника, который что-то мог бы переопределить, потому что у такого класса просто не может быть наследников.
struct TDerived final : IBase { // слово final тут
void Do() override;
};

Однако есть еще одно условие, когда класс считается финальным - если у него финальный деструктор 😁 Этот прикол я обнаружил в исходнике Clang.
struct TDerived : IBase {
~TDerived() final = default; // слово final тут
void Do() override;
};

3️⃣ Мы работаем с объектом класса, а не с указателем на класс. В этом случае точный класс объекта известен на этапе компиляции.
TDerived derived;
derived.Do(); // это же TDerived, инфа 100%

4️⃣ Объект является prvalue. В C++ есть укуренная классификация объектов, где prvalue (pure value) это грубо говоря выражение которое создает новый объект. Смысл в том, что в этом случае тоже известен точный класс объекта на этапе компиляции.
TDerived MakeDerived(); // просто функция
// ...
MakeDerived().Do(); // здесь будет девиртуализация
TDerived{}.Do(); // здесь тоже девиртуализация

На этом всё! Эта оптимизация логичная и скучная, потому что никаких чудес ожидать не приходится. Смысл в том, чтобы доказать что TDerived/TDerived&/TDerived* указывает именно на объект TDerived, а не на какой-то его потомок.

В реальном мире девиртуализация отрабатывает нечасто, так как надо, чтобы совпали два редких покемона кейса, оба противоречат ООП:
(1) работа с TDerived* вместо IBase*;
(2) Класс TDerived или нужный метод финальный (не помню когда в последний раз писал final).

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

Девиртуализация в C++ не гарантирована. В большинстве своем правила выше работают, но не всегда. В каких-то случаях оптимизировать вызовы виртуальных методов запрещено.

Например, в Apple macOS👩‍💻 есть Kext (Kernel Extension) - расширения ядра, запускающие то или иное несовместимое с оригинальным маком оборудование. Особенность этих Kext в том, что они могут в рантайме менять vtable, поэтому нельзя делать оптимизации, которые обходят обращение к vtable. В Clang есть флаг -fapple-kext для такой настройки.

А в "обычных" окружениях vtable лежат в секциях наподобии .rodata. Эта секция защищена на уровне операционной системы - программа обычно сразу падает при попытке сделать туда какую-нибудь запись в рантайме.

#compiler

Почему constexpr в компиляторах C++ развивается не в ту сторону 🤨

1.5 года назад была написана статья "Дизайн и эволюция constexpr в C++". Там описывается эволюция возможностей constexpr (его вычисление происходит прямо в компиляторе). Потом эту статью перевели на английский PVS-Studio и даже упомянули в твиттере Standard C++ 😀

Вычисление constexpr-выражений исторически связано с алгоритмом под названием constant folding (wikipedia). Алгоритмы этого рода работают на уровне AST (Abstract Syntax Tree), и изначально были нужны для вычисления простейших выражений с целыми числами. В коде выражение 4 + 5 * 6 выглядит в AST примерно так:

+
├── 4
└── *
    ├── 5
    └── 6

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

Вот так обычно вычисляются constexpr-выражения компилятором:
1️⃣ Компилятор сейчас строит AST из исходника на C++.
2️⃣ Встречается выражение, которое нужно вычислить "здесь и сейчас", наподобии такого:

template<int N> class Kek { /* ... */ };
// ...
using Kek34 = Kek<4+5*6>; // точное значение аргумента мне запили!

3️⃣ Компилятор вычисляет constexpr-выражение на основе текущего AST, и сразу использует результаты для продолжения построения AST.
4️⃣ Полностью готовый AST переводится в "модуль" LLVM IR (это байткод - промежуточное представление перед переводом в ассемблер).

Проблема в том, что constexpr становится вездесущим и поддерживать его все сложнее и сложнее. Например, до сих пор нет нормального constexpr std::vector<T>, хотя его должны были сделать еще 4 года назад. Также исправлять баги constexpr реально очень трудно - требуется куча времени, чтобы вникнуть в код. Это своеобразный интерпретатор С++ на AST.

Хватит это терпеть! Подумал кое-кто, и сейчас делает... всё тот же интерпретатор C++ внутри Clang на основе принципиально нового байткода: ConstantInterpreter (статья от авторов).
Эта штука намного быстрее, чем алгоритмы на AST, но не решает главной проблемы - все равное создается ненужный интерпретатор C++!

Я предложил сделать аутсорс constexpr-вычислений на реальное вычисление на процессоре: тема на форуме clang.

Когда мы собираем "модуль" LLVM IR, мы можем запросить выполнение какого-то кода в формате LLVM IR с использованием данных этого модуля (на процессоре текущего компьютера). Лучше всего это видно на примере этих штук:
1️⃣ Туториал по созданию своего языка программирования с LLVM - раздел 3.5.
2️⃣ Программа lli для выполнения LLVM IR.
3️⃣ clang-repl - вообще балдёжная программа, натуральный интерпретатор C++.

Вот так мог бы вычислять constexpr-выражения компилятор:
1️⃣ Компилятор строит AST, одновременно держится выделенный "модуль" LLVM IR.
2️⃣ Каждое constexpr-выражение вычисляется с использованием этого выделенного "модуля" на процессоре компьютера. В этот модуль пихались бы все данные, нужные этому выражению. В общем, выражение выполняется как в clang-repl
3️⃣ Полностью готовый AST переводится в новый "модуль" LLVM IR.

И можно выкинуть огромные куски кода для вычисления выражений там на AST.

Конечно, ничего из этого не вышло. Мейнтейнеры компилятора немедленно забросали меня говном за такую харамную идею. Я просто не стал разбирать по частям всё ими написанное, чтобы не вступать в бесполезный спор, настолько безапеляционные были ответы.

Основная мантра с их стороны была про проблемы с cross-compilation (когда программу собирают под другую платформу). Видимо, есть на свете такие платформы, что там 4+5*6 равняется не не 34, а чему-то еще.

Таким образом, теперь можно понять, почему constexpr в C++ медленно развивается, и возможно никогда не станет полноценным (потому что интерпретировать C++ на AST - плохая идея).

#books

Обзор книги "Linux Kernel Development" (2010 г.) 📚👩‍💻

(можно скачать PDF тут, лучше читать оригинал на английском, а не перевод Гоблина)

Автор этой книги писал код для ядра Linux на протяжении 15 лет (на момент написания книги) в качестве основной работы и сделал там много хорошего.

В этой книге на 400+ страниц содержится информация, нужная для начала разработки кода в ядре Линукса, по состоянию на релиз 2.6.34. Объем информации большой - ведь во многих open source проектах достаточно вникать в код всего несколько дней или часов, чтобы туда что-то написать.

В книге описание "как отправить патч" есть только в одной главе в конце, а в остальном информация выглядит так:
1️⃣ Старые песни о главном: как работает fork(), виртуальная страничная память, прерывания, планировщик задач, syscalls, драйвера, и т.д. и т.п.
2️⃣ Копипаст сишной структуры из исходного кода и описание каждого его поля.
3️⃣ Описание разнообразных настроек, которые могут повлиять на каждую сферу работы ядра.
4️⃣ Иногда описание используемой структуры данных (например красно-черных деревьев)

Ядро написано на ISO C99 и активно использует костыли GNU C Extensions. Я отметил самые крутые на мой взгляд особенности разработки ядра, о которых не задумываются в "обычных" проектах:

⭕️ Ядро не использует стандартную библиотеку C. Нужные функции просто скопипасчены. Например, вместо printf используется функция printk. Еще скопипасчены строковые алгоритмы.
⭕️ Почти нет операций с float, потому что для этого требуется ручная работа с float-регистрами процессора.
⭕️ Стек ядра (kernel stack) жестко ограничен - от 4KB до 16KB.
⭕️ Самый часто используемый инструмент синхронизации - спинлок, с "активным" ожиданием разблокировки в while-цикле. Он обусловлен тем, что в ядре всё происходит сравнительно быстро и дожидаться разблокировки в цикле выходит "дешевле", чем делать всю байду с укладыванием процесса в "сон" и его "пробуждение".
⭕️ Для аллокации страничной памяти есть vmalloc - аллоцирует виртуально непрерывную память, и kmalloc - аллоцирует физически непрерывную память. "Обычные" программы практически всегда используют vmalloc, но ядро практически всегда использует kmalloc для быстроты, чтобы не возиться со структурами виртуальной памяти. Тред на stackoverflow
⭕️ Часто используются "аллокаторы маленьких объектов". Например, slab allocator очень напомнил мне блоковый аллокатор из Box2D (хотя я не большой специалист в аллокаторах).
⭕️ Ядро нельзя нормально дебажить, все пишут логи, чтобы понять что происходит. gdb не работает нормально, он не может никак модифицировать данные ядра, ставить breakpoint-ы и выполнять код step by step. В книге приводится какая-то укуренная схема с костылем kgdb, где используется два компьютера, и один компьютер дебажит ядро второго через шнур. 😈

После этой книги я понял, насколько Linux огромен. Можно сказать, что эта книга "обо всем и ни о чем". Если можно сказать, что компилятор для C++ это "четкая цель", то ядро Linux это "нечеткая цель" - его можно собрать в миллиарде разных конфигураций.

Например: В описании обработчиков прерываний (interrupt handlers - грубо говоря обработка событий типа "ввод с клавиатуры") мы узнаем, что обработчик должен быть мега-быстрым, потому что пока обрабатывается одно прерывание, все остальные прерывания идут лесом.
Поэтому обработка прерывания разделена на две части - "top half" в interrupt handler (очень быстро сделать вещи, скажем поставить флаг где-то в ядре), и "bottom half" когда-то потом (копировать данные, менять структуры в ядре, блокировать поток и тд и тп).
Так вот, для обработки части "bottom half" по состоянию на 2010 год было 5 механизмов - 2 устаревших и 3 активных 😁

И так во всем - везде будет огромное количество опций.
По состоянию на 2010 год официально поддерживалось 60 файловых систем.
Есть целые классы алгоритмов для планировщика процессов.
Несколько методов управления I/O Scheduling (ввод-вывод с жестким диском).
Есть море драйверов, которые можно вкомпилировать в образ ядра по желанию.

Полностью "выучить" Linux невозможно, по каждой части можно писать отдельную книгу 📝

#story

Как я решал задачи по CTF 😀

CTF (Capture The Flag) это соревнования, где участники решают веселые задачки "типа" по кибербезопасности. Забегая вперед, я не понял при чем тут кибербезопасность.

Пару лет назад я порешал такие задачи, чтобы понять что это такое. Мне понравился сайт ctflearn.com (мой профиль). За несколько вечеров можно порешать несколько десятков задач.

Задачи разделяются на несколько категорий.
Дается какая-то сущность (адрес сайта, архив, бинарник, изображение) и из этой сущности надо вытащить "флаг" - строку наподобии flag{w0w_y0u_ar3_c00l_h@cker}, которая может находиться в неожиданных местах.

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

Какие типичные задачи попадаются и как их решать?

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

💻 Дается бинарник.
При запуске ./hack_me выводит хреновню. Однако где-то в нем в открытом виде (не обфусцированном) спрятан флаг. Запускаем strings hack_me (оно ищет человекочитаемые строки) и видим флаг.

💻 Дается бинарник.
По дизассемблеру видим, что требуется "типа" ввести какую-то правильную строку, чтобы показать флаг.
Вообще если где-то в коде есть const char* f = "flag{...}"; то этот flag{...} попадает в бинарь в виде человекочитаемой строки, однако авторы просто обфусцируют этот флаг, чтобы он вычислялся по переусложненной схеме.
Решением является заменить руками несколько байт в бинарнике на инструкцию jmp до вывода флага (чтобы он вывелся без условий).

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

Видел, что иногда бывает дизассемблер Python или Java, по идее это должно быть в 100500 раз проще C/C++, но мне такие задачи не встречались.

💻 Дается база данных.
Нужно написать запрос, который покажет ключ. Обычно делается в виде SQL-инъекции, типа вводишь 1" OR «1» = «1» и получаешь все записи. Напоминаю, что это никак не относится к хакерству, потому что даже самые тупые веб-фреймворки умеют обезопасиваться от этих школьных приемов.

Однако бывают ублюдские задачи, например в одной из них надо было по-моему знать специфические команды MySQL (которых ни в какой другой СУБД нет), которые покажут все доступные таблицы, и вывести данные из "тайной" таблицы.

💻 Дается изображение.
Теперь флаг реально зашифрован в изображении, а не в его метаданных. Это называется "стеганография".

Часто оказывается, что флаг можно увидеть, скажем посмотрев только зеленую маску (из пикселей (r,g,b) сделать (0,g,0)).

Если это картинка типа "помехи телевизора", можно отзеркалить картинку и наложить на исходную, тогда наложение покажет ключ.

Есть целые тулзы для классов задач(!) Для стеганографии это zsteg.

💻 Дается изображение или другой файл.
Часто нужный файл/файлы "спрятан" сразу после первого. То есть грубо говоря взяли файл картинки и сразу после последнего байта картинки приписали файл архива.

Прикол в том, что просмотрщик картинки игнорирует "лишние" байты, и обнаружить спрятанный архив можно только из терминала.

Это детектится по сигнатурам - например архив начинается с человекочитаемых байтов Rar!. По-моему тоже есть тулза специально для CTF, которая детектит такие файлы.

💻 Дается звуковый файл.
Обычно его даже не прослушивают 😁 А сразу смотрят на спектрограмму файла. Там может находиться флаг или какой-нибудь QR-код.

(продолжение в комментарии к посту, потому что у Телеграма есть ограничение по размеру 😤)

#madskillz

Напиши свой собственный RTTI 🖱

RTTI (run-time type information) это некая информация о всех виртуальных классах, которая попадает в бинарник программы.
Благодаря этому работают dynamic_cast<> (приведение типа в run-time) и typeid.
Генерацию RTTI можно выключить флагом компиляции -fno-rtti.

Пусть у нас есть указатель X* x (или ссылка X& x). Указатель может указывать на объект с типом не X (но это обязательно будет тип-потомок X).

Есть три варианта приведений типа X к типу Y (тип Y тоже не обязательно реальный тип объекта):

1️⃣Upcast: Y - класс-предок X.
Для этого не требуется никакого RTTI. Такое приведение всегда возможно. Можно было бы обойтись static_cast<> (приведение типа в compile-time).

2️⃣ Downcast: Y - класс-потомок X.
В этом случае обычно используют dynamic_cast<>. Если окажется, что тип объекта не Y (или не какого-то потомка Y), то приведения не случится.

Интересно, что если программист совершенно уверен, что приведение возможно, то можно использовать static_cast<> и не делать run-time проверку. Если окажется, что он был не прав, то получится undefined behaviour 😁

3️⃣ Sidecast: X и Y никак не связаны между собой.
Такое возможно, если X* указывает на объект класса Z:

class Z : public X, public Y {...};

Такие касты dynamic_cast<> тоже умеет делать.
Скорее всего sidecast значит, что в программе есть серьезные ошибки дизайна 🧐

Некоторые проекты не используют "официальный" RTTI 😡
Почему так происходит, на примере очень популярных проектов:

1️⃣ Protobuf: вынужденная поддержка проектов с -fno-rtti.

В protobuf есть базовый для всех "месседжей" класс google::protobuf::Message.

Чтобы попробовать сделать downcast от базового класса до класса "месседжа", можно использовать функцию DynamicCastToGenerated.
Как видно по исходнику, если уж нельзя вызвать dynamic_cast<>, то используется костыль - суррогат RTTI: сравнение ссылки на "рефлексию" (уникальное описание "месседжа"). Эту ссылку возвращает виртуальный метод.

Какие ограничения этого подхода: С -fno-rtti доступен только downcast строго на указанный класс - потомок класса Message.

2️⃣ LLVM: своя реализация RTTI для быстродействия.

Clang и LLVM имеют большую иерархию типов и делают огромную кучу проверок на типы. Большая часть кода в компиляторах (оптимизации, кодогенерация, ...) завязана на поиск специфических паттернов и операциях на них. Для этого необходимо проверять тип объектов в овер9000 местах, поэтому быстродействие dynamic_cast становится узким местом.

А быстродействие у dynamic_cast сравнительно плохое. Он должен делать обход иерархии наследования и вычисляет путь обхода динамическим образом. Это на несколько порядков медленнее, чем просто вызвать виртуальный метод и что-то сравнить.

В документации есть крутая статья, как сделать свой RTTI "почти как в LLVM" - How to set up LLVM-style RTTI for your class hierarchy. Для этого заводится специальный enum, и каждый класс реализует статический метод classof. Вместо обхода иерархии наследования делается один вызов виртуального метода!

Какие ограничения этого подхода: Дополнительный код - enum, статический метод в каждом классе. Нужно следить за тем, чтобы соответствие между enum и классами не разломалось (хотя тут могут помочь кодогенераторы). Эта схема работает, только если иерархия классов известна заранее (стандартный C++ RTTI такого не требует).

Всего известно три главных аргумента "против RTTI":
🅱️ Занимает память в бинарнике - очень сомнительный аргумент. RTTI не требует столько памяти, чтобы это стало заметно, по крайней мере в 2023 году.
🅱️ Медленно работает - хороший аргумент, если dynamic_cast<> является узким местом в программе. Но это должна быть специфическая программа, как поиск паттернов в структурах с большой иерархией классов... (например, компилятор C++)
🅱️ Его использование - ошибка дизайна - неожиданный аргумент, но именно по этой причине RTTI запрещен в Google C++ Style Guide. По ссылке есть описание "почему это плохо". Конечно, из каждого правила есть исключение.

#story

Информационное насилие: курс молодого бойца 🔫

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

Есть такой деятель, как Андрей Викторович Столяров. Дело в том, что многие люди, которым доводится контактировать с ним, испытывают спектр различных эмоций. Неполный список групп людей, постигших мудрость:
1️⃣ Жители linux.org.ru и прочих форумов. Запомнился розыском CMS на C/C++, критикой термина GNU/Linux, и просто комментариями с нестандартными речевыми оборотами в адрес тех, с кем он несогласен.
2️⃣ Студенты ВМК МГУ. Запомнился ведением занятий по Jabber во время ковида (об этом позже), неодобрительными отзывами на дипломные работы, неуважением к студентам с Windows и/или Code::Blocks на ноутбуке. Также благодаря ему первокурсники учат Pascal.
3️⃣ Его ученики. Запомнились пранкерским разоблачением Rust (rustmustdie.com), в ответ на что неравнодушные люди выпустили разоблачение разоблачения Rust (habr). Затем джихад был объявлен Сишке (cmustdie.com), но это уже было никому не интересно.
4️⃣ Зрители АйТиБороды, посмотревшие 4-часовое интервью. К сожалению, интервьюер не развел его на срач ИРЛ, а то бы просмотров было в 10 раз больше.

У Столярова есть idée fixe - теория информационного насилия. Можно считать, что это новая философская школа мысли, но по факту это просто другое агрегатное состояние "философии" Александра Гельевича Дугина - эклектичный микс разных аксиом. Это рационализаторство собственных предпочтений, оформленное в виде "как бы" философии.

Интересно, что, так сказать, magnum opus Столярова можно посмотреть в формате видеороликов - ссылка на YouTube.

Арсенал цитат из этих видеороликов:

"Пилотный выпуск"
- Информационное насилие - такая штука, исследованием которого я занимаюсь с 97 года.
- Браузер вообще не предназначен для просмотра видео, для этого есть другие программы, а браузером нужно смотреть гипертекст.

"О запрещенных книгах"
- Я признаюсь, я даже "Mein Kampf" читал, и знаете, книжка-то так себе, не умел Гитлер книжки писать.
- Какая-то непонятная шушера за меня решает, что мне читать, а что не читать.

"I don't like spam!"
- Был такой сервис - телеконференция NNTP. Нету больше этих конференций, они в районе 2000 года благополучно загнулись, потому что там оказалось невозможно устроить защиту от спама.
- Тут речь идет не только о рекламе. Многие пытались посылать такое всем получателям своей адресной книги: "А котеночек никому не нужен?" - да не нужен, блин, мне котеночек, и никому из них не нужен котеночек!

"История с телеграмом"
- Я вам открою один секрет. Меня нет в телеграме, меня нет в вотсапе, меня нет вконтактике, меня нет в фейсбуке. В этом зловредном ютубе я появился только потому, что Навальный объявил конкурс, иначе бы меня и здесь не было.
- Мне интересно вот что: когда ВКонтакте отжали у Павла Дурова, хоть бы кто-нибудь стёр свой аккаунт?
- Я ничего не имею против Павла Дурова, ну кроме того что он, зараза, уже вторую проприетарную систему поднимает. <...> Выглядит он красиво, презентабельно, хороший парень такой. Айтишник, опять же.

"В чью пользу авторское право?"
- Информация как таковая не может иметь денежной стоимости.

"Про DRM, Всемирную паутину, ..."
- Техническая стандартизация это особый и особо опасный вид международного терроризма. <...> Такие организации, как ISO, это на самом деле террористические группы.

Некоторые видео лучше посмотреть самому, так как они просто необычные:
"I don't like spam" - исторический обзор возникновения спама.
"Об основателях рунета" - про каких-то ноунеймов, с которым личные счета из-за смерти ЖЖ.
"Спам из мэрии Москвы" - про чудо спамерской инженерной мысли и письмо в суд.
"В чью пользу авторское право?" - жуткий срыв покровов над книжными издательствами.
"Безобидный гипертекст и коварный джаваскрипт" - просто бриллиант, можно разбирать на цитаты.

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

#story

Как сделать программу для читов в играх ⌨️

«Я буду устанавливать сейчас все игры»
- Сашко «Компьютерный Монстр»

Когда-то давно я познакомился с программой ArtMoney. Эта программа шла на диске к журналу "Лучшие Компьютерные Игры". Она была очень простой, и я быстро смог настроить бесконечную валюту в игре Spore.

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

Я решил поисследовать, как работают такие программы. Так как я не пишу под Windows, то исследую аналог для Linux, особой разницы не должно быть 😁 Это программа scanmem.
В этой программе также можно искать нужный адрес с переменной. Можно искать не только конкретное значение, но еще промежуток значений, а также "значение по адресу больше/меньше/равно/не равно чем было в прошлый раз" и так далее.
Такое бывает нужно, если например в игре есть "полоска здоровья" без числового значения, про которое известно, что оно становится больше/меньше чем в предыдущий раз.

Проверяется, что scanmem был запущен из-под суперюзера (sudo scanmem), без этого нельзя "следить" за другим процессом (если он не является процессом-"ребенком").
Проверка происходит через getuid() == 0 - uid суперюзера равен 0.

У процесса игры надо увидеть его виртуальное адресное пространство. Это память, которую игра использует и где надо будет фильтровать адреса. Увидеть регионы непрерывно занимаемой памяти может любой (в смысле не только суперюзер), прочитав файл /proc/<pid>/maps:

    cat /proc/<pid>/maps  # вывод в терминал

Вывод примерно такой:

559b8c5d1000-559b8c5f2000 rw-p 00000000 00:00 0                          [heap]
7faa72001000-7faa72023000 rw-p 00000000 00:00 0
7faa72023000-7faa72055000 r--p 00000000 08:30 3023                       /usr/lib/locale/C.UTF-8/LC_CTYPE
7faa726e0000-7faa726e1000 rw-p 0002d000 08:30 11854                      /usr/lib/x86_64-linux-gnu/ld-2.31.so
7faa726e1000-7faa726e2000 rw-p 00000000 00:00 0
7ffeb2f53000-7ffeb2f74000 rw-p 00000000 00:00 0                          [stack]

(подробнее об этих файлах можно прочитать тут)

scanmem просто открывает этот файл (через fopen) и парсит каждую строку. Оставляются только регионы с возможностью записи (флаг w). Обычно этого флага нет у загруженных секций .text (исполняемый код бинарника) и .rodata (константные данные).

Те, кто не программируют активно под Linux, могут удивиться двум специфичным вещам:
1️⃣ Очень многие данные о системе/процессе можно увидеть, прочитав особые файлы, хотя видно что это НЕ "стандартные" файлы, данные в них генерируются на ходу! Это концепция "everything is a file". 😐
2️⃣ Программы реально завязываются на формат вывода линуксовых тулз/файлов, в этом ничего страшного нет. Например, весь Android завязан на вывод тулзы wpa_supplicant (для поиска WiFi).

scanmem ждет, пока юзер введет текущее значение из игры. После ввода значения вызывается ptrace для слежки за другим процессом (target - process id процесса игры), из-за этого процесс игры остановится (кинет сигнал SIGSTOP):

ptrace(PTRACE_ATTACH, target, NULL, NULL)

Затем можно читать память процесса. Делать это можно двумя способами.
В первом способе (как бы вы думали?) снова открывается файл, на этот раз /proc/<pid>/mem.
Во втором способе можно читать память через ptrace: ptrace(PTRACE_PEEKDATA, target, cur_address, NULL)

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

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

#madskillz

Нестандартные представления строк ✨

В "стандартном" C++ есть три основных представления для строк. Не будем учитывать "составные" классы (как std::stringstream), у которых нет уникальных концепций.

=====
1️⃣ const char* - просто указатель на начало строки где-то в памяти. Обычно если итерироваться по указателю, то когда-то достигнем нулевой байт \0 (нуль-терминатор), который указывает на конец строки. Все строковые алгоритмы Си завязаны на признак \0 как на конец строки.

=====
2️⃣ std::string - класс строки, владеющий памятью для нее в куче. Запись std::string s = "abcd"; значит, что где-то в куче занята память под байты abcd\0. Известно, std::string гарантированно нуль-терминирован (начиная с C++11).
Маленькие строки полностью помещаются на стек (это называется small string optimization), но пока проигнорируем это.

=====
3️⃣ std::string_view - класс строки, не владеющий памятью. Представляет собой пару const char* s (начало строки) и size_t len (длину строки).
Не обязательно верно то, что *(s + len) == '\0'. 😁 Ведь std::string_view указывает не на всю строку, а только на какую-то ее часть.

=====
Класс std::string поведением похож на контейнер std::vector<char>. Можно посмотреть на какие-нибудь неклассические контейнеры, чтобы создать новые строковые классы, которых нет в стандартном C++.
4️⃣ SmallString - класс строки, владеющий памятью для нее, с поведением как у SmallVector<char>. Реализован в LLVM.
Запись

    std::string s1;
    SmallString<256> s2;

Дает два объекта s1 и s2, у которых одинаковый набор методов, но s2 хранится на стеке, если размер строки не превышает 256 символов (планируется, что так будет в 99.9% случаев). Если размер все-таки превысили, то строку начинают хранить в куче.

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

Major + "." + Minor + "." + VersionPatch

В этом случае происходит создание 3 (!) лишних "временных" строк с аллокациями памяти, то есть делается строка Major + ".", потом строка (Major + ".") + Minor и так далее. Более того, итоговая строка (4-я по счету) тоже по сути лишняя, если мы хотели сразу записать итог в какой-нибудь файл, а не хранить результат сложения.

В кодовой базе LLVM есть решение, которое сложно для понимания, но мы его разберем:
5️⃣ Twine - класс "сумма строк". Документация по Twine, но больше информации в исходнике.

Трудности начинаются на уровне названия класса, как у не-носителя английского 😁 Я так и не понял смысл названия.
Вообще, трудности сначала были со словом string. До того, как я начал программировать, у меня это ассоциировалось со стрингами, которые носил Борат. У этого слова куча значений, пусть в нашем случае это будет шнур.
Теперь посмотрим на слово twine. У него тоже вагон значений, пусть в нашем случае это будет бечёвка, пнятненько?
</конец бесполезного абзаца>

Этот класс опасный: он полагается на стремное правило Reference Lifetime Extension, а также на не менее стремное правило, что объекты, созданные для использования в full-expression, не удаляются до конца выполнения этого full-expression (сформулировал как смог).

Функция должна принимать Twine по константной ссылке:

void foo(const Twine& T);

А подавать туда Twine нужно не отходя от кассы, чтобы сработало правило RLE:

foo(Twine(Major) + "." + Minor + "." + VersionPatch);

Благодаря правилу про full-expression, все составные части строки "живы" на стеке, пока не выполнится вызов foo.

Twine внутри себя выглядит как бинарное дерево. У него два "ребенка":

    Child LHS;
    Child RHS;

Каждый ребенок это указатель на какой-нибудь строковой объект: const char, или std::string, или std::string_view, или другой Twine ("поддерево"). Также для удобства поддерживаются числа 😁

    union Child
    {
      const Twine *twine;
      const char *cString;
      const std::string *stdString;
      /* ... */
      int decI;
      /* ... */
    };

ПРОДОЛЖЕНИЕ В ПЕРВОМ КОММЕНТАРИИ (у телеграма ограничение по размеру постов 😟)

#opensource

Обзор на Boost 🆘

Boost это широко известный набор библиотек для C++. Boost оказал большое влияние на развитие C++, но что осталось от его влияния в 2023 году?

Чтобы не копаться в библиотеках самому, можно почитать про разработку в Boost в крутой книге крутого Антона Полухина, которой уже прилично лет, но ее держат в актуальном состоянии.

Надеюсь, не проспойлерю книгу (на сайте все равно есть исходники примеров), но очень, очень много чего в Boost вошло в стандарты C++, и вы половину книги будете читать про то, как работают классы boost::shared_ptr<T> и boost::string_view. Работают они почти так же, как канонические std::XXX, но иногда отличия бывают (в книге рассказано, какие именно).

Эта часть Boost отдала свои жизненные соки Стандарту C++ и перестала быть интересной (кроме как тем, кто пишет на C++ старого стандарта и не может перейти на более новый стандарт).

Далеко не все куски Boost находятся в ажурном состоянии. Сейчас в Boost состоит 169 библиотек, во многом независимых друг от друга. Практически у всех библиотек есть какие-то реальные проблемы из этих:

1️⃣ Не обновлялась с ~2006 года. Да, некоторые библиотеки просто написаны сумрачным гением тысячу лун назад и заброшены.

2️⃣ Стала неактуальной после вхождения в Стандарт C++. Это описал выше.

3️⃣ Повторяет другие библиотеки по функциональности. Бывают приколы как тупо Boost.Variant и Boost.Variant2.

4️⃣ Есть нишевая библиотека вне Boost с лучшим функционалом. Можно сравнить Boost.JSON и nlohmann/json.

В целом Boost так себе в нишевых библиотеках, количество контрибьюторов в отдельную библиотеку намного ниже, чем в популярный проект.
Иногда кто-то хочет усугубить проблему и добавить библиотеку по типу Boost.Lua (еще одну к овер9000 библиотекам про Lua), но к счастью количество библиотек растет не так быстро.
Видимо, делаются попытки с уверенностью, что Boost сам по себе типа как бы бренд, и библиотека становится лучше как бы самим фактом наличия в Boost... Что не так.

5️⃣ Лютая дичь и эрзац-компилятор. Это легендарные библиотеки-монстры, которые выглядят очень странно, потому что нестандартными способами обходят ограничения компиляторов, или просто "чем хуже тем лучше". Я бы отнес их использование к ненормальному программированию.

Например, Boost.Hana для метапрограммирования

struct Person {
  BOOST_HANA_DEFINE_STRUCT(Person,
    (std::string, name),
    (int, age)
  );
};

Boost.Spirit как LL-парсер, который притом header-only (поэтому собирается по 10 минут).

Есть библиотеки для имитации std::move до C++11 и прочие попытки перепрыгнуть выше крыши.

6️⃣ Не лучшая техническая реализация. Некоторые фанаты open source верят в миф, что стоит проекту бытоваться открытым, как тут же появляются "тысячи глаз", которые следят за его качеством. На деле никому это нафиг не нужно это вряд ли так, и большой вопрос, где качество кода в среднем лучше.

Из тех библиотек, что я активно исследовал:

Boost.ScopeExit - в другом опенсорсном проекте есть реализация подобной штуки без необходимости писать BOOST_SCOPE_EXIT_END в конце.

Boost.SmallVector - официально стырен из LLVM, а не придуман уникально. Почему бы тогда не использовать библиотеку LLVM?

Boost.DynamicBitset - по состоянию на 2018 год оно использовало захардкоженные таблицы, чтобы искать количество бит в числе или типа того.
Я туда сделал коммиты (github) и ускорил некоторые методы в 2 раза, если система поддерживает интринсики как __builtin_popcount.

Offtop: в 2018 году я исследовал dynamic bitset, потому что программировал тогда шахматы с кастомным размером доски (не 8x8) и std::bitset<64> не подходил. Но в итоге забросил идею, а запрограммировал шахматы только в 2022 году без dynamic bitset (мой лонгрид на хабре).

🤔 Таким образом, в 2023 году Boost может быть не лучшим выбором для активного использования!

#story

Сделай свой std::flat_set из C++23 📦

В C++23 были приняты новые контейнеры std::flat_set, std::flat_map (и их multi-варианты), аналогично уже существующим std::set и std::map.

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

API flat_set почти не отличается от set. Добавлены новые конструкторы и перегрузки insert. Заменены редкие методы:
node_type extract(...)
insert_return_type insert(node_type&& nh);
то есть те, где юзер должен был работать с вершинами красно-черного дерева.
Можно просто заменить тип на новый и почти наверняка это скомпилируется.

Новые контейнеры являются адаптерами. Это такие контейнеры, которые сами не делают ничего "тяжелого", а только держат у себя другой контейнер и все методы пробрасывают туда. В C++ уже было три таких контейнера - stack, queue, priority_queue:

    template<class T, class Container = std::deque<T>> class stack;
    template<class T, class Container = std::deque<T>> class queue;

flat_set (и ему подобные) такой же адаптер:

    template<class Key, class Compare = less<Key>, class KeyContainer = vector<Key>> class flat_set;

То есть множество представляется (по умолчанию) в виде отсортированного вектора (но можно дать и другой класс - static_vector, small_vector).

Пусть у нас есть std::vector<T> data. Попробуем реализовать для него все основные методы flat_set сами, в упрощенном виде (без кастомных компараторов и прочего) 😝

0️⃣Итераторы begin/end/..., методы empty()/size()/max_size()
Подобные методы не рассматриваем, они просто перенаправляют вызовы в сам контейнер

decltype(auto) begin() noexcept { return data.begin(); }

1️⃣ Конструктор flat_set(container_type cont);
Конструкторов там примерно 24 штуки на разные случаи жизни. Можно реализовать случай, когда дается контейнер, который изначально не отсортирован и там могут быть повторяющиеся элементы - с использованием std::unique:

    data = std::move(cont);
    std::sort(data.begin(), data.end());
    auto last = std::unique(data.begin(), data.end());
    data.erase(last, data.end());

Сложность этого метода O(NlogN)

2️⃣ Вставка insert(const value_type& x)
Нужно найти место, куда вставить новый элемент. Если он уже существует, то вставлять не нужно. Это можно делать бинарным поиском через std::lower_bound и вставкой в вектор в этом место.

    auto lower = std::lower_bound(data.begin(), data.end(), x);
    if (lower == data.end() || *lower != x) {
        data.insert(lower, x);
    }

Сложность этого метода O(N) в общем случае и амортизированный O(logN) в случае вставки в конец. "Амортизированный" - потому что можно попасть на реаллокацию вектора 😁

3️⃣ Удаление erase(const key_type& x) и прочие методы (find, contains, ...)
Действуют по одинаковому принципу с insert - найти место этого элемента бинарным поиском и что-то с этим сделать.

    auto lower = std::lower_bound(data.begin(), data.end(), x);
    if (lower != data.end() && *lower == x) {
        data.erase(lower);
    }

Сложность этого метода O(N) в общем случае и O(logN) в случае удаления с конца.

4️⃣ Слияние двух flat_set
В некоторых случаях надо делать слияние двух отсортированных векторов. Это стандартный алгоритм, его часто спрашивают на собеседованиях.

Если нужно вставить несколько элементов, то можно вызвать такой метод, который вставит каждый элемент по отдельности за O(N), с итоговой сложностью до O(N^2) в среднем:

    void insert(InputIterator first, InputIterator last);

Но если есть знание, что вставляемые элементы [first, last) уже отсортированы, то можно вызвать другой метод с "мусорным" объектом в начале, который сделает слияние, это будет работать за O(N), что может быть быстрее:

    void insert(sorted_unique_t, InputIterator first, InputIterator last);

Такую задачу можно решить на Leetcode - Merge Sorted Array 🙂

#madskillz

Сделай свой эмулятор процессора Motorola 68000 🖥

В свободное время программисты могут заниматься странными вещами. Например, я сделал эмулятор процессора Motorola 68000. Сейчас там поддержано 94% инструкций и все нужные абстракции, это заняло ~2500 строк кода.

Мне было интересно, рекомендую это делать всем, кто хочет лучше понять работу процессора 🍅

m68k (сокращенно) это процессор, сильно обогнавший свое время. Он использовался на протяжении десятилетий в компьютерах Macintosh, Amiga, Atari, приставке Sega Mega Drive, и прочих устройствах.

1️⃣ Представление в C++

В архитектуре процессора уже есть элементы 32-битовости, но с ограничениями.
Всего есть 16 регистров 32-битных (и 1 регистр 16-битный).
Несмотря на то, что "адресные" регистры (A0-A7) 32-битные, по факту для адреса берутся младшие 24 бита. То есть адресуется пространство в 16 мегабайт памяти.
Процессор поддерживает зачаток виртуализации для многозадачных систем - обращение к регистру A7 по факту будет обращением либо к USP, либо к SSP, в зависимости от флага в статусном регистре.
🔍 registers.h - представление регистров

Процессор может что-то читать/писать по адресам 0x000000 - 0xFFFFFF (24 бита), не обязательно это будет физическая память. Иногда запись в определенные адреса будет влиять на периферийные устройства. Поведение определяется "шиной".
Эмулятор имеет дело с интерфейсом. Запись/чтение могут спровоцировать ошибку по любой причине (например, чтение по нечетному адресу). Я не использую исключения C++ в эмуляторе - объект ошибки возвращается из методов.
🔍 i_device.h - интерфейс записи/чтения памяти

"Текущее состояние" эмулятора, которое можно менять, можно представлять так:

struct TContext {
    NRegisters::TRegisters& Registers;
    NMemory::IDevice& Memory;
};

Операнды в инструкциях ("цели") могут указывать на адрес в памяти/регистр большим количеством способов. Для этих способов можно выделить примерно такой интерфейс с общим методом чтения/записи данных:
🔍 target.h - представление операнда в инструкциях

Последнее, самый большое представление - у инструкций. У них есть "тип" инструкции и все нужные параметры. Ассемблер очень "ортогональный", поэтому представление в виде набора переменных подходит лучше всего.
🔍 instructions.h - представление инструкций

2️⃣ Как реализовать и протестировать инструкции

Каждая инструкция занимает 2 байта. Иногда могут потребоваться 2/4 байта дополнительных данных после инструкции (обязательно четное число).

Декодирование инструкции можно написать глядя на крутую таблицу от GoldenCrystal (сайт регулярно лежит, в комментариях к посту есть PDF).

Краткое описание инструкции можно читать в этой markdown-документации. Иногда этого недостаточно, тогда можно читать длинное описание в этой книге.

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

Мне очень помогли тесты из этого репозитория. На каждую инструкцию есть 8000+ тестов, которые покрывают все возможные случаи. Суммарно тестов чуть больше миллиона.
Они могут находить даже самые мелкие ошибки - нередко бывает ситуация, что не проходятся ~20 тестов из 8000.
Например, инструкция MOVE (A6)+ (A6)+ (обращение к регистру A6 делается с пост-инкрементом) должна работать не так, как я реализовал, поэтому я сделал костыль, чтобы работало корректно.

Продолжение в комментариях (эмуляция программ)

#opensource

Создание своих плагинов для Vim 👩‍💻

Я не люблю холивары, в том числе на тему текстовых редакторов. У людей есть баг - они рационализируют свой выбор и убеждения.
В худших случаях это вытекает в поиск того, за чей счет бы самоутвердиться, и приписывании другой стороне ложных свойств. Так, многие любители не-Vim уверены, что в Vim нет автокомплита, а многие любители Vim бывают уверены в каких-то вовсе страшных вещах насчет не-Vim.
Я сознательно отказываюсь от рационализации своего выбора. Например, довод о "быстроте редактирования" в Vim неактуален в обстановке, когда программист намного дольше читает уже написанный код или обсуждает решение, чем пишет новый код.

Vim👩‍💻 (позже его форк Neovim👩‍💻) для меня основной редактор с 2016 года, а полностью сменил гендер "акклиматизировался" я где-то за год (за сравнимое время можно полностью выучить любой другой редактор).
В Vim каждый сам собирает свою "IDE" из 15-20 плагинов и кучи настроек.

Vim я открываю прямо на удаленной машине - потому что работаю в виртуалке.

Для интереса можно сделать свои специфические плагины, чтобы "IDE" стала удобнее. На Neovim плагины можно писать на языке Lua. Чтобы понять, что нужно делать, можно для начала почитать эту и эту доки, но в процессе написания все равно надо много гуглить.

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

Сейчас я для работы использую три самодельных плагина, которые очень помогают решать задачи, которые раньше делал ручным способом. Они специфические для компании 😁

1️⃣ Ссылка на CodeSearch
🔍 Гифка (10.7 MB)
😱 Исходник
Раньше надо было копировать текст в терминале (выделение мышью и Ctrl+C), идти на сайт внутреннего поиска кода, вставлять текст Ctrl+V, экранировать спецсимволы... Сейчас можно выделить текст (или не выделять, если нужно найти одно слово под курсором) и нажать Ctrl+S (или ввести команду :CodeSearch, но хоткей быстрее), чтобы вывелась правильная ссылка.

Это конечно никуда не годится, лучшее решение - встроить CodeSearch например в плагин Telescope 😁

По исходнику видно, насколько много костылей в Vim. Например, "слово под курсором" ищется так: vim.fn.expand('<cword>'), а позиции начала и конца выделения это '< и '>.

2️⃣ Вставка на Pastebin
🔍 Гифка (13.3 MB)
😱 Исходник
Есть тулза, чтобы отправлять файлы в нечто вроде местного Pastebin. Чтобы вставить кусок логов или кода, приходилось выделять их, делать временный файл, вставлять выделенное, сохранять текст, вызывать тулзу в другой вкладке... Сейчас можно просто выделить текст (или не выделять, если нужно вставить весь файл) и нажать Ctrl+P (или ввести команду :Paste), чтобы плагин все это сделал и показал ссылку.

Видно еще больше костылей: отсутствие многих базовых функций (их надо писать самому), выделенный текст копируется в регистр " или 0, а путь до текущего файла можно вытащить через vim.fn.expand('%') - это все надо помнить или очень сильно читать документацию.

3️⃣ Автоматический code style при сохранении
🔍 Гифка (44.1 MB)
😱 Исходник
Используется тулза clang-format для форматирования кода, но с локальными хаками и особенностями. Если код не удовлетворяет код-стайлу, то падает проверка на CI, и приходится запускать тулзу, потом смотреть, что она нормально отработала, закрывать и открывать файл, и так далее... Сейчас эта тулза запускается сама, каждый раз после сохранения файла, меняя только нужные участки кода.

Таким образом, можно написать свои плагины, чтобы уменьшить боль от ручного труда. Это, конечно, базовые плагины, и не сравнятся с монстрами наподобии Telescope или Gitsigns. К "большим" плагинам можно делать свои плагины. 😐

Гифки записывал через blue-recorder, визуализация нажатий на кнопки через screenkey.