Source/WTF/wtf/dtoa/double-conversion.cc - Issue 14238015: Move Source/WTF/wtf to Source/wtf

Side by Side Diff: Source/WTF/wtf/dtoa/double-conversion.cc

Issue 14238015: Move Source/WTF/wtf to Source/wtf (Closed) Base URL: svn://svn.chromium.org/blink/trunk

Patch Set: Created 7 years, 8 months ago

Use n/p to move between diff chunks; N/P to move between comments. Draft comments are only viewable by you.

Jump to:

View unified diff | Download patch | Annotate | Revision Log

OLD	NEW
	(Empty)
1 // Copyright 2010 the V8 project authors. All rights reserved.

2 // Redistribution and use in source and binary forms, with or without

3 // modification, are permitted provided that the following conditions are

4 // met:

5 //

6 // * Redistributions of source code must retain the above copyright

7 // notice, this list of conditions and the following disclaimer.

8 // * Redistributions in binary form must reproduce the above

9 // copyright notice, this list of conditions and the following

10 // disclaimer in the documentation and/or other materials provided

11 // with the distribution.

12 // * Neither the name of Google Inc. nor the names of its

13 // contributors may be used to endorse or promote products derived

14 // from this software without specific prior written permission.

15 //

16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS

17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT

18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR

19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT

20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,

21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT

22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,

23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY

24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT

25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE

26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.

27

28 #include "config.h"

29

30 #include <limits.h>

31 #include <math.h>

32

33 #include "double-conversion.h"

34

35 #include "bignum-dtoa.h"

36 #include "double.h"

37 #include "fast-dtoa.h"

38 #include "fixed-dtoa.h"

39 #include "strtod.h"

40 #include "utils.h"

41

42 namespace WTF {

43

44 namespace double_conversion {

45

46 const DoubleToStringConverter& DoubleToStringConverter::EcmaScriptConverter( ) {

47 int flags = UNIQUE_ZERO \| EMIT_POSITIVE_EXPONENT_SIGN;

48 static DoubleToStringConverter converter(flags,

49 "Infinity",

50 "NaN",

51 'e',

52 -6, 21,

53 6, 0);

54 return converter;

55 }

56

57

58 bool DoubleToStringConverter::HandleSpecialValues(

59 double value,

60 StringBuilder* result_buil der) const {

61 Double double_inspect(value);

62 if (double_inspect.IsInfinite()) {

63 if (infinity_symbol_ == NULL) return false;

64 if (value < 0) {

65 result_builder->AddCharacter('-');

66 }

67 result_builder->AddString(infinity_symbol_);

68 return true;

69 }

70 if (double_inspect.IsNan()) {

71 if (nan_symbol_ == NULL) return false;

72 result_builder->AddString(nan_symbol_);

73 return true;

74 }

75 return false;

76 }

77

78

79 void DoubleToStringConverter::CreateExponentialRepresentation(

80 const char* de cimal_digits,

81 int length,

82 int exponent,

83 StringBuilder* result_builder) const {

84 ASSERT(length != 0);

85 result_builder->AddCharacter(decimal_digits[0]);

86 if (length != 1) {

87 result_builder->AddCharacter('.');

88 result_builder->AddSubstring(&decimal_digits[1], length-1);

89 }

90 result_builder->AddCharacter(exponent_character_);

91 if (exponent < 0) {

92 result_builder->AddCharacter('-');

93 exponent = -exponent;

94 } else {

95 if ((flags_ & EMIT_POSITIVE_EXPONENT_SIGN) != 0) {

96 result_builder->AddCharacter('+');

97 }

98 }

99 if (exponent == 0) {

100 result_builder->AddCharacter('0');

101 return;

102 }

103 ASSERT(exponent < 1e4);

104 const int kMaxExponentLength = 5;

105 char buffer[kMaxExponentLength + 1];

106 int first_char_pos = kMaxExponentLength;

107 buffer[first_char_pos] = '\0';

108 while (exponent > 0) {

109 buffer[--first_char_pos] = '0' + (exponent % 10);

110 exponent /= 10;

111 }

112 result_builder->AddSubstring(&buffer[first_char_pos],

113 kMaxExponentLength - first_char_pos);

114 }

115

116

117 void DoubleToStringConverter::CreateDecimalRepresentation(

118 const char* decima l_digits,

119 int length,

120 int decimal_point,

121 int digits_after_p oint,

122 StringBuilder* res ult_builder) const {

123 // Create a representation that is padded with zeros if needed.

124 if (decimal_point <= 0) {

125 // "0.00000decimal_rep".

126 result_builder->AddCharacter('0');

127 if (digits_after_point > 0) {

128 result_builder->AddCharacter('.');

129 result_builder->AddPadding('0', -decimal_point);

130 ASSERT(length <= digits_after_point - (-decimal_point));

131 result_builder->AddSubstring(decimal_digits, length);

132 int remaining_digits = digits_after_point - (-decimal_point) - l ength;

133 result_builder->AddPadding('0', remaining_digits);

134 }

135 } else if (decimal_point >= length) {

136 // "decimal_rep0000.00000" or "decimal_rep.0000"

137 result_builder->AddSubstring(decimal_digits, length);

138 result_builder->AddPadding('0', decimal_point - length);

139 if (digits_after_point > 0) {

140 result_builder->AddCharacter('.');

141 result_builder->AddPadding('0', digits_after_point);

142 }

143 } else {

144 // "decima.l_rep000"

145 ASSERT(digits_after_point > 0);

146 result_builder->AddSubstring(decimal_digits, decimal_point);

147 result_builder->AddCharacter('.');

148 ASSERT(length - decimal_point <= digits_after_point);

149 result_builder->AddSubstring(&decimal_digits[decimal_point],

150 length - decimal_point);

151 int remaining_digits = digits_after_point - (length - decimal_point) ;

152 result_builder->AddPadding('0', remaining_digits);

153 }

154 if (digits_after_point == 0) {

155 if ((flags_ & EMIT_TRAILING_DECIMAL_POINT) != 0) {

156 result_builder->AddCharacter('.');

157 }

158 if ((flags_ & EMIT_TRAILING_ZERO_AFTER_POINT) != 0) {

159 result_builder->AddCharacter('0');

160 }

161 }

162 }

163

164

165 bool DoubleToStringConverter::ToShortest(double value,

166 StringBuilder* result_builder) cons t {

167 if (Double(value).IsSpecial()) {

168 return HandleSpecialValues(value, result_builder);

169 }

170

171 int decimal_point;

172 bool sign;

173 const int kDecimalRepCapacity = kBase10MaximalLength + 1;

174 char decimal_rep[kDecimalRepCapacity];

175 int decimal_rep_length;

176

177 DoubleToAscii(value, SHORTEST, 0, decimal_rep, kDecimalRepCapacity,

178 &sign, &decimal_rep_length, &decimal_point);

179

180 bool unique_zero = (flags_ & UNIQUE_ZERO) != 0;

181 if (sign && (value != 0.0 \|\| !unique_zero)) {

182 result_builder->AddCharacter('-');

183 }

184

185 int exponent = decimal_point - 1;

186 if ((decimal_in_shortest_low_ <= exponent) &&

187 (exponent < decimal_in_shortest_high_)) {

188 CreateDecimalRepresentation(decimal_rep, decimal_rep_length,

189 decimal_point,

190 Max(0, decimal_rep_length - decimal_poin t),

191 result_builder);

192 } else {

193 CreateExponentialRepresentation(decimal_rep, decimal_rep_length, exp onent,

194 result_builder);

195 }

196 return true;

197 }

198

199

200 bool DoubleToStringConverter::ToFixed(double value,

201 int requested_digits,

202 StringBuilder* result_builder) const {

203 ASSERT(kMaxFixedDigitsBeforePoint == 60);

204 const double kFirstNonFixed = 1e60;

205

206 if (Double(value).IsSpecial()) {

207 return HandleSpecialValues(value, result_builder);

208 }

209

210 if (requested_digits > kMaxFixedDigitsAfterPoint) return false;

211 if (value >= kFirstNonFixed \|\| value <= -kFirstNonFixed) return false;

212

213 // Find a sufficiently precise decimal representation of n.

214 int decimal_point;

215 bool sign;

216 // Add space for the '\0' byte.

217 const int kDecimalRepCapacity =

218 kMaxFixedDigitsBeforePoint + kMaxFixedDigitsAfterPoint + 1;

219 char decimal_rep[kDecimalRepCapacity];

220 int decimal_rep_length;

221 DoubleToAscii(value, FIXED, requested_digits,

222 decimal_rep, kDecimalRepCapacity,

223 &sign, &decimal_rep_length, &decimal_point);

224

225 bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0);

226 if (sign && (value != 0.0 \|\| !unique_zero)) {

227 result_builder->AddCharacter('-');

228 }

229

230 CreateDecimalRepresentation(decimal_rep, decimal_rep_length, decimal_poi nt,

231 requested_digits, result_builder);

232 return true;

233 }

234

235

236 bool DoubleToStringConverter::ToExponential(

237 double value,

238 int requested_digits,

239 StringBuilder* result_builder) c onst {

240 if (Double(value).IsSpecial()) {

241 return HandleSpecialValues(value, result_builder);

242 }

243

244 if (requested_digits < -1) return false;

245 if (requested_digits > kMaxExponentialDigits) return false;

246

247 int decimal_point;

248 bool sign;

249 // Add space for digit before the decimal point and the '\0' character.

250 const int kDecimalRepCapacity = kMaxExponentialDigits + 2;

251 ASSERT(kDecimalRepCapacity > kBase10MaximalLength);

252 char decimal_rep[kDecimalRepCapacity];

253 int decimal_rep_length;

254

255 if (requested_digits == -1) {

256 DoubleToAscii(value, SHORTEST, 0,

257 decimal_rep, kDecimalRepCapacity,

258 &sign, &decimal_rep_length, &decimal_point);

259 } else {

260 DoubleToAscii(value, PRECISION, requested_digits + 1,

261 decimal_rep, kDecimalRepCapacity,

262 &sign, &decimal_rep_length, &decimal_point);

263 ASSERT(decimal_rep_length <= requested_digits + 1);

264

265 for (int i = decimal_rep_length; i < requested_digits + 1; ++i) {

266 decimal_rep[i] = '0';

267 }

268 decimal_rep_length = requested_digits + 1;

269 }

270

271 bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0);

272 if (sign && (value != 0.0 \|\| !unique_zero)) {

273 result_builder->AddCharacter('-');

274 }

275

276 int exponent = decimal_point - 1;

277 CreateExponentialRepresentation(decimal_rep,

278 decimal_rep_length,

279 exponent,

280 result_builder);

281 return true;

282 }

283

284

285 bool DoubleToStringConverter::ToPrecision(double value,

286 int precision,

287 StringBuilder* result_builder) con st {

288 if (Double(value).IsSpecial()) {

289 return HandleSpecialValues(value, result_builder);

290 }

291

292 if (precision < kMinPrecisionDigits \|\| precision > kMaxPrecisionDigits) {

293 return false;

294 }

295

296 // Find a sufficiently precise decimal representation of n.

297 int decimal_point;

298 bool sign;

299 // Add one for the terminating null character.

300 const int kDecimalRepCapacity = kMaxPrecisionDigits + 1;

301 char decimal_rep[kDecimalRepCapacity];

302 int decimal_rep_length;

303

304 DoubleToAscii(value, PRECISION, precision,

305 decimal_rep, kDecimalRepCapacity,

306 &sign, &decimal_rep_length, &decimal_point);

307 ASSERT(decimal_rep_length <= precision);

308

309 bool unique_zero = ((flags_ & UNIQUE_ZERO) != 0);

310 if (sign && (value != 0.0 \|\| !unique_zero)) {

311 result_builder->AddCharacter('-');

312 }

313

314 // The exponent if we print the number as x.xxeyyy. That is with the

315 // decimal point after the first digit.

316 int exponent = decimal_point - 1;

317

318 int extra_zero = ((flags_ & EMIT_TRAILING_ZERO_AFTER_POINT) != 0) ? 1 : 0;

319 if ((-decimal_point + 1 > max_leading_padding_zeroes_in_precision_mode_) \|\|

320 (decimal_point - precision + extra_zero >

321 max_trailing_padding_zeroes_in_precision_mode_)) {

322 // Fill buffer to contain 'precision' digits.

323 // Usually the buffer is already at the correct length, but 'Dou bleToAscii'

324 // is allowed to return less characters.

325 for (int i = decimal_rep_length; i < precision; ++i) {

326 decimal_rep[i] = '0';

327 }

328

329 CreateExponentialRepresentation(decimal_rep,

330 precision,

331 exponent,

332 result_builder);

333 } else {

334 CreateDecimalRepresentation(decimal_rep, decimal_rep_length, dec imal_point,

335 Max(0, precision - decimal_point),

336 result_builder);

337 }

338 return true;

339 }

340

341

342 static BignumDtoaMode DtoaToBignumDtoaMode(

343 DoubleToStringConverter::DtoaMode dtoa_mode) {

344 switch (dtoa_mode) {

345 case DoubleToStringConverter::SHORTEST: return BIGNUM_DTOA_SHORTEST ;

346 case DoubleToStringConverter::FIXED: return BIGNUM_DTOA_FIXED;

347 case DoubleToStringConverter::PRECISION: return BIGNUM_DTOA_PRECISIO N;

348 default:

349 UNREACHABLE();

350 return BIGNUM_DTOA_SHORTEST; // To silence compiler.

351 }

352 }

353

354

355 void DoubleToStringConverter::DoubleToAscii(double v,

356 DtoaMode mode,

357 int requested_digits,

358 char* buffer,

359 int buffer_length,

360 bool* sign,

361 int* length,

362 int* point) {

363 Vector<char> vector(buffer, buffer_length);

364 ASSERT(!Double(v).IsSpecial());

365 ASSERT(mode == SHORTEST \|\| requested_digits >= 0);

366

367 if (Double(v).Sign() < 0) {

368 *sign = true;

369 v = -v;

370 } else {

371 *sign = false;

372 }

373

374 if (mode == PRECISION && requested_digits == 0) {

375 vector[0] = '\0';

376 *length = 0;

377 return;

378 }

379

380 if (v == 0) {

381 vector[0] = '0';

382 vector[1] = '\0';

383 *length = 1;

384 *point = 1;

385 return;

386 }

387

388 bool fast_worked;

389 switch (mode) {

390 case SHORTEST:

391 fast_worked = FastDtoa(v, FAST_DTOA_SHORTEST, 0, vector, length, point);

392 break;

393 case FIXED:

394 fast_worked = FastFixedDtoa(v, requested_digits, vector, length, point);

395 break;

396 case PRECISION:

397 fast_worked = FastDtoa(v, FAST_DTOA_PRECISION, requested_digits,

398 vector, length, point);

399 break;

400 default:

401 UNREACHABLE();

402 fast_worked = false;

403 }

404 if (fast_worked) return;

405

406 // If the fast dtoa didn't succeed use the slower bignum version.

407 BignumDtoaMode bignum_mode = DtoaToBignumDtoaMode(mode);

408 BignumDtoa(v, bignum_mode, requested_digits, vector, length, point);

409 vector[*length] = '\0';

410 }

411

412

413 // Maximum number of significant digits in decimal representation.

414 // The longest possible double in decimal representation is

415 // (2^53 - 1) * 2 ^ -1074 that is (2 ^ 53 - 1) * 5 ^ 1074 / 10 ^ 1074

416 // (768 digits). If we parse a number whose first digits are equal to a

417 // mean of 2 adjacent doubles (that could have up to 769 digits) the result

418 // must be rounded to the bigger one unless the tail consists of zeros, so

419 // we don't need to preserve all the digits.

420 const int kMaxSignificantDigits = 772;

421

422

423 static double SignedZero(bool sign) {

424 return sign ? -0.0 : 0.0;

425 }

426

427

428 double StringToDoubleConverter::StringToDouble(

429 const char* input,

430 size_t length,

431 size_t* processed_characters_ count) {

432 const char* current = input;

433 const char* end = input + length;

434

435 *processed_characters_count = 0;

436

437 // To make sure that iterator dereferencing is valid the following

438 // convention is used:

439 // 1. Each '++current' statement is followed by check for equality to 'e nd'.

440 // 3. If 'current' becomes equal to 'end' the function returns or goes t o

441 // 'parsing_done'.

442 // 4. 'current' is not dereferenced after the 'parsing_done' label.

443 // 5. Code before 'parsing_done' may rely on 'current != end'.

444 if (current == end) return 0.0;

445

446 // The longest form of simplified number is: "-<significant digits>.1eXX X\0".

447 const int kBufferSize = kMaxSignificantDigits + 10;

448 char buffer[kBufferSize]; // NOLINT: size is known at compile time.

449 int buffer_pos = 0;

450

451 // Exponent will be adjusted if insignificant digits of the integer part

452 // or insignificant leading zeros of the fractional part are dropped.

453 int exponent = 0;

454 int significant_digits = 0;

455 int insignificant_digits = 0;

456 bool nonzero_digit_dropped = false;

457 bool sign = false;

458

459 if (current == '+' \|\| current == '-') {

460 sign = (*current == '-');

461 ++current;

462 if (current == end) return 0.0;

463 }

464

465 bool leading_zero = false;

466 if (*current == '0') {

467 ++current;

468 if (current == end) {

469 *processed_characters_count = current - input;

470 return SignedZero(sign);

471 }

472

473 leading_zero = true;

474

475 // Ignore leading zeros in the integer part.

476 while (*current == '0') {

477 ++current;

478 if (current == end) {

479 *processed_characters_count = current - input;

480 return SignedZero(sign);

481 }

482 }

483 }

484

485 // Copy significant digits of the integer part (if any) to the buffer.

486 while (current >= '0' && current <= '9') {

487 if (significant_digits < kMaxSignificantDigits) {

488 ASSERT(buffer_pos < kBufferSize);

489 buffer[buffer_pos++] = static_cast<char>(*current);

490 significant_digits++;

491 } else {

492 insignificant_digits++; // Move the digit into the exponential part.

493 nonzero_digit_dropped = nonzero_digit_dropped \|\| *current != '0' ;

494 }

495 ++current;

496 if (current == end) goto parsing_done;

497 }

498

499 if (*current == '.') {

500 ++current;

501 if (current == end) {

502 if (significant_digits == 0 && !leading_zero) {

503 return 0.0;

504 } else {

505 goto parsing_done;

506 }

507 }

508

509 if (significant_digits == 0) {

510 // Integer part consists of 0 or is absent. Significant digits s tart after

511 // leading zeros (if any).

512 while (*current == '0') {

513 ++current;

514 if (current == end) {

515 *processed_characters_count = current - input;

516 return SignedZero(sign);

517 }

518 exponent--; // Move this 0 into the exponent.

519 }

520 }

521

522 // There is a fractional part.

523 while (current >= '0' && current <= '9') {

524 if (significant_digits < kMaxSignificantDigits) {

525 ASSERT(buffer_pos < kBufferSize);

526 buffer[buffer_pos++] = static_cast<char>(*current);

527 significant_digits++;

528 exponent--;

529 } else {

530 // Ignore insignificant digits in the fractional part.

531 nonzero_digit_dropped = nonzero_digit_dropped \|\| *current != '0';

532 }

533 ++current;

534 if (current == end) goto parsing_done;

535 }

536 }

537

538 if (!leading_zero && exponent == 0 && significant_digits == 0) {

539 // If leading_zeros is true then the string contains zeros.

540 // If exponent < 0 then string was [+-]\.0*...

541 // If significant_digits != 0 the string is not equal to 0.

542 // Otherwise there are no digits in the string.

543 return 0.0;

544 }

545

546 // Parse exponential part.

547 if (current == 'e' \|\| current == 'E') {

548 ++current;

549 if (current == end) {

550 --current;

551 goto parsing_done;

552 }

553 char sign = 0;

554 if (current == '+' \|\| current == '-') {

555 sign = static_cast<char>(*current);

556 ++current;

557 if (current == end) {

558 current -= 2;

559 goto parsing_done;

560 }

561 }

562

563 if (current < '0' \|\| current > '9') {

564 if (sign)

565 --current;

566 --current;

567 goto parsing_done;

568 }

569

570 const int max_exponent = INT_MAX / 2;

571 ASSERT(-max_exponent / 2 <= exponent && exponent <= max_exponent / 2 );

572 int num = 0;

573 do {

574 // Check overflow.

575 int digit = *current - '0';

576 if (num >= max_exponent / 10

577 && !(num == max_exponent / 10 && digit <= max_exponent % 10) ) {

578 num = max_exponent;

579 } else {

580 num = num * 10 + digit;

581 }

582 ++current;

583 } while (current != end && current >= '0' && current <= '9');

584

585 exponent += (sign == '-' ? -num : num);

586 }

587

588 parsing_done:

589 exponent += insignificant_digits;

590

591 if (nonzero_digit_dropped) {

592 buffer[buffer_pos++] = '1';

593 exponent--;

594 }

595

596 ASSERT(buffer_pos < kBufferSize);

597 buffer[buffer_pos] = '\0';

598

599 double converted = Strtod(Vector<const char>(buffer, buffer_pos), expone nt);

600 *processed_characters_count = current - input;

601 return sign? -converted: converted;

602 }

603

604 } // namespace double_conversion

605

606 } // namespace WTF

OLD	NEW

« no previous file with comments | « Source/WTF/wtf/dtoa/double-conversion.h ('k') | Source/WTF/wtf/dtoa/fast-dtoa.h » ('j') | Source/config.h » ('J')