...

View Full Version : Not sure what's causing this Segmentation Fault



ChristianTool
11-25-2004, 08:38 PM
I'm having a problem with my latest program. Essentially, it's a program that tests every possible number from 111111111 to 999999999, and I'm getting a seg fault every time at 100131018. The recursive function is below. I'm having it print the test value just as a probe to see what's going on, but the seg fault occurs when it's not there, just alot faster.



void Permute ( int array[], INFO permInfo, FILE *output )
{
int i;
long counter;
counter = pow(10, permInfo.numItems-1);

if ( permInfo.testValue <= permInfo.maxValue )
{
for ( i = 0; i < permInfo.numItems; i++ )
{
array[i] = permInfo.testValue / counter;
counter /= 10;
}
if ( permInfo.numItems > 1 )
{
for ( i = permInfo.numItems; i != 0; i--)
{
array[i] -= array[i-1] * 10;
}
}

permInfo.testValue++;
Permute( array, permInfo, output );
}

}


The structure definition is below, if it helps.


typedef struct info
{
long testValue;
int numItems;
long maxValue;
char userChoice;
} INFO;


And here's the call to malloc.


int *array = malloc(sizeof (int) * permInfo.numItems);


Any ideas??

Edit : Happy Thanksgiving everybody.

aman
11-26-2004, 08:42 AM
I don't know what values you are passing in as part of the permInfo struct to start with, but two things come to mind.. 1) check to make sure counter is never 0 because you'll get a dbz error, and 2) you may be running out of stack memory with such a huge recursive function. You can increase the stack size (check your compiler's documentation) or better yet re-think your program so you don't need to use a recursive function for such huge operations.

ChristianTool
11-26-2004, 04:49 PM
Essentially if it's a 2x2 magic square ( which would be just a 4 element one-dimensional array ), I have to test every value from 1234 to 9876. Counter would be 10^3. Based on that, I'm pretty sure it would never reach 0.

Unfortunately, it's a program requirement for the Permute function to be recursive. How would I go about checking my compiler's documentation to increase the stack size? I'm using the GCC compiler.

Edit: Unless you could think of a better way to do it. A magic square is a square in which the sum of the rows vertically, horizontally, and diagonally are all the same. An example is :

816
357
492

My problem is, I can't think of a way to use that recursive function to test numbers with each integer being used only once. I.e. For a 3x3 square I'd ideally like to try and test 123456789 then 132456789, etc. That would significantly decrease the size of the stack

aman
11-26-2004, 10:09 PM
Have you tried compiling your code with debugging information and running it in gdb debugger? Everything you wanted to know about gcc (http://gcc.gnu.org/)

ChristianTool
11-26-2004, 11:15 PM
Whenever I run it, it exits with the following.


Program received signal SIGSEGV, Segmentation fault.
0x40024963 in sqrt () from /lib/i686/libm.so.6
I've been looking around for an explanation of that, with no luck. Not TOO familiar with gdb, couldn't figure out where it was occuring.

As for increasing the stack size, I've googled it but haven't really seen anything I'd know how to work with.

aman
11-26-2004, 11:40 PM
Yea try stepping through the stack, type help at the gdb prompt or find everything you wanted to know about gdb (http://www.gnu.org/software/gdb/gdb.html)

Also I could try running it if I knew what are the values of the struct you pass in...

ChristianTool
11-27-2004, 12:29 AM
Sure let me show you the rest of the code while I try and mess with GDB.

Here's magic.c


#include <stdio.h>
#include <stdlib.h>
#include "magic.h"

/* Prints a greeting/explanation to the user */
/* Name: PrintGreeting */
/* Inputs : none */
/* Returned value : none */
void PrintGreeting (void)
{
printf( "\nWelcome to the Magic Square program.");
printf( "\nThis program will calculate the possible");
printf( "\npermutations of a magic square.");
printf( "\nTo use this program, simply select whether");
printf( "\nyou want to display the squares to screen,");
printf( "\nhave them written to a file, or quit");
printf( "\n\nIn case you were wondering, a magic square");
printf( "\nis a square in which each number is used only");
printf( "\nonce, and the sum of it's rows, columns, and");
printf( "\ndiagonal lines are all the same. Simply run the");
printf( "\nprogram for a better example.\n");
}

/* Calculates all the possible permutations of a magic square */
/* Name: Permute */
/* Inputs : array of ints, starting point to analyze */
/* Returned value : none */
void Permute ( int array[], INFO permInfo, FILE *output )
{
int i;
long counter;
counter = pow(10, permInfo.numItems-1);

if ( permInfo.numItems == 1 )
{
permInfo.maxValue = 1;
}

if ( permInfo.testValue <= permInfo.maxValue )
{
for ( i = 0; i < permInfo.numItems; i++ )
{
array[i] = permInfo.testValue / counter;
counter /= 10;
}
if ( permInfo.numItems > 1 )
{
for ( i = permInfo.numItems; i != 0; i--)
{
array[i] -= array[i-1] * 10;
}
}

if ( CheckMagic ( array, permInfo ) == 1 )
{
if ( CheckUnique ( array, permInfo ) == 1 )
{
if ( permInfo.userChoice == 'D' || permInfo.userChoice =='d' )
{
PrintToScreen ( array, permInfo );
}
else
{
PrintToFile ( array, permInfo, output );
}
}
}
permInfo.testValue++;
Permute( array, permInfo, output );
}
}

/* Prints the user's choices, gets, and returns a valid response */
/* Name: GetUserChoice */
/* Inputs : none */
/* Returned value : none */
char GetUserChoice (void)
{
char choice, trash;

printf("\n D - Display to Screen \n");
printf("\n W - Write to File \n");
printf("\n Q - Quit \n");
printf("\nEnter your choice : ");
scanf ("%c%c", &choice, &trash );
fflush (stdin);

switch (choice)
{
case 'D':
return choice;
case 'd':
return choice;
case 'W':
return choice;
case 'w':
return choice;
case 'Q':
return choice;
case 'q':
return choice;
default :
fprintf( stderr, "\nPlease enter a valid response.\n");
return GetUserChoice();
}

return choice;
}

/* Verifies the sum of the diagonal, vertical, and horizontal */
/* lines are equal */
/* Name: CheckMagic */
/* Inputs: array containing magic square, number of items */
/* Returned values: true/false integer */
int CheckMagic ( int array[], INFO permInfo )
{
int i, j, k = 0, numItems;
long oldSum, newSum;

numItems = permInfo.numItems;

if ( numItems == 1 )
{
return 1;
}

/* HORIZONTAL CHECK */
for ( i = 0; i < (int)sqrt(numItems); i++ )
{
oldSum = array[i];

for ( j = 0; j <= (sqrt(numItems)) - 1; j++ )
{
oldSum = oldSum + array[k];
k++;
}

if ( i > 1 )
{
if ( newSum != oldSum )
{
return 0;
}
}
newSum = oldSum;
}

oldSum = newSum = k = 0;

/* VERTICAL CHECK */
for ( i = 0; i < sqrt(numItems); i++ )
{
oldSum = array[i];
for ( j = 0; j < sqrt(numItems) - 1; j++ )
{
k = k + sqrt(numItems);
oldSum = oldSum + array[k];
}

if ( i > 1 )
{
if ( newSum != oldSum )
{
return 0;
}
}
newSum = oldSum;
}

oldSum = k = 0;

/* DIAGONAL CHECK ONE */
oldSum = array[0];
for ( i = 0; i < sqrt(numItems) - 1; i++ )
{
k = k + (sqrt(numItems) + 1 );
oldSum = oldSum + array[k];
}

if ( oldSum != newSum )
{
return 0;
}

newSum = oldSum;

/* DIAGONAL CHECK TWO */
k = numItems - sqrt(numItems);
oldSum = array[k];
for ( i = 0; i < sqrt(numItems) - 1; i++ )
{
k = k + (sqrt(numItems) - 1 );
oldSum = oldSum - array[k];
}

if ( oldSum != newSum )
{
return 0;
}

return 1;
}

/* Verifies that no number in the magic square is used twice */
/* Name: CheckUnique */
/* Inputs: array containing magic square, number of items */
/* Returned values: true/false value */
int CheckUnique ( int array[], INFO permInfo )
{
int numItems;
numItems = permInfo.numItems;
int uniqueArray[numItems], i, j;
numItems = permInfo.numItems;

for ( i = 0; i < numItems; i++ )
{
uniqueArray[i] = 0;
}


for ( i = 0; i < numItems; i++ )
{
for ( j = 0; j < numItems; j++ )
{
if ( array[i] == j )
{
uniqueArray[j]++;
}
}
}


for ( i = 0; i < numItems; i++ )
{
if ( uniqueArray[i] > 1 )
{
return 0;
}
}

return 1;
}

/* Prints the magic squares to the screen */
/* Name: PrintToScreen */
/* Inputs : array containing magic square, structure of information, */
/* and the output file pointer. */
/* Returned value : none */
void PrintToScreen ( int array[], INFO permInfo )
{
int numItems, i, j;

numItems = sqrt(permInfo.numItems);


for ( i = 0; i < numItems; i++ )
{
if ( i % numItems == 0 )
{
for ( j = 0; j < (numItems * 4 + 1); j++ )
{
printf("-");
}
printf("\n|");
}
printf(" %d |", array[i]);
}

printf("\n");
for ( j = 0; j < (numItems * 4 + 1); j++ )
{
printf("-");
}
printf("\n");

}

/* Prints the magic squares to the output file */
/* Name: PrintToFile */
/* Inputs : array containing magic square, structure of information, */
/* and the output file pointer. */
/* Returned value : none */
void PrintToFile ( int array[], INFO permInfo, FILE *output)
{
int numItems, i, j;

numItems = sqrt(permInfo.numItems);


for ( i = 0; i < numItems; i++ )
{
if ( i % numItems == 0 )
{
for ( j = 0; j < (numItems * 4 + 1); j++ )
{
fprintf( output, "-");
}
fprintf( output, "\n|");
}
fprintf( output, " %d |", array[i]);
}

fprintf( output, "\n");
for ( j = 0; j < (numItems * 4 + 1); j++ )
{
fprintf( output, "-");
}
fprintf( output, "\n");

}

/* Gets the maximim value of a possible permutation */
/* Name: GetMaxValue */
/* Inputs : structure of information about square */
/* Returned value : none */
void GetMaxValue ( INFO permInfo, long *maxValue )
{
int i;
int *array = malloc(sizeof (int) * permInfo.numItems);
long counter;

*maxValue = 0;

for ( i = permInfo.numItems - 1; i >= 0; i-- )
{
array[i] = i + 1;
}

counter = pow(10, permInfo.numItems - 1);

for ( i = permInfo.numItems - 1; i >= 0; i-- )
{
*maxValue += array[i] * counter;
counter /= 10;
}
free ( array );
}

/* Gets the initial value of a possible permutation and puts it in an array */
/* Name: GetTestValue */
/* Inputs : structure of information about square, array of integers */
/* Returned value : none */
void GetTestValue ( INFO permInfo, int array[], long *testValue )
{
int i;
long counter;
*testValue = 0;

for ( i = 0; i < permInfo.numItems; i++ )
{
array[i] = i + 1;
}

counter = pow(10, permInfo.numItems - 1);

for ( i = 0; i < permInfo.numItems; i++ )
{
*testValue += array[i] * counter;
counter /= 10;
}

}

ChristianTool
11-27-2004, 12:31 AM
Here's proj4.c :



#include <stdio.h>
#include <stdlib.h>
#include "magic.h"

int main ( int argc, char* argv[] )
{
FILE *output;
INFO permInfo;
long testValue, maxValue;

if ( argc != 3 )
{
fprintf ( stderr, "There must be at least three arguments : ");
fprintf ( stderr, "\nthe name of the executable file, the value");
fprintf ( stderr, "\nof N, and the name of the output file in");
fprintf ( stderr, "\nwhich to write the squares. Try again. \n\n");
exit ( -1 );
}

output = fopen ( argv[2], "w" );

if ( output == NULL )
{
fprintf ( stderr, "Error opening '%s', exiting program\n", argv[2] );
exit ( -1 );
}

PrintGreeting();
permInfo.userChoice = GetUserChoice();

if ( permInfo.userChoice == 'Q' || permInfo.userChoice == 'q' )
{
exit(-2);
}

sscanf( argv[1], "%d", &permInfo.numItems);
permInfo.numItems *= permInfo.numItems;

if ( permInfo.numItems == 1 )
{
permInfo.testValue = 1;
}

int *array = malloc(sizeof (int) * permInfo.numItems);

GetTestValue ( permInfo, array, &testValue );
GetMaxValue ( permInfo, &maxValue );

permInfo.testValue = testValue;
permInfo.maxValue = maxValue;

Permute ( array, permInfo, output );

fclose ( output );
free ( array );

return 0;
}


And here's the header file, magic.h


#include <math.h>

typedef struct info
{
long testValue;
int numItems;
long maxValue;
char userChoice;
} INFO;


/* Prints a greeting/explanation to the user */
/* Name: PrintGreeting */
/* Inputs : none */
/* Returned value : none */
void PrintGreeting (void);

/* Calculates all the possible permutations of a magic square */
/* Name: Permute */
/* Inputs : array of ints, starting point to analyze */
/* Returned value : none */
void Permute ( int array[], INFO permInfo, FILE *output );

/* Prints the user's choices, gets, and returns a valid response */
/* Name: GetUserChoice */
/* Inputs : none */
/* Returned value : none */
char GetUserChoice (void);

/* Verifies that no number in the magic square is used twice */
/* Name: CheckUnique */
/* Inputs: array containing magic square, number of items */
/* Returned values: true/false value */
int CheckUnique ( int array[], INFO permInfo );

/* Verifies the sum of the diagonal, vertical, and horizontal */
/* lines are equal */
/* Name: CheckMagic */
/* Inputs: array containing magic square, number of items */
/* Returned values: true/false integer */
int CheckMagic ( int array[], INFO permInfo );

/* Prints the magic squares to the output file */
/* Name: PrintToFile */
/* Inputs : array containing magic square, structure of information, */
/* and the output file pointer. */
/* Returned value : none */
void PrintToFile ( int array[], INFO permInfo, FILE *output);

/* Prints the magic squares to the screen */
/* Name: PrintToScreen */
/* Inputs : array containing magic square, structure of information, */
/* and the output file pointer. */
/* Returned value : none */
void PrintToScreen ( int array[], INFO permInfo );

/* Gets the maximim value of a possible permutation */
/* Name: GetMaxValue */
/* Inputs : structure of information about square */
/* Returned value : none */
void GetMaxValue ( INFO permInfo, long *maxValue );

/* Gets the initial value of a possible permutation and puts it in an array */
/* Name: GetTestValue */
/* Inputs : structure of information about square, array of integers */
/* Returned value : none */
void GetTestValue ( INFO permInfo, int array[], long *testValue );


Edit : Make sure you compile with -lm, because I'm using functions stored in math.h.

aman
11-27-2004, 01:42 AM
I don't have a monitor plugged into my linux box at the moment so I haven't tried it there, but in both VC and Cygwin gcc it seems to be choking on the pow() function and the value of counter. Place a watch on counter in the debugger to see what it is. With some input values it is 0 and you get a dbz crash. Olydbg also shows a dbz error. You should probably re-think that portion of the code.

ChristianTool
11-27-2004, 02:11 AM
Well the user will be restricted to either entering a 1, 2, or 3... I should have mentioned. Also, I assume you figured out the command line arguments? I forgot to mention that as well. I changed the code for counter to


long counter = 1;
for ( i = 0; i < permInfo.numItems - 1; i++ )
{
counter *= 10;
printf("Counter is %li \n", counter );
}
but it reacts the same. The probe statement never shows the counter as anything less than 10.

aman
11-27-2004, 06:19 AM
I think you're just blowing the stack. Imagine 10,000 or more copies of your function being allocated.. You should try another method in my opinion.



EZ Archive Ads Plugin for vBulletin Copyright 2006 Computer Help Forum