1/* mpq_mul_2exp, mpq_div_2exp - multiply or divide by 2^N */ 2 3/* 4Copyright 2000, 2002 Free Software Foundation, Inc. 5 6This file is part of the GNU MP Library. 7 8The GNU MP Library is free software; you can redistribute it and/or modify 9it under the terms of the GNU Lesser General Public License as published by 10the Free Software Foundation; either version 3 of the License, or (at your 11option) any later version. 12 13The GNU MP Library is distributed in the hope that it will be useful, but 14WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 15or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 16License for more details. 17 18You should have received a copy of the GNU Lesser General Public License 19along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 20 21#include "gmp.h" 22#include "gmp-impl.h" 23#include "longlong.h" 24 25 26/* The multiplier/divisor "n", representing 2^n, is applied by right shifting 27 "r" until it's odd (if it isn't already), and left shifting "l" for the 28 rest. */ 29 30static void 31mord_2exp (mpz_ptr ldst, mpz_ptr rdst, mpz_srcptr lsrc, mpz_srcptr rsrc, 32 mp_bitcnt_t n) 33{ 34 mp_size_t rsrc_size = SIZ(rsrc); 35 mp_size_t len = ABS (rsrc_size); 36 mp_ptr rsrc_ptr = PTR(rsrc); 37 mp_ptr p, rdst_ptr; 38 mp_limb_t plow; 39 40 p = rsrc_ptr; 41 plow = *p; 42 while (n >= GMP_NUMB_BITS && plow == 0) 43 { 44 n -= GMP_NUMB_BITS; 45 p++; 46 plow = *p; 47 } 48 49 /* no realloc here if rsrc==rdst, so p and rsrc_ptr remain valid */ 50 len -= (p - rsrc_ptr); 51 MPZ_REALLOC (rdst, len); 52 rdst_ptr = PTR(rdst); 53 54 if ((plow & 1) || n == 0) 55 { 56 /* need DECR when src==dst */ 57 if (p != rdst_ptr) 58 MPN_COPY_DECR (rdst_ptr, p, len); 59 } 60 else 61 { 62 unsigned long shift; 63 if (plow == 0) 64 shift = n; 65 else 66 { 67 count_trailing_zeros (shift, plow); 68 shift = MIN (shift, n); 69 } 70 mpn_rshift (rdst_ptr, p, len, shift); 71 len -= (rdst_ptr[len-1] == 0); 72 n -= shift; 73 } 74 SIZ(rdst) = (rsrc_size >= 0) ? len : -len; 75 76 if (n) 77 mpz_mul_2exp (ldst, lsrc, n); 78 else if (ldst != lsrc) 79 mpz_set (ldst, lsrc); 80} 81 82 83void 84mpq_mul_2exp (mpq_ptr dst, mpq_srcptr src, mp_bitcnt_t n) 85{ 86 mord_2exp (mpq_numref (dst), mpq_denref (dst), 87 mpq_numref (src), mpq_denref (src), n); 88} 89 90void 91mpq_div_2exp (mpq_ptr dst, mpq_srcptr src, mp_bitcnt_t n) 92{ 93 if (SIZ (mpq_numref(src)) == 0) 94 { 95 dst->_mp_num._mp_size = 0; 96 dst->_mp_den._mp_size = 1; 97 dst->_mp_den._mp_d[0] = 1; 98 return; 99 } 100 101 mord_2exp (mpq_denref (dst), mpq_numref (dst), 102 mpq_denref (src), mpq_numref (src), n); 103} 104