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 mut 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 // B-type:
68 // 31 30 25 24 20 19 15 14 12 11 8 7 6 0
69 // ┌─────┬─────────┬────────┬────────────┬────────┬────────┬──┬──────┐
70 // │imm12│imm[10:5]│ rs2 │ rs1 │ funct3 │imm[4:1]│11│opcode│
71 // └─────┴─────────┴────────┴────────────┴────────┴────────┴──┴──────┘
72 //
73 // Note: we keep `imm` as the I-type imm, and in the S-type we compute
74 // the S-type respective imm from 31-25 and 11-7 positions, and for
75 // B-type we obtain imm from the positions 31, 31-25, 11-8, 7, and
76 // imm[0]=0.
77 let imm = sign_extend(instruction >> 20, 12);
78
79 let a = self.regs[rs1];
80 let b = self.regs[rs2];
81 let mut result: Option<u32> = None;
82
83 // 0x7f=0111_1111, match the lowest 7 bits to read the opcode
84 match instruction & 0x7f {
85 // I-type op'ns:
86 // Loads
87 0x03 => {
88 let (size, signed) = match funct3 {
89 // LB: load a byte at rs1 + immediate and sign-extend it into rd
90 0 => (1, true),
91 // LH: load a halfword at rs1 + immediate and sign-extend it into rd
92 1 => (2, true),
93 // LW: load a 32-bit word at rs1 + immediate into rd
94 2 => (4, false),
95 // LBU: load a byte at rs1 + immediate and zero-extend it into rd
96 4 => (1, false),
97 // LHU: load a halfword at rs1 + immediate and zero-extend it into rd
98 5 => (2, false),
99 _ => return Err(anyhow!("illegal instruction in I-type: {}", instruction)),
100 };
101 let value = self.read(a.wrapping_add(imm), size)?;
102 result = Some(if signed {
103 sign_extend(value, size as u32 * 8)
104 } else {
105 value
106 });
107 }
108 // S-type op'ns:
109 0x23 => {
110 let size = match funct3 {
111 // SB: store the low byte of rs2 at rs1 + immediate
112 0 => 1,
113 // SH: store the low halfword of rs2 at rs1 + immediate
114 1 => 2,
115 // SW: store the full 32-bit value of rs2 at rs1 + immediate
116 2 => 4,
117 _ => return Err(anyhow!("illegal instruction in S-type: {}", instruction)),
118 };
119 // for the S-type imm, get it from 25-31 and 7-11 positions
120 let s_type_imm = ((instruction >> 25) << 5) | ((instruction >> 7) & 31);
121 let offset = sign_extend(s_type_imm, 12);
122 let range = self.range(a.wrapping_add(offset), size)?;
123 self.mem[range].copy_from_slice(&b.to_le_bytes()[..size]);
124 }
125
126 // R-type (register-register) integer operations
127 0x33 => {
128 result = Some(match (funct7, funct3) {
129 // ADD: add rs1 and rs2, wrapping to 32 bits
130 (0, 0) => a.wrapping_add(b),
131 // SUB: subtract rs2 from rs1, wrapping to 32 bits
132 (0x20, 0) => a.wrapping_sub(b),
133 // SLL: shift rs1 left by the low five bits of rs2
134 (0, 1) => a << (b & 31),
135 // SLT: set rd to one if rs1 is less than rs2 as signed
136 // values, else zero
137 (0, 2) => u32::from((a as i32) < (b as i32)),
138 // SLTU: set rd to one if rs1 is less than rs2 as unsigned
139 // values, else zero
140 (0, 3) => u32::from(a < b),
141 // XOR: write the bitwise XOR of rs1 and rs2 into rd
142 (0, 4) => a ^ b,
143 // SRL: shift rs1 right by the low five bits of rs2, filling
144 // with zeros
145 (0, 5) => a >> (b & 31),
146 // SRA: shift rs1 right by the low five bits of rs2,
147 // preserving its sign
148 (0x20, 5) => ((a as i32) >> (b & 31)) as u32,
149 // OR: write the bitwise OR of rs1 and rs2 into rd
150 (0, 6) => a | b,
151 // AND: write the bitwise AND of rs1 and rs2 into rd
152 (0, 7) => a & b,
153
154 // Note: MUL,DIV,REM are not part of RV32I, but they are in
155 // the M extension.
156
157 // MUL: write the low 32 bits of the product of rs1 and rs2
158 (1, 0) => a.wrapping_mul(b),
159 // DIV: signed quotient toward zero; zero divisors return
160 // all ones
161 (1, 4) => {
162 if b == 0 {
163 u32::MAX
164 } else {
165 (a as i32).wrapping_div(b as i32) as u32
166 }
167 }
168 // REM: signed remainder; zero divisors return the dividend
169 (1, 6) => {
170 if b == 0 {
171 a
172 } else {
173 (a as i32).wrapping_rem(b as i32) as u32
174 }
175 }
176
177 _ => return Err(anyhow!("illegal instruction in R-type: {}", instruction)),
178 });
179 }
180 // B-type operations
181 0x63 => {
182 let taken = match funct3 {
183 // BEQ: branch by the signed PC-relative offset if the registers are equal
184 0 => a == b,
185 // BNE: branch if the registers are unequal
186 1 => a != b,
187 // BLT: branch if rs1 is less than rs2 using signed comparison
188 4 => (a as i32) < (b as i32),
189 // BGE: branch if rs1 is at least rs2 using signed comparison
190 5 => (a as i32) >= (b as i32),
191 // BLTU: branch if rs1 is less than rs2 using unsigned comparison
192 6 => a < b,
193 // BGEU: branch if rs1 is at least rs2 using unsigned comparison
194 7 => a >= b,
195 _ => return Err(anyhow!("illegal instruction in B-type: {}", instruction)),
196 };
197 if taken {
198 // offset: reconstruct imm for B-type from positions 31, 31-25,
199 // 11-8, 7, and imm[0]=0
200 let b_type_imm = ((instruction >> 31) << 12)
201 | (((instruction >> 7) & 1) << 11)
202 | (((instruction >> 25) & 0x3f) << 5)
203 | (((instruction >> 8) & 15) << 1);
204 next_pc = self.pc.wrapping_add(sign_extend(b_type_imm, 13));
205 }
206 }
207
208 _ => return Err(anyhow!("illegal instruction: {}", instruction)),
209 }
210
211 if next_pc & 3 != 0 {
212 return Err(anyhow!("misaligned, address: {}", next_pc,));
213 }
214 if let Some(value) = result {
215 self.set_register(rd, value);
216 }
217 self.pc = next_pc;
218 Ok(())
219 }
220}
221
222// sign-extend a smaller signed number to 32 bits
223fn sign_extend(value: u32, bits: u32) -> u32 {
224 ((value << (32 - bits)) as i32 >> (32 - bits)) as u32
225}
226
227#[cfg(test)]
228mod tests {
229 use super::*;
230
231 const OPCODE_R: u32 = 0b0110011;
232 const OPCODE_LOAD: u32 = 0b0000011;
233
234 // encodes R-type instruction
235 fn encode_r(name: &str, rd: u32, rs1: u32, rs2: u32) -> u32 {
236 let (funct7, funct3) = match name {
237 "add" => (0b0000000, 0b000),
238 "sub" => (0b0100000, 0b000),
239 "sll" => (0b0000000, 0b001),
240 "slt" => (0b0000000, 0b010),
241 "sltu" => (0b0000000, 0b011),
242 "xor" => (0b0000000, 0b100),
243 "srl" => (0b0000000, 0b101),
244 "sra" => (0b0100000, 0b101),
245 "or" => (0b0000000, 0b110),
246 "and" => (0b0000000, 0b111),
247 // M extension
248 "mul" => (0b0000001, 0b000),
249 "div" => (0b0000001, 0b100),
250 "rem" => (0b0000001, 0b110),
251 _ => panic!("unknown R-type instruction: {name}"),
252 };
253
254 (funct7 << 25) | (rs2 << 20) | (rs1 << 15) | (funct3 << 12) | (rd << 7) | OPCODE_R
255 }
256 fn encode_i(name: &str, rd: u32, rs1: u32, imm: i32) -> u32 {
257 let funct3 = match name {
258 "lb" => 0b000,
259 "lh" => 0b001,
260 "lw" => 0b010,
261 "lbu" => 0b100,
262 "lhu" => 0b101,
263 _ => panic!("unknown load instruction: {name}"),
264 };
265
266 let imm = (imm as u32) & 0xfff;
267
268 (imm << 20) | (rs1 << 15) | (funct3 << 12) | (rd << 7) | OPCODE_LOAD
269 }
270 fn encode_s(name: &str, rs1: u32, rs2: u32, imm: i32) -> u32 {
271 let (opcode, funct3) = match name {
272 "sb" => (0b0100011, 0b000),
273 "sh" => (0b0100011, 0b001),
274 "sw" => (0b0100011, 0b010),
275 _ => panic!("unknown store instruction: {name}"),
276 };
277
278 let imm = imm as u32;
279
280 let imm_11_5 = (imm >> 5) & 0x7f;
281 let imm_4_0 = imm & 0x1f;
282
283 (imm_11_5 << 25) | (rs2 << 20) | (rs1 << 15) | (funct3 << 12) | (imm_4_0 << 7) | opcode
284 }
285 fn encode_b(name: &str, rs1: u32, rs2: u32, offset: i32) -> u32 {
286 let funct3 = match name {
287 "beq" => 0b000,
288 "bne" => 0b001,
289 "blt" => 0b100,
290 "bge" => 0b101,
291 "bltu" => 0b110,
292 "bgeu" => 0b111,
293 _ => panic!("unknown B-type instruction: {name}"),
294 };
295
296 assert!(
297 offset % 2 == 0,
298 "B-type branch offset must be 2-byte aligned"
299 );
300
301 assert!(
302 (-4096..=4094).contains(&offset),
303 "B-type branch offset out of range: {offset}"
304 );
305
306 let imm = offset as u32;
307
308 let imm12 = (imm >> 12) & 0x1;
309 let imm11 = (imm >> 11) & 0x1;
310 let imm10_5 = (imm >> 5) & 0x3f;
311 let imm4_1 = (imm >> 1) & 0xf;
312
313 (imm12 << 31)
314 | (imm10_5 << 25)
315 | (rs2 << 20)
316 | (rs1 << 15)
317 | (funct3 << 12)
318 | (imm4_1 << 8)
319 | (imm11 << 7)
320 | 0b1100011
321 }
322
323 // R-type ops test
324 #[test]
325 fn test_ops_r_type() {
326 let test_vectors = vec![
327 // (op, rs1, rs2, rd)
328 ("add", 10, 20, 30),
329 ("add", u32::MAX, 1, 0), // overflow
330 ("sub", 30, 20, 10),
331 ("sub", 0, 1, u32::MAX), // overflow
332 ("sll", 1, 4, 16),
333 ("sll", 1, 31, 0x8000_0000), // SLL maximum shift
334 ("sll", 1, 32, 1), // SLL shift wrapping
335 ("slt", (-10i32) as u32, 20, 1),
336 ("sltu", 10, 20, 1),
337 ("slt", 0xffff_ffff, 0, 1), // signed comparison: -1 < 0
338 ("slt", 0xffff_ffff, 0, 1), // signed vs unsigned distinction
339 ("sltu", 0xffff_ffff, 0, 0),
340 ("xor", 0b1010, 0b1100, 0b0110),
341 ("srl", 0x8000_0000, 4, 0x0800_0000),
342 ("srl", 0x8000_0000, 1, 0x4000_0000), // logical shift should zero-fill
343 ("sra", 0x8000_0000, 4, 0xf800_0000),
344 ("sra", 0x8000_0000, 1, 0xc000_0000), // arithmetic shift should sign-fill
345 ("sra", 0xffff_ffff, 31, 0xffff_ffff), // arithmetic shift of -1 stays -1
346 ("or", 0b1010, 0b1100, 0b1110),
347 ("and", 0b1010, 0b1100, 0b1000),
348 ];
349 test_ops_r_types_opt(test_vectors);
350 }
351 #[test]
352 fn test_ops_m_extension() {
353 let test_vectors = vec![
354 ("mul", 10, 20, 200),
355 ("mul", 0, 123, 0),
356 ("mul", 1, u32::MAX, u32::MAX),
357 ("mul", u32::MAX, 2, u32::MAX - 1), // result wraps to lower 32 bits
358 ("mul", (-1i32) as u32, 10, (-10i32) as u32), // -1 * 10 = -10
359 ("mul", (-1i32) as u32, (-1i32) as u32, 1), // -1 * -1 = 1
360 ("mul", 0x8000_0000, 2, 0), // INT_MIN * 2 = 0 modulo 2^32
361 ("mul", 0x8000_0000, 0xffff_ffff, 0x8000_0000), // INT_MIN * -1 also wraps to INT_MIN
362 ("div", 20, 5, 4),
363 ("div", 21, 5, 4), // truncates toward zero
364 ("div", 0, 10, 0),
365 ("div", 10, 1, 10),
366 ("div", 10, (-1i32) as u32, (-10i32) as u32),
367 ("div", (-20i32) as u32, 5, (-4i32) as u32), // negative dividend
368 ("div", 20, (-5i32) as u32, (-4i32) as u32), // negative divisor
369 ("div", (-20i32) as u32, (-5i32) as u32, 4), // negative / negative
370 ("div", (-21i32) as u32, 5, (-4i32) as u32), // truncation toward zero: -21 / 5 = -4
371 // RISC-V special case:
372 ("div", 0x8000_0000, 0xffff_ffff, 0x8000_0000), // INT_MIN / -1 = INT_MIN (overflow)
373 ("div", 10, 0, u32::MAX), // division by zero returns -1 for signed DIV
374 ("div", 0x8000_0000, 0, u32::MAX),
375 ("rem", 20, 5, 0),
376 ("rem", 21, 5, 1),
377 ("rem", 0, 10, 0),
378 ("rem", 10, 1, 0),
379 ("rem", 23, 5, 3), // positive remainder
380 ("rem", (-23i32) as u32, 5, (-3i32) as u32), // remainder follows the sign of the dividend
381 ("rem", 23, (-5i32) as u32, 3), // negative divisor does not change the sign of the remainder
382 ("rem", (-23i32) as u32, (-5i32) as u32, (-3i32) as u32), // negative / negative
383 ("rem", 3, 5, 3), // dividend smaller than divisor
384 // RISC-V special case:
385 ("rem", 0x8000_0000, 0xffff_ffff, 0), // INT_MIN % -1 = 0.
386 ("rem", 123, 0, 123), // remainder by zero returns the dividend.
387 ("rem", u32::MAX, 0, u32::MAX),
388 ("rem", 0x8000_0000, 0, 0x8000_0000),
389 ];
390 test_ops_r_types_opt(test_vectors);
391 }
392 fn test_ops_r_types_opt(test_vectors: Vec<(&str, u32, u32, u32)>) {
393 for (name, rs1_value, rs2_value, expected) in test_vectors {
394 let rd = 3;
395 let rs1 = 1;
396 let rs2 = 2;
397
398 let instruction = encode_r(name, rd, rs1, rs2);
399
400 let mut cpu = RV32::new(instruction.to_le_bytes().to_vec());
401
402 cpu.regs[rs1 as usize] = rs1_value;
403 cpu.regs[rs2 as usize] = rs2_value;
404
405 cpu.step().unwrap();
406
407 assert_eq!(
408 cpu.regs[rd as usize], expected,
409 "{name} failed:
410 rs1={rs1_value:#010x}, rs2={rs2_value:#010x},
411 expected={expected:#010x}, got={:#010x}",
412 cpu.regs[rd as usize],
413 );
414 }
415 }
416
417 // I-type ops test
418 #[test]
419 fn test_ops_load() {
420 let test_vectors: Vec<(&str, u32, i32, u32)> = vec![
421 ("lb", 0x0000_0080, 0, 0xffff_ff80),
422 ("lbu", 0x0000_0080, 0, 0x0000_0080),
423 ("lb", 0x0000_00ff, 0, 0xffff_ffff),
424 ("lbu", 0x0000_00ff, 0, 0x0000_00ff),
425 ("lh", 0x0000_8000, 0, 0xffff_8000),
426 ("lhu", 0x0000_8000, 0, 0x0000_8000),
427 ("lh", 0x0000_ffff, 0, 0xffff_ffff),
428 ("lhu", 0x0000_ffff, 0, 0x0000_ffff),
429 ];
430
431 for (name, memory_value, address, expected) in test_vectors {
432 let rd = 1;
433 let rs1 = 2;
434
435 let instruction = encode_i(name, rd, rs1, address);
436
437 let mut memory = instruction.to_le_bytes().to_vec();
438 let data_address = memory.len() as u32;
439 memory.extend_from_slice(&memory_value.to_le_bytes());
440 let mut cpu = RV32::new(memory);
441
442 cpu.regs[rs1 as usize] = data_address;
443
444 cpu.step().unwrap();
445
446 assert_eq!(
447 cpu.regs[rd as usize], expected,
448 "{name} failed: memory={memory_value:#010x},
449 address={address}, \
450 expected={expected:#010x},
451 got={:#010x}",
452 cpu.regs[rd as usize],
453 );
454 }
455 }
456
457 // S-type ops test
458 #[test]
459 fn test_ops_store() {
460 let test_vectors: Vec<(&str, u32, i32)> = vec![
461 ("sb", 0x0000_0080, 0),
462 ("sb", 0x0000_00ff, 0),
463 ("sb", 0x1234_5678, 0),
464 ("sh", 0x0000_8000, 0),
465 ("sh", 0x0000_ffff, 0),
466 ("sw", 0x1234_5678, 0),
467 ];
468
469 for (name, value, address) in test_vectors {
470 let rs1 = 1;
471 let rs2 = 2;
472
473 let instruction = encode_s(name, rs1, rs2, address);
474
475 let mut memory = instruction.to_le_bytes().to_vec();
476 let data_address = memory.len() as u32;
477
478 // add space for the value being stored
479 memory.extend_from_slice(&[0u8; 4]);
480
481 let mut cpu = RV32::new(memory);
482
483 cpu.regs[rs1 as usize] = data_address;
484 cpu.regs[rs2 as usize] = value;
485
486 cpu.step().unwrap();
487
488 let stored = u32::from_le_bytes(
489 cpu.mem[data_address as usize..data_address as usize + 4]
490 .try_into()
491 .unwrap(),
492 );
493
494 let expected = match name {
495 "sb" => value & 0xff,
496 "sh" => value & 0xffff,
497 "sw" => value,
498 _ => unreachable!(),
499 };
500
501 assert_eq!(
502 stored, expected,
503 "{name} failed: value={value:#010x},
504 address={address}, \
505 expected={expected:#010x},
506 got={stored:#010x}",
507 );
508 }
509 }
510
511 // B-type ops test
512 #[test]
513 fn test_ops_branch() {
514 let test_vectors: Vec<(&str, u32, u32, i32, bool)> = vec![
515 // (name, rs1 value, rs2 value, offset, taken)
516 ("beq", 10, 10, 8, true),
517 ("beq", 10, 20, 8, false),
518 ("bne", 10, 20, 8, true),
519 ("bne", 10, 10, 8, false),
520 ("blt", 10, 20, 8, true),
521 ("blt", 20, 10, 8, false),
522 ("bge", 20, 10, 8, true),
523 ("bge", 10, 20, 8, false),
524 ("bltu", 10, 20, 8, true),
525 ("bltu", 20, 10, 8, false),
526 ("bgeu", 20, 10, 8, true),
527 ("bgeu", 10, 20, 8, false),
528 ("beq", 10, 10, -4, true), // negative branch offsets
529 ("bne", 10, 20, -4, true),
530 ("blt", 0xffff_ffff, 0, 8, true), // signed vs unsigned comparison
531 ("bltu", 0xffff_ffff, 0, 8, false),
532 ("bge", 0xffff_ffff, 0, 8, false),
533 ("bgeu", 0xffff_ffff, 0, 8, true),
534 ];
535
536 for (name, rs1_value, rs2_value, offset, taken) in test_vectors {
537 let rs1 = 1;
538 let rs2 = 2;
539
540 let instruction = encode_b(name, rs1, rs2, offset);
541 let mut cpu = RV32::new(instruction.to_le_bytes().to_vec());
542
543 cpu.regs[rs1 as usize] = rs1_value;
544 cpu.regs[rs2 as usize] = rs2_value;
545
546 let initial_pc = cpu.pc;
547
548 cpu.step().unwrap();
549
550 let expected_pc = if taken {
551 initial_pc.wrapping_add(offset as u32)
552 } else {
553 initial_pc.wrapping_add(4)
554 };
555
556 assert_eq!(
557 cpu.pc, expected_pc,
558 "{name} failed: rs1={rs1_value:#010x}, \
559 rs2={rs2_value:#010x}, offset={offset}, \
560 expected_pc={expected_pc:#010x}, \
561 got={:#010x}",
562 cpu.pc,
563 );
564 }
565 }
566}