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.
8 *
9 * This code is distributed in the hope that it will be useful, but WITHOUT
10 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
11 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
12 * version 2 for more details (a copy is included in the LICENSE file that
13 * accompanied this code).
14 *
15 * You should have received a copy of the GNU General Public License version
16 * 2 along with this work; if not, write to the Free Software Foundation,
17 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
18 *
19 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
20 * or visit www.oracle.com if you need additional information or have any
21 * questions.
22 */
23
24 //package sun.misc;
25
26 /*
27 * A really, really simple bigint package
28 * tailored to the needs of floating base conversion.
29 */
30 class OldFDBigIntForTest {
31 int nWords; // number of words used
32 int data[]; // value: data[0] is least significant
33
34
35 public OldFDBigIntForTest( int v ){
36 nWords = 1;
37 data = new int[1];
38 data[0] = v;
39 }
40
41 public OldFDBigIntForTest( long v ){
42 data = new int[2];
43 data[0] = (int)v;
44 data[1] = (int)(v>>>32);
45 nWords = (data[1]==0) ? 1 : 2;
46 }
47
48 public OldFDBigIntForTest( OldFDBigIntForTest other ){
49 data = new int[nWords = other.nWords];
50 System.arraycopy( other.data, 0, data, 0, nWords );
51 }
52
53 private OldFDBigIntForTest( int [] d, int n ){
54 data = d;
55 nWords = n;
56 }
57
58 public OldFDBigIntForTest( long seed, char digit[], int nd0, int nd ){
59 int n= (nd+8)/9; // estimate size needed.
60 if ( n < 2 ) n = 2;
61 data = new int[n]; // allocate enough space
62 data[0] = (int)seed; // starting value
63 data[1] = (int)(seed>>>32);
64 nWords = (data[1]==0) ? 1 : 2;
65 int i = nd0;
66 int limit = nd-5; // slurp digits 5 at a time.
67 int v;
68 while ( i < limit ){
69 int ilim = i+5;
70 v = (int)digit[i++]-(int)'0';
71 while( i <ilim ){
72 v = 10*v + (int)digit[i++]-(int)'0';
73 }
74 multaddMe( 100000, v); // ... where 100000 is 10^5.
75 }
76 int factor = 1;
77 v = 0;
78 while ( i < nd ){
79 v = 10*v + (int)digit[i++]-(int)'0';
80 factor *= 10;
81 }
82 if ( factor != 1 ){
83 multaddMe( factor, v );
84 }
85 }
86
87 /*
88 * Left shift by c bits.
89 * Shifts this in place.
90 */
91 public void
92 lshiftMe( int c )throws IllegalArgumentException {
93 if ( c <= 0 ){
94 if ( c == 0 )
95 return; // silly.
96 else
97 throw new IllegalArgumentException("negative shift count");
98 }
99 int wordcount = c>>5;
100 int bitcount = c & 0x1f;
101 int anticount = 32-bitcount;
102 int t[] = data;
103 int s[] = data;
104 if ( nWords+wordcount+1 > t.length ){
105 // reallocate.
106 t = new int[ nWords+wordcount+1 ];
107 }
108 int target = nWords+wordcount;
109 int src = nWords-1;
110 if ( bitcount == 0 ){
111 // special hack, since an anticount of 32 won't go!
112 System.arraycopy( s, 0, t, wordcount, nWords );
113 target = wordcount-1;
114 } else {
115 t[target--] = s[src]>>>anticount;
116 while ( src >= 1 ){
117 t[target--] = (s[src]<<bitcount) | (s[--src]>>>anticount);
118 }
119 t[target--] = s[src]<<bitcount;
120 }
121 while( target >= 0 ){
122 t[target--] = 0;
123 }
124 data = t;
125 nWords += wordcount + 1;
126 // may have constructed high-order word of 0.
127 // if so, trim it
128 while ( nWords > 1 && data[nWords-1] == 0 )
129 nWords--;
130 }
131
132 /*
133 * normalize this number by shifting until
134 * the MSB of the number is at 0x08000000.
135 * This is in preparation for quoRemIteration, below.
136 * The idea is that, to make division easier, we want the
137 * divisor to be "normalized" -- usually this means shifting
138 * the MSB into the high words sign bit. But because we know that
139 * the quotient will be 0 < q < 10, we would like to arrange that
140 * the dividend not span up into another word of precision.
141 * (This needs to be explained more clearly!)
142 */
143 public int
144 normalizeMe() throws IllegalArgumentException {
145 int src;
146 int wordcount = 0;
147 int bitcount = 0;
148 int v = 0;
149 for ( src= nWords-1 ; src >= 0 && (v=data[src]) == 0 ; src--){
150 wordcount += 1;
151 }
152 if ( src < 0 ){
153 // oops. Value is zero. Cannot normalize it!
154 throw new IllegalArgumentException("zero value");
155 }
156 /*
157 * In most cases, we assume that wordcount is zero. This only
158 * makes sense, as we try not to maintain any high-order
159 * words full of zeros. In fact, if there are zeros, we will
160 * simply SHORTEN our number at this point. Watch closely...
161 */
162 nWords -= wordcount;
163 /*
164 * Compute how far left we have to shift v s.t. its highest-
165 * order bit is in the right place. Then call lshiftMe to
166 * do the work.
167 */
168 if ( (v & 0xf0000000) != 0 ){
169 // will have to shift up into the next word.
170 // too bad.
171 for( bitcount = 32 ; (v & 0xf0000000) != 0 ; bitcount-- )
172 v >>>= 1;
173 } else {
174 while ( v <= 0x000fffff ){
175 // hack: byte-at-a-time shifting
176 v <<= 8;
177 bitcount += 8;
178 }
179 while ( v <= 0x07ffffff ){
180 v <<= 1;
181 bitcount += 1;
182 }
183 }
184 if ( bitcount != 0 )
185 lshiftMe( bitcount );
186 return bitcount;
187 }
188
189 /*
190 * Multiply a OldFDBigIntForTest by an int.
191 * Result is a new OldFDBigIntForTest.
192 */
193 public OldFDBigIntForTest
194 mult( int iv ) {
195 long v = iv;
196 int r[];
197 long p;
198
199 // guess adequate size of r.
200 r = new int[ ( v * ((long)data[nWords-1]&0xffffffffL) > 0xfffffffL ) ? nWords+1 : nWords ];
201 p = 0L;
202 for( int i=0; i < nWords; i++ ) {
203 p += v * ((long)data[i]&0xffffffffL);
204 r[i] = (int)p;
205 p >>>= 32;
206 }
207 if ( p == 0L){
208 return new OldFDBigIntForTest( r, nWords );
209 } else {
210 r[nWords] = (int)p;
211 return new OldFDBigIntForTest( r, nWords+1 );
212 }
213 }
214
215 /*
216 * Multiply a OldFDBigIntForTest by an int and add another int.
217 * Result is computed in place.
218 * Hope it fits!
219 */
220 public void
221 multaddMe( int iv, int addend ) {
222 long v = iv;
223 long p;
224
225 // unroll 0th iteration, doing addition.
226 p = v * ((long)data[0]&0xffffffffL) + ((long)addend&0xffffffffL);
227 data[0] = (int)p;
228 p >>>= 32;
229 for( int i=1; i < nWords; i++ ) {
230 p += v * ((long)data[i]&0xffffffffL);
231 data[i] = (int)p;
232 p >>>= 32;
233 }
234 if ( p != 0L){
235 data[nWords] = (int)p; // will fail noisily if illegal!
236 nWords++;
237 }
238 }
239
240 /*
241 * Multiply a OldFDBigIntForTest by another OldFDBigIntForTest.
242 * Result is a new OldFDBigIntForTest.
243 */
244 public OldFDBigIntForTest
245 mult( OldFDBigIntForTest other ){
246 // crudely guess adequate size for r
247 int r[] = new int[ nWords + other.nWords ];
248 int i;
249 // I think I am promised zeros...
250
251 for( i = 0; i < this.nWords; i++ ){
252 long v = (long)this.data[i] & 0xffffffffL; // UNSIGNED CONVERSION
253 long p = 0L;
254 int j;
255 for( j = 0; j < other.nWords; j++ ){
256 p += ((long)r[i+j]&0xffffffffL) + v*((long)other.data[j]&0xffffffffL); // UNSIGNED CONVERSIONS ALL 'ROUND.
257 r[i+j] = (int)p;
258 p >>>= 32;
259 }
260 r[i+j] = (int)p;
261 }
262 // compute how much of r we actually needed for all that.
263 for ( i = r.length-1; i> 0; i--)
264 if ( r[i] != 0 )
265 break;
266 return new OldFDBigIntForTest( r, i+1 );
267 }
268
269 /*
270 * Add one OldFDBigIntForTest to another. Return a OldFDBigIntForTest
271 */
272 public OldFDBigIntForTest
273 add( OldFDBigIntForTest other ){
274 int i;
275 int a[], b[];
276 int n, m;
277 long c = 0L;
278 // arrange such that a.nWords >= b.nWords;
279 // n = a.nWords, m = b.nWords
280 if ( this.nWords >= other.nWords ){
281 a = this.data;
282 n = this.nWords;
283 b = other.data;
284 m = other.nWords;
285 } else {
286 a = other.data;
287 n = other.nWords;
288 b = this.data;
289 m = this.nWords;
290 }
291 int r[] = new int[ n ];
292 for ( i = 0; i < n; i++ ){
293 c += (long)a[i] & 0xffffffffL;
294 if ( i < m ){
295 c += (long)b[i] & 0xffffffffL;
296 }
297 r[i] = (int) c;
298 c >>= 32; // signed shift.
299 }
300 if ( c != 0L ){
301 // oops -- carry out -- need longer result.
302 int s[] = new int[ r.length+1 ];
303 System.arraycopy( r, 0, s, 0, r.length );
304 s[i++] = (int)c;
305 return new OldFDBigIntForTest( s, i );
306 }
307 return new OldFDBigIntForTest( r, i );
308 }
309
310 /*
311 * Subtract one OldFDBigIntForTest from another. Return a OldFDBigIntForTest
312 * Assert that the result is positive.
313 */
314 public OldFDBigIntForTest
315 sub( OldFDBigIntForTest other ){
316 int r[] = new int[ this.nWords ];
317 int i;
318 int n = this.nWords;
319 int m = other.nWords;
320 int nzeros = 0;
321 long c = 0L;
322 for ( i = 0; i < n; i++ ){
323 c += (long)this.data[i] & 0xffffffffL;
324 if ( i < m ){
325 c -= (long)other.data[i] & 0xffffffffL;
326 }
327 if ( ( r[i] = (int) c ) == 0 )
328 nzeros++;
329 else
330 nzeros = 0;
331 c >>= 32; // signed shift
332 }
333 assert c == 0L : c; // borrow out of subtract
334 assert dataInRangeIsZero(i, m, other); // negative result of subtract
335 return new OldFDBigIntForTest( r, n-nzeros );
336 }
337
338 private static boolean dataInRangeIsZero(int i, int m, OldFDBigIntForTest other) {
339 while ( i < m )
340 if (other.data[i++] != 0)
341 return false;
342 return true;
343 }
344
345 /*
346 * Compare OldFDBigIntForTest with another OldFDBigIntForTest. Return an integer
347 * >0: this > other
348 * 0: this == other
349 * <0: this < other
350 */
351 public int
352 cmp( OldFDBigIntForTest other ){
353 int i;
354 if ( this.nWords > other.nWords ){
355 // if any of my high-order words is non-zero,
356 // then the answer is evident
357 int j = other.nWords-1;
358 for ( i = this.nWords-1; i > j ; i-- )
359 if ( this.data[i] != 0 ) return 1;
360 }else if ( this.nWords < other.nWords ){
361 // if any of other's high-order words is non-zero,
362 // then the answer is evident
363 int j = this.nWords-1;
364 for ( i = other.nWords-1; i > j ; i-- )
365 if ( other.data[i] != 0 ) return -1;
366 } else{
367 i = this.nWords-1;
368 }
369 for ( ; i > 0 ; i-- )
370 if ( this.data[i] != other.data[i] )
371 break;
372 // careful! want unsigned compare!
373 // use brute force here.
374 int a = this.data[i];
375 int b = other.data[i];
376 if ( a < 0 ){
377 // a is really big, unsigned
378 if ( b < 0 ){
379 return a-b; // both big, negative
380 } else {
381 return 1; // b not big, answer is obvious;
382 }
383 } else {
384 // a is not really big
385 if ( b < 0 ) {
386 // but b is really big
387 return -1;
388 } else {
389 return a - b;
390 }
391 }
392 }
393
394 /*
395 * Compute
396 * q = (int)( this / S )
397 * this = 10 * ( this mod S )
398 * Return q.
399 * This is the iteration step of digit development for output.
400 * We assume that S has been normalized, as above, and that
401 * "this" has been lshift'ed accordingly.
402 * Also assume, of course, that the result, q, can be expressed
403 * as an integer, 0 <= q < 10.
404 */
405 public int
406 quoRemIteration( OldFDBigIntForTest S )throws IllegalArgumentException {
407 // ensure that this and S have the same number of
408 // digits. If S is properly normalized and q < 10 then
409 // this must be so.
410 if ( nWords != S.nWords ){
411 throw new IllegalArgumentException("disparate values");
412 }
413 // estimate q the obvious way. We will usually be
414 // right. If not, then we're only off by a little and
415 // will re-add.
416 int n = nWords-1;
417 long q = ((long)data[n]&0xffffffffL) / (long)S.data[n];
418 long diff = 0L;
419 for ( int i = 0; i <= n ; i++ ){
420 diff += ((long)data[i]&0xffffffffL) - q*((long)S.data[i]&0xffffffffL);
421 data[i] = (int)diff;
422 diff >>= 32; // N.B. SIGNED shift.
423 }
424 if ( diff != 0L ) {
425 // damn, damn, damn. q is too big.
426 // add S back in until this turns +. This should
427 // not be very many times!
428 long sum = 0L;
429 while ( sum == 0L ){
430 sum = 0L;
431 for ( int i = 0; i <= n; i++ ){
432 sum += ((long)data[i]&0xffffffffL) + ((long)S.data[i]&0xffffffffL);
433 data[i] = (int) sum;
434 sum >>= 32; // Signed or unsigned, answer is 0 or 1
435 }
436 /*
437 * Originally the following line read
438 * "if ( sum !=0 && sum != -1 )"
439 * but that would be wrong, because of the
440 * treatment of the two values as entirely unsigned,
441 * it would be impossible for a carry-out to be interpreted
442 * as -1 -- it would have to be a single-bit carry-out, or
443 * +1.
444 */
445 assert sum == 0 || sum == 1 : sum; // carry out of division correction
446 q -= 1;
447 }
448 }
449 // finally, we can multiply this by 10.
450 // it cannot overflow, right, as the high-order word has
451 // at least 4 high-order zeros!
452 long p = 0L;
453 for ( int i = 0; i <= n; i++ ){
454 p += 10*((long)data[i]&0xffffffffL);
455 data[i] = (int)p;
456 p >>= 32; // SIGNED shift.
457 }
458 assert p == 0L : p; // Carry out of *10
459 return (int)q;
460 }
461
462 public long
463 longValue(){
464 // if this can be represented as a long, return the value
465 assert this.nWords > 0 : this.nWords; // longValue confused
466
467 if (this.nWords == 1)
468 return ((long)data[0]&0xffffffffL);
469
470 assert dataInRangeIsZero(2, this.nWords, this); // value too big
471 assert data[1] >= 0; // value too big
472 return ((long)(data[1]) << 32) | ((long)data[0]&0xffffffffL);
473 }
474
475 public String
476 toString() {
477 StringBuffer r = new StringBuffer(30);
478 r.append('[');
479 int i = Math.min( nWords-1, data.length-1) ;
480 if ( nWords > data.length ){
481 r.append( "("+data.length+"<"+nWords+"!)" );
482 }
483 for( ; i> 0 ; i-- ){
484 r.append( Integer.toHexString( data[i] ) );
485 r.append(' ');
486 }
487 r.append( Integer.toHexString( data[0] ) );
488 r.append(']');
489 return new String( r );
490 }
491 }