From d6703ded104fc9085474bfe68b7e897b35cfbe0a Mon Sep 17 00:00:00 2001 From: Jason Gross Date: Fri, 6 Oct 2017 04:26:12 -0400 Subject: Fold Karatsuba into json format and synthesis The json format now takes an additional, optional "goldilocks" boolean / boolean-string key determining if we're doing karatsuba. --- src/Specific/X2448/Karatsuba/C64/CurveParameters.v | 32 ++++++++++++ src/Specific/X2448/Karatsuba/C64/Synthesis.v | 14 +++++ src/Specific/X2448/Karatsuba/C64/femul.v | 12 +++++ src/Specific/X2448/Karatsuba/C64/femulDisplay.log | 61 ++++++++++++++++++++++ src/Specific/X2448/Karatsuba/C64/femulDisplay.v | 4 ++ 5 files changed, 123 insertions(+) create mode 100644 src/Specific/X2448/Karatsuba/C64/CurveParameters.v create mode 100644 src/Specific/X2448/Karatsuba/C64/Synthesis.v create mode 100644 src/Specific/X2448/Karatsuba/C64/femul.v create mode 100644 src/Specific/X2448/Karatsuba/C64/femulDisplay.log create mode 100644 src/Specific/X2448/Karatsuba/C64/femulDisplay.v (limited to 'src/Specific/X2448') diff --git a/src/Specific/X2448/Karatsuba/C64/CurveParameters.v b/src/Specific/X2448/Karatsuba/C64/CurveParameters.v new file mode 100644 index 000000000..aa8fd5614 --- /dev/null +++ b/src/Specific/X2448/Karatsuba/C64/CurveParameters.v @@ -0,0 +1,32 @@ +Require Import Crypto.Specific.Framework.CurveParameters. +Require Import Crypto.Util.LetIn. + +(*** +Modulus : 2^448-2^224-1 +Base: 56 +***) + +Module Curve <: CurveParameters. + Definition sz : nat := 8%nat. + Definition bitwidth : Z := 64. + Definition s : Z := 2^448. + Definition c : list limb := [(1, 1); (2^224, 1)]. + Definition carry_chains : option (list (list nat)) := Eval vm_compute in Some [[3; 7]; [0; 4; 1; 5; 2; 6; 3; 7]; [4; 0]]%nat. + + Definition a24 : option Z := None. + Definition coef_div_modulus : nat := 2%nat. (* add 2*modulus before subtracting *) + + Definition goldilocks : bool := true. + + Definition mul_code : option (Z^sz -> Z^sz -> Z^sz) + := None. + + Definition square_code : option (Z^sz -> Z^sz) + := None. + + Definition upper_bound_of_exponent : option (Z -> Z) := None. + Definition allowable_bit_widths : option (list nat) := None. + Definition freeze_extra_allowable_bit_widths : option (list nat) := None. + Ltac extra_prove_mul_eq := idtac. + Ltac extra_prove_square_eq := idtac. +End Curve. diff --git a/src/Specific/X2448/Karatsuba/C64/Synthesis.v b/src/Specific/X2448/Karatsuba/C64/Synthesis.v new file mode 100644 index 000000000..8ea8aa5c9 --- /dev/null +++ b/src/Specific/X2448/Karatsuba/C64/Synthesis.v @@ -0,0 +1,14 @@ +Require Import Crypto.Specific.Framework.SynthesisFramework. +Require Import Crypto.Specific.X2448.Karatsuba.C64.CurveParameters. + +Module Import T := MakeSynthesisTactics Curve. + +Module P <: SynthesisPrePackage. + Definition Synthesis_package' : Synthesis_package'_Type. + Proof. make_synthesis_package (). Defined. + + Definition Synthesis_package + := Eval cbv [Synthesis_package' projT2] in projT2 Synthesis_package'. +End P. + +Module Export S := PackageSynthesis Curve P. diff --git a/src/Specific/X2448/Karatsuba/C64/femul.v b/src/Specific/X2448/Karatsuba/C64/femul.v new file mode 100644 index 000000000..2f890a88f --- /dev/null +++ b/src/Specific/X2448/Karatsuba/C64/femul.v @@ -0,0 +1,12 @@ +Require Import Crypto.Arithmetic.PrimeFieldTheorems. +Require Import Crypto.Specific.X2448.Karatsuba.C64.Synthesis. + +(* TODO : change this to field once field isomorphism happens *) +Definition mul : + { mul : feBW -> feBW -> feBW + | forall a b, phiBW (mul a b) = F.mul (phiBW a) (phiBW b) }. +Proof. + Set Ltac Profiling. + Time synthesize_mul (). + Show Ltac Profile. +Time Defined. diff --git a/src/Specific/X2448/Karatsuba/C64/femulDisplay.log b/src/Specific/X2448/Karatsuba/C64/femulDisplay.log new file mode 100644 index 000000000..17db6102d --- /dev/null +++ b/src/Specific/X2448/Karatsuba/C64/femulDisplay.log @@ -0,0 +1,61 @@ +λ x x0 : word64 * word64 * word64 * word64 * word64 * word64 * word64 * word64, +Interp-η +(λ var : Syntax.base_type → Type, + λ '(x16, x17, x15, x13, x11, x9, x7, x5, (x30, x31, x29, x27, x25, x23, x21, x19))%core, + uint128_t x32 = (uint128_t) (x11 + x16) * (x25 + x30) - (uint128_t) x11 * x25; + uint128_t x33 = (uint128_t) (x9 + x17) * (x25 + x30) + (uint128_t) (x11 + x16) * (x23 + x31) - ((uint128_t) x9 * x25 + (uint128_t) x11 * x23); + uint128_t x34 = (uint128_t) (x7 + x15) * (x25 + x30) + ((uint128_t) (x9 + x17) * (x23 + x31) + (uint128_t) (x11 + x16) * (x21 + x29)) - ((uint128_t) x7 * x25 + ((uint128_t) x9 * x23 + (uint128_t) x11 * x21)); + uint128_t x35 = (uint128_t) (x5 + x13) * (x25 + x30) + ((uint128_t) (x7 + x15) * (x23 + x31) + ((uint128_t) (x9 + x17) * (x21 + x29) + (uint128_t) (x11 + x16) * (x19 + x27))) - ((uint128_t) x5 * x25 + ((uint128_t) x7 * x23 + ((uint128_t) x9 * x21 + (uint128_t) x11 * x19))); + uint128_t x36 = (uint128_t) (x5 + x13) * (x23 + x31) + ((uint128_t) (x7 + x15) * (x21 + x29) + (uint128_t) (x9 + x17) * (x19 + x27)) - ((uint128_t) x5 * x23 + ((uint128_t) x7 * x21 + (uint128_t) x9 * x19)); + uint128_t x37 = (uint128_t) (x5 + x13) * (x21 + x29) + (uint128_t) (x7 + x15) * (x19 + x27) - ((uint128_t) x5 * x21 + (uint128_t) x7 * x19); + uint128_t x38 = (uint128_t) (x5 + x13) * (x19 + x27) - (uint128_t) x5 * x19; + uint128_t x39 = (uint128_t) x11 * x25 + (uint128_t) x16 * x30 + x36 + x32; + uint128_t x40 = (uint128_t) x9 * x25 + (uint128_t) x11 * x23 + ((uint128_t) x17 * x30 + (uint128_t) x16 * x31) + x37 + x33; + uint128_t x41 = (uint128_t) x7 * x25 + ((uint128_t) x9 * x23 + (uint128_t) x11 * x21) + ((uint128_t) x15 * x30 + ((uint128_t) x17 * x31 + (uint128_t) x16 * x29)) + x38 + x34; + uint128_t x42 = (uint128_t) x5 * x25 + ((uint128_t) x7 * x23 + ((uint128_t) x9 * x21 + (uint128_t) x11 * x19)) + ((uint128_t) x13 * x30 + ((uint128_t) x15 * x31 + ((uint128_t) x17 * x29 + (uint128_t) x16 * x27))); + uint128_t x43 = (uint128_t) x5 * x23 + ((uint128_t) x7 * x21 + (uint128_t) x9 * x19) + ((uint128_t) x13 * x31 + ((uint128_t) x15 * x29 + (uint128_t) x17 * x27)) + x32; + uint128_t x44 = (uint128_t) x5 * x21 + (uint128_t) x7 * x19 + ((uint128_t) x13 * x29 + (uint128_t) x15 * x27) + x33; + uint128_t x45 = (uint128_t) x5 * x19 + (uint128_t) x13 * x27 + x34; + uint64_t x46 = (uint64_t) (x42 >> 0x38); + uint64_t x47 = (uint64_t) x42 & 0xffffffffffffff; + uint64_t x48 = (uint64_t) (x35 >> 0x38); + uint64_t x49 = (uint64_t) x35 & 0xffffffffffffff; + uint128_t x50 = (uint128_t) 0x100000000000000 * x48 + x49; + uint64_t x51 = (uint64_t) (x50 >> 0x38); + uint64_t x52 = (uint64_t) x50 & 0xffffffffffffff; + uint128_t x53 = x45 + x51; + uint64_t x54 = (uint64_t) (x53 >> 0x38); + uint64_t x55 = (uint64_t) x53 & 0xffffffffffffff; + uint128_t x56 = x46 + x41 + x51; + uint64_t x57 = (uint64_t) (x56 >> 0x38); + uint64_t x58 = (uint64_t) x56 & 0xffffffffffffff; + uint128_t x59 = x54 + x44; + uint64_t x60 = (uint64_t) (x59 >> 0x38); + uint64_t x61 = (uint64_t) x59 & 0xffffffffffffff; + uint128_t x62 = x57 + x40; + uint64_t x63 = (uint64_t) (x62 >> 0x38); + uint64_t x64 = (uint64_t) x62 & 0xffffffffffffff; + uint128_t x65 = x60 + x43; + uint64_t x66 = (uint64_t) (x65 >> 0x38); + uint64_t x67 = (uint64_t) x65 & 0xffffffffffffff; + uint128_t x68 = x63 + x39; + uint64_t x69 = (uint64_t) (x68 >> 0x38); + uint64_t x70 = (uint64_t) x68 & 0xffffffffffffff; + uint64_t x71 = x66 + x47; + uint64_t x72 = x71 >> 0x38; + uint64_t x73 = x71 & 0xffffffffffffff; + uint64_t x74 = x69 + x52; + uint64_t x75 = x74 >> 0x38; + uint64_t x76 = x74 & 0xffffffffffffff; + uint64_t x77 = 0x100000000000000 * x75 + x76; + uint64_t x78 = x77 >> 0x38; + uint64_t x79 = x77 & 0xffffffffffffff; + uint64_t x80 = x72 + x58 + x78; + uint64_t x81 = x80 >> 0x38; + uint64_t x82 = x80 & 0xffffffffffffff; + uint64_t x83 = x55 + x78; + uint64_t x84 = x83 >> 0x38; + uint64_t x85 = x83 & 0xffffffffffffff; + return (Return x79, Return x70, x81 + x64, Return x82, Return x73, Return x67, x84 + x61, Return x85)) +(x, x0)%core + : word64 * word64 * word64 * word64 * word64 * word64 * word64 * word64 → word64 * word64 * word64 * word64 * word64 * word64 * word64 * word64 → ReturnType (uint64_t * uint64_t * uint64_t * uint64_t * uint64_t * uint64_t * uint64_t * uint64_t) diff --git a/src/Specific/X2448/Karatsuba/C64/femulDisplay.v b/src/Specific/X2448/Karatsuba/C64/femulDisplay.v new file mode 100644 index 000000000..15877076f --- /dev/null +++ b/src/Specific/X2448/Karatsuba/C64/femulDisplay.v @@ -0,0 +1,4 @@ +Require Import Crypto.Specific.X2448.Karatsuba.C64.femul. +Require Import Crypto.Specific.Framework.IntegrationTestDisplayCommon. + +Check display mul. -- cgit v1.2.3