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