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

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: }