aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
-rw-r--r--bigint.cpp61
-rw-r--r--bigint.h41
-rw-r--r--gf28.cpp4
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;