sleigh_rs/semantic/
pattern.rs

1use crate::disassembly::VariableId;
2use crate::semantic::{
3    ContextId, Sleigh as FinalSleigh, TableId, TokenFieldId,
4};
5use crate::{
6    field_in_be, field_in_le, value_in_context, value_in_token, NumberUnsigned,
7    Span,
8};
9
10use super::disassembly::{Assertation, Expr, Variable};
11use super::InstStart;
12
13/// Represent how a bit is limited in a pattern
14#[derive(Clone, Copy, Debug, Default)]
15pub enum BitConstraint {
16    //can have any value
17    #[default]
18    Unrestrained,
19    //only one value possible 0->false, 1->true
20    Defined(bool),
21    //the value is limited depending on other bits.
22    Restrained,
23}
24
25impl BitConstraint {
26    pub fn value(&self) -> Option<bool> {
27        match self {
28            Self::Defined(value) => Some(*value),
29            _ => None,
30        }
31    }
32    pub fn restrained(&self) -> bool {
33        match self {
34            BitConstraint::Unrestrained => false,
35            BitConstraint::Defined(_) | BitConstraint::Restrained => true,
36        }
37    }
38}
39
40#[derive(Clone, Copy, Debug, PartialEq, Eq)]
41pub enum PatternLen {
42    Defined(NumberUnsigned),
43    Range {
44        min: NumberUnsigned,
45        max: NumberUnsigned,
46    },
47    Min(NumberUnsigned),
48}
49
50impl PatternLen {
51    /// new range/defined len for a pattern
52    pub fn new(min: NumberUnsigned, max: NumberUnsigned) -> Self {
53        match min.cmp(&max) {
54            std::cmp::Ordering::Greater => {
55                unreachable!("PatternLen min({}) > max({})", min, max)
56            }
57            std::cmp::Ordering::Equal => Self::Defined(min),
58            std::cmp::Ordering::Less => Self::Range { min, max },
59        }
60    }
61    /// is this pattern can contain itself and grown to infinite
62    pub fn is_recursive(&self) -> bool {
63        matches!(self, Self::Min(_))
64    }
65    /// min size of the token this patterns requires to match
66    pub fn min(&self) -> NumberUnsigned {
67        match self {
68            Self::Min(min)
69            | Self::Defined(min)
70            | Self::Range { min, max: _ } => *min,
71        }
72    }
73    /// max size of the token this patterns requires to match
74    pub fn max(&self) -> Option<NumberUnsigned> {
75        match self {
76            Self::Defined(value) => Some(*value),
77            Self::Range { min: _, max } => Some(*max),
78            Self::Min(_) => None,
79        }
80    }
81    /// token size, if this pattern is non-growing
82    pub fn single_len(&self) -> Option<NumberUnsigned> {
83        match self {
84            Self::Defined(value) => Some(*value),
85            Self::Min(_) | Self::Range { .. } => None,
86        }
87    }
88    /// create a new range calculated from the concatenation of the two original
89    /// ranges
90    pub fn concat(self, other: Self) -> Self {
91        match (self, other) {
92            (Self::Defined(x), Self::Defined(y)) => Self::Defined(x + y),
93            (
94                Self::Defined(ix @ ax) | Self::Range { min: ix, max: ax },
95                Self::Defined(iy @ ay) | Self::Range { min: iy, max: ay },
96            ) => {
97                let min = ix + iy;
98                let max = ax + ay;
99                Self::new(min, max)
100            }
101            (
102                Self::Min(x) | Self::Defined(x) | Self::Range { min: x, .. },
103                Self::Min(y) | Self::Defined(y) | Self::Range { min: y, .. },
104            ) => Self::Min(x + y),
105        }
106    }
107    /// creates a new range that is the greater of the two
108    pub(crate) fn greater(self, other: Self) -> Self {
109        match (self, other) {
110            (Self::Defined(x), Self::Defined(y)) => Self::Defined(x.max(y)),
111            (
112                Self::Defined(ix @ ax) | Self::Range { min: ix, max: ax },
113                Self::Defined(iy @ ay) | Self::Range { min: iy, max: ay },
114            ) => {
115                let min = ix.max(iy);
116                let max = ax.max(ay);
117                Self::new(min, max)
118            }
119            (
120                Self::Min(x) | Self::Defined(x) | Self::Range { min: x, .. },
121                Self::Min(y) | Self::Defined(y) | Self::Range { min: y, .. },
122            ) => Self::Min(x.max(y)),
123        }
124    }
125    /// creates a new range that only include the intersection of the orignal
126    /// ranges
127    pub(crate) fn intersection(self, other: Self) -> Self {
128        match (self, other) {
129            (
130                Self::Defined(ix @ ax) | Self::Range { min: ix, max: ax },
131                Self::Defined(iy @ ay) | Self::Range { min: iy, max: ay },
132            ) => {
133                let min = ix.min(iy);
134                let max = ax.max(ay);
135                Self::new(min, max)
136            }
137            (
138                Self::Min(x) | Self::Defined(x) | Self::Range { min: x, .. },
139                Self::Min(y) | Self::Defined(y) | Self::Range { min: y, .. },
140            ) => Self::Min(x.min(y)),
141        }
142    }
143}
144
145#[derive(Clone, Debug)]
146pub struct ProducedTable {
147    pub table: TableId,
148    pub location: Span,
149    pub always: bool,
150    pub recursive: bool,
151}
152
153#[derive(Clone, Debug)]
154pub struct ProducedTokenField {
155    pub field: TokenFieldId,
156    //if this field is produced explicitly (on pattern) or implicitly deduced
157    //the existence of by the use of it in a desassembly/execution
158    pub source: Option<Span>,
159    pub local: bool,
160}
161
162#[derive(Clone, Debug)]
163pub struct Pattern {
164    pub len: PatternLen,
165    pub disassembly_vars: Box<[Variable]>,
166    pub blocks: Box<[Block]>,
167    pub pos: Box<[Assertation]>,
168}
169
170impl Pattern {
171    pub fn blocks(&self) -> &[Block] {
172        &self.blocks
173    }
174
175    pub fn disassembly_var(&self, id: VariableId) -> &Variable {
176        &self.disassembly_vars[id.0]
177    }
178
179    pub fn disassembly_vars(&self) -> &[Variable] {
180        &self.disassembly_vars
181    }
182
183    pub fn disassembly_pos_match(&self) -> &[Assertation] {
184        &self.pos
185    }
186
187    pub fn produced_tables(&self) -> impl Iterator<Item = &ProducedTable> {
188        self.blocks().iter().flat_map(Block::tables)
189    }
190
191    pub fn produced_token_fields(
192        &self,
193    ) -> impl Iterator<Item = &ProducedTokenField> {
194        self.blocks()
195            .iter()
196            .flat_map(|block| block.token_fields().iter())
197    }
198
199    pub fn variants_num(&self) -> usize {
200        self.blocks
201            .iter()
202            .fold(1, |acc, block| acc * block.variants_number())
203    }
204
205    pub fn bits_produced(&self) -> usize {
206        let len = self.len.single_len().unwrap_or_else(|| self.len.min());
207        usize::try_from(len).unwrap() * 8
208    }
209
210    pub(crate) fn constraint(
211        &self,
212        sleigh: &FinalSleigh,
213        variant_id: usize,
214        context: &mut [BitConstraint],
215        constraint: &mut [BitConstraint],
216    ) -> Option<()> {
217        let mut current = constraint;
218        for block in self.blocks.iter() {
219            block.constraint(sleigh, variant_id, context, current);
220            let next_offset = block.bits_produced();
221            current = &mut current[next_offset..];
222        }
223        Some(())
224    }
225
226    /// the bit pattern for all variants.
227    pub(crate) fn pattern_bits_variants<'a>(
228        &'a self,
229        sleigh: &'a FinalSleigh,
230    ) -> impl Iterator<Item = (usize, Vec<BitConstraint>, Vec<BitConstraint>)> + 'a
231    {
232        let context_bits =
233            usize::try_from(sleigh.context_memory.memory_bits).unwrap();
234        let pattern_bits = self.bits_produced();
235        let mut context_buf = vec![BitConstraint::default(); context_bits];
236        let mut pattern_buf = vec![BitConstraint::default(); pattern_bits];
237        (0..self.variants_num()).into_iter().filter_map(move |i| {
238            context_buf.fill(BitConstraint::default());
239            pattern_buf.fill(BitConstraint::default());
240            self.constraint(sleigh, i, &mut context_buf, &mut pattern_buf)?;
241            Some((i, context_buf.clone(), pattern_buf.clone()))
242        })
243    }
244}
245
246#[derive(Clone, Debug)]
247pub enum Block {
248    And {
249        len: PatternLen,
250        token_fields: Box<[ProducedTokenField]>,
251        tables: Box<[ProducedTable]>,
252        verifications: Box<[Verification]>,
253        pre: Box<[Assertation]>,
254        pos: Box<[Assertation]>,
255        /// zero means it's the first in the chain
256        variants_prior: usize,
257        /// number of variants this block produce
258        variants_number: usize,
259    },
260    //TODO `OR` block can produce token_fields?
261    Or {
262        len: PatternLen,
263        token_fields: Box<[ProducedTokenField]>,
264        tables: Box<[ProducedTable]>,
265        branches: Box<[Verification]>,
266        pos: Box<[Assertation]>,
267        /// zero means it's the first in the chain
268        variants_prior: usize,
269        /// number of variants this block produce
270        variants_number: usize,
271    },
272}
273impl Block {
274    pub fn tables(&self) -> &[ProducedTable] {
275        match self {
276            Block::And { tables, .. } | Block::Or { tables, .. } => tables,
277        }
278    }
279    pub fn token_fields(&self) -> &[ProducedTokenField] {
280        match self {
281            Block::And { token_fields, .. }
282            | Block::Or { token_fields, .. } => token_fields,
283        }
284    }
285    pub fn len(&self) -> PatternLen {
286        match self {
287            Block::And { len, .. } | Block::Or { len, .. } => *len,
288        }
289    }
290    pub fn verifications(&self) -> &[Verification] {
291        match self {
292            Block::And { verifications, .. }
293            | Block::Or {
294                branches: verifications,
295                ..
296            } => verifications,
297        }
298    }
299
300    fn variants_number(&self) -> usize {
301        match self {
302            Block::And {
303                variants_number, ..
304            }
305            | Block::Or {
306                variants_number, ..
307            } => *variants_number,
308        }
309    }
310
311    fn bits_produced(&self) -> usize {
312        let len = self.len().single_len().unwrap_or_else(|| self.len().min());
313        usize::try_from(len).unwrap() * 8
314    }
315
316    fn constraint(
317        &self,
318        sleigh: &FinalSleigh,
319        variant_id: usize,
320        context_bits: &mut [BitConstraint],
321        constraint_bits: &mut [BitConstraint],
322    ) -> Option<()> {
323        match self {
324            Self::And { verifications, .. } => {
325                for verification in verifications.iter() {
326                    apply_verification(
327                        sleigh,
328                        variant_id,
329                        verification,
330                        context_bits,
331                        constraint_bits,
332                    )?;
333                }
334                Some(())
335            }
336            Self::Or {
337                branches,
338                variants_prior,
339                variants_number,
340                ..
341            } => {
342                //find the correct verification in the OR to constraint
343                let mut verification_id =
344                    (variant_id / variants_prior) % variants_number;
345                for branch in branches.iter() {
346                    let verification_variants = branch.variants_number();
347                    if verification_id < verification_variants {
348                        return apply_verification(
349                            sleigh,
350                            variant_id,
351                            branch,
352                            context_bits,
353                            constraint_bits,
354                        );
355                    }
356                    verification_id -= verification_variants;
357                }
358                unreachable!()
359            }
360        }
361    }
362}
363
364fn apply_verification(
365    sleigh: &FinalSleigh,
366    variant_id: usize,
367    verification: &Verification,
368    context_bits: &mut [BitConstraint],
369    constraint_bits: &mut [BitConstraint],
370) -> Option<()> {
371    match verification {
372        Verification::TableBuild { .. } => Some(()),
373        Verification::ContextCheck { context, op, value } => {
374            let bits = sleigh.context_memory.context(*context);
375            super::inner::pattern::apply_value(
376                context_bits,
377                field_in_le,
378                value_in_context,
379                bits,
380                *op,
381                value,
382            )
383        }
384        Verification::TokenFieldCheck { field, op, value } => {
385            let token_field = sleigh.token_field(*field);
386            let token = sleigh.token(token_field.token);
387            let token_len: usize = token.len_bytes.get().try_into().unwrap();
388            let bit_order = match token.endian {
389                crate::Endian::Little => field_in_le,
390                crate::Endian::Big => field_in_be,
391            };
392            super::inner::pattern::apply_value(
393                &mut constraint_bits[0..token_len * 8],
394                bit_order,
395                value_in_token,
396                token_field.bits.clone(),
397                *op,
398                value,
399            )
400        }
401        Verification::SubPattern { pattern, .. } => pattern.constraint(
402            sleigh,
403            variant_id,
404            context_bits,
405            constraint_bits,
406        ),
407    }
408}
409
410#[derive(Clone, Debug)]
411pub enum Verification {
412    ContextCheck {
413        context: ContextId,
414        op: CmpOp,
415        value: ConstraintValue,
416    },
417    TableBuild {
418        produced_table: ProducedTable,
419        verification: Option<(CmpOp, ConstraintValue)>,
420    },
421    TokenFieldCheck {
422        field: TokenFieldId,
423        op: CmpOp,
424        value: ConstraintValue,
425    },
426    SubPattern {
427        location: Span,
428        pattern: Pattern,
429    },
430}
431impl Verification {
432    pub fn variants_number(&self) -> usize {
433        match self {
434            Self::SubPattern { pattern, .. } => pattern.variants_num(),
435            _ => 1,
436        }
437    }
438}
439
440#[derive(Clone, Debug)]
441pub enum ConstraintField {
442    TokenField(TokenFieldId),
443    Context(ContextId),
444    InstStart(InstStart),
445    Table(TableId),
446}
447
448#[derive(Clone, Debug)]
449pub struct ConstraintValue {
450    expr: Expr,
451}
452
453impl ConstraintValue {
454    pub(crate) fn new(expr: Expr) -> Self {
455        Self { expr }
456    }
457    pub fn expr(&self) -> &Expr {
458        &self.expr
459    }
460}
461
462#[derive(Clone, Copy, Debug, Eq, PartialEq)]
463pub enum CmpOp {
464    Eq,
465    Ne,
466    Lt,
467    Gt,
468    Le,
469    Ge,
470}
471
472#[derive(Clone, Copy, Debug, Eq, PartialEq)]
473pub enum Ellipsis {
474    Left,
475    Right,
476}
sleigh_rs/semantic/pattern.rs

sleigh_rs/semantic/
pattern.rs
