Index: uspace/app/tester/Makefile =================================================================== --- uspace/app/tester/Makefile (revision f0da685587e02cc34984e5f558211f7bc44af1aa) +++ uspace/app/tester/Makefile (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -42,4 +42,5 @@ print/print4.c \ print/print5.c \ + print/print6.c \ console/console1.c \ stdio/stdio1.c \ Index: uspace/app/tester/print/print5.def =================================================================== --- uspace/app/tester/print/print5.def (revision f0da685587e02cc34984e5f558211f7bc44af1aa) +++ uspace/app/tester/print/print5.def (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -1,6 +1,6 @@ { - "print1", - "String printf test", - &test_print1, + "print5", + "Char printf test", + &test_print5, true }, Index: uspace/app/tester/print/print6.c =================================================================== --- uspace/app/tester/print/print6.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) +++ uspace/app/tester/print/print6.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -0,0 +1,151 @@ +#include +#include +#include "../tester.h" + +#include + + + + +const char *test_print6(void) +{ + struct { + double val; + const char *fmt; + const char *exp_str; + const char *warn_str; + } pat[] = { + /* + * Generic + */ + { 2.0, "%g", "2", 0 }, + { 0, "%g", "0", 0 }, + { 0.1, "%g", "0.1", 0 }, + { 9e59, "%g", "9e+59", 0 }, + { -9e-59, "%g", "-9e-59", 0 }, + { 1e307, "%g", "1e+307", 0 }, + { 0.09999999999999999, "%g", "9.999999999999999e-02", 0 }, + { 0.099999999999999999, "%g", "0.1", 0 }, + + /* gcc and msvc convert "3.4567e-317" to different binary doubles. */ + { 3.4567e-317, "%g", "3.4567e-317", "3.456998e-317" }, + { 3.4567e-318, "%g", "3.4567e-318", 0 }, + { 123456789012345.0, "%g", "123456789012345", 0 }, + { -123456789012345.0, "%g", "-123456789012345", 0 }, + + /* Special */ + { 1e300 * 1e300, "%g", "inf", 0 }, + { -1.0 /(1e300 * 1e300), "%g", "-0", 0 }, + + { 1234567.8901, "%g", "1234567.8901", 0 }, + { 1234567.80012, "%g", "1234567.80012", 0 }, + { 112e-32, "%g", "1.12e-30", 0 }, + { 10.0e45, "%g", "1e+46", 0 }, + + /* rounding w/ trailing zero removal */ + { 0.01, "%10.6g", " 0.01", 0 }, + { 9.495, "%10.2g", " 9.5", 0 }, + { 9.495e30, "%10.2g", " 9.5e+30", 0 }, + { 9.495e30, "%10g", " 9.495e+30", 0 }, + { 9.495e30, "%10.6g", " 9.495e+30", 0 }, + + /* + * Scientific + */ + { 1e05, "%e", "1.000000e+05", 0 }, + + /* full padding */ + { 1e-1, "%+010.3e", "+1.000e-01", 0 }, /* __PRINTF_FLAG_SHOWPLUS | __PRINTF_FLAG_ZEROPADDED */ + { 1e-1, "%+10.3e", "+1.000e-01", 0 }, + { 1e-1, "%+-10.3e", "+1.000e-01", 0 }, /* __PRINTF_FLAG_SHOWPLUS | __PRINTF_FLAG_LEFTALIGNED */ + + /* padding */ + { 1e-1, "%+010.2e", "+01.00e-01", 0 }, /* __PRINTF_FLAG_SHOWPLUS | __PRINTF_FLAG_ZEROPADDED */ + { 1e-1, "%+10.2e", " +1.00e-01", 0 }, + { 1e-1, "%+-10.2e", "+1.00e-01 ", 0 }, /* __PRINTF_FLAG_SHOWPLUS | __PRINTF_FLAG_LEFTALIGNED */ + + { 1e-1, "% 010.2e", " 01.00e-01", 0 }, /* __PRINTF_FLAG_SPACESIGN | __PRINTF_FLAG_ZEROPADDED */ + { 1e-1, "%010.2e", "001.00e-01", 0 }, /* __PRINTF_FLAG_ZEROPADDED */ + { 1e-1, "% 10.2e", " 1.00e-01", 0 }, /* __PRINTF_FLAG_SPACESIGN */ + { 1e-1, "%10.2e", " 1.00e-01", 0 }, + + /* padding fractionals */ + { 1.08e29, "%+010.3e", "+1.080e+29", 0 }, /* __PRINTF_FLAG_SHOWPLUS | __PRINTF_FLAG_ZEROPADDED */ + { 1.08e29, "%+10.3e", "+1.080e+29", 0 }, + { 1.08e29, "%+011.2e", "+001.08e+29", 0 }, /* __PRINTF_FLAG_SHOWPLUS | __PRINTF_FLAG_ZEROPADDED */ + { 1.085e29, "%11.2e", " 1.09e+29", 0 }, + + /* rounding */ + { 1.345e2, "%+10.2e", " +1.35e+02", 0 }, + { 9.995e2, "%+10.2e", " +1.00e+03", 0 }, + { -9.99499999e2, "%10.2e", " -9.99e+02", 0 }, + { -9.99499999e2, "%10.0e", " -1e+03", 0 }, + { -9.99499999e2, "%#10.0e", " -1.e+03", 0 }, /* __PRINTF_FLAG_DECIMALPT */ + { -1.2345006789e+231, "%#10.10e", "-1.2345006789e+231", 0 }, /* __PRINTF_FLAG_DECIMALPT */ + { -1.23450067995e+231, "%#10.10e", "-1.2345006800e+231", 0 }, /* __PRINTF_FLAG_DECIMALPT */ + + /* special */ + { 1e300 * 1e300, "%10.5e", " inf", 0 }, + { -1.0 /(1e300 * 1e300), "%10.2e", " -0.00e+00", 0 }, + { 1e300 * 1e300, "%10.5E", " INF", 0 }, /* __PRINTF_FLAG_BIGCHARS */ + { -1.0 /(1e300 * 1e300), "%10.2E", " -0.00E+00", 0 }, /* __PRINTF_FLAG_BIGCHARS */ + + /* + * Fixed + */ + + /* padding */ + { 1e-1, "% 010.3f", " 00000.100", 0 }, /* __PRINTF_FLAG_SPACESIGN | __PRINTF_FLAG_ZEROPADDED */ + { 1e-1, "% 0-10.3f", " 0.100 ", 0 }, /* __PRINTF_FLAG_SPACESIGN | __PRINTF_FLAG_ZEROPADDED | __PRINTF_FLAG_LEFTALIGNED */ + { 1e-1, "% 010.3f", " 00000.100", 0 }, /* __PRINTF_FLAG_SPACESIGN | __PRINTF_FLAG_ZEROPADDED */ + { 1e-1, "%10.3f", " 0.100", 0 }, + + /* rounding */ + { -0.0, "%10.0f", " -0", 0 }, + { -0.099, "%+10.3f", " -0.099", 0 }, + { -0.0995, "%+10.3f", " -0.100", 0 }, + { -0.0994, "%+10.3f", " -0.099", 0 }, + { -99.995, "%+10.0f", " -100", 0 }, + { 3.5, "%+10.30f", "+3.500000000000000000000000000000", 0 }, + { 3.5, "%+10.0f", " +4", 0 }, + { 0.1, "%+10.6f", " +0.100000", 0 }, + + /* The compiler will go for closer 0.10..055 instead of 0.09..917 */ + { 0.1, "%+10.20f", "+0.10000000000000000550", 0 }, + /* Next closest to 0.1 */ + { 0.0999999999999999917, "%+10.20f", "+0.09999999999999999170", 0 }, + { 0.0999999999999999917, "%+10f", " +0.100000", 0 }, + { 0.0999999999999998945, "%10.20f", "0.09999999999999989450", 0 }, + + }; + + int patterns_len = (int)(sizeof(pat) / sizeof(pat[0])); + int failed = 0; + const int buf_size = 256; + char buf[256 + 1] = { 0 }; + + TPRINTF("Test printing of floating point numbers via printf(\"%%f\"):\n"); + + for (int i = 0; i < patterns_len; ++i) { + + snprintf(buf, buf_size, pat[i].fmt, pat[i].val); + + if (0 == str_cmp(buf, pat[i].exp_str)) { + TPRINTF("ok: %s |%s| == |%s|\n", pat[i].fmt, buf, pat[i].exp_str); + } else { + if (pat[i].warn_str && 0 == str_cmp(buf, pat[i].warn_str)) { + TPRINTF("warn: %s |%s| != |%s|\n", pat[i].fmt, buf, pat[i].exp_str); + } else { + ++failed; + TPRINTF("ERR: %s |%s| != |%s|\n", pat[i].fmt, buf, pat[i].exp_str); + } + } + } + + if (failed) { + return "Unexpectedly misprinted floating point numbers."; + } else { + return 0; + } +} + Index: uspace/app/tester/print/print6.def =================================================================== --- uspace/app/tester/print/print6.def (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) +++ uspace/app/tester/print/print6.def (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -0,0 +1,6 @@ +{ + "print6", + "Floating point printf test", + &test_print6, + true +}, Index: uspace/app/tester/tester.c =================================================================== --- uspace/app/tester/tester.c (revision f0da685587e02cc34984e5f558211f7bc44af1aa) +++ uspace/app/tester/tester.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -53,4 +53,5 @@ #include "print/print4.def" #include "print/print5.def" +#include "print/print6.def" #include "console/console1.def" #include "stdio/stdio1.def" Index: uspace/app/tester/tester.h =================================================================== --- uspace/app/tester/tester.h (revision f0da685587e02cc34984e5f558211f7bc44af1aa) +++ uspace/app/tester/tester.h (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -85,4 +85,5 @@ extern const char *test_print4(void); extern const char *test_print5(void); +extern const char *test_print6(void); extern const char *test_console1(void); extern const char *test_stdio1(void); Index: uspace/lib/c/Makefile =================================================================== --- uspace/lib/c/Makefile (revision f0da685587e02cc34984e5f558211f7bc44af1aa) +++ uspace/lib/c/Makefile (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -116,4 +116,7 @@ generic/iplink.c \ generic/iplink_srv.c \ + generic/ieee_double.c \ + generic/power_of_ten.c \ + generic/double_to_str.c \ generic/malloc.c \ generic/sysinfo.c \ Index: uspace/lib/c/generic/double_to_str.c =================================================================== --- uspace/lib/c/generic/double_to_str.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) +++ uspace/lib/c/generic/double_to_str.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -0,0 +1,784 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include + +#include "private/power_of_ten.h" +#include + +#include +#include +#include + +/* + * Floating point numbers are converted from their binary representation + * into a decimal string using the algorithm described in: + * Printing floating-point numbers quickly and accurately with integers + * Loitsch, 2010 + */ + +/** The computation assumes a significand of 64 bits. */ +static const int significand_width = 64; + +/* Scale exponents to interval [alpha, gamma] to simplify conversion. */ +static const int alpha = -59; +static const int gamma = -32; + + +/** Returns true if the most-significant bit of num.significand is set. */ +static bool is_normalized(fp_num_t num) +{ + assert(8*sizeof(num.significand) == significand_width); + + /* Normalized == most significant bit of the significand is set. */ + return (num.significand & (1ULL << (significand_width - 1))) != 0; +} + +/** Returns a normalized num with the MSbit set. */ +static fp_num_t normalize(fp_num_t num) +{ + const uint64_t top10bits = 0xffc0000000000000ULL; + + /* num usually comes from ieee_double with top 10 bits zero. */ + while (0 == (num.significand & top10bits)) { + num.significand <<= 10; + num.exponent -= 10; + } + + while (!is_normalized(num)) { + num.significand <<= 1; + --num.exponent; + } + + return num; +} + + +/** Returns x * y with an error of less than 0.5 ulp. */ +static fp_num_t multiply(fp_num_t x, fp_num_t y) +{ + assert(/* is_normalized(x) && */ is_normalized(y)); + + const uint32_t low_bits = -1; + + uint64_t a, b, c, d; + a = x.significand >> 32; + b = x.significand & low_bits; + c = y.significand >> 32; + d = y.significand & low_bits; + + uint64_t bd, ad, bc, ac; + bd = b * d; + ad = a * d; + + bc = b * c; + ac = a * c; + + /* Denote 32 bit parts of x a y as: x == a b, y == c d. Then: + * a b + * * c d + * ---------- + * ad bd .. multiplication of 32bit parts results in 64bit parts + * + ac bc + * ---------- + * [b|d] .. Depicts 64 bit intermediate results and how + * [a|d] the 32 bit parts of these results overlap and + * [b|c] contribute to the final result. + * +[a|c] + * ---------- + * [ret] + * [tmp] + */ + uint64_t tmp = (bd >> 32) + (ad & low_bits) + (bc & low_bits); + + /* Round upwards. */ + tmp += 1U << 31; + + fp_num_t ret; + ret.significand = ac + (bc >> 32) + (ad >> 32) + (tmp >> 32); + ret.exponent = x.exponent + y.exponent + significand_width; + + return ret; +} + + +/** Returns a - b. Both must have the same exponent. */ +static fp_num_t subtract(fp_num_t a, fp_num_t b) +{ + assert(a.exponent == b.exponent); + assert(a.significand >= b.significand); + + fp_num_t result; + + result.significand = a.significand - b.significand; + result.exponent = a.exponent; + + return result; +} + + +/** Returns the interval [low, high] of numbers that convert to binary val. */ +static void get_normalized_bounds(ieee_double_t val, fp_num_t *high, + fp_num_t *low, fp_num_t *val_dist) +{ + /* + * Only works if val comes directly from extract_ieee_double without + * being manipulated in any way (eg it must not be normalized). + */ + assert(!is_normalized(val.pos_val)); + + high->significand = (val.pos_val.significand << 1) + 1; + high->exponent = val.pos_val.exponent - 1; + + /* val_dist = high - val */ + val_dist->significand = 1; + val_dist->exponent = val.pos_val.exponent - 1; + + /* Distance from both lower and upper bound is the same. */ + if (!val.is_accuracy_step) { + low->significand = (val.pos_val.significand << 1) - 1; + low->exponent = val.pos_val.exponent - 1; + } else { + low->significand = (val.pos_val.significand << 2) - 1; + low->exponent = val.pos_val.exponent - 2; + } + + *high = normalize(*high); + + /* + * Lower bound may not be normalized if subtracting 1 unit + * reset the most-significant bit to 0. + */ + low->significand = low->significand << (low->exponent - high->exponent); + low->exponent = high->exponent; + + val_dist->significand = + val_dist->significand << (val_dist->exponent - high->exponent); + val_dist->exponent = high->exponent; +} + +/** Determines the interval of numbers that have the binary representation + * of val. + * + * Numbers in the range [scaled_upper_bound - bounds_delta, scaled_upper_bound] + * have the same double binary representation as val. + * + * Bounds are scaled by 10^scale so that alpha <= exponent <= gamma. + * Moreover, scaled_upper_bound is normalized. + * + * val_dist is the scaled distance from val to the upper bound, ie + * val_dist == (upper_bound - val) * 10^scale + */ +static void calc_scaled_bounds(ieee_double_t val, fp_num_t *scaled_upper_bound, + fp_num_t *bounds_delta, fp_num_t *val_dist, int *scale) +{ + fp_num_t upper_bound, lower_bound; + + get_normalized_bounds(val, &upper_bound, &lower_bound, val_dist); + + assert(upper_bound.exponent == lower_bound.exponent); + assert(is_normalized(upper_bound)); + assert(normalize(val.pos_val).exponent == upper_bound.exponent); + + /* + * Find such a cached normalized power of 10 that if multiplied + * by upper_bound the binary exponent of upper_bound almost vanishes, + * ie: + * upper_scaled := upper_bound * 10^scale + * alpha <= upper_scaled.exponent <= gamma + * alpha <= upper_bound.exponent + pow_10.exponent + 64 <= gamma + */ + fp_num_t scaling_power_of_10; + int lower_bin_exp = alpha - upper_bound.exponent - significand_width; + + get_power_of_ten(lower_bin_exp, &scaling_power_of_10, scale); + + int scale_exp = scaling_power_of_10.exponent; + assert(alpha <= upper_bound.exponent + scale_exp + significand_width); + assert(upper_bound.exponent + scale_exp + significand_width <= gamma); + + fp_num_t upper_scaled = multiply(upper_bound, scaling_power_of_10); + fp_num_t lower_scaled = multiply(lower_bound, scaling_power_of_10); + *val_dist = multiply(*val_dist, scaling_power_of_10); + + assert(alpha <= upper_scaled.exponent && upper_scaled.exponent <= gamma); + + /* + * Any value between lower and upper bound would be represented + * in binary as the double val originated from. The bounds were + * however scaled by an imprecise power of 10 (error less than + * 1 ulp) so the scaled bounds have an error of less than 1 ulp. + * Conservatively round the lower bound up and the upper bound + * down by 1 ulp just to be on the safe side. It avoids pronouncing + * produced decimal digits as correct if such a decimal number + * is close to the bounds to within 1 ulp. + */ + upper_scaled.significand -= 1; + lower_scaled.significand += 1; + + *bounds_delta = subtract(upper_scaled, lower_scaled); + *scaled_upper_bound = upper_scaled; +} + + +/** Rounds the last digit of buf so that it is closest to the converted number.*/ +static void round_last_digit(uint64_t rest, uint64_t w_dist, uint64_t delta, + uint64_t digit_val_diff, char *buf, int len) +{ + /* + * | <------- delta -------> | + * | | <---- w_dist ----> | + * | | | <- rest -> | + * | | | | + * | | ` buffer | + * | ` w ` upper + * ` lower + * + * delta = upper - lower .. conservative/safe interval + * w_dist = upper - w + * upper = "number represented by digits in buf" + rest + * + * Changing buf[len - 1] changes the value represented by buf + * by digit_val_diff * scaling, where scaling is shared by + * all parameters. + * + */ + + /* Current number in buf is greater than the double being converted */ + bool cur_greater_w = rest < w_dist; + /* Rounding down by one would keep buf in between bounds (in safe rng). */ + bool next_in_val_rng = cur_greater_w && (rest + digit_val_diff < delta); + /* Rounding down by one would bring buf closer to the processed number. */ + bool next_closer = next_in_val_rng + && (rest + digit_val_diff < w_dist || rest - w_dist < w_dist - rest); + + /* Of the shortest strings pick the one that is closest to the actual + floating point number. */ + while (next_closer) { + assert('0' < buf[len - 1]); + assert(0 < digit_val_diff); + + --buf[len - 1]; + rest += digit_val_diff; + + cur_greater_w = rest < w_dist; + next_in_val_rng = cur_greater_w && (rest + digit_val_diff < delta); + next_closer = next_in_val_rng + && (rest + digit_val_diff < w_dist || rest - w_dist < w_dist - rest); + } +} + + +/** Generates the shortest accurate decimal string representation. + * + * Outputs (mostly) the shortest accurate string representation + * for the number scaled_upper - val_dist. Numbers in the interval + * [scaled_upper - delta, scaled_upper] have the same binary + * floating point representation and will therefore share the + * shortest string representation (up to the rounding of the last + * digit to bring the shortest string also the closest to the + * actual number). + * + * @param scaled_upper Scaled upper bound of numbers that have the + * same binary representation as the converted number. + * Scaled by 10^-scale so that alpha <= exponent <= gamma. + * @param delta scaled_upper - delta is the lower bound of numbers + * that share the same binary representation in double. + * @param val_dist scaled_upper - val_dist is the number whose + * decimal string we're generating. + * @param scale Decimal scaling of the value to convert (ie scaled_upper). + * @param buf Buffer to store the string representation. Must be large + * enough to store all digits and a null terminator. At most + * MAX_DOUBLE_STR_LEN digits will be written (not counting + * the null terminator). + * @param buf_size Size of buf in bytes. + * @param dec_exponent Will be set to the decimal exponent of the number + * string in buf. + * + * @return Number of digits; negative on failure (eg buffer too small). + */ +static int gen_dec_digits(fp_num_t scaled_upper, fp_num_t delta, + fp_num_t val_dist, int scale, char *buf, size_t buf_size, int *dec_exponent) +{ + /* + * The integral part of scaled_upper is 5 to 32 bits long while + * the remaining fractional part is 59 to 32 bits long because: + * -59 == alpha <= scaled_upper.e <= gamma == -32 + * + * | <------- delta -------> | + * | | <--- val_dist ---> | + * | | |<- remainder ->| + * | | | | + * | | ` buffer | + * | ` val ` upper + * ` lower + * + */ + assert(scaled_upper.significand != 0); + assert(alpha <= scaled_upper.exponent && scaled_upper.exponent <= gamma); + assert(scaled_upper.exponent == delta.exponent); + assert(scaled_upper.exponent == val_dist.exponent); + assert(val_dist.significand <= delta.significand); + + /* We'll produce at least one digit and a null terminator. */ + if (buf_size < 2) { + return -1; + } + + /* one is number 1 encoded with the same exponent as scaled_upper */ + fp_num_t one; + one.significand = ((uint64_t) 1) << (-scaled_upper.exponent); + one.exponent = scaled_upper.exponent; + + /* + * Extract the integral part of scaled_upper. + * upper / one == upper >> -one.e + */ + uint32_t int_part = (uint32_t)(scaled_upper.significand >> (-one.exponent)); + + /* + * Fractional part of scaled_upper. + * upper % one == upper & (one.f - 1) + */ + uint64_t frac_part = scaled_upper.significand & (one.significand - 1); + + /* + * The integral part of upper has at least 5 bits (64 + alpha) and + * at most 32 bits (64 + gamma). The integral part has at most 10 + * decimal digits, so kappa <= 10. + */ + int kappa = 10; + uint32_t div = 1000000000; + size_t len = 0; + + /* Produce decimal digits for the integral part of upper. */ + while (kappa > 0) { + int digit = int_part / div; + int_part %= div; + + --kappa; + + /* Skip leading zeros. */ + if (digit != 0 || len != 0) { + /* Current length + new digit + null terminator <= buf_size */ + if (len + 2 <= buf_size) { + buf[len] = '0' + digit; + ++len; + } else { + return -1; + } + } + + /* + * Difference between the so far produced decimal number and upper + * is calculated as: remaining_int_part * one + frac_part + */ + uint64_t remainder = (((uint64_t)int_part) << -one.exponent) + frac_part; + + /* The produced decimal number would convert back to upper. */ + if (remainder <= delta.significand) { + assert(0 < len && len < buf_size); + *dec_exponent = kappa - scale; + buf[len] = '\0'; + + /* Of the shortest representations choose the numerically closest. */ + round_last_digit(remainder, val_dist.significand, delta.significand, + (uint64_t)div << (-one.exponent), buf, len); + return len; + } + + div /= 10; + } + + /* Generate decimal digits for the fractional part of upper. */ + do { + /* + * Does not overflow because at least 5 upper bits were + * taken by the integral part and are now unused in frac_part. + */ + frac_part *= 10; + delta.significand *= 10; + val_dist.significand *= 10; + + /* frac_part / one */ + int digit = (int)(frac_part >> (-one.exponent)); + + /* frac_part %= one */ + frac_part &= one.significand - 1; + + --kappa; + + /* Skip leading zeros. */ + if (digit == 0 && len == 0) { + continue; + } + + /* Current length + new digit + null terminator <= buf_size */ + if (len + 2 <= buf_size) { + buf[len] = '0' + digit; + ++len; + } else { + return -1; + } + } while (frac_part > delta.significand); + + assert(0 < len && len < buf_size); + + *dec_exponent = kappa - scale; + buf[len] = '\0'; + + /* Of the shortest representations choose the numerically closest one. */ + round_last_digit(frac_part, val_dist.significand, delta.significand, + one.significand, buf, len); + + return len; +} + +/** Produce a string for 0.0 */ +static int zero_to_str(char *buf, size_t buf_size, int *dec_exponent) +{ + if (2 <= buf_size) { + buf[0] = '0'; + buf[1] = '\0'; + *dec_exponent = 0; + return 1; + } else { + return -1; + } +} + + +/** Converts a non-special double into its shortest accurate string + * representation. + * + * Produces an accurate string representation, ie the string will + * convert back to the same binary double (eg via strtod). In the + * vast majority of cases (99%) the string will be the shortest such + * string that is also the closest to the value of any shortest + * string representations. Therefore, no trailing zeros are ever + * produced. + * + * Conceptually, the value is: buf * 10^dec_exponent + * + * Never outputs trailing zeros. + * + * @param ieee_val Binary double description to convert. Must be the product + * of extract_ieee_double and it must not be a special number. + * @param buf Buffer to store the string representation. Must be large + * enough to store all digits and a null terminator. At most + * MAX_DOUBLE_STR_LEN digits will be written (not counting + * the null terminator). + * @param buf_size Size of buf in bytes. + * @param dec_exponent Will be set to the decimal exponent of the number + * string in buf. + * + * @return The number of printed digits. A negative value indicates + * an error: buf too small (or ieee_val.is_special). + */ +int double_to_short_str(ieee_double_t ieee_val, char *buf, size_t buf_size, + int *dec_exponent) +{ + /* The whole computation assumes 64bit significand. */ + assert(sizeof(ieee_val.pos_val.significand) == sizeof(uint64_t)); + + if (ieee_val.is_special) { + return -1; + } + + /* Zero cannot be normalized. Handle it here. */ + if (0 == ieee_val.pos_val.significand) { + return zero_to_str(buf, buf_size, dec_exponent); + } + + fp_num_t scaled_upper_bound; + fp_num_t delta; + fp_num_t val_dist; + int scale; + + calc_scaled_bounds(ieee_val, &scaled_upper_bound, + &delta, &val_dist, &scale); + + int len = gen_dec_digits(scaled_upper_bound, delta, val_dist, scale, + buf, buf_size, dec_exponent); + + assert(len <= MAX_DOUBLE_STR_LEN); + return len; +} + +/** Generates a fixed number of decimal digits of w_scaled. + * + * double == w_scaled * 10^-scale, where alpha <= w_scaled.e <= gamma + * + * @param w_scaled Scaled number by 10^-scale so that + * alpha <= exponent <= gamma + * @param scale Decimal scaling of the value to convert (ie w_scaled). + * @param signif_d_cnt Maximum number of significant digits to output. + * Negative if as many as possible are requested. + * @param frac_d_cnt Maximum number of fractional digits to output. + * Negative if as many as possible are requested. + * Eg. if 2 then 1.234 -> "1.23"; if 2 then 3e-9 -> "0". + * @param buf Buffer to store the string representation. Must be large + * enough to store all digits and a null terminator. At most + * MAX_DOUBLE_STR_LEN digits will be written (not counting + * the null terminator). + * @param buf_size Size of buf in bytes. + * + * @return Number of digits; negative on failure (eg buffer too small). + */ +static int gen_fixed_dec_digits(fp_num_t w_scaled, int scale, int signif_d_cnt, + int frac_d_cnt, char *buf, size_t buf_size, int *dec_exponent) +{ + /* We'll produce at least one digit and a null terminator. */ + if (0 == signif_d_cnt || buf_size < 2) { + return -1; + } + + /* + * The integral part of w_scaled is 5 to 32 bits long while the + * remaining fractional part is 59 to 32 bits long because: + * -59 == alpha <= w_scaled.e <= gamma == -32 + * + * Therefore: + * | 5..32 bits | 32..59 bits | == w_scaled == w * 10^scale + * | int_part | frac_part | + * |0 0 .. 0 1|0 0 .. 0 0| == one == 1.0 + * | 0 |0 0 .. 0 1| == w_err == 1 * 2^w_scaled.e + */ + assert(alpha <= w_scaled.exponent && w_scaled.exponent <= gamma); + assert(0 != w_scaled.significand); + + /* + * Scaling the number being converted by 10^scale introduced + * an error of less that 1 ulp. The actual value of w_scaled + * could lie anywhere between w_scaled.signif +/- w_err. + * Scale the error locally as we scale the fractional part + * of w_scaled. + */ + uint64_t w_err = 1; + + /* one is number 1.0 encoded with the same exponent as w_scaled */ + fp_num_t one; + one.significand = ((uint64_t) 1) << (-w_scaled.exponent); + one.exponent = w_scaled.exponent; + + /* Extract the integral part of w_scaled. + w_scaled / one == w_scaled >> -one.e */ + uint32_t int_part = (uint32_t)(w_scaled.significand >> (-one.exponent)); + + /* Fractional part of w_scaled. + w_scaled % one == w_scaled & (one.f - 1) */ + uint64_t frac_part = w_scaled.significand & (one.significand - 1); + + size_t len = 0; + /* + * The integral part of w_scaled has at least 5 bits (64 + alpha = 5) + * and at most 32 bits (64 + gamma = 32). The integral part has + * at most 10 decimal digits, so kappa <= 10. + */ + int kappa = 10; + uint32_t div = 1000000000; + + int rem_signif_d_cnt = signif_d_cnt; + int rem_frac_d_cnt = + (frac_d_cnt >= 0) ? (kappa - scale + frac_d_cnt) : INT_MAX; + + /* Produce decimal digits for the integral part of w_scaled. */ + while (kappa > 0 && rem_signif_d_cnt != 0 && rem_frac_d_cnt > 0) { + int digit = int_part / div; + int_part %= div; + + div /= 10; + --kappa; + --rem_frac_d_cnt; + + /* Skip leading zeros. */ + if (digit == 0 && len == 0) { + continue; + } + + /* Current length + new digit + null terminator <= buf_size */ + if (len + 2 <= buf_size) { + buf[len] = '0' + digit; + ++len; + --rem_signif_d_cnt; + } else { + return -1; + } + } + + /* Generate decimal digits for the fractional part of w_scaled. */ + while (w_err <= frac_part && rem_signif_d_cnt != 0 && rem_frac_d_cnt > 0) { + /* + * Does not overflow because at least 5 upper bits were + * taken by the integral part and are now unused in frac_part. + */ + frac_part *= 10; + w_err *= 10; + + /* frac_part / one */ + int digit = (int)(frac_part >> (-one.exponent)); + + /* frac_part %= one */ + frac_part &= one.significand - 1; + + --kappa; + --rem_frac_d_cnt; + + /* Skip leading zeros. */ + if (digit == 0 && len == 0) { + continue; + } + + /* Current length + new digit + null terminator <= buf_size */ + if (len + 2 <= buf_size) { + buf[len] = '0' + digit; + ++len; + --rem_signif_d_cnt; + } else { + return -1; + } + }; + + assert(/* 0 <= len && */ len < buf_size); + + if (0 < len) { + *dec_exponent = kappa - scale; + assert(frac_d_cnt < 0 || -frac_d_cnt <= *dec_exponent); + } else { + /* + * The number of fractional digits was too limiting to produce + * any digits. + */ + assert(rem_frac_d_cnt <= 0 || w_scaled.significand == 0); + *dec_exponent = 0; + buf[0] = '0'; + len = 1; + } + + if (len < buf_size) { + buf[len] = '\0'; + assert(signif_d_cnt < 0 || (int)len <= signif_d_cnt); + return len; + } else { + return -1; + } +} + + +/** Converts a non-special double into its string representation. + * + * Conceptually, the truncated double value is: buf * 10^dec_exponent + * + * Conversion errors are tracked, so all produced digits except the + * last one are accurate. Garbage digits are never produced. + * If the requested number of digits cannot be produced accurately + * due to conversion errors less digits are produced than requested + * and the last digit has an error of +/- 1 (so if '7' is the last + * converted digit it might have been converted to any of '6'..'8' + * had the conversion been completely precise). + * + * If no error occurs at least one digit is output. + * + * The conversion stops once the requested number of significant or + * fractional digits is reached or the conversion error is too large + * to generate any more digits (whichever happens first). + * + * Any digits following the first (most-significant) digit (this digit + * included) are counted as significant digits; eg: + * 1.4, 4 signif -> "1400" * 10^-3, ie 1.400 + * 1000.3, 1 signif -> "1" * 10^3 ie 1000 + * 0.003, 2 signif -> "30" * 10^-4 ie 0.003 + * 9.5 1 signif -> "9" * 10^0, ie 9 + * + * Any digits following the decimal point are counted as fractional digits. + * This includes the zeros that would appear between the decimal point + * and the first non-zero fractional digit. If fewer fractional digits + * are requested than would allow to place the most-significant digit + * a "0" is output. Eg: + * 1.4, 3 frac -> "1400" * 10^-3, ie 1.400 + * 12.34 4 frac -> "123400" * 10^-4, ie 12.3400 + * 3e-99 4 frac -> "0" * 10^0, ie 0 + * 0.009 2 frac -> "0" * 10^-2, ie 0 + * + * @param ieee_val Binary double description to convert. Must be the product + * of extract_ieee_double and it must not be a special number. + * @param signif_d_cnt Maximum number of significant digits to produce. + * The output is not rounded. + * Set to a negative value to generate as many digits + * as accurately possible. + * @param frac_d_cnt Maximum number of fractional digits to produce including + * any zeros immediately trailing the decimal point. + * The output is not rounded. + * Set to a negative value to generate as many digits + * as accurately possible. + * @param buf Buffer to store the string representation. Must be large + * enough to store all digits and a null terminator. At most + * MAX_DOUBLE_STR_LEN digits will be written (not counting + * the null terminator). + * @param buf_size Size of buf in bytes. + * @param dec_exponent Set to the decimal exponent of the number string + * in buf. + * + * @return The number of output digits. A negative value indicates + * an error: buf too small (or ieee_val.is_special, or + * signif_d_cnt == 0). + */ +int double_to_fixed_str(ieee_double_t ieee_val, int signif_d_cnt, + int frac_d_cnt, char *buf, size_t buf_size, int *dec_exponent) +{ + /* The whole computation assumes 64bit significand. */ + assert(sizeof(ieee_val.pos_val.significand) == sizeof(uint64_t)); + + if (ieee_val.is_special) { + return -1; + } + + /* Zero cannot be normalized. Handle it here. */ + if (0 == ieee_val.pos_val.significand) { + return zero_to_str(buf, buf_size, dec_exponent); + } + + /* Normalize and scale. */ + fp_num_t w = normalize(ieee_val.pos_val); + + int lower_bin_exp = alpha - w.exponent - significand_width; + + int scale; + fp_num_t scaling_power_of_10; + + get_power_of_ten(lower_bin_exp, &scaling_power_of_10, &scale); + + fp_num_t w_scaled = multiply(w, scaling_power_of_10); + + /* Produce decimal digits from the scaled number. */ + int len = gen_fixed_dec_digits(w_scaled, scale, signif_d_cnt, frac_d_cnt, + buf, buf_size, dec_exponent); + + assert(len <= MAX_DOUBLE_STR_LEN); + return len; +} + Index: uspace/lib/c/generic/ieee_double.c =================================================================== --- uspace/lib/c/generic/ieee_double.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) +++ uspace/lib/c/generic/ieee_double.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -0,0 +1,113 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include + +#include + +/** Returns an easily processible description of the double val. + */ +ieee_double_t extract_ieee_double(double val) +{ + const uint64_t significand_mask = 0xfffffffffffffULL; + const uint64_t exponent_mask = 0x7ff0000000000000ULL; + const int exponent_shift = 64 - 11 - 1; + const uint64_t sign_mask = 0x8000000000000000ULL; + + const int special_exponent = 0x7ff; + const int denormal_exponent = 0; + const uint64_t hidden_bit = (1ULL << 52); + const int exponent_bias = 1075; + + assert(sizeof(val) == sizeof(uint64_t)); + + union { + uint64_t num; + double val; + } bits; + + bits.val = val; + + /* + * Extract the binary ieee representation of the double. + * Relies on integers having the same endianness as doubles. + */ + uint64_t num = bits.num; + + ieee_double_t ret; + + /* Determine the sign. */ + ret.is_negative = ((num & sign_mask) != 0); + + /* Extract the exponent. */ + int raw_exponent = (num & exponent_mask) >> exponent_shift; + + /* The extracted raw significand may not contain the hidden bit */ + uint64_t raw_significand = num & significand_mask; + + ret.is_special = (raw_exponent == special_exponent); + + /* NaN or infinity */ + if (ret.is_special) { + ret.is_infinity = (raw_significand == 0); + ret.is_nan = (raw_significand != 0); + + /* These are not valid for special numbers but init them anyway. */ + ret.is_denormal = true; + ret.is_accuracy_step = false; + ret.pos_val.significand = 0; + ret.pos_val.exponent = 0; + } else { + ret.is_infinity = false; + ret.is_nan = false; + + ret.is_denormal = (raw_exponent == denormal_exponent); + + /* Denormal or zero. */ + if (ret.is_denormal) { + ret.pos_val.significand = raw_significand; + ret.pos_val.exponent = 1 - exponent_bias; + ret.is_accuracy_step = false; + } else { + ret.pos_val.significand = raw_significand + hidden_bit; + ret.pos_val.exponent = raw_exponent - exponent_bias; + + /* The predecessor is closer to val than the successor + * if val is a normal value of the form 2^k (hence + * raw_significand == 0) with the only exception being + * the smallest normal (raw_exponent == 1). The smallest + * normal's predecessor is the largest denormal and denormals + * do not get an extra bit of precision because their exponent + * stays the same (ie it does not decrease from k to k-1). + */ + ret.is_accuracy_step = (raw_significand == 0) && (raw_exponent != 1); + } + } + + return ret; +} + Index: uspace/lib/c/generic/io/printf_core.c =================================================================== --- uspace/lib/c/generic/io/printf_core.c (revision f0da685587e02cc34984e5f558211f7bc44af1aa) +++ uspace/lib/c/generic/io/printf_core.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -42,8 +42,16 @@ #include #include +#include +#include +#include +#include + /** show prefixes 0x or 0 */ #define __PRINTF_FLAG_PREFIX 0x00000001 +/** show the decimal point even if no fractional digits present */ +#define __PRINTF_FLAG_DECIMALPT 0x00000001 + /** signed / unsigned number */ #define __PRINTF_FLAG_SIGNED 0x00000002 @@ -66,4 +74,8 @@ /** number has - sign */ #define __PRINTF_FLAG_NEGATIVE 0x00000100 + +/** don't print trailing zeros in the fractional part */ +#define __PRINTF_FLAG_NOFRACZEROS 0x00000200 + /** @@ -110,4 +122,47 @@ static const char invalch = U_SPECIAL; + + +/** Unformatted double number string representation. */ +typedef struct { + /** Buffer with len digits, no sign or leading zeros. */ + char *str; + /** Number of digits in str. */ + int len; + /** Decimal exponent, ie number = str * 10^dec_exp */ + int dec_exp; + /** True if negative. */ + bool neg; +} double_str_t; + + + +/** Returns the sign character or 0 if no sign should be printed. */ +static int get_sign_char(bool negative, uint32_t flags) +{ + if (negative) { + return '-'; + } else if (flags & __PRINTF_FLAG_SHOWPLUS) { + return '+'; + } else if (flags & __PRINTF_FLAG_SPACESIGN) { + return ' '; + } else { + return 0; + } +} + +/** Prints count times character ch. */ +static int print_padding(char ch, int count, printf_spec_t *ps) +{ + for (int i = 0; i < count; ++i) { + if (ps->str_write(&ch, 1, ps->data) < 0) { + return -1; + } + } + + return count; +} + + /** Print one or more characters without adding newline. * @@ -281,6 +336,7 @@ return printf_putstr(nullstr, ps); - /* Print leading spaces. */ size_t strw = str_length(str); + + /* Precision unspecified - print everything. */ if ((precision == 0) || (precision > strw)) precision = strw; @@ -329,6 +385,7 @@ return printf_putstr(nullstr, ps); - /* Print leading spaces. */ size_t strw = wstr_length(str); + + /* Precision not specified - print everything. */ if ((precision == 0) || (precision > strw)) precision = strw; @@ -377,4 +434,9 @@ uint32_t flags, printf_spec_t *ps) { + /* Precision not specified. */ + if (precision < 0) { + precision = 0; + } + const char *digits; if (flags & __PRINTF_FLAG_BIGCHARS) @@ -525,4 +587,656 @@ return ((int) counter); +} + +/** Prints a special double (ie NaN, infinity) padded to width characters. */ +static int print_special(ieee_double_t val, int width, uint32_t flags, + printf_spec_t *ps) +{ + assert(val.is_special); + + char sign = get_sign_char(val.is_negative, flags); + + const int str_len = 3; + const char *str; + + if (flags & __PRINTF_FLAG_BIGCHARS) { + str = val.is_infinity ? "INF" : "NAN"; + } else { + str = val.is_infinity ? "inf" : "nan"; + } + + int padding_len = max(0, width - ((sign ? 1 : 0) + str_len)); + + int counter = 0; + int ret; + + /* Leading padding. */ + if (!(flags & __PRINTF_FLAG_LEFTALIGNED)) { + if ((ret = print_padding(' ', padding_len, ps)) < 0) + return -1; + + counter += ret; + } + + if (sign) { + if ((ret = ps->str_write(&sign, 1, ps->data)) < 0) + return -1; + + counter += ret; + } + + if ((ret = ps->str_write(str, str_len, ps->data)) < 0) + return -1; + + counter += ret; + + + /* Trailing padding. */ + if (flags & __PRINTF_FLAG_LEFTALIGNED) { + if ((ret = print_padding(' ', padding_len, ps)) < 0) + return -1; + + counter += ret; + } + + return counter; +} + +/** Trims trailing zeros but leaves a single "0" intact. */ +static void fp_trim_trailing_zeros(char *buf, int *len, int *dec_exp) +{ + /* Cut the zero off by adjusting the exponent. */ + while (2 <= *len && '0' == buf[*len - 1]) { + --*len; + ++*dec_exp; + } +} + +/** Textually round up the last digit thereby eliminating it. */ +static void fp_round_up(char *buf, int *len, int *dec_exp) +{ + assert(1 <= *len); + + char *last_digit = &buf[*len - 1]; + + int carry = ('5' <= *last_digit); + + /* Cut the digit off by adjusting the exponent. */ + --*len; + ++*dec_exp; + --last_digit; + + if (carry) { + /* Skip all the digits to cut off/round to zero. */ + while (buf <= last_digit && '9' == *last_digit) { + --last_digit; + } + + /* last_digit points to the last digit to round but not '9' */ + if (buf <= last_digit) { + *last_digit += 1; + int new_len = last_digit - buf + 1; + *dec_exp += *len - new_len; + *len = new_len; + } else { + /* All len digits rounded to 0. */ + buf[0] = '1'; + *dec_exp += *len; + *len = 1; + } + } else { + /* The only digit was rounded to 0. */ + if (last_digit < buf) { + buf[0] = '0'; + *dec_exp = 0; + *len = 1; + } + } +} + + +/** Format and print the double string repressentation according + * to the %f specifier. + */ +static int print_double_str_fixed(double_str_t *val_str, int precision, int width, + uint32_t flags, printf_spec_t *ps) +{ + int len = val_str->len; + char *buf = val_str->str; + int dec_exp = val_str->dec_exp; + + assert(0 < len); + assert(0 <= precision); + assert(0 <= dec_exp || -dec_exp <= precision); + + /* Number of integral digits to print (at least leading zero). */ + int int_len = max(1, len + dec_exp); + + char sign = get_sign_char(val_str->neg, flags); + + /* Fractional portion lengths. */ + int last_frac_signif_pos = max(0, -dec_exp); + int leading_frac_zeros = max(0, last_frac_signif_pos - len); + int signif_frac_figs = min(last_frac_signif_pos, len); + int trailing_frac_zeros = precision - last_frac_signif_pos; + char *buf_frac = buf + len - signif_frac_figs; + + if (flags & __PRINTF_FLAG_NOFRACZEROS) { + trailing_frac_zeros = 0; + } + + int frac_len = leading_frac_zeros + signif_frac_figs + trailing_frac_zeros; + + bool has_decimal_pt = (0 < frac_len) || (flags & __PRINTF_FLAG_DECIMALPT); + + /* Number of non-padding chars to print. */ + int num_len = (sign ? 1 : 0) + int_len + (has_decimal_pt ? 1 : 0) + frac_len; + + int padding_len = max(0, width - num_len); + int ret = 0; + int counter = 0; + + /* Leading padding and sign. */ + + if (!(flags & (__PRINTF_FLAG_LEFTALIGNED | __PRINTF_FLAG_ZEROPADDED))) { + if ((ret = print_padding(' ', padding_len, ps)) < 0) + return -1; + + counter += ret; + } + + if (sign) { + if ((ret = ps->str_write(&sign, 1, ps->data)) < 0) + return -1; + + counter += ret; + } + + if (flags & __PRINTF_FLAG_ZEROPADDED) { + if ((ret = print_padding('0', padding_len, ps)) < 0) + return -1; + + counter += ret; + } + + /* Print the intergral part of the buffer. */ + + int buf_int_len = min(len, len + dec_exp); + + if (0 < buf_int_len) { + if ((ret = ps->str_write(buf, buf_int_len, ps->data)) < 0) + return -1; + + counter += ret; + + /* Print trailing zeros of the integral part of the number. */ + if ((ret = print_padding('0', int_len - buf_int_len, ps)) < 0) + return -1; + } else { + /* Single leading integer 0. */ + char ch = '0'; + if ((ret = ps->str_write(&ch, 1, ps->data)) < 0) + return -1; + } + + counter += ret; + + /* Print the decimal point and the fractional part. */ + if (has_decimal_pt) { + char ch = '.'; + + if ((ret = ps->str_write(&ch, 1, ps->data)) < 0) + return -1; + + counter += ret; + + /* Print leading zeros of the fractional part of the number. */ + if ((ret = print_padding('0', leading_frac_zeros, ps)) < 0) + return -1; + + counter += ret; + + /* Print significant digits of the fractional part of the number. */ + if (0 < signif_frac_figs) { + if ((ret = ps->str_write(buf_frac, signif_frac_figs, ps->data)) < 0) + return -1; + + counter += ret; + } + + /* Print trailing zeros of the fractional part of the number. */ + if ((ret = print_padding('0', trailing_frac_zeros, ps)) < 0) + return -1; + + counter += ret; + } + + /* Trailing padding. */ + if (flags & __PRINTF_FLAG_LEFTALIGNED) { + if ((ret = print_padding(' ', padding_len, ps)) < 0) + return -1; + + counter += ret; + } + + return counter; +} + + +/** Convert, format and print a double according to the %f specifier. + * + * @param g Double to print. + * @param precision Number of fractional digits to print. If 0 no + * decimal point will be printed unless the flag + * __PRINTF_FLAG_DECIMALPT is specified. + * @param width Minimum number of characters to display. Pads + * with '0' or ' ' depending on the set flags; + * @param flags Printf flags. + * @param ps Printing functions. + * + * @return The number of characters printed; negative on failure. + */ +static int print_double_fixed(double g, int precision, int width, uint32_t flags, + printf_spec_t *ps) +{ + if (flags & __PRINTF_FLAG_LEFTALIGNED) { + flags &= ~__PRINTF_FLAG_ZEROPADDED; + } + + if (flags & __PRINTF_FLAG_DECIMALPT) { + flags &= ~__PRINTF_FLAG_NOFRACZEROS; + } + + ieee_double_t val = extract_ieee_double(g); + + if (val.is_special) { + return print_special(val, width, flags, ps); + } + + char buf[MAX_DOUBLE_STR_BUF_SIZE]; + const size_t buf_size = MAX_DOUBLE_STR_BUF_SIZE; + double_str_t val_str; + + val_str.str = buf; + val_str.neg = val.is_negative; + + if (0 <= precision) { + /* + * Request one more digit so we can round the result. The last + * digit it returns may have an error of at most +/- 1. + */ + val_str.len = double_to_fixed_str(val, -1, precision + 1, buf, buf_size, + &val_str.dec_exp); + + /* + * Round using the last digit to produce precision fractional digits. + * If less than precision+1 fractional digits were output the last + * digit is definitely inaccurate so also round to get rid of it. + */ + fp_round_up(buf, &val_str.len, &val_str.dec_exp); + + /* Rounding could have introduced trailing zeros. */ + if (flags & __PRINTF_FLAG_NOFRACZEROS) { + fp_trim_trailing_zeros(buf, &val_str.len, &val_str.dec_exp); + } + } else { + /* Let the implementation figure out the proper precision. */ + val_str.len = double_to_short_str(val, buf, buf_size, &val_str.dec_exp); + + /* Precision needed for the last significant digit. */ + precision = max(0, -val_str.dec_exp); + } + + return print_double_str_fixed(&val_str, precision, width, flags, ps); +} + +/** Prints the decimal exponent part of a %e specifier formatted number. */ +static int print_exponent(int exp_val, uint32_t flags, printf_spec_t *ps) +{ + int counter = 0; + int ret; + + char exp_ch = (flags & __PRINTF_FLAG_BIGCHARS) ? 'E' : 'e'; + + if ((ret = ps->str_write(&exp_ch, 1, ps->data)) < 0) + return -1; + + counter += ret; + + char exp_sign = (exp_val < 0) ? '-' : '+'; + + if ((ret = ps->str_write(&exp_sign, 1, ps->data)) < 0) + return -1; + + counter += ret; + + /* Print the exponent. */ + exp_val = abs(exp_val); + + char exp_str[4] = { 0 }; + + exp_str[0] = '0' + exp_val / 100; + exp_str[1] = '0' + (exp_val % 100) / 10 ; + exp_str[2] = '0' + (exp_val % 10); + + int exp_len = (exp_str[0] == '0') ? 2 : 3; + const char *exp_str_start = &exp_str[3] - exp_len; + + if ((ret = ps->str_write(exp_str_start, exp_len, ps->data)) < 0) + return -1; + + counter += ret; + + return counter; +} + + +/** Format and print the double string repressentation according + * to the %e specifier. + */ +static int print_double_str_scient(double_str_t *val_str, int precision, + int width, uint32_t flags, printf_spec_t *ps) +{ + int len = val_str->len; + int dec_exp = val_str->dec_exp; + char *buf = val_str->str; + + assert(0 < len); + + char sign = get_sign_char(val_str->neg, flags); + bool has_decimal_pt = (0 < precision) || (flags & __PRINTF_FLAG_DECIMALPT); + int dec_pt_len = has_decimal_pt ? 1 : 0; + + /* Fractional part lengths. */ + int signif_frac_figs = len - 1; + int trailing_frac_zeros = precision - signif_frac_figs; + + if (flags & __PRINTF_FLAG_NOFRACZEROS) { + trailing_frac_zeros = 0; + } + + int frac_len = signif_frac_figs + trailing_frac_zeros; + + int exp_val = dec_exp + len - 1; + /* Account for exponent sign and 'e'; minimum 2 digits. */ + int exp_len = 2 + (abs(exp_val) >= 100 ? 3 : 2); + + /* Number of non-padding chars to print. */ + int num_len = (sign ? 1 : 0) + 1 + dec_pt_len + frac_len + exp_len; + + int padding_len = max(0, width - num_len); + int ret = 0; + int counter = 0; + + if (!(flags & (__PRINTF_FLAG_LEFTALIGNED | __PRINTF_FLAG_ZEROPADDED))) { + if ((ret = print_padding(' ', padding_len, ps)) < 0) + return -1; + + counter += ret; + } + + if (sign) { + if ((ret = ps->str_write(&sign, 1, ps->data)) < 0) + return -1; + + counter += ret; + } + + if (flags & __PRINTF_FLAG_ZEROPADDED) { + if ((ret = print_padding('0', padding_len, ps)) < 0) + return -1; + + counter += ret; + } + + /* Single leading integer. */ + if ((ret = ps->str_write(buf, 1, ps->data)) < 0) + return -1; + + counter += ret; + + /* Print the decimal point and the fractional part. */ + if (has_decimal_pt) { + char ch = '.'; + + if ((ret = ps->str_write(&ch, 1, ps->data)) < 0) + return -1; + + counter += ret; + + /* Print significant digits of the fractional part of the number. */ + if (0 < signif_frac_figs) { + if ((ret = ps->str_write(buf + 1, signif_frac_figs, ps->data)) < 0) + return -1; + + counter += ret; + } + + /* Print trailing zeros of the fractional part of the number. */ + if ((ret = print_padding('0', trailing_frac_zeros, ps)) < 0) + return -1; + + counter += ret; + } + + /* Print the exponent. */ + if ((ret = print_exponent(exp_val, flags, ps)) < 0) + return -1; + + counter += ret; + + if (flags & __PRINTF_FLAG_LEFTALIGNED) { + if ((ret = print_padding(' ', padding_len, ps)) < 0) + return -1; + + counter += ret; + } + + return counter; +} + + +/** Convert, format and print a double according to the %e specifier. + * + * Note that if g is large, the output may be huge (3e100 prints + * with at least 100 digits). + * + * %e style: [-]d.dddde+dd + * left-justified: [-]d.dddde+dd[space_pad] + * right-justified: [space_pad][-][zero_pad]d.dddde+dd + * + * @param g Double to print. + * @param precision Number of fractional digits to print, ie + * precision + 1 significant digits to display. If 0 no + * decimal point will be printed unless the flag + * __PRINTF_FLAG_DECIMALPT is specified. If negative + * the shortest accurate number will be printed. + * @param width Minimum number of characters to display. Pads + * with '0' or ' ' depending on the set flags; + * @param flags Printf flags. + * @param ps Printing functions. + * + * @return The number of characters printed; negative on failure. + */ +static int print_double_scientific(double g, int precision, int width, + uint32_t flags, printf_spec_t *ps) +{ + if (flags & __PRINTF_FLAG_LEFTALIGNED) { + flags &= ~__PRINTF_FLAG_ZEROPADDED; + } + + ieee_double_t val = extract_ieee_double(g); + + if (val.is_special) { + return print_special(val, width, flags, ps); + } + + char buf[MAX_DOUBLE_STR_BUF_SIZE]; + const size_t buf_size = MAX_DOUBLE_STR_BUF_SIZE; + double_str_t val_str; + + val_str.str = buf; + val_str.neg = val.is_negative; + + if (0 <= precision) { + /* + * Request one more digit (in addition to the leading integer) + * so we can round the result. The last digit it returns may + * have an error of at most +/- 1. + */ + val_str.len = double_to_fixed_str(val, precision + 2, -1, buf, buf_size, + &val_str.dec_exp); + + /* + * Round the extra digit to produce precision+1 significant digits. + * If less than precision+2 significant digits were returned the last + * digit is definitely inaccurate so also round to get rid of it. + */ + fp_round_up(buf, &val_str.len, &val_str.dec_exp); + + /* Rounding could have introduced trailing zeros. */ + if (flags & __PRINTF_FLAG_NOFRACZEROS) { + fp_trim_trailing_zeros(buf, &val_str.len, &val_str.dec_exp); + } + } else { + /* Let the implementation figure out the proper precision. */ + val_str.len = double_to_short_str(val, buf, buf_size, &val_str.dec_exp); + + /* Use all produced digits. */ + precision = val_str.len - 1; + } + + return print_double_str_scient(&val_str, precision, width, flags, ps); +} + + +/** Convert, format and print a double according to the %g specifier. + * + * %g style chooses between %f and %e. + * + * @param g Double to print. + * @param precision Number of significant digits to display; excluding + * any leading zeros from this count. If negative + * the shortest accurate number will be printed. + * @param width Minimum number of characters to display. Pads + * with '0' or ' ' depending on the set flags; + * @param flags Printf flags. + * @param ps Printing functions. + * + * @return The number of characters printed; negative on failure. + */ +static int print_double_generic(double g, int precision, int width, + uint32_t flags, printf_spec_t *ps) +{ + ieee_double_t val = extract_ieee_double(g); + + if (val.is_special) { + return print_special(val, width, flags, ps); + } + + char buf[MAX_DOUBLE_STR_BUF_SIZE]; + const size_t buf_size = MAX_DOUBLE_STR_BUF_SIZE; + int dec_exp; + int len; + + /* Honor the user requested number of significant digits. */ + if (0 <= precision) { + /* + * Do a quick and dirty conversion of a single digit to determine + * the decimal exponent. + */ + len = double_to_fixed_str(val, 1, -1, buf, buf_size, &dec_exp); + assert(0 < len); + + precision = max(1, precision); + + if (-4 <= dec_exp && dec_exp < precision) { + precision = precision - (dec_exp + 1); + return print_double_fixed(g, precision, width, + flags | __PRINTF_FLAG_NOFRACZEROS, ps); + } else { + --precision; + return print_double_scientific(g, precision, width, + flags | __PRINTF_FLAG_NOFRACZEROS, ps); + } + } else { + /* Convert to get the decimal exponent and digit count.*/ + len = double_to_short_str(val, buf, buf_size, &dec_exp); + assert(0 < len); + + if (flags & __PRINTF_FLAG_LEFTALIGNED) { + flags &= ~__PRINTF_FLAG_ZEROPADDED; + } + + double_str_t val_str; + val_str.str = buf; + val_str.len = len; + val_str.neg = val.is_negative; + val_str.dec_exp = dec_exp; + + int first_digit_pos = len + dec_exp; + int last_digit_pos = dec_exp; + + /* The whole number (15 digits max) fits between dec places 15 .. -6 */ + if (len <= 15 && -6 <= last_digit_pos && first_digit_pos <= 15) { + /* Precision needed for the last significant digit. */ + precision = max(0, -val_str.dec_exp); + return print_double_str_fixed(&val_str, precision, width, flags, ps); + } else { + /* Use all produced digits. */ + precision = val_str.len - 1; + return print_double_str_scient(&val_str, precision, width, flags, ps); + } + } +} + + +/** Convert, format and print a double according to the specifier. + * + * Depending on the specifier it prints the double using the styles + * %g, %f or %e by means of print_double_generic(), print_double_fixed(), + * print_double_scientific(). + * + * @param g Double to print. + * @param spec Specifier of the style to print in; one of: 'g','G','f','F', + * 'e','E'. + * @param precision Number of fractional digits to display. If negative + * the shortest accurate number will be printed for style %g; + * negative precision defaults to 6 for styles %f, %e. + * @param width Minimum number of characters to display. Pads + * with '0' or ' ' depending on the set flags; + * @param flags Printf flags. + * @param ps Printing functions. + * + * @return The number of characters printed; negative on failure. + */ +static int print_double(double g, char spec, int precision, int width, + uint32_t flags, printf_spec_t *ps) +{ + switch (spec) { + case 'F': + flags |= __PRINTF_FLAG_BIGCHARS; + /* Fall through.*/ + case 'f': + precision = (precision < 0) ? 6 : precision; + return print_double_fixed(g, precision, width, flags, ps); + + case 'E': + flags |= __PRINTF_FLAG_BIGCHARS; + /* Fall through.*/ + case 'e': + precision = (precision < 0) ? 6 : precision; + return print_double_scientific(g, precision, width, flags, ps); + + case 'G': + flags |= __PRINTF_FLAG_BIGCHARS; + /* Fall through.*/ + case 'g': + return print_double_generic(g, precision, width, flags, ps); + + default: + assert(false); + return -1; + } } @@ -656,4 +1370,5 @@ case '#': flags |= __PRINTF_FLAG_PREFIX; + flags |= __PRINTF_FLAG_DECIMALPT; break; case '-': @@ -701,9 +1416,10 @@ /* Precision and '*' operator */ - int precision = 0; + int precision = -1; if (uc == '.') { i = nxt; uc = str_decode(fmt, &nxt, STR_NO_LIMIT); if (isdigit(uc)) { + precision = 0; while (true) { precision *= 10; @@ -723,6 +1439,6 @@ precision = (int) va_arg(ap, int); if (precision < 0) { - /* Ignore negative precision */ - precision = 0; + /* Ignore negative precision - use default instead */ + precision = -1; } } @@ -774,4 +1490,6 @@ */ case 's': + precision = max(0, precision); + if (qualifier == PrintfQualifierLong) retval = print_wstr(va_arg(ap, wchar_t *), width, precision, flags, ps); @@ -797,4 +1515,25 @@ goto out; }; + + counter += retval; + j = nxt; + goto next_char; + + /* + * Floating point values + */ + case 'G': + case 'g': + case 'F': + case 'f': + case 'E': + case 'e': + retval = print_double(va_arg(ap, double), uc, precision, + width, flags, ps); + + if (retval < 0) { + counter = -counter; + goto out; + } counter += retval; Index: uspace/lib/c/generic/power_of_ten.c =================================================================== --- uspace/lib/c/generic/power_of_ten.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) +++ uspace/lib/c/generic/power_of_ten.c (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -0,0 +1,186 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#include "private/power_of_ten.h" + +#include +#include + +/** Precomputed normalized rounded-up powers of 10^k. + * + * The powers were computed using arbitrary precision arithmetic + * and rounded up to the top 64 significant bits. Therefore: + * 10^dec_exp == significand * 2^bin_exp +/- 0.5 ulp error + * + * The smallest interval of binary exponents computed by hand + * is [-1083, 987]. Add 200 (exponent change > 3 * 64 bits) + * to both bounds just to be on the safe side; ie [-1283, 1187]. + */ +static struct { + uint64_t significand; + int16_t bin_exp; + int16_t dec_exp; +} fp_powers_of_10[] = { + { 0xb8e1cbc28bef0b69ULL, -1286, -368 }, + { 0x89bf722840327f82ULL, -1259, -360 }, + { 0xcd42a11346f34f7dULL, -1233, -352 }, + { 0x98ee4a22ecf3188cULL, -1206, -344 }, + { 0xe3e27a444d8d98b8ULL, -1180, -336 }, + { 0xa9c98d8ccb009506ULL, -1153, -328 }, + { 0xfd00b897478238d1ULL, -1127, -320 }, + { 0xbc807527ed3e12bdULL, -1100, -312 }, + { 0x8c71dcd9ba0b4926ULL, -1073, -304 }, + { 0xd1476e2c07286faaULL, -1047, -296 }, + { 0x9becce62836ac577ULL, -1020, -288 }, + { 0xe858ad248f5c22caULL, -994, -280 }, + { 0xad1c8eab5ee43b67ULL, -967, -272 }, + { 0x80fa687f881c7f8eULL, -940, -264 }, + { 0xc0314325637a193aULL, -914, -256 }, + { 0x8f31cc0937ae58d3ULL, -887, -248 }, + { 0xd5605fcdcf32e1d7ULL, -861, -240 }, + { 0x9efa548d26e5a6e2ULL, -834, -232 }, + { 0xece53cec4a314ebeULL, -808, -224 }, + { 0xb080392cc4349dedULL, -781, -216 }, + { 0x8380dea93da4bc60ULL, -754, -208 }, + { 0xc3f490aa77bd60fdULL, -728, -200 }, + { 0x91ff83775423cc06ULL, -701, -192 }, + { 0xd98ddaee19068c76ULL, -675, -184 }, + { 0xa21727db38cb0030ULL, -648, -176 }, + { 0xf18899b1bc3f8ca2ULL, -622, -168 }, + { 0xb3f4e093db73a093ULL, -595, -160 }, + { 0x8613fd0145877586ULL, -568, -152 }, + { 0xc7caba6e7c5382c9ULL, -542, -144 }, + { 0x94db483840b717f0ULL, -515, -136 }, + { 0xddd0467c64bce4a1ULL, -489, -128 }, + { 0xa54394fe1eedb8ffULL, -462, -120 }, + { 0xf64335bcf065d37dULL, -436, -112 }, + { 0xb77ada0617e3bbcbULL, -409, -104 }, + { 0x88b402f7fd75539bULL, -382, -96 }, + { 0xcbb41ef979346bcaULL, -356, -88 }, + { 0x97c560ba6b0919a6ULL, -329, -80 }, + { 0xe2280b6c20dd5232ULL, -303, -72 }, + { 0xa87fea27a539e9a5ULL, -276, -64 }, + { 0xfb158592be068d2fULL, -250, -56 }, + { 0xbb127c53b17ec159ULL, -223, -48 }, + { 0x8b61313bbabce2c6ULL, -196, -40 }, + { 0xcfb11ead453994baULL, -170, -32 }, + { 0x9abe14cd44753b53ULL, -143, -24 }, + { 0xe69594bec44de15bULL, -117, -16 }, + { 0xabcc77118461cefdULL, -90, -8 }, + { 0x8000000000000000ULL, -63, 0 }, + { 0xbebc200000000000ULL, -37, 8 }, + { 0x8e1bc9bf04000000ULL, -10, 16 }, + { 0xd3c21bcecceda100ULL, 16, 24 }, + { 0x9dc5ada82b70b59eULL, 43, 32 }, + { 0xeb194f8e1ae525fdULL, 69, 40 }, + { 0xaf298d050e4395d7ULL, 96, 48 }, + { 0x82818f1281ed44a0ULL, 123, 56 }, + { 0xc2781f49ffcfa6d5ULL, 149, 64 }, + { 0x90e40fbeea1d3a4bULL, 176, 72 }, + { 0xd7e77a8f87daf7fcULL, 202, 80 }, + { 0xa0dc75f1778e39d6ULL, 229, 88 }, + { 0xefb3ab16c59b14a3ULL, 255, 96 }, + { 0xb2977ee300c50fe7ULL, 282, 104 }, + { 0x850fadc09923329eULL, 309, 112 }, + { 0xc646d63501a1511eULL, 335, 120 }, + { 0x93ba47c980e98ce0ULL, 362, 128 }, + { 0xdc21a1171d42645dULL, 388, 136 }, + { 0xa402b9c5a8d3a6e7ULL, 415, 144 }, + { 0xf46518c2ef5b8cd1ULL, 441, 152 }, + { 0xb616a12b7fe617aaULL, 468, 160 }, + { 0x87aa9aff79042287ULL, 495, 168 }, + { 0xca28a291859bbf93ULL, 521, 176 }, + { 0x969eb7c47859e744ULL, 548, 184 }, + { 0xe070f78d3927556bULL, 574, 192 }, + { 0xa738c6bebb12d16dULL, 601, 200 }, + { 0xf92e0c3537826146ULL, 627, 208 }, + { 0xb9a74a0637ce2ee1ULL, 654, 216 }, + { 0x8a5296ffe33cc930ULL, 681, 224 }, + { 0xce1de40642e3f4b9ULL, 707, 232 }, + { 0x9991a6f3d6bf1766ULL, 734, 240 }, + { 0xe4d5e82392a40515ULL, 760, 248 }, + { 0xaa7eebfb9df9de8eULL, 787, 256 }, + { 0xfe0efb53d30dd4d8ULL, 813, 264 }, + { 0xbd49d14aa79dbc82ULL, 840, 272 }, + { 0x8d07e33455637eb3ULL, 867, 280 }, + { 0xd226fc195c6a2f8cULL, 893, 288 }, + { 0x9c935e00d4b9d8d2ULL, 920, 296 }, + { 0xe950df20247c83fdULL, 946, 304 }, + { 0xadd57a27d29339f6ULL, 973, 312 }, + { 0x81842f29f2cce376ULL, 1000, 320 }, + { 0xc0fe908895cf3b44ULL, 1026, 328 }, + { 0x8fcac257558ee4e6ULL, 1053, 336 }, + { 0xd6444e39c3db9b0aULL, 1079, 344 }, + { 0x9fa42700db900ad2ULL, 1106, 352 }, + { 0xede24ae798ec8284ULL, 1132, 360 }, + { 0xb13cc3832ef0c9acULL, 1159, 368 }, + { 0x840d57e2899d945fULL, 1186, 376 } +}; + + +/** + * Returns the smallest precomputed power of 10 such that + * binary_exp <= power_of_10.bin_exp + * where + * 10^decimal_exp = power_of_10.significand * 2^bin_exp + * with an error of 0.5 ulp in the significand. + */ +void get_power_of_ten(int binary_exp, fp_num_t *power_of_10, int *decimal_exp) +{ + const int powers_count = sizeof(fp_powers_of_10) / sizeof(fp_powers_of_10[0]); + const int min_bin_exp = fp_powers_of_10[0].bin_exp; + const int max_bin_exp = fp_powers_of_10[powers_count - 1].bin_exp; + const int max_bin_exp_diff = 27; + + assert(min_bin_exp <= binary_exp && binary_exp <= max_bin_exp); + + /* + * Binary exponent difference between adjacent powers of 10 + * is lg(10^8) = 26.575. The starting search index seed_idx + * undershoots the actual position by less than 1.6%, ie it + * skips 26.575/27 = 98.4% of all the smaller powers. This + * translates to at most three extra tests. + */ + int seed_idx = (binary_exp - min_bin_exp) / max_bin_exp_diff; + + assert(fp_powers_of_10[seed_idx].bin_exp < binary_exp); + + for (int i = seed_idx; i < powers_count; ++i) { + /* Found the smallest power of 10 with bin_exp >= binary_exp. */ + if (binary_exp <= fp_powers_of_10[i].bin_exp) { + assert(fp_powers_of_10[i].bin_exp <= binary_exp + max_bin_exp_diff); + + power_of_10->significand = fp_powers_of_10[i].significand; + power_of_10->exponent = fp_powers_of_10[i].bin_exp; + *decimal_exp = fp_powers_of_10[i].dec_exp; + return; + } + } + + assert(false); +} + Index: uspace/lib/c/generic/private/power_of_ten.h =================================================================== --- uspace/lib/c/generic/private/power_of_ten.h (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) +++ uspace/lib/c/generic/private/power_of_ten.h (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -0,0 +1,39 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef POWER_OF_TEN_H_ +#define POWER_OF_TEN_H_ + +/* Fwd decl. */ +struct fp_num_t_tag; + + +void get_power_of_ten(int binary_exp, struct fp_num_t_tag *power_of_10, + int *decimal_exp); + + +#endif Index: uspace/lib/c/include/double_to_str.h =================================================================== --- uspace/lib/c/include/double_to_str.h (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) +++ uspace/lib/c/include/double_to_str.h (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -0,0 +1,59 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef DOUBLE_TO_STR_H_ +#define DOUBLE_TO_STR_H_ + +#include + +/** Maximum number of digits double_to_*_str conversion functions produce. + * + * Both double_to_short_str and double_to_fixed_str generate digits out + * of a 64bit unsigned int number representation. The max number of + * of digits is therefore 20. Add 1 to help users who forget to reserve + * space for a null terminator. + */ +#define MAX_DOUBLE_STR_LEN (20 + 1) + +/** Maximum buffer size needed to store the output of double_to_*_str + * functions. + */ +#define MAX_DOUBLE_STR_BUF_SIZE 21 + + +/* Fwd decl.*/ +struct ieee_double_t_tag; + + +int double_to_short_str(struct ieee_double_t_tag val, char *buf, size_t buf_size, + int *dec_exponent); + +int double_to_fixed_str(struct ieee_double_t_tag ieee_val, int signif_d_cnt, + int frac_d_cnt, char *buf, size_t buf_size, int *dec_exponent); + + +#endif Index: uspace/lib/c/include/ieee_double.h =================================================================== --- uspace/lib/c/include/ieee_double.h (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) +++ uspace/lib/c/include/ieee_double.h (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -0,0 +1,71 @@ +/* + * Copyright (c) 2012 Adam Hraska + * All rights reserved. + * + * Redistribution and use in source and binary forms, with or without + * modification, are permitted provided that the following conditions + * are met: + * + * - Redistributions of source code must retain the above copyright + * notice, this list of conditions and the following disclaimer. + * - Redistributions in binary form must reproduce the above copyright + * notice, this list of conditions and the following disclaimer in the + * documentation and/or other materials provided with the distribution. + * - The name of the author may not be used to endorse or promote products + * derived from this software without specific prior written permission. + * + * THIS SOFTWARE IS PROVIDED BY THE AUTHOR ``AS IS'' AND ANY EXPRESS OR + * IMPLIED WARRANTIES, INCLUDING, BUT NOT LIMITED TO, THE IMPLIED WARRANTIES + * OF MERCHANTABILITY AND FITNESS FOR A PARTICULAR PURPOSE ARE DISCLAIMED. + * IN NO EVENT SHALL THE AUTHOR BE LIABLE FOR ANY DIRECT, INDIRECT, + * INCIDENTAL, SPECIAL, EXEMPLARY, OR CONSEQUENTIAL DAMAGES (INCLUDING, BUT + * NOT LIMITED TO, PROCUREMENT OF SUBSTITUTE GOODS OR SERVICES; LOSS OF USE, + * DATA, OR PROFITS; OR BUSINESS INTERRUPTION) HOWEVER CAUSED AND ON ANY + * THEORY OF LIABILITY, WHETHER IN CONTRACT, STRICT LIABILITY, OR TORT + * (INCLUDING NEGLIGENCE OR OTHERWISE) ARISING IN ANY WAY OUT OF THE USE OF + * THIS SOFTWARE, EVEN IF ADVISED OF THE POSSIBILITY OF SUCH DAMAGE. + */ +#ifndef IEEE_DOUBLE_H_ +#define IEEE_DOUBLE_H_ + +#include +#include + + +/** Represents a non-negative floating point number: significand * 2^exponent */ +typedef struct fp_num_t_tag { + /** Significand (aka mantissa). */ + uint64_t significand; + /** Binary exponent. */ + int exponent; +} fp_num_t; + + +/** Double number description according to IEEE 754. */ +typedef struct ieee_double_t_tag { + /** The number is a NaN or infinity. */ + bool is_special; + /** Not a number. */ + bool is_nan; + bool is_negative; + /** The number denoted infinity. */ + bool is_infinity; + /** The number could not be represented as a normalized double. */ + bool is_denormal; + /** + * The predecessor double is closer than the successor. This happens + * if a normal number is of the form 2^k and it is not the smallest + * normal number. + */ + bool is_accuracy_step; + /** + * If !is_special the double's value is: + * pos_val.significand * 2^pos_val.exponent + */ + fp_num_t pos_val; +} ieee_double_t; + + +ieee_double_t extract_ieee_double(double val); + +#endif Index: uspace/lib/c/include/macros.h =================================================================== --- uspace/lib/c/include/macros.h (revision f0da685587e02cc34984e5f558211f7bc44af1aa) +++ uspace/lib/c/include/macros.h (revision 34b92999226bf07be2f5361c23d768bda9cfc55e) @@ -38,4 +38,6 @@ #define min(a, b) ((a) < (b) ? (a) : (b)) #define max(a, b) ((a) > (b) ? (a) : (b)) +#define abs(a) ((a) >= 0 ? (a) : (-a)) + #define KiB2SIZE(kb) ((kb) << 10)