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
7 Copyright 1993-1997, 2000-2003, 2005, 2006, 2011, 2015, 2017 Free
8 Software Foundation, Inc.
9
10 This file is part of the GNU MP Library.
11
12 The GNU MP Library is free software; you can redistribute it and/or modify
13 it 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
19 or
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
25 or both in parallel, as here.
26
27 The GNU MP Library is distributed in the hope that it will be useful, but
28 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
29 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
30 for more details.
31
32 You should have received copies of the GNU General Public License and the
33 GNU Lesser General Public License along with the GNU MP Library. If not,
34 see 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. */
54 static mp_size_t
55 mpn_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
120 char *
121 mpf_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 }