Пишем регистровую машину

29 August 2019

Что-то давно я не писал в свой блог. Нужно исправлять данное недоразумение.

И сегодня в программе: регистровая виртуальную машину на языке Rust.

Введение

На написание собственной упрощенной версии меня вдохновили несколько статей с хабра, ссылки на них смотри в разделе [Полезные ссылки](#Полезные ссылки).

Но для начала давайте определимся с терминалогией с помощью вики.

Виртуальная машина (VM, от англ. virtual machine) — программная и/или аппаратная система, эмулирующая аппаратное обеспечение некоторой платформы (target — целевая, или гостевая платформа) и исполняющая программы для target-платформы на host-платформе (host — хост-платформа, платформа-хозяин) или виртуализирующая некоторую платформу и создающая на ней среды, изолирующие друг от друга программы и даже операционные системы (см.: песочница); также спецификация некоторой вычислительной среды (например: «виртуальная машина языка программирования Си»).

В общем разработанная нами программа не является в полной мере виртуальной машиной, а скорее всего её стоит называть интерпретатором кода. Эти разбирательства в терминологии я оставляю на читателя.

Давайте теперь перейдём к определение стековой машины — в общем говоря их два вида: стековая и регистровая и исходя из названий можно понять, что стековая машина использует для расчёт стек, а регистровая регистры... Но это не совсем так, в основном стековая использует только стек, а вот регистровая может использовать регистры и стек. Но это опять же терминологические фишки.

Мы же в своей реализации будем использовать только регистровую модель.

Вроде определились со всеми важными аспектами и теперь можно перейти к примеру, на котором будем проводить тесты.

Тестовый пример

Наша задачка основана на Гипотезе Коллатца и звучит вот так:

Следующая повторяющаяся последовательность определена для множества натуральных чисел:
n → n/2 (n - чётное)
n → 3n + 1 (n - нечётное)

Используя описанное выше правило и начиная с 13, сгенерируется следующая последовательность:
13 → 40 → 20 → 10 → 5 → 16 → 8 → 4 → 2 → 1

Получившаяся последовательность (начиная с 13 и заканчивая 1) содержит 10 элементов.

Какой начальный элемент меньше миллиона генерирует самую длинную последовательность?

В нашем же примере будем делать расчёт от единицы до миллиона и для интереса реализуем её на нескольких языках:

для языка Python
для языка Rust
для нашей виртуальной машин, назовём её vm_asm

Также стоит уточнить, что реализацию будем делать наивную чтобы не мучится с оптимизацией, да и это не самоцель для данного поста.

Алгоритм нахождения длины цепочки

Входные параметры:

start_value — начальное значение

Выходные параметры:

seq_length — длина последовательности

Алгоритм:

установить значение start_value в 0
цикл пока seq_length > 1
- если остаток от деления seq_length на 2 равен нулю, то:
  - поделить с округлением вниз start_value на 2
  - увеличить seq_length на 1
- иначе
  - умножить start_value на 3 и прибавить единицу
  - поделить с округлением вниз start_value на 2
  - увеличить seq_length на 2

Вы могли заметить, что в блоке с "иначе" мы делаем сразу два шага и вы будете правы. Это небольшая оптимизация, на которую я пошёл :)

Реализация на Python

На Python код будет выглядеть следующим образом:

def calc(index):
    step = 0
    while index > 1:
        if index % 2 == 0:
            index //= 2
            step += 1
        else:
            index = (3 * index + 1) // 2
            step += 2
    return step

Остаётся только перебрать все значения от 1 и до 1_000_000 включительно и выбрать максимально длинную цепочку, что можно сделать вот так:

result = 0
for i in range(1, 1000001):
    result = max(result, calc(i))
print(result)

Реализация на Rust

Реализация на языке Rust мало чем отличается от питоновского, лишь только синтаксис по другому выглядит и используется функция main.

fn calc(mut index: u64) -> u64 {
    let mut step = 0;
    while index > 1 {
        if index % 2 == 0 {
            index /= 2;
            step += 1;
        } else {
            index = (3 * index + 1) / 2;
            step += 2;
        }
    }
    step
}

fn main() {
    let mut result = 0;
    for i in 1..1_000_001 {
        result = result.max(calc(i));
    }
    println!("{:?}", result);
}

Реализация на виртуальной машине

Приступим к самому интересному, а именно к коду для виртуальной машины.

Я буду полагаться на Intel-подобный синтаксис ассемблера, т.к. он намного привычнее выглядит чем от AT&T.

И да, программа будет на ассемблере, так как его опкоды с операндами намного легче парсить, чем любой императивный язык программирования.

Начнём!

Сначала произведём инициализацию регистров необходимыми значениями

# r0 -- выходной результат
mov r0, 0
# r1 -- конечное значения для внешнего цикла for
mov r1, 1000001
# r2 -- внешний индекс для цикл for
mov r2, 1

Определим внешний цикл от for

# внешний цикл for
_next_step:
    inc r2
    cmp r2, r1
    # переход к печати результата
    jg _end_of_app

И последующий за ней блок с "функцией"

_calc_start:
    # r3 -- текущая длина цепочки (цикл while)
    mov r3, 0
    # r4 -- текущий индекс (цикл while)
    mov r4, r2

Внутренний цикл while выглядит немного мудрено, но это по сути прямой перенос питоновского кода на ассемблер

# внутренний цикл while
_while:
    cmp r4, 1
    jle _end_of_calc
    # r5 временный регистр для проверки на index % 2 == 0
    mov r5, r4
    mod r5, 2
    cmp r5, 0
    jne _3n_part
    # ветка при index % 2 == 0
    shr r4, 1
    inc r3
    jmp _while

# ветка при index % 2 != 0
_3n_part:
    mul r4, 3
    inc r4
    shr r4, 1
    add r3, 2
    jmp _while

Остаётся только выбрать максимальное значение цепочки и вывести на печать значение, если обход закончен

# выбора максимальной длины цепочки
_end_of_calc:
    cmp r3, r0
    jle _next_step
    mov r0, r3
    jmp _next_step

# вывод результата
_end_of_app:
    print r0

Реализация интерпретатора

Так как я не очень хочу реализовывать весь функционал какого-то процессора, то ограничимся небольшим набором команд, который нужен нам для решения задачки.

Исходя ранее написанного кода можно выделить следующий набор команд:

mov #1, #2 — поместить значение из #2 в #1
cmp #1, #1 — сравнить #1 и #2 и изменить регистровые флаги
jg #1 — перейти к #1 если F1 равен 0
jle #1 — перейти к #1 если F1 не равен 0
jne # — переход к #1 если F2 равен 0
jmp #1 — безусловный переход к метку #1
inc #1 — увеличить #1 на единицу
mod #1, #2 — деление модулю #1 на #2
add #1, #2 — добавить #2 к #1
mul #1, #2 — умножить #1 на #2
shr #1, #2 — логический сдвиг вправо #1 на #2
print #1 — вывести значение #1 в консоль

Здесь F1 и F2 два регистровых флага, о которых поговорим позднее.

Теперь давайте определимся с работой нашего интерпретатора, то есть с шагами которые он должен выполнить:

Загрузить файл исходного кода
Разобрать каждую строку на инструкцию
Выполнить код

Давайте для начала определим сущность виртуальной машины

struct VirtualMachine {
    ip: u8,
    reg: [u64; 8],
    app: Vec<Opcode>,
    label: HashMap<String, u8>,
    flags: [bool; 2]
}

У нас будет:

указатель на выполняемую инструкцию ip, так называемый Instruction Pointer
восемь 64-х байтовых регистра reg, так как много нам их и не надо
вектор с опкодами приложения app, то есть наша программа
хэшмап с метками label для реализации произвольного перехода к командам программы
и два флага, так называемый Регистр Флагов, но в упрощенном виде

Для упрощения написания программы регистр флагов у нас представляется только двумя значениями, хотя всегда можно реализовать весь их набор.

Установку флагов F1 и F2 будем делать вот таким образом — при сравнении двух значений с помощью опкода cmp:

если #1 больше #2, то F1 = 1, иначе F1 = 0
если #1 равен #2, то F2 = 1, иначе F2 = 0

здесь #1 — первый операнд, #2 — второй операд.

Теперь можно определить перечисление с нашим набором команд

enum Opcode {
    // сложение двух регистров
    ADD_r { r1: u8, r2: u8 },
    // сложение регистра и значения
    ADD_v { r1: u8, v1: u64 },
    // инкремент регистра
    INC { r1: u8 },
    // деление по модулю (регистр на регистр)
    MOD_r { r1: u8, r2: u8 },
    // деление по модулю (регистр на значение)
    MOD_v { r1: u8, v1: u64 },
    // перемножение двух регистров
    MUL_r { r1: u8, r2: u8 },
    // умножение регистра на значение
    MUL_v { r1: u8, v1: u64 },
    // сдвиг регистра на значение из другого регистра
    SHR_r { r1: u8, r2: u8 },
    // сдвиг регистра на значение
    SHR_v { r1: u8, v1: u64 },
    // безусловный переход к метку
    JMP { i: u8 },
    // переход если #1 больше #2
    JG { i: u8 },
    // переход если #1 меньше, либо равно #2
    JLE { i: u8 },
    // переход если #1 не равно #2
    JNE { i: u8 },
    // поместить в регистр значение другого регистра
    MOV_r { r1: u8, r2: u8 },
    // поместить в регистр значение
    MOV_v { r1: u8, v1: u64 },
    // сравнить два регистра
    CMP_r { r1: u8, r2: u8 },
    // сравнить регистр и значение
    CMP_v { r1: u8, v1: u64 },
    // распечатать содержимое регистра
    PRINT { r1: u8 }
}

Теперь остаётся только описать скелет программы

impl VirtualMachine {
    // функция инициализации
    fn new() -> VirtualMachine {
        VirtualMachine {
            ip: 0,
            reg: [0_u64; 8],
            app: Vec::new(),
            label: HashMap::new(),
            flags: [false; 2]
        }
    }
    // функция преобразованеи кода в файле в набор инструкций
    fn parse_code(&mut self, filename: &str) {}
    // функция для запуска кода на выполнение
    fn interp(&mut self) {}
}

fn main() {
    let mut vm = VirtualMachine::new();
    vm.parse_code("collatz.vm_asm");
    vm.interp();
}

Остаётся только реализовать два недостающих блока по парсингу и интерпретации кода.

Начнём с самой простой функции, а именно interp. Тут всё просто вытаскиваем инструкцию по ip из app и выполняем её, попутно увеличивая значение ip. После того как значение ip будет больше чем количества инструкций в app можно закончить выполнение.

В коде это выглядит вот так:

fn interp(&mut self) {
    while self.ip < self.app.len() as u8 {
        match self.app[self.ip as usize] {
            // здесь будут инструкции
        }
        self.ip += 1;
    }
}

А теперь к коду инструкций, которые очень просты в реализации

Opcode::ADD_r { r1, r2 } => {
    // прибавляем к первому регистру второй
    self.reg[r1 as usize] += self.reg[r2 as usize];
},
Opcode::ADD_v { r1, v1 } => {
    // прибавляем значение к регистру
    self.reg[r1 as usize] += v1;
},
Opcode::INC { r1 } => {
    // инкремент
    self.reg[r1 as usize] += 1;
},
Opcode::MOD_r { r1, r2 } => {
    // деление по модулю регистр на регистр
    self.reg[r1 as usize] %= self.reg[r2 as usize];
},
Opcode::MOD_v { r1, v1 } => {
    // деление по модулю регистр на значение
    self.reg[r1 as usize] %= v1;
},
Opcode::MUL_r { r1, r2 } => {
    // умножение регистров
    self.reg[r1 as usize] *= self.reg[r2 as usize];
},
Opcode::MUL_v { r1, v1 } => {
    // умножение на значение
    self.reg[r1 as usize] *= v1;
},
Opcode::SHR_r { r1, r2 } => {
    // сдвиг на значение во втором регистре
    self.reg[r1 as usize] >>= self.reg[r2 as usize];
},
Opcode::SHR_v { r1, v1 } => {
    // сдвиг на значение
    self.reg[r1 as usize] >>= v1;
},
Opcode::JMP { i } => {
    // меняем значение ip и переходим к циклу, без увеличения ip
    self.ip = i;
    continue;
},
Opcode::JG { i } => {
    // если F1 равен true, то меняем ip
    if self.flags[0] {
        self.ip = i;
        continue;
    }
},
Opcode::JLE { i } => {
    // если F1 не равен true, то меняем ip
    if !self.flags[0] {
        self.ip = i;
        continue;
    }
}
Opcode::JNE { i } => {
    // если F2 равен true, то меняем ip
    if self.flags[1] {
        self.ip = i;
        continue;
    }
},
Opcode::MOV_r { r1, r2 } => {
    // значение второго регистра записываем в первый
    self.reg[r1 as usize] = self.reg[r2 as usize];
},
Opcode::MOV_v { r1, v1 } => {
    // записываем значение в регистр
    self.reg[r1 as usize] = v1;
},
Opcode::CMP_r { r1, r2 } => {
    // получаем значения в регистрах
    let (v1, v2) = (self.reg[r1 as usize], self.reg[r2 as usize]);
    // и устанавливаем флаги в соответствии с ранее описанными условиями
    self.flags[0] = if v1 > v2 { true } else { false };
    self.flags[1] = if v1 != v2 { true } else { false };
},
Opcode::CMP_v { r1, v1 } => {
    // тоже самое, но только второй операнд -- число
    let v0 = self.reg[r1 as usize];
    self.flags[0] = if v0 > v1 { true } else { false };
    self.flags[1] = if v0 != v1 { true } else { false };
},
Opcode::PRINT { r1 } => {
    // вывод на печать значение регистра
    let v1 = self.reg[r1 as usize];
    println!("{}", v1);
}

Остаётся парсинг кода, который я разбил на несколько шагов:

чтение всего файла
парсинг меток для реализации переходов
парсинг основного кода

Чтение файла и разбор на отдельные блоки реализуется в пару строк

// чтения всего файла в строку
let mut f = File::open(filename).unwrap();
let mut buffer = String::new();
f.read_to_string(&mut buffer).unwrap();
// разбор на инструкции
let instr: Vec<&str> = buffer.split('\n')
                             // разделение строк по переносам
                             .map(|x| x.trim())
                             // убираем начальные и конечные пробелы в строке
                             .filter(|x| !x.starts_with('#') && x.len() > 3)
                             // убираем строки с комментариями
                             .collect();
                             // сбор значений в вектор

Далее проходимся по списку инструкций и вычленяем из него метки

for (index, item) in instr.iter().enumerate() {
    // наши метки начинаются с символа '_'
    if item.starts_with('_') {
        // номер строки определяем из индекса текущей строк минус количество уже определенных меток
        let label_index = index as u8 - self.label.len() as u8;
        // добавляем в хэшмап имя метки и номер строки для перехода
        self.label.insert(item[..item.len() - 1].to_string(), label_index);
    }
}

Осталось только преобразовать строковое представление инструкции в Opcode, но перед этим нужно определить пару вспомогательных функций

// функция проверяющая аргумент на принадлежность к регистру процессора
fn is_register(s: &str) -> bool {
    s.starts_with('r')
}

// получение индекса регистра из строки
fn parse_register(s: &str) -> u8 {
    s[1..].parse().unwrap()
}

// получение значения из строки
fn parse_value(s: &str) -> u64 {
    s.parse().unwrap()
}

Ну и собственно парсинг инструкций

for item in instr {
    // обрабатываем все строки, кроме меток
    if !item.starts_with('_') {
        // разбиваем строку по двум разделителям (' ' и ',') и отбрасываем пустые
        let block: Vec<&str> = item.split(|c| c == ' ' || c == ',')
                                   .filter(|c| c.len() > 0)
                                   .collect();
        // используем Slice pattern, чтобы разобрать список об образцу
        let cmd = match &block[..] {
            // инструкция сложения
            &["add", arg1, arg2] => {
                match (is_register(arg1), is_register(arg2)) {
                    // оба значения регистры
                    (true, true) => Opcode::ADD_r { r1: parse_register(arg1), r2: parse_register(arg2) },
                    // второе параметр является числом
                    (true, false) => Opcode::ADD_v { r1: parse_register(arg1), v1: parse_value(arg2) },
                    // в любых других случаях кидаем ошибку
                    _ => panic!("not valid arguments `{}, {}` for ADD", arg1, arg2)
                }
            }
            // инкремент
            &["inc", arg1] => {
                if is_register(arg1) {
                    Opcode::INC { r1: parse_register(arg1) }
                } else {
                    panic!("not valid argument `{}` for INC", arg1);
                }
            }
            // деление по модулю
            &["mod", arg1, arg2] => {
                match (is_register(arg1), is_register(arg2)) {
                    (true, true) => Opcode::MOD_r { r1: parse_register(arg1), r2: parse_register(arg2) },
                    (true, false) => Opcode::MOD_v { r1: parse_register(arg1), v1: parse_value(arg2) },
                    _ => panic!("not valid arguments `{}, {}` for MOD", arg1, arg2)
                }
            }
            // умножение
            &["mul", arg1, arg2] => {
                match (is_register(arg1), is_register(arg2)) {
                    (true, true) => Opcode::MUL_r { r1: parse_register(arg1), r2: parse_register(arg2) },
                    (true, false) => Opcode::MUL_v { r1: parse_register(arg1), v1: parse_value(arg2) },
                    _ => panic!("not valid arguments `{}, {}` for MUL", arg1, arg2)
                }
            }
            // логический сдвиг вправо
            &["shr", arg1, arg2] => {
                match (is_register(arg1), is_register(arg2)) {
                    (true, true) => Opcode::SHR_r { r1: parse_register(arg1), r2: parse_register(arg2) },
                    (true, false) => Opcode::SHR_v { r1: parse_register(arg1), v1: parse_value(arg2) },
                    _ => panic!("not valid arguments `{}, {}` for SHR", arg1, arg2)
                }
            }
            // безусловный переход
            &["jmp", arg1] => {
                // проверяем на существование метки
                match self.label.get(arg1) {
                    // формируем команду перехода к метке, если она есть
                    Some(value) => Opcode::JMP { i: *value },
                    // иначе -- ошибка
                    None => panic!("label `{}` not found!", arg1)
                }
            }
            // переход если больше
            &["jg", arg1] => {
                match self.label.get(arg1) {
                    Some(value) => Opcode::JG { i: *value },
                    None => panic!("label `{}` not found!", arg1)
                }
            }
            // переход при меньше, либо равно
            &["jle", arg1] => {
                match self.label.get(arg1) {
                    Some(value) => Opcode::JLE { i: *value },
                    None => panic!("label `{}` not found!", arg1)
                }
            }
            // переход если не равно
            &["jne", arg1] => {
                match self.label.get(arg1) {
                    Some(value) => Opcode::JNE { i: *value },
                    None => panic!("label `{}` not found!", arg1)
                }
            }
            // копирование
            &["mov", arg1, arg2] => {
                match (is_register(arg1), is_register(arg2)) {
                    (true, true) => Opcode::MOV_r { r1: parse_register(arg1), r2: parse_register(arg2) },
                    (true, false) => Opcode::MOV_v { r1: parse_register(arg1), v1: parse_value(arg2) },
                    _ => panic!("not valid arguments `{}, {}` for MOV", arg1, arg2)
                }
            }
            // сравнение
            &["cmp", arg1, arg2] => {
                match (is_register(arg1), is_register(arg2)) {
                    (true, true) => Opcode::CMP_r { r1: parse_register(arg1), r2: parse_register(arg2) },
                    (true, false) => Opcode::CMP_v { r1: parse_register(arg1), v1: parse_value(arg2) },
                    _ => panic!("not valid arguments `{}, {}` for CMP", arg1, arg2)
                }
            }
            // печать
            &["print", arg1] => {
                if is_register(arg1) {
                    Opcode::PRINT { r1: parse_register(arg1) }
                } else {
                    panic!("not valid argument `{}` for PRINT", arg1);
                }
            }
            // при любых других пишем о ошибке
            value => {
                panic!("unknown cmd `{:?}`", value)
            }
        };
        // добавляем распарсенную команду
        self.app.push(cmd);
    }
}

Вот и всё, наш интерпретатор готов, теперь можно перейти к тестам!

Тесты

На моей машине с процессором i5-8265U примеры выполняются за следующее время:

rust: 176ms
python: 9.83s
vm_asm: 2.80s

В идеале нужно было произвести как минимум запусков по 10 для каждого примера и взять среднее, но это же не исследовательская работа!

Мы здесь чисто по фану собрались, а те кто хочет всегда смогут сами его провести.

Заключение

Вот так просто и незатейливо можно написать самую простой регистровый интерпретатор кода.

Весь исходный код доступен по ссылке

На этом сегодня всё, увидимся ещё через пару лет!