author | nemo |
Thu, 15 Nov 2018 15:39:59 -0500 | |
changeset 14213 | 09dacb61d526 |
parent 14207 | bb2f301d4fe0 |
child 14627 | 2e2b31cf0871 |
permissions | -rw-r--r-- |
14207 | 1 |
use std::{ |
2 |
cmp, |
|
3 |
ops, |
|
4 |
ops::Shl |
|
5 |
}; |
|
13882 | 6 |
|
7 |
#[derive(Clone, Debug, Copy)] |
|
8 |
pub struct FPNum { |
|
9 |
is_negative: bool, |
|
10 |
value: u64, |
|
11 |
} |
|
12 |
||
13 |
impl FPNum { |
|
13927 | 14 |
#[inline] |
13928 | 15 |
pub fn new(numerator: i32, denominator: u32) -> Self { |
13882 | 16 |
FPNum::from(numerator) / denominator |
17 |
} |
|
18 |
||
13885 | 19 |
#[inline] |
13928 | 20 |
pub fn signum(&self) -> i8 { |
13882 | 21 |
if self.is_negative { |
22 |
-1 |
|
23 |
} else { |
|
24 |
1 |
|
25 |
} |
|
26 |
} |
|
27 |
||
13885 | 28 |
#[inline] |
13928 | 29 |
pub fn is_negative(&self) -> bool { |
13882 | 30 |
self.is_negative |
31 |
} |
|
32 |
||
13885 | 33 |
#[inline] |
13928 | 34 |
pub fn is_positive(&self) -> bool { |
13882 | 35 |
!self.is_negative |
36 |
} |
|
37 |
||
13885 | 38 |
#[inline] |
13928 | 39 |
pub fn is_zero(&self) -> bool { |
13882 | 40 |
self.value == 0 |
41 |
} |
|
42 |
||
13885 | 43 |
#[inline] |
13928 | 44 |
pub fn abs(&self) -> Self { |
13882 | 45 |
Self { |
46 |
is_negative: false, |
|
47 |
value: self.value, |
|
48 |
} |
|
49 |
} |
|
50 |
||
13885 | 51 |
#[inline] |
14139 | 52 |
pub fn round(&self) -> i32 { |
13882 | 53 |
if self.is_negative { |
14139 | 54 |
-((self.value >> 32) as i32) |
13882 | 55 |
} else { |
14139 | 56 |
(self.value >> 32) as i32 |
13882 | 57 |
} |
58 |
} |
|
59 |
||
13885 | 60 |
#[inline] |
14081 | 61 |
pub fn abs_round(&self) -> u32 { |
62 |
(self.value >> 32) as u32 |
|
63 |
} |
|
64 |
||
65 |
#[inline] |
|
13928 | 66 |
pub fn sqr(&self) -> Self { |
13882 | 67 |
Self { |
68 |
is_negative: false, |
|
69 |
value: ((self.value as u128).pow(2) >> 32) as u64, |
|
70 |
} |
|
71 |
} |
|
72 |
||
13928 | 73 |
pub fn sqrt(&self) -> Self { |
13882 | 74 |
debug_assert!(!self.is_negative); |
75 |
||
76 |
let mut t: u64 = 0x4000000000000000; |
|
77 |
let mut r: u64 = 0; |
|
78 |
let mut q = self.value; |
|
79 |
||
80 |
for _ in 0..32 { |
|
81 |
let s = r + t; |
|
82 |
r >>= 1; |
|
83 |
||
84 |
if s <= q { |
|
85 |
q -= s; |
|
86 |
r += t; |
|
87 |
} |
|
88 |
t >>= 2; |
|
89 |
} |
|
90 |
||
91 |
Self { |
|
92 |
is_negative: false, |
|
93 |
value: r << 16, |
|
94 |
} |
|
95 |
} |
|
13925 | 96 |
|
13927 | 97 |
#[inline] |
13928 | 98 |
pub fn with_sign(&self, is_negative: bool) -> FPNum { |
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
99 |
FPNum { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
100 |
is_negative, |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
101 |
..*self |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
102 |
} |
13925 | 103 |
} |
104 |
||
105 |
#[inline] |
|
13928 | 106 |
pub fn with_sign_as(self, other: FPNum) -> FPNum { |
13925 | 107 |
self.with_sign(other.is_negative) |
108 |
} |
|
13927 | 109 |
|
110 |
#[inline] |
|
13928 | 111 |
pub fn point(self) -> FPPoint { |
13927 | 112 |
FPPoint::new(self, self) |
113 |
} |
|
13882 | 114 |
} |
115 |
||
116 |
impl From<i32> for FPNum { |
|
117 |
#[inline] |
|
118 |
fn from(n: i32) -> Self { |
|
119 |
FPNum { |
|
120 |
is_negative: n < 0, |
|
121 |
value: (n.abs() as u64) << 32, |
|
122 |
} |
|
123 |
} |
|
124 |
} |
|
125 |
||
126 |
impl From<u32> for FPNum { |
|
127 |
#[inline] |
|
128 |
fn from(n: u32) -> Self { |
|
129 |
Self { |
|
130 |
is_negative: false, |
|
131 |
value: (n as u64) << 32, |
|
132 |
} |
|
133 |
} |
|
134 |
} |
|
135 |
||
136 |
impl From<FPNum> for f64 { |
|
137 |
#[inline] |
|
138 |
fn from(n: FPNum) -> Self { |
|
139 |
if n.is_negative { |
|
140 |
n.value as f64 / (-0x10000000 as f64) |
|
141 |
} else { |
|
142 |
n.value as f64 / 0x10000000 as f64 |
|
143 |
} |
|
144 |
} |
|
145 |
} |
|
146 |
||
147 |
impl PartialEq for FPNum { |
|
13885 | 148 |
#[inline] |
13882 | 149 |
fn eq(&self, other: &Self) -> bool { |
150 |
self.value == other.value && (self.is_negative == other.is_negative || self.value == 0) |
|
151 |
} |
|
152 |
} |
|
153 |
||
154 |
impl Eq for FPNum {} |
|
155 |
||
156 |
impl PartialOrd for FPNum { |
|
13885 | 157 |
#[inline] |
13882 | 158 |
fn partial_cmp(&self, rhs: &Self) -> std::option::Option<std::cmp::Ordering> { |
159 |
Some(self.cmp(rhs)) |
|
160 |
} |
|
161 |
} |
|
162 |
||
163 |
impl Ord for FPNum { |
|
164 |
#[inline] |
|
165 |
fn cmp(&self, rhs: &Self) -> cmp::Ordering { |
|
13884 | 166 |
#[inline] |
167 |
fn extend(n: &FPNum) -> i128 { |
|
168 |
if n.is_negative { |
|
169 |
-(n.value as i128) |
|
13882 | 170 |
} else { |
13884 | 171 |
n.value as i128 |
13882 | 172 |
} |
173 |
} |
|
13884 | 174 |
extend(self).cmp(&(extend(rhs))) |
13882 | 175 |
} |
176 |
} |
|
177 |
||
178 |
impl ops::Add for FPNum { |
|
179 |
type Output = Self; |
|
180 |
||
181 |
#[inline] |
|
182 |
fn add(self, rhs: Self) -> Self { |
|
183 |
if self.is_negative == rhs.is_negative { |
|
184 |
Self { |
|
185 |
is_negative: self.is_negative, |
|
186 |
value: self.value + rhs.value, |
|
187 |
} |
|
188 |
} else if self.value > rhs.value { |
|
189 |
Self { |
|
190 |
is_negative: self.is_negative, |
|
191 |
value: self.value - rhs.value, |
|
192 |
} |
|
193 |
} else { |
|
194 |
Self { |
|
195 |
is_negative: rhs.is_negative, |
|
196 |
value: rhs.value - self.value, |
|
197 |
} |
|
198 |
} |
|
199 |
} |
|
200 |
} |
|
201 |
||
202 |
impl ops::Sub for FPNum { |
|
203 |
type Output = Self; |
|
204 |
||
205 |
#[inline] |
|
206 |
fn sub(self, rhs: Self) -> Self { |
|
207 |
if self.is_negative == rhs.is_negative { |
|
208 |
if self.value > rhs.value { |
|
209 |
Self { |
|
210 |
is_negative: self.is_negative, |
|
211 |
value: self.value - rhs.value, |
|
212 |
} |
|
213 |
} else { |
|
214 |
Self { |
|
215 |
is_negative: !rhs.is_negative, |
|
216 |
value: rhs.value - self.value, |
|
217 |
} |
|
218 |
} |
|
219 |
} else { |
|
220 |
Self { |
|
221 |
is_negative: self.is_negative, |
|
222 |
value: self.value + rhs.value, |
|
223 |
} |
|
224 |
} |
|
225 |
} |
|
226 |
} |
|
227 |
||
228 |
impl ops::Neg for FPNum { |
|
229 |
type Output = Self; |
|
230 |
||
231 |
#[inline] |
|
232 |
fn neg(self) -> Self { |
|
233 |
Self { |
|
234 |
is_negative: !self.is_negative, |
|
235 |
value: self.value, |
|
236 |
} |
|
237 |
} |
|
238 |
} |
|
239 |
||
240 |
impl ops::Mul for FPNum { |
|
241 |
type Output = Self; |
|
242 |
||
243 |
#[inline] |
|
244 |
fn mul(self, rhs: Self) -> Self { |
|
245 |
Self { |
|
246 |
is_negative: self.is_negative ^ rhs.is_negative, |
|
247 |
value: ((self.value as u128 * rhs.value as u128) >> 32) as u64, |
|
248 |
} |
|
249 |
} |
|
250 |
} |
|
251 |
||
252 |
impl ops::Mul<i32> for FPNum { |
|
253 |
type Output = Self; |
|
254 |
||
255 |
#[inline] |
|
256 |
fn mul(self, rhs: i32) -> Self { |
|
257 |
Self { |
|
258 |
is_negative: self.is_negative ^ (rhs < 0), |
|
259 |
value: self.value * rhs.abs() as u64, |
|
260 |
} |
|
261 |
} |
|
262 |
} |
|
263 |
||
264 |
impl ops::Div for FPNum { |
|
265 |
type Output = Self; |
|
266 |
||
267 |
#[inline] |
|
268 |
fn div(self, rhs: Self) -> Self { |
|
269 |
Self { |
|
270 |
is_negative: self.is_negative ^ rhs.is_negative, |
|
271 |
value: (((self.value as u128) << 32) / rhs.value as u128) as u64, |
|
272 |
} |
|
273 |
} |
|
274 |
} |
|
275 |
||
276 |
impl ops::Div<i32> for FPNum { |
|
277 |
type Output = Self; |
|
278 |
||
279 |
#[inline] |
|
280 |
fn div(self, rhs: i32) -> Self { |
|
281 |
Self { |
|
282 |
is_negative: self.is_negative ^ (rhs < 0), |
|
283 |
value: self.value / rhs.abs() as u64, |
|
284 |
} |
|
285 |
} |
|
286 |
} |
|
287 |
||
288 |
impl ops::Div<u32> for FPNum { |
|
289 |
type Output = Self; |
|
290 |
||
291 |
#[inline] |
|
292 |
fn div(self, rhs: u32) -> Self { |
|
293 |
Self { |
|
294 |
is_negative: self.is_negative, |
|
295 |
value: self.value / rhs as u64, |
|
296 |
} |
|
297 |
} |
|
298 |
} |
|
299 |
||
13928 | 300 |
#[macro_export] |
13891 | 301 |
macro_rules! fp { |
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
302 |
(-$n: tt / $d: tt) => { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
303 |
FPNum::new(-$n, $d) |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
304 |
}; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
305 |
($n: tt / $d: tt) => { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
306 |
FPNum::new($n, $d) |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
307 |
}; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
308 |
(-$n: tt) => { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
309 |
FPNum::from(-$n) |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
310 |
}; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
311 |
($n: tt) => { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
312 |
FPNum::from($n) |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
313 |
}; |
13891 | 314 |
} |
315 |
||
13925 | 316 |
const LINEARIZE_TRESHOLD: u64 = 0x1_0000; |
317 |
||
318 |
#[derive(Clone, Copy, Debug)] |
|
13928 | 319 |
pub struct FPPoint { |
13925 | 320 |
x_is_negative: bool, |
321 |
y_is_negative: bool, |
|
322 |
x_value: u64, |
|
323 |
y_value: u64, |
|
324 |
} |
|
325 |
||
326 |
impl FPPoint { |
|
327 |
#[inline] |
|
13928 | 328 |
pub fn new(x: FPNum, y: FPNum) -> Self { |
13925 | 329 |
Self { |
330 |
x_is_negative: x.is_negative, |
|
331 |
y_is_negative: y.is_negative, |
|
332 |
x_value: x.value, |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
333 |
y_value: y.value, |
13925 | 334 |
} |
335 |
} |
|
336 |
||
337 |
#[inline] |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
338 |
pub fn zero() -> FPPoint { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
339 |
FPPoint::new(fp!(0), fp!(0)) |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
340 |
} |
13925 | 341 |
|
342 |
#[inline] |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
343 |
pub fn unit_x() -> FPPoint { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
344 |
FPPoint::new(fp!(1), fp!(0)) |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
345 |
} |
13925 | 346 |
|
347 |
#[inline] |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
348 |
pub fn unit_y() -> FPPoint { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
349 |
FPPoint::new(fp!(0), fp!(1)) |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
350 |
} |
13925 | 351 |
|
352 |
#[inline] |
|
13928 | 353 |
pub fn x(&self) -> FPNum { |
13925 | 354 |
FPNum { |
355 |
is_negative: self.x_is_negative, |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
356 |
value: self.x_value, |
13925 | 357 |
} |
358 |
} |
|
359 |
||
360 |
#[inline] |
|
13928 | 361 |
pub fn y(&self) -> FPNum { |
13925 | 362 |
FPNum { |
363 |
is_negative: self.y_is_negative, |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
364 |
value: self.y_value, |
13925 | 365 |
} |
366 |
} |
|
367 |
||
368 |
#[inline] |
|
14178 | 369 |
pub fn is_zero(&self) -> bool { |
370 |
self.x().is_zero() && self.y().is_zero() |
|
371 |
} |
|
372 |
||
373 |
#[inline] |
|
13928 | 374 |
pub fn max_norm(&self) -> FPNum { |
13939 | 375 |
std::cmp::max(self.x().abs(), self.y().abs()) |
13928 | 376 |
} |
377 |
||
378 |
#[inline] |
|
379 |
pub fn sqr_distance(&self) -> FPNum { |
|
13925 | 380 |
self.x().sqr() + self.y().sqr() |
381 |
} |
|
382 |
||
383 |
#[inline] |
|
13928 | 384 |
pub fn distance(&self) -> FPNum { |
13925 | 385 |
let r = self.x_value | self.y_value; |
386 |
if r < LINEARIZE_TRESHOLD { |
|
387 |
FPNum::from(r as u32) |
|
388 |
} else { |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
389 |
let mut sqr: u128 = (self.x_value as u128).pow(2) + (self.y_value as u128).pow(2); |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
390 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
391 |
let mut t: u128 = 0x40000000_00000000_00000000_00000000; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
392 |
let mut r: u128 = 0; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
393 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
394 |
for _ in 0..64 { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
395 |
let s = r + t; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
396 |
r >>= 1; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
397 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
398 |
if s <= sqr { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
399 |
sqr -= s; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
400 |
r += t; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
401 |
} |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
402 |
t >>= 2; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
403 |
} |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
404 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
405 |
FPNum { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
406 |
is_negative: false, |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
407 |
value: r as u64, |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
408 |
} |
13925 | 409 |
} |
410 |
} |
|
411 |
||
412 |
#[inline] |
|
13928 | 413 |
pub fn is_in_range(&self, radius: FPNum) -> bool { |
414 |
self.max_norm() < radius && self.sqr_distance() < radius.sqr() |
|
13925 | 415 |
} |
416 |
||
417 |
#[inline] |
|
13928 | 418 |
pub fn dot(&self, other: &FPPoint) -> FPNum { |
13925 | 419 |
self.x() * other.x() + self.y() * other.y() |
420 |
} |
|
421 |
} |
|
422 |
||
423 |
impl PartialEq for FPPoint { |
|
424 |
#[inline] |
|
425 |
fn eq(&self, other: &Self) -> bool { |
|
426 |
self.x() == other.x() && self.y() == other.y() |
|
427 |
} |
|
428 |
} |
|
429 |
||
430 |
impl Eq for FPPoint {} |
|
431 |
||
432 |
impl ops::Neg for FPPoint { |
|
433 |
type Output = Self; |
|
434 |
||
435 |
#[inline] |
|
436 |
fn neg(self) -> Self { |
|
437 |
Self::new(-self.x(), -self.y()) |
|
438 |
} |
|
439 |
} |
|
440 |
||
441 |
macro_rules! bin_op_impl { |
|
13927 | 442 |
($op: ty, $name: tt) => { |
13925 | 443 |
impl $op for FPPoint { |
444 |
type Output = Self; |
|
445 |
||
446 |
#[inline] |
|
447 |
fn $name(self, rhs: Self) -> Self { |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
448 |
Self::new(self.x().$name(rhs.x()), self.y().$name(rhs.y())) |
13925 | 449 |
} |
450 |
} |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
451 |
}; |
13925 | 452 |
} |
453 |
||
13932 | 454 |
macro_rules! right_scalar_bin_op_impl { |
455 |
($($op: tt)::+, $name: tt) => { |
|
456 |
impl $($op)::+<FPNum> for FPPoint { |
|
13927 | 457 |
type Output = Self; |
458 |
||
459 |
#[inline] |
|
460 |
fn $name(self, rhs: FPNum) -> Self { |
|
461 |
Self::new(self.x().$name(rhs), |
|
462 |
self.y().$name(rhs)) |
|
463 |
} |
|
464 |
} |
|
14140 | 465 |
}; |
466 |
($($op: tt)::+<$arg: tt>, $name: tt) => { |
|
467 |
impl $($op)::+<$arg> for FPPoint { |
|
468 |
type Output = Self; |
|
469 |
||
470 |
#[inline] |
|
471 |
fn $name(self, rhs: $arg) -> Self { |
|
472 |
Self::new(self.x().$name(rhs), |
|
473 |
self.y().$name(rhs)) |
|
474 |
} |
|
475 |
} |
|
13927 | 476 |
} |
477 |
} |
|
478 |
||
13932 | 479 |
macro_rules! left_scalar_bin_op_impl { |
480 |
($($op: tt)::+, $name: tt) => { |
|
481 |
impl $($op)::+<FPPoint> for FPNum { |
|
482 |
type Output = FPPoint; |
|
483 |
||
484 |
#[inline] |
|
485 |
fn $name(self, rhs: FPPoint) -> Self::Output { |
|
486 |
Self::Output::new(self.$name(rhs.x()), |
|
487 |
self.$name(rhs.y())) |
|
488 |
} |
|
489 |
} |
|
490 |
} |
|
491 |
} |
|
492 |
||
13925 | 493 |
bin_op_impl!(ops::Add, add); |
494 |
bin_op_impl!(ops::Sub, sub); |
|
495 |
bin_op_impl!(ops::Mul, mul); |
|
13929 | 496 |
bin_op_impl!(ops::Div, div); |
13932 | 497 |
right_scalar_bin_op_impl!(ops::Add, add); |
498 |
right_scalar_bin_op_impl!(ops::Mul, mul); |
|
499 |
right_scalar_bin_op_impl!(ops::Sub, sub); |
|
500 |
right_scalar_bin_op_impl!(ops::Div, div); |
|
14140 | 501 |
right_scalar_bin_op_impl!(ops::Div<u32>, div); |
13932 | 502 |
left_scalar_bin_op_impl!(ops::Mul, mul); |
13925 | 503 |
|
13929 | 504 |
macro_rules! bin_assign_op_impl { |
505 |
($typ: tt, $($op: tt)::+, $name: tt, $delegate: tt) => { |
|
506 |
bin_assign_op_impl!($typ, $($op)::+<$typ>, $name, $delegate); |
|
507 |
}; |
|
508 |
($typ: tt, $($op: tt)::+<$arg: tt>, $name: tt, $delegate: tt) => { |
|
509 |
impl $($op)::+<$arg> for $typ { |
|
510 |
#[inline] |
|
511 |
fn $name(&mut self, rhs: $arg) { |
|
512 |
*self = *self $delegate rhs; |
|
513 |
} |
|
514 |
} |
|
515 |
} |
|
516 |
} |
|
517 |
||
518 |
bin_assign_op_impl!(FPNum, ops::AddAssign, add_assign, +); |
|
519 |
bin_assign_op_impl!(FPNum, ops::SubAssign, sub_assign, -); |
|
520 |
bin_assign_op_impl!(FPNum, ops::MulAssign, mul_assign, *); |
|
521 |
bin_assign_op_impl!(FPNum, ops::DivAssign, div_assign, /); |
|
522 |
bin_assign_op_impl!(FPNum, ops::MulAssign<i32>, mul_assign, *); |
|
523 |
bin_assign_op_impl!(FPNum, ops::DivAssign<i32>, div_assign, /); |
|
524 |
bin_assign_op_impl!(FPNum, ops::DivAssign<u32>, div_assign, /); |
|
525 |
||
526 |
bin_assign_op_impl!(FPPoint, ops::AddAssign, add_assign, +); |
|
527 |
bin_assign_op_impl!(FPPoint, ops::SubAssign, sub_assign, -); |
|
528 |
bin_assign_op_impl!(FPPoint, ops::MulAssign, mul_assign, *); |
|
529 |
bin_assign_op_impl!(FPPoint, ops::DivAssign, div_assign, /); |
|
530 |
bin_assign_op_impl!(FPPoint, ops::AddAssign<FPNum>, add_assign, +); |
|
531 |
bin_assign_op_impl!(FPPoint, ops::SubAssign<FPNum>, sub_assign, -); |
|
532 |
bin_assign_op_impl!(FPPoint, ops::MulAssign<FPNum>, mul_assign, *); |
|
533 |
bin_assign_op_impl!(FPPoint, ops::DivAssign<FPNum>, div_assign, /); |
|
534 |
||
13928 | 535 |
pub fn distance<T>(x: T, y: T) -> FPNum |
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
536 |
where |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
537 |
T: Into<i64> + std::fmt::Debug, |
13925 | 538 |
{ |
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
539 |
let mut sqr: u128 = (x.into().pow(2) as u128).shl(64) + (y.into().pow(2) as u128).shl(64); |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
540 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
541 |
let mut t: u128 = 0x40000000_00000000_00000000_00000000; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
542 |
let mut r: u128 = 0; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
543 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
544 |
for _ in 0..64 { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
545 |
let s = r + t; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
546 |
r >>= 1; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
547 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
548 |
if s <= sqr { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
549 |
sqr -= s; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
550 |
r += t; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
551 |
} |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
552 |
t >>= 2; |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
553 |
} |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
554 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
555 |
FPNum { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
556 |
is_negative: false, |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
557 |
value: r as u64, |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
558 |
} |
13925 | 559 |
} |
560 |
||
13882 | 561 |
/* TODO: |
562 |
AngleSin |
|
563 |
AngleCos |
|
564 |
*/ |
|
565 |
||
566 |
#[cfg(test)] |
|
567 |
#[test] |
|
568 |
fn basics() { |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
569 |
let n = fp!(15 / 2); |
13882 | 570 |
assert!(n.is_positive()); |
571 |
assert!(!n.is_negative()); |
|
572 |
||
573 |
assert!(!(-n).is_positive()); |
|
574 |
assert!((-n).is_negative()); |
|
575 |
||
576 |
assert_eq!(-(-n), n); |
|
577 |
assert_eq!((-n).abs(), n); |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
578 |
assert_eq!(-n, fp!(-15 / 2)); |
13882 | 579 |
|
580 |
assert_eq!(n.round(), 7); |
|
581 |
assert_eq!((-n).round(), -7); |
|
582 |
} |
|
583 |
||
584 |
#[test] |
|
585 |
fn zero() { |
|
13891 | 586 |
let z = fp!(0); |
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
587 |
let n = fp!(15 / 2); |
13882 | 588 |
|
589 |
assert!(z.is_zero()); |
|
590 |
assert!(z.is_positive()); |
|
591 |
assert!((-z).is_negative); |
|
13883 | 592 |
assert_eq!(n - n, z); |
593 |
assert_eq!(-n + n, z); |
|
13926 | 594 |
assert_eq!(n.with_sign_as(-n), -n); |
13882 | 595 |
} |
596 |
||
597 |
#[test] |
|
13884 | 598 |
fn ord() { |
13891 | 599 |
let z = fp!(0); |
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
600 |
let n1_5 = fp!(3 / 2); |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
601 |
let n2_25 = fp!(9 / 4); |
13884 | 602 |
|
603 |
assert!(!(z > z)); |
|
604 |
assert!(!(z < z)); |
|
605 |
assert!(n2_25 > n1_5); |
|
606 |
assert!(-n2_25 < n1_5); |
|
607 |
assert!(-n2_25 < -n1_5); |
|
608 |
} |
|
609 |
||
610 |
#[test] |
|
13882 | 611 |
fn arith() { |
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
612 |
let n1_5 = fp!(3 / 2); |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
613 |
let n2_25 = fp!(9 / 4); |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
614 |
let n_0_15 = fp!(-15 / 100); |
13882 | 615 |
|
13891 | 616 |
assert_eq!(n1_5 + n1_5, fp!(3)); |
617 |
assert_eq!(-n1_5 - n1_5, fp!(-3)); |
|
13882 | 618 |
|
619 |
assert_eq!(n1_5 * n1_5, n2_25); |
|
620 |
assert_eq!(-n1_5 * -n1_5, n2_25); |
|
621 |
assert_eq!(n1_5 * -n1_5, -n2_25); |
|
622 |
assert_eq!(-n1_5 * n1_5, -n2_25); |
|
623 |
||
13883 | 624 |
assert_eq!(-n2_25 / -n1_5, n1_5); |
625 |
assert_eq!(n1_5 / -10, n_0_15); |
|
626 |
||
13882 | 627 |
assert_eq!(n1_5.sqr(), n2_25); |
628 |
assert_eq!((-n1_5).sqr(), n2_25); |
|
629 |
||
630 |
assert_eq!(n2_25.sqrt(), n1_5); |
|
631 |
||
632 |
assert_eq!((n1_5 * n1_5 * n1_5.sqr()).sqrt(), n2_25); |
|
13929 | 633 |
|
634 |
let mut m = fp!(1); |
|
635 |
m += n1_5; |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
636 |
assert_eq!(m, fp!(5 / 2)); |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
637 |
} |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
638 |
|
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
639 |
#[test] |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
640 |
fn test_distance_high_values() { |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
641 |
assert_eq!(distance(1_000_000i32, 0), fp!(1_000_000)); |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
642 |
assert_eq!( |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
643 |
FPPoint::new(fp!(1_000_000), fp!(0)).distance(), |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
644 |
fp!(1_000_000) |
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
645 |
); |
13882 | 646 |
} |
13925 | 647 |
|
648 |
#[test] |
|
649 |
fn point() { |
|
650 |
let z = FPPoint::zero(); |
|
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
651 |
let n = fp!(16 / 9); |
13925 | 652 |
let p = FPPoint::new(fp!(1), fp!(-2)); |
653 |
||
654 |
assert_eq!(p.sqr_distance(), fp!(5)); |
|
655 |
assert_eq!(p + -p, FPPoint::zero()); |
|
656 |
assert_eq!(p * z, z); |
|
657 |
assert_eq!(p.dot(&z), fp!(0)); |
|
13932 | 658 |
assert_eq!(n * p, p * n); |
13925 | 659 |
assert_eq!(distance(4, 3), fp!(5)); |
13927 | 660 |
assert_eq!(p * fp!(-3), FPPoint::new(fp!(-3), fp!(6))); |
13939 | 661 |
assert_eq!(p.max_norm(), fp!(2)); |
14122
c27461e6a9eb
Implement non-overflowing calculations for high values
unc0rr
parents:
14081
diff
changeset
|
662 |
} |