aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2006-04-23 23:19:49 +0000
committerAvatar Ciaran McCreesh <ciaran.mccreesh@googlemail.com> 2006-04-23 23:19:49 +0000
commit8a5169bde6d9de30945c22eb9b38bffccea98ea2 (patch)
tree3c3fd3651feb6d82660c5bb6206aff1249f80234
parent0b9bbf3669922d13cf15fedaaa4966e1bbdb473a (diff)
downloadpaludis-8a5169bde6d9de30945c22eb9b38bffccea98ea2.tar.gz
paludis-8a5169bde6d9de30945c22eb9b38bffccea98ea2.tar.xz
Don't use the c random number functions that have global state, use our own instead.
-rw-r--r--doc/doc_references.doxygen11
-rw-r--r--doc/doxygen.conf.in2
-rw-r--r--paludis/util/files.m42
-rw-r--r--paludis/util/random.cc14
-rw-r--r--paludis/util/random.hh29
-rw-r--r--paludis/util/random_TEST.cc113
6 files changed, 154 insertions, 17 deletions
diff --git a/doc/doc_references.doxygen b/doc/doc_references.doxygen
index 6cd4afa..2609f8d 100644
--- a/doc/doc_references.doxygen
+++ b/doc/doc_references.doxygen
@@ -5,8 +5,12 @@
\section ReferencesBooks Books
+\anchor AppCrypt
+<strong>AppCrypt</strong>: Applied Cryptography Second Edition / Bruce
+Schneier / Wiley / ISBN 0-471-11709-9
+
\anchor EffCpp
-<strong>EffCpp</strong>: Effective C++ Third Edition / Scott Meyer /
+<strong>EffCpp</strong>: Effective C++ Third Edition / Scott Meyers /
Addison-Wesley / ISBN 0-321-33487-6
\anchor EffSTL
@@ -22,6 +26,11 @@ Addison-Wesley / ISBN 0-201-63361-2
<strong>MCppD</strong>: Modern C++ Design: Generic Programming and Design
Patterns Applied / Andrei Alexandrescu / Addison-Wesley / ISBN 0-201-70431-5
+\anchor TaoCP2
+<strong>TaoCP2</strong>: The Art of Computer Programming, Volume 2:
+Seminumerical Algorithms, Third Edition / Donald E. Knuth / Addison-Wesley /
+ISBN 0-201-89684-2
+
\anchor TCppSL
<strong>TCppSL</strong>: The C++ Standard Library / Nicolai M. Josuttis /
Addison-Wesley / ISBN 0-201-37926-0
diff --git a/doc/doxygen.conf.in b/doc/doxygen.conf.in
index 91a4c39..763c551 100644
--- a/doc/doxygen.conf.in
+++ b/doc/doxygen.conf.in
@@ -452,7 +452,7 @@ WARN_LOGFILE =
# directories like "/usr/src/myproject". Separate the files or directories
# with spaces.
-INPUT = ../paludis ../paludis/args ../test ../doc ../src
+INPUT = ../paludis ../paludis/args ../paludis/util ../test ../doc ../src
# If the value of the INPUT tag contains directories, you can use the
# FILE_PATTERNS tag to specify one or more wildcard pattern (like *.cpp
diff --git a/paludis/util/files.m4 b/paludis/util/files.m4
index 947aadd..14ac79f 100644
--- a/paludis/util/files.m4
+++ b/paludis/util/files.m4
@@ -28,7 +28,7 @@ add(`log', `hh', `cc', `test')
add(`match_sequence', `hh', `cc', `test')
add(`private_implementation_pattern', `hh')
add(`pstream', `hh', `cc', `test')
-add(`random', `hh', `cc')
+add(`random', `hh', `cc', `test')
add(`save', `hh', `test')
add(`smart_record', `hh', `test')
add(`stringify', `hh', `test')
diff --git a/paludis/util/random.cc b/paludis/util/random.cc
index 0b026fe..4cb6b85 100644
--- a/paludis/util/random.cc
+++ b/paludis/util/random.cc
@@ -18,6 +18,7 @@
*/
#include "random.hh"
+#include <time.h>
/** \file
* Implementation for random.hh.
@@ -27,5 +28,16 @@
using namespace paludis;
-bool Random::done_srand(false);
+uint32_t Random::global_seed(0xdeadbeef ^ ::time(0));
+
+Random::Random(uint32_t seed) :
+ local_seed(seed)
+{
+}
+
+Random::Random() :
+ local_seed(global_seed ^ ((::time(0) >> 16) | (::time(0) << 16)))
+{
+ global_seed += local_seed;
+}
diff --git a/paludis/util/random.hh b/paludis/util/random.hh
index 547ef9f..6b278c2 100644
--- a/paludis/util/random.hh
+++ b/paludis/util/random.hh
@@ -21,35 +21,38 @@
#define PALUDIS_GUARD_PALUDIS_UTIL_RANDOM_HH 1
#include <cstdlib>
-#include <time.h>
+#include <inttypes.h>
namespace paludis
{
/**
- * A basic random number generator class.
+ * A basic random number generator class, which is not suitable for
+ * cryptography but is fast and reasonably pseudorandom.
*
- * See \ref TCppPL 22.7 for justification.
- *
- * \todo Don't use cstdlib functions here.
+ * See \ref TCppPL 22.7 for justification. See \ref TaoCP2 3.2.1 for the
+ * basic algorithm and \ref AppCrypt 16.1 for the choice of numbers.
*
* \ingroup grprandom
*/
class Random
{
private:
- static bool done_srand;
+ static uint32_t global_seed;
+ uint32_t local_seed;
+
+ static const uint32_t _a = 2416;
+ static const uint32_t _b = 374441;
+ static const uint32_t _m = 1771875;
public:
+ Random(uint32_t seed);
+ Random();
+
template <typename DiffType_>
DiffType_ operator() (DiffType_ max)
{
- if (! done_srand)
- {
- std::srand(time(0));
- done_srand = true;
- }
-
- double t(static_cast<double>(std::rand()) / static_cast<double>(RAND_MAX));
+ local_seed = (_a * local_seed + _b) % _m;
+ double t(static_cast<double>(local_seed) / static_cast<double>(_m));
return static_cast<DiffType_>(t * max);
}
};
diff --git a/paludis/util/random_TEST.cc b/paludis/util/random_TEST.cc
new file mode 100644
index 0000000..6dc2f4a
--- /dev/null
+++ b/paludis/util/random_TEST.cc
@@ -0,0 +1,113 @@
+/* vim: set sw=4 sts=4 et foldmethod=syntax : */
+
+/*
+ * Copyright (c) 2006 Ciaran McCreesh <ciaran.mccreesh@blueyonder.co.uk>
+ *
+ * This file is part of the Paludis package manager. Paludis is free software;
+ * you can redistribute it and/or modify it under the terms of the GNU General
+ * Public License version 2, as published by the Free Software Foundation.
+ *
+ * Paludis is distributed in the hope that it will be useful, but WITHOUT ANY
+ * WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS
+ * FOR A PARTICULAR PURPOSE. See the GNU General Public License for more
+ * details.
+ *
+ * You should have received a copy of the GNU General Public License along with
+ * this program; if not, write to the Free Software Foundation, Inc., 59 Temple
+ * Place, Suite 330, Boston, MA 02111-1307 USA
+ */
+
+#include "random.hh"
+#include <test/test_framework.hh>
+#include <test/test_runner.hh>
+#include <vector>
+#include <algorithm>
+
+/** \file
+ * Test cases for paludis::Random.
+ *
+ * \ingroup grptestcases
+ */
+
+using namespace paludis;
+using namespace test;
+
+namespace
+{
+ struct RandomUpTo
+ {
+ Random random;
+ unsigned max;
+
+ RandomUpTo(const Random & r, const unsigned m) :
+ random(r),
+ max(m)
+ {
+ }
+
+ int operator() ()
+ {
+ return random(max);
+ }
+ };
+
+ inline double square(double v)
+ {
+ return v * v;
+ }
+}
+
+namespace test_cases
+{
+ /**
+ * \test Test Random distibutions using counts.
+ *
+ * \ingroup grptestcases
+ */
+ struct RandomDistributionCountsTest : TestCase
+ {
+ RandomDistributionCountsTest() : TestCase("distribution (counts)") { }
+
+ void run()
+ {
+ std::vector<int> v;
+ v.reserve(10000);
+ std::generate_n(std::back_inserter(v), 10000, RandomUpTo(Random(), 10));
+
+ TEST_CHECK_EQUAL(0, *std::min_element(v.begin(), v.end()));
+ TEST_CHECK_EQUAL(9, *std::max_element(v.begin(), v.end()));
+ for (int i(0) ; i < 10 ; ++i)
+ {
+ TEST_CHECK(std::count(v.begin(), v.end(), i) > 1);
+ TEST_CHECK(std::count(v.begin(), v.end(), i) < 3000);
+ }
+ }
+ } test_random_counts;
+
+ /**
+ * \test Test Random distibutions using chi square.
+ *
+ * This is a chi square test, so it could theoretically fail
+ * occasionally. See \ref TaoCP2 3.3.1 for details.
+ */
+ struct RandomDistributionChiSquaredTest : TestCase
+ {
+ RandomDistributionChiSquaredTest() : TestCase("distribution (chi square)") { }
+
+ void run()
+ {
+ std::vector<int> v;
+ v.reserve(10000);
+ std::generate_n(std::back_inserter(v), 10000, RandomUpTo(Random(), 10));
+
+ double a(0);
+ for (int i(0) ; i <= 9 ; ++i)
+ a += (square(std::count(v.begin(), v.end(), i) - (10000 / 10)) / (10000 / 10));
+
+ TestMessageSuffix suffix("a=" + stringify(a), true);
+ TEST_CHECK(a >= 2.088);
+ TEST_CHECK(a <= 21.67);
+ }
+ } test_random_chi_square;
+}
+