/* YOUR FILE-HEADER COMMENT HERE */

/* PART 1: YOUR COMMENT HERE */

#define _POSIX_C_SOURCE 199309L

#include <inttypes.h>
#include <math.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#if defined(__clang__)
#define OPTIMIZED minsize
#define UNOPTIMIZED optnone
#else
#define OPTIMIZED optimize("O2")
#define UNOPTIMIZED optimize("O0")
#endif

/**
 * Number of times to execute target function.
 */
#define NUM_TRIALS 50

/**
 * This function does nothing, intentionally.
 */
static int __attribute__((UNOPTIMIZED)) do_nothing(int val)
{
	return val;
}

/**
 * Calculate the nth value in the Fibonacci sequence, unoptimized.
 * <strong>You do not need to modify this function.</strong>
 * @param[in] n Which Fibonacci number to return.
 * @return Value of the @a n-th Fibonacci number.
 */
static int __attribute__((UNOPTIMIZED)) fibonacci_unoptimized(int n)
{
	if (n <= 1)
		return n;
	return fibonacci_unoptimized(n - 1) + fibonacci_unoptimized(n - 2);
}

/**
 * Calculate the nth value in the Fibonacci sequence, optimized.
 * <strong>You do not need to modify this function.</strong>
 * @param[in] n Which Fibonacci number to return.
 * @return Value of the @a n-th Fibonacci number.
 */
static int __attribute__((OPTIMIZED)) fibonacci_optimized(int n)
{
	if (n <= 1)
		return n;
	return fibonacci_optimized(n - 1) + fibonacci_optimized(n - 2);
}

/**
 * Calculate if the dividend is evenly divisible by the divisor.
 *
 * <strong>SPECIAL RESTRICTION</strong>: This function may only be
 * written using an <strong>ITERATIVE</strong> loop. It may not use
 * multiplication, division, or modulo division operator.
 *
 * Note: a dividend of zero is always divisible by the divisor.
 *
 * @param[in] a Value to be divided (the "dividend")
 * @param[in] b Non-zero divisor
 * @return 1 if the dividend is evenly divided, 0 otherwise
 */
static int __attribute((UNOPTIMIZED)) is_divisible_by_iterative(unsigned a, unsigned b)
{
	/* PART 3: YOUR CODE HERE */
	return 0;
}

/**
 * Calculate if the dividend is evenly divisible by the divisor.
 *
 * <strong>SPECIAL RESTRICTION</strong>: This function may only be
 * written using a <strong>RECURSIVE</strong> design. It may not use
 * multiplication, division, or modulo division operator.
 *
 * Note: a dividend of zero is always divisible by the divisor.
 *
 * @param[in] a Value to be divided (the "dividend")
 * @param[in] b Non-zero divisor
 * @return 1 if the dividend is evenly divided, 0 otherwise
 */
static int __attribute((UNOPTIMIZED)) is_divisible_by_recursive(unsigned a, unsigned b)
{
	/* PART 3: YOUR CODE HERE */
	return 0;
}

/**
 * Calculate if the dividend is evenly divisible by the divisor.
 *
 * <strong>SPECIAL RESTRICTION</strong>: This assembly function may
 * not use multiplication, division, or modulo division operator.
 *
 * Note: a dividend of zero is always divisible by the divisor.
 *
 * @param[in] a Value to be divided (the "dividend")
 * @param[in] b Non-zero divisor
 * @return 1 if the dividend is evenly divided, 0 otherwise
 */
extern int is_divisible_by_assembly(unsigned a, unsigned b);

/**
 * Compare two memory buffers.
 * <strong>You do not need to modify this function.</strong>
 * @param[in] s1 First buffer to compare
 * @param[in] s2 Other buffer to compare
 * @param[in] n Number of bytes to compare
 * @return 0 if buffers hold same values, non-zero if they differ
 */
int memcmp_8bit(const void *s1, const void *s2, size_t n)
{
	const uint8_t *a = s1;
	const uint8_t *b = s2;
	while (n > 0) {
		if (*a != *b) {
			return 1;
		}
		a++;
		b++;
		n--;
	}
	return 0;
}

/**
 * Compare two memory buffers, 32 bits at a time.
 * @param[in] s1 First buffer to compare
 * @param[in] s2 Other buffer to compare
 * @param[in] n Number of bytes to compare, will always be divisible by 4
 * @return 0 if buffers hold same values, non-zero if they differ
 */
int memcmp_32bit(const void *s1, const void *s2, size_t n)
{
	/* PART 5: YOUR CODE HERE */
	return 0;
}

/**
 * Compare two memory buffers, 64 bits at a time.
 * @param[in] s1 First buffer to compare
 * @param[in] s2 Other buffer to compare
 * @param[in] n Number of bytes to compare, will always be divisible by 8
 * @return 0 if buffers hold same values, non-zero if they differ
 */
int memcmp_64bit(const void *s1, const void *s2, size_t n)
{
	/* PART 5: YOUR CODE HERE */
	return 0;
}

/**
 * Compare two memory buffers, 256 bits at a time.
 * @param[in] s1 First buffer to compare
 * @param[in] s2 Other buffer to compare
 * @param[in] n Number of bytes to compare, will always be divisible by 32
 * @return 0 if buffers hold same values, non-zero if they differ
 */
extern int memcmp_256bit_assembly(const void *s1, const void *s2, size_t n);

/**
 * Calculate and return the difference between two clock values.
 * <strong>You do not need to modify this function.</strong>
 * @param[in] stop Minuend to subtract from
 * @param[in] start Subtrahend to subtract
 * @return Number of nanoseconds that elapsed
 */
static unsigned long clock_diff(const struct timespec *stop,
				const struct timespec *start)
{
	time_t sec_diff = stop->tv_sec - start->tv_sec;
	unsigned long nsec_diff;
	if (stop->tv_nsec < start->tv_nsec) {
		nsec_diff = 1000000000lu + stop->tv_nsec - start->tv_nsec;
		sec_diff--;
	} else
		nsec_diff = stop->tv_nsec - start->tv_nsec;
	nsec_diff += 1000000000lu * sec_diff;
	return nsec_diff;
}

typedef int (*func1)(int);
typedef int (*func2)(unsigned, unsigned);
typedef int (*func3)(const void *, const void *, size_t);

/**
 * Lambda to qsort(), to sort a list of unsigned longs in ascending
 * order.
 */
static int ul_comp(const void *p1, const void *p2)
{
	unsigned long a = *((unsigned long *)(p1));
	unsigned long b = *((unsigned long *)(p2));
	return b - a;
}

static double overhead_time;

/**
 * Calculate the execution time for a function, given a series of data
 * points. Compensate for how long it takes to measure time itself.
 *
 * <strong>You do not need to modify this function.</strong>
 *
 * @param[in] samples Array of raw execution times
 * @param[in] num_elems Number of elements in @a samples
 * @return Average execution time, in nanoseconds
 */
static double calc_execution_time(unsigned long *samples, unsigned num_elems)
{
	qsort(samples, NUM_TRIALS, sizeof(samples[0]), ul_comp);
	double median;
	median = samples[NUM_TRIALS / 2];
	if (median >= overhead_time)
		return median - overhead_time;
	return 0.1;
}

/**
 * Measure how long the system timing takes itself to execute.
 * <strong>You do not need to modify this function.</strong>
 * @return Overhead time, in nanoseconds
 */
static void measure_overhead(void)
{
	unsigned long samples[NUM_TRIALS];
	overhead_time = 0;
	for (unsigned i = 0; i < NUM_TRIALS; i++) {
		struct timespec start, stop;
		clock_gettime(CLOCK_MONOTONIC, &start);
		clock_gettime(CLOCK_MONOTONIC, &stop);
		samples[i] = clock_diff(&stop, &start);
	}
	overhead_time = calc_execution_time(samples, NUM_TRIALS);
}

/**
 * Measure how long it takes to execute a function, passing it one
 * parameter. Call it multiple times, and return the median execution
 * time.
 *
 * <strong>You do not need to modify this function.</strong>
 *
 * @param[in] target_func Function to execute
 * @param[in] val Parameter to pass into function
 * @param[out] retval Return value from calling @a target_func
 * @return Median execution time, in nanoseconds
 */
static double measure_function1(func1 target_func, int val, int *retval)
{
	unsigned long samples[NUM_TRIALS];
	for (unsigned i = 0; i < NUM_TRIALS; i++) {
		struct timespec start, stop;
		int r;
		clock_gettime(CLOCK_MONOTONIC, &start);
		r = target_func(val);
		clock_gettime(CLOCK_MONOTONIC, &stop);
		*retval = r;
		samples[i] = clock_diff(&stop, &start);
	}
	return calc_execution_time(samples, NUM_TRIALS);
}

/**
 * Measure how long it takes to execute a function, passing it two
 * parameters. Call it multiple times, and return the median execution
 * time.
 *
 * <strong>You do not need to modify this function.</strong>
 *
 * @param[in] target_func Function to execute
 * @param[in] val1 First parameter to pass into function
 * @param[in] val2 Second parameter to pass into function
 * @param[out] retval Return value from calling @a target_func
 * @return Median execution time, in nanoseconds
 */
static double measure_function2(func2 target_func, unsigned val1, unsigned val2, int *retval)
{
	unsigned long samples[NUM_TRIALS];
	for (unsigned i = 0; i < NUM_TRIALS; i++) {
		struct timespec start, stop;
		int r;
		clock_gettime(CLOCK_MONOTONIC, &start);
		r = target_func(val1, val2);
		clock_gettime(CLOCK_MONOTONIC, &stop);
		*retval = r;
		samples[i] = clock_diff(&stop, &start);
	}
	return calc_execution_time(samples, NUM_TRIALS);
}

/**
 * Measure how long it takes to execute a memcmp()-like function,
 * passing three parameters. Call it multiple times, and return the
 * median execution time.
 *
 * <strong>You do not need to modify this function.</strong>
 *
 * @param[in] target_func Function to execute
 * @param[in] n Number of bytes to compare
 * @param[out] retval Return value from calling @a target_func
 * @return Median execution time, in nanoseconds
 */
static double measure_function3(func3 target_func, size_t n)
{
	static unsigned seed = 0;
	unsigned long samples[NUM_TRIALS];
	unsigned char *buf1 = malloc(n);
	unsigned char *buf2 = malloc(n);
	if (!buf1 || !buf2) {
		perror("malloc");
		exit(EXIT_FAILURE);
	}
	unsigned i;
	for (i = 0; i < n; i++) {
		buf1[i] = buf2[i] = (unsigned char) seed;
		seed++;
	}
	int retval;

	/* first check that functions are implemented correctly */
	retval = target_func(buf1, buf2, n);
	if (retval != 0) {
		fprintf(stderr, "WARNING! Implementation failed when buffers are same!\n");
	}
	buf2[n - 1] = ~buf1[n - 1];
	retval = target_func(buf1, buf2, n);
	if (retval == 0) {
		fprintf(stderr, "WARNING! Implementation failed when buffers differ!\n");
	}
	buf2[n - 1] = buf1[n - 1];

	for (unsigned i = 0; i < NUM_TRIALS; i++) {
		struct timespec start, stop;
		clock_gettime(CLOCK_MONOTONIC, &start);
		target_func(buf1, buf2, n);
		clock_gettime(CLOCK_MONOTONIC, &stop);
		samples[i] = clock_diff(&stop, &start);
	}

	free(buf1);
	free(buf2);
	return calc_execution_time(samples, NUM_TRIALS);
}

int main(int argc, char *argv[])
{
	measure_overhead();

	int retval;
	double time_do_nothing = measure_function1(do_nothing, 0, &retval);
	printf("PART 1:\n");
	printf("do_nothing: execution time = %f ns\n", time_do_nothing);


	if (argc < 2) {
		fprintf(stderr, "Need at least one argument to continue\n");
		exit(EXIT_FAILURE);
	}


	printf("\nPART 2:\n");
	int target = atoi(argv[1]);
	double time_fib_unopt =
	    measure_function1(fibonacci_unoptimized, target, &retval);
	printf
	    ("fibonacci (unoptimized): result = %d, execution time = %f ns\n",
	     retval, time_fib_unopt);
	double time_fib_opt =
	    measure_function1(fibonacci_optimized, target, &retval);
	printf("fibonacci (optimized): result = %d, execution time = %f ns\n",
	       retval, time_fib_opt);
	/* PART 2: YOUR CODE HERE */


	if (argc < 4) {
		fprintf(stderr, "Need at least three arguments to continue\n");
		exit(EXIT_FAILURE);
	}


	printf("\nPART 3:\n");
	int dividend = atoi(argv[2]);
	int divisor = atoi(argv[3]);
	double time_div_iter =
		measure_function2(is_divisible_by_iterative, dividend, divisor, &retval);
	printf("%u is %s divisible by %u (iterative)\n", dividend,
	       (retval == 0 ? "not divisible" : "divisible"), divisor);
	printf("  execution time = %f ns\n", time_div_iter);
	double time_div_recur =
		measure_function2(is_divisible_by_recursive, dividend, divisor, &retval);
	printf("%u is %s divisible by %u (recursive)\n", dividend,
	       (retval == 0 ? "not divisible" : "divisible"), divisor);
	printf("  execution time = %f ns\n", time_div_recur);
	double time_div_asm =
		measure_function2(is_divisible_by_assembly, dividend, divisor, &retval);
	printf("%u is %s divisible by %u (assembly)\n", dividend,
	       (retval == 0 ? "not divisible" : "divisible"), divisor);
	printf("  execution time = %f ns\n", time_div_asm);


	if (argc < 7) {
		fprintf(stderr, "Need at least six arguments to continue\n");
		exit(EXIT_FAILURE);
	}


	printf("\nPART 4:\n");
	int i;
	for (i = 0; i < 3; i++) {
		int new_dividend = atoi(argv[i + 4]);
		/* PART 4: YOUR CODE HERE */
	}


	if (argc < 8) {
		fprintf(stderr, "Need at least seven arguments to continue\n");
		exit(EXIT_FAILURE);
	}


	printf("\nPART 5:\n");
	target = atoi(argv[7]);
	double time_memcmp = measure_function3(memcmp, target);
	printf("memcmp (built-in): execution time = %f ns\n", time_memcmp);
	double time_memcmp_8bit = measure_function3(memcmp_8bit, target);
	printf("memcmp (8 bits at a time): execution time = %f ns\n",
	       time_memcmp_8bit);
	double time_memcmp_32bit = measure_function3(memcmp_32bit, target);
	printf("memcmp (32 bits at a time): execution time = %f ns\n",
	       time_memcmp_32bit);
	double time_memcmp_64bit = measure_function3(memcmp_64bit, target);
	printf("memcmp (64 bits at a time): execution time = %f ns\n",
	       time_memcmp_64bit);
	double time_memcmp_256bit = measure_function3(memcmp_256bit_assembly, target);
	printf("memcmp (256 bits at a time): execution time = %f ns\n",
	       time_memcmp_256bit);

	return 0;
}