Недавно познакомился с интересным компилятором подмножества языка Си — 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
}

У Романа Парпалака прочитал про «простейший HTTP-прокси». Ну нет, действительно простейший HTTP-прокси как-то я изобрёл, когда надо было обновить сервер у одного из заказчиков, а там интернета не было. Я тогда запустил этот прокси у себя и прокинул соединение к себе через SSH-туннель.

Выглядит он так:

<?php readfile($_SERVER["REQUEST_URI"]);

Запускается так:

php -S 127.0.0.1:8080 proxy.php

А вот так работает:

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

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

У жены ситуацию чуть получше — сохранился патефон деда, а у бабушки хранится икона, которая когда-то досталась ей от её бабушки.

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

Сложно сказать откуда во мне любовь к старинным предметам, но наверное, раз существуют музеи, я не один такой. Кажется, если бы я работал сотрудником с допуском к запасниками Национального музея, не вылезал бы оттуда месяцами, — говорят запасники там огромные!

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

Ева выступила дважды — сначала сольно спела песню «Лесной олень» (ей она очень нравится), а после в общем хоре — «Дорогою добра».

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

— Да. Я, конечно, не юрист, но…
— Этот вопрос решают не законники, а психологи. Теперь вся тяжесть проблемы легла на плечи Маллина, и он хорошо это понимал.

— «Маленький пушистик», Бим Пайпер, «Полярис», 1997

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

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

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

Есть тут собачники? У кого-нибудь ещё так же? Как боретесь? Я уже смотрю в сторону каких-нибудь резиновых накладок на когти, если такие существуют.

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

Который год являюсь членом государственной экзаменационной комиссии на двух кафедрах ИВМиИТ КФУ (бывший факультет ВМК) и всё это время меня не могу отделаться от ощущения, что многие студенты руководствуются правилом «всё равно это никто не будет читать».

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

Ещё проблем доставляет мода на тёмные темы оформления — скриншоты с кодом теперь на бумаге выглядят как тёмно-серые буквы на чёрном фоне. Учитывая, что комиссия из-за проектора сидит в полумраке, глаза сломаешь такое читать.

Это 100% никто читать не будет, — просто потому, что прочесть это невозможно.

Какая-то ерунда у меня творится во время просмотра сериалов на ноуте — всё время хочется выйти из полноэкранного режима и посмотреть параллельно что-нибудь ещё — вдруг в «телегу» кто-нибудь написал или статья на «Хабре» новая вышла. Это что за расстройство внимания такое?

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

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

Не понимаю.

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

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

Второе реализовать совсем просто, тут мне помогает некогда богатый опыт программирования на Ассемблерах. SectorC транслируется напрямую в машинный код, а значит адреса возвратов из функций хранятся на стеке. Так что надо всего лишь удалить верхний адрес возврата и мы вернёмся не в функцию, которая нас вызвала, а на уровень выше. Я делаю это командой pop ax.

Теперь посмотрим на первую задачу.

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

Напрашивается следующая реализация, — перед вызовом присваиваем возвращаемую переменную самой себе, в функции return() записываем содержимое AX в какую-нибудь переменную (я выбрал return) и возвращаемся.

Моя реализация вместе с примером использования ниже:

void return()
{
    // mov [&return], ax
    asm 163; asm 236; asm 229;
    // pop ax (clear stack from prev return address)
    asm 88;
}

void random()
{
    // xor ax, ax    int 0x1A         xchg ax, dx
    asm 49; asm 192; asm 205; asm 26; asm 146;
    // xor dx, dx    mov cx, 10
    asm 49; asm 210; asm 185; asm 10; asm 0;
    // div cx         inc dx  xchg ax, dx
    asm 247; asm 241; asm 66; asm 146;
    return();
}

void function()
{
    i = 0; while( i < 20 ){
        random();
        if( i >  return ){
            i = i; return();
        }
        i = i + 1;
    }

    i = 0; return();
}

void main()
{
    function();
    print_num = return; print_u16();
}

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

Продолжаем рубрику «все побежали и я побежал».

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

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

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

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

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

Это работающие куар-коды, ведущие на мой сайт

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

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

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

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

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

Жалкие остатки от писательской мозоли

Очень неудобно, что в языке 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 и так далее. Отсюда и название заметки.

Вчера выложил свою тему оформления для движка «Эгеи». Меня давно просили, а вчера был очередной комментарий на эту тему, ну я и сделал это наконец. Тему надо положить в папку user/themes/bolk, выбрать её в настройках блога и сбросить кеши.

Вчера я обещал рассказать что я придумал, чтобы компактнее выводить строки в языке 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(); // '.'
}

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

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

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

Подарок с рыбалки для дочки — вероятно это мушкетные пули

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

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

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

Прочитал свежую новость о том как ребята из «Гугла» при помощи алгоритмов искуственного интеллекта ускорили сортировку. На коротких последовательностях ускорение там достигает 70%:

AlphaDev’s newly discovered algorithm achieves a 70% increase in efficiency for sorting short sequences of elements and approximately 1.7% for sequences surpassing 250 000 elements, as compared to the algorithms in the C++ library.

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

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

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

Компьютер на базе «Эльбруса», стоит у нас на подоконнике

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

Такой упрощённый процессор дешевле разрабатывать и производить, ну и компилятор дорабатывать проще процессора — новая версия не требует запуска новой производственной линии.

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

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

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