1 /* _mpz_get_str (string, base, mp_src) -- Convert the multiple precision
2 number MP_SRC to a string STRING of base BASE. If STRING is NULL
3 allocate space for the result. In any case, return a pointer to the
4 result. If STRING is not NULL, the caller must ensure enough space is
5 available to store the result.
7 Copyright (C) 1991, 1993 Free Software Foundation, Inc.
9 This file is part of the GNU MP Library.
11 The GNU MP Library is free software; you can redistribute it and/or modify
12 it under the terms of the GNU General Public License as published by
13 the Free Software Foundation; either version 2, or (at your option)
16 The GNU MP Library is distributed in the hope that it will be useful,
17 but WITHOUT ANY WARRANTY; without even the implied warranty of
18 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
19 GNU General Public License for more details.
21 You should have received a copy of the GNU General Public License
22 along with the GNU MP Library; see the file COPYING. If not, write to
23 the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA. */
34 #define UDIV_TIME UMUL_TIME
37 #define udiv_qrnndx(q, r, nh, nl, d, di) \
39 unsigned long int _q, _ql, _r; \
40 unsigned long int _xh, _xl; \
41 umul_ppmm (_q, _ql, (nh), (di)); \
42 _q += (nh); /* DI is 2**32 too small. Compensate */\
45 /* Got carry. Propagate it in the multiplication. */ \
46 umul_ppmm (_xh, _xl, (d), _q); \
50 umul_ppmm (_xh, _xl, (d), _q); \
51 sub_ddmmss (_xh, _r, (nh), (nl), _xh, _xl); \
54 sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \
58 sub_ddmmss (_xh, _r, _xh, _r, 0, (d)); \
73 _mpz_get_str (char *str, int base, const MP_INT *m)
75 _mpz_get_str (str, base, m)
84 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
86 int normalization_steps;
87 #if UDIV_TIME > 2 * UMUL_TIME
88 mp_limb big_base_inverted;
91 unsigned int dig_per_u;
100 num_to_ascii = "0123456789abcdefghijklmnopqrstuvwxyz";
105 num_to_ascii = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
108 dig_per_u = __mp_bases[base].chars_per_limb;
109 out_len = mpz_sizeinbase (m, base) + 1;
110 big_base = __mp_bases[base].big_base;
115 str = (char *) (*_mp_allocate_func) (out_len + (msize < 0));
123 /* Special case zero, as the code below doesn't handle it. */
131 if ((base & (base - 1)) == 0)
133 /* The base is a power of 2. Make conversion from most
136 int bits_per_digit = big_base;
140 unsigned mask = (1 << bits_per_digit) - 1;
144 count_leading_zeros (x, n1);
146 /* BIT_POS should be R when input ends in least sign. nibble,
147 R + bits_per_digit * n when input ends in n:th least significant
153 bits = BITS_PER_MP_LIMB * msize - x;
154 x = bits % bits_per_digit;
156 bits += bits_per_digit - x;
157 bit_pos = bits - (msize - 1) * BITS_PER_MP_LIMB;
160 /* Fast loop for bit output. */
164 bit_pos -= bits_per_digit;
167 *s++ = num_to_ascii[(n1 >> bit_pos) & mask];
168 bit_pos -= bits_per_digit;
173 n0 = (n1 << -bit_pos) & mask;
175 bit_pos += BITS_PER_MP_LIMB;
176 *s++ = num_to_ascii[n0 | (n1 >> bit_pos)];
183 /* General case. The base is not a power of 2. Make conversion
184 from least significant end. */
186 /* If udiv_qrnnd only handles divisors with the most significant bit
187 set, prepare BIG_BASE for being a divisor by shifting it to the
188 left exactly enough to set the most significant bit. */
189 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
190 count_leading_zeros (normalization_steps, big_base);
191 big_base <<= normalization_steps;
192 #if UDIV_TIME > 2 * UMUL_TIME
193 /* Get the fixed-point approximation to 1/BIG_BASE. */
194 big_base_inverted = __mp_bases[base].big_base_inverted;
198 out_len--; /* now not include terminating \0 */
201 /* Allocate temporary space and move the multi prec number to
202 convert there, as we need to overwrite it below, while
203 computing the successive remainders. */
204 tp = (mp_ptr) alloca ((msize + 1) * BYTES_PER_MP_LIMB);
205 MPN_COPY (tp, m->d, msize);
212 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
213 /* If we shifted BIG_BASE above, shift the dividend too, to get
214 the right quotient. We need to do this every loop,
215 as the intermediate quotients are OK, but the quotient from
216 one turn in the loop is going to be the dividend in the
217 next turn, and the dividend needs to be up-shifted. */
218 if (normalization_steps != 0)
220 n0 = mpn_lshift (tp, tp, msize, normalization_steps);
222 /* If the shifting gave a carry out limb, store it and
223 increase the length. */
232 /* Divide the number at TP with BIG_BASE to get a quotient and a
233 remainder. The remainder is our new digit in base BIG_BASE. */
248 #if UDIV_TIME > 2 * UMUL_TIME
249 udiv_qrnndx (tp[i], n1, n1, n0, big_base, big_base_inverted);
251 udiv_qrnnd (tp[i], n1, n1, n0, big_base);
255 #if UDIV_NEEDS_NORMALIZATION || UDIV_TIME > 2 * UMUL_TIME
256 /* If we shifted above (at previous UDIV_NEEDS_NORMALIZATION tests)
257 the remainder will be up-shifted here. Compensate. */
258 n1 >>= normalization_steps;
261 /* Convert N1 from BIG_BASE to a string of digits in BASE
262 using single precision operations. */
263 for (i = dig_per_u - 1; i >= 0; i--)
265 *--s = num_to_ascii[n1 % base];
267 /* Break from the loop as soon as we would only write zeros. */
268 if (n1 == 0 && msize == 0)
273 /* There should be no leading zeros. */
279 /* This should be the common case. */
282 else if (s == str + 1)
284 /* The string became 1 digit shorter than its maximum. */
285 /* Need to copy it back one char pos. */
291 for (i = 0; i < out_len; i++)
295 memmove (str, s, out_len);
301 /* Hopefully never. */
307 /* Ugly, we incremented str for negative numbers. Fix that here. */
308 return str - (m->size < 0);