mpn/generic/set_str.c

   1 /* mpn_set_str (mp_ptr res_ptr, const char *str, size_t str_len, int base) --
   2    Convert a STR_LEN long base BASE byte string pointed to by STR to a limb
   3    vector pointed to by RES_PTR.  Return the number of limbs in RES_PTR.
   4
   5    Contributed to the GNU project by Torbjorn Granlund.
   6
   7    THE FUNCTIONS IN THIS FILE, EXCEPT mpn_set_str, ARE INTERNAL WITH A MUTABLE
   8    INTERFACE.  IT IS ONLY SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.  IN
   9    FACT, IT IS ALMOST GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A FUTURE
  10    GNU MP RELEASE.
  11
  12 Copyright 1991, 1992, 1993, 1994, 1996, 2000, 2001, 2002, 2004, 2006, 2007,
  13 2008 Free Software Foundation, Inc.
  14
  15 This file is part of the GNU MP Library.
  16
  17 The GNU MP Library is free software; you can redistribute it and/or modify
  18 it under the terms of the GNU Lesser General Public License as published by
  19 the Free Software Foundation; either version 3 of the License, or (at your
  20 option) any later version.
  21
  22 The GNU MP Library is distributed in the hope that it will be useful, but
  23 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  24 or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
  25 License for more details.
  26
  27 You should have received a copy of the GNU Lesser General Public License
  28 along with the GNU MP Library.  If not, see http://www.gnu.org/licenses/.  */
  29
  30
  31 /* TODO:
  32
  33       Perhaps do not compute the highest power?
  34       Instead, multiply twice by the 2nd highest power:
  35
  36                _______
  37               |_______|  hp
  38               |_______|  pow
  39        _______________
  40       |_______________|  final result
  41
  42
  43                _______
  44               |_______|  hp
  45                   |___|  pow[-1]
  46            ___________
  47           |___________|  intermediate result
  48                   |___|  pow[-1]
  49        _______________
  50       |_______________|  final result
  51
  52       Generalizing that idea, perhaps we should make powtab contain successive
  53       cubes, not squares.
  54 */
  55
  56 #include "gmp.h"
  57 #include "gmp-impl.h"
  58 #include "longlong.h"
  59
  60 mp_size_t
  61 mpn_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
  62 {
  63   if (POW2_P (base))
  64     {
  65       /* The base is a power of 2.  Read the input string from least to most
  66          significant character/digit.  */
  67
  68       const unsigned char *s;
  69       int next_bitpos;
  70       mp_limb_t res_digit;
  71       mp_size_t size;
  72       int bits_per_indigit = mp_bases[base].big_base;
  73
  74       size = 0;
  75       res_digit = 0;
  76       next_bitpos = 0;
  77
  78       for (s = str + str_len - 1; s >= str; s--)
  79         {
  80           int inp_digit = *s;
  81
  82           res_digit |= ((mp_limb_t) inp_digit << next_bitpos) & GMP_NUMB_MASK;
  83           next_bitpos += bits_per_indigit;
  84           if (next_bitpos >= GMP_NUMB_BITS)
  85             {
  86               rp[size++] = res_digit;
  87               next_bitpos -= GMP_NUMB_BITS;
  88               res_digit = inp_digit >> (bits_per_indigit - next_bitpos);
  89             }
  90         }
  91
  92       if (res_digit != 0)
  93         rp[size++] = res_digit;
  94       return size;
  95     }
  96
  97   if (BELOW_THRESHOLD (str_len, SET_STR_PRECOMPUTE_THRESHOLD))
  98     return mpn_bc_set_str (rp, str, str_len, base);
  99   else
 100     {
 101       mp_ptr powtab_mem, tp;
 102       powers_t powtab[GMP_LIMB_BITS];
 103       int chars_per_limb;
 104       mp_size_t size;
 105       mp_size_t un;
 106       TMP_DECL;
 107
 108       TMP_MARK;
 109
 110       chars_per_limb = mp_bases[base].chars_per_limb;
 111
 112       un = str_len / chars_per_limb + 1;
 113
 114       /* Allocate one large block for the powers of big_base.  */
 115       powtab_mem = TMP_BALLOC_LIMBS (mpn_dc_set_str_powtab_alloc (un));
 116
 117       mpn_set_str_compute_powtab (powtab, powtab_mem, un, base);
 118
 119       tp = TMP_BALLOC_LIMBS (mpn_dc_set_str_itch (un));
 120       size = mpn_dc_set_str (rp, str, str_len, powtab, tp);
 121
 122       TMP_FREE;
 123       return size;
 124     }
 125 }
 126
 127 void
 128 mpn_set_str_compute_powtab (powers_t *powtab, mp_ptr powtab_mem, mp_size_t un, int base)
 129 {
 130   mp_ptr powtab_mem_ptr;
 131   long i, pi;
 132   mp_size_t n;
 133   mp_ptr p, t;
 134   unsigned normalization_steps;
 135   mp_limb_t big_base, big_base_inverted;
 136   int chars_per_limb;
 137   size_t digits_in_base;
 138   mp_size_t shift;
 139
 140   powtab_mem_ptr = powtab_mem;
 141
 142   chars_per_limb = mp_bases[base].chars_per_limb;
 143   big_base = mp_bases[base].big_base;
 144   big_base_inverted = mp_bases[base].big_base_inverted;
 145   count_leading_zeros (normalization_steps, big_base);
 146
 147   p = powtab_mem_ptr;
 148   powtab_mem_ptr += 1;
 149
 150   digits_in_base = chars_per_limb;
 151
 152   p[0] = big_base;
 153   n = 1;
 154
 155   count_leading_zeros (i, un - 1);
 156   i = GMP_LIMB_BITS - 1 - i;
 157
 158   powtab[i].p = p;
 159   powtab[i].n = n;
 160   powtab[i].digits_in_base = digits_in_base;
 161   powtab[i].base = base;
 162   powtab[i].shift = 0;
 163
 164   shift = 0;
 165   for (pi = i - 1; pi >= 0; pi--)
 166     {
 167       t = powtab_mem_ptr;
 168       powtab_mem_ptr += 2 * n;
 169
 170       ASSERT_ALWAYS (powtab_mem_ptr < powtab_mem + mpn_dc_set_str_powtab_alloc (un));
 171
 172       mpn_sqr (t, p, n);
 173       n = 2 * n - 1; n += t[n] != 0;
 174       digits_in_base *= 2;
 175 #if 1
 176       if ((((un - 1) >> pi) & 2) == 0)
 177         {
 178           mpn_divexact_1 (t, t, n, big_base);
 179           n -= t[n - 1] == 0;
 180           digits_in_base -= chars_per_limb;
 181         }
 182 #else
 183       if (CLEVER_CONDITION_1 ())
 184         {
 185           /* perform adjustment operation of previous */
 186           cy = mpn_mul_1 (p, p, n, big_base);
 187         }
 188       if (CLEVER_CONDITION_2 ())
 189         {
 190           /* perform adjustment operation of new */
 191           cy = mpn_mul_1 (t, t, n, big_base);
 192         }
 193 #endif
 194       shift *= 2;
 195       /* Strip low zero limbs, but be careful to keep the result divisible by
 196          big_base.  */
 197       while (t[0] == 0 && (t[1] & ((big_base & -big_base) - 1)) == 0)
 198         {
 199           t++;
 200           n--;
 201           shift++;
 202         }
 203       p = t;
 204       powtab[pi].p = p;
 205       powtab[pi].n = n;
 206       powtab[pi].digits_in_base = digits_in_base;
 207       powtab[pi].base = base;
 208       powtab[pi].shift = shift;
 209     }
 210 }
 211
 212 mp_size_t
 213 mpn_dc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len,
 214                 const powers_t *powtab, mp_ptr tp)
 215 {
 216   size_t len_lo, len_hi;
 217   mp_limb_t cy;
 218   mp_size_t ln, hn, n, sn;
 219
 220   len_lo = powtab->digits_in_base;
 221
 222   if (str_len <= len_lo)
 223     {
 224       if (BELOW_THRESHOLD (str_len, SET_STR_DC_THRESHOLD))
 225         return mpn_bc_set_str (rp, str, str_len, powtab->base);
 226       else
 227         return mpn_dc_set_str (rp, str, str_len, powtab + 1, tp);
 228     }
 229
 230   len_hi = str_len - len_lo;
 231   ASSERT (len_lo >= len_hi);
 232
 233   if (BELOW_THRESHOLD (len_hi, SET_STR_DC_THRESHOLD))
 234     hn = mpn_bc_set_str (tp, str, len_hi, powtab->base);
 235   else
 236     hn = mpn_dc_set_str (tp, str, len_hi, powtab + 1, rp);
 237
 238   sn = powtab->shift;
 239
 240   if (hn == 0)
 241     {
 242       MPN_ZERO (rp, powtab->n + sn);
 243     }
 244   else
 245     {
 246       if (powtab->n > hn)
 247         mpn_mul (rp + sn, powtab->p, powtab->n, tp, hn);
 248       else
 249         mpn_mul (rp + sn, tp, hn, powtab->p, powtab->n);
 250       MPN_ZERO (rp, sn);
 251     }
 252
 253   str = str + str_len - len_lo;
 254   if (BELOW_THRESHOLD (len_lo, SET_STR_DC_THRESHOLD))
 255     ln = mpn_bc_set_str (tp, str, len_lo, powtab->base);
 256   else
 257     ln = mpn_dc_set_str (tp, str, len_lo, powtab + 1, tp + powtab->n + sn + 1);
 258
 259   if (ln != 0)
 260     {
 261       cy = mpn_add_n (rp, rp, tp, ln);
 262       mpn_incr_u (rp + ln, cy);
 263     }
 264   n = hn + powtab->n + sn;
 265   return n - (rp[n - 1] == 0);
 266 }
 267
 268 mp_size_t
 269 mpn_bc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
 270 {
 271   mp_size_t size;
 272   size_t i;
 273   long j;
 274   mp_limb_t cy_limb;
 275
 276   mp_limb_t big_base;
 277   int chars_per_limb;
 278   mp_limb_t res_digit;
 279
 280   ASSERT (base >= 2);
 281   ASSERT (base < numberof (mp_bases));
 282   ASSERT (str_len >= 1);
 283
 284   big_base = mp_bases[base].big_base;
 285   chars_per_limb = mp_bases[base].chars_per_limb;
 286
 287   size = 0;
 288   for (i = chars_per_limb; i < str_len; i += chars_per_limb)
 289     {
 290       res_digit = *str++;
 291       if (base == 10)
 292         { /* This is a common case.
 293              Help the compiler to avoid multiplication.  */
 294           for (j = MP_BASES_CHARS_PER_LIMB_10 - 1; j != 0; j--)
 295             res_digit = res_digit * 10 + *str++;
 296         }
 297       else
 298         {
 299           for (j = chars_per_limb - 1; j != 0; j--)
 300             res_digit = res_digit * base + *str++;
 301         }
 302
 303       if (size == 0)
 304         {
 305           if (res_digit != 0)
 306             {
 307               rp[0] = res_digit;
 308               size = 1;
 309             }
 310         }
 311       else
 312         {
 313 #if HAVE_NATIVE_mpn_mul_1c
 314           cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
 315 #else
 316           cy_limb = mpn_mul_1 (rp, rp, size, big_base);
 317           cy_limb += mpn_add_1 (rp, rp, size, res_digit);
 318 #endif
 319           if (cy_limb != 0)
 320             rp[size++] = cy_limb;
 321         }
 322     }
 323
 324   big_base = base;
 325   res_digit = *str++;
 326   if (base == 10)
 327     { /* This is a common case.
 328          Help the compiler to avoid multiplication.  */
 329       for (j = str_len - (i - MP_BASES_CHARS_PER_LIMB_10) - 1; j > 0; j--)
 330         {
 331           res_digit = res_digit * 10 + *str++;
 332           big_base *= 10;
 333         }
 334     }
 335   else
 336     {
 337       for (j = str_len - (i - chars_per_limb) - 1; j > 0; j--)
 338         {
 339           res_digit = res_digit * base + *str++;
 340           big_base *= base;
 341         }
 342     }
 343
 344   if (size == 0)
 345     {
 346       if (res_digit != 0)
 347         {
 348           rp[0] = res_digit;
 349           size = 1;
 350         }
 351     }
 352   else
 353     {
 354 #if HAVE_NATIVE_mpn_mul_1c
 355       cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
 356 #else
 357       cy_limb = mpn_mul_1 (rp, rp, size, big_base);
 358       cy_limb += mpn_add_1 (rp, rp, size, res_digit);
 359 #endif
 360       if (cy_limb != 0)
 361         rp[size++] = cy_limb;
 362     }
 363   return size;
 364 }