]>
Commit | Line | Data |
---|---|---|
d64b6ad0 | 1 | /* Internal function for converting integers to ASCII. |
765bbb24 | 2 | Copyright (C) 1994-1996,1999,2000,2002,2007 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 UD |
104 | do \ |
105 | { \ | |
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 | { | |
162 | mp_limb_t quo, rem, x, dummy; | |
163 | ||
164 | umul_ppmm (x, dummy, value, base_multiplier); | |
165 | quo = (x + ((value - x) >> 1)) >> (brec->post_shift - 1); | |
166 | rem = value - quo * base; | |
167 | *--bp = digits[rem]; | |
168 | value = quo; | |
169 | } | |
170 | else | |
171 | while (value != 0) | |
172 | { | |
173 | mp_limb_t quo, rem, x, dummy; | |
174 | ||
175 | umul_ppmm (x, dummy, value, base_multiplier); | |
176 | quo = x >> brec->post_shift; | |
177 | rem = value - quo * base; | |
178 | *--bp = digits[rem]; | |
179 | value = quo; | |
180 | } | |
765bbb24 UD |
181 | # endif |
182 | # if BITS_PER_MP_LIMB == 32 | |
d64b6ad0 UD |
183 | mp_limb_t t[3]; |
184 | int n; | |
185 | ||
186 | /* First convert x0 to 1-3 words in base s->big.base. | |
187 | Optimize for frequent cases of 32 bit numbers. */ | |
188 | if ((mp_limb_t) (value >> 32) >= 1) | |
189 | { | |
765bbb24 | 190 | # if UDIV_TIME > 2 * UMUL_TIME || UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
191 | int big_normalization_steps = brec->big.normalization_steps; |
192 | mp_limb_t big_base_norm | |
193 | = brec->big.base << big_normalization_steps; | |
765bbb24 | 194 | # endif |
d64b6ad0 UD |
195 | if ((mp_limb_t) (value >> 32) >= brec->big.base) |
196 | { | |
197 | mp_limb_t x1hi, x1lo, r; | |
198 | /* If you want to optimize this, take advantage of | |
199 | that the quotient in the first udiv_qrnnd will | |
200 | always be very small. It might be faster just to | |
201 | subtract in a tight loop. */ | |
202 | ||
765bbb24 | 203 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
204 | mp_limb_t x, xh, xl; |
205 | ||
206 | if (big_normalization_steps == 0) | |
207 | xh = 0; | |
208 | else | |
209 | xh = (mp_limb_t) (value >> (64 - big_normalization_steps)); | |
210 | xl = (mp_limb_t) (value >> (32 - big_normalization_steps)); | |
211 | udiv_qrnnd_preinv (x1hi, r, xh, xl, big_base_norm, | |
212 | brec->big.base_ninv); | |
213 | ||
214 | xl = ((mp_limb_t) value) << big_normalization_steps; | |
215 | udiv_qrnnd_preinv (x1lo, x, r, xl, big_base_norm, | |
216 | brec->big.base_ninv); | |
217 | t[2] = x >> big_normalization_steps; | |
218 | ||
219 | if (big_normalization_steps == 0) | |
220 | xh = x1hi; | |
221 | else | |
222 | xh = ((x1hi << big_normalization_steps) | |
223 | | (x1lo >> (32 - big_normalization_steps))); | |
224 | xl = x1lo << big_normalization_steps; | |
225 | udiv_qrnnd_preinv (t[0], x, xh, xl, big_base_norm, | |
226 | brec->big.base_ninv); | |
227 | t[1] = x >> big_normalization_steps; | |
765bbb24 | 228 | # elif UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
229 | mp_limb_t x, xh, xl; |
230 | ||
231 | if (big_normalization_steps == 0) | |
232 | xh = 0; | |
233 | else | |
234 | xh = (mp_limb_t) (value >> 64 - big_normalization_steps); | |
235 | xl = (mp_limb_t) (value >> 32 - big_normalization_steps); | |
236 | udiv_qrnnd (x1hi, r, xh, xl, big_base_norm); | |
237 | ||
238 | xl = ((mp_limb_t) value) << big_normalization_steps; | |
239 | udiv_qrnnd (x1lo, x, r, xl, big_base_norm); | |
240 | t[2] = x >> big_normalization_steps; | |
241 | ||
242 | if (big_normalization_steps == 0) | |
243 | xh = x1hi; | |
244 | else | |
245 | xh = ((x1hi << big_normalization_steps) | |
246 | | (x1lo >> 32 - big_normalization_steps)); | |
247 | xl = x1lo << big_normalization_steps; | |
248 | udiv_qrnnd (t[0], x, xh, xl, big_base_norm); | |
249 | t[1] = x >> big_normalization_steps; | |
765bbb24 | 250 | # else |
d64b6ad0 UD |
251 | udiv_qrnnd (x1hi, r, 0, (mp_limb_t) (value >> 32), |
252 | brec->big.base); | |
253 | udiv_qrnnd (x1lo, t[2], r, (mp_limb_t) value, brec->big.base); | |
254 | udiv_qrnnd (t[0], t[1], x1hi, x1lo, brec->big.base); | |
765bbb24 | 255 | # endif |
d64b6ad0 UD |
256 | n = 3; |
257 | } | |
258 | else | |
259 | { | |
765bbb24 | 260 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
261 | mp_limb_t x; |
262 | ||
263 | value <<= brec->big.normalization_steps; | |
264 | udiv_qrnnd_preinv (t[0], x, (mp_limb_t) (value >> 32), | |
265 | (mp_limb_t) value, big_base_norm, | |
266 | brec->big.base_ninv); | |
267 | t[1] = x >> brec->big.normalization_steps; | |
765bbb24 | 268 | # elif UDIV_NEEDS_NORMALIZATION |
d64b6ad0 UD |
269 | mp_limb_t x; |
270 | ||
271 | value <<= big_normalization_steps; | |
272 | udiv_qrnnd (t[0], x, (mp_limb_t) (value >> 32), | |
273 | (mp_limb_t) value, big_base_norm); | |
274 | t[1] = x >> big_normalization_steps; | |
765bbb24 | 275 | # else |
d64b6ad0 UD |
276 | udiv_qrnnd (t[0], t[1], (mp_limb_t) (value >> 32), |
277 | (mp_limb_t) value, brec->big.base); | |
765bbb24 | 278 | # endif |
d64b6ad0 UD |
279 | n = 2; |
280 | } | |
281 | } | |
282 | else | |
283 | { | |
284 | t[0] = value; | |
285 | n = 1; | |
286 | } | |
287 | ||
288 | /* Convert the 1-3 words in t[], word by word, to ASCII. */ | |
289 | do | |
290 | { | |
291 | mp_limb_t ti = t[--n]; | |
292 | int ndig_for_this_limb = 0; | |
293 | ||
765bbb24 | 294 | # if UDIV_TIME > 2 * UMUL_TIME |
d64b6ad0 UD |
295 | mp_limb_t base_multiplier = brec->base_multiplier; |
296 | if (brec->flag) | |
297 | while (ti != 0) | |
298 | { | |
299 | mp_limb_t quo, rem, x, dummy; | |
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 | { | |
311 | mp_limb_t quo, rem, x, dummy; | |
312 | ||
313 | umul_ppmm (x, dummy, ti, base_multiplier); | |
314 | quo = x >> brec->post_shift; | |
315 | rem = ti - quo * base; | |
316 | *--bp = digits[rem]; | |
317 | ti = quo; | |
318 | ++ndig_for_this_limb; | |
319 | } | |
765bbb24 | 320 | # else |
d64b6ad0 UD |
321 | while (ti != 0) |
322 | { | |
323 | mp_limb_t quo, rem; | |
324 | ||
325 | quo = ti / base; | |
326 | rem = ti % base; | |
327 | *--bp = digits[rem]; | |
328 | ti = quo; | |
329 | ++ndig_for_this_limb; | |
330 | } | |
765bbb24 | 331 | # endif |
d64b6ad0 UD |
332 | /* If this wasn't the most significant word, pad with zeros. */ |
333 | if (n != 0) | |
334 | while (ndig_for_this_limb < brec->big.ndigits) | |
335 | { | |
336 | *--bp = '0'; | |
337 | ++ndig_for_this_limb; | |
338 | } | |
339 | } | |
340 | while (n != 0); | |
765bbb24 | 341 | # endif |
d64b6ad0 UD |
342 | } |
343 | break; | |
344 | } | |
345 | ||
346 | return bp; | |
347 | } | |
765bbb24 | 348 | #endif |