# modelmachine
Model machine emulator
[](https://travis-ci.org/vslutov/modelmachine)
## TODO
* Проверить test.alu.swap
* Работа с плавающей запятой
* Подумать еще о mock в тестах
* Переделать документацию модулей
* Исправить опечатки в документации
* Расширить howto
## Модельная машина
Модельная машина - это чистая архитектурная концепция, позволяющая понять
логику функционирования центральных процессоров. По своей структуре она близка
к компьютерам первого поколения. Подробнее читайте по ссылкам внизу.
## Quickstart
Установка пакета происходит командой:
# python3 -m pip install --upgrade modelmachine
После этого вам становится доступна консольная команда `modelmachine`.
Для проверки вы можете сделать `modelmachine test`. Будет выполнена
серия тестов, все тесты должны закончиться успехом.
Посмотрите примеры в папке <samples>, по их образу можно начинать писать
программы для модельных машин. Запуск программы делается командой:
$ modelmachine run program.mmach
Также доступна пошаговая отладка командой:
$ modelmachine debug program.mmach
Поддерживается компилирование ассемблера модельной машины (mmasm) в ее машинный
код.
$ modelmachine asmg source.mmasm result.mmach
### Пример
mm3
[config]
input = 0x100,0x101
output = 0x103
[code]
; x = ((a * -21) % 50 - b) ** 2 == 178929
03 0100 0005 0103 ; x := a * -21
04 0103 0006 0102 ; [0102] := x / 50, x := x % 50
02 0103 0101 0103 ; x := x - b
03 0103 0103 0103 ; x := x * x
99 0000 0000 0000 ; halt
; ---------------------
FFFFFFFFFFFFEB ; -21
00000000000032 ; 50
[input]
-123 456
* Все, что идет после символа `;` - комментарий.
* Первая строчка - обязательное название архитектуры. Список поддерживаемых
архитектур смотри ниже.
* После этого должна идти секция `config`, описывающая ячейки памяти,
по которым нужно производить ввод и вывод.
* После этого секция кода, содержащая набор 16-ричных чисел, записываемых в
память модельной машины. Пропускать часть машинного слова нельзя.
Рекомендуется писать по одному машинному слову в строке, по желанию
разбивая разряды на части пробелами.
* Пустые строки игнорируются.
* После этого идет секция ввода - несколько чисел, разделенных пробельными
символами. Их число должно совпадать с числом ячеек для ввода в параметре
`input` в секции `config`.
* Если секция ввода отсутствует или если она пустая, то входные данные читаются
со стандартного потока ввода до исполнения программы.
* По окончании работы на экран будут напечатаны десятичные числа со знаком,
лежащие в ячейках, перечисленных в параметре `output` в секции `config`.
### Язык ассемблера
Для машины с модификаией адресов поддерживается ассемблер.
Ассемблер нечувствителен к регистру. Команды компилятору предворяются точкой.
Доступные команды компилятора:
- `.config число` - дальнейшие команды и данные располагать начиная с адреса
`число`.
- `.code` - дальше идет исходный код, который нужно располагать начиная с
адреса `0x00`.
- `.word список_чисел` - разместить список чисел в памяти как есть, каждое
число занимает пару ячеек.
- `.dump имя_метки` - по завершении работы программы вывести содержимое памяти
по адресу `имя_метки`, команда выводит содержимое двух ячеек как одно число.
Коды команд те же, что и в таблице кодов `mmm`. Имя метки - последовательность
английских букв, цифр и знака `_`, первый символ последовательности - не цифра.
Адрес представляет собой либо имя метки, либо строку вида
`имя_метки(имя_регистра)`, где `имя_регистра` - одно из значений `R0-RF`.
Ввод данных не поддерживается.
.config 0x100
sum: .word 0
array: .word 1, 2, 3, 4, 5
zero: .word 0
size_word: .word 2
size_array: .word 10
.dump sum
.code
load R2, size_word
load RF, size_array
load R5, zero
rsub R6, R6
rpt: add R5, array(R6)
radd R6, R2
rcomp R6, RF
jneq rpt
store R5, sum
halt
## Внутреннее устройство
Данная реализация модельной машины состоит из классов, разбитых на
файлы-модули:
* `memory.py` - память; делится на два класса: `регистровая` и
`оперативная`; оперативная делится на `little-endian` и `big-endian`
* `numeric.py` - целочисленная арифметика с фиксированным числом
двоичных знаков
* `alu.py` - арифметико-логическое устройство, работает с четко
специализированными регистрами: `R1`, `R2`, `S`, `FLAGS` и `PC`.
* `cu.py` - контролирующее устройство, выполняющее
считывание команд из памяти и запускающее необходимые методы в
арифметико-логическом устройстве
* `io.py` - устройство ввода-вывода
* `cpu.py` - финальное объединение составляющих устройств в единое целое
* `asm.py` - ассемблер для машины с модификацией адресов
Здесь дано поверхностное описание модулей. За более подробным
обращайтесь к документации конкретных модулей и их исходным кодам.
### memory.py
`AbstractMemory` - класс абстрактной памяти, предоставляющий интерфейс для
надежной связи частей компьютера. Основные методы: `fetch` и `put`, которые
принимают на вход адрес в памяти и количество битов, с которыми нужно работать,
количество должно быть кратно размеру ячейки (слова). Строго
рекомендуется их использовать везде.
`RandomAccessMemory` - класс, реализующий память прямого доступа. При
инициализации указывается размер машинного слова и количество этих слов. Если
`is_protected=True`, то при попытке считывания из неинициализированной ячейки
будет выброшено исключение, иначе, метод `fetch` вернет нуль.
`RegisterMemory` - класс, реализующий регистровую память. Метод `add_register`
добавляет регистр определенного размера или проверяет, что уже добавленный
регистр имеет правильный размер.
### numeric.py
Класс Integer реализует целочисленную арифметику фиксированной длины.
Поддерживаемые операторы: `+`, `-`, `*`, `/`, `%`, `==`, `!=`. Плюс методы
`get_value` и `get_data`. Округление при делении производится в сторону нуля.
### alu.py
Арифметико-логическое устройство работает с четко специализированными
регистрами:
* `R1`, `R2`, `S` для арифметических операций.
* `FLAGS` для хранения флагов состояния.
* `PC` *только* для пересылки туда адреса из регистра `R1` при условных
переходах.
Схема работы:
* Арифметические команды: `add`, `sub`, `smul`, `sdiv`, `umul`, `udiv`,
`sdivmod`, `udivmod`. За исключением команд `divmod` арифметические
команды работают следующим образом: `S := R1 op R2`.
Плюс в зависимости от результата выставляется регистр `FLAGS` - комбинация
флагов CF, OF, SF и ZF.
* `add` и `sub` - сложение и вычитание соответсвенно.
* `smul` и `sdiv` - знаковое умножение и деление соответсвенно.
* `umul` и `udiv` - беззнаковое умножение и деление соответсвенно.
* `sdivmod` и `udivmod` - знаковое и беззнаковое соответственно деление с
остатком. `S := R1 / R2; R1 := R1 % R2`.
* Команда пересылки `move`: `S := R1`.
* Команды безусловного перехода `jump` и условного перехода `cond_jump`
работают по схеме `PC := R1`, режим работы `cond_jump` зависит от того,
какие дополнительные аргументы будут переданы.
* Команда останова `halt` просто выставляет флаг остановки HALT в
регистре флагов
### cu.py
Управляющее устройство.
#### AbstractControlUnit
Обычно управляющее устройство работает по схеме:
1. `fetch_and_decode` - загрузка и расшифровка очередной команды.
Содержимое ячейки оперативной памяти с адресом записанным
в регистре `PC` загружается в регистр `RI`, затем из него извлекается
код операции и адреса операндов, затем счетчик `PC` увеличивается на
длину только что считанной команды.
2. `load` - данные по только что считанным адресам загружаются в регистры
процессора `R1` и `R2`
3. `execute` - в зависимости от кода операции в арифметико-логическом
устройстве запускается та или иная схема вычислений.
4. `write_back` - результат вычислений записывается куда полагается (например,
по одному из адресов считанных в начале).
Все эти методы поддерживаются в `AbstractControlUnit`.
Также в нем написаны использующие их методы, являющиеся интерфейсом
устройства управления:
* `step` - сделать один шаг, описанный алгоритмом выше.
* `get_status` - вернуть статус процессора (выполняется/остановлен).
Остановка производится командой останова `halt`.
* `run` - выполнять один шаг за другим, пока процессор не будет остановлен.
Далее, наследники `AbstractControlUnit` определяют первые 4 метода.
### io.py
Устройство ввода-вывода.
* При инициализации устанавливается адрес с которого нужно загружать
программы пользователя.
* Метод `load_source` загружает последовательность шеснадцатиричных слов
по указанному адресу.
* Метод `load_data` загружает данные (полученные из строки чисел)
по данным адресам.
* Методы `get_int` и `put_int` работают с содержимым одного слова.
Размер слова устанавливается при инициализации.
### cpu.py
Финальная сборка всех составных устройств в единое целое.
* Поддерживается доступ к составным устройствам. Например, доступ
к устройству ввода/вывода можно получить через `cpu.io_unit`,
к регистрам через `cpu.registers` и так далее.
* `load_program` - загрузка программы, конфигурации и данных в оперативную
память.
* `print_result` - печать результата работы программы.
* `run_file` - загрузка, исполнение и печать результата.
## Поддерживаемые архитектуры
### Как добавить новую архитектуру?
1. Выписать все команды устройстройства и их коды.
2. Добавить их в таблицу ниже и описание еще ниже.
3. Добавить новый класс устройства управления на основе существующего.
4. Добавить новый класс CPU использующий это устройство управления,
добавить этот класс в список `CPU_LIST` в файле `cpu.py`.
5. Добавить тесты для обоих этих классов в файлы `tests/test_cu.py` и
`tests/test_cpu.py`.
6. Добавить примеры в папку `samples`.
7. Прислать pull request.
### Таблица команд модельных машин
|OPCODE|mm-3 |mm-2 |mm-v |mm-1 |mm-m |
|:-----|:---:|:---:|:---:|:---:|:----:|
|0x00 |move |move |move |load | load |
|0x01 | add | add | add | add | add |
|0x02 | sub | sub | sub | sub | sub |
|0x03 |smul |smul |smul |smul | smul |
|0x04 |sdiv |sdiv |sdiv |sdiv | sdiv |
|0x05 | |comp |comp |comp | comp |
|0x13 |umul |umul |umul |umul | umul |
|0x14 |udiv |udiv |udiv |udiv | udiv |
|0x10 | | | |store|store |
|0x20 | | | |swap | move |
|0x21 | | | | | radd |
|0x22 | | | | | rsub |
|0x23 | | | | |rsmul |
|0x24 | | | | |rsdiv |
|0x25 | | | | |rcomp |
|0x33 | | | | |rumul |
|0x34 | | | | |rudiv |
|0x80 |jump |jump |jump |jump | jump |
|0x81 | jeq | jeq | jeq | jeq | jeq |
|0x82 |jneq |jneq |jneq |jneq | jneq |
|0x83 | sjl | sjl | sjl | sjl | sjl |
|0x84 |sjgeq|sjgeq|sjneq|sjgeq|sjgeq |
|0x85 |sjleq|sjleq|sjleq|sjleq|sjleq |
|0x86 | sjg | sjg | sjg | sjg | sjg |
|0x93 | ujl | ujl | ujl | ujl | ujl |
|0x94 |ujgeq|ujgeq|ujgeq|ujgeq|ujgeq |
|0x95 |ujleq|ujleq|ujleq|ujleq|ujleq |
|0x96 | ujg | ujg | ujg | ujg | ujg |
|0x99 |halt |halt |halt |halt | halt |
На самом деле операция `div` запускает в АЛУ схему `divmod`.
Ниже дана таблица команд условных переходов.
Откуда берутся операнды для сравнения зависит от архитектуры модельной
машины. Подробнее смотри *[1]*.
|Мнемонический код|Условие перехода|Расшифровка/описание |
|:----------------|:--------------:|:--------------------------------|
|jeq | == |jump if equal |
|jneq | != |jump if not equal |
|sjl | < s |signed jump if less |
|sjgeq | >= s |signed jump if greater or equal |
|sjleq | <= s |signed jump if less or equal |
|sjg | > s |signed jump if greater |
|ujl | < u |unsigned jump if less |
|ujgeq | >= u |unsigned jump if greater or equal|
|ujleq | <= u |unsigned jump if less or equal |
|ujg | > u |unsigned jump if greater |
### mm-3
Архитектура трехадресной модельной машины.
* Размер ячейки оперативной памяти: 7 байт.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся с одной ячейкой оперативной памяти.
* Код команды помещается в одну ячейку оперативной памяти `КОП А1 А2 А3`.
* Регистры: `S`, `R1`, `R2`, `FLAGS`, `PC`, `RI`, `ADDR`.
Назначение регистров:
* `S` - регистр сумматор, в него записывается результат арифметической операции.
* `R1`, `R2` - регистры операндов арифметических операций.
* `FLAGS` - регистр флагов.
* `PC` - регистр указатель инструкции.
* `RI` - регистр для хранения инструкции.
* `ADDR` - регистр для хранения адреса для инструкции перехода.
Действия процессора для арифметических инструкций (`add`, `sub`,
`smul`, `sdiv`, `umul`, `udiv`) `КОП A1 A2 A3`:
1. Загрузить содержимое ячейки оперативной памяти с адресом `А1` в
регистр `R1` (`R1 := [A1]`).
2. Загрузить содержимое ячейки оперативной памяти с адресом `А2` в
регистр `R2` (`R2 := [A2]`).
3. Запустить в АЛУ схему, реализующую операцию, задаваемую `КОП`.
4. Записать результат из регистра `S` в ячейку оперативной памяти с
адресом `А3`.
Если выполняется операция деления, в оперативную память записываются
два результата: частное – в ячейку с адресом `А3`, остаток – в следующую
ячейку, по адресу `(А3+1) mod 16^4`.
* `jump A1 A2 A3`: `PC := A3`
* Условные переходы: сравниваются `R1` и `R2`, в зависимости от результата
происходит `PC := A3`.
* Команда пересылки `move`: [A3] := R1.
### mm-2
Архитектура двухадресной модельной машины.
* Размер ячейки оперативной памяти: 5 байт.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся с одной ячейкой оперативной памяти.
* Код команды помещается в одну ячейку оперативной памяти `КОП А1 А2`.
* Регистры: `R1`, `R2`, `FLAGS`, `PC`, `RI`, `ADDR`.
Действия для арифметических команд `add`, `sub`, `smul`, `sdiv`, `umul`,
`udiv`:
1. `R1 := [A1], R2 := [A2]`
2. `R1 := R1 op R2`
3. `[A1] := R1`
Действия для команды сравнения `cmp`:
1. `R1 := [A1], R2 := [A2]`
2. Запустить в АЛУ схему `sub`, выставить регистр `FLAGS`
* `jump A1 A2`: `PC := A2`
* Условные переходы делаются исходя из регистра `FLAGS`
* `move A1 A2`: `[A1] := [A2]`
* Команда останова `halt` взводит флаг `HALT` в регистре `FLAGS`
### mm-v
Архитектура модельной машины с переменным (variable) фарматом команд.
* Размер ячейки оперативной памяти: 1 байт.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся со словами в 5 ячеек оперативной
памяти.
* Код команды занимает разное количество ячеек в зависимости от выполняемой
операции.
* Регистры: `R1`, `R2`, `FLAGS`, `PC`, `RI`, `ADDR`.
Таблица кодов команд:
|Код команды|Мнемоник|Формат |Длина (в байтах)|
|:----------|:------:|:---------|---------------:|
|0x00 |move |move A1 A2| 5|
|0x01 |add |add A1 A2| 5|
|0x02 |sub |sub A1 A2| 5|
|0x03 |smul |smul A1 A2| 5|
|0x04 |sdiv |sdiv A1 A2| 5|
|0x05 |comp |comp A1 A2| 5|
|0x13 |umul |umul A1 A2| 5|
|0x14 |udiv |udiv A1 A2| 5|
|0x80 |jump |jump A1 | 3|
|0x81 |jeq |jeq A1 | 3|
|0x82 |jneq |jneq A1 | 3|
|0x83 |sjl |sjl A1 | 3|
|0x84 |sjgeq |sjgeq A1 | 3|
|0x85 |sjleq |sjleq A1 | 3|
|0x86 |sjg |sjg A1 | 3|
|0x93 |ujl |ujl A1 | 3|
|0x94 |ujgeq |ujgeq A1 | 3|
|0x95 |ujleq |ujleq A1 | 3|
|0x96 |ujg |ujg A1 | 3|
|0x99 |halt |halt | 1|
Действия для арифметических команд `add`, `sub`, `smul`, `sdiv`, `umul`,
`udiv`:
1. `R1 := [A1], R2 := [A2]`
2. `R1 := R1 op R2`
3. `[A1] := S`
Действия для команды сравнения `cmp`:
1. `R1 := [A1], R2 := [A2]`
2. Запустить в АЛУ схему `sub`, выставить регистр `FLAGS`
* `jump A1`: `PC := A1`
* Условные переходы делаются исходя из регистра `FLAGS`
* `move A1 A2`: `[A1] := [A2]`
* Команда останова `halt` взводит флаг `HALT` в регистре `FLAGS`
### mm-1
Архитектура одноадресной модельной машины.
* Размер ячейки оперативной памяти: 3 байта.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся с одной ячейкой оперативной памяти.
* Код команды помещается в одну ячейку оперативной памяти `КОП А`.
* Регистры: `S`, `R`, `S1`, `FLAGS`, `PC`, `RI`.
Регистры `S` и `S1` хранят информацию постоянно, а не затираются при
выполнении очередной команды, как было раньше. В регистр `R` закгружается
операнд для арифметических операций.
Действия для арифметических команд (исключая деление) `add`, `sub`, `smul`,
`umul`:
1. `R := [A]`
2. `S := S op R`
Действия для команд деления `sdivmod`, `udivmod`:
1. `R := [A]`
2. `S := S / R; S1 := S % R`
Действия для команды сравнения `cmp`:
1. `R := [A]`
2. Запустить в АЛУ схему `sub`, выставить регистр `FLAGS`
* `jump A`: `PC := A`
* Условные переходы делаются исходя из регистра `FLAGS`
* `load A`: `S := [A]`
* `store A`: `[A] := S`
* `swap`: `S, S1 := S1, S`
* Команда останова `halt` взводит флаг `HALT` в регистре `FLAGS`
### mm-m
Архитектура модельной машины с модификацией адресов (modification).
* Размер ячейки оперативной памяти: 2 байта.
* Размер адреса: 2 байта.
* Арифметические вычисления производятся со словом в 4 байта.
* Код команды занимает разное количество ячеек в зависимости от выполняемой
операции. Арифметические команды имеют формы регистр-регистр и регистр-память.
Команды регистр-регистр имеют формат `КОП RA1 RA2` и занимают 2 байта.
Команды регистр-память имеют формат `КОП R M A` и занимают 4 байта.
Команды перехода имеют формат `КОП 0 0 A` и занимают 4 байта.
* Регистры: `R0-RF`, `S`, `RZ`, `FLAGS`, `PC`, `RI`.
Основное отличие этой машины от предыдущих - наличие адресуемых регистров
общего назначения `R0-RF`, используемых для арифметических
вычислений и адресации памяти. `S`, `RZ` - неадресуемые регистры для работы
АЛУ.
Также адресация данных теперь производится таким алгоритмом:
1. Возьмем содержимое адресуемого регистра с номером `M` (от 0x0 до 0xF): `[M]`.
Если номер регистра `M` равен нулю, значение `[M]` также равно нулю вне
зависимости от содержимого регистра `R0`.
2. Добавим к нему адрес `A` (от 0x0000 до 0xFFFF): `[M] + A`.
3. Возьмем остаток от деления этого адреса на 2^16: `([M] + A) % 2^16`.
4. Возьмем из ОЗУ данные по полученному адресу: `[[M] + A]`.
Таблица кодов команд:
|Код команды|Мнемоник|Формат |Длина (в байтах)|
|:----------|:------:|:----------|---------------:|
|0x00 |load |load R M A | 4|
|0x01 |add |add R M A | 4|
|0x02 |sub |sub R M A | 4|
|0x03 |smul |smul R M A | 4|
|0x04 |sdiv |sdiv R M A | 4|
|0x05 |comp |comp R M A | 4|
|0x11 |addr |addr R M A | 4|
|0x13 |umul |umul R M A | 4|
|0x14 |udiv |udiv R M A | 4|
|0x10 |store |store R M A| 4|
|0x20 |rmove |rmove RX RY| 2|
|0x21 |radd |radd RX RY | 2|
|0x22 |rsub |rsub RX RY | 2|
|0x23 |rsmul |rsmul RX RY| 2|
|0x24 |rsdiv |rsdiv RX RY| 2|
|0x25 |rcomp |rcomp RX RY| 2|
|0x33 |rumul |rumul RX RY| 2|
|0x34 |rudiv |rudiv RX RY| 2|
|0x80 |jump |jump 0 M A | 4|
|0x81 |jeq |jeq 0 M A | 4|
|0x82 |jneq |jneq 0 M A | 4|
|0x83 |sjl |sjl 0 M A | 4|
|0x84 |sjgeq |sjgeq 0 M A| 4|
|0x85 |sjleq |sjleq 0 M A| 4|
|0x86 |sjg |sjg 0 M A | 4|
|0x93 |ujl |ujl 0 M A | 4|
|0x94 |ujgeq |ujgeq 0 M A| 4|
|0x95 |ujleq |ujleq 0 M A| 4|
|0x96 |ujg |ujg 0 M A | 4|
|0x99 |halt |halt 00 | 2|
Действия для загрузки исполнительного адреса в регистр `addr R M A`:
1. `S := [M] + A`
2. `R := S`
Действия для арифметических команд регистр-память (исключая деление) `add`,
`sub`, `smul`, `umul` (формат `op R M A`):
1. `S, RZ := R, [[M] + A]`
2. `S := S op RZ`
3. `R := S`
Действия для команд деления регистр-память `sdivmod` и `udivmod`
(формат `op R M A`, `R_next` - регистр, следующий за регистром `R`):
1. `S, RZ := S, [[M] + A]`
2. `S, RZ := S / RZ, S % RZ`
3. `R, R_next := S, RZ`
Действия для команды сравнения `comp R M A`:
1. `S, RZ := S, [[M] + A]`
2. Запустить в АЛУ схему `sub S RZ`, выставить регистр `FLAGS`
Действия для команды загрузки `load R M A`:
1. `R := [[M] + A]`
Действия для команды выгрузки `store R M A`:
1. `[[M] + A] := R`
Действия для арифметических команд регистр-регистр (исключая деление) `radd`,
`rsub`, `rsmul`, `rumul` (формат `op RX RY`):
1. `S, RZ := RX, RY`
2. `S := S op RZ`
3. `RX := S`
Действия для команд деления регистр-регистр `rsdiv` и `rudiv`
(формат - `op RX RY`; `RX_next` - регистр, следующий за регистром `RX`, если
`RX = RF`, то `RX_next = R0`):
1. `S, RZ := RX, RY`
2. `S, RZ := S / RZ, S % RZ`
3. `RX, RX_next := S, RZ`
Действия для команды сравнения `rcomp RX RY`:
1. `S, RZ := RX, RY`
2. Запустить в АЛУ схему `sub S RZ`, выставить регистр `FLAGS`
* `jump 00 A`: `PC := A`
* Условные переходы делаются исходя из регистра `FLAGS`
* Команда останова `halt` взводит флаг `HALT` в регистре `FLAGS`
## References
1. E. А. Бордаченкова - "Модельные ЭВМ" <http://al.cs.msu.su/files/ModComp.pdf>
2. Е. А. Бордаченкова - "Архитектура ЭВМ. Учебные машины. Методическое пособие"
<http://al.cs.msu.su/files/bordachenkova.architecture.model.machines.2010.doc>
3. В. Г. Баула - "Введение в архитектуру ЭВМ и системы программирования"
<http://arch.cs.msu.ru/Page2.htm>
4. <http://cmcmsu.no-ip.info/1course/um3.command.set.htm>