1589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch// Copyright 2011 the V8 project authors. All rights reserved. 225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// Redistribution and use in source and binary forms, with or without 325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// modification, are permitted provided that the following conditions are 425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// met: 525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// 625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// * Redistributions of source code must retain the above copyright 725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// notice, this list of conditions and the following disclaimer. 825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// * Redistributions in binary form must reproduce the above 925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// copyright notice, this list of conditions and the following 1025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// disclaimer in the documentation and/or other materials provided 1125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// with the distribution. 1225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// * Neither the name of Google Inc. nor the names of its 1325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// contributors may be used to endorse or promote products derived 1425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// from this software without specific prior written permission. 1525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// 1625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS 1725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT 1825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR 1925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT 2025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL, 2125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT 2225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, 2325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY 2425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT 2525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE 2625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. 2725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 2825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen#include <math.h> 2925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 30589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch#include "../include/v8stdint.h" 31589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch#include "checks.h" 32589d6979ff2ef66fca2d8fa51404c369ca5e9250Ben Murdoch#include "utils.h" 3325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 3425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen#include "double.h" 3525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen#include "fixed-dtoa.h" 3625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 3725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsennamespace v8 { 3825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsennamespace internal { 3925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 4025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// Represents a 128bit type. This class should be replaced by a native type on 4125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// platforms that support 128bit integers. 4225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenclass UInt128 { 4325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen public: 4425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen UInt128() : high_bits_(0), low_bits_(0) { } 4525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen UInt128(uint64_t high, uint64_t low) : high_bits_(high), low_bits_(low) { } 4625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 4725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen void Multiply(uint32_t multiplicand) { 4825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t accumulator; 4925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 5025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen accumulator = (low_bits_ & kMask32) * multiplicand; 5125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint32_t part = static_cast<uint32_t>(accumulator & kMask32); 5225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen accumulator >>= 32; 5325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen accumulator = accumulator + (low_bits_ >> 32) * multiplicand; 5425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen low_bits_ = (accumulator << 32) + part; 5525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen accumulator >>= 32; 5625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen accumulator = accumulator + (high_bits_ & kMask32) * multiplicand; 5725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen part = static_cast<uint32_t>(accumulator & kMask32); 5825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen accumulator >>= 32; 5925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen accumulator = accumulator + (high_bits_ >> 32) * multiplicand; 6025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen high_bits_ = (accumulator << 32) + part; 6125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen ASSERT((accumulator >> 32) == 0); 6225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 6325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 6425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen void Shift(int shift_amount) { 6525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen ASSERT(-64 <= shift_amount && shift_amount <= 64); 6625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (shift_amount == 0) { 6725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return; 6825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else if (shift_amount == -64) { 6925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen high_bits_ = low_bits_; 7025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen low_bits_ = 0; 7125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else if (shift_amount == 64) { 7225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen low_bits_ = high_bits_; 7325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen high_bits_ = 0; 7425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else if (shift_amount <= 0) { 7525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen high_bits_ <<= -shift_amount; 7625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen high_bits_ += low_bits_ >> (64 + shift_amount); 7725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen low_bits_ <<= -shift_amount; 7825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else { 7925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen low_bits_ >>= shift_amount; 8025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen low_bits_ += high_bits_ << (64 - shift_amount); 8125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen high_bits_ >>= shift_amount; 8225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 8325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 8425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 8525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Modifies *this to *this MOD (2^power). 8625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Returns *this DIV (2^power). 8725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int DivModPowerOf2(int power) { 8825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (power >= 64) { 8925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int result = static_cast<int>(high_bits_ >> (power - 64)); 9025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen high_bits_ -= static_cast<uint64_t>(result) << (power - 64); 9125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return result; 9225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else { 9325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t part_low = low_bits_ >> power; 9425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t part_high = high_bits_ << (64 - power); 9525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int result = static_cast<int>(part_low + part_high); 9625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen high_bits_ = 0; 9725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen low_bits_ -= part_low << power; 9825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return result; 9925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 10025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 10125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 10225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen bool IsZero() const { 10325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return high_bits_ == 0 && low_bits_ == 0; 10425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 10525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 10625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int BitAt(int position) { 10725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (position >= 64) { 10825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return static_cast<int>(high_bits_ >> (position - 64)) & 1; 10925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else { 11025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return static_cast<int>(low_bits_ >> position) & 1; 11125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 11225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 11325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 11425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen private: 11525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen static const uint64_t kMask32 = 0xFFFFFFFF; 11625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Value == (high_bits_ << 64) + low_bits_ 11725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t high_bits_; 11825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t low_bits_; 11925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen}; 12025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 12125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 12225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenstatic const int kDoubleSignificandSize = 53; // Includes the hidden bit. 12325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 12425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 12525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenstatic void FillDigits32FixedLength(uint32_t number, int requested_length, 12625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen Vector<char> buffer, int* length) { 12725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen for (int i = requested_length - 1; i >= 0; --i) { 12825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[(*length) + i] = '0' + number % 10; 12925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen number /= 10; 13025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 13125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *length += requested_length; 13225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} 13325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 13425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 13525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenstatic void FillDigits32(uint32_t number, Vector<char> buffer, int* length) { 13625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int number_length = 0; 13725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // We fill the digits in reverse order and exchange them afterwards. 13825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen while (number != 0) { 13925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int digit = number % 10; 14025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen number /= 10; 14125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[(*length) + number_length] = '0' + digit; 14225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen number_length++; 14325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 14425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Exchange the digits. 14525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int i = *length; 14625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int j = *length + number_length - 1; 14725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen while (i < j) { 14825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen char tmp = buffer[i]; 14925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[i] = buffer[j]; 15025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[j] = tmp; 15125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen i++; 15225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen j--; 15325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 15425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *length += number_length; 15525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} 15625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 15725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 15825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenstatic void FillDigits64FixedLength(uint64_t number, int requested_length, 15925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen Vector<char> buffer, int* length) { 16025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen const uint32_t kTen7 = 10000000; 16125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // For efficiency cut the number into 3 uint32_t parts, and print those. 16225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint32_t part2 = static_cast<uint32_t>(number % kTen7); 16325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen number /= kTen7; 16425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint32_t part1 = static_cast<uint32_t>(number % kTen7); 16525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint32_t part0 = static_cast<uint32_t>(number / kTen7); 16625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 16725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32FixedLength(part0, 3, buffer, length); 16825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32FixedLength(part1, 7, buffer, length); 16925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32FixedLength(part2, 7, buffer, length); 17025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} 17125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 17225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 17325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenstatic void FillDigits64(uint64_t number, Vector<char> buffer, int* length) { 17425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen const uint32_t kTen7 = 10000000; 17525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // For efficiency cut the number into 3 uint32_t parts, and print those. 17625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint32_t part2 = static_cast<uint32_t>(number % kTen7); 17725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen number /= kTen7; 17825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint32_t part1 = static_cast<uint32_t>(number % kTen7); 17925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint32_t part0 = static_cast<uint32_t>(number / kTen7); 18025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 18125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (part0 != 0) { 18225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32(part0, buffer, length); 18325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32FixedLength(part1, 7, buffer, length); 18425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32FixedLength(part2, 7, buffer, length); 18525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else if (part1 != 0) { 18625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32(part1, buffer, length); 18725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32FixedLength(part2, 7, buffer, length); 18825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else { 18925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32(part2, buffer, length); 19025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 19125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} 19225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 19325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 19425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenstatic void RoundUp(Vector<char> buffer, int* length, int* decimal_point) { 19525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // An empty buffer represents 0. 19625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (*length == 0) { 19725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[0] = '1'; 19825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *decimal_point = 1; 19925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *length = 1; 20025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return; 20125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 20225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Round the last digit until we either have a digit that was not '9' or until 20325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // we reached the first digit. 20425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[(*length) - 1]++; 20525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen for (int i = (*length) - 1; i > 0; --i) { 20625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (buffer[i] != '0' + 10) { 20725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return; 20825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 20925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[i] = '0'; 21025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[i - 1]++; 21125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 21225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // If the first digit is now '0' + 10, we would need to set it to '0' and add 21325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // a '1' in front. However we reach the first digit only if all following 21425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // digits had been '9' before rounding up. Now all trailing digits are '0' and 21525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // we simply switch the first digit to '1' and update the decimal-point 21625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // (indicating that the point is now one digit to the right). 21725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (buffer[0] == '0' + 10) { 21825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[0] = '1'; 21925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen (*decimal_point)++; 22025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 22125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} 22225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 22325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 22425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// The given fractionals number represents a fixed-point number with binary 22525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// point at bit (-exponent). 22625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// Preconditions: 22725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// -128 <= exponent <= 0. 22825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// 0 <= fractionals * 2^exponent < 1 22925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// The buffer holds the result. 23025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// The function will round its result. During the rounding-process digits not 23125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// generated by this function might be updated, and the decimal-point variable 23225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// might be updated. If this function generates the digits 99 and the buffer 23325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// already contained "199" (thus yielding a buffer of "19999") then a 23425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// rounding-up will change the contents of the buffer to "20000". 23525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenstatic void FillFractionals(uint64_t fractionals, int exponent, 23625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int fractional_count, Vector<char> buffer, 23725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int* length, int* decimal_point) { 23825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen ASSERT(-128 <= exponent && exponent <= 0); 23925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // 'fractionals' is a fixed-point number, with binary point at bit 24025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // (-exponent). Inside the function the non-converted remainder of fractionals 24125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // is a fixed-point number, with binary point at bit 'point'. 24225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (-exponent <= 64) { 24325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // One 64 bit number is sufficient. 24425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen ASSERT(fractionals >> 56 == 0); 24525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int point = -exponent; 24625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen for (int i = 0; i < fractional_count; ++i) { 24725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (fractionals == 0) break; 24825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Instead of multiplying by 10 we multiply by 5 and adjust the point 24925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // location. This way the fractionals variable will not overflow. 25025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Invariant at the beginning of the loop: fractionals < 2^point. 25125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Initially we have: point <= 64 and fractionals < 2^56 25225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // After each iteration the point is decremented by one. 25325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Note that 5^3 = 125 < 128 = 2^7. 25425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Therefore three iterations of this loop will not overflow fractionals 25525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // (even without the subtraction at the end of the loop body). At this 25625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // time point will satisfy point <= 61 and therefore fractionals < 2^point 25725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // and any further multiplication of fractionals by 5 will not overflow. 25825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen fractionals *= 5; 25925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen point--; 26025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int digit = static_cast<int>(fractionals >> point); 26125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[*length] = '0' + digit; 26225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen (*length)++; 26325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen fractionals -= static_cast<uint64_t>(digit) << point; 26425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 26525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // If the first bit after the point is set we have to round up. 26625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (((fractionals >> (point - 1)) & 1) == 1) { 26725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen RoundUp(buffer, length, decimal_point); 26825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 26925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else { // We need 128 bits. 27025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen ASSERT(64 < -exponent && -exponent <= 128); 27125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen UInt128 fractionals128 = UInt128(fractionals, 0); 27225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen fractionals128.Shift(-exponent - 64); 27325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int point = 128; 27425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen for (int i = 0; i < fractional_count; ++i) { 27525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (fractionals128.IsZero()) break; 27625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // As before: instead of multiplying by 10 we multiply by 5 and adjust the 27725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // point location. 27825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // This multiplication will not overflow for the same reasons as before. 27925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen fractionals128.Multiply(5); 28025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen point--; 28125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int digit = fractionals128.DivModPowerOf2(point); 28225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[*length] = '0' + digit; 28325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen (*length)++; 28425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 28525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (fractionals128.BitAt(point - 1) == 1) { 28625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen RoundUp(buffer, length, decimal_point); 28725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 28825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 28925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} 29025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 29125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 29225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// Removes leading and trailing zeros. 29325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen// If leading zeros are removed then the decimal point position is adjusted. 29425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenstatic void TrimZeros(Vector<char> buffer, int* length, int* decimal_point) { 29525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen while (*length > 0 && buffer[(*length) - 1] == '0') { 29625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen (*length)--; 29725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 29825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int first_non_zero = 0; 29925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen while (first_non_zero < *length && buffer[first_non_zero] == '0') { 30025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen first_non_zero++; 30125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 30225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (first_non_zero != 0) { 30325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen for (int i = first_non_zero; i < *length; ++i) { 30425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[i - first_non_zero] = buffer[i]; 30525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 30625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *length -= first_non_zero; 30725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *decimal_point -= first_non_zero; 30825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 30925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} 31025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 31125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 31225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsenbool FastFixedDtoa(double v, 31325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int fractional_count, 31425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen Vector<char> buffer, 31525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int* length, 31625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int* decimal_point) { 31725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen const uint32_t kMaxUInt32 = 0xFFFFFFFF; 31825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t significand = Double(v).Significand(); 31925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int exponent = Double(v).Exponent(); 32025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // v = significand * 2^exponent (with significand a 53bit integer). 32125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // If the exponent is larger than 20 (i.e. we may have a 73bit number) then we 32225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // don't know how to compute the representation. 2^73 ~= 9.5*10^21. 32325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // If necessary this limit could probably be increased, but we don't need 32425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // more. 32525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (exponent > 20) return false; 32625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (fractional_count > 20) return false; 32725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *length = 0; 32825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // At most kDoubleSignificandSize bits of the significand are non-zero. 32925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Given a 64 bit integer we have 11 0s followed by 53 potentially non-zero 33025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // bits: 0..11*..0xxx..53*..xx 33125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (exponent + kDoubleSignificandSize > 64) { 33225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // The exponent must be > 11. 33325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // 33425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // We know that v = significand * 2^exponent. 33525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // And the exponent > 11. 33625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // We simplify the task by dividing v by 10^17. 33725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // The quotient delivers the first digits, and the remainder fits into a 64 33825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // bit number. 33925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Dividing by 10^17 is equivalent to dividing by 5^17*2^17. 34025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen const uint64_t kFive17 = V8_2PART_UINT64_C(0xB1, A2BC2EC5); // 5^17 34125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t divisor = kFive17; 34225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen int divisor_power = 17; 34325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t dividend = significand; 34425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint32_t quotient; 34525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t remainder; 34625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Let v = f * 2^e with f == significand and e == exponent. 34725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Then need q (quotient) and r (remainder) as follows: 34825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // v = q * 10^17 + r 34925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // f * 2^e = q * 10^17 + r 35025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // f * 2^e = q * 5^17 * 2^17 + r 35125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // If e > 17 then 35225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // f * 2^(e-17) = q * 5^17 + r/2^17 35325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // else 35425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // f = q * 5^17 * 2^(17-e) + r/2^e 35525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (exponent > divisor_power) { 35625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // We only allow exponents of up to 20 and therefore (17 - e) <= 3 35725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen dividend <<= exponent - divisor_power; 35825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen quotient = static_cast<uint32_t>(dividend / divisor); 35925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen remainder = (dividend % divisor) << divisor_power; 36025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else { 36125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen divisor <<= divisor_power - exponent; 36225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen quotient = static_cast<uint32_t>(dividend / divisor); 36325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen remainder = (dividend % divisor) << exponent; 36425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 36525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32(quotient, buffer, length); 36625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits64FixedLength(remainder, divisor_power, buffer, length); 36725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *decimal_point = *length; 36825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else if (exponent >= 0) { 36925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // 0 <= exponent <= 11 37025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen significand <<= exponent; 37125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits64(significand, buffer, length); 37225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *decimal_point = *length; 37325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else if (exponent > -kDoubleSignificandSize) { 37425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // We have to cut the number. 37525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t integrals = significand >> -exponent; 37625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen uint64_t fractionals = significand - (integrals << -exponent); 37725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if (integrals > kMaxUInt32) { 37825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits64(integrals, buffer, length); 37925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else { 38025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillDigits32(static_cast<uint32_t>(integrals), buffer, length); 38125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 38225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *decimal_point = *length; 38325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillFractionals(fractionals, exponent, fractional_count, 38425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer, length, decimal_point); 38525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else if (exponent < -128) { 38625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // This configuration (with at most 20 digits) means that all digits must be 38725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // 0. 38825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen ASSERT(fractional_count <= 20); 38925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[0] = '\0'; 39025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *length = 0; 39125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *decimal_point = -fractional_count; 39225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } else { 39325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *decimal_point = 0; 39425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen FillFractionals(significand, exponent, fractional_count, 39525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer, length, decimal_point); 39625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 39725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen TrimZeros(buffer, length, decimal_point); 39825f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen buffer[*length] = '\0'; 39925f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen if ((*length) == 0) { 40025f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // The string is empty and the decimal_point thus has no importance. Mimick 40125f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen // Gay's dtoa and and set it to -fractional_count. 40225f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen *decimal_point = -fractional_count; 40325f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen } 40425f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen return true; 40525f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} 40625f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen 40725f6136652d8341ed047e7fc1a450af5bd218ea9Kristian Monsen} } // namespace v8::internal 408