aboutsummaryrefslogtreecommitdiffstats
path: root/src/math/bigint
diff options
context:
space:
mode:
Diffstat (limited to 'src/math/bigint')
-rw-r--r--src/math/bigint/big_code.cpp150
-rw-r--r--src/math/bigint/big_io.cpp55
-rw-r--r--src/math/bigint/big_ops2.cpp221
-rw-r--r--src/math/bigint/big_ops3.cpp191
-rw-r--r--src/math/bigint/big_rand.cpp48
-rw-r--r--src/math/bigint/bigint.cpp350
-rw-r--r--src/math/bigint/bigint.h570
-rw-r--r--src/math/bigint/divide.cpp140
-rw-r--r--src/math/bigint/divide.h29
-rw-r--r--src/math/bigint/info.txt25
10 files changed, 0 insertions, 1779 deletions
diff --git a/src/math/bigint/big_code.cpp b/src/math/bigint/big_code.cpp
deleted file mode 100644
index 972312cdb..000000000
--- a/src/math/bigint/big_code.cpp
+++ /dev/null
@@ -1,150 +0,0 @@
-/*
-* BigInt Encoding/Decoding
-* (C) 1999-2010,2012 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/bigint.h>
-#include <botan/divide.h>
-#include <botan/charset.h>
-#include <botan/hex.h>
-
-namespace Botan {
-
-/*
-* Encode a BigInt
-*/
-void BigInt::encode(byte output[], const BigInt& n, Base base)
- {
- if(base == Binary)
- {
- n.binary_encode(output);
- }
- else if(base == Hexadecimal)
- {
- secure_vector<byte> binary(n.encoded_size(Binary));
- n.binary_encode(&binary[0]);
-
- hex_encode(reinterpret_cast<char*>(output),
- &binary[0], binary.size());
- }
- else if(base == Decimal)
- {
- BigInt copy = n;
- BigInt remainder;
- copy.set_sign(Positive);
- const size_t output_size = n.encoded_size(Decimal);
- for(size_t j = 0; j != output_size; ++j)
- {
- divide(copy, 10, copy, remainder);
- output[output_size - 1 - j] =
- Charset::digit2char(static_cast<byte>(remainder.word_at(0)));
- if(copy.is_zero())
- break;
- }
- }
- else
- throw Invalid_Argument("Unknown BigInt encoding method");
- }
-
-/*
-* Encode a BigInt
-*/
-std::vector<byte> BigInt::encode(const BigInt& n, Base base)
- {
- std::vector<byte> output(n.encoded_size(base));
- encode(&output[0], n, base);
- if(base != Binary)
- for(size_t j = 0; j != output.size(); ++j)
- if(output[j] == 0)
- output[j] = '0';
- return output;
- }
-
-/*
-* Encode a BigInt
-*/
-secure_vector<byte> BigInt::encode_locked(const BigInt& n, Base base)
- {
- secure_vector<byte> output(n.encoded_size(base));
- encode(&output[0], n, base);
- if(base != Binary)
- for(size_t j = 0; j != output.size(); ++j)
- if(output[j] == 0)
- output[j] = '0';
- return output;
- }
-
-/*
-* Encode a BigInt, with leading 0s if needed
-*/
-secure_vector<byte> BigInt::encode_1363(const BigInt& n, size_t bytes)
- {
- const size_t n_bytes = n.bytes();
- if(n_bytes > bytes)
- throw Encoding_Error("encode_1363: n is too large to encode properly");
-
- const size_t leading_0s = bytes - n_bytes;
-
- secure_vector<byte> output(bytes);
- encode(&output[leading_0s], n, Binary);
- return output;
- }
-
-/*
-* Decode a BigInt
-*/
-BigInt BigInt::decode(const byte buf[], size_t length, Base base)
- {
- BigInt r;
- if(base == Binary)
- r.binary_decode(buf, length);
- else if(base == Hexadecimal)
- {
- secure_vector<byte> binary;
-
- if(length % 2)
- {
- // Handle lack of leading 0
- const char buf0_with_leading_0[2] =
- { '0', static_cast<char>(buf[0]) };
-
- binary = hex_decode_locked(buf0_with_leading_0, 2);
-
- binary += hex_decode_locked(reinterpret_cast<const char*>(&buf[1]),
- length - 1,
- false);
- }
- else
- binary = hex_decode_locked(reinterpret_cast<const char*>(buf),
- length, false);
-
- r.binary_decode(&binary[0], binary.size());
- }
- else if(base == Decimal)
- {
- for(size_t i = 0; i != length; ++i)
- {
- if(Charset::is_space(buf[i]))
- continue;
-
- if(!Charset::is_digit(buf[i]))
- throw Invalid_Argument("BigInt::decode: "
- "Invalid character in decimal input");
-
- const byte x = Charset::char2digit(buf[i]);
-
- if(x >= 10)
- throw Invalid_Argument("BigInt: Invalid decimal string");
-
- r *= 10;
- r += x;
- }
- }
- else
- throw Invalid_Argument("Unknown BigInt decoding method");
- return r;
- }
-
-}
diff --git a/src/math/bigint/big_io.cpp b/src/math/bigint/big_io.cpp
deleted file mode 100644
index b561c218f..000000000
--- a/src/math/bigint/big_io.cpp
+++ /dev/null
@@ -1,55 +0,0 @@
-/*
-* BigInt Input/Output
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/bigint.h>
-#include <iostream>
-
-namespace Botan {
-
-/*
-* Write the BigInt into a stream
-*/
-std::ostream& operator<<(std::ostream& stream, const BigInt& n)
- {
- BigInt::Base base = BigInt::Decimal;
- if(stream.flags() & std::ios::hex)
- base = BigInt::Hexadecimal;
- else if(stream.flags() & std::ios::oct)
- throw std::runtime_error("Octal output of BigInt not supported");
-
- if(n == 0)
- stream.write("0", 1);
- else
- {
- if(n < 0)
- stream.write("-", 1);
- const std::vector<byte> buffer = BigInt::encode(n, base);
- size_t skip = 0;
- while(skip < buffer.size() && buffer[skip] == '0')
- ++skip;
- stream.write(reinterpret_cast<const char*>(&buffer[0]) + skip,
- buffer.size() - skip);
- }
- if(!stream.good())
- throw Stream_IO_Error("BigInt output operator has failed");
- return stream;
- }
-
-/*
-* Read the BigInt from a stream
-*/
-std::istream& operator>>(std::istream& stream, BigInt& n)
- {
- std::string str;
- std::getline(stream, str);
- if(stream.bad() || (stream.fail() && !stream.eof()))
- throw Stream_IO_Error("BigInt input operator has failed");
- n = BigInt(str);
- return stream;
- }
-
-}
diff --git a/src/math/bigint/big_ops2.cpp b/src/math/bigint/big_ops2.cpp
deleted file mode 100644
index 37b6a5df1..000000000
--- a/src/math/bigint/big_ops2.cpp
+++ /dev/null
@@ -1,221 +0,0 @@
-/*
-* BigInt Assignment Operators
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/bigint.h>
-#include <botan/internal/mp_core.h>
-#include <botan/internal/bit_ops.h>
-#include <algorithm>
-
-namespace Botan {
-
-/*
-* Addition Operator
-*/
-BigInt& BigInt::operator+=(const BigInt& y)
- {
- const size_t x_sw = sig_words(), y_sw = y.sig_words();
-
- const size_t reg_size = std::max(x_sw, y_sw) + 1;
- grow_to(reg_size);
-
- if(sign() == y.sign())
- bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
- else
- {
- s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
-
- if(relative_size < 0)
- {
- secure_vector<word> z(reg_size - 1);
- bigint_sub3(&z[0], y.data(), reg_size - 1, data(), x_sw);
- std::swap(m_reg, z);
- set_sign(y.sign());
- }
- else if(relative_size == 0)
- {
- zeroise(m_reg);
- set_sign(Positive);
- }
- else if(relative_size > 0)
- bigint_sub2(mutable_data(), x_sw, y.data(), y_sw);
- }
-
- return (*this);
- }
-
-/*
-* Subtraction Operator
-*/
-BigInt& BigInt::operator-=(const BigInt& y)
- {
- const size_t x_sw = sig_words(), y_sw = y.sig_words();
-
- s32bit relative_size = bigint_cmp(data(), x_sw, y.data(), y_sw);
-
- const size_t reg_size = std::max(x_sw, y_sw) + 1;
- grow_to(reg_size);
-
- if(relative_size < 0)
- {
- if(sign() == y.sign())
- bigint_sub2_rev(mutable_data(), y.data(), y_sw);
- else
- bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
-
- set_sign(y.reverse_sign());
- }
- else if(relative_size == 0)
- {
- if(sign() == y.sign())
- {
- clear();
- set_sign(Positive);
- }
- else
- bigint_shl1(mutable_data(), x_sw, 0, 1);
- }
- else if(relative_size > 0)
- {
- if(sign() == y.sign())
- bigint_sub2(mutable_data(), x_sw, y.data(), y_sw);
- else
- bigint_add2(mutable_data(), reg_size - 1, y.data(), y_sw);
- }
-
- return (*this);
- }
-
-/*
-* Multiplication Operator
-*/
-BigInt& BigInt::operator*=(const BigInt& y)
- {
- const size_t x_sw = sig_words(), y_sw = y.sig_words();
- set_sign((sign() == y.sign()) ? Positive : Negative);
-
- if(x_sw == 0 || y_sw == 0)
- {
- clear();
- set_sign(Positive);
- }
- else if(x_sw == 1 && y_sw)
- {
- grow_to(y_sw + 2);
- bigint_linmul3(mutable_data(), y.data(), y_sw, word_at(0));
- }
- else if(y_sw == 1 && x_sw)
- {
- grow_to(x_sw + 2);
- bigint_linmul2(mutable_data(), x_sw, y.word_at(0));
- }
- else
- {
- grow_to(size() + y.size());
-
- secure_vector<word> z(data(), data() + x_sw);
- secure_vector<word> workspace(size());
-
- bigint_mul(mutable_data(), size(), &workspace[0],
- &z[0], z.size(), x_sw,
- y.data(), y.size(), y_sw);
- }
-
- return (*this);
- }
-
-/*
-* Division Operator
-*/
-BigInt& BigInt::operator/=(const BigInt& y)
- {
- if(y.sig_words() == 1 && is_power_of_2(y.word_at(0)))
- (*this) >>= (y.bits() - 1);
- else
- (*this) = (*this) / y;
- return (*this);
- }
-
-/*
-* Modulo Operator
-*/
-BigInt& BigInt::operator%=(const BigInt& mod)
- {
- return (*this = (*this) % mod);
- }
-
-/*
-* Modulo Operator
-*/
-word BigInt::operator%=(word mod)
- {
- if(mod == 0)
- throw BigInt::DivideByZero();
-
- if(is_power_of_2(mod))
- {
- word result = (word_at(0) & (mod - 1));
- clear();
- grow_to(2);
- m_reg[0] = result;
- return result;
- }
-
- word remainder = 0;
-
- for(size_t j = sig_words(); j > 0; --j)
- remainder = bigint_modop(remainder, word_at(j-1), mod);
- clear();
- grow_to(2);
-
- if(remainder && sign() == BigInt::Negative)
- m_reg[0] = mod - remainder;
- else
- m_reg[0] = remainder;
-
- set_sign(BigInt::Positive);
-
- return word_at(0);
- }
-
-/*
-* Left Shift Operator
-*/
-BigInt& BigInt::operator<<=(size_t shift)
- {
- if(shift)
- {
- const size_t shift_words = shift / MP_WORD_BITS,
- shift_bits = shift % MP_WORD_BITS,
- words = sig_words();
-
- grow_to(words + shift_words + (shift_bits ? 1 : 0));
- bigint_shl1(mutable_data(), words, shift_words, shift_bits);
- }
-
- return (*this);
- }
-
-/*
-* Right Shift Operator
-*/
-BigInt& BigInt::operator>>=(size_t shift)
- {
- if(shift)
- {
- const size_t shift_words = shift / MP_WORD_BITS,
- shift_bits = shift % MP_WORD_BITS;
-
- bigint_shr1(mutable_data(), sig_words(), shift_words, shift_bits);
-
- if(is_zero())
- set_sign(Positive);
- }
-
- return (*this);
- }
-
-}
diff --git a/src/math/bigint/big_ops3.cpp b/src/math/bigint/big_ops3.cpp
deleted file mode 100644
index cad730197..000000000
--- a/src/math/bigint/big_ops3.cpp
+++ /dev/null
@@ -1,191 +0,0 @@
-/*
-* BigInt Binary Operators
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/bigint.h>
-#include <botan/divide.h>
-#include <botan/internal/mp_core.h>
-#include <botan/internal/bit_ops.h>
-#include <algorithm>
-
-namespace Botan {
-
-/*
-* Addition Operator
-*/
-BigInt operator+(const BigInt& x, const BigInt& y)
- {
- const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
-
- BigInt z(x.sign(), std::max(x_sw, y_sw) + 1);
-
- if((x.sign() == y.sign()))
- bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
- else
- {
- s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
-
- if(relative_size < 0)
- {
- bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
- z.set_sign(y.sign());
- }
- else if(relative_size == 0)
- z.set_sign(BigInt::Positive);
- else if(relative_size > 0)
- bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
- }
-
- return z;
- }
-
-/*
-* Subtraction Operator
-*/
-BigInt operator-(const BigInt& x, const BigInt& y)
- {
- const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
-
- s32bit relative_size = bigint_cmp(x.data(), x_sw, y.data(), y_sw);
-
- BigInt z(BigInt::Positive, std::max(x_sw, y_sw) + 1);
-
- if(relative_size < 0)
- {
- if(x.sign() == y.sign())
- bigint_sub3(z.mutable_data(), y.data(), y_sw, x.data(), x_sw);
- else
- bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
- z.set_sign(y.reverse_sign());
- }
- else if(relative_size == 0)
- {
- if(x.sign() != y.sign())
- bigint_shl2(z.mutable_data(), x.data(), x_sw, 0, 1);
- }
- else if(relative_size > 0)
- {
- if(x.sign() == y.sign())
- bigint_sub3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
- else
- bigint_add3(z.mutable_data(), x.data(), x_sw, y.data(), y_sw);
- z.set_sign(x.sign());
- }
- return z;
- }
-
-/*
-* Multiplication Operator
-*/
-BigInt operator*(const BigInt& x, const BigInt& y)
- {
- const size_t x_sw = x.sig_words(), y_sw = y.sig_words();
-
- BigInt z(BigInt::Positive, x.size() + y.size());
-
- if(x_sw == 1 && y_sw)
- bigint_linmul3(z.mutable_data(), y.data(), y_sw, x.word_at(0));
- else if(y_sw == 1 && x_sw)
- bigint_linmul3(z.mutable_data(), x.data(), x_sw, y.word_at(0));
- else if(x_sw && y_sw)
- {
- secure_vector<word> workspace(z.size());
- bigint_mul(z.mutable_data(), z.size(), &workspace[0],
- x.data(), x.size(), x_sw,
- y.data(), y.size(), y_sw);
- }
-
- if(x_sw && y_sw && x.sign() != y.sign())
- z.flip_sign();
- return z;
- }
-
-/*
-* Division Operator
-*/
-BigInt operator/(const BigInt& x, const BigInt& y)
- {
- BigInt q, r;
- divide(x, y, q, r);
- return q;
- }
-
-/*
-* Modulo Operator
-*/
-BigInt operator%(const BigInt& n, const BigInt& mod)
- {
- if(mod.is_zero())
- throw BigInt::DivideByZero();
- if(mod.is_negative())
- throw Invalid_Argument("BigInt::operator%: modulus must be > 0");
- if(n.is_positive() && mod.is_positive() && n < mod)
- return n;
-
- BigInt q, r;
- divide(n, mod, q, r);
- return r;
- }
-
-/*
-* Modulo Operator
-*/
-word operator%(const BigInt& n, word mod)
- {
- if(mod == 0)
- throw BigInt::DivideByZero();
-
- if(is_power_of_2(mod))
- return (n.word_at(0) & (mod - 1));
-
- word remainder = 0;
-
- for(size_t j = n.sig_words(); j > 0; --j)
- remainder = bigint_modop(remainder, n.word_at(j-1), mod);
-
- if(remainder && n.sign() == BigInt::Negative)
- return mod - remainder;
- return remainder;
- }
-
-/*
-* Left Shift Operator
-*/
-BigInt operator<<(const BigInt& x, size_t shift)
- {
- if(shift == 0)
- return x;
-
- const size_t shift_words = shift / MP_WORD_BITS,
- shift_bits = shift % MP_WORD_BITS;
-
- const size_t x_sw = x.sig_words();
-
- BigInt y(x.sign(), x_sw + shift_words + (shift_bits ? 1 : 0));
- bigint_shl2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
- return y;
- }
-
-/*
-* Right Shift Operator
-*/
-BigInt operator>>(const BigInt& x, size_t shift)
- {
- if(shift == 0)
- return x;
- if(x.bits() <= shift)
- return 0;
-
- const size_t shift_words = shift / MP_WORD_BITS,
- shift_bits = shift % MP_WORD_BITS,
- x_sw = x.sig_words();
-
- BigInt y(x.sign(), x_sw - shift_words);
- bigint_shr2(y.mutable_data(), x.data(), x_sw, shift_words, shift_bits);
- return y;
- }
-
-}
diff --git a/src/math/bigint/big_rand.cpp b/src/math/bigint/big_rand.cpp
deleted file mode 100644
index 78b9ee244..000000000
--- a/src/math/bigint/big_rand.cpp
+++ /dev/null
@@ -1,48 +0,0 @@
-/*
-* BigInt Random Generation
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/bigint.h>
-#include <botan/parsing.h>
-
-namespace Botan {
-
-/*
-* Randomize this number
-*/
-void BigInt::randomize(RandomNumberGenerator& rng,
- size_t bitsize)
- {
- set_sign(Positive);
-
- if(bitsize == 0)
- clear();
- else
- {
- secure_vector<byte> array = rng.random_vec((bitsize + 7) / 8);
-
- if(bitsize % 8)
- array[0] &= 0xFF >> (8 - (bitsize % 8));
- array[0] |= 0x80 >> ((bitsize % 8) ? (8 - bitsize % 8) : 0);
- binary_decode(&array[0], array.size());
- }
- }
-
-/*
-* Generate a random integer within given range
-*/
-BigInt BigInt::random_integer(RandomNumberGenerator& rng,
- const BigInt& min, const BigInt& max)
- {
- BigInt range = max - min;
-
- if(range <= 0)
- throw Invalid_Argument("random_integer: invalid min/max values");
-
- return (min + (BigInt(rng, range.bits() + 2) % range));
- }
-
-}
diff --git a/src/math/bigint/bigint.cpp b/src/math/bigint/bigint.cpp
deleted file mode 100644
index 45c351256..000000000
--- a/src/math/bigint/bigint.cpp
+++ /dev/null
@@ -1,350 +0,0 @@
-/*
-* BigInt Base
-* (C) 1999-2011,2012 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/bigint.h>
-#include <botan/internal/mp_core.h>
-#include <botan/get_byte.h>
-#include <botan/parsing.h>
-#include <botan/internal/rounding.h>
-
-namespace Botan {
-
-/*
-* Construct a BigInt from a regular number
-*/
-BigInt::BigInt(u64bit n)
- {
- set_sign(Positive);
-
- if(n == 0)
- return;
-
- const size_t limbs_needed = sizeof(u64bit) / sizeof(word);
-
- m_reg.resize(4*limbs_needed);
- for(size_t i = 0; i != limbs_needed; ++i)
- m_reg[i] = ((n >> (i*MP_WORD_BITS)) & MP_WORD_MASK);
- }
-
-/*
-* Construct a BigInt of the specified size
-*/
-BigInt::BigInt(Sign s, size_t size)
- {
- m_reg.resize(round_up<size_t>(size, 8));
- m_signedness = s;
- }
-
-/*
-* Copy constructor
-*/
-BigInt::BigInt(const BigInt& other)
- {
- m_reg = other.m_reg;
- m_signedness = other.m_signedness;
- }
-
-/*
-* Construct a BigInt from a string
-*/
-BigInt::BigInt(const std::string& str)
- {
- Base base = Decimal;
- size_t markers = 0;
- bool negative = false;
-
- if(str.length() > 0 && str[0] == '-')
- {
- markers += 1;
- negative = true;
- }
-
- if(str.length() > markers + 2 && str[markers ] == '0' &&
- str[markers + 1] == 'x')
- {
- markers += 2;
- base = Hexadecimal;
- }
-
- *this = decode(reinterpret_cast<const byte*>(str.data()) + markers,
- str.length() - markers, base);
-
- if(negative) set_sign(Negative);
- else set_sign(Positive);
- }
-
-/*
-* Construct a BigInt from an encoded BigInt
-*/
-BigInt::BigInt(const byte input[], size_t length, Base base)
- {
- set_sign(Positive);
- *this = decode(input, length, base);
- }
-
-/*
-* Construct a BigInt from an encoded BigInt
-*/
-BigInt::BigInt(RandomNumberGenerator& rng, size_t bits)
- {
- set_sign(Positive);
- randomize(rng, bits);
- }
-
-/*
-* Grow the internal storage
-*/
-void BigInt::grow_to(size_t n)
- {
- if(n > size())
- m_reg.resize(round_up<size_t>(n, 8));
- }
-
-/*
-* Comparison Function
-*/
-s32bit BigInt::cmp(const BigInt& other, bool check_signs) const
- {
- if(check_signs)
- {
- if(other.is_positive() && this->is_negative())
- return -1;
-
- if(other.is_negative() && this->is_positive())
- return 1;
-
- if(other.is_negative() && this->is_negative())
- return (-bigint_cmp(this->data(), this->sig_words(),
- other.data(), other.sig_words()));
- }
-
- return bigint_cmp(this->data(), this->sig_words(),
- other.data(), other.sig_words());
- }
-
-/*
-* Return byte n of this number
-*/
-byte BigInt::byte_at(size_t n) const
- {
- const size_t WORD_BYTES = sizeof(word);
- size_t word_num = n / WORD_BYTES, byte_num = n % WORD_BYTES;
- if(word_num >= size())
- return 0;
- else
- return get_byte(WORD_BYTES - byte_num - 1, m_reg[word_num]);
- }
-
-/*
-* Return bit n of this number
-*/
-bool BigInt::get_bit(size_t n) const
- {
- return ((word_at(n / MP_WORD_BITS) >> (n % MP_WORD_BITS)) & 1);
- }
-
-/*
-* Return bits {offset...offset+length}
-*/
-u32bit BigInt::get_substring(size_t offset, size_t length) const
- {
- if(length > 32)
- throw Invalid_Argument("BigInt::get_substring: Substring size too big");
-
- u64bit piece = 0;
- for(size_t i = 0; i != 8; ++i)
- {
- const byte part = byte_at((offset / 8) + (7-i));
- piece = (piece << 8) | part;
- }
-
- const u64bit mask = (static_cast<u64bit>(1) << length) - 1;
- const size_t shift = (offset % 8);
-
- return static_cast<u32bit>((piece >> shift) & mask);
- }
-
-/*
-* Convert this number to a u32bit, if possible
-*/
-u32bit BigInt::to_u32bit() const
- {
- if(is_negative())
- throw Encoding_Error("BigInt::to_u32bit: Number is negative");
- if(bits() >= 32)
- throw Encoding_Error("BigInt::to_u32bit: Number is too big to convert");
-
- u32bit out = 0;
- for(u32bit j = 0; j != 4; ++j)
- out = (out << 8) | byte_at(3-j);
- return out;
- }
-
-/*
-* Set bit number n
-*/
-void BigInt::set_bit(size_t n)
- {
- const size_t which = n / MP_WORD_BITS;
- const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
- if(which >= size()) grow_to(which + 1);
- m_reg[which] |= mask;
- }
-
-/*
-* Clear bit number n
-*/
-void BigInt::clear_bit(size_t n)
- {
- const size_t which = n / MP_WORD_BITS;
- const word mask = static_cast<word>(1) << (n % MP_WORD_BITS);
- if(which < size())
- m_reg[which] &= ~mask;
- }
-
-/*
-* Clear all but the lowest n bits
-*/
-void BigInt::mask_bits(size_t n)
- {
- if(n == 0) { clear(); return; }
- if(n >= bits()) return;
-
- const size_t top_word = n / MP_WORD_BITS;
- const word mask = (static_cast<word>(1) << (n % MP_WORD_BITS)) - 1;
-
- if(top_word < size())
- clear_mem(&m_reg[top_word+1], size() - (top_word + 1));
-
- m_reg[top_word] &= mask;
- }
-
-/*
-* Count how many bytes are being used
-*/
-size_t BigInt::bytes() const
- {
- return (bits() + 7) / 8;
- }
-
-/*
-* Count how many bits are being used
-*/
-size_t BigInt::bits() const
- {
- const size_t words = sig_words();
-
- if(words == 0)
- return 0;
-
- size_t full_words = words - 1, top_bits = MP_WORD_BITS;
- word top_word = word_at(full_words), mask = MP_WORD_TOP_BIT;
-
- while(top_bits && ((top_word & mask) == 0))
- { mask >>= 1; top_bits--; }
-
- return (full_words * MP_WORD_BITS + top_bits);
- }
-
-/*
-* Calcluate the size in a certain base
-*/
-size_t BigInt::encoded_size(Base base) const
- {
- static const double LOG_2_BASE_10 = 0.30102999566;
-
- if(base == Binary)
- return bytes();
- else if(base == Hexadecimal)
- return 2*bytes();
- else if(base == Decimal)
- return static_cast<size_t>((bits() * LOG_2_BASE_10) + 1);
- else
- throw Invalid_Argument("Unknown base for BigInt encoding");
- }
-
-/*
-* Set the sign
-*/
-void BigInt::set_sign(Sign s)
- {
- if(is_zero())
- m_signedness = Positive;
- else
- m_signedness = s;
- }
-
-/*
-* Reverse the value of the sign flag
-*/
-void BigInt::flip_sign()
- {
- set_sign(reverse_sign());
- }
-
-/*
-* Return the opposite value of the current sign
-*/
-BigInt::Sign BigInt::reverse_sign() const
- {
- if(sign() == Positive)
- return Negative;
- return Positive;
- }
-
-/*
-* Return the negation of this number
-*/
-BigInt BigInt::operator-() const
- {
- BigInt x = (*this);
- x.flip_sign();
- return x;
- }
-
-/*
-* Return the absolute value of this number
-*/
-BigInt BigInt::abs() const
- {
- BigInt x = (*this);
- x.set_sign(Positive);
- return x;
- }
-
-/*
-* Encode this number into bytes
-*/
-void BigInt::binary_encode(byte output[]) const
- {
- const size_t sig_bytes = bytes();
- for(size_t i = 0; i != sig_bytes; ++i)
- output[sig_bytes-i-1] = byte_at(i);
- }
-
-/*
-* Set this number to the value in buf
-*/
-void BigInt::binary_decode(const byte buf[], size_t length)
- {
- const size_t WORD_BYTES = sizeof(word);
-
- clear();
- m_reg.resize(round_up<size_t>((length / WORD_BYTES) + 1, 8));
-
- for(size_t i = 0; i != length / WORD_BYTES; ++i)
- {
- const size_t top = length - WORD_BYTES*i;
- for(size_t j = WORD_BYTES; j > 0; --j)
- m_reg[i] = (m_reg[i] << 8) | buf[top - j];
- }
-
- for(size_t i = 0; i != length % WORD_BYTES; ++i)
- m_reg[length / WORD_BYTES] = (m_reg[length / WORD_BYTES] << 8) | buf[i];
- }
-
-}
diff --git a/src/math/bigint/bigint.h b/src/math/bigint/bigint.h
deleted file mode 100644
index 08b7d53fc..000000000
--- a/src/math/bigint/bigint.h
+++ /dev/null
@@ -1,570 +0,0 @@
-/*
-* BigInt
-* (C) 1999-2008,2012 Jack Lloyd
-* 2007 FlexSecure
-*
-* Distributed under the terms of the Botan license
-*/
-
-#ifndef BOTAN_BIGINT_H__
-#define BOTAN_BIGINT_H__
-
-#include <botan/rng.h>
-#include <botan/secmem.h>
-#include <botan/mp_types.h>
-#include <iosfwd>
-
-namespace Botan {
-
-/**
-* Arbitrary precision integer
-*/
-class BOTAN_DLL BigInt
- {
- public:
- /**
- * Base enumerator for encoding and decoding
- */
- enum Base { Decimal = 10, Hexadecimal = 16, Binary = 256 };
-
- /**
- * Sign symbol definitions for positive and negative numbers
- */
- enum Sign { Negative = 0, Positive = 1 };
-
- /**
- * DivideByZero Exception
- */
- struct BOTAN_DLL DivideByZero : public Exception
- { DivideByZero() : Exception("BigInt divide by zero") {} };
-
- /**
- * Create empty BigInt
- */
- BigInt() { m_signedness = Positive; }
-
- /**
- * Create BigInt from 64 bit integer
- * @param n initial value of this BigInt
- */
- BigInt(u64bit n);
-
- /**
- * Copy Constructor
- * @param other the BigInt to copy
- */
- BigInt(const BigInt& other);
-
- /**
- * Create BigInt from a string. If the string starts with 0x the
- * rest of the string will be interpreted as hexadecimal digits.
- * Otherwise, it will be interpreted as a decimal number.
- *
- * @param str the string to parse for an integer value
- */
- BigInt(const std::string& str);
-
- /**
- * Create a BigInt from an integer in a byte array
- * @param buf the byte array holding the value
- * @param length size of buf
- * @param base is the number base of the integer in buf
- */
- BigInt(const byte buf[], size_t length, Base base = Binary);
-
- /**
- * Create a random BigInt of the specified size
- * @param rng random number generator
- * @param bits size in bits
- */
- BigInt(RandomNumberGenerator& rng, size_t bits);
-
- /**
- * Create BigInt of specified size, all zeros
- * @param sign the sign
- * @param n size of the internal register in words
- */
- BigInt(Sign sign, size_t n);
-
- /**
- * Move constructor
- */
- BigInt(BigInt&& other)
- {
- this->swap(other);
- }
-
- /**
- * Move assignment
- */
- BigInt& operator=(BigInt&& other)
- {
- if(this != &other)
- this->swap(other);
-
- return (*this);
- }
-
- /**
- * Copy assignment
- */
- BigInt& operator=(const BigInt&) = default;
-
- /**
- * Swap this value with another
- * @param other BigInt to swap values with
- */
- void swap(BigInt& other)
- {
- m_reg.swap(other.m_reg);
- std::swap(m_signedness, other.m_signedness);
- }
-
- /**
- * += operator
- * @param y the BigInt to add to this
- */
- BigInt& operator+=(const BigInt& y);
-
- /**
- * -= operator
- * @param y the BigInt to subtract from this
- */
- BigInt& operator-=(const BigInt& y);
-
- /**
- * *= operator
- * @param y the BigInt to multiply with this
- */
- BigInt& operator*=(const BigInt& y);
-
- /**
- * /= operator
- * @param y the BigInt to divide this by
- */
- BigInt& operator/=(const BigInt& y);
-
- /**
- * Modulo operator
- * @param y the modulus to reduce this by
- */
- BigInt& operator%=(const BigInt& y);
-
- /**
- * Modulo operator
- * @param y the modulus (word) to reduce this by
- */
- word operator%=(word y);
-
- /**
- * Left shift operator
- * @param shift the number of bits to shift this left by
- */
- BigInt& operator<<=(size_t shift);
-
- /**
- * Right shift operator
- * @param shift the number of bits to shift this right by
- */
- BigInt& operator>>=(size_t shift);
-
- /**
- * Increment operator
- */
- BigInt& operator++() { return (*this += 1); }
-
- /**
- * Decrement operator
- */
- BigInt& operator--() { return (*this -= 1); }
-
- /**
- * Postfix increment operator
- */
- BigInt operator++(int) { BigInt x = (*this); ++(*this); return x; }
-
- /**
- * Postfix decrement operator
- */
- BigInt operator--(int) { BigInt x = (*this); --(*this); return x; }
-
- /**
- * Unary negation operator
- * @return negative this
- */
- BigInt operator-() const;
-
- /**
- * ! operator
- * @return true iff this is zero, otherwise false
- */
- bool operator !() const { return (!is_nonzero()); }
-
- /**
- * Zeroize the BigInt. The size of the underlying register is not
- * modified.
- */
- void clear() { zeroise(m_reg); }
-
- /**
- * Compare this to another BigInt
- * @param n the BigInt value to compare with
- * @param check_signs include sign in comparison?
- * @result if (this<n) return -1, if (this>n) return 1, if both
- * values are identical return 0 [like Perl's <=> operator]
- */
- s32bit cmp(const BigInt& n, bool check_signs = true) const;
-
- /**
- * Test if the integer has an even value
- * @result true if the integer is even, false otherwise
- */
- bool is_even() const { return (get_bit(0) == 0); }
-
- /**
- * Test if the integer has an odd value
- * @result true if the integer is odd, false otherwise
- */
- bool is_odd() const { return (get_bit(0) == 1); }
-
- /**
- * Test if the integer is not zero
- * @result true if the integer is non-zero, false otherwise
- */
- bool is_nonzero() const { return (!is_zero()); }
-
- /**
- * Test if the integer is zero
- * @result true if the integer is zero, false otherwise
- */
- bool is_zero() const
- {
- const size_t sw = sig_words();
-
- for(size_t i = 0; i != sw; ++i)
- if(m_reg[i])
- return false;
- return true;
- }
-
- /**
- * Set bit at specified position
- * @param n bit position to set
- */
- void set_bit(size_t n);
-
- /**
- * Clear bit at specified position
- * @param n bit position to clear
- */
- void clear_bit(size_t n);
-
- /**
- * Clear all but the lowest n bits
- * @param n amount of bits to keep
- */
- void mask_bits(size_t n);
-
- /**
- * Return bit value at specified position
- * @param n the bit offset to test
- * @result true, if the bit at position n is set, false otherwise
- */
- bool get_bit(size_t n) const;
-
- /**
- * Return (a maximum of) 32 bits of the complete value
- * @param offset the offset to start extracting
- * @param length amount of bits to extract (starting at offset)
- * @result the integer extracted from the register starting at
- * offset with specified length
- */
- u32bit get_substring(size_t offset, size_t length) const;
-
- /**
- * Convert this value into a u32bit, if it is in the range
- * [0 ... 2**32-1], or otherwise throw an exception.
- * @result the value as a u32bit if conversion is possible
- */
- u32bit to_u32bit() const;
-
- /**
- * @param n the offset to get a byte from
- * @result byte at offset n
- */
- byte byte_at(size_t n) const;
-
- /**
- * Return the word at a specified position of the internal register
- * @param n position in the register
- * @return value at position n
- */
- word word_at(size_t n) const
- { return ((n < size()) ? m_reg[n] : 0); }
-
- /**
- * Tests if the sign of the integer is negative
- * @result true, iff the integer has a negative sign
- */
- bool is_negative() const { return (sign() == Negative); }
-
- /**
- * Tests if the sign of the integer is positive
- * @result true, iff the integer has a positive sign
- */
- bool is_positive() const { return (sign() == Positive); }
-
- /**
- * Return the sign of the integer
- * @result the sign of the integer
- */
- Sign sign() const { return (m_signedness); }
-
- /**
- * @result the opposite sign of the represented integer value
- */
- Sign reverse_sign() const;
-
- /**
- * Flip the sign of this BigInt
- */
- void flip_sign();
-
- /**
- * Set sign of the integer
- * @param sign new Sign to set
- */
- void set_sign(Sign sign);
-
- /**
- * @result absolute (positive) value of this
- */
- BigInt abs() const;
-
- /**
- * Give size of internal register
- * @result size of internal register in words
- */
- size_t size() const { return m_reg.size(); }
-
- /**
- * Return how many words we need to hold this value
- * @result significant words of the represented integer value
- */
- size_t sig_words() const
- {
- const word* x = &m_reg[0];
- size_t sig = m_reg.size();
-
- while(sig && (x[sig-1] == 0))
- sig--;
- return sig;
- }
-
- /**
- * Give byte length of the integer
- * @result byte length of the represented integer value
- */
- size_t bytes() const;
-
- /**
- * Get the bit length of the integer
- * @result bit length of the represented integer value
- */
- size_t bits() const;
-
- /**
- * Return a mutable pointer to the register
- * @result a pointer to the start of the internal register
- */
- word* mutable_data() { return &m_reg[0]; }
-
- /**
- * Return a const pointer to the register
- * @result a pointer to the start of the internal register
- */
- const word* data() const { return &m_reg[0]; }
-
- /**
- * Increase internal register buffer to at least n words
- * @param n new size of register
- */
- void grow_to(size_t n);
-
- /**
- * Fill BigInt with a random number with size of bitsize
- * @param rng the random number generator to use
- * @param bitsize number of bits the created random value should have
- */
- void randomize(RandomNumberGenerator& rng, size_t bitsize = 0);
-
- /**
- * Store BigInt-value in a given byte array
- * @param buf destination byte array for the integer value
- */
- void binary_encode(byte buf[]) const;
-
- /**
- * Read integer value from a byte array with given size
- * @param buf byte array buffer containing the integer
- * @param length size of buf
- */
- void binary_decode(const byte buf[], size_t length);
-
- /**
- * Read integer value from a byte array (secure_vector<byte>)
- * @param buf the array to load from
- */
- void binary_decode(const secure_vector<byte>& buf)
- {
- binary_decode(&buf[0], buf.size());
- }
-
- /**
- * @param base the base to measure the size for
- * @return size of this integer in base base
- */
- size_t encoded_size(Base base = Binary) const;
-
- /**
- * @param rng a random number generator
- * @param min the minimum value
- * @param max the maximum value
- * @return random integer between min and max
- */
- static BigInt random_integer(RandomNumberGenerator& rng,
- const BigInt& min,
- const BigInt& max);
-
- /**
- * Create a power of two
- * @param n the power of two to create
- * @return bigint representing 2^n
- */
- static BigInt power_of_2(size_t n)
- {
- BigInt b;
- b.set_bit(n);
- return b;
- }
-
- /**
- * Encode the integer value from a BigInt to a std::vector of bytes
- * @param n the BigInt to use as integer source
- * @param base number-base of resulting byte array representation
- * @result secure_vector of bytes containing the integer with given base
- */
- static std::vector<byte> encode(const BigInt& n, Base base = Binary);
-
- /**
- * Encode the integer value from a BigInt to a secure_vector of bytes
- * @param n the BigInt to use as integer source
- * @param base number-base of resulting byte array representation
- * @result secure_vector of bytes containing the integer with given base
- */
- static secure_vector<byte> encode_locked(const BigInt& n,
- Base base = Binary);
-
- /**
- * Encode the integer value from a BigInt to a byte array
- * @param buf destination byte array for the encoded integer
- * value with given base
- * @param n the BigInt to use as integer source
- * @param base number-base of resulting byte array representation
- */
- static void encode(byte buf[], const BigInt& n, Base base = Binary);
-
- /**
- * Create a BigInt from an integer in a byte array
- * @param buf the binary value to load
- * @param length size of buf
- * @param base number-base of the integer in buf
- * @result BigInt representing the integer in the byte array
- */
- static BigInt decode(const byte buf[], size_t length,
- Base base = Binary);
-
- /**
- * Create a BigInt from an integer in a byte array
- * @param buf the binary value to load
- * @param base number-base of the integer in buf
- * @result BigInt representing the integer in the byte array
- */
- static BigInt decode(const secure_vector<byte>& buf,
- Base base = Binary)
- {
- return BigInt::decode(&buf[0], buf.size(), base);
- }
-
- /**
- * Create a BigInt from an integer in a byte array
- * @param buf the binary value to load
- * @param base number-base of the integer in buf
- * @result BigInt representing the integer in the byte array
- */
- static BigInt decode(const std::vector<byte>& buf,
- Base base = Binary)
- {
- return BigInt::decode(&buf[0], buf.size(), base);
- }
-
- /**
- * Encode a BigInt to a byte array according to IEEE 1363
- * @param n the BigInt to encode
- * @param bytes the length of the resulting secure_vector<byte>
- * @result a secure_vector<byte> containing the encoded BigInt
- */
- static secure_vector<byte> encode_1363(const BigInt& n, size_t bytes);
-
- private:
- secure_vector<word> m_reg;
- Sign m_signedness;
- };
-
-/*
-* Arithmetic Operators
-*/
-BigInt BOTAN_DLL operator+(const BigInt& x, const BigInt& y);
-BigInt BOTAN_DLL operator-(const BigInt& x, const BigInt& y);
-BigInt BOTAN_DLL operator*(const BigInt& x, const BigInt& y);
-BigInt BOTAN_DLL operator/(const BigInt& x, const BigInt& d);
-BigInt BOTAN_DLL operator%(const BigInt& x, const BigInt& m);
-word BOTAN_DLL operator%(const BigInt& x, word m);
-BigInt BOTAN_DLL operator<<(const BigInt& x, size_t n);
-BigInt BOTAN_DLL operator>>(const BigInt& x, size_t n);
-
-/*
-* Comparison Operators
-*/
-inline bool operator==(const BigInt& a, const BigInt& b)
- { return (a.cmp(b) == 0); }
-inline bool operator!=(const BigInt& a, const BigInt& b)
- { return (a.cmp(b) != 0); }
-inline bool operator<=(const BigInt& a, const BigInt& b)
- { return (a.cmp(b) <= 0); }
-inline bool operator>=(const BigInt& a, const BigInt& b)
- { return (a.cmp(b) >= 0); }
-inline bool operator<(const BigInt& a, const BigInt& b)
- { return (a.cmp(b) < 0); }
-inline bool operator>(const BigInt& a, const BigInt& b)
- { return (a.cmp(b) > 0); }
-
-/*
-* I/O Operators
-*/
-BOTAN_DLL std::ostream& operator<<(std::ostream&, const BigInt&);
-BOTAN_DLL std::istream& operator>>(std::istream&, BigInt&);
-
-}
-
-namespace std {
-
-template<>
-inline void swap<Botan::BigInt>(Botan::BigInt& x, Botan::BigInt& y)
- {
- x.swap(y);
- }
-
-}
-
-#endif
diff --git a/src/math/bigint/divide.cpp b/src/math/bigint/divide.cpp
deleted file mode 100644
index 8b21bce13..000000000
--- a/src/math/bigint/divide.cpp
+++ /dev/null
@@ -1,140 +0,0 @@
-/*
-* Division Algorithm
-* (C) 1999-2007,2012 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#include <botan/divide.h>
-#include <botan/internal/mp_core.h>
-#include <botan/internal/mp_madd.h>
-
-namespace Botan {
-
-namespace {
-
-/*
-* Handle signed operands, if necessary
-*/
-void sign_fixup(const BigInt& x, const BigInt& y, BigInt& q, BigInt& r)
- {
- if(x.sign() == BigInt::Negative)
- {
- q.flip_sign();
- if(r.is_nonzero()) { --q; r = y.abs() - r; }
- }
- if(y.sign() == BigInt::Negative)
- q.flip_sign();
- }
-
-bool division_check(word q, word y2, word y1,
- word x3, word x2, word x1)
- {
- // Compute (y3,y2,y1) = (y2,y1) * q
-
- word y3 = 0;
- y1 = word_madd2(q, y1, &y3);
- y2 = word_madd2(q, y2, &y3);
-
- // Return (y3,y2,y1) >? (x3,x2,x1)
-
- if(y3 > x3) return true;
- if(y3 < x3) return false;
-
- if(y2 > x2) return true;
- if(y2 < x2) return false;
-
- if(y1 > x1) return true;
- if(y1 < x1) return false;
-
- return false;
- }
-
-}
-
-/*
-* Solve x = q * y + r
-*/
-void divide(const BigInt& x, const BigInt& y_arg, BigInt& q, BigInt& r)
- {
- if(y_arg.is_zero())
- throw BigInt::DivideByZero();
-
- BigInt y = y_arg;
- const size_t y_words = y.sig_words();
-
- r = x;
- q = 0;
-
- r.set_sign(BigInt::Positive);
- y.set_sign(BigInt::Positive);
-
- s32bit compare = r.cmp(y);
-
- if(compare == 0)
- {
- q = 1;
- r = 0;
- }
- else if(compare > 0)
- {
- size_t shifts = 0;
- word y_top = y.word_at(y.sig_words()-1);
- while(y_top < MP_WORD_TOP_BIT) { y_top <<= 1; ++shifts; }
- y <<= shifts;
- r <<= shifts;
-
- const size_t n = r.sig_words() - 1, t = y_words - 1;
-
- if(n < t)
- throw Internal_Error("BigInt division word sizes");
-
- q.grow_to(n - t + 1);
-
- word* q_words = q.mutable_data();
-
- if(n <= t)
- {
- while(r > y) { r -= y; ++q; }
- r >>= shifts;
- sign_fixup(x, y_arg, q, r);
- return;
- }
-
- BigInt temp = y << (MP_WORD_BITS * (n-t));
-
- while(r >= temp) { r -= temp; q_words[n-t] += 1; }
-
- for(size_t j = n; j != t; --j)
- {
- const word x_j0 = r.word_at(j);
- const word x_j1 = r.word_at(j-1);
- const word y_t = y.word_at(t);
-
- if(x_j0 == y_t)
- q_words[j-t-1] = MP_WORD_MAX;
- else
- q_words[j-t-1] = bigint_divop(x_j0, x_j1, y_t);
-
- while(division_check(q_words[j-t-1],
- y_t, y.word_at(t-1),
- x_j0, x_j1, r.word_at(j-2)))
- {
- q_words[j-t-1] -= 1;
- }
-
- r -= (q_words[j-t-1] * y) << (MP_WORD_BITS * (j-t-1));
-
- if(r.is_negative())
- {
- r += y << (MP_WORD_BITS * (j-t-1));
- q_words[j-t-1] -= 1;
- }
- }
- r >>= shifts;
- }
-
- sign_fixup(x, y_arg, q, r);
- }
-
-}
diff --git a/src/math/bigint/divide.h b/src/math/bigint/divide.h
deleted file mode 100644
index 36aed7854..000000000
--- a/src/math/bigint/divide.h
+++ /dev/null
@@ -1,29 +0,0 @@
-/*
-* Division
-* (C) 1999-2007 Jack Lloyd
-*
-* Distributed under the terms of the Botan license
-*/
-
-#ifndef BOTAN_DIVISON_ALGORITHM_H__
-#define BOTAN_DIVISON_ALGORITHM_H__
-
-#include <botan/bigint.h>
-
-namespace Botan {
-
-/**
-* BigInt Division
-* @param x an integer
-* @param y a non-zero integer
-* @param q will be set to x / y
-* @param r will be set to x % y
-*/
-void BOTAN_DLL divide(const BigInt& x,
- const BigInt& y,
- BigInt& q,
- BigInt& r);
-
-}
-
-#endif
diff --git a/src/math/bigint/info.txt b/src/math/bigint/info.txt
deleted file mode 100644
index b5dabb7bc..000000000
--- a/src/math/bigint/info.txt
+++ /dev/null
@@ -1,25 +0,0 @@
-load_on auto
-
-define BIGINT 20131128
-
-<header:public>
-bigint.h
-divide.h
-</header:public>
-
-<source>
-big_code.cpp
-big_io.cpp
-big_ops2.cpp
-big_ops3.cpp
-big_rand.cpp
-bigint.cpp
-divide.cpp
-</source>
-
-<requires>
-alloc
-mp
-hex
-rng
-</requires>
generated by cgit v1.2.3 (git 2.39.1) at 2024-12-16 18:06:41 +0000