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.
5 Contributed to the GNU project by Torbjorn Granlund.
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
12 Copyright 1991-1994, 1996, 2000-2002, 2004, 2006-2008, 2012, 2013 Free
13 Software Foundation, Inc.
15 This file is part of the GNU MP Library.
17 The GNU MP Library is free software; you can redistribute it and/or modify
18 it under the terms of either:
20 * the GNU Lesser General Public License as published by the Free
21 Software Foundation; either version 3 of the License, or (at your
22 option) any later version.
26 * the GNU General Public License as published by the Free Software
27 Foundation; either version 2 of the License, or (at your option) any
30 or both in parallel, as here.
32 The GNU MP Library is distributed in the hope that it will be useful, but
33 WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
34 or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
37 You should have received copies of the GNU General Public License and the
38 GNU Lesser General Public License along with the GNU MP Library. If not,
39 see https://www.gnu.org/licenses/. */
44 Perhaps do not compute the highest power?
45 Instead, multiply twice by the 2nd highest power:
51 |_______________| final result
58 |___________| intermediate result
61 |_______________| final result
63 Generalizing that idea, perhaps we should make powtab contain successive
72 mpn_set_str (mp_ptr rp
, const unsigned char *str
, size_t str_len
, int base
)
76 /* The base is a power of 2. Read the input string from least to most
77 significant character/digit. */
79 const unsigned char *s
;
83 int bits_per_indigit
= mp_bases
[base
].big_base
;
89 for (s
= str
+ str_len
- 1; s
>= str
; s
--)
93 res_digit
|= ((mp_limb_t
) inp_digit
<< next_bitpos
) & GMP_NUMB_MASK
;
94 next_bitpos
+= bits_per_indigit
;
95 if (next_bitpos
>= GMP_NUMB_BITS
)
97 rp
[size
++] = res_digit
;
98 next_bitpos
-= GMP_NUMB_BITS
;
99 res_digit
= inp_digit
>> (bits_per_indigit
- next_bitpos
);
104 rp
[size
++] = res_digit
;
108 if (BELOW_THRESHOLD (str_len
, SET_STR_PRECOMPUTE_THRESHOLD
))
109 return mpn_bc_set_str (rp
, str
, str_len
, base
);
112 mp_ptr powtab_mem
, tp
;
113 powers_t powtab
[GMP_LIMB_BITS
];
121 chars_per_limb
= mp_bases
[base
].chars_per_limb
;
123 un
= str_len
/ chars_per_limb
+ 1;
125 /* Allocate one large block for the powers of big_base. */
126 powtab_mem
= TMP_BALLOC_LIMBS (mpn_dc_set_str_powtab_alloc (un
));
128 mpn_set_str_compute_powtab (powtab
, powtab_mem
, un
, base
);
130 tp
= TMP_BALLOC_LIMBS (mpn_dc_set_str_itch (un
));
131 size
= mpn_dc_set_str (rp
, str
, str_len
, powtab
, tp
);
139 mpn_set_str_compute_powtab (powers_t
*powtab
, mp_ptr powtab_mem
, mp_size_t un
, int base
)
141 mp_ptr powtab_mem_ptr
;
147 size_t digits_in_base
;
150 powtab_mem_ptr
= powtab_mem
;
152 chars_per_limb
= mp_bases
[base
].chars_per_limb
;
153 big_base
= mp_bases
[base
].big_base
;
158 digits_in_base
= chars_per_limb
;
163 count_leading_zeros (i
, un
- 1);
164 i
= GMP_LIMB_BITS
- 1 - i
;
168 powtab
[i
].digits_in_base
= digits_in_base
;
169 powtab
[i
].base
= base
;
173 for (pi
= i
- 1; pi
>= 0; pi
--)
176 powtab_mem_ptr
+= 2 * n
;
178 ASSERT_ALWAYS (powtab_mem_ptr
< powtab_mem
+ mpn_dc_set_str_powtab_alloc (un
));
181 n
= 2 * n
- 1; n
+= t
[n
] != 0;
184 if ((((un
- 1) >> pi
) & 2) == 0)
186 mpn_divexact_1 (t
, t
, n
, big_base
);
188 digits_in_base
-= chars_per_limb
;
191 if (CLEVER_CONDITION_1 ())
193 /* perform adjustment operation of previous */
194 cy
= mpn_mul_1 (p
, p
, n
, big_base
);
196 if (CLEVER_CONDITION_2 ())
198 /* perform adjustment operation of new */
199 cy
= mpn_mul_1 (t
, t
, n
, big_base
);
203 /* Strip low zero limbs, but be careful to keep the result divisible by
205 while (t
[0] == 0 && (t
[1] & ((big_base
& -big_base
) - 1)) == 0)
214 powtab
[pi
].digits_in_base
= digits_in_base
;
215 powtab
[pi
].base
= base
;
216 powtab
[pi
].shift
= shift
;
221 mpn_dc_set_str (mp_ptr rp
, const unsigned char *str
, size_t str_len
,
222 const powers_t
*powtab
, mp_ptr tp
)
224 size_t len_lo
, len_hi
;
226 mp_size_t ln
, hn
, n
, sn
;
228 len_lo
= powtab
->digits_in_base
;
230 if (str_len
<= len_lo
)
232 if (BELOW_THRESHOLD (str_len
, SET_STR_DC_THRESHOLD
))
233 return mpn_bc_set_str (rp
, str
, str_len
, powtab
->base
);
235 return mpn_dc_set_str (rp
, str
, str_len
, powtab
+ 1, tp
);
238 len_hi
= str_len
- len_lo
;
239 ASSERT (len_lo
>= len_hi
);
241 if (BELOW_THRESHOLD (len_hi
, SET_STR_DC_THRESHOLD
))
242 hn
= mpn_bc_set_str (tp
, str
, len_hi
, powtab
->base
);
244 hn
= mpn_dc_set_str (tp
, str
, len_hi
, powtab
+ 1, rp
);
250 /* Zero +1 limb here, to avoid reading an allocated but uninitialised
251 limb in mpn_incr_u below. */
252 MPN_ZERO (rp
, powtab
->n
+ sn
+ 1);
257 mpn_mul (rp
+ sn
, powtab
->p
, powtab
->n
, tp
, hn
);
259 mpn_mul (rp
+ sn
, tp
, hn
, powtab
->p
, powtab
->n
);
263 str
= str
+ str_len
- len_lo
;
264 if (BELOW_THRESHOLD (len_lo
, SET_STR_DC_THRESHOLD
))
265 ln
= mpn_bc_set_str (tp
, str
, len_lo
, powtab
->base
);
267 ln
= mpn_dc_set_str (tp
, str
, len_lo
, powtab
+ 1, tp
+ powtab
->n
+ sn
+ 1);
271 cy
= mpn_add_n (rp
, rp
, tp
, ln
);
272 mpn_incr_u (rp
+ ln
, cy
);
274 n
= hn
+ powtab
->n
+ sn
;
275 return n
- (rp
[n
- 1] == 0);
279 mpn_bc_set_str (mp_ptr rp
, const unsigned char *str
, size_t str_len
, int base
)
291 ASSERT (base
< numberof (mp_bases
));
292 ASSERT (str_len
>= 1);
294 big_base
= mp_bases
[base
].big_base
;
295 chars_per_limb
= mp_bases
[base
].chars_per_limb
;
298 for (i
= chars_per_limb
; i
< str_len
; i
+= chars_per_limb
)
302 { /* This is a common case.
303 Help the compiler to avoid multiplication. */
304 for (j
= MP_BASES_CHARS_PER_LIMB_10
- 1; j
!= 0; j
--)
305 res_digit
= res_digit
* 10 + *str
++;
309 for (j
= chars_per_limb
- 1; j
!= 0; j
--)
310 res_digit
= res_digit
* base
+ *str
++;
323 #if HAVE_NATIVE_mpn_mul_1c
324 cy_limb
= mpn_mul_1c (rp
, rp
, size
, big_base
, res_digit
);
326 cy_limb
= mpn_mul_1 (rp
, rp
, size
, big_base
);
327 cy_limb
+= mpn_add_1 (rp
, rp
, size
, res_digit
);
330 rp
[size
++] = cy_limb
;
337 { /* This is a common case.
338 Help the compiler to avoid multiplication. */
339 for (j
= str_len
- (i
- MP_BASES_CHARS_PER_LIMB_10
) - 1; j
> 0; j
--)
341 res_digit
= res_digit
* 10 + *str
++;
347 for (j
= str_len
- (i
- chars_per_limb
) - 1; j
> 0; j
--)
349 res_digit
= res_digit
* base
+ *str
++;
364 #if HAVE_NATIVE_mpn_mul_1c
365 cy_limb
= mpn_mul_1c (rp
, rp
, size
, big_base
, res_digit
);
367 cy_limb
= mpn_mul_1 (rp
, rp
, size
, big_base
);
368 cy_limb
+= mpn_add_1 (rp
, rp
, size
, res_digit
);
371 rp
[size
++] = cy_limb
;