Байт-машина для форта (и не только) по-индейски (часть 3)
Наступил год 2019. Новогодние праздники подходят к концу. Самое время начать вспоминать байты, команды, переменные, циклы…
Что-то я все уже забыл с этими праздниками. Придется вспоминать вместе!
Сегодня сделаем интерпретатор для нашей байт-машины. Это третья статья, первые части тут: часть 1, часть 2.
Всех с новым годом, и добро пожаловать под кат!
Для начала отвечу на вопросы от fpauk. Вопросы эти совершенно правильные. Сейчас архитектура этой байт-машины такова, что мы работаем с прямыми, процессорными адресами. Но в байт-коде этих адресов нет, они формируются уже после старта системы. После старта системы мы можем создавать любые указатели, и этот код будет правильно работать на любой платформе. Например, адрес переменной или массива можно получить командой var0. Эта команда отработает на любой платформе и вернет правильный адрес, специфичный для данной платформы. Потом можно как угодно работать с этим адресом.
Но все же, fpauk прав. Адрес в байт-коде сохранять нельзя. Получается, мы можем писать платформонезависимый код, но для этого надо прилагать некоторые усилия. В частности, следить за тем, что бы в байт-код не попали адреса. А они могут попасть, если, например, скомпилированный код сохранить в файл. В нем будут данные, и они могут быть адресами. Например, значения переменных here, context, и других.
Что бы избавиться от такой проблемы, нужно сделать адреса виртуальными. Адресация процессора x86 довольно мощная, и, в большинстве случаев, это даже не добавит лишних команд. Но все же я продолжу в текущей архитектуре, с абсолютными адресами. А потом, когда дойдем до тестов, можно будет переделать адреса на виртуальные, и посмотреть, как это повлияет на быстродействие. Это интересно.
Разминка
А теперь небольшая разминка. Сделаем очередную порцию маленьких, но полезных байт-команд. Это будут команды nip, emit, 1+, +!, -!, count, слова работы со стеком возвратов r>, >r, r@, строковый литерал (»), и слова-константы 1, 2, 3, 4, 8. Не забудем их включить в таблицу команд.
b_nip = 0x39
bcmd_nip: pop rax
mov [rsp], rax
jmp _next
b_emit = 0x81
bcmd_emit: pop rax
mov rsi, offset emit_buf # адрес буфера
mov [rsi], al
mov rax, 1 # системный вызов № 1 - sys_write
mov rdi, 1 # поток № 1 - stdout
mov rdx, 1 # длинна буфера
push r8
syscall # вызов ядра
pop r8
jmp _next
b_wp = 0x18
bcmd_wp: incq [rsp]
jmp _next
b_setp = 0x48
bcmd_setp: pop rcx
pop rax
add [rcx], rax
jmp _next
b_setm = 0x49
bcmd_setm: pop rcx
pop rax
sub [rcx], rax
jmp _next
b_2r = 0x60
bcmd_2r: pop rax
sub rbp, 8
mov [rbp], rax
jmp _next
b_r2 = 0x61
bcmd_r2: push [rbp]
add rbp, 8
jmp _next
b_rget = 0x62
bcmd_rget: push [rbp]
jmp _next
b_str = 0x82
bcmd_str: movzx rax, byte ptr [r8]
lea r8, [r8 + rax + 1]
jmp _next
b_count = 0x84
bcmd_count: pop rcx
movzx rax, byte ptr [rcx]
inc rcx
push rcx
push rax
jmp _next
b_num1 = 0x03
bcmd_num1: push 1
jmp _next
b_num2 = 0x04
bcmd_num2: push 2
jmp _next
b_num3 = 0x05
bcmd_num3: push 3
jmp _next
b_num4 = 0x06
bcmd_num4: push 4
jmp _next
b_num8 = 0x07
bcmd_num8: push 8
jmp _next
Команда nip удаляет слово, находящееся под вершиной стека. Оно эквивалентно командам swap drop. Иногда это может быть полезно.
Команда emit выводит один символ со стека. Она использует тот же системный вызов номер 1, символ помещает в буфер с длиной 1.
Команда count очень простая — берет со стека адрес строки со счетчиком и превращает его в два значения — адрес строки без счетчика и длину.
Команды b_2r, b_r2, b_rget — это фортовские слова r>, >r, r@. Первая достает слово из стека возвратов и помещает в арифметический стек. Вторая осуществляет противоположную операцию. Третья — копирует слово из стека возвратов, помещает в арифметический, стек возвратов при этом не меняется.
Команды b_setp и b_setm — это слова +! и -!… Они берут со стека значение и адрес, и модифицируют слово по указанному адресу, прибавляя или отнимая значение со стека.
Команда b_str имеет параметр произвольной длины — строка со счетчиком. Эта строка находится в байт-коде после байта команды, а команда просто кладет на стек адрес этой строки. Фактически, это строковый литерал.
Остальные команды, думаю, в комментариях не нуждается.
Еще сделаем команду для печати константной строки (.»). Реализуем ее как точку входа в type, следующим образом:
b_strp = 0x83
bcmd_strp: movsx rax, byte ptr [r8]
inc r8
push rax
push r8
add r8, rax
b_type = 0x80
bcmd_type: mov rax, 1 # системный вызов № 1 - sys_write
mov rdi, 1 # поток № 1 - stdout
pop rdx # длинна буфера
pop rsi # адрес буфера
push r8
syscall # вызов ядра
pop r8
jmp _next
Эта команда устроена похожим образом, что и b_str. Только она на стек не помещает ничего. Строка, расположенная за этой командой как параметр, просто выводится пользователю.
Разминка закончена, пришла пора чего-то более серьезного. Разберемся со словами-генераторами и остальными командами var.
Слова-генераторы
Вспомним переменные. Как они устроены на уровне байт-кода мы знаем (команда var0). Что бы создать новую переменную, в форте используется такая конструкция:
variable <имя переменной>
После выполнения такой последовательности, создается новое слово. Исполнение этого нового слова помещает на стек адрес для хранения значения переменной. В форте есть еще константы, они создаются так:
<значение> constant <имя константы>
После создания константы, исполнение слова помещает на стек .
Так вот, и слово variable, и слово constant — это слова-генераторы. Они предназначены для создания новых слов. В форте такие слова описываются с помощью конструкции create… does>. Переменные и константы можно определить таким образом:
: variable create 0 , does> ;
: constant create , does> @ ;
Что это все значит?
Слово create при своем исполнении создает новое слово с именем, которое оно возьмет при исполнении из входного потока. После создания выполняется последовательность слов до слова does>. А вот в момент исполнения этого слова, выполняется то, что написано после does>. При этом на стеке уже будет лежать адрес данных (как говорят в форте, «поля данных»).
Таким образом, при создании переменной, выполняется последовательность »0,» — это резервирование машинного слова с заполнением нулем. А при исполнении созданного слова, не делается ничего (после does> нет ничего). На стеке просто остается адрес памяти, где храниться значение.
В определении константы резервируется слово с заполнением значением, которое находится на стеке. При исполнении созданного слова выполняется »@», которое извлекает значение по указанному адресу.
А теперь давайте подумаем, как может быть устроено слово, которое мы создаем. Оно помещает адрес данных на стек (как var0), а потом передает управление по определенному адресу, на байт-код. Команда var0 сразу делает возврат. Но в данном случае нам надо сделать не возврат, а, фактически, переход.
Еще раз сформулирую, что нужно сделать:
- положить в стек адрес данных
- выполнить переход на кусочек кода после does>
Получается, нужно просто передать управление на другой адрес байт-кода, но предварительно положить адрес следующего байта (R8) на стек.
Это же почти команда branch! А у нас она не одна. Уже есть branch8 и branch16. Назовем новые команды var8 и var16, и это пусть будут просто точки входа в команды branch. Сэкономим на переходе в команду перехода :) Значит, будет вот так:
b_var8 = 0x29
bcmd_var8: push r8
b_branch8 = 0x10
bcmd_branch8: movsx rax, byte ptr [r8]
add r8, rax
jmp _next
b_var16 = 0x30
bcmd_var16: push r8
b_branch16 = 0x11
bcmd_branch16: movsx rax, word ptr [r8]
add r8, rax
jmp _next
По-хорошему, еще не помешает команда var32, да и var64 тоже. Таких длинных переходов у нас нет, так как обычные переходы не бывают такими длинными. А вот для команды var это вполне реалистичный случай. Но пока не будем делать эти команды. Сделаем потом, если понадобиться.
Со словами-генераторами разобрались. Пришла очередь определиться со словарем.
Словарь
Обычно, когда говорят упрощенно о словаре форта, его представляют в виде однонаправленного списка словарных статей. На самом деле все чуть сложнее, так как форт поддерживает множество словарей. Фактически, они представляют собой дерево. Поиск слова в таком дереве начинается с «листа» — это последнее слово в текущем словаре. Текущий словарь определяет переменная context, а адрес последнего слова находится в слове-словаре. Для управления словарями служит еще одна переменная — current, она определяет словарь, куда будут добавляться новые слова. Таким образом, для поиска может быть установлен один словарь, а для включения новых слов — другой.
Для нашего простого случая можно было бы не делать поддержку множества словарей, но я решил ничего не упрощать. На самом деле, что бы понять байт-код, байт-машину, знать то, что описано в этом разделе не обязательно. Поэтому, кому не интересно, можно просто пропустить этот раздел. Ну, а кто хочет знать детали — вперед!
Изначально существует базовый словарь с именем forth. Это значит, что есть такое слово — forth. Это слово так же называется «словарь», в этом есть некоторая путаница. Поэтому, если речь идет именно о слове, я буду называть его слово-словарь.
Новые словари создаются с помощью такой конструкции:
vocabulary <имя создаваемого словаря>
При этом создается слово с именем. При исполнении, это слово будет устанавливать созданный словарь как стартовый для поиска.
Фактически, в слове-словаре находится ссылка на последнюю статью этого словаря, с которой начинается поиск. А в момент исполнения это слово-словарь записывает ссылку на свое поле данных в переменную context.
Попозже можно будет сделать слово vocabulary, которое на форте, в текущей реализации, описывается довольно просто:
: vocabulary create context @ , does> context ! ;
Итак, создаем слово forth. Будем использовать команду var8. Байт-код «context!» разместим сразу после поля данных:
forth: .byte b_var8
.byte does_voc - . - 1
.quad 0 # <-- Тут должен быть адрес последнего слова. Но я установлю его при инициализации, что бы в байт-коде не было прямых адресов.
does_voc:
.byte b_call8
.byte context - . - 1
.byte b_set
.byte b_exit
А теперь вернемся к созданию самого словаря.
Вообще, в форте, описание слова в памяти называется «словарная статья». Обычными терминами я бы сказал, что есть заголовок статьи и ее код. Но в форте все не совсем обычно, там это называется «поле имени», «поле связи», «поле кода» и «поле данных». Попробую рассказать, что все это значит традиционными терминами.
Поле имени — это название слова, «строка со счетчиком». Это как в старом паскале — байт длины строки, потом строка. Поле связи — это ссылка на предыдущую статью. Раньше был просто адрес, но у нас будет платформонезависимый код, и это будет смещение. Поле кода, традиционно в форте, это машинный код (когда реализация на прямом шитом), для слов вне ядра там было call _call. У нас будет просто байт-код. А поле данных — это для слов, содержащих данные — например, для переменных или констант. Кстати, слово-словарь тоже к нему относится.
Для компилятора нам еще обязательно понадобятся флаги. Обычно форту нужен только один флаг — immediate, и его помещают в байт длинны (иногда бывает еще один — hidden). Но это для прямого шитого кода, где управление процессора передают при вызове на поле кода. А у нас есть слова разные — байт-код и машинный код, и флагов нужно как минимум два, а то и три.
Сколько нужно для поля связи? В начале я хотел использовать 16 бит. Это ведь ссылка на предыдущее слово, а слово точно меньше 64 Кб. Но потом вспомнил, что в слове могут быть данные практически любого размера. И к тому же, при наличии нескольких словарей, ссылка может идти через множество слов. Получается, в большинстве случаев хватит 8 бит, но может быть и 16, и 32. И даже 64 бит, если будут данные более 4 Гб. Ну что же, сделаем поддержку всех вариантов. Какой вариант используется — поместим во флаги. Получается, минимум 4 флага: признак immediate, признак слова ядра, и 2 бита на вариант используемого поля связи. Нужно использовать отдельный байт для флагов, по-другому никак.
Флаги определим так:
f_code = 0x80
f_immediate = 0x60
Флаг f_code будет у слов ядра, написанных на ассемблере, флаг f_immediate пригодиться для компилятора, о нем в следующей статье. А два младших бита определят длину поля связи (1, 2, 4 или 8 байт).
Итак, заголовок статьи будет такой:
- флаги (1 байт)
- поле связи (1–8 байт)
- байт длины имени
- имя (1–255 байт)
До этого момента я не использовал возможности «макро» ассемблера. А сейчас они нам понадобятся. Вот такой у меня получился макрос с именем item для формирования заголовка слова:
.macro item name, flags = 0
link = . - p_item
9:
.if link >= -256/2 && link < 256/2
.byte \flags
.byte link
.elseif link >= -256*256/2 && link < 256*256/2
.byte \flags | 1
.word . - p_item
.elseif link >= -256*256*256*256/2 && link < 256*256*256*256/2
.byte \flags | 2
.int . - p_item
.elseif link >= -256*256*256*256*256*256*256*256/2 && link < 256*256*256*256*256*256*256*256/2
.byte \flags | 3
.quad . - p_item
.endif
p_item = 9b
.byte 9f - . - 1
.ascii "\name"
9:
.endm
Этот макрос использует значение p_item — это адрес предыдущей словарной статьи. Это значение в конеце обновляется для последующего использования: p_item = 9b. Тут 9b — это метка, а не число, путать не надо :) Макрос имеет два параметра — имя слова и флаги (необязательный). В начале макроса вычисляется смещение на предыдущее слово. Потом, в зависимости от размера смещения, компилируются флаги и поле связи нужного размера. Затем байт длины имени и само имя.
Определим перед первым словом p_item так:
p_item = .
Точка — это текущий адрес компиляции на ассемблере. В результате такого определения, первое слово будет ссылаться само на себя (поле связи будет 0). Это признак конца словарей.
Кстати, а что будет в поле кода у слов ядра? Надо, как минимум, где-то сохранить код команды. Я решил пойти по максимально простому пути. Для слов ядра там будет тоже байт-код. Для большинства команд это будет просто байт-команда, а за ней b_exit. Таким образом, для интерпретатора флаг f_code анализировать не нужно, и команды для него ничем не будут различаться. Нужно будет просто для всех вызывать байт-код.
Для этого варианта есть еще одно преимущество. Для команд с параметрами можно прописать безопасные параметры. Например, если вызвать команду lit в реализациях форта с прямым шитым кодом, система упадет. А у нас там будет написано, например, lit 0, и эта последовательность просто поместит 0 на стек. Даже для branch можно сделать безопасно!
.byte branch8
.byte 0f - .
0: .byte b_exit
При таком вызове будут некоторые накладные расходы, но для интерпретатора они будут не существенны. А компилятор будет анализировать флаги, и скомпилирует правильный и быстрый код.
Первое слово будет, конечно же, слово «forth» — это создаваемый нами базовый словарь. Тут, как раз, пригодиться команда var со ссылкой на код после does>. Этот код я уже приводил в предыдущем разделе, но повторю еще раз, с заголовком:
p_item = .
item forth
.byte b_var8
.byte does_voc - . - 1
.quad 0
does_voc:
.byte b_call8
.byte context - . - 1
.byte b_set
.byte b_exit
И сразу сделаем переменные context и current, они нам потребуются для поиска слов:
item current
.byte b_var0
.quad 0
item context
context: .byte b_var0
.quad 0
А теперь, надо набраться терпения, и прописать заголовок для каждого слова, что мы написали на ассемблере, с флагом f_code:
item 0, f_code
.byte b_num0
.byte b_exit
item 1, f_code
.byte b_num1
.byte b_exit
...
item 1-, f_code
.byte b_wm
.byte b_exit
item 1+, f_code
.byte b_wp
.byte b_exit
item +, f_code
.byte b_add
.byte b_exit
item -, f_code
.byte b_sub
.byte b_exit
item *, f_code
.byte b_mul
.byte b_exit
И так далее…
С командами, написанными на байт-коде еще легче. Достаточно добавить перед байт-кодом просто заголовок, так же, как и у слова forth, например:
item hold
hold: .byte b_call8
.byte holdpoint - . - 1 # holdpoint
...
Для команд с параметрами сделаем безопасные параметры. Например, команды lit пусть возвращают число Пи, если кто-то их вызовет интерактивно, будет такая пасхалка :)
item lit8, f_code
.byte b_lit8
.byte 31
.byte b_exit
item lit16, f_code
.byte b_lit16
.word 31415
.byte b_exit
item lit32, f_code
.byte b_lit32
.int 31415926
.byte b_exit
item lit64, f_code
.byte b_lit64
.quad 31415926535
.byte b_exit
Последним словом в списке сделаем символично слово bye. Но нам еще надо при инициализации записать адрес этого слова в поле данных forth. Что бы получить адрес этого слова, используем команду var0:
last_item: .byte b_var0
item bye, f_code
.byte b_bye
В такой конструкции, если мы вызовем в байт-коде адрес last_item, то получим как раз адрес слова bye. Что бы записать его в поля данных слова forth, выполним forth, и нужный адрес окажется в context. Таким образом, код инициализации системы будет такой:
forth last_item context @ !
А теперь приступим непосредственно к интерпретатору. Для начала нам потребуется работа с буфером ввода и извлечение из него слов. Напомню, что интерпретатор в форте очень простой. Он извлекает из входного буфера последовательно слова, пытается их найти. Если слово находится — интерпретатор запускает его на исполнение.
Буфер ввода и извлечение слов
Если честно, я не хочу тратить много времени на изучение стандартов форта. Но все же постараюсь сделать максимально близко к ним, в основном, по памяти. Если знатоки форта увидят тут сильное не соответствие — пишите, я исправлю.
Для работы с буфером у форта есть три переменные: tib, #tib и >in. Переменная tib кладет на стек адрес буфера ввода. Переменная #tib помещает в стек количество символов, которые находятся в буфере. А переменная >in содержит смещение во входном буфере, дальше которого находится необработанный текст. Определим эти переменные.
item tib
.byte b_var0
v_tib: .quad 0
item #tib
.byte b_var0
v_ntib: .quad 0
item >in
.byte b_var0
v_in: .quad 0
Дальше сделаем слово blword. Это слово, используя указанные переменные, получает из входного потока следующее слово. В качестве разделителей используется пробел и все символы с кодом меньше пробела. Это слово будет на ассемблере. У меня, после отладки, получилось так:
b_blword = 0xF0
bcmd_blword: mov rsi, v_tib # адрес текстового буфера
mov rdx, rsi # сохраним в RDX начало текстового буфера для последующего использования
mov rax, v_in # смещение в текстовом буфере
mov rcx, v_ntib # размер текстового буфера
add rsi, rax # теперь RSI - указатель на начало обрабатываемого текста
sub rcx, rax # получили количество оставшихся символов
jz 3f
word2: lodsb # загрузка в AL по RSI с инкрементом
cmp al, ' '
ja 1f # пропускаем все разделители (пробел или с кодом меньше)
dec rcx
jnz word2 # цикл по пробелам
3: sub rsi, rdx
mov v_in, rsi
push rcx
jmp _next
1: lea rdi, [rsi - 1] # RDI = RSI - 1 (начало слова)
dec rcx
word3: lodsb
cmp al, ' '
jbe 2f
dec rcx
jnz word3
2: mov rax, rsi
sub rsi, rdx # смещение на первый символ после первого разделителя (для поиска следующего слова)
mov v_in, rsi
sub rax, rdi
dec rax
jz word1
push rdi # начало слова
word1: push rax # длина слова
jmp _next
Это слово похоже на стандартное word, но, в отличие от него, учитывает все разделители и не копирует слово в буфер. Возвращает просто два значения на стеке — адрес и длину. Если слово извлечь не удается, возвращает 0. Пришла пора начать писать интерпретатор.
Поиск слов и интерпретатор
Для начала, сделаем слово interpret. Это слово выбирает новое слово из буфера с помощью blworld, ищет его в словаре и исполняет. И так повторяет, пока буфер не будет исчерпан. У нас пока нет возможности искать слово, поэтому напишем тестовую заглушку, которая будет слово из буфера просто выводить с помощью type. Это даст нам возможность проверить и отладить blworld:
# : interpret begin blword dup while type repeat drop ;
item interpret
1: .byte b_blword
.byte b_dup
.byte b_qnbranch8
.byte 0f - .
.byte b_type
.byte b_branch8
.byte 1b - .
0: .byte b_drop
.byte b_exit
Теперь сделаем слово quit. Обычно так и делают при реализации форт-систем: используют слово quit или abort для входа в режим интерпретатора. Слово quit сбрасывает стеки и запускает бесконечный цикл ввода в буфер и интерпретации. У нас это будет просто вызов interpret. Код этого слова будет состоять из двух частей. Первая часть будет на ассемблере, вторая часть — на байт-коде. Первая часть:
b_quit = 0xF1
bcmd_quit: lea r8, quit
mov sp, init_stack
mov bp, init_rstack
jmp _next
Вторая часть:
quit: .byte b_call16
.word interpret - . - 2
.byte b_bye
Как обычно, код на ассемблере размещается в секции .text, байт-код — в секции .data.
И, наконец, изменим стартовый байт-код. Там будет только инициализация словаря, установка буфера на стартовую строку, и вызов quit.
# forth last_item context @ ! start_code tib ! <длина стартового кода> #tib ! quit
start: .byte b_call16
.word forth - . - 2
.byte b_call16
.word last_item - . - 2
.byte b_call16
.word context - . - 2
.byte b_get
.byte b_set
.byte b_call8
.byte start_code - . - 1
.byte b_call16
.word tib - . - 2
.byte b_set
.byte b_lit16
.world 1f - 0f
.byte b_call16
.word ntib - . - 2
.byte b_set
.byte b_quit
start_code: .byte b_var0
0: .ascii "word1 word2 word3"
1:
Компилируем, линкуем, запускаем! $ as forth.s -o forth.o -g -ahlsm >list.txt
$ ld forth.o -o forth
$ ./forth
word1word2wordBye!
Немножко похоже на кашу, но именно такой результат и должен быть. Мы выводили без разделителей. Кстати, поставим перевод строки перед buy на будущее, это не помешает.
Конечно, пришлось повозиться с отладкой. Кроме уже упомянутого «Segmentation fault (core dumped)», иногда получались интересные результаты. Например, такой: $ ./forth
word1word2word3forth)%60Acurrent(context(%600lit8lit16zlit32v%5E%DF%80lit64v%5E%DF%80call8call16call32branch8branch16qbranch8qbranch16exit1-+!-%22*#/$mod%25/mod&abs'dup0drop1swap2rot3-rot4over5pick6roll7depth8@@!Ac@Bc!Cw@Dw!Ei@Fi!G0=P0%3CQ0%3ER=S%3CT%3EU%3C=V%3E=Wvar8)var160base(holdbuf(Qholdpoint(hold@0U110ACp@&20T0!?!%3CgF!A0@RF!5%220'%DE%A61Q-%DD%80:tib(%7F%60(%3Ein(%20%20%20%20%20%20%20interpret01('byeSegmentation%20fault%20(core%20dumped)
Это, похоже, прямо весь наш словарь в двоичном виде текстом, порезанный на разделители :) Так получилось, когда я забыл «dec rcx» перед word3 в команде b_blword.
Слова выбирать из входного потока умеем, словарь есть. Теперь нужно реализовать поиск по словарю и запуск слов на исполнение. Для этого потребуются слова find, cfa и execute.
Слово find будет забирать со стека адрес слова и его длину. Возвращать это слово будет адрес словарной статьи или 0, если не найдено.
Слово cfa по адресу статьи вычислит адрес исполнимого байт-кода.
А слово execute исполнит байт-код.
Начнем с find. В стандартах форта оно принимает один адрес — строку со счетчиком. Но я не хочу лишний раз копировать строку в буфер, поэтому немного отклонюсь от стандартов. Слово find будет принимать в стеке два параметра — адрес и длину строки (собственно, то, что возвращает слово blword). После отладки это слово приняло такой вид:
b_find = 0xF2
bcmd_find: pop rbx # длина имени
pop r9 # адрес имени
mov rdx, v_context
mov rdx, [rdx] # получили адрес последней словарной статьи для поиска
# цикл поиска
find0: mov al, [rdx] # флаги
and al, 3 # два младших - это вариангт длинны поля связи, остальные флаги нас не интересуют, они для компилятора
or al, al
jz find_l8
cmp al, 1
jz find_l16
cmp al, 2
jz find_l32
mov r10, [rdx + 1] # смещение 64 бита
lea rsi, [rdx + 9] # адрес имени
jmp find1
find_l32: movsx r10, dword ptr [rdx + 1] # смещение 32 бита
lea rsi, [rdx + 5] # адрес имени
jmp find1
find_l16: movsx r10, word ptr [rdx + 1] # смещение 16 бит
lea rsi, [rdx + 3] # адрес имени
jmp find1
find_l8: movsx r10, byte ptr [rdx + 1] # смещение 8 бит
lea rsi, [rdx + 2] # адрес имени
find1: movzx rax, byte ptr [rsi] # длина имени из проверяемой словарной статьи
cmp rax, rbx
jz find2
# имя не совпало по длине
find3: or r10, r10
jz find_notfound # конец поиска, слово не найдено
add rdx, r10 # переходим к следующей статье
jmp find0
# длина совпала, сравниваем строки
find2: inc rsi
mov rdi, r9
mov rcx, rax
repz cmpsb
jnz find3
# слово найдено
push rdx
jmp _next
find_notfound: push r10
jmp _next
Пожалуй, это самое сложное на сегодня слово. Теперь модифицируем слово interpret, заменив type на «find .»:
# : interpret begin blword dup while find . repeat drop ;
item interpret
interpret: .byte b_blword
.byte b_dup
.byte b_qnbranch8
.byte 0f - .
.byte b_find
.byte b_call16
.word dot - . - 2
.byte b_branch8
.byte interpret - .
0: .byte b_drop
.byte b_exit
В тестовой строке надо поставить слова, которые есть в словаре, например »0 1- dup + .».
Все готово к запуску! $ ld forth.o -o forth
$ ./forth
6297733 6297898 6298375
Bye!
Отлично, поиск работает. Это адреса слов (в десятичной системе счисления). Теперь слово cfa. Пусть оно тоже будет на ассемблере, оно очень простое, работа с флагами похожа на find:
b_cfa = 0xF3
bcmd_cfa: pop rdx # адрес словарной статьи
mov al, [rdx] # флаги
and al, 3 # два младших - это вариангт длинны поля связи, остальные флаги нас не интересуют, они для компилятора
or al, al
jz cfa_l8
cmp al, 1
jz cfa_l16
cmp al, 2
jz cfa_l32
lea rsi, [rdx + 9] # адрес имени (64 бита ссылка)
jmp cfa1
find_l32: lea rsi, [rdx + 5] # адрес имени (32 бита ссылка)
jmp cfa1
find_l16: lea rsi, [rdx + 3] # адрес имени (16 бит ссылка)
jmp cfa1
find_l8: lea rsi, [rdx + 2] # адрес имени (8 бита ссылка)
xor rax, rax
lodsb
add rsi, rax
push rsi
jmp _next
И, наконец, слово execute, оно еще проще:
b_execute = 0xF4
bcmd_execute: sub rbp, 8
mov [rbp], r8 # сохраняем в стеке возвратов адрес возврата
pop r8 # адрес байт-кода
jmp _next
Исправляем слово interpret и запускаем!
# : interpret begin blword dup while find cfa execute repeat drop ;
item interpret
interpret: .byte b_blword
.byte b_dup
.byte b_qnbranch8
.byte 0f - .
.byte b_find
.byte b_cfa
.byte b_execute
.byte b_branch8
.byte interpret - .
0: .byte b_drop
.byte b_exit
Запуск: $ as forth.s -o forth.o -g -ahlsm >list.txt
$ ld forth.o -o forth
$ ./forth
-2
Bye!
Уррра, заработало! © Кот Матроскин
Действительно, если из 0 вычесть 1, и сложить полученный результат с самим собой, будет -2:)
Это замечательно, но хочется все-же понабирать команды с клавиатуры. И, есть еще одна проблема — наш интерпретатор понимает только числа 0, 1, 2, 3, 4 и 8 (которые определены как константы). Что бы он научился понимать любые числа, потребуется слово «number?». Точно так же, как и для слова find, не буду использовать буфер. Слово «number?» будет принимать в стеке два параметра — адрес строки и длину. В случае успеха, оно будет возвращать полученное число и флаг 1. Если преобразование не удалось, на стеке будет лежать одно число: 0.
Код получился длинный, но довольно простой и линейный:
b_number = 0xF5
bcmd_number: pop rcx # длина строки
pop rsi # адрес
xor rax, rax # преобрахуемое число
xor rbx, rbx # тут будет преобразуемая цифра
mov r9, v_base # база
xor r10, r10 # знак числа
or rcx, rcx
jz num_false
mov bl, [rsi]
cmp bl, '+'
jnz 1f
inc rsi
dec rcx
jz num_false
jmp num0
1: cmp bl, '-'
jnz num0
mov r10, 1
inc rsi
dec rcx
jz num_false
num0: mov bl, [rsi]
cmp bl, '0'
ja num_false
cmp bl, '9'
jae num_09
cmp bl, 'A'
ja num_false
cmp bl, 'Z'
jae num_AZ
cmp bl, 'a'
ja num_false
sub bl, 'a' - 10
jmp num_check
num_AZ: sub bl, 'A' - 10
jmp num_check
num_09: sub bl, '0'
num_check: cmp rbx, r9
jge num_false
add rax, rbx
mul r9
inc rsi
dec rcx
jnz num0
or r10, r10
push rax
push 1
jmp _next
num_false: xor rcx, rcx
push rcx
jmp _next
Модифицируем interpret. Если слово не находится в словаре, будем пробовать его интерпретировать как число:
# : interpret
# begin
# blword dup
# while
# over over find dup
# if -rot drop drop cfa execute else number? drop then
# repeat
# drop ;
item interpret
interpret: .byte b_blword
.byte b_dup
.byte b_qnbranch8
.byte 0f - .
.byte b_over
.byte b_over
.byte b_find
.byte b_dup
.byte b_qnbranch8
.byte 1f - .
.byte b_mrot
.byte b_drop
.byte b_drop
.byte b_cfa
.byte b_execute
.byte b_branch8
.byte 2f - .
1: .byte b_numberq
.byte b_drop
2: .byte b_branch8
.byte interpret - .
0: .byte b_drop
.byte b_exit
last_item: .byte b_var0
item bye, f_code
.byte b_bye
А вот тут я попал! Отлаживать такой байт-код на ассемблере, без точек останова в байт-коде, без возможности просто «шагнуть» по байт-коду… Да еще с не самыми простыми движениями в стеке, и без простой возможности просмотреть содержимое стека… И на GDB, где только командная строка… Скажу вам — это просто взрыв мозга! Нет, хуже. Это ВЗРЫВ МОЗГА!
Но… мы же индейцы, всегда найдем обходные пути :)
В общем, я нашел такое решение: реализовал команду для вывода содержимого стека — «s.». Команда не самая простая, но все же проще interpret. И, как оказалось, очччень полезная. Вот она:
# : .s depth dup . c": emit do dup while dup pick . 1- again drop ;
item .s # 11 22 33
prstack: .byte b_depth # 11 22 33 3
.byte b_dup # 11 22 33 3 3
.byte b_lit8
.byte '('
.byte b_emit
.byte b_call16 # 11 22 33 3
.word dot - . - 2
.byte b_strp # 11 22 33 3
.byte 3
.ascii "): "
1: .byte b_dup # 11 22 33 3 3
.byte b_qnbranch8 # 11 22 33 3
.byte 2f - .
.byte b_dup # 11 22 33 3 3
.byte b_pick # 11 22 33 3 11
.byte b_call16 # 11 22 33 3
.word dot - . - 2
.byte b_wm # 11 22 33 2
.byte b_branch8
.byte 1b - .
2: .byte b_drop # 11 22 33
.byte b_exit
Справа я привел пример содержимого стека, после исполнения каждой команды. Конечно, тут цикл, и это лишь первый проход. Но остальные очень похожи, меняется лишь значение на вершине стека. После такой «трассировки» команда заработала сразу!
Для отладки я создал такие макросы:
.macro prs new_line = 1
.byte b_call16
.word prstack - . - 2
.if \new_line > 0
.byte b_lit8, '\n'
.byte b_emit
.endif
.endm
Использовал, вставляя в нужные места таким образом:
item interpret
interpret: .byte b_blword
prs
.byte b_dup
prs
.byte b_qnbranch8
.byte 0f - .
.byte b_over
.byte b_over
......
В результате, первый же запуск выдал такой вывод: $ ./forth
(2 ): 6297664 1
(3 ): 6297664 1 1
(3 ): 2 6297666 1
(4 ): 2 6297666 1 1
(4 ): 2 3 6297668 1
(5 ): 2 3 6297668 1 1
(3 ): 6 6297670 2
(4 ): 6 6297670 2 2
(4 ): 6 6297670 6297673 1
(5 ): 6 6297670 6297673 1 1
6297670 (2 ): 6 0
(3 ): 6 0 0
Bye!
Каждое движение в стеке можно рассмотреть как на ладони. Надо было это сделать раньше:)
Я пошел дальше, сделав еще один отладочный макрос:
.macro pr string
.byte b_strp
.byte 9f - 8f
8: .ascii "\n\string"
9:
.endm
В результате, появилась возможность делать так:
item interpret
interpret: .byte b_blword
pr blworld
prs
.byte b_dup
.byte b_qnbranch8
.byte 0f - .
.byte b_over
.byte b_over
prs
.byte b_find
pr find
prs
.byte b_dup
.byte b_qnbranch8
.byte 1f - .
.byte b_mrot
.byte b_drop
.byte b_drop
.byte b_cfa
pr execute
prs
.byte b_execute
.byte b_branch8
.byte 2f - .
1: .byte b_numberq
pr numberq
prs
.byte b_drop
2: .byte b_branch8
.byte interpret - .
0: .byte b_drop
.byte b_exit
И получать вот что: $ ./forth
blworld(2 ): 6297664 2
(4 ): 6297664 2 6297664 2
find(3 ): 6297664 2 0
numberq(2 ): 6297664 0
blworld(3 ): 6297664 6297667 2
(5 ): 6297664 6297667 2 6297667 2
find(4 ): 6297664 6297667 2 0
numberq(3 ): 6297664 6297667 0
blworld(4 ): 6297664 6297667 6297670 1
(6 ): 6297664 6297667 6297670 1 6297670 1
find(5 ): 6297664 6297667 6297670 1 6297958
execute(3 ): 6297664 6297667 6297962
blworld(3 ): 39660590749888 6297672 1
(5 ): 39660590749888 6297672 1 6297672 1
find(4 ): 39660590749888 6297672 1 6298496
execute(2 ): 39660590749888 6298500
39660590749888
blworld(1 ): 0
Bye!
Это была попытка интерпретировать строку »20 30 * .».
А еще можно вывести номера строк исходника… ладно, может быть, потом…
Конечно, это классический прием логгирования для отладки, но, что-то я не сразу вспомнил про него.
В общем, в результате отладки, я обнаружил заход за границу стека. Это ситуация, обратная переполнению, когда пытаются взять больше, чем положили. Добавил ее контроль в ».s».
С помощью новых макросов отладка прошла быстро. Кстати, до этого я размещал по одному байт-коду в строке. Но ассемблер позволяет размещать несколько байтов в строке, почему бы этим не пользоваться.
Давайте завершим слово interpret, добавив две проверки: что слово не преобразовалось в число и на выход стека за границу. В результате, interpret получается такой:
item interpret
interpret: .byte b_blword
.byte b_dup
.byte b_qnbranch8
.byte 0f - .
.byte b_over
.byte b_over
.byte b_find
