X-Git-Url: http://git.megacz.com/?a=blobdiff_plain;ds=sidebyside;f=rts%2Fgmp%2Fmpn%2Fgeneric%2Fdivrem_1.c;fp=rts%2Fgmp%2Fmpn%2Fgeneric%2Fdivrem_1.c;h=0000000000000000000000000000000000000000;hb=fdf1cd0399158308769fcb2ab7e46e215a68d865;hp=e93f241c9dda3e4069d680eacca0d967b77c9f9f;hpb=e552cfc427d2734b9a9629f2ab1d22f493e775f6;p=ghc-hetmet.git diff --git a/rts/gmp/mpn/generic/divrem_1.c b/rts/gmp/mpn/generic/divrem_1.c deleted file mode 100644 index e93f241..0000000 --- a/rts/gmp/mpn/generic/divrem_1.c +++ /dev/null @@ -1,248 +0,0 @@ -/* mpn_divrem_1(quot_ptr, qsize, dividend_ptr, dividend_size, divisor_limb) -- - Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB. - Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR. - Return the single-limb remainder. - There are no constraints on the value of the divisor. - - QUOT_PTR and DIVIDEND_PTR might point to the same limb. - -Copyright (C) 1991, 1993, 1994, 1996, 1998, 1999, 2000 Free Software -Foundation, Inc. - -This file is part of the GNU MP Library. - -The GNU MP Library is free software; you can redistribute it and/or modify -it under the terms of the GNU Lesser General Public License as published by -the Free Software Foundation; either version 2.1 of the License, or (at your -option) any later version. - -The GNU MP Library is distributed in the hope that it will be useful, but -WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY -or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public -License for more details. - -You should have received a copy of the GNU Lesser General Public License -along with the GNU MP Library; see the file COPYING.LIB. If not, write to -the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, -MA 02111-1307, USA. */ - -#include "gmp.h" -#include "gmp-impl.h" -#include "longlong.h" - - - -/* __gmpn_divmod_1_internal(quot_ptr,dividend_ptr,dividend_size,divisor_limb) - Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB. - Write DIVIDEND_SIZE limbs of quotient at QUOT_PTR. - Return the single-limb remainder. - There are no constraints on the value of the divisor. - - QUOT_PTR and DIVIDEND_PTR might point to the same limb. */ - -#ifndef UMUL_TIME -#define UMUL_TIME 1 -#endif - -#ifndef UDIV_TIME -#define UDIV_TIME UMUL_TIME -#endif - -static mp_limb_t -#if __STDC__ -__gmpn_divmod_1_internal (mp_ptr quot_ptr, - mp_srcptr dividend_ptr, mp_size_t dividend_size, - mp_limb_t divisor_limb) -#else -__gmpn_divmod_1_internal (quot_ptr, dividend_ptr, dividend_size, divisor_limb) - mp_ptr quot_ptr; - mp_srcptr dividend_ptr; - mp_size_t dividend_size; - mp_limb_t divisor_limb; -#endif -{ - mp_size_t i; - mp_limb_t n1, n0, r; - int dummy; - - /* ??? Should this be handled at all? Rely on callers? */ - if (dividend_size == 0) - return 0; - - /* If multiplication is much faster than division, and the - dividend is large, pre-invert the divisor, and use - only multiplications in the inner loop. */ - - /* This test should be read: - Does it ever help to use udiv_qrnnd_preinv? - && Does what we save compensate for the inversion overhead? */ - if (UDIV_TIME > (2 * UMUL_TIME + 6) - && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME) - { - int normalization_steps; - - count_leading_zeros (normalization_steps, divisor_limb); - if (normalization_steps != 0) - { - mp_limb_t divisor_limb_inverted; - - divisor_limb <<= normalization_steps; - invert_limb (divisor_limb_inverted, divisor_limb); - - n1 = dividend_ptr[dividend_size - 1]; - r = n1 >> (BITS_PER_MP_LIMB - normalization_steps); - - /* Possible optimization: - if (r == 0 - && divisor_limb > ((n1 << normalization_steps) - | (dividend_ptr[dividend_size - 2] >> ...))) - ...one division less... */ - - for (i = dividend_size - 2; i >= 0; i--) - { - n0 = dividend_ptr[i]; - udiv_qrnnd_preinv (quot_ptr[i + 1], r, r, - ((n1 << normalization_steps) - | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))), - divisor_limb, divisor_limb_inverted); - n1 = n0; - } - udiv_qrnnd_preinv (quot_ptr[0], r, r, - n1 << normalization_steps, - divisor_limb, divisor_limb_inverted); - return r >> normalization_steps; - } - else - { - mp_limb_t divisor_limb_inverted; - - invert_limb (divisor_limb_inverted, divisor_limb); - - i = dividend_size - 1; - r = dividend_ptr[i]; - - if (r >= divisor_limb) - r = 0; - else - { - quot_ptr[i] = 0; - i--; - } - - for (; i >= 0; i--) - { - n0 = dividend_ptr[i]; - udiv_qrnnd_preinv (quot_ptr[i], r, r, - n0, divisor_limb, divisor_limb_inverted); - } - return r; - } - } - else - { - if (UDIV_NEEDS_NORMALIZATION) - { - int normalization_steps; - - count_leading_zeros (normalization_steps, divisor_limb); - if (normalization_steps != 0) - { - divisor_limb <<= normalization_steps; - - n1 = dividend_ptr[dividend_size - 1]; - r = n1 >> (BITS_PER_MP_LIMB - normalization_steps); - - /* Possible optimization: - if (r == 0 - && divisor_limb > ((n1 << normalization_steps) - | (dividend_ptr[dividend_size - 2] >> ...))) - ...one division less... */ - - for (i = dividend_size - 2; i >= 0; i--) - { - n0 = dividend_ptr[i]; - udiv_qrnnd (quot_ptr[i + 1], r, r, - ((n1 << normalization_steps) - | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))), - divisor_limb); - n1 = n0; - } - udiv_qrnnd (quot_ptr[0], r, r, - n1 << normalization_steps, - divisor_limb); - return r >> normalization_steps; - } - } - /* No normalization needed, either because udiv_qrnnd doesn't require - it, or because DIVISOR_LIMB is already normalized. */ - - i = dividend_size - 1; - r = dividend_ptr[i]; - - if (r >= divisor_limb) - r = 0; - else - { - quot_ptr[i] = 0; - i--; - } - - for (; i >= 0; i--) - { - n0 = dividend_ptr[i]; - udiv_qrnnd (quot_ptr[i], r, r, n0, divisor_limb); - } - return r; - } -} - - - -mp_limb_t -#if __STDC__ -mpn_divrem_1 (mp_ptr qp, mp_size_t qxn, - mp_srcptr np, mp_size_t nn, - mp_limb_t d) -#else -mpn_divrem_1 (qp, qxn, np, nn, d) - mp_ptr qp; - mp_size_t qxn; - mp_srcptr np; - mp_size_t nn; - mp_limb_t d; -#endif -{ - mp_limb_t rlimb; - mp_size_t i; - - /* Develop integer part of quotient. */ - rlimb = __gmpn_divmod_1_internal (qp + qxn, np, nn, d); - - /* Develop fraction part of quotient. This is not as fast as it should; - the preinvert stuff from __gmpn_divmod_1_internal ought to be used here - too. */ - if (UDIV_NEEDS_NORMALIZATION) - { - int normalization_steps; - - count_leading_zeros (normalization_steps, d); - if (normalization_steps != 0) - { - d <<= normalization_steps; - rlimb <<= normalization_steps; - - for (i = qxn - 1; i >= 0; i--) - udiv_qrnnd (qp[i], rlimb, rlimb, 0, d); - - return rlimb >> normalization_steps; - } - else - /* fall out */ - ; - } - - for (i = qxn - 1; i >= 0; i--) - udiv_qrnnd (qp[i], rlimb, rlimb, 0, d); - - return rlimb; -}