Back to index

glibc  2.9
_itoa.c
Go to the documentation of this file.
00001 /* Internal function for converting integers to ASCII.
00002    Copyright (C) 1994, 1995, 1996, 1999, 2000, 2002, 2003, 2004, 2007
00003    Free Software Foundation, Inc.
00004    This file is part of the GNU C Library.
00005    Contributed by Torbjorn Granlund <tege@matematik.su.se>
00006    and Ulrich Drepper <drepper@gnu.org>.
00007 
00008    The GNU C Library is free software; you can redistribute it and/or
00009    modify it under the terms of the GNU Lesser General Public
00010    License as published by the Free Software Foundation; either
00011    version 2.1 of the License, or (at your option) any later version.
00012 
00013    The GNU C Library is distributed in the hope that it will be useful,
00014    but WITHOUT ANY WARRANTY; without even the implied warranty of
00015    MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
00016    Lesser General Public License for more details.
00017 
00018    You should have received a copy of the GNU Lesser General Public
00019    License along with the GNU C Library; if not, write to the Free
00020    Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
00021    02111-1307 USA.  */
00022 
00023 #include <gmp-mparam.h>
00024 #include <gmp.h>
00025 #include <limits.h>
00026 #include <stdlib/gmp-impl.h>
00027 #include <stdlib/longlong.h>
00028 
00029 #include "_itoa.h"
00030 
00031 
00032 /* Canonize environment.  For some architectures not all values might
00033    be defined in the GMP header files.  */
00034 #ifndef UMUL_TIME
00035 # define UMUL_TIME 1
00036 #endif
00037 #ifndef UDIV_TIME
00038 # define UDIV_TIME 3
00039 #endif
00040 
00041 /* Control memory layout.  */
00042 #ifdef PACK
00043 # undef PACK
00044 # define PACK __attribute__ ((packed))
00045 #else
00046 # define PACK
00047 #endif
00048 
00049 
00050 /* Declare local types.  */
00051 struct base_table_t
00052 {
00053 #if (UDIV_TIME > 2 * UMUL_TIME)
00054   mp_limb_t base_multiplier;
00055 #endif
00056   char flag;
00057   char post_shift;
00058 #if BITS_PER_MP_LIMB == 32
00059   struct
00060     {
00061       char normalization_steps;
00062       char ndigits;
00063       mp_limb_t base PACK;
00064 #if UDIV_TIME > 2 * UMUL_TIME
00065       mp_limb_t base_ninv PACK;
00066 #endif
00067     } big;
00068 #endif
00069 };
00070 
00071 /* To reduce the memory needed we include some fields of the tables
00072    only conditionally.  */
00073 #if UDIV_TIME > 2 * UMUL_TIME
00074 # define SEL1(X) X,
00075 # define SEL2(X) ,X
00076 #else
00077 # define SEL1(X)
00078 # define SEL2(X)
00079 #endif
00080 
00081 
00082 /* We do not compile _itoa if we always can use _itoa_word.  */
00083 #if LLONG_MAX != LONG_MAX
00084 /* Local variables.  */
00085 const struct base_table_t _itoa_base_table[] attribute_hidden =
00086 {
00087 # if BITS_PER_MP_LIMB == 64
00088   /*  2 */ {SEL1(0ull) 1, 1},
00089   /*  3 */ {SEL1(0xaaaaaaaaaaaaaaabull) 0, 1},
00090   /*  4 */ {SEL1(0ull) 1, 2},
00091   /*  5 */ {SEL1(0xcccccccccccccccdull) 0, 2},
00092   /*  6 */ {SEL1(0xaaaaaaaaaaaaaaabull) 0, 2},
00093   /*  7 */ {SEL1(0x2492492492492493ull) 1, 3},
00094   /*  8 */ {SEL1(0ull) 1, 3},
00095   /*  9 */ {SEL1(0xe38e38e38e38e38full) 0, 3},
00096   /* 10 */ {SEL1(0xcccccccccccccccdull) 0, 3},
00097   /* 11 */ {SEL1(0x2e8ba2e8ba2e8ba3ull) 0, 1},
00098   /* 12 */ {SEL1(0xaaaaaaaaaaaaaaabull) 0, 3},
00099   /* 13 */ {SEL1(0x4ec4ec4ec4ec4ec5ull) 0, 2},
00100   /* 14 */ {SEL1(0x2492492492492493ull) 1, 4},
00101   /* 15 */ {SEL1(0x8888888888888889ull) 0, 3},
00102   /* 16 */ {SEL1(0ull) 1, 4},
00103   /* 17 */ {SEL1(0xf0f0f0f0f0f0f0f1ull) 0, 4},
00104   /* 18 */ {SEL1(0xe38e38e38e38e38full) 0, 4},
00105   /* 19 */ {SEL1(0xd79435e50d79435full) 0, 4},
00106   /* 20 */ {SEL1(0xcccccccccccccccdull) 0, 4},
00107   /* 21 */ {SEL1(0x8618618618618619ull) 1, 5},
00108   /* 22 */ {SEL1(0x2e8ba2e8ba2e8ba3ull) 0, 2},
00109   /* 23 */ {SEL1(0x642c8590b21642c9ull) 1, 5},
00110   /* 24 */ {SEL1(0xaaaaaaaaaaaaaaabull) 0, 4},
00111   /* 25 */ {SEL1(0x47ae147ae147ae15ull) 1, 5},
00112   /* 26 */ {SEL1(0x4ec4ec4ec4ec4ec5ull) 0, 3},
00113   /* 27 */ {SEL1(0x97b425ed097b425full) 0, 4},
00114   /* 28 */ {SEL1(0x2492492492492493ull) 1, 5},
00115   /* 29 */ {SEL1(0x1a7b9611a7b9611bull) 1, 5},
00116   /* 30 */ {SEL1(0x8888888888888889ull) 0, 4},
00117   /* 31 */ {SEL1(0x0842108421084211ull) 1, 5},
00118   /* 32 */ {SEL1(0ull) 1, 5},
00119   /* 33 */ {SEL1(0x0f83e0f83e0f83e1ull) 0, 1},
00120   /* 34 */ {SEL1(0xf0f0f0f0f0f0f0f1ull) 0, 5},
00121   /* 35 */ {SEL1(0xea0ea0ea0ea0ea0full) 0, 5},
00122   /* 36 */ {SEL1(0xe38e38e38e38e38full) 0, 5}
00123 # endif
00124 # if BITS_PER_MP_LIMB == 32
00125   /*  2 */ {SEL1(0ul) 1, 1, {0, 31, 0x80000000ul SEL2(0xfffffffful)}},
00126   /*  3 */ {SEL1(0xaaaaaaabul) 0, 1, {0, 20, 0xcfd41b91ul SEL2(0x3b563c24ul)}},
00127   /*  4 */ {SEL1(0ul) 1, 2, {1, 15, 0x40000000ul SEL2(0xfffffffful)}},
00128   /*  5 */ {SEL1(0xcccccccdul) 0, 2, {1, 13, 0x48c27395ul SEL2(0xc25c2684ul)}},
00129   /*  6 */ {SEL1(0xaaaaaaabul) 0, 2, {0, 12, 0x81bf1000ul SEL2(0xf91bd1b6ul)}},
00130   /*  7 */ {SEL1(0x24924925ul) 1, 3, {1, 11, 0x75db9c97ul SEL2(0x1607a2cbul)}},
00131   /*  8 */ {SEL1(0ul) 1, 3, {1, 10, 0x40000000ul SEL2(0xfffffffful)}},
00132   /*  9 */ {SEL1(0x38e38e39ul) 0, 1, {0, 10, 0xcfd41b91ul SEL2(0x3b563c24ul)}},
00133   /* 10 */ {SEL1(0xcccccccdul) 0, 3, {2, 9, 0x3b9aca00ul SEL2(0x12e0be82ul)}},
00134   /* 11 */ {SEL1(0xba2e8ba3ul) 0, 3, {0, 9, 0x8c8b6d2bul SEL2(0xd24cde04ul)}},
00135   /* 12 */ {SEL1(0xaaaaaaabul) 0, 3, {3, 8, 0x19a10000ul SEL2(0x3fa39ab5ul)}},
00136   /* 13 */ {SEL1(0x4ec4ec4ful) 0, 2, {2, 8, 0x309f1021ul SEL2(0x50f8ac5ful)}},
00137   /* 14 */ {SEL1(0x24924925ul) 1, 4, {1, 8, 0x57f6c100ul SEL2(0x74843b1eul)}},
00138   /* 15 */ {SEL1(0x88888889ul) 0, 3, {0, 8, 0x98c29b81ul SEL2(0xad0326c2ul)}},
00139   /* 16 */ {SEL1(0ul) 1, 4, {3, 7, 0x10000000ul SEL2(0xfffffffful)}},
00140   /* 17 */ {SEL1(0xf0f0f0f1ul) 0, 4, {3, 7, 0x18754571ul SEL2(0x4ef0b6bdul)}},
00141   /* 18 */ {SEL1(0x38e38e39ul) 0, 2, {2, 7, 0x247dbc80ul SEL2(0xc0fc48a1ul)}},
00142   /* 19 */ {SEL1(0xaf286bcbul) 1, 5, {2, 7, 0x3547667bul SEL2(0x33838942ul)}},
00143   /* 20 */ {SEL1(0xcccccccdul) 0, 4, {1, 7, 0x4c4b4000ul SEL2(0xad7f29abul)}},
00144   /* 21 */ {SEL1(0x86186187ul) 1, 5, {1, 7, 0x6b5a6e1dul SEL2(0x313c3d15ul)}},
00145   /* 22 */ {SEL1(0xba2e8ba3ul) 0, 4, {0, 7, 0x94ace180ul SEL2(0xb8cca9e0ul)}},
00146   /* 23 */ {SEL1(0xb21642c9ul) 0, 4, {0, 7, 0xcaf18367ul SEL2(0x42ed6de9ul)}},
00147   /* 24 */ {SEL1(0xaaaaaaabul) 0, 4, {4, 6, 0x0b640000ul SEL2(0x67980e0bul)}},
00148   /* 25 */ {SEL1(0x51eb851ful) 0, 3, {4, 6, 0x0e8d4a51ul SEL2(0x19799812ul)}},
00149   /* 26 */ {SEL1(0x4ec4ec4ful) 0, 3, {3, 6, 0x1269ae40ul SEL2(0xbce85396ul)}},
00150   /* 27 */ {SEL1(0x2f684bdbul) 1, 5, {3, 6, 0x17179149ul SEL2(0x62c103a9ul)}},
00151   /* 28 */ {SEL1(0x24924925ul) 1, 5, {3, 6, 0x1cb91000ul SEL2(0x1d353d43ul)}},
00152   /* 29 */ {SEL1(0x8d3dcb09ul) 0, 4, {2, 6, 0x23744899ul SEL2(0xce1deceaul)}},
00153   /* 30 */ {SEL1(0x88888889ul) 0, 4, {2, 6, 0x2b73a840ul SEL2(0x790fc511ul)}},
00154   /* 31 */ {SEL1(0x08421085ul) 1, 5, {2, 6, 0x34e63b41ul SEL2(0x35b865a0ul)}},
00155   /* 32 */ {SEL1(0ul) 1, 5, {1, 6, 0x40000000ul SEL2(0xfffffffful)}},
00156   /* 33 */ {SEL1(0x3e0f83e1ul) 0, 3, {1, 6, 0x4cfa3cc1ul SEL2(0xa9aed1b3ul)}},
00157   /* 34 */ {SEL1(0xf0f0f0f1ul) 0, 5, {1, 6, 0x5c13d840ul SEL2(0x63dfc229ul)}},
00158   /* 35 */ {SEL1(0xd41d41d5ul) 1, 6, {1, 6, 0x6d91b519ul SEL2(0x2b0fee30ul)}},
00159   /* 36 */ {SEL1(0x38e38e39ul) 0, 3, {0, 6, 0x81bf1000ul SEL2(0xf91bd1b6ul)}}
00160 # endif
00161 };
00162 #endif
00163 
00164 /* Lower-case digits.  */
00165 extern const char _itoa_lower_digits[];
00166 extern const char _itoa_lower_digits_internal[] attribute_hidden;
00167 /* Upper-case digits.  */
00168 extern const char _itoa_upper_digits[];
00169 extern const char _itoa_upper_digits_internal[] attribute_hidden;
00170 
00171 
00172 char *
00173 _itoa_word (unsigned long value, char *buflim,
00174            unsigned int base, int upper_case)
00175 {
00176   const char *digits = (upper_case
00177 #if !defined NOT_IN_libc || defined IS_IN_rtld
00178                      ? INTUSE(_itoa_upper_digits)
00179                      : INTUSE(_itoa_lower_digits)
00180 #else
00181                      ? _itoa_upper_digits
00182                      : _itoa_lower_digits
00183 #endif
00184                      );
00185 
00186   switch (base)
00187     {
00188 #define SPECIAL(Base)                                                       \
00189     case Base:                                                              \
00190       do                                                             \
00191        *--buflim = digits[value % Base];                             \
00192       while ((value /= Base) != 0);                                         \
00193       break
00194 
00195       SPECIAL (10);
00196       SPECIAL (16);
00197       SPECIAL (8);
00198     default:
00199       do
00200        *--buflim = digits[value % base];
00201       while ((value /= base) != 0);
00202     }
00203   return buflim;
00204 }
00205 #undef SPECIAL
00206 
00207 
00208 #if LLONG_MAX != LONG_MAX
00209 char *
00210 _itoa (value, buflim, base, upper_case)
00211      unsigned long long int value;
00212      char *buflim;
00213      unsigned int base;
00214      int upper_case;
00215 {
00216   const char *digits = (upper_case
00217                      ? INTUSE(_itoa_upper_digits)
00218                      : INTUSE(_itoa_lower_digits));
00219   const struct base_table_t *brec = &_itoa_base_table[base - 2];
00220 
00221   switch (base)
00222     {
00223 # define RUN_2N(BITS) \
00224       do                                                             \
00225         {                                                            \
00226          /* `unsigned long long int' always has 64 bits.  */                \
00227          mp_limb_t work_hi = value >> (64 - BITS_PER_MP_LIMB);              \
00228                                                                      \
00229          if (BITS_PER_MP_LIMB == 32)                                        \
00230            {                                                         \
00231              if (work_hi != 0)                                              \
00232               {                                                      \
00233                 mp_limb_t work_lo;                                   \
00234                 int cnt;                                             \
00235                                                                      \
00236                 work_lo = value & 0xfffffffful;                      \
00237                 for (cnt = BITS_PER_MP_LIMB / BITS; cnt > 0; --cnt)         \
00238                   {                                                  \
00239                     *--buflim = digits[work_lo & ((1ul << BITS) - 1)];      \
00240                     work_lo >>= BITS;                                       \
00241                   }                                                  \
00242                 if (BITS_PER_MP_LIMB % BITS != 0)                           \
00243                   {                                                  \
00244                     work_lo                                          \
00245                      |= ((work_hi                                    \
00246                           & ((1 << (BITS - BITS_PER_MP_LIMB%BITS))          \
00247                             - 1))                                    \
00248                          << BITS_PER_MP_LIMB % BITS);                \
00249                     work_hi >>= BITS - BITS_PER_MP_LIMB % BITS;             \
00250                     if (work_hi == 0)                                       \
00251                      work_hi = work_lo;                              \
00252                     else                                             \
00253                      *--buflim = digits[work_lo];                           \
00254                   }                                                  \
00255               }                                                      \
00256              else                                                    \
00257               work_hi = value & 0xfffffffful;                               \
00258            }                                                         \
00259          do                                                          \
00260            {                                                         \
00261              *--buflim = digits[work_hi & ((1 << BITS) - 1)];               \
00262              work_hi >>= BITS;                                              \
00263            }                                                         \
00264          while (work_hi != 0);                                              \
00265        }                                                             \
00266       while (0)
00267     case 8:
00268       RUN_2N (3);
00269       break;
00270 
00271     case 16:
00272       RUN_2N (4);
00273       break;
00274 
00275     default:
00276       {
00277        char *bufend = buflim;
00278 # if BITS_PER_MP_LIMB == 64
00279        mp_limb_t base_multiplier = brec->base_multiplier;
00280        if (brec->flag)
00281          while (value != 0)
00282            {
00283              mp_limb_t quo, rem, x, dummy;
00284 
00285              umul_ppmm (x, dummy, value, base_multiplier);
00286              quo = (x + ((value - x) >> 1)) >> (brec->post_shift - 1);
00287              rem = value - quo * base;
00288              *--buflim = digits[rem];
00289              value = quo;
00290            }
00291        else
00292          while (value != 0)
00293            {
00294              mp_limb_t quo, rem, x, dummy;
00295 
00296              umul_ppmm (x, dummy, value, base_multiplier);
00297              quo = x >> brec->post_shift;
00298              rem = value - quo * base;
00299              *--buflim = digits[rem];
00300              value = quo;
00301            }
00302 # endif
00303 # if BITS_PER_MP_LIMB == 32
00304        mp_limb_t t[3];
00305        int n;
00306 
00307        /* First convert x0 to 1-3 words in base s->big.base.
00308           Optimize for frequent cases of 32 bit numbers.  */
00309        if ((mp_limb_t) (value >> 32) >= 1)
00310          {
00311 #  if UDIV_TIME > 2 * UMUL_TIME || UDIV_NEEDS_NORMALIZATION
00312            int big_normalization_steps = brec->big.normalization_steps;
00313            mp_limb_t big_base_norm
00314              = brec->big.base << big_normalization_steps;
00315 #  endif
00316            if ((mp_limb_t) (value >> 32) >= brec->big.base)
00317              {
00318               mp_limb_t x1hi, x1lo, r;
00319               /* If you want to optimize this, take advantage of
00320                  that the quotient in the first udiv_qrnnd will
00321                  always be very small.  It might be faster just to
00322                  subtract in a tight loop.  */
00323 
00324 #  if UDIV_TIME > 2 * UMUL_TIME
00325               mp_limb_t x, xh, xl;
00326 
00327               if (big_normalization_steps == 0)
00328                 xh = 0;
00329               else
00330                 xh = (mp_limb_t) (value >> (64 - big_normalization_steps));
00331               xl = (mp_limb_t) (value >> (32 - big_normalization_steps));
00332               udiv_qrnnd_preinv (x1hi, r, xh, xl, big_base_norm,
00333                                brec->big.base_ninv);
00334 
00335               xl = ((mp_limb_t) value) << big_normalization_steps;
00336               udiv_qrnnd_preinv (x1lo, x, r, xl, big_base_norm,
00337                                brec->big.base_ninv);
00338               t[2] = x >> big_normalization_steps;
00339 
00340               if (big_normalization_steps == 0)
00341                 xh = x1hi;
00342               else
00343                 xh = ((x1hi << big_normalization_steps)
00344                      | (x1lo >> (32 - big_normalization_steps)));
00345               xl = x1lo << big_normalization_steps;
00346               udiv_qrnnd_preinv (t[0], x, xh, xl, big_base_norm,
00347                                brec->big.base_ninv);
00348               t[1] = x >> big_normalization_steps;
00349 #  elif UDIV_NEEDS_NORMALIZATION
00350               mp_limb_t x, xh, xl;
00351 
00352               if (big_normalization_steps == 0)
00353                 xh = 0;
00354               else
00355                 xh = (mp_limb_t) (value >> 64 - big_normalization_steps);
00356               xl = (mp_limb_t) (value >> 32 - big_normalization_steps);
00357               udiv_qrnnd (x1hi, r, xh, xl, big_base_norm);
00358 
00359               xl = ((mp_limb_t) value) << big_normalization_steps;
00360               udiv_qrnnd (x1lo, x, r, xl, big_base_norm);
00361               t[2] = x >> big_normalization_steps;
00362 
00363               if (big_normalization_steps == 0)
00364                 xh = x1hi;
00365               else
00366                 xh = ((x1hi << big_normalization_steps)
00367                      | (x1lo >> 32 - big_normalization_steps));
00368               xl = x1lo << big_normalization_steps;
00369               udiv_qrnnd (t[0], x, xh, xl, big_base_norm);
00370               t[1] = x >> big_normalization_steps;
00371 #  else
00372               udiv_qrnnd (x1hi, r, 0, (mp_limb_t) (value >> 32),
00373                          brec->big.base);
00374               udiv_qrnnd (x1lo, t[2], r, (mp_limb_t) value, brec->big.base);
00375               udiv_qrnnd (t[0], t[1], x1hi, x1lo, brec->big.base);
00376 #  endif
00377               n = 3;
00378              }
00379            else
00380              {
00381 #  if UDIV_TIME > 2 * UMUL_TIME
00382               mp_limb_t x;
00383 
00384               value <<= brec->big.normalization_steps;
00385               udiv_qrnnd_preinv (t[0], x, (mp_limb_t) (value >> 32),
00386                                (mp_limb_t) value, big_base_norm,
00387                                brec->big.base_ninv);
00388               t[1] = x >> brec->big.normalization_steps;
00389 #  elif UDIV_NEEDS_NORMALIZATION
00390               mp_limb_t x;
00391 
00392               value <<= big_normalization_steps;
00393               udiv_qrnnd (t[0], x, (mp_limb_t) (value >> 32),
00394                          (mp_limb_t) value, big_base_norm);
00395               t[1] = x >> big_normalization_steps;
00396 #  else
00397               udiv_qrnnd (t[0], t[1], (mp_limb_t) (value >> 32),
00398                          (mp_limb_t) value, brec->big.base);
00399 #  endif
00400               n = 2;
00401              }
00402          }
00403        else
00404          {
00405            t[0] = value;
00406            n = 1;
00407          }
00408 
00409        /* Convert the 1-3 words in t[], word by word, to ASCII.  */
00410        do
00411          {
00412            mp_limb_t ti = t[--n];
00413            int ndig_for_this_limb = 0;
00414 
00415 #  if UDIV_TIME > 2 * UMUL_TIME
00416            mp_limb_t base_multiplier = brec->base_multiplier;
00417            if (brec->flag)
00418              while (ti != 0)
00419               {
00420                 mp_limb_t quo, rem, x, dummy;
00421 
00422                 umul_ppmm (x, dummy, ti, base_multiplier);
00423                 quo = (x + ((ti - x) >> 1)) >> (brec->post_shift - 1);
00424                 rem = ti - quo * base;
00425                 *--buflim = digits[rem];
00426                 ti = quo;
00427                 ++ndig_for_this_limb;
00428               }
00429            else
00430              while (ti != 0)
00431               {
00432                 mp_limb_t quo, rem, x, dummy;
00433 
00434                 umul_ppmm (x, dummy, ti, base_multiplier);
00435                 quo = x >> brec->post_shift;
00436                 rem = ti - quo * base;
00437                 *--buflim = digits[rem];
00438                 ti = quo;
00439                 ++ndig_for_this_limb;
00440               }
00441 #  else
00442            while (ti != 0)
00443              {
00444               mp_limb_t quo, rem;
00445 
00446               quo = ti / base;
00447               rem = ti % base;
00448               *--buflim = digits[rem];
00449               ti = quo;
00450               ++ndig_for_this_limb;
00451              }
00452 #  endif
00453            /* If this wasn't the most significant word, pad with zeros.  */
00454            if (n != 0)
00455              while (ndig_for_this_limb < brec->big.ndigits)
00456               {
00457                 *--buflim = '0';
00458                 ++ndig_for_this_limb;
00459               }
00460          }
00461        while (n != 0);
00462 # endif
00463        if (buflim == bufend)
00464          *--buflim = '0';
00465       }
00466       break;
00467     }
00468 
00469   return buflim;
00470 }
00471 #endif
00472 
00473 char *
00474 _fitoa_word (unsigned long value, char *buf, unsigned int base, int upper_case)
00475 {
00476   char tmpbuf[sizeof (value) * 4];       /* Worst case length: base 2.  */
00477   char *cp = _itoa_word (value, tmpbuf + sizeof (value) * 4, base, upper_case);
00478   while (cp < tmpbuf + sizeof (value) * 4)
00479     *buf++ = *cp++;
00480   return buf;
00481 }
00482 
00483 #if LLONG_MAX != LONG_MAX
00484 char *
00485 _fitoa (unsigned long long value, char *buf, unsigned int base, int upper_case)
00486 {
00487   char tmpbuf[sizeof (value) * 4];       /* Worst case length: base 2.  */
00488   char *cp = _itoa (value, tmpbuf + sizeof (value) * 4, base, upper_case);
00489   while (cp < tmpbuf + sizeof (value) * 4)
00490     *buf++ = *cp++;
00491   return buf;
00492 }
00493 #endif