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