competitive/algebra/
ring_operations.rs

1use super::{magma::*, operations::BitXorOperation, ring::*};
2
3#[codesnip::entry("Gf2_63")]
4pub use self::gf2_63::Gf2_63;
5#[codesnip::entry("Gf2_63", include("BitXorOperation", "ring"))]
6mod gf2_63 {
7    use super::*;
8    pub enum Gf2_63 {}
9    impl Gf2_63 {
10        pub const MOD: u64 = 1 << 63;
11    }
12    impl Magma for Gf2_63 {
13        type T = u64;
14        fn operate(x: &Self::T, y: &Self::T) -> Self::T {
15            #[cfg(target_arch = "x86_64")]
16            {
17                use core::arch::x86_64::{_mm_clmulepi64_si128, _mm_extract_epi64, _mm_set_epi64x};
18                unsafe {
19                    let a = _mm_set_epi64x(0, *x as i64);
20                    let b = _mm_set_epi64x(0, *y as i64);
21                    let c = _mm_clmulepi64_si128(a, b, 0);
22                    let lo = _mm_extract_epi64(c, 0) as u64;
23                    let hi = _mm_extract_epi64(c, 1) as u64;
24                    let hi = (hi << 1) | (lo >> 63);
25                    let lo = lo & !(!(0u64) << 63);
26                    lo ^ hi ^ (hi << 1)
27                }
28            }
29            #[cfg(not(target_arch = "x86_64"))]
30            {
31                let x = *x as u128;
32                let mut bit = 0u128;
33                for i in 0u32..63 {
34                    if y >> i & 1 != 0 {
35                        bit ^= x << i;
36                    }
37                }
38                let hi = (bit >> 64) as u64;
39                let lo = (bit & ((1 << 64) - 1)) as u64;
40                let hi = (hi << 1) | (lo >> 63);
41                let lo = lo & !(!(0u64) << 63);
42                lo ^ hi ^ (hi << 1)
43            }
44        }
45    }
46    impl Unital for Gf2_63 {
47        fn unit() -> Self::T {
48            1
49        }
50    }
51    impl Associative for Gf2_63 {}
52    impl Commutative for Gf2_63 {}
53    impl SemiRing for Gf2_63 {
54        type T = u64;
55        type Additive = BitXorOperation<u64>;
56        type Multiplicative = Self;
57    }
58}
59
60#[codesnip::entry("Mersenne61")]
61pub use self::mersenne61::Mersenne61;
62#[codesnip::entry("Mersenne61", include("ring"))]
63mod mersenne61 {
64    use super::*;
65    pub enum Mersenne61Add {}
66    impl Magma for Mersenne61Add {
67        type T = u64;
68        fn operate(x: &Self::T, y: &Self::T) -> Self::T {
69            let mut z = x + y;
70            if z >= Mersenne61::MOD {
71                z -= Mersenne61::MOD
72            }
73            z
74        }
75    }
76    impl Unital for Mersenne61Add {
77        fn unit() -> Self::T {
78            0
79        }
80    }
81    impl Associative for Mersenne61Add {}
82    impl Commutative for Mersenne61Add {}
83    impl Invertible for Mersenne61Add {
84        fn inverse(x: &Self::T) -> Self::T {
85            if *x == 0 { 0 } else { Mersenne61::MOD - x }
86        }
87    }
88
89    pub enum Mersenne61 {}
90    impl Mersenne61 {
91        pub const MOD: u64 = (1 << 61) - 1;
92    }
93    impl Magma for Mersenne61 {
94        type T = u64;
95        fn operate(x: &Self::T, y: &Self::T) -> Self::T {
96            let z = *x as u128 * *y as u128;
97            Mersenne61Add::operate(&((z >> 61) as _), &(z as u64 & Self::MOD))
98        }
99    }
100    impl Unital for Mersenne61 {
101        fn unit() -> Self::T {
102            1
103        }
104    }
105    impl Associative for Mersenne61 {}
106    impl Commutative for Mersenne61 {}
107    impl SemiRing for Mersenne61 {
108        type T = u64;
109        type Additive = Mersenne61Add;
110        type Multiplicative = Self;
111    }
112}
competitive/algebra/ring_operations.rs

competitive/algebra/
ring_operations.rs
