1 //! Decoding support for pulley bytecode. 2 3 use core::ptr::NonNull; 4 5 use alloc::vec::Vec; 6 use cranelift_bitset::scalar::ScalarBitSetStorage; 7 use cranelift_bitset::ScalarBitSet; 8 9 use crate::imms::*; 10 use crate::opcode::*; 11 use crate::regs::*; 12 13 /// Either an `Ok(T)` or an `Err(DecodingError)`. 14 pub type Result<T, E = DecodingError> = core::result::Result<T, E>; 15 16 /// An error when decoding Pulley bytecode. 17 pub enum DecodingError { 18 /// Reached the end of the bytecode stream before we finished decoding a 19 /// single bytecode. 20 UnexpectedEof { 21 /// The position in the bytecode stream where this error occurred. 22 position: usize, 23 }, 24 25 /// Found an invalid opcode. 26 InvalidOpcode { 27 /// The position in the bytecode stream where this error occurred. 28 position: usize, 29 /// The invalid opcode that was found. 30 code: u8, 31 }, 32 33 /// Found an invalid extended opcode. 34 InvalidExtendedOpcode { 35 /// The position in the bytecode stream where this error occurred. 36 position: usize, 37 /// The invalid extended opcode that was found. 38 code: u16, 39 }, 40 41 /// Found an invalid register. 42 InvalidReg { 43 /// The position in the bytecode stream where this error occurred. 44 position: usize, 45 /// The invalid register that was found. 46 reg: u8, 47 }, 48 } 49 50 impl core::fmt::Debug for DecodingError { 51 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { 52 core::fmt::Display::fmt(self, f) 53 } 54 } 55 56 impl core::fmt::Display for DecodingError { 57 fn fmt(&self, f: &mut core::fmt::Formatter<'_>) -> core::fmt::Result { 58 match self { 59 Self::UnexpectedEof { position } => { 60 write!(f, "unexpected end-of-file at bytecode offset {position:#x}") 61 } 62 Self::InvalidOpcode { position, code } => { 63 write!( 64 f, 65 "found invalid opcode {code:#x} at bytecode offset {position:#x}" 66 ) 67 } 68 Self::InvalidExtendedOpcode { position, code } => { 69 write!( 70 f, 71 "found invalid opcode {code:#x} at bytecode offset {position:#x}" 72 ) 73 } 74 Self::InvalidReg { position, reg } => { 75 write!( 76 f, 77 "found invalid register {reg:#x} at bytecode offset {position:#x}" 78 ) 79 } 80 } 81 } 82 } 83 84 #[cfg(feature = "std")] 85 impl std::error::Error for DecodingError {} 86 87 /// An abstraction over any kind of bytecode stream. 88 /// 89 /// There are two primary implementations: 90 /// 91 /// 1. `SafeBytecodeStream`: A thin wrapper around an index into a `&[u8]`. This 92 /// implementation is 100% safe code. 93 /// 94 /// 2. `UnsafeBytecodeStream`: A thin wrapper over a raw pointer. This 95 /// implementation is wildly unsafe and will result in memory unsafety and 96 /// other terrors when given invalid bytecode, or even valid bytecode 97 /// encoding a program that itself does not preserve memory safety. 98 pub trait BytecodeStream: Copy { 99 /// The type of error that this bytecode stream produces on invalid 100 /// operations. 101 type Error; 102 103 /// Create an "unexpected end-of-stream" error at the current position. 104 fn unexpected_eof(&self) -> Self::Error; 105 106 /// Create an "invalid opcode" error at the current position. 107 fn invalid_opcode(&self, code: u8) -> Self::Error; 108 109 /// Create an "invalid extended opcode" error at the current position. 110 fn invalid_extended_opcode(&self, code: u16) -> Self::Error; 111 112 /// Create an "invalid register" error at the current position. 113 fn invalid_reg(&self, reg: u8) -> Self::Error; 114 115 /// Read `N` bytes from this bytecode stream, advancing the stream's 116 /// position at the same time. 117 fn read<const N: usize>(&mut self) -> Result<[u8; N], Self::Error>; 118 } 119 120 /// A 100% safe implementation of a bytecode stream. 121 /// 122 /// This is a thin wrapper around an index into a `&[u8]`. 123 #[derive(Clone, Copy, Debug)] 124 pub struct SafeBytecodeStream<'a> { 125 bytecode: &'a [u8], 126 position: usize, 127 } 128 129 impl<'a> SafeBytecodeStream<'a> { 130 /// Create a new `SafeBytecodeStream` from the given slice and with an 131 /// initial position pointing at the start of the slice. 132 pub fn new(bytecode: &'a [u8]) -> Self { 133 Self { 134 bytecode, 135 position: 0, 136 } 137 } 138 139 /// Get this stream's current position within its underlying slice. 140 pub fn position(&self) -> usize { 141 self.position 142 } 143 144 /// Get this stream's underlying bytecode slice. 145 pub fn as_slice(&self) -> &[u8] { 146 &self.bytecode 147 } 148 } 149 150 impl BytecodeStream for SafeBytecodeStream<'_> { 151 fn read<const N: usize>(&mut self) -> Result<[u8; N], Self::Error> { 152 let (bytes, rest) = self 153 .bytecode 154 .split_first_chunk() 155 .ok_or_else(|| self.unexpected_eof())?; 156 self.bytecode = rest; 157 self.position += N; 158 Ok(*bytes) 159 } 160 161 type Error = DecodingError; 162 163 fn unexpected_eof(&self) -> Self::Error { 164 DecodingError::UnexpectedEof { 165 position: self.position, 166 } 167 } 168 169 fn invalid_opcode(&self, code: u8) -> Self::Error { 170 DecodingError::InvalidOpcode { 171 position: self.position - 1, 172 code, 173 } 174 } 175 176 fn invalid_extended_opcode(&self, code: u16) -> Self::Error { 177 DecodingError::InvalidExtendedOpcode { 178 position: self.position, 179 code, 180 } 181 } 182 183 fn invalid_reg(&self, reg: u8) -> Self::Error { 184 DecodingError::InvalidReg { 185 position: self.position, 186 reg, 187 } 188 } 189 } 190 191 /// An uninhabited type that cannot be constructed at runtime. 192 #[derive(Debug)] 193 pub enum Uninhabited {} 194 195 /// An unsafe bytecode stream. 196 /// 197 /// This is a wrapper over a raw pointer to bytecode somewhere in memory. 198 #[derive(Clone, Copy, Debug)] 199 pub struct UnsafeBytecodeStream(NonNull<u8>); 200 201 impl UnsafeBytecodeStream { 202 /// Construct a new `UnsafeBytecodeStream` pointing at the given PC. 203 /// 204 /// # Safety 205 /// 206 /// The given `pc` must point to valid Pulley bytecode, and it is the 207 /// caller's responsibility to ensure that the resulting 208 /// `UnsafeBytecodeStream` is only used to access the valid bytecode. For 209 /// example, if the current bytecode instruction unconditionally jumps to a 210 /// new PC, this stream must not be used to read just after the 211 /// unconditional jump instruction because there is no guarantee that that 212 /// memory is part of the bytecode stream or not. 213 pub unsafe fn new(pc: NonNull<u8>) -> Self { 214 UnsafeBytecodeStream(pc) 215 } 216 217 /// Get a new `UnsafeBytecodeStream` pointing at the bytecode that is at the 218 /// given relative offset from this stream's current position. 219 /// 220 /// # Safety 221 /// 222 /// Same as the `new` constructor. May only be used when it is guaranteed 223 /// that the address at `self._as_ptr() + offset` contains valid Pulley 224 /// bytecode. 225 pub unsafe fn offset(&self, offset: isize) -> Self { 226 UnsafeBytecodeStream(NonNull::new_unchecked(self.0.as_ptr().offset(offset))) 227 } 228 229 /// Get this stream's underlying raw pointer. 230 pub fn as_ptr(&self) -> NonNull<u8> { 231 self.0 232 } 233 } 234 235 impl BytecodeStream for UnsafeBytecodeStream { 236 fn read<const N: usize>(&mut self) -> Result<[u8; N], Self::Error> { 237 let bytes = unsafe { self.0.cast::<[u8; N]>().as_ptr().read() }; 238 self.0 = unsafe { NonNull::new_unchecked(self.0.as_ptr().add(N)) }; 239 Ok(bytes) 240 } 241 242 type Error = Uninhabited; 243 244 fn unexpected_eof(&self) -> Self::Error { 245 unsafe { crate::unreachable_unchecked() } 246 } 247 248 fn invalid_opcode(&self, _code: u8) -> Self::Error { 249 unsafe { crate::unreachable_unchecked() } 250 } 251 252 fn invalid_extended_opcode(&self, _code: u16) -> Self::Error { 253 unsafe { crate::unreachable_unchecked() } 254 } 255 256 fn invalid_reg(&self, _reg: u8) -> Self::Error { 257 unsafe { crate::unreachable_unchecked() } 258 } 259 } 260 261 /// Anything that can be decoded from a bytecode stream, e.g. opcodes, 262 /// immediates, registers, etc... 263 trait Decode: Sized { 264 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 265 where 266 T: BytecodeStream; 267 } 268 269 impl Decode for u8 { 270 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 271 where 272 T: BytecodeStream, 273 { 274 bytecode.read::<1>().map(|a| a[0]) 275 } 276 } 277 278 impl Decode for u16 { 279 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 280 where 281 T: BytecodeStream, 282 { 283 Ok(u16::from_le_bytes(bytecode.read()?)) 284 } 285 } 286 287 impl Decode for u32 { 288 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 289 where 290 T: BytecodeStream, 291 { 292 Ok(u32::from_le_bytes(bytecode.read()?)) 293 } 294 } 295 296 impl Decode for u64 { 297 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 298 where 299 T: BytecodeStream, 300 { 301 Ok(u64::from_le_bytes(bytecode.read()?)) 302 } 303 } 304 305 impl Decode for i8 { 306 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 307 where 308 T: BytecodeStream, 309 { 310 bytecode.read::<1>().map(|a| a[0] as i8) 311 } 312 } 313 314 impl Decode for i16 { 315 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 316 where 317 T: BytecodeStream, 318 { 319 Ok(i16::from_le_bytes(bytecode.read()?)) 320 } 321 } 322 323 impl Decode for i32 { 324 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 325 where 326 T: BytecodeStream, 327 { 328 Ok(i32::from_le_bytes(bytecode.read()?)) 329 } 330 } 331 332 impl Decode for i64 { 333 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 334 where 335 T: BytecodeStream, 336 { 337 Ok(i64::from_le_bytes(bytecode.read()?)) 338 } 339 } 340 341 impl Decode for XReg { 342 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 343 where 344 T: BytecodeStream, 345 { 346 let byte = u8::decode(bytecode)?; 347 XReg::new(byte).ok_or_else(|| bytecode.invalid_reg(byte)) 348 } 349 } 350 351 impl Decode for FReg { 352 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 353 where 354 T: BytecodeStream, 355 { 356 let byte = u8::decode(bytecode)?; 357 FReg::new(byte).ok_or_else(|| bytecode.invalid_reg(byte)) 358 } 359 } 360 361 impl Decode for VReg { 362 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 363 where 364 T: BytecodeStream, 365 { 366 let byte = u8::decode(bytecode)?; 367 VReg::new(byte).ok_or_else(|| bytecode.invalid_reg(byte)) 368 } 369 } 370 371 impl Decode for PcRelOffset { 372 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 373 where 374 T: BytecodeStream, 375 { 376 i32::decode(bytecode).map(|x| Self::from(x)) 377 } 378 } 379 380 impl<R: Reg> Decode for BinaryOperands<R> { 381 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 382 where 383 T: BytecodeStream, 384 { 385 u16::decode(bytecode).map(|bits| Self::from_bits(bits)) 386 } 387 } 388 389 impl<S: Decode + ScalarBitSetStorage> Decode for ScalarBitSet<S> { 390 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 391 where 392 T: BytecodeStream, 393 { 394 S::decode(bytecode).map(ScalarBitSet::from) 395 } 396 } 397 398 impl<R: Reg + Decode> Decode for RegSet<R> { 399 fn decode<T>(bytecode: &mut T) -> Result<Self, T::Error> 400 where 401 T: BytecodeStream, 402 { 403 ScalarBitSet::decode(bytecode).map(Self::from) 404 } 405 } 406 407 /// A Pulley bytecode decoder. 408 /// 409 /// Does not materialize bytecode instructions, instead all decoding methods are 410 /// given an `OpVisitor` implementation and the appropriate visitor methods are 411 /// called upon decoding an instruction. This minimizes the amount of times we 412 /// branch on the opcode, avoids constructing temporary storage, and plays well 413 /// with our variable-length instruction encoding. 414 #[derive(Default)] 415 pub struct Decoder { 416 _private: (), 417 } 418 419 impl Decoder { 420 /// Create a new decoder. 421 pub fn new() -> Self { 422 Self::default() 423 } 424 425 /// Decode all instructions in the visitor's bytecode stream. 426 /// 427 /// The associated visitor method is invoked after each instruction is 428 /// decoded. 429 pub fn decode_all<'a, V>(visitor: &mut V) -> Result<Vec<V::Return>> 430 where 431 V: OpVisitor<BytecodeStream = SafeBytecodeStream<'a>> + ExtendedOpVisitor, 432 { 433 let mut decoder = Decoder::new(); 434 let mut results = Vec::new(); 435 436 while !visitor.bytecode().as_slice().is_empty() { 437 results.push(decoder.decode_one(visitor)?); 438 } 439 440 Ok(results) 441 } 442 } 443 444 /// An `OpVisitor` combinator to sequence one visitor and then another. 445 pub struct SequencedVisitor<'a, F, V1, V2> { 446 join: F, 447 v1: &'a mut V1, 448 v2: &'a mut V2, 449 } 450 451 impl<'a, F, V1, V2> SequencedVisitor<'a, F, V1, V2> { 452 /// Create a new sequenced visitor. 453 /// 454 /// The given `join` function is used to combine the results of each 455 /// sub-visitor so that it can be returned from this combined visitor. 456 pub fn new(join: F, v1: &'a mut V1, v2: &'a mut V2) -> Self { 457 SequencedVisitor { join, v1, v2 } 458 } 459 } 460 461 macro_rules! define_decoder { 462 ( 463 $( 464 $( #[$attr:meta] )* 465 $snake_name:ident = $name:ident $( { 466 $( 467 $( #[$field_attr:meta] )* 468 $field:ident : $field_ty:ty 469 ),* 470 } )? ; 471 )* 472 ) => { 473 impl Decoder { 474 /// Decode one instruction from the visitor's bytestream. 475 /// 476 /// Upon decoding, the visitor's associated callback is invoked and 477 /// the results returned. 478 #[inline(always)] 479 pub fn decode_one<V>( 480 &mut self, 481 visitor: &mut V, 482 ) -> Result<V::Return, <V::BytecodeStream as BytecodeStream>::Error> 483 where 484 V: OpVisitor + ExtendedOpVisitor, 485 { 486 visitor.before_visit(); 487 488 let byte = u8::decode(visitor.bytecode())?; 489 let opcode = Opcode::new(byte).ok_or_else(|| { 490 visitor.bytecode().invalid_opcode(byte) 491 })?; 492 493 match opcode { 494 $( 495 Opcode::$name => { 496 $( 497 $( 498 let $field = <$field_ty>::decode( 499 visitor.bytecode(), 500 )?; 501 )* 502 )? 503 504 let ret = visitor.$snake_name($( $( $field ),* )?); 505 visitor.after_visit(); 506 Ok(ret) 507 }, 508 )* 509 Opcode::ExtendedOp => { 510 decode_one_extended(visitor) 511 } 512 } 513 } 514 } 515 516 /// Callbacks upon decoding instructions from bytecode. 517 /// 518 /// Implement this trait for your type, give an instance of your type to 519 /// a `Decoder` method, and the `Decoder` will invoke the associated 520 /// method for each instruction that it decodes. For example, if the 521 /// `Decoder` decodes an `xadd32` instruction, then it will invoke the 522 /// `xadd32` visitor method, passing along any decoded immediates, 523 /// operands, etc... as arguments. 524 pub trait OpVisitor { 525 /// The type of this visitor's bytecode stream. 526 type BytecodeStream: BytecodeStream; 527 528 /// Get this visitor's underlying bytecode stream. 529 fn bytecode(&mut self) -> &mut Self::BytecodeStream; 530 531 /// The type of values returned by each visitor method. 532 type Return; 533 534 /// A callback invoked before starting to decode an instruction. 535 /// 536 /// Does nothing by default. 537 fn before_visit(&mut self) {} 538 539 /// A callback invoked after an instruction has been completely 540 /// decoded. 541 /// 542 /// Does nothing by default. 543 fn after_visit(&mut self) {} 544 545 $( 546 $( #[$attr] )* 547 fn $snake_name(&mut self $( $( , $field : $field_ty )* )? ) -> Self::Return; 548 )* 549 } 550 551 impl<F, T, V1, V2> OpVisitor for SequencedVisitor<'_, F, V1, V2> 552 where 553 F: FnMut(V1::Return, V2::Return) -> T, 554 V1: OpVisitor, 555 V2: OpVisitor<BytecodeStream = V1::BytecodeStream>, 556 { 557 type BytecodeStream = V1::BytecodeStream; 558 559 fn bytecode(&mut self) -> &mut Self::BytecodeStream { 560 self.v1.bytecode() 561 } 562 563 type Return = T; 564 565 fn before_visit(&mut self) { 566 self.v1.before_visit(); 567 self.v2.before_visit(); 568 } 569 570 fn after_visit(&mut self) { 571 *self.v2.bytecode() = *self.v1.bytecode(); 572 self.v1.after_visit(); 573 self.v2.after_visit(); 574 } 575 576 $( 577 $( #[$attr] )* 578 fn $snake_name(&mut self $( $( , $field : $field_ty )* )? ) -> Self::Return { 579 let a = self.v1.$snake_name( $( $( $field , )* )? ); 580 let b = self.v2.$snake_name( $( $( $field , )* )? ); 581 (self.join)(a, b) 582 } 583 )* 584 } 585 }; 586 } 587 for_each_op!(define_decoder); 588 589 macro_rules! define_extended_decoder { 590 ( 591 $( 592 $( #[$attr:meta] )* 593 $snake_name:ident = $name:ident $( { 594 $( 595 $( #[$field_attr:meta] )* 596 $field:ident : $field_ty:ty 597 ),* 598 } )? ; 599 )* 600 ) => { 601 /// Like `OpVisitor` but for extended operations. 602 pub trait ExtendedOpVisitor: OpVisitor { 603 $( 604 $( #[$attr] )* 605 fn $snake_name(&mut self $( $( , $field : $field_ty )* )? ) -> Self::Return; 606 )* 607 } 608 609 fn decode_one_extended<V>( 610 visitor: &mut V, 611 ) -> Result<V::Return, <V::BytecodeStream as BytecodeStream>::Error> 612 where 613 V: ExtendedOpVisitor, 614 { 615 let code = u16::decode(visitor.bytecode())?; 616 let opcode = ExtendedOpcode::new(code).ok_or_else(|| { 617 visitor.bytecode().invalid_extended_opcode(code) 618 })?; 619 620 match opcode { 621 $( 622 ExtendedOpcode::$name => { 623 $( 624 $( 625 let $field = <$field_ty>::decode( 626 visitor.bytecode(), 627 )?; 628 )* 629 )? 630 631 let ret = visitor.$snake_name($( $( $field ),* )?); 632 visitor.after_visit(); 633 Ok(ret) 634 } 635 )* 636 } 637 } 638 639 640 impl<F, T, V1, V2> ExtendedOpVisitor for SequencedVisitor<'_, F, V1, V2> 641 where 642 F: FnMut(V1::Return, V2::Return) -> T, 643 V1: ExtendedOpVisitor, 644 V2: ExtendedOpVisitor<BytecodeStream = V1::BytecodeStream>, 645 { 646 $( 647 $( #[$attr] )* 648 fn $snake_name(&mut self $( $( , $field : $field_ty )* )? ) -> Self::Return { 649 let a = self.v1.$snake_name( $( $( $field , )* )? ); 650 let b = self.v2.$snake_name( $( $( $field , )* )? ); 651 (self.join)(a, b) 652 } 653 )* 654 } 655 }; 656 } 657 for_each_extended_op!(define_extended_decoder); 658