diff options
Diffstat (limited to 'gf28.cpp')
-rw-r--r-- | gf28.cpp | 119 |
1 files changed, 119 insertions, 0 deletions
diff --git a/gf28.cpp b/gf28.cpp new file mode 100644 index 0000000..e65c20a --- /dev/null +++ b/gf28.cpp @@ -0,0 +1,119 @@ +#include <cassert> +#include "gf28.h" + +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; +} + +GF28& GF28::operator<<=(int n){ //multiplication by x^n + assert(n>=0); + value<<=n; + if(value&0x100)value^=modulus; + return *this; +} + +GF28 GF28::operator+(GF28 o) const { + return GF28(value^o.value); +} + +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; + } + 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; + } + } + 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; + } + } + return os; +} |