си

Пока проект внедрения Юникода во «Флиппер Зеро» на паузе, — разработчики занимаются обновлением одной из важных библиотек, я вспомнил, что вообще-то в природе существуют разные способы ускорения обработки строки в кодировке UTF-8. Именно её я выбрал для хранения строк. А поскольку железо у «Флиппера» весьма ограниченное, может быть имеет смысл подумать как сэкономить ресурсы.

Например, когда-то, ещё во времена работы в «Яндексе», я сравнивал между собой различные реализации функции strlen, где ускорение достигалось за счёт векторизации.

Любопытно посмотреть как обстоят дела с ускорением таких вещей на процессоре, который установлен на «Флиппере». Правда до него у меня руки ещё не дошли, но я уже потренировался на своём «Макбуке», благо тут процессор той же архитектуры.

Идея всё та же — векторизация. За референс я взял наивную реализацию с перебором по одному байту:

size_t strlen_naive(const char* str) {
    size_t len = 0;
    char ch;
	
    while ((ch = *str++)) {
        len += (ch & 0b11000000) != 0b10000000;
    }

    return len;
}

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

После переделки она стала выглядеть так:

size_t strlen_php(unsigned char * p) {
    size_t len = 0;

    const int8x16_t threshold = vdupq_n_s8(-64);
    const uint8x16_t delta = vdupq_n_u8(1);

    for(;;) {
        int8x16_t operand = vld1q_s8((const int8_t * ) p);
        if (vminvq_u8(operand) == 0) {
            break;
        }

        uint8x16_t lt = vcltq_s8(operand, threshold);
        len += sizeof(uint8x16_t) - vaddvq_u8(vandq_u8(lt, delta));
        p += sizeof(uint8x16_t);
    }

    for (signed char c; (c = *p); p++) {
        if (c >= -64) {
            len++;
        }
    }

    return len;
}

Повторюсь, у меня пока не дошли руки попробовать это всё на «Флиппере», но на моём «Макбуке» результаты выглядят следующим образом. Это десять тысяч прогонов на русскоязычном тексте, размер которого чуть больше ста тысяч символов.

Name   Length  Time
----   ------  ----
PHP    117465   97797
Fast   117465  143780
Naïve  117465  531535

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

Цифры в попугаях (больше — хуже), которые выдаёт сишная функция clock(), компилировал компилятором Clang 15 с ключом -O3.

Наверняка вам интересно, что там происходит с моим мини-проектом по внедрению Юникода во «Флиппер Зеро»? Шучу, понимаю, что всем пофигу!

Тем не менее всё равно напишу. Проект пока на паузе.

Причина — разработчики прошивки решили обновить фреймворк «U∞g²», который используется для вывода текста. Дело хорошее, но поскольку мои правки зависят от этого фреймворка, придётся подождать его обновления.

Что там в нём изменится мне интересно, можно бы посмотреть, но форсировать не буду, обновится — гляну.

А пока заметил, что переписать придётся ещё одну функцию — elements_multiline_text_aligned. Когда просматривал, не заметил, что в ней используется местный аналог printf, который с Юникодом сроду не работал:

if((start[chars_fit] == '\n') || (start[chars_fit] == 0)) {
    line = furi_string_alloc_printf("%.*s", chars_fit, start);
} else if((y + font_height) > canvas_height(canvas)) {
    line = furi_string_alloc_printf("%.*s...\n", chars_fit, start);
} else {
    chars_fit -= 1; // account for the dash
    line = furi_string_alloc_printf("%.*s-\n", chars_fit, start);
}

Конкретно это место никак не зависит от «U∞g²», можно бы и заняться. Но пока у меня с новогодними праздниками не задалось — всё ещё работаю, плюс немного заболел — горло болит и кашель. Разгребусь, выздоровлю и займусь.

Решил ковать железо, пока горячо — раз дали шанс, постараюсь довести поддержку UTF-8 во «Флиппере Зеро» до ума. Я уже пытался прикинуть объём работ, но при внимательном рассмотрении оказалось, что получившаяся оценка сильно сверху — доработки требуют только три функции, а не одиннадцать.

Тем не менее, поначалу я всё равно приуныл, — там вполне есть где накосячить, значит результат надо тестировать. У «Флиппера» нет эмулятора, получается надо компилировать прошивку, потом заливать её в устройство, делать примеры и уже на них смотреть что пошло не так. Долго и трудоёмко.

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

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

Работу я разбил на два этапа — пока закоммитил только функции elements_scrollable_text_line и elements_string_fit_width. Функцию elements_text_box перепишу попозже, она объёмная, если найдутся замечания по ревью текущего коммита, добью сначала их, так проще.

Вывод информации стендом для тестирования изменений в функциях АПИ «Флиппера Зеро»

Вот что значит живой, развивающийся проект. Стоило закоммитить в репозиторий «Флиппера Зеро» своё второе предложение по улучшению поддержки Юникода во «Флиппере», почти сразу его рассмотрели и дали обратную связь. Так далеко не всегда бывает.

Похоже зря я опасался, что поддержка Юникода никому не нужна, пока всё идёт очень гладко. Одно одобрение коммита из необходимых трёх я получил, но мне напомнили, что работа ещё не окончена.

«Most of the methods in elements library are not ready for unicode…»

Я это понял и сам, но, честно сказать, всего за несколько минут до того как получил сообщение от ревьювера. Мои правки пока касались только вывода текста, тогда как во «Флиппере» поверх него работает АПИ, позволяющее выводить ещё и различные элементы интерфейса — окошки, кнопки и тому подобное.

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

< targets/f7/api_symbols.csv awk -F, '$3~/^elements_/&&/char|String/{print$3}'
elements_bubble_str
elements_button_center
elements_button_left
elements_button_right
elements_multiline_text
elements_multiline_text_aligned
elements_multiline_text_framed
elements_progress_bar_with_text
elements_scrollable_text_line
elements_string_fit_width
elements_text_box

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

Не везде, кстати, побайтовый перебор является проблемой. В первой же функции по списку всё будет работать нормально и без правок:

uint8_t lines = 1;
const char* t = text;
while(*t != '\0') {
    if(*t == '\n') {
        lines++;
        uint16_t temp_width = canvas_string_width(canvas, t + 1);
        str_width = temp_width > str_width ? temp_width : str_width;
    }
    t++;
}

Тут идёт подсчёт количества строк и вычисление их максимальной ширины. Для этого функция разбивает последовательность байтов по символу перевода строки — \n. Это работает, так как кодировка UTF-8, используемая тут, устроена так, что символ \n однобайтовый и не может встретиться внутри многобайтовой последовательности.

В других же случаях кое-что придётся довольно существенно переписать, работы предстоит немало.

— Прощай, Фариа. Дни, проведённые с тобой, я запомню, как самые счастливые дни моей жизни. Но и я больше не жилец, потому что отсюда выходят только мертвецы.
— Сын мой, если отсюда выходят только мертвецы, то превратитесь в мертвеца!

Фильм «Узник замка Иф», 1988

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

К сожалению, всё АПИ так устроено, что на вход можно подавать только char, то есть только те символы, коды которых помещаются в байт, в данном случае.

Когда я научился манипулировать шрифтами, которые использует «Флиппер», мне пришло в голову, что если всё, что у нас есть должно поместиться в байт, то почему бы не сделать шрифт в однобайтной кодировке?

Я, конечно, не сомневался, что это заработает, но попробовать не помешало. Много времени не заняло. Взял русский пиксельный шрифт, преобразовал его в формат BDF утилитой otf2bdf, сдвинул русские буквы на их места в кодировке CP1251 и проверил работает ли это на самом деле.

Основной код выглядит следующим образом:

canvas_clear(canvas);
canvas_set_color(canvas, ColorBlack);
canvas_set_custom_u8g2_font(canvas, silkscr_rus);

char* str = recode_to_cp1251("ВЫВОД РУССКОГО ЯЗЫКА В КОМПОНЕНТ");
elements_multiline_text_aligned(canvas, 0, 0, AlignLeft, AlignTop, str);
free(str);

Текст приходится кодировать, но это единственное неудобство. Если всё что нужно помещается в байт, то способ рабочий.

Вывод русских букв шрифтом в однобайтной кодировке CP1251

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

Метался-метался, пока внутри исходников прошивки не наткнулся на использования расширения «операторы в выражениях» и сразу успокоился. Раз в прошивке есть, то и мне можно.

Я с первого приложения использую атрибут __cleanup__, но там я ещё скромничал — он используется только один раз. А теперь осмелел и завёл себе макрос с __auto_type, о применении которого мечтал со времён случайного опыта программирования на Си++. Теперь и определения переменных идут стройными рядами, и задумываться о подходящих типах не приходится.

Братишка мне давно говорит, чтобы я не мучился со своим Си и писал на Си++, но ничего не могу с собой поделать: не люблю этот язык, просто не-люб-лю.

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

Только выложил её на «Гитхаб», как мне написал автор одной из популярных альтернативных прошивок, прислал патч, исправляющий некую ошибку и попросил английскую версию, — хочет включить игру в свою прошивку.

Вчера для «Флиппера» пришёл чехол из Китая, выглядит — супер!

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

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

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

Файл описания языка, пример для русского

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

Если открыть словарь для английского языка обычным текстовым редактором, то внутри будет текст, с русским такой номер не пройдёт. Объясню почему.

Когда я только начал программировать игру, начал я с упаковки русского словаря в программный код и генерации случайного слова. Оказалось, что быстро выбрать случайное слово не так-то просто. Первый вариант работал очень медленно, поэтому я сделал оптимизации, которые мне помогли достичь комфортной скорости.

Во-первых, я перешёл на другой генератор — встроенный вызов furi_hal_random_get() вместо обычного для Си random(). Друг, который в прошлом имел дело с микроконтроллёрами, сказал, что как правило лучше использовать то, что предлагает фреймворк — так быстрее.

Во-вторых, я переделал метод выбора случайного слова. Раньше я выбирал слово с линейной сложностью — генерировал номер строки и читал словарь, пока его не достигну. Переделал на константную — выбираю случайное смещение в файле и ищу следующее слово после него. Что дало теоретический положительный эффект — более длинные слова выбираются чаще.

В-третьих, почти в два раза сократил файл словаря. Любая русская буква занимает в распространённых юникодных кодировках два байта, но второй байт всегда одинаковый, его можно выкинуть. Если посмотреть на ряд, описывающий клавиши в моём файле, видно, что первая четвёрка всё время повторяется. То есть из кода русской буквы А — 0x0410 можно убрать 0x04 и оставить только 0x10, мы и так будем знать какую букву кодировать.

В словаре так и сделано. Поскольку внутри программы я храню различные состояния в виде массива, мне нужно знать минимальный получившийся код символа, чтобы вычитать его, преобразовывая код в смещение в массиве. Для русского языка минимальный код будет у буквы А — 0x10, как я показывал выше, то его и нужно записать в файл описания языка. Цифра 16 в нём — это и есть 0x10 в десятичной кодировке.

Надеюсь сегодня допишу всё что нужно и выложу новый вариант.

Вкратце: в русским текстом работать можно, но сложно, код лежит на «Гитхабе».

Не мог не обратить внимание, что несмотря на приличное количество русскоязычных авторов программ для «Флиппера Зеро» и российское происхождение устройства, в софте под него нигде не обнаружилось ни одной буквы по-русски.

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

Вывод русских букв (трансляция с экрана через оболочку qFlipper)

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

Внутри «Флиппера» довольно много всякого АПИ для вывода текста, от незатейливого, выводящего строку в заданные координаты, до довольно навороченного, умеющего переносить и выравнивать текст. К сожалению, с русскими буквами оно работать не умеет.

Под капотом у этого АПИ — очень известная в своей нише библиотека U∞g2, у которой по историческим, видимо, причинам есть два набора функций для работы со строками. Одни принимают только однобайтовую кодировку ASCII, другие работают в Юникоде.

АПИ «Флиппера», к сожалению, использует функции, которые с Юникодом работать не умеют. К счастью, по какой-то случайности, упомянутое АПИ содержит два вызова, которые помогают решить эту проблему, правда придётся помучаться.

Первый из них — canvas_set_custom_u8g2_font.

Чтобы что-то написать русскими буквами, нужен шрифт, который их содержит. Стандартный вывод canvas_set_font позволяет выбрать один из нескольких шрифтов, ни одни из которых кириллицу не поддерживает. Тут и приходит на помощь canvas_set_custom_u8g2_font. Он позволяет выбрать произвольный шрифт пакета U∞g2, — внутри их целая куча и некоторые в названии содержат слово «cyrillic».

Вот как я это делаю:

#include <u8g2/u8g2_fonts.c>
// …
canvas_set_custom_u8g2_font(canvas, u8g2_font_haxrcorp4089_t_cyrillic);

Файл u8g2/u8g2_fonts.c внутри себя содержит шрифты в особом формате, можно открыть его прямо в текстовом виде и посмотреть как всё устроено.

Шрифт мы выбрали, теперь надо что-нибудь вывести. Тут на помощь приходит canvas_draw_glyph. «Под капотом» у него лежит u8g2_DrawGlyph, которая понимает символы Юникода почти без танцев с бубном. Думаю, это чистое везение — наверняка эта функция появилась сильно позднее, поэтому у неё нет двух вариантов для работы с разными кодировками.

Плохая новость в том, что строки в коде мы обычно пишем в кодировке UTF-8, а canvas_draw_glyph ожидает их в UCS-2. Но есть и хорошая новость — в прошивке доступно АПИ для перекодирования, как обычно, великолепно документированное на языке Си.

Но canvas_draw_glyph, как можно понять из названия, выводит только один символ. Как же вывести строку? Достаточно просто — надо вывести её посимвольно, сдвигая координату на ширину символа. Звучит просто, но как это сделать?

Тут нас ждёт очередная засада. Дело в том, что canvas_glyph_width, которая должна бы это делать, принимает на вход только char, при том, что нижележащая u8g2_GetGlyphWidth преспокойно работает с Юникодом.

Поэтому я сделал просто — выдрал реализацию u8g2_GetGlyphWidth себе в исходники. В итоге мякотка моего решения выглядит вот так:

void unicode_draw_utf8_str(Canvas* canvas, uint8_t x, uint8_t y, char* str) {
    FuriStringUTF8State state = FuriStringUTF8StateStarting;
    FuriStringUnicodeValue value = 0;

    for(; *str; str++) {
        furi_string_utf8_decode(*str, &state, &value);
        if(state == FuriStringUTF8StateError) furi_crash(NULL);

        if(state == FuriStringUTF8StateStarting) {
            canvas_draw_glyph(canvas, x, y, value);
            x += unicode_GetGlyphWidth(&canvas->fb, value);
        }
    }
}

Тут unicode_GetGlyphWidth — скопированная реализация u8g2_GetGlyphWidth, а furi_string_utf8_decode используется для кодирования UTF-8-строки в последовательные символы UCS-2.

Вчера вечером разобрался-таки с прокруткой экрана для «песни про пиво» под Флиппер Зеро и выложил всё в репозиторий.

Как я уже писал, документации на удивление мало, пришлось налегать на чужие исходники. Если касаться темы прокрутки экрана, то, по всей видимости, существуют два способа: перерисовывать экран самостоятельно, вызывая каждый раз компонент полосы прокрутки с нужным значением или заморочиться с созданием так называемой «сцены», разместить на ней виджет прокручиваемого текста и засунуть туда весь текст, который надо прокручивать, целиком.

Второй способ больше подходит для многоэкранных приложений, поэтому его я не выбрал — для моих целей там слишком много мороки. Поэтому в этой части всё получилось достаточно просто:

void beer_render_callback(Canvas* canvas, void* ctx) {
    // …
    elements_scrollbar(canvas, BEER_MAX - pos, BEER_MAX + 1);
    // …
}

int32_t beer_main(void* p) {
    // …
    switch (event.key) {
        case InputKeyDown:
            if (app->pos > 0) app->pos--;
            break;

        case InputKeyUp:
            if (app->pos < BEER_MAX) app->pos++;
            break;

        default:
            break;
    }

    view_port_update(app->view_port);
    // …
}

В цикле опроса клавиатуры ловим клавиши «вверх» и «вниз», в соответствии с клавишей увеличиваем или уменьшаем счётчик, после чего вызываем перерисовку, в коллбеке которой выводим экран и полосу прокрутки с правильной позицией.

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

Мне месяц назад на день рождения подарили «Флиппер Зеро» — «перочинный ножик для хакера». Довольно известное в узких кругах устройство, очень занятное. Но об этом как-нибудь в другой раз.

Давно подмывало что-нибудь под него написать, но всё как-то занят по уши был всякими неотложными делами — то сериалы надо посмотреть, то ленту в соцсетях полистать. Но наконец освободился, сегодня утром начал.

Попробую написать «Песню о пиве»

В интернете есть несколько статей о том как начать, которые мне очень помогли. Довольно быстро я научился собирать первое приложение, которые выводит строчку текста и опрашивает клавиатуру. По пути поразился сколько бойлерплейта (шаблонного почти одинакового для каждого приложения кода) пришлось написать. Очень не хватает какого-нибудь фреймворка.

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

Недавно познакомился с интересным компилятором подмножества языка Си — SectorC. Он интересен тем, что влезает в один сектор (512 байт), но позволяет писать вполне реальные программы. В реализованном языке очень многого нет, тем не менее, это очень интересное достижение и мне было интересно поразбираться как всё сделано. Кстати, результат автора мне удалось в несколько приёмов уменьшить на несколько байт.

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

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

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

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

Отсюда следует, что последовательно называющиеся переменные — a, b, c и так далее, с будут в памяти располагаться последовательно со смещением в два байта, точностью до переполнения. При этом их даже не обязательно определять — переменная с любым именем существует с начальным нулевым значением.

Идём дальше.

В языке есть любопытная операция — &, позволяющая получить адрес переменной, который, напомню, равен одновременно хешу (atoi) к её имени. Для однобуквенных имён это позволяет по полученному адресу восстановить код символа — надо поделить полученное значение на два и добавить 48 — код символа 0.

Таким образом, передав в функцию адреса & H, & e, & l, & l, & o, мы сможем восстановить из них символы и составить из них слово Hello. Если записать эти адреса в переменные, которые располагаются в памяти подряд, можно, читая память последовательно, выводить закодированную строку.

Есть ли в языке способ прочитать что-то по адресу? Как ни странно, есть — токен *(int*) позволяющий это сделать.

Теперь всё вышесказанное можно соединить в следующий довольно компактный код:

void print_str()
{
    print_str_pointer = & _0;
    while( *(int*) print_str_pointer ){
        print_ch = ( *(int*) print_str_pointer >> 1 ) + 48; print_char();
        print_str_pointer = print_str_pointer + 2;
    }
}

void main()
{
    _0 = & H; _1 = & e; _2 = & l; _3 = & l; _4 = & o; _5 = 0;
    print_str(); // Hello
}

Очень неудобно, что в языке SectorC нет деления. Я сначала думал, что это из-за ограничений — ведь задумка в том, чтобы компилятор помещался в сектор (512 байт). В таком случае можно было бы выкинуть операции левого и правого сдвига (<< и >>), чтобы освободить место. Эти операции как раз можно было бы заменить умножением и делением.

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

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

При этом надо знать две вещи: присваивание значения переменной происходит через регистр AX, так что присвоив переменную саму себе, можно записать в AX её значение, и второе — если посчитать atoi (см. мою вчерашнюю заметку) для имени переменной и умножить получившееся число на два, можно получить ячейку, где хранится значение этой переменной.

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

Объединив всё вышесказанное, получим такой результат:

int div_a; int div_b; // input
int div_result;

void div()
{
    div_b = div_b;             // mov ax, [&div_b]
    asm 145;                   // xchg cx, ax
    asm 49; asm 210;           // xor dx, dx
    div_a = div_a;             // mov ax, [&div_a]
    asm 247; asm 241;          // div cx

    asm 163; asm 48; asm 193;  // mov [&div_result], ax
}

void main()
{
    div_a = 35500; div_b = 113; div();
    print_num = div_result; print_u16(); // «314»
}

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

Когда смотришь на код такого маленького объёма, сразу возникает вопрос — каким чудом удалось туда запихнуть грамматику языка Си, даже если какое-то подмножество? Ответ — хеширование.

Автор использует реализацию функции atoi, которая превращает любые строки в шестнадцатибитное числа:

unsigned short sectorc_atoi(const char *s)
{
    unsigned short n = 0;
    for (;;) {
        char c = *s++;
        if (!c) break;

        n = 10 * n + (c - '0');
    }

    return n;
}

Все токены, которые встречаются в программе, обязательно разделяются пробелами (за исключением ;, для него есть специальная обработка). Это позволяет довольно просто парсить программу — любой токен скармливаем atoi, получаем число и по таблице смотрим с чем имеем дело.

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

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

Если линтер выключить, можно достигнуть интересного эффекта. Для каждого токена можно вычислить коллизию позаковыристей и написать всю программу без букв и цифр. SectorC как будто бы «из коробки» предназначен для запуска обфусцированного кода.

Ниже программа, выводящая «Hello» (её надо запускать без линтера):

<**^ ')'|] /=]
    -_.@" -[ )~( /@< $^+>\() /<'
    -_.@" -[ /<'' /@< $^+>\() /<'
    -_.@" -[ ,[~ /@< $^+>\() /<'
    -_.@" -[ +^^` /@< $^+>\() /<'
    -_.@" -[ /<(' /@< $^+>\() /<'
,[_

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

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

Обфусцированный таким образом листинг, запускающий файл и программу для поиска коллизий выложил на «Гитхаб», можно посмотреть подробности там.

Кстати, такое развлечение, когда мы не используем в программе алфавитно-цифровые символы, называется ЧтоНибудьFuck, уж так повелось, — FuckJS, FuckPHP и так далее. Отсюда и название заметки.

Вчера я обещал рассказать что я придумал, чтобы компактнее выводить строки в языке SectorC. Напомню, это компактный компилятор подмножества Си, который занимает один сектор (512 байт).

Для начала посмотрим что доступно в компиляторе для вывода текста. В самом языке для этого ничего нет, но если заглянуть в стандартную библиотеку языка, которая подключается автоматически, то можно увидеть там функции print_char(), print_u16() и print_i16(), предназначенные, соответственно, для вывода символа, заданного его кодом, целого числа без знака и целого числа со знаком.

Соответственно вывод «Hello» выглядит так:

print_ch =  72; print_char(); // H
print_ch = 101; print_char(); // e
print_ch = 108; print_char(); // l
print_ch = 108; print_char(); // l
print_ch = 111; print_char(); // o

Очень многословно. Когда я вчера написал «песню о пиве» в таком формате, программа получилась чересчур длинной. Мне захотелось как-то её упросить. Вот как я рассуждал.

Код задаётся целым типом int, который имеет в этом языке 65536 значений. Поскольку мне нужны не все буквы, выглядит так как будто в одно число можно запихнуть несколько знаков. Но сколько?

Для начала посмотрим сколько символов вообще используется. Цифры меня не интересуют (числа выводятся отдельной функцией), поэтому выкинем их:

import sys
from collections import Counter
data = Counter(x for x in ''.join(sys.stdin.readlines()) if x > '9' or x < '0')

print(data)

Вот что получилось:

Counter({' ': 2306, 'e': 1305, 'o': 1108, 't': 903, 'l': 702, 'b': 601, 'n': 600, 'a': 598, 's': 497, 'r': 403, 'f': 300, 'w': 300, '\n': 298, 'd': 298, 'h': 202, ',': 200, '.': 200, 'u': 100, 'T': 99, 'i': 99, 'k': 99, 'p': 99, 'm': 4, 'G': 1, 'N': 1, 'y': 1})

Двадцать шесть символов. Жаль не шестнадцать, было бы удобно хранить — как я говорил выше, значений в целом типе помещается 65536 штук. Какая связь? Чтобы это понять, разберёмся откуда взялось число 65536.

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

Отсюда получается, байт — восемь бит по два значения или 2⁸ = 256 значений, два байта — 256² = 65536. В десятичной системе выглядит довольно бессмысленно, но если перейти на шестнадцатеричную, где цифры записываются от 0…9, A…F, с префиксом 0x (он ставится чтобы различить две формы записи числа), то становится понятнее.

Тогда число 65536 будет выглядеть как 0xFFFF — визуально распадается на два байта по 256 (0xFF) значений или на четыре полубайта по 16 (0xF).

Я решил хранить символы в полубайтах. Поскольку символов у меня 26, а в полубайте помещается 16 значений, то одно значение пришлось занять префиксом — если он встречается, то мы используем вторую таблицу символов. Под префикс я выделил 0xF. Таким образом, в одном int можно закодировать от двух до четырёх символов.

Например, число 0x2F40 или 0x2 0xF 0x4 0x0 означает, что мы смотрим второй символ в первой таблице, потом переключаемся на вторую (так как встретили 0xF) и смотрим там четвёртый символ, а символ 0x0 имеет специальное значение, — он не выводится и нужен для того, чтобы у нас была возможность закодировать строку, которая короче, чем могла бы поместиться.

В первую таблицу я поместил самые часто встречающиеся символы, во вторую — те, что встречаются реже. Получилось намного компактнее. Например, строка «hello» в моём алфавите выводится вот так:

s = 21023; ps(); s = 53; ps(); // 0x521F, 0x35

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

Код для преобразования строк в такую форму выглядит следующим образом:

input = 'hello'

from itertools import *
# основная таблица
t0 = [' ', 'e', 'o', 't', 'l', 'b', 'n', 'a', 's', 'r', 'f', 'w', '\n', 'd']
# и дополнительная
t1 = ['h', ',', '.', 'u', 'T', 'i', 'k', 'p', 'm', 'G', 'N', 'y']

# поиск символов в таблицах
def conv(ch):
    try:
        yield t0.index(ch) + 1
    except ValueError:
        yield 0xF
        yield t1.index(ch) + 1

# подготовка к разбиению по группам, которые будут кодироваться вместе
def make_shifter():
    pos = 0
    gr  = 0

    def shifter(v):
        nonlocal pos
        nonlocal gr

        if pos == 4:
            pos = 0
            gr += 1

        # префикс переключения таблиц не может остаться в одиночестве,
        # поэтому мы не можем оставить его в хвосте
        if pos == 3 and v == 0xF:
            pos = 1
            gr += 1
        else:
            pos += 1

        return (v, gr, )
    return shifter

shifter = make_shifter()

# нумеруем группы символов
gen = (shifter(x) for x in chain(*(conv(ch) for ch in input)))
# собираем группы символов вместе
gen = groupby(gen, key = lambda x: x[1])

# двигаемся по собранным группам, собираем их в число
for x in gen:
    sum = 0
    for y in list(x[1])[::-1]:
        sum *= 16
        sum += y[0]

    print("s = {}; ps(); ".format(sum))

Теперь только осталось запрограммировать декодирующую часть в SectorC. У нас будет две функции — одна достаёт из числа по одном полубайту за раз, вторая преобразовывает полубайт в соответствующий символ. Как всё работает в деталях объяснять не буду, покажу с минимальными комментариями.

Первая выглядит совсем просто:

int s; // input
void ps() {
    while( s ){
        c = s & 15;
        c2c();
        s = s >> 4;
        if( s == ( 0 - 1 ) ){ s = 0; } // signed workaround
    }
}

Напоминаю, что вы языке у функции нет аргументов и возможности вернуть значение — всё делается через глобальные переменные, поэтому код выглядит странновато.

Строка с комментарием нужна, так как число у нас знаковое (то есть возможные 65536 значений делятся пополам, часть значений считается отрицательным, другая часть — положительными). У отрицательных чисел есть особенность — битовый сдвиг (>>) хоть и считается эквивалентом деления на два, но из минус единицы ноль не делает.

c2c тут — как раз функция, которая должна преобразовывать код в символ (code-to-character). Она выглядит сложнее. Поскольку массивов в языке тоже нет, приходится выкручиваться как-то иначе. Самый простой способ — инструкциями if проверять каждое значение и найдя нужно, записать в специальную переменную искомый код.

Сначала я так и сделал, но выглядело, опять же, громоздко. В итоге, переделал чуть попроще: код сравнения выделил в короткую функцию x(), а пару что во что превращается закодировал в один int:

int c; // input
int x;
void x() { if( c == ( x >> 8 ) ){ print_ch = x & 255; } }

После такого кодирования функция code-to-character стала выглядеть вот так:

void c2c() {
    c = c + shift;
    x =  288; x(); x =  613; x(); x =  879; x(); x = 1140; x(); x = 1388; x();
    x = 1634; x(); x = 1902; x(); x = 2145; x(); x = 2419; x(); x = 2674; x();
    x = 2918; x(); x = 3191; x(); x = 3338; x(); x = 3684; x(); x = 4200; x();
    x = 4396; x(); x = 4654; x(); x = 4981; x(); x = 5204; x(); x = 5481; x();
    x = 5739; x(); x = 6000; x(); x = 6253; x(); x = 6471; x(); x = 6734; x();
    x = 7033; x();

    if( c != 15 ){ print_char(); }
    shift = 0; if( c == 15 ){ shift = 15; }
}

Как видите, код 0xF (15) устанавливает флаг сдвига значений shift, который в следующий раз складывается с кодом (c + shift) и сдвигает значение на следующем декодировании. Заметно, что нигде нет else, потому что этого оператора в языке тоже нет!

Как будто бы рассказал всё.

Вместо вывода — интересный своей компактностью компилятор, автору моё уважение, — я даже и не подозревал, что в таком малом объёме можно уложить полноценный язык! Очень и очень круто!

Мне тут попеняли в комментариях, что я совсем забросил раздел, в котором я пишу на разных языках программирования американскую считалочку про пиво на стене. Я почему-то думал, что недавно что-то в него добавлял, а оказалось, что с того раза прошло полтора года.

Пора возобновить.

76. SectorC — очень маленький компилятор подмножества языка Си. Помещается в один сектор — 512 байт, отсюда и название. Язык очень сильно урезанный, но всё равно меня поражает как автор запихнул имеющееся в такой малый объём.

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

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

Самые распространённые в выходном тексте буквы я кодирую полубайтом от 0x1 до 0xE, а более редкие — байтом от 0xF1 до 0xFC. Завтра попробую описать это чуть подробнее.

Немного так же печалит, что нет локальных переменных, параметров и возвращаемых значений — всё передаётся через глобальные переменные, как в ранних Бейсиках. Кроме того, немного по-особенному расставляются пробелы. Так надо для упрощения разбиения компилятором программы на токены.

// Written by Evgeny Stepanischev https://bolknote.ru
// SectorC

int c; // input
int shift; int x;

void x() { if( c == ( x >> 8 ) ){ print_ch = x & 255; } }
void p() { print_ch = c; print_char(); }

void c2c() {
    c = c + shift;
    x =  288; x(); x =  613; x(); x =  879; x(); x = 1140; x(); x = 1388; x();
    x = 1634; x(); x = 1902; x(); x = 2145; x(); x = 2419; x(); x = 2674; x();
    x = 2918; x(); x = 3191; x(); x = 3338; x(); x = 3684; x(); x = 4200; x();
    x = 4396; x(); x = 4654; x(); x = 4981; x(); x = 5204; x(); x = 5481; x();
    x = 5739; x(); x = 6000; x(); x = 6253; x(); x = 6471; x(); x = 6734; x();
    x = 7033; x();

    if( c != 15 ){ print_char(); }
    shift = 0; if( c == 15 ){ shift = 15; }
}

int s; // input
void ps() {
    while( s ){
        c = s & 15;
        c2c();
        s = s >> 4;
        if( s == ( 0 - 1 ) ){ s = 0; } // signed workaround
    }
}

void bottle()  { s = 17249; ps(); s = 596; ps(); }
void of_beer() { s = 6961; ps(); s = 41510; ps(); }
void on_wall() { of_beer(); s = 5937; ps(); s = 8692; ps(); s = 22721; ps(); print_char(); }
void o_more()  { s = 40723; ps(); s = 675; ps(); }

int b; // input
void bottle_b() {
    if( b == 0 ){ s = 55; ps(); }
    if( b > 0 ){ print_num = b; print_u16(); }
    bottle();
    if( b != 1 ){ c = 115; p(); } // s
}

void main() {
    shift = 0; b = 99;

    while( b > 0 ){
        bottle_b(); on_wall();

        s = 303; ps(); /* ', ' */ bottle_b(); of_beer();
        c = 46; p(); // '.'
        print_newline();
        b = b - 1;

        s = 2143; ps(); s = 4735; ps(); s = 4723; ps(); s = 31806; ps();
        s = 59265; ps(); s = 35057; ps(); s = 409; ps(); s = 5231; ps();
        s = 936; ps(); s = 59215; ps(); s = 303; ps();

        bottle_b(); on_wall(); c = 46; p(); // '.'
        print_newline(); print_newline();
    }

    c = 78;  p(); /* 'N' */ o_more(); bottle(); c = 115; p(); // 's'
    on_wall();
    s = 28975; ps(); /* ', n' */ o_more(); bottle(); c = 115; p(); // 's'
    on_wall();
    c = 46;  p(); // '.'
    print_newline(); 

    s = 5039; ps(); s = 16692; ps(); s = 4639; ps(); s = 41801; ps();
    s = 30738; ps(); s = 1566; ps(); s = 53071; ps(); s = 913; ps();
    s = 4767; ps(); s = 41887; ps(); s = 4850; ps();
    b = 99; bottle_b(); on_wall(); c = 46; p(); // '.'
}

Почитал тут на досуге какие ещё расширения есть у «ГНУ Си». Хотя я их и не использую, но знать не помешает. Оказалось, что там много такого, что лично мне хотелось бы видеть в языке. Например, хорошая штука — диапазоны. Выглядят они так:

const char *whatisit(char code) {
    switch (code) {
        case 'a' ... 'z':
            return "lowercase";
        case 'A' ... 'Z':
            return "capital";
        case '0' ... '9':
            return "digit";
        case 0 ... 31:
            return "special";
        default:
            return "unknown";
    }
}

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

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

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

Из-за дикой перегруженности фичами мне никогда не нравился язык Си++. До увлечения игрой «Гопник-2» никогда на нём не программировал, но нужда заставила. Тянет с ней повозиться, а она написана на смеси Си и Си++, правда с упором на Си.

Несмотря на неприязнь к Си++, всё-таки не могу не отметить, что местами на нём программировать куда проще, чем на Си. К сожалению, для того чтобы использовать реально полезные вещи, — нормальные строки или управление памятью, пришлось бы в игре многое переписать, но какие-то мелочи выручают и без переписывания кода.

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

В Си++ оно означает автоматический вывод типа, вместо его явного указания. Клёвая штука, позволяет делать например такое (пример из кода «Гопника-2»):

auto old_mode = set_tty_special_mode();
// тут какой-то код
restore_tty_mode(old_mode);

Фишка тут в том, что у set_tty_special_mode и restore_tty_mode две реализации — под «Виндоуз» своя. Эти две реализации работают с разными типами, под «Виндоуз» там DWORD, в остальных случаях — структура termios.

В Си было бы что-то вроде:

#ifdef __MINGW32__
#typedef DWORD terminal_mode
#else
#typedef struct termios terminal_mode
#endif

terminal_mode old_mode = set_tty_special_mode();
// тут какой-то код
restore_tty_mode(old_mode);

А в Си++ можно просто поставить auto и обойтись без шаблонного кода. Очень хочется иметь такую клёвую примочку и в Си.

Как я писал уже сегодня, мне пришлось вчера выключить буферизацию вывода, так как текст визуально «застревал» на экране. Добавление fflush проблему решало, но не будешь же выставлять этот вызов везде, где есть вывод, это несколько сотен мест.

В общем, вчера я сделал попроще, а сегодня пришла в голову более удачная идея обернуть printf в макрос:

// включаем буферизацию вывода
setvbuf(stdout, nullptr, _IOFBF, 1000);
// делаем макрос со сбросом буфера
#define PRINTF(...) { printf (__VA_ARGS__); fflush(stdout); }

Работает просто отлично, вывод текста стал выглядеть комфортно.

В итоге, вчерашняя мысль адаптировать «Гопника-2» под Виндоуз меня не отпустила. Открыл вечером «ЧатГПТ» и попробовал с его помощью сделать первые шаги.

Несмотря на то, что «Чат» у меня последней, четвёртой версии, всё равно, даже на простых примерах он допускает совершенно детские ошибки, — не подключает нужные заголовочные файлы (мы программировали на Си), упускает важные части.

Пытаемся программировать на пару с «ЧатГПТ-4»; подсказанный пример не скомпилируется

На скриншоте у меня как раз такой пример — он не скомпилируется из-за отсутствия констант и не содержит условия для обработки комбинации Ctrl+C, как было в том коде, который я попросил «ЧатГПТ» переписать.

Вот как в итоге стал выглядеть этот кусок после нескольких уточняющих вопросов и гуглежа:

#ifdef __MINGW32__
    HANDLE hStdin = GetStdHandle(STD_INPUT_HANDLE);
    DWORD mode = 0;
    GetConsoleMode(hStdin, &mode);
    if (echo) {
        mode &= ~ENABLE_ECHO_INPUT;
    } else {
        mode |= ENABLE_ECHO_INPUT;
    }

    SetConsoleMode(hStdin, mode);

    int ch = _getch();
    if (ch == 0x03) // Ctrl+C
    {
        printf("Ctrl+C hit, exiting...\n");
        gracefulexit();
    }

    return ch;
#endif

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

#ifdef __MINGW32__
    SetConsoleCP(CP_UTF8);
    SetConsoleOutputCP(CP_UTF8);
    setvbuf(stdout, nullptr, _IONBF, 0);

    HANDLE handle = GetStdHandle(STD_OUTPUT_HANDLE);
    DWORD mode = 0;
    GetConsoleMode(handle, &mode);
    SetConsoleMode(handle, mode | ENABLE_VIRTUAL_TERMINAL_PROCESSING);
#endif

Пришлось полностью выключить буферизацию, чтобы нормально отрабатывал printf с UTF-8. Работает на троечку — вывод текста стал подтормаживать, такое себе.

Насколько я понял то, что написано в интернете, у консоли Виндоуз до сих пор большие проблемы с кодировкой UTF-8, чтобы их побороть, придётся переделать весь ввод и вывод в программе, а мне этого делать совсем не хочется.

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

По всей видимости тот, кто портировал игру «Гопник 2» под Линукс, сам в свой порт не играл. За эти два дня пришлось исправить два падения, бесчисленное количество логических ошибок, восстановить работоспособность команды «слэм» (есть у «нефора») и дописать здоровые куски для загрузки и выгрузки состояния игры — они там просто отсутствовали.

Дописал новую локацию — станцию метро «Чёрная речка»

Заодно, пока уж более-менее изучил код, добавил новую локацию — станцию метро «Чёрная речка», она «на ремонте», но по ходу игры открывается.

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