[FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero

[FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero

[Gerion Entrup]

---
 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".

[FFmpeg-devel] [PATCH 2/2] libavfilter/signature_lookup: fix jaccard distance

[Gerion Entrup]

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".

Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero

[Michael Niedermayer]

[-- 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".

Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero

[Gerion Entrup]

[-- 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".

Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero

[Michael Niedermayer]

[-- 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".

Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero

[Gerion Entrup]

[-- 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".

Re: [FFmpeg-devel] [PATCH 1/2] libavfilter/signature_lookup: fix possible division by zero

[Michael Niedermayer]

[-- 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".