Annotation of OpenXM_contrib/gmp/mpn/generic/get_str.c, Revision 1.1.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