diff options
Diffstat (limited to 'gf28.cpp')
-rw-r--r-- | gf28.cpp | 143 |
1 files changed, 39 insertions, 104 deletions
@@ -3,117 +3,52 @@ using namespace std; -int GF28::reduce(int v,int m){ - assert(m); - while(true){ - int sh=__builtin_clz(m)-__builtin_clz(v); - if(sh<0)break; - v^=m<<sh; - if(v==0)break; - } - return v; -} - -uint8_t GF28::multiply(uint8_t x,uint8_t y){ - if(x==0||y==0)return 0; - int res=0; - int addend=x; - while(y){ - if(y&1)res^=addend; - addend<<=1; - if(addend&0x100)addend^=modulus; - y>>=1; - } - return res; -} - -GF28::GF28() - :value(0){} - -GF28::GF28(int v) - :value(reduce(v,modulus)){} - -GF28::operator uint8_t() const { - return value; -} - -GF28& GF28::operator+=(GF28 o){ - value^=o.value; - return *this; -} - -GF28& GF28::operator-=(GF28 o){ - value^=o.value; - return *this; -} +namespace GF28 { -GF28& GF28::operator<<=(int n){ - assert(n>=0); - value<<=n; - if(value&0x100)value^=modulus; - return *this; -} - -GF28 GF28::operator+(GF28 o) const { - return GF28(value^o.value); -} + const int modulus=0x11b; -GF28 GF28::operator-(GF28 o) const { - return GF28(value^o.value); -} - -GF28 GF28::operator*(GF28 o) const { - if(value==0||o.value==0)return GF28(0); - GF28 res; - GF28 addend(*this); - while(o.value){ - if(o.value&1)res+=addend; - addend<<=1; - o.value>>=1; + uint8_t reduce(int v,int m){ + assert(v&&m); + while(true){ + int sh=__builtin_clz(m)-__builtin_clz(v); + if(sh<0)break; + v^=m<<sh; + if(v==0)break; + } + return (uint8_t)(unsigned int)v; } - return res; -} -GF28 GF28::operator<<(int n) const { - return GF28(*this)<<=n; -} - -bool GF28::operator==(GF28 o) const { - return value==o.value; -} -GF28 GF28::inverse() const { - if(value==0)return *this; - int x=1,y=0,x2=0,y2=1,r=modulus,r2=value; - while(r2!=0){ - assert(r!=0); - int ex=__builtin_clz(r2)-__builtin_clz(r); - if(ex<0){ - swap(x,x2); - swap(y,y2); - swap(r,r2); - } else { - int xn=x^(x2<<ex); x=x2; x2=xn; - int yn=y^(y2<<ex); y=y2; y2=yn; - int rn=r^(r2<<ex); r=r2; r2=rn; + uint8_t multiply(uint8_t x,uint8_t y){ + if(x==0||y==0)return 0; + int res=0; + int addend=x; + while(y){ + if(y&1)res^=addend; + addend<<=1; + if(addend&0x100)addend^=modulus; + y>>=1; } + return res; } - assert(r==1); - return GF28(y); -} -ostream& operator<<(ostream &os,GF28 p){ - if(os.flags()&ios_base::hex){ - return os<<p.value; - } - if(p.value==0)return os<<'0'; - bool first=true; - for(int m=1<<16,i=16;m!=0;m>>=1,i--){ - if(p.value&m){ - if(!first)os<<'+'; - first=false; - if(i==0)os<<'1'; - else os<<"x^"<<i; + uint8_t inverse(uint8_t value){ + if(value==0)return value; + int x=1,y=0,x2=0,y2=1,r=modulus,r2=value; + while(r2!=0){ + assert(r!=0); + int ex=__builtin_clz(r2)-__builtin_clz(r); + if(ex<0){ + swap(x,x2); + swap(y,y2); + swap(r,r2); + } else { + int xn=x^(x2<<ex); x=x2; x2=xn; + int yn=y^(y2<<ex); y=y2; y2=yn; + int rn=r^(r2<<ex); r=r2; r2=rn; + } } + assert(r==1); + return reduce(y,modulus); } - return os; + } |