yaxpeax_core/analyses/
mod.rs

1use yaxpeax_arch::Arch;
2use data::ValueLocations;
3
4#[macro_use]
5pub mod control_flow;
6pub mod data_flow;
7pub mod function_signatures;
8pub mod memory_layout;
9pub mod static_single_assignment;
10pub mod xrefs;
11pub mod evaluators;
12pub mod value_range;
13
14pub enum CompletionStatus {
15    Incomplete,
16    Complete,
17}
18
19pub struct ValueRes<V> {
20    pub value: V,
21    pub carry: V,
22}
23
24#[allow(dead_code)]
25impl<V: Value> ValueRes<V> {
26    pub(crate) fn from_zero() -> Self {
27        ValueRes::literal(V::from_const(0))
28    }
29    pub(crate) fn literal(value: V) -> Self {
30        ValueRes {
31            value,
32            carry: V::from_const(0),
33        }
34    }
35    pub(crate) fn unknown() -> Self {
36        ValueRes {
37            value: V::unknown(),
38            carry: V::unknown(),
39        }
40    }
41    pub(crate) fn parts(self) -> (V, V) {
42        (self.value, self.carry)
43    }
44    pub(crate) fn value(self) -> V {
45        self.value
46    }
47    pub(crate) fn carry(self) -> V {
48        self.carry
49    }
50    pub(crate) fn zero(&self) -> V {
51        self.value.eq(&V::from_const(0))
52    }
53    pub(crate) fn sign(&self) -> V {
54        self.value.lt(&V::from_const(0))
55    }
56}
57
58/// interface to query a data flow graph (dfg). this interface is .... in flux.
59///
60/// TODOs in order of "how hard i think they are":
61/// * it should be possible to look up a def site for a value
62/// * it should be possible to iterate the use sites of a value
63/// * perhaps it should be possible to insert new values to the dfg? optionally? this approaches
64/// supporting general patching
65/// * it should be possible to detach and move values
66///
67/// conceptually, these graphs have vertices at places where values are read or written, edges
68/// from uses to some write, and a value associated with the write describing what subsequent reads
69/// will see. these graphs describe the relation between values in a machine with
70/// architecture-defined locations for values to exist. in many cases these graphs are operated on
71/// in a manner consistent with the most atomic changes for a given architcture - typically an
72/// instruction's execution. in an ideal world, this means `DFG` would have vertices at a pair
73/// `(A::Address, A::Instruction, A::Location)`; "at a given address in memory, with a
74/// corresponding instruction, the value at a specific architectural location is ___".
75///
76/// why is using an `(Address, Location)` pair, like `(0x1234, rdi)` not sufficient to uniquely
77/// identify a location? because, dear reader, data at an address is not constant. if you decode
78/// data at address `0x1234`, is that before or after relocations are applied? if that address is
79/// known to be modified after loading, is the instruction there before or after the modification?
80/// different answers to this temporal question mean the architectural locations referenced by the
81/// corresponding instruction can be totally different!
82///
83/// so, really, a `DFG` describes the architectural state of a program at every discrete point of
84/// change for any point in the program. an eventual TODO is to key on `(Address, Generation)`
85/// where a "Generation" describes some series of memory edits. this is approximately supported in
86/// SSA-based DFG construction, where `Memory` is a single architectural location that can be
87/// versioned - perhaps "the program" may be inferred to a distinct memory region from
88/// unknown-destination memorry accesses by default? in a way, a `DFG` might be self-describing if
89/// at some location `(0x1234, Gen1)` the instruction modifies code memory by writing `(0x1236,
90/// Gen2)`, where finding bytes to decode the next instruction would have to be a DFG query? this
91/// suggests that in the most precise case, a DFG might be backed by a `MemoryRepr` with a series
92/// of edits for each generation layered on top? it's not clear how this might interact with
93/// disjoint memory regions that are versioned independently.
94pub trait DFG<V: Value, A: Arch + ValueLocations, When=<A as Arch>::Address> where When: Copy {
95    type Indirect: IndirectQuery<V>;
96
97    fn read_loc(&self, when: When, loc: A::Location) -> V;
98    fn read<T: ToDFGLoc<A::Location>>(&self, when: When, loc: &T) -> V {
99        self.read_loc(when, loc.convert())
100    }
101    fn write_loc(&mut self, when: When, loc: A::Location, value: V);
102    fn write<T: ToDFGLoc<A::Location>>(&mut self, when: When, loc: &T, value: V) {
103        self.write_loc(when, loc.convert(), value)
104    }
105    // in an ideal world with a GAT-enabled rustc, `Indirect` would be spelled as
106    // ```
107    // type Indirect<'dfg>: IndirectQuery<'dfg>;
108    // ```
109    // and could retain a `&'dfg mut DFG` to do queries through. because we do not have GAT, that
110    // associated type cannot be written, and we must obligate `Self::Indirect` and DFG impls to
111    // holding `Rc<RefCell<IndirectionStruct>>` even though we know no user of a `DFG` interface
112    // can get multiple refs, let alone mutable refs.
113    fn indirect_loc(&self, _when: When, _loc: A::Location) -> Self::Indirect;
114    fn indirect<T: ToDFGLoc<A::Location>>(&self, when: When, loc: &T) -> Self::Indirect {
115        self.indirect_loc(when, loc.convert())
116    }
117    fn query_at(&self, when: When) -> DFGLocationQueryCursor<When, V, A, Self> {
118        DFGLocationQueryCursor {
119            dfg: self,
120            addr: when,
121            _a: std::marker::PhantomData,
122            _v: std::marker::PhantomData,
123        }
124    }
125    fn query_at_mut(&mut self, when: When) -> DFGLocationQueryCursorMut<When, V, A, Self> {
126        DFGLocationQueryCursorMut {
127            dfg: self,
128            addr: when,
129            _a: std::marker::PhantomData,
130            _v: std::marker::PhantomData,
131        }
132    }
133}
134
135pub struct DFGLocationQueryCursor<'dfg, K: Copy + Sized, V: Value, A: Arch + ValueLocations, D: DFG<V, A, K> + ?Sized> {
136    dfg: &'dfg D,
137    addr: K,
138    _a: std::marker::PhantomData<A>,
139    _v: std::marker::PhantomData<V>,
140}
141
142pub struct DFGLocationQueryCursorMut<'dfg, K: Copy + Sized, V: Value, A: Arch + ValueLocations, D: DFG<V, A, K> + ?Sized> {
143    dfg: &'dfg mut D,
144    addr: K,
145    _a: std::marker::PhantomData<A>,
146    _v: std::marker::PhantomData<V>,
147}
148
149impl<'dfg, K: Copy, V: Value, A: Arch + ValueLocations, D: DFG<V, A, K> + ?Sized> DFGLocationQuery<V, A> for DFGLocationQueryCursor<'dfg, K, V, A, D> {
150    type Indirect = D::Indirect;
151
152    fn read_loc(&self, loc: A::Location) -> V {
153        self.dfg.read_loc(self.addr, loc)
154    }
155    fn read<T: ToDFGLoc<A::Location>>(&self, loc: &T) -> V {
156        self.read_loc(loc.convert())
157    }
158    fn indirect_loc(&self, loc: A::Location) -> Self::Indirect {
159        self.dfg.indirect_loc(self.addr, loc)
160    }
161    fn indirect<T: ToDFGLoc<A::Location>>(&self, loc: &T) -> Self::Indirect {
162        self.indirect_loc(loc.convert())
163    }
164}
165impl<'dfg, K: Copy, V: Value, A: Arch + ValueLocations, D: DFG<V, A, K> + ?Sized> DFGLocationQuery<V, A> for DFGLocationQueryCursorMut<'dfg, K, V, A, D> {
166    type Indirect = D::Indirect;
167
168    fn read_loc(&self, loc: A::Location) -> V {
169        self.dfg.read_loc(self.addr, loc)
170    }
171    fn read<T: ToDFGLoc<A::Location>>(&self, loc: &T) -> V {
172        self.read_loc(loc.convert())
173    }
174    fn indirect_loc(&self, loc: A::Location) -> Self::Indirect {
175        self.dfg.indirect_loc(self.addr, loc)
176    }
177    fn indirect<T: ToDFGLoc<A::Location>>(&self, loc: &T) -> Self::Indirect {
178        self.indirect_loc(loc.convert())
179    }
180}
181impl<'dfg, K: Copy, V: Value, A: Arch + ValueLocations, D: DFG<V, A, K> + ?Sized> DFGLocationQueryMut<V, A> for DFGLocationQueryCursorMut<'dfg, K, V, A, D> {
182    fn write_loc(&mut self, loc: A::Location, value: V) {
183        self.dfg.write_loc(self.addr, loc, value)
184    }
185    fn write<T: ToDFGLoc<A::Location>>(&mut self, loc: &T, value: V) {
186        self.write_loc(loc.convert(), value)
187    }
188}
189
190/// it's relatively common to want to query a dfg at one address, for multiple values/read-write
191/// accesses. `DFGLocationQuery` is essentially a helper to curry a specific address for future
192/// queries.
193pub trait DFGLocationQuery<V: Value, A: Arch + ValueLocations> where Self: Sized {
194    type Indirect: IndirectQuery<V>;
195
196    fn read_loc(&self, loc: A::Location) -> V;
197    fn read<T: ToDFGLoc<A::Location>>(&self, loc: &T) -> V {
198        self.read_loc(loc.convert())
199    }
200    fn indirect_loc(&self, loc: A::Location) -> Self::Indirect;
201    fn indirect<T: ToDFGLoc<A::Location>>(&self, loc: &T) -> Self::Indirect {
202        self.indirect_loc(loc.convert())
203    }
204}
205
206pub trait DFGLocationQueryMut<V: Value, A: Arch + ValueLocations> where Self: Sized + DFGLocationQuery<V, A> {
207    fn write_loc(&mut self, loc: A::Location, value: V);
208    fn write<T: ToDFGLoc<A::Location>>(&mut self, loc: &T, value: V) {
209        self.write_loc(loc.convert(), value)
210    }
211}
212
213pub trait ToDFGLoc<U> {
214    fn convert(&self) -> U;
215}
216
217impl<T: Clone> ToDFGLoc<T> for T {
218    fn convert(&self) -> T {
219        self.to_owned()
220    }
221}
222
223impl<'a, T: Clone> ToDFGLoc<T> for &'a T {
224    fn convert(&self) -> T {
225        self.to_owned().to_owned()
226    }
227}
228
229#[derive(Copy, Clone, Debug)]
230pub struct ValueIndex<'v, V: ?Sized> {
231    pub base: &'v V,
232    pub size: usize,
233}
234
235impl<'v, V: ?Sized + crate::analyses::static_single_assignment::DataDisplay<'v, 'static>> fmt::Display for ValueIndex<'v, V> {
236    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
237        write!(f, "[{}, width: {}]", self.base.display(false, None), self.size)
238    }
239}
240
241pub trait IntoValueIndex {
242    fn byte(&self) -> ValueIndex<Self> {
243        ValueIndex {
244            base: self,
245            size: 1,
246        }
247    }
248
249    fn word(&self) -> ValueIndex<Self> {
250        ValueIndex {
251            base: self,
252            size: 2,
253        }
254    }
255
256    fn dword(&self) -> ValueIndex<Self> {
257        ValueIndex {
258            base: self,
259            size: 4,
260        }
261    }
262
263    fn qword(&self) -> ValueIndex<Self> {
264        ValueIndex {
265            base: self,
266            size: 8,
267        }
268    }
269
270    fn width(&self, size: usize) -> ValueIndex<Self> {
271        ValueIndex {
272            base: self,
273            size,
274        }
275    }
276}
277
278impl <T: Value> IntoValueIndex for T {}
279
280pub trait IndirectQuery<V> {
281    /// attempt to load `address` indirectly through this value, indexed by `address`.
282    ///
283    /// ## panics
284    ///
285    /// * if `self` does not represent a value that can be indexed. for example, the value backing
286    /// a register can probably not be indexed. the value backing main memory probably can be
287    /// indexed.
288    fn load(&self, _address: ValueIndex<V>) -> V;
289
290    /// attempt to load `address` indirectly through this value, indexed by `address`.
291    ///
292    /// ## panics
293    ///
294    /// * if `self` does not represent a value that can be indexed. for example, the value backing
295    /// a register can probably not be indexed. the value backing main memory probably can be
296    /// indexed.
297    fn store(&self, _address: ValueIndex<V>, _value: &V);
298
299    /// check if `address` is a load known to this query cursor. get the referenced value if so,
300    /// `None` if not.
301    ///
302    /// ## panics
303    ///
304    /// * if `self` does not represent a value that can be indexed. for example, the value backing
305    /// a register can probably not be indexed. the value backing main memory probably can be
306    /// indexed.
307    fn try_get_load(&self, _address: ValueIndex<V>) -> Option<V>;
308
309    /// check if `address` is a store known to this query cursor. `Some(())` if it is, `None` if not.
310    ///
311    /// ## panics
312    ///
313    /// * if `self` does not represent a value that can be indexed. for example, the value backing
314    /// a register can probably not be indexed. the value backing main memory probably can be
315    /// indexed.
316    fn try_get_store(&self, _address: ValueIndex<V>) -> Option<()>;
317}
318
319pub struct OpaqueIndirection<V> {
320    _marker: std::marker::PhantomData<V>,
321}
322
323impl<V> OpaqueIndirection<V> {
324    pub fn inst() -> Self {
325        OpaqueIndirection {
326            _marker: std::marker::PhantomData
327        }
328    }
329}
330
331
332impl<V: Value> IndirectQuery<V> for OpaqueIndirection<V> {
333    fn load(&self, _: ValueIndex<V>) -> V {
334        V::unknown()
335    }
336
337    fn store(&self, _: ValueIndex<V>, _: &V) { }
338
339    fn try_get_load(&self, _: ValueIndex<V>) -> Option<V> {
340        None
341    }
342
343    fn try_get_store(&self, _: ValueIndex<V>) -> Option<()> {
344        None
345    }
346}
347
348pub trait Value: Sized {
349//    type Indirect: IndirectQuery<Self>; // associated type defaults are unstable, but should be `= OpaqueIndirection<V>`
350
351    fn unknown() -> Self;
352
353    fn from_const(_c: i64) -> Self {
354        Self::unknown()
355    }
356
357    fn from_set(xs: &[Self]) -> Self;
358
359    fn to_const(&self) -> Option<i64>;
360
361    fn as_bool(&self) -> Option<bool> {
362        self.ne(&Value::from_const(0)).to_const().map(|x| x != 0)
363    }
364
365    fn add(&self, _other: &Self) -> ValueRes<Self> {
366        ValueRes::unknown()
367    }
368
369    fn sub(&self, _other: &Self) -> ValueRes<Self> {
370        ValueRes::unknown()
371    }
372
373    fn mul(&self, _other: &Self) -> ValueRes<Self> {
374        ValueRes::unknown()
375    }
376
377    fn or(&self, _other: &Self) -> ValueRes<Self> {
378        ValueRes::unknown()
379    }
380
381    fn and(&self, _other: &Self) -> ValueRes<Self> {
382        ValueRes::unknown()
383    }
384
385    fn xor(&self, _other: &Self) -> ValueRes<Self> {
386        ValueRes::unknown()
387    }
388
389    fn modulo(&self, other: &Self) -> Self {
390        match (self.to_const(), other.to_const()) {
391            (Some(x), Some(y)) => {
392                Value::from_const(x % y)
393            }
394            _ => {
395                Self::unknown()
396            }
397        }
398    }
399
400    fn ne(&self, _other: &Self) -> Self {
401        Self::unknown()
402    }
403
404    fn le(&self, _other: &Self) -> Self {
405        Self::unknown()
406    }
407
408    fn lt(&self, other: &Self) -> Self {
409        self.le(other).and(&self.eq(other).not()).value()
410    }
411
412    fn gte(&self, other: &Self) -> Self {
413        self.lt(other).not()
414    }
415
416    fn eq(&self, _other: &Self) -> Self {
417        Self::unknown()
418    }
419
420    fn not(&self) -> Self {
421        Self::unknown()
422    }
423
424    fn sxt(&self, _width: &Self) -> Self {
425        Self::unknown()
426    }
427
428    fn zxt(&self, _width: &Self) -> Self {
429        Self::unknown()
430    }
431
432    fn shr(&self, _amt: &Self) -> Self {
433        Self::unknown()
434    }
435
436    fn sar(&self, _width: &Self) -> Self {
437        Self::unknown()
438    }
439
440    fn shl(&self, _width: &Self) -> Self {
441        Self::unknown()
442    }
443
444    fn sal(&self, _width: &Self) -> Self {
445        Self::unknown()
446    }
447
448    fn rcl(&self, _width: &Self) -> Self {
449        Self::unknown()
450    }
451
452    fn rcr(&self, _width: &Self) -> Self {
453        Self::unknown()
454    }
455
456    fn rol(&self, _width: &Self) -> Self {
457        Self::unknown()
458    }
459
460    fn ror(&self, _width: &Self) -> Self {
461        Self::unknown()
462    }
463}
464
465use SSAValues;
466use std::rc::Rc;
467use analyses::static_single_assignment::{DataDisplay, DFGRef};
468use crate::ColorSettings;
469use data::types::TypeSpec;
470
471#[derive(Debug, Eq, Hash, PartialEq)]
472pub struct Item<Leaf> {
473    pub ty: Option<TypeSpec>,
474    pub value: Expression<Leaf>,
475}
476
477pub struct ItemDisplay<'data, 'colors, Leaf> where Leaf: DataDisplay<'data, 'colors> {
478    data: &'data Rc<Item<Leaf>>,
479    detailed: bool,
480    colors: Option<&'colors ColorSettings>,
481}
482
483impl<'data, 'colors, Leaf: 'data + DataDisplay<'data, 'colors>> DataDisplay<'data, 'colors> for Rc<Item<Leaf>> {
484    type Displayer = ItemDisplay<'data, 'colors, Leaf>;
485    fn display(&'data self, detailed: bool, colors: Option<&'colors ColorSettings>) -> Self::Displayer {
486        ItemDisplay {
487            data: self,
488            detailed,
489            colors
490        }
491    }
492}
493
494impl<'data, 'colors, Leaf: 'data + DataDisplay<'data, 'colors>> fmt::Display for ItemDisplay<'data, 'colors, Leaf> {
495    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
496        if let Some(ty) = self.data.ty.as_ref() {
497            write!(f, "({}: {:?})", self.data.value.display(self.detailed, self.colors), ty)
498        } else {
499            write!(f, "{}", self.data.value.display(self.detailed, self.colors))
500        }
501    }
502}
503
504impl<Leaf: fmt::Display> fmt::Display for Item<Leaf> {
505    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
506        fmt::Display::fmt(&self.value, f)
507    }
508}
509
510impl<A: SSAValues> Item<ValueOrImmediate<A>> where A::Data: Eq + fmt::Display {
511    pub fn immediate(v: i64) -> Rc<Self> {
512        Self::untyped(Expression::value(ValueOrImmediate::Immediate(v)))
513    }
514}
515
516use analyses::memory_layout::Underlying;
517impl<A: SSAValues> Item<ValueOrImmediate<A>> where A::Data: Underlying<Arch=A> + Eq + fmt::Display {
518    pub fn dealiased(&self) -> Rc<Self> {
519        let ty = self.ty.clone();
520        let value = self.value.dealiased();
521        Rc::new(Item { ty, value })
522    }
523}
524
525impl<A: SSAValues> Item<ValueOrImmediate<A>> where A::Data: Eq + fmt::Display{
526}
527
528impl<Leaf> Item<Leaf> {
529    pub fn untyped(value: Expression<Leaf>) -> Rc<Self> {
530        Rc::new(Item {
531            ty: None,
532            value,
533        })
534    }
535
536    pub fn opaque(ty: TypeSpec) -> Rc<Self> {
537        Rc::new(Item {
538            ty: Some(ty),
539            value: Expression::unknown()
540        })
541    }
542
543    pub fn unknown() -> Rc<Self> {
544        Self::untyped(Expression::unknown())
545    }
546
547    pub fn value(leaf: Leaf) -> Rc<Self> {
548        Self::untyped(Expression::value(leaf))
549    }
550
551    pub fn loadb(self: &Rc<Self>) -> Rc<Self> {
552        self.load(1)
553    }
554
555    pub fn loadw(self: &Rc<Self>) -> Rc<Self> {
556        self.load(2)
557    }
558
559    pub fn loadd(self: &Rc<Self>) -> Rc<Self> {
560        self.load(4)
561    }
562
563    pub fn loadq(self: &Rc<Self>) -> Rc<Self> {
564        self.load(8)
565    }
566
567    pub fn load(self: &Rc<Self>, size: u8) -> Rc<Self> {
568        Self::untyped(Expression::Load { address: Rc::clone(self), size })
569    }
570
571    pub fn add(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
572        Self::untyped(Expression::Add { left: Rc::clone(self), right: Rc::clone(other) })
573    }
574
575    pub fn sub(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
576        Self::untyped(Expression::Sub { left: Rc::clone(self), right: Rc::clone(other) })
577    }
578
579    pub fn mul(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
580        Self::untyped(Expression::Mul { left: Rc::clone(self), right: Rc::clone(other) })
581    }
582
583    pub fn or(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
584        Self::untyped(Expression::Or { left: Rc::clone(self), right: Rc::clone(other) })
585    }
586
587    pub fn and(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
588        Self::untyped(Expression::And { left: Rc::clone(self), right: Rc::clone(other) })
589    }
590
591    pub fn xor(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
592        Self::untyped(Expression::Xor { left: Rc::clone(self), right: Rc::clone(other) })
593    }
594
595    pub fn shl(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
596        Self::untyped(Expression::Shl { value: Rc::clone(self), amount: Rc::clone(other) })
597    }
598
599    pub fn shr(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
600        Self::untyped(Expression::Shr { value: Rc::clone(self), amount: Rc::clone(other) })
601    }
602}
603
604/// a very literal construction of `Value` operations into an expression tree. if `Leaf` is only
605/// concrete values, this is suitable for computation. if `Leaf` can be abstract variables, this is
606/// becomes a symbolic expression tree. realistically these expressions are often a mix of the two;
607/// constants from immediates and variables from the rest of the program.
608#[derive(Debug, Eq, Hash, PartialEq)]
609pub enum Expression<Leaf> {
610    Unknown,
611    Value(Leaf),
612    Load { address: Rc<Item<Leaf>>, size: u8 },
613    // TODO: should there be a corresponding "store"?
614    // Store { address: Rc<Item<Leaf>>, size: u8, value: Rc<Item<Leaf>> },
615    Add { left: Rc<Item<Leaf>>, right: Rc<Item<Leaf>> },
616    Sub { left: Rc<Item<Leaf>>, right: Rc<Item<Leaf>> },
617    Mul { left: Rc<Item<Leaf>>, right: Rc<Item<Leaf>> },
618    Or { left: Rc<Item<Leaf>>, right: Rc<Item<Leaf>> },
619    And { left: Rc<Item<Leaf>>, right: Rc<Item<Leaf>> },
620    Xor { left: Rc<Item<Leaf>>, right: Rc<Item<Leaf>> },
621    Shl { value: Rc<Item<Leaf>>, amount: Rc<Item<Leaf>> },
622    Shr { value: Rc<Item<Leaf>>, amount: Rc<Item<Leaf>> },
623}
624
625pub struct ExpressionDisplay<'data, 'colors, Leaf: DataDisplay<'data, 'colors>> {
626    data: &'data Expression<Leaf>,
627    detailed: bool,
628    colors: Option<&'colors ColorSettings>,
629}
630
631impl<'data, 'colors, Leaf: 'data + DataDisplay<'data, 'colors>> DataDisplay<'data, 'colors> for Expression<Leaf> {
632    type Displayer = ExpressionDisplay<'data, 'colors, Leaf>;
633    fn display(&'data self, detailed: bool, colors: Option<&'colors ColorSettings>) -> Self::Displayer {
634        ExpressionDisplay {
635            data: self,
636            detailed,
637            colors
638        }
639    }
640}
641
642impl<'data, 'colors, Leaf: 'data + DataDisplay<'data, 'colors>> fmt::Display for ExpressionDisplay<'data, 'colors, Leaf> {
643    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
644        match self.data {
645            Expression::Unknown => {
646                write!(f, "<unknown>")
647            }
648            Expression::Value(l) => {
649                write!(f, "{}", l.display(self.detailed, self.colors))
650            }
651            Expression::Load { address, size } => {
652                write!(f, "[{}:{}]", address.display(self.detailed, self.colors), size)
653            }
654            Expression::Add { left, right } => {
655                write!(f, "({} + {})", left.display(self.detailed, self.colors), right.display(self.detailed, self.colors))
656            }
657            Expression::Sub { left, right } => {
658                write!(f, "({} - {})", left.display(self.detailed, self.colors), right.display(self.detailed, self.colors))
659            }
660            Expression::Mul { left, right } => {
661                write!(f, "({} * {})", left.display(self.detailed, self.colors), right.display(self.detailed, self.colors))
662            }
663            Expression::Or { left, right } => {
664                write!(f, "({} | {})", left.display(self.detailed, self.colors), right.display(self.detailed, self.colors))
665            }
666            Expression::And { left, right } => {
667                write!(f, "({} & {})", left.display(self.detailed, self.colors), right.display(self.detailed, self.colors))
668            }
669            Expression::Xor { left, right } => {
670                write!(f, "({} ^ {})", left.display(self.detailed, self.colors), right.display(self.detailed, self.colors))
671            }
672            Expression::Shl { value, amount } => {
673                write!(f, "({} << {})", value.display(self.detailed, self.colors), amount.display(self.detailed, self.colors))
674            }
675            Expression::Shr { value, amount } => {
676                write!(f, "({} >> {})", value.display(self.detailed, self.colors), amount.display(self.detailed, self.colors))
677            }
678        }
679    }
680}
681
682impl<Leaf: fmt::Display> fmt::Display for Expression<Leaf> {
683    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
684        match self {
685            Expression::Unknown => {
686                write!(f, "<unknown>")
687            }
688            Expression::Value(l) => {
689                write!(f, "{}", l)
690            }
691            Expression::Load { address, size } => {
692                write!(f, "[{}:{}]", address, size)
693            }
694            Expression::Add { left, right } => {
695                write!(f, "({} + {})", left, right)
696            }
697            Expression::Sub { left, right } => {
698                write!(f, "({} - {})", left, right)
699            }
700            Expression::Mul { left, right } => {
701                write!(f, "({} * {})", left, right)
702            }
703            Expression::Or { left, right } => {
704                write!(f, "({} | {})", left, right)
705            }
706            Expression::And { left, right } => {
707                write!(f, "({} & {})", left, right)
708            }
709            Expression::Xor { left, right } => {
710                write!(f, "({} ^ {})", left, right)
711            }
712            Expression::Shl { value, amount } => {
713                write!(f, "({} << {})", value, amount)
714            }
715            Expression::Shr { value, amount } => {
716                write!(f, "({} >> {})", value, amount)
717            }
718        }
719    }
720}
721
722impl<T: SSAValues> Expression<ValueOrImmediate<T>> where T::Data: Eq + fmt::Display {
723    pub fn as_immediate(&self) -> Option<i64> {
724        if let Expression::Value(ValueOrImmediate::Immediate(i)) = self {
725            Some(*i)
726        } else {
727            None
728        }
729    }
730}
731
732impl<A: SSAValues> Expression<ValueOrImmediate<A>> where A::Data: Underlying<Arch=A> + Eq + fmt::Display {
733    pub fn dealiased(&self) -> Self {
734        match self {
735            Expression::Unknown => Expression::Unknown,
736            Expression::Value(ValueOrImmediate::Immediate(i)) => Expression::Value(ValueOrImmediate::Immediate(*i)),
737            Expression::Value(ValueOrImmediate::Value(v)) => {
738                if let Some(underlying) = v.borrow().data.as_ref().and_then(|x| x.underlying()) {
739                    Expression::Value(ValueOrImmediate::Value(underlying))
740                } else {
741                    Expression::Value(ValueOrImmediate::Value(Rc::clone(v)))
742                }
743            }
744            Expression::Load { address, size } => Expression::Load { address: address.dealiased(), size: *size },
745            Expression::Add { left, right } => Expression::Add {
746                left: left.dealiased(), right: right.dealiased(),
747            },
748            Expression::Sub { left, right } => Expression::Sub {
749                left: left.dealiased(), right: right.dealiased(),
750            },
751            Expression::Mul { left, right } => Expression::Mul {
752                left: left.dealiased(), right: right.dealiased(),
753            },
754            Expression::Or { left, right } => Expression::Or {
755                left: left.dealiased(), right: right.dealiased(),
756            },
757            Expression::And { left, right } => Expression::And {
758                left: left.dealiased(), right: right.dealiased(),
759            },
760            Expression::Xor { left, right } => Expression::Xor {
761                left: left.dealiased(), right: right.dealiased(),
762            },
763            Expression::Shl { value, amount } => Expression::Shl {
764                value: value.dealiased(), amount: amount.dealiased(),
765            },
766            Expression::Shr { value, amount } => Expression::Shr {
767                value: value.dealiased(), amount: amount.dealiased(),
768            },
769        }
770    }
771}
772
773impl<Leaf> Expression<Leaf> {
774    pub fn unknown() -> Self {
775        Self::Unknown
776    }
777
778    pub fn value(leaf: Leaf) -> Self {
779        Self::Value(leaf)
780    }
781
782    /*
783    pub fn add(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
784        Rc::new(Expression::Add { left: Rc::clone(self), right: Rc::clone(other) })
785    }
786
787    pub fn sub(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
788        Rc::new(Expression::Sub { left: Rc::clone(self), right: Rc::clone(other) })
789    }
790
791    pub fn mul(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
792        Rc::new(Expression::Mul { left: Rc::clone(self), right: Rc::clone(other) })
793    }
794
795    pub fn or(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
796        Rc::new(Expression::Or { left: Rc::clone(self), right: Rc::clone(other) })
797    }
798
799    pub fn and(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
800        Rc::new(Expression::And { left: Rc::clone(self), right: Rc::clone(other) })
801    }
802
803    pub fn xor(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
804        Rc::new(Expression::Xor { left: Rc::clone(self), right: Rc::clone(other) })
805    }
806
807    pub fn shl(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
808        Rc::new(Expression::Shl { value: Rc::clone(self), amount: Rc::clone(other) })
809    }
810
811    pub fn shr(self: &Rc<Self>, other: &Rc<Self>) -> Rc<Self> {
812        Rc::new(Expression::Shr { value: Rc::clone(self), amount: Rc::clone(other) })
813    }
814    */
815}
816
817use std::hash::Hash;
818use std::hash::Hasher;
819pub enum ValueOrImmediate<A: SSAValues> where A::Data: Eq + fmt::Display {
820    Immediate(i64),
821    Value(DFGRef<A>),
822}
823
824impl<A: SSAValues> ValueOrImmediate<A> where A::Data: Eq + fmt::Display {
825    pub fn immediate(v: i64) -> Expression<Self> {
826        Expression::value(ValueOrImmediate::Immediate(v))
827    }
828
829    fn name(&self) -> String {
830        match self {
831            ValueOrImmediate::Immediate(v) => {
832                format!("{}", v)
833            }
834            ValueOrImmediate::Value(v) => {
835                let version_string = match v.borrow().version {
836                    Some(v) => { v.to_string() },
837                    None => "input".to_string()
838                };
839                if let Some(_data) = v.borrow().data.as_ref() {
840                    format!("{:?}_{}", v.borrow().location, version_string)
841                } else {
842                    format!("{:?}_{}", v.borrow().location, version_string)
843                }
844            }
845        }
846    }
847}
848
849use std::fmt;
850impl<A: SSAValues> fmt::Debug for ValueOrImmediate<A> where A::Data: Eq + fmt::Display {
851    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
852        match self {
853            ValueOrImmediate::Immediate(v) => {
854                write!(f, "Immediate({})", v)
855            }
856            ValueOrImmediate::Value(v) => {
857                write!(f, "Value({:?})", v)
858            }
859        }
860    }
861}
862
863impl<A: SSAValues> fmt::Display for ValueOrImmediate<A> where A::Data: Eq + fmt::Display {
864    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
865        match self {
866            ValueOrImmediate::Immediate(v) => {
867                write!(f, "{}", v)
868            }
869            ValueOrImmediate::Value(v) => {
870                let version_string = match v.borrow().version {
871                    Some(v) => { v.to_string() },
872                    None => "input".to_string()
873                };
874                if let Some(data) = v.borrow().data.as_ref() {
875                    write!(f, "{} ({:?}_{})", data, v.borrow().location, version_string)
876                } else {
877                    write!(f, "<unknown value> ({:?}_{})", v.borrow().location, version_string)
878                }
879            }
880        }
881    }
882}
883
884pub struct LeafDisplay<'data, 'colors, A: SSAValues> where A::Data: Eq + fmt::Display {
885    data: &'data ValueOrImmediate<A>,
886    detailed: bool,
887    colors: Option<&'colors ColorSettings>,
888}
889
890impl<'data, 'colors, A: 'data + SSAValues> DataDisplay<'data, 'colors> for ValueOrImmediate<A> where A::Data: Eq + fmt::Display {
891    type Displayer = LeafDisplay<'data, 'colors, A>;
892    fn display(&'data self, detailed: bool, colors: Option<&'colors ColorSettings>) -> Self::Displayer {
893        LeafDisplay {
894            data: self,
895            detailed,
896            colors
897        }
898    }
899}
900
901impl<'data, 'colors, A: SSAValues> fmt::Display for LeafDisplay<'data, 'colors, A> where A::Data: Eq + fmt::Display {
902    fn fmt(&self, f: &mut fmt::Formatter) -> fmt::Result {
903        match &self.data {
904            ValueOrImmediate::Immediate(i) => {
905                // TODO: signed hex
906                write!(f, "{:#x}", i)
907            }
908            ValueOrImmediate::Value(v) => {
909                fmt::Display::fmt(&v.borrow().display(self.detailed, self.colors), f)
910            }
911        }
912    }
913}
914
915
916impl<A: SSAValues> Eq for ValueOrImmediate<A> where A::Data: Eq + fmt::Display { }
917impl<A: SSAValues> PartialEq for ValueOrImmediate<A> where A::Data: Eq + fmt::Display {
918    fn eq(&self, other: &Self) -> bool {
919        match (self, other) {
920            (ValueOrImmediate::Immediate(l), ValueOrImmediate::Immediate(r)) => {
921                l == r
922            }
923            (ValueOrImmediate::Value(l), ValueOrImmediate::Value(r)) => {
924                Rc::ptr_eq(l, r)
925            }
926            _ => {
927                false
928            }
929        }
930    }
931}
932
933impl<A: SSAValues> Clone for ValueOrImmediate<A> where A::Data: Eq + fmt::Display {
934    fn clone(&self) -> Self {
935        match self {
936            ValueOrImmediate::Immediate(v) => {
937                ValueOrImmediate::Immediate(*v)
938            }
939            ValueOrImmediate::Value(v) => {
940                ValueOrImmediate::Value(Rc::clone(v))
941            }
942        }
943    }
944}
945
946impl<A: SSAValues> Hash for ValueOrImmediate<A> where A::Data: Eq + fmt::Display {
947    fn hash<H: Hasher>(&self, state: &mut H) {
948        match self {
949            ValueOrImmediate::Immediate(v) => {
950                state.write_u8(1);
951                state.write_i64(*v);
952            }
953            ValueOrImmediate::Value(value) => {
954                state.write_u8(2);
955                (crate::analyses::static_single_assignment::HashedValue { value: Rc::clone(value) }).hash(state);
956            }
957        }
958    }
959}
960
961use analyses::static_single_assignment::{DFGRebase, DefSource, HashedValue, SSA};
962impl<A: SSAValues + Arch> DFGRebase<A> for Rc<Item<ValueOrImmediate<A>>> where A::Data: Hash + Eq + fmt::Display, A::Location: DFGRebase<A> {
963    fn rebase_references(&self, old_dfg: &SSA<A>, new_dfg: &SSA<A>) -> Self {
964        match &self.value {
965            Expression::Unknown => Item::unknown(),
966            Expression::Value(leaf) => {
967                match leaf {
968                    ValueOrImmediate::Immediate(v) => {
969                        Item::untyped(Expression::Value(ValueOrImmediate::Immediate(*v)))
970                    }
971                    ValueOrImmediate::Value(v) => {
972                        if !new_dfg.defs.contains_key(&HashedValue { value: Rc::clone(v) }) {
973                            let (old_def_addr, old_def_source) = old_dfg.get_def_site(Rc::clone(v));
974                            let new_use = match old_def_source {
975                                DefSource::Instruction => {
976                                    new_dfg.get_use(old_def_addr, v.borrow().location.rebase_references(old_dfg, new_dfg))
977                                        .value
978                                },
979                                DefSource::External => {
980                                    new_dfg.instruction_values.values()
981                                        .find_map(|values| {
982                                            values.iter().find_map(|((loc, dir), dfg_ref)| {
983                                                if dir == &crate::data::Direction::Read && loc == &v.borrow().location && v.borrow().version.is_none() {
984                                                    Some(Rc::clone(dfg_ref))
985                                                } else {
986                                                    None
987                                                }
988                                            })
989                                        })
990                                        .expect(&format!("corresponding external def exists for location {:?}", v.borrow().location))
991                                }
992                                DefSource::Between(addr) => {
993                                    Rc::clone(new_dfg.control_dependent_values
994                                        .get(&old_def_addr).expect("old def addr is valid")
995                                        .get(&addr).expect("between's prior addr is valid")
996                                        .get(&(v.borrow().location.rebase_references(old_dfg, new_dfg), crate::data::Direction::Write))
997                                        .expect("corresponding def exists in new dfg"))
998                                }
999                                other => {
1000                                    panic!("aaaa {}", other);
1001                                }
1002                            };
1003                            Item::untyped(Expression::Value(ValueOrImmediate::Value(new_use)))
1004                        } else {
1005                            Item::untyped(Expression::Value(ValueOrImmediate::Value(Rc::clone(v))))
1006                        }
1007                    }
1008                }
1009            }
1010            Expression::Load { address, size } => {
1011                Item::load(&address.rebase_references(old_dfg, new_dfg), *size)
1012            },
1013            Expression::Add { left, right } => {
1014                Item::add(
1015                    &left.rebase_references(old_dfg, new_dfg),
1016                    &right.rebase_references(old_dfg, new_dfg),
1017                )
1018            },
1019            Expression::Sub { left, right } => {
1020                Item::sub(
1021                    &left.rebase_references(old_dfg, new_dfg),
1022                    &right.rebase_references(old_dfg, new_dfg),
1023                )
1024            },
1025            Expression::Mul { left, right } => {
1026                Item::mul(
1027                    &left.rebase_references(old_dfg, new_dfg),
1028                    &right.rebase_references(old_dfg, new_dfg),
1029                )
1030            },
1031            Expression::Or { left, right } => {
1032                Item::or(
1033                    &left.rebase_references(old_dfg, new_dfg),
1034                    &right.rebase_references(old_dfg, new_dfg),
1035                )
1036            },
1037            Expression::And { left, right } => {
1038                Item::and(
1039                    &left.rebase_references(old_dfg, new_dfg),
1040                    &right.rebase_references(old_dfg, new_dfg),
1041                )
1042            },
1043            Expression::Xor { left, right } => {
1044                Item::xor(
1045                    &left.rebase_references(old_dfg, new_dfg),
1046                    &right.rebase_references(old_dfg, new_dfg),
1047                )
1048            },
1049            Expression::Shl { value, amount } => {
1050                Item::shl(
1051                    &value.rebase_references(old_dfg, new_dfg),
1052                    &amount.rebase_references(old_dfg, new_dfg),
1053                )
1054            },
1055            Expression::Shr { value, amount } => {
1056                Item::shr(
1057                    &value.rebase_references(old_dfg, new_dfg),
1058                    &amount.rebase_references(old_dfg, new_dfg),
1059                )
1060            },
1061        }
1062    }
1063}
1064
1065impl<A: SSAValues> Value for Rc<Item<ValueOrImmediate<A>>> where A::Data: Hash + Eq + fmt::Display {
1066    // type Indirect = OpaqueIndirection<Self>;
1067
1068    fn unknown() -> Self {
1069        Item::untyped(Expression::Unknown)
1070    }
1071
1072    fn from_const(c: i64) -> Self {
1073        Item::untyped(Expression::Value(ValueOrImmediate::Immediate(c)))
1074    }
1075
1076    fn from_set(_xs: &[Self]) -> Self {
1077        // TODO: tag the information loss here
1078        Self::unknown()
1079    }
1080
1081    fn to_const(&self) -> Option<i64> {
1082        if let Expression::Value(ValueOrImmediate::Immediate(c)) = self.as_ref().value {
1083            Some(c)
1084        } else {
1085            None
1086        }
1087    }
1088
1089    fn as_bool(&self) -> Option<bool> {
1090        self.to_const().map(|x| x != 0)
1091    }
1092
1093    fn add(&self, other: &Self) -> ValueRes<Self> {
1094        ValueRes {
1095            value: Item::untyped(Expression::Add { left: Rc::clone(self), right: Rc::clone(other) }),
1096            carry: Self::unknown()
1097        }
1098    }
1099
1100    fn sub(&self, other: &Self) -> ValueRes<Self> {
1101        ValueRes {
1102            value: Item::untyped(Expression::Sub { left: Rc::clone(self), right: Rc::clone(other) }),
1103            carry: Self::unknown()
1104        }
1105    }
1106
1107    fn mul(&self, other: &Self) -> ValueRes<Self> {
1108        ValueRes {
1109            value: Item::untyped(Expression::Mul { left: Rc::clone(self), right: Rc::clone(other) }),
1110            carry: Self::unknown()
1111        }
1112    }
1113
1114    fn or(&self, other: &Self) -> ValueRes<Self> {
1115        ValueRes {
1116            value: Item::untyped(Expression::Or { left: Rc::clone(self), right: Rc::clone(other) }),
1117            carry: Self::unknown()
1118        }
1119    }
1120
1121    fn and(&self, other: &Self) -> ValueRes<Self> {
1122        ValueRes {
1123            value: Item::untyped(Expression::And { left: Rc::clone(self), right: Rc::clone(other) }),
1124            carry: Self::unknown()
1125        }
1126    }
1127
1128    fn xor(&self, other: &Self) -> ValueRes<Self> {
1129        ValueRes {
1130            value: Item::untyped(Expression::Xor { left: Rc::clone(self), right: Rc::clone(other) }),
1131            carry: Self::unknown()
1132        }
1133    }
1134
1135    fn sxt(&self, _width: &Self) -> Self {
1136        Self::unknown()
1137    }
1138
1139    fn zxt(&self, _width: &Self) -> Self {
1140        Self::unknown()
1141    }
1142
1143    fn shr(&self, amount: &Self) -> Self {
1144        Item::untyped(Expression::Shr { value: Rc::clone(self), amount: Rc::clone(amount) })
1145    }
1146
1147    fn shl(&self, amount: &Self) -> Self {
1148        Item::untyped(Expression::Shl { value: Rc::clone(self), amount: Rc::clone(amount) })
1149    }
1150}
yaxpeax_core/analyses/mod.rs

yaxpeax_core/analyses/
mod.rs
