diff 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 /3rdParty/Boost/src/boost/random/mersenne_twister.hpp | |
parent | c2cf7f0e59c7880a9ce979d8a45d97442c705110 (diff) | |
download | swift-contrib-4c58e9a2d266c23a2060edd08081bf86ebd1862c.zip swift-contrib-4c58e9a2d266c23a2060edd08081bf86ebd1862c.tar.bz2 |
Use UUIDs as nonce when authenticating with SCRAM-SHA-1.
Diffstat (limited to '3rdParty/Boost/src/boost/random/mersenne_twister.hpp')
-rw-r--r-- | 3rdParty/Boost/src/boost/random/mersenne_twister.hpp | 367 |
1 files changed, 367 insertions, 0 deletions
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 |