secp256k1FeNormalize static method

Implementation

static void secp256k1FeNormalize(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).toUnsigned64;
  t4 = (t4 & Secp256k1Const.mask48).toUnsigned64;

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

  /// 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)
      .toUnsigned64;

  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;

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

  /// 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;
}