// codesnip-guard: BarrettReduction
#[cfg_attr(any(),rustfmt::skip)]pub use self::barrett_reduction::{BarrettReduction,Barrettable};#[cfg_attr(any(),rustfmt::skip)]mod barrett_reduction{use super::{One,Zero};use std::ops::{Add,Mul,Sub};#[derive(Debug,Clone,Copy)]pub struct BarrettReduction<T>{m:T,im:T}impl<T>BarrettReduction<T>where T:Barrettable{pub fn new(m:T)->Self{Self{m,im:T::inv_mod_approx(m)}}pub const fn new_with_im(m:T,im:T)->Self{Self{m,im}}pub const fn get_mod(&self)->T{self.m}pub fn div_rem(&self,a:T)->(T,T){T::barrett_reduce(a,self.m,self.im)}pub fn div(&self,a:T)->T{self.div_rem(a).0}pub fn rem(&self,a:T)->T{self.div_rem(a).1}}pub trait Barrettable:Sized+Copy+PartialOrd+Zero+One+Add<Output=Self>+Sub<Output=Self>+Mul<Output=Self>{fn inv_mod_approx(m:Self)->Self;fn div_approx(self,im:Self)->Self;fn barrett_reduce(self,m:Self,im:Self)->(Self,Self){if m==Self::one(){return(self,Self::zero());}let q=self.div_approx(im);let r=self-q*m;if m<=r{(q+Self::one(),r-m)}else{(q,r)}}}impl Barrettable for u32{fn inv_mod_approx(m:Self)->Self{!0/m}fn div_approx(self,im:Self)->Self{((self as u64*im as u64)>>32)as u32}}impl Barrettable for u64{fn inv_mod_approx(m:Self)->Self{!0/m}fn div_approx(self,im:Self)->Self{((self as u128*im as u128)>>64)as u64}}impl Barrettable for u128{fn inv_mod_approx(m:Self)->Self{!0/m}fn div_approx(self,im:Self)->Self{const MASK64:u128=0xffff_ffff_ffff_ffff;let au=self>>64;let ad=self&MASK64;let imu=im>>64;let imd=im&MASK64;let res=au*imu;let x=((ad*imd)>>64)+au*imd;let(x,c)=x.overflowing_add(ad*imu);res+((c as u128)<<64)+(x>>64)}}}
// codesnip-guard: zero_one
#[cfg_attr(any(),rustfmt::skip)]pub use self::zero_one::{One,Zero};#[cfg_attr(any(),rustfmt::skip)]mod zero_one{pub trait Zero:Sized{fn zero()->Self;#[inline]fn is_zero(&self)->bool where Self:PartialEq{self==&Self::zero()}#[inline]fn set_zero(&mut self){*self=Self::zero();}}pub trait One:Sized{fn one()->Self;#[inline]fn is_one(&self)->bool where Self:PartialEq{self==&Self::one()}#[inline]fn set_one(&mut self){*self=Self::one();}}macro_rules!impl_zero_one{($({$(<$T:ident:$Bound:ident>)?$Trait:ident$method:ident$($t:ty)*,$e:expr})*)=>{$(impl_zero_one!(@impl[$(<$T:$Bound>)?]$Trait$method[$($t)*],$e);)*};(@impl[<$T:ident:$Bound:ident>]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl<$T:$Bound>$Trait for$t{fn$method()->Self{$e}})*};(@impl[]$Trait:ident$method:ident[$($t:ty)*],$e:expr)=>{$(impl$Trait for$t{fn$method()->Self{$e}})*};}impl_zero_one!({Zero zero u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,0}{Zero zero f32 f64,0.}{One one u8 u16 u32 u64 usize i8 i16 i32 i64 isize u128 i128,1}{One one f32 f64,1.}{<T:Zero>Zero zero std::num::Wrapping<T>,Self(T::zero())}{<T:One>One one std::num::Wrapping<T>,Self(T::one())});}