How Much Stack Memory am I Using? <C>

Question

I'm coding homework in C and the upload system tells me I'm using too much stack memory. I need to find the root of the problem as I'm kinda stuck.

Is there any way I could analyze the stack memory usage or even see what variables use it and how much they use?

EDIT: Here's the code. It's not complete (because this is case 2 when the file is launched with a parameter; case 1 is working fine), so I hope I didn't leave any functions I'm not using etc.

What this is meant to do is The Caesar cipher with a bit of a twist to it. On input I get two strings of unknown size. The first one is cipher, the second one is a supposed to be close to the decoded message (it could be missing letters, it may have extra letters). The code works fine and outputs everything like it should, but if I input longer strings (like 200 chars each), the upload system starts saying I'm using too much stack.

f.e. with input (screenshot here https://i.sstatic.net/6A0n1.jpg )

NOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyzABCDEFGHIJKLM
        abcRkfgchijklmnbCGqrstuvpxyzeABQDEFQGvIJKLMNOPRTUVWPZabcdefghijklnopdrPstuvwxorkCzABCEqFDpGHdJMNOPQcRSTUNVGYuZbMcTefghjklmnopqrstcvgwyzABCOiGHIPJKLMNOYPQRsTUWvYYZaQcdZpfgCfiXjekmnopqrptuvtwxyiABCDQFGHUEIJKLMQOPQRSTfVWXYZ

I apparently used 185232B of stack memory.

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <ctype.h>

const char* alphabet = "ABCDEFGHIJKLMNOPQRSTUVWXYZabcdefghijklmnopqrstuvwxyz";

char rotate(char, int);
void shift(const char *src, char * dst, int offset);
char * inputstr(size_t size);
int edit_distance(const char *str1, const char *str2, int len1, int len2);

int main(int argc, char * argv[])
{
    char * source = inputstr(10);
    char * example = inputstr(10);
    size_t len_source = strlen(source);
    size_t len_example = strlen(example);

    //char *closest = calloc(len_source+1,sizeof(char));
    char * destination = calloc(len_source + 1, sizeof(char));
    int min_match = len_source;
    int best_i = 0;
    for (int i = 0; i < 52;++i)
    {
        shift(source, destination, i);
        int match = edit_distance(destination, example, len_source, len_example);
        //printf("%2d: %s ~ %s > %d\n",i, destination, example, match);
        if (match < min_match) {
            min_match = match;
            best_i = i;
        }
    }
    shift(source, destination, best_i);
    printf("%s\n", destination);
    free(source);
    free(example);
    //free(closest);
    free(destination);
    return 0;

}

char rotate(char original, int offset)
{
    int index;
    char * rest;
    rest = strchr(alphabet, original);
    index = (int)(rest - alphabet);
    int distance = (index + offset) % 52;
    char new = *(alphabet + distance);
    return new;
}

void shift(const char *src, char * dst, int offset)
{
    int counter = 0;
    int len = strlen(src);
    for (int i = 0; i < len; ++i)
    {
        dst[i] = rotate(src[i], offset);
        counter++;
    }

}


char * inputstr(size_t size)
{
    char * str;
    if ((str = realloc(NULL, size * sizeof(char))) == NULL) {
        printf("Not enough memory\n");
        free(str);
        exit(69);
    }
    int ch;
    size_t len = 0;
    while ((ch = getchar()) != EOF && ch != '\n') {
        if (isalpha(ch)) {
            str[len] = ch;
            ++len;
            if (len == size) {
                size *= 5;
                if ((str = realloc(str, size * sizeof(char))) == NULL) {
                    printf("Not enough memory\n");
                    free(str);
                    exit(69);
                }
            }
        } else {
            fprintf(stderr, "Error: Chybny vstup!\n");
            free(str);
            exit(100);
        }
    }
    str[len++] = '\0';
    return str;
}

int edit_distance(const char *str1, const char *str2, int len1, int len2)
{
    int d[len1 + 1][len2 + 1];
    for (int i = 0; i <= len1; ++i)
    {
        d[i][0] = i;
    }
    for (int j = 0; j <= len2; ++j)
    {
        d[0][j] = j;
    }
    for (int j = 1; j <= len2; ++j)
    {
        for (int i = 1; i <= len1;
        ++i)
        {
            if (str1[i - 1] == str2[j - 1]) {
                d[i][j] = d[i - 1][j - 1];

            } else {
                int min = d[i - 1][j] + 1;
                if ((d[i][j - 1] + 1) < min) {
                    min = d[i][j - 1] + 1;
                }
                if ((d[i - 1][j - 1] + 1) < min) {
                    min = d[i - 1][j - 1] + 1;
                }
                d[i][j] = min;

            }
        }
    }
    //printf("%d %d\n", len1, len2);
    /*for(int i = 0; i<=len1; ++i)
    {
        for(int j = 0; j<=len2; ++j)
        {
            printf("%2d ", d[i][j]);
        }
        printf("\n");
    }*/
    return d[len1][len2];
}

Answer 1

The culprit looks like this array in edit_distance:

int d[len1 + 1][len2 + 1];

This array has size (len_source + 1) * (len_example + 1) * sizeof(int). So if for example the source and example string are each 200 bytes and an int is 4 bytes you have roughly 200 * 200 * 4 = 160000 bytes for this array. Those aren't huge strings but that's already more than 3 times your stack limit.

Instead of declaring this array on the stack, you can allocate a 2D array (technically an array of pointers, each of which points to an array of ints) dynamically:

int i;
int **d = malloc(sizeof(int *) * (len1 + 1));
for (i=0; i < len1 + 1; i++) {
    d[i] = malloc(sizeof(int) * (len2 + 1));
}

Then make sure you save off the value you want to return and free everything:

int result = d[len1][len2];
for (i=0; i < len1 + 1; i++) {
   free(d[i]);
}
free(d);
return result;