1// Copyright 2010 the V8 project authors. All rights reserved.
2// Redistribution and use in source and binary forms, with or without
3// modification, are permitted provided that the following conditions are
4// met:
5//
6// * Redistributions of source code must retain the above copyright
7// notice, this list of conditions and the following disclaimer.
8// * Redistributions in binary form must reproduce the above
9// copyright notice, this list of conditions and the following
10// disclaimer in the documentation and/or other materials provided
11// with the distribution.
12// * Neither the name of Google Inc. nor the names of its
13// contributors may be used to endorse or promote products derived
14// from this software without specific prior written permission.
15//
16// THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
17// "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
18// LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
19// A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
20// OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
21// SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
22// LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
23// DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
24// THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
25// (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
26// OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
27
28#include "config.h"
29
30#include <cmath>
31
32#include <wtf/dtoa/bignum-dtoa.h>
33
34#include <wtf/dtoa/bignum.h>
35#include <wtf/dtoa/ieee.h>
36
37namespace WTF {
38namespace double_conversion {
39
40static int NormalizedExponent(uint64_t significand, int exponent) {
41 ASSERT(significand != 0);
42 while ((significand & Double::kHiddenBit) == 0) {
43 significand = significand << 1;
44 exponent = exponent - 1;
45 }
46 return exponent;
47}
48
49
50// Forward declarations:
51// Returns an estimation of k such that 10^(k-1) <= v < 10^k.
52static int EstimatePower(int exponent);
53// Computes v / 10^estimated_power exactly, as a ratio of two bignums, numerator
54// and denominator.
55static void InitialScaledStartValues(uint64_t significand,
56 int exponent,
57 bool lower_boundary_is_closer,
58 int estimated_power,
59 bool need_boundary_deltas,
60 Bignum* numerator,
61 Bignum* denominator,
62 Bignum* delta_minus,
63 Bignum* delta_plus);
64// Multiplies numerator/denominator so that its values lies in the range 1-10.
65// Returns decimal_point s.t.
66// v = numerator'/denominator' * 10^(decimal_point-1)
67// where numerator' and denominator' are the values of numerator and
68// denominator after the call to this function.
69static void FixupMultiply10(int estimated_power, bool is_even,
70 int* decimal_point,
71 Bignum* numerator, Bignum* denominator,
72 Bignum* delta_minus, Bignum* delta_plus);
73// Generates digits from the left to the right and stops when the generated
74// digits yield the shortest decimal representation of v.
75static void GenerateShortestDigits(Bignum* numerator, Bignum* denominator,
76 Bignum* delta_minus, Bignum* delta_plus,
77 bool is_even,
78 BufferReference<char> buffer, int* length);
79// Generates 'requested_digits' after the decimal point.
80static void BignumToFixed(int requested_digits, int* decimal_point,
81 Bignum* numerator, Bignum* denominator,
82 BufferReference<char>(buffer), int* length);
83// Generates 'count' digits of numerator/denominator.
84// Once 'count' digits have been produced rounds the result depending on the
85// remainder (remainders of exactly .5 round upwards). Might update the
86// decimal_point when rounding up (for example for 0.9999).
87static void GenerateCountedDigits(int count, int* decimal_point,
88 Bignum* numerator, Bignum* denominator,
89 BufferReference<char>(buffer), int* length);
90
91
92void BignumDtoa(double v, BignumDtoaMode mode, int requested_digits,
93 BufferReference<char> buffer, int* length, int* decimal_point) {
94 ASSERT(v > 0);
95 ASSERT(!Double(v).IsSpecial());
96 uint64_t significand;
97 int exponent;
98 bool lower_boundary_is_closer;
99 if (mode == BIGNUM_DTOA_SHORTEST_SINGLE) {
100 float f = static_cast<float>(v);
101 ASSERT(f == v);
102 significand = Single(f).Significand();
103 exponent = Single(f).Exponent();
104 lower_boundary_is_closer = Single(f).LowerBoundaryIsCloser();
105 } else {
106 significand = Double(v).Significand();
107 exponent = Double(v).Exponent();
108 lower_boundary_is_closer = Double(v).LowerBoundaryIsCloser();
109 }
110 bool need_boundary_deltas =
111 (mode == BIGNUM_DTOA_SHORTEST || mode == BIGNUM_DTOA_SHORTEST_SINGLE);
112
113 bool is_even = (significand & 1) == 0;
114 int normalized_exponent = NormalizedExponent(significand, exponent);
115 // estimated_power might be too low by 1.
116 int estimated_power = EstimatePower(normalized_exponent);
117
118 // Shortcut for Fixed.
119 // The requested digits correspond to the digits after the point. If the
120 // number is much too small, then there is no need in trying to get any
121 // digits.
122 if (mode == BIGNUM_DTOA_FIXED && -estimated_power - 1 > requested_digits) {
123 buffer[0] = '\0';
124 *length = 0;
125 // Set decimal-point to -requested_digits. This is what Gay does.
126 // Note that it should not have any effect anyways since the string is
127 // empty.
128 *decimal_point = -requested_digits;
129 return;
130 }
131
132 Bignum numerator;
133 Bignum denominator;
134 Bignum delta_minus;
135 Bignum delta_plus;
136 // Make sure the bignum can grow large enough. The smallest double equals
137 // 4e-324. In this case the denominator needs fewer than 324*4 binary digits.
138 // The maximum double is 1.7976931348623157e308 which needs fewer than
139 // 308*4 binary digits.
140 ASSERT(Bignum::kMaxSignificantBits >= 324*4);
141 InitialScaledStartValues(significand, exponent, lower_boundary_is_closer,
142 estimated_power, need_boundary_deltas,
143 &numerator, &denominator,
144 &delta_minus, &delta_plus);
145 // We now have v = (numerator / denominator) * 10^estimated_power.
146 FixupMultiply10(estimated_power, is_even, decimal_point,
147 &numerator, &denominator,
148 &delta_minus, &delta_plus);
149 // We now have v = (numerator / denominator) * 10^(decimal_point-1), and
150 // 1 <= (numerator + delta_plus) / denominator < 10
151 switch (mode) {
152 case BIGNUM_DTOA_SHORTEST:
153 case BIGNUM_DTOA_SHORTEST_SINGLE:
154 GenerateShortestDigits(&numerator, &denominator,
155 &delta_minus, &delta_plus,
156 is_even, buffer, length);
157 break;
158 case BIGNUM_DTOA_FIXED:
159 BignumToFixed(requested_digits, decimal_point,
160 &numerator, &denominator,
161 buffer, length);
162 break;
163 case BIGNUM_DTOA_PRECISION:
164 GenerateCountedDigits(requested_digits, decimal_point,
165 &numerator, &denominator,
166 buffer, length);
167 break;
168 default:
169 UNREACHABLE();
170 }
171 buffer[*length] = '\0';
172}
173
174
175// The procedure starts generating digits from the left to the right and stops
176// when the generated digits yield the shortest decimal representation of v. A
177// decimal representation of v is a number lying closer to v than to any other
178// double, so it converts to v when read.
179//
180// This is true if d, the decimal representation, is between m- and m+, the
181// upper and lower boundaries. d must be strictly between them if !is_even.
182// m- := (numerator - delta_minus) / denominator
183// m+ := (numerator + delta_plus) / denominator
184//
185// Precondition: 0 <= (numerator+delta_plus) / denominator < 10.
186// If 1 <= (numerator+delta_plus) / denominator < 10 then no leading 0 digit
187// will be produced. This should be the standard precondition.
188static void GenerateShortestDigits(Bignum* numerator, Bignum* denominator,
189 Bignum* delta_minus, Bignum* delta_plus,
190 bool is_even,
191 BufferReference<char> buffer, int* length) {
192 // Small optimization: if delta_minus and delta_plus are the same just reuse
193 // one of the two bignums.
194 if (Bignum::Equal(*delta_minus, *delta_plus)) {
195 delta_plus = delta_minus;
196 }
197 *length = 0;
198 for (;;) {
199 uint16_t digit;
200 digit = numerator->DivideModuloIntBignum(*denominator);
201 ASSERT(digit <= 9); // digit is a uint16_t and therefore always positive.
202 // digit = numerator / denominator (integer division).
203 // numerator = numerator % denominator.
204 buffer[(*length)++] = static_cast<char>(digit + '0');
205
206 // Can we stop already?
207 // If the remainder of the division is less than the distance to the lower
208 // boundary we can stop. In this case we simply round down (discarding the
209 // remainder).
210 // Similarly we test if we can round up (using the upper boundary).
211 bool in_delta_room_minus;
212 bool in_delta_room_plus;
213 if (is_even) {
214 in_delta_room_minus = Bignum::LessEqual(*numerator, *delta_minus);
215 } else {
216 in_delta_room_minus = Bignum::Less(*numerator, *delta_minus);
217 }
218 if (is_even) {
219 in_delta_room_plus =
220 Bignum::PlusCompare(*numerator, *delta_plus, *denominator) >= 0;
221 } else {
222 in_delta_room_plus =
223 Bignum::PlusCompare(*numerator, *delta_plus, *denominator) > 0;
224 }
225 if (!in_delta_room_minus && !in_delta_room_plus) {
226 // Prepare for next iteration.
227 numerator->Times10();
228 delta_minus->Times10();
229 // We optimized delta_plus to be equal to delta_minus (if they share the
230 // same value). So don't multiply delta_plus if they point to the same
231 // object.
232 if (delta_minus != delta_plus) {
233 delta_plus->Times10();
234 }
235 } else if (in_delta_room_minus && in_delta_room_plus) {
236 // Let's see if 2*numerator < denominator.
237 // If yes, then the next digit would be < 5 and we can round down.
238 int compare = Bignum::PlusCompare(*numerator, *numerator, *denominator);
239 if (compare < 0) {
240 // Remaining digits are less than .5. -> Round down (== do nothing).
241 } else if (compare > 0) {
242 // Remaining digits are more than .5 of denominator. -> Round up.
243 // Note that the last digit could not be a '9' as otherwise the whole
244 // loop would have stopped earlier.
245 // We still have an assert here in case the preconditions were not
246 // satisfied.
247 ASSERT(buffer[(*length) - 1] != '9');
248 buffer[(*length) - 1]++;
249 } else {
250 // Halfway case.
251 // TODO(floitsch): need a way to solve half-way cases.
252 // For now let's round towards even (since this is what Gay seems to
253 // do).
254
255 if ((buffer[(*length) - 1] - '0') % 2 == 0) {
256 // Round down => Do nothing.
257 } else {
258 ASSERT(buffer[(*length) - 1] != '9');
259 buffer[(*length) - 1]++;
260 }
261 }
262 return;
263 } else if (in_delta_room_minus) {
264 // Round down (== do nothing).
265 return;
266 } else { // in_delta_room_plus
267 // Round up.
268 // Note again that the last digit could not be '9' since this would have
269 // stopped the loop earlier.
270 // We still have an ASSERT here, in case the preconditions were not
271 // satisfied.
272 ASSERT(buffer[(*length) -1] != '9');
273 buffer[(*length) - 1]++;
274 return;
275 }
276 }
277}
278
279
280// Let v = numerator / denominator < 10.
281// Then we generate 'count' digits of d = x.xxxxx... (without the decimal point)
282// from left to right. Once 'count' digits have been produced we decide wether
283// to round up or down. Remainders of exactly .5 round upwards. Numbers such
284// as 9.999999 propagate a carry all the way, and change the
285// exponent (decimal_point), when rounding upwards.
286static void GenerateCountedDigits(int count, int* decimal_point,
287 Bignum* numerator, Bignum* denominator,
288 BufferReference<char> buffer, int* length) {
289 ASSERT(count >= 0);
290 for (int i = 0; i < count - 1; ++i) {
291 uint16_t digit;
292 digit = numerator->DivideModuloIntBignum(*denominator);
293 ASSERT(digit <= 9); // digit is a uint16_t and therefore always positive.
294 // digit = numerator / denominator (integer division).
295 // numerator = numerator % denominator.
296 buffer[i] = static_cast<char>(digit + '0');
297 // Prepare for next iteration.
298 numerator->Times10();
299 }
300 // Generate the last digit.
301 uint16_t digit;
302 digit = numerator->DivideModuloIntBignum(*denominator);
303 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) {
304 digit++;
305 }
306 ASSERT(digit <= 10);
307 buffer[count - 1] = static_cast<char>(digit + '0');
308 // Correct bad digits (in case we had a sequence of '9's). Propagate the
309 // carry until we hat a non-'9' or til we reach the first digit.
310 for (int i = count - 1; i > 0; --i) {
311 if (buffer[i] != '0' + 10) break;
312 buffer[i] = '0';
313 buffer[i - 1]++;
314 }
315 if (buffer[0] == '0' + 10) {
316 // Propagate a carry past the top place.
317 buffer[0] = '1';
318 (*decimal_point)++;
319 }
320 *length = count;
321}
322
323
324// Generates 'requested_digits' after the decimal point. It might omit
325// trailing '0's. If the input number is too small then no digits at all are
326// generated (ex.: 2 fixed digits for 0.00001).
327//
328// Input verifies: 1 <= (numerator + delta) / denominator < 10.
329static void BignumToFixed(int requested_digits, int* decimal_point,
330 Bignum* numerator, Bignum* denominator,
331 BufferReference<char>(buffer), int* length) {
332 // Note that we have to look at more than just the requested_digits, since
333 // a number could be rounded up. Example: v=0.5 with requested_digits=0.
334 // Even though the power of v equals 0 we can't just stop here.
335 if (-(*decimal_point) > requested_digits) {
336 // The number is definitively too small.
337 // Ex: 0.001 with requested_digits == 1.
338 // Set decimal-point to -requested_digits. This is what Gay does.
339 // Note that it should not have any effect anyways since the string is
340 // empty.
341 *decimal_point = -requested_digits;
342 *length = 0;
343 return;
344 } else if (-(*decimal_point) == requested_digits) {
345 // We only need to verify if the number rounds down or up.
346 // Ex: 0.04 and 0.06 with requested_digits == 1.
347 ASSERT(*decimal_point == -requested_digits);
348 // Initially the fraction lies in range (1, 10]. Multiply the denominator
349 // by 10 so that we can compare more easily.
350 denominator->Times10();
351 if (Bignum::PlusCompare(*numerator, *numerator, *denominator) >= 0) {
352 // If the fraction is >= 0.5 then we have to include the rounded
353 // digit.
354 buffer[0] = '1';
355 *length = 1;
356 (*decimal_point)++;
357 } else {
358 // Note that we caught most of similar cases earlier.
359 *length = 0;
360 }
361 return;
362 } else {
363 // The requested digits correspond to the digits after the point.
364 // The variable 'needed_digits' includes the digits before the point.
365 int needed_digits = (*decimal_point) + requested_digits;
366 GenerateCountedDigits(needed_digits, decimal_point,
367 numerator, denominator,
368 buffer, length);
369 }
370}
371
372
373// Returns an estimation of k such that 10^(k-1) <= v < 10^k where
374// v = f * 2^exponent and 2^52 <= f < 2^53.
375// v is hence a normalized double with the given exponent. The output is an
376// approximation for the exponent of the decimal approimation .digits * 10^k.
377//
378// The result might undershoot by 1 in which case 10^k <= v < 10^k+1.
379// Note: this property holds for v's upper boundary m+ too.
380// 10^k <= m+ < 10^k+1.
381// (see explanation below).
382//
383// Examples:
384// EstimatePower(0) => 16
385// EstimatePower(-52) => 0
386//
387// Note: e >= 0 => EstimatedPower(e) > 0. No similar claim can be made for e<0.
388static int EstimatePower(int exponent) {
389 // This function estimates log10 of v where v = f*2^e (with e == exponent).
390 // Note that 10^floor(log10(v)) <= v, but v <= 10^ceil(log10(v)).
391 // Note that f is bounded by its container size. Let p = 53 (the double's
392 // significand size). Then 2^(p-1) <= f < 2^p.
393 //
394 // Given that log10(v) == log2(v)/log2(10) and e+(len(f)-1) is quite close
395 // to log2(v) the function is simplified to (e+(len(f)-1)/log2(10)).
396 // The computed number undershoots by less than 0.631 (when we compute log3
397 // and not log10).
398 //
399 // Optimization: since we only need an approximated result this computation
400 // can be performed on 64 bit integers. On x86/x64 architecture the speedup is
401 // not really measurable, though.
402 //
403 // Since we want to avoid overshooting we decrement by 1e10 so that
404 // floating-point imprecisions don't affect us.
405 //
406 // Explanation for v's boundary m+: the computation takes advantage of
407 // the fact that 2^(p-1) <= f < 2^p. Boundaries still satisfy this requirement
408 // (even for denormals where the delta can be much more important).
409
410 const double k1Log10 = 0.30102999566398114; // 1/lg(10)
411
412 // For doubles len(f) == 53 (don't forget the hidden bit).
413 const int kSignificandSize = Double::kSignificandSize;
414 double estimate = ceil((exponent + kSignificandSize - 1) * k1Log10 - 1e-10);
415 return static_cast<int>(estimate);
416}
417
418
419// See comments for InitialScaledStartValues.
420static void InitialScaledStartValuesPositiveExponent(
421 uint64_t significand, int exponent,
422 int estimated_power, bool need_boundary_deltas,
423 Bignum* numerator, Bignum* denominator,
424 Bignum* delta_minus, Bignum* delta_plus) {
425 // A positive exponent implies a positive power.
426 ASSERT(estimated_power >= 0);
427 // Since the estimated_power is positive we simply multiply the denominator
428 // by 10^estimated_power.
429
430 // numerator = v.
431 numerator->AssignUInt64(significand);
432 numerator->ShiftLeft(exponent);
433 // denominator = 10^estimated_power.
434 denominator->AssignPowerUInt16(10, estimated_power);
435
436 if (need_boundary_deltas) {
437 // Introduce a common denominator so that the deltas to the boundaries are
438 // integers.
439 denominator->ShiftLeft(1);
440 numerator->ShiftLeft(1);
441 // Let v = f * 2^e, then m+ - v = 1/2 * 2^e; With the common
442 // denominator (of 2) delta_plus equals 2^e.
443 delta_plus->AssignUInt16(1);
444 delta_plus->ShiftLeft(exponent);
445 // Same for delta_minus. The adjustments if f == 2^p-1 are done later.
446 delta_minus->AssignUInt16(1);
447 delta_minus->ShiftLeft(exponent);
448 }
449}
450
451
452// See comments for InitialScaledStartValues
453static void InitialScaledStartValuesNegativeExponentPositivePower(
454 uint64_t significand, int exponent,
455 int estimated_power, bool need_boundary_deltas,
456 Bignum* numerator, Bignum* denominator,
457 Bignum* delta_minus, Bignum* delta_plus) {
458 // v = f * 2^e with e < 0, and with estimated_power >= 0.
459 // This means that e is close to 0 (have a look at how estimated_power is
460 // computed).
461
462 // numerator = significand
463 // since v = significand * 2^exponent this is equivalent to
464 // numerator = v * / 2^-exponent
465 numerator->AssignUInt64(significand);
466 // denominator = 10^estimated_power * 2^-exponent (with exponent < 0)
467 denominator->AssignPowerUInt16(10, estimated_power);
468 denominator->ShiftLeft(-exponent);
469
470 if (need_boundary_deltas) {
471 // Introduce a common denominator so that the deltas to the boundaries are
472 // integers.
473 denominator->ShiftLeft(1);
474 numerator->ShiftLeft(1);
475 // Let v = f * 2^e, then m+ - v = 1/2 * 2^e; With the common
476 // denominator (of 2) delta_plus equals 2^e.
477 // Given that the denominator already includes v's exponent the distance
478 // to the boundaries is simply 1.
479 delta_plus->AssignUInt16(1);
480 // Same for delta_minus. The adjustments if f == 2^p-1 are done later.
481 delta_minus->AssignUInt16(1);
482 }
483}
484
485
486// See comments for InitialScaledStartValues
487static void InitialScaledStartValuesNegativeExponentNegativePower(
488 uint64_t significand, int exponent,
489 int estimated_power, bool need_boundary_deltas,
490 Bignum* numerator, Bignum* denominator,
491 Bignum* delta_minus, Bignum* delta_plus) {
492 // Instead of multiplying the denominator with 10^estimated_power we
493 // multiply all values (numerator and deltas) by 10^-estimated_power.
494
495 // Use numerator as temporary container for power_ten.
496 Bignum* power_ten = numerator;
497 power_ten->AssignPowerUInt16(10, -estimated_power);
498
499 if (need_boundary_deltas) {
500 // Since power_ten == numerator we must make a copy of 10^estimated_power
501 // before we complete the computation of the numerator.
502 // delta_plus = delta_minus = 10^estimated_power
503 delta_plus->AssignBignum(*power_ten);
504 delta_minus->AssignBignum(*power_ten);
505 }
506
507 // numerator = significand * 2 * 10^-estimated_power
508 // since v = significand * 2^exponent this is equivalent to
509 // numerator = v * 10^-estimated_power * 2 * 2^-exponent.
510 // Remember: numerator has been abused as power_ten. So no need to assign it
511 // to itself.
512 ASSERT(numerator == power_ten);
513 numerator->MultiplyByUInt64(significand);
514
515 // denominator = 2 * 2^-exponent with exponent < 0.
516 denominator->AssignUInt16(1);
517 denominator->ShiftLeft(-exponent);
518
519 if (need_boundary_deltas) {
520 // Introduce a common denominator so that the deltas to the boundaries are
521 // integers.
522 numerator->ShiftLeft(1);
523 denominator->ShiftLeft(1);
524 // With this shift the boundaries have their correct value, since
525 // delta_plus = 10^-estimated_power, and
526 // delta_minus = 10^-estimated_power.
527 // These assignments have been done earlier.
528 // The adjustments if f == 2^p-1 (lower boundary is closer) are done later.
529 }
530}
531
532
533// Let v = significand * 2^exponent.
534// Computes v / 10^estimated_power exactly, as a ratio of two bignums, numerator
535// and denominator. The functions GenerateShortestDigits and
536// GenerateCountedDigits will then convert this ratio to its decimal
537// representation d, with the required accuracy.
538// Then d * 10^estimated_power is the representation of v.
539// (Note: the fraction and the estimated_power might get adjusted before
540// generating the decimal representation.)
541//
542// The initial start values consist of:
543// - a scaled numerator: s.t. numerator/denominator == v / 10^estimated_power.
544// - a scaled (common) denominator.
545// optionally (used by GenerateShortestDigits to decide if it has the shortest
546// decimal converting back to v):
547// - v - m-: the distance to the lower boundary.
548// - m+ - v: the distance to the upper boundary.
549//
550// v, m+, m-, and therefore v - m- and m+ - v all share the same denominator.
551//
552// Let ep == estimated_power, then the returned values will satisfy:
553// v / 10^ep = numerator / denominator.
554// v's boundarys m- and m+:
555// m- / 10^ep == v / 10^ep - delta_minus / denominator
556// m+ / 10^ep == v / 10^ep + delta_plus / denominator
557// Or in other words:
558// m- == v - delta_minus * 10^ep / denominator;
559// m+ == v + delta_plus * 10^ep / denominator;
560//
561// Since 10^(k-1) <= v < 10^k (with k == estimated_power)
562// or 10^k <= v < 10^(k+1)
563// we then have 0.1 <= numerator/denominator < 1
564// or 1 <= numerator/denominator < 10
565//
566// It is then easy to kickstart the digit-generation routine.
567//
568// The boundary-deltas are only filled if the mode equals BIGNUM_DTOA_SHORTEST
569// or BIGNUM_DTOA_SHORTEST_SINGLE.
570
571static void InitialScaledStartValues(uint64_t significand,
572 int exponent,
573 bool lower_boundary_is_closer,
574 int estimated_power,
575 bool need_boundary_deltas,
576 Bignum* numerator,
577 Bignum* denominator,
578 Bignum* delta_minus,
579 Bignum* delta_plus) {
580 if (exponent >= 0) {
581 InitialScaledStartValuesPositiveExponent(
582 significand, exponent, estimated_power, need_boundary_deltas,
583 numerator, denominator, delta_minus, delta_plus);
584 } else if (estimated_power >= 0) {
585 InitialScaledStartValuesNegativeExponentPositivePower(
586 significand, exponent, estimated_power, need_boundary_deltas,
587 numerator, denominator, delta_minus, delta_plus);
588 } else {
589 InitialScaledStartValuesNegativeExponentNegativePower(
590 significand, exponent, estimated_power, need_boundary_deltas,
591 numerator, denominator, delta_minus, delta_plus);
592 }
593
594 if (need_boundary_deltas && lower_boundary_is_closer) {
595 // The lower boundary is closer at half the distance of "normal" numbers.
596 // Increase the common denominator and adapt all but the delta_minus.
597 denominator->ShiftLeft(1); // *2
598 numerator->ShiftLeft(1); // *2
599 delta_plus->ShiftLeft(1); // *2
600 }
601}
602
603
604// This routine multiplies numerator/denominator so that its values lies in the
605// range 1-10. That is after a call to this function we have:
606// 1 <= (numerator + delta_plus) /denominator < 10.
607// Let numerator the input before modification and numerator' the argument
608// after modification, then the output-parameter decimal_point is such that
609// numerator / denominator * 10^estimated_power ==
610// numerator' / denominator' * 10^(decimal_point - 1)
611// In some cases estimated_power was too low, and this is already the case. We
612// then simply adjust the power so that 10^(k-1) <= v < 10^k (with k ==
613// estimated_power) but do not touch the numerator or denominator.
614// Otherwise the routine multiplies the numerator and the deltas by 10.
615static void FixupMultiply10(int estimated_power, bool is_even,
616 int* decimal_point,
617 Bignum* numerator, Bignum* denominator,
618 Bignum* delta_minus, Bignum* delta_plus) {
619 bool in_range;
620 if (is_even) {
621 // For IEEE doubles half-way cases (in decimal system numbers ending with 5)
622 // are rounded to the closest floating-point number with even significand.
623 in_range = Bignum::PlusCompare(*numerator, *delta_plus, *denominator) >= 0;
624 } else {
625 in_range = Bignum::PlusCompare(*numerator, *delta_plus, *denominator) > 0;
626 }
627 if (in_range) {
628 // Since numerator + delta_plus >= denominator we already have
629 // 1 <= numerator/denominator < 10. Simply update the estimated_power.
630 *decimal_point = estimated_power + 1;
631 } else {
632 *decimal_point = estimated_power;
633 numerator->Times10();
634 if (Bignum::Equal(*delta_minus, *delta_plus)) {
635 delta_minus->Times10();
636 delta_plus->AssignBignum(*delta_minus);
637 } else {
638 delta_minus->Times10();
639 delta_plus->Times10();
640 }
641 }
642}
643
644} // namespace double_conversion
645} // namespace WTF
646