#include <stdlib.h>

int max1(int* ints, size_t size)
{
    if (size <= 0) return 0;
    if (size == 1) return ints[0];

    int max = ints[0];
    for (size_t i = 1; i < size; i++)
    {
        max = max > ints[i] ? max : ints[i];
    }

    return max;
}

int max2(int input[], size_t length)
{
	if(length < 4) return 0;

	int m1 = input[0];
	int m2 = input[0];
	int m3 = input[0];
	int m4 = input[0];
	length /= 4;
	while(length--)
	{
		if(m1 < input[0]) m1 = input[0];
		if(m2 < input[1]) m2 = input[1];
		if(m3 < input[2]) m3 = input[2];
		if(m4 < input[3]) m4 = input[3];

		input += 4;
	}
	int _max1 = m1 < m2 ? m2 : m1;
	int _max2 = m3 < m4 ? m4 : m3;
	return _max1 < _max2 ? _max2 : _max1;
}

int max3(int input[], size_t length)
{
	if(length < 4) return 0;

	int m1 = input[0];
	int m2 = input[0];
	int m3 = input[0];
	int m4 = input[0];
	length /= 4;
	for(size_t i = 0; i < length; i++)
	{
		if(m1 < input[0]) m1 = input[0];
		if(m2 < input[1]) m2 = input[1];
		if(m3 < input[2]) m3 = input[2];
		if(m4 < input[3]) m4 = input[3];

		input += 4;
	}
	int _max1 = m1 < m2 ? m2 : m1;
	int _max2 = m3 < m4 ? m4 : m3;
	return _max1 < _max2 ? _max2 : _max1;
}

int max4(int input[], size_t length)
{

	if(length < 4) return 0;
	size_t olength = length;

	int m1 = input[0];
	int m2 = input[0];
	int m3 = input[0];
	int m4 = input[0];
	length /= 4;
	while(length--)
	{
		if(m1 < input[0]) m1 = input[0];
		if(m2 < input[1]) m2 = input[1];
		if(m3 < input[2]) m3 = input[2];
		if(m4 < input[3]) m4 = input[3];

		input += 4;
	}
	int _max1 = m1 < m2 ? m2 : m1;
	int _max2 = m3 < m4 ? m4 : m3;
	int _max3 = _max1 < _max2 ? _max2 : _max1;

	olength %= 4;
	while(olength--)
	{
		if(_max3 < input[0])
			_max3 = input[0];
		++input;
	}

	return _max3;
}

// testing stuff below

#include <stdio.h>
#include <time.h>
#include <assert.h>
#include <math.h>

#define SIZE  10000003
#define TIMES 100

/*
#define INITPERF()\
unsigned int seed = time(NULL);\
printf("\nseed: %u, %u ints, ran %u times, shortest run time taken\n\n", seed, SIZE, TIMES);\
srand(seed);\
int* testarray = calloc(SIZE, sizeof(int));\
assert(testarray != NULL);\
unsigned long long start;\
unsigned long long end;\
unsigned long long* times = calloc(TIMES, sizeof(unsigned long long))

#define PERF(F, NAME)\
printf("%s: ", NAME);fflush(stdout);\
for(size_t i=0;i<SIZE;i++)testarray[i]=rand();\
for(size_t j=0;j<TIMES;j++){\
start=rdtsc();\
F(testarray,SIZE);\
end=rdtsc();\
times[j]=(end - start);}\
printf("min: %llu clock cycles, max: %llu clock cycles\n", findminllu(times, TIMES), findmaxllu(times, TIMES))
*/

extern unsigned long long rdtsc();

unsigned long long findminllu(unsigned long long input[], size_t length)
{
	if(length < 4) return 0;

	unsigned long long m1 = input[0];
	unsigned long long m2 = input[0];
	unsigned long long m3 = input[0];
	unsigned long long m4 = input[0];
	length /= 4;
	while(--length)
	{
		if(m1 > input[0]) m1 = input[0];
		if(m2 > input[1]) m2 = input[1];
		if(m3 > input[2]) m3 = input[2];
		if(m4 > input[3]) m4 = input[3];

		input += 4;
	}
	unsigned long long _max1 = m1 < m2 ? m1 : m2;
	unsigned long long _max2 = m3 < m4 ? m3 : m4;
	return _max1 < _max2 ? _max1 : _max2;
}

unsigned long long findmaxllu(unsigned long long input[], size_t length)
{
	if(length < 4) return 0;

	unsigned long long m1 = input[0];
	unsigned long long m2 = input[0];
	unsigned long long m3 = input[0];
	unsigned long long m4 = input[0];
	length /= 4;
	while(--length)
	{
		if(m1 < input[0]) m1 = input[0];
		if(m2 < input[1]) m2 = input[1];
		if(m3 < input[2]) m3 = input[2];
		if(m4 < input[3]) m4 = input[3];

		input += 4;
	}
	unsigned long long _max1 = m1 < m2 ? m2 : m1;
	unsigned long long _max2 = m3 < m4 ? m4 : m3;
	return _max1 < _max2 ? _max2 : _max1;
}

int* testarray;
unsigned long long* times;

void perf(int (*func)(int[], size_t), char name[])
{
	printf("%s: ", name);
	fflush(stdout);
	
	for(size_t i = 0; i < SIZE; i++) testarray[i]=rand();
	size_t j;
	unsigned long long start, end;
	for(j = 0; j < TIMES; j++)
	{
		repeat:

		start = rdtsc(); // TODO: use rdtscp?
		[[maybe_unused]] volatile int _ = func(testarray, SIZE); // volatile unused read so at -O3 the function call doesn't get wished away
		end = rdtsc();

		if(end <= start) goto repeat; // process probably moved cores? idk
		// this is the actual cause of the bug that results in random gigantic numbers
		// ACTUAL fix TODO: set thread affinity, since otherwise it cannot be guaranteed that 2 separate rdtsc instructions run on the same core and read the same tsc
		times[j]=(end - start);

		//printf("%llu: %llu to %llu : %llu\n", j, start, end, times[j]);
	}
	printf("min: %llu clock cycles, max: %llu clock cycles\n", findminllu(times, TIMES), findmaxllu(times, TIMES));
}

int main()
{
	time_t seed = time(NULL);
	printf("\nseed: %lld, %u ints, ran %u times, shortest run time taken\n\n", (long long)seed, SIZE, TIMES);
	srand((unsigned)seed);

	testarray = calloc(SIZE, sizeof(int));
	assert(testarray != NULL);

	times = calloc(TIMES, sizeof(unsigned long long));
	assert(times != NULL);

	perf(max1, "max1");
	perf(max2, "max2");
	perf(max3, "max3");
	perf(max4, "max4");

	// sanity check
	for(size_t i=0;i<SIZE;++i) testarray[i]=rand();
	int m1 = max1(testarray, SIZE);
	int m2 = max2(testarray, SIZE);
	int m3 = max3(testarray, SIZE);
	int m4 = max4(testarray, SIZE);

	free(times);
	free(testarray);
	assert(m1 == m4);
	assert(m1 == m2);
	assert(m1 == m3);

	return 0;
}