Небольшой путеводитель по серии статей про трюки:

1. Математика, биты, магия и немного ненормального программирования на C
2. Фокусы, хаки, магия и прочее ненормальное программирование на C
3. Тёмная сторона Си: трюки, хаки, магия и алгоритмы

Статьи в большинстве своем независимы, можно читать с любой части, единственное что есть - эволюция бенчмарков.

16 и 23 декабря выйдут 4 и 5 часть соответственно, а сейчас пока 6 часть в процессе написания.

Спасибо всем за плюсы и поддержку!

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

Эта метрика активно используется для исправления ошибок в словах, поиска дубликатов текстов, сравнения геномов и прочих полезных операций с символьными последовательностями. Если вы хотите подробнее узнать о математических основах этого алгоритма, то есть [эта замечательная статья](https://habr.com/ru/articles/676858/).

int min2(int a, int b) {
    return a < b ? a : b;
}

int min3(int a, int b, int c) {
    return min2(a, min2(b, c));
}

int levenshtein(const char* s1, const char* s2) {
    int n = strlen(s1);
    int m = strlen(s2);

    if (n == 0) {
        return m;
    }
    if (m == 0) {
        return n;
    }

    if (n > m) {
        const char* tmp = s1;
        s1 = s2;
        s2 = tmp;
        int t = n;
        n = m;
        m = t;
    }

    int* prev = (int*)malloc((n + 1) * sizeof(int));
    int* curr = (int*)malloc((n + 1) * sizeof(int));

    for (int i = 0; i <= n; i++) {
        prev[i] = i;
    }

    for (int j = 1; j <= m; j++) {
        curr[0] = j;

        for (int i = 1; i <= n; i++) {
            int cost = (s1[i - 1] == s2[j - 1]) ? 0 : 1;
            curr[i] = min3(prev[i] + 1, curr[i - 1] + 1, prev[i - 1] + cost);
        }

        int* tmp = prev;
        prev = curr;
        curr = tmp;
    }

    int result = prev[n];

    free(prev);
    free(curr);

    return result;
}

В начале функция обрабатывает тривиальные случаи, когда одна из строк пуста. Затем, чтобы оптимизировать использование памяти, строки переставляются, гарантируя, что первая строка s1 является более короткой. Вместо хранения всей матрицы размером (n+1) x (m+1) алгоритм использует только два одномерных массива длиной (n+1), что значительно сокращает потребление памяти.

Алгоритм заполняет первый массив базовыми значениями. Затем для каждого символа j второй строки s2 он вычисляет новую строку матрицы в массиве curr. Для каждого символа i первой строки s1 вычисляется стоимость трех возможных операций: удаление (стоимость из предыдущей строки + 1), вставка (стоимость из текущей строки + 1) и замена или совпадение (стоимость из предыдущей диагонали + 0 или 1). Из этих трех вариантов выбирается минимальная стоимость. После обработки всех символов s1 массивы prev и curr меняются местами для следующей итерации.

После завершения циклов результат — минимальная стоимость редактирования — хранится в prev[n]. Память освобождается, и значение возвращается.

Если вам нравится тема таких алгоритмов на C, ставьте реакции⚡️

Вычисление числа π через ряд Лейбница

Алгоритм Лейбница — это один из самых простых способов получить π, хотя и не самый быстрый. Формула выглядит так: π/4 = 1 - 1/3 + 1/5 - 1/7 + 1/9 - ... и так до бесконечности. Знаки чередуются, а в знаменателе стоят нечётные числа. Чем больше слагаемых мы посчитаем, тем точнее будет результат. В конце это всё умножается на 4, чтобы получить само π.

#include <omp.h>

double calculate_pi_leibniz(long long iterations) {
    double pi = 1.0;
    long long i;
    int sign = -1;

    #pragma omp parallel for reduction(+:pi) private(sign)
    for (i = 1; i < iterations; i++) {
        sign = (i % 2 == 0) ? 1 : -1;
        pi += sign / (2.0 * i + 1.0);
    }

    return pi * 4;
}

int main(int argc, char *argv[]) {
    long long iterations = 1000000000;
    if (argc > 1) {
        iterations = atoll(argv[1]);
    }

    double start_time = omp_get_wtime();
    double pi = calculate_pi_leibniz(iterations);
    double end_time = omp_get_wtime();

    printf("π = %.15f\n", pi);
    printf("Iters: %lld\n", iterations);
    printf("Time: %.3f seconds\n", end_time - start_time);

    return 0;
}

OpenMP здесь ускоряет вычисления, распараллеливая цикл на несколько ядер процессора. Все потоки считают свою часть суммы, а потом результаты объединяются в один. Без этого работа шла бы только на одном ядре и дольше.

Вот такой вывод получился у меня при -O2:

π = 3.141592652589449
Iters: 1000000000
time: 0.160 seconds

В 2005 году id Software опубликовала под лицензией GPL-2 исходный код своей игры 1999 года Quake III Arena. В файле code/game/q_math.c есть функция для вычисления обратного квадратного корня числа, которая на первый взгляд выглядит очень любопытным алгоритмом:

float Q_rsqrt( float number )
{
  long i;
  float x2, y;
  const float threehalfs = 1.5F;

  x2 = number * 0.5F;
  y  = number;
  i  = * ( long * ) &y;            // evil floating point bit level hacking
  i  = 0x5f3759df - ( i >> 1 );               // what the fuck?
  y  = * ( float * ) &i;
  y  = y * ( threehalfs - ( x2 * y * y ) );   // 1st iteration
//  y  = y * ( threehalfs - ( x2 * y * y ) );   // 2nd iteration, this can be removed

#ifndef Q3_VM
#ifdef __linux__
  assert( !isnan(y) ); // bk010122 - FPE?
#endif
#endif
  return y;
}

Как же работает этот алгоритм? Он выполняется в два этапа:

1. Получение грубой аппроксимации y обратного квадратного корня нужного числа number:

y  = number;
i  = * ( long * ) &y;
i  = 0x5f3759df - ( i >> 1 );
y  = * ( float * ) &i;

2. Уточнение аппроксимации при помощи одного шага метода Ньютона-Рафсона (NR):

const float threehalfs = 1.5F;
x2 = number * 0.5F;
y  = y * ( threehalfs - ( x2 * y * y ) );

Алгоритм принимает 32-битное число с плавающей запятой (одинарной точности в формате IEEE 754) в качестве исходных данных. Точность алгоритма — менее 0,2% в меньшую сторону и никогда — в большую. Это не хватает для настоящих численных расчётов, но достаточно для трёхмерной графики.

Подробнее о работе данной функции можно прочитать в этой статье и на странице в википедии.

Для проверки можно немного изменить код:

float Q_rsqrt(float number) {
    int32_t i;
    float x2, y;
    const float threehalfs = 1.5F;

    x2 = number * 0.5F;
    y  = number;
    i  = * ( int32_t* ) &y;
    i  = 0x5f3759df - ( i >> 1 );
    y  = * ( float* ) &i;
    y  = y * ( threehalfs - ( x2 * y * y ) );
    return y;
}

И мы должны получить почти-что правильный результат: Q_rsqrt(25.00) = 0.199690. Для точности можно добавить еще одну итерацию Ньютона y = y * (threehalfs — (x2 * y * y));: Q_rsqrt(25.00) = 0.199999.

https://habr.com/ru/companies/timeweb/articles/971528/

Четвертая часть серии статей про трюки на си!

В этой статье будет еще больше всевозможных генераторов псевдослучайных чисел, гонок за скоростью и производительностью, алгоритмов, хаков и трюков!

Вот и наступила 4 часть! В этой статье мы погружаемся в менее известные хаки, фаны, алгоритмы на нашем любимом живом C!

Идиома RAII (Resource Acquisition Is Initialization)

В среде разработчиков C++ широко используется идиома RAII (Resource Acquisition Is Initialization). Её суть заключается в автоматизации управления жизненным циклом ограниченных ресурсов вычислительной системы (таких как память, файловые дескрипторы, сетевые соединения).

Типичный жизненный цикл ресурса включает три этапа:
1. Захват ресурса (выделение памяти, открытие файла, установка соединения).
2. Использование ресурса (операции чтения/записи, передача данных).
3. Освобождение ресурса (возврат памяти системе, закрытие дескриптора).

Идиома RAII гарантирует корректное освобождение ресурсов путём привязки их жизненного цикла к времени существования объектов C++. Это достигается через:
- Конструктор → захват ресурса
- Методы класса → использование ресурса
- Деструктор → автоматическое освобождение ресурса

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

Примеры из стандартной библиотеки C++:

1. std::unique_ptr — эксклюзивное владение ресурсом:

{
    std::unique_ptr<int> ptr(new int(42)); // Выделение памяти (захват)
    *ptr = 10; // Использование ресурса
} // Память автоматически освобождается (деструктор)

2. std::shared_ptr — разделяемое владение:

{
    auto ptr1 = std::make_shared<double>(3.14); // Захват ресурса
    {
        auto ptr2 = ptr1; // Копирование указателя
        std::cout << *ptr2; // Использование
    } // ptr2 уничтожается, ресурс сохраняется
} // ptr1 уничтожается → ресурс освобождается

Пользовательский класс RAII для работы с файлами:

class FileHandler {
public:
    explicit FileHandler(const std::string& path) 
        : file_(std::fopen(path.c_str(), "r")) // Захват ресурса
    {
        if (!file_) throw std::runtime_error("File open error");
    }

    void write(const std::string& data) {
        if (std::fputs(data.c_str(), file_) == EOF) {
            throw std::runtime_error("Write error");
        }
    }

    ~FileHandler() { 
        if (file_) std::fclose(file_); // Освобождение ресурса
    }

    // Запрещаем копирование
    FileHandler(const FileHandler&) = delete;
    FileHandler& operator=(const FileHandler&) = delete;

private:
    FILE* file_;
};

// Использование:
{
    FileHandler file("data.txt"); // Открытие файла
    file.write("Hello RAII"); // Запись данных
} // Файл автоматически закрывается

Ключевые преимущества подхода:
1. Детерминированное освобождение — ресурсы возвращаются сразу при выходе объекта из области видимости.
2. Исключение безопасности — корректная обработка исключений благодаря стековой раскрутке.
3. Инкапсуляция — логика управления ресурсом изолирована внутри класса.
4. Устранение ручного управления — исключены ошибки забытого освобождения ресурсов.

Джин

Однажды Линус Торвальдс шёл по пляжу, думал о том, что мы все живём в матрице, и грустно смотрел под ноги. В песке он заметил бутылку, подозрительно похожую на коньяк, и возрадовался. Но при ближайшем рассмотрении бутылка оказалась непрозрачной, с сургучной печатью, на которой проступал религиозный символ страны, с которой сложные отношения.

Линус конечно же применил брутфорс и открыл бутылку, из которой немедленно вылез джинн.

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

— А меньше желаний желать можно? — уточнил Линус, продолжая думать про матрицу.

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

— Тогда я хочу чтобы количество моих желаний уменьшилось на три.

— Зачем? — поинтересовался джинн.

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

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

— Ты просто сделай так, как я говорю, — посоветовал Линус.

Джинн вырвал жменьку волос из бороды, пошептал, поводил руками в воздухе, и ничего не произошло. Тогда он достал из широких шаровар записной свиток из папируса.

— У тебя теперь три желания, — прокомментировал он, сверившись с папирусом.

— O shit, — удивился Линус.

— Но вообще довольно здорово, — попытался ободрить его джинн. — Я никогда раньше не видел, чтобы человек загадал желание, и у него осталось столько же желаний. Даже если бесполезное. Хороший фокус для вечеринок.

— Двухбитная переменная, — удивился Линус. — Необычно.

— Может, дворец? — сочувственно предложил джинн. — Миллион динаров? 72 девственницы? Я могу, если что...

— Я хочу, чтобы переменная, хранящая информацию о доступных мне желаниях, стала 16-битной, определился Линус.

— Я всё ещё не понимаю, — покачал головой джин. — 900-е годы. До нашей эры.

— Это ничего, — ответил Линус, привыкший иметь дело с гуманитариями. — Ты просто сделай то что я сказал, слово в слово.

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

— У тебя теперь два желания, — развёл руками он.

— А вот теперь я хочу, чтобы у меня стало на два желания меньше.

Джинн вырвал волоски из подмышки, поколдовал и посмотрел в папирус.

— У тебя 65 535 желаний, — озадаченно сказал он.

Линус Торвальдс нехорошо улыбнулся.

— Я же говорил, что мы живём в матрице. Присаживайся. Записывай. Значит, во-первых...

me cleaner

me cleaner — это Python-скрипт, предназначенный для модификации прошивки Intel Management Engine (ME) с целью снижения её взаимодействия с системой.

Intel ME, присутствующий на большинстве материнских плат Intel с 2006 года, выполняет функции, требующие полного доступа к системе, однако его прошивку невозможно полностью отключить или удалить с 2008 года без последствий.

me cleaner предлагает решение, позволяющее оставить Intel ME активным только в процессе загрузки, а затем отключить его во время обычной работы.

Скрипт совместим с большинством платформ Intel.

https://github.com/corna/me_cleaner

Интерпретатор Python, написанный на Python в 500 строк кода

Byterun - это интерпретатор Python. Работая над Byterun, автор обнаружил, что фундаментальная структура интерпретатора Python легко укладывается в ограничение на размер в 500 строк. В этой статье рассмотрена структура интерпретатора и дан контекст для его дальнейшего изучения.

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

Byterun был написан Недом Батчелдером, опираясь на работу Пола Шварца. Его структура похожа на основную реализацию Python, CPython, поэтому понимание Byterun поможет вам понять интерпретаторы в целом и интерпретатор CPython в частности. (Если вы не знаете, какой Python вы используете, то, скорее всего, это CPython). 

Статья: https://aosabook.org/en/500L/a-python-interpreter-written-in-python.html
Github: https://github.com/nedbat/byterun

https://pshenok.github.io/server-survival/

Довольно залипательная игра,позволяющая прокачать system design.

Игра в жанре tower defence, где мы управляем серверной инфраструктурой.

PEP-799: Семплирующий профилировщик встроенный в Python 3.15+

Краткий обзор: https://docs.python.org/3.15/whatsnew/3.15.html#whatsnew315-sampling-profiler
Документация: https://docs.python.org/3.15/library/profiling.sampling.html

Кратко:
- В 3.15 cProfile (написан на C) был перемещен в profiling.tracing
- В 3.15 profile (написан на Python) стал deprecated, его уберут в 3.17
- Добавили новый profiling.sampling (кодовое имя `tachyons`), о нем и поговорим
- А еще добавили встроенные TUI (на скриншоте) и GUI

Ключевые фичи:
- Almost Zero-overhead: добиваемся такого, за счет того, что переодически получаем готовые стектрейсы работающих процессов, не нужно добавлять инструментацию функций как в cProfile
- Не нужно менять существующий код
- Разные режимы работы: attach позволяет подключиться к работающему Python процессу, а run позволяет запустить код для профилировки
- Разные виды замеров: --mode wall, --mode cpu, --mode gil, --mode exception
- Поддержка тредов
- Поддержка asyncio с флагом --async-aware, можно смотреть даже suspended tasks с --async-mode=all
- Разные форматы вывода информации: --flamegraph, --pstats, --heatmap, --gecko
- --live вместе с TUI для отображения информации в реальном времени (как в top условном)
- Поддержка профилирования до уровня опкодов виртуальной машины, включая специализации
- Гибкая конфигурация буквально всего

Примеры запуска:
- python -m profiling.sampling run --flamegraph -o profile.html noscript.py - запускаем скрипты и генерим флеймграф
- python -m profiling.sampling attach --live $YOUR_PID - профилируем работающий процесс и получаем данные в реальном времени

На чем основана работа технически?

- PEP-768 с remote-debugging предоставляет техническую возможность быстро и легко получать семплы из виртуальной машины
- Для asyncio используется новый АПИ для async-aware call-graphs

Личное мнение: очень крутая фича, пока у меня вопросы по TUI / GUI. Не очень понимаю, зачем их затащили в stdlib. Зарепортил пару багов. На маке требуется запускать профилировщик с sudo -E. Остальное - нравится!
Кирилл вот тоже заценил.

Обсуждение: Что вы думаете о данной фиче? Как вы сейчас профилируете ваши приложения в разработке и в проде?

P.S. Последний пост в текущем году. Всех с наступающим! 🎄

| Поддержать | YouTube | GitHub | Чат |

https://habr.com/ru/companies/timeweb/articles/971962/

Вышла 5, юбилейная часть серии статей про трюки на си!

В этой статье будет еще порция свежих хаков, фанов, трюков, еще больше магии и скорости!

BusyBox — набор UNIX-утилит командной строки, представленный в виде единого исполняемого файла. Разработан в 1996 году Брюсом Перенсом.

Особенности:

Малый размер и низкие требования к аппаратуре.
Модульность: в момент компиляции можно включить или исключить все необходимые компоненты.
Распространяется под лицензией GNU GPL 2.

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

Вызвать BusyBox можно, введя команду в качестве аргумента в командной строке. Также можно использовать ссылки на двоичный файл BusyBox: например, ввод ln -s /bin/busybox ls ./ls заставляет BusyBox вести себя как команду ls (если команда ls была скомпилирована в BusyBox).

Busybox можно использовать в эмбеддед устройствах, загрузочных средах (многие могли столкнуться с ним во время фикса очередной проблемы загрузки). А также busybox используют минималистичные системы, например Tiny Core Linux (на хабре есть интересная статья о нем). Он воплощает философию Unix "делай одну вещь и делай ее хорошо", но на мета-уровне: сам BusyBox — это единый инструмент, который предоставляет множество инструментов, оставаясь при этом минималистичным, эффективным и универсальным решением для ситуаций, где каждый байт имеет значение.

Буду рад плюсам статье на Хабре

В конце декабря или начале января выйдет скорее всего заключительная 6 часть серии статей.

Сейчас пишу статью про полезные скрипты и алиасы на линукс, а также статью про устройство и написание ГПСЧ на C

Клон ChatGPT в 3000 байтах на C, основанный на GPT-2

Эта программа представляет собой свободную от зависимостей реализацию GPT-2. Она загружает матрицу весов и файл BPE из оригинальных файлов TensorFlow, токенизирует вывод при помощи простого энкодера, работающего по принципу частотного кодирования, реализует базовый пакет для линейной алгебры, в котором заключены математические операции над матрицами, определяет архитектуру трансформера, выполняет инференс трансформера, а затем очищает вывод от токенов при помощи BPE-декодера. Всё это — примерно в 3000 байт на C.

Код достаточно эффективно оптимизирован — настолько, что малый GPT-2 на любой современной машине выдаёт отклик всего за несколько секунд.