home *** CD-ROM | disk | FTP | other *** search
/ OS/2 Shareware BBS: 22 gnu / 22-gnu.zip / gmp202.zip / mpn / generic / get_str.c < prev    next >
C/C++ Source or Header  |  1996-05-08  |  6KB  |  212 lines
  1. /* mpn_get_str -- Convert a MSIZE long limb vector pointed to by MPTR
  2.    to a printable string in STR in base BASE.
  3.  
  4. Copyright (C) 1991, 1992, 1993, 1994, 1996 Free Software Foundation, Inc.
  5.  
  6. This file is part of the GNU MP Library.
  7.  
  8. The GNU MP Library is free software; you can redistribute it and/or modify
  9. it under the terms of the GNU Library General Public License as published by
  10. the Free Software Foundation; either version 2 of the License, or (at your
  11. option) any later version.
  12.  
  13. The GNU MP Library is distributed in the hope that it will be useful, but
  14. WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  15. or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Library General Public
  16. License for more details.
  17.  
  18. You should have received a copy of the GNU Library General Public License
  19. along with the GNU MP Library; see the file COPYING.LIB.  If not, write to
  20. the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
  21. MA 02111-1307, USA. */
  22.  
  23. #include "gmp.h"
  24. #include "gmp-impl.h"
  25. #include "longlong.h"
  26.  
  27. /* Convert the limb vector pointed to by MPTR and MSIZE long to a
  28.    char array, using base BASE for the result array.  Store the
  29.    result in the character array STR.  STR must point to an array with
  30.    space for the largest possible number represented by a MSIZE long
  31.    limb vector + 1 extra character.
  32.  
  33.    The result is NOT in Ascii, to convert it to printable format, add
  34.    '0' or 'A' depending on the base and range.
  35.  
  36.    Return the number of digits in the result string.
  37.    This may include some leading zeros.
  38.  
  39.    The limb vector pointed to by MPTR is clobbered.  */
  40.  
  41. size_t
  42. mpn_get_str (str, base, mptr, msize)
  43.      unsigned char *str;
  44.      int base;
  45.      mp_ptr mptr;
  46.      mp_size_t msize;
  47. {
  48.   mp_limb_t big_base;
  49. #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
  50.   int normalization_steps;
  51. #endif
  52. #if UDIV_TIME > 2 * UMUL_TIME
  53.   mp_limb_t big_base_inverted;
  54. #endif
  55.   unsigned int dig_per_u;
  56.   mp_size_t out_len;
  57.   register unsigned char *s;
  58.  
  59.   big_base = __mp_bases[base].big_base;
  60.  
  61.   s = str;
  62.  
  63.   /* Special case zero, as the code below doesn't handle it.  */
  64.   if (msize == 0)
  65.     {
  66.       s[0] = 0;
  67.       return 1;
  68.     }
  69.  
  70.   if ((base & (base - 1)) == 0)
  71.     {
  72.       /* The base is a power of 2.  Make conversion from most
  73.      significant side.  */
  74.       mp_limb_t n1, n0;
  75.       register int bits_per_digit = big_base;
  76.       register int x;
  77.       register int bit_pos;
  78.       register int i;
  79.  
  80.       n1 = mptr[msize - 1];
  81.       count_leading_zeros (x, n1);
  82.  
  83.     /* BIT_POS should be R when input ends in least sign. nibble,
  84.        R + bits_per_digit * n when input ends in n:th least significant
  85.        nibble. */
  86.  
  87.       {
  88.     int bits;
  89.  
  90.     bits = BITS_PER_MP_LIMB * msize - x;
  91.     x = bits % bits_per_digit;
  92.     if (x != 0)
  93.       bits += bits_per_digit - x;
  94.     bit_pos = bits - (msize - 1) * BITS_PER_MP_LIMB;
  95.       }
  96.  
  97.       /* Fast loop for bit output.  */
  98.       i = msize - 1;
  99.       for (;;)
  100.     {
  101.       bit_pos -= bits_per_digit;
  102.       while (bit_pos >= 0)
  103.         {
  104.           *s++ = (n1 >> bit_pos) & ((1 << bits_per_digit) - 1);
  105.           bit_pos -= bits_per_digit;
  106.         }
  107.       i--;
  108.       if (i < 0)
  109.         break;
  110.       n0 = (n1 << -bit_pos) & ((1 << bits_per_digit) - 1);
  111.       n1 = mptr[i];
  112.       bit_pos += BITS_PER_MP_LIMB;
  113.       *s++ = n0 | (n1 >> bit_pos);
  114.     }
  115.  
  116.       *s = 0;
  117.  
  118.       return s - str;
  119.     }
  120.   else
  121.     {
  122.       /* General case.  The base is not a power of 2.  Make conversion
  123.      from least significant end.  */
  124.  
  125.       /* If udiv_qrnnd only handles divisors with the most significant bit
  126.      set, prepare BIG_BASE for being a divisor by shifting it to the
  127.      left exactly enough to set the most significant bit.  */
  128. #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
  129.       count_leading_zeros (normalization_steps, big_base);
  130.       big_base <<= normalization_steps;
  131. #if UDIV_TIME > 2 * UMUL_TIME
  132.       /* Get the fixed-point approximation to 1/(BIG_BASE << NORMALIZATION_STEPS).  */
  133.       big_base_inverted = __mp_bases[base].big_base_inverted;
  134. #endif
  135. #endif
  136.  
  137.       dig_per_u = __mp_bases[base].chars_per_limb;
  138.       out_len = ((size_t) msize * BITS_PER_MP_LIMB
  139.          * __mp_bases[base].chars_per_bit_exactly) + 1;
  140.       s += out_len;
  141.  
  142.       while (msize != 0)
  143.     {
  144.       int i;
  145.       mp_limb_t n0, n1;
  146.  
  147. #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
  148.       /* If we shifted BIG_BASE above, shift the dividend too, to get
  149.          the right quotient.  We need to do this every loop,
  150.          since the intermediate quotients are OK, but the quotient from
  151.          one turn in the loop is going to be the dividend in the
  152.          next turn, and the dividend needs to be up-shifted.  */
  153.       if (normalization_steps != 0)
  154.         {
  155.           n0 = mpn_lshift (mptr, mptr, msize, normalization_steps);
  156.  
  157.           /* If the shifting gave a carry out limb, store it and
  158.          increase the length.  */
  159.           if (n0 != 0)
  160.         {
  161.           mptr[msize] = n0;
  162.           msize++;
  163.         }
  164.         }
  165. #endif
  166.  
  167.       /* Divide the number at TP with BIG_BASE to get a quotient and a
  168.          remainder.  The remainder is our new digit in base BIG_BASE.  */
  169.       i = msize - 1;
  170.       n1 = mptr[i];
  171.  
  172.       if (n1 >= big_base)
  173.         n1 = 0;
  174.       else
  175.         {
  176.           msize--;
  177.           i--;
  178.         }
  179.  
  180.       for (; i >= 0; i--)
  181.         {
  182.           n0 = mptr[i];
  183. #if UDIV_TIME > 2 * UMUL_TIME
  184.           udiv_qrnnd_preinv (mptr[i], n1, n1, n0, big_base, big_base_inverted);
  185. #else
  186.           udiv_qrnnd (mptr[i], n1, n1, n0, big_base);
  187. #endif
  188.         }
  189.  
  190. #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
  191.       /* If we shifted above (at previous UDIV_NEEDS_NORMALIZATION tests)
  192.          the remainder will be up-shifted here.  Compensate.  */
  193.       n1 >>= normalization_steps;
  194. #endif
  195.  
  196.       /* Convert N1 from BIG_BASE to a string of digits in BASE
  197.          using single precision operations.  */
  198.       for (i = dig_per_u - 1; i >= 0; i--)
  199.         {
  200.           *--s = n1 % base;
  201.           n1 /= base;
  202.           if (n1 == 0 && msize == 0)
  203.         break;
  204.         }
  205.     }
  206.  
  207.       while (s != str)
  208.     *--s = 0;
  209.       return out_len;
  210.     }
  211. }
  212.