rts/gmp/mpn/generic/mod_1_rs.c

   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 }