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

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

И сегодня в программе: регистровая виртуальную машину на языке 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 элементов.

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

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

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

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

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

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

Алгоритм:

  1. установить значение start_value в 0
  2. цикл пока 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

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

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

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

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

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

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

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

У нас будет:

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

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

здесь #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 примеры выполняются за следующее время:

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

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

Заключение

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

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

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

Полезные ссылки

  1. Пишем собственную виртуальную машину
  2. Интерпретаторы байт-кодов своими руками
  3. Стековые и регистровые машины
  4. Гипотеза Коллатца
  5. Регистр флагов
Назад