#include <stdio.h>
#include <string.h>
#include <mpi.h>
#include "fib_reduce.h"

int Fib_Reduce(const void *sendbuf, void *recvbuf, int count,
		MPI_Datatype datatype, MPI_Op op, int root, MPI_Comm comm) {
	if (root != 0) {
		fprintf(stderr, "Sorry, root!=0 not allowed");
		return -1;
	}

	int r, p, size;
	MPI_Status status;
	void *recv_right;

	MPI_Comm_rank(comm, &r);
	MPI_Comm_size(comm, &p);
	MPI_Type_size(datatype, &size);

	int temp;
	int right = 1;
	int fib = 1;

	while (fib - 1 < p) {
		temp = fib;
		fib += right;
		right = temp;
	}

	int left = fib - right;
	int i = 0;
	int parent = 0;

	while (i != r) {
		parent = i;
		if (r >= i + left) {
			i += left;
			temp = left;
			left = right - left;
			right = temp;
		} else {
			i++;
			right -= left;
			left -= right;
		}
	}

	if (r == root) {
		recv_right = recvbuf;
	} else {
		MPI_Alloc_mem(size * count, MPI_INFO_NULL, &recv_right);
	}

	if (right - 1 > 0 && r + 1 < p) {
		void *recv_left;
		MPI_Alloc_mem(count * size, MPI_INFO_NULL, &recv_left);
		MPI_Recv(recv_left, count, datatype, r + 1, 0, comm, &status);
		MPI_Reduce_local(sendbuf, recv_left, count, datatype, op);

		if (left - 1 > 0 && r + left < p) {
			MPI_Recv(recv_right, count, datatype, r + left, 0, comm, &status);
			MPI_Reduce_local(recv_left, recv_right, count, datatype, op);
		} else {
			memcpy(recv_right, recv_left, count * size);
		}

		MPI_Free_mem(recv_left);
	} else {
		memcpy(recv_right, sendbuf, count * size);
	}

	if (r != root) {
		MPI_Send(recv_right, count, datatype, parent, 0, comm);
		MPI_Free_mem(recv_right);
	}

	return 0;
}