]>
Commit | Line | Data |
---|---|---|
d64b6ad0 | 1 | /* Internal function for converting integers to ASCII. |
581c785b | 2 | Copyright (C) 1994-2022 Free Software Foundation, Inc. |
d64b6ad0 | 3 | This file is part of the GNU C Library. |
d64b6ad0 UD |
4 | |
5 | The GNU C Library is free software; you can redistribute it and/or | |
41bdb6e2 AJ |
6 | modify it under the terms of the GNU Lesser General Public |
7 | License as published by the Free Software Foundation; either | |
8 | version 2.1 of the License, or (at your option) any later version. | |
d64b6ad0 UD |
9 | |
10 | The GNU C Library is distributed in the hope that it will be useful, | |
11 | but WITHOUT ANY WARRANTY; without even the implied warranty of | |
12 | MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU | |
41bdb6e2 | 13 | Lesser General Public License for more details. |
d64b6ad0 | 14 | |
41bdb6e2 | 15 | You should have received a copy of the GNU Lesser General Public |
59ba27a6 | 16 | License along with the GNU C Library; if not, see |
5a82c748 | 17 | <https://www.gnu.org/licenses/>. */ |
d64b6ad0 UD |
18 | |
19 | #include <gmp-mparam.h> | |
48896b9d | 20 | #include <gmp.h> |
c1f0486a | 21 | #include <limits.h> |
d64b6ad0 UD |
22 | #include <stdlib/gmp-impl.h> |
23 | #include <stdlib/longlong.h> | |
24 | ||
eb96ffb0 | 25 | #include <_itowa.h> |
d64b6ad0 UD |
26 | |
27 | ||
28 | /* Canonize environment. For some architectures not all values might | |
29 | be defined in the GMP header files. */ | |
30 | #ifndef UMUL_TIME | |
31 | # define UMUL_TIME 1 | |
32 | #endif | |
33 | #ifndef UDIV_TIME | |
34 | # define UDIV_TIME 3 | |
35 | #endif | |
36 | ||
37 | /* Control memory layout. */ | |
38 | #ifdef PACK | |
39 | # undef PACK | |
40 | # define PACK __attribute__ ((packed)) | |
41 | #else | |
42 | # define PACK | |
43 | #endif | |
44 | ||
45 | ||
46 | /* Declare local types. */ | |
47 | struct base_table_t | |
48 | { | |
49 | #if (UDIV_TIME > 2 * UMUL_TIME) | |
50 | mp_limb_t base_multiplier; | |
51 | #endif | |
52 | char flag; | |
53 | char post_shift; | |
54 | #if BITS_PER_MP_LIMB == 32 | |
55 | struct | |
56 | { | |
57 | char normalization_steps; | |
58 | char ndigits; | |
59 | mp_limb_t base PACK; | |
60 | #if UDIV_TIME > 2 * UMUL_TIME | |
61 | mp_limb_t base_ninv PACK; | |
62 | #endif | |
63 | } big; | |
64 | #endif | |
65 | }; | |
66 | ||
67 | /* To reduce the memory needed we include some fields of the tables | |
68 | only conditionally. */ | |
69 | #if UDIV_TIME > 2 * UMUL_TIME | |
70 | # define SEL1(X) X, | |
71 | # define SEL2(X) ,X | |
72 | #else | |
73 | # define SEL1(X) | |
74 | # define SEL2(X) | |
75 | #endif | |
76 | ||
77 | /* Factor table for the different bases. */ | |
aa32f798 | 78 | extern const struct base_table_t _itoa_base_table[] attribute_hidden; |
d64b6ad0 UD |
79 | |
80 | /* Lower-case digits. */ | |
aa32f798 | 81 | extern const wchar_t _itowa_lower_digits[] attribute_hidden; |
d64b6ad0 | 82 | /* Upper-case digits. */ |
aa32f798 | 83 | extern const wchar_t _itowa_upper_digits[] attribute_hidden; |
d64b6ad0 UD |
84 | |
85 | ||
8e95c99a | 86 | #if _ITOA_NEEDED |
d64b6ad0 | 87 | wchar_t * |
f63f2bfd JM |
88 | _itowa (unsigned long long int value, wchar_t *buflim, unsigned int base, |
89 | int upper_case) | |
d64b6ad0 UD |
90 | { |
91 | const wchar_t *digits = (upper_case | |
92 | ? _itowa_upper_digits : _itowa_lower_digits); | |
93 | wchar_t *bp = buflim; | |
94 | const struct base_table_t *brec = &_itoa_base_table[base - 2]; | |
95 | ||
96 | switch (base) | |
97 | { | |
765bbb24 | 98 | # define RUN_2N(BITS) \ |
d64b6ad0 | 99 | do \ |
db1ee0a8 | 100 | { \ |
d64b6ad0 UD |
101 | /* `unsigned long long int' always has 64 bits. */ \ |
102 | mp_limb_t work_hi = value >> (64 - BITS_PER_MP_LIMB); \ | |
103 | \ | |
104 | if (BITS_PER_MP_LIMB == 32) \ | |
105 | { \ | |
106 | if (work_hi != 0) \ | |
107 | { \ | |
108 | mp_limb_t work_lo; \ | |
109 | int cnt; \ | |
110 | \ | |
111 | work_lo = value & 0xfffffffful; \ | |
112 | for (cnt = BITS_PER_MP_LIMB / BITS; cnt > 0; --cnt) \ | |
113 | { \ | |
114 | *--bp = digits[work_lo & ((1ul << BITS) - 1)]; \ | |
115 | work_lo >>= BITS; \ | |
116 | } \ | |
117 | if (BITS_PER_MP_LIMB % BITS != 0) \ | |
118 | { \ | |
119 | work_lo \ | |
120 | |= ((work_hi \ | |
121 | & ((1 << (BITS - BITS_PER_MP_LIMB%BITS)) \ | |
122 | - 1)) \ | |
123 | << BITS_PER_MP_LIMB % BITS); \ | |
124 | work_hi >>= BITS - BITS_PER_MP_LIMB % BITS; \ | |
125 | if (work_hi == 0) \ | |
126 | work_hi = work_lo; \ | |
127 | else \ | |
128 | *--bp = digits[work_lo]; \ | |
129 | } \ | |
130 | } \ | |
131 | else \ | |
132 | work_hi = value & 0xfffffffful; \ | |
133 | } \ | |
134 | do \ | |
135 | { \ | |
136 | *--bp = digits[work_hi & ((1 << BITS) - 1)]; \ | |
137 | work_hi >>= BITS; \ | |
138 | } \ | |
139 | while (work_hi != 0); \ | |
140 | } \ | |
141 | while (0) | |
142 | case 8: | |
143 | RUN_2N (3); | |
144 | break; | |
145 | ||
146 | case 16: | |
147 | RUN_2N (4); | |
148 | break; | |
149 | ||
150 | default: | |
151 | { | |
765bbb24 | 152 | # if BITS_PER_MP_LIMB == 64 |
d64b6ad0 UD |
153 | mp_limb_t base_multiplier = brec->base_multiplier; |
154 | if (brec->flag) | |
155 | while (value != 0) | |
156 | { | |
be14d48f JM |
157 | mp_limb_t quo, rem, x; |
158 | mp_limb_t dummy __attribute__ ((unused)); | |
d64b6ad0 UD |
159 | |
160 | umul_ppmm (x, dummy, value, base_multiplier); | |
161 | quo = (x + ((value - x) >> 1)) >> (brec->post_shift - 1); | |
162 | rem = value - quo * base; | |
163 | *--bp = digits[rem]; | |
164 | value = quo; | |
165 | } | |
166 | else | |
167 | while (value != 0) | |
168 | { | |
be14d48f JM |
169 | mp_limb_t quo, rem, x; |
170 | mp_limb_t dummy __attribute__ ((unused)); | |
d64b6ad0 UD |
171 | |
172 | umul_ppmm (x, dummy, value, base_multiplier); | |
173 | quo = x >> brec->post_shift; | |
174 | rem = value - quo * base; | |
175 | *--bp = digits[rem]; | |
176 | value = quo; | |
177 | } | |
765bbb24 UD |
178 | # endif |
179 | # if BITS_PER_MP_LIMB == 32 | |
d64b6ad0 UD |
180 | mp_limb_t t[3]; |
181 | int n; | |
182 | ||
183 | /* First convert x0 to 1-3 words in base s->big.base. | |
184 | Optimize for frequent cases of 32 bit numbers. */ | |
185 | if ((mp_limb_t) (value >> 32) >= 1) | |
186 | { | |
765bbb24 | 187 | # if UDIV_TIME > 2 * UMUL_TIME || UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
188 | int big_normalization_steps = brec->big.normalization_steps; |
189 | mp_limb_t big_base_norm | |
190 | = brec->big.base << big_normalization_steps; | |
765bbb24 | 191 | # endif |
d64b6ad0 UD |
192 | if ((mp_limb_t) (value >> 32) >= brec->big.base) |
193 | { | |
194 | mp_limb_t x1hi, x1lo, r; | |
195 | /* If you want to optimize this, take advantage of | |
196 | that the quotient in the first udiv_qrnnd will | |
197 | always be very small. It might be faster just to | |
198 | subtract in a tight loop. */ | |
199 | ||
765bbb24 | 200 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
201 | mp_limb_t x, xh, xl; |
202 | ||
203 | if (big_normalization_steps == 0) | |
204 | xh = 0; | |
205 | else | |
206 | xh = (mp_limb_t) (value >> (64 - big_normalization_steps)); | |
207 | xl = (mp_limb_t) (value >> (32 - big_normalization_steps)); | |
208 | udiv_qrnnd_preinv (x1hi, r, xh, xl, big_base_norm, | |
209 | brec->big.base_ninv); | |
210 | ||
211 | xl = ((mp_limb_t) value) << big_normalization_steps; | |
212 | udiv_qrnnd_preinv (x1lo, x, r, xl, big_base_norm, | |
213 | brec->big.base_ninv); | |
214 | t[2] = x >> big_normalization_steps; | |
215 | ||
216 | if (big_normalization_steps == 0) | |
217 | xh = x1hi; | |
218 | else | |
219 | xh = ((x1hi << big_normalization_steps) | |
220 | | (x1lo >> (32 - big_normalization_steps))); | |
221 | xl = x1lo << big_normalization_steps; | |
222 | udiv_qrnnd_preinv (t[0], x, xh, xl, big_base_norm, | |
223 | brec->big.base_ninv); | |
224 | t[1] = x >> big_normalization_steps; | |
765bbb24 | 225 | # elif UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
226 | mp_limb_t x, xh, xl; |
227 | ||
228 | if (big_normalization_steps == 0) | |
229 | xh = 0; | |
230 | else | |
231 | xh = (mp_limb_t) (value >> 64 - big_normalization_steps); | |
232 | xl = (mp_limb_t) (value >> 32 - big_normalization_steps); | |
233 | udiv_qrnnd (x1hi, r, xh, xl, big_base_norm); | |
234 | ||
235 | xl = ((mp_limb_t) value) << big_normalization_steps; | |
236 | udiv_qrnnd (x1lo, x, r, xl, big_base_norm); | |
237 | t[2] = x >> big_normalization_steps; | |
238 | ||
239 | if (big_normalization_steps == 0) | |
240 | xh = x1hi; | |
241 | else | |
242 | xh = ((x1hi << big_normalization_steps) | |
243 | | (x1lo >> 32 - big_normalization_steps)); | |
244 | xl = x1lo << big_normalization_steps; | |
245 | udiv_qrnnd (t[0], x, xh, xl, big_base_norm); | |
246 | t[1] = x >> big_normalization_steps; | |
765bbb24 | 247 | # else |
d64b6ad0 UD |
248 | udiv_qrnnd (x1hi, r, 0, (mp_limb_t) (value >> 32), |
249 | brec->big.base); | |
250 | udiv_qrnnd (x1lo, t[2], r, (mp_limb_t) value, brec->big.base); | |
251 | udiv_qrnnd (t[0], t[1], x1hi, x1lo, brec->big.base); | |
765bbb24 | 252 | # endif |
d64b6ad0 UD |
253 | n = 3; |
254 | } | |
255 | else | |
256 | { | |
765bbb24 | 257 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
258 | mp_limb_t x; |
259 | ||
260 | value <<= brec->big.normalization_steps; | |
261 | udiv_qrnnd_preinv (t[0], x, (mp_limb_t) (value >> 32), | |
262 | (mp_limb_t) value, big_base_norm, | |
263 | brec->big.base_ninv); | |
264 | t[1] = x >> brec->big.normalization_steps; | |
765bbb24 | 265 | # elif UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
266 | mp_limb_t x; |
267 | ||
268 | value <<= big_normalization_steps; | |
269 | udiv_qrnnd (t[0], x, (mp_limb_t) (value >> 32), | |
270 | (mp_limb_t) value, big_base_norm); | |
271 | t[1] = x >> big_normalization_steps; | |
765bbb24 | 272 | # else |
d64b6ad0 UD |
273 | udiv_qrnnd (t[0], t[1], (mp_limb_t) (value >> 32), |
274 | (mp_limb_t) value, brec->big.base); | |
765bbb24 | 275 | # endif |
d64b6ad0 UD |
276 | n = 2; |
277 | } | |
278 | } | |
279 | else | |
280 | { | |
281 | t[0] = value; | |
282 | n = 1; | |
283 | } | |
284 | ||
285 | /* Convert the 1-3 words in t[], word by word, to ASCII. */ | |
286 | do | |
287 | { | |
288 | mp_limb_t ti = t[--n]; | |
289 | int ndig_for_this_limb = 0; | |
290 | ||
765bbb24 | 291 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
292 | mp_limb_t base_multiplier = brec->base_multiplier; |
293 | if (brec->flag) | |
294 | while (ti != 0) | |
295 | { | |
db1ee0a8 RM |
296 | mp_limb_t quo, rem, x; |
297 | mp_limb_t dummy __attribute__ ((unused)); | |
d64b6ad0 UD |
298 | |
299 | umul_ppmm (x, dummy, ti, base_multiplier); | |
300 | quo = (x + ((ti - x) >> 1)) >> (brec->post_shift - 1); | |
301 | rem = ti - quo * base; | |
302 | *--bp = digits[rem]; | |
303 | ti = quo; | |
304 | ++ndig_for_this_limb; | |
305 | } | |
306 | else | |
307 | while (ti != 0) | |
308 | { | |
db1ee0a8 RM |
309 | mp_limb_t quo, rem, x; |
310 | mp_limb_t dummy __attribute__ ((unused)); | |
d64b6ad0 UD |
311 | |
312 | umul_ppmm (x, dummy, ti, base_multiplier); | |
313 | quo = x >> brec->post_shift; | |
314 | rem = ti - quo * base; | |
315 | *--bp = digits[rem]; | |
316 | ti = quo; | |
317 | ++ndig_for_this_limb; | |
318 | } | |
765bbb24 | 319 | # else |
d64b6ad0 UD |
320 | while (ti != 0) |
321 | { | |
322 | mp_limb_t quo, rem; | |
323 | ||
324 | quo = ti / base; | |
325 | rem = ti % base; | |
326 | *--bp = digits[rem]; | |
327 | ti = quo; | |
328 | ++ndig_for_this_limb; | |
329 | } | |
765bbb24 | 330 | # endif |
d64b6ad0 UD |
331 | /* If this wasn't the most significant word, pad with zeros. */ |
332 | if (n != 0) | |
333 | while (ndig_for_this_limb < brec->big.ndigits) | |
334 | { | |
335 | *--bp = '0'; | |
336 | ++ndig_for_this_limb; | |
337 | } | |
338 | } | |
339 | while (n != 0); | |
765bbb24 | 340 | # endif |
d64b6ad0 UD |
341 | } |
342 | break; | |
343 | } | |
344 | ||
345 | return bp; | |
346 | } | |
765bbb24 | 347 | #endif |