ghc/runtime/gmp/_mpz_get_str.c

   1 /* _mpz_get_str (string, base, mp_src) -- Convert the multiple precision
   2    number MP_SRC to a string STRING of base BASE.  If STRING is NULL
   3    allocate space for the result.  In any case, return a pointer to the
   4    result.  If STRING is not NULL, the caller must ensure enough space is
   5    available to store the result.
   6
   7 Copyright (C) 1991, 1993 Free Software Foundation, Inc.
   8
   9 This file is part of the GNU MP Library.
  10
  11 The GNU MP Library is free software; you can redistribute it and/or modify
  12 it under the terms of the GNU General Public License as published by
  13 the Free Software Foundation; either version 2, or (at your option)
  14 any later version.
  15
  16 The GNU MP Library is distributed in the hope that it will be useful,
  17 but WITHOUT ANY WARRANTY; without even the implied warranty of
  18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  19 GNU General Public License for more details.
  20
  21 You should have received a copy of the GNU General Public License
  22 along with the GNU MP Library; see the file COPYING.  If not, write to
  23 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.  */
  24
  25 #include "gmp.h"
  26 #include "gmp-impl.h"
  27 #include "longlong.h"
  28
  29 #ifndef UMUL_TIME
  30 #define UMUL_TIME 1
  31 #endif
  32
  33 #ifndef UDIV_TIME
  34 #define UDIV_TIME UMUL_TIME
  35 #endif
  36
  37 #define udiv_qrnndx(q, r, nh, nl, d, di) \
  38   do {                                                                  \
  39     unsigned long int _q, _ql, _r;                                      \
  40     unsigned long int _xh, _xl;                                         \
  41     umul_ppmm (_q, _ql, (nh), (di));                                    \
  42     _q += (nh);                 /* DI is 2**32 too small.  Compensate */\
  43     if (_q < (nh))                                                      \
  44       {                                                                 \
  45         /* Got carry.  Propagate it in the multiplication.  */          \
  46         umul_ppmm (_xh, _xl, (d), _q);                                  \
  47         _xh += (d);                                                     \
  48       }                                                                 \
  49     else                                                                \
  50       umul_ppmm (_xh, _xl, (d), _q);                                    \
  51     sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl);                         \
  52     if (_xh != 0)                                                       \
  53       {                                                                 \
  54         sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                          \
  55         _q += 1;                                                        \
  56         if (_xh != 0)                                                   \
  57           {                                                             \
  58             sub_ddmmss (_xh, _r, _xh, _r, 0, (d));                      \
  59             _q += 1;                                                    \
  60           }                                                             \
  61       }                                                                 \
  62     if (_r >= (d))                                                      \
  63       {                                                                 \
  64         _r -= (d);                                                      \
  65         _q += 1;                                                        \
  66       }                                                                 \
  67     (r) = _r;                                                           \
  68     (q) = _q;                                                           \
  69   } while (0)
  70
  71 char *
  72 #ifdef __STDC__
  73 _mpz_get_str (char *str, int base, const MP_INT *m)
  74 #else
  75 _mpz_get_str (str, base, m)
  76      char *str;
  77      int base;
  78      const MP_INT *m;
  79 #endif
  80 {
  81   mp_ptr tp;
  82   mp_size msize;
  83   mp_limb big_base;
  84 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
  85
  86   int normalization_steps;
  87 #if UDIV_TIME > 2 * UMUL_TIME
  88   mp_limb big_base_inverted;
  89 #endif
  90 #endif
  91   unsigned int dig_per_u;
  92   mp_size out_len;
  93   char *s;
  94   char *num_to_ascii;
  95
  96   if (base >= 0)
  97     {
  98       if (base == 0)
  99         base = 10;
 100       num_to_ascii = "0123456789abcdefghijklmnopqrstuvwxyz";
 101     }
 102   else
 103     {
 104       base = -base;
 105       num_to_ascii = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
 106     }
 107
 108   dig_per_u = __mp_bases[base].chars_per_limb;
 109   out_len = mpz_sizeinbase (m, base) + 1;
 110   big_base = __mp_bases[base].big_base;
 111
 112   msize = m->size;
 113
 114   if (str == NULL)
 115     str = (char *) (*_mp_allocate_func) (out_len + (msize < 0));
 116
 117   if (msize < 0)
 118     *str++ = '-';
 119   s = str;
 120
 121   msize = ABS (msize);
 122
 123   /* Special case zero, as the code below doesn't handle it.  */
 124   if (msize == 0)
 125     {
 126       s[0] = '0';
 127       s[1] = 0;
 128       return str;
 129     }
 130
 131   if ((base & (base - 1)) == 0)
 132     {
 133       /* The base is a power of 2.  Make conversion from most
 134          significant side.  */
 135       mp_limb n1, n0;
 136       int bits_per_digit = big_base;
 137       int x;
 138       int bit_pos;
 139       int i;
 140       unsigned mask = (1 << bits_per_digit) - 1;
 141
 142       tp = m->d;
 143       n1 = tp[msize - 1];
 144       count_leading_zeros (x, n1);
 145
 146         /* BIT_POS should be R when input ends in least sign. nibble,
 147            R + bits_per_digit * n when input ends in n:th least significant
 148            nibble. */
 149
 150       {
 151         int bits;
 152
 153         bits = BITS_PER_MP_LIMB * msize - x;
 154         x = bits % bits_per_digit;
 155         if (x != 0)
 156           bits += bits_per_digit - x;
 157         bit_pos = bits - (msize - 1) * BITS_PER_MP_LIMB;
 158       }
 159
 160       /* Fast loop for bit output.  */
 161       i = msize - 1;
 162       for (;;)
 163         {
 164           bit_pos -= bits_per_digit;
 165           while (bit_pos >= 0)
 166             {
 167               *s++ = num_to_ascii[(n1 >> bit_pos) & mask];
 168               bit_pos -= bits_per_digit;
 169             }
 170           i--;
 171           if (i < 0)
 172             break;
 173           n0 = (n1 << -bit_pos) & mask;
 174           n1 = tp[i];
 175           bit_pos += BITS_PER_MP_LIMB;
 176           *s++ = num_to_ascii[n0 | (n1 >> bit_pos)];
 177         }
 178
 179       *s = 0;
 180     }
 181   else
 182     {
 183       /* General case.  The base is not a power of 2.  Make conversion
 184          from least significant end.  */
 185
 186       /* If udiv_qrnnd only handles divisors with the most significant bit
 187          set, prepare BIG_BASE for being a divisor by shifting it to the
 188          left exactly enough to set the most significant bit.  */
 189 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
 190       count_leading_zeros (normalization_steps, big_base);
 191       big_base <<= normalization_steps;
 192 #if UDIV_TIME > 2 * UMUL_TIME
 193       /* Get the fixed-point approximation to 1/BIG_BASE.  */
 194       big_base_inverted = __mp_bases[base].big_base_inverted;
 195 #endif
 196 #endif
 197
 198       out_len--;                /* now not include terminating \0 */
 199       s += out_len;
 200
 201       /* Allocate temporary space and move the multi prec number to
 202          convert there, as we need to overwrite it below, while
 203          computing the successive remainders.  */
 204       tp = (mp_ptr) alloca ((msize + 1) * BYTES_PER_MP_LIMB);
 205       MPN_COPY (tp, m->d, msize);
 206
 207       while (msize != 0)
 208         {
 209           int i;
 210           mp_limb n0, n1;
 211
 212 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
 213           /* If we shifted BIG_BASE above, shift the dividend too, to get
 214              the right quotient.  We need to do this every loop,
 215              as the intermediate quotients are OK, but the quotient from
 216              one turn in the loop is going to be the dividend in the
 217              next turn, and the dividend needs to be up-shifted.  */
 218           if (normalization_steps != 0)
 219             {
 220               n0 = mpn_lshift (tp, tp, msize, normalization_steps);
 221
 222               /* If the shifting gave a carry out limb, store it and
 223                  increase the length.  */
 224               if (n0 != 0)
 225                 {
 226                   tp[msize] = n0;
 227                   msize++;
 228                 }
 229             }
 230 #endif
 231
 232           /* Divide the number at TP with BIG_BASE to get a quotient and a
 233              remainder.  The remainder is our new digit in base BIG_BASE.  */
 234           i = msize - 1;
 235           n1 = tp[i];
 236
 237           if (n1 >= big_base)
 238             n1 = 0;
 239           else
 240             {
 241               msize--;
 242               i--;
 243             }
 244
 245           for (; i >= 0; i--)
 246             {
 247               n0 = tp[i];
 248 #if UDIV_TIME > 2 * UMUL_TIME
 249               udiv_qrnndx (tp[i], n1, n1, n0, big_base, big_base_inverted);
 250 #else
 251               udiv_qrnnd (tp[i], n1, n1, n0, big_base);
 252 #endif
 253             }
 254
 255 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
 256           /* If we shifted above (at previous UDIV_NEEDS_NORMALIZATION tests)
 257              the remainder will be up-shifted here.  Compensate.  */
 258           n1 >>= normalization_steps;
 259 #endif
 260
 261           /* Convert N1 from BIG_BASE to a string of digits in BASE
 262              using single precision operations.  */
 263           for (i = dig_per_u - 1; i >= 0; i--)
 264             {
 265               *--s = num_to_ascii[n1 % base];
 266               n1 /= base;
 267               /* Break from the loop as soon as we would only write zeros.  */
 268               if (n1 == 0 && msize == 0)
 269                 break;
 270             }
 271         }
 272
 273       /* There should be no leading zeros.  */
 274       if (*s == '0')
 275         abort ();
 276
 277       if (s == str)
 278         {
 279           /* This should be the common case.  */
 280           s[out_len] = 0;
 281         }
 282       else if (s == str + 1)
 283         {
 284           /* The string became 1 digit shorter than its maximum.  */
 285           /* Need to copy it back one char pos.  */
 286           out_len--;
 287 #ifndef HAS_MEMMOVE
 288           {
 289             size_t i;
 290
 291             for (i = 0; i < out_len; i++)
 292               str[i] = s[i];
 293           }
 294 #else
 295           memmove (str, s, out_len);
 296 #endif
 297           str[out_len] = 0;
 298         }
 299       else
 300         {
 301           /* Hopefully never.  */
 302           abort ();
 303         }
 304     }
 305
 306   alloca (0);
 307   /* Ugly, we incremented str for negative numbers.  Fix that here.  */
 308   return str - (m->size < 0);
 309 }