src/crypto/p224.cc
// Contract converts a FieldElement to its minimal, distinguished form.
//
// On entry, in[i] < 2**29
// On exit, in[i] < 2**28
Contract converts a FieldElement to its minimal, distinguished form.
Contract converts a FieldElement to its minimal distinguished form .
void Contract(FieldElement* inout) {
  FieldElement& out = *inout;
  for (int i = 0; i < 7; i++) {
    out[i+1] += out[i] >> 28;
    out[i] &= kBottom28Bits;
  }
  uint32_t top = out[7] >> 28;
  out[7] &= kBottom28Bits;
  out[0] -= top;
  out[3] += top << 12;
  for (int i = 0; i < 3; i++) {
    uint32_t mask = static_cast<uint32_t>(static_cast<int32_t>(out[i]) >> 31);
    out[i] += (1 << 28) & mask;
    out[i+1] -= 1 & mask;
  }
  for (int i = 3; i < 7; i++) {
    out[i+1] += out[i] >> 28;
    out[i] &= kBottom28Bits;
  }
  top = out[7] >> 28;
  out[7] &= kBottom28Bits;
  out[0] -= top;
  out[3] += top << 12;
  for (int i = 0; i < 3; i++) {
    uint32_t mask = static_cast<uint32_t>(static_cast<int32_t>(out[i]) >> 31);
    out[i] += (1 << 28) & mask;
    out[i+1] -= 1 & mask;
  }
  uint32_t top_4_all_ones = 0xffffffffu;
  for (int i = 4; i < 8; i++) {
    top_4_all_ones &= out[i];
  }
  top_4_all_ones |= 0xf0000000;
  top_4_all_ones &= top_4_all_ones >> 16;
  top_4_all_ones &= top_4_all_ones >> 8;
  top_4_all_ones &= top_4_all_ones >> 4;
  top_4_all_ones &= top_4_all_ones >> 2;
  top_4_all_ones &= top_4_all_ones >> 1;
  top_4_all_ones =
      static_cast<uint32_t>(static_cast<int32_t>(top_4_all_ones << 31) >> 31);
  uint32_t bottom_3_non_zero = out[0] | out[1] | out[2];
  bottom_3_non_zero |= bottom_3_non_zero >> 16;
  bottom_3_non_zero |= bottom_3_non_zero >> 8;
  bottom_3_non_zero |= bottom_3_non_zero >> 4;
  bottom_3_non_zero |= bottom_3_non_zero >> 2;
  bottom_3_non_zero |= bottom_3_non_zero >> 1;
  bottom_3_non_zero =
      static_cast<uint32_t>(static_cast<int32_t>(bottom_3_non_zero) >> 31);
  uint32_t n = out[3] - 0xffff000;
  uint32_t out_3_equal = n;
  out_3_equal |= out_3_equal >> 16;
  out_3_equal |= out_3_equal >> 8;
  out_3_equal |= out_3_equal >> 4;
  out_3_equal |= out_3_equal >> 2;
  out_3_equal |= out_3_equal >> 1;
  out_3_equal =
      ~static_cast<uint32_t>(static_cast<int32_t>(out_3_equal << 31) >> 31);
  uint32_t out_3_gt =
      ~static_cast<uint32_t>(static_cast<int32_t>(n << 31) >> 31);
  uint32_t mask =
      top_4_all_ones & ((out_3_equal & bottom_3_non_zero) | out_3_gt);
  out[0] -= 1 & mask;
  out[3] -= 0xffff000 & mask;
  out[4] -= 0xfffffff & mask;
  out[5] -= 0xfffffff & mask;
  out[6] -= 0xfffffff & mask;
  out[7] -= 0xfffffff & mask;
}
void Contract ( FieldElement * inout ) { FieldElement & out = * inout ; for ( int i = 0 ; i < 7 ; i ++ ) { out [ i + 1 ] += out [ i ] >> 28 ; out [ i ] &= kBottom28Bits ; } uint32_t top = out [ 7 ] >> 28 ; out [ 7 ] &= kBottom28Bits ; out [ 0 ] -= top ; out [ 3 ] += top << 12 ; for ( int i = 0 ; i < 3 ; i ++ ) { uint32_t mask = static_cast < uint32_t > ( static_cast < int32_t > ( out [ i ] ) >> 31 ) ; out [ i ] += ( 1 << 28 ) & mask ; out [ i + 1 ] -= 1 & mask ; } for ( int i = 3 ; i < 7 ; i ++ ) { out [ i + 1 ] += out [ i ] >> 28 ; out [ i ] &= kBottom28Bits ; } top = out [ 7 ] >> 28 ; out [ 7 ] &= kBottom28Bits ; out [ 0 ] -= top ; out [ 3 ] += top << 12 ; for ( int i = 0 ; i < 3 ; i ++ ) { uint32_t mask = static_cast < uint32_t > ( static_cast < int32_t > ( out [ i ] ) >> 31 ) ; out [ i ] += ( 1 << 28 ) & mask ; out [ i + 1 ] -= 1 & mask ; } uint32_t top_4_all_ones = 0xffffffffu ; for ( int i = 4 ; i < 8 ; i ++ ) { top_4_all_ones &= out [ i ] ; } top_4_all_ones |= 0xf0000000 ; top_4_all_ones &= top_4_all_ones >> 16 ; top_4_all_ones &= top_4_all_ones >> 8 ; top_4_all_ones &= top_4_all_ones >> 4 ; top_4_all_ones &= top_4_all_ones >> 2 ; top_4_all_ones &= top_4_all_ones >> 1 ; top_4_all_ones = static_cast < uint32_t > ( static_cast < int32_t > ( top_4_all_ones << 31 ) >> 31 ) ; uint32_t bottom_3_non_zero = out [ 0 ] | out [ 1 ] | out [ 2 ] ; bottom_3_non_zero |= bottom_3_non_zero >> 16 ; bottom_3_non_zero |= bottom_3_non_zero >> 8 ; bottom_3_non_zero |= bottom_3_non_zero >> 4 ; bottom_3_non_zero |= bottom_3_non_zero >> 2 ; bottom_3_non_zero |= bottom_3_non_zero >> 1 ; bottom_3_non_zero = static_cast < uint32_t > ( static_cast < int32_t > ( bottom_3_non_zero ) >> 31 ) ; uint32_t n = out [ 3 ] - 0xffff000 ; uint32_t out_3_equal = n ; out_3_equal |= out_3_equal >> 16 ; out_3_equal |= out_3_equal >> 8 ; out_3_equal |= out_3_equal >> 4 ; out_3_equal |= out_3_equal >> 2 ; out_3_equal |= out_3_equal >> 1 ; out_3_equal = ~ static_cast < uint32_t > ( static_cast < int32_t > ( out_3_equal << 31 ) >> 31 ) ; uint32_t out_3_gt = ~ static_cast < uint32_t > ( static_cast < int32_t > ( n << 31 ) >> 31 ) ; uint32_t mask = top_4_all_ones & ( ( out_3_equal & bottom_3_non_zero ) | out_3_gt ) ; out [ 0 ] -= 1 & mask ; out [ 3 ] -= 0xffff000 & mask ; out [ 4 ] -= 0xfffffff & mask ; out [ 5 ] -= 0xfffffff & mask ; out [ 6 ] -= 0xfffffff & mask ; out [ 7 ] -= 0xfffffff & mask ; }
Contract converts a FieldElement to its minimal, distinguished form.
Contract converts a FieldElement to its minimal distinguished form .
// Reduce the coefficients to < 2**28. // Eliminate top while maintaining the same value mod p. // We may just have made out[0] negative. So we carry down. If we made // out[0] negative then we know that out[3] is sufficiently positive // because we just added to it. // We might have pushed out[3] over 2**28 so we perform another, partial // carry chain. // Eliminate top while maintaining the same value mod p. // There are two cases to consider for out[3]: //   1) The first time that we eliminated top, we didn't push out[3] over //      2**28. In this case, the partial carry chain didn't change any values //      and top is zero. //   2) We did push out[3] over 2**28 the first time that we eliminated top. //      The first value of top was in [0..16), therefore, prior to eliminating //      the first top, 0xfff1000 <= out[3] <= 0xfffffff. Therefore, after //      overflowing and being reduced by the second carry chain, out[3] <= //      0xf000. Thus it cannot have overflowed when we eliminated top for the //      second time. // Again, we may just have made out[0] negative, so do the same carry down. // As before, if we made out[0] negative then we know that out[3] is // sufficiently positive. // The value is < 2**224, but maybe greater than p. In order to reduce to a // unique, minimal value we see if the value is >= p and, if so, subtract p. // First we build a mask from the top four limbs, which must all be // equal to bottom28Bits if the whole value is >= p. If top_4_all_ones // ends up with any zero bits in the bottom 28 bits, then this wasn't // true. // Now we replicate any zero bits to all the bits in top_4_all_ones. // Now we test whether the bottom three limbs are non-zero. // Everything depends on the value of out[3]. //    If it's > 0xffff000 and top_4_all_ones != 0 then the whole value is >= p //    If it's = 0xffff000 and top_4_all_ones != 0 and bottom_3_non_zero != 0, //      then the whole value is >= p //    If it's < 0xffff000, then the whole value is < p // If out[3] > 0xffff000 then n's MSB will be zero.