1use std::{u64,i64,cmp};
26use num_traits::Saturating;
27use quickcheck::{Arbitrary,Gen};
28use {Value,Constant,Result};
29
30#[derive(Debug,Clone,PartialEq,Eq)]
32pub enum Constraint {
33 Empty{
35 bits: usize,
37 },
38
39 Unsigned{
41 from: u64,
43 to: u64,
45 bits: usize,
47 },
48
49 Signed{
51 from: i64,
53 to: i64,
55 bits: usize,
57 },
58
59 Full{
61 bits: usize,
63 },
64}
65
66impl Constraint {
67 pub fn new(bits: usize) -> Result<Constraint> {
69 if bits == 0 { return Err("Constraints can't have bits size zero".into()); }
70 Ok(Constraint::Full{ bits: bits })
71 }
72
73 pub fn is_empty(&self) -> bool {
75 if let &Constraint::Empty{ .. } = self { true } else { false }
76 }
77
78 pub fn clamp_lower_bound_unsigned(&mut self, bound: u64) {
80 let bits = self.bits();
81 self.make_unsigned();
82
83 match self {
84 &mut Constraint::Empty{ .. } => { }
85 &mut Constraint::Unsigned{ ref mut from, ref mut to,.. } if *to >= bound =>{
86 *from = cmp::max(bound,*from);
87 *to = cmp::max(bound,*to);
88 }
89 a@&mut Constraint::Unsigned{ .. } => {
90 *a = Constraint::Empty{ bits: bits };
91 }
92 &mut Constraint::Signed{ .. } => { unreachable!() }
93 a@&mut Constraint::Full{ .. } => {
94 *a = Constraint::Unsigned{
95 from: bound,
96 to: u64::MAX >> (64 - cmp::min(64,bits)),
97 bits: bits,
98 };
99 }
100 }
101 }
102
103 pub fn clamp_lower_bound_signed(&mut self, bound: u64) {
105 let bits = self.bits();
106 let missing = u64::MAX << (cmp::min(64,bits) % 64);
107 let sign_bit = 1 << (cmp::min(64,bits) - 1);
108 let bound = if sign_bit & bound != 0 { (bound | missing) as i64 } else { bound as i64 };
109
110 self.make_signed();
111
112 match self {
113 &mut Constraint::Empty{ .. } => { }
114 &mut Constraint::Unsigned{ .. } => { unreachable!() }
115 &mut Constraint::Signed{ ref mut from, ref mut to,.. } if *to < bound =>{
116 *from = cmp::max(bound,*from);
117 *to = cmp::max(bound,*to);
118 }
119 a@&mut Constraint::Signed{ .. } => {
120 *a = Constraint::Empty{ bits: bits };
121 }
122 a@&mut Constraint::Full{ .. } => {
123 *a = Constraint::Signed{
124 from: bound,
125 to: i64::MAX >> (64 - cmp::min(64,bits)),
126 bits: bits,
127 };
128 }
129 }
130 }
131
132 pub fn clamp_upper_bound_unsigned(&mut self, bound: u64) {
134 let bits = self.bits();
135 self.make_unsigned();
136
137 match self {
138 &mut Constraint::Empty{ .. } => { }
139 &mut Constraint::Unsigned{ ref mut from, ref mut to,.. } if *from < bound =>{
140 *from = cmp::min(bound,*from);
141 *to = cmp::min(bound,*to);
142 }
143 a@&mut Constraint::Unsigned{ .. } => {
144 *a = Constraint::Empty{ bits: bits };
145 }
146 &mut Constraint::Signed{ .. } => { unreachable!() }
147 a@&mut Constraint::Full{ .. } => {
148 *a = Constraint::Unsigned{
149 from: 0,
150 to: bound,
151 bits: bits,
152 };
153 }
154 }
155 }
156
157 pub fn clamp_upper_bound_signed(&mut self, bound: u64) {
159 let bits = self.bits();
160 let missing = u64::MAX << (cmp::min(64,bits) % 64);
161 let sign_bit = 1 << (cmp::min(64,bits) - 1);
162 let bound = if sign_bit & bound != 0 { (bound | missing) as i64 } else { bound as i64 };
163
164 self.make_signed();
165
166 match self {
167 &mut Constraint::Empty{ .. } => { }
168 &mut Constraint::Unsigned{ .. } => { unreachable!() }
169 &mut Constraint::Signed{ ref mut from, ref mut to,.. } if *from < bound =>{
170 *from = cmp::min(bound,*from);
171 *to = cmp::min(bound,*to);
172 }
173 a@&mut Constraint::Signed{ .. } => {
174 *a = Constraint::Empty{ bits: bits };
175 }
176 a@&mut Constraint::Full{ .. } => {
177 *a = Constraint::Signed{
178 from: i64::MIN >> (64 - cmp::min(64,bits)),
179 to: bound,
180 bits: bits,
181 };
182 }
183 }
184 }
185
186 pub fn union_with(&mut self, mut other: Self) {
188 match (self.clone(),other.clone()) {
189 (Constraint::Empty{ .. },_) => { }
190 (_,Constraint::Empty{ bits }) => {
191 *self = Constraint::Empty{ bits: bits };
192 }
193 (_,Constraint::Full{ .. }) => { }
194 (Constraint::Full{ .. },a) => {
195 *self = a;
196 }
197 (Constraint::Signed{ from: from_s,.. },Constraint::Unsigned{ .. }) => {
198 if from_s >= 0 {
199 self.make_unsigned();
200 } else {
201 other.make_signed();
202 }
203
204 self.union_with(other);
205 }
206 (Constraint::Unsigned{ .. },Constraint::Signed{ from: from_s,.. }) => {
207 if from_s >= 0 {
208 other.make_unsigned();
209 } else {
210 self.make_signed();
211 }
212
213 self.union_with(other);
214 }
215 (Constraint::Unsigned{ from: from_a, to: to_a,.. },
216 Constraint::Unsigned{ from: from_b, to: to_b, bits: bits_b }) => {
217 let max = u64::MAX >> 64.saturating_sub(bits_b);
218 let from = cmp::min(from_a as u64,from_b);
219 let to = cmp::max(to_a as u64,to_b);
220
221 *self = if from <= to && to <= max {
222 Constraint::Unsigned{
223 from: from,
224 to: to,
225 bits: bits_b,
226 }
227 } else {
228 Constraint::Empty{ bits: bits_b }
229 };
230 }
231 (Constraint::Signed{ from: from_a, to: to_a,.. },
232 Constraint::Signed{ from: from_b, to: to_b, bits: bits_b }) => {
233 let max = (u64::MAX >> 64.saturating_sub(bits_b) + 1) as i64;
234 let from = cmp::min(from_a,from_b);
235 let to = cmp::max(to_a,to_b);
236
237 *self = if from <= to && to <= max {
238 Constraint::Signed{
239 from: from,
240 to: to,
241 bits: bits_b,
242 }
243 } else {
244 Constraint::Empty{ bits: bits_b }
245 };
246 }
247 }
248 }
249
250 pub fn intersect_with(&mut self, mut other: Self) {
252 match (self.clone(),other.clone()) {
253 (Constraint::Empty{ .. },_) => { }
254 (_,Constraint::Empty{ bits }) => {
255 *self = Constraint::Empty{ bits: bits };
256 }
257 (_,Constraint::Full{ .. }) => { }
258 (Constraint::Full{ .. },a) => {
259 *self = a;
260 }
261 (Constraint::Signed{ from: from_s,.. },Constraint::Unsigned{ .. }) |
262 (Constraint::Unsigned{ .. },Constraint::Signed{ from: from_s,.. }) => {
263 if from_s >= 0 {
264 other.make_unsigned();
265 } else {
266 other.make_signed();
267 }
268
269 self.union_with(other);
270 }
271 (Constraint::Unsigned{ from: from_a, to: to_a,.. },
272 Constraint::Unsigned{ from: from_b, to: to_b, bits: bits_b }) => {
273 let max = u64::MAX >> 64.saturating_sub(bits_b);
274 let from = cmp::max(from_a as u64,from_b);
275 let to = cmp::min(to_a as u64,to_b);
276
277 *self = if from <= to && to <= max {
278 Constraint::Unsigned{
279 from: from,
280 to: to,
281 bits: bits_b,
282 }
283 } else {
284 Constraint::Empty{ bits: bits_b }
285 };
286 }
287 (Constraint::Signed{ from: from_a, to: to_a,.. },
288 Constraint::Signed{ from: from_b, to: to_b, bits: bits_b }) => {
289 let max = (u64::MAX >> 64.saturating_sub(bits_b) + 1) as i64;
290 let from = cmp::max(from_a,from_b);
291 let to = cmp::min(to_a,to_b);
292
293 *self = if from <= to && to <= max as i64 {
294 Constraint::Signed{
295 from: from,
296 to: to,
297 bits: bits_b,
298 }
299 } else {
300 Constraint::Empty{ bits: bits_b }
301 };
302 }
303 }
304 }
305
306 pub fn include(&mut self, bound: u64) {
308 match self.clone() {
309 Constraint::Empty{ .. } => { },
310 Constraint::Signed{ .. } => { }
311 Constraint::Unsigned{ bits, from, to } if from <= bound && to >= bound => {
312 *self = Constraint::Unsigned{
313 from: bound,
314 to: bound,
315 bits: bits
316 };
317 }
318 Constraint::Unsigned{ bits,.. } => {
319 *self = Constraint::Empty{ bits: bits }
320 }
321 Constraint::Full{ bits } => {
322 *self = Constraint::Unsigned{
323 from: bound,
324 to: bound,
325 bits: bits
326 };
327 }
328 }
329 }
330
331 pub fn exclude(&mut self, bound: u64) {
333 match self.clone() {
334 Constraint::Empty{ .. } => { },
335 Constraint::Signed{ .. } => { }
336 Constraint::Full{ .. } => { }
337 Constraint::Unsigned{ bits, from, to } if from == bound && to == bound => {
338 *self = Constraint::Empty{ bits: bits }
339 }
340 Constraint::Unsigned{ bits, from, to } if from == bound => {
341 *self = Constraint::Unsigned{
342 from: bound + 1,
343 to: to,
344 bits: bits
345 };
346 }
347 Constraint::Unsigned{ bits, from, to } if to == bound => {
348 *self = Constraint::Unsigned{
349 from: from,
350 to: bound - 1,
351 bits: bits
352 };
353 }
354 Constraint::Unsigned{ .. } => { }
355 }
356 }
357
358 pub fn bits(&self) -> usize {
360 match self {
361 &Constraint::Empty{ bits } => bits,
362 &Constraint::Signed{ bits,.. } => bits,
363 &Constraint::Unsigned{ bits,.. } => bits,
364 &Constraint::Full{ bits } => bits,
365 }
366 }
367
368 pub fn limit(&self, v: Value) -> Value {
370 match v {
371 Value::Undefined => Value::Undefined,
372 Value::Constant(Constant{ value, bits }) => {
373 let svalue = Self::signed(value,bits);
374 match self {
375 &Constraint::Empty{ .. } => Value::Undefined,
376 &Constraint::Unsigned{ ref from, ref to,.. } if *from <= value && *to >= value => {
377 Value::val(value,bits).unwrap()
378 }
379 &Constraint::Unsigned{ .. } => Value::Undefined,
380 &Constraint::Signed{ ref from, ref to,.. } if *from <= svalue && *to >= svalue => {
381 Value::val(value,bits).unwrap()
382 }
383 &Constraint::Signed{ .. } => Value::Undefined,
384 &Constraint::Full{ .. } => Value::val(value,bits).unwrap()
385 }
386 }
387 val@Value::Variable(_) => val,
388 }
389 }
390
391 pub fn signed(value: u64, bits: usize) -> i64 {
393 let missing = if bits < 64 { u64::MAX << bits } else { 0 };
394 let sign_bit = if bits < 64 { 1 << (cmp::min(64,bits) - 1) } else { 0x8000000000000000 };
395 if sign_bit & value != 0 { (value | missing) as i64 } else { value as i64 }
396 }
397
398 pub fn invert(&mut self) {
400 match self.clone() {
401 Constraint::Empty{ bits } => {
402 *self = Constraint::Full{ bits: bits };
403 }
404 Constraint::Full{ bits } => {
405 *self = Constraint::Empty{ bits: bits };
406 }
407 Constraint::Signed{ to, bits,.. } if to >= Self::signed_max(bits) => {
408 *self = Constraint::Signed{
409 from: i64::MIN >> (64 - cmp::min(64,bits)),
410 to: to.saturating_sub(1),
411 bits: bits,
412 };
413 }
414 Constraint::Signed{ from, to, bits } if from <= i64::MIN >> (64 - cmp::min(64,bits)) => {
415 *self = Constraint::Signed{
416 from: to.saturating_add(1),
417 to: i64::MAX >> (64 - cmp::min(64,bits)),
418 bits: bits,
419 };
420 }
421 Constraint::Unsigned{ from, to, bits } if to >= Self::unsigned_max(bits) => {
422 *self = Constraint::Unsigned{
423 from: 0,
424 to: from.saturating_sub(1),
425 bits: bits,
426 };
427 }
428 Constraint::Unsigned{ from, to, bits } if from == 0 => {
429 *self = Constraint::Unsigned{
430 from: to.saturating_add(1),
431 to: u64::MAX >> (64 - cmp::min(64,bits)),
432 bits: bits,
433 };
434 }
435 _ => {
436 *self = Constraint::Full{ bits: self.bits() };
437 }
438 }
439 }
440
441 pub fn inverted(&self) -> Self {
443 let mut r = self.clone();
444 r.invert();
445 r
446 }
447
448 fn make_unsigned(&mut self) {
449 if let Constraint::Signed{ from, to, bits } = self.clone() {
450 let from = cmp::max(0,from) as u64;
451 let to = cmp::max(0,to) as u64;
452
453 *self = if from < to {
454 Constraint::Unsigned{
455 from: from,
456 to: to,
457 bits: bits,
458 }
459 } else {
460 Constraint::Empty{ bits: bits }
461 };
462 }
463 }
464
465 fn make_signed(&mut self) {
466 if let Constraint::Unsigned{ from, to, bits } = self.clone() {
467 let from = cmp::min(u64::MAX >> 1,from) as i64;
468 let to = cmp::min(u64::MAX >> 1,to) as i64;
469
470 *self = if from < to {
471 Constraint::Signed{
472 from: from,
473 to: to,
474 bits: bits,
475 }
476 } else {
477 Constraint::Empty{ bits: bits }
478 };
479 }
480 }
481
482 fn unsigned_max(b: usize) -> u64 {
483 u64::MAX >> (64 - cmp::min(64,b))
484 }
485
486 fn signed_max(b: usize) -> i64 {
487 i64::MAX >> (64 - cmp::min(64,b))
488 }
489}
490
491impl Arbitrary for Constraint {
492 fn arbitrary<G: Gen>(g: &mut G) -> Self {
493 let bits = g.gen_range(0,65);
494
495 match g.gen_range(0, 4) {
496 0 => Constraint::Empty{ bits: bits },
497 1 => {
498 let a = g.gen_range(0,u64::MAX >> cmp::min(63,bits));
499 let b = g.gen_range(0,u64::MAX >> cmp::min(63,bits));
500
501 Constraint::Unsigned{
502 from: cmp::min(a,b),
503 to: cmp::max(a,b),
504 bits: bits
505 }
506 },
507 2 => {
508 let a = g.gen_range(i64::MIN >> cmp::min(63,bits),i64::MAX >> cmp::min(63,bits));
509 let b = g.gen_range(i64::MIN >> cmp::min(63,bits),i64::MAX >> cmp::min(63,bits));
510
511 Constraint::Signed{
512 from: cmp::min(a,b),
513 to: cmp::max(a,b),
514 bits: bits,
515 }
516 }
517 3 => Constraint::Full{ bits: bits },
518 _ => { unreachable!() }
519 }
520 }
521}
522
523#[cfg(test)]
524mod tests {
525 use super::*;
526
527 #[test]
528 fn constraint_include() {
529 let mut c1 = Constraint::new(16).unwrap();
530
531 c1.include(42);
532 assert_eq!(c1, Constraint::Unsigned{ from: 42, to: 42, bits: 16 });
533
534 c1.include(41);
535 assert_eq!(c1, Constraint::Empty{ bits: 16 });
536 }
537
538 #[test]
539 fn constraint_lower_bound_unsigned() {
540 let mut c1 = Constraint::new(16).unwrap();
541
542 c1.clamp_lower_bound_unsigned(23);
543 assert_eq!(c1, Constraint::Unsigned{ from: 23, to: 0xFFFF, bits: 16 });
544
545 c1.clamp_lower_bound_unsigned(42);
546 assert_eq!(c1, Constraint::Unsigned{ from: 42, to: 0xFFFF, bits: 16 });
547
548 c1.clamp_lower_bound_unsigned(23);
549 assert_eq!(c1, Constraint::Unsigned{ from: 42, to: 0xFFFF, bits: 16 });
550 }
551
552 #[test]
553 fn constraint_lower_bound_signed() {
554 let mut c1 = Constraint::new(16).unwrap();
555
556 c1.clamp_lower_bound_signed(23);
557 assert_eq!(c1, Constraint::Signed{ from: 23, to: 0x7FFF, bits: 16 });
558
559 c1.clamp_lower_bound_unsigned(42);
560 assert_eq!(c1, Constraint::Unsigned{ from: 42, to: 0x7FFF, bits: 16 });
561
562 c1.clamp_lower_bound_unsigned(23);
563 assert_eq!(c1, Constraint::Unsigned{ from: 42, to: 0x7FFF, bits: 16 });
564 }
565
566 #[test]
567 fn constraint_lower_bound_mixed() {
568 let mut c1 = Constraint::new(16).unwrap();
569
570 c1.clamp_lower_bound_signed(0xffe9);
572 assert_eq!(c1, Constraint::Signed{ from: -23, to: 0x7FFF, bits: 16 });
573
574 c1.clamp_lower_bound_unsigned(23);
575 assert_eq!(c1, Constraint::Unsigned{ from: 23, to: 0x7FFF, bits: 16 });
576 }
577 #[test]
578 fn constraint_upper_bound_unsigned() {
579 let mut c1 = Constraint::new(16).unwrap();
580
581 c1.clamp_upper_bound_unsigned(0x1337);
582 assert_eq!(c1, Constraint::Unsigned{ from: 0, to: 0x1337, bits: 16 });
583
584 c1.clamp_lower_bound_unsigned(0x100);
585 assert_eq!(c1, Constraint::Unsigned{ from: 0x100, to: 0x1337, bits: 16 });
586
587 c1.clamp_lower_bound_unsigned(0x1337);
588 assert_eq!(c1, Constraint::Unsigned{ from: 0x1337, to: 0x1337, bits: 16 });
589 }
590
591 #[test]
592 fn constraint_upper_bound_signed() {
593 let mut c1 = Constraint::new(16).unwrap();
594
595 c1.clamp_upper_bound_signed(42);
596 assert_eq!(c1, Constraint::Signed{ from: -0x8000, to: 42, bits: 16 });
597
598 c1.clamp_upper_bound_signed(23);
599 assert_eq!(c1, Constraint::Signed{ from: -0x8000, to: 23, bits: 16 });
600
601 c1.clamp_upper_bound_signed(42);
602 assert_eq!(c1, Constraint::Signed{ from: -0x8000, to: 23, bits: 16 });
603 }
604
605 #[test]
606 fn constraint_upper_bound_mixed() {
607 let mut c1 = Constraint::new(16).unwrap();
608
609 c1.clamp_upper_bound_signed(0xffe9);
611 assert_eq!(c1, Constraint::Signed{ from: -0x8000, to: -23, bits: 16 });
612
613 c1.clamp_upper_bound_unsigned(23);
614 assert_eq!(c1, Constraint::Empty{ bits: 16 });
615 }
616
617 #[test]
620 fn max() {
621 assert_eq!(Constraint::unsigned_max(1), 1);
622 assert_eq!(Constraint::unsigned_max(8), 0xff);
623 assert_eq!(Constraint::unsigned_max(16), 0xffff);
624 assert_eq!(Constraint::unsigned_max(32), 0xffffffff);
625 assert_eq!(Constraint::unsigned_max(64), 0xffffffffffffffff);
626 assert_eq!(Constraint::unsigned_max(128), 0xffffffffffffffff);
627
628 assert_eq!(Constraint::signed_max(1), 0);
629 assert_eq!(Constraint::signed_max(8), 0x7f);
630 assert_eq!(Constraint::signed_max(16), 0x7fff);
631 assert_eq!(Constraint::signed_max(32), 0x7fffffff);
632 assert_eq!(Constraint::signed_max(64), 0x7fffffffffffffff);
633 assert_eq!(Constraint::signed_max(128), 0x7fffffffffffffff);
634 }
635
636 #[test]
637 fn constraint_invert() {
638 assert_eq!(Constraint::Empty{ bits: 16 }.inverted(), Constraint::Full{ bits: 16 });
639 assert_eq!(Constraint::Full{ bits: 16 }.inverted(), Constraint::Empty{ bits: 16 });
640 assert_eq!(Constraint::Unsigned{ from: 0, to: 100, bits: 16 }.inverted(), Constraint::Unsigned{ from: 101, to: 0xffff, bits: 16 });
641 assert_eq!(Constraint::Unsigned{ from: 101, to: 0xffff, bits: 16 }.inverted(), Constraint::Unsigned{ from: 0, to: 100, bits: 16 });
642 assert_eq!(Constraint::Unsigned{ from: 0, to: 0, bits: 16 }.inverted(), Constraint::Unsigned{ from: 1, to: 0xffff, bits: 16 });
643 assert_eq!(Constraint::Unsigned{ from: 1, to: 0xffff, bits: 16 }.inverted(), Constraint::Unsigned{ from: 0, to: 0, bits: 16 });
644 assert_eq!(Constraint::Unsigned{ from: 1, to: 2, bits: 16 }.inverted(), Constraint::Full{ bits: 16 });
645 }
646}