1/* mpf_get_str (digit_ptr, exp, base, n_digits, a) -- Convert the floating
2   point number A to a base BASE number and store N_DIGITS raw digits at
3   DIGIT_PTR, and the base BASE exponent in the word pointed to by EXP.  For
4   example, the number 3.1416 would be returned as "31416" in DIGIT_PTR and
5   1 in EXP.
6
7Copyright 1993-1997, 2000-2003, 2005, 2006, 2011, 2015, 2017 Free
8Software 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 either:
14
15  * the GNU Lesser General Public License as published by the Free
16    Software Foundation; either version 3 of the License, or (at your
17    option) any later version.
18
19or
20
21  * the GNU General Public License as published by the Free Software
22    Foundation; either version 2 of the License, or (at your option) any
23    later version.
24
25or both in parallel, as here.
26
27The GNU MP Library is distributed in the hope that it will be useful, but
28WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
29or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
30for more details.
31
32You should have received copies of the GNU General Public License and the
33GNU Lesser General Public License along with the GNU MP Library.  If not,
34see https://www.gnu.org/licenses/.  */
35
36#include <stdlib.h>		/* for NULL */
37#include "gmp-impl.h"
38#include "longlong.h"		/* for count_leading_zeros */
39
40/* Could use some more work.
41
42   1. Allocation is excessive.  Try to combine areas.  Perhaps use result
43      string area for temp limb space?
44   2. We generate up to two limbs of extra digits.  This is because we don't
45      check the exact number of bits in the input operand, and from that
46      compute an accurate exponent (variable e in the code).  It would be
47      cleaner and probably somewhat faster to change this.
48*/
49
50/* Compute base^exp and return the most significant prec limbs in rp[].
51   Put the count of omitted low limbs in *ign.
52   Return the actual size (which might be less than prec).
53   Allocation of rp[] and the temporary tp[] should be 2*prec+2 limbs.  */
54static mp_size_t
55mpn_pow_1_highpart (mp_ptr rp, mp_size_t *ignp,
56		    mp_limb_t base, unsigned long exp,
57		    mp_size_t prec, mp_ptr tp)
58{
59  mp_size_t ign;		/* counts number of ignored low limbs in r */
60  mp_size_t off;		/* keeps track of offset where value starts */
61  mp_ptr passed_rp = rp;
62  mp_size_t rn;
63  int cnt;
64  int i;
65
66  if (exp == 0)
67    {
68      rp[0] = 1;
69      *ignp = 0;
70      return 1;
71    }
72
73  rp[0] = base;
74  rn = 1;
75  off = 0;
76  ign = 0;
77  count_leading_zeros (cnt, exp);
78  for (i = GMP_LIMB_BITS - cnt - 2; i >= 0; i--)
79    {
80      mpn_sqr (tp, rp + off, rn);
81      rn = 2 * rn;
82      rn -= tp[rn - 1] == 0;
83      ign <<= 1;
84
85      off = 0;
86      if (rn > prec)
87	{
88	  ign += rn - prec;
89	  off = rn - prec;
90	  rn = prec;
91	}
92      MP_PTR_SWAP (rp, tp);
93
94      if (((exp >> i) & 1) != 0)
95	{
96	  mp_limb_t cy;
97	  cy = mpn_mul_1 (rp, rp + off, rn, base);
98	  rp[rn] = cy;
99	  rn += cy != 0;
100	  off = 0;
101	}
102    }
103
104  if (rn > prec)
105    {
106      ASSERT (rn == prec + 1);
107
108      ign += rn - prec;
109      rp += rn - prec;
110      rn = prec;
111    }
112
113  /* With somewhat less than 50% probability, we can skip this copy.  */
114  if (passed_rp != rp + off)
115    MPN_COPY_INCR (passed_rp, rp + off, rn);
116  *ignp = ign;
117  return rn;
118}
119
120char *
121mpf_get_str (char *dbuf, mp_exp_t *exp, int base, size_t n_digits, mpf_srcptr u)
122{
123  mp_exp_t ue;
124  mp_size_t n_limbs_needed;
125  size_t max_digits;
126  mp_ptr up, pp, tp;
127  mp_size_t un, pn, tn;
128  unsigned char *tstr;
129  mp_exp_t exp_in_base;
130  size_t n_digits_computed;
131  mp_size_t i;
132  const char *num_to_text;
133  size_t alloc_size = 0;
134  char *dp;
135  TMP_DECL;
136
137  up = PTR(u);
138  un = ABSIZ(u);
139  ue = EXP(u);
140
141  num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";
142  if (base > 1)
143    {
144      if (base <= 36)
145	num_to_text = "0123456789abcdefghijklmnopqrstuvwxyz";
146      else if (UNLIKELY (base > 62))
147	    return NULL;
148    }
149  else if (base > -2)
150    {
151      base = 10;
152    }
153  else
154    {
155      base = -base;
156      if (UNLIKELY (base > 36))
157	return NULL;
158    }
159
160  MPF_SIGNIFICANT_DIGITS (max_digits, base, PREC(u));
161  if (n_digits == 0 || n_digits > max_digits)
162    n_digits = max_digits;
163
164  if (dbuf == 0)
165    {
166      /* We didn't get a string from the user.  Allocate one (and return
167	 a pointer to it) with space for `-' and terminating null.  */
168      alloc_size = n_digits + 2;
169      dbuf = __GMP_ALLOCATE_FUNC_TYPE (n_digits + 2, char);
170    }
171
172  if (un == 0)
173    {
174      *exp = 0;
175      *dbuf = 0;
176      n_digits = 0;
177      goto done;
178    }
179
180  TMP_MARK;
181
182  /* Allocate temporary digit space.  We can't put digits directly in the user
183     area, since we generate more digits than requested.  (We allocate
184     2 * GMP_LIMB_BITS extra bytes because of the digit block nature of the
185     conversion.)  */
186  tstr = (unsigned char *) TMP_ALLOC (n_digits + 2 * GMP_LIMB_BITS + 3);
187
188  LIMBS_PER_DIGIT_IN_BASE (n_limbs_needed, n_digits, base);
189
190  if (un > n_limbs_needed)
191    {
192      up += un - n_limbs_needed;
193      un = n_limbs_needed;
194    }
195
196  TMP_ALLOC_LIMBS_2 (pp, 2 * n_limbs_needed + 4,
197		     tp, 2 * n_limbs_needed + 4);
198
199  if (ue <= n_limbs_needed)
200    {
201      /* We need to multiply number by base^n to get an n_digits integer part.  */
202      mp_size_t n_more_limbs_needed, ign, off;
203      unsigned long e;
204
205      n_more_limbs_needed = n_limbs_needed - ue;
206      DIGITS_IN_BASE_PER_LIMB (e, n_more_limbs_needed, base);
207
208      pn = mpn_pow_1_highpart (pp, &ign, (mp_limb_t) base, e, n_limbs_needed + 1, tp);
209      if (un > pn)
210	mpn_mul (tp, up, un, pp, pn);	/* FIXME: mpn_mul_highpart */
211      else
212	mpn_mul (tp, pp, pn, up, un);	/* FIXME: mpn_mul_highpart */
213      tn = un + pn;
214      tn -= tp[tn - 1] == 0;
215      off = un - ue - ign;
216      if (off < 0)
217	{
218	  MPN_COPY_DECR (tp - off, tp, tn);
219	  MPN_ZERO (tp, -off);
220	  tn -= off;
221	  off = 0;
222	}
223      n_digits_computed = mpn_get_str (tstr, base, tp + off, tn - off);
224
225      exp_in_base = n_digits_computed - e;
226    }
227  else
228    {
229      /* We need to divide number by base^n to get an n_digits integer part.  */
230      mp_size_t n_less_limbs_needed, ign, off, xn;
231      unsigned long e;
232      mp_ptr dummyp, xp;
233
234      n_less_limbs_needed = ue - n_limbs_needed;
235      DIGITS_IN_BASE_PER_LIMB (e, n_less_limbs_needed, base);
236
237      pn = mpn_pow_1_highpart (pp, &ign, (mp_limb_t) base, e, n_limbs_needed + 1, tp);
238
239      xn = n_limbs_needed + (n_less_limbs_needed-ign);
240      xp = TMP_ALLOC_LIMBS (xn);
241      off = xn - un;
242      MPN_ZERO (xp, off);
243      MPN_COPY (xp + off, up, un);
244
245      dummyp = TMP_ALLOC_LIMBS (pn);
246      mpn_tdiv_qr (tp, dummyp, (mp_size_t) 0, xp, xn, pp, pn);
247      tn = xn - pn + 1;
248      tn -= tp[tn - 1] == 0;
249      n_digits_computed = mpn_get_str (tstr, base, tp, tn);
250
251      exp_in_base = n_digits_computed + e;
252    }
253
254  /* We should normally have computed too many digits.  Round the result
255     at the point indicated by n_digits.  */
256  if (n_digits_computed > n_digits)
257    {
258      size_t i;
259      /* Round the result.  */
260      if (tstr[n_digits] * 2 >= base)
261	{
262	  n_digits_computed = n_digits;
263	  for (i = n_digits - 1;; i--)
264	    {
265	      unsigned int x;
266	      x = ++(tstr[i]);
267	      if (x != base)
268		break;
269	      n_digits_computed--;
270	      if (i == 0)
271		{
272		  /* We had something like `bbbbbbb...bd', where 2*d >= base
273		     and `b' denotes digit with significance base - 1.
274		     This rounds up to `1', increasing the exponent.  */
275		  tstr[0] = 1;
276		  n_digits_computed = 1;
277		  exp_in_base++;
278		  break;
279		}
280	    }
281	}
282    }
283
284  /* We might have fewer digits than requested as a result of rounding above,
285     (i.e. 0.999999 => 1.0) or because we have a number that simply doesn't
286     need many digits in this base (e.g., 0.125 in base 10).  */
287  if (n_digits > n_digits_computed)
288    n_digits = n_digits_computed;
289
290  /* Remove trailing 0.  There can be many zeros.  */
291  while (n_digits != 0 && tstr[n_digits - 1] == 0)
292    n_digits--;
293
294  dp = dbuf + (SIZ(u) < 0);
295
296  /* Translate to ASCII and copy to result string.  */
297  for (i = 0; i < n_digits; i++)
298    dp[i] = num_to_text[tstr[i]];
299  dp[n_digits] = 0;
300
301  *exp = exp_in_base;
302
303  if (SIZ(u) < 0)
304    {
305      dbuf[0] = '-';
306      n_digits++;
307    }
308
309  TMP_FREE;
310
311 done:
312  /* If the string was alloced then resize it down to the actual space
313     required.  */
314  if (alloc_size != 0)
315    {
316      __GMP_REALLOCATE_FUNC_MAYBE_TYPE (dbuf, alloc_size, n_digits + 1, char);
317    }
318
319  return dbuf;
320}
321