Завтра выйдет новая статья этой серии, третья часть по счету

Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. И я — не исключение. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень), алгоритмах на языке C!

Идея написать эту статью зародилась из моего поста, после него я написал статью «Математика, биты, магия и немного ненормального программирования на C» и «Фокусы, хаки, магия и прочее ненормальное программирование на C», которые раскрывали много интересных моментов. Увидев, что многим понравилась, я задумался: почему бы не изучить еще какие-нибудь трюки, заодно практикуясь в программировании на C?

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

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

The Product-Minded Software Engineer /
Инженер программного обеспечения, ориентированный на продукт

Интересная статья-размышление:

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

https://blog.pragmaticengineer.com/the-product-minded-engineer/

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

unsigned char* unwrap(void (*fn)()) {
    static unsigned char buffer[sizeof(fn)];
    memcpy(buffer, fn, sizeof(fn));
    return buffer;
}

void bar() {};

int main() {
    volatile unsigned char* icall_w = unwrap(bar);

    printf("code: ");

    for (int i = 0; i < sizeof(icall_w); i++) {
        printf("%02x ", (unsigned char)icall_w[i]);
    }

    printf("\n");
    return 0;
}

Вся суть в функции unwrap. Она получает указатель на функцию (проще говоря — её адрес в памяти), копирует этот адрес в байтовый массив и возвращает его. Важный момент: sizeof(fn) — это размер указателя (4 или 8 байт), а не размер кода самой функции. Поэтому копируется только адрес, а не инструкции функции. В главной функции мы передаём адрес функции bar в unwrap. Получаем массив байтов, который и есть этот самый адрес. Затем программа просто выводит эти байты в шестнадцатеричном виде.

Что выводится на самом деле? Не код функции, а её местоположение в памяти. Этот адрес будет меняться при каждом запуске (из-за ASLR — защиты операционной системы), и порядок байтов в выводе зависит от архитектуры процессора.

Например, у меня вывод следующий:

code: c3 66 66 2e 0f 1f 84 00

TechPulse — короткие и понятные IT-новости.
Короткие и понятные IT-новости: главное за день, нейросети и ИИ, гаджеты, кибербезопасность, софт, обновления и итоги недели.

Всё самое важное — в одном месте.
👉 https://news.1rj.ru/str/newstechpulse

FyneDesk - это простая в использовании среда рабочего стола Linux / Unix, основанная на material design.

Написан на Golang

git clone https://github.com/fyshos/fynedesk
cd fynedesk
make
sudo make install

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

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