1

I have the following code that prints as intended in ubuntu linux but prints nothing in cygwin in windows. However, if I get rid of free(t) in is_rotation function then it works ok. I want to know if I am doing bad memory management or it is a cygwin issue. Why it is happening. And any other suggestion to improve the memory management.

Here is the code: 

/**
* sub is a substring of str or not
**/
int is_substring(const char* str,const char* sub){
    const char* s1=str;
    const char*  s2=sub;
    int count=0;
    while(1){       
        if(*s2=='\0') return 1;
        else if(*s1=='\0') return 0;
        else if(*s1==*s2){
            count++;
            s2++;
        }   
        else{
            if(count!=0){
                s1-=count;
                count=0;
                s2=sub;
            }
        }
        s1++;
    }
    return 0;
}
/**
* s1 and s2 are rotations of eachother or not, given only the is_substring function.
**/
int is_rotation(const char* s1,const char* s2){
    int l1=strlen(s1);
    if(l1!=strlen(s2)) return 0;
    char* t=malloc(2*l1*sizeof(char));
    strcat(t,s1);
    strcat(t,s1);
    int r=is_substring(t,s2);
    free(t);
    return r;
}

/**
* USAGE: ./a.out string1 string2
**/
int main(int argc, char *argv[]){
    if(argc<3) return 1;
    printf("is_substring=%d",is_substring(argv[1],argv[2]));
    printf("\nis_rotation=%d",is_rotation(argv[1],argv[2]));
    return 0;
}

Thanks for the help :)

faisal
  • 1,327
  • 10
  • 19
  • Please don't use `strcat`. It can lead to buffer overflows. Use `strncat` (or `strlcat`, if available) instead. – michaelb958--GoFundMonica Apr 25 '13 at 22:54
  • ok, I will try with those functions – faisal Apr 25 '13 at 22:56
  • `sizeof(char)` is `1`. – Carl Norum Apr 25 '13 at 23:00
  • Theoretically, given that the `malloc()` is 2x the size of `l1` that should not be an issue. However, given that he didn't add 1 for the null terminator, and he didn't initialize the memory allocated before calling `strcat` he still had problems. That said, yeah... `strcat` is dangerous. – K Scott Piel Apr 25 '13 at 23:00
  • if I add 1 to malloc and use strcat, it works also. But, you are right strcat is probably not the best. – faisal Apr 25 '13 at 23:10
  • 1
    `strcat` is ok *if* you verify that there's enough space. It's just as easy to pass an incorrect size to `strncat` as it is to misuse `strcat`. – Keith Thompson Apr 25 '13 at 23:39

2 Answers2

4

The issue is in the first strcat() call. You should replace it with a strcpy() instead.

int is_rotation(const char* s1,const char* s2){
    int l1=strlen(s1);
    if(l1!=strlen(s2)) return 0;
    char* t=malloc(2*l1*sizeof(char) + 1);
    strcpy(t,s1); // initialize with strcpy() so we have a null in the string
    strcat(t,s1);
    int r=is_substring(t,s2);
    free(t);
    return r;
}

Note that malloc() does not initialize the buffer it allocates normally. Perhaps the one on ubuntu does, but it is not guaranteed. In cygwin, the buffer is not initialized, so the strcat() is walking memory looking for a null before it copies the string... which very likely is past the end of your allocated buffer.

Also, you have to add an extra character to the buffer to hold the null terminator for the final string... it's 2x the length of l1 + 1 for the null terminator

K Scott Piel
  • 4,320
  • 14
  • 19
1

Here is a bug that kills your stack:

char* t=malloc(2*l1*sizeof(char));
strcat(t,s1);
strcat(t,s1);

The first strcat adds characters to somewhere... As you are using malloc the contents of the t buffer is unknown. Also you need one more byte for zero.

char* t=malloc(2*l1+1); // (2*l1+1)*sizeof(char)
strcpy(t,s1);
strcat(t,s1);
Valeri Atamaniouk
  • 5,125
  • 2
  • 16
  • 18