Add more zutil morphisms

After     | File Name                                                            | Before    || Change    | % Change
--------------------------------------------------------------------------------------------------------------------
58m47.93s | Total                                                                | 58m44.74s || +0m03.19s | +0.09%
--------------------------------------------------------------------------------------------------------------------
0m05.68s  | Util/ZUtil/Morphisms                                                 | 0m00.76s  || +0m04.92s | +647.36%
1m51.74s  | Specific/NISTP256/AMD64/femul                                        | 1m54.10s  || -0m02.35s | -2.06%
8m42.26s  | Experiments/SimplyTypedArithmetic                                    | 8m44.21s  || -0m01.95s | -0.37%
6m03.05s  | Experiments/NewPipeline/SlowPrimeSynthesisExamples                   | 6m04.33s  || -0m01.27s | -0.35%
5m09.13s  | Experiments/NewPipeline/Toplevel1                                    | 5m07.64s  || +0m01.49s | +0.48%
3m46.25s  | Curves/Montgomery/XZProofs                                           | 3m44.74s  || +0m01.50s | +0.67%
2m12.91s  | Specific/X25519/C64/ladderstep                                       | 2m13.06s  || -0m00.15s | -0.11%
1m29.49s  | Experiments/NewPipeline/Arithmetic                                   | 1m29.77s  || -0m00.28s | -0.31%
1m29.04s  | Spec/Test/X25519                                                     | 1m28.84s  || +0m00.19s | +0.22%
1m22.84s  | Compilers/Named/MapCastInterp                                        | 1m23.24s  || -0m00.39s | -0.48%
1m20.52s  | Experiments/NewPipeline/Toplevel2                                    | 1m20.60s  || -0m00.07s | -0.09%
1m18.85s  | Specific/X2448/Karatsuba/C64/femul                                   | 1m18.71s  || +0m00.13s | +0.17%
0m59.89s  | Specific/X25519/C32/femul                                            | 0m59.98s  || -0m00.08s | -0.15%
0m52.28s  | Demo                                                                 | 0m52.81s  || -0m00.53s | -1.00%
0m48.63s  | Compilers/Z/Named/RewriteAddToAdcInterp                              | 0m48.46s  || +0m00.17s | +0.35%
0m47.29s  | Compilers/Z/ArithmeticSimplifierInterp                               | 0m47.17s  || +0m00.11s | +0.25%
0m43.10s  | Specific/X25519/C32/fesquare                                         | 0m42.98s  || +0m00.12s | +0.27%
0m42.06s  | Arithmetic/Karatsuba                                                 | 0m42.55s  || -0m00.48s | -1.15%
0m38.15s  | p521_32.c                                                            | 0m38.05s  || +0m00.10s | +0.26%
0m36.56s  | Experiments/NewPipeline/ExtractionOCaml/word_by_word_montgomery      | 0m36.45s  || +0m00.10s | +0.30%
0m36.25s  | Spec/Ed25519                                                         | 0m36.28s  || -0m00.03s | -0.08%
0m35.70s  | Experiments/NewPipeline/ExtractionHaskell/word_by_word_montgomery    | 0m35.94s  || -0m00.23s | -0.66%
0m33.46s  | Specific/X25519/C32/freeze                                           | 0m33.44s  || +0m00.02s | +0.05%
0m31.85s  | p521_64.c                                                            | 0m31.82s  || +0m00.03s | +0.09%
0m31.03s  | Compilers/Z/ArithmeticSimplifierWf                                   | 0m30.95s  || +0m00.08s | +0.25%
0m27.97s  | Specific/NISTP256/AMD128/femul                                       | 0m27.83s  || +0m00.14s | +0.50%
0m27.04s  | Primitives/EdDSARepChange                                            | 0m26.86s  || +0m00.17s | +0.67%
0m25.50s  | Specific/X25519/C32/fecarry                                          | 0m25.35s  || +0m00.14s | +0.59%
0m23.67s  | p384_32.c                                                            | 0m23.68s  || -0m00.00s | -0.04%
0m22.12s  | Experiments/NewPipeline/ExtractionHaskell/unsaturated_solinas        | 0m22.01s  || +0m00.10s | +0.49%
0m21.54s  | Arithmetic/Core                                                      | 0m21.43s  || +0m00.10s | +0.51%
0m21.52s  | Specific/X25519/C32/fesub                                            | 0m21.48s  || +0m00.03s | +0.18%
0m20.96s  | Specific/NISTP256/AMD64/fesub                                        | 0m20.95s  || +0m00.01s | +0.04%
0m20.85s  | Arithmetic/MontgomeryReduction/WordByWord/Abstract/Dependent/Proofs  | 0m20.82s  || +0m00.03s | +0.14%
0m20.48s  | Specific/X25519/C64/femul                                            | 0m20.49s  || -0m00.00s | -0.04%
0m19.90s  | Specific/X25519/C32/Synthesis                                        | 0m19.78s  || +0m00.11s | +0.60%
0m19.40s  | Experiments/NewPipeline/ExtractionOCaml/unsaturated_solinas          | 0m19.30s  || +0m00.09s | +0.51%
0m19.25s  | Specific/X25519/C32/feadd                                            | 0m19.19s  || +0m00.05s | +0.31%
0m19.08s  | Specific/NISTP256/AMD64/feadd                                        | 0m19.10s  || -0m00.02s | -0.10%
0m18.15s  | Compilers/Named/MapCastWf                                            | 0m18.05s  || +0m00.09s | +0.55%
0m17.44s  | Specific/X25519/C64/freeze                                           | 0m17.42s  || +0m00.01s | +0.11%
0m17.00s  | Specific/X25519/C64/fesquare                                         | 0m17.05s  || -0m00.05s | -0.29%
0m15.98s  | Specific/NISTP256/AMD64/feopp                                        | 0m15.85s  || +0m00.13s | +0.82%
0m15.04s  | Specific/NISTP256/AMD128/feadd                                       | 0m15.00s  || +0m00.03s | +0.26%
0m14.93s  | Specific/NISTP256/AMD128/fesub                                       | 0m15.04s  || -0m00.10s | -0.73%
0m14.61s  | Experiments/NewPipeline/ExtractionHaskell/saturated_solinas          | 0m14.51s  || +0m00.09s | +0.68%
0m14.31s  | Specific/NISTP256/AMD64/fenz                                         | 0m14.28s  || +0m00.03s | +0.21%
0m14.25s  | Specific/X25519/C64/fecarry                                          | 0m14.18s  || +0m00.07s | +0.49%
0m13.80s  | Arithmetic/Saturated/AddSub                                          | 0m13.80s  || +0m00.00s | +0.00%
0m13.78s  | Specific/NISTP256/AMD128/fenz                                        | 0m13.80s  || -0m00.02s | -0.14%
0m13.26s  | Compilers/Z/Syntax/Equality                                          | 0m12.55s  || +0m00.70s | +5.65%
0m13.23s  | Specific/X25519/C64/fesub                                            | 0m13.16s  || +0m00.07s | +0.53%
0m12.25s  | Specific/NISTP256/AMD128/feopp                                       | 0m12.33s  || -0m00.08s | -0.64%
0m12.06s  | Arithmetic/MontgomeryReduction/WordByWord/Abstract/Proofs            | 0m11.96s  || +0m00.09s | +0.83%
0m11.88s  | Specific/X25519/C64/feadd                                            | 0m11.98s  || -0m00.09s | -0.83%
0m11.45s  | Arithmetic/Saturated/MontgomeryAPI                                   | 0m11.73s  || -0m00.28s | -2.38%
0m10.89s  | Arithmetic/MontgomeryReduction/Proofs                                | 0m10.96s  || -0m00.07s | -0.63%
0m10.81s  | LegacyArithmetic/Double/Proofs/Multiply                              | 0m10.78s  || +0m00.03s | +0.27%
0m10.72s  | Arithmetic/Saturated/Core                                            | 0m10.70s  || +0m00.02s | +0.18%
0m10.66s  | Experiments/NewPipeline/ExtractionOCaml/saturated_solinas            | 0m10.88s  || -0m00.22s | -2.02%
0m10.09s  | Util/ZUtil                                                           | 0m10.07s  || +0m00.01s | +0.19%
0m09.90s  | Specific/X2448/Karatsuba/C64/Synthesis                               | 0m09.80s  || +0m00.09s | +1.02%
0m08.60s  | Experiments/NewPipeline/ExtractionOCaml/word_by_word_montgomery.ml   | 0m08.64s  || -0m00.04s | -0.46%
0m08.60s  | LegacyArithmetic/ArchitectureToZLikeProofs                           | 0m08.52s  || +0m00.08s | +0.93%
0m08.55s  | LegacyArithmetic/Double/Proofs/ShiftRightDoubleWordImmediate         | 0m08.46s  || +0m00.08s | +1.06%
0m08.36s  | p384_64.c                                                            | 0m08.51s  || -0m00.15s | -1.76%
0m08.24s  | LegacyArithmetic/Double/Proofs/SpreadLeftImmediate                   | 0m08.11s  || +0m00.13s | +1.60%
0m08.20s  | Arithmetic/BarrettReduction/RidiculousFish                           | 0m08.23s  || -0m00.03s | -0.36%
0m07.10s  | Specific/NISTP256/AMD64/Synthesis                                    | 0m07.09s  || +0m00.00s | +0.14%
0m06.99s  | LegacyArithmetic/Double/Proofs/RippleCarryAddSub                     | 0m07.02s  || -0m00.02s | -0.42%
0m06.60s  | Arithmetic/BarrettReduction/Generalized                              | 0m06.53s  || +0m00.06s | +1.07%
0m06.60s  | Arithmetic/Saturated/MulSplit                                        | 0m06.53s  || +0m00.06s | +1.07%
0m06.56s  | Util/FixedWordSizesEquality                                          | 0m06.50s  || +0m00.05s | +0.92%
0m06.47s  | LegacyArithmetic/Pow2BaseProofs                                      | 0m06.32s  || +0m00.14s | +2.37%
0m06.32s  | Compilers/Z/Bounds/InterpretationLemmas/PullCast                     | 0m06.36s  || -0m00.04s | -0.62%
0m06.05s  | Specific/X25519/C64/Synthesis                                        | 0m06.07s  || -0m00.02s | -0.32%
0m05.58s  | Experiments/NewPipeline/ExtractionHaskell/word_by_word_montgomery.hs | 0m05.51s  || +0m00.07s | +1.27%
0m05.44s  | Experiments/NewPipeline/ExtractionOCaml/unsaturated_solinas.ml       | 0m05.43s  || +0m00.01s | +0.18%
0m05.08s  | Arithmetic/BarrettReduction/HAC                                      | 0m05.06s  || +0m00.02s | +0.39%
0m04.74s  | LegacyArithmetic/InterfaceProofs                                     | 0m04.98s  || -0m00.24s | -4.81%
0m04.62s  | Compilers/Z/Bounds/Pipeline/Definition                               | 0m04.60s  || +0m00.02s | +0.43%
0m04.60s  | Specific/Framework/ArithmeticSynthesis/Montgomery                    | 0m04.76s  || -0m00.16s | -3.36%
0m04.03s  | Experiments/NewPipeline/ExtractionOCaml/saturated_solinas.ml         | 0m04.00s  || +0m00.03s | +0.75%
0m04.02s  | LegacyArithmetic/ZBoundedZ                                           | 0m03.82s  || +0m00.19s | +5.23%
0m04.00s  | Experiments/NewPipeline/ExtractionHaskell/unsaturated_solinas.hs     | 0m03.98s  || +0m00.02s | +0.50%
0m03.78s  | p256_32.c                                                            | 0m03.80s  || -0m00.02s | -0.52%
0m03.74s  | Arithmetic/MontgomeryReduction/WordByWord/Proofs                     | 0m03.88s  || -0m00.13s | -3.60%
0m03.71s  | secp256k1_32.c                                                       | 0m03.71s  || +0m00.00s | +0.00%
0m03.64s  | LegacyArithmetic/Double/Proofs/ShiftRight                            | 0m03.68s  || -0m00.04s | -1.08%
0m03.52s  | Compilers/Z/ArithmeticSimplifier                                     | 0m03.53s  || -0m00.00s | -0.28%
0m03.47s  | Compilers/Z/Bounds/InterpretationLemmas/IsBoundedBy                  | 0m03.41s  || +0m00.06s | +1.75%
0m03.43s  | Arithmetic/ModularArithmeticTheorems                                 | 0m03.44s  || -0m00.00s | -0.29%
0m03.43s  | LegacyArithmetic/Double/Proofs/Decode                                | 0m03.36s  || +0m00.07s | +2.08%
0m03.34s  | Specific/NISTP256/AMD128/Synthesis                                   | 0m03.36s  || -0m00.02s | -0.59%
0m03.21s  | Experiments/NewPipeline/ExtractionHaskell/saturated_solinas.hs       | 0m03.24s  || -0m00.03s | -0.92%
0m03.14s  | LegacyArithmetic/Double/Proofs/ShiftLeft                             | 0m03.09s  || +0m00.05s | +1.61%
0m03.02s  | Util/WordUtil                                                        | 0m03.06s  || -0m00.04s | -1.30%
0m02.74s  | LegacyArithmetic/BarretReduction                                     | 0m02.76s  || -0m00.01s | -0.72%
0m02.65s  | Arithmetic/Saturated/Freeze                                          | 0m02.63s  || +0m00.02s | +0.76%
0m02.32s  | Specific/NISTP256/FancyMachine256/Core                               | 0m02.33s  || -0m00.01s | -0.42%
0m02.32s  | Specific/NISTP256/FancyMachine256/Montgomery                         | 0m02.35s  || -0m00.03s | -1.27%
0m02.24s  | p224_32.c                                                            | 0m02.08s  || +0m00.16s | +7.69%
0m02.23s  | Compilers/Z/Bounds/Relax                                             | 0m02.24s  || -0m00.01s | -0.44%
0m02.19s  | Specific/NISTP256/FancyMachine256/Barrett                            | 0m02.18s  || +0m00.00s | +0.45%
0m02.15s  | curve25519_32.c                                                      | 0m02.18s  || -0m00.03s | -1.37%
0m02.13s  | Compilers/Z/RewriteAddToAdcInterp                                    | 0m02.11s  || +0m00.02s | +0.94%
0m02.12s  | Arithmetic/BarrettReduction/Wikipedia                                | 0m02.07s  || +0m00.05s | +2.41%
0m02.08s  | Specific/Framework/ArithmeticSynthesis/Defaults                      | 0m02.07s  || +0m00.01s | +0.48%
0m01.89s  | LegacyArithmetic/MontgomeryReduction                                 | 0m02.39s  || -0m00.50s | -20.92%
0m01.77s  | LegacyArithmetic/Double/Proofs/BitwiseOr                             | 0m01.45s  || +0m00.32s | +22.06%
0m01.70s  | Arithmetic/CoreUnfolder                                              | 0m01.69s  || +0m00.01s | +0.59%
0m01.70s  | Specific/Framework/ReificationTypes                                  | 0m01.69s  || +0m00.01s | +0.59%
0m01.64s  | p224_64.c                                                            | 0m01.52s  || +0m00.11s | +7.89%
0m01.56s  | p256_64.c                                                            | 0m01.58s  || -0m00.02s | -1.26%
0m01.54s  | curve25519_64.c                                                      | 0m01.38s  || +0m00.16s | +11.59%
0m01.50s  | Specific/Framework/OutputType                                        | 0m01.52s  || -0m00.02s | -1.31%
0m01.48s  | Util/QUtil                                                           | 0m01.45s  || +0m00.03s | +2.06%
0m01.48s  | secp256k1_64.c                                                       | 0m01.49s  || -0m00.01s | -0.67%
0m01.47s  | Specific/Framework/ArithmeticSynthesis/Base                          | 0m01.48s  || -0m00.01s | -0.67%
0m01.44s  | Experiments/NewPipeline/CLI                                          | 0m01.45s  || -0m00.01s | -0.68%
0m01.38s  | Specific/Framework/ArithmeticSynthesis/Karatsuba                     | 0m01.37s  || +0m00.00s | +0.72%
0m01.33s  | Arithmetic/PrimeFieldTheorems                                        | 0m01.34s  || -0m00.01s | -0.74%
0m01.30s  | Compilers/Z/Syntax/Util                                              | 0m00.83s  || +0m00.47s | +56.62%
0m01.30s  | LegacyArithmetic/Double/Proofs/LoadImmediate                         | 0m01.32s  || -0m00.02s | -1.51%
0m01.26s  | LegacyArithmetic/BaseSystemProofs                                    | 0m01.26s  || +0m00.00s | +0.00%
0m01.21s  | Experiments/NewPipeline/StandaloneOCamlMain                          | 0m01.24s  || -0m00.03s | -2.41%
0m01.16s  | Experiments/NewPipeline/StandaloneHaskellMain                        | 0m01.27s  || -0m00.11s | -8.66%
0m01.14s  | Arithmetic/Saturated/CoreUnfolder                                    | 0m01.11s  || +0m00.02s | +2.70%
0m01.13s  | Util/ZRange/CornersMonotoneBounds                                    | 0m01.18s  || -0m00.05s | -4.23%
0m01.08s  | Util/NumTheoryUtil                                                   | 0m01.04s  || +0m00.04s | +3.84%
0m01.04s  | Specific/Framework/SynthesisFramework                                | 0m01.00s  || +0m00.04s | +4.00%
0m01.04s  | Util/ZUtil/Stabilization                                             | 0m01.06s  || -0m00.02s | -1.88%
0m00.98s  | Arithmetic/Saturated/WrappersUnfolder                                | 0m01.31s  || -0m00.33s | -25.19%
0m00.95s  | Arithmetic/Saturated/UniformWeight                                   | 0m00.93s  || +0m00.01s | +2.15%
0m00.91s  | Compilers/Z/Bounds/Pipeline/ReflectiveTactics                        | 0m00.97s  || -0m00.05s | -6.18%
0m00.88s  | Compilers/Z/CommonSubexpressionElimination                           | 0m00.87s  || +0m00.01s | +1.14%
0m00.86s  | Specific/Framework/ArithmeticSynthesis/Freeze                        | 0m00.86s  || +0m00.00s | +0.00%
0m00.85s  | Compilers/MapCastByDeBruijnInterp                                    | 0m00.84s  || +0m00.01s | +1.19%
0m00.80s  | Arithmetic/Saturated/MulSplitUnfolder                                | 0m00.83s  || -0m00.02s | -3.61%
0m00.78s  | LegacyArithmetic/Interface                                           | 0m00.72s  || +0m00.06s | +8.33%
0m00.77s  | Compilers/Z/Bounds/InterpretationLemmas/Tactics                      | 0m00.58s  || +0m00.19s | +32.75%
0m00.76s  | Arithmetic/Saturated/Wrappers                                        | 0m00.78s  || -0m00.02s | -2.56%
0m00.76s  | Specific/Framework/ArithmeticSynthesis/HelperTactics                 | 0m00.73s  || +0m00.03s | +4.10%
0m00.76s  | Specific/Framework/ReificationTypesPackage                           | 0m00.77s  || -0m00.01s | -1.29%
0m00.75s  | Specific/Framework/MontgomeryReificationTypesPackage                 | 0m00.72s  || +0m00.03s | +4.16%
0m00.73s  | Arithmetic/MontgomeryReduction/WordByWord/Definition                 | 0m00.70s  || +0m00.03s | +4.28%
0m00.73s  | Arithmetic/Saturated/FreezeUnfolder                                  | 0m00.84s  || -0m00.10s | -13.09%
0m00.73s  | Specific/Framework/ArithmeticSynthesis/BasePackage                   | 0m00.77s  || -0m00.04s | -5.19%
0m00.72s  | Arithmetic/Saturated/UniformWeightInstances                          | 0m00.70s  || +0m00.02s | +2.85%
0m00.72s  | Specific/Framework/ArithmeticSynthesis/Ladderstep                    | 0m00.69s  || +0m00.03s | +4.34%
0m00.72s  | Specific/Framework/ArithmeticSynthesis/MontgomeryPackage             | 0m00.73s  || -0m00.01s | -1.36%
0m00.72s  | Specific/Framework/ArithmeticSynthesis/SquareFromMul                 | 0m00.70s  || +0m00.02s | +2.85%
0m00.72s  | Specific/Framework/MontgomeryReificationTypes                        | 0m00.74s  || -0m00.02s | -2.70%
0m00.71s  | Compilers/Z/Bounds/MapCastByDeBruijnWf                               | 0m00.56s  || +0m00.14s | +26.78%
0m00.71s  | Specific/Framework/ArithmeticSynthesis/FreezePackage                 | 0m00.70s  || +0m00.01s | +1.42%
0m00.69s  | LegacyArithmetic/Double/Proofs/SelectConditional                     | 0m00.68s  || +0m00.00s | +1.47%
0m00.68s  | Compilers/Z/Bounds/Pipeline                                          | 0m00.67s  || +0m00.01s | +1.49%
0m00.68s  | Specific/Framework/ArithmeticSynthesis/KaratsubaPackage              | 0m00.66s  || +0m00.02s | +3.03%
0m00.66s  | Compilers/MapCastByDeBruijnWf                                        | 0m00.75s  || -0m00.08s | -11.99%
0m00.65s  | Specific/Framework/ArithmeticSynthesis/DefaultsPackage               | 0m00.67s  || -0m00.02s | -2.98%
0m00.65s  | Specific/Framework/ArithmeticSynthesis/LadderstepPackage             | 0m00.72s  || -0m00.06s | -9.72%
0m00.61s  | Util/NUtil                                                           | 0m00.62s  || -0m00.01s | -1.61%
0m00.60s  | LegacyArithmetic/Double/Core                                         | 0m00.64s  || -0m00.04s | -6.25%
0m00.58s  | Compilers/Z/Bounds/Pipeline/Glue                                     | 0m00.64s  || -0m00.06s | -9.37%
0m00.57s  | Arithmetic/ModularArithmeticPre                                      | 0m00.56s  || +0m00.00s | +1.78%
0m00.57s  | Compilers/Z/Bounds/MapCastByDeBruijnInterp                           | 0m00.54s  || +0m00.02s | +5.55%
0m00.57s  | Compilers/Z/Reify                                                    | 0m00.56s  || +0m00.00s | +1.78%
0m00.57s  | LegacyArithmetic/ZBounded                                            | 0m00.63s  || -0m00.06s | -9.52%
0m00.55s  | Compilers/Z/FoldTypes                                                | 0m00.50s  || +0m00.05s | +10.00%
0m00.55s  | Compilers/ZExtended/MapBaseType                                      | 0m00.48s  || +0m00.07s | +14.58%
0m00.54s  | Compilers/Z/Bounds/MapCastByDeBruijn                                 | 0m00.65s  || -0m00.10s | -16.92%
0m00.54s  | Compilers/Z/MapCastByDeBruijnWf                                      | 0m00.56s  || -0m00.02s | -3.57%
0m00.53s  | Compilers/Z/CommonSubexpressionEliminationInterp                     | 0m00.46s  || +0m00.07s | +15.21%
0m00.53s  | Compilers/Z/MapCastByDeBruijnInterp                                  | 0m00.56s  || -0m00.03s | -5.35%
0m00.53s  | LegacyArithmetic/Double/Proofs/ShiftLeftRightTactic                  | 0m00.53s  || +0m00.00s | +0.00%
0m00.52s  | LegacyArithmetic/BaseSystem                                          | 0m00.53s  || -0m00.01s | -1.88%
0m00.52s  | Spec/EdDSA                                                           | 0m00.50s  || +0m00.02s | +4.00%
0m00.51s  | Compilers/Z/CommonSubexpressionEliminationWf                         | 0m00.52s  || -0m00.01s | -1.92%
0m00.51s  | Compilers/Z/InlineConstAndOpWf                                       | 0m00.48s  || +0m00.03s | +6.25%
0m00.50s  | Compilers/Z/ArithmeticSimplifierUtil                                 | 0m00.51s  || -0m00.01s | -1.96%
0m00.50s  | Compilers/Z/Inline                                                   | 0m00.49s  || +0m00.01s | +2.04%
0m00.50s  | Compilers/Z/InlineConstAndOpByRewriteWf                              | 0m00.48s  || +0m00.02s | +4.16%
0m00.50s  | LegacyArithmetic/ArchitectureToZLike                                 | 0m00.64s  || -0m00.14s | -21.87%
0m00.50s  | LegacyArithmetic/Pow2Base                                            | 0m00.48s  || +0m00.02s | +4.16%
0m00.49s  | Arithmetic/MontgomeryReduction/Definition                            | 0m00.48s  || +0m00.01s | +2.08%
0m00.49s  | Compilers/Z/InterpSideConditions                                     | 0m00.50s  || -0m00.01s | -2.00%
0m00.48s  | Compilers/Z/InlineConstAndOp                                         | 0m00.46s  || +0m00.01s | +4.34%
0m00.47s  | Compilers/Z/InlineConstAndOpInterp                                   | 0m00.48s  || -0m00.01s | -2.08%
0m00.47s  | Compilers/Z/InlineInterp                                             | 0m00.50s  || -0m00.03s | -6.00%
0m00.47s  | Compilers/Z/InlineWf                                                 | 0m00.48s  || -0m00.01s | -2.08%
0m00.46s  | Compilers/Z/InlineConstAndOpByRewrite                                | 0m00.47s  || -0m00.00s | -2.12%
0m00.46s  | Compilers/Z/InlineConstAndOpByRewriteInterp                          | 0m00.45s  || +0m00.01s | +2.22%
0m00.45s  | Spec/ModularArithmetic                                               | 0m00.44s  || +0m00.01s | +2.27%

1 files changed, 203 insertions, 0 deletions

diff --git a/src/Util/ZUtil/Morphisms.v b/src/Util/ZUtil/Morphisms.v
index 731219a6a..91f3dff3c 100644
--- a/src/Util/ZUtil/Morphisms.v
+++ b/src/Util/ZUtil/Morphisms.v
@@ -5,6 +5,13 @@ Require Import Coq.ZArith.ZArith.
 Require Import Coq.Classes.Morphisms.
 Require Import Coq.Classes.RelationPairs.
 Require Import Crypto.Util.ZUtil.Definitions.
+Require Import Crypto.Util.ZUtil.Div.
+Require Import Crypto.Util.ZUtil.Tactics.PeelLe.
+Require Import Crypto.Util.ZUtil.Tactics.DivModToQuotRem.
+Require Import Crypto.Util.ZUtil.Tactics.LtbToLt.
+Require Import Crypto.Util.Tactics.UniquePose.
+Require Import Crypto.Util.Tactics.DestructHead.
+Require Import Crypto.Util.Tactics.BreakMatch.
 Local Open Scope Z_scope.
 
 Module Z.
@@ -76,4 +83,200 @@ Module Z.
   Lemma sub_with_borrow_le_Proper : Proper (Basics.flip Z.le ==> Z.le ==> Basics.flip Z.le ==> Z.le) Z.sub_with_borrow.
   Proof. unfold Z.sub_with_borrow, Z.add_with_carry, Basics.flip; repeat (omega || intro). Qed.
   Hint Resolve sub_with_borrow_le_Proper : zarith.
+  Lemma opp_flip_le_le_Proper : Proper (Basics.flip Z.le ==> Z.le) Z.opp.
+  Proof. cbv [Basics.flip]; repeat (lia || intro). Qed.
+  Hint Resolve opp_flip_le_le_Proper : zarith.
+  Lemma opp_le_flip_le_Proper : Proper (Z.le ==> Basics.flip Z.le) Z.opp.
+  Proof. cbv [Basics.flip]; repeat (lia || intro). Qed.
+  Hint Resolve opp_le_flip_le_Proper : zarith.
+  Lemma opp_le_ge_Proper : Proper (Z.le ==> Z.ge) Z.opp.
+  Proof. cbv [Basics.flip]; repeat (lia || intro). Qed.
+  Hint Resolve opp_le_ge_Proper : zarith.
+  Lemma opp_ge_le_Proper : Proper (Z.ge ==> Z.le) Z.opp.
+  Proof. cbv [Basics.flip]; repeat (lia || intro). Qed.
+  Hint Resolve opp_ge_le_Proper : zarith.
+  Lemma add_le_Proper'' x : Proper (Z.le ==> Z.le) (fun y => Z.add y x).
+  Proof. repeat (omega || intro). Qed.
+  Hint Resolve add_le_Proper'' : zarith.
+  Lemma sub_le_ge_Proper_r p : Proper (Z.le ==> Z.ge) (Z.sub p).
+  Proof. repeat (omega || intro). Qed.
+  Hint Resolve sub_le_ge_Proper_r : zarith.
+  Lemma sub_le_le_Proper_l p : Proper (Z.le ==> Z.le) (fun x => Z.sub x p).
+  Proof. repeat (omega || intro). Qed.
+  Hint Resolve sub_le_le_Proper_l : zarith.
+  Lemma sub_le_flip_le_Proper_r p : Proper (Z.le ==> Basics.flip Z.le) (Z.sub p).
+  Proof. unfold Basics.flip; repeat (omega || intro). Qed.
+  Hint Resolve sub_le_flip_le_Proper_r : zarith.
+  Lemma sub_flip_le_le_Proper_r p : Proper (Basics.flip Z.le ==> Z.le) (Z.sub p).
+  Proof. unfold Basics.flip; repeat (omega || intro). Qed.
+  Hint Resolve sub_flip_le_le_Proper_r : zarith.
+  Lemma sub_ge_le_Proper_r p : Proper (Z.ge ==> Z.le) (Z.sub p).
+  Proof. unfold Basics.flip; repeat (omega || intro). Qed.
+  Hint Resolve sub_ge_le_Proper_r : zarith.
+  Lemma mul_Z0_le_Proper : Proper (Z.le ==> Z.le) (Z.mul Z0).
+  Proof. repeat (nia || intro). Qed.
+  Hint Resolve mul_Z0_le_Proper : zarith.
+  Lemma mul_Zneg_le_flip_le_Proper p : Proper (Z.le ==> Basics.flip Z.le) (Z.mul (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zneg_le_flip_le_Proper : zarith.
+  Lemma mul_Zneg_le_ge_Proper p : Proper (Z.le ==> Z.ge) (Z.mul (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zneg_le_ge_Proper : zarith.
+  Lemma mul_Zneg_flip_le_le_Proper p : Proper (Basics.flip Z.le ==> Z.le) (Z.mul (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zneg_flip_le_le_Proper : zarith.
+  Lemma mul_Zneg_ge_le_Proper p : Proper (Z.ge ==> Z.le) (Z.mul (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zneg_ge_le_Proper : zarith.
+  Lemma mul_Zpos_le_Proper' p : Proper (Z.le ==> Z.le) (fun y => Z.mul y (Zpos p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zpos_le_Proper' : zarith.
+  Lemma mul_Z0_le_Proper' : Proper (Z.le ==> Z.le) (fun y => Z.mul y Z0).
+  Proof. repeat (nia || intro). Qed.
+  Hint Resolve mul_Z0_le_Proper' : zarith.
+  Lemma mul_Zneg_le_flip_le_Proper' p : Proper (Z.le ==> Basics.flip Z.le) (fun y => Z.mul y (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zneg_le_flip_le_Proper' : zarith.
+  Lemma mul_Zneg_le_ge_Proper' p : Proper (Z.le ==> Z.ge) (fun y => Z.mul y (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zneg_le_ge_Proper' : zarith.
+  Lemma mul_Zneg_flip_le_le_Proper' p : Proper (Basics.flip Z.le ==> Z.le) (fun y => Z.mul y (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zneg_flip_le_le_Proper' : zarith.
+  Lemma mul_Zneg_ge_le_Proper' p : Proper (Z.ge ==> Z.le) (fun y => Z.mul y (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || intro). Qed.
+  Hint Resolve mul_Zneg_ge_le_Proper' : zarith.
+  Lemma div_Zpos_le_Proper_r p : Proper (Z.le ==> Z.le) (fun x => Z.div x (Zpos p)).
+  Proof. repeat (nia || Z.div_mod_to_quot_rem || intro). Qed.
+  Hint Resolve div_Zpos_le_Proper_r : zarith.
+  Lemma div_Z0_le_Proper_r : Proper (Z.le ==> Z.le) (fun x => Z.div x Z0).
+  Proof. repeat (nia || Z.div_mod_to_quot_rem || intro). Qed.
+  Hint Resolve div_Z0_le_Proper_r : zarith.
+  Lemma div_Zneg_le_flip_le_Proper_r p : Proper (Z.le ==> Basics.flip Z.le) (fun x => Z.div x (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || Z.div_mod_to_quot_rem || intro). Qed.
+  Hint Resolve div_Zneg_le_flip_le_Proper_r : zarith.
+  Lemma div_Zneg_flip_le_le_Proper_r p : Proper (Basics.flip Z.le ==> Z.le) (fun x => Z.div x (Zneg p)).
+  Proof. cbv [Basics.flip]; repeat (nia || Z.div_mod_to_quot_rem || intro). Qed.
+  Hint Resolve div_Zneg_flip_le_le_Proper_r : zarith.
+  Lemma div_Z0_le_Proper_l : Proper (Z.le ==> Z.le) (Z.div Z0).
+  Proof. do 3 intro; destruct_head' Z; cbv; congruence. Qed.
+  Hint Resolve div_Z0_le_Proper_l : zarith.
+  Local Ltac div_Proper_t :=
+    let H := fresh in
+    cbv [Basics.flip]; intros ?? H; apply Pos2Z.pos_le_pos in H;
+    apply Z.div_cross_le_abs; cbn [Z.sgn Z.abs]; try nia.
+  Lemma div_Zpos_Zpos_le_Proper_l p : Proper (Basics.flip Pos.le ==> Z.le) (fun x => Z.div (Zpos p) (Zpos x)).
+  Proof. div_Proper_t. Qed.
+  Hint Resolve div_Zpos_Zpos_le_Proper_l : zarith.
+  Lemma div_Zpos_Zneg_le_Proper_l p : Proper (Pos.le ==> Z.le) (fun x => Z.div (Zpos p) (Zneg x)).
+  Proof. div_Proper_t. Qed.
+  Hint Resolve div_Zpos_Zneg_le_Proper_l : zarith.
+  Lemma div_Zneg_Zpos_le_Proper_l p : Proper (Pos.le ==> Z.le) (fun x => Z.div (Zneg p) (Zpos x)).
+  Proof. div_Proper_t. Qed.
+  Hint Resolve div_Zneg_Zpos_le_Proper_l : zarith.
+  Lemma div_Zneg_Zneg_le_Proper_l p : Proper (Basics.flip Pos.le ==> Z.le) (fun x => Z.div (Zneg p) (Zneg x)).
+  Proof. div_Proper_t. Qed.
+  Hint Resolve div_Zneg_Zneg_le_Proper_l : zarith.
+  Lemma div_Zpos_Zpos_le_Proper_r x : Proper (Pos.le ==> Z.le) (fun p => Z.div (Zpos p) (Zpos x)).
+  Proof. div_Proper_t. Qed.
+  Hint Resolve div_Zpos_Zpos_le_Proper_r : zarith.
+  Lemma div_Zpos_Zneg_le_Proper_r x : Proper (Basics.flip Pos.le ==> Z.le) (fun p => Z.div (Zpos p) (Zneg x)).
+  Proof. div_Proper_t. Qed.
+  Hint Resolve div_Zpos_Zneg_le_Proper_r : zarith.
+  Lemma div_Zneg_Zpos_le_Proper_r x : Proper (Basics.flip Pos.le ==> Z.le) (fun p => Z.div (Zneg p) (Zpos x)).
+  Proof. div_Proper_t. Qed.
+  Hint Resolve div_Zneg_Zpos_le_Proper_r : zarith.
+  Lemma div_Zneg_Zneg_le_Proper_r x : Proper (Pos.le ==> Z.le) (fun p => Z.div (Zneg p) (Zneg x)).
+  Proof. div_Proper_t. Qed.
+  Hint Resolve div_Zneg_Zneg_le_Proper_r : zarith.
+  Local Ltac shift_t :=
+    repeat first [ progress intros
+                 | progress cbv [Proper respectful Basics.flip] in *
+                 | progress rewrite ?Z.shiftr_div_pow2, ?Z.shiftr_mul_pow2, ?Z.shiftl_div_pow2, ?Z.shiftl_mul_pow2, ?Z.div_1_r, ?Zdiv_0_l by lia
+                 | progress (cbn [Z.pow Z.opp]; change Z.pow_pos with (fun x p => Z.pow x (Zpos p)); cbn beta)
+                 | progress Z.peel_le
+                 | nia
+                 | match goal with
+                   | [ |- context[(2^Zpos ?p)%Z] ] => unique assert (0 < 2^Zpos p)%Z by (apply Z.pow_pos_nonneg; lia)
+                   | [ |- (?x / ?a <= ?x * ?b)%Z ] => transitivity x
+                   | [ |- (?x * ?a <= ?x / ?b)%Z ] => transitivity x
+                   | [ H : (0 > Z.neg _)%Z |- _ ] => clear H
+                   | [ H : (Zneg ?a <= Zneg ?b)%Z |- _ ] => assert ((Zpos b <= Zpos a)%Z) by lia; clear H
+                   | [ H : (?a <= ?b)%Z |- context[(2^?a)%Z] ]
+                     => unique assert (2^a <= 2^b)%Z by (apply Z.pow_le_mono_r; lia); clear H
+                   | [ |- context[(2^Zpos ?a)%Z] ] => generalize dependent (2^Zpos a)%Z; clear a
+                   end
+                 | progress destruct_head' Z
+                 | Z.div_mod_to_quot_rem; nia
+                 | apply Z.div_cross_le_abs; cbn [Z.sgn Z.abs]; nia ].
+  Lemma shiftr_le_Proper_l : forall y : Z, Proper (Z.le ==> Z.le) (fun x : Z => Z.shiftr x y).
+  Proof. shift_t. Qed.
+  Hint Resolve shiftr_le_Proper_l : zarith.
+  Lemma shiftl_le_Proper_l : forall y : Z, Proper (Z.le ==> Z.le) (fun x : Z => Z.shiftl x y).
+  Proof. shift_t. Qed.
+  Hint Resolve shiftl_le_Proper_l : zarith.
+  Lemma shiftr_le_Proper_r x
+        (R := fun b : bool => if b then Basics.flip Z.le else Z.le)
+    : Proper (R (0 <=? x)%Z ==> Z.le) (Z.shiftr x).
+  Proof. subst R; cbv beta; break_match; Z.ltb_to_lt; shift_t. Qed.
+  Hint Resolve shiftr_le_Proper_r : zarith.
+  Lemma shiftl_le_Proper_r x
+        (R := fun b : bool => if b then Z.le else Basics.flip Z.le)
+    : Proper (R (0 <=? x)%Z ==> Z.le) (Z.shiftl x).
+  Proof. subst R; cbv beta; break_match; Z.ltb_to_lt; shift_t. Qed.
+  Hint Resolve shiftl_le_Proper_r : zarith.
+  Local Ltac shift_Proper_t' :=
+    let H := fresh in
+    cbv [Basics.flip]; intros ?? H; apply Pos2Z.pos_le_pos in H;
+    try ((apply shiftr_le_Proper_r + apply shiftr_le_Proper_l + apply shiftl_le_Proper_r + apply shiftl_le_Proper_l);
+         cbv [Z.leb Z.compare Basics.flip];
+         lia).
+  Lemma shiftr_Zpos_Zpos_le_Proper_l p : Proper (Basics.flip Pos.le ==> Z.le) (fun x => Z.shiftr (Zpos p) (Zpos x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftr_Zpos_Zpos_le_Proper_l : zarith.
+  Lemma shiftr_Zpos_Zneg_le_Proper_l p : Proper (Pos.le ==> Z.le) (fun x => Z.shiftr (Zpos p) (Zneg x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftr_Zpos_Zneg_le_Proper_l : zarith.
+  Lemma shiftr_Zneg_Zpos_le_Proper_l p : Proper (Pos.le ==> Z.le) (fun x => Z.shiftr (Zneg p) (Zpos x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftr_Zneg_Zpos_le_Proper_l : zarith.
+  Lemma shiftr_Zneg_Zneg_le_Proper_l p : Proper (Basics.flip Pos.le ==> Z.le) (fun x => Z.shiftr (Zneg p) (Zneg x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftr_Zneg_Zneg_le_Proper_l : zarith.
+  Lemma shiftr_Zpos_Zpos_le_Proper_r x : Proper (Pos.le ==> Z.le) (fun p => Z.shiftr (Zpos p) (Zpos x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftr_Zpos_Zpos_le_Proper_r : zarith.
+  Lemma shiftr_Zpos_Zneg_le_Proper_r x : Proper (Pos.le ==> Z.le) (fun p => Z.shiftr (Zpos p) (Zneg x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftr_Zpos_Zneg_le_Proper_r : zarith.
+  Lemma shiftr_Zneg_Zpos_le_Proper_r x : Proper (Basics.flip Pos.le ==> Z.le) (fun p => Z.shiftr (Zneg p) (Zpos x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftr_Zneg_Zpos_le_Proper_r : zarith.
+  Lemma shiftr_Zneg_Zneg_le_Proper_r x : Proper (Basics.flip Pos.le ==> Z.le) (fun p => Z.shiftr (Zneg p) (Zneg x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftr_Zneg_Zneg_le_Proper_r : zarith.
+  Lemma shiftl_Zpos_Zpos_le_Proper_l p : Proper (Pos.le ==> Z.le) (fun x => Z.shiftl (Zpos p) (Zpos x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftl_Zpos_Zpos_le_Proper_l : zarith.
+  Lemma shiftl_Zpos_Zneg_le_Proper_l p : Proper (Basics.flip Pos.le ==> Z.le) (fun x => Z.shiftl (Zpos p) (Zneg x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftl_Zpos_Zneg_le_Proper_l : zarith.
+  Lemma shiftl_Zneg_Zpos_le_Proper_l p : Proper (Basics.flip Pos.le ==> Z.le) (fun x => Z.shiftl (Zneg p) (Zpos x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftl_Zneg_Zpos_le_Proper_l : zarith.
+  Lemma shiftl_Zneg_Zneg_le_Proper_l p : Proper (Pos.le ==> Z.le) (fun x => Z.shiftl (Zneg p) (Zneg x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftl_Zneg_Zneg_le_Proper_l : zarith.
+  Lemma shiftl_Zpos_Zpos_le_Proper_r x : Proper (Pos.le ==> Z.le) (fun p => Z.shiftl (Zpos p) (Zpos x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftl_Zpos_Zpos_le_Proper_r : zarith.
+  Lemma shiftl_Zpos_Zneg_le_Proper_r x : Proper (Pos.le ==> Z.le) (fun p => Z.shiftl (Zpos p) (Zneg x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftl_Zpos_Zneg_le_Proper_r : zarith.
+  Lemma shiftl_Zneg_Zpos_le_Proper_r x : Proper (Basics.flip Pos.le ==> Z.le) (fun p => Z.shiftl (Zneg p) (Zpos x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftl_Zneg_Zpos_le_Proper_r : zarith.
+  Lemma shiftl_Zneg_Zneg_le_Proper_r x : Proper (Basics.flip Pos.le ==> Z.le) (fun p => Z.shiftl (Zneg p) (Zneg x)).
+  Proof. shift_Proper_t'. Qed.
+  Hint Resolve shiftl_Zneg_Zneg_le_Proper_r : zarith.
 End Z.