code.vuplus.com Git - vuplus_webkit/blob - Source/JavaScriptCore/wtf/dtoa/fixed-dtoa.cc

   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 "UnusedParam.h"
  33 #include "fixed-dtoa.h"
  34 #include "double.h"
  35
  36 namespace WTF {
  37
  38 namespace double_conversion {
  39
  40     // Represents a 128bit type. This class should be replaced by a native type on
  41     // platforms that support 128bit integers.
  42     class UInt128 {
  43     public:
  44         UInt128() : high_bits_(0), low_bits_(0) { }
  45         UInt128(uint64_t high, uint64_t low) : high_bits_(high), low_bits_(low) { }
  46
  47         void Multiply(uint32_t multiplicand) {
  48             uint64_t accumulator;
  49
  50             accumulator = (low_bits_ & kMask32) * multiplicand;
  51             uint32_t part = static_cast<uint32_t>(accumulator & kMask32);
  52             accumulator >>= 32;
  53             accumulator = accumulator + (low_bits_ >> 32) * multiplicand;
  54             low_bits_ = (accumulator << 32) + part;
  55             accumulator >>= 32;
  56             accumulator = accumulator + (high_bits_ & kMask32) * multiplicand;
  57             part = static_cast<uint32_t>(accumulator & kMask32);
  58             accumulator >>= 32;
  59             accumulator = accumulator + (high_bits_ >> 32) * multiplicand;
  60             high_bits_ = (accumulator << 32) + part;
  61             ASSERT((accumulator >> 32) == 0);
  62         }
  63
  64         void Shift(int shift_amount) {
  65             ASSERT(-64 <= shift_amount && shift_amount <= 64);
  66             if (shift_amount == 0) {
  67                 return;
  68             } else if (shift_amount == -64) {
  69                 high_bits_ = low_bits_;
  70                 low_bits_ = 0;
  71             } else if (shift_amount == 64) {
  72                 low_bits_ = high_bits_;
  73                 high_bits_ = 0;
  74             } else if (shift_amount <= 0) {
  75                 high_bits_ <<= -shift_amount;
  76                 high_bits_ += low_bits_ >> (64 + shift_amount);
  77                 low_bits_ <<= -shift_amount;
  78             } else {
  79                 low_bits_ >>= shift_amount;
  80                 low_bits_ += high_bits_ << (64 - shift_amount);
  81                 high_bits_ >>= shift_amount;
  82             }
  83         }
  84
  85         // Modifies *this to *this MOD (2^power).
  86         // Returns *this DIV (2^power).
  87         int DivModPowerOf2(int power) {
  88             if (power >= 64) {
  89                 int result = static_cast<int>(high_bits_ >> (power - 64));
  90                 high_bits_ -= static_cast<uint64_t>(result) << (power - 64);
  91                 return result;
  92             } else {
  93                 uint64_t part_low = low_bits_ >> power;
  94                 uint64_t part_high = high_bits_ << (64 - power);
  95                 int result = static_cast<int>(part_low + part_high);
  96                 high_bits_ = 0;
  97                 low_bits_ -= part_low << power;
  98                 return result;
  99             }
 100         }
 101
 102         bool IsZero() const {
 103             return high_bits_ == 0 && low_bits_ == 0;
 104         }
 105
 106         int BitAt(int position) {
 107             if (position >= 64) {
 108                 return static_cast<int>(high_bits_ >> (position - 64)) & 1;
 109             } else {
 110                 return static_cast<int>(low_bits_ >> position) & 1;
 111             }
 112         }
 113
 114     private:
 115         static const uint64_t kMask32 = 0xFFFFFFFF;
 116         // Value == (high_bits_ << 64) + low_bits_
 117         uint64_t high_bits_;
 118         uint64_t low_bits_;
 119     };
 120
 121
 122     static const int kDoubleSignificandSize = 53;  // Includes the hidden bit.
 123
 124
 125     static void FillDigits32FixedLength(uint32_t number, int requested_length,
 126                                         Vector<char> buffer, int* length) {
 127         for (int i = requested_length - 1; i >= 0; --i) {
 128             buffer[(*length) + i] = '0' + number % 10;
 129             number /= 10;
 130         }
 131         *length += requested_length;
 132     }
 133
 134
 135     static void FillDigits32(uint32_t number, Vector<char> buffer, int* length) {
 136         int number_length = 0;
 137         // We fill the digits in reverse order and exchange them afterwards.
 138         while (number != 0) {
 139             int digit = number % 10;
 140             number /= 10;
 141             buffer[(*length) + number_length] = '0' + digit;
 142             number_length++;
 143         }
 144         // Exchange the digits.
 145         int i = *length;
 146         int j = *length + number_length - 1;
 147         while (i < j) {
 148             char tmp = buffer[i];
 149             buffer[i] = buffer[j];
 150             buffer[j] = tmp;
 151             i++;
 152             j--;
 153         }
 154         *length += number_length;
 155     }
 156
 157
 158     static void FillDigits64FixedLength(uint64_t number, int requested_length,
 159                                         Vector<char> buffer, int* length) {
 160         UNUSED_PARAM(requested_length);
 161         const uint32_t kTen7 = 10000000;
 162         // For efficiency cut the number into 3 uint32_t parts, and print those.
 163         uint32_t part2 = static_cast<uint32_t>(number % kTen7);
 164         number /= kTen7;
 165         uint32_t part1 = static_cast<uint32_t>(number % kTen7);
 166         uint32_t part0 = static_cast<uint32_t>(number / kTen7);
 167
 168         FillDigits32FixedLength(part0, 3, buffer, length);
 169         FillDigits32FixedLength(part1, 7, buffer, length);
 170         FillDigits32FixedLength(part2, 7, buffer, length);
 171     }
 172
 173
 174     static void FillDigits64(uint64_t number, Vector<char> buffer, int* length) {
 175         const uint32_t kTen7 = 10000000;
 176         // For efficiency cut the number into 3 uint32_t parts, and print those.
 177         uint32_t part2 = static_cast<uint32_t>(number % kTen7);
 178         number /= kTen7;
 179         uint32_t part1 = static_cast<uint32_t>(number % kTen7);
 180         uint32_t part0 = static_cast<uint32_t>(number / kTen7);
 181
 182         if (part0 != 0) {
 183             FillDigits32(part0, buffer, length);
 184             FillDigits32FixedLength(part1, 7, buffer, length);
 185             FillDigits32FixedLength(part2, 7, buffer, length);
 186         } else if (part1 != 0) {
 187             FillDigits32(part1, buffer, length);
 188             FillDigits32FixedLength(part2, 7, buffer, length);
 189         } else {
 190             FillDigits32(part2, buffer, length);
 191         }
 192     }
 193
 194
 195     static void RoundUp(Vector<char> buffer, int* length, int* decimal_point) {
 196         // An empty buffer represents 0.
 197         if (*length == 0) {
 198             buffer[0] = '1';
 199             *decimal_point = 1;
 200             *length = 1;
 201             return;
 202         }
 203         // Round the last digit until we either have a digit that was not '9' or until
 204         // we reached the first digit.
 205         buffer[(*length) - 1]++;
 206         for (int i = (*length) - 1; i > 0; --i) {
 207             if (buffer[i] != '0' + 10) {
 208                 return;
 209             }
 210             buffer[i] = '0';
 211             buffer[i - 1]++;
 212         }
 213         // If the first digit is now '0' + 10, we would need to set it to '0' and add
 214         // a '1' in front. However we reach the first digit only if all following
 215         // digits had been '9' before rounding up. Now all trailing digits are '0' and
 216         // we simply switch the first digit to '1' and update the decimal-point
 217         // (indicating that the point is now one digit to the right).
 218         if (buffer[0] == '0' + 10) {
 219             buffer[0] = '1';
 220             (*decimal_point)++;
 221         }
 222     }
 223
 224
 225     // The given fractionals number represents a fixed-point number with binary
 226     // point at bit (-exponent).
 227     // Preconditions:
 228     //   -128 <= exponent <= 0.
 229     //   0 <= fractionals * 2^exponent < 1
 230     //   The buffer holds the result.
 231     // The function will round its result. During the rounding-process digits not
 232     // generated by this function might be updated, and the decimal-point variable
 233     // might be updated. If this function generates the digits 99 and the buffer
 234     // already contained "199" (thus yielding a buffer of "19999") then a
 235     // rounding-up will change the contents of the buffer to "20000".
 236     static void FillFractionals(uint64_t fractionals, int exponent,
 237                                 int fractional_count, Vector<char> buffer,
 238                                 int* length, int* decimal_point) {
 239         ASSERT(-128 <= exponent && exponent <= 0);
 240         // 'fractionals' is a fixed-point number, with binary point at bit
 241         // (-exponent). Inside the function the non-converted remainder of fractionals
 242         // is a fixed-point number, with binary point at bit 'point'.
 243         if (-exponent <= 64) {
 244             // One 64 bit number is sufficient.
 245             ASSERT(fractionals >> 56 == 0);
 246             int point = -exponent;
 247             for (int i = 0; i < fractional_count; ++i) {
 248                 if (fractionals == 0) break;
 249                 // Instead of multiplying by 10 we multiply by 5 and adjust the point
 250                 // location. This way the fractionals variable will not overflow.
 251                 // Invariant at the beginning of the loop: fractionals < 2^point.
 252                 // Initially we have: point <= 64 and fractionals < 2^56
 253                 // After each iteration the point is decremented by one.
 254                 // Note that 5^3 = 125 < 128 = 2^7.
 255                 // Therefore three iterations of this loop will not overflow fractionals
 256                 // (even without the subtraction at the end of the loop body). At this
 257                 // time point will satisfy point <= 61 and therefore fractionals < 2^point
 258                 // and any further multiplication of fractionals by 5 will not overflow.
 259                 fractionals *= 5;
 260                 point--;
 261                 int digit = static_cast<int>(fractionals >> point);
 262                 buffer[*length] = '0' + digit;
 263                 (*length)++;
 264                 fractionals -= static_cast<uint64_t>(digit) << point;
 265             }
 266             // If the first bit after the point is set we have to round up.
 267             if (((fractionals >> (point - 1)) & 1) == 1) {
 268                 RoundUp(buffer, length, decimal_point);
 269             }
 270         } else {  // We need 128 bits.
 271             ASSERT(64 < -exponent && -exponent <= 128);
 272             UInt128 fractionals128 = UInt128(fractionals, 0);
 273             fractionals128.Shift(-exponent - 64);
 274             int point = 128;
 275             for (int i = 0; i < fractional_count; ++i) {
 276                 if (fractionals128.IsZero()) break;
 277                 // As before: instead of multiplying by 10 we multiply by 5 and adjust the
 278                 // point location.
 279                 // This multiplication will not overflow for the same reasons as before.
 280                 fractionals128.Multiply(5);
 281                 point--;
 282                 int digit = fractionals128.DivModPowerOf2(point);
 283                 buffer[*length] = '0' + digit;
 284                 (*length)++;
 285             }
 286             if (fractionals128.BitAt(point - 1) == 1) {
 287                 RoundUp(buffer, length, decimal_point);
 288             }
 289         }
 290     }
 291
 292
 293     // Removes leading and trailing zeros.
 294     // If leading zeros are removed then the decimal point position is adjusted.
 295     static void TrimZeros(Vector<char> buffer, int* length, int* decimal_point) {
 296         while (*length > 0 && buffer[(*length) - 1] == '0') {
 297             (*length)--;
 298         }
 299         int first_non_zero = 0;
 300         while (first_non_zero < *length && buffer[first_non_zero] == '0') {
 301             first_non_zero++;
 302         }
 303         if (first_non_zero != 0) {
 304             for (int i = first_non_zero; i < *length; ++i) {
 305                 buffer[i - first_non_zero] = buffer[i];
 306             }
 307             *length -= first_non_zero;
 308             *decimal_point -= first_non_zero;
 309         }
 310     }
 311
 312
 313     bool FastFixedDtoa(double v,
 314                        int fractional_count,
 315                        Vector<char> buffer,
 316                        int* length,
 317                        int* decimal_point) {
 318         const uint32_t kMaxUInt32 = 0xFFFFFFFF;
 319         uint64_t significand = Double(v).Significand();
 320         int exponent = Double(v).Exponent();
 321         // v = significand * 2^exponent (with significand a 53bit integer).
 322         // If the exponent is larger than 20 (i.e. we may have a 73bit number) then we
 323         // don't know how to compute the representation. 2^73 ~= 9.5*10^21.
 324         // If necessary this limit could probably be increased, but we don't need
 325         // more.
 326         if (exponent > 20) return false;
 327         if (fractional_count > 20) return false;
 328         *length = 0;
 329         // At most kDoubleSignificandSize bits of the significand are non-zero.
 330         // Given a 64 bit integer we have 11 0s followed by 53 potentially non-zero
 331         // bits:  0..11*..0xxx..53*..xx
 332         if (exponent + kDoubleSignificandSize > 64) {
 333             // The exponent must be > 11.
 334             //
 335             // We know that v = significand * 2^exponent.
 336             // And the exponent > 11.
 337             // We simplify the task by dividing v by 10^17.
 338             // The quotient delivers the first digits, and the remainder fits into a 64
 339             // bit number.
 340             // Dividing by 10^17 is equivalent to dividing by 5^17*2^17.
 341             const uint64_t kFive17 = UINT64_2PART_C(0xB1, A2BC2EC5);  // 5^17
 342             uint64_t divisor = kFive17;
 343             int divisor_power = 17;
 344             uint64_t dividend = significand;
 345             uint32_t quotient;
 346             uint64_t remainder;
 347             // Let v = f * 2^e with f == significand and e == exponent.
 348             // Then need q (quotient) and r (remainder) as follows:
 349             //   v            = q * 10^17       + r
 350             //   f * 2^e      = q * 10^17       + r
 351             //   f * 2^e      = q * 5^17 * 2^17 + r
 352             // If e > 17 then
 353             //   f * 2^(e-17) = q * 5^17        + r/2^17
 354             // else
 355             //   f  = q * 5^17 * 2^(17-e) + r/2^e
 356             if (exponent > divisor_power) {
 357                 // We only allow exponents of up to 20 and therefore (17 - e) <= 3
 358                 dividend <<= exponent - divisor_power;
 359                 quotient = static_cast<uint32_t>(dividend / divisor);
 360                 remainder = (dividend % divisor) << divisor_power;
 361             } else {
 362                 divisor <<= divisor_power - exponent;
 363                 quotient = static_cast<uint32_t>(dividend / divisor);
 364                 remainder = (dividend % divisor) << exponent;
 365             }
 366             FillDigits32(quotient, buffer, length);
 367             FillDigits64FixedLength(remainder, divisor_power, buffer, length);
 368             *decimal_point = *length;
 369         } else if (exponent >= 0) {
 370             // 0 <= exponent <= 11
 371             significand <<= exponent;
 372             FillDigits64(significand, buffer, length);
 373             *decimal_point = *length;
 374         } else if (exponent > -kDoubleSignificandSize) {
 375             // We have to cut the number.
 376             uint64_t integrals = significand >> -exponent;
 377             uint64_t fractionals = significand - (integrals << -exponent);
 378             if (integrals > kMaxUInt32) {
 379                 FillDigits64(integrals, buffer, length);
 380             } else {
 381                 FillDigits32(static_cast<uint32_t>(integrals), buffer, length);
 382             }
 383             *decimal_point = *length;
 384             FillFractionals(fractionals, exponent, fractional_count,
 385                             buffer, length, decimal_point);
 386         } else if (exponent < -128) {
 387             // This configuration (with at most 20 digits) means that all digits must be
 388             // 0.
 389             ASSERT(fractional_count <= 20);
 390             buffer[0] = '\0';
 391             *length = 0;
 392             *decimal_point = -fractional_count;
 393         } else {
 394             *decimal_point = 0;
 395             FillFractionals(significand, exponent, fractional_count,
 396                             buffer, length, decimal_point);
 397         }
 398         TrimZeros(buffer, length, decimal_point);
 399         buffer[*length] = '\0';
 400         if ((*length) == 0) {
 401             // The string is empty and the decimal_point thus has no importance. Mimick
 402             // Gay's dtoa and and set it to -fractional_count.
 403             *decimal_point = -fractional_count;
 404         }
 405         return true;
 406     }
 407
 408 }  // namespace double_conversion
 409
 410 } // namespace WTF