Guys,
I'm pretty new at C programming, nevertheless I am currently interviewing for an embedded sw position. As part of the interview I was given a coding exercise in C.
I would appreciate if you guys could give some constructive feedback on coding and style. I'm open to any and all suggestions on style, good coding practices and code optimization (both for memory and performance).
Thanks a lot!
The Problem Statement:
Implement a function in C to perform the computation described below. Then implement a program to test the function. The input data for the test program shall be provided in the file TEST.PRN, and consists of an array of floating point numbers, one per line. The output of the test program shall consist of the matrix II displayed to standard output, with one row of II being displayed per line. The test program shall provide for command line options to specify the input data file to be processed, and for the value of c and N.
My Solution:
If you look at the equation for the summation (in the file header comment), you will see that the solution matrix is actually symmetric, and mirrored about the array diagonal (from top left to bottom right). So, I decided to only allocate memory for a triangular array and compute only what is necessary. That's pretty much the only optimization that I can see. Any ideas are welcome. As for parallelizing, I was thinking to maybe use pthreads, but somehow I feel that may be a bit of overkill. On the other hand, it's for a job... so any ideas on that are also welcome!
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