aboutsummaryrefslogtreecommitdiff
path: root/src/Experiments/NewPipeline/Toplevel1.v
diff options
context:
space:
mode:
authorGravatar Jason Gross <jgross@mit.edu>2018-06-19 00:03:37 -0400
committerGravatar Jason Gross <jasongross9@gmail.com>2018-07-21 03:47:14 +0100
commit875789c7756941296306b6781142f62d0d5e5fbe (patch)
tree9af2eb874de18744ffd66df9a8b8a85f642fe2dc /src/Experiments/NewPipeline/Toplevel1.v
parentcb1449271906998bb29c00d68c0bee4b58d2803c (diff)
Montgomery reduction in new pipeline
After | File Name | Before || Change | % Change -------------------------------------------------------------------------------------------------------- 18m19.81s | Total | 14m31.66s || +3m48.14s | +26.17% -------------------------------------------------------------------------------------------------------- 4m04.77s | Experiments/NewPipeline/Toplevel1 | 1m38.04s || +2m26.73s | +149.66% 5m12.44s | Experiments/NewPipeline/Rewriter | 4m20.00s || +0m52.43s | +20.16% 1m26.58s | Experiments/NewPipeline/Arithmetic | 0m55.51s || +0m31.07s | +55.97% 5m44.19s | Experiments/NewPipeline/SlowPrimeSynthesisExamples | 5m45.62s || -0m01.43s | -0.41% 1m29.48s | Experiments/NewPipeline/Toplevel2 | 1m29.73s || -0m00.25s | -0.27% 0m12.75s | Experiments/NewPipeline/CStringification | 0m12.71s || +0m00.03s | +0.31% 0m01.32s | Experiments/NewPipeline/GENERATEDIdentifiersWithoutTypes | 0m01.20s || +0m00.12s | +10.00% 0m01.31s | Experiments/NewPipeline/CLI | 0m01.33s || -0m00.02s | -1.50% 0m01.18s | Experiments/NewPipeline/StandaloneHaskellMain | 0m01.22s || -0m00.04s | -3.27% 0m01.12s | Experiments/NewPipeline/StandaloneOCamlMain | 0m01.21s || -0m00.08s | -7.43% 0m01.11s | Experiments/NewPipeline/Language | 0m01.14s || -0m00.02s | -2.63% 0m01.08s | Experiments/NewPipeline/AbstractInterpretation | 0m01.16s || -0m00.07s | -6.89% 0m00.90s | Experiments/NewPipeline/MiscCompilerPasses | 0m00.87s || +0m00.03s | +3.44% 0m00.74s | Experiments/NewPipeline/CompilersTestCases | 0m01.03s || -0m00.29s | -28.15% 0m00.44s | Experiments/NewPipeline/AbstractInterpretationProofs | 0m00.40s || +0m00.03s | +9.99% 0m00.41s | Experiments/NewPipeline/UnderLets | 0m00.50s || -0m00.09s | -18.00% After | File Name | Before || Change | % Change ------------------------------------------------------------------------------------------------------------------------- 107m58.13s | Total | 102m35.85s || +5m22.27s | +5.23% ------------------------------------------------------------------------------------------------------------------------- 4m32.58s | Experiments/NewPipeline/Toplevel1 | 1m50.07s || +2m42.50s | +147.64% N/A | ─abstract | 1m54.94s || -1m54.93s | -100.00% 1m54.19s | Specific/X2448/Karatsuba/C64/femul | N/A || +1m54.18s | ∞ 7m58.19s | Experiments/NewPipeline/Rewriter | 6m45.32s || +1m12.87s | +17.97% 2m13.30s | Experiments/NewPipeline/Arithmetic | 1m34.69s || +0m38.61s | +40.77% 5m30.50s | Curves/Weierstrass/Projective | 5m09.44s || +0m21.06s | +6.80% 12m00.73s | Curves/Weierstrass/AffineProofs | 11m43.07s || +0m17.65s | +2.51% 0m54.76s | Compilers/Z/ArithmeticSimplifierWf | 0m43.68s || +0m11.07s | +25.36% 10m06.67s | Experiments/SimplyTypedArithmetic | 9m58.44s || +0m08.22s | +1.37% 1m05.15s | Arithmetic/Karatsuba | 0m58.76s || +0m06.39s | +10.87% 0m41.15s | Specific/NISTP256/AMD128/femul | 0m47.16s || -0m06.00s | -12.74% 5m46.39s | Experiments/NewPipeline/SlowPrimeSynthesisExamples | 5m52.03s || -0m05.63s | -1.60% 2m14.99s | Specific/X25519/C64/ladderstep | 2m20.69s || -0m05.69s | -4.05% 0m48.64s | Specific/X25519/C32/freeze | 0m43.24s || +0m05.39s | +12.48% 0m26.80s | Specific/X25519/C64/fesquare | 0m20.83s || +0m05.97s | +28.66% 0m27.22s | Specific/X25519/C32/feadd | 0m31.34s || -0m04.12s | -13.14% 0m23.26s | Specific/NISTP256/AMD64/fenz | 0m19.10s || +0m04.16s | +21.78% 0m21.24s | Specific/NISTP256/AMD128/fesub | 0m25.24s || -0m04.00s | -15.84% 3m38.32s | Curves/Montgomery/XZProofs | 3m34.65s || +0m03.66s | +1.70% 1m14.93s | Compilers/Z/ArithmeticSimplifierInterp | 1m11.88s || +0m03.05s | +4.24% 0m16.16s | Arithmetic/Saturated/MontgomeryAPI | 0m12.26s || +0m03.90s | +31.81% 0m07.54s | Compilers/Z/Bounds/InterpretationLemmas/PullCast | 0m10.65s || -0m03.11s | -29.20% 2m29.22s | Specific/NISTP256/AMD64/femul | 2m31.90s || -0m02.68s | -1.76% 2m02.88s | Compilers/Named/MapCastInterp | 2m00.84s || +0m02.03s | +1.68% 1m54.19s | Curves/Weierstrass/Jacobian | 1m52.12s || +0m02.06s | +1.84% 1m30.98s | Specific/X25519/C32/femul | 1m28.28s || +0m02.70s | +3.05% 1m30.59s | Experiments/NewPipeline/Toplevel2 | 1m32.97s || -0m02.37s | -2.55% 1m20.73s | Demo | 1m18.51s || +0m02.21s | +2.82% 1m07.85s | Specific/X25519/C32/fesquare | 1m09.85s || -0m02.00s | -2.86% 0m31.78s | Specific/X25519/C32/fesub | 0m34.25s || -0m02.46s | -7.21% 0m31.18s | Arithmetic/Core | 0m33.92s || -0m02.74s | -8.07% 0m26.24s | Compilers/Z/CNotations | 0m28.35s || -0m02.11s | -7.44% 0m22.15s | Specific/X25519/C64/fecarry | 0m19.73s || +0m02.41s | +12.26% 0m21.61s | Arithmetic/Saturated/AddSub | 0m18.87s || +0m02.73s | +14.52% 0m21.58s | Specific/X25519/C64/fesub | 0m19.14s || +0m02.43s | +12.74% 0m14.37s | Arithmetic/Saturated/Core | 0m16.57s || -0m02.20s | -13.27% 2m57.98s | Curves/Montgomery/AffineProofs | 2m59.71s || -0m01.73s | -0.96% 1m46.10s | Spec/Test/X25519 | 1m47.38s || -0m01.28s | -1.19% 0m40.69s | Primitives/EdDSARepChange | 0m42.34s || -0m01.65s | -3.89% 0m40.29s | Specific/X25519/C32/fecarry | 0m42.21s || -0m01.92s | -4.54% 0m33.64s | Arithmetic/MontgomeryReduction/WordByWord/Abstract/Dependent/Proofs | 0m31.88s || +0m01.76s | +5.52% 0m31.96s | Specific/NISTP256/AMD64/feadd | 0m30.27s || +0m01.69s | +5.58% 0m23.14s | Specific/NISTP256/AMD128/feadd | 0m24.34s || -0m01.19s | -4.93% 0m18.76s | Specific/NISTP256/AMD128/feopp | 0m20.20s || -0m01.43s | -7.12% 0m18.62s | Compilers/Z/Syntax/Equality | 0m17.08s || +0m01.54s | +9.01% 0m15.06s | Util/ZUtil | 0m13.95s || +0m01.11s | +7.95% 0m14.13s | LegacyArithmetic/ArchitectureToZLikeProofs | 0m12.75s || +0m01.38s | +10.82% 0m12.43s | Compilers/Named/CompileInterpSideConditions | 0m10.85s || +0m01.58s | +14.56% 0m10.06s | Specific/NISTP256/AMD64/Synthesis | 0m11.31s || -0m01.25s | -11.05% 0m08.04s | Arithmetic/BarrettReduction/Generalized | 0m09.68s || -0m01.64s | -16.94% 0m06.25s | Specific/Framework/ArithmeticSynthesis/Montgomery | 0m05.18s || +0m01.07s | +20.65% 0m05.70s | LegacyArithmetic/InterfaceProofs | 0m07.21s || -0m01.50s | -20.94% 0m05.50s | Compilers/Z/Bounds/Pipeline/Definition | 0m06.57s || -0m01.07s | -16.28% 0m04.54s | LegacyArithmetic/Double/Proofs/Decode | 0m05.59s || -0m01.04s | -18.78% 0m04.32s | Compilers/Z/ArithmeticSimplifier | 0m05.36s || -0m01.04s | -19.40% 0m02.15s | Specific/Framework/ArithmeticSynthesis/Defaults | 0m03.49s || -0m01.34s | -38.39% N/A | Coqprime/PrimalityTest/EGroup | 0m01.32s || -0m01.32s | -100.00% N/A | Coqprime/Z/ZCAux | 0m01.08s || -0m01.08s | -100.00% 1m21.20s | Compilers/Z/Named/RewriteAddToAdcInterp | 1m21.80s || -0m00.59s | -0.73% 0m43.90s | Spec/Ed25519 | 0m43.40s || +0m00.50s | +1.15% 0m40.68s | Compilers/CommonSubexpressionEliminationWf | 0m40.81s || -0m00.13s | -0.31% 0m34.84s | Specific/NISTP256/AMD64/fesub | 0m33.87s || +0m00.97s | +2.86% 0m32.80s | Specific/X25519/C64/femul | 0m31.99s || +0m00.80s | +2.53% 0m30.69s | Curves/Edwards/XYZT/Basic | 0m30.20s || +0m00.49s | +1.62% 0m27.90s | Compilers/Named/MapCastWf | 0m27.10s || +0m00.79s | +2.95% 0m27.80s | Specific/X25519/C32/Synthesis | 0m28.14s || -0m00.33s | -1.20% 0m27.70s | bbv/Word | 0m27.58s || +0m00.12s | +0.43% 0m26.05s | Specific/NISTP256/AMD64/feopp | 0m26.52s || -0m00.46s | -1.77% 0m25.59s | Specific/X25519/C64/freeze | 0m25.20s || +0m00.39s | +1.54% 0m25.40s | Curves/Edwards/AffineProofs | 0m24.70s || +0m00.69s | +2.83% 0m22.94s | Compilers/Named/ContextProperties/NameUtil | 0m23.02s || -0m00.07s | -0.34% 0m22.14s | Algebra/Field | 0m21.80s || +0m00.33s | +1.55% 0m21.99s | Specific/NISTP256/AMD128/fenz | 0m21.30s || +0m00.68s | +3.23% 0m21.68s | Compilers/Named/ContextProperties/SmartMap | 0m22.15s || -0m00.46s | -2.12% 0m20.08s | Experiments/NewPipeline/CStringification | 0m19.13s || +0m00.94s | +4.96% 0m19.91s | Arithmetic/MontgomeryReduction/WordByWord/Abstract/Proofs | 0m19.60s || +0m00.30s | +1.58% 0m19.57s | Specific/X25519/C64/feadd | 0m19.12s || +0m00.44s | +2.35% 0m17.58s | Primitives/MxDHRepChange | 0m17.59s || -0m00.01s | -0.05% 0m17.56s | LegacyArithmetic/Double/Proofs/Multiply | 0m18.42s || -0m00.86s | -4.66% 0m15.44s | Arithmetic/MontgomeryReduction/Proofs | 0m14.96s || +0m00.47s | +3.20% 0m14.54s | Specific/X2448/Karatsuba/C64/Synthesis | 0m14.15s || +0m00.38s | +2.75% 0m14.18s | LegacyArithmetic/Double/Proofs/ShiftRightDoubleWordImmediate | 0m13.57s || +0m00.60s | +4.49% 0m13.88s | Algebra/Ring | 0m13.58s || +0m00.30s | +2.20% 0m13.44s | LegacyArithmetic/Double/Proofs/SpreadLeftImmediate | 0m13.40s || +0m00.03s | +0.29% 0m11.85s | LegacyArithmetic/Double/Proofs/RippleCarryAddSub | 0m11.82s || +0m00.02s | +0.25% 0m11.46s | Compilers/InlineConstAndOpWf | 0m11.58s || -0m00.11s | -1.03% 0m11.43s | Compilers/Named/RegisterAssignInterp | 0m11.26s || +0m00.16s | +1.50% 0m11.29s | Arithmetic/BarrettReduction/RidiculousFish | 0m10.73s || +0m00.55s | +5.21% 0m10.27s | Arithmetic/Saturated/MulSplit | 0m10.24s || +0m00.02s | +0.29% 0m10.07s | Util/ZUtil/ZSimplify/Autogenerated | 0m09.74s || +0m00.33s | +3.38% 0m09.72s | Util/FixedWordSizesEquality | 0m10.08s || -0m00.35s | -3.57% 0m09.25s | LegacyArithmetic/Pow2BaseProofs | 0m09.10s || +0m00.15s | +1.64% 0m08.74s | Compilers/InlineWf | 0m08.45s || +0m00.29s | +3.43% 0m08.65s | Util/FsatzAutoLemmas | 0m08.94s || -0m00.28s | -3.24% 0m08.30s | Util/ListUtil | 0m08.37s || -0m00.06s | -0.83% 0m08.12s | Compilers/LinearizeWf | 0m08.43s || -0m00.31s | -3.67% 0m07.92s | Specific/X25519/C64/Synthesis | 0m07.90s || +0m00.01s | +0.25% 0m07.72s | Arithmetic/BarrettReduction/HAC | 0m07.57s || +0m00.14s | +1.98% 0m07.64s | Compilers/Z/HexNotationConstants | 0m08.06s || -0m00.42s | -5.21% 0m07.62s | Util/ZUtil/Modulo | 0m07.58s || +0m00.04s | +0.52% 0m07.54s | Curves/Edwards/Pre | 0m07.92s || -0m00.37s | -4.79% 0m07.34s | Compilers/WfProofs | 0m06.72s || +0m00.62s | +9.22% 0m06.86s | Algebra/Field_test | 0m07.34s || -0m00.47s | -6.53% 0m06.80s | Compilers/Z/BinaryNotationConstants | 0m06.76s || +0m00.04s | +0.59% 0m06.00s | LegacyArithmetic/Double/Proofs/ShiftRight | 0m06.00s || +0m00.00s | +0.00% 0m05.58s | Compilers/Named/CompileWf | 0m05.85s || -0m00.26s | -4.61% 0m05.58s | Curves/Montgomery/Affine | 0m06.52s || -0m00.93s | -14.41% 0m05.31s | Specific/NISTP256/AMD128/Synthesis | 0m04.90s || +0m00.40s | +8.36% 0m05.17s | LegacyArithmetic/Double/Proofs/ShiftLeft | 0m05.14s || +0m00.03s | +0.58% 0m05.14s | Arithmetic/ModularArithmeticTheorems | 0m05.32s || -0m00.18s | -3.38% 0m04.93s | LegacyArithmetic/ZBoundedZ | 0m05.51s || -0m00.58s | -10.52% 0m04.90s | Compilers/Z/Bounds/InterpretationLemmas/IsBoundedBy | 0m05.62s || -0m00.71s | -12.81% 0m04.76s | Compilers/TestCase | 0m04.72s || +0m00.04s | +0.84% 0m04.74s | Arithmetic/MontgomeryReduction/WordByWord/Proofs | 0m05.51s || -0m00.76s | -13.97% 0m04.48s | Util/WordUtil | 0m04.51s || -0m00.02s | -0.66% 0m04.32s | Spec/MontgomeryCurve | 0m03.77s || +0m00.55s | +14.58% 0m04.13s | Compilers/InlineInterp | 0m04.29s || -0m00.16s | -3.72% 0m04.09s | Util/ZUtil/Div | 0m03.82s || +0m00.27s | +7.06% 0m03.96s | LegacyArithmetic/BarretReduction | 0m04.49s || -0m00.53s | -11.80% 0m03.93s | Compilers/EtaWf | 0m03.94s || -0m00.00s | -0.25% 0m03.81s | Compilers/Named/ContextProperties | 0m04.33s || -0m00.52s | -12.00% 0m03.69s | Specific/NISTP256/FancyMachine256/Montgomery | 0m03.77s || -0m00.08s | -2.12% 0m03.65s | Algebra/Group | 0m03.95s || -0m00.30s | -7.59% 0m03.63s | Arithmetic/Saturated/Freeze | 0m03.63s || +0m00.00s | +0.00% 0m03.54s | Compilers/Z/RewriteAddToAdcInterp | 0m03.26s || +0m00.28s | +8.58% 0m03.49s | Compilers/Named/CompileInterp | 0m03.55s || -0m00.05s | -1.69% 0m03.47s | Compilers/Z/Bounds/Relax | 0m03.12s || +0m00.35s | +11.21% 0m03.31s | Specific/NISTP256/FancyMachine256/Barrett | 0m03.70s || -0m00.39s | -10.54% 0m03.21s | Compilers/Named/NameUtilProperties | 0m03.16s || +0m00.04s | +1.58% 0m03.15s | Specific/NISTP256/FancyMachine256/Core | 0m02.96s || +0m00.18s | +6.41% 0m03.14s | Compilers/Named/ContextProperties/Proper | 0m03.67s || -0m00.52s | -14.44% 0m03.06s | Compilers/Z/JavaNotations | 0m03.18s || -0m00.12s | -3.77% 0m03.00s | Compilers/CommonSubexpressionEliminationProperties | 0m02.91s || +0m00.08s | +3.09% 0m02.94s | Compilers/WfReflective | 0m02.18s || +0m00.75s | +34.86% 0m02.91s | Util/ZUtil/Quot | 0m02.24s || +0m00.67s | +29.91% 0m02.80s | Arithmetic/CoreUnfolder | 0m02.53s || +0m00.27s | +10.67% 0m02.78s | Util/ZUtil/AddGetCarry | 0m02.78s || +0m00.00s | +0.00% 0m02.67s | Spec/WeierstrassCurve | 0m02.45s || +0m00.21s | +8.97% 0m02.54s | Compilers/Named/WfFromUnit | 0m02.61s || -0m00.06s | -2.68% 0m02.51s | Specific/Framework/ReificationTypes | 0m02.57s || -0m00.06s | -2.33% 0m02.45s | Arithmetic/BarrettReduction/Wikipedia | 0m02.72s || -0m00.27s | -9.92% 0m02.41s | Specific/Framework/OutputType | 0m02.49s || -0m00.08s | -3.21% 0m02.35s | Compilers/Named/InterpretToPHOASWf | 0m02.44s || -0m00.08s | -3.68% 0m02.31s | Util/NatUtil | 0m02.31s || +0m00.00s | +0.00% 0m02.26s | LegacyArithmetic/MontgomeryReduction | 0m02.40s || -0m00.14s | -5.83% 0m02.25s | Util/ZUtil/Pow2Mod | 0m02.19s || +0m00.06s | +2.73% 0m02.21s | Specific/Framework/ArithmeticSynthesis/Base | 0m02.23s || -0m00.02s | -0.89% 0m02.20s | Curves/Edwards/XYZT/Precomputed | 0m02.07s || +0m00.13s | +6.28% 0m02.16s | Arithmetic/PrimeFieldTheorems | 0m01.58s || +0m00.58s | +36.70% 0m02.16s | LegacyArithmetic/Double/Proofs/BitwiseOr | 0m02.20s || -0m00.04s | -1.81% 0m02.12s | LegacyArithmetic/Double/Proofs/LoadImmediate | 0m02.20s || -0m00.08s | -3.63% 0m02.06s | Util/QUtil | 0m02.08s || -0m00.02s | -0.96% 0m02.03s | Compilers/Relations | 0m02.31s || -0m00.28s | -12.12% 0m02.02s | Experiments/NewPipeline/GENERATEDIdentifiersWithoutTypes | 0m01.99s || +0m00.03s | +1.50% 0m02.00s | Util/Tuple | 0m01.75s || +0m00.25s | +14.28% 0m01.87s | Algebra/ScalarMult | 0m01.76s || +0m00.11s | +6.25% 0m01.82s | Arithmetic/Saturated/CoreUnfolder | 0m01.76s || +0m00.06s | +3.40% 0m01.82s | Experiments/NewPipeline/StandaloneOCamlMain | 0m01.43s || +0m00.39s | +27.27% 0m01.82s | LegacyArithmetic/BaseSystemProofs | 0m01.98s || -0m00.15s | -8.08% 0m01.80s | Compilers/LinearizeInterp | 0m01.76s || +0m00.04s | +2.27% 0m01.80s | Experiments/NewPipeline/StandaloneHaskellMain | 0m01.47s || +0m00.33s | +22.44% 0m01.76s | Compilers/MultiSizeTest | 0m01.78s || -0m00.02s | -1.12% 0m01.76s | Compilers/Z/RewriteAddToAdcWf | 0m01.70s || +0m00.06s | +3.52% 0m01.76s | Experiments/NewPipeline/Language | 0m01.67s || +0m00.09s | +5.38% 0m01.72s | Experiments/NewPipeline/AbstractInterpretation | 0m01.72s || +0m00.00s | +0.00% 0m01.66s | Util/ZUtil/Stabilization | 0m01.55s || +0m00.10s | +7.09% 0m01.64s | Specific/Framework/IntegrationTestDisplayCommon | 0m01.75s || -0m00.11s | -6.28% 0m01.58s | Compilers/Named/InterpretToPHOASInterp | 0m01.59s || -0m00.01s | -0.62% 0m01.54s | Util/ZUtil/Modulo/PullPush | 0m01.26s || +0m00.28s | +22.22% 0m01.51s | Util/NumTheoryUtil | 0m01.33s || +0m00.17s | +13.53% 0m01.51s | Util/ZRange/CornersMonotoneBounds | 0m01.88s || -0m00.36s | -19.68% 0m01.45s | Arithmetic/Saturated/UniformWeight | 0m01.30s || +0m00.14s | +11.53% 0m01.42s | Specific/Framework/ArithmeticSynthesis/Karatsuba | 0m01.49s || -0m00.07s | -4.69% 0m01.37s | Compilers/Z/CommonSubexpressionElimination | 0m01.45s || -0m00.07s | -5.51% 0m01.36s | Compilers/MapCastByDeBruijnInterp | 0m01.32s || +0m00.04s | +3.03% 0m01.34s | Specific/X25519/C32/CurveParameters | 0m01.25s || +0m00.09s | +7.20% 0m01.32s | Compilers/Z/Syntax/Util | 0m01.12s || +0m00.19s | +17.85% 0m01.32s | Specific/Framework/ArithmeticSynthesis/Freeze | 0m00.90s || +0m00.42s | +46.66% 0m01.31s | Algebra/IntegralDomain | 0m01.31s || +0m00.00s | +0.00% 0m01.31s | Arithmetic/Saturated/MulSplitUnfolder | 0m01.32s || -0m00.01s | -0.75% 0m01.31s | Compilers/Named/CompileProperties | 0m01.30s || +0m00.01s | +0.76% 0m01.31s | Util/ZUtil/Testbit | 0m01.66s || -0m00.34s | -21.08% 0m01.30s | Compilers/Z/Bounds/Pipeline/ReflectiveTactics | 0m01.29s || +0m00.01s | +0.77% 0m01.30s | Experiments/NewPipeline/CLI | 0m01.28s || +0m00.02s | +1.56% 0m01.27s | bbv/NatLib | 0m01.06s || +0m00.20s | +19.81% 0m01.26s | Arithmetic/Saturated/FreezeUnfolder | 0m00.84s || +0m00.42s | +50.00% 0m01.24s | Specific/Framework/IntegrationTestTemporaryMiscCommon | 0m01.31s || -0m00.07s | -5.34% 0m01.22s | Util/ZUtil/EquivModulo | 0m01.16s || +0m00.06s | +5.17% 0m01.21s | Specific/Framework/MontgomeryReificationTypes | 0m01.19s || +0m00.02s | +1.68% 0m01.19s | Specific/Framework/ReificationTypesPackage | 0m00.85s || +0m00.34s | +40.00% 0m01.19s | Specific/Framework/SynthesisFramework | 0m01.04s || +0m00.14s | +14.42% 0m01.17s | Experiments/NewPipeline/MiscCompilerPasses | 0m01.25s || -0m00.08s | -6.40% 0m01.15s | Compilers/Named/AListContext | 0m01.08s || +0m00.06s | +6.48% 0m01.14s | Arithmetic/MontgomeryReduction/WordByWord/Definition | 0m01.18s || -0m00.04s | -3.38% 0m01.14s | Arithmetic/Saturated/Wrappers | 0m00.85s || +0m00.28s | +34.11% 0m01.14s | Specific/Framework/ArithmeticSynthesis/HelperTactics | 0m01.12s || +0m00.01s | +1.78% 0m01.14s | Util/PartiallyReifiedProp | 0m01.12s || +0m00.01s | +1.78% 0m01.14s | Util/ZRange/BasicLemmas | 0m01.26s || -0m00.12s | -9.52% 0m01.13s | Specific/Framework/ArithmeticSynthesis/DefaultsPackage | 0m00.86s || +0m00.26s | +31.39% 0m01.12s | Compilers/InlineConstAndOpInterp | 0m00.90s || +0m00.22s | +24.44% 0m01.12s | Compilers/WfInversion | 0m01.18s || -0m00.05s | -5.08% 0m01.12s | Specific/Framework/ArithmeticSynthesis/FreezePackage | 0m00.77s || +0m00.35s | +45.45% 0m01.11s | Specific/Framework/ArithmeticSynthesis/SquareFromMul | 0m01.13s || -0m00.01s | -1.76% 0m01.08s | Compilers/Named/FMapContext | 0m01.27s || -0m00.18s | -14.96% 0m01.08s | Curves/Montgomery/AffineInstances | 0m01.16s || -0m00.07s | -6.89% 0m01.08s | Util/ZUtil/Peano | 0m01.10s || -0m00.02s | -1.81% 0m01.08s | Util/ZUtil/ZSimplify/Simple | 0m00.88s || +0m00.20s | +22.72% 0m01.07s | Specific/Framework/ArithmeticSynthesis/BasePackage | 0m01.14s || -0m00.06s | -6.14% 0m01.06s | LegacyArithmetic/Double/Proofs/SelectConditional | 0m01.09s || -0m00.03s | -2.75% 0m01.04s | Compilers/InterpByIsoProofs | 0m01.16s || -0m00.11s | -10.34% 0m01.03s | Compilers/SmartMap | 0m01.04s || -0m00.01s | -0.96% 0m01.03s | Compilers/Z/Bounds/Pipeline | 0m00.85s || +0m00.18s | +21.17% 0m01.03s | Util/ZUtil/Morphisms | 0m01.23s || -0m00.19s | -16.26% 0m01.02s | Curves/Montgomery/XZ | 0m00.96s || +0m00.06s | +6.25% 0m01.01s | Arithmetic/Saturated/WrappersUnfolder | 0m01.59s || -0m00.58s | -36.47% 0m01.01s | Compilers/Named/InterpSideConditionsInterp | 0m01.12s || -0m00.11s | -9.82% 0m01.00s | Util/CPSUtil | 0m01.09s || -0m00.09s | -8.25% 0m00.99s | Compilers/CommonSubexpressionElimination | 0m00.78s || +0m00.20s | +26.92% 0m00.96s | Util/ZUtil/CC | 0m00.89s || +0m00.06s | +7.86% 0m00.95s | Compilers/MapBaseTypeWf | 0m00.78s || +0m00.16s | +21.79% 0m00.95s | Specific/Framework/ArithmeticSynthesis/LadderstepPackage | 0m01.10s || -0m00.15s | -13.63% 0m00.94s | Compilers/Z/Reify | 0m00.96s || -0m00.02s | -2.08% 0m00.93s | Compilers/Z/Bounds/Pipeline/Glue | 0m00.88s || +0m00.05s | +5.68% 0m00.92s | Arithmetic/Saturated/UniformWeightInstances | 0m01.10s || -0m00.18s | -16.36% 0m00.92s | Compilers/Z/Bounds/MapCastByDeBruijnInterp | 0m00.90s || +0m00.02s | +2.22% 0m00.89s | Compilers/Z/MapCastByDeBruijnInterp | 0m00.87s || +0m00.02s | +2.29% 0m00.89s | Curves/Weierstrass/Affine | 0m00.79s || +0m00.09s | +12.65% 0m00.89s | Specific/Framework/ArithmeticSynthesis/KaratsubaPackage | 0m00.76s || +0m00.13s | +17.10% 0m00.89s | Util/ZUtil/Tactics/RewriteModSmall | 0m01.13s || -0m00.23s | -21.23% 0m00.88s | Compilers/Named/WfInterp | 0m00.76s || +0m00.12s | +15.78% 0m00.88s | Compilers/Z/ArithmeticSimplifierUtil | 0m00.80s || +0m00.07s | +9.99% 0m00.88s | Util/Decidable | 0m00.81s || +0m00.06s | +8.64% 0m00.88s | Util/Factorize | 0m00.92s || -0m00.04s | -4.34% 0m00.88s | Util/ZUtil/Rshi | 0m01.11s || -0m00.23s | -20.72% 0m00.86s | Compilers/Z/Bounds/RoundUpLemmas | 0m00.90s || -0m00.04s | -4.44% 0m00.86s | LegacyArithmetic/Double/Core | 0m00.90s || -0m00.04s | -4.44% 0m00.85s | Arithmetic/ModularArithmeticPre | 0m00.82s || +0m00.03s | +3.65% N/A | Coqprime/Z/ZSum | 0m00.85s || -0m00.85s | -100.00% 0m00.85s | Specific/Framework/ArithmeticSynthesis/Ladderstep | 0m01.10s || -0m00.25s | -22.72% 0m00.84s | Compilers/Z/Bounds/InterpretationLemmas/Tactics | 0m00.88s || -0m00.04s | -4.54% 0m00.84s | Compilers/Z/Bounds/MapCastByDeBruijnWf | 0m00.85s || -0m00.01s | -1.17% 0m00.84s | LegacyArithmetic/ZBounded | 0m00.80s || +0m00.03s | +4.99% 0m00.84s | Spec/EdDSA | 0m00.55s || +0m00.28s | +52.72% 0m00.83s | Compilers/Z/Bounds/MapCastByDeBruijn | 0m00.87s || -0m00.04s | -4.59% 0m00.83s | LegacyArithmetic/BaseSystem | 0m00.78s || +0m00.04s | +6.41% 0m00.82s | Compilers/Z/MapCastByDeBruijnWf | 0m00.89s || -0m00.07s | -7.86% 0m00.82s | LegacyArithmetic/Double/Proofs/ShiftLeftRightTactic | 0m00.82s || +0m00.00s | +0.00% 0m00.82s | Specific/Framework/MontgomeryReificationTypesPackage | 0m00.92s || -0m00.10s | -10.86% 0m00.81s | Compilers/Z/CommonSubexpressionEliminationInterp | 0m00.80s || +0m00.01s | +1.25% 0m00.80s | Compilers/Z/FoldTypes | 0m00.76s || +0m00.04s | +5.26% 0m00.80s | Compilers/Z/MapCastByDeBruijn | 0m00.77s || +0m00.03s | +3.89% N/A | Coqprime/PrimalityTest/Root | 0m00.80s || -0m00.80s | -100.00% 0m00.79s | Arithmetic/MontgomeryReduction/Definition | 0m00.71s || +0m00.08s | +11.26% 0m00.79s | Compilers/GeneralizeVarInterp | 0m00.75s || +0m00.04s | +5.33% 0m00.79s | Compilers/MapCastByDeBruijnWf | 0m01.12s || -0m00.33s | -29.46% 0m00.79s | Compilers/Z/CommonSubexpressionEliminationWf | 0m00.79s || +0m00.00s | +0.00% 0m00.79s | Experiments/NewPipeline/CompilersTestCases | 0m01.62s || -0m00.83s | -51.23% 0m00.79s | Specific/Framework/ArithmeticSynthesis/MontgomeryPackage | 0m00.78s || +0m00.01s | +1.28% 0m00.78s | Compilers/Z/InlineConstAndOpInterp | 0m00.72s || +0m00.06s | +8.33% 0m00.78s | Compilers/Z/InlineConstAndOpWf | 0m00.80s || -0m00.02s | -2.50% 0m00.78s | Util/ZBounded | 0m00.81s || -0m00.03s | -3.70% 0m00.77s | Compilers/GeneralizeVarWf | 0m00.76s || +0m00.01s | +1.31% 0m00.77s | Compilers/Z/RewriteAddToAdc | 0m00.78s || -0m00.01s | -1.28% 0m00.77s | Util/NUtil | 0m00.84s || -0m00.06s | -8.33% 0m00.76s | Algebra/SubsetoidRing | 0m00.94s || -0m00.17s | -19.14% 0m00.76s | Compilers/Z/InlineConstAndOpByRewriteInterp | 0m00.75s || +0m00.01s | +1.33% N/A | Coqprime/PrimalityTest/Cyclic | 0m00.76s || -0m00.76s | -100.00% 0m00.76s | Util/HList | 0m00.80s || -0m00.04s | -5.00% 0m00.75s | Compilers/Z/Bounds/Interpretation | 0m00.70s || +0m00.05s | +7.14% 0m00.75s | Compilers/Z/InlineConstAndOpByRewriteWf | 0m00.73s || +0m00.02s | +2.73% 0m00.75s | Compilers/Z/InlineWf | 0m00.82s || -0m00.06s | -8.53% 0m00.75s | Compilers/Z/InterpSideConditions | 0m00.55s || +0m00.19s | +36.36% 0m00.75s | Compilers/ZExtended/MapBaseType | 0m00.68s || +0m00.06s | +10.29% 0m00.75s | Util/Loops | 0m00.90s || -0m00.15s | -16.66% 0m00.74s | Compilers/Named/DeadCodeEliminationInterp | 0m00.70s || +0m00.04s | +5.71% 0m00.74s | Compilers/Named/PositiveContext/DefaultsProperties | 0m00.74s || +0m00.00s | +0.00% 0m00.74s | LegacyArithmetic/Interface | 0m01.04s || -0m00.30s | -28.84% 0m00.73s | Compilers/Z/GeneralizeVarInterp | 0m00.70s || +0m00.03s | +4.28% 0m00.73s | Spec/CompleteEdwardsCurve | 0m00.90s || -0m00.17s | -18.88% 0m00.72s | Algebra/Nsatz | 0m00.75s || -0m00.03s | -4.00% 0m00.72s | Compilers/InterpRewriting | 0m00.66s || +0m00.05s | +9.09% 0m00.72s | Specific/Framework/IntegrationTestDisplayCommonTactics | 0m00.70s || +0m00.02s | +2.85% 0m00.71s | Compilers/InterpProofs | 0m00.71s || +0m00.00s | +0.00% 0m00.71s | Compilers/Z/InlineConstAndOp | 0m00.51s || +0m00.19s | +39.21% 0m00.71s | Compilers/Z/Named/RewriteAddToAdc | 0m00.98s || -0m00.27s | -27.55% 0m00.71s | Compilers/ZExtended/Syntax | 0m00.54s || +0m00.16s | +31.48% 0m00.71s | Specific/X25519/C64/CurveParameters | 0m00.50s || +0m00.20s | +41.99% 0m00.70s | Compilers/InterpWf | 0m00.72s || -0m00.02s | -2.77% 0m00.70s | LegacyArithmetic/ArchitectureToZLike | 0m00.84s || -0m00.14s | -16.66% 0m00.70s | Util/ZRange | 0m00.70s || +0m00.00s | +0.00% 0m00.69s | Compilers/InputSyntax | 0m00.74s || -0m00.05s | -6.75% 0m00.69s | Compilers/Z/InlineConstAndOpByRewrite | 0m00.86s || -0m00.17s | -19.76% 0m00.69s | Spec/ModularArithmetic | 0m00.66s || +0m00.02s | +4.54% 0m00.68s | Compilers/CommonSubexpressionEliminationInterp | 0m00.98s || -0m00.29s | -30.61% 0m00.68s | Compilers/InterpWfRel | 0m00.78s || -0m00.09s | -12.82% 0m00.68s | Util/ZUtil/CPS | 0m00.61s || +0m00.07s | +11.47% 0m00.67s | Compilers/Z/Syntax | 0m00.66s || +0m00.01s | +1.51% 0m00.67s | Experiments/NewPipeline/AbstractInterpretationProofs | 0m00.60s || +0m00.07s | +11.66% 0m00.66s | Compilers/Reify | 0m00.60s || +0m00.06s | +10.00% 0m00.66s | Specific/Framework/CurveParameters | 0m00.64s || +0m00.02s | +3.12% 0m00.66s | Util/ZRange/Operations | 0m00.64s || +0m00.02s | +3.12% 0m00.64s | Experiments/PartialEvaluationWithLetIn | 0m00.61s || +0m00.03s | +4.91% 0m00.62s | Algebra/Monoid | 0m00.57s || +0m00.05s | +8.77% 0m00.62s | Compilers/InlineConstAndOp | 0m00.61s || +0m00.01s | +1.63% 0m00.62s | Compilers/InlineConstAndOpByRewriteWf | 0m00.78s || -0m00.16s | -20.51% 0m00.62s | Compilers/Named/WeakListContext | 0m00.62s || +0m00.00s | +0.00% 0m00.62s | Compilers/WfReflectiveGen | 0m00.60s || +0m00.02s | +3.33% 0m00.62s | Compilers/Z/GeneralizeVarWf | 0m00.75s || -0m00.13s | -17.33% 0m00.62s | Specific/Framework/RawCurveParameters | 0m00.58s || +0m00.04s | +6.89% 0m00.61s | Compilers/CommonSubexpressionEliminationDenote | 0m00.41s || +0m00.20s | +48.78% 0m00.61s | Compilers/Named/RegisterAssign | 0m00.60s || +0m00.01s | +1.66% 0m00.61s | Compilers/Z/Inline | 0m00.56s || +0m00.04s | +8.92% 0m00.61s | Util/BoundedWord | 0m00.57s || +0m00.04s | +7.01% 0m00.60s | Compilers/InlineConstAndOpByRewriteInterp | 0m00.68s || -0m00.08s | -11.76% 0m00.60s | Compilers/MapCastByDeBruijn | 0m00.61s || -0m00.01s | -1.63% 0m00.60s | LegacyArithmetic/Pow2Base | 0m00.73s || -0m00.13s | -17.80% 0m00.59s | Compilers/Z/Named/DeadCodeElimination | 0m00.51s || +0m00.07s | +15.68% 0m00.58s | Compilers/Linearize | 0m00.56s || +0m00.01s | +3.57% 0m00.58s | Compilers/Named/MapCast | 0m00.56s || +0m00.01s | +3.57% 0m00.58s | Compilers/Z/Bounds/Pipeline/OutputType | 0m00.61s || -0m00.03s | -4.91% 0m00.58s | Compilers/ZExtended/InlineConstAndOpWf | 0m00.53s || +0m00.04s | +9.43% 0m00.58s | Util/FixedWordSizes | 0m00.53s || +0m00.04s | +9.43% 0m00.58s | Util/ZUtil/Tactics/SimplifyFractionsLe | 0m00.43s || +0m00.14s | +34.88% 0m00.57s | Compilers/GeneralizeVar | 0m00.56s || +0m00.00s | +1.78% 0m00.57s | Compilers/Z/Named/DeadCodeEliminationInterp | 0m00.69s || -0m00.12s | -17.39% N/A | Coqprime/PrimalityTest/Zp | 0m00.57s || -0m00.56s | -100.00% 0m00.57s | Util/ZUtil/MulSplit | 0m00.48s || +0m00.08s | +18.74% 0m00.56s | Compilers/Z/OpInversion | 0m00.56s || +0m00.00s | +0.00% 0m00.56s | Compilers/Z/TypeInversion | 0m00.39s || +0m00.17s | +43.58% 0m00.56s | Specific/NISTP256/AMD64/CurveParameters | 0m00.61s || -0m00.04s | -8.19% 0m00.56s | Util/Decidable/Decidable2Bool | 0m00.81s || -0m00.25s | -30.86% 0m00.55s | Compilers/FilterLive | 0m00.47s || +0m00.08s | +17.02% 0m00.55s | Compilers/Named/IdContext | 0m00.50s || +0m00.05s | +10.00% 0m00.55s | Compilers/ZExtended/InlineConstAndOpByRewrite | 0m00.50s || +0m00.05s | +10.00% 0m00.55s | Compilers/ZExtended/InlineConstAndOpByRewriteWf | 0m00.45s || +0m00.10s | +22.22% 0m00.55s | Compilers/ZExtended/Syntax/Util | 0m00.58s || -0m00.02s | -5.17% 0m00.55s | Specific/X2448/Karatsuba/C64/CurveParameters | 0m00.38s || +0m00.17s | +44.73% 0m00.54s | Compilers/Inline | 0m00.54s || +0m00.00s | +0.00% 0m00.54s | Compilers/Named/InterpSideConditions | 0m00.40s || +0m00.14s | +35.00% 0m00.54s | Compilers/Named/Wf | 0m00.49s || +0m00.05s | +10.20% 0m00.53s | Compilers/Named/ContextDefinitions | 0m00.55s || -0m00.02s | -3.63% 0m00.53s | Compilers/ZExtended/InlineConstAndOpByRewriteInterp | 0m00.51s || +0m00.02s | +3.92% 0m00.53s | Compilers/ZExtended/InlineConstAndOpInterp | 0m00.58s || -0m00.04s | -8.62% 0m00.53s | Specific/Framework/CurveParametersPackage | 0m00.44s || +0m00.09s | +20.45% 0m00.53s | Util/ZRange/Show | 0m00.56s || -0m00.03s | -5.35% 0m00.53s | Util/ZUtil/Tactics/ZeroBounds | 0m00.40s || +0m00.13s | +32.50% 0m00.52s | Compilers/Named/Context | 0m00.47s || +0m00.05s | +10.63% 0m00.52s | Compilers/Named/CountLets | 0m00.44s || +0m00.08s | +18.18% 0m00.52s | Compilers/Named/GetNames | 0m00.50s || +0m00.02s | +4.00% 0m00.52s | Compilers/Named/InterpretToPHOAS | 0m00.55s || -0m00.03s | -5.45% 0m00.52s | Compilers/Tuple | 0m00.53s || -0m00.01s | -1.88% 0m00.52s | Util/ZUtil/Sgn | 0m00.51s || +0m00.01s | +1.96% 0m00.52s | Util/ZUtil/Tactics/PullPush/Modulo | 0m00.48s || +0m00.04s | +8.33% 0m00.51s | Compilers/CountLets | 0m00.42s || +0m00.09s | +21.42% 0m00.51s | Compilers/Named/ContextOn | 0m00.49s || +0m00.02s | +4.08% 0m00.51s | Util/AdditionChainExponentiation | 0m00.62s || -0m00.10s | -17.74% 0m00.51s | Util/Strings/String | 0m00.58s || -0m00.06s | -12.06% 0m00.51s | Util/ZUtil/Tactics/Ztestbit | 0m00.43s || +0m00.08s | +18.60% 0m00.50s | Compilers/ExprInversion | 0m00.46s || +0m00.03s | +8.69% 0m00.50s | Compilers/FoldTypes | 0m00.51s || -0m00.01s | -1.96% 0m00.50s | Compilers/InlineConstAndOpByRewrite | 0m00.50s || +0m00.00s | +0.00% 0m00.50s | Compilers/Z/InlineInterp | 0m00.59s || -0m00.08s | -15.25% N/A | Coqprime/List/UList | 0m00.50s || -0m00.50s | -100.00% 0m00.49s | Util/ZUtil/Hints/PullPush | 0m00.41s || +0m00.08s | +19.51% 0m00.48s | Compilers/Named/ContextProperties/Tactics | 0m00.53s || -0m00.05s | -9.43% 0m00.48s | Compilers/Z/GeneralizeVar | 0m00.49s || -0m00.01s | -2.04% 0m00.48s | Compilers/ZExtended/InlineConstAndOp | 0m00.52s || -0m00.04s | -7.69% 0m00.48s | Util/ZUtil/Hints/Ztestbit | 0m00.50s || -0m00.02s | -4.00% 0m00.48s | Util/ZUtil/ZSimplify/Core | 0m00.44s || +0m00.03s | +9.09% 0m00.48s | Util/ZUtil/Zselect | 0m00.44s || +0m00.03s | +9.09% 0m00.47s | Compilers/InterpByIso | 0m00.47s || +0m00.00s | +0.00% 0m00.47s | Util/IdfunWithAlt | 0m00.59s || -0m00.12s | -20.33% 0m00.47s | Util/ZUtil/Hints/ZArith | 0m00.49s || -0m00.02s | -4.08% 0m00.46s | Compilers/Named/DeadCodeElimination | 0m00.58s || -0m00.11s | -20.68% N/A | Coqprime/List/Permutation | 0m00.46s || -0m00.46s | -100.00% 0m00.46s | Experiments/NewPipeline/UnderLets | 0m00.72s || -0m00.25s | -36.11% 0m00.46s | Util/Sum | 0m00.44s || +0m00.02s | +4.54% 0m00.45s | Compilers/Named/SmartMap | 0m00.54s || -0m00.09s | -16.66% 0m00.45s | Util/ZUtil/Z2Nat | 0m00.41s || +0m00.04s | +9.75% 0m00.44s | Compilers/MapBaseType | 0m00.46s || -0m00.02s | -4.34% 0m00.44s | Util/Strings/HexString | 0m00.44s || +0m00.00s | +0.00% 0m00.44s | Util/ZUtil/Div/Bootstrap | 0m00.50s || -0m00.06s | -12.00% 0m00.44s | Util/ZUtil/Hints/Core | 0m00.52s || -0m00.08s | -15.38% 0m00.43s | Compilers/Named/EstablishLiveness | 0m00.38s || +0m00.04s | +13.15% 0m00.43s | Compilers/Named/ExprInversion | 0m00.56s || -0m00.13s | -23.21% 0m00.43s | Compilers/StripExpr | 0m00.50s || -0m00.07s | -14.00% 0m00.43s | Util/ZUtil/Tactics/LtbToLt | 0m00.54s || -0m00.11s | -20.37% 0m00.42s | Arithmetic/MontgomeryReduction/WordByWord/Abstract/Dependent/Definition | 0m00.43s || -0m00.01s | -2.32% 0m00.42s | Util/ZUtil/Hints | 0m00.40s || +0m00.01s | +4.99% 0m00.42s | Util/ZUtil/Le | 0m00.43s || -0m00.01s | -2.32% 0m00.42s | Util/ZUtil/ZSimplify | 0m00.28s || +0m00.13s | +49.99% 0m00.42s | bbv/Nomega | 0m00.45s || -0m00.03s | -6.66% 0m00.41s | Util/ZUtil/Sorting | 0m00.47s || -0m00.06s | -12.76% 0m00.41s | Util/ZUtil/Tactics/PrimeBound | 0m00.36s || +0m00.04s | +13.88% 0m00.41s | bbv/HexNotationWord | 0m00.45s || -0m00.04s | -8.88% 0m00.40s | Compilers/Named/PositiveContext | 0m00.59s || -0m00.18s | -32.20% 0m00.40s | Compilers/Named/Syntax | 0m00.50s || -0m00.09s | -19.99% N/A | Coqprime/List/ListAux | 0m00.40s || -0m00.40s | -100.00% 0m00.40s | Util/SideConditions/RingPackage | 0m00.37s || +0m00.03s | +8.10% 0m00.40s | Util/ZUtil/Tactics/DivModToQuotRem | 0m00.38s || +0m00.02s | +5.26% 0m00.40s | Util/ZUtil/Tactics/LinearSubstitute | 0m00.42s || -0m00.01s | -4.76% 0m00.39s | Compilers/Equality | 0m00.38s || +0m00.01s | +2.63% 0m00.39s | Util/SideConditions/Autosolve | 0m00.28s || +0m00.10s | +39.28% 0m00.39s | Util/SideConditions/ModInvPackage | 0m00.41s || -0m00.01s | -4.87% 0m00.39s | bbv/HexNotation | 0m00.38s || +0m00.01s | +2.63% N/A | Coqprime/PrimalityTest/Lagrange | 0m00.38s || -0m00.38s | -100.00% 0m00.38s | Specific/NISTP256/AMD128/CurveParameters | 0m00.58s || -0m00.19s | -34.48% 0m00.38s | Util/ZUtil/AddModulo | 0m00.28s || +0m00.09s | +35.71% 0m00.38s | Util/ZUtil/Modulo/Bootstrap | 0m00.40s || -0m00.02s | -5.00% 0m00.38s | Util/ZUtil/Tactics/CompareToSgn | 0m00.43s || -0m00.04s | -11.62% 0m00.38s | Util/ZUtil/Tactics/DivideExistsMul | 0m00.38s || +0m00.00s | +0.00% 0m00.38s | bbv/WordScope | 0m00.40s || -0m00.02s | -5.00% 0m00.37s | Algebra/Hierarchy | 0m00.40s || -0m00.03s | -7.50% 0m00.37s | Compilers/Named/Compile | 0m00.50s || -0m00.13s | -26.00% N/A | Coqprime/List/ZProgression | 0m00.37s || -0m00.37s | -100.00% N/A | Coqprime/PrimalityTest/IGroup | 0m00.37s || -0m00.37s | -100.00% 0m00.37s | Util/ZUtil/Ge | 0m00.33s || +0m00.03s | +12.12% 0m00.37s | Util/ZUtil/Land | 0m00.43s || -0m00.06s | -13.95% 0m00.36s | Arithmetic/MontgomeryReduction/WordByWord/Abstract/Definition | 0m00.42s || -0m00.06s | -14.28% 0m00.36s | Compilers/Named/MapType | 0m00.33s || +0m00.02s | +9.09% 0m00.36s | Compilers/Named/PositiveContext/Defaults | 0m00.57s || -0m00.20s | -36.84% 0m00.36s | Util/Strings/OctalString | 0m00.33s || +0m00.02s | +9.09% 0m00.36s | Util/ZUtil/Definitions | 0m00.40s || -0m00.04s | -10.00% 0m00.36s | Util/ZUtil/Tactics/PullPush | 0m00.39s || -0m00.03s | -7.69% 0m00.36s | Util/ZUtil/Tactics/ReplaceNegWithPos | 0m00.33s || +0m00.02s | +9.09% 0m00.36s | bbv/BinNotation | 0m00.37s || -0m00.01s | -2.70% N/A | Coqprime/PrimalityTest/Euler | 0m00.35s || -0m00.35s | -100.00% 0m00.35s | Spec/MxDH | 0m00.39s || -0m00.04s | -10.25% 0m00.35s | Util/Decidable/Bool2Prop | 0m00.22s || +0m00.12s | +59.09% 0m00.35s | Util/ZUtil/Tactics | 0m00.48s || -0m00.13s | -27.08% 0m00.35s | Util/ZUtil/Tactics/PeelLe | 0m00.44s || -0m00.09s | -20.45% 0m00.35s | Util/ZUtil/Tactics/SplitMinMax | 0m00.35s || +0m00.00s | +0.00% 0m00.34s | Util/Option | 0m00.31s || +0m00.03s | +9.67% 0m00.34s | Util/ZUtil/ModInv | 0m00.38s || -0m00.03s | -10.52% 0m00.34s | bbv/BinNotationZ | 0m00.34s || +0m00.00s | +0.00% 0m00.34s | bbv/HexNotationZ | 0m00.37s || -0m00.02s | -8.10% 0m00.34s | bbv/NLib | 0m00.42s || -0m00.07s | -19.04% 0m00.33s | Util/Strings/Show | 0m00.45s || -0m00.12s | -26.66% N/A | Coqprime/List/Iterator | 0m00.31s || -0m00.31s | -100.00% 0m00.31s | Util/PointedProp | 0m00.30s || +0m00.01s | +3.33% 0m00.29s | Util/LetInMonad | 0m00.29s || +0m00.00s | +0.00% 0m00.28s | Compilers/EtaInterp | 0m00.34s || -0m00.06s | -17.64% 0m00.28s | Compilers/InSet/TypeifyInterp | 0m00.18s || +0m00.10s | +55.55% 0m00.28s | Util/Strings/BinaryString | 0m00.32s || -0m00.03s | -12.49% 0m00.28s | Util/Strings/Equality | 0m00.29s || -0m00.00s | -3.44% N/A | Coqprime/PrimalityTest/FGroup | 0m00.27s || -0m00.27s | -100.00% 0m00.27s | Util/Strings/Ascii | 0m00.33s || -0m00.06s | -18.18% 0m00.27s | Util/Strings/Decimal | 0m00.26s || +0m00.01s | +3.84% N/A | Coqprime/N/NatAux | 0m00.26s || -0m00.26s | -100.00% 0m00.26s | Util/ParseTaps | 0m00.29s || -0m00.02s | -10.34% 0m00.25s | Util/SideConditions/ReductionPackages | 0m00.24s || +0m00.01s | +4.16% 0m00.24s | Util/ZUtil/Notations | 0m00.29s || -0m00.04s | -17.24% 0m00.20s | Compilers/Conversion | 0m00.12s || +0m00.08s | +66.66% 0m00.20s | Util/ListUtil/FoldBool | 0m00.20s || +0m00.00s | +0.00% 0m00.19s | Compilers/Named/NameUtil | 0m00.18s || +0m00.01s | +5.55% 0m00.19s | Compilers/Wf | 0m00.20s || -0m00.01s | -5.00% 0m00.18s | Specific/Framework/Packages | 0m00.17s || +0m00.00s | +5.88% 0m00.18s | Util/PrimitiveProd | 0m00.19s || -0m00.01s | -5.26% 0m00.18s | Util/Relations | 0m00.14s || +0m00.03s | +28.57% 0m00.18s | bbv/DepEq | 0m00.22s || -0m00.04s | -18.18% 0m00.17s | Util/ListUtil/Forall | 0m00.18s || -0m00.00s | -5.55% 0m00.17s | Util/Sigma | 0m00.14s || +0m00.03s | +21.42% 0m00.16s | Compilers/RewriterWf | 0m00.16s || +0m00.00s | +0.00% 0m00.16s | Util/TagList | 0m00.20s || -0m00.04s | -20.00% 0m00.14s | Compilers/RewriterInterp | 0m00.12s || +0m00.02s | +16.66% 0m00.14s | Compilers/TypeInversion | 0m00.14s || +0m00.00s | +0.00% 0m00.12s | Compilers/InSet/Syntax | 0m00.09s || +0m00.03s | +33.33% 0m00.12s | Compilers/InterpSideConditions | 0m00.07s || +0m00.04s | +71.42% 0m00.12s | Util/AutoRewrite | 0m00.09s || +0m00.03s | +33.33% 0m00.12s | Util/Equality | 0m00.13s || -0m00.01s | -7.69% 0m00.12s | Util/PrimitiveHList | 0m00.14s || -0m00.02s | -14.28% 0m00.12s | Util/Prod | 0m00.18s || -0m00.06s | -33.33% 0m00.11s | Compilers/RenameBinders | 0m00.10s || +0m00.00s | +9.99% 0m00.11s | Compilers/Rewriter | 0m00.10s || +0m00.00s | +9.99% 0m00.11s | Compilers/TypeUtil | 0m00.08s || +0m00.03s | +37.50% 0m00.11s | Util/HProp | 0m00.10s || +0m00.00s | +9.99% 0m00.11s | Util/IffT | 0m00.05s || +0m00.06s | +120.00% 0m00.11s | Util/Tactics | 0m00.08s || +0m00.03s | +37.50% 0m00.10s | Compilers/Eta | 0m00.11s || -0m00.00s | -9.09% 0m00.10s | Compilers/Syntax | 0m00.13s || -0m00.03s | -23.07% 0m00.10s | Util/Bool | 0m00.08s || +0m00.02s | +25.00% 0m00.10s | Util/Isomorphism | 0m00.12s || -0m00.01s | -16.66% 0m00.10s | Util/LetIn | 0m00.09s || +0m00.01s | +11.11% 0m00.10s | Util/Sumbool | 0m00.09s || +0m00.01s | +11.11% 0m00.10s | Util/Tactics/MoveLetIn | 0m00.09s || +0m00.01s | +11.11% 0m00.10s | Util/Tactics/Revert | 0m00.07s || +0m00.03s | +42.85% 0m00.10s | Util/Tower | 0m00.10s || +0m00.00s | +0.00% 0m00.10s | bbv/DepEqNat | 0m00.06s || +0m00.04s | +66.66% 0m00.09s | Compilers/InSet/Typeify | 0m00.12s || -0m00.03s | -25.00% 0m00.09s | Util/Tactics/Contains | 0m00.04s || +0m00.05s | +124.99% 0m00.09s | Util/Tactics/ConvoyDestruct | 0m00.05s || +0m00.03s | +79.99% 0m00.09s | Util/Tactics/DestructHead | 0m00.10s || -0m00.01s | -10.00% 0m00.09s | Util/Tactics/ETransitivity | 0m00.08s || +0m00.00s | +12.49% 0m00.09s | Util/Tactics/SpecializeBy | 0m00.06s || +0m00.03s | +50.00% 0m00.08s | Compilers/Intros | 0m00.08s || +0m00.00s | +0.00% 0m00.08s | Compilers/Map | 0m00.10s || -0m00.02s | -20.00% 0m00.08s | Util/Bool/IsTrue | 0m00.06s || +0m00.02s | +33.33% 0m00.08s | Util/ErrorT | 0m00.07s || +0m00.00s | +14.28% 0m00.08s | Util/Logic | 0m00.08s || +0m00.00s | +0.00% 0m00.08s | Util/Pointed | 0m00.08s || +0m00.00s | +0.00% 0m00.08s | Util/Pos | 0m00.04s || +0m00.04s | +100.00% 0m00.08s | Util/SideConditions/AdmitPackage | 0m00.08s || +0m00.00s | +0.00% 0m00.08s | Util/Sigma/Lift | 0m00.06s || +0m00.02s | +33.33% 0m00.08s | Util/Tactics/CacheTerm | 0m00.08s || +0m00.00s | +0.00% 0m00.08s | Util/Tactics/DebugPrint | 0m00.10s || -0m00.02s | -20.00% 0m00.08s | Util/Tactics/DestructTrivial | 0m00.05s || +0m00.03s | +60.00% 0m00.08s | Util/Tactics/GetGoal | 0m00.06s || +0m00.02s | +33.33% 0m00.08s | Util/Tactics/Head | 0m00.07s || +0m00.00s | +14.28% 0m00.08s | Util/Tactics/RewriteHyp | 0m00.06s || +0m00.02s | +33.33% 0m00.08s | Util/Tactics/SubstEvars | 0m00.07s || +0m00.00s | +14.28% 0m00.08s | Util/Tactics/UnifyAbstractReflexivity | 0m00.06s || +0m00.02s | +33.33% 0m00.08s | Util/Tactics/VM | 0m00.08s || +0m00.00s | +0.00% 0m00.07s | LegacyArithmetic/VerdiTactics | 0m00.10s || -0m00.03s | -30.00% 0m00.07s | Util/Bool/Equality | 0m00.07s || +0m00.00s | +0.00% 0m00.07s | Util/CPSNotations | 0m00.09s || -0m00.01s | -22.22% 0m00.07s | Util/Logic/ImplAnd | 0m00.07s || +0m00.00s | +0.00% 0m00.07s | Util/Tactics/BreakMatch | 0m00.06s || +0m00.01s | +16.66% 0m00.07s | Util/Tactics/DestructHyps | 0m00.07s || +0m00.00s | +0.00% 0m00.07s | Util/Tactics/DoWithHyp | 0m00.09s || -0m00.01s | -22.22% 0m00.07s | Util/Tactics/ESpecialize | 0m00.08s || -0m00.00s | -12.49% 0m00.07s | Util/Tactics/HeadUnderBinders | 0m00.06s || +0m00.01s | +16.66% 0m00.07s | Util/Tactics/Not | 0m00.07s || +0m00.00s | +0.00% 0m00.07s | Util/Tactics/PoseTermWithName | 0m00.06s || +0m00.01s | +16.66% 0m00.07s | Util/Tactics/PrintContext | 0m00.06s || +0m00.01s | +16.66% 0m00.07s | Util/Tactics/SetEvars | 0m00.05s || +0m00.02s | +40.00% 0m00.07s | Util/Tactics/SpecializeAllWays | 0m00.08s || -0m00.00s | -12.49% 0m00.07s | Util/Tactics/SplitInContext | 0m00.07s || +0m00.00s | +0.00% 0m00.07s | Util/Tactics/TransparentAssert | 0m00.06s || +0m00.01s | +16.66% 0m00.07s | Util/Unit | 0m00.06s || +0m00.01s | +16.66% 0m00.06s | Util/Curry | 0m00.08s || -0m00.02s | -25.00% 0m00.06s | Util/DefaultedTypes | 0m00.07s || -0m00.01s | -14.28% 0m00.06s | Util/FixCoqMistakes | 0m00.09s || -0m00.03s | -33.33% 0m00.06s | Util/GlobalSettings | 0m00.12s || -0m00.06s | -50.00% 0m00.06s | Util/SideConditions/CorePackages | 0m00.07s || -0m00.01s | -14.28% 0m00.06s | Util/Sigma/Associativity | 0m00.08s || -0m00.02s | -25.00% 0m00.06s | Util/Sigma/MapProjections | 0m00.05s || +0m00.00s | +19.99% 0m00.06s | Util/Tactics/ClearDuplicates | 0m00.07s || -0m00.01s | -14.28% 0m00.06s | Util/Tactics/ClearbodyAll | 0m00.07s || -0m00.01s | -14.28% 0m00.06s | Util/Tactics/EvarExists | 0m00.06s || +0m00.00s | +0.00% 0m00.06s | Util/Tactics/Forward | 0m00.04s || +0m00.01s | +49.99% 0m00.06s | Util/Tactics/OnSubterms | 0m00.04s || +0m00.01s | +49.99% 0m00.06s | Util/Tactics/RunTacticAsConstr | 0m00.06s || +0m00.00s | +0.00% 0m00.06s | Util/Tactics/SideConditionsBeforeToAfter | 0m00.06s || +0m00.00s | +0.00% 0m00.06s | Util/Tactics/SimplifyProjections | 0m00.08s || -0m00.02s | -25.00% 0m00.06s | Util/Tactics/SubstLet | 0m00.06s || +0m00.00s | +0.00% 0m00.06s | Util/Tactics/Test | 0m00.07s || -0m00.01s | -14.28% 0m00.05s | Util/ChangeInAll | 0m00.06s || -0m00.00s | -16.66% 0m00.05s | Util/Notations | 0m00.08s || -0m00.03s | -37.50% 0m00.05s | Util/Tactics/SimplifyRepeatedIfs | 0m00.06s || -0m00.00s | -16.66% 0m00.05s | Util/Tactics/UnfoldArg | 0m00.08s || -0m00.03s | -37.50% 0m00.05s | Util/Tactics/UniquePose | 0m00.06s || -0m00.00s | -16.66% 0m00.04s | Util/OptionList | 0m00.09s || -0m00.05s | -55.55% 0m00.04s | Util/Tactics/ChangeInAll | 0m00.08s || -0m00.04s | -50.00% 0m00.04s | Util/Tactics/SetoidSubst | 0m00.05s || -0m00.01s | -20.00% 0m00.03s | Util/Tactics/ClearAll | 0m00.06s || -0m00.03s | -50.00% N/A | Coqprime/Tactic/Tactic | 0m00.02s || -0m00.02s | -100.00%
Diffstat (limited to 'src/Experiments/NewPipeline/Toplevel1.v')
-rw-r--r--src/Experiments/NewPipeline/Toplevel1.v985
1 files changed, 974 insertions, 11 deletions
diff --git a/src/Experiments/NewPipeline/Toplevel1.v b/src/Experiments/NewPipeline/Toplevel1.v
index 1f86f656f..8a79fc852 100644
--- a/src/Experiments/NewPipeline/Toplevel1.v
+++ b/src/Experiments/NewPipeline/Toplevel1.v
@@ -36,6 +36,7 @@ Require Import Crypto.Util.ZUtil.AddModulo.
Require Import Crypto.Util.ZUtil.CC.
Require Import Crypto.Arithmetic.MontgomeryReduction.Definition.
Require Import Crypto.Arithmetic.MontgomeryReduction.Proofs.
+Require Import Crypto.Util.ZUtil.ModInv.
Require Import Crypto.Util.ErrorT.
Require Import Crypto.Util.Strings.Show.
Require Import Crypto.Util.ZRange.Show.
@@ -261,6 +262,230 @@ Module Ring.
End ring_goal.
End Ring.
+(** NOTE: Module MontgomeryStyleRing SHOULD NOT depend on any compilers things *)
+Module MontgomeryStyleRing.
+ Local Notation is_bounded_by0 r v
+ := ((lower r <=? v) && (v <=? upper r)).
+ Local Notation is_bounded_by0o r
+ := (match r with Some r' => fun v' => is_bounded_by0 r' v' | None => fun _ => true end).
+ Local Notation is_bounded_by bounds ls
+ := (fold_andb_map (fun r v'' => is_bounded_by0o r v'') bounds ls).
+ Local Notation is_bounded_by1 bounds ls
+ := (andb (is_bounded_by bounds (@fst _ unit ls)) true).
+ Local Notation is_bounded_by2 bounds ls
+ := (andb (is_bounded_by bounds (fst ls)) (is_bounded_by1 bounds (snd ls))).
+
+ Lemma length_is_bounded_by bounds ls
+ : is_bounded_by bounds ls = true -> length ls = length bounds.
+ Proof.
+ intro H.
+ apply fold_andb_map_length in H; congruence.
+ Qed.
+
+ Section ring_goal.
+ Context (limbwidth_num limbwidth_den : Z)
+ (n : nat)
+ (s : Z)
+ (c : list (Z * Z))
+ (bounds : list (option zrange))
+ (length_bounds : length bounds = n).
+ Local Notation weight := (weight limbwidth_num limbwidth_den).
+ Local Notation eval := (Positional.eval weight n).
+ Let prime_bound : zrange
+ := r[0~>(s - Associational.eval c - 1)]%zrange.
+ Let m := Z.to_pos (s - Associational.eval c).
+ Context (m_eq : Z.pos m = s - Associational.eval c)
+ (sc_pos : 0 < s - Associational.eval c)
+ (valid : list Z -> Prop)
+ (from_montgomery_mod : list Z -> list Z)
+ (Hfrom_montgomery_mod
+ : forall v, valid v -> valid (from_montgomery_mod v))
+ (Interp_rfrom_montgomeryv : list Z -> list Z)
+ (HInterp_rfrom_montgomeryv : forall arg,
+ is_bounded_by1 bounds arg = true
+ -> is_bounded_by bounds (Interp_rfrom_montgomeryv (fst arg)) = true
+ /\ Interp_rfrom_montgomeryv (fst arg) = from_montgomery_mod (fst arg))
+ (mulmod : list Z -> list Z -> list Z)
+ (Hmulmod
+ : (forall a (_ : valid a) b (_ : valid b), eval (from_montgomery_mod (mulmod a b)) mod (s - Associational.eval c)
+ = (eval (from_montgomery_mod a) * eval (from_montgomery_mod b)) mod (s - Associational.eval c))
+ /\ (forall a (_ : valid a) b (_ : valid b), valid (mulmod a b)))
+ (Interp_rmulv : list Z -> list Z -> list Z)
+ (HInterp_rmulv : forall arg,
+ is_bounded_by2 bounds arg = true
+ -> is_bounded_by bounds (Interp_rmulv (fst arg) (fst (snd arg))) = true
+ /\ Interp_rmulv (fst arg) (fst (snd arg)) = mulmod (fst arg) (fst (snd arg)))
+ (addmod : list Z -> list Z -> list Z)
+ (Haddmod
+ : (forall a (_ : valid a) b (_ : valid b), eval (from_montgomery_mod (addmod a b)) mod (s - Associational.eval c)
+ = (eval (from_montgomery_mod a) + eval (from_montgomery_mod b)) mod (s - Associational.eval c))
+ /\ (forall a (_ : valid a) b (_ : valid b), valid (addmod a b)))
+ (Interp_raddv : list Z -> list Z -> list Z)
+ (HInterp_raddv : forall arg,
+ is_bounded_by2 bounds arg = true
+ -> is_bounded_by bounds (Interp_raddv (fst arg) (fst (snd arg))) = true
+ /\ Interp_raddv (fst arg) (fst (snd arg)) = addmod (fst arg) (fst (snd arg)))
+ (submod : list Z -> list Z -> list Z)
+ (Hsubmod
+ : (forall a (_ : valid a) b (_ : valid b), eval (from_montgomery_mod (submod a b)) mod (s - Associational.eval c)
+ = (eval (from_montgomery_mod a) - eval (from_montgomery_mod b)) mod (s - Associational.eval c))
+ /\ (forall a (_ : valid a) b (_ : valid b), valid (submod a b)))
+ (Interp_rsubv : list Z -> list Z -> list Z)
+ (HInterp_rsubv : forall arg,
+ is_bounded_by2 bounds arg = true
+ -> is_bounded_by bounds (Interp_rsubv (fst arg) (fst (snd arg))) = true
+ /\ Interp_rsubv (fst arg) (fst (snd arg)) = submod (fst arg) (fst (snd arg)))
+ (oppmod : list Z -> list Z)
+ (Hoppmod
+ : (forall a (_ : valid a), eval (from_montgomery_mod (oppmod a)) mod (s - Associational.eval c)
+ = (-eval (from_montgomery_mod a)) mod (s - Associational.eval c))
+ /\ (forall a (_ : valid a), valid (oppmod a)))
+ (Interp_roppv : list Z -> list Z)
+ (HInterp_roppv : forall arg,
+ is_bounded_by1 bounds arg = true
+ -> is_bounded_by bounds (Interp_roppv (fst arg)) = true
+ /\ Interp_roppv (fst arg) = oppmod (fst arg))
+ (zeromod : list Z)
+ (Hzeromod
+ : (eval (from_montgomery_mod zeromod)) mod (s - Associational.eval c)
+ = 0 mod (s - Associational.eval c)
+ /\ valid zeromod)
+ (Interp_rzerov : list Z)
+ (HInterp_rzerov : is_bounded_by bounds Interp_rzerov = true
+ /\ Interp_rzerov = zeromod)
+ (onemod : list Z)
+ (Honemod
+ : (eval (from_montgomery_mod onemod)) mod (s - Associational.eval c)
+ = 1 mod (s - Associational.eval c)
+ /\ valid onemod)
+ (Interp_ronev : list Z)
+ (HInterp_ronev : is_bounded_by bounds Interp_ronev = true
+ /\ Interp_ronev = onemod)
+ (encodemod : Z -> list Z)
+ (Hencodemod
+ : (forall v, 0 <= v < s - Associational.eval c -> eval (from_montgomery_mod (encodemod v)) mod (s - Associational.eval c) = v mod (s - Associational.eval c))
+ /\ (forall v, 0 <= v < s - Associational.eval c -> valid (encodemod v)))
+ (Interp_rencodev : Z -> list Z)
+ (HInterp_rencodev : forall arg,
+ is_bounded_by0 prime_bound (@fst _ unit arg) && true = true
+ -> is_bounded_by bounds (Interp_rencodev (fst arg)) = true
+ /\ Interp_rencodev (fst arg) = encodemod (fst arg)).
+
+ Local Notation T := (list Z) (only parsing).
+ Local Notation encoded_ok ls
+ := (is_bounded_by bounds ls = true /\ valid ls) (only parsing).
+ Local Notation encoded_okf := (fun ls => encoded_ok ls) (only parsing).
+
+ Definition Fdecode (v : T) : F m
+ := F.of_Z m (Positional.eval weight n (Interp_rfrom_montgomeryv v)).
+ Definition T_eq (x y : T)
+ := Fdecode x = Fdecode y.
+
+ Definition encodedT := sig encoded_okf.
+
+ Definition ring_mul (x y : T) : T
+ := Interp_rmulv x y.
+ Definition ring_add (x y : T) : T := Interp_raddv x y.
+ Definition ring_sub (x y : T) : T := Interp_rsubv x y.
+ Definition ring_opp (x : T) : T := Interp_roppv x.
+ Definition ring_encode (x : F m) : T := Interp_rencodev (F.to_Z x).
+
+ Definition GoodT : Prop
+ := @subsetoid_ring
+ (list Z) encoded_okf T_eq
+ Interp_rzerov Interp_ronev ring_opp ring_add ring_sub ring_mul
+ /\ @is_subsetoid_homomorphism
+ (F m) (fun _ => True) eq 1%F F.add F.mul
+ (list Z) encoded_okf T_eq Interp_ronev ring_add ring_mul ring_encode
+ /\ @is_subsetoid_homomorphism
+ (list Z) encoded_okf T_eq Interp_ronev ring_add ring_mul
+ (F m) (fun _ => True) eq 1%F F.add F.mul
+ Fdecode.
+
+ Hint Rewrite ->@F.to_Z_add : push_FtoZ.
+ Hint Rewrite ->@F.to_Z_mul : push_FtoZ.
+ Hint Rewrite ->@F.to_Z_opp : push_FtoZ.
+ Hint Rewrite ->@F.to_Z_of_Z : push_FtoZ.
+
+ Lemma Fm_bounded_alt (x : F m)
+ : (0 <=? F.to_Z x) && (F.to_Z x <=? Z.pos m - 1) = true.
+ Proof using m_eq.
+ clear -m_eq.
+ destruct x as [x H]; cbn [F.to_Z proj1_sig].
+ pose proof (Z.mod_pos_bound x (Z.pos m)).
+ rewrite andb_true_iff; split; Z.ltb_to_lt; lia.
+ Qed.
+
+ Lemma Fm_bounded_alt' (x : F m)
+ : 0 <= F.to_Z x < Z.pos m.
+ Proof using m_eq.
+ clear -m_eq.
+ destruct x as [x H]; cbn [F.to_Z proj1_sig].
+ pose proof (Z.mod_pos_bound x (Z.pos m)).
+ split; Z.ltb_to_lt; lia.
+ Qed.
+
+ Lemma Good : GoodT.
+ Proof.
+ split_and.
+ repeat match goal with
+ | [ H : context[andb _ true] |- _ ] => setoid_rewrite andb_true_r in H
+ end.
+ eapply subsetoid_ring_by_ring_isomorphism;
+ cbv [ring_opp ring_add ring_sub ring_mul ring_encode F.sub] in *;
+ repeat match goal with
+ | [ H : forall arg : _ * unit, _ |- _ ] => specialize (fun arg => H (arg, tt))
+ | [ H : forall arg : _ * (_ * unit), _ |- _ ] => specialize (fun a b => H (a, (b, tt)))
+ | _ => progress cbn [fst snd] in *
+ | _ => solve [ auto using andb_true_intro, conj with nocore ]
+ | _ => progress intros
+ | [ H : is_bounded_by _ _ = true /\ _ |- _ ] => destruct H
+ | [ |- is_bounded_by _ _ = true /\ _ ] => split
+ | [ H : _ |- is_bounded_by _ _ = true ] => apply H
+ | [ H : _ |- valid _ ] => rewrite H
+ | [ H : context[valid _] |- valid _ ] => apply H
+ | [ |- _ <-> _ ] => reflexivity
+ | [ |- ?x = ?x ] => reflexivity
+ | [ |- _ = _ :> Z ] => first [ reflexivity | rewrite <- m_eq; reflexivity ]
+ | [ H : context[?x] |- Fdecode ?x = _ ] => rewrite H
+ | [ H : context[?x _] |- Fdecode (?x _) = _ ] => rewrite H
+ | [ H : context[?x _ _] |- Fdecode (?x _ _) = _ ] => rewrite H
+ | _ => progress cbv [Fdecode]
+ | [ |- _ = _ :> F _ ] => apply F.eq_to_Z_iff
+ | _ => progress autorewrite with push_FtoZ
+ | _ => rewrite m_eq
+ | [ H : context[?f (?x _ _)] |- context[eval (?f (?x _ _))] ] => rewrite H
+ | [ H : context[?f (?x _)] |- context[eval (?f (?x _))] ] => rewrite H
+ | [ H : context[?f ?x] |- context[eval (?f ?x)] ] => rewrite H
+ | [ H : context[?x _ _] |- context[eval (?x _ _)] ] => rewrite H
+ | [ H : context[?x _] |- context[eval (?x _)] ] => rewrite H
+ | [ H : context[?x] |- context[eval ?x] ] => rewrite H
+ | [ H : context[?y _ _ = ?x _ _], H' : context[is_bounded_by _ (?y _ _) = true]
+ |- is_bounded_by _ (?x _ _) = true ]
+ => rewrite <- H; [ apply H' | .. ]
+ | [ H : context[?y _ = ?x _], H' : context[is_bounded_by _ (?y _) = true]
+ |- is_bounded_by _ (?x _) = true ]
+ => rewrite <- H; [ apply H' | .. ]
+ | [ H : context[?y = ?x], H' : context[is_bounded_by _ ?y = true]
+ |- is_bounded_by _ ?x = true ]
+ => rewrite <- H; [ apply H' | .. ]
+ | [ |- context[List.length ?x] ]
+ => erewrite (length_is_bounded_by _ x)
+ by eauto using andb_true_intro, conj with nocore
+ | [ |- _ = _ :> Z ]
+ => push_Zmod; reflexivity
+ | _ => pull_Zmod; rewrite Z.add_opp_r
+ | _ => rewrite expanding_id_id
+ | [ |- context[F.to_Z _ mod (_ - _)] ]
+ => rewrite <- m_eq, F.mod_to_Z
+ | _ => rewrite <- m_eq; apply Fm_bounded_alt
+ | _ => rewrite <- m_eq; apply Fm_bounded_alt'
+ | [ |- context[andb _ true] ] => rewrite andb_true_r
+ end.
+ Qed.
+ End ring_goal.
+End MontgomeryStyleRing.
+
Import Associational Positional.
Import
@@ -289,13 +514,14 @@ Notation "x" := (expr.Var x) (only printing, at level 9) : expr_scope.
Axiom admit_pf : False.
Notation admit := (match admit_pf with end).
+
Module Pipeline.
Import GeneralizeVar.
Inductive ErrorMessage :=
| Computed_bounds_are_not_tight_enough
{t} (computed_bounds expected_bounds : ZRange.type.base.option.interp (type.final_codomain t))
(syntax_tree : Expr t) (arg_bounds : type.for_each_lhs_of_arrow ZRange.type.option.interp t)
- | Type_too_complicated_for_cps (t : type)
+ | No_modular_inverse (descr : string) (v : Z) (m : Z)
| Value_not_leZ (descr : string) (lhs rhs : Z)
| Value_not_leQ (descr : string) (lhs rhs : Q)
| Value_not_ltZ (descr : string) (lhs rhs : Z)
@@ -395,8 +621,8 @@ Module Pipeline.
=> (["(Unprintible syntax tree used in bounds analysis)" ++ String.NewLine]%string)
++ ["Stringification failed on the syntax tree:"] ++ show_lines false syntax_tree ++ [errs]
end)%list
- | Type_too_complicated_for_cps t
- => ["Type too complicated for cps: " ++ show false t]
+ | No_modular_inverse descr v m
+ => ["Could not compute a modular inverse (" ++ descr ++ ") for " ++ show false v ++ " mod " ++ show false m]
| Value_not_leZ descr lhs rhs
=> ["Value not ≤ (" ++ descr ++ ") : expected " ++ show false lhs ++ " ≤ " ++ show false rhs]
| Value_not_leQ descr lhs rhs
@@ -437,6 +663,7 @@ Module Pipeline.
:= (*let E := expr.Uncurry E in*)
let E := PartialEvaluateWithListInfoFromBounds E arg_bounds in
let E := PartialEvaluate E in
+ let E := RewriteRules.RewriteArith E in
(* Note that DCE evaluates the expr with two different [var]
arguments, and so results in a pipeline that is 2x slower
unless we pass through a uniformly concrete [var] type
@@ -448,7 +675,10 @@ Module Pipeline.
let E := FromFlat e in
let E := if with_subst01 then Subst01.Subst01 E else E in
let E := UnderLets.LetBindReturn E in
- let E := PartialEvaluate E in (* after inlining, see if any new rewrite redexes are available *)
+ let E := RewriteRules.RewriteArith E in (* after inlining, see if any new rewrite redexes are available *)
+ dlet_nd e := ToFlat E in
+ let E := FromFlat e in
+ let E := if with_dead_code_elimination then DeadCodeElimination.EliminateDead E else E in
let E := ReassociateSmallConstants.Reassociate (2^8) E in
let E := match translate_to_fancy with
| Some {| invert_low := invert_low ; invert_high := invert_high |} => RewriteRules.RewriteToFancy invert_low invert_high E
@@ -823,12 +1053,12 @@ Derive to_bytes_gen
(bitwidth : Z)
(m_enc : list Z)
(f : list Z),
- Interp (t:=reify_type_of to_bytesmod)
+ Interp (t:=reify_type_of freeze_to_bytesmod)
to_bytes_gen limbwidth_num limbwidth_den n bitwidth m_enc f
- = to_bytesmod limbwidth_num limbwidth_den n bitwidth m_enc f)
+ = freeze_to_bytesmod limbwidth_num limbwidth_den n bitwidth m_enc f)
As to_bytes_gen_correct.
Proof. cache_reify (). Qed.
-Hint Extern 1 (_ = to_bytesmod _ _ _ _ _ _) => simple apply to_bytes_gen_correct : reify_gen_cache.
+Hint Extern 1 (_ = freeze_to_bytesmod _ _ _ _ _ _) => simple apply to_bytes_gen_correct : reify_gen_cache.
Derive from_bytes_gen
SuchThat (forall (limbwidth_num limbwidth_den : Z)
@@ -1152,7 +1382,7 @@ Module Import UnsaturatedSolinas.
:= BoundsPipeline_with_bytes_no_subst01_correct
(Some tight_bounds, tt)
prime_bytes_bounds
- (to_bytesmod (Qnum limbwidth) (Z.pos (Qden limbwidth)) n machine_wordsize m_enc).
+ (freeze_to_bytesmod (Qnum limbwidth) (Z.pos (Qden limbwidth)) n machine_wordsize m_enc).
Definition srfrom_bytes prefix
:= BoundsPipelineToStrings_with_bytes_no_subst01
@@ -1373,8 +1603,8 @@ Module Import UnsaturatedSolinas.
(Hf : type.andb_bool_for_each_lhs_of_arrow (t:=to_bytesT) (@ZRange.type.option.is_bounded_by) (Some tight_bounds, tt) f = true),
((ZRange.type.base.option.is_bounded_by prime_bytes_bounds (type.app_curried (Interp rto_bytesv) f) = true
/\ (forall cast_outside_of_range, type.app_curried (expr.Interp (@ident.gen_interp cast_outside_of_range) rto_bytesv) f
- = type.app_curried (t:=to_bytesT) (to_bytesmod (Qnum limbwidth) (Z.pos (Qden limbwidth)) n machine_wordsize m_enc) f))
- /\ (Positional.eval (weight 8 1) n_bytes (type.app_curried (t:=to_bytesT) (to_bytesmod (Qnum limbwidth) (Z.pos (Qden limbwidth)) n machine_wordsize m_enc) f)) = (Positional.eval (weight (Qnum limbwidth) (Z.pos (Qden limbwidth))) n (fst f) mod m))).
+ = type.app_curried (t:=to_bytesT) (freeze_to_bytesmod (Qnum limbwidth) (Z.pos (Qden limbwidth)) n machine_wordsize m_enc) f))
+ /\ (Positional.eval (weight 8 1) n_bytes (type.app_curried (t:=to_bytesT) (freeze_to_bytesmod (Qnum limbwidth) (Z.pos (Qden limbwidth)) n machine_wordsize m_enc) f)) = (Positional.eval (weight (Qnum limbwidth) (Z.pos (Qden limbwidth))) n (fst f) mod m))).
(** XXX TODO MOVE ME *)
Lemma fold_andb_map_snoc A B f x xs y ys
@@ -1448,7 +1678,7 @@ Module Import UnsaturatedSolinas.
{ apply Hto_bytesv; assumption. }
{ cbn [type.for_each_lhs_of_arrow type_base type.andb_bool_for_each_lhs_of_arrow ZRange.type.option.is_bounded_by fst snd] in *.
rewrite Bool.andb_true_iff in *; split_and'.
- etransitivity; [ apply eval_to_bytesmod | f_equal; (eassumption || (symmetry; eassumption)) ];
+ etransitivity; [ apply eval_freeze_to_bytesmod | f_equal; (eassumption || (symmetry; eassumption)) ];
auto; try omega.
{ erewrite Ring.length_is_bounded_by by eassumption; assumption. }
{ lazymatch goal with
@@ -1834,6 +2064,739 @@ Goal False.
Abort.
*)
+Module WordByWordMontgomery.
+ Import Arithmetic.WordByWordMontgomery.
+ Derive mul_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (m' : Z)
+ (f g : list Z),
+ Interp (t:=reify_type_of mulmod)
+ mul_gen bitwidth n m m' f g
+ = mulmod bitwidth n m m' f g)
+ As mul_gen_correct.
+ Proof. Time cache_reify (). Time Qed.
+ Hint Extern 1 (_ = mulmod _ _ _ _ _ _) => simple apply mul_gen_correct : reify_gen_cache.
+
+ Derive square_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (m' : Z)
+ (f : list Z),
+ Interp (t:=reify_type_of squaremod)
+ square_gen bitwidth n m m' f
+ = squaremod bitwidth n m m' f)
+ As square_gen_correct.
+ Proof.
+ Time cache_reify ().
+ (* we would do something faster, but it breaks extraction COQBUG(https://github.com/coq/coq/issues/7954) *)
+ (*
+ intros; etransitivity; [ | cbv [squaremod]; apply mul_gen_correct ].
+ subst square_gen.
+ instantiate (1:=ltac:(let r := Reify (fun F (bitwidth:Z) (n:nat) (m m' : Z) (f : list Z) => (F bitwidth n m m' f f):list Z) in refine (r @ mul_gen)%Expr)).
+ reflexivity.
+ *)
+ Time Qed.
+ Hint Extern 1 (_ = squaremod _ _ _ _ _) => simple apply square_gen_correct : reify_gen_cache.
+
+ Derive encode_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (m' : Z)
+ (v : Z),
+ Interp (t:=reify_type_of encodemod)
+ encode_gen bitwidth n m m' v
+ = encodemod bitwidth n m m' v)
+ As encode_gen_correct.
+ Proof.
+ Time cache_reify ().
+ (* we would do something faster, but it breaks extraction COQBUG(https://github.com/coq/coq/issues/7954) *)
+ (*
+ intros; etransitivity; [ | cbv [encodemod]; apply mul_gen_correct ].
+ subst encode_gen; revert bitwidth n m m' v.
+ lazymatch goal with
+ | [ |- forall bw n m m' v, ?interp ?ev bw n m m' v = ?interp' mul_gen bw n m m' (@?A bw n m m' v) (@?B bw n m m' v) ]
+ => let rv := constr:(fun F bw n m m' v => (F bw n m m' (A bw n m m' v) (B bw n m m' v)):list Z) in
+ intros;
+ instantiate (1:=ltac:(let r := Reify rv in
+ refine (r @ mul_gen)%Expr))
+ end.
+ reflexivity.
+ *)
+ Time Qed.
+ Hint Extern 1 (_ = encodemod _ _ _ _ _) => simple apply encode_gen_correct : reify_gen_cache.
+
+ Derive add_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (f g : list Z),
+ Interp (t:=reify_type_of addmod)
+ add_gen bitwidth n m f g
+ = addmod bitwidth n m f g)
+ As add_gen_correct.
+ Proof. Time cache_reify (). Time Qed.
+ Hint Extern 1 (_ = addmod _ _ _ _ _) => simple apply add_gen_correct : reify_gen_cache.
+
+ Derive sub_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (f g : list Z),
+ Interp (t:=reify_type_of submod)
+ sub_gen bitwidth n m f g
+ = submod bitwidth n m f g)
+ As sub_gen_correct.
+ Proof. Time cache_reify (). Time Qed.
+ Hint Extern 1 (_ = submod _ _ _ _ _) => simple apply sub_gen_correct : reify_gen_cache.
+
+ Derive opp_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (f : list Z),
+ Interp (t:=reify_type_of oppmod)
+ opp_gen bitwidth n m f
+ = oppmod bitwidth n m f)
+ As opp_gen_correct.
+ Proof. Time cache_reify (). Time Qed.
+ Hint Extern 1 (_ = oppmod _ _ _ _) => simple apply opp_gen_correct : reify_gen_cache.
+
+ Derive from_montgomery_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (m' : Z)
+ (f : list Z),
+ Interp (t:=reify_type_of from_montgomery_mod)
+ from_montgomery_gen bitwidth n m m' f
+ = from_montgomery_mod bitwidth n m m' f)
+ As from_montgomery_gen_correct.
+ Proof.
+ Time cache_reify ().
+ (* we would do something faster, but it breaks extraction COQBUG(https://github.com/coq/coq/issues/7954) *)
+ (*
+ intros; etransitivity; [ | cbv [from_montgomery_mod]; apply mul_gen_correct ].
+ subst from_montgomery_gen.
+ instantiate (1:=ltac:(let r := Reify (fun F (bitwidth:Z) (n:nat) (m m' : Z) (f : list Z) => (F bitwidth n m m' f (onemod bitwidth n)):list Z) in refine (r @ mul_gen)%Expr)).
+ reflexivity.
+ *)
+ Qed.
+ Hint Extern 1 (_ = from_montgomery_mod _ _ _ _ _) => simple apply from_montgomery_gen_correct : reify_gen_cache.
+
+ Definition zeromod bitwidth n m m' := encodemod bitwidth n m m' 0.
+ Definition onemod bitwidth n m m' := encodemod bitwidth n m m' 1.
+ Derive zero_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (m' : Z),
+ Interp (t:=reify_type_of zeromod)
+ zero_gen bitwidth n m m'
+ = zeromod bitwidth n m m')
+ As zero_gen_correct.
+ Proof.
+ (* Time cache_reify (). *)
+ (* we do something faster *)
+ intros; etransitivity; [ | cbv [zeromod]; apply encode_gen_correct ].
+ subst zero_gen.
+ instantiate (1:=ltac:(let r := Reify (fun F (bitwidth:Z) (n:nat) (m m' : Z) => (F bitwidth n m m' 0):list Z) in refine (r @ encode_gen)%Expr)).
+ reflexivity.
+ Qed.
+ Hint Extern 1 (_ = zeromod _ _ _ _) => simple apply zero_gen_correct : reify_gen_cache.
+
+ Derive one_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (m : Z)
+ (m' : Z),
+ Interp (t:=reify_type_of onemod)
+ one_gen bitwidth n m m'
+ = onemod bitwidth n m m')
+ As one_gen_correct.
+ Proof.
+ (* Time cache_reify (). *)
+ (* we do something faster *)
+ intros; etransitivity; [ | cbv [onemod]; apply encode_gen_correct ].
+ subst one_gen.
+ instantiate (1:=ltac:(let r := Reify (fun F (bitwidth:Z) (n:nat) (m m' : Z) => (F bitwidth n m m' 1):list Z) in refine (r @ encode_gen)%Expr)).
+ reflexivity.
+ Qed.
+ Hint Extern 1 (_ = onemod _ _ _ _) => simple apply one_gen_correct : reify_gen_cache.
+
+ Derive nonzero_gen
+ SuchThat (forall (f : list Z),
+ Interp (t:=reify_type_of nonzeromod)
+ nonzero_gen f
+ = nonzeromod f)
+ As nonzero_gen_correct.
+ Proof. Time cache_reify (). Time Qed.
+ Hint Extern 1 (_ = nonzeromod _) => simple apply nonzero_gen_correct : reify_gen_cache.
+
+ Derive to_bytes_gen
+ SuchThat (forall (bitwidth : Z)
+ (n : nat)
+ (f : list Z),
+ Interp (t:=reify_type_of to_bytesmod)
+ to_bytes_gen bitwidth n f
+ = to_bytesmod bitwidth n f)
+ As to_bytes_gen_correct.
+ Proof. cache_reify (). Qed.
+ Hint Extern 1 (_ = to_bytesmod _ _ _) => simple apply to_bytes_gen_correct : reify_gen_cache.
+
+ Section rcarry_mul.
+ Context (s : Z)
+ (c : list (Z * Z))
+ (machine_wordsize : Z).
+
+ Let n : nat := Z.to_nat (Qceiling (Z.log2_up s / machine_wordsize)).
+ Let m := s - Associational.eval c.
+ Let r := 2^machine_wordsize.
+ Let r' := match Z.modinv r m with
+ | Some r' => r'
+ | None => 0
+ end.
+ Let m' := match Z.modinv (-m) r with
+ | Some m' => m'
+ | None => 0
+ end.
+ Let n_bytes := bytes_n machine_wordsize 1 n.
+ Let prime_upperbound_list : list Z
+ := encode (UniformWeight.uweight machine_wordsize) n s c (s-1).
+ Let prime_bytes_upperbound_list : list Z
+ := encode (weight 8 1) n_bytes s c (s-1).
+ Let upperbounds : list Z := prime_upperbound_list.
+ Definition prime_bound : ZRange.type.option.interp (base.type.Z)
+ := Some r[0~>(s - Associational.eval c - 1)]%zrange.
+ Definition prime_bounds : ZRange.type.option.interp (base.type.list (base.type.Z))
+ := Some (List.map (fun v => Some r[0 ~> v]%zrange) prime_upperbound_list).
+ Definition prime_bytes_bounds : ZRange.type.option.interp (base.type.list (base.type.Z))
+ := Some (List.map (fun v => Some r[0 ~> v]%zrange) prime_bytes_upperbound_list).
+ Definition saturated_bounds : ZRange.type.option.interp (base.type.list (base.type.Z))
+ := Some (List.repeat (Some r[0 ~> 2^machine_wordsize-1]%zrange) n).
+
+ Definition m_enc : list Z
+ := encode (UniformWeight.uweight machine_wordsize) n s c (s-Associational.eval c).
+
+ Definition relax_zrange_of_machine_wordsize
+ := relax_zrange_gen [1; machine_wordsize; 2 * machine_wordsize]%Z.
+
+ Definition relax_zrange_of_machine_wordsize_with_bytes
+ := relax_zrange_gen [1; 8; machine_wordsize; 2 * machine_wordsize]%Z.
+
+ Let relax_zrange := relax_zrange_of_machine_wordsize.
+ Let relax_zrange_with_bytes := relax_zrange_of_machine_wordsize_with_bytes.
+ Definition bounds : list (ZRange.type.option.interp base.type.Z)
+ := Option.invert_Some saturated_bounds (*List.map (fun u => Some r[0~>u]%zrange) upperbounds*).
+
+ (** Note: If you change the name or type signature of this
+ function, you will need to update the code in CLI.v *)
+ Definition check_args {T} (res : Pipeline.ErrorT T)
+ : Pipeline.ErrorT T
+ := fold_right
+ (fun '(b, e) k => if b:bool then Error e else k)
+ res
+ [(negb (1 <? machine_wordsize)%Z, Pipeline.Value_not_ltZ "machine_wordsize <= 1" 1 machine_wordsize);
+ ((negb (0 <? Associational.eval c))%Z, Pipeline.Value_not_ltZ "Associational.eval c ≤ 0" 0 (Associational.eval c));
+ ((negb (Associational.eval c <? s))%Z, Pipeline.Value_not_ltZ "s ≤ Associational.eval c" (Associational.eval c) s);
+ ((s =? 0)%Z, Pipeline.Values_not_provably_distinctZ "s = 0" s 0);
+ ((n =? 0)%nat, Pipeline.Values_not_provably_distinctZ "n = 0" n 0%nat);
+ ((r' =? 0)%Z, Pipeline.No_modular_inverse "r⁻¹ mod m" r m);
+ (negb ((r * r') mod m =? 1)%Z, Pipeline.Values_not_provably_equalZ "(r * r') mod m ≠ 1" ((r * r') mod m) 1);
+ (negb ((m * m') mod r =? (-1) mod r)%Z, Pipeline.Values_not_provably_equalZ "(m * m') mod r ≠ (-1) mod r" ((m * m') mod r) ((-1) mod r));
+ (negb (s <=? r^n), Pipeline.Value_not_leZ "r^n ≤ s" s (r^n));
+ (negb (1 <? s - Associational.eval c), Pipeline.Value_not_ltZ "s - Associational.eval c ≤ 1" 1 (s - Associational.eval c))].
+
+ Notation type_of_strip_3arrow := ((fun (d : Prop) (_ : forall A B C, d) => d) _).
+
+ Notation BoundsPipelineToStrings prefix name comment rop in_bounds out_bounds
+ := ((prefix ++ name)%string,
+ Pipeline.BoundsPipelineToStrings
+ true (* static *) prefix (prefix ++ name)%string comment%string%list
+ (*false*) true None
+ relax_zrange
+ rop%Expr in_bounds out_bounds).
+
+ Notation BoundsPipeline_correct in_bounds out_bounds op
+ := (fun rv (rop : Expr (reify_type_of op)) Hrop
+ => @Pipeline.BoundsPipeline_correct_trans
+ (*false*) true None
+ relax_zrange
+ (relax_zrange_gen_good _)
+ _
+ rop
+ in_bounds
+ out_bounds
+ op
+ Hrop rv)
+ (only parsing).
+
+ Notation BoundsPipelineToStrings_no_subst01 prefix name comment rop in_bounds out_bounds
+ := ((prefix ++ name)%string,
+ Pipeline.BoundsPipelineToStrings
+ true (* static *) prefix (prefix ++ name)%string comment%string%list
+ (*false*) false None
+ relax_zrange
+ rop%Expr in_bounds out_bounds).
+
+ Notation BoundsPipeline_no_subst01_correct in_bounds out_bounds op
+ := (fun rv (rop : Expr (reify_type_of op)) Hrop
+ => @Pipeline.BoundsPipeline_correct_trans
+ (*false*) false None
+ relax_zrange
+ (relax_zrange_gen_good _)
+ _
+ rop
+ in_bounds
+ out_bounds
+ op
+ Hrop rv)
+ (only parsing).
+
+ Notation BoundsPipelineToStrings_with_bytes_no_subst01 prefix name comment rop in_bounds out_bounds
+ := ((prefix ++ name)%string,
+ Pipeline.BoundsPipelineToStrings
+ true (* static *) prefix (prefix ++ name)%string comment%string%list
+ (*false*) false None
+ relax_zrange_with_bytes
+ rop%Expr in_bounds out_bounds).
+
+ Notation BoundsPipeline_with_bytes_no_subst01_correct in_bounds out_bounds op
+ := (fun rv (rop : Expr (reify_type_of op)) Hrop
+ => @Pipeline.BoundsPipeline_correct_trans
+ (*false*) false None
+ relax_zrange_with_bytes
+ (relax_zrange_gen_good _)
+ _
+ rop
+ in_bounds
+ out_bounds
+ op
+ Hrop rv)
+ (only parsing).
+
+ (* N.B. We only need [rmul] if we want to extract the Pipeline; otherwise we can just use [rmul_correct] *)
+ Definition srmul prefix
+ := BoundsPipelineToStrings_no_subst01
+ prefix "mul" []
+ (mul_gen
+ @ GallinaReify.Reify machine_wordsize @ GallinaReify.Reify n @ GallinaReify.Reify m @ GallinaReify.Reify m')
+ (Some bounds, (Some bounds, tt))
+ (Some bounds).
+
+ Definition rmul_correct
+ := BoundsPipeline_no_subst01_correct
+ (Some bounds, (Some bounds, tt))
+ (Some bounds)
+ (mulmod machine_wordsize n m m').
+
+ Definition srsquare prefix
+ := BoundsPipelineToStrings_no_subst01
+ prefix "square" []
+ (square_gen
+ @ GallinaReify.Reify machine_wordsize @ GallinaReify.Reify n @ GallinaReify.Reify m @ GallinaReify.Reify m')
+ (Some bounds, tt)
+ (Some bounds).
+
+ Definition rsquare_correct
+ := BoundsPipeline_no_subst01_correct
+ (Some bounds, tt)
+ (Some bounds)
+ (squaremod machine_wordsize n m m').
+
+ Definition sradd prefix
+ := BoundsPipelineToStrings
+ prefix "add" []
+ (add_gen
+ @ GallinaReify.Reify machine_wordsize @ GallinaReify.Reify n @ GallinaReify.Reify m)
+ (Some bounds, (Some bounds, tt))
+ (Some bounds).
+
+ Definition radd_correct
+ := BoundsPipeline_correct
+ (Some bounds, (Some bounds, tt))
+ (Some bounds)
+ (addmod machine_wordsize n m).
+
+ Definition srsub prefix
+ := BoundsPipelineToStrings
+ prefix "sub" []
+ (sub_gen
+ @ GallinaReify.Reify machine_wordsize @ GallinaReify.Reify n @ GallinaReify.Reify m)
+ (Some bounds, (Some bounds, tt))
+ (Some bounds).
+
+ Definition rsub_correct
+ := BoundsPipeline_correct
+ (Some bounds, (Some bounds, tt))
+ (Some bounds)
+ (submod machine_wordsize n m).
+
+ Definition sropp prefix
+ := BoundsPipelineToStrings
+ prefix "opp" []
+ (opp_gen
+ @ GallinaReify.Reify machine_wordsize @ GallinaReify.Reify n @ GallinaReify.Reify m)
+ (Some bounds, tt)
+ (Some bounds).
+
+ Definition ropp_correct
+ := BoundsPipeline_correct
+ (Some bounds, tt)
+ (Some bounds)
+ (oppmod machine_wordsize n m).
+
+ Definition srfrom_montgomery prefix
+ := BoundsPipelineToStrings
+ prefix "from_montgomery" []
+ (from_montgomery_gen
+ @ GallinaReify.Reify machine_wordsize @ GallinaReify.Reify n @ GallinaReify.Reify m @ GallinaReify.Reify m')
+ (Some bounds, tt)
+ (Some bounds).
+
+ Definition rfrom_montgomery_correct
+ := BoundsPipeline_correct
+ (Some bounds, tt)
+ (Some bounds)
+ (from_montgomery_mod machine_wordsize n m m').
+
+ Definition srnonzero prefix
+ := BoundsPipelineToStrings
+ prefix "nonzero" []
+ nonzero_gen
+ (Some bounds, tt)
+ (Some r[0~>r-1]%zrange).
+
+ Definition rnonzero_correct
+ := BoundsPipeline_correct
+ (Some bounds, tt)
+ (Some r[0~>r-1]%zrange)
+ nonzeromod.
+
+ Definition srselectznz prefix
+ := BoundsPipelineToStrings_with_bytes_no_subst01
+ prefix "selectznz" []
+ selectznz_gen
+ (Some r[0~>1], (saturated_bounds, (saturated_bounds, tt)))%zrange
+ saturated_bounds.
+
+ Definition rselectznz_correct
+ := BoundsPipeline_with_bytes_no_subst01_correct
+ (Some r[0~>1], (saturated_bounds, (saturated_bounds, tt)))%zrange
+ saturated_bounds
+ Positional.select.
+
+ Definition srto_bytes prefix
+ := BoundsPipelineToStrings_with_bytes_no_subst01
+ prefix "to_bytes" []
+ (to_bytes_gen
+ @ GallinaReify.Reify machine_wordsize @ GallinaReify.Reify n)
+ (prime_bounds, tt)
+ prime_bytes_bounds.
+
+ Definition rto_bytes_correct
+ := BoundsPipeline_with_bytes_no_subst01_correct
+ (prime_bounds, tt)
+ prime_bytes_bounds
+ (to_bytesmod machine_wordsize n).
+
+ Definition srfrom_bytes prefix
+ := BoundsPipelineToStrings_with_bytes_no_subst01
+ prefix "from_bytes" []
+ (from_bytes_gen
+ @ GallinaReify.Reify machine_wordsize @ GallinaReify.Reify 1 @ GallinaReify.Reify n)
+ (prime_bytes_bounds, tt)
+ prime_bounds.
+
+ Definition rfrom_bytes_correct
+ := BoundsPipeline_with_bytes_no_subst01_correct
+ (prime_bytes_bounds, tt)
+ prime_bounds
+ (from_bytesmod machine_wordsize 1 n).
+
+ Definition rencode_correct
+ := BoundsPipeline_correct
+ (prime_bound, tt)
+ (Some bounds)
+ (encodemod machine_wordsize n m m').
+
+ Definition rzero_correct
+ := BoundsPipeline_correct
+ tt
+ (Some bounds)
+ (zeromod machine_wordsize n m m').
+
+ Definition rone_correct
+ := BoundsPipeline_correct
+ tt
+ (Some bounds)
+ (onemod machine_wordsize n m m').
+
+ Notation srmulx := (srmulx machine_wordsize).
+ Notation srmulx_correct := (srmulx_correct machine_wordsize).
+ Notation sraddcarryx := (sraddcarryx machine_wordsize).
+ Notation sraddcarryx_correct := (sraddcarryx_correct machine_wordsize).
+ Notation srsubborrowx := (srsubborrowx machine_wordsize).
+ Notation srsubborrowx_correct := (srsubborrowx_correct machine_wordsize).
+ Notation srcmovznz := (srcmovznz machine_wordsize).
+ Notation srcmovznz_correct := (srcmovznz_correct machine_wordsize).
+
+ (* we need to strip off [Hrv : ... = Pipeline.Success rv] and related arguments *)
+ Definition rmul_correctT rv : Prop
+ := type_of_strip_3arrow (@rmul_correct rv).
+ Definition rsquare_correctT rv : Prop
+ := type_of_strip_3arrow (@rsquare_correct rv).
+ Definition radd_correctT rv : Prop
+ := type_of_strip_3arrow (@radd_correct rv).
+ Definition rsub_correctT rv : Prop
+ := type_of_strip_3arrow (@rsub_correct rv).
+ Definition rfrom_montgomery_correctT rv : Prop
+ := type_of_strip_3arrow (@rfrom_montgomery_correct rv).
+ Definition ropp_correctT rv : Prop
+ := type_of_strip_3arrow (@ropp_correct rv).
+ Definition rnonzero_correctT rv : Prop
+ := type_of_strip_3arrow (@rnonzero_correct rv).
+ Definition rselectznz_correctT rv : Prop
+ := type_of_strip_3arrow (@rselectznz_correct rv).
+ Definition rto_bytes_correctT rv : Prop
+ := type_of_strip_3arrow (@rto_bytes_correct rv).
+ Definition rfrom_bytes_correctT rv : Prop
+ := type_of_strip_3arrow (@rfrom_bytes_correct rv).
+ Definition rencode_correctT rv : Prop
+ := type_of_strip_3arrow (@rencode_correct rv).
+ Definition rzero_correctT rv : Prop
+ := type_of_strip_3arrow (@rzero_correct rv).
+ Definition rone_correctT rv : Prop
+ := type_of_strip_3arrow (@rone_correct rv).
+
+ Section make_ring.
+ Let mv : positive := Z.to_pos (s - Associational.eval c).
+ Context (curve_good : check_args (Success tt) = Success tt)
+ {rmulv} (Hrmulv : rmul_correctT rmulv)
+ {raddv} (Hraddv : radd_correctT raddv)
+ {rsubv} (Hrsubv : rsub_correctT rsubv)
+ {rfrom_montgomeryv} (Hrfrom_montgomeryv : rfrom_montgomery_correctT rfrom_montgomeryv)
+ {roppv} (Hroppv : ropp_correctT roppv)
+ {rzerov} (Hrzerov : rzero_correctT rzerov)
+ {ronev} (Hronev : rone_correctT ronev)
+ {rencodev} (Hrencodev : rencode_correctT rencodev)
+ {rnonzerov} (Hrnonzerov : rnonzero_correctT rnonzerov)
+ {rto_bytesv} (Hto_bytesv : rto_bytes_correctT rto_bytesv)
+ {rfrom_bytesv} (Hfrom_bytesv : rfrom_bytes_correctT rfrom_bytesv).
+
+ Local Ltac use_curve_good_t :=
+ repeat first [ assumption
+ | progress rewrite ?map_length, ?Z.mul_0_r, ?Pos.mul_1_r, ?Z.mul_1_r in *
+ | reflexivity
+ | lia
+ | rewrite interp_reify_list, ?map_map
+ | rewrite map_ext with (g:=id), map_id
+ | progress distr_length
+ | progress cbv [Qceiling Qfloor Qopp Qdiv Qplus inject_Z Qmult Qinv] in *
+ | progress cbv [Qle] in *
+ | progress cbn -[reify_list] in *
+ | progress intros
+ | solve [ auto ] ].
+
+ Lemma use_curve_good
+ : Z.pos mv = s - Associational.eval c
+ /\ Z.pos mv <> 0
+ /\ s - Associational.eval c <> 0
+ /\ s <> 0
+ /\ 0 < machine_wordsize
+ /\ n <> 0%nat
+ /\ List.length bounds = n
+ /\ List.length bounds = n
+ /\ 0 < 1 <= machine_wordsize
+ /\ 0 < Associational.eval c < s
+ /\ (r * r') mod m = 1
+ /\ (m * m') mod r = (-1) mod r
+ /\ 0 < machine_wordsize
+ /\ 1 < m
+ /\ m < r^n.
+ Proof.
+ clear -curve_good.
+ cbv [check_args fold_right] in curve_good.
+ cbv [bounds prime_bound m_enc prime_bounds] in *.
+ break_innermost_match_hyps; try discriminate.
+ rewrite negb_false_iff in *.
+ Z.ltb_to_lt.
+ rewrite NPeano.Nat.eqb_neq in *.
+ intros.
+ cbv [Qnum Qden Qceiling Qfloor Qopp Qdiv Qplus inject_Z Qmult Qinv] in *.
+ rewrite ?map_length, ?Z.mul_0_r, ?Pos.mul_1_r, ?Z.mul_1_r in *.
+ specialize_by lia.
+ repeat match goal with H := _ |- _ => subst H end.
+ repeat match goal with
+ | [ H : list_beq _ _ _ _ = true |- _ ] => apply internal_list_dec_bl in H; [ | intros; Z.ltb_to_lt; omega.. ]
+ end.
+ repeat apply conj.
+ { destruct (s - Associational.eval c) eqn:?; cbn; lia. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ { use_curve_good_t. }
+ Qed.
+
+ (** TODO: Find a better place to put the spec for [to_bytes] *)
+ Definition GoodT : Prop
+ := @MontgomeryStyleRing.GoodT
+ machine_wordsize 1
+ n s c
+ bounds
+ (valid machine_wordsize n m)
+ (Interp rfrom_montgomeryv)
+ (Interp rmulv)
+ (Interp raddv)
+ (Interp rsubv)
+ (Interp roppv)
+ (Interp rzerov)
+ (Interp ronev)
+ (Interp rencodev)
+ /\ (let to_bytesT := (base.type.list base.type.Z -> base.type.list base.type.Z)%etype in
+ forall f
+ (Hf : type.andb_bool_for_each_lhs_of_arrow (t:=to_bytesT) (@ZRange.type.option.is_bounded_by) (prime_bounds, tt) f = true),
+ ((ZRange.type.base.option.is_bounded_by prime_bytes_bounds (type.app_curried (Interp rto_bytesv) f) = true
+ /\ (forall cast_outside_of_range, type.app_curried (expr.Interp (@ident.gen_interp cast_outside_of_range) rto_bytesv) f
+ = type.app_curried (t:=to_bytesT) (to_bytesmod machine_wordsize n) f))
+ /\ (Positional.eval (weight 8 1) n_bytes (type.app_curried (t:=to_bytesT) (to_bytesmod machine_wordsize n) f)) = (Positional.eval (weight machine_wordsize 1) n (fst f) mod m)))
+ /\ (forall f
+ (Hf : type.andb_bool_for_each_lhs_of_arrow (t:=(base.type.list base.type.Z -> base.type.Z)%etype) (@ZRange.type.option.is_bounded_by) (Some bounds, tt) f = true), (Interp rnonzerov (fst f) = 0) <-> ((@eval machine_wordsize n (from_montgomery_mod machine_wordsize n m m' (fst f))) mod m = 0)).
+
+ (** XXX TODO MOVE ME *)
+ Local Opaque valid addmod submod oppmod encodemod mulmod from_montgomery_mod nonzeromod.
+ Theorem Good : GoodT.
+ Proof.
+ pose proof use_curve_good; destruct_head'_and; destruct_head_hnf' ex.
+ split; [ | split ].
+ { eapply MontgomeryStyleRing.Good;
+ lazymatch goal with
+ | [ H : ?P ?rop |- context[expr.Interp _ ?rop] ]
+ => intros;
+ let H1 := fresh in
+ let H2 := fresh in
+ unshelve edestruct H as [H1 H2]; [ .. | solve [ split; [ eapply H1 | eapply H2 ] ] ];
+ solve [ exact tt | eassumption | reflexivity ]
+ | _ => idtac
+ end;
+ repeat first [ eassumption
+ | eapply mulmod_correct
+ | eapply addmod_correct
+ | eapply submod_correct
+ | eapply oppmod_correct
+ | eapply encodemod_correct
+ | eapply from_montgomery_mod_correct
+ | eapply nonzeromod_correct
+ | intros; apply conj
+ | omega ]. }
+ { cbv zeta; intros f Hf; split.
+ { apply Hto_bytesv; assumption. }
+ { cbn [type.for_each_lhs_of_arrow type_base type.andb_bool_for_each_lhs_of_arrow ZRange.type.option.is_bounded_by fst snd] in *.
+ rewrite Bool.andb_true_iff in *; split_and'.
+ apply to_bytesmod_correct; eauto; [].
+ split; cbv [small].
+ admit.
+ admit. } }
+ { intros.
+ split; [ intro H'; eapply nonzeromod_correct;
+ [ .. | rewrite <- H'; symmetry; eapply Hrnonzerov ]
+ | etransitivity; [ apply Hrnonzerov | eapply nonzeromod_correct; [ .. | eassumption ] ] ];
+ try eassumption.
+ admit.
+ admit. }
+ Admitted.
+ End make_ring.
+
+ Section for_stringification.
+ Definition aggregate_infos {A B C} (ls : list (A * ErrorT B (C * ToString.C.ident_infos))) : ToString.C.ident_infos
+ := fold_right
+ ToString.C.ident_info_union
+ ToString.C.ident_info_empty
+ (List.map
+ (fun '(_, res) => match res with
+ | Success (_, infos) => infos
+ | Error _ => ToString.C.ident_info_empty
+ end)
+ ls).
+
+ Definition extra_synthesis (function_name_prefix : string) (infos : ToString.C.ident_infos)
+ : list (string * Pipeline.ErrorT (list string)) * PositiveSet.t
+ := let ls_addcarryx := List.flat_map
+ (fun lg_split:positive => [sraddcarryx function_name_prefix lg_split; srsubborrowx function_name_prefix lg_split])
+ (PositiveSet.elements (ToString.C.addcarryx_lg_splits infos)) in
+ let ls_mulx := List.map
+ (fun lg_split:positive => srmulx function_name_prefix lg_split)
+ (PositiveSet.elements (ToString.C.mulx_lg_splits infos)) in
+ let ls_cmov := List.map
+ (fun bitwidth:positive => srcmovznz function_name_prefix bitwidth)
+ (PositiveSet.elements (ToString.C.cmovznz_bitwidths infos)) in
+ let ls := ls_addcarryx ++ ls_mulx ++ ls_cmov in
+ let infos := aggregate_infos ls in
+ (List.map (fun '(name, res) => (name, (res <- res; Success (fst res))%error)) ls,
+ ToString.C.bitwidths_used infos).
+
+ Local Open Scope string_scope.
+ Local Open Scope list_scope.
+
+ Definition known_functions
+ := [("mul", srmul);
+ ("square", srsquare);
+ ("add", sradd);
+ ("sub", srsub);
+ ("opp", sropp);
+ ("from_montgomery", srfrom_montgomery);
+ ("nonzero", srnonzero);
+ ("selectznz", srselectznz);
+ ("to_bytes", srto_bytes);
+ ("from_bytes", srfrom_bytes)].
+
+ Definition synthesize_of_name (function_name_prefix : string) (name : string)
+ : string * ErrorT Pipeline.ErrorMessage (list string * ToString.C.ident_infos)
+ := fold_right
+ (fun v default
+ => match v with
+ | Some res => res
+ | None => default
+ end)
+ ((name,
+ Error
+ (Pipeline.Invalid_argument
+ ("Unrecognized request to synthesize """ ++ name ++ """; valid names are " ++ String.concat ", " (List.map (@fst _ _) known_functions)))))
+ (map
+ (fun '(expected_name, resf) => if string_beq name expected_name then Some (resf function_name_prefix) else None)
+ known_functions).
+
+ (** Note: If you change the name or type signature of this
+ function, you will need to update the code in CLI.v *)
+ Definition Synthesize (function_name_prefix : string) (requests : list string)
+ : list (string * Pipeline.ErrorT (list string)) * PositiveSet.t (* types used *)
+ := let ls := match requests with
+ | nil => List.map (fun '(_, sr) => sr function_name_prefix) known_functions
+ | requests => List.map (synthesize_of_name function_name_prefix) requests
+ end in
+ let infos := aggregate_infos ls in
+ let '(extra_ls, extra_bit_widths) := extra_synthesis function_name_prefix infos in
+ (extra_ls ++ List.map (fun '(name, res) => (name, (res <- res; Success (fst res))%error)) ls,
+ PositiveSet.union extra_bit_widths (ToString.C.bitwidths_used infos)).
+ End for_stringification.
+ End rcarry_mul.
+End WordByWordMontgomery.
+
Module SaturatedSolinas.
Section MulMod.
Context (s : Z) (c : list (Z * Z))
generated by cgit v1.2.3 (git 2.39.1) at 2024-06-12 19:08:36 +0000