Декодирование инструкций
открытый урокЭтот раздел читается без входа. Войди, чтобы отмечать прогресс, вести заметки и решать задачи в редакторе. войти
Декодирование инструкций
У процессора есть состояние и шина из прошлого урока. Осталось наполнить середину цикла: превратить 16 бит, прочитанных по
PC, в структурированную инструкцию (decode) и выполнить её, посчитав арифметику и флаги (execute). Это два самых «битовых» урока блока, и они прямо опираются на то, что ты разбирал про дополнительный код.
Декодер: биты в структуру
Декодирование это разбор слова на поля. Старшие 4 бита дают опкод, по опкоду мы знаем формат, а из формата вытаскиваем нужные поля. Заведём маленькие функции-извлекатели, по одной на поле, чтобы декодер читался как таблица.
/// Достаёт поле регистра rd (биты 11..9).
const fn rd(word: u16) -> Reg { Reg::new((word >> 9) as u8) }
/// Поле rs1 (биты 8..6).
const fn rs1(word: u16) -> Reg { Reg::new((word >> 6) as u8) }
/// Поле rs2 (биты 5..3).
const fn rs2(word: u16) -> Reg { Reg::new((word >> 3) as u8) }
/// imm6 (биты 5..0), знаковое.
const fn imm6(word: u16) -> i16 { sign_extend(word & 0x3F, 6) }
/// imm8 (биты 7..0), беззнаковое.
const fn imm8(word: u16) -> u8 { (word & 0xFF) as u8 }
/// imm9 (биты 8..0), знаковое.
const fn imm9(word: u16) -> i16 { sign_extend(word & 0x1FF, 9) }Знаковое расширение делается парой сдвигов: загнать знаковый бит на место 15, потом сдвинуть обратно вправо со знаком (в Rust сдвиг вправо у знакового типа арифметический).
pub const fn sign_extend(value: u16, bits: u32) -> i16 {
let shift = 16 - bits;
((value << shift) as i16) >> shift
}Опкод ALU несёт в младших трёх битах поле funct, которое выбирает одну из восьми операций. Декодеру нужно превратить эти три бита в AluOp, поэтому добавим к перечислению из урока 36 обратный конструктор. Он зеркалит таблицу funct и тоже тотальный: маска & 0x7 оставляет ровно восемь значений.
impl AluOp {
pub const fn from_funct(funct: u8) -> Self {
match funct & 0x7 {
0 => AluOp::Add,
1 => AluOp::Sub,
2 => AluOp::And,
3 => AluOp::Or,
4 => AluOp::Xor,
5 => AluOp::Shl,
6 => AluOp::Shr,
_ => AluOp::Sar,
}
}
pub const fn funct(self) -> u8 {
self as u8
}
}funct это обратная сторона: она нужна кодировщику encode из урока 36, чтобы AluOp::Sub снова стал тройкой бит. Пара from_funct/funct держит круговой проход (биты в инструкцию, инструкция в биты) честным.
Сам декодер это один match по опкоду. Он тотальный: все 16 опкодов заняты, незанятых битовых комбинаций нет, поэтому функция не возвращает ошибку и не имеет ветки «неизвестная инструкция». Замыкающая ветка _ нужна лишь формально: опкод хранится в u8, и компилятор требует разобрать все байтовые значения, хотя на деле их только 16.
/// Декодирует одно слово инструкции в структурированную форму.
pub fn decode(word: u16) -> Instr {
let op = (word >> 12) as u8;
match op {
opcode::ALU => Instr::Alu {
op: AluOp::from_funct((word & 0x7) as u8),
rd: rd(word),
rs1: rs1(word),
rs2: rs2(word),
},
opcode::ADDI => Instr::Addi {
rd: rd(word),
rs1: rs1(word),
imm: imm6(word),
},
opcode::LUI => Instr::Lui {
rd: rd(word),
imm: imm8(word),
},
opcode::LLI => Instr::Lli {
rd: rd(word),
imm: imm8(word),
},
opcode::LW => Instr::Lw {
rd: rd(word),
base: rs1(word),
off: imm6(word),
},
opcode::SW => Instr::Sw {
src: rd(word),
base: rs1(word),
off: imm6(word),
},
opcode::LB => Instr::Lb {
rd: rd(word),
base: rs1(word),
off: imm6(word),
},
opcode::SB => Instr::Sb {
src: rd(word),
base: rs1(word),
off: imm6(word),
},
opcode::BEQ => Instr::Beq {
a: rd(word),
b: rs1(word),
off: imm6(word),
},
opcode::BNE => Instr::Bne {
a: rd(word),
b: rs1(word),
off: imm6(word),
},
opcode::BLT => Instr::Blt {
a: rd(word),
b: rs1(word),
off: imm6(word),
},
opcode::BGE => Instr::Bge {
a: rd(word),
b: rs1(word),
off: imm6(word),
},
opcode::JAL => Instr::Jal {
rd: rd(word),
off: imm9(word),
},
opcode::JALR => Instr::Jalr {
rd: rd(word),
base: rs1(word),
off: imm6(word),
},
opcode::ORI => Instr::Ori {
rd: rd(word),
rs1: rs1(word),
imm: word & 0x3F,
},
// Единственный оставшийся опкод, маска 0xF выше его и ловит. Поэтому
// ветка не `unreachable!`, а реальный разбор: декодер тотальный.
_ => Instr::Sys {
code: word & 0x1FF,
},
}
}Шестнадцать опкодов, шестнадцать веток, и ни одной лишней. Заметь, что замыкающая ветка _ это не «неизвестная инструкция», а честный разбор SYS: все 16 значений опкода заняты, поэтому она ловит ровно 0xF и ничего больше. Декодер не возвращает Result, потому что декодировать нечего: любая 16-битная комбинация это валидная инструкция. Так бывает не у всякой ISA, и это сознательное свойство bcpu из урока 36.
В виджете ниже выбери слово из галереи и смотри, как оно раскладывается на поля: опкод определяет формат, поля окрашены, а движок дизассемблирует слово в мнемонику. Это буквально то, что делает decode, только показанное по битам.
Режимы адресации это и есть форматы
Декодер незаметно реализует все четыре режима адресации из урока 36. Регистровый режим это формат R (операнды из rs1, rs2). Непосредственный это imm6/imm8 в форматах I и U. База со смещением это rs1 + imm6 в LW/SW. Относительный к PC это знаковое смещение в ветвлениях и JAL. Формат инструкции и режим адресации это две стороны одной монеты: выбрав четыре формата, мы тем самым выбрали четыре режима, и декодер от этого остался крошечным.
ALU: арифметика на битах
Вторая половина урока это исполнение, и его сердце это ALU. У нас это чистая функция: получает операцию и два операнда, возвращает результат и флаги. Никакого состояния, поэтому ALU легко тестировать и переиспользовать (его же зовёт виджет в браузере).
/// Результат ALU: значение плюс флаги, которые оно породило.
pub struct AluResult {
pub value: u16,
pub flags: Flags,
}
pub fn alu(op: AluOp, a: u16, b: u16) -> AluResult {
match op {
AluOp::Add => add(a, b),
AluOp::Sub => sub(a, b),
AluOp::And => logic(a & b),
AluOp::Or => logic(a | b),
AluOp::Xor => logic(a ^ b),
AluOp::Shl => shl(a, b),
AluOp::Shr => shr(a, b),
AluOp::Sar => sar(a, b),
}
}Самое тонкое тут это флаги сложения и вычитания. Перенос C Rust отдаёт прямо из overflowing_add. А знаковое переполнение V ловится классическим трюком: оно случается, когда знаки операндов совпали, а знак результата вдруг другой.
fn add(a: u16, b: u16) -> AluResult {
let (value, carry) = a.overflowing_add(b);
let mut flags = Flags::new();
flags.set_zn(value); // Z и N выводятся прямо из результата
flags.carry = carry;
// Знаковое переполнение: знаки a и b совпали, а знак результата другой.
flags.overflow = ((a ^ value) & (b ^ value) & 0x8000) != 0;
AluResult { value, flags }
}
fn sub(a: u16, b: u16) -> AluResult {
let (value, borrow) = a.overflowing_sub(b);
let mut flags = Flags::new();
flags.set_zn(value);
// C=1 значит заёма не было, то есть a >= b без знака.
flags.carry = !borrow;
flags.overflow = ((a ^ b) & (a ^ value) & 0x8000) != 0;
AluResult { value, flags }
}
fn logic(value: u16) -> AluResult {
let mut flags = Flags::new();
flags.set_zn(value); // логические операции перенос и переполнение обнуляют
AluResult { value, flags }
}Остаются три сдвига. Величину сдвига берём по модулю 16 (b & 0xF), чтобы не выйти за разрядность слова. В C для сдвигов кладём последний выдвинутый бит: при сдвиге влево это бит, ушедший за старший разряд, при сдвиге вправо это последний ушедший младший. Логический сдвиг вправо (SHR) затягивает нули, арифметический (SAR) тянет знаковый бит, поэтому SAR мы делаем через i16.
fn shl(a: u16, b: u16) -> AluResult {
let amount = (b & 0xF) as u32;
let value = a.wrapping_shl(amount);
let mut flags = Flags::new();
flags.set_zn(value);
// Последний выдвинутый слева бит.
flags.carry = amount != 0 && (a >> (16 - amount)) & 1 != 0;
AluResult { value, flags }
}
fn shr(a: u16, b: u16) -> AluResult {
let amount = (b & 0xF) as u32;
let value = a.wrapping_shr(amount);
let mut flags = Flags::new();
flags.set_zn(value);
flags.carry = amount != 0 && (a >> (amount - 1)) & 1 != 0;
AluResult { value, flags }
}
fn sar(a: u16, b: u16) -> AluResult {
let amount = (b & 0xF) as u32;
let value = ((a as i16).wrapping_shr(amount)) as u16;
let mut flags = Flags::new();
flags.set_zn(value);
flags.carry = amount != 0 && (a >> (amount - 1)) & 1 != 0;
AluResult { value, flags }
}Это весь alu.rs: чистая функция и восемь её случаев. У него нет состояния, нет шины, нет процессора, поэтому его тривиально проверить таблицей «вход, ожидаемый результат, ожидаемые флаги», и тот же alu без изменений зовёт виджет в браузере.
Возьми в виджете панель ALU и проверь это руками. Сложи 0xFFFF и 1: результат 0x0000, поднимутся Z (ноль) и C (перенос за разряд). Вычти из 5 восьмёрку: результат отрицательный, поднимется N, а C погаснет (был заём). Это ровно те правила, что записаны выше.
Один шаг процессора
Декодер даёт Instr, ALU считает арифметику. Осталось связать их в цикл: прочитать слово по PC, декодировать, исполнить, продвинуть время. Это и есть step, сердце эмулятора. Допишем cpu.rs из прошлого урока.
Сначала опишем, чем может закончиться один шаг и весь прогон, а заодно заведём коды системного вызова SYS и базу таблицы векторов прерываний (она пригодится в уроке 39, но пусть константа уже лежит на месте).
/// Системные подфункции инструкции `SYS`, код в поле `imm9`.
pub mod sys {
/// Остановить процессор.
pub const HALT: u16 = 0;
/// Вернуться из обработчика прерывания (урок 39).
pub const RETI: u16 = 1;
/// Разрешить прерывания.
pub const EI: u16 = 2;
/// Запретить прерывания.
pub const DI: u16 = 3;
}
/// База таблицы векторов прерываний (урок 39).
pub const IVT_BASE: u16 = 0xFFE0;
/// Результат одного шага процессора.
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum Step {
/// Инструкция исполнена за `cycles` тактов.
Executed { instr: Instr, cycles: u32 },
/// Сработало прерывание: ушли в обработчик по вектору (урок 39).
Interrupt { vector: u8, cycles: u32 },
/// `SYS HALT`: процессор остановлен с кодом `code`.
Halted { code: u16 },
}
/// Чем закончился прогон [`Cpu::run`].
#[derive(Clone, Copy, PartialEq, Eq, Debug)]
pub enum RunOutcome {
/// Процессор остановился сам (`SYS HALT`).
Halted { code: u16 },
/// Исчерпан бюджет шагов, процессор всё ещё работает.
BudgetExhausted,
}Теперь сам шаг. Он читает слово по PC, сдвигает PC на +2 (адрес следующей инструкции, относительно которого считаются ветвления), исполняет инструкцию, узнаёт её стоимость в тактах и продвигает на эту стоимость периферию через bus.tick. Цикл run гоняет шаги, пока процессор не остановится сам или не выйдет бюджет.
impl Cpu {
/// Один шаг: выбрать, декодировать и исполнить одну инструкцию, затем
/// тикнуть периферию на её стоимость. Проверку прерываний добавим в уроке 39.
pub fn step(&mut self, bus: &mut impl Bus) -> Step {
if self.halted {
return Step::Halted { code: 0 };
}
let word = bus.read16(self.pc);
let instr = decode(word);
self.pc = self.pc.wrapping_add(2);
let step = self.execute(bus, instr);
let cost = match step {
Step::Executed { cycles, .. } => cycles,
Step::Halted { .. } => 1,
Step::Interrupt { cycles, .. } => cycles,
};
self.cycles += cost as u64;
bus.tick(cost);
step
}
/// Гоняет процессор не более `max_steps` шагов или до остановки.
pub fn run(&mut self, bus: &mut impl Bus, max_steps: u64) -> RunOutcome {
for _ in 0..max_steps {
if let Step::Halted { code } = self.step(bus) {
return RunOutcome::Halted { code };
}
}
RunOutcome::BudgetExhausted
}
}step берёт bus: &mut impl Bus: процессор обобщён по шине из урока 37 и одинаково работает поверх Ram и поверх будущей шины с периферией. Вот ради чего шина была трейтом.
Исполнитель: один match на всю систему команд
execute это диспетчер по декодированной инструкции. Каждая ветка делает ровно то, что записано в таблице опкодов: считает через alu, пишет регистр через set_reg, ходит в память через шину, двигает PC. Ветки, которые стоят дороже одного такта (память, переходы), возвращают Step::Executed со своей ценой через return; всё остальное проваливается в общий хвост со стоимостью 1.
impl Cpu {
fn execute(&mut self, bus: &mut impl Bus, instr: Instr) -> Step {
match instr {
Instr::Alu { op, rd, rs1, rs2 } => {
let result = alu(op, self.reg(rs1), self.reg(rs2));
self.set_reg(rd, result.value);
self.flags = result.flags;
}
Instr::Addi { rd, rs1, imm } => {
let result = alu(AluOp::Add, self.reg(rs1), imm as u16);
self.set_reg(rd, result.value);
self.flags = result.flags;
}
Instr::Lui { rd, imm } => {
self.set_reg(rd, (imm as u16) << 8);
}
Instr::Lli { rd, imm } => {
let kept = self.reg(rd) & 0xFF00;
self.set_reg(rd, kept | imm as u16);
}
Instr::Ori { rd, rs1, imm } => {
self.set_reg(rd, self.reg(rs1) | imm);
}
Instr::Lw { rd, base, off } => {
let addr = self.reg(base).wrapping_add(off as u16);
let value = bus.read16(addr);
self.set_reg(rd, value);
return Step::Executed { instr, cycles: 3 };
}
Instr::Sw { src, base, off } => {
let addr = self.reg(base).wrapping_add(off as u16);
bus.write16(addr, self.reg(src));
return Step::Executed { instr, cycles: 3 };
}
Instr::Lb { rd, base, off } => {
let addr = self.reg(base).wrapping_add(off as u16);
self.set_reg(rd, bus.read8(addr) as u16);
return Step::Executed { instr, cycles: 3 };
}
Instr::Sb { src, base, off } => {
let addr = self.reg(base).wrapping_add(off as u16);
bus.write8(addr, (self.reg(src) & 0xFF) as u8);
return Step::Executed { instr, cycles: 3 };
}
Instr::Beq { a, b, off } => {
return self.branch(instr, self.reg(a) == self.reg(b), off);
}
Instr::Bne { a, b, off } => {
return self.branch(instr, self.reg(a) != self.reg(b), off);
}
Instr::Blt { a, b, off } => {
let lt = (self.reg(a) as i16) < (self.reg(b) as i16);
return self.branch(instr, lt, off);
}
Instr::Bge { a, b, off } => {
let ge = (self.reg(a) as i16) >= (self.reg(b) as i16);
return self.branch(instr, ge, off);
}
Instr::Jal { rd, off } => {
self.set_reg(rd, self.pc);
self.pc = self.pc.wrapping_add((off as u16) << 1);
return Step::Executed { instr, cycles: 2 };
}
Instr::Jalr { rd, base, off } => {
let target = self.reg(base).wrapping_add(off as u16) & 0xFFFE;
self.set_reg(rd, self.pc);
self.pc = target;
return Step::Executed { instr, cycles: 2 };
}
Instr::Sys { code } => return self.system(bus, instr, code),
}
Step::Executed { instr, cycles: 1 }
}
}Несколько мест стоит проговорить. ADDI это то же сложение, что и ALU::Add, только второй операнд это знаково-расширенное imm: imm as u16 сохраняет его битовый узор, а сложение по модулю 2^16 само разберётся со знаком. LUI кладёт байт в старшую половину, LLI подменяет младшую, не трогая старшую (& 0xFF00); вдвоём они грузят произвольное 16-битное число (псевдоинструкция LI). Смещение ветвления и JAL сдвинуто на 1 (<< 1), потому что в единицах инструкций, а инструкции по 2 байта. У JALR адрес перехода обнуляется по младшему биту (& 0xFFFE), чтобы PC остался чётным.
branch это общий помощник для всех четырёх ветвлений: взяли переход, заплатили 2 такта и сдвинули PC, не взяли, заплатили 1 и пошли дальше.
impl Cpu {
fn branch(&mut self, instr: Instr, taken: bool, off: i16) -> Step {
if taken {
self.pc = self.pc.wrapping_add((off as u16) << 1);
Step::Executed { instr, cycles: 2 }
} else {
Step::Executed { instr, cycles: 1 }
}
}
}Остался SYS. HALT это наш единственный по-настоящему рабочий код в этом уроке: он останавливает процессор. Коды EI, DI, RETI управляют прерываниями, их роль раскроется в уроке 39, но раз мы пишем исполнитель SYS целиком, заложим их сразу. RETI снимает со стека флаги и PC теми же pop16/push16, что мы написали в прошлом уроке.
impl Cpu {
fn system(&mut self, bus: &mut impl Bus, instr: Instr, code: u16) -> Step {
match code {
sys::HALT => {
self.halted = true;
Step::Halted { code }
}
sys::RETI => {
let flags = self.pop16(bus);
self.pc = self.pop16(bus);
self.flags = unpack_flags(flags);
self.interrupts_enabled = true;
Step::Executed { instr, cycles: 3 }
}
sys::EI => {
self.interrupts_enabled = true;
Step::Executed { instr, cycles: 1 }
}
sys::DI => {
self.interrupts_enabled = false;
Step::Executed { instr, cycles: 1 }
}
_ => Step::Executed { instr, cycles: 1 },
}
}
}И две свободные функции, которые упаковывают флаги в слово и обратно: они нужны RETI сейчас и прерываниям в уроке 39, когда флаги придётся сохранять на стек.
/// Упаковывает флаги в слово: бит 0 Z, 1 N, 2 C, 3 V.
pub fn pack_flags(f: Flags) -> u16 {
(f.zero as u16) | (f.negative as u16) << 1 | (f.carry as u16) << 2 | (f.overflow as u16) << 3
}
/// Обратная распаковка.
pub fn unpack_flags(word: u16) -> Flags {
Flags {
zero: word & 1 != 0,
negative: word & 2 != 0,
carry: word & 4 != 0,
overflow: word & 8 != 0,
}
}Теперь cpu.rs исполняет любую программу без прерываний целиком: собери в памяти слова, вызови reset(0), потом run(&mut bus, 10_000), и процессор прогонит её до HALT. Чего не хватает, это проверки прерываний перед выборкой и входа в обработчик: их добавим в step в уроке 39, когда на шину встанет периферия, которая умеет их поднимать.
Развилка дизайна и её цена
Мысль урока про устройство: диспетчеризация это выбор между читаемостью и скоростью.
Мы декодируем и исполняем через match по опкоду. Это диспетчеризация через сопоставление с образцом: читается как таблица опкодов, проверяется компилятором на полноту, легко добавить инструкцию. Альтернатива это таблица указателей на функции-обработчики, по одной на опкод: иногда чуть быстрее (один индексный переход вместо ветвлений) и гибче, если опкоды надо подменять на лету. Цена таблицы это потеря читаемости и проверки полноты: легко забыть заполнить ячейку, и компилятор не подскажет.
Для интерпретатора с шестнадцатью опкодами match это правильный выбор: компилятор сам соберёт из него таблицу переходов, когда сочтёт нужным, а мы получаем код, который читается как спецификация. Таблицу указателей берут, когда опкодов сотни или когда их набор меняется во время работы. Мы будем называть эту цену вслух и дальше: в следующем уроке к шине подключится периферия, и встанет вопрос, когда её тикать.