/* *********************************************************************

 *

 * Sun elects to have this file available under and governed by the

 * Mozilla Public License Version 1.1 ("MPL") (see

 * http://www.mozilla.org/MPL/ for full license text). For the avoidance

 * of doubt and subject to the following, Sun also elects to allow

 * licensees to use this file under the MPL, the GNU General Public

 * License version 2 only or the Lesser General Public License version

 * 2.1 only. Any references to the "GNU General Public License version 2

 * or later" or "GPL" in the following shall be construed to mean the

 * GNU General Public License version 2 only. Any references to the "GNU

 * Lesser General Public License version 2.1 or later" or "LGPL" in the

 * following shall be construed to mean the GNU Lesser General Public

 * License version 2.1 only. However, the following notice accompanied

 * the original version of this file:

 *

 *

 *  Arbitrary precision integer arithmetic library

 *

 * Version: MPL 1.1/GPL 2.0/LGPL 2.1

 *

 * The contents of this file are subject to the Mozilla Public License Version

 * 1.1 (the "License"); you may not use this file except in compliance with

 * the License. You may obtain a copy of the License at

 * http://www.mozilla.org/MPL/

 *

 * Software distributed under the License is distributed on an "AS IS" basis,

 * WITHOUT WARRANTY OF ANY KIND, either express or implied. See the License

 * for the specific language governing rights and limitations under the

 * License.

 *

 * The Original Code is the MPI Arbitrary Precision Integer Arithmetic library.

 *

 * The Initial Developer of the Original Code is

 * Michael J. Fromberger.

 * Portions created by the Initial Developer are Copyright (C) 1998

 * the Initial Developer. All Rights Reserved.

 *

 * Contributor(s):

 *   Netscape Communications Corporation

 *   Douglas Stebila <douglas@stebila.ca> of Sun Laboratories.

 *

 * Alternatively, the contents of this file may be used under the terms of

 * either the GNU General Public License Version 2 or later (the "GPL"), or

 * the GNU Lesser General Public License Version 2.1 or later (the "LGPL"),

 * in which case the provisions of the GPL or the LGPL are applicable instead

 * of those above. If you wish to allow use of your version of this file only

 * under the terms of either the GPL or the LGPL, and not to allow others to

 * use your version of this file under the terms of the MPL, indicate your

 * decision by deleting the provisions above and replace them with the notice

 * and other provisions required by the GPL or the LGPL. If you do not delete

 * the provisions above, a recipient may use your version of this file under

 * the terms of any one of the MPL, the GPL or the LGPL.

 *

 *********************************************************************** */

/*

 * Use is subject to license terms.

 */

/* $Id: mpi.c,v 1.45 2006/09/29 20:12:21 alexei.volkov.bugs%sun.com Exp $ */

#include "mpi-priv.h"

#if defined(OSF1)

#include <c_asm.h>

#endif

#if MP_LOGTAB

/*

  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.

 */

#include "logtab.h"

#endif

/* {{{ Constant strings */

/* Constant strings returned by mp_strerror() */

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

};

/* Value to digit maps for radix conversion   */

/* s_dmap_1 - standard digits and letters */

static const char *s_dmap_1 =

  "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz+/";

/* }}} */

unsigned long mp_allocs;

unsigned long mp_frees;

unsigned long mp_copies;

/* {{{ Default precision manipulation */

/* Default precision for newly created mp_int's      */

static mp_size s_mp_defprec = MP_DEFPREC;

mp_size mp_get_prec(void)

{

  return s_mp_defprec;

} /* end mp_get_prec() */

void         mp_set_prec(mp_size prec)

{

  if(prec == 0)

    s_mp_defprec = MP_DEFPREC;

  else

    s_mp_defprec = prec;

} /* end mp_set_prec() */

/* }}} */

/*------------------------------------------------------------------------*/

/* {{{ mp_init(mp, kmflag) */

/*

  mp_init(mp, kmflag)

  Initialize a new zero-valued mp_int.  Returns MP_OKAY if successful,

  MP_MEM if memory could not be allocated for the structure.

 */

mp_err mp_init(mp_int *mp, int kmflag)

{

  return mp_init_size(mp, s_mp_defprec, kmflag);

} /* end mp_init() */

/* }}} */

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

/*

  mp_init_size(mp, prec, kmflag)

  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.

 */

mp_err mp_init_size(mp_int *mp, mp_size prec, int kmflag)

{

  ARGCHK(mp != NULL && prec > 0, MP_BADARG);

  prec = MP_ROUNDUP(prec, s_mp_defprec);

  if((DIGITS(mp) = s_mp_alloc(prec, sizeof(mp_digit), kmflag)) == NULL)

    return MP_MEM;

  SIGN(mp) = ZPOS;

  USED(mp) = 1;

  ALLOC(mp) = prec;

  return MP_OKAY;

} /* end mp_init_size() */

/* }}} */

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

/*

  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.

 */

mp_err mp_init_copy(mp_int *mp, const mp_int *from)

{

  ARGCHK(mp != NULL && from != NULL, MP_BADARG);

  if(mp == from)

    return MP_OKAY;

  if((DIGITS(mp) = s_mp_alloc(ALLOC(from), sizeof(mp_digit), FLAG(from))) == NULL)

    return MP_MEM;

  s_mp_copy(DIGITS(from), DIGITS(mp), USED(from));

  USED(mp) = USED(from);

  ALLOC(mp) = ALLOC(from);

  SIGN(mp) = SIGN(from);

#ifndef _WIN32

  FLAG(mp) = FLAG(from);

#endif /* _WIN32 */

  return MP_OKAY;

} /* end mp_init_copy() */

/* }}} */

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

/*

  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.

 */

mp_err mp_copy(const mp_int *from, mp_int *to)

{

  ARGCHK(from != NULL && to != NULL, MP_BADARG);

  if(from == to)

    return MP_OKAY;

  ++mp_copies;

  { /* 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) >= USED(from)) {

      s_mp_setz(DIGITS(to) + USED(from), ALLOC(to) - USED(from));

      s_mp_copy(DIGITS(from), DIGITS(to), USED(from));

    } else {

      if((tmp = s_mp_alloc(ALLOC(from), sizeof(mp_digit), FLAG(from))) == NULL)

        return MP_MEM;

      s_mp_copy(DIGITS(from), tmp, USED(from));

      if(DIGITS(to) != NULL) {

#if MP_CRYPTO

        s_mp_setz(DIGITS(to), ALLOC(to));

#endif

        s_mp_free(DIGITS(to), ALLOC(to));

      }

      DIGITS(to) = tmp;

      ALLOC(to) = ALLOC(from);

    }

    /* Copy the precision and sign from the original */

    USED(to) = USED(from);

    SIGN(to) = SIGN(from);

  } /* end copy */

  return MP_OKAY;

} /* end mp_copy() */

/* }}} */

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

/*

  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.

 */

void mp_exch(mp_int *mp1, mp_int *mp2)

{

#if MP_ARGCHK == 2

  assert(mp1 != NULL && mp2 != NULL);

#else

  if(mp1 == NULL || mp2 == NULL)

    return;

#endif

  s_mp_exch(mp1, mp2);

} /* end mp_exch() */

/* }}} */

/* {{{ mp_clear(mp) */

/*

  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.

 */

void   mp_clear(mp_int *mp)

{

  if(mp == NULL)

    return;

  if(DIGITS(mp) != NULL) {

#if MP_CRYPTO

    s_mp_setz(DIGITS(mp), ALLOC(mp));

#endif

    s_mp_free(DIGITS(mp), ALLOC(mp));

    DIGITS(mp) = NULL;

  }

  USED(mp) = 0;

  ALLOC(mp) = 0;

} /* end mp_clear() */

/* }}} */

/* {{{ mp_zero(mp) */

/*

  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)

 */

void   mp_zero(mp_int *mp)

{

  if(mp == NULL)

    return;

  s_mp_setz(DIGITS(mp), ALLOC(mp));

  USED(mp) = 1;

  SIGN(mp) = ZPOS;

} /* end mp_zero() */

/* }}} */

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

void   mp_set(mp_int *mp, mp_digit d)

{

  if(mp == NULL)

    return;

  mp_zero(mp);

  DIGIT(mp, 0) = d;

} /* end mp_set() */

/* }}} */

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

mp_err mp_set_int(mp_int *mp, long z)

{

  int            ix;

  unsigned long  v = labs(z);

  mp_err         res;

  ARGCHK(mp != NULL, MP_BADARG);

  mp_zero(mp);

  if(z == 0)

    return MP_OKAY;  /* shortcut for zero */

  if (sizeof v <= sizeof(mp_digit)) {

    DIGIT(mp,0) = v;

  } else {

    for (ix = sizeof(long) - 1; ix >= 0; ix--) {

      if ((res = s_mp_mul_d(mp, (UCHAR_MAX + 1))) != MP_OKAY)

        return res;

      res = s_mp_add_d(mp, (mp_digit)((v >> (ix * CHAR_BIT)) & UCHAR_MAX));

      if (res != MP_OKAY)

        return res;

    }

  }

  if(z < 0)

    SIGN(mp) = NEG;

  return MP_OKAY;

} /* end mp_set_int() */

/* }}} */

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

mp_err mp_set_ulong(mp_int *mp, unsigned long z)

{

  int            ix;

  mp_err         res;

  ARGCHK(mp != NULL, MP_BADARG);

  mp_zero(mp);

  if(z == 0)

    return MP_OKAY;  /* shortcut for zero */

  if (sizeof z <= sizeof(mp_digit)) {

    DIGIT(mp,0) = z;

  } else {

    for (ix = sizeof(long) - 1; ix >= 0; ix--) {

      if ((res = s_mp_mul_d(mp, (UCHAR_MAX + 1))) != MP_OKAY)

        return res;

      res = s_mp_add_d(mp, (mp_digit)((z >> (ix * CHAR_BIT)) & UCHAR_MAX));

      if (res != MP_OKAY)

        return res;

    }

  }

  return MP_OKAY;

} /* end mp_set_ulong() */

/* }}} */

/*------------------------------------------------------------------------*/

/* {{{ Digit arithmetic */

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

/*

  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).

 */

mp_err mp_add_d(const mp_int *a, mp_digit d, mp_int *b)

{

  mp_int   tmp;

  mp_err   res;

  ARGCHK(a != NULL && b != NULL, MP_BADARG);

  if((res = mp_init_copy(&tmp, a)) != MP_OKAY)

    return res;

  if(SIGN(&tmp) == ZPOS) {

    if((res = s_mp_add_d(&tmp, d)) != MP_OKAY)

      goto CLEANUP;

  } else if(s_mp_cmp_d(&tmp, d) >= 0) {

    if((res = s_mp_sub_d(&tmp, d)) != MP_OKAY)

      goto CLEANUP;

  } else {

    mp_neg(&tmp, &tmp);

    DIGIT(&tmp, 0) = d - DIGIT(&tmp, 0);

  }

  if(s_mp_cmp_d(&tmp, 0) == 0)

    SIGN(&tmp) = ZPOS;

  s_mp_exch(&tmp, b);

CLEANUP:

  mp_clear(&tmp);

  return res;

} /* end mp_add_d() */

/* }}} */

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

/*

  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).

 */

mp_err mp_sub_d(const mp_int *a, mp_digit d, mp_int *b)

{

  mp_int   tmp;

  mp_err   res;

  ARGCHK(a != NULL && b != NULL, MP_BADARG);

  if((res = mp_init_copy(&tmp, a)) != MP_OKAY)

    return res;

  if(SIGN(&tmp) == NEG) {

    if((res = s_mp_add_d(&tmp, d)) != MP_OKAY)

      goto CLEANUP;

  } else if(s_mp_cmp_d(&tmp, d) >= 0) {

    if((res = s_mp_sub_d(&tmp, d)) != MP_OKAY)

      goto CLEANUP;

  } else {

    mp_neg(&tmp, &tmp);

    DIGIT(&tmp, 0) = d - DIGIT(&tmp, 0);

    SIGN(&tmp) = NEG;

  }

  if(s_mp_cmp_d(&tmp, 0) == 0)

    SIGN(&tmp) = ZPOS;

  s_mp_exch(&tmp, b);

CLEANUP:

  mp_clear(&tmp);

  return res;

} /* end mp_sub_d() */

/* }}} */

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

/*

  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)

 */