OLD | NEW |
1 // Copyright 2010 the V8 project authors. All rights reserved. | 1 // Copyright 2010 the V8 project authors. All rights reserved. |
2 // Redistribution and use in source and binary forms, with or without | 2 // Redistribution and use in source and binary forms, with or without |
3 // modification, are permitted provided that the following conditions are | 3 // modification, are permitted provided that the following conditions are |
4 // met: | 4 // met: |
5 // | 5 // |
6 // * Redistributions of source code must retain the above copyright | 6 // * Redistributions of source code must retain the above copyright |
7 // notice, this list of conditions and the following disclaimer. | 7 // notice, this list of conditions and the following disclaimer. |
8 // * Redistributions in binary form must reproduce the above | 8 // * Redistributions in binary form must reproduce the above |
9 // copyright notice, this list of conditions and the following | 9 // copyright notice, this list of conditions and the following |
10 // disclaimer in the documentation and/or other materials provided | 10 // disclaimer in the documentation and/or other materials provided |
(...skipping 56 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
67 // Generates w's digits. The result is the shortest in the interval low-high. | 67 // Generates w's digits. The result is the shortest in the interval low-high. |
68 // All DiyFp are assumed to be imprecise and this function takes this | 68 // All DiyFp are assumed to be imprecise and this function takes this |
69 // imprecision into account. If the function cannot compute the best | 69 // imprecision into account. If the function cannot compute the best |
70 // representation (due to the imprecision) then false is returned. | 70 // representation (due to the imprecision) then false is returned. |
71 static bool DigitGen_m60_m32(DiyFp low, DiyFp w, DiyFp high, | 71 static bool DigitGen_m60_m32(DiyFp low, DiyFp w, DiyFp high, |
72 char* buffer, int* length, int* kappa); | 72 char* buffer, int* length, int* kappa); |
73 }; | 73 }; |
74 | 74 |
75 | 75 |
76 template<int alpha, int gamma> | 76 template<int alpha, int gamma> |
77 bool Grisu3<alpha, gamma>::grisu3( | 77 bool Grisu3<alpha, gamma>::grisu3(double v, |
78 double v, char* buffer, int* length, int* decimal_exponent) { | 78 char* buffer, |
| 79 int* length, |
| 80 int* decimal_exponent) { |
79 DiyFp w = Double(v).AsNormalizedDiyFp(); | 81 DiyFp w = Double(v).AsNormalizedDiyFp(); |
80 // boundary_minus and boundary_plus are the boundaries between v and its | 82 // boundary_minus and boundary_plus are the boundaries between v and its |
81 // neighbors. Any number strictly between boundary_minus and boundary_plus | 83 // neighbors. Any number strictly between boundary_minus and boundary_plus |
82 // will round to v when read as double. | 84 // will round to v when read as double. |
83 // Grisu3 will never output representations that lie exactly on a boundary. | 85 // Grisu3 will never output representations that lie exactly on a boundary. |
84 DiyFp boundary_minus, boundary_plus; | 86 DiyFp boundary_minus, boundary_plus; |
85 Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus); | 87 Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus); |
86 ASSERT(boundary_plus.e() == w.e()); | 88 ASSERT(boundary_plus.e() == w.e()); |
87 DiyFp ten_mk; // Cached power of ten: 10^-k | 89 DiyFp ten_mk; // Cached power of ten: 10^-k |
88 int mk; // -k | 90 int mk; // -k |
(...skipping 51 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
140 // * buffer contains the shortest possible decimal digit-sequence | 142 // * buffer contains the shortest possible decimal digit-sequence |
141 // such that LOW < buffer * 10^kappa < HIGH, where LOW and HIGH are the | 143 // such that LOW < buffer * 10^kappa < HIGH, where LOW and HIGH are the |
142 // correct values of low and high (without their error). | 144 // correct values of low and high (without their error). |
143 // * if more than one decimal representation gives the minimal number of | 145 // * if more than one decimal representation gives the minimal number of |
144 // decimal digits then the one closest to W (where W is the correct value | 146 // decimal digits then the one closest to W (where W is the correct value |
145 // of w) is chosen. | 147 // of w) is chosen. |
146 // Remark: this procedure takes into account the imprecision of its input | 148 // Remark: this procedure takes into account the imprecision of its input |
147 // numbers. If the precision is not enough to guarantee all the postconditions | 149 // numbers. If the precision is not enough to guarantee all the postconditions |
148 // then false is returned. This usually happens rarely (~0.5%). | 150 // then false is returned. This usually happens rarely (~0.5%). |
149 template<int alpha, int gamma> | 151 template<int alpha, int gamma> |
150 bool Grisu3<alpha, gamma>::DigitGen( | 152 bool Grisu3<alpha, gamma>::DigitGen(DiyFp low, |
151 DiyFp low, DiyFp w, DiyFp high, char* buffer, int* len, int* kappa) { | 153 DiyFp w, |
| 154 DiyFp high, |
| 155 char* buffer, |
| 156 int* len, |
| 157 int* kappa) { |
152 ASSERT(low.e() == w.e() && w.e() == high.e()); | 158 ASSERT(low.e() == w.e() && w.e() == high.e()); |
153 ASSERT(low.f() + 1 <= high.f() - 1); | 159 ASSERT(low.f() + 1 <= high.f() - 1); |
154 ASSERT(alpha <= w.e() && w.e() <= gamma); | 160 ASSERT(alpha <= w.e() && w.e() <= gamma); |
155 // The following tests use alpha and gamma to avoid unnecessary dynamic tests. | 161 // The following tests use alpha and gamma to avoid unnecessary dynamic tests. |
156 if ((alpha >= -60 && gamma <= -32) || // -60 <= w.e() <= -32 | 162 if ((alpha >= -60 && gamma <= -32) || // -60 <= w.e() <= -32 |
157 (alpha <= -32 && gamma >= -60 && // Alpha/gamma overlaps -60/-32 region. | 163 (alpha <= -32 && gamma >= -60 && // Alpha/gamma overlaps -60/-32 region. |
158 -60 <= w.e() && w.e() <= -32)) { | 164 -60 <= w.e() && w.e() <= -32)) { |
159 return DigitGen_m60_m32(low, w, high, buffer, len, kappa); | 165 return DigitGen_m60_m32(low, w, high, buffer, len, kappa); |
160 } else { | 166 } else { |
161 // A simple adaption of the special case -60/-32 would allow greater ranges | 167 // A simple adaption of the special case -60/-32 would allow greater ranges |
162 // of alpha/gamma and thus reduce the number of precomputed cached powers of | 168 // of alpha/gamma and thus reduce the number of precomputed cached powers of |
163 // ten. | 169 // ten. |
164 UNIMPLEMENTED(); | 170 UNIMPLEMENTED(); |
165 return false; | 171 return false; |
166 } | 172 } |
167 } | 173 } |
168 | 174 |
169 static const uint32_t kTen4 = 10000; | 175 static const uint32_t kTen4 = 10000; |
170 static const uint32_t kTen5 = 100000; | 176 static const uint32_t kTen5 = 100000; |
171 static const uint32_t kTen6 = 1000000; | 177 static const uint32_t kTen6 = 1000000; |
172 static const uint32_t kTen7 = 10000000; | 178 static const uint32_t kTen7 = 10000000; |
173 static const uint32_t kTen8 = 100000000; | 179 static const uint32_t kTen8 = 100000000; |
174 static const uint32_t kTen9 = 1000000000; | 180 static const uint32_t kTen9 = 1000000000; |
175 | 181 |
176 // Returns the biggest power of ten that is <= than the given number. We | 182 // Returns the biggest power of ten that is <= than the given number. We |
177 // furthermore receive the maximum number of bits 'number' has. | 183 // furthermore receive the maximum number of bits 'number' has. |
178 // If number_bits == 0 then 0^-1 is returned | 184 // If number_bits == 0 then 0^-1 is returned |
179 // The number of bits must be <= 32. | 185 // The number of bits must be <= 32. |
180 static void BiggestPowerTen(uint32_t number, int number_bits, | 186 static void BiggestPowerTen(uint32_t number, |
181 uint32_t* power, int* exponent) { | 187 int number_bits, |
| 188 uint32_t* power, |
| 189 int* exponent) { |
182 switch (number_bits) { | 190 switch (number_bits) { |
183 case 32: | 191 case 32: |
184 case 31: | 192 case 31: |
185 case 30: | 193 case 30: |
186 if (kTen9 <= number) { | 194 if (kTen9 <= number) { |
187 *power = kTen9; | 195 *power = kTen9; |
188 *exponent = 9; | 196 *exponent = 9; |
189 break; | 197 break; |
190 } // else fallthrough | 198 } // else fallthrough |
191 case 29: | 199 case 29: |
(...skipping 95 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
287 // Printing w's integral part is easy (simply print 0x1234 in decimal). | 295 // Printing w's integral part is easy (simply print 0x1234 in decimal). |
288 // In order to print its fraction we repeatedly multiply the fraction by 10 and | 296 // In order to print its fraction we repeatedly multiply the fraction by 10 and |
289 // get each digit. Example the first digit after the comma would be computed by | 297 // get each digit. Example the first digit after the comma would be computed by |
290 // (0x567890abcdef * 10) >> 48. -> 3 | 298 // (0x567890abcdef * 10) >> 48. -> 3 |
291 // The whole thing becomes slightly more complicated because we want to stop | 299 // The whole thing becomes slightly more complicated because we want to stop |
292 // once we have enough digits. That is, once the digits inside the buffer | 300 // once we have enough digits. That is, once the digits inside the buffer |
293 // represent 'w' we can stop. Everything inside the interval low - high | 301 // represent 'w' we can stop. Everything inside the interval low - high |
294 // represents w. However we have to pay attention to low, high and w's | 302 // represents w. However we have to pay attention to low, high and w's |
295 // imprecision. | 303 // imprecision. |
296 template<int alpha, int gamma> | 304 template<int alpha, int gamma> |
297 bool Grisu3<alpha, gamma>::DigitGen_m60_m32( | 305 bool Grisu3<alpha, gamma>::DigitGen_m60_m32(DiyFp low, |
298 DiyFp low, DiyFp w, DiyFp high, char* buffer, int* length, int* kappa) { | 306 DiyFp w, |
| 307 DiyFp high, |
| 308 char* buffer, |
| 309 int* length, |
| 310 int* kappa) { |
299 // low, w and high are imprecise, but by less than one ulp (unit in the last | 311 // low, w and high are imprecise, but by less than one ulp (unit in the last |
300 // place). | 312 // place). |
301 // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that | 313 // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that |
302 // the new numbers are outside of the interval we want the final | 314 // the new numbers are outside of the interval we want the final |
303 // representation to lie in. | 315 // representation to lie in. |
304 // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield | 316 // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield |
305 // numbers that are certain to lie in the interval. We will use this fact | 317 // numbers that are certain to lie in the interval. We will use this fact |
306 // later on. | 318 // later on. |
307 // We will now start by generating the digits within the uncertain | 319 // We will now start by generating the digits within the uncertain |
308 // interval. Later we will weed out representations that lie outside the safe | 320 // interval. Later we will weed out representations that lie outside the safe |
309 // interval and thus _might_ lie outside the correct interval. | 321 // interval and thus _might_ lie outside the correct interval. |
310 uint64_t unit = 1; | 322 uint64_t unit = 1; |
311 DiyFp too_low = DiyFp(low.f() - unit, low.e()); | 323 DiyFp too_low = DiyFp(low.f() - unit, low.e()); |
312 DiyFp too_high = DiyFp(high.f() + unit, high.e()); | 324 DiyFp too_high = DiyFp(high.f() + unit, high.e()); |
313 // too_low and too_high are guaranteed to lie outside the interval we want the | 325 // too_low and too_high are guaranteed to lie outside the interval we want the |
314 // generated number in. | 326 // generated number in. |
315 DiyFp unsafe_interval = DiyFp::Minus(too_high, too_low); | 327 DiyFp unsafe_interval = DiyFp::Minus(too_high, too_low); |
316 // We now cut the input number into two parts: the integral digits and the | 328 // We now cut the input number into two parts: the integral digits and the |
317 // fractionals. We will not write any decimal separator though, but adapt | 329 // fractionals. We will not write any decimal separator though, but adapt |
318 // kappa instead. | 330 // kappa instead. |
319 // Reminder: we are currently computing the digits (stored inside the buffer) | 331 // Reminder: we are currently computing the digits (stored inside the buffer) |
320 // such that: too_low < buffer * 10^kappa < too_high | 332 // such that: too_low < buffer * 10^kappa < too_high |
321 // We use too_high for the digit_generation and stop as soon as possible. | 333 // We use too_high for the digit_generation and stop as soon as possible. |
322 // If we stop early we effectively round down. | 334 // If we stop early we effectively round down. |
323 DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e()); | 335 DiyFp one = DiyFp(static_cast<uint64_t>(1) << -w.e(), w.e()); |
324 uint32_t integrals = too_high.f() >> -one.e(); // Division by one. | 336 // Division by one is a shift. |
325 uint64_t fractionals = too_high.f() & (one.f() - 1); // Modulo by one. | 337 uint32_t integrals = static_cast<uint32_t>(too_high.f() >> -one.e()); |
| 338 // Modulo by one is an and. |
| 339 uint64_t fractionals = too_high.f() & (one.f() - 1); |
326 uint32_t divider; | 340 uint32_t divider; |
327 int divider_exponent; | 341 int divider_exponent; |
328 BiggestPowerTen(integrals, DiyFp::kSignificandSize - (-one.e()), | 342 BiggestPowerTen(integrals, DiyFp::kSignificandSize - (-one.e()), |
329 ÷r, ÷r_exponent); | 343 ÷r, ÷r_exponent); |
330 *kappa = divider_exponent + 1; | 344 *kappa = divider_exponent + 1; |
331 *length = 0; | 345 *length = 0; |
332 // Loop invariant: buffer = too_high / 10^kappa (integer division) | 346 // Loop invariant: buffer = too_high / 10^kappa (integer division) |
333 // The invariant holds for the first iteration: kappa has been initialized | 347 // The invariant holds for the first iteration: kappa has been initialized |
334 // with the divider exponent + 1. And the divider is the biggest power of ten | 348 // with the divider exponent + 1. And the divider is the biggest power of ten |
335 // that fits into the bits that had been reserved for the integrals. | 349 // that is smaller than integrals. |
336 while (*kappa > 0) { | 350 while (*kappa > 0) { |
337 int digit = integrals / divider; | 351 int digit = integrals / divider; |
338 buffer[*length] = '0' + digit; | 352 buffer[*length] = '0' + digit; |
339 (*length)++; | 353 (*length)++; |
340 integrals %= divider; | 354 integrals %= divider; |
341 (*kappa)--; | 355 (*kappa)--; |
342 // Note that kappa now equals the exponent of the divider and that the | 356 // Note that kappa now equals the exponent of the divider and that the |
343 // invariant thus holds again. | 357 // invariant thus holds again. |
344 uint64_t rest = | 358 uint64_t rest = |
345 (static_cast<uint64_t>(integrals) << -one.e()) + fractionals; | 359 (static_cast<uint64_t>(integrals) << -one.e()) + fractionals; |
(...skipping 23 matching lines...) Expand all Loading... |
369 // and we have again fractionals.e == one.e which allows us to divide | 383 // and we have again fractionals.e == one.e which allows us to divide |
370 // fractionals.f() by one.f() | 384 // fractionals.f() by one.f() |
371 // We simply combine the *= 10 and the >>= 1. | 385 // We simply combine the *= 10 and the >>= 1. |
372 while (true) { | 386 while (true) { |
373 fractionals *= 5; | 387 fractionals *= 5; |
374 unit *= 5; | 388 unit *= 5; |
375 unsafe_interval.set_f(unsafe_interval.f() * 5); | 389 unsafe_interval.set_f(unsafe_interval.f() * 5); |
376 unsafe_interval.set_e(unsafe_interval.e() + 1); // Will be optimized out. | 390 unsafe_interval.set_e(unsafe_interval.e() + 1); // Will be optimized out. |
377 one.set_f(one.f() >> 1); | 391 one.set_f(one.f() >> 1); |
378 one.set_e(one.e() + 1); | 392 one.set_e(one.e() + 1); |
379 int digit = fractionals >> -one.e(); // Integer division by one. | 393 // Integer division by one. |
| 394 int digit = static_cast<int>(fractionals >> -one.e()); |
380 buffer[*length] = '0' + digit; | 395 buffer[*length] = '0' + digit; |
381 (*length)++; | 396 (*length)++; |
382 fractionals &= one.f() - 1; // Modulo by one. | 397 fractionals &= one.f() - 1; // Modulo by one. |
383 (*kappa)--; | 398 (*kappa)--; |
384 if (fractionals < unsafe_interval.f()) { | 399 if (fractionals < unsafe_interval.f()) { |
385 return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f() * unit, | 400 return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f() * unit, |
386 unsafe_interval.f(), fractionals, one.f(), unit); | 401 unsafe_interval.f(), fractionals, one.f(), unit); |
387 } | 402 } |
388 } | 403 } |
389 } | 404 } |
390 | 405 |
391 | 406 |
392 // Rounds the given generated digits in the buffer and weeds out generated | 407 // Rounds the given generated digits in the buffer and weeds out generated |
393 // digits that are not in the safe interval, or where we cannot find a rounded | 408 // digits that are not in the safe interval, or where we cannot find a rounded |
394 // representation. | 409 // representation. |
395 // Input: * buffer containing the digits of too_high / 10^kappa | 410 // Input: * buffer containing the digits of too_high / 10^kappa |
396 // * the buffer's length | 411 // * the buffer's length |
397 // * distance_too_high_w == (too_high - w).f() * unit | 412 // * distance_too_high_w == (too_high - w).f() * unit |
398 // * unsafe_interval == (too_high - too_low).f() * unit | 413 // * unsafe_interval == (too_high - too_low).f() * unit |
399 // * rest = (too_high - buffer * 10^kappa).f() * unit | 414 // * rest = (too_high - buffer * 10^kappa).f() * unit |
400 // * ten_kappa = 10^kappa * unit | 415 // * ten_kappa = 10^kappa * unit |
401 // * unit = the common multiplier | 416 // * unit = the common multiplier |
402 // Output: returns true on success. | 417 // Output: returns true on success. |
403 // Modifies the generated digits in the buffer to approach (round towards) w. | 418 // Modifies the generated digits in the buffer to approach (round towards) w. |
404 template<int alpha, int gamma> | 419 template<int alpha, int gamma> |
405 bool Grisu3<alpha, gamma>::RoundWeed( | 420 bool Grisu3<alpha, gamma>::RoundWeed(char* buffer, |
406 char* buffer, int length, uint64_t distance_too_high_w, | 421 int length, |
407 uint64_t unsafe_interval, uint64_t rest, uint64_t ten_kappa, | 422 uint64_t distance_too_high_w, |
408 uint64_t unit) { | 423 uint64_t unsafe_interval, |
| 424 uint64_t rest, |
| 425 uint64_t ten_kappa, |
| 426 uint64_t unit) { |
409 uint64_t small_distance = distance_too_high_w - unit; | 427 uint64_t small_distance = distance_too_high_w - unit; |
410 uint64_t big_distance = distance_too_high_w + unit; | 428 uint64_t big_distance = distance_too_high_w + unit; |
411 // Let w- = too_high - big_distance, and | 429 // Let w- = too_high - big_distance, and |
412 // w+ = too_high - small_distance. | 430 // w+ = too_high - small_distance. |
413 // Note: w- < w < w+ | 431 // Note: w- < w < w+ |
414 // | 432 // |
415 // The real w (* unit) must lie somewhere inside the interval | 433 // The real w (* unit) must lie somewhere inside the interval |
416 // ]w-; w+[ (often written as "(w-; w+)") | 434 // ]w-; w+[ (often written as "(w-; w+)") |
417 | 435 |
418 // Basically the buffer currently contains a number in the unsafe interval | 436 // Basically the buffer currently contains a number in the unsafe interval |
(...skipping 30 matching lines...) Expand all Loading... |
449 | 467 |
450 // Weeding test. | 468 // Weeding test. |
451 // The safe interval is [too_low + 2 ulp; too_high - 2 ulp] | 469 // The safe interval is [too_low + 2 ulp; too_high - 2 ulp] |
452 // Since too_low = too_high - unsafe_interval this is equivalent too | 470 // Since too_low = too_high - unsafe_interval this is equivalent too |
453 // [too_high - unsafe_interval + 4 ulp; too_high - 2 ulp] | 471 // [too_high - unsafe_interval + 4 ulp; too_high - 2 ulp] |
454 // Conceptually we have: rest ~= too_high - buffer | 472 // Conceptually we have: rest ~= too_high - buffer |
455 return (2 * unit <= rest) && (rest <= unsafe_interval - 4 * unit); | 473 return (2 * unit <= rest) && (rest <= unsafe_interval - 4 * unit); |
456 } | 474 } |
457 | 475 |
458 | 476 |
459 bool grisu3(double v, | 477 bool grisu3(double v, char* buffer, int* sign, int* length, int* point) { |
460 char* buffer, int* sign, int* length, int* decimal_point) { | |
461 ASSERT(v != 0); | 478 ASSERT(v != 0); |
462 ASSERT(!Double(v).IsSpecial()); | 479 ASSERT(!Double(v).IsSpecial()); |
463 | 480 |
464 if (v < 0) { | 481 if (v < 0) { |
465 v = -v; | 482 v = -v; |
466 *sign = 1; | 483 *sign = 1; |
467 } else { | 484 } else { |
468 *sign = 0; | 485 *sign = 0; |
469 } | 486 } |
470 int decimal_exponent; | 487 int decimal_exponent; |
471 bool result = Grisu3<-60, -32>::grisu3(v, buffer, length, &decimal_exponent); | 488 bool result = Grisu3<-60, -32>::grisu3(v, buffer, length, &decimal_exponent); |
472 *decimal_point = *length + decimal_exponent; | 489 *point = *length + decimal_exponent; |
473 buffer[*length] = '\0'; | 490 buffer[*length] = '\0'; |
474 return result; | 491 return result; |
475 } | 492 } |
476 | 493 |
477 } } // namespace v8::internal | 494 } } // namespace v8::internal |
OLD | NEW |