| 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 "bignum-dtoa.h" | |
| 29 | |
| 30 #include "bignum.h" | |
| 31 #include "double.h" | |
| 32 #include <math.h> | |
| 33 | |
| 34 namespace WTF { | |
| 35 | |
| 36 namespace double_conversion { | |
| 37 | |
| 38 static int NormalizedExponent(uint64_t significand, int exponent) { | |
| 39 ASSERT(significand != 0); | |
| 40 while ((significand & Double::kHiddenBit) == 0) { | |
| 41 significand = significand << 1; | |
| 42 exponent = exponent - 1; | |
| 43 } | |
| 44 return exponent; | |
| 45 } | |
| 46 | |
| 47 | |
| 48 // Forward declarations: | |
| 49 // Returns an estimation of k such that 10^(k-1) <= v < 10^k. | |
| 50 static int EstimatePower(int exponent); | |
| 51 // Computes v / 10^estimated_power exactly, as a ratio of two bignums, numer
ator | |
| 52 // and denominator. | |
| 53 static void InitialScaledStartValues(double v, | |
| 54 int estimated_power, | |
| 55 bool need_boundary_deltas, | |
| 56 Bignum* numerator, | |
| 57 Bignum* denominator, | |
| 58 Bignum* delta_minus, | |
| 59 Bignum* delta_plus); | |
| 60 // Multiplies numerator/denominator so that its values lies in the range 1-1
0. | |
| 61 // Returns decimal_point s.t. | |
| 62 // v = numerator'/denominator' * 10^(decimal_point-1) | |
| 63 // where numerator' and denominator' are the values of numerator and | |
| 64 // denominator after the call to this function. | |
| 65 static void FixupMultiply10(int estimated_power, bool is_even, | |
| 66 int* decimal_point, | |
| 67 Bignum* numerator, Bignum* denominator, | |
| 68 Bignum* delta_minus, Bignum* delta_plus); | |
| 69 // Generates digits from the left to the right and stops when the generated | |
| 70 // digits yield the shortest decimal representation of v. | |
| 71 static void GenerateShortestDigits(Bignum* numerator, Bignum* denominator, | |
| 72 Bignum* delta_minus, Bignum* delta_plus, | |
| 73 bool is_even, | |
| 74 Vector<char> buffer, int* length); | |
| 75 // Generates 'requested_digits' after the decimal point. | |
| 76 static void BignumToFixed(int requested_digits, int* decimal_point, | |
| 77 Bignum* numerator, Bignum* denominator, | |
| 78 Vector<char>(buffer), int* length); | |
| 79 // Generates 'count' digits of numerator/denominator. | |
| 80 // Once 'count' digits have been produced rounds the result depending on the | |
| 81 // remainder (remainders of exactly .5 round upwards). Might update the | |
| 82 // decimal_point when rounding up (for example for 0.9999). | |
| 83 static void GenerateCountedDigits(int count, int* decimal_point, | |
| 84 Bignum* numerator, Bignum* denominator, | |
| 85 Vector<char>(buffer), int* length); | |
| 86 | |
| 87 | |
| 88 void BignumDtoa(double v, BignumDtoaMode mode, int requested_digits, | |
| 89 Vector<char> buffer, int* length, int* decimal_point) { | |
| 90 ASSERT(v > 0); | |
| 91 ASSERT(!Double(v).IsSpecial()); | |
| 92 uint64_t significand = Double(v).Significand(); | |
| 93 bool is_even = (significand & 1) == 0; | |
| 94 int exponent = Double(v).Exponent(); | |
| 95 int normalized_exponent = NormalizedExponent(significand, exponent); | |
| 96 // estimated_power might be too low by 1. | |
| 97 int estimated_power = EstimatePower(normalized_exponent); | |
| 98 | |
| 99 // Shortcut for Fixed. | |
| 100 // The requested digits correspond to the digits after the point. If the | |
| 101 // number is much too small, then there is no need in trying to get any | |
| 102 // digits. | |
| 103 if (mode == BIGNUM_DTOA_FIXED && -estimated_power - 1 > requested_digits
) { | |
| 104 buffer[0] = '\0'; | |
| 105 *length = 0; | |
| 106 // Set decimal-point to -requested_digits. This is what Gay does. | |
| 107 // Note that it should not have any effect anyways since the string
is | |
| 108 // empty. | |
| 109 *decimal_point = -requested_digits; | |
| 110 return; | |
| 111 } | |
| 112 | |
| 113 Bignum numerator; | |
| 114 Bignum denominator; | |
| 115 Bignum delta_minus; | |
| 116 Bignum delta_plus; | |
| 117 // Make sure the bignum can grow large enough. The smallest double equal
s | |
| 118 // 4e-324. In this case the denominator needs fewer than 324*4 binary di
gits. | |
| 119 // The maximum double is 1.7976931348623157e308 which needs fewer than | |
| 120 // 308*4 binary digits. | |
| 121 ASSERT(Bignum::kMaxSignificantBits >= 324*4); | |
| 122 bool need_boundary_deltas = (mode == BIGNUM_DTOA_SHORTEST); | |
| 123 InitialScaledStartValues(v, estimated_power, need_boundary_deltas, | |
| 124 &numerator, &denominator, | |
| 125 &delta_minus, &delta_plus); | |
| 126 // We now have v = (numerator / denominator) * 10^estimated_power. | |
| 127 FixupMultiply10(estimated_power, is_even, decimal_point, | |
| 128 &numerator, &denominator, | |
| 129 &delta_minus, &delta_plus); | |
| 130 // We now have v = (numerator / denominator) * 10^(decimal_point-1), and | |
| 131 // 1 <= (numerator + delta_plus) / denominator < 10 | |
| 132 switch (mode) { | |
| 133 case BIGNUM_DTOA_SHORTEST: | |
| 134 GenerateShortestDigits(&numerator, &denominator, | |
| 135 &delta_minus, &delta_plus, | |
| 136 is_even, buffer, length); | |
| 137 break; | |
| 138 case BIGNUM_DTOA_FIXED: | |
| 139 BignumToFixed(requested_digits, decimal_point, | |
| 140 &numerator, &denominator, | |
| 141 buffer, length); | |
| 142 break; | |
| 143 case BIGNUM_DTOA_PRECISION: | |
| 144 GenerateCountedDigits(requested_digits, decimal_point, | |
| 145 &numerator, &denominator, | |
| 146 buffer, length); | |
| 147 break; | |
| 148 default: | |
| 149 UNREACHABLE(); | |
| 150 } | |
| 151 buffer[*length] = '\0'; | |
| 152 } | |
| 153 | |
| 154 | |
| 155 // The procedure starts generating digits from the left to the right and sto
ps | |
| 156 // when the generated digits yield the shortest decimal representation of v.
A | |
| 157 // decimal representation of v is a number lying closer to v than to any oth
er | |
| 158 // double, so it converts to v when read. | |
| 159 // | |
| 160 // This is true if d, the decimal representation, is between m- and m+, the | |
| 161 // upper and lower boundaries. d must be strictly between them if !is_even. | |
| 162 // m- := (numerator - delta_minus) / denominator | |
| 163 // m+ := (numerator + delta_plus) / denominator | |
| 164 // | |
| 165 // Precondition: 0 <= (numerator+delta_plus) / denominator < 10. | |
| 166 // If 1 <= (numerator+delta_plus) / denominator < 10 then no leading 0 dig
it | |
| 167 // will be produced. This should be the standard precondition. | |
| 168 static void GenerateShortestDigits(Bignum* numerator, Bignum* denominator, | |
| 169 Bignum* delta_minus, Bignum* delta_plus, | |
| 170 bool is_even, | |
| 171 Vector<char> buffer, int* length) { | |
| 172 // Small optimization: if delta_minus and delta_plus are the same just r
euse | |
| 173 // one of the two bignums. | |
| 174 if (Bignum::Equal(*delta_minus, *delta_plus)) { | |
| 175 delta_plus = delta_minus; | |
| 176 } | |
| 177 *length = 0; | |
| 178 while (true) { | |
| 179 uint16_t digit; | |
| 180 digit = numerator->DivideModuloIntBignum(*denominator); | |
| 181 ASSERT(digit <= 9); // digit is a uint16_t and therefore always pos
itive. | |
| 182 // digit = numerator / denominator (integer division). | |
| 183 // numerator = numerator % denominator. | |
| 184 buffer[(*length)++] = static_cast<char>(digit + '0'); | |
| 185 | |
| 186 // Can we stop already? | |
| 187 // If the remainder of the division is less than the distance to the
lower | |
| 188 // boundary we can stop. In this case we simply round down (discardi
ng the | |
| 189 // remainder). | |
| 190 // Similarly we test if we can round up (using the upper boundary). | |
| 191 bool in_delta_room_minus; | |
| 192 bool in_delta_room_plus; | |
| 193 if (is_even) { | |
| 194 in_delta_room_minus = Bignum::LessEqual(*numerator, *delta_minus
); | |
| 195 } else { | |
| 196 in_delta_room_minus = Bignum::Less(*numerator, *delta_minus); | |
| 197 } | |
| 198 if (is_even) { | |
| 199 in_delta_room_plus = | |
| 200 Bignum::PlusCompare(*numerator, *delta_plus, *denominator) >= 0; | |
| 201 } else { | |
| 202 in_delta_room_plus = | |
| 203 Bignum::PlusCompare(*numerator, *delta_plus, *denominator) > 0; | |
| 204 } | |
| 205 if (!in_delta_room_minus && !in_delta_room_plus) { | |
| 206 // Prepare for next iteration. | |
| 207 numerator->Times10(); | |
| 208 delta_minus->Times10(); | |
| 209 // We optimized delta_plus to be equal to delta_minus (if they s
hare the | |
| 210 // same value). So don't multiply delta_plus if they point to th
e same | |
| 211 // object. | |
| 212 if (delta_minus != delta_plus) { | |
| 213 delta_plus->Times10(); | |
| 214 } | |
| 215 } else if (in_delta_room_minus && in_delta_room_plus) { | |
| 216 // Let's see if 2*numerator < denominator. | |
| 217 // If yes, then the next digit would be < 5 and we can round dow
n. | |
| 218 int compare = Bignum::PlusCompare(*numerator, *numerator, *denom
inator); | |
| 219 if (compare < 0) { | |
| 220 // Remaining digits are less than .5. -> Round down (== do n
othing). | |
| 221 } else if (compare > 0) { | |
| 222 // Remaining digits are more than .5 of denominator. -> Roun
d up. | |
| 223 // Note that the last digit could not be a '9' as otherwise
the whole | |
| 224 // loop would have stopped earlier. | |
| 225 // We still have an assert here in case the preconditions we
re not | |
| 226 // satisfied. | |
| 227 ASSERT(buffer[(*length) - 1] != '9'); | |
| 228 buffer[(*length) - 1]++; | |
| 229 } else { | |
| 230 // Halfway case. | |
| 231 // TODO(floitsch): need a way to solve half-way cases. | |
| 232 // For now let's round towards even (since this is what Ga
y seems to | |
| 233 // do). | |
| 234 | |
| 235 if ((buffer[(*length) - 1] - '0') % 2 == 0) { | |
| 236 // Round down => Do nothing. | |
| 237 } else { | |
| 238 ASSERT(buffer[(*length) - 1] != '9'); | |
| 239 buffer[(*length) - 1]++; | |
| 240 } | |
| 241 } | |
| 242 return; | |
| 243 } else if (in_delta_room_minus) { | |
| 244 // Round down (== do nothing). | |
| 245 return; | |
| 246 } else { // in_delta_room_plus | |
| 247 // Round up. | |
| 248 // Note again that the last digit could not be '9' since this wo
uld have | |
| 249 // stopped the loop earlier. | |
| 250 // We still have an ASSERT here, in case the preconditions were
not | |
| 251 // satisfied. | |
| 252 ASSERT(buffer[(*length) -1] != '9'); | |
| 253 buffer[(*length) - 1]++; | |
| 254 return; | |
| 255 } | |
| 256 } | |
| 257 } | |
| 258 | |
| 259 | |
| 260 // Let v = numerator / denominator < 10. | |
| 261 // Then we generate 'count' digits of d = x.xxxxx... (without the decimal po
int) | |
| 262 // from left to right. Once 'count' digits have been produced we decide weth
er | |
| 263 // to round up or down. Remainders of exactly .5 round upwards. Numbers such | |
| 264 // as 9.999999 propagate a carry all the way, and change the | |
| 265 // exponent (decimal_point), when rounding upwards. | |
| 266 static void GenerateCountedDigits(int count, int* decimal_point, | |
| 267 Bignum* numerator, Bignum* denominator, | |
| 268 Vector<char>(buffer), int* length) { | |
| 269 ASSERT(count >= 0); | |
| 270 for (int i = 0; i < count - 1; ++i) { | |
| 271 uint16_t digit; | |
| 272 digit = numerator->DivideModuloIntBignum(*denominator); | |
| 273 ASSERT(digit <= 9); // digit is a uint16_t and therefore always pos
itive. | |
| 274 // digit = numerator / denominator (integer division). | |
| 275 // numerator = numerator % denominator. | |
| 276 buffer[i] = static_cast<char>(digit + '0'); | |
| 277 // Prepare for next iteration. | |
| 278 numerator->Times10(); | |
| 279 } | |
| 280 // Generate the last digit. | |
| 281 uint16_t digit; | |
| 282 digit = numerator->DivideModuloIntBignum(*denominator); | |
| 283 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) { | |
| 284 digit++; | |
| 285 } | |
| 286 buffer[count - 1] = static_cast<char>(digit + '0'); | |
| 287 // Correct bad digits (in case we had a sequence of '9's). Propagate the | |
| 288 // carry until we hat a non-'9' or til we reach the first digit. | |
| 289 for (int i = count - 1; i > 0; --i) { | |
| 290 if (buffer[i] != '0' + 10) break; | |
| 291 buffer[i] = '0'; | |
| 292 buffer[i - 1]++; | |
| 293 } | |
| 294 if (buffer[0] == '0' + 10) { | |
| 295 // Propagate a carry past the top place. | |
| 296 buffer[0] = '1'; | |
| 297 (*decimal_point)++; | |
| 298 } | |
| 299 *length = count; | |
| 300 } | |
| 301 | |
| 302 | |
| 303 // Generates 'requested_digits' after the decimal point. It might omit | |
| 304 // trailing '0's. If the input number is too small then no digits at all are | |
| 305 // generated (ex.: 2 fixed digits for 0.00001). | |
| 306 // | |
| 307 // Input verifies: 1 <= (numerator + delta) / denominator < 10. | |
| 308 static void BignumToFixed(int requested_digits, int* decimal_point, | |
| 309 Bignum* numerator, Bignum* denominator, | |
| 310 Vector<char>(buffer), int* length) { | |
| 311 // Note that we have to look at more than just the requested_digits, sin
ce | |
| 312 // a number could be rounded up. Example: v=0.5 with requested_digits=0. | |
| 313 // Even though the power of v equals 0 we can't just stop here. | |
| 314 if (-(*decimal_point) > requested_digits) { | |
| 315 // The number is definitively too small. | |
| 316 // Ex: 0.001 with requested_digits == 1. | |
| 317 // Set decimal-point to -requested_digits. This is what Gay does. | |
| 318 // Note that it should not have any effect anyways since the string
is | |
| 319 // empty. | |
| 320 *decimal_point = -requested_digits; | |
| 321 *length = 0; | |
| 322 return; | |
| 323 } else if (-(*decimal_point) == requested_digits) { | |
| 324 // We only need to verify if the number rounds down or up. | |
| 325 // Ex: 0.04 and 0.06 with requested_digits == 1. | |
| 326 ASSERT(*decimal_point == -requested_digits); | |
| 327 // Initially the fraction lies in range (1, 10]. Multiply the denomi
nator | |
| 328 // by 10 so that we can compare more easily. | |
| 329 denominator->Times10(); | |
| 330 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0)
{ | |
| 331 // If the fraction is >= 0.5 then we have to include the rounded | |
| 332 // digit. | |
| 333 buffer[0] = '1'; | |
| 334 *length = 1; | |
| 335 (*decimal_point)++; | |
| 336 } else { | |
| 337 // Note that we caught most of similar cases earlier. | |
| 338 *length = 0; | |
| 339 } | |
| 340 return; | |
| 341 } else { | |
| 342 // The requested digits correspond to the digits after the point. | |
| 343 // The variable 'needed_digits' includes the digits before the point
. | |
| 344 int needed_digits = (*decimal_point) + requested_digits; | |
| 345 GenerateCountedDigits(needed_digits, decimal_point, | |
| 346 numerator, denominator, | |
| 347 buffer, length); | |
| 348 } | |
| 349 } | |
| 350 | |
| 351 | |
| 352 // Returns an estimation of k such that 10^(k-1) <= v < 10^k where | |
| 353 // v = f * 2^exponent and 2^52 <= f < 2^53. | |
| 354 // v is hence a normalized double with the given exponent. The output is an | |
| 355 // approximation for the exponent of the decimal approimation .digits * 10^k
. | |
| 356 // | |
| 357 // The result might undershoot by 1 in which case 10^k <= v < 10^k+1. | |
| 358 // Note: this property holds for v's upper boundary m+ too. | |
| 359 // 10^k <= m+ < 10^k+1. | |
| 360 // (see explanation below). | |
| 361 // | |
| 362 // Examples: | |
| 363 // EstimatePower(0) => 16 | |
| 364 // EstimatePower(-52) => 0 | |
| 365 // | |
| 366 // Note: e >= 0 => EstimatedPower(e) > 0. No similar claim can be made for e
<0. | |
| 367 static int EstimatePower(int exponent) { | |
| 368 // This function estimates log10 of v where v = f*2^e (with e == exponen
t). | |
| 369 // Note that 10^floor(log10(v)) <= v, but v <= 10^ceil(log10(v)). | |
| 370 // Note that f is bounded by its container size. Let p = 53 (the double'
s | |
| 371 // significand size). Then 2^(p-1) <= f < 2^p. | |
| 372 // | |
| 373 // Given that log10(v) == log2(v)/log2(10) and e+(len(f)-1) is quite clo
se | |
| 374 // to log2(v) the function is simplified to (e+(len(f)-1)/log2(10)). | |
| 375 // The computed number undershoots by less than 0.631 (when we compute l
og3 | |
| 376 // and not log10). | |
| 377 // | |
| 378 // Optimization: since we only need an approximated result this computat
ion | |
| 379 // can be performed on 64 bit integers. On x86/x64 architecture the spee
dup is | |
| 380 // not really measurable, though. | |
| 381 // | |
| 382 // Since we want to avoid overshooting we decrement by 1e10 so that | |
| 383 // floating-point imprecisions don't affect us. | |
| 384 // | |
| 385 // Explanation for v's boundary m+: the computation takes advantage of | |
| 386 // the fact that 2^(p-1) <= f < 2^p. Boundaries still satisfy this requi
rement | |
| 387 // (even for denormals where the delta can be much more important). | |
| 388 | |
| 389 const double k1Log10 = 0.30102999566398114; // 1/lg(10) | |
| 390 | |
| 391 // For doubles len(f) == 53 (don't forget the hidden bit). | |
| 392 const int kSignificandSize = 53; | |
| 393 double estimate = ceil((exponent + kSignificandSize - 1) * k1Log10 - 1e-
10); | |
| 394 return static_cast<int>(estimate); | |
| 395 } | |
| 396 | |
| 397 | |
| 398 // See comments for InitialScaledStartValues. | |
| 399 static void InitialScaledStartValuesPositiveExponent( | |
| 400 double v, int estimated
_power, bool need_boundary_deltas, | |
| 401 Bignum* numerator, Bign
um* denominator, | |
| 402 Bignum* delta_minus, Bi
gnum* delta_plus) { | |
| 403 // A positive exponent implies a positive power. | |
| 404 ASSERT(estimated_power >= 0); | |
| 405 // Since the estimated_power is positive we simply multiply the denomina
tor | |
| 406 // by 10^estimated_power. | |
| 407 | |
| 408 // numerator = v. | |
| 409 numerator->AssignUInt64(Double(v).Significand()); | |
| 410 numerator->ShiftLeft(Double(v).Exponent()); | |
| 411 // denominator = 10^estimated_power. | |
| 412 denominator->AssignPowerUInt16(10, estimated_power); | |
| 413 | |
| 414 if (need_boundary_deltas) { | |
| 415 // Introduce a common denominator so that the deltas to the boundari
es are | |
| 416 // integers. | |
| 417 denominator->ShiftLeft(1); | |
| 418 numerator->ShiftLeft(1); | |
| 419 // Let v = f * 2^e, then m+ - v = 1/2 * 2^e; With the common | |
| 420 // denominator (of 2) delta_plus equals 2^e. | |
| 421 delta_plus->AssignUInt16(1); | |
| 422 delta_plus->ShiftLeft(Double(v).Exponent()); | |
| 423 // Same for delta_minus (with adjustments below if f == 2^p-1). | |
| 424 delta_minus->AssignUInt16(1); | |
| 425 delta_minus->ShiftLeft(Double(v).Exponent()); | |
| 426 | |
| 427 // If the significand (without the hidden bit) is 0, then the lower | |
| 428 // boundary is closer than just half a ulp (unit in the last place). | |
| 429 // There is only one exception: if the next lower number is a denorm
al then | |
| 430 // the distance is 1 ulp. This cannot be the case for exponent >= 0
(but we | |
| 431 // have to test it in the other function where exponent < 0). | |
| 432 uint64_t v_bits = Double(v).AsUint64(); | |
| 433 if ((v_bits & Double::kSignificandMask) == 0) { | |
| 434 // The lower boundary is closer at half the distance of "normal"
numbers. | |
| 435 // Increase the common denominator and adapt all but the delta_m
inus. | |
| 436 denominator->ShiftLeft(1); // *2 | |
| 437 numerator->ShiftLeft(1); // *2 | |
| 438 delta_plus->ShiftLeft(1); // *2 | |
| 439 } | |
| 440 } | |
| 441 } | |
| 442 | |
| 443 | |
| 444 // See comments for InitialScaledStartValues | |
| 445 static void InitialScaledStartValuesNegativeExponentPositivePower( | |
| 446 double v,
int estimated_power, bool need_boundary_deltas, | |
| 447 Bignum* nu
merator, Bignum* denominator, | |
| 448 Bignum* de
lta_minus, Bignum* delta_plus) { | |
| 449 uint64_t significand = Double(v).Significand(); | |
| 450 int exponent = Double(v).Exponent(); | |
| 451 // v = f * 2^e with e < 0, and with estimated_power >= 0. | |
| 452 // This means that e is close to 0 (have a look at how estimated_power i
s | |
| 453 // computed). | |
| 454 | |
| 455 // numerator = significand | |
| 456 // since v = significand * 2^exponent this is equivalent to | |
| 457 // numerator = v * / 2^-exponent | |
| 458 numerator->AssignUInt64(significand); | |
| 459 // denominator = 10^estimated_power * 2^-exponent (with exponent < 0) | |
| 460 denominator->AssignPowerUInt16(10, estimated_power); | |
| 461 denominator->ShiftLeft(-exponent); | |
| 462 | |
| 463 if (need_boundary_deltas) { | |
| 464 // Introduce a common denominator so that the deltas to the boundari
es are | |
| 465 // integers. | |
| 466 denominator->ShiftLeft(1); | |
| 467 numerator->ShiftLeft(1); | |
| 468 // Let v = f * 2^e, then m+ - v = 1/2 * 2^e; With the common | |
| 469 // denominator (of 2) delta_plus equals 2^e. | |
| 470 // Given that the denominator already includes v's exponent the dist
ance | |
| 471 // to the boundaries is simply 1. | |
| 472 delta_plus->AssignUInt16(1); | |
| 473 // Same for delta_minus (with adjustments below if f == 2^p-1). | |
| 474 delta_minus->AssignUInt16(1); | |
| 475 | |
| 476 // If the significand (without the hidden bit) is 0, then the lower | |
| 477 // boundary is closer than just one ulp (unit in the last place). | |
| 478 // There is only one exception: if the next lower number is a denorm
al | |
| 479 // then the distance is 1 ulp. Since the exponent is close to zero | |
| 480 // (otherwise estimated_power would have been negative) this cannot
happen | |
| 481 // here either. | |
| 482 uint64_t v_bits = Double(v).AsUint64(); | |
| 483 if ((v_bits & Double::kSignificandMask) == 0) { | |
| 484 // The lower boundary is closer at half the distance of "normal"
numbers. | |
| 485 // Increase the denominator and adapt all but the delta_minus. | |
| 486 denominator->ShiftLeft(1); // *2 | |
| 487 numerator->ShiftLeft(1); // *2 | |
| 488 delta_plus->ShiftLeft(1); // *2 | |
| 489 } | |
| 490 } | |
| 491 } | |
| 492 | |
| 493 | |
| 494 // See comments for InitialScaledStartValues | |
| 495 static void InitialScaledStartValuesNegativeExponentNegativePower( | |
| 496 double v,
int estimated_power, bool need_boundary_deltas, | |
| 497 Bignum* nu
merator, Bignum* denominator, | |
| 498 Bignum* de
lta_minus, Bignum* delta_plus) { | |
| 499 const uint64_t kMinimalNormalizedExponent = | |
| 500 UINT64_2PART_C(0x00100000, 00000000); | |
| 501 uint64_t significand = Double(v).Significand(); | |
| 502 int exponent = Double(v).Exponent(); | |
| 503 // Instead of multiplying the denominator with 10^estimated_power we | |
| 504 // multiply all values (numerator and deltas) by 10^-estimated_power. | |
| 505 | |
| 506 // Use numerator as temporary container for power_ten. | |
| 507 Bignum* power_ten = numerator; | |
| 508 power_ten->AssignPowerUInt16(10, -estimated_power); | |
| 509 | |
| 510 if (need_boundary_deltas) { | |
| 511 // Since power_ten == numerator we must make a copy of 10^estimated_
power | |
| 512 // before we complete the computation of the numerator. | |
| 513 // delta_plus = delta_minus = 10^estimated_power | |
| 514 delta_plus->AssignBignum(*power_ten); | |
| 515 delta_minus->AssignBignum(*power_ten); | |
| 516 } | |
| 517 | |
| 518 // numerator = significand * 2 * 10^-estimated_power | |
| 519 // since v = significand * 2^exponent this is equivalent to | |
| 520 // numerator = v * 10^-estimated_power * 2 * 2^-exponent. | |
| 521 // Remember: numerator has been abused as power_ten. So no need to assig
n it | |
| 522 // to itself. | |
| 523 ASSERT(numerator == power_ten); | |
| 524 numerator->MultiplyByUInt64(significand); | |
| 525 | |
| 526 // denominator = 2 * 2^-exponent with exponent < 0. | |
| 527 denominator->AssignUInt16(1); | |
| 528 denominator->ShiftLeft(-exponent); | |
| 529 | |
| 530 if (need_boundary_deltas) { | |
| 531 // Introduce a common denominator so that the deltas to the boundari
es are | |
| 532 // integers. | |
| 533 numerator->ShiftLeft(1); | |
| 534 denominator->ShiftLeft(1); | |
| 535 // With this shift the boundaries have their correct value, since | |
| 536 // delta_plus = 10^-estimated_power, and | |
| 537 // delta_minus = 10^-estimated_power. | |
| 538 // These assignments have been done earlier. | |
| 539 | |
| 540 // The special case where the lower boundary is twice as close. | |
| 541 // This time we have to look out for the exception too. | |
| 542 uint64_t v_bits = Double(v).AsUint64(); | |
| 543 if ((v_bits & Double::kSignificandMask) == 0 && | |
| 544 // The only exception where a significand == 0 has its boundarie
s at | |
| 545 // "normal" distances: | |
| 546 (v_bits & Double::kExponentMask) != kMinimalNormalizedExponent)
{ | |
| 547 numerator->ShiftLeft(1); // *2 | |
| 548 denominator->ShiftLeft(1); // *2 | |
| 549 delta_plus->ShiftLeft(1); // *2 | |
| 550 } | |
| 551 } | |
| 552 } | |
| 553 | |
| 554 | |
| 555 // Let v = significand * 2^exponent. | |
| 556 // Computes v / 10^estimated_power exactly, as a ratio of two bignums, numer
ator | |
| 557 // and denominator. The functions GenerateShortestDigits and | |
| 558 // GenerateCountedDigits will then convert this ratio to its decimal | |
| 559 // representation d, with the required accuracy. | |
| 560 // Then d * 10^estimated_power is the representation of v. | |
| 561 // (Note: the fraction and the estimated_power might get adjusted before | |
| 562 // generating the decimal representation.) | |
| 563 // | |
| 564 // The initial start values consist of: | |
| 565 // - a scaled numerator: s.t. numerator/denominator == v / 10^estimated_pow
er. | |
| 566 // - a scaled (common) denominator. | |
| 567 // optionally (used by GenerateShortestDigits to decide if it has the short
est | |
| 568 // decimal converting back to v): | |
| 569 // - v - m-: the distance to the lower boundary. | |
| 570 // - m+ - v: the distance to the upper boundary. | |
| 571 // | |
| 572 // v, m+, m-, and therefore v - m- and m+ - v all share the same denominator
. | |
| 573 // | |
| 574 // Let ep == estimated_power, then the returned values will satisfy: | |
| 575 // v / 10^ep = numerator / denominator. | |
| 576 // v's boundarys m- and m+: | |
| 577 // m- / 10^ep == v / 10^ep - delta_minus / denominator | |
| 578 // m+ / 10^ep == v / 10^ep + delta_plus / denominator | |
| 579 // Or in other words: | |
| 580 // m- == v - delta_minus * 10^ep / denominator; | |
| 581 // m+ == v + delta_plus * 10^ep / denominator; | |
| 582 // | |
| 583 // Since 10^(k-1) <= v < 10^k (with k == estimated_power) | |
| 584 // or 10^k <= v < 10^(k+1) | |
| 585 // we then have 0.1 <= numerator/denominator < 1 | |
| 586 // or 1 <= numerator/denominator < 10 | |
| 587 // | |
| 588 // It is then easy to kickstart the digit-generation routine. | |
| 589 // | |
| 590 // The boundary-deltas are only filled if need_boundary_deltas is set. | |
| 591 static void InitialScaledStartValues(double v, | |
| 592 int estimated_power, | |
| 593 bool need_boundary_deltas, | |
| 594 Bignum* numerator, | |
| 595 Bignum* denominator, | |
| 596 Bignum* delta_minus, | |
| 597 Bignum* delta_plus) { | |
| 598 if (Double(v).Exponent() >= 0) { | |
| 599 InitialScaledStartValuesPositiveExponent( | |
| 600 v, estimated_power, need_bo
undary_deltas, | |
| 601 numerator, denominator, del
ta_minus, delta_plus); | |
| 602 } else if (estimated_power >= 0) { | |
| 603 InitialScaledStartValuesNegativeExponentPositivePower( | |
| 604 v, estimated_p
ower, need_boundary_deltas, | |
| 605 numerator, den
ominator, delta_minus, delta_plus); | |
| 606 } else { | |
| 607 InitialScaledStartValuesNegativeExponentNegativePower( | |
| 608 v, estimated_p
ower, need_boundary_deltas, | |
| 609 numerator, den
ominator, delta_minus, delta_plus); | |
| 610 } | |
| 611 } | |
| 612 | |
| 613 | |
| 614 // This routine multiplies numerator/denominator so that its values lies in
the | |
| 615 // range 1-10. That is after a call to this function we have: | |
| 616 // 1 <= (numerator + delta_plus) /denominator < 10. | |
| 617 // Let numerator the input before modification and numerator' the argument | |
| 618 // after modification, then the output-parameter decimal_point is such that | |
| 619 // numerator / denominator * 10^estimated_power == | |
| 620 // numerator' / denominator' * 10^(decimal_point - 1) | |
| 621 // In some cases estimated_power was too low, and this is already the case.
We | |
| 622 // then simply adjust the power so that 10^(k-1) <= v < 10^k (with k == | |
| 623 // estimated_power) but do not touch the numerator or denominator. | |
| 624 // Otherwise the routine multiplies the numerator and the deltas by 10. | |
| 625 static void FixupMultiply10(int estimated_power, bool is_even, | |
| 626 int* decimal_point, | |
| 627 Bignum* numerator, Bignum* denominator, | |
| 628 Bignum* delta_minus, Bignum* delta_plus) { | |
| 629 bool in_range; | |
| 630 if (is_even) { | |
| 631 // For IEEE doubles half-way cases (in decimal system numbers ending
with 5) | |
| 632 // are rounded to the closest floating-point number with even signif
icand. | |
| 633 in_range = Bignum::PlusCompare(*numerator, *delta_plus, *denominator
) >= 0; | |
| 634 } else { | |
| 635 in_range = Bignum::PlusCompare(*numerator, *delta_plus, *denominator
) > 0; | |
| 636 } | |
| 637 if (in_range) { | |
| 638 // Since numerator + delta_plus >= denominator we already have | |
| 639 // 1 <= numerator/denominator < 10. Simply update the estimated_powe
r. | |
| 640 *decimal_point = estimated_power + 1; | |
| 641 } else { | |
| 642 *decimal_point = estimated_power; | |
| 643 numerator->Times10(); | |
| 644 if (Bignum::Equal(*delta_minus, *delta_plus)) { | |
| 645 delta_minus->Times10(); | |
| 646 delta_plus->AssignBignum(*delta_minus); | |
| 647 } else { | |
| 648 delta_minus->Times10(); | |
| 649 delta_plus->Times10(); | |
| 650 } | |
| 651 } | |
| 652 } | |
| 653 | |
| 654 } // namespace double_conversion | |
| 655 | |
| 656 } // namespace WTF | |
| OLD | NEW |
|---|
Chromium Code Reviews
Issue 2764243002:
Move files in wtf/ to platform/wtf/ (Part 9). (Closed)
