1 /* Internal function for converting integers to ASCII.
2 Copyright (C) 1994-2015 Free Software Foundation, Inc.
3 This file is part of the GNU C Library.
4 Contributed by Torbjorn Granlund <tege@matematik.su.se>
5 and Ulrich Drepper <drepper@gnu.org>.
7 The GNU C Library is free software; you can redistribute it and/or
8 modify it under the terms of the GNU Lesser General Public
9 License as published by the Free Software Foundation; either
10 version 2.1 of the License, or (at your option) any later version.
12 The GNU C Library is distributed in the hope that it will be useful,
13 but WITHOUT ANY WARRANTY; without even the implied warranty of
14 MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
15 Lesser General Public License for more details.
17 You should have received a copy of the GNU Lesser General Public
18 License along with the GNU C Library; if not, see
19 <http://www.gnu.org/licenses/>. */
21 #include <gmp-mparam.h>
24 #include <stdlib/gmp-impl.h>
25 #include <stdlib/longlong.h>
30 /* Canonize environment. For some architectures not all values might
31 be defined in the GMP header files. */
39 /* Control memory layout. */
42 # define PACK __attribute__ ((packed))
48 /* Declare local types. */
51 #if (UDIV_TIME > 2 * UMUL_TIME)
52 mp_limb_t base_multiplier
;
56 #if BITS_PER_MP_LIMB == 32
59 char normalization_steps
;
62 #if UDIV_TIME > 2 * UMUL_TIME
63 mp_limb_t base_ninv PACK
;
69 /* To reduce the memory needed we include some fields of the tables
70 only conditionally. */
71 #if UDIV_TIME > 2 * UMUL_TIME
79 /* Factor table for the different bases. */
80 extern const struct base_table_t _itoa_base_table
[] attribute_hidden
;
82 /* Lower-case digits. */
83 extern const wchar_t _itowa_lower_digits
[] attribute_hidden
;
84 /* Upper-case digits. */
85 extern const wchar_t _itowa_upper_digits
[] attribute_hidden
;
90 _itowa (value
, buflim
, base
, upper_case
)
91 unsigned long long int value
;
96 const wchar_t *digits
= (upper_case
97 ? _itowa_upper_digits
: _itowa_lower_digits
);
99 const struct base_table_t
*brec
= &_itoa_base_table
[base
- 2];
103 # define RUN_2N(BITS) \
106 /* `unsigned long long int' always has 64 bits. */ \
107 mp_limb_t work_hi = value >> (64 - BITS_PER_MP_LIMB); \
109 if (BITS_PER_MP_LIMB == 32) \
116 work_lo = value & 0xfffffffful; \
117 for (cnt = BITS_PER_MP_LIMB / BITS; cnt > 0; --cnt) \
119 *--bp = digits[work_lo & ((1ul << BITS) - 1)]; \
122 if (BITS_PER_MP_LIMB % BITS != 0) \
126 & ((1 << (BITS - BITS_PER_MP_LIMB%BITS)) \
128 << BITS_PER_MP_LIMB % BITS); \
129 work_hi >>= BITS - BITS_PER_MP_LIMB % BITS; \
133 *--bp = digits[work_lo]; \
137 work_hi = value & 0xfffffffful; \
141 *--bp = digits[work_hi & ((1 << BITS) - 1)]; \
144 while (work_hi != 0); \
157 # if BITS_PER_MP_LIMB == 64
158 mp_limb_t base_multiplier
= brec
->base_multiplier
;
162 mp_limb_t quo
, rem
, x
;
163 mp_limb_t dummy
__attribute__ ((unused
));
165 umul_ppmm (x
, dummy
, value
, base_multiplier
);
166 quo
= (x
+ ((value
- x
) >> 1)) >> (brec
->post_shift
- 1);
167 rem
= value
- quo
* base
;
174 mp_limb_t quo
, rem
, x
;
175 mp_limb_t dummy
__attribute__ ((unused
));
177 umul_ppmm (x
, dummy
, value
, base_multiplier
);
178 quo
= x
>> brec
->post_shift
;
179 rem
= value
- quo
* base
;
184 # if BITS_PER_MP_LIMB == 32
188 /* First convert x0 to 1-3 words in base s->big.base.
189 Optimize for frequent cases of 32 bit numbers. */
190 if ((mp_limb_t
) (value
>> 32) >= 1)
192 # if UDIV_TIME > 2 * UMUL_TIME || UDIV_NEEDS_NORMALIZATION
193 int big_normalization_steps
= brec
->big
.normalization_steps
;
194 mp_limb_t big_base_norm
195 = brec
->big
.base
<< big_normalization_steps
;
197 if ((mp_limb_t
) (value
>> 32) >= brec
->big
.base
)
199 mp_limb_t x1hi
, x1lo
, r
;
200 /* If you want to optimize this, take advantage of
201 that the quotient in the first udiv_qrnnd will
202 always be very small. It might be faster just to
203 subtract in a tight loop. */
205 # if UDIV_TIME > 2 * UMUL_TIME
208 if (big_normalization_steps
== 0)
211 xh
= (mp_limb_t
) (value
>> (64 - big_normalization_steps
));
212 xl
= (mp_limb_t
) (value
>> (32 - big_normalization_steps
));
213 udiv_qrnnd_preinv (x1hi
, r
, xh
, xl
, big_base_norm
,
214 brec
->big
.base_ninv
);
216 xl
= ((mp_limb_t
) value
) << big_normalization_steps
;
217 udiv_qrnnd_preinv (x1lo
, x
, r
, xl
, big_base_norm
,
218 brec
->big
.base_ninv
);
219 t
[2] = x
>> big_normalization_steps
;
221 if (big_normalization_steps
== 0)
224 xh
= ((x1hi
<< big_normalization_steps
)
225 | (x1lo
>> (32 - big_normalization_steps
)));
226 xl
= x1lo
<< big_normalization_steps
;
227 udiv_qrnnd_preinv (t
[0], x
, xh
, xl
, big_base_norm
,
228 brec
->big
.base_ninv
);
229 t
[1] = x
>> big_normalization_steps
;
230 # elif UDIV_NEEDS_NORMALIZATION
233 if (big_normalization_steps
== 0)
236 xh
= (mp_limb_t
) (value
>> 64 - big_normalization_steps
);
237 xl
= (mp_limb_t
) (value
>> 32 - big_normalization_steps
);
238 udiv_qrnnd (x1hi
, r
, xh
, xl
, big_base_norm
);
240 xl
= ((mp_limb_t
) value
) << big_normalization_steps
;
241 udiv_qrnnd (x1lo
, x
, r
, xl
, big_base_norm
);
242 t
[2] = x
>> big_normalization_steps
;
244 if (big_normalization_steps
== 0)
247 xh
= ((x1hi
<< big_normalization_steps
)
248 | (x1lo
>> 32 - big_normalization_steps
));
249 xl
= x1lo
<< big_normalization_steps
;
250 udiv_qrnnd (t
[0], x
, xh
, xl
, big_base_norm
);
251 t
[1] = x
>> big_normalization_steps
;
253 udiv_qrnnd (x1hi
, r
, 0, (mp_limb_t
) (value
>> 32),
255 udiv_qrnnd (x1lo
, t
[2], r
, (mp_limb_t
) value
, brec
->big
.base
);
256 udiv_qrnnd (t
[0], t
[1], x1hi
, x1lo
, brec
->big
.base
);
262 # if UDIV_TIME > 2 * UMUL_TIME
265 value
<<= brec
->big
.normalization_steps
;
266 udiv_qrnnd_preinv (t
[0], x
, (mp_limb_t
) (value
>> 32),
267 (mp_limb_t
) value
, big_base_norm
,
268 brec
->big
.base_ninv
);
269 t
[1] = x
>> brec
->big
.normalization_steps
;
270 # elif UDIV_NEEDS_NORMALIZATION
273 value
<<= big_normalization_steps
;
274 udiv_qrnnd (t
[0], x
, (mp_limb_t
) (value
>> 32),
275 (mp_limb_t
) value
, big_base_norm
);
276 t
[1] = x
>> big_normalization_steps
;
278 udiv_qrnnd (t
[0], t
[1], (mp_limb_t
) (value
>> 32),
279 (mp_limb_t
) value
, brec
->big
.base
);
290 /* Convert the 1-3 words in t[], word by word, to ASCII. */
293 mp_limb_t ti
= t
[--n
];
294 int ndig_for_this_limb
= 0;
296 # if UDIV_TIME > 2 * UMUL_TIME
297 mp_limb_t base_multiplier
= brec
->base_multiplier
;
301 mp_limb_t quo
, rem
, x
;
302 mp_limb_t dummy
__attribute__ ((unused
));
304 umul_ppmm (x
, dummy
, ti
, base_multiplier
);
305 quo
= (x
+ ((ti
- x
) >> 1)) >> (brec
->post_shift
- 1);
306 rem
= ti
- quo
* base
;
309 ++ndig_for_this_limb
;
314 mp_limb_t quo
, rem
, x
;
315 mp_limb_t dummy
__attribute__ ((unused
));
317 umul_ppmm (x
, dummy
, ti
, base_multiplier
);
318 quo
= x
>> brec
->post_shift
;
319 rem
= ti
- quo
* base
;
322 ++ndig_for_this_limb
;
333 ++ndig_for_this_limb
;
336 /* If this wasn't the most significant word, pad with zeros. */
338 while (ndig_for_this_limb
< brec
->big
.ndigits
)
341 ++ndig_for_this_limb
;