secp256k1Modinv64Divsteps62Var static method

Implementation

static BigInt secp256k1Modinv64Divsteps62Var(
    BigInt eta, BigInt f0, BigInt g0, Secp256k1ModinvTrans t) {
  /// Transformation matrix; see comments in secp256k1_modinv64_divsteps_62.
  BigInt u = BigInt.one, v = BigInt.zero, q = BigInt.zero, r = BigInt.one;
  BigInt f = f0, g = g0, m;
  int w;
  int i = 62, limit, zeros;

  for (;;) {
    /// Use a sentinel bit to count zeros only up to i.
    zeros = secp256k1CtzVar((g | (maxU64 << i)).toUnsigned64);

    /// Perform zeros divsteps at once; they all just divide g by two.
    g = (g >> zeros).toUnsigned64;
    u = (u << zeros).toUnsigned64;
    v = (v << zeros).toUnsigned64;
    eta = (eta - zeros.toBigInt).toSigned64;
    i = (i - zeros).toSigned32;

    /// We're done once we've done 62 divsteps.
    if (i == 0) break;
    _cond((f & BigInt.one) == BigInt.one, "secp256k1Modinv64Divsteps62Var");
    _cond((g & BigInt.one) == BigInt.one, "secp256k1Modinv64Divsteps62Var");
    _cond((u * f0 + v * g0).toUnsigned64 == (f << (62 - i)).toUnsigned64,
        "secp256k1Modinv64Divsteps62Var");
    _cond((q * f0 + r * g0).toUnsigned64 == (g << (62 - i)).toUnsigned64,
        "secp256k1Modinv64Divsteps62Var");

    /// Bounds on eta that follow from the bounds on iteration count (max 12*62 divsteps).
    _cond(eta >= -745.toBigInt && eta <= 745.toBigInt,
        "secp256k1Modinv64Divsteps62Var");

    /// If eta is negative, negate it and replace f,g with g,-f.
    if (eta.isNegative) {
      BigInt tmp;
      eta = -eta;
      tmp = f;
      f = g;
      g = (-tmp).toUnsigned64;
      tmp = u;
      u = q;
      q = (-tmp).toUnsigned64;
      tmp = v;
      v = r;
      r = (-tmp).toUnsigned64;
      limit = (eta.toSignedInt32 + 1) > i ? i : (eta.toSignedInt32 + 1);
      // VERIFY_CHECK(limit > 0 && limit <= 62);
      /// m is a mask for the bottom min(limit, 6) bits.
      m = ((maxU64 >> (64 - limit)) & 63.toBigInt).toUnsigned64;

      w = ((f * g * (f * f - BigInt.two)) & m).toUnSignedInt32;
    } else {
      limit = (eta.toSignedInt32 + 1) > i ? i : (eta.toSignedInt32 + 1);
      _cond(limit > 0 && limit <= 62, "secp256k1Modinv64Divsteps62Var");

      /// m is a mask for the bottom min(limit, 4) bits.
      m = ((maxU64 >> (64 - limit)) & 15.toBigInt).toUnsigned64;

      w = (f + (((f + BigInt.one) & 4.toBigInt) << 1)).toUnSignedInt32;
      w = (((-w).toBigInt * g) & m).toUnSignedInt32;
    }
    g = (g + (f * w.toBigInt)).toUnsigned64;
    q = (q + (u * w.toBigInt)).toUnsigned64;
    r = (r + (v * w.toBigInt)).toUnsigned64;
    _cond((g & m) == BigInt.zero, "secp256k1Modinv64Divsteps62Var");
  }

  /// Return data in t and return value.
  // t.u = u.toSigned64;
  // t.v = v.toSigned64;
  // t.q = q.toSigned64;
  // t.r = r.toSigned64;
  t.set(u, v, q, r);

  _cond(secp256k1Modinv64DetCheckPow2(t, 62, 0).toBool,
      "secp256k1Modinv64Divsteps62Var");

  return eta;
}