Re: [FFmpeg-devel] [PATCH] avutil/mathematics: correct documentation for av_gcd

[Clément Bœsch]

On Thu, Oct 29, 2015 at 07:49:44PM -0400, Ganesh Ajjanagadde wrote:
[...]
> although you did explain to me where optimizations could be useful at
> an algorithmic level privately, I take this as an opportunity to
> request for general comments on places that people think could benefit
> from performance at a C/algorithmic level (NOT asm/simd stuff for me
> personally): yet another ping for Clement.

Mmh... without SIMD let me think...

You may look at the TODO in libavfilter/f_ebur128.c. There is a PRE-filter
and a RLB-filter to merge into one to reduce computation time. This is an
already solved mathematical problem. You may want to have a look, it's
most likely a good way to speed up that filter algorithmically.

Then maybe you can look into adding threading support in some codecs or
filters.

No other idea that do not involve SIMD right now.

[...]

-- 
Clément B.


signature.asc
Description: PGP signature
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: correct documentation for av_gcd

[Michael Niedermayer]

On Tue, Oct 27, 2015 at 08:18:34PM -0400, Ganesh Ajjanagadde wrote:
> av_gcd is now always defined regardless of input. This documents this
> change in the "documented API". Two benefits (closely related):
> 1. The function is robust, and there is no need to worry about INT64_MIN, etc.
> 
> 2. Clients of av_gcd, like av_reduce, can now be made fully correct. 
> Currently,
> av_reduce can trigger undefined behavior if e.g num is INT64_MIN due to
> integer overflow in the FFABS. Furthermore, this undefined behavior is
> completely undocumented, and could be a fuzzer's paradise. The FFABS was 
> needed in the past as
> av_gcd was undefined for negative inputs. In order to make av_reduce
> robust, it is essential to guarantee that av_gcd works for all int64_t.
> 
> Signed-off-by: Ganesh Ajjanagadde 
> ---
>  libavutil/mathematics.h | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
> 
> diff --git a/libavutil/mathematics.h b/libavutil/mathematics.h
> index ac94488..6fc2577 100644
> --- a/libavutil/mathematics.h
> +++ b/libavutil/mathematics.h
> @@ -77,9 +77,9 @@ enum AVRounding {
>  };
>  
>  /**
> - * Return the greatest common divisor of a and b.
> - * If both a and b are 0 or either or both are <0 then behavior is
> - * undefined.
> + * Compute the greatest common divisor of a and b.
> + *
> + * @return gcd of a and b up to sign; if a and b are both zero returns 0
>   */
>  int64_t av_const av_gcd(int64_t a, int64_t b);

LGTM

thanks

[...]
-- 
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope


signature.asc
Description: Digital signature
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: correct documentation for av_gcd

[Ganesh Ajjanagadde]

On Fri, Oct 30, 2015 at 12:16 PM, Michael Niedermayer
 wrote:
> On Tue, Oct 27, 2015 at 08:18:34PM -0400, Ganesh Ajjanagadde wrote:
>> av_gcd is now always defined regardless of input. This documents this
>> change in the "documented API". Two benefits (closely related):
>> 1. The function is robust, and there is no need to worry about INT64_MIN, 
>> etc.
>>
>> 2. Clients of av_gcd, like av_reduce, can now be made fully correct. 
>> Currently,
>> av_reduce can trigger undefined behavior if e.g num is INT64_MIN due to
>> integer overflow in the FFABS. Furthermore, this undefined behavior is
>> completely undocumented, and could be a fuzzer's paradise. The FFABS was 
>> needed in the past as
>> av_gcd was undefined for negative inputs. In order to make av_reduce
>> robust, it is essential to guarantee that av_gcd works for all int64_t.
>>
>> Signed-off-by: Ganesh Ajjanagadde 
>> ---
>>  libavutil/mathematics.h | 6 +++---
>>  1 file changed, 3 insertions(+), 3 deletions(-)
>>
>> diff --git a/libavutil/mathematics.h b/libavutil/mathematics.h
>> index ac94488..6fc2577 100644
>> --- a/libavutil/mathematics.h
>> +++ b/libavutil/mathematics.h
>> @@ -77,9 +77,9 @@ enum AVRounding {
>>  };
>>
>>  /**
>> - * Return the greatest common divisor of a and b.
>> - * If both a and b are 0 or either or both are <0 then behavior is
>> - * undefined.
>> + * Compute the greatest common divisor of a and b.
>> + *
>> + * @return gcd of a and b up to sign; if a and b are both zero returns 0
>>   */
>>  int64_t av_const av_gcd(int64_t a, int64_t b);
>
> LGTM
>
> thanks

pushed, thanks

>
> [...]
> --
> Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB
>
> Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope
>
> ___
> 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

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: correct documentation for av_gcd

[Michael Niedermayer]

On Wed, Oct 28, 2015 at 10:49:08PM -0400, Ganesh Ajjanagadde wrote:
> On Wed, Oct 28, 2015 at 10:09 AM, Ganesh Ajjanagadde
>  wrote:
> > On Tue, Oct 27, 2015 at 8:18 PM, Ganesh Ajjanagadde
> >  wrote:
> >> av_gcd is now always defined regardless of input. This documents this
> >> change in the "documented API". Two benefits (closely related):
> >> 1. The function is robust, and there is no need to worry about INT64_MIN, 
> >> etc.
> >>
> >> 2. Clients of av_gcd, like av_reduce, can now be made fully correct. 
> >> Currently,
> >> av_reduce can trigger undefined behavior if e.g num is INT64_MIN due to
> >> integer overflow in the FFABS. Furthermore, this undefined behavior is
> >> completely undocumented, and could be a fuzzer's paradise. The FFABS was 
> >> needed in the past as
> >> av_gcd was undefined for negative inputs. In order to make av_reduce
> >> robust, it is essential to guarantee that av_gcd works for all int64_t.
> >>
> >> Signed-off-by: Ganesh Ajjanagadde 
> >> ---
> >>  libavutil/mathematics.h | 6 +++---
> >>  1 file changed, 3 insertions(+), 3 deletions(-)
> >>
> >> diff --git a/libavutil/mathematics.h b/libavutil/mathematics.h
> >> index ac94488..6fc2577 100644
> >> --- a/libavutil/mathematics.h
> >> +++ b/libavutil/mathematics.h
> >> @@ -77,9 +77,9 @@ enum AVRounding {
> >>  };
> >>
> >>  /**
> >> - * Return the greatest common divisor of a and b.
> >> - * If both a and b are 0 or either or both are <0 then behavior is
> >> - * undefined.
> >> + * Compute the greatest common divisor of a and b.
> >> + *
> >> + * @return gcd of a and b up to sign; if a and b are both zero returns 0
> >>   */
> >>  int64_t av_const av_gcd(int64_t a, int64_t b);
> >>
> >> --
> >> 2.6.2
> >>
> >
> > Patch dropped for now, undefined behavior is still possible with
> > av_gcd: take a and b to be both INT64_MIN. Need to examine this a
> > little more closely to make it robust without losing performance.
> 
> Request to reconsider; patch making av_gcd more robust sent.

I guess if the stricter API doesnt prevent any possibly optimizations
then the change is a good idea

[...]
-- 
Michael GnuPG fingerprint: 9FF2128B147EF6730BADF133611EC787040B0FAB

Why not whip the teacher when the pupil misbehaves? -- Diogenes of Sinope


signature.asc
Description: Digital signature
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: correct documentation for av_gcd

[Ganesh Ajjanagadde]

On Tue, Oct 27, 2015 at 8:18 PM, Ganesh Ajjanagadde
 wrote:
> av_gcd is now always defined regardless of input. This documents this
> change in the "documented API". Two benefits (closely related):
> 1. The function is robust, and there is no need to worry about INT64_MIN, etc.
>
> 2. Clients of av_gcd, like av_reduce, can now be made fully correct. 
> Currently,
> av_reduce can trigger undefined behavior if e.g num is INT64_MIN due to
> integer overflow in the FFABS. Furthermore, this undefined behavior is
> completely undocumented, and could be a fuzzer's paradise. The FFABS was 
> needed in the past as
> av_gcd was undefined for negative inputs. In order to make av_reduce
> robust, it is essential to guarantee that av_gcd works for all int64_t.
>
> Signed-off-by: Ganesh Ajjanagadde 
> ---
>  libavutil/mathematics.h | 6 +++---
>  1 file changed, 3 insertions(+), 3 deletions(-)
>
> diff --git a/libavutil/mathematics.h b/libavutil/mathematics.h
> index ac94488..6fc2577 100644
> --- a/libavutil/mathematics.h
> +++ b/libavutil/mathematics.h
> @@ -77,9 +77,9 @@ enum AVRounding {
>  };
>
>  /**
> - * Return the greatest common divisor of a and b.
> - * If both a and b are 0 or either or both are <0 then behavior is
> - * undefined.
> + * Compute the greatest common divisor of a and b.
> + *
> + * @return gcd of a and b up to sign; if a and b are both zero returns 0
>   */
>  int64_t av_const av_gcd(int64_t a, int64_t b);
>
> --
> 2.6.2
>

Patch dropped for now, undefined behavior is still possible with
av_gcd: take a and b to be both INT64_MIN. Need to examine this a
little more closely to make it robust without losing performance.
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel

Re: [FFmpeg-devel] [PATCH] avutil/mathematics: correct documentation for av_gcd

[Ganesh Ajjanagadde]

On Wed, Oct 28, 2015 at 10:09 AM, Ganesh Ajjanagadde
 wrote:
> On Tue, Oct 27, 2015 at 8:18 PM, Ganesh Ajjanagadde
>  wrote:
>> av_gcd is now always defined regardless of input. This documents this
>> change in the "documented API". Two benefits (closely related):
>> 1. The function is robust, and there is no need to worry about INT64_MIN, 
>> etc.
>>
>> 2. Clients of av_gcd, like av_reduce, can now be made fully correct. 
>> Currently,
>> av_reduce can trigger undefined behavior if e.g num is INT64_MIN due to
>> integer overflow in the FFABS. Furthermore, this undefined behavior is
>> completely undocumented, and could be a fuzzer's paradise. The FFABS was 
>> needed in the past as
>> av_gcd was undefined for negative inputs. In order to make av_reduce
>> robust, it is essential to guarantee that av_gcd works for all int64_t.
>>
>> Signed-off-by: Ganesh Ajjanagadde 
>> ---
>>  libavutil/mathematics.h | 6 +++---
>>  1 file changed, 3 insertions(+), 3 deletions(-)
>>
>> diff --git a/libavutil/mathematics.h b/libavutil/mathematics.h
>> index ac94488..6fc2577 100644
>> --- a/libavutil/mathematics.h
>> +++ b/libavutil/mathematics.h
>> @@ -77,9 +77,9 @@ enum AVRounding {
>>  };
>>
>>  /**
>> - * Return the greatest common divisor of a and b.
>> - * If both a and b are 0 or either or both are <0 then behavior is
>> - * undefined.
>> + * Compute the greatest common divisor of a and b.
>> + *
>> + * @return gcd of a and b up to sign; if a and b are both zero returns 0
>>   */
>>  int64_t av_const av_gcd(int64_t a, int64_t b);
>>
>> --
>> 2.6.2
>>
>
> Patch dropped for now, undefined behavior is still possible with
> av_gcd: take a and b to be both INT64_MIN. Need to examine this a
> little more closely to make it robust without losing performance.

Request to reconsider; patch making av_gcd more robust sent.
___
ffmpeg-devel mailing list
ffmpeg-devel@ffmpeg.org
http://ffmpeg.org/mailman/listinfo/ffmpeg-devel