SkFloatToDecimal.cpp 6.5 KB

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