1. 09 Dec, 2015 1 commit
  2. 02 Dec, 2015 1 commit
  3. 01 Dec, 2015 1 commit
  4. 29 Oct, 2015 1 commit
    • Ganesh Ajjanagadde's avatar
      avutil/mathematics: make av_gcd more robust · b7fb7c45
      Ganesh Ajjanagadde authored
      This ensures that no undefined behavior is invoked, while retaining
      identical return values in all cases and at no loss of performance
      (identical asm on clang and gcc).
      Essentially, this patch exchanges undefined behavior with implementation
      defined behavior, a strict improvement.
      
      Rationale:
      1. The ideal solution is to have the return type a uint64_t. This
      unfortunately requires an API change.
      2. The only pathological behavior happens if both arguments are
      INT64_MIN, to the best of my knowledge. In such a case, the
      implementation defined behavior is invoked in the sense that UINT64_MAX
      is interpreted as INT64_MIN, which any reasonable implementation will
      do. In any case, any usage where both arguments are INT64_MIN is a
      fuzzer anyway.
      3. Alternatives of checking, etc require branching and lose performance
      for no concrete gain - no client cares about av_gcd's actual value when
      both args are INT64_MIN. Even if it did, on sane platforms (e.g all the
      ones FFmpeg cares about), it produces a correct gcd, namely INT64_MIN.
      Reviewed-by: 's avatarMichael Niedermayer <michael@niedermayer.cc>
      Signed-off-by: 's avatarGanesh Ajjanagadde <gajjanagadde@gmail.com>
      b7fb7c45
  5. 11 Oct, 2015 1 commit
    • Ganesh Ajjanagadde's avatar
      avutil/mathematics: speed up av_gcd by using Stein's binary GCD algorithm · 971d12b7
      Ganesh Ajjanagadde authored
      This uses Stein's binary GCD algorithm:
      https://en.wikipedia.org/wiki/Binary_GCD_algorithm
      to get a roughly 4x speedup over Euclidean GCD on standard architectures
      with a compiler intrinsic for ctzll, and a roughly 2x speedup otherwise.
      At the moment, the compiler intrinsic is used on GCC and Clang due to
      its easy availability.
      
      Quick note regarding overflow: yes, subtractions on int64_t can, but the
      llabs takes care of that. The llabs is also guaranteed to be safe, with
      no annoying INT64_MIN business since INT64_MIN being a power of 2, is
      shifted down before being sent to llabs.
      
      The binary GCD needs ff_ctzll, an extension of ff_ctz for long long (int64_t). On
      GCC, this is provided by a built-in. On Microsoft, there is a
      BitScanForward64 analog of BitScanForward that should work; but I can't confirm.
      Apparently it is not available on 32 bit builds; so this may or may not
      work correctly. On Intel, per the documentation there is only an
      intrinsic for _bit_scan_forward and people have posted on forums
      regarding _bit_scan_forward64, but often their documentation is
      woeful. Again, I don't have it, so I can't test.
      
      As such, to be safe, for now only the GCC/Clang intrinsic is added, the rest
      use a compiled version based on the De-Bruijn method of Leiserson et al:
      http://supertech.csail.mit.edu/papers/debruijn.pdf.
      
      Tested with FATE, sample benchmark (x86-64, GCC 5.2.0, Haswell)
      with a START_TIMER and STOP_TIMER in libavutil/rationsl.c, followed by a
      make fate.
      
      aac-am00_88.err:
      builtin:
      714 decicycles in av_gcd,    4095 runs,      1 skips
      
      de-bruijn:
      1440 decicycles in av_gcd,    4096 runs,      0 skips
      
      previous:
      2889 decicycles in av_gcd,    4096 runs,      0 skips
      Signed-off-by: 's avatarGanesh Ajjanagadde <gajjanagadde@gmail.com>
      Signed-off-by: 's avatarMichael Niedermayer <michael@niedermayer.cc>
      971d12b7
  6. 28 Aug, 2015 1 commit
  7. 02 Jun, 2014 4 commits
  8. 03 May, 2014 1 commit
  9. 04 Jan, 2014 1 commit
  10. 03 Jan, 2014 1 commit
  11. 02 Jan, 2013 1 commit
  12. 26 Oct, 2012 2 commits
  13. 12 Oct, 2012 2 commits
  14. 11 Oct, 2012 1 commit
  15. 06 Jun, 2012 1 commit
  16. 20 Feb, 2012 1 commit
  17. 28 Jun, 2011 1 commit
  18. 11 May, 2011 1 commit
  19. 19 Mar, 2011 1 commit
  20. 03 Jul, 2010 1 commit
  21. 09 Jun, 2010 1 commit
  22. 20 Apr, 2010 1 commit
  23. 09 Mar, 2010 1 commit
  24. 07 Feb, 2010 1 commit
  25. 09 Nov, 2009 1 commit
  26. 09 Mar, 2009 1 commit
  27. 01 Feb, 2009 1 commit
  28. 28 Jan, 2009 1 commit
  29. 27 Jan, 2009 1 commit
  30. 24 Jan, 2009 1 commit
  31. 17 Jan, 2009 1 commit
  32. 21 Jan, 2008 1 commit
  33. 10 Jan, 2008 1 commit
  34. 08 Jan, 2008 1 commit
  35. 23 Nov, 2007 1 commit