big_integer_gmp.cpp

Go to the documentation of this file.

/*
SeComLib
Copyright 2012-2013 TU Delft, Information Security & Privacy Lab (http://isplab.tudelft.nl/)

Contributors:
Inald Lagendijk (R.L.Lagendijk@TUDelft.nl)
Mihai Todor (todormihai@gmail.com)
Thijs Veugen (P.J.M.Veugen@tudelft.nl)
Zekeriya Erkin (z.erkin@tudelft.nl)

Licensed under the Apache License, Version 2.0 (the "License");
you may not use this file except in compliance with the License.
You may obtain a copy of the License at

http://www.apache.org/licenses/LICENSE-2.0

Unless required by applicable law or agreed to in writing, software
distributed under the License is distributed on an "AS IS" BASIS,
WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
See the License for the specific language governing permissions and
limitations under the License.
*/
#include "big_integer_gmp.h"

namespace SeComLib {
namespace Core {
    void BigIntegerGmp::Initialize (BigIntegerBase<BigIntegerGmp> &input) {
        mpz_init(input.data);
    }
    
    void BigIntegerGmp::Initialize (BigIntegerBase<BigIntegerGmp> &input, const BigIntegerBase<BigIntegerGmp> &value) {
        mpz_init_set(input.data, value.data);
    }
    
    void BigIntegerGmp::Initialize (BigIntegerBase<BigIntegerGmp> &input, const long value) {
        mpz_init_set_si(input.data, value);
    }
    
    void BigIntegerGmp::Initialize (BigIntegerBase<BigIntegerGmp> &input, const unsigned long value) {
        mpz_init_set_ui(input.data, value);
    }
    
    void BigIntegerGmp::Initialize (BigIntegerBase<BigIntegerGmp> &input, const double value, const BigIntegerBase<BigIntegerGmp> &scaling, const bool truncate) {
        mpz_init(input.data);

        mpf_set_default_prec(1024);//1024 is the default value and it should be more than enough

        //auxiliary big float used for applying scaling and rounding before exporting it to input.data
        mpf_t tempFloat;
        //we can't multiply mpf_t with mpz_t, so we need a temporary mpf_t for the scaling
        mpf_t tempScaling;
        //contains the value 0.5, used for the rounding procedure
        mpf_t zeroPointFive;

        //set the value
        mpf_init_set_d(tempFloat, value);
        
        //gmp_printf ("Value: %.*Ff\r\n", 30, tempFloat);

        //set the scaling
        mpf_init(tempScaling);
        mpf_set_z(tempScaling, scaling.data);

        //set 0.5
        mpf_init_set_d(zeroPointFive, 0.5);

        //apply the scaling
        mpf_mul(tempFloat, tempFloat, tempScaling);

        if (truncate) {
            //discard decimals
            mpf_trunc(tempFloat, tempFloat);
        }
        else {
            //round the value to the nearest (positive or negative) integer
            //input < 0.0 ? ceil(input - 0.5) : floor(input + 0.5));
            if (-1 == mpf_sgn(tempFloat)) {
                mpf_sub(tempFloat, tempFloat, zeroPointFive);
                mpf_ceil(tempFloat, tempFloat);
            }
            else {
                mpf_add(tempFloat, tempFloat, zeroPointFive);
                mpf_floor(tempFloat, tempFloat);
            }
        }

        //gmp_printf ("Value: %.*Ff\r\n", 30, tempFloat);

        //finally, transfer the value to our internal data
        mpz_set_f(input.data, tempFloat);
        
        //gmp_printf ("%Zd\r\n", this->data);

        //don't forget to clean up the memory
        mpf_clear(tempFloat);
        mpf_clear(tempScaling);
        mpf_clear(zeroPointFive);
    }
    
    void BigIntegerGmp::Initialize (BigIntegerBase<BigIntegerGmp> &input, const double value, const unsigned int numberOfDigits, const bool truncate) {
        mpz_init(input.data);

        mpf_set_default_prec(1024);//1024 is the default value and it should be more than enough

        //auxiliary big float used for applying scaling and rounding before exporting it to input.data
        mpf_t tempFloat;
        //we can't multiply mpf_t with mpz_t, so we need a temporary mpf_t for the scaling
        mpf_t tempScaling;
        //contains the value 0.5, used for the rounding procedure
        mpf_t zeroPointFive;

        //set the value
        mpf_init_set_d(tempFloat, value);
        
        //gmp_printf ("Value: %.*Ff\r\n", 30, tempFloat);

        //set the scaling
        if (numberOfDigits > 0) {
            mpf_init_set_si(tempScaling, 10);
            mpf_pow_ui(tempScaling, tempScaling, numberOfDigits);
        }
        else {
            mpf_init_set_si(tempScaling, 1);
        }

        //set 0.5
        mpf_init_set_d(zeroPointFive, 0.5);

        //apply the scaling
        mpf_mul(tempFloat, tempFloat, tempScaling);

        if (truncate) {
            //discard decimals
            mpf_trunc(tempFloat, tempFloat);
        }
        else {
            //round the value to the nearest (positive or negative) integer
            //input < 0.0 ? ceil(input - 0.5) : floor(input + 0.5));
            if (-1 == mpf_sgn(tempFloat)) {
                mpf_sub(tempFloat, tempFloat, zeroPointFive);
                mpf_ceil(tempFloat, tempFloat);
            }
            else {
                mpf_add(tempFloat, tempFloat, zeroPointFive);
                mpf_floor(tempFloat, tempFloat);
            }
        }

        //gmp_printf ("Value: %.*Ff\r\n", 30, tempFloat);

        //finally, transfer the value to our internal data
        mpz_set_f(input.data, tempFloat);
        
        //gmp_printf ("%Zd\r\n", this->data);

        //don't forget to clean up the memory
        mpf_clear(tempFloat);
        mpf_clear(tempScaling);
        mpf_clear(zeroPointFive);
    }
    
    void BigIntegerGmp::Initialize (BigIntegerBase<BigIntegerGmp> &input, const std::string &value, const int base) {
        if (0 != mpz_init_set_str(input.data, value.c_str(), base)) {
            throw std::runtime_error("The input string is not a valid number in the specified base.");
        }
    }

    void BigIntegerGmp::Destroy (BigIntegerBase<BigIntegerGmp> &input) {
        mpz_clear(input.data);
    }

    void BigIntegerGmp::Set (BigIntegerBase<BigIntegerGmp> &input, const BigIntegerBase<BigIntegerGmp> &value) {
        mpz_set(input.data, value.data);
    }
    
    void BigIntegerGmp::Set (BigIntegerBase<BigIntegerGmp> &input, const long value) {
        mpz_set_si(input.data, value);
    }
    
    void BigIntegerGmp::Set (BigIntegerBase<BigIntegerGmp> &input, const unsigned long value) {
        mpz_set_ui(input.data, value);
    }

    void BigIntegerGmp::InvertSign (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input) {
        mpz_neg(output.data, input.data);
    }

    void BigIntegerGmp::Add (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_add(output.data, lhs.data, rhs.data);
    }
    
    void BigIntegerGmp::Add (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const long rhs) {
        if (rhs < 0) {
            mpz_sub_ui(output.data, lhs.data, -rhs);
        }
        else {
            mpz_add_ui(output.data, lhs.data, rhs);
        }
    }
    
    void BigIntegerGmp::Add (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const unsigned long rhs) {
        mpz_add_ui(output.data, lhs.data, rhs);
    }

    void BigIntegerGmp::Subtract (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_sub(output.data, lhs.data, rhs.data);
    }
    
    void BigIntegerGmp::Subtract (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const long rhs) {
        if (rhs < 0) {
            mpz_add_ui(output.data, lhs.data, -rhs);
        }
        else {
            mpz_sub_ui(output.data, lhs.data, rhs);
        }
    }
    
    void BigIntegerGmp::Subtract (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const unsigned long rhs) {
        mpz_sub_ui(output.data, lhs.data, rhs);
    }

    void BigIntegerGmp::Multiply (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_mul(output.data, lhs.data, rhs.data);
    }
    
    void BigIntegerGmp::Multiply (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const long rhs) {
        mpz_mul_si(output.data, lhs.data, rhs);
    }
    
    void BigIntegerGmp::Multiply (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const unsigned long rhs) {
        mpz_mul_ui(output.data, lhs.data, rhs);
    }

    void BigIntegerGmp::Divide (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_tdiv_q(output.data, lhs.data, rhs.data);
    }
    
    void BigIntegerGmp::Divide (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const long rhs) {
        if (rhs < 0) {
            mpz_tdiv_q_ui(output.data, lhs.data, -rhs);
            mpz_neg(output.data, output.data);
        }
        else {
            mpz_tdiv_q_ui(output.data, lhs.data, rhs);
        }
    }
    
    void BigIntegerGmp::Divide (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const unsigned long rhs) {
        mpz_tdiv_q_ui(output.data, lhs.data, rhs);
    }

    void BigIntegerGmp::Modulo (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_mod(output.data, lhs.data, rhs.data);
    }
    
    void BigIntegerGmp::Modulo (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const long rhs) {
        if (rhs < 0) {
            mpz_mod_ui(output.data, lhs.data, -rhs);
            mpz_neg(output.data, output.data);
        }
        else {
            mpz_mod_ui(output.data, lhs.data, rhs);
        }
    }
    
    void BigIntegerGmp::Modulo (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const unsigned long rhs) {
        mpz_mod_ui(output.data, lhs.data, rhs);
    }

    void BigIntegerGmp::RightShift (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const unsigned long numberOfBits) {
        mpz_tdiv_q_2exp(output.data, input.data, numberOfBits);
    }
    
    void BigIntegerGmp::LeftShift (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const unsigned long numberOfBits) {
        mpz_mul_2exp(output.data, input.data, numberOfBits);
    }

    int BigIntegerGmp::Compare (const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        return mpz_cmp(lhs.data, rhs.data);
    }
    
    int BigIntegerGmp::Compare (const BigIntegerBase<BigIntegerGmp> &lhs, const long rhs) {
        return mpz_cmp_si(lhs.data, rhs);
    }
    
    int BigIntegerGmp::Compare (const BigIntegerBase<BigIntegerGmp> &lhs, const unsigned long rhs) {
        return mpz_cmp_ui(lhs.data, rhs);
    }

    void BigIntegerGmp::InvertBits (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input) {
        mpz_com(output.data, input.data);
    }

    void BigIntegerGmp::BitwiseAnd (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_and(output.data, lhs.data, rhs.data);
    }

    void BigIntegerGmp::BitwiseOr (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_ior(output.data, lhs.data, rhs.data);
    }

    void BigIntegerGmp::BitwiseXor (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_xor(output.data, lhs.data, rhs.data);
    }

    void BigIntegerGmp::GetNextPrime (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input) {
        mpz_nextprime(output.data, input.data);
    }

    bool BigIntegerGmp::IsPrime (const BigIntegerBase<BigIntegerGmp> &input) {
        if (0 != mpz_probab_prime_p(input.data, MILLER_RABIN_PRIMALITY_TEST_COUNT)) {
            return true;
        }
        
        return false;
    }

    void BigIntegerGmp::SetBit (BigIntegerBase<BigIntegerGmp> &input, const size_t index) {
        mpz_setbit(input.data, index);
    }

    int BigIntegerGmp::GetBit (const BigIntegerBase<BigIntegerGmp> &input, const size_t index) {
        return mpz_tstbit(input.data, index);
    }

    size_t BigIntegerGmp::GetSize (const BigIntegerBase<BigIntegerGmp> &input, const unsigned int base) {
        return mpz_sizeinbase(input.data, base);
    }

    void BigIntegerGmp::Abs (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input) {
        mpz_abs(output.data, input.data);
    }

    void BigIntegerGmp::Pow (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const BigIntegerBase<BigIntegerGmp> &power) {
        mpz_pow_ui(output.data, input.data, power.ToUnsignedLong());
    }
    
    void BigIntegerGmp::Pow (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const long power) {
        if (power < 0) {
            mpz_set_si(output.data, 0);
        }
        else {
            mpz_pow_ui(output.data, input.data, power);
        }
    }
    
    void BigIntegerGmp::Pow (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const unsigned long power) {
        mpz_pow_ui(output.data, input.data, power);
    }

    void BigIntegerGmp::PowModN (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const BigIntegerBase<BigIntegerGmp> &power, const BigIntegerBase<BigIntegerGmp> &n) {
        mpz_powm(output.data, input.data, power.data, n.data);
    }
    
    void BigIntegerGmp::PowModN (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const long power, const BigIntegerBase<BigIntegerGmp> &n) {
        if (power < 0) {
            BigIntegerGmp::PowModN (output, input, BigIntegerBase<BigIntegerGmp>(power), n);
        }
        else {
            mpz_powm_ui(output.data, input.data, power, n.data);
        }
    }
    
    void BigIntegerGmp::PowModN (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const unsigned long power, const BigIntegerBase<BigIntegerGmp> &n) {
        mpz_powm_ui(output.data, input.data, power, n.data);
    }

    void BigIntegerGmp::InvertModN (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &input, const BigIntegerBase<BigIntegerGmp> &n) {
        if (0 == mpz_invert(output.data, input.data, n.data)) {
            throw std::runtime_error("Failed to compute inverse modulo n.");
        }
    }

    void BigIntegerGmp::Swap (BigIntegerBase<BigIntegerGmp> &lhs, BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_swap(lhs.data, rhs.data);
    }

    void BigIntegerGmp::Gcd (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_gcd(output.data, lhs.data, rhs.data);
    }
    
    void BigIntegerGmp::Lcm (BigIntegerBase<BigIntegerGmp> &output, const BigIntegerBase<BigIntegerGmp> &lhs, const BigIntegerBase<BigIntegerGmp> &rhs) {
        mpz_lcm(output.data, lhs.data, rhs.data);
    }

    std::string BigIntegerGmp::ToString (const BigIntegerBase<BigIntegerGmp> &input, const unsigned int base) {
        //get a pointer to GMP's internal memory deallocator function
        void (*deallocator)(void *, size_t);
        mp_get_memory_functions(NULL, NULL, &deallocator);

        //get the string representation of input
        char *data = mpz_get_str(NULL, base, input.data);

        std::string output(data);

        //deallocate data, including the terminator character
        //calling std::free on the char * returned by mpz_get_str is dangerous, because it is initialized internally by GMP
        (*deallocator)((void *)data, std::char_traits<char>::length(data) + 1);

        return output;
    }

    unsigned long BigIntegerGmp::ToUnsignedLong (const BigIntegerBase<BigIntegerGmp> &input) {
        //if (0 == mpz_fits_ulong_p(input.data))
        //{
        //  throw std::runtime_error("The integer does not fit in an unsigned long.");
        //}

        return mpz_get_ui(input.data);
    }

}//namespace Core
}//namespace SeComLib