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