Return to sqr_basecase.c CVS log

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

Annotation of OpenXM_contrib/gmp/mpn/generic/sqr_basecase.c, Revision 1.1.1.2

1.1.1.2 ! ohara       1: /* mpn_sqr_basecase -- Internal routine to square a natural number
        !             2:    of length n.
1.1       maekawa     3:
                      4:    THIS IS AN INTERNAL FUNCTION WITH A MUTABLE INTERFACE.  IT IS ONLY
                      5:    SAFE TO REACH THIS FUNCTION THROUGH DOCUMENTED INTERFACES.
                      6:
                      7:
1.1.1.2 ! ohara       8: Copyright 1991, 1992, 1993, 1994, 1996, 1997, 2000, 2001, 2002 Free Software
1.1       maekawa     9: Foundation, Inc.
                     10:
                     11: This file is part of the GNU MP Library.
                     12:
                     13: The GNU MP Library is free software; you can redistribute it and/or modify
                     14: it under the terms of the GNU Lesser General Public License as published by
                     15: the Free Software Foundation; either version 2.1 of the License, or (at your
                     16: option) any later version.
                     17:
                     18: The GNU MP Library is distributed in the hope that it will be useful, but
                     19: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
                     20: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
                     21: License for more details.
                     22:
                     23: You should have received a copy of the GNU Lesser General Public License
                     24: along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
                     25: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
                     26: MA 02111-1307, USA. */
                     27:
                     28: #include "gmp.h"
                     29: #include "gmp-impl.h"
                     30: #include "longlong.h"
                     31:
                     32: void
                     33: mpn_sqr_basecase (mp_ptr prodp, mp_srcptr up, mp_size_t n)
                     34: {
                     35:   mp_size_t i;
                     36:
1.1.1.2 ! ohara      37:   ASSERT (n >= 1);
        !            38:   ASSERT (! MPN_OVERLAP_P (prodp, 2*n, up, n));
        !            39:
1.1       maekawa    40:   {
                     41:     /* N.B.!  We need the superfluous indirection through argh to work around
                     42:        a reloader bug in GCC 2.7.*.  */
1.1.1.2 ! ohara      43: #if GMP_NAIL_BITS == 0
        !            44:     mp_limb_t ul, argh;
        !            45:     ul = up[0];
        !            46:     umul_ppmm (argh, prodp[0], ul, ul);
1.1       maekawa    47:     prodp[1] = argh;
1.1.1.2 ! ohara      48: #else
        !            49:     mp_limb_t ul, lpl;
        !            50:     ul = up[0];
        !            51:     umul_ppmm (prodp[1], lpl, ul, ul << GMP_NAIL_BITS);
        !            52:     prodp[0] = lpl >> GMP_NAIL_BITS;
        !            53: #endif
1.1       maekawa    54:   }
                     55:   if (n > 1)
                     56:     {
1.1.1.2 ! ohara      57:       mp_limb_t tarr[2 * SQR_KARATSUBA_THRESHOLD];
1.1       maekawa    58:       mp_ptr tp = tarr;
                     59:       mp_limb_t cy;
                     60:
                     61:       /* must fit 2*n limbs in tarr */
1.1.1.2 ! ohara      62:       ASSERT (n <= SQR_KARATSUBA_THRESHOLD);
1.1       maekawa    63:
                     64:       cy = mpn_mul_1 (tp, up + 1, n - 1, up[0]);
                     65:       tp[n - 1] = cy;
                     66:       for (i = 2; i < n; i++)
                     67:        {
                     68:          mp_limb_t cy;
                     69:          cy = mpn_addmul_1 (tp + 2 * i - 2, up + i, n - i, up[i - 1]);
                     70:          tp[n + i - 2] = cy;
                     71:        }
1.1.1.2 ! ohara      72: #if HAVE_NATIVE_mpn_sqr_diagonal
        !            73:       mpn_sqr_diagonal (prodp + 2, up + 1, n - 1);
        !            74: #else
1.1       maekawa    75:       for (i = 1; i < n; i++)
                     76:        {
1.1.1.2 ! ohara      77: #if GMP_NAIL_BITS == 0
        !            78:          mp_limb_t ul;
        !            79:          ul = up[i];
        !            80:          umul_ppmm (prodp[2 * i + 1], prodp[2 * i], ul, ul);
        !            81: #else
        !            82:          mp_limb_t ul, lpl;
        !            83:          ul = up[i];
        !            84:          umul_ppmm (prodp[2 * i + 1], lpl, ul, ul << GMP_NAIL_BITS);
        !            85:          prodp[2 * i] = lpl >> GMP_NAIL_BITS;
        !            86: #endif
1.1       maekawa    87:        }
1.1.1.2 ! ohara      88: #endif
1.1       maekawa    89:       {
                     90:        mp_limb_t cy;
                     91:        cy = mpn_lshift (tp, tp, 2 * n - 2, 1);
                     92:        cy += mpn_add_n (prodp + 1, prodp + 1, tp, 2 * n - 2);
                     93:        prodp[2 * n - 1] += cy;
                     94:       }
                     95:     }
                     96: }