1  # Constantine
  2  # Copyright (c) 2018-2019    Status Research & Development GmbH
  3  # Copyright (c) 2020-Present Mamy André-Ratsimbazafy
  4  # Licensed and distributed under either of
  5  #   * MIT license (license terms in the root directory or at http://opensource.org/licenses/MIT).
  6  #   * Apache v2 license (license terms in the root directory or at http://www.apache.org/licenses/LICENSE-2.0).
  7  # at your option. This file may not be copied, modified, or distributed except according to those terms.
  8  
  9  # ############################################################
 10  #
 11  #             Benchmark of finite fields
 12  #
 13  # ############################################################
 14  
 15  import
 16    # Internals
 17    ../constantine/platforms/abstractions,
 18    ../constantine/math/config/curves,
 19    ../constantine/math/arithmetic,
 20    ../constantine/math/extension_fields,
 21    ../constantine/math/constants/zoo_square_roots,
 22    # Helpers
 23    ../helpers/prng_unsafe,
 24    ./bench_blueprint
 25  
 26  export notes, abstractions
 27  proc separator*() = separator(165)
 28  proc smallSeparator*() = separator(8)
 29  
 30  proc report(op, field: string, start, stop: MonoTime, startClk, stopClk: int64, iters: int) =
 31    let ns = inNanoseconds((stop-start) div iters)
 32    let throughput = 1e9 / float64(ns)
 33    when SupportsGetTicks:
 34      echo &"{op:<70} {field:<18} {throughput:>15.3f} ops/s     {ns:>9} ns/op     {(stopClk - startClk) div iters:>9} CPU cycles (approx)"
 35    else:
 36      echo &"{op:<70} {field:<18} {throughput:>15.3f} ops/s     {ns:>9} ns/op"
 37  
 38  macro fixFieldDisplay(T: typedesc): untyped =
 39    # At compile-time, enums are integers and their display is buggy
 40    # we get the Curve ID instead of the curve name.
 41    let instantiated = T.getTypeInst()
 42    var name = $instantiated[1][0] # 𝔽p
 43    name.add "[" & $Curve(instantiated[1][1].intVal) & "]"
 44    result = newLit name
 45  
 46  template bench(op: string, T: typedesc, iters: int, body: untyped): untyped =
 47    measure(iters, startTime, stopTime, startClk, stopClk, body)
 48    report(op, fixFieldDisplay(T), startTime, stopTime, startClk, stopClk, iters)
 49  
 50  func random_unsafe(rng: var RngState, a: var FpDbl) =
 51    ## Initialize a standalone Double-Width field element
 52    ## we don't reduce it modulo p², this is only used for benchmark
 53    let aHi = rng.random_unsafe(Fp[FpDbl.C])
 54    let aLo = rng.random_unsafe(Fp[FpDbl.C])
 55    for i in 0 ..< aLo.mres.limbs.len:
 56      a.limbs2x[i] = aLo.mres.limbs[i]
 57    for i in 0 ..< aHi.mres.limbs.len:
 58      a.limbs2x[aLo.mres.limbs.len+i] = aHi.mres.limbs[i]
 59  
 60  func random_unsafe(rng: var RngState, a: var ExtensionField2x) =
 61    for i in 0 ..< a.coords.len:
 62      rng.random_unsafe(a.coords[i])
 63  
 64  proc addBench*(T: typedesc, iters: int) =
 65    var x = rng.random_unsafe(T)
 66    let y = rng.random_unsafe(T)
 67    bench("Addition", T, iters):
 68      x += y
 69  
 70  proc subBench*(T: typedesc, iters: int) =
 71    var x = rng.random_unsafe(T)
 72    let y = rng.random_unsafe(T)
 73    preventOptimAway(x)
 74    bench("Substraction", T, iters):
 75      x -= y
 76  
 77  proc negBench*(T: typedesc, iters: int) =
 78    var r: T
 79    let x = rng.random_unsafe(T)
 80    bench("Negation", T, iters):
 81      r.neg(x)
 82  
 83  proc ccopyBench*(T: typedesc, iters: int) =
 84    var r: T
 85    let x = rng.random_unsafe(T)
 86    bench("Conditional Copy", T, iters):
 87      r.ccopy(x, CtFalse)
 88  
 89  proc div2Bench*(T: typedesc, iters: int) =
 90    var x = rng.random_unsafe(T)
 91    bench("Division by 2", T, iters):
 92      x.div2()
 93  
 94  proc mulBench*(T: typedesc, iters: int) =
 95    var r: T
 96    let x = rng.random_unsafe(T)
 97    let y = rng.random_unsafe(T)
 98    preventOptimAway(r)
 99    bench("Multiplication", T, iters):
100      r.prod(x, y)
101  
102  proc sqrBench*(T: typedesc, iters: int) =
103    var r: T
104    let x = rng.random_unsafe(T)
105    preventOptimAway(r)
106    bench("Squaring", T, iters):
107      r.square(x)
108  
109  proc mul2xUnrBench*(T: typedesc, iters: int) =
110    var r: doublePrec(T)
111    let x = rng.random_unsafe(T)
112    let y = rng.random_unsafe(T)
113    preventOptimAway(r)
114    bench("Multiplication 2x unreduced", T, iters):
115      r.prod2x(x, y)
116  
117  proc sqr2xUnrBench*(T: typedesc, iters: int) =
118    var r: doublePrec(T)
119    let x = rng.random_unsafe(T)
120    preventOptimAway(r)
121    bench("Squaring 2x unreduced", T, iters):
122      r.square2x(x)
123  
124  proc rdc2xBench*(T: typedesc, iters: int) =
125    var r: T
126    var t: doublePrec(T)
127    rng.random_unsafe(t)
128    preventOptimAway(r)
129    bench("Redc 2x", T, iters):
130      r.redc2x(t)
131  
132  proc sumprodBench*(T: typedesc, iters: int) =
133    var r: T
134    let a = rng.random_unsafe(T)
135    let b = rng.random_unsafe(T)
136    let u = rng.random_unsafe(T)
137    let v = rng.random_unsafe(T)
138    preventOptimAway(r)
139    bench("Linear combination", T, iters):
140      r.sumprod([a, b], [u, v])
141  
142  proc toBigBench*(T: typedesc, iters: int) =
143    var r: matchingBigInt(T.C)
144    let x = rng.random_unsafe(T)
145    preventOptimAway(r)
146    bench("BigInt <- field conversion", T, iters):
147      r.fromField(x)
148  
149  proc toFieldBench*(T: typedesc, iters: int) =
150    var r: T
151    let x = rng.random_unsafe(matchingBigInt(T.C))
152    preventOptimAway(r)
153    bench("BigInt -> field conversion", T, iters):
154      r.fromBig(x)
155  
156  proc invBench*(T: typedesc, iters: int) =
157    var r: T
158    let x = rng.random_unsafe(T)
159    preventOptimAway(r)
160    bench("Inversion (constant-time)", T, iters):
161      r.inv(x)
162  
163  proc invVartimeBench*(T: typedesc, iters: int) =
164    var r: T
165    let x = rng.random_unsafe(T)
166    preventOptimAway(r)
167    bench("Inversion (variable-time)", T, iters):
168      r.inv_vartime(x)
169  
170  proc isSquareBench*(T: typedesc, iters: int) =
171    let x = rng.random_unsafe(T)
172    bench("isSquare (constant-time)", T, iters):
173      let qrt = x.isSquare()
174  
175  proc sqrtBench*(T: typedesc, iters: int) =
176    let x = rng.random_unsafe(T)
177  
178    const algoType = block:
179      when T.C.has_P_3mod4_primeModulus():
180        "p ≡ 3 (mod 4)"
181      elif T.C.has_P_5mod8_primeModulus():
182        "p ≡ 5 (mod 8)"
183      else:
184        "Tonelli-Shanks"
185    const addchain = block:
186      when T.C.hasSqrtAddchain() or T.C.hasTonelliShanksAddchain():
187        "with addition chain"
188      else:
189        "without addition chain"
190    const desc = "Square Root (constant-time " & algoType & " " & addchain & ")"
191    bench(desc, T, iters):
192      var r = x
193      discard r.sqrt_if_square()
194  
195  proc sqrtRatioBench*(T: typedesc, iters: int) =
196    var r: T
197    let u = rng.random_unsafe(T)
198    let v = rng.random_unsafe(T)
199    bench("Fused SquareRoot+Division+isSquare sqrt(u/v)", T, iters):
200      let isSquare = r.sqrt_ratio_if_square(u, v)
201  
202  proc powBench*(T: typedesc, iters: int) =
203    let x = rng.random_unsafe(T)
204    let exponent = rng.random_unsafe(BigInt[T.C.getCurveOrderBitwidth()])
205    bench("Exp curve order (constant-time) - " & $exponent.bits & "-bit", T, iters):
206      var r = x
207      r.pow(exponent)
208  
209  proc powUnsafeBench*(T: typedesc, iters: int) =
210    let x = rng.random_unsafe(T)
211    let exponent = rng.random_unsafe(BigInt[T.C.getCurveOrderBitwidth()])
212    bench("Exp curve order (Leak exponent bits) - " & $exponent.bits & "-bit", T, iters):
213      var r = x
214      r.pow_vartime(exponent)