aboutsummaryrefslogtreecommitdiff
path: root/gf28.cpp
diff options
context:
space:
mode:
Diffstat (limited to 'gf28.cpp')
-rw-r--r--gf28.cpp119
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;
+}