Идея
Всем здравствуйте! Я интересуюсь языком программирования C и решил поделиться, как пытаюсь сделать два консольных приложения:
i8008compiler- программа, которая переводит код на ассемблереIntel-8008в бинарный код. Предполагается, что ассемблерный код содержится в.txtфайле, а бинарный код записывается в файл с форматом.bini8008emulator- программа, которая исполняет бинарный код так, как бы это делал процессорIntel-8008. На входе имеем.bin-файл, который содержит скомпилированную программу. В консоль выводится информация о том, какие значения имели регистры, когда исполнение завершилось.
В этой публикации расскажу про текущее состояние компилятора и о планах по его развитию. Пишу для того, чтобы поделиться наработками и прислушаться к критике читателей статьи. Эмулятор на данный момент умеет выполнять простые программки, к примеру:
Посчитать нужное число Фибоначчи (естественно нужно учесть 8-битность)
Умножения, возведения в степень
Определить по входящим трём числам, заранее неотсортированным, можно ли из отрезков таких длин построить треугольник и записать в аккумуляторный регистр булевый результат (
1- да,0- нет)
Обзор процессора Intel-8008
8-битные регистры:
Аккумуляторный регистр A (в него складываются результаты арифметических и логических операций)
Регистры общего назначения B, C, D, E
Два регистра H и L: адреса для обращения к памяти 14-битные, поэтому регистр L хранит первые 8 бит адреса, а регистр H хранит старшие 6 бит адреса. Эти регистры используются в командах взаимодействия с памятью. Их можно изменять
Флаги, стек вызовов и PC:
Имеем 4 флага:
PF (флаг чётности числа),SF (знак числа),ZF (равенство нулю)а также CF (бит переноса)Стек вызововпредставляет собой семь 14-битных регистров, в которые сохраняются адреса следующих инструкций при выполнении инструкцийCALLи вызовов с условиями. Также имеется 3-битный счётчик, который и указывает, сколько регистров в стеке занятоPCпредставляет собой 14-битный регистр, в котором хранится адрес инструкции, которую нужно выполнить
Что реализовано в компиляторе на данный момент
На данный момент компилятор научился следующему:
Работает с вводом-выводом через консоль: проверка флагов, форматов файлов
Умеет транслировать
Index-registerинструкции,Acc-groupинструкции а также инструкции перехода по меткам, вызова функции и возвращения из функций
Компилятор может выловить пока маленькое количество ошибок:
Используется функция перехода по метке, но такой метки в программе нет
В программе присутствует несуществующая инструкция
Существует проверка для инструкций декремента и инкремента, которые не должны работать с аккумуляторным регистром. То есть компилятор ловит ситуацию, когда вы пытаетесь применить эти две инструкции к аккумулятору
Как происходит обработка меток
Специально для этой цели я решил сделать динамическую библиотеку (.dll), которая будет подключаться к компилятору при его запуске. Покажу в этом пункте фрагменты из .h-файла для этой библиотеки и из .c файла этой библиотеки
Для того, чтобы корректно скомпилировать программу с JMP и CALL инструкциями, я решил сделать хэш-таблицу, которая для каждой метки хранит адрес, на который она указывает
Для каждой метки применяется функция полиномиального хэша, которая проходится по строке и формирует её уникальное число. Конечно, необходимо также предусмотреть коллизию - решил сделать с помощью связных списков. Для "ноды" в этой хэш-таблице я сделал struct, которая хранит строку, указатель на следующую "ноду" в списке, а также значение адреса:
typedef union mem_addr_u // union, который отвечает за 14-битный адрес
{
uint16_t value; // значение адреса
uint8_t bytes[2]; // байты адреса
} mem_addr_s;
typedef struct table_node_s // собственно, сама нода для хэш-таблицы
{
char* symbol; // метка
mem_addr_s jump_addr; // адрес, соответствующий метке
struct table_node_s* next; // указатель на следующую ноду
} table_node_s;Когда мы проходимся по текстовому файлу, все функции вызовов и переходов добавляются в специальный стек. В него добавляется адрес данной команды, и по какой метке совершается переход
typedef struct stack_node_s // элемент стека
{
uint16_t instr_addr; // адрес инструкции в памяти
char* label; // метка
} stack_node_s;
typedef struct stack_s
{
stack_node_s* arr; // указатель на массив с элементами стека
int cap; // выделенное место в памяти для стека
int length; // текущий размер стека
} stack_s;Компилятор проходится по тексту программы один раз. За этот проход мы узнаём информацию о метках, а также про все инструкции перехода, которые есть в программе
В конце компиляции мы обрабатываем стек следующим образом:
Из стека берём инструкцию перехода или вызова
Высчитываем хэш для её метки: если есть такая метка - отлично, если нет - ошибка :(
Если ошибки нет, то тогда нам нужно извлечь из хэш-таблицы соответствующий этой метке адрес в памяти и поместить нужные байты в программный код
Если обработки в конце компиляции обязательно очищаем память от хэш-таблицы и стека для избежания утечек памяти: очищать нужно не только память для "нод", но также и память для строковых буферов
Код хэш-таблицы
table_node_s** InitSymbolTable () // создание в памяти хэш-таблицы
{
table_node_s** table = (table_node_s**) malloc(sizeof(table_node_s*) * TABLE_SIZE);
for (int i = 0; i < TABLE_SIZE; i++)
table[i] = NULL;
return table;
}
void AddElem (table_node_s** table, char* symbol, uint16_t value) // добавление ноды
{
uint32_t hash = PolinHash(symbol);
if (table[hash] == NULL)
{
table[hash] = (table_node_s*) malloc (sizeof(table_node_s) * 1);
table[hash]->next = NULL;
table[hash]->symbol = symbol;
table[hash]->jump_addr.value = value;
}
else
{
table_node_s* new_node = (table_node_s*) malloc (sizeof(table_node_s) * 1);
new_node->next = table[hash];
new_node->symbol = symbol;
new_node->jump_addr.value = value;
table[hash] = new_node;
}
}
table_node_s* GetElement (table_node_s** table, char* symbol) // просмотреть информацию о метке (получаем указатель на ноду)
{
uint32_t hash = PolinHash(symbol);
table_node_s* node = table[hash];
while (node != NULL && strcmp(node->symbol, symbol) != 0)
node = node->next;
return node;
}
void DestroyTable (table_node_s** table) // очистить память от хэш-таблицы
{
for (int i = 0; i < TABLE_SIZE; i++)
{
table_node_s* node = table[i];
table_node_s* next_node;
while (node != NULL)
{
next_node = node->next;
free(node->symbol);
free(node);
node = next_node;
}
}
free(table);
}Код для стека
stack_s* InitStack () // создание стека в памяти
{
stack_s* stack = (stack_s*) malloc (sizeof(stack_s));
stack->arr = (stack_node_s*) malloc (sizeof(stack_node_s) * 30);
stack->length = 0;
stack->cap = 30;
}
void JmpPush (stack_s* stack, uint16_t instr_addr, char* label) // запушить информацию об инструкции на стек
{
if (stack->length + 1 > stack->cap)
{
stack->cap *= 2;
stack->arr = (stack_node_s*) realloc (stack->arr, sizeof(stack_node_s) * stack->cap);
}
stack->arr[stack->length].instr_addr = instr_addr;
stack->arr[stack->length].label = label;
stack->length += 1;
}
int FillAddr (stack_node_s* addrs, int length, table_node_s** table, uint8_t* RAM) // "обойти" стек, заполнив адреса перехода для соответствующих инструкций
{
char* label;
uint16_t instr_addr;
table_node_s* table_node;
for (int i = 0; i < length; i++)
{
label = addrs[i].label;
instr_addr = addrs[i].instr_addr;
table_node = GetElement(table, label);
if (table_node == NULL)
{
printf("\nERROR! No such symbol in the program!!! -> %s\n", label);
return 1;
}
RAM[instr_addr + 1] = table_node->jump_addr.bytes[0];
RAM[instr_addr + 2] = table_node->jump_addr.bytes[1];
}
return 0;
}
void DestroyStack (stack_s* addrs) // очистить память от стека
{
for (int i = 0; i < addrs->length; i++)
free(addrs->arr[i].label);
free(addrs->arr);
free(addrs);
}Проход по программе
Важные технические моменты
Перед описанием покажу важные структуры, которые были созданы для работы компилятора:
typedef struct machine_code_s // динамический массив, который хранит машинный код
{
uint8_t* img;
int buff_size;
int act_size;
} machine_code_s;
typedef struct opcode_s // решил именовать так: opcode - 0b(id)(reg1)(reg2)
{
uint8_t reg2 : 3;
uint8_t reg1 : 3;
uint8_t id : 2;
} opcode_s;
typedef union opcode_u // опкод инструкции: можем обращаться как к отдельному параметру, так и к значению в целом
{
opcode_s labels;
uint8_t value;
} opcode_u;
typedef struct instr_s // инструкция содержит опкод, второй и третий байт, а так же длину
{
opcode_u opcode;
uint8_t second_byte;
uint8_t third_byte;
uint8_t length;
} instr_s;При запуске сначала проверяется корректный ввод с консоли (демонстрация будет в конце статьи)
Далее компилятор пытается открыть файл. Если это не получается, сообщается об ошибке:
FILE* program = fopen(input_name, "r");
if (program == NULL)
{
printf("\nERROR! Please, check that the file %s exists\n", input_name);
return 0;
}При проходе по текстовому файлу программа считывает строку. Сначала нам нужно проверить, что это не метка (пока что реализовано так, что на одной строке может быть только либо метка либо команда). Для этого ищем вхождение символа :
double_point = strstr(instr_buff, ":");Если это вхождение есть, то значит мы нашли метку - добавляем её в нашу хэш-таблицу и считываем следующую строку
Если мы наткнулись на команду - вызываем функцию, которая переведёт эту команду в машинный код. Функция может сообщить об ошибке и вернуть код - в таком случае нужно уточнить ещё и строку, на которой находится эта ошибка
encoder_code = InstrEncoder(&input_instr, instr_buff, stack, MACHINE_CODE.act_size, program);
if (encoder_code != 0)
{
printf("Location of the error: %d\n", line);
DEST_EXEC_MEMORY;
DestroyTable(symbol_table);
DestroyStack(stack);
return 0;
}Если ошибки не возникло, то записываем бинарный код в буфер и продолжаем считывание строк. Функция для записи в память:
void WriteInMemImg(machine_code_s* mem, instr_s* src) // на вход - две структуры: абстрактная память и бинарный код инструкции
{
if (mem->act_size + src->length + 1 > mem->buff_size) // проверяем, что можем записать
{
mem->buff_size *= 2;
mem->img = (uint8_t*) realloc (mem->img, sizeof(uint8_t) * mem->buff_size);
}
switch (src->length) // рассматриваем каждую длину команды отдельно
{
case 0b01:
mem->img[mem->act_size] = src->opcode.value;
mem->act_size += 1;
return;
case 0b10:
mem->img[mem->act_size] = src->opcode.value;
mem->act_size += 1;
mem->img[mem->act_size] = src->second_byte;
mem->act_size += 1;
return;
case 0b11: // длину 3 имеют инструкции перехода по меткам. Адреса записываются на финальном этапе
mem->img[mem->act_size] = src->opcode.value;
mem->act_size += 3;
return;
}
}Функция трансляции
Функция InstrEncoder записывает в структуру по указателю бинарный код команды, который потом будет добавлен в код программы
Решил поступить так:
В отдельном скрипте проходимся по мнемоникам из ISA нашего процессора
Выводим в текстовый файлик каждую мнемонику и значение её полиномиального хэша
Создаём
.hс этими хэшамиПодключаем этот хедер в исходном коде компилятора
Далее мы рассматриваем каждый хэш с помощью оператора switch-case, где в секции default выводим сообщение, что функции с такой-то мнемоникой нет и возвращаем код ошибки
int InstrEncoder(instr_s* dest, char* instr_buff, stack_s* stack, int act_size, FILE* src)
{
char* mnemonic; // сюда будем загружать команду
char* symbol; // сюда будем загружать метку для инструкций перехода
uint16_t addr_jmp_instr; // переменная, которая хранит адрес инструкции перехода
mnemonic = strtok(instr_buff, " ");
uint32_t hash = PolinHash(mnemonic);
switch (hash) // парсим строку программы и записываем нужные параметры в структуру исходя из ISA
{
case MOV_HASH: // обрабатываем команду MOV
dest->opcode.labels.id = 0b11;
mnemonic = strtok(NULL, " ");
dest->opcode.labels.reg1 = GetRegIdx(mnemonic[0]);
mnemonic = strtok(NULL, " ");
dest->opcode.labels.reg2 = GetRegIdx(mnemonic[0]);
dest->length = 0b01;
return 0;
case MVI_HASH: // обрабатываем команду MVI
uint8_t imm;
dest->opcode.labels.id = 0;
mnemonic = strtok(NULL, " ");
dest->opcode.labels.reg1 = GetRegIdx(mnemonic[0]);
dest->opcode.labels.reg2 = 0b110;
mnemonic = strtok(NULL, " ");
sscanf(mnemonic, "%" SCNu8, &imm);
dest->second_byte = imm;
dest->length = 0b10;
return 0;
case INC_HASH:
// ... Стоит уделить внимание обработке инструкций перехода:
char* name = (char*) malloc (sizeof(char) * (strlen(mnemonic) + 1));
strcpy(name, mnemonic); // сохраняем имя инструкции
mnemonic = strtok(NULL, " ");
if (mnemonic == NULL) // проверка на то, что после инструкции есть метка
{
fclose(src);
printf("\nERROR! No any label after jump-instruction -> [%s ???] \n", name);
free(name);
return 1;
}
symbol = (char*) malloc (sizeof(char) * (strlen(mnemonic) + 1));
if (strstr(mnemonic, "\n") != NULL)
*(strstr(mnemonic, "\n")) = '\0';
strcpy(symbol, mnemonic); // копируем метку в отдельный буфер
addr_jmp_instr = (uint16_t) act_size;
JmpPush(stack, addr_jmp_instr, symbol); // после считывания метки делаем пуш на наш "стек инструкций перехода", чтобы потом добавить адреса
switch (hash)
{
case JMP_HASH: // обрабатываем команду JMP (безусловный переход)
dest->opcode.value = 0b01000100;
dest->length = 0b11;
free(name);
return 0;
case JNC_HASH: // обрабатываем команду JNC (переход в случае Carry = 0)
dest->opcode.value = 0b01000000;
dest->length = 0b11;
free(name);
return 0;
case JNZ_HASH: // обрабатываем команду JNZ (переход в случае Z = 0)
dest->opcode.value = 0b01001000;
dest->length = 0b11;
free(name);
return 0;
case JP_HASH:
// ...Пример работы
Покажу на примере ассемблерной программы, как компилятор работает
Пока что не буду разбирать сами программы на ассемблере, потому что хотел бы это сделать в статье про эмулятор. Пока что просто покажу пример работы
Числа Фибоначчи по номеру в регистре E
MVI E, 3
DEC E
DEC E
CALL CALC_FIB
JMP END
CALC_FIB:
MVI A, 1
WHILE:
MOV C, A
ADD B
MOV B, C
DEC E
RZ
JMP WHILE
END: // пока что сделал эту штуку, которая явно указывает на конец программы. Планирую исбавиться и от неё в дальнейшемКогда нет ошибки
Скрипт для компиляции:
..\bin\i8008compiler -i ..\tests\fibonacchi\fib_3.txt -o ..\tests\fibonacchi\fib_3.binРезультат, выводимый в консоль:
Compiling finished
COMPILING REPORT
Number of bytes: 24
Amount of commands: 12Когда ошибка есть
К примеру, введём несуществующий файл на вход - тогда компилятор выведет в консоль следующее:
ERROR! File opening failed! Please, check that the file *PATH* existsСмоделируем следующую ошибку: команда перехода по метке переходит по несуществующей метке:
MVI E, 3
DEC E
DEC E
CALL CALC
JMP END
CALC_FIB:
MVI A, 1
WHILE:
MOV C, A
ADD B
MOV B, C
DEC E
RZ
JMP WHILE
END:Подадим на компиляцию и получим в консоль следующее сообщение:
ERROR! No such symbol in the program!!! -> CALCПромежуточные итоги
Компилятор имеет три флага:
-iдля входного файла,-oдля результата и-hдля вывода справочной информацииОбрабатывает ошибки связанные с метками и несуществующими командами
Обрабатываются ошибки ввода: предусмотрена ситуация, когда подан несуществующий файл или файл некорректного формата
Что хочется добавить в компилятор
Более гибкую обработку меток (чтобы можно было писать метку не только в отдельной строке но ещё и в одной строке с командами)
Обработка ошибок синтаксиса
Обработка остальных групп инструкций
Добавить возможность писать комментарии
tonyk_av
Вашу энергию да в нужное русло...
Лучше бы написали транслятор языка ST в IL, а IL в байт-код, и эмулятор процессора, исполняющего этот байт-код. Вот это было бы интересно и полезно.
kna_4192 Автор
Благодарю за идею)
HardWrMan
А зачем? Есть и более интересные и полезные задачи.