/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c

Bug Summary

File:	root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c
Warning:	line 1950, column 35 The right operand of '<' is a garbage value
Annotated Source Code

Press '?' to see keyboard shortcuts
Show analyzer invocation
clang -cc1 -cc1 -triple x86_64-pc-linux-gnu -O2 -analyze -disable-free -clear-ast-before-backend -disable-llvm-verifier -discard-value-names -main-file-name mpi.c -analyzer-checker=core -analyzer-checker=apiModeling -analyzer-checker=unix -analyzer-checker=deadcode -analyzer-checker=security.insecureAPI.UncheckedReturn -analyzer-checker=security.insecureAPI.getpw -analyzer-checker=security.insecureAPI.gets -analyzer-checker=security.insecureAPI.mktemp -analyzer-checker=security.insecureAPI.mkstemp -analyzer-checker=security.insecureAPI.vfork -analyzer-checker=nullability.NullPassedToNonnull -analyzer-checker=nullability.NullReturnedFromNonnull -analyzer-output plist -w -setup-static-analyzer -analyzer-config-compatibility-mode=true -mrelocation-model pic -pic-level 2 -fhalf-no-semantic-interposition -mframe-pointer=all -relaxed-aliasing -ffp-contract=off -fno-rounding-math -mconstructor-aliases -funwind-tables=2 -target-cpu x86-64 -tune-cpu generic -debugger-tuning=gdb -fdebug-compilation-dir=/root/firefox-clang/obj-x86_64-pc-linux-gnu/security/nss/lib/freebl/freebl_freeblpriv3 -fcoverage-compilation-dir=/root/firefox-clang/obj-x86_64-pc-linux-gnu/security/nss/lib/freebl/freebl_freeblpriv3 -resource-dir /usr/lib/llvm-23/lib/clang/23 -include /root/firefox-clang/obj-x86_64-pc-linux-gnu/mozilla-config.h -U _FORTIFY_SOURCE -D _FORTIFY_SOURCE=2 -D DEBUG -D SHLIB_SUFFIX="so" -D SHLIB_PREFIX="lib" -D SHLIB_VERSION="3" -D SOFTOKEN_SHLIB_VERSION="3" -D RIJNDAEL_INCLUDE_TABLES -D MP_API_COMPATIBLE -D KRML_MUSTINLINE=inline -D HACL_CAN_COMPILE_VEC128 -D HACL_CAN_COMPILE_VEC256 -D HACL_CAN_COMPILE_INTRINSICS -D HAVE_INT128_SUPPORT -D HACL_CAN_COMPILE_UINT128 -D FREEBL_LOWHASH -D FREEBL_NO_DEPEND -D NSS_BEVAND_ARCFOUR -D MPI_AMD64 -D MP_ASSEMBLY_MULTIPLY -D NSS_USE_COMBA -D USE_HW_AES -D USE_HW_SHA2 -D NSS_FIPS_DISABLED -D NSS_NO_INIT_SUPPORT -D NSS_X86_OR_X64 -D NSS_X64 -D NSS_USE_64 -D SEED_ONLY_DEV_URANDOM -D USE_UTIL_DIRECTLY -D NO_NSPR_10_SUPPORT -D SSL_DISABLE_DEPRECATED_CIPHER_SUITE_NAMES -D LINUX2_1 -D LINUX -D linux -D _DEFAULT_SOURCE -D _BSD_SOURCE -D _POSIX_SOURCE -D SDB_MEASURE_USE_TEMP_DIR -D HAVE_STRERROR -D XP_UNIX -D _REENTRANT -D NSS_DISABLE_DBM -D NSS_DISABLE_LIBPKIX -D NSS_USE_PKCS5_PBKD2_PARAMS2_ONLY -D SOFTOKEN_USE_PKCS5_PBKD2_PARAMS2_ONLY -I /root/firefox-clang/security/nss/lib/freebl -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/security/nss/lib/freebl/freebl_freeblpriv3 -I /root/firefox-clang/security/nss/lib/freebl/mpi -I /root/firefox-clang/security/nss/lib/freebl/ecl -I /root/firefox-clang/security/nss/lib/freebl/verified -I /root/firefox-clang/security/nss/lib/freebl/verified/internal -I /root/firefox-clang/security/nss/lib/freebl/verified/karamel/include -I /root/firefox-clang/security/nss/lib/freebl/verified/karamel/krmllib/dist/minimal -I /root/firefox-clang/security/nss/lib/freebl/deprecated -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include/nspr -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include/private/nss -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include/nss -I /root/firefox-clang/obj-x86_64-pc-linux-gnu/dist/include -D MOZILLA_CLIENT -internal-isystem /usr/lib/llvm-23/lib/clang/23/include -internal-isystem /usr/local/include -internal-isystem /usr/lib/gcc/x86_64-linux-gnu/16/../../../../x86_64-linux-gnu/include -internal-externc-isystem /usr/include/x86_64-linux-gnu -internal-externc-isystem /include -internal-externc-isystem /usr/include -Wno-error=tautological-type-limit-compare -Wno-range-loop-analysis -Wno-error=deprecated-declarations -Wno-error=array-bounds -Wno-error=free-nonheap-object -Wno-error=atomic-alignment -Wno-error=deprecated-builtins -Wno-psabi -Wno-error=builtin-macro-redefined -Wno-unknown-warning-option -Wno-character-conversion -ferror-limit 19 -fstrict-flex-arrays=1 -stack-protector 2 -fstack-clash-protection -ftrivial-auto-var-init=pattern -fgnuc-version=4.2.1 -fskip-odr-check-in-gmf -fdiagnostics-absolute-paths -vectorize-loops -vectorize-slp -analyzer-checker optin.performance.Padding -analyzer-output=html -analyzer-config stable-report-filename=true -mllvm -dwarf-linkage-names=Abstract -faddrsig -fdwarf2-cfi-asm -o /tmp/scan-build-2026-10-17-231001-351276-1 -x c /root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c
1/*
*  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/. */

10#include "mpi-priv.h"
11#include "mplogic.h"

13#include <assert.h>

15#if defined(__arm__) && \
  ((defined(__thumb__) && !defined(__thumb2__)) || defined(__ARM_ARCH_3__))
17/* 16-bit thumb or ARM v3 doesn't work inlined assember version */
18#undef MP_ASSEMBLY_MULTIPLY1
19#undef MP_ASSEMBLY_SQUARE
20#endif

22#if MP_LOGTAB1
23/*
A table of the logs of 2 for various bases (the 0 and 1 entries of
this table are meaningless and should not be referenced).

This table is used to compute output lengths for the mp_toradix()
function.  Since a number n in radix r takes up about log_r(n)
digits, we estimate the output size by taking the least integer
greater than log_r(n), where:

log_r(n) = log_2(n) * log_r(2)

This table, therefore, is a table of log_r(2) for 2 <= r <= 36,
which are the output bases supported.
*/
37#include "logtab.h"
38#endif

40#ifdef CT_VERIF
41#include <valgrind/memcheck.h>
42#endif

44/* {{{ Constant strings */

46/* Constant strings returned by mp_strerror() */
47static const char *mp_err_string[] = {
  "unknown result code",     /* say what?            */
  "boolean true",            /* MP_OKAY, MP_YES      */
  "boolean false",           /* MP_NO                */
  "out of memory",           /* MP_MEM               */
  "argument out of range",   /* MP_RANGE             */
  "invalid input parameter", /* MP_BADARG            */
  "result is undefined"      /* MP_UNDEF             */
55};

57/* Value to digit maps for radix conversion   */

59/* s_dmap_1 - standard digits and letters */
60static const char *s_dmap_1 =
  "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

63/* }}} */

65/* {{{ Default precision manipulation */

67/* Default precision for newly created mp_int's      */
68static mp_size s_mp_defprec = MP_DEFPREC64;

70mp_size
71mp_get_prec(void)
72{
  return s_mp_defprec;

75} /* end mp_get_prec() */

77void
78mp_set_prec(mp_size prec)
79{
  if (prec == 0)
      s_mp_defprec = MP_DEFPREC64;
  else
      s_mp_defprec = prec;

85} /* end mp_set_prec() */

87/* }}} */

89#ifdef CT_VERIF
90void
91mp_taint(mp_int *mp)
92{
  size_t i;
  for (i = 0; i < mp->used; ++i) {
      VALGRIND_MAKE_MEM_UNDEFINED(&(mp->dp[i]), sizeof(mp_digit));
  }
97}

99void
100mp_untaint(mp_int *mp)
101{
  size_t i;
  for (i = 0; i < mp->used; ++i) {
      VALGRIND_MAKE_MEM_DEFINED(&(mp->dp[i]), sizeof(mp_digit));
  }
106}
107#endif

109/*------------------------------------------------------------------------*/
110/* {{{ mp_init(mp) */

112/*
mp_init(mp)

Initialize a new zero-valued mp_int.  Returns MP_OKAY if successful,
MP_MEM if memory could not be allocated for the structure.
*/

119mp_err
120mp_init(mp_int *mp)
121{
  return mp_init_size(mp, s_mp_defprec);

124} /* end mp_init() */

126/* }}} */

128/* {{{ mp_init_size(mp, prec) */

130/*
mp_init_size(mp, prec)

Initialize a new zero-valued mp_int with at least the given
precision; returns MP_OKAY if successful, or MP_MEM if memory could
not be allocated for the structure.
*/

138mp_err
139mp_init_size(mp_int *mp, mp_size prec)
140{
  ARGCHK(mp != NULL && prec > 0, MP_BADARG)((void) sizeof ((mp != ((void*)0) && prec > 0) ? 1
 : 0), __extension__ ({ if (mp != ((void*)0) && prec >
 0) ; else __assert_fail ("mp != ((void*)0) && prec > 0"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 141
, __extension__ __PRETTY_FUNCTION__); }));

  prec = MP_ROUNDUP(prec, s_mp_defprec)((((prec) + (s_mp_defprec) - 1) / (s_mp_defprec)) * (s_mp_defprec
));
  if ((DIGITS(mp)((mp)->dp) = s_mp_alloc(prec, sizeof(mp_digit))) == NULL((void*)0))
      return MP_MEM-2;

  SIGN(mp)((mp)->sign) = ZPOS0;
  USED(mp)((mp)->used) = 1;
  ALLOC(mp)((mp)->alloc) = prec;

  return MP_OKAY0;

153} /* end mp_init_size() */

155/* }}} */

157/* {{{ mp_init_copy(mp, from) */

159/*
mp_init_copy(mp, from)

Initialize mp as an exact copy of from.  Returns MP_OKAY if
successful, MP_MEM if memory could not be allocated for the new
structure.
*/

167mp_err
168mp_init_copy(mp_int *mp, const mp_int *from)
169{
  ARGCHK(mp != NULL && from != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0) && from != ((void*)
0)) ? 1 : 0), __extension__ ({ if (mp != ((void*)0) &&
 from != ((void*)0)) ; else __assert_fail ("mp != ((void*)0) && from != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 170
, __extension__ __PRETTY_FUNCTION__); }));
15
←
Taking true branch→

  if (mp == from)
16
←
Assuming 'mp' is equal to 'from'→
17
←
Taking true branch→
      return MP_OKAY0;
18
←
Returning without writing to 'mp->used'→

  if ((DIGITS(mp)((mp)->dp) = s_mp_alloc(ALLOC(from)((from)->alloc), sizeof(mp_digit))) == NULL((void*)0))
      return MP_MEM-2;

  s_mp_copy(DIGITS(from)((from)->dp), DIGITS(mp)((mp)->dp), USED(from)((from)->used));
  USED(mp)((mp)->used) = USED(from)((from)->used);
  ALLOC(mp)((mp)->alloc) = ALLOC(from)((from)->alloc);
  SIGN(mp)((mp)->sign) = SIGN(from)((from)->sign);

  return MP_OKAY0;

185} /* end mp_init_copy() */

187/* }}} */

189/* {{{ mp_copy(from, to) */

191/*
mp_copy(from, to)

Copies the mp_int 'from' to the mp_int 'to'.  It is presumed that
'to' has already been initialized (if not, use mp_init_copy()
instead). If 'from' and 'to' are identical, nothing happens.
*/

199mp_err
200mp_copy(const mp_int *from, mp_int *to)
201{
  ARGCHK(from != NULL && to != NULL, MP_BADARG)((void) sizeof ((from != ((void*)0) && to != ((void*)
0)) ? 1 : 0), __extension__ ({ if (from != ((void*)0) &&
 to != ((void*)0)) ; else __assert_fail ("from != ((void*)0) && to != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 202
, __extension__ __PRETTY_FUNCTION__); }));

  if (from == to)
      return MP_OKAY0;

  { /* copy */
      mp_digit *tmp;

      /*
        If the allocated buffer in 'to' already has enough space to hold
        all the used digits of 'from', we'll re-use it to avoid hitting
        the memory allocater more than necessary; otherwise, we'd have
        to grow anyway, so we just allocate a hunk and make the copy as
        usual
       */
      if (ALLOC(to)((to)->alloc) >= USED(from)((from)->used)) {
          s_mp_setz(DIGITS(to)((to)->dp) + USED(from)((from)->used), ALLOC(to)((to)->alloc) - USED(from)((from)->used));
          s_mp_copy(DIGITS(from)((from)->dp), DIGITS(to)((to)->dp), USED(from)((from)->used));

      } else {
          if ((tmp = s_mp_alloc(ALLOC(from)((from)->alloc), sizeof(mp_digit))) == NULL((void*)0))
              return MP_MEM-2;

          s_mp_copy(DIGITS(from)((from)->dp), tmp, USED(from)((from)->used));

          if (DIGITS(to)((to)->dp) != NULL((void*)0)) {
              s_mp_setz(DIGITS(to)((to)->dp), ALLOC(to)((to)->alloc));
              s_mp_free(DIGITS(to)((to)->dp));
          }

          DIGITS(to)((to)->dp) = tmp;
          ALLOC(to)((to)->alloc) = ALLOC(from)((from)->alloc);
      }

      /* Copy the precision and sign from the original */
      USED(to)((to)->used) = USED(from)((from)->used);
      SIGN(to)((to)->sign) = SIGN(from)((from)->sign);
  } /* end copy */

  return MP_OKAY0;

243} /* end mp_copy() */

245/* }}} */

247/* {{{ mp_exch(mp1, mp2) */

249/*
mp_exch(mp1, mp2)

Exchange mp1 and mp2 without allocating any intermediate memory
(well, unless you count the stack space needed for this call and the
locals it creates...).  This cannot fail.
*/

257void
258mp_exch(mp_int *mp1, mp_int *mp2)
259{
260#if MP_ARGCHK2 == 2
  assert(mp1 != NULL && mp2 != NULL)((void) sizeof ((mp1 != ((void*)0) && mp2 != ((void*)
0)) ? 1 : 0), __extension__ ({ if (mp1 != ((void*)0) &&
 mp2 != ((void*)0)) ; else __assert_fail ("mp1 != NULL && mp2 != NULL"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 261
, __extension__ __PRETTY_FUNCTION__); }));
262#else
  if (mp1 == NULL((void*)0) || mp2 == NULL((void*)0))
      return;
265#endif

  s_mp_exch(mp1, mp2);

269} /* end mp_exch() */

271/* }}} */

273/* {{{ mp_clear(mp) */

275/*
mp_clear(mp)

Release the storage used by an mp_int, and void its fields so that
if someone calls mp_clear() again for the same int later, we won't
get tollchocked.
*/

283void
284mp_clear(mp_int *mp)
285{
  if (mp == NULL((void*)0))
      return;

  if (DIGITS(mp)((mp)->dp) != NULL((void*)0)) {
      s_mp_setz(DIGITS(mp)((mp)->dp), ALLOC(mp)((mp)->alloc));
      s_mp_free(DIGITS(mp)((mp)->dp));
      DIGITS(mp)((mp)->dp) = NULL((void*)0);
  }

  USED(mp)((mp)->used) = 0;
  ALLOC(mp)((mp)->alloc) = 0;

298} /* end mp_clear() */

300/* }}} */

302/* {{{ mp_zero(mp) */

304/*
mp_zero(mp)

Set mp to zero.  Does not change the allocated size of the structure,
and therefore cannot fail (except on a bad argument, which we ignore)
*/
310void
311mp_zero(mp_int *mp)
312{
  if (mp == NULL((void*)0))
      return;

  s_mp_setz(DIGITS(mp)((mp)->dp), ALLOC(mp)((mp)->alloc));
  USED(mp)((mp)->used) = 1;
  SIGN(mp)((mp)->sign) = ZPOS0;

320} /* end mp_zero() */

322/* }}} */

324/* {{{ mp_set(mp, d) */

326void
327mp_set(mp_int *mp, mp_digit d)
328{
  if (mp == NULL((void*)0))
      return;

  mp_zero(mp);
  DIGIT(mp, 0)(mp)->dp[(0)] = d;

335} /* end mp_set() */

337/* }}} */

339/* {{{ mp_set_int(mp, z) */

341mp_err
342mp_set_int(mp_int *mp, long z)
343{
  unsigned long v = labs(z);
  mp_err res;

  ARGCHK(mp != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 347
, __extension__ __PRETTY_FUNCTION__); }));

  /* https://bugzilla.mozilla.org/show_bug.cgi?id=1509432 */
  if ((res = mp_set_ulong(mp, v)) != MP_OKAY0) { /* avoids duplicated code */
      return res;
  }

  if (z < 0) {
      SIGN(mp)((mp)->sign) = NEG1;
  }

  return MP_OKAY0;
359} /* end mp_set_int() */

361/* }}} */

363/* {{{ mp_set_ulong(mp, z) */

365mp_err
366mp_set_ulong(mp_int *mp, unsigned long z)
367{
  int ix;
  mp_err res;

  ARGCHK(mp != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 371
, __extension__ __PRETTY_FUNCTION__); }));

  mp_zero(mp);
  if (z == 0)
      return MP_OKAY0; /* shortcut for zero */

  if (sizeof z <= sizeof(mp_digit)) {
      DIGIT(mp, 0)(mp)->dp[(0)] = z;
  } else {
      for (ix = sizeof(long) - 1; ix >= 0; ix--) {
          if ((res = s_mp_mul_d(mp, (UCHAR_MAX(127*2 +1) + 1))) != MP_OKAY0)
              return res;

          res = s_mp_add_d(mp, (mp_digit)((z >> (ix * CHAR_BIT8)) & UCHAR_MAX(127*2 +1)));
          if (res != MP_OKAY0)
              return res;
      }
  }
  return MP_OKAY0;
390} /* end mp_set_ulong() */

392/* }}} */

394/*------------------------------------------------------------------------*/
395/* {{{ Digit arithmetic */

397/* {{{ mp_add_d(a, d, b) */

399/*
mp_add_d(a, d, b)

Compute the sum b = a + d, for a single digit d.  Respects the sign of
its primary addend (single digits are unsigned anyway).
*/

406mp_err
407mp_add_d(const mp_int *a, mp_digit d, mp_int *b)
408{
  mp_int tmp;
  mp_err res;

  ARGCHK(a != NULL && b != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 412
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_init_copy(&tmp, a)) != MP_OKAY0)
      return res;

  if (SIGN(&tmp)((&tmp)->sign) == ZPOS0) {
      if ((res = s_mp_add_d(&tmp, d)) != MP_OKAY0)
          goto CLEANUP;
  } else if (s_mp_cmp_d(&tmp, d) >= 0) {
      if ((res = s_mp_sub_d(&tmp, d)) != MP_OKAY0)
          goto CLEANUP;
  } else {
      mp_neg(&tmp, &tmp);

      DIGIT(&tmp, 0)(&tmp)->dp[(0)] = d - DIGIT(&tmp, 0)(&tmp)->dp[(0)];
  }

  if (s_mp_cmp_d(&tmp, 0) == 0)
      SIGN(&tmp)((&tmp)->sign) = ZPOS0;

  s_mp_exch(&tmp, b);

434CLEANUP:
  mp_clear(&tmp);
  return res;

438} /* end mp_add_d() */

440/* }}} */

442/* {{{ mp_sub_d(a, d, b) */

444/*
mp_sub_d(a, d, b)

Compute the difference b = a - d, for a single digit d.  Respects the
sign of its subtrahend (single digits are unsigned anyway).
*/

451mp_err
452mp_sub_d(const mp_int *a, mp_digit d, mp_int *b)
453{
  mp_int tmp;
  mp_err res;

  ARGCHK(a != NULL && b != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 457
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_init_copy(&tmp, a)) != MP_OKAY0)
      return res;

  if (SIGN(&tmp)((&tmp)->sign) == NEG1) {
      if ((res = s_mp_add_d(&tmp, d)) != MP_OKAY0)
          goto CLEANUP;
  } else if (s_mp_cmp_d(&tmp, d) >= 0) {
      if ((res = s_mp_sub_d(&tmp, d)) != MP_OKAY0)
          goto CLEANUP;
  } else {
      mp_neg(&tmp, &tmp);

      DIGIT(&tmp, 0)(&tmp)->dp[(0)] = d - DIGIT(&tmp, 0)(&tmp)->dp[(0)];
      SIGN(&tmp)((&tmp)->sign) = NEG1;
  }

  if (s_mp_cmp_d(&tmp, 0) == 0)
      SIGN(&tmp)((&tmp)->sign) = ZPOS0;

  s_mp_exch(&tmp, b);

480CLEANUP:
  mp_clear(&tmp);
  return res;

484} /* end mp_sub_d() */

486/* }}} */

488/* {{{ mp_mul_d(a, d, b) */

490/*
mp_mul_d(a, d, b)

Compute the product b = a * d, for a single digit d.  Respects the sign
of its multiplicand (single digits are unsigned anyway)
*/

497mp_err
498mp_mul_d(const mp_int *a, mp_digit d, mp_int *b)
499{
  mp_err res;

  ARGCHK(a != NULL && b != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 502
, __extension__ __PRETTY_FUNCTION__); }));

  if (d == 0) {
      mp_zero(b);
      return MP_OKAY0;
  }

  if ((res = mp_copy(a, b)) != MP_OKAY0)
      return res;

  res = s_mp_mul_d(b, d);

  return res;

516} /* end mp_mul_d() */

518/* }}} */

520/* {{{ mp_mul_2(a, c) */

522mp_err
523mp_mul_2(const mp_int *a, mp_int *c)
524{
  mp_err res;

  ARGCHK(a != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && c != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && c !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 527
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_copy(a, c)) != MP_OKAY0)
      return res;

  return s_mp_mul_2(c);

534} /* end mp_mul_2() */

536/* }}} */

538/* {{{ mp_div_d(a, d, q, r) */

540/*
mp_div_d(a, d, q, r)

Compute the quotient q = a / d and remainder r = a mod d, for a
single digit d.  Respects the sign of its divisor (single digits are
unsigned anyway).
*/

548mp_err
549mp_div_d(const mp_int *a, mp_digit d, mp_int *q, mp_digit *r)
550{
  mp_err res;
  mp_int qp;
  mp_digit rem = 0;
  int pow;

  ARGCHK(a != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (a != ((void*)0)) ; else __assert_fail ("a != ((void*)0)", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 556, __extension__ __PRETTY_FUNCTION__); }));

  if (d == 0)
      return MP_RANGE-3;

  /* Shortcut for powers of two ... */
  if ((pow = s_mp_ispow2d(d)) >= 0) {
      mp_digit mask;

      mask = ((mp_digit)1 << pow) - 1;
      rem = DIGIT(a, 0)(a)->dp[(0)] & mask;

      if (q) {
          if ((res = mp_copy(a, q)) != MP_OKAY0) {
              return res;
          }
          s_mp_div_2d(q, pow);
      }

      if (r)
          *r = rem;

      return MP_OKAY0;
  }

  if ((res = mp_init_copy(&qp, a)) != MP_OKAY0)
      return res;

  res = s_mp_div_d(&qp, d, &rem);

  if (s_mp_cmp_d(&qp, 0) == 0)
      SIGN(&qp)((&qp)->sign) = ZPOS0;

  if (r) {
      *r = rem;
  }

  if (q)
      s_mp_exch(&qp, q);

  mp_clear(&qp);
  return res;

599} /* end mp_div_d() */

601/* }}} */

603/* {{{ mp_div_2(a, c) */

605/*
mp_div_2(a, c)

Compute c = a / 2, disregarding the remainder.
*/

611mp_err
612mp_div_2(const mp_int *a, mp_int *c)
613{
  mp_err res;

  ARGCHK(a != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && c != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && c !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 616
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_copy(a, c)) != MP_OKAY0)
      return res;

  s_mp_div_2(c);

  return MP_OKAY0;

625} /* end mp_div_2() */

627/* }}} */

629/* {{{ mp_expt_d(a, d, b) */

631mp_err
632mp_expt_d(const mp_int *a, mp_digit d, mp_int *c)
633{
  mp_int s, x;
  mp_err res;

  ARGCHK(a != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && c != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && c !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 637
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_init(&s)) != MP_OKAY0)
      return res;
  if ((res = mp_init_copy(&x, a)) != MP_OKAY0)
      goto X;

  DIGIT(&s, 0)(&s)->dp[(0)] = 1;

  while (d != 0) {
      if (d & 1) {
          if ((res = s_mp_mul(&s, &x)) != MP_OKAY0)
              goto CLEANUP;
      }

      d /= 2;

      if ((res = s_mp_sqr(&x)) != MP_OKAY0)
          goto CLEANUP;
  }

  s_mp_exch(&s, c);

660CLEANUP:
  mp_clear(&x);
662X:
  mp_clear(&s);

  return res;

667} /* end mp_expt_d() */

669/* }}} */

671/* }}} */

673/*------------------------------------------------------------------------*/
674/* {{{ Full arithmetic */

676/* {{{ mp_abs(a, b) */

678/*
mp_abs(a, b)

Compute b = |a|.  'a' and 'b' may be identical.
*/

684mp_err
685mp_abs(const mp_int *a, mp_int *b)
686{
  mp_err res;

  ARGCHK(a != NULL && b != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 689
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_copy(a, b)) != MP_OKAY0)
      return res;

  SIGN(b)((b)->sign) = ZPOS0;

  return MP_OKAY0;

698} /* end mp_abs() */

700/* }}} */

702/* {{{ mp_neg(a, b) */

704/*
mp_neg(a, b)

Compute b = -a.  'a' and 'b' may be identical.
*/

710mp_err
711mp_neg(const mp_int *a, mp_int *b)
712{
  mp_err res;

  ARGCHK(a != NULL && b != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 715
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_copy(a, b)) != MP_OKAY0)
      return res;

  if (s_mp_cmp_d(b, 0) == MP_EQ0)
      SIGN(b)((b)->sign) = ZPOS0;
  else
      SIGN(b)((b)->sign) = (SIGN(b)((b)->sign) == NEG1) ? ZPOS0 : NEG1;

  return MP_OKAY0;

727} /* end mp_neg() */

729/* }}} */

731/* {{{ mp_add(a, b, c) */

733/*
mp_add(a, b, c)

Compute c = a + b.  All parameters may be identical.
*/

739mp_err
740mp_add(const mp_int *a, const mp_int *b, mp_int *c)
741{
  mp_err res;

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 744
, __extension__ __PRETTY_FUNCTION__); }));

  if (SIGN(a)((a)->sign) == SIGN(b)((b)->sign)) { /* same sign:  add values, keep sign */
      MP_CHECKOK(s_mp_add_3arg(a, b, c))if (0 > (res = (s_mp_add_3arg(a, b, c)))) goto CLEANUP;
  } else if (s_mp_cmp(a, b) >= 0) { /* different sign: |a| >= |b|   */
      MP_CHECKOK(s_mp_sub_3arg(a, b, c))if (0 > (res = (s_mp_sub_3arg(a, b, c)))) goto CLEANUP;
  } else { /* different sign: |a|  < |b|   */
      MP_CHECKOK(s_mp_sub_3arg(b, a, c))if (0 > (res = (s_mp_sub_3arg(b, a, c)))) goto CLEANUP;
  }

  if (s_mp_cmp_d(c, 0) == MP_EQ0)
      SIGN(c)((c)->sign) = ZPOS0;

757CLEANUP:
  return res;

760} /* end mp_add() */

762/* }}} */

764/* {{{ mp_sub(a, b, c) */

766/*
mp_sub(a, b, c)

Compute c = a - b.  All parameters may be identical.
*/

772mp_err
773mp_sub(const mp_int *a, const mp_int *b, mp_int *c)
774{
  mp_err res;
  int magDiff;

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 778
, __extension__ __PRETTY_FUNCTION__); }));

  if (a == b) {
      mp_zero(c);
      return MP_OKAY0;
  }

  if (MP_SIGN(a)((a)->sign) != MP_SIGN(b)((b)->sign)) {
      MP_CHECKOK(s_mp_add_3arg(a, b, c))if (0 > (res = (s_mp_add_3arg(a, b, c)))) goto CLEANUP;
  } else if (!(magDiff = s_mp_cmp(a, b))) {
      mp_zero(c);
      res = MP_OKAY0;
  } else if (magDiff > 0) {
      MP_CHECKOK(s_mp_sub_3arg(a, b, c))if (0 > (res = (s_mp_sub_3arg(a, b, c)))) goto CLEANUP;
  } else {
      MP_CHECKOK(s_mp_sub_3arg(b, a, c))if (0 > (res = (s_mp_sub_3arg(b, a, c)))) goto CLEANUP;
      MP_SIGN(c)((c)->sign) = !MP_SIGN(a)((a)->sign);
  }

  if (s_mp_cmp_d(c, 0) == MP_EQ0)
      MP_SIGN(c)((c)->sign) = MP_ZPOS0;

800CLEANUP:
  return res;

803} /* end mp_sub() */

805/* }}} */

807/* {{{ s_mp_mulg(a, b, c) */

809/*
s_mp_mulg(a, b, c)

Compute c = a * b.  All parameters may be identical. if constantTime is set,
then the operations are done in constant time. The original is mostly
constant time as long as s_mpv_mul_d_add() is constant time. This is true
of the x86 assembler, as well as the current c code.
*/
817mp_err
818s_mp_mulg(const mp_int *a, const mp_int *b, mp_int *c, int constantTime)
819{
  mp_digit *pb;
  mp_int tmp;
  mp_err res;
  mp_size ib;
  mp_size useda, usedb;

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 826
, __extension__ __PRETTY_FUNCTION__); }));

  if (a == c) {
      if ((res = mp_init_copy(&tmp, a)) != MP_OKAY0)
          return res;
      if (a == b)
          b = &tmp;
      a = &tmp;
  } else if (b == c) {
      if ((res = mp_init_copy(&tmp, b)) != MP_OKAY0)
          return res;
      b = &tmp;
  } else {
      MP_DIGITS(&tmp)((&tmp)->dp) = 0;
  }

  if (MP_USED(a)((a)->used) < MP_USED(b)((b)->used)) {
      const mp_int *xch = b; /* switch a and b, to do fewer outer loops */
      b = a;
      a = xch;
  }

  MP_USED(c)((c)->used) = 1;
  MP_DIGIT(c, 0)(c)->dp[(0)] = 0;
  if ((res = s_mp_pad(c, USED(a)((a)->used) + USED(b)((b)->used))) != MP_OKAY0)
      goto CLEANUP;

853#ifdef NSS_USE_COMBA1
  /* comba isn't constant time because it clamps! If we cared
   * (we needed a constant time version of multiply that was 'faster'
   * we could easily pass constantTime down to the comba code and
   * get it to skip the clamp... but here are assembler versions
   * which add comba to platforms that can't compile the normal
   * comba's imbedded assembler which would also need to change, so
   * for now we just skip comba when we are running constant time. */
  if (!constantTime && (MP_USED(a)((a)->used) == MP_USED(b)((b)->used)) && IS_POWER_OF_2(MP_USED(b))((((b)->used)) && !((((b)->used)) & ((((b)->
used)) - 1)))) {
      if (MP_USED(a)((a)->used) == 4) {
          s_mp_mul_comba_4(a, b, c);
          goto CLEANUP;
      }
      if (MP_USED(a)((a)->used) == 8) {
          s_mp_mul_comba_8(a, b, c);
          goto CLEANUP;
      }
      if (MP_USED(a)((a)->used) == 16) {
          s_mp_mul_comba_16(a, b, c);
          goto CLEANUP;
      }
      if (MP_USED(a)((a)->used) == 32) {
          s_mp_mul_comba_32(a, b, c);
          goto CLEANUP;
      }
  }
879#endif

  pb = MP_DIGITS(b)((b)->dp);
  s_mpv_mul_d(MP_DIGITS(a), MP_USED(a), *pb++, MP_DIGITS(c))((mp_digit *)((c)->dp))[((a)->used)] = s_mpv_mul_set_vec64
(((c)->dp), ((a)->dp), ((a)->used), *pb++);

  /* Outer loop:  Digits of b */
  useda = MP_USED(a)((a)->used);
  usedb = MP_USED(b)((b)->used);
  for (ib = 1; ib < usedb; ib++) {
      mp_digit b_i = *pb++;

      /* Inner product:  Digits of a */
      if (constantTime || b_i)
          s_mpv_mul_d_add(MP_DIGITS(a), useda, b_i, MP_DIGITS(c) + ib)((mp_digit *)((c)->dp) + ib)[useda] = s_mpv_mul_add_vec64(
((c)->dp) + ib, ((a)->dp), useda, b_i);
      else
          MP_DIGIT(c, ib + useda)(c)->dp[(ib + useda)] = b_i;
  }

  if (!constantTime) {
      s_mp_clamp(c);
  }

  if (SIGN(a)((a)->sign) == SIGN(b)((b)->sign) || s_mp_cmp_d(c, 0) == MP_EQ0)
      SIGN(c)((c)->sign) = ZPOS0;
  else
      SIGN(c)((c)->sign) = NEG1;

906CLEANUP:
  mp_clear(&tmp);
  return res;
909} /* end smp_mulg() */

911/* }}} */

913/* {{{ mp_mul(a, b, c) */

915/*
mp_mul(a, b, c)

Compute c = a * b.  All parameters may be identical.
*/

921mp_err
922mp_mul(const mp_int *a, const mp_int *b, mp_int *c)
923{
  return s_mp_mulg(a, b, c, 0);
925} /* end mp_mul() */

927/* }}} */

929/* {{{ mp_mulCT(a, b, c) */

931/*
mp_mulCT(a, b, c)

Compute c = a * b. In constant time. Parameters may not be identical.
NOTE: a and b may be modified.
*/

938mp_err
939mp_mulCT(mp_int *a, mp_int *b, mp_int *c, mp_size setSize)
940{
  mp_err res;

  /* make the multiply values fixed length so multiply
   * doesn't leak the length. at this point all the
   * values are blinded, but once we finish we want the
   * output size to be hidden (so no clamping the out put) */
  MP_CHECKOK(s_mp_pad(a, setSize))if (0 > (res = (s_mp_pad(a, setSize)))) goto CLEANUP;
  MP_CHECKOK(s_mp_pad(b, setSize))if (0 > (res = (s_mp_pad(b, setSize)))) goto CLEANUP;
  MP_CHECKOK(s_mp_pad(c, 2 * setSize))if (0 > (res = (s_mp_pad(c, 2 * setSize)))) goto CLEANUP;
  MP_CHECKOK(s_mp_mulg(a, b, c, 1))if (0 > (res = (s_mp_mulg(a, b, c, 1)))) goto CLEANUP;
951CLEANUP:
  return res;
953} /* end mp_mulCT() */

955/* }}} */

957/* {{{ mp_sqr(a, sqr) */

959#if MP_SQUARE1
960/*
Computes the square of a.  This can be done more
efficiently than a general multiplication, because many of the
computation steps are redundant when squaring.  The inner product
step is a bit more complicated, but we save a fair number of
iterations of the multiplication loop.
*/

968/* sqr = a^2;   Caller provides both a and tmp; */
969mp_err
970mp_sqr(const mp_int *a, mp_int *sqr)
971{
  mp_digit *pa;
  mp_digit d;
  mp_err res;
  mp_size ix;
  mp_int tmp;
  int count;

  ARGCHK(a != NULL && sqr != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && sqr != ((void*)0)
) ? 1 : 0), __extension__ ({ if (a != ((void*)0) && sqr
 != ((void*)0)) ; else __assert_fail ("a != ((void*)0) && sqr != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 979
, __extension__ __PRETTY_FUNCTION__); }));

  if (a == sqr) {
      if ((res = mp_init_copy(&tmp, a)) != MP_OKAY0)
          return res;
      a = &tmp;
  } else {
      DIGITS(&tmp)((&tmp)->dp) = 0;
      res = MP_OKAY0;
  }

  ix = 2 * MP_USED(a)((a)->used);
  if (ix > MP_ALLOC(sqr)((sqr)->alloc)) {
      MP_USED(sqr)((sqr)->used) = 1;
      MP_CHECKOK(s_mp_grow(sqr, ix))if (0 > (res = (s_mp_grow(sqr, ix)))) goto CLEANUP;
  }
  MP_USED(sqr)((sqr)->used) = ix;
  MP_DIGIT(sqr, 0)(sqr)->dp[(0)] = 0;

998#ifdef NSS_USE_COMBA1
  if (IS_POWER_OF_2(MP_USED(a))((((a)->used)) && !((((a)->used)) & ((((a)->
used)) - 1)))) {
      if (MP_USED(a)((a)->used) == 4) {
          s_mp_sqr_comba_4(a, sqr);
          goto CLEANUP;
      }
      if (MP_USED(a)((a)->used) == 8) {
          s_mp_sqr_comba_8(a, sqr);
          goto CLEANUP;
      }
      if (MP_USED(a)((a)->used) == 16) {
          s_mp_sqr_comba_16(a, sqr);
          goto CLEANUP;
      }
      if (MP_USED(a)((a)->used) == 32) {
          s_mp_sqr_comba_32(a, sqr);
          goto CLEANUP;
      }
  }
1017#endif

  pa = MP_DIGITS(a)((a)->dp);
  count = MP_USED(a)((a)->used) - 1;
  if (count > 0) {
      d = *pa++;
      s_mpv_mul_d(pa, count, d, MP_DIGITS(sqr) + 1)((mp_digit *)((sqr)->dp) + 1)[count] = s_mpv_mul_set_vec64
(((sqr)->dp) + 1, pa, count, d);
      for (ix = 3; --count > 0; ix += 2) {
          d = *pa++;
          s_mpv_mul_d_add(pa, count, d, MP_DIGITS(sqr) + ix)((mp_digit *)((sqr)->dp) + ix)[count] = s_mpv_mul_add_vec64
(((sqr)->dp) + ix, pa, count, d);
      } /* for(ix ...) */
      MP_DIGIT(sqr, MP_USED(sqr) - 1)(sqr)->dp[(((sqr)->used) - 1)] = 0; /* above loop stopped short of this. */

      /* now sqr *= 2 */
      s_mp_mul_2(sqr);
  } else {
      MP_DIGIT(sqr, 1)(sqr)->dp[(1)] = 0;
  }

  /* now add the squares of the digits of a to sqr. */
  s_mpv_sqr_add_prop(MP_DIGITS(a)((a)->dp), MP_USED(a)((a)->used), MP_DIGITS(sqr)((sqr)->dp));

  SIGN(sqr)((sqr)->sign) = ZPOS0;
  s_mp_clamp(sqr);

1042CLEANUP:
  mp_clear(&tmp);
  return res;

1046} /* end mp_sqr() */
1047#endif

1049/* }}} */

1051/* {{{ mp_div(a, b, q, r) */

1053/*
mp_div(a, b, q, r)

Compute q = a / b and r = a mod b.  Input parameters may be re-used
as output parameters.  If q or r is NULL, that portion of the
computation will be discarded (although it will still be computed)
*/
1060mp_err
1061mp_div(const mp_int *a, const mp_int *b, mp_int *q, mp_int *r)
1062{
  mp_err res;
  mp_int *pQ, *pR;
  mp_int qtmp, rtmp, btmp;
  int cmp;
  mp_sign signA;
  mp_sign signB;

  ARGCHK(a != NULL && b != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1070
, __extension__ __PRETTY_FUNCTION__); }));

  signA = MP_SIGN(a)((a)->sign);
  signB = MP_SIGN(b)((b)->sign);

  if (mp_cmp_z(b) == MP_EQ0)
      return MP_RANGE-3;

  DIGITS(&qtmp)((&qtmp)->dp) = 0;
  DIGITS(&rtmp)((&rtmp)->dp) = 0;
  DIGITS(&btmp)((&btmp)->dp) = 0;

  /* Set up some temporaries... */
  if (!r || r == a || r == b) {
      MP_CHECKOK(mp_init_copy(&rtmp, a))if (0 > (res = (mp_init_copy(&rtmp, a)))) goto CLEANUP;
      pR = &rtmp;
  } else {
      MP_CHECKOK(mp_copy(a, r))if (0 > (res = (mp_copy(a, r)))) goto CLEANUP;
      pR = r;
  }

  if (!q || q == a || q == b) {
      MP_CHECKOK(mp_init_size(&qtmp, MP_USED(a)))if (0 > (res = (mp_init_size(&qtmp, ((a)->used)))))
 goto CLEANUP;
      pQ = &qtmp;
  } else {
      MP_CHECKOK(s_mp_pad(q, MP_USED(a)))if (0 > (res = (s_mp_pad(q, ((a)->used))))) goto CLEANUP;
      pQ = q;
      mp_zero(pQ);
  }

  /*
    If |a| <= |b|, we can compute the solution without division;
    otherwise, we actually do the work required.
   */
  if ((cmp = s_mp_cmp(a, b)) <= 0) {
      if (cmp) {
          /* r was set to a above. */
          mp_zero(pQ);
      } else {
          mp_set(pQ, 1);
          mp_zero(pR);
      }
  } else {
      MP_CHECKOK(mp_init_copy(&btmp, b))if (0 > (res = (mp_init_copy(&btmp, b)))) goto CLEANUP;
      MP_CHECKOK(s_mp_div(pR, &btmp, pQ))if (0 > (res = (s_mp_div(pR, &btmp, pQ)))) goto CLEANUP;
  }

  /* Compute the signs for the output  */
  MP_SIGN(pR)((pR)->sign) = signA;        /* Sr = Sa              */
  /* Sq = ZPOS if Sa == Sb */ /* Sq = NEG if Sa != Sb */
  MP_SIGN(pQ)((pQ)->sign) = (signA == signB) ? ZPOS0 : NEG1;

  if (s_mp_cmp_d(pQ, 0) == MP_EQ0)
      SIGN(pQ)((pQ)->sign) = ZPOS0;
  if (s_mp_cmp_d(pR, 0) == MP_EQ0)
      SIGN(pR)((pR)->sign) = ZPOS0;

  /* Copy output, if it is needed      */
  if (q && q != pQ)
      s_mp_exch(pQ, q);

  if (r && r != pR)
      s_mp_exch(pR, r);

1134CLEANUP:
  mp_clear(&btmp);
  mp_clear(&rtmp);
  mp_clear(&qtmp);

  return res;

1141} /* end mp_div() */

1143/* }}} */

1145/* {{{ mp_div_2d(a, d, q, r) */

1147mp_err
1148mp_div_2d(const mp_int *a, mp_digit d, mp_int *q, mp_int *r)
1149{
  mp_err res;

  ARGCHK(a != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (a != ((void*)0)) ; else __assert_fail ("a != ((void*)0)", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 1152, __extension__ __PRETTY_FUNCTION__); }));

  if (q) {
      if ((res = mp_copy(a, q)) != MP_OKAY0)
          return res;
  }
  if (r) {
      if ((res = mp_copy(a, r)) != MP_OKAY0)
          return res;
  }
  if (q) {
      s_mp_div_2d(q, d);
  }
  if (r) {
      s_mp_mod_2d(r, d);
  }

  return MP_OKAY0;

1171} /* end mp_div_2d() */

1173/* }}} */

1175/* {{{ mp_expt(a, b, c) */

1177/*
mp_expt(a, b, c)

Compute c = a ** b, that is, raise a to the b power.  Uses a
standard iterative square-and-multiply technique.
*/

1184mp_err
1185mp_expt(mp_int *a, mp_int *b, mp_int *c)
1186{
  mp_int s, x;
  mp_err res;
  mp_digit d;
  unsigned int dig, bit;

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1192
, __extension__ __PRETTY_FUNCTION__); }));

  if (mp_cmp_z(b) < 0)
      return MP_RANGE-3;

  if ((res = mp_init(&s)) != MP_OKAY0)
      return res;

  mp_set(&s, 1);

  if ((res = mp_init_copy(&x, a)) != MP_OKAY0)
      goto X;

  /* Loop over low-order digits in ascending order */
  for (dig = 0; dig < (USED(b)((b)->used) - 1); dig++) {
      d = DIGIT(b, dig)(b)->dp[(dig)];

      /* Loop over bits of each non-maximal digit */
      for (bit = 0; bit < DIGIT_BIT(8 * sizeof(mp_digit)); bit++) {
          if (d & 1) {
              if ((res = s_mp_mul(&s, &x)) != MP_OKAY0)
                  goto CLEANUP;
          }

          d >>= 1;

          if ((res = s_mp_sqr(&x)) != MP_OKAY0)
              goto CLEANUP;
      }
  }

  /* Consider now the last digit... */
  d = DIGIT(b, dig)(b)->dp[(dig)];

  while (d) {
      if (d & 1) {
          if ((res = s_mp_mul(&s, &x)) != MP_OKAY0)
              goto CLEANUP;
      }

      d >>= 1;

      if ((res = s_mp_sqr(&x)) != MP_OKAY0)
          goto CLEANUP;
  }

  if (mp_iseven(b))
      SIGN(&s)((&s)->sign) = SIGN(a)((a)->sign);

  res = mp_copy(&s, c);

1243CLEANUP:
  mp_clear(&x);
1245X:
  mp_clear(&s);

  return res;

1250} /* end mp_expt() */

1252/* }}} */

1254/* {{{ mp_2expt(a, k) */

1256/* Compute a = 2^k */

1258mp_err
1259mp_2expt(mp_int *a, mp_digit k)
1260{
  ARGCHK(a != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (a != ((void*)0)) ; else __assert_fail ("a != ((void*)0)", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 1261, __extension__ __PRETTY_FUNCTION__); }));

  return s_mp_2expt(a, k);

1265} /* end mp_2expt() */

1267/* }}} */

1269/* {{{ mp_mod(a, m, c) */

1271/*
mp_mod(a, m, c)

Compute c = a (mod m).  Result will always be 0 <= c < m.
*/

1277mp_err
1278mp_mod(const mp_int *a, const mp_int *m, mp_int *c)
1279{
  mp_err res;
  int mag;

  ARGCHK(a != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && m != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && m != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1283
, __extension__ __PRETTY_FUNCTION__); }));

  if (SIGN(m)((m)->sign) == NEG1)
      return MP_RANGE-3;

  /*
   If |a| > m, we need to divide to get the remainder and take the
   absolute value.

   If |a| < m, we don't need to do any division, just copy and adjust
   the sign (if a is negative).

   If |a| == m, we can simply set the result to zero.

   This order is intended to minimize the average path length of the
   comparison chain on common workloads -- the most frequent cases are
   that |a| != m, so we do those first.
   */
  if ((mag = s_mp_cmp(a, m)) > 0) {
      if ((res = mp_div(a, m, NULL((void*)0), c)) != MP_OKAY0)
          return res;

      if (SIGN(c)((c)->sign) == NEG1) {
          if ((res = mp_add(c, m, c)) != MP_OKAY0)
              return res;
      }

  } else if (mag < 0) {
      if ((res = mp_copy(a, c)) != MP_OKAY0)
          return res;

      if (mp_cmp_z(a) < 0) {
          if ((res = mp_add(c, m, c)) != MP_OKAY0)
              return res;
      }

  } else {
      mp_zero(c);
  }

  return MP_OKAY0;

1325} /* end mp_mod() */

1327/* }}} */

1329/* {{{ s_mp_subCT_d(a, b, borrow, c) */

1331/*
s_mp_subCT_d(a, b, borrow, c)

Compute c = (a -b) - subtract in constant time. returns borrow
*/
1336mp_digit
1337s_mp_subCT_d(mp_digit a, mp_digit b, mp_digit borrow, mp_digit *ret)
1338{
  *ret = a - b - borrow;
  return MP_CT_LTU(a, *ret)((((mp_digit)((mp_digit)((a) - (*ret)) >> ((8 * sizeof(
mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a) ^ (*ret)) >>
 ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit)((mp_digit
)((a) - (*ret)) >> ((8 * sizeof(mp_digit)) - 1)))) ^ ((
((mp_digit)((mp_digit)(*ret) >> ((8 * sizeof(mp_digit))
 - 1)))))))) | (MP_CT_EQ(a, *ret)(((mp_digit)1) ^ ((mp_digit)((mp_digit)(((((a) ^ (*ret))) | (
((mp_digit)0) - (((a) ^ (*ret)))))) >> ((8 * sizeof(mp_digit
)) - 1)))) & borrow);
1341} /*  s_mp_subCT_d() */

1343/* }}} */

1345/* {{{ mp_subCT(a, b, ret, borrow) */

1347/* return ret= a - b and borrow in borrow. done in constant time.
* b could be modified.
*/
1350mp_err
1351mp_subCT(const mp_int *a, mp_int *b, mp_int *ret, mp_digit *borrow)
1352{
  mp_size used_a = MP_USED(a)((a)->used);
  mp_size i;
  mp_err res;

  MP_CHECKOK(s_mp_pad(b, used_a))if (0 > (res = (s_mp_pad(b, used_a)))) goto CLEANUP;
  MP_CHECKOK(s_mp_pad(ret, used_a))if (0 > (res = (s_mp_pad(ret, used_a)))) goto CLEANUP;
  *borrow = 0;
  for (i = 0; i < used_a; i++) {
      *borrow = s_mp_subCT_d(MP_DIGIT(a, i)(a)->dp[(i)], MP_DIGIT(b, i)(b)->dp[(i)], *borrow,
                             &MP_DIGIT(ret, i)(ret)->dp[(i)]);
  }

  res = MP_OKAY0;
1366CLEANUP:
  return res;
1368} /*  end mp_subCT() */

1370/* }}} */

1372/* {{{ mp_selectCT(cond, a, b, ret) */

1374/*
* return ret= cond ? a : b; cond should be either 0 or 1
*/
1377mp_err
1378mp_selectCT(mp_digit cond, const mp_int *a, const mp_int *b, mp_int *ret)
1379{
  mp_size used_a = MP_USED(a)((a)->used);
  mp_err res;
  mp_size i;

  cond *= MP_DIGIT_MAX(9223372036854775807L *2UL+1UL);

  /* we currently require these to be equal on input,
   * we could use pad to extend one of them, but that might
   * leak data as it wouldn't be constant time */
  if (used_a != MP_USED(b)((b)->used)) {
      return MP_BADARG-4;
  }

  MP_CHECKOK(s_mp_pad(ret, used_a))if (0 > (res = (s_mp_pad(ret, used_a)))) goto CLEANUP;
  for (i = 0; i < used_a; i++) {
      MP_DIGIT(ret, i)(ret)->dp[(i)] = MP_CT_SEL_DIGIT(cond, MP_DIGIT(a, i), MP_DIGIT(b, i))(((b)->dp[(i)]) ^ ((cond) & (((b)->dp[(i)]) ^ ((a)->
dp[(i)]))));
  }
  res = MP_OKAY0;
1398CLEANUP:
  return res;
1400} /* end mp_selectCT() */

1402/* {{{ mp_reduceCT(a, m, c) */

1404/*
mp_reduceCT(a, m, c)

Compute c = aR^-1 (mod m) in constant time.
 input should be in montgomery form. If input is the
 result of a montgomery multiply then out put will be
 in mongomery form.
 Result will be reduced to MP_USED(m), but not be
 clamped.
*/

1415mp_err
1416mp_reduceCT(const mp_int *a, const mp_int *m, mp_digit n0i, mp_int *c)
1417{
  mp_size used_m = MP_USED(m)((m)->used);
  mp_size used_c = used_m * 2 + 1;
  mp_digit *m_digits, *c_digits;
  mp_size i;
  mp_digit borrow, carry;
  mp_err res;
  mp_int sub;

  MP_DIGITS(&sub)((&sub)->dp) = 0;
  MP_CHECKOK(mp_init_size(&sub, used_m))if (0 > (res = (mp_init_size(&sub, used_m)))) goto CLEANUP;

  if (a != c) {
      MP_CHECKOK(mp_copy(a, c))if (0 > (res = (mp_copy(a, c)))) goto CLEANUP;
  }
  MP_CHECKOK(s_mp_pad(c, used_c))if (0 > (res = (s_mp_pad(c, used_c)))) goto CLEANUP;
  m_digits = MP_DIGITS(m)((m)->dp);
  c_digits = MP_DIGITS(c)((c)->dp);
  for (i = 0; i < used_m; i++) {
      mp_digit m_i = MP_DIGIT(c, i)(c)->dp[(i)] * n0i;
      s_mpv_mul_d_add_propCT(m_digits, used_m, m_i, c_digits++, used_c--);
  }
  s_mp_rshd(c, used_m);
  /* MP_USED(c) should be used_m+1 with the high word being any carry
   * from the previous multiply, save that carry and drop the high
   * word for the substraction below */
  carry = MP_DIGIT(c, used_m)(c)->dp[(used_m)];
  MP_DIGIT(c, used_m)(c)->dp[(used_m)] = 0;
  MP_USED(c)((c)->used) = used_m;
  /* mp_subCT wants c and m to be the same size, we've already
   * guarrenteed that in the previous statement, so mp_subCT won't actually
   * modify m, so it's safe to recast */
  MP_CHECKOK(mp_subCT(c, (mp_int *)m, &sub, &borrow))if (0 > (res = (mp_subCT(c, (mp_int *)m, &sub, &borrow
)))) goto CLEANUP;

  /* we return c-m if c >= m no borrow or there was a borrow and a carry */
  MP_CHECKOK(mp_selectCT(borrow ^ carry, c, &sub, c))if (0 > (res = (mp_selectCT(borrow ^ carry, c, &sub, c
)))) goto CLEANUP;
  res = MP_OKAY0;
1454CLEANUP:
  mp_clear(&sub);
  return res;
1457} /* end mp_reduceCT() */

1459/* }}} */

1461/* {{{ mp_mod_d(a, d, c) */

1463/*
mp_mod_d(a, d, c)

Compute c = a (mod d).  Result will always be 0 <= c < d
*/
1468mp_err
1469mp_mod_d(const mp_int *a, mp_digit d, mp_digit *c)
1470{
  mp_err res;
  mp_digit rem;

  ARGCHK(a != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && c != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && c !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1474
, __extension__ __PRETTY_FUNCTION__); }));

  if (s_mp_cmp_d(a, d) > 0) {
      if ((res = mp_div_d(a, d, NULL((void*)0), &rem)) != MP_OKAY0)
          return res;

  } else {
      if (SIGN(a)((a)->sign) == NEG1)
          rem = d - DIGIT(a, 0)(a)->dp[(0)];
      else
          rem = DIGIT(a, 0)(a)->dp[(0)];
  }

  if (c)
      *c = rem;

  return MP_OKAY0;

1492} /* end mp_mod_d() */

1494/* }}} */

1496/* }}} */

1498/*------------------------------------------------------------------------*/
1499/* {{{ Modular arithmetic */

1501#if MP_MODARITH1
1502/* {{{ mp_addmod(a, b, m, c) */

1504/*
mp_addmod(a, b, m, c)

Compute c = (a + b) mod m
*/

1510mp_err
1511mp_addmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c)
1512{
  mp_err res;

  ARGCHK(a != NULL && b != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 m != ((void*)0) && c != ((void*)0)) ? 1 : 0), __extension__
 ({ if (a != ((void*)0) && b != ((void*)0) &&
 m != ((void*)0) && c != ((void*)0)) ; else __assert_fail
 ("a != ((void*)0) && b != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1515
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_add(a, b, c)) != MP_OKAY0)
      return res;
  if ((res = mp_mod(c, m, c)) != MP_OKAY0)
      return res;

  return MP_OKAY0;
1523}

1525/* }}} */

1527/* {{{ mp_submod(a, b, m, c) */

1529/*
mp_submod(a, b, m, c)

Compute c = (a - b) mod m
*/

1535mp_err
1536mp_submod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c)
1537{
  mp_err res;

  ARGCHK(a != NULL && b != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 m != ((void*)0) && c != ((void*)0)) ? 1 : 0), __extension__
 ({ if (a != ((void*)0) && b != ((void*)0) &&
 m != ((void*)0) && c != ((void*)0)) ; else __assert_fail
 ("a != ((void*)0) && b != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1540
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_sub(a, b, c)) != MP_OKAY0)
      return res;
  if ((res = mp_mod(c, m, c)) != MP_OKAY0)
      return res;

  return MP_OKAY0;
1548}

1550/* }}} */

1552/* {{{ mp_mulmod(a, b, m, c) */

1554/*
mp_mulmod(a, b, m, c)

Compute c = (a * b) mod m
*/

1560mp_err
1561mp_mulmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c)
1562{
  mp_err res;

  ARGCHK(a != NULL && b != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 m != ((void*)0) && c != ((void*)0)) ? 1 : 0), __extension__
 ({ if (a != ((void*)0) && b != ((void*)0) &&
 m != ((void*)0) && c != ((void*)0)) ; else __assert_fail
 ("a != ((void*)0) && b != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1565
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_mul(a, b, c)) != MP_OKAY0)
      return res;
  if ((res = mp_mod(c, m, c)) != MP_OKAY0)
      return res;

  return MP_OKAY0;
1573}

1575/* }}} */

1577/* {{{ mp_mulmontmodCT(a, b, m, c) */

1579/*
mp_mulmontmodCT(a, b, m, c)

Compute c = (a * b) mod m in constant time wrt a and b. either a or b
should be in montgomery form and the output is native. If both a and b
are in montgomery form, then the output will also be in montgomery form
and can be recovered with an mp_reduceCT call.
NOTE: a and b may be modified.
*/

1589mp_err
1590mp_mulmontmodCT(mp_int *a, mp_int *b, const mp_int *m, mp_digit n0i,
              mp_int *c)
1592{
  mp_err res;

  ARGCHK(a != NULL && b != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 m != ((void*)0) && c != ((void*)0)) ? 1 : 0), __extension__
 ({ if (a != ((void*)0) && b != ((void*)0) &&
 m != ((void*)0) && c != ((void*)0)) ; else __assert_fail
 ("a != ((void*)0) && b != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1595
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_mulCT(a, b, c, MP_USED(m)((m)->used))) != MP_OKAY0)
      return res;

  if ((res = mp_reduceCT(c, m, n0i, c)) != MP_OKAY0)
      return res;

  return MP_OKAY0;
1604}

1606/* }}} */

1608/* {{{ mp_sqrmod(a, m, c) */

1610#if MP_SQUARE1
1611mp_err
1612mp_sqrmod(const mp_int *a, const mp_int *m, mp_int *c)
1613{
  mp_err res;

  ARGCHK(a != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && m != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && m != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1616
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_sqr(a, c)) != MP_OKAY0)
      return res;
  if ((res = mp_mod(c, m, c)) != MP_OKAY0)
      return res;

  return MP_OKAY0;

1625} /* end mp_sqrmod() */
1626#endif

1628/* }}} */

1630/* {{{ s_mp_exptmod(a, b, m, c) */

1632/*
s_mp_exptmod(a, b, m, c)

Compute c = (a ** b) mod m.  Uses a standard square-and-multiply
method with modular reductions at each step. (This is basically the
same code as mp_expt(), except for the addition of the reductions)

The modular reductions are done using Barrett's algorithm (see
s_mp_reduce() below for details)
*/

1643mp_err
1644s_mp_exptmod(const mp_int *a, const mp_int *b, const mp_int *m, mp_int *c)
1645{
  mp_int s, x, mu;
  mp_err res;
  mp_digit d;
  unsigned int dig, bit;

  ARGCHK(a != NULL && b != NULL && c != NULL && m != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0) && m != ((void*)0)) ? 1 : 0), __extension__
 ({ if (a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0) && m != ((void*)0)) ; else __assert_fail
 ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0) && m != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1651
, __extension__ __PRETTY_FUNCTION__); }));

  if (mp_cmp_z(b) < 0 || mp_cmp_z(m) <= 0)
      return MP_RANGE-3;

  if ((res = mp_init(&s)) != MP_OKAY0)
      return res;
  if ((res = mp_init_copy(&x, a)) != MP_OKAY0 ||
      (res = mp_mod(&x, m, &x)) != MP_OKAY0)
      goto X;
  if ((res = mp_init(&mu)) != MP_OKAY0)
      goto MU;

  mp_set(&s, 1);

  /* mu = b^2k / m */
  if ((res = s_mp_add_d(&mu, 1)) != MP_OKAY0)
      goto CLEANUP;
  if ((res = s_mp_lshd(&mu, 2 * USED(m)((m)->used))) != MP_OKAY0)
      goto CLEANUP;
  if ((res = mp_div(&mu, m, &mu, NULL((void*)0))) != MP_OKAY0)
      goto CLEANUP;

  /* Loop over digits of b in ascending order, except highest order */
  for (dig = 0; dig < (USED(b)((b)->used) - 1); dig++) {
      d = DIGIT(b, dig)(b)->dp[(dig)];

      /* Loop over the bits of the lower-order digits */
      for (bit = 0; bit < DIGIT_BIT(8 * sizeof(mp_digit)); bit++) {
          if (d & 1) {
              if ((res = s_mp_mul(&s, &x)) != MP_OKAY0)
                  goto CLEANUP;
              if ((res = s_mp_reduce(&s, m, &mu)) != MP_OKAY0)
                  goto CLEANUP;
          }

          d >>= 1;

          if ((res = s_mp_sqr(&x)) != MP_OKAY0)
              goto CLEANUP;
          if ((res = s_mp_reduce(&x, m, &mu)) != MP_OKAY0)
              goto CLEANUP;
      }
  }

  /* Now do the last digit... */
  d = DIGIT(b, dig)(b)->dp[(dig)];

  while (d) {
      if (d & 1) {
          if ((res = s_mp_mul(&s, &x)) != MP_OKAY0)
              goto CLEANUP;
          if ((res = s_mp_reduce(&s, m, &mu)) != MP_OKAY0)
              goto CLEANUP;
      }

      d >>= 1;

      if ((res = s_mp_sqr(&x)) != MP_OKAY0)
          goto CLEANUP;
      if ((res = s_mp_reduce(&x, m, &mu)) != MP_OKAY0)
          goto CLEANUP;
  }

  s_mp_exch(&s, c);

1717CLEANUP:
  mp_clear(&mu);
1719MU:
  mp_clear(&x);
1721X:
  mp_clear(&s);

  return res;

1726} /* end s_mp_exptmod() */

1728/* }}} */

1730/* {{{ mp_exptmod_d(a, d, m, c) */

1732mp_err
1733mp_exptmod_d(const mp_int *a, mp_digit d, const mp_int *m, mp_int *c)
1734{
  mp_int s, x;
  mp_err res;

  ARGCHK(a != NULL && c != NULL && m != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && c != ((void*)0) &&
 m != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && c != ((void*)0) && m != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && c != ((void*)0) && m != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1738
, __extension__ __PRETTY_FUNCTION__); }));

  if ((res = mp_init(&s)) != MP_OKAY0)
      return res;
  if ((res = mp_init_copy(&x, a)) != MP_OKAY0)
      goto X;

  mp_set(&s, 1);

  while (d != 0) {
      if (d & 1) {
          if ((res = s_mp_mul(&s, &x)) != MP_OKAY0 ||
              (res = mp_mod(&s, m, &s)) != MP_OKAY0)
              goto CLEANUP;
      }

      d /= 2;

      if ((res = s_mp_sqr(&x)) != MP_OKAY0 ||
          (res = mp_mod(&x, m, &x)) != MP_OKAY0)
          goto CLEANUP;
  }

  s_mp_exch(&s, c);

1763CLEANUP:
  mp_clear(&x);
1765X:
  mp_clear(&s);

  return res;

1770} /* end mp_exptmod_d() */

1772/* }}} */
1773#endif /* if MP_MODARITH */

1775/* }}} */

1777/*------------------------------------------------------------------------*/
1778/* {{{ Comparison functions */

1780/* {{{ mp_cmp_z(a) */

1782/*
mp_cmp_z(a)

Compare a <=> 0.  Returns <0 if a<0, 0 if a=0, >0 if a>0.
*/

1788int
1789mp_cmp_z(const mp_int *a)
1790{
  ARGMPCHK(a != NULL)((void) sizeof ((a != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (a != ((void*)0)) ; else __assert_fail ("a != ((void*)0)", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 1791, __extension__ __PRETTY_FUNCTION__); }));

  if (SIGN(a)((a)->sign) == NEG1)
      return MP_LT-1;
  else if (USED(a)((a)->used) == 1 && DIGIT(a, 0)(a)->dp[(0)] == 0)
      return MP_EQ0;
  else
      return MP_GT1;

1800} /* end mp_cmp_z() */

1802/* }}} */

1804/* {{{ mp_cmp_d(a, d) */

1806/*
mp_cmp_d(a, d)

Compare a <=> d.  Returns <0 if a<d, 0 if a=d, >0 if a>d
*/

1812int
1813mp_cmp_d(const mp_int *a, mp_digit d)
1814{
  ARGCHK(a != NULL, MP_EQ)((void) sizeof ((a != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (a != ((void*)0)) ; else __assert_fail ("a != ((void*)0)", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 1815, __extension__ __PRETTY_FUNCTION__); }));

  if (SIGN(a)((a)->sign) == NEG1)
      return MP_LT-1;

  return s_mp_cmp_d(a, d);

1822} /* end mp_cmp_d() */

1824/* }}} */

1826/* {{{ mp_cmp(a, b) */

1828int
1829mp_cmp(const mp_int *a, const mp_int *b)
1830{
  ARGCHK(a != NULL && b != NULL, MP_EQ)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1831
, __extension__ __PRETTY_FUNCTION__); }));

  if (SIGN(a)((a)->sign) == SIGN(b)((b)->sign)) {
      int mag;

      if ((mag = s_mp_cmp(a, b)) == MP_EQ0)
          return MP_EQ0;

      if (SIGN(a)((a)->sign) == ZPOS0)
          return mag;
      else
          return -mag;

  } else if (SIGN(a)((a)->sign) == ZPOS0) {
      return MP_GT1;
  } else {
      return MP_LT-1;
  }

1850} /* end mp_cmp() */

1852/* }}} */

1854/* {{{ mp_cmp_mag(a, b) */

1856/*
mp_cmp_mag(a, b)

Compares |a| <=> |b|, and returns an appropriate comparison result
*/

1862int
1863mp_cmp_mag(const mp_int *a, const mp_int *b)
1864{
  ARGCHK(a != NULL && b != NULL, MP_EQ)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1865
, __extension__ __PRETTY_FUNCTION__); }));

  return s_mp_cmp(a, b);

1869} /* end mp_cmp_mag() */

1871/* }}} */

1873/* {{{ mp_isodd(a) */

1875/*
mp_isodd(a)

Returns a true (non-zero) value if a is odd, false (zero) otherwise.
*/
1880int
1881mp_isodd(const mp_int *a)
1882{
  ARGMPCHK(a != NULL)((void) sizeof ((a != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (a != ((void*)0)) ; else __assert_fail ("a != ((void*)0)", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 1883, __extension__ __PRETTY_FUNCTION__); }));

  return (int)(DIGIT(a, 0)(a)->dp[(0)] & 1);

1887} /* end mp_isodd() */

1889/* }}} */

1891/* {{{ mp_iseven(a) */

1893int
1894mp_iseven(const mp_int *a)
1895{
  return !mp_isodd(a);

1898} /* end mp_iseven() */

1900/* }}} */

1902/* }}} */

1904/*------------------------------------------------------------------------*/
1905/* {{{ Number theoretic functions */

1907/* {{{ mp_gcd(a, b, c) */

1909/*
Computes the GCD using the constant-time algorithm
by Bernstein and Yang (https://eprint.iacr.org/2019/266)
"Fast constant-time gcd computation and modular inversion"
*/
1914mp_err
1915mp_gcd(mp_int *a, mp_int *b, mp_int *c)
1916{
  mp_err res;
  mp_digit cond = 0, mask = 0;
  mp_int g, temp, f;
  int i, j, m, bit = 1, delta = 1, shifts = 0, last = -1;
  mp_size top, flen, glen;
  mp_int *clear[3];

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 1924
, __extension__ __PRETTY_FUNCTION__); }));
10
←
Taking true branch→
  /*
  Early exit if either of the inputs is zero.
  Caller is responsible for the proper handling of inputs.
  */
  if (mp_cmp_z(a) == MP_EQ0) {
11
←
Taking false branch→
      res = mp_copy(b, c);
      SIGN(c)((c)->sign) = ZPOS0;
      return res;
  } else if (mp_cmp_z(b) == MP_EQ0) {
12
←
Taking false branch→
      res = mp_copy(a, c);
      SIGN(c)((c)->sign) = ZPOS0;
      return res;
  }

  MP_CHECKOK(mp_init(&temp))if (0 > (res = (mp_init(&temp)))) goto CLEANUP;
13
←
Taking false branch→
  clear[++last] = &temp;
  MP_CHECKOK(mp_init_copy(&g, a))if (0 > (res = (mp_init_copy(&g, a)))) goto CLEANUP;
14
←
Calling 'mp_init_copy'→
19
←
Returning from 'mp_init_copy'→
20
←
Taking false branch→
  clear[++last] = &g;
  MP_CHECKOK(mp_init_copy(&f, b))if (0 > (res = (mp_init_copy(&f, b)))) goto CLEANUP;
21
←
Taking false branch→
  clear[++last] = &f;

  /*
  For even case compute the number of
  shared powers of 2 in f and g.
  */
  for (i = 0; i < USED(&f)((&f)->used) && i < USED(&g)((&g)->used); i++) {
22
←
Assuming 'i' is < field 'used'→
23
←
The right operand of '<' is a garbage value
      mask = ~(DIGIT(&f, i)(&f)->dp[(i)] | DIGIT(&g, i)(&g)->dp[(i)]);
      for (j = 0; j < MP_DIGIT_BIT(8 * sizeof(mp_digit)); j++) {
          bit &= mask;
          shifts += bit;
          mask >>= 1;
      }
  }
  /* Reduce to the odd case by removing the powers of 2. */
  s_mp_div_2d(&f, shifts);
  s_mp_div_2d(&g, shifts);

  /* Allocate to the size of largest mp_int. */
  top = (mp_size)1 + ((USED(&f)((&f)->used) >= USED(&g)((&g)->used)) ? USED(&f)((&f)->used) : USED(&g)((&g)->used));
  MP_CHECKOK(s_mp_grow(&f, top))if (0 > (res = (s_mp_grow(&f, top)))) goto CLEANUP;
  MP_CHECKOK(s_mp_grow(&g, top))if (0 > (res = (s_mp_grow(&g, top)))) goto CLEANUP;
  MP_CHECKOK(s_mp_grow(&temp, top))if (0 > (res = (s_mp_grow(&temp, top)))) goto CLEANUP;

  /* Make sure f contains the odd value. */
  MP_CHECKOK(mp_cswap((~DIGIT(&f, 0) & 1), &f, &g, top))if (0 > (res = (mp_cswap((~(&f)->dp[(0)] & 1), &
f, &g, top)))) goto CLEANUP;

  /* Upper bound for the total iterations. */
  flen = mpl_significant_bits(&f);
  glen = mpl_significant_bits(&g);
  m = 4 + 3 * ((flen >= glen) ? flen : glen);

1976#if defined(_MSC_VER)
1977#pragma warning(push)
1978#pragma warning(disable : 4146) // Thanks MSVC, we know what we're negating an unsigned mp_digit
1979#endif

  for (i = 0; i < m; i++) {
      /* Step 1: conditional swap. */
      /* Set cond if delta > 0 and g is odd. */
      cond = (-delta >> (8 * sizeof(delta) - 1)) & DIGIT(&g, 0)(&g)->dp[(0)] & 1;
      /* If cond is set replace (delta,f) with (-delta,-f). */
      delta = (-cond & -delta) | ((cond - 1) & delta);
      SIGN(&f)((&f)->sign) ^= cond;
      /* If cond is set swap f with g. */
      MP_CHECKOK(mp_cswap(cond, &f, &g, top))if (0 > (res = (mp_cswap(cond, &f, &g, top)))) goto
 CLEANUP;

      /* Step 2: elemination. */
      /* Update delta. */
      delta++;
      /* If g is odd, right shift (g+f) else right shift g. */
      MP_CHECKOK(mp_add(&g, &f, &temp))if (0 > (res = (mp_add(&g, &f, &temp)))) goto CLEANUP;
      MP_CHECKOK(mp_cswap((DIGIT(&g, 0) & 1), &g, &temp, top))if (0 > (res = (mp_cswap(((&g)->dp[(0)] & 1), &
g, &temp, top)))) goto CLEANUP;
      s_mp_div_2(&g);
  }

2000#if defined(_MSC_VER)
2001#pragma warning(pop)
2002#endif

  /* GCD is in f, take the absolute value. */
  SIGN(&f)((&f)->sign) = ZPOS0;

  /* Add back the removed powers of 2. */
  MP_CHECKOK(s_mp_mul_2d(&f, shifts))if (0 > (res = (s_mp_mul_2d(&f, shifts)))) goto CLEANUP;

  MP_CHECKOK(mp_copy(&f, c))if (0 > (res = (mp_copy(&f, c)))) goto CLEANUP;

2012CLEANUP:
  while (last >= 0)
      mp_clear(clear[last--]);
  return res;
2016} /* end mp_gcd() */

2018/* }}} */

2020/* {{{ mp_lcm(a, b, c) */

2022/* We compute the least common multiple using the rule:

 ab = [a, b](a, b)

 ... by computing the product, and dividing out the gcd.
*/

2029mp_err
2030mp_lcm(mp_int *a, mp_int *b, mp_int *c)
2031{
  mp_int gcd, prod;
  mp_err res;

  ARGCHK(a != NULL && b != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && b != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && b != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2035
, __extension__ __PRETTY_FUNCTION__); }));
1
Assuming 'a' is not equal to null→
2
←
Assuming 'b' is not equal to null→
3
←
Assuming 'c' is not equal to null→
4
←
Taking true branch→

  /* Set up temporaries */
  if ((res = mp_init(&gcd)) != MP_OKAY0)
5
←
Taking false branch→
      return res;
  if ((res = mp_init(&prod)) != MP_OKAY0)
6
←
Taking false branch→
      goto GCD;

  if ((res = mp_mul(a, b, &prod)) != MP_OKAY0)
7
←
Assuming the condition is false→
8
←
Taking false branch→
      goto CLEANUP;
  if ((res = mp_gcd(a, b, &gcd)) != MP_OKAY0)
9
←
Calling 'mp_gcd'→
      goto CLEANUP;

  res = mp_div(&prod, &gcd, c, NULL((void*)0));

2050CLEANUP:
  mp_clear(&prod);
2052GCD:
  mp_clear(&gcd);

  return res;

2057} /* end mp_lcm() */

2059/* }}} */

2061/* {{{ mp_xgcd(a, b, g, x, y) */

2063/*
mp_xgcd(a, b, g, x, y)

Compute g = (a, b) and values x and y satisfying Bezout's identity
(that is, ax + by = g).  This uses the binary extended GCD algorithm
based on the Stein algorithm used for mp_gcd()
See algorithm 14.61 in Handbook of Applied Cryptogrpahy.
*/

2072mp_err
2073mp_xgcd(const mp_int *a, const mp_int *b, mp_int *g, mp_int *x, mp_int *y)
2074{
  mp_int gx, xc, yc, u, v, A, B, C, D;
  mp_int *clean[9];
  mp_err res;
  int last = -1;

  if (mp_cmp_z(b) == 0)
      return MP_RANGE-3;

  /* Initialize all these variables we need */
  MP_CHECKOK(mp_init(&u))if (0 > (res = (mp_init(&u)))) goto CLEANUP;
  clean[++last] = &u;
  MP_CHECKOK(mp_init(&v))if (0 > (res = (mp_init(&v)))) goto CLEANUP;
  clean[++last] = &v;
  MP_CHECKOK(mp_init(&gx))if (0 > (res = (mp_init(&gx)))) goto CLEANUP;
  clean[++last] = &gx;
  MP_CHECKOK(mp_init(&A))if (0 > (res = (mp_init(&A)))) goto CLEANUP;
  clean[++last] = &A;
  MP_CHECKOK(mp_init(&B))if (0 > (res = (mp_init(&B)))) goto CLEANUP;
  clean[++last] = &B;
  MP_CHECKOK(mp_init(&C))if (0 > (res = (mp_init(&C)))) goto CLEANUP;
  clean[++last] = &C;
  MP_CHECKOK(mp_init(&D))if (0 > (res = (mp_init(&D)))) goto CLEANUP;
  clean[++last] = &D;
  MP_CHECKOK(mp_init_copy(&xc, a))if (0 > (res = (mp_init_copy(&xc, a)))) goto CLEANUP;
  clean[++last] = &xc;
  mp_abs(&xc, &xc);
  MP_CHECKOK(mp_init_copy(&yc, b))if (0 > (res = (mp_init_copy(&yc, b)))) goto CLEANUP;
  clean[++last] = &yc;
  mp_abs(&yc, &yc);

  mp_set(&gx, 1);

  /* Divide by two until at least one of them is odd */
  while (mp_iseven(&xc) && mp_iseven(&yc)) {
      mp_size nx = mp_trailing_zeros(&xc);
      mp_size ny = mp_trailing_zeros(&yc);
      mp_size n = MP_MIN(nx, ny)(((nx) < (ny)) ? (nx) : (ny));
      s_mp_div_2d(&xc, n);
      s_mp_div_2d(&yc, n);
      MP_CHECKOK(s_mp_mul_2d(&gx, n))if (0 > (res = (s_mp_mul_2d(&gx, n)))) goto CLEANUP;
  }

  MP_CHECKOK(mp_copy(&xc, &u))if (0 > (res = (mp_copy(&xc, &u)))) goto CLEANUP;
  MP_CHECKOK(mp_copy(&yc, &v))if (0 > (res = (mp_copy(&yc, &v)))) goto CLEANUP;
  mp_set(&A, 1);
  mp_set(&D, 1);

  /* Loop through binary GCD algorithm */
  do {
      while (mp_iseven(&u)) {
          s_mp_div_2(&u);

          if (mp_iseven(&A) && mp_iseven(&B)) {
              s_mp_div_2(&A);
              s_mp_div_2(&B);
          } else {
              MP_CHECKOK(mp_add(&A, &yc, &A))if (0 > (res = (mp_add(&A, &yc, &A)))) goto CLEANUP;
              s_mp_div_2(&A);
              MP_CHECKOK(mp_sub(&B, &xc, &B))if (0 > (res = (mp_sub(&B, &xc, &B)))) goto CLEANUP;
              s_mp_div_2(&B);
          }
      }

      while (mp_iseven(&v)) {
          s_mp_div_2(&v);

          if (mp_iseven(&C) && mp_iseven(&D)) {
              s_mp_div_2(&C);
              s_mp_div_2(&D);
          } else {
              MP_CHECKOK(mp_add(&C, &yc, &C))if (0 > (res = (mp_add(&C, &yc, &C)))) goto CLEANUP;
              s_mp_div_2(&C);
              MP_CHECKOK(mp_sub(&D, &xc, &D))if (0 > (res = (mp_sub(&D, &xc, &D)))) goto CLEANUP;
              s_mp_div_2(&D);
          }
      }

      if (mp_cmp(&u, &v) >= 0) {
          MP_CHECKOK(mp_sub(&u, &v, &u))if (0 > (res = (mp_sub(&u, &v, &u)))) goto CLEANUP;
          MP_CHECKOK(mp_sub(&A, &C, &A))if (0 > (res = (mp_sub(&A, &C, &A)))) goto CLEANUP;
          MP_CHECKOK(mp_sub(&B, &D, &B))if (0 > (res = (mp_sub(&B, &D, &B)))) goto CLEANUP;
      } else {
          MP_CHECKOK(mp_sub(&v, &u, &v))if (0 > (res = (mp_sub(&v, &u, &v)))) goto CLEANUP;
          MP_CHECKOK(mp_sub(&C, &A, &C))if (0 > (res = (mp_sub(&C, &A, &C)))) goto CLEANUP;
          MP_CHECKOK(mp_sub(&D, &B, &D))if (0 > (res = (mp_sub(&D, &B, &D)))) goto CLEANUP;
      }
  } while (mp_cmp_z(&u) != 0);

  /* copy results to output */
  if (x)
      MP_CHECKOK(mp_copy(&C, x))if (0 > (res = (mp_copy(&C, x)))) goto CLEANUP;

  if (y)
      MP_CHECKOK(mp_copy(&D, y))if (0 > (res = (mp_copy(&D, y)))) goto CLEANUP;

  if (g)
      MP_CHECKOK(mp_mul(&gx, &v, g))if (0 > (res = (mp_mul(&gx, &v, g)))) goto CLEANUP;

2173CLEANUP:
  while (last >= 0)
      mp_clear(clean[last--]);

  return res;

2179} /* end mp_xgcd() */

2181/* }}} */

2183mp_size
2184mp_trailing_zeros(const mp_int *mp)
2185{
  mp_digit d;
  mp_size n = 0;
  unsigned int ix;

  if (!mp || !MP_DIGITS(mp)((mp)->dp) || !mp_cmp_z(mp))
      return n;

  for (ix = 0; !(d = MP_DIGIT(mp, ix)(mp)->dp[(ix)]) && (ix < MP_USED(mp)((mp)->used)); ++ix)
      n += MP_DIGIT_BIT(8 * sizeof(mp_digit));
  if (!d)
      return 0; /* shouldn't happen, but ... */
2197#if !defined(MP_USE_UINT_DIGIT)
  if (!(d & 0xffffffffU)) {
      d >>= 32;
      n += 32;
  }
2202#endif
  if (!(d & 0xffffU)) {
      d >>= 16;
      n += 16;
  }
  if (!(d & 0xffU)) {
      d >>= 8;
      n += 8;
  }
  if (!(d & 0xfU)) {
      d >>= 4;
      n += 4;
  }
  if (!(d & 0x3U)) {
      d >>= 2;
      n += 2;
  }
  if (!(d & 0x1U)) {
      d >>= 1;
      n += 1;
  }
2223#if MP_ARGCHK2 == 2
  assert(0 != (d & 1))((void) sizeof ((0 != (d & 1)) ? 1 : 0), __extension__ ({
 if (0 != (d & 1)) ; else __assert_fail ("0 != (d & 1)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2224
, __extension__ __PRETTY_FUNCTION__); }));
2225#endif
  return n;
2227}

2229/* Given a and prime p, computes c and k such that a*c == 2**k (mod p).
2230** Returns k (positive) or error (negative).
2231** This technique from the paper "Fast Modular Reciprocals" (unpublished)
2232** by Richard Schroeppel (a.k.a. Captain Nemo).
2233*/
2234mp_err
2235s_mp_almost_inverse(const mp_int *a, const mp_int *p, mp_int *c)
2236{
  mp_err res;
  mp_err k = 0;
  mp_int d, f, g;

  ARGCHK(a != NULL && p != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && p != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && p != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && p != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2241
, __extension__ __PRETTY_FUNCTION__); }));

  MP_DIGITS(&d)((&d)->dp) = 0;
  MP_DIGITS(&f)((&f)->dp) = 0;
  MP_DIGITS(&g)((&g)->dp) = 0;
  MP_CHECKOK(mp_init(&d))if (0 > (res = (mp_init(&d)))) goto CLEANUP;
  MP_CHECKOK(mp_init_copy(&f, a))if (0 > (res = (mp_init_copy(&f, a)))) goto CLEANUP; /* f = a */
  MP_CHECKOK(mp_init_copy(&g, p))if (0 > (res = (mp_init_copy(&g, p)))) goto CLEANUP; /* g = p */

  mp_set(c, 1);
  mp_zero(&d);

  if (mp_cmp_z(&f) == 0) {
      res = MP_UNDEF-5;
  } else
      for (;;) {
          int diff_sign;
          while (mp_iseven(&f)) {
              mp_size n = mp_trailing_zeros(&f);
              if (!n) {
                  res = MP_UNDEF-5;
                  goto CLEANUP;
              }
              s_mp_div_2d(&f, n);
              MP_CHECKOK(s_mp_mul_2d(&d, n))if (0 > (res = (s_mp_mul_2d(&d, n)))) goto CLEANUP;
              k += n;
          }
          if (mp_cmp_d(&f, 1) == MP_EQ0) { /* f == 1 */
              res = k;
              break;
          }
          diff_sign = mp_cmp(&f, &g);
          if (diff_sign < 0) { /* f < g */
              s_mp_exch(&f, &g);
              s_mp_exch(c, &d);
          } else if (diff_sign == 0) { /* f == g */
              res = MP_UNDEF-5;          /* a and p are not relatively prime */
              break;
          }
          if ((MP_DIGIT(&f, 0)(&f)->dp[(0)] % 4) == (MP_DIGIT(&g, 0)(&g)->dp[(0)] % 4)) {
              MP_CHECKOK(mp_sub(&f, &g, &f))if (0 > (res = (mp_sub(&f, &g, &f)))) goto CLEANUP; /* f = f - g */
              MP_CHECKOK(mp_sub(c, &d, c))if (0 > (res = (mp_sub(c, &d, c)))) goto CLEANUP;   /* c = c - d */
          } else {
              MP_CHECKOK(mp_add(&f, &g, &f))if (0 > (res = (mp_add(&f, &g, &f)))) goto CLEANUP; /* f = f + g */
              MP_CHECKOK(mp_add(c, &d, c))if (0 > (res = (mp_add(c, &d, c)))) goto CLEANUP;   /* c = c + d */
          }
      }
  if (res >= 0) {
      if (mp_cmp_mag(c, p) >= 0) {
          MP_CHECKOK(mp_div(c, p, NULL, c))if (0 > (res = (mp_div(c, p, ((void*)0), c)))) goto CLEANUP;
      }
      if (MP_SIGN(c)((c)->sign) != MP_ZPOS0) {
          MP_CHECKOK(mp_add(c, p, c))if (0 > (res = (mp_add(c, p, c)))) goto CLEANUP;
      }
      res = k;
  }

2298CLEANUP:
  mp_clear(&d);
  mp_clear(&f);
  mp_clear(&g);
  return res;
2303}

2305/* Compute T = (P ** -1) mod MP_RADIX.  Also works for 16-bit mp_digits.
2306** This technique from the paper "Fast Modular Reciprocals" (unpublished)
2307** by Richard Schroeppel (a.k.a. Captain Nemo).
2308*/
2309mp_digit
2310s_mp_invmod_radix(mp_digit P)
2311{
  mp_digit T = P;
  T *= 2 - (P * T);
  T *= 2 - (P * T);
  T *= 2 - (P * T);
  T *= 2 - (P * T);
2317#if !defined(MP_USE_UINT_DIGIT)
  T *= 2 - (P * T);
  T *= 2 - (P * T);
2320#endif
  return T;
2322}

2324/* Given c, k, and prime p, where a*c == 2**k (mod p),
2325** Compute x = (a ** -1) mod p.  This is similar to Montgomery reduction.
2326** This technique from the paper "Fast Modular Reciprocals" (unpublished)
2327** by Richard Schroeppel (a.k.a. Captain Nemo).
2328*/
2329mp_err
2330s_mp_fixup_reciprocal(const mp_int *c, const mp_int *p, int k, mp_int *x)
2331{
  int k_orig = k;
  mp_digit r;
  mp_size ix;
  mp_err res;

  if (mp_cmp_z(c) < 0) {           /* c < 0 */
      MP_CHECKOK(mp_add(c, p, x))if (0 > (res = (mp_add(c, p, x)))) goto CLEANUP; /* x = c + p */
  } else {
      MP_CHECKOK(mp_copy(c, x))if (0 > (res = (mp_copy(c, x)))) goto CLEANUP; /* x = c */
  }

  /* make sure x is large enough */
  ix = MP_HOWMANY(k, MP_DIGIT_BIT)(((k) + ((8 * sizeof(mp_digit))) - 1) / ((8 * sizeof(mp_digit
)))) + MP_USED(p)((p)->used) + 1;
  ix = MP_MAX(ix, MP_USED(x))(((ix) > (((x)->used))) ? (ix) : (((x)->used)));
  MP_CHECKOK(s_mp_pad(x, ix))if (0 > (res = (s_mp_pad(x, ix)))) goto CLEANUP;

  r = 0 - s_mp_invmod_radix(MP_DIGIT(p, 0)(p)->dp[(0)]);

  for (ix = 0; k > 0; ix++) {
      int j = MP_MIN(k, MP_DIGIT_BIT)(((k) < ((8 * sizeof(mp_digit)))) ? (k) : ((8 * sizeof(mp_digit
))));
      mp_digit v = r * MP_DIGIT(x, ix)(x)->dp[(ix)];
      if (j < MP_DIGIT_BIT(8 * sizeof(mp_digit))) {
          v &= ((mp_digit)1 << j) - 1; /* v = v mod (2 ** j) */
      }
      s_mp_mul_d_add_offset(p, v, x, ix)s_mpv_mul_d_add_prop(((p)->dp), ((p)->used), v, ((x)->
dp) + ix); /* x += p * v * (RADIX ** ix) */
      k -= j;
  }
  s_mp_clamp(x);
  s_mp_div_2d(x, k_orig);
  res = MP_OKAY0;

2363CLEANUP:
  return res;
2365}

2367/*
Computes the modular inverse using the constant-time algorithm
by Bernstein and Yang (https://eprint.iacr.org/2019/266)
"Fast constant-time gcd computation and modular inversion"
*/
2372mp_err
2373s_mp_invmod_odd_m(const mp_int *a, const mp_int *m, mp_int *c)
2374{
  mp_err res;
  mp_digit cond = 0;
  mp_int g, f, v, r, temp;
  int i, its, delta = 1, last = -1;
  mp_size top, flen, glen;
  mp_int *clear[6];

  ARGCHK(a != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && m != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && m != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2382
, __extension__ __PRETTY_FUNCTION__); }));
  /* Check for invalid inputs. */
  if (mp_cmp_z(a) == MP_EQ0 || mp_cmp_d(m, 2) == MP_LT-1)
      return MP_RANGE-3;

  if (a == m || mp_iseven(m))
      return MP_UNDEF-5;

  MP_CHECKOK(mp_init(&temp))if (0 > (res = (mp_init(&temp)))) goto CLEANUP;
  clear[++last] = &temp;
  MP_CHECKOK(mp_init(&v))if (0 > (res = (mp_init(&v)))) goto CLEANUP;
  clear[++last] = &v;
  MP_CHECKOK(mp_init(&r))if (0 > (res = (mp_init(&r)))) goto CLEANUP;
  clear[++last] = &r;
  MP_CHECKOK(mp_init_copy(&g, a))if (0 > (res = (mp_init_copy(&g, a)))) goto CLEANUP;
  clear[++last] = &g;
  MP_CHECKOK(mp_init_copy(&f, m))if (0 > (res = (mp_init_copy(&f, m)))) goto CLEANUP;
  clear[++last] = &f;

  mp_set(&v, 0);
  mp_set(&r, 1);

  /* Allocate to the size of largest mp_int. */
  top = (mp_size)1 + ((USED(&f)((&f)->used) >= USED(&g)((&g)->used)) ? USED(&f)((&f)->used) : USED(&g)((&g)->used));
  MP_CHECKOK(s_mp_grow(&f, top))if (0 > (res = (s_mp_grow(&f, top)))) goto CLEANUP;
  MP_CHECKOK(s_mp_grow(&g, top))if (0 > (res = (s_mp_grow(&g, top)))) goto CLEANUP;
  MP_CHECKOK(s_mp_grow(&temp, top))if (0 > (res = (s_mp_grow(&temp, top)))) goto CLEANUP;
  MP_CHECKOK(s_mp_grow(&v, top))if (0 > (res = (s_mp_grow(&v, top)))) goto CLEANUP;
  MP_CHECKOK(s_mp_grow(&r, top))if (0 > (res = (s_mp_grow(&r, top)))) goto CLEANUP;

  /* Upper bound for the total iterations. */
  flen = mpl_significant_bits(&f);
  glen = mpl_significant_bits(&g);
  its = 4 + 3 * ((flen >= glen) ? flen : glen);

2417#if defined(_MSC_VER)
2418#pragma warning(push)
2419#pragma warning(disable : 4146) // Thanks MSVC, we know what we're negating an unsigned mp_digit
2420#endif

  for (i = 0; i < its; i++) {
      /* Step 1: conditional swap. */
      /* Set cond if delta > 0 and g is odd. */
      cond = (-delta >> (8 * sizeof(delta) - 1)) & DIGIT(&g, 0)(&g)->dp[(0)] & 1;
      /* If cond is set replace (delta,f,v) with (-delta,-f,-v). */
      delta = (-cond & -delta) | ((cond - 1) & delta);
      SIGN(&f)((&f)->sign) ^= cond;
      SIGN(&v)((&v)->sign) ^= cond;
      /* If cond is set swap (f,v) with (g,r). */
      MP_CHECKOK(mp_cswap(cond, &f, &g, top))if (0 > (res = (mp_cswap(cond, &f, &g, top)))) goto
 CLEANUP;
      MP_CHECKOK(mp_cswap(cond, &v, &r, top))if (0 > (res = (mp_cswap(cond, &v, &r, top)))) goto
 CLEANUP;

      /* Step 2: elemination. */
      /* Update delta */
      delta++;
      /* If g is odd replace r with (r+v). */
      MP_CHECKOK(mp_add(&r, &v, &temp))if (0 > (res = (mp_add(&r, &v, &temp)))) goto CLEANUP;
      MP_CHECKOK(mp_cswap((DIGIT(&g, 0) & 1), &r, &temp, top))if (0 > (res = (mp_cswap(((&g)->dp[(0)] & 1), &
r, &temp, top)))) goto CLEANUP;
      /* If g is odd, right shift (g+f) else right shift g. */
      MP_CHECKOK(mp_add(&g, &f, &temp))if (0 > (res = (mp_add(&g, &f, &temp)))) goto CLEANUP;
      MP_CHECKOK(mp_cswap((DIGIT(&g, 0) & 1), &g, &temp, top))if (0 > (res = (mp_cswap(((&g)->dp[(0)] & 1), &
g, &temp, top)))) goto CLEANUP;
      s_mp_div_2(&g);
      /*
      If r is even, right shift it.
      If r is odd, right shift (r+m) which is even because m is odd.
      We want the result modulo m so adding in multiples of m here vanish.
      */
      MP_CHECKOK(mp_add(&r, m, &temp))if (0 > (res = (mp_add(&r, m, &temp)))) goto CLEANUP;
      MP_CHECKOK(mp_cswap((DIGIT(&r, 0) & 1), &r, &temp, top))if (0 > (res = (mp_cswap(((&r)->dp[(0)] & 1), &
r, &temp, top)))) goto CLEANUP;
      s_mp_div_2(&r);
  }

2454#if defined(_MSC_VER)
2455#pragma warning(pop)
2456#endif

  /* We have the inverse in v, propagate sign from f. */
  SIGN(&v)((&v)->sign) ^= SIGN(&f)((&f)->sign);
  /* GCD is in f, take the absolute value. */
  SIGN(&f)((&f)->sign) = ZPOS0;

  /* If gcd != 1, not invertible. */
  if (mp_cmp_d(&f, 1) != MP_EQ0) {
      res = MP_UNDEF-5;
      goto CLEANUP;
  }

  /* Return inverse modulo m. */
  MP_CHECKOK(mp_mod(&v, m, c))if (0 > (res = (mp_mod(&v, m, c)))) goto CLEANUP;

2472CLEANUP:
  while (last >= 0)
      mp_clear(clear[last--]);
  return res;
2476}

2478/* Known good algorithm for computing modular inverse.  But slow. */
2479mp_err
2480mp_invmod_xgcd(const mp_int *a, const mp_int *m, mp_int *c)
2481{
  mp_int g, x;
  mp_err res;

  ARGCHK(a != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && m != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && m != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2485
, __extension__ __PRETTY_FUNCTION__); }));

  if (mp_cmp_z(a) == 0 || mp_cmp_z(m) == 0)
      return MP_RANGE-3;

  MP_DIGITS(&g)((&g)->dp) = 0;
  MP_DIGITS(&x)((&x)->dp) = 0;
  MP_CHECKOK(mp_init(&x))if (0 > (res = (mp_init(&x)))) goto CLEANUP;
  MP_CHECKOK(mp_init(&g))if (0 > (res = (mp_init(&g)))) goto CLEANUP;

  MP_CHECKOK(mp_xgcd(a, m, &g, &x, NULL))if (0 > (res = (mp_xgcd(a, m, &g, &x, ((void*)0)))
)) goto CLEANUP;

  if (mp_cmp_d(&g, 1) != MP_EQ0) {
      res = MP_UNDEF-5;
      goto CLEANUP;
  }

  res = mp_mod(&x, m, c);
  SIGN(c)((c)->sign) = SIGN(a)((a)->sign);

2505CLEANUP:
  mp_clear(&x);
  mp_clear(&g);

  return res;
2510}

2512/* modular inverse where modulus is 2**k. */
2513/* c = a**-1 mod 2**k */
2514mp_err
2515s_mp_invmod_2d(const mp_int *a, mp_size k, mp_int *c)
2516{
  mp_err res;
  mp_size ix = k + 4;
  mp_int t0, t1, val, tmp, two2k;

  static const mp_digit d2 = 2;
  static const mp_int two = { MP_ZPOS0, 1, 1, (mp_digit *)&d2 };

  if (mp_iseven(a))
      return MP_UNDEF-5;

2527#if defined(_MSC_VER)
2528#pragma warning(push)
2529#pragma warning(disable : 4146) // Thanks MSVC, we know what we're negating an unsigned mp_digit
2530#endif
  if (k <= MP_DIGIT_BIT(8 * sizeof(mp_digit))) {
      mp_digit i = s_mp_invmod_radix(MP_DIGIT(a, 0)(a)->dp[(0)]);
      /* propagate the sign from mp_int */
      i = (i ^ -(mp_digit)SIGN(a)((a)->sign)) + (mp_digit)SIGN(a)((a)->sign);
      if (k < MP_DIGIT_BIT(8 * sizeof(mp_digit)))
          i &= ((mp_digit)1 << k) - (mp_digit)1;
      mp_set(c, i);
      return MP_OKAY0;
  }
2540#if defined(_MSC_VER)
2541#pragma warning(pop)
2542#endif

  MP_DIGITS(&t0)((&t0)->dp) = 0;
  MP_DIGITS(&t1)((&t1)->dp) = 0;
  MP_DIGITS(&val)((&val)->dp) = 0;
  MP_DIGITS(&tmp)((&tmp)->dp) = 0;
  MP_DIGITS(&two2k)((&two2k)->dp) = 0;
  MP_CHECKOK(mp_init_copy(&val, a))if (0 > (res = (mp_init_copy(&val, a)))) goto CLEANUP;
  s_mp_mod_2d(&val, k);
  MP_CHECKOK(mp_init_copy(&t0, &val))if (0 > (res = (mp_init_copy(&t0, &val)))) goto CLEANUP;
  MP_CHECKOK(mp_init_copy(&t1, &t0))if (0 > (res = (mp_init_copy(&t1, &t0)))) goto CLEANUP;
  MP_CHECKOK(mp_init(&tmp))if (0 > (res = (mp_init(&tmp)))) goto CLEANUP;
  MP_CHECKOK(mp_init(&two2k))if (0 > (res = (mp_init(&two2k)))) goto CLEANUP;
  MP_CHECKOK(s_mp_2expt(&two2k, k))if (0 > (res = (s_mp_2expt(&two2k, k)))) goto CLEANUP;
  do {
      MP_CHECKOK(mp_mul(&val, &t1, &tmp))if (0 > (res = (mp_mul(&val, &t1, &tmp)))) goto
 CLEANUP;
      MP_CHECKOK(mp_sub(&two, &tmp, &tmp))if (0 > (res = (mp_sub(&two, &tmp, &tmp)))) goto
 CLEANUP;
      MP_CHECKOK(mp_mul(&t1, &tmp, &t1))if (0 > (res = (mp_mul(&t1, &tmp, &t1)))) goto
 CLEANUP;
      s_mp_mod_2d(&t1, k);
      while (MP_SIGN(&t1)((&t1)->sign) != MP_ZPOS0) {
          MP_CHECKOK(mp_add(&t1, &two2k, &t1))if (0 > (res = (mp_add(&t1, &two2k, &t1)))) goto
 CLEANUP;
      }
      if (mp_cmp(&t1, &t0) == MP_EQ0)
          break;
      MP_CHECKOK(mp_copy(&t1, &t0))if (0 > (res = (mp_copy(&t1, &t0)))) goto CLEANUP;
  } while (--ix > 0);
  if (!ix) {
      res = MP_UNDEF-5;
  } else {
      mp_exch(c, &t1);
  }

2574CLEANUP:
  mp_clear(&t0);
  mp_clear(&t1);
  mp_clear(&val);
  mp_clear(&tmp);
  mp_clear(&two2k);
  return res;
2581}

2583mp_err
2584s_mp_invmod_even_m(const mp_int *a, const mp_int *m, mp_int *c)
2585{
  mp_err res;
  mp_size k;
  mp_int oddFactor, evenFactor; /* factors of the modulus */
  mp_int oddPart, evenPart;     /* parts to combine via CRT. */
  mp_int C2, tmp1, tmp2;

  ARGCHK(a != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && m != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && m != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2592
, __extension__ __PRETTY_FUNCTION__); }));

  /*static const mp_digit d1 = 1; */
  /*static const mp_int one = { MP_ZPOS, 1, 1, (mp_digit *)&d1 }; */

  if ((res = s_mp_ispow2(m)) >= 0) {
      k = res;
      return s_mp_invmod_2d(a, k, c);
  }
  MP_DIGITS(&oddFactor)((&oddFactor)->dp) = 0;
  MP_DIGITS(&evenFactor)((&evenFactor)->dp) = 0;
  MP_DIGITS(&oddPart)((&oddPart)->dp) = 0;
  MP_DIGITS(&evenPart)((&evenPart)->dp) = 0;
  MP_DIGITS(&C2)((&C2)->dp) = 0;
  MP_DIGITS(&tmp1)((&tmp1)->dp) = 0;
  MP_DIGITS(&tmp2)((&tmp2)->dp) = 0;

  MP_CHECKOK(mp_init_copy(&oddFactor, m))if (0 > (res = (mp_init_copy(&oddFactor, m)))) goto CLEANUP; /* oddFactor = m */
  MP_CHECKOK(mp_init(&evenFactor))if (0 > (res = (mp_init(&evenFactor)))) goto CLEANUP;
  MP_CHECKOK(mp_init(&oddPart))if (0 > (res = (mp_init(&oddPart)))) goto CLEANUP;
  MP_CHECKOK(mp_init(&evenPart))if (0 > (res = (mp_init(&evenPart)))) goto CLEANUP;
  MP_CHECKOK(mp_init(&C2))if (0 > (res = (mp_init(&C2)))) goto CLEANUP;
  MP_CHECKOK(mp_init(&tmp1))if (0 > (res = (mp_init(&tmp1)))) goto CLEANUP;
  MP_CHECKOK(mp_init(&tmp2))if (0 > (res = (mp_init(&tmp2)))) goto CLEANUP;

  k = mp_trailing_zeros(m);
  s_mp_div_2d(&oddFactor, k);
  MP_CHECKOK(s_mp_2expt(&evenFactor, k))if (0 > (res = (s_mp_2expt(&evenFactor, k)))) goto CLEANUP;

  /* compute a**-1 mod oddFactor. */
  MP_CHECKOK(s_mp_invmod_odd_m(a, &oddFactor, &oddPart))if (0 > (res = (s_mp_invmod_odd_m(a, &oddFactor, &
oddPart)))) goto CLEANUP;
  /* compute a**-1 mod evenFactor, where evenFactor == 2**k. */
  MP_CHECKOK(s_mp_invmod_2d(a, k, &evenPart))if (0 > (res = (s_mp_invmod_2d(a, k, &evenPart)))) goto
 CLEANUP;

  /* Use Chinese Remainer theorem to compute a**-1 mod m. */
  /* let m1 = oddFactor,  v1 = oddPart,
   * let m2 = evenFactor, v2 = evenPart.
   */

  /* Compute C2 = m1**-1 mod m2. */
  MP_CHECKOK(s_mp_invmod_2d(&oddFactor, k, &C2))if (0 > (res = (s_mp_invmod_2d(&oddFactor, k, &C2)
))) goto CLEANUP;

  /* compute u = (v2 - v1)*C2 mod m2 */
  MP_CHECKOK(mp_sub(&evenPart, &oddPart, &tmp1))if (0 > (res = (mp_sub(&evenPart, &oddPart, &tmp1
)))) goto CLEANUP;
  MP_CHECKOK(mp_mul(&tmp1, &C2, &tmp2))if (0 > (res = (mp_mul(&tmp1, &C2, &tmp2)))) goto
 CLEANUP;
  s_mp_mod_2d(&tmp2, k);
  while (MP_SIGN(&tmp2)((&tmp2)->sign) != MP_ZPOS0) {
      MP_CHECKOK(mp_add(&tmp2, &evenFactor, &tmp2))if (0 > (res = (mp_add(&tmp2, &evenFactor, &tmp2
)))) goto CLEANUP;
  }

  /* compute answer = v1 + u*m1 */
  MP_CHECKOK(mp_mul(&tmp2, &oddFactor, c))if (0 > (res = (mp_mul(&tmp2, &oddFactor, c)))) goto
 CLEANUP;
  MP_CHECKOK(mp_add(&oddPart, c, c))if (0 > (res = (mp_add(&oddPart, c, c)))) goto CLEANUP;
  /* not sure this is necessary, but it's low cost if not. */
  MP_CHECKOK(mp_mod(c, m, c))if (0 > (res = (mp_mod(c, m, c)))) goto CLEANUP;

2648CLEANUP:
  mp_clear(&oddFactor);
  mp_clear(&evenFactor);
  mp_clear(&oddPart);
  mp_clear(&evenPart);
  mp_clear(&C2);
  mp_clear(&tmp1);
  mp_clear(&tmp2);
  return res;
2657}

2659/* {{{ mp_invmod(a, m, c) */

2661/*
mp_invmod(a, m, c)

Compute c = a^-1 (mod m), if there is an inverse for a (mod m).
This is equivalent to the question of whether (a, m) = 1.  If not,
MP_UNDEF is returned, and there is no inverse.
*/

2669mp_err
2670mp_invmod(const mp_int *a, const mp_int *m, mp_int *c)
2671{
  ARGCHK(a != NULL && m != NULL && c != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && m != ((void*)0) &&
 c != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void*
)0) && m != ((void*)0) && c != ((void*)0)) ; else
 __assert_fail ("a != ((void*)0) && m != ((void*)0) && c != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2672
, __extension__ __PRETTY_FUNCTION__); }));

  if (mp_cmp_z(a) == 0 || mp_cmp_z(m) == 0)
      return MP_RANGE-3;

  if (mp_isodd(m)) {
      return s_mp_invmod_odd_m(a, m, c);
  }
  if (mp_iseven(a))
      return MP_UNDEF-5; /* not invertable */

  return s_mp_invmod_even_m(a, m, c);

2685} /* end mp_invmod() */

2687/* }}} */

2689/* }}} */

2691/*------------------------------------------------------------------------*/
2692/* {{{ mp_print(mp, ofp) */

2694#if MP_IOFUNC0
2695/*
mp_print(mp, ofp)

Print a textual representation of the given mp_int on the output
stream 'ofp'.  Output is generated using the internal radix.
*/

2702void
2703mp_print(mp_int *mp, FILE *ofp)
2704{
  int ix;

  if (mp == NULL((void*)0) || ofp == NULL((void*)0))
      return;

  fputc((SIGN(mp)((mp)->sign) == NEG1) ? '-' : '+', ofp);

  for (ix = USED(mp)((mp)->used) - 1; ix >= 0; ix--) {
      fprintf(ofp, DIGIT_FMT"%016lX", DIGIT(mp, ix)(mp)->dp[(ix)]);
  }

2716} /* end mp_print() */

2718#endif /* if MP_IOFUNC */

2720/* }}} */

2722/*------------------------------------------------------------------------*/
2723/* {{{ More I/O Functions */

2725/* {{{ mp_read_raw(mp, str, len) */

2727/*
 mp_read_raw(mp, str, len)

 Read in a raw value (base 256) into the given mp_int
*/

2733mp_err
2734mp_read_raw(mp_int *mp, char *str, int len)
2735{
  int ix;
  mp_err res;
  unsigned char *ustr = (unsigned char *)str;

  ARGCHK(mp != NULL && str != NULL && len > 0, MP_BADARG)((void) sizeof ((mp != ((void*)0) && str != ((void*)0
) && len > 0) ? 1 : 0), __extension__ ({ if (mp !=
 ((void*)0) && str != ((void*)0) && len > 0
) ; else __assert_fail ("mp != ((void*)0) && str != ((void*)0) && len > 0"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2740
, __extension__ __PRETTY_FUNCTION__); }));

  mp_zero(mp);

  /* Read the rest of the digits */
  for (ix = 1; ix < len; ix++) {
      if ((res = mp_mul_d(mp, 256, mp)) != MP_OKAY0)
          return res;
      if ((res = mp_add_d(mp, ustr[ix], mp)) != MP_OKAY0)
          return res;
  }

  /* Get sign from first byte */
  if (ustr[0])
      SIGN(mp)((mp)->sign) = NEG1;
  else
      SIGN(mp)((mp)->sign) = ZPOS0;

  return MP_OKAY0;

2760} /* end mp_read_raw() */

2762/* }}} */

2764/* {{{ mp_raw_size(mp) */

2766int
2767mp_raw_size(mp_int *mp)
2768{
  ARGCHK(mp != NULL, 0)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2769
, __extension__ __PRETTY_FUNCTION__); }));

  return (USED(mp)((mp)->used) * sizeof(mp_digit)) + 1;

2773} /* end mp_raw_size() */

2775/* }}} */

2777/* {{{ mp_toraw(mp, str) */

2779mp_err
2780mp_toraw(mp_int *mp, char *str)
2781{
  int ix, jx, pos = 1;

  ARGCHK(mp != NULL && str != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0) && str != ((void*)0
)) ? 1 : 0), __extension__ ({ if (mp != ((void*)0) &&
 str != ((void*)0)) ; else __assert_fail ("mp != ((void*)0) && str != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2784
, __extension__ __PRETTY_FUNCTION__); }));

  str[0] = (char)SIGN(mp)((mp)->sign);

  /* Iterate over each digit... */
  for (ix = USED(mp)((mp)->used) - 1; ix >= 0; ix--) {
      mp_digit d = DIGIT(mp, ix)(mp)->dp[(ix)];

      /* Unpack digit bytes, high order first */
      for (jx = sizeof(mp_digit) - 1; jx >= 0; jx--) {
          str[pos++] = (char)(d >> (jx * CHAR_BIT8));
      }
  }

  return MP_OKAY0;

2800} /* end mp_toraw() */

2802/* }}} */

2804/* {{{ mp_read_radix(mp, str, radix) */

2806/*
mp_read_radix(mp, str, radix)

Read an integer from the given string, and set mp to the resulting
value.  The input is presumed to be in base 10.  Leading non-digit
characters are ignored, and the function reads until a non-digit
character or the end of the string.
*/

2815mp_err
2816mp_read_radix(mp_int *mp, const char *str, int radix)
2817{
  int ix = 0, val = 0;
  mp_err res;
  mp_sign sig = ZPOS0;

  ARGCHK(mp != NULL && str != NULL && radix >= 2 && radix <= MAX_RADIX,((void) sizeof ((mp != ((void*)0) && str != ((void*)0
) && radix >= 2 && radix <= 64) ? 1 : 0
), __extension__ ({ if (mp != ((void*)0) && str != ((
void*)0) && radix >= 2 && radix <= 64) ;
 else __assert_fail ("mp != ((void*)0) && str != ((void*)0) && radix >= 2 && radix <= 64"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2823
, __extension__ __PRETTY_FUNCTION__); }))
         MP_BADARG)((void) sizeof ((mp != ((void*)0) && str != ((void*)0
) && radix >= 2 && radix <= 64) ? 1 : 0
), __extension__ ({ if (mp != ((void*)0) && str != ((
void*)0) && radix >= 2 && radix <= 64) ;
 else __assert_fail ("mp != ((void*)0) && str != ((void*)0) && radix >= 2 && radix <= 64"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2823
, __extension__ __PRETTY_FUNCTION__); }));

  mp_zero(mp);

  /* Skip leading non-digit characters until a digit or '-' or '+' */
  while (str[ix] &&
         (s_mp_tovalue(str[ix], radix) < 0) &&
         str[ix] != '-' &&
         str[ix] != '+') {
      ++ix;
  }

  if (str[ix] == '-') {
      sig = NEG1;
      ++ix;
  } else if (str[ix] == '+') {
      sig = ZPOS0; /* this is the default anyway... */
      ++ix;
  }

  while ((val = s_mp_tovalue(str[ix], radix)) >= 0) {
      if ((res = s_mp_mul_d(mp, radix)) != MP_OKAY0)
          return res;
      if ((res = s_mp_add_d(mp, val)) != MP_OKAY0)
          return res;
      ++ix;
  }

  if (s_mp_cmp_d(mp, 0) == MP_EQ0)
      SIGN(mp)((mp)->sign) = ZPOS0;
  else
      SIGN(mp)((mp)->sign) = sig;

  return MP_OKAY0;

2858} /* end mp_read_radix() */

2860mp_err
2861mp_read_variable_radix(mp_int *a, const char *str, int default_radix)
2862{
  int radix = default_radix;
  int cx;
  mp_sign sig = ZPOS0;
  mp_err res;

  /* Skip leading non-digit characters until a digit or '-' or '+' */
  while ((cx = *str) != 0 &&
         (s_mp_tovalue(cx, radix) < 0) &&
         cx != '-' &&
         cx != '+') {
      ++str;
  }

  if (cx == '-') {
      sig = NEG1;
      ++str;
  } else if (cx == '+') {
      sig = ZPOS0; /* this is the default anyway... */
      ++str;
  }

  if (str[0] == '0') {
      if ((str[1] | 0x20) == 'x') {
          radix = 16;
          str += 2;
      } else {
          radix = 8;
          str++;
      }
  }
  res = mp_read_radix(a, str, radix);
  if (res == MP_OKAY0) {
      MP_SIGN(a)((a)->sign) = (s_mp_cmp_d(a, 0) == MP_EQ0) ? ZPOS0 : sig;
  }
  return res;
2898}

2900/* }}} */

2902/* {{{ mp_radix_size(mp, radix) */

2904int
2905mp_radix_size(mp_int *mp, int radix)
2906{
  int bits;

  if (!mp || radix < 2 || radix > MAX_RADIX64)
      return 0;

  bits = USED(mp)((mp)->used) * DIGIT_BIT(8 * sizeof(mp_digit)) - 1;

  return SIGN(mp)((mp)->sign) + s_mp_outlen(bits, radix);

2916} /* end mp_radix_size() */

2918/* }}} */

2920/* {{{ mp_toradix(mp, str, radix) */

2922mp_err
2923mp_toradix(mp_int *mp, char *str, int radix)
2924{
  int ix, pos = 0;

  ARGCHK(mp != NULL && str != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0) && str != ((void*)0
)) ? 1 : 0), __extension__ ({ if (mp != ((void*)0) &&
 str != ((void*)0)) ; else __assert_fail ("mp != ((void*)0) && str != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2927
, __extension__ __PRETTY_FUNCTION__); }));
  ARGCHK(radix > 1 && radix <= MAX_RADIX, MP_RANGE)((void) sizeof ((radix > 1 && radix <= 64) ? 1 :
 0), __extension__ ({ if (radix > 1 && radix <=
 64) ; else __assert_fail ("radix > 1 && radix <= 64"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 2928
, __extension__ __PRETTY_FUNCTION__); }));

  if (mp_cmp_z(mp) == MP_EQ0) {
      str[0] = '0';
      str[1] = '\0';
  } else {
      mp_err res;
      mp_int tmp;
      mp_sign sgn;
      mp_digit rem, rdx = (mp_digit)radix;
      char ch;

      if ((res = mp_init_copy(&tmp, mp)) != MP_OKAY0)
          return res;

      /* Save sign for later, and take absolute value */
      sgn = SIGN(&tmp)((&tmp)->sign);
      SIGN(&tmp)((&tmp)->sign) = ZPOS0;

      /* Generate output digits in reverse order      */
      while (mp_cmp_z(&tmp) != 0) {
          if ((res = mp_div_d(&tmp, rdx, &tmp, &rem)) != MP_OKAY0) {
              mp_clear(&tmp);
              return res;
          }

          /* Generate digits, use capital letters */
          ch = s_mp_todigit(rem, radix, 0);

          str[pos++] = ch;
      }

      /* Add - sign if original value was negative */
      if (sgn == NEG1)
          str[pos++] = '-';

      /* Add trailing NUL to end the string        */
      str[pos--] = '\0';

      /* Reverse the digits and sign indicator     */
      ix = 0;
      while (ix < pos) {
          char tmpc = str[ix];

          str[ix] = str[pos];
          str[pos] = tmpc;
          ++ix;
          --pos;
      }

      mp_clear(&tmp);
  }

  return MP_OKAY0;

2983} /* end mp_toradix() */

2985/* }}} */

2987/* {{{ mp_tovalue(ch, r) */

2989int
2990mp_tovalue(char ch, int r)
2991{
  return s_mp_tovalue(ch, r);

2994} /* end mp_tovalue() */

2996/* }}} */

2998/* }}} */

3000/* {{{ mp_strerror(ec) */

3002/*
mp_strerror(ec)

Return a string describing the meaning of error code 'ec'.  The
string returned is allocated in static memory, so the caller should
not attempt to modify or free the memory associated with this
string.
*/
3010const char *
3011mp_strerror(mp_err ec)
3012{
  int aec = (ec < 0) ? -ec : ec;

  /* Code values are negative, so the senses of these comparisons
   are accurate */
  if (ec < MP_LAST_CODE-5 || ec > MP_OKAY0) {
      return mp_err_string[0]; /* unknown error code */
  } else {
      return mp_err_string[aec + 1];
  }

3023} /* end mp_strerror() */

3025/* }}} */

3027/*========================================================================*/
3028/*------------------------------------------------------------------------*/
3029/* Static function definitions (internal use only)                        */

3031/* {{{ Memory management */

3033/* {{{ s_mp_grow(mp, min) */

3035/* Make sure there are at least 'min' digits allocated to mp              */
3036mp_err
3037s_mp_grow(mp_int *mp, mp_size min)
3038{
  ARGCHK(mp != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 3039
, __extension__ __PRETTY_FUNCTION__); }));

  if (min > ALLOC(mp)((mp)->alloc)) {
      mp_digit *tmp;

      /* Set min to next nearest default precision block size */
      min = MP_ROUNDUP(min, s_mp_defprec)((((min) + (s_mp_defprec) - 1) / (s_mp_defprec)) * (s_mp_defprec
));

      if ((tmp = s_mp_alloc(min, sizeof(mp_digit))) == NULL((void*)0))
          return MP_MEM-2;

      s_mp_copy(DIGITS(mp)((mp)->dp), tmp, USED(mp)((mp)->used));

      s_mp_setz(DIGITS(mp)((mp)->dp), ALLOC(mp)((mp)->alloc));
      s_mp_free(DIGITS(mp)((mp)->dp));
      DIGITS(mp)((mp)->dp) = tmp;
      ALLOC(mp)((mp)->alloc) = min;
  }

  return MP_OKAY0;

3060} /* end s_mp_grow() */

3062/* }}} */

3064/* {{{ s_mp_pad(mp, min) */

3066/* Make sure the used size of mp is at least 'min', growing if needed     */
3067mp_err
3068s_mp_pad(mp_int *mp, mp_size min)
3069{
  ARGCHK(mp != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 3070
, __extension__ __PRETTY_FUNCTION__); }));

  if (min > USED(mp)((mp)->used)) {
      mp_err res;

      /* Make sure there is room to increase precision  */
      if (min > ALLOC(mp)((mp)->alloc)) {
          if ((res = s_mp_grow(mp, min)) != MP_OKAY0)
              return res;
      } else {
          s_mp_setz(DIGITS(mp)((mp)->dp) + USED(mp)((mp)->used), min - USED(mp)((mp)->used));
      }

      /* Increase precision; should already be 0-filled */
      USED(mp)((mp)->used) = min;
  }

  return MP_OKAY0;

3089} /* end s_mp_pad() */

3091/* }}} */

3093/* {{{ s_mp_setz(dp, count) */

3095/* Set 'count' digits pointed to by dp to be zeroes                       */
3096void
3097s_mp_setz(mp_digit *dp, mp_size count)
3098{
  memset(dp, 0, count * sizeof(mp_digit));
3100} /* end s_mp_setz() */

3102/* }}} */

3104/* {{{ s_mp_copy(sp, dp, count) */

3106/* Copy 'count' digits from sp to dp                                      */
3107void
3108s_mp_copy(const mp_digit *sp, mp_digit *dp, mp_size count)
3109{
  memcpy(dp, sp, count * sizeof(mp_digit));
3111} /* end s_mp_copy() */

3113/* }}} */

3115/* {{{ s_mp_alloc(nb, ni) */

3117/* Allocate ni records of nb bytes each, and return a pointer to that     */
3118void *
3119s_mp_alloc(size_t nb, size_t ni)
3120{
  return calloc(nb, ni);

3123} /* end s_mp_alloc() */

3125/* }}} */

3127/* {{{ s_mp_free(ptr) */

3129/* Free the memory pointed to by ptr                                      */
3130void
3131s_mp_free(void *ptr)
3132{
  if (ptr) {
      free(ptr);
  }
3136} /* end s_mp_free() */

3138/* }}} */

3140/* {{{ s_mp_clamp(mp) */

3142/* Remove leading zeroes from the given value                             */
3143void
3144s_mp_clamp(mp_int *mp)
3145{
  mp_size used = MP_USED(mp)((mp)->used);
  while (used > 1 && DIGIT(mp, used - 1)(mp)->dp[(used - 1)] == 0)
      --used;
  MP_USED(mp)((mp)->used) = used;
  if (used == 1 && DIGIT(mp, 0)(mp)->dp[(0)] == 0)
      MP_SIGN(mp)((mp)->sign) = ZPOS0;
3152} /* end s_mp_clamp() */

3154/* }}} */

3156/* {{{ s_mp_exch(a, b) */

3158/* Exchange the data for a and b; (b, a) = (a, b)                         */
3159void
3160s_mp_exch(mp_int *a, mp_int *b)
3161{
  mp_int tmp;
  if (!a || !b) {
      return;
  }

  tmp = *a;
  *a = *b;
  *b = tmp;

3171} /* end s_mp_exch() */

3173/* }}} */

3175/* }}} */

3177/* {{{ Arithmetic helpers */

3179/* {{{ s_mp_lshd(mp, p) */

3181/*
 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
*/

3187mp_err
3188s_mp_lshd(mp_int *mp, mp_size p)
3189{
  mp_err res;
  unsigned int ix;

  ARGCHK(mp != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 3193
, __extension__ __PRETTY_FUNCTION__); }));

  if (p == 0)
      return MP_OKAY0;

  if (MP_USED(mp)((mp)->used) == 1 && MP_DIGIT(mp, 0)(mp)->dp[(0)] == 0)
      return MP_OKAY0;

  if ((res = s_mp_pad(mp, USED(mp)((mp)->used) + p)) != MP_OKAY0)
      return res;

  /* Shift all the significant figures over as needed */
  for (ix = USED(mp)((mp)->used) - p; ix-- > 0;) {
      DIGIT(mp, ix + p)(mp)->dp[(ix + p)] = DIGIT(mp, ix)(mp)->dp[(ix)];
  }

  /* Fill the bottom digits with zeroes */
  for (ix = 0; (mp_size)ix < p; ix++)
      DIGIT(mp, ix)(mp)->dp[(ix)] = 0;

  return MP_OKAY0;

3215} /* end s_mp_lshd() */

3217/* }}} */

3219/* {{{ s_mp_mul_2d(mp, d) */

3221/*
Multiply the integer by 2^d, where d is a number of bits.  This
amounts to a bitwise shift of the value.
*/
3225mp_err
3226s_mp_mul_2d(mp_int *mp, mp_digit d)
3227{
  mp_err res;
  mp_digit dshift, rshift, mask, x, prev = 0;
  mp_digit *pa = NULL((void*)0);
  int i;

  ARGCHK(mp != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 3233
, __extension__ __PRETTY_FUNCTION__); }));

  dshift = d / MP_DIGIT_BIT(8 * sizeof(mp_digit));
  d %= MP_DIGIT_BIT(8 * sizeof(mp_digit));
  /* mp_digit >> rshift is undefined behavior for rshift >= MP_DIGIT_BIT */
  /* mod and corresponding mask logic avoid that when d = 0 */
  rshift = MP_DIGIT_BIT(8 * sizeof(mp_digit)) - d;
  rshift %= MP_DIGIT_BIT(8 * sizeof(mp_digit));
  /* mask = (2**d - 1) * 2**(w-d) mod 2**w */
  mask = (DIGIT_MAX(9223372036854775807L *2UL+1UL) << rshift) + 1;
  mask &= DIGIT_MAX(9223372036854775807L *2UL+1UL) - 1;
  /* bits to be shifted out of the top word */
  x = MP_DIGIT(mp, MP_USED(mp) - 1)(mp)->dp[(((mp)->used) - 1)] & mask;

  if (MP_OKAY0 != (res = s_mp_pad(mp, MP_USED(mp)((mp)->used) + dshift + (x != 0))))
      return res;

  if (dshift && MP_OKAY0 != (res = s_mp_lshd(mp, dshift)))
      return res;

  pa = MP_DIGITS(mp)((mp)->dp) + dshift;

  for (i = MP_USED(mp)((mp)->used) - dshift; i > 0; i--) {
      x = *pa;
      *pa++ = (x << d) | prev;
      prev = (x & mask) >> rshift;
  }

  s_mp_clamp(mp);
  return MP_OKAY0;
3263} /* end s_mp_mul_2d() */

3265/* {{{ s_mp_rshd(mp, p) */

3267/*
 Shift mp rightward by p digits.  Maintains the invariant that
 digits above the precision are all zero.  Digits shifted off the
 end are lost.  Cannot fail.
*/

3273void
3274s_mp_rshd(mp_int *mp, mp_size p)
3275{
  mp_size ix;
  mp_digit *src, *dst;

  if (p == 0)
      return;

  /* Shortcut when all digits are to be shifted off */
  if (p >= USED(mp)((mp)->used)) {
      s_mp_setz(DIGITS(mp)((mp)->dp), ALLOC(mp)((mp)->alloc));
      USED(mp)((mp)->used) = 1;
      SIGN(mp)((mp)->sign) = ZPOS0;
      return;
  }

  /* Shift all the significant figures over as needed */
  dst = MP_DIGITS(mp)((mp)->dp);
  src = dst + p;
  for (ix = USED(mp)((mp)->used) - p; ix > 0; ix--)
      *dst++ = *src++;

  MP_USED(mp)((mp)->used) -= p;
  /* Fill the top digits with zeroes */
  while (p-- > 0)
      *dst++ = 0;

3301} /* end s_mp_rshd() */

3303/* }}} */

3305/* {{{ s_mp_div_2(mp) */

3307/* Divide by two -- take advantage of radix properties to do it fast      */
3308void
3309s_mp_div_2(mp_int *mp)
3310{
  s_mp_div_2d(mp, 1);

3313} /* end s_mp_div_2() */

3315/* }}} */

3317/* {{{ s_mp_mul_2(mp) */

3319mp_err
3320s_mp_mul_2(mp_int *mp)
3321{
  mp_digit *pd;
  unsigned int ix, used;
  mp_digit kin = 0;

  ARGCHK(mp != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 3326
, __extension__ __PRETTY_FUNCTION__); }));

  /* Shift digits leftward by 1 bit */
  used = MP_USED(mp)((mp)->used);
  pd = MP_DIGITS(mp)((mp)->dp);
  for (ix = 0; ix < used; ix++) {
      mp_digit d = *pd;
      *pd++ = (d << 1) | kin;
      kin = (d >> (DIGIT_BIT(8 * sizeof(mp_digit)) - 1));
  }

  /* Deal with rollover from last digit */
  if (kin) {
      if (ix >= ALLOC(mp)((mp)->alloc)) {
          mp_err res;
          if ((res = s_mp_grow(mp, ALLOC(mp)((mp)->alloc) + 1)) != MP_OKAY0)
              return res;
      }

      DIGIT(mp, ix)(mp)->dp[(ix)] = kin;
      USED(mp)((mp)->used) += 1;
  }

  return MP_OKAY0;

3351} /* end s_mp_mul_2() */

3353/* }}} */

3355/* {{{ s_mp_mod_2d(mp, d) */

3357/*
Remainder the integer by 2^d, where d is a number of bits.  This
amounts to a bitwise AND of the value, and does not require the full
division code
*/
3362void
3363s_mp_mod_2d(mp_int *mp, mp_digit d)
3364{
  mp_size ndig = (d / DIGIT_BIT(8 * sizeof(mp_digit))), nbit = (d % DIGIT_BIT(8 * sizeof(mp_digit)));
  mp_size ix;
  mp_digit dmask;

  if (ndig >= USED(mp)((mp)->used))
      return;

  /* Flush all the bits above 2^d in its digit */
  dmask = ((mp_digit)1 << nbit) - 1;
  DIGIT(mp, ndig)(mp)->dp[(ndig)] &= dmask;

  /* Flush all digits above the one with 2^d in it */
  for (ix = ndig + 1; ix < USED(mp)((mp)->used); ix++)
      DIGIT(mp, ix)(mp)->dp[(ix)] = 0;

  s_mp_clamp(mp);

3382} /* end s_mp_mod_2d() */

3384/* }}} */

3386/* {{{ s_mp_div_2d(mp, d) */

3388/*
Divide the integer by 2^d, where d is a number of bits.  This
amounts to a bitwise shift of the value, and does not require the
full division code (used in Barrett reduction, see below)
*/
3393void
3394s_mp_div_2d(mp_int *mp, mp_digit d)
3395{
  int ix;
  mp_digit save, next, mask, lshift;

  s_mp_rshd(mp, d / DIGIT_BIT(8 * sizeof(mp_digit)));
  d %= DIGIT_BIT(8 * sizeof(mp_digit));
  /* mp_digit << lshift is undefined behavior for lshift >= MP_DIGIT_BIT */
  /* mod and corresponding mask logic avoid that when d = 0 */
  lshift = DIGIT_BIT(8 * sizeof(mp_digit)) - d;
  lshift %= DIGIT_BIT(8 * sizeof(mp_digit));
  mask = ((mp_digit)1 << d) - 1;
  save = 0;
  for (ix = USED(mp)((mp)->used) - 1; ix >= 0; ix--) {
      next = DIGIT(mp, ix)(mp)->dp[(ix)] & mask;
      DIGIT(mp, ix)(mp)->dp[(ix)] = (save << lshift) | (DIGIT(mp, ix)(mp)->dp[(ix)] >> d);
      save = next;
  }
  s_mp_clamp(mp);

3414} /* end s_mp_div_2d() */

3416/* }}} */

3418/* {{{ s_mp_norm(a, b, *d) */

3420/*
s_mp_norm(a, b, *d)

Normalize a and b for division, where b is the divisor.  In order
that we might make good guesses for quotient digits, we want the
leading digit of b to be at least half the radix, which we
accomplish by multiplying a and b by a power of 2.  The exponent
(shift count) is placed in *pd, so that the remainder can be shifted
back at the end of the division process.
*/

3431mp_err
3432s_mp_norm(mp_int *a, mp_int *b, mp_digit *pd)
3433{
  mp_digit d;
  mp_digit mask;
  mp_digit b_msd;
  mp_err res = MP_OKAY0;

  ARGCHK(a != NULL && b != NULL && pd != NULL, MP_BADARG)((void) sizeof ((a != ((void*)0) && b != ((void*)0) &&
 pd != ((void*)0)) ? 1 : 0), __extension__ ({ if (a != ((void
*)0) && b != ((void*)0) && pd != ((void*)0)) ;
 else __assert_fail ("a != ((void*)0) && b != ((void*)0) && pd != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 3439
, __extension__ __PRETTY_FUNCTION__); }));

  d = 0;
  mask = DIGIT_MAX(9223372036854775807L *2UL+1UL) & ~(DIGIT_MAX(9223372036854775807L *2UL+1UL) >> 1); /* mask is msb of digit */
  b_msd = DIGIT(b, USED(b) - 1)(b)->dp[(((b)->used) - 1)];
  while (!(b_msd & mask)) {
      b_msd <<= 1;
      ++d;
  }

  if (d) {
      MP_CHECKOK(s_mp_mul_2d(a, d))if (0 > (res = (s_mp_mul_2d(a, d)))) goto CLEANUP;
      MP_CHECKOK(s_mp_mul_2d(b, d))if (0 > (res = (s_mp_mul_2d(b, d)))) goto CLEANUP;
  }

  *pd = d;
3455CLEANUP:
  return res;

3458} /* end s_mp_norm() */

3460/* }}} */

3462/* }}} */

3464/* {{{ Primitive digit arithmetic */

3466/* {{{ s_mp_add_d(mp, d) */

3468/* Add d to |mp| in place                                                 */
3469mp_err
3470s_mp_add_d(mp_int *mp, mp_digit d) /* unsigned digit addition */
3471{
3472#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  mp_word w, k = 0;
  mp_size ix = 1;

  w = (mp_word)DIGIT(mp, 0)(mp)->dp[(0)] + d;
  DIGIT(mp, 0)(mp)->dp[(0)] = ACCUM(w)(mp_digit)(w);
  k = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));

  while (ix < USED(mp)((mp)->used) && k) {
      w = (mp_word)DIGIT(mp, ix)(mp)->dp[(ix)] + k;
      DIGIT(mp, ix)(mp)->dp[(ix)] = ACCUM(w)(mp_digit)(w);
      k = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
      ++ix;
  }

  if (k != 0) {
      mp_err res;

      if ((res = s_mp_pad(mp, USED(mp)((mp)->used) + 1)) != MP_OKAY0)
          return res;

      DIGIT(mp, ix)(mp)->dp[(ix)] = (mp_digit)k;
  }

  return MP_OKAY0;
3497#else
  mp_digit *pmp = MP_DIGITS(mp)((mp)->dp);
  mp_digit sum, mp_i, carry = 0;
  mp_err res = MP_OKAY0;
  int used = (int)MP_USED(mp)((mp)->used);

  mp_i = *pmp;
  *pmp++ = sum = d + mp_i;
  carry = (sum < d);
  while (carry && --used > 0) {
      mp_i = *pmp;
      *pmp++ = sum = carry + mp_i;
      carry = !sum;
  }
  if (carry && !used) {
      /* mp is growing */
      used = MP_USED(mp)((mp)->used);
      MP_CHECKOK(s_mp_pad(mp, used + 1))if (0 > (res = (s_mp_pad(mp, used + 1)))) goto CLEANUP;
      MP_DIGIT(mp, used)(mp)->dp[(used)] = carry;
  }
3517CLEANUP:
  return res;
3519#endif
3520} /* end s_mp_add_d() */

3522/* }}} */

3524/* {{{ s_mp_sub_d(mp, d) */

3526/* Subtract d from |mp| in place, assumes |mp| > d                        */
3527mp_err
3528s_mp_sub_d(mp_int *mp, mp_digit d) /* unsigned digit subtract */
3529{
3530#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
  mp_word w, b = 0;
  mp_size ix = 1;

  /* Compute initial subtraction    */
  w = (RADIX(1 + (mp_word)(9223372036854775807L *2UL+1UL)) + (mp_word)DIGIT(mp, 0)(mp)->dp[(0)]) - d;
  b = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit))) ? 0 : 1;
  DIGIT(mp, 0)(mp)->dp[(0)] = ACCUM(w)(mp_digit)(w);

  /* Propagate borrows leftward     */
  while (b && ix < USED(mp)((mp)->used)) {
      w = (RADIX(1 + (mp_word)(9223372036854775807L *2UL+1UL)) + (mp_word)DIGIT(mp, ix)(mp)->dp[(ix)]) - b;
      b = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit))) ? 0 : 1;
      DIGIT(mp, ix)(mp)->dp[(ix)] = ACCUM(w)(mp_digit)(w);
      ++ix;
  }

  /* Remove leading zeroes          */
  s_mp_clamp(mp);

  /* If we have a borrow out, it's a violation of the input invariant */
  if (b)
      return MP_RANGE-3;
  else
      return MP_OKAY0;
3555#else
  mp_digit *pmp = MP_DIGITS(mp)((mp)->dp);
  mp_digit mp_i, diff, borrow;
  mp_size used = MP_USED(mp)((mp)->used);

  mp_i = *pmp;
  *pmp++ = diff = mp_i - d;
  borrow = (diff > mp_i);
  while (borrow && --used) {
      mp_i = *pmp;
      *pmp++ = diff = mp_i - borrow;
      borrow = (diff > mp_i);
  }
  s_mp_clamp(mp);
  return (borrow && !used) ? MP_RANGE-3 : MP_OKAY0;
3570#endif
3571} /* end s_mp_sub_d() */

3573/* }}} */

3575/* {{{ s_mp_mul_d(a, d) */

3577/* Compute a = a * d, single digit multiplication                         */
3578mp_err
3579s_mp_mul_d(mp_int *a, mp_digit d)
3580{
  mp_err res;
  mp_size used;
  int pow;

  if (!d) {
      mp_zero(a);
      return MP_OKAY0;
  }
  if (d == 1)
      return MP_OKAY0;
  if (0 <= (pow = s_mp_ispow2d(d))) {
      return s_mp_mul_2d(a, (mp_digit)pow);
  }

  used = MP_USED(a)((a)->used);
  MP_CHECKOK(s_mp_pad(a, used + 1))if (0 > (res = (s_mp_pad(a, used + 1)))) goto CLEANUP;

  s_mpv_mul_d(MP_DIGITS(a), used, d, MP_DIGITS(a))((mp_digit *)((a)->dp))[used] = s_mpv_mul_set_vec64(((a)->
dp), ((a)->dp), used, d);

  s_mp_clamp(a);

3602CLEANUP:
  return res;

3605} /* end s_mp_mul_d() */

3607/* }}} */

3609/* {{{ s_mp_div_d(mp, d, r) */

3611/*
s_mp_div_d(mp, d, r)

Compute the quotient mp = mp / d and remainder r = mp mod d, for a
single digit d.  If r is null, the remainder will be discarded.
*/

3618mp_err
3619s_mp_div_d(mp_int *mp, mp_digit d, mp_digit *r)
3620{
3621#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_DIV_WORD)
  mp_word w = 0, q;
3623#else
  mp_digit w = 0, q;
3625#endif
  int ix;
  mp_err res;
  mp_int quot;
  mp_int rem;

  if (d == 0)
      return MP_RANGE-3;
  if (d == 1) {
      if (r)
          *r = 0;
      return MP_OKAY0;
  }
  /* could check for power of 2 here, but mp_div_d does that. */
  if (MP_USED(mp)((mp)->used) == 1) {
      mp_digit n = MP_DIGIT(mp, 0)(mp)->dp[(0)];
      mp_digit remdig;

      q = n / d;
      remdig = n % d;
      MP_DIGIT(mp, 0)(mp)->dp[(0)] = q;
      if (r) {
          *r = remdig;
      }
      return MP_OKAY0;
  }

  MP_DIGITS(&rem)((&rem)->dp) = 0;
  MP_DIGITS(&quot)((&quot)->dp) = 0;
  /* Make room for the quotient */
  MP_CHECKOK(mp_init_size(&quot, USED(mp)))if (0 > (res = (mp_init_size(&quot, ((mp)->used))))
) goto CLEANUP;

3657#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_DIV_WORD)
  for (ix = USED(mp)((mp)->used) - 1; ix >= 0; ix--) {
      w = (w << DIGIT_BIT(8 * sizeof(mp_digit))) | DIGIT(mp, ix)(mp)->dp[(ix)];

      if (w >= d) {
          q = w / d;
          w = w % d;
      } else {
          q = 0;
      }

      s_mp_lshd(&quot, 1);
      DIGIT(&quot, 0)(&quot)->dp[(0)] = (mp_digit)q;
  }
3671#else
  {
      mp_digit p;
3674#if !defined(MP_ASSEMBLY_DIV_2DX1D)
      mp_digit norm;
3676#endif

      MP_CHECKOK(mp_init_copy(&rem, mp))if (0 > (res = (mp_init_copy(&rem, mp)))) goto CLEANUP;

3680#if !defined(MP_ASSEMBLY_DIV_2DX1D)
      MP_DIGIT(&quot, 0)(&quot)->dp[(0)] = d;
      MP_CHECKOK(s_mp_norm(&rem, &quot, &norm))if (0 > (res = (s_mp_norm(&rem, &quot, &norm))
)) goto CLEANUP;
      if (norm)
          d <<= norm;
      MP_DIGIT(&quot, 0)(&quot)->dp[(0)] = 0;
3686#endif

      p = 0;
      for (ix = USED(&rem)((&rem)->used) - 1; ix >= 0; ix--) {
          w = DIGIT(&rem, ix)(&rem)->dp[(ix)];

          if (p) {
              MP_CHECKOK(s_mpv_div_2dx1d(p, w, d, &q, &w))if (0 > (res = (s_mpv_div_2dx1d(p, w, d, &q, &w)))
) goto CLEANUP;
          } else if (w >= d) {
              q = w / d;
              w = w % d;
          } else {
              q = 0;
          }

          MP_CHECKOK(s_mp_lshd(&quot, 1))if (0 > (res = (s_mp_lshd(&quot, 1)))) goto CLEANUP;
          DIGIT(&quot, 0)(&quot)->dp[(0)] = q;
          p = w;
      }
3705#if !defined(MP_ASSEMBLY_DIV_2DX1D)
      if (norm)
          w >>= norm;
3708#endif
  }
3710#endif

  /* Deliver the remainder, if desired */
  if (r) {
      *r = (mp_digit)w;
  }

  s_mp_clamp(&quot);
  mp_exch(&quot, mp);
3719CLEANUP:
  mp_clear(&quot);
  mp_clear(&rem);

  return res;
3724} /* end s_mp_div_d() */

3726/* }}} */

3728/* }}} */

3730/* {{{ Primitive full arithmetic */

3732/* {{{ s_mp_add(a, b) */

3734/* Compute a = |a| + |b|                                                  */
3735mp_err
3736s_mp_add(mp_int *a, const mp_int *b) /* magnitude addition      */
3737{
3738#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  mp_word w = 0;
3740#else
  mp_digit d, sum, carry = 0;
3742#endif
  mp_digit *pa, *pb;
  mp_size ix;
  mp_size used;
  mp_err res;

  /* Make sure a has enough precision for the output value */
  if ((USED(b)((b)->used) > USED(a)((a)->used)) && (res = s_mp_pad(a, USED(b)((b)->used))) != MP_OKAY0)
      return res;

  /*
    Add up all digits up to the precision of b.  If b had initially
    the same precision as a, or greater, we took care of it by the
    padding step above, so there is no problem.  If b had initially
    less precision, we'll have to make sure the carry out is duly
    propagated upward among the higher-order digits of the sum.
   */
  pa = MP_DIGITS(a)((a)->dp);
  pb = MP_DIGITS(b)((b)->dp);
  used = MP_USED(b)((b)->used);
  for (ix = 0; ix < used; ix++) {
3763#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
      w = w + *pa + *pb++;
      *pa++ = ACCUM(w)(mp_digit)(w);
      w = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
3767#else
      d = *pa;
      sum = d + *pb++;
      d = (sum < d); /* detect overflow */
      *pa++ = sum += carry;
      carry = d + (sum < carry); /* detect overflow */
3773#endif
  }

  /* If we run out of 'b' digits before we're actually done, make
     sure the carries get propagated upward...
   */
  used = MP_USED(a)((a)->used);
3780#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  while (w && ix < used) {
      w = w + *pa;
      *pa++ = ACCUM(w)(mp_digit)(w);
      w = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
      ++ix;
  }
3787#else
  while (carry && ix < used) {
      sum = carry + *pa;
      *pa++ = sum;
      carry = !sum;
      ++ix;
  }
3794#endif

3796/* If there's an overall carry out, increase precision and include
   it.  We could have done this initially, but why touch the memory
   allocator unless we're sure we have to?
 */
3800#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  if (w) {
      if ((res = s_mp_pad(a, used + 1)) != MP_OKAY0)
          return res;

      DIGIT(a, ix)(a)->dp[(ix)] = (mp_digit)w;
  }
3807#else
  if (carry) {
      if ((res = s_mp_pad(a, used + 1)) != MP_OKAY0)
          return res;

      DIGIT(a, used)(a)->dp[(used)] = carry;
  }
3814#endif

  return MP_OKAY0;
3817} /* end s_mp_add() */

3819/* }}} */

3821/* Compute c = |a| + |b|         */ /* magnitude addition      */
3822mp_err
3823s_mp_add_3arg(const mp_int *a, const mp_int *b, mp_int *c)
3824{
  mp_digit *pa, *pb, *pc;
3826#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  mp_word w = 0;
3828#else
  mp_digit sum, carry = 0, d;
3830#endif
  mp_size ix;
  mp_size used;
  mp_err res;

  MP_SIGN(c)((c)->sign) = MP_SIGN(a)((a)->sign);
  if (MP_USED(a)((a)->used) < MP_USED(b)((b)->used)) {
      const mp_int *xch = a;
      a = b;
      b = xch;
  }

  /* Make sure a has enough precision for the output value */
  if (MP_OKAY0 != (res = s_mp_pad(c, MP_USED(a)((a)->used))))
      return res;

  /*
   Add up all digits up to the precision of b.  If b had initially
   the same precision as a, or greater, we took care of it by the
   exchange step above, so there is no problem.  If b had initially
   less precision, we'll have to make sure the carry out is duly
   propagated upward among the higher-order digits of the sum.
  */
  pa = MP_DIGITS(a)((a)->dp);
  pb = MP_DIGITS(b)((b)->dp);
  pc = MP_DIGITS(c)((c)->dp);
  used = MP_USED(b)((b)->used);
  for (ix = 0; ix < used; ix++) {
3858#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
      w = w + *pa++ + *pb++;
      *pc++ = ACCUM(w)(mp_digit)(w);
      w = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
3862#else
      d = *pa++;
      sum = d + *pb++;
      d = (sum < d); /* detect overflow */
      *pc++ = sum += carry;
      carry = d + (sum < carry); /* detect overflow */
3868#endif
  }

  /* If we run out of 'b' digits before we're actually done, make
   sure the carries get propagated upward...
 */
  for (used = MP_USED(a)((a)->used); ix < used; ++ix) {
3875#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
      w = w + *pa++;
      *pc++ = ACCUM(w)(mp_digit)(w);
      w = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
3879#else
      *pc++ = sum = carry + *pa++;
      carry = (sum < carry);
3882#endif
  }

3885/* If there's an overall carry out, increase precision and include
   it.  We could have done this initially, but why touch the memory
   allocator unless we're sure we have to?
 */
3889#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  if (w) {
      if ((res = s_mp_pad(c, used + 1)) != MP_OKAY0)
          return res;

      DIGIT(c, used)(c)->dp[(used)] = (mp_digit)w;
      ++used;
  }
3897#else
  if (carry) {
      if ((res = s_mp_pad(c, used + 1)) != MP_OKAY0)
          return res;

      DIGIT(c, used)(c)->dp[(used)] = carry;
      ++used;
  }
3905#endif
  MP_USED(c)((c)->used) = used;
  return MP_OKAY0;
3908}
3909/* {{{ s_mp_add_offset(a, b, offset) */

3911/* Compute a = |a| + ( |b| * (RADIX ** offset) )             */
3912mp_err
3913s_mp_add_offset(mp_int *a, mp_int *b, mp_size offset)
3914{
3915#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  mp_word w, k = 0;
3917#else
  mp_digit d, sum, carry = 0;
3919#endif
  mp_size ib;
  mp_size ia;
  mp_size lim;
  mp_err res;

  /* Make sure a has enough precision for the output value */
  lim = MP_USED(b)((b)->used) + offset;
  if ((lim > USED(a)((a)->used)) && (res = s_mp_pad(a, lim)) != MP_OKAY0)
      return res;

  /*
  Add up all digits up to the precision of b.  If b had initially
  the same precision as a, or greater, we took care of it by the
  padding step above, so there is no problem.  If b had initially
  less precision, we'll have to make sure the carry out is duly
  propagated upward among the higher-order digits of the sum.
 */
  lim = USED(b)((b)->used);
  for (ib = 0, ia = offset; ib < lim; ib++, ia++) {
3939#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
      w = (mp_word)DIGIT(a, ia)(a)->dp[(ia)] + DIGIT(b, ib)(b)->dp[(ib)] + k;
      DIGIT(a, ia)(a)->dp[(ia)] = ACCUM(w)(mp_digit)(w);
      k = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
3943#else
      d = MP_DIGIT(a, ia)(a)->dp[(ia)];
      sum = d + MP_DIGIT(b, ib)(b)->dp[(ib)];
      d = (sum < d);
      MP_DIGIT(a, ia)(a)->dp[(ia)] = sum += carry;
      carry = d + (sum < carry);
3949#endif
  }

3952/* If we run out of 'b' digits before we're actually done, make
   sure the carries get propagated upward...
 */
3955#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  for (lim = MP_USED(a)((a)->used); k && (ia < lim); ++ia) {
      w = (mp_word)DIGIT(a, ia)(a)->dp[(ia)] + k;
      DIGIT(a, ia)(a)->dp[(ia)] = ACCUM(w)(mp_digit)(w);
      k = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
  }
3961#else
  for (lim = MP_USED(a)((a)->used); carry && (ia < lim); ++ia) {
      d = MP_DIGIT(a, ia)(a)->dp[(ia)];
      MP_DIGIT(a, ia)(a)->dp[(ia)] = sum = d + carry;
      carry = (sum < d);
  }
3967#endif

3969/* If there's an overall carry out, increase precision and include
   it.  We could have done this initially, but why touch the memory
   allocator unless we're sure we have to?
 */
3973#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_ADD_WORD)
  if (k) {
      if ((res = s_mp_pad(a, USED(a)((a)->used) + 1)) != MP_OKAY0)
          return res;

      DIGIT(a, ia)(a)->dp[(ia)] = (mp_digit)k;
  }
3980#else
  if (carry) {
      if ((res = s_mp_pad(a, lim + 1)) != MP_OKAY0)
          return res;

      DIGIT(a, lim)(a)->dp[(lim)] = carry;
  }
3987#endif
  s_mp_clamp(a);

  return MP_OKAY0;

3992} /* end s_mp_add_offset() */

3994/* }}} */

3996/* {{{ s_mp_sub(a, b) */

3998/* Compute a = |a| - |b|, assumes |a| >= |b|                              */
3999mp_err
4000s_mp_sub(mp_int *a, const mp_int *b) /* magnitude subtract      */
4001{
  mp_digit *pa, *pb, *limit;
4003#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
  mp_sword w = 0;
4005#else
  mp_digit d, diff, borrow = 0;
4007#endif

  /*
  Subtract and propagate borrow.  Up to the precision of b, this
  accounts for the digits of b; after that, we just make sure the
  carries get to the right place.  This saves having to pad b out to
  the precision of a just to make the loops work right...
 */
  pa = MP_DIGITS(a)((a)->dp);
  pb = MP_DIGITS(b)((b)->dp);
  limit = pb + MP_USED(b)((b)->used);
  while (pb < limit) {
4019#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
      w = w + *pa - *pb++;
      *pa++ = ACCUM(w)(mp_digit)(w);
      w >>= MP_DIGIT_BIT(8 * sizeof(mp_digit));
4023#else
      d = *pa;
      diff = d - *pb++;
      d = (diff > d); /* detect borrow */
      if (borrow && --diff == MP_DIGIT_MAX(9223372036854775807L *2UL+1UL))
          ++d;
      *pa++ = diff;
      borrow = d;
4031#endif
  }
  limit = MP_DIGITS(a)((a)->dp) + MP_USED(a)((a)->used);
4034#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
  while (w && pa < limit) {
      w = w + *pa;
      *pa++ = ACCUM(w)(mp_digit)(w);
      w >>= MP_DIGIT_BIT(8 * sizeof(mp_digit));
  }
4040#else
  while (borrow && pa < limit) {
      d = *pa;
      *pa++ = diff = d - borrow;
      borrow = (diff > d);
  }
4046#endif

  /* Clobber any leading zeroes we created    */
  s_mp_clamp(a);

4051/*
   If there was a borrow out, then |b| > |a| in violation
   of our input invariant.  We've already done the work,
   but we'll at least complain about it...
 */
4056#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
  return w ? MP_RANGE-3 : MP_OKAY0;
4058#else
  return borrow ? MP_RANGE-3 : MP_OKAY0;
4060#endif
4061} /* end s_mp_sub() */

4063/* }}} */

4065/* Compute c = |a| - |b|, assumes |a| >= |b| */ /* magnitude subtract      */
4066mp_err
4067s_mp_sub_3arg(const mp_int *a, const mp_int *b, mp_int *c)
4068{
  mp_digit *pa, *pb, *pc;
4070#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
  mp_sword w = 0;
4072#else
  mp_digit d, diff, borrow = 0;
4074#endif
  int ix, limit;
  mp_err res;

  MP_SIGN(c)((c)->sign) = MP_SIGN(a)((a)->sign);

  /* Make sure a has enough precision for the output value */
  if (MP_OKAY0 != (res = s_mp_pad(c, MP_USED(a)((a)->used))))
      return res;

  /*
  Subtract and propagate borrow.  Up to the precision of b, this
  accounts for the digits of b; after that, we just make sure the
  carries get to the right place.  This saves having to pad b out to
  the precision of a just to make the loops work right...
 */
  pa = MP_DIGITS(a)((a)->dp);
  pb = MP_DIGITS(b)((b)->dp);
  pc = MP_DIGITS(c)((c)->dp);
  limit = MP_USED(b)((b)->used);
  for (ix = 0; ix < limit; ++ix) {
4095#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
      w = w + *pa++ - *pb++;
      *pc++ = ACCUM(w)(mp_digit)(w);
      w >>= MP_DIGIT_BIT(8 * sizeof(mp_digit));
4099#else
      d = *pa++;
      diff = d - *pb++;
      d = (diff > d);
      if (borrow && --diff == MP_DIGIT_MAX(9223372036854775807L *2UL+1UL))
          ++d;
      *pc++ = diff;
      borrow = d;
4107#endif
  }
  for (limit = MP_USED(a)((a)->used); ix < limit; ++ix) {
4110#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
      w = w + *pa++;
      *pc++ = ACCUM(w)(mp_digit)(w);
      w >>= MP_DIGIT_BIT(8 * sizeof(mp_digit));
4114#else
      d = *pa++;
      *pc++ = diff = d - borrow;
      borrow = (diff > d);
4118#endif
  }

  /* Clobber any leading zeroes we created    */
  MP_USED(c)((c)->used) = ix;
  s_mp_clamp(c);

4125/*
   If there was a borrow out, then |b| > |a| in violation
   of our input invariant.  We've already done the work,
   but we'll at least complain about it...
 */
4130#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_SUB_WORD)
  return w ? MP_RANGE-3 : MP_OKAY0;
4132#else
  return borrow ? MP_RANGE-3 : MP_OKAY0;
4134#endif
4135}
4136/* {{{ s_mp_mul(a, b) */

4138/* Compute a = |a| * |b|                                                  */
4139mp_err
4140s_mp_mul(mp_int *a, const mp_int *b)
4141{
  return mp_mul(a, b, a);
4143} /* end s_mp_mul() */

4145/* }}} */

4147#if defined(MP_USE_UINT_DIGIT) && defined(MP_USE_LONG_LONG_MULTIPLY)
4148/* This trick works on Sparc V8 CPUs with the Workshop compilers. */
4149#define MP_MUL_DxD(a, b, Phi, Plo){ mp_digit a0b1, a1b0; Plo = (a & (2147483647 *2U +1U)) *
 (b & (2147483647 *2U +1U)); Phi = (a >> ((8 * sizeof
(mp_digit)) / 2)) * (b >> ((8 * sizeof(mp_digit)) / 2))
; a0b1 = (a & (2147483647 *2U +1U)) * (b >> ((8 * sizeof
(mp_digit)) / 2)); a1b0 = (a >> ((8 * sizeof(mp_digit))
 / 2)) * (b & (2147483647 *2U +1U)); a1b0 += a0b1; Phi +=
 a1b0 >> ((8 * sizeof(mp_digit)) / 2); Phi += (((((mp_digit
)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)
) - 1)))) ^ ((((mp_digit)((mp_digit)((a1b0) ^ (a0b1)) >>
 ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit)((mp_digit
)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)) - 1)))) ^
 ((((mp_digit)((mp_digit)(a0b1) >> ((8 * sizeof(mp_digit
)) - 1))))))))) << ((8 * sizeof(mp_digit)) / 2); a1b0 <<=
 ((8 * sizeof(mp_digit)) / 2); Plo += a1b0; Phi += ((((mp_digit
)((mp_digit)((Plo) - (a1b0)) >> ((8 * sizeof(mp_digit))
 - 1)))) ^ ((((mp_digit)((mp_digit)((Plo) ^ (a1b0)) >> (
(8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit)((mp_digit)
((Plo) - (a1b0)) >> ((8 * sizeof(mp_digit)) - 1)))) ^ (
(((mp_digit)((mp_digit)(a1b0) >> ((8 * sizeof(mp_digit)
) - 1)))))))); }                              \
  {                                                           \
      unsigned long long product = (unsigned long long)a * b; \
      Plo = (mp_digit)product;                                \
      Phi = (mp_digit)(product >> MP_DIGIT_BIT(8 * sizeof(mp_digit)));              \
  }
4155#else
4156#define MP_MUL_DxD(a, b, Phi, Plo){ mp_digit a0b1, a1b0; Plo = (a & (2147483647 *2U +1U)) *
 (b & (2147483647 *2U +1U)); Phi = (a >> ((8 * sizeof
(mp_digit)) / 2)) * (b >> ((8 * sizeof(mp_digit)) / 2))
; a0b1 = (a & (2147483647 *2U +1U)) * (b >> ((8 * sizeof
(mp_digit)) / 2)); a1b0 = (a >> ((8 * sizeof(mp_digit))
 / 2)) * (b & (2147483647 *2U +1U)); a1b0 += a0b1; Phi +=
 a1b0 >> ((8 * sizeof(mp_digit)) / 2); Phi += (((((mp_digit
)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)
) - 1)))) ^ ((((mp_digit)((mp_digit)((a1b0) ^ (a0b1)) >>
 ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit)((mp_digit
)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)) - 1)))) ^
 ((((mp_digit)((mp_digit)(a0b1) >> ((8 * sizeof(mp_digit
)) - 1))))))))) << ((8 * sizeof(mp_digit)) / 2); a1b0 <<=
 ((8 * sizeof(mp_digit)) / 2); Plo += a1b0; Phi += ((((mp_digit
)((mp_digit)((Plo) - (a1b0)) >> ((8 * sizeof(mp_digit))
 - 1)))) ^ ((((mp_digit)((mp_digit)((Plo) ^ (a1b0)) >> (
(8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit)((mp_digit)
((Plo) - (a1b0)) >> ((8 * sizeof(mp_digit)) - 1)))) ^ (
(((mp_digit)((mp_digit)(a1b0) >> ((8 * sizeof(mp_digit)
) - 1)))))))); }                                 \
  {                                                              \
      mp_digit a0b1, a1b0;                                       \
      Plo = (a & MP_HALF_DIGIT_MAX(2147483647 *2U +1U)) * (b & MP_HALF_DIGIT_MAX(2147483647 *2U +1U));   \
      Phi = (a >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)) * (b >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)); \
      a0b1 = (a & MP_HALF_DIGIT_MAX(2147483647 *2U +1U)) * (b >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)); \
      a1b0 = (a >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)) * (b & MP_HALF_DIGIT_MAX(2147483647 *2U +1U)); \
      a1b0 += a0b1;                                              \
      Phi += a1b0 >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2);                          \
      Phi += (MP_CT_LTU(a1b0, a0b1)((((mp_digit)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a1b0) ^ (a0b1
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)
) - 1)))) ^ ((((mp_digit)((mp_digit)(a0b1) >> ((8 * sizeof
(mp_digit)) - 1))))))))) << MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2);       \
      a1b0 <<= MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2);                                \
      Plo += a1b0;                                               \
      Phi += MP_CT_LTU(Plo, a1b0)((((mp_digit)((mp_digit)((Plo) - (a1b0)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((Plo) ^ (a1b0)
) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((Plo) - (a1b0)) >> ((8 * sizeof(mp_digit))
 - 1)))) ^ ((((mp_digit)((mp_digit)(a1b0) >> ((8 * sizeof
(mp_digit)) - 1))))))));                               \
  }
4170#endif

4172/* Constant time version of s_mpv_mul_d_add_prop.
* Presently, this is only used by the Constant time Montgomery arithmetic code. */
4174/* c += a * b */
4175void
4176s_mpv_mul_d_add_propCT(const mp_digit *a, mp_size a_len, mp_digit b,
                     mp_digit *c, mp_size c_len)
4178{
4179#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_MUL_WORD)
  mp_digit d = 0;

  c_len -= a_len;
  /* Inner product:  Digits of a */
  while (a_len--) {
      mp_word w = ((mp_word)b * *a++) + *c + d;
      *c++ = ACCUM(w)(mp_digit)(w);
      d = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
  }

  /* propagate the carry to the end, even if carry is zero */
  while (c_len--) {
      mp_word w = (mp_word)*c + d;
      *c++ = ACCUM(w)(mp_digit)(w);
      d = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
  }
4196#else
  mp_digit carry = 0;
  c_len -= a_len;
  while (a_len--) {
      mp_digit a_i = *a++;
      mp_digit a0b0, a1b1;
      MP_MUL_DxD(a_i, b, a1b1, a0b0){ mp_digit a0b1, a1b0; a0b0 = (a_i & (2147483647 *2U +1U)
) * (b & (2147483647 *2U +1U)); a1b1 = (a_i >> ((8 *
 sizeof(mp_digit)) / 2)) * (b >> ((8 * sizeof(mp_digit)
) / 2)); a0b1 = (a_i & (2147483647 *2U +1U)) * (b >>
 ((8 * sizeof(mp_digit)) / 2)); a1b0 = (a_i >> ((8 * sizeof
(mp_digit)) / 2)) * (b & (2147483647 *2U +1U)); a1b0 += a0b1
; a1b1 += a1b0 >> ((8 * sizeof(mp_digit)) / 2); a1b1 +=
 (((((mp_digit)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a1b0) ^ (a0b1
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)
) - 1)))) ^ ((((mp_digit)((mp_digit)(a0b1) >> ((8 * sizeof
(mp_digit)) - 1))))))))) << ((8 * sizeof(mp_digit)) / 2
); a1b0 <<= ((8 * sizeof(mp_digit)) / 2); a0b0 += a1b0;
 a1b1 += ((((mp_digit)((mp_digit)((a0b0) - (a1b0)) >> (
(8 * sizeof(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0
) ^ (a1b0)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((
((mp_digit)((mp_digit)((a0b0) - (a1b0)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)(a1b0) >>
 ((8 * sizeof(mp_digit)) - 1)))))))); };

      a0b0 += carry;
      a1b1 += MP_CT_LTU(a0b0, carry)((((mp_digit)((mp_digit)((a0b0) - (carry)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0) ^ (carry
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a0b0) - (carry)) >> ((8 * sizeof(mp_digit
)) - 1)))) ^ ((((mp_digit)((mp_digit)(carry) >> ((8 * sizeof
(mp_digit)) - 1))))))));
      a0b0 += a_i = *c;
      a1b1 += MP_CT_LTU(a0b0, a_i)((((mp_digit)((mp_digit)((a0b0) - (a_i)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0) ^ (a_i)
) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a0b0) - (a_i)) >> ((8 * sizeof(mp_digit))
 - 1)))) ^ ((((mp_digit)((mp_digit)(a_i) >> ((8 * sizeof
(mp_digit)) - 1))))))));

      *c++ = a0b0;
      carry = a1b1;
  }
  /* propagate the carry to the end, even if carry is zero */
  while (c_len--) {
      mp_digit c_i = *c;
      carry += c_i;
      *c++ = carry;
      carry = MP_CT_LTU(carry, c_i)((((mp_digit)((mp_digit)((carry) - (c_i)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((carry) ^ (c_i
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((carry) - (c_i)) >> ((8 * sizeof(mp_digit)
) - 1)))) ^ ((((mp_digit)((mp_digit)(c_i) >> ((8 * sizeof
(mp_digit)) - 1))))))));
  }
4219#endif
4220}

4222#if !defined(MP_ASSEMBLY_MULTIPLY1)
4223/* c = a * b */
4224void
4225s_mpv_mul_d(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *c)((mp_digit *)mp_digit *c)[mp_size a_len] = s_mpv_mul_set_vec64
(mp_digit *c, const mp_digit *a, mp_size a_len, mp_digit b)
4226{
4227#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_MUL_WORD)
  mp_digit d = 0;

  /* Inner product:  Digits of a */
  while (a_len--) {
      mp_word w = ((mp_word)b * *a++) + d;
      *c++ = ACCUM(w)(mp_digit)(w);
      d = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
  }
  *c = d;
4237#else
  mp_digit carry = 0;
  while (a_len--) {
      mp_digit a_i = *a++;
      mp_digit a0b0, a1b1;

      MP_MUL_DxD(a_i, b, a1b1, a0b0){ mp_digit a0b1, a1b0; a0b0 = (a_i & (2147483647 *2U +1U)
) * (b & (2147483647 *2U +1U)); a1b1 = (a_i >> ((8 *
 sizeof(mp_digit)) / 2)) * (b >> ((8 * sizeof(mp_digit)
) / 2)); a0b1 = (a_i & (2147483647 *2U +1U)) * (b >>
 ((8 * sizeof(mp_digit)) / 2)); a1b0 = (a_i >> ((8 * sizeof
(mp_digit)) / 2)) * (b & (2147483647 *2U +1U)); a1b0 += a0b1
; a1b1 += a1b0 >> ((8 * sizeof(mp_digit)) / 2); a1b1 +=
 (((((mp_digit)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a1b0) ^ (a0b1
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)
) - 1)))) ^ ((((mp_digit)((mp_digit)(a0b1) >> ((8 * sizeof
(mp_digit)) - 1))))))))) << ((8 * sizeof(mp_digit)) / 2
); a1b0 <<= ((8 * sizeof(mp_digit)) / 2); a0b0 += a1b0;
 a1b1 += ((((mp_digit)((mp_digit)((a0b0) - (a1b0)) >> (
(8 * sizeof(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0
) ^ (a1b0)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((
((mp_digit)((mp_digit)((a0b0) - (a1b0)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)(a1b0) >>
 ((8 * sizeof(mp_digit)) - 1)))))))); };

      a0b0 += carry;
      a1b1 += MP_CT_LTU(a0b0, carry)((((mp_digit)((mp_digit)((a0b0) - (carry)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0) ^ (carry
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a0b0) - (carry)) >> ((8 * sizeof(mp_digit
)) - 1)))) ^ ((((mp_digit)((mp_digit)(carry) >> ((8 * sizeof
(mp_digit)) - 1))))))));
      *c++ = a0b0;
      carry = a1b1;
  }
  *c = carry;
4251#endif
4252}

4254/* c += a * b */
4255void
4256s_mpv_mul_d_add(const mp_digit *a, mp_size a_len, mp_digit b,((mp_digit *)mp_digit *c)[mp_size a_len] = s_mpv_mul_add_vec64
(mp_digit *c, const mp_digit *a, mp_size a_len, mp_digit b)
              mp_digit *c)((mp_digit *)mp_digit *c)[mp_size a_len] = s_mpv_mul_add_vec64
(mp_digit *c, const mp_digit *a, mp_size a_len, mp_digit b)
4258{
4259#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_MUL_WORD)
  mp_digit d = 0;

  /* Inner product:  Digits of a */
  while (a_len--) {
      mp_word w = ((mp_word)b * *a++) + *c + d;
      *c++ = ACCUM(w)(mp_digit)(w);
      d = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
  }
  *c = d;
4269#else
  mp_digit carry = 0;
  while (a_len--) {
      mp_digit a_i = *a++;
      mp_digit a0b0, a1b1;

      MP_MUL_DxD(a_i, b, a1b1, a0b0){ mp_digit a0b1, a1b0; a0b0 = (a_i & (2147483647 *2U +1U)
) * (b & (2147483647 *2U +1U)); a1b1 = (a_i >> ((8 *
 sizeof(mp_digit)) / 2)) * (b >> ((8 * sizeof(mp_digit)
) / 2)); a0b1 = (a_i & (2147483647 *2U +1U)) * (b >>
 ((8 * sizeof(mp_digit)) / 2)); a1b0 = (a_i >> ((8 * sizeof
(mp_digit)) / 2)) * (b & (2147483647 *2U +1U)); a1b0 += a0b1
; a1b1 += a1b0 >> ((8 * sizeof(mp_digit)) / 2); a1b1 +=
 (((((mp_digit)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a1b0) ^ (a0b1
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)
) - 1)))) ^ ((((mp_digit)((mp_digit)(a0b1) >> ((8 * sizeof
(mp_digit)) - 1))))))))) << ((8 * sizeof(mp_digit)) / 2
); a1b0 <<= ((8 * sizeof(mp_digit)) / 2); a0b0 += a1b0;
 a1b1 += ((((mp_digit)((mp_digit)((a0b0) - (a1b0)) >> (
(8 * sizeof(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0
) ^ (a1b0)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((
((mp_digit)((mp_digit)((a0b0) - (a1b0)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)(a1b0) >>
 ((8 * sizeof(mp_digit)) - 1)))))))); };

      a0b0 += carry;
      a1b1 += MP_CT_LTU(a0b0, carry)((((mp_digit)((mp_digit)((a0b0) - (carry)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0) ^ (carry
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a0b0) - (carry)) >> ((8 * sizeof(mp_digit
)) - 1)))) ^ ((((mp_digit)((mp_digit)(carry) >> ((8 * sizeof
(mp_digit)) - 1))))))));
      a0b0 += a_i = *c;
      a1b1 += MP_CT_LTU(a0b0, a_i)((((mp_digit)((mp_digit)((a0b0) - (a_i)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0) ^ (a_i)
) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a0b0) - (a_i)) >> ((8 * sizeof(mp_digit))
 - 1)))) ^ ((((mp_digit)((mp_digit)(a_i) >> ((8 * sizeof
(mp_digit)) - 1))))))));
      *c++ = a0b0;
      carry = a1b1;
  }
  *c = carry;
4285#endif
4286}

4288/* Presently, this is only used by the Montgomery arithmetic code. */
4289/* c += a * b */
4290void
4291s_mpv_mul_d_add_prop(const mp_digit *a, mp_size a_len, mp_digit b, mp_digit *c)
4292{
4293#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_MUL_WORD)
  mp_digit d = 0;

  /* Inner product:  Digits of a */
  while (a_len--) {
      mp_word w = ((mp_word)b * *a++) + *c + d;
      *c++ = ACCUM(w)(mp_digit)(w);
      d = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
  }

  while (d) {
      mp_word w = (mp_word)*c + d;
      *c++ = ACCUM(w)(mp_digit)(w);
      d = CARRYOUT(w)(mp_digit)((w) >> (8 * sizeof(mp_digit)));
  }
4308#else
  mp_digit carry = 0;
  while (a_len--) {
      mp_digit a_i = *a++;
      mp_digit a0b0, a1b1;

      MP_MUL_DxD(a_i, b, a1b1, a0b0){ mp_digit a0b1, a1b0; a0b0 = (a_i & (2147483647 *2U +1U)
) * (b & (2147483647 *2U +1U)); a1b1 = (a_i >> ((8 *
 sizeof(mp_digit)) / 2)) * (b >> ((8 * sizeof(mp_digit)
) / 2)); a0b1 = (a_i & (2147483647 *2U +1U)) * (b >>
 ((8 * sizeof(mp_digit)) / 2)); a1b0 = (a_i >> ((8 * sizeof
(mp_digit)) / 2)) * (b & (2147483647 *2U +1U)); a1b0 += a0b1
; a1b1 += a1b0 >> ((8 * sizeof(mp_digit)) / 2); a1b1 +=
 (((((mp_digit)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a1b0) ^ (a0b1
)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((((mp_digit
)((mp_digit)((a1b0) - (a0b1)) >> ((8 * sizeof(mp_digit)
) - 1)))) ^ ((((mp_digit)((mp_digit)(a0b1) >> ((8 * sizeof
(mp_digit)) - 1))))))))) << ((8 * sizeof(mp_digit)) / 2
); a1b0 <<= ((8 * sizeof(mp_digit)) / 2); a0b0 += a1b0;
 a1b1 += ((((mp_digit)((mp_digit)((a0b0) - (a1b0)) >> (
(8 * sizeof(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)((a0b0
) ^ (a1b0)) >> ((8 * sizeof(mp_digit)) - 1)))) & ((
((mp_digit)((mp_digit)((a0b0) - (a1b0)) >> ((8 * sizeof
(mp_digit)) - 1)))) ^ ((((mp_digit)((mp_digit)(a1b0) >>
 ((8 * sizeof(mp_digit)) - 1)))))))); };

      a0b0 += carry;
      if (a0b0 < carry)
          ++a1b1;

      a0b0 += a_i = *c;
      if (a0b0 < a_i)
          ++a1b1;

      *c++ = a0b0;
      carry = a1b1;
  }
  while (carry) {
      mp_digit c_i = *c;
      carry += c_i;
      *c++ = carry;
      carry = carry < c_i;
  }
4333#endif
4334}
4335#endif

4337#if defined(MP_USE_UINT_DIGIT) && defined(MP_USE_LONG_LONG_MULTIPLY)
4338/* This trick works on Sparc V8 CPUs with the Workshop compilers. */
4339#define MP_SQR_D(a, Phi, Plo){ mp_digit Pmid; Plo = (a & (2147483647 *2U +1U)) * (a &
 (2147483647 *2U +1U)); Phi = (a >> ((8 * sizeof(mp_digit
)) / 2)) * (a >> ((8 * sizeof(mp_digit)) / 2)); Pmid = (
a & (2147483647 *2U +1U)) * (a >> ((8 * sizeof(mp_digit
)) / 2)); Phi += Pmid >> (((8 * sizeof(mp_digit)) / 2) -
 1); Pmid <<= (((8 * sizeof(mp_digit)) / 2) + 1); Plo +=
 Pmid; if (Plo < Pmid) ++Phi; }                                  \
  {                                                          \
      unsigned long long square = (unsigned long long)a * a; \
      Plo = (mp_digit)square;                                \
      Phi = (mp_digit)(square >> MP_DIGIT_BIT(8 * sizeof(mp_digit)));              \
  }
4345#else
4346#define MP_SQR_D(a, Phi, Plo){ mp_digit Pmid; Plo = (a & (2147483647 *2U +1U)) * (a &
 (2147483647 *2U +1U)); Phi = (a >> ((8 * sizeof(mp_digit
)) / 2)) * (a >> ((8 * sizeof(mp_digit)) / 2)); Pmid = (
a & (2147483647 *2U +1U)) * (a >> ((8 * sizeof(mp_digit
)) / 2)); Phi += Pmid >> (((8 * sizeof(mp_digit)) / 2) -
 1); Pmid <<= (((8 * sizeof(mp_digit)) / 2) + 1); Plo +=
 Pmid; if (Plo < Pmid) ++Phi; }                                      \
  {                                                              \
      mp_digit Pmid;                                             \
      Plo = (a & MP_HALF_DIGIT_MAX(2147483647 *2U +1U)) * (a & MP_HALF_DIGIT_MAX(2147483647 *2U +1U));   \
      Phi = (a >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)) * (a >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)); \
      Pmid = (a & MP_HALF_DIGIT_MAX(2147483647 *2U +1U)) * (a >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)); \
      Phi += Pmid >> (MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2) - 1);                    \
      Pmid <<= (MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2) + 1);                          \
      Plo += Pmid;                                               \
      if (Plo < Pmid)                                            \
          ++Phi;                                                 \
  }
4358#endif

4360#if !defined(MP_ASSEMBLY_SQUARE)
4361/* Add the squares of the digits of a to the digits of b. */
4362void
4363s_mpv_sqr_add_prop(const mp_digit *pa, mp_size a_len, mp_digit *ps)
4364{
4365#if !defined(MP_NO_MP_WORD1) && !defined(MP_NO_MUL_WORD)
  mp_word w;
  mp_digit d;
  mp_size ix;

  w = 0;
4371#define ADD_SQUARE(n)                     \
  d = pa[n];                            \
  w += (d * (mp_word)d) + ps[2 * n];    \
  ps[2 * n] = ACCUM(w)(mp_digit)(w);                 \
  w = (w >> DIGIT_BIT(8 * sizeof(mp_digit))) + ps[2 * n + 1]; \
  ps[2 * n + 1] = ACCUM(w)(mp_digit)(w);             \
  w = (w >> DIGIT_BIT(8 * sizeof(mp_digit)))

  for (ix = a_len; ix >= 4; ix -= 4) {
      ADD_SQUARE(0);
      ADD_SQUARE(1);
      ADD_SQUARE(2);
      ADD_SQUARE(3);
      pa += 4;
      ps += 8;
  }
  if (ix) {
      ps += 2 * ix;
      pa += ix;
      switch (ix) {
          case 3:
              ADD_SQUARE(-3); /* FALLTHRU */
          case 2:
              ADD_SQUARE(-2); /* FALLTHRU */
          case 1:
              ADD_SQUARE(-1); /* FALLTHRU */
          case 0:
              break;
      }
  }
  while (w) {
      w += *ps;
      *ps++ = ACCUM(w)(mp_digit)(w);
      w = (w >> DIGIT_BIT(8 * sizeof(mp_digit)));
  }
4406#else
  mp_digit carry = 0;
  while (a_len--) {
      mp_digit a_i = *pa++;
      mp_digit a0a0, a1a1;

      MP_SQR_D(a_i, a1a1, a0a0){ mp_digit Pmid; a0a0 = (a_i & (2147483647 *2U +1U)) * (a_i
 & (2147483647 *2U +1U)); a1a1 = (a_i >> ((8 * sizeof
(mp_digit)) / 2)) * (a_i >> ((8 * sizeof(mp_digit)) / 2
)); Pmid = (a_i & (2147483647 *2U +1U)) * (a_i >> (
(8 * sizeof(mp_digit)) / 2)); a1a1 += Pmid >> (((8 * sizeof
(mp_digit)) / 2) - 1); Pmid <<= (((8 * sizeof(mp_digit)
) / 2) + 1); a0a0 += Pmid; if (a0a0 < Pmid) ++a1a1; };

      /* here a1a1 and a0a0 constitute a_i ** 2 */
      a0a0 += carry;
      if (a0a0 < carry)
          ++a1a1;

      /* now add to ps */
      a0a0 += a_i = *ps;
      if (a0a0 < a_i)
          ++a1a1;
      *ps++ = a0a0;
      a1a1 += a_i = *ps;
      carry = (a1a1 < a_i);
      *ps++ = a1a1;
  }
  while (carry) {
      mp_digit s_i = *ps;
      carry += s_i;
      *ps++ = carry;
      carry = carry < s_i;
  }
4434#endif
4435}
4436#endif

4438#if !defined(MP_ASSEMBLY_DIV_2DX1D)
4439/*
4440** Divide 64-bit (Nhi,Nlo) by 32-bit divisor, which must be normalized
4441** so its high bit is 1.   This code is from NSPR.
4442*/
4443mp_err
4444s_mpv_div_2dx1d(mp_digit Nhi, mp_digit Nlo, mp_digit divisor,
              mp_digit *qp, mp_digit *rp)
4446{
  mp_digit d1, d0, q1, q0;
  mp_digit r1, r0, m;

  d1 = divisor >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2);
  d0 = divisor & MP_HALF_DIGIT_MAX(2147483647 *2U +1U);
  r1 = Nhi % d1;
  q1 = Nhi / d1;
  m = q1 * d0;
  r1 = (r1 << MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)) | (Nlo >> MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2));
  if (r1 < m) {
      q1--, r1 += divisor;
      if (r1 >= divisor && r1 < m) {
          q1--, r1 += divisor;
      }
  }
  r1 -= m;
  r0 = r1 % d1;
  q0 = r1 / d1;
  m = q0 * d0;
  r0 = (r0 << MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)) | (Nlo & MP_HALF_DIGIT_MAX(2147483647 *2U +1U));
  if (r0 < m) {
      q0--, r0 += divisor;
      if (r0 >= divisor && r0 < m) {
          q0--, r0 += divisor;
      }
  }
  if (qp)
      *qp = (q1 << MP_HALF_DIGIT_BIT((8 * sizeof(mp_digit)) / 2)) | q0;
  if (rp)
      *rp = r0 - m;
  return MP_OKAY0;
4478}
4479#endif

4481#if MP_SQUARE1
4482/* {{{ s_mp_sqr(a) */

4484mp_err
4485s_mp_sqr(mp_int *a)
4486{
  mp_err res;
  mp_int tmp;

  if ((res = mp_init_size(&tmp, 2 * USED(a)((a)->used))) != MP_OKAY0)
      return res;
  res = mp_sqr(a, &tmp);
  if (res == MP_OKAY0) {
      s_mp_exch(&tmp, a);
  }
  mp_clear(&tmp);
  return res;
4498}

4500/* }}} */
4501#endif

4503/* {{{ s_mp_div(a, b) */

4505/*
s_mp_div(a, b)

Compute a = a / b and b = a mod b.  Assumes b > a.
*/

4511mp_err
4512s_mp_div(mp_int *rem,  /* i: dividend, o: remainder */
       mp_int *div,  /* i: divisor                */
       mp_int *quot) /* i: 0;        o: quotient  */
4515{
  mp_int part, t;
  mp_digit q_msd;
  mp_err res;
  mp_digit d;
  mp_digit div_msd;
  int ix;

  if (mp_cmp_z(div) == 0)
      return MP_RANGE-3;

  DIGITS(&t)((&t)->dp) = 0;
  /* Shortcut if divisor is power of two */
  if ((ix = s_mp_ispow2(div)) >= 0) {
      MP_CHECKOK(mp_copy(rem, quot))if (0 > (res = (mp_copy(rem, quot)))) goto CLEANUP;
      s_mp_div_2d(quot, (mp_digit)ix);
      s_mp_mod_2d(rem, (mp_digit)ix);

      return MP_OKAY0;
  }

  MP_SIGN(rem)((rem)->sign) = ZPOS0;
  MP_SIGN(div)((div)->sign) = ZPOS0;
  MP_SIGN(&part)((&part)->sign) = ZPOS0;

  /* A working temporary for division     */
  MP_CHECKOK(mp_init_size(&t, MP_ALLOC(rem)))if (0 > (res = (mp_init_size(&t, ((rem)->alloc)))))
 goto CLEANUP;

  /* Normalize to optimize guessing       */
  MP_CHECKOK(s_mp_norm(rem, div, &d))if (0 > (res = (s_mp_norm(rem, div, &d)))) goto CLEANUP;

  /* Perform the division itself...woo!   */
  MP_USED(quot)((quot)->used) = MP_ALLOC(quot)((quot)->alloc);

  /* 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)((rem)->used) > MP_USED(div)((div)->used) || 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)((rem)->used) - MP_USED(div)((div)->used);
      MP_DIGITS(&part)((&part)->dp) = MP_DIGITS(rem)((rem)->dp) + unusedRem;
      MP_ALLOC(&part)((&part)->alloc) = MP_ALLOC(rem)((rem)->alloc) - unusedRem;
      MP_USED(&part)((&part)->used) = MP_USED(div)((div)->used);

      /* 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;
4565#if MP_ARGCHK2 == 2
          assert(unusedRem >= 0)((void) sizeof ((unusedRem >= 0) ? 1 : 0), __extension__ (
{ if (unusedRem >= 0) ; else __assert_fail ("unusedRem >= 0"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 4566
, __extension__ __PRETTY_FUNCTION__); }));
4567#endif
          --MP_DIGITS(&part)((&part)->dp);
          ++MP_USED(&part)((&part)->used);
          ++MP_ALLOC(&part)((&part)->alloc);
          partExtended = 1;
      }

      /* Compute a guess for the next quotient digit       */
      q_msd = MP_DIGIT(&part, MP_USED(&part) - 1)(&part)->dp[(((&part)->used) - 1)];
      div_msd = MP_DIGIT(div, MP_USED(div) - 1)(div)->dp[(((div)->used) - 1)];
      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 (q_msd == div_msd) {
              q_msd = MP_DIGIT_MAX(9223372036854775807L *2UL+1UL);
          } else {
              mp_digit r;
              MP_CHECKOK(s_mpv_div_2dx1d(q_msd, MP_DIGIT(&part, MP_USED(&part) - 2),if (0 > (res = (s_mpv_div_2dx1d(q_msd, (&part)->dp[
(((&part)->used) - 2)], div_msd, &q_msd, &r)))
) goto CLEANUP
                                         div_msd, &q_msd, &r))if (0 > (res = (s_mpv_div_2dx1d(q_msd, (&part)->dp[
(((&part)->used) - 2)], div_msd, &q_msd, &r)))
) goto CLEANUP;
          }
      }
4593#if MP_ARGCHK2 == 2
      assert(q_msd > 0)((void) sizeof ((q_msd > 0) ? 1 : 0), __extension__ ({ if (
q_msd > 0) ; else __assert_fail ("q_msd > 0", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 4594, __extension__ __PRETTY_FUNCTION__); })); /* This case should never occur any more. */
4595#endif
      if (q_msd <= 0)
          break;

      /* See what that multiplies out to                   */
      mp_copy(div, &t);
      MP_CHECKOK(s_mp_mul_d(&t, q_msd))if (0 > (res = (s_mp_mul_d(&t, q_msd)))) goto CLEANUP;

      /*
         If it's too big, back it off.  We should not have to do this
         more than once, or, in rare cases, twice.  Knuth describes a
         method by which this could be reduced to a maximum of once, but
         I didn't implement that here.
         When using s_mpv_div_2dx1d, we may have to do this 3 times.
       */
      for (i = 4; s_mp_cmp(&t, &part) > 0 && i > 0; --i) {
          --q_msd;
          MP_CHECKOK(s_mp_sub(&t, div))if (0 > (res = (s_mp_sub(&t, div)))) goto CLEANUP; /* t -= div */
      }
      if (i < 0) {
          res = MP_RANGE-3;
          goto CLEANUP;
      }

      /* At this point, q_msd should be the right next digit   */
      MP_CHECKOK(s_mp_sub(&part, &t))if (0 > (res = (s_mp_sub(&part, &t)))) goto CLEANUP; /* part -= t */
      s_mp_clamp(rem);

      /*
        Include the digit in the quotient.  We allocated enough memory
        for any quotient we could ever possibly get, so we should not
        have to check for failures here
       */
      MP_DIGIT(quot, unusedRem)(quot)->dp[(unusedRem)] = q_msd;
  }

  /* Denormalize remainder                */
  if (d) {
      s_mp_div_2d(rem, d);
  }

  s_mp_clamp(quot);

4638CLEANUP:
  mp_clear(&t);

  return res;

4643} /* end s_mp_div() */

4645/* }}} */

4647/* {{{ s_mp_2expt(a, k) */

4649mp_err
4650s_mp_2expt(mp_int *a, mp_digit k)
4651{
  mp_err res;
  mp_size dig, bit;

  dig = k / DIGIT_BIT(8 * sizeof(mp_digit));
  bit = k % DIGIT_BIT(8 * sizeof(mp_digit));

  mp_zero(a);
  if ((res = s_mp_pad(a, dig + 1)) != MP_OKAY0)
      return res;

  DIGIT(a, dig)(a)->dp[(dig)] |= ((mp_digit)1 << bit);

  return MP_OKAY0;

4666} /* end s_mp_2expt() */

4668/* }}} */

4670/* {{{ s_mp_reduce(x, m, mu) */

4672/*
Compute Barrett reduction, x (mod m), given a precomputed value for
mu = b^2k / m, where b = RADIX and k = #digits(m).  This should be
faster than straight division, when many reductions by the same
value of m are required (such as in modular exponentiation).  This
can nearly halve the time required to do modular exponentiation,
as compared to using the full integer divide to reduce.

This algorithm was derived from the _Handbook of Applied
Cryptography_ by Menezes, Oorschot and VanStone, Ch. 14,
pp. 603-604.
*/

4685mp_err
4686s_mp_reduce(mp_int *x, const mp_int *m, const mp_int *mu)
4687{
  mp_int q;
  mp_err res;

  if ((res = mp_init_copy(&q, x)) != MP_OKAY0)
      return res;

  s_mp_rshd(&q, USED(m)((m)->used) - 1); /* q1 = x / b^(k-1)  */
  s_mp_mul(&q, mu);           /* q2 = q1 * mu      */
  s_mp_rshd(&q, USED(m)((m)->used) + 1); /* q3 = q2 / b^(k+1) */

  /* x = x mod b^(k+1), quick (no division) */
  s_mp_mod_2d(x, DIGIT_BIT(8 * sizeof(mp_digit)) * (USED(m)((m)->used) + 1));

  /* q = q * m mod b^(k+1), quick (no division) */
  s_mp_mul(&q, m);
  s_mp_mod_2d(&q, DIGIT_BIT(8 * sizeof(mp_digit)) * (USED(m)((m)->used) + 1));

  /* x = x - q */
  if ((res = mp_sub(x, &q, x)) != MP_OKAY0)
      goto CLEANUP;

  /* If x < 0, add b^(k+1) to it */
  if (mp_cmp_z(x) < 0) {
      mp_set(&q, 1);
      if ((res = s_mp_lshd(&q, USED(m)((m)->used) + 1)) != MP_OKAY0)
          goto CLEANUP;
      if ((res = mp_add(x, &q, x)) != MP_OKAY0)
          goto CLEANUP;
  }

  /* Back off if it's too big */
  while (mp_cmp(x, m) >= 0) {
      if ((res = s_mp_sub(x, m)) != MP_OKAY0)
          break;
  }

4724CLEANUP:
  mp_clear(&q);

  return res;

4729} /* end s_mp_reduce() */

4731/* }}} */

4733/* }}} */

4735/* {{{ Primitive comparisons */

4737/* {{{ s_mp_cmp(a, b) */

4739/* Compare |a| <=> |b|, return 0 if equal, <0 if a<b, >0 if a>b           */
4740int
4741s_mp_cmp(const mp_int *a, const mp_int *b)
4742{
  ARGMPCHK(a != NULL && b != NULL)((void) sizeof ((a != ((void*)0) && b != ((void*)0)) ?
: 0), __extension__ ({ if (a != ((void*)0) && b !=
 ((void*)0)) ; else __assert_fail ("a != ((void*)0) && b != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 4743
, __extension__ __PRETTY_FUNCTION__); }));

  mp_size used_a = MP_USED(a)((a)->used);
  {
      mp_size used_b = MP_USED(b)((b)->used);

      if (used_a > used_b)
          goto IS_GT;
      if (used_a < used_b)
          goto IS_LT;
  }
  {
      mp_digit *pa, *pb;
      mp_digit da = 0, db = 0;

4758#define CMP_AB(n)if ((da = pa[n]) != (db = pb[n])) goto done                     \
  if ((da = pa[n]) != (db = pb[n])) \
  goto done

      pa = MP_DIGITS(a)((a)->dp) + used_a;
      pb = MP_DIGITS(b)((b)->dp) + used_a;
      while (used_a >= 4) {
          pa -= 4;
          pb -= 4;
          used_a -= 4;
          CMP_AB(3)if ((da = pa[3]) != (db = pb[3])) goto done;
          CMP_AB(2)if ((da = pa[2]) != (db = pb[2])) goto done;
          CMP_AB(1)if ((da = pa[1]) != (db = pb[1])) goto done;
          CMP_AB(0)if ((da = pa[0]) != (db = pb[0])) goto done;
      }
      while (used_a-- > 0 && ((da = *--pa) == (db = *--pb)))
          /* do nothing */;
  done:
      if (da > db)
          goto IS_GT;
      if (da < db)
          goto IS_LT;
  }
  return MP_EQ0;
4782IS_LT:
  return MP_LT-1;
4784IS_GT:
  return MP_GT1;
4786} /* end s_mp_cmp() */

4788/* }}} */

4790/* {{{ s_mp_cmp_d(a, d) */

4792/* Compare |a| <=> d, return 0 if equal, <0 if a<d, >0 if a>d             */
4793int
4794s_mp_cmp_d(const mp_int *a, mp_digit d)
4795{
  ARGMPCHK(a != NULL)((void) sizeof ((a != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (a != ((void*)0)) ; else __assert_fail ("a != ((void*)0)", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 4796, __extension__ __PRETTY_FUNCTION__); }));

  if (USED(a)((a)->used) > 1)
      return MP_GT1;

  if (DIGIT(a, 0)(a)->dp[(0)] < d)
      return MP_LT-1;
  else if (DIGIT(a, 0)(a)->dp[(0)] > d)
      return MP_GT1;
  else
      return MP_EQ0;

4808} /* end s_mp_cmp_d() */

4810/* }}} */

4812/* {{{ s_mp_ispow2(v) */

4814/*
Returns -1 if the value is not a power of two; otherwise, it returns
k such that v = 2^k, i.e. lg(v).
*/
4818int
4819s_mp_ispow2(const mp_int *v)
4820{
  mp_digit d;
  int extra = 0, ix;

  ARGMPCHK(v != NULL)((void) sizeof ((v != ((void*)0)) ? 1 : 0), __extension__ ({ if
 (v != ((void*)0)) ; else __assert_fail ("v != ((void*)0)", "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c"
, 4824, __extension__ __PRETTY_FUNCTION__); }));

  ix = MP_USED(v)((v)->used) - 1;
  d = MP_DIGIT(v, ix)(v)->dp[(ix)]; /* most significant digit of v */

  extra = s_mp_ispow2d(d);
  if (extra < 0 || ix == 0)
      return extra;

  while (--ix >= 0) {
      if (DIGIT(v, ix)(v)->dp[(ix)] != 0)
          return -1; /* not a power of two */
      extra += MP_DIGIT_BIT(8 * sizeof(mp_digit));
  }

  return extra;

4841} /* end s_mp_ispow2() */

4843/* }}} */

4845/* {{{ s_mp_ispow2d(d) */

4847int
4848s_mp_ispow2d(mp_digit d)
4849{
  if ((d != 0) && ((d & (d - 1)) == 0)) { /* d is a power of 2 */
      int pow = 0;
4852#if defined(MP_USE_UINT_DIGIT)
      if (d & 0xffff0000U)
          pow += 16;
      if (d & 0xff00ff00U)
          pow += 8;
      if (d & 0xf0f0f0f0U)
          pow += 4;
      if (d & 0xccccccccU)
          pow += 2;
      if (d & 0xaaaaaaaaU)
          pow += 1;
4863#elif defined(MP_USE_LONG_LONG_DIGIT)
      if (d & 0xffffffff00000000ULL)
          pow += 32;
      if (d & 0xffff0000ffff0000ULL)
          pow += 16;
      if (d & 0xff00ff00ff00ff00ULL)
          pow += 8;
      if (d & 0xf0f0f0f0f0f0f0f0ULL)
          pow += 4;
      if (d & 0xccccccccccccccccULL)
          pow += 2;
      if (d & 0xaaaaaaaaaaaaaaaaULL)
          pow += 1;
4876#elif defined(MP_USE_LONG_DIGIT1)
      if (d & 0xffffffff00000000UL)
          pow += 32;
      if (d & 0xffff0000ffff0000UL)
          pow += 16;
      if (d & 0xff00ff00ff00ff00UL)
          pow += 8;
      if (d & 0xf0f0f0f0f0f0f0f0UL)
          pow += 4;
      if (d & 0xccccccccccccccccUL)
          pow += 2;
      if (d & 0xaaaaaaaaaaaaaaaaUL)
          pow += 1;
4889#else
4890#error "unknown type for mp_digit"
4891#endif
      return pow;
  }
  return -1;

4896} /* end s_mp_ispow2d() */

4898/* }}} */

4900/* }}} */

4902/* {{{ Primitive I/O helpers */

4904/* {{{ s_mp_tovalue(ch, r) */

4906/*
Convert the given character to its digit value, in the given radix.
If the given character is not understood in the given radix, -1 is
returned.  Otherwise the digit's numeric value is returned.

The results will be odd if you use a radix < 2 or > 62, you are
expected to know what you're up to.
*/
4914int
4915s_mp_tovalue(char ch, int r)
4916{
  int val, xch;

  if (r > 36)
      xch = ch;
  else
      xch = toupper((unsigned char)ch)(__extension__ ({ int __res; if (sizeof ((unsigned char)ch) >
 1) { if (__builtin_constant_p ((unsigned char)ch)) { int __c
 = ((unsigned char)ch); __res = __c < -128 || __c > 255
 ? __c : (*__ctype_toupper_loc ())[__c]; } else __res = toupper
 ((unsigned char)ch); } else __res = (*__ctype_toupper_loc ()
)[(int) ((unsigned char)ch)]; __res; }));

  if (isdigit((unsigned char)xch)((*__ctype_b_loc ())[(int) (((unsigned char)xch))] & (unsigned
 short int) _ISdigit))
      val = xch - '0';
  else if (isupper((unsigned char)xch)((*__ctype_b_loc ())[(int) (((unsigned char)xch))] & (unsigned
 short int) _ISupper))
      val = xch - 'A' + 10;
  else if (islower((unsigned char)xch)((*__ctype_b_loc ())[(int) (((unsigned char)xch))] & (unsigned
 short int) _ISlower))
      val = xch - 'a' + 36;
  else if (xch == '+')
      val = 62;
  else if (xch == '/')
      val = 63;
  else
      return -1;

  if (val < 0 || val >= r)
      return -1;

  return val;

4942} /* end s_mp_tovalue() */

4944/* }}} */

4946/* {{{ s_mp_todigit(val, r, low) */

4948/*
Convert val to a radix-r digit, if possible.  If val is out of range
for r, returns zero.  Otherwise, returns an ASCII character denoting
the value in the given radix.

The results may be odd if you use a radix < 2 or > 64, you are
expected to know what you're doing.
*/

4957char
4958s_mp_todigit(mp_digit val, int r, int low)
4959{
  char ch;

  if (val >= r)
      return 0;

  ch = s_dmap_1[val];

  if (r <= 36 && low)
      ch = tolower((unsigned char)ch)(__extension__ ({ int __res; if (sizeof ((unsigned char)ch) >
 1) { if (__builtin_constant_p ((unsigned char)ch)) { int __c
 = ((unsigned char)ch); __res = __c < -128 || __c > 255
 ? __c : (*__ctype_tolower_loc ())[__c]; } else __res = tolower
 ((unsigned char)ch); } else __res = (*__ctype_tolower_loc ()
)[(int) ((unsigned char)ch)]; __res; }));

  return ch;

4972} /* end s_mp_todigit() */

4974/* }}} */

4976/* {{{ s_mp_outlen(bits, radix) */

4978/*
 Return an estimate for how long a string is needed to hold a radix
 r representation of a number with 'bits' significant bits, plus an
 extra for a zero terminator (assuming C style strings here)
*/
4983int
4984s_mp_outlen(int bits, int r)
4985{
  return (int)((double)bits * LOG_V_2(r)s_logv_2[(r)] + 1.5) + 1;

4988} /* end s_mp_outlen() */

4990/* }}} */

4992/* }}} */

4994/* {{{ mp_read_unsigned_octets(mp, str, len) */
4995/* mp_read_unsigned_octets(mp, str, len)
 Read in a raw value (base 256) into the given mp_int
 No sign bit, number is positive.  Leading zeros ignored.
*/

5000mp_err
5001mp_read_unsigned_octets(mp_int *mp, const unsigned char *str, mp_size len)
5002{
  int count;
  mp_err res;
  mp_digit d;

  ARGCHK(mp != NULL && str != NULL && len > 0, MP_BADARG)((void) sizeof ((mp != ((void*)0) && str != ((void*)0
) && len > 0) ? 1 : 0), __extension__ ({ if (mp !=
 ((void*)0) && str != ((void*)0) && len > 0
) ; else __assert_fail ("mp != ((void*)0) && str != ((void*)0) && len > 0"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5007
, __extension__ __PRETTY_FUNCTION__); }));

  mp_zero(mp);

  count = len % sizeof(mp_digit);
  if (count) {
      for (d = 0; count-- > 0; --len) {
          d = (d << 8) | *str++;
      }
      MP_DIGIT(mp, 0)(mp)->dp[(0)] = d;
  }

  /* Read the rest of the digits */
  for (; len > 0; len -= sizeof(mp_digit)) {
      for (d = 0, count = sizeof(mp_digit); count > 0; --count) {
          d = (d << 8) | *str++;
      }
      if (MP_EQ0 == mp_cmp_z(mp)) {
          if (!d)
              continue;
      } else {
          if ((res = s_mp_lshd(mp, 1)) != MP_OKAY0)
              return res;
      }
      MP_DIGIT(mp, 0)(mp)->dp[(0)] = d;
  }
  return MP_OKAY0;
5034} /* end mp_read_unsigned_octets() */
5035/* }}} */

5037/* {{{ mp_unsigned_octet_size(mp) */
5038unsigned int
5039mp_unsigned_octet_size(const mp_int *mp)
5040{
  unsigned int bytes;
  int ix;
  mp_digit d = 0;

  ARGCHK(mp != NULL, MP_BADARG)((void) sizeof ((mp != ((void*)0)) ? 1 : 0), __extension__ ({
 if (mp != ((void*)0)) ; else __assert_fail ("mp != ((void*)0)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5045
, __extension__ __PRETTY_FUNCTION__); }));
  ARGCHK(MP_ZPOS == SIGN(mp), MP_BADARG)((void) sizeof ((0 == ((mp)->sign)) ? 1 : 0), __extension__
 ({ if (0 == ((mp)->sign)) ; else __assert_fail ("0 == ((mp)->sign)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5046
, __extension__ __PRETTY_FUNCTION__); }));

  bytes = (USED(mp)((mp)->used) * sizeof(mp_digit));

  /* subtract leading zeros. */
  /* Iterate over each digit... */
  for (ix = USED(mp)((mp)->used) - 1; ix >= 0; ix--) {
      d = DIGIT(mp, ix)(mp)->dp[(ix)];
      if (d)
          break;
      bytes -= sizeof(d);
  }
  if (!bytes)
      return 1;

  /* Have MSD, check digit bytes, high order first */
  for (ix = sizeof(mp_digit) - 1; ix >= 0; ix--) {
      unsigned char x = (unsigned char)(d >> (ix * CHAR_BIT8));
      if (x)
          break;
      --bytes;
  }
  return bytes;
5069} /* end mp_unsigned_octet_size() */
5070/* }}} */

5072/* {{{ mp_to_unsigned_octets(mp, str) */
5073/* output a buffer of big endian octets no longer than specified. */
5074mp_err
5075mp_to_unsigned_octets(const mp_int *mp, unsigned char *str, mp_size maxlen)
5076{
  int ix, pos = 0;
  unsigned int bytes;

  ARGCHK(mp != NULL && str != NULL && !SIGN(mp), MP_BADARG)((void) sizeof ((mp != ((void*)0) && str != ((void*)0
) && !((mp)->sign)) ? 1 : 0), __extension__ ({ if (
mp != ((void*)0) && str != ((void*)0) && !((mp
)->sign)) ; else __assert_fail ("mp != ((void*)0) && str != ((void*)0) && !((mp)->sign)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5080
, __extension__ __PRETTY_FUNCTION__); }));

  bytes = mp_unsigned_octet_size(mp);
  ARGCHK(bytes <= maxlen, MP_BADARG)((void) sizeof ((bytes <= maxlen) ? 1 : 0), __extension__ (
{ if (bytes <= maxlen) ; else __assert_fail ("bytes <= maxlen"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5083
, __extension__ __PRETTY_FUNCTION__); }));

  /* Iterate over each digit... */
  for (ix = USED(mp)((mp)->used) - 1; ix >= 0; ix--) {
      mp_digit d = DIGIT(mp, ix)(mp)->dp[(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_BIT8));
          if (!pos && !x) /* suppress leading zeros */
              continue;
          str[pos++] = x;
      }
  }
  if (!pos)
      str[pos++] = 0;
  return pos;
5101} /* end mp_to_unsigned_octets() */
5102/* }}} */

5104/* {{{ mp_to_signed_octets(mp, str) */
5105/* output a buffer of big endian octets no longer than specified. */
5106mp_err
5107mp_to_signed_octets(const mp_int *mp, unsigned char *str, mp_size maxlen)
5108{
  int ix, pos = 0;
  unsigned int bytes;

  ARGCHK(mp != NULL && str != NULL && !SIGN(mp), MP_BADARG)((void) sizeof ((mp != ((void*)0) && str != ((void*)0
) && !((mp)->sign)) ? 1 : 0), __extension__ ({ if (
mp != ((void*)0) && str != ((void*)0) && !((mp
)->sign)) ; else __assert_fail ("mp != ((void*)0) && str != ((void*)0) && !((mp)->sign)"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5112
, __extension__ __PRETTY_FUNCTION__); }));

  bytes = mp_unsigned_octet_size(mp);
  ARGCHK(bytes <= maxlen, MP_BADARG)((void) sizeof ((bytes <= maxlen) ? 1 : 0), __extension__ (
{ if (bytes <= maxlen) ; else __assert_fail ("bytes <= maxlen"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5115
, __extension__ __PRETTY_FUNCTION__); }));

  /* Iterate over each digit... */
  for (ix = USED(mp)((mp)->used) - 1; ix >= 0; ix--) {
      mp_digit d = DIGIT(mp, ix)(mp)->dp[(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_BIT8));
          if (!pos) {
              if (!x) /* suppress leading zeros */
                  continue;
              if (x & 0x80) { /* add one leading zero to make output positive.  */
                  ARGCHK(bytes + 1 <= maxlen, MP_BADARG)((void) sizeof ((bytes + 1 <= maxlen) ? 1 : 0), __extension__
 ({ if (bytes + 1 <= maxlen) ; else __assert_fail ("bytes + 1 <= maxlen"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5129
, __extension__ __PRETTY_FUNCTION__); }));
                  if (bytes + 1 > maxlen)
                      return MP_BADARG-4;
                  str[pos++] = 0;
              }
          }
          str[pos++] = x;
      }
  }
  if (!pos)
      str[pos++] = 0;
  return pos;
5141} /* end mp_to_signed_octets() */
5142/* }}} */

5144/* {{{ mp_to_fixlen_octets(mp, str) */
5145/* output a buffer of big endian octets exactly as long as requested.
 constant time on the value of mp. */
5147mp_err
5148mp_to_fixlen_octets(const mp_int *mp, unsigned char *str, mp_size length)
5149{
  int ix, jx;
  unsigned int bytes;

  ARGCHK(mp != NULL && str != NULL && !SIGN(mp) && length > 0, MP_BADARG)((void) sizeof ((mp != ((void*)0) && str != ((void*)0
) && !((mp)->sign) && length > 0) ? 1 :
 0), __extension__ ({ if (mp != ((void*)0) && str != (
(void*)0) && !((mp)->sign) && length > 0
) ; else __assert_fail ("mp != ((void*)0) && str != ((void*)0) && !((mp)->sign) && length > 0"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5153
, __extension__ __PRETTY_FUNCTION__); }));

  /* Constant time on the value of mp.  Don't use mp_unsigned_octet_size. */
  bytes = USED(mp)((mp)->used) * MP_DIGIT_SIZEsizeof(mp_digit);

  /* If the output is shorter than the native size of mp, then check that any
   * bytes not written have zero values.  This check isn't constant time on
   * the assumption that timing-sensitive callers can guarantee that mp fits
   * in the allocated space. */
  ix = USED(mp)((mp)->used) - 1;
  if (bytes > length) {
      unsigned int zeros = bytes - length;

      while (zeros >= MP_DIGIT_SIZEsizeof(mp_digit)) {
          ARGCHK(DIGIT(mp, ix) == 0, MP_BADARG)((void) sizeof (((mp)->dp[(ix)] == 0) ? 1 : 0), __extension__
 ({ if ((mp)->dp[(ix)] == 0) ; else __assert_fail ("(mp)->dp[(ix)] == 0"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5167
, __extension__ __PRETTY_FUNCTION__); }));
          zeros -= MP_DIGIT_SIZEsizeof(mp_digit);
          ix--;
      }

      if (zeros > 0) {
          mp_digit d = DIGIT(mp, ix)(mp)->dp[(ix)];
          mp_digit m = ~0ULL << ((MP_DIGIT_SIZEsizeof(mp_digit) - zeros) * CHAR_BIT8);
          ARGCHK((d & m) == 0, MP_BADARG)((void) sizeof (((d & m) == 0) ? 1 : 0), __extension__ ({
 if ((d & m) == 0) ; else __assert_fail ("(d & m) == 0"
, "/root/firefox-clang/security/nss/lib/freebl/mpi/mpi.c", 5175
, __extension__ __PRETTY_FUNCTION__); }));
          for (jx = MP_DIGIT_SIZEsizeof(mp_digit) - zeros - 1; jx >= 0; jx--) {
              *str++ = d >> (jx * CHAR_BIT8);
          }
          ix--;
      }
  } else if (bytes < length) {
      /* Place any needed leading zeros. */
      unsigned int zeros = length - bytes;
      memset(str, 0, zeros);
      str += zeros;
  }

  /* Iterate over each whole digit... */
  for (; ix >= 0; ix--) {
      mp_digit d = DIGIT(mp, ix)(mp)->dp[(ix)];

      /* Unpack digit bytes, high order first */
      for (jx = MP_DIGIT_SIZEsizeof(mp_digit) - 1; jx >= 0; jx--) {
          *str++ = d >> (jx * CHAR_BIT8);
      }
  }
  return MP_OKAY0;
5198} /* end mp_to_fixlen_octets() */
5199/* }}} */

5201/* {{{ mp_cswap(condition, a, b, numdigits) */
5202/* performs a conditional swap between mp_int. */
5203mp_err
5204mp_cswap(mp_digit condition, mp_int *a, mp_int *b, mp_size numdigits)
5205{
  mp_digit x;
  unsigned int i;
  mp_err res = 0;

  /* if pointers are equal return */
  if (a == b)
      return res;

  if (MP_ALLOC(a)((a)->alloc) < numdigits || MP_ALLOC(b)((b)->alloc) < numdigits) {
      MP_CHECKOK(s_mp_grow(a, numdigits))if (0 > (res = (s_mp_grow(a, numdigits)))) goto CLEANUP;
      MP_CHECKOK(s_mp_grow(b, numdigits))if (0 > (res = (s_mp_grow(b, numdigits)))) goto CLEANUP;
  }

  condition = ((~condition & ((condition - 1))) >> (MP_DIGIT_BIT(8 * sizeof(mp_digit)) - 1)) - 1;

  x = (USED(a)((a)->used) ^ USED(b)((b)->used)) & condition;
  USED(a)((a)->used) ^= x;
  USED(b)((b)->used) ^= x;

  x = (SIGN(a)((a)->sign) ^ SIGN(b)((b)->sign)) & condition;
  SIGN(a)((a)->sign) ^= x;
  SIGN(b)((b)->sign) ^= x;

  for (i = 0; i < numdigits; i++) {
      x = (DIGIT(a, i)(a)->dp[(i)] ^ DIGIT(b, i)(b)->dp[(i)]) & condition;
      DIGIT(a, i)(a)->dp[(i)] ^= x;
      DIGIT(b, i)(b)->dp[(i)] ^= x;
  }

5235CLEANUP:
  return res;
5237} /* end mp_cswap() */
5238/* }}} */

5240/*------------------------------------------------------------------------*/
5241/* HERE THERE BE DRAGONS                                                  */