rts/gmp/mpn/generic/get_str.c

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