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