#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <time.h>
#include <sys/mman.h>

#define MAX_SHIFT 24
#define REPETITIONS 10
#define ITERATIONS (1 << 20)

void *mmalloc(size_t length)
{
	void *addr = mmap(NULL, length, PROT_READ | PROT_WRITE | PROT_EXEC, MAP_PRIVATE | MAP_ANONYMOUS, -1, 0);
	if(addr == (void*)-1)
	{
		perror("mmap");
		exit(EXIT_FAILURE);
	}
	return addr;
}

void mfree(void *addr, size_t length)
{
	if(-1 == munmap(addr, length))
	{
		perror("munmap");
		exit(EXIT_FAILURE);
	}
}

void yates_shuffle(size_t volatile *a, size_t length)
{
	size_t *t = calloc(length, sizeof(size_t));
	size_t i;
	for(i = 0; i < length; i++)
		t[i] = i;
	for(i = length; i;)
	{
		size_t j = rand() % i;
		i--;
		size_t tmp = t[i];
		t[i] = t[j];
		t[j] = tmp;
	}
	for(i = 0; i < length - 1; i++)
		a[t[i]] = t[i + 1];
	a[t[length - 1]] = t[0];
}

long long int test(size_t length, int n)
{
	size_t volatile *window = mmalloc(length * sizeof(size_t));
	yates_shuffle(window, length);
	struct timespec s, e;
	size_t ptr = 0;
	int i;
	clock_gettime(CLOCK_REALTIME, &s);
	for(i = 0; i < n; i++)
		ptr = window[ptr];
	clock_gettime(CLOCK_REALTIME, &e);
	mfree((void *)window, length * sizeof(size_t));
	return (e.tv_sec - s.tv_sec) * 1000000 + ((signed long long int)e.tv_nsec - (signed long long int)s.tv_nsec) / 1000;
}

int main()
{
	int i;
	for(i = 1; i <= MAX_SHIFT; i++)
	{
		long long int sum = 0;
		printf("%10lld octets (%11lld bytes): ", 1LL << i, sizeof(size_t) * (1LL << i));
		fflush(stdout);
		int j;
		for(j = 0; j < REPETITIONS; j++)
		{
			sum += test(1 << i, ITERATIONS);
			printf(".");
			fflush(stdout);
		}
		printf(" %11lld microseconds\n", sum / REPETITIONS);
	}
}