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

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

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

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

Всех, кто заинтересовался — прошу под кат.

❯ Содержание

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

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

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

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

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

❯ Бесконечный цикл без while

Простой, но интересный трюк:

#include <stdio.h>

void infinite_loop(int n) {
    printf("%d\n", n);
    infinite_loop(n + 1);
}

int main() {
    infinite_loop(1);
    return 0;
}

Классическое переполнение стека через рекурсию. Рекурсия без базового случая — это гарантированное переполнение стека.

❯ ГПСЧ SplitMix64

Ещё один качественный и быстрый ГПСЧ, часто используемый для инициализации состояния других генераторов (например, того же xoshiro256pp).

uint64_t splitmix64(uint64_t *x) {
    *x += 0x9e3779b97f4a7c15;
    uint64_t z = *x;
    z = (z ^ (z >> 30)) * 0xbf58476d1ce4e5b9;
    z = (z ^ (z >> 27)) * 0x94d049bb133111eb;
    return z ^ (z >> 31);
}

Эта функция принимает указатель на внутреннее состояние генератора. При каждом вызове состояние увеличивается на константу 0x9e3779b97f4a7c15. Затем выполняется три этапа преобразования этого состояния:

1. Сдвиг вправо на 30 бит и XOR с исходным значением, после чего результат умножается на константу 0xbf58476d1ce4e5b9.

2. Сдвиг вправо на 27 бит и XOR с текущим значением, затем умножение на константу 0x94d049bb133111eb.

3. Сдвиг вправо на 31 бит и операция XOR с полученным значением. Результат этой операции и есть псевдослучайное число.

30, 27 и 31 бит были подобраны экспериментальным путем, так же как и константы. Алгоритм детерминированный — при одинаковом начальном состоянии выдает одинаковые последовательности.

❯ Счетчик Морриса

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

uint8_t morris_counter = 0;
void morris_increment() {
    if (rand() < (RAND_MAX / (1 << morris_counter))) {
        morris_counter++;
    }
}
uint32_t morris_estimate() {
    return (1 << morris_counter) - 1;
}

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

Сама функция очень экономичная по памяти, 8-битный счётчик может представлять числа до 2⁸–1 = 255, но алгоритм позволяет оценивать гораздо большие значения (до 2²⁵⁵–1 в теории).

Ну и также он неточен и зависит от генератора случайных (или псевдослучайных) чисел.

Вы можете реализовать этот алгоритм, используя ГПСЧ, которые мы писали ранее в статьях!

❯ Алгоритм Зеллера

Алгоритм Зеллера — это формула для определения дня недели для заданной даты.

Формула выглядит так: h = (d + [13(m + 1)/5] + K + [K/4] + [J/4] – 2J) mod 7, где:

• h — день недели (0 — суббота, 1 — воскресенье, …, 6 — пятница);

• d — день месяца (от 1 до 31);

• m — номер месяца (март — 3, …, декабрь — 12, январь и февраль — 13 и 4 предыдущего года);

• K — последние две цифры года;

• J — первые две цифры года.

Функция mod 7 нормализует результат так, чтобы он находился в диапазоне от 0 до 6.

Давайте напишем алгоритм Зеллера на C:

int zellers_congruence(int day, int month, int year) {
    if (month < 3) {
        month += 12;
        year--;
    }
    int k = year % 100;
    int j = year / 100;
    return (day + 13*(month + 1)/5 + k + k/4 + j/4 + 5*j) % 7;
}

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

int is_leap_year(int year) {
    return (year % 4 == 0 && year % 100 != 0) || (year % 400 == 0);
}

Високосный год должен делиться на 4, и не должен делиться на 100 либо должен делиться на 400.

❯ Определение палиндрома битовым способом

Палиндром — это число, буквосочетание, слово или текст, одинаково читающееся в обоих направлениях (слева направо и справа налево).

int is_palindrome_bit(const char *str) {
    uint64_t mask = 0;
    for (const char *p = str; *p; p++) {
        mask ^= (1ULL << (*p - 'a'));
    }
    return (mask & (mask - 1)) == 0;
}

Данная функция проверяет, является ли строка палиндромом по битовой маске. Она работает только для строчных латинских букв.

Для каждого символа строки вычисляется его позиция в алфавите (от 0 до 25) и устанавливается соответствующий бит в 64-битной маске. Операция XOR используется для переключения бита с 0 до 1 и наоборот.

Принцип работы: для каждого символа строки вычисляется его позиция в алфавите (от 0 до 25) и устанавливается соответствующий бит в 64-битной маске. Операция XOR используется для переключения бита: если бит был 0, он становится 1, и наоборот. Проверка (mask & (mask - 1)) == 0 определяет, что в маске установлен не более чем один бит.

Но функция имеет ограничение, она не учитывает порядок символов. Например строки «abba» и «aabb» дадут одинаковый результат, хотя вторая не является палиндромом.

❯ ГПСЧ на основе упрощенного sha1

Давайте реализуем еще одну версию генератора псевдослучайных чисел, уже на основе хеш-функции SHA-1 в упрощенном виде. Функция принимает массив state из 5 элементов.

uint32_t sha1_prng(uint32_t *state) {
    uint32_t a = state[0];
    uint32_t b = state[1];
    uint32_t c = state[2];
    uint32_t d = state[3];
    uint32_t e = state[4];

    for (int i = 0; i < 20; i++) {
        uint32_t f = (b & c) | ((~b) & d);
        uint32_t temp = ((a << 5) | (a >> 27)) + f + e + 0x5A827999 + state[i % 16];
        e = d; d = c; c = (b << 30) | (b >> 2); b = a; a = temp;
    }

    state[0] = a; state[1] = b; state[2] = c; state[3] = d; state[4] = e;
    return a ^ b ^ c ^ d ^ e;
}

Затем выполняется 20 раундов преобразования, аналогичных SHA-1, но в упрощенном формате. Вычисляется нелинейная функция f = (b & c) | ((~b) & d), выполняется циклический сдвиг переменной a на 5 битов влево, третьим шагом вычисляется переменная temp, которая преобразует значение a, e, функцию f, константу 0x5A827999 и элемент из исходного состояния state[i % 16]. И финальным шагом значения переменных сдвигаются, e получает значение d, d — значение c, c — циклически сдвинутое значение b, b — значение a, a — значение temp.

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

Этот алгоритм показан ТОЛЬКО для ознакомления с тем, как можно упрощать другие алгоритмы для генерации чисел. Этот ГПСЧ чрезвычайно медленный. Но зато он относится к криптографическим, хоть и не самый оптимимальным, генераторам.

❯ ГСПЧ JSF

Боб Дженкинс славится и ГПСЧ. JSF — один из них.

uint32_t jsf32_state[4] = {0x12345678, 0x9ABCDEF0, 0x13579BDF, 0x2468ACE0};

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

static jsf32_state_t jsf32_global = {0x12345678, 0x9ABCDEF0, 0x13579BDF, 0x2468ACE0};

uint32_t jsf32() {
    jsf32_state_t* s = &jsf32_global;
    uint32_t e = s->a - ((s->b << 27) | (s->b >> 5));
    s->a = s->b ^ ((s->c << 17) | (s->c >> 15));
    s->b = s->c + s->d;
    s->c = s->d + e;
    s->d = e + s->a;
    return s->d;
}

Генератор оперирует внутренним состоянием из четырёх 32-битных беззнаковых целых чисел, инициализированных фиксированными значениями.

При каждом вызове функция выполняет один раунд перемешивания состояния с использованием циклических сдвигов, сложения, вычитания и операции XOR. Все четыре слова состояния интенсивно взаимодействуют, что обеспечивает хорошее распределение. Результатом работы функции становится обновлённое значение одного из элементов состояния (jsf32_state[3]), которое и возвращается как псевдослучайное число.

Но этот алгоритм тоже не из быстрых.

❯ Алгоритм RLE

Мы еще не затрагивали интересные алгоритмы сжатия данных. Давайте реализуем кодирование и декодирование по алгоритму RLE (Run-Length Encoding), который заменяет повторяющиеся последовательности одинаковых символов (серии) на пары «счетчик-символ». Вместо хранения одинаковых символов подряд сохраняется количество повторений и один экземпляр символа.

Вот пример работы:

Исходная строка: AAABBCDDDDEEFGGGHHH
Сжатая строка: 3A2BC4D2EF3G3H
Распакованная строка: AAABBCDDDDEEFGGGHHH

void rle_encode(const char* input, char* output) {
    int input_len = strlen(input);
    int output_index = 0;
    int count;
    char current_char;

    for (int i = 0; i < input_len; i++) {
        current_char = input[i];
        count = 1;

        while (i + 1 < input_len && input[i] == input[i + 1]) {
            count++;
            i++;
        }

        if (count > 1) {
            int written = snprintf(output + output_index,
                                 (input_len * 3 + 1) - output_index,
                                 "%d%c", count, current_char);
            if (written < 0) break;
            output_index += written;
        } else {
            if (output_index < input_len * 3) {
                output[output_index++] = current_char;
            } else {
                break;
            }
        }
    }
    output[output_index] = '\0';
}

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

char* rle_decode(const char* input) {
    int input_len = strlen(input);
    char* output = malloc((input_len * 10) + 1);
    if (!output) return NULL;

    int output_index = 0;
    int i = 0;

    while (i < input_len) {
        if (input[i] >= '0' && input[i] <= '9') {
            int count = 0;
            while (i < input_len && input[i] >= '0' && input[i] <= '9') {
                count = count * 10 + (input[i] - '0');
                i++;
            }

            if (i < input_len) {
                char symbol = input[i];
                for (int j = 0; j < count && output_index < input_len * 10; j++) {
                    output[output_index++] = symbol;
                }
                i++;
            }
        } else {
            if (output_index < input_len * 10) {
                output[output_index++] = input[i++];
            } else {
                break;
            }
        }
    }
    output[output_index] = '\0';
    return output;
}

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

❯ Ближайшее число до степени двойки

Данный алгоритм находит ближайшую степень двойки, которая больше или равна входному числу X. Сначала выполняется декремент x, чтобы корректно отработать случай, когда x уже степень двойки. Затем выполняется серия битовых операций ИЛИ со сдвигами на 1, 2, 4, 8 и 16 бит. Эти операции последовательно заполняют младшие биты единицами, начиная со старшего установленного бита.

В результате получается число, состоящее из всех единиц в младших битах. При добавлении 1 это число переполняется и образует степень двойки.

Особенность алгоритма в том, что он корректно обрабатывает граничные случаи, включая x = 0 и x = 1, а также максимальные значения uint32_t.

uint32_t next_power_of_two(uint32_t x) {
    x--;
    x |= x >> 1;
    x |= x >> 2;
    x |= x >> 4;
    x |= x >> 8;
    x |= x >> 16;
    return x + 1;
}

❯ Алгоритм Фишера–Йейтса для перемешивания массива

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

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

void fisher_yates_shuffle(uint32_t *arr, size_t n, uint64_t *seed) {
    for (size_t i = n - 1; i > 0; i--) {
        size_t j = sha1_prng(seed) % (i + 1);
        uint32_t temp = arr[i];
        arr[i] = arr[j];
        arr[j] = temp;
    }
}

Данный код реализует алгоритм тасования Фишера–Йейтса для случайного перемешивания массива. Алгоритм работает следующим образом: он проходит по массиву от последнего элемента к первому. На каждом шаге выбирается случайный индекс j от 0 до i (включительно) с помощью генератора псевдослучайных чисел sha1_prng (который мы разбирали выше). Затем элемент с индексом i меняется местами с элементом с индексом j. Такой подход гарантирует, что каждый элемент массива с равной вероятностью может оказаться на любой позиции, включая текущую. В результате получается равномерно перемешанный массив.

❯ ГПСЧ SFC (Small Fast Chaotic)

ГПСЧ SFC — 256-битная реализация алгоритма SFC Криса Доти-Хамфри. В алгоритме есть несколько циклов, которые могут быть разными в зависимости от начального значения.

uint32_t sfc32_state[4] = {0x12345678, 0x9ABCDEF0, 0x13579BDF, 0x2468ACE0};

uint32_t sfc32() {
    uint32_t result = sfc32_state[0] + sfc32_state[1] + sfc32_state[3]++;
    sfc32_state[0] = sfc32_state[1] ^ (sfc32_state[1] >> 9);
    sfc32_state[1] = sfc32_state[2] + (sfc32_state[2] << 3);
    sfc32_state[2] = ((sfc32_state[2] << 21) | (sfc32_state[2] >> 11)) + result;
    return result;
}

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

Затем состояние обновляется: первый элемент становится результатом XOR между вторым элементом и его сдвинутой версией на 9 бит вправо. Второй элемент преобразуется в сумму третьего элемента и его сдвига на 3 бита влево. Третий элемент становится комбинацией циклического сдвига исходного третьего элемента (21 бит влево и 11 бит вправо) с добавлением вычисленного ранее результата.

Каждый вызов функции производит новое 32-битное псевдослучайное число и модифицирует внутреннее состояние.

❯ Бенчмарки

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

PRNG Performance (10,000,000 iterations):
-----------------------------------------
xorshift64:      16.44 ms  (608.18M numbers/s)
lehmer64:        20.76 ms  (481.78M numbers/s)
xoshiro256pp:    15.87 ms  (630.23M numbers/s)
pcg32:           11.27 ms  (887.28M numbers/s)
wyrand:          17.65 ms  (566.52M numbers/s)
msws32:          17.26 ms  (579.37M numbers/s)
jsf32:           99.95 ms  (100.05M numbers/s)
romu_duo:        13.57 ms  (736.93M numbers/s)
sfc32:           43.12 ms  (231.92M numbers/s)
sha1_prng:      254.77 ms  ( 39.25M numbers/s)
-----------------------------------------

Math Algorithms Performance (1000000 iterations):
--------------------------------------------
fast_pow:                1.62 ms  ( 0.002 us/call)
fastest_pow:             1.38 ms  ( 0.001 us/call)
fast_mod:                1.14 ms  ( 0.001 us/call)
is_power_of_two:         1.36 ms  ( 0.001 us/call)
jenkins_hash:           29.41 ms  ( 0.029 us/call)
jenkins_mix+final:      29.12 ms  ( 0.029 us/call)
xor_swap:                2.20 ms  ( 0.002 us/call)
div3:                    1.35 ms  ( 0.001 us/call)
isqrt:                   5.92 ms  ( 0.006 us/call)
to_gray:                 1.34 ms  ( 0.001 us/call)
from_gray:               1.57 ms  ( 0.002 us/call)
counting_sort_256:       7.42 ms  ( 0.742 us/call)
next_power_of_two:       1.34 ms  ( 0.001 us/call)
count_trailing_zeros:    1.72 ms  ( 0.002 us/call)
count_trailing_zeros_kernighan:    1.69 ms  ( 0.002 us/call)
fisher_yates_shuffle:    2.06 ms  ( 0.206 us/call)
--------------------------------------------

Compression Algorithms Performance (1000 iterations):
---------------------------------------------------
RLE Encode:              4.36 ms  ( 0.873 us/call)
RLE Decode:              0.46 ms  ( 0.091 us/call)
Compression Ratio:      70.75%
---------------------------------------------------

Date Algorithms Performance (100000 iterations):
--------------------------------------------
is_leap_year:            0.17 ms  ( 0.002 us/call)
zellers_congruence:      0.46 ms  ( 0.005 us/call)
--------------------------------------------

String Algorithms Performance (100000 iterations):
---------------------------------------------
is_palindrome_bit:       0.43 ms  ( 0.004 us/call)
---------------------------------------------

И для наглядности графики для PRNG Performance, Math Algorithms Performance и Compression Algorithms Performance.

❯ Заключение

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

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

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

Новости, обзоры продуктов и конкурсы от команды Timeweb.Cloud — в нашем Telegram-канале ↩