2017-04-02 17:41 GMT+08:00 Nicolas George <geo...@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 <l...@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 > > _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org http://ffmpeg.org/mailman/listinfo/ffmpeg-devel
