Update NSS to 3.21 RTM and NSPR to 4.11 RTM

nss/lib/freebl/mpi/mpi.c

 /*
  *  mpi.c
  *
  *  Arbitrary precision integer arithmetic library
  *
  * This Source Code Form is subject to the terms of the Mozilla Public
  * License, v. 2.0. If a copy of the MPL was not distributed with this
  * file, You can obtain one at http://mozilla.org/MPL/2.0/. */
 
 #include "mpi-priv.h"
@@ skipping 1077 matching lines @@
 
   Compute c = a ** b, that is, raise a to the b power.  Uses a
   standard iterative square-and-multiply technique.
  */
 
 mp_err mp_expt(mp_int *a, mp_int *b, mp_int *c)
 {
   mp_int   s, x;
   mp_err   res;
   mp_digit d;
-  int      dig, bit;
+  unsigned int      dig, bit;
 
   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
 
   if(mp_cmp_z(b) < 0)
     return MP_RANGE;
 
   if((res = mp_init(&s)) != MP_OKAY)
     return res;
 
   mp_set(&s, 1);
@@ skipping 354 matching lines @@
   
   The modular reductions are done using Barrett's algorithm (see
   s_mp_reduce() below for details)
  */
 
 mp_err s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c)
 {
   mp_int   s, x, mu;
   mp_err   res;
   mp_digit d;
-  int      dig, bit;
+  unsigned int      dig, bit;
 
   ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG);
 
   if(mp_cmp_z(b) < 0 || mp_cmp_z(m) <= 0)
     return MP_RANGE;
 
   if((res = mp_init(&s)) != MP_OKAY)
     return res;
   if((res = mp_init_copy(&x, a)) != MP_OKAY ||
      (res = mp_mod(&x, m, &x)) != MP_OKAY)
@@ skipping 513 matching lines @@
   return res;
 
 } /* end mp_xgcd() */
 
 /* }}} */
 
 mp_size mp_trailing_zeros(const mp_int *mp)
 {
   mp_digit d;
   mp_size  n = 0;
-  int      ix;
+  unsigned int      ix;
 
   if (!mp || !MP_DIGITS(mp) || !mp_cmp_z(mp))
     return n;
 
   for (ix = 0; !(d = MP_DIGIT(mp,ix)) && (ix < MP_USED(mp)); ++ix)
     n += MP_DIGIT_BIT;
   if (!d)
     return 0;   /* shouldn't happen, but ... */
 #if !defined(MP_USE_UINT_DIGIT)
   if (!(d & 0xffffffffU)) {
@@ skipping 891 matching lines @@
 
 /* 
    Shift mp leftward by p digits, growing if needed, and zero-filling
    the in-shifted digits at the right end.  This is a convenient
    alternative to multiplication by powers of the radix
  */   
 
 mp_err   s_mp_lshd(mp_int *mp, mp_size p)
 {
   mp_err  res;
-  mp_size pos;
-  int     ix;
+  unsigned int     ix;
 
   if(p == 0)
     return MP_OKAY;
 
   if (MP_USED(mp) == 1 && MP_DIGIT(mp, 0) == 0)
     return MP_OKAY;
 
   if((res = s_mp_pad(mp, USED(mp) + p)) != MP_OKAY)
     return res;
 
-  pos = USED(mp) - 1;
-
   /* Shift all the significant figures over as needed */
-  for(ix = pos - p; ix >= 0; ix--) 
+  for (ix = USED(mp) - p; ix-- > 0;) {
     DIGIT(mp, ix + p) = DIGIT(mp, ix);
+  }
 
   /* Fill the bottom digits with zeroes */
-  for(ix = 0; ix < p; ix++)
+  for(ix = 0; (mp_size)ix < p; ix++)
     DIGIT(mp, ix) = 0;
 
   return MP_OKAY;
 
 } /* end s_mp_lshd() */
 
 /* }}} */
 
 /* {{{ s_mp_mul_2d(mp, d) */
 
@@ skipping 90 matching lines @@
 
 } /* end s_mp_div_2() */
 
 /* }}} */
 
 /* {{{ s_mp_mul_2(mp) */
 
 mp_err s_mp_mul_2(mp_int *mp)
 {
   mp_digit *pd;
-  int      ix, used;
+  unsigned int ix, used;
   mp_digit kin = 0;
 
   /* Shift digits leftward by 1 bit */
   used = MP_USED(mp);
   pd = MP_DIGITS(mp);
   for (ix = 0; ix < used; ix++) {
     mp_digit d = *pd;
     *pd++ = (d << 1) | kin;
     kin = (d >> (DIGIT_BIT - 1));
   }
@@ skipping 1125 matching lines @@
   if((ix = s_mp_ispow2(div)) >= 0) {
     MP_CHECKOK( mp_copy(rem, quot) );
     s_mp_div_2d(quot, (mp_digit)ix);
     s_mp_mod_2d(rem,  (mp_digit)ix);
 
     return MP_OKAY;
   }
 
   MP_SIGN(rem) = ZPOS;
   MP_SIGN(div) = ZPOS;
+  MP_SIGN(&part) = ZPOS;
 
   /* A working temporary for division     */
   MP_CHECKOK( mp_init_size(&t, MP_ALLOC(rem)));
 
   /* Normalize to optimize guessing       */
   MP_CHECKOK( s_mp_norm(rem, div, &d) );
 
-  part = *rem;
-
   /* Perform the division itself...woo!   */
   MP_USED(quot) = MP_ALLOC(quot);
 
   /* Find a partial substring of rem which is at least div */
   /* If we didn't find one, we're finished dividing    */
   while (MP_USED(rem) > MP_USED(div) || s_mp_cmp(rem, div) >= 0) {
     int i;
     int unusedRem;
+    int partExtended = 0;  /* set to true if we need to extend part */
 
     unusedRem = MP_USED(rem) - MP_USED(div);
     MP_DIGITS(&part) = MP_DIGITS(rem) + unusedRem;
     MP_ALLOC(&part)  = MP_ALLOC(rem)  - unusedRem;
     MP_USED(&part)   = MP_USED(div);
+
+    /* We have now truncated the part of the remainder to the same length as
+     * the divisor. If part is smaller than div, extend part by one digit. */
     if (s_mp_cmp(&part, div) < 0) {
       -- unusedRem;
 #if MP_ARGCHK == 2
       assert(unusedRem >= 0);
 #endif
       -- MP_DIGITS(&part);
       ++ MP_USED(&part);
       ++ MP_ALLOC(&part);
+      partExtended = 1;
     }
 
     /* Compute a guess for the next quotient digit       */
     q_msd = MP_DIGIT(&part, MP_USED(&part) - 1);
     div_msd = MP_DIGIT(div, MP_USED(div) - 1);
-    if (q_msd >= div_msd) {
+    if (!partExtended) {
+      /* In this case, q_msd /= div_msd is always 1. First, since div_msd is
+       * normalized to have the high bit set, 2*div_msd > MP_DIGIT_MAX. Since
+       * we didn't extend part, q_msd >= div_msd. Therefore we know that
+       * div_msd <= q_msd <= MP_DIGIT_MAX < 2*div_msd. Dividing by div_msd we
+       * get 1 <= q_msd/div_msd < 2. So q_msd /= div_msd must be 1. */
       q_msd = 1;
-    } else if (MP_USED(&part) > 1) {
+    } else {
 #if !defined(MP_NO_MP_WORD) && !defined(MP_NO_DIV_WORD)
       q_msd = (q_msd << MP_DIGIT_BIT) | MP_DIGIT(&part, MP_USED(&part) - 2);
       q_msd /= div_msd;
       if (q_msd == RADIX)
         --q_msd;
 #else
-      mp_digit r;
-      MP_CHECKOK( s_mpv_div_2dx1d(q_msd, MP_DIGIT(&part, MP_USED(&part) - 2), 
-                                  div_msd, &q_msd, &r) );
+      if (q_msd == div_msd) {
+        q_msd = MP_DIGIT_MAX;
+      } else {
+        mp_digit r;
+        MP_CHECKOK( s_mpv_div_2dx1d(q_msd, MP_DIGIT(&part, MP_USED(&part) - 2),
+                                    div_msd, &q_msd, &r) );
+      }
 #endif
-    } else {
-      q_msd = 0;
     }
 #if MP_ARGCHK == 2
     assert(q_msd > 0); /* This case should never occur any more. */
 #endif
     if (q_msd <= 0)
       break;
 
     /* See what that multiplies out to                   */
     mp_copy(div, &t);
     MP_CHECKOK( s_mp_mul_d(&t, (mp_digit)q_msd) );
@@ skipping 410 matching lines @@
       if((res = s_mp_lshd(mp, 1)) != MP_OKAY)
         return res;
     }
     MP_DIGIT(mp, 0) = d;
   }
   return MP_OKAY;
 } /* end mp_read_unsigned_octets() */
 /* }}} */
 
 /* {{{ mp_unsigned_octet_size(mp) */
-int    
+unsigned int
 mp_unsigned_octet_size(const mp_int *mp)
 {
-  int  bytes;
+  unsigned int bytes;
   int  ix;
   mp_digit  d = 0;
 
   ARGCHK(mp != NULL, MP_BADARG);
   ARGCHK(MP_ZPOS == SIGN(mp), MP_BADARG);
 
   bytes = (USED(mp) * sizeof(mp_digit));
 
   /* subtract leading zeros. */
   /* Iterate over each digit... */
@@ skipping 16 matching lines @@
   return bytes;
 } /* end mp_unsigned_octet_size() */
 /* }}} */
 
 /* {{{ mp_to_unsigned_octets(mp, str) */
 /* output a buffer of big endian octets no longer than specified. */
 mp_err 
 mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen)
 {
   int  ix, pos = 0;
-  int  bytes;
+  unsigned int  bytes;
 
   ARGCHK(mp != NULL && str != NULL && !SIGN(mp), MP_BADARG);
 
   bytes = mp_unsigned_octet_size(mp);
-  ARGCHK(bytes >= 0 && bytes <= maxlen, MP_BADARG);
+  ARGCHK(bytes <= maxlen, MP_BADARG);
 
   /* Iterate over each digit... */
   for(ix = USED(mp) - 1; ix >= 0; ix--) {
     mp_digit  d = DIGIT(mp, ix);
     int       jx;
 
     /* Unpack digit bytes, high order first */
     for(jx = sizeof(mp_digit) - 1; jx >= 0; jx--) {
       unsigned char x = (unsigned char)(d >> (jx * CHAR_BIT));
       if (!pos && !x)   /* suppress leading zeros */
         continue;
       str[pos++] = x;
     }
   }
   if (!pos)
     str[pos++] = 0;
   return pos;
 } /* end mp_to_unsigned_octets() */
 /* }}} */
 
 /* {{{ mp_to_signed_octets(mp, str) */
 /* output a buffer of big endian octets no longer than specified. */
 mp_err 
 mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen)
 {
   int  ix, pos = 0;
-  int  bytes;
+  unsigned int  bytes;
 
   ARGCHK(mp != NULL && str != NULL && !SIGN(mp), MP_BADARG);
 
   bytes = mp_unsigned_octet_size(mp);
-  ARGCHK(bytes >= 0 && bytes <= maxlen, MP_BADARG);
+  ARGCHK(bytes <= maxlen, MP_BADARG);
 
   /* Iterate over each digit... */
   for(ix = USED(mp) - 1; ix >= 0; ix--) {
     mp_digit  d = DIGIT(mp, ix);
     int       jx;
 
     /* Unpack digit bytes, high order first */
     for(jx = sizeof(mp_digit) - 1; jx >= 0; jx--) {
       unsigned char x = (unsigned char)(d >> (jx * CHAR_BIT));
       if (!pos) {
@@ skipping 14 matching lines @@
   return pos;
 } /* end mp_to_signed_octets() */
 /* }}} */
 
 /* {{{ mp_to_fixlen_octets(mp, str) */
 /* output a buffer of big endian octets exactly as long as requested. */
 mp_err 
 mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size length)
 {
   int  ix, pos = 0;
-  int  bytes;
+  unsigned int  bytes;
 
   ARGCHK(mp != NULL && str != NULL && !SIGN(mp), MP_BADARG);
 
   bytes = mp_unsigned_octet_size(mp);
-  ARGCHK(bytes >= 0 && bytes <= length, MP_BADARG);
+  ARGCHK(bytes <= length, MP_BADARG);
 
   /* place any needed leading zeros */
   for (;length > bytes; --length) {
         *str++ = 0;
   }
 
   /* Iterate over each digit... */
   for(ix = USED(mp) - 1; ix >= 0; ix--) {
     mp_digit  d = DIGIT(mp, ix);
     int       jx;
 
     /* Unpack digit bytes, high order first */
     for(jx = sizeof(mp_digit) - 1; jx >= 0; jx--) {
       unsigned char x = (unsigned char)(d >> (jx * CHAR_BIT));
       if (!pos && !x)   /* suppress leading zeros */
         continue;
       str[pos++] = x;
     }
   }
   if (!pos)
     str[pos++] = 0;
   return MP_OKAY;
 } /* end mp_to_fixlen_octets() */
 /* }}} */
 
 
 /*------------------------------------------------------------------------*/
 /* HERE THERE BE DRAGONS                                                  */