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 }