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 |
11 // with the distribution. | 11 // with the distribution. |
12 // * Neither the name of Google Inc. nor the names of its | 12 // * Neither the name of Google Inc. nor the names of its |
13 // contributors may be used to endorse or promote products derived | 13 // contributors may be used to endorse or promote products derived |
14 // from this software without specific prior written permission. | 14 // from this software without specific prior written permission. |
15 // | 15 // |
16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS | 16 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS |
17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT | 17 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT |
18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR | 18 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR |
19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT | 19 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT |
20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, | 20 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, |
21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT | 21 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT |
22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, | 22 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, |
23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY | 23 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY |
24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT | 24 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT |
25 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE | 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. | 26 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. |
27 | 27 |
28 #include "v8.h" | 28 #include "v8.h" |
29 | 29 |
30 #include "grisu3.h" | 30 #include "fast-dtoa.h" |
31 | 31 |
32 #include "cached_powers.h" | 32 #include "cached_powers.h" |
33 #include "diy_fp.h" | 33 #include "diy_fp.h" |
34 #include "double.h" | 34 #include "double.h" |
35 | 35 |
36 namespace v8 { | 36 namespace v8 { |
37 namespace internal { | 37 namespace internal { |
38 | 38 |
39 template <int alpha = -60, int gamma = -32> | 39 // The minimal and maximal target exponent define the range of w's binary |
40 class Grisu3 { | 40 // exponent, where 'w' is the result of multiplying the input by a cached power |
41 public: | 41 // of ten. |
42 // Provides a decimal representation of v. | 42 // |
43 // Returns true if it succeeds, otherwise the result can not be trusted. | 43 // A different range might be chosen on a different platform, to optimize digit |
44 // There will be *length digits inside the buffer (not null-terminated). | 44 // generation, but a smaller range requires more powers of ten to be cached. |
45 // If the function returns true then | 45 static const int minimal_target_exponent = -60; |
46 // v == (double) (buffer * 10^decimal_exponent). | 46 static const int maximal_target_exponent = -32; |
47 // The digits in the buffer are the shortest representation possible: no | |
48 // 0.099999999999 instead of 0.1. | |
49 // The last digit will be closest to the actual v. That is, even if several | |
50 // digits might correctly yield 'v' when read again, the closest will be | |
51 // computed. | |
52 static bool grisu3(double v, | |
53 char* buffer, int* length, int* decimal_exponent); | |
54 | |
55 private: | |
56 // Rounds the buffer according to the rest. | |
57 // If there is too much imprecision to round then false is returned. | |
58 // Similarily false is returned when the buffer is not within Delta. | |
59 static bool RoundWeed(char* buffer, int len, uint64_t wp_W, uint64_t Delta, | |
60 uint64_t rest, uint64_t ten_kappa, uint64_t ulp); | |
61 // Dispatches to the a specialized digit-generation routine. The chosen | |
62 // routine depends on w.e (which in turn depends on alpha and gamma). | |
63 // Currently there is only one digit-generation routine, but it would be easy | |
64 // to add others. | |
65 static bool DigitGen(DiyFp low, DiyFp w, DiyFp high, | |
66 char* buffer, int* len, int* kappa); | |
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 | |
69 // imprecision into account. If the function cannot compute the best | |
70 // representation (due to the imprecision) then false is returned. | |
71 static bool DigitGen_m60_m32(DiyFp low, DiyFp w, DiyFp high, | |
72 char* buffer, int* length, int* kappa); | |
73 }; | |
74 | 47 |
75 | 48 |
76 template<int alpha, int gamma> | 49 // Adjusts the last digit of the generated number, and screens out generated |
77 bool Grisu3<alpha, gamma>::grisu3(double v, | 50 // solutions that may be inaccurate. A solution may be inaccurate if it is |
78 char* buffer, | 51 // outside the safe interval, or if we ctannot prove that it is closer to the |
79 int* length, | 52 // input than a neighboring representation of the same length. |
80 int* decimal_exponent) { | 53 // |
81 DiyFp w = Double(v).AsNormalizedDiyFp(); | 54 // Input: * buffer containing the digits of too_high / 10^kappa |
82 // boundary_minus and boundary_plus are the boundaries between v and its | 55 // * the buffer's length |
83 // neighbors. Any number strictly between boundary_minus and boundary_plus | 56 // * distance_too_high_w == (too_high - w).f() * unit |
84 // will round to v when read as double. | 57 // * unsafe_interval == (too_high - too_low).f() * unit |
85 // Grisu3 will never output representations that lie exactly on a boundary. | 58 // * rest = (too_high - buffer * 10^kappa).f() * unit |
86 DiyFp boundary_minus, boundary_plus; | 59 // * ten_kappa = 10^kappa * unit |
87 Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus); | 60 // * unit = the common multiplier |
88 ASSERT(boundary_plus.e() == w.e()); | 61 // Output: returns true if the buffer is guaranteed to contain the closest |
89 DiyFp ten_mk; // Cached power of ten: 10^-k | 62 // representable number to the input. |
90 int mk; // -k | 63 // Modifies the generated digits in the buffer to approach (round towards) w. |
91 GetCachedPower(w.e() + DiyFp::kSignificandSize, alpha, gamma, &mk, &ten_mk); | 64 bool RoundWeed(char* buffer, |
92 ASSERT(alpha <= w.e() + ten_mk.e() + DiyFp::kSignificandSize && | 65 int length, |
93 gamma >= w.e() + ten_mk.e() + DiyFp::kSignificandSize); | 66 uint64_t distance_too_high_w, |
94 // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a | 67 uint64_t unsafe_interval, |
95 // 64 bit significand and ten_mk is thus only precise up to 64 bits. | 68 uint64_t rest, |
| 69 uint64_t ten_kappa, |
| 70 uint64_t unit) { |
| 71 uint64_t small_distance = distance_too_high_w - unit; |
| 72 uint64_t big_distance = distance_too_high_w + unit; |
| 73 // Let w_low = too_high - big_distance, and |
| 74 // w_high = too_high - small_distance. |
| 75 // Note: w_low < w < w_high |
| 76 // |
| 77 // The real w (* unit) must lie somewhere inside the interval |
| 78 // ]w_low; w_low[ (often written as "(w_low; w_low)") |
96 | 79 |
97 // The DiyFp::Times procedure rounds its result, and ten_mk is approximated | 80 // Basically the buffer currently contains a number in the unsafe interval |
98 // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now | 81 // ]too_low; too_high[ with too_low < w < too_high |
99 // off by a small amount. | 82 // |
100 // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w. | 83 // too_high - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
101 // In other words: let f = scaled_w.f() and e = scaled_w.e(), then | 84 // ^v 1 unit ^ ^ ^ ^ |
102 // (f-1) * 2^e < w*10^k < (f+1) * 2^e | 85 // boundary_high --------------------- . . . . |
103 DiyFp scaled_w = DiyFp::Times(w, ten_mk); | 86 // ^v 1 unit . . . . |
104 ASSERT(scaled_w.e() == | 87 // - - - - - - - - - - - - - - - - - - - + - - + - - - - - - . . |
105 boundary_plus.e() + ten_mk.e() + DiyFp::kSignificandSize); | 88 // . . ^ . . |
106 // In theory it would be possible to avoid some recomputations by computing | 89 // . big_distance . . . |
107 // the difference between w and boundary_minus/plus (a power of 2) and to | 90 // . . . . rest |
108 // compute scaled_boundary_minus/plus by subtracting/adding from | 91 // small_distance . . . . |
109 // scaled_w. However the code becomes much less readable and the speed | 92 // v . . . . |
110 // enhancements are not terriffic. | 93 // w_high - - - - - - - - - - - - - - - - - - . . . . |
111 DiyFp scaled_boundary_minus = DiyFp::Times(boundary_minus, ten_mk); | 94 // ^v 1 unit . . . . |
112 DiyFp scaled_boundary_plus = DiyFp::Times(boundary_plus, ten_mk); | 95 // w ---------------------------------------- . . . . |
| 96 // ^v 1 unit v . . . |
| 97 // w_low - - - - - - - - - - - - - - - - - - - - - . . . |
| 98 // . . v |
| 99 // buffer --------------------------------------------------+-------+-------- |
| 100 // . . |
| 101 // safe_interval . |
| 102 // v . |
| 103 // - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - . |
| 104 // ^v 1 unit . |
| 105 // boundary_low ------------------------- unsafe_interval |
| 106 // ^v 1 unit v |
| 107 // too_low - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - |
| 108 // |
| 109 // |
| 110 // Note that the value of buffer could lie anywhere inside the range too_low |
| 111 // to too_high. |
| 112 // |
| 113 // boundary_low, boundary_high and w are approximations of the real boundaries |
| 114 // and v (the input number). They are guaranteed to be precise up to one unit. |
| 115 // In fact the error is guaranteed to be strictly less than one unit. |
| 116 // |
| 117 // Anything that lies outside the unsafe interval is guaranteed not to round |
| 118 // to v when read again. |
| 119 // Anything that lies inside the safe interval is guaranteed to round to v |
| 120 // when read again. |
| 121 // If the number inside the buffer lies inside the unsafe interval but not |
| 122 // inside the safe interval then we simply do not know and bail out (returning |
| 123 // false). |
| 124 // |
| 125 // Similarly we have to take into account the imprecision of 'w' when rounding |
| 126 // the buffer. If we have two potential representations we need to make sure |
| 127 // that the chosen one is closer to w_low and w_high since v can be anywhere |
| 128 // between them. |
| 129 // |
| 130 // By generating the digits of too_high we got the largest (closest to |
| 131 // too_high) buffer that is still in the unsafe interval. In the case where |
| 132 // w_high < buffer < too_high we try to decrement the buffer. |
| 133 // This way the buffer approaches (rounds towards) w. |
| 134 // There are 3 conditions that stop the decrementation process: |
| 135 // 1) the buffer is already below w_high |
| 136 // 2) decrementing the buffer would make it leave the unsafe interval |
| 137 // 3) decrementing the buffer would yield a number below w_high and farther |
| 138 // away than the current number. In other words: |
| 139 // (buffer{-1} < w_high) && w_high - buffer{-1} > buffer - w_high |
| 140 // Instead of using the buffer directly we use its distance to too_high. |
| 141 // Conceptually rest ~= too_high - buffer |
| 142 while (rest < small_distance && // Negated condition 1 |
| 143 unsafe_interval - rest >= ten_kappa && // Negated condition 2 |
| 144 (rest + ten_kappa < small_distance || // buffer{-1} > w_high |
| 145 small_distance - rest >= rest + ten_kappa - small_distance)) { |
| 146 buffer[length - 1]--; |
| 147 rest += ten_kappa; |
| 148 } |
113 | 149 |
114 // DigitGen will generate the digits of scaled_w. Therefore we have | 150 // We have approached w+ as much as possible. We now test if approaching w- |
115 // v == (double) (scaled_w * 10^-mk). | 151 // would require changing the buffer. If yes, then we have two possible |
116 // Set decimal_exponent == -mk and pass it to DigitGen. If scaled_w is not an | 152 // representations close to w, but we cannot decide which one is closer. |
117 // integer than it will be updated. For instance if scaled_w == 1.23 then | 153 if (rest < big_distance && |
118 // the buffer will be filled with "123" und the decimal_exponent will be | 154 unsafe_interval - rest >= ten_kappa && |
119 // decreased by 2. | 155 (rest + ten_kappa < big_distance || |
120 int kappa; | 156 big_distance - rest > rest + ten_kappa - big_distance)) { |
121 bool result = DigitGen(scaled_boundary_minus, scaled_w, scaled_boundary_plus, | 157 return false; |
122 buffer, length, &kappa); | 158 } |
123 *decimal_exponent = -mk + kappa; | 159 |
124 return result; | 160 // Weeding test. |
| 161 // The safe interval is [too_low + 2 ulp; too_high - 2 ulp] |
| 162 // Since too_low = too_high - unsafe_interval this is equivalent to |
| 163 // [too_high - unsafe_interval + 4 ulp; too_high - 2 ulp] |
| 164 // Conceptually we have: rest ~= too_high - buffer |
| 165 return (2 * unit <= rest) && (rest <= unsafe_interval - 4 * unit); |
125 } | 166 } |
126 | 167 |
127 // Generates the digits of input number w. | 168 |
128 // w is a floating-point number (DiyFp), consisting of a significand and an | |
129 // exponent. Its exponent is bounded by alpha and gamma. Typically alpha >= -63 | |
130 // and gamma <= 3. | |
131 // Returns false if it fails, in which case the generated digits in the buffer | |
132 // should not be used. | |
133 // Preconditions: | |
134 // * low, w and high are correct up to 1 ulp (unit in the last place). That | |
135 // is, their error must be less that a unit of their last digits. | |
136 // * low.e() == w.e() == high.e() | |
137 // * low < w < high, and taking into account their error: low~ <= high~ | |
138 // * alpha <= w.e() <= gamma | |
139 // Postconditions: returns false if procedure fails. | |
140 // otherwise: | |
141 // * buffer is not null-terminated, but len contains the number of digits. | |
142 // * buffer contains the shortest possible decimal digit-sequence | |
143 // such that LOW < buffer * 10^kappa < HIGH, where LOW and HIGH are the | |
144 // correct values of low and high (without their error). | |
145 // * if more than one decimal representation gives the minimal number of | |
146 // decimal digits then the one closest to W (where W is the correct value | |
147 // of w) is chosen. | |
148 // Remark: this procedure takes into account the imprecision of its input | |
149 // numbers. If the precision is not enough to guarantee all the postconditions | |
150 // then false is returned. This usually happens rarely (~0.5%). | |
151 template<int alpha, int gamma> | |
152 bool Grisu3<alpha, gamma>::DigitGen(DiyFp low, | |
153 DiyFp w, | |
154 DiyFp high, | |
155 char* buffer, | |
156 int* len, | |
157 int* kappa) { | |
158 ASSERT(low.e() == w.e() && w.e() == high.e()); | |
159 ASSERT(low.f() + 1 <= high.f() - 1); | |
160 ASSERT(alpha <= w.e() && w.e() <= gamma); | |
161 // The following tests use alpha and gamma to avoid unnecessary dynamic tests. | |
162 if ((alpha >= -60 && gamma <= -32) || // -60 <= w.e() <= -32 | |
163 (alpha <= -32 && gamma >= -60 && // Alpha/gamma overlaps -60/-32 region. | |
164 -60 <= w.e() && w.e() <= -32)) { | |
165 return DigitGen_m60_m32(low, w, high, buffer, len, kappa); | |
166 } else { | |
167 // A simple adaption of the special case -60/-32 would allow greater ranges | |
168 // of alpha/gamma and thus reduce the number of precomputed cached powers of | |
169 // ten. | |
170 UNIMPLEMENTED(); | |
171 return false; | |
172 } | |
173 } | |
174 | 169 |
175 static const uint32_t kTen4 = 10000; | 170 static const uint32_t kTen4 = 10000; |
176 static const uint32_t kTen5 = 100000; | 171 static const uint32_t kTen5 = 100000; |
177 static const uint32_t kTen6 = 1000000; | 172 static const uint32_t kTen6 = 1000000; |
178 static const uint32_t kTen7 = 10000000; | 173 static const uint32_t kTen7 = 10000000; |
179 static const uint32_t kTen8 = 100000000; | 174 static const uint32_t kTen8 = 100000000; |
180 static const uint32_t kTen9 = 1000000000; | 175 static const uint32_t kTen9 = 1000000000; |
181 | 176 |
182 // Returns the biggest power of ten that is <= than the given number. We | 177 // Returns the biggest power of ten that is less than or equal than the given |
183 // furthermore receive the maximum number of bits 'number' has. | 178 // number. We furthermore receive the maximum number of bits 'number' has. |
184 // If number_bits == 0 then 0^-1 is returned | 179 // If number_bits == 0 then 0^-1 is returned |
185 // The number of bits must be <= 32. | 180 // The number of bits must be <= 32. |
| 181 // Precondition: (1 << number_bits) <= number < (1 << (number_bits + 1)). |
186 static void BiggestPowerTen(uint32_t number, | 182 static void BiggestPowerTen(uint32_t number, |
187 int number_bits, | 183 int number_bits, |
188 uint32_t* power, | 184 uint32_t* power, |
189 int* exponent) { | 185 int* exponent) { |
190 switch (number_bits) { | 186 switch (number_bits) { |
191 case 32: | 187 case 32: |
192 case 31: | 188 case 31: |
193 case 30: | 189 case 30: |
194 if (kTen9 <= number) { | 190 if (kTen9 <= number) { |
195 *power = kTen9; | 191 *power = kTen9; |
(...skipping 80 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
276 break; | 272 break; |
277 default: | 273 default: |
278 // Following assignments are here to silence compiler warnings. | 274 // Following assignments are here to silence compiler warnings. |
279 *power = 0; | 275 *power = 0; |
280 *exponent = 0; | 276 *exponent = 0; |
281 UNREACHABLE(); | 277 UNREACHABLE(); |
282 } | 278 } |
283 } | 279 } |
284 | 280 |
285 | 281 |
286 // Same comments as for DigitGen but with additional precondition: | 282 // Generates the digits of input number w. |
287 // -60 <= w.e() <= -32 | 283 // w is a floating-point number (DiyFp), consisting of a significand and an |
| 284 // exponent. Its exponent is bounded by minimal_target_exponent and |
| 285 // maximal_target_exponent. |
| 286 // Hence -60 <= w.e() <= -32. |
| 287 // |
| 288 // Returns false if it fails, in which case the generated digits in the buffer |
| 289 // should not be used. |
| 290 // Preconditions: |
| 291 // * low, w and high are correct up to 1 ulp (unit in the last place). That |
| 292 // is, their error must be less that a unit of their last digits. |
| 293 // * low.e() == w.e() == high.e() |
| 294 // * low < w < high, and taking into account their error: low~ <= high~ |
| 295 // * minimal_target_exponent <= w.e() <= maximal_target_exponent |
| 296 // Postconditions: returns false if procedure fails. |
| 297 // otherwise: |
| 298 // * buffer is not null-terminated, but len contains the number of digits. |
| 299 // * buffer contains the shortest possible decimal digit-sequence |
| 300 // such that LOW < buffer * 10^kappa < HIGH, where LOW and HIGH are the |
| 301 // correct values of low and high (without their error). |
| 302 // * if more than one decimal representation gives the minimal number of |
| 303 // decimal digits then the one closest to W (where W is the correct value |
| 304 // of w) is chosen. |
| 305 // Remark: this procedure takes into account the imprecision of its input |
| 306 // numbers. If the precision is not enough to guarantee all the postconditions |
| 307 // then false is returned. This usually happens rarely (~0.5%). |
288 // | 308 // |
289 // Say, for the sake of example, that | 309 // Say, for the sake of example, that |
290 // w.e() == -48, and w.f() == 0x1234567890abcdef | 310 // w.e() == -48, and w.f() == 0x1234567890abcdef |
291 // w's value can be computed by w.f() * 2^w.e() | 311 // w's value can be computed by w.f() * 2^w.e() |
292 // We can obtain w's integral digits by simply shifting w.f() by -w.e(). | 312 // We can obtain w's integral digits by simply shifting w.f() by -w.e(). |
293 // -> w's integral part is 0x1234 | 313 // -> w's integral part is 0x1234 |
294 // w's fractional part is therefore 0x567890abcdef. | 314 // w's fractional part is therefore 0x567890abcdef. |
295 // Printing w's integral part is easy (simply print 0x1234 in decimal). | 315 // Printing w's integral part is easy (simply print 0x1234 in decimal). |
296 // In order to print its fraction we repeatedly multiply the fraction by 10 and | 316 // In order to print its fraction we repeatedly multiply the fraction by 10 and |
297 // get each digit. Example the first digit after the comma would be computed by | 317 // get each digit. Example the first digit after the comma would be computed by |
298 // (0x567890abcdef * 10) >> 48. -> 3 | 318 // (0x567890abcdef * 10) >> 48. -> 3 |
299 // The whole thing becomes slightly more complicated because we want to stop | 319 // The whole thing becomes slightly more complicated because we want to stop |
300 // once we have enough digits. That is, once the digits inside the buffer | 320 // once we have enough digits. That is, once the digits inside the buffer |
301 // represent 'w' we can stop. Everything inside the interval low - high | 321 // represent 'w' we can stop. Everything inside the interval low - high |
302 // represents w. However we have to pay attention to low, high and w's | 322 // represents w. However we have to pay attention to low, high and w's |
303 // imprecision. | 323 // imprecision. |
304 template<int alpha, int gamma> | 324 bool DigitGen(DiyFp low, |
305 bool Grisu3<alpha, gamma>::DigitGen_m60_m32(DiyFp low, | 325 DiyFp w, |
306 DiyFp w, | 326 DiyFp high, |
307 DiyFp high, | 327 char* buffer, |
308 char* buffer, | 328 int* length, |
309 int* length, | 329 int* kappa) { |
310 int* kappa) { | 330 ASSERT(low.e() == w.e() && w.e() == high.e()); |
| 331 ASSERT(low.f() + 1 <= high.f() - 1); |
| 332 ASSERT(minimal_target_exponent <= w.e() && w.e() <= maximal_target_exponent); |
311 // low, w and high are imprecise, but by less than one ulp (unit in the last | 333 // low, w and high are imprecise, but by less than one ulp (unit in the last |
312 // place). | 334 // place). |
313 // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that | 335 // If we remove (resp. add) 1 ulp from low (resp. high) we are certain that |
314 // the new numbers are outside of the interval we want the final | 336 // the new numbers are outside of the interval we want the final |
315 // representation to lie in. | 337 // representation to lie in. |
316 // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield | 338 // Inversely adding (resp. removing) 1 ulp from low (resp. high) would yield |
317 // numbers that are certain to lie in the interval. We will use this fact | 339 // numbers that are certain to lie in the interval. We will use this fact |
318 // later on. | 340 // later on. |
319 // We will now start by generating the digits within the uncertain | 341 // We will now start by generating the digits within the uncertain |
320 // interval. Later we will weed out representations that lie outside the safe | 342 // interval. Later we will weed out representations that lie outside the safe |
(...skipping 76 matching lines...) Expand 10 before | Expand all | Expand 10 after Loading... |
397 fractionals &= one.f() - 1; // Modulo by one. | 419 fractionals &= one.f() - 1; // Modulo by one. |
398 (*kappa)--; | 420 (*kappa)--; |
399 if (fractionals < unsafe_interval.f()) { | 421 if (fractionals < unsafe_interval.f()) { |
400 return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f() * unit, | 422 return RoundWeed(buffer, *length, DiyFp::Minus(too_high, w).f() * unit, |
401 unsafe_interval.f(), fractionals, one.f(), unit); | 423 unsafe_interval.f(), fractionals, one.f(), unit); |
402 } | 424 } |
403 } | 425 } |
404 } | 426 } |
405 | 427 |
406 | 428 |
407 // Rounds the given generated digits in the buffer and weeds out generated | 429 // Provides a decimal representation of v. |
408 // digits that are not in the safe interval, or where we cannot find a rounded | 430 // Returns true if it succeeds, otherwise the result cannot be trusted. |
409 // representation. | 431 // There will be *length digits inside the buffer (not null-terminated). |
410 // Input: * buffer containing the digits of too_high / 10^kappa | 432 // If the function returns true then |
411 // * the buffer's length | 433 // v == (double) (buffer * 10^decimal_exponent). |
412 // * distance_too_high_w == (too_high - w).f() * unit | 434 // The digits in the buffer are the shortest representation possible: no |
413 // * unsafe_interval == (too_high - too_low).f() * unit | 435 // 0.09999999999999999 instead of 0.1. The shorter representation will even be |
414 // * rest = (too_high - buffer * 10^kappa).f() * unit | 436 // chosen even if the longer one would be closer to v. |
415 // * ten_kappa = 10^kappa * unit | 437 // The last digit will be closest to the actual v. That is, even if several |
416 // * unit = the common multiplier | 438 // digits might correctly yield 'v' when read again, the closest will be |
417 // Output: returns true on success. | 439 // computed. |
418 // Modifies the generated digits in the buffer to approach (round towards) w. | 440 bool grisu3(double v, char* buffer, int* length, int* decimal_exponent) { |
419 template<int alpha, int gamma> | 441 DiyFp w = Double(v).AsNormalizedDiyFp(); |
420 bool Grisu3<alpha, gamma>::RoundWeed(char* buffer, | 442 // boundary_minus and boundary_plus are the boundaries between v and its |
421 int length, | 443 // closest floating-point neighbors. Any number strictly between |
422 uint64_t distance_too_high_w, | 444 // boundary_minus and boundary_plus will round to v when convert to a double. |
423 uint64_t unsafe_interval, | 445 // Grisu3 will never output representations that lie exactly on a boundary. |
424 uint64_t rest, | 446 DiyFp boundary_minus, boundary_plus; |
425 uint64_t ten_kappa, | 447 Double(v).NormalizedBoundaries(&boundary_minus, &boundary_plus); |
426 uint64_t unit) { | 448 ASSERT(boundary_plus.e() == w.e()); |
427 uint64_t small_distance = distance_too_high_w - unit; | 449 DiyFp ten_mk; // Cached power of ten: 10^-k |
428 uint64_t big_distance = distance_too_high_w + unit; | 450 int mk; // -k |
429 // Let w- = too_high - big_distance, and | 451 GetCachedPower(w.e() + DiyFp::kSignificandSize, minimal_target_exponent, |
430 // w+ = too_high - small_distance. | 452 maximal_target_exponent, &mk, &ten_mk); |
431 // Note: w- < w < w+ | 453 ASSERT(minimal_target_exponent <= w.e() + ten_mk.e() + |
432 // | 454 DiyFp::kSignificandSize && |
433 // The real w (* unit) must lie somewhere inside the interval | 455 maximal_target_exponent >= w.e() + ten_mk.e() + |
434 // ]w-; w+[ (often written as "(w-; w+)") | 456 DiyFp::kSignificandSize); |
| 457 // Note that ten_mk is only an approximation of 10^-k. A DiyFp only contains a |
| 458 // 64 bit significand and ten_mk is thus only precise up to 64 bits. |
435 | 459 |
436 // Basically the buffer currently contains a number in the unsafe interval | 460 // The DiyFp::Times procedure rounds its result, and ten_mk is approximated |
437 // ]too_low; too_high[ with too_low < w < too_high | 461 // too. The variable scaled_w (as well as scaled_boundary_minus/plus) are now |
438 // | 462 // off by a small amount. |
439 // By generating the digits of too_high we got the biggest last digit. | 463 // In fact: scaled_w - w*10^k < 1ulp (unit in the last place) of scaled_w. |
440 // In the case that w+ < buffer < too_high we try to decrement the buffer. | 464 // In other words: let f = scaled_w.f() and e = scaled_w.e(), then |
441 // This way the buffer approaches (rounds towards) w. | 465 // (f-1) * 2^e < w*10^k < (f+1) * 2^e |
442 // There are 3 conditions that stop the decrementation process: | 466 DiyFp scaled_w = DiyFp::Times(w, ten_mk); |
443 // 1) the buffer is already below w+ | 467 ASSERT(scaled_w.e() == |
444 // 2) decrementing the buffer would make it leave the unsafe interval | 468 boundary_plus.e() + ten_mk.e() + DiyFp::kSignificandSize); |
445 // 3) decrementing the buffer would yield a number below w+ and farther away | 469 // In theory it would be possible to avoid some recomputations by computing |
446 // than the current number. In other words: | 470 // the difference between w and boundary_minus/plus (a power of 2) and to |
447 // (buffer{-1} < w+) && w+ - buffer{-1} > buffer - w+ | 471 // compute scaled_boundary_minus/plus by subtracting/adding from |
448 // Instead of using the buffer directly we use its distance to too_high. | 472 // scaled_w. However the code becomes much less readable and the speed |
449 // Conceptually rest ~= too_high - buffer | 473 // enhancements are not terriffic. |
450 while (rest < small_distance && // Negated condition 1 | 474 DiyFp scaled_boundary_minus = DiyFp::Times(boundary_minus, ten_mk); |
451 unsafe_interval - rest >= ten_kappa && // Negated condition 2 | 475 DiyFp scaled_boundary_plus = DiyFp::Times(boundary_plus, ten_mk); |
452 (rest + ten_kappa < small_distance || // buffer{-1} > w+ | |
453 small_distance - rest >= rest + ten_kappa - small_distance)) { | |
454 buffer[length - 1]--; | |
455 rest += ten_kappa; | |
456 } | |
457 | 476 |
458 // We have approached w+ as much as possible. We now test if approaching w- | 477 // DigitGen will generate the digits of scaled_w. Therefore we have |
459 // would require changing the buffer. If yes, then we have two possible | 478 // v == (double) (scaled_w * 10^-mk). |
460 // representations close to w, but we cannot decide which one is closer. | 479 // Set decimal_exponent == -mk and pass it to DigitGen. If scaled_w is not an |
461 if (rest < big_distance && | 480 // integer than it will be updated. For instance if scaled_w == 1.23 then |
462 unsafe_interval - rest >= ten_kappa && | 481 // the buffer will be filled with "123" und the decimal_exponent will be |
463 (rest + ten_kappa < big_distance || | 482 // decreased by 2. |
464 big_distance - rest > rest + ten_kappa - big_distance)) { | 483 int kappa; |
465 return false; | 484 bool result = DigitGen(scaled_boundary_minus, scaled_w, scaled_boundary_plus, |
466 } | 485 buffer, length, &kappa); |
467 | 486 *decimal_exponent = -mk + kappa; |
468 // Weeding test. | 487 return result; |
469 // The safe interval is [too_low + 2 ulp; too_high - 2 ulp] | |
470 // Since too_low = too_high - unsafe_interval this is equivalent too | |
471 // [too_high - unsafe_interval + 4 ulp; too_high - 2 ulp] | |
472 // Conceptually we have: rest ~= too_high - buffer | |
473 return (2 * unit <= rest) && (rest <= unsafe_interval - 4 * unit); | |
474 } | 488 } |
475 | 489 |
476 | 490 |
477 bool grisu3(double v, char* buffer, int* sign, int* length, int* point) { | 491 bool FastDtoa(double v, char* buffer, int* sign, int* length, int* point) { |
478 ASSERT(v != 0); | 492 ASSERT(v != 0); |
479 ASSERT(!Double(v).IsSpecial()); | 493 ASSERT(!Double(v).IsSpecial()); |
480 | 494 |
481 if (v < 0) { | 495 if (v < 0) { |
482 v = -v; | 496 v = -v; |
483 *sign = 1; | 497 *sign = 1; |
484 } else { | 498 } else { |
485 *sign = 0; | 499 *sign = 0; |
486 } | 500 } |
487 int decimal_exponent; | 501 int decimal_exponent; |
488 bool result = Grisu3<-60, -32>::grisu3(v, buffer, length, &decimal_exponent); | 502 bool result = grisu3(v, buffer, length, &decimal_exponent); |
489 *point = *length + decimal_exponent; | 503 *point = *length + decimal_exponent; |
490 buffer[*length] = '\0'; | 504 buffer[*length] = '\0'; |
491 return result; | 505 return result; |
492 } | 506 } |
493 | 507 |
494 } } // namespace v8::internal | 508 } } // namespace v8::internal |
OLD | NEW |