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
12Copyright 1991, 1992, 1993, 1994, 1996, 2000, 2001, 2002, 2004, 2006, 2007,
132008 Free Software Foundation, Inc.
14
15This file is part of the GNU MP Library.
16
17The GNU MP Library is free software; you can redistribute it and/or modify
18it under the terms of the GNU Lesser General Public License as published by
19the Free Software Foundation; either version 3 of the License, or (at your
20option) any later version.
21
22The GNU MP Library is distributed in the hope that it will be useful, but
23WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
24or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU Lesser General Public
25License for more details.
26
27You should have received a copy of the GNU Lesser General Public License
28along 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
60mp_size_t
61mpn_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
127void
128mpn_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
212mp_size_t
213mpn_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
268mp_size_t
269mpn_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}
365