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 MUTABLE
8   INTERFACES.  IT IS ONLY SAFE TO REACH THEM THROUGH DOCUMENTED INTERFACES.
9   IN FACT, IT IS ALMOST GUARANTEED THAT THEY WILL CHANGE OR DISAPPEAR IN A
10   FUTURE GNU MP RELEASE.
11
12Copyright 1991-2017 Free Software Foundation, Inc.
13
14This file is part of the GNU MP Library.
15
16The GNU MP Library is free software; you can redistribute it and/or modify
17it under the terms of either:
18
19  * the GNU Lesser General Public License as published by the Free
20    Software Foundation; either version 3 of the License, or (at your
21    option) any later version.
22
23or
24
25  * the GNU General Public License as published by the Free Software
26    Foundation; either version 2 of the License, or (at your option) any
27    later version.
28
29or both in parallel, as here.
30
31The GNU MP Library is distributed in the hope that it will be useful, but
32WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
33or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License
34for more details.
35
36You should have received copies of the GNU General Public License and the
37GNU Lesser General Public License along with the GNU MP Library.  If not,
38see https://www.gnu.org/licenses/.  */
39
40
41/* TODO:
42
43      Perhaps do not compute the highest power?
44      Instead, multiply twice by the 2nd highest power:
45
46	       _______
47	      |_______|  hp
48	      |_______|  pow
49       _______________
50      |_______________|  final result
51
52
53	       _______
54	      |_______|  hp
55		  |___|  pow[-1]
56	   ___________
57	  |___________|  intermediate result
58		  |___|  pow[-1]
59       _______________
60      |_______________|  final result
61
62      Generalizing that idea, perhaps we should make powtab contain successive
63      cubes, not squares.
64*/
65
66#include "gmp-impl.h"
67
68mp_size_t
69mpn_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
70{
71  if (POW2_P (base))
72    {
73      /* The base is a power of 2.  Read the input string from least to most
74	 significant character/digit.  */
75
76      const unsigned char *s;
77      int next_bitpos;
78      mp_limb_t res_digit;
79      mp_size_t size;
80      int bits_per_indigit = mp_bases[base].big_base;
81
82      size = 0;
83      res_digit = 0;
84      next_bitpos = 0;
85
86      for (s = str + str_len - 1; s >= str; s--)
87	{
88	  int inp_digit = *s;
89
90	  res_digit |= ((mp_limb_t) inp_digit << next_bitpos) & GMP_NUMB_MASK;
91	  next_bitpos += bits_per_indigit;
92	  if (next_bitpos >= GMP_NUMB_BITS)
93	    {
94	      rp[size++] = res_digit;
95	      next_bitpos -= GMP_NUMB_BITS;
96	      res_digit = inp_digit >> (bits_per_indigit - next_bitpos);
97	    }
98	}
99
100      if (res_digit != 0)
101	rp[size++] = res_digit;
102      return size;
103    }
104
105  if (BELOW_THRESHOLD (str_len, SET_STR_PRECOMPUTE_THRESHOLD))
106    return mpn_bc_set_str (rp, str, str_len, base);
107  else
108    {
109      mp_ptr powtab_mem, tp;
110      powers_t powtab[GMP_LIMB_BITS];
111      int chars_per_limb;
112      powers_t *pt;
113      size_t n_pows;
114      mp_size_t size;
115      mp_size_t un;
116      TMP_DECL;
117
118      TMP_MARK;
119
120      chars_per_limb = mp_bases[base].chars_per_limb;
121
122      un = str_len / chars_per_limb + 1; /* FIXME: scalar integer division */
123
124      /* Allocate one large block for the powers of big_base.  */
125      powtab_mem = TMP_BALLOC_LIMBS (mpn_str_powtab_alloc (un));
126
127      n_pows = mpn_compute_powtab (powtab, powtab_mem, un, base);
128      pt = powtab + n_pows;
129
130      tp = TMP_BALLOC_LIMBS (mpn_dc_set_str_itch (un));
131      size = mpn_dc_set_str (rp, str, str_len, pt, tp);
132
133      TMP_FREE;
134      return size;
135    }
136}
137
138mp_size_t
139mpn_dc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len,
140		const powers_t *powtab, mp_ptr tp)
141{
142  size_t len_lo, len_hi;
143  mp_limb_t cy;
144  mp_size_t ln, hn, n, sn;
145
146  len_lo = powtab->digits_in_base;
147
148  if (str_len <= len_lo)
149    {
150      if (BELOW_THRESHOLD (str_len, SET_STR_DC_THRESHOLD))
151	return mpn_bc_set_str (rp, str, str_len, powtab->base);
152      else
153	return mpn_dc_set_str (rp, str, str_len, powtab - 1, tp);
154    }
155
156  len_hi = str_len - len_lo;
157  ASSERT (len_lo >= len_hi);
158
159  if (BELOW_THRESHOLD (len_hi, SET_STR_DC_THRESHOLD))
160    hn = mpn_bc_set_str (tp, str, len_hi, powtab->base);
161  else
162    hn = mpn_dc_set_str (tp, str, len_hi, powtab - 1, rp);
163
164  sn = powtab->shift;
165
166  if (hn == 0)
167    {
168      /* Zero +1 limb here, to avoid reading an allocated but uninitialised
169	 limb in mpn_incr_u below.  */
170      MPN_ZERO (rp, powtab->n + sn + 1);
171    }
172  else
173    {
174      if (powtab->n > hn)
175	mpn_mul (rp + sn, powtab->p, powtab->n, tp, hn);
176      else
177	mpn_mul (rp + sn, tp, hn, powtab->p, powtab->n);
178      MPN_ZERO (rp, sn);
179    }
180
181  str = str + str_len - len_lo;
182  if (BELOW_THRESHOLD (len_lo, SET_STR_DC_THRESHOLD))
183    ln = mpn_bc_set_str (tp, str, len_lo, powtab->base);
184  else
185    ln = mpn_dc_set_str (tp, str, len_lo, powtab - 1, tp + powtab->n + sn + 1);
186
187  if (ln != 0)
188    {
189      cy = mpn_add_n (rp, rp, tp, ln);
190      mpn_incr_u (rp + ln, cy);
191    }
192  n = hn + powtab->n + sn;
193  return n - (rp[n - 1] == 0);
194}
195
196mp_size_t
197mpn_bc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
198{
199  mp_size_t size;
200  size_t i;
201  long j;
202  mp_limb_t cy_limb;
203
204  mp_limb_t big_base;
205  int chars_per_limb;
206  mp_limb_t res_digit;
207
208  ASSERT (base >= 2);
209  ASSERT (base < numberof (mp_bases));
210  ASSERT (str_len >= 1);
211
212  big_base = mp_bases[base].big_base;
213  chars_per_limb = mp_bases[base].chars_per_limb;
214
215  size = 0;
216  for (i = chars_per_limb; i < str_len; i += chars_per_limb)
217    {
218      res_digit = *str++;
219      if (base == 10)
220	{ /* This is a common case.
221	     Help the compiler to avoid multiplication.  */
222	  for (j = MP_BASES_CHARS_PER_LIMB_10 - 1; j != 0; j--)
223	    res_digit = res_digit * 10 + *str++;
224	}
225      else
226	{
227	  for (j = chars_per_limb - 1; j != 0; j--)
228	    res_digit = res_digit * base + *str++;
229	}
230
231      if (size == 0)
232	{
233	  if (res_digit != 0)
234	    {
235	      rp[0] = res_digit;
236	      size = 1;
237	    }
238	}
239      else
240	{
241#if HAVE_NATIVE_mpn_mul_1c
242	  cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
243#else
244	  cy_limb = mpn_mul_1 (rp, rp, size, big_base);
245	  cy_limb += mpn_add_1 (rp, rp, size, res_digit);
246#endif
247	  if (cy_limb != 0)
248	    rp[size++] = cy_limb;
249	}
250    }
251
252  big_base = base;
253  res_digit = *str++;
254  if (base == 10)
255    { /* This is a common case.
256	 Help the compiler to avoid multiplication.  */
257      for (j = str_len - (i - MP_BASES_CHARS_PER_LIMB_10) - 1; j > 0; j--)
258	{
259	  res_digit = res_digit * 10 + *str++;
260	  big_base *= 10;
261	}
262    }
263  else
264    {
265      for (j = str_len - (i - chars_per_limb) - 1; j > 0; j--)
266	{
267	  res_digit = res_digit * base + *str++;
268	  big_base *= base;
269	}
270    }
271
272  if (size == 0)
273    {
274      if (res_digit != 0)
275	{
276	  rp[0] = res_digit;
277	  size = 1;
278	}
279    }
280  else
281    {
282#if HAVE_NATIVE_mpn_mul_1c
283      cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
284#else
285      cy_limb = mpn_mul_1 (rp, rp, size, big_base);
286      cy_limb += mpn_add_1 (rp, rp, size, res_digit);
287#endif
288      if (cy_limb != 0)
289	rp[size++] = cy_limb;
290    }
291  return size;
292}
293