//  Swarm library. Copyright (C) 1996 Santa Fe Institute.
// This library is distributed without any warranty; 
// without even the implied warranty of merchantability 
// or fitness for a particular purpose.
// See file LICENSE for details and terms of copying.

/*
Name:            ACGgen.m
Description:     Additive Congruential Generator
Library:         random
Original Author: Nelson Minar
Date:            1996-09-09
Modified by:     Sven Thommesen
Date:            1997-01-15
*/

/*
123456789|123456789|123456789|123456789|123456789|123456789|123456789|123456789|
*/

// ACG: Additive Congruential generator
//   X_n = X_(n-s) + X_(n-r) mod 2^32; r > s.

// Nelson's comments about ACG:

// ACG: an old warhorse, mentioned in Knuth, Sedgewick, Numerical Recipies.
// Personally, I don't recommend using this: the low order bits are very
// bad, and there are other problems.
// The SWB has nicer theory behind it and is only slightly slower.
// The period should be fairly high (roughly 2^r), and it should be efficient.

// Nelson's comments about Lagged Fibonacci generators:

// The basic algorithm for lagged fibonaccis is
//   X_n = f(X_(n-r) , X_(n-s)) mod m
// The function f is typically xor, addition, subtraction, multiplication,
// or subtract with carry. This is a big wide RNG class. The mathematics
// per number is simpler than an LCG, but it keeps more state around.

// The X_n .. X_(n-r) are stored in the "state" vector. This state vector
// is initialized with an LCG from one 32 bit seed.
// After initializing the state vector with the LCG, we throw away
// r*5 numbers to prime the generator.

#import <collections.h>
#import <random/ACGgen.h>

@implementation ACG

// This struct is used by getState and setState
// to pass our state data to/from other objects:

typedef struct {
// Generator identification:
  unsigned magic;
// RandomNumberGenerator data:
  unsigned stateSize;
  unsigned unsignedMax;
  unsigned initialSeed;
  unsigned currentCount;
// generator specific data:
  unsigned r;
  unsigned s;
  unsigned index;
  unsigned state[ACGLONGLAG];
} state_struct_t;

-resetState {				// Override RandomNumberGenerator method

// Called from setStateFromSeed in the superclass.

// We load up the state vector with the results of an LCG generator,
// LCG1, reimplemented here for economy. The LCG is initialized with
// the seed provided. We also throw away r*5 numbers to prime this
// generator.

  const unsigned a = 1664525;		// 'magic numbers' for LCG1
  const unsigned c = 1521933251;	//
  unsigned v;
  int i;
  unsigned bitbucket;

// If initialSeed needs to be tested for sanity, do it here:
   // seed==4x+1? seed isOdd?

// Make sure generator was initialized with good parameters:

  if ( (r > s) && (s > 0) ) {
    // all is fine
  } else {
    [InvalidCombination raiseEvent:
       "ACG: Initialization error: need 0 < s < r\n"];
  }

// Use an implicit LCG1 generator
// to fill up the state vector:
  
  v = a * initialSeed + c;
  for (i = 0; i < r; i++) 
  {
    v = a * v + c;
    state[i] = v;
  }

// Point to the beginning of the state vector:

  index = 0;

// Throw away 5*r numbers:

  for (i = 0; i < r*5; i++)
    bitbucket = [self getUnsignedSample];

  return self;
}


-initState {				// Override RandomNumberGenerator method

// Called from createBegin in the superclasss.

// Math is modulo 2^32, so max value is 2^32-1
   unsignedMax =  0xffffffffU;

// State size for getState and setState:
   stateSize = sizeof(state_struct_t);

// Set the 'personality' of this generator:
// ( Reference: Knuth p. 26 )

  r = ACGLONGLAG;
  s = ACGSHORTLAG;

// The state vector is allocated as an instance variable.
// It is initialized in resetState above.

   return self;
}


// ----- protocol RandomNumberGenerator: -----

-(unsigned) getUnsignedSample {		// Override RandomNumberGenerator method
  unsigned rth, sth, new;

// Generate the next 'random' value from the state.
// The math is implicitly modulo 2^32.

// Algorithm for ACG:
//   basically: new = (sth + rth) mod 2^32

// NOTE: no check is made that the state has been properly initialized.
// Responsibility for doing so rests with the RandomNumberGenerator class.

// Update count of variates delivered:

  currentCount++;

// Calculate next variate:

// Variant #1: using LagFibInline.h
//   rth = rthValue();
//   sth = sthValue();
//   new = sth + rth;	  // implicitly mod 2^32
//   updateState(new);
// end of variant 1

// Variant #2: using equivalent inline code

   rth = state[index];
   if (s <= index)
      sth = state[index-s];
   else
      sth = state[index+r-s];

   new = sth + rth;

   state[index] = new;
   index++;
   if (index >=r)
     index = 0;

// end of variant 2

// Variant #3: equivalent but less efficient code
//  rth = state[index];
//  sth = state[(index+r-s)%r];
//  new = sth + rth;	  // implicitly mod 2^32
//  state[index] = new;
//  index = (index+1)%r;
// end of variant 3

  return new;
}

// ----- protocol InternalState: -----

-(void) getState: (void *) stateBuf {	// Override RandomNumberGenerator method
   state_struct_t * internalState;
   int i;

// Recast the caller's pointer:
internalState = (state_struct_t *) (stateBuf) ;

// Fill the external buffer with current values:
  // Generator identification:
  internalState->magic = ACGMAGIC;
  // RandomNumberGenerator variables:
  internalState->unsignedMax = unsignedMax;
  internalState->stateSize = stateSize;
  internalState->initialSeed = initialSeed;
  internalState->currentCount = currentCount;
  // generator specific variables:
  internalState->r = r;
  internalState->s = s;
  internalState->index = index;
  for (i=0; i < ACGLONGLAG; i++)
    internalState->state[i] = state[i];

  // nothing returned from a (void) function
}

-(void) setState: (void *) stateBuf {	// Override RandomNumberGenerator method
   state_struct_t * internalState;
   int i;

// Recast the caller's pointer:
internalState = (state_struct_t *) (stateBuf) ;

// TEST the integrity of the external data:
if (     (internalState->magic     != ACGMAGIC)
      || (internalState->stateSize != stateSize)
      || (internalState->r         != r)
      || (internalState->s         != s) 
   )
[InvalidCombination raiseEvent:
 "ACG generator: your are passing bad data to setState!\n %u %u %u %u\n",
  internalState->magic, internalState->stateSize, 
  internalState->r, internalState->s ];

// Place external data into internal variables:
  // RandomNumberGenerator variables:
    // stateSize = internalState->stateSize;
    // unsignedMax = internalState->unsignedMax;
  initialSeed = internalState->initialSeed;
  currentCount = internalState->currentCount;
  // generator specific variables:
    // r = internalState->r;
    // s = internalState->s;
  index = internalState->index;
  for (i=0; i < ACGLONGLAG; i++)
    state[i] = internalState->state[i];

  // nothing returned from a (void) function
}

// ----- temporary methods: -----

- (void) describe: outStream {	// Extend RandomNumberGenerator method
  char buffer[200];
  //  int i;

  (void)sprintf(buffer,"ACG printSelf: \n");
  (void)sprintf(buffer,"            r = %u\n", r);
  (void)sprintf(buffer,"            s = %u\n", s);
  (void)sprintf(buffer,"        index = %u\n", index);
  //  for (i = 0; i < r; i++)
  //    (void)sprintf(buffer,"    state[%2d] = %u\n", i, state[i]);

  [super describe: outStream];	// Print RandomNumberGenerator data

  [outStream catC: buffer];
  [outStream catC: "\n"];
  //  return self;
}

-(int) verifySelf {
   const unsigned testValue = 282108301U;
   unsigned bitbucket;
   int i;

   [self setStateFromSeed: 1];

   for (i = 0; i < 10000; i++)
     bitbucket = [self getUnsignedSample];

   if (bitbucket == testValue) {
     printf("     ACG: Verify passed. Actual value = Expected value = %u\n",
            testValue);
     return 1;
   } else {
     printf("     ACG: Verify failed! Actual value = %u, Expected value = %u\n",
       testValue, bitbucket);
     return 0;
   } 

}

@end
