1use qbe_reader::types::*;2use qbe_reader::Definition;3use std::collections::HashMap;45use z3::{6 ast::{Ast, BV},7 Context,8};910use crate::error::*;11use crate::memory::*;12use crate::value::*;1314// Bit pattern used to pretend that we actually store functions15// in memory (which we don't) cause we don't have an instruction16// representation. Hence, we just store this pattern instead.17//18// TODO: Just store unconstrained symbolic bytes instead.19const FUNC_PATTERN: u32 = 0xdeadbeef;2021struct FuncState<'ctx, 'src> {22 labels: HashMap<&'src str, &'src Block>,23 local: HashMap<&'src str, BV<'ctx>>,2425 // Value of the stack pointer when this stack frame was created.26 stkptr: BV<'ctx>,27}2829pub struct State<'ctx, 'src> {30 v: ValueFactory<'ctx>,31 pub mem: Memory<'ctx>,32 stkptr: BV<'ctx>,3334 func: HashMap<&'src str, (BV<'ctx>, &'src FuncDef)>,35 data: HashMap<&'src str, (BV<'ctx>, &'src DataDef)>,36 stck: Vec<FuncState<'ctx, 'src>>,37}3839impl<'ctx, 'src> State<'ctx, 'src> {40 pub fn new(41 ctx: &'ctx Context,42 source: &'src Vec<Definition>,43 ) -> Result<State<'ctx, 'src>, Error> {44 let v = ValueFactory::new(ctx);45 let mut state = State {46 stkptr: v.make_long(0),47 v,4849 func: HashMap::new(),50 data: HashMap::new(),51 stck: Vec::new(),5253 mem: Memory::new(ctx),54 };5556 let mut func_end_ptr = state.v.make_long(0);57 for x in source.into_iter() {58 if let Definition::Func(f) = x {59 func_end_ptr = state.add_func(func_end_ptr.clone(), f);60 }61 }6263 let mut data_end_ptr = func_end_ptr.clone();64 for x in source.into_iter() {65 if let Definition::Data(d) = x {66 data_end_ptr = state.add_data(data_end_ptr.clone(), d)?;67 }68 }6970 state.stkptr = data_end_ptr;71 Ok(state)72 }7374 fn add_func(&mut self, addr: BV<'ctx>, func: &'src FuncDef) -> BV<'ctx> {75 self.mem76 .store_word(addr.clone(), self.v.make_word(FUNC_PATTERN));77 let end_addr = addr.bvadd(&self.v.make_long(4));7879 self.func.insert(&func.name, (addr.clone(), func));80 end_addr81 }8283 fn add_data(&mut self, addr: BV<'ctx>, data: &'src DataDef) -> Result<BV<'ctx>, Error> {84 // Insert into map before actually inserting the data into memory85 // to support self-referencing data decls: `data $c = { l $c }`.86 self.data.insert(&data.name, (addr.clone(), data));8788 let mut end_addr = addr;89 for obj in data.objs.iter() {90 end_addr = self.insert_data_object(end_addr.clone(), obj)?;91 }92 Ok(end_addr)93 }9495 fn insert_data_object(&mut self, addr: BV<'ctx>, obj: &DataObj) -> Result<BV<'ctx>, Error> {96 let mut cur_addr = addr;97 match obj {98 DataObj::DataItem(ty, items) => {99 for item in items.iter() {100 cur_addr = self.insert_data_item(ty, cur_addr, item)?;101 }102 }103 DataObj::ZeroFill(n) => {104 let zero = self.v.make_byte(0);105 for i in 0..*n {106 cur_addr = cur_addr.bvadd(&self.v.make_long(i));107 self.mem.store_byte(cur_addr.clone(), zero.clone())108 }109 }110 }111112 Ok(cur_addr)113 }114115 pub fn insert_data_item(116 &mut self,117 ty: &ExtType,118 addr: BV<'ctx>,119 item: &DataItem,120 ) -> Result<BV<'ctx>, Error> {121 let mut cur_addr = addr;122 match item {123 DataItem::Symbol(name, offset) => {124 let mut ptr = self125 .get_ptr(name)126 .ok_or(Error::UnknownVariable(name.to_string()))?;127 assert!(ptr.get_size() == LONG_SIZE);128 if let Some(off) = offset {129 let off = self.v.make_long(*off);130 ptr = ptr.bvadd(&off);131 }132133 assert!(ptr.get_size() % 8 == 0);134 let bytes = (ptr.get_size() / 8) as u64;135136 self.mem.store_bitvector(cur_addr.clone(), ptr);137 cur_addr = cur_addr.bvadd(&self.v.make_long(bytes));138 }139 DataItem::String(str) => {140 if *ty != ExtType::Byte {141 return Err(Error::UnsupportedStringType);142 }143 cur_addr = self.mem.store_string(cur_addr, str);144 }145 // TODO: Reduce code duplication with get_const() from interp.rs146 DataItem::Const(c) => match c {147 Const::Number(n) => {148 let bv = self.v.from_ext_i64(*ty, *n);149 let size = bv.get_size() as u64;150 self.mem.store_bitvector(cur_addr.clone(), bv);151152 assert!(size % 8 == 0);153 cur_addr = cur_addr.bvadd(&self.v.make_long(size / 8));154 }155 Const::SFP(_) => {156 panic!("single precision floating points not supported")157 }158 Const::DFP(_) => {159 panic!("double precision floating points not supported")160 }161 Const::Global(_) => unreachable!(),162 },163 }164165 Ok(cur_addr)166 }167168 pub fn get_ptr(&self, name: &str) -> Option<BV<'ctx>> {169 // TODO: Check based on end pointer which map we need to consult.170 match self.data.get(name) {171 Some((addr, _)) => Some(addr.clone()),172 None => match self.func.get(name) {173 Some((addr, _)) => Some(addr.clone()),174 None => None,175 },176 }177 }178179 pub fn get_func(&mut self, name: &str) -> Option<&'src FuncDef> {180 Some(self.func.get(name)?.1)181 }182183 pub fn stack_size(&self) -> usize {184 self.stck.len()185 }186187 pub fn stack_alloc(&mut self, align: u8, size: u64) -> BV<'ctx> {188 let align = align as u64;189 assert!(self.stck.len() != 0);190191 // (addr - (addr % alignment)) + alignment192 let aligned_addr = self193 .stkptr194 .bvsub(&self.stkptr.bvurem(&self.v.make_long(align)))195 .bvadd(&self.v.make_long(align));196 self.stkptr = aligned_addr.bvadd(&self.v.make_long(size));197198 assert!(aligned_addr.get_size() == LONG_SIZE);199 aligned_addr.clone()200 }201202 /////203 // Function-local operations204 /////205206 pub fn push_func(&mut self, func: &'src FuncDef) {207 let blocks = func.body.iter().map(|blk| (blk.label.as_str(), blk));208 let state = FuncState {209 labels: HashMap::from_iter(blocks),210 local: HashMap::new(),211 stkptr: self.stkptr.clone(),212 };213214 self.stck.push(state);215 }216217 pub fn get_block(&self, name: &str) -> Option<&'src Block> {218 let func = self.stck.last().unwrap();219 func.labels.get(name).map(|b| *b)220 }221222 pub fn add_local(&mut self, name: &'src str, value: BV<'ctx>) {223 let func = self.stck.last_mut().unwrap();224 func.local.insert(name, value);225 }226227 pub fn get_local(&self, name: &str) -> Option<BV<'ctx>> {228 let func = self.stck.last().unwrap();229 // BV should be an owned object modeled on a C++230 // smart pointer. Hence the clone here is cheap231 func.local.get(name).cloned()232 }233234 pub fn pop_func(&mut self) {235 let func = self.stck.pop().unwrap();236 self.stkptr = func.stkptr;237 }238239 // TODO: Remove this240 pub fn dump_locals(&self) {241 let func = self.stck.last().unwrap();242243 let mut v: Vec<_> = func.local.iter().collect();244 v.sort_by_key(|a| a.0);245246 for (key, value) in v.iter() {247 println!("\t{} = {}", key, value.simplify());248 }249 }250}