Generate a Simple FFT

This SPIRAL script will generate a simple FFT of size 4. You can copy and paste it into the SPIRAL window to see the results.

opts := SpiralDefaults;
transform := DFT(4);
ruletree := RandomRuleTree(transform, opts);
icode := CodeRuleTree(ruletree, opts);
PrintCode("DFT4", icode, opts);

Let’s walk through it line by line, sometimes using other commands to look deeper into what is happening.

Set the controlling options.

spiral> opts := SpiralDefaults;
<Spiral options record>
spiral>

Sets the opts variable to the default set of options for SPIRAL. Later examples will set specific option values to modify the default behavior.

Specify the transform.

spiral> transform := DFT(4);
DFT(4, 1)
spiral> pm(transform);
[ [ 1, 1, 1, 1 ],
  [ 1, E(4), -1, -E(4) ],
  [ 1, -1, 1, -1 ],
  [ 1, -E(4), -1, E(4) ] ]
spiral>

DFT() creates a transform object for a discrete fourier transform of specified size.

pm() – print matrix – is a handy utility to print the matrix representation of a transform.

Generate a tree of breakdown rules.

spiral> ruletree := RandomRuleTree(transform, opts);
DFT_HW_CT( DFT(4, 1),
  DFT_Base( DFT(2, 1) ),
  DFT_Base( DFT(2, 1) ) )
spiral>

Builds the tree of smaller transforms that define the FFT. RandomRuleTree() randomly picks one of potentially very many valid rule trees.

Generate code.

spiral> icode := CodeRuleTree(ruletree, opts);
program(
   chain(
      func(TVoid, "init", [  ],
         chain()
      ),
      func(TVoid, "transform", [ Y, X ],
         decl([ t57, t58, t59, t60, t61, t62, t63, t64 ],
            chain(
               assign(t57, add(deref(X), deref(add(X, V(4))))),
               assign(t58, add(deref(add(X, V(1))), deref(add(X, V(5))))),
               assign(t59, sub(deref(X), deref(add(X, V(4))))),
               assign(t60, sub(deref(add(X, V(1))), deref(add(X, V(5))))),
               assign(t61, add(deref(add(X, V(2))), deref(add(X, V(6))))),
               assign(t62, add(deref(add(X, V(3))), deref(add(X, V(7))))),
               assign(t63, sub(deref(add(X, V(2))), deref(add(X, V(6))))),
               assign(t64, sub(deref(add(X, V(3))), deref(add(X, V(7))))),
               assign(deref(Y), add(t57, t61)),
               assign(deref(add(Y, V(1))), add(t58, t62)),
               assign(deref(add(Y, V(4))), sub(t57, t61)),
               assign(deref(add(Y, V(5))), sub(t58, t62)),
               assign(deref(add(Y, V(2))), sub(t59, t64)),
               assign(deref(add(Y, V(3))), add(t60, t63)),
               assign(deref(add(Y, V(6))), add(t59, t64)),
               assign(deref(add(Y, V(7))), sub(t60, t63))
            )
         )
      )
   )
)
spiral>

Creates the abstract code.

Produce the compileable C code.

spiral> PrintCode("DFT4", icode, opts);

/*
 * This code was generated by Spiral 8.0.0, www.spiral.net
 */

#include <include/omega64.h>

void init_DFT4() {
}

void DFT4(double  *Y, double  *X) {
    double t57, t58, t59, t60, t61, t62, t63, t64;
    t57 = (*(X) + *((X + 4)));
    t58 = (*((X + 1)) + *((X + 5)));
    t59 = (*(X) - *((X + 4)));
    t60 = (*((X + 1)) - *((X + 5)));
    t61 = (*((X + 2)) + *((X + 6)));
    t62 = (*((X + 3)) + *((X + 7)));
    t63 = (*((X + 2)) - *((X + 6)));
    t64 = (*((X + 3)) - *((X + 7)));
    *(Y) = (t57 + t61);
    *((Y + 1)) = (t58 + t62);
    *((Y + 4)) = (t57 - t61);
    *((Y + 5)) = (t58 - t62);
    *((Y + 2)) = (t59 - t64);
    *((Y + 3)) = (t60 + t63);
    *((Y + 6)) = (t59 + t64);
    *((Y + 7)) = (t60 - t63);
}
spiral>

PrintCode() generates the C code.