Введение
Разработка виртуальных машин может быть не только интересным занятием на вечер, но также и полезным приложением при обучении студентов языку ассемблера на предметах ОАиП (основы алгоритмизации и программирования) и ААС (архитектура аппаратных средств). Целью данной статьи станет создание простой стековой виртуальной машины с собственным языком ассемблера, способным выполнять операции условного и безусловного переходов, инкрементирования и декрементирования чисел, загрузки и выгрузки значений в стек. Машина получится минималистичной и будет обладать лишь 10-ью инструкциями, на основе которых можно будет далее вполне корректно создать собственный высокоуровневый язык программирования.
Экземпляр виртуальной машины
Виртуальной машине, помимо инструкций, нужна также память. Память может быть представлена двумя значениями: максимальным количеством загружаемого байт-кода и максимальным значением стека выполнения. Стек у нас будет состоять из 32-битных чисел. Фактически это будет единственным типом данных на базе которого будут производиться все дальнейшие операции.
#define CVM_KERNEL_SMEMORY (1 << 10) // Stack = 1024 INT32 #define CVM_KERNEL_CMEMORY (4 << 10) // Code = 4096 BYTEДалее, нам необходимо сформировать список инструкций. Он будет минимальным в том лишь плане, что будут отсутствовать такие инструкции как: add, sub, mul, div, shift, not, xor, or, and, je, jl, jge, jle и т.д. В нашем концепте, минимализм — это самое главное. Таким образом, список инструкций будет следующим:
enum { C_PUSH = 0x0A, // 5 bytes C_POP = 0x0B, // 1 byte C_INC = 0x0C, // 1 byte C_DEC = 0x0D, // 1 byte C_JMP = 0x0E, // 1 byte C_JG = 0x0F, // 1 byte C_STOR = 0x1A, // 1 byte C_LOAD = 0x1B, // 1 byte C_CALL = 0x1C, // 1 byte C_HLT = 0x1D, // 1 byte };Инструкция push будет класть 32-битное значение в стек. Инструкция pop будет удалять последнее значение из стека. Инструкции inc, dec — будут инкрементировать и декрементировать последнее значение в стеке. Инструкции jmp, jg — представляют безусловный и условный (x>y) переходы. stor, load — сохраняет / выгружает значение в / из определённой области памяти стека. call — сохраняет адрес возврата в стек и производит выполнение инструкции jmp. hlt — прекращает выполнение кода виртуальной машиной. Все вышеописанные инструкции, за исключением push и hlt, берут свои аргументы / значения из стека. Инструкция hlt не содержит аргументов вовсе, а вот push — является уникальной инструкцией, потому как аргумент передаётся ей не через стек, а непосредственно через неё саму. Поэтому инструкция и занимает целых 5 байт, хотя её опкод на деле равен всё также одному байту.
Чтобы написать работающий код, выполняющий какое-либо вычисление, нам будет вполне достаточно иметь опкоды данных инструкций. В таком случае, мы бы напрямую использовали их, а виртуальная машина их корректно бы интерпретировала. Но в таком случае существует ряд минусов: 1) сложно держать в голове все 16-ые числа и понимать за что они отвечают, особенно когда количество инструкций будет увеличиваться, 2) необходимо использовать редактор кода, который записывал бы инструкции не в текстовом формате, а в бинарном, что не совсем удобно при программировании.
В результате, чтобы побороть данные минусы, нам необходимо создать дополнительный слой абстракции в роли мнемоников, т.е. создать ассемблер, который бы транслировал текстовые инструкции по типу `push 5, jmp` в 0x0A 0x00 0x00 0x00 0x05, 0x0E.
В слое абстракции есть также ещё дополнительный плюс, а именно — мы теперь сможем создавать псевдоинструкции, которые бы позволяли более просто писать ассемблерный код, но при этом не занимали бы памяти в результирующем машинном коде. Из таких псевдоинструкций мы можем вычленить метки по которым было бы удобно совершать инструкции условного и безусловного переходов. К таким же псевдоинструкциям мы можем добавить комментирование, которое бы игнорировалось ассемблером, но было бы полезно для людей.
enum { C_CMNT = 0x11, // 0 bytes, comment C_LABL = 0x22, // 0 bytes, label C_UNDF = 0xAA, // 0 bytes, undefined mnemonic C_VOID = 0xBB, // 0 bytes, void string }В данной реализации присутствует ещё две дополнительные псевдоинструкции, отвечающие за то, что строка в ассемблерном листинге кода — пустая, а также, что мнемоник не был найден. Псевдоинструкция C_VOID схожа с C_CMNT, т.к. вводится программистом для удобочитаемости кода, но отличие заключается в том, что она неявная и признана логически разделять участки / блоки кода пустыми символами (знаками переноса с возможным содержанием других пустых символов). C_UNDF служит триггером для указания виртуальной машине, что конкретный псевдокод не был ею найден. Таким образом, псевдоинструкции C_VOID, C_UNDF не обладают реальными мнемониками.
Итого, мы наконец можем получить следующий экземпляр виртуальной машины:
#define CVM_KERNEL_ISIZE 14 static struct virtual_machine { int32_t cmused; uint8_t memory[CVM_KERNEL_CMEMORY]; struct { uint8_t bcode; char *mnem; } bclist[CVM_KERNEL_ISIZE]; } VM = { .cmused = 0, .bclist = { { C_VOID, "\0" }, // 0 arg { C_UNDF, "\1" }, // 0 arg { C_CMNT, ";" }, // 0 arg { C_LABL, "labl" }, // 1 arg { C_PUSH, "push" }, // 1 arg, 0 stack { C_POP, "pop" }, // 0 arg, 1 stack { C_INC, "inc" }, // 0 arg, 1 stack { C_DEC, "dec" }, // 0 arg, 1 stack { C_JMP, "jmp" }, // 0 arg, 1 stack { C_JG, "jg" }, // 0 arg, 3 stack { C_STOR, "stor" }, // 0 arg, 2 stack { C_LOAD, "load" }, // 0 arg, 1 stack { C_CALL, "call" }, // 0 arg, 1 stack { C_HLT, "hlt" }, // 0 arg, 0 stack }, };В данном объекте существует три поля: cmused — количество байт загруженного кода, memory — пространство выполнения кода, bclist — словарь мнемоников и опкодов.
Процесс ассемблирования
Перед тем как виртуальная машина сможет корректно интерпретировать байткод — его необходимо будет создать из имеющегося ассемблерного кода. Фактически, данная задача не является реальной задачей для виртуальной машины, и в идеале, функция ассемблирования должна была бы быть сброшена на отдельную программу. Но чтобы не разрывать связь кода, мы будем всё это делать в одном пространстве.
Процесс ассемблирования будет происходить в два этапа: 1) проход ассемблерного листинга для сбора меток с сохранением их позиций, 2) проход ассемблерного листинга для транслирования мнемоников в байткод. При этом, этапы должны выполняться не вместе, а последовательно для того, чтобы метки могли быть видны в любой части исполняемого кода.
Сбор меток должен постоянно фиксировать текущее местоположение в памяти кода, исходя из размера принимаемой инструкции, для сохранения корректного адреса перехода.
hashtab_t *hashtab; int32_t bindex; char buffer[BUFSIZ]; char *arg; uint8_t opcode; hashtab = hashtab_new(512); bindex = 0; // читаем каждую строку из файла input while(fgets(buffer, BUFSIZ, input) != NULL) { // считываем инструкцию, // в opcode присваиваем её номер (из enum), // в arg присваиваем аргумент инструкции arg = read_opcode(buffer, &opcode); // если инструкция не найдена -> выдаём ошибку if (opcode == C_UNDF) { hashtab_free(hashtab); return 1; } // если инструкция = комментарий или пустая строка, // тогда читаем следующую инструкцию if(opcode == C_CMNT || opcode == C_VOID) { continue; } switch(opcode) { // если инструкция = метка, тогда сохраняем текущую позицию кода case C_LABL: // аргумент не должен быть пустым и не должен быть числовой строкой if (strlen(arg) == 0 || str_is_number(arg)) { return 2; } // agr = имя метки, bindex = адрес указанной метки hashtab_set(hashtab, arg, &bindex, sizeof(bindex)); break; // если инструкция = push, тогда позиция сдвигается на +5 байт case C_PUSH: bindex += 5; break; // сдвиг всех остальных инструкций равен +1 байт default: bindex += 1; break; } } ...Код ассемблирования выглядит схожим образом, но задача отличается — теперь вместо сохранения позиций, необходимо записывать опкоды инструкций в файл исходя из имён мнемоников.
... // возвращаем указатель чтения файла на начало fseek(input, 0, SEEK_SET); // снова читаем каждую строку из файла input while(fgets(buffer, BUFSIZ, input) != NULL) { arg = read_opcode(buffer, &opcode); switch (opcode) { // если инструкция является псевдоинструкцией, // тогда пропускаем её case C_VOID: case C_CMNT: case C_LABL: break; // если это инструкция push, тогда ассемблируем её // особенным образом (за счёт наличия аргумента) case C_PUSH: // аргумент не должен быть пустым if (strlen(arg) == 0) { return 3; } compile_push(output, hashtab, arg); break; // если это обычная инструкция, тогда просто // сохраняем её опкод в файл default: fprintf(output, "%c", opcode); break; } } // завершаем процесс ассемблирования с успехом hashtab_free(hashtab); return 0;В данном коде используется хеш-таблица для сохранения меток, указывающих адрес, которая далее передаётся в функцию compile_push. Это говорит о том, что инструкция push может применять не только 32-битные числа, но также и имена меток, которые далее всё равно будут восприниматься как такие же 32-битные числа.
Код хеш-таблицы
Файл hashtab.h
#ifndef EXTCLIB_TYPE_HASHTAB_H_ #define EXTCLIB_TYPE_HASHTAB_H_ typedef struct hashtab_t hashtab_t; extern hashtab_t *hashtab_new(int size); extern void hashtab_free(hashtab_t *ht); extern void *hashtab_get(hashtab_t *ht, char *key); extern int hashtab_set(hashtab_t *ht, char *key, void *elem, int size); extern int hashtab_del(hashtab_t *ht, char *key); #endif /* EXTCLIB_TYPE_HASHTAB_H_ */ Файл hashtab.c
#include "hashtab.h" #include "list.h" #include <stdlib.h> #include <string.h> typedef struct hashtab_t { int size; list_t **table; } hashtab_t; static unsigned int strhash(char *str, size_t size); extern hashtab_t *hashtab_new(int size) { hashtab_t *ht = (hashtab_t*)malloc(sizeof(hashtab_t)); ht->size = size; ht->table = (list_t**)malloc(sizeof(list_t*)*size); for (int i = 0; i < size; ++i) { ht->table[i] = list_new(); } return ht; } extern void hashtab_free(hashtab_t *ht) { for (int i = 0; i < ht->size; ++i) { list_free(ht->table[i]); } free(ht->table); free(ht); } extern void *hashtab_get(hashtab_t *ht, char *key) { unsigned int hash = strhash(key, ht->size); size_t lenkey = strlen(key)+1; char *val; for (int i = 0; (val = list_get(ht->table[hash], i)) != NULL; ++i) { if (strcmp(val, key) == 0) { return (void*)val + lenkey; } } return NULL; } extern int hashtab_set(hashtab_t *ht, char *key, void *elem, int size) { unsigned int hash = strhash(key, ht->size); size_t lenkey = strlen(key)+1; char *val; int rc, i; for (i = 0; (val = list_get(ht->table[hash], i)) != NULL; ++i) { if (strcmp(val, key) == 0) { break; } } val = (char*)malloc(size+lenkey); memcpy(val, key, lenkey); memcpy(val+lenkey, elem, size); rc = list_set(ht->table[hash], i, val, size+lenkey); free(val); return rc; } extern int hashtab_del(hashtab_t *ht, char *key) { unsigned int hash = strhash(key, ht->size); char *val; for (int i = 0; (val = list_get(ht->table[hash], i)) != NULL; ++i) { if (strcmp(val, key) == 0) { return list_del(ht->table[hash], i); } } return -1; } // K&R 6.6 static unsigned int strhash(char *s, size_t size) { unsigned hashval; for (hashval = 0; *s != '\0'; s++) hashval = *s + 31 * hashval; return hashval % size; } Код списка (используется в реализации хеш-таблицы)
Файл list.h
#ifndef EXTCLIB_TYPE_LIST_H_ #define EXTCLIB_TYPE_LIST_H_ typedef struct list_t list_t; extern list_t *list_new(void); extern void list_free(list_t *ls); extern int list_size(list_t *ls); extern int list_find(list_t *ls, void *elem, int size); extern void *list_get(list_t *ls, int index); extern int list_set(list_t *ls, int index, void *elem, int size); extern int list_del(list_t *ls, int index); #endif /* EXTCLIB_TYPE_LIST_H_ */ Файл list.c
#include "list.h" #include <stdlib.h> #include <string.h> typedef struct list_t { int size; void *elem; struct list_t *next; } list_t; extern list_t *list_new(void) { list_t *ls = (list_t*)malloc(sizeof(list_t)); ls->size = 0; ls->elem = NULL; ls->next = NULL; return ls; } extern void list_free(list_t *ls) { list_t *next; while(ls != NULL) { next = ls->next; free(ls->elem); free(ls); ls = next; } } extern int list_find(list_t *ls, void *elem, int size) { for (int i = 0; ls->next != NULL; ++i) { ls = ls->next; if (ls->size == size && memcmp(ls->elem, elem, size) == 0) { return i; } } return -1; } extern void *list_get(list_t *ls, int index) { for (int i = 0; ls->next != NULL && i < index; ++i) { ls = ls->next; } if (ls->next == NULL) { return NULL; } return ls->next->elem; } extern int list_set(list_t *ls, int index, void *elem, int size) { list_t *root = ls; if (size <= 0) { return 1; } for (int i = 0; ls != NULL && i < index; ++i) { ls = ls->next; } if (ls == NULL) { return 2; } if (ls->next == NULL) { ls->next = list_new(); ls->next->elem = (void*)malloc(size); root->size += 1; } else { ls->next->elem = (void*)realloc(ls->next->elem, size); } ls->next->size = size; memcpy(ls->next->elem, elem, size); return 0; } extern int list_del(list_t *ls, int index) { list_t *temp; list_t *root = ls; for (int i = 0; ls->next != NULL && i < index; ++i) { ls = ls->next; } if (ls->next == NULL) { return 1; } temp = ls->next; ls->next = ls->next->next; free(temp); root->size -= 1; return 0; } extern int list_size(list_t *ls) { return ls->size; } Функция compile_push будет выглядеть достаточно просто, т.к. её основная задача — это прочитать аргумент инструкции push и в зависимости от его происхождения (метка это или оригинальное число) сохранить в байткоде 32-битное значение.
static void compile_push(FILE *output, hashtab_t *hashtab, char *arg) { uint8_t bytes[4]; int32_t *temp; int32_t num; // пытаемся получить по аргументу адрес метки temp = hashtab_get(hashtab, arg); // если в хеш-таблице не содержится метки по такому названию, // тогда интерпретируем аргумент как число if (temp == NULL) { num = atoi(arg); // иначе, воспринимаем полученный результат из хеш-таблицы // как адрес метки (в любом случае - это число) } else { num = *temp; } // Преобразуем 32-битное число в 4 байта (т.е. в четыре 8-битных числа) // и записываем [инструкцию + 4 байта] в файл split_32bits_to_8bits((uint32_t)num, bytes); fprintf(output, "%c%c%c%c%c", C_PUSH, bytes[0], bytes[1], bytes[2], bytes[3]); }И финальной важной функцией в нашем разборе является функция чтения строки, вычерпывающей инструкцию с аргументом.
static char *read_opcode(char *line, uint8_t *opcode) { char *ptr; // игнорируем пустые символы до тех пор, // пока не дойдём до читаемого символа line = str_trim_spaces(line); // игнорируем все читаемые символы до тех пор, // пока не дойдём до нечитаемого символа. // после прохода заменяем нечитаемый символ на '\0' (окончание строки) ptr = str_set_end(line); // в `line` теперь хранится имя инструкции (мнемоник) // по мнемонику инструкции пытаемся найти его опкод *opcode = find_opcode(line); switch(*opcode) { // Если инструкция = push или labl, // тогда обрабатываем их case C_PUSH: case C_LABL: break; // В ином случае обработка не требуется, // т.к. у всех остальных инструкций аргументы отсутствуют default: return NULL; } // в `line` теперь будет храниться аргумент инструкции line = str_trim_spaces(++ptr); str_set_end(line); // возвращаем аргумент return line; }Оставшиеся функции
static uint8_t find_opcode(char *str) { uint8_t opcode; opcode = C_UNDF; for (int i = 0; i < CVM_KERNEL_ISIZE; ++i) { if (strcmp(str_to_lower(str), VM.bclist[i].mnem) == 0) { opcode = VM.bclist[i].bcode; break; } } return opcode; } static int str_is_number(char *str) { int len = strlen(str); if (len == 0) { return 0; } for (int i = 0; i < len; ++i) { if (!isdigit(str[i])) { return 0; } } return 1; } static char *str_to_lower(char *str) { int len = strlen(str); for (int i = 0; i < len; ++i) { str[i] = tolower(str[i]); } return str; } static char *str_trim_spaces(char *str) { while(isspace(*str)) { ++str; } return str; } static char *str_set_end(char *str) { char *ptr = str; while(!isspace(*ptr)) { ++ptr; } *ptr = '\0'; return ptr; } static void split_32bits_to_8bits(uint32_t num, uint8_t *bytes) { for (int i = 0; i < 4; ++i) { bytes[i] = (uint8_t)(num >> (24 - i * 8)); } }Проверяем результат ассемблирования
В этой проверке нам не нужно проверять все инструкции, т.к. мы смотрим на результат ассемблирования, а не на корректность исполнения байткода. В таком случае, достаточно лишь проверить все уникальные инструкции (т.е. всего одну — push), все псевдоинструкции (метку, комментарий и пустую строку), а также любую одну обычную инструкцию (по типу inc).
; это какая-то константа push 1 ; это предположительное начало программы labl start push start ; это какая-то логика push 10 inc В результате мы получим следующий байткод, где 0A 00 00 00 01 = push 1, 0A 00 00 00 05 = push start (где start = 5, т.к. размер инструкции push = 5 байт), 0A 00 00 0A = push 10, 0C = inc.
$ hexdump --format '16/1 "%02X " "\n"' main.bcd > 0A 00 00 00 01 0A 00 00 00 05 0A 00 00 00 0A 0CПроверить данный результат можно при помощи репозитория cvm, скачав, скомпилировав и запустив процедуру ассемблирования виртуальной машины.
$ git clone https://github.com/number571/cvm $ cd cvm && make build $ ./cvm build main.asm -o main.bcdПроцесс интерпретации
Интерпретация байткода является основной функцией виртуальной машины, и на деле — наиболее интересной. В ней необходимо будет анализировать принимаемые инструкции и в зависимости от их опкодов совершать конкретные действия.
Предположим, что мы вгрузили в память виртуальной машины весь полученный байткод из предыдущего этапа ассемблирования. В таком случае, VM.memory будет содержать непосредственно байткод, а VM.cmused количество байт нашего кода.
Основной код интерпретации байткода выглядит следующим образом:
stack_t *stack; uint8_t opcode; int32_t mi; int retcode; stack = stack_new(CVM_KERNEL_SMEMORY, sizeof(int32_t)); mi = 0; // позиция исполнения в коде while(mi < VM.cmused) { opcode = VM.memory[mi++]; switch(opcode) { // jg, jmp, call помимо получения значений из стека, // необходимо также изменять позицию исполнения mi case C_JG: retcode = exec_jmpif(stack, &mi); break; case C_JMP: retcode = exec_jmp(stack, &mi); break; case C_CALL: retcode = exec_call(stack, &mi); break; // push изменяет позицию исполнения mi константно на +4 case C_PUSH: retcode = exec_push(stack, &mi); break; case C_POP: retcode = exec_pop(stack); break; // inc, dec функционально работают схожим образом, но для конкретики // функции exec_incdec нужно знать что применять -> +1 или -1, // поэтому передаётся также opcode case C_INC: case C_DEC: retcode = exec_incdec(stack, opcode); break; case C_STOR: retcode = exec_stor(stack); break; case C_LOAD: retcode = exec_load(stack); break; case C_HLT: mi = VM.cmused; // для завершения цикла retcode = 0; // завершение - удачно break; // опкод не был определён виртуальной машиной default: retcode = wrap_return(C_UNDF, 1); break; } // исполнение было завершено с ошибкой if (retcode != 0) { stack_free(stack); return retcode; } } ...Код стека
Файл stack.h
#ifndef EXTCLIB_TYPE_STACK_H_ #define EXTCLIB_TYPE_STACK_H_ typedef struct stack_t stack_t; extern stack_t *stack_new(int size, int valsize); extern void stack_free(stack_t *st); extern int stack_size(stack_t *st); extern int stack_push(stack_t *st, void *elem); extern void *stack_pop(stack_t *st); extern int stack_set(stack_t *st, int index, void *elem); extern void *stack_get(stack_t *st, int index); #endif /* EXTCLIB_TYPE_STACK_H_ */ Файл stack.c
#include "stack.h" #include <stdlib.h> #include <string.h> typedef struct stack_t { int size; int valsize; int currpos; char *buffer; } stack_t; extern stack_t *stack_new(int size, int valsize) { stack_t *st = (stack_t*)malloc(sizeof(stack_t)); st->size = size; st->valsize = valsize; st->currpos = 0; st->buffer = (char*)malloc(size*valsize); return st; } extern void stack_free(stack_t *st) { free(st->buffer); free(st); } extern int stack_size(stack_t *st) { return st->currpos; } extern int stack_push(stack_t *st, void *elem) { if (st->currpos == st->size) { return 1; } memcpy(st->buffer + st->currpos * st->valsize, elem, st->valsize); st->currpos += 1; return 0; } extern void *stack_pop(stack_t *st) { if (st->currpos == 0) { return NULL; } st->currpos -= 1; return (void*)st->buffer + st->currpos * st->valsize; } extern int stack_set(stack_t *st, int index, void *elem) { if (index < 0 || index >= st->size) { return 1; } memcpy(st->buffer + index * st->valsize, elem, st->valsize); return 0; } extern void *stack_get(stack_t *st, int index) { if (index < 0 || index >= st->size) { return NULL; } return (void*)st->buffer + index * st->valsize; } После исполнения основной части нам необходимо получить какой-то результат. Результат будет сохранён в стеке, а потому его нужно куда-то выгрузить.
... mi = stack_size(stack); *output = (int32_t*)malloc(sizeof(int32_t)*(mi+1)); // первое число массива output - это количество значений в стеке (*output)[0] = mi; // все последующие числа - это сами значения стека for (int i = 1; i <= mi; ++i) { (*output)[i] = *(int32_t*)stack_pop(stack); } // успешное исполнение stack_free(stack); return 0;Всё что нам остаётся — это посмотреть функции исполнения конкретного опкода. Начнём с функций безусловного и условного переходов.
extern int exec_jmp(stack_t *stack, int32_t *mi) { int32_t num; // стек не должен быть пустым if (stack_size(stack) == 0) { return wrap_return(C_JMP, 1); } // выгружаем значение из стека - оно будет являться // адресом, на который нужно будет 'сджампиться' num = *(int32_t*)stack_pop(stack); // если адрес отрицательный или он переходит границу памяти, // тогда это является ошибкой исполнения if (num < 0 || num >= VM.cmused) { return wrap_return(C_JMP, 3); } // меняем позицию исполнения *mi = num; return 0; }Похожим образом работает условный переход, но с выгрузкой двух значений из стека и дополнительным условием.
static int exec_jmpif(stack_t *stack, int32_t *mi) { int32_t num, x, y; // стек должен содержать как минимум 3 элемента if (stack_size(stack) < 3) { return wrap_return(opcode, 1); } num = *(int32_t*)stack_pop(stack); if (num < 0 || num >= VM.cmused) { return wrap_return(opcode, 3); } x = *(int32_t*)stack_pop(stack); y = *(int32_t*)stack_pop(stack); if (y > x) { *mi = num; } return 0; }Инструкция call — это фактически jmp, но с процедурой сохранения текущего адреса исполнения в стек.
static int exec_call(stack_t *stack, int32_t *mi) { int retcode; int32_t num; // сохраняем текущую позицию исполнения в переменную // *не сохраняем сразу в стек для того, чтобы jmp не восприняла // запушенное значение как адрес перехода num = *mi; // выполняем jmp retcode = exec_jmp(stack, mi); if (retcode != 0) { // & 0xFF - сохраняет ошибку из C_JMP, но без указания // того, что это C_JMP ошибка (для перезаписи на C_CALL) return wrap_return(C_CALL, retcode & 0xFF); } // пушим в стек сохранённую позицию исполнения stack_push(stack, &num); return 0; }Далее идут классические инструкции push и pop.
static int exec_push(stack_t *stack, int32_t *mi) { int32_t num; uint8_t bytes[4]; // переполненность стека = ошибка if (stack_size(stack) == CVM_KERNEL_SMEMORY) { return wrap_return(C_PUSH, 1); } // копируем 4 байта из памяти memcpy(bytes, VM.memory + *mi, 4); *mi += 4; // воспринимаем их как одно 32-битное число // с последующим сохранением в стек num = (int32_t)join_8bits_to_32bits(bytes); stack_push(stack, &num); return 0; } static int exec_pop(stack_t *stack) { // пустота стека = ошибка if (stack_size(stack) == 0) { return wrap_return(C_POP, 1); } // удаляем число из стека stack_pop(stack); return 0; }Одни из самых простых инструкций — это инструкции с полезным выполнением по типу inc и dec (а также add, sub, mul, div, mod и прочие, если бы мы их реализовывали). Они все работают схожим образом, отличием является лишь количество выгружаемых значений из стека и сама применяемая операция.
static int exec_incdec(stack_t *stack, uint8_t opcode) { int32_t x; // пустота стека = ошибка if (stack_size(stack) == 0) { return wrap_return(opcode, 1); } // выгружаем значение из стека x = *(int32_t*)stack_pop(stack); // производим операцию switch(opcode) { case C_INC: ++x; break; case C_DEC: --x; break; default: return wrap_return(opcode, 1); } // сохраняем результат в стек stack_push(stack, &x); return 0; }Самыми сложными инструкциями здесь являются stor и load. В большей мере это связано из-за того, что они обходят среду исполнения чистого стека и воспринимают его как обычный массив. А потому могут индексироваться по нему, сохраняя или выгружая нужные значения.
static int exec_stor(stack_t *stack) { int32_t num1, num2; // нужно как минимум два значения в стеке if (stack_size(stack) < 2) { return wrap_return(C_STOR, 1); } num1 = *(int32_t*)stack_pop(stack); num2 = *(int32_t*)stack_pop(stack); // отрицательное число является корректным, т.к. служит для // определения относительности или абсолютности индекса в стеке // *абсолютность относительно нуля // *относительность относительно текущего размера стека // (извиняюсь за тавтологию) if (num1 < 0) { // относительный индекс преобразуем в абсолютный num1 = stack_size(stack) + num1; // сохранение отрицательного числа = ошибка if (num1 < 0) { return wrap_return(C_STOR, 2); } } else { // превышение стека = ошибка if (num1 >= stack_size(stack)) { return wrap_return(C_STOR, 3); } } // то же самое выполняем с вторым числом if (num2 < 0) { num2 = stack_size(stack) + num2; if (num2 < 0) { return wrap_return(C_STOR, 4); } } else { if (num2 >= stack_size(stack)) { return wrap_return(C_STOR, 5); } } // По индексу второго числа получаем хранимое значение в стеке num2 = *(int32_t*)stack_get(stack, num2); // Сохраняем полученное значение по индексу первого числа stack_set(stack, num1, &num2); return 0; }Инструкция load работает схожим образом со stor, но сохраняет полученное значение не по индексу, а в конец стека. Поэтому требует лишь одно значение из стека, а не два.
static int exec_load(stack_t *stack) { int32_t num; // стек должен быть непустым if (stack_size(stack) == 0) { return wrap_return(C_LOAD, 1); } // определяем индекс в стеке по логике exec_stor num = *(int32_t*)stack_pop(stack); if (num < 0) { num = stack_size(stack) + num; if (num < 0) { return wrap_return(C_LOAD, 2); } } else { if (num >= stack_size(stack)) { return wrap_return(C_LOAD, 3); } } // по индексу получаем хранимое значение в стеке num = *(int32_t*)stack_get(stack, num); // пушим полученное значение в стек (тобишь в конец стека) stack_push(stack, &num); return 0; }Оставшиеся функции
static uint32_t join_8bits_to_32bits(uint8_t *bytes) { uint32_t num; for (uint8_t *ptr = bytes; ptr < bytes + 4; ++ptr) { num = (num << 8) | *ptr; } return num; } static uint16_t wrap_return(uint8_t x, uint8_t y) { return ((uint16_t)x << 8) | y; } Проверяем результат интерпретации
Давайте для начала протестируем корректность исполнения на старом байткоде, который был получен в ходе процедуры ассемблирования.
$ ./cvm run main.bcd > 11,5,1Из стека мы получаем значения в обратном порядке (т.к. используется pop), а потому первый выполненный push с единицей у нас вывелся в конце. Число пять — это адрес, на который указывала метка start. А число 11 — это результат инструкции inc на push 10. Таким образом, мы получили корректный результат.
Но в отличие от проверки на результат ассемблирования, мы к сожалению не можем быть уверены в полной корректности результата интерпретации, т.к. требуется проверить все возможные инструкции. Было бы хорошо написать какой-нибудь алгоритм по типу факториала, но проблема заключается в том, что у нас отсутствует операция умножения. Единственный способ её реализовать — так это через множество операций инкрементирования. Но всё это будет сложно и муторно делать.
В результате, у нас присутствует два выбора: 1) либо мы расширяем количество инструкций, добавляя mul, 2) либо мы пишем язык высокого уровня, который бы самостоятельно мог создавать операцию mul из inc. В реальности существует уже оба решения. В репозитории cvm существуют дополнительные инструкции, определяемые наличием CVM_KERNEL_IAPPEND. В репозитории allang находится LISP-подобный язык программирования, который использует только 10 вышеописанных и реализованных инструкций.
Для начала попробуем проверить виртуальную машину при помощи полученного кода (в ходе трансляции) из языка ALLang, а далее при помощи расширения инструкций. Алгоритмом будет являться факториал от пяти.
Используем высокоуровневый язык
Более подробно о языке ALLang можно узнать в статье: Бесполезный и красиво ужасный язык программирования ALLang
(include assembly lib/cvm/init.asm) (include source lib/all/lr.all lib/all/ret.all lib/all/dec.all lib/all/mul.all) (define (main x) (fact x)) ; f(x) = 1, if x < 1 ; f(x) = x * f(x-1) (define (fact x) (if (lr x 1) (ret 1) (mul x (fact (dec x)))))Полученный ассемблерный листинг (более 700 строк кода)
; cvm может передавать значения в стек через свои аргументы; ; этот принцип использует allang для передачи n-ого количества ; аргументов в свою функцию main ; поэтому данный push был добавлен самостоятельно, чтобы ; не усложнять понимание работы виртуальной машины push 5 labl _init push main call hlt labl _gr push -3 load push -3 load push _if_gr jg labl _else_gr push 0 push _end_gr jmp labl _if_gr push 1 labl _end_gr push -1 push -4 stor pop jmp labl eq push -3 load push -3 load push -2 load push -2 load push _gr call pop push 0 push _if_0 jg push _else_0 jmp labl _if_0 push 0 push ret call push _end_0 jmp labl _else_0 push -1 load push -3 load push _gr call pop push 0 push _if_1 jg push _else_1 jmp labl _if_1 push 0 push ret call push _end_1 jmp labl _else_1 push 1 push ret call labl _end_1 labl _end_0 push -1 push -6 stor pop pop pop jmp labl _inc push -2 load inc push -1 push -3 stor pop jmp labl inc push -2 load push -1 load push _inc call push -1 push -4 stor pop pop jmp labl _dec push -2 load dec push -1 push -3 stor pop jmp labl dec push -2 load push -1 load push _dec call push -1 push -4 stor pop pop jmp labl ret push -2 load push -1 load push inc call push dec call push -1 push -4 stor pop pop jmp labl not push -2 load push -1 load push 0 push eq call pop push 0 push _if_2 jg push _else_2 jmp labl _if_2 push 1 push ret call push _end_2 jmp labl _else_2 push 0 push ret call labl _end_2 push -1 push -4 stor pop pop jmp labl gr push -3 load push -3 load push -2 load push -2 load push _gr call pop push -1 push -6 stor pop pop pop jmp labl neq push -3 load push -3 load push -2 load push -2 load push eq call pop push not call push -1 push -6 stor pop pop pop jmp labl or push -3 load push -3 load push -2 load push 0 push neq call pop push 0 push _if_3 jg push _else_3 jmp labl _if_3 push 1 push ret call push _end_3 jmp labl _else_3 push -1 load push 0 push neq call pop push 0 push _if_4 jg push _else_4 jmp labl _if_4 push 1 push ret call push _end_4 jmp labl _else_4 push 0 push ret call labl _end_4 labl _end_3 push -1 push -6 stor pop pop pop jmp labl ge push -3 load push -3 load push -2 load push -2 load push eq call pop push -3 load push -3 load push gr call pop push or call pop push -1 push -6 stor pop pop pop jmp labl lr push -3 load push -3 load push -2 load push -2 load push ge call pop push not call push -1 push -6 stor pop pop pop jmp labl add push -3 load push -3 load push -1 load push 0 push eq call pop push 0 push _if_5 jg push _else_5 jmp labl _if_5 push -2 load push ret call push _end_5 jmp labl _else_5 push -1 load push 0 push lr call pop push 0 push _if_6 jg push _else_6 jmp labl _if_6 push -2 load push -2 load push inc call push add call pop push dec call push _end_6 jmp labl _else_6 push -2 load push -2 load push dec call push add call pop push inc call labl _end_6 labl _end_5 push -1 push -6 stor pop pop pop jmp labl sub push -3 load push -3 load push -1 load push 0 push eq call pop push 0 push _if_7 jg push _else_7 jmp labl _if_7 push -2 load push ret call push _end_7 jmp labl _else_7 push -1 load push 0 push lr call pop push 0 push _if_8 jg push _else_8 jmp labl _if_8 push -2 load push -2 load push inc call push sub call pop push inc call push _end_8 jmp labl _else_8 push -2 load push -2 load push dec call push sub call pop push dec call labl _end_8 labl _end_7 push -1 push -6 stor pop pop pop jmp labl neg push -2 load push 0 push -2 load push sub call pop push -1 push -4 stor pop pop jmp labl abs push -2 load push -1 load push 0 push lr call pop push 0 push _if_9 jg push _else_9 jmp labl _if_9 push -1 load push neg call push _end_9 jmp labl _else_9 push -1 load push ret call labl _end_9 push -1 push -4 stor pop pop jmp labl and push -3 load push -3 load push -2 load push 0 push neq call pop push 0 push _if_10 jg push _else_10 jmp labl _if_10 push -1 load push 0 push neq call pop push 0 push _if_11 jg push _else_11 jmp labl _if_11 push 1 push ret call push _end_11 jmp labl _else_11 push 0 push ret call labl _end_11 push _end_10 jmp labl _else_10 push 0 push ret call labl _end_10 push -1 push -6 stor pop pop pop jmp labl xor push -3 load push -3 load push -2 load push not call push -2 load push and call pop push -3 load push -3 load push not call push and call pop push or call pop push -1 push -6 stor pop pop pop jmp labl mul push -3 load push -3 load push -2 load push 0 push lr call pop push -2 load push 0 push lr call pop push xor call pop push 0 push _if_12 jg push _else_12 jmp labl _if_12 push -2 load push abs call push -2 load push abs call push mul call pop push neg call push _end_12 jmp labl _else_12 push -1 load push 0 push eq call pop push 0 push _if_13 jg push _else_13 jmp labl _if_13 push 0 push ret call push _end_13 jmp labl _else_13 push -2 load push abs call push -3 load push abs call push -3 load push abs call push dec call push mul call pop push add call pop labl _end_13 labl _end_12 push -1 push -6 stor pop pop pop jmp labl main push -2 load push -1 load push fact call push -1 push -4 stor pop pop jmp labl fact push -2 load push -1 load push 1 push lr call pop push 0 push _if_14 jg push _else_14 jmp labl _if_14 push 1 push ret call push _end_14 jmp labl _else_14 push -1 load push -2 load push dec call push fact call push mul call pop labl _end_14 push -1 push -4 stor pop pop jmp $ ./cvm build main.asm -o main.bcd $ ./cvm run main.bcd > 120hexdump main.bcd
$ hexdump --format '16/1 "%02X " "\n"' main.bcd 0A 00 00 00 05 0A 00 00 06 D1 1C 1D 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A 00 00 00 29 0F 0A 00 00 00 00 0A 00 00 00 2E 0E 0A 00 00 00 01 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 00 0C 1C 0B 0A 00 00 00 00 0A 00 00 00 6B 0F 0A 00 00 00 7C 0E 0A 00 00 00 00 0A 00 00 01 33 1C 0A 00 00 00 BC 0E 0A FF FF FF FF 1B 0A FF FF FF FD 1B 0A 00 00 00 0C 1C 0B 0A 00 00 00 00 0A 00 00 00 A0 0F 0A 00 00 00 B1 0E 0A 00 00 00 00 0A 00 00 01 33 1C 0A 00 00 00 BC 0E 0A 00 00 00 01 0A 00 00 01 33 1C 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FE 1B 0C 0A FF FF FF FF 0A FF FF FF FD 1A 0B 0E 0A FF FF FF FE 1B 0A FF FF FF FF 1B 0A 00 00 00 CB 1C 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0B 0E 0A FF FF FF FE 1B 0D 0A FF FF FF FF 0A FF FF FF FD 1A 0B 0E 0A FF FF FF FE 1B 0A FF FF FF FF 1B 0A 00 00 00 FF 1C 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0B 0E 0A FF FF FF FE 1B 0A FF FF FF FF 1B 0A 00 00 00 DF 1C 0A 00 00 01 13 1C 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0B 0E 0A FF FF FF FE 1B 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 00 3B 1C 0B 0A 00 00 00 00 0A 00 00 01 82 0F 0A 00 00 01 93 0E 0A 00 00 00 01 0A 00 00 01 33 1C 0A 00 00 01 9E 0E 0A 00 00 00 00 0A 00 00 01 33 1C 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 00 0C 1C 0B 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 00 3B 1C 0B 0A 00 00 01 59 1C 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A 00 00 00 00 0A 00 00 01 DA 1C 0B 0A 00 00 00 00 0A 00 00 02 3D 0F 0A 00 00 02 4E 0E 0A 00 00 00 01 0A 00 00 01 33 1C 0A 00 00 02 8D 0E 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 01 DA 1C 0B 0A 00 00 00 00 0A 00 00 02 71 0F 0A 00 00 02 82 0E 0A 00 00 00 01 0A 00 00 01 33 1C 0A 00 00 02 8D 0E 0A 00 00 00 00 0A 00 00 01 33 1C 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 00 3B 1C 0B 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A 00 00 01 AC 1C 0B 0A 00 00 02 0E 1C 0B 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 02 9C 1C 0B 0A 00 00 01 59 1C 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 00 3B 1C 0B 0A 00 00 00 00 0A 00 00 03 47 0F 0A 00 00 03 59 0E 0A FF FF FF FE 1B 0A 00 00 01 33 1C 0A 00 00 03 C0 0E 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 02 E4 1C 0B 0A 00 00 00 00 0A 00 00 03 7C 0F 0A 00 00 03 A1 0E 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 00 DF 1C 0A 00 00 03 18 1C 0B 0A 00 00 01 13 1C 0A 00 00 03 C0 0E 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 01 13 1C 0A 00 00 03 18 1C 0B 0A 00 00 00 DF 1C 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 00 3B 1C 0B 0A 00 00 00 00 0A 00 00 03 FE 0F 0A 00 00 04 10 0E 0A FF FF FF FE 1B 0A 00 00 01 33 1C 0A 00 00 04 77 0E 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 02 E4 1C 0B 0A 00 00 00 00 0A 00 00 04 33 0F 0A 00 00 04 58 0E 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 00 DF 1C 0A 00 00 03 CF 1C 0B 0A 00 00 00 DF 1C 0A 00 00 04 77 0E 0A FF FF FF FE 1B 0A FF FF FF FE 1B 0A 00 00 01 13 1C 0A 00 00 03 CF 1C 0B 0A 00 00 01 13 1C 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FE 1B 0A 00 00 00 00 0A FF FF FF FE 1B 0A 00 00 03 CF 1C 0B 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0B 0E 0A FF FF FF FE 1B 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 02 E4 1C 0B 0A 00 00 00 00 0A 00 00 04 D5 0F 0A 00 00 04 E7 0E 0A FF FF FF FF 1B 0A 00 00 04 86 1C 0A 00 00 04 F3 0E 0A FF FF FF FF 1B 0A 00 00 01 33 1C 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A 00 00 00 00 0A 00 00 01 DA 1C 0B 0A 00 00 00 00 0A 00 00 05 30 0F 0A 00 00 05 75 0E 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 01 DA 1C 0B 0A 00 00 00 00 0A 00 00 05 53 0F 0A 00 00 05 64 0E 0A 00 00 00 01 0A 00 00 01 33 1C 0A 00 00 05 6F 0E 0A 00 00 00 00 0A 00 00 01 33 1C 0A 00 00 05 80 0E 0A 00 00 00 00 0A 00 00 01 33 1C 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A 00 00 01 59 1C 0A FF FF FF FE 1B 0A 00 00 05 01 1C 0B 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A 00 00 01 59 1C 0A 00 00 05 01 1C 0B 0A 00 00 02 0E 1C 0B 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FD 1B 0A FF FF FF FD 1B 0A FF FF FF FE 1B 0A 00 00 00 00 0A 00 00 02 E4 1C 0B 0A FF FF FF FE 1B 0A 00 00 00 00 0A 00 00 02 E4 1C 0B 0A 00 00 05 8F 1C 0B 0A 00 00 00 00 0A 00 00 06 2B 0F 0A 00 00 06 56 0E 0A FF FF FF FE 1B 0A 00 00 04 AC 1C 0A FF FF FF FE 1B 0A 00 00 04 AC 1C 0A 00 00 05 E3 1C 0B 0A 00 00 04 86 1C 0A 00 00 06 C2 0E 0A FF FF FF FF 1B 0A 00 00 00 00 0A 00 00 00 3B 1C 0B 0A 00 00 00 00 0A 00 00 06 79 0F 0A 00 00 06 8A 0E 0A 00 00 00 00 0A 00 00 01 33 1C 0A 00 00 06 C2 0E 0A FF FF FF FE 1B 0A 00 00 04 AC 1C 0A FF FF FF FD 1B 0A 00 00 04 AC 1C 0A FF FF FF FD 1B 0A 00 00 04 AC 1C 0A 00 00 01 13 1C 0A 00 00 05 E3 1C 0B 0A 00 00 03 18 1C 0B 0A FF FF FF FF 0A FF FF FF FA 1A 0B 0B 0B 0E 0A FF FF FF FE 1B 0A FF FF FF FF 1B 0A 00 00 06 F1 1C 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0B 0E 0A FF FF FF FE 1B 0A FF FF FF FF 1B 0A 00 00 00 01 0A 00 00 02 E4 1C 0B 0A 00 00 00 00 0A 00 00 07 1A 0F 0A 00 00 07 2B 0E 0A 00 00 00 01 0A 00 00 01 33 1C 0A 00 00 07 4A 0E 0A FF FF FF FF 1B 0A FF FF FF FE 1B 0A 00 00 01 13 1C 0A 00 00 06 F1 1C 0A 00 00 05 E3 1C 0B 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0B 0EРезультат корректный.
Используем расширение инструкций
labl start ; A <- 5 push 5 push fact call hlt ; A <- fact(A) labl fact ; B <- A push -2 load labl _fact_for ; IF 2 > B push 2 push -2 load push _fact_end jg ; ELSE ; B <- B - 1 push -1 load dec push -1 push -2 stor pop ; A <- A * B push -3 load push -2 load mul push -1 push -4 stor pop push _fact_for jmp labl _fact_end ; return pop jmp $ ./cvm build main.asm -o main.bcd $ ./cvm run main.bcd > 120Получаем такой же результат, а это значит, что всё сработало верно.
hexdump main.bcd
$ hexdump --format '16/1 "%02X " "\n"' main.bcd 0A 00 00 00 05 0A 00 00 00 0C 1C 1D 0A FF FF FF FE 1B 0A 00 00 00 02 0A FF FF FF FE 1B 0A 00 00 00 55 0F 0A FF FF FF FF 1B 0D 0A FF FF FF FF 0A FF FF FF FE 1A 0B 0A FF FF FF FD 1B 0A FF FF FF FE 1B C0 0A FF FF FF FF 0A FF FF FF FC 1A 0B 0A 00 00 00 12 0E 0B 0EЗаключение
В результате мы смогли написать виртуальную машину, которая не только исполняет байткод, но также и обладает собственным языком ассемблера. Благодаря этому, на основе виртуальной машины, и в частности на основе языка ассемблера, могут строиться далее уже высокоуровневые языки программирования (по типу представленного ранее ALLang). Весь исходный код можно найти в файле cvmkernel.c репозитория cvm.
ссылка на оригинал статьи https://habr.com/ru/articles/870938/
Добавить комментарий