Comment bigint (and fix indentation in gf28)

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())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){
diff --git a/bigint.h b/bigint.h
index a3c5be3..cff7bd4 100644
--- a/bigint.h
+++ b/bigint.h
@@ -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
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;