dtoa.c 3.2 KB

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135136137138139140141142143144145146147148149150151152153154155156157158159160161
  1. /* Exact binary-double to decimal decomposition.
  2. *
  3. * A finite double is m * 2^e. For e >= 0 it is an integer; for e < 0 we
  4. * compute m * 5^(-e) / 10^(-e), so the decimal expansion is exact. The
  5. * result is a digit string plus the decimal-point position. stdio.c does
  6. * precision rounding and the %f/%e/%g layout from this representation. */
  7. #include <string.h>
  8. #include "dtoa.h"
  9. #define DTOA_LIMBS 128
  10. static void big_zero(unsigned int *a, int *n)
  11. {
  12. int i;
  13. for (i = 0; i < DTOA_LIMBS; i++)
  14. a[i] = 0;
  15. *n = 0;
  16. }
  17. static void big_set_u64(unsigned int *a, int *n, unsigned long long v)
  18. {
  19. big_zero(a, n);
  20. a[0] = (unsigned int)v;
  21. a[1] = (unsigned int)(v >> 32);
  22. *n = a[1] ? 2 : (a[0] ? 1 : 0);
  23. }
  24. static void big_shl(unsigned int *a, int *n, unsigned int bits)
  25. {
  26. unsigned int words = bits / 32u;
  27. unsigned int shift = bits % 32u;
  28. int i;
  29. if (words) {
  30. for (i = *n - 1; i >= 0; i--)
  31. a[i + words] = a[i];
  32. for (i = 0; i < (int)words; i++)
  33. a[i] = 0;
  34. *n += (int)words;
  35. }
  36. if (shift) {
  37. unsigned long long carry = 0;
  38. for (i = 0; i < *n; i++) {
  39. unsigned long long v =
  40. ((unsigned long long)a[i] << shift) | carry;
  41. a[i] = (unsigned int)v;
  42. carry = v >> 32;
  43. }
  44. if (carry && *n < DTOA_LIMBS)
  45. a[(*n)++] = (unsigned int)carry;
  46. }
  47. }
  48. static void big_mul5(unsigned int *a, int *n)
  49. {
  50. unsigned long long carry = 0;
  51. int i;
  52. for (i = 0; i < *n; i++) {
  53. unsigned long long v = (unsigned long long)a[i] * 5u + carry;
  54. a[i] = (unsigned int)v;
  55. carry = v >> 32;
  56. }
  57. if (carry && *n < DTOA_LIMBS)
  58. a[(*n)++] = (unsigned int)carry;
  59. }
  60. /* Divide by 10 in place; returns the remainder. */
  61. static unsigned int big_div10(unsigned int *a, int *n)
  62. {
  63. unsigned long long rem = 0;
  64. int i;
  65. for (i = *n - 1; i >= 0; i--) {
  66. unsigned long long cur = (rem << 32) | a[i];
  67. a[i] = (unsigned int)(cur / 10u);
  68. rem = cur % 10u;
  69. }
  70. while (*n > 0 && a[*n - 1] == 0)
  71. (*n)--;
  72. return (unsigned int)rem;
  73. }
  74. static int big_to_digits(unsigned int *a, int *n, char *digits, int *point)
  75. {
  76. char rev[LIBC_DTOA_MAX];
  77. int len = 0;
  78. int i;
  79. while (*n > 0) {
  80. unsigned int d = big_div10(a, n);
  81. if (len >= LIBC_DTOA_MAX)
  82. break;
  83. rev[len++] = (char)('0' + d);
  84. }
  85. if (len == 0) {
  86. digits[0] = '0';
  87. *point = 1;
  88. return 1;
  89. }
  90. for (i = 0; i < len; i++)
  91. digits[i] = rev[len - 1 - i];
  92. *point = len;
  93. return len;
  94. }
  95. int libc_dtoa(double value, struct libc_dtoa *out)
  96. {
  97. union {
  98. double d;
  99. unsigned long long u;
  100. } v;
  101. unsigned long long bits;
  102. unsigned int exp;
  103. unsigned long long mant;
  104. int e2;
  105. unsigned int a[DTOA_LIMBS];
  106. int n;
  107. int len;
  108. v.d = value;
  109. bits = v.u;
  110. out->neg = (int)(bits >> 63);
  111. exp = (unsigned int)((bits >> 52) & 0x7ffu);
  112. mant = bits & 0x000fffffffffffffULL;
  113. if (exp == 0x7ffu)
  114. return mant ? 2 : 1;
  115. if (exp == 0 && mant == 0) {
  116. out->digits[0] = '0';
  117. out->ndigits = 1;
  118. out->point = 1;
  119. return 0;
  120. }
  121. if (exp == 0) {
  122. e2 = -1074;
  123. } else {
  124. mant |= 1ULL << 52;
  125. e2 = (int)exp - 1023 - 52;
  126. }
  127. big_set_u64(a, &n, mant);
  128. if (e2 >= 0) {
  129. big_shl(a, &n, (unsigned int)e2);
  130. len = big_to_digits(a, &n, out->digits, &out->point);
  131. } else {
  132. int k = -e2;
  133. while (k-- > 0)
  134. big_mul5(a, &n);
  135. len = big_to_digits(a, &n, out->digits, &out->point);
  136. out->point = len + e2;
  137. }
  138. out->ndigits = len;
  139. return 0;
  140. }