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 на любой современной машине выдаёт отклик всего за несколько секунд.

Давайте проверим, знаете ли вы основные команды, практики, которые вокруг них существуют, и алгоритмы решения типовых ситуаций. Насколько уверенно вы можете ответить на следующие вопросы:

❓Почему стоит почти всегда начинать свою работу с команды git pull, если вы не forever alone на проекте?
❓Почему стоит пользоваться командой git push почаще (хотя бы раз в день)? Какие риски могут быть, если вы редко отправляете изменения в удалённый репозиторий?
❓Представьте, что вы сделали пуллреквест, отправили его на ревью. Ревьюер предложил вам мелкую правку прямо в ПР (например, поправил опечатку в слове) и вы нажали в интерфейсе Github кнопку "Commit changes". После нажатия на эту кнопку изменения попадут вам сразу и в локальный репозиторий?
❓Какие основные практики оформления коммитов вы знаете?
❓Зачем нужно ветвление в git?
❓Вы сделали коммит, отправили изменения в удалённый репозиторий. И тут в интерфейсе Github вдруг видите, что приехало не всё, над чем вы работали, точно должны были быть ещё какие-то файлы. Что пошло не так и как это исправить?
❓В вашей ветке есть конфликты с base branch. Как их разрешить?
❓Вы и коллега работали в разных ветках над разными фичами, но эти фичи могли затрагивать одни и те же файлы. Вы оба сделали ПР, но коллега замержил свой ПР быстрее, чем вы свой. В вашей ветке возникли конфликты. Вы их порешали, пересобрали свою ветку, чтобы проверить, что все ок, и при проверке понимаете, что что-то поломалось. Что-то отвалилось в том, над чем работали вы и/или пропали какие-то части изменений, которые вносил коллега.
Как всё исправить, чтобы в вашей ветке корректно работало то, над чем трудились вы, и были видны все изменения коллеги?

Понятия задачи (task), потока (thread) и процесса (process) в Linux

Task, thread и process – это, в принципе, достаточно близкие по смыслу понятия, но надо всё-таки разобраться, что каждое из них значит.

Когда вы запускаете приложение, в системе создаётся процесс (process), которому выделяется память на хранение исполняемого кода и других данных. В рамках этого процесса создаётся минимум один поток (thread). Именно среди потоков планировщики Linux и распределяют время процессора, а также решают, в какой очерёдности они будут выполняться. Задачей (task) можно назвать уже непосредственно сами инструкции, которые процессор получает и выполняет.

Важно также знать, что у процессов есть поле state, которое, как понятно по названию, показывает, в каком состоянии сейчас находится процесс. Состояний может быть несколько:

Running или Runnable (R) – процесс в состоянии running прямо сейчас использует процессорное время, в свою очередь runnable процесс только ожидает его.

Uninterruptible Sleep (D) – процесс ждёт результата операции ввода-вывода. Например, ждёт данные от диска. Такой процесс никак нельзя убить.

Interruptible Sleep (S) – процесс ждёт какое-то событие и не потребляет процессорного времени. Пример: ввод из командной строки.

Stopped (T) – процесс получил сигнал SIGSTOP или SIGTSTP и остановил свою работу. В этом состоянии процессу можно послать сигнал SIGCONT и запустить его снова.

Zombie (Z) – процесс, который получил сигналы на завершение работы, и полностью её завершил – он больше не потребляет ресурсов системы, только PID идентификатор. Он ждет, когда его родительский процесс выполнит системный вызов wait, после этого Zombie исчезнет. Иногда этого может не происходить, в таком случае приходится дебажить родителя.

Всю информации о процессе можно достать из папки /proc/<PID>, где <PID> – это идентификатор процесса. Если вам нужно получить информацию в более “user friendly” виде, то воспользуйтесь утилитами top, htop, ps и тд.

Генератор случайных чисел Лемера

Очень быстрый генератор случайных чисел. Подробнее можно почитать здесь.

Алгоритм Lehmer64 — это быстрый генератор псевдослучайных чисел (ГПСЧ), основанный на мультипликативном линейном конгруэнтном методе. Он использует 128-битное состояние для генерации 64-битных случайных чисел, обеспечивая высокую производительность и достаточную статистическую случайность для большинства некриптографических задач.

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

Принцип работы
Основная формула метода: Xn+1 = (a ⋅ Xn + c) mod m, где:

+ Xn+1 — следующее псевдослучайное число;
+ Xn — текущее псевдослучайное число;
+ a — мультипликативный множитель;
+ c — приращение;
+ m — модуль;
+ X0 — начальное значение (seed).

И вот его простейшая реализация на C:

static __uint128_t g_lehmer64_state;

uint64_t lehmer64(void) {
    g_lehmer64_state *= 0xda942042e4dd58b5ULL;
    return g_lehmer64_state >> 64;
}

Каждый раз, когда нужно новое число, мы умножаем состояние на константу 0xda942042e4dd58b5ULL (высчитанная экспериментальным путем). g_lehmer64_state - это состояние размером 128 бит, на старте в котором хранится нечетный сид. После этого берем старшие 64 бита и возвращаем их, младшие остаются.

Всех с наступающим новым годом!

В этот год наш канал вырос в разы, достиг 350+ подписчиков, мы узнали много нового.

В этот день хочется поблагодарить каждого из вас, за участие в нашем канале Дальше - больше!

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

С наступающим новым годом!

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

Наши первые 5 статей показали, что математика и низкоуровневые оптимизации могут быть не только полезными, но и по‑настоящему увлекательными.

Но на этом наша история не заканчивается. Впереди нас ждут структуры данных, алгоритмы сжатия, ГПСЧ и настолько бесполезные трюки, что их полезность становится философским вопросом.


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

Хабр лёг! #хабр_не_торт

Полезные алиасы для GIT

Алиасы для git можно делать как стандартным внешним путём через конфиг вашего шелла:

alias gga="git add"
alias ggc="git commit"
alias ggcm="git commit -m"
alias ggs="git status"
alias ggl="git log"
alias gglo="git log --oneline"
alias ggd="git diff"
alias ggds="git diff --staged"
alias ggr="git restore"

Так и через конфигурирование файла ~/.gitconfig:

[alias]
    st = status -b
    c = commit
    co = checkout
    br = branch
    slog = log --pretty=format:"%C(auto)%h%C(auto)%d\\ %C(auto,reset)%s\\ \\ [%C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)]"
    glog = log --graph --pretty=format:"%C(auto,yellow)%h%C(auto)%d\\ %C(auto,reset)%s\\ \\ [%C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)]"
    wlog = log --pretty=format:"%C(auto,yellow)%h%C(auto)%d%C(auto,reset)\\ by\\ %C(auto,blue)%an%C(auto,reset),\\ %C(auto,cyan)%ar%C(auto,reset)%n\\ %s%n" --stat
    gr = log --graph --abbrev-commit --decorate --format=format:'%C(bold blue)%h%C(reset) - %C(bold green)(%ar)%C(reset) %C(white)%s%C(reset) %C(dim white)- %an%C(reset)%C(bold yellow)%d%C(reset)' --all
    wt = worktree

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

Давайте попробуем импортозаместить стандартный pow нашим алгоритмом, а точнее — бинарным возведением в степень. Сложность — O(log n).

Широко известный алгоритм для возведения любого числа в целую степень с абсолютной точностью. Принцип действия прост: есть целая степень e, чтобы получить число b в этой степени нужно возвести это число во все степени 1, 2, 4, … 2n (в коде этому соответствует b *= b), каждый раз сдвигая биты e вправо (e >>= 1) пока оно не равно 0 и тогда, когда последний бит e не равен нулю ((e & 1) != 0), домножать результат v на полученное b. Этот метод позволяет возвести число в целую степень за логарифмическое время, что особенно важно при работе с большими числами.

Возьмём 2⁵. Вместо 2×2×2×2×2 мы представляем 5 в двоичном виде (101) и идем по битам справа налево. Первый бит (1) равен 2, второй бит (0) равен 2 в квадрате, и в последнем третьем биту (1) результат (2) умножаем на текущее значение (4²=16) → 32.

Технически, при каждом проходе цикла, мы проверяем младший бит степени e. Если этот бит равен 1 (e & 1 != 0), мы умножаем текущий результат v на основание b. После этого мы умножаем b на само себя (квадрат), что соответствует следующей степени двоичного представления. Уменьшая e с помощью побитового сдвига вправо, мы продолжаем цикл, пока e не достигает нуля, в результате чего получаем финальный результат.

double binary_pow(double b, unsigned long long e) {
    double v = 1.0;
    while(e != 0) {
            if((e & 1) != 0) {
                    v *= b;
            }
            b *= b;
            e >>= 1;
    }
    return v;
}

И при выполнении мы можем получить 10.00 ^ 2.00 = 100.00, 10.50 ^ 2.00 = 110.25. Но если экспонента не целое число, то данный способ не подойдет (10.50^2.50 вычисляется как 110.25). Так что важно отметить, что этот алгоритм применим только к целым числам.

Согласно википедии, Код Мортона (называемый также Z-порядок, кривая Мортона, кривая Лебега) - это функция, которая отоброжает многомерные данные в одномерные. Идея — чередовать биты координатных значений.

Bit Interleaving (перемежение битов, интерливинг) — процесс изменения порядка следования битов в передаваемой последовательности. Цель — разнести ошибки так, чтобы они влияли на разбросанные биты, а не на последовательные.

static uint32_t split_bits(uint16_t x) {
    x = (x | (x << 8)) & 0x00FF00FF;
    x = (x | (x << 4)) & 0x0F0F0F0F;
    x = (x | (x << 2)) & 0x33333333;
    x = (x | (x << 1)) & 0x55555555;
    return x;
}

uint32_t morton_encode(uint16_t x, uint16_t y) {
    return split_bits(x) | (split_bits(y) << 1);
}

void morton_decode(uint32_t code, uint16_t *x, uint16_t *y) {
    uint32_t x_code = code & 0x55555555;
    uint32_t y_code = code & 0xAAAAAAAA;

    x_code = (x_code | (x_code >> 1)) & 0x33333333;
    x_code = (x_code | (x_code >> 2)) & 0x0F0F0F0F;
    x_code = (x_code | (x_code >> 4)) & 0x00FF00FF;
    x_code = (x_code | (x_code >> 8)) & 0x0000FFFF;

    y_code = (y_code | (y_code >> 1)) & 0x33333333;
    y_code = (y_code | (y_code >> 2)) & 0x0F0F0F0F;
    y_code = (y_code | (y_code >> 4)) & 0x00FF00FF;
    y_code = (y_code | (y_code >> 8)) & 0x0000FFFF;

    *x = (uint16_t)x_code;
    *y = (uint16_t)(y_code >> 1);
}

Битовый интерливинг перемешивает биты двух чисел. Для координат x и y мы берем их бинарные представления и создаем некое новое число, куда поочередно будем записывать биты из x и y. К примеру, если x = 10 (1010) и y=12 (1100), то процесс будет таким: возьмем младшие биты x (0) и y (0), соединив их получаем 00. Затем следующий бит y (0) и следующий бит x (1), получаем 01. Затем бит y (1) и бит x (0), получаем 10. Наконец, старший бит y (1) и старший бит x (1), получаем 11. Итоговый код Мортона: 11 10 01 00 = 11100100₂ = 228.

Функция split_bits выполняет ключевую операцию - она раздвигает биты числа, вставляя между ними нули. Для 4-битного числа 1010 после split_bits получается 01000100 в бинарном виде.

Функция morton_encode вызывает функцию split_bits для x и y, после сдвигает результат для y на один бит влево и объедяняет XOR'ом.

Функция morton_decode выполняет обратную операцию. Сначала она разделяет код на биты, принадлежащие x (нечетные позиции) и y (четные позиции), используя маски 0x55555555 и 0xAAAAAAAA. Затем сжимает биты обратно в 16-битные числа, выполняя операции, обратные split_bits.

Основное преимущество кода Мортона - сохранение пространственной локальности. Точки, близкие в двумерном пространстве, обычно имеют близкие значения кодов Мортона. Это свойство используется в пространственных индексах, квадродеревьях, компьютерной графике и GIS системах для эффективной организации данных.

Давайте попробуем запустить и проверить алгоритм:

int main() {
    uint16_t x = 10;
    uint16_t y = 13;

    uint32_t code = morton_encode(x, y);
    printf("x=%u, y=%u\n", x, y);
    printf("Morton code: %u (0x%08X)\n", code, code);

    uint16_t decoded_x, decoded_y;
    morton_decode(code, &decoded_x, &decoded_y);
    printf("Decoded: x=%u, y=%u\n", decoded_x, decoded_y);

    return 0;
}

При запуске получаем:

x=10, y=12
Morton code: 228 (0x000000E4)
Decoded: x=10, y=6

Сам код мортона благодаря тому что упаковывает 2D/3D координаты в 1D число, используется в ГИС, базах данных, играх и прочих системах где нужна упаковка координат.

Бьюсь об заклад, что вы крайне редко видели код на GNU-стандартах. В качестве примера я хочу показать пример рабочей программы с устаревшими и специфичными вещами.

??=include <stdio.h>

int $func(int array[static 10]) <%
    int sum = 0;
    for (int i = 9; i --> 0;) <%
        sum += array<:i:>;
    %>
    return sum;
%>

int $print_func(int array[static 10]) <%
    for (int i = 9; i >= 0; --i) <%
        printf("Value %i with index %i\n", array[i], i);
    %>
    return 0;
%>


int main() ??<
    int arr<:10:> = {[0]=1, [5]=5, [9]=9};

    $print_func(arr);

    int result = (<%
        int temp = $func(arr);
        printf("Sum: %d??/n", temp);
        temp;
    %>);

    void *ptr = ??< &&label ??>;
    goto *ptr;

    label:
    return result;
??>

Скомпилировав код выше через gcc gnustd_fun.c -o gnustd_fun -std=gnu11 -trigraphs, мы получим:

Value 9 with index 9
Value 0 with index 8
Value 0 with index 7
Value 0 with index 6
Value 5 with index 5
Value 0 with index 4
Value 0 with index 3
Value 0 with index 2
Value 0 with index 1
Value 1 with index 0
Sum: 6

Этот код использует такие вещи, как триграфы ??= вместо символа #, ??< для открывающей фигурной скобки и ??> для закрывающей. Триграфы и диграфы (<% и %> также заменяют фигурные скобки, а <: и :> служат заменой квадратных скобок) были созданы для замены возможных несуществующих на клавиатуре символов скобок в стародавние времена.

Имена функций func и print_func начинаются с символа $ (php-разработчики должны пустить слезу), что является допустимым расширением компилятора.

Цикл в функции $func записан в необычной форме: for (int i = 9; i --> 0;). Оператор --> на самом деле комбинация постфиксного декремента i-- и оператора сравнения >. В функции main массив инициализируется следующим образом: {[0]=1, [5]=5, [9]=9}, где явно задаются значения только для конкретных индексов.

Далее используется составное выражение в круглых скобках ({ ... }), которое является расширением GCC и называется statement expression. Оно выполняет блок кода, а значением всего выражения становится результат последнего оператора внутри блока, в данном случае temp;. Это позволяет совместить вычисление суммы, её вывод через printf и передачу значения в переменную result.

Наиболее экзотическая часть кода — это использование указателей на метки. Конструкция &&label берет адрес метки в памяти, сохраняя его в указатель void *ptr. Затем с помощью оператора косвенного перехода goto *ptr; выполняется прыжок по этому адресу. Это нестандартное расширение GCC. После перехода на метку label: функция main возвращает ранее вычисленную сумму.

Floyd's Tortoise and Hare

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

Суть алгоритма: Два указателя ("черепаха" и "заяц") движутся по последовательности с разной скоростью. Заяц делает два шага за итерацию, черепаха — один. Если в последовательности есть цикл, то заяц неизбежно "догонит" черепаху внутри цикла. Если цикла нет, заяц первым достигнет конца последовательности.

#include <stdio.h>

int findCycle(int nums[], int numsSize) {
    if (numsSize <= 1) return -1;

    int tortoise = nums[0];
    int hare = nums[0];

    do {
        tortoise = nums[tortoise];
        hare = nums[nums[hare]];
        if (hare < 0 || hare >= numsSize) return -1;
    } while (tortoise != hare);

    tortoise = nums[0];
    while (tortoise != hare) {
        tortoise = nums[tortoise];
        hare = nums[hare];
    }

    return tortoise;
}

Код использует два указателя — медленный (черепаха) и быстрый (заяц). Оба стартуют с начала массива. Медленный движется на 1 шаг: tortoise = nums[tortoise]. Быстрый — на 2 шага: hare = nums[nums[hare]]. Если массив содержит цикл, быстрый рано или поздно догонит медленного внутри цикла. Это первая фаза — обнаружение факта цикла.

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

Проверка hare < 0 || hare >= numsSize отлавливает выход за границы, что означает отсутствие цикла. Алгоритм работает за O(n) времени и O(1) памяти, не меняя исходные данные. В примере {1,3,4,2,2} последовательность индексов 0→1→3→2→4→2 зацикливается на значениях 2 и 4, а начало цикла — значение 2.

Давайте протестируем код:

int main() {
    int arr[] = {1, 3, 4, 2, 2};
    int size = sizeof(arr) / sizeof(arr[0]);
    int result = findCycle(arr, size);

    if (result != -1) {
        printf("Cycle starts at value: %d\n", result);
    } else {
        printf("No cycle found\n");
    }

    return 0;
}

Как мы видим, массив становится цикличным на 2: Cycle starts at value: 2.

Если хотите больше контента по PostgreSQL и SQL, СУБД, ставьте реакции, тогда я пойму что тема интересна вам.

Каждый, кто проводит в терминале больше пяти минут, сталкивается с одним и тем же: одни и те же длинные команды приходится набирать снова и снова, а рутинные действия отнимают время и внимание. Сначала терпишь, потом — начинаешь оптимизировать.

Простейший алиас в .bashrc или .zshrc кажется небольшим открытием. Первый рабочий скрипт, сохранённый в ~/.local/bin, ощущается как прорыв. Это не просто про лень — это про эффективность, про оптимизацию работы.

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

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