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