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