Нет ветвлений? Нет проблем — Форт-ассемблер

Перевод
Оригинальный текст:
22 июня 2021 г. · 36 минут чтения

Эта статья является частью серии «Начальная загрузка» , в которой я начинаю с 512-байтного начального числа и пытаюсь загрузить реальную систему.

Предыдущий пост:
Разместить FORTH в 512 байтах
Следующий пост:
Ветвление: сборка не требуется

Набор слов, доступных после загрузки Miniforth, довольно скуден. Один читатель даже заявил , что, поскольку ветвей нет, он не является полным по Тьюрингу и, следовательно, не достоин называться Фортом! Сегодня тот день, когда мы докажем, что они ошибались.

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

+ - ! @ c! c@ dup drop swap emit u. >r r> [ ] : ; load s:

Большинство из них будут знакомы программистам на Forth, но load и s: могут нуждаться в некоторых комментариях. load ( u -- )является стандартным словом из необязательного набора слов Block — оно загружает блок uи выполняет его как исходный код Forth. 1 Это слово имеет решающее значение для практического использования такого маленького Форта, поскольку, как только вы загрузитесь достаточно далеко, вы можете сохранить свой код на диск, а после перезагрузки возобновить работу с помощью всего лишь 1 load.

Однако, чтобы добраться до этой точки, вам нужно написать довольно много кода. Чтобы сделать исходный код доступным в памяти, как только вы сможете его сохранить, я включил s: ( buf -- buf+len ), что, по сути, представляет собой ввод строки — остальная часть входного буфера копируется в buf. Адрес конца буфера остается в стеке, чтобы его можно было использовать s:на следующей строке, и результат будет конкатенирован (соеденён).

В этом посте мы начнем с состояния, в котором загружается Miniforth, и:

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

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

s:- рабочий процесс

Я решил хранить свой исходный код по адресу 1000, в пространстве между стеками параметра и возврата. Первое, что нам понадобится, — это способ запуска кода, который мы туда поместили. Определено InputPtr, чтобы быть по адресу A02, поэтому давайте определим run, который подставляет значение по нашему выбору по этому адресу:

: >in A02 ;  : run >in ! ;

>in— это традиционное имя для указателя входного буфера, поэтому я выбрал его. 2 Чтобы убедиться, что он также доступен при последующих загрузках, я сохраняю этот фрагмент кода в памяти:

1000 s: : >in A02 ;  : run >in ! ;

Это хорошее время для просмотра текущего указателя на исходный буфер с помощью dup u.. Если вы не добавили некоторое пространство для записи, ответ будет 101A, и это адрес, на который мы хотим перейти runпозже, чтобы избежать переопределения >inи run. 3

Написав достаточно кода, чтобы протестировать его, я печатал текущий адрес буфера с помощью u., а затем runновый код из предыдущего напечатанного адреса буфера. Во-первых, важно, чтобы адрес буфера не оставался наверху стека, так как Miniforth загружается с адресами встроенных системных переменных в стеке , и мы хотим получить к ним доступ.

Системные переменные

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

latest st base dp disk#

Обычно мы просто делаем constant disk#, constant hereи так далее. Однако у нас нет constant, или какого-либо способа его определения (пока). literalближе, но нам нужно по крайней мере hereреализовать его и latestпометить как немедленное. Мы можем обойти насущную проблему с помощью [и ], что предполагает следующий порядок действий:

swap : dp 0 [ dup @ 2 - ! ] ;

Давайте рассмотрим это шаг за шагом, так как это работает довольно сложно. dpозначает указатель данных . Это переменная back here, указатель компиляции, значение которого hereпросто определяется как

: here dp @ ;

Когда выполняется код внутри квадратных скобок, наша память выглядит так:

Сначала идет заголовок словаря, содержащий поле ссылки и имя.  Затем вызов DOCOL, LIT и 0. HERE указывает на самый конец, после 0.
Сначала идет заголовок словаря, содержащий поле ссылки и имя. Затем вызов DOCOL, LIT и 0. HERE указывает на самый конец, после 0.

То, что мы хотим сделать, это поставить dpтам, где 0в настоящее время. Так как мы запустили swapперед определением нашего слова, адрес dpнаходится на вершине стека. После dup @ 2 -у нас будет указатель на ячейку, содержащую 0, и !мы перезапишем ее. Как видите, the 0не имеет особого значения, мы могли бы использовать любой литерал.

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

: cell+ 2 + ;
: cells dup + ;

Кроме того, поскольку у нас теперь есть dp, давайте напишем allot. Функциональность увеличения переменной может быть выделена в +!:

: +! ( u addr -- ) dup >r @ + r> ! ;
: allot ( len -- ) dp +! ;

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

: c, here c! 1 allot ;
: , here ! 2 allot ;

Далее мы напишем lit,, который добавляет литерал к текущему определению. Для этого нам нужен адрес LITассемблерной процедуры, которая обрабатывает литерал. Мы сохраняем его в 'lit«константе» с помощью трюка, аналогичного тому, что мы сделали для dp:

: 'lit 0 [ here 4 - @ here 2 - ! ] ;
: lit, 'lit , , ;

Это позволяет нам легко обрабатывать остальные переменные в стеке:

: disk# [ lit, ] ;
: base [ lit, ] ;
: st [ lit, ] ;
: latest [ lit, ] ;

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

Пользовательские переменные

Если вы в настроении пошалить, вы можете создать переменные из воздуха, просто упомянув их. Отсутствие проверки ошибок превратит их в число, по сути, дав вам случайный адрес. Например, srcpos u.выходы DA9C. Конечно, вы рискуете тем, что эти адреса будут конфликтовать либо друг с другом, либо с чем-то еще, например со стеком или пространством словаря.

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

: [[ 1 st c! ;

Нам также понадобится непрямой вариант ;. Единственное, что нужно сделать, это скомпилировать exit. Мы не знаем адрес exit, но можем прочитать его из последнего скомпилированного слова:

here 2 - @ : 'exit [ lit, ] ;

Например, вот как мы будем использовать его для constant:

: constant \ example: 42 constant the-answer
  : [[ lit, 'exit ,
;

createопределяет слово, которое помещает адрес сразу после него. Типичное использование

create some-array 10 cells allot

Чтобы вычислить адрес, который мы должны скомпилировать, нам нужно добавить 3 cells— по одному для каждого из LIT, фактического значения и EXIT.

: create : [[ here 3 cells + lit, 'exit , ;

variable, то просто allotодна ячейка:

: variable create 1 cells allot ;

Улучшениеs:

До сих пор указатели передавались s:и runуправлялись вручную. Однако это простой процесс, поэтому давайте его автоматизируем. srcposбудет содержать текущий конец буфера и checkpointбудет указывать на часть, которая еще не была запущена.

То есть в типичной ситуации исходный код начинался бы с 1000, заканчивался бы на srcpos, с контрольной точкой где-то посередине.
То есть в типичной ситуации исходный код начинался бы с 1000, заканчивался бы на srcpos, с контрольной точкой где-то посередине.
variable checkpoint
variable srcpos

Автоматический вариант s:называется s+:

: s+ ( -- ) srcpos @ s: dup u. srcpos ! ;

Мы также печатаем новый указатель. Это имеет два применения:

  • если вы допустили опечатку и хотите исправить, то можете просто прочитать примерный адрес, где нужно ковыряться;

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

Отложенная часть буфера может быть выполнена с помощью doit:

: move-checkpoint ( -- ) srcpos @ checkpoint ! ;
: doit ( -- ) checkpoint @ run move-checkpoint ;

Настройка этого сводится к чему-то вроде

1234 srcpos ! move-checkpoint

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

Ассемблер четвертого стиля

Обычный синтаксис сборки выглядит так:

    mov ax, bx

Если бы мы хотели справиться с этим , нам пришлось бы написать модный синтаксический анализатор, а мы никак не сможем сделать это без ветвей. Вместо этого давайте настроим синтаксис для наших целей — если AT&T разрешено это делать, то и мы тоже. Чтобы быть конкретным, давайте сделаем каждую инструкцию Форт-словом, передав аргументы через стек:

    bx ax movw-rr,

Я решил упорядочить аргументы как src dst instr,, с потоком данных слева направо. Это согласуется с тем, как данные передаются в обычном коде Forth, и является точным отражением синтаксиса Intel. После дефиса я включаю типы аргументов в том же порядке — регистр ( r), память ( m) или непосредственный ( i). Наконец, инструкции, которые могут быть размером как в байт, так и в слово, имеют суффикс bили w, как в синтаксисе AT&T.

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

кодировка инструкций x86

Проще всего кодировать инструкции, которые не принимают никаких аргументов. Например,

: stosb, AA c, ;  : stosw, AB c, ;  : lodsb, AC c, ;  : lodsw, AD c, ;

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

: int, CD c, c, ;

Некоторые инструкции используют битовое поле в байте кода операции. Например, немедленная загрузка, такая как mov cx, 0x1234`, кодирует регистр младшими 3 битами кода операции:

Младшие 3 бита кода операции инструкции «mov r16, imm16» содержат номер регистра, а остальные постоянны.
Младшие 3 бита кода операции инструкции «mov r16, imm16» содержат номер регистра, а остальные постоянны.

Регистры сопоставляются со следующими числовыми значениями:

: ax 0 ;  : cx 1 ;  : dx 2 ;  : bx 3 ;  : sp 4 ;  : bp 5 ;  : si 6 ;  : di 7 ;

Вы правильно прочитали, это идет AX CX DX BX. Насколько мне известно, это не потому, что кто-то в Intel забыл свои азбуки, а потому, что этимология этих имен регистров выглядит примерно так: «Аккумулятор , Счетчик , Данные , База » , и тот факт, что они являются первые четыре буквы просто совпадение. Или, во всяком случае, в этом суть. Этот пост на retrocomputing.SE содержит некоторые предположения о том, как это может быть полезно для конструкции оборудования, но не содержит твердых фактов.

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

: al 0 ;  : cl 1 ;  : dl 2 ;  : bl 3 ;  : ah 4 ;  : ch 5 ;  : dh 6 ;  : bh 7 ;

Таким образом, мы можем закодировать некоторые movs:

: movw-ir, B8 + c, , ;
: movb-ir, B0 + c, c, ;

Их можно использовать так:

ACAB bx movw-ir,
42 al movb-ir,

Обратите внимание, что ответственность за использование 8-битного регистра с movb, и 16-битного регистра с movw.

Некоторые другие инструкции, которые закодированы таким образом, incw/decwи push/pop:

: incw, 40 + c, ;
: decw, 48 + c, ;
: push, 50 + c, ;
: pop,  58 + c, ;

ModR/M

Самые сложные инструкции, с которыми нам придется иметь дело, используют байт ModR/M . Это механизм кодирования, отвечающий за такие инструкции, как add ax, [bx+si+16], но также и за такие простые, как mov ax, bx.

Сам код операции определяет шаблон, например mov r16, r/m16. В данном случае это означает, что адресатом является регистр, а источником является либо регистр, либо память. Байт ModR/M, который следует за кодом операции, определяет детали операндов:

Байт ModR/M идет сразу после кода операции.  Это битовое поле с тремя полями.  Старшие биты 7 и 6 образуют поле mod. Вместе с младшими тремя битами оно определяет режим адресации для операнда r/m.  Три бита в середине определяют другой операнд, который всегда является регистром.
Байт ModR/M идет сразу после кода операции. Это битовое поле с тремя полями. Старшие биты 7 и 6 образуют поле mod. Вместе с младшими тремя битами оно определяет режим адресации для операнда r/m. Три бита в середине определяют другой операнд, который всегда является регистром.

Три бита в середине определяют r16часть, а остальные определяют часть r/m16в соответствии с этой таблицей:

поле reg/[regs]

mod: 00

mod: 01

mod: 10

mod: 11

0

[BX+SI]

[BХ+SI+d8]

[BХ+SI+d16]

AL/AX

1

[BX+DI]

[BХ+DI+d8]

[BХ+DI+d16]

CL/CX

2

[BP+SI]

[BP+SI+d8]

[BP+SI+d16]

DL/DX

3

[BP+DI]

[BP+DI+d8]

[BP+DI+d16]

BL/BX

4

[SI]

[SI+d8]

[SI+d16]

АХ/SP

5

[DI]

[DI+d8]

[DI+d16]

CH/BP

6

[d16]

[BP+d8]

[BP+d16]

DH/SI

7

[BХ]

[BХ+d8]

[BХ+d16]

BH/DI

Как видите, если в поле mod установлено значение 3, то младшие 3 бита просто кодируют другой регистр в том же порядке, что и раньше. В противном случае мы выбираем одну из восьми возможностей для вычисления адреса с необязательным смещением, которое может быть либо 8, либо 16 бит. Упомянутое смещение идет сразу после байта ModR/M и при необходимости расширяется по знаку до 16 бит.

Есть одна неточность: если мы попытаемся закодировать a [BP]без какого-либо смещения, вместо этого мы получим жестко закодированный адрес, такой как mov bx, [0x1234], который должен идти после самого байта ModR/M. 4 Если вы помните, именно из-за отсутствия было выгодно [BP]переключение стека возврата на использование вместо него.DI

Специфическим аспектом этого кодирования является то, что операции между регистрами могут быть закодированы двумя разными способами. Возьмем xor cx, dx, например:

С одной стороны, вы можете использовать код операции «xor r/m16, r16» и поместить DX в поле регистра, а CX — в поле r/m.  Это дает байты 31 D1.  С другой стороны, вы можете использовать код операции «xor r16, r/m16» и соответствующим образом переупорядоченный байт ModR/M для кодирования той же инструкции, что и 33 CA.
С одной стороны, вы можете использовать код операции «xor r/m16, r16» и поместить DX в поле регистра, а CX — в поле r/m. Это дает байты 31 D1. С другой стороны, вы можете использовать код операции «xor r16, r/m16» и соответствующим образом переупорядоченный байт ModR/M для кодирования той же инструкции, что и 33 CA.

В любом случае, давайте это реализуем. Во-первых, вариант от регистрации к регистрации. Я выбрал слово для компиляции такого байта ModR/M , означающее, что в поле rm-r,есть регистр, который также может быть emory, за которым следует еще один регистр. У нас нет битовых смещений, но мы можем обойти это повторным добавлением:r``m``r

: 2* dup + ;
: 3shl 2* 2* 2* ;
: rm-r, ( reg-as-r/m reg -- ) 3shl + C0 + c, ;

При использовании rm-r,нам нужно убедиться, что используемый код операции соответствует шаблону r/m16, r16— в противном случае нам потребовались бы swapдва регистра:

: movw-rr, 8B c, rm-r, ;
: addw-rr, 03 c, rm-r, ;
: orw-rr, 0B c, rm-r, ;
: andw-rr, 23 c, rm-r, ;
: subw-rr, 2B c, rm-r, ;
: xorw-rr, 33 c, rm-r, ;
: cmpw-rr, 3B c, rm-r, ;

Варианты памяти для регистрации не намного сложнее. Мы определяем режимы адресации так же, как мы это делали для регистров.

: [bx+si] 0 ;  ; [bx+di] 1 ;  ; [bp+si] 2 ;  ; [bp+di] 3 ;
: [si] 4 ;  ; [di] 5 ;  ; [#] 6 ;  ; [bp] 6 ;  ; [bx] 7 ;

[#]режим абсолютного адреса, который следует использовать, собирая адрес вручную после инструкции, например

[#] ax movw-mr, some-addr ,

Я также включаю [bp], который конфликтует с [#], так как слова режима адреса могут использоваться совместно с режимами [??+d8]и [??+d16].

Аналогично rm-r,имеем m-r,:

: m-r, ( mem reg -- ) 3shl + c, ;

r-m,то же самое, просто поменяйте местами операнды:

: r-m, ( reg mem -- ) swap m-r, ;

Нет необходимости определять каждую инструкцию с операндами памяти, movдостаточно просто s:

: movw-mr, 8B c, m-r, ;
: movw-rm, 89 c, r-m, ;

Существует также одно несколько иное использование байта ModR/M. А именно, если инструкции требуется только один операнд (например, not bxили jmp ax), r/mфактически используется только он. В этом случае поле регистра вместо этого повторно используется как дополнительные биты для самого кода операции.

В руководстве Intel для этого используется обозначение opcode /regbits. Например, непрямой переход — это FF /4, а непрямой вызов — это FF /2совместное использование основного байта кода операции. Мы можем кодировать такие инструкции, просто введя нужное значение перед вызовом rm-r,.

: jmp-r, FF c, 4 rm-r, ;
: notw-r, F7 c, 2 rm-r, ;

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

: :code : [[ here 3 - dp ! ;

Чтобы закончить такое определение, мы компилируем NEXT:

: next, lodsw, ax jmp-r, ;

Обратите внимание, что next,не определяется с помощью :code— это эквивалент макроса ассемблера.

В качестве примера простого собранного примитива рассмотрим реализацию 1+:

:code 1+ bx incw, next,

Дисковый ввод-вывод

На самом деле этого достаточно, чтобы записать нашу работу на диск. Как и в случае с load, нам нужно создать пакет адресов дисков, а затем вызвать int 0x13. Одно примитивное слово может служить как для чтения, так и для записи, поскольку единственная разница заключается в значении, которое AXвам нужно. Крайне важно сохранить SI— я имел неудовольствие узнать это эмпирически .

create packet 10 allot
:code int13
  si push,              \ push si
  packet si movw-ir,    \ mov si, packet
  bx ax movw-rr,        \ mov ax, bx
  disk# dl movb-ir,     \ mov dl, disk#
  13 int,               \ int 0x13
  ax bx movw-rr,        \ mov bx, ax
  si pop,               \ pop si
next,

Обратите внимание, что мы сохраняем возвращаемое значение AXback в стеке. Это связано с тем, что ненулевое AHзначение сигнализирует об ошибке.

Чтобы заполнить packetданные, я использую вариант, ,который записывает в контролируемое место вместо here:

variable pos
: pos, ( val -- ) pos @ ! 2 pos +! ;
: make-packet ( block buffer -- )
  packet pos !
  10 pos, \ size of packet
  2 pos,  \ sector count
  pos, 0 pos, \ buffer address
  2* pos, 0 pos, 0 pos, 0 pos, \ LBA
;

Для чтения мы используем AH = 0x42, как и раньше. Запись использует AH = 0x43, но в этом случае значение определяет, ALхотим ли мы, чтобы BIOS проверял запись — мы делаем это, поэтому я установил для него значение 0x02.

: read-block make-packet 4200 int13 ;
: write-block make-packet 4302 int13 ;

Меры предосторожности

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

: p ( buf -- buf+1 ) dup c@ u. 1 + ;
\ later...
here 10 - p p p p p p p p p p p p p p p p drop

Еще одна хорошая проверка работоспособности — убедиться, что ничего, чего мы не ожидали, не было помещено в стек — обычно это происходит из-за того, что неопределенные слова плохо преобразуются в числа. Это можно сделать следующим образом dup u.: пустой стек приведет к ответу E0E, происходящему из-за безобидного опустошения стека, которое мы только что вызвали. Одним из примеров обнаруженной ошибки является опечатка, когда я набрал movb-it,вместо movb-ir,.

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

Первый доступ к диску, который я попробовал, был 0 4000 read-block u. 41fe @ u.. Это показывает AA55магическое число в конце загрузочного сектора. Затем я записал свой исходный код в блоки 1 и 2 и прочитал их в отдельный буфер, чтобы убедиться, что он работает. Оглядываясь назад, возможно, было бы неплохо прочитать блок, отличный от 0, перед попыткой записи, чтобы убедиться, что предоставление LBA работает правильно. К счастью, эта конкретная ошибка была чисто гипотетической.

Я также записал те же данные в блоки 0x101 и 0x102. Таким образом, я могу восстановиться, если когда-нибудь сломаю загрузку с обычными номерами блоков.

Прыжки

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

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

74 02 кодирует условный переход, который пропускает следующие 2 байта инструкций.  74 FD, который равен -3 в дополнении до двух, создаст петлю с еще одним байтом в нем, а также с двумя байтами перехода.
74 02 кодирует условный переход, который пропускает следующие 2 байта инструкций. 74 FD, который равен -3 в дополнении до двух, создаст петлю с еще одним байтом в нем, а также с двумя байтами перехода.

Чтобы составить дистанции прыжков, я использую две пары слов — одну для прыжков вперед, а другую для прыжков назад:

jnz, j> ... >j \ forward jump
j< ... jnz, <j \ backward jump

Правило состоит в том, что стрелки показывают направление прыжка, и стрелки должны быть «внутри» — другими словами, если вы получили два слова рядом друг с другом, эти стрелки должны подойти как влитые. Два слова просто общаются через стек. Например, j<просто запомнит текущее местоположение:

: j< here ;

Затем это используется функцией <j, которая вычитает текущую позицию и компилирует смещение:

: <j here 1 + - c, ;

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

: j> here 0 c, ;
: >j dup >r 1 + here swap - r> c! ;

Наконец, сами инструкции по прыжкам. Некоторые прыжки имеют несколько названий. Например, поскольку флаг переноса устанавливается, когда при вычитании требуется заимствование, a jcведет себя точно так же, как беззнаковое сравнение jump, если below. То же самое относится к jeи jz, но это достаточно интуитивно для меня, поэтому я не чувствовал необходимости определять оба имени.

: jb, 72 c, ;  ; jc, 72 c, ;  ; jae, 73 c, ;  ; jnc, 73 c, ;
: jz, 74 c, ;  ; jnz, 75 c, ;  ; jbe, 76 c, ;  ; ja, 77 c, ;
: jl, 7C c, ;  ; jge, 7D c, ;  ; jle, 7E c, ;  ; jg, 7F c, ;

Ветви

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

Диаграмма демонстрирует стратегию компиляции структуры if-else.  IF компилируется в две ячейки, где первая — (0branch), а вторая — цель перехода, которая указывает сразу после ELSE.  Перед этой целью перехода ELSE вводит безусловное (ответвление) в позицию THEN.
Диаграмма демонстрирует стратегию компиляции структуры if-else. IF компилируется в две ячейки, где первая — (0branch), а вторая — цель перехода, которая указывает сразу после ELSE. Перед этой целью перехода ELSE вводит безусловное (ответвление) в позицию THEN.

По соглашению имена слов, которые компилируются в определение, но не используются напрямую, заключены в круглые скобки, поэтому наши ветки называются (branch), что является безусловным, и (0branch), что выталкивает значение из стека и выполняет ветки, если оно равно нулю.

Мы можем прочитать цель перехода из последовательности указателей с помощью lodsw:

:code (branch)
  lodsw,           \ lodsw
  ax si movw-rr,   \ mov si, ax
next,

В случае условного перехода важно всегда читать (или пропускать) цель перехода, независимо от того, верно ли условие перехода.

:code (0branch)
  lodsw,           \ lodsw
  bx bx orw-rr,    \ or bx, bx
  jnz, j>          \ jnz .skip
  ax si movw-rr,   \ mov si, ax
>j               \ .skip:
  bx pop,          \ pop bx
next,

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

: br> here 0 , ;
: >br here swap ! ;
: br< here ;
: <br , ;

Поток управления

Чтобы логика, которая компилирует ifs, действительно выполнялась во время компиляции, нам нужно пометить эти слова как немедленные. Для этого мы используем immediate, который устанавливает непосредственный флаг последнего скомпилированного слова:

: immediate ( -- )
  latest @      \ получить указатель на слово
  cell+         \ пропустить поле ссылки
  dup >r c@     \ прочитать текущее значение  из length+flags поля
  80 +          \ установить flag
  r> c!         \ запись обратно
;

Нам также понадобится compile, который при вызове как compile xдобавляется xк слову, которое компилируется в данный момент. На самом деле нам не нужно делать его непосредственным словом, которое само по себе анализирует следующее слово, достаточно просто прочитать адрес xlike litили do it:(branch)

: compile r> dup cell+ >r @ , ;

ifэто просто условная прямая ветвь:

: if compile (0branch) br> ; immediate
: then >br ; immediate

elseнемного сложнее. Нам нужно скомпилировать безусловную ветвь, переходящую к then, а также разрешить ifпереход к точке сразу после безусловного перехода. Мне нравится использовать для этого слова манипулирования стеком возврата, поскольку стрелки совпадают со стрелками, используемыми >brи облегчают чтение кода:

: else >r compile (branch) br> r> >br ; immediate

Далее нам понадобятся циклы. Во-первых, простой begin ... againбесконечный цикл:

: begin br< ; immediate
: again compile (branch) <br ; immediate

begin ... untilне намного сложнее — просто используйте условный переход в конце:

: until compile (0branch) <br ; immediate

Наконец, уникальный цикл Форта begin ... while ... repeat, где условие цикла находится в середине цикла:

Диаграмма иллюстрирует стратегию компиляции для BEGIN-WHILE-REPEAT.  BEGIN ничего не компилирует, а просто сохраняет местоположение.  WHILE выполняет (0ветвь) после цикла, а REPEAT выполняет безусловную (ветвь) обратно к точке НАЧАЛА.
Диаграмма иллюстрирует стратегию компиляции для BEGIN-WHILE-REPEAT. BEGIN ничего не компилирует, а просто сохраняет местоположение. WHILE выполняет (0ветвь) после цикла, а REPEAT выполняет безусловную (ветвь) обратно к точке НАЧАЛА.
: while ( backjmp -- fwdjmp backjmp )
  compile (0branch) br> swap
; immediate
: repeat ( fwdjmp backjmp -- )
  compile (branch) <br >br
; immediate

Сравнения

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

: false 0 ;
: true FFFF ;

Я решил сгенерировать эти логические значения, сначала установив axзначение 0, а затем, возможно, уменьшив его на основе результата сравнения. Этот код можно разложить следующим образом:

: :cmp :code ax ax xorw-rr, ;
: cmp; j> ax decw, >j ax bx movw-rr, next, ;

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

:cmp 0= bx bx orw-rr, jnz, cmp;
:cmp 0<> bx bx orw-rr, jz, cmp;
:cmp 0< bx bx orw-rr, jge, cmp;
:cmp 0<= bx bx orw-rr, jg, cmp;
:cmp 0> bx bx orw-rr, jle, cmp;
:cmp 0>= bx bx orw-rr, jl, cmp;
:cmp = cx pop, bx cx cmpw-rr, jnz, cmp;
:cmp <> cx pop, bx cx cmpw-rr, jz, cmp;
:cmp u< cx pop, bx cx cmpw-rr, jae, cmp;
:cmp u<= cx pop, bx cx cmpw-rr, ja, cmp;
:cmp u> cx pop, bx cx cmpw-rr, jbe, cmp;
:cmp u>= cx pop, bx cx cmpw-rr, jb, cmp;
:cmp < cx pop, bx cx cmpw-rr, jge, cmp;
:cmp <= cx pop, bx cx cmpw-rr, jg, cmp;
:cmp > cx pop, bx cx cmpw-rr, jle, cmp;
:cmp >= cx pop, bx cx cmpw-rr, jl, cmp;

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

:code or ax pop, ax bx orw-rr, next,
:code and ax pop, ax bx andw-rr, next,
:code xor ax pop, ax bx xorw-rr, next,
:code invert bx notw-r, next,

Ура, циклы! Что теперь?

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

: type ( addr len -- )
  begin dup while 1 - >r
    dup c@ emit 1 +
  r> repeat drop drop
;

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

: seek ( addr -- end-addr ) begin dup c@ 0<> while 1 + repeat ;

Затем он используется для appendingустановки srcposи checkpointсоответствующим образом:

: appending ( addr -- ) seek dup u. srcpos ! move-checkpoint ;

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

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

\ cr emits a linebreak
: cr 0D emit 0A emit ;

40 constant line-length
10 constant #lines
: show-line ( addr -- next-addr )
  dup u.                    \ номер линии
  dup line-length type cr   \ содержимое линии
  line-length +
;

Затем он вызывается 16 раз в цикле с помощью list. Поскольку у нас еще нет do- loop, это довольно сложно.

: list ( addr -- )
  #lines begin
    >r show-line r>
  1 - dup 0= until
  drop drop
;

Иногда нам нужно переместить некоторый код. Для этого нам понадобится move. Это похоже на C memmoveв том, что он копирует данные с правого конца, так что результат правильный, даже если источник и место назначения перекрываются. Мы реализуем это с помощью инструкции x86 rep movsb, которая, по сути, состоит memcpyиз одной инструкции. Давайте пока обучим ассемблер остальным строковым инструкциям:

: rep, F2 c, ;
: movsb, A4 c, ;  ; movsw, A5 c, ;  ; cmpsb, A6 c, ;  ; cmpsw, A7 c, ;

Затем он используется cmove, который копирует данные вперед. 5 Эта оболочка несколько длинная, так как нам нужно сохранить значения siи di.

:code cmove ( src dest len -- )
  bx cx movw-rr,
  si ax movw-rr, di dx movw-rr,
  di pop, si pop,
  rep, movsb,
  ax si movw-rr, dx di movw-rr,
  bx pop,
next,

Далее нам понадобится cmove>, который начинается с конца буферов и копируется в обратном направлении. Стрелка >указывает, что это правильное слово для использования, если данные должны быть перемещены по более высокому адресу, т. е. вправо. Чтобы запустить такую копию, мы запускаем ее rep movsbс включенным флагом направления x86. Это предполагает, что регистры будут содержать адреса концов буферов , поэтому мы запускаем саму копию в (cmove>), а потом фактическое cmove>отвечает за вычисление правильного адреса.

: cld, FC c, ;  ; std, FD c, ;
:code (cmove>)
  bx cx movw-rr,
  si ax movw-rr, di dx movw-rr,
  di pop, si pop,
  std, rep, movsb, cld,
  ax si movw-rr, dx di movw-rr,
  bx pop,
next,
: cmove> ( src dest len -- )
  dup >r                  \ сохранить длину на стеке возвратов
  1 -                     \ нам нужно добавить len-1, чтобы получить конечный указатель
  dup >r + swap r> + swap \ настроить указатели
  r> (cmove>)
;

Наконец, moveсравнивает два адреса и выбирает подходящее направление копирования:

: over ( a b -- a b a ) >r dup r> swap ;
: move ( src dest len -- )
  >r
  over over u< if
    r> cmove>
  else
    r> cmove
  then
;

Реализация fillпохожа, и она полезна для стирания любых остатков после moves.

:code fill ( addr len byte -- )
  bx ax movw-rr,
  cx pop,
  di dx movw-rr, di pop,
  rep, stosb,
  dx di movw-rr,
  bx pop,
next,

Еще одна проблема при редактировании кода — определить, было ли уже написано конкретное слово. Для этого я написал words, который выводит список слов, известных системе. Напомним структуру словаря:

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

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

: count ( addr -- addr+1 len )
  dup 1+ swap c@
;

Учитывая указатель на заголовок словаря, >nameизвлечет из него имя:

1F constant lenmask
: >name ( header-ptr -- addr len )
  cell+     \ skip link pointer
  count lenmask and
;

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

: visible? ( header-ptr -- t | f )
  cell+ c@ 40 and 0=
;

Нашими последними вспомогательными словами являются space, которое просто печатает пробел, и #bl(обозначает пробел ), представляющее собой константу, в которой хранится ASCII-значение пробела. 6

: #bl 20 ;
: space #bl emit ;

Все это затем используется функцией words-in, которая принимает указатель на первое слово в списке. Это облегчит адаптацию, как только наш Форт получит поддержку словарей. 7

: words-in ( dictionary-ptr -- )
  begin dup while \ loop until NULL
    dup visible? if
      dup >name type space
    then
    @
  repeat
  drop ;
: words latest @ words-in ;

Разбор

Со временем мне нужно будет заменить внешний интерпретатор codegolf на другой, написанный на Forth. Это позволит мне добавить такие вещи, как правильная обработка неопределенных слов, знакомая okподсказка, а также словари и обработка исключений. 8 Первым шагом к этому является parse ( delim -- addr len )слово, которое будет анализировать ввод до тех пор, пока не встретится указанный символ-разделитель. Для обычного синтаксического анализа это будет пробел, но если мы установим его равным ), у нас, наконец, появятся комментарии.

parseхранит разделитель в переменной, чтобы его могли использовать вспомогательные слова.

variable sep

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

: sep? ( ch -- t | f ) dup 0= swap sep @ = or ;

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

: +sep ( ptr -- ptr' ) dup c@ 0<> if 1+ then ;

Цикл parseудерживает два указателя в стеке. Один не двигается и отмечает начало жетона. Другой продвигается в каждой итерации. В конце мы сохраняем перемещенный указатель в >in, а затем вычисляем длину, вычитая два указателя.

: parse ( sep -- addr len )
  sep ! >in @ dup begin ( begin-ptr end-ptr )
    dup c@ sep? invert
  while 1+ repeat
  dup +sep >in !  \ обновить >in
  over -          \ вычислить length
;

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

: skip ( sep -- sep ) begin dup >in @ c@ = while 1 >in +! repeat ;

tokenсочетает в себе два.

: token ( sep -- addr len ) skip parse ;

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

: char #bl token drop c@ ;

Однако, чтобы включить такой литерал в скомпилированное слово, нам нужно [char]:

: [char] char lit, ; immediate

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

: ( [char] ) parse 2drop ; immediate

Голое железо

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

В первый раз я попытался реализовать ветки перед записью на сам диск. Сам код ветвления был в порядке, но мой тест на зацикливание - нет. Попробуйте найти ошибку:

: foo begin dup u. 1 - 0= until ; 5 foo

Показать подсказку

Код вылетел вот так:

После выполнения 5 foo появилось около 6 строк вывода до зависания.  Выходные данные начинаются: 5 E0E 1F0E 1707 5BC и т. д., заканчиваясь на DB69 10 1, нижний левый символ рисования границы, 4, стрелка вправо, 1B 1) 10
После выполнения 5 foo появилось около 6 строк вывода до зависания. Выходные данные начинаются: 5 E0E 1F0E 1707 5BC и т. д., заканчиваясь на DB69 10 1, нижний левый символ рисования границы, 4, стрелка вправо, 1B 1) 10

Показать решение

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

Другая ошибка была в int13самом слове. Как я упоминал ранее, я забыл сохранить SI, который является указателем выполнения для многопоточного кода. Он рухнул, как только запустился next. По иронии судьбы, если бы я не был так осторожен и не выполнил write-blockсвою первую операцию, большая часть кода была бы сохранена ????

Помимо ошибок, есть еще одна проблема с запуском на «голом железе»: публикация кода на GitHub. Я решил эту проблему, написав скрипт, splitdisk.pyкоторый извлекает код из образа диска. Поскольку я загружаюсь с USB-накопителя, получение кода не займет много времени.

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

Что дальше?

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

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

Понравилась эта статья?

Возможно, вам понравятся и другие мои посты . Если вы хотите получать уведомления о новых, вы можете подписаться на меня в Твиттере или подписаться на RSS-канал .

Я хотел бы поблагодарить моих спонсоров GitHub за их поддержку: Michalina Sidor и Tijn Kersjes.


1

Есть небольшое отличие от стандартного поведения в том, что my loadпросто перенаправляет входной указатель, и блок будет выполняться только один раз, непосредственно перед тем, как выполнение достигнет REPL верхнего уровня.

2

Теперь до меня дошло, что причина, по которой его обычно называют, >inзаключается в том, что обычно это смещение ( >), которое добавляется к отдельному базовому адресу входного буфера. Ну что ж.

3

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

4

Если бы это было что-то вроде mov [0x1234], 0x5678, то использовался бы точный порядок: код операции, ModR/M, адрес, немедленный.

5

Это не лучшее название, так как это не то, что программист на C назвал бы "движением", но это то, что использует стандарт Forth, так что я буду придерживаться его.

6

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

7

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

8

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

Комментарии (5)


  1. ru_vlad
    31.05.2023 21:05
    +1

    Сколько лет прошло, а еще кое что вспомнил... Интересно, а где еще сейчас применяют Форт? Знаю что зарубежное сообщество вроде еще существует, а в нашей стране?


    1. forthuse Автор
      31.05.2023 21:05
      +2

      Есть действующий форум по Forth (Форт) и другим саморасширяющимся системам программирования

      P.S. Вероятно Форт где то применяется, если, к примеру, есть и железные контроллеры с поддержкой стековой модели вычислений и в виде реализации на FPGA, а также много Форт систем разной направленности и применимости сделаны и делаются как энтузиастами так и в представлении от некоторых фирм. В большей степени, конечно, для использования в составе контроллеров общего применения представленными на рынке, но и в создании программ для ПК и Мини-ПК он применяется под разными ОС (операционными системами Linux, Windows,… KolibriOS)
      В качесте языка реализации Форт можно встретить и достаточно экзотичные инструменты на том же Github при поиске по слову Forth.

      Телеграм канал по Форт

      [TF] Форт и общение фортеров
      Обсуждение конкатенативных языков программирования и тематическое общение программистов.

      Вопросы по Forth в qna.habr.com


  1. ru_vlad
    31.05.2023 21:05
    +1

    Про "железную" реализацию Фортмашины еще с Барановым и Ноздруновым в 80х обсуждали, были очень интересные планы на то время. Использования в системах реального времени на тот момент Форт давал хорошее время исполнения, сравнимым с ассемблером.


  1. Worky
    31.05.2023 21:05

    На тытрубке есть 2 канала любителей ФОРТа: один из США, вроде из Калифорнии, а второй международный - там и немцы, и японцы были. На всемирном Мур показывал свой многоядерный ФОРТ процессор и рассказывал как на нем программировать)))

    Еще запомнилось видео про портирование ФОРТа на LILYGO® FabGL VGA32 VGA ESP32.

    Короче, энтузиастов хватает, процесс идет, ФОРТ развивается.


    1. forthuse Автор
      31.05.2023 21:05

      Немного видео контента по Форт есть и на русском языке, но англоязычного контента гораздо больше как регулярно проводимые Zoom тусовки Forth2020

      https://www.youtube.com/watch?v=C9sLcsd8QT4

      P.S. Отсюда https://gamedev.ru/flame/forum/?id=263400&page=31