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, 2012, 2013 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 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 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 mp_limb_t big_base; 135 int chars_per_limb; 136 size_t digits_in_base; 137 mp_size_t shift; 138 139 powtab_mem_ptr = powtab_mem; 140 141 chars_per_limb = mp_bases[base].chars_per_limb; 142 big_base = mp_bases[base].big_base; 143 144 p = powtab_mem_ptr; 145 powtab_mem_ptr += 1; 146 147 digits_in_base = chars_per_limb; 148 149 p[0] = big_base; 150 n = 1; 151 152 count_leading_zeros (i, un - 1); 153 i = GMP_LIMB_BITS - 1 - i; 154 155 powtab[i].p = p; 156 powtab[i].n = n; 157 powtab[i].digits_in_base = digits_in_base; 158 powtab[i].base = base; 159 powtab[i].shift = 0; 160 161 shift = 0; 162 for (pi = i - 1; pi >= 0; pi--) 163 { 164 t = powtab_mem_ptr; 165 powtab_mem_ptr += 2 * n; 166 167 ASSERT_ALWAYS (powtab_mem_ptr < powtab_mem + mpn_dc_set_str_powtab_alloc (un)); 168 169 mpn_sqr (t, p, n); 170 n = 2 * n - 1; n += t[n] != 0; 171 digits_in_base *= 2; 172 #if 1 173 if ((((un - 1) >> pi) & 2) == 0) 174 { 175 mpn_divexact_1 (t, t, n, big_base); 176 n -= t[n - 1] == 0; 177 digits_in_base -= chars_per_limb; 178 } 179 #else 180 if (CLEVER_CONDITION_1 ()) 181 { 182 /* perform adjustment operation of previous */ 183 cy = mpn_mul_1 (p, p, n, big_base); 184 } 185 if (CLEVER_CONDITION_2 ()) 186 { 187 /* perform adjustment operation of new */ 188 cy = mpn_mul_1 (t, t, n, big_base); 189 } 190 #endif 191 shift *= 2; 192 /* Strip low zero limbs, but be careful to keep the result divisible by 193 big_base. */ 194 while (t[0] == 0 && (t[1] & ((big_base & -big_base) - 1)) == 0) 195 { 196 t++; 197 n--; 198 shift++; 199 } 200 p = t; 201 powtab[pi].p = p; 202 powtab[pi].n = n; 203 powtab[pi].digits_in_base = digits_in_base; 204 powtab[pi].base = base; 205 powtab[pi].shift = shift; 206 } 207 } 208 209 mp_size_t 210 mpn_dc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, 211 const powers_t *powtab, mp_ptr tp) 212 { 213 size_t len_lo, len_hi; 214 mp_limb_t cy; 215 mp_size_t ln, hn, n, sn; 216 217 len_lo = powtab->digits_in_base; 218 219 if (str_len <= len_lo) 220 { 221 if (BELOW_THRESHOLD (str_len, SET_STR_DC_THRESHOLD)) 222 return mpn_bc_set_str (rp, str, str_len, powtab->base); 223 else 224 return mpn_dc_set_str (rp, str, str_len, powtab + 1, tp); 225 } 226 227 len_hi = str_len - len_lo; 228 ASSERT (len_lo >= len_hi); 229 230 if (BELOW_THRESHOLD (len_hi, SET_STR_DC_THRESHOLD)) 231 hn = mpn_bc_set_str (tp, str, len_hi, powtab->base); 232 else 233 hn = mpn_dc_set_str (tp, str, len_hi, powtab + 1, rp); 234 235 sn = powtab->shift; 236 237 if (hn == 0) 238 { 239 /* Zero +1 limb here, to avoid reading an allocated but uninitialised 240 limb in mpn_incr_u below. */ 241 MPN_ZERO (rp, powtab->n + sn + 1); 242 } 243 else 244 { 245 if (powtab->n > hn) 246 mpn_mul (rp + sn, powtab->p, powtab->n, tp, hn); 247 else 248 mpn_mul (rp + sn, tp, hn, powtab->p, powtab->n); 249 MPN_ZERO (rp, sn); 250 } 251 252 str = str + str_len - len_lo; 253 if (BELOW_THRESHOLD (len_lo, SET_STR_DC_THRESHOLD)) 254 ln = mpn_bc_set_str (tp, str, len_lo, powtab->base); 255 else 256 ln = mpn_dc_set_str (tp, str, len_lo, powtab + 1, tp + powtab->n + sn + 1); 257 258 if (ln != 0) 259 { 260 cy = mpn_add_n (rp, rp, tp, ln); 261 mpn_incr_u (rp + ln, cy); 262 } 263 n = hn + powtab->n + sn; 264 return n - (rp[n - 1] == 0); 265 } 266 267 mp_size_t 268 mpn_bc_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base) 269 { 270 mp_size_t size; 271 size_t i; 272 long j; 273 mp_limb_t cy_limb; 274 275 mp_limb_t big_base; 276 int chars_per_limb; 277 mp_limb_t res_digit; 278 279 ASSERT (base >= 2); 280 ASSERT (base < numberof (mp_bases)); 281 ASSERT (str_len >= 1); 282 283 big_base = mp_bases[base].big_base; 284 chars_per_limb = mp_bases[base].chars_per_limb; 285 286 size = 0; 287 for (i = chars_per_limb; i < str_len; i += chars_per_limb) 288 { 289 res_digit = *str++; 290 if (base == 10) 291 { /* This is a common case. 292 Help the compiler to avoid multiplication. */ 293 for (j = MP_BASES_CHARS_PER_LIMB_10 - 1; j != 0; j--) 294 res_digit = res_digit * 10 + *str++; 295 } 296 else 297 { 298 for (j = chars_per_limb - 1; j != 0; j--) 299 res_digit = res_digit * base + *str++; 300 } 301 302 if (size == 0) 303 { 304 if (res_digit != 0) 305 { 306 rp[0] = res_digit; 307 size = 1; 308 } 309 } 310 else 311 { 312 #if HAVE_NATIVE_mpn_mul_1c 313 cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit); 314 #else 315 cy_limb = mpn_mul_1 (rp, rp, size, big_base); 316 cy_limb += mpn_add_1 (rp, rp, size, res_digit); 317 #endif 318 if (cy_limb != 0) 319 rp[size++] = cy_limb; 320 } 321 } 322 323 big_base = base; 324 res_digit = *str++; 325 if (base == 10) 326 { /* This is a common case. 327 Help the compiler to avoid multiplication. */ 328 for (j = str_len - (i - MP_BASES_CHARS_PER_LIMB_10) - 1; j > 0; j--) 329 { 330 res_digit = res_digit * 10 + *str++; 331 big_base *= 10; 332 } 333 } 334 else 335 { 336 for (j = str_len - (i - chars_per_limb) - 1; j > 0; j--) 337 { 338 res_digit = res_digit * base + *str++; 339 big_base *= base; 340 } 341 } 342 343 if (size == 0) 344 { 345 if (res_digit != 0) 346 { 347 rp[0] = res_digit; 348 size = 1; 349 } 350 } 351 else 352 { 353 #if HAVE_NATIVE_mpn_mul_1c 354 cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit); 355 #else 356 cy_limb = mpn_mul_1 (rp, rp, size, big_base); 357 cy_limb += mpn_add_1 (rp, rp, size, res_digit); 358 #endif 359 if (cy_limb != 0) 360 rp[size++] = cy_limb; 361 } 362 return size; 363 } 364