Annotation of OpenXM_contrib/gmp/mpn/generic/set_str.c, Revision 1.1.1.3
1.1.1.3 ! ohara 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.
1.1 maekawa 4:
1.1.1.3 ! ohara 5: Copyright 1991, 1992, 1993, 1994, 1996, 2000, 2001, 2002 Free Software
! 6: Foundation, Inc.
1.1 maekawa 7:
8: This file is part of the GNU MP Library.
9:
1.1.1.3 ! ohara 10: The GNU MP Library is free software; you can redistribute it and/or modify it
! 11: under the terms of the GNU Library General Public License as published by the
! 12: Free Software Foundation; either version 2 of the License, or (at your option)
! 13: any later version.
1.1 maekawa 14:
15: The GNU MP Library is distributed in the hope that it will be useful, but
1.1.1.3 ! ohara 16: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
! 17: FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public License
! 18: for more details.
! 19:
! 20: You should have received a copy of the GNU Library General Public License along
! 21: with the GNU MP Library; see the file COPYING.LIB. If not, write to the Free
! 22: Software Foundation, Inc., 59 Temple Place - Suite 330, Boston, MA 02111-1307,
! 23: USA. */
1.1 maekawa 24:
25: #include "gmp.h"
26: #include "gmp-impl.h"
27:
1.1.1.3 ! ohara 28: static mp_size_t convert_blocks __GMP_PROTO ((mp_ptr, const unsigned char *, size_t, int));
! 29:
! 30: /* When to switch to sub-quadratic code. This counts characters/digits in
! 31: the input string, not limbs as most other *_THRESHOLD. */
! 32: #ifndef SET_STR_THRESHOLD
! 33: #define SET_STR_THRESHOLD 4000
! 34: #endif
! 35:
! 36: /* Don't define this to anything but 1 for now. In order to make other values
! 37: work well, either the convert_blocks function should be generazed to handle
! 38: larger blocks than chars_per_limb, or the basecase code should be broken out
! 39: of the main function. Also note that this must be a power of 2. */
! 40: #ifndef SET_STR_BLOCK_SIZE
! 41: #define SET_STR_BLOCK_SIZE 1 /* Must be a power of 2. */
1.1.1.2 maekawa 42: #endif
1.1.1.3 ! ohara 43:
! 44:
! 45: /* This check interferes with expression based values of SET_STR_THRESHOLD
! 46: used for tuning and measuring.
! 47: #if SET_STR_BLOCK_SIZE >= SET_STR_THRESHOLD
! 48: These values are silly.
! 49: The sub-quadratic code would recurse to itself.
! 50: #endif
! 51: */
! 52:
! 53: mp_size_t
! 54: mpn_set_str (mp_ptr rp, const unsigned char *str, size_t str_len, int base)
1.1 maekawa 55: {
56: mp_size_t size;
57: mp_limb_t big_base;
1.1.1.3 ! ohara 58: int chars_per_limb;
1.1 maekawa 59: mp_limb_t res_digit;
60:
1.1.1.3 ! ohara 61: ASSERT (base >= 2);
! 62: ASSERT (base < numberof (__mp_bases));
! 63: ASSERT (str_len >= 1);
1.1 maekawa 64:
1.1.1.3 ! ohara 65: big_base = __mp_bases[base].big_base;
! 66: chars_per_limb = __mp_bases[base].chars_per_limb;
1.1 maekawa 67:
68: size = 0;
69:
1.1.1.3 ! ohara 70: if (POW2_P (base))
1.1 maekawa 71: {
1.1.1.3 ! ohara 72: /* The base is a power of 2. Read the input string from least to most
! 73: significant character/digit. */
1.1 maekawa 74:
75: const unsigned char *s;
76: int next_bitpos;
77: int bits_per_indigit = big_base;
78:
79: res_digit = 0;
80: next_bitpos = 0;
81:
82: for (s = str + str_len - 1; s >= str; s--)
83: {
84: int inp_digit = *s;
85:
1.1.1.3 ! ohara 86: res_digit |= ((mp_limb_t) inp_digit << next_bitpos) & GMP_NUMB_MASK;
1.1 maekawa 87: next_bitpos += bits_per_indigit;
1.1.1.3 ! ohara 88: if (next_bitpos >= GMP_NUMB_BITS)
1.1 maekawa 89: {
1.1.1.3 ! ohara 90: rp[size++] = res_digit;
! 91: next_bitpos -= GMP_NUMB_BITS;
1.1 maekawa 92: res_digit = inp_digit >> (bits_per_indigit - next_bitpos);
93: }
94: }
95:
96: if (res_digit != 0)
1.1.1.3 ! ohara 97: rp[size++] = res_digit;
! 98: return size;
1.1 maekawa 99: }
100: else
101: {
102: /* General case. The base is not a power of 2. */
103:
1.1.1.3 ! ohara 104: if (str_len < SET_STR_THRESHOLD)
1.1 maekawa 105: {
1.1.1.3 ! ohara 106: size_t i;
! 107: int j;
! 108: mp_limb_t cy_limb;
! 109:
! 110: for (i = chars_per_limb; i < str_len; i += chars_per_limb)
! 111: {
! 112: res_digit = *str++;
! 113: if (base == 10)
! 114: { /* This is a common case.
! 115: Help the compiler to avoid multiplication. */
! 116: for (j = MP_BASES_CHARS_PER_LIMB_10 - 1; j != 0; j--)
! 117: res_digit = res_digit * 10 + *str++;
! 118: }
! 119: else
! 120: {
! 121: for (j = chars_per_limb - 1; j != 0; j--)
! 122: res_digit = res_digit * base + *str++;
! 123: }
! 124:
! 125: if (size == 0)
! 126: {
! 127: if (res_digit != 0)
! 128: {
! 129: rp[0] = res_digit;
! 130: size = 1;
! 131: }
! 132: }
! 133: else
! 134: {
! 135: #if HAVE_NATIVE_mpn_mul_1c
! 136: cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
! 137: #else
! 138: cy_limb = mpn_mul_1 (rp, rp, size, big_base);
! 139: cy_limb += mpn_add_1 (rp, rp, size, res_digit);
! 140: #endif
! 141: if (cy_limb != 0)
! 142: rp[size++] = cy_limb;
! 143: }
! 144: }
! 145:
! 146: big_base = base;
1.1 maekawa 147: res_digit = *str++;
148: if (base == 10)
149: { /* This is a common case.
150: Help the compiler to avoid multiplication. */
1.1.1.3 ! ohara 151: for (j = str_len - (i - MP_BASES_CHARS_PER_LIMB_10) - 1; j > 0; j--)
! 152: {
! 153: res_digit = res_digit * 10 + *str++;
! 154: big_base *= 10;
! 155: }
1.1 maekawa 156: }
157: else
158: {
1.1.1.3 ! ohara 159: for (j = str_len - (i - chars_per_limb) - 1; j > 0; j--)
! 160: {
! 161: res_digit = res_digit * base + *str++;
! 162: big_base *= base;
! 163: }
1.1 maekawa 164: }
165:
166: if (size == 0)
167: {
168: if (res_digit != 0)
169: {
1.1.1.3 ! ohara 170: rp[0] = res_digit;
1.1 maekawa 171: size = 1;
172: }
173: }
174: else
175: {
1.1.1.3 ! ohara 176: #if HAVE_NATIVE_mpn_mul_1c
! 177: cy_limb = mpn_mul_1c (rp, rp, size, big_base, res_digit);
! 178: #else
! 179: cy_limb = mpn_mul_1 (rp, rp, size, big_base);
! 180: cy_limb += mpn_add_1 (rp, rp, size, res_digit);
! 181: #endif
1.1 maekawa 182: if (cy_limb != 0)
1.1.1.3 ! ohara 183: rp[size++] = cy_limb;
1.1 maekawa 184: }
1.1.1.3 ! ohara 185: return size;
1.1 maekawa 186: }
1.1.1.3 ! ohara 187: else
! 188: {
! 189: /* Sub-quadratic code. */
1.1 maekawa 190:
1.1.1.3 ! ohara 191: mp_ptr dp;
! 192: mp_size_t dsize;
! 193: mp_ptr xp, tp;
! 194: mp_size_t step;
! 195: mp_size_t i;
! 196: size_t alloc;
! 197: mp_size_t n;
! 198: mp_ptr pow_mem;
! 199:
! 200: alloc = (str_len + chars_per_limb - 1) / chars_per_limb;
! 201: alloc = 2 * alloc;
! 202: dp = __GMP_ALLOCATE_FUNC_LIMBS (alloc);
! 203:
! 204: #if SET_STR_BLOCK_SIZE == 1
! 205: dsize = convert_blocks (dp, str, str_len, base);
! 206: #else
! 207: {
! 208: const unsigned char *s;
! 209: mp_ptr ddp = dp;
! 210:
! 211: s = str + str_len;
! 212: while (s - str > SET_STR_BLOCK_SIZE * chars_per_limb)
! 213: {
! 214: s -= SET_STR_BLOCK_SIZE * chars_per_limb;
! 215: mpn_set_str (ddp, s, SET_STR_BLOCK_SIZE * chars_per_limb, base);
! 216: ddp += SET_STR_BLOCK_SIZE;
! 217: }
! 218: ddp += mpn_set_str (ddp, str, s - str, base);
! 219: dsize = ddp - dp;
! 220: }
! 221: #endif
! 222:
! 223: /* Allocate space for powers of big_base. Could trim this in two
! 224: ways:
! 225: 1. Only really need 2^ceil(log2(dsize)) bits for the largest
! 226: power.
! 227: 2. Only the variable to get the largest power need that much
! 228: memory. The other variable needs half as much. Need just
! 229: figure out which of xp and tp will hold the last one.
! 230: Net space savings would be in the range 1/4 to 5/8 of current
! 231: allocation, depending on how close to the next power of 2 that
! 232: dsize is. */
! 233: pow_mem = __GMP_ALLOCATE_FUNC_LIMBS (2 * alloc);
! 234: xp = pow_mem;
! 235: tp = pow_mem + alloc;
! 236:
! 237: xp[0] = big_base;
! 238: n = 1;
! 239: step = 1;
! 240: #if SET_STR_BLOCK_SIZE != 1
! 241: for (i = SET_STR_BLOCK_SIZE; i > 1; i >>= 1)
1.1 maekawa 242: {
1.1.1.3 ! ohara 243: mpn_sqr_n (tp, xp, n);
! 244: n = 2 * n;
! 245: n -= tp[n - 1] == 0;
! 246:
! 247: step = 2 * step;
! 248: MP_PTR_SWAP (tp, xp);
1.1 maekawa 249: }
1.1.1.3 ! ohara 250: #endif
! 251:
! 252: /* Multiply every second limb block, each `step' limbs large by the
! 253: base power currently in xp[], then add this to the adjacent block.
! 254: We thereby convert from dsize blocks in base big_base, to dsize/2
! 255: blocks in base big_base^2, then to dsize/4 blocks in base
! 256: big_base^4, etc, etc. */
! 257:
! 258: if (step < dsize)
1.1 maekawa 259: {
1.1.1.3 ! ohara 260: for (;;)
! 261: {
! 262: for (i = 0; i < dsize - step; i += 2 * step)
! 263: {
! 264: mp_ptr bp = dp + i;
! 265: mp_size_t m = dsize - i - step;
! 266: mp_size_t hi;
! 267: if (n >= m)
! 268: {
! 269: mpn_mul (tp, xp, n, bp + step, m);
! 270: mpn_add (bp, tp, n + m, bp, n);
! 271: hi = i + n + m;
! 272: dsize = hi;
! 273: dsize -= dp[dsize - 1] == 0;
! 274: }
! 275: else
! 276: {
! 277: mpn_mul_n (tp, xp, bp + step, n);
! 278: mpn_add (bp, tp, n + n, bp, n);
! 279: }
! 280: }
! 281:
! 282: step = 2 * step;
! 283: if (! (step < dsize))
! 284: break;
! 285:
! 286: mpn_sqr_n (tp, xp, n);
! 287: n = 2 * n;
! 288: n -= tp[n - 1] == 0;
! 289: MP_PTR_SWAP (tp, xp);
! 290: }
1.1 maekawa 291: }
1.1.1.3 ! ohara 292:
! 293: MPN_NORMALIZE (dp, dsize);
! 294: MPN_COPY (rp, dp, dsize);
! 295: __GMP_FREE_FUNC_LIMBS (pow_mem, 2 * alloc);
! 296: __GMP_FREE_FUNC_LIMBS (dp, alloc);
! 297: return dsize;
1.1 maekawa 298: }
1.1.1.3 ! ohara 299: }
! 300: }
! 301:
! 302: static mp_size_t
! 303: convert_blocks (mp_ptr dp, const unsigned char *str, size_t str_len, int base)
! 304: {
! 305: int chars_per_limb;
! 306: mp_size_t i;
! 307: int j;
! 308: int ds;
! 309: mp_size_t dsize;
! 310: mp_limb_t res_digit;
! 311:
! 312: chars_per_limb = __mp_bases[base].chars_per_limb;
1.1 maekawa 313:
1.1.1.3 ! ohara 314: dsize = str_len / chars_per_limb;
! 315: ds = str_len % chars_per_limb;
! 316:
! 317: if (ds != 0)
! 318: {
! 319: res_digit = *str++;
! 320: for (j = ds - 1; j != 0; j--)
! 321: res_digit = res_digit * base + *str++;
! 322: dp[dsize] = res_digit;
! 323: }
! 324:
! 325: if (base == 10)
! 326: {
! 327: for (i = dsize - 1; i >= 0; i--)
1.1 maekawa 328: {
1.1.1.3 ! ohara 329: res_digit = *str++;
! 330: for (j = MP_BASES_CHARS_PER_LIMB_10 - 1; j != 0; j--)
! 331: res_digit = res_digit * 10 + *str++;
! 332: dp[i] = res_digit;
1.1 maekawa 333: }
1.1.1.3 ! ohara 334: }
! 335: else
! 336: {
! 337: for (i = dsize - 1; i >= 0; i--)
1.1 maekawa 338: {
1.1.1.3 ! ohara 339: res_digit = *str++;
! 340: for (j = chars_per_limb - 1; j != 0; j--)
! 341: res_digit = res_digit * base + *str++;
! 342: dp[i] = res_digit;
1.1 maekawa 343: }
344: }
345:
1.1.1.3 ! ohara 346: return dsize + (ds != 0);
1.1 maekawa 347: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to set_str.c CVS log ![[TXT]](/icons/cvsweb/text.gif){kind=icon}
![[DIR]](/icons/cvsweb/dir.gif){kind=icon}
Up to [local] / OpenXM_contrib / gmp / mpn / generic