]>
Commit | Line | Data |
---|---|---|
d64b6ad0 | 1 | /* Internal function for converting integers to ASCII. |
b168057a | 2 | Copyright (C) 1994-2015 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 PE |
18 | License along with the GNU C Library; if not, see |
19 | <http://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 UD |
89 | wchar_t * |
90 | _itowa (value, buflim, base, upper_case) | |
91 | unsigned long long int value; | |
92 | wchar_t *buflim; | |
93 | unsigned int base; | |
94 | int upper_case; | |
95 | { | |
96 | const wchar_t *digits = (upper_case | |
97 | ? _itowa_upper_digits : _itowa_lower_digits); | |
98 | wchar_t *bp = buflim; | |
99 | const struct base_table_t *brec = &_itoa_base_table[base - 2]; | |
100 | ||
101 | switch (base) | |
102 | { | |
765bbb24 | 103 | # define RUN_2N(BITS) \ |
d64b6ad0 | 104 | do \ |
db1ee0a8 | 105 | { \ |
d64b6ad0 UD |
106 | /* `unsigned long long int' always has 64 bits. */ \ |
107 | mp_limb_t work_hi = value >> (64 - BITS_PER_MP_LIMB); \ | |
108 | \ | |
109 | if (BITS_PER_MP_LIMB == 32) \ | |
110 | { \ | |
111 | if (work_hi != 0) \ | |
112 | { \ | |
113 | mp_limb_t work_lo; \ | |
114 | int cnt; \ | |
115 | \ | |
116 | work_lo = value & 0xfffffffful; \ | |
117 | for (cnt = BITS_PER_MP_LIMB / BITS; cnt > 0; --cnt) \ | |
118 | { \ | |
119 | *--bp = digits[work_lo & ((1ul << BITS) - 1)]; \ | |
120 | work_lo >>= BITS; \ | |
121 | } \ | |
122 | if (BITS_PER_MP_LIMB % BITS != 0) \ | |
123 | { \ | |
124 | work_lo \ | |
125 | |= ((work_hi \ | |
126 | & ((1 << (BITS - BITS_PER_MP_LIMB%BITS)) \ | |
127 | - 1)) \ | |
128 | << BITS_PER_MP_LIMB % BITS); \ | |
129 | work_hi >>= BITS - BITS_PER_MP_LIMB % BITS; \ | |
130 | if (work_hi == 0) \ | |
131 | work_hi = work_lo; \ | |
132 | else \ | |
133 | *--bp = digits[work_lo]; \ | |
134 | } \ | |
135 | } \ | |
136 | else \ | |
137 | work_hi = value & 0xfffffffful; \ | |
138 | } \ | |
139 | do \ | |
140 | { \ | |
141 | *--bp = digits[work_hi & ((1 << BITS) - 1)]; \ | |
142 | work_hi >>= BITS; \ | |
143 | } \ | |
144 | while (work_hi != 0); \ | |
145 | } \ | |
146 | while (0) | |
147 | case 8: | |
148 | RUN_2N (3); | |
149 | break; | |
150 | ||
151 | case 16: | |
152 | RUN_2N (4); | |
153 | break; | |
154 | ||
155 | default: | |
156 | { | |
765bbb24 | 157 | # if BITS_PER_MP_LIMB == 64 |
d64b6ad0 UD |
158 | mp_limb_t base_multiplier = brec->base_multiplier; |
159 | if (brec->flag) | |
160 | while (value != 0) | |
161 | { | |
be14d48f JM |
162 | mp_limb_t quo, rem, x; |
163 | mp_limb_t dummy __attribute__ ((unused)); | |
d64b6ad0 UD |
164 | |
165 | umul_ppmm (x, dummy, value, base_multiplier); | |
166 | quo = (x + ((value - x) >> 1)) >> (brec->post_shift - 1); | |
167 | rem = value - quo * base; | |
168 | *--bp = digits[rem]; | |
169 | value = quo; | |
170 | } | |
171 | else | |
172 | while (value != 0) | |
173 | { | |
be14d48f JM |
174 | mp_limb_t quo, rem, x; |
175 | mp_limb_t dummy __attribute__ ((unused)); | |
d64b6ad0 UD |
176 | |
177 | umul_ppmm (x, dummy, value, base_multiplier); | |
178 | quo = x >> brec->post_shift; | |
179 | rem = value - quo * base; | |
180 | *--bp = digits[rem]; | |
181 | value = quo; | |
182 | } | |
765bbb24 UD |
183 | # endif |
184 | # if BITS_PER_MP_LIMB == 32 | |
d64b6ad0 UD |
185 | mp_limb_t t[3]; |
186 | int n; | |
187 | ||
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) | |
191 | { | |
765bbb24 | 192 | # if UDIV_TIME > 2 * UMUL_TIME || UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
193 | int big_normalization_steps = brec->big.normalization_steps; |
194 | mp_limb_t big_base_norm | |
195 | = brec->big.base << big_normalization_steps; | |
765bbb24 | 196 | # endif |
d64b6ad0 UD |
197 | if ((mp_limb_t) (value >> 32) >= brec->big.base) |
198 | { | |
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. */ | |
204 | ||
765bbb24 | 205 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
206 | mp_limb_t x, xh, xl; |
207 | ||
208 | if (big_normalization_steps == 0) | |
209 | xh = 0; | |
210 | else | |
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); | |
215 | ||
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; | |
220 | ||
221 | if (big_normalization_steps == 0) | |
222 | xh = x1hi; | |
223 | else | |
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; | |
765bbb24 | 230 | # elif UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
231 | mp_limb_t x, xh, xl; |
232 | ||
233 | if (big_normalization_steps == 0) | |
234 | xh = 0; | |
235 | else | |
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); | |
239 | ||
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; | |
243 | ||
244 | if (big_normalization_steps == 0) | |
245 | xh = x1hi; | |
246 | else | |
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; | |
765bbb24 | 252 | # else |
d64b6ad0 UD |
253 | udiv_qrnnd (x1hi, r, 0, (mp_limb_t) (value >> 32), |
254 | brec->big.base); | |
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); | |
765bbb24 | 257 | # endif |
d64b6ad0 UD |
258 | n = 3; |
259 | } | |
260 | else | |
261 | { | |
765bbb24 | 262 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
263 | mp_limb_t x; |
264 | ||
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; | |
765bbb24 | 270 | # elif UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
271 | mp_limb_t x; |
272 | ||
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; | |
765bbb24 | 277 | # else |
d64b6ad0 UD |
278 | udiv_qrnnd (t[0], t[1], (mp_limb_t) (value >> 32), |
279 | (mp_limb_t) value, brec->big.base); | |
765bbb24 | 280 | # endif |
d64b6ad0 UD |
281 | n = 2; |
282 | } | |
283 | } | |
284 | else | |
285 | { | |
286 | t[0] = value; | |
287 | n = 1; | |
288 | } | |
289 | ||
290 | /* Convert the 1-3 words in t[], word by word, to ASCII. */ | |
291 | do | |
292 | { | |
293 | mp_limb_t ti = t[--n]; | |
294 | int ndig_for_this_limb = 0; | |
295 | ||
765bbb24 | 296 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
297 | mp_limb_t base_multiplier = brec->base_multiplier; |
298 | if (brec->flag) | |
299 | while (ti != 0) | |
300 | { | |
db1ee0a8 RM |
301 | mp_limb_t quo, rem, x; |
302 | mp_limb_t dummy __attribute__ ((unused)); | |
d64b6ad0 UD |
303 | |
304 | umul_ppmm (x, dummy, ti, base_multiplier); | |
305 | quo = (x + ((ti - x) >> 1)) >> (brec->post_shift - 1); | |
306 | rem = ti - quo * base; | |
307 | *--bp = digits[rem]; | |
308 | ti = quo; | |
309 | ++ndig_for_this_limb; | |
310 | } | |
311 | else | |
312 | while (ti != 0) | |
313 | { | |
db1ee0a8 RM |
314 | mp_limb_t quo, rem, x; |
315 | mp_limb_t dummy __attribute__ ((unused)); | |
d64b6ad0 UD |
316 | |
317 | umul_ppmm (x, dummy, ti, base_multiplier); | |
318 | quo = x >> brec->post_shift; | |
319 | rem = ti - quo * base; | |
320 | *--bp = digits[rem]; | |
321 | ti = quo; | |
322 | ++ndig_for_this_limb; | |
323 | } | |
765bbb24 | 324 | # else |
d64b6ad0 UD |
325 | while (ti != 0) |
326 | { | |
327 | mp_limb_t quo, rem; | |
328 | ||
329 | quo = ti / base; | |
330 | rem = ti % base; | |
331 | *--bp = digits[rem]; | |
332 | ti = quo; | |
333 | ++ndig_for_this_limb; | |
334 | } | |
765bbb24 | 335 | # endif |
d64b6ad0 UD |
336 | /* If this wasn't the most significant word, pad with zeros. */ |
337 | if (n != 0) | |
338 | while (ndig_for_this_limb < brec->big.ndigits) | |
339 | { | |
340 | *--bp = '0'; | |
341 | ++ndig_for_this_limb; | |
342 | } | |
343 | } | |
344 | while (n != 0); | |
765bbb24 | 345 | # endif |
d64b6ad0 UD |
346 | } |
347 | break; | |
348 | } | |
349 | ||
350 | return bp; | |
351 | } | |
765bbb24 | 352 | #endif |