Random.c

/*
 *  RogueMain.c
 *  Brogue
 *
 *  Created by Brian Walker on 12/26/08.
 *  Copyright 2012. All rights reserved.
 *  
 *  This file is part of Brogue.
 *
 *  This program is free software: you can redistribute it and/or modify
 *  it under the terms of the GNU Affero General Public License as
 *  published by the Free Software Foundation, either version 3 of the
 *  License, or (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU Affero General Public License for more details.
 *
 *  You should have received a copy of the GNU Affero General Public License
 *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
 */

#include <math.h>
#include <time.h>
#include <limits.h>
#include <stdint.h> // C99

#include "Rogue.h"
#include "IncludeGlobals.h"

short randClump(randomRange theRange) {
	return randClumpedRange(theRange.lowerBound, theRange.upperBound, theRange.clumpFactor);
}

// Get a random int between lowerBound and upperBound, inclusive, with probability distribution
// affected by clumpFactor.
short randClumpedRange(short lowerBound, short upperBound, short clumpFactor) {
	if (upperBound <= lowerBound) {
		return lowerBound;
	}
	if (clumpFactor <= 1) {
		return rand_range(lowerBound, upperBound);
	}
	
	short i, total = 0, numSides = (upperBound - lowerBound) / clumpFactor;
	
	for(i=0; i < (upperBound - lowerBound) % clumpFactor; i++) {
		total += rand_range(0, numSides + 1);
	}
	
	for(; i< clumpFactor; i++) {
		total += rand_range(0, numSides);
	}
	
	return (total + lowerBound);
}

// Get a random int between lowerBound and upperBound, inclusive
boolean rand_percent(short percent) {
	return (rand_range(0, 99) < clamp(percent, 0, 100));
}

void shuffleList(short *list, short listLength) {
	short i, r, buf;
	for (i=0; i<listLength; i++) {
		r = rand_range(0, listLength-1);
		if (i != r) {
			buf = list[r];
			list[r] = list[i];
			list[i] = buf;
		}
	}
}

void fillSequentialList(short *list, short listLength) {
    short i;
    for (i=0; i<listLength; i++) {
        list[i] = i;
    }
}

//typedef unsigned long int  u4;
typedef uint32_t u4;
typedef struct ranctx { u4 a; u4 b; u4 c; u4 d; } ranctx;

static ranctx RNGState[2];

#define rot(x,k) (((x)<<(k))|((x)>>(32-(k))))
u4 ranval( ranctx *x ) {
    u4 e = x->a - rot(x->b, 27);
    x->a = x->b ^ rot(x->c, 17);
    x->b = x->c + x->d;
    x->c = x->d + e;
    x->d = e + x->a;
    return x->d;
}

void raninit( ranctx *x, u4 seed ) {
    u4 i;
    x->a = 0xf1ea5eed, x->b = x->c = x->d = seed;
    for (i=0; i<20; ++i) {
        (void)ranval(x);
    }
}

/* ----------------------------------------------------------------------
 range
 
 returns a number between 0 and N-1
 without any bias.
 
 */

#define RAND_MAX_COMBO ((unsigned long) UINT32_MAX)

int range(int n, short RNG) {
	unsigned long div;
	int r;
	
	div = RAND_MAX_COMBO/n;
	
	do {
		r = ranval(&(RNGState[RNG])) / div;
	} while (r >= n);
	
	return r;
}

// Get a random int between lowerBound and upperBound, inclusive, with uniform probability distribution

#ifdef AUDIT_RNG // debug version
int rand_range(int lowerBound, int upperBound) {
	int retval;
	char RNGMessage[100];
	
    brogueAssert(lowerBound <= INT_MAX && upperBound <= INT_MAX);
	
	if (upperBound <= lowerBound) {
		return lowerBound;
	}
	retval = lowerBound + range(upperBound-lowerBound+1, rogue.RNG);
	if (rogue.RNG == RNG_SUBSTANTIVE) {
		randomNumbersGenerated++;
		if (1) { //randomNumbersGenerated >= 1128397) {
			sprintf(RNGMessage, "\n#%lu, %i to %i: %i", randomNumbersGenerated, lowerBound, upperBound, retval);
			RNGLog(RNGMessage);
		}
	}
	return retval;
}
#else // normal version
int rand_range(int lowerBound, int upperBound) {
    brogueAssert(lowerBound <= INT_MAX && upperBound <= INT_MAX);
	if (upperBound <= lowerBound) {
		return lowerBound;
	}
	if (rogue.RNG == RNG_SUBSTANTIVE) {
		randomNumbersGenerated++;
	}
	return lowerBound + range(upperBound-lowerBound+1, rogue.RNG);
}
#endif

// seeds with the time if called with a parameter of 0; returns the seed regardless.
// All RNGs are seeded simultaneously and identically.
unsigned long seedRandomGenerator(unsigned long seed) {
	if (seed == 0) {
		seed = (unsigned long) time(NULL) - 1352700000;
	}
	raninit(&(RNGState[RNG_SUBSTANTIVE]), seed);
	raninit(&(RNGState[RNG_COSMETIC]), seed);
	return seed;
}