diff options
| -rw-r--r-- | bigint.cpp | 61 | ||||
| -rw-r--r-- | bigint.h | 41 | ||||
| -rw-r--r-- | gf28.cpp | 4 |
3 files changed, 59 insertions, 47 deletions
@@ -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())a.digits.resize(b.digits.size()); int sz=a.digits.size(); @@ -77,12 +79,13 @@ void Bigint::add(Bigint &a,const Bigint &b){ a.checkconsistent(); } +//ignores sign of arguments void Bigint::subtract(Bigint &a,const Bigint &b){ if(a.digits.size()<b.digits.size()){ a.digits.resize(b.digits.size()); //adds zeros } assert(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<b //we do a fake 2s complement, sort of carry=0; for(int i=0;i<sz;i++){ @@ -112,6 +115,10 @@ void Bigint::subtract(Bigint &a,const Bigint &b){ a.checkconsistent(); } +//This is simple O(n^2) multiplication, with no optimisation for a==b. Also, no Karatsuba here. +//This works and is simple (KISS), but doesn't perform that well. In fact, it seems to be the +//bottleneck of the entire bigint implementation (through its use divmod, which is used A LOT +//for modulo in RSA). Bigint Bigint::product(const Bigint &a,const Bigint &b){ int asz=a.digits.size(),bsz=b.digits.size(); if(asz==0||bsz==0)return Bigint(); @@ -155,9 +162,10 @@ void Bigint::checkconsistent(){ Bigint& Bigint::operator=(Bigint &&o){ sign=o.sign; digits=move(o.digits); - o.normalise(); + o.sign=1; normalise(); checkconsistent(); + o.checkconsistent(); return *this; } @@ -207,7 +215,7 @@ Bigint& Bigint::operator=(digit_t v){ } Bigint& Bigint::operator+=(const Bigint &o){ - if(&o==this){ //*this + *this + if(&o==this){ //*this + *this = *this<<1 operator<<=(1); return *this; } @@ -223,7 +231,7 @@ Bigint& Bigint::operator+=(const Bigint &o){ } Bigint& Bigint::operator-=(const Bigint &o){ - if(&o==this){ // *this - *this + if(&o==this){ // *this - *this = 0 sign=1; digits.clear(); return *this; @@ -253,8 +261,8 @@ Bigint& Bigint::operator*=(slongdigit_t n){return *this*=Bigint(n);} 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 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<sz;i++){ digits[i-1]|=digits[i]<<(digit_bits-sh); @@ -334,7 +342,6 @@ Bigint Bigint::operator>>(int sh) const { } pair<Bigint,Bigint> Bigint::divmod(const Bigint &div) const { - // cerr<<"divmod("<<hex<<*this<<','<<div<<dec<<')'<<endl; int bitcdiff=bitcount()-div.bitcount(); if(bitcdiff<0)bitcdiff=0; pair<Bigint,Bigint> p=divmod(div,1,bitcdiff/29+10); //ignores all signs @@ -373,9 +380,11 @@ pair<Bigint,Bigint> 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,Bigint> Bigint::divmod(const Bigint &div,int depth,int maxdepth) const { - if(depth>maxdepth)assert(false); - // cerr<<"divmod("<<hex<<*this<<','<<div<<dec<<") depth="<<depth<<" maxdepth="<<maxdepth<<endl; + if(depth>maxdepth)assert(false); //Sanity check if(div.digits.size()==0)throw domain_error("Bigint divide by zero"); if(digits.size()==0)return make_pair(Bigint::zero,Bigint::zero); @@ -399,7 +408,7 @@ pair<Bigint,Bigint> 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]<<spill); @@ -508,6 +517,7 @@ bool Bigint::odd() const { return !even(); } +//Produces a string with the bytes of the mantissa in little-endian order. string Bigint::serialiseMantissa() const { string s; s.resize(digits.size()*sizeof(digit_t)); @@ -520,6 +530,7 @@ string Bigint::serialiseMantissa() const { return s; } +//Inverse of serialiseMantissa void Bigint::deserialiseMantissa(const string &s){ if(s.size()%sizeof(digit_t)!=0)throw invalid_argument("Not a serialised Bigint"); sign=1; @@ -550,10 +561,6 @@ vector<bool> 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){ @@ -6,24 +6,30 @@ #include <utility> #include <cstdint> +//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<digit_t> digits; - int sign; + std::vector<digit_t> 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<Bigint,Bigint> 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<bool> bits() const; + void deserialiseMantissa(const std::string&); //restores non-negative number; can throw invalid_argument + std::vector<bool> 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 @@ -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; |