/* mbRand.cp */

#include "myTypedef.h"
#include "mbConv.h"
#include "mbMath.h"
#include "mbRand.h"
#include <math.h>
#include <time.h>
#include <stdlib.h>


// returns theBit (0 or 1) at bitPosition in blockNum of x
static INT32 findBit(const mb& x, INT32 bitPosition, INT32 blockNum)
{
	UINT32				mask;
	
	// now construct mask for getting theBit, we want to AND with something like 00010000
	mask = 1;
	mask = (mask<<bitPosition);
	return (mask & x.b[blockNum]);
	
}/* findBit */


// inserts theBit (0 or 1) at bitPosition in blockNum
static void insertBit(mb& x, INT32 theBit, INT32 bitPosition, INT32 blockNum)
{
	UINT32				mask;
	static UINT64		temp; // 0xFFFFFFFF
	static bool			arrayGood=false;
	
	if(!arrayGood)
	{
		temp = 1;
		temp = (temp<<32) - 1;
		arrayGood = true;
	}
	
	// construct mask for theBit=0, we want to AND with something like 11101111
	// so could form 00010000 and do a NOT?
	if(!theBit)
	{
		mask = 1;
		mask = (mask<<bitPosition);
		mask = temp - mask;
		x.b[blockNum] = (mask & x.b[blockNum]);
		return;
	}
	
	// now construct mask for theBit=1, we want to OR with something like 00010000
	mask = 1;
	mask = (mask<<bitPosition);
	x.b[blockNum] = (mask | x.b[blockNum]);
	
}/* insertBit */


// randomly set or clear bits starting at bitPosition and blockNum all the way down
static void randSetClear(mb& n, INT32 bitPosition, INT32 blockNum)
{
	INT32		theBit;
	
	while(blockNum>=0)
	{
		while(bitPosition>=0)
		{
			theBit = rand() % 2;
			insertBit(n, theBit, bitPosition, blockNum);
			bitPosition--;
		}
		bitPosition = 31;
		blockNum--;
	}
	
}/* randSetClear */


// constructs a random z where 0 <= z < n and n>0
bool mbRandom(mb& z, const mb& n)
{
	INT32		blockNumHigh, bitPositionHigh, blockNumLow, bitPositionLow; // locate high 1 bit and low 1 bit
	INT32		blockNum, bitPosition, theBit;
	bool		foundBit, doContinue;
	
	//srand(time(NULL)); // do in calling program
	
	if(n.n<=0)
		return false;
	
mbRandomAgain:
	
	foundBit = false;
	
	// find location of high 1 bit in n
	blockNum = n.n - 1;
	while(blockNum>=0 && !foundBit)
	{
		bitPosition = 31;
		while(bitPosition>=0 && !foundBit)
		{
			if(findBit(n, bitPosition, blockNum))
			{
				bitPositionHigh = bitPosition;
				blockNumHigh = blockNum;
				foundBit = true;
			}
			bitPosition--;
		}
		blockNum--;
	}
	
	if(!foundBit)
		return false;
	
	foundBit = false;
	
	// find location of low 1 bit in n
	blockNum = 0;
	while(blockNum<n.n && !foundBit)
	{
		bitPosition = 0;
		while(bitPosition<32 && !foundBit)
		{
			if(findBit(n, bitPosition, blockNum))
			{
				bitPositionLow = bitPosition;
				blockNumLow = blockNum;
				foundBit = true;
			}
			bitPosition++;
		}
		blockNum++;
	}
	
	if(!foundBit)
		return false;
	
	bitPosition = bitPositionHigh;
	blockNum = blockNumHigh;
	
	equate(z, n);
	
	// special case
	if(bitPositionHigh==bitPositionLow && blockNumHigh==blockNumLow)
	{
		insertBit(z, 0, bitPosition, blockNum);  // zero out the 1 bit
		// point to next lower bit
		bitPosition--;
		if(bitPosition<0)
		{
			blockNum--;
			bitPosition = 31;
		}
		if(blockNum>=0 && bitPosition>=0)
			randSetClear(z, bitPosition, blockNum);
		
		return true;
	}
	
	/*
		Going from high to low if find a 1 bit in z, roll the die for a 0 or 1.
		If 0, then can randomly set or clear all the remaining bits.
		If 1, then find the next 1 as go lower in n, and repeat above.
	*/
	doContinue = true;
	while(doContinue)
	{
		theBit = rand() % 2;
		if(!theBit)
		{
			insertBit(z, 0, bitPosition, blockNum);  // zero out the 1 bit
			// point to next lower bit
			bitPosition--;
			if(bitPosition<0)
			{
				blockNum--;
				bitPosition = 31;
			}
			if(blockNum>=0 && bitPosition>=0)
				randSetClear(z, bitPosition, blockNum);
			
			doContinue = false;
		}
		else
		{
			foundBit = false;
			// find next lower 1 bit
			// point to next lower bit
			bitPosition--;
			if(bitPosition<0)
			{
				blockNum--;
				bitPosition = 31;
			}
			
			while(blockNum>=0 && !foundBit)
			{
				while(bitPosition>=0 && !foundBit)
				{
					if(findBit(z, bitPosition, blockNum))
					{
						bitPositionHigh = bitPosition;
						blockNumHigh = blockNum;
						foundBit = true;
					}
					bitPosition--;
				}
				bitPosition = 31;
				blockNum--;
			}
			if(foundBit)
			{
				bitPosition = bitPositionHigh;
				blockNum = blockNumHigh;
			}
			else
				return false;
		}
		
		// end game
		if(bitPosition==bitPositionLow && blockNum==blockNumLow && doContinue)
		{
			doContinue = false;
			theBit = rand() % 2;
			if(!theBit)
			{
				insertBit(z, 0, bitPosition, blockNum);  // zero out the 1 bit
				// point to next lower bit
				bitPosition--;
				if(bitPosition<0)
				{
					blockNum--;
					bitPosition = 31;
				}
				if(blockNum>=0 && bitPosition>=0)
					randSetClear(z, bitPosition, blockNum);
			}
		}
	}
	
	// there is a possibility that z = n, should use goto and do again
	if(!compare(z, n))
		goto mbRandomAgain;
	
	return true;

}/* mbRandom */