secp256k1FeNormalizeVar static method

Implementation

static void secp256k1FeNormalizeVar(Secp256k1Fe r) {
  BigInt t0 = r[0], t1 = r[1], t2 = r[2], t3 = r[3], t4 = r[4];

  /// Reduce t4 at the start so there will be at most a single carry from the first pass
  BigInt m;
  BigInt x = t4 >> 48;
  t4 = t4 & Secp256k1Const.mask48;

  /// The first pass ensures the magnitude is 1, ...
  t0 = (t0 + x * Secp256k1Const.mask33).toUnsigned64;
  t1 = (t1 + (t0 >> 52)).toUnsigned64;
  t0 = (t0 & Secp256k1Const.mask52).toUnsigned64;
  t2 = (t2 + (t1 >> 52)).toUnsigned64;
  t1 = (t1 & Secp256k1Const.mask52).toUnsigned64;
  m = t1;
  t3 = (t3 + (t2 >> 52)).toUnsigned64;
  t2 = (t2 & Secp256k1Const.mask52).toUnsigned64;
  m = (m & t2).toUnsigned64;
  t4 = (t4 + (t3 >> 52)).toUnsigned64;
  t3 = (t3 & Secp256k1Const.mask52).toUnsigned64;
  m = (m & t3).toUnsigned64;

  /// ... except for a possible carry at bit 48 of t4 (i.e. bit 256 of the field element)
  _cond(t4 >> 49 == BigInt.zero, "secp256k1FeNormalizeVar");

  /// At most a single final reduction is needed; check if the value is >= the field characteristic
  x = (t4 >> 48) |
      ((t4 == Secp256k1Const.mask48) &
              (m == Secp256k1Const.mask52) &
              (t0 >= Secp256k1Const.mask47))
          .toBigInt;

  if (x.toBool) {
    t0 = (t0 + Secp256k1Const.mask33).toUnsigned64;
    t1 = (t1 + (t0 >> 52)).toUnsigned64;
    t0 = (t0 & Secp256k1Const.mask52).toUnsigned64;
    t2 = (t2 + (t1 >> 52)).toUnsigned64;
    t1 = (t1 & Secp256k1Const.mask52).toUnsigned64;
    t3 = (t3 + (t2 >> 52)).toUnsigned64;
    t2 = (t2 & Secp256k1Const.mask52).toUnsigned64;
    t4 = (t4 + (t3 >> 52)).toUnsigned64;
    t3 = (t3 & Secp256k1Const.mask52).toUnsigned64;

    /// If t4 didn't carry to bit 48 already, then it should have after any final reduction
    _cond(t4 >> 48 == x, "secp256k1FeNormalizeVar");

    /// Mask off the possible multiple of 2^256 from the final reduction
    t4 = (t4 & Secp256k1Const.mask48).toUnsigned64;
  }

  r[0] = t0;
  r[1] = t1;
  r[2] = t2;
  r[3] = t3;
  r[4] = t4;
}