Главная » Хабрахабр » [Из песочницы] Байт-машина для форта (и не только) по-индейски

[Из песочницы] Байт-машина для форта (и не только) по-индейски

image

Начну по порядку. Да-да, именно «байт» и именно по индейски (не по индийски). А когда-то давным-давно я развлекался тем, что писал форт-системы. В последнее время тут, на Хабре, стали появляться статьи о байт-коде. Они были 16-ти разрядными. Конечно, на ассемблере. Даже с 32 поиграться не удалось. На x86-64 никогда не программировал. Почему бы не замутить 64х разрядный форт, да ещё с байт-кодом? Вот и пришла такая мысль — а почему бы нет? Да еще и на Linux, где я тоже ничего системного не писал.

В общем, я немного погуглил и узнал, что ассемблер на Linux называется GAS, а команда as. У меня есть домашний сервер с Linux. Он у меня уже установлен. Подключаюсь по SSH к серверу, набираю as — есть! Вот так, и попробуем написать что-нибудь интересное на ассемблере. Ещё нужен компоновщик, набираю ld — есть! Редактор будет Nano, который висит у меня на F4 в mc. Без цивилизации, только лес, как у настоящих индейцев 🙂 Без среды разработки, только командная строка и Midnight Commander. Настоящему индейцу нужно только одного… Что еще нужно настоящему индейцу? Как там поет группа «Ноль»? Набираем gdb — есть! Конечно, отладчик. Ну что же, нажмем Shift+F4, и вперед!

Архитектура

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

Значит, у нас будет таблица, содержащая 256 адресов — по одному для каждой байт-команды. Попробуем сделать максимально быструю стековую байт-машину (но без JIT). А нам нужно быстро, без компромиссов. Меньше никак — лишняя проверка, это уже 1-2 команды процессора.

Стеки

Обычно, в реализациях форта стек возвратов процессора (*SP) используют как стек данных, а стек возвратов реализуют другими средствами. Действительно, у нас машина будет стековая, и основная работа идет на стеке данных. Поэтому, сделаем так же — RSP будет стек данных. Ну а стек возвратов пусть будет RBP, который так же, по умолчанию, работает с сегментом стека. Таким образом, у нас будет три сегмента памяти: сегмент кода, сегмент данных и сегмент стеков (в нем будет и стек данных, и стек возвратов).

Регистры

Захожу в описание регистров x86-64, и упс! Тут есть еще целых 8 дополнительных регистров общего назначения (R8 — R16), по сравнению с режимами разрядности 32 или 16. Неплохо…

Еще нужен указатель (счетчик) команд байт-кода. Уже определились, что будут нужны RSP и RBP. Основные регистры (RAX, RBX, RCX, RDX, RSI, RDI) более гибки, универсальны, с ними существует множество специальных команд. Из операций по этому регистру нужно только чтение памяти. Они нам пригодятся для различных задач, а для счетчика команд байт-кода возьмем один из новых для меня регистров, пусть это будет R8.

Начнем?

У меня нет опыта программирования под Linux на ассемблере. Поэтому, для начала, найдем готовый «Hello, world», что бы понять, как программа стартует и выводит текст. Неожиданно для меня, я нашел варианты со странным синтаксисом, где даже источник и приемник переставлены местами. Как оказалось, это AT&T-синтаксис, и на нем, в основном, и пишут под Linux. Но, поддерживается и другой вариант синтаксиса, он называется Intel-синтаксис. Подумав, я решил использовать все же его. Ну что ж, пишем в начале .intel_syntax noprefix.

Путем чтения хелпа и экспериментов я стал использовать для компиляции такую команду:
$ as fort.asm -o fort.o -g -ahlsm >list.txt
Тут ключ -o указывает файл результата, ключ -g предписывает генерировать отладочную информацию, а ключ -ahlsm задает формат листинга. Скомпилируем и исполним «Hello, world», что бы убедиться, что все работает. Признаюсь, в начале работы я не делал листинг, и даже не указывал ключ -g. А вывод сохраняю в листинг, в нем можно увидеть много полезного. Ключ -g я стал использовать после первого применения отладчика, а делать листинг стал после того, как в коде появились макросы 🙂

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

$ ld forth.o -o forth
Ну и запускаем!
$ ./forth
Hello, world!

Работает.

Вот такой был первый forth.asm (на самом деле это 'Hellow, world!', конечно)

.intel_syntax noprefix
.section .data
msg:
.ascii "Hello, world!\n"
len = . - msg # символу len присваивается длина строки
.section .text
.global _start # точка входа в программу
_start: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, OFFSET FLAT:msg # указатель на выводимую строку mov edx, len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit xor ebx, ebx # выход с кодом 0 int 0x80 # вызов ядра

Кстати, чуть позже узнал, что в x86-64 для системного вызова правильнее использовать syscall, а не int 0x80. Вызов 0x80 считается для этой архитектуры устаревшим, хотя поддерживается.

Начало положено, а теперь…

Поехали!

Что бы была хоть какая-то конкретика, напишем код одной байт-команды. Пусть, это будет фортовское слово «0», кладущее 0 на вершину стека:

bcmd_num0: push 0 jmp _next

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

Тут мне пришлось изрядно покопаться в новой для меня системе команд x86-64. Но… какой разрядности будет таблица адресов байт-команд? Значит, либо вычислять адрес, либо адрес будет готовый — 64 бита. Увы, я не нашел команд, которые позволяют перейти по смещению в памяти. В этом случае размер таблицы будет 256 * 8 = 4096 байт. Вычислять нам некогда, значит — 64 бита. Ну и закодируем, наконец, вызов _next:

_next: movzx rcx, byte ptr [r8] inc r8 jmp [bcmd + rcx*8] # bcmd - таблица адресов байт-команд

Неплохо, как мне кажется… Всего три команды процессора, при переходе от одной байт-команды до другой.

Пришлось снова копаться в системе комманд 0x86-64 и найти новую для меня команду MOVZX. На самом деле, мне не так просто дались эти команды. Есть два варианта этой команды: беззнаковый, где старшие разряды дополняются нулями, и знаковый — MOVSX. Фактически, эта команда конвертирует значение размера 8, 16 или 32 бита в регистр 64 бита. Этот вариант еще нам пригодится для байт-команды lit. В знаковом варианте расширяется знак, то есть, для положительных чисел в старшие разряды пойдут нули, а для отрицательных — единицы.

Возможно, кто-то предложит еще быстрее? Кстати, действительно ли этот вариант самый быстрый?

Надо ее испытать в деле, заставить выполнить хотя бы одну команду. Ну что ж, у нас теперь есть байт-машина, которая умеет бежать по последовательности байт-команд и выполнять их. Ноль в стек? Только вот какую? Но тут даже не узнать результат, если не смотреть стек под отладчиком… Но если программа стартовала, ее можно завершить 🙂

Напишем команду bye, которая завершает выполнение программы и пишет об этом, тем более, у нас есть «Hellow, world!».

bcmd_bye: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bye # указатель на выводимую строку mov edx, msg_bye_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 0 # выход с кодом 0 int 0x80 # вызов ядра

Остается дело за малым — создать таблицу адресов байт-комманд, инициализировать регистры, и запустить байт-машину. Так… в таблице 256 значений, а команд две. Что в остальные ячейки?
В остальных будет недопустимый код операции. Но, проверку на него делать нельзя, это лишние команды, у нас сейчас три, а с проверкой станет пять. Значит, сделаем такую команду-заглушку — плохая команда. Заполним вначале ей всю таблицу, а потом начнем занимать ячейки полезными командами. Пусть у плохой команды будет код 0x00, у команды bye — 0x01, а у '0' будет код 0x02, раз уже она написана. Плохая команда пока будет делать то же самое, что и bye, только с другим кодом завершения и текстом (положу в спойлер, почти то же, что и bye):

bcmd_bad

bcmd_bad: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bad_byte # указатель на выводимую строку mov edx, msg_bad_byte_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 1 # выход с кодом 1 int 0x80 # вызов ядра

Теперь нарисуем таблицу адресов. Для удобства, разместим по восемь в каждой строке, строк будет 16. Таблица получается довольно большая по размеру:

Таблица адресов байт-команд

bcmd:
.quad bcmd_bad, bcmd_bye, bcmd_num0, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad

Напишем тело байт-программы. Для этого присвоим коды команд переменным ассемблера. У нас будет следующие соглашения:

  • Адреса для исполнения байт-команд будут начинаться на bcmd_
  • Сами коды команд будут храниться в переменных, начинающихся с b_

Таким образом, тело байт-программы будет таким:

start: .byte b_bye

Объявим размер стека данных, как stack_size. Пусть будет пока 1024. При инициализации, сделаем RBP = RSP — stack_size.

Собственно, получаем такой код программы (forth.asm)


.intel_syntax noprefix stack_size = 1024 .section .data msg_bad_byte:
.ascii "Bad byte code!\n"
msg_bad_byte_len = . - msg_bad_byte # символу len присваевается длина строки msg_bye:
.ascii "bye!\n"
msg_bye_len = . - msg_bye msg_hello:
.ascii "Hello, world!\n"
msg_hello_len = . - msg_hello bcmd:
.quad bcmd_bad, bcmd_bye, bcmd_num0, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad start: .byte b_bye .section .text
.global _start # точка входа в программу _start: mov rbp, rsp sub rbp, stack_size lea r8, start jmp _next _next: movzx rcx, byte ptr [r8] inc r8 jmp [bcmd + rcx*8] b_bad = 0x00
bcmd_bad: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bad_byte # указатель на выводимую строку mov edx, msg_bad_byte_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 1 # выход с кодом 1 int 0x80 # вызов ядра b_bye = 0x01
bcmd_bye: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bye # указатель на выводимую строку mov edx, msg_bye_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 0 # выход с кодом 0 int 0x80 # вызов ядра b_num0 = 0x02
bcmd_num0: push 0 jmp _next

Компилируем, запускаем:

Запустилась наша первая программа на байт-коде из одного байта 🙂
Конечно, так будет, если все сделано правильно. $ as fort.asm -o fort.o -g -ahlsm >list.txt
$ ld forth.o -o forth
$ ./forth
bye!

Работает! А если нет, то результат, скорее всего, будет такой:

И нам понадобиться отладчик. $ ./forth
Ошибка сегментирования

Конечно, возможны и другие варианты, но с таким я сталкивался наиболее часто.

Лирическое отступление про отладчик

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

$ gdb ./forth
GNU gdb (Ubuntu 7.11.1-0ubuntu1~16.5) 7.11.1
Copyright (C) 2016 Free Software Foundation, Inc.
License GPLv3+: GNU GPL version 3 or later <http://gnu.org/licenses/gpl.html>
This is free software: you are free to change and redistribute it.
There is NO WARRANTY, to the extent permitted by law. Type "show copying"
and "show warranty" for details.
This GDB was configured as "x86_64-linux-gnu".
Type "show configuration" for configuration details.
For bug reporting instructions, please see:
<http://www.gnu.org/software/gdb/bugs/>.
Find the GDB manual and other documentation resources online at:
<http://www.gnu.org/software/gdb/documentation/>.
For help, type "help".
Type "apropos word" to search for commands related to "word"...
Reading symbols from ./forth...done.
(gdb)

Далее, вводя команды, производим отладку. Мне хватило часа, что бы найти несколько нужных команд и научиться использовать их для отладки. Вот они:
b — поставить точку останова
l — посмотреть исходный код
r — старт или рестарт программы
i r — посмотреть состояние регистров процессора
s — шаг

Иначе, метки и исходный код будут недоступны. Кстати, помним, что компилировать программу надо с ключом -g? Мы, конечно, индейцы, но не до такой же степени... В этом случае можно будет отлаживать только по дизассемблированному коду и использовать адреса в памяти.

Но как-то совсем мало делает программа. Мы ей только «Привет», а она сразу «Пока!». Давайте сделаем настоящий «Hello, world!» на байт-коде. Для этого положим на стек адрес и длину строки, затем выполним команду, выводящую строку, а после команду bye. Что бы сделать все это, потребуются новые команды: type для вывода строки, и lit для того, что бы положить адрес и длину строки. В начале напишем type, пусть ее код будет 0x80. Нам, снова, понадобиться тот кусочек кода с вызовом sys_write:

b_type = 0x80
bcmd_type: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout pop rdx pop rcx push r8 int 0x80 # вызов ядра pop r8 jmp _next

Здесь мы адрес и длину строки берем из стека данных командами POP. Вызов int 0x80 может менять регистр R8, поэтому сохраняем его. Раньше мы так не делали, потому что программа завершалась. На содержимое этих регистров было плевать. Теперь же это обычная байт-команда, после которой продолжается выполнение байт-кода, и надо вести себя хорошо.

Это будет первая наша команда с параметрами. Теперь напишем команду lit. Сразу возникает вопрос — а какая разрядность тут нужна? После байта с кодом этой команды, будут идти байты, содержащие число, которое она положит в стек. Но, каждый раз команда будет занимать 5 байт, что бы положить одно число? Что бы можно было положить любое число, нужно 64 бита. Так мы теряем компактность, одно из главных свойств байт-кода, да и фортовского кода тоже…

Это будут lit8, lit16, lit32 и lit64. Выход простой — сделаем несколько команд для разной разрядности. Наиболее часто используются маленькие числа, и для них будет самая короткая команда, которая занимает два байта. Для маленьких чисел будем использовать lit8 и lit16, для боьших — lit32 и lit64. Коды этих команд сделаем 0x08 — 0x0B. Неплохо!..


b_lit8 = 0x08
bcmd_lit8: movsx rax, byte ptr [r8] inc r8 push rax jmp _next b_lit16 = 0x09
bcmd_lit16: movsx rax, word ptr [r8] add r8, 2 push rax jmp _next b_lit32 = 0x0A
bcmd_lit32: movsx rax, dword ptr [r8] add r8, 4 push rax jmp _next b_lit64 = 0x0B
bcmd_lit64: mov rax, [r8] add r8, 8 push rax jmp _next

Тут используем команду MOVSX — это знаковый вариант уже известной нам команды MOVZX. R8 у нас счетчик байт-команд. Загружаем по нему значение нужного размера, передвигаем его на следующую команду, а сконвертированное до 64 бит значение кладем в стек.

Не забудем занести адреса новых команд в таблицу на нужные позиции.

Поработаем компилятором! Вот и все готово, что бы написать свою первую программу «Hello, world!» на нашем байт-коде. 🙂

start: .byte b_lit64 .quad msg_hello .byte b_lit8 .byte msg_hello_len .byte b_type .byte b_bye

Используем две разных команды lit: lit64, что бы положить в стек адрес строки, и lit8, с помощью которой помещаем в стек длину. Дальше выполняем еще две байт-команды: type и bye.
Компилируем, запускаем:

$ as fort.asm -o fort.o -g -ahlsm >list.txt
$ ld forth.o -o forth
$ ./forth
Hello, world!
bye!

Заработал наш байт-код! Именно такой результат должен быть, если все нормально.

Полный исходник


.intel_syntax noprefix stack_size = 1024 .section .data msg_bad_byte:
.ascii "Bad byte code!\n"
msg_bad_byte_len = . - msg_bad_byte # символу len присвавается длина строки msg_bye:
.ascii "bye!\n"
msg_bye_len = . - msg_bye msg_hello:
.ascii "Hello, world!\n"
msg_hello_len = . - msg_hello bcmd:
.quad bcmd_bad, bcmd_bye, bcmd_num0, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x00
.quad bcmd_lit8, bcmd_lit16, bcmd_lit32, bcmd_lit64, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x10
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x20
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x30
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x40
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x60
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_type, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x80
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad start: .byte b_lit64 .quad msg_hello .byte b_lit8 .byte msg_hello_len .byte b_type .byte b_bye .section .text
.global _start # точка входа в программу _start: mov rbp, rsp sub rbp, stack_size lea r8, start jmp _next _next: movzx rcx, byte ptr [r8] inc r8 jmp [bcmd + rcx*8] b_bad = 0x00
bcmd_bad: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bad_byte # указатель на выводимую строку mov edx, msg_bad_byte_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 1 # выход с кодом 1 int 0x80 # вызов ядра b_bye = 0x01
bcmd_bye: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bye # указатель на выводимую строку mov edx, msg_bye_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 0 # выход с кодом 0 int 0x80 # вызов ядра b_num0 = 0x02
bcmd_num0: push 0 jmp _next b_lit8 = 0x08
bcmd_lit8: movsx rax, byte ptr [r8] inc r8 push rax jmp _next b_lit16 = 0x09
bcmd_lit16: movsx rax, word ptr [r8] add r8, 2 push rax jmp _next b_lit32 = 0x0A
bcmd_lit32: movsx rax, dword ptr [r8] add r8, 4 push rax jmp _next b_lit64 = 0x0B
bcmd_lit64: mov rax, [r8] add r8, 8 push rax jmp _next b_type = 0x80
bcmd_type: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout pop rdx pop rcx push r8 int 0x80 # вызов ядра pop r8 jmp _next

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

Можно, все в наших руках! Как нельзя? Для этого потребуется команда условного перехода, а так же немного стековой арифметики: команда, уменьшающая значение на стеке на 1 (на форте «1-») и команда дублирования вершины («dup»). Сделаем-ка мы вывод этой строчки в цикле, 10 раз.

С арифметикой все просто, даже не буду комментировать:

b_dup = 0x18
bcmd_dup: push [rsp] jmp _next b_wm = 0x20
bcmd_wm: decq [rsp] jmp _next

Теперь условный переход. Для начала, сделаем задачу попроще — безусловный переход. Понятно, что нужно просто изменить значение регистра R8. Первое, что приходит в голову — это будет байт-команда, за которой лежит параметр — адрес перехода 64 бита. Опять пять байт. А нужны ли нам эти пять байт? Переходы обычно происходят на короткие расстояния, часто в пределах нескольких сотен байт. Значит, будем использовать не адрес, а смещение!

Во многих случаях хватит 8 бит (127 вперед/назад), но иногда этого будет мало. Разрядность? Поэтому поступим так же, как с командой lit, сделаем два варианта — 8 и 16 разрядов, коды команд будут 0x10 и 0x11:

b_branch8 = 0x10
bcmd_branch8: movsx rax, byte ptr [r8] add r8, rax jmp _next b_branch16 = 0x11
bcmd_branch16: movsx rax, word ptr [r8] add r8, rax jmp _next

Теперь условный переход реализовать совсем просто. Если на стеке 0, идем в _next, а если нет — переходим в команду branch!

b_qbranch8 = 0x12
bcmd_qbranch8: pop rax or rax, rax jnz bcmd_branch8 inc r8 jmp _next b_qbranch16 = 0x13
bcmd_qbranch16: pop rax or rax, rax jnz bcmd_branch16 add r8, 2 jmp _next

Теперь у нас есть все, что бы сделать цикл:

start: .byte b_lit8 .byte 10 #счетчик повторений #тело цикла
m0: .byte b_lit64 .quad msg_hello .byte b_lit8 .byte msg_hello_len .byte b_type .byte b_wm .byte b_dup .byte b_qbranch8 .byte m0 - . .byte b_bye

Первые две команды — кладем на стек счетчик цикла. Далее выводим строку Hello. Затем вычитаем 1 из счетчика, дублируем его и выполняем (или не выполняем) переход. Команда дублирования нужна потому, что команда условного перехода забирает значение с вершины стека. Переход тут используется восьмиразрядный, так как расстояние всего несколько байт.

Помещаем адреса новых команд в таблицу, компилируем и выполняем.

Помещу в спойлер, а то наша программа стала многословной)

$ as fort.asm -o fort.o -g -ahlsm >list.txt
$ ld forth.o -o forth
$ ./forth
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
bye!

Отлично, условия и циклы мы уже делать можем!

Полный исходник


.intel_syntax noprefix stack_size = 1024 .section .data msg_bad_byte:
.ascii "Bad byte code!\n"
msg_bad_byte_len = . - msg_bad_byte # символу len присваевается длина строки msg_bye:
.ascii "bye!\n"
msg_bye_len = . - msg_bye msg_hello:
.ascii "Hello, world!\n"
msg_hello_len = . - msg_hello bcmd:
.quad bcmd_bad, bcmd_bye, bcmd_num0, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x00
.quad bcmd_lit8, bcmd_lit16, bcmd_lit32, bcmd_lit64, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_branch8, bcmd_branch16, bcmd_qbranch8, bcmd_qbranch16, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x10
.quad bcmd_dup, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_wm, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x20
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x30
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x40
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x60
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_type, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x80
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad start: .byte b_lit8 .byte 10 #счетчик повторений #тело цикла
m0: .byte b_lit64 .quad msg_hello .byte b_lit8 .byte msg_hello_len .byte b_type .byte b_wm .byte b_dup .byte b_qbranch8 .byte m0 - . .byte b_bye .section .text
.global _start # точка входа в программу _start: mov rbp, rsp sub rbp, stack_size lea r8, start jmp _next _next: movzx rcx, byte ptr [r8] inc r8 jmp [bcmd + rcx*8] b_bad = 0x00
bcmd_bad: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bad_byte # указатель на выводимую строку mov edx, msg_bad_byte_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 1 # выход с кодом 1 int 0x80 # вызов ядра b_bye = 0x01
bcmd_bye: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bye # указатель на выводимую строку mov edx, msg_bye_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 0 # выход с кодом 0 int 0x80 # вызов ядра b_num0 = 0x02
bcmd_num0: push 0 jmp _next b_lit8 = 0x08
bcmd_lit8: movsx rax, byte ptr [r8] inc r8 push rax jmp _next b_lit16 = 0x09
bcmd_lit16: movsx rax, word ptr [r8] add r8, 2 push rax jmp _next b_lit32 = 0x0A
bcmd_lit32: movsx rax, dword ptr [r8] add r8, 4 push rax jmp _next b_lit64 = 0x0B
bcmd_lit64: mov rax, [r8] add r8, 8 push rax jmp _next b_type = 0x80
bcmd_type: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout pop rdx pop rcx push r8 int 0x80 # вызов ядра pop r8 jmp _next b_dup = 0x18
bcmd_dup: push [rsp] jmp _next b_wm = 0x20
bcmd_wm: decq [rsp] jmp _next b_branch8 = 0x10
bcmd_branch8: movsx rax, byte ptr [r8] add r8, rax jmp _next b_branch16 = 0x11
bcmd_branch16: movsx rax, word ptr [r8] add r8, rax jmp _next b_qbranch8 = 0x12
bcmd_qbranch8: pop rax or rax, rax jnz bcmd_branch8 inc r8 jmp _next b_qbranch16 = 0x13
bcmd_qbranch16: pop rax or rax, rax jnz bcmd_branch16 add r8, 2 jmp _next

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

Тут впервые нам потребуется стек возвратов. Доведем работу до конца. Команды нужны две — команда вызова и команда возврата (call и exit).

Но, в отличие от branch, нужно еще сохранить адрес возврата в стеке возвратов, что бы можно было вернуться и продолжить выполнение. Команда call, в принципе, делает то же самое, что и branch — передает управление на другой кусочек байт-кода. Поэтому сделаем команду call по подобию branch, но в трех вариантах — 8, 16 и 32 бита. Есть и еще отличие — такие вызовы могут происходить на гораздо большие расстояния.

b_call8 = 0x0C
bcmd_call8: movsx rax, byte ptr [r8] sub rbp, 8 inc r8 mov [rbp], r8 add r8, rax jmp _next b_call16 = 0x0D
bcmd_call16: movsx rax, word ptr [r8] sub rbp, 8 add r8, 2 mov [rbp], r8 add r8, rax jmp _next b_call32 = 0x0E
bcmd_call32: movsx rax, dword ptr [r8] sub rbp, 8 add r8, 4 mov [rbp], r8 add r8, rax jmp _next

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

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

Собственно, ее дело лишь восстановить R8 из стека возвратов и передать дальше управление байт-машине: Теперь команда возврата.

b_exit = 0x1F
bcmd_exit: mov r8, [rbp] add rbp, 8 jmp _next

Эти команды будут применяться очень часто, и оптимизировать их нужно по максимуму. Байт-команда exit занимает три машинных команды. Можно ли тут что-то сократить? Оказывается, можно! Можно просто убрать команду перехода 🙂

Для этого разместим ее над точкой входа байт-машины _next:

b_exit = 0x1F
bcmd_exit: mov r8, [rbp] add rbp, 8 _next: movzx rcx, byte ptr [r8] inc r8 jmp [bcmd + rcx*8]

Кстати, наиболее важные и часто используемые команды (например, такие как call) нужно разместить ближе к байт-машине, что бы компилятор мог сформировать команду короткого перехода. Это хорошо видно в листинге. Вот пример.

262 0084 490FBE00 bcmd_lit8: movsx rax, byte ptr [r8] 263 0088 49FFC0 inc r8 264 008b 50 push rax 265 008c EB90 jmp _next 266 267 b_lit16 = 0x09 268 008e 490FBF00 bcmd_lit16: movsx rax, word ptr [r8] 269 0092 4983C002 add r8, 2 270 0096 50 push rax 271 0097 EB85 jmp _next 272 273 b_lit32 = 0x0A 274 0099 496300 bcmd_lit32: movsx rax, dword ptr [r8] 275 009c 4983C004 add r8, 4 276 00a0 50 push rax 277 00a1 E978FFFF jmp _next 277 FF 278

Тут в строке 265 и 271 команда jmp занимает по 2 байта, а в строке 277 та же команда компилируется уже в 5 байт, так как расстояние перехода превысило возможное для короткой команды.

К сожалению, в переход 127 байт уместить можно не так много.
Новые команды добавим в таблицу адресов команд, согласно их кодам. Поэтому байт-команды, такие, как bad, bye, type переставим дальше, а такие, как call, branch, lit — ближе.

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

start: .byte b_lit8 .byte 3 #счетчик повторений #тело цикла
m0: .byte b_call16 .word sub_hello - . - 2 .byte b_call16 .word sub_hello - . - 2 .byte b_wm .byte b_dup .byte b_qbranch8 .byte m0 - . .byte b_bye sub_hello: .byte b_lit64 .quad msg_hello .byte b_lit8 .byte msg_hello_len .byte b_type .byte b_exit

Тут можно было использовать и call8, но я решил применить call16, как наиболее вероятно используемую. Значение 2 вычитается из-за особенности вычисления адреса для байт-команды call, о которой я писал. Для call8 тут будет вычитаться 1, для call32, соответственно, 4.
Компилируем и вызываем:

$ as forth.asm -o forth.o -g -ahlsm>list.txt
$ ld forth.o -o forth
$ ./forth
Hello, world!
Bad byte code!

Упс… как говориться, что-то пошло не так 🙂 Ну что ж, запускаем GDB и смотрим что там твориться. Точку останова я поставил сразу на bcmd_exit, так как видно, что вызов sub_hello проходит, и тело процедуры исполняется… запустил… и в точку останова программа не попала. Сразу возникло подозрение на код байт-команды. И, действительно, причина была в нем. b_exit я присвоил значение 0x1f, а сам адрес разместил в ячейке таблицы номер 0x17. Ну что же, исправлю значение b_exit на 0x17 и пробуем снова выполнить:

$ as forth.asm -o forth.o -g -ahlsm>list.txt
$ ld forth.o -o forth
$ ./forth
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
Hello, world!
bye!

Ровно шесть раз здоровается, и один раз прощаеться. Как и должно быть 🙂

Полный исходник


.intel_syntax noprefix stack_size = 1024 .section .data msg_bad_byte:
.ascii "Bad byte code!\n"
msg_bad_byte_len = . - msg_bad_byte # символу len присваевается длина строки msg_bye:
.ascii "bye!\n"
msg_bye_len = . - msg_bye msg_hello:
.ascii "Hello, world!\n"
msg_hello_len = . - msg_hello bcmd:
.quad bcmd_bad, bcmd_bye, bcmd_num0, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x00
.quad bcmd_lit8, bcmd_lit16, bcmd_lit32, bcmd_lit64, bcmd_call8, bcmd_call16, bcmd_call32, bcmd_bad
.quad bcmd_branch8, bcmd_branch16, bcmd_qbranch8, bcmd_qbranch16, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_exit # 0x10
.quad bcmd_dup, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_wm, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x20
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x30
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x40
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad .quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x60
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_type, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad # 0x80
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad
.quad bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad, bcmd_bad start: .byte b_lit8 .byte 3 #счетчик повторений #тело цикла
m0: .byte b_call16 .word sub_hello - . - 2 .byte b_call16 .word sub_hello - . - 2 .byte b_wm .byte b_dup .byte b_qbranch8 .byte m0 - . .byte b_bye sub_hello: .byte b_lit64 .quad msg_hello .byte b_lit8 .byte msg_hello_len .byte b_type .byte b_exit .section .text
.global _start # точка входа в программу _start: mov rbp, rsp sub rbp, stack_size lea r8, start jmp _next b_exit = 0x17
bcmd_exit: mov r8, [rbp] add rbp, 8 _next: movzx rcx, byte ptr [r8] inc r8 jmp [bcmd + rcx*8] b_num0 = 0x02
bcmd_num0: push 0 jmp _next b_lit8 = 0x08
bcmd_lit8: movsx rax, byte ptr [r8] inc r8 push rax jmp _next b_lit16 = 0x09
bcmd_lit16: movsx rax, word ptr [r8] add r8, 2 push rax jmp _next b_call8 = 0x0C
bcmd_call8: movsx rax, byte ptr [r8] sub rbp, 8 inc r8 mov [rbp], r8 add r8, rax jmp _next b_call16 = 0x0D
bcmd_call16: movsx rax, word ptr [r8] sub rbp, 8 add r8, 2 mov [rbp], r8 add r8, rax jmp _next b_call32 = 0x0E
bcmd_call32: movsx rax, dword ptr [r8] sub rbp, 8 add r8, 4 mov [rbp], r8 add r8, rax jmp _next b_lit32 = 0x0A
bcmd_lit32: movsx rax, dword ptr [r8] add r8, 4 push rax jmp _next b_lit64 = 0x0B
bcmd_lit64: mov rax, [r8] add r8, 8 push rax jmp _next b_dup = 0x18
bcmd_dup: push [rsp] jmp _next b_wm = 0x20
bcmd_wm: decq [rsp] jmp _next b_branch8 = 0x10
bcmd_branch8: movsx rax, byte ptr [r8] add r8, rax jmp _next b_branch16 = 0x11
bcmd_branch16: movsx rax, word ptr [r8] add r8, rax jmp _next b_qbranch8 = 0x12
bcmd_qbranch8: pop rax or rax, rax jnz bcmd_branch8 inc r8 jmp _next b_qbranch16 = 0x13
bcmd_qbranch16: pop rax or rax, rax jnz bcmd_branch16 add r8, 2 jmp _next b_bad = 0x00
bcmd_bad: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bad_byte # указатель на выводимую строку mov edx, msg_bad_byte_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 1 # выход с кодом 1 int 0x80 # вызов ядра b_bye = 0x01
bcmd_bye: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout mov ecx, offset msg_bye # указатель на выводимую строку mov edx, msg_bye_len # длина строки int 0x80 # вызов ядра mov eax, 1 # системный вызов № 1 — sys_exit mov ebx, 0 # выход с кодом 0 int 0x80 # вызов ядра b_type = 0x80
bcmd_type: mov eax, 4 # системный вызов № 4 — sys_write mov ebx, 1 # поток № 1 — stdout pop rdx pop rcx push r8 int 0x80 # вызов ядра pop r8 jmp _next

Что в итоге

Мы сделали и протестировали законченную и довольно быструю 64-разрядную стековую байт-машину. По скорости, возможно, эта байт-машина будет одной из самых быстрых в своем классе (стековая байт-машина без JIT). Она умеет выполнять команды последовательно, делать условные и безусловные переходы, вызывать процедуры, возвращаться из них. В то же время используемый байт-код обладает достаточной компактностью. В основном, байт-команды занимают 1-3 байта, больше — это очень редко (только числа большого размера, и очень дальние вызовы процедур). Так же набросан небольшой набор байт-команд, который легко расширять. Допустим, все основные команды работы со стеком (drop, swap, over, root и т.д. можно написать минут за 20, столько же уйдет на арифметические целочисленные команды).

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

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

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

Например, сделать таблицу команд 16-ти разрядной, и посмотреть, как это повлияет на быстродействие. Интересно еще по экспериментировать с вариантами. То есть, в конце будет не переход на _next, а содержимое самой точки _next (это 14 байт). Еще можно точку входа _next превратить в макрос, в этом случае машинный код каждой байт-команды увеличиться в размере на две команды (минус переход и плюс три команды из _next). Еще можно попробовать сделать оптимизацию, используя регистры. Интересно узнать, как это повлияет на быстродействие. Можно сделать регистровый вариант и так же по тестировать. Например, стандартный цикл со счетчиком в форте хранит счетчик в стеке возвратов.

Еще можно сделать компилятор выражений, записанных в классической форме (например, A = 5 + (B + C * 4) ).

🙂 В общем, есть простор для экспериментов!


Оставить комментарий

Ваш email нигде не будет показан
Обязательные для заполнения поля помечены *

*

x

Ещё Hi-Tech Интересное!

Векторные представления товаров, или еще одно применение модели Word2Vec

Когда видов товаров тоже много, решить задачу помогает модель Word2Vec. Каждый день полтора миллиона людей ищут на Ozon самые разные товары, и к каждому из них сервис должен подбирать похожие (если пылесос все-таки нужен помощней) или сопутствующие (если к поющему ...

[Перевод] Внутренняя и внешняя линковка в C++

Всем добрый день! Надеемся, что она будет полезна и интересна для вас, как и нашим слушателям. Представляем вам перевод интересной статьи, который подготовили для вас рамках курса «Разработчик C++». Поехали. Хотите узнать, для чего используется ключевое слово extern, или как ...