1 /*
2 * Copyright (c) 2015, Oracle and/or its affiliates. All rights reserved.
3 * DO NOT ALTER OR REMOVE COPYRIGHT NOTICES OR THIS FILE HEADER.
4 *
5 * This code is free software; you can redistribute it and/or modify it
6 * under the terms of the GNU General Public License version 2 only, as
7 * published by the Free Software Foundation. Oracle designates this
8 * particular file as subject to the "Classpath" exception as provided
9 * by Oracle in the LICENSE file that accompanied this code.
10 *
11 * This code is distributed in the hope that it will be useful, but WITHOUT
12 * ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or
13 * FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License
14 * version 2 for more details (a copy is included in the LICENSE file that
15 * accompanied this code).
16 *
17 * You should have received a copy of the GNU General Public License version
18 * 2 along with this work; if not, write to the Free Software Foundation,
19 * Inc., 51 Franklin St, Fifth Floor, Boston, MA 02110-1301 USA.
20 *
21 * Please contact Oracle, 500 Oracle Parkway, Redwood Shores, CA 94065 USA
22 * or visit www.oracle.com if you need additional information or have any
23 * questions.
24 */
25
26 // This file is available under and governed by the GNU General Public
27 // License version 2 only, as published by the Free Software Foundation.
28 // However, the following notice accompanied the original version of this
29 // file:
30 //
31 // Copyright 2010 the V8 project authors. All rights reserved.
32 // Redistribution and use in source and binary forms, with or without
33 // modification, are permitted provided that the following conditions are
34 // met:
35 //
36 // * Redistributions of source code must retain the above copyright
37 // notice, this list of conditions and the following disclaimer.
38 // * Redistributions in binary form must reproduce the above
39 // copyright notice, this list of conditions and the following
40 // disclaimer in the documentation and/or other materials provided
41 // with the distribution.
42 // * Neither the name of Google Inc. nor the names of its
43 // contributors may be used to endorse or promote products derived
44 // from this software without specific prior written permission.
45 //
46 // THIS SOFTWARE IS PROVIDED BY THE COPYRIGHT HOLDERS AND CONTRIBUTORS
47 // "AS IS" AND ANY EXPRESS OR IMPLIED WARRANTIES, INCLUDING, BUT NOT
48 // LIMITED TO, THE IMPLIED WARRANTIES OF MERCHANTABILITY AND FITNESS FOR
49 // A PARTICULAR PURPOSE ARE DISCLAIMED. IN NO EVENT SHALL THE COPYRIGHT
50 // OWNER OR CONTRIBUTORS BE LIABLE FOR ANY DIRECT, INDIRECT, INCIDENTAL,
51 // SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT NOT
52 // LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE,
53 // DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY
54 // THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT
55 // (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE
56 // OF THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE.
57
58 package jdk.nashorn.internal.runtime.doubleconv;
59
60 class FixedDtoa {
61
62 // Represents a 128bit type. This class should be replaced by a native type on
63 // platforms that support 128bit integers.
64 static class UInt128 {
65
66 private static final long kMask32 = 0xFFFFFFFFL;
67 // Value == (high_bits_ << 64) + low_bits_
68 private long high_bits_;
69 private long low_bits_;
70
71 UInt128(final long high_bits, final long low_bits) {
72 this.high_bits_ = high_bits;
73 this.low_bits_ = low_bits;
74 }
75
76 void multiply(final int multiplicand) {
77 long accumulator;
78
79 accumulator = (low_bits_ & kMask32) * multiplicand;
80 long part = accumulator & kMask32;
81 accumulator >>>= 32;
82 accumulator = accumulator + (low_bits_ >>> 32) * multiplicand;
83 low_bits_ = (accumulator << 32) + part;
84 accumulator >>>= 32;
85 accumulator = accumulator + (high_bits_ & kMask32) * multiplicand;
86 part = accumulator & kMask32;
87 accumulator >>>= 32;
88 accumulator = accumulator + (high_bits_ >>> 32) * multiplicand;
89 high_bits_ = (accumulator << 32) + part;
90 assert ((accumulator >>> 32) == 0);
91 }
92
93 void shift(final int shift_amount) {
94 assert (-64 <= shift_amount && shift_amount <= 64);
95 if (shift_amount == 0) {
96 return;
97 } else if (shift_amount == -64) {
98 high_bits_ = low_bits_;
99 low_bits_ = 0;
100 } else if (shift_amount == 64) {
101 low_bits_ = high_bits_;
102 high_bits_ = 0;
103 } else if (shift_amount <= 0) {
104 high_bits_ <<= -shift_amount;
105 high_bits_ += low_bits_ >>> (64 + shift_amount);
106 low_bits_ <<= -shift_amount;
107 } else {
108 low_bits_ >>>= shift_amount;
109 low_bits_ += high_bits_ << (64 - shift_amount);
110 high_bits_ >>>= shift_amount;
111 }
112 }
113
114 // Modifies *this to *this MOD (2^power).
115 // Returns *this DIV (2^power).
116 int divModPowerOf2(final int power) {
117 if (power >= 64) {
118 final int result = (int) (high_bits_ >>> (power - 64));
119 high_bits_ -= (long) (result) << (power - 64);
120 return result;
121 } else {
122 final long part_low = low_bits_ >>> power;
123 final long part_high = high_bits_ << (64 - power);
124 final int result = (int) (part_low + part_high);
125 high_bits_ = 0;
126 low_bits_ -= part_low << power;
127 return result;
128 }
129 }
130
131 boolean isZero() {
132 return high_bits_ == 0 && low_bits_ == 0;
133 }
134
135 int bitAt(final int position) {
136 if (position >= 64) {
137 return (int) (high_bits_ >>> (position - 64)) & 1;
138 } else {
139 return (int) (low_bits_ >>> position) & 1;
140 }
141 }
142
143 };
144
145
146 static final int kDoubleSignificandSize = 53; // Includes the hidden bit.
147
148
149 static void fillDigits32FixedLength(int number, final int requested_length,
150 final DtoaBuffer buffer) {
151 for (int i = requested_length - 1; i >= 0; --i) {
152 buffer.chars[buffer.length + i] = (char) ('0' + Integer.remainderUnsigned(number, 10));
153 number = Integer.divideUnsigned(number, 10);
154 }
155 buffer.length += requested_length;
156 }
157
158
159 static void fillDigits32(int number, final DtoaBuffer buffer) {
160 int number_length = 0;
161 // We fill the digits in reverse order and exchange them afterwards.
162 while (number != 0) {
163 final int digit = Integer.remainderUnsigned(number, 10);
164 number = Integer.divideUnsigned(number, 10);
165 buffer.chars[buffer.length + number_length] = (char) ('0' + digit);
166 number_length++;
167 }
168 // Exchange the digits.
169 int i = buffer.length;
170 int j = buffer.length + number_length - 1;
171 while (i < j) {
172 final char tmp = buffer.chars[i];
173 buffer.chars[i] = buffer.chars[j];
174 buffer.chars[j] = tmp;
175 i++;
176 j--;
177 }
178 buffer.length += number_length;
179 }
180
181
182 static void fillDigits64FixedLength(long number, final DtoaBuffer buffer) {
183 final int kTen7 = 10000000;
184 // For efficiency cut the number into 3 uint32_t parts, and print those.
185 final int part2 = (int) Long.remainderUnsigned(number, kTen7);
186 number = Long.divideUnsigned(number, kTen7);
187 final int part1 = (int) Long.remainderUnsigned(number, kTen7);
188 final int part0 = (int) Long.divideUnsigned(number, kTen7);
189
190 fillDigits32FixedLength(part0, 3, buffer);
191 fillDigits32FixedLength(part1, 7, buffer);
192 fillDigits32FixedLength(part2, 7, buffer);
193 }
194
195
196 static void FillDigits64(long number, final DtoaBuffer buffer) {
197 final int kTen7 = 10000000;
198 // For efficiency cut the number into 3 uint32_t parts, and print those.
199 final int part2 = (int) Long.remainderUnsigned(number, kTen7);
200 number = Long.divideUnsigned(number, kTen7);
201 final int part1 = (int) Long.remainderUnsigned(number, kTen7);
202 final int part0 = (int) Long.divideUnsigned(number, kTen7);
203
204 if (part0 != 0) {
205 fillDigits32(part0, buffer);
206 fillDigits32FixedLength(part1, 7, buffer);
207 fillDigits32FixedLength(part2, 7, buffer);
208 } else if (part1 != 0) {
209 fillDigits32(part1, buffer);
210 fillDigits32FixedLength(part2, 7, buffer);
211 } else {
212 fillDigits32(part2, buffer);
213 }
214 }
215
216
217 static void roundUp(final DtoaBuffer buffer) {
218 // An empty buffer represents 0.
219 if (buffer.length == 0) {
220 buffer.chars[0] = '1';
221 buffer.decimalPoint = 1;
222 buffer.length = 1;
223 return;
224 }
225 // Round the last digit until we either have a digit that was not '9' or until
226 // we reached the first digit.
227 buffer.chars[buffer.length - 1]++;
228 for (int i = buffer.length - 1; i > 0; --i) {
229 if (buffer.chars[i] != '0' + 10) {
230 return;
231 }
232 buffer.chars[i] = '0';
233 buffer.chars[i - 1]++;
234 }
235 // If the first digit is now '0' + 10, we would need to set it to '0' and add
236 // a '1' in front. However we reach the first digit only if all following
237 // digits had been '9' before rounding up. Now all trailing digits are '0' and
238 // we simply switch the first digit to '1' and update the decimal-point
239 // (indicating that the point is now one digit to the right).
240 if (buffer.chars[0] == '0' + 10) {
241 buffer.chars[0] = '1';
242 buffer.decimalPoint++;
243 }
244 }
245
246
247 // The given fractionals number represents a fixed-point number with binary
248 // point at bit (-exponent).
249 // Preconditions:
250 // -128 <= exponent <= 0.
251 // 0 <= fractionals * 2^exponent < 1
252 // The buffer holds the result.
253 // The function will round its result. During the rounding-process digits not
254 // generated by this function might be updated, and the decimal-point variable
255 // might be updated. If this function generates the digits 99 and the buffer
256 // already contained "199" (thus yielding a buffer of "19999") then a
257 // rounding-up will change the contents of the buffer to "20000".
258 static void fillFractionals(long fractionals, final int exponent,
259 final int fractional_count, final DtoaBuffer buffer) {
260 assert (-128 <= exponent && exponent <= 0);
261 // 'fractionals' is a fixed-decimalPoint number, with binary decimalPoint at bit
262 // (-exponent). Inside the function the non-converted remainder of fractionals
263 // is a fixed-decimalPoint number, with binary decimalPoint at bit 'decimalPoint'.
264 if (-exponent <= 64) {
265 // One 64 bit number is sufficient.
266 assert (fractionals >>> 56 == 0);
267 int point = -exponent;
268 for (int i = 0; i < fractional_count; ++i) {
269 if (fractionals == 0) break;
270 // Instead of multiplying by 10 we multiply by 5 and adjust the point
271 // location. This way the fractionals variable will not overflow.
272 // Invariant at the beginning of the loop: fractionals < 2^point.
273 // Initially we have: point <= 64 and fractionals < 2^56
274 // After each iteration the point is decremented by one.
275 // Note that 5^3 = 125 < 128 = 2^7.
276 // Therefore three iterations of this loop will not overflow fractionals
277 // (even without the subtraction at the end of the loop body). At this
278 // time point will satisfy point <= 61 and therefore fractionals < 2^point
279 // and any further multiplication of fractionals by 5 will not overflow.
280 fractionals *= 5;
281 point--;
282 final int digit = (int) (fractionals >>> point);
283 assert (digit <= 9);
284 buffer.chars[buffer.length] = (char) ('0' + digit);
285 buffer.length++;
286 fractionals -= (long) (digit) << point;
287 }
288 // If the first bit after the point is set we have to round up.
289 assert (fractionals == 0 || point - 1 >= 0);
290 if ((fractionals != 0) && ((fractionals >>> (point - 1)) & 1) == 1) {
291 roundUp(buffer);
292 }
293 } else { // We need 128 bits.
294 assert (64 < -exponent && -exponent <= 128);
295 final UInt128 fractionals128 = new UInt128(fractionals, 0);
296 fractionals128.shift(-exponent - 64);
297 int point = 128;
298 for (int i = 0; i < fractional_count; ++i) {
299 if (fractionals128.isZero()) break;
300 // As before: instead of multiplying by 10 we multiply by 5 and adjust the
301 // point location.
302 // This multiplication will not overflow for the same reasons as before.
303 fractionals128.multiply(5);
304 point--;
305 final int digit = fractionals128.divModPowerOf2(point);
306 assert (digit <= 9);
307 buffer.chars[buffer.length] = (char) ('0' + digit);
308 buffer.length++;
309 }
310 if (fractionals128.bitAt(point - 1) == 1) {
311 roundUp(buffer);
312 }
313 }
314 }
315
316
317 // Removes leading and trailing zeros.
318 // If leading zeros are removed then the decimal point position is adjusted.
319 static void trimZeros(final DtoaBuffer buffer) {
320 while (buffer.length > 0 && buffer.chars[buffer.length - 1] == '0') {
321 buffer.length--;
322 }
323 int first_non_zero = 0;
324 while (first_non_zero < buffer.length && buffer.chars[first_non_zero] == '0') {
325 first_non_zero++;
326 }
327 if (first_non_zero != 0) {
328 for (int i = first_non_zero; i < buffer.length; ++i) {
329 buffer.chars[i - first_non_zero] = buffer.chars[i];
330 }
331 buffer.length -= first_non_zero;
332 buffer.decimalPoint -= first_non_zero;
333 }
334 }
335
336
337 static boolean fastFixedDtoa(final double v,
338 final int fractional_count,
339 final DtoaBuffer buffer) {
340 final long kMaxUInt32 = 0xFFFFFFFFL;
341 final long l = IeeeDouble.doubleToLong(v);
342 long significand = IeeeDouble.significand(l);
343 final int exponent = IeeeDouble.exponent(l);
344 // v = significand * 2^exponent (with significand a 53bit integer).
345 // If the exponent is larger than 20 (i.e. we may have a 73bit number) then we
346 // don't know how to compute the representation. 2^73 ~= 9.5*10^21.
347 // If necessary this limit could probably be increased, but we don't need
348 // more.
349 if (exponent > 20) return false;
350 if (fractional_count > 20) return false;
351 // At most kDoubleSignificandSize bits of the significand are non-zero.
352 // Given a 64 bit integer we have 11 0s followed by 53 potentially non-zero
353 // bits: 0..11*..0xxx..53*..xx
354 if (exponent + kDoubleSignificandSize > 64) {
355 // The exponent must be > 11.
356 //
357 // We know that v = significand * 2^exponent.
358 // And the exponent > 11.
359 // We simplify the task by dividing v by 10^17.
360 // The quotient delivers the first digits, and the remainder fits into a 64
361 // bit number.
362 // Dividing by 10^17 is equivalent to dividing by 5^17*2^17.
363 final long kFive17 = 0xB1A2BC2EC5L; // 5^17
364 long divisor = kFive17;
365 final int divisor_power = 17;
366 long dividend = significand;
367 final int quotient;
368 final long remainder;
369 // Let v = f * 2^e with f == significand and e == exponent.
370 // Then need q (quotient) and r (remainder) as follows:
371 // v = q * 10^17 + r
372 // f * 2^e = q * 10^17 + r
373 // f * 2^e = q * 5^17 * 2^17 + r
374 // If e > 17 then
375 // f * 2^(e-17) = q * 5^17 + r/2^17
376 // else
377 // f = q * 5^17 * 2^(17-e) + r/2^e
378 if (exponent > divisor_power) {
379 // We only allow exponents of up to 20 and therefore (17 - e) <= 3
380 dividend <<= exponent - divisor_power;
381 quotient = (int) Long.divideUnsigned(dividend, divisor);
382 remainder = Long.remainderUnsigned(dividend, divisor) << divisor_power;
383 } else {
384 divisor <<= divisor_power - exponent;
385 quotient = (int) Long.divideUnsigned(dividend, divisor);
386 remainder = Long.remainderUnsigned(dividend, divisor) << exponent;
387 }
388 fillDigits32(quotient, buffer);
389 fillDigits64FixedLength(remainder, buffer);
390 buffer.decimalPoint = buffer.length;
391 } else if (exponent >= 0) {
392 // 0 <= exponent <= 11
393 significand <<= exponent;
394 FillDigits64(significand, buffer);
395 buffer.decimalPoint = buffer.length;
396 } else if (exponent > -kDoubleSignificandSize) {
397 // We have to cut the number.
398 final long integrals = significand >>> -exponent;
399 final long fractionals = significand - (integrals << -exponent);
400 if (Long.compareUnsigned(integrals, kMaxUInt32) > 0) {
401 FillDigits64(integrals, buffer);
402 } else {
403 fillDigits32((int) (integrals), buffer);
404 }
405 buffer.decimalPoint = buffer.length;
406 fillFractionals(fractionals, exponent, fractional_count, buffer);
407 } else if (exponent < -128) {
408 // This configuration (with at most 20 digits) means that all digits must be
409 // 0.
410 assert (fractional_count <= 20);
411 buffer.reset();
412 buffer.decimalPoint = -fractional_count;
413 } else {
414 buffer.decimalPoint = 0;
415 fillFractionals(significand, exponent, fractional_count, buffer);
416 }
417 trimZeros(buffer);
418 if (buffer.length == 0) {
419 // The string is empty and the decimal_point thus has no importance. Mimick
420 // Gay's dtoa and and set it to -fractional_count.
421 buffer.decimalPoint = -fractional_count;
422 }
423 return true;
424 }
425
426 }