fsp/tests/randomcheck.c

#include "tweak.h"
#include <stdio.h>
#include <stdlib.h>
#include "my-string.h"
#include <math.h>

#define GROUPS 6
static int group[GROUPS];
static int bitcount[16];
static int rounds;
static int groups;
static int result;
#define MAX_WORST_ALLOWED 0.1f

/**
Tests how to get 16 bit unsigned short number
from long random(void) function without
losing randomness
*/

/* FSP classic algo */
static unsigned short classic (void)
{
  unsigned long k;

  k = random();
  k = k ^ (k >> 8) ^ (k >> 16) ^ (k << 8);

  return k;
}

/* get low bits from random result */
static unsigned short simple (void)
{
  return random();
}

/*
shift random() 15 times to get higher bits.
used in fsp beta 29 as production random code.
*/
static unsigned short simple15 (void)
{
  return ( random() >> 15 );
}

/* get high bits from random() result.

In most classic random implementations used in libc
highest bits have better randomness.

In modern random() generators there should be no difference.
*/
static unsigned short simple2 (void)
{
  /* we assume that our return value is 16 bits long
     and random() returns only positive long integers.
     Original code used >> 15
  */
  /* TODO: this needs to be checked on 64-bit systems because
     I am not sure if random returns 31 bits or 63 bits of
     randomness there.

     Current status:
     32-bit: 17 shifts
     64-bit: 49 shifts
  */
  return ( random() >> (SIZEOF_LONG*8 - 16 - 1) );
}

/* The following algorithm is recommended by Numerical Recipies: */
/* Best, but needs floating point division */
static unsigned short nr(void)
{
        unsigned short ulRandom = ((float)(0xffff)*rand()/(RAND_MAX+1.0f));
        return(ulRandom);
}

/* Skip lowest 8 bits */
static unsigned short skip8(void)
{
        long randomValue = random();
        return randomValue >> 8;
}

static void run_randomtest( unsigned short (*keygen)(void) )
{
    int i,j;
    unsigned short rnd;

    /* zero bitcount first */
    memset(bitcount, 0, sizeof(bitcount));

    for(i=0;i<rounds;i++)
    {
        rnd=keygen();

        for(j=0;j<16;j++)
        {
            if(rnd & 1)
                bitcount[j]++;
            rnd=rnd>>1;
        }
    }
}

static void print_bitcount(void)
{
    int i;
    float worst = 0;

    printf("Set ratio: ");

    for(i=0;i<16;i++)
    {
        float ratio;
        float delta;
        ratio=(float)bitcount[i]/rounds;
        delta = fabs(ratio-0.5f);
        if(delta > worst)
            worst=delta;
        printf("%.2f ", ratio);
    }
    printf("  Worst: %.4f\n", worst);
    if(worst>MAX_WORST_ALLOWED) result++;
}

static float worst_bitcount(void)
{
    int i;
    float worst = 0.0f;

    for(i=0;i<16;i++)
    {
        float ratio;
        float delta;
        ratio=(float)bitcount[i]/rounds;
        delta = fabs(ratio-0.5f);
        if(delta > worst)
            worst=delta;
    }
    return worst;
}

static void run_one(void)
{
    float worst[GROUPS];
    memset(worst, 0, sizeof(worst));

    run_randomtest(classic);
    worst[0] = worst_bitcount();

    run_randomtest(simple);
    worst[1] = worst_bitcount();

    run_randomtest(simple2);
    worst[2] = worst_bitcount();

    run_randomtest(nr);
    worst[3] = worst_bitcount();

    run_randomtest(skip8);
    worst[4] = worst_bitcount();

    run_randomtest(simple15);
    worst[5] = worst_bitcount();

    /* fimd the best algo */
    float minValue = worst[0];
    int minIndex = 0;

    for (int i = 1; i < GROUPS; i++)
    {
       if (worst[i] < minValue)
       {
          minValue = worst[i];
          minIndex = i;
       }
    }

    group[minIndex] += 1;
}

static void seed_rng(void)
{
#ifdef HAVE_SRANDOMDEV
    srandomdev();
#endif
}

int main(int argc,const char *argv[])
{
    /* 100k rounds by default */
    rounds=100000;
    /* 20 groups by default */
    groups=20;

    /* override counts from command line */
    if(argc>2)
    {
        groups=atoi(argv[2]);
    }
    if(argc>1)
    {
        rounds=atoi(argv[1]);
    }

    printf("Running %d groups of %d rounds.\n\n", groups, rounds);

    result=0;
    memset(group, 0, sizeof(group));

    if ( groups == 1 )
    {
        seed_rng();
        printf("Generator: classic\n");
        run_randomtest(classic);
        print_bitcount();

        printf("Generator: simple (low bits)\n");
        run_randomtest(simple);
        print_bitcount();

        printf("Generator: simple2 (high bits)\n");
        run_randomtest(simple2);
        print_bitcount();

        printf("Generator: simple15 (high bits legacy)\n");
        run_randomtest(simple15);
        print_bitcount();

        printf("Generator: Numerical Recipes\n");
        run_randomtest(nr);
        print_bitcount();

        printf("Generator: skip8\n");
        run_randomtest(skip8);
        print_bitcount();
    } else {
        int i;
        for (i=0; i< groups; i++)
        {
           seed_rng();
           run_one();
        }

        printf("Winning generators:\n\n");
        printf("Generator: classic %d\n", group[0]);
        printf("Generator: simple (low bits) %d\n", group[1]);
        printf("Generator: simple2 (high bits) %d\n", group[2]);
        printf("Generator: simple15 (shift by 15) %d\n", group[5]);
        printf("Generator: Numerical Recipes %d\n", group[3]);
        printf("Generator: skip8 (skip 8 lower bits) %d\n", group[4]);
    }

    return result;
}