ghc/runtime/gmp/_mpz_set_str.c

   1 /* _mpz_set_str(mp_dest, string, base) -- Convert the \0-terminated
   2    string STRING in base BASE to multiple precision integer in
   3    MP_DEST.  Allow white space in the string.  If BASE == 0 determine
   4    the base in the C standard way, i.e.  0xhh...h means base 16,
   5    0oo...o means base 8, otherwise assume base 10.
   6
   7 Copyright (C) 1991 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 enum char_type
  30 {
  31   XX = -3,
  32   SPC = -2,
  33   EOF = -1
  34 };
  35
  36 static signed char ascii_to_num[256] =
  37 {
  38   EOF,XX, XX, XX, XX, XX, XX, XX, XX, SPC,SPC,XX, XX, XX, XX, XX,
  39   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  40   SPC,XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  41   0,  1,  2,  3,  4,  5,  6,  7,  8,  9,  XX, XX, XX, XX, XX, XX,
  42   XX, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
  43   25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, XX, XX, XX, XX, XX,
  44   XX, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24,
  45   25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, XX, XX, XX, XX, XX,
  46   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  47   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  48   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  49   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  50   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  51   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  52   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX,
  53   XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX, XX
  54 };
  55
  56 int
  57 #ifdef __STDC__
  58 _mpz_set_str (MP_INT *x, const char *str, int base)
  59 #else
  60 _mpz_set_str (x, str, base)
  61      MP_INT *x;
  62      const char *str;
  63      int base;
  64 #endif
  65 {
  66   mp_ptr xp;
  67   mp_size size;
  68   mp_limb big_base;
  69   int indigits_per_limb;
  70   int negative = 0;
  71   int inp_rawchar;
  72   mp_limb inp_digit;
  73   mp_limb res_digit;
  74   size_t str_len;
  75   mp_size i;
  76
  77   if (str[0] == '-')
  78     {
  79       negative = 1;
  80       str++;
  81     }
  82
  83   if (base == 0)
  84     {
  85       if (str[0] == '0')
  86         {
  87           if (str[1] == 'x' || str[1] == 'X')
  88             base = 16;
  89           else
  90             base = 8;
  91         }
  92       else
  93         base = 10;
  94     }
  95
  96   big_base = __mp_bases[base].big_base;
  97   indigits_per_limb = __mp_bases[base].chars_per_limb;
  98
  99   str_len = strlen (str);
 100
 101   size = str_len / indigits_per_limb + 1;
 102   if (x->alloc < size)
 103     _mpz_realloc (x, size);
 104   xp = x->d;
 105
 106   size = 0;
 107
 108   if ((base & (base - 1)) == 0)
 109     {
 110       /* The base is a power of 2.  Read the input string from
 111          least to most significant character/digit.  */
 112
 113       const char *s;
 114       int next_bitpos;
 115       int bits_per_indigit = big_base;
 116
 117       /* Accept and ignore 0x or 0X before hexadecimal numbers.  */
 118       if (base == 16 && str[0] == '0' && (str[1] == 'x' || str[1] == 'X'))
 119         {
 120           str += 2;
 121           str_len -= 2;
 122         }
 123
 124       res_digit = 0;
 125       next_bitpos = 0;
 126
 127       for (s = str + str_len - 1; s >= str; s--)
 128         {
 129           inp_rawchar = *s;
 130           inp_digit = ascii_to_num[inp_rawchar];
 131
 132           if (inp_digit >= base)
 133             {
 134               /* Was it white space?  Just ignore it.  */
 135               if ((char) inp_digit == (char) SPC)
 136                 continue;
 137
 138               /* We found rubbish in the string.  Return -1 to indicate
 139                  the error.  */
 140               return -1;
 141             }
 142
 143           res_digit |= inp_digit << next_bitpos;
 144           next_bitpos += bits_per_indigit;
 145           if (next_bitpos >= BITS_PER_MP_LIMB)
 146             {
 147               xp[size] = res_digit;
 148               size++;
 149               next_bitpos -= BITS_PER_MP_LIMB;
 150               res_digit = inp_digit >> (bits_per_indigit - next_bitpos);
 151             }
 152         }
 153
 154       xp[size] = res_digit;
 155       size++;
 156       for (i = size - 1; i >= 0; i--)
 157         {
 158           if (xp[i] != 0)
 159             break;
 160         }
 161       size = i + 1;
 162     }
 163   else
 164     {
 165       /* General case.  The base is not a power of 2.  */
 166
 167       mp_size i;
 168       int j;
 169       mp_limb cy;
 170
 171       for (;;)
 172         {
 173           res_digit = 0;
 174           for (j = 0; j < indigits_per_limb; )
 175             {
 176               inp_rawchar = (unsigned char) *str++;
 177               inp_digit = ascii_to_num[inp_rawchar];
 178
 179               /* Negative means that the character was not a proper digit.  */
 180               if (inp_digit >= base)
 181                 {
 182                   /* Was it white space?  Just ignore it.  */
 183                   if ((char) inp_digit == (char) SPC)
 184                     continue;
 185
 186                   goto end_or_error;
 187                 }
 188
 189               res_digit = res_digit * base + inp_digit;
 190
 191               /* Increment the loop counter here, since it mustn't be
 192                  incremented when we do "continue" above.  */
 193               j++;
 194             }
 195
 196           cy = res_digit;
 197
 198           /* Insert RES_DIGIT into the result multi prec integer.  */
 199           for (i = 0; i < size; i++)
 200             {
 201               mp_limb p1, p0;
 202               umul_ppmm (p1, p0, big_base, xp[i]);
 203               p0 += cy;
 204               cy = p1 + (p0 < cy);
 205               xp[i] = p0;
 206             }
 207           if (cy != 0)
 208             {
 209               xp[size] = cy;
 210               size++;
 211             }
 212         }
 213
 214     end_or_error:
 215       /* We probably have some digits in RES_DIGIT  (J tells how many).  */
 216       if ((char) inp_digit != (char) EOF)
 217         {
 218           /* Error return.  */
 219           return -1;
 220         }
 221
 222       /* J contains number of digits (in base BASE) remaining in
 223          RES_DIGIT.  */
 224       if (j > 0)
 225         {
 226           big_base = 1;
 227           do
 228             {
 229               big_base *= base;
 230               j--;
 231             }
 232           while (j > 0);
 233
 234           cy = res_digit;
 235
 236           /* Insert ultimate RES_DIGIT into the result multi prec integer.  */
 237           for (i = 0; i < size; i++)
 238             {
 239               mp_limb p1, p0;
 240               umul_ppmm (p1, p0, big_base, xp[i]);
 241               p0 += cy;
 242               cy = p1 + (p0 < cy);
 243               xp[i] = p0;
 244             }
 245           if (cy != 0)
 246             {
 247               xp[size] = cy;
 248               size++;
 249             }
 250         }
 251     }
 252
 253   if (negative)
 254     size = -size;
 255   x->size = size;
 256
 257   return 0;
 258 }