feanor_math/rings/mpir/
mod.rs

1use libc;
2use serde::de::DeserializeSeed;
3use serde::ser::SerializeTuple;
4use serde::{Deserializer, Serializer, Serialize};
5
6use crate::impl_poly_gcd_locally_for_ZZ;
7use crate::algorithms;
8use crate::pid::*;
9use crate::ordered::*;
10use crate::primitive_int::*;
11use crate::divisibility::*;
12use crate::ring::*;
13use crate::homomorphism::*;
14use crate::integer::*;
15use crate::specialization::*;
16use crate::rings::rust_bigint::*;
17use crate::algorithms::bigint::deserialize_bigint_from_bytes;
18use crate::serialization::*;
19
20mod mpir_bindings;
21
22///
23/// An `mpir` integer.
24/// 
25pub struct MPZEl {
26    integer: mpir_bindings::__mpz_struct
27}
28
29impl MPZEl {
30
31    fn new() -> Self {
32        unsafe {
33            let mut result = mpir_bindings::UNINIT_MPZ;
34            mpir_bindings::__gmpz_init(&mut result as mpir_bindings::mpz_ptr);
35            return MPZEl { integer: result };
36        }
37    }
38
39    pub fn assign(&mut self, rhs: &MPZEl) {
40        unsafe {
41            mpir_bindings::__gmpz_set(&mut self.integer as mpir_bindings::mpz_ptr, &rhs.integer as mpir_bindings::mpz_srcptr);
42        }
43    }
44}
45
46///
47/// Except for random number generation (which we do in Rust), GMP/MPIR
48/// is thread-safe (Section 3.7 of the manual)
49/// 
50unsafe impl Send for MPZEl {}
51///
52/// Except for random number generation (which we do in Rust), GMP/MPIR
53/// is thread-safe (Section 3.7 of the manual)
54/// 
55unsafe impl Sync for MPZEl {}
56
57impl Drop for MPZEl {
58
59    fn drop(&mut self) {
60        unsafe {
61            mpir_bindings::__gmpz_clear(&mut self.integer as mpir_bindings::mpz_ptr)
62        }
63    }
64}
65
66///
67/// Arbitrary-precision integer ring, implemented by binding to the well-known
68/// and heavily optimized library mpir (fork of gmp).
69/// 
70#[derive(Debug, Clone, Copy, PartialEq, Eq)]
71pub struct MPZBase;
72
73///
74/// [`RingStore`] corresponding to [`MPZBase`].
75/// 
76pub type MPZ = RingValue<MPZBase>;
77
78impl MPZ {
79    
80    pub const RING: MPZ = RingValue::from(MPZBase);
81}
82
83impl MPZBase {
84
85    ///
86    /// Interprets the bytes in `input` as little endian bytes and returns the
87    /// nonnegative integer represented by them. 
88    /// 
89    pub fn from_le_bytes(&self, dst: &mut MPZEl, input: &[u8]) {
90        unsafe {
91            assert_eq!(std::mem::size_of::<mpir_bindings::mpir_ui>(), std::mem::size_of::<u64>());
92            if input.len() == 0 {
93                mpir_bindings::__gmpz_set_ui(&mut dst.integer as mpir_bindings::mpz_ptr, 0);
94                return;
95            }
96            assert!(input.len() > 0);
97            mpir_bindings::__gmpz_import(
98                &mut dst.integer as mpir_bindings::mpz_ptr, 
99                input.len(), 
100                -1i32, // least significant digit first
101                1 as libc::size_t,
102                -1, // little endian 
103                0, 
104                input.as_ptr() as *const libc::c_void
105            );
106        }
107    }
108
109    ///
110    /// Interprets the `u64` as digits w.r.t. base `2^64` (with least-significant digit first)
111    /// and returns the nonnegative integer represented by them. 
112    /// 
113    pub fn from_base_u64_repr(&self, dst: &mut MPZEl, input: &[u64]) {
114        unsafe {
115            assert_eq!(std::mem::size_of::<mpir_bindings::mpir_ui>(), std::mem::size_of::<u64>());
116            if input.len() == 0 {
117                mpir_bindings::__gmpz_set_ui(&mut dst.integer as mpir_bindings::mpz_ptr, 0);
118                return;
119            }
120            assert!(input.len() > 0);
121            mpir_bindings::__gmpz_import(
122                &mut dst.integer as mpir_bindings::mpz_ptr, 
123                input.len(), 
124                -1i32, // least significant digit first
125                (u64::BITS / 8) as libc::size_t,
126                0, // native endianess 
127                0, 
128                input.as_ptr() as *const libc::c_void
129            );
130        }
131    }
132
133    pub fn abs_base_u64_repr_len(&self, src: &MPZEl) -> usize {
134        self.abs_highest_set_bit(src).map(|n| (n / u64::BITS as usize) + 1).unwrap_or(0)
135    }
136
137    ///
138    /// Inverse to [`MPZBase::from_base_u64_repr()`].
139    /// 
140    pub fn abs_base_u64_repr(&self, src: &MPZEl, out: &mut [u64]) {
141        unsafe {
142            if self.abs_base_u64_repr_len(src) > 0 {
143                assert!(out.len() >= self.abs_base_u64_repr_len(src));
144                let mut size = 0;
145        
146                let result_ptr = mpir_bindings::__gmpz_export(
147                    out.as_mut_ptr() as *mut libc::c_void,
148                    &mut size,
149                    -1, // least significant digit first
150                    (u64::BITS / 8) as libc::size_t,
151                    0, // native endianess 
152                    0,
153                    &src.integer as mpir_bindings::mpz_srcptr
154                );
155                assert_eq!(result_ptr as *const libc::c_void, out.as_ptr() as *const libc::c_void);
156                for i in size..out.len() {
157                    out[i] = 0;
158                }
159            } else {
160                for i in 0..out.len() {
161                    out[i] = 0;
162                }
163            }
164        }
165    }
166
167    pub fn to_le_bytes_len(&self, src: &MPZEl) -> usize {
168        self.abs_highest_set_bit(src).map(|n| (n / u8::BITS as usize) + 1).unwrap_or(0)
169    }
170
171    ///
172    /// Inverse to [`MPZBase::from_le_bytes()`].
173    /// 
174    pub fn to_le_bytes(&self, src: &MPZEl, out: &mut [u8]) {
175        unsafe {
176            if self.to_le_bytes_len(src) > 0 {
177                assert!(out.len() >= self.to_le_bytes_len(src));
178                let mut size = 0;
179        
180                let result_ptr = mpir_bindings::__gmpz_export(
181                    out.as_mut_ptr() as *mut libc::c_void,
182                    &mut size,
183                    -1, // least significant digit first
184                    1 as libc::size_t,
185                    -1, // little endian
186                    0,
187                    &src.integer as mpir_bindings::mpz_srcptr
188                );
189                assert_eq!(result_ptr as *const libc::c_void, out.as_ptr() as *const libc::c_void);
190                for i in size..out.len() {
191                    out[i] = 0;
192                }
193            } else {
194                for i in 0..out.len() {
195                    out[i] = 0;
196                }
197            }
198        }
199    }
200}
201
202impl RingBase for MPZBase {
203    
204    type Element = MPZEl;
205
206    fn clone_el(&self, val: &Self::Element) -> Self::Element {
207        unsafe {
208            let mut result = MPZEl::new();
209            mpir_bindings::__gmpz_set(&mut result.integer as mpir_bindings::mpz_ptr, &val.integer as mpir_bindings::mpz_srcptr);
210            return result;
211        }
212    }
213
214    fn mul_ref(&self, lhs: &Self::Element, rhs: &Self::Element) -> Self::Element {
215        unsafe {
216            let mut result = MPZEl::new();
217            mpir_bindings::__gmpz_mul(&mut result.integer as mpir_bindings::mpz_ptr, &lhs.integer as mpir_bindings::mpz_srcptr, &rhs.integer as mpir_bindings::mpz_srcptr);
218            return result;
219        }
220    }
221
222    fn negate_inplace(&self, lhs: &mut Self::Element) {
223        unsafe {
224            mpir_bindings::__gmpz_neg(&mut lhs.integer as mpir_bindings::mpz_ptr, &lhs.integer as mpir_bindings::mpz_srcptr)
225        }
226    }
227
228    fn zero(&self) -> Self::Element {
229        MPZEl::new()
230    }
231
232    fn one(&self) -> Self::Element {
233        self.from_int(1)
234    }
235
236    fn sub_ref_fst(&self, lhs: &Self::Element, mut rhs: Self::Element) -> Self::Element {
237        unsafe {
238            mpir_bindings::__gmpz_sub(&mut rhs.integer as mpir_bindings::mpz_ptr, &lhs.integer as mpir_bindings::mpz_srcptr, &rhs.integer as mpir_bindings::mpz_srcptr);
239            return rhs;
240        }
241    }
242
243    fn sub_ref_snd(&self, mut lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
244        unsafe {
245            mpir_bindings::__gmpz_sub(&mut lhs.integer as mpir_bindings::mpz_ptr, &lhs.integer as mpir_bindings::mpz_srcptr, &rhs.integer as mpir_bindings::mpz_srcptr);
246            return lhs;
247        }
248    }
249
250    fn add_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) { 
251        self.add_assign_ref(lhs, &rhs);
252    }
253
254    fn add_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { 
255        unsafe {
256            mpir_bindings::__gmpz_add(&mut lhs.integer as mpir_bindings::mpz_ptr, &lhs.integer as mpir_bindings::mpz_srcptr, &rhs.integer as mpir_bindings::mpz_srcptr);
257        }
258    }
259
260    fn mul_assign(&self, lhs: &mut Self::Element, rhs: Self::Element) {
261        self.mul_assign_ref(lhs, &rhs)
262    }
263
264    fn mul_assign_ref(&self, lhs: &mut Self::Element, rhs: &Self::Element) { 
265        unsafe {
266            mpir_bindings::__gmpz_mul(&mut lhs.integer as mpir_bindings::mpz_ptr, &lhs.integer as mpir_bindings::mpz_srcptr, &rhs.integer as mpir_bindings::mpz_srcptr);
267        }
268    }
269
270    fn mul_assign_int(&self, lhs: &mut Self::Element, rhs: i32) {
271        unsafe {
272            mpir_bindings::__gmpz_mul_ui(&mut lhs.integer as mpir_bindings::mpz_ptr, &lhs.integer as mpir_bindings::mpz_srcptr, rhs.abs() as u64);
273            if rhs < 0 {
274                mpir_bindings::__gmpz_neg(&mut lhs.integer as mpir_bindings::mpz_ptr, &lhs.integer as mpir_bindings::mpz_srcptr)
275            }
276        }
277    }
278
279    fn sub(&self, lhs: Self::Element, rhs: Self::Element) -> Self::Element {
280        self.sub_ref_snd(lhs, &rhs)
281    }
282
283    fn from_int(&self, value: i32) -> Self::Element {
284        unsafe {
285            let mut result = MPZEl::new();
286            mpir_bindings::__gmpz_set_ui(&mut result.integer as mpir_bindings::mpz_ptr, value.abs() as u64);
287            if value < 0 {
288                return self.negate(result);
289            } else {
290                return result;
291            }
292        }
293    }
294
295    fn eq_el(&self, lhs: &Self::Element, rhs: &Self::Element) -> bool {
296        unsafe {
297            mpir_bindings::__gmpz_cmp(&lhs.integer as mpir_bindings::mpz_srcptr, &rhs.integer as mpir_bindings::mpz_srcptr) == 0
298        }
299    }
300
301    fn is_zero(&self, val: &Self::Element) -> bool { 
302        unsafe {
303            mpir_bindings::__gmpz_cmp_si(&val.integer as mpir_bindings::mpz_srcptr, 0) == 0
304        }
305    }
306    
307    fn is_one(&self, val: &Self::Element) -> bool { 
308        unsafe {
309            mpir_bindings::__gmpz_cmp_si(&val.integer as mpir_bindings::mpz_srcptr, 1) == 0
310        }
311    }
312
313    fn is_neg_one(&self, val: &Self::Element) -> bool {
314        unsafe {
315            mpir_bindings::__gmpz_cmp_si(&val.integer as mpir_bindings::mpz_srcptr, -1) == 0
316        }
317    }
318
319    fn is_noetherian(&self) -> bool {
320        true
321    }
322
323    fn is_commutative(&self) -> bool {
324        true
325    }
326
327    fn is_approximate(&self) -> bool {
328        false
329    }
330
331    fn dbg_within<'a>(&self, value: &Self::Element, out: &mut std::fmt::Formatter<'a>, _env: EnvBindingStrength) -> std::fmt::Result {
332        RustBigintRing::RING.get_ring().dbg(&self.map_out(RustBigintRing::RING.get_ring(), self.clone_el(value), &()), out)
333    }
334    
335    fn characteristic<I: IntegerRingStore + Copy>(&self, other_ZZ: I) -> Option<El<I>>
336        where I::Type: IntegerRing
337    {
338        Some(other_ZZ.zero())
339    }
340}
341
342impl OrderedRing for MPZBase {
343
344    fn cmp(&self, lhs: &Self::Element, rhs: &Self::Element) -> std::cmp::Ordering {
345        unsafe {
346            let res = mpir_bindings::__gmpz_cmp(
347                &lhs.integer as mpir_bindings::mpz_srcptr,
348                &rhs.integer as mpir_bindings::mpz_srcptr
349            );
350            if res < 0 {
351                return std::cmp::Ordering::Less;
352            } else if res > 0 {
353                return std::cmp::Ordering::Greater;
354            } else {
355                return std::cmp::Ordering::Equal;
356            }
357        }
358    }
359
360    fn is_neg(&self, value: &Self::Element) -> bool {
361        unsafe {
362            mpir_bindings::mpz_is_neg(&value.integer as mpir_bindings::mpz_srcptr)
363        }
364    }
365}
366
367impl SerializableElementRing for MPZBase {
368
369    fn deserialize<'de, D>(&self, deserializer: D) -> Result<Self::Element, D::Error>
370        where D: Deserializer<'de>
371    {
372        if deserializer.is_human_readable() {
373            return DeserializeWithRing::new(RustBigintRing::RING).deserialize(deserializer).map(|n| int_cast(n, RingRef::new(self), RustBigintRing::RING));
374        } else {
375            let (negative, mut result) = deserialize_bigint_from_bytes(deserializer, |data| {
376                let mut result = self.zero();
377                self.from_le_bytes(&mut result, data);
378                return result;
379            })?;
380            if negative {
381                self.negate_inplace(&mut result);
382            }
383            return Ok(result);
384        }
385    }
386
387    fn serialize<S>(&self, el: &Self::Element, serializer: S) -> Result<S::Ok, S::Error>
388        where S: Serializer
389    {
390        if serializer.is_human_readable() {
391            SerializableNewtype::new("BigInt", format!("{}", RingRef::new(self).format(el)).as_str()).serialize(serializer)
392        } else {
393            let len = self.to_le_bytes_len(el);
394            let mut data = Vec::with_capacity(len);
395            data.resize(len, 0u8);
396            self.to_le_bytes(el, &mut data);
397            let mut seq = serializer.serialize_tuple(2)?;
398            seq.serialize_element(&self.is_neg(el))?;
399            seq.serialize_element(serde_bytes::Bytes::new(&data[..]))?;
400            return seq.end();
401        }
402    }
403}
404
405impl DivisibilityRing for MPZBase {
406
407    fn checked_left_div(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
408        if self.is_zero(rhs) {
409            if self.is_zero(lhs) {
410                return Some(self.zero());
411            } else {
412                return None;
413            }
414        }
415        let (quo, rem) = self.euclidean_div_rem(self.clone_el(lhs), rhs);
416        if self.is_zero(&rem) {
417            return Some(quo);
418        } else {
419            return None;
420        }
421    }
422
423    fn balance_factor<'a, I>(&self, elements: I) -> Option<Self::Element>
424        where I: Iterator<Item = &'a Self::Element>,
425            Self: 'a
426    {
427        Some(elements.fold(self.zero(), |a, b| self.ideal_gen(&a, b)))
428    }
429}
430
431impl PrincipalIdealRing for MPZBase {
432    
433    fn extended_ideal_gen(&self, lhs: &Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element, Self::Element) {
434        algorithms::eea::eea(self.clone_el(lhs), self.clone_el(rhs), MPZ::RING)
435    }
436
437    fn checked_div_min(&self, lhs: &Self::Element, rhs: &Self::Element) -> Option<Self::Element> {
438        if self.is_zero(lhs) && self.is_zero(rhs) {
439            return Some(self.one());
440        }
441        self.checked_left_div(lhs, rhs)
442    }
443}
444
445impl EuclideanRing for MPZBase {
446    
447    fn euclidean_div_rem(&self, mut lhs: Self::Element, rhs: &Self::Element) -> (Self::Element, Self::Element) {
448        unsafe {
449            assert!(!self.is_zero(rhs));
450            let mut quo = MPZEl::new();
451            mpir_bindings::__gmpz_tdiv_qr(
452                &mut quo.integer as mpir_bindings::mpz_ptr, 
453                &mut lhs.integer as mpir_bindings::mpz_ptr, 
454                &lhs.integer as mpir_bindings::mpz_srcptr, 
455                &rhs.integer as mpir_bindings::mpz_srcptr
456            );
457            return (quo, lhs);
458        }
459    }
460
461    fn euclidean_rem(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element { 
462        unsafe {
463            assert!(!self.is_zero(rhs));
464            let mut rem = MPZEl::new();
465            mpir_bindings::__gmpz_tdiv_r(
466                &mut rem.integer as mpir_bindings::mpz_ptr, 
467                &lhs.integer as mpir_bindings::mpz_srcptr, 
468                &rhs.integer as mpir_bindings::mpz_srcptr
469            );
470            return rem;
471        }
472    }
473
474    fn euclidean_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
475        unsafe {
476            assert!(!self.is_zero(rhs));
477            let mut rem = MPZEl::new();
478            mpir_bindings::__gmpz_tdiv_q(
479                &mut rem.integer as mpir_bindings::mpz_ptr, 
480                &lhs.integer as mpir_bindings::mpz_srcptr, 
481                &rhs.integer as mpir_bindings::mpz_srcptr
482            );
483            return rem;
484        }
485    }
486
487    fn euclidean_deg(&self, val: &Self::Element) -> Option<usize> {
488        if self.abs_highest_set_bit(val).unwrap_or(0) < usize::BITS as usize {
489            unsafe {
490                mpir_bindings::__gmpz_get_ui(&val.integer as mpir_bindings::mpz_srcptr).try_into().ok()
491            }
492        } else {
493            None
494        }
495    }
496}
497
498impl Default for MPZBase {
499    
500    fn default() -> Self {
501        MPZ::RING.into()
502    }
503}
504
505impl Domain for MPZBase {}
506
507impl IntegerRing for MPZBase {
508    
509    fn to_float_approx(&self, el: &Self::Element) -> f64 {
510        unsafe {
511            mpir_bindings::__gmpz_get_d(&el.integer as mpir_bindings::mpz_srcptr)
512        }
513    }
514
515    fn from_float_approx(&self, el: f64) -> Option<Self::Element> {
516        unsafe {
517            let mut result = MPZEl::new();
518            mpir_bindings::__gmpz_set_d(&mut result.integer as mpir_bindings::mpz_ptr, el);
519            return Some(result);
520        }
521    }
522
523    fn mul_pow_2(&self, el: &mut Self::Element, power: usize) {
524        unsafe {
525            mpir_bindings::__gmpz_mul_2exp(&mut el.integer as mpir_bindings::mpz_ptr, &el.integer as mpir_bindings::mpz_srcptr, power as u64)
526        }
527    }
528
529    fn euclidean_div_pow_2(&self, el: &mut Self::Element, power: usize) {
530        unsafe {
531            mpir_bindings::__gmpz_tdiv_q_2exp(&mut el.integer as mpir_bindings::mpz_ptr, &el.integer as mpir_bindings::mpz_srcptr, power as u64)
532        }
533    }
534
535    fn abs_is_bit_set(&self, el: &Self::Element, bit: usize) -> bool {
536        unsafe {
537            if mpir_bindings::mpz_is_neg(&el.integer as mpir_bindings::mpz_srcptr) {
538                let value = mpir_bindings::__gmpz_tstbit(&el.integer as mpir_bindings::mpz_srcptr, bit as u64) == 1;
539                let least_significant_zero = mpir_bindings::__gmpz_scan1(&el.integer as mpir_bindings::mpz_srcptr, 0);
540                if bit <= least_significant_zero as usize {
541                    value
542                } else {
543                    !value
544                }
545            } else {
546                mpir_bindings::__gmpz_tstbit(&el.integer as mpir_bindings::mpz_srcptr, bit as u64) == 1
547            }
548        }
549    }
550    
551    fn abs_highest_set_bit(&self, value: &Self::Element) -> Option<usize> {
552        unsafe {
553            if self.is_zero(value) {
554                return None;
555            }
556            Some(mpir_bindings::__gmpz_sizeinbase(&value.integer as mpir_bindings::mpz_srcptr, 2) - 1)
557        }
558    }
559
560    fn abs_lowest_set_bit(&self, value: &Self::Element) -> Option<usize> {
561        unsafe {
562            let result = mpir_bindings::__gmpz_scan1(&value.integer as mpir_bindings::mpz_srcptr, 0);
563            if result == mpir_bindings::mpir_ui::MAX {
564                return None;
565            } else {
566                return Some(result as usize);
567            }
568        }
569    }
570
571    fn rounded_div(&self, lhs: Self::Element, rhs: &Self::Element) -> Self::Element {
572        let mut rhs_half = self.abs(self.clone_el(rhs));
573        self.euclidean_div_pow_2(&mut rhs_half, 1);
574        if self.is_neg(&lhs) {
575            return self.euclidean_div(self.sub(lhs, rhs_half), rhs);
576        } else {
577            return self.euclidean_div(self.add(lhs, rhs_half), rhs);
578        }
579    }
580
581    fn get_uniformly_random_bits<G: FnMut() -> u64>(&self, log2_bound_exclusive: usize, rng: G) -> Self::Element {
582        unsafe {
583            let mut result = MPZEl::new();
584            let len = (log2_bound_exclusive - 1) / u64::BITS as usize + 1;
585            let mut data = Vec::new();
586            data.resize_with(len, rng);
587
588            mpir_bindings::__gmpz_import(
589                &mut result.integer as mpir_bindings::mpz_ptr, 
590                data.len(), 
591                -1i32,
592                (u64::BITS / 8) as libc::size_t,
593                0, 
594                0, 
595                (data.as_ptr() as *const mpir_bindings::mpir_ui) as *const libc::c_void
596            );
597
598            self.euclidean_div_pow_2(&mut result, len * u64::BITS as usize - log2_bound_exclusive);
599            return result;
600        }
601    }
602
603    fn representable_bits(&self) -> Option<usize> {
604        None
605    }
606}
607
608impl_poly_gcd_locally_for_ZZ!{ IntegerPolyGCDRing for MPZBase }
609
610impl FiniteRingSpecializable for MPZBase {
611    
612    fn specialize<O: FiniteRingOperation<Self>>(_op: O) -> Result<O::Output, ()> {
613        Err(())
614    }
615}
616
617impl HashableElRing for MPZBase {
618
619    fn hash<H: std::hash::Hasher>(&self, el: &Self::Element, h: &mut H) {
620        unsafe {
621            <_ as std::hash::Hash>::hash(&(self.is_neg(&el), self.abs_highest_set_bit(&el), mpir_bindings::__gmpz_get_ui(&el.integer as mpir_bindings::mpz_srcptr)), h)
622        }
623    }
624}
625
626impl IntCast<RustBigintRingBase> for MPZBase {
627
628    fn cast(&self, _: &RustBigintRingBase, el: RustBigint) -> Self::Element {
629        let mut result = MPZEl::new();
630        self.from_base_u64_repr(&mut result, &RustBigintRing::RING.get_ring().abs_base_u64_repr(&el).collect::<Vec<_>>()[..]);
631        if RustBigintRing::RING.is_neg(&el) {
632            self.negate_inplace(&mut result);
633        }
634        return result;
635    }
636}
637
638impl IntCast<MPZBase> for RustBigintRingBase {
639
640    fn cast(&self, from: &MPZBase, el: MPZEl) -> RustBigint {
641        let mut result = (0..from.abs_base_u64_repr_len(&el)).map(|_| 0u64).collect::<Vec<_>>();
642        from.abs_base_u64_repr(&el, &mut result[..]);
643        let result = RustBigintRing::RING.get_ring().from_base_u64_repr(result.into_iter());
644        if from.is_neg(&el) {
645            return RustBigintRing::RING.negate(result);
646        } else {
647            return result;
648        }
649    }
650}
651
652impl IntCast<MPZBase> for MPZBase {
653
654    fn cast(&self, _from: &MPZBase, el: MPZEl) -> MPZEl {
655        el
656    }
657}
658
659impl IntCast<StaticRingBase<i64>> for MPZBase {
660
661    fn cast(&self, _: &StaticRingBase<i64>, el: i64) -> Self::Element {
662        unsafe {
663            let mut result = MPZEl::new(); 
664            mpir_bindings::__gmpz_set_si(&mut result.integer as *mut _, el);
665            return result;
666        }
667    }
668}
669
670impl IntCast<MPZBase> for StaticRingBase<i64> {
671
672    fn cast(&self, from: &MPZBase, el: MPZEl) -> i64 {
673        assert!(from.abs_highest_set_bit(&el).unwrap_or(0) < u64::BITS as usize);
674        let negative = from.is_neg(&el);
675        unsafe {
676            let result = mpir_bindings::__gmpz_get_ui(&el.integer as mpir_bindings::mpz_srcptr);
677            if !negative {
678                result.try_into().unwrap()
679            } else if result == i64::MAX as u64 + 1 {
680                i64::MIN
681            } else {
682                -i64::try_from(result).unwrap()
683            }
684        }
685    }
686}
687
688impl IntCast<StaticRingBase<i128>> for MPZBase {
689
690    fn cast(&self, _: &StaticRingBase<i128>, el: i128) -> MPZEl {
691        let el_abs = el.unsigned_abs();
692        let data = [(el_abs & u64::MAX as u128) as u64, (el_abs >> u64::BITS) as u64];
693        let mut result = MPZEl::new();
694        self.from_base_u64_repr(&mut result, &data[..]);
695        if el < 0 {
696            self.negate_inplace(&mut result);
697        }
698        return result;
699    }
700}
701
702impl IntCast<MPZBase> for StaticRingBase<i128> {
703
704    fn cast(&self, from: &MPZBase, el: MPZEl) -> i128 {
705        assert!(from.abs_base_u64_repr_len(&el) <= 2);
706        let mut data = [0u64; 2];
707        from.abs_base_u64_repr(&el, &mut data);
708        let result = data[0] as u128 + ((data[1] as u128) << u64::BITS);
709        if from.is_neg(&el) {
710            if result == i128::MIN.unsigned_abs() {
711                return i128::MIN;
712            } else {
713                return -i128::try_from(result).unwrap();
714            }
715        } else {
716            return result.try_into().unwrap();
717        }
718    }
719}
720
721macro_rules! specialize_int_cast {
722    ($($from:ty),*) => {
723        $(
724            impl IntCast<StaticRingBase<$from>> for MPZBase {
725
726                fn cast(&self, _: &StaticRingBase<$from>, el: $from) -> MPZEl {
727                    int_cast(el as i64, &RingRef::new(self), StaticRing::<i64>::RING)
728                }
729            }
730
731            impl IntCast<MPZBase> for StaticRingBase<$from> {
732
733                fn cast(&self, _: &MPZBase, el: MPZEl) -> $from {
734                    int_cast(el, &StaticRing::<i64>::RING, &MPZ::RING) as $from
735                }
736            }
737        )*
738    }
739}
740
741specialize_int_cast!{ i8, i16, i32 }
742
743#[cfg(test)]
744use crate::pid::EuclideanRingStore;
745use crate::serialization::DeserializeWithRing;
746use crate::serialization::SerializableElementRing;
747
748#[cfg(test)]
749fn edge_case_elements_bigint() -> impl Iterator<Item = RustBigint> {
750    [
751        RustBigintRing::RING.int_hom().map(0),
752        RustBigintRing::RING.int_hom().map(1),
753        RustBigintRing::RING.int_hom().map(-1),
754        RustBigintRing::RING.int_hom().map(7),
755        RustBigintRing::RING.int_hom().map(-7),
756        RustBigintRing::RING.int_hom().map(i32::MAX),
757        RustBigintRing::RING.int_hom().map(i32::MIN),
758        RustBigintRing::RING.power_of_two(64),
759        RustBigintRing::RING.negate(RustBigintRing::RING.power_of_two(64)),
760        RustBigintRing::RING.sub(RustBigintRing::RING.power_of_two(64), RustBigintRing::RING.one()),
761        RustBigintRing::RING.power_of_two(128),
762        RustBigintRing::RING.negate(RustBigintRing::RING.power_of_two(128)),
763        RustBigintRing::RING.sub(RustBigintRing::RING.power_of_two(128), RustBigintRing::RING.one()),
764        RustBigintRing::RING.power_of_two(192),
765        RustBigintRing::RING.negate(RustBigintRing::RING.power_of_two(192)),
766        RustBigintRing::RING.sub(RustBigintRing::RING.power_of_two(192), RustBigintRing::RING.one())
767    ].into_iter()
768}
769
770#[cfg(test)]
771fn edge_case_elements() -> impl Iterator<Item = MPZEl> {
772    edge_case_elements_bigint().map(|n| MPZ::RING.coerce(&RustBigintRing::RING, n))
773}
774
775#[test]
776fn test_negate_inplace() {
777    let mut a = MPZ::RING.power_of_two(64);
778    MPZ::RING.negate_inplace(&mut a);
779    assert!(MPZ::RING.is_neg(&a));
780
781    for a in edge_case_elements() {
782        let mut b = MPZ::RING.clone_el(&a);
783        MPZ::RING.negate_inplace(&mut b);
784        assert!(MPZ::RING.is_zero(&a) || (MPZ::RING.is_neg(&a) ^ MPZ::RING.is_neg(&b)));
785    }
786}
787
788#[test]
789fn test_ring_axioms() {
790    crate::ring::generic_tests::test_ring_axioms(MPZ::RING, edge_case_elements())
791}
792
793#[test]
794fn test_hash_axioms() {
795    crate::ring::generic_tests::test_hash_axioms(MPZ::RING, edge_case_elements());
796}
797
798#[test]
799fn test_divisibility_ring_axioms() {
800    crate::divisibility::generic_tests::test_divisibility_axioms(MPZ::RING, edge_case_elements())
801}
802
803#[test]
804fn test_euclidean_ring_axioms() {
805    crate::pid::generic_tests::test_euclidean_ring_axioms(MPZ::RING, edge_case_elements())
806}
807
808#[test]
809fn test_integer_ring_axioms() {
810    crate::integer::generic_tests::test_integer_axioms(MPZ::RING, edge_case_elements())
811}
812
813#[test]
814fn test_canonical_iso_axioms_i32() {
815    crate::ring::generic_tests::test_hom_axioms(StaticRing::<i32>::RING, MPZ::RING, [0, -1, 1, i16::MAX as i32, i16::MIN as i32].into_iter());
816    crate::ring::generic_tests::test_iso_axioms(StaticRing::<i32>::RING, MPZ::RING, [0, -1, 1, i16::MIN as i32, i16::MAX as i32].into_iter());
817}
818
819#[test]
820fn test_canonical_iso_axioms_i64() {
821    crate::ring::generic_tests::test_hom_axioms(StaticRing::<i64>::RING, MPZ::RING, [0, -1, 1, i32::MAX as i64, i32::MIN as i64].into_iter());
822    crate::ring::generic_tests::test_iso_axioms(StaticRing::<i64>::RING, MPZ::RING, [0, -1, 1, i32::MIN as i64, i32::MAX as i64].into_iter());
823
824    assert_el_eq!(MPZ::RING, MPZ::RING.sub(MPZ::RING.power_of_two(63), MPZ::RING.one()), &MPZ::RING.coerce(&StaticRing::<i64>::RING, i64::MAX));
825    assert_el_eq!(MPZ::RING, MPZ::RING.negate(MPZ::RING.power_of_two(63)), MPZ::RING.coerce(&StaticRing::<i64>::RING, i64::MIN));
826    assert_eq!(i64::MAX, int_cast(MPZ::RING.sub(MPZ::RING.power_of_two(63), MPZ::RING.one()), &StaticRing::<i64>::RING, MPZ::RING));
827    assert_eq!(i64::MIN, int_cast(MPZ::RING.negate(MPZ::RING.power_of_two(63)), &StaticRing::<i64>::RING, MPZ::RING));
828}
829
830#[test]
831fn test_canonical_iso_axioms_i128() {
832    crate::ring::generic_tests::test_hom_axioms(StaticRing::<i128>::RING, MPZ::RING, [0, -1, 1, i64::MAX as i128, i64::MIN as i128].into_iter());
833    crate::ring::generic_tests::test_iso_axioms(StaticRing::<i128>::RING, MPZ::RING, [0, -1, 1, i64::MIN as i128, i64::MAX as i128].into_iter());
834
835    assert_el_eq!(MPZ::RING, MPZ::RING.sub(MPZ::RING.power_of_two(127), MPZ::RING.one()), &MPZ::RING.coerce(&StaticRing::<i128>::RING, i128::MAX));
836    assert_el_eq!(MPZ::RING, MPZ::RING.negate(MPZ::RING.power_of_two(127)), MPZ::RING.coerce(&StaticRing::<i128>::RING, i128::MIN));
837    assert_eq!(i128::MAX, int_cast(MPZ::RING.sub(MPZ::RING.power_of_two(127), MPZ::RING.one()), &StaticRing::<i128>::RING, MPZ::RING));
838    assert_eq!(i128::MIN, int_cast(MPZ::RING.negate(MPZ::RING.power_of_two(127)), &StaticRing::<i128>::RING, MPZ::RING));
839}
840
841#[test]
842fn test_canonical_iso_axioms_bigint() {
843    crate::ring::generic_tests::test_hom_axioms(RustBigintRing::RING, MPZ::RING, edge_case_elements_bigint());
844    crate::ring::generic_tests::test_iso_axioms(RustBigintRing::RING, MPZ::RING, edge_case_elements_bigint());
845}
846
847#[test]
848fn test_abs_is_bit_set() {
849    let a = MPZ::RING.int_hom().map(1 << 15);
850    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 15));
851    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 16));
852    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 14));
853
854    let a = MPZ::RING.int_hom().map(-7);
855    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 0));
856    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 1));
857    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 2));
858    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 3));
859
860    let a = MPZ::RING.int_hom().map(-1 << 15);
861    assert_eq!(true, MPZ::RING.abs_is_bit_set(&a, 15));
862    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 16));
863    assert_eq!(false, MPZ::RING.abs_is_bit_set(&a, 14));
864}
865
866#[test]
867fn test_highest_set_bit() {
868    assert_eq!(None, MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(0)));
869    assert_eq!(Some(0), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(1)));
870    assert_eq!(Some(0), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(-1)));
871    assert_eq!(Some(1), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(2)));
872    assert_eq!(Some(1), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(-2)));
873    assert_eq!(Some(1), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(3)));
874    assert_eq!(Some(1), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(-3)));
875    assert_eq!(Some(2), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(4)));
876    assert_eq!(Some(2), MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(-4)));
877}
878
879#[test]
880fn test_lowest_set_bit() {
881    assert_eq!(None, MPZ::RING.abs_highest_set_bit(&MPZ::RING.int_hom().map(0)));
882    assert_eq!(Some(0), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(1)));
883    assert_eq!(Some(0), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(-1)));
884    assert_eq!(Some(1), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(2)));
885    assert_eq!(Some(1), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(-2)));
886    assert_eq!(Some(0), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(3)));
887    assert_eq!(Some(0), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(-3)));
888    assert_eq!(Some(2), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(4)));
889    assert_eq!(Some(2), MPZ::RING.abs_lowest_set_bit(&MPZ::RING.int_hom().map(-4)));
890}
891
892#[test]
893fn from_to_float_approx() {
894    let x: f64 = 83465209236517892563478156042389675783219532497861237985328563.;
895    let y = MPZ::RING.to_float_approx(&MPZ::RING.from_float_approx(x).unwrap());
896    assert!(x * 0.99 < y);
897    assert!(y < x * 1.01);
898}
899
900#[bench]
901fn bench_mul_300_bits(bencher: &mut test::Bencher) {
902    let x = MPZ::RING.coerce(&RustBigintRing::RING, RustBigintRing::RING.get_ring().parse("2382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754", 10).unwrap());
903    let y = MPZ::RING.coerce(&RustBigintRing::RING, RustBigintRing::RING.get_ring().parse("48937502893645789234569182735646324895723409587234", 10).unwrap());
904    let z = MPZ::RING.coerce(&RustBigintRing::RING, RustBigintRing::RING.get_ring().parse("116588006478839442056346504147013274749794691549803163727888681858469844569693215953808606899770104590589390919543097259495176008551856143726436", 10).unwrap());
905    bencher.iter(|| {
906        let p = MPZ::RING.mul_ref(&x, &y);
907        assert_el_eq!(MPZ::RING, z, p);
908    })
909}
910
911#[bench]
912fn bench_div_300_bits(bencher: &mut test::Bencher) {
913    let x = MPZ::RING.coerce(&RustBigintRing::RING, RustBigintRing::RING.get_ring().parse("2382385687561872365981723456981723456987134659834659813491964132897159283746918732563498628754", 10).unwrap());
914    let y = MPZ::RING.coerce(&RustBigintRing::RING, RustBigintRing::RING.get_ring().parse("48937502893645789234569182735646324895723409587234", 10).unwrap());
915    let z = MPZ::RING.coerce(&RustBigintRing::RING, RustBigintRing::RING.get_ring().parse("116588006478839442056346504147013274749794691549803163727888681858469844569693215953808606899770104590589390919543097259495176008551856143726436", 10).unwrap());
916    bencher.iter(|| {
917        let q = MPZ::RING.euclidean_div(MPZ::RING.clone_el(&z), &y);
918        assert_el_eq!(MPZ::RING, x, q);
919    })
920}
921
922#[test]
923fn test_serialization() {
924    crate::serialization::generic_tests::test_serialization(MPZ::RING, edge_case_elements());
925}
feanor_math/rings/mpir/mod.rs

feanor_math/rings/mpir/
mod.rs
