contrib/gmp/mpf/get_str.c

   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 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 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_n (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 == 0)
 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       num_to_text = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 147     }
 148
 149   MPF_SIGNIFICANT_DIGITS (max_digits, base, PREC(u));
 150   if (n_digits == 0 || n_digits > max_digits)
 151     n_digits = max_digits;
 152
 153   if (dbuf == 0)
 154     {
 155       /* We didn't get a string from the user.  Allocate one (and return
 156          a pointer to it) with space for `-' and terminating null.  */
 157       alloc_size = n_digits + 2;
 158       dbuf = (char *) (*__gmp_allocate_func) (n_digits + 2);
 159     }
 160
 161   if (un == 0)
 162     {
 163       *exp = 0;
 164       *dbuf = 0;
 165       n_digits = 0;
 166       goto done;
 167     }
 168
 169   TMP_MARK;
 170
 171   /* Allocate temporary digit space.  We can't put digits directly in the user
 172      area, since we generate more digits than requested.  (We allocate
 173      2 * GMP_LIMB_BITS extra bytes because of the digit block nature of the
 174      conversion.)  */
 175   tstr = (unsigned char *) TMP_ALLOC (n_digits + 2 * GMP_LIMB_BITS + 3);
 176
 177   n_limbs_needed = 2 + ((mp_size_t) (n_digits / mp_bases[base].chars_per_bit_exactly)) / GMP_NUMB_BITS;
 178
 179   if (ue <= n_limbs_needed)
 180     {
 181       /* We need to multiply number by base^n to get an n_digits integer part.  */
 182       mp_size_t n_more_limbs_needed, ign, off;
 183       unsigned long e;
 184
 185       n_more_limbs_needed = n_limbs_needed - ue;
 186       e = (unsigned long) n_more_limbs_needed * (GMP_NUMB_BITS * mp_bases[base].chars_per_bit_exactly);
 187
 188       if (un > n_limbs_needed)
 189         {
 190           up += un - n_limbs_needed;
 191           un = n_limbs_needed;
 192         }
 193       pp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2);
 194       tp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2);
 195
 196       pn = mpn_pow_1_highpart (pp, &ign, (mp_limb_t) base, e, n_limbs_needed, tp);
 197       if (un > pn)
 198         mpn_mul (tp, up, un, pp, pn);   /* FIXME: mpn_mul_highpart */
 199       else
 200         mpn_mul (tp, pp, pn, up, un);   /* FIXME: mpn_mul_highpart */
 201       tn = un + pn;
 202       tn -= tp[tn - 1] == 0;
 203       off = un - ue - ign;
 204       if (off < 0)
 205         {
 206           MPN_COPY_DECR (tp - off, tp, tn);
 207           MPN_ZERO (tp, -off);
 208           tn -= off;
 209           off = 0;
 210         }
 211       n_digits_computed = mpn_get_str (tstr, base, tp + off, tn - off);
 212
 213       exp_in_base = n_digits_computed - e;
 214     }
 215   else
 216     {
 217       /* We need to divide number by base^n to get an n_digits integer part.  */
 218       mp_size_t n_less_limbs_needed, ign, off, xn;
 219       unsigned long e;
 220       mp_ptr dummyp, xp;
 221
 222       n_less_limbs_needed = ue - n_limbs_needed;
 223       e = (unsigned long) n_less_limbs_needed * (GMP_NUMB_BITS * mp_bases[base].chars_per_bit_exactly);
 224
 225       if (un > n_limbs_needed)
 226         {
 227           up += un - n_limbs_needed;
 228           un = n_limbs_needed;
 229         }
 230       pp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2);
 231       tp = TMP_ALLOC_LIMBS (2 * n_limbs_needed + 2);
 232
 233       pn = mpn_pow_1_highpart (pp, &ign, (mp_limb_t) base, e, n_limbs_needed, tp);
 234
 235       xn = n_limbs_needed + (n_less_limbs_needed-ign);
 236       xp = TMP_ALLOC_LIMBS (xn);
 237       off = xn - un;
 238       MPN_ZERO (xp, off);
 239       MPN_COPY (xp + off, up, un);
 240
 241       dummyp = TMP_ALLOC_LIMBS (pn);
 242       mpn_tdiv_qr (tp, dummyp, (mp_size_t) 0, xp, xn, pp, pn);
 243       tn = xn - pn + 1;
 244       tn -= tp[tn - 1] == 0;
 245       n_digits_computed = mpn_get_str (tstr, base, tp, tn);
 246
 247       exp_in_base = n_digits_computed + e;
 248     }
 249
 250   /* We should normally have computed too many digits.  Round the result
 251      at the point indicated by n_digits.  */
 252   if (n_digits_computed > n_digits)
 253     {
 254       size_t i;
 255       /* Round the result.  */
 256       if (tstr[n_digits] * 2 >= base)
 257         {
 258           n_digits_computed = n_digits;
 259           for (i = n_digits - 1;; i--)
 260             {
 261               unsigned int x;
 262               x = ++(tstr[i]);
 263               if (x != base)
 264                 break;
 265               n_digits_computed--;
 266               if (i == 0)
 267                 {
 268                   /* We had something like `bbbbbbb...bd', where 2*d >= base
 269                      and `b' denotes digit with significance base - 1.
 270                      This rounds up to `1', increasing the exponent.  */
 271                   tstr[0] = 1;
 272                   n_digits_computed = 1;
 273                   exp_in_base++;
 274                   break;
 275                 }
 276             }
 277         }
 278     }
 279
 280   /* We might have fewer digits than requested as a result of rounding above,
 281      (i.e. 0.999999 => 1.0) or because we have a number that simply doesn't
 282      need many digits in this base (e.g., 0.125 in base 10).  */
 283   if (n_digits > n_digits_computed)
 284     n_digits = n_digits_computed;
 285
 286   /* Remove trailing 0.  There can be many zeros.  */
 287   while (n_digits != 0 && tstr[n_digits - 1] == 0)
 288     n_digits--;
 289
 290   dp = dbuf + (SIZ(u) < 0);
 291
 292   /* Translate to ASCII and copy to result string.  */
 293   for (i = 0; i < n_digits; i++)
 294     dp[i] = num_to_text[tstr[i]];
 295   dp[n_digits] = 0;
 296
 297   *exp = exp_in_base;
 298
 299   if (SIZ(u) < 0)
 300     {
 301       dbuf[0] = '-';
 302       n_digits++;
 303     }
 304
 305   TMP_FREE;
 306
 307  done:
 308   /* If the string was alloced then resize it down to the actual space
 309      required.  */
 310   if (alloc_size != 0)
 311     {
 312       __GMP_REALLOCATE_FUNC_MAYBE_TYPE (dbuf, alloc_size, n_digits + 1, char);
 313     }
 314
 315   return dbuf;
 316 }