* [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero @ 2024-05-05 22:30 Gerion Entrup 2024-05-05 22:30 ` [FFmpeg-devel] [PATCH 2/2] libavfilter/signature_lookup: fix jaccard distance Gerion Entrup 2024-05-07 17:46 ` [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero Michael Niedermayer 0 siblings, 2 replies; 7+ messages in thread From: Gerion Entrup @ 2024-05-05 22:30 UTC (permalink / raw) To: ffmpeg-devel --- libavfilter/signature_lookup.c | 2 +- 1 file changed, 1 insertion(+), 1 deletion(-) diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c index a0ca818a9b..b39a3e225b 100644 --- a/libavfilter/signature_lookup.c +++ b/libavfilter/signature_lookup.c @@ -128,7 +128,7 @@ static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseS int jaccarddist, i, composdist = 0, cwthcount = 0; for (i = 0; i < 5; i++) { if ((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0) { - jaccarddist /= union_word(first->data[i], second->data[i]); + jaccarddist /= FFMAX(union_word(first->data[i], second->data[i]), 1); } if (jaccarddist >= sc->thworddist) { if (++cwthcount > 2) { -- 2.43.2 _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe". ^ permalink raw reply [flat|nested] 7+ messages in thread
* [FFmpeg-devel] [PATCH 2/2] libavfilter/signature_lookup: fix jaccard distance 2024-05-05 22:30 [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero Gerion Entrup @ 2024-05-05 22:30 ` Gerion Entrup 2024-05-07 17:46 ` [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero Michael Niedermayer 1 sibling, 0 replies; 7+ messages in thread From: Gerion Entrup @ 2024-05-05 22:30 UTC (permalink / raw) To: ffmpeg-devel; +Cc: Sachin Tilloo Actually, the jaccard distance is defined as D = 1 - intersect / union. Additionally, the distance value is compared against a constant that must be between 0 and 1, which is not the case here. Both facts together has led to the fact, that the function always returned a matching course signature. To leave the constant intact and to avoid floating point computation, this commit multiplies with 1 << 16 making the constant effectively 9000 / (1<<16) =~ 0.14. Reported-by: Sachin Tilloo <sachin.tilloo@gmail.com> Reviewed-by: Sachin Tilloo <sachin.tilloo@gmail.com> Tested-by: Sachin Tilloo <sachin.tilloo@gmail.com> --- libavfilter/signature_lookup.c | 3 ++- 1 file changed, 2 insertions(+), 1 deletion(-) diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c index b39a3e225b..b90b63f3f2 100644 --- a/libavfilter/signature_lookup.c +++ b/libavfilter/signature_lookup.c @@ -127,9 +127,10 @@ static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseS { int jaccarddist, i, composdist = 0, cwthcount = 0; for (i = 0; i < 5; i++) { - if ((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0) { + if ((jaccarddist = (1 << 16) * intersection_word(first->data[i], second->data[i])) > 0) { jaccarddist /= FFMAX(union_word(first->data[i], second->data[i]), 1); } + jaccarddist = (1 << 16) - jaccarddist; if (jaccarddist >= sc->thworddist) { if (++cwthcount > 2) { /* more than half (5/2) of distances are too wide */ -- 2.43.2 _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe". ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero 2024-05-05 22:30 [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero Gerion Entrup 2024-05-05 22:30 ` [FFmpeg-devel] [PATCH 2/2] libavfilter/signature_lookup: fix jaccard distance Gerion Entrup @ 2024-05-07 17:46 ` Michael Niedermayer 2024-05-24 10:33 ` Gerion Entrup 1 sibling, 1 reply; 7+ messages in thread From: Michael Niedermayer @ 2024-05-07 17:46 UTC (permalink / raw) To: FFmpeg development discussions and patches [-- Attachment #1.1: Type: text/plain, Size: 1079 bytes --] On Mon, May 06, 2024 at 12:30:39AM +0200, Gerion Entrup wrote: > --- > libavfilter/signature_lookup.c | 2 +- > 1 file changed, 1 insertion(+), 1 deletion(-) > > diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c > index a0ca818a9b..b39a3e225b 100644 > --- a/libavfilter/signature_lookup.c > +++ b/libavfilter/signature_lookup.c > @@ -128,7 +128,7 @@ static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseS > int jaccarddist, i, composdist = 0, cwthcount = 0; > for (i = 0; i < 5; i++) { > if ((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0) { > - jaccarddist /= union_word(first->data[i], second->data[i]); > + jaccarddist /= FFMAX(union_word(first->data[i], second->data[i]), 1); > } for which input data does this cause a division by 0 ? thx [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB I am the wisest man alive, for I know one thing, and that is that I know nothing. -- Socrates [-- Attachment #1.2: signature.asc --] [-- Type: application/pgp-signature, Size: 195 bytes --] [-- Attachment #2: Type: text/plain, Size: 251 bytes --] _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe". ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero 2024-05-07 17:46 ` [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero Michael Niedermayer @ 2024-05-24 10:33 ` Gerion Entrup 2024-05-24 21:03 ` Michael Niedermayer 0 siblings, 1 reply; 7+ messages in thread From: Gerion Entrup @ 2024-05-24 10:33 UTC (permalink / raw) To: FFmpeg development discussions and patches [-- Attachment #1.1: Type: text/plain, Size: 1329 bytes --] Am Dienstag, 7. Mai 2024, 19:46:28 MESZ schrieb Michael Niedermayer: > On Mon, May 06, 2024 at 12:30:39AM +0200, Gerion Entrup wrote: > > --- > > libavfilter/signature_lookup.c | 2 +- > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c > > index a0ca818a9b..b39a3e225b 100644 > > --- a/libavfilter/signature_lookup.c > > +++ b/libavfilter/signature_lookup.c > > @@ -128,7 +128,7 @@ static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseS > > int jaccarddist, i, composdist = 0, cwthcount = 0; > > for (i = 0; i < 5; i++) { > > if ((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0) { > > - jaccarddist /= union_word(first->data[i], second->data[i]); > > + jaccarddist /= FFMAX(union_word(first->data[i], second->data[i]), 1); > > } > > for which input data does this cause a division by 0 ? Sorry for the late answer. I missed your mail somehow. union_word counts the amount of one bits that are created when you are "or"ing the course signatures. So, when the underlying videos are so different that all bits of the created signatures are different, the "or"-operator will always return 0 and so also its sum (I have not tested this). Gerion [-- Attachment #1.2: This is a digitally signed message part. --] [-- Type: application/pgp-signature, Size: 659 bytes --] [-- Attachment #2: Type: text/plain, Size: 251 bytes --] _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe". ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero 2024-05-24 10:33 ` Gerion Entrup @ 2024-05-24 21:03 ` Michael Niedermayer 2024-05-26 15:08 ` Gerion Entrup 0 siblings, 1 reply; 7+ messages in thread From: Michael Niedermayer @ 2024-05-24 21:03 UTC (permalink / raw) To: FFmpeg development discussions and patches [-- Attachment #1.1: Type: text/plain, Size: 1998 bytes --] On Fri, May 24, 2024 at 12:33:11PM +0200, Gerion Entrup wrote: > Am Dienstag, 7. Mai 2024, 19:46:28 MESZ schrieb Michael Niedermayer: > > On Mon, May 06, 2024 at 12:30:39AM +0200, Gerion Entrup wrote: > > > --- > > > libavfilter/signature_lookup.c | 2 +- > > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > > > diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c > > > index a0ca818a9b..b39a3e225b 100644 > > > --- a/libavfilter/signature_lookup.c > > > +++ b/libavfilter/signature_lookup.c > > > @@ -128,7 +128,7 @@ static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseS > > > int jaccarddist, i, composdist = 0, cwthcount = 0; > > > for (i = 0; i < 5; i++) { > > > if ((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0) { > > > - jaccarddist /= union_word(first->data[i], second->data[i]); > > > + jaccarddist /= FFMAX(union_word(first->data[i], second->data[i]), 1); > > > } > > > > for which input data does this cause a division by 0 ? > > Sorry for the late answer. I missed your mail somehow. > union_word counts the amount of one bits that are created when you are "or"ing > the course signatures. So, when the underlying videos are so different that all > bits of the created signatures are different, the "or"-operator will always > return 0 and so also its sum (I have not tested this). the division only occurs if jaccarddist > 0 basically what iam asking is for which A and B do we have (A&B) != 0 && (A|B) == 0 or am i misreading the code ? thx [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB Awnsering whenever a program halts or runs forever is On a turing machine, in general impossible (turings halting problem). On any real computer, always possible as a real computer has a finite number of states N, and will either halt in less than N cycles or never halt. [-- Attachment #1.2: signature.asc --] [-- Type: application/pgp-signature, Size: 195 bytes --] [-- Attachment #2: Type: text/plain, Size: 251 bytes --] _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe". ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero 2024-05-24 21:03 ` Michael Niedermayer @ 2024-05-26 15:08 ` Gerion Entrup 2024-05-26 17:26 ` Michael Niedermayer 0 siblings, 1 reply; 7+ messages in thread From: Gerion Entrup @ 2024-05-26 15:08 UTC (permalink / raw) To: FFmpeg development discussions and patches [-- Attachment #1.1: Type: text/plain, Size: 1835 bytes --] Am Freitag, 24. Mai 2024, 23:03:37 MESZ schrieb Michael Niedermayer: > On Fri, May 24, 2024 at 12:33:11PM +0200, Gerion Entrup wrote: > > Am Dienstag, 7. Mai 2024, 19:46:28 MESZ schrieb Michael Niedermayer: > > > On Mon, May 06, 2024 at 12:30:39AM +0200, Gerion Entrup wrote: > > > > --- > > > > libavfilter/signature_lookup.c | 2 +- > > > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > > > > > diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c > > > > index a0ca818a9b..b39a3e225b 100644 > > > > --- a/libavfilter/signature_lookup.c > > > > +++ b/libavfilter/signature_lookup.c > > > > @@ -128,7 +128,7 @@ static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseS > > > > int jaccarddist, i, composdist = 0, cwthcount = 0; > > > > for (i = 0; i < 5; i++) { > > > > if ((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0) { > > > > - jaccarddist /= union_word(first->data[i], second->data[i]); > > > > + jaccarddist /= FFMAX(union_word(first->data[i], second->data[i]), 1); > > > > } > > > > > > for which input data does this cause a division by 0 ? > > > > Sorry for the late answer. I missed your mail somehow. > > union_word counts the amount of one bits that are created when you are "or"ing > > the course signatures. So, when the underlying videos are so different that all > > bits of the created signatures are different, the "or"-operator will always > > return 0 and so also its sum (I have not tested this). > > the division only occurs if jaccarddist > 0 > > basically what iam asking is for which A and B do we have > (A&B) != 0 && (A|B) == 0 > or am i misreading the code ? Hmm, valid point. Then, this patch should be unnecessary. Should I send 2/2 again without 1/2 then? Gerion [-- Attachment #1.2: This is a digitally signed message part. --] [-- Type: application/pgp-signature, Size: 659 bytes --] [-- Attachment #2: Type: text/plain, Size: 251 bytes --] _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe". ^ permalink raw reply [flat|nested] 7+ messages in thread
* Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero 2024-05-26 15:08 ` Gerion Entrup @ 2024-05-26 17:26 ` Michael Niedermayer 0 siblings, 0 replies; 7+ messages in thread From: Michael Niedermayer @ 2024-05-26 17:26 UTC (permalink / raw) To: FFmpeg development discussions and patches [-- Attachment #1.1: Type: text/plain, Size: 2285 bytes --] On Sun, May 26, 2024 at 05:08:09PM +0200, Gerion Entrup wrote: > Am Freitag, 24. Mai 2024, 23:03:37 MESZ schrieb Michael Niedermayer: > > On Fri, May 24, 2024 at 12:33:11PM +0200, Gerion Entrup wrote: > > > Am Dienstag, 7. Mai 2024, 19:46:28 MESZ schrieb Michael Niedermayer: > > > > On Mon, May 06, 2024 at 12:30:39AM +0200, Gerion Entrup wrote: > > > > > --- > > > > > libavfilter/signature_lookup.c | 2 +- > > > > > 1 file changed, 1 insertion(+), 1 deletion(-) > > > > > > > > > > diff --git a/libavfilter/signature_lookup.c b/libavfilter/signature_lookup.c > > > > > index a0ca818a9b..b39a3e225b 100644 > > > > > --- a/libavfilter/signature_lookup.c > > > > > +++ b/libavfilter/signature_lookup.c > > > > > @@ -128,7 +128,7 @@ static int get_jaccarddist(SignatureContext *sc, CoarseSignature *first, CoarseS > > > > > int jaccarddist, i, composdist = 0, cwthcount = 0; > > > > > for (i = 0; i < 5; i++) { > > > > > if ((jaccarddist = intersection_word(first->data[i], second->data[i])) > 0) { > > > > > - jaccarddist /= union_word(first->data[i], second->data[i]); > > > > > + jaccarddist /= FFMAX(union_word(first->data[i], second->data[i]), 1); > > > > > } > > > > > > > > for which input data does this cause a division by 0 ? > > > > > > Sorry for the late answer. I missed your mail somehow. > > > union_word counts the amount of one bits that are created when you are "or"ing > > > the course signatures. So, when the underlying videos are so different that all > > > bits of the created signatures are different, the "or"-operator will always > > > return 0 and so also its sum (I have not tested this). > > > > the division only occurs if jaccarddist > 0 > > > > basically what iam asking is for which A and B do we have > > (A&B) != 0 && (A|B) == 0 > > or am i misreading the code ? > > Hmm, valid point. Then, this patch should be unnecessary. > Should I send 2/2 again without 1/2 then? I didnt compare the code to the specification but if its a bugfix then yes of course thx [...] -- Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB During times of universal deceit, telling the truth becomes a revolutionary act. -- George Orwell [-- Attachment #1.2: signature.asc --] [-- Type: application/pgp-signature, Size: 195 bytes --] [-- Attachment #2: Type: text/plain, Size: 251 bytes --] _______________________________________________ ffmpeg-devel mailing list ffmpeg-devel@ffmpeg.org https://ffmpeg.org/mailman/listinfo/ffmpeg-devel To unsubscribe, visit link above, or email ffmpeg-devel-request@ffmpeg.org with subject "unsubscribe". ^ permalink raw reply [flat|nested] 7+ messages in thread
end of thread, other threads:[~2024-05-26 17:26 UTC | newest] Thread overview: 7+ messages (download: mbox.gz / follow: Atom feed) -- links below jump to the message on this page -- 2024-05-05 22:30 [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero Gerion Entrup 2024-05-05 22:30 ` [FFmpeg-devel] [PATCH 2/2] libavfilter/signature_lookup: fix jaccard distance Gerion Entrup 2024-05-07 17:46 ` [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero Michael Niedermayer 2024-05-24 10:33 ` Gerion Entrup 2024-05-24 21:03 ` Michael Niedermayer 2024-05-26 15:08 ` Gerion Entrup 2024-05-26 17:26 ` Michael Niedermayer
Git Inbox Mirror of the ffmpeg-devel mailing list - see https://ffmpeg.org/mailman/listinfo/ffmpeg-devel This inbox may be cloned and mirrored by anyone: git clone --mirror https://master.gitmailbox.com/ffmpegdev/0 ffmpegdev/git/0.git # If you have public-inbox 1.1+ installed, you may # initialize and index your mirror using the following commands: public-inbox-init -V2 ffmpegdev ffmpegdev/ https://master.gitmailbox.com/ffmpegdev \ ffmpegdev@gitmailbox.com public-inbox-index ffmpegdev Example config snippet for mirrors. AGPL code for this site: git clone https://public-inbox.org/public-inbox.git