[BACK]Return to mod_1.c CVS log [TXT][DIR] Up to [local] / OpenXM / src / kan96xx / gmp-2.0.2-ssh-2 / mpn / generic

Annotation of OpenXM/src/kan96xx/gmp-2.0.2-ssh-2/mpn/generic/mod_1.c, Revision 1.1.1.1

1.1       takayama    1: /* mpn_mod_1(dividend_ptr, dividend_size, divisor_limb) --
                      2:    Divide (DIVIDEND_PTR,,DIVIDEND_SIZE) by DIVISOR_LIMB.
                      3:    Return the single-limb remainder.
                      4:    There are no constraints on the value of the divisor.
                      5:
                      6: Copyright (C) 1991, 1993, 1994, Free Software Foundation, Inc.
                      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
                     11: it under the terms of the GNU Library General Public License as published by
                     12: the Free Software Foundation; either version 2 of the License, or (at your
                     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
                     17: or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
                     18: License for more details.
                     19:
                     20: You should have received a copy of the GNU Library General Public License
                     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: #ifndef UMUL_TIME
                     30: #define UMUL_TIME 1
                     31: #endif
                     32:
                     33: #ifndef UDIV_TIME
                     34: #define UDIV_TIME UMUL_TIME
                     35: #endif
                     36:
                     37: /* FIXME: We should be using invert_limb (or invert_normalized_limb)
                     38:    here (not udiv_qrnnd).  */
                     39:
                     40: mp_limb_t
                     41: #if __STDC__
                     42: mpn_mod_1 (mp_srcptr dividend_ptr, mp_size_t dividend_size,
                     43:           mp_limb_t divisor_limb)
                     44: #else
                     45: mpn_mod_1 (dividend_ptr, dividend_size, divisor_limb)
                     46:      mp_srcptr dividend_ptr;
                     47:      mp_size_t dividend_size;
                     48:      mp_limb_t divisor_limb;
                     49: #endif
                     50: {
                     51:   mp_size_t i;
                     52:   mp_limb_t n1, n0, r;
                     53:   int dummy;
                     54:
                     55:   /* Botch: Should this be handled at all?  Rely on callers?  */
                     56:   if (dividend_size == 0)
                     57:     return 0;
                     58:
                     59:   /* If multiplication is much faster than division, and the
                     60:      dividend is large, pre-invert the divisor, and use
                     61:      only multiplications in the inner loop.  */
                     62:
                     63:   /* This test should be read:
                     64:        Does it ever help to use udiv_qrnnd_preinv?
                     65:         && Does what we save compensate for the inversion overhead?  */
                     66:   if (UDIV_TIME > (2 * UMUL_TIME + 6)
                     67:       && (UDIV_TIME - (2 * UMUL_TIME + 6)) * dividend_size > UDIV_TIME)
                     68:     {
                     69:       int normalization_steps;
                     70:
                     71:       count_leading_zeros (normalization_steps, divisor_limb);
                     72:       if (normalization_steps != 0)
                     73:        {
                     74:          mp_limb_t divisor_limb_inverted;
                     75:
                     76:          divisor_limb <<= normalization_steps;
                     77:
                     78:          /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
                     79:             result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
                     80:             most significant bit (with weight 2**N) implicit.  */
                     81:
                     82:          /* Special case for DIVISOR_LIMB == 100...000.  */
                     83:          if (divisor_limb << 1 == 0)
                     84:            divisor_limb_inverted = ~(mp_limb_t) 0;
                     85:          else
                     86:            udiv_qrnnd (divisor_limb_inverted, dummy,
                     87:                        -divisor_limb, 0, divisor_limb);
                     88:
                     89:          n1 = dividend_ptr[dividend_size - 1];
                     90:          r = n1 >> (BITS_PER_MP_LIMB - normalization_steps);
                     91:
                     92:          /* Possible optimization:
                     93:             if (r == 0
                     94:             && divisor_limb > ((n1 << normalization_steps)
                     95:                             | (dividend_ptr[dividend_size - 2] >> ...)))
                     96:             ...one division less... */
                     97:
                     98:          for (i = dividend_size - 2; i >= 0; i--)
                     99:            {
                    100:              n0 = dividend_ptr[i];
                    101:              udiv_qrnnd_preinv (dummy, r, r,
                    102:                                 ((n1 << normalization_steps)
                    103:                                  | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))),
                    104:                                 divisor_limb, divisor_limb_inverted);
                    105:              n1 = n0;
                    106:            }
                    107:          udiv_qrnnd_preinv (dummy, r, r,
                    108:                             n1 << normalization_steps,
                    109:                             divisor_limb, divisor_limb_inverted);
                    110:          return r >> normalization_steps;
                    111:        }
                    112:       else
                    113:        {
                    114:          mp_limb_t divisor_limb_inverted;
                    115:
                    116:          /* Compute (2**2N - 2**N * DIVISOR_LIMB) / DIVISOR_LIMB.  The
                    117:             result is a (N+1)-bit approximation to 1/DIVISOR_LIMB, with the
                    118:             most significant bit (with weight 2**N) implicit.  */
                    119:
                    120:          /* Special case for DIVISOR_LIMB == 100...000.  */
                    121:          if (divisor_limb << 1 == 0)
                    122:            divisor_limb_inverted = ~(mp_limb_t) 0;
                    123:          else
                    124:            udiv_qrnnd (divisor_limb_inverted, dummy,
                    125:                        -divisor_limb, 0, divisor_limb);
                    126:
                    127:          i = dividend_size - 1;
                    128:          r = dividend_ptr[i];
                    129:
                    130:          if (r >= divisor_limb)
                    131:            r = 0;
                    132:          else
                    133:            i--;
                    134:
                    135:          for (; i >= 0; i--)
                    136:            {
                    137:              n0 = dividend_ptr[i];
                    138:              udiv_qrnnd_preinv (dummy, r, r,
                    139:                                 n0, divisor_limb, divisor_limb_inverted);
                    140:            }
                    141:          return r;
                    142:        }
                    143:     }
                    144:   else
                    145:     {
                    146:       if (UDIV_NEEDS_NORMALIZATION)
                    147:        {
                    148:          int normalization_steps;
                    149:
                    150:          count_leading_zeros (normalization_steps, divisor_limb);
                    151:          if (normalization_steps != 0)
                    152:            {
                    153:              divisor_limb <<= normalization_steps;
                    154:
                    155:              n1 = dividend_ptr[dividend_size - 1];
                    156:              r = n1 >> (BITS_PER_MP_LIMB - normalization_steps);
                    157:
                    158:              /* Possible optimization:
                    159:                 if (r == 0
                    160:                 && divisor_limb > ((n1 << normalization_steps)
                    161:                                 | (dividend_ptr[dividend_size - 2] >> ...)))
                    162:                 ...one division less... */
                    163:
                    164:              for (i = dividend_size - 2; i >= 0; i--)
                    165:                {
                    166:                  n0 = dividend_ptr[i];
                    167:                  udiv_qrnnd (dummy, r, r,
                    168:                              ((n1 << normalization_steps)
                    169:                               | (n0 >> (BITS_PER_MP_LIMB - normalization_steps))),
                    170:                              divisor_limb);
                    171:                  n1 = n0;
                    172:                }
                    173:              udiv_qrnnd (dummy, r, r,
                    174:                          n1 << normalization_steps,
                    175:                          divisor_limb);
                    176:              return r >> normalization_steps;
                    177:            }
                    178:        }
                    179:       /* No normalization needed, either because udiv_qrnnd doesn't require
                    180:         it, or because DIVISOR_LIMB is already normalized.  */
                    181:
                    182:       i = dividend_size - 1;
                    183:       r = dividend_ptr[i];
                    184:
                    185:       if (r >= divisor_limb)
                    186:        r = 0;
                    187:       else
                    188:        i--;
                    189:
                    190:       for (; i >= 0; i--)
                    191:        {
                    192:          n0 = dividend_ptr[i];
                    193:          udiv_qrnnd (dummy, r, r, n0, divisor_limb);
                    194:        }
                    195:       return r;
                    196:     }
                    197: }

FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>