From 9b4f54c826ffa4f94efa866068c9d6ecdfb4b424 Mon Sep 17 00:00:00 2001 From: Jacek Antonelli Date: Fri, 15 Aug 2008 23:44:48 -0500 Subject: Second Life viewer sources 1.13.2.15 --- linden/indra/llmath/llrand.cpp | 59 +++++++---------- linden/indra/llmath/llrand.h | 134 +++++++++++++++++++++++++-------------- linden/indra/llmath/lluuid.cpp | 75 ++++++++++++++++++---- linden/indra/llmath/llvolume.cpp | 24 +++++-- 4 files changed, 191 insertions(+), 101 deletions(-) (limited to 'linden/indra/llmath') diff --git a/linden/indra/llmath/llrand.cpp b/linden/indra/llmath/llrand.cpp index 38e0639..4c214c4 100644 --- a/linden/indra/llmath/llrand.cpp +++ b/linden/indra/llmath/llrand.cpp @@ -1,6 +1,6 @@ /** * @file llrand.cpp - * @brief a few useful math functions. + * @brief Global random generator. * * Copyright (c) 2000-2007, Linden Research, Inc. * @@ -30,45 +30,34 @@ #include "llrand.h" #include "lluuid.h" -/* Put this back if you re-enabled slamFPCW -#if LL_WINDOWS -#include -#else -#include -#endif -*/ +static LLRandLagFib2281 gRandomGenerator(LLUUID::getRandomSeed()); -void slamFPCW( void ) +S32 ll_rand() { -/* -#if LL_WINDOWS - // for Intel based CPUs, slam the FP control word directly - WORD wTemp, wSave; - - __asm fstcw wSave - if ( (wSave & 0x300) // Not single mode - ||(0x3f != (wSave & 0x3f)) // Exceptions enabled - ||(wSave & 0xC00)) // Not round to nearest mode - { - __asm - { - mov ax, wSave - and ax, not 300h ;; single mode - or ax, 3fh ;; disable all exceptions - and ax, not 0xC00 ;; round to nearest mode - mov wTemp, ax - fldcw wTemp - } - } -#endif -*/ + return (S32)(gRandomGenerator() * RAND_MAX); } -LLRand gLindenLabRandomNumber(LLUUID::getRandomSeed()); +S32 ll_rand(S32 val) +{ + return (S32)(gRandomGenerator() * val); +} + +F32 ll_frand() +{ + return (F32)gRandomGenerator(); +} -F32 frand(F32 val) +F32 ll_frand(F32 val) { -// return (val * (F32)rand()/(F32)RAND_MAX); - return gLindenLabRandomNumber.llfrand(val); + return (F32)gRandomGenerator() * val; } +F64 ll_drand() +{ + return gRandomGenerator(); +} + +F64 ll_drand(F64 val) +{ + return gRandomGenerator() * val; +} diff --git a/linden/indra/llmath/llrand.h b/linden/indra/llmath/llrand.h index db9f353..47b5651 100644 --- a/linden/indra/llmath/llrand.h +++ b/linden/indra/llmath/llrand.h @@ -1,6 +1,6 @@ /** * @file llrand.h - * @brief Some useful math functions. + * @brief Information, functions, and typedefs for randomness. * * Copyright (c) 2000-2007, Linden Research, Inc. * @@ -28,61 +28,101 @@ #ifndef LL_LLRAND_H #define LL_LLRAND_H -// As long as you #include "llviewerprecompiledheaders.h", -// you can use "gLindenLabRandomNumber.llfrand( range );" which returns a -// random number F32 ranging from 0.0f to range. -// -Ventrella - Sept 30, 2005 +#include "boost/random/lagged_fibonacci.hpp" +#include "boost/random/mersenne_twister.hpp" -// Slams Intel processors into Single Precision FP mode -// (which is not any faster on modern hardware) -void slamFPCW( void ); - -class LLRand -{ -public: - LLRand(U32 seed) : mSeed(seed) {} - ~LLRand() {} - - void seed(U32 seed) { mSeed = seed; } +/** + * Use the boost random number generators if you want a stateful + * random numbers. If you want more random numbers, use the + * c-functions since they will generate faster/better randomness + * across the process. + * + * I tested some of the boost random engines, and picked a good double + * generator and a good integer generator. I also took some timings + * for them on linux using gcc 3.3.5. The harness also did some other + * fairly trivial operations to try to limit compiler optimizations, + * so these numbers are only good for relative comparisons. + * + * usec/inter algorithm + * 0.21 boost::minstd_rand0 + * 0.039 boost:lagged_fibonacci19937 + * 0.036 boost:lagged_fibonacci607 + * 0.44 boost::hellekalek1995 + * 0.44 boost::ecuyer1988 + * 0.042 boost::rand48 + * 0.043 boost::mt11213b + * 0.028 stdlib random() + * 0.05 stdlib lrand48() + * 0.034 stdlib rand() + * 0.020 the old & lame LLRand + */ - U32 llrand() - { - mSeed = U64L(1664525) * mSeed + U64L(1013904223); - return (U32)mSeed; - } +/** + *@brief Generate a float from [0, RAND_MAX). + */ +S32 ll_rand(); - U32 llrand(U32 val) - { - mSeed = U64L(1664525) * mSeed + U64L(1013904223); - return (U32)(mSeed) % val; - } +/** + *@brief Generate a float from [0, val). + */ +S32 ll_rand(S32 val); - // val is the maximum - F32 llfrand(F32 val) - { - const U32 FP_ONE = 0x3f800000; - const U32 FP_MASK = 0x007fffff; - U32 ir = llrand(); +/** + *@brief Generate a float from [0, 1.0). + */ +F32 ll_frand(); - ir = FP_ONE | (FP_MASK & ir); - - // generate random float - F32 fr = (*(F32 *)&ir); +/** + *@brief Generate a float from [0, val). + */ +F32 ll_frand(F32 val); - // correct to [0..1) - fr -= 1.f; +/** + *@brief Generate a double from [0, 1.0). + */ +F64 ll_drand(); - fr *= val; +/** + *@brief Generate a double from [0, val). + */ +F64 ll_drand(F64 val); - return fr; - } - -public: - U64 mSeed; -}; +/** + * @brief typedefs for good boost lagged fibonacci. + * @see boost::lagged_fibonacci + * + * These generators will quickly generate doubles. Note the memory + * requirements, because they are somewhat high. I chose the smallest + * one, and one comparable in speed but higher periodicity without + * outrageous memory requirements. + * To use: + * LLRandLagFib607 foo((U32)time(NULL)); + * double bar = foo(); + */ -F32 frand(F32 val); +typedef boost::lagged_fibonacci607 LLRandLagFib607; +/**< + * lengh of cycle: 2^32,000 + * memory: 607*sizeof(double) (about 5K) + */ -extern LLRand gLindenLabRandomNumber; +typedef boost::lagged_fibonacci2281 LLRandLagFib2281; +/**< + * lengh of cycle: 2^120,000 + * memory: 2281*sizeof(double) (about 17K) + */ +/** + * @breif typedefs for a good boost mersenne twister implementation. + * @see boost::mersenne_twister + * + * This fairly quickly generates U32 values + * To use: + * LLRandMT19937 foo((U32)time(NULL)); + * U32 bar = foo(); + * + * lengh of cycle: 2^19,937-1 + * memory: about 2496 bytes + */ +typedef boost::mt11213b LLRandMT19937; #endif diff --git a/linden/indra/llmath/lluuid.cpp b/linden/indra/llmath/lluuid.cpp index 216dac9..3fb31a6 100644 --- a/linden/indra/llmath/lluuid.cpp +++ b/linden/indra/llmath/lluuid.cpp @@ -110,6 +110,40 @@ unsigned int decode( char const * fiveChars ) throw( bad_input_data ) } */ +#define LL_USE_JANKY_RANDOM_NUMBER_GENERATOR 0 +#if LL_USE_JANKY_RANDOM_NUMBER_GENERATOR +/** + * @brief a global for + */ +static U64 sJankyRandomSeed(LLUUID::getRandomSeed()); + +/** + * @brief generate a random U32. + */ +U32 janky_fast_random_bytes() +{ + sJankyRandomSeed = U64L(1664525) * sJankyRandomSeed + U64L(1013904223); + return (U32)sJankyRandomSeed; +} + +/** + * @brief generate a random U32 from [0, val) + */ +U32 janky_fast_random_byes_range(U32 val) +{ + sJankyRandomSeed = U64L(1664525) * sJankyRandomSeed + U64L(1013904223); + return (U32)(sJankyRandomSeed) % val; +} + +/** + * @brief generate a random U32 from [0, val) + */ +U32 janky_fast_random_seeded_bytes(U32 seed, U32 val) +{ + seed = U64L(1664525) * (U64)(seed) + U64L(1013904223); + return (U32)(seed) % val; +} +#endif // Common to all UUID implementations void LLUUID::toString(char *out) const @@ -395,8 +429,16 @@ static void get_random_bytes(void *buf, int nbytes) int i; char *cp = (char *) buf; + // *NOTE: If we are not using the janky generator ll_rand() + // generates at least 3 good bytes of data since it is 0 to + // RAND_MAX. This could be made more efficient by copying all the + // bytes. for (i=0; i < nbytes; i++) - *cp++ = gLindenLabRandomNumber.llrand() & 0xFF; +#if LL_USE_JANKY_RANDOM_NUMBER_GENERATOR + *cp++ = janky_fast_random_bytes() & 0xFF; +#else + *cp++ = ll_rand() & 0xFF; +#endif return; } @@ -738,18 +780,18 @@ void LLUUID::getCurrentTime(uuid_time_t *timestamp) void LLUUID::generate() { - // Create a UUID. - - - uuid_time_t timestamp; + // Create a UUID. + uuid_time_t timestamp; - static unsigned char node_id[6]; - static int has_init = 0; + static unsigned char node_id[6]; + static int has_init = 0; - // Create a UUID. - static uuid_time_t time_last = {0,0}; - static U16 clock_seq = 0; - static LLRand random_generator(0); // dummy seed. reset it below + // Create a UUID. + static uuid_time_t time_last = {0,0}; + static U16 clock_seq = 0; +#if LL_USE_JANKY_RANDOM_NUMBER_GENERATOR + static U32 seed = 0L; // dummy seed. reset it below +#endif if (!has_init) { if (getNodeID(node_id) <= 0) @@ -764,8 +806,15 @@ void LLUUID::generate() } getCurrentTime(&time_last); - random_generator.seed(time_last.low); - clock_seq = (U16) random_generator.llrand(65536); +#if LL_USE_JANKY_RANDOM_NUMBER_GENERATOR + seed = time_last.low; +#endif + +#if LL_USE_JANKY_RANDOM_NUMBER_GENERATOR + clock_seq = (U16)janky_fast_random_seeded_bytes(seed, 65536); +#else + clock_seq = (U16)ll_rand(65536); +#endif has_init = 1; } diff --git a/linden/indra/llmath/llvolume.cpp b/linden/indra/llmath/llvolume.cpp index 14d4cdf..c527e85 100644 --- a/linden/indra/llmath/llvolume.cpp +++ b/linden/indra/llmath/llvolume.cpp @@ -725,6 +725,8 @@ BOOL LLProfileParams::importFile(FILE *fp) { const S32 BUFSIZE = 16384; char buffer[BUFSIZE]; + // *NOTE: changing the size or type of these buffers will require + // changing the sscanf below. char keyword[256]; char valuestr[256]; keyword[0] = 0; @@ -735,7 +737,7 @@ BOOL LLProfileParams::importFile(FILE *fp) while (!feof(fp)) { fgets(buffer, BUFSIZE, fp); - sscanf(buffer, " %s %s", keyword, valuestr); + sscanf(buffer, " %255s %255s", keyword, valuestr); if (!keyword) { continue; @@ -795,6 +797,8 @@ BOOL LLProfileParams::importLegacyStream(std::istream& input_stream) { const S32 BUFSIZE = 16384; char buffer[BUFSIZE]; + // *NOTE: changing the size or type of these buffers will require + // changing the sscanf below. char keyword[256]; char valuestr[256]; keyword[0] = 0; @@ -805,7 +809,7 @@ BOOL LLProfileParams::importLegacyStream(std::istream& input_stream) while (input_stream.good()) { input_stream.getline(buffer, BUFSIZE); - sscanf(buffer, " %s %s", keyword, valuestr); + sscanf(buffer, " %255s %255s", keyword, valuestr); if (!keyword) { continue; @@ -1215,6 +1219,8 @@ BOOL LLPathParams::importFile(FILE *fp) { const S32 BUFSIZE = 16384; char buffer[BUFSIZE]; + // *NOTE: changing the size or type of these buffers will require + // changing the sscanf below. char keyword[256]; char valuestr[256]; keyword[0] = 0; @@ -1227,7 +1233,7 @@ BOOL LLPathParams::importFile(FILE *fp) while (!feof(fp)) { fgets(buffer, BUFSIZE, fp); - sscanf(buffer, " %s %s", keyword, valuestr); + sscanf(buffer, " %255s %255s", keyword, valuestr); if (!keyword) { continue; @@ -1354,6 +1360,8 @@ BOOL LLPathParams::importLegacyStream(std::istream& input_stream) { const S32 BUFSIZE = 16384; char buffer[BUFSIZE]; + // *NOTE: changing the size or type of these buffers will require + // changing the sscanf below. char keyword[256]; char valuestr[256]; keyword[0] = 0; @@ -1366,7 +1374,7 @@ BOOL LLPathParams::importLegacyStream(std::istream& input_stream) while (input_stream.good()) { input_stream.getline(buffer, BUFSIZE); - sscanf(buffer, " %s %s", keyword, valuestr); + sscanf(buffer, " %255s %255s", keyword, valuestr); if (!keyword) { continue; @@ -3340,13 +3348,15 @@ BOOL LLVolumeParams::importFile(FILE *fp) //llinfos << "importing volume" << llendl; const S32 BUFSIZE = 16384; char buffer[BUFSIZE]; + // *NOTE: changing the size or type of this buffer will require + // changing the sscanf below. char keyword[256]; keyword[0] = 0; while (!feof(fp)) { fgets(buffer, BUFSIZE, fp); - sscanf(buffer, " %s", keyword); + sscanf(buffer, " %255s", keyword); if (!keyword) { continue; @@ -3391,6 +3401,8 @@ BOOL LLVolumeParams::importLegacyStream(std::istream& input_stream) { //llinfos << "importing volume" << llendl; const S32 BUFSIZE = 16384; + // *NOTE: changing the size or type of this buffer will require + // changing the sscanf below. char buffer[BUFSIZE]; char keyword[256]; keyword[0] = 0; @@ -3398,7 +3410,7 @@ BOOL LLVolumeParams::importLegacyStream(std::istream& input_stream) while (input_stream.good()) { input_stream.getline(buffer, BUFSIZE); - sscanf(buffer, " %s", keyword); + sscanf(buffer, " %255s", keyword); if (!keyword) { continue; -- cgit v1.1