bdiv_q_1.c revision 1.1.1.1
1/* mpn_bdiv_q_1, mpn_pi1_bdiv_q_1 -- schoolbook Hensel division by 1-limb 2 divisor, returning quotient only. 3 4 THE FUNCTIONS IN THIS FILE ARE FOR INTERNAL USE ONLY. THEY'RE ALMOST 5 CERTAIN TO BE SUBJECT TO INCOMPATIBLE CHANGES OR DISAPPEAR COMPLETELY IN 6 FUTURE GNU MP RELEASES. 7 8Copyright 2000, 2001, 2002, 2003, 2005, 2009 Free Software Foundation, Inc. 9 10This file is part of the GNU MP Library. 11 12The GNU MP Library is free software; you can redistribute it and/or modify 13it under the terms of the GNU Lesser General Public License as published by 14the Free Software Foundation; either version 3 of the License, or (at your 15option) any later version. 16 17The GNU MP Library is distributed in the hope that it will be useful, but 18WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 19or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 20License for more details. 21 22You should have received a copy of the GNU Lesser General Public License 23along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 24 25#include "gmp.h" 26#include "gmp-impl.h" 27#include "longlong.h" 28 29mp_limb_t 30mpn_pi1_bdiv_q_1 (mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t d, 31 mp_limb_t di, int shift) 32{ 33 mp_size_t i; 34 mp_limb_t c, h, l, u, u_next, dummy; 35 36 ASSERT (n >= 1); 37 ASSERT (d != 0); 38 ASSERT (MPN_SAME_OR_SEPARATE_P (rp, up, n)); 39 ASSERT_MPN (up, n); 40 ASSERT_LIMB (d); 41 42 d <<= GMP_NAIL_BITS; 43 44 if (shift != 0) 45 { 46 c = 0; 47 48 u = up[0]; 49 rp--; 50 for (i = 1; i < n; i++) 51 { 52 u_next = up[i]; 53 u = ((u >> shift) | (u_next << (GMP_NUMB_BITS-shift))) & GMP_NUMB_MASK; 54 55 SUBC_LIMB (c, l, u, c); 56 57 l = (l * di) & GMP_NUMB_MASK; 58 rp[i] = l; 59 60 umul_ppmm (h, dummy, l, d); 61 c += h; 62 u = u_next; 63 } 64 65 u = u >> shift; 66 l = u - c; 67 l = (l * di) & GMP_NUMB_MASK; 68 rp[i] = l; 69 } 70 else 71 { 72 u = up[0]; 73 l = (u * di) & GMP_NUMB_MASK; 74 rp[0] = l; 75 c = 0; 76 77 for (i = 1; i < n; i++) 78 { 79 umul_ppmm (h, dummy, l, d); 80 c += h; 81 82 u = up[i]; 83 SUBC_LIMB (c, l, u, c); 84 85 l = (l * di) & GMP_NUMB_MASK; 86 rp[i] = l; 87 } 88 } 89 90 return c; 91} 92 93mp_limb_t 94mpn_bdiv_q_1 (mp_ptr rp, mp_srcptr up, mp_size_t n, mp_limb_t d) 95{ 96 mp_limb_t di; 97 int shift; 98 99 ASSERT (n >= 1); 100 ASSERT (d != 0); 101 ASSERT (MPN_SAME_OR_SEPARATE_P (rp, up, n)); 102 ASSERT_MPN (up, n); 103 ASSERT_LIMB (d); 104 105 if ((d & 1) == 0) 106 { 107 count_trailing_zeros (shift, d); 108 d >>= shift; 109 } 110 else 111 shift = 0; 112 113 binvert_limb (di, d); 114 return mpn_pi1_bdiv_q_1 (rp, up, n, d, di, shift); 115} 116