Hello and welcome to our community! Is this your first visit?
Register
Enjoy an ad free experience by logging in. Not a member yet? Register.
Results 1 to 11 of 11
  1. #1
    New Coder
    Join Date
    Nov 2004
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts

    Not sure what's causing this Segmentation Fault

    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.

    Code:
    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.
    Code:
    typedef struct info
    {
          long testValue;
          int numItems;
          long maxValue;
          char userChoice;
    } INFO;
    And here's the call to malloc.
    Code:
    int *array = malloc(sizeof (int) * permInfo.numItems);
    Any ideas??

    Edit : Happy Thanksgiving everybody.

  • #2
    Regular Coder
    Join Date
    Oct 2004
    Posts
    230
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #3
    New Coder
    Join Date
    Nov 2004
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Last edited by ChristianTool; 11-26-2004 at 06:35 PM.

  • #4
    Regular Coder
    Join Date
    Oct 2004
    Posts
    230
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Have you tried compiling your code with debugging information and running it in gdb debugger? Everything you wanted to know about gcc

  • #5
    New Coder
    Join Date
    Nov 2004
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Whenever I run it, it exits with the following.
    Code:
    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.
    Last edited by ChristianTool; 11-26-2004 at 11:19 PM.

  • #6
    Regular Coder
    Join Date
    Oct 2004
    Posts
    230
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Yea try stepping through the stack, type help at the gdb prompt or find everything you wanted to know about gdb

    Also I could try running it if I knew what are the values of the struct you pass in...
    Last edited by aman; 11-26-2004 at 11:43 PM.

  • #7
    New Coder
    Join Date
    Nov 2004
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Sure let me show you the rest of the code while I try and mess with GDB.

    Here's magic.c
    Code:
    #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;
       }
    
    }

  • #8
    New Coder
    Join Date
    Nov 2004
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    Here's proj4.c :

    Code:
    #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
    Code:
    #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.

  • #9
    Regular Coder
    Join Date
    Oct 2004
    Posts
    230
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.

  • #10
    New Coder
    Join Date
    Nov 2004
    Posts
    12
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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
    Code:
    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.
    Last edited by ChristianTool; 11-27-2004 at 02:20 AM.

  • #11
    Regular Coder
    Join Date
    Oct 2004
    Posts
    230
    Thanks
    0
    Thanked 0 Times in 0 Posts
    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.


  •  

    Posting Permissions

    • You may not post new threads
    • You may not post replies
    • You may not post attachments
    • You may not edit your posts
    •