blob: 70149063a1300e1cb892653d5050ad156b64502a [file] [log] [blame]
/*
* Copyright (C) Dmitry Volyntsev
* Copyright (C) NGINX, Inc.
*
* Grisu2 algorithm implementation for printing floating-point numbers based
* upon the work of Milo Yip and Doug Currie.
*
* For algorithm information, see Loitsch, Florian. "Printing
* floating-point numbers quickly and accurately with integers." ACM Sigplan
* Notices 45.6 (2010): 233-243.
*
* Copyright (C) 2015 Doug Currie
* based on dtoa_milo.h
* Copyright (C) 2014 Milo Yip
*
* Permission is hereby granted, free of charge, to any person obtaining a copy
* of this software and associated documentation files (the "Software"), to deal
* in the Software without restriction, including without limitation the rights
* to use, copy, modify, merge, publish, distribute, sublicense, and/or sell
* copies of the Software, and to permit persons to whom the Software is
* furnished to do so, subject to the following conditions:
*
* The above copyright notice and this permission notice shall be included in
* all copies or substantial portions of the Software.
*
* THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
* IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
* FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
* AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
* LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
* OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN
* THE SOFTWARE.
*/
#include <njs_main.h>
#include <njs_diyfp.h>
#include <njs_dtoa.h>
njs_inline void
njs_grisu2_round(char *start, size_t len, uint64_t delta, uint64_t rest,
uint64_t ten_kappa, uint64_t wp_w)
{
while (rest < wp_w && delta - rest >= ten_kappa
&& (rest + ten_kappa < wp_w || /* closer */
wp_w - rest > rest + ten_kappa - wp_w))
{
start[len - 1]--;
rest += ten_kappa;
}
}
njs_inline int
njs_dec_count(uint32_t n)
{
if (n < 10000) {
if (n < 100) {
return (n < 10) ? 1 : 2;
} else {
return (n < 1000) ? 3 : 4;
}
} else {
if (n < 1000000) {
return (n < 100000) ? 5 : 6;
} else {
if (n < 100000000) {
return (n < 10000000) ? 7 : 8;
} else {
return (n < 1000000000) ? 9 : 10;
}
}
}
}
njs_inline size_t
njs_grisu2_gen(njs_diyfp_t W, njs_diyfp_t Mp, uint64_t delta, char *start,
int *dec_exp)
{
int kappa;
char c, *p;
uint32_t p1, d;
uint64_t p2, tmp;
njs_diyfp_t one, wp_w;
static const uint64_t pow10[] = {
1,
10,
100,
1000,
10000,
100000,
1000000,
10000000,
100000000,
1000000000
};
wp_w = njs_diyfp_sub(Mp, W);
one = njs_diyfp((uint64_t) 1 << -Mp.exp, Mp.exp);
p1 = (uint32_t) (Mp.significand >> -one.exp);
p2 = Mp.significand & (one.significand - 1);
p = start;
/* GCC 4.2 complains about uninitialized d. */
d = 0;
kappa = njs_dec_count(p1);
while (kappa > 0) {
switch (kappa) {
case 10: d = p1 / 1000000000; p1 %= 1000000000; break;
case 9: d = p1 / 100000000; p1 %= 100000000; break;
case 8: d = p1 / 10000000; p1 %= 10000000; break;
case 7: d = p1 / 1000000; p1 %= 1000000; break;
case 6: d = p1 / 100000; p1 %= 100000; break;
case 5: d = p1 / 10000; p1 %= 10000; break;
case 4: d = p1 / 1000; p1 %= 1000; break;
case 3: d = p1 / 100; p1 %= 100; break;
case 2: d = p1 / 10; p1 %= 10; break;
case 1: d = p1; p1 = 0; break;
default:
njs_unreachable();
}
if (d != 0 || p != start) {
*p++ = '0' + d;
}
kappa--;
tmp = ((uint64_t) p1 << -one.exp) + p2;
if (tmp <= delta) {
*dec_exp += kappa;
njs_grisu2_round(start, p - start, delta, tmp,
pow10[kappa] << -one.exp, wp_w.significand);
return p - start;
}
}
/* kappa = 0. */
for ( ;; ) {
p2 *= 10;
delta *= 10;
c = (char) (p2 >> -one.exp);
if (c != 0 || p != start) {
*p++ = '0' + c;
}
p2 &= one.significand - 1;
kappa--;
if (p2 < delta) {
*dec_exp += kappa;
tmp = (-kappa < 10) ? pow10[-kappa] : 0;
njs_grisu2_round(start, p - start, delta, p2, one.significand,
wp_w.significand * tmp);
break;
}
}
return p - start;
}
njs_inline njs_diyfp_t
njs_diyfp_normalize_boundary(njs_diyfp_t v)
{
while ((v.significand & (NJS_DBL_HIDDEN_BIT << 1)) == 0) {
v.significand <<= 1;
v.exp--;
}
return njs_diyfp_shift_left(v, NJS_SIGNIFICAND_SHIFT - 2);
}
njs_inline void
njs_diyfp_normalize_boundaries(njs_diyfp_t v, njs_diyfp_t* minus,
njs_diyfp_t* plus)
{
njs_diyfp_t pl, mi;
pl = njs_diyfp_normalize_boundary(njs_diyfp((v.significand << 1) + 1,
v.exp - 1));
if (v.significand == NJS_DBL_HIDDEN_BIT) {
mi = njs_diyfp((v.significand << 2) - 1, v.exp - 2);
} else {
mi = njs_diyfp((v.significand << 1) - 1, v.exp - 1);
}
mi.significand <<= mi.exp - pl.exp;
mi.exp = pl.exp;
*plus = pl;
*minus = mi;
}
njs_inline size_t
njs_grisu2(double value, char *start, int *dec_exp)
{
njs_diyfp_t v, w_m, w_p, c_mk, W, Wp, Wm;
v = njs_d2diyfp(value);
njs_diyfp_normalize_boundaries(v, &w_m, &w_p);
c_mk = njs_cached_power_bin(w_p.exp, dec_exp);
W = njs_diyfp_mul(njs_diyfp_normalize(v), c_mk);
Wp = njs_diyfp_mul(w_p, c_mk);
Wm = njs_diyfp_mul(w_m, c_mk);
Wm.significand++;
Wp.significand--;
return njs_grisu2_gen(W, Wp, Wp.significand - Wm.significand, start,
dec_exp);
}
njs_inline size_t
njs_write_exponent(int exp, char* start)
{
char *p;
size_t len;
uint32_t u32;
char buf[4];
/* -324 <= exp <= 308. */
if (exp < 0) {
*start++ = '-';
exp = -exp;
} else {
*start++ = '+';
}
u32 = exp;
p = buf + njs_length(buf);
do {
*--p = u32 % 10 + '0';
u32 /= 10;
} while (u32 != 0);
len = buf + njs_length(buf) - p;
memcpy(start, p, len);
return len + 1;
}
njs_inline size_t
njs_prettify(char *start, size_t len, int dec_exp)
{
int kk, offset, length;
size_t size;
/* 10^(kk-1) <= v < 10^kk */
length = (int) len;
kk = length + dec_exp;
if (length <= kk && kk <= 21) {
/* 1234e7 -> 12340000000 */
if (kk - length > 0) {
njs_memset(&start[length], '0', kk - length);
}
return kk;
} else if (0 < kk && kk <= 21) {
/* 1234e-2 -> 12.34 */
memmove(&start[kk + 1], &start[kk], length - kk);
start[kk] = '.';
return (length + 1);
} else if (-6 < kk && kk <= 0) {
/* 1234e-6 -> 0.001234 */
offset = 2 - kk;
memmove(&start[offset], start, length);
start[0] = '0';
start[1] = '.';
if (offset - 2 > 0) {
njs_memset(&start[2], '0', offset - 2);
}
return (length + offset);
} else if (length == 1) {
/* 1e30 */
start[1] = 'e';
size = njs_write_exponent(kk - 1, &start[2]);
return (size + 2);
}
/* 1234e30 -> 1.234e33 */
memmove(&start[2], &start[1], length - 1);
start[1] = '.';
start[length + 1] = 'e';
size = njs_write_exponent(kk - 1, &start[length + 2]);
return (size + length + 2);
}
size_t
njs_dtoa(double value, char *start)
{
int dec_exp, minus;
char *p;
size_t length;
/* Not handling NaN and inf. */
minus = 0;
p = start;
if (value == 0) {
*p++ = '0';
return (p - start);
}
if (signbit(value)) {
*p++ = '-';
value = -value;
minus = 1;
}
length = njs_grisu2(value, p, &dec_exp);
length = njs_prettify(p, length, dec_exp);
return (minus + length);
}