From 68bab3e56e7df618c093f5b93901f5319ef65997 Mon Sep 17 00:00:00 2001 From: Pyry Kontio Date: Sat, 23 May 2020 04:41:24 +0900 Subject: Add total_cmp to f32 and f64, plus tests --- src/libcore/num/f32.rs | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++ src/libcore/num/f64.rs | 73 ++++++++++++++++++++++++++++++++++++++++++++++++++ 2 files changed, 146 insertions(+) (limited to 'src/libcore') diff --git a/src/libcore/num/f32.rs b/src/libcore/num/f32.rs index 434569020d2..47f489c40ab 100644 --- a/src/libcore/num/f32.rs +++ b/src/libcore/num/f32.rs @@ -810,4 +810,77 @@ impl f32 { pub fn from_ne_bytes(bytes: [u8; 4]) -> Self { Self::from_bits(u32::from_ne_bytes(bytes)) } + + /// Returns an ordering between self and other values. + /// Unlike the standard partial comparison between floating point numbers, + /// this comparison always produces an ordering in accordance to + /// the totalOrder predicate as defined in IEEE 754 (2008 revision) + /// floating point standard. The values are ordered in following order: + /// - Negative quiet NaN + /// - Negative signaling NaN + /// - Negative infinity + /// - Negative numbers + /// - Negative subnormal numbers + /// - Negative zero + /// - Positive zero + /// - Positive subnormal numbers + /// - Positive numbers + /// - Positive infinity + /// - Positive signaling NaN + /// - Positive quiet NaN + /// + /// # Example + /// ``` + /// #![feature(total_cmp)] + /// struct GoodBoy { + /// name: String, + /// weight: f32, + /// } + /// + /// let mut bois = vec![ + /// GoodBoy { name: "Pucci".to_owned(), weight: 0.1 }, + /// GoodBoy { name: "Woofer".to_owned(), weight: 99.0 }, + /// GoodBoy { name: "Yapper".to_owned(), weight: 10.0 }, + /// GoodBoy { name: "Chonk".to_owned(), weight: f32::INFINITY }, + /// GoodBoy { name: "Abs. Unit".to_owned(), weight: f32::NAN }, + /// GoodBoy { name: "Floaty".to_owned(), weight: -5.0 }, + /// ]; + /// + /// bois.sort_by(|a, b| a.weight.total_cmp(&b.weight)); + /// # assert!(bois.into_iter().map(|b| b.weight) + /// # .zip([-5.0, 0.1, 10.0, 99.0, f32::INFINITY, f32::NAN].iter()) + /// # .all(|(a, b)| a.to_bits() == b.to_bits())) + /// ``` + #[must_use = "method returns a new number and does not mutate the original value"] + #[unstable(feature = "total_cmp", issue = "none")] + #[inline] + pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { + let mut left = self.to_bits() as i32; + let mut right = other.to_bits() as i32; + + // In case of negatives, flip all the bits expect the sign + // to achieve a similar layout as two's complement integers + // + // Why does this work? IEEE 754 floats consist of three fields: + // Sign bit, exponent and mantissa. The set of exponent and mantissa + // fields as a whole have the property that their bitwise order is + // equal to the numeric magnitude where the magnitude is defined. + // The magnitude is not normally defined on NaN values, but + // IEEE 754 totalOrder defines the NaN values also to follow the + // bitwise order. This leads to order explained in the doc comment. + // However, the representation of magnitude is the same for negative + // and positive numbers – only the sign bit is different. + // To easily compare the floats as signed integers, we need to + // flip the exponent and mantissa bits in case of negative numbers. + // We effectively convert the numbers to "two's complement" form. + if left < 0 { + // i32::MAX corresponds the bit pattern of "all ones expect for the sign bit" + left ^= i32::MAX + }; + if right < 0 { + right ^= i32::MAX + }; + + left.cmp(&right) + } } diff --git a/src/libcore/num/f64.rs b/src/libcore/num/f64.rs index 6476ddb4541..9c021808380 100644 --- a/src/libcore/num/f64.rs +++ b/src/libcore/num/f64.rs @@ -824,4 +824,77 @@ impl f64 { pub fn from_ne_bytes(bytes: [u8; 8]) -> Self { Self::from_bits(u64::from_ne_bytes(bytes)) } + + /// Returns an ordering between self and other values. + /// Unlike the standard partial comparison between floating point numbers, + /// this comparison always produces an ordering in accordance to + /// the totalOrder predicate as defined in IEEE 754 (2008 revision) + /// floating point standard. The values are ordered in following order: + /// - Negative quiet NaN + /// - Negative signaling NaN + /// - Negative infinity + /// - Negative numbers + /// - Negative subnormal numbers + /// - Negative zero + /// - Positive zero + /// - Positive subnormal numbers + /// - Positive numbers + /// - Positive infinity + /// - Positive signaling NaN + /// - Positive quiet NaN + /// + /// # Example + /// ``` + /// #![feature(total_cmp)] + /// struct GoodBoy { + /// name: String, + /// weight: f64, + /// } + /// + /// let mut bois = vec![ + /// GoodBoy { name: "Pucci".to_owned(), weight: 0.1 }, + /// GoodBoy { name: "Woofer".to_owned(), weight: 99.0 }, + /// GoodBoy { name: "Yapper".to_owned(), weight: 10.0 }, + /// GoodBoy { name: "Chonk".to_owned(), weight: f64::INFINITY }, + /// GoodBoy { name: "Abs. Unit".to_owned(), weight: f64::NAN }, + /// GoodBoy { name: "Floaty".to_owned(), weight: -5.0 }, + /// ]; + /// + /// bois.sort_by(|a, b| a.weight.total_cmp(&b.weight)); + /// # assert!(bois.into_iter().map(|b| b.weight) + /// # .zip([-5.0, 0.1, 10.0, 99.0, f64::INFINITY, f64::NAN].iter()) + /// # .all(|(a, b)| a.to_bits() == b.to_bits())) + /// ``` + #[must_use = "method returns a new number and does not mutate the original value"] + #[unstable(feature = "total_cmp", issue = "none")] + #[inline] + pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { + let mut left = self.to_bits() as i64; + let mut right = other.to_bits() as i64; + + // In case of negatives, flip all the bits expect the sign + // to achieve a similar layout as two's complement integers + // + // Why does this work? IEEE 754 floats consist of three fields: + // Sign bit, exponent and mantissa. The set of exponent and mantissa + // fields as a whole have the property that their bitwise order is + // equal to the numeric magnitude where the magnitude is defined. + // The magnitude is not normally defined on NaN values, but + // IEEE 754 totalOrder defines the NaN values also to follow the + // bitwise order. This leads to order explained in the doc comment. + // However, the representation of magnitude is the same for negative + // and positive numbers – only the sign bit is different. + // To easily compare the floats as signed integers, we need to + // flip the exponent and mantissa bits in case of negative numbers. + // We effectively convert the numbers to "two's complement" form. + if left < 0 { + // i64::MAX corresponds the bit pattern of "all ones expect for the sign bit" + left ^= i64::MAX + }; + if right < 0 { + right ^= i64::MAX + }; + + left.cmp(&right) + } } -- cgit 1.4.1-3-g733a5 From b6eec22dd49b74eda4257d0fd634fa179de9c2ec Mon Sep 17 00:00:00 2001 From: Pyry Kontio Date: Tue, 26 May 2020 02:44:55 +0900 Subject: Fix typo in src/libcore/num/f32.rs Co-authored-by: bluss --- src/libcore/num/f32.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libcore') diff --git a/src/libcore/num/f32.rs b/src/libcore/num/f32.rs index 47f489c40ab..56c77c8aea0 100644 --- a/src/libcore/num/f32.rs +++ b/src/libcore/num/f32.rs @@ -874,7 +874,7 @@ impl f32 { // flip the exponent and mantissa bits in case of negative numbers. // We effectively convert the numbers to "two's complement" form. if left < 0 { - // i32::MAX corresponds the bit pattern of "all ones expect for the sign bit" + // i32::MAX corresponds the bit pattern of "all ones except for the sign bit" left ^= i32::MAX }; if right < 0 { -- cgit 1.4.1-3-g733a5 From d6650e0d2b1027de341ba7f48937eab499fca3ee Mon Sep 17 00:00:00 2001 From: Pyry Kontio Date: Tue, 26 May 2020 02:45:06 +0900 Subject: Fix typo in src/libcore/num/f32.rs Co-authored-by: bluss --- src/libcore/num/f32.rs | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) (limited to 'src/libcore') diff --git a/src/libcore/num/f32.rs b/src/libcore/num/f32.rs index 56c77c8aea0..813e3077c3b 100644 --- a/src/libcore/num/f32.rs +++ b/src/libcore/num/f32.rs @@ -858,7 +858,7 @@ impl f32 { let mut left = self.to_bits() as i32; let mut right = other.to_bits() as i32; - // In case of negatives, flip all the bits expect the sign + // In case of negatives, flip all the bits except the sign // to achieve a similar layout as two's complement integers // // Why does this work? IEEE 754 floats consist of three fields: -- cgit 1.4.1-3-g733a5 From bd68de89b55d7f7d7adc41fdcd0a5bac1f805692 Mon Sep 17 00:00:00 2001 From: Pyry Kontio Date: Tue, 26 May 2020 02:48:56 +0900 Subject: remove unneeded and unidiomatic must_use --- src/libcore/num/f32.rs | 1 - src/libcore/num/f64.rs | 1 - 2 files changed, 2 deletions(-) (limited to 'src/libcore') diff --git a/src/libcore/num/f32.rs b/src/libcore/num/f32.rs index 813e3077c3b..36b70587385 100644 --- a/src/libcore/num/f32.rs +++ b/src/libcore/num/f32.rs @@ -851,7 +851,6 @@ impl f32 { /// # .zip([-5.0, 0.1, 10.0, 99.0, f32::INFINITY, f32::NAN].iter()) /// # .all(|(a, b)| a.to_bits() == b.to_bits())) /// ``` - #[must_use = "method returns a new number and does not mutate the original value"] #[unstable(feature = "total_cmp", issue = "none")] #[inline] pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { diff --git a/src/libcore/num/f64.rs b/src/libcore/num/f64.rs index 9c021808380..61711df3c65 100644 --- a/src/libcore/num/f64.rs +++ b/src/libcore/num/f64.rs @@ -865,7 +865,6 @@ impl f64 { /// # .zip([-5.0, 0.1, 10.0, 99.0, f64::INFINITY, f64::NAN].iter()) /// # .all(|(a, b)| a.to_bits() == b.to_bits())) /// ``` - #[must_use = "method returns a new number and does not mutate the original value"] #[unstable(feature = "total_cmp", issue = "none")] #[inline] pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { -- cgit 1.4.1-3-g733a5 From 6973fd716b51b01debf39edd8e43f0059be3d053 Mon Sep 17 00:00:00 2001 From: Pyry Kontio Date: Tue, 26 May 2020 04:50:53 +0900 Subject: Add bit twiddling --- src/libcore/num/f32.rs | 18 ++++++++++-------- src/libcore/num/f64.rs | 16 +++++++++------- 2 files changed, 19 insertions(+), 15 deletions(-) (limited to 'src/libcore') diff --git a/src/libcore/num/f32.rs b/src/libcore/num/f32.rs index 36b70587385..538cca712ca 100644 --- a/src/libcore/num/f32.rs +++ b/src/libcore/num/f32.rs @@ -857,7 +857,7 @@ impl f32 { let mut left = self.to_bits() as i32; let mut right = other.to_bits() as i32; - // In case of negatives, flip all the bits except the sign + // In case of negatives, flip all the bits expect the sign // to achieve a similar layout as two's complement integers // // Why does this work? IEEE 754 floats consist of three fields: @@ -872,13 +872,15 @@ impl f32 { // To easily compare the floats as signed integers, we need to // flip the exponent and mantissa bits in case of negative numbers. // We effectively convert the numbers to "two's complement" form. - if left < 0 { - // i32::MAX corresponds the bit pattern of "all ones except for the sign bit" - left ^= i32::MAX - }; - if right < 0 { - right ^= i32::MAX - }; + // + // To do the flipping, we construct a mask and XOR against it. + // We branchlessly calculate an "all-ones expect for the sign bit" + // mask from negative-signed values: right shifting sign-extends + // the integer, so we "fill" the mask with sign bits, and then + // convert to unsigned to push one more zero bit. + // On positive values, the mask is all zeros, so it's a no-op. + left ^= (((left >> 31) as u32) >> 1) as i32; + right ^= (((right >> 31) as u32) >> 1) as i32; left.cmp(&right) } diff --git a/src/libcore/num/f64.rs b/src/libcore/num/f64.rs index 61711df3c65..b3ebceb77c2 100644 --- a/src/libcore/num/f64.rs +++ b/src/libcore/num/f64.rs @@ -886,13 +886,15 @@ impl f64 { // To easily compare the floats as signed integers, we need to // flip the exponent and mantissa bits in case of negative numbers. // We effectively convert the numbers to "two's complement" form. - if left < 0 { - // i64::MAX corresponds the bit pattern of "all ones expect for the sign bit" - left ^= i64::MAX - }; - if right < 0 { - right ^= i64::MAX - }; + // + // To do the flipping, we construct a mask and XOR against it. + // We branchlessly calculate an "all-ones expect for the sign bit" + // mask from negative-signed values: right shifting sign-extends + // the integer, so we "fill" the mask with sign bits, and then + // convert to unsigned to push one more zero bit. + // On positive values, the mask is all zeros, so it's a no-op. + left ^= (((left >> 63) as u64) >> 1) as i64; + right ^= (((right >> 63) as u64) >> 1) as i64; left.cmp(&right) } -- cgit 1.4.1-3-g733a5 From 8bc31ff9055c50e9d882dd56909dc0b40c3a6453 Mon Sep 17 00:00:00 2001 From: Pyry Kontio Date: Tue, 26 May 2020 04:54:50 +0900 Subject: Fix the same typos again orz --- src/libcore/num/f32.rs | 4 ++-- src/libcore/num/f64.rs | 4 ++-- 2 files changed, 4 insertions(+), 4 deletions(-) (limited to 'src/libcore') diff --git a/src/libcore/num/f32.rs b/src/libcore/num/f32.rs index 538cca712ca..c54bfb27dfe 100644 --- a/src/libcore/num/f32.rs +++ b/src/libcore/num/f32.rs @@ -857,7 +857,7 @@ impl f32 { let mut left = self.to_bits() as i32; let mut right = other.to_bits() as i32; - // In case of negatives, flip all the bits expect the sign + // In case of negatives, flip all the bits except the sign // to achieve a similar layout as two's complement integers // // Why does this work? IEEE 754 floats consist of three fields: @@ -874,7 +874,7 @@ impl f32 { // We effectively convert the numbers to "two's complement" form. // // To do the flipping, we construct a mask and XOR against it. - // We branchlessly calculate an "all-ones expect for the sign bit" + // We branchlessly calculate an "all-ones except for the sign bit" // mask from negative-signed values: right shifting sign-extends // the integer, so we "fill" the mask with sign bits, and then // convert to unsigned to push one more zero bit. diff --git a/src/libcore/num/f64.rs b/src/libcore/num/f64.rs index b3ebceb77c2..18d5d720a05 100644 --- a/src/libcore/num/f64.rs +++ b/src/libcore/num/f64.rs @@ -871,7 +871,7 @@ impl f64 { let mut left = self.to_bits() as i64; let mut right = other.to_bits() as i64; - // In case of negatives, flip all the bits expect the sign + // In case of negatives, flip all the bits except the sign // to achieve a similar layout as two's complement integers // // Why does this work? IEEE 754 floats consist of three fields: @@ -888,7 +888,7 @@ impl f64 { // We effectively convert the numbers to "two's complement" form. // // To do the flipping, we construct a mask and XOR against it. - // We branchlessly calculate an "all-ones expect for the sign bit" + // We branchlessly calculate an "all-ones except for the sign bit" // mask from negative-signed values: right shifting sign-extends // the integer, so we "fill" the mask with sign bits, and then // convert to unsigned to push one more zero bit. -- cgit 1.4.1-3-g733a5 From 66da7350963edf3d40461e6f5bafde95974908fc Mon Sep 17 00:00:00 2001 From: Pyry Kontio Date: Tue, 26 May 2020 11:59:23 +0900 Subject: Add tracing issue for total_cmp --- src/libcore/num/f32.rs | 2 +- src/libcore/num/f64.rs | 2 +- 2 files changed, 2 insertions(+), 2 deletions(-) (limited to 'src/libcore') diff --git a/src/libcore/num/f32.rs b/src/libcore/num/f32.rs index c54bfb27dfe..6313de31ce4 100644 --- a/src/libcore/num/f32.rs +++ b/src/libcore/num/f32.rs @@ -851,7 +851,7 @@ impl f32 { /// # .zip([-5.0, 0.1, 10.0, 99.0, f32::INFINITY, f32::NAN].iter()) /// # .all(|(a, b)| a.to_bits() == b.to_bits())) /// ``` - #[unstable(feature = "total_cmp", issue = "none")] + #[unstable(feature = "total_cmp", issue = "72599")] #[inline] pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { let mut left = self.to_bits() as i32; diff --git a/src/libcore/num/f64.rs b/src/libcore/num/f64.rs index 18d5d720a05..d42e5392c58 100644 --- a/src/libcore/num/f64.rs +++ b/src/libcore/num/f64.rs @@ -865,7 +865,7 @@ impl f64 { /// # .zip([-5.0, 0.1, 10.0, 99.0, f64::INFINITY, f64::NAN].iter()) /// # .all(|(a, b)| a.to_bits() == b.to_bits())) /// ``` - #[unstable(feature = "total_cmp", issue = "none")] + #[unstable(feature = "total_cmp", issue = "72599")] #[inline] pub fn total_cmp(&self, other: &Self) -> crate::cmp::Ordering { let mut left = self.to_bits() as i64; -- cgit 1.4.1-3-g733a5