1 /* 2 ********************************************************************** 3 * Copyright (C) 1997-2007, International Business Machines 4 * Corporation and others. All Rights Reserved. 5 ********************************************************************** 6 * 7 * File DIGITLST.CPP 8 * 9 * Modification History: 10 * 11 * Date Name Description 12 * 03/21/97 clhuang Converted from java. 13 * 03/21/97 clhuang Implemented with new APIs. 14 * 03/27/97 helena Updated to pass the simple test after code review. 15 * 03/31/97 aliu Moved isLONG_MIN to here, and fixed it. 16 * 04/15/97 aliu Changed MAX_COUNT to DBL_DIG. Changed Digit to char. 17 * Reworked representation by replacing fDecimalAt 18 * with fExponent. 19 * 04/16/97 aliu Rewrote set() and getDouble() to use sprintf/atof 20 * to do digit conversion. 21 * 09/09/97 aliu Modified for exponential notation support. 22 * 08/02/98 stephen Added nearest/even rounding 23 * Fixed bug in fitsIntoLong 24 ****************************************************************************** 25 */ 26 27 #include "digitlst.h" 28 29 #if !UCONFIG_NO_FORMATTING 30 #include "unicode/putil.h" 31 #include "cstring.h" 32 #include "putilimp.h" 33 #include "uassert.h" 34 #include <stdlib.h> 35 #include <limits.h> 36 #include <string.h> 37 #include <stdio.h> 38 39 // *************************************************************************** 40 // class DigitList 41 // This class handles the transcoding between numeric values and strings of 42 // characters. Only handles as non-negative numbers. 43 // *************************************************************************** 44 45 /** 46 * This is the zero digit. Array elements fDigits[i] have values from 47 * kZero to kZero + 9. Typically, this is '0'. 48 */ 49 #define kZero '0' 50 51 static char gDecimal = 0; 52 53 /* Only for 32 bit numbers. Ignore the negative sign. */ 54 static const char LONG_MIN_REP[] = "2147483648"; 55 static const char I64_MIN_REP[] = "9223372036854775808"; 56 57 enum { 58 LONG_MIN_REP_LENGTH = sizeof(LONG_MIN_REP) - 1, //Ignore the NULL at the end 59 I64_MIN_REP_LENGTH = sizeof(I64_MIN_REP) - 1 //Ignore the NULL at the end 60 }; 61 62 U_NAMESPACE_BEGIN 63 64 65 // ------------------------------------- 66 // default constructor 67 68 DigitList::DigitList() 69 { 70 fDigits = fDecimalDigits + 1; // skip the decimal 71 clear(); 72 } 73 74 // ------------------------------------- 75 76 DigitList::~DigitList() 77 { 78 } 79 80 // ------------------------------------- 81 // copy constructor 82 83 DigitList::DigitList(const DigitList &other) 84 { 85 fDigits = fDecimalDigits + 1; // skip the decimal 86 *this = other; 87 } 88 89 // ------------------------------------- 90 // assignment operator 91 92 DigitList& 93 DigitList::operator=(const DigitList& other) 94 { 95 if (this != &other) 96 { 97 fDecimalAt = other.fDecimalAt; 98 fCount = other.fCount; 99 fIsPositive = other.fIsPositive; 100 fRoundingMode = other.fRoundingMode; 101 uprv_strncpy(fDigits, other.fDigits, fCount); 102 } 103 return *this; 104 } 105 106 // ------------------------------------- 107 108 UBool 109 DigitList::operator==(const DigitList& that) const 110 { 111 return ((this == &that) || 112 (fDecimalAt == that.fDecimalAt && 113 fCount == that.fCount && 114 fIsPositive == that.fIsPositive && 115 fRoundingMode == that.fRoundingMode && 116 uprv_strncmp(fDigits, that.fDigits, fCount) == 0)); 117 } 118 119 // ------------------------------------- 120 // Resets the digit list; sets all the digits to zero. 121 122 void 123 DigitList::clear() 124 { 125 fDecimalAt = 0; 126 fCount = 0; 127 fIsPositive = TRUE; 128 fRoundingMode = DecimalFormat::kRoundHalfEven; 129 130 // Don't bother initializing fDigits because fCount is 0. 131 } 132 133 134 135 // ------------------------------------- 136 137 /** 138 * Formats a number into a base 10 string representation, and NULL terminates it. 139 * @param number The number to format 140 * @param outputStr The string to output to 141 * @param outputLen The maximum number of characters to put into outputStr 142 * (including NULL). 143 * @return the number of digits written, not including the sign. 144 */ 145 static int32_t 146 formatBase10(int64_t number, char *outputStr, int32_t outputLen) 147 { 148 char buffer[MAX_DIGITS + 1]; 149 int32_t bufferLen; 150 int32_t result; 151 152 if (outputLen > MAX_DIGITS) { 153 outputLen = MAX_DIGITS; // Ignore NULL 154 } 155 else if (outputLen < 3) { 156 return 0; // Not enough room 157 } 158 159 bufferLen = outputLen; 160 161 if (number < 0) { // Negative numbers are slightly larger than a postive 162 buffer[bufferLen--] = (char)(-(number % 10) + kZero); 163 number /= -10; 164 *(outputStr++) = '-'; 165 } 166 else { 167 *(outputStr++) = '+'; // allow +0 168 } 169 while (bufferLen >= 0 && number) { // Output the number 170 buffer[bufferLen--] = (char)(number % 10 + kZero); 171 number /= 10; 172 } 173 174 result = outputLen - bufferLen++; 175 176 while (bufferLen <= outputLen) { // Copy the number to output 177 *(outputStr++) = buffer[bufferLen++]; 178 } 179 *outputStr = 0; // NULL terminate. 180 return result; 181 } 182 183 /** 184 * Currently, getDouble() depends on atof() to do its conversion. 185 * 186 * WARNING!! 187 * This is an extremely costly function. ~1/2 of the conversion time 188 * can be linked to this function. 189 */ 190 double 191 DigitList::getDouble() /*const*/ 192 { 193 double value; 194 195 if (fCount == 0) { 196 value = 0.0; 197 } 198 else { 199 char* end = NULL; 200 if (!gDecimal) { 201 char rep[MAX_DIGITS]; 202 // For machines that decide to change the decimal on you, 203 // and try to be too smart with localization. 204 // This normally should be just a '.'. 205 sprintf(rep, "%+1.1f", 1.0); 206 gDecimal = rep[2]; 207 } 208 209 *fDecimalDigits = gDecimal; 210 *(fDigits+fCount) = 'e'; // add an e after the digits. 211 formatBase10(fDecimalAt, 212 fDigits + fCount + 1, // skip the 'e' 213 MAX_DEC_DIGITS - fCount - 3); // skip the 'e' and '.' 214 value = uprv_strtod(fDecimalDigits, &end); 215 } 216 217 return fIsPositive ? value : -value; 218 } 219 220 // ------------------------------------- 221 222 /** 223 * Make sure that fitsIntoLong() is called before calling this function. 224 */ 225 int32_t DigitList::getLong() /*const*/ 226 { 227 if (fCount == fDecimalAt) { 228 int32_t value; 229 230 fDigits[fCount] = 0; // NULL terminate 231 232 // This conversion is bad on 64-bit platforms when we want to 233 // be able to return a 64-bit number [grhoten] 234 *fDecimalDigits = fIsPositive ? '+' : '-'; 235 value = (int32_t)atol(fDecimalDigits); 236 return value; 237 } 238 else { 239 // This is 100% accurate in c++ because if we are representing 240 // an integral value, we suffer nothing in the conversion to 241 // double. If we are to support 64-bit longs later, getLong() 242 // must be rewritten. [LIU] 243 return (int32_t)getDouble(); 244 } 245 } 246 247 248 /** 249 * Make sure that fitsIntoInt64() is called before calling this function. 250 */ 251 int64_t DigitList::getInt64() /*const*/ 252 { 253 if (fCount == fDecimalAt) { 254 uint64_t value; 255 256 fDigits[fCount] = 0; // NULL terminate 257 258 // This conversion is bad on 64-bit platforms when we want to 259 // be able to return a 64-bit number [grhoten] 260 *fDecimalDigits = fIsPositive ? '+' : '-'; 261 262 // emulate a platform independent atoi64() 263 value = 0; 264 for (int i = 0; i < fCount; ++i) { 265 int v = fDigits[i] - kZero; 266 value = value * (uint64_t)10 + (uint64_t)v; 267 } 268 if (!fIsPositive) { 269 value = ~value; 270 value += 1; 271 } 272 int64_t svalue = (int64_t)value; 273 return svalue; 274 } 275 else { 276 // TODO: figure out best approach 277 278 // This is 100% accurate in c++ because if we are representing 279 // an integral value, we suffer nothing in the conversion to 280 // double. If we are to support 64-bit longs later, getLong() 281 // must be rewritten. [LIU] 282 return (int64_t)getDouble(); 283 } 284 } 285 286 /** 287 * Return true if the number represented by this object can fit into 288 * a long. 289 */ 290 UBool 291 DigitList::fitsIntoLong(UBool ignoreNegativeZero) /*const*/ 292 { 293 // Figure out if the result will fit in a long. We have to 294 // first look for nonzero digits after the decimal point; 295 // then check the size. 296 297 // Trim trailing zeros after the decimal point. This does not change 298 // the represented value. 299 while (fCount > fDecimalAt && fCount > 0 && fDigits[fCount - 1] == kZero) 300 --fCount; 301 302 if (fCount == 0) { 303 // Positive zero fits into a long, but negative zero can only 304 // be represented as a double. - bug 4162852 305 return fIsPositive || ignoreNegativeZero; 306 } 307 308 // If the digit list represents a double or this number is too 309 // big for a long. 310 if (fDecimalAt < fCount || fDecimalAt > LONG_MIN_REP_LENGTH) 311 return FALSE; 312 313 // If number is small enough to fit in a long 314 if (fDecimalAt < LONG_MIN_REP_LENGTH) 315 return TRUE; 316 317 // At this point we have fDecimalAt == fCount, and fCount == LONG_MIN_REP_LENGTH. 318 // The number will overflow if it is larger than LONG_MAX 319 // or smaller than LONG_MIN. 320 for (int32_t i=0; i<fCount; ++i) 321 { 322 char dig = fDigits[i], 323 max = LONG_MIN_REP[i]; 324 if (dig > max) 325 return FALSE; 326 if (dig < max) 327 return TRUE; 328 } 329 330 // At this point the first count digits match. If fDecimalAt is less 331 // than count, then the remaining digits are zero, and we return true. 332 if (fCount < fDecimalAt) 333 return TRUE; 334 335 // Now we have a representation of Long.MIN_VALUE, without the leading 336 // negative sign. If this represents a positive value, then it does 337 // not fit; otherwise it fits. 338 return !fIsPositive; 339 } 340 341 /** 342 * Return true if the number represented by this object can fit into 343 * a long. 344 */ 345 UBool 346 DigitList::fitsIntoInt64(UBool ignoreNegativeZero) /*const*/ 347 { 348 // Figure out if the result will fit in a long. We have to 349 // first look for nonzero digits after the decimal point; 350 // then check the size. 351 352 // Trim trailing zeros after the decimal point. This does not change 353 // the represented value. 354 while (fCount > fDecimalAt && fCount > 0 && fDigits[fCount - 1] == kZero) 355 --fCount; 356 357 if (fCount == 0) { 358 // Positive zero fits into a long, but negative zero can only 359 // be represented as a double. - bug 4162852 360 return fIsPositive || ignoreNegativeZero; 361 } 362 363 // If the digit list represents a double or this number is too 364 // big for a long. 365 if (fDecimalAt < fCount || fDecimalAt > I64_MIN_REP_LENGTH) 366 return FALSE; 367 368 // If number is small enough to fit in an int64 369 if (fDecimalAt < I64_MIN_REP_LENGTH) 370 return TRUE; 371 372 // At this point we have fDecimalAt == fCount, and fCount == INT64_MIN_REP_LENGTH. 373 // The number will overflow if it is larger than U_INT64_MAX 374 // or smaller than U_INT64_MIN. 375 for (int32_t i=0; i<fCount; ++i) 376 { 377 char dig = fDigits[i], 378 max = I64_MIN_REP[i]; 379 if (dig > max) 380 return FALSE; 381 if (dig < max) 382 return TRUE; 383 } 384 385 // At this point the first count digits match. If fDecimalAt is less 386 // than count, then the remaining digits are zero, and we return true. 387 if (fCount < fDecimalAt) 388 return TRUE; 389 390 // Now we have a representation of INT64_MIN_VALUE, without the leading 391 // negative sign. If this represents a positive value, then it does 392 // not fit; otherwise it fits. 393 return !fIsPositive; 394 } 395 396 397 // ------------------------------------- 398 399 void 400 DigitList::set(int32_t source, int32_t maximumDigits) 401 { 402 set((int64_t)source, maximumDigits); 403 } 404 405 // ------------------------------------- 406 /** 407 * @param maximumDigits The maximum digits to be generated. If zero, 408 * there is no maximum -- generate all digits. 409 */ 410 void 411 DigitList::set(int64_t source, int32_t maximumDigits) 412 { 413 fCount = fDecimalAt = formatBase10(source, fDecimalDigits, MAX_DIGITS); 414 415 fIsPositive = (*fDecimalDigits == '+'); 416 417 // Don't copy trailing zeros 418 while (fCount > 1 && fDigits[fCount - 1] == kZero) 419 --fCount; 420 421 if(maximumDigits > 0) 422 round(maximumDigits); 423 } 424 425 /** 426 * Set the digit list to a representation of the given double value. 427 * This method supports both fixed-point and exponential notation. 428 * @param source Value to be converted; must not be Inf, -Inf, Nan, 429 * or a value <= 0. 430 * @param maximumDigits The most fractional or total digits which should 431 * be converted. If total digits, and the value is zero, then 432 * there is no maximum -- generate all digits. 433 * @param fixedPoint If true, then maximumDigits is the maximum 434 * fractional digits to be converted. If false, total digits. 435 */ 436 void 437 DigitList::set(double source, int32_t maximumDigits, UBool fixedPoint) 438 { 439 // for now, simple implementation; later, do proper IEEE stuff 440 char rep[MAX_DIGITS + 8]; // Extra space for '+', '.', e+NNN, and '\0' (actually +8 is enough) 441 char *digitPtr = fDigits; 442 char *repPtr = rep + 2; // +2 to skip the sign and decimal 443 int32_t exponent = 0; 444 445 fIsPositive = !uprv_isNegative(source); // Allow +0 and -0 446 447 // Generate a representation of the form /[+-][0-9]+e[+-][0-9]+/ 448 sprintf(rep, "%+1.*e", MAX_DBL_DIGITS - 1, source); 449 fDecimalAt = 0; 450 rep[2] = rep[1]; // remove decimal 451 452 while (*repPtr == kZero) { 453 repPtr++; 454 fDecimalAt--; // account for leading zeros 455 } 456 457 while (*repPtr != 'e') { 458 *(digitPtr++) = *(repPtr++); 459 } 460 fCount = MAX_DBL_DIGITS + fDecimalAt; 461 462 // Parse an exponent of the form /[eE][+-][0-9]+/ 463 UBool negExp = (*(++repPtr) == '-'); 464 while (*(++repPtr) != 0) { 465 exponent = 10*exponent + *repPtr - kZero; 466 } 467 if (negExp) { 468 exponent = -exponent; 469 } 470 fDecimalAt += exponent + 1; // +1 for decimal removal 471 472 // The negative of the exponent represents the number of leading 473 // zeros between the decimal and the first non-zero digit, for 474 // a value < 0.1 (e.g., for 0.00123, -decimalAt == 2). If this 475 // is more than the maximum fraction digits, then we have an underflow 476 // for the printed representation. 477 if (fixedPoint && -fDecimalAt >= maximumDigits) 478 { 479 // If we round 0.0009 to 3 fractional digits, then we have to 480 // create a new one digit in the least significant location. 481 if (-fDecimalAt == maximumDigits && shouldRoundUp(0)) { 482 fCount = 1; 483 ++fDecimalAt; 484 fDigits[0] = (char)'1'; 485 } else { 486 // Handle an underflow to zero when we round something like 487 // 0.0009 to 2 fractional digits. 488 fCount = 0; 489 } 490 return; 491 } 492 493 494 // Eliminate digits beyond maximum digits to be displayed. 495 // Round up if appropriate. Do NOT round in the special 496 // case where maximumDigits == 0 and fixedPoint is FALSE. 497 if (fixedPoint || (0 < maximumDigits && maximumDigits < fCount)) { 498 round(fixedPoint ? (maximumDigits + fDecimalAt) : maximumDigits); 499 } 500 else { 501 // Eliminate trailing zeros. 502 while (fCount > 1 && fDigits[fCount - 1] == kZero) 503 --fCount; 504 } 505 } 506 507 // ------------------------------------- 508 509 /** 510 * Round the representation to the given number of digits. 511 * @param maximumDigits The maximum number of digits to be shown. 512 * Upon return, count will be less than or equal to maximumDigits. 513 */ 514 void 515 DigitList::round(int32_t maximumDigits) 516 { 517 // Eliminate digits beyond maximum digits to be displayed. 518 // Round up if appropriate. 519 if (maximumDigits >= 0 && maximumDigits < fCount) 520 { 521 if (shouldRoundUp(maximumDigits)) { 522 // Rounding up involved incrementing digits from LSD to MSD. 523 // In most cases this is simple, but in a worst case situation 524 // (9999..99) we have to adjust the decimalAt value. 525 while (--maximumDigits >= 0 && ++fDigits[maximumDigits] > '9') 526 ; 527 528 if (maximumDigits < 0) 529 { 530 // We have all 9's, so we increment to a single digit 531 // of one and adjust the exponent. 532 fDigits[0] = (char) '1'; 533 ++fDecimalAt; 534 maximumDigits = 1; // Adjust the count 535 } 536 else 537 { 538 ++maximumDigits; // Increment for use as count 539 } 540 } 541 fCount = maximumDigits; 542 } 543 544 // Eliminate trailing zeros. 545 while (fCount > 1 && fDigits[fCount-1] == kZero) { 546 --fCount; 547 } 548 } 549 550 /** 551 * Return true if truncating the representation to the given number 552 * of digits will result in an increment to the last digit. This 553 * method implements the requested rounding mode. 554 * [bnf] 555 * @param maximumDigits the number of digits to keep, from 0 to 556 * <code>count-1</code>. If 0, then all digits are rounded away, and 557 * this method returns true if a one should be generated (e.g., formatting 558 * 0.09 with "#.#"). 559 * @return true if digit <code>maximumDigits-1</code> should be 560 * incremented 561 */ 562 UBool DigitList::shouldRoundUp(int32_t maximumDigits) const { 563 int i = 0; 564 if (fRoundingMode == DecimalFormat::kRoundDown || 565 fRoundingMode == DecimalFormat::kRoundFloor && fIsPositive || 566 fRoundingMode == DecimalFormat::kRoundCeiling && !fIsPositive) { 567 return FALSE; 568 } 569 570 if (fRoundingMode == DecimalFormat::kRoundHalfEven || 571 fRoundingMode == DecimalFormat::kRoundHalfDown || 572 fRoundingMode == DecimalFormat::kRoundHalfUp) { 573 if (fDigits[maximumDigits] == '5' ) { 574 for (i=maximumDigits+1; i<fCount; ++i) { 575 if (fDigits[i] != kZero) { 576 return TRUE; 577 } 578 } 579 switch (fRoundingMode) { 580 case DecimalFormat::kRoundHalfEven: 581 default: 582 // Implement IEEE half-even rounding 583 return maximumDigits > 0 && (fDigits[maximumDigits-1] % 2 != 0); 584 case DecimalFormat::kRoundHalfDown: 585 return FALSE; 586 case DecimalFormat::kRoundHalfUp: 587 return TRUE; 588 } 589 } 590 return (fDigits[maximumDigits] > '5'); 591 } 592 593 U_ASSERT(fRoundingMode == DecimalFormat::kRoundUp || 594 fRoundingMode == DecimalFormat::kRoundFloor && !fIsPositive || 595 fRoundingMode == DecimalFormat::kRoundCeiling && fIsPositive); 596 597 for (i=maximumDigits; i<fCount; ++i) { 598 if (fDigits[i] != kZero) { 599 return TRUE; 600 } 601 } 602 return false; 603 } 604 605 // ------------------------------------- 606 607 // In the Java implementation, we need a separate set(long) because 64-bit longs 608 // have too much precision to fit into a 64-bit double. In C++, longs can just 609 // be passed to set(double) as long as they are 32 bits in size. We currently 610 // don't implement 64-bit longs in C++, although the code below would work for 611 // that with slight modifications. [LIU] 612 /* 613 void 614 DigitList::set(long source) 615 { 616 // handle the special case of zero using a standard exponent of 0. 617 // mathematically, the exponent can be any value. 618 if (source == 0) 619 { 620 fcount = 0; 621 fDecimalAt = 0; 622 return; 623 } 624 625 // we don't accept negative numbers, with the exception of long_min. 626 // long_min is treated specially by being represented as long_max+1, 627 // which is actually an impossible signed long value, so there is no 628 // ambiguity. we do this for convenience, so digitlist can easily 629 // represent the digits of a long. 630 bool islongmin = (source == long_min); 631 if (islongmin) 632 { 633 source = -(source + 1); // that is, long_max 634 islongmin = true; 635 } 636 sprintf(fdigits, "%d", source); 637 638 // now we need to compute the exponent. it's easy in this case; it's 639 // just the same as the count. e.g., 0.123 * 10^3 = 123. 640 fcount = strlen(fdigits); 641 fDecimalAt = fcount; 642 643 // here's how we represent long_max + 1. note that we always know 644 // that the last digit of long_max will not be 9, because long_max 645 // is of the form (2^n)-1. 646 if (islongmin) 647 ++fdigits[fcount-1]; 648 649 // finally, we trim off trailing zeros. we don't alter fDecimalAt, 650 // so this has no effect on the represented value. we know the first 651 // digit is non-zero (see code above), so we only have to check down 652 // to fdigits[1]. 653 while (fcount > 1 && fdigits[fcount-1] == kzero) 654 --fcount; 655 } 656 */ 657 658 /** 659 * Return true if this object represents the value zero. Anything with 660 * no digits, or all zero digits, is zero, regardless of fDecimalAt. 661 */ 662 UBool 663 DigitList::isZero() const 664 { 665 for (int32_t i=0; i<fCount; ++i) 666 if (fDigits[i] != kZero) 667 return FALSE; 668 return TRUE; 669 } 670 671 U_NAMESPACE_END 672 #endif // #if !UCONFIG_NO_FORMATTING 673 674 //eof 675