CODEWITHSUNDEEP
cstringrecursioncs50
Vitor Falleiros
Vitor Falleiros

Reputation: 55

How to recursively return string value in C?

Trying to learn something here more than solve the specific problem. Please help me towards some best practices to apply in this situation, and if possible some clarification of why. Thanks in advance for your assistance.

Basically I'm brute-force breaking a very simple hash algorithm, within known limits. Function tests possibilities of a string (within a length limit) against the hash, until it matches the hash passed. Then recursion should stop all iterations and return the string that matched. The iteration works, but when the answer is found, it seems that each run of the function doesn't get the value returned by its call of the same function.

Here's the code of the function, with extra comments for clarity:

//'hash' is the hash to be replicated
//'leading' is for recursive iteration (1st call should have leading=="")
//'limit' is the maximum string length to be tested

string crack(string hash, string leading, int limit)
{
    string cracked=NULL, force=NULL, test=NULL;

    //as per definition of C's crypt function - validated
    char salt[3] = {hash[0], hash[1], '\0'};

    // iterate letters of the alphabet - validated
    for(char c='A'; c<='z'; c++)
    {
        // append c at the end of string 'leading' - validated
        test = append(leading,c);

        // apply hash function to tested string - validated
        force = crypt(test,salt);

        // if hash replicated, store answer in 'cracked' - validated
        if(strcmp(hash,force)==0)
        {
            cracked = test;
        }
        else
        {
            // if within length limit, iterate next character - validated
            if(strlen(test)<=limit+1)
            {
                // THIS IS WHERE THE PROBLEM OCCURS
                // value received when solution found
                // is always empty string ("", not NULL)
                // tried replacing this with strcpy, same result
                cracked = crack_des(hash,test,limit);
            }
        }

        // if answer found, break out of loop - validated
        if(cracked){break;}

        // test only alphabetic characters - validated
        if(c=='Z'){c='a' - 1;}
    }

    free(test);

    // return NULL if not cracked to continue iteration on level below
    // this has something to do with the problem
    return cracked;
} // end of function

From the little bit I recall of pointers, I'd guess it is something with passing references instead of values, but I don't have enough knowledge to solve it. I have read this thread, but this suggestion doesn't seem to solve the issue - I tried using strcpy and got the same results.

Disclaimer: this is an exercise in 2018's CS50 by Harvard at EDX. It won't affect my grading (have already submitted two perfect exercises for the week, which is what is required) but as stated above I'm looking to learn.

Edit: edited the tag back to C (as clarified in comments, string is from string.h, and append was coded by me and validated several times over - I'll get to TDD in a while). Thanks all for your comments; problem solved and lessons learned!

Upvotes: 0

Views: 381

Answers (1)

Yi Zhenfei
Yi Zhenfei

Reputation: 166

I found a bug in the code, but I am not sure whether it is the root cause of your problem.

When the code hit the line:

strcmp(hash,force)==0

then you will assign the string pointed by 'test' to 'cracked':

cracked = test;

then this line is hit:

if(cracked){break;}

then the loop is breaked, and the next line:

free(test);

this line will free the string pointed by test, and remember that it is the same string pointed by 'cracked', thus you returned a string which is already freed.

What will happened to the string is dependent on your compiler and libc. You can try to fix this problem by allocating memory for 'cracked':

cracked = strdup(test);

Also, there are memory leaks caused by the 'test' and 'force' string, but they should be irrelevant to your problem.

Upvotes: 4

Related Questions