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
12 Copyright 1991-2017 Free Software Foundation, Inc.
13
14 This file is part of the GNU MP Library.
15
16 The GNU MP Library is free software; you can redistribute it and/or modify
17 it 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
23 or
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
29 or both in parallel, as here.
30
31 The GNU MP Library is distributed in the hope that it will be useful, but
32 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
33 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
34 for more details.
35
36 You should have received copies of the GNU General Public License and the
37 GNU Lesser General Public License along with the GNU MP Library. If not,
38 see 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
68 mp_size_t
mpn_set_str(mp_ptr rp,const unsigned char * str,size_t str_len,int base)69 mpn_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
138 mp_size_t
mpn_dc_set_str(mp_ptr rp,const unsigned char * str,size_t str_len,const powers_t * powtab,mp_ptr tp)139 mpn_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
196 mp_size_t
mpn_bc_set_str(mp_ptr rp,const unsigned char * str,size_t str_len,int base)197 mpn_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