/*
 * 5799-WZQ (C) COPYRIGHT IBM CORPORATION 1987
 * LICENSED MATERIALS - PROPERTY OF IBM
 * REFER TO COPYRIGHT INSTRUCTIONS FORM NUMBER G120-2083
 */
/* $Header:rad2a.c 12.0$ */
/* $ACIS:rad2a.c 12.0$ */
/* $Source: /ibm/acis/usr/src/lib/libc/ca/gen/RCS/rad2a.c,v $ */

#ifndef lint
static char *rcsid = "$Header:rad2a.c 12.0$";
#endif

/* CONVERT INTEGER TO ASCII

The argument is u, an unsigned longword integer less than 1e9. 
The result is U, a character string representing the decimal 
digits of u.

The algorithm is based on one given by D.E. Knuth, The Art of 
Computer Programming, volume 2, Seminumerical Algorithms, section 
4.4, "radix conversion", page 304, second edition. The idea 
behind the algorithm is to change the task from integer 
conversion to fraction conversion, so that divides can be 
replaced by multiplies, and also so that the digits can be 
obtained from left to right. Multiplies are less expensive than 
divides, and moreover multiplying by ten can easily be done in 
terms of shifts and adds. Obtaining digits from the left is 
important because we expect that quite often fewer than nine 
digits will be obtained, that is, that the number can have a 
significant number of trailing zero digits. We want to find a q 
and an r such that w times u is r + 1e9 times q. Then we can 
obtain the digits of u by repeatedly taking the floor of 10 times 
(q + 1) / w , since u is equal to floor of 1e9 times (q + 1) / w.  

For example, suppose we wish to obtain the decimal digits of 
123456789. We divide the two-digit radix w number 123456789 1e9 
by 1e9, getting the quotient (q + 1) = 530242872 and remainder r 
= 224172544. The remainder is of no concern to us. Now we imagine 
that we divide q + 1 by w, giving us an x with the radix point at 
its left, that is, that we have a fraction x = (q + 1) / w, which 
is, to nine places, 0.123456789.  Multiplying this by ten and 
taking the floor nine times in succession will give us the digits 
1 2 3 4 5 6 7 8 9. In detail, we show the two-digit, radix w 
product of 10 and the successive new x's, with the previous 
fraction column labelled x and the result columns labelled d and 
new x: 
 
            x            d   new x
        530242872 x 10 = 1 1007461425 
       1007461425 x 10 = 2 1484679648
       1484679648 x 10 = 3 1961894592
       1961894592 x 10 = 4 2439076736
       2439076736 x 10 = 5 2915930880
       2915930880 x 10 = 6 3389505024
       3389505024 x 10 = 7 3830279168
       3830279168 x 10 = 8 3943053312
       3943053312 x 10 = 9  775827456
       
The decimal digits are obtained by taking the successive values 
of the high-order digit d, and stopping after nine d's have been 
obtained.  

Because quite often there will be one or more trailing zeros, 
there is an advantage in checking whether the new x is so small 
that the remaining number of multiplications by ten is too few to 
produce another nonzero digit. Thus the test for termination at 
the jth step is to compare the new x value against the jth value 
in a list M, where M[j] is the largest value which, when 
multiplied by ten (9 - j) times, will still be less than w, and 
thus not be able to produce a nonzero decimal digit again. The 
tenth and last entry in M is (w - 1), and since the test for 
termination is if new x is less than or equal to M[j], the test 
for early termination also serves to terminate the algorithm 
after the maximum nine iterations.  Note also that the initial 
value in M is 4, and therefore that the algorithm will terminate 
with no iterations if the initial x is 4 or less, which will be 
the case if and only if u is 0 (if u is 1, the first x will be 
5).  

This method assumes that the radix for unsigned long integers, w, 
is two to the 32nd power, and that the argument u is a number 
between 0 and 1e9 - 1, inclusive. */


#define ONEBILL 1000000000 

/* The values in M can be computed by (ceil w / 10 tothe 9 - 
integers 10) - 1. */ 

static unsigned long M[] = {4, 42, 429, 4294, 42949, 429496, 
4294967, 42949672, 429496729, 4294967295};

/* The values in BILL can be obtained by 1e9 times integers 5. */

static unsigned long BILL[] = {0, 1000000000, 2000000000, 
3000000000, 4000000000};

_rad2b (U, u)  /* Convert u to characters in U) */
char U[9];
unsigned long u;               /* 0 <= u < 1e9, we trust. */

{unsigned long s0, s1, s2;     /* dividend */
 unsigned long t0, t1, t2; 
 int i, j;                     /* counters */

 s0 = 0;
 s1 = u;
 s2 = ONEBILL;

 _spdiv8 (&s0, &s1, &s2); /* result replaces argument

The value s0 may be nonzero -- the possibilities are 1 through 4 
-- (and will be if u is larger than 232830643). We take care of 
this possibility by adding the appropriate integer multiple of 1e9 
and s0 to form t1. */ 
 
 t1 = s1 + BILL[s0]; /*

The result U is initiated to all character '0's, so that we can 
end the algorithm below safely. */

 for (i = 0 ; i < 9 ; i++)
     U[i] = '0';

 for (j = 0 ; t1 >= M[j] ; j++) /*
 
 We multiply by ten by using shifts and adds. */

  {t0 = (t1 >> 29) + (t1 >> 31); /* d, possibly */

   /* Overflow can occur, and we detect it by seeing whether the 
   sum in t1 is less than the summand in t2, since overflow has 
   occurred if (a = b + c) (mod m) is less than either b or c. 
   */

   t2 = t1 << 1;                 /* to help detect overflow */
   t1 = (t1 << 3) + t2;          /* new x, may overflow w - 1 */
   t0 += t1 < t2;                /* overflow if t1 < t2; d, certainly */
   U[j] = (char) t0 + '0';       /* translate d to ASCII */
  };
}
