From 9a337c68ff0ac8c1cd18be2917318f273af7d8a0 Mon Sep 17 00:00:00 2001 From: tomsmeding Date: Wed, 12 Oct 2016 23:10:29 +0200 Subject: Comment bigint (and fix indentation in gf28) --- bigint.cpp | 61 ++++++++++++++++++++++++++++++++++--------------------------- bigint.h | 41 +++++++++++++++++++++++------------------ gf28.cpp | 4 ++-- 3 files changed, 59 insertions(+), 47 deletions(-) diff --git a/bigint.cpp b/bigint.cpp index c25a2c1..7c9fec7 100644 --- a/bigint.cpp +++ b/bigint.cpp @@ -14,12 +14,13 @@ Bigint Bigint::one(1); Bigint Bigint::two(2); Bigint::Bigint() - :sign(1){} + :sign(1){} Bigint::Bigint(Bigint &&o) - :digits(move(o.digits)),sign(o.sign){ - o.normalise(); + :digits(move(o.digits)),sign(o.sign){ + o.sign=1; checkconsistent(); + o.checkconsistent(); } Bigint::Bigint(const string &repr){ @@ -28,7 +29,7 @@ Bigint::Bigint(const string &repr){ } Bigint::Bigint(slongdigit_t v) - :digits(1,abs(v)),sign(v>=0?1:-1){ + :digits(1,abs(v)),sign(v>=0?1:-1){ static_assert(sizeof(longdigit_t)==2*sizeof(digit_t), "longdigit_t should be twice as large as digit_t"); v=abs(v); @@ -41,14 +42,14 @@ Bigint::Bigint(slongdigit_t v) } Bigint::Bigint(longdigit_t v) - :digits(1,(digit_t)v),sign(1){ + :digits(1,(digit_t)v),sign(1){ if(v>digits[0])digits.push_back(v>>digit_bits); else if(v==0)digits.clear(); checkconsistent(); } Bigint::Bigint(sdigit_t v) - :digits(1,abs(v)),sign(v>=0?1:-1){ + :digits(1,abs(v)),sign(v>=0?1:-1){ if(v==0){ digits.clear(); sign=1; @@ -57,11 +58,12 @@ Bigint::Bigint(sdigit_t v) } Bigint::Bigint(digit_t v) - :digits(1,v),sign(1){ + :digits(1,v),sign(1){ if(v==0)digits.clear(); checkconsistent(); } +//ignores sign of arguments void Bigint::add(Bigint &a,const Bigint &b){ if(a.digits.size()=b.digits.size()); - if(a.digits.size()==0){ + if(a.digits.size()==0){ //then a==b==0 a.checkconsistent(); return; } @@ -97,7 +100,7 @@ void Bigint::subtract(Bigint &a,const Bigint &b){ carry=(bdig||carry)&&res>=adig; a.digits[i]=res; } - if(carry){ + if(carry){ //Apparently, a>=-sh; - if(sh/digit_bits>0){ + if(sh<0)return *this>>=-sh; //we support negative shifting + if(sh/digit_bits>0){ //first shift by a multiple of our digit size, since that's easy digits.insert(digits.begin(),sh/digit_bits,0); sh%=digit_bits; if(sh==0){ @@ -262,7 +270,7 @@ Bigint& Bigint::operator<<=(int sh){ return *this; } } - digits.push_back(0); + digits.push_back(0); //afterwards, shift by the remaining amount for(int i=digits.size()-2;i>=0;i--){ digits[i+1]|=digits[i]>>(digit_bits-sh); digits[i]<<=sh; @@ -276,8 +284,8 @@ Bigint& Bigint::operator<<=(int sh){ Bigint& Bigint::operator>>=(int sh){ if(sh==0)return *this; if(digits.size()==0)return *this; - if(sh<0)return *this<<=-sh; - if(sh/digit_bits>0){ + if(sh<0)return *this<<=-sh; //we support negative shifting + if(sh/digit_bits>0){ //first shift by a multiple of our digit size, since that's easy if(sh/digit_bits>=(int)digits.size()){ digits.clear(); sign=1; @@ -291,7 +299,7 @@ Bigint& Bigint::operator>>=(int sh){ return *this; } } - digits[0]>>=sh; + digits[0]>>=sh; //afterwards, shift by the remaining amount int sz=digits.size(); for(int i=1;i>(int sh) const { } pair Bigint::divmod(const Bigint &div) const { - // cerr<<"divmod("< p=divmod(div,1,bitcdiff/29+10); //ignores all signs @@ -373,9 +380,11 @@ pair Bigint::divmod(const Bigint &div) const { } //ignores all signs, and always returns positive numbers! +//This function is opaque and way more complicated than it should be. Sorry for that. +//Strategy: find a quotient (and guess=quotient*div) such that guess<=*this, but *this-guess +//is small. Then subtract guess from *this, and repeat. pair Bigint::divmod(const Bigint &div,int depth,int maxdepth) const { - if(depth>maxdepth)assert(false); - // cerr<<"divmod("< Bigint::divmod(const Bigint &div,int depth,int maxdepth) con return make_pair( Bigint((slongdigit_t)(thisnum/divnum)), Bigint((slongdigit_t)(thisnum%divnum))); - } else if(divbtc>=digit_bits){ //the large case + } else if(divbtc>=digit_bits){ //both *this and div are large //take 2*digit_bits of *this and 1*digit_bits of div; quotient gives a good guess int spill=__builtin_clz(digits.back()); longdigit_t thishead2=((longdigit_t)digits.back()<<(spill+digit_bits))|((longdigit_t)digits[digits.size()-2]< Bigint::bits() const { return v; } -Bigint::digit_t Bigint::_digit(int idx) const { - return digits.at(idx); -} - istream& operator>>(istream &is,Bigint &b){ while(isspace(is.peek()))is.get(); if(!is)return is; @@ -567,7 +574,7 @@ istream& operator>>(istream &is,Bigint &b){ bool acted=false; if(is.peek()=='0'){ is.get(); - if(is.peek()=='x'){ + if(is.peek()=='x'){ //hex value is.get(); acted=false; while(true){ diff --git a/bigint.h b/bigint.h index a3c5be3..cff7bd4 100644 --- a/bigint.h +++ b/bigint.h @@ -6,24 +6,30 @@ #include #include +//A bigint implementation based on unsigned 32-bit digits. +//The implementation relies on having native 64-bit arithmetic (or specifically, +//(2*digit_bits)-bit arithmetic). class Bigint{ public: typedef uint32_t digit_t; - typedef int32_t sdigit_t; - typedef uint64_t longdigit_t; - typedef int64_t slongdigit_t; + typedef int32_t sdigit_t; //signed version + typedef uint64_t longdigit_t; //should be twice as large as digit_t + typedef int64_t slongdigit_t; //signed version static const int digit_bits=8*sizeof(digit_t); private: - std::vector digits; - int sign; + std::vector digits; //little-endian order + int sign; //-1 for negative, 1 for positive; -0 is not a valid state static void add(Bigint&,const Bigint&); //ignores sign of arguments - static void subtract(Bigint&,const Bigint&); //ignores sign of arguments; assumes a>=b + static void subtract(Bigint&,const Bigint&); //ignores sign of arguments static Bigint product(const Bigint&,const Bigint&); - void shrink(); - void normalise(); + void shrink(); //prune unnecessary zero digits on top + void normalise(); //make sure -0 doesn't occur + + //This function is called from all relevant return points of the member functions. It's + //basically a debug check, but it can't hurt to have it since it takes few cpu cycles. void checkconsistent(); std::pair divmod(const Bigint&,int depth,int maxdepth) const; //ignores all signs @@ -32,8 +38,9 @@ public: Bigint(); Bigint(const Bigint&)=default; Bigint(Bigint&&); - explicit Bigint(const std::string&); - explicit Bigint(sdigit_t); + + explicit Bigint(const std::string&); //Initialise with a large value + explicit Bigint(sdigit_t); //Initialise with a small value explicit Bigint(digit_t); explicit Bigint(slongdigit_t); explicit Bigint(longdigit_t); @@ -54,6 +61,8 @@ public: Bigint& operator<<=(int); Bigint& operator>>=(int); Bigint& negate(); + //Division and modulo operators are explicitly NOT included, to promote clever usage + //of the divmod function, which combines both. Bigint operator+(const Bigint&) const; Bigint operator-(const Bigint&) const; @@ -93,22 +102,18 @@ public: bool odd() const; std::string serialiseMantissa() const; //stores everything but the sign - - //restores non-negative number; can throw invalid_argument - void deserialiseMantissa(const std::string&); - std::vector bits() const; + void deserialiseMantissa(const std::string&); //restores non-negative number; can throw invalid_argument + std::vector bits() const; //Stores bits in little-endian order friend std::istream& operator>>(std::istream&,Bigint&); friend std::ostream& operator<<(std::ostream&,Bigint); - digit_t _digit(int idx) const; - - static Bigint mone; + static Bigint mone; //Some small values to save a constructor call static Bigint zero; static Bigint one; static Bigint two; }; std::istream& operator>>(std::istream&,Bigint&); -std::ostream& operator<<(std::ostream&,Bigint); +std::ostream& operator<<(std::ostream&,Bigint); //The output operator supports the `hex` modifier diff --git a/gf28.cpp b/gf28.cpp index 61f47b1..9513818 100644 --- a/gf28.cpp +++ b/gf28.cpp @@ -28,10 +28,10 @@ uint8_t GF28::multiply(uint8_t x,uint8_t y){ } GF28::GF28() - :value(0){} + :value(0){} GF28::GF28(int v) - :value(reduce(v,modulus)){} + :value(reduce(v,modulus)){} GF28::operator uint8_t() const { return value; -- cgit v1.2.3-54-g00ecf