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