Pseudorandom number with PB internal Random

[Caronte3D]

You can ruin files, if you want, and get them back with the valid seed 1 byte after an other, while
never having a full key in your memory/executable file.

Interessant approach

[miso]

You can ruin files, if you want, and get them back with the valid seed 1 byte after an other, while
never having a full key in your memory/executable file.

Interessant approach

Uhh, as a second read this sounds really bad. I am interested in games. Allowing modding is appreciated by players, not allowing modding ensures that your original quality stays steady. So if I ruin the first 2kbyte of the headers of my images, I can still retrieve them, while modding won't be possible for the majority. Modding support is a decision, allowing and disallowing it both have their pros and cons. (No malicious intensions here.)

[Fred]

Here it is, as fr34k said it's not the easiest to understand code ! Good luck

Code: Select all

/* === Copyright Notice ===
 *
 *
 *                  PureBasic source code file
 *
 *
 * This file is part of the PureBasic Software package. It may not
 * be distributed or published in source code or binary form without
 * the expressed permission by Fantaisie Software.
 *
 * By contributing modifications or additions to this file, you grant
 * Fantaisie Software the rights to use, modify and distribute your
 * work in the PureBasic package.
 *
 *
 * Copyright (C) 2000-2010 Fantaisie Software - all rights reserved
 *
 */

/*
 * RANROT type W algorithm, based on: http://www.agner.org/random/theory/chaosran.pdf
 * (custom implementation, not based on the GPL'ed ASM/C++ version by the paper author)
 */
 
#include "Math.h"

#ifndef WINDOWS
	#include <sys/time.h>
	#include <pthread.h>
#endif

M_PBFUNCTION(void) PB_RandomSeed(unsigned int Value);

/* Keep these the same as the ASM sample code to be compatible to the
 * old Random()
 */
#define R1 19
#define R2 27
#define R3  0
#define R4  0
#define J  10
#define K   0
#define BUFFER_SIZE 17

/* For a threadsafe Random()
 */
typedef struct
{
  // Note: we would need a 3rd index k (= n-K), but since K=0, we optimze that to n
  int n;
  int j;
  unsigned int Z[BUFFER_SIZE];
  unsigned int Y[BUFFER_SIZE];  
} PB_RandomDataStruct;

#ifdef THREAD
  static M_TLS RandomDataKey;
  
  #define Random_n   (RandomData->n)
  #define Random_j   (RandomData->j)
  #define Random_Z   (RandomData->Z)
  #define Random_Y   (RandomData->Y)
  #define Random_Ptr RandomData
#else
  static PB_RandomDataStruct RandomData;
  
  #define Random_n   (RandomData.n)
  #define Random_j   (RandomData.j)
  #define Random_Z   (RandomData.Z)
  #define Random_Y   (RandomData.Y)
  #define Random_Ptr (&RandomData)
#endif

static int Initialized = 0;


// -----------------------------------------------------------------------------------

// extract low/high part of a quad, (in quad form)
// do not use quad type, as it is 32bit on PPC!
//
// NOTE: These are the same on big endian, as the >> operator seems to take that into effect.
#define LOW_INT(x)          ((unsigned long long)(x) & 0xFFFFFFFF)
#define HIGH_INT(x)         (((unsigned long long)(x) >> (unsigned long long)32) & 0xFFFFFFFF)
#define MAKE_QUAD(l, h)     ((unsigned long long)(l) & ((unsigned long long)(h) << (unsigned long long)32))


//
// all inline, as here speed is much more important than size.
//

M_INLINE(unsigned int) ROTL(unsigned int Input, int Steps)
{
  // If steps are 0, then we try to do rotate of '32' which is not compatiable for OS X gcc
  // http://www.purebasic.fr/english/viewtopic.php?f=24&t=63023
  //
  if (Steps)
  {
    return (Input << Steps) | (Input >> (32-Steps)); // its unsigned int, so this is a logical shift (no 1's added on top)
  }
  else
  {
    return Input;
  }
}


M_INLINE(void) RANROT(PB_RandomDataStruct *Data, unsigned int *low, unsigned int *high)
{
  unsigned int Yn, Zn;
  int n, j;
  
  // read the indexes to local vars for speed
  n = Data->n;
  j = Data->j;
 
  // store Z,Y in separate variables first as we need the originals in the calculation
  Zn = ROTL(Data->Y[j], R3) + ROTL(Data->Y[n], R1); // (mod b/2 automatic, as its 32bit variable)
  Yn = ROTL(Data->Z[j], R4) + ROTL(Data->Z[n], R2);  
  
  Data->Z[n] = Zn;
  Data->Y[n] = Yn;
  
  // for some odd reason, the old code walked backward through the circular buffer, so do the same
  n--;
  j--;
  if (n < 0) n = BUFFER_SIZE-1;
  if (j < 0) j = BUFFER_SIZE-1;
  
  // write back to data structure
  Data->n = n;
  Data->j = j;
  
  *low  = Yn;
  *high = Zn;
}

M_INLINE(void) Initialize()
{
  #ifdef THREAD
    PB_RandomDataStruct *RandomData;
    
    if (Initialized == 0)
    {
      // global initialisation
      M_TlsInit(RandomDataKey);
      Initialized = 1;
    }
    
    // threadlocal initialisation
    M_TlsWrite(RandomDataKey, M_Alloc(sizeof(PB_RandomDataStruct)));    
    
  #else
    Initialized = 1; // Must be before PB_RandomSeed() as it call this init function as well
  #endif
  

  /* Factor in the current time + thread id, so that if multiple threads call Random() the first 
   * time at the same ms time (for example if creating multiple threads at once)
   * we still get a different random seed
   */
  #ifdef WINDOWS  
    PB_RandomSeed(GetTickCount() ^ GetCurrentThreadId()); // bitwise xor
  #else
  {
    struct timeval Time;

    gettimeofday(&Time, 0);
    PB_RandomSeed(((Time.tv_sec*1000)+Time.tv_usec/1000) ^ ((unsigned_integer)pthread_self()));
  }
  #endif	
}

// -----------------------------------------------------------------------------------

/* Use unsigned_integer, so Random($7FFFFFFF) works correctly.
 * Additional benefit: The full long range can be used now (if the result is interpreted as unsigned)
 */
M_PBFUNCTION(unsigned_integer) PB_Random(unsigned_integer Max)
{ 
  unsigned int low, high;
  #ifdef THREAD
    PB_RandomDataStruct *RandomData;
  #endif
  
  if (Initialized == 0)
    Initialize();
  
  #ifdef THREAD
    if ((RandomData = M_TlsRead(RandomDataKey)) == 0) 
    {
      Initialize();                          // need a per-thread initialisation!
      RandomData = M_TlsRead(RandomDataKey); // read value again
    }
	#endif

  // Note: if Max = MAXLONG (or MAXQUAD) then this will result in 0. Thats why we have a check for this below.
  Max++;  
	RANROT(Random_Ptr, &low, &high);
	
	#ifdef PB_64
    /* Since we cannot calculate (x * Max) / 0xFFFFFFFFFFFFFFFF in the quad range (would require 128bit values), we use a trick
     * wich works just like multiplication on paper: 25 * 31 = 775
     *
     *   5 * 1  = 0 0 0 5   
     *   5 * 3  = 0 1 5 0
     *   2 * 1  = 0 0 2 0
     *   2 * 3  = 0 6 0 0
     *
     * The same in binary: (h1, l1) * (h2, l2)
     *
     *        0              0       high(l1 * l2)   low(l1 * l2)
     *        0        high(h1 * l2)  low(h1 * l2)        0
     *        0        high(l1 * h2)  low(l1 * h2)        0
     *  high(h1 * h2)   low(h1 * h2)       0              0
     *
     * Of this, we only use the high 64bit, so we have (x * Max) / 0xFFFFFFFFFFFFFFFF
     * This produces the same output as the 32bit version if Max < 0x7FFFFFFF, but allows quad range Max values, which is perfect
     */
    if (Max)
	    return (unsigned_integer)(HIGH_INT((unsigned long long)high * LOW_INT(Max)) + HIGH_INT((unsigned long long)low * HIGH_INT(Max)) + ((unsigned long long)high * HIGH_INT(Max)));
	  else
	    return (unsigned_integer)MAKE_QUAD(low, high);
	#else    
    // This is the same as calculating (high * Max) / 0xFFFFFFFF
    // the old Random() does this too, among some other weird (but ineffective) stuff :-)
    //
    if (Max)
      return (unsigned_integer)HIGH_INT((unsigned long long)high * (unsigned long long)Max);
    else
      return (unsigned_integer)high;
  #endif
}


M_PBFUNCTION(unsigned_integer) PB_Random2(unsigned_integer Max, unsigned_integer Min)
{
  if (Min > Max) // Avoid common error
    Min = Max;
  
  return PB_Random(Max-Min) + Min;
}

// -----------------------------------------------------------------------------------

M_PBFUNCTION(void) PB_RandomData(char *Buffer, integer Length)
{
  char RandomBytes[8];
  
  #ifdef THREAD
    PB_RandomDataStruct *RandomData;
  #endif
  
  if (Initialized == 0)
    Initialize();
  
  #ifdef THREAD
    if ((RandomData = M_TlsRead(RandomDataKey)) == 0) 
    {
      Initialize();                          // need a per-thread initialisation!
      RandomData = M_TlsRead(RandomDataKey); // read value again
    }
	#endif
	
	while (Length >= 8)
	{
	  // use directly the output buffer if it is large enough
	  RANROT(Random_Ptr, (unsigned int *)Buffer, (unsigned int *)(Buffer + 4));
	  Buffer += 8;
	  Length -= 8;
	}
	
	if (Length > 0)
	{
	  // use a separate buffer for the rest
	  RANROT(Random_Ptr, (unsigned int *)&RandomBytes[0], (unsigned int *)&RandomBytes[4]);
	  memcpy(Buffer, RandomBytes, Length);	  
	}
}



// -----------------------------------------------------------------------------------

M_PBFUNCTION(void) PB_RandomSeed(unsigned int Value)
{
  int Index;
  unsigned int low, high;
  #ifdef THREAD
    PB_RandomDataStruct *RandomData;
  #endif
  
  if (Initialized == 0)
    Initialize();
  
  #ifdef THREAD
    if ((RandomData = M_TlsRead(RandomDataKey)) == 0) 
    {
      Initialize();                          // need a per-thread initialisation!
      RandomData = M_TlsRead(RandomDataKey); // read value again
    }
	#endif  
  
  // initialize the buffer in exactly the same way the old RandomSeed did.
  //
	for (Index = 0; Index < BUFFER_SIZE; Index++)
	{
	  Value = Value*0xAC564B05+1; // Uses the hex value, else a warning is issued: "warning: this decimal constant is unsigned only in ISO C90"	  
	  Random_Y[Index] = Value;
	  Value = Value*0xAC564B05+1;
	  Random_Z[Index] = Value;
	}

	Random_n = 0;
	Random_j = 10;
	
	for (Index = 0; Index < 31; Index++)
	  RANROT(Random_Ptr, &low, &high);
}

[miso]

It's Christmas, thank you very much!

[Caronte3D]

Uhh, as a second read this sounds really bad.

I understood it perfectly the first time, no misunderstandings

[threedslider]

If you want to implement yourself so be inspired from C++ PRNG : https://github.com/MLeadbetter/prng

Here a little doc from wikipedia : https://en.wikipedia.org/wiki/Pseudoran ... _generator

Good luck !

[Piero]

These days I'm able to write a random generator, but it will generate a different content

Me too!

Random Post:

Forgive me if it'is not Hungarian (Czech) but I'm a big fan of "Švejka za světové války"
I still remember my Father reading it when I was VERY young… I have a very rare (Italian) edition…

F*ck war!