rv32-rs/src/lib.rs
src/lib.rsRaw
1//! Implementation of the RV32I ISA. Each opcode has a comment explaining it.
2use anyhow::{anyhow, Result};
3
4pub struct RV32 {
5 regs: [u32; 32], // registers
6 mem: Vec<u8>, // memory
7 pc: u32,
8}
9
10impl RV32 {
11 pub fn new(mem: Vec<u8>) -> Self {
12 Self {
13 regs: [0; 32],
14 pc: 0,
15 mem,
16 }
17 }
18 pub fn set_register(&mut self, index: usize, value: u32) {
19 assert!(index < 32, "register index must <32");
20 if index != 0 {
21 self.regs[index] = value;
22 }
23 }
24 // validate the access
25 fn range(&self, address: u32, size: usize) -> Result<std::ops::Range<usize>> {
26 if !address.is_multiple_of(size as u32) {
27 return Err(anyhow!("misaligned at address: {}", address));
28 }
29 let start = address as usize;
30 let end = start
31 .checked_add(size)
32 .filter(|&end| end <= self.mem.len())
33 .ok_or(anyhow!("access fault, address: {}", address))?;
34 Ok(start..end)
35 }
36 fn read(&self, address: u32, size: usize) -> Result<u32> {
37 let range = self.range(address, size)?;
38 let mut bytes = [0; 4];
39 bytes[..size].copy_from_slice(&self.mem[range]);
40 Ok(u32::from_le_bytes(bytes))
41 }
42 pub fn step(&mut self) -> Result<()> {
43 let instruction = self.read(self.pc, 4)?;
44 let next_pc = self.pc.wrapping_add(4);
45
46 // R-type instruction:
47 // R-type:
48 // 31 25 24 20 19 15 14 12 11 7 6 0
49 // ┌───────────┬────────────┬────────────┬────────┬────────┬─────────┐
50 // │ funct7 │ rs2 │ rs1 │ funct3 │ rd │ opcode │
51 // └───────────┴────────────┴────────────┴────────┴────────┴─────────┘
52 let rd = ((instruction >> 7) & 31) as usize;
53 let funct3 = (instruction >> 12) & 7;
54 let rs1 = ((instruction >> 15) & 31) as usize;
55 let rs2 = ((instruction >> 20) & 31) as usize;
56 let funct7 = instruction >> 25;
57 // I-type:
58 // 31 20 19 15 14 12 11 7 6 0
59 // ┌────────────────────────┬────────────┬────────┬────────┬─────────┐
60 // │ imm[11:0] │ rs1 │ funct3 │ rd │ opcode │
61 // └────────────────────────┴────────────┴────────┴────────┴─────────┘
62 // S-type:
63 // 31 25 24 20 19 15 14 12 11 7 6 0
64 // ┌───────────┬────────────┬────────────┬────────┬───────────┬─────────┐
65 // │ imm[11:5] │ rs2 │ rs1 │ funct3 │ imm[4:0] │ opcode │
66 // └───────────┴────────────┴────────────┴────────┴───────────┴─────────┘
67 //
68 // Note: we keep `imm` as the I-type imm, and in the S-type we compute
69 // the S-type respective imm from 25-31 and 7-11 positions
70 let imm = sign_extend(instruction >> 20, 12);
71
72 let a = self.regs[rs1];
73 let b = self.regs[rs2];
74 let mut result: Option<u32> = None;
75
76 // 0x7f=0111_1111, match the lowest 7 bits to read the opcode
77 match instruction & 0x7f {
78 // I-type op'ns:
79 // Loads
80 0x03 => {
81 let (size, signed) = match funct3 {
82 // LB: load a byte at rs1 + immediate and sign-extend it into rd
83 0 => (1, true),
84 // LH: load a halfword at rs1 + immediate and sign-extend it into rd
85 1 => (2, true),
86 // LW: load a 32-bit word at rs1 + immediate into rd
87 2 => (4, false),
88 // LBU: load a byte at rs1 + immediate and zero-extend it into rd
89 4 => (1, false),
90 // LHU: load a halfword at rs1 + immediate and zero-extend it into rd
91 5 => (2, false),
92 _ => return Err(anyhow!("illegal instruction: {}", instruction)),
93 };
94 let value = self.read(a.wrapping_add(imm), size)?;
95 result = Some(if signed {
96 sign_extend(value, size as u32 * 8)
97 } else {
98 value
99 });
100 }
101 // S-type op'ns:
102 0x23 => {
103 let size = match funct3 {
104 // SB: store the low byte of rs2 at rs1 + immediate
105 0 => 1,
106 // SH: store the low halfword of rs2 at rs1 + immediate
107 1 => 2,
108 // SW: store the full 32-bit value of rs2 at rs1 + immediate
109 2 => 4,
110 _ => return Err(anyhow!("illegal instruction: {}", instruction)),
111 };
112 // for the S-type imm, get it from 25-31 and 7-11 positions
113 let s_type_imm = ((instruction >> 25) << 5) | ((instruction >> 7) & 31);
114 let offset = sign_extend(s_type_imm, 12);
115 let range = self.range(a.wrapping_add(offset), size)?;
116 self.mem[range].copy_from_slice(&b.to_le_bytes()[..size]);
117 }
118
119 // R-type (register-register) integer operations
120 0x33 => {
121 result = Some(match (funct7, funct3) {
122 // ADD: add rs1 and rs2, wrapping to 32 bits
123 (0, 0) => a.wrapping_add(b),
124 // SUB: subtract rs2 from rs1, wrapping to 32 bits
125 (0x20, 0) => a.wrapping_sub(b),
126 // SLL: shift rs1 left by the low five bits of rs2
127 (0, 1) => a << (b & 31),
128 // SLT: set rd to one if rs1 is less than rs2 as signed
129 // values, else zero
130 (0, 2) => u32::from((a as i32) < (b as i32)),
131 // SLTU: set rd to one if rs1 is less than rs2 as unsigned
132 // values, else zero
133 (0, 3) => u32::from(a < b),
134 // XOR: write the bitwise XOR of rs1 and rs2 into rd
135 (0, 4) => a ^ b,
136 // SRL: shift rs1 right by the low five bits of rs2, filling
137 // with zeros
138 (0, 5) => a >> (b & 31),
139 // SRA: shift rs1 right by the low five bits of rs2,
140 // preserving its sign
141 (0x20, 5) => ((a as i32) >> (b & 31)) as u32,
142 // OR: write the bitwise OR of rs1 and rs2 into rd
143 (0, 6) => a | b,
144 // AND: write the bitwise AND of rs1 and rs2 into rd
145 (0, 7) => a & b,
146
147 // Note: MUL,DIV,REM are not part of RV32I, but they are in
148 // the M extension.
149
150 // MUL: write the low 32 bits of the product of rs1 and rs2
151 (1, 0) => a.wrapping_mul(b),
152 // DIV: signed quotient toward zero; zero divisors return
153 // all ones
154 (1, 4) => {
155 if b == 0 {
156 u32::MAX
157 } else {
158 (a as i32).wrapping_div(b as i32) as u32
159 }
160 }
161 // REM: signed remainder; zero divisors return the dividend
162 (1, 6) => {
163 if b == 0 {
164 a
165 } else {
166 (a as i32).wrapping_rem(b as i32) as u32
167 }
168 }
169
170 _ => return Err(anyhow!("illegal instruction (A): {}", instruction)),
171 });
172 }
173 _ => return Err(anyhow!("illegal instruction (B): {}", instruction)),
174 }
175
176 if next_pc & 3 != 0 {
177 return Err(anyhow!("misaligned, address: {}", next_pc,));
178 }
179 if let Some(value) = result {
180 self.set_register(rd, value);
181 }
182 self.pc = next_pc;
183 Ok(())
184 }
185}
186
187// sign-extend a smaller signed number to 32 bits
188fn sign_extend(value: u32, bits: u32) -> u32 {
189 ((value << (32 - bits)) as i32 >> (32 - bits)) as u32
190}
191
192#[cfg(test)]
193mod tests {
194 use super::*;
195
196 const OPCODE_R: u32 = 0b0110011;
197 const OPCODE_LOAD: u32 = 0b0000011;
198
199 // encodes R-type instruction
200 fn encode_r(name: &str, rd: u32, rs1: u32, rs2: u32) -> u32 {
201 let (funct7, funct3) = match name {
202 "add" => (0b0000000, 0b000),
203 "sub" => (0b0100000, 0b000),
204 "sll" => (0b0000000, 0b001),
205 "slt" => (0b0000000, 0b010),
206 "sltu" => (0b0000000, 0b011),
207 "xor" => (0b0000000, 0b100),
208 "srl" => (0b0000000, 0b101),
209 "sra" => (0b0100000, 0b101),
210 "or" => (0b0000000, 0b110),
211 "and" => (0b0000000, 0b111),
212 // M extension
213 "mul" => (0b0000001, 0b000),
214 "div" => (0b0000001, 0b100),
215 "rem" => (0b0000001, 0b110),
216 _ => panic!("unknown R-type instruction: {name}"),
217 };
218
219 (funct7 << 25) | (rs2 << 20) | (rs1 << 15) | (funct3 << 12) | (rd << 7) | OPCODE_R
220 }
221 fn encode_i(name: &str, rd: u32, rs1: u32, imm: i32) -> u32 {
222 let funct3 = match name {
223 "lb" => 0b000,
224 "lh" => 0b001,
225 "lw" => 0b010,
226 "lbu" => 0b100,
227 "lhu" => 0b101,
228 _ => panic!("unknown load instruction: {name}"),
229 };
230
231 let imm = (imm as u32) & 0xfff;
232
233 (imm << 20) | (rs1 << 15) | (funct3 << 12) | (rd << 7) | OPCODE_LOAD
234 }
235 fn encode_s(name: &str, rs1: u32, rs2: u32, imm: i32) -> u32 {
236 let (opcode, funct3) = match name {
237 "sb" => (0b0100011, 0b000),
238 "sh" => (0b0100011, 0b001),
239 "sw" => (0b0100011, 0b010),
240 _ => panic!("unknown store instruction: {name}"),
241 };
242
243 let imm = imm as u32;
244
245 let imm_11_5 = (imm >> 5) & 0x7f;
246 let imm_4_0 = imm & 0x1f;
247
248 (imm_11_5 << 25) | (rs2 << 20) | (rs1 << 15) | (funct3 << 12) | (imm_4_0 << 7) | opcode
249 }
250
251 #[test]
252 fn test_ops_r_type() {
253 let test_vectors = vec![
254 // (op, rs1, rs2, rd)
255 ("add", 10, 20, 30),
256 ("add", u32::MAX, 1, 0), // overflow
257 ("sub", 30, 20, 10),
258 ("sub", 0, 1, u32::MAX), // overflow
259 ("sll", 1, 4, 16),
260 ("sll", 1, 31, 0x8000_0000), // SLL maximum shift
261 ("sll", 1, 32, 1), // SLL shift wrapping
262 ("slt", (-10i32) as u32, 20, 1),
263 ("sltu", 10, 20, 1),
264 ("slt", 0xffff_ffff, 0, 1), // signed comparison: -1 < 0
265 ("slt", 0xffff_ffff, 0, 1), // signed vs unsigned distinction
266 ("sltu", 0xffff_ffff, 0, 0),
267 ("xor", 0b1010, 0b1100, 0b0110),
268 ("srl", 0x8000_0000, 4, 0x0800_0000),
269 ("srl", 0x8000_0000, 1, 0x4000_0000), // logical shift should zero-fill
270 ("sra", 0x8000_0000, 4, 0xf800_0000),
271 ("sra", 0x8000_0000, 1, 0xc000_0000), // arithmetic shift should sign-fill
272 ("sra", 0xffff_ffff, 31, 0xffff_ffff), // arithmetic shift of -1 stays -1
273 ("or", 0b1010, 0b1100, 0b1110),
274 ("and", 0b1010, 0b1100, 0b1000),
275 ];
276 test_ops_r_types_opt(test_vectors);
277 }
278 #[test]
279 fn test_ops_m_extension() {
280 let test_vectors = vec![
281 ("mul", 10, 20, 200),
282 ("mul", 0, 123, 0),
283 ("mul", 1, u32::MAX, u32::MAX),
284 ("mul", u32::MAX, 2, u32::MAX - 1), // result wraps to lower 32 bits
285 ("mul", (-1i32) as u32, 10, (-10i32) as u32), // -1 * 10 = -10
286 ("mul", (-1i32) as u32, (-1i32) as u32, 1), // -1 * -1 = 1
287 ("mul", 0x8000_0000, 2, 0), // INT_MIN * 2 = 0 modulo 2^32
288 ("mul", 0x8000_0000, 0xffff_ffff, 0x8000_0000), // INT_MIN * -1 also wraps to INT_MIN
289 ("div", 20, 5, 4),
290 ("div", 21, 5, 4), // truncates toward zero
291 ("div", 0, 10, 0),
292 ("div", 10, 1, 10),
293 ("div", 10, (-1i32) as u32, (-10i32) as u32),
294 ("div", (-20i32) as u32, 5, (-4i32) as u32), // negative dividend
295 ("div", 20, (-5i32) as u32, (-4i32) as u32), // negative divisor
296 ("div", (-20i32) as u32, (-5i32) as u32, 4), // negative / negative
297 ("div", (-21i32) as u32, 5, (-4i32) as u32), // truncation toward zero: -21 / 5 = -4
298 // RISC-V special case:
299 ("div", 0x8000_0000, 0xffff_ffff, 0x8000_0000), // INT_MIN / -1 = INT_MIN (overflow)
300 ("div", 10, 0, u32::MAX), // division by zero returns -1 for signed DIV
301 ("div", 0x8000_0000, 0, u32::MAX),
302 ("rem", 20, 5, 0),
303 ("rem", 21, 5, 1),
304 ("rem", 0, 10, 0),
305 ("rem", 10, 1, 0),
306 ("rem", 23, 5, 3), // positive remainder
307 ("rem", (-23i32) as u32, 5, (-3i32) as u32), // remainder follows the sign of the dividend
308 ("rem", 23, (-5i32) as u32, 3), // negative divisor does not change the sign of the remainder
309 ("rem", (-23i32) as u32, (-5i32) as u32, (-3i32) as u32), // negative / negative
310 ("rem", 3, 5, 3), // dividend smaller than divisor
311 // RISC-V special case:
312 ("rem", 0x8000_0000, 0xffff_ffff, 0), // INT_MIN % -1 = 0.
313 ("rem", 123, 0, 123), // remainder by zero returns the dividend.
314 ("rem", u32::MAX, 0, u32::MAX),
315 ("rem", 0x8000_0000, 0, 0x8000_0000),
316 ];
317 test_ops_r_types_opt(test_vectors);
318 }
319 fn test_ops_r_types_opt(test_vectors: Vec<(&str, u32, u32, u32)>) {
320 for (name, rs1_value, rs2_value, expected) in test_vectors {
321 let rd = 3;
322 let rs1 = 1;
323 let rs2 = 2;
324
325 let instruction = encode_r(name, rd, rs1, rs2);
326
327 let mut cpu = RV32::new(instruction.to_le_bytes().to_vec());
328
329 cpu.regs[rs1 as usize] = rs1_value;
330 cpu.regs[rs2 as usize] = rs2_value;
331
332 cpu.step().unwrap();
333
334 assert_eq!(
335 cpu.regs[rd as usize], expected,
336 "{name} failed:
337 rs1={rs1_value:#010x}, rs2={rs2_value:#010x},
338 expected={expected:#010x}, got={:#010x}",
339 cpu.regs[rd as usize],
340 );
341 }
342 }
343
344 #[test]
345 fn test_ops_load() {
346 let test_vectors: Vec<(&str, u32, i32, u32)> = vec![
347 ("lb", 0x0000_0080, 0, 0xffff_ff80),
348 ("lbu", 0x0000_0080, 0, 0x0000_0080),
349 ("lb", 0x0000_00ff, 0, 0xffff_ffff),
350 ("lbu", 0x0000_00ff, 0, 0x0000_00ff),
351 ("lh", 0x0000_8000, 0, 0xffff_8000),
352 ("lhu", 0x0000_8000, 0, 0x0000_8000),
353 ("lh", 0x0000_ffff, 0, 0xffff_ffff),
354 ("lhu", 0x0000_ffff, 0, 0x0000_ffff),
355 ];
356
357 for (name, memory_value, address, expected) in test_vectors {
358 let rd = 1;
359 let rs1 = 2;
360
361 let instruction = encode_i(name, rd, rs1, address);
362
363 let mut memory = instruction.to_le_bytes().to_vec();
364 let data_address = memory.len() as u32;
365 memory.extend_from_slice(&memory_value.to_le_bytes());
366 let mut cpu = RV32::new(memory);
367
368 cpu.regs[rs1 as usize] = data_address;
369
370 cpu.step().unwrap();
371
372 assert_eq!(
373 cpu.regs[rd as usize], expected,
374 "{name} failed: memory={memory_value:#010x},
375 address={address}, \
376 expected={expected:#010x},
377 got={:#010x}",
378 cpu.regs[rd as usize],
379 );
380 }
381 }
382 #[test]
383 fn test_ops_store() {
384 let test_vectors: Vec<(&str, u32, i32)> = vec![
385 ("sb", 0x0000_0080, 0),
386 ("sb", 0x0000_00ff, 0),
387 ("sb", 0x1234_5678, 0),
388 ("sh", 0x0000_8000, 0),
389 ("sh", 0x0000_ffff, 0),
390 ("sw", 0x1234_5678, 0),
391 ];
392
393 for (name, value, address) in test_vectors {
394 let rs1 = 1;
395 let rs2 = 2;
396
397 let instruction = encode_s(name, rs1, rs2, address);
398
399 let mut memory = instruction.to_le_bytes().to_vec();
400 let data_address = memory.len() as u32;
401
402 // add space for the value being stored
403 memory.extend_from_slice(&[0u8; 4]);
404
405 let mut cpu = RV32::new(memory);
406
407 cpu.regs[rs1 as usize] = data_address;
408 cpu.regs[rs2 as usize] = value;
409
410 cpu.step().unwrap();
411
412 let stored = u32::from_le_bytes(
413 cpu.mem[data_address as usize..data_address as usize + 4]
414 .try_into()
415 .unwrap(),
416 );
417
418 let expected = match name {
419 "sb" => value & 0xff,
420 "sh" => value & 0xffff,
421 "sw" => value,
422 _ => unreachable!(),
423 };
424
425 assert_eq!(
426 stored, expected,
427 "{name} failed: value={value:#010x},
428 address={address}, \
429 expected={expected:#010x},
430 got={stored:#010x}",
431 );
432 }
433 }
434}