1 /* 2 * Copyright (c) 1996, 2011, 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 public 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 } 494
