17.06.2021 09:07
forthuse 2 2200 Источник
Связь СЛОВ через словарик
Связь СЛОВ через словарик

Оригинал текста Июнь 10, 2021 - 38 минут чтения

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

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

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

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

6a00    push word 0
07      pop es
fd      std
bf1e7c  mov di, buffer+16 ; Adjust to taste. Beware of fenceposting.
        input_loop:
b400    mov ah, 0
cd16    int 0x16
aa      stosb
ebf9    jmp short input_loop
        buffer:

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

Оскар Толедо написал много интересных программ размером с сектор. Среди них много игр, таких как DooM-подобная игра или шахматный ИИ, а также базовый интерпретатор BASIC, но самой, пожалуй, актуальной для нашего случая является bootOS:

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

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

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

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

Вводная экскурсия в FORTH

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

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

?1 2 3 + .s  <enter>

<2> 1 5 ok

Примечание: ok - готовность системы к приёму слов языка

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

 : double dup + ; <enter>

ok  3 double  .  <enter>

6 ок

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

42 dup .s <enter>

<2> 42 42 ok

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

Чтобы описать влияние слова на состояние стека, мы используем следующую нотацию:

dup ( a -- a a ) 

swap ( a b -- b a )

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

Шитый код

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

DOUBLE:
    call DUP
    call PLUS
    ret

Однако это связывает аппаратный стек x86 для стека возврата, заставляя нас вручную обрабатывать отдельный стек для фактического стека пользовательского уровня (известного как стек параметров). Поскольку доступ к стеку параметров встречается гораздо чаще, мы хотели бы использовать для этого инструкции push и pop, а вместо них можно применить механизм, аналогичный call. Во-первых, давайте просто сохраним список указателей на слова:

DOUBLE:
    dw DUP
    dw PLUS

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

DUP:
    pop ax
    push ax
    push ax

    lodsw
    jmp ax

PLUS:
    pop ax
    pop bx 
    add ax, bx
    push ax

    lodsw
    jmp ax

Этот общий код можно абстрагировать в макрос, который традиционно называется NEXT:

%macro NEXT 0
    lodsw
    jmp ax
%endmacro

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

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

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

DOUBLE:
    call DOCOL
    dw DUP
    dw PLUS
    dw EXIT

DOCOL:            ; сокращение от "do colon word".
    xchg ax, si ; используется здесь как  mov ax, si ,

              ;   но меняет местами.
                ; ax - только один байт, а  mov  - два байта.
    stosw
    pop si ; захватить указатель, вытолкнутый  call .
    NEXT

EXIT:
    dec di
    dec di
    mov si, [di]
    NEXT

Это практически та же стратегия выполнения, что и в Miniforth, с одним простым, но существенным улучшением - значение на вершине стека хранится в регистре BX. Это позволяет пропустить push и pop во многих примитивах:

PLUS:
    pop ax
    add bx, ax
    NEXT

DROP:
    pop bx
    NEXT

DUP:
      push  bx 
      NEXT

Однако один случай все еще остается нерешенным. Что произойдет, если слово содержит число, например : DOUBLE 2 \ ;? С этим справляется LIT, который извлекает литерал, следующий за ним, из потока указателей:

DOUBLE:
      call DOCOL
      dw LIT, 2
      dw MULT
      dw EXIT

LIT:
      push  bx 
      lodsw
      xchg  bx ,  ax 
      NEXT

Словарь

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

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

F_IMMEDIATE equ 0x80
F_HIDDEN    equ 0x40
F_LENMASK   equ 0x1f

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

Компрессия

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

?

ad      lodsw
ffe0    jmp  ax

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

Я выбрал схему сжатия, в которой каждый байт 0xff заменяется на NEXT, за которым следует поле ссылки, которое вычисляется на основе предыдущего появления байта 0xff. Эта стратегия сэкономила 19 байт, когда я ее внедрил.4

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

Чтобы создать ссылку, мы копируем значение LATEST на выход декомпрессора и обновляем LATEST, чтобы оно указывало на слово, которое мы только что написали. Это может быть сделано очень компактной последовательностью инструкций, но все равно занимает достаточно байт, чтобы стоило оформить это в виде подпрограммы. Она также используется в реализации :, которая создает словарные статьи во время выполнения.

; Создает ссылку словарного связного списка в DI.

MakeLink:
      mov  ax ,  di 
      xchg [LATEST],  ax    ; AX теперь указывает на старую запись, 

                  ; а LATEST и DI указывают на новую.

      stosw
      ret

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

     jmp short .after
.write:
      stosb
.after:

пишим

3c      db 0x3c ; пропустить stosb ниже, сравнив его опкод с AL 
      .write:
aa      stosb

Таким образом, если какой-то другой код переходит к .write, выполняется stosb, но этот кодовый путь просто выполняет cmp al, 0xaa. Сначала я не подумал об инструкции cmp al, и вместо нее использовал mov в отбрасываемый регистр. Это привело кэффектному отказуиз-за моей неспособности выбрать регистр, который можно безопасно перезаписать.

Илья Курдюков затем продемонстрировал , что тот же самый байткоунт может быть достигнут без подобной "магии". Аналогичная модификация позволила мне устранить и другое проявление этого трюка. Суть в том, что вместо того, чтобы пытаться пропустить stosb, мы выполняем его безоговорочно перед ветвлением кодовых путей, а затем, по сути, отменяем его с помощью dec di, если это необходимо:

SPECIAL_BYTE equ 0xff

      mov  si , CompressedData
      mov  di , CompressedBegin
      mov  cx , COMPRESSED_SIZE
.decompress:
      lodsb
      stosb
      cmp  al , SPECIAL_BYTE
      jnz short .not_special
      dec  di 
      mov  ax , 0xffad ; lodsw / jmp ax
      stosw
      mov  al , 0xe0
      stosb
      call MakeLink
.not_special:
      loop .decompress

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

boot.s:137: error: program origin redefined

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

%macro compression_sentinel 0
      db SPECIAL_BYTE
      dd 0xdeadbeef
%endmacro

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

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

\1. Несжатый код начинается с 7C00 - инициализация, декомпрессия и внешний интерпретатор.

\2. Сжатые данные немедленно следуют за ним, заполняя бутсектор вплоть до момента перед 7E00.

\3. Сразу после этого выделяется буфер декомпрессии, в который yasm выводит содержимое цели.

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

%assign savings 0

%macro compression_sentinel 0
%assign savings savings+4
      db SPECIAL_BYTE
      dd 0xdeadbeef
%endmacro

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

CompressedData:
      times COMPRESSED_SIZE db 0xcc

CompressedBegin:
; ...
CompressedEnd:

COMPRESSED_SIZE equ CompressedEnd - CompressedBegin - savings

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

SPECIAL_BYTE =  b'\xff'
SENTINEL = SPECIAL_BYTE +  b '\xef\xbe\xad\xde'

with open('raw.bin', 'rb') as f:
      data = f.read()

output_offset = data.index( b '\xcc' \  20)
chunks = data[output_offset:].lstrip( b '\xcc').split(SENTINEL)

assert SPECIAL_BYTE not in chunks[0]
compressed =  bytearray (chunks[0])

for chunk in chunks[1:]:
      assert SPECIAL_BYTE not in chunk
      compressed.extend(SPECIAL_BYTE)
      compressed.extend(chunk)

\# Убедитесь, что для сжатых данных выделено именно то место, которое нужно.

\# для сжатых данных.

assert  b '\xcc' \  len(compressed) in data
assert  b '\xcc' \  (len(compressed) + 1) not in data

output = data[:output_offset] + compressed

print(len(output), 'bytes used')
output +=  b '\x00' \  (510 - len(output))
output +=  b '\x55\xaa'

with open('boot.bin', 'wb') as f:
      f.write(output)

Этот же сценарий также генерирует расширенный образ диска, который содержит некоторый код для тестирования в блоке 1:

output +=  b '\x00' \  512
output += open('test.fth', 'rb').read().replace( b '\n',  b ' ')
output +=  b ' ' \  (2048 - len(output))

with open('test.img', 'wb') as f:
      f.write(output)

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

; defcode PLUS, "+"
; defcode SEMI, ";", F_IMMEDIATE
%macro defcode 2-3 0
      compression_sentinel
%strlen namelength %2
      db %3 | namelength, %2
%1:
%endmacro

Затем это используется для определения примитивов. Код, по сути, переходит в defcode:

defcode PLUS, "+"
      pop  ax 
      add  bx ,  ax 

defcode MINUS, "-"
      pop  ax 
      sub  ax ,  bx 
      xchg  bx ,  ax 

defcode PEEK, "@"
      ; ...

Однако DOCOL, EXIT и LIT также используют механизм сжатия для своих NEXT. Поскольку поле ссылки все еще записывается, это создает фиктивные словарные статьи. К счастью, первый опкод EXIT и LIT имеет установленный бит F_HIDDEN, так что это не проблема:

CompressedBegin:

DOCOL:
      xchg  ax ,  si 
      stosw
      pop  si  ; grab the pointer pushed by  call 
      compression_sentinel

LIT:
      push  bx 
      lodsw
      xchg  bx ,  ax 
      compression_sentinel

EXIT:
      dec  di 
      dec  di 
      mov  si , [ di ]

defcode PLUS, "+"
      ; ...

Переменные?

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

be3412    mov  si , 0x1234
8b363412  mov  si , [0x1234]

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

      org 0x7c00

      jmp 0:start
stack:
      dw HERE
      dw BASE
      dw STATE
      dw LATEST
start:
      ; ...
      mov  sp , stack

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

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

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

      jmp 0:start
      ; ...
start:
      push  cs 
      push  cs 
      push  cs 
      pop  ds 
      pop  es 
      pop  ss 
      mov  sp , stack
      cld

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

?

31c0    xor  ax ,  ax   ; through AX - 8 bytes
8ed8    mov  ds ,  ax 
8ec0    mov  es ,  ax 
8ed0    mov  ss ,  ax 

0e      push  cs      ; through the stack - 6 bytes
0e      push  cs 
0e      push  cs 
1f      pop  ds 
07      pop  es 
17      pop  ss

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

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

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

      mov [DRIVE_NUMBER],  dl 
      push  dx  ; for FORTH code

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

На этом этапе мы достигаем внешнего интерпретатора - части системы FORTH, которая обрабатывает пользовательский ввод. Название "внешний интерпретатор" отличает его от внутреннего интерпретатора, который является компонентом, координирующим выполнение в пределах определенного слова, и состоит из NEXT, DOCOL, EXIT и LIT.

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

  • REFILL (считывание строки ввода из текущего выполняющегося источника),

    • WORD (разбор слова из входного потока),

    • FIND (искать слово в словаре),

    • NUMBER (преобразование строки в число).

В Miniforth этой практике вообще не уделяется никакого внимания. Заголовки словарей стоят байты, как и общение только через стек. Фактически, WORD и >NUMBER объединяются в одну процедуру, которая выполняет работу обеих. Таким образом, цикл может быть общим, что экономит байты.

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

Ввод с клавиатуры

После завершения инициализации код переходит к ReadLine, процедуре для чтения строки ввода с клавиатуры. Мы также вернемся сюда позже, когда текущая строка ввода будет исчерпана. Буфер ввода находится по адресу 0x500, сразу послеBDA. Хотя идиоматический формат строк для FORTH использует отдельное поле длины, этот буфер NULL-терминирован, так как это легче обрабатывать при разборе. Указатель на неразобранный фрагмент ввода хранится в InputPtr, которая является единственной переменной, не использующей технику самомодификации, так как ее не нужно явно инициализировать и она естественным образом записывается до чтения.

InputBuf equ 0x500 InputPtr equ 0xa02 ; dw

ReadLine:
      mov  di , InputBuf
      mov [InputPtr],  di 
.loop:
      mov  ah , 0
      int 0x16
      cmp  al , 0x0d
      je short .enter
      stosb
      cmp  al , 0x08
      jne short .write
      dec  di 
      cmp  di , InputBuf ; underflow check
      je short .loop
      dec  di 
.write:
      call PutChar
      jmp short .loop
.enter:
      call PutChar
      mov  al , 0x0a
      int 0x10
      xchg  ax ,  bx  ; write the null terminator by using the BX = 0 from PutChar
      stosb
InterpreterLoop:
      call ParseWord ; returns length in CX. Zero implies no more input.
      jcxz short ReadLine

Прерывание BIOS для получения символа с клавиатуры не печатает клавишу и мы должны сделать это сами. Это делается с помощью функции "TELETYPE OUTPUT", которая уже обрабатывает специальные символы, такие как backspace или newline.

?

PutChar:
      xor  bx ,  bx 
      mov  ah , 0x0e
      int 0x10
      ret

У этой функции есть свои недостатки. Например, необходимы "грязные" символы окончания строки CRLF (CR для перемещения курсора в начало строки и LF для перемещения на следующую строку). Кроме того, символ backspace только перемещает курсор на один символ назад, но не стирает его. Чтобы получить поведение, которого мы ожидаем, необходимо напечатать \b \b (справедливости ради, это также происходит на современных терминалах). Я решил это пропустить.

Наконец, в "Списке прерываний" Ральфа Браунаупоминается, что некоторые BIOS сбрасывают BP, когда печатаемый символ вызывает прокрутку экрана. Это нас не касается, так как мы вообще не используем этот регистр.

Парсинг

После того как мы прочитали строку, нам нужно разобрать ее на слова. Это делается по требованию и каждое слово выполняется (или компилируется, в зависимости от состояния), как только оно разобрано. Помимо цикла интерпретатора, ParseWord также вызывается реализацией : (для получения имени определяемого слова).

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

Для начала мы пропускаем все пробельные символы во входном буфере:

; returns
; DX = pointer to string
; CX = string length
; BX = numeric value
; clobbers SI and BP
ParseWord:
      mov  si , [InputPtr]
      ; repe scasb вероятно, сохранит некоторые байты здесь, если бы реестры были разработаны - SCASB  ; использует DI вместо SI :( - scasb
      ; uses DI instead of SI :(
.skiploop:
      mov  dx ,  si  ; Если мы выйдем на петлю в этой итерации, DX укажет первую букву слова
      lodsb
      cmp  al , " "
      je short .skiploop

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

В этот момент регистр AL загружен первым символом слова. Таким образом, наш следующий цикл должен будет выполнить lodsb в своем конце.

      xor  cx ,  cx 
      xor  bx ,  bx 
.takeloop:
      and  al , ~0x20
      jz short Return ; jump to a borrowed  ret  from some other routine

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

Если мы не обнаружили конец слова, мы увеличиваем счетчик длины и преобразуем цифру в ее числовое значение:

      inc  cx 
      sub  al , "0" &~0x20
      cmp  al , 9
      jbe .digit_ok
      sub  al , "A" - ("0" &~0x20) - 10
.digit_ok
      cbw

cbw - это малоизвестная инструкция, которая преобразует знаковое число из байта в слово, но для нас это просто более короткое mov ah, 0. Возможно, аналогичным образом мы используем знаковое умножение imul, потому что у него больше возможностей для использования регистров, чем у беззнакового mul. Используемая здесь форма позволяет умножать на непосредственное значение и не перезаписывать в DX верхнюю половину произведения.7

Эта конкретная инструкция должна быть закодирована вручную, чтобы ширина литерала составляла 2 байта.8

      ; imul bx, bx, <BASE> но yasm настаивает на кодировании непосредственного в один байт... 
      db 0x69, 0xdb
BASE equ $
      dw 16
      add  bx ,  ax  ; add the new digit

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

   ?   mov [InputPtr],  si 
      lodsb
      jmp short .takeloop

Поиск по словарю

После того как слово разобрано, мы пытаемся найти его в словаре. Для каждой записи нам нужно сравнить длину имени, а если она совпадает, то и само имя. Включая F_HIDDEN в маску, мы автоматически обрабатываем и скрытые записи. То, как мы сравниваем длину, может выглядеть немного странно. Цель состоит в том, чтобы сохранить бит F_IMMEDIATE в AL, чтобы нам не пришлось держать рядом указатель на заголовок этого слова. Это одна из умных оптимизаций Ильи Курдюкова.

?

    InterpreterLoop:
          call ParseWord
          jcxz short ReadLine
    
    ; Пытаемся найти слово в словаре..
    ; SI = указатель словаря
    ; DX = указатель строки
    ; CX = длина строки
    ; Следим за сохранением BX, в котором хранится числовое значение
    LATEST equ $+1
          mov  si , 0
    .find:
          lodsw
          push  ax  ; сохранить указатель на следующую запись
          lodsb
          xor  al ,  cl  ; если длина совпадает, то AL содержит только флаги
          test  al , F_HIDDEN | F_LENMASK
          jnz short .next
    
          mov  di ,  dx 
          push  cx 
          repe cmpsb
          pop  cx 
          je short .found
    .next:
          pop  si 
          or  si ,  si 
          jnz short .find
    
          ; Если мы дойдем до этой точки, то это будет число.
          ; ...

.found:
      pop  bx  ; отбрасываем указатель на следующую запись
      ; Когда мы дойдем до этого места, SI указывает на код слова, а AL содержит 

; флаг F_IMMEDIATE

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

Должны ли мы его выполнить?

Система может находиться в двух возможных состояниях:

  • интерпретация - все слова должны быть выполнены

  • компиляция - непосредственные слова должны быть выполнены

Другими словами, слово должно быть выполнено, если оно немедленное, или мы его интерпретируем. Мы храним этот флаг в поле immediate инструкции or, так как при компиляции он будет установлен в 0:

?

      ; Когда мы сюда попадаем, SI указывает на код слова, а AL содержит 

; флаг F_IMMEDIATE STATE
STATE equ $+1
      or  al , 1
      xchg  ax ,  si  ;  оба кодовых пути должны иметь указатель в AX
      jz short .compile

      ; Выполняем слово
      ; ...

Наиболее важными словами, которые должны изменить состояние, являются : и ;, но они просто переходят в [ и ] слова, которые позволяют временно вернуться в интерпретируемый режим при компиляции слова. Типичный случай использования - вычисление значения постоянного выражения:

 : third-foo [ foos 3 cells + ] literal @ ;

Поскольку два значения STATE отличаются только на 1, мы можем переключаться между ними с помощью inc и dec. Это имеет тот недостаток, что они больше не являются идемпотентными, но это не должно иметь значения для хорошо написанного кода:

defcode LBRACK, "[", F_IMMEDIATE
      inc byte[STATE]

defcode RBRACK, "]"
      dec byte[STATE]

Выполнение слова

Если мы решили выполнить слово, мы извлекаем BX и DI, и настраиваем SI так, чтобы NEXT перешел обратно к .executed:

; Выполнение слова RetSP ?

RetSP equ $+1
      mov  di , RS0
      pop  bx 
      mov  si , .return
      jmp  ax 
.return:
      dw .executed
.executed:
      mov [RetSP],  di 
      push  bx 
      jmp short InterpreterLoop

Обработка чисел

Для чисел нет флага F_IMMEDIATE, поэтому для принятия решения нам нужно просто проверить состояние. Это простое сравнение, но если мы будем достаточно умны, здесь можно сэкономить байт. Давайте снова посмотрим на код, который выполняет поиск в словаре. Какое значение будет иметь AH, когда мы дойдем до регистра чисел?

.find:
      lodsw
      push  ax  ;  сохранить указатель на следующую запись
      lodsb
      xor  al ,  cl  ; если длина совпадает, то AL содержит только флаги
      test  al , F_HIDDEN | F_LENMASK
      jnz short .next

      mov  di ,  dx 
      push  cx 
      repe cmpsb
      pop  cx 
      je short .found
.next:
      pop  si 
      or  si ,  si 
      jnz short .find

      ; AH = ?

Видите ли вы это? В этот момент AH равен нулю, так как содержит старшую половину указателя на следующее слово, которое, как мы знаем, является NULL, поскольку мы только что добрались до конца списка. Это позволяет нам проверить значение STATE, не загружая его в регистр или какие-либо непосредственные байты:

      ; Это число. Вставьте его значение - мы выкинем его позже, если окажется, что нужно скомпилировать 

; его вместо этого. 

      push  bx 
      cmp byte[STATE],  ah 
      jnz short InterpreterLoop

      ; Иначе скомпилируйте литерал. ; ...

Компиляция вещей

Указатель точки процесса компиляции называется HERE. Он начинается сразу после распакованных данных. Функция, которая выписывает слово в эту область, называется COMMA, так как слово FORTH, которое это делает, - ,.

COMMA:
HERE equ $+1
      mov [CompressedEnd],  ax 
      add word[HERE], 2
      ret

Он используется в прямом смысле для составления как чисел, так и слов. Мы можем разделить хвост, хотя a составлении слова он будет перескакивать на середину составления числа:

      ; Иначе, компилируем литерал. 
      mov  ax , LIT
      call COMMA
      pop  ax 
.compile:
      call COMMA
      jmp short InterpreterLoop

Последним кусочком головоломки являются : и ;. Давайте сначала рассмотрим :. Поскольку ParseWord использует BX и SI, нам нужно сохранить эти регистры. Более того, поскольку мы пишем множество частей заголовка словаря, мы загрузим HERE в DI, чтобы упростить работу. Это большое количество регистров, которые нам нужно переместить. Однако на самом деле нам не нужно изменять ни один регистр, поэтому мы можем просто сохранить все регистры с помощью pusha.

defcode COLON, ":"
      pusha
      mov  di , [HERE]
      call MakeLink    ; link field
      call ParseWord
      mov  ax ,  cx 
      stosb            ; length field
      mov  si ,  dx 
      rep movsb        ; name field

      mov  al , 0xe8     ; call
      stosb



   ; поле длины mov si, dx rep movsb ; поле имени mov al, 0xe8 

; вызов stosb ; Смещение определяется как (цель вызова) - (ip после инструкции вызова) 

; Получается DOCOL - (di + 2) = DOCOL - 2 - di 

?

     mov  ax , DOCOL - 2
      sub  ax ,  di 
      stosw
      mov [HERE],  di 
      popa
      jmp short RBRACK ; enter compilation mode
   ; войти в режим компиляции

; гораздо короче. Нам просто нужно скомпилировать EXIT и вернуться в режим интерпретации:

defcode SEMI, ";", F_IMMEDIATE
      mov  ax , EXIT
      call COMMA
      jmp short LBRACK

То, как эти слова переходят к другому слову в конце, весьма удобно. Помните, как NEXT записываются как часть кода следующего слова? Одно из слов должно быть последним в памяти, и тогда после него не будет никакого "следующего слова". : и ; - идеальные кандидаты для этого, поскольку им вообще не нужен NEXT.

Загрузка кода с диска

Поскольку мы не хотим вводить дисковые подпрограммы при каждой загрузке, нам нужно предусмотреть способ запуска исходного кода, загруженного с диска. Файловая система была бы отдельным зверем, но в традициях FORTH есть минималистичное решение: диск просто делится на блоки по 1 КБ, в которых хранится исходный код, отформатированный как 16 строк по 64 символа. Затем load ( blknum -- ) выполнит блок с указанным номером.

Мы размещаем блок 0 в LBA 0 и 1, блок 1 в LBA 2 и 3 и так далее. Это означает, что блок 0 частично занят MBR, а LBA 1 используется впустую, но меня это не особенно беспокоит.

Поскольку оригинальная служба BIOS по адресу int 0x13 / ah = 0x02 требует адресации CHS, я решил использовать вариант расширения EDD (ah = 0x42). Это означает, что дискеты не поддерживаются, но я все равно не планировал их использовать.

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

      db 0x10 ; размер пакета
      db 0    ; зарезервировано
      dw sector_count
      dw buffer_offset, buffer_segment
      dq LBA

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

>  
>  
> DiskPacket:       db 0x10, 0 .count:       dw 2 .buffer:

; остальное заполняется во время выполнения, перезаписывая сжатые данные,

; которые больше не нужны

CompressedData: times COMPRESSED_SIZE db 0xcc

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

c706020a0006    mov word[InputPtr], BlockBuf

Однако мы можем получить эту переменную в AX без дополнительных затрат:

?b80006          mov  ax , BlockBuf
a3020a          mov [InputPtr],  ax

Таким образом, мы можем записать эти два байта дискового пакета с помощью всего 1 байта кода:

defcode LOAD, "load"
      pusha
      mov  di , DiskPacket.buffer
      mov  ax , BlockBuf
      mov word[InputPtr],  ax 
      stosw

Далее нам нужно записать сегмент (0000) и LBA (который заканчивается шестью байтами 00). Мне нравится думать о соответствующих инструкциях следующим образом:

31c0    xor  ax ,  ax     ; LBA zeroes
ab      stosw         ; segment
d1e3    shl  bx , 1     ; LBA data
93      xchg  ax ,  bx    ; LBA data
ab      stosw         ; LBA data
93      xchg  ax ,  bx    ; segment
ab      stosw         ; LBA zeroes
ab      stosw         ; LBA zeroes
ab      stosw         ; LBA zeroes

То есть, мы записываем шесть нулей LBA за 5 байт кода. Запись сегмента потребовала только перемещения xor ax, ax ранее, и дополнительных stosw и xchg ax, bx. Таким образом, он занимает нейтральные 2 байта (но нам нужно выписать его в коде, чтобы указатель был правильным для остальной части пакета). Наконец, конечно, у нас есть фактические данные LBA, которые меняются.

Пока AX равен нулю, воспользуемся случаем и поставим нулевой терминатор после буфера:

      mov [BlockBuf.end],  al

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

DRIVE_NUMBER equ $+1
      mov  dl , 0
      mov  ah , 0x42
      mov  si , DiskPacket
      int 0x13
      jc short $
      popa
      pop  bx

Числа для печати

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

defcode UDOT, "u."
    xchg  ax ,  bx 
    push " " - "0"
.split:
      xor  dx ,  dx 
      div word[BASE]
      push  dx 
      or  ax ,  ax 
      jnz .split
.print:
      pop  ax 
      add  al , "0"
      cmp  al , "9"
      jbe .got_digit
      add  al , "A" - "0" - 10
.got_digit:
      call PutChar
      cmp  al , " "
      jne short .print
      pop  bx

s: Поместить в строку

s: - это функция, которая, как мне кажется, имеет уникальное значение для бутстраппинга. Это слово принимает адрес буфера и копирует туда остаток текущей строки ввода. Без этого значительный объем кода пришлось бы набирать дважды: сначала для того, чтобы запустить его и загрузить редактор дисковых блоков, а затем еще раз, чтобы сохранить его на диске.

Реализация представляет собой простой цикл, но установка вокруг него заслуживает внимания и мы хотим загрузить входной указатель в SI, но нам также нужно сохранить SI, чтобы мы могли правильно вернуться. Используя xchg, мы можем сохранить его в [InputPtr] на время копирования без дополнительных затрат:

;; Копирует остаток строки в buf. 

   defcode LINE, "s:" ; ( buf -- buf+len )
      xchg  si , [InputPtr]
.copy:
      lodsb
      mov [ bx ],  al 
      inc  bx 
      or  al ,  al 
      jnz short .copy
.done:
      dec  bx 
      dec  si 
      xchg  si , [InputPtr]

Указатель назначения хранится в BX. Хотя запись в DI займет всего один стосб, получение указателя в DI и обратно перевешивает это преимущество. В конце мы оставляем в стеке указатель на нулевой терминатор. Таким образом, вы можете продолжить строку, просто используя s: в следующей строке. Поскольку мы не пропускаем пробельные символы, это даже гарантирует правильную расстановку символов.

Другие примитивы

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

Такая базовая арифметика, как +, незаменима. Я определяю и +, и -, хотя, если бы я хотел вписать что-то более важное, я мог бы оставить только - и позже определить ?: negate 0 swap - ; и : + negate - ;.

Как и в любом низкоуровневом языке программирования, нам нужен способ подглядывать и пихать значения в память. Реализация ! особенно хороша, поскольку мы можем просто заглянуть прямо в [bx]:

defcode PEEK, "@" ; ( addr -- val )
    mov bx, [bx]

defcode POKE, "!" ; ( val addr -- )
    pop word [bx]
    pop bx

Существуют также варианты, которые читают и записывают только один байт:

?defcode CPEEK, "c@" ; ( addr -- ch )
      movzx  bx , byte[ bx ]

defcode CPOKE, "c!" ; ( ch addr -- )
      pop  ax 
      mov [bx],  al 
      pop  bx

Нам определенно нужны слова для работы со стеком. dup и drop имеют очень простые реализации, а swap определенно слишком полезен, чтобы его пропустить.

defcode DUP, "dup" ; ( a -- a a )
      push  bx 

defcode DROP, "drop" ; ( a -- )
      pop  bx 

defcode SWAP, "swap" ; ( a b -- b a )
      pop  ax 
      push  bx 
      xchg  ax ,  bx

Я решил также включить >r и r>, которые позволяют использовать стек возвратов в качестве второго стека для значений (но, очевидно, только в пределах одного слова). Это довольно мощный инструмент. Фактически, в сочетании с dup, drop и swap они позволяют реализовать любое слово для манипуляции стеком, которое вы только можете себе представить.9

defcode TO_R, ">r"
      xchg  ax ,  bx 
      stosw
      pop  bx 

defcode FROM_R, "r>"
      dec  di 
      dec  di 
      push  bx 
      mov  bx , [ di ]

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

defcode EMIT, "emit"
      xchg  bx ,  ax 
      call PutChar
      pop  bx

Заключение

Я доволен тем, что получилось. Для системы, ограниченной загрузочным сектором, я могу назвать ее вполне законченной по функциям - я не могу придумать ничего, что могло бы значительно упростить бутстрап, занимая при этом достаточно мало байт, чтобы это казалось удаленно досягаемым для кодового гольфа. Это во многом благодаря помощи Ильи Курдюкова - без него я бы не смог вписать s:.

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

Я буду документировать свое путешествие по созданию Miniforth в будущих записях этого блога. Если это похоже на вашу чашку чая (а если вы дочитали до этого места, то, вероятно, так оно и есть), подпишитесь на RSS-канал или следите за мной в Twitter, чтобы получать уведомления о новых статьях.

1

У теоретика графов было бы много сильных слов, чтобы описать это, а не только цикл.

2

И даже если бы это было не так, есть много, многопримеров кода x86, написанного с использованием печатаемого подмножества ASCII. Я даже сам однажды сделал этонесколько лет назад.

3 Если вы, дорогой читатель, считаете это неудовлетворительным, я хотел бы пригласить вас в собственное путешествие по бутстрапингу. Это действительно очень весело!

4

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

5

Хотя в этом отрывке справки говорится только о pop ss, аналогичное утверждение содержится в документации по mov.

6

Похоже, это одна из многих ошибок в SDM и использование pop esp для этого не работает. Раздел 6.8.3 ("Маскировка исключений и прерываний при переключении стека") в томе 3A разъясняет, что все одноинструкционные способы загрузки SP работают для этого. Я бы процитировал этот раздел, если бы не тот факт, что, хотя в нем перечислены многие другие типы событий, которые подавляются, в нем не упоминаются реальные прерывания как один из них. Однако в этом разделе упоминаются некоторые интересные крайние случаи. Например, если вы похожи на меня, вам может быть интересно, что произойдет, если много инструкций подряд записываются в SS. Ответ заключается в том, что только первая из них гарантированно подавляет прерывания.

7

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

8

Вы можете спросить, почему бы просто не объявить, что BASE - это переменная размером в байт? Ответ заключается в том, что u., которое является словом, печатающим число, использует div word[BASE], так что результат все еще 16-битный.

9

Сюда не входят слова типа PICK, для них нужны циклы. Однако все, что можно определить как ( <список имен> -- <список имен>), является честной игрой. Доказательство этого факта мы оставляем на усмотрение читателя. 10

10

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

github.com/NieDzejkob