Return to mod_1_rs.c CVS log

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

Annotation of OpenXM_contrib/gmp/mpn/generic/mod_1_rs.c, Revision 1.1

1.1     ! maekawa     1: /* mpn_mod_1_rshift -- mpn remainder under hypothetical right shift.
        !             2:
        !             3:    THE FUNCTION IN THIS FILE IS FOR INTERNAL USE AND HAS A MUTABLE
        !             4:    INTERFACE.  IT IS ONLY SAFE TO REACH IT THROUGH DOCUMENTED INTERFACES.
        !             5:    IT'S ALMOST GUARANTEED THAT IT'LL CHANGE OR DISAPPEAR IN A FUTURE GNU MP
        !             6:    RELEASE. */
        !             7:
        !             8: /*
        !             9: Copyright (C) 1999, 2000 Free Software 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:
        !            33: /* When testing on a CPU with UDIV_NEEDS_NORMALIZATION equal to 0, it can be
        !            34:    changed to 1 temporarily to test the code under that case too. */
        !            35: #if 0
        !            36: #undef UDIV_NEEDS_NORMALIZATION
        !            37: #define UDIV_NEEDS_NORMALIZATION 1
        !            38: #endif
        !            39:
        !            40:
        !            41: /* Calculate the remainder "(ptr,size >> shift) % divisor".  Note ptr,size
        !            42:    is unchanged, the shift is only for its effect on the remainder.
        !            43:    The shift doesn't even need to be considered until the last limb.
        !            44:
        !            45:    This function has the normal size!=0 restriction, unlike the basic
        !            46:    mpn_mod_1. */
        !            47:
        !            48: mp_limb_t
        !            49: #if __STDC__
        !            50: mpn_mod_1_rshift (mp_srcptr ptr, mp_size_t size, unsigned shift,
        !            51:                   mp_limb_t divisor)
        !            52: #else
        !            53: mpn_mod_1_rshift (ptr, size, shift, divisor)
        !            54:      mp_srcptr ptr;
        !            55:      mp_size_t size;
        !            56:      unsigned  shift;
        !            57:      mp_limb_t divisor;
        !            58: #endif
        !            59: {
        !            60:   mp_limb_t  quot, rem;
        !            61:
        !            62:   ASSERT (shift >= 1);
        !            63:   ASSERT (shift < BITS_PER_MP_LIMB);
        !            64:   ASSERT (size >= 1);
        !            65:
        !            66:   if (size == 1)
        !            67:     return (ptr[0] >> shift) % divisor;
        !            68:
        !            69: #if UDIV_NEEDS_NORMALIZATION
        !            70:   {
        !            71:     int  norm;
        !            72:     int  delta;
        !            73:
        !            74:     count_leading_zeros (norm, divisor);
        !            75:     divisor <<= norm;
        !            76:
        !            77:     delta = shift - norm;
        !            78:     if (delta == 0)
        !            79:       return mpn_mod_1 (ptr, size, divisor) >> norm;
        !            80:
        !            81:     if (delta > 0)
        !            82:       {
        !            83:         rem = mpn_mod_1 (ptr+1, size-1, divisor);
        !            84:         udiv_qrnnd (quot, rem,
        !            85:                     rem >> delta,
        !            86:                     (rem << (BITS_PER_MP_LIMB-delta)) | (ptr[0] >> delta),
        !            87:                     divisor);
        !            88:         return rem >> norm;
        !            89:       }
        !            90:     else
        !            91:       {
        !            92:         rem = mpn_mod_1 (ptr, size, divisor);
        !            93:         udiv_qrnnd (quot, rem,
        !            94:                     rem >> (BITS_PER_MP_LIMB+delta),
        !            95:                     rem << -delta,
        !            96:                     divisor);
        !            97:         return rem >> norm;
        !            98:       }
        !            99:   }
        !           100:
        !           101: #else /* !UDIV_NEEDS_NORMALIZATION */
        !           102:
        !           103:   rem = mpn_mod_1 (ptr+1, size-1, divisor);
        !           104:   udiv_qrnnd (quot, rem,
        !           105:               rem >> shift,
        !           106:               (rem << (BITS_PER_MP_LIMB-shift)) | (ptr[0] >> shift),
        !           107:               divisor);
        !           108:   return rem;
        !           109:
        !           110: #endif
        !           111: }