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