1 | // Adapted from https://github.com/Alexhuszagh/rust-lexical. |
---|---|

2 | |

3 | //! Algorithms to efficiently convert strings to floats. |

4 | |

5 | use super::bhcomp::*; |

6 | use super::cached::*; |

7 | use super::errors::*; |

8 | use super::float::ExtendedFloat; |

9 | use super::num::*; |

10 | use super::small_powers::*; |

11 | |

12 | // FAST |

13 | // ---- |

14 | |

15 | /// Convert mantissa to exact value for a non-base2 power. |

16 | /// |

17 | /// Returns the resulting float and if the value can be represented exactly. |

18 | pub(crate) fn fast_path<F>(mantissa: u64, exponent: i32) -> Option<F> |

19 | where |

20 | F: Float, |

21 | { |

22 | // `mantissa >> (F::MANTISSA_SIZE+1) != 0` effectively checks if the |

23 | // value has a no bits above the hidden bit, which is what we want. |

24 | let (min_exp, max_exp) = F::exponent_limit(); |

25 | let shift_exp = F::mantissa_limit(); |

26 | let mantissa_size = F::MANTISSA_SIZE + 1; |

27 | if mantissa == 0 { |

28 | Some(F::ZERO) |

29 | } else if mantissa >> mantissa_size != 0 { |

30 | // Would require truncation of the mantissa. |

31 | None |

32 | } else if exponent == 0 { |

33 | // 0 exponent, same as value, exact representation. |

34 | let float = F::as_cast(mantissa); |

35 | Some(float) |

36 | } else if exponent >= min_exp && exponent <= max_exp { |

37 | // Value can be exactly represented, return the value. |

38 | // Do not use powi, since powi can incrementally introduce |

39 | // error. |

40 | let float = F::as_cast(mantissa); |

41 | Some(float.pow10(exponent)) |

42 | } else if exponent >= 0 && exponent <= max_exp + shift_exp { |

43 | // Check to see if we have a disguised fast-path, where the |

44 | // number of digits in the mantissa is very small, but and |

45 | // so digits can be shifted from the exponent to the mantissa. |

46 | // https://www.exploringbinary.com/fast-path-decimal-to-floating-point-conversion/ |

47 | let small_powers = POW10_64; |

48 | let shift = exponent - max_exp; |

49 | let power = small_powers[shift as usize]; |

50 | |

51 | // Compute the product of the power, if it overflows, |

52 | // prematurely return early, otherwise, if we didn't overshoot, |

53 | // we can get an exact value. |

54 | let value = match mantissa.checked_mul(power) { |

55 | None => return None, |

56 | Some(value) => value, |

57 | }; |

58 | if value >> mantissa_size != 0 { |

59 | None |

60 | } else { |

61 | // Use powi, since it's correct, and faster on |

62 | // the fast-path. |

63 | let float = F::as_cast(value); |

64 | Some(float.pow10(max_exp)) |

65 | } |

66 | } else { |

67 | // Cannot be exactly represented, exponent too small or too big, |

68 | // would require truncation. |

69 | None |

70 | } |

71 | } |

72 | |

73 | // MODERATE |

74 | // -------- |

75 | |

76 | /// Multiply the floating-point by the exponent. |

77 | /// |

78 | /// Multiply by pre-calculated powers of the base, modify the extended- |

79 | /// float, and return if new value and if the value can be represented |

80 | /// accurately. |

81 | fn multiply_exponent_extended<F>(fp: &mut ExtendedFloat, exponent: i32, truncated: bool) -> bool |

82 | where |

83 | F: Float, |

84 | { |

85 | let powers = ExtendedFloat::get_powers(); |

86 | let exponent = exponent.saturating_add(powers.bias); |

87 | let small_index = exponent % powers.step; |

88 | let large_index = exponent / powers.step; |

89 | if exponent < 0 { |

90 | // Guaranteed underflow (assign 0). |

91 | fp.mant = 0; |

92 | true |

93 | } else if large_index as usize >= powers.large.len() { |

94 | // Overflow (assign infinity) |

95 | fp.mant = 1 << 63; |

96 | fp.exp = 0x7FF; |

97 | true |

98 | } else { |

99 | // Within the valid exponent range, multiply by the large and small |

100 | // exponents and return the resulting value. |

101 | |

102 | // Track errors to as a factor of unit in last-precision. |

103 | let mut errors: u32 = 0; |

104 | if truncated { |

105 | errors += u64::error_halfscale(); |

106 | } |

107 | |

108 | // Multiply by the small power. |

109 | // Check if we can directly multiply by an integer, if not, |

110 | // use extended-precision multiplication. |

111 | match fp |

112 | .mant |

113 | .overflowing_mul(powers.get_small_int(small_index as usize)) |

114 | { |

115 | // Overflow, multiplication unsuccessful, go slow path. |

116 | (_, true) => { |

117 | fp.normalize(); |

118 | fp.imul(&powers.get_small(small_index as usize)); |

119 | errors += u64::error_halfscale(); |

120 | } |

121 | // No overflow, multiplication successful. |

122 | (mant, false) => { |

123 | fp.mant = mant; |

124 | fp.normalize(); |

125 | } |

126 | } |

127 | |

128 | // Multiply by the large power |

129 | fp.imul(&powers.get_large(large_index as usize)); |

130 | if errors > 0 { |

131 | errors += 1; |

132 | } |

133 | errors += u64::error_halfscale(); |

134 | |

135 | // Normalize the floating point (and the errors). |

136 | let shift = fp.normalize(); |

137 | errors <<= shift; |

138 | |

139 | u64::error_is_accurate::<F>(errors, fp) |

140 | } |

141 | } |

142 | |

143 | /// Create a precise native float using an intermediate extended-precision float. |

144 | /// |

145 | /// Return the float approximation and if the value can be accurately |

146 | /// represented with mantissa bits of precision. |

147 | #[inline] |

148 | pub(crate) fn moderate_path<F>( |

149 | mantissa: u64, |

150 | exponent: i32, |

151 | truncated: bool, |

152 | ) -> (ExtendedFloat, bool) |

153 | where |

154 | F: Float, |

155 | { |

156 | let mut fp = ExtendedFloat { |

157 | mant: mantissa, |

158 | exp: 0, |

159 | }; |

160 | let valid = multiply_exponent_extended::<F>(&mut fp, exponent, truncated); |

161 | (fp, valid) |

162 | } |

163 | |

164 | // FALLBACK |

165 | // -------- |

166 | |

167 | /// Fallback path when the fast path does not work. |

168 | /// |

169 | /// Uses the moderate path, if applicable, otherwise, uses the slow path |

170 | /// as required. |

171 | pub(crate) fn fallback_path<F>( |

172 | integer: &[u8], |

173 | fraction: &[u8], |

174 | mantissa: u64, |

175 | exponent: i32, |

176 | mantissa_exponent: i32, |

177 | truncated: bool, |

178 | ) -> F |

179 | where |

180 | F: Float, |

181 | { |

182 | // Moderate path (use an extended 80-bit representation). |

183 | let (fp, valid) = moderate_path::<F>(mantissa, mantissa_exponent, truncated); |

184 | if valid { |

185 | return fp.into_float::<F>(); |

186 | } |

187 | |

188 | // Slow path, fast path didn't work. |

189 | let b = fp.into_downward_float::<F>(); |

190 | if b.is_special() { |

191 | // We have a non-finite number, we get to leave early. |

192 | b |

193 | } else { |

194 | bhcomp(b, integer, fraction, exponent) |

195 | } |

196 | } |

197 |