Return to divrem.c CVS log

Up to [local] / OpenXM_contrib / gmp / mpn / generic

Annotation of OpenXM_contrib/gmp/mpn/generic/divrem.c, Revision 1.1.1.3

1.1       maekawa     1: /* mpn_divrem -- Divide natural numbers, producing both remainder and
1.1.1.2   maekawa     2:    quotient.  This is now just a middle layer for calling the new
                      3:    internal mpn_tdiv_qr.
1.1       maekawa     4:
1.1.1.3 ! ohara       5: Copyright 1993, 1994, 1995, 1996, 1997, 1999, 2000, 2001, 2002 Free Software
1.1.1.2   maekawa     6: Foundation, Inc.
1.1       maekawa     7:
                      8: This file is part of the GNU MP Library.
                      9:
                     10: The GNU MP Library is free software; you can redistribute it and/or modify
1.1.1.2   maekawa    11: it under the terms of the GNU Lesser General Public License as published by
                     12: the Free Software Foundation; either version 2.1 of the License, or (at your
1.1       maekawa    13: option) any later version.
                     14:
                     15: The GNU MP Library is distributed in the hope that it will be useful, but
                     16: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
1.1.1.2   maekawa    17: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
1.1       maekawa    18: License for more details.
                     19:
1.1.1.2   maekawa    20: You should have received a copy of the GNU Lesser General Public License
1.1       maekawa    21: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     22: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     23: MA 02111-1307, USA. */
                     24:
                     25: #include "gmp.h"
                     26: #include "gmp-impl.h"
                     27: #include "longlong.h"
                     28:
                     29: mp_limb_t
1.1.1.2   maekawa    30: mpn_divrem (mp_ptr qp, mp_size_t qxn,
                     31:            mp_ptr np, mp_size_t nn,
                     32:            mp_srcptr dp, mp_size_t dn)
1.1       maekawa    33: {
1.1.1.3 ! ohara      34:   ASSERT (qxn >= 0);
        !            35:   ASSERT (nn >= dn);
        !            36:   ASSERT (dn >= 1);
        !            37:   ASSERT (dp[dn-1] & GMP_NUMB_HIGHBIT);
        !            38:   ASSERT (! MPN_OVERLAP_P (np, nn, dp, dn));
        !            39:   ASSERT (! MPN_OVERLAP_P (qp, nn-dn+qxn, np, nn) || qp==np+dn+qxn);
        !            40:   ASSERT (! MPN_OVERLAP_P (qp, nn-dn+qxn, dp, dn));
        !            41:   ASSERT_MPN (np, nn);
        !            42:   ASSERT_MPN (dp, dn);
        !            43:
1.1.1.2   maekawa    44:   if (dn == 1)
                     45:     {
                     46:       mp_limb_t ret;
                     47:       mp_ptr q2p;
                     48:       mp_size_t qn;
                     49:       TMP_DECL (marker);
                     50:
                     51:       TMP_MARK (marker);
                     52:       q2p = (mp_ptr) TMP_ALLOC ((nn + qxn) * BYTES_PER_MP_LIMB);
                     53:
                     54:       np[0] = mpn_divrem_1 (q2p, qxn, np, nn, dp[0]);
                     55:       qn = nn + qxn - 1;
                     56:       MPN_COPY (qp, q2p, qn);
                     57:       ret = q2p[qn];
1.1       maekawa    58:
1.1.1.2   maekawa    59:       TMP_FREE (marker);
                     60:       return ret;
                     61:     }
                     62:   else if (dn == 2)
1.1       maekawa    63:     {
1.1.1.2   maekawa    64:       return mpn_divrem_2 (qp, qxn, np, nn, dp);
                     65:     }
                     66:   else
                     67:     {
                     68:       mp_ptr rp, q2p;
                     69:       mp_limb_t qhl;
                     70:       mp_size_t qn;
                     71:       TMP_DECL (marker);
                     72:
                     73:       TMP_MARK (marker);
                     74:       if (qxn != 0)
                     75:        {
                     76:          mp_ptr n2p;
                     77:          n2p = (mp_ptr) TMP_ALLOC ((nn + qxn) * BYTES_PER_MP_LIMB);
                     78:          MPN_ZERO (n2p, qxn);
                     79:          MPN_COPY (n2p + qxn, np, nn);
                     80:          q2p = (mp_ptr) TMP_ALLOC ((nn - dn + qxn + 1) * BYTES_PER_MP_LIMB);
                     81:          rp = (mp_ptr) TMP_ALLOC (dn * BYTES_PER_MP_LIMB);
                     82:          mpn_tdiv_qr (q2p, rp, 0L, n2p, nn + qxn, dp, dn);
                     83:          MPN_COPY (np, rp, dn);
                     84:          qn = nn - dn + qxn;
                     85:          MPN_COPY (qp, q2p, qn);
                     86:          qhl = q2p[qn];
                     87:        }
                     88:       else
                     89:        {
                     90:          q2p = (mp_ptr) TMP_ALLOC ((nn - dn + 1) * BYTES_PER_MP_LIMB);
                     91:          rp = (mp_ptr) TMP_ALLOC (dn * BYTES_PER_MP_LIMB);
                     92:          mpn_tdiv_qr (q2p, rp, 0L, np, nn, dp, dn);
                     93:          MPN_COPY (np, rp, dn);        /* overwrite np area with remainder */
                     94:          qn = nn - dn;
                     95:          MPN_COPY (qp, q2p, qn);
                     96:          qhl = q2p[qn];
                     97:        }
                     98:       TMP_FREE (marker);
                     99:       return qhl;
1.1       maekawa   100:     }
                    101: }