Доброго времени суток, господа и дамы! Иногда у некоторых людей возникает желание заняться откровенным непотребством в программировании — то, что не несет практической пользы напрямую, но помогает развлечься. И я — не исключение. В этой статье я хочу рассказать вам о лайфхаках, трюках (магических и не очень) и алгоритмах на языке 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("%016llxn", 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%08Xn", data[0], data[1]);
xxtea_encrypt(data, 2, key);
printf("After encrypt: 0x%08X 0x%08Xn", data[0], data[1]);
xxtea_decrypt(data, 2, key);
printf("After decrypt: 0x%08X 0x%08Xn", 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: %fn", fc.f);
printf("Sign: %un", fc.bits.sign);
printf("Exponent: %un", fc.bits.exponent);
printf("Mantissa: 0x%06Xn", 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: %08Xn", xor_fold(array1, 3));
printf("Hash array2: %08Xn", xor_fold(array2, 3));
printf("Hash array3: %08Xn", 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%08Xn", 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.
Автор: DrArgentum
