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