/*
 * Getting Started With the ADSP-BF537 EZ-KIT Lite
 * Part 1, Exercise 2
 */

#include <stdlib.h>
#include <stdio.h>
#include <ccblkfn.h>
#include <cdefbf533.h>
#include <sysreg.h>
#include <time.h>

#define NUM_ITERATIONS   5000
#define ARRAY_LENGTH     128


void start_real_time_clock(void);
unsigned int get_real_time_clock_in_seconds(void);

/* Helper function to enable the real-time clock and reset it to time "zero" */
#define WAIT_FOR_RTC_WRITE_COMPLETE()  { 	while ( *pRTC_ISTAT & 0x8000 ); }

void start_real_time_clock ()
{
	if ( !*pRTC_PREN )
	{
		*pRTC_PREN = 1;
		WAIT_FOR_RTC_WRITE_COMPLETE();
	}
	
	*pRTC_STAT = 0;
	WAIT_FOR_RTC_WRITE_COMPLETE();
}


/* Help function to get the number of seconds since "zero" time.
 * Only works up to one hour of time. */
unsigned int get_real_time_clock_in_seconds ()
{
	unsigned int clock = *pRTC_STAT;
	
	/* second */
	unsigned int seconds = ( clock & 0x3f );
	
	/* minutes */
	seconds += 60 * ( clock & 0xfc0 ) >> 6;
	
	return seconds;
}
	
/* Initialize two arrays to the same set of random values */
void randomize_arrays ( int *v1, int *v2, unsigned int length )
{
	unsigned int i;
	
	for ( i = 0; i < length; ++i )
	{
		v1[ i ] = v2[ i ] = rand () % 1024;
	}
}

/* A standard bubble sort algorithm, O(n^2) */
/*section("L1_code")*/ void bubble_sort ( int *v, unsigned int length )
{
	unsigned int i, j;
	
	for ( i = 0; i < length - 1; ++i )
	{
		for ( j = i + 1; j < length; ++j )
		{
			if ( v[ i ] > v[ j ] )
			{
				int temp = v[ i ];
				v[ i ] = v[ j ];
				v[ j ] = temp;
			}
		}
	}
}

/* A standard quick sort algorithm, O(n*log(n)) */
void quick_sort ( int *v, unsigned int p, unsigned int r )
{
	if ( p < r )
	{
		unsigned int x, i, j, q;
		
		x = v[ p ];
		i = p - 1;
		j = r + 1;
		
		for ( ;; )
		{
			do { --j; } while ( v[ j ] > x );
			do { ++i; } while ( v[ i ] < x );
			
			if ( i < j )
			{
				int temp = v[ i ];
				v[ i ] = v[ j ];
				v[ j ] = temp;
			}
			else
			{
				q = j;
				break;
			}
		}
		
		quick_sort ( v, p, q );
		quick_sort ( v, q + 1, r );
	}
}

int out_b[ ARRAY_LENGTH ];
int out_m[ ARRAY_LENGTH ];

void main ()
{
	clock_t cycles_begin, cycles_end;
	unsigned long seconds_begin, seconds_end;
	unsigned long display_cycles_end;
	volatile unsigned int time_end;
	int i;
	
	srand ( 22 );
	
	start_real_time_clock ();
	
	cycles_begin = clock ();
	
	for ( i = 0; i < NUM_ITERATIONS; ++i )
	{
		int j;
		
		randomize_arrays ( out_b, out_m, ARRAY_LENGTH );
		bubble_sort ( out_b, ARRAY_LENGTH );
		quick_sort ( out_m, 0, ARRAY_LENGTH - 1 );
	}

	cycles_end = clock () - cycles_begin;
	display_cycles_end = ( unsigned long ) ( cycles_end / 1000000 );
	
	time_end = get_real_time_clock_in_seconds ();
	
	printf ( "Completed in %d seconds and approx. %u million cycles.\n",
			time_end, display_cycles_end );
}