00001
00002
00003
00004
00005
00006
00007
00008
00009
00010
00011
00012
00013
00014
00015
00016
00017
00018
00019
00020
00021
00022
00023
00024
00025
00026
00027
00028 #include <cmath>
00029
00030 #include "fixed-dtoa.h"
00031 #include "ieee.h"
00032
00033 namespace double_conversion {
00034
00035
00036
00037 class UInt128 {
00038 public:
00039 UInt128() : high_bits_(0), low_bits_(0) { }
00040 UInt128(uint64_t high, uint64_t low) : high_bits_(high), low_bits_(low) { }
00041
00042 void Multiply(uint32_t multiplicand) {
00043 uint64_t accumulator;
00044
00045 accumulator = (low_bits_ & kMask32) * multiplicand;
00046 uint32_t part = static_cast<uint32_t>(accumulator & kMask32);
00047 accumulator >>= 32;
00048 accumulator = accumulator + (low_bits_ >> 32) * multiplicand;
00049 low_bits_ = (accumulator << 32) + part;
00050 accumulator >>= 32;
00051 accumulator = accumulator + (high_bits_ & kMask32) * multiplicand;
00052 part = static_cast<uint32_t>(accumulator & kMask32);
00053 accumulator >>= 32;
00054 accumulator = accumulator + (high_bits_ >> 32) * multiplicand;
00055 high_bits_ = (accumulator << 32) + part;
00056 ASSERT((accumulator >> 32) == 0);
00057 }
00058
00059 void Shift(int shift_amount) {
00060 ASSERT(-64 <= shift_amount && shift_amount <= 64);
00061 if (shift_amount == 0) {
00062 return;
00063 } else if (shift_amount == -64) {
00064 high_bits_ = low_bits_;
00065 low_bits_ = 0;
00066 } else if (shift_amount == 64) {
00067 low_bits_ = high_bits_;
00068 high_bits_ = 0;
00069 } else if (shift_amount <= 0) {
00070 high_bits_ <<= -shift_amount;
00071 high_bits_ += low_bits_ >> (64 + shift_amount);
00072 low_bits_ <<= -shift_amount;
00073 } else {
00074 low_bits_ >>= shift_amount;
00075 low_bits_ += high_bits_ << (64 - shift_amount);
00076 high_bits_ >>= shift_amount;
00077 }
00078 }
00079
00080
00081
00082 int DivModPowerOf2(int power) {
00083 if (power >= 64) {
00084 int result = static_cast<int>(high_bits_ >> (power - 64));
00085 high_bits_ -= static_cast<uint64_t>(result) << (power - 64);
00086 return result;
00087 } else {
00088 uint64_t part_low = low_bits_ >> power;
00089 uint64_t part_high = high_bits_ << (64 - power);
00090 int result = static_cast<int>(part_low + part_high);
00091 high_bits_ = 0;
00092 low_bits_ -= part_low << power;
00093 return result;
00094 }
00095 }
00096
00097 bool IsZero() const {
00098 return high_bits_ == 0 && low_bits_ == 0;
00099 }
00100
00101 int BitAt(int position) {
00102 if (position >= 64) {
00103 return static_cast<int>(high_bits_ >> (position - 64)) & 1;
00104 } else {
00105 return static_cast<int>(low_bits_ >> position) & 1;
00106 }
00107 }
00108
00109 private:
00110 static const uint64_t kMask32 = 0xFFFFFFFF;
00111
00112 uint64_t high_bits_;
00113 uint64_t low_bits_;
00114 };
00115
00116
00117 static const int kDoubleSignificandSize = 53;
00118
00119
00120 static void FillDigits32FixedLength(uint32_t number, int requested_length,
00121 Vector<char> buffer, int* length) {
00122 for (int i = requested_length - 1; i >= 0; --i) {
00123 buffer[(*length) + i] = '0' + number % 10;
00124 number /= 10;
00125 }
00126 *length += requested_length;
00127 }
00128
00129
00130 static void FillDigits32(uint32_t number, Vector<char> buffer, int* length) {
00131 int number_length = 0;
00132
00133 while (number != 0) {
00134 int digit = number % 10;
00135 number /= 10;
00136 buffer[(*length) + number_length] = '0' + digit;
00137 number_length++;
00138 }
00139
00140 int i = *length;
00141 int j = *length + number_length - 1;
00142 while (i < j) {
00143 char tmp = buffer[i];
00144 buffer[i] = buffer[j];
00145 buffer[j] = tmp;
00146 i++;
00147 j--;
00148 }
00149 *length += number_length;
00150 }
00151
00152
00153 static void FillDigits64FixedLength(uint64_t number, int requested_length,
00154 Vector<char> buffer, int* length) {
00155 const uint32_t kTen7 = 10000000;
00156
00157 uint32_t part2 = static_cast<uint32_t>(number % kTen7);
00158 number /= kTen7;
00159 uint32_t part1 = static_cast<uint32_t>(number % kTen7);
00160 uint32_t part0 = static_cast<uint32_t>(number / kTen7);
00161
00162 FillDigits32FixedLength(part0, 3, buffer, length);
00163 FillDigits32FixedLength(part1, 7, buffer, length);
00164 FillDigits32FixedLength(part2, 7, buffer, length);
00165 }
00166
00167
00168 static void FillDigits64(uint64_t number, Vector<char> buffer, int* length) {
00169 const uint32_t kTen7 = 10000000;
00170
00171 uint32_t part2 = static_cast<uint32_t>(number % kTen7);
00172 number /= kTen7;
00173 uint32_t part1 = static_cast<uint32_t>(number % kTen7);
00174 uint32_t part0 = static_cast<uint32_t>(number / kTen7);
00175
00176 if (part0 != 0) {
00177 FillDigits32(part0, buffer, length);
00178 FillDigits32FixedLength(part1, 7, buffer, length);
00179 FillDigits32FixedLength(part2, 7, buffer, length);
00180 } else if (part1 != 0) {
00181 FillDigits32(part1, buffer, length);
00182 FillDigits32FixedLength(part2, 7, buffer, length);
00183 } else {
00184 FillDigits32(part2, buffer, length);
00185 }
00186 }
00187
00188
00189 static void RoundUp(Vector<char> buffer, int* length, int* decimal_point) {
00190
00191 if (*length == 0) {
00192 buffer[0] = '1';
00193 *decimal_point = 1;
00194 *length = 1;
00195 return;
00196 }
00197
00198
00199 buffer[(*length) - 1]++;
00200 for (int i = (*length) - 1; i > 0; --i) {
00201 if (buffer[i] != '0' + 10) {
00202 return;
00203 }
00204 buffer[i] = '0';
00205 buffer[i - 1]++;
00206 }
00207
00208
00209
00210
00211
00212 if (buffer[0] == '0' + 10) {
00213 buffer[0] = '1';
00214 (*decimal_point)++;
00215 }
00216 }
00217
00218
00219
00220
00221
00222
00223
00224
00225
00226
00227
00228
00229
00230 static void FillFractionals(uint64_t fractionals, int exponent,
00231 int fractional_count, Vector<char> buffer,
00232 int* length, int* decimal_point) {
00233 ASSERT(-128 <= exponent && exponent <= 0);
00234
00235
00236
00237 if (-exponent <= 64) {
00238
00239 ASSERT(fractionals >> 56 == 0);
00240 int point = -exponent;
00241 for (int i = 0; i < fractional_count; ++i) {
00242 if (fractionals == 0) break;
00243
00244
00245
00246
00247
00248
00249
00250
00251
00252
00253 fractionals *= 5;
00254 point--;
00255 int digit = static_cast<int>(fractionals >> point);
00256 buffer[*length] = '0' + digit;
00257 (*length)++;
00258 fractionals -= static_cast<uint64_t>(digit) << point;
00259 }
00260
00261 if (((fractionals >> (point - 1)) & 1) == 1) {
00262 RoundUp(buffer, length, decimal_point);
00263 }
00264 } else {
00265 ASSERT(64 < -exponent && -exponent <= 128);
00266 UInt128 fractionals128 = UInt128(fractionals, 0);
00267 fractionals128.Shift(-exponent - 64);
00268 int point = 128;
00269 for (int i = 0; i < fractional_count; ++i) {
00270 if (fractionals128.IsZero()) break;
00271
00272
00273
00274 fractionals128.Multiply(5);
00275 point--;
00276 int digit = fractionals128.DivModPowerOf2(point);
00277 buffer[*length] = '0' + digit;
00278 (*length)++;
00279 }
00280 if (fractionals128.BitAt(point - 1) == 1) {
00281 RoundUp(buffer, length, decimal_point);
00282 }
00283 }
00284 }
00285
00286
00287
00288
00289 static void TrimZeros(Vector<char> buffer, int* length, int* decimal_point) {
00290 while (*length > 0 && buffer[(*length) - 1] == '0') {
00291 (*length)--;
00292 }
00293 int first_non_zero = 0;
00294 while (first_non_zero < *length && buffer[first_non_zero] == '0') {
00295 first_non_zero++;
00296 }
00297 if (first_non_zero != 0) {
00298 for (int i = first_non_zero; i < *length; ++i) {
00299 buffer[i - first_non_zero] = buffer[i];
00300 }
00301 *length -= first_non_zero;
00302 *decimal_point -= first_non_zero;
00303 }
00304 }
00305
00306
00307 bool FastFixedDtoa(double v,
00308 int fractional_count,
00309 Vector<char> buffer,
00310 int* length,
00311 int* decimal_point) {
00312 const uint32_t kMaxUInt32 = 0xFFFFFFFF;
00313 uint64_t significand = Double(v).Significand();
00314 int exponent = Double(v).Exponent();
00315
00316
00317
00318
00319
00320 if (exponent > 20) return false;
00321 if (fractional_count > 20) return false;
00322 *length = 0;
00323
00324
00325
00326 if (exponent + kDoubleSignificandSize > 64) {
00327
00328
00329
00330
00331
00332
00333
00334
00335 const uint64_t kFive17 = UINT64_2PART_C(0xB1, A2BC2EC5);
00336 uint64_t divisor = kFive17;
00337 int divisor_power = 17;
00338 uint64_t dividend = significand;
00339 uint32_t quotient;
00340 uint64_t remainder;
00341
00342
00343
00344
00345
00346
00347
00348
00349
00350 if (exponent > divisor_power) {
00351
00352 dividend <<= exponent - divisor_power;
00353 quotient = static_cast<uint32_t>(dividend / divisor);
00354 remainder = (dividend % divisor) << divisor_power;
00355 } else {
00356 divisor <<= divisor_power - exponent;
00357 quotient = static_cast<uint32_t>(dividend / divisor);
00358 remainder = (dividend % divisor) << exponent;
00359 }
00360 FillDigits32(quotient, buffer, length);
00361 FillDigits64FixedLength(remainder, divisor_power, buffer, length);
00362 *decimal_point = *length;
00363 } else if (exponent >= 0) {
00364
00365 significand <<= exponent;
00366 FillDigits64(significand, buffer, length);
00367 *decimal_point = *length;
00368 } else if (exponent > -kDoubleSignificandSize) {
00369
00370 uint64_t integrals = significand >> -exponent;
00371 uint64_t fractionals = significand - (integrals << -exponent);
00372 if (integrals > kMaxUInt32) {
00373 FillDigits64(integrals, buffer, length);
00374 } else {
00375 FillDigits32(static_cast<uint32_t>(integrals), buffer, length);
00376 }
00377 *decimal_point = *length;
00378 FillFractionals(fractionals, exponent, fractional_count,
00379 buffer, length, decimal_point);
00380 } else if (exponent < -128) {
00381
00382
00383 ASSERT(fractional_count <= 20);
00384 buffer[0] = '\0';
00385 *length = 0;
00386 *decimal_point = -fractional_count;
00387 } else {
00388 *decimal_point = 0;
00389 FillFractionals(significand, exponent, fractional_count,
00390 buffer, length, decimal_point);
00391 }
00392 TrimZeros(buffer, length, decimal_point);
00393 buffer[*length] = '\0';
00394 if ((*length) == 0) {
00395
00396
00397 *decimal_point = -fractional_count;
00398 }
00399 return true;
00400 }
00401
00402 }