Байт-машина для форта (и не только) по-индейски (часть 2)

    image

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

    Вообще, я планировал во второй части сделать интерпретатор форта, а в третьей — компилятор форта для этой байт-машины. Но объем, который получался для статьи, оказался очень велик. Что бы сделать интерпретатор, надо расширить ядро (набор байт-команд), и реализовать: переменные, парсинг строк, ввод строк, словари, поиск по словарям… Ну и должен работать хотя бы вывод чисел. В результате, я решил разбить статью об интерпретаторе на две. Поэтому, в этой статье мы расширим ядро, определимся с переменными, сделаем вывод чисел. Дальше примерный план такой: 3-я часть — интерпретатор, 4-я — компилятор. И, конечно же, тесты быстродействия. Они будут в 4-й или 5-й статье. Эти статьи будут уже после нового года.

    А кто еще не испугался страшного ассемблера и байт-кода — добро пожаловать под кат! :)

    Для начала исправим ошибки. Зададим файлу расширение .s, как это принято для GAS (спасибо mistergrim). Затем, заменим int 0x80 на syscall и используем 64-битные регистры (спасибо qw1). В начале я не внимательно прочитал описание вызова и исправил только регистры… и получил Segmentation fault. Оказывается, для syscall поменялось все, в том числе и номера вызовов. sys_write для syscall имеет номер 1, а sys_exit — 60. В итоге, команды bad, type и bye приобрели такой вид:

    b_bad = 0x00
    bcmd_bad:	mov	rax, 1			# системный вызов № 1 - sys_write
    		mov	rdi, 1			# поток № 1 - stdout
    		mov	rsi, offset msg_bad_byte # указатель на выводимую строку
    		mov	rdx, msg_bad_byte_len	# длина строки
    		syscall				# вызов ядра
    		mov	rax, 60			# системный вызов № 1 - sys_exit
    		mov	rbx, 1			# выход с кодом 1
    		syscall				# вызов ядра
    
    b_bye = 0x01
    bcmd_bye:	mov	rax, 1			# системный вызов № 1 - sys_write
    		mov	rdi, 1			# поток № 1 - stdout
    		mov	rsi, offset msg_bye	# указатель на выводимую строку
    		mov	rdx, msg_bye_len	# длина строки
    		syscall				# вызов ядра
    		mov	rax, 60			# системный вызов № 60 - sys_exit
    		mov	rdi, 0			# выход с кодом 0
    		syscall				# вызов ядра
    
    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
    

    И еще один момент. Совершенно справедливо написали в комментариях к прошлой статье berez и fpauk, что, если использовать в байт-коде адреса процессора, то байт-код зависит от платформы. А в том примере адрес строки для «Hello, world!», был задан в байт-коде по значению (командой lit64). Конечно же, так делать не нужно. Но это был самый простой способ проверить байт-машину. Больше я так делать не буду, а адреса переменных буду получать другими средствами: в частности, командой var (об этом чуть позже).

    Разминка


    А сейчас, в качестве разминки, сделаем все основные целочисленные арифметические операции (+, -, *, /, mod, /mod, abs). Они нам понадобятся.

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

    Арифметика
    b_add = 0x21
    bcmd_add:	pop	rax
    		add	[rsp], rax
    		jmp	_next
    
    b_sub = 0x22
    bcmd_sub:	pop	rax
    		sub	[rsp], rax
    		jmp	_next
    
    b_mul = 0x23
    bcmd_mul:	pop	rax
    		pop	rbx
    		imul	rbx
    		push	rax
    		jmp	_next
    
    b_div = 0x24
    bcmd_div:	pop	rbx
    		pop	rax
    		cqo
    		idiv	rbx
    		push	rax
    		jmp	_next
    
    b_mod = 0x25
    bcmd_mod:	pop	rbx
    		pop	rax
    		cqo
    		idiv	rbx
    		push	rdx
    		jmp	_next
    
    b_divmod = 0x26
    bcmd_divmod:	pop	rbx
    		pop	rax
    		cqo
    		idiv	rbx
    		push	rdx
    		push	rax
    		jmp	_next
    
    b_abs = 0x27
    bcmd_abs:	mov	rax, [rsp]
    		or	rax, rax
    		jge	_next
    		neg	rax
    		mov	[rsp], rax
    		jmp	_next
    

    Традиционно, в форте к обычным арифметическим и стековым операциям добавляют операции двойной точности. Слова для таких операций обычно начинаются с символа «2»: 2DUP, 2SWAP и т.д. Но у нас стандартная арифметика уже 64 разряда, и 128 мы сегодня точно делать не будем :)

    Дальше добавим основные стековые операции (drop, swap, root, -root, over, pick, roll).

    Стековые операции
    b_drop = 0x31
    bcmd_drop:	add	rsp, 8
    		jmp	_next
    
    b_swap = 0x32
    bcmd_swap:	pop	rax
    		pop	rbx
    		push	rax
    		push	rbx
    		jmp	_next
    
    b_rot = 0x33
    bcmd_rot:	pop	rax
    		pop	rbx
    		pop	rcx
    		push	rbx
    		push	rax
    		push	rcx
    		jmp	_next
    		
    b_mrot = 0x34
    bcmd_mrot:	pop	rcx
    		pop	rbx
    		pop	rax
    		push	rcx
    		push	rax
    		push	rbx
    		jmp	_next
    		
    b_over = 0x35
    bcmd_over:	push	[rsp + 8]
    		jmp	_next
    		
    b_pick = 0x36
    bcmd_pick:	pop	rcx
    		push	[rsp + 8*rcx]
    		jmp	_next
    		
    b_roll = 0x37
    bcmd_roll:	pop	rcx
    		mov	rbx, [rsp + 8*rcx]
    roll1:		mov	rax, [rsp + 8*rcx - 8]
    		mov	[rsp + 8*rcx], rax
    		dec	rcx
    		jnz	roll1
    		push	rbx
    		jmp	_next

    И еще сделаем команды чтения и записи в память (фортовские слова @ и !). А так же их аналоги на другую разрядность.

    Чтение и запись в память
    b_get = 0x40
    bcmd_get:	pop	rcx
    		push	[rcx]
    		jmp	_next
    
    b_set = 0x41
    bcmd_set:	pop	rcx
    		pop	rax
    		mov	[rcx], rax
    		jmp	_next
    
    b_get8 = 0x42
    bcmd_get8:	pop	rcx
    		movsx	rax, byte ptr [rcx]
    		push	rax
    		jmp	_next
    
    b_set8 = 0x43
    bcmd_set8:	pop	rcx
    		pop	rax
    		mov	[rcx], al
    		jmp	_next
    
    b_get16 = 0x44
    bcmd_get16:	pop	rcx
    		movsx	rax, word ptr [rcx]
    		push	rax
    		jmp	_next
    
    b_set16 = 0x45
    bcmd_set16:	pop	rcx
    		pop	rax
    		mov	[rcx], ax
    		jmp	_next
    
    b_get32 = 0x46
    bcmd_get32:	pop	rcx
    		movsx	rax, dword ptr [rcx]
    		push	rax
    		jmp	_next
    
    b_set32 = 0x47
    bcmd_set32:	pop	rcx
    		pop	rax
    		mov	[rcx], eax
    		jmp	_next

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

    Команды сравнения
    # 0=
    b_zeq = 0x50
    bcmd_zeq:	pop	rax
    		or	rax, rax
    		jnz	rfalse
    rtrue:		push	-1
    		jmp	_next
    rfalse:		push	0
    		jmp	_next
    		
    # 0<
    b_zlt = 0x51
    bcmd_zlt:	pop	rax
    		or	rax, rax
    		jl	rtrue
    		push	0
    		jmp	_next
    		
    # 0>
    b_zgt = 0x52
    bcmd_zgt:	pop	rax
    		or	rax, rax
    		jg	rtrue
    		push	0
    		jmp	_next
    
    # =
    b_eq = 0x53
    bcmd_eq:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jz	rtrue
    		push	0
    		jmp	_next
    
    # <
    b_lt = 0x54
    bcmd_lt:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jl	rtrue
    		push	0
    		jmp	_next
    		
    # >
    b_gt = 0x55
    bcmd_gt:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jg	rtrue
    		push	0
    		jmp	_next
    
    # <=
    b_lteq = 0x56
    bcmd_lteq:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jle	rtrue
    		push	0
    		jmp	_next
    		
    # >=
    b_gteq = 0x57
    bcmd_gteq:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jge	rtrue
    		push	0
    		jmp	_next

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

    Еще сразу сделаем слово depth (глубина стека). Для этого, при старте, сохраним начальные значения стека данных и стека возвратов. Эти значения могут еще пригодиться и при рестарте системы.

    init_stack:	.quad	0
    init_rstack:	.quad	0
    
    _start:		mov	rbp, rsp
    		sub	rbp, stack_size
    		lea	r8, start
    		mov	init_stack, rsp
    		mov	init_rstack, rbp
    		jmp	_next
    
    b_depth = 0x38
    bcmd_depth:	mov	rax, init_stack
    		sub	rax, rsp
    		shr	rax, 3
    		push	rax
    		jmp	_next

    Вывод чисел


    Ну что же, разминка кончилась, и придется немного попотеть. Научим нашу систему выводить числа. Для вывода чисел в форте используется слово "." (точка). Сделаем это так, как делается в стандартных реализациях форта, с использованием слов <#, hold, #, #s, #>, base. Придется реализовать все эти слова. Для формирования числа используется буфер и указатель на формируемый символ, это будут слова holdbuf и holdpoint.

    Итак, нам потребуются вот такие слова:

    • holdbuf — буфер для формирования представления числа, формирование происходит с конца
    • holdpoint — адрес на последний выведенный символ (в holdbuf)
    • <# — начало формирования числа; устанавливает holdpoint на байт, за последним байтом holdbuf
    • hold — уменьшает holdpoint на 1 и по полученному адресу сохраняет символ со стека в буфер
    • # — делит слово на вершине стека на основание системы счисления, остаток от деления переводит в символ и сохраняет в буфер с помощью hold
    • #s — преобразует все слово; фактически вызывает слово # в цикле, пока на стеке не останется 0
    • #> — завершение преобразования; помещает в стек начало сформированной строки и ее длину

    Все слова сделаем на байт-коде, но для начала разберемся с переменными.

    Переменные


    А вот тут будет немного фортовской магии. Дело в том, что в форте переменная — это слово. При исполнении этого слова, в стеке оказывается адрес ячейки памяти, хранящее значение переменной. По этому адресу можно читать или писать. Например, что бы записать в переменную A значение 12345, нужно выполнить такие команды: «12345 A !». В этом примере, в стек помещается 12345, потом переменная A кладет свой адрес, а слово "!" снимает со стека два значения и записывает 12345 по адресу переменной A. В типичных реализациях форта (с прямым шитым кодом), переменные представляют собой команду микропроцессора CALL с адресом _next, после которой зарезервировано место для хранения значения переменной. При исполнении такого слова микропроцессор передает управление на _next и кладет в стек адрес возврата (по RSP). Но в форте стек микропроцессора — арифметический, и возвращаться никуда не будем. В результате этого, выполнение продолжается, а в стеке — адрес переменной. И все это одной процессорной командой! На ассемблере это выглядело бы так:

    		call	_next	# улетели на _next, а в стек попал адрес возврата, где лежит 12345
    		.quad	12345

    Но у нас байт-код, и мы не можем использовать этот механизм! Я не сразу сообразил, как можно сделать подобный механизм на байт-коде. Но, если рассуждать логически, ни что не мешает реализовать что-то очень похожее. Просто надо учитывать, что это будет не команда процессора, а байт-код, точнее, «подпрограмма» на байт-коде. Вот постановка задачи:

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

    У нас есть байт-команда exit. Сделаем слово на байт-коде, содержащее одну-единственную команду exit. Тогда эта команда будет осуществлять возврат из него. Остается сделать такую же команду, которая дополнительно положит в стек адрес следующего байта (регистр R8). Сделаем это в виде дополнительной точки входа в exit, что бы сэкономить на переходе:

    b_var0 = 0x28
    bcmd_var0:	push	r8
    
    b_exit = 0x17
    bcmd_exit:	mov	r8, [rbp]
    		add	rbp, 8
    
    _next:		movzx	rcx, byte ptr [r8]
    		inc	r8
    		jmp	[bcmd + rcx*8]

    Теперь переменная base будет выглядеть так:
    base:		.byte	b_var0
    		.quad	10

    Кстати, а почему именно var0, а не просто var? Дело в том, что будут другие команды для определения более продвинутых слов, которые содержат данные. Подробнее я расскажу в следующих статьях.

    Теперь у нас все готово, что бы сделать вывод чисел. Начнем!

    Слова base, holdbuf, holdpoint


    Как будут устроены переменные, уже определились. Поэтому, слова base, holdbuf, holdpoint получаются такими:

    base:		.byte	b_var0
    		.quad	10
    
    holdbuf_len = 70
    holdbuf:	.byte	b_var0
    		.space	holdbuf_len
    
    holdpoint:	.byte	b_var0
    		.quad	0

    Размер буфера holdbuf выбран 70. Максимальное количество разрядов числа — 64 (это если выбрать двоичную систему). Еще сделан запас в несколько символов, что бы поместить, например, знак числа и пробел после него. На переполнение буфера сделаем проверку, но пока не будем помещать лишние символы в буфер. Потом можно будет сделать другую диагностику.

    hold


    Теперь можно сделать слово hold. На форте его код выглядит так:

    : hold holdpoint @ 1- dup holdbuf > if drop drop else dup holdpoint ! c! then ;

    Для тех, кто видит форт впервые, разберу подробно код. Для последующих слов делать этого не буду.

    В начале идет слово для определения новых слов и имя нового слова: ": hold". После этого идет код, который завершается словом ";". Разберем код слова. Приведу команду и состояние стека после исполнения команды. Перед вызовом слова на стеке находиться код символа, который помещается в буфер (обозначено <символ>). Далее получается так:

    holdpoint	<символ> <адрес переменной holdpoint>
    @		<символ> <содержимое переменной holdpoint>
    1-		<символ> <содержимое переменной holdpoint минус 1>
    dup		<символ> <содержимое переменной holdpoint минус 1> <содержимое переменной holdpoint минус 1>
    holdbuf		<символ> <содержимое переменной holdpoint минус 1> <содержимое переменной holdpoint минус 1> <начало буфера holdbuf>
    >		<символ> <содержимое переменной holdpoint минус 1> <истина, если содержимое переменной holdpoint минус 1 больше начала буфера holdbuf>

    После этого находится команда if, которая компилируется в условный переход на последовательность команд между else и then. Условный переход снимает со стека результат сравнения и выполняет переход, если на стеке была ложь. Если перехода не было, то выполняется ветвь между if и else, в которой две комманды drop, которые убирают символ и адрес. В противном случае выполнение продолжается. Слово "!" сохраняет новое значение в holdpoint (со стека снимается адрес и значение). А слово «c!» записывает символ в буфер, это байт-команда set8 (со стека снимается адрес и значение символа).

    dup		<символ> <содержимое переменной holdpoint минус 1> <содержимое переменной holdpoint минус 1>
    holdpoint	<символ> <содержимое переменной holdpoint минус 1> <содержимое переменной holdpoint минус 1> <адрес переменной holdpoint>
    !		<символ> <содержимое переменной holdpoint минус 1>
    c!		все, символ записан, а стек пустой! :)

    Вот сколько действий делает эта короткая последовательность комманд! Да, форт лаконичен. А теперь включаем ручной «компилятор» в голове :) И компилируем все это в байт-код:
    hold:		.byte	b_call8
    		.byte	holdpoint - . - 1	# holdpoint
    		.byte	b_get			# @
    		.byte	b_wm			# 1-
    		.byte	b_dup			# dup
    		.byte	b_call8
    		.byte	holdbuf - . - 1		# holdbuf
    		.byte	b_gt			# >
    		.byte	b_qbranch8		# if
    		.byte	0f - .
    		.byte	b_drop			# drop
    		.byte	b_drop			# drop
    		.byte	b_branch8		# команда перехода на возврат (после then)
    		.byte	1f - .
    0:		.byte	b_dup			# dup
    		.byte	b_call8
    		.byte	holdpoint - . - 1	# holdpoint
    		.byte	b_set			# !
    		.byte	b_set8			# c!
    1:		.byte	b_exit			# ;

    Здесь я использовал локальные метки (0 и 1). К этим меткам можно обращаться по специальным именам. Например, к метке 0 можно обращаться по именам 0f или 0b. Это означает ссылку на ближайшую метку 0 (вперед или назад). Довольно удобно для меток, которые используются локально, что бы не придумывать различные имена.

    Слово #


    Сделаем слово #. На форте его код будет выглядеть так:

    : # base /mod swap dup 10 < if c″ 0 + else 10 - c″ A + then hold ;

    Условие тут применяется для проверки: меньше ли полученная цифра десяти? Если меньше, используются цифры 0-9, иначе — символы, начиная с «A». Это позволит работать и с шестнадцатиричной системой счисления. Последовательность c″ 0 кладет на стек код символа 0. Включаем «компилятор»:

    conv:		.byte	b_call16
    		.word	base - . - 2		# base
    		.byte	b_get			# @
    		.byte	b_divmod		# /mod
    		.byte	b_swap			# swap
    		.byte	b_dup			# dup
    		.byte	b_lit8
    		.byte	10			# 10
    		.byte	b_lt			# <
    		.byte	b_qnbranch8		# if
    		.byte	0f - .
    		.byte	b_lit8
    		.byte	'0'			# c″ 0
    		.byte	b_add			# +
    		.byte	b_branch8		# else
    		.byte	1f - .
    0:		.byte	b_lit8
    		.byte	'A'			# c″ A
    		.byte	b_add			# +
    1:		.byte	b_call16
    		.word	hold - . - 2		# hold
    		.byte	b_exit			# ;

    Слово <#


    Слово <# совсем простое:

    : <# holdbuf 70 + holdpoint ! ;

    Байт-код:

    conv_start:	.byte	b_call16
    		.word	holdbuf - . - 2
    		.byte	b_lit8
    		.byte	holdbuf_len
    		.byte	b_add
    		.byte	b_call16
    		.word	holdpoint - . - 2
    		.byte	b_set
    		.byte	b_exit

    Слово #>


    Слово #> для завершения преобразования выглядит так:

    : #> holdpoint @ holdbuf 70 + over - ;

    Байт-код:

    conv_end:	.byte	b_call16
    		.word	holdpoint - . - 2
    		.byte	b_get
    		.byte	b_call16
    		.word	holdbuf - . - 2
    		.byte	b_lit8
    		.byte	holdbuf_len
    		.byte	b_add
    		.byte	b_over
    		.byte	b_sub
    		.byte	b_exit

    Слово #s


    И, наконец, слово #s:

    : #s do # dup 0= until ;

    Байт-код:

    conv_s:		.byte	b_call8
    		.byte	conv - . - 1
    		.byte	b_dup
    		.byte	b_qbranch8
    		.byte	conv_s - .
    		.byte	b_exit

    Кто внимательный, заметит здесь небольшое несоответствие байт-кода и кода форта :)

    Все готово


    Теперь ничто не помешает сделать слово ".", которое выводит число:

    : . <# #s drop #> type ;

    Байт-код:

    dot:		.byte	b_call8
    		.byte	conv_start - . - 1
    		.byte	b_call8
    		.byte	conv_s - . - 1
    		.byte	b_drop
    		.byte	b_call8
    		.byte	conv_end - . - 1
    		.byte	b_type
    		.byte	b_exit

    Сделаем тестовый байт-код, который проверяет нашу точку:

    start:	.byte	b_lit16
    	.word	1234
    	.byte	b_call16
    	.word	dot - . - 2
    	.byte	b_bye

    Конечно, заработало все не сразу. Но, после отладки, был получен такой результат:

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

    Косяк виден сразу. После числа форт должен выводить пробел. Добавим после вызова conv_start (<#) команды 32 hold.

    Еще сделаем вывод знака. В начале добавим dup abs, а в конце проверим знак оставленной копии и поместим минус, если число отрицательное (0< if c″ – hold then). В результате, слово "." приобретает такой вид:

    : . dup abs <# 32 hold #s drop #> 0< if c″ - hold then type ;

    Байт-код:

    dot:		.byte	b_dup
    		.byte	b_abs
    		.byte	b_call8
    		.byte	conv_start - . - 1
    		.byte	b_lit8
    		.byte	' '
    		.byte	b_call16
    		.word	hold - . - 2
    		.byte	b_call8
    		.byte	conv_s - . - 1
    		.byte	b_drop
    		.byte	b_zlt
    		.byte	b_qnbranch8
    		.byte	1f - .
    		.byte	b_lit8
    		.byte	'-'
    		.byte	b_call16
    		.word	hold - . - 2
    1:		.byte	b_call8
    		.byte	conv_end - . - 1
    		.byte	b_type
    		.byte	b_exit

    В стартовой последовательности байт-команд поставим отрицательное число и проверим:

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

    Вывод чисел есть!

    Полный исходник
    
    .intel_syntax noprefix
    
    stack_size = 1024
    
    .section .data
    
    init_stack:	.quad	0
    init_rstack:	.quad	0
    
    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 
    
    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_qnbranch8,	bcmd_qnbranch16,bcmd_bad,	bcmd_exit	# 0x10
    .quad		bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad
    .quad		bcmd_wm,	bcmd_add,	bcmd_sub,	bcmd_mul,	bcmd_div,	bcmd_mod,	bcmd_divmod,	bcmd_abs	# 0x20
    .quad		bcmd_var0,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad
    .quad		bcmd_dup,	bcmd_drop,	bcmd_swap,	bcmd_rot,	bcmd_mrot,	bcmd_over,	bcmd_pick,	bcmd_roll	# 0x30
    .quad		bcmd_depth,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad 
    .quad		bcmd_get,	bcmd_set,	bcmd_get8,	bcmd_set8,	bcmd_get16,	bcmd_set16,	bcmd_get32,	bcmd_set32 	# 0x40
    .quad		bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad,	bcmd_bad 
    .quad		bcmd_zeq,	bcmd_zlt,	bcmd_zgt,	bcmd_eq,	bcmd_lt,	bcmd_gt,	bcmd_lteq,	bcmd_gteq	#0x50
    .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_lit16
    		.word	-1234
    		.byte	b_call16
    		.word	dot - . - 2
    		.byte	b_bye
    
    base:		.byte	b_var0
    		.quad	10
    
    holdbuf_len = 70
    holdbuf:	.byte	b_var0
    		.space	holdbuf_len
    
    holdpoint:	.byte	b_var0
    		.quad	0
    
    # : hold holdpoint @ 1- dup holdbuf > if drop drop else dup holdpoint ! c! then ;
    hold:		.byte	b_call8
    		.byte	holdpoint - . - 1	# holdpoint
    		.byte	b_get			# @
    		.byte	b_wm			# 1-
    		.byte	b_dup			# dup
    		.byte	b_call8
    		.byte	holdbuf - . - 1		# holdbuf
    		.byte	b_gt			# >
    		.byte	b_qbranch8		# if
    		.byte	0f - .
    		.byte	b_drop			# drop
    		.byte	b_drop			# drop
    		.byte	b_branch8		# команда перехода на возврат (после then)
    		.byte	1f - .
    0:		.byte	b_dup			# dup
    		.byte	b_call8
    		.byte	holdpoint - . - 1	# holdpoint
    		.byte	b_set			# !
    		.byte	b_set8			# c!
    1:		.byte	b_exit			# ;
    
    # : # base /mod swap dup 10 < if c" 0 + else 10 - c" A + then hold ;
    conv:		.byte	b_call16
    		.word	base - . - 2		# base
    		.byte	b_get			# @
    		.byte	b_divmod		# /mod
    		.byte	b_swap			# swap
    		.byte	b_dup			# dup
    		.byte	b_lit8
    		.byte	10			# 10
    		.byte	b_lt			# <
    		.byte	b_qnbranch8		# if
    		.byte	0f - .
    		.byte	b_lit8
    		.byte	'0'			# c" 0
    		.byte	b_add			# +
    		.byte	b_branch8		# else
    		.byte	1f - .
    0:		.byte	b_lit8
    		.byte	'?'			# c" A
    		.byte	b_add			# +
    1:		.byte	b_call16
    		.word	hold - . - 2		# hold
    		.byte	b_exit			# ;
    
    # : <# holdbuf 70 + holdpoint ! ;
    conv_start:	.byte	b_call16
    		.word	holdbuf - . - 2
    		.byte	b_lit8
    		.byte	holdbuf_len
    		.byte	b_add
    		.byte	b_call16
    		.word	holdpoint - . - 2
    		.byte	b_set
    		.byte	b_exit
    
    # : #s do # dup 0=until ;
    conv_s:		.byte	b_call8
    		.byte	conv - . - 1
    		.byte	b_dup
    		.byte	b_qbranch8
    		.byte	conv_s - .
    		.byte	b_exit
    
    # : #> holdpoint @ holdbuf 70 + over - ;
    conv_end:	.byte	b_call16
    		.word	holdpoint - . - 2
    		.byte	b_get
    		.byte	b_call16
    		.word	holdbuf - . - 2
    		.byte	b_lit8
    		.byte	holdbuf_len
    		.byte	b_add
    		.byte	b_over
    		.byte	b_sub
    		.byte	b_exit
    
    dot:		.byte	b_dup
    		.byte	b_abs
    		.byte	b_call8
    		.byte	conv_start - . - 1
    		.byte	b_lit8
    		.byte	' '
    		.byte	b_call16
    		.word	hold - . - 2
    		.byte	b_call8
    		.byte	conv_s - . - 1
    		.byte	b_drop
    		.byte	b_zlt
    		.byte	b_qnbranch8
    		.byte	1f - .
    		.byte	b_lit8
    		.byte	'-'
    		.byte	b_call16
    		.word	hold - . - 2
    1:		.byte	b_call8
    		.byte	conv_end - . - 1
    		.byte	b_type
    		.byte	b_exit
    
    	.section .text
    .global _start # точка входа в программу
    
    _start:		mov	rbp, rsp
    		sub	rbp, stack_size
    		lea	r8, start
    		mov	init_stack, rsp
    		mov	init_rstack, rbp
    		jmp	_next
    
    b_var0 = 0x28
    bcmd_var0:	push	r8
    
    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 = 0x30
    bcmd_dup:       push    [rsp]
                    jmp     _next
    
    b_wm = 0x20
    bcmd_wm:        decq    [rsp]
                    jmp     _next
    
    b_add = 0x21
    bcmd_add:	pop	rax
    		add	[rsp], rax
    		jmp	_next
    
    b_sub = 0x22
    bcmd_sub:	pop	rax
    		sub	[rsp], rax
    		jmp	_next
    
    b_mul = 0x23
    bcmd_mul:	pop	rax
    		pop	rbx
    		imul	rbx
    		push	rax
    		jmp	_next
    
    b_div = 0x24
    bcmd_div:	pop	rbx
    		pop	rax
    		cqo
    		idiv	rbx
    		push	rax
    		jmp	_next
    
    b_mod = 0x25
    bcmd_mod:	pop	rbx
    		pop	rax
    		cqo
    		idiv	rbx
    		push	rdx
    		jmp	_next
    
    b_divmod = 0x26
    bcmd_divmod:	pop	rbx
    		pop	rax
    		cqo
    		idiv	rbx
    		push	rdx
    		push	rax
    		jmp	_next
    
    b_abs = 0x27
    bcmd_abs:	mov	rax, [rsp]
    		or	rax, rax
    		jge	_next
    		neg	rax
    		mov	[rsp], rax
    		jmp	_next
    
    b_drop = 0x31
    bcmd_drop:	add	rsp, 8
    		jmp	_next
    
    b_swap = 0x32
    bcmd_swap:	pop	rax
    		pop	rbx
    		push	rax
    		push	rbx
    		jmp	_next
    
    b_rot = 0x33
    bcmd_rot:	pop	rax
    		pop	rbx
    		pop	rcx
    		push	rbx
    		push	rax
    		push	rcx
    		jmp	_next
    		
    b_mrot = 0x34
    bcmd_mrot:	pop	rcx
    		pop	rbx
    		pop	rax
    		push	rcx
    		push	rax
    		push	rbx
    		jmp	_next
    		
    b_over = 0x35
    bcmd_over:	push	[rsp + 8]
    		jmp	_next
    		
    b_pick = 0x36
    bcmd_pick:	pop	rcx
    		push	[rsp + 8*rcx]
    		jmp	_next
    		
    b_roll = 0x37
    bcmd_roll:	pop	rcx
    		mov	rbx, [rsp + 8*rcx]
    roll1:		mov	rax, [rsp + 8*rcx - 8]
    		mov	[rsp + 8*rcx], rax
    		dec	rcx
    		jnz	roll1
    		push	rbx
    		jmp	_next
    
    b_depth = 0x38
    bcmd_depth:	mov	rax, init_stack
    		sub	rax, rsp
    		shr	rax, 3
    		push	rax
    		jmp	_next
    		
    b_get = 0x40
    bcmd_get:	pop	rcx
    		push	[rcx]
    		jmp	_next
    
    b_set = 0x41
    bcmd_set:	pop	rcx
    		pop	rax
    		mov	[rcx], rax
    		jmp	_next
    
    b_get8 = 0x42
    bcmd_get8:	pop	rcx
    		movsx	rax, byte ptr [rcx]
    		push	rax
    		jmp	_next
    
    b_set8 = 0x43
    bcmd_set8:	pop	rcx
    		pop	rax
    		mov	[rcx], al
    		jmp	_next
    
    b_get16 = 0x44
    bcmd_get16:	pop	rcx
    		movsx	rax, word ptr [rcx]
    		push	rax
    		jmp	_next
    
    b_set16 = 0x45
    bcmd_set16:	pop	rcx
    		pop	rax
    		mov	[rcx], ax
    		jmp	_next
    
    b_get32 = 0x46
    bcmd_get32:	pop	rcx
    		movsx	rax, dword ptr [rcx]
    		push	rax
    		jmp	_next
    
    b_set32 = 0x47
    bcmd_set32:	pop	rcx
    		pop	rax
    		mov	[rcx], eax
    		jmp	_next
    		
    # 0=
    b_zeq = 0x50
    bcmd_zeq:	pop	rax
    		or	rax, rax
    		jnz	rfalse
    rtrue:		push	-1
    		jmp	_next
    rfalse:		push	0
    		jmp	_next
    		
    # 0<
    b_zlt = 0x51
    bcmd_zlt:	pop	rax
    		or	rax, rax
    		jl	rtrue
    		push	0
    		jmp	_next
    		
    # 0>
    b_zgt = 0x52
    bcmd_zgt:	pop	rax
    		or	rax, rax
    		jg	rtrue
    		push	0
    		jmp	_next
    
    # =
    b_eq = 0x53
    bcmd_eq:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jz	rtrue
    		push	0
    		jmp	_next
    
    # <
    b_lt = 0x54
    bcmd_lt:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jl	rtrue
    		push	0
    		jmp	_next
    		
    # >
    b_gt = 0x55
    bcmd_gt:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jg	rtrue
    		push	0
    		jmp	_next
    
    # <=
    b_lteq = 0x56
    bcmd_lteq:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jle	rtrue
    		push	0
    		jmp	_next
    		
    # >=
    b_gteq = 0x57
    bcmd_gteq:	pop	rbx
    		pop	rax
    		cmp	rax, rbx
    		jge	rtrue
    		push	0
    		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_qnbranch8 = 0x14
    bcmd_qnbranch8:	pop     rax
                    or      rax, rax
                    jz	bcmd_branch8
                    inc     r8
                    jmp     _next
    
    b_qnbranch16 = 0x15
    bcmd_qnbranch16:pop     rax
                    or      rax, rax
                    jz	bcmd_branch16
                    add     r8, 2
                    jmp     _next
    
    b_bad = 0x00
    bcmd_bad:	mov	rax, 1			# системный вызов № 1 - sys_write
    		mov	rdi, 1			# поток № 1 — stdout
    		mov	rsi, offset msg_bad_byte # указатель на выводимую строку
    		mov	rdx, msg_bad_byte_len	# длина строки
    		syscall				# вызов ядра
    		mov	rax, 60			# системный вызов № 1 - sys_exit
    		mov	rbx, 1			# выход с кодом 1
    		syscall				# вызов ядра
    
    b_bye = 0x01
    bcmd_bye:	mov	rax, 1			# системный вызов № 1 - sys_write
    		mov	rdi, 1			# поток № 1 — stdout
    		mov	rsi, offset msg_bye	# указатель на выводимую строку
    		mov	rdx, msg_bye_len	# длина строки
    		syscall				# вызов ядра
    		mov	rax, 60			# системный вызов № 60 - sys_exit
    		mov	rdi, 0			# выход с кодом 0
    		syscall				# вызов ядра
    
    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
    

    Итог


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

    Всех с наступающим Новым годом!

    Критика — приветствуется! :)
    Поделиться публикацией

    Комментарии 16

      0
      Погодите. Парсинг строк, ввод строк и т.п. для форта ведь делается (точнее, берётся готовый) на форте, ядро — совсем крохотное, нет?
        0
        Не совсем понял вопрос. Я не брал ничего готового, даже каких-то библиотек. Все с полного нуля. Под парсингом строк на форте я понимаю слово word и подобные, которые берут для обработки информацию из входного буфера. Все это нужно создавать на ассемблере — буфер, его парсинг, заполнение буфера из стандартного ввода системными вызовами, и другое. Под ядром в форте обычно понимают то, что написано не на форте — обычно на C или ассемблере. В данном случае на ассемблере. Да, оно небольшое, думаю, несколько килобайт.
          0
          Ну вот мне и казалось, что парсинг буфера — не в ядре. Смысл его в ядро выносить? Достаточно функции получения буфера.
          Насчёт «ввода строк» я, может, и погорячился — но при наличии функций ввода символа, отображения символа и стирания символа или позиционирования курсора — почему нет?
            0
            Можно сделать и не в ядре, но тогда в ядре надо будет сделать строковые операции. А уже на на них делать парсинг. Но парсинг на форте очень прост. Там либо читается следующее слово, либо строка до определенного разделителя. Я хочу максимально быстро сделать интерпретатор, а потом компилятор. Сделать несколько слов для парсинга на ассемблере проще, чем делать строковые операции, а на них уже эти слова парсинга. И работать они будут быстрее. К тому же, если делать через строковые операции в ядре, придется много писать байт-кода вручную.
            В общем, сделать несколько слов парсинга в ядре проще, работать они будут быстрее, и цель — создать компилятор, будет достигнута быстрее.
            Как-то так :)
        0
        Не зняю, что за команда var. В первом приближении,
        во всех процедурах работающие с памятью,
        достаточно к адресам прибавить базовый адрес.
        не пример:
        b_get = 0x40
        bcmd_get: pop rcx
        push [rcx+start]
        jmp _next

        b_set = 0x41
        bcmd_set: pop rcx
        pop rax
        mov [rcx+start], rax
        jmp _next
          0
          Описал эту команду по максимуму. Думал, даже самые непонятливые поймут) прибавлять точно ничего не нужно :)
            0
            Не только в переменных дело, если ставится задача переносимости
            на уровне бинарных модулей. В бинарном модуле не допустимо
            появления ни одного прямого адреса. В принципе, эту задачу
            можно возложить на пользователей системы. Но думаю, пользователи
            с этим не согласятся.
          0
          fpauk
          разберись с командой var0
            0
            Тут следует вычесть базу:
            b_var0 = 0x28
            bcmd_var0:
            mov rax,r8
            sub rax,start
            push rax

            Иначе, что собой будут представлять список указателей?
            Например, список указателей на словари.
              0
              Спасибо за интерес!
              В следующей статье подробно опишу этот момент.
            +1
            b_bad = 0x00
            bcmd_bad: mov rax, 1 # системный вызов № 1 — sys_write

            mov rax, 60 # системный вызов № 1 — sys_exit
            mov rbx, 1 # выход с кодом 1
            syscall # вызов ядра

            b_bye = 0x01
            bcmd_bye: mov rax, 1 # системный вызов № 1 — sys_write
            mov rdi, 1 # поток № 1 — stdout
            mov rsi, offset msg_bye # указатель на выводимую строку
            mov rdx, msg_bye_len # длина строки
            syscall # вызов ядра
            mov rax, 60 # системный вызов № 60 — sys_exit
            mov rdi, 0 # выход с кодом 0
            syscall # вызов ядра
              0
              Да, ошибка.

              Должно быть так:

              mov rax, 60 # системный вызов № 1 — sys_exit
              mov rdi, 1 # выход с кодом 1
              syscall # вызов ядра

              Первый параметр в 64-х битном syscall — это RDI.
              В 32-х битном был EBX, видимо, на автомате, исправил на RBX.

              Спасибо! :)
              0
                +1
                Планируются ли какие фишки (байт-коды) добавить в систему, помимо стандартных слов Форт-системы? (насколько система будет покрывать существующие стандарты Форта)
                Один из примеров Форт-подобного языка имеющего нестандартные байт-кода home.hccnet.nl/anij/nof/noforth.html
                Существуют и другие разные варианты.

                P.S. Есть и такая статья о Форте на нейронных сетях
                Programming with a Differentiable Forth Interpreter
                arxiv.org/abs/1605.06640

                  0
                  Ого, не думал, что что-то общее может быть между фортом и нейронными сетями :)
                  Спасибо за ссылки, обязательно прочитаю.

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

                  Никаких упрощений не делаю, при желании можно будет развить в полноценную форт-систему.
                    0
                    Форт ориентированный байт-код можно много где встретить (неплохо, если бы был дополнительно какой то обзор этого в рамках данного цикла статей)
                    P.S. Например в Radare2, язык промежуточного представления реверсируемой программы ESIL использует Форт-подобный процессор (и для симуляции логики кода)
                    radare.gitbooks.io/radare2book/disassembling/esil.html
                    OpenBios ещё одно «широко» известное использование Форта+байт-кода github.com/openbios

                    P.S. Большее количество информации Форт направленности можно найти в сообщениях рускоязычного Форт-форума fforum.winglion.ru/index.php (активного c 2006 года)
                    Отдельно интересен вопрос нативного ускорения байт-кода в целевом устройстве и оптимизации его по параметру быстродействие/размер_кода.
                    Один из примеров в этом направлении github.com/mic-/forthec (Форт-подобный язык транслируется в ассемблерный код целевого процессора с некоторыми оптимизациями) язык реализации проекта Euphoria (язык программирования)
                    Запуск примера из этого проекта в рамках KolibriOS системы board.kolibrios.org/viewtopic.php?f=38&t=3268

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

                Самое читаемое