1/* Internal function for converting integers to ASCII.
2   Copyright (C) 1994,1995,1996,1999,2000,2002 Free Software Foundation, Inc.
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
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.
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
15   Lesser General Public License for more details.
16
17   You should have received a copy of the GNU Lesser General Public
18   License along with the GNU C Library; if not, write to the Free
19   Software Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA
20   02111-1307 USA.  */
21
22#include <gmp-mparam.h>
23#include <gmp.h>
24#include <stdlib/gmp-impl.h>
25#include <stdlib/longlong.h>
26
27#include "_itowa.h"
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.  */
49struct 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.  */
80extern const struct base_table_t _itoa_base_table[] attribute_hidden;
81
82/* Lower-case digits.  */
83extern const wchar_t _itowa_lower_digits[] attribute_hidden;
84/* Upper-case digits.  */
85extern const wchar_t _itowa_upper_digits[] attribute_hidden;
86
87
88wchar_t *
89_itowa (value, buflim, base, upper_case)
90     unsigned long long int value;
91     wchar_t *buflim;
92     unsigned int base;
93     int upper_case;
94{
95  const wchar_t *digits = (upper_case
96			   ? _itowa_upper_digits : _itowa_lower_digits);
97  wchar_t *bp = buflim;
98  const struct base_table_t *brec = &_itoa_base_table[base - 2];
99
100  switch (base)
101    {
102#define RUN_2N(BITS) \
103      do								      \
104        {								      \
105	  /* `unsigned long long int' always has 64 bits.  */		      \
106	  mp_limb_t work_hi = value >> (64 - BITS_PER_MP_LIMB);		      \
107									      \
108	  if (BITS_PER_MP_LIMB == 32)					      \
109	    {								      \
110	      if (work_hi != 0)						      \
111		{							      \
112		  mp_limb_t work_lo;					      \
113		  int cnt;						      \
114									      \
115		  work_lo = value & 0xfffffffful;			      \
116		  for (cnt = BITS_PER_MP_LIMB / BITS; cnt > 0; --cnt)	      \
117		    {							      \
118		      *--bp = digits[work_lo & ((1ul << BITS) - 1)];	      \
119		      work_lo >>= BITS;					      \
120		    }							      \
121		  if (BITS_PER_MP_LIMB % BITS != 0)			      \
122		    {							      \
123		      work_lo						      \
124			|= ((work_hi					      \
125			     & ((1 << (BITS - BITS_PER_MP_LIMB%BITS))	      \
126				- 1))					      \
127			    << BITS_PER_MP_LIMB % BITS);		      \
128		      work_hi >>= BITS - BITS_PER_MP_LIMB % BITS;	      \
129		      if (work_hi == 0)					      \
130			work_hi = work_lo;				      \
131		      else						      \
132			*--bp = digits[work_lo];			      \
133		    }							      \
134		}							      \
135	      else							      \
136		work_hi = value & 0xfffffffful;				      \
137	    }								      \
138	  do								      \
139	    {								      \
140	      *--bp = digits[work_hi & ((1 << BITS) - 1)];		      \
141	      work_hi >>= BITS;						      \
142	    }								      \
143	  while (work_hi != 0);						      \
144	}								      \
145      while (0)
146    case 8:
147      RUN_2N (3);
148      break;
149
150    case 16:
151      RUN_2N (4);
152      break;
153
154    default:
155      {
156#if BITS_PER_MP_LIMB == 64
157	mp_limb_t base_multiplier = brec->base_multiplier;
158	if (brec->flag)
159	  while (value != 0)
160	    {
161	      mp_limb_t quo, rem, x, dummy;
162
163	      umul_ppmm (x, dummy, value, base_multiplier);
164	      quo = (x + ((value - x) >> 1)) >> (brec->post_shift - 1);
165	      rem = value - quo * base;
166	      *--bp = digits[rem];
167	      value = quo;
168	    }
169	else
170	  while (value != 0)
171	    {
172	      mp_limb_t quo, rem, x, dummy;
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	    }
180#endif
181#if BITS_PER_MP_LIMB == 32
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	  {
189#if UDIV_TIME > 2 * UMUL_TIME || UDIV_NEEDS_NORMALIZATION
190	    int big_normalization_steps = brec->big.normalization_steps;
191	    mp_limb_t big_base_norm
192	      = brec->big.base << big_normalization_steps;
193#endif
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
202#if UDIV_TIME > 2 * UMUL_TIME
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;
227#elif UDIV_NEEDS_NORMALIZATION
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;
249#else
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);
254#endif
255		n = 3;
256	      }
257	    else
258	      {
259#if (UDIV_TIME > 2 * UMUL_TIME)
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;
267#elif UDIV_NEEDS_NORMALIZATION
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;
274#else
275		udiv_qrnnd (t[0], t[1], (mp_limb_t) (value >> 32),
276			    (mp_limb_t) value, brec->big.base);
277#endif
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
293#if UDIV_TIME > 2 * UMUL_TIME
294	    mp_limb_t base_multiplier = brec->base_multiplier;
295	    if (brec->flag)
296	      while (ti != 0)
297		{
298		  mp_limb_t quo, rem, x, dummy;
299
300		  umul_ppmm (x, dummy, ti, base_multiplier);
301		  quo = (x + ((ti - x) >> 1)) >> (brec->post_shift - 1);
302		  rem = ti - quo * base;
303		  *--bp = digits[rem];
304		  ti = quo;
305		  ++ndig_for_this_limb;
306		}
307	    else
308	      while (ti != 0)
309		{
310		  mp_limb_t quo, rem, x, dummy;
311
312		  umul_ppmm (x, dummy, ti, base_multiplier);
313		  quo = x >> brec->post_shift;
314		  rem = ti - quo * base;
315		  *--bp = digits[rem];
316		  ti = quo;
317		  ++ndig_for_this_limb;
318		}
319#else
320	    while (ti != 0)
321	      {
322		mp_limb_t quo, rem;
323
324		quo = ti / base;
325		rem = ti % base;
326		*--bp = digits[rem];
327		ti = quo;
328		++ndig_for_this_limb;
329	      }
330#endif
331	    /* If this wasn't the most significant word, pad with zeros.  */
332	    if (n != 0)
333	      while (ndig_for_this_limb < brec->big.ndigits)
334		{
335		  *--bp = '0';
336		  ++ndig_for_this_limb;
337		}
338	  }
339	while (n != 0);
340#endif
341      }
342      break;
343    }
344
345  return bp;
346}
347