Thread: Seeded/Seedless random number

Well just finished running the version that was using NULL on the seed under dieharder (results attached), while not perfect it does seem to pass roughly 50% of the tests which is good enough for now, especially as it is a seedless run. As stated before security software should be able to use this just fine, although I wouldn't trust it if it uses just this.

Incidentally I found a way to not bother remembering macros:

Code:

#define MCC___DEF(NAME) (NAME)
#define MCC__DEF(NAME) MCC___DEF(NAME)
#define MCC_DEF(NAME) \
	(MCC__DEF(__##NAME##__) | MCC__DEF(__##NAME)\
	| MCC__DEF(_##NAME##_) | MCC__DEF(_##NAME)\
	| MCC__DEF(NAME))
#define MCC____RND(V) (V ^ (V * (V << (V & 0xF))))
uint mcc____rnd() {
#if MCC_DEF(X86) | MCC_DEF(X86_64) | MCC_DEF(x86) | MCC_DEF(x86_64)
	uint a, b;
	asm volatile("rdtsc":"=a"(a),"=b"(b));
	return MCC____RND(a);
#else
	struct timespec ts;
	clock_gettime(CLOCK_REALTIME,&ts);
	return MCC____RND(ts.tv_nsec);
#endif
}

Edit: Because some peops will be curios...

Code:

gcc -ggdb -Wall -lpthread -DQUICKY_RND -o ./mcc_rnd_quicky.elf mcc_rnd.c
./mcc_rnd_quicky.elf
mcc___rnd() took 0 seconds and 198353 nanoseconds
rand_r() took 0 seconds and 116349 nanoseconds
Compilation finished successfully.

Code:

#define PER_LOOP 10000
int main() {
	struct timespec init, stop;
	uint seed = time(NULL), i;
	clock_gettime(CLOCK_REALTIME,&init);
	for ( i = 0; i < PER_LOOP; ++i ) {
		(void)mcc____rnd();
	}
	clock_gettime(CLOCK_REALTIME,&stop);
	printf( "mcc___rnd() took %lld seconds and %lld nanoseconds\n",
		(long long)(stop.tv_sec - init.tv_sec),
		(long long)(stop.tv_nsec - init.tv_nsec) );
	clock_gettime(CLOCK_REALTIME,&init);
	for ( i = 0; i < PER_LOOP; ++i ) {
		(void)rand_r(&seed);
	}
	clock_gettime(CLOCK_REALTIME,&stop);
	printf( "rand_r() took %lld seconds and %lld nanoseconds\n",
		(long long)(stop.tv_sec - init.tv_sec),
		(long long)(stop.tv_nsec - init.tv_nsec) );
	return 0;
}

Edit 2: I tried removing the loop out of curiosity, was surprised to get consistent results looking like this:

Code:

gcc -ggdb -Wall -lpthread -DQUICKY_RND -o ./mcc_rnd_quicky.elf mcc_rnd.c
mcc_rnd.c: In function ‘main’:
mcc_rnd.c:101:26: warning: unused variable ‘i’ [-Wunused-variable]
  101 |  uint seed = time(NULL), i;
      |                          ^
./mcc_rnd_quicky.elf
mcc___rnd() took 0 seconds and 182 nanoseconds
rand_r() took 0 seconds and 550 nanoseconds
Compilation finished successfully.

Originally Posted by awsdert

Isn't the point of a random number generator supposed to be ooh I dunno not fixed?

No, that's not necessarily the point: while "true randomness" typically cannot have sequences reproduced on demand other than by saving the sequences to replay them, there's statistical randomness and randomness that is unpredictable, and these don't require that the sequence cannot be repeated on demand given only a seed. If you're running a simulation, or as Hodor said, debugging, being able to repeat the pseudorandom sequence on demand is useful.

Originally Posted by awsdert

Nah its not that, I can read scripts easily enough since they're in nice simple lines but math symbols go all over the place and there are some I'm not even familiar with, I only got a B in my GCSEs and wasn't really interested in studying it in the last 14 odd years, but on that note do you have a good reference to look through for studying each symbol? (preferably list format with the name of each symbol next to them and a basic description, I can google from there once I know the name and find the description insufficient for learning about it)

Knuth gives pseudocode or code in the MIX or MMIX language (which both have assemblers... MIX or MMIX depends on what revision of his books you look at) or both. So volume 2 and the stuff about random numbers has lots of mathematics but lots of pseudocode as well (all the volumes do). The Mersenne twister algorithm, linked to above, even uses a LCG random number generator to set its initial state from a given seed and references Knuth. There's not really even much, if any, mathematics to understand (unless you want to). If I see code that uses some kind of weird unpublished random (or pseudo-random) number generator all sorts of alarm bells go off and I'd steer clear of it. I can understand the mathematics for most PRNGs but even if I can't (there are some that are just beyond my ability) I'd rather see code using algorithms written in peer-reviewed journals; especially if I need something that approaches anything useful for secure cryptography because I either don't have the ability to prove these things myself or I don't have the time.

Mersenne twister is fast but not as fast as your code or a LCG PRNG. Pretty close though and it has better randomness than rand() (side note: does the C standard specify what algorithm rand() must use?)

Edit: there was a PRNG algorithm published in Doctor Dobb's Journal in about 1995 based on the Fibonacci sequence that was good for CPUs at the time that didn't have FPUs. Its period was terrible but it was easy to implement in ASM and good enough for games. I can't find a reference to it but I don't think it was a "classical" LCG, although it might have been (can't say for sure because I cannot find the article)

Originally Posted by Hodor

does the C standard specify what algorithm rand() must use?

No, except that it does require a PRNG and imposes some minimum requirements on the PRNG like a minimum RAND_MAX.

I, erm, think I fixed the time based generator to be shall we say WAY more secure than before, I was experimenting hoping to get a few more passed and on my current attempt (dieharder is still running, at lagged sum tests right now) a LOT more were passing than I expected with the simple change I made (also change a few names because I found this method only works for counter based values, got a different one for seeds).
My current experimental code

Code:

#define MCC_RND(TICK) (((TICK) ^ ((TICK) * ((TICK) << ((TICK) & 0xF)))) + ((TICK) % 123))
#define MCC_RNG_SEED(SEED) (((SEED) * ((SEED) % 4321)) + ((SEED) % 12345))
#define MCC_RNG_(SEED) ((MCC_RNG_SEED(SEED) ^ (SEED)))
#define MCC_RNG(SEED) MCC_RND(MCC_RNG_(SEED))

#if 0//MCC_DEF(X86) | MCC_DEF(X86_64) | MCC_DEF(x86) | MCC_DEF(x86_64)
#define mcc_get_ticks(TS) \
	do { asm volatile("rdtsc":\
		"=" #TS ".tv_sec" (TS.tv_sec),\
		"=" #TS ".tv_nsec" (TS.tv_nsec));\
	} while (0)
#else
#define mcc_get_ticks(TS) clock_gettime(CLOCK_REALTIME,&TS);
#endif

#define mcc_random(V,TS) \
	do { mcc_init_seed(TS); \
	V = MCC_RND(TS.tv_nsec ^ V); } while (0)

uint mcc_rng() {
	struct timespec ts;
	mcc_get_ticks(ts);
	return MCC_RNG(ts.tv_nsec + (ulong)&ts);
}
uint mcc_rng_r( uint *seed ) {
	return (*seed = MCC_RNG(*seed));
}
long mcc_random_between( uint *seed, long min, long max ) {
	/* Initial random value */
	long val = (*seed = MCC_RNG( *seed ));
	if ( val < min ) return (min != 0) ? val % min : -(val & 1);
	if ( val > max ) return (max != 0) ? val % max : (val & 1);
	return val;
}

Edit: Gonna go out for breakfast, dieharder should be done by the time I come back and I can then upload the results

Why not keep this simple. You are not, obviously, interested in a cryptographically secure RNG, so LCG, Mersene Twister, Xorshift128 or any other PRNG is suitable. A thread safe LCG is easy enough to be implemented. For example:

Code:

unsigned int myrand( unsigned int *state )
{
  unsigned int r;

  /* LCG: Stolen from glibc (changed to unsigned int). */
  r = ( *state * 1103515245 ) + 12345;
  *state = r;

  return r;
}

This "state" is your initial seed and the values 1103515245 and 12345 are good enough for an LCG...

If you want to use RDRAND for Intel/AMD processors, you can do something like this:

Code:

/* rand.c */
#include <cpuid.h>

/* Interface pointers to proper functions. */
void (*SRAND)( unsigned int *, unsigned int );
unsigned int (*RAND)( unsigned int * );

/* Because RDRAND don't need a seed! */
static void empty( unsigned int *state, unsigned int seed ) {}

/* mysrand() & myrand() are thread safe. You need only to provide
   A pointer to the initial seed */
static void mysrand( unsigned int *state, unsigned int seed )
{
  *state = seed;
}

static unsigned int myrand( unsigned int *state )
{
  unsigned int r;

  /* LCG: Stolen from glibc (changed to unsigned int). */
  r = ( *state * 1103515245 ) + 12345;
  *state = r;

  return r;
}

#if defined(__i386) || defined(__x86_64)
static unsigned int rdrand( unsigned int *state )
/* state pointer is ignored! */
{
  unsigned int r;

  /* Need to save EBX/RBX because of SysV calling convention. */
  __asm__ __volatile__(
    "1:\n\t"
    "  rdrand %0\n\t"
    "  jnc 1b" : "=c" (r) ::
  #ifdef __i386
    "ebx"
  #else
    "rbx"
  #endif
  );

  // NOTE: There is an intrinsic called _rdrand32_step(), but it created worse code
  // than this one...

  return r;
}
#endif

/* The default behavior is to use LCG, unless we are dealing with
   Intel/AMD processors which have RDRAND instruction. */
void (*SRAND)( unsigned int *, unsigned int ) = mysrand;
unsigned int (*RAND)( unsigned int * ) = myrand;

#if defined(__i386) || defined(__x86_64)
/* You can change this to a simple RAND_init() function which must be called before any
   use of SRAND() or RAND(). I prefer to use the GCC extension. */
static void __attribute__((constructor)) RAND_ctor( void )
{
  int a, b, c, d;

  __cpuid( 1, a, b, c, d ); // Yep, this is an intrinsic @ cpuid.h.
                            // You can do this in asm, if you wish...

  if ( c & bit_RDRND )      // bit_RDRND also defined in cpuid.h
  {
    SRAND = empty;
    RAND = rdrand;
  }  
}
#endif

A small test code:

Code:

/* test.c */
#include <stdio.h>
#include <time.h>
#include <limits.h>

#define scale2rgb(n) \
  ( unsigned int ) ( ( (n) * 16777215.0 ) / UINT_MAX )

extern void (*SRAND)( unsigned int *, unsigned int );
extern unsigned int (*RAND)( unsigned int * );

int main ( void )
{
  int i;
  unsigned int rnd_state, r;

  SRAND( &rnd_state, time(NULL) );

  puts("P6\n1024 1024\n255");
  for ( i = 0; i < 1024*1024; i++ )
  {
    r = scale2rgb(RAND(&rnd_state));
    fwrite( &r, 3, 1, stdout );
  }
}

Compiling and linking:

Code:

$ cc -O2 -c rand.c test.c
$ cc -O2 -s -o test test.o rand.o
$ ./test > pic.ppm