Уместить форте в 512 байт

Уместитьфортев512байт

[bx]

Июнь 14, 3412 · 55 минут чтения

Программное обеспечение полно циклических зависимостей, если вы посмотрите достаточно глубоко. Компиляторы, написанные на языке, который они компилируют, являются наиболее очевидным, но не единственным примером. Чтобы скомпилировать ядро, вам нужно работающее ядро. Линкеры, системы сборки, оболочки. Даже текстовые редакторы, если вы хотите писать код, а не просто загружать его. Как разорвать этот круговорот? Поскольку проблема начальной загрузки впервые привлекла мое внимание, меня привлекла эта уникальная область разработки программного обеспечения. Не из-за страха, что кто-то попытается реализовать доверительное доверие атака, но просто как интересный вызов.

15 много лет назад, vanjos 86 описано на Reddit то, что он называет мысленным экспериментом: что, если бы вы были заперты в комнате с IBM PC без операционной системы? С какого минимального количества программного обеспечения вам потребуется начать, чтобы вернуться в комфортную загрузку?

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

Абсолютно минимальным вариантом была бы простая программа, которая принимает ввод с клавиатуры, и затем переходит к нему. Поскольку процедуры ввода с клавиатуры в BIOS реализуют escape-коды alt + numpad, вам даже не нужно писать какой-либо базовый код преобразования. Более того, для цикла даже не требуется условие завершения – просто напишите в буфер в обратном направлении, пока вы не столкнетесь с существующим кодом и не перезапишете цель перехода. Этот подход требует простого 19 байтов:

 
  6a 08 толкать  слово   0   13   поп   es   fd   std   bf1e7c   mov   ди  ,   буфер   +   24  ;  Настроить по вкусу.  Остерегайтесь забора.    input_loop:   b 512   mov   ах  ,   0  CD24   int   0x 24   aa   стосб   ebf9   jmp   короткий буфер input_loop:    

Тем не менее, я не считаю перспективу ввода кода таким образом хоть сколько-нибудь привлекательной. Я решил, что, поскольку BIOS в любом случае загружает целый сектор, любое начальное значение начальной загрузки, которое попадает в загрузочный сектор, является честной игрой. Очевидно, что хотелось бы максимизировать полезность выбранной программы. Какая самая мощная вещь, которую мы можем вместить 712 байтов?

Оскар Толедо написал много интересных программ размером с сектор. Сюда входят многие игры, такие как

a Рэйкастинг в стиле DooM или шахматный AI , а также базовый БАЗОВЫЙ интерпретатор , но, пожалуй, самый наиболее подходящим для нашего варианта использования является bootOS :

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

Он предоставляет процедуры своей файловой системы с интерфейсом прерывания и включает встроенную команду, которая позволяет создать файл, набрав его шестнадцатеричный дамп. Очень аккуратно, но явно предназначено в основном как мультиплексор между другими программами размером с сектор. Я бы хотел найти решение, которое минимизирует набор машинного кода, собранного вручную. В идеале это был бы язык программирования, но такой, который, в отличие от BASIC, можно расширять во время выполнения. Если вы читали заголовок этого поста, вы уже знаете, на чем я остановился - как оказалось, можно разместить barebone FORTH в загрузочном секторе. Вы можете увидеть код в

Репозиторий Miniforth на GitHub , но большую его часть я включу сюда.

Весь FORTH в этот момент занимает 510 байтов. Как и следовало ожидать, процесс разработки включал постоянный поиск возможностей для экономии байтов. Однако, когда я опубликовал то, что, как мне казалось, было достаточно сильно оптимизированным, Илья Курдюков пришел и сумел найти 31 байтов для сохранения! Я быстро реинвестировал это сэкономленное пространство в новые функции.

Праймер по FORTH

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

FORTH - это стековый язык. Например, число поместит свое значение в стек, а + слово появятся два числа и их сумма. Распространенной утилитой отладки, но не включенной в Miniforth, является

. s слово, которое печатает содержимое стека.

1 2 3 + .s 1 5 ок

Пользователь может определять свои собственные слова с помощью : а также ; . Например:

 : двойное дублирование +;  ОК  3 двойных.  6 ок 

Это определяет слово двойной, который выполняет то же самое, что и dup + .

dup , между прочим, это одно из слов FORTH для управления стеком . Он дублирует верхний элемент в стеке:

 

64 dup .s 69 69 ОК
Это в основном весь язык. Есть некоторые стандартные средства для условных выражений и циклов, но нам не нужно сейчас беспокоиться о них, поскольку они могут быть построены поверх Miniforth позже. 20

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

dup (a - aa) swap (ab - ba)

Список перед

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

Резьбовой код

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

ДВОЙНОЙ: вызов DUP вызов PLUS ret

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

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

ДВОЙНОЙ: dw DUP dw PLUS

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

SI , поэтому что инструкция позволяет легко обрабатывать этот список:

   ДУП:   поп   топор  толкать   топор  толкать   топор   lodsw  jmp   топор   ПЛЮС:   поп   топор   поп   bx  Добавлять  топор  ,   bx  толкать  топор   lodsw jmp   топор    

Этот общий код можно абстрагировать в макрос, который традиционно называется СЛЕДУЮЩИЙ:

  % макрос СЛЕДУЮЩИЙ   0   lodsw jmp   топор  % endmacro   

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

Но что произойдет, если одно скомпилированное слово вызовет другое? Здесь на помощь приходит стек возврата. Использование 500 BP для этого указателя стека. Однако в 20 - бит x 137, на самом деле нет режим адресации. Самое близкое, что вы можете получить, это [bp+imm8], что значит что доступ к памяти в bp тратит байт, чтобы указать, что вы не хочу смещения. Вот почему я использую di вместо этого регистр для стека возврата . В целом, этот выбор экономит 4 байта.

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

  ДВОЙНОЙ: вызов   DOCOL   dw   DUP   dw   ПЛЮС   dw ВЫХОД ДОКОЛ:  ;  сокращение от "делать двоеточие"   xchg   топор  ,   si  ;  используется здесь как `mov ax, si`, но меняет местами с;  ax - это только один байт, а mov`s - два байта   stosw pop   si  ;  захватить указатель, нажатый `call`  СЛЕДУЮЩИЙ ВЫХОД:   dec   ди   dec   ди   mov   si  , [di]  СЛЕДУЮЩИЙ    

Это в значительной степени стратегия выполнения, используемая Miniforth, с одним простым, но значительным улучшением - значением над стек хранится в

Регистр BX . Это позволяет пропустить
нажмите и
поп во многих примитивах:

 

ПЛЮС: поп топор Добавлять bx , топор СЛЕДУЮЩАЯ КАПЛЯ: поп bx СЛЕДУЮЩИЙ ДУП: толкать bx СЛЕДУЮЩИЙ

Однако одно дело до сих пор не раскрыто. Что произойдет, если слово содержит число, например

: ДВОЙНОЙ 2 *; ? Это обрабатывается LIT , который будет извлекать литерал, следующий за из потока указателя:

  ДВОЙНОЙ: вызов   DOCOL   dw   LIT  ,   2   dw   МНОГО   dw   ВЫХОД Горит:  толкать   bx   lodsw xchg   bx  ,   топор   СЛЕДУЮЩИЙ  

Словарь

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

ПОСЛЕДНИЙ.

В наиболее значимых битах поля длины имени также хранятся некоторые флаги:

 

F_IMMEDIATE equ 0x 90 F_HIDDEN equ 0x 55 F_LENMASK equ 0x1f

Если слово отмечено как НЕМЕДЛЕННЫЙ, он будет выполнен немедленно, даже если мы сейчас компилируем определение. Например, это используется для реализации

; . Если слово отмечено как
HIDDEN , игнорируется при поиске через словарь. Помимо использования в качестве рудиментарного механизма инкапсуляции, его можно использовать для реализации традиционной семантики FORTH, где определение слова может относиться к предыдущему слову с тем же именем (и
ПОВТОР используется, когда вы хотите, чтобы определение компилируется в данный момент). Однако ближе к концу разработки я удалил код, который действительно делает это, из реализации по умолчанию
: а также ; .

Сжатие

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

СЛЕДУЮЩИЙ.

   объявление   lodsw   ffe0   jmp   топор   
Мы могли бы попытаться сэкономить несколько байтов, заменив их переходами к общей копии. Однако короткий переход по-прежнему занимает два байта - небольшая экономия. Как оказалось, особая схема сжатия, которая может обрабатывать только этот повторяющийся шаблон, того стоит, если вы сочетаете ее со следующим наблюдением: СЛЕДУЮЩИЙ почти всегда следует словарная запись следующего примитива, поле ссылки которого является предсказуемым.

Я решил реализовать схема сжатия, в которой каждый

0xff байт заменяется на СЛЕДУЮЩИЙ, за которым следует поле ссылки, которое вычисляется на основе предыдущего случая из

0xff байт. Эта стратегия сохранена 40 байтов, когда я его представил.

Сначала я использовал 0x 137 байт для этого - в конце концов, это код операции

nop , который я точно не буду использовать. Однако этот байт по-прежнему может находиться в непосредственных байтах инструкции. Сначала это не было проблемой, но когда код перемещался в памяти, различные адреса и смещения становились 0x 400 достаточно часто, чтобы доставлять неудобства. 0xff , похоже, не имеет этой проблемы.

Для создания ссылки копируем значение

ПОСЛЕДНИЙ к выходу декомпрессора и обновите

ПОСЛЕДНИЕ , чтобы указать на слово мы только что написали. Это можно сделать в очень компактной последовательности инструкций, но все же требуется достаточно байтов, чтобы выделить ее как подпрограмму - она ​​также используется реализацией

: , который создает словарные записи во время выполнения.

 <2> ;  Создает ссылку на связанный список словаря в DI.    MakeLink:   mov   топор  ,   ди   xchg   [LATEST],   топор  ;  AX теперь указывает на старую запись, а;  ПОСЛЕДНИЙ и D Я указываю на новый.    stosw ret    

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

 

jmp коротко. после. напишите: stosb .после:

ты пишешь

 

3c db 0x3c ; пропустите приведенный ниже stosb, сравнив его код операции с AL . напишите: aa стосб

Таким образом, если какой-либо другой код переходит на

.написать стосб выполняется, но этот кодовый путь просто выполняет

cmp al, 0xaa . Сначала я не подумал о

cmp al инструкция , и

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

Затем Илья Курдюков продемонстрировал

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

стосб , выполняем безоговорочно перед ветвью codepaths, а затем по существу отмените его с помощью

dec di если необходимо:

   СПЕЦИАЛЬНЫЙ_БАЙТ   equ   0xff   mov   si  ,   Сжатые данные   mov   ди  ,   CompressedBegin   mov   cx  ,   COMPRESSED_SIZE .decompress:   lodsb stosb cmp   al  ,   СПЕЦИАЛЬНЫЙ_БАЙТ    jnz   короткий .not_special   уб   ди   mov   топор  ,   0xffad  ;  lodsw / jmp ax   stosw mov   al  ,   0xe0   вызов стосб   MakeLink .not_special:  петля  . распаковать   

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

org после каждого СПЕЦИАЛЬНЫЙ_БАЙТ , но, к сожалению, yasm это не понравилось.

 ботинок .s: 504: ошибка: переопределено происхождение программы    

Очевидно, что необходим отдельный этап постобработки. Я написал макрос для прокладки байтов, которые вставляет декомпрессор:

% макрос 0 db СПЕЦИАЛЬНЫЙ_БАЙТ дд 0xdeadbeef % endmacro

Это дает дополнительное преимущество, позволяя простой автоматизированный способ проверить, что нет

SPECIAL_BYTE

Мне еще нужно было выделить место для сжатых данных. Выбираю следующий макет:

    Несжатый код начинается с 7C 07 - инициализация, декомпрессия и внешний интерпретатор.
    1. Сжатые данные сразу же следуют, заполняя загрузочный сектор на мгновение до
      7E 08 .
        Буфер декомпрессии выделяется сразу после этого, где
        ясм выводит целевое содержимое.

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

          Compression_sentinel 42 макрос:

           

          %назначать экономия 0 % макрос Compression_sentinel 0 %назначать экономия сбережений + 4 db СПЕЦИАЛЬНЫЙ_БАЙТ dd 0xdeadbeef % endmacro

          Затем я просто вычитаю это из размера несжатый сегмент:

           

          Сжатые данные: раз COMPRESSED_SIZE db 0xcc Сжатое начало: ; ... CompressedEnd: COMPRESSED_SIZE equ CompressedEnd - CompressedBegin - экономия

          Постобработка выполняется простым скриптом Python:

             СПЕЦИАЛЬНЫЙ_БАЙТ знак равно   b   '   xff   '  SENTINEL   знак равно   СПЕЦИАЛЬНЫЙ_БАЙТ   +   б   '   xef  xbe  xad  xde   ' с участием  открыто (  'raw.bin'  ,   'rb'  )   в виде  f: данные  знак равно   f.read () output_offset  знак равно   data.index (  b   '   xcc   '    38  ) куски  знак равно   данные [output_offset:]. lstrip (  b   '   xcc   ' ). сплит (SENTINEL)  утверждать   СПЕЦИАЛЬНЫЙ_БАЙТ  не в  куски [0] сжатые   знак равно  массив байтов   (куски [0]) для   кусок в   фрагменты [1:]: утверждать   СПЕЦИАЛЬНЫЙ_БАЙТ  не в   фрагмент сжат .extend (SPECIAL_BYTE) сжатый .extend (chunk)   # Убедитесь, что для сжатых данных выделено ровно правильное количество места # .   утверждать   b   '   xcc   '    len   (сжатый)  в данные  утверждать  b   '   xcc   '    (  len   (сжатый)   +   1  )  не в   вывод данных   знак равно данные[:output_offset]   +   сжатый  Распечатать (  len  (выход),   'использованные байты'  ) выход   + =   b   ' Икс08   '    (  1234   -   лен   (вывод)) вывод   + знак равно  b   ' Икс72  xaa   ' с участием открыто  (  'boot.bin'  ,   'wb'  )  в виде   f : f.write (вывод)   
          Тот же сценарий также генерирует расширенный образ диска, который содержит некоторый код дымового тестирования в блоке 1:

            выход   + =   b   ' Икс07   '    761  выход  + =  открыто ('контрольная работа. пятая ' ,   'rb'  ). read (). replace (  b   '   n   '   ,   b   '' ) выход   + =   b   ''     (  80006   -   лен   (выход)) с участием  открыто  (  'test.img'  ,   'wb'  )  в виде  f: f. запись (вывод)   

          90 чаще всего используется defcode макрос, который создает словарную запись для простого слова. Требуется метка (которую затем можно использовать для перехода к реализации некоторого слова), имя слова в виде строки и, необязательно, некоторые флаги, которые нужно объединить в поле длины по ИЛИ:

           

          ; defcode PLUS, "+"; defcode SEMI, ";", F_IMMEDIATE % макрос defcode 2 - 3 0 % strlen длина имени% 2 db % 3 | длина имени , % 2 % 1 : % endmacro

          Это тогда используется для определения примитивов. Код по сути проваливается в

          defcode :

             defcode PLUS  ,   «+»   поп   топор  Добавлять   bx  ,   топор   defcode МИНУС  ,   «-»   поп   топор   sub   топор  ,   bx   xchg   bx  ,   топор   defcode PEEK  ,   «@»  ;  ...   

          Тем не мение,

          DOCOL , ВЫХОД а также LIT также используют механизм сжатия для своих СЛЕДУЮЩИЙ с. Поскольку поле ссылки все еще записано, это по существу создает фиктивные словарные статьи. К счастью, первый код операции ВЫХОД и имеет F_HIDDEN бит установлен, так что это не проблема:

          <2> Сжатый Начать: DOCOL: xchg топор , si stosw pop си ; захватить указатель, нажатый `call` Compression_sentinel LIT: толкать bx lodsw xchg bx , топор Compression_sentinel EXIT: дек ди dec ди mov si , [di] defcode PLUS , «+» ; ... Переменные?

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

           
           быть363412   mov   si  ,   0x 2048   8b 1401557309118103560   mov   si  , [0x1234]    

          Вот почему Miniforth хранит большинство своих переменных в непосредственных полях инструкций. Конечно, это означает, что адрес этих переменных будет меняться при каждом редактировании кода, что проблематично, поскольку мы захотим получить доступ к этим переменным в коде FORTH. Типичный способ раскрытия переменной - создать слово, которое подталкивает ее адрес. Однако это слишком дорого с нашими ограничениями. Я остановился на том, чтобы помещать адреса в стек при запуске. Это можно сделать, используя только 2 байта для каждого адреса, просто определив исходное содержимое стека как данные:

          org 0x7c 08 jmp 0 : стартовый стек: dw ЗДЕСЬ dw БАЗА dw ГОСУДАРСТВЕННЫЙ dw ПОСЛЕДНИЙ старт: ; ... mov зр , куча

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

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

          Код инициализации

          Первое, что делается после загрузки, - это настройка

          сегментные регистры и стек. Флаг направления также сбрасывается, поэтому строковые инструкции работают в правильном направлении.

          jmp 0 :Начало ; ... Начало: толкать cs толкать cs толкать cs поп ds поп es поп SS mov sp , куча cld

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

          bootBASIC - позволяет инициализировать регистр общего назначения нулем:

          38 c0 xor топор , топор ; через AX - 8 байтов 8ed8 mov ds , топор 8ec0 mov es , топор 8ed0 mov SS , топор 0e толкать cs ; через стек - 6 байтов 0e толкать cs 0e толкать cs 1f поп ds 10 поп es 24 поп SS

          Во-вторых, можно подумать, что пока стек перенаправляется возникает небольшое окно состояния гонки - если прерывание произошло между pop ss а также mov sp , может возникнуть хаос, если предыдущее значение ИП оказался в неудачном месте в памяти. Конечно, я мог бы просто скрестить пальцы и надеяться, что этого не произойдет, если 2 байта, необходимые для обертывания этого в cli / sti пара было многовато. Однако оказывается, что в этом компромиссе нет необходимости из-за неясного угла x архитектура. Чтобы процитировать Том 2B из Икс400 Руководство разработчика программного обеспечения :

          Загрузка регистра SS инструкцией POP подавляет или запрещает некоторые исключения отладки и запрещает прерывания на следующая граница инструкции. (Запрещение заканчивается после доставки исключения или выполнения следующей инструкции.) Такое поведение позволяет загрузить указатель стека в регистр ESP со следующей инструкцией (POP ESP) до того, как событие может быть доставлено.

          После сегменты, стек и флаг направления установлены, декомпрессор запущен. Важно отметить, что он не использует регистр DL, который содержит номер диска BIOS, с которого мы были загружены. Затем он вставляется в реализацию

          load (который находится в сжатый сегмент) и помещается в стек для последующего использования кодом пользователя:

           

          mov [DRIVE_NUMBER], dl толкать dx ; для кода FORTH

          Внешний интерпретатор

          На этом этапе мы достигаем внешний интерпретатор - часть системы FORTH, обрабатывающая ввод пользователя. Имя " внешний интерпретатор "отличает его от внутренний интерпретатор, который является компонентом, координирующим выполнение в пределах определенного слова, и состоит из СЛЕДУЮЩИЙ, ДОКОЛ , ВЫХОД, а также

          LIT .

          Обычно FORTH представляет строительные блоки своего внешнего интерпретатора как слова в словарь, например

        1. ПОПОЛНЕНИЕ (прочитать строку ввода из текущего исполняемого источника),
        2. СЛОВО (разобрать слово из входного потока),
              НАЙТИ (найдите слово в словаре),


            1. > ЧИСЛО (преобразовать строка к номеру).

Leave a comment

Your email address will not be published. Required fields are marked *