/*****************************************************************************
 * $LastChangedDate: 2011-04-23 21:07:07 -0400 (Sat, 23 Apr 2011) $
 * @file
 * @author  Jim E. Brooks  http://www.palomino3d.org
 * @brief   Test of random functions.
 * @remarks [2009/12] This test was revised for the rewritten Random class
 *          that contains its own random functions so it should work
 *          identically on all systems (with the same CPU register size).
 *//*
 * LEGAL:   COPYRIGHT (C) 2005 JIM E. BROOKS
 *          THIS SOURCE CODE IS RELEASED UNDER THE TERMS
 *          OF THE GNU GENERAL PUBLIC LICENSE VERSION 2 (GPL 2).
 *****************************************************************************/

#define TESTING 1
#include "test.hh"
#include "base/module.hh"
#include "base/types.hh"
#include "base/random.hh"
using namespace base;

const uint TEST_RANDOM_LOOPS          = 8 * 1000 * 1000;
const uint TEST_RANDOMNESS_TABLE_SIZE = 50000;
const fp   TEST_RANDOM_FP_MARGIN      = 0.001f;  // margin of error

#define TEST_RANDOM_SEED_VAR   (Random::random_ui_real())   // if seed can vary
#define TEST_RANDOM_SEED_CONST (0xabcd1234)                 // --DO NOT CHANGE--

// Use this function so that the seed is printed in case of error.
// Some seeds that are passed are really random themselves.
void
TEST_RANDOMIZE( const uint seed )
{
    CDEBUG << std::hex <<"Testing with seed " << seed << std::endl;
    CDEBUG << std::dec;
    Random::randomize( seed );
}

/*****************************************************************************
 * Catch if random_f(range) is returning an out-of-range random fp number.
 *****************************************************************************/
static inline
bool
TEST_RANDOM_CHECK_FP_RANGE( const fp r, const fp range )
{
    if ( (r + TEST_RANDOM_FP_MARGIN < 0.0f)
      or (r - TEST_RANDOM_FP_MARGIN > range) )
    {
        CERROR << "ERROR: random_f(range) went out-of-range" << std::endl;
        CERROR << "r=" << r << " range=" << range << std::endl;
        return false;
    }
    else
    {
        return true;
    }
}

/*****************************************************************************
 * Test random functions (non-range).
 *****************************************************************************/
bool
TestRandomBasic( void )
{
    CDEBUG << "Testing random_ui(void) and random_f(void)" << std::endl;

    TEST_RANDOMIZE( TEST_RANDOM_SEED_VAR );

    for ( uint i = 0; i < TEST_RANDOM_LOOPS; ++i )
    {
        if ( Random::random_ui() > BASE_RANDOM_MAX )
            return Fail();

        if ( Random::random_f() > 1.0 )
            return Fail();
    }

    return true;
}

/*****************************************************************************
 * Test random_ui(range).
 * The goal is to ensure no random value is returned that is greater than
 * the specified range.  Otherwise, since random values are sometimes
 * used as array indexs, the error could cause out-of-bound bugs
 *****************************************************************************/
bool
TestRandomRangeUI( const uint range )
{
    CDEBUG << "Testing random_ui(" << range << ")." << std::endl;

    // random_ui(range) won't accept range > BASE_RANDOM_MAX.
    if ( range >= BASE_RANDOM_MAX )
    {
        CDEBUG << "range > BASE_RANDOM_MAX (ok)" << std::endl;
        return true;
    }

    TEST_RANDOMIZE( TEST_RANDOM_SEED_VAR );

    for ( uint i = 0; i < TEST_RANDOM_LOOPS; ++i )
    {
        const uint r = Random::random_ui( range );
        if ( r >= range )   // equal to range is wrong too because
        {                   // of using random indexs for tables
            CERROR << "ERROR: random_ui() >= range" << std::endl;
            CERROR << "r=" << r << " range=" << range << std::endl;
            return Fail();
        }
    }

    return true;
}

/*****************************************************************************
 * FP variant of TestRandomRangeUI().
 *****************************************************************************/
bool
TestRandomRangeFP( const fp range )
{
    CDEBUG << "Testing random_f(" << range << ")." << std::endl;

    // Underlying random_ui(range) won't accept range > BASE_RANDOM_MAX.
    if ( range >= BASE_RANDOM_MAX )
    {
        CDEBUG << "range > BASE_RANDOM_MAX (ok)" << std::endl;
        return true;
    }

    TEST_RANDOMIZE( TEST_RANDOM_SEED_VAR );

    for ( uint i = 0; i < TEST_RANDOM_LOOPS; ++i )
    {
        const fp r = Random::random_f( range );
        if ( not TEST_RANDOM_CHECK_FP_RANGE( r, range ) )
            return Fail();
    }

    return true;
}

/*****************************************************************************
 * Test that some low and some high values are generated.
 *****************************************************************************/
bool
TestRandomExtremes( const uint range )
{
    CDEBUG << "Testing random numbers at low/high extremes at range = " << range << std::endl;

    // Use the same seed.
    TEST_RANDOMIZE( TEST_RANDOM_SEED_CONST );

    uint lowExtremes = 0;
    uint highExtremes = 0;
  //const uint limit = 0xffffffff;          // wrong, random function may not (and does not)
    const uint limit = BASE_RANDOM_MAX;     // generate for full 32-bit range!

    for ( uint i = 0; i < TEST_RANDOM_LOOPS; ++i )
    {
        const uint r = Random::random_ui( limit );
        if ( r > limit - range )
            ++highExtremes;
        else if ( r < range )
            ++lowExtremes;
    }

    CDEBUG << "Low extremes = " << lowExtremes << " high extremes = " << highExtremes << std::endl;

    if ( lowExtremes == 0 )
        return Fail();

    if ( highExtremes == 0 )
        return Fail();

    return true;
}

/*****************************************************************************
 * Test that distribution of random numbers is uniforms.
 * Uses random_f().
 *****************************************************************************/
bool
TestRandomUniformDistribution( void )
{
    CDEBUG << "Testing random_f()." << std::endl;

    TEST_RANDOMIZE( TEST_RANDOM_SEED_VAR );

    fp avg = 0.0f;
    for ( uint i = 0; i < TEST_RANDOM_LOOPS; ++i )
    {
        const fp r = Random::random_f();
        avg += r;

        // Along the way, catch out-of-range values.
        if ( not TEST_RANDOM_CHECK_FP_RANGE( r, 1.0f ) )
            return Fail();
    }
    avg /= TEST_RANDOM_LOOPS;
    CERROR << "Average random fp = " << avg << std::endl;    

    // Average should be 0.5 if random distribution is uniform.
    if ( (avg < 0.475f)
      or (avg > 0.525f) )
    {
        return Fail();
    }
    
    return true;
}

/*****************************************************************************
 * Test randomness (test distribution of random numbers).
 * Will catch if sudo-random generator doesn't work or works poorly.
 * Written in 2009/12 for the self-contained Random class
 * (which no longer uses the random functions of standard libraries).
 *****************************************************************************/
bool
TestRandomness( void )
{
    CDEBUG << "Testing randomness." << std::endl;

    // Use the same seed.
    TEST_RANDOMIZE( TEST_RANDOM_SEED_CONST );

    const uint VAL = 0xaabbccdd;

    // Test randomness by randomly picking an index into a table.
    // Enough loops should randomly pick all indexs.
    PERSISTENT uint numbers[TEST_RANDOMNESS_TABLE_SIZE];  // zeros
    uint changeCount = 0;
    for ( uint i = 0; i < 10 * MILLION; ++i )
    {
        const uint r = Random::random_ui( TEST_RANDOMNESS_TABLE_SIZE );
        if ( EX( r < TEST_RANDOMNESS_TABLE_SIZE ) )
        {
            // Stop when all the elements have been changed.
            if ( numbers[r] != VAL )
            {
                ++changeCount;
                numbers[r] = VAL;
                if ( changeCount == TEST_RANDOMNESS_TABLE_SIZE )
                {
                    CDEBUG << "Changed all " << TEST_RANDOMNESS_TABLE_SIZE << " elements of table by randomness using " << i << " loops (ok)." << std::endl;
                    break;
                }
            }
        }
        else
        {
            return Fail();
        }
    }

    // Check if any element was not changed.
    for ( uint i = 0; i < TEST_RANDOMNESS_TABLE_SIZE; ++i )
    {
        if ( numbers[i] != VAL )
        {
            CERROR << "ERROR: TestRandomness() table element not assigned" << std::endl;
            return Fail();
        }
    }

    return true;
}

/*****************************************************************************
 * Test that same sequence of random numbers are generated.
 * Written in 2009/12 for the self-contained Random class
 * (which no longer uses the random functions of standard libraries).
 *****************************************************************************/
bool
TestSameRandomSequence( void )
{
    CDEBUG << "Testing that the self-contained Random class produces the same random sequence." << std::endl;

    // Use the same seed.
    TEST_RANDOMIZE( TEST_RANDOM_SEED_CONST );

    // Now, the idea is that, since Random::random_ui() is supposed to use only 32-bit integers,
    // if by mistake it is compiled 64-bit, this this 64-bit checksum will catch that mistake.
    uint32 checksum32 = 0;
    uint64 checksum64 = 0;

    for ( uint i = 0; i < TEST_RANDOM_LOOPS; ++i )
    {
        const uint64 r = Random::random_ui();
        checksum32 += r;
        checksum64 += r;
    }

#define EXPECTED_CHECKSUM32 0xe0fc4b4aUL
#define EXPECTED_CHECKSUM64 0x1e8555e0fc4b4aULL

    CDEBUG << std::hex << "Expected : checksum32 = 0x" << EXPECTED_CHECKSUM32
                       << " checksum64 = 0x" << EXPECTED_CHECKSUM64
           << std::dec << std::endl;

    CDEBUG << std::hex << "As tested: checksum32 = 0x" << checksum32
                       << " checksum64 = 0x" << checksum64
           << std::dec << std::endl;

    if ( checksum32 != EXPECTED_CHECKSUM32 )
        return Fail();

    if ( checksum64 != EXPECTED_CHECKSUM64 )
        return Fail();

    return true;
}

/*****************************************************************************
 * main.
 *****************************************************************************/
int main( int argc, char** argv )
{
     RUN_TEST( "random", TEST_ERROR_MODE_ABORT,
               TestRandomBasic()
           and TestRandomRangeUI( 1 )
           and TestRandomRangeUI( 2 )
           and TestRandomRangeUI( 10 )
           and TestRandomRangeUI( 50 )
           and TestRandomRangeUI( 100 )
           and TestRandomRangeUI( 1000 ) 
           and TestRandomRangeUI( 0x7fffffff )
           and TestRandomRangeUI( 0xf0000000 )
           and TestRandomRangeFP( 1.0f )
           and TestRandomRangeFP( 0.5f )
           and TestRandomRangeFP( 0.25f )
           and TestRandomRangeFP( 0.1f )
           and TestRandomRangeFP( 100.0f )
           and TestRandomRangeFP( 1000.0f )
           and TestRandomRangeFP( 1000000.0f )
           and TestRandomRangeFP( 10000000000.0f )
           and TestRandomExtremes(10000000)
           and TestRandomExtremes(1000000)
           and TestRandomExtremes(100000)
           and TestRandomExtremes(10000)
           and TestRandomExtremes(5000)
           and TestRandomUniformDistribution()
           and TestRandomness()
           and TestSameRandomSequence() )
}
