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 let imm = sign_extend(instruction >> 20, 12);
63
64 let a = self.regs[rs1];
65 let b = self.regs[rs2];
66 let result: Option<u32>;
67
68 // 0x7f=0111_1111, match the lowest 7 bits to read the opcode
69 match instruction & 0x7f {
70 // I-type op'ns:
71 // Loads
72 0x03 => {
73 let (size, signed) = match funct3 {
74 // LB: load a byte at rs1 + immediate and sign-extend it into rd
75 0 => (1, true),
76 // LH: load a halfword at rs1 + immediate and sign-extend it into rd
77 1 => (2, true),
78 // LW: load a 32-bit word at rs1 + immediate into rd
79 2 => (4, false),
80 // LBU: load a byte at rs1 + immediate and zero-extend it into rd
81 4 => (1, false),
82 // LHU: load a halfword at rs1 + immediate and zero-extend it into rd
83 5 => (2, false),
84 _ => return Err(anyhow!("illegal instruction: {}", instruction)),
85 };
86 let value = self.read(a.wrapping_add(imm), size)?;
87 result = Some(if signed {
88 sign_extend(value, size as u32 * 8)
89 } else {
90 value
91 });
92 }
93
94 // R-type (register-register) integer operations
95 0x33 => {
96 result = Some(match (funct7, funct3) {
97 // ADD: add rs1 and rs2, wrapping to 32 bits
98 (0, 0) => a.wrapping_add(b),
99 // SUB: subtract rs2 from rs1, wrapping to 32 bits
100 (0x20, 0) => a.wrapping_sub(b),
101 // SLL: shift rs1 left by the low five bits of rs2
102 (0, 1) => a << (b & 31),
103 // SLT: set rd to one if rs1 is less than rs2 as signed
104 // values, else zero
105 (0, 2) => u32::from((a as i32) < (b as i32)),
106 // SLTU: set rd to one if rs1 is less than rs2 as unsigned
107 // values, else zero
108 (0, 3) => u32::from(a < b),
109 // XOR: write the bitwise XOR of rs1 and rs2 into rd
110 (0, 4) => a ^ b,
111 // SRL: shift rs1 right by the low five bits of rs2, filling
112 // with zeros
113 (0, 5) => a >> (b & 31),
114 // SRA: shift rs1 right by the low five bits of rs2,
115 // preserving its sign
116 (0x20, 5) => ((a as i32) >> (b & 31)) as u32,
117 // OR: write the bitwise OR of rs1 and rs2 into rd
118 (0, 6) => a | b,
119 // AND: write the bitwise AND of rs1 and rs2 into rd
120 (0, 7) => a & b,
121
122 // Note: MUL,DIV,REM are not part of RV32I, but they are in
123 // the M extension.
124
125 // MUL: write the low 32 bits of the product of rs1 and rs2
126 (1, 0) => a.wrapping_mul(b),
127 // DIV: signed quotient toward zero; zero divisors return
128 // all ones
129 (1, 4) => {
130 if b == 0 {
131 u32::MAX
132 } else {
133 (a as i32).wrapping_div(b as i32) as u32
134 }
135 }
136 // REM: signed remainder; zero divisors return the dividend
137 (1, 6) => {
138 if b == 0 {
139 a
140 } else {
141 (a as i32).wrapping_rem(b as i32) as u32
142 }
143 }
144
145 _ => return Err(anyhow!("illegal instruction (A): {}", instruction)),
146 });
147 }
148 _ => return Err(anyhow!("illegal instruction (B): {}", instruction)),
149 }
150
151 if next_pc & 3 != 0 {
152 return Err(anyhow!("misaligned, address: {}", next_pc,));
153 }
154 if let Some(value) = result {
155 self.set_register(rd, value);
156 }
157 self.pc = next_pc;
158 Ok(())
159 }
160}
161
162// sign-extend a smaller signed number to 32 bits
163fn sign_extend(value: u32, bits: u32) -> u32 {
164 ((value << (32 - bits)) as i32 >> (32 - bits)) as u32
165}
166
167#[cfg(test)]
168mod tests {
169 use super::*;
170
171 const OPCODE_R: u32 = 0b0110011;
172 const OPCODE_LOAD: u32 = 0b0000011;
173
174 // encodes R-type instruction
175 fn encode_r(name: &str, rd: u32, rs1: u32, rs2: u32) -> u32 {
176 let (funct7, funct3) = match name {
177 "add" => (0b0000000, 0b000),
178 "sub" => (0b0100000, 0b000),
179 "sll" => (0b0000000, 0b001),
180 "slt" => (0b0000000, 0b010),
181 "sltu" => (0b0000000, 0b011),
182 "xor" => (0b0000000, 0b100),
183 "srl" => (0b0000000, 0b101),
184 "sra" => (0b0100000, 0b101),
185 "or" => (0b0000000, 0b110),
186 "and" => (0b0000000, 0b111),
187 // M extension
188 "mul" => (0b0000001, 0b000),
189 "div" => (0b0000001, 0b100),
190 "rem" => (0b0000001, 0b110),
191 _ => panic!("unknown R-type instruction: {name}"),
192 };
193
194 (funct7 << 25) | (rs2 << 20) | (rs1 << 15) | (funct3 << 12) | (rd << 7) | OPCODE_R
195 }
196 fn encode_i(name: &str, rd: u32, rs1: u32, imm: i32) -> u32 {
197 let funct3 = match name {
198 "lb" => 0b000,
199 "lh" => 0b001,
200 "lw" => 0b010,
201 "lbu" => 0b100,
202 "lhu" => 0b101,
203 _ => panic!("unknown load instruction: {name}"),
204 };
205
206 let imm = (imm as u32) & 0xfff;
207
208 (imm << 20) | (rs1 << 15) | (funct3 << 12) | (rd << 7) | OPCODE_LOAD
209 }
210
211 #[test]
212 fn test_ops_r_type() {
213 let test_vectors = vec![
214 // (op, rs1, rs2, rd)
215 ("add", 10, 20, 30),
216 ("add", u32::MAX, 1, 0), // overflow
217 ("sub", 30, 20, 10),
218 ("sub", 0, 1, u32::MAX), // overflow
219 ("sll", 1, 4, 16),
220 ("sll", 1, 31, 0x8000_0000), // SLL maximum shift
221 ("sll", 1, 32, 1), // SLL shift wrapping
222 ("slt", (-10i32) as u32, 20, 1),
223 ("sltu", 10, 20, 1),
224 ("slt", 0xffff_ffff, 0, 1), // signed comparison: -1 < 0
225 ("slt", 0xffff_ffff, 0, 1), // signed vs unsigned distinction
226 ("sltu", 0xffff_ffff, 0, 0),
227 ("xor", 0b1010, 0b1100, 0b0110),
228 ("srl", 0x8000_0000, 4, 0x0800_0000),
229 ("srl", 0x8000_0000, 1, 0x4000_0000), // logical shift should zero-fill
230 ("sra", 0x8000_0000, 4, 0xf800_0000),
231 ("sra", 0x8000_0000, 1, 0xc000_0000), // arithmetic shift should sign-fill
232 ("sra", 0xffff_ffff, 31, 0xffff_ffff), // arithmetic shift of -1 stays -1
233 ("or", 0b1010, 0b1100, 0b1110),
234 ("and", 0b1010, 0b1100, 0b1000),
235 ];
236 test_ops_r_types_opt(test_vectors);
237 }
238 #[test]
239 fn test_ops_m_extension() {
240 let test_vectors = vec![
241 ("mul", 10, 20, 200),
242 ("mul", 0, 123, 0),
243 ("mul", 1, u32::MAX, u32::MAX),
244 ("mul", u32::MAX, 2, u32::MAX - 1), // result wraps to lower 32 bits
245 ("mul", (-1i32) as u32, 10, (-10i32) as u32), // -1 * 10 = -10
246 ("mul", (-1i32) as u32, (-1i32) as u32, 1), // -1 * -1 = 1
247 ("mul", 0x8000_0000, 2, 0), // INT_MIN * 2 = 0 modulo 2^32
248 ("mul", 0x8000_0000, 0xffff_ffff, 0x8000_0000), // INT_MIN * -1 also wraps to INT_MIN
249 ("div", 20, 5, 4),
250 ("div", 21, 5, 4), // truncates toward zero
251 ("div", 0, 10, 0),
252 ("div", 10, 1, 10),
253 ("div", 10, (-1i32) as u32, (-10i32) as u32),
254 ("div", (-20i32) as u32, 5, (-4i32) as u32), // negative dividend
255 ("div", 20, (-5i32) as u32, (-4i32) as u32), // negative divisor
256 ("div", (-20i32) as u32, (-5i32) as u32, 4), // negative / negative
257 ("div", (-21i32) as u32, 5, (-4i32) as u32), // truncation toward zero: -21 / 5 = -4
258 // RISC-V special case:
259 ("div", 0x8000_0000, 0xffff_ffff, 0x8000_0000), // INT_MIN / -1 = INT_MIN (overflow)
260 ("div", 10, 0, u32::MAX), // division by zero returns -1 for signed DIV
261 ("div", 0x8000_0000, 0, u32::MAX),
262 ("rem", 20, 5, 0),
263 ("rem", 21, 5, 1),
264 ("rem", 0, 10, 0),
265 ("rem", 10, 1, 0),
266 ("rem", 23, 5, 3), // positive remainder
267 ("rem", (-23i32) as u32, 5, (-3i32) as u32), // remainder follows the sign of the dividend
268 ("rem", 23, (-5i32) as u32, 3), // negative divisor does not change the sign of the remainder
269 ("rem", (-23i32) as u32, (-5i32) as u32, (-3i32) as u32), // negative / negative
270 ("rem", 3, 5, 3), // dividend smaller than divisor
271 // RISC-V special case:
272 ("rem", 0x8000_0000, 0xffff_ffff, 0), // INT_MIN % -1 = 0.
273 ("rem", 123, 0, 123), // remainder by zero returns the dividend.
274 ("rem", u32::MAX, 0, u32::MAX),
275 ("rem", 0x8000_0000, 0, 0x8000_0000),
276 ];
277 test_ops_r_types_opt(test_vectors);
278 }
279 fn test_ops_r_types_opt(test_vectors: Vec<(&str, u32, u32, u32)>) {
280 for (name, rs1_value, rs2_value, expected) in test_vectors {
281 let rd = 3;
282 let rs1 = 1;
283 let rs2 = 2;
284
285 let instruction = encode_r(name, rd, rs1, rs2);
286
287 let mut cpu = RV32::new(instruction.to_le_bytes().to_vec());
288
289 cpu.regs[rs1 as usize] = rs1_value;
290 cpu.regs[rs2 as usize] = rs2_value;
291
292 cpu.step().unwrap();
293
294 assert_eq!(
295 cpu.regs[rd as usize], expected,
296 "{name} failed:
297 rs1={rs1_value:#010x}, rs2={rs2_value:#010x},
298 expected={expected:#010x}, got={:#010x}",
299 cpu.regs[rd as usize],
300 );
301 }
302 }
303
304 #[test]
305 fn test_ops_load() {
306 let test_vectors: [(&str, u32, i32, u32); 8] = [
307 ("lb", 0x0000_0080, 0, 0xffff_ff80),
308 ("lbu", 0x0000_0080, 0, 0x0000_0080),
309 ("lb", 0x0000_00ff, 0, 0xffff_ffff),
310 ("lbu", 0x0000_00ff, 0, 0x0000_00ff),
311 ("lh", 0x0000_8000, 0, 0xffff_8000),
312 ("lhu", 0x0000_8000, 0, 0x0000_8000),
313 ("lh", 0x0000_ffff, 0, 0xffff_ffff),
314 ("lhu", 0x0000_ffff, 0, 0x0000_ffff),
315 ];
316
317 for (name, memory_value, address, expected) in test_vectors {
318 let rd = 1;
319 let rs1 = 2;
320
321 let instruction = encode_i(name, rd, rs1, address);
322
323 let mut memory = instruction.to_le_bytes().to_vec();
324 let data_address = memory.len() as u32;
325 memory.extend_from_slice(&memory_value.to_le_bytes());
326 let mut cpu = RV32::new(memory);
327
328 cpu.regs[rs1 as usize] = data_address;
329
330 cpu.step().unwrap();
331
332 assert_eq!(
333 cpu.regs[rd as usize], expected,
334 "{name} failed: memory={memory_value:#010x},
335 address={address}, \
336 expected={expected:#010x},
337 got={:#010x}",
338 cpu.regs[rd as usize],
339 );
340 }
341 }
342}