1 /* Internal function for converting integers to ASCII.
2 Copyright (C) 1994-2019 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
80 /* We do not compile _itoa if we always can use _itoa_word. */
82 /* Local variables. */
83 const struct base_table_t _itoa_base_table
[] attribute_hidden
=
85 # if BITS_PER_MP_LIMB == 64
86 /* 2 */ {SEL1(0ull) 1, 1},
87 /* 3 */ {SEL1(0xaaaaaaaaaaaaaaabull
) 0, 1},
88 /* 4 */ {SEL1(0ull) 1, 2},
89 /* 5 */ {SEL1(0xcccccccccccccccdull
) 0, 2},
90 /* 6 */ {SEL1(0xaaaaaaaaaaaaaaabull
) 0, 2},
91 /* 7 */ {SEL1(0x2492492492492493ull
) 1, 3},
92 /* 8 */ {SEL1(0ull) 1, 3},
93 /* 9 */ {SEL1(0xe38e38e38e38e38full
) 0, 3},
94 /* 10 */ {SEL1(0xcccccccccccccccdull
) 0, 3},
95 /* 11 */ {SEL1(0x2e8ba2e8ba2e8ba3ull
) 0, 1},
96 /* 12 */ {SEL1(0xaaaaaaaaaaaaaaabull
) 0, 3},
97 /* 13 */ {SEL1(0x4ec4ec4ec4ec4ec5ull
) 0, 2},
98 /* 14 */ {SEL1(0x2492492492492493ull
) 1, 4},
99 /* 15 */ {SEL1(0x8888888888888889ull
) 0, 3},
100 /* 16 */ {SEL1(0ull) 1, 4},
101 /* 17 */ {SEL1(0xf0f0f0f0f0f0f0f1ull
) 0, 4},
102 /* 18 */ {SEL1(0xe38e38e38e38e38full
) 0, 4},
103 /* 19 */ {SEL1(0xd79435e50d79435full
) 0, 4},
104 /* 20 */ {SEL1(0xcccccccccccccccdull
) 0, 4},
105 /* 21 */ {SEL1(0x8618618618618619ull
) 1, 5},
106 /* 22 */ {SEL1(0x2e8ba2e8ba2e8ba3ull
) 0, 2},
107 /* 23 */ {SEL1(0x642c8590b21642c9ull
) 1, 5},
108 /* 24 */ {SEL1(0xaaaaaaaaaaaaaaabull
) 0, 4},
109 /* 25 */ {SEL1(0x47ae147ae147ae15ull
) 1, 5},
110 /* 26 */ {SEL1(0x4ec4ec4ec4ec4ec5ull
) 0, 3},
111 /* 27 */ {SEL1(0x97b425ed097b425full
) 0, 4},
112 /* 28 */ {SEL1(0x2492492492492493ull
) 1, 5},
113 /* 29 */ {SEL1(0x1a7b9611a7b9611bull
) 1, 5},
114 /* 30 */ {SEL1(0x8888888888888889ull
) 0, 4},
115 /* 31 */ {SEL1(0x0842108421084211ull
) 1, 5},
116 /* 32 */ {SEL1(0ull) 1, 5},
117 /* 33 */ {SEL1(0x0f83e0f83e0f83e1ull
) 0, 1},
118 /* 34 */ {SEL1(0xf0f0f0f0f0f0f0f1ull
) 0, 5},
119 /* 35 */ {SEL1(0xea0ea0ea0ea0ea0full
) 0, 5},
120 /* 36 */ {SEL1(0xe38e38e38e38e38full
) 0, 5}
122 # if BITS_PER_MP_LIMB == 32
123 /* 2 */ {SEL1(0ul) 1, 1, {0, 31, 0x80000000ul
SEL2(0xfffffffful
)}},
124 /* 3 */ {SEL1(0xaaaaaaabul
) 0, 1, {0, 20, 0xcfd41b91ul
SEL2(0x3b563c24ul
)}},
125 /* 4 */ {SEL1(0ul) 1, 2, {1, 15, 0x40000000ul
SEL2(0xfffffffful
)}},
126 /* 5 */ {SEL1(0xcccccccdul
) 0, 2, {1, 13, 0x48c27395ul
SEL2(0xc25c2684ul
)}},
127 /* 6 */ {SEL1(0xaaaaaaabul
) 0, 2, {0, 12, 0x81bf1000ul
SEL2(0xf91bd1b6ul
)}},
128 /* 7 */ {SEL1(0x24924925ul
) 1, 3, {1, 11, 0x75db9c97ul
SEL2(0x1607a2cbul
)}},
129 /* 8 */ {SEL1(0ul) 1, 3, {1, 10, 0x40000000ul
SEL2(0xfffffffful
)}},
130 /* 9 */ {SEL1(0x38e38e39ul
) 0, 1, {0, 10, 0xcfd41b91ul
SEL2(0x3b563c24ul
)}},
131 /* 10 */ {SEL1(0xcccccccdul
) 0, 3, {2, 9, 0x3b9aca00ul
SEL2(0x12e0be82ul
)}},
132 /* 11 */ {SEL1(0xba2e8ba3ul
) 0, 3, {0, 9, 0x8c8b6d2bul
SEL2(0xd24cde04ul
)}},
133 /* 12 */ {SEL1(0xaaaaaaabul
) 0, 3, {3, 8, 0x19a10000ul
SEL2(0x3fa39ab5ul
)}},
134 /* 13 */ {SEL1(0x4ec4ec4ful
) 0, 2, {2, 8, 0x309f1021ul
SEL2(0x50f8ac5ful
)}},
135 /* 14 */ {SEL1(0x24924925ul
) 1, 4, {1, 8, 0x57f6c100ul
SEL2(0x74843b1eul
)}},
136 /* 15 */ {SEL1(0x88888889ul
) 0, 3, {0, 8, 0x98c29b81ul
SEL2(0xad0326c2ul
)}},
137 /* 16 */ {SEL1(0ul) 1, 4, {3, 7, 0x10000000ul
SEL2(0xfffffffful
)}},
138 /* 17 */ {SEL1(0xf0f0f0f1ul
) 0, 4, {3, 7, 0x18754571ul
SEL2(0x4ef0b6bdul
)}},
139 /* 18 */ {SEL1(0x38e38e39ul
) 0, 2, {2, 7, 0x247dbc80ul
SEL2(0xc0fc48a1ul
)}},
140 /* 19 */ {SEL1(0xaf286bcbul
) 1, 5, {2, 7, 0x3547667bul
SEL2(0x33838942ul
)}},
141 /* 20 */ {SEL1(0xcccccccdul
) 0, 4, {1, 7, 0x4c4b4000ul
SEL2(0xad7f29abul
)}},
142 /* 21 */ {SEL1(0x86186187ul
) 1, 5, {1, 7, 0x6b5a6e1dul
SEL2(0x313c3d15ul
)}},
143 /* 22 */ {SEL1(0xba2e8ba3ul
) 0, 4, {0, 7, 0x94ace180ul
SEL2(0xb8cca9e0ul
)}},
144 /* 23 */ {SEL1(0xb21642c9ul
) 0, 4, {0, 7, 0xcaf18367ul
SEL2(0x42ed6de9ul
)}},
145 /* 24 */ {SEL1(0xaaaaaaabul
) 0, 4, {4, 6, 0x0b640000ul
SEL2(0x67980e0bul
)}},
146 /* 25 */ {SEL1(0x51eb851ful
) 0, 3, {4, 6, 0x0e8d4a51ul
SEL2(0x19799812ul
)}},
147 /* 26 */ {SEL1(0x4ec4ec4ful
) 0, 3, {3, 6, 0x1269ae40ul
SEL2(0xbce85396ul
)}},
148 /* 27 */ {SEL1(0x2f684bdbul
) 1, 5, {3, 6, 0x17179149ul
SEL2(0x62c103a9ul
)}},
149 /* 28 */ {SEL1(0x24924925ul
) 1, 5, {3, 6, 0x1cb91000ul
SEL2(0x1d353d43ul
)}},
150 /* 29 */ {SEL1(0x8d3dcb09ul
) 0, 4, {2, 6, 0x23744899ul
SEL2(0xce1deceaul
)}},
151 /* 30 */ {SEL1(0x88888889ul
) 0, 4, {2, 6, 0x2b73a840ul
SEL2(0x790fc511ul
)}},
152 /* 31 */ {SEL1(0x08421085ul
) 1, 5, {2, 6, 0x34e63b41ul
SEL2(0x35b865a0ul
)}},
153 /* 32 */ {SEL1(0ul) 1, 5, {1, 6, 0x40000000ul
SEL2(0xfffffffful
)}},
154 /* 33 */ {SEL1(0x3e0f83e1ul
) 0, 3, {1, 6, 0x4cfa3cc1ul
SEL2(0xa9aed1b3ul
)}},
155 /* 34 */ {SEL1(0xf0f0f0f1ul
) 0, 5, {1, 6, 0x5c13d840ul
SEL2(0x63dfc229ul
)}},
156 /* 35 */ {SEL1(0xd41d41d5ul
) 1, 6, {1, 6, 0x6d91b519ul
SEL2(0x2b0fee30ul
)}},
157 /* 36 */ {SEL1(0x38e38e39ul
) 0, 3, {0, 6, 0x81bf1000ul
SEL2(0xf91bd1b6ul
)}}
163 _itoa_word (_ITOA_WORD_TYPE value
, char *buflim
,
164 unsigned int base
, int upper_case
)
166 const char *digits
= (upper_case
168 : _itoa_lower_digits
);
172 #define SPECIAL(Base) \
175 *--buflim = digits[value % Base]; \
176 while ((value /= Base) != 0); \
184 *--buflim
= digits
[value
% base
];
185 while ((value
/= base
) != 0);
194 _itoa (unsigned long long int value
, char *buflim
, unsigned int base
,
197 const char *digits
= (upper_case
199 : _itoa_lower_digits
);
200 const struct base_table_t
*brec
= &_itoa_base_table
[base
- 2];
204 # define RUN_2N(BITS) \
207 /* `unsigned long long int' always has 64 bits. */ \
208 mp_limb_t work_hi = value >> (64 - BITS_PER_MP_LIMB); \
210 if (BITS_PER_MP_LIMB == 32) \
217 work_lo = value & 0xfffffffful; \
218 for (cnt = BITS_PER_MP_LIMB / BITS; cnt > 0; --cnt) \
220 *--buflim = digits[work_lo & ((1ul << BITS) - 1)]; \
223 if (BITS_PER_MP_LIMB % BITS != 0) \
227 & ((1 << (BITS - BITS_PER_MP_LIMB%BITS)) \
229 << BITS_PER_MP_LIMB % BITS); \
230 work_hi >>= BITS - BITS_PER_MP_LIMB % BITS; \
234 *--buflim = digits[work_lo]; \
238 work_hi = value & 0xfffffffful; \
242 *--buflim = digits[work_hi & ((1 << BITS) - 1)]; \
245 while (work_hi != 0); \
258 char *bufend
= buflim
;
259 # if BITS_PER_MP_LIMB == 64
260 mp_limb_t base_multiplier
= brec
->base_multiplier
;
264 mp_limb_t quo
, rem
, x
;
265 mp_limb_t dummy
__attribute__ ((unused
));
267 umul_ppmm (x
, dummy
, value
, base_multiplier
);
268 quo
= (x
+ ((value
- x
) >> 1)) >> (brec
->post_shift
- 1);
269 rem
= value
- quo
* base
;
270 *--buflim
= digits
[rem
];
276 mp_limb_t quo
, rem
, x
;
277 mp_limb_t dummy
__attribute__ ((unused
));
279 umul_ppmm (x
, dummy
, value
, base_multiplier
);
280 quo
= x
>> brec
->post_shift
;
281 rem
= value
- quo
* base
;
282 *--buflim
= digits
[rem
];
286 # if BITS_PER_MP_LIMB == 32
290 /* First convert x0 to 1-3 words in base s->big.base.
291 Optimize for frequent cases of 32 bit numbers. */
292 if ((mp_limb_t
) (value
>> 32) >= 1)
294 # if UDIV_TIME > 2 * UMUL_TIME || UDIV_NEEDS_NORMALIZATION
295 int big_normalization_steps
= brec
->big
.normalization_steps
;
296 mp_limb_t big_base_norm
297 = brec
->big
.base
<< big_normalization_steps
;
299 if ((mp_limb_t
) (value
>> 32) >= brec
->big
.base
)
301 mp_limb_t x1hi
, x1lo
, r
;
302 /* If you want to optimize this, take advantage of
303 that the quotient in the first udiv_qrnnd will
304 always be very small. It might be faster just to
305 subtract in a tight loop. */
307 # if UDIV_TIME > 2 * UMUL_TIME
310 if (big_normalization_steps
== 0)
313 xh
= (mp_limb_t
) (value
>> (64 - big_normalization_steps
));
314 xl
= (mp_limb_t
) (value
>> (32 - big_normalization_steps
));
315 udiv_qrnnd_preinv (x1hi
, r
, xh
, xl
, big_base_norm
,
316 brec
->big
.base_ninv
);
318 xl
= ((mp_limb_t
) value
) << big_normalization_steps
;
319 udiv_qrnnd_preinv (x1lo
, x
, r
, xl
, big_base_norm
,
320 brec
->big
.base_ninv
);
321 t
[2] = x
>> big_normalization_steps
;
323 if (big_normalization_steps
== 0)
326 xh
= ((x1hi
<< big_normalization_steps
)
327 | (x1lo
>> (32 - big_normalization_steps
)));
328 xl
= x1lo
<< big_normalization_steps
;
329 udiv_qrnnd_preinv (t
[0], x
, xh
, xl
, big_base_norm
,
330 brec
->big
.base_ninv
);
331 t
[1] = x
>> big_normalization_steps
;
332 # elif UDIV_NEEDS_NORMALIZATION
335 if (big_normalization_steps
== 0)
338 xh
= (mp_limb_t
) (value
>> 64 - big_normalization_steps
);
339 xl
= (mp_limb_t
) (value
>> 32 - big_normalization_steps
);
340 udiv_qrnnd (x1hi
, r
, xh
, xl
, big_base_norm
);
342 xl
= ((mp_limb_t
) value
) << big_normalization_steps
;
343 udiv_qrnnd (x1lo
, x
, r
, xl
, big_base_norm
);
344 t
[2] = x
>> big_normalization_steps
;
346 if (big_normalization_steps
== 0)
349 xh
= ((x1hi
<< big_normalization_steps
)
350 | (x1lo
>> 32 - big_normalization_steps
));
351 xl
= x1lo
<< big_normalization_steps
;
352 udiv_qrnnd (t
[0], x
, xh
, xl
, big_base_norm
);
353 t
[1] = x
>> big_normalization_steps
;
355 udiv_qrnnd (x1hi
, r
, 0, (mp_limb_t
) (value
>> 32),
357 udiv_qrnnd (x1lo
, t
[2], r
, (mp_limb_t
) value
, brec
->big
.base
);
358 udiv_qrnnd (t
[0], t
[1], x1hi
, x1lo
, brec
->big
.base
);
364 # if UDIV_TIME > 2 * UMUL_TIME
367 value
<<= brec
->big
.normalization_steps
;
368 udiv_qrnnd_preinv (t
[0], x
, (mp_limb_t
) (value
>> 32),
369 (mp_limb_t
) value
, big_base_norm
,
370 brec
->big
.base_ninv
);
371 t
[1] = x
>> brec
->big
.normalization_steps
;
372 # elif UDIV_NEEDS_NORMALIZATION
375 value
<<= big_normalization_steps
;
376 udiv_qrnnd (t
[0], x
, (mp_limb_t
) (value
>> 32),
377 (mp_limb_t
) value
, big_base_norm
);
378 t
[1] = x
>> big_normalization_steps
;
380 udiv_qrnnd (t
[0], t
[1], (mp_limb_t
) (value
>> 32),
381 (mp_limb_t
) value
, brec
->big
.base
);
392 /* Convert the 1-3 words in t[], word by word, to ASCII. */
395 mp_limb_t ti
= t
[--n
];
396 int ndig_for_this_limb
= 0;
398 # if UDIV_TIME > 2 * UMUL_TIME
399 mp_limb_t base_multiplier
= brec
->base_multiplier
;
403 mp_limb_t quo
, rem
, x
;
404 mp_limb_t dummy
__attribute__ ((unused
));
406 umul_ppmm (x
, dummy
, ti
, base_multiplier
);
407 quo
= (x
+ ((ti
- x
) >> 1)) >> (brec
->post_shift
- 1);
408 rem
= ti
- quo
* base
;
409 *--buflim
= digits
[rem
];
411 ++ndig_for_this_limb
;
416 mp_limb_t quo
, rem
, x
;
417 mp_limb_t dummy
__attribute__ ((unused
));
419 umul_ppmm (x
, dummy
, ti
, base_multiplier
);
420 quo
= x
>> brec
->post_shift
;
421 rem
= ti
- quo
* base
;
422 *--buflim
= digits
[rem
];
424 ++ndig_for_this_limb
;
433 *--buflim
= digits
[rem
];
435 ++ndig_for_this_limb
;
438 /* If this wasn't the most significant word, pad with zeros. */
440 while (ndig_for_this_limb
< brec
->big
.ndigits
)
443 ++ndig_for_this_limb
;
448 if (buflim
== bufend
)
459 _fitoa_word (_ITOA_WORD_TYPE value
, char *buf
, unsigned int base
,
462 char tmpbuf
[sizeof (value
) * 4]; /* Worst case length: base 2. */
463 char *cp
= _itoa_word (value
, tmpbuf
+ sizeof (value
) * 4, base
, upper_case
);
464 while (cp
< tmpbuf
+ sizeof (value
) * 4)
471 _fitoa (unsigned long long value
, char *buf
, unsigned int base
, int upper_case
)
473 char tmpbuf
[sizeof (value
) * 4]; /* Worst case length: base 2. */
474 char *cp
= _itoa (value
, tmpbuf
+ sizeof (value
) * 4, base
, upper_case
);
475 while (cp
< tmpbuf
+ sizeof (value
) * 4)