diff options
author | tomsmeding <tom.smeding@gmail.com> | 2016-10-12 23:10:29 +0200 |
---|---|---|
committer | tomsmeding <tom.smeding@gmail.com> | 2016-10-12 23:10:29 +0200 |
commit | 9a337c68ff0ac8c1cd18be2917318f273af7d8a0 (patch) | |
tree | 5f774032d13f434e45466071381c9e010e8be680 /bigint.cpp | |
parent | b9fd7bda32613c44bbf11d9c019d0c28e70c4064 (diff) |
Comment bigint (and fix indentation in gf28)
Diffstat (limited to 'bigint.cpp')
-rw-r--r-- | bigint.cpp | 61 |
1 files changed, 34 insertions, 27 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){ |