1 //! Bit fiddling on positive IEEE 754 floats. Negative numbers aren't and needn't be handled.
2 //! Normal floating point numbers have a canonical representation as (frac, exp) such that the
3 //! value is 2<sup>exp</sup> * (1 + sum(frac[N-i] / 2<sup>i</sup>)) where N is the number of bits.
4 //! Subnormals are slightly different and weird, but the same principle applies.
6 //! Here, however, we represent them as (sig, k) with f positive, such that the value is f *
7 //! 2<sup>e</sup>. Besides making the "hidden bit" explicit, this changes the exponent by the
8 //! so-called mantissa shift.
10 //! Put another way, normally floats are written as (1) but here they are written as (2):
12 //! 1. `1.101100...11 * 2^m`
13 //! 2. `1101100...11 * 2^n`
15 //! We call (1) the **fractional representation** and (2) the **integral representation**.
17 //! Many functions in this module only handle normal numbers. The dec2flt routines conservatively
18 //! take the universally-correct slow path (Algorithm M) for very small and very large numbers.
19 //! That algorithm needs only next_float() which does handle subnormals and zeros.
20 use cmp::Ordering::{Less, Equal, Greater};
21 use convert::{TryFrom, TryInto};
22 use ops::{Add, Mul, Div, Neg};
23 use fmt::{Debug, LowerExp};
24 use num::diy_float::Fp;
25 use num::FpCategory::{Infinite, Zero, Subnormal, Normal, Nan};
27 use num::dec2flt::num::{self, Big};
28 use num::dec2flt::table;
30 #[derive(Copy, Clone, Debug)]
37 pub fn new(sig: u64, k: i16) -> Self {
42 /// A helper trait to avoid duplicating basically all the conversion code for `f32` and `f64`.
44 /// See the parent module's doc comment for why this is necessary.
46 /// Should **never ever** be implemented for other types or be used outside the dec2flt module.
59 /// Type used by `to_bits` and `from_bits`.
60 type Bits: Add<Output = Self::Bits> + From<u8> + TryFrom<u64>;
62 /// Performs a raw transmutation to an integer.
63 fn to_bits(self) -> Self::Bits;
65 /// Performs a raw transmutation from an integer.
66 fn from_bits(v: Self::Bits) -> Self;
68 /// Returns the category that this number falls into.
69 fn classify(self) -> FpCategory;
71 /// Returns the mantissa, exponent and sign as integers.
72 fn integer_decode(self) -> (u64, i16, i8);
74 /// Decodes the float.
75 fn unpack(self) -> Unpacked;
77 /// Casts from a small integer that can be represented exactly. Panic if the integer can't be
78 /// represented, the other code in this module makes sure to never let that happen.
79 fn from_int(x: u64) -> Self;
81 /// Gets the value 10<sup>e</sup> from a pre-computed table.
82 /// Panics for `e >= CEIL_LOG5_OF_MAX_SIG`.
83 fn short_fast_pow10(e: usize) -> Self;
85 /// What the name says. It's easier to hard code than juggling intrinsics and
86 /// hoping LLVM constant folds it.
87 const CEIL_LOG5_OF_MAX_SIG: i16;
89 // A conservative bound on the decimal digits of inputs that can't produce overflow or zero or
90 /// subnormals. Probably the decimal exponent of the maximum normal value, hence the name.
91 const MAX_NORMAL_DIGITS: usize;
93 /// When the most significant decimal digit has a place value greater than this, the number
94 /// is certainly rounded to infinity.
95 const INF_CUTOFF: i64;
97 /// When the most significant decimal digit has a place value less than this, the number
98 /// is certainly rounded to zero.
99 const ZERO_CUTOFF: i64;
101 /// The number of bits in the exponent.
104 /// The number of bits in the significand, *including* the hidden bit.
107 /// The number of bits in the significand, *excluding* the hidden bit.
108 const EXPLICIT_SIG_BITS: u8;
110 /// The maximum legal exponent in fractional representation.
113 /// The minimum legal exponent in fractional representation, excluding subnormals.
116 /// `MAX_EXP` for integral representation, i.e., with the shift applied.
117 const MAX_EXP_INT: i16;
119 /// `MAX_EXP` encoded (i.e., with offset bias)
120 const MAX_ENCODED_EXP: i16;
122 /// `MIN_EXP` for integral representation, i.e., with the shift applied.
123 const MIN_EXP_INT: i16;
125 /// The maximum normalized significand in integral representation.
128 /// The minimal normalized significand in integral representation.
132 // Mostly a workaround for #34344.
133 macro_rules! other_constants {
135 const EXPLICIT_SIG_BITS: u8 = Self::SIG_BITS - 1;
136 const MAX_EXP: i16 = (1 << (Self::EXP_BITS - 1)) - 1;
137 const MIN_EXP: i16 = -Self::MAX_EXP + 1;
138 const MAX_EXP_INT: i16 = Self::MAX_EXP - (Self::SIG_BITS as i16 - 1);
139 const MAX_ENCODED_EXP: i16 = (1 << Self::EXP_BITS) - 1;
140 const MIN_EXP_INT: i16 = Self::MIN_EXP - (Self::SIG_BITS as i16 - 1);
141 const MAX_SIG: u64 = (1 << Self::SIG_BITS) - 1;
142 const MIN_SIG: u64 = 1 << (Self::SIG_BITS - 1);
144 const INFINITY: Self = $crate::$type::INFINITY;
145 const NAN: Self = $crate::$type::NAN;
146 const ZERO: Self = 0.0;
150 impl RawFloat for f32 {
153 const SIG_BITS: u8 = 24;
154 const EXP_BITS: u8 = 8;
155 const CEIL_LOG5_OF_MAX_SIG: i16 = 11;
156 const MAX_NORMAL_DIGITS: usize = 35;
157 const INF_CUTOFF: i64 = 40;
158 const ZERO_CUTOFF: i64 = -48;
159 other_constants!(f32);
161 /// Returns the mantissa, exponent and sign as integers.
162 fn integer_decode(self) -> (u64, i16, i8) {
163 let bits = self.to_bits();
164 let sign: i8 = if bits >> 31 == 0 { 1 } else { -1 };
165 let mut exponent: i16 = ((bits >> 23) & 0xff) as i16;
166 let mantissa = if exponent == 0 {
167 (bits & 0x7fffff) << 1
169 (bits & 0x7fffff) | 0x800000
171 // Exponent bias + mantissa shift
172 exponent -= 127 + 23;
173 (mantissa as u64, exponent, sign)
176 fn unpack(self) -> Unpacked {
177 let (sig, exp, _sig) = self.integer_decode();
178 Unpacked::new(sig, exp)
181 fn from_int(x: u64) -> f32 {
182 // rkruppe is uncertain whether `as` rounds correctly on all platforms.
183 debug_assert!(x as f32 == fp_to_float(Fp { f: x, e: 0 }));
187 fn short_fast_pow10(e: usize) -> Self {
188 table::F32_SHORT_POWERS[e]
191 fn classify(self) -> FpCategory { self.classify() }
192 fn to_bits(self) -> Self::Bits { self.to_bits() }
193 fn from_bits(v: Self::Bits) -> Self { Self::from_bits(v) }
197 impl RawFloat for f64 {
200 const SIG_BITS: u8 = 53;
201 const EXP_BITS: u8 = 11;
202 const CEIL_LOG5_OF_MAX_SIG: i16 = 23;
203 const MAX_NORMAL_DIGITS: usize = 305;
204 const INF_CUTOFF: i64 = 310;
205 const ZERO_CUTOFF: i64 = -326;
206 other_constants!(f64);
208 /// Returns the mantissa, exponent and sign as integers.
209 fn integer_decode(self) -> (u64, i16, i8) {
210 let bits = self.to_bits();
211 let sign: i8 = if bits >> 63 == 0 { 1 } else { -1 };
212 let mut exponent: i16 = ((bits >> 52) & 0x7ff) as i16;
213 let mantissa = if exponent == 0 {
214 (bits & 0xfffffffffffff) << 1
216 (bits & 0xfffffffffffff) | 0x10000000000000
218 // Exponent bias + mantissa shift
219 exponent -= 1023 + 52;
220 (mantissa, exponent, sign)
223 fn unpack(self) -> Unpacked {
224 let (sig, exp, _sig) = self.integer_decode();
225 Unpacked::new(sig, exp)
228 fn from_int(x: u64) -> f64 {
229 // rkruppe is uncertain whether `as` rounds correctly on all platforms.
230 debug_assert!(x as f64 == fp_to_float(Fp { f: x, e: 0 }));
234 fn short_fast_pow10(e: usize) -> Self {
235 table::F64_SHORT_POWERS[e]
238 fn classify(self) -> FpCategory { self.classify() }
239 fn to_bits(self) -> Self::Bits { self.to_bits() }
240 fn from_bits(v: Self::Bits) -> Self { Self::from_bits(v) }
243 /// Converts an `Fp` to the closest machine float type.
244 /// Does not handle subnormal results.
245 pub fn fp_to_float<T: RawFloat>(x: Fp) -> T {
246 let x = x.normalize();
247 // x.f is 64 bit, so x.e has a mantissa shift of 63
250 panic!("fp_to_float: exponent {} too large", e)
251 } else if e > T::MIN_EXP {
252 encode_normal(round_normal::<T>(x))
254 panic!("fp_to_float: exponent {} too small", e)
258 /// Round the 64-bit significand to T::SIG_BITS bits with half-to-even.
259 /// Does not handle exponent overflow.
260 pub fn round_normal<T: RawFloat>(x: Fp) -> Unpacked {
261 let excess = 64 - T::SIG_BITS as i16;
262 let half: u64 = 1 << (excess - 1);
263 let (q, rem) = (x.f >> excess, x.f & ((1 << excess) - 1));
264 assert_eq!(q << excess | rem, x.f);
265 // Adjust mantissa shift
266 let k = x.e + excess;
269 } else if rem == half && (q % 2) == 0 {
271 } else if q == T::MAX_SIG {
272 Unpacked::new(T::MIN_SIG, k + 1)
274 Unpacked::new(q + 1, k)
278 /// Inverse of `RawFloat::unpack()` for normalized numbers.
279 /// Panics if the significand or exponent are not valid for normalized numbers.
280 pub fn encode_normal<T: RawFloat>(x: Unpacked) -> T {
281 debug_assert!(T::MIN_SIG <= x.sig && x.sig <= T::MAX_SIG,
282 "encode_normal: significand not normalized");
283 // Remove the hidden bit
284 let sig_enc = x.sig & !(1 << T::EXPLICIT_SIG_BITS);
285 // Adjust the exponent for exponent bias and mantissa shift
286 let k_enc = x.k + T::MAX_EXP + T::EXPLICIT_SIG_BITS as i16;
287 debug_assert!(k_enc != 0 && k_enc < T::MAX_ENCODED_EXP,
288 "encode_normal: exponent out of range");
289 // Leave sign bit at 0 ("+"), our numbers are all positive
290 let bits = (k_enc as u64) << T::EXPLICIT_SIG_BITS | sig_enc;
291 T::from_bits(bits.try_into().unwrap_or_else(|_| unreachable!()))
294 /// Construct a subnormal. A mantissa of 0 is allowed and constructs zero.
295 pub fn encode_subnormal<T: RawFloat>(significand: u64) -> T {
296 assert!(significand < T::MIN_SIG, "encode_subnormal: not actually subnormal");
297 // Encoded exponent is 0, the sign bit is 0, so we just have to reinterpret the bits.
298 T::from_bits(significand.try_into().unwrap_or_else(|_| unreachable!()))
301 /// Approximate a bignum with an Fp. Rounds within 0.5 ULP with half-to-even.
302 pub fn big_to_fp(f: &Big) -> Fp {
303 let end = f.bit_length();
304 assert!(end != 0, "big_to_fp: unexpectedly, input is zero");
305 let start = end.saturating_sub(64);
306 let leading = num::get_bits(f, start, end);
307 // We cut off all bits prior to the index `start`, i.e., we effectively right-shift by
308 // an amount of `start`, so this is also the exponent we need.
309 let e = start as i16;
310 let rounded_down = Fp { f: leading, e }.normalize();
311 // Round (half-to-even) depending on the truncated bits.
312 match num::compare_with_half_ulp(f, start) {
313 Less => rounded_down,
314 Equal if leading % 2 == 0 => rounded_down,
315 Equal | Greater => match leading.checked_add(1) {
316 Some(f) => Fp { f, e }.normalize(),
317 None => Fp { f: 1 << 63, e: e + 1 },
322 /// Finds the largest floating point number strictly smaller than the argument.
323 /// Does not handle subnormals, zero, or exponent underflow.
324 pub fn prev_float<T: RawFloat>(x: T) -> T {
326 Infinite => panic!("prev_float: argument is infinite"),
327 Nan => panic!("prev_float: argument is NaN"),
328 Subnormal => panic!("prev_float: argument is subnormal"),
329 Zero => panic!("prev_float: argument is zero"),
331 let Unpacked { sig, k } = x.unpack();
332 if sig == T::MIN_SIG {
333 encode_normal(Unpacked::new(T::MAX_SIG, k - 1))
335 encode_normal(Unpacked::new(sig - 1, k))
341 // Find the smallest floating point number strictly larger than the argument.
342 // This operation is saturating, i.e., next_float(inf) == inf.
343 // Unlike most code in this module, this function does handle zero, subnormals, and infinities.
344 // However, like all other code here, it does not deal with NaN and negative numbers.
345 pub fn next_float<T: RawFloat>(x: T) -> T {
347 Nan => panic!("next_float: argument is NaN"),
348 Infinite => T::INFINITY,
349 // This seems too good to be true, but it works.
350 // 0.0 is encoded as the all-zero word. Subnormals are 0x000m...m where m is the mantissa.
351 // In particular, the smallest subnormal is 0x0...01 and the largest is 0x000F...F.
352 // The smallest normal number is 0x0010...0, so this corner case works as well.
353 // If the increment overflows the mantissa, the carry bit increments the exponent as we
354 // want, and the mantissa bits become zero. Because of the hidden bit convention, this
355 // too is exactly what we want!
356 // Finally, f64::MAX + 1 = 7eff...f + 1 = 7ff0...0 = f64::INFINITY.
357 Zero | Subnormal | Normal => {
358 T::from_bits(x.to_bits() + T::Bits::from(1u8))