Add ZUtil lemmas, and Util.Bool

After    | File Name                                       | Before   || Change
----------------------------------------------------------------------------------
1m43.58s | Total                                           | 1m44.69s || -0m01.10s
----------------------------------------------------------------------------------
0m32.94s | Specific/GF25519                                | 0m33.18s || -0m00.24s
0m15.34s | ModularArithmetic/ModularBaseSystemProofs       | 0m15.35s || -0m00.00s
0m11.42s | Experiments/SpecEd25519                         | 0m11.46s || -0m00.04s
0m07.12s | Specific/GF1305                                 | 0m07.38s || -0m00.25s
0m04.04s | ModularArithmetic/Pow2BaseProofs                | 0m04.09s || -0m00.04s
0m03.82s | ModularArithmetic/Tutorial                      | 0m03.79s || +0m00.02s
0m03.81s | BaseSystemProofs                                | 0m03.71s || +0m00.10s
0m03.16s | ModularArithmetic/ModularBaseSystemOpt          | 0m03.23s || -0m00.06s
0m02.76s | Util/ZUtil                                      | 0m02.79s || -0m00.03s
0m01.63s | ModularArithmetic/PrimeFieldTheorems            | 0m01.65s || -0m00.02s
0m01.58s | Encoding/PointEncodingPre                       | 0m01.51s || +0m00.07s
0m01.57s | ModularArithmetic/ModularArithmeticTheorems     | 0m01.59s || -0m00.02s
0m01.33s | BaseSystem                                      | 0m01.50s || -0m00.16s
0m01.09s | ModularArithmetic/ExtendedBaseVector            | 0m01.13s || -0m00.03s
0m00.95s | Experiments/DerivationsOptionRectLetInEncoding  | 0m00.97s || -0m00.02s
0m00.93s | ModularArithmetic/BarrettReduction/Z            | 0m00.98s || -0m00.04s
0m00.91s | Util/NumTheoryUtil                              | 0m01.19s || -0m00.27s
0m00.91s | ModularArithmetic/ModularBaseSystemField        | 0m00.91s || +0m00.00s
0m00.81s | ModularArithmetic/ModularBaseSystemListProofs   | 0m00.81s || +0m00.00s
0m00.74s | Experiments/SpecificCurve25519                  | 0m00.70s || +0m00.04s
0m00.65s | Encoding/ModularWordEncodingTheorems            | 0m00.72s || -0m00.06s
0m00.65s | Encoding/ModularWordEncodingPre                 | 0m00.62s || +0m00.03s
0m00.64s | Testbit                                         | 0m00.66s || -0m00.02s
0m00.63s | ModularArithmetic/ExtPow2BaseMulProofs          | 0m00.63s || +0m00.00s
0m00.63s | Spec/ModularWordEncoding                        | 0m00.63s || +0m00.00s
0m00.60s | ModularArithmetic/ModularBaseSystem             | 0m00.57s || +0m00.03s
0m00.59s | ModularArithmetic/ModularBaseSystemList         | 0m00.61s || -0m00.02s
0m00.57s | ModularArithmetic/PseudoMersenneBaseParamProofs | 0m00.61s || -0m00.04s
0m00.56s | ModularArithmetic/Pre                           | 0m00.48s || +0m00.08s
0m00.41s | ModularArithmetic/Pow2Base                      | 0m00.42s || -0m00.01s
0m00.38s | ModularArithmetic/PseudoMersenneBaseParams      | 0m00.43s || -0m00.04s
0m00.38s | Spec/ModularArithmetic                          | 0m00.39s || -0m00.01s
0m00.04s | Util/Bool                                       |   N/A    || +0m00.04s

3 files changed, 53 insertions, 1 deletions

diff --git a/_CoqProject b/_CoqProject
index 0d45357f9..fe9916326 100644
--- a/_CoqProject
+++ b/_CoqProject
@@ -62,6 +62,7 @@ src/Specific/GF25519.v
 src/Tactics/VerdiTactics.v
 src/Tactics/Algebra_syntax/Nsatz.v
 src/Util/AdditionChainExponentiation.v
+src/Util/Bool.v
 src/Util/CaseUtil.v
 src/Util/Decidable.v
 src/Util/Equality.v
diff --git a/src/Util/Bool.v b/src/Util/Bool.v
new file mode 100644
index 000000000..031718c87
--- /dev/null
+++ b/src/Util/Bool.v
@@ -0,0 +1,43 @@
+(*** Boolean Utility Lemmas and Databases *)
+Require Import Coq.Bool.Bool.
+
+(** For equalities of booleans *)
+Create HintDb bool_congr discriminated.
+(** For properties of booleans, with, e.g., [iff] *)
+Create HintDb bool_congr_setoid discriminated.
+(** For generic simplifications of things involving booleans, e.g., if-statements *)
+Create HintDb boolsimplify discriminated.
+
+Hint Extern 1 => progress autorewrite with boolsimplify in * : boolsimplify.
+Hint Extern 1 => progress autorewrite with bool_congr in * : bool_congr.
+Hint Extern 1 => progress autorewrite with bool_congr_setoid in * : bool_congr_setoid.
+Hint Extern 2 => progress rewrite_strat topdown hints bool_congr_setoid : bool_congr_setoid.
+
+Hint Rewrite Bool.andb_diag Bool.orb_diag Bool.eqb_reflx Bool.negb_involutive Bool.eqb_negb1 Bool.eqb_negb2 Bool.orb_true_r Bool.orb_true_l Bool.orb_false_r Bool.orb_false_l Bool.orb_negb_r Bool.andb_false_r Bool.andb_false_l Bool.andb_true_r Bool.andb_false_r Bool.andb_negb_r Bool.absorption_andb Bool.absorption_orb Bool.xorb_false_r Bool.xorb_false_l Bool.xorb_true_r Bool.xorb_true_l Bool.xorb_nilpotent : bool_congr.
+Hint Rewrite Bool.negb_if : boolsimplify.
+Hint Rewrite <- Bool.andb_if Bool.andb_lazy_alt Bool.orb_lazy_alt : boolsimplify.
+Hint Rewrite Bool.not_true_iff_false Bool.not_false_iff_true Bool.eqb_true_iff Bool.eqb_false_iff Bool.negb_true_iff Bool.negb_false_iff Bool.orb_true_iff Bool.orb_false_iff Bool.andb_true_iff Bool.andb_false_iff Bool.xorb_negb_negb : bool_congr_setoid.
+
+Create HintDb push_orb discriminated.
+Create HintDb pull_orb discriminated.
+Create HintDb push_andb discriminated.
+Create HintDb pull_andb discriminated.
+Create HintDb push_negb discriminated.
+Create HintDb pull_negb discriminated.
+Hint Extern 1 => progress autorewrite with push_orb in * : push_orb.
+Hint Extern 1 => progress autorewrite with pull_orb in * : pull_orb.
+Hint Extern 1 => progress autorewrite with push_andb in * : push_andb.
+Hint Extern 1 => progress autorewrite with pull_andb in * : pull_andb.
+Hint Extern 1 => progress autorewrite with push_negb in * : push_negb.
+Hint Extern 1 => progress autorewrite with pull_negb in * : pull_negb.
+Hint Rewrite Bool.negb_orb Bool.negb_andb : push_negb.
+Hint Rewrite Bool.xorb_negb_negb : pull_negb.
+Hint Rewrite <- Bool.negb_orb Bool.negb_andb Bool.negb_xorb_l Bool.negb_xorb_r : pull_negb.
+Hint Rewrite Bool.andb_orb_distrib_r Bool.andb_orb_distrib_l : push_andb.
+Hint Rewrite <- Bool.orb_andb_distrib_r Bool.orb_andb_distrib_l : push_andb.
+Hint Rewrite Bool.orb_andb_distrib_r Bool.orb_andb_distrib_l : pull_andb.
+Hint Rewrite <- Bool.andb_orb_distrib_r Bool.andb_orb_distrib_l : pull_andb.
+Hint Rewrite Bool.orb_andb_distrib_r Bool.orb_andb_distrib_l : push_orb.
+Hint Rewrite <- Bool.andb_orb_distrib_r Bool.andb_orb_distrib_l : push_orb.
+Hint Rewrite <- Bool.orb_andb_distrib_r Bool.orb_andb_distrib_l : pull_orb.
+Hint Rewrite Bool.andb_orb_distrib_r Bool.andb_orb_distrib_l : pull_orb.
diff --git a/src/Util/ZUtil.v b/src/Util/ZUtil.v
index 0b1d097bb..b7547f150 100644
--- a/src/Util/ZUtil.v
+++ b/src/Util/ZUtil.v
@@ -24,7 +24,7 @@ Hint Resolve (fun a b H => proj1 (Z.mod_pos_bound a b H)) (fun a b H => proj2 (Z
     which can reasonably be said to "simplify" the goal, should go in
     this database. *)
 Create HintDb zsimplify discriminated.
-Hint Rewrite Z.div_1_r Z.mul_1_r Z.mul_1_l Z.sub_diag Z.mul_0_r Z.mul_0_l Z.add_0_l Z.add_0_r Z.opp_involutive Z.sub_0_r Z_mod_same_full Z.sub_simpl_r Z.sub_simpl_l Z.add_opp_diag_r Z.add_opp_diag_l Zmod_0_l Z.add_simpl_r Z.add_simpl_l : zsimplify.
+Hint Rewrite Z.div_1_r Z.mul_1_r Z.mul_1_l Z.sub_diag Z.mul_0_r Z.mul_0_l Z.add_0_l Z.add_0_r Z.opp_involutive Z.sub_0_r Z_mod_same_full Z.sub_simpl_r Z.sub_simpl_l Z.add_opp_diag_r Z.add_opp_diag_l Zmod_0_l Z.add_simpl_r Z.add_simpl_l Z.opp_0 : zsimplify.
 Hint Rewrite Z.div_mul Z.div_1_l Z.div_same Z.mod_same Z.div_small Z.mod_small Z.div_add Z.div_add_l Z.mod_add Z.div_0_l Z.mod_mod using lia : zsimplify.
 Hint Rewrite <- Z.opp_eq_mul_m1 : zsimplify.
 
@@ -1162,6 +1162,14 @@ Module Z.
     reflexivity.
   Qed.
 
+  Lemma minus_distr_if (b : bool) x y : -(if b then x else y) = if b then -x else -y.
+  Proof. destruct b; reflexivity. Qed.
+  Hint Rewrite minus_distr_if : push_Zopp.
+
+  Lemma minus_minus_one : - -1 = 1.
+  Proof. reflexivity. Qed.
+  Hint Rewrite minus_minus_one : zsimplify.
+
   Lemma mul_mod_l a b n : n <> 0 -> (a * b) mod n = ((a mod n) * b) mod n.
   Proof.
     intros; rewrite (Z.mul_mod a b), (Z.mul_mod (a mod n) b) by lia.