1 /*

     2  * Copyright (c) 1996, 2012, Oracle and/or its affiliates. All rights reserved.

     3  * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.

     4  *

     5  * This code is free software; you can redistribute it and/or modify it

     6  * under the terms of the GNU General Public License version 2 only, as

     7  * published by the Free Software Foundation.  Oracle designates this

     8  * particular file as subject to the "Classpath" exception as provided

     9  * by Oracle in the LICENSE file that accompanied this code.

    10  *

    11  * This code is distributed in the hope that it will be useful, but WITHOUT

    12  * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or

    13  * FITNESS FOR A PARTICULAR PURPOSE.  See the GNU General Public License

    14  * version 2 for more details (a copy is included in the LICENSE file that

    15  * accompanied this code).

    16  *

    17  * You should have received a copy of the GNU General Public License version

    18  * 2 along with this work; if not, write to the Free Software Foundation,

    19  * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.

    20  *

    21  * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA

    22  * or visit www.oracle.com if you need additional information or have any

    23  * questions.

    24  */

    25 

    26 package sun.misc;

    27 

    28 /*

    29  * A really, really simple bigint package

    30  * tailored to the needs of floating base conversion.

    31  */

    32 class FDBigInt {

    33     int nWords; // number of words used

    34     int data[]; // value: data[0] is least significant

    35 

    36 

    37     public FDBigInt( int v ){

    38         nWords = 1;

    39         data = new int[1];

    40         data[0] = v;

    41     }

    42 

    43     public FDBigInt( long v ){

    44         data = new int[2];

    45         data[0] = (int)v;

    46         data[1] = (int)(v>>>32);

    47         nWords = (data[1]==0) ? 1 : 2;

    48     }

    49 

    50     public FDBigInt( FDBigInt other ){

    51         data = new int[nWords = other.nWords];

    52         System.arraycopy( other.data, 0, data, 0, nWords );

    53     }

    54 

    55     private FDBigInt( int [] d, int n ){

    56         data = d;

    57         nWords = n;

    58     }

    59 

    60     public FDBigInt( long seed, char digit[], int nd0, int nd ){

    61         int n= (nd+8)/9;        // estimate size needed.

    62         if ( n < 2 ) n = 2;

    63         data = new int[n];      // allocate enough space

    64         data[0] = (int)seed;    // starting value

    65         data[1] = (int)(seed>>>32);

    66         nWords = (data[1]==0) ? 1 : 2;

    67         int i = nd0;

    68         int limit = nd-5;       // slurp digits 5 at a time.

    69         int v;

    70         while ( i < limit ){

    71             int ilim = i+5;

    72             v = (int)digit[i++]-(int)'0';

    73             while( i <ilim ){

    74                 v = 10*v + (int)digit[i++]-(int)'0';

    75             }

    76             multaddMe( 100000, v); // ... where 100000 is 10^5.

    77         }

    78         int factor = 1;

    79         v = 0;

    80         while ( i < nd ){

    81             v = 10*v + (int)digit[i++]-(int)'0';

    82             factor *= 10;

    83         }

    84         if ( factor != 1 ){

    85             multaddMe( factor, v );

    86         }

    87     }

    88 

    89     /*

    90      * Left shift by c bits.

    91      * Shifts this in place.

    92      */

    93     public void

    94     lshiftMe( int c )throws IllegalArgumentException {

    95         if ( c <= 0 ){

    96             if ( c == 0 )

    97                 return; // silly.

    98             else

    99                 throw new IllegalArgumentException("negative shift count");

   100         }

   101         int wordcount = c>>5;

   102         int bitcount  = c & 0x1f;

   103         int anticount = 32-bitcount;

   104         int t[] = data;

   105         int s[] = data;

   106         if ( nWords+wordcount+1 > t.length ){

   107             // reallocate.

   108             t = new int[ nWords+wordcount+1 ];

   109         }

   110         int target = nWords+wordcount;

   111         int src    = nWords-1;

   112         if ( bitcount == 0 ){

   113             // special hack, since an anticount of 32 won't go!

   114             System.arraycopy( s, 0, t, wordcount, nWords );

   115             target = wordcount-1;

   116         } else {

   117             t[target--] = s[src]>>>anticount;

   118             while ( src >= 1 ){

   119                 t[target--] = (s[src]<<bitcount) | (s[--src]>>>anticount);

   120             }

   121             t[target--] = s[src]<<bitcount;

   122         }

   123         while( target >= 0 ){

   124             t[target--] = 0;

   125         }

   126         data = t;

   127         nWords += wordcount + 1;

   128         // may have constructed high-order word of 0.

   129         // if so, trim it

   130         while ( nWords > 1 && data[nWords-1] == 0 )

   131             nWords--;

   132     }

   133 

   134     /*

   135      * normalize this number by shifting until

   136      * the MSB of the number is at 0x08000000.

   137      * This is in preparation for quoRemIteration, below.

   138      * The idea is that, to make division easier, we want the

   139      * divisor to be "normalized" -- usually this means shifting

   140      * the MSB into the high words sign bit. But because we know that

   141      * the quotient will be 0 < q < 10, we would like to arrange that

   142      * the dividend not span up into another word of precision.

   143      * (This needs to be explained more clearly!)

   144      */

   145     public int

   146     normalizeMe() throws IllegalArgumentException {

   147         int src;

   148         int wordcount = 0;

   149         int bitcount  = 0;

   150         int v = 0;

   151         for ( src= nWords-1 ; src >= 0 && (v=data[src]) == 0 ; src--){

   152             wordcount += 1;

   153         }

   154         if ( src < 0 ){

   155             // oops. Value is zero. Cannot normalize it!

   156             throw new IllegalArgumentException("zero value");

   157         }

   158         /*

   159          * In most cases, we assume that wordcount is zero. This only

   160          * makes sense, as we try not to maintain any high-order

   161          * words full of zeros. In fact, if there are zeros, we will

   162          * simply SHORTEN our number at this point. Watch closely...

   163          */

   164         nWords -= wordcount;

   165         /*

   166          * Compute how far left we have to shift v s.t. its highest-

   167          * order bit is in the right place. Then call lshiftMe to

   168          * do the work.

   169          */

   170         if ( (v & 0xf0000000) != 0 ){

   171             // will have to shift up into the next word.

   172             // too bad.

   173             for( bitcount = 32 ; (v & 0xf0000000) != 0 ; bitcount-- )

   174                 v >>>= 1;

   175         } else {

   176             while ( v <= 0x000fffff ){

   177                 // hack: byte-at-a-time shifting

   178                 v <<= 8;

   179                 bitcount += 8;

   180             }

   181             while ( v <= 0x07ffffff ){

   182                 v <<= 1;

   183                 bitcount += 1;

   184             }

   185         }

   186         if ( bitcount != 0 )

   187             lshiftMe( bitcount );

   188         return bitcount;

   189     }

   190 

   191     /*

   192      * Multiply a FDBigInt by an int.

   193      * Result is a new FDBigInt.

   194      */

   195     public FDBigInt

   196     mult( int iv ) {

   197         long v = iv;

   198         int r[];

   199         long p;

   200 

   201         // guess adequate size of r.

   202         r = new int[ ( v * ((long)data[nWords-1]&0xffffffffL) > 0xfffffffL ) ? nWords+1 : nWords ];

   203         p = 0L;

   204         for( int i=0; i < nWords; i++ ) {

   205             p += v * ((long)data[i]&0xffffffffL);

   206             r[i] = (int)p;

   207             p >>>= 32;

   208         }

   209         if ( p == 0L){

   210             return new FDBigInt( r, nWords );

   211         } else {

   212             r[nWords] = (int)p;

   213             return new FDBigInt( r, nWords+1 );

   214         }

   215     }

   216 

   217     /*

   218      * Multiply a FDBigInt by an int and add another int.

   219      * Result is computed in place.

   220      * Hope it fits!

   221      */

   222     public void

   223     multaddMe( int iv, int addend ) {

   224         long v = iv;

   225         long p;

   226 

   227         // unroll 0th iteration, doing addition.

   228         p = v * ((long)data[0]&0xffffffffL) + ((long)addend&0xffffffffL);

   229         data[0] = (int)p;

   230         p >>>= 32;

   231         for( int i=1; i < nWords; i++ ) {

   232             p += v * ((long)data[i]&0xffffffffL);

   233             data[i] = (int)p;

   234             p >>>= 32;

   235         }

   236         if ( p != 0L){

   237             data[nWords] = (int)p; // will fail noisily if illegal!

   238             nWords++;

   239         }

   240     }

   241 

   242     /*

   243      * Multiply a FDBigInt by another FDBigInt.

   244      * Result is a new FDBigInt.

   245      */

   246     public FDBigInt

   247     mult( FDBigInt other ){

   248         // crudely guess adequate size for r

   249         int r[] = new int[ nWords + other.nWords ];

   250         int i;

   251         // I think I am promised zeros...

   252 

   253         for( i = 0; i < this.nWords; i++ ){

   254             long v = (long)this.data[i] & 0xffffffffL; // UNSIGNED CONVERSION

   255             long p = 0L;

   256             int j;

   257             for( j = 0; j < other.nWords; j++ ){

   258                 p += ((long)r[i+j]&0xffffffffL) + v*((long)other.data[j]&0xffffffffL); // UNSIGNED CONVERSIONS ALL 'ROUND.

   259                 r[i+j] = (int)p;

   260                 p >>>= 32;

   261             }

   262             r[i+j] = (int)p;

   263         }

   264         // compute how much of r we actually needed for all that.

   265         for ( i = r.length-1; i> 0; i--)

   266             if ( r[i] != 0 )

   267                 break;

   268         return new FDBigInt( r, i+1 );

   269     }

   270 

   271     /*

   272      * Add one FDBigInt to another. Return a FDBigInt

   273      */

   274     public FDBigInt

   275     add( FDBigInt other ){

   276         int i;

   277         int a[], b[];

   278         int n, m;

   279         long c = 0L;

   280         // arrange such that a.nWords >= b.nWords;

   281         // n = a.nWords, m = b.nWords

   282         if ( this.nWords >= other.nWords ){

   283             a = this.data;

   284             n = this.nWords;

   285             b = other.data;

   286             m = other.nWords;

   287         } else {

   288             a = other.data;

   289             n = other.nWords;

   290             b = this.data;

   291             m = this.nWords;

   292         }

   293         int r[] = new int[ n ];

   294         for ( i = 0; i < n; i++ ){

   295             c += (long)a[i] & 0xffffffffL;

   296             if ( i < m ){

   297                 c += (long)b[i] & 0xffffffffL;

   298             }

   299             r[i] = (int) c;

   300             c >>= 32; // signed shift.

   301         }

   302         if ( c != 0L ){

   303             // oops -- carry out -- need longer result.

   304             int s[] = new int[ r.length+1 ];

   305             System.arraycopy( r, 0, s, 0, r.length );

   306             s[i++] = (int)c;

   307             return new FDBigInt( s, i );

   308         }

   309         return new FDBigInt( r, i );

   310     }

   311 

   312     /*

   313      * Subtract one FDBigInt from another. Return a FDBigInt

   314      * Assert that the result is positive.

   315      */

   316     public FDBigInt

   317     sub( FDBigInt other ){

   318         int r[] = new int[ this.nWords ];

   319         int i;

   320         int n = this.nWords;

   321         int m = other.nWords;

   322         int nzeros = 0;

   323         long c = 0L;

   324         for ( i = 0; i < n; i++ ){

   325             c += (long)this.data[i] & 0xffffffffL;

   326             if ( i < m ){

   327                 c -= (long)other.data[i] & 0xffffffffL;

   328             }

   329             if ( ( r[i] = (int) c ) == 0 )

   330                 nzeros++;

   331             else

   332                 nzeros = 0;

   333             c >>= 32; // signed shift

   334         }

   335         assert c == 0L : c; // borrow out of subtract

   336         assert dataInRangeIsZero(i, m, other); // negative result of subtract

   337         return new FDBigInt( r, n-nzeros );

   338     }

   339 

   340     private static boolean dataInRangeIsZero(int i, int m, FDBigInt other) {

   341         while ( i < m )

   342             if (other.data[i++] != 0)

   343                 return false;

   344         return true;

   345     }

   346 

   347     /*

   348      * Compare FDBigInt with another FDBigInt. Return an integer

   349      * >0: this > other

   350      *  0: this == other

   351      * <0: this < other

   352      */

   353     public int

   354     cmp( FDBigInt other ){

   355         int i;

   356         if ( this.nWords > other.nWords ){

   357             // if any of my high-order words is non-zero,

   358             // then the answer is evident

   359             int j = other.nWords-1;

   360             for ( i = this.nWords-1; i > j ; i-- )

   361                 if ( this.data[i] != 0 ) return 1;

   362         }else if ( this.nWords < other.nWords ){

   363             // if any of other's high-order words is non-zero,

   364             // then the answer is evident

   365             int j = this.nWords-1;

   366             for ( i = other.nWords-1; i > j ; i-- )

   367                 if ( other.data[i] != 0 ) return -1;

   368         } else{

   369             i = this.nWords-1;

   370         }

   371         for ( ; i > 0 ; i-- )

   372             if ( this.data[i] != other.data[i] )

   373                 break;

   374         // careful! want unsigned compare!

   375         // use brute force here.

   376         int a = this.data[i];

   377         int b = other.data[i];

   378         if ( a < 0 ){

   379             // a is really big, unsigned

   380             if ( b < 0 ){

   381                 return a-b; // both big, negative

   382             } else {

   383                 return 1; // b not big, answer is obvious;

   384             }

   385         } else {

   386             // a is not really big

   387             if ( b < 0 ) {

   388                 // but b is really big

   389                 return -1;

   390             } else {

   391                 return a - b;

   392             }

   393         }

   394     }

   395 

   396     /*

   397      * Compute

   398      * q = (int)( this / S )

   399      * this = 10 * ( this mod S )

   400      * Return q.

   401      * This is the iteration step of digit development for output.

   402      * We assume that S has been normalized, as above, and that

   403      * "this" has been lshift'ed accordingly.

   404      * Also assume, of course, that the result, q, can be expressed

   405      * as an integer, 0 <= q < 10.

   406      */

   407     public int

   408     quoRemIteration( FDBigInt S )throws IllegalArgumentException {

   409         // ensure that this and S have the same number of

   410         // digits. If S is properly normalized and q < 10 then

   411         // this must be so.

   412         if ( nWords != S.nWords ){

   413             throw new IllegalArgumentException("disparate values");

   414         }

   415         // estimate q the obvious way. We will usually be

   416         // right. If not, then we're only off by a little and

   417         // will re-add.

   418         int n = nWords-1;

   419         long q = ((long)data[n]&0xffffffffL) / (long)S.data[n];

   420         long diff = 0L;

   421         for ( int i = 0; i <= n ; i++ ){

   422             diff += ((long)data[i]&0xffffffffL) -  q*((long)S.data[i]&0xffffffffL);

   423             data[i] = (int)diff;

   424             diff >>= 32; // N.B. SIGNED shift.

   425         }

   426         if ( diff != 0L ) {

   427             // damn, damn, damn. q is too big.

   428             // add S back in until this turns +. This should

   429             // not be very many times!

   430             long sum = 0L;

   431             while ( sum ==  0L ){

   432                 sum = 0L;

   433                 for ( int i = 0; i <= n; i++ ){

   434                     sum += ((long)data[i]&0xffffffffL) +  ((long)S.data[i]&0xffffffffL);

   435                     data[i] = (int) sum;

   436                     sum >>= 32; // Signed or unsigned, answer is 0 or 1

   437                 }

   438                 /*

   439                  * Originally the following line read

   440                  * "if ( sum !=0 && sum != -1 )"

   441                  * but that would be wrong, because of the

   442                  * treatment of the two values as entirely unsigned,

   443                  * it would be impossible for a carry-out to be interpreted

   444                  * as -1 -- it would have to be a single-bit carry-out, or

   445                  * +1.

   446                  */

   447                 assert sum == 0 || sum == 1 : sum; // carry out of division correction

   448                 q -= 1;

   449             }

   450         }

   451         // finally, we can multiply this by 10.

   452         // it cannot overflow, right, as the high-order word has

   453         // at least 4 high-order zeros!

   454         long p = 0L;

   455         for ( int i = 0; i <= n; i++ ){

   456             p += 10*((long)data[i]&0xffffffffL);

   457             data[i] = (int)p;

   458             p >>= 32; // SIGNED shift.

   459         }

   460         assert p == 0L : p; // Carry out of *10

   461         return (int)q;

   462     }

   463 

   464     public long

   465     longValue(){

   466         // if this can be represented as a long, return the value

   467         assert this.nWords > 0 : this.nWords; // longValue confused

   468 

   469         if (this.nWords == 1)

   470             return ((long)data[0]&0xffffffffL);

   471 

   472         assert dataInRangeIsZero(2, this.nWords, this); // value too big

   473         assert data[1] >= 0;  // value too big

   474         return ((long)(data[1]) << 32) | ((long)data[0]&0xffffffffL);

   475     }

   476 

   477     public String

   478     toString() {

   479         StringBuffer r = new StringBuffer(30);

   480         r.append('[');

   481         int i = Math.min( nWords-1, data.length-1) ;

   482         if ( nWords > data.length ){

   483             r.append( "("+data.length+"<"+nWords+"!)" );

   484         }

   485         for( ; i> 0 ; i-- ){

   486             r.append( Integer.toHexString( data[i] ) );

   487             r.append(' ');

   488         }

   489         r.append( Integer.toHexString( data[0] ) );

   490         r.append(']');

   491         return new String( r );

   492     }

   493 }