diff options
Diffstat (limited to 'ml/dlib/dlib/bigint')
| -rw-r--r-- | ml/dlib/dlib/bigint/bigint_kernel_1.cpp | 1720 | ||||
| -rw-r--r-- | ml/dlib/dlib/bigint/bigint_kernel_1.h | 544 | ||||
| -rw-r--r-- | ml/dlib/dlib/bigint/bigint_kernel_2.cpp | 1945 | ||||
| -rw-r--r-- | ml/dlib/dlib/bigint/bigint_kernel_2.h | 570 | ||||
| -rw-r--r-- | ml/dlib/dlib/bigint/bigint_kernel_abstract.h | 670 | ||||
| -rw-r--r-- | ml/dlib/dlib/bigint/bigint_kernel_c.h | 1141 |
6 files changed, 6590 insertions, 0 deletions
diff --git a/ml/dlib/dlib/bigint/bigint_kernel_1.cpp b/ml/dlib/dlib/bigint/bigint_kernel_1.cpp new file mode 100644 index 000000000..feef761c2 --- /dev/null +++ b/ml/dlib/dlib/bigint/bigint_kernel_1.cpp @@ -0,0 +1,1720 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_BIGINT_KERNEL_1_CPp_ +#define DLIB_BIGINT_KERNEL_1_CPp_ +#include "bigint_kernel_1.h" + +#include <iostream> + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // member/friend function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1:: + bigint_kernel_1 ( + ) : + slack(25), + data(new data_record(slack)) + {} + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1:: + bigint_kernel_1 ( + uint32 value + ) : + slack(25), + data(new data_record(slack)) + { + *(data->number) = static_cast<uint16>(value&0xFFFF); + *(data->number+1) = static_cast<uint16>((value>>16)&0xFFFF); + if (*(data->number+1) != 0) + data->digits_used = 2; + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1:: + bigint_kernel_1 ( + const bigint_kernel_1& item + ) : + slack(25), + data(item.data) + { + data->references += 1; + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1:: + ~bigint_kernel_1 ( + ) + { + if (data->references == 1) + { + delete data; + } + else + { + data->references -= 1; + } + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 bigint_kernel_1:: + operator+ ( + const bigint_kernel_1& rhs + ) const + { + data_record* temp = new data_record ( + std::max(rhs.data->digits_used,data->digits_used) + slack + ); + long_add(data,rhs.data,temp); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator+= ( + const bigint_kernel_1& rhs + ) + { + // if there are other references to our data + if (data->references != 1) + { + data_record* temp = new data_record(std::max(data->digits_used,rhs.data->digits_used)+slack); + data->references -= 1; + long_add(data,rhs.data,temp); + data = temp; + } + // if data is not big enough for the result + else if (data->size <= std::max(data->digits_used,rhs.data->digits_used)) + { + data_record* temp = new data_record(std::max(data->digits_used,rhs.data->digits_used)+slack); + long_add(data,rhs.data,temp); + delete data; + data = temp; + } + // there is enough size and no references + else + { + long_add(data,rhs.data,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 bigint_kernel_1:: + operator- ( + const bigint_kernel_1& rhs + ) const + { + data_record* temp = new data_record ( + data->digits_used + slack + ); + long_sub(data,rhs.data,temp); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator-= ( + const bigint_kernel_1& rhs + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + long_sub(data,rhs.data,temp); + data = temp; + } + else + { + long_sub(data,rhs.data,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 bigint_kernel_1:: + operator* ( + const bigint_kernel_1& rhs + ) const + { + data_record* temp = new data_record ( + data->digits_used + rhs.data->digits_used + slack + ); + long_mul(data,rhs.data,temp); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator*= ( + const bigint_kernel_1& rhs + ) + { + // create a data_record to store the result of the multiplication in + data_record* temp = new data_record(rhs.data->digits_used+data->digits_used+slack); + long_mul(data,rhs.data,temp); + + // if there are other references to data + if (data->references != 1) + { + data->references -= 1; + } + else + { + delete data; + } + data = temp; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 bigint_kernel_1:: + operator/ ( + const bigint_kernel_1& rhs + ) const + { + data_record* temp = new data_record(data->digits_used+slack); + data_record* remainder; + try { + remainder = new data_record(data->digits_used+slack); + } catch (...) { delete temp; throw; } + + long_div(data,rhs.data,temp,remainder); + delete remainder; + + + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator/= ( + const bigint_kernel_1& rhs + ) + { + + data_record* temp = new data_record(data->digits_used+slack); + data_record* remainder; + try { + remainder = new data_record(data->digits_used+slack); + } catch (...) { delete temp; throw; } + + long_div(data,rhs.data,temp,remainder); + + // check if there are other references to data + if (data->references != 1) + { + data->references -= 1; + } + // if there are no references to data then it must be deleted + else + { + delete data; + } + data = temp; + delete remainder; + + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 bigint_kernel_1:: + operator% ( + const bigint_kernel_1& rhs + ) const + { + data_record* temp = new data_record(data->digits_used+slack); + data_record* remainder; + try { + remainder = new data_record(data->digits_used+slack); + } catch (...) { delete temp; throw; } + + long_div(data,rhs.data,temp,remainder); + delete temp; + return bigint_kernel_1(remainder,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator%= ( + const bigint_kernel_1& rhs + ) + { + data_record* temp = new data_record(data->digits_used+slack); + data_record* remainder; + try { + remainder = new data_record(data->digits_used+slack); + } catch (...) { delete temp; throw; } + + long_div(data,rhs.data,temp,remainder); + + // check if there are other references to data + if (data->references != 1) + { + data->references -= 1; + } + // if there are no references to data then it must be deleted + else + { + delete data; + } + data = remainder; + delete temp; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + bool bigint_kernel_1:: + operator < ( + const bigint_kernel_1& rhs + ) const + { + return is_less_than(data,rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + bool bigint_kernel_1:: + operator == ( + const bigint_kernel_1& rhs + ) const + { + return is_equal_to(data,rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator= ( + const bigint_kernel_1& rhs + ) + { + if (this == &rhs) + return *this; + + // if we have the only reference to our data then delete it + if (data->references == 1) + { + delete data; + data = rhs.data; + data->references += 1; + } + else + { + data->references -= 1; + data = rhs.data; + data->references += 1; + } + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + std::ostream& operator<< ( + std::ostream& out_, + const bigint_kernel_1& rhs + ) + { + std::ostream out(out_.rdbuf()); + + typedef bigint_kernel_1 bigint; + + bigint::data_record* temp = new bigint::data_record(*rhs.data,0); + + + + // get a char array big enough to hold the number in ascii format + char* str; + try { + str = new char[(rhs.data->digits_used)*5+10]; + } catch (...) { delete temp; throw; } + + char* str_start = str; + str += (rhs.data->digits_used)*5+9; + *str = 0; --str; + + + uint16 remainder; + rhs.short_div(temp,10000,temp,remainder); + + // pull the digits out of remainder + char a = remainder % 10 + '0'; + remainder /= 10; + char b = remainder % 10 + '0'; + remainder /= 10; + char c = remainder % 10 + '0'; + remainder /= 10; + char d = remainder % 10 + '0'; + remainder /= 10; + + + *str = a; --str; + *str = b; --str; + *str = c; --str; + *str = d; --str; + + + // keep looping until temp represents zero + while (temp->digits_used != 1 || *(temp->number) != 0) + { + rhs.short_div(temp,10000,temp,remainder); + + // pull the digits out of remainder + char a = remainder % 10 + '0'; + remainder /= 10; + char b = remainder % 10 + '0'; + remainder /= 10; + char c = remainder % 10 + '0'; + remainder /= 10; + char d = remainder % 10 + '0'; + remainder /= 10; + + *str = a; --str; + *str = b; --str; + *str = c; --str; + *str = d; --str; + } + + // throw away and extra leading zeros + ++str; + if (*str == '0') + ++str; + if (*str == '0') + ++str; + if (*str == '0') + ++str; + + + + + out << str; + delete [] str_start; + delete temp; + return out_; + + } + +// ---------------------------------------------------------------------------------------- + + std::istream& operator>> ( + std::istream& in_, + bigint_kernel_1& rhs + ) + { + std::istream in(in_.rdbuf()); + + // ignore any leading whitespaces + while (in.peek() == ' ' || in.peek() == '\t' || in.peek() == '\n') + { + in.get(); + } + + // if the first digit is not an integer then this is an error + if ( !(in.peek() >= '0' && in.peek() <= '9')) + { + in_.clear(std::ios::failbit); + return in_; + } + + int num_read; + bigint_kernel_1 temp; + do + { + + // try to get 4 chars from in + num_read = 1; + char a = 0; + char b = 0; + char c = 0; + char d = 0; + + if (in.peek() >= '0' && in.peek() <= '9') + { + num_read *= 10; + a = in.get(); + } + if (in.peek() >= '0' && in.peek() <= '9') + { + num_read *= 10; + b = in.get(); + } + if (in.peek() >= '0' && in.peek() <= '9') + { + num_read *= 10; + c = in.get(); + } + if (in.peek() >= '0' && in.peek() <= '9') + { + num_read *= 10; + d = in.get(); + } + + // merge the for digits into an uint16 + uint16 num = 0; + if (a != 0) + { + num = a - '0'; + } + if (b != 0) + { + num *= 10; + num += b - '0'; + } + if (c != 0) + { + num *= 10; + num += c - '0'; + } + if (d != 0) + { + num *= 10; + num += d - '0'; + } + + + if (num_read != 1) + { + // shift the digits in temp left by the number of new digits we just read + temp *= num_read; + // add in new digits + temp += num; + } + + } while (num_read == 10000); + + + rhs = temp; + return in_; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator+ ( + uint16 lhs, + const bigint_kernel_1& rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record + (rhs.data->digits_used+rhs.slack); + + rhs.short_add(rhs.data,lhs,temp); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator+ ( + const bigint_kernel_1& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record + (lhs.data->digits_used+lhs.slack); + + lhs.short_add(lhs.data,rhs,temp); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator+= ( + uint16 rhs + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_add(data,rhs,temp); + data = temp; + } + // or if we need to enlarge data then do so + else if (data->digits_used == data->size) + { + data_record* temp = new data_record(data->digits_used+slack); + short_add(data,rhs,temp); + delete data; + data = temp; + } + // or if there is plenty of space and no references + else + { + short_add(data,rhs,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator- ( + uint16 lhs, + const bigint_kernel_1& rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record(rhs.slack); + + *(temp->number) = lhs - *(rhs.data->number); + + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator- ( + const bigint_kernel_1& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record + (lhs.data->digits_used+lhs.slack); + + lhs.short_sub(lhs.data,rhs,temp); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator-= ( + uint16 rhs + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_sub(data,rhs,temp); + data = temp; + } + else + { + short_sub(data,rhs,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator* ( + uint16 lhs, + const bigint_kernel_1& rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record + (rhs.data->digits_used+rhs.slack); + + rhs.short_mul(rhs.data,lhs,temp); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator* ( + const bigint_kernel_1& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record + (lhs.data->digits_used+lhs.slack); + + lhs.short_mul(lhs.data,rhs,temp); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator*= ( + uint16 rhs + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_mul(data,rhs,temp); + data = temp; + } + // or if we need to enlarge data + else if (data->digits_used == data->size) + { + data_record* temp = new data_record(data->digits_used+slack); + short_mul(data,rhs,temp); + delete data; + data = temp; + } + else + { + short_mul(data,rhs,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator/ ( + uint16 lhs, + const bigint_kernel_1& rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record(rhs.slack); + + // if rhs might not be bigger than lhs + if (rhs.data->digits_used == 1) + { + *(temp->number) = lhs/ *(rhs.data->number); + } + + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator/ ( + const bigint_kernel_1& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record + (lhs.data->digits_used+lhs.slack); + + uint16 remainder; + lhs.short_div(lhs.data,rhs,temp,remainder); + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator/= ( + uint16 rhs + ) + { + uint16 remainder; + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_div(data,rhs,temp,remainder); + data = temp; + } + else + { + short_div(data,rhs,data,remainder); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator% ( + uint16 lhs, + const bigint_kernel_1& rhs + ) + { + typedef bigint_kernel_1 bigint; + // temp is zero by default + bigint::data_record* temp = new bigint::data_record(rhs.slack); + + if (rhs.data->digits_used == 1) + { + // if rhs is just an uint16 inside then perform the modulus + *(temp->number) = lhs % *(rhs.data->number); + } + else + { + // if rhs is bigger than lhs then the answer is lhs + *(temp->number) = lhs; + } + + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 operator% ( + const bigint_kernel_1& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_1 bigint; + bigint::data_record* temp = new bigint::data_record(lhs.data->digits_used+lhs.slack); + + uint16 remainder; + + lhs.short_div(lhs.data,rhs,temp,remainder); + temp->digits_used = 1; + *(temp->number) = remainder; + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator%= ( + uint16 rhs + ) + { + uint16 remainder; + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_div(data,rhs,temp,remainder); + data = temp; + } + else + { + short_div(data,rhs,data,remainder); + } + + data->digits_used = 1; + *(data->number) = remainder; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + bool operator < ( + uint16 lhs, + const bigint_kernel_1& rhs + ) + { + return (rhs.data->digits_used > 1 || lhs < *(rhs.data->number) ); + } + +// ---------------------------------------------------------------------------------------- + + bool operator < ( + const bigint_kernel_1& lhs, + uint16 rhs + ) + { + return (lhs.data->digits_used == 1 && *(lhs.data->number) < rhs); + } + +// ---------------------------------------------------------------------------------------- + + bool operator == ( + const bigint_kernel_1& lhs, + uint16 rhs + ) + { + return (lhs.data->digits_used == 1 && *(lhs.data->number) == rhs); + } + +// ---------------------------------------------------------------------------------------- + + bool operator == ( + uint16 lhs, + const bigint_kernel_1& rhs + ) + { + return (rhs.data->digits_used == 1 && *(rhs.data->number) == lhs); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator= ( + uint16 rhs + ) + { + // check if there are other references to our data + if (data->references != 1) + { + data->references -= 1; + try { + data = new data_record(slack); + } catch (...) { data->references += 1; throw; } + } + else + { + data->digits_used = 1; + } + + *(data->number) = rhs; + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator++ ( + ) + { + // if there are other references to this data then make a copy of it + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + increment(data,temp); + data = temp; + } + // or if we need to enlarge data then do so + else if (data->digits_used == data->size) + { + data_record* temp = new data_record(data->digits_used+slack); + increment(data,temp); + delete data; + data = temp; + } + else + { + increment(data,data); + } + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 bigint_kernel_1:: + operator++ ( + int + ) + { + data_record* temp; // this is the copy of temp we will return in the end + + data_record* temp2 = new data_record(data->digits_used+slack); + increment(data,temp2); + + temp = data; + data = temp2; + + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_1& bigint_kernel_1:: + operator-- ( + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + decrement(data,temp); + data = temp; + } + else + { + decrement(data,data); + } + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_1 bigint_kernel_1:: + operator-- ( + int + ) + { + data_record* temp; // this is the copy of temp we will return in the end + + data_record* temp2 = new data_record(data->digits_used+slack); + decrement(data,temp2); + + temp = data; + data = temp2; + + return bigint_kernel_1(temp,0); + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // private member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + short_add ( + const data_record* data, + uint16 value, + data_record* result + ) const + { + // put value into the carry part of temp + uint32 temp = value; + temp <<= 16; + + + const uint16* number = data->number; + const uint16* end = number + data->digits_used; // one past the end of number + uint16* r = result->number; + + while (number != end) + { + // add *number and the current carry + temp = *number + (temp>>16); + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++number; + ++r; + } + + // if there is a final carry + if ((temp>>16) != 0) + { + result->digits_used = data->digits_used + 1; + // store the carry in the most significant digit of the result + *r = static_cast<uint16>(temp>>16); + } + else + { + result->digits_used = data->digits_used; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + short_sub ( + const data_record* data, + uint16 value, + data_record* result + ) const + { + + + const uint16* number = data->number; + const uint16* end = number + data->digits_used - 1; + uint16* r = result->number; + + uint32 temp = *number - value; + + // put the low word of temp into *data + *r = static_cast<uint16>(temp & 0xFFFF); + + + while (number != end) + { + ++number; + ++r; + + // subtract the carry from *number + temp = *number - (temp>>31); + + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + } + + // if we lost a digit in the subtraction + if (*r == 0) + { + if (data->digits_used == 1) + result->digits_used = 1; + else + result->digits_used = data->digits_used - 1; + } + else + { + result->digits_used = data->digits_used; + } + + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + short_mul ( + const data_record* data, + uint16 value, + data_record* result + ) const + { + + uint32 temp = 0; + + + const uint16* number = data->number; + uint16* r = result->number; + const uint16* end = r + data->digits_used; + + + + while ( r != end) + { + + // multiply *data and value and add in the carry + temp = *number*(uint32)value + (temp>>16); + + // put the low word of temp into *data + *r = static_cast<uint16>(temp & 0xFFFF); + + ++number; + ++r; + } + + // if there is a final carry + if ((temp>>16) != 0) + { + result->digits_used = data->digits_used + 1; + // put the final carry into the most significant digit of the result + *r = static_cast<uint16>(temp>>16); + } + else + { + result->digits_used = data->digits_used; + } + + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + short_div ( + const data_record* data, + uint16 value, + data_record* result, + uint16& rem + ) const + { + + uint16 remainder = 0; + uint32 temp; + + + + const uint16* number = data->number + data->digits_used - 1; + const uint16* end = number - data->digits_used; + uint16* r = result->number + data->digits_used - 1; + + + // if we are losing a digit in this division + if (*number < value) + { + if (data->digits_used == 1) + result->digits_used = 1; + else + result->digits_used = data->digits_used - 1; + } + else + { + result->digits_used = data->digits_used; + } + + + // perform the actual division + while (number != end) + { + + temp = *number + (((uint32)remainder)<<16); + + *r = static_cast<uint16>(temp/value); + remainder = static_cast<uint16>(temp%value); + + --number; + --r; + } + + rem = remainder; + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + long_add ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const + { + // put value into the carry part of temp + uint32 temp=0; + + uint16* min_num; // the number with the least digits used + uint16* max_num; // the number with the most digits used + uint16* min_end; // one past the end of min_num + uint16* max_end; // one past the end of max_num + uint16* r = result->number; + + uint32 max_digits_used; + if (lhs->digits_used < rhs->digits_used) + { + max_digits_used = rhs->digits_used; + min_num = lhs->number; + max_num = rhs->number; + min_end = min_num + lhs->digits_used; + max_end = max_num + rhs->digits_used; + } + else + { + max_digits_used = lhs->digits_used; + min_num = rhs->number; + max_num = lhs->number; + min_end = min_num + rhs->digits_used; + max_end = max_num + lhs->digits_used; + } + + + + + while (min_num != min_end) + { + // add *min_num, *max_num and the current carry + temp = *min_num + *max_num + (temp>>16); + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++min_num; + ++max_num; + ++r; + } + + + while (max_num != max_end) + { + // add *max_num and the current carry + temp = *max_num + (temp>>16); + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++max_num; + ++r; + } + + // check if there was a final carry + if ((temp>>16) != 0) + { + result->digits_used = max_digits_used + 1; + // put the carry into the most significant digit in the result + *r = static_cast<uint16>(temp>>16); + } + else + { + result->digits_used = max_digits_used; + } + + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + long_sub ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const + { + + + const uint16* number1 = lhs->number; + const uint16* number2 = rhs->number; + const uint16* end = number2 + rhs->digits_used; + uint16* r = result->number; + + + + uint32 temp =0; + + + while (number2 != end) + { + + // subtract *number2 from *number1 and then subtract any carry + temp = *number1 - *number2 - (temp>>31); + + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++number1; + ++number2; + ++r; + } + + end = lhs->number + lhs->digits_used; + while (number1 != end) + { + + // subtract the carry from *number1 + temp = *number1 - (temp>>31); + + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++number1; + ++r; + } + + result->digits_used = lhs->digits_used; + // adjust the number of digits used appropriately + --r; + while (*r == 0 && result->digits_used > 1) + { + --r; + --result->digits_used; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + long_div ( + const data_record* lhs, + const data_record* rhs, + data_record* result, + data_record* remainder + ) const + { + // zero result + result->digits_used = 1; + *(result->number) = 0; + + uint16* a; + uint16* b; + uint16* end; + + // copy lhs into remainder + remainder->digits_used = lhs->digits_used; + a = remainder->number; + end = a + remainder->digits_used; + b = lhs->number; + while (a != end) + { + *a = *b; + ++a; + ++b; + } + + + // if rhs is bigger than lhs then result == 0 and remainder == lhs + // so then we can quit right now + if (is_less_than(lhs,rhs)) + { + return; + } + + + // make a temporary number + data_record temp(lhs->digits_used + slack); + + + // shift rhs left until it is one shift away from being larger than lhs and + // put the number of left shifts necessary into shifts + uint32 shifts; + shifts = (lhs->digits_used - rhs->digits_used) * 16; + + shift_left(rhs,&temp,shifts); + + + // while (lhs > temp) + while (is_less_than(&temp,lhs)) + { + shift_left(&temp,&temp,1); + ++shifts; + } + // make sure lhs isn't smaller than temp + while (is_less_than(lhs,&temp)) + { + shift_right(&temp,&temp); + --shifts; + } + + + + // we want to execute the loop shifts +1 times + ++shifts; + while (shifts != 0) + { + shift_left(result,result,1); + // if (temp <= remainder) + if (!is_less_than(remainder,&temp)) + { + long_sub(remainder,&temp,remainder); + + // increment result + uint16* r = result->number; + uint16* end = r + result->digits_used; + while (true) + { + ++(*r); + // if there was no carry then we are done + if (*r != 0) + break; + + ++r; + + // if we hit the end of r and there is still a carry then + // the next digit of r is 1 and there is one more digit used + if (r == end) + { + *r = 1; + ++(result->digits_used); + break; + } + } + } + shift_right(&temp,&temp); + --shifts; + } + + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + long_mul ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const + { + // make result be zero + result->digits_used = 1; + *(result->number) = 0; + + + const data_record* aa; + const data_record* bb; + + if (lhs->digits_used < rhs->digits_used) + { + // make copies of lhs and rhs and give them an appropriate amount of + // extra memory so there won't be any overflows + aa = lhs; + bb = rhs; + } + else + { + // make copies of lhs and rhs and give them an appropriate amount of + // extra memory so there won't be any overflows + aa = rhs; + bb = lhs; + } + // this is where we actually copy lhs and rhs + data_record b(*bb,aa->digits_used+slack); // the larger(approximately) of lhs and rhs + + + uint32 shift_value = 0; + uint16* anum = aa->number; + uint16* end = anum + aa->digits_used; + while (anum != end ) + { + uint16 bit = 0x0001; + + for (int i = 0; i < 16; ++i) + { + // if the specified bit of a is 1 + if ((*anum & bit) != 0) + { + shift_left(&b,&b,shift_value); + shift_value = 0; + long_add(&b,result,result); + } + ++shift_value; + bit <<= 1; + } + + ++anum; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + shift_left ( + const data_record* data, + data_record* result, + uint32 shift_amount + ) const + { + uint32 offset = shift_amount/16; + shift_amount &= 0xf; // same as shift_amount %= 16; + + uint16* r = result->number + data->digits_used + offset; // result + uint16* end = data->number; + uint16* s = end + data->digits_used; // source + const uint32 temp = 16 - shift_amount; + + *r = (*(--s) >> temp); + // set the number of digits used in the result + // if the upper bits from *s were zero then don't count this first word + if (*r == 0) + { + result->digits_used = data->digits_used + offset; + } + else + { + result->digits_used = data->digits_used + offset + 1; + } + --r; + + while (s != end) + { + *r = ((*s << shift_amount) | ( *(s-1) >> temp)); + --r; + --s; + } + *r = *s << shift_amount; + + // now zero the rest of the result + end = result->number; + while (r != end) + *(--r) = 0; + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + shift_right ( + const data_record* data, + data_record* result + ) const + { + + uint16* r = result->number; // result + uint16* s = data->number; // source + uint16* end = s + data->digits_used - 1; + + while (s != end) + { + *r = (*s >> 1) | (*(s+1) << 15); + ++r; + ++s; + } + *r = *s >> 1; + + + // calculate the new number for digits_used + if (*r == 0) + { + if (data->digits_used != 1) + result->digits_used = data->digits_used - 1; + else + result->digits_used = 1; + } + else + { + result->digits_used = data->digits_used; + } + + + } + +// ---------------------------------------------------------------------------------------- + + bool bigint_kernel_1:: + is_less_than ( + const data_record* lhs, + const data_record* rhs + ) const + { + uint32 lhs_digits_used = lhs->digits_used; + uint32 rhs_digits_used = rhs->digits_used; + + // if lhs is definitely less than rhs + if (lhs_digits_used < rhs_digits_used ) + return true; + // if lhs is definitely greater than rhs + else if (lhs_digits_used > rhs_digits_used) + return false; + else + { + uint16* end = lhs->number; + uint16* l = end + lhs_digits_used; + uint16* r = rhs->number + rhs_digits_used; + + while (l != end) + { + --l; + --r; + if (*l < *r) + return true; + else if (*l > *r) + return false; + } + + // at this point we know that they are equal + return false; + } + + } + +// ---------------------------------------------------------------------------------------- + + bool bigint_kernel_1:: + is_equal_to ( + const data_record* lhs, + const data_record* rhs + ) const + { + // if lhs and rhs are definitely not equal + if (lhs->digits_used != rhs->digits_used ) + { + return false; + } + else + { + uint16* l = lhs->number; + uint16* r = rhs->number; + uint16* end = l + lhs->digits_used; + + while (l != end) + { + if (*l != *r) + return false; + ++l; + ++r; + } + + // at this point we know that they are equal + return true; + } + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + increment ( + const data_record* source, + data_record* dest + ) const + { + uint16* s = source->number; + uint16* d = dest->number; + uint16* end = s + source->digits_used; + while (true) + { + *d = *s + 1; + + // if there was no carry then break out of the loop + if (*d != 0) + { + dest->digits_used = source->digits_used; + + // copy the rest of the digits over to d + ++d; ++s; + while (s != end) + { + *d = *s; + ++d; + ++s; + } + + break; + } + + + ++s; + + // if we have hit the end of s and there was a carry up to this point + // then just make the next digit 1 and add one to the digits used + if (s == end) + { + ++d; + dest->digits_used = source->digits_used + 1; + *d = 1; + break; + } + + ++d; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_1:: + decrement ( + const data_record* source, + data_record* dest + ) const + { + uint16* s = source->number; + uint16* d = dest->number; + uint16* end = s + source->digits_used; + while (true) + { + *d = *s - 1; + + // if there was no carry then break out of the loop + if (*d != 0xFFFF) + { + // if we lost a digit in the subtraction + if (*d == 0 && s+1 == end) + { + if (source->digits_used == 1) + dest->digits_used = 1; + else + dest->digits_used = source->digits_used - 1; + } + else + { + dest->digits_used = source->digits_used; + } + break; + } + else + { + ++d; + ++s; + } + + } + + // copy the rest of the digits over to d + ++d; + ++s; + while (s != end) + { + *d = *s; + ++d; + ++s; + } + } + +// ---------------------------------------------------------------------------------------- + +} +#endif // DLIB_BIGINT_KERNEL_1_CPp_ + diff --git a/ml/dlib/dlib/bigint/bigint_kernel_1.h b/ml/dlib/dlib/bigint/bigint_kernel_1.h new file mode 100644 index 000000000..3e7f3d851 --- /dev/null +++ b/ml/dlib/dlib/bigint/bigint_kernel_1.h @@ -0,0 +1,544 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_BIGINT_KERNEl_1_ +#define DLIB_BIGINT_KERNEl_1_ + +#include "bigint_kernel_abstract.h" +#include "../algs.h" +#include "../serialize.h" +#include "../uintn.h" +#include <iosfwd> + +namespace dlib +{ + + + class bigint_kernel_1 + { + /*! + INITIAL VALUE + slack == 25 + data->number[0] == 0 + data->size == slack + data->references == 1 + data->digits_used == 1 + + + CONVENTION + slack == the number of extra digits placed into the number when it is + created. the slack value should never be less than 1 + + data->number == pointer to an array of data->size uint16s. + data represents a string of base 65535 numbers with data[0] being + the least significant bit and data[data->digits_used-1] being the most + significant + + + NOTE: In the comments I will consider a word to be a 16 bit value + + + data->digits_used == the number of significant digits in the number. + data->digits_used tells us the number of used elements in the + data->number array so everything beyond data->number[data->digits_used-1] + is undefined + + data->references == the number of bigint_kernel_1 objects which refer + to this data_record + + + + !*/ + + + struct data_record + { + + + explicit data_record( + uint32 size_ + ) : + size(size_), + number(new uint16[size_]), + references(1), + digits_used(1) + {*number = 0;} + /*! + ensures + - initializes *this to represent zero + !*/ + + data_record( + const data_record& item, + uint32 additional_size + ) : + size(item.digits_used + additional_size), + number(new uint16[size]), + references(1), + digits_used(item.digits_used) + { + uint16* source = item.number; + uint16* dest = number; + uint16* end = source + digits_used; + while (source != end) + { + *dest = *source; + ++dest; + ++source; + } + } + /*! + ensures + - *this is a copy of item except with + size == item.digits_used + additional_size + !*/ + + ~data_record( + ) + { + delete [] number; + } + + + const uint32 size; + uint16* number; + uint32 references; + uint32 digits_used; + + private: + // no copy constructor + data_record ( data_record&); + }; + + + + // note that the second parameter is just there + // to resolve the ambiguity between this constructor and + // bigint_kernel_1(uint32) + explicit bigint_kernel_1 ( + data_record* data_, int + ): slack(25),data(data_) {} + /*! + ensures + - *this is initialized with data_ as its data member + !*/ + + + public: + + bigint_kernel_1 ( + ); + + bigint_kernel_1 ( + uint32 value + ); + + bigint_kernel_1 ( + const bigint_kernel_1& item + ); + + virtual ~bigint_kernel_1 ( + ); + + const bigint_kernel_1 operator+ ( + const bigint_kernel_1& rhs + ) const; + + bigint_kernel_1& operator+= ( + const bigint_kernel_1& rhs + ); + + const bigint_kernel_1 operator- ( + const bigint_kernel_1& rhs + ) const; + + bigint_kernel_1& operator-= ( + const bigint_kernel_1& rhs + ); + + const bigint_kernel_1 operator* ( + const bigint_kernel_1& rhs + ) const; + + bigint_kernel_1& operator*= ( + const bigint_kernel_1& rhs + ); + + const bigint_kernel_1 operator/ ( + const bigint_kernel_1& rhs + ) const; + + bigint_kernel_1& operator/= ( + const bigint_kernel_1& rhs + ); + + const bigint_kernel_1 operator% ( + const bigint_kernel_1& rhs + ) const; + + bigint_kernel_1& operator%= ( + const bigint_kernel_1& rhs + ); + + bool operator < ( + const bigint_kernel_1& rhs + ) const; + + bool operator == ( + const bigint_kernel_1& rhs + ) const; + + bigint_kernel_1& operator= ( + const bigint_kernel_1& rhs + ); + + friend std::ostream& operator<< ( + std::ostream& out, + const bigint_kernel_1& rhs + ); + + friend std::istream& operator>> ( + std::istream& in, + bigint_kernel_1& rhs + ); + + bigint_kernel_1& operator++ ( + ); + + const bigint_kernel_1 operator++ ( + int + ); + + bigint_kernel_1& operator-- ( + ); + + const bigint_kernel_1 operator-- ( + int + ); + + friend const bigint_kernel_1 operator+ ( + uint16 lhs, + const bigint_kernel_1& rhs + ); + + friend const bigint_kernel_1 operator+ ( + const bigint_kernel_1& lhs, + uint16 rhs + ); + + bigint_kernel_1& operator+= ( + uint16 rhs + ); + + friend const bigint_kernel_1 operator- ( + uint16 lhs, + const bigint_kernel_1& rhs + ); + + friend const bigint_kernel_1 operator- ( + const bigint_kernel_1& lhs, + uint16 rhs + ); + + bigint_kernel_1& operator-= ( + uint16 rhs + ); + + friend const bigint_kernel_1 operator* ( + uint16 lhs, + const bigint_kernel_1& rhs + ); + + friend const bigint_kernel_1 operator* ( + const bigint_kernel_1& lhs, + uint16 rhs + ); + + bigint_kernel_1& operator*= ( + uint16 rhs + ); + + friend const bigint_kernel_1 operator/ ( + uint16 lhs, + const bigint_kernel_1& rhs + ); + + friend const bigint_kernel_1 operator/ ( + const bigint_kernel_1& lhs, + uint16 rhs + ); + + bigint_kernel_1& operator/= ( + uint16 rhs + ); + + friend const bigint_kernel_1 operator% ( + uint16 lhs, + const bigint_kernel_1& rhs + ); + + friend const bigint_kernel_1 operator% ( + const bigint_kernel_1& lhs, + uint16 rhs + ); + + bigint_kernel_1& operator%= ( + uint16 rhs + ); + + friend bool operator < ( + uint16 lhs, + const bigint_kernel_1& rhs + ); + + friend bool operator < ( + const bigint_kernel_1& lhs, + uint16 rhs + ); + + friend bool operator == ( + const bigint_kernel_1& lhs, + uint16 rhs + ); + + friend bool operator == ( + uint16 lhs, + const bigint_kernel_1& rhs + ); + + bigint_kernel_1& operator= ( + uint16 rhs + ); + + + void swap ( + bigint_kernel_1& item + ) { data_record* temp = data; data = item.data; item.data = temp; } + + + private: + + void long_add ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const; + /*! + requires + - result->size >= max(lhs->digits_used,rhs->digits_used) + 1 + ensures + - result == lhs + rhs + !*/ + + void long_sub ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const; + /*! + requires + - lhs >= rhs + - result->size >= lhs->digits_used + ensures + - result == lhs - rhs + !*/ + + void long_div ( + const data_record* lhs, + const data_record* rhs, + data_record* result, + data_record* remainder + ) const; + /*! + requires + - rhs != 0 + - result->size >= lhs->digits_used + - remainder->size >= lhs->digits_used + - each parameter is unique (i.e. lhs != result, lhs != remainder, etc.) + ensures + - result == lhs / rhs + - remainder == lhs % rhs + !*/ + + void long_mul ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const; + /*! + requires + - result->size >= lhs->digits_used + rhs->digits_used + - result != lhs + - result != rhs + ensures + - result == lhs * rhs + !*/ + + void short_add ( + const data_record* data, + uint16 value, + data_record* result + ) const; + /*! + requires + - result->size >= data->size + 1 + ensures + - result == data + value + !*/ + + void short_sub ( + const data_record* data, + uint16 value, + data_record* result + ) const; + /*! + requires + - data >= value + - result->size >= data->digits_used + ensures + - result == data - value + !*/ + + void short_mul ( + const data_record* data, + uint16 value, + data_record* result + ) const; + /*! + requires + - result->size >= data->digits_used + 1 + ensures + - result == data * value + !*/ + + void short_div ( + const data_record* data, + uint16 value, + data_record* result, + uint16& remainder + ) const; + /*! + requires + - value != 0 + - result->size >= data->digits_used + ensures + - result = data*value + - remainder = data%value + !*/ + + void shift_left ( + const data_record* data, + data_record* result, + uint32 shift_amount + ) const; + /*! + requires + - result->size >= data->digits_used + shift_amount/8 + 1 + ensures + - result == data << shift_amount + !*/ + + void shift_right ( + const data_record* data, + data_record* result + ) const; + /*! + requires + - result->size >= data->digits_used + ensures + - result == data >> 1 + !*/ + + bool is_less_than ( + const data_record* lhs, + const data_record* rhs + ) const; + /*! + ensures + - returns true if lhs < rhs + - returns false otherwise + !*/ + + bool is_equal_to ( + const data_record* lhs, + const data_record* rhs + ) const; + /*! + ensures + - returns true if lhs == rhs + - returns false otherwise + !*/ + + void increment ( + const data_record* source, + data_record* dest + ) const; + /*! + requires + - dest->size >= source->digits_used + 1 + ensures + - dest = source + 1 + !*/ + + void decrement ( + const data_record* source, + data_record* dest + ) const; + /*! + requires + source != 0 + ensuers + dest = source - 1 + !*/ + + // member data + const uint32 slack; + data_record* data; + + + + }; + + inline void swap ( + bigint_kernel_1& a, + bigint_kernel_1& b + ) { a.swap(b); } + + inline void serialize ( + const bigint_kernel_1& item, + std::ostream& out + ) + { + std::ios::fmtflags oldflags = out.flags(); + out.flags(); + out << item << ' '; + out.flags(oldflags); + if (!out) throw serialization_error("Error serializing object of type bigint_kernel_c"); + } + + inline void deserialize ( + bigint_kernel_1& item, + std::istream& in + ) + { + std::ios::fmtflags oldflags = in.flags(); + in.flags(); + in >> item; in.flags(oldflags); + if (in.get() != ' ') + { + item = 0; + throw serialization_error("Error deserializing object of type bigint_kernel_c"); + } + } + + inline bool operator> (const bigint_kernel_1& a, const bigint_kernel_1& b) { return b < a; } + inline bool operator!= (const bigint_kernel_1& a, const bigint_kernel_1& b) { return !(a == b); } + inline bool operator<= (const bigint_kernel_1& a, const bigint_kernel_1& b) { return !(b < a); } + inline bool operator>= (const bigint_kernel_1& a, const bigint_kernel_1& b) { return !(a < b); } +} + +#ifdef NO_MAKEFILE +#include "bigint_kernel_1.cpp" +#endif + +#endif // DLIB_BIGINT_KERNEl_1_ + diff --git a/ml/dlib/dlib/bigint/bigint_kernel_2.cpp b/ml/dlib/dlib/bigint/bigint_kernel_2.cpp new file mode 100644 index 000000000..005e080af --- /dev/null +++ b/ml/dlib/dlib/bigint/bigint_kernel_2.cpp @@ -0,0 +1,1945 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_BIGINT_KERNEL_2_CPp_ +#define DLIB_BIGINT_KERNEL_2_CPp_ +#include "bigint_kernel_2.h" + +#include <iostream> +#include <cmath> + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // member/friend function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2:: + bigint_kernel_2 ( + ) : + slack(25), + data(new data_record(slack)) + {} + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2:: + bigint_kernel_2 ( + uint32 value + ) : + slack(25), + data(new data_record(slack)) + { + *(data->number) = static_cast<uint16>(value&0xFFFF); + *(data->number+1) = static_cast<uint16>((value>>16)&0xFFFF); + if (*(data->number+1) != 0) + data->digits_used = 2; + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2:: + bigint_kernel_2 ( + const bigint_kernel_2& item + ) : + slack(25), + data(item.data) + { + data->references += 1; + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2:: + ~bigint_kernel_2 ( + ) + { + if (data->references == 1) + { + delete data; + } + else + { + data->references -= 1; + } + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 bigint_kernel_2:: + operator+ ( + const bigint_kernel_2& rhs + ) const + { + data_record* temp = new data_record ( + std::max(rhs.data->digits_used,data->digits_used) + slack + ); + long_add(data,rhs.data,temp); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator+= ( + const bigint_kernel_2& rhs + ) + { + // if there are other references to our data + if (data->references != 1) + { + data_record* temp = new data_record(std::max(data->digits_used,rhs.data->digits_used)+slack); + data->references -= 1; + long_add(data,rhs.data,temp); + data = temp; + } + // if data is not big enough for the result + else if (data->size <= std::max(data->digits_used,rhs.data->digits_used)) + { + data_record* temp = new data_record(std::max(data->digits_used,rhs.data->digits_used)+slack); + long_add(data,rhs.data,temp); + delete data; + data = temp; + } + // there is enough size and no references + else + { + long_add(data,rhs.data,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 bigint_kernel_2:: + operator- ( + const bigint_kernel_2& rhs + ) const + { + data_record* temp = new data_record ( + data->digits_used + slack + ); + long_sub(data,rhs.data,temp); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator-= ( + const bigint_kernel_2& rhs + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + long_sub(data,rhs.data,temp); + data = temp; + } + else + { + long_sub(data,rhs.data,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 bigint_kernel_2:: + operator* ( + const bigint_kernel_2& rhs + ) const + { + data_record* temp = new data_record ( + data->digits_used + rhs.data->digits_used + slack + ); + long_mul(data,rhs.data,temp); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator*= ( + const bigint_kernel_2& rhs + ) + { + // create a data_record to store the result of the multiplication in + data_record* temp = new data_record(rhs.data->digits_used+data->digits_used+slack); + long_mul(data,rhs.data,temp); + + // if there are other references to data + if (data->references != 1) + { + data->references -= 1; + } + else + { + delete data; + } + data = temp; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 bigint_kernel_2:: + operator/ ( + const bigint_kernel_2& rhs + ) const + { + data_record* temp = new data_record(data->digits_used+slack); + data_record* remainder; + try { + remainder = new data_record(data->digits_used+slack); + } catch (...) { delete temp; throw; } + + long_div(data,rhs.data,temp,remainder); + delete remainder; + + + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator/= ( + const bigint_kernel_2& rhs + ) + { + + data_record* temp = new data_record(data->digits_used+slack); + data_record* remainder; + try { + remainder = new data_record(data->digits_used+slack); + } catch (...) { delete temp; throw; } + + long_div(data,rhs.data,temp,remainder); + + // check if there are other references to data + if (data->references != 1) + { + data->references -= 1; + } + // if there are no references to data then it must be deleted + else + { + delete data; + } + data = temp; + delete remainder; + + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 bigint_kernel_2:: + operator% ( + const bigint_kernel_2& rhs + ) const + { + data_record* temp = new data_record(data->digits_used+slack); + data_record* remainder; + try { + remainder = new data_record(data->digits_used+slack); + } catch (...) { delete temp; throw; } + + long_div(data,rhs.data,temp,remainder); + delete temp; + return bigint_kernel_2(remainder,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator%= ( + const bigint_kernel_2& rhs + ) + { + data_record* temp = new data_record(data->digits_used+slack); + data_record* remainder; + try { + remainder = new data_record(data->digits_used+slack); + } catch (...) { delete temp; throw; } + + long_div(data,rhs.data,temp,remainder); + + // check if there are other references to data + if (data->references != 1) + { + data->references -= 1; + } + // if there are no references to data then it must be deleted + else + { + delete data; + } + data = remainder; + delete temp; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + bool bigint_kernel_2:: + operator < ( + const bigint_kernel_2& rhs + ) const + { + return is_less_than(data,rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + bool bigint_kernel_2:: + operator == ( + const bigint_kernel_2& rhs + ) const + { + return is_equal_to(data,rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator= ( + const bigint_kernel_2& rhs + ) + { + if (this == &rhs) + return *this; + + // if we have the only reference to our data then delete it + if (data->references == 1) + { + delete data; + data = rhs.data; + data->references += 1; + } + else + { + data->references -= 1; + data = rhs.data; + data->references += 1; + } + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + std::ostream& operator<< ( + std::ostream& out_, + const bigint_kernel_2& rhs + ) + { + std::ostream out(out_.rdbuf()); + + typedef bigint_kernel_2 bigint; + + bigint::data_record* temp = new bigint::data_record(*rhs.data,0); + + + + // get a char array big enough to hold the number in ascii format + char* str; + try { + str = new char[(rhs.data->digits_used)*5+10]; + } catch (...) { delete temp; throw; } + + char* str_start = str; + str += (rhs.data->digits_used)*5+9; + *str = 0; --str; + + + uint16 remainder; + rhs.short_div(temp,10000,temp,remainder); + + // pull the digits out of remainder + char a = remainder % 10 + '0'; + remainder /= 10; + char b = remainder % 10 + '0'; + remainder /= 10; + char c = remainder % 10 + '0'; + remainder /= 10; + char d = remainder % 10 + '0'; + remainder /= 10; + + + *str = a; --str; + *str = b; --str; + *str = c; --str; + *str = d; --str; + + + // keep looping until temp represents zero + while (temp->digits_used != 1 || *(temp->number) != 0) + { + rhs.short_div(temp,10000,temp,remainder); + + // pull the digits out of remainder + char a = remainder % 10 + '0'; + remainder /= 10; + char b = remainder % 10 + '0'; + remainder /= 10; + char c = remainder % 10 + '0'; + remainder /= 10; + char d = remainder % 10 + '0'; + remainder /= 10; + + *str = a; --str; + *str = b; --str; + *str = c; --str; + *str = d; --str; + } + + // throw away and extra leading zeros + ++str; + if (*str == '0') + ++str; + if (*str == '0') + ++str; + if (*str == '0') + ++str; + + + + + out << str; + delete [] str_start; + delete temp; + return out_; + + } + +// ---------------------------------------------------------------------------------------- + + std::istream& operator>> ( + std::istream& in_, + bigint_kernel_2& rhs + ) + { + std::istream in(in_.rdbuf()); + + // ignore any leading whitespaces + while (in.peek() == ' ' || in.peek() == '\t' || in.peek() == '\n') + { + in.get(); + } + + // if the first digit is not an integer then this is an error + if ( !(in.peek() >= '0' && in.peek() <= '9')) + { + in_.clear(std::ios::failbit); + return in_; + } + + int num_read; + bigint_kernel_2 temp; + do + { + + // try to get 4 chars from in + num_read = 1; + char a = 0; + char b = 0; + char c = 0; + char d = 0; + + if (in.peek() >= '0' && in.peek() <= '9') + { + num_read *= 10; + a = in.get(); + } + if (in.peek() >= '0' && in.peek() <= '9') + { + num_read *= 10; + b = in.get(); + } + if (in.peek() >= '0' && in.peek() <= '9') + { + num_read *= 10; + c = in.get(); + } + if (in.peek() >= '0' && in.peek() <= '9') + { + num_read *= 10; + d = in.get(); + } + + // merge the for digits into an uint16 + uint16 num = 0; + if (a != 0) + { + num = a - '0'; + } + if (b != 0) + { + num *= 10; + num += b - '0'; + } + if (c != 0) + { + num *= 10; + num += c - '0'; + } + if (d != 0) + { + num *= 10; + num += d - '0'; + } + + + if (num_read != 1) + { + // shift the digits in temp left by the number of new digits we just read + temp *= num_read; + // add in new digits + temp += num; + } + + } while (num_read == 10000); + + + rhs = temp; + return in_; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator+ ( + uint16 lhs, + const bigint_kernel_2& rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record + (rhs.data->digits_used+rhs.slack); + + rhs.short_add(rhs.data,lhs,temp); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator+ ( + const bigint_kernel_2& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record + (lhs.data->digits_used+lhs.slack); + + lhs.short_add(lhs.data,rhs,temp); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator+= ( + uint16 rhs + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_add(data,rhs,temp); + data = temp; + } + // or if we need to enlarge data then do so + else if (data->digits_used == data->size) + { + data_record* temp = new data_record(data->digits_used+slack); + short_add(data,rhs,temp); + delete data; + data = temp; + } + // or if there is plenty of space and no references + else + { + short_add(data,rhs,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator- ( + uint16 lhs, + const bigint_kernel_2& rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record(rhs.slack); + + *(temp->number) = lhs - *(rhs.data->number); + + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator- ( + const bigint_kernel_2& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record + (lhs.data->digits_used+lhs.slack); + + lhs.short_sub(lhs.data,rhs,temp); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator-= ( + uint16 rhs + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_sub(data,rhs,temp); + data = temp; + } + else + { + short_sub(data,rhs,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator* ( + uint16 lhs, + const bigint_kernel_2& rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record + (rhs.data->digits_used+rhs.slack); + + rhs.short_mul(rhs.data,lhs,temp); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator* ( + const bigint_kernel_2& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record + (lhs.data->digits_used+lhs.slack); + + lhs.short_mul(lhs.data,rhs,temp); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator*= ( + uint16 rhs + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_mul(data,rhs,temp); + data = temp; + } + // or if we need to enlarge data + else if (data->digits_used == data->size) + { + data_record* temp = new data_record(data->digits_used+slack); + short_mul(data,rhs,temp); + delete data; + data = temp; + } + else + { + short_mul(data,rhs,data); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator/ ( + uint16 lhs, + const bigint_kernel_2& rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record(rhs.slack); + + // if rhs might not be bigger than lhs + if (rhs.data->digits_used == 1) + { + *(temp->number) = lhs/ *(rhs.data->number); + } + + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator/ ( + const bigint_kernel_2& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record + (lhs.data->digits_used+lhs.slack); + + uint16 remainder; + lhs.short_div(lhs.data,rhs,temp,remainder); + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator/= ( + uint16 rhs + ) + { + uint16 remainder; + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_div(data,rhs,temp,remainder); + data = temp; + } + else + { + short_div(data,rhs,data,remainder); + } + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator% ( + uint16 lhs, + const bigint_kernel_2& rhs + ) + { + typedef bigint_kernel_2 bigint; + // temp is zero by default + bigint::data_record* temp = new bigint::data_record(rhs.slack); + + if (rhs.data->digits_used == 1) + { + // if rhs is just an uint16 inside then perform the modulus + *(temp->number) = lhs % *(rhs.data->number); + } + else + { + // if rhs is bigger than lhs then the answer is lhs + *(temp->number) = lhs; + } + + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 operator% ( + const bigint_kernel_2& lhs, + uint16 rhs + ) + { + typedef bigint_kernel_2 bigint; + bigint::data_record* temp = new bigint::data_record(lhs.data->digits_used+lhs.slack); + + uint16 remainder; + + lhs.short_div(lhs.data,rhs,temp,remainder); + temp->digits_used = 1; + *(temp->number) = remainder; + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator%= ( + uint16 rhs + ) + { + uint16 remainder; + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + short_div(data,rhs,temp,remainder); + data = temp; + } + else + { + short_div(data,rhs,data,remainder); + } + + data->digits_used = 1; + *(data->number) = remainder; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + bool operator < ( + uint16 lhs, + const bigint_kernel_2& rhs + ) + { + return (rhs.data->digits_used > 1 || lhs < *(rhs.data->number) ); + } + +// ---------------------------------------------------------------------------------------- + + bool operator < ( + const bigint_kernel_2& lhs, + uint16 rhs + ) + { + return (lhs.data->digits_used == 1 && *(lhs.data->number) < rhs); + } + +// ---------------------------------------------------------------------------------------- + + bool operator == ( + const bigint_kernel_2& lhs, + uint16 rhs + ) + { + return (lhs.data->digits_used == 1 && *(lhs.data->number) == rhs); + } + +// ---------------------------------------------------------------------------------------- + + bool operator == ( + uint16 lhs, + const bigint_kernel_2& rhs + ) + { + return (rhs.data->digits_used == 1 && *(rhs.data->number) == lhs); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator= ( + uint16 rhs + ) + { + // check if there are other references to our data + if (data->references != 1) + { + data->references -= 1; + try { + data = new data_record(slack); + } catch (...) { data->references += 1; throw; } + } + else + { + data->digits_used = 1; + } + + *(data->number) = rhs; + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator++ ( + ) + { + // if there are other references to this data then make a copy of it + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + increment(data,temp); + data = temp; + } + // or if we need to enlarge data then do so + else if (data->digits_used == data->size) + { + data_record* temp = new data_record(data->digits_used+slack); + increment(data,temp); + delete data; + data = temp; + } + else + { + increment(data,data); + } + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 bigint_kernel_2:: + operator++ ( + int + ) + { + data_record* temp; // this is the copy of temp we will return in the end + + data_record* temp2 = new data_record(data->digits_used+slack); + increment(data,temp2); + + temp = data; + data = temp2; + + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- + + bigint_kernel_2& bigint_kernel_2:: + operator-- ( + ) + { + // if there are other references to this data + if (data->references != 1) + { + data_record* temp = new data_record(data->digits_used+slack); + data->references -= 1; + decrement(data,temp); + data = temp; + } + else + { + decrement(data,data); + } + + return *this; + } + +// ---------------------------------------------------------------------------------------- + + const bigint_kernel_2 bigint_kernel_2:: + operator-- ( + int + ) + { + data_record* temp; // this is the copy of temp we will return in the end + + data_record* temp2 = new data_record(data->digits_used+slack); + decrement(data,temp2); + + temp = data; + data = temp2; + + return bigint_kernel_2(temp,0); + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // private member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + short_add ( + const data_record* data, + uint16 value, + data_record* result + ) const + { + // put value into the carry part of temp + uint32 temp = value; + temp <<= 16; + + + const uint16* number = data->number; + const uint16* end = number + data->digits_used; // one past the end of number + uint16* r = result->number; + + while (number != end) + { + // add *number and the current carry + temp = *number + (temp>>16); + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++number; + ++r; + } + + // if there is a final carry + if ((temp>>16) != 0) + { + result->digits_used = data->digits_used + 1; + // store the carry in the most significant digit of the result + *r = static_cast<uint16>(temp>>16); + } + else + { + result->digits_used = data->digits_used; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + short_sub ( + const data_record* data, + uint16 value, + data_record* result + ) const + { + + + const uint16* number = data->number; + const uint16* end = number + data->digits_used - 1; + uint16* r = result->number; + + uint32 temp = *number - value; + + // put the low word of temp into *data + *r = static_cast<uint16>(temp & 0xFFFF); + + + while (number != end) + { + ++number; + ++r; + + // subtract the carry from *number + temp = *number - (temp>>31); + + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + } + + // if we lost a digit in the subtraction + if (*r == 0) + { + if (data->digits_used == 1) + result->digits_used = 1; + else + result->digits_used = data->digits_used - 1; + } + else + { + result->digits_used = data->digits_used; + } + + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + short_mul ( + const data_record* data, + uint16 value, + data_record* result + ) const + { + + uint32 temp = 0; + + + const uint16* number = data->number; + uint16* r = result->number; + const uint16* end = r + data->digits_used; + + + + while ( r != end) + { + + // multiply *data and value and add in the carry + temp = *number*(uint32)value + (temp>>16); + + // put the low word of temp into *data + *r = static_cast<uint16>(temp & 0xFFFF); + + ++number; + ++r; + } + + // if there is a final carry + if ((temp>>16) != 0) + { + result->digits_used = data->digits_used + 1; + // put the final carry into the most significant digit of the result + *r = static_cast<uint16>(temp>>16); + } + else + { + result->digits_used = data->digits_used; + } + + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + short_div ( + const data_record* data, + uint16 value, + data_record* result, + uint16& rem + ) const + { + + uint16 remainder = 0; + uint32 temp; + + + + const uint16* number = data->number + data->digits_used - 1; + const uint16* end = number - data->digits_used; + uint16* r = result->number + data->digits_used - 1; + + + // if we are losing a digit in this division + if (*number < value) + { + if (data->digits_used == 1) + result->digits_used = 1; + else + result->digits_used = data->digits_used - 1; + } + else + { + result->digits_used = data->digits_used; + } + + + // perform the actual division + while (number != end) + { + + temp = *number + (((uint32)remainder)<<16); + + *r = static_cast<uint16>(temp/value); + remainder = static_cast<uint16>(temp%value); + + --number; + --r; + } + + rem = remainder; + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + long_add ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const + { + // put value into the carry part of temp + uint32 temp=0; + + uint16* min_num; // the number with the least digits used + uint16* max_num; // the number with the most digits used + uint16* min_end; // one past the end of min_num + uint16* max_end; // one past the end of max_num + uint16* r = result->number; + + uint32 max_digits_used; + if (lhs->digits_used < rhs->digits_used) + { + max_digits_used = rhs->digits_used; + min_num = lhs->number; + max_num = rhs->number; + min_end = min_num + lhs->digits_used; + max_end = max_num + rhs->digits_used; + } + else + { + max_digits_used = lhs->digits_used; + min_num = rhs->number; + max_num = lhs->number; + min_end = min_num + rhs->digits_used; + max_end = max_num + lhs->digits_used; + } + + + + + while (min_num != min_end) + { + // add *min_num, *max_num and the current carry + temp = *min_num + *max_num + (temp>>16); + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++min_num; + ++max_num; + ++r; + } + + + while (max_num != max_end) + { + // add *max_num and the current carry + temp = *max_num + (temp>>16); + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++max_num; + ++r; + } + + // check if there was a final carry + if ((temp>>16) != 0) + { + result->digits_used = max_digits_used + 1; + // put the carry into the most significant digit in the result + *r = static_cast<uint16>(temp>>16); + } + else + { + result->digits_used = max_digits_used; + } + + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + long_sub ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const + { + + + const uint16* number1 = lhs->number; + const uint16* number2 = rhs->number; + const uint16* end = number2 + rhs->digits_used; + uint16* r = result->number; + + + + uint32 temp =0; + + + while (number2 != end) + { + + // subtract *number2 from *number1 and then subtract any carry + temp = *number1 - *number2 - (temp>>31); + + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++number1; + ++number2; + ++r; + } + + end = lhs->number + lhs->digits_used; + while (number1 != end) + { + + // subtract the carry from *number1 + temp = *number1 - (temp>>31); + + // put the low word of temp into *r + *r = static_cast<uint16>(temp & 0xFFFF); + + ++number1; + ++r; + } + + result->digits_used = lhs->digits_used; + // adjust the number of digits used appropriately + --r; + while (*r == 0 && result->digits_used > 1) + { + --r; + --result->digits_used; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + long_div ( + const data_record* lhs, + const data_record* rhs, + data_record* result, + data_record* remainder + ) const + { + // zero result + result->digits_used = 1; + *(result->number) = 0; + + uint16* a; + uint16* b; + uint16* end; + + // copy lhs into remainder + remainder->digits_used = lhs->digits_used; + a = remainder->number; + end = a + remainder->digits_used; + b = lhs->number; + while (a != end) + { + *a = *b; + ++a; + ++b; + } + + + // if rhs is bigger than lhs then result == 0 and remainder == lhs + // so then we can quit right now + if (is_less_than(lhs,rhs)) + { + return; + } + + + // make a temporary number + data_record temp(lhs->digits_used + slack); + + + // shift rhs left until it is one shift away from being larger than lhs and + // put the number of left shifts necessary into shifts + uint32 shifts; + shifts = (lhs->digits_used - rhs->digits_used) * 16; + + shift_left(rhs,&temp,shifts); + + + // while (lhs > temp) + while (is_less_than(&temp,lhs)) + { + shift_left(&temp,&temp,1); + ++shifts; + } + // make sure lhs isn't smaller than temp + while (is_less_than(lhs,&temp)) + { + shift_right(&temp,&temp); + --shifts; + } + + + + // we want to execute the loop shifts +1 times + ++shifts; + while (shifts != 0) + { + shift_left(result,result,1); + // if (temp <= remainder) + if (!is_less_than(remainder,&temp)) + { + long_sub(remainder,&temp,remainder); + + // increment result + uint16* r = result->number; + uint16* end = r + result->digits_used; + while (true) + { + ++(*r); + // if there was no carry then we are done + if (*r != 0) + break; + + ++r; + + // if we hit the end of r and there is still a carry then + // the next digit of r is 1 and there is one more digit used + if (r == end) + { + *r = 1; + ++(result->digits_used); + break; + } + } + } + shift_right(&temp,&temp); + --shifts; + } + + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + long_mul ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const + { + // if one of the numbers is small then use this simple but O(n^2) algorithm + if (std::min(lhs->digits_used, rhs->digits_used) < 10) + { + // make result be zero + result->digits_used = 1; + *(result->number) = 0; + + + const data_record* aa; + const data_record* bb; + + if (lhs->digits_used < rhs->digits_used) + { + // make copies of lhs and rhs and give them an appropriate amount of + // extra memory so there won't be any overflows + aa = lhs; + bb = rhs; + } + else + { + // make copies of lhs and rhs and give them an appropriate amount of + // extra memory so there won't be any overflows + aa = rhs; + bb = lhs; + } + + // copy the larger(approximately) of lhs and rhs into b + data_record b(*bb,aa->digits_used+slack); + + + uint32 shift_value = 0; + uint16* anum = aa->number; + uint16* end = anum + aa->digits_used; + while (anum != end ) + { + uint16 bit = 0x0001; + + for (int i = 0; i < 16; ++i) + { + // if the specified bit of a is 1 + if ((*anum & bit) != 0) + { + shift_left(&b,&b,shift_value); + shift_value = 0; + long_add(&b,result,result); + } + ++shift_value; + bit <<= 1; + } + + ++anum; + } + } + else // else if both lhs and rhs are large then use the more complex + // O(n*logn) algorithm + { + uint32 size = 1; + // make size a power of 2 + while (size < (lhs->digits_used + rhs->digits_used)*2) + { + size *= 2; + } + + // allocate some temporary space so we can do the FFT + ct* a = new ct[size]; + ct* b; try {b = new ct[size]; } catch (...) { delete [] a; throw; } + + // load lhs into the a array. We are breaking the input number into + // 8bit chunks for the purpose of using this fft algorithm. The reason + // for this is so that we have smaller numbers coming out of the final + // ifft. This helps avoid overflow. + for (uint32 i = 0; i < lhs->digits_used; ++i) + { + a[i*2] = ct((t)(lhs->number[i]&0xFF),0); + a[i*2+1] = ct((t)(lhs->number[i]>>8),0); + } + for (uint32 i = lhs->digits_used*2; i < size; ++i) + { + a[i] = 0; + } + + // load rhs into the b array + for (uint32 i = 0; i < rhs->digits_used; ++i) + { + b[i*2] = ct((t)(rhs->number[i]&0xFF),0); + b[i*2+1] = ct((t)(rhs->number[i]>>8),0); + } + for (uint32 i = rhs->digits_used*2; i < size; ++i) + { + b[i] = 0; + } + + // perform the forward fft of a and b + fft(a,size); + fft(b,size); + + const double l = 1.0/size; + + // do the pointwise multiply of a and b and also apply the scale + // factor in this loop too. + for (unsigned long i = 0; i < size; ++i) + { + a[i] = l*a[i]*b[i]; + } + + // Now compute the inverse fft of the pointwise multiplication of a and b. + // This is basically the result. We just have to take care of any carries + // that should happen. + ifft(a,size); + + // loop over the result and propagate any carries that need to take place. + // We will also be moving the resulting numbers into result->number at + // the same time. + uint64 carry = 0; + result->digits_used = 0; + int zeros = 0; + const uint32 len = lhs->digits_used + rhs->digits_used; + for (unsigned long i = 0; i < len; ++i) + { + uint64 num1 = static_cast<uint64>(std::floor(a[i*2].real()+0.5)); + num1 += carry; + carry = 0; + if (num1 > 255) + { + carry = num1 >> 8; + num1 = (num1&0xFF); + } + + uint64 num2 = static_cast<uint64>(std::floor(a[i*2+1].real()+0.5)); + num2 += carry; + carry = 0; + if (num2 > 255) + { + carry = num2 >> 8; + num2 = (num2&0xFF); + } + + // put the new number into its final place + num1 = (num2<<8) | num1; + result->number[i] = static_cast<uint16>(num1); + + // keep track of the number of leading zeros + if (num1 == 0) + ++zeros; + else + zeros = 0; + ++(result->digits_used); + } + + // adjust digits_used so that it reflects the actual number + // of non-zero digits in our representation. + result->digits_used -= zeros; + + // if the result was zero then adjust the result accordingly + if (result->digits_used == 0) + { + // make result be zero + result->digits_used = 1; + *(result->number) = 0; + } + + // free all the temporary buffers + delete [] a; + delete [] b; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + shift_left ( + const data_record* data, + data_record* result, + uint32 shift_amount + ) const + { + uint32 offset = shift_amount/16; + shift_amount &= 0xf; // same as shift_amount %= 16; + + uint16* r = result->number + data->digits_used + offset; // result + uint16* end = data->number; + uint16* s = end + data->digits_used; // source + const uint32 temp = 16 - shift_amount; + + *r = (*(--s) >> temp); + // set the number of digits used in the result + // if the upper bits from *s were zero then don't count this first word + if (*r == 0) + { + result->digits_used = data->digits_used + offset; + } + else + { + result->digits_used = data->digits_used + offset + 1; + } + --r; + + while (s != end) + { + *r = ((*s << shift_amount) | ( *(s-1) >> temp)); + --r; + --s; + } + *r = *s << shift_amount; + + // now zero the rest of the result + end = result->number; + while (r != end) + *(--r) = 0; + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + shift_right ( + const data_record* data, + data_record* result + ) const + { + + uint16* r = result->number; // result + uint16* s = data->number; // source + uint16* end = s + data->digits_used - 1; + + while (s != end) + { + *r = (*s >> 1) | (*(s+1) << 15); + ++r; + ++s; + } + *r = *s >> 1; + + + // calculate the new number for digits_used + if (*r == 0) + { + if (data->digits_used != 1) + result->digits_used = data->digits_used - 1; + else + result->digits_used = 1; + } + else + { + result->digits_used = data->digits_used; + } + + + } + +// ---------------------------------------------------------------------------------------- + + bool bigint_kernel_2:: + is_less_than ( + const data_record* lhs, + const data_record* rhs + ) const + { + uint32 lhs_digits_used = lhs->digits_used; + uint32 rhs_digits_used = rhs->digits_used; + + // if lhs is definitely less than rhs + if (lhs_digits_used < rhs_digits_used ) + return true; + // if lhs is definitely greater than rhs + else if (lhs_digits_used > rhs_digits_used) + return false; + else + { + uint16* end = lhs->number; + uint16* l = end + lhs_digits_used; + uint16* r = rhs->number + rhs_digits_used; + + while (l != end) + { + --l; + --r; + if (*l < *r) + return true; + else if (*l > *r) + return false; + } + + // at this point we know that they are equal + return false; + } + + } + +// ---------------------------------------------------------------------------------------- + + bool bigint_kernel_2:: + is_equal_to ( + const data_record* lhs, + const data_record* rhs + ) const + { + // if lhs and rhs are definitely not equal + if (lhs->digits_used != rhs->digits_used ) + { + return false; + } + else + { + uint16* l = lhs->number; + uint16* r = rhs->number; + uint16* end = l + lhs->digits_used; + + while (l != end) + { + if (*l != *r) + return false; + ++l; + ++r; + } + + // at this point we know that they are equal + return true; + } + + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + increment ( + const data_record* source, + data_record* dest + ) const + { + uint16* s = source->number; + uint16* d = dest->number; + uint16* end = s + source->digits_used; + while (true) + { + *d = *s + 1; + + // if there was no carry then break out of the loop + if (*d != 0) + { + dest->digits_used = source->digits_used; + + // copy the rest of the digits over to d + ++d; ++s; + while (s != end) + { + *d = *s; + ++d; + ++s; + } + + break; + } + + + ++s; + + // if we have hit the end of s and there was a carry up to this point + // then just make the next digit 1 and add one to the digits used + if (s == end) + { + ++d; + dest->digits_used = source->digits_used + 1; + *d = 1; + break; + } + + ++d; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + decrement ( + const data_record* source, + data_record* dest + ) const + { + uint16* s = source->number; + uint16* d = dest->number; + uint16* end = s + source->digits_used; + while (true) + { + *d = *s - 1; + + // if there was no carry then break out of the loop + if (*d != 0xFFFF) + { + // if we lost a digit in the subtraction + if (*d == 0 && s+1 == end) + { + if (source->digits_used == 1) + dest->digits_used = 1; + else + dest->digits_used = source->digits_used - 1; + } + else + { + dest->digits_used = source->digits_used; + } + break; + } + else + { + ++d; + ++s; + } + + } + + // copy the rest of the digits over to d + ++d; + ++s; + while (s != end) + { + *d = *s; + ++d; + ++s; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + fft ( + ct* data, + unsigned long len + ) const + { + const t pi2 = -2.0*3.1415926535897932384626433832795028841971693993751; + + const unsigned long half = len/2; + + std::vector<ct> twiddle_factors; + twiddle_factors.resize(half); + + // compute the complex root of unity w + const t temp = pi2/len; + ct w = ct(std::cos(temp),std::sin(temp)); + + ct w_pow = 1; + + // compute the twiddle factors + for (std::vector<ct>::size_type j = 0; j < twiddle_factors.size(); ++j) + { + twiddle_factors[j] = w_pow; + w_pow *= w; + } + + ct a, b; + + // now compute the decimation in frequency. This first + // outer loop loops log2(len) number of times + unsigned long skip = 1; + for (unsigned long step = half; step != 0; step >>= 1) + { + // do blocks of butterflies in this loop + for (unsigned long j = 0; j < len; j += step*2) + { + // do step butterflies + for (unsigned long k = 0; k < step; ++k) + { + const unsigned long a_idx = j+k; + const unsigned long b_idx = j+k+step; + a = data[a_idx] + data[b_idx]; + b = (data[a_idx] - data[b_idx])*twiddle_factors[k*skip]; + data[a_idx] = a; + data[b_idx] = b; + } + } + skip *= 2; + } + } + +// ---------------------------------------------------------------------------------------- + + void bigint_kernel_2:: + ifft( + ct* data, + unsigned long len + ) const + { + const t pi2 = 2.0*3.1415926535897932384626433832795028841971693993751; + + const unsigned long half = len/2; + + std::vector<ct> twiddle_factors; + twiddle_factors.resize(half); + + // compute the complex root of unity w + const t temp = pi2/len; + ct w = ct(std::cos(temp),std::sin(temp)); + + ct w_pow = 1; + + // compute the twiddle factors + for (std::vector<ct>::size_type j = 0; j < twiddle_factors.size(); ++j) + { + twiddle_factors[j] = w_pow; + w_pow *= w; + } + + ct a, b; + + // now compute the inverse decimation in frequency. This first + // outer loop loops log2(len) number of times + unsigned long skip = half; + for (unsigned long step = 1; step <= half; step <<= 1) + { + // do blocks of butterflies in this loop + for (unsigned long j = 0; j < len; j += step*2) + { + // do step butterflies + for (unsigned long k = 0; k < step; ++k) + { + const unsigned long a_idx = j+k; + const unsigned long b_idx = j+k+step; + data[b_idx] *= twiddle_factors[k*skip]; + a = data[a_idx] + data[b_idx]; + b = data[a_idx] - data[b_idx]; + data[a_idx] = a; + data[b_idx] = b; + } + } + skip /= 2; + } + } + +// ---------------------------------------------------------------------------------------- + +} +#endif // DLIB_BIGINT_KERNEL_2_CPp_ + diff --git a/ml/dlib/dlib/bigint/bigint_kernel_2.h b/ml/dlib/dlib/bigint/bigint_kernel_2.h new file mode 100644 index 000000000..cbd8f895d --- /dev/null +++ b/ml/dlib/dlib/bigint/bigint_kernel_2.h @@ -0,0 +1,570 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_BIGINT_KERNEl_2_ +#define DLIB_BIGINT_KERNEl_2_ + +#include "bigint_kernel_abstract.h" +#include "../algs.h" +#include "../serialize.h" +#include "../uintn.h" +#include <iosfwd> +#include <cmath> +#include <complex> +#include <vector> + +namespace dlib +{ + + class bigint_kernel_2 + { + /*! + INITIAL VALUE + slack == 25 + data->number[0] == 0 + data->size == slack + data->references == 1 + data->digits_used == 1 + + + CONVENTION + slack == the number of extra digits placed into the number when it is + created. the slack value should never be less than 1 + + data->number == pointer to an array of data->size uint16s. + data represents a string of base 65535 numbers with data[0] being + the least significant bit and data[data->digits_used-1] being the most + significant + + + NOTE: In the comments I will consider a word to be a 16 bit value + + + data->digits_used == the number of significant digits in the number. + data->digits_used tells us the number of used elements in the + data->number array so everything beyond data->number[data->digits_used-1] + is undefined + + data->references == the number of bigint_kernel_2 objects which refer + to this data_record + !*/ + + + struct data_record + { + + + explicit data_record( + uint32 size_ + ) : + size(size_), + number(new uint16[size_]), + references(1), + digits_used(1) + {*number = 0;} + /*! + ensures + - initializes *this to represent zero + !*/ + + data_record( + const data_record& item, + uint32 additional_size + ) : + size(item.digits_used + additional_size), + number(new uint16[size]), + references(1), + digits_used(item.digits_used) + { + uint16* source = item.number; + uint16* dest = number; + uint16* end = source + digits_used; + while (source != end) + { + *dest = *source; + ++dest; + ++source; + } + } + /*! + ensures + - *this is a copy of item except with + size == item.digits_used + additional_size + !*/ + + ~data_record( + ) + { + delete [] number; + } + + + const uint32 size; + uint16* number; + uint32 references; + uint32 digits_used; + + private: + // no copy constructor + data_record ( data_record&); + }; + + + // note that the second parameter is just there + // to resolve the ambiguity between this constructor and + // bigint_kernel_2(uint32) + explicit bigint_kernel_2 ( + data_record* data_, int + ): slack(25),data(data_) {} + /*! + ensures + - *this is initialized with data_ as its data member + !*/ + + public: + + bigint_kernel_2 ( + ); + + bigint_kernel_2 ( + uint32 value + ); + + bigint_kernel_2 ( + const bigint_kernel_2& item + ); + + virtual ~bigint_kernel_2 ( + ); + + const bigint_kernel_2 operator+ ( + const bigint_kernel_2& rhs + ) const; + + bigint_kernel_2& operator+= ( + const bigint_kernel_2& rhs + ); + + const bigint_kernel_2 operator- ( + const bigint_kernel_2& rhs + ) const; + + bigint_kernel_2& operator-= ( + const bigint_kernel_2& rhs + ); + + const bigint_kernel_2 operator* ( + const bigint_kernel_2& rhs + ) const; + + bigint_kernel_2& operator*= ( + const bigint_kernel_2& rhs + ); + + const bigint_kernel_2 operator/ ( + const bigint_kernel_2& rhs + ) const; + + bigint_kernel_2& operator/= ( + const bigint_kernel_2& rhs + ); + + const bigint_kernel_2 operator% ( + const bigint_kernel_2& rhs + ) const; + + bigint_kernel_2& operator%= ( + const bigint_kernel_2& rhs + ); + + bool operator < ( + const bigint_kernel_2& rhs + ) const; + + bool operator == ( + const bigint_kernel_2& rhs + ) const; + + bigint_kernel_2& operator= ( + const bigint_kernel_2& rhs + ); + + friend std::ostream& operator<< ( + std::ostream& out, + const bigint_kernel_2& rhs + ); + + friend std::istream& operator>> ( + std::istream& in, + bigint_kernel_2& rhs + ); + + bigint_kernel_2& operator++ ( + ); + + const bigint_kernel_2 operator++ ( + int + ); + + bigint_kernel_2& operator-- ( + ); + + const bigint_kernel_2 operator-- ( + int + ); + + friend const bigint_kernel_2 operator+ ( + uint16 lhs, + const bigint_kernel_2& rhs + ); + + friend const bigint_kernel_2 operator+ ( + const bigint_kernel_2& lhs, + uint16 rhs + ); + + bigint_kernel_2& operator+= ( + uint16 rhs + ); + + friend const bigint_kernel_2 operator- ( + uint16 lhs, + const bigint_kernel_2& rhs + ); + + friend const bigint_kernel_2 operator- ( + const bigint_kernel_2& lhs, + uint16 rhs + ); + + bigint_kernel_2& operator-= ( + uint16 rhs + ); + + friend const bigint_kernel_2 operator* ( + uint16 lhs, + const bigint_kernel_2& rhs + ); + + friend const bigint_kernel_2 operator* ( + const bigint_kernel_2& lhs, + uint16 rhs + ); + + bigint_kernel_2& operator*= ( + uint16 rhs + ); + + friend const bigint_kernel_2 operator/ ( + uint16 lhs, + const bigint_kernel_2& rhs + ); + + friend const bigint_kernel_2 operator/ ( + const bigint_kernel_2& lhs, + uint16 rhs + ); + + bigint_kernel_2& operator/= ( + uint16 rhs + ); + + friend const bigint_kernel_2 operator% ( + uint16 lhs, + const bigint_kernel_2& rhs + ); + + friend const bigint_kernel_2 operator% ( + const bigint_kernel_2& lhs, + uint16 rhs + ); + + bigint_kernel_2& operator%= ( + uint16 rhs + ); + + friend bool operator < ( + uint16 lhs, + const bigint_kernel_2& rhs + ); + + friend bool operator < ( + const bigint_kernel_2& lhs, + uint16 rhs + ); + + friend bool operator == ( + const bigint_kernel_2& lhs, + uint16 rhs + ); + + friend bool operator == ( + uint16 lhs, + const bigint_kernel_2& rhs + ); + + bigint_kernel_2& operator= ( + uint16 rhs + ); + + + void swap ( + bigint_kernel_2& item + ) { data_record* temp = data; data = item.data; item.data = temp; } + + + private: + + typedef double t; + typedef std::complex<t> ct; + + void fft( + ct* data, + unsigned long len + ) const; + /*! + requires + - len == x^n for some integer n (i.e. len is a power of 2) + - len > 0 + ensures + - #data == the FT decimation in frequency of data + !*/ + + void ifft( + ct* data, + unsigned long len + ) const; + /*! + requires + - len == x^n for some integer n (i.e. len is a power of 2) + - len > 0 + ensures + - #data == the inverse decimation in frequency of data. + (i.e. the inverse of what fft(data,len,-1) does to data) + !*/ + + void long_add ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const; + /*! + requires + - result->size >= max(lhs->digits_used,rhs->digits_used) + 1 + ensures + - result == lhs + rhs + !*/ + + void long_sub ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const; + /*! + requires + - lhs >= rhs + - result->size >= lhs->digits_used + ensures + - result == lhs - rhs + !*/ + + void long_div ( + const data_record* lhs, + const data_record* rhs, + data_record* result, + data_record* remainder + ) const; + /*! + requires + - rhs != 0 + - result->size >= lhs->digits_used + - remainder->size >= lhs->digits_used + - each parameter is unique (i.e. lhs != result, lhs != remainder, etc.) + ensures + - result == lhs / rhs + - remainder == lhs % rhs + !*/ + + void long_mul ( + const data_record* lhs, + const data_record* rhs, + data_record* result + ) const; + /*! + requires + - result->size >= lhs->digits_used + rhs->digits_used + - result != lhs + - result != rhs + ensures + - result == lhs * rhs + !*/ + + void short_add ( + const data_record* data, + uint16 value, + data_record* result + ) const; + /*! + requires + - result->size >= data->size + 1 + ensures + - result == data + value + !*/ + + void short_sub ( + const data_record* data, + uint16 value, + data_record* result + ) const; + /*! + requires + - data >= value + - result->size >= data->digits_used + ensures + - result == data - value + !*/ + + void short_mul ( + const data_record* data, + uint16 value, + data_record* result + ) const; + /*! + requires + - result->size >= data->digits_used + 1 + ensures + - result == data * value + !*/ + + void short_div ( + const data_record* data, + uint16 value, + data_record* result, + uint16& remainder + ) const; + /*! + requires + - value != 0 + - result->size >= data->digits_used + ensures + - result = data*value + - remainder = data%value + !*/ + + void shift_left ( + const data_record* data, + data_record* result, + uint32 shift_amount + ) const; + /*! + requires + - result->size >= data->digits_used + shift_amount/8 + 1 + ensures + - result == data << shift_amount + !*/ + + void shift_right ( + const data_record* data, + data_record* result + ) const; + /*! + requires + - result->size >= data->digits_used + ensures + - result == data >> 1 + !*/ + + bool is_less_than ( + const data_record* lhs, + const data_record* rhs + ) const; + /*! + ensures + - returns true if lhs < rhs + - returns false otherwise + !*/ + + bool is_equal_to ( + const data_record* lhs, + const data_record* rhs + ) const; + /*! + ensures + - returns true if lhs == rhs + - returns false otherwise + !*/ + + void increment ( + const data_record* source, + data_record* dest + ) const; + /*! + requires + - dest->size >= source->digits_used + 1 + ensures + - dest = source + 1 + !*/ + + void decrement ( + const data_record* source, + data_record* dest + ) const; + /*! + requires + source != 0 + ensuers + dest = source - 1 + !*/ + + // member data + const uint32 slack; + data_record* data; + + + + }; + + inline void swap ( + bigint_kernel_2& a, + bigint_kernel_2& b + ) { a.swap(b); } + + inline void serialize ( + const bigint_kernel_2& item, + std::ostream& out + ) + { + std::ios::fmtflags oldflags = out.flags(); + out.flags(); + out << item << ' '; + out.flags(oldflags); + if (!out) throw serialization_error("Error serializing object of type bigint_kernel_c"); + } + + inline void deserialize ( + bigint_kernel_2& item, + std::istream& in + ) + { + std::ios::fmtflags oldflags = in.flags(); + in.flags(); + in >> item; in.flags(oldflags); + if (in.get() != ' ') + { + item = 0; + throw serialization_error("Error deserializing object of type bigint_kernel_c"); + } + } + + inline bool operator> (const bigint_kernel_2& a, const bigint_kernel_2& b) { return b < a; } + inline bool operator!= (const bigint_kernel_2& a, const bigint_kernel_2& b) { return !(a == b); } + inline bool operator<= (const bigint_kernel_2& a, const bigint_kernel_2& b) { return !(b < a); } + inline bool operator>= (const bigint_kernel_2& a, const bigint_kernel_2& b) { return !(a < b); } + +} + +#ifdef NO_MAKEFILE +#include "bigint_kernel_2.cpp" +#endif + +#endif // DLIB_BIGINT_KERNEl_2_ + diff --git a/ml/dlib/dlib/bigint/bigint_kernel_abstract.h b/ml/dlib/dlib/bigint/bigint_kernel_abstract.h new file mode 100644 index 000000000..99a54520b --- /dev/null +++ b/ml/dlib/dlib/bigint/bigint_kernel_abstract.h @@ -0,0 +1,670 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#undef DLIB_BIGINT_KERNEl_ABSTRACT_ +#ifdef DLIB_BIGINT_KERNEl_ABSTRACT_ + +#include <iosfwd> +#include "../algs.h" +#include "../serialize.h" +#include "../uintn.h" + +namespace dlib +{ + + class bigint + { + /*! + INITIAL VALUE + *this == 0 + + WHAT THIS OBJECT REPRESENTS + This object represents an arbitrary precision unsigned integer + + the following operators are supported: + operator + + operator += + operator - + operator -= + operator * + operator *= + operator / + operator /= + operator % + operator %= + operator == + operator < + operator = + operator << (for writing to ostreams) + operator >> (for reading from istreams) + operator++ // pre increment + operator++(int) // post increment + operator-- // pre decrement + operator--(int) // post decrement + + + the other comparason operators(>, !=, <=, and >=) are + available and come from the templates in dlib::relational_operators + + THREAD SAFETY + bigint may be reference counted so it is very unthread safe. + use with care in a multithreaded program + + !*/ + + public: + + bigint ( + ); + /*! + ensures + - #*this is properly initialized + throws + - std::bad_alloc + if this is thrown the bigint will be unusable but + will not leak memory + !*/ + + bigint ( + uint32 value + ); + /*! + requires + - value <= (2^32)-1 + ensures + - #*this is properly initialized + - #*this == value + throws + - std::bad_alloc + if this is thrown the bigint will be unusable but + will not leak memory + !*/ + + bigint ( + const bigint& item + ); + /*! + ensures + - #*this is properly initialized + - #*this == value + throws + - std::bad_alloc + if this is thrown the bigint will be unusable but + will not leak memory + !*/ + + virtual ~bigint ( + ); + /*! + ensures + - all resources associated with #*this have been released + !*/ + + const bigint operator+ ( + const bigint& rhs + ) const; + /*! + ensures + - returns the result of adding rhs to *this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator+= ( + const bigint& rhs + ); + /*! + ensures + - #*this == *this + rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + const bigint operator- ( + const bigint& rhs + ) const; + /*! + requires + - *this >= rhs + ensures + - returns the result of subtracting rhs from *this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator-= ( + const bigint& rhs + ); + /*! + requires + - *this >= rhs + ensures + - #*this == *this - rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + const bigint operator* ( + const bigint& rhs + ) const; + /*! + ensures + - returns the result of multiplying *this and rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator*= ( + const bigint& rhs + ); + /*! + ensures + - #*this == *this * rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + const bigint operator/ ( + const bigint& rhs + ) const; + /*! + requires + - rhs != 0 + ensures + - returns the result of dividing *this by rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator/= ( + const bigint& rhs + ); + /*! + requires + - rhs != 0 + ensures + - #*this == *this / rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + const bigint operator% ( + const bigint& rhs + ) const; + /*! + requires + - rhs != 0 + ensures + - returns the result of *this mod rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator%= ( + const bigint& rhs + ); + /*! + requires + - rhs != 0 + ensures + - #*this == *this % rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bool operator < ( + const bigint& rhs + ) const; + /*! + ensures + - returns true if *this is less than rhs + - returns false otherwise + !*/ + + bool operator == ( + const bigint& rhs + ) const; + /*! + ensures + - returns true if *this and rhs represent the same number + - returns false otherwise + !*/ + + bigint& operator= ( + const bigint& rhs + ); + /*! + ensures + - #*this == rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + + friend std::ostream& operator<< ( + std::ostream& out, + const bigint& rhs + ); + /*! + ensures + - the number in *this has been written to #out as a base ten number + throws + - std::bad_alloc + if this function throws then it has no effect (nothing + is written to out) + !*/ + + friend std::istream& operator>> ( + std::istream& in, + bigint& rhs + ); + /*! + ensures + - reads a number from in and puts it into #*this + - if (there is no positive base ten number on the input stream ) then + - #in.fail() == true + throws + - std::bad_alloc + if this function throws the value in rhs is undefined and some + characters may have been read from in. rhs is still usable though, + its value is just unknown. + !*/ + + + bigint& operator++ ( + ); + /*! + ensures + - #*this == *this + 1 + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + const bigint operator++ ( + int + ); + /*! + ensures + - #*this == *this + 1 + - returns *this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator-- ( + ); + /*! + requires + - *this != 0 + ensures + - #*this == *this - 1 + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + const bigint operator-- ( + int + ); + /*! + requires + - *this != 0 + ensures + - #*this == *this - 1 + - returns *this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + void swap ( + bigint& item + ); + /*! + ensures + - swaps *this and item + !*/ + + + // ------------------------------------------------------------------ + // ---- The following functions are identical to the above ----- + // ---- but take uint16 as one of their arguments. They --- + // ---- exist only to allow for a more efficient implementation --- + // ------------------------------------------------------------------ + + + friend const bigint operator+ ( + uint16 lhs, + const bigint& rhs + ); + /*! + requires + - lhs <= 65535 + ensures + - returns the result of adding rhs to lhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator+ ( + const bigint& lhs, + uint16 rhs + ); + /*! + requires + - rhs <= 65535 + ensures + - returns the result of adding rhs to lhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator+= ( + uint16 rhs + ); + /*! + requires + - rhs <= 65535 + ensures + - #*this == *this + rhs + - returns #this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator- ( + uint16 lhs, + const bigint& rhs + ); + /*! + requires + - lhs >= rhs + - lhs <= 65535 + ensures + - returns the result of subtracting rhs from lhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator- ( + const bigint& lhs, + uint16 rhs + ); + /*! + requires + - lhs >= rhs + - rhs <= 65535 + ensures + - returns the result of subtracting rhs from lhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator-= ( + uint16 rhs + ); + /*! + requires + - *this >= rhs + - rhs <= 65535 + ensures + - #*this == *this - rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator* ( + uint16 lhs, + const bigint& rhs + ); + /*! + requires + - lhs <= 65535 + ensures + - returns the result of multiplying lhs and rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator* ( + const bigint& lhs, + uint16 rhs + ); + /*! + requires + - rhs <= 65535 + ensures + - returns the result of multiplying lhs and rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator*= ( + uint16 rhs + ); + /*! + requires + - rhs <= 65535 + ensures + - #*this == *this * rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator/ ( + uint16 lhs, + const bigint& rhs + ); + /*! + requires + - rhs != 0 + - lhs <= 65535 + ensures + - returns the result of dividing lhs by rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator/ ( + const bigint& lhs, + uint16 rhs + ); + /*! + requires + - rhs != 0 + - rhs <= 65535 + ensures + - returns the result of dividing lhs by rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator/= ( + uint16 rhs + ); + /*! + requires + - rhs != 0 + - rhs <= 65535 + ensures + - #*this == *this / rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator% ( + uint16 lhs, + const bigint& rhs + ); + /*! + requires + - rhs != 0 + - lhs <= 65535 + ensures + - returns the result of lhs mod rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + friend const bigint operator% ( + const bigint& lhs, + uint16 rhs + ); + /*! + requires + - rhs != 0 + - rhs <= 65535 + ensures + - returns the result of lhs mod rhs + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + bigint& operator%= ( + uint16 rhs + ); + /*! + requires + - rhs != 0 + - rhs <= 65535 + ensures + - #*this == *this % rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + + friend bool operator < ( + uint16 lhs, + const bigint& rhs + ); + /*! + requires + - lhs <= 65535 + ensures + - returns true if lhs is less than rhs + - returns false otherwise + !*/ + + friend bool operator < ( + const bigint& lhs, + uint16 rhs + ); + /*! + requires + - rhs <= 65535 + ensures + - returns true if lhs is less than rhs + - returns false otherwise + !*/ + + friend bool operator == ( + const bigint& lhs, + uint16 rhs + ); + /*! + requires + - rhs <= 65535 + ensures + - returns true if lhs and rhs represent the same number + - returns false otherwise + !*/ + + friend bool operator == ( + uint16 lhs, + const bigint& rhs + ); + /*! + requires + - lhs <= 65535 + ensures + - returns true if lhs and rhs represent the same number + - returns false otherwise + !*/ + + bigint& operator= ( + uint16 rhs + ); + /*! + requires + - rhs <= 65535 + ensures + - #*this == rhs + - returns #*this + throws + - std::bad_alloc + if this function throws then it has no effect + !*/ + + }; + + inline void swap ( + bigint& a, + bigint& b + ) { a.swap(b); } + /*! + provides a global swap function + !*/ + + void serialize ( + const bigint& item, + std::istream& in + ); + /*! + provides serialization support + !*/ + + void deserialize ( + bigint& item, + std::istream& in + ); + /*! + provides deserialization support + !*/ + + inline bool operator> (const bigint& a, const bigint& b) { return b < a; } + inline bool operator!= (const bigint& a, const bigint& b) { return !(a == b); } + inline bool operator<= (const bigint& a, const bigint& b) { return !(b < a); } + inline bool operator>= (const bigint& a, const bigint& b) { return !(a < b); } +} + +#endif // DLIB_BIGINT_KERNEl_ABSTRACT_ + diff --git a/ml/dlib/dlib/bigint/bigint_kernel_c.h b/ml/dlib/dlib/bigint/bigint_kernel_c.h new file mode 100644 index 000000000..954869a38 --- /dev/null +++ b/ml/dlib/dlib/bigint/bigint_kernel_c.h @@ -0,0 +1,1141 @@ +// Copyright (C) 2003 Davis E. King (davis@dlib.net) +// License: Boost Software License See LICENSE.txt for the full license. +#ifndef DLIB_BIGINT_KERNEl_C_ +#define DLIB_BIGINT_KERNEl_C_ + +#include "bigint_kernel_abstract.h" +#include "../algs.h" +#include "../assert.h" +#include <iostream> + +namespace dlib +{ + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + class bigint_kernel_c + { + bigint_base data; + + explicit bigint_kernel_c ( + const bigint_base& item + ) : data(item) {} + + public: + + + bigint_kernel_c ( + ); + + bigint_kernel_c ( + uint32 value + ); + + bigint_kernel_c ( + const bigint_kernel_c<bigint_base>& item + ); + + ~bigint_kernel_c ( + ); + + const bigint_kernel_c<bigint_base> operator+ ( + const bigint_kernel_c<bigint_base>& rhs + ) const; + + bigint_kernel_c<bigint_base>& operator+= ( + const bigint_kernel_c<bigint_base>& rhs + ); + + const bigint_kernel_c<bigint_base> operator- ( + const bigint_kernel_c<bigint_base>& rhs + ) const; + bigint_kernel_c<bigint_base>& operator-= ( + const bigint_kernel_c<bigint_base>& rhs + ); + + const bigint_kernel_c<bigint_base> operator* ( + const bigint_kernel_c<bigint_base>& rhs + ) const; + + bigint_kernel_c<bigint_base>& operator*= ( + const bigint_kernel_c<bigint_base>& rhs + ); + + const bigint_kernel_c<bigint_base> operator/ ( + const bigint_kernel_c<bigint_base>& rhs + ) const; + + bigint_kernel_c<bigint_base>& operator/= ( + const bigint_kernel_c<bigint_base>& rhs + ); + + const bigint_kernel_c<bigint_base> operator% ( + const bigint_kernel_c<bigint_base>& rhs + ) const; + + bigint_kernel_c<bigint_base>& operator%= ( + const bigint_kernel_c<bigint_base>& rhs + ); + + bool operator < ( + const bigint_kernel_c<bigint_base>& rhs + ) const; + + bool operator == ( + const bigint_kernel_c<bigint_base>& rhs + ) const; + + bigint_kernel_c<bigint_base>& operator= ( + const bigint_kernel_c<bigint_base>& rhs + ); + + template <typename T> + friend std::ostream& operator<< ( + std::ostream& out, + const bigint_kernel_c<T>& rhs + ); + + template <typename T> + friend std::istream& operator>> ( + std::istream& in, + bigint_kernel_c<T>& rhs + ); + + bigint_kernel_c<bigint_base>& operator++ ( + ); + + const bigint_kernel_c<bigint_base> operator++ ( + int + ); + + bigint_kernel_c<bigint_base>& operator-- ( + ); + + const bigint_kernel_c<bigint_base> operator-- ( + int + ); + + template <typename T> + friend const bigint_kernel_c<T> operator+ ( + uint16 lhs, + const bigint_kernel_c<T>& rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator+ ( + const bigint_kernel_c<T>& lhs, + uint16 rhs + ); + + bigint_kernel_c<bigint_base>& operator+= ( + uint16 rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator- ( + uint16 lhs, + const bigint_kernel_c<T>& rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator- ( + const bigint_kernel_c<T>& lhs, + uint16 rhs + ); + + bigint_kernel_c<bigint_base>& operator-= ( + uint16 rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator* ( + uint16 lhs, + const bigint_kernel_c<T>& rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator* ( + const bigint_kernel_c<T>& lhs, + uint16 rhs + ); + + bigint_kernel_c<bigint_base>& operator*= ( + uint16 rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator/ ( + uint16 lhs, + const bigint_kernel_c<T>& rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator/ ( + const bigint_kernel_c<T>& lhs, + uint16 rhs + ); + + bigint_kernel_c<bigint_base>& operator/= ( + uint16 rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator% ( + uint16 lhs, + const bigint_kernel_c<T>& rhs + ); + + template <typename T> + friend const bigint_kernel_c<T> operator% ( + const bigint_kernel_c<T>& lhs, + uint16 rhs + ); + + bigint_kernel_c<bigint_base>& operator%= ( + uint16 rhs + ); + + template <typename T> + friend bool operator < ( + uint16 lhs, + const bigint_kernel_c<T>& rhs + ); + + template <typename T> + friend bool operator < ( + const bigint_kernel_c<T>& lhs, + uint16 rhs + ); + + template <typename T> + friend bool operator == ( + const bigint_kernel_c<T>& lhs, + uint16 rhs + ); + + template <typename T> + friend bool operator == ( + uint16 lhs, + const bigint_kernel_c<T>& rhs + ); + + bigint_kernel_c<bigint_base>& operator= ( + uint16 rhs + ); + + + void swap ( + bigint_kernel_c<bigint_base>& item + ) { data.swap(item.data); } + + }; + + template < + typename bigint_base + > + void swap ( + bigint_kernel_c<bigint_base>& a, + bigint_kernel_c<bigint_base>& b + ) { a.swap(b); } + + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + inline void serialize ( + const bigint_kernel_c<bigint_base>& item, + std::ostream& out + ) + { + std::ios::fmtflags oldflags = out.flags(); + out.flags(); + out << item << ' '; + out.flags(oldflags); + if (!out) throw serialization_error("Error serializing object of type bigint_kernel_c"); + } + + template < + typename bigint_base + > + inline void deserialize ( + bigint_kernel_c<bigint_base>& item, + std::istream& in + ) + { + std::ios::fmtflags oldflags = in.flags(); + in.flags(); + in >> item; in.flags(oldflags); + if (in.get() != ' ') + { + item = 0; + throw serialization_error("Error deserializing object of type bigint_kernel_c"); + } + } + +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + // member function definitions +// ---------------------------------------------------------------------------------------- +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>:: + bigint_kernel_c ( + ) + {} + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>:: + bigint_kernel_c ( + uint32 value + ) : + data(value) + { + // make sure requires clause is not broken + DLIB_CASSERT( value <= 0xFFFFFFFF , + "\tbigint::bigint(uint16)" + << "\n\t value must be <= (2^32)-1" + << "\n\tthis: " << this + << "\n\tvalue: " << value + ); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>:: + bigint_kernel_c ( + const bigint_kernel_c<bigint_base>& item + ) : + data(item.data) + {} + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>:: + ~bigint_kernel_c ( + ) + {} + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> bigint_kernel_c<bigint_base>:: + operator+ ( + const bigint_kernel_c<bigint_base>& rhs + ) const + { + return bigint_kernel_c<bigint_base>(data + rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator+= ( + const bigint_kernel_c<bigint_base>& rhs + ) + { + data += rhs.data; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> bigint_kernel_c<bigint_base>:: + operator- ( + const bigint_kernel_c<bigint_base>& rhs + ) const + { + // make sure requires clause is not broken + DLIB_CASSERT( !(*this < rhs), + "\tconst bigint bigint::operator-(const bigint&)" + << "\n\t *this should not be less than rhs" + << "\n\tthis: " << this + << "\n\t*this: " << *this + << "\n\trhs: " << rhs + ); + + // call the real function + return bigint_kernel_c<bigint_base>(data-rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator-= ( + const bigint_kernel_c<bigint_base>& rhs + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( !(*this < rhs), + "\tbigint& bigint::operator-=(const bigint&)" + << "\n\t *this should not be less than rhs" + << "\n\tthis: " << this + << "\n\t*this: " << *this + << "\n\trhs: " << rhs + ); + + // call the real function + data -= rhs.data; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> bigint_kernel_c<bigint_base>:: + operator* ( + const bigint_kernel_c<bigint_base>& rhs + ) const + { + return bigint_kernel_c<bigint_base>(data * rhs.data ); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator*= ( + const bigint_kernel_c<bigint_base>& rhs + ) + { + data *= rhs.data; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> bigint_kernel_c<bigint_base>:: + operator/ ( + const bigint_kernel_c<bigint_base>& rhs + ) const + { + //make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0), + "\tconst bigint bigint::operator/(const bigint&)" + << "\n\t can't divide by zero" + << "\n\tthis: " << this + ); + + // call the real function + return bigint_kernel_c<bigint_base>(data/rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator/= ( + const bigint_kernel_c<bigint_base>& rhs + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0), + "\tbigint& bigint::operator/=(const bigint&)" + << "\n\t can't divide by zero" + << "\n\tthis: " << this + ); + + // call the real function + data /= rhs.data; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> bigint_kernel_c<bigint_base>:: + operator% ( + const bigint_kernel_c<bigint_base>& rhs + ) const + { + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0), + "\tconst bigint bigint::operator%(const bigint&)" + << "\n\t can't divide by zero" + << "\n\tthis: " << this + ); + + // call the real function + return bigint_kernel_c<bigint_base>(data%rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator%= ( + const bigint_kernel_c<bigint_base>& rhs + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0), + "\tbigint& bigint::operator%=(const bigint&)" + << "\n\t can't divide by zero" + << "\n\tthis: " << this + ); + + // call the real function + data %= rhs.data; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bool bigint_kernel_c<bigint_base>:: + operator < ( + const bigint_kernel_c<bigint_base>& rhs + ) const + { + return data < rhs.data; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bool bigint_kernel_c<bigint_base>:: + operator == ( + const bigint_kernel_c<bigint_base>& rhs + ) const + { + return data == rhs.data; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator= ( + const bigint_kernel_c<bigint_base>& rhs + ) + { + data = rhs.data; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + std::ostream& operator<< ( + std::ostream& out, + const bigint_kernel_c<bigint_base>& rhs + ) + { + out << rhs.data; + return out; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + std::istream& operator>> ( + std::istream& in, + bigint_kernel_c<bigint_base>& rhs + ) + { + in >> rhs.data; + return in; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator++ ( + ) + { + ++data; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> bigint_kernel_c<bigint_base>:: + operator++ ( + int + ) + { + return bigint_kernel_c<bigint_base>(data++); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator-- ( + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( !(*this == 0), + "\tbigint& bigint::operator--()" + << "\n\t *this to subtract from *this it must not be zero to begin with" + << "\n\tthis: " << this + ); + + // call the real function + --data; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> bigint_kernel_c<bigint_base>:: + operator-- ( + int + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( !(*this == 0), + "\tconst bigint bigint::operator--(int)" + << "\n\t *this to subtract from *this it must not be zero to begin with" + << "\n\tthis: " << this + ); + + // call the real function + return bigint_kernel_c<bigint_base>(data--); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator+ ( + uint16 l, + const bigint_kernel_c<bigint_base>& rhs + ) + { + uint32 lhs = l; + // make sure requires clause is not broken + DLIB_CASSERT( lhs <= 65535, + "\tconst bigint operator+(uint16, const bigint&)" + << "\n\t lhs must be <= 65535" + << "\n\trhs: " << rhs + << "\n\tlhs: " << lhs + ); + + return bigint_kernel_c<bigint_base>(static_cast<uint16>(lhs)+rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator+ ( + const bigint_kernel_c<bigint_base>& lhs, + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( rhs <= 65535, + "\tconst bigint operator+(const bigint&, uint16)" + << "\n\t rhs must be <= 65535" + << "\n\trhs: " << rhs + << "\n\tlhs: " << lhs + ); + + return bigint_kernel_c<bigint_base>(lhs.data+static_cast<uint16>(rhs)); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator+= ( + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( rhs <= 65535, + "\tbigint& bigint::operator+=(uint16)" + << "\n\t rhs must be <= 65535" + << "\n\tthis: " << this + << "\n\t*this: " << *this + << "\n\trhs: " << rhs + ); + + data += rhs; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator- ( + uint16 l, + const bigint_kernel_c<bigint_base>& rhs + ) + { + uint32 lhs = l; + // make sure requires clause is not broken + DLIB_CASSERT( !(static_cast<uint16>(lhs) < rhs) && lhs <= 65535, + "\tconst bigint operator-(uint16,const bigint&)" + << "\n\t lhs must be greater than or equal to rhs and lhs <= 65535" + << "\n\tlhs: " << lhs + << "\n\trhs: " << rhs + << "\n\t&lhs: " << &lhs + << "\n\t&rhs: " << &rhs + ); + + // call the real function + return bigint_kernel_c<bigint_base>(static_cast<uint16>(lhs)-rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator- ( + const bigint_kernel_c<bigint_base>& lhs, + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( !(lhs < static_cast<uint16>(rhs)) && rhs <= 65535, + "\tconst bigint operator-(const bigint&,uint16)" + << "\n\t lhs must be greater than or equal to rhs and rhs <= 65535" + << "\n\tlhs: " << lhs + << "\n\trhs: " << rhs + << "\n\t&lhs: " << &lhs + << "\n\t&rhs: " << &rhs + ); + + // call the real function + return bigint_kernel_c<bigint_base>(lhs.data-static_cast<uint16>(rhs)); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator-= ( + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( !(*this < static_cast<uint16>(rhs)) && rhs <= 65535, + "\tbigint& bigint::operator-=(uint16)" + << "\n\t *this must not be less than rhs and rhs <= 65535" + << "\n\tthis: " << this + << "\n\t*this: " << *this + << "\n\trhs: " << rhs + ); + + // call the real function + data -= static_cast<uint16>(rhs); + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator* ( + uint16 l, + const bigint_kernel_c<bigint_base>& rhs + ) + { + uint32 lhs = l; + // make sure requires clause is not broken + DLIB_CASSERT( lhs <= 65535, + "\tconst bigint operator*(uint16, const bigint&)" + << "\n\t lhs must be <= 65535" + << "\n\trhs: " << rhs + << "\n\tlhs: " << lhs + ); + + return bigint_kernel_c<bigint_base>(lhs*rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator* ( + const bigint_kernel_c<bigint_base>& lhs, + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( rhs <= 65535, + "\tconst bigint operator*(const bigint&, uint16)" + << "\n\t rhs must be <= 65535" + << "\n\trhs: " << rhs + << "\n\tlhs: " << lhs + ); + + return bigint_kernel_c<bigint_base>(lhs.data*rhs); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator*= ( + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( rhs <= 65535, + "\t bigint bigint::operator*=(uint16)" + << "\n\t rhs must be <= 65535" + << "\n\tthis: " << this + << "\n\t*this: " << *this + << "\n\trhs: " << rhs + ); + + data *= static_cast<uint16>(rhs); + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator/ ( + uint16 l, + const bigint_kernel_c<bigint_base>& rhs + ) + { + uint32 lhs = l; + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0) && lhs <= 65535, + "\tconst bigint operator/(uint16,const bigint&)" + << "\n\t you can't divide by zero and lhs <= 65535" + << "\n\t&lhs: " << &lhs + << "\n\t&rhs: " << &rhs + << "\n\tlhs: " << lhs + ); + + // call the real function + return bigint_kernel_c<bigint_base>(lhs/rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator/ ( + const bigint_kernel_c<bigint_base>& lhs, + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0) && rhs <= 65535, + "\tconst bigint operator/(const bigint&,uint16)" + << "\n\t you can't divide by zero and rhs <= 65535" + << "\n\t&lhs: " << &lhs + << "\n\t&rhs: " << &rhs + << "\n\trhs: " << rhs + ); + + // call the real function + return bigint_kernel_c<bigint_base>(lhs.data/static_cast<uint16>(rhs)); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator/= ( + uint16 rhs + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0) && static_cast<uint32>(rhs) <= 65535, + "\tbigint& bigint::operator/=(uint16)" + << "\n\t you can't divide by zero and rhs must be <= 65535" + << "\n\tthis: " << this + << "\n\trhs: " << rhs + ); + + // call the real function + data /= rhs; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator% ( + uint16 lhs, + const bigint_kernel_c<bigint_base>& rhs + ) + { + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0) && static_cast<uint32>(lhs) <= 65535, + "\tconst bigint operator%(uint16,const bigint&)" + << "\n\t you can't divide by zero and lhs must be <= 65535" + << "\n\t&lhs: " << &lhs + << "\n\t&rhs: " << &rhs + << "\n\tlhs: " << lhs + ); + + // call the real function + return bigint_kernel_c<bigint_base>(lhs%rhs.data); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + const bigint_kernel_c<bigint_base> operator% ( + const bigint_kernel_c<bigint_base>& lhs, + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0) && rhs <= 65535, + "\tconst bigint operator%(const bigint&,uint16)" + << "\n\t you can't divide by zero and rhs must be <= 65535" + << "\n\t&lhs: " << &lhs + << "\n\t&rhs: " << &rhs + << "\n\trhs: " << rhs + ); + + // call the real function + return bigint_kernel_c<bigint_base>(lhs.data%static_cast<uint16>(rhs)); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator%= ( + uint16 r + ) + { + + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( !(rhs == 0) && rhs <= 65535, + "\tbigint& bigint::operator%=(uint16)" + << "\n\t you can't divide by zero and rhs must be <= 65535" + << "\n\tthis: " << this + << "\n\trhs: " << rhs + ); + + // call the real function + data %= rhs; + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bool operator < ( + uint16 l, + const bigint_kernel_c<bigint_base>& rhs + ) + { + uint32 lhs = l; + // make sure requires clause is not broken + DLIB_CASSERT( lhs <= 65535, + "\tbool operator<(uint16, const bigint&)" + << "\n\t lhs must be <= 65535" + << "\n\trhs: " << rhs + << "\n\tlhs: " << lhs + ); + + return static_cast<uint16>(lhs) < rhs.data; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bool operator < ( + const bigint_kernel_c<bigint_base>& lhs, + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( rhs <= 65535, + "\tbool operator<(const bigint&, uint16)" + << "\n\t rhs must be <= 65535" + << "\n\trhs: " << rhs + << "\n\tlhs: " << lhs + ); + + return lhs.data < static_cast<uint16>(rhs); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bool operator == ( + const bigint_kernel_c<bigint_base>& lhs, + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( rhs <= 65535, + "\tbool operator==(const bigint&, uint16)" + << "\n\t rhs must be <= 65535" + << "\n\trhs: " << rhs + << "\n\tlhs: " << lhs + ); + + return lhs.data == static_cast<uint16>(rhs); + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bool operator == ( + uint16 l, + const bigint_kernel_c<bigint_base>& rhs + ) + { + uint32 lhs = l; + // make sure requires clause is not broken + DLIB_CASSERT( lhs <= 65535, + "\tbool operator==(uint16, const bigint&)" + << "\n\t lhs must be <= 65535" + << "\n\trhs: " << rhs + << "\n\tlhs: " << lhs + ); + + return static_cast<uint16>(lhs) == rhs.data; + } + +// ---------------------------------------------------------------------------------------- + + template < + typename bigint_base + > + bigint_kernel_c<bigint_base>& bigint_kernel_c<bigint_base>:: + operator= ( + uint16 r + ) + { + uint32 rhs = r; + // make sure requires clause is not broken + DLIB_CASSERT( rhs <= 65535, + "\tbigint bigint::operator=(uint16)" + << "\n\t rhs must be <= 65535" + << "\n\t*this: " << *this + << "\n\tthis: " << this + << "\n\tlhs: " << rhs + ); + + data = static_cast<uint16>(rhs); + return *this; + } + +// ---------------------------------------------------------------------------------------- + + template < typename bigint_base > + inline bool operator> (const bigint_kernel_c<bigint_base>& a, const bigint_kernel_c<bigint_base>& b) { return b < a; } + template < typename bigint_base > + inline bool operator!= (const bigint_kernel_c<bigint_base>& a, const bigint_kernel_c<bigint_base>& b) { return !(a == b); } + template < typename bigint_base > + inline bool operator<= (const bigint_kernel_c<bigint_base>& a, const bigint_kernel_c<bigint_base>& b) { return !(b < a); } + template < typename bigint_base > + inline bool operator>= (const bigint_kernel_c<bigint_base>& a, const bigint_kernel_c<bigint_base>& b) { return !(a < b); } + +// ---------------------------------------------------------------------------------------- + +} + +#endif // DLIB_BIGINT_KERNEl_C_ + |