diff options
author | 2017-06-28 19:29:53 -0400 | |
---|---|---|
committer | 2017-06-29 19:42:55 -0400 | |
commit | dd5212a24e79a98b19b0e3ec558f60fbb0c3a1b3 (patch) | |
tree | 80f0c0152e238c1344cdad673c489a289f6c283d /src | |
parent | 98f367931b372ffc4a75c63496faa1d17c3e2317 (diff) |
Add wrappers for subborrow and add_with_get_carry so they work when it is not known that they split on a power of 2
Diffstat (limited to 'src')
-rw-r--r-- | src/Util/ZUtil/AddGetCarry.v | 49 | ||||
-rw-r--r-- | src/Util/ZUtil/Definitions.v | 12 |
2 files changed, 49 insertions, 12 deletions
diff --git a/src/Util/ZUtil/AddGetCarry.v b/src/Util/ZUtil/AddGetCarry.v index 34f5f2ea8..18822cbe3 100644 --- a/src/Util/ZUtil/AddGetCarry.v +++ b/src/Util/ZUtil/AddGetCarry.v @@ -52,26 +52,51 @@ Module Z. Qed. End with_bitwidth. - Local Hint Unfold Z.add_get_carry_full Z.add_get_carry - Z.add_with_get_carry Z.get_carry Z.add_with_carry. + Local Ltac easypeasy := + repeat progress autounfold; + break_match; autorewrite with cancel_pair zsimplify; + solve [repeat (f_equal; try ring)]. + + Local Hint Unfold Z.get_carry Z.get_borrow + Z.add_get_carry_full Z.add_with_get_carry_full + Z.add_get_carry Z.add_with_get_carry Z.add_with_carry + Z.sub_get_borrow_full Z.sub_with_get_borrow_full + Z.sub_get_borrow Z.sub_with_get_borrow Z.sub_with_borrow. + Lemma add_get_carry_full_mod s x y : fst (Z.add_get_carry_full s x y) = (x + y) mod s. - Proof. - repeat progress autounfold. - break_match; autorewrite with cancel_pair zsimplify; - reflexivity. - Qed. + Proof. easypeasy. Qed. Lemma add_get_carry_full_div s x y : snd (Z.add_get_carry_full s x y) = (x + y) / s. - Proof. - repeat progress autounfold. - break_match; autorewrite with cancel_pair zsimplify; - reflexivity. - Qed. + Proof. easypeasy. Qed. + + Lemma add_with_get_carry_full_mod s c x y : + fst (Z.add_with_get_carry_full s c x y) = (c + x + y) mod s. + Proof. easypeasy. Qed. + + Lemma add_with_get_carry_full_div s c x y : + snd (Z.add_with_get_carry_full s c x y) = (c + x + y) / s. + Proof. easypeasy. Qed. Lemma sub_with_borrow_to_add_get_carry c x y : Z.sub_with_borrow c x y = Z.add_with_carry (-c) x (-y). Proof. reflexivity. Qed. + Lemma sub_get_borrow_full_mod s x y : + fst (Z.sub_get_borrow_full s x y) = (x - y) mod s. + Proof. easypeasy. Qed. + + Lemma sub_get_borrow_full_div s x y : + snd (Z.sub_get_borrow_full s x y) = - ((x - y) / s). + Proof. easypeasy. Qed. + + Lemma sub_with_get_borrow_full_mod s c x y : + fst (Z.sub_with_get_borrow_full s c x y) = (x - y - c) mod s. + Proof. easypeasy. Qed. + + Lemma sub_with_get_borrow_full_div s c x y : + snd (Z.sub_with_get_borrow_full s c x y) = - ((x - y - c) / s). + Proof. easypeasy. Qed. + End Z. diff --git a/src/Util/ZUtil/Definitions.v b/src/Util/ZUtil/Definitions.v index f6892be13..d80b2bde5 100644 --- a/src/Util/ZUtil/Definitions.v +++ b/src/Util/ZUtil/Definitions.v @@ -35,6 +35,18 @@ Module Z. := if dec (2 ^ (Z.log2 bound) = bound) then add_get_carry (Z.log2 bound) x y else ((x + y) mod bound, (x + y) / bound). + Definition add_with_get_carry_full (bound : Z) (c x y : Z) : Z * Z + := if dec (2 ^ (Z.log2 bound) = bound) + then add_with_get_carry (Z.log2 bound) c x y + else ((c + x + y) mod bound, (c + x + y) / bound). + Definition sub_get_borrow_full (bound : Z) (x y : Z) : Z * Z + := if dec (2 ^ (Z.log2 bound) = bound) + then sub_get_borrow (Z.log2 bound) x y + else ((x - y) mod bound, -((x - y) / bound)). + Definition sub_with_get_borrow_full (bound : Z) (c x y : Z) : Z * Z + := if dec (2 ^ (Z.log2 bound) = bound) + then sub_with_get_borrow (Z.log2 bound) c x y + else ((x - y - c) mod bound, -((x - y - c) / bound)). Definition mul_split_at_bitwidth (bitwidth : Z) (x y : Z) : Z * Z := dlet xy := x * y in |