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
mpn_set_str(mp_ptr rp,const unsigned char * str,size_t str_len,int base)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
mpn_set_str_compute_powtab(powers_t * powtab,mp_ptr powtab_mem,mp_size_t un,int base)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
mpn_dc_set_str(mp_ptr rp,const unsigned char * str,size_t str_len,const powers_t * powtab,mp_ptr tp)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
mpn_bc_set_str(mp_ptr rp,const unsigned char * str,size_t str_len,int base)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 }
365