1use crate::bits;
2use crate::deserialise::parse::XmlExt;
3use crate::deserialise::Error as DeserialiseError;
4use crate::disassembly::error::Error;
5use crate::disassembly::symbol::{Symbol, SymbolTable};
6use crate::disassembly::walker::ParserWalker;
7
8use std::mem::size_of;
9use std::ops::Range;
10
11#[derive(Debug, Clone, PartialEq, Eq, serde::Deserialize, serde::Serialize)]
12pub enum PatternExpression {
13 TokenField {
14 big_endian: bool,
15 sign_bit: bool,
16 bit_start: usize,
17 bit_end: usize,
18 byte_start: usize,
19 byte_end: usize,
20 shift: u32,
21 },
22 ContextField {
23 sign_bit: bool,
24 bit_start: usize,
25 bit_end: usize,
26 byte_start: usize,
27 byte_end: usize,
28 shift: u32,
29 },
30 Constant {
31 value: i64,
32 },
33 Operand {
34 index: usize,
35 table_id: usize,
36 constructor_id: usize,
37 },
38 StartInstruction,
39 EndInstruction,
40 Next2Instruction,
41 Plus(Box<Self>, Box<Self>),
42 Sub(Box<Self>, Box<Self>),
43 Mult(Box<Self>, Box<Self>),
44 LeftShift(Box<Self>, Box<Self>),
45 RightShift(Box<Self>, Box<Self>),
46 And(Box<Self>, Box<Self>),
47 Or(Box<Self>, Box<Self>),
48 Xor(Box<Self>, Box<Self>),
49 Div(Box<Self>, Box<Self>),
50 Minus(Box<Self>),
51 Not(Box<Self>),
52}
53
54impl PatternExpression {
55 pub fn min_value(&self) -> Option<i64> {
56 match self {
57 Self::TokenField { .. }
58 | Self::ContextField { .. }
59 | Self::StartInstruction
60 | Self::EndInstruction
61 | Self::Next2Instruction => Some(0),
62 Self::Constant { value, .. } => Some(*value),
63 _ => None,
64 }
65 }
66
67 pub fn max_value(&self) -> Option<i64> {
68 match self {
69 Self::TokenField {
70 bit_start, bit_end, ..
71 }
72 | Self::ContextField {
73 bit_start, bit_end, ..
74 } => {
75 Some(bits::zero_extend(!0i64, bit_end - bit_start))
77 }
78 Self::StartInstruction | Self::EndInstruction | Self::Next2Instruction => Some(0),
79 Self::Constant { value, .. } => Some(*value),
80 _ => None,
81 }
82 }
83
84 pub fn value_with<'b, 'c, 'z>(
85 &'b self,
86 walker: &mut ParserWalker<'b, 'c, 'z>,
87 symbols: &'b SymbolTable,
88 ) -> Result<(i64, Option<Range<u32>>), Error> {
89 Ok(match self {
90 Self::TokenField {
91 big_endian,
92 sign_bit,
93 bit_start,
94 bit_end,
95 byte_start,
96 byte_end,
97 shift,
98 } => {
99 let size = byte_end - byte_start + 1;
100 let mut res = 0i64;
101 let mut start = *byte_start as isize;
102 let mut tsize = size as isize;
103
104 while tsize >= size_of::<u32>() as isize {
105 let tmp = walker.instruction_bytes(start as usize, size_of::<u32>())?;
106 res = res.checked_shl(8 * size_of::<u32>() as u32).unwrap_or(0);
107 res = (res as u64 | tmp as u64) as i64;
108 start += size_of::<u32>() as isize;
109 tsize = (*byte_end as isize) - start + 1;
110 }
111 if tsize > 0 {
112 let tmp = walker.instruction_bytes(start as usize, tsize as usize)?;
113 res = res.checked_shl(8 * tsize as u32).unwrap_or(0);
114 res = (res as u64 | tmp as u64) as i64;
115 }
116
117 res = if !big_endian {
118 bits::byte_swap(res, size)
119 } else {
120 res
121 };
122 res = res
123 .checked_shr(*shift)
124 .unwrap_or(if res < 0 { -1 } else { 0 });
125
126 let value = if *sign_bit {
127 bits::sign_extend(res, bit_end - bit_start)
128 } else {
129 bits::zero_extend(res, bit_end - bit_start)
130 };
131
132 let offset = (*byte_start + unsafe { walker.offset(None) }) as u32 * 8;
133 let end_offset = size as u32 * 8;
134
135 (
136 value,
137 Some(
138 offset + end_offset - (*bit_end as u32 + 1)
139 ..offset + end_offset - *bit_start as u32,
140 ),
141 )
142 }
143 Self::ContextField {
144 sign_bit,
145 bit_start,
146 bit_end,
147 byte_start,
148 byte_end,
149 shift,
150 } => {
151 let mut res = 0i64;
152 let mut size = (*byte_end as isize) - (*byte_start as isize) + 1;
153 let mut start = *byte_start as isize;
154
155 while size >= size_of::<u32>() as isize {
156 let tmp = walker.context_bytes(start as usize, size_of::<u32>());
157 res = res.checked_shl(8 * size_of::<u32>() as u32).unwrap_or(0);
158 res = (res as u64 | tmp as u64) as i64;
159 start += size_of::<u32>() as isize;
160 size = (*byte_end as isize) - start + 1;
161 }
162 if size > 0 {
163 let tmp = walker.context_bytes(start as usize, size as usize);
164 res = res.checked_shl(8 * size as u32).unwrap_or(0);
165 res = (res as u64 | tmp as u64) as i64;
166 }
167
168 res = res
169 .checked_shr(*shift)
170 .unwrap_or(if res < 0 { -1 } else { 0 });
171
172 let value = if *sign_bit {
173 bits::sign_extend(res, bit_end - bit_start)
174 } else {
175 bits::zero_extend(res, bit_end - bit_start)
176 };
177
178 let offset = (*byte_start + unsafe { walker.offset(None) }) as u32 * 8;
179 let end_offset = size as u32 * 8;
180
181 (
182 value,
183 Some(
184 offset + end_offset - (*bit_end as u32 + 1)
185 ..offset + end_offset - *bit_start as u32,
186 ),
187 )
188 }
189 Self::Constant { value } => (*value, None),
190 Self::Operand {
191 table_id,
192 constructor_id,
193 index,
194 } => {
195 let table = unsafe { symbols.unchecked_symbol(*table_id) };
196 let ctor = if let Symbol::Subtable { constructors, .. } = table {
197 unsafe { constructors.get_unchecked(*constructor_id) }
198 } else {
199 unreachable!()
200 };
202
203 let pexp = if let Symbol::Operand {
204 def_expr,
205 subsym_id,
206 ..
207 } = unsafe { symbols.unchecked_symbol(ctor.operand(*index)) }
208 {
209 if let Some(def_expr) = def_expr {
210 def_expr
211 } else if let Some(subsym_id) = subsym_id {
212 let sym = unsafe { symbols.unchecked_symbol(*subsym_id) };
213 sym.pattern_value()
214 } else {
215 return Ok((0, None));
216 }
217 } else {
218 unreachable!()
219 };
221
222 let (value, bits) =
223 unsafe { walker.resolve_with_bits(pexp, ctor, *index, symbols)? };
224 (
225 value,
226 bits.map(|r| {
227 let offset = 0; r.start + offset..r.end + offset
229 }),
230 )
231 }
232 Self::StartInstruction => (walker.address().offset() as i64, None),
233 Self::EndInstruction => (
234 walker
235 .next_address()
236 .map(|a| a.offset() as i64)
237 .unwrap_or(0),
238 None,
239 ),
240 Self::Next2Instruction => (
241 walker
242 .next2_address()
243 .map(|a| a.offset() as i64)
244 .unwrap_or(0),
245 None,
246 ),
247 Self::Plus(ref lhs, ref rhs) => {
248 let (l, m) = lhs.value_with(walker, symbols)?;
249 let (r, n) = rhs.value_with(walker, symbols)?;
250
251 (
252 l.wrapping_add(r),
253 match (m, n) {
254 (None, v) | (v, None) => v,
255 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
256 },
257 )
258 }
259 Self::Sub(ref lhs, ref rhs) => {
260 let (l, m) = lhs.value_with(walker, symbols)?;
261 let (r, n) = rhs.value_with(walker, symbols)?;
262
263 (
264 l.wrapping_sub(r),
265 match (m, n) {
266 (None, v) | (v, None) => v,
267 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
268 },
269 )
270 }
271 Self::Mult(ref lhs, ref rhs) => {
272 let (l, m) = lhs.value_with(walker, symbols)?;
273 let (r, n) = rhs.value_with(walker, symbols)?;
274
275 (
276 l.wrapping_mul(r),
277 match (m, n) {
278 (None, v) | (v, None) => v,
279 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
280 },
281 )
282 }
283 Self::LeftShift(ref lhs, ref rhs) => {
284 let (l, m) = lhs.value_with(walker, symbols)?;
285 let (r, n) = rhs.value_with(walker, symbols)?;
286
287 (
288 l.checked_shl(r as u8 as u32).unwrap_or(0),
289 match (m, n) {
290 (None, v) | (v, None) => v,
291 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
292 },
293 )
294 }
295 Self::RightShift(ref lhs, ref rhs) => {
296 let (l, m) = lhs.value_with(walker, symbols)?;
297 let (r, n) = rhs.value_with(walker, symbols)?;
298
299 (
300 l.checked_shr(r as u8 as u32)
301 .unwrap_or(if l < 0 { -1 } else { 0 }),
302 match (m, n) {
303 (None, v) | (v, None) => v,
304 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
305 },
306 )
307 }
308 Self::And(ref lhs, ref rhs) => {
309 let (l, m) = lhs.value_with(walker, symbols)?;
310 let (r, n) = rhs.value_with(walker, symbols)?;
311
312 (
313 l & r,
314 match (m, n) {
315 (None, v) | (v, None) => v,
316 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
317 },
318 )
319 }
320 Self::Or(ref lhs, ref rhs) => {
321 let (l, m) = lhs.value_with(walker, symbols)?;
322 let (r, n) = rhs.value_with(walker, symbols)?;
323
324 (
325 l | r,
326 match (m, n) {
327 (None, v) | (v, None) => v,
328 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
329 },
330 )
331 }
332 Self::Xor(ref lhs, ref rhs) => {
333 let (l, m) = lhs.value_with(walker, symbols)?;
334 let (r, n) = rhs.value_with(walker, symbols)?;
335
336 (
337 l ^ r,
338 match (m, n) {
339 (None, v) | (v, None) => v,
340 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
341 },
342 )
343 }
344 Self::Div(ref lhs, ref rhs) => {
345 let (l, m) = lhs.value_with(walker, symbols)?;
346 let (r, n) = rhs.value_with(walker, symbols)?;
347
348 (
349 l.wrapping_div(r),
350 match (m, n) {
351 (None, v) | (v, None) => v,
352 (Some(r1), Some(r2)) => Some(r1.start.min(r2.start)..r1.end.max(r2.end)),
353 },
354 )
355 }
356 Self::Minus(ref operand) => {
357 let (operand, m) = operand.value_with(walker, symbols)?;
358 (-operand, m)
359 }
360 Self::Not(ref operand) => {
361 let (operand, m) = operand.value_with(walker, symbols)?;
362 (!operand, m)
363 }
364 })
365 }
366
367 pub fn value<'b, 'c, 'z>(
368 &'b self,
369 walker: &mut ParserWalker<'b, 'c, 'z>,
370 symbols: &'b SymbolTable,
371 ) -> Result<i64, Error> {
372 Ok(match self {
373 Self::TokenField {
374 big_endian,
375 sign_bit,
376 bit_start,
377 bit_end,
378 byte_start,
379 byte_end,
380 shift,
381 } => {
382 let size = byte_end - byte_start + 1;
383 let mut res = 0i64;
384 let mut start = *byte_start as isize;
385 let mut tsize = size as isize;
386
387 while tsize >= size_of::<u32>() as isize {
388 let tmp = walker.instruction_bytes(start as usize, size_of::<u32>())?;
389 res = res.checked_shl(8 * size_of::<u32>() as u32).unwrap_or(0);
390 res = (res as u64 | tmp as u64) as i64;
391 start += size_of::<u32>() as isize;
392 tsize = (*byte_end as isize) - start + 1;
393 }
394 if tsize > 0 {
395 let tmp = walker.instruction_bytes(start as usize, tsize as usize)?;
396 res = res.checked_shl(8 * tsize as u32).unwrap_or(0);
397 res = (res as u64 | tmp as u64) as i64;
398 }
399
400 res = if !big_endian {
401 bits::byte_swap(res, size)
402 } else {
403 res
404 };
405 res = res
406 .checked_shr(*shift)
407 .unwrap_or(if res < 0 { -1 } else { 0 });
408
409 if *sign_bit {
410 bits::sign_extend(res, bit_end - bit_start)
411 } else {
412 bits::zero_extend(res, bit_end - bit_start)
413 }
414 }
415 Self::ContextField {
416 sign_bit,
417 bit_start,
418 bit_end,
419 byte_start,
420 byte_end,
421 shift,
422 } => {
423 let mut res = 0i64;
424 let mut size = (*byte_end as isize) - (*byte_start as isize) + 1;
425 let mut start = *byte_start as isize;
426
427 while size >= size_of::<u32>() as isize {
428 let tmp = walker.context_bytes(start as usize, size_of::<u32>());
429 res = res.checked_shl(8 * size_of::<u32>() as u32).unwrap_or(0);
430 res = (res as u64 | tmp as u64) as i64;
431 start += size_of::<u32>() as isize;
432 size = (*byte_end as isize) - start + 1;
433 }
434 if size > 0 {
435 let tmp = walker.context_bytes(start as usize, size as usize);
436 res = res.checked_shl(8 * size as u32).unwrap_or(0);
437 res = (res as u64 | tmp as u64) as i64;
438 }
439
440 res = res
441 .checked_shr(*shift)
442 .unwrap_or(if res < 0 { -1 } else { 0 });
443
444 if *sign_bit {
445 bits::sign_extend(res, bit_end - bit_start)
446 } else {
447 bits::zero_extend(res, bit_end - bit_start)
448 }
449 }
450 Self::Constant { value } => *value,
451 Self::Operand {
452 table_id,
453 constructor_id,
454 index,
455 } => {
456 let table = unsafe { symbols.unchecked_symbol(*table_id) };
457 let ctor = if let Symbol::Subtable { constructors, .. } = table {
458 unsafe { constructors.get_unchecked(*constructor_id) }
459 } else {
460 unreachable!()
461 };
463
464 let pexp = if let Symbol::Operand {
465 def_expr,
466 subsym_id,
467 ..
468 } = unsafe { symbols.unchecked_symbol(ctor.operand(*index)) }
469 {
470 if let Some(def_expr) = def_expr {
471 def_expr
472 } else if let Some(subsym_id) = subsym_id {
473 let sym = unsafe { symbols.unchecked_symbol(*subsym_id) };
474 sym.pattern_value()
475 } else {
476 return Ok(0);
477 }
478 } else {
479 unreachable!()
480 };
482
483 unsafe { walker.resolve_with(pexp, ctor, *index, symbols)? }
484 }
485 Self::StartInstruction => walker.address().offset() as i64,
486 Self::EndInstruction => walker
487 .next_address()
488 .map(|a| a.offset() as i64)
489 .unwrap_or(0),
490 Self::Next2Instruction => walker
491 .next2_address()
492 .map(|a| a.offset() as i64)
493 .unwrap_or(0),
494 Self::Plus(ref lhs, ref rhs) => lhs
495 .value(walker, symbols)?
496 .wrapping_add(rhs.value(walker, symbols)?),
497 Self::Sub(ref lhs, ref rhs) => lhs
498 .value(walker, symbols)?
499 .wrapping_sub(rhs.value(walker, symbols)?),
500 Self::Mult(ref lhs, ref rhs) => lhs
501 .value(walker, symbols)?
502 .wrapping_mul(rhs.value(walker, symbols)?),
503 Self::LeftShift(ref lhs, ref rhs) => {
504 let l = lhs.value(walker, symbols)?;
505 let r = rhs.value(walker, symbols)?;
506
507 l.checked_shl(r as u8 as u32).unwrap_or(0)
508 }
509 Self::RightShift(ref lhs, ref rhs) => {
510 let l = lhs.value(walker, symbols)?;
511 let r = rhs.value(walker, symbols)?;
512
513 l.checked_shr(r as u8 as u32)
514 .unwrap_or(if l < 0 { -1 } else { 0 })
515 }
516 Self::And(ref lhs, ref rhs) => {
517 lhs.value(walker, symbols)? & rhs.value(walker, symbols)?
518 }
519 Self::Or(ref lhs, ref rhs) => {
520 lhs.value(walker, symbols)? | rhs.value(walker, symbols)?
521 }
522 Self::Xor(ref lhs, ref rhs) => {
523 lhs.value(walker, symbols)? ^ rhs.value(walker, symbols)?
524 }
525 Self::Div(ref lhs, ref rhs) => lhs
526 .value(walker, symbols)?
527 .wrapping_div(rhs.value(walker, symbols)?),
528 Self::Minus(ref operand) => -operand.value(walker, symbols)?,
529 Self::Not(ref operand) => !operand.value(walker, symbols)?,
530 })
531 }
532
533 pub fn from_xml(input: xml::Node) -> Result<Self, DeserialiseError> {
534 Ok(match input.tag_name().name() {
535 "tokenfield" => Self::TokenField {
536 big_endian: input.attribute_bool("bigendian")?,
537 sign_bit: input.attribute_bool("signbit")?,
538 bit_start: input.attribute_int("bitstart")?,
539 bit_end: input.attribute_int("bitend")?,
540 byte_start: input.attribute_int("bytestart")?,
541 byte_end: input.attribute_int("byteend")?,
542 shift: input.attribute_int("shift")?,
543 },
544 "contextfield" => Self::ContextField {
545 sign_bit: input.attribute_bool("signbit")?,
546 bit_start: input.attribute_int("startbit")?,
547 bit_end: input.attribute_int("endbit")?,
548 byte_start: input.attribute_int("startbyte")?,
549 byte_end: input.attribute_int("endbyte")?,
550 shift: input.attribute_int("shift")?,
551 },
552 "intb" => Self::Constant {
553 value: input.attribute_int("val")?,
554 },
555 "operand_exp" => Self::Operand {
556 index: input.attribute_int("index")?,
557 table_id: input.attribute_int("table")?,
558 constructor_id: input.attribute_int("ct")?,
559 },
560 "start_exp" => Self::StartInstruction,
561 "end_exp" => Self::EndInstruction,
562 "next2_exp" => Self::EndInstruction,
563 "plus_exp" => {
564 let mut children = input.children().filter(xml::Node::is_element);
565 Self::Plus(
566 Box::new(Self::from_xml(children.next().ok_or_else(|| {
567 DeserialiseError::Invariant("missing lhs of binary expression")
568 })?)?),
569 Box::new(Self::from_xml(children.next().ok_or_else(|| {
570 DeserialiseError::Invariant("missing rhs of binary expression")
571 })?)?),
572 )
573 }
574 "sub_exp" => {
575 let mut children = input.children().filter(xml::Node::is_element);
576 Self::Sub(
577 Box::new(Self::from_xml(children.next().ok_or_else(|| {
578 DeserialiseError::Invariant("missing lhs of binary expression")
579 })?)?),
580 Box::new(Self::from_xml(children.next().ok_or_else(|| {
581 DeserialiseError::Invariant("missing rhs of binary expression")
582 })?)?),
583 )
584 }
585 "mult_exp" => {
586 let mut children = input.children().filter(xml::Node::is_element);
587 Self::Mult(
588 Box::new(Self::from_xml(children.next().ok_or_else(|| {
589 DeserialiseError::Invariant("missing lhs of binary expression")
590 })?)?),
591 Box::new(Self::from_xml(children.next().ok_or_else(|| {
592 DeserialiseError::Invariant("missing rhs of binary expression")
593 })?)?),
594 )
595 }
596 "lshift_exp" => {
597 let mut children = input.children().filter(xml::Node::is_element);
598 Self::LeftShift(
599 Box::new(Self::from_xml(children.next().ok_or_else(|| {
600 DeserialiseError::Invariant("missing lhs of binary expression")
601 })?)?),
602 Box::new(Self::from_xml(children.next().ok_or_else(|| {
603 DeserialiseError::Invariant("missing rhs of binary expression")
604 })?)?),
605 )
606 }
607 "rshift_exp" => {
608 let mut children = input.children().filter(xml::Node::is_element);
609 Self::RightShift(
610 Box::new(Self::from_xml(children.next().ok_or_else(|| {
611 DeserialiseError::Invariant("missing lhs of binary expression")
612 })?)?),
613 Box::new(Self::from_xml(children.next().ok_or_else(|| {
614 DeserialiseError::Invariant("missing rhs of binary expression")
615 })?)?),
616 )
617 }
618 "and_exp" => {
619 let mut children = input.children().filter(xml::Node::is_element);
620 Self::And(
621 Box::new(Self::from_xml(children.next().ok_or_else(|| {
622 DeserialiseError::Invariant("missing lhs of binary expression")
623 })?)?),
624 Box::new(Self::from_xml(children.next().ok_or_else(|| {
625 DeserialiseError::Invariant("missing rhs of binary expression")
626 })?)?),
627 )
628 }
629 "or_exp" => {
630 let mut children = input.children().filter(xml::Node::is_element);
631 Self::Or(
632 Box::new(Self::from_xml(children.next().ok_or_else(|| {
633 DeserialiseError::Invariant("missing lhs of binary expression")
634 })?)?),
635 Box::new(Self::from_xml(children.next().ok_or_else(|| {
636 DeserialiseError::Invariant("missing rhs of binary expression")
637 })?)?),
638 )
639 }
640 "xor_exp" => {
641 let mut children = input.children().filter(xml::Node::is_element);
642 Self::Xor(
643 Box::new(Self::from_xml(children.next().ok_or_else(|| {
644 DeserialiseError::Invariant("missing lhs of binary expression")
645 })?)?),
646 Box::new(Self::from_xml(children.next().ok_or_else(|| {
647 DeserialiseError::Invariant("missing rhs of binary expression")
648 })?)?),
649 )
650 }
651 "div_exp" => {
652 let mut children = input.children().filter(xml::Node::is_element);
653 Self::Div(
654 Box::new(Self::from_xml(children.next().ok_or_else(|| {
655 DeserialiseError::Invariant("missing lhs of binary expression")
656 })?)?),
657 Box::new(Self::from_xml(children.next().ok_or_else(|| {
658 DeserialiseError::Invariant("missing rhs of binary expression")
659 })?)?),
660 )
661 }
662 "minus_exp" => {
663 let mut children = input.children().filter(xml::Node::is_element);
664 Self::Minus(Box::new(Self::from_xml(children.next().ok_or_else(
665 || DeserialiseError::Invariant("missing operand of unary expression"),
666 )?)?))
667 }
668 "not_exp" => {
669 let mut children = input.children().filter(xml::Node::is_element);
670 Self::Not(Box::new(Self::from_xml(children.next().ok_or_else(
671 || DeserialiseError::Invariant("missing operand of unary expression"),
672 )?)?))
673 }
674 name => return Err(DeserialiseError::TagUnexpected(name.to_owned())),
675 })
676 }
677}