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