Segmentation error while replacing substrings of a string with other substring

Question

I have string " {"1":"[4,11,14,19,20,18,27]"} ". I want to change it into "{\"1\":\"4,11,14,19,20,18,27\"}".

Below is my code:

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

char *replace (char *this, char *withthat, char *inthis) {
    char *where = inthis;

    while ((where = strstr(where, this))) {
        memcpy(where, withthat, strlen(withthat));
        memmove(where+strlen(withthat),where+strlen(this), strlen(where+strlen(this))+1);
    }
    return inthis;
}

int main(void) {
    char string[] = "{&quot;1&quot;:&quot;[4,11,14,19,20,18,27]&quot;}";
    printf("%s\n", replace("&quot;", "\\\"", string));
    printf("%s\n", replace("\"[" , "\"", string));
    printf("%s\n", replace("]\\" , "\\", string));
    printf("%s\n", replace("{" , "\"{", string));
    printf("%s\n", replace("}" , "}\"", string));
    return 0;
}

I get the error for the last two replace calls. My o/p is {\"1\":\"[4,11,14,19,20,18,27]\"} {\"1\":\"4,11,14,19,20,18,27]\"} {\"1\":\"4,11,14,19,20,18,27\"} Segmentation fault

I tried doing gdb, but not able to find the root cause of error. it is somehow concerned with memcopy, but not able to understand. If anyone can help me, it would be great. Thanks in advance.

Jerry Coffin · Answer 1 · 2011-10-21T00:26:23.157

Your replacement string is longer than the input, but when you allocate string, it has only space for the input size plus NUL terminator. When you try to expand it, you overrun the buffer, and the system shuts you down (though it might let you by with a small overrun, such as rounding the allocation up to the next multiple of 4 or maybe 8.

To fix the problem, you (probably) want to figure out the maximum amount by which your string could grow, allocate that large of a string, and use it for the result.

Edit: for example, consider your last replacement, changing } to }". This doubles the length of the substring you find. As a really simple worst-case estimate, let's assume the entire input consists entirely of }. In this case, the result would be twice as long as the input, so we'd need to allocate strlen(input)*2+1 bytes for the result.

In your case, the last four replacements (at least) are mutually exclusive (e.g., an input can't be a { and a } and a [ and a ] simultaneously) so doubling the length once will be enough to cover all of them.

Thanks!!! since I am new to C, can you guide me to a reference material for allocating memory and using. — user537670, Oct 21 '11 at 00:44
@user537670: for that, you just about need a good book. I learned from the classic K&R (there weren't many alternatives at the time). There are a lot more alternatives now, but I still think K&R is a good choice. — Jerry Coffin, Oct 21 '11 at 02:55

score 1 · Accepted Answer · answered Oct 21 '11 at 00:51

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

char *replace (char *old, char *new, char *buff) {
    char *ptr;
    size_t oldlen = strlen(old);
    size_t newlen = strlen(new);

    for(ptr=buff; ptr = strstr(ptr, old); ptr += newlen) {
        memmove(ptr+newlen, ptr+oldlen, strlen(ptr+oldlen)+1);
        memcpy(ptr, new, newlen);
    }
    return buff;
}

int main(void) {
    char string[1234] = "{&quot;1&quot;:&quot;[4,11,14,19,20,18,27]&quot;}";
    printf("%s\n", replace("&quot;", "\\\"", string));
    printf("%s\n", replace("\"[" , "\"", string));
    printf("%s\n", replace("]\\" , "\\", string));
    printf("%s\n", replace("{" , "\"{", string));
    printf("%s\n", replace("}" , "}\"", string));

    return 0;
}

The last two substitutions "{}" contain themselves. This causes the original string to be rescanned at the same place, rematched+ resubstututed. At infinitum. The ptr+=newlen avoids this.

score 0 · Answer 3 · answered Oct 20 '11 at 23:58

0

Your replace assumes that the buffer is big enough to hold the result. You need to allocate the buffer so big that it can hold the result of expansion.

answered Oct 20 '11 at 23:58

Vlad

35,022
6
77
199

A simple workaround is allocating more space in the string: `char string[1024] = ...`. A more elaborate solution would be to make `replace` allocate the memory for the output itself, and not use the given buffer. – Vlad Oct 21 '11 at 00:01
i tried char string[1024], but still the same issue. can you give any example for allocating memory operations in C? Thanks – user537670 Oct 21 '11 at 00:06
Well, you allocate memory with a simple `malloc`. You can do two passes through the input: first pass calculates the answer's size, then you allocate the needed amount of memory with `malloc`, and then in the second pass copy the string into the allocated memory chunk, replacing `this` with `withwhat`, like your code does now. – Vlad Oct 21 '11 at 00:10

score 0 · Answer 4 · answered Oct 21 '11 at 00:10

Your order of operations is wrong. You should first make place for the replacement string, and than insert the replacement. (given enough space). Also, you could calculate the strlen()s in advance, since they do not change. (except if they are only used once)

score 0 · Answer 5 · answered Oct 21 '11 at 00:11

0

If withthat is longer than this, then your memcpy is overwriting part of the string that goes after the replacement. You would have to do the memmove before memcpy in this case.

answered Oct 21 '11 at 00:11

TJD

11,800
1
26
34

It would be easier to debug if you do some unit tests of your replace function with simpler sample input data, e.g., replace "cat" with "lolcat". The quote backslash stuff is ridiculous to try and think through and see what's happening. Also, you should create some temp variables and print out all the args that you are passing to memcpy and memmove as it executes – TJD Oct 21 '11 at 00:40

Segmentation error while replacing substrings of a string with other substring

5 Answers5

Linked