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.

.. code-block:: none

    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.

.. code-block:: none

    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.

.. code-block:: none

    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.

.. code-block:: none

    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.

.. code-block:: none

    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.
	
.. code-block:: C

    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.