driver.cpp

卡耐基SSD6全部选择题和练习题解决方法。

/*

  driver.c

  Driver program.

*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>
#include <assert.h>
#include <math.h>
#include <signal.h>
#include "defs.h"
#include "cache.h"


#define FIND_BEST_OF_MANY


/*******************************************
 *******************************************
 *
 *		FILE-GLOBAL DECLARATIONS
 *
 *******************************************
 *******************************************
 */


/* Keep track of a number of different test functions */
#define MAX_BENCHMARKS 100
#define DIM_CNT 5



/* 
 * defining FIND_BEST_OF_MANY might help you sift through many different functions;
 *  if it is defined, the program will print the name and speed of the best function for each size tested.
 */
#ifdef FIND_BEST_OF_MANY
char* best_desc;
double best_mean;
#endif



/* struct to hold all information about a certain function to be tested */
typedef struct {
	lab_test_func tfunct;
	int cache_hits[DIM_CNT];
	int cache_attempts[DIM_CNT];
	float cache_hitrate[DIM_CNT];
	char *description;
	unsigned short valid; /* The function is tested if this is non zero */
} bench_t;


/* keep track of benchmarks */
static bench_t benchmarks_rotate[MAX_BENCHMARKS];
static int rotate_benchmark_count = 0;
static bench_t benchmarks_smooth[MAX_BENCHMARKS];
static int smooth_benchmark_count = 0;


/* Define block size for aligning data */
#define BSIZE 64
#define MAX_DIM 1280 /* 1024+256 */
#define ODD_DIM 96 /* not a power of 2, not a dimension that will be scored for speed */

/* giant array to hold all three image matrices */
static pixel data[3*MAX_DIM*MAX_DIM+BSIZE/sizeof(pixel)];

/* pointers to each image matrix */
static pixel *orig = 0;
static pixel *copy_of_orig = 0;
static pixel *result = 0;

/* sizes we will be testing */
static int test_dim[] = {64, 128, 256, 512, 1024};


/*******************************************
 *******************************************
 *
 *			STATIC FUNCTIONS
 *
 *******************************************
 *******************************************
 */


/* Returns random integer in interval [low, high) */
static int random_in_interval(int low, int high) {
	int size = high - low;

	return (rand()% size) + low;
}


static int clean_up_matrix[128][128];
static void clean_up_cache(){
	int i,j;
	for(i=0; i<1000; i++){
		for(j=0; j<1000; j++){
			clean_up_matrix[i][j] = 0;
		}
	}
}


/* create a dim*dim image of random contents */
static void create(int dim)
{
	int i, j;
	
	orig = data;
	while ((unsigned) orig % BSIZE) {
		orig++;
	}
	result = orig + dim*dim;
	copy_of_orig = result + dim*dim;

	for(i=0; i<dim; i++) {
		for(j=0; j<dim; j++) {
			/* Original image initialized to random colors */
			orig[PIXEL(i,j,dim)].red = random_in_interval(0, 256);
			orig[PIXEL(i,j,dim)].green = random_in_interval(0, 256);
			orig[PIXEL(i,j,dim)].blue = random_in_interval(0, 256);
			//orig[PIXEL(i,j,dim)].alpha = random_in_interval(0, 256);
			/* Copy of original image for checking result */
			copy_of_orig[PIXEL(i,j,dim)].red = orig[PIXEL(i,j,dim)].red;
			copy_of_orig[PIXEL(i,j,dim)].green = orig[PIXEL(i,j,dim)].green;
			copy_of_orig[PIXEL(i,j,dim)].blue = orig[PIXEL(i,j,dim)].blue;
			//copy_of_orig[PIXEL(i,j,dim)].alpha = orig[PIXEL(i,j,dim)].alpha;
			/* Result image initialized to all black */
			result[PIXEL(i,j,dim)].red = 0;
			result[PIXEL(i,j,dim)].green = 0;
			result[PIXEL(i,j,dim)].blue = 0;
			//result[PIXEL(i,j,dim)].alpha = 0;
		}
	}
	return;
}


/* unimplemented */
static void cleanup(int dim) {
	return;
}


/* Returns 1 if the two arguments don't have same RGBA values, 0 o.w. */
static int compare_pixels(pixel p1, pixel p2) {
	return (p1.red != p2.red) || (p1.green != p2.green) || (p1.blue != p2.blue) || 0/*(p1.alpha != p2.alpha)*/;
}


/* Make sure the orig array is unchanged */
static int check_orig(int dim) {
	int i, j;

	for (i = 0; i < dim; i++) 
		for (j = 0; j < dim; j++) 
			if (compare_pixels(orig[PIXEL(i,j,dim)], copy_of_orig[PIXEL(i,j,dim)])) {
		printf("\n");
		printf("Error: Original image has been changed!\n");
		printf("Changed at position %d, %d\n", i, j);
		printf("A: (%d, %d, %d)\nB: (%d,%d,%d)\n",
				orig[PIXEL(i,j,dim)].red,
				orig[PIXEL(i,j,dim)].green,
				orig[PIXEL(i,j,dim)].blue,
				copy_of_orig[PIXEL(i,j,dim)].red,
				copy_of_orig[PIXEL(i,j,dim)].green,
				copy_of_orig[PIXEL(i,j,dim)].blue);
		return 1;
	}

	return 0;
}

/* Make sure the rotate actually works. The orig array should not 
	 have been tampered with! 
*/
static int check_rotate(int dim) {
	int err = 0;
	int i, j;
	int badi = 0;
	int badj = 0;
	pixel orig_bad, res_bad;

	if (check_orig(dim)) return 1; /* return 1 if original image has been
				 changed */

	for (i = 0; i < dim; i++) 
		for (j = 0; j < dim; j++) 
			if (compare_pixels(orig[PIXEL(i,j,dim)], result[PIXEL(dim-1-j,i,dim)])) {
	err++;
	badi = i;
	badj = j;
	orig_bad = orig[PIXEL(i,j,dim)];
	res_bad = result[PIXEL(dim-1-j,i,dim)];
			}
	
	if (err) {
		printf("\n");
		printf("ERROR: Dimension=%d, %d errors\n", dim, err);		
		printf("E.g., The following two pixels should have equal value:\n");
		printf("src[%d][%d].{red,green,blue,alpha} = {%d,%d,%d}\n",
		 badi, badj, orig_bad.red, orig_bad.green, orig_bad.blue); 
					//, orig_bad.alpha);
		printf("dst[%d][%d].{red,green,blue, alpha} = {%d,%d,%d}\n",
		 (dim-1-badj), badi, res_bad.red, res_bad.green, res_bad.blue);
					//, res_bad.alpha);
	}

	return err;
}

/* Make sure the smooth actually works. The orig array should not 
	 have been tampered with! 
*/
static int check_smooth(int dim) {
	int err = 0;
	int i, j;
	int badi = 0;
	int badj = 0;
	pixel p, orig_bad, res_bad;

	if (check_orig(dim)) return 1; /* return 1 if original image has been
				 changed */

	for( i=0; i < dim; i++ ) {
		for( j=0 ; j < dim ; j++ ) {
			if (i != 0 && j != 0 && i != (dim - 1) && j != (dim - 1)) {
				cache_smooth(&p, &orig[PIXEL(i,j,dim)],
						&orig[PIXEL(i-1,j,dim)],
						&orig[PIXEL(i+1,j,dim)],
						&orig[PIXEL(i,j-1,dim)],
						&orig[PIXEL(i,j+1,dim)],
						&orig[PIXEL(i-1,j-1,dim)],
						&orig[PIXEL(i+1,j+1,dim)],
						&orig[PIXEL(i-1,j-1,dim)],
						&orig[PIXEL(i+1,j+1,dim)]);
			}
			else {
				cache_copy(&p, &orig[PIXEL(i, j, dim)]);
			}
			
			if(compare_pixels(p, result[PIXEL(i,j,dim)]))
			{
				err++;
				badi = i;
				badj = j;
				orig_bad = p;
				res_bad = result[PIXEL(i,j,dim)];
			}
		}
	}
	
	if (err) {
		printf("\n");
		printf("ERROR: Dimension=%d, %d errors\n", dim, err);		
		printf("E.g., The following two pixels should have equal value:\n");
		printf("src[%d][%d].{red,green,blue,alpha} = {%d,%d,%d}\n",
		 badi, badj, orig_bad.red, orig_bad.green, orig_bad.blue); 
					//, orig_bad.alpha);
		printf("dst[%d][%d].{red,green,blue, alpha} = {%d,%d,%d}\n",
		 badi, badj, res_bad.red, res_bad.green, res_bad.blue);
					//, res_bad.alpha);
	}

	return err;
}


static void print(int dim, pixel *screen){
	int i, j;

	assert(screen != 0);

	for (j = 0; j < dim; j++){
		for (i = 0; i < dim; i++){
			int rval, bval, gval;
			rval = (int) screen[PIXEL(i,j,dim)].red;
			gval = (int) screen[PIXEL(i,j,dim)].green;
			bval = (int) screen[PIXEL(i,j,dim)].blue;
			//bval = (int) screen[PIXEL(i,j,dim)].alpha;
			printf("%d ", rval+bval+gval);
		}
		printf("\n");
	}	

	return;
}


static void func_wrapper(void *arglist[]) {
	pixel *src, *dst;
	int mydim;
	lab_test_func f;

	f = (lab_test_func) arglist[0];
	mydim = *((int *) arglist[1]);
	src = (pixel *) arglist[2];
	dst = (pixel *) arglist[3];

	(*f)(mydim, src, dst);

	return;
}

static char rotate_naive_reference_descr[] = "Rotate Reference Naive Implementation!";
static void rotate_naive_reference(int dim, pixel* src, pixel* dst) {
	int i, j;
	for(i=0; i<dim; i++) {
		for(j=0; j<dim; j++) {
			COPY(&dst[PIXEL(dim-1-j,i,dim)], &src[PIXEL(i,j,dim)]);
		}
	}
}

static char smooth_naive_reference_descr[] = "Smooth Reference Naive Implementation!";
static void smooth_naive_reference(int dim, pixel* src, pixel* dst) {
	int i, j;
	for(i=0; i<dim;i++) {
		COPY(&dst[PIXEL(i,0,dim)], &src[PIXEL(i,0,dim)]);
		COPY(&dst[PIXEL(i,dim-1,dim)], &src[PIXEL(i,dim-1,dim)]);
	}
	for(j=1; j<dim-1;j++) {
		COPY(&dst[PIXEL(0,j,dim)], &src[PIXEL(0,j,dim)]);
		COPY(&dst[PIXEL(dim-1,j,dim)], &src[PIXEL(dim-1,j,dim)]);
	}
	for(i=1; i<dim-1; i++) {
		for(j=1; j<dim-1; j++) {
			SMOOTH(&dst[PIXEL(j,i,dim)],
					&src[PIXEL(j,i,dim)],
					&src[PIXEL(j-1,i,dim)],
					&src[PIXEL(j+1,i,dim)],
					&src[PIXEL(j,i+1,dim)],
					&src[PIXEL(j,i-1,dim)],
					&src[PIXEL(j-1,i-1,dim)],
					&src[PIXEL(j+1,i+1,dim)],
					&src[PIXEL(j-1,i+1,dim)],
					&src[PIXEL(j+1,i-1,dim)]);
		}
	}
}



static void run_rotate_benchmark(int idx, int dim) {