1.1 --- /dev/null Thu Jan 01 00:00:00 1970 +0000
1.2 +++ b/mfbt/double-conversion/fixed-dtoa.cc Wed Dec 31 06:09:35 2014 +0100
1.3 @@ -0,0 +1,402 @@
1.4 +// Copyright 2010 the V8 project authors. All rights reserved.
1.5 +// Redistribution and use in source and binary forms, with or without
1.6 +// modification, are permitted provided that the following conditions are
1.7 +// met:
1.8 +//
1.9 +// * Redistributions of source code must retain the above copyright
1.10 +// notice, this list of conditions and the following disclaimer.
1.11 +// * Redistributions in binary form must reproduce the above
1.12 +// copyright notice, this list of conditions and the following
1.13 +// disclaimer in the documentation and/or other materials provided
1.14 +// with the distribution.
1.15 +// * Neither the name of Google Inc. nor the names of its
1.16 +// contributors may be used to endorse or promote products derived
1.17 +// from this software without specific prior written permission.
1.18 +//
1.19 +// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
1.20 +// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
1.21 +// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
1.22 +// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
1.23 +// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
1.24 +// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
1.25 +// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
1.26 +// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
1.27 +// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
1.28 +// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
1.29 +// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
1.30 +
1.31 +#include <math.h>
1.32 +
1.33 +#include "fixed-dtoa.h"
1.34 +#include "ieee.h"
1.35 +
1.36 +namespace double_conversion {
1.37 +
1.38 +// Represents a 128bit type. This class should be replaced by a native type on
1.39 +// platforms that support 128bit integers.
1.40 +class UInt128 {
1.41 + public:
1.42 + UInt128() : high_bits_(0), low_bits_(0) { }
1.43 + UInt128(uint64_t high, uint64_t low) : high_bits_(high), low_bits_(low) { }
1.44 +
1.45 + void Multiply(uint32_t multiplicand) {
1.46 + uint64_t accumulator;
1.47 +
1.48 + accumulator = (low_bits_ & kMask32) * multiplicand;
1.49 + uint32_t part = static_cast<uint32_t>(accumulator & kMask32);
1.50 + accumulator >>= 32;
1.51 + accumulator = accumulator + (low_bits_ >> 32) * multiplicand;
1.52 + low_bits_ = (accumulator << 32) + part;
1.53 + accumulator >>= 32;
1.54 + accumulator = accumulator + (high_bits_ & kMask32) * multiplicand;
1.55 + part = static_cast<uint32_t>(accumulator & kMask32);
1.56 + accumulator >>= 32;
1.57 + accumulator = accumulator + (high_bits_ >> 32) * multiplicand;
1.58 + high_bits_ = (accumulator << 32) + part;
1.59 + ASSERT((accumulator >> 32) == 0);
1.60 + }
1.61 +
1.62 + void Shift(int shift_amount) {
1.63 + ASSERT(-64 <= shift_amount && shift_amount <= 64);
1.64 + if (shift_amount == 0) {
1.65 + return;
1.66 + } else if (shift_amount == -64) {
1.67 + high_bits_ = low_bits_;
1.68 + low_bits_ = 0;
1.69 + } else if (shift_amount == 64) {
1.70 + low_bits_ = high_bits_;
1.71 + high_bits_ = 0;
1.72 + } else if (shift_amount <= 0) {
1.73 + high_bits_ <<= -shift_amount;
1.74 + high_bits_ += low_bits_ >> (64 + shift_amount);
1.75 + low_bits_ <<= -shift_amount;
1.76 + } else {
1.77 + low_bits_ >>= shift_amount;
1.78 + low_bits_ += high_bits_ << (64 - shift_amount);
1.79 + high_bits_ >>= shift_amount;
1.80 + }
1.81 + }
1.82 +
1.83 + // Modifies *this to *this MOD (2^power).
1.84 + // Returns *this DIV (2^power).
1.85 + int DivModPowerOf2(int power) {
1.86 + if (power >= 64) {
1.87 + int result = static_cast<int>(high_bits_ >> (power - 64));
1.88 + high_bits_ -= static_cast<uint64_t>(result) << (power - 64);
1.89 + return result;
1.90 + } else {
1.91 + uint64_t part_low = low_bits_ >> power;
1.92 + uint64_t part_high = high_bits_ << (64 - power);
1.93 + int result = static_cast<int>(part_low + part_high);
1.94 + high_bits_ = 0;
1.95 + low_bits_ -= part_low << power;
1.96 + return result;
1.97 + }
1.98 + }
1.99 +
1.100 + bool IsZero() const {
1.101 + return high_bits_ == 0 && low_bits_ == 0;
1.102 + }
1.103 +
1.104 + int BitAt(int position) {
1.105 + if (position >= 64) {
1.106 + return static_cast<int>(high_bits_ >> (position - 64)) & 1;
1.107 + } else {
1.108 + return static_cast<int>(low_bits_ >> position) & 1;
1.109 + }
1.110 + }
1.111 +
1.112 + private:
1.113 + static const uint64_t kMask32 = 0xFFFFFFFF;
1.114 + // Value == (high_bits_ << 64) + low_bits_
1.115 + uint64_t high_bits_;
1.116 + uint64_t low_bits_;
1.117 +};
1.118 +
1.119 +
1.120 +static const int kDoubleSignificandSize = 53; // Includes the hidden bit.
1.121 +
1.122 +
1.123 +static void FillDigits32FixedLength(uint32_t number, int requested_length,
1.124 + Vector<char> buffer, int* length) {
1.125 + for (int i = requested_length - 1; i >= 0; --i) {
1.126 + buffer[(*length) + i] = '0' + number % 10;
1.127 + number /= 10;
1.128 + }
1.129 + *length += requested_length;
1.130 +}
1.131 +
1.132 +
1.133 +static void FillDigits32(uint32_t number, Vector<char> buffer, int* length) {
1.134 + int number_length = 0;
1.135 + // We fill the digits in reverse order and exchange them afterwards.
1.136 + while (number != 0) {
1.137 + int digit = number % 10;
1.138 + number /= 10;
1.139 + buffer[(*length) + number_length] = '0' + digit;
1.140 + number_length++;
1.141 + }
1.142 + // Exchange the digits.
1.143 + int i = *length;
1.144 + int j = *length + number_length - 1;
1.145 + while (i < j) {
1.146 + char tmp = buffer[i];
1.147 + buffer[i] = buffer[j];
1.148 + buffer[j] = tmp;
1.149 + i++;
1.150 + j--;
1.151 + }
1.152 + *length += number_length;
1.153 +}
1.154 +
1.155 +
1.156 +static void FillDigits64FixedLength(uint64_t number, int requested_length,
1.157 + Vector<char> buffer, int* length) {
1.158 + const uint32_t kTen7 = 10000000;
1.159 + // For efficiency cut the number into 3 uint32_t parts, and print those.
1.160 + uint32_t part2 = static_cast<uint32_t>(number % kTen7);
1.161 + number /= kTen7;
1.162 + uint32_t part1 = static_cast<uint32_t>(number % kTen7);
1.163 + uint32_t part0 = static_cast<uint32_t>(number / kTen7);
1.164 +
1.165 + FillDigits32FixedLength(part0, 3, buffer, length);
1.166 + FillDigits32FixedLength(part1, 7, buffer, length);
1.167 + FillDigits32FixedLength(part2, 7, buffer, length);
1.168 +}
1.169 +
1.170 +
1.171 +static void FillDigits64(uint64_t number, Vector<char> buffer, int* length) {
1.172 + const uint32_t kTen7 = 10000000;
1.173 + // For efficiency cut the number into 3 uint32_t parts, and print those.
1.174 + uint32_t part2 = static_cast<uint32_t>(number % kTen7);
1.175 + number /= kTen7;
1.176 + uint32_t part1 = static_cast<uint32_t>(number % kTen7);
1.177 + uint32_t part0 = static_cast<uint32_t>(number / kTen7);
1.178 +
1.179 + if (part0 != 0) {
1.180 + FillDigits32(part0, buffer, length);
1.181 + FillDigits32FixedLength(part1, 7, buffer, length);
1.182 + FillDigits32FixedLength(part2, 7, buffer, length);
1.183 + } else if (part1 != 0) {
1.184 + FillDigits32(part1, buffer, length);
1.185 + FillDigits32FixedLength(part2, 7, buffer, length);
1.186 + } else {
1.187 + FillDigits32(part2, buffer, length);
1.188 + }
1.189 +}
1.190 +
1.191 +
1.192 +static void RoundUp(Vector<char> buffer, int* length, int* decimal_point) {
1.193 + // An empty buffer represents 0.
1.194 + if (*length == 0) {
1.195 + buffer[0] = '1';
1.196 + *decimal_point = 1;
1.197 + *length = 1;
1.198 + return;
1.199 + }
1.200 + // Round the last digit until we either have a digit that was not '9' or until
1.201 + // we reached the first digit.
1.202 + buffer[(*length) - 1]++;
1.203 + for (int i = (*length) - 1; i > 0; --i) {
1.204 + if (buffer[i] != '0' + 10) {
1.205 + return;
1.206 + }
1.207 + buffer[i] = '0';
1.208 + buffer[i - 1]++;
1.209 + }
1.210 + // If the first digit is now '0' + 10, we would need to set it to '0' and add
1.211 + // a '1' in front. However we reach the first digit only if all following
1.212 + // digits had been '9' before rounding up. Now all trailing digits are '0' and
1.213 + // we simply switch the first digit to '1' and update the decimal-point
1.214 + // (indicating that the point is now one digit to the right).
1.215 + if (buffer[0] == '0' + 10) {
1.216 + buffer[0] = '1';
1.217 + (*decimal_point)++;
1.218 + }
1.219 +}
1.220 +
1.221 +
1.222 +// The given fractionals number represents a fixed-point number with binary
1.223 +// point at bit (-exponent).
1.224 +// Preconditions:
1.225 +// -128 <= exponent <= 0.
1.226 +// 0 <= fractionals * 2^exponent < 1
1.227 +// The buffer holds the result.
1.228 +// The function will round its result. During the rounding-process digits not
1.229 +// generated by this function might be updated, and the decimal-point variable
1.230 +// might be updated. If this function generates the digits 99 and the buffer
1.231 +// already contained "199" (thus yielding a buffer of "19999") then a
1.232 +// rounding-up will change the contents of the buffer to "20000".
1.233 +static void FillFractionals(uint64_t fractionals, int exponent,
1.234 + int fractional_count, Vector<char> buffer,
1.235 + int* length, int* decimal_point) {
1.236 + ASSERT(-128 <= exponent && exponent <= 0);
1.237 + // 'fractionals' is a fixed-point number, with binary point at bit
1.238 + // (-exponent). Inside the function the non-converted remainder of fractionals
1.239 + // is a fixed-point number, with binary point at bit 'point'.
1.240 + if (-exponent <= 64) {
1.241 + // One 64 bit number is sufficient.
1.242 + ASSERT(fractionals >> 56 == 0);
1.243 + int point = -exponent;
1.244 + for (int i = 0; i < fractional_count; ++i) {
1.245 + if (fractionals == 0) break;
1.246 + // Instead of multiplying by 10 we multiply by 5 and adjust the point
1.247 + // location. This way the fractionals variable will not overflow.
1.248 + // Invariant at the beginning of the loop: fractionals < 2^point.
1.249 + // Initially we have: point <= 64 and fractionals < 2^56
1.250 + // After each iteration the point is decremented by one.
1.251 + // Note that 5^3 = 125 < 128 = 2^7.
1.252 + // Therefore three iterations of this loop will not overflow fractionals
1.253 + // (even without the subtraction at the end of the loop body). At this
1.254 + // time point will satisfy point <= 61 and therefore fractionals < 2^point
1.255 + // and any further multiplication of fractionals by 5 will not overflow.
1.256 + fractionals *= 5;
1.257 + point--;
1.258 + int digit = static_cast<int>(fractionals >> point);
1.259 + buffer[*length] = '0' + digit;
1.260 + (*length)++;
1.261 + fractionals -= static_cast<uint64_t>(digit) << point;
1.262 + }
1.263 + // If the first bit after the point is set we have to round up.
1.264 + if (((fractionals >> (point - 1)) & 1) == 1) {
1.265 + RoundUp(buffer, length, decimal_point);
1.266 + }
1.267 + } else { // We need 128 bits.
1.268 + ASSERT(64 < -exponent && -exponent <= 128);
1.269 + UInt128 fractionals128 = UInt128(fractionals, 0);
1.270 + fractionals128.Shift(-exponent - 64);
1.271 + int point = 128;
1.272 + for (int i = 0; i < fractional_count; ++i) {
1.273 + if (fractionals128.IsZero()) break;
1.274 + // As before: instead of multiplying by 10 we multiply by 5 and adjust the
1.275 + // point location.
1.276 + // This multiplication will not overflow for the same reasons as before.
1.277 + fractionals128.Multiply(5);
1.278 + point--;
1.279 + int digit = fractionals128.DivModPowerOf2(point);
1.280 + buffer[*length] = '0' + digit;
1.281 + (*length)++;
1.282 + }
1.283 + if (fractionals128.BitAt(point - 1) == 1) {
1.284 + RoundUp(buffer, length, decimal_point);
1.285 + }
1.286 + }
1.287 +}
1.288 +
1.289 +
1.290 +// Removes leading and trailing zeros.
1.291 +// If leading zeros are removed then the decimal point position is adjusted.
1.292 +static void TrimZeros(Vector<char> buffer, int* length, int* decimal_point) {
1.293 + while (*length > 0 && buffer[(*length) - 1] == '0') {
1.294 + (*length)--;
1.295 + }
1.296 + int first_non_zero = 0;
1.297 + while (first_non_zero < *length && buffer[first_non_zero] == '0') {
1.298 + first_non_zero++;
1.299 + }
1.300 + if (first_non_zero != 0) {
1.301 + for (int i = first_non_zero; i < *length; ++i) {
1.302 + buffer[i - first_non_zero] = buffer[i];
1.303 + }
1.304 + *length -= first_non_zero;
1.305 + *decimal_point -= first_non_zero;
1.306 + }
1.307 +}
1.308 +
1.309 +
1.310 +bool FastFixedDtoa(double v,
1.311 + int fractional_count,
1.312 + Vector<char> buffer,
1.313 + int* length,
1.314 + int* decimal_point) {
1.315 + const uint32_t kMaxUInt32 = 0xFFFFFFFF;
1.316 + uint64_t significand = Double(v).Significand();
1.317 + int exponent = Double(v).Exponent();
1.318 + // v = significand * 2^exponent (with significand a 53bit integer).
1.319 + // If the exponent is larger than 20 (i.e. we may have a 73bit number) then we
1.320 + // don't know how to compute the representation. 2^73 ~= 9.5*10^21.
1.321 + // If necessary this limit could probably be increased, but we don't need
1.322 + // more.
1.323 + if (exponent > 20) return false;
1.324 + if (fractional_count > 20) return false;
1.325 + *length = 0;
1.326 + // At most kDoubleSignificandSize bits of the significand are non-zero.
1.327 + // Given a 64 bit integer we have 11 0s followed by 53 potentially non-zero
1.328 + // bits: 0..11*..0xxx..53*..xx
1.329 + if (exponent + kDoubleSignificandSize > 64) {
1.330 + // The exponent must be > 11.
1.331 + //
1.332 + // We know that v = significand * 2^exponent.
1.333 + // And the exponent > 11.
1.334 + // We simplify the task by dividing v by 10^17.
1.335 + // The quotient delivers the first digits, and the remainder fits into a 64
1.336 + // bit number.
1.337 + // Dividing by 10^17 is equivalent to dividing by 5^17*2^17.
1.338 + const uint64_t kFive17 = UINT64_2PART_C(0xB1, A2BC2EC5); // 5^17
1.339 + uint64_t divisor = kFive17;
1.340 + int divisor_power = 17;
1.341 + uint64_t dividend = significand;
1.342 + uint32_t quotient;
1.343 + uint64_t remainder;
1.344 + // Let v = f * 2^e with f == significand and e == exponent.
1.345 + // Then need q (quotient) and r (remainder) as follows:
1.346 + // v = q * 10^17 + r
1.347 + // f * 2^e = q * 10^17 + r
1.348 + // f * 2^e = q * 5^17 * 2^17 + r
1.349 + // If e > 17 then
1.350 + // f * 2^(e-17) = q * 5^17 + r/2^17
1.351 + // else
1.352 + // f = q * 5^17 * 2^(17-e) + r/2^e
1.353 + if (exponent > divisor_power) {
1.354 + // We only allow exponents of up to 20 and therefore (17 - e) <= 3
1.355 + dividend <<= exponent - divisor_power;
1.356 + quotient = static_cast<uint32_t>(dividend / divisor);
1.357 + remainder = (dividend % divisor) << divisor_power;
1.358 + } else {
1.359 + divisor <<= divisor_power - exponent;
1.360 + quotient = static_cast<uint32_t>(dividend / divisor);
1.361 + remainder = (dividend % divisor) << exponent;
1.362 + }
1.363 + FillDigits32(quotient, buffer, length);
1.364 + FillDigits64FixedLength(remainder, divisor_power, buffer, length);
1.365 + *decimal_point = *length;
1.366 + } else if (exponent >= 0) {
1.367 + // 0 <= exponent <= 11
1.368 + significand <<= exponent;
1.369 + FillDigits64(significand, buffer, length);
1.370 + *decimal_point = *length;
1.371 + } else if (exponent > -kDoubleSignificandSize) {
1.372 + // We have to cut the number.
1.373 + uint64_t integrals = significand >> -exponent;
1.374 + uint64_t fractionals = significand - (integrals << -exponent);
1.375 + if (integrals > kMaxUInt32) {
1.376 + FillDigits64(integrals, buffer, length);
1.377 + } else {
1.378 + FillDigits32(static_cast<uint32_t>(integrals), buffer, length);
1.379 + }
1.380 + *decimal_point = *length;
1.381 + FillFractionals(fractionals, exponent, fractional_count,
1.382 + buffer, length, decimal_point);
1.383 + } else if (exponent < -128) {
1.384 + // This configuration (with at most 20 digits) means that all digits must be
1.385 + // 0.
1.386 + ASSERT(fractional_count <= 20);
1.387 + buffer[0] = '\0';
1.388 + *length = 0;
1.389 + *decimal_point = -fractional_count;
1.390 + } else {
1.391 + *decimal_point = 0;
1.392 + FillFractionals(significand, exponent, fractional_count,
1.393 + buffer, length, decimal_point);
1.394 + }
1.395 + TrimZeros(buffer, length, decimal_point);
1.396 + buffer[*length] = '\0';
1.397 + if ((*length) == 0) {
1.398 + // The string is empty and the decimal_point thus has no importance. Mimick
1.399 + // Gay's dtoa and and set it to -fractional_count.
1.400 + *decimal_point = -fractional_count;
1.401 + }
1.402 + return true;
1.403 +}
1.404 +
1.405 +} // namespace double_conversion
