[Libre-soc-dev] [RFC] REMAP, SHAPE, complex (full) FFT

[Jacob Lifshay]

On Sun, Jul 18, 2021 at 2:58 PM Luke Kenneth Casson Leighton
<lkcl at lkcl.net> wrote:
>
> i've moved on to DCT now, not the version that uses FFT followed by
> extraction of real coefficients.
>
> most DCT algorithms unfortunately are either expressed inline as a
> massive batch of unintelligible hand-created MULADDs, or as assembler,
> or as recursive algorithms.
>
> i found *one* iterative butterfly implementation in c++ and it
> completely failed to work.
>
> currently struggling with converting a recursive implementation to iterative.
>
> i could really do with some assistance.

I wasn't able to find any really good examples, but I did find some
slightly-bitrotted code in the AV1 reference library:
https://aomedia.googlesource.com/aom/+/refs/heads/master/tools/txfm_analyzer/txfm_gen_code.cc

It isn't included in the CMake build system, so needs to be manually
built. It generates C code to do a bunch of DCTs and inverse DCTs
needed for AV1 (or at least something similar).

Apply the below patch to switch it to generate generic C instead of
SSE intrinsics, then build using:
g++ -o txfm_gen_code tools/txfm_analyzer/txfm_gen_code.cc
tools/txfm_analyzer/txfm_graph.cc -I ../aom-av1
'-DPI=(3.141592653589793238462643383279502884)' -include stdint.h

Patch:
diff --git a/tools/txfm_analyzer/txfm_gen_code.cc
b/tools/txfm_analyzer/txfm_gen_code.cc
index 7c5400b91..abf899060 100644
--- a/tools/txfm_analyzer/txfm_gen_code.cc
+++ b/tools/txfm_analyzer/txfm_gen_code.cc
@@ -570,7 +570,7 @@ void gen_hybrid_code(CODE_TYPE code_type,
TYPE_TXFM txfm_type, int node_num) {
 }

 int main(int argc, char **argv) {
-  CODE_TYPE code_type = CODE_TYPE_SSE4_1;
+  CODE_TYPE code_type = CODE_TYPE_C;
   for (int txfm_type = TYPE_DCT; txfm_type < TYPE_LAST; txfm_type++) {
     for (int node_num = 4; node_num <= 64; node_num *= 2) {
       gen_hybrid_code(code_type, (TYPE_TXFM)txfm_type, node_num);

Jacob