summaryrefslogtreecommitdiff
path: root/libavutil/tx.c
Commit message (Collapse)AuthorAge
* avutil/tx: print debug log at trace levelJames Almer2024-02-22
| | | | | | | The output of TX is extremely verbose and makes it harder to find other debug log messages, so print most of it at trace level. Signed-off-by: James Almer <jamrial@gmail.com>
* lavu/tx: correctly use a default scale parameter for all transform typesLynne2024-02-18
| | | | | | | This fixes the previous commit and adds more cases (DCT-I and DST-I). I am holding off on defining a scale parameter for FFTs as I'd like to use a complex value for them.
* av_tx_init: accept NULL scale for RDFTPeter Ross2024-02-15
| | | | | | | | | | | | Make av_tx_init() agree with documentation: * Real to complex and complex to real DFTs. * For the float and int32 variants, the scale type is 'float', while for * the double variant, it's a 'double'. If scale is NULL, 1.0 will be used * as a default. Reviewed-by: Lynne <dev@lynne.ee> Signed-off-by: Peter Ross <pross@xvid.org>
* avcodec/libaribb24,ttmlenc, avutil/tx: Remove redundant init of AVBPrintAndreas Rheinhardt2023-09-14
| | | | | | | | | An AVBPrint is initialized via av_bprint_init() (or av_bprint_init_for_buffer()) which expects uninitialized AVBPrints; it is therefore not necessary to zero them before the actual initialization. Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
* lavu/tx: add missing prints for the type of dctI/dstILynne2023-09-08
|
* lavu/tx: add real to real and real to imaginary RDFT transformsLynne2023-09-01
| | | | | | | These are in-place transforms, required for DCT-I and DST-I. Templated as the mod2 variant requires minor modifications, and is required specifically for DCT-I/DST-I.
* avutil/tx: Use proper deallocatorAndreas Rheinhardt2022-11-25
| | | | | | | | May fix the FATE failures on x64 Windows here: https://fate.ffmpeg.org/report.cgi?slot=x86_64-msvc17-windows-native&time=20221125130443 Reviewed-by: Lynne <dev@lynne.ee> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
* lavu/tx: add length decomposition functionLynne2022-11-24
| | | | | Rather than using a list of lengths supported, this goes a step beyond and uses all registered codelets to come up with a good decomposition.
* lavu/tx: refactor to explicitly track and convert lookup table orderLynne2022-11-24
| | | | Necessary for generalizing PFAs.
* lavu/tx: refactor and separate codelet list and prio codeLynne2022-11-24
|
* lavu/tx: improve transform tree loggingLynne2022-11-24
| | | | | Now prints the actual codelet size used, as well as the number of allowed factors.
* lavu/tx: allow codelets to specify a minimum number of matching factorsLynne2022-11-24
|
* lavu/tx: add ff_tx_clear_ctx()Lynne2022-11-24
| | | | | This function allows implementations to clean up a context after successfully initializing subcontexts.
* lavu/tx: generalize single-factor transformsLynne2022-11-24
| | | | Not that useful, but it gives us fast small odd-length transforms.
* avutil/tx: use a lower log level for the debug messagesJames Almer2022-11-08
| | | | | | | The amount of lines printed is too high for the verbose level, and the debug level is a better fit for their content. Signed-off-by: James Almer <jamrial@gmail.com>
* lavu/tx: remove special -1 inverted lookup modeLynne2022-09-23
| | | | It was somewhat hacky and unnecessary.
* lavu/tx: propagate the codelet flags into the contextLynne2022-09-10
| | | | The field is documented as a combination of both.
* x86/tx_float: implement inverse MDCT AVX2 assemblyLynne2022-09-06
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit implements an iMDCT in pure assembly. This is capable of processing any mod-8 transforms, rather than just power of two, but since power of two is all we have assembly for currently, that's what's supported. It would really benefit if we could somehow use the C code to decide which function to jump into, but exposing function labels from assebly into C is anything but easy. The post-transform loop could probably be improved. This was somewhat annoying to write, as we must support arbitrary strides during runtime. There's a fast branch for stride == 4 bytes and a slower one which uses vgatherdps. Zen 3 benchmarks for stride == 4 for old (av_imdct_half) vs new (av_tx): 128pt: 2811 decicycles in av_tx (imdct),16775916 runs, 1300 skips 3082 decicycles in av_imdct_half,16776751 runs, 465 skips 256pt: 4920 decicycles in av_tx (imdct),16775820 runs, 1396 skips 5378 decicycles in av_imdct_half,16776411 runs, 805 skips 512pt: 9668 decicycles in av_tx (imdct),16775774 runs, 1442 skips 10626 decicycles in av_imdct_half,16775647 runs, 1569 skips 1024pt: 19812 decicycles in av_tx (imdct),16777144 runs, 72 skips 23036 decicycles in av_imdct_half,16777167 runs, 49 skips
* x86/tx_float: add support for calling assembly functions from assemblyLynne2022-09-06
| | | | | | Needed for the next patch. We get this for the extremely small cost of a branch on _ns functions, which wouldn't be used anyway with assembly.
* lavu/tx: implement aarch64 NEON SIMD FFTLynne2022-08-25
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | The fastest fast Fourier transform in not just the west, but the world, now for the most popular toy ISA. On a high level, it follows the design of the AVX2 version closely, with the exception that the input is slightly less permuted as we don't have to do lane switching with the input on double 4pt and 8pt. On a low level, the lack of subadd/addsub instructions REALLY penalizes any attempt at writing an FFT. That single register matters a lot, and reloading it simply takes unacceptably long. In x86 land, vendors would've noticed developers need this. In ARM land, you get a badly designed complex multiplication instruction we cannot use, that's not present on 95% of devices. Because only compilers matter, right? Future optimization options are very few, perhaps better register management to use more ld1/st1s. All timings below are in cycles: A53: Length | C | New (lavu) | Old (lavc) | FFTW ------ |-------------|-------------|-------------|----- 4 | 842 | 420 | 1210 | 1460 8 | 1538 | 1020 | 1850 | 2520 16 | 3717 | 1900 | 3700 | 3990 32 | 9156 | 4070 | 8289 | 8860 64 | 21160 | 9931 | 18600 | 19625 128 | 49180 | 23278 | 41922 | 41922 256 | 112073 | 53876 | 93202 | 101092 512 | 252864 | 122884 | 205897 | 207868 1024 | 560512 | 278322 | 458071 | 453053 2048 | 1295402 | 775835 | 1038205 | 1020265 4096 | 3281263 | 2021221 | 2409718 | 2577554 8192 | 8577845 | 4780526 | 5673041 | 6802722 Apple M1 New - Total for len 512 reps 2097152 = 1.459141 s Old - Total for len 512 reps 2097152 = 2.251344 s FFTW - Total for len 512 reps 2097152 = 1.868429 s New - Total for len 1024 reps 4194304 = 6.490080 s Old - Total for len 1024 reps 4194304 = 9.604949 s FFTW - Total for len 1024 reps 4194304 = 7.889281 s New - Total for len 16384 reps 262144 = 10.374001 s Old - Total for len 16384 reps 262144 = 15.266713 s FFTW - Total for len 16384 reps 262144 = 12.341745 s New - Total for len 65536 reps 8192 = 1.769812 s Old - Total for len 65536 reps 8192 = 4.209413 s FFTW - Total for len 65536 reps 8192 = 3.012365 s New - Total for len 131072 reps 4096 = 1.942836 s Old - Segfaults FFTW - Total for len 131072 reps 4096 = 3.713713 s Thanks to wbs for some simplifications, assembler fixes and a review and to jannau for giving it a look.
* avutil/mem_internal: Fix headersAndreas Rheinhardt2022-08-24
| | | | | | | Including avassert.h is unnecessary since commit 786be70e28fe739b8e49893fa13ae4652a68d1ea. Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@outlook.com>
* lavu/tx: optimize and simplify inverse MDCTsLynne2022-08-16
| | | | | | | | | | | | | | | | Convert the input from a scatter to a gather instead, which is faster and better for SIMD. Also, add a pre-shuffled exptab version to avoid gathering there at all. This doubles the exptab size, but the speedup makes it worth it. In SIMD, the exptab will likely be purged to a higher cache anyway because of the FFT in the middle, and the amount of loads stays identical. For a 960-point inverse MDCT, the speedup is 10%. This makes it possible to write sane and fast SIMD versions of inverse MDCTs.
* lavu/tx: make slow ISA extension penalties smarterLynne2022-05-21
| | | | | | | | Instead of having a fixed -64 prio penalty, make the penalties more granular. As the prio is based on the register size in bits, decrementing it by 129 makes AVX SLOW functions be avoided in favor of any SSE versions.
* lavu/tx: wrap missed string in NULL_IF_CONFIG_SMALLLynne2022-02-07
| | | | It's the only one that isn't defined through the macros used elsewhere.
* lavu/tx: disable debugging information when CONFIG_SMALLLynne2022-02-07
|
* lavu/tx: do not unconditionally free subcontexts if initialization failsLynne2022-01-29
| | | | | | | | | If a codelet initializes 2 subtransforms, and the second one fails, the failure would free all subcontexts. Instead, if there are subcontexts still left, don't free the array. If all initializations fail, the init() function will return, and reset_ctx() from the previous step will clean up all contained subtransforms.
* lavu/tx: reset subcontext pointer if initialization failsLynne2022-01-29
| | | | Thanks to mkver for pointing this out.
* lavu/tx: print debug info even if no transforms are foundLynne2022-01-28
|
* avutil/tx: add null pointer check after av_malloczSteven Liu2022-01-28
| | | | | | | Fix CID: 1497863 there will get null pointer in attempt to initialize each if alloc memory failed. Signed-off-by: Steven Liu <liuqi05@kuaishou.com>
* avutil/tx: remove deadcode of the control flowSteven Liu2022-01-28
| | | | | | | | | Fix CID: 1497864 The control flow should return ENOSYS if nb_cd_matches is 0 at before and the ret equal AVERROR(ENOMEM) or goto end label, so remove the last control flow if (ret >= 0) before end label. Signed-off-by: Steven Liu <liuqi05@kuaishou.com>
* lavu/tx: clean up CPU flags checkLynne2022-01-27
| | | | Just makes it more readable.
* x86/tx_float: do not build tx_float_init.c if x86 assembly is disabledLynne2022-01-27
| | | | | | | | This broke builds with --disable-mmx, which also disabled assembly entirely, but ARCH_X86 was still true, so the init file tried to find assembly that didn't exist. Instead of checking for architecture, check if external x86 assembly is enabled.
* lavu/tx: do not mix declarations and codeLynne2022-01-26
|
* lavu/tx: add an RDFT implementationLynne2022-01-26
| | | | | | | | | | | | | | | | | | RDFTs are full of conventions that vary between implementations. What I've gone for here is what's most common between both fftw, avcodec's rdft and what we use, the equivalent of which is DFT_R2C for forward and IDFT_C2R for inverse. The other 2 conventions (IDFT_R2C and DFT_C2R) were not used at all in our code, and their names are also not appropriate. If there's a use for either, we can easily add a flag which would just flip the sign on one exptab. For some unknown reason, possibly to allow reusing FFT's exp tables, av_rdft's C2R output is 0.5x lower than what it should be to ensure a proper back-and-forth conversion. This code outputs its real samples at the correct level, which matches FFTW's level, and allows the user to change the level and insert arbitrary multiplies for free by setting the scale option.
* lavu/tx: rewrite internal code as a tree-based codelet constructorLynne2022-01-26
| | | | | | | | | | This commit rewrites the internal transform code into a constructor that stitches transforms (codelets). This allows for transforms to reuse arbitrary parts of other transforms, and allows transforms to be stacked onto one another (such as a full iMDCT using a half-iMDCT which in turn uses an FFT). It also permits for each step to be individually replaced by assembly or a custom implementation (such as an ASIC).
* avutil/tx: add a return at the end of non-void functionsJames Almer2021-08-06
| | | | | | Fixes compilation with GCC 11 when configured with --disable-optimizations Signed-off-by: James Almer <jamrial@gmail.com>
* avutil/tx: avoid negative left shiftsMichael Niedermayer2021-06-18
| | | | | | | | Fixes: left shift of negative value -1 Fixes: 33736/clusterfuzz-testcase-minimized-ffmpeg_AV_CODEC_ID_SIREN_fuzzer-6657785795313664 Found-by: continuous fuzzing process https://github.com/google/oss-fuzz/tree/master/projects/ffmpeg Signed-off-by: Michael Niedermayer <michael@niedermayer.cc>
* lavu/x86: add FFT assemblyLynne2021-04-24
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit adds a pure x86 assembly SIMD version of the FFT in libavutil/tx. The design of this pure assembly FFT is pretty unconventional. On the lowest level, instead of splitting the complex numbers into real and imaginary parts, we keep complex numbers together but split them in terms of parity. This saves a number of shuffles in each transform, but more importantly, it splits each transform into two independent paths, which we process using separate registers in parallel. This allows us to keep all units saturated and lets us use all available registers to avoid dependencies. Moreover, it allows us to double the granularity of our per-load permutation, skipping many expensive lookups and allowing us to use just 4 loads per register, rather than 8, or in case FMA3 (and by extension, AVX2), use the vgatherdpd instruction, which is at least as fast as 4 separate loads on old hardware, and quite a bit faster on modern CPUs). Higher up, we go for a bottom-up construction of large transforms, foregoing the traditional per-transform call-return recursion chains. Instead, we always start at the bottom-most basis transform (in this case, a 32-point transform), and continue constructing larger and larger transforms until we return to the top-most transform. This way, we only touch the stack 3 times per a complete target transform: once for the 1/2 length transform and two times for the 1/4 length transform. The combination algorithm we use is a standard Split-Radix algorithm, as used in our C code. Although a version with less operations exists (Steven G. Johnson and Matteo Frigo's "A modified split-radix FFT with fewer arithmetic operations", IEEE Trans. Signal Process. 55 (1), 111–119 (2007), which is the one FFTW uses), it only has 2% less operations and requires at least 4x the binary code (due to it needing 4 different paths to do a single transform). That version also has other issues which prevent it from being implemented with SIMD code as efficiently, which makes it lose the marginal gains it offered, and cannot be performed bottom-up, requiring many recursive call-return chains, whose overhead adds up. We go through a lot of effort to minimize load/stores by keeping as much in registers in between construcring transforms. This saves us around 32 cycles, on paper, but in reality a lot more due to load/store aliasing (a load from a memory location cannot be issued while there's a store pending, and there are only so many (2 for Zen 3) load/store units in a CPU). Also, we interleave coefficients during the last stage to save on a store+load per register. Each of the smallest, basis transforms (4, 8 and 16-point in our case) has been extremely optimized. Our 8-point transform is barely 20 instructions in total, beating our old implementation 8-point transform by 1 instruction. Our 2x8-point transform is 23 instructions, beating our old implementation by 6 instruction and needing 50% less cycles. Our 16-point transform's combination code takes slightly more instructions than our old implementation, but makes up for it by requiring a lot less arithmetic operations. Overall, the transform was optimized for the timings of Zen 3, which at the time of writing has the most IPC from all documented CPUs. Shuffles were preferred over arithmetic operations due to their 1/0.5 latency/throughput. On average, this code is 30% faster than our old libavcodec implementation. It's able to trade blows with the previously-untouchable FFTW on small transforms, and due to its tiny size and better prediction, outdoes FFTW on larger transforms by 11% on the largest currently supported size.
* checkasm: add av_tx FFT SIMD testing codeLynne2021-04-24
| | | | | | This sadly required making changes to the code itself, due to the same context needing to be reused for both versions. The lookup table had to be duplicated for both versions.
* lavu/tx: add parity revtab generator versionLynne2021-04-24
| | | | This will be used for SIMD support.
* lavu/tx: minor code style improvements and additional commentsLynne2021-04-24
|
* lavu/tx: invert permutation lookupsLynne2021-02-27
| | | | | | | | | | | | | out[lut[i]] = in[i] lookups were 4.04 times(!) slower than out[i] = in[lut[i]] lookups for an out-of-place FFT of length 4096. The permutes remain unchanged for anything but out-of-place monolithic FFT, as those benefit quite a lot from the current order (it means there's only 1 lookup necessary to add to an offset, rather than a full gather). The code was based around non-power-of-two FFTs, so this wasn't benchmarked early on.
* lavu/tx: simplify in-place permute search functionLynne2021-02-27
|
* avutil/tx: Fix declaration after statementAndreas Rheinhardt2021-02-22
| | | | | Reviewed-by: Paul B Mahol <onemda@gmail.com> Signed-off-by: Andreas Rheinhardt <andreas.rheinhardt@gmail.com>
* lavu/tx: support in-place FFT transformsLynne2021-02-21
| | | | | | | | | | | | | | | | | | | | | | | | | | | | | This commit adds support for in-place FFT transforms. Since our internal transforms were all in-place anyway, this only changes the permutation on the input. Unfortunately, research papers were of no help here. All focused on dry hardware implementations, where permutes are free, or on software implementations where binary bloat is of no concern so storing dozen times the transforms for each permutation and version is not considered bad practice. Still, for a pure C implementation, it's only around 28% slower than the multi-megabyte FFTW3 in unaligned mode. Unlike a closed permutation like with PFA, split-radix FFT bit-reversals contain multiple NOPs, multiple simple swaps, and a few chained swaps, so regular single-loop single-state permute loops were not possible. Instead, we filter out parts of the input indices which are redundant. This allows for a single branch, and with some clever AVX512 asm, could possibly be SIMD'd without refactoring. The inplace_idx array is guaranteed to never be larger than the revtab array, and in practice only requires around log2(len) entries. The power-of-two MDCTs can be done in-place as well. And it's possible to eliminate a copy in the compound MDCTs too, however it'll be slower than doing them out of place, and we'd need to dirty the input array.
* lavu/tx: implement 32 bit fixed point FFT and MDCTLynne2020-02-13
| | | | | | | | | | | | | | | | | | | | Required minimal changes to the code so made sense to implement. FFT and MDCT tested, the output of both was properly rounded. Fun fact: the non-power-of-two fixed-point FFT and MDCT are the fastest ever non-power-of-two fixed-point FFT and MDCT written. This can replace the power of two integer MDCTs in aac and ac3 if the MIPS optimizations are ported across. Unfortunately the ac3 encoder uses a 16-bit fixed point forward transform, unlike the encoder which uses a 32bit inverse transform, so some modifications might be required there. The 3-point FFT is somewhat less accurate than it otherwise could be, having minor rounding errors with bigger transforms. However, this could be improved later, and the way its currently written is the way one would write assembly for it. Similar rounding errors can also be found throughout the power of two FFTs as well, though those are more difficult to correct. Despite this, the integer transforms are more than accurate enough.
* lavu/tx: add support for double precision FFT and MDCTLynne2019-08-02
| | | | | | | Simply moves and templates the actual transforms to support an additional data type. Unlike the float version, which is equal or better than libfftw3f, double precision output is bit identical with libfftw3.
* avutil/tx: should check against (*ctx)Ruiling Song2019-05-16
| | | | | | ctx is a pointer to pointer here. Signed-off-by: Ruiling Song <ruiling.song@intel.com>
* avutil/tx: fix forward compound non-mod-15 based MDCTsLynne2019-05-16
| | | | | There was a hardcoded value left. Wasn't caught earlier as no code uses compound forward mod-3/5 MDCTs yet.
* libavutil: add an FFT & MDCT implementationLynne2019-05-15
This commit adds a new API to libavutil to allow for arbitrary transformations on various types of data. This is a partly new implementation, with the power of two transforms taken from libavcodec/fft_template, the 5 and 15-point FFT taken from mdct15, while the 3-point FFT was written from scratch. The (i)mdct folding code is taken from mdct15 as well, as the mdct_template code was somewhat old, messy and not easy to separate. A notable feature of this implementation is that it allows for 3xM and 5xM based transforms, where M is a power of two, e.g. 384, 640, 768, 1280, etc. AC-4 uses 3xM transforms while Siren uses 5xM transforms, so the code will allow for decoding of such streams. A non-exaustive list of supported sizes: 4, 8, 12, 16, 20, 24, 32, 40, 48, 60, 64, 80, 96, 120, 128, 160, 192, 240, 256, 320, 384, 480, 512, 640, 768, 960, 1024, 1280, 1536, 1920, 2048, 2560... The API was designed such that it allows for not only 1D transforms but also 2D transforms of certain block sizes. This was partly on accident as the stride argument is required for Opus MDCTs, but can be used in the context of a 2D transform as well. Also, various data types would be implemented eventually as well, such as "double" and "int32_t". Some performance comparisons with libfftw3f (SIMD disabled for both): 120: 22353 decicycles in fftwf_execute, 1024 runs, 0 skips 21836 decicycles in compound_fft_15x8, 1024 runs, 0 skips 128: 22003 decicycles in fftwf_execute, 1024 runs, 0 skips 23132 decicycles in monolithic_fft_ptwo, 1024 runs, 0 skips 384: 75939 decicycles in fftwf_execute, 1024 runs, 0 skips 73973 decicycles in compound_fft_3x128, 1024 runs, 0 skips 640: 104354 decicycles in fftwf_execute, 1024 runs, 0 skips 149518 decicycles in compound_fft_5x128, 1024 runs, 0 skips 768: 109323 decicycles in fftwf_execute, 1024 runs, 0 skips 164096 decicycles in compound_fft_3x256, 1024 runs, 0 skips 960: 186210 decicycles in fftwf_execute, 1024 runs, 0 skips 215256 decicycles in compound_fft_15x64, 1024 runs, 0 skips 1024: 163464 decicycles in fftwf_execute, 1024 runs, 0 skips 199686 decicycles in monolithic_fft_ptwo, 1024 runs, 0 skips With SIMD we should be faster than fftw for 15xM transforms as our fft15 SIMD is around 2x faster than theirs, even if our ptwo SIMD is slightly slower. The goal is to remove the libavcodec/mdct15 code and deprecate the libavcodec/avfft interface once aarch64 and x86 SIMD code has been ported. New code throughout the project should use this API. The implementation passes fate when used in Opus, AAC and Vorbis, and the output is identical with ATRAC9 as well.
generated by cgit v1.2.3 (git 2.39.1) at 2024-07-01 09:10:35 +0000