Ветвление: сборка не требуется

29 июня 2021 г. · 7 минут чтения

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

Предыдущий пост:
Нет веток? Нет проблем — Форт-ассемблер

Следующее сообщение:
Как Forth реализует исключения

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

Соответствующие ² доступных примитива:

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

Кроме того, у нас есть реализации следующего из [предыдущего поста](https://habr.com/ru/articles/739012/ :

• системные переменные latest, st, base, dp,disk#

• доступ к пространству словаря: here, allot, ,,c,

• определяющие слова create, variable,constant

• немного разного: +!, cell+, cells, compile, immediate,lit,

Вы можете запустить Miniforth, следуя инструкциям в репозитории GitHub . Если вы хотите попробовать реализовать ветки pure-Forth самостоятельно, сейчас самое время прекратить чтение. В противном случае мы будем изучать ветки на purityветке .

Безусловные ветви

Когда (branch)or (0branch)компилируется в слово, за ним сразу же следует адрес цели ветки:

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

: (branch)
  r>  \ вывести адрес возврата, который указывает на ячейку, содержащую цель перехода
  @   \ получить цель перехода
  >r  \ сделать это новым обратным адресом
;

Условные ветки

Ясно, что сложность условного перехода сводится к выбору между двумя возможными значениями адреса возврата. Это было бы довольно просто, если бы у нас было andи 0=— поскольку в Форте trueустановлены все биты, мы можем andс помощью логического флага выбирать между значением по нашему выбору и 0,3 ^.

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

: (0branch)
  0=              ( должен перейти )
  r> dup cell+    ( должен пкркйти addr-of-offset retaddr-if-false )
  >r @ and r>     ( offset|0 retaddr-if-false )
  + >r
;

К сожалению, у нас нет andили 0=. Тем не менее, это все еще полезная отправная точка. Можем ли мы как-то реализовать эти слова?

Сдвиг битов вокруг

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

Сдвиг влево достаточно прост, так как это просто умножение на два:

: 2* dup + ;

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

variable x
: lobyte x ! x c@ ;
: hibyte x ! x 1 + c@ ;

По сути, это 8-битный сдвиг вправо. Давайте используем это, чтобы проверить, равно ли число нулю. Нам нужно ИЛИ все биты вместе, но у нас нет ни того, orни другого. Однако сложение несколько похоже, поэтому давайте посчитаем биты в значении.

s ( c v -- c' v' )обрабатывает одну итерацию «цикла» — он немного сдвигается за пределы 8-битного значения vи добавляет его к счетчику c.

: s 2* dup >r hibyte + r> lobyte ;

Выполнение этого 8 раз будет подсчитывать биты в байте, вот что делает nb( number of its):b

: nb 0 swap s s s s s s s s drop ;

nbw( nчисло bего в wорде) делает то же самое для полного 16-битного значения, вызывая nbдля каждой половины:

: nbw dup hibyte nb swap lobyte nb + ;

Как нам превратить это в сравнение с нулем? Повторяем nbнесколько раз:

• после nbwу вас будет значение не более 16,

• после nbw nbу вас будет значение не более 4,

• после nbw nb nbу вас будет значение не более 2,

• после nbw nb nb nbу вас будет значение либо 0, либо 1.

: 1bit nbw nb nb nb ;

Выбор между значениями

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

create bb 2 cells allot
: (0branch)
  r> dup              \ две копии
  @ bb !              \ bb[0] = адрес возврата, если на стеке 0
  cell+ bb cell+ !    \ bb[1] = адрес возврата, если на стеке есть что-то еще
  1bit cells bb + @ >r
;

Другие решения: компромисс между временем и памятью

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

Например, мы могли бы подготовить 256-байтовую таблицу поиска для файлов 1bit. Поскольку у нас нет никакого способа зациклиться, нам нужно будет повторить все вручную. Поскольку 255 = 3 × 5 × 17, это может выглядеть так:

: x 1 c, ;      \ записать 1 один
: y x x x ;     \  записать 3
: z y y y y y ; \ записать 15
create tab 0 c,
z z z z z z z z z z z z z z z z z     \ 17 times
: 1bit-half tab + c@ ;
: 1bit dup hibyte 1bit-half swap lobyte 1bit-half + 1bit-half ;

И это всё?

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

Вы можете спросить, это все, что нам нужно для полноты по Тьюрингу? ⁶ Возможно, есть какой-то примитив, который мы не сможем определить по какой-то причине? Я не думаю, что нам нужно беспокоиться. Наша ветвь может быть использована для реализации структуры управления циклом до нуля, и это все, что есть у brainfuck .

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

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

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

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

¹

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

²

Я пропускаю loadи s:, так как они не помогут, и их описание выходит за рамки этого поста. Я описал их в предыдущем посте , если вам интересно.↩

³

Этот подход, кажется, независимо изобретался как минимум трижды: мной , Цезарем Блюмом и Полом Слей .↩

⁴

Напомним, что x86 имеет прямой порядок следования байтов, и поэтому значение like 1234хранится как 34 12в памяти.↩

⁵

Кажется, я научился этой технике у M/o/Vfuscator .↩

⁶

Что ж, поскольку память конечна, все, что мы на самом деле когда-либо создавали, — это просто очень большая конечная машина. Я полагаю, что более близким понятием будет LBA-полнота, если мы будем педантичными, но я не стал бы надеяться на полностью формальное определение, которое отражает то, что мы обычно подразумеваем под «полным по Тьюрингу», когда говорим о вещах, которые действительно существуют.↩