Swiftdiff options
| author | Remko Tronçon <git@el-tramo.be> | 2010-05-06 18:00:41 (GMT) |
|---|---|---|
| committer | Remko Tronçon <git@el-tramo.be> | 2010-05-06 18:00:41 (GMT) |
| commit | 4c58e9a2d266c23a2060edd08081bf86ebd1862c (patch) | |
| tree | 0030a4f3360c9da905165db1feed18997481fee5 | |
| parent | c2cf7f0e59c7880a9ce979d8a45d97442c705110 (diff) | |
| download | swift-contrib-4c58e9a2d266c23a2060edd08081bf86ebd1862c.zip swift-contrib-4c58e9a2d266c23a2060edd08081bf86ebd1862c.tar.bz2 | |
Use UUIDs as nonce when authenticating with SCRAM-SHA-1.
24 files changed, 3618 insertions, 2 deletions
diff --git a/3rdParty/Boost/src/boost/random/detail/config.hpp b/3rdParty/Boost/src/boost/random/detail/config.hpp new file mode 100644 index 0000000..d6bc0cc --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/config.hpp @@ -0,0 +1,18 @@ +/* boost random/detail/config.hpp header file + * + * Copyright Steven Watanabe 2009 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: config.hpp 52492 2009-04-19 14:55:57Z steven_watanabe $ + */ + +#include <boost/config.hpp> + +#if (defined(BOOST_NO_OPERATORS_IN_NAMESPACE) || defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS)) \ + && !defined(BOOST_MSVC) + #define BOOST_RANDOM_NO_STREAM_OPERATORS +#endif diff --git a/3rdParty/Boost/src/boost/random/detail/const_mod.hpp b/3rdParty/Boost/src/boost/random/detail/const_mod.hpp new file mode 100644 index 0000000..e0a8839 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/const_mod.hpp @@ -0,0 +1,363 @@ +/* boost random/detail/const_mod.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: const_mod.hpp 58649 2010-01-02 21:23:17Z steven_watanabe $ + * + * Revision history + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_CONST_MOD_HPP +#define BOOST_RANDOM_CONST_MOD_HPP + +#include <cassert> +#include <boost/static_assert.hpp> +#include <boost/cstdint.hpp> +#include <boost/integer_traits.hpp> +#include <boost/detail/workaround.hpp> + +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { +namespace random { + +/* + * Some random number generators require modular arithmetic. Put + * everything we need here. + * IntType must be an integral type. + */ + +namespace detail { + + template<bool is_signed> + struct do_add + { }; + + template<> + struct do_add<true> + { + template<class IntType> + static IntType add(IntType m, IntType x, IntType c) + { + if (x < m - c) + return x + c; + else + return x - (m-c); + } + }; + + template<> + struct do_add<false> + { + template<class IntType> + static IntType add(IntType, IntType, IntType) + { + // difficult + assert(!"const_mod::add with c too large"); + return 0; + } + }; +} // namespace detail + +#if !(defined(__BORLANDC__) && (__BORLANDC__ == 0x560)) + +template<class IntType, IntType m> +class const_mod +{ +public: + static IntType add(IntType x, IntType c) + { + if(c == 0) + return x; + else if(c <= traits::const_max - m) // i.e. m+c < max + return add_small(x, c); + else + return detail::do_add<traits::is_signed>::add(m, x, c); + } + + static IntType mult(IntType a, IntType x) + { + if(a == 1) + return x; + else if(m <= traits::const_max/a) // i.e. a*m <= max + return mult_small(a, x); + else if(traits::is_signed && (m%a < m/a)) + return mult_schrage(a, x); + else { + // difficult + assert(!"const_mod::mult with a too large"); + return 0; + } + } + + static IntType mult_add(IntType a, IntType x, IntType c) + { + if(m <= (traits::const_max-c)/a) // i.e. a*m+c <= max + return (a*x+c) % m; + else + return add(mult(a, x), c); + } + + static IntType invert(IntType x) + { return x == 0 ? 0 : invert_euclidian(x); } + +private: + typedef integer_traits<IntType> traits; + + const_mod(); // don't instantiate + + static IntType add_small(IntType x, IntType c) + { + x += c; + if(x >= m) + x -= m; + return x; + } + + static IntType mult_small(IntType a, IntType x) + { + return a*x % m; + } + + static IntType mult_schrage(IntType a, IntType value) + { + const IntType q = m / a; + const IntType r = m % a; + + assert(r < q); // check that overflow cannot happen + + value = a*(value%q) - r*(value/q); + // An optimizer bug in the SGI MIPSpro 7.3.1.x compiler requires this + // convoluted formulation of the loop (Synge Todo) + for(;;) { + if (value > 0) + break; + value += m; + } + return value; + } + + // invert c in the finite field (mod m) (m must be prime) + static IntType invert_euclidian(IntType c) + { + // we are interested in the gcd factor for c, because this is our inverse + BOOST_STATIC_ASSERT(m > 0); +#if BOOST_WORKAROUND(__MWERKS__, BOOST_TESTED_AT(0x3003)) + assert(boost::integer_traits<IntType>::is_signed); +#elif !defined(BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS) + BOOST_STATIC_ASSERT(boost::integer_traits<IntType>::is_signed); +#endif + assert(c > 0); + IntType l1 = 0; + IntType l2 = 1; + IntType n = c; + IntType p = m; + for(;;) { + IntType q = p / n; + l1 -= q * l2; // this requires a signed IntType! + p -= q * n; + if(p == 0) + return (l2 < 1 ? l2 + m : l2); + IntType q2 = n / p; + l2 -= q2 * l1; + n -= q2 * p; + if(n == 0) + return (l1 < 1 ? l1 + m : l1); + } + } +}; + +// The modulus is exactly the word size: rely on machine overflow handling. +// Due to a GCC bug, we cannot partially specialize in the presence of +// template value parameters. +template<> +class const_mod<unsigned int, 0> +{ + typedef unsigned int IntType; +public: + static IntType add(IntType x, IntType c) { return x+c; } + static IntType mult(IntType a, IntType x) { return a*x; } + static IntType mult_add(IntType a, IntType x, IntType c) { return a*x+c; } + + // m is not prime, thus invert is not useful +private: // don't instantiate + const_mod(); +}; + +template<> +class const_mod<unsigned long, 0> +{ + typedef unsigned long IntType; +public: + static IntType add(IntType x, IntType c) { return x+c; } + static IntType mult(IntType a, IntType x) { return a*x; } + static IntType mult_add(IntType a, IntType x, IntType c) { return a*x+c; } + + // m is not prime, thus invert is not useful +private: // don't instantiate + const_mod(); +}; + +// the modulus is some power of 2: rely partly on machine overflow handling +// we only specialize for rand48 at the moment +#ifndef BOOST_NO_INT64_T +template<> +class const_mod<uint64_t, uint64_t(1) << 48> +{ + typedef uint64_t IntType; +public: + static IntType add(IntType x, IntType c) { return c == 0 ? x : mod(x+c); } + static IntType mult(IntType a, IntType x) { return mod(a*x); } + static IntType mult_add(IntType a, IntType x, IntType c) + { return mod(a*x+c); } + static IntType mod(IntType x) { return x &= ((uint64_t(1) << 48)-1); } + + // m is not prime, thus invert is not useful +private: // don't instantiate + const_mod(); +}; +#endif /* !BOOST_NO_INT64_T */ + +#else + +// +// for some reason Borland C++ Builder 6 has problems with +// the full specialisations of const_mod, define a generic version +// instead, the compiler will optimise away the const-if statements: +// + +template<class IntType, IntType m> +class const_mod +{ +public: + static IntType add(IntType x, IntType c) + { + if(0 == m) + { + return x+c; + } + else + { + if(c == 0) + return x; + else if(c <= traits::const_max - m) // i.e. m+c < max + return add_small(x, c); + else + return detail::do_add<traits::is_signed>::add(m, x, c); + } + } + + static IntType mult(IntType a, IntType x) + { + if(x == 0) + { + return a*x; + } + else + { + if(a == 1) + return x; + else if(m <= traits::const_max/a) // i.e. a*m <= max + return mult_small(a, x); + else if(traits::is_signed && (m%a < m/a)) + return mult_schrage(a, x); + else { + // difficult + assert(!"const_mod::mult with a too large"); + return 0; + } + } + } + + static IntType mult_add(IntType a, IntType x, IntType c) + { + if(m == 0) + { + return a*x+c; + } + else + { + if(m <= (traits::const_max-c)/a) // i.e. a*m+c <= max + return (a*x+c) % m; + else + return add(mult(a, x), c); + } + } + + static IntType invert(IntType x) + { return x == 0 ? 0 : invert_euclidian(x); } + +private: + typedef integer_traits<IntType> traits; + + const_mod(); // don't instantiate + + static IntType add_small(IntType x, IntType c) + { + x += c; + if(x >= m) + x -= m; + return x; + } + + static IntType mult_small(IntType a, IntType x) + { + return a*x % m; + } + + static IntType mult_schrage(IntType a, IntType value) + { + const IntType q = m / a; + const IntType r = m % a; + + assert(r < q); // check that overflow cannot happen + + value = a*(value%q) - r*(value/q); + while(value <= 0) + value += m; + return value; + } + + // invert c in the finite field (mod m) (m must be prime) + static IntType invert_euclidian(IntType c) + { + // we are interested in the gcd factor for c, because this is our inverse + BOOST_STATIC_ASSERT(m > 0); +#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + BOOST_STATIC_ASSERT(boost::integer_traits<IntType>::is_signed); +#endif + assert(c > 0); + IntType l1 = 0; + IntType l2 = 1; + IntType n = c; + IntType p = m; + for(;;) { + IntType q = p / n; + l1 -= q * l2; // this requires a signed IntType! + p -= q * n; + if(p == 0) + return (l2 < 1 ? l2 + m : l2); + IntType q2 = n / p; + l2 -= q2 * l1; + n -= q2 * p; + if(n == 0) + return (l1 < 1 ? l1 + m : l1); + } + } +}; + + +#endif + +} // namespace random +} // namespace boost + +#include <boost/random/detail/enable_warnings.hpp> + +#endif // BOOST_RANDOM_CONST_MOD_HPP diff --git a/3rdParty/Boost/src/boost/random/detail/disable_warnings.hpp b/3rdParty/Boost/src/boost/random/detail/disable_warnings.hpp new file mode 100644 index 0000000..f3ade5e --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/disable_warnings.hpp @@ -0,0 +1,23 @@ +/* boost random/detail/disable_warnings.hpp header file + * + * Copyright Steven Watanabe 2009 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: disable_warnings.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + */ + +// No #include guard. This header is intended to be included multiple times. + +#include <boost/config.hpp> + +#ifdef BOOST_MSVC +#pragma warning(push) +#pragma warning(disable:4512) +#pragma warning(disable:4127) +#pragma warning(disable:4724) +#endif diff --git a/3rdParty/Boost/src/boost/random/detail/enable_warnings.hpp b/3rdParty/Boost/src/boost/random/detail/enable_warnings.hpp new file mode 100644 index 0000000..26184ea --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/enable_warnings.hpp @@ -0,0 +1,18 @@ +/* boost random/detail/enable_warnings.hpp header file + * + * Copyright Steven Watanabe 2009 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: enable_warnings.hpp 58649 2010-01-02 21:23:17Z steven_watanabe $ + * + */ + +// No #include guard. This header is intended to be included multiple times. + +#ifdef BOOST_MSVC +#pragma warning(pop) +#endif diff --git a/3rdParty/Boost/src/boost/random/detail/pass_through_engine.hpp b/3rdParty/Boost/src/boost/random/detail/pass_through_engine.hpp new file mode 100644 index 0000000..468427c --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/pass_through_engine.hpp @@ -0,0 +1,100 @@ +/* boost random/detail/uniform_int_float.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: pass_through_engine.hpp 58649 2010-01-02 21:23:17Z steven_watanabe $ + * + */ + +#ifndef BOOST_RANDOM_DETAIL_PASS_THROUGH_ENGINE_HPP +#define BOOST_RANDOM_DETAIL_PASS_THROUGH_ENGINE_HPP + +#include <boost/config.hpp> +#include <boost/random/detail/ptr_helper.hpp> +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { +namespace random { +namespace detail { + +template<class UniformRandomNumberGenerator> +class pass_through_engine +{ +private: + typedef ptr_helper<UniformRandomNumberGenerator> helper_type; + +public: + typedef typename helper_type::value_type base_type; + typedef typename base_type::result_type result_type; + + explicit pass_through_engine(UniformRandomNumberGenerator rng) + // make argument an rvalue to avoid matching Generator& constructor + : _rng(static_cast<typename helper_type::rvalue_type>(rng)) + { } + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (base().min)(); } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (base().max)(); } + base_type& base() { return helper_type::ref(_rng); } + const base_type& base() const { return helper_type::ref(_rng); } + + result_type operator()() { return base()(); } + +private: + UniformRandomNumberGenerator _rng; +}; + +#ifndef BOOST_NO_STD_LOCALE + +template<class UniformRandomNumberGenerator, class CharT, class Traits> +std::basic_ostream<CharT,Traits>& +operator<<( + std::basic_ostream<CharT,Traits>& os + , const pass_through_engine<UniformRandomNumberGenerator>& ud + ) +{ + return os << ud.base(); +} + +template<class UniformRandomNumberGenerator, class CharT, class Traits> +std::basic_istream<CharT,Traits>& +operator>>( + std::basic_istream<CharT,Traits>& is + , const pass_through_engine<UniformRandomNumberGenerator>& ud + ) +{ + return is >> ud.base(); +} + +#else // no new streams + +template<class UniformRandomNumberGenerator> +inline std::ostream& +operator<<(std::ostream& os, + const pass_through_engine<UniformRandomNumberGenerator>& ud) +{ + return os << ud.base(); +} + +template<class UniformRandomNumberGenerator> +inline std::istream& +operator>>(std::istream& is, + const pass_through_engine<UniformRandomNumberGenerator>& ud) +{ + return is >> ud.base(); +} + +#endif + +} // namespace detail +} // namespace random +} // namespace boost + +#include <boost/random/detail/enable_warnings.hpp> + +#endif // BOOST_RANDOM_DETAIL_PASS_THROUGH_ENGINE_HPP + diff --git a/3rdParty/Boost/src/boost/random/detail/ptr_helper.hpp b/3rdParty/Boost/src/boost/random/detail/ptr_helper.hpp new file mode 100644 index 0000000..3f3fbdd --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/ptr_helper.hpp @@ -0,0 +1,94 @@ +/* boost random/detail/ptr_helper.hpp header file + * + * Copyright Jens Maurer 2002 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: ptr_helper.hpp 24096 2004-07-27 03:43:34Z dgregor $ + * + */ + +#ifndef BOOST_RANDOM_DETAIL_PTR_HELPER_HPP +#define BOOST_RANDOM_DETAIL_PTR_HELPER_HPP + +#include <boost/config.hpp> + + +namespace boost { +namespace random { +namespace detail { + +// type_traits could help here, but I don't want to depend on type_traits. +template<class T> +struct ptr_helper +{ + typedef T value_type; + typedef T& reference_type; + typedef const T& rvalue_type; + static reference_type ref(T& r) { return r; } + static const T& ref(const T& r) { return r; } +}; + +#ifndef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION +template<class T> +struct ptr_helper<T&> +{ + typedef T value_type; + typedef T& reference_type; + typedef T& rvalue_type; + static reference_type ref(T& r) { return r; } + static const T& ref(const T& r) { return r; } +}; + +template<class T> +struct ptr_helper<T*> +{ + typedef T value_type; + typedef T& reference_type; + typedef T* rvalue_type; + static reference_type ref(T * p) { return *p; } + static const T& ref(const T * p) { return *p; } +}; +#endif + +} // namespace detail +} // namespace random +} // namespace boost + +// +// BOOST_RANDOM_PTR_HELPER_SPEC -- +// +// Helper macro for broken compilers defines specializations of +// ptr_helper. +// +#ifdef BOOST_NO_TEMPLATE_PARTIAL_SPECIALIZATION +# define BOOST_RANDOM_PTR_HELPER_SPEC(T) \ +namespace boost { namespace random { namespace detail { \ +template<> \ +struct ptr_helper<T&> \ +{ \ + typedef T value_type; \ + typedef T& reference_type; \ + typedef T& rvalue_type; \ + static reference_type ref(T& r) { return r; } \ + static const T& ref(const T& r) { return r; } \ +}; \ + \ +template<> \ +struct ptr_helper<T*> \ +{ \ + typedef T value_type; \ + typedef T& reference_type; \ + typedef T* rvalue_type; \ + static reference_type ref(T * p) { return *p; } \ + static const T& ref(const T * p) { return *p; } \ +}; \ +}}} +#else +# define BOOST_RANDOM_PTR_HELPER_SPEC(T) +#endif + +#endif // BOOST_RANDOM_DETAIL_PTR_HELPER_HPP diff --git a/3rdParty/Boost/src/boost/random/detail/seed.hpp b/3rdParty/Boost/src/boost/random/detail/seed.hpp new file mode 100644 index 0000000..48cc17e --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/seed.hpp @@ -0,0 +1,89 @@ +/* boost random/detail/seed.hpp header file + * + * Copyright Steven Watanabe 2009 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: seed.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + */ + +#ifndef BOOST_RANDOM_DETAIL_SEED_HPP +#define BOOST_RANDOM_DETAIL_SEED_HPP + +#include <boost/config.hpp> + +// Sun seems to have trouble with the use of SFINAE for the +// templated constructor. So does Borland. +#if !defined(BOOST_NO_SFINAE) && !defined(__SUNPRO_CC) && !defined(__BORLANDC__) + +#include <boost/utility/enable_if.hpp> +#include <boost/type_traits/is_arithmetic.hpp> + +namespace boost { +namespace random { +namespace detail { + +template<class T> +struct disable_seed : boost::disable_if<boost::is_arithmetic<T> > {}; + +template<class Engine, class T> +struct disable_constructor : disable_seed<T> {}; + +template<class Engine> +struct disable_constructor<Engine, Engine> {}; + +#define BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(Self, Generator, gen) \ + template<class Generator> \ + explicit Self(Generator& gen, typename ::boost::random::detail::disable_constructor<Self, Generator>::type* = 0) + +#define BOOST_RANDOM_DETAIL_GENERATOR_SEED(Self, Generator, gen) \ + template<class Generator> \ + void seed(Generator& gen, typename ::boost::random::detail::disable_seed<Generator>::type* = 0) + +#define BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(Self, T, x) \ + explicit Self(const T& x) + +#define BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(Self, T, x) \ + void seed(const T& x) + +} +} +} + +#else + +#include <boost/type_traits/is_arithmetic.hpp> +#include <boost/mpl/bool.hpp> + +#define BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(Self, Generator, gen) \ + Self(Self& other) { *this = other; } \ + Self(const Self& other) { *this = other; } \ + template<class Generator> \ + explicit Self(Generator& gen) { \ + boost_random_constructor_impl(gen, ::boost::is_arithmetic<Generator>());\ + } \ + template<class Generator> \ + void boost_random_constructor_impl(Generator& gen, ::boost::mpl::false_) + +#define BOOST_RANDOM_DETAIL_GENERATOR_SEED(Self, Generator, gen) \ + template<class Generator> \ + void seed(Generator& gen) { \ + boost_random_seed_impl(gen, ::boost::is_arithmetic<Generator>());\ + }\ + template<class Generator>\ + void boost_random_seed_impl(Generator& gen, ::boost::mpl::false_) + +#define BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(Self, T, x) \ + explicit Self(const T& x) { boost_random_constructor_impl(x, ::boost::mpl::true_()); }\ + void boost_random_constructor_impl(const T& x, ::boost::mpl::true_) + +#define BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(Self, T, x) \ + void seed(const T& x) { boost_random_seed_impl(x, ::boost::mpl::true_()); }\ + void boost_random_seed_impl(const T& x, ::boost::mpl::true_) + +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/random/detail/signed_unsigned_tools.hpp b/3rdParty/Boost/src/boost/random/detail/signed_unsigned_tools.hpp new file mode 100644 index 0000000..3c81cf4 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/signed_unsigned_tools.hpp @@ -0,0 +1,89 @@ +/* boost random/detail/signed_unsigned_tools.hpp header file + * + * Copyright Jens Maurer 2006 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + */ + +#ifndef BOOST_RANDOM_DETAIL_SIGNED_UNSIGNED_TOOLS +#define BOOST_RANDOM_DETAIL_SIGNED_UNSIGNED_TOOLS + +#include <boost/limits.hpp> +#include <boost/config.hpp> +#include <boost/type_traits/make_unsigned.hpp> + +namespace boost { +namespace random { +namespace detail { + + +/* + * Compute x - y, we know that x >= y, return an unsigned value. + */ + +template<class T, bool sgn = std::numeric_limits<T>::is_signed> +struct subtract { }; + +template<class T> +struct subtract<T, /* signed */ false> +{ + typedef T result_type; + result_type operator()(T x, T y) { return x - y; } +}; + +template<class T> +struct subtract<T, /* signed */ true> +{ + typedef typename make_unsigned<T>::type result_type; + result_type operator()(T x, T y) + { + if (y >= 0) // because x >= y, it follows that x >= 0, too + return result_type(x) - result_type(y); + if (x >= 0) // y < 0 + // avoid the nasty two's complement case for y == min() + return result_type(x) + result_type(-(y+1)) + 1; + // both x and y are negative: no signed overflow + return result_type(x - y); + } +}; + +/* + * Compute x + y, x is unsigned, result fits in type of "y". + */ + +template<class T1, class T2, bool sgn = std::numeric_limits<T2>::is_signed> +struct add { }; + +template<class T1, class T2> +struct add<T1, T2, /* signed */ false> +{ + typedef T2 result_type; + result_type operator()(T1 x, T2 y) { return T2(x) + y; } +}; + +template<class T1, class T2> +struct add<T1, T2, /* signed */ true> +{ + typedef T2 result_type; + result_type operator()(T1 x, T2 y) + { + if (y >= 0) + return T2(x) + y; + // y < 0 + if (x >= T1(-(y+1))) // result >= 0 after subtraction + // avoid the nasty two's complement edge case for y == min() + return T2(x - T1(-(y+1)) - 1); + // abs(x) < abs(y), thus T2 able to represent x + return T2(x) + y; + } +}; + +} // namespace detail +} // namespace random +} // namespace boost + +#endif // BOOST_RANDOM_DETAIL_SIGNED_UNSIGNED_TOOLS + diff --git a/3rdParty/Boost/src/boost/random/detail/uniform_int_float.hpp b/3rdParty/Boost/src/boost/random/detail/uniform_int_float.hpp new file mode 100644 index 0000000..4607021 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/detail/uniform_int_float.hpp @@ -0,0 +1,85 @@ +/* boost random/detail/uniform_int_float.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: uniform_int_float.hpp 52492 2009-04-19 14:55:57Z steven_watanabe $ + * + */ + +#ifndef BOOST_RANDOM_DETAIL_UNIFORM_INT_FLOAT_HPP +#define BOOST_RANDOM_DETAIL_UNIFORM_INT_FLOAT_HPP + +#include <boost/config.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/uniform_01.hpp> + + +namespace boost { +namespace random { +namespace detail { + +template<class UniformRandomNumberGenerator, class IntType = unsigned long> +class uniform_int_float +{ +public: + typedef UniformRandomNumberGenerator base_type; + typedef IntType result_type; + + uniform_int_float(base_type rng, IntType min_arg = 0, IntType max_arg = 0xffffffff) + : _rng(rng), _min(min_arg), _max(max_arg) + { + init(); + } + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; } + base_type& base() { return _rng.base(); } + const base_type& base() const { return _rng.base(); } + + result_type operator()() + { + return static_cast<IntType>(_rng() * _range) + _min; + } + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_int_float& ud) + { + os << ud._min << " " << ud._max; + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, uniform_int_float& ud) + { + is >> std::ws >> ud._min >> std::ws >> ud._max; + ud.init(); + return is; + } +#endif + +private: + void init() + { + _range = static_cast<base_result>(_max-_min)+1; + } + + typedef typename base_type::result_type base_result; + uniform_01<base_type> _rng; + result_type _min, _max; + base_result _range; +}; + + +} // namespace detail +} // namespace random +} // namespace boost + +#endif // BOOST_RANDOM_DETAIL_UNIFORM_INT_FLOAT_HPP diff --git a/3rdParty/Boost/src/boost/random/linear_congruential.hpp b/3rdParty/Boost/src/boost/random/linear_congruential.hpp new file mode 100644 index 0000000..351b9c1 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/linear_congruential.hpp @@ -0,0 +1,403 @@ +/* boost random/linear_congruential.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: linear_congruential.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + * Revision history + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP +#define BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP + +#include <iostream> +#include <cassert> +#include <stdexcept> +#include <boost/config.hpp> +#include <boost/limits.hpp> +#include <boost/static_assert.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/detail/const_mod.hpp> +#include <boost/detail/workaround.hpp> + +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { +namespace random { + +/** + * Instantiations of class template linear_congruential model a + * \pseudo_random_number_generator. Linear congruential pseudo-random + * number generators are described in: + * + * "Mathematical methods in large-scale computing units", D. H. Lehmer, + * Proc. 2nd Symposium on Large-Scale Digital Calculating Machines, + * Harvard University Press, 1951, pp. 141-146 + * + * Let x(n) denote the sequence of numbers returned by some pseudo-random + * number generator. Then for the linear congruential generator, + * x(n+1) := (a * x(n) + c) mod m. Parameters for the generator are + * x(0), a, c, m. The template parameter IntType shall denote an integral + * type. It must be large enough to hold values a, c, and m. The template + * parameters a and c must be smaller than m. + * + * Note: The quality of the generator crucially depends on the choice of + * the parameters. User code should use one of the sensibly parameterized + * generators such as minstd_rand instead. + */ +template<class IntType, IntType a, IntType c, IntType m, IntType val> +class linear_congruential +{ +public: + typedef IntType result_type; +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION + static const bool has_fixed_range = true; + static const result_type min_value = ( c == 0 ? 1 : 0 ); + static const result_type max_value = m-1; +#else + BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); +#endif + BOOST_STATIC_CONSTANT(IntType, multiplier = a); + BOOST_STATIC_CONSTANT(IntType, increment = c); + BOOST_STATIC_CONSTANT(IntType, modulus = m); + + // MSVC 6 and possibly others crash when encountering complicated integral + // constant expressions. Avoid the check for now. + // BOOST_STATIC_ASSERT(m == 0 || a < m); + // BOOST_STATIC_ASSERT(m == 0 || c < m); + + /** + * Constructs a linear_congruential generator, seeding it with @c x0. + */ + explicit linear_congruential(IntType x0 = 1) + { + seed(x0); + + // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope +#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer); +#endif + } + + /** + * Constructs a @c linear_congruential generator and seeds it + * with values taken from the itrator range [first, last) + * and adjusts first to point to the element after the last one + * used. If there are not enough elements, throws @c std::invalid_argument. + * + * first and last must be input iterators. + */ + template<class It> + linear_congruential(It& first, It last) + { + seed(first, last); + } + + // compiler-generated copy constructor and assignment operator are fine + + /** + * If c mod m is zero and x0 mod m is zero, changes the current value of + * the generator to 1. Otherwise, changes it to x0 mod m. If c is zero, + * distinct seeds in the range [1,m) will leave the generator in distinct + * states. If c is not zero, the range is [0,m). + */ + void seed(IntType x0 = 1) + { + // wrap _x if it doesn't fit in the destination + if(modulus == 0) { + _x = x0; + } else { + _x = x0 % modulus; + } + // handle negative seeds + if(_x <= 0 && _x != 0) { + _x += modulus; + } + // adjust to the correct range + if(increment == 0 && _x == 0) { + _x = 1; + } + assert(_x >= (min)()); + assert(_x <= (max)()); + } + + /** + * seeds a @c linear_congruential generator with values taken + * from the itrator range [first, last) and adjusts @c first to + * point to the element after the last one used. If there are + * not enough elements, throws @c std::invalid_argument. + * + * @c first and @c last must be input iterators. + */ + template<class It> + void seed(It& first, It last) + { + if(first == last) + throw std::invalid_argument("linear_congruential::seed"); + seed(*first++); + } + + /** + * Returns the smallest value that the @c linear_congruential generator + * can produce. + */ + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return c == 0 ? 1 : 0; } + /** + * Returns the largest value that the @c linear_congruential generator + * can produce. + */ + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return modulus-1; } + + /** Returns the next value of the @c linear_congruential generator. */ + IntType operator()() + { + _x = const_mod<IntType, m>::mult_add(a, _x, c); + return _x; + } + + static bool validation(IntType x) { return val == x; } + +#ifdef BOOST_NO_OPERATORS_IN_NAMESPACE + + // Use a member function; Streamable concept not supported. + bool operator==(const linear_congruential& rhs) const + { return _x == rhs._x; } + bool operator!=(const linear_congruential& rhs) const + { return !(*this == rhs); } + +#else + friend bool operator==(const linear_congruential& x, + const linear_congruential& y) + { return x._x == y._x; } + friend bool operator!=(const linear_congruential& x, + const linear_congruential& y) + { return !(x == y); } + +#if !defined(BOOST_RANDOM_NO_STREAM_OPERATORS) && !BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, + const linear_congruential& lcg) + { + return os << lcg._x; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, + linear_congruential& lcg) + { + return is >> lcg._x; + } + +private: +#endif +#endif + + IntType _x; +}; + +// probably needs the "no native streams" caveat for STLPort +#if !defined(__SGI_STL_PORT) && BOOST_WORKAROUND(__GNUC__, == 2) +template<class IntType, IntType a, IntType c, IntType m, IntType val> +std::ostream& +operator<<(std::ostream& os, + const linear_congruential<IntType,a,c,m,val>& lcg) +{ + return os << lcg._x; +} + +template<class IntType, IntType a, IntType c, IntType m, IntType val> +std::istream& +operator>>(std::istream& is, + linear_congruential<IntType,a,c,m,val>& lcg) +{ + return is >> lcg._x; +} +#elif defined(BOOST_RANDOM_NO_STREAM_OPERATORS) || BOOST_WORKAROUND(__BORLANDC__, BOOST_TESTED_AT(0x551)) +template<class CharT, class Traits, class IntType, IntType a, IntType c, IntType m, IntType val> +std::basic_ostream<CharT,Traits>& +operator<<(std::basic_ostream<CharT,Traits>& os, + const linear_congruential<IntType,a,c,m,val>& lcg) +{ + return os << lcg._x; +} + +template<class CharT, class Traits, class IntType, IntType a, IntType c, IntType m, IntType val> +std::basic_istream<CharT,Traits>& +operator>>(std::basic_istream<CharT,Traits>& is, + linear_congruential<IntType,a,c,m,val>& lcg) +{ + return is >> lcg._x; +} +#endif + +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION +// A definition is required even for integral static constants +template<class IntType, IntType a, IntType c, IntType m, IntType val> +const bool linear_congruential<IntType, a, c, m, val>::has_fixed_range; +template<class IntType, IntType a, IntType c, IntType m, IntType val> +const typename linear_congruential<IntType, a, c, m, val>::result_type linear_congruential<IntType, a, c, m, val>::min_value; +template<class IntType, IntType a, IntType c, IntType m, IntType val> +const typename linear_congruential<IntType, a, c, m, val>::result_type linear_congruential<IntType, a, c, m, val>::max_value; +template<class IntType, IntType a, IntType c, IntType m, IntType val> +const IntType linear_congruential<IntType,a,c,m,val>::modulus; +#endif + +} // namespace random + +// validation values from the publications +/** + * The specialization \minstd_rand0 was originally suggested in + * + * @blockquote + * A pseudo-random number generator for the System/360, P.A. Lewis, + * A.S. Goodman, J.M. Miller, IBM Systems Journal, Vol. 8, No. 2, + * 1969, pp. 136-146 + * @endblockquote + * + * It is examined more closely together with \minstd_rand in + * + * @blockquote + * "Random Number Generators: Good ones are hard to find", + * Stephen K. Park and Keith W. Miller, Communications of + * the ACM, Vol. 31, No. 10, October 1988, pp. 1192-1201 + * @endblockquote + */ +typedef random::linear_congruential<int32_t, 16807, 0, 2147483647, + 1043618065> minstd_rand0; + +/** The specialization \minstd_rand was suggested in + * + * @blockquote + * "Random Number Generators: Good ones are hard to find", + * Stephen K. Park and Keith W. Miller, Communications of + * the ACM, Vol. 31, No. 10, October 1988, pp. 1192-1201 + * @endblockquote + */ +typedef random::linear_congruential<int32_t, 48271, 0, 2147483647, + 399268537> minstd_rand; + + +#if !defined(BOOST_NO_INT64_T) && !defined(BOOST_NO_INTEGRAL_INT64_T) +/** Class @c rand48 models a \pseudo_random_number_generator. It uses + * the linear congruential algorithm with the parameters a = 0x5DEECE66D, + * c = 0xB, m = 2**48. It delivers identical results to the @c lrand48() + * function available on some systems (assuming lcong48 has not been called). + * + * It is only available on systems where @c uint64_t is provided as an + * integral type, so that for example static in-class constants and/or + * enum definitions with large @c uint64_t numbers work. + */ +class rand48 +{ +public: + typedef int32_t result_type; +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION + static const bool has_fixed_range = true; + static const int32_t min_value = 0; + static const int32_t max_value = integer_traits<int32_t>::const_max; +#else + enum { has_fixed_range = false }; +#endif + /** + * Returns the smallest value that the generator can produce + */ + int32_t min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; } + /** + * Returns the largest value that the generator can produce + */ + int32_t max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return std::numeric_limits<int32_t>::max BOOST_PREVENT_MACRO_SUBSTITUTION (); } + +#ifdef BOOST_RANDOM_DOXYGEN + /** + * If T is an integral type smaller than int46_t, constructs + * a \rand48 generator with x(0) := (x0 << 16) | 0x330e. Otherwise + * constructs a \rand48 generator with x(0) = x0. + */ + template<class T> explicit rand48(T x0 = 1); +#else + rand48() : lcf(cnv(static_cast<int32_t>(1))) {} + template<class T> explicit rand48(T x0) : lcf(cnv(x0)) { } +#endif + template<class It> rand48(It& first, It last) : lcf(first, last) { } + + // compiler-generated copy ctor and assignment operator are fine + +#ifdef BOOST_RANDOM_DOXYGEN + /** + * If T is an integral type smaller than int46_t, changes + * the current value x(n) of the generator to (x0 << 16) | 0x330e. + * Otherwise changes the current value x(n) to x0. + */ + template<class T> void seed(T x0 = 1); +#else + void seed() { seed(static_cast<int32_t>(1)); } + template<class T> void seed(T x0) { lcf.seed(cnv(x0)); } +#endif + template<class It> void seed(It& first, It last) { lcf.seed(first,last); } + + /** + * Returns the next value of the generator. + */ + int32_t operator()() { return static_cast<int32_t>(lcf() >> 17); } + // by experiment from lrand48() + static bool validation(int32_t x) { return x == 1993516219; } + +#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT,class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const rand48& r) + { os << r.lcf; return os; } + + template<class CharT,class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, rand48& r) + { is >> r.lcf; return is; } +#endif + + friend bool operator==(const rand48& x, const rand48& y) + { return x.lcf == y.lcf; } + friend bool operator!=(const rand48& x, const rand48& y) + { return !(x == y); } +#else + // Use a member function; Streamable concept not supported. + bool operator==(const rand48& rhs) const + { return lcf == rhs.lcf; } + bool operator!=(const rand48& rhs) const + { return !(*this == rhs); } +#endif +private: + /// \cond hide_private_members + random::linear_congruential<uint64_t, + uint64_t(0xDEECE66DUL) | (uint64_t(0x5) << 32), // xxxxULL is not portable + 0xB, uint64_t(1)<<48, /* unknown */ 0> lcf; + template<class T> + static uint64_t cnv(T x) + { + if(sizeof(T) < sizeof(uint64_t)) { + return (static_cast<uint64_t>(x) << 16) | 0x330e; + } else { + return(static_cast<uint64_t>(x)); + } + } + static uint64_t cnv(float x) { return(static_cast<uint64_t>(x)); } + static uint64_t cnv(double x) { return(static_cast<uint64_t>(x)); } + static uint64_t cnv(long double x) { return(static_cast<uint64_t>(x)); } + /// \endcond +}; +#endif /* !BOOST_NO_INT64_T && !BOOST_NO_INTEGRAL_INT64_T */ + +} // namespace boost + +#include <boost/random/detail/enable_warnings.hpp> + +#endif // BOOST_RANDOM_LINEAR_CONGRUENTIAL_HPP diff --git a/3rdParty/Boost/src/boost/random/mersenne_twister.hpp b/3rdParty/Boost/src/boost/random/mersenne_twister.hpp new file mode 100644 index 0000000..fa80aa6 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/mersenne_twister.hpp @@ -0,0 +1,367 @@ +/* boost random/mersenne_twister.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: mersenne_twister.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + * Revision history + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_MERSENNE_TWISTER_HPP +#define BOOST_RANDOM_MERSENNE_TWISTER_HPP + +#include <iostream> +#include <algorithm> // std::copy +#include <stdexcept> +#include <boost/config.hpp> +#include <boost/limits.hpp> +#include <boost/static_assert.hpp> +#include <boost/integer_traits.hpp> +#include <boost/cstdint.hpp> +#include <boost/random/linear_congruential.hpp> +#include <boost/detail/workaround.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/detail/ptr_helper.hpp> +#include <boost/random/detail/seed.hpp> + +namespace boost { +namespace random { + +/** + * Instantiations of class template mersenne_twister model a + * \pseudo_random_number_generator. It uses the algorithm described in + * + * @blockquote + * "Mersenne Twister: A 623-dimensionally equidistributed uniform + * pseudo-random number generator", Makoto Matsumoto and Takuji Nishimura, + * ACM Transactions on Modeling and Computer Simulation: Special Issue on + * Uniform Random Number Generation, Vol. 8, No. 1, January 1998, pp. 3-30. + * @endblockquote + * + * @xmlnote + * The boost variant has been implemented from scratch and does not + * derive from or use mt19937.c provided on the above WWW site. However, it + * was verified that both produce identical output. + * @endxmlnote + * + * The seeding from an integer was changed in April 2005 to address a + * <a href="http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html">weakness</a>. + * + * The quality of the generator crucially depends on the choice of the + * parameters. User code should employ one of the sensibly parameterized + * generators such as \mt19937 instead. + * + * The generator requires considerable amounts of memory for the storage of + * its state array. For example, \mt11213b requires about 1408 bytes and + * \mt19937 requires about 2496 bytes. + */ +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +class mersenne_twister +{ +public: + typedef UIntType result_type; + BOOST_STATIC_CONSTANT(int, word_size = w); + BOOST_STATIC_CONSTANT(int, state_size = n); + BOOST_STATIC_CONSTANT(int, shift_size = m); + BOOST_STATIC_CONSTANT(int, mask_bits = r); + BOOST_STATIC_CONSTANT(UIntType, parameter_a = a); + BOOST_STATIC_CONSTANT(int, output_u = u); + BOOST_STATIC_CONSTANT(int, output_s = s); + BOOST_STATIC_CONSTANT(UIntType, output_b = b); + BOOST_STATIC_CONSTANT(int, output_t = t); + BOOST_STATIC_CONSTANT(UIntType, output_c = c); + BOOST_STATIC_CONSTANT(int, output_l = l); + + BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); + + /** + * Constructs a @c mersenne_twister and calls @c seed(). + */ + mersenne_twister() { seed(); } + + /** + * Constructs a @c mersenne_twister and calls @c seed(value). + */ + BOOST_RANDOM_DETAIL_ARITHMETIC_CONSTRUCTOR(mersenne_twister, UIntType, value) + { seed(value); } + template<class It> mersenne_twister(It& first, It last) { seed(first,last); } + + /** + * Constructs a mersenne_twister and calls @c seed(gen). + * + * @xmlnote + * The copy constructor will always be preferred over + * the templated constructor. + * @endxmlnote + */ + BOOST_RANDOM_DETAIL_GENERATOR_CONSTRUCTOR(mersenne_twister, Generator, gen) + { seed(gen); } + + // compiler-generated copy ctor and assignment operator are fine + + /** Calls @c seed(result_type(5489)). */ + void seed() { seed(UIntType(5489)); } + + /** + * Sets the state x(0) to v mod 2w. Then, iteratively, + * sets x(i) to (i + 1812433253 * (x(i-1) xor (x(i-1) rshift w-2))) mod 2<sup>w</sup> + * for i = 1 .. n-1. x(n) is the first value to be returned by operator(). + */ + BOOST_RANDOM_DETAIL_ARITHMETIC_SEED(mersenne_twister, UIntType, value) + { + // New seeding algorithm from + // http://www.math.sci.hiroshima-u.ac.jp/~m-mat/MT/MT2002/emt19937ar.html + // In the previous versions, MSBs of the seed affected only MSBs of the + // state x[]. + const UIntType mask = ~0u; + x[0] = value & mask; + for (i = 1; i < n; i++) { + // See Knuth "The Art of Computer Programming" Vol. 2, 3rd ed., page 106 + x[i] = (1812433253UL * (x[i-1] ^ (x[i-1] >> (w-2))) + i) & mask; + } + } + + /** + * Sets the state of this mersenne_twister to the values + * returned by n invocations of gen. + * + * Complexity: Exactly n invocations of gen. + */ + BOOST_RANDOM_DETAIL_GENERATOR_SEED(mersenne_twister, Generator, gen) + { +#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + BOOST_STATIC_ASSERT(!std::numeric_limits<result_type>::is_signed); +#endif + // I could have used std::generate_n, but it takes "gen" by value + for(int j = 0; j < n; j++) + x[j] = gen(); + i = n; + } + + template<class It> + void seed(It& first, It last) + { + int j; + for(j = 0; j < n && first != last; ++j, ++first) + x[j] = *first; + i = n; + if(first == last && j < n) + throw std::invalid_argument("mersenne_twister::seed"); + } + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return 0; } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const + { + // avoid "left shift count >= with of type" warning + result_type res = 0; + for(int j = 0; j < w; ++j) + res |= (1u << j); + return res; + } + + result_type operator()(); + static bool validation(result_type v) { return val == v; } + +#ifndef BOOST_NO_OPERATORS_IN_NAMESPACE + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const mersenne_twister& mt) + { + for(int j = 0; j < mt.state_size; ++j) + os << mt.compute(j) << " "; + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, mersenne_twister& mt) + { + for(int j = 0; j < mt.state_size; ++j) + is >> mt.x[j] >> std::ws; + // MSVC (up to 7.1) and Borland (up to 5.64) don't handle the template + // value parameter "n" available from the class template scope, so use + // the static constant with the same value + mt.i = mt.state_size; + return is; + } +#endif + + friend bool operator==(const mersenne_twister& x, const mersenne_twister& y) + { + for(int j = 0; j < state_size; ++j) + if(x.compute(j) != y.compute(j)) + return false; + return true; + } + + friend bool operator!=(const mersenne_twister& x, const mersenne_twister& y) + { return !(x == y); } +#else + // Use a member function; Streamable concept not supported. + bool operator==(const mersenne_twister& rhs) const + { + for(int j = 0; j < state_size; ++j) + if(compute(j) != rhs.compute(j)) + return false; + return true; + } + + bool operator!=(const mersenne_twister& rhs) const + { return !(*this == rhs); } +#endif + +private: + /// \cond hide_private_members + // returns x(i-n+index), where index is in 0..n-1 + UIntType compute(unsigned int index) const + { + // equivalent to (i-n+index) % 2n, but doesn't produce negative numbers + return x[ (i + n + index) % (2*n) ]; + } + void twist(int block); + /// \endcond + + // state representation: next output is o(x(i)) + // x[0] ... x[k] x[k+1] ... x[n-1] x[n] ... x[2*n-1] represents + // x(i-k) ... x(i) x(i+1) ... x(i-k+n-1) x(i-k-n) ... x[i(i-k-1)] + // The goal is to always have x(i-n) ... x(i-1) available for + // operator== and save/restore. + + UIntType x[2*n]; + int i; +}; + +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION +// A definition is required even for integral static constants +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const bool mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::has_fixed_range; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::state_size; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::shift_size; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::mask_bits; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::parameter_a; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_u; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_s; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_b; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_t; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const UIntType mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_c; +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +const int mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::output_l; +#endif + +/// \cond hide_private_members +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +void mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::twist(int block) +{ + const UIntType upper_mask = (~0u) << r; + const UIntType lower_mask = ~upper_mask; + + if(block == 0) { + for(int j = n; j < 2*n; j++) { + UIntType y = (x[j-n] & upper_mask) | (x[j-(n-1)] & lower_mask); + x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0); + } + } else if (block == 1) { + // split loop to avoid costly modulo operations + { // extra scope for MSVC brokenness w.r.t. for scope + for(int j = 0; j < n-m; j++) { + UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask); + x[j] = x[j+n+m] ^ (y >> 1) ^ (y&1 ? a : 0); + } + } + + for(int j = n-m; j < n-1; j++) { + UIntType y = (x[j+n] & upper_mask) | (x[j+n+1] & lower_mask); + x[j] = x[j-(n-m)] ^ (y >> 1) ^ (y&1 ? a : 0); + } + // last iteration + UIntType y = (x[2*n-1] & upper_mask) | (x[0] & lower_mask); + x[n-1] = x[m-1] ^ (y >> 1) ^ (y&1 ? a : 0); + i = 0; + } +} +/// \endcond + +template<class UIntType, int w, int n, int m, int r, UIntType a, int u, + int s, UIntType b, int t, UIntType c, int l, UIntType val> +inline typename mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::result_type +mersenne_twister<UIntType,w,n,m,r,a,u,s,b,t,c,l,val>::operator()() +{ + if(i == n) + twist(0); + else if(i >= 2*n) + twist(1); + // Step 4 + UIntType z = x[i]; + ++i; + z ^= (z >> u); + z ^= ((z << s) & b); + z ^= ((z << t) & c); + z ^= (z >> l); + return z; +} + +} // namespace random + +/** + * The specializations \mt11213b and \mt19937 are from + * + * @blockquote + * "Mersenne Twister: A 623-dimensionally equidistributed + * uniform pseudo-random number generator", Makoto Matsumoto + * and Takuji Nishimura, ACM Transactions on Modeling and + * Computer Simulation: Special Issue on Uniform Random Number + * Generation, Vol. 8, No. 1, January 1998, pp. 3-30. + * @endblockquote + */ +typedef random::mersenne_twister<uint32_t,32,351,175,19,0xccab8ee7,11, + 7,0x31b6ab00,15,0xffe50000,17, 0xa37d3c92> mt11213b; + +/** + * The specializations \mt11213b and \mt19937 are from + * + * @blockquote + * "Mersenne Twister: A 623-dimensionally equidistributed + * uniform pseudo-random number generator", Makoto Matsumoto + * and Takuji Nishimura, ACM Transactions on Modeling and + * Computer Simulation: Special Issue on Uniform Random Number + * Generation, Vol. 8, No. 1, January 1998, pp. 3-30. + * @endblockquote + */ +typedef random::mersenne_twister<uint32_t,32,624,397,31,0x9908b0df,11, + 7,0x9d2c5680,15,0xefc60000,18, 3346425566U> mt19937; + +} // namespace boost + +BOOST_RANDOM_PTR_HELPER_SPEC(boost::mt19937) + +#endif // BOOST_RANDOM_MERSENNE_TWISTER_HPP diff --git a/3rdParty/Boost/src/boost/random/uniform_01.hpp b/3rdParty/Boost/src/boost/random/uniform_01.hpp new file mode 100644 index 0000000..2cdd05f --- /dev/null +++ b/3rdParty/Boost/src/boost/random/uniform_01.hpp @@ -0,0 +1,273 @@ +/* boost random/uniform_01.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: uniform_01.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + * Revision history + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_UNIFORM_01_HPP +#define BOOST_RANDOM_UNIFORM_01_HPP + +#include <iostream> +#include <boost/config.hpp> +#include <boost/limits.hpp> +#include <boost/static_assert.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/detail/pass_through_engine.hpp> + +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { + +#ifdef BOOST_RANDOM_DOXYGEN + +/** + * The distribution function uniform_01 models a \random_distribution. + * On each invocation, it returns a random floating-point value + * uniformly distributed in the range [0..1). + * + * The template parameter RealType shall denote a float-like value type + * with support for binary operators +, -, and /. + * + * Note: The current implementation is buggy, because it may not fill + * all of the mantissa with random bits. I'm unsure how to fill a + * (to-be-invented) @c boost::bigfloat class with random bits efficiently. + * It's probably time for a traits class. + */ +template<class RealType = double> +class uniform_01 +{ +public: + typedef RealType input_type; + typedef RealType result_type; + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const; + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const; + void reset(); + + template<class Engine> + result_type operator()(Engine& eng); + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const new_uniform_01&) + { + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, new_uniform_01&) + { + return is; + } +#endif +}; + +#else + +namespace detail { + +template<class RealType> +class new_uniform_01 +{ +public: + typedef RealType input_type; + typedef RealType result_type; + // compiler-generated copy ctor and copy assignment are fine + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(0); } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(1); } + void reset() { } + + template<class Engine> + result_type operator()(Engine& eng) { + for (;;) { + typedef typename Engine::result_type base_result; + result_type factor = result_type(1) / + (result_type((eng.max)()-(eng.min)()) + + result_type(std::numeric_limits<base_result>::is_integer ? 1 : 0)); + result_type result = result_type(eng() - (eng.min)()) * factor; + if (result < result_type(1)) + return result; + } + } + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const new_uniform_01&) + { + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, new_uniform_01&) + { + return is; + } +#endif +}; + +template<class UniformRandomNumberGenerator, class RealType> +class backward_compatible_uniform_01 +{ + typedef boost::random::detail::ptr_helper<UniformRandomNumberGenerator> traits; + typedef boost::random::detail::pass_through_engine<UniformRandomNumberGenerator> internal_engine_type; +public: + typedef UniformRandomNumberGenerator base_type; + typedef RealType result_type; + + BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); + +#if !defined(BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS) && !(defined(BOOST_MSVC) && BOOST_MSVC <= 1300) + BOOST_STATIC_ASSERT(!std::numeric_limits<RealType>::is_integer); +#endif + + explicit backward_compatible_uniform_01(typename traits::rvalue_type rng) + : _rng(rng), + _factor(result_type(1) / + (result_type((_rng.max)()-(_rng.min)()) + + result_type(std::numeric_limits<base_result>::is_integer ? 1 : 0))) + { + } + // compiler-generated copy ctor and copy assignment are fine + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(0); } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return result_type(1); } + typename traits::value_type& base() { return _rng.base(); } + const typename traits::value_type& base() const { return _rng.base(); } + void reset() { } + + result_type operator()() { + for (;;) { + result_type result = result_type(_rng() - (_rng.min)()) * _factor; + if (result < result_type(1)) + return result; + } + } + +#if !defined(BOOST_NO_OPERATORS_IN_NAMESPACE) && !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const backward_compatible_uniform_01& u) + { + os << u._rng; + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, backward_compatible_uniform_01& u) + { + is >> u._rng; + return is; + } +#endif + +private: + typedef typename internal_engine_type::result_type base_result; + internal_engine_type _rng; + result_type _factor; +}; + +#ifndef BOOST_NO_INCLASS_MEMBER_INITIALIZATION +// A definition is required even for integral static constants +template<class UniformRandomNumberGenerator, class RealType> +const bool backward_compatible_uniform_01<UniformRandomNumberGenerator, RealType>::has_fixed_range; +#endif + +template<class UniformRandomNumberGenerator> +struct select_uniform_01 +{ + template<class RealType> + struct apply + { + typedef backward_compatible_uniform_01<UniformRandomNumberGenerator, RealType> type; + }; +}; + +template<> +struct select_uniform_01<float> +{ + template<class RealType> + struct apply + { + typedef new_uniform_01<float> type; + }; +}; + +template<> +struct select_uniform_01<double> +{ + template<class RealType> + struct apply + { + typedef new_uniform_01<double> type; + }; +}; + +template<> +struct select_uniform_01<long double> +{ + template<class RealType> + struct apply + { + typedef new_uniform_01<long double> type; + }; +}; + +} + +// Because it is so commonly used: uniform distribution on the real [0..1) +// range. This allows for specializations to avoid a costly int -> float +// conversion plus float multiplication +template<class UniformRandomNumberGenerator = double, class RealType = double> +class uniform_01 + : public detail::select_uniform_01<UniformRandomNumberGenerator>::BOOST_NESTED_TEMPLATE apply<RealType>::type +{ + typedef typename detail::select_uniform_01<UniformRandomNumberGenerator>::BOOST_NESTED_TEMPLATE apply<RealType>::type impl_type; + typedef boost::random::detail::ptr_helper<UniformRandomNumberGenerator> traits; +public: + + uniform_01() {} + + explicit uniform_01(typename traits::rvalue_type rng) + : impl_type(rng) + { + } + +#if !defined(BOOST_NO_OPERATORS_IN_NAMESPACE) && !defined(BOOST_NO_MEMBER_TEMPLATE_FRIENDS) + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_01& u) + { + os << static_cast<const impl_type&>(u); + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, uniform_01& u) + { + is >> static_cast<impl_type&>(u); + return is; + } +#endif +}; + +#endif + +} // namespace boost + +#include <boost/random/detail/enable_warnings.hpp> + +#endif // BOOST_RANDOM_UNIFORM_01_HPP diff --git a/3rdParty/Boost/src/boost/random/uniform_int.hpp b/3rdParty/Boost/src/boost/random/uniform_int.hpp new file mode 100644 index 0000000..426a9e1 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/uniform_int.hpp @@ -0,0 +1,300 @@ +/* boost random/uniform_int.hpp header file + * + * Copyright Jens Maurer 2000-2001 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: uniform_int.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + * Revision history + * 2001-04-08 added min<max assertion (N. Becker) + * 2001-02-18 moved to individual header files + */ + +#ifndef BOOST_RANDOM_UNIFORM_INT_HPP +#define BOOST_RANDOM_UNIFORM_INT_HPP + +#include <cassert> +#include <iostream> +#include <boost/config.hpp> +#include <boost/limits.hpp> +#include <boost/static_assert.hpp> +#include <boost/detail/workaround.hpp> +#include <boost/random/detail/config.hpp> +#include <boost/random/detail/signed_unsigned_tools.hpp> +#include <boost/type_traits/make_unsigned.hpp> + +namespace boost { + +/** + * The distribution function uniform_int models a \random_distribution. + * On each invocation, it returns a random integer value uniformly + * distributed in the set of integer numbers {min, min+1, min+2, ..., max}. + * + * The template parameter IntType shall denote an integer-like value type. + */ +template<class IntType = int> +class uniform_int +{ +public: + typedef IntType input_type; + typedef IntType result_type; + + /// \cond hide_private_members + typedef typename make_unsigned<result_type>::type range_type; + /// \endcond + + /** + * Constructs a uniform_int object. @c min and @c max are + * the parameters of the distribution. + * + * Requires: min <= max + */ + explicit uniform_int(IntType min_arg = 0, IntType max_arg = 9) + : _min(min_arg), _max(max_arg) + { +#ifndef BOOST_NO_LIMITS_COMPILE_TIME_CONSTANTS + // MSVC fails BOOST_STATIC_ASSERT with std::numeric_limits at class scope + BOOST_STATIC_ASSERT(std::numeric_limits<IntType>::is_integer); +#endif + assert(min_arg <= max_arg); + init(); + } + + /** + * Returns: The "min" parameter of the distribution + */ + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _min; } + /** + * Returns: The "max" parameter of the distribution + */ + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return _max; } + void reset() { } + + // can't have member function templates out-of-line due to MSVC bugs + template<class Engine> + result_type operator()(Engine& eng) + { + return generate(eng, _min, _max, _range); + } + + template<class Engine> + result_type operator()(Engine& eng, result_type n) + { + assert(n > 0); + + if (n == 1) + { + return 0; + } + + return generate(eng, 0, n - 1, n - 1); + } + +#ifndef BOOST_RANDOM_NO_STREAM_OPERATORS + template<class CharT, class Traits> + friend std::basic_ostream<CharT,Traits>& + operator<<(std::basic_ostream<CharT,Traits>& os, const uniform_int& ud) + { + os << ud._min << " " << ud._max; + return os; + } + + template<class CharT, class Traits> + friend std::basic_istream<CharT,Traits>& + operator>>(std::basic_istream<CharT,Traits>& is, uniform_int& ud) + { + is >> std::ws >> ud._min >> std::ws >> ud._max; + ud.init(); + return is; + } +#endif + +private: + +#ifdef BOOST_MSVC +#pragma warning(push) +// disable division by zero warning, since we can't +// actually divide by zero. +#pragma warning(disable:4723) +#endif + + /// \cond hide_private_members + template<class Engine> + static result_type generate(Engine& eng, result_type min_value, result_type /*max_value*/, range_type range) + { + typedef typename Engine::result_type base_result; + // ranges are always unsigned + typedef typename make_unsigned<base_result>::type base_unsigned; + const base_result bmin = (eng.min)(); + const base_unsigned brange = + random::detail::subtract<base_result>()((eng.max)(), (eng.min)()); + + if(range == 0) { + return min_value; + } else if(brange == range) { + // this will probably never happen in real life + // basically nothing to do; just take care we don't overflow / underflow + base_unsigned v = random::detail::subtract<base_result>()(eng(), bmin); + return random::detail::add<base_unsigned, result_type>()(v, min_value); + } else if(brange < range) { + // use rejection method to handle things like 0..3 --> 0..4 + for(;;) { + // concatenate several invocations of the base RNG + // take extra care to avoid overflows + + // limit == floor((range+1)/(brange+1)) + // Therefore limit*(brange+1) <= range+1 + range_type limit; + if(range == (std::numeric_limits<range_type>::max)()) { + limit = range/(range_type(brange)+1); + if(range % (range_type(brange)+1) == range_type(brange)) + ++limit; + } else { + limit = (range+1)/(range_type(brange)+1); + } + + // We consider "result" as expressed to base (brange+1): + // For every power of (brange+1), we determine a random factor + range_type result = range_type(0); + range_type mult = range_type(1); + + // loop invariants: + // result < mult + // mult <= range + while(mult <= limit) { + // Postcondition: result <= range, thus no overflow + // + // limit*(brange+1)<=range+1 def. of limit (1) + // eng()-bmin<=brange eng() post. (2) + // and mult<=limit. loop condition (3) + // Therefore mult*(eng()-bmin+1)<=range+1 by (1),(2),(3) (4) + // Therefore mult*(eng()-bmin)+mult<=range+1 rearranging (4) (5) + // result<mult loop invariant (6) + // Therefore result+mult*(eng()-bmin)<range+1 by (5), (6) (7) + // + // Postcondition: result < mult*(brange+1) + // + // result<mult loop invariant (1) + // eng()-bmin<=brange eng() post. (2) + // Therefore result+mult*(eng()-bmin) < + // mult+mult*(eng()-bmin) by (1) (3) + // Therefore result+(eng()-bmin)*mult < + // mult+mult*brange by (2), (3) (4) + // Therefore result+(eng()-bmin)*mult < + // mult*(brange+1) by (4) + result += static_cast<range_type>(random::detail::subtract<base_result>()(eng(), bmin) * mult); + + // equivalent to (mult * (brange+1)) == range+1, but avoids overflow. + if(mult * range_type(brange) == range - mult + 1) { + // The destination range is an integer power of + // the generator's range. + return(result); + } + + // Postcondition: mult <= range + // + // limit*(brange+1)<=range+1 def. of limit (1) + // mult<=limit loop condition (2) + // Therefore mult*(brange+1)<=range+1 by (1), (2) (3) + // mult*(brange+1)!=range+1 preceding if (4) + // Therefore mult*(brange+1)<range+1 by (3), (4) (5) + // + // Postcondition: result < mult + // + // See the second postcondition on the change to result. + mult *= range_type(brange)+range_type(1); + } + // loop postcondition: range/mult < brange+1 + // + // mult > limit loop condition (1) + // Suppose range/mult >= brange+1 Assumption (2) + // range >= mult*(brange+1) by (2) (3) + // range+1 > mult*(brange+1) by (3) (4) + // range+1 > (limit+1)*(brange+1) by (1), (4) (5) + // (range+1)/(brange+1) > limit+1 by (5) (6) + // limit < floor((range+1)/(brange+1)) by (6) (7) + // limit==floor((range+1)/(brange+1)) def. of limit (8) + // not (2) reductio (9) + // + // loop postcondition: (range/mult)*mult+(mult-1) >= range + // + // (range/mult)*mult + range%mult == range identity (1) + // range%mult < mult def. of % (2) + // (range/mult)*mult+mult > range by (1), (2) (3) + // (range/mult)*mult+(mult-1) >= range by (3) (4) + // + // Note that the maximum value of result at this point is (mult-1), + // so after this final step, we generate numbers that can be + // at least as large as range. We have to really careful to avoid + // overflow in this final addition and in the rejection. Anything + // that overflows is larger than range and can thus be rejected. + + // range/mult < brange+1 -> no endless loop + range_type result_increment = uniform_int<range_type>(0, range/mult)(eng); + if((std::numeric_limits<range_type>::max)() / mult < result_increment) { + // The multiplcation would overflow. Reject immediately. + continue; + } + result_increment *= mult; + // unsigned integers are guaranteed to wrap on overflow. + result += result_increment; + if(result < result_increment) { + // The addition overflowed. Reject. + continue; + } + if(result > range) { + // Too big. Reject. + continue; + } + return random::detail::add<range_type, result_type>()(result, min_value); + } + } else { // brange > range + base_unsigned bucket_size; + // it's safe to add 1 to range, as long as we cast it first, + // because we know that it is less than brange. However, + // we do need to be careful not to cause overflow by adding 1 + // to brange. + if(brange == (std::numeric_limits<base_unsigned>::max)()) { + bucket_size = brange / (static_cast<base_unsigned>(range)+1); + if(brange % (static_cast<base_unsigned>(range)+1) == static_cast<base_unsigned>(range)) { + ++bucket_size; + } + } else { + bucket_size = (brange+1) / (static_cast<base_unsigned>(range)+1); + } + for(;;) { + base_unsigned result = + random::detail::subtract<base_result>()(eng(), bmin); + result /= bucket_size; + // result and range are non-negative, and result is possibly larger + // than range, so the cast is safe + if(result <= static_cast<base_unsigned>(range)) + return random::detail::add<base_unsigned, result_type>()(result, min_value); + } + } + } + +#ifdef BOOST_MSVC +#pragma warning(pop) +#endif + + void init() + { + _range = random::detail::subtract<result_type>()(_max, _min); + } + + /// \endcond + + // The result_type may be signed or unsigned, but the _range is always + // unsigned. + result_type _min, _max; + range_type _range; +}; + +} // namespace boost + +#endif // BOOST_RANDOM_UNIFORM_INT_HPP diff --git a/3rdParty/Boost/src/boost/random/variate_generator.hpp b/3rdParty/Boost/src/boost/random/variate_generator.hpp new file mode 100644 index 0000000..930d961 --- /dev/null +++ b/3rdParty/Boost/src/boost/random/variate_generator.hpp @@ -0,0 +1,220 @@ +/* boost random/variate_generator.hpp header file + * + * Copyright Jens Maurer 2002 + * Distributed under the Boost Software License, Version 1.0. (See + * accompanying file LICENSE_1_0.txt or copy at + * http://www.boost.org/LICENSE_1_0.txt) + * + * See http://www.boost.org for most recent version including documentation. + * + * $Id: variate_generator.hpp 60755 2010-03-22 00:45:06Z steven_watanabe $ + * + */ + +#ifndef BOOST_RANDOM_RANDOM_GENERATOR_HPP +#define BOOST_RANDOM_RANDOM_GENERATOR_HPP + +#include <boost/config.hpp> + +// implementation details +#include <boost/detail/workaround.hpp> +#include <boost/random/uniform_01.hpp> +#include <boost/random/detail/pass_through_engine.hpp> +#include <boost/random/detail/uniform_int_float.hpp> +#include <boost/random/detail/ptr_helper.hpp> + +// Borland C++ 5.6.0 has problems using its numeric_limits traits as +// template parameters +#if BOOST_WORKAROUND(__BORLANDC__, <= 0x564) +#include <boost/type_traits/is_integral.hpp> +#endif + +#include <boost/random/detail/disable_warnings.hpp> + +namespace boost { + +/// \cond hide_private_members + +namespace random { +namespace detail { + +template<bool have_int, bool want_int> +struct engine_helper; + +// for consistency, always have two levels of decorations +template<> +struct engine_helper<true, true> +{ + template<class Engine, class DistInputType> + struct impl + { + typedef pass_through_engine<Engine> type; + }; +}; + +template<> +struct engine_helper<false, false> +{ + template<class Engine, class DistInputType> + struct impl + { + typedef uniform_01<Engine, DistInputType> type; + }; +}; + +template<> +struct engine_helper<true, false> +{ + template<class Engine, class DistInputType> + struct impl + { + typedef uniform_01<Engine, DistInputType> type; + }; +}; + +template<> +struct engine_helper<false, true> +{ + template<class Engine, class DistInputType> + struct impl + { + typedef uniform_int_float<Engine, unsigned long> type; + }; +}; + +} // namespace detail +} // namespace random + +///\endcond + +/** + * A random variate generator is used to join a random number + * generator together with a random number distribution. + * Boost.Random provides a vast choice of \generators as well + * as \distributions. + * + * Instantations of class template @c variate_generator model + * a \number_generator. + * + * The argument for the template parameter Engine shall be of + * the form U, U&, or U*, where U models a + * \uniform_random_number_generator. Then, the member + * engine_value_type names U (not the pointer or reference to U). + * + * Specializations of @c variate_generator satisfy the + * requirements of CopyConstructible. They also satisfy the + * requirements of Assignable unless the template parameter + * Engine is of the form U&. + * + * The complexity of all functions specified in this section + * is constant. No function described in this section except + * the constructor throws an exception. + */ +template<class Engine, class Distribution> +class variate_generator +{ +private: + typedef random::detail::pass_through_engine<Engine> decorated_engine; + +public: + typedef typename decorated_engine::base_type engine_value_type; + typedef Engine engine_type; + typedef Distribution distribution_type; + typedef typename Distribution::result_type result_type; + + /** + * Constructs a @c variate_generator object with the associated + * \uniform_random_number_generator eng and the associated + * \random_distribution d. + * + * Throws: If and what the copy constructor of Engine or + * Distribution throws. + */ + variate_generator(Engine e, Distribution d) + : _eng(decorated_engine(e)), _dist(d) { } + + /** + * Returns: distribution()(e) + * + * Notes: The sequence of numbers produced by the + * \uniform_random_number_generator e, s<sub>e</sub>, is + * obtained from the sequence of numbers produced by the + * associated \uniform_random_number_generator eng, s<sub>eng</sub>, + * as follows: Consider the values of @c numeric_limits<T>::is_integer + * for @c T both @c Distribution::input_type and + * @c engine_value_type::result_type. If the values for both types are + * true, then se is identical to s<sub>eng</sub>. Otherwise, if the + * values for both types are false, then the numbers in s<sub>eng</sub> + * are divided by engine().max()-engine().min() to obtain the numbers + * in s<sub>e</sub>. Otherwise, if the value for + * @c engine_value_type::result_type is true and the value for + * @c Distribution::input_type is false, then the numbers in s<sub>eng</sub> + * are divided by engine().max()-engine().min()+1 to obtain the numbers in + * s<sub>e</sub>. Otherwise, the mapping from s<sub>eng</sub> to + * s<sub>e</sub> is implementation-defined. In all cases, an + * implicit conversion from @c engine_value_type::result_type to + * @c Distribution::input_type is performed. If such a conversion does + * not exist, the program is ill-formed. + */ + result_type operator()() { return _dist(_eng); } + /** + * Returns: distribution()(e, value). + * For the semantics of e, see the description of operator()(). + */ + template<class T> + result_type operator()(T value) { return _dist(_eng, value); } + + /** + * Returns: A reference to the associated uniform random number generator. + */ + engine_value_type& engine() { return _eng.base().base(); } + /** + * Returns: A reference to the associated uniform random number generator. + */ + const engine_value_type& engine() const { return _eng.base().base(); } + + /** + * Returns: A reference to the associated random distribution. + */ + distribution_type& distribution() { return _dist; } + /** + * Returns: A reference to the associated random distribution. + */ + const distribution_type& distribution() const { return _dist; } + + /** + * Precondition: distribution().min() is well-formed + * + * Returns: distribution().min() + */ + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (distribution().min)(); } + /** + * Precondition: distribution().max() is well-formed + * + * Returns: distribution().max() + */ + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const { return (distribution().max)(); } + +private: +#if BOOST_WORKAROUND(__BORLANDC__, <= 0x564) + typedef typename random::detail::engine_helper< + ::boost::is_integral<typename decorated_engine::result_type>::value, + ::boost::is_integral<typename Distribution::input_type>::value + >::BOOST_NESTED_TEMPLATE impl<decorated_engine, typename Distribution::input_type>::type internal_engine_type; +#else + enum { + have_int = std::numeric_limits<typename decorated_engine::result_type>::is_integer, + want_int = std::numeric_limits<typename Distribution::input_type>::is_integer + }; + typedef typename random::detail::engine_helper<have_int, want_int>::BOOST_NESTED_TEMPLATE impl<decorated_engine, typename Distribution::input_type>::type internal_engine_type; +#endif + + internal_engine_type _eng; + distribution_type _dist; +}; + +} // namespace boost + +#include <boost/random/detail/disable_warnings.hpp> + +#endif // BOOST_RANDOM_RANDOM_GENERATOR_HPP diff --git a/3rdParty/Boost/src/boost/uuid/name_generator.hpp b/3rdParty/Boost/src/boost/uuid/name_generator.hpp new file mode 100644 index 0000000..42473a6 --- /dev/null +++ b/3rdParty/Boost/src/boost/uuid/name_generator.hpp @@ -0,0 +1,125 @@ +// Boost name_generator.hpp header file ----------------------------------------------// + +// Copyright 2010 Andy Tompkins. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_UUID_NAME_GENERATOR_HPP +#define BOOST_UUID_NAME_GENERATOR_HPP + +#include <boost/uuid/uuid.hpp> +#include <boost/uuid/sha1.hpp> +#include <boost/assert.hpp> +#include <string> +#include <cstring> // for strlen, wcslen + +#ifdef BOOST_NO_STDC_NAMESPACE +namespace std { + using ::strlen; + using ::wcslen; +} //namespace std +#endif //BOOST_NO_STDC_NAMESPACE + +namespace boost { +namespace uuids { + +// generate a name-based uuid +// TODO: add in common namesspace uuids +class name_generator { +public: + typedef uuid result_type; + + explicit name_generator(uuid const& namespace_uuid) + : namespace_uuid(namespace_uuid) + {} + + uuid operator()(const char* name) { + reset(); + process_characters(name, std::strlen(name)); + return sha_to_uuid(); + } + + uuid operator()(const wchar_t* name) { + reset(); + process_characters(name, std::wcslen(name)); + return sha_to_uuid(); + } + + template <typename ch, typename char_traits, typename alloc> + uuid operator()(std::basic_string<ch, char_traits, alloc> const& name) { + reset(); + process_characters(name.c_str(), name.length()); + return sha_to_uuid(); + } + + uuid operator()(void const* buffer, std::size_t byte_count) { + reset(); + sha.process_bytes(buffer, byte_count); + return sha_to_uuid(); + }; + +private: + // we convert all characters to uint32_t so that each + // character is 4 bytes reguardless of sizeof(char) or + // sizeof(wchar_t). We want the name string on any + // platform / compiler to generate the same uuid + // except for char + template <typename char_type> + void process_characters(char_type const*const characters, size_t count) { + BOOST_ASSERT(sizeof(uint32_t) >= sizeof(char_type)); + + for (size_t i=0; i<count; i++) { + uint32_t c = characters[i]; + sha.process_byte( (c >> 0) && 0xFF ); + sha.process_byte( (c >> 8) && 0xFF ); + sha.process_byte( (c >> 16) && 0xFF ); + sha.process_byte( (c >> 24) && 0xFF ); + } + } + + void process_characters(char const*const characters, size_t count) { + sha.process_bytes(characters, count); + } + + void reset() + { + sha.reset(); + sha.process_bytes(namespace_uuid.begin(), namespace_uuid.size()); + } + + uuid sha_to_uuid() + { + unsigned int digest[5]; + + sha.get_digest(digest); + + uuid u; + for (int i=0; i<4; ++i) { + *(u.begin() + i*4+0) = ((digest[i] >> 24) & 0xFF); + *(u.begin() + i*4+1) = ((digest[i] >> 16) & 0xFF); + *(u.begin() + i*4+2) = ((digest[i] >> 8) & 0xFF); + *(u.begin() + i*4+3) = ((digest[i] >> 0) & 0xFF); + } + + // set variant + // must be 0b10xxxxxx + *(u.begin()+8) &= 0xBF; + *(u.begin()+8) |= 0x80; + + // set version + // must be 0b0101xxxx + *(u.begin()+6) &= 0x5F; //0b01011111 + *(u.begin()+6) |= 0x50; //0b01010000 + + return u; + } + +private: + uuid namespace_uuid; + detail::sha1 sha; +}; + +}} // namespace boost::uuids + +#endif // BOOST_UUID_NAME_GENERATOR_HPP diff --git a/3rdParty/Boost/src/boost/uuid/nil_generator.hpp b/3rdParty/Boost/src/boost/uuid/nil_generator.hpp new file mode 100644 index 0000000..c3c5818 --- /dev/null +++ b/3rdParty/Boost/src/boost/uuid/nil_generator.hpp @@ -0,0 +1,34 @@ +// Boost nil_generator.hpp header file ----------------------------------------------// + +// Copyright 2010 Andy Tompkins. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_UUID_NIL_GENERATOR_HPP +#define BOOST_UUID_NIL_GENERATOR_HPP + +#include <boost/uuid/uuid.hpp> + +namespace boost { +namespace uuids { + +// generate a nil uuid +struct nil_generator { + typedef uuid result_type; + + uuid operator()() const { + // initialize to all zeros + uuid u = {{0}}; + return u; + } +}; + +inline uuid nil_uuid() { + return nil_generator()(); +} + +}} // namespace boost::uuids + +#endif // BOOST_UUID_NIL_GENERATOR_HPP + diff --git a/3rdParty/Boost/src/boost/uuid/random_generator.hpp b/3rdParty/Boost/src/boost/uuid/random_generator.hpp new file mode 100644 index 0000000..4d11f6b --- /dev/null +++ b/3rdParty/Boost/src/boost/uuid/random_generator.hpp @@ -0,0 +1,118 @@ +// Boost random_generator.hpp header file ----------------------------------------------// + +// Copyright 2010 Andy Tompkins. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_UUID_RANDOM_GENERATOR_HPP +#define BOOST_UUID_RANDOM_GENERATOR_HPP + +#include <boost/uuid/uuid.hpp> +#include <boost/uuid/seed_rng.hpp> +#include <boost/random/uniform_int.hpp> +#include <boost/random/variate_generator.hpp> +#include <boost/random/mersenne_twister.hpp> +#include <boost/assert.hpp> +#include <boost/shared_ptr.hpp> +#include <limits> + +namespace boost { +namespace uuids { + +// generate a random-based uuid +template <typename UniformRandomNumberGenerator> +class basic_random_generator { +private: + typedef uniform_int<unsigned long> distribution_type; + typedef variate_generator<UniformRandomNumberGenerator*, distribution_type> generator_type; + + struct null_deleter + { + void operator()(void const *) const {} + }; + +public: + typedef uuid result_type; + + // default constructor creates the random number generator + basic_random_generator() + : pURNG(new UniformRandomNumberGenerator) + , generator + ( pURNG.get() + , distribution_type + ( (std::numeric_limits<unsigned long>::min)() + , (std::numeric_limits<unsigned long>::max)() + ) + ) + { + // seed the random number generator + detail::seed(*pURNG); + } + + // keep a reference to a random number generator + // don't seed a given random number generator + explicit basic_random_generator(UniformRandomNumberGenerator& gen) + : pURNG(&gen, null_deleter()) + , generator + ( pURNG.get() + , distribution_type + ( (std::numeric_limits<unsigned long>::min)() + , (std::numeric_limits<unsigned long>::max)() + ) + ) + {} + + // keep a pointer to a random number generator + // don't seed a given random number generator + explicit basic_random_generator(UniformRandomNumberGenerator* pGen) + : pURNG(pGen, null_deleter()) + , generator + ( pURNG.get() + , distribution_type + ( (std::numeric_limits<unsigned long>::min)() + , (std::numeric_limits<unsigned long>::max)() + ) + ) + { + BOOST_ASSERT(pURNG); + } + + uuid operator()() + { + uuid u; + + int i=0; + unsigned long random_value = generator(); + for (uuid::iterator it=u.begin(); it!=u.end(); ++it, ++i) { + if (i==sizeof(unsigned long)) { + random_value = generator(); + i = 0; + } + + *it = ((random_value >> (i*8)) & 0xFF); + } + + // set variant + // must be 0b10xxxxxx + *(u.begin()+8) &= 0xBF; + *(u.begin()+8) |= 0x80; + + // set version + // must be 0b0100xxxx + *(u.begin()+6) &= 0x4F; //0b01001111 + *(u.begin()+6) |= 0x40; //0b01000000 + + return u; + } + +private: + shared_ptr<UniformRandomNumberGenerator> pURNG; + generator_type generator; +}; + +typedef basic_random_generator<mt19937> random_generator; + +}} // namespace boost::uuids + +#endif //BOOST_UUID_RANDOM_GENERATOR_HPP diff --git a/3rdParty/Boost/src/boost/uuid/seed_rng.hpp b/3rdParty/Boost/src/boost/uuid/seed_rng.hpp new file mode 100644 index 0000000..3090197 --- /dev/null +++ b/3rdParty/Boost/src/boost/uuid/seed_rng.hpp @@ -0,0 +1,262 @@ +// Boost seed_rng.hpp header file ----------------------------------------------// + +// Copyright 2007 Andy Tompkins. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Revision History +// 09 Nov 2007 - Initial Revision +// 25 Feb 2008 - moved to namespace boost::uuids::detail +// 28 Nov 2009 - disabled deprecated warnings for MSVC + +// seed_rng models a UniformRandomNumberGenerator (see Boost.Random). +// Random number generators are hard to seed well. This is intended to provide +// good seed values for random number generators. +// It creates random numbers from a sha1 hash of data from a variary of sources, +// all of which are standard function calls. It produces random numbers slowly. +// Peter Dimov provided the details of sha1_random_digest_(). +// see http://archives.free.net.ph/message/20070507.175609.4c4f503a.en.html + +#ifndef BOOST_UUID_SEED_RNG_HPP +#define BOOST_UUID_SEED_RNG_HPP + +#include <boost/config.hpp> +#include <cstring> // for memcpy +#include <limits> +#include <memory.h> +#include <ctime> // for time_t, time, clock_t, clock +#include <cstdlib> // for rand +#include <cstdio> // for FILE, fopen, fread, fclose +#include <boost/uuid/sha1.hpp> +//#include <boost/nondet_random.hpp> //forward declare boost::random_device + +// can't use boost::generator_iterator since boost::random number seed(Iter&, Iter) +// functions need a last iterator +//#include <boost/generator_iterator.hpp> +# include <boost/iterator/iterator_facade.hpp> + +#if defined(_MSC_VER) +#pragma warning(push) // Save warning settings. +#pragma warning(disable : 4996) // Disable deprecated std::fopen +#endif + +#ifdef BOOST_NO_STDC_NAMESPACE +namespace std { + using ::memcpy; + using ::time_t; + using ::time; + using ::clock_t; + using ::clock; + using ::rand; + using ::FILE; + using ::fopen; + using ::fread; + using ::fclose; +} //namespace std +#endif + +// forward declare random number generators +namespace boost { +class random_device; +} //namespace boost + +namespace boost { +namespace uuids { +namespace detail { + +// should this be part of Boost.Random? +class seed_rng +{ +public: + typedef unsigned int result_type; + BOOST_STATIC_CONSTANT(bool, has_fixed_range = false); + //BOOST_STATIC_CONSTANT(unsigned int, min_value = 0); + //BOOST_STATIC_CONSTANT(unsigned int, max_value = UINT_MAX); + +public: + // note: rd_ intentionally left uninitialized + seed_rng() + : rd_index_(5) + , random_(std::fopen( "/dev/urandom", "rb" )) + {} + + ~seed_rng() + { + if (random_) { + std::fclose(random_); + } + } + + result_type min BOOST_PREVENT_MACRO_SUBSTITUTION () const + { + return (std::numeric_limits<result_type>::min)(); + } + result_type max BOOST_PREVENT_MACRO_SUBSTITUTION () const + { + return (std::numeric_limits<result_type>::max)(); + } + + result_type operator()() + { + if (rd_index_ >= 5) { + //get new digest + sha1_random_digest_(); + + rd_index_ = 0; + } + + return rd_[rd_index_++]; + } + +private: + static unsigned int * sha1_random_digest_state_() + { + // intentionally left uninitialized + static unsigned int state[ 5 ]; + return state; + } + + void sha1_random_digest_() + { + boost::uuids::detail::sha1 sha; + + unsigned int * ps = sha1_random_digest_state_(); + + unsigned int state[ 5 ]; + std::memcpy( state, ps, sizeof( state ) ); // harmless data race + + sha.process_bytes( (unsigned char const*)state, sizeof( state ) ); + sha.process_bytes( (unsigned char const*)&ps, sizeof( ps ) ); + + { + std::time_t tm = std::time( 0 ); + sha.process_bytes( (unsigned char const*)&tm, sizeof( tm ) ); + } + + { + std::clock_t ck = std::clock(); + sha.process_bytes( (unsigned char const*)&ck, sizeof( ck ) ); + } + + { + unsigned int rn[] = { std::rand(), std::rand(), std::rand() }; + sha.process_bytes( (unsigned char const*)rn, sizeof( rn ) ); + } + + { + // intentionally left uninitialized + unsigned char buffer[ 20 ]; + + if(random_) + { + std::fread( buffer, 1, 20, random_ ); + } + + // using an uninitialized buffer[] if fopen fails + // intentional, we rely on its contents being random + sha.process_bytes( buffer, sizeof( buffer ) ); + } + + { + // *p is intentionally left uninitialized + unsigned int * p = new unsigned int; + + sha.process_bytes( (unsigned char const*)p, sizeof( *p ) ); + sha.process_bytes( (unsigned char const*)&p, sizeof( p ) ); + + delete p; + } + + sha.process_bytes( (unsigned char const*)rd_, sizeof( rd_ ) ); + + unsigned int digest[ 5 ]; + sha.get_digest( digest ); + + for( int i = 0; i < 5; ++i ) + { + // harmless data race + ps[ i ] ^= digest[ i ]; + rd_[ i ] ^= digest[ i ]; + } + } + +private: + unsigned int rd_[5]; + int rd_index_; + std::FILE * random_; + +private: // make seed_rng noncopyable + seed_rng(seed_rng const&); + seed_rng& operator=(seed_rng const&); +}; + +// almost a copy of boost::generator_iterator +// but default constructor sets m_g to NULL +template <class Generator> +class generator_iterator + : public iterator_facade< + generator_iterator<Generator> + , typename Generator::result_type + , single_pass_traversal_tag + , typename Generator::result_type const& + > +{ + typedef iterator_facade< + generator_iterator<Generator> + , typename Generator::result_type + , single_pass_traversal_tag + , typename Generator::result_type const& + > super_t; + + public: + generator_iterator() : m_g(NULL) {} + generator_iterator(Generator* g) : m_g(g), m_value((*m_g)()) {} + + void increment() + { + m_value = (*m_g)(); + } + + const typename Generator::result_type& + dereference() const + { + return m_value; + } + + bool equal(generator_iterator const& y) const + { + return this->m_g == y.m_g && this->m_value == y.m_value; + } + + private: + Generator* m_g; + typename Generator::result_type m_value; +}; + +// seed() seeds a random number generator with good seed values + +template <typename UniformRandomNumberGenerator> +inline void seed(UniformRandomNumberGenerator& rng) +{ + seed_rng seed_gen; + generator_iterator<seed_rng> begin(&seed_gen); + generator_iterator<seed_rng> end; + rng.seed(begin, end); +} + +// random_device does not / can not be seeded +template <> +inline void seed<boost::random_device>(boost::random_device&) {} + +// random_device does not / can not be seeded +template <> +inline void seed<seed_rng>(seed_rng&) {} + +}}} //namespace boost::uuids::detail + +#if defined(_MSC_VER) +#pragma warning(pop) // Restore warnings to previous state. +#endif + +#endif diff --git a/3rdParty/Boost/src/boost/uuid/sha1.hpp b/3rdParty/Boost/src/boost/uuid/sha1.hpp new file mode 100644 index 0000000..b4a1344 --- /dev/null +++ b/3rdParty/Boost/src/boost/uuid/sha1.hpp @@ -0,0 +1,208 @@ +// boost/uuid/sha1.hpp header file ----------------------------------------------// + +// Copyright 2007 Andy Tompkins. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Revision History +// 29 May 2007 - Initial Revision +// 25 Feb 2008 - moved to namespace boost::uuids::detail + +// This is a byte oriented implementation +// Note: this implementation does not handle message longer than +// 2^32 bytes. + +#ifndef BOOST_UUID_SHA1_H +#define BOOST_UUID_SHA1_H + +#include <boost/static_assert.hpp> +#include <cstddef> + +#ifdef BOOST_NO_STDC_NAMESPACE +namespace std { + using ::size_t; +} // namespace std +#endif + +namespace boost { +namespace uuids { +namespace detail { + +BOOST_STATIC_ASSERT(sizeof(unsigned char)*8 == 8); +BOOST_STATIC_ASSERT(sizeof(unsigned int)*8 == 32); + +inline unsigned int left_rotate(unsigned int x, std::size_t n) +{ + return (x<<n) ^ (x>> (32-n)); +} + +class sha1 +{ +public: + typedef unsigned int(&digest_type)[5]; +public: + sha1(); + + void reset(); + + void process_byte(unsigned char byte); + void process_block(void const* bytes_begin, void const* bytes_end); + void process_bytes(void const* buffer, std::size_t byte_count); + + void get_digest(digest_type digest); + +private: + void process_block(); + +private: + unsigned int h_[5]; + + unsigned char block_[64]; + + std::size_t block_byte_index_; + std::size_t byte_count_; +}; + +inline sha1::sha1() +{ + reset(); +} + +inline void sha1::reset() +{ + h_[0] = 0x67452301; + h_[1] = 0xEFCDAB89; + h_[2] = 0x98BADCFE; + h_[3] = 0x10325476; + h_[4] = 0xC3D2E1F0; + + block_byte_index_ = 0; + byte_count_ = 0; +} + +inline void sha1::process_byte(unsigned char byte) +{ + block_[block_byte_index_++] = byte; + ++byte_count_; + if (block_byte_index_ == 64) { + block_byte_index_ = 0; + process_block(); + } +} + +inline void sha1::process_block(void const* bytes_begin, void const* bytes_end) +{ + unsigned char const* begin = static_cast<unsigned char const*>(bytes_begin); + unsigned char const* end = static_cast<unsigned char const*>(bytes_end); + for(; begin != end; ++begin) { + process_byte(*begin); + } +} + +inline void sha1::process_bytes(void const* buffer, std::size_t byte_count) +{ + unsigned char const* b = static_cast<unsigned char const*>(buffer); + process_block(b, b+byte_count); +} + +inline void sha1::process_block() +{ + unsigned int w[80]; + for (std::size_t i=0; i<16; ++i) { + w[i] = (block_[i*4 + 0] << 24); + w[i] |= (block_[i*4 + 1] << 16); + w[i] |= (block_[i*4 + 2] << 8); + w[i] |= (block_[i*4 + 3]); + } + for (std::size_t i=16; i<80; ++i) { + w[i] = left_rotate((w[i-3] ^ w[i-8] ^ w[i-14] ^ w[i-16]), 1); + } + + unsigned int a = h_[0]; + unsigned int b = h_[1]; + unsigned int c = h_[2]; + unsigned int d = h_[3]; + unsigned int e = h_[4]; + + for (std::size_t i=0; i<80; ++i) { + unsigned int f; + unsigned int k; + + if (i<20) { + f = (b & c) | (~b & d); + k = 0x5A827999; + } else if (i<40) { + f = b ^ c ^ d; + k = 0x6ED9EBA1; + } else if (i<60) { + f = (b & c) | (b & d) | (c & d); + k = 0x8F1BBCDC; + } else { + f = b ^ c ^ d; + k = 0xCA62C1D6; + } + + unsigned temp = left_rotate(a, 5) + f + e + k + w[i]; + e = d; + d = c; + c = left_rotate(b, 30); + b = a; + a = temp; + } + + h_[0] += a; + h_[1] += b; + h_[2] += c; + h_[3] += d; + h_[4] += e; +} + +inline void sha1::get_digest(digest_type digest) +{ + std::size_t bit_count = byte_count_*8; + + // append the bit '1' to the message + process_byte(0x80); + + // append k bits '0', where k is the minimum number >= 0 + // such that the resulting message length is congruent to 56 (mod 64) + // check if there is enough space for padding and bit_count + if (block_byte_index_ > 56) { + // finish this block + while (block_byte_index_ != 0) { + process_byte(0); + } + + // one more block + while (block_byte_index_ < 56) { + process_byte(0); + } + } else { + while (block_byte_index_ < 56) { + process_byte(0); + } + } + + // append length of message (before pre-processing) + // as a 64-bit big-endian integer + process_byte(0); + process_byte(0); + process_byte(0); + process_byte(0); + process_byte( static_cast<unsigned char>((bit_count>>24) & 0xFF)); + process_byte( static_cast<unsigned char>((bit_count>>16) & 0xFF)); + process_byte( static_cast<unsigned char>((bit_count>>8 ) & 0xFF)); + process_byte( static_cast<unsigned char>((bit_count) & 0xFF)); + + // get final digest + digest[0] = h_[0]; + digest[1] = h_[1]; + digest[2] = h_[2]; + digest[3] = h_[3]; + digest[4] = h_[4]; +} + +}}} // namespace boost::uuids::detail + +#endif diff --git a/3rdParty/Boost/src/boost/uuid/string_generator.hpp b/3rdParty/Boost/src/boost/uuid/string_generator.hpp new file mode 100644 index 0000000..7d2733b --- /dev/null +++ b/3rdParty/Boost/src/boost/uuid/string_generator.hpp @@ -0,0 +1,184 @@ +// Boost string_generator.hpp header file ----------------------------------------------// + +// Copyright 2010 Andy Tompkins. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +#ifndef BOOST_UUID_STRING_GENERATOR_HPP +#define BOOST_UUID_STRING_GENERATOR_HPP + +#include <boost/uuid/uuid.hpp> +#include <string> +#include <cstring> // for strlen, wcslen +#include <iterator> +#include <algorithm> // for find +#include <stdexcept> + +#ifdef BOOST_NO_STDC_NAMESPACE +namespace std { + using ::strlen; + using ::wcslen; +} //namespace std +#endif //BOOST_NO_STDC_NAMESPACE + +namespace boost { +namespace uuids { + +// generate a uuid from a string +// lexical_cast works fine using uuid_io.hpp +// but this generator should accept more forms +// and be more efficient +// would like to accept the following forms: +// 0123456789abcdef0123456789abcdef +// 01234567-89ab-cdef-0123456789abcdef +// {01234567-89ab-cdef-0123456789abcdef} +// {0123456789abcdef0123456789abcdef} +// others? +struct string_generator { + typedef uuid result_type; + + template <typename ch, typename char_traits, typename alloc> + uuid operator()(std::basic_string<ch, char_traits, alloc> const& s) const { + return operator()(s.begin(), s.end()); + }; + + uuid operator()(char const*const s) const { + return operator()(s, s+std::strlen(s)); + } + + uuid operator()(wchar_t const*const s) const { + return operator()(s, s+std::wcslen(s)); + } + + template <typename CharIterator> + uuid operator()(CharIterator begin, CharIterator end) const + { + typedef typename std::iterator_traits<CharIterator>::value_type char_type; + + // check open brace + char_type c = get_next_char(begin, end); + bool has_open_brace = is_open_brace(c); + char_type open_brace_char = c; + if (has_open_brace) { + c = get_next_char(begin, end); + } + + bool has_dashes = false; + + uuid u; + int i=0; + for (uuid::iterator it_byte=u.begin(); it_byte!=u.end(); ++it_byte, ++i) { + if (it_byte != u.begin()) { + c = get_next_char(begin, end); + } + + if (i == 4) { + has_dashes = is_dash(c); + if (has_dashes) { + c = get_next_char(begin, end); + } + } + + if (has_dashes) { + if (i == 6 || i == 8 || i == 10) { + if (is_dash(c)) { + c = get_next_char(begin, end); + } else { + throw_invalid(); + } + } + } + + *it_byte = get_value(c); + + c = get_next_char(begin, end); + *it_byte <<= 4; + *it_byte |= get_value(c); + } + + // check close brace + if (has_open_brace) { + c = get_next_char(begin, end); + check_close_brace(c, open_brace_char); + } + + return u; + } + +private: + template <typename CharIterator> + typename std::iterator_traits<CharIterator>::value_type + get_next_char(CharIterator& begin, CharIterator end) const { + if (begin == end) { + throw_invalid(); + } + return *begin++; + } + + unsigned char get_value(char c) const { + static char const*const digits_begin = "0123456789abcdefABCDEF"; + static char const*const digits_end = digits_begin + 22; + + static unsigned char const values[] = + { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,10,11,12,13,14,15 + , static_cast<unsigned char>(-1) }; + + char const* d = std::find(digits_begin, digits_end, c); + return values[d - digits_begin]; + } + + unsigned char get_value(wchar_t c) const { + static wchar_t const*const digits_begin = L"0123456789abcdefABCDEF"; + static wchar_t const*const digits_end = digits_begin + 22; + + static unsigned char const values[] = + { 0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,10,11,12,13,14,15 + , static_cast<unsigned char>(-1) }; + + wchar_t const* d = std::find(digits_begin, digits_end, c); + return values[d - digits_begin]; + } + + bool is_dash(char c) const { + return c == '-'; + } + + bool is_dash(wchar_t c) const { + return c == L'-'; + } + + // return closing brace + bool is_open_brace(char c) const { + return (c == '{'); + } + + bool is_open_brace(wchar_t c) const { + return (c == L'{'); + } + + void check_close_brace(char c, char open_brace) const { + if (open_brace == '{' && c == '}') { + //great + } else { + throw_invalid(); + } + } + + void check_close_brace(wchar_t c, wchar_t open_brace) const { + if (open_brace == L'{' && c == L'}') { + // great + } else { + throw_invalid(); + } + } + + void throw_invalid() const { + throw std::runtime_error("invalid uuid string"); + } +}; + +}} // namespace boost::uuids + +#endif //BOOST_UUID_STRING_GENERATOR_HPP + diff --git a/3rdParty/Boost/src/boost/uuid/uuid.hpp b/3rdParty/Boost/src/boost/uuid/uuid.hpp new file mode 100644 index 0000000..ceebd4d --- /dev/null +++ b/3rdParty/Boost/src/boost/uuid/uuid.hpp @@ -0,0 +1,218 @@ +// Boost uuid.hpp header file ----------------------------------------------// + +// Copyright 2006 Andy Tompkins. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Revision History +// 06 Feb 2006 - Initial Revision +// 09 Nov 2006 - fixed variant and version bits for v4 guids +// 13 Nov 2006 - added serialization +// 17 Nov 2006 - added name-based guid creation +// 20 Nov 2006 - add fixes for gcc (from Tim Blechmann) +// 07 Mar 2007 - converted to header only +// 10 May 2007 - removed need for Boost.Thread +// - added better seed - thanks Peter Dimov +// - removed null() +// - replaced byte_count() and output_bytes() with size() and begin() and end() +// 11 May 2007 - fixed guid(ByteInputIterator first, ByteInputIterator last) +// - optimized operator>> +// 14 May 2007 - converted from guid to uuid +// 29 May 2007 - uses new implementation of sha1 +// 01 Jun 2007 - removed using namespace directives +// 09 Nov 2007 - moved implementation to uuid.ipp file +// 12 Nov 2007 - moved serialize code to uuid_serialize.hpp file +// 25 Feb 2008 - moved to namespace boost::uuids +// 19 Mar 2009 - changed to a POD, reorganized files +// 28 Nov 2009 - disabled deprecated warnings for MSVC +// 30 Nov 2009 - used BOOST_STATIC_CONSTANT +// 02 Dec 2009 - removed BOOST_STATIC_CONSTANT - not all compilers like it + +#ifndef BOOST_UUID_HPP +#define BOOST_UUID_HPP + +#include <boost/config.hpp> +#include <stddef.h> +#include <boost/cstdint.hpp> +#include <algorithm> +#include <boost/config.hpp> // for static assert +#include <boost/mpl/bool.hpp> +#include <boost/type_traits/is_pod.hpp> + +#if defined(_MSC_VER) +#pragma warning(push) // Save warning settings. +#pragma warning(disable : 4996) // Disable deprecated std::swap_ranges, std::equal +#endif + +#ifdef BOOST_NO_STDC_NAMESPACE +namespace std { + using ::size_t; + using ::ptrdiff_t; +} //namespace std +#endif //BOOST_NO_STDC_NAMESPACE + +namespace boost { +namespace uuids { + +struct uuid +{ +public: + typedef uint8_t value_type; + typedef uint8_t& reference; + typedef uint8_t const& const_reference; + typedef uint8_t* iterator; + typedef uint8_t const* const_iterator; + typedef std::size_t size_type; + typedef std::ptrdiff_t difference_type; + + // This does not work on some compilers + // They seem to want the variable definec in + // a cpp file + //BOOST_STATIC_CONSTANT(size_type, static_size = 16); + static size_type static_size() { return 16; } + +public: + iterator begin() { return data; } /* throw() */ + const_iterator begin() const { return data; } /* throw() */ + iterator end() { return data+size(); } /* throw() */ + const_iterator end() const { return data+size(); } /* throw() */ + + size_type size() const { return static_size(); } /* throw() */ + + bool is_nil() const /* throw() */ + { + for(size_t i=0; i<static_size(); i++) { + if (data[i] != 0U) { + return false; + } + } + return true; + } + + enum variant_type + { + variant_ncs, // NCS backward compatibility + variant_rfc_4122, // defined in RFC 4122 document + variant_microsoft, // Microsoft Corporation backward compatibility + variant_future // future definition + }; + variant_type variant() const /* throw() */ + { + // variant is stored in octet 7 + // which is index 8, since indexes count backwards + unsigned char octet7 = data[8]; // octet 7 is array index 8 + if ( (octet7 & 0x80) == 0x00 ) { // 0b0xxxxxxx + return variant_ncs; + } else if ( (octet7 & 0xC0) == 0x80 ) { // 0b10xxxxxx + return variant_rfc_4122; + } else if ( (octet7 & 0xE0) == 0xC0 ) { // 0b110xxxxx + return variant_microsoft; + } else { + //assert( (octet7 & 0xE0) == 0xE0 ) // 0b111xxxx + return variant_future; + } + } + + enum version_type + { + version_unknown = -1, + version_time_based = 1, + version_dce_security = 2, + version_name_based_md5 = 3, + version_random_number_based = 4, + version_name_based_sha1 = 5 + }; + version_type version() const /* throw() */ + { + //version is stored in octet 9 + // which is index 6, since indexes count backwards + unsigned char octet9 = data[6]; + if ( (octet9 & 0xF0) == 0x10 ) { + return version_time_based; + } else if ( (octet9 & 0xF0) == 0x20 ) { + return version_dce_security; + } else if ( (octet9 & 0xF0) == 0x30 ) { + return version_name_based_md5; + } else if ( (octet9 & 0xF0) == 0x40 ) { + return version_random_number_based; + } else if ( (octet9 & 0xF0) == 0x50 ) { + return version_name_based_sha1; + } else { + return version_unknown; + } + } + + // note: linear complexity + void swap(uuid& rhs) /* throw() */ + { + std::swap_ranges(begin(), end(), rhs.begin()); + } + +public: + // or should it be array<uint8_t, 16> + uint8_t data[16]; +}; + +inline bool operator==(uuid const& lhs, uuid const& rhs) /* throw() */ +{ + return std::equal(lhs.begin(), lhs.end(), rhs.begin()); +} + +inline bool operator!=(uuid const& lhs, uuid const& rhs) /* throw() */ +{ + return !(lhs == rhs); +} + +inline bool operator<(uuid const& lhs, uuid const& rhs) /* throw() */ +{ + return std::lexicographical_compare(lhs.begin(), lhs.end(), rhs.begin(), rhs.end()); +} + +inline bool operator>(uuid const& lhs, uuid const& rhs) /* throw() */ +{ + return rhs < lhs; +} +inline bool operator<=(uuid const& lhs, uuid const& rhs) /* throw() */ +{ + return !(rhs < lhs); +} + +inline bool operator>=(uuid const& lhs, uuid const& rhs) /* throw() */ +{ + return !(lhs < rhs); +} + +inline void swap(uuid& lhs, uuid& rhs) /* throw() */ +{ + lhs.swap(rhs); +} + +// This is equivalent to boost::hash_range(u.begin(), u.end()); +inline std::size_t hash_value(uuid const& u) /* throw() */ +{ + std::size_t seed = 0; + for(uuid::const_iterator i=u.begin(); i != u.end(); ++i) + { + seed ^= static_cast<std::size_t>(*i) + 0x9e3779b9 + (seed << 6) + (seed >> 2); + } + + return seed; +} + +}} //namespace boost::uuids + +// type traits specializations +namespace boost { + +template <> +struct is_pod<uuids::uuid> : mpl::true_ +{}; + +} // namespace boost + +#if defined(_MSC_VER) +#pragma warning(pop) // Restore warnings to previous state. +#endif + +#endif // BOOST_UUID_HPP diff --git a/3rdParty/Boost/src/boost/uuid/uuid_generators.hpp b/3rdParty/Boost/src/boost/uuid/uuid_generators.hpp new file mode 100644 index 0000000..29d39cc --- /dev/null +++ b/3rdParty/Boost/src/boost/uuid/uuid_generators.hpp @@ -0,0 +1,19 @@ +// Boost uuid_generators.hpp header file ----------------------------------------------// + +// Copyright 2006 Andy Tompkins. +// Distributed under the Boost Software License, Version 1.0. (See +// accompanying file LICENSE_1_0.txt or copy at +// http://www.boost.org/LICENSE_1_0.txt) + +// Revision History +// 06 Feb 2006 - Initial Revision + +#ifndef BOOST_UUID_GENERATORS_HPP +#define BOOST_UUID_GENERATORS_HPP + +#include <boost/uuid/nil_generator.hpp> +#include <boost/uuid/string_generator.hpp> +#include <boost/uuid/name_generator.hpp> +#include <boost/uuid/random_generator.hpp> + +#endif //BOOST_UUID_GENERATORS_HPP diff --git a/3rdParty/Boost/update.sh b/3rdParty/Boost/update.sh index bb5715c..c51bf1f 100755 --- a/3rdParty/Boost/update.sh +++ b/3rdParty/Boost/update.sh @@ -24,7 +24,8 @@ fi program_options.hpp \ thread.hpp \ asio.hpp \ - uuid.hpp \ + uuid/uuid.hpp \ + uuid/uuid_generators.hpp \ regex.hpp \ $TARGET_DIR diff --git a/Swiften/Client/ClientSession.cpp b/Swiften/Client/ClientSession.cpp index e90d325..7fdb8ac 100644 --- a/Swiften/Client/ClientSession.cpp +++ b/Swiften/Client/ClientSession.cpp @@ -7,6 +7,9 @@ #include "Swiften/Client/ClientSession.h" #include <boost/bind.hpp> +#include <boost/uuid/uuid.hpp> +#include <boost/uuid/uuid_io.hpp> +#include <boost/uuid/uuid_generators.hpp> #include "Swiften/Elements/ProtocolHeader.h" #include "Swiften/Elements/StreamFeatures.h" @@ -98,7 +101,9 @@ void ClientSession::handleElement(boost::shared_ptr<Element> element) { } else if (streamFeatures->hasAuthenticationMechanism("SCRAM-SHA-1")) { // FIXME: Use a real nonce - authenticator = new SCRAMSHA1ClientAuthenticator("ClientNonce"); + std::ostringstream s; + s << boost::uuids::random_generator()(); + authenticator = new SCRAMSHA1ClientAuthenticator(s.str()); state = WaitingForCredentials; onNeedCredentials(); } |