secp256k1Modinv64Posdivsteps62var static method

Implementation

static (BigInt, int) secp256k1Modinv64Posdivsteps62var(
    BigInt eta, BigInt f0, BigInt g0, Secp256k1ModinvTrans t, int jacp) {
  /// 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;
  int jac = jacp;

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

    /// 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 -= zeros;

    jac = (jac ^ (zeros & ((f >> 1) ^ (f >> 2)).toSignedInt32));

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

    /// If eta is negative, negate it and replace f,g with g,f.
    if (eta < BigInt.zero) {
      BigInt tmp;
      eta = -eta;
      tmp = f;
      f = g;
      g = tmp;
      tmp = u;
      u = q;
      q = tmp;
      tmp = v;
      v = r;
      r = tmp;

      jac ^= ((f & g) >> 1).toSignedInt32;

      limit = (eta.toSignedInt32 + 1) > i ? i : (eta.toSignedInt32 + 1);
      _cond(limit > 0 && limit <= 62, "secp256k1Modinv64Posdivsteps62var");

      /// 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, "secp256k1Modinv64Posdivsteps62var");

      /// 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 += f * w.toBigInt;
    q += u * w.toBigInt;
    r += v * w.toBigInt;
    _cond((g & m) == BigInt.zero, "secp256k1Modinv64Posdivsteps62var");
  }

  /// 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, 1).toBool,
      "secp256k1Modinv64Posdivsteps62var");

  return (eta, jac);
}