diff mbox

[FFmpeg-devel] avutil/avstring: add av_strreplace API into avstring

Message ID 20170330143350.4420-1-lq@chinaffmpeg.org
State Accepted
Commit 99e5d81ef997cb88b1a40e6f253f37f7cbf251d9
Headers show

Commit Message

Steven Liu March 30, 2017, 2:33 p.m. UTC
refer to: http://creativeandcritical.net/str-replace-c
add av_strreplace API for replace string operations.

Signed-off-by: Steven Liu <lq@chinaffmpeg.org>
---
 libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++
 libavutil/avstring.h |  5 ++++
 2 files changed, 82 insertions(+)

Comments

Nicolas George March 31, 2017, 9:51 a.m. UTC | #1
Le decadi 10 germinal, an CCXXV, Steven Liu a écrit :
> refer to: http://creativeandcritical.net/str-replace-c
> add av_strreplace API for replace string operations.
> 
> Signed-off-by: Steven Liu <lq@chinaffmpeg.org>
> ---
>  libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++
>  libavutil/avstring.h |  5 ++++
>  2 files changed, 82 insertions(+)

It looks like it is duplicating a lot of functionality already
implemented in BPrint. I suggest you try implementing it using BPrint
instead.

Regards,
Steven Liu March 31, 2017, 12:11 p.m. UTC | #2
2017-03-31 17:51 GMT+08:00 Nicolas George <george@nsup.org>:

> Le decadi 10 germinal, an CCXXV, Steven Liu a écrit :
> > refer to: http://creativeandcritical.net/str-replace-c
> > add av_strreplace API for replace string operations.
> >
> > Signed-off-by: Steven Liu <lq@chinaffmpeg.org>
> > ---
> >  libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++
> ++++++++++++++++++++++
> >  libavutil/avstring.h |  5 ++++
> >  2 files changed, 82 insertions(+)
>
> It looks like it is duplicating a lot of functionality already
> implemented in BPrint. I suggest you try implementing it using BPrint
> instead.
>
I think just similar, not duplicating, and the simple functionality use
BPrint maybe too complex.

>
> Regards,
>
> --
>   Nicolas George
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
Steven Liu April 1, 2017, 2:58 a.m. UTC | #3
2017-03-31 20:11 GMT+08:00 Steven Liu <lingjiujianke@gmail.com>:

>
>
> 2017-03-31 17:51 GMT+08:00 Nicolas George <george@nsup.org>:
>
>> Le decadi 10 germinal, an CCXXV, Steven Liu a écrit :
>> > refer to: http://creativeandcritical.net/str-replace-c
>> > add av_strreplace API for replace string operations.
>> >
>> > Signed-off-by: Steven Liu <lq@chinaffmpeg.org>
>> > ---
>> >  libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++
>> ++++++++++++++++++++++
>> >  libavutil/avstring.h |  5 ++++
>> >  2 files changed, 82 insertions(+)
>>
>> It looks like it is duplicating a lot of functionality already
>> implemented in BPrint. I suggest you try implementing it using BPrint
>> instead.
>>
> I think just similar, not duplicating, and the simple functionality use
> BPrint maybe too complex.
>
>>
>> Regards,
>>
>> --
>>   Nicolas George
>> _______________________________________________
>> ffmpeg-devel mailing list
>> ffmpeg-devel@ffmpeg.org
>> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>>
>
> Pushed



Thanks!
Nicolas George April 1, 2017, 8:01 a.m. UTC | #4
Le primidi 11 germinal, an CCXXV, Steven Liu a écrit :
> I think just similar, not duplicating, and the simple functionality use
> BPrint maybe too complex.

Well, I will say it unambiguously:

Parts of this patch DO duplicate logic that we already have, and your
statement about BPrint being too complex is simply completely wrong.

Therefore, it was not acceptable as is and should not have been pushed.

Pushing while leaving only half a day to answer this was UNACCEPTABLE.
Do not ever do it again please.

Now, I will not insist on reverting, but I will demand that you make a
priority of simplifying this code.

Regards,
Steven Liu April 1, 2017, 8:37 a.m. UTC | #5
2017-04-01 16:01 GMT+08:00 Nicolas George <george@nsup.org>:

> Le primidi 11 germinal, an CCXXV, Steven Liu a écrit :
> > I think just similar, not duplicating, and the simple functionality use
> > BPrint maybe too complex.
>
> Well, I will say it unambiguously:
>
> Parts of this patch DO duplicate logic that we already have, and your
> statement about BPrint being too complex is simply completely wrong.
>
Ok, Can you guide me to improve it please?

>
> Therefore, it was not acceptable as is and should not have been pushed.
>
> Pushing while leaving only half a day to answer this was UNACCEPTABLE.
> Do not ever do it again please.
>
> Now, I will not insist on reverting, but I will demand that you make a
> priority of simplifying this code.
>
> Regards,
>
> --
>   Nicolas George
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
>
wm4 April 1, 2017, 11:12 a.m. UTC | #6
On Sat, 1 Apr 2017 10:01:15 +0200
Nicolas George <george@nsup.org> wrote:

> Le primidi 11 germinal, an CCXXV, Steven Liu a écrit :
> > I think just similar, not duplicating, and the simple functionality use
> > BPrint maybe too complex.  
> 
> Well, I will say it unambiguously:
> 
> Parts of this patch DO duplicate logic that we already have, and your
> statement about BPrint being too complex is simply completely wrong.

The bprint API is somewhat complicated.

> Therefore, it was not acceptable as is and should not have been pushed.
> 
> Pushing while leaving only half a day to answer this was UNACCEPTABLE.
> Do not ever do it again please.

Why get upset over a simple function being added?

Lots of unreviewed patches or patches that were half-approved or not
really approved get pushed. That's how this project work. If you don't
like it, propose a rule change.

> Now, I will not insist on reverting, but I will demand that you make a
> priority of simplifying this code.

It's already maximally self-contained.
Alexander Strasser April 1, 2017, 8:34 p.m. UTC | #7
On 2017-04-01 13:12 +0200, wm4 wrote:
> On Sat, 1 Apr 2017 10:01:15 +0200
> Nicolas George <george@nsup.org> wrote:
[...]
> > Therefore, it was not acceptable as is and should not have been pushed.
> > 
> > Pushing while leaving only half a day to answer this was UNACCEPTABLE.
> > Do not ever do it again please.
> 
> Why get upset over a simple function being added?
> 
> Lots of unreviewed patches or patches that were half-approved or not
> really approved get pushed. That's how this project work. If you don't
> like it, propose a rule change.

I do not think a rule change is needed for this case at hand.

While it is probably true that there were patches that didn't have enough 
review before they were pushed, it is not at all common, that patches
which are the subject of an active discussion, as it was in this case,
just get pushed.

Additionally this patch adds public API which should be sufficiently
discussed because reverting soon becomes difficult and involved.


[...]

  Alexander
wm4 April 1, 2017, 9:48 p.m. UTC | #8
On Sat, 1 Apr 2017 22:34:26 +0200
Alexander Strasser <eclipse7@gmx.net> wrote:

> On 2017-04-01 13:12 +0200, wm4 wrote:
> > On Sat, 1 Apr 2017 10:01:15 +0200
> > Nicolas George <george@nsup.org> wrote:  
> [...]
> > > Therefore, it was not acceptable as is and should not have been pushed.
> > > 
> > > Pushing while leaving only half a day to answer this was UNACCEPTABLE.
> > > Do not ever do it again please.  
> > 
> > Why get upset over a simple function being added?
> > 
> > Lots of unreviewed patches or patches that were half-approved or not
> > really approved get pushed. That's how this project work. If you don't
> > like it, propose a rule change.  
> 
> I do not think a rule change is needed for this case at hand.
> 
> While it is probably true that there were patches that didn't have enough 
> review before they were pushed, it is not at all common, that patches
> which are the subject of an active discussion, as it was in this case,
> just get pushed.
> 
> Additionally this patch adds public API which should be sufficiently
> discussed because reverting soon becomes difficult and involved.

Especially for someone new this is not obvious.

Either have clear rules, or don't hand out push rights like free
cookies to inexperienced project members (and then complain that they
make use of it).

I requested that the rules be clarified a while ago, but nobody cared,
and a patch attempting to improve the description of the existing rules
and practice was not accepted.

In the case at hand, Steven Liu might have pushed a bit too early, but
it's not like he ignored Nicolas George's post. Also I encouraged him
to separate this function and move it to libavutil, and nobody had
anything against it all that time (until Nicolas George objected later).
So I don't see a terrible offense here.

Again, if you don't like this, make the damn rules clearer.
Nicolas George April 2, 2017, 9:41 a.m. UTC | #9
Le decadi 10 germinal, an CCXXV, Steven Liu a écrit :
> refer to: http://creativeandcritical.net/str-replace-c
> add av_strreplace API for replace string operations.
> 
> Signed-off-by: Steven Liu <lq@chinaffmpeg.org>
> ---
>  libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++++++++++++++++++++++++
>  libavutil/avstring.h |  5 ++++
>  2 files changed, 82 insertions(+)
> 
> diff --git a/libavutil/avstring.c b/libavutil/avstring.c
> index 1787a1ef54..52e6e6cd13 100644
> --- a/libavutil/avstring.c
> +++ b/libavutil/avstring.c
> @@ -231,6 +231,83 @@ int av_strncasecmp(const char *a, const char *b, size_t n)
>      return c1 - c2;
>  }
>  

> +char *av_strreplace(const char *str, const char *from, const char *to)

Before starting: Steven, you seem not completely familiar with the
English language. Sometimes, I make complex sentences. If you need, ask
and I will rephrase.

First, I think the "strreplace" name should have been reserved for the
case-sensitive version, using possibly strireplace for the
case-insensitive version.

Since it was only applied very recently, and is not yet used even in the
rest of FFmpeg, I say we fix the name right now.

(Note: that does not mean this minute, that means this week, leaving a
chance for other to give their opinion. And of course, you yourself are
allowed to disagree.)

Second, I notice quite a few potential integer overflows. They would
need to be fixed if the code is to stay that way. Fortunately, I think
we can get rid of all that.

Third, and most important for the rest of my discourse: this code is
guilty of the sin of premature optimization. It builds a rather complex
cache mechanism, but possibly cripples it by introducing an arbitrary
limit, and more importantly, it uses av_stristr() repeatedly;
av_stristr() itself is not optimized at all, and there are further
optimizations for repeated use with the same needle; see the
Knuth-Morris-Pratt algorithm. Keep that in mind if anything I write
below seems "less efficient" than what is already there.

I told that it duplicated the BPrint API, I was wrong: the API it
duplicates dynarray. But it could have been BPrint, and they are the
same anyway.

Because there are three obvious ways of implementing this function.

1. (the present implementation) Find and keep track of all occurrences
   of the needle, allocate the target string with the exact size, and
   build it.

2. Find and count all occurrences of the needle, allocate the target
   string with the exact size, and then re-find all occurrences of the
   needle to build it.

3. Build the target string on the fly.

(Lexicon: strstr(haystack, needle): to find a needle in a haystack.)

By itself, the simplest solution to implement in C is #2 because it uses
only a single dynamic allocation and very simple loops. It requires
twice as much needle searches, but if they are optimized it may well be
a non-issue.

Solution #1 addresses the "twice as much needle searches" issue by
storing the results. I believe it is a very bad idea, because storing
the results requires a rather complex dynamic reallocation mechanism: in
this code, the dynamic array to store the results is about one third of
the whole code, and most of the integer overflows. One of the
av_dynarray API can make it simpler, but it is still a little tricky to
use. And I suspect it is not even worth the effort; only a benchmark
could tell: premature optimization.

I say: let us NOT use solution #1.

Solution #3 takes a completely different road. To implement it in plain
C would require the same kind of tricky dynamic reallocation as solution
#1, for the target string instead of the positions. But we have the
BPrint API that makes it very simple.

My advice would be: go with solution #3, and if performance is a problem
start by implementing KMP.

If per chance you prefer solution #2, you can achieve it by removing all
the "cache"-related code and replacing access to the "cache" with a new
call to av_stristr().


> +{
> +    /* Adjust each of the below values to suit your needs. */
> +    /* Increment positions cache size initially by this number. */
> +    size_t cache_sz_inc = 16;
> +    /* Thereafter, each time capacity needs to be increased,
> +     * multiply the increment by this factor. */
> +    const size_t cache_sz_inc_factor = 3;
> +    /* But never increment capacity by more than this number. */
> +    const size_t cache_sz_inc_max = 1048576;

> +    uintptr_t *pos_cache_tmp, *pos_cache = NULL;
> +    size_t cache_sz = 0;

> +        /* Increase the cache size when necessary. */
> +        if (cache_sz < count) {
> +            cache_sz += cache_sz_inc;
> +            pos_cache_tmp = av_realloc(pos_cache, sizeof(*pos_cache) * cache_sz);
> +            if (!pos_cache_tmp) {
> +                goto end_strreplace;
> +            } else pos_cache = pos_cache_tmp;
> +            cache_sz_inc *= cache_sz_inc_factor;
> +            if (cache_sz_inc > cache_sz_inc_max) {
> +                cache_sz_inc = cache_sz_inc_max;
> +            }
> +        }
> +        pos_cache[count-1] = pstr2 - str;
> +        pstr = pstr2 + fromlen;

All this is the code needed to keep track of the positions of the
needle. One way or another, it must go away.

> +        retlen = orglen + (tolen - fromlen) * count;

This is a potential integer overflow, for example.

> +        /* Otherwise, duplicate the string whilst performing
> +         * the replacements using the position cache. */
> +        pret = ret;
> +        memcpy(pret, str, pos_cache[0]);
> +        pret += pos_cache[0];
> +        for (i = 0; i < count; i++) {
> +            memcpy(pret, to, tolen);
> +            pret += tolen;
> +            pstr = str + pos_cache[i] + fromlen;
> +            cpylen = (i == count-1 ? orglen : pos_cache[i+1]) - pos_cache[i] - fromlen;
> +            memcpy(pret, pstr, cpylen);
> +            pret += cpylen;
> +        }

If there are n copies of the needle, there are n+1 pieces of string
around them, and one of them has to be taken out of the loop. This
version isolates the one before the first needle. It would have been
much simpler to isolate the one after the last needle. The formula for
cpylen, in particular, is a symptom of this non-optimal choice. The loop
could look that way:

	while (needle) {
	    copy from pos to needle
	    update pos
	    add replacement string
	}
	copy from pos to the end

The BPrint version is actually exactly the same:

	av_bprint_init()
	while (needle) {
	    av_bprint_append_data() to copy from pos to needle
	    update pos
	    av_bprint_append_data() to add the replacement string
	}
	av_bprint_append_data() to copy from pos to the end
	av_bprint_is_complete() to check malloc errors
	av_print_finalize()

All in all, I think the BPrint version is the easiest to implement right
now.

Regards,
Steven Liu April 2, 2017, 11:45 a.m. UTC | #10
2017-04-02 17:41 GMT+08:00 Nicolas George <george@nsup.org>:

> Le decadi 10 germinal, an CCXXV, Steven Liu a écrit :
> > refer to: http://creativeandcritical.net/str-replace-c
> > add av_strreplace API for replace string operations.
> >
> > Signed-off-by: Steven Liu <lq@chinaffmpeg.org>
> > ---
> >  libavutil/avstring.c | 77 ++++++++++++++++++++++++++++++
> ++++++++++++++++++++++
> >  libavutil/avstring.h |  5 ++++
> >  2 files changed, 82 insertions(+)
> >
> > diff --git a/libavutil/avstring.c b/libavutil/avstring.c
> > index 1787a1ef54..52e6e6cd13 100644
> > --- a/libavutil/avstring.c
> > +++ b/libavutil/avstring.c
> > @@ -231,6 +231,83 @@ int av_strncasecmp(const char *a, const char *b,
> size_t n)
> >      return c1 - c2;
> >  }
> >
>
> > +char *av_strreplace(const char *str, const char *from, const char *to)
>
> Before starting: Steven, you seem not completely familiar with the
> English language. Sometimes, I make complex sentences. If you need, ask
> and I will rephrase.
>
> First, I think the "strreplace" name should have been reserved for the
> case-sensitive version, using possibly strireplace for the
> case-insensitive version.
>
> Since it was only applied very recently, and is not yet used even in the
> rest of FFmpeg, I say we fix the name right now.
>
> (Note: that does not mean this minute, that means this week, leaving a
> chance for other to give their opinion. And of course, you yourself are
> allowed to disagree.)
>
> Second, I notice quite a few potential integer overflows. They would
> need to be fixed if the code is to stay that way. Fortunately, I think
> we can get rid of all that.
>
> Third, and most important for the rest of my discourse: this code is
> guilty of the sin of premature optimization. It builds a rather complex
> cache mechanism, but possibly cripples it by introducing an arbitrary
> limit, and more importantly, it uses av_stristr() repeatedly;
> av_stristr() itself is not optimized at all, and there are further
> optimizations for repeated use with the same needle; see the
> Knuth-Morris-Pratt algorithm. Keep that in mind if anything I write
> below seems "less efficient" than what is already there.
>
> I told that it duplicated the BPrint API, I was wrong: the API it
> duplicates dynarray. But it could have been BPrint, and they are the
> same anyway.
>
> Because there are three obvious ways of implementing this function.
>
> 1. (the present implementation) Find and keep track of all occurrences
>    of the needle, allocate the target string with the exact size, and
>    build it.
>
> 2. Find and count all occurrences of the needle, allocate the target
>    string with the exact size, and then re-find all occurrences of the
>    needle to build it.
>
> 3. Build the target string on the fly.
>
> (Lexicon: strstr(haystack, needle): to find a needle in a haystack.)
>
> By itself, the simplest solution to implement in C is #2 because it uses
> only a single dynamic allocation and very simple loops. It requires
> twice as much needle searches, but if they are optimized it may well be
> a non-issue.
>
> Solution #1 addresses the "twice as much needle searches" issue by
> storing the results. I believe it is a very bad idea, because storing
> the results requires a rather complex dynamic reallocation mechanism: in
> this code, the dynamic array to store the results is about one third of
> the whole code, and most of the integer overflows. One of the
> av_dynarray API can make it simpler, but it is still a little tricky to
> use. And I suspect it is not even worth the effort; only a benchmark
> could tell: premature optimization.
>
> I say: let us NOT use solution #1.
>
> Solution #3 takes a completely different road. To implement it in plain
> C would require the same kind of tricky dynamic reallocation as solution
> #1, for the target string instead of the positions. But we have the
> BPrint API that makes it very simple.
>
> My advice would be: go with solution #3, and if performance is a problem
> start by implementing KMP.
>
> If per chance you prefer solution #2, you can achieve it by removing all
> the "cache"-related code and replacing access to the "cache" with a new
> call to av_stristr().
>
>
> > +{
> > +    /* Adjust each of the below values to suit your needs. */
> > +    /* Increment positions cache size initially by this number. */
> > +    size_t cache_sz_inc = 16;
> > +    /* Thereafter, each time capacity needs to be increased,
> > +     * multiply the increment by this factor. */
> > +    const size_t cache_sz_inc_factor = 3;
> > +    /* But never increment capacity by more than this number. */
> > +    const size_t cache_sz_inc_max = 1048576;
>
> > +    uintptr_t *pos_cache_tmp, *pos_cache = NULL;
> > +    size_t cache_sz = 0;
>
> > +        /* Increase the cache size when necessary. */
> > +        if (cache_sz < count) {
> > +            cache_sz += cache_sz_inc;
> > +            pos_cache_tmp = av_realloc(pos_cache, sizeof(*pos_cache) *
> cache_sz);
> > +            if (!pos_cache_tmp) {
> > +                goto end_strreplace;
> > +            } else pos_cache = pos_cache_tmp;
> > +            cache_sz_inc *= cache_sz_inc_factor;
> > +            if (cache_sz_inc > cache_sz_inc_max) {
> > +                cache_sz_inc = cache_sz_inc_max;
> > +            }
> > +        }
> > +        pos_cache[count-1] = pstr2 - str;
> > +        pstr = pstr2 + fromlen;
>
> All this is the code needed to keep track of the positions of the
> needle. One way or another, it must go away.
>
> > +        retlen = orglen + (tolen - fromlen) * count;
>
> This is a potential integer overflow, for example.
>
> > +        /* Otherwise, duplicate the string whilst performing
> > +         * the replacements using the position cache. */
> > +        pret = ret;
> > +        memcpy(pret, str, pos_cache[0]);
> > +        pret += pos_cache[0];
> > +        for (i = 0; i < count; i++) {
> > +            memcpy(pret, to, tolen);
> > +            pret += tolen;
> > +            pstr = str + pos_cache[i] + fromlen;
> > +            cpylen = (i == count-1 ? orglen : pos_cache[i+1]) -
> pos_cache[i] - fromlen;
> > +            memcpy(pret, pstr, cpylen);
> > +            pret += cpylen;
> > +        }
>
> If there are n copies of the needle, there are n+1 pieces of string
> around them, and one of them has to be taken out of the loop. This
> version isolates the one before the first needle. It would have been
> much simpler to isolate the one after the last needle. The formula for
> cpylen, in particular, is a symptom of this non-optimal choice. The loop
> could look that way:
>
>         while (needle) {
>             copy from pos to needle
>             update pos
>             add replacement string
>         }
>         copy from pos to the end
>
> The BPrint version is actually exactly the same:
>
>         av_bprint_init()
>         while (needle) {
>             av_bprint_append_data() to copy from pos to needle
>             update pos
>             av_bprint_append_data() to add the replacement string
>         }
>         av_bprint_append_data() to copy from pos to the end
>         av_bprint_is_complete() to check malloc errors
>         av_print_finalize()
>
> All in all, I think the BPrint version is the easiest to implement right
> now.
>

I'm not sure if i misunderstand, but i will try to do it with your
suggestion.
I will try to understand BPrint and try to use it.

>
> Regards,
>
> --
>   Nicolas George
>
> _______________________________________________
> ffmpeg-devel mailing list
> ffmpeg-devel@ffmpeg.org
> http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
>
>
diff mbox

Patch

diff --git a/libavutil/avstring.c b/libavutil/avstring.c
index 1787a1ef54..52e6e6cd13 100644
--- a/libavutil/avstring.c
+++ b/libavutil/avstring.c
@@ -231,6 +231,83 @@  int av_strncasecmp(const char *a, const char *b, size_t n)
     return c1 - c2;
 }
 
+char *av_strreplace(const char *str, const char *from, const char *to)
+{
+    /* Adjust each of the below values to suit your needs. */
+    /* Increment positions cache size initially by this number. */
+    size_t cache_sz_inc = 16;
+    /* Thereafter, each time capacity needs to be increased,
+     * multiply the increment by this factor. */
+    const size_t cache_sz_inc_factor = 3;
+    /* But never increment capacity by more than this number. */
+    const size_t cache_sz_inc_max = 1048576;
+
+    char *pret, *ret = NULL;
+    const char *pstr2, *pstr = str;
+    size_t i, count = 0;
+    uintptr_t *pos_cache_tmp, *pos_cache = NULL;
+    size_t cache_sz = 0;
+    size_t cpylen, orglen, retlen, tolen, fromlen = strlen(from);
+
+    /* Find all matches and cache their positions. */
+    while ((pstr2 = av_stristr(pstr, from))) {
+        count++;
+        /* Increase the cache size when necessary. */
+        if (cache_sz < count) {
+            cache_sz += cache_sz_inc;
+            pos_cache_tmp = av_realloc(pos_cache, sizeof(*pos_cache) * cache_sz);
+            if (!pos_cache_tmp) {
+                goto end_strreplace;
+            } else pos_cache = pos_cache_tmp;
+            cache_sz_inc *= cache_sz_inc_factor;
+            if (cache_sz_inc > cache_sz_inc_max) {
+                cache_sz_inc = cache_sz_inc_max;
+            }
+        }
+
+        pos_cache[count-1] = pstr2 - str;
+        pstr = pstr2 + fromlen;
+    }
+    orglen = pstr - str + strlen(pstr);
+    /* Allocate memory for the post-replacement string. */
+    if (count > 0) {
+        tolen = strlen(to);
+        retlen = orglen + (tolen - fromlen) * count;
+    } else {
+        retlen = orglen;
+    }
+    ret = av_malloc(retlen + 1);
+    if (!ret) {
+        goto end_strreplace;
+    }
+
+    if (!count) {
+        /* If no matches, then just duplicate the string. */
+        av_strlcpy(ret, str, retlen + 1);
+    } else {
+        /* Otherwise, duplicate the string whilst performing
+         * the replacements using the position cache. */
+        pret = ret;
+        memcpy(pret, str, pos_cache[0]);
+        pret += pos_cache[0];
+        for (i = 0; i < count; i++) {
+            memcpy(pret, to, tolen);
+            pret += tolen;
+            pstr = str + pos_cache[i] + fromlen;
+            cpylen = (i == count-1 ? orglen : pos_cache[i+1]) - pos_cache[i] - fromlen;
+            memcpy(pret, pstr, cpylen);
+            pret += cpylen;
+        }
+        ret[retlen] = '\0';
+    }
+
+end_strreplace:
+    /* Free the cache and return the post-replacement string,
+     * which will be NULL in the event of an error. */
+    av_free(pos_cache);
+    return ret;
+}
+
 const char *av_basename(const char *path)
 {
     char *p = strrchr(path, '/');
diff --git a/libavutil/avstring.h b/libavutil/avstring.h
index dd2876990f..33be8bf484 100644
--- a/libavutil/avstring.h
+++ b/libavutil/avstring.h
@@ -266,6 +266,11 @@  int av_strcasecmp(const char *a, const char *b);
  */
 int av_strncasecmp(const char *a, const char *b, size_t n);
 
+/**
+ * Locale-independent strings replace.
+ * @note This means only ASCII-range characters are replace
+ */
+char *av_strreplace(const char *str, const char *from, const char *to);
 
 /**
  * Thread safe basename.