lib/gmp/mpn/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 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 <config.h>
  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 mpn_get_str (str, base, mptr, msize)
  44      unsigned char *str;
  45      int base;
  46      mp_ptr mptr;
  47      mp_size_t msize;
  48 {
  49   mp_limb_t big_base;
  50 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
  51   int normalization_steps;
  52 #endif
  53 #if UDIV_TIME > 2 * UMUL_TIME
  54   mp_limb_t big_base_inverted;
  55 #endif
  56   unsigned int dig_per_u;
  57   mp_size_t out_len;
  58   register unsigned char *s;
  59
  60   big_base = __mp_bases[base].big_base;
  61
  62   s = str;
  63
  64   /* Special case zero, as the code below doesn't handle it.  */
  65   if (msize == 0)
  66     {
  67       s[0] = 0;
  68       return 1;
  69     }
  70
  71   if ((base & (base - 1)) == 0)
  72     {
  73       /* The base is a power of 2.  Make conversion from most
  74          significant side.  */
  75       mp_limb_t n1, n0;
  76       register int bits_per_digit = big_base;
  77       register int x;
  78       register int bit_pos;
  79       register int i;
  80
  81       n1 = mptr[msize - 1];
  82       count_leading_zeros (x, n1);
  83
  84         /* BIT_POS should be R when input ends in least sign. nibble,
  85            R + bits_per_digit * n when input ends in n:th least significant
  86            nibble. */
  87
  88       {
  89         int bits;
  90
  91         bits = BITS_PER_MP_LIMB * msize - x;
  92         x = bits % bits_per_digit;
  93         if (x != 0)
  94           bits += bits_per_digit - x;
  95         bit_pos = bits - (msize - 1) * BITS_PER_MP_LIMB;
  96       }
  97
  98       /* Fast loop for bit output.  */
  99       i = msize - 1;
 100       for (;;)
 101         {
 102           bit_pos -= bits_per_digit;
 103           while (bit_pos >= 0)
 104             {
 105               *s++ = (n1 >> bit_pos) & ((1 << bits_per_digit) - 1);
 106               bit_pos -= bits_per_digit;
 107             }
 108           i--;
 109           if (i < 0)
 110             break;
 111           n0 = (n1 << -bit_pos) & ((1 << bits_per_digit) - 1);
 112           n1 = mptr[i];
 113           bit_pos += BITS_PER_MP_LIMB;
 114           *s++ = n0 | (n1 >> bit_pos);
 115         }
 116
 117       *s = 0;
 118
 119       return s - str;
 120     }
 121   else
 122     {
 123       /* General case.  The base is not a power of 2.  Make conversion
 124          from least significant end.  */
 125
 126       /* If udiv_qrnnd only handles divisors with the most significant bit
 127          set, prepare BIG_BASE for being a divisor by shifting it to the
 128          left exactly enough to set the most significant bit.  */
 129 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
 130       count_leading_zeros (normalization_steps, big_base);
 131       big_base <<= normalization_steps;
 132 #if UDIV_TIME > 2 * UMUL_TIME
 133       /* Get the fixed-point approximation to 1/(BIG_BASE << NORMALIZATION_STEPS).  */
 134       big_base_inverted = __mp_bases[base].big_base_inverted;
 135 #endif
 136 #endif
 137
 138       dig_per_u = __mp_bases[base].chars_per_limb;
 139       out_len = ((size_t) msize * BITS_PER_MP_LIMB
 140                  * __mp_bases[base].chars_per_bit_exactly) + 1;
 141       s += out_len;
 142
 143       while (msize != 0)
 144         {
 145           int i;
 146           mp_limb_t n0, n1;
 147
 148 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
 149           /* If we shifted BIG_BASE above, shift the dividend too, to get
 150              the right quotient.  We need to do this every loop,
 151              since the intermediate quotients are OK, but the quotient from
 152              one turn in the loop is going to be the dividend in the
 153              next turn, and the dividend needs to be up-shifted.  */
 154           if (normalization_steps != 0)
 155             {
 156               n0 = mpn_lshift (mptr, mptr, msize, normalization_steps);
 157
 158               /* If the shifting gave a carry out limb, store it and
 159                  increase the length.  */
 160               if (n0 != 0)
 161                 {
 162                   mptr[msize] = n0;
 163                   msize++;
 164                 }
 165             }
 166 #endif
 167
 168           /* Divide the number at TP with BIG_BASE to get a quotient and a
 169              remainder.  The remainder is our new digit in base BIG_BASE.  */
 170           i = msize - 1;
 171           n1 = mptr[i];
 172
 173           if (n1 >= big_base)
 174             n1 = 0;
 175           else
 176             {
 177               msize--;
 178               i--;
 179             }
 180
 181           for (; i >= 0; i--)
 182             {
 183               n0 = mptr[i];
 184 #if UDIV_TIME > 2 * UMUL_TIME
 185               udiv_qrnnd_preinv (mptr[i], n1, n1, n0, big_base, big_base_inverted);
 186 #else
 187               udiv_qrnnd (mptr[i], n1, n1, n0, big_base);
 188 #endif
 189             }
 190
 191 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
 192           /* If we shifted above (at previous UDIV_NEEDS_NORMALIZATION tests)
 193              the remainder will be up-shifted here.  Compensate.  */
 194           n1 >>= normalization_steps;
 195 #endif
 196
 197           /* Convert N1 from BIG_BASE to a string of digits in BASE
 198              using single precision operations.  */
 199           for (i = dig_per_u - 1; i >= 0; i--)
 200             {
 201               *--s = n1 % base;
 202               n1 /= base;
 203               if (n1 == 0 && msize == 0)
 204                 break;
 205             }
 206         }
 207
 208       while (s != str)
 209         *--s = 0;
 210       return out_len;
 211     }
 212 }