- Разинкин Александр Владимирович, P3207
- asm | stack | neum | hw | instr | binary -> struct | trap -> stream | mem | cstr | prob2 | spi
- Базовый вариант (без усложнения)
Примечания:
- Большая часть идей в плане реализации модели была взята из информационного источника.
Синтаксис в расширенной БНВ.
[ ... ]-- вхождение 0 или 1 раз{ ... }-- вхождение 0 или несколько раз{ ... }--- вхождение 1 или несколько раз
program ::= section_data "\n" section_text
section_data ::= "section .data:" [ comment ] "\n" { data_line }
data_line ::= variable comment
variable ::= variable_name ":" variable_value
variable_name ::= <any of "a-z A-Z _"> { <any of "a-z A-Z 0-9 _"> }
variable_value ::= integer
| string
| buffer
| variable_name
section_text ::= "section .text:" [ comment ] "\n" { command_line }
command_line ::= label comment
| command comment
label ::= <any of "a-z A-Z _"> { <any of "a-z A-Z 0-9 _"> }
command ::= op0 comment
| op1 comment
op0 ::= nop
| add
| sub
| mul
| div
| mod
| inc
| dec
| dup
| over
| switch
| cmp
| ret
| push
| pop
| drop
| ei
| di
| iret
| halt
op1 ::= jmp label
| jz label
| jnz label
| call label
| lit integer
| lit variable
| lit in
| lit out
integer ::= [ "-" ] { <any of "0-9"> }-
positive_integer ::= <any of "1-9"> { <any of "0-9"> }
string ::= "\"" { <any symbol except "\t \n"> } "\""
| "\'" { <any symbol except "\t \n"> } "\'"
buffer ::= "bf " positive_integer
comment ::= ";" { <any symbol except "\n"> }Команды:
nop-- ничего не делать (добавлена для общего кругозора)add-- сумма двух значений на верхушке стека данных кладется на верхушку стека данных[a, b] -> [b + a]sub-- разность двух значений на верхушке стека данных (из первого вычитается второе) кладется на верхушку стека данных[a, b] -> [b - a]mul-- произведение двух значений на верхушке стека данных кладется на верхушку стека данных[a, b] -> [b * a]div-- целочисленное деление двух значений на верхушке стека данных (первое делится на второе) кладется на верхушку стека данных[a, b] -> [b / a]mod-- остаток от деления двух значений на верхушке стека данных (первое делится на второе) кладется на верхушку стека данных[a, b] -> [b % a]inc-- вместо значения на верхушке стека данных положить данное значение, увеличенное на единицу[a] -> [a + 1]dec-- вместо значения на верхушке стека данных положить данное значение, уменьшенное на единицу[a] -> [a - 1]dup-- продублировать на верхушку стека данных текущее значение на верхушке стека данных[a] -> [a, a]over-- положить на верхушку стека данных следующее значение после текущей верхушки стека данных[a, b] -> [a, b, a]switch-- поменять верхушку стека данных и следующее значение местами[a, b] -> [b, a]cmp-- установить флаги результата операцииsub(стек данных не меняется)[a, b] -> [a, b] + updated_flagsjmp label-- переход на указанную меткуjz label-- переход на указанную метку при условии, чтоz-flagравен 1, иначе - переход к следующей по порядку командеjnz label-- переход на указанную метку при условии, чтоz-flagравен 0, иначе - переход к следующей по порядку командеcall label-- вызов подпрограммы по указанной меткеret-- возврат из вызванной подпрограммы при помощи командыcalllit integer-- положить на верхушку стека данных переданное целочисленное значениеlit variable-- положить на верхушку стека данных адрес, с которого начинается переданная переменнаяpush-- взять адрес с верхушки стека данных и положить вместо него значение из памяти по указанному адресу[address] -> [value_from_memory]pop-- взять адрес с верхушки стека данных и записать в память следующее значение после верхушки стека данных[value, address] -> []drop-- удалить значение с верхушки стека данных[a] -> []ei-- разрешить прерыванияdi-- за FF8 ретить прерыванияiret-- возврат из текущего прерыванияhalt-- останов
- Память соответствует фон Неймановской архитектуре.
- Размер машинного слова - 32 бита.
- Адресация - абсолютная.
memory
+----------------------------+
| 00 : start address (n) |
| 01 : interruption vector 1 |
| 02 : input port |
| 03 : output port |
| 04 : ... |
| part for variables |
| ... |
| n : program start |
| ... |
+----------------------------+
-
Ячейка памяти
0соответствует адресу первой инструкции (началу кода, написанного в секции .text). -
Ячейка памяти
1соответствуетвектору прерывания 1. -
Ячейки памяти
2и3соответствуютmemory-mapped портам ввода-вывода. -
С ячейки памяти
4начинается секция.data. Переменные могут быть четырех типов:Целочисленные-- под них отводится одна ячейка памяти;Строковые-- под них отводитсяn + 1последовательных ячеек памяти, гдеn- длина строки (дополнительный символ -нуль-терминатор);Буфферные-- под них отводитсяnпоследовательных ячеек памяти, гдеn- значение из запроса на выделение памяти (bf n);Ссылочные-- этоцелочисленныепеременные, но при начальной инициализации хранят адрес другой переменной. Под них отводится одна ячейка памяти.
Переменн FBC8 е располагаются в памяти в таком порядке, в котором они указаны в исходном коде в секции
.data. -
С ячейки памяти
nначинаются инструкции, соответствующие исходному коду, прописанному в секции.text.
Особенности процессора:
- Машинное слово -- 32 бита, знаковое.
- Доступ к памяти осуществляется по адресу, хранящемуся в специальном регистре
PC (programm counter). Установка адреса осуществляется тремя разными способами:- Путем инкрементирования текущего значения, записанного в
PC; - Путем записи значения с верхушки
стека адресов; - Путем записи значения с верхушки
стека данных.
- Путем инкрементирования текущего значения, записанного в
- Поток управления:
- увеличение
PCна1или2после каждой команды (увеличение зависит от выполненной команды; например, после командыlitPCувеличивается на2) - условный (
jzилиjnz) и безусловный (jmp) переходы
- увеличение
Команды языка однозначно транслируюстя в инструкции (см. описание в разделе Язык программирования)
| Инструкция | Кол-во тактов |
|---|---|
| nop | 0 |
| add | 4 |
| sub | 4 |
| mul | 4 |
| div | 4 |
| mod | 4 |
| inc | 3 |
| dec | 3 |
| dup | 3 |
| over | 5 |
| switch | 4 |
| cmp | 4 |
| jmp | 2 |
| jz | 1 или 2 |
| jnz | 1 или 2 |
| call | 4 |
| ret | 2 |
| lit | 2 |
| push | 4 |
| pop | 5 |
| drop | 1 |
| ei | 1 |
| di | 1 |
| iret | 0 или 2 |
Стоит учитывать, что в таблице приведено кол-во тактов на цикл исполнения инструкции.
Цикл выборки следующей инструкции выполняется за 2 такта.
Инструкции имеют бинарное представление и состоят только из опкода, состоящего из 5 битов
(соответствие между инструкцией и ее опкодом можно прочитать в файле isa.py в классе Opcode).
Особенность инструкций перехода (jmp, jz и jnz) и непосредственного ввода (lit) заключается в том, что
их операнд лежит в следующей ячейке памяти. Например, команда lit 42 будет представлена в виде:
l : 10001000000000000000000000000000 lit
l + 1 : 00000000000000000000000000101010 42
По этой причине PC после команды увеличивается на 2.
Интерфейс командной строки: python3 translator.py <source_file> <target_file>
Реализовано в модуле: translator
Этапы трансляции (функция translate_source):
- Очистка исходного текста от пустых строк, лишних пробелов и комментариев (функция
clean_source). - Выделение переменных (функция
translate_section_data). - Выделение меток (функция
translate_section_text_stage_1). - Выделение выделение команд (функция
translate_section_text_stage_2). - Трансляция переменных в бинарный код (функция
translate_variables). - Трансляция команд в бинарный код (функция
translate_commands). - Объединение результатов двух последних шагов и формирование машинного кода.
Правила трансляции:
- Одна переменная - одна строка.
- Одна команда - одна строка.
- Метки пишутся в отдельной строке.
- Названия секций пишутся в отдельной строке.
- Ссылаться можно только на существующие переменные и метки.
Стоит заметить, что, помимо бинарного файла с машинным кодом, формируется текстовый файл с комментариями.
Интерфейс командной строки: python3 machine.py <binary_code_file> <input_file>
Реализовано в модуле: machine
+------------+
reset_int_signal | |
+--------------------------->|interruption|
| +-------------------------| controller |
| | int_signal +------------+
| | | int_number
| | |
| | |
| | +---------+ | +---------+
| | wr_ds->| data | | | address |<-wr_ds
| | re_ds->| stack | | | stack |<-re_ds
| | | | | | |
| | value +---------+ op_2 | pc_value+---------+ pc_value
| | +----------->| tods |---+ | +-----| toas |<-------------+
| | | +---------+ | | | +---------+ |
| | | op_1| v v | |
| | +-----+ | +-----+ | |
| | | mux |<-sel | sel->| mux | | |
| | +-----+ | +-----+ | |
| | ^ ^ | | | +----------(+1)------------+
| | | | v v | | |
| | | | +1-1+-*/%~ _______ _______ | | +---+ |
| | | | ----------->\ \/ / | +-->| m | +--------+ |
| | | | z_flag\ alu / +------>| u |----->| pc |--+
| | +-|--|---------------\__________/ +------>| x | +--------+ |
| | | | | | | +---+ ^ |
| | | | +--------------------+-----------+ ^ | |
| | | +----------------+ | | latch_pc |
| | | | data_in| sel |
| v v | v |
+---------+ | +--------------+ |
| control | | | | |
| unit |<---------------+-------| memory + I/O |<-------------------------+
+---------+ instr data_out| | address
+--------------+
^ ^
| |
wr_mem re_mem
Реализован в классе DataPath.
interruption_controller -- контроллер прерываний, выставляет сигнал (int_signal)
и номер вектора прерывания (int_number). Для сброса сигнала прерывания control_unit
формирует сигнал reset_int_signal.
data_stack -- стек данных. Схема с более детальным описанием модуля TODS (top of data stack):
+---------+
wr_ds->| data |
re_ds->| stack |
| |
+---------+
^ | data_out
data_in| |
| | tods
+--------------------------------------------------------------------------|
| | | |
| +---------------+-------------------------+ |
| | | | |
| | +---+ | v |
| +->| m | +----------+ +----------+ |
value | | u |-->| tods_r_1 |<-latch_tods_r_1 | tods_r_2 |<-latch_tods_r_2 |
-------|------->| x | +----------+ +----------+ |
| +---+ | | |
| ^ | | |
| | | | |
| sel | | |
+--------------------------------------------------------------------------+
| |
| op_1 | op_2
v v
tods_r_1 и tods_r_2 -- регистры для ввода/вывода стека данных.
address_stack -- стек адресов. Схема с более детальным описанием модуля toas (top of address stack):
+---------+
| address |<-wr_as
| stack |<-re_as
| |
+---------+
^ |data_out
data_in| |
| | toas
+---------------------------------+
| | | |
| | +----------------+ |
| | | |
pc_value| +--------+ +---+ | |
<--------|----| toas_r |<---| m |<---+ |
| +--------+ | u | | pc_value
| ^ | x |<---------|---------
| | +---+ |
| latch_toas_r ^ |
| | |
| sel |
+---------------------------------+
toas_r -- регистр для ввода/вывода стека адрессов.
Сигналы (обрабатываются за один такт, реализованы в качестве методов класса):
reset_int_signal-- сброс сигнала прерывания в контроллере прерываний, используется в случаях, когда прерывание обработано;wr_ds-- запись в стек данных, на верхушку записывается значение из tods_1;re_ds-- чтение из стека данных, значение с верхушки записывается в один или во все регистры tods (зависит от сигналовlatch_tods_r_1,latch_tods_r_2);latch_tods_r_1,latch_tods_r_2-- защелкнуть входное значение в регистрtods_r_1,tods_r_2, соответственно;wr_as-- запись в стек адрессов, на верхушку записывается значение из toas;re_as-- чтение из стека адрессов, значение с верхушки записывается вtoas;latch_toas-- защелкнуть входное значение в регистрtoas;+1-- сигналaluвыполнить операцию инкремента;-1-- сигналaluвыполнить операцию декремента;+-- сигналaluвыполнить операцию сложения;--- сигналaluвыполнить операцию вычитания;*-- сигналaluвыполнить операцию умножения;/-- сигналaluвыполнить операцию целочисленного деления;%-- сигналaluвыполнить операцию взятия остатка от деления;~-- сигналaluвыполнить операцию сравнения;latch_pc-- защелкнуть входное значение в регистрpc;wr_mem-- запись в память по переданному адресу;re_mem-- чтение из памяти по переданному адресу.
Флаги:
z_flag-- отражает нулевое значение результата операции вalu;int_signal-- отражает наличие вызова прерывания от внешнего устройства.
+------+
+---->| tick |
| +------+
| |
+-------------+ |
+----------------| instruction |<----+
| +--->| decoder |
| | +-------------+
| | ^ ^ |
| int_signal| instr| z_flag| | signals
| | | | v
| | +---------------+
| +----| data path |
+--------------->| |
reset_int_signal +---------------+
Реализовано в классе ControlUnit.
- Hardwired (реализовано полностью на Python).
- Выполняет предварительную инициализацию машины -- выполняет список инструкций, чтобы защелкнуть адрес первой
инструкции в
pc(методinitialization_cycle). - Выполнение и декодирование инструкций происходит в методе
decode_and_execute_instruction. - Проверяет наличие прерываний и обрабатывает их (метод
check_and_handle_interruption). tickнужен для подсчета тактов (пригождается при вызове прерываний).
Особенности работы модели:
- Цикл симуляции осуществляется в функции
simulation. - Шаг моделирования соответствует одной инструкции с выводом состояния в журнал.
- Для журнала состояний процессора используется стандартный модуль
logging. - Количество инструкций для моделирования лимитировано.
- Перед выполнением следующей инструкции происходит проверка на вызов прерывания (функция
initiate_interruption). - Остановка моделирования осуществляется при:
- превышении лимита количества выполняемых инструкций;
- исключении
StopIteration-- если выполнена инструкцияhalt.
- Тестирование осуществляется при помощи golden test-ов.
- Настройка golden тестирования находится в файле
- Конфигурация golden test-ов лежит в директории
Запустить тесты: poetry run pytest . -v
Обновить конфигурацию golden tests: poetry run pytest . -v --update-goldens
CI при помощи Github Actions:
name: Stack-Machine
on:
push:
branches:
- main
jobs:
test:
runs-on: ubuntu-latest
steps:
- name: Checkout code
uses: actions/checkout@v4
- name: Set up Python
uses: actions/setup-python@v4
with:
python-version: 3.12
- name: Install dependencies
run: |
python3 -m pip install --upgrade pip
pip3 install poetry
poetry install
- name: Run tests and collect coverage
run: |
poetry run coverage run -m pytest .
poetry run coverage report -m
env:
CI: true
lint:
runs-on: ubuntu-latest
steps:
- name: Checkout code
uses: actions/checkout@v4
- name: Set up Python
uses: actions/setup-python@v4
with:
python-version: 3.12
- name: Install dependencies
run: |
python3 -m pip install --upgrade pip
pip3 install poetry
poetry install
- name: Check code formatting with Ruff
run: poetry run ruff format --check .
- name: Run Ruff linters
run: poetry run ruff check .где:
poetry-- управления зависимостями для языка программирования Python.coverage-- формирование отчёта об уровне покрытия исходного кода.pytest-- утилита для запуска тестов.ruff-- утилита для форматирования и проверки стиля кодирования.
Пример использования и журнал работы процессора на примере add:
python3 translator.py examples/add.txt target.bin
source LoC: 10 code instr: 14
python3 machine.py target.bin examples/input.txt
DEBUG:root:TICK: 6 PC: 8 TODS1: 4 TODS2: 0 TOAS: 0 Z_FLAG: 0 lit 4
DATA_STACK: [4]
ADDRESS_STACK: []
DEBUG:root:TICK: 12 PC: 9 TODS1: 1 TODS2: 0 TOAS: 9 Z_FLAG: 0 push
DATA_STACK: [1]
ADDRESS_STACK: []
DEBUG:root:TICK: 16 PC: 11 TODS1: 5 TODS2: 0 TOAS: 9 Z_FLAG: 0 lit 5
DATA_STACK: [1, 5]
ADDRESS_STACK: []
DEBUG:root:TICK: 22 PC: 12 TODS1: 1 TODS2: 0 TOAS: 12 Z_FLAG: 0 push
DATA_STACK: [1, 1]
ADDRESS_STACK: []
DEBUG:root:TICK: 28 PC: 13 TODS1: 2 TODS2: 1 TOAS: 12 Z_FLAG: 0 add
DATA_STACK: [2]
ADDRESS_STACK: []
DEBUG:root:TICK: 30 PC: 14 TODS1: 2 TODS2: 1 TOAS: 12 Z_FLAG: 0 halt
DATA_STACK: [2]
ADDRESS_STACK: []
instr_counter: 5 ticks: 30Пример проверки исходного кода:
poetry run pytest . -v
============================================================================= test session starts ==============================================================================
platform darwin -- Python 3.12.0, pytest-7.4.4, pluggy-1.5.0 -- /Users/decafmango/Library/Caches/pypoetry/virtualenvs/stack-machine-otZU_h5E-py3.12/bin/python
cachedir: .pytest_cache
rootdir: /Users/decafmango/Desktop/stack-machine
configfile: pyproject.toml
plugins: golden-0.2.2
collected 5 items
golden_test.py::test_translator_and_machine[golden/hello_username.yml] PASSED [ 20%]
golden_test.py::test_translator_and_machine[golden/cat.yml] PASSED [ 40%]
golden_test.py::test_translator_and_machine[golden/fib_numbers.yml] PASSED [ 60%]
golden_test.py::test_translator_and_machine[golden/hello_world.yml] PASSED [ 80%]
golden_test.py::test_translator_and_machine[golden/add.yml] PASSED [100%]
============================================================================== 5 passed in 0.42s ===============================================================================| ФИО | алг | LoC | code инстр. | инстр. | такт. |
| Разинкин Александр Владимирович | add | 10 | 14 | 5 | 30 |
| Разинкин Александр Владимирович | cat | 18 | 21 | 258 | 1133 |
| Разинкин Александр Владимирович | hello_world | 23 | 41 | 198 | 994 |
| Разинкин Александр Владимирович | hello_username | 85 | 150 | 723 | 3668 |
| Разинкин Александр Владимирович | prob2 | 59 | 71 | 2000 | 9714 |