home *** CD-ROM | disk | FTP | other *** search
/ InfoMagic Source Code 1993 July / THE_SOURCE_CODE_CD_ROM.iso / gnu / gmp-1.3.2 / _mpz_get_str.c next >
Encoding:
C/C++ Source or Header  |  1993-05-18  |  7.7 KB  |  310 lines
  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. }
  310.