Mercurial Mercurial > hedgewars / comparison
summary | shortlog | changelog | graph | tags | bookmarks | branches | files | changeset | file | latest | revisions | annotate | diff | comparison | raw | help
Find changesets by keywords (author, files, the commit message), revision number or hash, or revset expression.
rust/fpnum/src/lib.rs
branchtransitional_engine
changeset 16052 6633961698ad
parent 16050 624b74443b53
equal deleted inserted replaced
16051:a5eaeefa4ab3 16052:6633961698ad 
     1 use std::{cmp, ops};
 
     1 use std::{cmp, ops};
 
       
     2 use std::marker::PhantomData;
 
     2 use saturate::SaturatingInto;
 
     3 use saturate::SaturatingInto;
 
     3 
     4 
     4 const POSITIVE_MASK: u64 = 0x0000_0000_0000_0000;
 
     5 const POSITIVE_MASK: u64 = 0x0000_0000_0000_0000;
 
     5 const NEGATIVE_MASK: u64 = 0xFFFF_FFFF_FFFF_FFFF;
 
     6 const NEGATIVE_MASK: u64 = 0xFFFF_FFFF_FFFF_FFFF;
 
     6 
     7 
    11     } else {
 
    12     } else {
 
    12         POSITIVE_MASK
 
    13         POSITIVE_MASK
 
    13     }
 
    14     }
 
    14 }
 
    15 }
 
    15 
    16 
       
    17 struct FracBits<const N: u8>;
 
    16 #[derive(Clone, Debug, Copy)]
 
    18 #[derive(Clone, Debug, Copy)]
 
    17 pub struct FPNum {
 
    19 pub struct FixedPoint<const FRAC_BITS: u8> {
 
    18     sign_mask: u64,
 
    20     sign_mask: u64,
 
    19     value: u64,
 
    21     value: u64,
 
    20 }
 
    22     _marker: PhantomData<FracBits<FRAC_BITS>>,
 
    21 
    23 }
 
    22 impl FPNum {
 
    24 
       
    25 pub type FPNum = FixedPoint<20>;
 
       
    26 
       
    27 impl<const FRAC_BITS: u8> FixedPoint<FRAC_BITS> {
 
    23     #[inline]
 
    28     #[inline]
 
    24     pub fn new(numerator: i32, denominator: u32) -> Self {
 
    29     pub fn new(numerator: i32, denominator: u32) -> Self {
 
    25         FPNum::from(numerator) / denominator
 
    30         Self::from(numerator) / denominator
 
    26     }
 
    31     }
 
    27 
    32 
    28     #[inline]
 
    33     #[inline]
 
    29     pub fn signum(&self) -> i8 {
 
    34     pub fn signum(&self) -> i8 {
 
    30         (1u64 ^ self.sign_mask).wrapping_sub(self.sign_mask) as i8
 
    35         (1u64 ^ self.sign_mask).wrapping_sub(self.sign_mask) as i8
 
    48     #[inline]
 
    53     #[inline]
 
    49     pub const fn abs(&self) -> Self {
 
    54     pub const fn abs(&self) -> Self {
 
    50         Self {
 
    55         Self {
 
    51             sign_mask: POSITIVE_MASK,
 
    56             sign_mask: POSITIVE_MASK,
 
    52             value: self.value,
 
    57             value: self.value,
 
    53         }
 
    58             _marker: self._marker,
 
    54     }
 
    59         }
 
    55 
    60     }
 
    56     #[inline]
 
    61 
    57     pub fn round(&self) -> i32 {
 
    62     #[inline]
 
    58         ((self.value >> 32) as i32 ^ self.sign_mask as i32).wrapping_sub(self.sign_mask as i32)
 
    63     pub fn round(&self) -> i64 {
 
    59     }
 
    64         ((self.value >> FRAC_BITS) as i64 ^ self.sign_mask as i64).wrapping_sub(self.sign_mask as i64)
 
    60 
    65     }
 
    61     #[inline]
 
    66 
    62     pub const fn abs_round(&self) -> u32 {
 
    67     #[inline]
 
    63         (self.value >> 32) as u32
 
    68     pub const fn abs_round(&self) -> u64 {
 
       
    69         self.value >> FRAC_BITS
 
    64     }
 
    70     }
 
    65 
    71 
    66     #[inline]
 
    72     #[inline]
 
    67     pub fn sqr(&self) -> Self {
 
    73     pub fn sqr(&self) -> Self {
 
    68         Self {
 
    74         Self {
 
    69             sign_mask: 0,
 
    75             sign_mask: 0,
 
    70             value: ((self.value as u128).pow(2) >> 32).saturating_into(),
 
    76             value: ((self.value as u128).pow(2) >> FRAC_BITS).saturating_into(),
 
       
    77             _marker: self._marker
 
    71         }
 
    78         }
 
    72     }
 
    79     }
 
    73 
    80 
    74     #[inline]
 
    81     #[inline]
 
    75     pub fn sqrt(&self) -> Self {
 
    82     pub fn sqrt(&self) -> Self {
 
    76         debug_assert!(self.is_positive());
 
    83         debug_assert!(self.is_positive());
 
    77 
    84 
    78         Self {
 
    85         Self {
 
    79             sign_mask: POSITIVE_MASK,
 
    86             sign_mask: POSITIVE_MASK,
 
    80             value: integral_sqrt(self.value) << 16,
 
    87             value: integral_sqrt(self.value) << (FRAC_BITS / 2),
 
    81         }
 
    88             _marker: self._marker
 
    82     }
 
    89         }
 
    83 
    90     }
 
    84     #[inline]
 
    91 
    85     pub fn with_sign(&self, is_negative: bool) -> FPNum {
 
    92     #[inline]
 
    86         FPNum {
 
    93     pub fn with_sign(&self, is_negative: bool) -> Self {
 
       
    94         Self {
 
    87             sign_mask: bool_mask(is_negative),
 
    95             sign_mask: bool_mask(is_negative),
 
    88             ..*self
 
    96             ..*self
 
    89         }
 
    97         }
 
    90     }
 
    98     }
 
    91 
    99 
    92     #[inline]
 
   100     #[inline]
 
    93     pub const fn with_sign_as(self, other: FPNum) -> FPNum {
 
   101     pub const fn with_sign_as(self, other: Self) -> Self {
 
    94         FPNum {
 
   102         Self {
 
    95             sign_mask: other.sign_mask,
 
   103             sign_mask: other.sign_mask,
 
    96             ..self
 
   104             ..self
 
    97         }
 
   105         }
 
    98     }
 
   106     }
 
    99 
   107 /*
 
   100     #[inline]
 
   108     #[inline]
 
   101     pub const fn point(self) -> FPPoint {
 
   109     pub const fn point(self) -> FPPoint {
 
   102         FPPoint::new(self, self)
 
   110         FPPoint::new(self, self)
 
   103     }
 
   111     }
 
   104 
   112 */
 
   105     #[inline]
 
   113     #[inline]
 
   106     const fn temp_i128(self) -> i128 {
 
   114     const fn temp_i128(self) -> i128 {
 
   107         ((self.value ^ self.sign_mask) as i128).wrapping_sub(self.sign_mask as i128)
 
   115         ((self.value ^ self.sign_mask) as i128).wrapping_sub(self.sign_mask as i128)
 
   108     }
 
   116     }
 
   109 }
 
   117 }
 
   110 
   118 
   111 impl From<i32> for FPNum {
 
   119 impl<const FRAC_BITS: u8> From<i32> for FixedPoint<FRAC_BITS> {
 
   112     #[inline]
 
   120     #[inline]
 
   113     fn from(n: i32) -> Self {
 
   121     fn from(n: i32) -> Self {
 
   114         FPNum {
 
   122         Self {
 
   115             sign_mask: bool_mask(n < 0),
 
   123             sign_mask: bool_mask(n < 0),
 
   116             value: (n.abs() as u64) << 32,
 
   124             value: (n.abs() as u64) << FRAC_BITS,
 
   117         }
 
   125             _marker: PhantomData,
 
   118     }
 
   126         }
 
   119 }
 
   127     }
 
   120 
   128 }
 
   121 impl From<u32> for FPNum {
 
   129 
       
   130 impl<const FRAC_BITS: u8> From<u32> for FixedPoint<FRAC_BITS> {
 
   122     #[inline]
 
   131     #[inline]
 
   123     fn from(n: u32) -> Self {
 
   132     fn from(n: u32) -> Self {
 
   124         Self {
 
   133         Self {
 
   125             sign_mask: POSITIVE_MASK,
 
   134             sign_mask: POSITIVE_MASK,
 
   126             value: (n as u64) << 32,
 
   135             value: (n as u64) << FRAC_BITS,
 
   127         }
 
   136             _marker: PhantomData,
 
   128     }
 
   137         }
 
   129 }
 
   138     }
 
   130 
   139 }
 
   131 impl From<FPNum> for f64 {
 
   140 
   132     #[inline]
 
   141 impl<const FRAC_BITS: u8> From<FixedPoint<FRAC_BITS>> for f64 {
 
   133     fn from(n: FPNum) -> Self {
 
   142     #[inline]
 
       
   143     fn from(n: FixedPoint<FRAC_BITS>) -> Self {
 
   134         if n.is_negative() {
 
   144         if n.is_negative() {
 
   135             n.value as f64 / -0x1_0000_0000i64 as f64
 
   145             n.value as f64 / -(1i64 << FRAC_BITS) as f64
 
   136         } else {
 
   146         } else {
 
   137             n.value as f64 / 0x1_0000_0000i64 as f64
 
   147             n.value as f64 / (1i64 << FRAC_BITS) as f64
 
   138         }
 
   148         }
 
   139     }
 
   149     }
 
   140 }
 
   150 }
 
   141 
   151 
   142 impl PartialEq for FPNum {
 
   152 impl<const FRAC_BITS: u8> PartialEq for FixedPoint<FRAC_BITS> {
 
   143     #[inline]
 
   153     #[inline]
 
   144     fn eq(&self, other: &Self) -> bool {
 
   154     fn eq(&self, other: &Self) -> bool {
 
   145         self.value == other.value && (self.sign_mask == other.sign_mask || self.value == 0)
 
   155         self.value == other.value && (self.sign_mask == other.sign_mask || self.value == 0)
 
   146     }
 
   156     }
 
   147 }
 
   157 }
 
   148 
   158 
   149 impl Eq for FPNum {}
 
   159 impl<const FRAC_BITS: u8> Eq for FixedPoint<FRAC_BITS> {}
 
   150 
   160 
   151 impl PartialOrd for FPNum {
 
   161 impl<const FRAC_BITS: u8> PartialOrd for FixedPoint<FRAC_BITS> {
 
   152     #[inline]
 
   162     #[inline]
 
   153     fn partial_cmp(&self, rhs: &Self) -> Option<cmp::Ordering> {
 
   163     fn partial_cmp(&self, rhs: &Self) -> Option<cmp::Ordering> {
 
   154         Some(self.cmp(rhs))
 
   164         Some(self.cmp(rhs))
 
   155     }
 
   165     }
 
   156 }
 
   166 }
 
   157 
   167 
   158 impl Ord for FPNum {
 
   168 impl<const FRAC_BITS: u8> Ord for FixedPoint<FRAC_BITS> {
 
   159     #[inline]
 
   169     #[inline]
 
   160     fn cmp(&self, rhs: &Self) -> cmp::Ordering {
 
   170     fn cmp(&self, rhs: &Self) -> cmp::Ordering {
 
   161         self.temp_i128().cmp(&(rhs.temp_i128()))
 
   171         self.temp_i128().cmp(&(rhs.temp_i128()))
 
   162     }
 
   172     }
 
   163 }
 
   173 }
 
   164 
   174 
   165 impl ops::Add for FPNum {
 
   175 impl<const FRAC_BITS: u8> ops::Add for FixedPoint<FRAC_BITS> {
 
   166     type Output = Self;
 
   176     type Output = Self;
 
   167 
   177 
   168     #[inline]
 
   178     #[inline]
 
   169     fn add(self, rhs: Self) -> Self {
 
   179     fn add(self, rhs: Self) -> Self {
 
   170         let tmp = self.temp_i128() + rhs.temp_i128();
 
   180         let tmp = self.temp_i128() + rhs.temp_i128();
 
   171         let mask = bool_mask(tmp < 0);
 
   181         let mask = bool_mask(tmp < 0);
 
   172         Self {
 
   182         Self {
 
   173             sign_mask: mask,
 
   183             sign_mask: mask,
 
   174             value: ((tmp as u64) ^ mask).wrapping_sub(mask),
 
   184             value: ((tmp as u64) ^ mask).wrapping_sub(mask),
 
   175         }
 
   185             _marker: PhantomData,
 
   176     }
 
   186         }
 
   177 }
 
   187     }
 
   178 
   188 }
 
   179 impl ops::Sub for FPNum {
 
   189 
       
   190 impl<const FRAC_BITS: u8> ops::Sub for FixedPoint<FRAC_BITS> {
 
   180     type Output = Self;
 
   191     type Output = Self;
 
   181 
   192 
   182     #[inline]
 
   193     #[inline]
 
   183     fn sub(self, mut rhs: Self) -> Self {
 
   194     fn sub(self, mut rhs: Self) -> Self {
 
   184         rhs.sign_mask = !rhs.sign_mask;
 
   195         rhs.sign_mask = !rhs.sign_mask;
 
   185         self + rhs
 
   196         self + rhs
 
   186     }
 
   197     }
 
   187 }
 
   198 }
 
   188 
   199 
   189 impl ops::Neg for FPNum {
 
   200 impl<const FRAC_BITS: u8> ops::Neg for FixedPoint<FRAC_BITS> {
 
   190     type Output = Self;
 
   201     type Output = Self;
 
   191 
   202 
   192     #[inline]
 
   203     #[inline]
 
   193     fn neg(self) -> Self {
 
   204     fn neg(self) -> Self {
 
   194         Self {
 
   205         Self {
 
   195             sign_mask: !self.sign_mask,
 
   206             sign_mask: !self.sign_mask,
 
   196             value: self.value,
 
   207             value: self.value,
 
   197         }
 
   208             _marker: PhantomData,
 
   198     }
 
   209         }
 
   199 }
 
   210     }
 
   200 
   211 }
 
   201 impl ops::Mul for FPNum {
 
   212 
       
   213 impl<const FRAC_BITS: u8> ops::Mul for FixedPoint<FRAC_BITS> {
 
   202     type Output = Self;
 
   214     type Output = Self;
 
   203 
   215 
   204     #[inline]
 
   216     #[inline]
 
   205     fn mul(self, rhs: Self) -> Self {
 
   217     fn mul(self, rhs: Self) -> Self {
 
   206         Self {
 
   218         Self {
 
   207             sign_mask: self.sign_mask ^ rhs.sign_mask,
 
   219             sign_mask: self.sign_mask ^ rhs.sign_mask,
 
   208             value: ((self.value as u128 * rhs.value as u128) >> 32).saturating_into(),
 
   220             value: ((self.value as u128 * rhs.value as u128) >> FRAC_BITS).saturating_into(),
 
   209         }
 
   221             _marker: PhantomData,
 
   210     }
 
   222         }
 
   211 }
 
   223     }
 
   212 
   224 }
 
   213 impl ops::Mul<i32> for FPNum {
 
   225 
       
   226 impl<const FRAC_BITS: u8> ops::Mul<i32> for FixedPoint<FRAC_BITS> {
 
   214     type Output = Self;
 
   227     type Output = Self;
 
   215 
   228 
   216     #[inline]
 
   229     #[inline]
 
   217     fn mul(self, rhs: i32) -> Self {
 
   230     fn mul(self, rhs: i32) -> Self {
 
   218         Self {
 
   231         Self {
 
   219             sign_mask: self.sign_mask ^ bool_mask(rhs < 0),
 
   232             sign_mask: self.sign_mask ^ bool_mask(rhs < 0),
 
   220             value: (self.value as u128 * rhs.abs() as u128).saturating_into(),
 
   233             value: (self.value as u128 * rhs.abs() as u128).saturating_into(),
 
   221         }
 
   234             _marker: PhantomData,
 
   222     }
 
   235         }
 
   223 }
 
   236     }
 
   224 
   237 }
 
   225 impl ops::Div for FPNum {
 
   238 
       
   239 impl<const FRAC_BITS: u8> ops::Div for FixedPoint<FRAC_BITS> {
 
   226     type Output = Self;
 
   240     type Output = Self;
 
   227 
   241 
   228     #[inline]
 
   242     #[inline]
 
   229     fn div(self, rhs: Self) -> Self {
 
   243     fn div(self, rhs: Self) -> Self {
 
   230         Self {
 
   244         Self {
 
   231             sign_mask: self.sign_mask ^ rhs.sign_mask,
 
   245             sign_mask: self.sign_mask ^ rhs.sign_mask,
 
   232             value: (((self.value as u128) << 32) / rhs.value as u128).saturating_into(),
 
   246             value: (((self.value as u128) << FRAC_BITS) / rhs.value as u128).saturating_into(),
 
   233         }
 
   247             _marker: PhantomData,
 
   234     }
 
   248         }
 
   235 }
 
   249     }
 
   236 
   250 }
 
   237 impl ops::Div<i32> for FPNum {
 
   251 
       
   252 impl<const FRAC_BITS: u8> ops::Div<i32> for FixedPoint<FRAC_BITS> {
 
   238     type Output = Self;
 
   253     type Output = Self;
 
   239 
   254 
   240     #[inline]
 
   255     #[inline]
 
   241     fn div(self, rhs: i32) -> Self {
 
   256     fn div(self, rhs: i32) -> Self {
 
   242         Self {
 
   257         Self {
 
   243             sign_mask: self.sign_mask ^ bool_mask(rhs < 0),
 
   258             sign_mask: self.sign_mask ^ bool_mask(rhs < 0),
 
   244             value: self.value / rhs.abs() as u64,
 
   259             value: self.value / rhs.abs() as u64,
 
   245         }
 
   260             _marker: PhantomData,
 
   246     }
 
   261         }
 
   247 }
 
   262     }
 
   248 
   263 }
 
   249 impl ops::Div<u32> for FPNum {
 
   264 
       
   265 impl<const FRAC_BITS: u8> ops::Div<u32> for FixedPoint<FRAC_BITS> {
 
   250     type Output = Self;
 
   266     type Output = Self;
 
   251 
   267 
   252     #[inline]
 
   268     #[inline]
 
   253     fn div(self, rhs: u32) -> Self {
 
   269     fn div(self, rhs: u32) -> Self {
 
   254         Self {
 
   270         Self {
 
   255             sign_mask: self.sign_mask,
 
   271             sign_mask: self.sign_mask,
 
   256             value: self.value / rhs as u64,
 
   272             value: self.value / rhs as u64,
 
       
   273             _marker: PhantomData,
 
   257         }
 
   274         }
 
   258     }
 
   275     }
 
   259 }
 
   276 }
 
   260 
   277 
   261 #[macro_export]
 
   278 #[macro_export]
 
   307     #[inline]
 
   324     #[inline]
 
   308     pub const fn x(&self) -> FPNum {
 
   325     pub const fn x(&self) -> FPNum {
 
   309         FPNum {
 
   326         FPNum {
 
   310             sign_mask: self.x_sign_mask as i32 as u64,
 
   327             sign_mask: self.x_sign_mask as i32 as u64,
 
   311             value: self.x_value,
 
   328             value: self.x_value,
 
       
   329             _marker: PhantomData,
 
   312         }
 
   330         }
 
   313     }
 
   331     }
 
   314 
   332 
   315     #[inline]
 
   333     #[inline]
 
   316     pub const fn y(&self) -> FPNum {
 
   334     pub const fn y(&self) -> FPNum {
 
   317         FPNum {
 
   335         FPNum {
 
   318             sign_mask: self.y_sign_mask as i32 as u64,
 
   336             sign_mask: self.y_sign_mask as i32 as u64,
 
   319             value: self.y_value,
 
   337             value: self.y_value,
 
       
   338             _marker: PhantomData,
 
   320         }
 
   339         }
 
   321     }
 
   340     }
 
   322 
   341 
   323     #[inline]
 
   342     #[inline]
 
   324     pub fn is_zero(&self) -> bool {
 
   343     pub fn is_zero(&self) -> bool {
 
   344             let sqr: u128 = (self.x_value as u128).pow(2) + (self.y_value as u128).pow(2);
 
   363             let sqr: u128 = (self.x_value as u128).pow(2) + (self.y_value as u128).pow(2);
 
   345 
   364 
   346             FPNum {
 
   365             FPNum {
 
   347                 sign_mask: POSITIVE_MASK,
 
   366                 sign_mask: POSITIVE_MASK,
 
   348                 value: integral_sqrt_ext(sqr),
 
   367                 value: integral_sqrt_ext(sqr),
 
       
   368                 _marker: PhantomData,
 
   349             }
 
   369             }
 
   350         }
 
   370         }
 
   351     }
 
   371     }
 
   352 
   372 
   353     #[inline]
 
   373     #[inline]
 
   502 
   522 
   503     result
 
   523     result
 
   504 }
 
   524 }
 
   505 
   525 
   506 #[inline]
 
   526 #[inline]
 
   507 pub fn distance<T>(x: T, y: T) -> FPNum
 
   527 pub fn distance<T, const FRAC_BITS: u8>(x: T, y: T) -> FixedPoint<FRAC_BITS>
 
   508 where
 
   528 where
 
   509     T: Into<i128> + std::fmt::Debug,
 
   529     T: Into<i128> + std::fmt::Debug,
 
   510 {
 
   530 {
 
   511     let [x_squared, y_squared] = [x, y].map(|i| (i.into().pow(2) as u128).saturating_mul(2^64));
 
   531     let [x_squared, y_squared] = [x, y].map(|i| (i.into().pow(2) as u128).saturating_mul(1 << FRAC_BITS << FRAC_BITS));
 
   512     let sqr: u128 = x_squared.saturating_add(y_squared);
 
   532     let sqr: u128 = x_squared.saturating_add(y_squared);
 
   513 
   533 
   514     FPNum {
 
   534     FixedPoint {
 
   515         sign_mask: POSITIVE_MASK,
 
   535         sign_mask: POSITIVE_MASK,
 
   516         value: integral_sqrt_ext(sqr),
 
   536         value: integral_sqrt_ext(sqr),
 
       
   537         _marker: PhantomData,
 
   517     }
 
   538     }
 
   518 }
 
   539 }
 
   519 
   540 
   520 /* TODO:
 
   541 /* TODO:
 
   521  AngleSin
 
   542  AngleSin
hedgewars