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

competitive/algebra/
ring_operations.rs
