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