#include <err.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <unistd.h>

extern char *malloc_options;

/*
cc arc4random_uniform_fast.c -O2 -march=native -mtune=native -flto=full \
-static -p -fno-inline && ./a.out && gprof a.out gmon.out

cc arc4random_uniform_fast.c -O2 && ./a.out
 */


/* 
 * uint32_t
 * arc4random_uniform(uint32_t upper_bound);
 * 
 * for which this function is named, provides a cryptographically secure:
 * uint32_t arc4random() % upper_bound;
 * 
 * this function minimizes the waste of randomly generated bits,
 * for small upper bounds.
 * 
 * 'bits' is the requested number of random bits and it needs to be
 * within the following parameters:
 * 
 *   1 << bits     >=     upper_bound     >     (1 << bits) >> 1
 */
static uint32_t
arc4random_uniform_fast(uint64_t upper_bound)
{	
	static uint64_t rand_holder = 0;
	static size_t rand_bits = 0;
	
	static uint64_t upper_bound0 = 2;
	static size_t bits0 = 1;

	size_t ret;
	size_t bits = 16, i = 1, n = 32, ub = upper_bound;

	if (ub != upper_bound0) {
		
		if (ub < 2)
			return 0;
		
		for (;;) {
			
			if ( ub <= ((size_t)1 << bits) >> 1 ) {
				
				if (n - i == 1) {
					bits = n;
					break;
				}
				
				n = bits;
				bits = (i + n) / 2;
				continue;
			}
			if ( ub > ((size_t)1 << bits) ) {
				
				if (n - i == 1) {
					bits = n;
					break;
				}
				
				i = bits;
				bits = (i + n) / 2;
				continue;
			}
			
			
			break;
		}
		upper_bound0 = ub;
		bits0 = bits;
		
	} else
		bits = bits0;
		
	for (;;) {
		if (rand_bits < bits) {
			rand_holder |= ((uint64_t)arc4random()) << rand_bits;
			
			/* 
			 * rand_bits will be a number between 0 and 31 here
			 * so the 0x20 bit will be empty
			 * rand_bits += 32;
			 */ 
			rand_bits |= 32;
		}
		
		ret = rand_holder & (  ((size_t)1 << bits) - 1  );
		rand_holder >>= bits;
		rand_bits -= bits;
		
		if (ret < upper_bound)
			return ret;
	}
}


/* 
 * uint32_t
 * arc4random_uniform(uint32_t upper_bound);
 * 
 * for which this function is named, provides a cryptographically secure:
 * uint32_t arc4random() % upper_bound;
 * 
 * this function minimizes the waste of randomly generated bits,
 * for small upper bounds and is possibly more secure.
 * 
 *   1 << bits     >=     upper_bound     >     (1 << bits) >> 1
 */
/*
 * this one doesn't waste any bits it doesn't need to.
 * it doesn't take a bits value, because it generates it for you.
 * This makes it less efficient than the other arc4random_uniform_fast
 * functions
 */
static uint32_t
arc4random_uniform_fast2(uint32_t upper_bound)
{
	static uint64_t rand_holder = 0;
	static size_t rand_bits = 0;
	
	static uint64_t upper_bound0 = 2;
	static size_t bits0 = 1;

	size_t ret;
	size_t bits = 16, i = 1, n = 32, ub = upper_bound;

	if (ub != upper_bound0) {
		
		if (ub < 2)
			return 0;
		
		for (;;) {
			
			if ( ub <= ((size_t)1 << bits) >> 1 ) {
				
				if (n - i == 1) {
					bits = n;
					break;
				}
				
				n = bits;
				bits = (i + n) / 2;
				continue;
			}
			if ( ub > ((size_t)1 << bits) ) {
				
				if (n - i == 1) {
					bits = n;
					break;
				}
				
				i = bits;
				bits = (i + n) / 2;
				continue;
			}
			
			
			break;
		}
		upper_bound0 = ub;
		bits0 = bits;
		
	} else
		bits = bits0;

	if (rand_bits < bits) {
		
		rand_holder |= ((uint64_t)arc4random()) << rand_bits;
		
		/* 
		 * rand_bits will be a number between 0 and 31 here
		 * so the 0x20 bit will be empty
		 * rand_bits += 32;
		 */ 
		rand_bits |= 32;
	}
	
	ret = rand_holder & (  ((size_t)1 << bits) - 1  );
	rand_holder >>= bits;
	rand_bits -= bits;
	
	while (ret >= ub) {
		
		if (!rand_bits) {
			rand_holder = arc4random();
			rand_bits = 32;
		}
		
		/*
		 * this shifts ret right and puts in
		 * a new maximum bit from rand_holder
		 * 
		 *            bits >= 1
		 */
		ret = ((rand_holder & 1) << (bits - 1)) | ( ret >> 1 );

		rand_holder >>= 1;
		--rand_bits;
	}
	
	return ret;
}

/*
 *  Random short plus. Reveals limitations of arc4random_uniform_fast2()
 */
static
void rand_ideal(size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		arc4random_uniform(2);
}

/*
 *  Random short plus. Reveals limitations of arc4random_uniform_fast2()
 */
static
void rand_ideal_fast(size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		arc4random_uniform_fast(2);
}

/*
 *  Random short. Ideal conditions.
 */
static
void rand_short_ideal(size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		arc4random_uniform(0x10000);
}

/*
 *  Random short. Ideal conditions.
 */
static
void rand_short_ideal_fast(size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		arc4random_uniform_fast(0x10000);
}

/*
 *  Random short plus. Reveals limitations of arc4random_uniform_fast2()
 */
static
void rand_short_worst(size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		arc4random_uniform(0x10001);
}

/*
 *  Random short plus. Reveals limitations of arc4random_uniform_fast2()
 */
static
void rand_short_worst_fast(size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		arc4random_uniform_fast(0x10001);
}

/*
 *  Random long long plus. Reveals limitations of arc4random_uniform_fast2()
 */
static
void rand_worst(size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		arc4random_uniform(0x400001);
}

/*
 *  Random long long plus. Reveals limitations of arc4random_uniform_fast2()
 */
static
void rand_worst_fast(size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		arc4random_uniform_fast(0x400001);
}

/*
 *  Random 'a'-'z'
 * length doesn't include the '\0' character at the end
 */
static
void newdata(char a[], size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n)
		a[n] = 'a' + (char)arc4random_uniform(26);
	a[len] = '\0';
}

/*
 *  Random 'a'-'z'
 * length doesn't include the '\0' character at the end
 */
static
void newdata_fast(char a[], size_t length)
{
	size_t len = length, n;
	for (n = 0; n != len; ++n) {
		a[n] = 'a' +
		    (char)arc4random_uniform_fast(26);
	}
	a[len] = '\0';
}


//	33-45		skip a bunch of whitespace characters
//	48-126		skip '.' and '/'
//	I don't include '.'(46), because it could cause issues I'd rather avoid
static const char filenameTypableArray[92] =
{
	 33,  34,  35,  36,  37,  38,  39,  40,  41,  42,
	 43,  44,  45,  48,  49,  50,  51,  52,  53,  54,
	 55,  56,  57,  58,  59,  60,  61,  62,  63,  64,
	 65,  66,  67,  68,  69,  70,  71,  72,  73,  74,
	 75,  76,  77,  78,  79,  80,  81,  82,  83,  84,
	 85,  86,  87,  88,  89,  90,  91,  92,  93,  94,
	 95,  96,  97,  98,  99, 100, 101, 102, 103, 104,
	105, 106, 107, 108, 109, 110, 111, 112, 113, 114,
	115, 116, 117, 118, 119, 120, 121, 122, 123, 124,
	125, 126
};

//length doesn't include the '\0' character at the end
static
void newdataTypableFilename(char a[], const size_t length)
{
	size_t j;

	for (j = 0; j < length; ++j)
		a[j] = filenameTypableArray[ arc4random_uniform(92) ];
	a[j] = '\0';
}

//length doesn't include the '\0' character at the end
static
void newdataTypableFilename_fast(char a[], const size_t length)
{
	size_t j;

	for (j = 0; j < length; ++j) {
		a[j] = 
		    filenameTypableArray[ arc4random_uniform_fast(92) ];
	}
	a[j] = '\0';
}

/* 
 * simulate the kind of decreasing upperbound
 * random generation needed to shuffle an array
 */
static
void shuffle(const size_t length)
{
	size_t i, g = length - 1;
	
	for (i = 0; i < g; ++i)
		arc4random_uniform(length - i);
}

/* 
 * simulate the kind of decreasing upperbound
 * random generation needed to shuffle an array
 */
static
void shuffle_fast(const size_t length)
{
	size_t i, g = length - 1;
	
	for (i = 0; i < g; ++i)
		arc4random_uniform_fast(length - i);
}

#define LIMIT   49

int main()
{
	
	
	malloc_options = "CFGJJU";

	if (unveil(NULL, NULL) == -1)
		err(1, "unveil, line: %d", __LINE__);
	
	if (pledge("stdio", NULL) == -1)
		err(1, "pledge, line: %d", __LINE__);
	
	
	
	unsigned counts[LIMIT] = { 0 };
	unsigned counts2[LIMIT] = { 0 };
        int i;
        for (i = 0; i < 100000 * LIMIT; i++) {
                counts[arc4random_uniform(LIMIT)]++;
                counts2[arc4random_uniform_fast(LIMIT)]++;
        }
        for (i = 0; i < LIMIT; i++)
                printf("%2d\t%7u\t%7u\n", i+1, counts[i], counts2[i]);
                
                
                
	printf("\n\n\n\n\n");
	
	
	
	
	
	
	

		
	//~ size_t n = 100000000, m;
	//~ size_t m;
	size_t n = 5000000;
	
	long double cpu_time_used0;
	long double cpu_time_used1;
	
	struct timespec start, end;
	
	char *buf = malloc(n + 1);
	if (buf == NULL)
		errx(1, "malloc");
		
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	
	printf("\n\n\n");
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	newdata(buf, n);
	//~ printf("%s\n\n", buf);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used0 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("newdata\n");
	printf("time = %.9Lf seconds\n\n", cpu_time_used0);
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	newdata_fast(buf, n);
	//~ printf("%s\n\n", buf);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used1 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("newdata_fast\n");
	printf("time = %.9Lf seconds\n", cpu_time_used1);
	
printf("\nThe original takes %.3Lf%% of the runtime of newdata_fast\n\n",
	    (cpu_time_used0 / cpu_time_used1) * (long double)100.0);
	
	
	printf("\n\n\n\n\n");
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	newdataTypableFilename(buf, n);
	//~ printf("%s\n\n", buf);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used0 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("newdataTypableFilename\n");
	printf("time = %.9Lf seconds\n\n", cpu_time_used0);
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	newdataTypableFilename_fast(buf, n);
	//~ printf("%s\n\n", buf);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used1 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("newdataTypableFilename_fast\n");
	printf("time = %.9Lf seconds\n", cpu_time_used1);
	
	printf("\nThe original takes %.3Lf%% ",
	    (cpu_time_used0 / cpu_time_used1) * (long double)100.0);
	printf("of the runtime of newdataTypableFilename_fast\n\n");
	
	
	printf("\n\n\n\n\n");

	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	rand_ideal(n);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used0 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("rand_ideal\n");
	printf("time = %.9Lf seconds\n\n", cpu_time_used0);
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	rand_ideal_fast(n);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used1 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("rand_ideal_fast\n");
	printf("time = %.9Lf seconds\n", cpu_time_used1);
	
printf("\nThe original takes %.3Lf%% of the runtime of rand_ideal_fast\n\n",
	    (cpu_time_used0 / cpu_time_used1) * (long double)100.0);
	
	
	printf("\n\n\n\n\n");

	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	rand_short_ideal(n);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used0 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("rand_short_ideal\n");
	printf("time = %.9Lf seconds\n\n", cpu_time_used0);
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	rand_short_ideal_fast(n);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used1 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("rand_short_ideal_fast\n");
	printf("time = %.9Lf seconds\n", cpu_time_used1);
	
printf("\nThe original takes %.3Lf%% of the runtime of rand_short_ideal_fast\n\n",
	    (cpu_time_used0 / cpu_time_used1) * (long double)100.0);
	
	
	printf("\n\n\n\n\n");

	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	rand_short_worst(n);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used0 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("rand_short_worst\n");
	printf("time = %.9Lf seconds\n\n", cpu_time_used0);
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	rand_short_worst_fast(n);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used1 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("rand_short_worst_fast\n");
	printf("time = %.9Lf seconds\n", cpu_time_used1);
	
printf("\nThe original takes %.3Lf%% of the runtime of rand_short_worst_fast\n\n",
	    (cpu_time_used0 / cpu_time_used1) * (long double)100.0);
	
	
	printf("\n\n\n\n\n");

	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	rand_worst(n);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used0 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("rand_worst\n");
	printf("time = %.9Lf seconds\n\n", cpu_time_used0);
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	rand_worst_fast(n);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used1 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("rand_worst_fast\n");
	printf("time = %.9Lf seconds\n", cpu_time_used1);
	
printf("\nThe original takes %.3Lf%% of the runtime of rand_worst_fast\n\n",
	    (cpu_time_used0 / cpu_time_used1) * (long double)100.0);
	
	
	printf("\n\n\n\n\n");

	
	
	size_t shuffle_length = 65536;
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	//~ for (m = n / shuffle_length; m; --m)
		shuffle(shuffle_length);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used0 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("shuffle\n");
	printf("time = %.9Lf seconds\n\n", cpu_time_used0);
	
	
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &start);
	//~ for (m = n / shuffle_length; m; --m)
		shuffle_fast(shuffle_length);
	clock_gettime(CLOCK_PROCESS_CPUTIME_ID, &end);

	cpu_time_used1 =
	    (long double) (end.tv_sec - start.tv_sec) +
	    (long double) (end.tv_nsec - start.tv_nsec) /
	    (long double) 1000000000;

	printf("shuffle_fast\n");
	printf("time = %.9Lf seconds\n", cpu_time_used1);
	
printf("\nThe original takes %.3Lf%% of the runtime of shuffle_fast\n\n",
	    (cpu_time_used0 / cpu_time_used1) * (long double)100.0);
	
	free(buf);
	
	printf("If it crashed here, you are trying to profile.\n");
	printf("Turn off pledge at the beginning of main().\n\n");
	
	return 0;
}