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, 1994, 1995, 1996, 1997, 2000, 2001, 2002, 2003, 2005, 2006, 2011 8 Free 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 the GNU Lesser General Public License as published by 14 the Free Software Foundation; either version 3 of the License, or (at your 15 option) any later version. 16 17 The GNU MP Library is distributed in the hope that it will be useful, but 18 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY 19 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public 20 License for more details. 21 22 You should have received a copy of the GNU Lesser General Public License 23 along with the GNU MP Library. If not, see http://www.gnu.org/licenses/. */ 24 25 #include <stdlib.h> /* for NULL */ 26 #include "gmp.h" 27 #include "gmp-impl.h" 28 #include "longlong.h" /* for count_leading_zeros */ 29 30 /* Could use some more work. 31 32 1. Allocation is excessive. Try to combine areas. Perhaps use result 33 string area for temp limb space? 34 2. We generate up to two limbs of extra digits. This is because we don't 35 check the exact number of bits in the input operand, and from that 36 compute an accurate exponent (variable e in the code). It would be 37 cleaner and probably somewhat faster to change this. 38 */ 39 40 /* Compute base^exp and return the most significant prec limbs in rp[]. 41 Put the count of omitted low limbs in *ign. 42 Return the actual size (which might be less than prec). 43 Allocation of rp[] and the temporary tp[] should be 2*prec+2 limbs. */ 44 static mp_size_t 45 mpn_pow_1_highpart (mp_ptr rp, mp_size_t *ignp, 46 mp_limb_t base, unsigned long exp, 47 mp_size_t prec, mp_ptr tp) 48 { 49 mp_size_t ign; /* counts number of ignored low limbs in r */ 50 mp_size_t off; /* keeps track of offset where value starts */ 51 mp_ptr passed_rp = rp; 52 mp_size_t rn; 53 int cnt; 54 int i; 55 56 if (exp == 0) 57 { 58 rp[0] = 1; 59 *ignp = 0; 60 return 1; 61 } 62 63 rp[0] = base; 64 rn = 1; 65 off = 0; 66 ign = 0; 67 count_leading_zeros (cnt, exp); 68 for (i = GMP_LIMB_BITS - cnt - 2; i >= 0; i--) 69 { 70 mpn_sqr (tp, rp + off, rn); 71 rn = 2 * rn; 72 rn -= tp[rn - 1] == 0; 73 ign <<= 1; 74 75 off = 0; 76 if (rn > prec) 77 { 78 ign += rn - prec; 79 off = rn - prec; 80 rn = prec; 81 } 82 MP_PTR_SWAP (rp, tp); 83 84 if (((exp >> i) & 1) != 0) 85 { 86 mp_limb_t cy; 87 cy = mpn_mul_1 (rp, rp + off, rn, base); 88 rp[rn] = cy; 89 rn += cy != 0; 90 off = 0; 91 } 92 } 93 94 if (rn > prec) 95 { 96 ASSERT (rn == prec + 1); 97 98 ign += rn - prec; 99 rp += rn - prec; 100 rn = prec; 101 } 102 103 /* With somewhat less than 50% probability, we can skip this copy. */ 104 if (passed_rp != rp + off) 105 MPN_COPY_INCR (passed_rp, rp + off, rn); 106 *ignp = ign; 107 return rn; 108 } 109 110 char * 111 mpf_get_str (char *dbuf, mp_exp_t *exp, int base, size_t n_digits, mpf_srcptr u) 112 { 113 mp_exp_t ue; 114 mp_size_t n_limbs_needed; 115 size_t max_digits; 116 mp_ptr up, pp, tp; 117 mp_size_t un, pn, tn; 118 unsigned char *tstr; 119 mp_exp_t exp_in_base; 120 size_t n_digits_computed; 121 mp_size_t i; 122 const char *num_to_text; 123 size_t alloc_size = 0; 124 char *dp; 125 TMP_DECL; 126 127 up = PTR(u); 128 un = ABSIZ(u); 129 ue = EXP(u); 130 131 if (base >= 0) 132 { 133 num_to_text = "0123456789abcdefghijklmnopqrstuvwxyz"; 134 if (base <= 1) 135 base = 10; 136 else if (base > 36) 137 { 138 num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz"; 139 if (base > 62) 140 return NULL; 141 } 142 } 143 else 144 { 145 base = -base; 146 if (base <= 1) 147 base = 10; 148 else if (base > 36) 149 return NULL; 150 num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"; 151 } 152 153 MPF_SIGNIFICANT_DIGITS (max_digits, base, PREC(u)); 154 if (n_digits == 0 || n_digits > max_digits) 155 n_digits = max_digits; 156 157 if (dbuf == 0) 158 { 159 /* We didn't get a string from the user. Allocate one (and return 160 a pointer to it) with space for `-' and terminating null. */ 161 alloc_size = n_digits + 2; 162 dbuf = (char *) (*__gmp_allocate_func) (n_digits + 2); 163 } 164 165 if (un == 0) 166 { 167 *exp = 0; 168 *dbuf = 0; 169 n_digits = 0; 170 goto done; 171 } 172 173 TMP_MARK; 174 175 /* Allocate temporary digit space. We can't put digits directly in the user 176 area, since we generate more digits than requested. (We allocate 177 2 * GMP_LIMB_BITS extra bytes because of the digit block nature of the 178 conversion.) */ 179 tstr = (unsigned char *) TMP_ALLOC (n_digits + 2 * GMP_LIMB_BITS + 3); 180 181 LIMBS_PER_DIGIT_IN_BASE (n_limbs_needed, n_digits, base); 182 183 if (ue <= n_limbs_needed) 184 { 185 /* We need to multiply number by base^n to get an n_digits integer part. */ 186 mp_size_t n_more_limbs_needed, ign, off; 187 unsigned long e; 188 189 n_more_limbs_needed = n_limbs_needed - ue; 190 DIGITS_IN_BASE_PER_LIMB (e, n_more_limbs_needed, base); 191 192 if (un > n_limbs_needed) 193 { 194 up += un - n_limbs_needed; 195 un = n_limbs_needed; 196 } 197 pp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2); 198 tp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2); 199 200 pn = mpn_pow_1_highpart (pp, &ign, (mp_limb_t) base, e, n_limbs_needed, tp); 201 if (un > pn) 202 mpn_mul (tp, up, un, pp, pn); /* FIXME: mpn_mul_highpart */ 203 else 204 mpn_mul (tp, pp, pn, up, un); /* FIXME: mpn_mul_highpart */ 205 tn = un + pn; 206 tn -= tp[tn - 1] == 0; 207 off = un - ue - ign; 208 if (off < 0) 209 { 210 MPN_COPY_DECR (tp - off, tp, tn); 211 MPN_ZERO (tp, -off); 212 tn -= off; 213 off = 0; 214 } 215 n_digits_computed = mpn_get_str (tstr, base, tp + off, tn - off); 216 217 exp_in_base = n_digits_computed - e; 218 } 219 else 220 { 221 /* We need to divide number by base^n to get an n_digits integer part. */ 222 mp_size_t n_less_limbs_needed, ign, off, xn; 223 unsigned long e; 224 mp_ptr dummyp, xp; 225 226 n_less_limbs_needed = ue - n_limbs_needed; 227 DIGITS_IN_BASE_PER_LIMB (e, n_less_limbs_needed, base); 228 229 if (un > n_limbs_needed) 230 { 231 up += un - n_limbs_needed; 232 un = n_limbs_needed; 233 } 234 pp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2); 235 tp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2); 236 237 pn = mpn_pow_1_highpart (pp, &ign, (mp_limb_t) base, e, n_limbs_needed, 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