Недавно, в целях исследования теории алгоритмов и машин Тьюринга у меня появилась идея написать свою простенькую виртуальную машину (далее ВМ), со своим байт-кодом, и маленьким языком программирования(ЯП). Основное применение ВМ – выполнение одной функции(например декодирование данных) запрограммированное в байт-коде функции.
В качестве ЯП был выбран Тьюринг-полный и простой язык BrainFuck, т.к. для начала его вполне хватит, потом можно его усложнить
Архитектура ВМ
- Первое, что хотелось бы отметить, ВМ должна быть самой простой, по этому, все что она будет уметь это делать преобразование над данными в памяти, поэтому она имеет один(два в будущем) регистра для выполнение базовых битовых, арифметических, логических операций.
- Второе, тип данных – классический байт (И не надо тут говорить, что в начале было слово. Ибо, в начале был байт, а потом было слово). И инструкции(байт-код) тоже будут длинной 8 бит, т.е. всего можно сделать 256 инструкций, с разными кодами. Хочу заметить, что, как говорил Бабаян (http://habrahabr.ru/post/205168/, habrahabr.ru/post/214377/) железо(ВМ) должно быть связано с алгоритмом(задачей), которую оно выполняет и языком программирования.
Третее, список инструкций:
- перейти к следующей ячейке r_move_forward
- перейти к предыдущей ячейке r_move_backward
- увеличить значение в текущей ячейке на 1 r_increment
- уменьшить значение в текущей ячейке на 1 r_decrement
- напечатать значение из текущей ячейки r_print_char
- ввести извне значение и сохранить в текущей ячейке r_get_char
- проверка значения в текущей ячейки на ==0, !=0 r_if, r_if_not
- goto r_goto_address
- конец программы r_end
Далее пойдут интересные куски кода самой VM (полностью тут). Написан на С, но с множеством define вставок, по этому для понимания базового синтаксиса, который использовался необходимо прочитать habrahabr.ru/post/239505/ и знать С.
method(void, executeFunction, RVirtualMachine), RVirtualFunction *function) {
uint64_t result = 0;
// копируем указатель на исполняемую функцию
object->functionExecuting = function;
// выводим имя функции
RPrintf("RVM. Start Executing Function : "%s"nn", function->name->baseString);
// задаем счетчик тактов в 0
object->tickCount = 0;
// очищаем память (1кБ)
$(object, m(setUpDataBlock, RVirtualMachine)) );
// задаем регистр данных как указательна первый елемент массива
object->dataRegister = &object->memory->array[0];
// задаем регистр команд, как указатель на первый елемент тела функции в байт-коде
object->functionStartAddress = master(object->functionExecuting, RByteArray)->array;
object->command = object->functionStartAddress;
// выполняем по одному байт-коду, пока результат не 1,
// или не установлен прерывающий флаг
while(object->breakFlag == 0 && result != 1) {
result = $(object, m(executeCode, RVirtualMachine)));
// инкрементим кол-во тактов
++object->tickCount;
}
// в конце выполнения – выводим снимок памяти
RPrintf("nRVM. End Executing Function : "%s"n", function->name->baseString);
RPrintf("Ticks count for executing is - %qun", object->tickCount);
RPrintf("Memory snapshot : {");
$(object->memory, p(RByteArray)) );
RPrintf("n } end memory snapshotnn");
}
Далее метод, исполняет одиночный байт-код:
method(uint64_t, executeCode, RVirtualMachine)) {
switch(*object->command) {
case r_increment : {
// инкрементируем регистр данных
++(*object->dataRegister);
++object->command;
} break;
case r_decrement : {
// отнимаем у регистра данных 1
--(*object->dataRegister);
++object->command;
} break;
// выводы
// это пока зарезервировано
case r_print_0_string : {
RPrintf("%sn", object->dataRegister);
while(*object->dataRegister != 0) {
++object->dataRegister;
++object->tickCount;
}
++object->command;
} break;
// выводим символ, если не служебный и не ascii печатаем в HEX
case r_print_char : {
if(*object->dataRegister == 'n'
|| *object->dataRegister == 'r'
|| *object->dataRegister == 't') {
RPrintf("%c", *object->dataRegister);
} else if(*object->dataRegister < 32
|| *object->dataRegister > 127) {
RPrintf("%02x ", *object->dataRegister);
} else {
RPrintf("%c", *object->dataRegister);
}
++object->command;
} break;
// ввод
case r_get_char : {
*object->dataRegister = getchar();
++object->command;
} break;
// сдвиги (в усложненной версии будут ненужны)
case r_move_forward : {
// инкрементируем УКАЗАТЕЛЬ на данные
++object->dataRegister;
++object->command;
} break;
case r_move_backward : {
// двигаемся назад на одну ячейку
--object->dataRegister;
++object->command;
} break;
case r_goto_address : {
// присваеваем регистру команд указатель, на величину,
// следующую за командой goto.
// Адрес, относительный указателя на начало функции
object->command = object->functionStartAddress + *(++object->command);
} break;
case r_if : {
if((*object->dataRegister) != 0) {
// правдивая инструкция
object->command += 3; // 3 – из-за байта в аргументе goto
} else {
// ложная инструкция
++object->command;
}
} break;
case r_if_not : { // добавлено тоже исключительно для brainfuck далее будет выпилена
if((*object->dataRegister) == 0) {
// аналогично IF
object->command += 3;
} else {
++object->command;
}
} break;
// конец работы
case r_end : {
RPrintf("nEnd work of RVM.n");
return 1;
}
// очень-очень плохой байт-код
default: {
RPrintf("RVM. Warning, default case, unhalted resultn");
return 1;
}
}
return 0;
}
Как можно увидеть, инструкция if имеет интересное строение, т.е. if (false_instruction, reserved byte, true_instruction) место зарезервировано под аргумент иструкции goto, таким образом можно легко строить циклы, основанные на инструкция if и goto.
Далее сам компилятор (адский процессинг строк на С стал чуть менее адским в RayFoundation):
Основной метод для процессинга brainfuck-строки в rasm байт-код:
method(RVirtualFunction *, createFunctionFromBrainFuckSourceCode, RVirtualCompiler), const RCString *sourceCode) {
if(sourceCode->size != 0) {
RVirtualFunction *function = $(NULL, c(RVirtualFunction)) );
// копируем исходники
object->code = $(sourceCode, m(copy, RCString)) );
// инициализируем рабочие переменные
object->deltaToNext = 0;
object->toPrev = 0;
// задаем имя и тело
function->name = $(object, m(getFunctionName, RVirtualCompiler)) );
master(function, RByteArray) = $(object, m(getBrainFuckFunctionBody, RVirtualCompiler)) );
// уничтожаем рабочие исходники
$(object->code, d(RCString)) );
RPrintf("RVC. Brainfuck. Processed lines - %qu of %qu, in %qu iterations n", object->lines, object->numberOfLines + 1, object->iterator);
// вывод байт-кода для отладки
// $(function, p(RVirtualFunction)) );
return function;
} else {
RPrintf("Error. RVC. Bad virtual-code sizen");
}
return NULL;
}
Теперь метод получение имени:
method(RCString *, getFunctionName, RVirtualCompiler)) {
if(object->code->size != 0){
uint64_t place;
// находим символ начала кода - ':'
place = indexOfFirstCharacterCString(object->code->baseString, object->code->size, ':');
// копируем подстроку с именем
RCString *name = $(object->code, m(getSubstringInRange, RCString)), makeRRange(0, place));
// удаляем имя и ':' символ из исходников
$(object->code, m(deleteInRange, RCString)), makeRRange(0, place + 1));
// удаляем все пробелы
$(object->code, m(deleteAllCharacters, RCString)), ' ');
// считаем количество строк
object->numberOfLines = $(object->code, m(numberOfRepetitions, RCString)), 'n');
return name;
}
return NULL;
}
Метод получения тела функции:
method(RByteArray *, getBrainFuckFunctionBody, RVirtualCompiler)) {
RByteArray *body;
byte character;
uint64_t sizeOfByteCode;
object->iterator = 0;
object->iteratorShift = 0; // сдвиг получается из-за '[' и ']' утроения
// все [, ] символы будут утроены в байт-коде,
// из-за r_if инструкции + goto
object->forwardRepetitions = $(object->code, m(numberOfRepetitions, RCString)), '[');
object->backwardRepetitions = $(object->code, m(numberOfRepetitions, RCString)), ']');
if(object->forwardRepetitions != object->backwardRepetitions) {
// если скобочек не хватает
RPrintf("Warning. RVC (BrainFuck). Count of '[' and ']' isn't equal!");
}
// из размера байткода удаляем все 'n', +1 для инструкции r_end
sizeOfByteCode = object->code->size - object->numberOfLines + 1 + 2 * (object->forwardRepetitions + object->backwardRepetitions);
body = makeRByteArray(sizeOfByteCode);
// устанавливаем указатель на тело
object->body = body;
// препроцессим посимвольно
while(object->iterator < object->code->size) {
character = $(object, m(brainFuckSourceToByteCode, RVirtualCompiler)));
// eсли r_ignore не присваеваем байт-код
if(character != r_ignore) {
body->array[object->iterator + object->iteratorShift] = character;
}
++object->iterator;
}
body->array[object->iterator + object->iteratorShift] = r_end;
return body;
}
Разбор посимвольно:
method(byte, brainFuckSourceToByteCode, RVirtualCompiler)) {
byte byteCode;
switch (object->code->baseString[object->iterator]) {
case '+': {
byteCode = r_increment;
} break;
case '-': {
byteCode = r_decrement;
} break;
case '.': {
byteCode = r_print_char;
} break;
case '>': {
byteCode = r_move_forward;
} break;
case '<': {
byteCode = r_move_backward;
} break;
case ',': {
byteCode = r_get_char;
} break;
case '[': {
// complicated case
uint64_t realPath;
object->deltaToNext = indexOfLastCharacterCString(&object->code->baseString[object->iterator + object->iteratorShift], object->code->size - object->deltaToNext, ']');
--object->forwardRepetitions;
realPath = object->iterator + object->iteratorShift + object->deltaToNext + (object->forwardRepetitions + object->backwardRepetitions) * 2;
if(realPath > 255) {
RPrintf("Warning. RVC (BrainFuck). '[' Too long loopn");
}
object->body->array[object->iterator + object->iteratorShift] = r_if;
object->body->array[object->iterator + object->iteratorShift + 1] = r_goto_address;
object->body->array[object->iterator + object->iteratorShift + 2] = realPath;
object->iteratorShift += 2;
byteCode = r_ignore;
} break;
case ']': {
// complicated case
uint64_t realPath;
object->toPrev = indexOfLastCharacterCString(object->code->baseString, object->toPrev ? object->toPrev : object->code->size, '[');
--object->backwardRepetitions;
realPath = object->toPrev + (object->forwardRepetitions + object->backwardRepetitions) * 2;
if(realPath > 255) {
RPrintf("Warning. RVC (BrainFuck). ']' Too long loopn");
}
object->body->array[object->iterator + object->iteratorShift] = r_if_not;
object->body->array[object->iterator + object->iteratorShift + 1] = r_goto_address;
object->body->array[object->iterator + object->iteratorShift + 2] = realPath;
object->iteratorShift += 2;
byteCode = r_ignore;
} break;
case 'n': {
++object->lines;
object->symbols = 1;
--object->iteratorShift;
byteCode = r_ignore;
} break;
case ' ': {
--object->iteratorShift;
byteCode = r_ignore;
} break;
default: {
byteCode = r_end;
RPrintf("ERROR. RVC (BrainFuck). Undefined symbol on line: %qu, place: %qu !n", object->lines, object->symbols);
}
}
++object->symbols;
return byteCode;
}
В конце-концов мы имеем полноценную ВМ заточенную под Brainfuck, написанную на С, с которой можно долго играться.
Пример использования:
#include "RayFoundation/RayFoundation.h"
#include "RVirtualMachine/RVirtualFunction/RVirtualFunction.h"
#include "RVirtualMachine/RVirtualMachine/RVirtualMachine.h"
#include "RVirtualMachine/RVirtualCompiler.h"
int main(int argc, const char *argv[]) {
// простой привет-мир без циклов
RVirtualFunction *function = $(RVC, m(createFunctionFromBrainFuckSourceCode, RVirtualCompiler)),
RS(" My brainfuck hello world : +++++++++++++++++++++++++++++++++++++++++++++n"
" +++++++++++++++++++++++++++.+++++++++++++++++n"
" ++++++++++++.+++++++..+++.-------------------n"
" ---------------------------------------------n"
" ---------------.+++++++++++++++++++++++++++++n"
" ++++++++++++++++++++++++++.++++++++++++++++++n"
" ++++++.+++.------.--------.------------------n"
" ---------------------------------------------n"
" ----.-----------------------."));
// исполняем байт-код на RVM-одиночке
executeRay(function);
$(function, d(RVirtualFunction)) );
// тест компилятора множественных циклов
function = $(RVC, m(createFunctionFromBrainFuckSourceCode, RVirtualCompiler)),
RS(" Cycles : +++ [ > +++ [.-] <-]")); // печатает '03 02 01' 3 раза
executeRay(function);
$(function, d(RVirtualFunction)) );
// сложный привет-мир с циклом
function = $(RVC, m(createFunctionFromBrainFuckSourceCode, RVirtualCompiler)),
RS(" Hard Hello world : ++++++++++[>+++++++>++++++++++>+++>+<<<<-]>++n"
" .>+.+++++++..+++.>++.<<+++++++++++++++.>.+++.n"
" ------.--------.>+.>."));
// печатаем функцию как rasm байт-код
$(function, p(RVirtualFunction)) );
executeRay(function);
$(function, d(RVirtualFunction)) );
deallocator(function);
// удаляем одиночку
deleteRVM();
return 0;
}
Всем спасибо за внимание. Let's play a game!
Автор: StrangerInRed