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