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 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 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_n (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 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 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