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
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 mp_size_t size;
113 mp_size_t un;
114 TMP_DECL;
115
116 TMP_MARK;
117
118 chars_per_limb = mp_bases[base].chars_per_limb;
119
120 un = str_len / chars_per_limb + 1; /* FIXME: scalar integer division */
121
122 /* Allocate one large block for the powers of big_base. */
123 powtab_mem = TMP_BALLOC_LIMBS (mpn_str_powtab_alloc (un));
124
125 size_t n_pows = mpn_compute_powtab (powtab, powtab_mem, un, base);
126 powers_t *pt = powtab + n_pows;
127
128 tp = TMP_BALLOC_LIMBS (mpn_dc_set_str_itch (un));
129 size = mpn_dc_set_str (rp, str, str_len, pt, tp);
130
131 TMP_FREE;
132 return size;
133 }
134 }
135
136 mp_size_t
137 mpn_dc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len,
138 const powers_t *powtab, mp_ptr tp)
139 {
140 size_t len_lo, len_hi;
141 mp_limb_t cy;
142 mp_size_t ln, hn, n, sn;
143
144 len_lo = powtab->digits_in_base;
145
146 if (str_len <= len_lo)
147 {
148 if (BELOW_THRESHOLD (str_len, SET_STR_DC_THRESHOLD))
149 return mpn_bc_set_str (rp, str, str_len, powtab->base);
150 else
151 return mpn_dc_set_str (rp, str, str_len, powtab - 1, tp);
152 }
153
154 len_hi = str_len - len_lo;
155 ASSERT (len_lo >= len_hi);
156
157 if (BELOW_THRESHOLD (len_hi, SET_STR_DC_THRESHOLD))
158 hn = mpn_bc_set_str (tp, str, len_hi, powtab->base);
159 else
160 hn = mpn_dc_set_str (tp, str, len_hi, powtab - 1, rp);
161
162 sn = powtab->shift;
163
164 if (hn == 0)
165 {
166 /* Zero +1 limb here, to avoid reading an allocated but uninitialised
167 limb in mpn_incr_u below. */
168 MPN_ZERO (rp, powtab->n + sn + 1);
169 }
170 else
171 {
172 if (powtab->n > hn)
173 mpn_mul (rp + sn, powtab->p, powtab->n, tp, hn);
174 else
175 mpn_mul (rp + sn, tp, hn, powtab->p, powtab->n);
176 MPN_ZERO (rp, sn);
177 }
178
179 str = str + str_len - len_lo;
180 if (BELOW_THRESHOLD (len_lo, SET_STR_DC_THRESHOLD))
181 ln = mpn_bc_set_str (tp, str, len_lo, powtab->base);
182 else
183 ln = mpn_dc_set_str (tp, str, len_lo, powtab - 1, tp + powtab->n + sn + 1);
184
185 if (ln != 0)
186 {
187 cy = mpn_add_n (rp, rp, tp, ln);
188 mpn_incr_u (rp + ln, cy);
189 }
190 n = hn + powtab->n + sn;
191 return n - (rp[n - 1] == 0);
192 }
193
194 mp_size_t
195 mpn_bc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
196 {
197 mp_size_t size;
198 size_t i;
199 long j;
200 mp_limb_t cy_limb;
201
202 mp_limb_t big_base;
203 int chars_per_limb;
204 mp_limb_t res_digit;
205
206 ASSERT (base >= 2);
207 ASSERT (base < numberof (mp_bases));
208 ASSERT (str_len >= 1);
209
210 big_base = mp_bases[base].big_base;
211 chars_per_limb = mp_bases[base].chars_per_limb;
212
213 size = 0;
214 for (i = chars_per_limb; i < str_len; i += chars_per_limb)
215 {
216 res_digit = *str++;
217 if (base == 10)
218 { /* This is a common case.
219 Help the compiler to avoid multiplication. */
220 for (j = MP_BASES_CHARS_PER_LIMB_10 - 1; j != 0; j--)
221 res_digit = res_digit * 10 + *str++;
222 }
223 else
224 {
225 for (j = chars_per_limb - 1; j != 0; j--)
226 res_digit = res_digit * base + *str++;
227 }
228
229 if (size == 0)
230 {
231 if (res_digit != 0)
232 {
233 rp[0] = res_digit;
234 size = 1;
235 }
236 }
237 else
238 {
239 #if HAVE_NATIVE_mpn_mul_1c
240 cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
241 #else
242 cy_limb = mpn_mul_1 (rp, rp, size, big_base);
243 cy_limb += mpn_add_1 (rp, rp, size, res_digit);
244 #endif
245 if (cy_limb != 0)
246 rp[size++] = cy_limb;
247 }
248 }
249
250 big_base = base;
251 res_digit = *str++;
252 if (base == 10)
253 { /* This is a common case.
254 Help the compiler to avoid multiplication. */
255 for (j = str_len - (i - MP_BASES_CHARS_PER_LIMB_10) - 1; j > 0; j--)
256 {
257 res_digit = res_digit * 10 + *str++;
258 big_base *= 10;
259 }
260 }
261 else
262 {
263 for (j = str_len - (i - chars_per_limb) - 1; j > 0; j--)
264 {
265 res_digit = res_digit * base + *str++;
266 big_base *= base;
267 }
268 }
269
270 if (size == 0)
271 {
272 if (res_digit != 0)
273 {
274 rp[0] = res_digit;
275 size = 1;
276 }
277 }
278 else
279 {
280 #if HAVE_NATIVE_mpn_mul_1c
281 cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
282 #else
283 cy_limb = mpn_mul_1 (rp, rp, size, big_base);
284 cy_limb += mpn_add_1 (rp, rp, size, res_digit);
285 #endif
286 if (cy_limb != 0)
287 rp[size++] = cy_limb;
288 }
289 return size;
290 }