Annotation of OpenXM_contrib/gmp/mpn/generic/get_str.c, Revision 1.1
1.1 ! maekawa 1: /* mpn_get_str -- Convert a MSIZE long limb vector pointed to by MPTR
! 2: to a printable string in STR in base BASE.
! 3:
! 4: Copyright (C) 1991, 1992, 1993, 1994, 1996 Free Software Foundation, Inc.
! 5:
! 6: This file is part of the GNU MP Library.
! 7:
! 8: The GNU MP Library is free software; you can redistribute it and/or modify
! 9: it under the terms of the GNU Library General Public License as published by
! 10: the Free Software Foundation; either version 2 of the License, or (at your
! 11: option) any later version.
! 12:
! 13: The GNU MP Library is distributed in the hope that it will be useful, but
! 14: WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
! 15: or FITNESS FOR A PARTICULAR PURPOSE. See the GNU Library General Public
! 16: License for more details.
! 17:
! 18: You should have received a copy of the GNU Library General Public License
! 19: along with the GNU MP Library; see the file COPYING.LIB. If not, write to
! 20: the Free Software Foundation, Inc., 59 Temple Place - Suite 330, Boston,
! 21: MA 02111-1307, USA. */
! 22:
! 23: #include "gmp.h"
! 24: #include "gmp-impl.h"
! 25: #include "longlong.h"
! 26:
! 27: /* Convert the limb vector pointed to by MPTR and MSIZE long to a
! 28: char array, using base BASE for the result array. Store the
! 29: result in the character array STR. STR must point to an array with
! 30: space for the largest possible number represented by a MSIZE long
! 31: limb vector + 1 extra character.
! 32:
! 33: The result is NOT in Ascii, to convert it to printable format, add
! 34: '0' or 'A' depending on the base and range.
! 35:
! 36: Return the number of digits in the result string.
! 37: This may include some leading zeros.
! 38:
! 39: The limb vector pointed to by MPTR is clobbered. */
! 40:
! 41: size_t
! 42: mpn_get_str (str, base, mptr, msize)
! 43: unsigned char *str;
! 44: int base;
! 45: mp_ptr mptr;
! 46: mp_size_t msize;
! 47: {
! 48: mp_limb_t big_base;
! 49: #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
! 50: int normalization_steps;
! 51: #endif
! 52: #if UDIV_TIME > 2 * UMUL_TIME
! 53: mp_limb_t big_base_inverted;
! 54: #endif
! 55: unsigned int dig_per_u;
! 56: mp_size_t out_len;
! 57: register unsigned char *s;
! 58:
! 59: big_base = __mp_bases[base].big_base;
! 60:
! 61: s = str;
! 62:
! 63: /* Special case zero, as the code below doesn't handle it. */
! 64: if (msize == 0)
! 65: {
! 66: s[0] = 0;
! 67: return 1;
! 68: }
! 69:
! 70: if ((base & (base - 1)) == 0)
! 71: {
! 72: /* The base is a power of 2. Make conversion from most
! 73: significant side. */
! 74: mp_limb_t n1, n0;
! 75: register int bits_per_digit = big_base;
! 76: register int x;
! 77: register int bit_pos;
! 78: register int i;
! 79:
! 80: n1 = mptr[msize - 1];
! 81: count_leading_zeros (x, n1);
! 82:
! 83: /* BIT_POS should be R when input ends in least sign. nibble,
! 84: R + bits_per_digit * n when input ends in n:th least significant
! 85: nibble. */
! 86:
! 87: {
! 88: int bits;
! 89:
! 90: bits = BITS_PER_MP_LIMB * msize - x;
! 91: x = bits % bits_per_digit;
! 92: if (x != 0)
! 93: bits += bits_per_digit - x;
! 94: bit_pos = bits - (msize - 1) * BITS_PER_MP_LIMB;
! 95: }
! 96:
! 97: /* Fast loop for bit output. */
! 98: i = msize - 1;
! 99: for (;;)
! 100: {
! 101: bit_pos -= bits_per_digit;
! 102: while (bit_pos >= 0)
! 103: {
! 104: *s++ = (n1 >> bit_pos) & ((1 << bits_per_digit) - 1);
! 105: bit_pos -= bits_per_digit;
! 106: }
! 107: i--;
! 108: if (i < 0)
! 109: break;
! 110: n0 = (n1 << -bit_pos) & ((1 << bits_per_digit) - 1);
! 111: n1 = mptr[i];
! 112: bit_pos += BITS_PER_MP_LIMB;
! 113: *s++ = n0 | (n1 >> bit_pos);
! 114: }
! 115:
! 116: *s = 0;
! 117:
! 118: return s - str;
! 119: }
! 120: else
! 121: {
! 122: /* General case. The base is not a power of 2. Make conversion
! 123: from least significant end. */
! 124:
! 125: /* If udiv_qrnnd only handles divisors with the most significant bit
! 126: set, prepare BIG_BASE for being a divisor by shifting it to the
! 127: left exactly enough to set the most significant bit. */
! 128: #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
! 129: count_leading_zeros (normalization_steps, big_base);
! 130: big_base <<= normalization_steps;
! 131: #if UDIV_TIME > 2 * UMUL_TIME
! 132: /* Get the fixed-point approximation to 1/(BIG_BASE << NORMALIZATION_STEPS). */
! 133: big_base_inverted = __mp_bases[base].big_base_inverted;
! 134: #endif
! 135: #endif
! 136:
! 137: dig_per_u = __mp_bases[base].chars_per_limb;
! 138: out_len = ((size_t) msize * BITS_PER_MP_LIMB
! 139: * __mp_bases[base].chars_per_bit_exactly) + 1;
! 140: s += out_len;
! 141:
! 142: while (msize != 0)
! 143: {
! 144: int i;
! 145: mp_limb_t n0, n1;
! 146:
! 147: #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
! 148: /* If we shifted BIG_BASE above, shift the dividend too, to get
! 149: the right quotient. We need to do this every loop,
! 150: since the intermediate quotients are OK, but the quotient from
! 151: one turn in the loop is going to be the dividend in the
! 152: next turn, and the dividend needs to be up-shifted. */
! 153: if (normalization_steps != 0)
! 154: {
! 155: n0 = mpn_lshift (mptr, mptr, msize, normalization_steps);
! 156:
! 157: /* If the shifting gave a carry out limb, store it and
! 158: increase the length. */
! 159: if (n0 != 0)
! 160: {
! 161: mptr[msize] = n0;
! 162: msize++;
! 163: }
! 164: }
! 165: #endif
! 166:
! 167: /* Divide the number at TP with BIG_BASE to get a quotient and a
! 168: remainder. The remainder is our new digit in base BIG_BASE. */
! 169: i = msize - 1;
! 170: n1 = mptr[i];
! 171:
! 172: if (n1 >= big_base)
! 173: n1 = 0;
! 174: else
! 175: {
! 176: msize--;
! 177: i--;
! 178: }
! 179:
! 180: for (; i >= 0; i--)
! 181: {
! 182: n0 = mptr[i];
! 183: #if UDIV_TIME > 2 * UMUL_TIME
! 184: udiv_qrnnd_preinv (mptr[i], n1, n1, n0, big_base, big_base_inverted);
! 185: #else
! 186: udiv_qrnnd (mptr[i], n1, n1, n0, big_base);
! 187: #endif
! 188: }
! 189:
! 190: #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
! 191: /* If we shifted above (at previous UDIV_NEEDS_NORMALIZATION tests)
! 192: the remainder will be up-shifted here. Compensate. */
! 193: n1 >>= normalization_steps;
! 194: #endif
! 195:
! 196: /* Convert N1 from BIG_BASE to a string of digits in BASE
! 197: using single precision operations. */
! 198: for (i = dig_per_u - 1; i >= 0; i--)
! 199: {
! 200: *--s = n1 % base;
! 201: n1 /= base;
! 202: if (n1 == 0 && msize == 0)
! 203: break;
! 204: }
! 205: }
! 206:
! 207: while (s != str)
! 208: *--s = 0;
! 209: return out_len;
! 210: }
! 211: }
FreeBSD-CVSweb <freebsd-cvsweb@FreeBSD.org>
![[BACK]](/icons/cvsweb/back.gif){kind=icon}
Return to get_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