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

Идея написать эту статью зародилась из моего поста, после него я начал серию статей, которая раскрывала много интересных моментов — от математических алгоритмов и оптимизации до ГПСЧ.

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

Добро пожаловать в новую часть. Прошу под кат — там будет жарко, быстро и очень, очень интересно.

❯ Содержание

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

• «Математика, биты, магия и немного ненормального программирования на C»

• «Фокусы, хаки, магия и прочее ненормальное программирование на C»

• «Темная сторона Си: трюки, хаки, магия и алгоритмы»

• «Изящные, быстрые и удивительные алгоритмы на C»

• «Фантастические трюки на языке C»

• «Ненормальные непотребства, трюки, хаки и алгоритмы на C»

• «Невозможные возможные трюки и интересные алгоритмы на C»

• «Непотребные алгоритмы, ненормальные трюки и всевозможные хаки на C»

❯ Алгоритм bitboard для шахмат/игр

Использование 64-битных чисел для игрового поля — классика оптимизации.

#include <stdio.h>
#include <stdint.h>

typedef uint64_t Bitboard;

Bitboard knights_attacks(Bitboard knights) {
    Bitboard l1 = (knights >> 1) & 0x7F7F7F7F7F7F7F7F;
    Bitboard l2 = (knights >> 2) & 0x3F3F3F3F3F3F3F3F;
    Bitboard r1 = (knights << 1) & 0xFEFEFEFEFEFEFEFE;
    Bitboard r2 = (knights << 2) & 0xFCFCFCFCFCFCFCFC;
    return (l1 | r1) << 16 | (l1 | r1) >> 16 | (l2 | r2) << 8 | (l2 | r2) >> 8;
}

void print_bitboard(Bitboard bb) {
    for (int row = 7; row >= 0; row--) {
        for (int col = 0; col < 8; col++) {3
            int square = row * 8 + col;
            printf("%c ", (bb >> square) & 1 ? '1' : '.');
        }
        printf("\n");
    }
    printf("\n");
}

int main() {
    Bitboard knight = 1ULL << 36;  /* конь на e4*/

    printf("позиция коня:\n");
    print_bitboard(knight);

    printf("возможные ходы коня:\n");
    Bitboard attacks = knights_attacks(knight);
    print_bitboard(attacks);

    return 0;
}

Фанфакт: в английском как шахматная фигура конь это не horse, а knight. Ладья — Rook (грач/утес/башня). Слон — Bishop (епископ).

Функция knights_attacks вычисляет все возможные ходы коня за несколько битовых операций. Принцип такой: конь ходит буквой «Г» — на две клетки в одном направлении и одну в перпендикулярном.

Алгоритм делает сдвиги в четыре стороны. Сначала сдвигает позиции коней влево и вправо на 1 и 2 клетки (l1, r1, l2, r2). Маски 0x7F... и 0xFE... нужны чтобы не было «перетекания» битов через края доски — они отсекают боковые столбцы.

Затем комбинируем эти сдвиги. Объединение l1 и r1 дает горизонтальные смещения на одну клетку. Сдвиг этой комбинации на 16 рядов вверх и вниз дает вертикальное смещение на две клетки — получаем ходы типа «две вверх/вниз, одна вбок». Аналогично l2 и r2 дают смещение на две клетки по горизонтали. Сдвиг на 8 рядов дает смещение на одну клетку по вертикали — это ходы «одна вверх/вниз, две вбок».

Битовое ИЛИ всех четырех вариантов дает полную маску атак.

Главная прелесть — всего 10 битовых операций для любого количества коней на доске. Вместо перебора 64 клеток или циклов по фигурам — мгновенный расчет. Именно так работают современные шахматные движки.

При запуске мы получаем такой красивый вывод:

позиция коня:
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . 1 . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .
. . . . . . . .

возможные ходы коня:
. . . . . . . .
. . . 1 . 1 . .
. . 1 . . . 1 .
. . . . . . . .
. . 1 . . . 1 .
. . . 1 . 1 . .
. . . . . . . .
. . . . . . . .

❯ Неточное сравнение дробных чисел

Алгоритм решает проблему неточного сравнения чисел с плавающей точкой. Прямое сравнение через == часто даёт ложный результат из-за особенностей двоичного представления и накопления ошибок округления.

bool fuzzy_float_eq(float a, float b) {
    float abs_diff = fabsf(a - b);
    float max_abs = fmaxf(fabsf(a), fabsf(b));
    return abs_diff <= max_abs * 1e-6f || abs_diff < 1e-12f;
}

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

int main() {
    float num1 = 1.0000009901f;
    float num2 = 1.0000009902f;

    if (fuzzy_float_eq(num1, num2)) {
        printf("Числа считаются равными\n");
    } else {
        printf("Числа различны\n");
    }

    return 0;
}

Но так как это нечеткое сравнение, данный код выдаст что числа num1 и num2 равные. По сути, суть алгоритма в том, что числа считаются равными, если они либо очень близки относительно их величины, либо отличаются на исчезающе малую величину.

❯ ГПСЧ GJF (Gonzalo Joseph’s Fast)

В этой серии статьи мы давно не затрагивали тему ГПСЧ!

#include <stdint.h>
uint64_t gjf_state[2] = {0x123456789ABCDEF, 0xFEDCBA987654321};

uint64_t gjf64(void) {
    uint64_t s0 = gjf_state[0];
    uint64_t s1 = gjf_state[1];
    gjf_state[0] = s1;
    s0 ^= s0 << 23;
    gjf_state[1] = s0 ^ s1 ^ (s0 >> 17) ^ (s1 >> 26);
    return gjf_state[1] + s1;
}

Это компактный и ⚡ blazingly fast ⚡ (и даже не надо переписывать на раст) генератор, который хранит состояние в двух 64-битных переменных. В основе — перестановка и смешивание битов через сдвиги и XOR.

Его работа основана на быстрых битовых операциях: сдвигах и XOR. В начале функции сохраняются текущие значения состояния в локальные переменные s0 и s1. Первое состояние обновляется простой перестановкой — оно становится равным старому второму состоянию.

Затем начинается перемешивание. Значение s0 подвергается операции XOR'а с собственной копией, сдвинутой влево на 23 бита. Этот этап вносит нелинейность и распространяет изменение битов. После этого вычисляется новое значение для второго элемента состояния. Оно представляет собой XOR четырёх компонентов: только что изменённого s0, старого s1, а также сдвинутых вправо на 17 бит версии s0 и на 26 бит версии s1. Такая комбинация сдвигов разной длины обеспечивает тщательное перемешивание битов со всего 128-битного пространства состояния.

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

Давайте посмотрим на пример:

int main() {
    for (int i = 0; i < 5; i++) {
        printf("%016llx\n", gjf64());
    }
    return 0;
}

И код выдаст следующие шестнадцатеричные числа:

ccf7ce0251e21edb
232e19416e19e115
5d6f795c479bf4d2
dc8a1592370d6141
10e2fc8d1d6cc6f0

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

❯ XXTEA — крошечный блочный шифр

Компактный и эффективный шифр для эмбединга, осдева или прочих ваших странных потребностей. XXTEA шифрует массив 32-битных слов налету, используя ключ из 4 слов. Алгоритм выполняет несколько раундов, на каждом смешивая данные с ключом через XOR, сдвиги и сложение.

#include <stdint.h>
#define DELTA 0x9e3779b9
#define MX (((z>>5^y<<2) + (y>>3^z<<4)) ^ ((sum^y) + (key[(p&3)^e] ^ z)))

void xxtea_encrypt(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n < 1) return;
    rounds = 6 + 52/n;
    sum = 0;
    z = v[n-1];
    do {
        sum += DELTA;
        e = (sum >> 2) & 3;
        for (p=0; p<n-1; p++) {
            y = v[p+1];
            z = v[p] += MX;
        }
        y = v[0];
        z = v[n-1] += MX;
    } while (--rounds);
}

Первое, что делает алгоритм — вычисляет число раундов. Формула 6 + 52/n гарантирует, что даже для больших массивов будет выполнено достаточное количество перемешиваний. Начинается цикл с обнулённой переменной sum.

В каждом раунде к sum прибавляется число DELTA. Затем определяется e — индекс для выбора слова ключа, основанный на текущей сумме.

Далее идёт сердце алгоритма — внутренний цикл по всем словам массива, кроме последнего. Для каждого слова вычисляется замысловатая функция MX. В ней через сдвиги, сложения и XOR перемешиваются соседние слова (y и z), текущая сумма и часть ключа. Результат этого микса прибавляется к текущему слову, что и является шифрованием.

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

void xxtea_decrypt(uint32_t *v, int n, uint32_t const key[4]) {
    uint32_t y, z, sum;
    unsigned p, rounds, e;
    if (n < 1) return;
    rounds = 6 + 52/n;
    sum = rounds * DELTA;
    y = v[0];
    do {
        e = (sum >> 2) & 3;
        for (p=n-1; p>0; p--) {
            z = v[p-1];
            y = v[p] -= MX;
        }
        z = v[n-1];
        y = v[0] -= MX;
        sum -= DELTA;
    } while (--rounds);
}

Ну и также покажу функцию для дешифровки, ключевое отличие в обратном порядке операций и направлении. Если шифрование идёт «вперёд», то дешифрование идёт «назад», отменяя каждый шаг. Начальное значение sum не ноль, а rounds * DELTA — полная сумма, которая накопилась бы к концу шифрования. Важно понимать, что порядок обновления переменных y и z в дешифровании обратный по отношению к шифрованию, чтобы гарантировать, что при вычислении MX используются те же значения, что и при шифровании.

Ну и на примере демонстрация работы:

int main() {
    uint32_t data[] = {0x12345678, 0x9ABCDEF0};
    uint32_t key[4] = {0xA1B2C3D4, 0x5E6F7A8B, 0x9C0D1E2F, 0x3A4B5C6D};

    printf("Original:      0x%08X 0x%08X\n", data[0], data[1]);

    xxtea_encrypt(data, 2, key);
    printf("After encrypt: 0x%08X 0x%08X\n", data[0], data[1]);

    xxtea_decrypt(data, 2, key);
    printf("After decrypt: 0x%08X 0x%08X\n", data[0], data[1]);

    return 0;
}

С таким вот выводом:

Original:      0x12345678 0x9ABCDEF0
After encrypt: 0xB9F221ED 0x71F80F5B
After decrypt: 0x12345678 0x9ABCDEF0

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

Original:      0x12345678 0x9ABCDEF0
After encrypt: 0xB9F221ED 0x71F80F5B
After decrypt: 0x12345678 0x9ABCDEF0

________________________________________________________
Executed in    3.96 millis    fish           external
   usr time    1.09 millis    1.09 millis    0.00 millis
   sys time    2.89 millis    1.02 millis    1.87 millis

❯ Прямой доступ к битам дробного числа

В языке C нет прямого способа посмотреть битовое представление числа с плавающей запятой. Трюк в том, чтобы заставить память интерпретироваться по-разному. Для этого используется union — область памяти, в которой данные разных типов хранятся по одному и тому же адресу.

#include <stdio.h>
#include <stdint.h>

typedef union {
    float f;
    struct {
        uint32_t mantissa : 23;
        uint32_t exponent : 8;
        uint32_t sign : 1;
    } bits;
} float_cast;

int main() {
    float_cast fc;
    fc.f = -3.14f;

    printf("Number: %f\n", fc.f);
    printf("Sign: %u\n", fc.bits.sign);
    printf("Exponent: %u\n", fc.bits.exponent);
    printf("Mantissa: 0x%06X\n", fc.bits.mantissa);
    return 0;
}

Объявляется union с именем float_cast. Внутри него два поля: обычное число float f и структура bits. Они занимают один и тот же участок памяти размером 4 байта (32 бита). Когда мы записываем значение в fc.f, биты сразу располагаются в соответствии со стандартом IEEE 754. Через структуру bits мы получаем доступ к этим же битам, но уже как к отдельным именованным полям: знак (1 бит), порядок (8 бит) и мантисса (23 бита). Это не создаёт копии и не конвертирует данные — это просто другая «маска» для просмотра тех же битов.

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

Number: -3.140000
Sign: 1
Exponent: 128
Mantissa: 0x48F5C3

❯ Свертка массива XOR-ом для быстрой проверки изменений

Код выполняет быструю свёртку (контрольную сумму, checksum) массива данных с помощью операции XOR. Он создаёт короткий «отпечаток» массива, который резко меняется при любом изменении входных данных.

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

#include <stdio.h>
#include <stdint.h>

uint32_t xor_fold(const uint32_t* data, size_t len) {
    uint32_t result = 0;
    for (size_t i = 0; i < len; i++) result ^= data[i];
    return result;
}

int main() {
    uint32_t array1[] = {0x12345678, 0x9ABCDEF0, 0x13579BDF};
    uint32_t array2[] = {0x12345678, 0x9ABCDEF0, 0x13579BDF};
    uint32_t array3[] = {0x12345678, 0x9ABCDEF0, 0x13579BDE};

    printf("Hash array1: %08X\n", xor_fold(array1, 3));
    printf("Hash array2: %08X\n", xor_fold(array2, 3));
    printf("Hash array3: %08X\n", xor_fold(array3, 3));
    return 0;
}

И вот такой вот вывод:

Hash array1: 9BDF1357
Hash array2: 9BDF1357
Hash array3: 9BDF1356

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

❯ ГПСЧ Tyche

Tyche — это вариация генератора Xorshift с 128-битным состоянием (мы его уже рассматривали в прошлой статье). Алгоритм использует сдвиги и XOR для перемешивания. Инициализация выполняет «прогрев» генератора (20 пустых итераций) для улучшения начального состояния. Генератор быстр и подходит для симуляций.

#include <stdio.h>
#include <stdint.h>
#include <time.h>

typedef struct {
    uint32_t a, b, c, d;
} TycheState;

uint32_t tyche_next(TycheState *s) {
    uint32_t t = s->b;
    s->b = s->c;
    s->c = s->d;
    s->a = (s->a ^ (s->a << 11)) ^ (t ^ (t >> 19));
    s->d = s->a ^ s->b ^ s->c;
    return s->d;
}

void tyche_init(TycheState *s, uint32_t seed) {
    s->a = 0x6C078965 * (seed ^ (seed >> 30)) + 1;
    s->b = s->a + 0x6C078965;
    s->c = s->b + 0x6C078965;
    s->d = s->c + 0x6C078965;

    for (int i = 0; i < 20; i++) {
        tyche_next(s);
    }
}

Ключевая структура — TycheState. Это сердце генератора, где хранится его 128-битное состояние в виде четырёх 32-битных целых чисел: a, b, c, d.

Алгоритм работает в два этапа. Первый — инициализация в tyche_init. Она превращает один сид в начальное состояние из четырёх чисел. Используется умножение на константу и XOR для рассеивания битов. После этого генератор «прогревается» 20 холостыми тактами, чтобы устранить возможные корреляции, если начальное зерно было таким себе.

Второй этап — генерация нового числа в tyche_next. Это и есть вариация Xorshift. Алгоритм выполняет быструю перестановку: b, c, d сдвигаются, а значение a интенсивно перемешивается с использованием сдвигов и операции XOR с предыдущим значением b. Новое значение d (которое и возвращается) вычисляется как XOR всех трёх обновлённых регистров состояния. Весь процесс крайне быстр, требует лишь несколько битовых операций на процессоре.

И давайте реализуем пример работы:

int main() {
    TycheState rng;
    tyche_init(&rng, time(NULL));

    printf("рандомные 16битные числа:\n");
    for (int i = 0; i < 10; i++) {
        printf("0x%08X\n", tyche_next(&rng));
    }

    printf("\nВ диапазоне 0..99:\n");
    for (int i = 0; i < 10; i++) {
        printf("%d ", tyche_next(&rng) % 100);
    }
    printf("\n");

    return 0;
}

С вот таким выводом у меня:

рандомные 16битные числа:
0xF01D2505
0x71012006
0xE0182024
0x21292603
0x81310620
0x00002403
0xC0210425
0x81302026
0x88000000
0x89200004

В диапазоне 0..99:
38 20 16 84 72 61 80 52 44 65

❯ Заключение

Спасибо за прочтение статьи! Я надеюсь, вы узнали что‑нибудь новенькое, или, может быть, какой‑нибудь трюк натолкнул вас на другой интересный алгоритм. Если нашли нюанс в самой статье — пишите в комментарии.

Девятая часть получилась насыщенной: от сортировок и криптографии до битовой магии и математических трюков.

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

Примеры работы кода вы можете увидеть в моем репозитории The Art Of Fun C.

Перед оплатой в разделе «Бонусы и промокоды» в панели управления активируйте промокод и получите кэшбэк на баланс.