SectorC: компилятор Си в пределах 512 байт

SectorC (github) – это компилятор Си, написанный на ассемблере x86-16 и умещающийся в загрузочный сектор 512 байт машины x86. Он поддерживает достаточное обширный функционал Си для создания реальных и интересных программ, являясь при этом, пожалуй, самым миниатюрным компилятором Си из когда-либо написанных.

В кодировке base64 он выглядит так:

6gUAwAdoADAfaAAgBzH/6DABPfQYdQXoJQHr8+gjAVOJP+gSALDDqluB+9lQdeAG/zdoAEAfy+gI
AegFAYnYg/hNdFuE9nQNsOiqiwcp+IPoAqvr4j3/FXUG6OUAquvXPVgYdQXoJgDrGj0C2nUGV+gb
AOsF6CgA68Ow6apYKfiD6AKrifgp8CaJRP7rrOg4ALiFwKu4D4Srq1fonP9ewz2N/HUV6JoA6BkA
ieu4iQRQuIs26IAAWKvD6AcAieu4iQbrc4nd6HkA6HYA6DgAHg4fvq8Bra052HQGhcB19h/DrVCw
UKroWQDoGwC4WZGrW4D/wHUMuDnIq7i4AKu4AA+ridirH8M9jfx1COgzALiLBOucg/j4dQXorf/r
JIP49nUI6BwAuI0G6wyE0nQFsLiq6wa4iwarAduJ2KvrA+gAAOhLADwgfvkx2zHJPDkPnsI8IH4S
weEIiMFr2wqD6DABw+gqAOvqicg9Ly90Dj0qL3QSPSkoD5TGidjD6BAAPAp1+eu86Ln/g/jDdfjr
slIx9osEMQQ8O3QUuAACMdLNFIDkgHX0PDt1BIkEMcBaw/v/A8H9/yvB+v/34fb/I8FMAAvBLgAz
wYQA0+CaANP4jwCUwHf/lcAMAJzADgCfwIUAnsCZAJ3AAAAAAAAAAAAAAAAAAAAAAAAAAAAAVao=

Поддерживаемый функционал языка

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

К примеру, следующая программа анимирует движущуюся синусоидальную волну:

int y;
int x;
int x_0;
void sin_positive_approx()
{
  y = ( x_0 * ( 157 - x_0 ) ) >> 7;
}
void sin()
{
  x_0 = x;
  while( x_0 > 314 ){
    x_0 = x_0 - 314;
  }
  if( x_0 <= 157 ){
    sin_positive_approx();
  }
  if( x_0 > 157 ){
    x_0 = x_0 - 157;
    sin_positive_approx();
    y = 0 - y;
  }
  y = 100 + y;
}


int offset;
int x_end;
void draw_sine_wave()
{
  x = offset;
  x_end = x + 314;
  while( x <= x_end ){
    sin();
    pixel_x = x - offset;
    pixel_y = y;
    vga_set_pixel();
    x = x + 1;
  }
}

int v_1;
int v_2;
void delay()
{
  v_1 = 0;
  while( v_1 < 50 ){
    v_2 = 0;
    while( v_2 < 10000 ){
      v_2 = v_2 + 1;
    }
    v_1 = v_1 + 1;
  }
}

void main()
{
  vga_init();

  offset = 0;
  while( 1 ){
    vga_clear();
    draw_sine_wave();

    delay();
    offset = offset + 1;
    if( offset >= 314 ){ // используйте модуль значения, чтобы избежать целочисленного переполнения  2^16
      offset = offset - 314;
    }
  }
}

Но как?

О написании SectorC я задумался сразу после завершения Deobfuscating OTCC, так что у меня в голове присутствовало множество свежих идей. К тому же я почитал материалы justine.lol и Tom7, которые дополнительно вдохновили меня на столь абсурдный шаг.

Ожидал ли я, что преуспею? Скорее, нет. Вместить целый компилятор Си в 510 байт памяти инструкций? Удачи!

▍ Токенизация

Первая проблема проявилась очень быстро. В Си один только токенизатор/лексер занимает больше сектора 512 байт. Нам же нужно получать произвольный поток байтов, создавая из него «токены».

Например, код:

int main()
{
  if( a < 5 ){
    func();
  }
}

Будет получен и преобразован в:

'int'  TOKEN_KEYWORD_INT
'main' TOKEN_IDENTIFIER
'('    TOKEN_LPAREN
')'    TOKEN_RPAREN
'{'    TOKEN_LBRACE
'if'   TOKEN_KEYWORD_IF
'('    TOKEN_LPAREN
'a'    TOKEN_IDENTIFIER
'<'    TOKEN_OPERATOR
'5'    TOKEN_NUMBER
')'    TOKEN_RPAREN
{'    TOKEN_LBRACE
'func' TOKEN_IDENTIFIER
'('    TOKEN_LPAREN
')'    TOKEN_RPAREN
';'    TOKEN_SEMI
'}'    TOKEN_RBRACE
'}'    TOKEN_RBRACE

Нам необходимо распознавать keywords, identifiers, operators и numbers. Далее полученные значения нужно будет преобразовывать из строк в целые числа с помощью функции наподобие atoi():

int atoi(const char *s)
{
  int n = 0;
  while (1) {
    char c = *s++;
    if (!c) break;
    n = 10 * n + (c - '0');
  }
  return n;
}

Я написал простой и минималистичный лексер, который занял чуть больше 150 строк Си. Примерно такой же код на x86-16 занял бы от 300 до 450 байт минимум (например, простая инструкция add ax, bx кодируется в 2 байта). И это без учёта таблицы символов, парсера с рекурсивным спуском, кодогенератора, исправления ветвлений и так далее.

Никаких шансов.

Поэтому, естественно, … я продолжил. Всегда ставьте на аутсайдеров – так веселее.

Озарение #1

Первое озарение пришло в процессе размышления о других языках вроде Forth. Токенизатор в Forth довольно примитивен – в нём токены разграничиваются пробелом. При этом каждый токен просто называется WORD без каких-либо особенностей (не совсем так). Хмм, а что насчёт варианта Си, который будет делать так же? Я придумал такой код, который технически остался Си, сохранил полноту по Тьюрингу, но определённо будет пугать любого мейнтейнера.

Буду называть эту версию языка «почти Си»:

int done , a , b , c , p , cond ;
int(main)(){while(!done){
     a = b - c ;
     *(int*) p = b - c ;
     a = *(int*) p ;
     if(cond) a = b - 45 ;
}}

Здесь мы добавили пробелы, расположенные стратегически для создания «мега-токенов».
К примеру, одним из таких «мега-токенов» является int(main)(){while(!done){

В некотором смысле мы фактически получили язык больше похожий на:

VAR_BEGIN done AND a AND b AND c AND p AND cond END
MAIN_BEGIN
  a = b - c END
  DEREF p = b - c END
  a = DEREF p END
  COND a = b - 45 END
MAIN_END

Но стандартный компилятор Си также распознаёт его как родной.

Даже после разграничения у нас всё равно получается много токенов, то есть нужно искать другие способы уменьшить токенизатор. Без чего здесь не обойтись? Хмм, довольно трудно избежать atoi(), если мы хотим фактически иметь целочисленные литералы. Что ещё необходимо? Может, ничего?

Озарение #2

Вторым озарением стало то, что atoi() действует для стандартного текста как (плохая) хэш-функция. Она получает символы и обновляет 16-битное целое число. Хэши, пожалуй, являются священным граалем в вычислительном мире. С помощью хорошего хэша можно запросто обойти все трудные проблемы, разменяв их на ещё более трудную (коллизию хэшей), а затем просто проигнорировав её. Гениально. (затыкаю уши пальцами).

Итак, у нас есть следующее:

Реализация «почти Си»

Первая реализация версии «почти Си» вписалась в 468 байт. Это был простой парсер с рекурсивным спуском для токенов atoi. В нём не было никакой таблицы символов. Переменные просто обращаются к сегменту 64К по хэш-значению. Кодогенератор получился похожим на реализованный в OTCC – он использует ax в качестве регистра результатов, передаёт значения в стек, а затем в cx для бинарных операторов.

Минимизация с помощью «byte-threaded code»

В попытке украсть все удачные идеи Forth далее я придумал то, что решил назвать «byte-threaded code»*. Поскольку размер сектора составляет 512 байтов, то если просто выровнять адрес по 2-байтовой границе, то появится возможность выполнять адресацию с помощью одного байта. Мы можем задействовать серию «гаджетов» и реализовать потоковость в стиле Forth.

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

bits 16
  cpu 386

  jmp 0x07c0:entry

entry:
  push cs
  pop  ds

  lea si,operations
next:
  xor ax,ax
  lodsb
  add ax,ax
  push next
  jmp ax

putch:
  mov ah,0x01
  mov al,bl
  mov dx,0
  int 0x14
  ret

  align 2
hang:
  jmp hang

  align 2
print_F:
  mov bx,'F'
  jmp putch

  align 2
print_G:
  mov bx,'G'
  jmp putch

operations:
  db 17  ; print_F
  db 20  ; print_G
  db 17  ; print_F
  db 17  ; print_F
  db 20  ; print_G
  db 17  ; print_F
  db 17  ; print_F
  db 17  ; print_F
  db 20  ; print_G
  db 16  ; hang

К сожалению, nasm не позволяет выполнять что-либо наподобие db print_F/2, поэтому мне пришлось написать для этого небольшой кастомный код ассемблера.

Увы, эта идея не сработала. В 512 байтах издержки этой вычислительной модели в стиле Forth себя не оправдывают. Здесь получается много мелких накладных расходов: выравнивание по 2 байтам, дополнительные инструкции ret, вызов других «потоков», функция next и так далее. Размер этой потоковой версии получился почти таким же, как у прежней.

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

Минимизация простой версии

В итоге я вернулся к простой версии и минимизировал её, насколько это оказалось возможным. Мне удалось сократить размер с 468 до 303 байтов (165 байт экономии: 510 — 303 ⇒ 207 свободных байтов для нового функционала).

На какие я пошёл ухищрения:

• Реорганизовал код так, чтобы инструкции выполнялись последовательно без явного использования команд jmp или call.
• По возможности использовал завершающие вызовы через jmp.
• Произвёл слияние вызовов (например, call tok_next2 вместо call tok_next; call tok_next).
• Активно задействовал stosw и lodsw.
• Устранил таблицы машинного кода для получения менее затратных встроенных версий stows.
• Использовал cmp ax,imm вместо cmp bx,imm.
• Сохранил размер смещений переходов в пределах 8 бит для более эффективного кодирования.

Смотри, мам, реальный Си!

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

• Произвольно вкладываемый блок инструкции if с произвольным условным выражением.
• Произвольно вкладываемый блок инструкции while с произвольным условным выражением.
• Множество операторов: +, -, *, &, |, ^, <<, >>, ==, !=, <, >, <=, >=
• Группирующие выражения: ( expression )
• Определения функций и рекурсивные вызовы функций (с использованием func() в качестве хэш-значения в сегменте 0х3000 таблицы символов)
• Специальную инструкцию asm для встраиваемого машинного кода.
• Однострочные комментарии //.
• Многострочные комментарии /*.
• Приём для «вставки пробелов» перед точками с запятой, чтобы код выглядел более типично.

Наиболее значимый фактор здесь – это таблица binary_oper_tbl, которая обеспечивает очень экономичный способ добавления множества операций. Каждый оператор представляет собой просто пару <16-битное значение токена> <16-битный машинный код>, занимающую всего 4 байта. Перечисленные выше 14 операторов требуют 56 байт плюс небольшие издержки на сканирование таблицы.

Грамматика

Вот вся спецификация грамматики:

program     = (var_decl | func_decl)+
var_decl    = "int" identifier ";"
func_decl   = "void" func_name "{" statement* "}"
func_name   = <identifier that ends in "()" with no space>
statement   = "if(" expr "){" statement* "}"
            | "while(" expr "){" statement* "}"
            | "asm" integer ";"
            | func_name ";"
            | assign_expr ";"
assign_expr = deref? identifier "=" expr
deref       = "*(int*)"
expr        = unary (op unary)?
unary       = deref identifier
            | "&" identifier
            | "(" expr ")"
            | indentifier
            | integer
op          = "+" | "-" | "&" | "|" | "^" | "<<" | ">>"
            | "==" | "!=" | "<" | ">" | "<=" | ">="

Помимо этого, здесь поддерживаются и // однострочные комментарии, и /* многострочные */.

Примечание: эта грамматика занимает 704 байта в ASCII, что на 38% больше её реализации.

Встраиваемый машинный код

Язык программирования без ввода-вывода окажется бесполезен. А поскольку Си в этом отношении универсален, нам нужно выбрать подходящий вариант. Я склонился к расширению asm, которое позволяет программам генерировать встроенные литералы сырого машинного кода x86-16. Используя asm, программы могут обращаться к любому низкоуровневому компоненту машины. В своём примере кода это расширение я активно задействую.

Обработка ошибок

Что такое «обработка ошибок»?

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

Для менее же всесильных представителей мира программирования также была создана программа lint (которая не вмещается в сектор), предназначенная для перехвата ошибок. Автору при разработке этот инструмент, естественно, не потребовался.

Среда выполнения

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

В SectorC по пути rt/ находится среда выполнения, состоящая из двух файлов, реализованных на самом Си:

• rt/lib.c: коллекция библиотечных процедур, зачастую встраиваемых через asm.
• rt/_start.c: фактическая точка входа _start().

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

Примеры

Приведу несколько примеров, в которых используются уникальные аппаратные аспекты x86-16 IBM PC:

• examples/hello.c: выводит текстовое приветствие на экран и записывает его в память по адресу 0xB8000.
• examples/sinwave.c: отрисовывает движущуюся синусоидальную волну в режиме VGA 13h с использованием соответствюущей плохой аппроксимации sin(x).
• examples/twinkle.c: воспроизводит “Twinkle Twinkle Little Star” через PC-спикер (предупреждение: ГРОМКО).

Заключение

Будет уместным завершить статью чем-то вроде «основных выводов» или «усвоенных уроков». Итак…чему же мы научились? Честно говоря, не уверен. Но забавы ради выражу эту идею в виде таблицы в стиле «Выбери собственное приключение»: