Code:
/***************************************************************
*
* Dependencies:
* - gcc version 4.3.3 (Ubuntu 4.3.3-5ubuntu4).
* - stdio.h
* - stdlib.h
* - math.h
*
* Purpose:
* This program provides a command line interface to compute the
* following function:
*
* II = SUM( I[i-col]*I[i-row] ) from i = c to i = N-1
*
* where I is the input array (file name given by user)
* c is array dim given by user
* N is summation sentinel
*
* the above three parameters are expected when invoking this
* program:
* <prog name> <input file name> <c> <N>
*
***************************************************************/
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <time.h>
/* defines for verification */
#undef VERIFY
#ifdef VERIFY
#define VALIDATION_FILE "test.txt_299_300"
#define VER_VALUE 1000000
#endif
/* Function declarations.
* explanations given in respective function header
*/
void fnc(int c, int N, float *src, float **res);
void printMatrix(int c, float **res);
float * alloc1D(int N);
float ** alloc2D(int c, int N);
int initArray(int N, float *ar, char *fname);
int checkArgs( int argc, char *argv[], int *c, int *N);
int cleanup(float *src, float **res, int *c, int *N);
#ifdef VERIFY
int checkRes(int c, char fname[], float **res);
#endif
int main( int argc, char *argv[] ) {
/* Variable declarations:.*/
int *c;
int *N;
float *src;
float **res;
c = malloc(sizeof(*c));
N = malloc(sizeof(*N));
/* check arguments, allocate source and result array
* and initialize source array with data from file
*/
if (checkArgs(argc, argv, c, N)) return EXIT_FAILURE;
if ((src = alloc1D(*N)) == NULL) return EXIT_FAILURE;
if ((res = alloc2D(*c, *N)) == NULL) return EXIT_FAILURE;
if ((*N = initArray(*N, src, argv[1])) == -1) return EXIT_FAILURE;
/* start the timer and compute the function */
clock_t start = clock();
fnc(*c, *N, src, res);
/* print out stats and result */
fprintf(stdout, "\nCalculating II from file data: %s, with N = %d, c = %d\n", argv[1], *N, *c-1);
printMatrix(*c, res);
#ifdef VERIFY
if (checkRes(*c, VALIDATION_FILE, res))
fprintf(stdout, "\nValidation did not succeed!\nResult may be incorrect!\n");
else
fprintf(stdout, "\nResult validated (correct to within %f)!\n\n", (float)1/VER_VALUE);
#endif
printf("Execution time in seconds: %.15lf\n", ((double)clock()-start)/CLOCKS_PER_SEC);
/* Finally, free allocated memory and return*/
return cleanup(src, res, c, N);
}
/* fnc(): This is the actual computation of the sum.
*
* args: c - specifies array size
* N - specifies sum sentinel
* *src - the source data
* **res - result data array
*
* return: Nothing
*/
void fnc(int c, int N, float *src, float **res) {
int row, col, i;
/* since the array is mirrored about the diagonal,
* we only compute part of the array.
* this significantly reduces the computation time
* and memory requirements
* The inner-most for-loop computes the summation
* SUM(I[i-col]*I[i-row]) from i = c to N-1 for
* the bottom left triangle.
*/
for (row = 0; row < c; row++) {
for (col = 0; col < row+1; col++) {
res[row][col] = 0;
for (i = c-1; i < N; i++)
res[row][col] += src[i-col]*src[i-row];
}
}
}
/* checkArgs(): this function checks the command line
* arguments for valid input. We also assign *c and *N
* here.
*
* args: argc - the # of args passed into main
* argv[] - the actual arguments
* *c - pointer to where c should be stored
* *N - pointer to where N should be stored
*
* return: EXIT_FAILURE or EXIT_SUCCESS
*/
int checkArgs(int argc, char *argv[], int *c, int *N) {
/* the number of command line arguments must be not less and
* not more than 4. <prog name> <input file> <N> <c>.
* print out usage instructions and return.
*/
if ( (argc < 4) | (argc > 4)) {
fprintf(stderr, "Usage: %s <input file> <N> <c>\n", argv[0]);
return EXIT_FAILURE;
}
/* we check here to make sure a valid file is provided
* before doing anything else.
*/
if (!(fopen(argv[1], "r"))) {
fprintf(stderr, "Cannot open file %s\n", argv[1]);
return EXIT_FAILURE;
}
/* assign c and N, and make sure c < N
* Note, it is assumed that these are ints
* The program's behavior is undefined if these are not ints,
* but does seem to handle invalid inputs gracefully.
*/
if ((*c = atoi(argv[2])) > (*N = atoi(argv[3]))-1) {
fprintf(stderr, "c must be strictly smaller than N!\n");
return EXIT_FAILURE;
}
*c += 1;
return EXIT_SUCCESS;
}
/* initArray(): loads the source data array with data from
* the given file.
* if N is specified to be larger than the number of data
* elements found in the file, N will be capped to the
* number of data elements.
* returns *N, possibly modified, in case N is capped.
*
* args: *N - the size of the array to be init'ed
* *ar - the pointer to the array to be filled
* fname[] - the filename to read data from
*
* return: *N. If the user specifies N greater than
* data available in fname, N is capped
* to reflect the nbr of data elements
* NOTE: If fopen fails, -1 is returned.
*/
int initArray(int N, float *ar, char fname[]) {
int i = 0;
FILE *fp = fopen( fname, "r");
/* check if fopen succeeded, then read the file until the
* end-of-file (EOF) is reached or we have reached N
*/
if (fp == NULL) {
fprintf(stderr, "Cannot open file %s\n", fname);
/* return -1 because we need to be able to check for failure
* (vs valid N) in checkRes if VERIFY is defined.
*/
return -1;
}
while((fscanf( fp, "%f", &ar[i++]) != EOF) & ((i-1) < N)){}
fclose(fp);
/* if N is actually larger than the size of the data array,
* we return i so that N can be set to the actual number of
* data elements
* The reason for i-1 is that i is actually incremented once
* for EOF, so we need to sub 1 from i
*/
if ((i-1) < N) {
fprintf(stderr, "WARNING:\nWill only use the N=%d data elements found in %s\n", (i-1), fname);
return i-1;
}
return N;
}
/* alloc1D(): allocates memory and error-check for the 1-d source
* data array.
*
* args: size - the size of the array to be allocated
*
* return: pointer to the array initialized. May be NULL
* if malloc fails.
*/
float * alloc1D(int size) {
float *ar;
/* try and allocate float array of size 'size',
* return pointer to start of array, return null if unsuccessful
*/
if ((ar = malloc(sizeof(*ar)*(size+1))) == NULL){
fprintf(stderr, "Could not allocate memory for 1D array!\n");
return NULL;
}
return ar;
}
/* alloc2D(): allocates memory and error-check for the 2-D triangular
* array to hold the result data
*/
float ** alloc2D(int c, int N) {
int i = 0;
float **ar = NULL;
/* try and allocate memory for the row pointers of the
* triangular array that stores the result
*/
if ((ar = (float **)alloc1D(c)) == NULL ) return ar;
/* now we allocate memory for the columns.
* since the result is actually mirrored about the top left to bottom right
* diagnoal, we only allocate memory for the bottome left triangle.
* this saves memory and allows for faster computation.
*/
for (i = 0; i < c; i++) {
ar[i] = malloc(sizeof(**ar)*(i+1));
if (ar[i] == NULL){
fprintf(stderr, "Could not allocate 2-D memory for result data!\n");
return NULL;
}
}
return ar;
}
/* printMatrix(): prints out the triangular array as a full
* square array.
*/
void printMatrix(int c, float **res) {
int row, col;
printf("\n");
for (row = 0; row < c; row++) {
fprintf(stdout, "%s", (row==c/2)?"II = | ":" | ");
for (col = 0; col < c; col++) {
/* since we only computed part of the array, and the matrix has the
* property such that res[i][j] == res[j][i], we need to print
* selectively depending on the relative values of row and col
*/
fprintf(stdout, "%f ", (row>col)?res[row][col]:res[col][row]);
}
fprintf(stdout, "|\n");
}
printf("\n");
}
/* cleanup(): deallocates all the allocated memory */
int cleanup(float *src, float **res, int *c, int *N) {
int i;
if (src) free(src);
if (N) free(N);
if (res)
for (i = 0; i < *c; i++)
free(res[i]);
free(res);
if (c) free(c);
return ((res == NULL) & (src == NULL) & (c == NULL) & (N == NULL));
}
/* checkRes(): given golden result in a file, this function
* validates the computed result.
* expects data from file in colum order. i.e.
* 0
* 1 3
* 2 4 5
*/
#ifdef VERIFY
int checkRes(int c, char fname[], float **res) {
float *gres;
int row, col, k;
int *n = malloc(sizeof(*n));
fprintf(stdout, "Validating result against %s.\n", VALIDATION_FILE);
/* triangular array size is c + (c-1) + ... + 1 */
*n = 0;
for (k = c; k > 0; k--)
*n += k;
/* try to allocate and initialize array for golden result */
if ((gres = alloc1D(*n)) == NULL) {
fprintf(stderr, "Could not allocate memory for golden result data!\n");
return EXIT_FAILURE;
}
if ((initArray(*n, gres, fname)) == -1) return EXIT_FAILURE;
/* compare computed result to golden result */
k=0;
for (col = 0; col < c; col++)
for (row = col; row < c; row++) {
if ((fabs((double)res[row][col]-(double)gres[k]))*VER_VALUE > 1){
return EXIT_FAILURE;
}
k++;
}
cleanup(gres, NULL, n, NULL);
return EXIT_SUCCESS;
}
#endif