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

[Nicolas George]

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 at 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,

-- 
  Nicolas George
-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 833 bytes
Desc: Digital signature
URL: <http://ffmpeg.org/pipermail/ffmpeg-devel/attachments/20170402/bbd53b62/attachment.sig>