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