1/*
2 * Copyright 2017 Google Inc.
3 *
4 * Use of this source code is governed by a BSD-style license that can be
5 * found in the LICENSE file.
6 */
7
8#include "src/utils/SkFloatToDecimal.h"
9
10#include <cfloat>
11#include <climits>
12#include <cmath>
13
14#include "include/core/SkTypes.h"
15
16// returns `value * pow(base, e)`, assuming `e` is positive.
17static double pow_by_squaring(double value, double base, int e) {
18    // https://en.wikipedia.org/wiki/Exponentiation_by_squaring
19    SkASSERT(e > 0);
20    while (true) {
21        if (e & 1) {
22            value *= base;
23        }
24        e >>= 1;
25        if (0 == e) {
26            return value;
27        }
28        base *= base;
29    }
30}
31
32// Return pow(10.0, e), optimized for common cases.
33static double pow10(int e) {
34    switch (e) {
35        case 0:  return 1.0;  // common cases
36        case 1:  return 10.0;
37        case 2:  return 100.0;
38        case 3:  return 1e+03;
39        case 4:  return 1e+04;
40        case 5:  return 1e+05;
41        case 6:  return 1e+06;
42        case 7:  return 1e+07;
43        case 8:  return 1e+08;
44        case 9:  return 1e+09;
45        case 10: return 1e+10;
46        case 11: return 1e+11;
47        case 12: return 1e+12;
48        case 13: return 1e+13;
49        case 14: return 1e+14;
50        case 15: return 1e+15;
51        default:
52            if (e > 15) {
53                return pow_by_squaring(1e+15, 10.0, e - 15);
54            } else {
55                SkASSERT(e < 0);
56                return pow_by_squaring(1.0, 0.1, -e);
57            }
58    }
59}
60
61/** Write a string into output, including a terminating '\0' (for
62    unit testing).  Return strlen(output) (for SkWStream::write) The
63    resulting string will be in the form /[-]?([0-9]*.)?[0-9]+/ and
64    sscanf(output, "%f", &x) will return the original value iff the
65    value is finite. This function accepts all possible input values.
66
67    Motivation: "PDF does not support [numbers] in exponential format
68    (such as 6.02e23)."  Otherwise, this function would rely on a
69    sprintf-type function from the standard library. */
70unsigned SkFloatToDecimal(float value, char output[kMaximumSkFloatToDecimalLength]) {
71    /* The longest result is -FLT_MIN.
72       We serialize it as "-.0000000000000000000000000000000000000117549435"
73       which has 48 characters plus a terminating '\0'. */
74
75    static_assert(kMaximumSkFloatToDecimalLength == 49, "");
76    // 3 = '-', '.', and '\0' characters.
77    // 9 = number of significant digits
78    // abs(FLT_MIN_10_EXP) = number of zeros in FLT_MIN
79    static_assert(kMaximumSkFloatToDecimalLength == 3 + 9 - FLT_MIN_10_EXP, "");
80
81    /* section C.1 of the PDF1.4 spec (http://goo.gl/0SCswJ) says that
82       most PDF rasterizers will use fixed-point scalars that lack the
83       dynamic range of floats.  Even if this is the case, I want to
84       serialize these (uncommon) very small and very large scalar
85       values with enough precision to allow a floating-point
86       rasterizer to read them in with perfect accuracy.
87       Experimentally, rasterizers such as pdfium do seem to benefit
88       from this.  Rasterizers that rely on fixed-point scalars should
89       gracefully ignore these values that they can not parse. */
90    char* output_ptr = &output[0];
91    const char* const end = &output[kMaximumSkFloatToDecimalLength - 1];
92    // subtract one to leave space for '\0'.
93
94    /* This function is written to accept any possible input value,
95       including non-finite values such as INF and NAN.  In that case,
96       we ignore value-correctness and output a syntacticly-valid
97       number. */
98    if (value == INFINITY) {
99        value = FLT_MAX;  // nearest finite float.
100    }
101    if (value == -INFINITY) {
102        value = -FLT_MAX;  // nearest finite float.
103    }
104    if (!std::isfinite(value) || value == 0.0f) {
105        // NAN is unsupported in PDF.  Always output a valid number.
106        // Also catch zero here, as a special case.
107        *output_ptr++ = '0';
108        *output_ptr = '\0';
109        return static_cast<unsigned>(output_ptr - output);
110    }
111    if (value < 0.0) {
112        *output_ptr++ = '-';
113        value = -value;
114    }
115    SkASSERT(value >= 0.0f);
116
117    int binaryExponent;
118    (void)std::frexp(value, &binaryExponent);
119    static const double kLog2 = 0.3010299956639812;  // log10(2.0);
120    int decimalExponent = static_cast<int>(std::floor(kLog2 * binaryExponent));
121    int decimalShift = decimalExponent - 8;
122    double power = pow10(-decimalShift);
123    SkASSERT(value * power <= (double)INT_MAX);
124    int d = static_cast<int>(value * power + 0.5);
125    // SkASSERT(value == (float)(d * pow(10.0, decimalShift)));
126    SkASSERT(d <= 999999999);
127    if (d > 167772159) {  // floor(pow(10,1+log10(1<<24)))
128       // need one fewer decimal digits for 24-bit precision.
129       decimalShift = decimalExponent - 7;
130       // SkASSERT(power * 0.1 = pow10(-decimalShift));
131       // recalculate to get rounding right.
132       d = static_cast<int>(value * (power * 0.1) + 0.5);
133       SkASSERT(d <= 99999999);
134    }
135    while (d % 10 == 0) {
136        d /= 10;
137        ++decimalShift;
138    }
139    SkASSERT(d > 0);
140    // SkASSERT(value == (float)(d * pow(10.0, decimalShift)));
141    unsigned char buffer[9]; // decimal value buffer.
142    int bufferIndex = 0;
143    do {
144        buffer[bufferIndex++] = d % 10;
145        d /= 10;
146    } while (d != 0);
147    SkASSERT(bufferIndex <= (int)sizeof(buffer) && bufferIndex > 0);
148    if (decimalShift >= 0) {
149        do {
150            --bufferIndex;
151            *output_ptr++ = '0' + buffer[bufferIndex];
152        } while (bufferIndex);
153        for (int i = 0; i < decimalShift; ++i) {
154            *output_ptr++ = '0';
155        }
156    } else {
157        int placesBeforeDecimal = bufferIndex + decimalShift;
158        if (placesBeforeDecimal > 0) {
159            while (placesBeforeDecimal-- > 0) {
160                --bufferIndex;
161                *output_ptr++ = '0' + buffer[bufferIndex];
162            }
163            *output_ptr++ = '.';
164        } else {
165            *output_ptr++ = '.';
166            int placesAfterDecimal = -placesBeforeDecimal;
167            while (placesAfterDecimal-- > 0) {
168                *output_ptr++ = '0';
169            }
170        }
171        while (bufferIndex > 0) {
172            --bufferIndex;
173            *output_ptr++ = '0' + buffer[bufferIndex];
174            if (output_ptr == end) {
175                break;  // denormalized: don't need extra precision.
176                // Note: denormalized numbers will not have the same number of
177                // significantDigits, but do not need them to round-trip.
178            }
179        }
180    }
181    SkASSERT(output_ptr <= end);
182    *output_ptr = '\0';
183    return static_cast<unsigned>(output_ptr - output);
184}
185